202509 组合数学与计数类 DP 笔记

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$ 行里选这么多行出来：$(\genfrac{}{}{0ex}{}{n-p}{\mathrm{dx}})(\genfrac{}{}{0ex}{}{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}$ 个出来：$(\genfrac{}{}{0ex}{}{i\times j}{\mathrm{id}})$。但是有可能实际只占据了 $p$ 行 $q$ 列，可能的方案是 $g_{\mathrm{id},p,q}\times (\genfrac{}{}{0ex}{}{i}{p})\times (\genfrac{}{}{0ex}{}{j}{q})$，容斥减去即可。

状态数 $O(nmc)$，转移 $O(nm)$，时间复杂度 $O(n^2{m}^{2}c)$，空间复杂度 $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$ 这样重复的排列情况，综上：

$$f_{i,j}\leftarrow f_{i,j}+f_{i-k,j-k+1}\times (\genfrac{}{}{0ex}{}{n-i+k-1}{k-1})\times k!÷2$$

接着环的情况也是一样的，只不过要多选一条边，还要除去环同构的情况（$1-2-3-1$ 和 $2-3-1-2$）。

$$f_{i,j}\leftarrow f_{i,j}+f_{i-k,j-k}\times (\genfrac{}{}{0ex}{}{n-i+k-1}{k-1})\times k!÷2÷k$$

细节是大小为 $1$ 的链和 $2$ 的环没有算出来两个颠倒的的情况，不需要 $÷2$。

状态数 $O(NM)$，转移 $O(L)$，时间复杂度 $O(NML)$，空间复杂度 $O(NM)$。