← 返回题目列表

AtCoder · arc218_e

E. 反向和反向

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

分数: 800 点

问题陈述

对于排列 p=(p_1,p_2,\dots,p_N) of (1,2,\dots,N) 和一个正整数 M,让 f(p,M) 表示以下问题的答案。

执行以下操作 M 次 p.

  • 选择一个整数 i 与 1 \le i \le N-1,并反转每个 (p_1,p_2,\dots,p_i) 和 (p_{i+1},p_{i+2},\dots,p_N)。正式地,替换 p 与 (p_i,p_{i-1},\dots,p_1,p_N,p_{N-1},\dots,p_{i+1}).

有 (N-1)^M 可能的操作顺序。求总和,取模 998244353,“的反转次数 p 之后 对所有此类序列进行“ M 操作”。

给你一个排列 P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N)。处理以下查询 Q 次。

  • 给你一个整数 x 与 1 \le x \le N-1 和一个正整数 K。互换 P_x 和 P_{x+1}。然后,找到 f(P,K).

约束

  • 2 \le N \le 2 \times 10^5
  • 1 \le Q \le 2 \times 10^5
  • P 是一个排列 (1,2,\dots,N).
  • 1 \le x \le N-1
  • 1 \le K \le 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N Q
P_1\ P_2\ \dots\ P_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

每个查询均按以下格式给出:

x K

输出

输出 Q 行。的 i- 第行应包含以下问题的答案 \mathrm{query}_i.


示例输入 1

3 2
1 3 2
1 1
2 1

示例输出 1

4
4

对于第一个查询,交换 P_1 和 P_2 给出 P=(3,1,2)。有两种可能的操作顺序,如下所示:

  • 选择 i = 1. P 变为 (3,2,1)。反转次数为 3.
  • 选择 i = 2. P 变为 (1,3,2)。反转次数为 1.

因此,答案是 3+1=4.

对于第二个查询,交换 P_2 和 P_3 给出 P=(3,2,1)。有两种可能的操作顺序,如下所示:

  • 选择 i = 1. P 变为 (3,1,2)。反转次数为 2.
  • 选择 i = 2. P 变为 (2,3,1)。反转次数为 2.

因此,答案是 2+2=4.


示例输入 2

4 4
3 2 4 1
2 1
2 2
3 3
1 4

示例输出 2

11
28
67
242

示例输入 3

10 7
7 9 3 10 5 2 4 6 8 1
2 29
1 86
3 30
8 64
1 24
1 9
5 55

示例输出 3

29362950
633265500
847469581
741165544
385334408
653522086
169485402