今天是 scx 的生日，她邀请了许多朋友来参加她的生日 party。scx 带着朋友们来到花园中，打算坐成一排玩游戏。

为了游戏不至于无聊，就座的方案应满足如下条件：对于任意连续的一段，男孩与女孩的数目之差不超过 $k$。很快，小朋友便找到了一种方案坐了下来开始游戏。

scx 的好朋友 sse 发现，这样的就座方案其实是很多的，所以大家很快就找到了一种，那么到底有多少种呢？

热爱数学的 scx 和她的朋友们开始思考这个问题：假设参加 party 的人中共有 $n$ 个男孩与 $m$ 个女孩，你是否能解答 scx 和 sse 的疑问呢？由于这个数目可能很多，她们只想知道这个数目除以 $12345678$ 的余数。

输入格式

共一行，包含三个非负整数 $n, m, k$ ($n, m \leq 150, k \leq 20$)，分别表示男孩数目、女孩数目和给定的常数。

输出格式

题解

假如说这道题的题目改为 "对于任意前 $l$ 个人 (即一个前缀)，男孩与女孩的数目之差不超过 $k$"，很容易想到，应该用 DP，用两维记录当前男孩个数的女孩个数，然后转移。

考虑原题，继续考虑 DP。由于不仅是前缀，而且任意一个子串都要满足要求，因此 $k = 1$ 时像 $\texttt{bgg}$ 一样的就不行了 (存在子串 $\texttt{g}$)，因此单纯地二维 DP 就不够了。

不过我们发现，每次往后加一个人，能造成影响的子串就是包含最后一个人的所有子串 (即后缀)，因此我们考虑记录后缀的男女之差，于是可以这样记录状态：

用 $f_{i, j, k, l}$ 表示当前用了 $i$ 个男孩，$j$ 个女孩，且它的所有后缀中 (包括空串)，男孩个数 - 女孩个数的最大值为 $k$，女孩个数 - 男孩个数的最大值为 $l$，满足条件的方案数。那么显然有边界 $f_{0, 0, 0, 0} = 1$。 (ps: 此处及以后用 $K$ 代表原题中的 $k$，而 $k$ 只是一个普通的下标变量)

考虑状态 $(i, j, k, l)$，如果后面放一个男孩，可以发现 $i$ 值加 $1$，$j$ 值不变，$k$ 值——即男孩个数 - 女孩个数的最大值——将会增加 $1$，$l$ 值——即女孩个数 - 男孩个数的最大值，如果它非 $0$，将会减少 $1$，如果它为 $0$，那么它将还是 $0$，因为空串中这个差值为 $0$。

那么一来，后面放一个男孩的转移方程就是 $$ f_{i+1, j, k+1, \max \{0, l-1\} } \uparrow f_{i, j, k, l} $$

完全类似地，后面放一个女孩的转移方程就是 $$ f_{i, j+1, \max \{0, k-1\}, l+1} \uparrow f_{i, j, k, l} $$

不过要注意的是，以上两种转移都需要保证新的下标 $i \leq n, j \leq m$，且 (新的) $k, l \leq K$。

枚举最终状态的任意差值 $k, l$，就有答案为 $\sum\limits_{k, l} f_{n, m, k, l}$，时空复杂度均为 $O(nmK^2)$。

代码

#include <bits/stdc++.h>
#define N 170
#define K 24
using namespace std;

const int mod = 12345678;

int n, m, D, ans = 0;
int i, j, k, l;
int f[N][N][K][K];

inline void add(int &x, const int y) {(x += y) >= mod ? x -= mod : 0;}

int main(){
    scanf("%d%d%d", &n, &m, &D);
    f[0][0][0][0] = 1;
    for(i = 0; i <= n; ++i)
        for(j = 0; j <= m; ++j)
            for(k = 0; k <= i && k <= D; ++k)
                for(l = 0; l <= j && l <= D; ++l)
                    if(f[i][j][k][l]){
                        if(i < n && k < D)
                            add(f[i + 1][j][k + 1][max(0, l - 1)], f[i][j][k][l]);
                        if(j < m && l < D)
                            add(f[i][j + 1][max(0, k - 1)][l + 1], f[i][j][k][l]);
                    }
    for(k = 0; k <= D; ++k)
        for(l = 0; l <= D; ++l)
            add(ans, f[n][m][k][l]);
    printf("%d\n", ans);
    return 0;
}

坑

坑1：要注意转移的时候，原先的 $k$ (或 $l$) 需要严格小于 $K$，才能保证 $+ 1$ 后不超过 $K$。

题目描述

输入格式

输出格式

题解

代码

坑