[ABC335F] Hop Sugoroku 【根号分治】

\(\mathtt {TAGS}\)：根号分治 DP

\(\mathtt {APPRAIS}\)：很优美的暴力 DP

First. 朴素 DP

这里做一个转化：求不同集合的数量相当与求走到所有点的不同方案数之和。

设 \(dp_i\) 表示走到 \(i\) 号的方案数。

显然， \(dp_i\) 可以去更新所有 \(dp_{i + a_i \times x}[i + a_i \times x \le n]\)。

即：

for (int i = 1; i <= n; i ++) {
	for (int j = i + a[i]; j <= n; j += a[i]) {
		dp[j] += dp[i], dp[j] -= (dp[j] >= mod) ? mod : 0;
	}
}

时间复杂度：\(\text{O}(n ^ 2)\)

Second. 优化

记 \(su_{i,x, r}\) 为所有小于 \(i\) 的数中模 \(x\) 余 \(r\) 的 \(dp\) 值之和。

对于 \(a_i\) 的大小不同，我们尝试去做不同的解决方案。

设阈值为 \(x\)，对于 \(i \le x\) 的部分：

此时枚举所有 \(p \le x\)，\(dp_i = \sum su_{p, i \bmod x}\)。这相当枚举所有与 \(i\) 模 \(p\) 同余的所有 \(j\) 的位置的 \(dp\) 值之和。

剩余部分已经由 \(a_i > x\) 的 \(i\) 更新过了。

更新时，对于 \(a_i \le x\)：

在 \(su_{a_i, i \bmod a_i}\) 上累加即可实现向后更新的转移。

对于 \(a_i > x\)：

此时直接暴力更新 \(dp_i + a_i \times j\) 最多更新 \(\frac{n}{x}\) 次。

所以总复杂度为 \(\text{O}(x + \frac{n}{x})\)。

当 \(x\) 取 \(\sqrt{n}\) 时得到最优。

傻缺代码

#include <bits/stdc++.h>
using namespace std;
// 根号分治
// 1: a <= sqrt(n)
// 记 sum[x][y] 表示 % x = y 的 i 的 dp[i] 之和。
// 2: a > sqrt(n)
// 暴力更新，次数不会超过 sqrt(n) 次
/*
for (int i = 1; i <= n; i ++) {
	for (int j = i + a[i]; j <= n; j += a[i]) {
		dp[j] = (dp[j] + dp[i]) % mod;
	}
}
*/
const int N = 2e5 + 10, M = 500 + 10;
const int mod = 998244353;
int n, b, a, ans;
int dp[N], su[M][M];

signed main() {
	ios::sync_with_stdio(0);
	cin >> n;
	b = sqrt(n);
	dp[1] = 1;
	for (int  i = 1; i <= n; i ++) {
		cin >> a;
		for (int j = 1; j <= b; j ++) dp[i] = (dp[i] + su[j][i % j]) % mod;
		if(a >= b) for (int j = i + a; j <= n; j += a) dp[j] = (dp[j] + dp[i]) % mod;
		else su[a][i % a] = (su[a][i % a] + dp[i]) % mod;
		(ans += dp[i]) %= mod;
	}
	cout << ans << endl;
	return 0;
}