1. P2051 [AHOI2009] 中国象棋
一格一格进行考虑做 DP 想不出来，考虑到一行实际上只需要选两格进行操作，因此可以一行一行操作。
设 \(f_{i,j,k}\) 表示考虑到第 \(i\) 行，有 \(m-j-k\) 列有 \(0\) 个棋子，有 \(j\) 列有 \(1\) 个棋子，有 \(k\) 列有 \(2\) 个棋子。边界条件为 \(f_{0,0,0}=1\)。考虑 \(i-1\to i\) 的转移分类讨论。
- 第 \(i\) 行放 \(0\) 个：不变。
- 第 \(i\) 行放 \(1\) 个：可以在 \(j+1\) 列里面选一列变成 \(2\) 个棋子的，\(0\) 个 \(\to 1\) 个同理。
- 第 \(i\) 行放 \(2\) 个：可以选择两列 \(0\)，选择两列 \(1\) 或选择一列 \(0\)、一列 \(1\) 进行放置，分别分类讨论，乘上选择其中几列的方案数即可。
最终没有规定有几列 \(1/2\)，因此答案是 \(\sum_{i,j} f_{n,i,j}\)
状态数 \(O(n^3)\)，转移 \(O(1)\)，时间复杂度 \(O(n^3)\)，空间复杂度 \(O(n^3)\)。
2. P3158 [CQOI2011] 放棋子
设 \(f_{\mathrm{id},i,j}\) 表示考虑了前 \(\mathrm{id}\) 种颜色，现在已经占据了 \(i\) 行 \(j\) 列。边界条件 \(f_{0,0,0}=1\)。
那么枚举第 \(i-1\) 列占据了 \(p\) 行 \(q\) 列，那么第 \(\mathrm{id}\) 种颜色就占据了 \(\mathrm{dx}=i-p\) 行，\(\mathrm{dy}=j-q\) 列。先从剩下的 \(n-p\) 行里选这么多行出来：\(\binom{n-p}{\mathrm{dx}}\binom{m-q}{\mathrm{dy}}\)，然后再乘上 \(\mathrm{dx}\) 行 \(\mathrm{dy}\) 列放 \(a_{\mathrm{id}}\) 个棋子的方案数，记作 \(g_{\mathrm{id},\mathrm{dx},\mathrm{dy}}\)。
考虑求 \(g_{\mathrm{id},i,j}\)，首先直接从 \(i\) 行 \(j\) 列里面选 \(\mathrm{id}\) 个出来：\(\binom{i\times j}{\mathrm{id}}\)。但是有可能实际只占据了 \(p\) 行 \(q\) 列，可能的方案是 \(g_{\mathrm{id},p,q}\times \binom i p\times \binom j q\)，容斥减去即可。
状态数 \(O(nmc)\)，转移 \(O(nm)\)，时间复杂度 \(O(n^2m^2c)\)，空间复杂度 \(O(nmc)\)。
3. AT_abc180_f [ABC180F] Unbranched
容斥的另一种体现：差分。
当恰好连通块最大为 \(L\) 不好做时，考虑转换为最多为 \(L\)，减去最多为 \(L-1\) 的答案。
设 \(f_{i,j}\) 表示考虑了 \(i\) 个点 \(j\) 条边且每个连通块的大小都不超过 \(L\) 的方案数。边界条件为 \(f_{0,0}=1\)。
考虑 \(\to i,j\) 转移，枚举当前连通块的大小 \(k\)。考虑链的情况，则需要 \(k-1\) 条边：\(f_{i-k,j-k+1}\to f_{i,j}\)。如果这条链的点直接在剩下的点里面随便选的话，可能会选出 \(1-2-3,4-5-6\) 和 \(4-5-6,1-2-3\) 两种本质相同的情况。解决方案就是强制选当前未选的点的最小点。然后选好点只有，有 \(k!\) 种排列方式。除掉 \(1-2\) 和 \(2-1\) 这样重复的排列情况，综上：
接着环的情况也是一样的，只不过要多选一条边，还要除去环同构的情况（\(1-2-3-1\) 和 \(2-3-1-2\)）。
细节是大小为 \(1\) 的链和 \(2\) 的环没有算出来两个颠倒的的情况，不需要 \(\div 2\)。
状态数 \(O(NM)\)，转移 \(O(L)\)，时间复杂度 \(O(NML)\)，空间复杂度 \(O(NM)\)。