P3158 [CQOI2011]放棋子

传送门

首先考虑到放一个棋子以后少掉的哪一行一列我们可以直接忽略，把被切开的四个部分重新拼成一个矩形

所以状态就只要考虑当前有几行几列，放了哪些棋子，考虑同一种颜色的一起放

设 $f[i][j][k]$ 表示放完前 $i$ 种颜色的棋子，剩下 $j$ 行 $k$ 列空着

那么转移直接枚举这一种颜色占了多少行列：$f[i][j][k]=sum_{x=1}^{j+x<=n}sum_{y=1}^{k+y<=m}f[i-1][j+x][k+y]* inom{j+x}{x} inom{k+y}{y} * g[x][y][a[k]] $

其中 $a[i]$ 表示颜色 $i$ 的棋子数量，$g[x][y][a[i]]$ 就表示把 $a[i]$ 个同色的棋子占 $x$ 行 $y$ 列（每一行或列都至少有一个棋子）的方案数

乘组合数是因为行列可以任选

现在问题就是如何预处理 $g$，考虑简单的容斥，总方案数减去不合法方案数

那么考虑对 $g$ 进行一波 $dp$ ，$g[i][j][k]= inom{i*j}{k} - sum_{x=1}^{x<=i}sum_{y=1}^{y<=j} inom{i}{x} inom{j}{y} *g[x][y][k]$

即枚举多少行列没有棋子占领，组合数同样是因为行列任选

最后答案就是 $sum_{i=0}^{n-1}sum_{j=0}^{m-1}f[C][i][j]$ ，其中 $C$ 是颜色数

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=37,M=1007,mo=1e9+9;
inline int fk(int x) { return x>=mo ? x-mo : x; }
int n,m,K,tot,a[N];
int C[M][M],f[N][N][N],g[N][N][M],ans;
int main()
{
    n=read(),m=read(),K=read();
    for(int i=1;i<=K;i++) a[i]=read(),tot+=a[i];
    for(int i=0;i<M;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=i;j++) C[i][j]=fk(C[i-1][j-1]+C[i-1][j]);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=1;k<=tot;k++)
            {
                if(i*j<k) continue;
                g[i][j][k]=C[i*j][k];
                for(int x=1;x<=i;x++)
                    for(int y=1;y<=j;y++)
                        if(x<i||y<j) g[i][j][k]=fk(g[i][j][k]- 1ll*C[i][x]*C[j][y]%mo*g[x][y][k]%mo +mo);
            }
    f[0][n][m]=1;
    for(int i=1;i<=K;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<m;k++)
                for(int x=1;j+x<=n;x++)
                    for(int y=1;k+y<=m;y++)
                        f[i][j][k]=fk(f[i][j][k]+ 1ll*f[i-1][j+x][k+y]*C[j+x][x]%mo*C[k+y][y]%mo*g[x][y][a[i]]%mo );
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) ans=fk(ans+f[K][i][j]);
    printf("%d
",ans);
}