[CQOI2011] 放棋子

BZOJ
luogu
很神仙的一题
首先一般这个数据范围的dp足以让我等蒟蒻感到畏惧
我们发现每个颜色的摆放与摆放的先后顺序无关,哪种颜色占领了哪几行,哪几列我们也不关心
可以设个状态\(f[t][i][j]\)表示前t种颜色合起来占领了i行j列
\(f[t][i][j]=\sum_{p=0}^i\sum_{q=0}^jf[t-1][p][q]*C(n-p,i-p)*C(m-q,j-q)*\)第t种颜色占领i-p行j-q列的方案数
再设\(g[i][j]\)表示当前颜色占领i行j列的方案数,假设当前颜色总共有k个子
这个可以容斥做,\(g[i][j]=\)总方案数\(C(i*j,k)-\)不合法方案数\(\sum_{p=1}^i\sum_{q=1}^jg[p][q]*C(i,p)*C(j,q)\)
复杂度:\(O(n^2m^2c)\)

#include<bits/stdc++.h>
using namespace std;
const int _=35,N=905,mod=1e9+9;
int re(){
    int x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*w;
}
int n,m,C,ans,c[N][N],g[_][_],f[15][_][_];
void add(int&x,int y){x=(x+y)%mod;}
int main(){
    n=re(),m=re(),C=re();
    for(int i=0;i<=n*m;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }
    f[0][0][0]=1;
    for(int t=1,k;t<=C;t++){
        k=re();memset(g,0,sizeof(g));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if(i*j<k)continue;
                g[i][j]=c[i*j][k];
                for(int p=1;p<=i;p++)
                    for(int q=1;q<=j;q++){
                        if(i==p&&j==q)continue;
                        add(g[i][j],mod-1ll*g[p][q]*c[i][p]%mod*c[j][q]%mod);
                    }
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                for(int p=0;p<=i;p++)
                    for(int q=0;q<=j;q++)
                        add(f[t][i][j],1ll*f[t-1][p][q]*g[i-p][j-q]%mod*c[n-p][i-p]%mod*c[m-q][j-q]%mod);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            add(ans,f[C][i][j]);
    printf("%d\n",ans);return 0;
}

[CQOI2011] 放棋子

原文：https://www.cnblogs.com/sdzwyq/p/9846734.html