UOI 的题面是一个外星八爪鱼用脚写的。
由于题面写的很差,大D米不得不不断提问来确认题意。但外星八爪鱼没有手回复,只好叫你来帮忙。
这些问题可以抽象成一个栈的结构,初始为空,大D米有两种操作:
push
:新提一个问题置于栈顶。此时你需要对问题做出以下两种回应之一:R(no Response)或 B(Buzhidao)。pop
:大D米在胡乱提交后知道了栈顶问题的答案,问题从栈中移除。
这些操作按时间顺序形成了一个长为 $2k$ 的操作序列,保证操作序列合法,且做完所有操作后栈中没有元素。
你需要保证任意时刻栈中 R 类回应数量不超过 $c_r$,B 类回应数量不超过 $c_b$,否则会被大D米发现你是随便回的。
两种回应都很敷衍,B 类回应更让人愤怒。如果你的整个回应过程中,做出了 $p_r$ 次 R 类回应,$p_b$ 次 B 类回应,大D米的愤怒值将是 $p_rp_b^2$。
现在,你想知道所有回应方案中大D米愤怒值的总和。答案可能很大,你只需要输出其对 $998244353$ 取模的结果。
输入格式
第一行三个整数 $k,c_r,c_b$,表示操作序列长度、栈中 R 类回应数量限制、栈中 B 类回应数量限制。
接下来 $2k$ 行每行一个为 push
或 pop
的字符串,描述操作序列。
输出格式
输出一行一个整数,表示所有回应方案中大D米愤怒值的总和对 $998244353$ 取模后的结果。
样例一
input
3 1 2 push push push pop pop pop
output
12
explanation
由于操作过程是先放入三个问题再依次移除,所以要求三个回复中恰好有 $1$ 个是 R,$2$ 个是 B。总共有 $\binom{3}{2} = 3$ 个方案,每个方案的愤怒值都是 $1 \times 2^2 = 4$,所以答案为 $3 \times 4 = 12$。
样例二
input
3 1 2 push push pop push pop pop
output
14
explanation
若第一个问题回的是 R,则剩余两个问题都只能选择回 B,总共有 $1$ 种方案,权值为 $1 \times 2^2 = 4$;
若第一个问题回的是 B,则剩余两个问题没有限制。
- 若这两次都回 B,则有 $1$ 种方案,权值为 $0 \times 3^2 = 0$;
- 若这两次都回 R,则有 $1$ 种方案,权值为 $2 \times 1^2 = 2$;
- 若这两次回应不同,则有 $2$ 种方案,权值为 $1 \times 2^2 = 4$。
所以所有方案的愤怒值和为 $1 \times 4 + 1 \times 0 + 1 \times 2 + 2 \times 4 = 14$。
样例三
见附加文件中 ex_stack3.in
与 ex_stack3.out
,该组样例满足子任务 1 的性质。
样例四
见附加文件中 ex_stack4.in
与 ex_stack4.out
,该组样例满足子任务 3 的性质。
样例五
见附加文件中 ex_stack5.in
与 ex_stack5.out
,该组样例满足子任务 5 的性质。
限制与约定
对于 $100\%$ 的数据,$1 \leq k \leq 2500, 0 \leq c_r,c_b \leq k$,保证操作序列合法,且做完所有操作后栈中没有元素。
子任务编号 | $k\le$ | 特殊性质 | 分值 |
---|---|---|---|
$1$ | $20$ | 无 | $20$ |
$2$ | $40$ | $15$ | |
$3$ | $80$ | $15$ | |
$4$ | $250$ | $20$ | |
$5$ | $2500$ | $c_r = 1$ | $10$ |
$6$ | $c_r=c_b=k$ | $5$ | |
$7$ | 无 | $15$ |
时间限制:$\texttt{1s}$
空间限制:$\texttt{512MB}$