Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 100 点
うさぎたちがいろいろな種類のサイコロを使うことはよく知られていますが,サイは本当にたくさんの種類を持っているようです.
問題文
正の整数 N, A が与えられる.
m を正の整数とする.サイは 1 から m までの番号のついた m 個の特殊なサイコロを持っている.これからサイは,それぞれのサイコロを A 回ずつ振る.サイコロ i (1 \le i \le m) を 1 回振るたびに,\frac{1}{i^2} の確率であたりが出る.これらの試行の結果はすべて独立な事象である.
合計でちょうど N 回あたりが出る確率はいくつだろうか? この値は m に依存するが,m が限りなく大きくなるときのこの確率の極限を求めよ.
この極限の値を p とおくと,有理数 c_0, \ldots, c_{N-1} であって p = \sum_{j=0}^{N-1} c_j \pi^j となるものが一意に存在することが証明できる (\pi は円周率).この c_0, \ldots, c_{N-1} を \operatorname{mod} 998244353 で出力せよ.
有理数を \operatorname{mod} 998244353 で出力する際は,それを既約分数 \frac{x}{y} で表したとき,x - y z が 998244353 で割り切れるような 0 以上 998244353 未満の整数 z を出力せよ.この問題の制約によって,出力すべき値は一意に定まることが証明できる.
制約
- 1 \le A \le N \le 250\,000.
部分点
- N \le 100 かつ A = 1 を満たすデータセットに正解した場合は,10 点が与えられる.
- A = 1 を満たすデータセットに正解した場合は,上記とは別に 10 点が与えられる.
- 追加制約のないデータセットに正解した場合は,上記とは別に 80 点が与えられる.
入力
入力は以下の形式で標準入力から与えられる.
N A
出力
c_0, \ldots, c_{N-1} を,この順に空白区切りで,\operatorname{mod} 998244353 で出力せよ.
入力例 1
1 1
出力例 1
499122177
p = \frac{1}{2} である.
入力例 2
2 1
出力例 2
623902721 0
p = \frac{3}{8} である.
入力例 3
3 1
出力例 3
686292993 0 353544875
p = \frac{5}{16} - \frac{1}{48} \pi^2 である.
入力例 4
3 2
出力例 4
623902721 0 0
p = \frac{3}{8} である.
入力例 5
10 5
出力例 5
748591874 0 809083222 0 440705764 0 0 0 0 0