P3158 [CQOI2011]放棋子
斯德哥尔摩
2018-08-04 23:26:45
[P3158 [CQOI2011]放棋子](https://www.luogu.org/problemnew/show/P3158)
本蒟蒻表示把$DP$与数论放在一起真~~有趣~~恶心。。。
因为不同颜色的棋子不能在同一行或者同一列，所以每种颜色的棋子的摆放是相对独立的。
于是考虑设计这么一个状态$dp[i][j][k]$，表示用前$k$种颜色的棋子占领了任意$i$行$j$列的方案数，则：（假设第$k$种棋子有$a[k]$枚）
$dp[i][j][k]=\sum_{l=0}^{i-1}\sum_{r=0}^{j-1}f[l][r][k-1]\times $用$a[k]$枚棋子占领$(i-l)$行$(j-r)$列的方案数$\times C_{n - l}^{i - l} \times C_{m-r}^{j-r}((i-l)\times(j-r)\ge a[k])$
其它都好处理，但“用$a[k]$枚棋子占领$(i−l)$行$(j−r)$列的方案数”似乎不是那么容易直接求。
考虑再设一个状态$g[i][j][k]$，表示任意$k$枚同色棋子占领了任意$i$行$j$列的方案数。
则$g[i][j][k]$就为总方案数$-$不合法方案数（实际上有没有被占领的行或列的方案数），即：
$$g[i][j][k]=C_{i\times j}^k-\sum_{l=1}^i\sum_{r=1}^jg[l][r][k]\times C_i^l\times C_j^r,l<i||r<j,i\times j\ge k$$
我们预处理$g[i][j][k]$，则$f[i][j][k]$的转移就可表示为：
$$f[i][j][k]=\sum_{l=0}^{i-1}\sum_{r=0}^{j-1}f[l][r][k - 1]\times g[i-l][j-r][a[k]]\times C_{n-l}^{i-l}\times C_{m-r}^{j-r}((i-l)\times(j-r)\ge a[k])$$
不一定要每行每列都占领，但棋子要全放完，答案就为：
$$\sum_{i=1}^n\sum_{j=1}^mf[i][j][c]$$
时间复杂度$O(n^2m^2c)$。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 40
#define MAXM 20
#define MAXK 910
#define MOD 1000000009LL
using namespace std;
int n,m,c,S;
long long ans=0;
long long g[MAXN][MAXN],triangle[MAXK][MAXK],dp[MAXN][MAXN][MAXM];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
int u,v,w;
for(int k=1;k<=c;k++){
int w=read();
memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(i*j>=w){
g[i][j]=triangle[i*j][w];
for(int l=1;l<=i;l++)
for(int r=1;r<=j;r++)
if(l<i||r<j)
g[i][j]=(g[i][j]-g[l][r]*triangle[i][l]%MOD*triangle[j][r]%MOD+MOD)%MOD;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int l=0;l<=i;l++)
for(int r=0;r<=j;r++){
int u=i-l,v=j-r;
if(u*v>=w)
dp[i][j][k]=(dp[i][j][k]+dp[l][r][k-1]*g[u][v]%MOD*triangle[n-l][u]%MOD*triangle[m-r][v]%MOD)%MOD;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=(ans+dp[i][j][c])%MOD;
printf("%lld\n",ans);
}
void init(){
n=read();m=read();c=read();
S=n*m;
for(int i=0;i<=S;i++)triangle[i][0]=1;
for(int i=1;i<=S;i++)
for(int j=1;j<=i;j++)
triangle[i][j]=(triangle[i-1][j-1]+triangle[i-1][j])%MOD;
dp[0][0][0]=1;
}
int main(){
init();
work();
return 0;
}
```