h998: 整數分拆問題
Tags : NTT 五邊形數 生成函數
Accepted rate : 1人/4人 ( 25% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-07-12 11:18

Content

一個正整數可以分拆成許多正整數加在一起,比如說 $3 = 2 + 1 = 1 + 1 + 1, 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1$,另 $a_k$ 為將正整數 $k$ 分拆的方法數,比如說 $4$ 就有 $5$ 種分拆方法,然後數字的順序不同視為一樣的方法 (例如 $1 + 2$ 與 $2 + 1$ 視為相同)。

請你輸出 $a_1 \sim a_n\ (\bmod 998244353)$。

Input

輸入一個正整數 $n$。

  • $1 \leq n \leq 2\times 10^5$
Output

輸出一行,共 $n$ 個數字,代表 $a_1\sim a_n\ (\bmod 998244353)$。

Sample Input #1
10
Sample Output #1
1 2 3 5 7 11 15 22 30 42
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 3.0s , <1K
公開 測資點#1 (20%): 3.0s , <1K
公開 測資點#2 (70%): 3.0s , <1K
Hint :

$10\%:n \leq 20$

$20\%:n \leq 5000$

$70\%:無特別限制$

Tags:
NTT 五邊形數 生成函數
出處:
Caido [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」