← 返回题目列表

AtCoder · arc174_e

E. 存在计数

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

分数: 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. 时:
  1. |A|<|B| 和 (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
  2. 有一个整数 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