输入第一行为两个整数n, m, c，即行数、列数和棋子的颜色数。第二行包含c个正整数，即每个颜色的棋子数。所有颜色的棋子总数保证不超过nm。N,M<=30 C<=10 总棋子数有大于250的情况
输出仅一行，即方案总数除以 1,000,000,009的余数。
30% n,m<=10
看题解，觉得这道题挺水的，然而考试时候的我，只能打出来20分TLE的暴力
又是一道出现在组合数里的DP，不过跟地精比，这道题跟跟组合数关系还稍微大一点
既然是DP，我们先来想一想怎么进行状态转移
我们用shu[o]表示第o种棋子的数量，g[o][i][j]表示第o种棋子，占了i行j列，那首先想到的就是g[o][i][j]=C(i*j,shu[o])，但是仔细想一想这样算的话，这shu[o]个棋子可能并没有占满i行j列，你可能就只用了x行y列(x<i,j<y)，这个时候要怎么办？答案容斥，也不知道为啥，最近老碰见它，我还老想不起来它，怎么斥就很明显了，用基础的C(i*j,shu[o])-每一个不占满的情况，所以就有g[o][i][j]=C(i*j,shu[o])-∑g[o][x][y]*C(i,x)*C(j,y)，保证x<=i，y<=j且x=i，y=j不同时满足，这很显然吧，然而我卡了好久，说一句吧，如果两个等号同时成立，那你就把要的也同时容斥掉了，为什么乘两个C应该就更好理解了吧，关于C的计算，直接杨辉三角，两层循环跑一遍就可以
我们算出来第o种之后，答案要的是前C种，那就需要算前o种的，照葫芦画瓢，我们用f[o][i][j]表示前o种棋子，占i行j列的方案数，这个就好想了，f[o][i][j]=∑f[o-1][x][y]*g[o][i-x][j-y]*C(i,x)*C(j,y)，最后把所有的f[C][i][j]加起来就是最后的答案了
关于暴搜：我暴搜就只拿到了20分，就是把每个棋子都当作不同的去放，最后除以全排列就可以了，剪枝我没太剪成，想练一练暴搜的可以试一试这道题，还算是需要注意的细节比较多的
要开始集训了，希望过完这个暑假可以场场不暴零了吧
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define maxz 11 5 #define maxn 31 6 #define ll long long 7 const long long mod=1e9+9; 8 using namespace std; 9 int n,m,z; 10 ll ans; 11 int shu[maxz]; 12 ll C[maxn*maxn][maxn*maxn]; 13 ll g[maxz][maxn][maxn],f[maxz][maxn][maxn]={1}; 14 int main() 15 { 16 scanf("%d%d%d",&n,&m,&z); 17 for(int i=1;i<=z;++i) scanf("%d",&shu[i]); 18 int ls=n*m+1; 19 for(int i=0;i<=ls;++i) 20 { 21 C[i][0]=1; C[i][i]=1; 22 for(int j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; 23 } 24 for(int o=1;o<=z;++o) 25 for(int i=1;i<=n;++i) 26 for(int j=1;j<=m;++j) 27 { 28 if(i*j<shu[o]) continue; 29 if(max(i,j)>shu[o]) continue; 30 g[o][i][j]=C[i*j][shu[o]]%mod; 31 for(int x=1;x<=i;++x) 32 for(int y=1;y<=j;++y) 33 { 34 if(i==x&&j==y) continue; 35 g[o][i][j]=(g[o][i][j]-(g[o][x][y]*C[i][x]*C[j][y])%mod)%mod; 36 } 37 } 38 for(int o=1;o<=z;++o) 39 for(int i=1;i<=n;++i) 40 for(int j=1;j<=m;++j) 41 { 42 if(i*j<shu[o]) continue; 43 for(int x=0;x<=i;++x) 44 for(int y=0;y<=j;++y) 45 { 46 if(i==x&&j==y) continue; 47 ll ls1=(C[i][x]*C[j][y])%mod; 48 ll ls2=(g[o][i-x][j-y]*ls1)%mod; 49 f[o][i][j]=(f[o][i][j]+(f[o-1][x][y]*ls2)%mod)%mod; 50 } 51 } 52 for(int i=1;i<=n;++i) 53 for(int j=1;j<=m;++j) 54 ans=(ans+((f[z][i][j]*C[n][i]%mod)*C[m][j])%mod)%mod; 55 printf("%lld\n",ans); 56 return 0; 57 }
转载于:https://www.cnblogs.com/hzjuruo/p/11166608.html
相关资源：各显卡算力对照表！