AT_pakencamp_2024_day3_1_a Many Many Shiomusubi

考虑如下问题。 > 给定正整数 $N$，一个长度为 $N$ 的正整数序列 $S=(S_1,S_2,\dots,S_N)$，以及一个仅由 $\mathtt{L}$ 或 $\mathtt{R}$ 组成的长度为 $N$ 的字符串 $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$ 的速度向其朝向前进。当有多个盐饭团处于同一坐标时，会发生以下事件： > > - 在该坐标上，大小最大的盐饭团中编号最大的那个，把该坐标上的其他盐饭团全部吃掉。被吃掉的盐饭团会消失。这一过程中剩下的盐饭团的朝向和大小都不会改变。 > > 请计算 $10^{100}$ 秒后，剩下的盐饭团大小的总积。 > > 给定整数 $N, M$。 > > 满足 $1\leq S_i\leq M$ $(1\leq i\leq N)$ 的输入共有 $(2M)^N$ 种，请求出上述所有情况的答案之和，并对 $998244353$ 取模。

输入由标准输入按以下格式给出。 > $N$ $M$

请输出答案。

## 部分分 - 对于 $N,M \leq 300$ 的数据集，答对可获得 $15$ 分。 - 对于 $N,M \leq 3000$ 的数据集，另可获得 $15$ 分。 - 对于无附加限制的数据集，另可获得 $70$ 分。 ## 样例解释 1 对于要考虑的 $16$ 种输入，剩余盐饭团大小的总积如下： $$ \begin{array}{cccc} & S=(1,1) & S=(1,2) & S=(2,1) & S=(2,2) \\ \text{D=LL} & 1 & 2 & 2 & 4 \\ \text{D=LR} & 1 & 2 & 2 & 4 \\ \text{D=RL} & 1 & 2 & 2 & 2 \\ \text{D=RR} & 1 & 2 & 2 & 4 \\ \end{array} $$ 因此，答案是 $34$。 ## 样例解释 2 不要忘记对 $998244353$ 取模。 ## 数据范围 - $1 \leq N,M\leq 2\times 10^5$ - 输入均为整数。 由 ChatGPT 5 翻译。