BZOJ3294: [Cqoi2011]放棋子

2019-11-06 06:11:40

字體：大中小

供稿：網(wǎng)友

一開始一直以為可以不放完棋子…

n、m都不大，可以考慮DP 因為每行、每列只能放一種顏色的棋子，所以考慮把棋盤獨立成n行m列，將這些行和列分給每種顏色的棋子定義： f[i][j] $f[i][j]$ 表示第k種棋子占據(jù)i行j列有多少種合法的放法， g[k][i][j] $g[k][i][j]$ 表示前k種棋子占據(jù)i行j列有多少種合法的放法求f $f$ 的時候可以用容斥，用所有的放法減去所有不合法的放法，預(yù)處理一下組合數(shù) 然后f $f$ 和g $g$ 合并

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;