Luogu

BZOJ

分析

如果一行/一列有颜色为 $x$ 的棋子,我们称“ $x$ 占领了该行/该列”。

设 $a[k]$ 表示第 $k$ 种颜色的数目。

设 $f[i][j][k]$ 表示前 $k$ 种颜色,占领了 $i$ 行、 $j$ 列的方案数。

设 $g[i][j][k]$ 表示第 $k$ 种颜色,占领了 $i$ 行、 $j$ 列的方案数。

显然 $g$ 比较好算,那么先考虑怎么计算 $g$ 。

直接算不好算,那么可以用总数减去不合法的。

可以得到 $\large g[i][j][k]={{i\times j}\choose a[k]}-\sum\limits_{p=1}^i\sum\limits_{q=1}^jg[p][q][k]\times{i\choose p}\times{j\choose q}$ 。转移的条件是 $i\times j\geq a[k]$ , $p<i\text{或}q<j$ 。

再考虑 $f$ 怎么算。

可以得到 $\large f[i][j][k]=\sum\limits_{p=0}^{i-1}\sum\limits_{q=0}^{j-1}f[p][q][k-1]\times g[i-p][j-1]\left[a\small[k\small]\right]\times{{n-p}\choose{i-p}}\times{{m-q}\choose{j-q}}$ 。转移的边界是 $f[0][0][0]=1$ ,条件是 $(i-p)(j-q)\geq a[k]$ 。

答案为 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m f[i][j][c]$ 。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=30+10,M=10+10;
const int mod=1e9+9;

inline void add(int& x,int y) { x=(x+y)%mod; }

int n,m,c;
int a[M];
int f[N][N][M],g[N][N][M];
int C[N*N][N*N];

int main() {
    n=read(),m=read(),c=read();
    for (re int i=1;i<=c;++i) a[i]=read();

    C[0][0]=1;
    for (re int i=1;i<=n*m;++i) {
        C[i][0]=1;
        for (re int j=1;j<=i;++j)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }

    for (re int k=1;k<=c;++k)
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=m;++j) {
                if (i*j<a[k]) continue;
                g[i][j][k]=C[i*j][a[k]];
                for (re int p=1;p<=i;++p)
                    for (re int q=1;q<=j;++q) {
                        if (p==i&&q==j) continue;
                        add(g[i][j][k],mod-1ll*g[p][q][k]*C[i][p]%mod*C[j][q]%mod);
                    }
            }

    f[0][0][0]=1;
    for (re int k=1;k<=c;++k)
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=m;++j)
                for (re int p=0;p<i;++p)
                    for (re int q=0;q<j;++q) {
                        if ((i-p)*(j-q)<a[k]) continue;
                        add(f[i][j][k],1ll*f[p][q][k-1]*g[i-p][j-q][k]%mod*C[n-p][i-p]%mod*C[m-q][j-q]%mod);
                    }

    int ans=0;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            add(ans,f[i][j][c]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 40 PM