Description
输入第一行为两个整数n, m, c，即行数、列数和棋子的颜色数。第二行包含c个正整数，即每个颜色的棋子数。所有颜色的棋子总数保证不超过nm。
Output
输出仅一行，即方案总数除以 1,000,000,009的余数。
4 2 2
3 1
Sample Output
8
HINT
N,M<=30 C<=10 总棋子数<=250
Solution
—————Vani
注意答案的统计！
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1<<30;
const LL mod = 1000000009;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
int n, m, c, A[15];
LL dp[15][35][35], g[15][35][35], CC[1605][1605];
LL C(int n, int k) {
return CC[n][k];
}
int main() {
for (int i = 0; i < 1600; ++i)
CC[i][0] = 1;
for (int i = 1; i < 1600; ++i)
for (int j = 1; j <= i; ++j)
CC[i][j] = (CC[i-1][j] + CC[i-1][j-1]) % mod;
n = getint(); m = getint(); c = getint();
for (int i = 1; i <= c; ++i) A[i] = getint();
for (int k = 1; k <= c; ++k)
for (int x = 1; x <= n; ++x)
for (int y = 1; y <= m; ++y) {
g[k][x][y] = C(x * y, A[k]);
for (int i = 1; i <= x; ++i)
for (int j = 1; j <= y; ++j) {
if (i == x && j == y) continue;
g[k][x][y] = (mod + g[k][x][y]-((g[k][i][j] * C(x, i) % mod) * C(y, j))%mod) % mod;
}
}
for (int x = 1; x <= n; ++x)
for (int y = 1; y <= m; ++y)
dp[1][x][y] = g[1][x][y];
for (int k = 2; k <= c; ++k)
for (int x = 1; x <= n; ++x)
for (int y = 1; y <= m; ++y)
for (int i = 0; i < x; ++i)
for (int j = 0; j < y; ++j)
dp[k][x][y] = (dp[k][x][y] + ((dp[k-1][i][j] * g[k][x-i][y-j]) % mod * C(x, i) % mod * C(y, j)) % mod) % mod;
LL ans = 0;
for (int x = 1; x <= n; ++x)
for (int y = 1; y <= m; ++y)
ans = (ans + dp[c][x][y] * CC[n][x] % mod * CC[m][y] % mod) % mod;
printf("%lld", ans);
}
|