「luogu - P3158」「cqoi 2011」放棋子

link。

解读一下，大概就是一种颜色放进去就会占据一行一列，dp 状态就好想了：\(f_{i,j,k}\) 表示恰好用完前 \(k\) 种颜色的所有棋子，占据了 \(i\) 行 \(j\) 列的方案数。你把已经被占据的行列挪到??角角，这就导出了一个子问题，在一个 \((n-i)\times(m-j)\) 的矩形中，使用恰好 \(u\) 个棋子（注意不是种类，这也是子问题和原问题的区别）占据其中一些行列的方案数。

容易发现，我们比较关心的是占据的行列数，而其与整个 \((n-i)\times(m-j)\) 矩形的关联并不强（因为我们都可以把选出来的挪到??角角），设占据了 \(x\) 行 \(y\) 列，最后把方案数乘 \(\binom{n}{x}\binom{m}{y}\) 即可。于是设 \(f'_{i,j,k}\) 表示用恰好 \(k\) 个棋子填满 \(i\times j\) 矩形的方案数。转移逐行考虑，上一行就填了 \(j\) 个棋子，设当前行填了 \(h\) 个棋子，有 \(l\) 列是和上一行共享，则当前行有 \(j+h-l\) 个格子有棋子，于是可以写出 \(f'_{i,j+h-l,k+h}=\sum\sum\binom{j+h-l}{,j}\binom{j}{l}f'_{i-1,j,k}\)。

看回到 \(f\) 的转移，考虑新棋子所占据的行列数 \(h,l\)，则有 \(f_{i-h,j-l,k}=\sum\sum\binom{i}{h}\binom{j}{l}f_{i,j,k-1}f'_{h,l,a_k}\)。

#include
using namespace std;
typedef long long ll;
const int MOD=1e9+9;
int n,m,c,a[20],mx,coef[40][40]; ll fac[110],ifac[110],dp[11][50][50],dpsub[50][50][1000],ans;
inline ll C(const int i,const int j) { assert(i>=j); return coef[i][j]; }
char buf[1<<21],*p1=buf,*p2=buf;
#define Gc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int Gi() {
	int x=0; char c=Gc(); bool f=0;
	while(c<'0' || c>'9')	f|=(c=='-'),c=Gc();
	while(c>='0' && c<='9')	x=x*10+(c&15),c=Gc();
	return f?-x:x;
}
signed main() {
	for(int i=0; i<=35; ++i) {
		coef[i][0]=1;
		for(int j=1; j<=i; ++j)	coef[i][j]=(coef[i-1][j-1]+coef[i-1][j])%MOD;
	}
	n=Gi(); m=Gi(); c=Gi();
	for(int i=1; i<=c; ++i)	mx=max(mx,a[i]=Gi());
	dpsub[0][0][0]=1;
	for(int i=1; i<=n; ++i) {
		for(int j=0; j<=m; ++j) {
			for(int k=0; k<=mx; ++k) {
				for(int h=1; h<=m; ++h) {
					for(int l=0; l<=min(h,j); ++l) {
						if(j+h-l<=m)	(dpsub[i][j+h-l][k+h]+=C(j+h-l,j)*C(j,l)%MOD*dpsub[i-1][j][k]%MOD)%=MOD;
					}
				}
			}
		}
	}
	dp[0][n][m]=1;
	for(int k=1; k<=c; ++k) {
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=m; ++j) {
				for(int h=1; h<=i; ++h) {
					for(int l=1; l<=j; ++l)	(dp[k][i-h][j-l]+=C(i,h)*C(j,l)%MOD*dp[k-1][i][j]%MOD*dpsub[h][l][a[k]]%MOD)%=MOD;
				}
			}
		}
	}
	for(int i=0; i<=n; ++i) {
		for(int j=0; j<=m; ++j)	ans+=dp[c][i][j],ans%=MOD;
	}
	printf("%lld\n",ans);
	return 0;
}