有一棵二叉树,根结点上有一个空字符串,每个点的左儿子上的字符串为其父亲结点的字符串尾部额外加一个左括号,右儿子则是在尾部加一个右括号。树中的每个叶子结点上的字符串都分别和每个由 \(n\) 对括号组成的合法括号序列一一对应。
给定 n,求此时这棵树的最大匹配所含的边数。(对 \(998244353\) 取模)
输入:
9
输出:
10350
今天心血来潮推了下式子,然后就推出来了
\[f(n)=\sum_{i=0}^{n-1}C(2×i+1,i)-\sum_{i=\lceil\frac n2\rceil}^{n-1}C(2×i+1,2×i-n) \]明天最后一场考试,考完再回来补推导过程(