bzoj3294[Cqoi2011]放棋子 dp+组合+容斥

2023-07-26 17:12:58

3294: [Cqoi2011]放棋子

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 755 Solved: 294
[Submit][Status][Discuss]

Description

Input

输入第一行为两个整数n, m, c，即行数、列数和棋子的颜色数。第二行包含c个正整数，即每个颜色的棋子数。所有颜色的棋子总数保证不超过nm。

Output

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

Sample Input

4 2 2
3 1

Sample Output

HINT

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

很巧妙的dp,状态的定义很好
首先g[k][i][j]表示第k种颜色占据i行j列的方案
占据i行j列,放的棋子数在[max(i,j),i*j]之间
有i*j个格子,选择a[k]个放置,再减去没有完全占据i行j列的情况

然后f[k][i][j]表示前k种颜色占据i行j列
枚举每种颜色占据几行几列,从前一种颜色转移过来

最后统计ans的时候,考虑前p中颜色占据几行几列再乘上组合数

具体转移的看代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define ll long long

#define N 35

#define mod 1000000009

using namespace std;

int n,m,p,a[N],c[N*N][N*N];

ll g[N][N][N],f[N][N][N];

int main(){

#ifdef wsy

    freopen("data.in","r",stdin);

#else

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

#endif

    scanf("%d%d%d",&n,&m,&p);

    for(int i=;i<=p;i++)scanf("%d",&a[i]);

    for(int i=;i<=n*m;i++)c[i][i]=c[i][]=;

    for(int i=;i<=n*m;i++)

    for(int j=;j<i;j++)

    c[i][j]=(c[i-][j-]+c[i-][j])%mod;

    for(int k=;k<=p;k++)

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++){

        if(i*j<a[k]||max(i,j)>a[k])continue;

        g[k][i][j]=c[i*j][a[k]];

        for(int x=;x<=i;x++)

        for(int y=;y<=j;y++)

        if((i-x)||(j-y))

        g[k][i][j]=(mod+g[k][i][j]-g[k][x][y]*c[i][x]%mod*c[j][y]%mod)%mod;

    }

    f[][][]=;

    for(int k=;k<=p;k++)

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++){

        if(i*j<a[k])continue;

        for(int x=;x<i;x++)

        for(int y=;y<j;y++)

        f[k][i][j]=(f[k][i][j]+(f[k-][x][y]*g[k][i-x][j-y]%mod*c[i][x]%mod*c[j][y]%mod))%mod;

    }

    ll ans=;

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    ans=(ans+f[p][i][j]*c[n][i]%mod*c[m][j]%mod)%mod;

    cout<<ans;

    return ;

}

码农公寓