← 返回题目列表

AtCoder · arc217_b

B. 元素不高

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

分数: 700 点

问题陈述

给你整数 N,K 和一个整数序列 A=(A_1,A_2,\ldots,A_K) 长度 K。保证每个元素 A 介于 1 和 N,包含在内,并且所有元素都是不同的。

对于排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N),定义 f(P) 如下。

  • 可以执行以下操作的最大次数 P.
    • 选择 2\le i\le N 满意 P_i < \max(P_1,P_2,\ldots,P_{i-1}),然后移动 P_i 到前面。也就是说,替换 P 与 (P_i,P_1,P_2,\ldots,P_{i-1},P_{i+1},\ldots,P_N).

有 (N-K)! 排列 P of (1,2,\ldots,N) 满意 P_i=A_i 为 i=1,2,\ldots,K。求总和,取模 998244353,属于 f(P) 超过所有此类排列。

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1\le T\le 10^5
  • 1\le K\le N
  • 总和 N 所有测试用例最多 5\times 10^5.
  • 1\le A_i\le N
  • 的所有元素 A 是不同的。
  • 所有输入值均为整数。

输入

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

N K
A_1 A_2 \ldots A_K

输出

按顺序输出测试用例的答案,以换行符分隔。


示例输入 1

3
3 1
1
4 2
3 2
10 3
2 1 7

示例输出 1

2
6
1382640

考虑第一个测试用例。

排列 P of (1,2,\ldots,N) 满意 P_i=A_i 为 i=1,2,\ldots,K 是 P=(1,2,3) 和 P=(1,3,2),给出两种排列。

当 P=(1,2,3),无法执行任何操作,因此 f(P)=0.

当 P=(1,3,2),可以执行两次操作,如下所示。

  • 选择 i=3。现在 P=(2,1,3).
  • 选择 i=2。现在 P=(1,2,3).

该操作不能执行三次或多次,因此 f(P)=2 在这种情况下。

因此,答案是 0+2=2.