E - Existence Counting

Contest Duration: 2024-03-17(Sun) 12:00 - 2024-03-17(Sun) 14:00 (local time) (120 minutes) Back to Home

E - Existence Counting Editorial

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$ であるときの質問の答えを整数として出力せよ。

入力例 1Copy

Copy

4 2
3 2

出力例 1Copy

Copy

この入力では、 $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$ 個

です。

入力例 2Copy

Copy

18 13
5 13 11 2 18 1 10 15 17 4 12 7 3

出力例 2Copy

Copy

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 1Copy

Copy

4 2
3 2

Sample Output 1Copy

Copy

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 2Copy

Copy

18 13
5 13 11 2 18 1 10 15 17 4 12 7 3

Sample Output 2Copy

Copy