题解 P3158 【[CQOI2011]放棋子】

· · 题解

计数DP

这是一道计数DP题，不同颜色的棋子不能在同一行同一列，否则就不合法，所以每种颜色的棋子摆放的方案数是相对独立的。

本题解和一楼题解解法一样，对其中一些问题会进行更深入的解释，若新手看不懂一楼题解，可以帮助大家理解一下。

解决问题

预设状态

我们设数组f[i][j][k]表示前k种颜色占领了任意i行j列的方案数。

设数组g[i][j][k]表示任意k枚同色棋子放任意i行j列的方案数。

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)≥a[k])

理解公式

这个部分对上述公式进行解释，大家可以自己先思考一下为什么。

假设我们当前计算的是第k种颜色，那么前k-1种颜色所占领的行列肯定会包含在i和j中，但又不能超过i和j，因为第k种颜色至少会占领其中一行，而l和r从0开始枚举是因为当计算第1种颜色时，前面的颜色没有占领任何一行一列。所以，我们可以在这个范围内枚举前k-1种颜色占领l行r列的情况。

接下来，我们能够发现，既然前k-1种棋子占领l行r列，前k种棋子占领i行j列，那第k种棋子就会占领i-l行j-r列，所以g[i-l][j-r][a[k]]考虑的是当前第k种棋子放置的方案数。

而后面的两个组合数其实就是当前k-1种棋子已经占领了l行r列时，第k种棋子从剩下的行列中占领哪些行列的方案数，这些东西结合在一起，就求得了我们的f[i][j][k]。

最后为什么会有这个范围，原因在与棋子是必须要放完的，如果你枚举的行列所拥有的格子数不足该种颜色棋子的总数量，说明这种方法不可行。

求解各个部分

理清楚了为什么，接下来的问题就是求解。

其实g[i][j][k]就是总方案数-不合法的方案数，什么意思呢？就是将k个棋子随意分入i行j列种也许会分到前面已经被占领的行列，我们要将这些方案数减去。总方案数很好理解，从能够分的总格子数中选出k个各自来放，就是一个组合数。

而不合法的方案数也其实就是枚举l行r列放k个棋子时的方案数再乘上从i行里面选l行的方案数和从j行里面选r行的方案数，则g的求解公式即为：

g[i][j][k]= C_{i \times j}^{k} - \sum \limits_{l = 1}^i \sum \limits_{r = 1}^j g[l][r][k] \times C_i^l \times C_j^r(l < i || r < j, i \times j \ge k)

注意一下这里的范围其实就是使其不和i行j列完全重合

scanf("%d",&a[k]);
        //在这里k=a[k] 
        memset(g,0,sizeof(g));
        //求解g数组 
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i*j>=a[k]){
                    g[i][j]=C[i*j][a[k]];
                    for(int l=1;l<=i;l++)
                        for(int r=1;r<=j;r++)
                            if( l<i || r<j ) g[i][j]=((ll)g[i][j]-(ll)g[l][r]*C[i][l]%MOD*C[j][r]%MOD+MOD)%MOD;
                }
            }
        }

然后组合数由于数据很小，直接一波杨辉三角预处理即可，当然若是你不嫌麻烦，乘法逆元也未尝不可。

inline void intial()    //杨辉三角初始化组合数 
{
    for(int i=0;i<=N*N-1;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;
    }
}

最后的答案也是呼之欲出，由于n行m列不必放满，但是棋子得放完，答案就是：

\sum _{i=1}^n\sum _{j=1}^mf[i][j][c] 
    //不一定每行每列都要有棋子，但是棋子得放完 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=(ans+f[i][j][c])%MOD;

最后的最后

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=35,K=15,MOD=1e9+9;
int n,m,c,a[K];
//不同颜色的棋子不能在同一行或者同一列，所以每种颜色的棋子摆放是相对独立的 
//状态f[i][j][k]表示用前k种颜色的棋子占领了任意i行j列的方案数 
ll ans,C[N*N][N*N],g[N][N],f[N][N][K]; 
inline void intial()    //杨辉三角初始化组合数 
{
    for(int i=0;i<=N*N-1;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;
    }
}

int main()
{
    intial();
    scanf("%d%d%d",&n,&m,&c);
    //初始化f[0][0][0]=1 
    f[0][0][0]=1; 
    //另设一个状态g[i][j][k]表示任意k枚同色棋子占领任意i行j列的方案数 
    for(int k=1;k<=c;k++){
        scanf("%d",&a[k]);
        //在这里k=a[k] 
        memset(g,0,sizeof(g));
        //求解g数组 
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i*j>=a[k]){
                    g[i][j]=C[i*j][a[k]];
                    for(int l=1;l<=i;l++)
                        for(int r=1;r<=j;r++)
                            if( l<i || r<j ) g[i][j]=((ll)g[i][j]-(ll)g[l][r]*C[i][l]%MOD*C[j][r]%MOD+MOD)%MOD;
                }
            }
        }
        //求解f数组 
        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)>=a[k]) f[i][j][k]=(f[i][j][k]+(ll)f[l][r][k-1]*g[i-l][j-r]%MOD*C[n-l][i-l]%MOD*C[m-r][j-r]%MOD)%MOD;
    }
    //不一定每行每列都要有棋子，但是棋子得放完 
    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;
}