蓝桥杯2022 括号序列树

Jelefy · 2022-06-21 18:36:06 · 题解

题面

有一棵二叉树，根结点上有一个空字符串，每个点的左儿子上的字符串为其父亲结点的字符串尾部额外加一个左括号，右儿子则是在尾部加一个右括号。树中的每个叶子结点上的字符串都分别和每个由 n 对括号组成的合法括号序列一一对应。 给定 n，求此时这棵树的最大匹配所含的边数。（对 998244353 取模）

样例

输入：

9

输出：

10350

题解

题意就是说，一颗深度为 2n+1 的二叉树，从根节点开始向左子节点走相当于增加一个左括号，向右子节点走相当于增加一个右括号，先设这颗二叉树是满二叉树，然后不停地将所有不表示合法括号序列的叶子节点删掉，直到所有叶子节点都表示一个长度为 2n 的括号序列。

题目要求这棵树的最大匹配，那么我们不妨先构造一个最大匹配出来。这里实际上是贪心地去构造的。

不妨考虑一下这个非常简单的情况：

     1
    /
   2
  / \
 3   4
/\   /\
...  ...

第一个结论：在最大匹配中 2 一定参与匹配。因为如果 2 不参与匹配，那么最终 2 一定还能够和 1 匹配。

第二个结论：2 一定和 1 匹配。因为如果 2 和 1 匹配，那么 3 和 4 都可以继续去匹配；如果 2 和 3 匹配，那么 1 无法再与 2 匹配，而 3 也无法再和其他点匹配了，这显然是不优的。

也就是说，对于一个度数为 1 的点我们一定会尽可能地让它匹配。于是我们可以考虑自下而上地去匹配，每匹配一个点就可以将该点删除，得到新的叶子节点，再从新的叶子节点去匹配。这样的话最终结论就是：答案等于奇数层的节点个数之和。

下一步是将节点合并。如图

          0
         /
        1
     /     \
    2       3
   /\      /
  4   5   6
  \  /\   /\
  8 9 10 11 12
  \ /\ /\ /\ /
... ... ... ...

将其合并为

         0
        /
       1
      / \
    2    3
   / \  /
  4   5/6
 / \ /  \
8 9/11 10/12
... ... ...

换句话说，我们构造一个 2n+1 层 n+1 列的图，图中左儿子在父亲节点的左边一列，右儿子在父亲节点的右边一列，规定根节点在右上角，不能走出图外，且所有路径收敛到右下角。于是我们将走到了同一个位置的所有结点归为一类，该类节点的个数就是从根节点走到该节点的路径条数。

我们把节点标号改成该位置的节点个数，得到了

         1
        /
       1
      / \
     1   1
    / \ /
   1   2
  / \ / \
 1   3   2
... ... ...

显然这就是一个形状不太一样的杨辉三角了。假如你是个**数学天才**，或许你已经看出来了这是一个杨辉三角的差分。下面解释一下这个结论。

不妨补全这个杨辉三角，得到了

       1  -1
      / \ / \
     1   0  -1
    / \ / \ / \
   1   1  -1  -1
  / \ / \ / \ / \
 1   2   0  -2  -1
... ... ... ... ...

于是就可以看出来这是一个杨辉三角对位减去一个向右错位一格的杨辉三角。于是得到了公式

由于我们要对奇数层求和，在图中也就是偶数行（因为这里首行从 0 开始了）那么对于前 n+1 行中的第 i 行（i 为偶数）就是求 \sum_{j=0}^{\frac i2} f(i,j)=C(i,\frac i2)

对于第 n+1\sim 2n 行则是上式减去一个前缀，所以最终的式子整理过后就是

利用该公式计算答案即可获得满分了

代码

#include <cstdio>
using namespace std;
const int N = 5001, M = 2e6 + 1, p = 998244353;

int fpow(int base, int t = p - 2){
    int ret = 1;
    while(t){
        if(t & 1)
            ret = 1ll * ret * base % p;
        base = 1ll * base * base % p;
        t >>= 1;
    }
    return ret;
}

int n, fac[M] = {1}, facinv[M];

int C(int n, int m){
    return 1ll * fac[n] * facinv[m] % p * facinv[n - m] % p;
}

int main(){
    scanf("%d", &n);
    int ans = 0;
    for (int i = 1; i <= 2 * n; i++)
        fac[i] = 1ll * fac[i - 1] * i % p;
    facinv[2 * n] = fpow(fac[2 * n]);
    for (int i = 2 * n; i; i--)
        facinv[i - 1] = 1ll * facinv[i] * i % p;
    for (int i = 0; i < n; i++)
        ans = (ans + C(2 * i + 1, i)) % p;
    for (int i = (n - 1) / 2 + 1; i < n; i++)
        ans = (ans - C(2 * i + 1, 2 * i - n)) % p;
    printf("\n%d", (ans + p) % p);
    return 0;
}