ABC335F 题解

Register_int · 2024-01-06 22:51:38 · 个人记录

设 dp_i 为将棋子跳到第 i 格时的方案数。那么有：

然而这种形式不太好优化。尝试用 dp_j 去更新 dp_i：

当 a_j\le B 时，我们可以用 s_{x,y} 储存所有 \text{}\bmod x=y 的位置的 dp 值之和。计算 dp_i 时暴力枚举 x 加上 s_{x,i\bmod x} 即可。时间复杂度 O(B)。

当 a_j>B 时，dp_j 更新的位置不会超过 \dfrac nB 个，暴力更新。时间复杂度为 O(\dfrac nB)。

总复杂度 O(B+\dfrac nB)，B 取 \sqrt n 时得到最优复杂度 O(n\sqrt n)。答案为 \sum dp_i。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;
const int MAXM = 4.5e2;
const int mod = 998244353;

int n, m, a[MAXN]; ll dp[MAXN], sum[MAXM][MAXM], ans;

int main() {
    scanf("%d", &n), m = sqrt(n), dp[1] = 1;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        if (i > 1) for (int j = 1; j <= m; j++) dp[i] = (dp[i] + sum[j][i % j]) % mod;
        if (a[i] <= m) sum[a[i]][i % a[i]] = (sum[a[i]][i % a[i]] + dp[i]) % mod;
        else for (int j = i + a[i]; j <= n; j += a[i]) dp[j] = (dp[j] + dp[i]) % mod;
        ans = (ans + dp[i]) % mod;
    }
    printf("%lld", ans);
}