2011-08-31 プログラミングコンテストチャレンジブック 4-1 その2 4-1 「より複雑な数学的問題」の続きです。 連立線形合同式 ai*x = bi (mod mi) (1<=i<=n) 中国余剰定理 連立線形合同式の ai を全て 1、mi を互いに素とする 合成数を法とする式はその素因数を法とする式に分解できる n! mod m n! = a p^e (p 素数) とした時 e = Σ(n/p^i) a (mod p) = - (n mod p)! nCk mod p 数え上げ 包除原理 1からnの整数のうち ai(1<=i<=m)で割り切れるものの数 n/ai の和から共通の倍数を除外。集合で考える メビウス関数 周期的でない文字列の数え上げ 包除原理が使えるが計算量が大きすぎる メビウス関数を作って約数の数だけ計算して間に合わせる 対称性のある数え上げ - 回転や反転して一致するものを同じと見做す時の数え上げ ポリアの数え上げ定理 - 回転などの操作を施して変化しないような塗り方を数え上げて平均をとる だいぶはしょりました。メビウス関数についてはあまりちゃんと理解していないので機会があれば別の本で勉強してみたいです。
