競技プログラミングにおける包除原理問題まとめ - はまやんはまやんはまやん

競技プログラミングにおける包除原理問題まとめ - はまやんはまやんはまやん

包除原理 包除原理についての偉大なスライド 数え上げをする時の定理 ここが詳しい ここの包除原理の欄...概要を表示 包除原理 包除原理についての偉大なスライド 数え上げをする時の定理 ここが詳しい ここの包除原理の欄も詳しい 基本は状態系包除原理 状態系包除原理を個数に注目して個数系包除原理にするテクがある（抽象化による状態圧縮） 例 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であるときの組み合わせ数」のように更に状態を圧縮出来る場合もある これ 順列の組み合わせ数は、組合せの組み合わせ数と包除原理から求めるテク