メモ
ある条件を満たすようなものを数え上げるとき、そのままでは状態が大きくなってしまうことがある。
片方の条件を固定して、もう片方の条件について包除原理を行うことでうまく数え上げられることがある。
例1
onlinejudge.u-aizu.ac.jp
この問題は、O(N)かけて赤い頂点の数を固定すると、以下の二つの条件を両方満たすような辺の貼り方の通り数を求める問題に帰着される。
- すべての赤い頂点は一つ以上の黒い頂点に接続している
- すべての黒い頂点は一つ以上の赤い頂点に接続している
これらの二つの条件は独立ではないため、単純なDPをするには
- 条件を満たす赤の頂点の個数
- 条件を満たす黒の頂点の個数
- 条件を満たさない赤の頂点の個数
- 条件を満たさない黒の頂点の個数
が必要となり、状態数が大きくなりすぎてしまう。
ところで、二つ目の条件「すべての黒い頂点は一つ以上の赤い頂点に接続している」は「赤い頂点に接続していない黒い頂点はない（ちょうど0個）」と言い換えることができる。
「赤い頂点に接続していない黒い頂点の個数がK個以上」であるような対象は場合の数を利用して求められるから、二つ目の条件のみを考えたときについては包除原理を用いて対象を数え上げることができる。
ここで、一つ目の条件を固定する。つまり、注目する対象として、一つ目の条件を満たしているものだけを考える。
すると、「すべての赤い頂点は一つ以上の黒い頂点に接続している」かつ「赤い頂点に接続していない黒い頂点の個数がK個以上」であるものを数え上げることができれば、元の条件を満たしているものも数え上げられることがわかる。これはKのみに依存するから、O(N)で数え上げることができる。
したがって、この問題をO(N^2)で解くことができた。
例2
atcoder.jp
この問題は、N個の要素からなる集合Uに対して、
- Mより小さいバス停が含まれている要素がK個以下である
ようなものを数え上げる問題に帰着される。
これは各集合の空きを状態としてDPをすることで求められるが、状態数が大きくなりすぎてしまう。
ここで
- Uの部分集合Sに対して、Sに含まれるすべての要素にMより小さいバス停が含まれていない
ようなものを数え上げることで、メビウス変換を用いて、すべての部分集合について「その部分集合以外のすべての要素にMより小さいバス停が含まれているような通り数」を求められることに着目する
また、後者の条件は前者の条件とは独立になっている。
したがって、前者の条件を固定した上で、後者の条件について包除原理を行うことで、この問題を解くことができる。
例3
atcoder.jp
これはかなりそのままで、前者の条件を固定した上で後者の条件を満たさないものがK個以上のものの通り数をDPで求めると、包除原理で解くことができる
まとめ
集合を制限しても包除原理が動くの、非自明感があってむずかしいね
