[CQOI2011] 放棋子
本题有一个性质，棋子间互不关联，又因为数据范围小，很容易 \(dp\)
记 \(f_{p,i,j}\) 表示考虑前 \(p\) 种颜色，放了 \(i\) 行 \(j\) 列的方案数
则枚举 \(p\) 放了几行几列，有
\[f_{p,i,j} = \sum_{k=0}^{i-1} \sum_{l=0}^{j-1} \begin{pmatrix} n-k \\ i-k \\ \end{pmatrix} \begin{pmatrix} m-l \\ j-l \\ \end{pmatrix}f_{p-1,k,l} \times g_{p,i-k,j-l}
\]
\(g_{p,i,j}\) 表示第 \(p\) 种颜色棋子放 \(i\) 行 \(j\) 列的方案数，直接算不好算，可以用总数减去不合法方案数，则
\[g_{p,i,j} = \begin{pmatrix} i \times j \\ a_p \\ \end{pmatrix} - \sum_{k=1}^{i} \sum_{l=1}^{j} [i \ne k 且 j \ne l] \begin{pmatrix} i \\ k \\ \end{pmatrix} \begin{pmatrix} j \\ l \\ \end{pmatrix} g_{p,k,l}
\]
最后注意边界
图计数
首先发现图由若干个链和环组成，连通块大小恰好为 \(l\) 不好求，考虑转化为连通块大小 \(\le l\)，则答案为 \(solve(l) - solve(l-1)\)
可以定义状态 \(f_{i,j}\) 表示选了 \(i\) 个点和 \(j\) 条边的方案数，则枚举添加的连通块大小即可，注意一元链和二元环的情况
(\(x\) 个点的链的总数为 \(\frac{x!}{2}\), \(x\) 个点的环的总数有 \(\frac{(x-1)!}{2}\))
转移方程为
\[f_{i,j} = \sum_{k=1}^{l} f_{i-k,j-(k-1)}
\]