分数: 575 点
问题陈述
给你一个排列 P of (1,2,\dots,N) 和一个整数 K.
求期望值,模 998244353, 的反转数 P 执行以下操作后:
- 首先,选择一个整数 i 之间均匀随机 1 和 N - K + 1,包括在内。
- 然后,随机播放 P_i, P_{i+1}, \dots, P_{i+K-1} 均匀随机。
反转数是多少?
序列的反转数 (A_1, A_2, \dots, A_N) 是整数对的数量 (i, j) 满意 1 \le i < j \le N 和 A_i > A_j.什么是“期望值模 998244353“是什么意思?
可以证明,所求的期望值总是有理数。在这个问题的约束下,当这个值表示为不可约分数时 \frac{P}{Q},还可以证明 Q \not\equiv 0 \pmod{998244353}。因此,有一个唯一的整数 R 满意 R \times Q \equiv P \pmod{998244353}, \ 0 \le R < 998244353。报告这个整数 R.约束
- 所有输入值均为整数。
- 1 \le K \le N \le 2 \times 10^5
- P 是一个排列 (1,2,\dots,N).
输入
输入由标准输入按以下格式给出:
N K P_1 P_2 \dots P_N
输出
在一行中打印答案。
示例输入 1
4 2 1 4 2 3
示例输出 1
166374061
该操作改变了排列 P 分为以下内容:
- (1,4,2,3) ...概率 1/2
- (4,1,2,3) ...概率 1/6
- (1,2,4,3) ...概率 1/6
- (1,4,3,2) ...概率 1/6
反转数的期望值为 \displaystyle 2 \times \frac{1}{2} + 3 \times \frac{1}{6} + 1 \times \frac{1}{6} + 3 \times \frac{1}{6} = \frac{13}{6}.
\displaystyle \frac{13}{6} 模数 998244353 is 166374061,所以打印这个数字。
示例输入 2
1 1 1
示例输出 2
0
示例输入 3
10 6 7 4 10 5 6 1 8 2 3 9
示例输出 3
499122200