题意:
分析:
可以考虑简化问题,考虑 \(1\times n\) 的一行中,有一些不能放,放 \(a\) 个一格骨牌, \(b\) 个两格骨牌的方案数。
设 \(f(i,j)\) 表示前 \(i\)个格子放 \(j\)个两格的方案数。
那如果 \(i,i−1\) 都能放, \(f(i,j)=f(i-1,j)+f(i-2,j-1)\)
否则 \(f(i,j)=f(i-1,j)\)
最后放 \(a\) 个一格骨牌, \(b\)个两格骨牌的方案数 = \(f(n,b)*C(cnt-2\times b,a)\),\(cnt\) 表示一行有多少个可以放的格子。
画图会发现,一些行,一些列是不能放的,可以看做上面的简化版问题,所以我们对每一行,每一列都求一下上面的 dp 值,放进 \(f,g\) 两个数组里。
放一个横放的骨牌相当于占掉一行两列,放一个竖放的骨牌相当于占掉一列两行。
枚举 \(i\) 个横放,\(j\) 个竖放,答案为
\[\sum f(n,j)\times g(m,i) \times C_{cntx-2\times i}^j\times C_{cnty-2\times j}^i\times i!\times j! \]代码:
#include<bits/stdc++.h>
using namespace std;
namespace zzc
{
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 35;
const int maxm = 905;
const int mod = 1e9+9;
int c[maxm][maxm];
int f[maxn][maxn][maxm],g[maxn][maxn];
int n,m,k;
long long ans=0;
void init()
{
c[0][0]=1;
c[1][0]=c[1][1]=1;
for(int i=2;i<=900;i++)
{
c[i][0]=1;
for(int j=1;j<=i;j++)
{
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}
}
void work()
{
int a;
init();
n=read();m=read();k=read();
f[0][0][0]=1;
for(int i=1;i<=k;i++)
{
a=read();
memset(g,0,sizeof(g));
for(int x=1;x<=n;x++)
{
for(int y=1;y<=m;y++)
{
if(x*y>=a)
{
g[x][y]=c[x*y][a];
for(int l=1;l<=x;l++)
{
for(int r=1;r<=y;r++)
{
if(l<x||r<y) g[x][y]=(g[x][y]-(long long)g[l][r]*c[x][l]%mod*c[y][r]%mod+mod)%mod;
}
}
}
}
}
for(int x=1;x<=n;x++)
{
for(int y=1;y<=m;y++)
{
for(int l=0;l<=x;l++)
{
for(int r=0;r<=y;r++)
{
int tmpx=x-l;
int tmpy=y-r;
if(tmpx*tmpy>=a)
{
f[x][y][i]=(f[x][y][i]+(long long)f[l][r][i-1]*g[tmpx][tmpy]%mod*c[n-l][tmpx]%mod*c[m-r][tmpy]%mod)%mod;
}
}
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
ans=(ans+f[i][j][k])%mod;
}
}
printf("%lld\n",ans);
}
}
int main()
{
zzc::work();
return 0;
}