BZOJ 3294: [Cqoi2011]放棋子(计数dp)

传送门

解题思路

　　设\(f[i][j][k]\)表示前\(k\)个颜色的棋子占领了\(i\)行\(j\)列的方案数，那么转移时可以枚举上一个颜色时占领的位置，\(f[i][j][k]=\sum\limits_{l=1}^n\sum\limits_{j=1}^mf[l][r][k-1]*C(n-l,i-l)*C(m-r,j-r)\)，但发现这样会少一个\(k\)这种颜色占领的方案数，再设\(g[i][j][k]\)表示用相同颜色的\(k\)个棋子占领\(i\)行\(j\)列的方案数，而算\(g\)时可以考虑用总的情况减去不符合的情况，即\(g[i][j][k]=C(i*j,k)-g[l][r][k]*C(i,l)*C(j,r)\)。然后把\(g\)也算到\(f\)里去即可，时间复杂度\(O(n^2m^2c)\)

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long 

using namespace std;
const int N=35;
const int MOD=1e9+9;
typedef long long LL;

inline int rd(){
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) f=ch==‘-‘?0:1,ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-‘0‘,ch=getchar();
    return f?x:-x;  
}

int n,m,c,cnt[15],C[N*N][N*N];
int f[N][N][15],g[N][N],ans;

inline void prework(){
    C[0][0]=1;
    for(int i=1;i<=n*m;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;    
    }
}

signed main(){
    n=rd(),m=rd(),c=rd(); prework();
    for(int i=1;i<=c;i++) cnt[i]=rd();
    f[0][0][0]=1;
    for(int o=1;o<=c;o++){
        memset(g,0,sizeof(g));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)if(i*j>=cnt[o]){
                g[i][j]=C[i*j][cnt[o]];
                for(int l=1;l<=i;l++)
                    for(int r=1;r<=j;r++)if(i>l || j>r){
                        g[i][j]-=(LL)g[l][r]*C[i][l]%MOD*C[j][r]%MOD;
                        g[i][j]=(g[i][j]%MOD+MOD)%MOD;
                    }   
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                for(int l=0;l<i;l++)
                    for(int r=0;r<j;r++)if((i-l)*(j-r)>=cnt[o]) {
                        f[i][j][o]+=(LL)f[l][r][o-1]*g[i-l][j-r]%MOD*C[n-l][i-l]%MOD*C[m-r][j-r]%MOD;
                        f[i][j][o]%=MOD;
                    }               
    }
//  for(int i=1;i<=n;i++)
//      for(int j=1;j<=m;j++)
//          for(int o=1;o<=c;o++)
//              printf("f[%d][%d][%d]=%d\n",i,j,o,f[i][j][o]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=(ans+f[i][j][c])%MOD;
    printf("%lld\n",ans);
    return 0;   
}

BZOJ 3294: [Cqoi2011]放棋子(计数dp)

原文：https://www.cnblogs.com/sdfzsyq/p/10389118.html