不错的组合计数题。
因为黑车和白车不能在同一行或者同一列,所以可以考虑枚举黑车有 \(i\) 行 \(k\) 列的位置放,白车有 \(j\) 行 \(l\) 列的位置放。如果设 \(f_{i,j,k}\) 为 \(i\) 行 \(j\) 列的棋盘,需要放 \(k\) 个车,且 每一行每一列都必须放车的方案数 ,答案即为:
\[\sum\limits_{i=1}^n \sum\limits_{j=1}^{n-i} \sum\limits_{k=1}^m \sum\limits_{l=1}^{m-k} \dbinom{n}{i} \dbinom{n-i}{j} \dbinom{m}{k} \dbinom{m-k}{l} f_{i,k,B} f_{j,l,W} \]考虑如何求 \(f_{i,j,k}\)。考虑容斥,枚举 至少 \(x\) 行 \(y\) 列没有车,其他的行和列不管。那么:
\[f_{i,j,k} = \sum\limits_{x=0}^i \sum\limits_{y=0}^j \dbinom{i}{x} \dbinom{j}{y} \dbinom{(i-x) \times (j-y)}{k} \]于是这题就做完了。总时间复杂度 \(O(n^2m^2)\)。
标签:AtCoder,Rooks,dbinom,limits,Contest,传送门,sum,Beginner From: https://www.cnblogs.com/zltzlt-blog/p/16974335.html