测试地址：放棋子 做法：本题需要用到DP+组合数学。 观察发现，每种颜色的棋子都独占若干行和若干列，如果我们能知道在正好占用若干行若干列时，放若干个棋子的方案数的话，就可以做二维背包了！令 f(i,j,k) 为 k 个同色棋子正好占用i行 j 列的方案数，那么可得状态转移方程： f(i,j,k)=Cki×j−∑ip=0∑jq=0CpiCqjf(i−p,j−q,k) 上式是怎么推出来的呢？可以看做，用在 i×j 个格子里放 k 个棋子的方案数，减去正好空p行 q 列的方案数。注意到第三维实际上没有必要枚举全部1~ 900 ，只要求出 k= 某种棋子颜色总数的情况就可以了，那么我们删去第三维，上式就是 O(cn2m2) 的了，可以接受。 接下来就是二维背包了。令 g(k,i,j) 为放前 k 种颜色，还剩i行 j 列没有占用的方案数，那么有状态转移方程： g(k,i,j)=∑np=i∑mq=jCipCjqf(p−i,q−j,num(k))g(k−1,p,q) 其中 num(k) 为第 k 种颜色的棋子数量，边界条件为g(0,n,m)=1，显然答案为 ∑ni=1∑mj=1g(c,i,j) 。上述的方程应该可以挺容易推出来了，时间复杂度为 O(cn2m2) ，那么预处理出组合数就可以通过该题了。 以下是本人代码：
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define ll long long #define mod 1000000009 using namespace std; int n,m,c,num[11],tot=0; ll cc[1010][1010],f[35][35]={0},g[2][35][35]={0}; ll power(ll a,ll b) { ll s=1,ss=a; while(b) { if (b&1) s=(s*ss)%mod; b>>=1;ss=(ss*ss)%mod; } return s; } ll C(int n,int m) { if (m>n) return 0; return cc[n][m]; } int main() { scanf("%d%d%d",&n,&m,&c); for(int i=1;i<=c;i++) scanf("%d",&num[i]),tot+=num[i]; cc[0][0]=1; for(int i=1;i<=1000;i++) { cc[i][0]=1; for(int j=1;j<=i;j++) cc[i][j]=(cc[i-1][j-1]+cc[i-1][j])%mod; } int now=1,past=0; g[past][n][m]=1; for(int k=1;k<=c;k++) { memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { f[i][j]=C(i*j,num[k]); for(int p=0;p<=i;p++) for(int q=0;q<=j;q++) if (p||q) f[i][j]=(((f[i][j]-((C(i,p)*C(j,q))%mod)*f[i-p][j-q])%mod)+mod)%mod; } for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) { g[now][i][j]=0; for(int p=i;p<=n;p++) for(int q=j;q<=m;q++) g[now][i][j]=(g[now][i][j]+((((C(p,i)*C(q,j))%mod)*f[p-i][q-j])%mod)*g[past][p][q])%mod; } swap(now,past); } ll ans=0; for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) ans=(ans+g[past][i][j])%mod; printf("%lld\n",ans); return 0; }