Chip Move
Contest: Educational Codeforces Round 133 (Rated for Div. 2)
Difficulty rating: 2000
Tags: brute force, dp, math

There is a chip on the coordinate line. Initially, the chip is located at the point $$$0$$$. You can perform any number of moves; each move increases the coordinate of the chip by some positive integer (which is called the length of the move). The length of the first move you make should be divisible by $$$k$$$, the length of the second move — by $$$k+1$$$, the third — by $$$k+2$$$, and so on.

For example, if $$$k=2$$$, then the sequence of moves may look like this: $$$0 \rightarrow 4 \rightarrow 7 \rightarrow 19 \rightarrow 44$$$, because $$$4 - 0 = 4$$$ is divisible by $$$2 = k$$$, $$$7 - 4 = 3$$$ is divisible by $$$3 = k + 1$$$, $$$19 - 7 = 12$$$ is divisible by $$$4 = k + 2$$$, $$$44 - 19 = 25$$$ is divisible by $$$5 = k + 3$$$.

You are given two positive integers $$$n$$$ and $$$k$$$. Your task is to count the number of ways to reach the point $$$x$$$, starting from $$$0$$$, for every $$$x \in [1, n]$$$. The number of ways can be very large, so print it modulo $$$998244353$$$. Two ways are considered different if they differ as sets of visited positions.

Input format:
The first (and only) line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).

Output format:
Print $$$n$$$ integers — the number of ways to reach the point $$$x$$$, starting from $$$0$$$, for every $$$x \in [1, n]$$$, taken modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let's look at the first example:

Ways to reach the point $$$1$$$: $$$[0, 1]$$$;

Ways to reach the point $$$2$$$: $$$[0, 2]$$$;

Ways to reach the point $$$3$$$: $$$[0, 1, 3]$$$, $$$[0, 3]$$$;

Ways to reach the point $$$4$$$: $$$[0, 2, 4]$$$, $$$[0, 4]$$$;

Ways to reach the point $$$5$$$: $$$[0, 1, 5]$$$, $$$[0, 3, 5]$$$, $$$[0, 5]$$$;

Ways to reach the point $$$6$$$: $$$[0, 1, 3, 6]$$$, $$$[0, 2, 6]$$$, $$$[0, 4, 6]$$$, $$$[0, 6]$$$;

Ways to reach the point $$$7$$$: $$$[0, 2, 4, 7]$$$, $$$[0, 1, 7]$$$, $$$[0, 3, 7]$$$, $$$[0, 5, 7]$$$, $$$[0, 7]$$$;

Ways to reach the point $$$8$$$: $$$[0, 3, 5, 8]$$$, $$$[0, 1, 5, 8]$$$, $$$[0, 2, 8]$$$, $$$[0, 4, 8]$$$, $$$[0, 6, 8]$$$, $$$[0, 8]$$$.

Example input:
8 1

Example output:
1 1 2 2 3 4 5 6

Example input:
10 2

Example output:
0 1 0 1 1 1 1 2 2 2

Editorial:
Let's calculate dynamic programming $$$dp_{s, i}$$$ — the number of ways to achieve $$$i$$$ in $$$s$$$ moves. From the state $$$(s, i)$$$, you can make a transition to the states $$$(s+1, j)$$$, where $$$i < j$$$ and $$$j - i$$$ is divisible by $$$k + s$$$.
Let's try to estimate the maximum number of moves, because it seems that there can't be very many of them. For $$$m$$$ moves, the minimum distance by which a chip can be moved is $$$k+ (k + 1) + \dots + (k + m - 1)$$$ or $$$\frac{(k + k + m - 1) \cdot m}{2}$$$. From here one can see that the maximum number of transitions does not exceed $$$\sqrt{2n}$$$ (maximum at $$$k=1$$$). So it remains to make transitions in dynamic programming faster than $$$O(n)$$$ from a single state for a fast enough solution. Let's use the fact that $$$j \equiv i \pmod{k+s}$$$. Let's iterate over the value of $$$j$$$ and maintain the sum of dynamic programming values with smaller indices for each remainder modulo $$$k + s$$$ in a separate array.
The final complexity of such a solution is $$$O(n\sqrt{n})$$$.
It remains to solve the memory problem, because with the existing limits, it is impossible to save the entire $$$dp$$$ matrix of size $$$n^{\frac{3}{2}}$$$. However, this is easy to solve if you notice that only the previous layer is used for transitions in dp, i.e. it is enough to store $$$dp_s$$$ to calculate $$$dp_{s+1}$$$.