/ 
実行時間制限: 8 sec / メモリ制限: 1024 MiB
配点 : 1400 点
問題文
L=10^8 とします．
整数 N 及び長さ M の非負整数列 A=(A_1,A_2,\cdots,A_M) (0 \leq A_i < L) が与えられます． 各 k=1,2,\cdots,N に対して，次の問題を解いてください．
1 から k までの番号のついた k 個の赤いボールと，1 から k までの番号のついた k 個の青いボールがあります． 今から以下の方法で各ボールに実数を書き込みます． なお，すべてのランダムな選択は独立です．
-
各 1 \leq i \leq k について，赤いボール i に書き込む数は，L \times (i-1)+A_{j_i} である． ただし j_i は 1 以上 M 以下の範囲で一様ランダムに選ばれた整数である．
-
各 1 \leq i \leq k について，青いボール i に書き込む数は [0,k \times L) の範囲で一様ランダムに選ばれた実数である．
すべてのボールに数を書き込んだあと以下の条件が満たされている確率を \text{mod }{998244353} で求めてください．
- 任意の実数 x (0 \leq x \leq k \times L) に対して，「x 以下の数が書き込まれた赤いボールの個数」\geq「x 以下の数が書き込まれた青いボールの個数」が成立する．
確率 \text{mod }{998244353} の定義
求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、求める有理数を既約分数 \frac{P}{Q} で表した時、Q \neq 0 \pmod{998244353} となることが証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。
制約
- 1 \leq N \leq 250000
- 1 \leq M \leq 250000
- 0 \leq A_i < L=10^8
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N M A_1 A_2 \cdots A_M
出力
N 行出力せよ． i 行目には k=i に対する答えを出力せよ．
入力例 1
2 1 50000000
出力例 1
499122177 686292993
- k=1: 条件を満たす確率は 1/2 です．
- k=2: 条件を満たす確率は 5/16 です．
入力例 2
3 5 78682095 25048034 71067122 94666780 1927105
出力例 2
741897823 406774904 435399949
入力例 3
10 7 40490214 25131781 2271243 52064315 34467030 27419560 56103210
出力例 3
457696464 497746652 679391958 742383895 245278311 709723420 729551291 1911348 414224424 650563524
Score : 1400 points
Problem Statement
Let L=10^8.
You are given an integer N and a non-negative integer sequence A=(A_1,A_2,\cdots,A_M) of length M (0 \leq A_i < L). For each k=1,2,\cdots,N, solve the following problem:
There are k red balls numbered from 1 to k and k blue balls numbered from 1 to k. Now, you will write a real number on each ball in the following way. Here, all random choices are independent.
-
For each 1 \leq i \leq k, the number written on red ball i is L \times (i-1)+A_{j_i}. Here, j_i is an integer chosen uniformly at random from the range between 1 and M (inclusive).
-
For each 1 \leq i \leq k, the number written on blue ball i is a real number chosen uniformly at random from the range [0,k \times L).
Find the probability, modulo 998244353, that the following condition is satisfied after writing numbers on all balls.
- For any real number x (0 \leq x \leq k \times L), "the number of red balls with a number written that is at most x" \geq "the number of blue balls with a number written that is at most x".
Definition of probability modulo 998244353
It can be proved that the desired probability is always a rational number. Also, under the constraints of this problem, it can be proved that if the desired rational number is represented as an irreducible fraction \frac{P}{Q}, then Q \neq 0 \pmod{998244353}. Therefore, there uniquely exists an integer R satisfying R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353. Output this R.
Constraints
- 1 \leq N \leq 250000
- 1 \leq M \leq 250000
- 0 \leq A_i < L=10^8
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \cdots A_M
Output
Output N lines. The i-th line should contain the answer for k=i.
Sample Input 1
2 1 50000000
Sample Output 1
499122177 686292993
- k=1: The probability of satisfying the condition is 1/2.
- k=2: The probability of satisfying the condition is 5/16.
Sample Input 2
3 5 78682095 25048034 71067122 94666780 1927105
Sample Output 2
741897823 406774904 435399949
Sample Input 3
10 7 40490214 25131781 2271243 52064315 34467030 27419560 56103210
Sample Output 3
457696464 497746652 679391958 742383895 245278311 709723420 729551291 1911348 414224424 650563524