/ 
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
全ての目が出る確率が等しい N 面サイコロがあります。このサイコロを、全ての目が出るまで振り続けます。
1 \le i \le M を満たす整数 i に対して、サイコロを振る回数の i 乗の期待値 \bmod\ 998244353 を求めてください。
期待値 \bmod\ 998244353 の定義
求める期待値は必ず有理数になることが証明できます。また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \neq 0 \pmod{998244353} となることも証明できます。よって、R \times Q = P \pmod{998244353},0 \le R < 998244353 を満たす整数 R が一意に定まります。この R を答えてください。
制約
- 1 \le N,M \le 2 \times 10^5
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
M 行出力せよ。
i 行目には、サイコロを振る回数の i 乗の期待値 \bmod\ 998244353 を出力せよ。
入力例 1
3 3
出力例 1
499122182 37 748683574
i=1 の場合、求めるべき期待値は全ての目が出るまでの操作回数です。その値は \frac{11}{2} です。
入力例 2
7 8
出力例 2
449209977 705980975 631316005 119321168 62397541 596241562 584585746 378338599
入力例 3
2023 7
出力例 3
442614988 884066164 757979000 548628857 593993207 780067557 524115712
Score : 900 points
Problem Statement
We have an N-sided die where all sides have the same probability to show up. Let us repeat rolling this die until every side has shown up.
For integers i such that 1 \le i \le M, find the expected value, modulo 998244353, of the i-th power of the number of times we roll the die.
Definition of expected value modulo 998244353
It can be proved that the sought expected values are always rational numbers. Additionally, under the constraints of this problem, when such a value is represented as an irreducible fraction \frac{P}{Q}, it can be proved that Q \neq 0 \pmod{998244353}. Thus, there is a unique integer R such that R \times Q = P \pmod{998244353} and 0 \le R < 998244353. Print this R.
Constraints
- 1 \le N,M \le 2 \times 10^5
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print M lines.
The i-th line should contain the expected value, modulo 998244353, of the i-th power of the number of times we roll the die.
Sample Input 1
3 3
Sample Output 1
499122182 37 748683574
For i=1, you should find the expected value of the number of times we roll the die, which is \frac{11}{2}.
Sample Input 2
7 8
Sample Output 2
449209977 705980975 631316005 119321168 62397541 596241562 584585746 378338599
Sample Input 3
2023 7
Sample Output 3
442614988 884066164 757979000 548628857 593993207 780067557 524115712