codeforces：D. Chip Move【dp + 逆向思维考虑】

分析

每个状态显然跟之前的有关系，所以用dp
我们可以知道如果每次取1倍，我们可以得到最多的步数，我们计算出最多的步数为tmp - 1
所以我们的步数可以是k到tmp - 1
顺着来的话，只能模拟超时
但如果倒着来，dp:只有tmp - 1, tmp - 2, tmp - t能去到的位置的次数
new_dp: 包括tmp - 1, tmp - 2, tmp - t, tmp - t - 1 >= k去到的位置的次数
那么我们在知道dp的前提下
new_dp[j] = new_dp[j - i] + dp[j - i]
因为当前的j，可以是当前新的tmp - t - 1得到的，也可以是旧的dp[j - i]时得到的
比较难想

ac code

import sys
from collections import defaultdict
input = sys.stdin.readline

MOD = 998244353

n, k = list(map(int, input().split()))

tmp = k
acc = k

while acc <= n:
    tmp += 1
    acc += tmp

dp = [0] * (n + 1)
#dp[tmp] = 1
#print(tmp, dp)

# 最大tmp - 1，从k开始

for i in range(tmp - 1, k - 1, -1):

    # dp:只有tmp - 1, tmp - 2, tmp - t
    # new_dp: 包括tmp - 1, tmp - 2, tmp - t, tmp - t - 1 >= k

    new_dp = [0] * (n + 1)
    new_dp[i] = 1
    for j in range(i + 1, n + 1):
        new_dp[j] = new_dp[j - i] + dp[j - i]
        new_dp[j] %= MOD
    dp = new_dp
    #print(i, dp)

print(*dp[1:])
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

复杂度o^1.5

总结

正难则反
考虑最大步数
然后倒序dp
当前的newdp[j]，由于我们必须把小的考虑进来，也就是i必须要参与
所以new_dp[j] = new_dp[j - i] + dp[j - i]