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

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

设 $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]* \binom{j+x}{x} \binom{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]= \binom{i*j}{k} - \sum_{x=1}^{x<=i}\sum_{y=1}^{y<=j} \binom{i}{x} \binom{j}{y} *g[x][y][k]$

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

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

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          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