cf Educational Codeforces Round 133 D. Chip Move

原题：

D. Chip Move
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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→4→7→19→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∈[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
The first (and only) line of the input contains two integers n and k (1≤k≤n≤2⋅10^5).

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

Examples
input
8 1
output
1 1 2 2 3 4 5 6
input
10 2
output
0 1 0 1 1 1 1 2 2 2
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].

中文：

给你一个一维数轴，开始时候你0点。每次可以向前移动，每次移动的大小必须是移动次数加上+ k的整数倍。比如k等于2，那么第一次移动可以是2，4，6…;第二次移动的距离需要时k + 1的整数倍，比如3, 6, 9以此类推。
最后问你，要走到n，有多少种走法？

代码:

#include 
using namespace std;
 
const int mod = 998244353;
const int maxn = 2e5 + 2;

int dp[maxn];
int pre_dp[maxn];
int ans[maxn];
int main() {
    int n, k;
    ios::sync_with_stdio(false);
    while (cin >> n >> k) {
        memset(dp, 0, sizeof(dp));
        memset(pre_dp, 0, sizeof(pre_dp));
        memset(ans, 0, sizeof(ans));
        pre_dp[0] = 1;
        int sum;
        for (int j = 1; j * (j + 1) <= 2 * n; j++) {
            sum = 0;
            for (int i = 1; i <= n; i++) {
                if (i >= k + j - 1) {
                    dp[i] = (dp[i - (k + j - 1)] % mod + pre_dp[i - (k + j - 1)] % mod) % mod;
                }
                ans[i] = (ans[i] + dp[i]) % mod;
            }
            for (int i = 0; i <= n; i++) {
                pre_dp[i] = dp[i];
                dp[i] = 0;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (i != n) {
                cout << ans[i] << " ";
            } else {
                cout << ans[i] << endl;
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

解答:

一个组合计数问题。
设$dp[i][j]$表示走到i走了j步时的走法。
那么状态转移方程可以表示成
$dp[i][j]=dp[i-(k+j-1)][j]+dp[i-(k+j-1)][j-1]$

等号左侧第一个状态表示，走了j步可以移动到$i-(k+j-1)$的位置，那么走j步也一定可以移动i的位置，因为可以移动两倍的$k+j-1$的距离，从$dp[i-2\ast (k+j-1)][j-1]$转移过来，两倍的$k+j-1$因为也是k + j的倍数。

等号左侧第二个状态，表示从了j - 1步，此时再走一步，步长为$k+j-1$即可。

int ans[maxn][650];
 
int main() {
    int n, k;
    ios::sync_with_stdio(false);
    while (cin >> n >> k) {
        memset(ans, 0, sizeof(ans));
        ans[0][0] = 1;
        int sum;
        for (int i = 1; i <= n; i++) {
            sum = 0;
            for (int j = 1; j * (j + 1) <= 2 * n; j++) {
                if (i >= k + j - 1) {
                    ans[i][j] = (ans[i - (k + j - 1)][j] % mod + ans[i - (k + j - 1)][j - 1] % mod) % mod;
                    sum =  (sum + ans[i][j]) % mod;
                }
            }
            cout << sum << " ";
        }
        cout << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

上面的状态可以优化，用滚动数组的方式来节省空间。否则mle