分数: 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