← 返回题目列表

AtCoder · acl1_e

E. 随机播放窗口

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

分数: 900 点

问题陈述

给定一个排列 p_1, p_2, \dots, p_N of (1, 2, ..., N) 和一个整数 K。 Maroon 执行以下操作 i = 1, 2, \dots, N - K + 1 按此顺序:

  • 随机播放 p_i, p_{i + 1}, \dots, p_{i + K - 1} 均匀随机。

求所有运算完成后数列的反转数的期望值,并取模打印 998244353.

更具体地说,从这个问题的约束来看,可以证明期望值始终是一个有理数,可以表示为一个不可约分数 \frac{P}{Q},并且整数 R 满足 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 是唯一确定的。打印此内容 R.

这里,序列的反转数 a_1, a_2, \dots, a_N 被定义为有序对的数量 (i, j) 满足 i < j, a_i > a_j.

约束

  • 2 \leq N \leq 200,000
  • 2 \leq K \leq N
  • (p_1, p_2, \dots, p_N) 是一个排列 (1, 2, \dots, N).
  • 输入中的所有值都是整数。

输入

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

N K
p_1 p_2 ... p_N

输出

打印期望值模 998244353.


示例输入 1

3 2
1 2 3

示例输出 1

1

最终序列是以下之一 (1, 2, 3), (2, 1, 3), (1, 3, 2), (2, 3, 1),每个都有概率 \frac{1}{4}。 他们的反转数是 0, 1, 1, 2 分别,所以期望值为 1.


示例输入 2

10 3
1 8 4 9 2 3 7 10 5 6

示例输出 2

164091855