题意：在一个m行n列的棋盘里放一些彩色的棋子，使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列。有多少祌方法？
解法：这道题不会做，太菜了qwq。题解是看洛谷大佬的。
设C是组合数，f[i][j][k]:代表前k种棋子合法地恰好占领i行j列
那么得到状态转移方程：f[i][j][k]=sigma f[ki][kj][k-1] * C[n-ki][i-ki] * C[m-kj][j-kj] * a[k]个棋子恰好占领i-ki行j-kj列的方案数。 这个式子的意思是我们枚举前k-1种棋子的占领情况是行占领ki行列占领kj列，那么第k种棋子就能占领i-ki行j-kj列，我们选出这i-ki/j-kj之后乘上通知颜色棋子a[k]个占领这i-ki/j-kj的方案数。
我们发现前面都都比较好算，唯独 a[k]个棋子恰好占领i-ki行j-kj列的方案数 这一项难算。
那么我们就考虑单独先预处理出这一项，设g[i][j][k]:代表k个同色棋子恰好占领了i行j列 ；
那么写出状态转移方程：g[i][j][k]=C[i*j][k] - sigma g[ki][kj][k] * C[i][i-ki] * C[j][j-kj] ；式子的意思是总的方案数减去不合法方案数，即同样是k个棋子却没有占满i行j列。
那么我们预处理出C数组和g数组，就可以获得AC了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100+10; 4 const int P=1e9+9; 5 typedef long long LL; 6 int n,m,c,a[N]; 7 int C[N*10][N*10],f[N][N][N*10],g[N][N][N*10]; 8 //g[i][j][k]:代表k个同色棋子恰好占领了i行j列 9 //f[i][j][k]:代表前k种棋子合法地恰好占领i行j列 10 11 void prework() { 12 for (int i=0;i<=1000;i++) 13 for (int j=0;j<=1000;j++) 14 if (j==0 || i==j) C[i][j]=1; 15 else C[i][j]=(C[i-1][j-1]+C[i-1][j])%P; 16 } 17 18 int main() 19 { 20 cin>>n>>m>>c; 21 int sum=0; 22 for (int i=1;i<=c;i++) scanf("%d",&a[i]),sum+=a[i]; 23 prework(); 24 25 for (int i=1;i<=n;i++) 26 for (int j=1;j<=m;j++) 27 for (int k=1;k<=sum;k++) { 28 if (i*j<k) continue; 29 g[i][j][k]=C[i*j][k]; 30 for (int ki=1;ki<=i;ki++) 31 for (int kj=1;kj<=j;kj++) 32 if (ki!=i || kj!=j) g[i][j][k]=(g[i][j][k]-(LL)g[ki][kj][k]*C[i][ki]%P*C[j][kj]%P)%P; 33 g[i][j][k]=(g[i][j][k]%P+P)%P; 34 } 35 36 LL ans=0; 37 f[0][0][0]=1; 38 for (int i=1;i<=n;i++) 39 for (int j=1;j<=m;j++) 40 for (int k=1;k<=c;k++) { 41 for (int ki=0;ki<=i;ki++) 42 for (int kj=0;kj<=j;kj++) 43 if ((i-ki)*(j-kj)>=a[k]) 44 f[i][j][k]=(f[i][j][k]+(LL)f[ki][kj][k-1]*C[n-ki][i-ki]%P*C[m-kj][j-kj]%P*g[i-ki][j-kj][a[k]]%P)%P; 45 if (k==c) ans=(ans+f[i][j][k])%P; 46 } 47 cout<<ans<<endl; 48 return 0; 49 }