$dp[i][j][k][l]$ 表示 $i$ 个男生，$j$ 个女生，结尾段男生最多比女生多 $k$ 个，女生最多比男生多 $l$ 个。

$dp[i + 1][j][k + 1][\max\{l - 1, 0\}]$ $+=$ $dp[i][j][k][l]$

$dp[i][j+1][\max\{k - 1, 0\}][l+1]$ $+=$ $dp[i][j][k][l]$

#include <bits/stdc++.h>

const int MOD = 12345678;
const int N = 157;
int dp[N][N][22][22];

void M(int &x) {
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    dp[0][0][0][0] = 1;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int o = 0; o <= k; o++)
                for (int p = 0; p <= k; p++) if (dp[i][j][o][p]) {
                    if (i < n && o < k)
                        M(dp[i + 1][j][o + 1][std::max(p - 1, 0)] += dp[i][j][o][p]);
                    if (j < m && p < k)
                        M(dp[i][j + 1][std::max(o - 1, 0)][p + 1] += dp[i][j][o][p]);
                }
    int ans = 0;
    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= k; j++)
            M(ans += dp[n][m][i][j]);
    printf("%d\n", ans);
    return 0;
}

View Code