包除原理
- 数え上げをする時の定理 ここが詳しい ここの包除原理の欄も詳しい
- 基本は状態系包除原理
- 状態系包除原理を個数に注目して個数系包除原理にするテクがある(抽象化による状態圧縮)
- 例
- n(AorBorC) = n(A) + n(B) + n(C) - n(A&B) - n(B&C) - n(C&A) + n(A&B&C)
- もし、「dp[i] := i個の&で表現できる組み合わせ数」が高速に計算できれば、
- n(AorBorC) = dp[1] - dp[2] + dp[3]
- 事前計算が高速にできれば包除原理計算部分をO(2^N)からO(N)に削減できる
- 問題によっては「dp[i] := &でつながれている個数の偶奇がiであるときの組み合わせ数」のように更に状態を圧縮出来る場合もある これ
- 順列の組み合わせ数は、組合せの組み合わせ数と包除原理から求めるテクがある 問題1 問題2
- 約数系包除原理というのもある(まだ完全に理解できてないかも)
- drkenさんの記事のまとめ DEGwerさんの数え上げテクニック集 に記述がある
- 上の包除原理とは少し異なる
- DEGwerさんの資料抜粋
- あるパラメタがkの倍数である場合
- dp[k]を確定する時に重複して数えているkの倍数を引く
- dp[k] = (kに対する何らかの計算)- Σ{lはkの倍数}dp[l]
- 計算量はエラトステネスの篩と同じ形になるのでO(NlogN)
- 計算はkを大きい順からやっていく。k以上から倍数の数を引いていくことで丁度kを求める感じ
- あるパラメタがkの約数である
- dp[k]を確定する時に重複して数えているkの約数を引く
- dp[k] = (kに対する何らかの計算)- Σ{lはkの約数}dp[l]
- 計算量はO(Nf(N))、f(x)はxの約数の個数(約数の個数は10^9で10^3くらい)
- 計算はkを小さい順からやっていく。これも、k以下から約数の数を引いていくことで丁度kを求める感じ
- あるパラメタがkの倍数である場合
- 包除原理に見られる(-1)^kは出てこない
- 状態系包除原理においてメビウス関数を使って(-1)^k部分を決定するテクがある
- n(2) + n(3) + n(5) - n(6) - n(10) - n(15) + n(30)みたいな計算の+,-,0を決定できる
- 具体的には
- 0 : 平方数が因数に含まれる(包除原理での計算外としてみなせる)
- -1 : 素因数の個数が奇数
- 1 : 素因数の個数が偶数
- メビウス関数ってO(NlogN)以外の高速な計算法ある?
問題
- (普通の)状態系包除原理
- yukicoder No.316 もっと刺激的なFizzBuzzをください
- yukicoder No.546 オンリー・ワン 解説
- 蟻本p.264の包除原理問題
- Educational Codeforces Round 20 F. Coprime Subsequences
- CodeChef Chef and Digits
- ABC003 D. AtCoder社の冬
- CSA71 Losing Nim
- AC Uncommon
- 約数を扱う包除原理(約数系包除原理かもしれないけど、自分の視点では状態系包除原理。約数が出てくるだけで考え方が異なる)
- 個数系包除原理
- 約数系包除原理
- 状態系包除原理においてメビウス関数を使って(-1)^k部分を決定するテク
工事中
http://kmjp.hatenablog.jp/search?q=包除原理
http://kimiyuki.net/categories/inclusion-exclusion-principle/
http://pekempey.hatenablog.com/search?q=包除原理
以下、解説