题目链接：Codeforces 1152D

Neko 把所有长度为 $2n$ 的合法括号序列插入到一棵 $\text{Trie}$ 树中，接着 Aki 向他提出了一个有趣的问题：在这个 $\text{Trie}$ 树中的最大匹配（找到最大的一组边，使得没有两条边具有公共顶点）的大小是多少？答案对 $10 ^ 9 + 7$ 取模。

数据范围：$1 \le n \le 1000$。

Solution

可以把最大匹配转化为：所有深度为奇数的点的数量（特殊地，定义 $\text{Trie}$ 树中根节点的深度为 $0$），具体构造方法就是对于每个深度为奇数的点，选择其下方的任意一条边。

我们可以直接 $\text{DP}$ 所有前缀的数量，设 $f(i, j)$ 表示有 $i$ 个左括号，$j$ 个右括号的前缀数量。转移方程非常简单：

$$ f(i, j) = f(i - 1, j) + f(i, j - 1) \quad (i \ge j) $$

那么答案就是 $\sum_{2 \not \mid i + j} f(i, j)$。

时间复杂度：$\mathcal O(n ^ 2)$。

Code

#include <cstdio>

const int N = 1e3 + 5;
const int P = 1e9 + 7;

int n, f[N][N];

void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
int main() {
    scanf("%d", &n);
    f[0][0] = 1;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            f[i][j] = (f[i - 1][j] + f[i][j - 1]) % P;
            if ((i + j) & 1) add(ans, f[i][j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}