← 返回题目列表

AtCoder · abc380_g

G. 另一个随机播放窗口

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

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