BZOJ3294 CQOI2011放棋子（动态规划）

时间：2023-03-08 20:14:03
BZOJ3294 CQOI2011放棋子（动态规划）

　　可以看做棋子放在某个位置后该种颜色就占领了那一行一列。行列间彼此没有区别。

　　于是可以设f[i][j][k]表示前k种棋子占领了i行j列的方案数。转移时枚举第k种棋子占领几行几列。注意行列间是有序的，要乘上一个组合数。这里f[i][j][k]可以是在原棋盘选i行j列占领的方案数，也可以是占领i行j列棋盘的方案数，如果是第二种最后统计答案的时候还要乘上个组合数，转移略有不同但没有本质区别。我们还需要计算出k个棋子占领i行j列中的方案数才能转移。

　　考虑怎么求这个东西。设其为g[i][j][k]。不妨把行列尽量往左往上移，可以发现棋子只能放置在其重合区域，也就是一个i*j的棋盘。使得这里面每行每列都有棋子就可以了。

　　然而还是不太好算。考虑求存在某一行或某一列没有棋子的方案数，那么可以枚举其中有几行几列是空的转移。于是可得g[i][j][k]=C(i*j,k)-Σg[x][y][k]*C(i,x)*C(j,y) (x+y<i+j)。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define P 1000000009

#define N 31

#define K 11

int n,m,c,l,a[K],f[K][N][N],g[K][N][N],ans=;

int fac[N*N],inv[N*N],C[N*N][N*N];

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int main()

{

#ifndef ONLINE_JUDGE

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

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

    const char LL[]="%I64d";

#else

    const char LL[]="%lld";

#endif

    n=read(),m=read(),c=read();

    for (int i=;i<=c;i++) a[i]=read();

    C[][]=C[][]=;

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

    {

        C[i][]=C[i][i]=;

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

        C[i][j]=(C[i-][j-]+C[i-][j])%P;

    }

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

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

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

            if (i*j>=a[k])

            {

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

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

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

                    if (x<i||y<j)

                    inc(g[k][i][j],P-1ll*C[i][x]*C[j][y]%P*g[k][x][y]%P);

            }

    f[][][]=;

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

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

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

            if (i*j>=a[k])

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

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

                    inc(f[k][i][j],1ll*f[k-][i-x][j-y]*g[k][x][y]%P*C[n-i+x][x]%P*C[m-j+y][y]%P);

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

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

        inc(ans,f[c][i][j]);

    cout<<ans;

    return ;

}

相关文章