P3158 [CQOI2011]放棋子

· · 个人记录

P3158 [CQOI2011]放棋子

本蒟蒻表示把DP与数论放在一起真有趣恶心。。。

因为不同颜色的棋子不能在同一行或者同一列，所以每种颜色的棋子的摆放是相对独立的。

于是考虑设计这么一个状态dp[i][j][k]，表示用前k种颜色的棋子占领了任意i行j列的方案数，则：（假设第k种棋子有a[k]枚）

dp[i][j][k]=\sum_{l=0}^{i-1}\sum_{r=0}^{j-1}f[l][r][k-1]\times $用$a[k]$枚棋子占领$(i-l)$行$(j-r)$列的方案数$\times C_{n - l}^{i - l} \times C_{m-r}^{j-r}((i-l)\times(j-r)\ge a[k])

其它都好处理，但“用a[k]枚棋子占领(i−l)行(j−r)列的方案数”似乎不是那么容易直接求。

考虑再设一个状态g[i][j][k]，表示任意k枚同色棋子占领了任意i行j列的方案数。

则g[i][j][k]就为总方案数-不合法方案数（实际上有没有被占领的行或列的方案数），即：

g[i][j][k]=C_{i\times j}^k-\sum_{l=1}^i\sum_{r=1}^jg[l][r][k]\times C_i^l\times C_j^r,l<i||r<j,i\times j\ge k

我们预处理g[i][j][k]，则f[i][j][k]的转移就可表示为：

f[i][j][k]=\sum_{l=0}^{i-1}\sum_{r=0}^{j-1}f[l][r][k - 1]\times g[i-l][j-r][a[k]]\times C_{n-l}^{i-l}\times C_{m-r}^{j-r}((i-l)\times(j-r)\ge a[k])

不一定要每行每列都占领，但棋子要全放完，答案就为：

\sum_{i=1}^n\sum_{j=1}^mf[i][j][c]

时间复杂度O(n^2m^2c)。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 40
#define MAXM 20
#define MAXK 910
#define MOD 1000000009LL
using namespace std;
int n,m,c,S;
long long ans=0;
long long g[MAXN][MAXN],triangle[MAXK][MAXK],dp[MAXN][MAXN][MAXM];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
void work(){
    int u,v,w;
    for(int k=1;k<=c;k++){
        int w=read();
        memset(g,0,sizeof(g));
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        if(i*j>=w){
            g[i][j]=triangle[i*j][w];
            for(int l=1;l<=i;l++)
            for(int r=1;r<=j;r++)
            if(l<i||r<j)
            g[i][j]=(g[i][j]-g[l][r]*triangle[i][l]%MOD*triangle[j][r]%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++){
            int u=i-l,v=j-r;
            if(u*v>=w)
            dp[i][j][k]=(dp[i][j][k]+dp[l][r][k-1]*g[u][v]%MOD*triangle[n-l][u]%MOD*triangle[m-r][v]%MOD)%MOD;
        }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    ans=(ans+dp[i][j][c])%MOD;
    printf("%lld\n",ans);
}
void init(){
    n=read();m=read();c=read();
    S=n*m;
    for(int i=0;i<=S;i++)triangle[i][0]=1;
    for(int i=1;i<=S;i++)
    for(int j=1;j<=i;j++)
    triangle[i][j]=(triangle[i-1][j-1]+triangle[i-1][j])%MOD;
    dp[0][0][0]=1;
}
int main(){
    init();
    work();
    return 0;
}