103806: [Atcoder]ABC380 G - Another Shuffle Window
Description
Score : $575$ points
Problem Statement
You are given a permutation $P$ of $(1,2,\dots,N)$ and an integer $K$.
Find the expected value, modulo $998244353$, of the inversion number of $P$ after performing the following operation:
- First, choose an integer $i$ uniformly at random between $1$ and $N - K + 1$, inclusive.
- Then, shuffle $P_i, P_{i+1}, \dots, P_{i+K-1}$ uniformly at random.
What is the inversion number?
The inversion number of a sequence $(A_1, A_2, \dots, A_N)$ is the number of integer pairs $(i, j)$ satisfying $1 \le i < j \le N$ and $A_i > A_j$.What does "expected value modulo $998244353$" mean?
It can be proved that the sought expected value is always rational. Under the constraints of this problem, when this value is represented as an irreducible fraction $\frac{P}{Q}$, it can also be proved that $Q \not\equiv 0 \pmod{998244353}$. Thus, there is a unique integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}, \ 0 \le R < 998244353$. Report this integer $R$.Constraints
- All input values are integers.
- $1 \le K \le N \le 2 \times 10^5$
- $P$ is a permutation of $(1,2,\dots,N)$.
Input
The input is given from Standard Input in the following format:
$N$ $K$ $P_1$ $P_2$ $\dots$ $P_N$
Output
Print the answer in one line.
Sample Input 1
4 2 1 4 2 3
Sample Output 1
166374061
The operation changes the permutation $P$ into the following:
- $(1,4,2,3)$ ... probability $1/2$
- $(4,1,2,3)$ ... probability $1/6$
- $(1,2,4,3)$ ... probability $1/6$
- $(1,4,3,2)$ ... probability $1/6$
The expected value of the inversion number is $\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}$ modulo $998244353$ is $166374061$, so print this number.
Sample Input 2
1 1 1
Sample Output 2
0
Sample Input 3
10 6 7 4 10 5 6 1 8 2 3 9
Sample Output 3
499122200
Output
得分：575分
问题陈述
给你一个整数序列$P$，它是$(1,2,\dots,N)$的一个排列，以及一个整数$K$。
求执行以下操作后排列$P$的逆序数的期望值，对$998244353$取模：
- 首先，从$1$到$N-K+1$（含）之间均匀随机选择一个整数$i$。
- 然后，将$P_i, P_{i+1}, \dots, P_{i+K-1}$均匀随机地打乱。
什么是逆序数？
一个序列$(A_1, A_2, \dots, A_N)$的逆序数是指满足$1 \le i < j \le N$且$A_i > A_j$的整数对$(i, 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$取模是$166374061$，所以打印这个数。
示例输入 2
1 1 1
示例输出 2
0
示例输入 3
10 6 7 4 10 5 6 1 8 2 3 9
示例输出 3
499122200