bzoj千题计划261：bzoj3294: [Cqoi2011]放棋子

http://www.lydsy.com/JudgeOnline/problem.php?id=3294

如果一个颜色的棋子放在了第i行第j列，那这种颜色就会占据第i行第j列，其他颜色不能往这儿放

设第k种颜色的棋子有a[k]个

令g[k][i][j] 表示第k种颜色的棋子，恰好占据i行j列的方案数

g[k][i][j]=C(i*j,a[k])-Σh Σl g[h][l]*C(i,h)*C(j,l) 1<=h<=i,1<=l<=j,且满足 h!=i 或 l !=j

即总方案数（在i*j个格子中选a[k]个）减去没有恰好占据i行j列的方案数

令f[k][i][j] 表示前k种颜色的棋子，放完之后，还剩下i行j列的方案数

f[k][i][j]= Σh Σl f[k-1][h][l]*g[k][h-i][l-j]*C[h][h-i]*C[l][l-j] i<h<=n,j<l<=m

即枚举前k-1种颜色的棋子放完后，剩下h行l列，那么第k种颜色就占据h-i行l-j列

#include<cstdio>

using namespace std;

const int mod=1e9+9;

#define min(x,y) x<y ? x : y

#define N 31
#define M 11

int C[N*N][N*N];

int a[M];
long long g[M][N][N],f[M][N][N];

int main()
{
    int n,m,c;
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=c;++i) scanf("%d",&a[i]);
    int lim=n*m;
    C[0][0]=1;
    for(int i=1;i<=lim;++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;
    }
    int r1,r2;
    for(int k=1;k<=c;++k)
    {
        r1=min(a[k],n);
        for(int i=1;i<=r1;++i)
        {
            r2=min(a[k],m);
            for(int j=1;j<=r2;++j)
                if(i*j>=a[k])
                {
                    g[k][i][j]=C[i*j][a[k]];
                    for(int h=1;h<=i;++h)
                        for(int l=1;l<=j;++l)
                            if((h!=i || l!=j) && h*l>=a[k])
                            {
                                g[k][i][j]-=g[k][h][l]*C[i][h]%mod*C[j][l]%mod;
                                if(g[k][i][j]<0) g[k][i][j]+=mod;
                            }
                }
        }
    }
    f[0][n][m]=1;
    for(int k=1;k<=c;++k)
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                for(int h=i+1;h<=n;++h)
                    for(int l=j+1;l<=m;++l)
                        if((h-i)*(l-j)>=a[k])
                            f[k][i][j]=(f[k][i][j]+f[k-1][h][l]*g[k][h-i][l-j]%mod*C[h][h-i]%mod*C[l][l-j]%mod)%mod;
    int ans=0;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
        {
            ans+=f[c][i][j];
            if(ans>=mod) ans-=mod;
        }
    printf("%d",ans);
    return 0;
}

3294: [Cqoi2011]放棋子

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 797 Solved: 319
[Submit][Status][Discuss]

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