3.奶牛的新家
【问题描述】
由于奶牛们纷纷表示破旧的房子实在是太丑陋了，DD决定给他们建造新家。现在有许多奶牛决定将家建造在n*m的城市中。然而奶牛们分成了k帮派，不同帮派的奶牛不能住在同列或同行上。现在DD想知道一共有多少建造方案。
【输入】
第一行三个整数n,m,k
接下来一行k个整数，分别表示每个帮派有多少只牛
【输出】
一行一个整数，建造方案数mod 100000007
【样例输入】
2 3 2
1 1
【样例输出】
12
【输入输出样例说明】
两头不同帮派的牛放在2*3的图中的方案数为12
【数据范围】
对于30%的数据，n,m≤4
对于80%的数据，n,m≤20
对于100%的数据,n,m≤30;k≤10
这是我们第二次六校联测（标题是“多校联测3”），又挂了，唉，又是死在了dp上了，烦透了。
先观察这一题，一种颜色一定是占据了若干行和若干列的，在这些行与列上是不能放别的颜色的。令g(i, j, k)表示第k种颜色恰好占据了i行j列的方案数，这里“恰好”是指这i行j列中没有哪一行或者哪一列是空的。那么有：
g(i, j, k) = C(i * j, a[k]) - sigma ( g(i', j', k) * C(i, i') * C(j, j') )，其中要满足i' < i或 j' < j，i * j要 >= a[k]（a[k]表示第k种颜色的个数），C表示的是组合。
上面那条方程的意思就是，首先要加上C(i * j, a[k])表示在这i * j个格子里放a[k]个，那么有C(i * j, a[k])种方案。减掉的那一部分的意义是：某些方案并不满足这种状态（注意状态表示的是“恰好占据”），所以需要减掉这些状态。
然后f(i, j, k)表示前k种颜色，恰好占据了i行j列的方案数，那么有：
f(i, j, k) = sigma( f(i - i', j - j', k - 1) * g(i', j') * C(i, i') * C(j, j') )
#include <cstdio> const long long mod = 100000007; int n, m, K, a[15];
long long c[1005][1005], f[35][35][15], g[35][35][15], ans; int main(void) {
scanf("%d%d%d", &n, &m, &K);
for (int i = 1; i <= K; ++i) {
scanf("%d", a + i);
}
c[0][0] = 1;
for (int i = 1; i < 1001; ++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;
}
} for (int k = 1; k <= K; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i * j < a[k]) {
continue;
}
g[i][j][k] = c[i * j][a[k]];
for (int i_ = 1; i_ <= i; ++i_) {
for (int j_ = 1; j_ <= j; ++j_) {
if (i_ < i || j_ < j) {
g[i][j][k] = (g[i][j][k] - (g[i_][j_][k] * c[i][i_] % mod * c[j][j_] % mod) + mod) % mod;
}
}
}
}
}
} f[0][0][0] = 1;
for (int k = 1; k <= K; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i * j < a[k]) {
continue;
}
for (int i_ = 1; i_ <= i; ++i_) {
for (int j_ = 1; j_ <= j; ++j_) {
f[i][j][k] = (f[i][j][k] + f[i - i_][j - j_][k - 1] * g[i_][j_][k] % mod * c[i][i_] % mod * c[j][j_]) % mod;
}
}
}
}
} for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
ans = (ans + f[i][j][K] * c[n][i] % mod * c[m][j] % mod) % mod;
}
}
printf("%d\n", (int)ans);
return 0;
}