hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング 包除原理 包除原理についての偉大なスライド 数え上げをする時の定理 ここが詳しい ここの包除原理の欄も詳しい 基本は状態系包除原理 状態系包除原理を個数に注目して個数系包除原理にするテクがある（抽象化による状態圧縮） 例 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)に削減できる 問題… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2017%2F04%2F17%2F161345" title="競技プログラミングにおける包除原理問題まとめ - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2017-04-17 16:13:45 rich https://blog.hamayanhamayan.com/entry/2017/04/17/161345 1.0 100%