G - Accumulation of Wealth 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 625 点

問題文

2 以上の整数 N と、0 以上 100 以下の整数 P が与えられます。以下、 p=P/100 とします。

数列 A があります。はじめ、A の長さは 1 で、唯一の要素は 1 です。

数列 A に対して、以下の操作を N-1 回繰り返します。

  • A に現れない最小の正整数を m とする。確率 p で操作 1、確率 1-p で操作 2 を行う：
    • 操作 1: A の末尾に m を追加する。
    • 操作 2: 1,2,\dots,m-1 が A に含まれる個数を c_1,c_2,\dots,c_{m-1} とする。1 以上 m-1 以下の整数 k を c_k に比例する確率で 1 つ選ぶ。すなわち、確率 c_k/\sum_{j=1}^{m-1} c_j で k を選ぶ。そして、A の末尾に k を追加する。

各 k=1,2,\dots,N について、N-1 回の操作後に A に含まれる k の個数の期待値を \mathrm{mod}\; 998244353 で求めてください。

期待値 \pmod{998244353} の定義

求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \neq 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。

制約

  • 2 \leq N \leq 10^5
  • 0 \leq P \leq 100
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N P

出力

N 行出力せよ。k\;(1\leq k \leq N) 行目には、操作後の A に含まれる k の個数の期待値を \mathrm{mod}\; 998244353 で出力せよ。

入力例 1

3 50

出力例 1

124780546
124780545
748683265

操作は以下のように進行します。

  • はじめ、 A=(1) です。
  • 1 回目の操作：確率 1/2 で A=(1,2)、確率 1/2 で A=(1,1) となります。
  • 2 回目の操作
    • A=(1,2) のとき、確率 1/2 で A=(1,2,3), 確率 1/4 で A=(1,2,1), 確率 1/4 で A=(1,2,2) となります。
    • A=(1,1) のとき、確率 1/2 で A=(1,1,2), 確率 1/2 で A=(1,1,1) となります。

最終的な A に含まれる 1,2,3 の個数の期待値はそれぞれ \frac{15}{8}, \frac{7}{8}, \frac{1}{4} です。

入力例 2

2 0

出力例 2

2
0

入力例 3

5 24

出力例 3

297734288
442981554
937492320
798158491
518366411

Score : 625 points

Problem Statement

You are given an integer N \geq 2 and an integer P between 0 and 100, inclusive. Let p=P/100.

There is a sequence A. Initially, the length of A is 1, and its only element is 1.

The following operation is repeated N-1 times on sequence A:

  • Let m be the smallest positive integer that does not appear in A. With probability p, perform operation 1; with probability 1-p, perform operation 2:
    • Operation 1: Append m to the end of A.
    • Operation 2: Let c_1,c_2,\dots,c_{m-1} be the number of times 1,2,\dots,m-1 appear in A, respectively. Choose an integer k between 1 and m-1, inclusive, with probability proportional to c_k. That is, choose k with probability c_k/\sum_{j=1}^{m-1} c_j. Then, append k to the end of A.

For each k=1,2,\dots,N, find the expected number of occurrences of k in A after N-1 operations, modulo 998244353.

Definition of expected value modulo 998244353

It can be proved that the expected value you seek is always a rational number. Also, under the constraints of this problem, it can be proved that when this value is expressed as an irreducible fraction \frac{P}{Q}, we have Q \neq 0 \pmod{998244353}. Therefore, there is a unique integer R such that R \times Q \equiv P \pmod{998244353} and 0 \leq R \lt 998244353. Output this R.

Constraints

  • 2 \leq N \leq 10^5
  • 0 \leq P \leq 100
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N P

Output

Output N lines. The k-th (1\leq k \leq N) line should contain the expected number of occurrences of k in A after the operations, modulo 998244353.

Sample Input 1

3 50

Sample Output 1

124780546
124780545
748683265

The operations proceed as follows:

  • Initially, A=(1).
  • 1st operation: It becomes A=(1,2) with probability 1/2, and A=(1,1) with probability 1/2.
  • 2nd operation:
    • If A=(1,2), it becomes A=(1,2,3) with probability 1/2, A=(1,2,1) with probability 1/4, and A=(1,2,2) with probability 1/4.
    • If A=(1,1), it becomes A=(1,1,2) with probability 1/2, and A=(1,1,1) with probability 1/2.

The expected numbers of occurrences of 1,2,3 in the final A are \frac{15}{8}, \frac{7}{8}, \frac{1}{4}, respectively.

Sample Input 2

2 0

Sample Output 2

2
0

Sample Input 3

5 24

Sample Output 3

297734288
442981554
937492320
798158491
518366411