[CQOI2011]放棋子
题目描述
在一个 \(m\) 行 \(n\) 列的棋盘里放一些彩色的棋子，使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列，有多少种方法？
例如，\(n=m=3\)，有两个白棋子和一个灰棋子，下面左边两种方法都是合法的，但右边两种都是非法的。
\(1\le n,m\le 30\)，\(1\le c\le 10\)，总棋子数 \(\le \max (250,n\times m)\)。
思路点拨
计数问题考虑 \(dp\) ，这是本题的难点。因为数据范围的误导不好想到这个。我们看看我们需要定义那些状态，由于每一行，每一列只能填一种颜色，所以行列要记录。又因为我们需要一个个将元素插入棋盘中，所以插入到了那种颜色的棋子也是必要的。最终我们获得了初步的状态： \(f[i][j][k]\) 表示填到了第 \(i\) 中棋子，已经有 \(j\) 行，\(k\) 列的棋盘上使用棋子。
接下来考虑转移吧，我们可以枚举每一中颜色的棋子的 "统治范围"，也就是那些行列只包含这种颜色。可以得到转移式：
\[f[i][j][k]=\sum_{x=0}^j \sum_{y=0}^k f[i-1][x][y]\times C_{n-x}^{j-x} C_{m-y}^{k-y} \times w_{i-x,j-y} \]先解释一下 \(C_{n-x}^{j-x} C_{m-y}^{k-y}\) ,这是因为转移中，对于第 \(i\) 中颜色，它的统治范围是 \(i-x\) 行，\(j-y\) 列。那么我们显然是要从剩余的 \(n-x\) 行， \(m-y\) 列中选取的。转移式中还有一个转移的贡献 \(w_{i,j}\) ,相信读者们可以猜出来这是什么意思： $w_{x,y} $ 表示在一个 \(x\times y\) 的矩阵中填入 全部的 颜色 \(i\) 棋子的方案数。
Q:为什么是一个 \(x \times y\) 的矩阵呢？
A:这是因为我们转移时枚举了 \(x,y\) ,也就是棋子 \(i\) 的统治范围，那么我们多出的行数就是 \(i-x\)行， \(j-y\) 列。显然，在这些行列中可以使用的格子只有 \((i-x) \times (j-y )\) 这么多。
有的童鞋就想（一开始的我），这不是直接 \(C_{xy}^{cnt_i} =w_{x,y}\) （其中 \(cnt_i\) 表示颜色 \(i\) 的数量）就可以了吗？然后给出了如下代码：
f[0][0][0]=1;
for(int k=1;k<=col;k++)
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
for(int x=0;x<=i;x++)
for(int y=0;y<=j;y++)
f[k][i][j]=(f[k][i][j]+f[k-1][x][y]*C((i-x)*(jy),a[k])%mod*C(i,x)*C(j,y)%mod)%mod;
cout<<f[col][n][m];
OK啊这只有 $50 $ 分（这么多我已经很满意了）。
这就是因为，刚刚我们的 \(w\) 的定义不够严谨。如果在这 \(x \times y\) 的矩阵中，有某一行或者某一列没有放棋子，那么这样会算重的。为什么会算重呢？如果一行没有东西，那么在别的转移中我是不是也可以多选出这一行，那么这样不就会有问题吗？这和我们的定义是有一定出入的。这一点比较难被发现。我们重新定义 \(w_{x,y}\) 吧，就是加上每一行每一列都 必须有 棋子的方案。
这样不好搞，因为每一行列都有 至少 一个棋子的限制。这样的问题我们很容易想到使用二项式反演转换成一般的问题。我们定义 \(f(x)\) 表示 刚好 \(x\) 行满足条件的方案数。 \(g(x)\) 表示 不超过 \(x\) 行满足条件的方案数。那么有：
\[g(x)=\sum_{i=0}^x C_{x}^i f(x) \]反演得：
\[f(x)=\sum_{i=0}^x (-1)^{x-i} C_{x}^i g(x) \]考虑 \(g(x)\) 得求法。我们先补充完整 \(g(x)\) 得定义：\(g(x)\) 表示 不超过 \(x\) 行满足条件，全部 \(y\) 列都满足条件得方案数。我们在此基础上设， \(h(y)\) 表示在 不超过 \(x\) 行满足条件，不超过 \(y\) 行满足条件得方案数。
那么有：
\[h(y)=\sum_{i=0}^{y} C_{y}^i g(i) \]反演的：
\[g(y)=\sum_{i=0}^{y} (-1)^{y-i}C_{y}^i h(i) \]我们发现 \(h(y)\) 的取值十分简单求出，就是 \(C_{xy}^{cnt_i}\) ，\(cnt_i\) 表示颜色 \(i\) 的数量，为了节省变量名，下文称 \(cnt\) 。
我们将刚刚的式子回代，那么就有：
\[f(x)=\sum_{i=0}^x\sum_{j=0}^{y} (-1)^{x-i+y-j}C_{x}^{i}C_{y}^{j}C_{ij}^{cnt} \]这个式子 \(O(nm)\) 求就可以了。每一次转移我们都需要求出每一个 \(w_{x,y}\) 的值域。所以这部分在每一次转移的时候是 \(O((nm)^2)\) 的。
现在我们会求出转移时的贡献 \(w\) 了，那么转移应该是会写与懒得写的区别了：
f[0][0][0]=1;
for(int k=1;k<=col;k++){
memset(g,0,sizeof(g));
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
for(int x=0;x<=i;x++)
for(int y=0;y<=j;y++)
g[i][j]=(g[i][j]+(C[i][x]*C[j][y]%mod*pw[i-x]*pw[j-y]+mod)%mod*C[x*y][a[k]])%mod;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
for(int x=0;x<=i;x++)
for(int y=0;y<=j;y++)
f[k][i][j]=(f[k][i][j]+f[k-1][x][y]*g[i-x][j-y]%mod*C[n-x][i-x]%mod*C[m-y][j-y]%mod)%mod;
}
时空复杂度计算
我们的 \(dp\) ,一共有 \(c\) 轮，每一次转移 \(O((nm)^2)\) ，预处理 \(O((nm)^2)\) 。总时间 \(O(cn^2m^2)\) 。
空间不会爆就完了。
标签：满足条件,cnt,P3158,times,棋子,sum,CQOI2011,转移 From： https://www.cnblogs.com/Diavolo/p/17467483.html