正解:dp+數論
解題報告:
考慮對每種顏色的棋子單獨考慮鴨,那顯然有,當某一行或某一列已經被佔據的時候,那一行/一列就不能再放別的顏色的棋子了,相當於直接把那一行/一列直接消了
顯然就能考慮到dp?設f[i][j]:剩餘i行j列的方案數
轉移就枚舉這個顏色的棋子放了p行q列,設g[d][p][q]:d個棋子恰好放了p行q列的方案數
直接枚舉pq,f[i][j]=∑f[i+p][j+1]*g[c[k]][p][q]
現在就只要知道怎麼求g就好
看到這種恰好balabala的應該就第一反應想到容斥,,,?
這裏也一樣啊,就組合數算下容斥下就歐克辣!
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#define gc getchar()
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
const int mod=1000000009,N=30+10;
int n,m,c,num[N],fac[N*N],ifac[N*N],g[N][N][N],f[N][N][N]={1},as;
il int read()
{
rc ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il int power(ri x,ri y){int ret=1;while(y){if(y&1)ret=1ll*ret*x%mod;x=1ll*x*x%mod;y>>=1;}return ret;}
il void pre(ri n)
{
fac[0]=1;rp(i,1,n)fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=power(fac[n],mod-2);my(i,n-1,0)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
inline int C(ri n,ri m){return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
int main()
{
// freopen("3158.in","r",stdin);freopen("3158.out","w",stdout);
n=read();m=read();c=read();rp(i,1,c)num[i]=read();pre(n*m);
rp(i,1,c)
{
rp(j,1,n)
{
rp(k,1,m)
{
if(j*k<num[i])continue;
g[i][j][k]=C(j*k,num[i]);
rp(p,1,j)rp(q,1,k)if(p^j || q^k)g[i][j][k]=(g[i][j][k]+(mod-1ll*C(j,p)*C(k,q)%mod*g[i][p][q]%mod))%mod;
}
}
}
rp(i,1,c)rp(j,1,n)rp(k,1,m)rp(p,1,j)rp(q,1,k)f[i][j][k]=(f[i][j][k]+1ll*f[i-1][j-p][k-q]*g[i][p][q]%mod*C(n-j+p,p)%mod*C(m-k+q,q)%mod)%mod;
rp(i,1,n)rp(j,1,m)as=(as+f[c][i][j])%mod;printf("%d\n",as);
return 0;
}