dp，f[i][j][k][l]表示前i个人，j个男生，后缀中男生比女生最多多k人，最少少l人的方案数。
/** * Problem:Party * Author:Shun Yao * Time:2013.5.30 * Result:Accepted * Memo:DP */#include#include #include long min(long x, long y) { return x < y ? x : y;}long max(long x, long y) { return x > y ? x : y;}const long MOD = 12345678;long n, m, lim, N, f[20043891], ans;int main() { freopen("party.in", "r", stdin); freopen("party.out", "w", stdout); scanf("%ld%ld%ld", &n, &m, &lim); N = n + m; memset(f, 0, sizeof f);#define F(a, b, c, d) f[(((a) * (n + 1) +(b)) * (lim + 1) + (c)) * (lim + 1) + (d)] long i, j, k, l, J, K, L; F(0, 0, 0, 0) = 1; for (i = 0; i < N; ++i) { for (J = min(i, n), j = 0; j <= J; ++j) for (K = min(j, lim), k = 0; k <= K; ++k) for (L = min(i - j, lim), l = 0; l <= L; ++l) { if (k < lim && j < n) { long &a = F(i + 1, j + 1, k + 1, max(l - 1, 0)); a = (a + F(i, j, k, l)) % MOD; } if (l < lim && i - j < m) { long &b = F(i + 1, j, max(k - 1, 0), l + 1); b = (b + F(i, j, k, l)) % MOD; } } } ans = 0; for (k = 0; k <= lim; ++k) for (l = 0; l <= lim; ++l) ans = (ans + F(N, n, k, l)) % MOD; printf("%ld", ans); fclose(stdin);fclose(stdout); return 0;}