好久没做过数据范围这么小的题了。
看来我是有点偏科了。
这么前面的题居然都不做。
dp就好。状态是前面男-女的最大值和最小值还有现在有多少男。然后滚动。
我毕竟太年轻。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 159;
const int maxk = 49;
const int kbase = 23;
const int mod = 12345678;
int n, m, c, f[2][maxn][maxk][maxk];
#define incm(_x_,_b_) { \
int& _a_ = _x_; \
_a_ += _b_; \
if (_a_ >= mod) \
_a_ %= mod; \
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d%d", &n, &m, &c);
if (c == 0) {
puts("0");
}
else {
int prv = 0, cur = 1;
memset(f, 0, sizeof(f));
f[cur][0][kbase][kbase] = 1;
for (int i = 0; i < m + n; ++ i) {
swap(cur, prv);
for (int j = 0; j <= n; ++ j)
for (int k = kbase - c; k <= kbase + c; ++ k)
for (int l = kbase - c; l <= kbase + c; ++ l)
f[cur][j][k][l] = 0;
for (int j = 0; j <= n; ++ j)
for (int k = kbase - c; k <= kbase + c; ++ k)
for (int l = k; l <= k + c && l <= kbase + c; ++ l)
if (f[prv][j][k][l]) {
int d = j * 2 - i + kbase;
if (l - k < c || d < l)
incm(f[cur][j + 1][k][max(d + 1, l)], f[prv][j][k][l]);
if (l - k < c || d > k)
incm(f[cur][j][min(d - 1, k)][l], f[prv][j][k][l]);
}
}
int ans = 0;
for (int k = kbase - c; k <= kbase + c; ++ k)
for (int l = k; l <= k + c && l <= kbase + c; ++ l)
incm(ans, f[cur][n][k][l]);
printf("%d\n", ans);
}
}