laekov

好久没做过数据范围这么小的题了。

看来我是有点偏科了。

这么前面的题居然都不做。

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);

}

}