← 返回题目列表

AtCoder · pakencamp_2024_day3_1_a

A. 很多很多盐结

中文机器翻译题面 查看原题

配点 : 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 后求余数。 给出了