「ZJOI 2008」生日聚会

题目大意：给 $m$ 个男孩和 $n$ 个女孩排队，求任意区间男女之差不超过 $k$ 的方案数。$n,m≤150，k≤20$

前缀的后缀是子串。

设 $f[i][j][a][b]$ 表示在前 $i+j$ 个人中，男生有 $i$ 个，女生有 $j$ 个，且在当前所有的后缀中，男生最多比女生多 $a$ 个，女生最多比男生多 $b$ 个的方案数。

如 ♂♂♂♀♀♀♂，这种状态是 $f[4][3][1][2]$，即从最右边的 ♂ 开始往前的一段连续区间里，男生最多比女生多 $1$ 个，女生最多比男生多 $2$ 个。

有状态转移方程

$$f[i][j][a][b]=f[i-1][j][a-1][b+1]+f[i][j-1][a+1][b-1]$$

但这种转移在实现起来会很不方便，比如 ♂♀♀，应该是 $f[1][2][0][2]$ 由 $f[1][1][0][1]$ 转移过来，但上式会由 $f[1][1][1][1]$ 转移，因此我们需要改变一下转移的方向：

$$f[i+1][j][a+1][b-1] += f[i][j][a][b] \\ f[i][j+1][a-1][b+1] += f[i][j][a][b]$$

#include <cstdio>

const int N = 155, M = 25, P = 12345678;
int f[N][N][M][M], n, m, k, ans;

int main() {
    scanf("%d%d%d", &n, &m, &k);
    f[0][0][0][0] = 1;
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            for (int a = 0; a <= k; ++a)
                for (int b = 0; b <= k; ++b)
                    (f[i+1][j][a+1][b>0?b-1:0] += f[i][j][a][b]) %= P,
                    (f[i][j+1][a>0?a-1:0][b+1] += f[i][j][a][b]) %= P;
    for (int i = 0; i <= k; ++i)
        for (int j = 0; j <= k; ++j)
            ans = (ans + f[n][m][i][j]) % P;
    printf("%d\n", ans);
    return 0;
}

时间复杂度 $O(nmk^2)$