package main import . "fmt" func main() { var n, k int Scan(&n, &k) ans := solve(n, k) Println(ans) } func solve(n, k int) int { if k > n { return 1 } const MOD = 998244353 dp1 := 0 dp2 := make([]int, n+1) dp2[0] = 1 ans := 1 for i := k; i <= n; i++ { dp1 = (dp1+dp2[i-k])%MOD dp2[i] = dp1 ans = (ans+dp1)%MOD } return ans } func init() { for n := 1; n <= 300; n++ { for k := 1; k <= n; k++ { sa := solve(n, k) ha := hoge(n, k) if sa != ha { panic(Sprintf("n=%d,k=%d,sa=%d,ha=%d",n,k,sa,ha)) } } } } func hoge(n, k int) int { if k > n { return 1 } const MOD = 998244353 // reference: https ://cp-algorithms.com/data_structures/fenwick.html#3-range-update-and-range-query b1 := make([]int, n+3) b2 := make([]int, n+3) add := func(b []int, idx, x int) { for x < 0 { x += (-x+MOD-1)/MOD*MOD } for idx < len(b) { b[idx] = (b[idx]+x)%MOD idx += idx & -idx } } rangeAdd := func(l, r, x int) { add(b1, l, x) add(b1, r+1, -x) add(b2, l, x*(l-1)) add(b2, r+1, -x*r) } sum := func(b []int, idx int) int { total := 0 for idx > 0 { total = (total + b[idx])%MOD idx -= idx & -idx } return total } prefixSum := func(idx int) int { return (sum(b1, idx)*idx - sum(b2, idx))%MOD } rangeSum := func(l, r int) int { return (prefixSum(r) - prefixSum(l-1))%MOD } rangeAdd(1, 1, 1) for i := 1; i+k <= n+1; i++ { x := rangeSum(i, i) rangeAdd(i+k, n+1, x) } ans := rangeSum(1, n+1) for ans < 0 { ans += (-ans+MOD-1)/MOD*MOD } return ans }