分数: 700 点
问题陈述
给你整数 N 和 K。考虑一个序列 a=(a_1,a_2,\dots,a_K) 长度 K 满足以下所有条件:
- a_i 是一个整数,使得 1 \le a_i \le N.
- 中的所有元素 a 不同。
让我们排列所有可能的序列 a 按字典顺序形成一个“序列的序列”,称为字典 s.
给定一个序列 字典中存在的 P 字典中存在的 s,针对每个整数回答以下问题 t=1,2,\dots,N:
- 求模数 998244353,序列 b 满足以下所有条件:
- 序列 b 存在于字典中 s.
- 整数 t 包含在序列中 b.
- 序列 b 按字典顺序小于或等于序列 P.
序列的字典顺序是什么?
一个序列 A = (A_1, \ldots, A_{|A|}) is 按字典顺序严格少于 比 B = (B_1, \ldots, B_{|B|}) 当且仅当满足以下 1. 或 2. 时:- |A|<|B| 和 (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
- 有一个整数 1\leq i\leq \min\{|A|,|B|\} 满足以下两个条件:
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
- A_i < B_i
约束
- 所有输入值均为整数。
- 1 \le K \le N \le 3 \times 10^5
- P 满足问题陈述中的条件。
输入
输入由标准输入按以下格式给出:
N K P_1 P_2 \dots P_K
输出
打印
您选择的 N 行。
的 i- 第行应包含问题的答案 t=i 作为整数。
示例输入 1
4 2 3 2
示例输出 1
5 5 4 2
在此输入中, N=4,K=2.
这里,字典 s is ((1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)).
字典中的序列 s 按字典顺序小于或等于 (3,2),
- 五个序列包含 1: (1,2),(1,3),(1,4),(2,1),(3,1),
- 五个序列包含 2: (1,2),(2,1),(2,3),(2,4),(3,2),
- 四个序列包含 3: (1,3),(2,3),(3,1),(3,2),
- 两个序列包含 4: (1,4),(2,4).
示例输入 2
18 13 5 13 11 2 18 1 10 15 17 4 12 7 3
示例输出 2
925879409 905921009 665544804 665544719 783035803 349952762 349952758 349952757 349952757 349921178 212092637 710350150 378895603 129113201 129111892 129098081 129096772 110181652