Inclusion and Exclusion

天下一プログラマーコンテスト2013 決勝D: 天下一ボディービルコンテスト

http://tenka1-2013-final.contest.atcoder.jp/tasks/tenka1_2013_final_d包除原理の良問です。目標を達成しないスケジュールを考えます。それはどれかの筋肉が目標を達成しなければいいです。 なのでS:=目標を達成しない筋肉の集合、f(S):=Sについて何通り…

メビウス関数

周期的なものの数え上げの時に役立ちそう。蟻本の周期的でない文字列の数え上げを考えましょう。 周期1,2,3,4,...みたいな感じでNの約数をすべて列挙して包除原理をすれば求まりますが、約数は100コとか200コになる可能性があるのでこれでは間に合いません。…

高速ゼータ変換、高速メビウス変換

包除原理で活躍する二つのアルゴリズムです。この2つの記事がわかりやすかったです。 高速メビウス変換について - 篠突く雨の日記 ゼータ変換とメビウス変換 - pekempeyのブログメビウス:∩→∪ ゼータ :∪→∩と覚えればいいです。たぶんメビウスの方がよく使うと…