嘟嘟嘟
做了一天容斥的题，感觉做过和这题类似的，于是就一直往容斥想。
然而正解可以不用容斥，看来自己的思维被限制了……
直接dp，令(f[i][j][k])表示前(k)种颜色的棋子占领任意(i)行(j)列的方案数，转移的时候就枚举第(k)种颜色能占领多少行和多少列。因此我们需要先预处理另一个dp方程：(g[i][j][k])表示(k)枚同色的棋子占领任意(i)行(j)列的方案数，这样(f)的转移方程就能写出来了：$$f[i][j][k] = sum _ {h = 0} ^ {i - 1} sum _ {w = 0} ^ {j - 1} f[h][w][k - 1] * g[i - h][j - w][a[k]] * C_{n - h} ^ {i - h} * C_{m - w} ^ {j - w}$$
至于(g)怎么求，思想就是用所有方案减去不合法的方案：$$g[i][j][k] = C_{i j} ^ {k} - sum _ {h = 1} ^ {i} sum _ {w = 1} ^ {j} g[h][w][k] * C_{i}^{ h} * C_{j} ^ {w}$$
这个应该不算是容斥，因为每一次减去的刚好是(h)行(w)列不合法的情况，并没有减多。
答案就是(sum _ {i = 1} ^ {n} sum _ {j = 1} ^ {m} f[i][j][c])。
这题给我的启示就是有时候不会转移并不是状态设的不好，反而需要设别的子状态辅助转移。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<assert.h>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 35;
const int maxN = 905;
const int maxc = 12;
const ll mod = 1e9 + 9;
In ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
}
int n, m, c, Max = 0, a[maxc];
ll g[maxn][maxn][maxN], f[maxn][maxn][maxc];
ll fac[maxN], inv[maxN];
In ll inc(ll a, ll b) {return a + b < mod ? a + b : a + b - mod;}
In ll C(int n, int m)
{
if(m > n) return 0;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
In ll quickpow(ll a, ll b)
{
ll ret = 1;
for(; b; b >>= 1, a = a * a % mod)
if(b & 1) ret = ret * a % mod;
return ret;
}
In void init()
{
fac[0] = inv[0] = 1;
for(int i = 1; i < maxN; ++i) fac[i] = fac[i - 1] * i % mod;
inv[maxN - 1] = quickpow(fac[maxN - 1], mod - 2);
for(int i = maxN - 2; i; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
for(int k = 1; k <= Max; ++k)
if(i * j >= k)
{
g[i][j][k] = C(i * j, k);
for(int h = 1; h <= i; ++h)
for(int w = 1; w <= j; ++w)
if(h != i || w != j) g[i][j][k] = inc(g[i][j][k], mod - g[h][w][k] * C(i, h) % mod * C(j, w) % mod);
}
}
int main()
{
MYFILE();
n = read(), m = read(), c = read();
for(int i = 1; i <= c; ++i) a[i] = read(), Max = max(Max, a[i]);
init();
f[0][0][0] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
for(int k = 1; k <= c; ++k)
for(int h = 0; h < i; ++h)
for(int w = 0; w < j; ++w)
f[i][j][k] = inc(f[i][j][k], f[h][w][k - 1] * g[i - h][j - w][a[k]] % mod * C(n - h, i - h) % mod * C(m - w, j - w) % mod);
ll ans = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) ans = inc(ans, f[i][j][c]);
write(ans), enter;
return 0;
}