一开始一直以为可以不放完棋子…
n、m都不大，可以考虑DP 因为每行、每列只能放一种颜色的棋子，所以考虑把棋盘独立成n行m列，将这些行和列分给每种颜色的棋子 定义：
tips：最后输出答案要计算未占满所有行列的情况
code：
#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x) using namespace std;const int maxn = 32;const int maxk = 12;const int maxm = 910;const ll Mod = 1e9+9;int n,m,N,v[maxn];ll c[maxm][maxm];ll f[maxn][maxn],g[maxk][maxn][maxn];int main(){ c[0][0]=1; for(int i=0;i<maxm;i++) { c[i][0]=1; for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%Mod; } scanf("%d%d%d",&n,&m,&N); for(int i=1;i<=N;i++) scanf("%d",&v[i]); g[0][0][0]=1ll; for(int k=1;k<=N;k++) { for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)f[i][j]=0ll; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(i*j>=v[k]) { f[i][j]=c[i*j][v[k]]; for(int x=1;x<=i;x++) for(int y=1;y<=j;y++) { if(x==i&&y==j) break; if(f[x][y]) (f[i][j]-=f[x][y]*c[i][x]%Mod*c[j][y]%Mod)%=Mod; } } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { for(int x=1;x<=i;x++) for(int y=1;y<=j;y++) if(f[x][y]) (g[k][i][j]+=g[k-1][i-x][j-y] *f[x][y]%Mod*c[i][x]%Mod*c[j][y]%Mod)%=Mod; } } ll ret=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) (ret+=g[N][i][j]*c[n][i]%Mod*c[m][j]%Mod)%=Mod; PRintf("%lld/n",ret); return 0;}新闻热点
疑难解答
