[CQOI2011]放棋子题解(dp+组合数学)

Description

Input

输入第一行为两个整数n, m, c，即行数、列数和棋子的颜色数。

第二行包含c个正整数，即每个颜色的棋子数。

所有颜色的棋子总数保证不超过nm。

N,M<=30 C<=10 总棋子数有大于250的情况。

Output

输出仅一行，即方案总数除以 1,000,000,009的余数。

Sample Input

4 2 2
3 1

Sample Output

$Solution$

20%:爆搜，没甚么技术含量虽然我考场上还是没打对只骗到10分Orz

100%:

考虑dp

设$f[i][j][k]$为前k种颜色的棋子占任意i行j列的方案数

那么这个值肯定是前面一系列值的$sum$

显然需要枚举两层$0<=l<i , 0<=r<j$

之后就可以得到$f[l][r][k-1]$并将其累加

但因为我们设的状态是任意行列

需要在剩下的$n-l$行中选$i-l$行，列的话同理

所以要$*C_{n-l}^{i-l}*C_{m-r}^{j-r}$,

而且如果要转移过去还必须乘上某一种颜色占任意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] * g[i - l][j - r][a[k]] * C_{n - l} ^ {i - l} * C_{m - r} ^ {j - r}$

正向求g比较困难，我们可以逆向思维，用所有方案数-不合法方案数之和

$g[i][j][k] = C_{i j} ^ {k} - sum _ {l = 1} ^ {i} sum _ {r = 1} ^ {j} g[l][r][k] * C_{i}^{l} * C_{j} ^ {r}$

最后统计$ans=sum _ {i = 1} ^ {n} sum _ {j = 1} ^ {m} f[i][j][c]$

收获:如果觉得状态设计得当，而缺少转移方程的某一部分时，不妨设一个辅助数组单独考虑。

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
int n,m,c,a[35];
const ll mod=1e9+9;
ll f[35][35][15],g[35][35][920],ans=0,C[920][920];
int main()
{
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=c;i++)
        scanf("%d",&a[i]);
    if(c>min(n,m))
    {
        puts("0");
        return 0;
    }
    f[0][0][0]=1;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]+C[i-1][j-1])%mod;
    }
    for(int k=1;k<=c;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(a[k]>i*j)continue;
                ll res=0;
                g[i][j][a[k]]=C[i*j][a[k]];
                for(int l=1;l<=i;l++)
                    for(int r=1;r<=j;r++)
                        if(l<i||r<j)
                            (res+=C[i][l]*C[j][r]%mod*g[l][r][a[k]]%mod)%=mod;    
                g[i][j][a[k]]=(g[i][j][a[k]]-res+mod)%mod;
            }
    for(int k=1;k<=c;k++)
        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++)    
                        (f[i][j][k]+=C[n-l][i-l]*C[m-r][j-r]%mod*f[l][r][k-1]%mod*g[i-l][j-r][a[k]]%mod)%=mod;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            (ans+=f[i][j][c])%=mod;
    cout<<ans<<endl;
    return 0;
}