D. Chip Move（DP，优化时间和空间）

题意
在一维坐标中，从 0 位置开始跳。
第 1 次移动可以跳 k 的倍数距离，第 2 次移动可以跳 k+1 的倍数距离，…，第 m 次跳可以跳 k+m-1 的倍数距离。
问，跳到 1~n 位置的方案数分别为多少？

$1\le k\le n\le 2\cdot 10^5,ans\mathrm{mod}998244353$

思路
朴素做法：
定义两维状态 f[i, j] 表示，到 i 位置时已经跳了 j 步的方案数。
当 k 最小为 1 时，每次跳只跳距离的一倍，n 最大为 2e5，$m^2+m\le 2\ast n$，所以最多跳 640 次。
遍历所有位置 i，遍历跳的次数 j，遍历上一次跳的倍数 b，所以转移方程为：
f[i][j] += f[i - b*(k+j-1)][j-1];
时间复杂度 $O(n^2\ast 640)$，空间复杂度 $O(n\ast 640)$。 时间复杂度和空间复杂度都超限。

cin >> n >> k;
	
f[0][0] = 1;
for(int i=1;i<=n;i++)
{
	int sum = 0;
	for(int j=1; j*(j+1) <= 2*n; j++)
	{
		for(int b=1; i - b*(k+j-1) >= 0; b++)
			f[i][j] += f[i - b*(k+j-1)][j-1];
	}
	cout << sum << " ";
}
1
2
3
4
5
6
7
8
9
10
11
12
13

需要想办法优化。
能不能像优化完全背包那样，把枚举倍数的这一重循环优化掉？
优化后的转移方程是这样的：
f[i][j] = f[i - (k+j-1)][j] + f[i - (k+j-1)][j-1];
对于走到当前 i 位置跳了 j 步，可以由 走到上一次跳的位置 i-k+j-1 跳了 j 步的方案数 加上 走到上一位置跳了 j-1 步的方案数。
走到上一位置跳了 j 步，再到当前位置跳了 j 步，就相当于从一开始的位置跳了 i-k+j-1 的倍数步了，这个倍数至少为 2。
再加上倍数为 1 的方案数 f[i-(k+j-1)][j-1]，走到上个位置跳了 j-1 步，再跳 1 倍的距离到当前位置。

优化掉一维后的代码：

cin >> n >> k;

f[0][0] = 1;
for(int i=1;i<=n;i++)
{
	int sum = 0;
	for(int j=1; j*(j+1) <= 2*n; j++)
	{
		if(i >= k+j-1)
		{
			f[i][j] = f[i - (k+j-1)][j] + f[i - (k+j-1)][j-1];
			sum += f[i][j];
		}
	}
	cout << sum << " ";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度 O(n*640)，但是还需要优化空间。

观察状态转移方程 f[i][j] = f[i - (k+j-1)][j] + f[i - (k+j-1)][j-1] 发现，当前更新 f[i, j] 只用到了 f[j] 和 f[j-1]，只用到了当前层和上一层。
如果只用到了上一层的话可以用滚动数组优化，现在也用到了当前层，所以可以再开一个数组交替更新。

当前步数用到了当前层和上一层，为了方便数组交替，将枚举位置和枚举步数的两重循环互换，先枚举步数再枚举位置。

t[0] = 1;
for(int j=1; j*(j+1) <= 2*n; j++) //交换遍历顺序
{
	for(int i=1;i<=n;i++) //更新状态
	{
		if(i >= k+j-1) f[i] = (f[i - (k+j-1)] + t[i - (k+j-1)]) % mod;
	}
	for(int i=0;i<=n;i++) //交替数组，数组重置，注意从0开始
	{
		ans[i] = (ans[i] + f[i]) % mod, t[i] = f[i], f[i] = 0; 
	}
}

for(int i=1;i<=n;i++) cout << ans[i] << " ";
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Code

//https://codeforces.com/contest/1716/problem/D
#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 998244353;
int T, n, m;
int a[N];
int f[N], t[N];
int ans[N];

signed main(){
	Ios;
	int k; cin >> n >> k;
	
	t[0] = 1;
	for(int j=1; j*(j+1) <= 2*n; j++)
	{
		for(int i=1;i<=n;i++)
		{
			if(i >= k+j-1) f[i] = (f[i - (k+j-1)] + t[i - (k+j-1)]) % mod;
		}
		for(int i=0;i<=n;i++) ans[i] = (ans[i] + f[i]) % mod, t[i] = f[i], f[i] = 0;
	}
	
	for(int i=1;i<=n;i++) cout << ans[i] << " ";

	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

优化确实强，要多积累这样的模型。