配点 : 100 点
問題文
考虑以下问题。 有
正整数 N ,长度 N 的正整数序列 给出了 S=(S_1,S_2,\dots,S_N) ,长度 N 可以得到第 \mathtt{L} 或 至少 \mathtt{R} 仅由…组成的字符串 D=D_1D_2\dots D_N 。 对于
在数轴上 N 盐结, 它的编号为1,2,\dots,N 。盐结 i 是坐标 i 其大小为 S_i 。盐结 i 方向为文本 当 D_i 什么时候可以工作D_i=\mathtt{L} 时,数轴的负方向为 当D_i=\mathtt{R} 时,它指向数轴的正方向。
从现在开始,饭团会动了。盐结 i 以秒为单位 S_i 朝您面对的方向移动。 当多个盐结位于同一坐标时,会发生以下事件。
- 该坐标处编号最大的 Shiomusubi 吃掉了该坐标处的另一个 Shiomusubi。一旦吃完,饭团就消失了。这不会改变剩余饭团的方向或大小。
10^{100} 秒后,求剩余饭团的总乘积。 满足
整数 N,M 。 对于
1\leq S_i\leq M (1\leq i\leq N) 的输入是 (2M)^N 解决上述问题的方法有很多种。 998244353 后求余数。
制約
- 1 \leq N,M\leq 2\times 10^5
- 所有输入均为整数
部分点
- N,M \leq 300 的数据集,15 授予积分。
- N,M \leq 3000 的数据集, 15 授予积分。
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 70 授予积分。
入力
输入是按以下格式从标准输入给出的。
N M
出力
打印答案。 来自
入力例 1
2 2
出力例 1
34
要考虑的输入 16 街道剩余饭团的总大小如下。
| S=(1,1) | S=(1,2) | S=(2,1) | S=(2,2) | |
|---|---|---|---|---|
| D=\mathtt{LL} | 1 | 2 | 2 | 4 |
| D=\mathtt{LR} | 1 | 2 | 2 | 4 |
| D=\mathtt{RL} | 1 | 2 | 2 | 2 |
| D=\mathtt{RR} | 1 | 2 | 2 | 4 |
因此,答案是 34 。
入力例 2
200000 200000
出力例 2
815432809
总和 除以 998244353 后求余数。 给出了