题目内容

程序语言中有各种各样的括号，比如圆括号$()$,方括号$[]$,花括号$<>$,等等。

如果一个括号串$s$满足下列三个条件中的至少一个，则我们认为该括号串是合法的。

思路

  此题是一个较为经典的数学问题，首先有一个前置问题，由n个相同的括号可以组成多少个不同的括号串，这个数字其实就是一个卡特兰数，并且是卡特兰数的一个经典应用之一，关于卡特兰数的计算以及证明可以自行学习，在我们知道n个相同括号能够组成不同的括号串的个数之后，再来思考如果此时有k种括号任意使用，那么不同的括号串个数将会是原来的多少，其实不难看出在一个合法的括号串当中，其中任意一个配对的括号都可以置换成k种括号中的任意一种，并且在任意置换中括号穿都不会相同，所以显然括号串的数量将会扩充为原来的k^n^倍，所以n个k种类的括号任意组合最终不同的合法括号串数量即为n的卡特兰数*k^n^

代码

python

mod = 998244353
N = 10010
d = [0] * N
n, k = map(int, input().split())