開門見山的說,我們摯愛的曾老師今天遇上了一個生成函數題。
不過他懶得下凡演示他精湛的解微分方程技巧, 這題對他的兩個隊友(神仙數學講師和威力枕頭)來說又太簡單,於是他就把這題交給了你。
給定正整數 $K$,定義生成函數 $F_0(x), F_1(x), F_2(x), \cdots $ 如下:
$ F_0(x) = 1 $ 並且 $$ F_{i+1} = F'_{i}(x) + \frac{1-x^ K}{1-x}F_i(x)$$ 對所有的非負整數 $i$ , 其中 $F'_{i}(x)$ 是 $F_i(x)$ 的微分。
請告訴曾老師 $F_N(0)$ 的值,因為這個數字很大,輸出除以 $998244353$ 的餘數即可。
你現在幫過我,我承諾讓你當神仙隊伍 NoName 的下一任隊員。
輸入兩個正整數 $N, K$。
輸出一行整數,代表 $F_N(0) \text{ mod } 998244353$ 的值。
範例一中 $F_N(x) = x^ 4+2x^ 3+3x^ 2+4x+2$
範例二中 $F_N(x) = x^ 4+4x^ 3+12x^ 2+16x+10$
IOICamp 2022 Day5 pC
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~8 | $1 \leq N, K \leq 2 \times 10^ 5$ | 50 |
3 | 0~11 | 無額外限制 | 50 |