Chip Move

发表于 分类于 ，

    初始时，你的位置在0，每次第i次移动时必须让你的位置增长t，t是k+i的倍数。

    现在求1到n的所有x，从0到x的不同路径有多少条。访问位置集不同则视为路径不同。

Chip Move

Created by LXC on Wed Aug 30 09:48:18 2023

https://codeforces.com/problemset/problem/1716/D

ranting: 2000

tag: brute force, dp, math

problem

初始时，你的位置在0，每次第i次移动时必须让你的位置增长t，t是k+i的倍数。

现在求1到n的所有x，从0到x的不同路径有多少条。访问位置集不同则视为路径不同。

solution

最少会移动多少次？假设最少移动m次到达x，那么$k + k+1 + k+2 + \cdots + k+m-1 = x$，显然m是$O(\sqrt x)$级别的

设$f_{i,j}$为上一次移动距离为j到达i的所有路径数。
$f$的总状态数为$O(n\sqrt n)$，我们每次转移的时间复杂度看样子得$O(1)$才能不超时。

状态转移，在已知$f_{?,j-1}$可以求得$f_{?,j}$

$f_{i,j}=f_{i-j, j-1}+f_{i-2j,j-1}+f_{i-3j, j-1} + \cdots + f_{i\bmod j, j-1}$，看样子会超时。

实际上我们可以对于前缀中模k同余的索引，用哈希表进行维护。一边遍历、一边更新、一边查询。做到$O(1)$时间复杂度转移。

总时间复杂度为状态数乘以每个状态转移时间，$O(n \sqrt n)$

注意空间复杂度会超出限制，$f_{?,j}$只依赖于$f_{?,j-1}$，可以利用滚动数组做到$O(n)$空间。

code

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
42
43
44
45
46
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int k, n;
    cin >> n >> k;
    vector<int> f(n + 1), ans(n + 1);
    f[0] = 1;
    for (int c = 0; c + k <= n; c += k++) {  // iterate sqrt n
        vector<int> s(k);
        for (int i = c; i <= n; i++) {
            int t = f[i];
            f[i] = s[i % k];
            s[i % k] += t;
            s[i % k] %= MOD;
            ans[i] += f[i];
            ans[i] %= MOD;
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}