Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届决赛真题-括号序列树
题目 2714:

蓝桥杯2022年第十三届决赛真题-括号序列树

时间限制: 2s 内存限制: 320MB 提交: 44 解决: 11

题目描述

有一棵二叉树,根结点上有一个空字符串,每个点的左儿子上的字符串为其父亲结点的字符串尾部额外加一个左括号,右儿子则是在尾部加一个右括号。树中的每个叶子结点上的字符串都分别和每个由 n 对括号组成的合法括号序列一一对应。

给定 n,求此时这棵树的最大匹配所含的边数。

输入格式

输入一行包含一个整数 n。 

输出格式

输出一行包含一个整数表示满足条件的序列的数量,答案可能很大,请输出答案除以 998244353 的余数。 

样例输入

9

样例输出

10350

提示

对于 20% 的评测用例,n ≤ 10 ;

对于 40% 的评测用例,n ≤ 300 ;

对于 60% 的评测用例,n ≤ 5000 ;

对于 85% 的评测用例,n ≤ 105

对于所有评测用例,1 ≤ n ≤ 106

标签