/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
整数 N,K が与えられます。このとき、以下の条件を全て満たす長さ K の数列 a=(a_1,a_2,\dots,a_K) を考えます。
- a_i は 1 \le a_i \le N を満たす整数である
- a の全ての要素は相異なる
a として考えられる数列を辞書順に全て並べた 「数列の列」 を辞書 s とします。
辞書 s 中に存在する数列 P が与えられるので、整数 t=1,2,\dots,N に対して以下の質問に答えてください。
- 以下の条件を全て満たす数列 b の個数を 998244353 で割った余りを求めよ。
- 数列 b は辞書 s 中に存在する。
- 数列 b 中に整数 t が含まれる。
- 数列 b は辞書順で数列 P 以下である。
数列の辞書順とは？
数列 A = (A_1, \ldots, A_{|A|}) が 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|\} が存在して、下記の 2 つがともに成り立つ。
- (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=((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) の 5 個
- 2 が含まれるものは (1,2),(2,1),(2,3),(2,4),(3,2) の 5 個
- 3 が含まれるものは (1,3),(2,3),(3,1),(3,2) の 4 個
- 4 が含まれるものは (1,4),(2,4) の 2 個
です。
入力例 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
Score: 700 points
Problem Statement
You are given integers N and K. Consider a sequence a=(a_1,a_2,\dots,a_K) of length K that satisfies all of the following conditions:
- a_i is an integer such that 1 \le a_i \le N.
- All elements in a are different.
Let us arrange all possible sequences a in lexicographical order to form a "sequence of sequences" called the dictionary s.
Given a sequence P that exists in the dictionary s, answer the following question for each integer t=1,2,\dots,N:
- Find the number, modulo 998244353, of sequences b that satisfy all of the following conditions:
- The sequence b exists in the dictionary s.
- The integer t is contained in the sequence b.
- The sequence b is lexicographically less than or equal to the sequence P.
What is lexicographical order for sequences?
A sequence A = (A_1, \ldots, A_{|A|}) is lexicographically strictly less than B = (B_1, \ldots, B_{|B|}) if and only if 1. or 2. below is satisfied:- |A|<|B| and (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
- There is an integer 1\leq i\leq \min\{|A|,|B|\} that satisfies both of the following:
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
- A_i < B_i
Constraints
- All input values are integers.
- 1 \le K \le N \le 3 \times 10^5
- P satisfies the condition in the problem statement.
Input
The input is given from Standard Input in the following format:
N K P_1 P_2 \dots P_K
Output
Print N lines in total.
The i-th line should contain the answer to the problem for t=i as an integer.
Sample Input 1
4 2 3 2
Sample Output 1
5 5 4 2
In this input, N=4,K=2.
Here, the dictionary 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)).
Among the sequences in the dictionary s that are lexicographically less than or equal to (3,2),
- five sequences contain 1: (1,2),(1,3),(1,4),(2,1),(3,1),
- five sequences contain 2: (1,2),(2,1),(2,3),(2,4),(3,2),
- four sequences contain 3: (1,3),(2,3),(3,1),(3,2),
- two sequences contain 4: (1,4),(2,4).
Sample Input 2
18 13 5 13 11 2 18 1 10 15 17 4 12 7 3
Sample Output 2
925879409 905921009 665544804 665544719 783035803 349952762 349952758 349952757 349952757 349921178 212092637 710350150 378895603 129113201 129111892 129098081 129096772 110181652