CF1603C Extreme Extension

CF1603C Extreme Extension

拿到一题有神秘操作的题目，先考虑把神秘操作搞清楚

对于一个子段，最末尾的数一定不能动，考虑从后往前贪心，当出现 \(a_i>a_{i+1}\) 时，需要将 \(a_i\) 拆分。要使当前操作最优，我们要让拆分完的第一个数尽可能大，手算一下就可以得出结论：一共需要拆分 \(\lceil \frac{a_i}{a_{i+1}}\rceil-1\) 次，第一个数的最大值为 \(\lfloor\frac{a_i}{\lceil \frac{a_i}{a_{i+1}}\rceil}\rfloor\)。

此时根据 \(a_i\) 只被 \(a_{i+1}\) 影响，可以考虑 dp，设 \(f_{i,v}\) 表示有多少以 \(a_i\) 为开头的子段，使得 \(a_i\) 拆分完之后最小值为 \(v\)。

考虑转移，朴素的做法，枚举所有 \(f_{i+1,x}\)，此时 \(c=\lceil \frac{a_i}{a_{i+1}}\rceil\)，\(p=\lfloor\frac{a_i}{c}\rfloor\)，转移到对应的 \(f_{i,p}\) 中，复杂度为 \(O(nV)\)，无法通过。

发现对于每一个 \(i+1\)，最多只能转移到 \(\sqrt{a_{i+1}}\) 个状态中，而对于每个 \(i\)，也只有 \(\sqrt{a_{i+1}}\) 个状态不为零，可以继续转移。这个结论可以用数论分块证明。

所以考虑优化 dp，首先滚动数组，空间复杂度为 \(O(n)\)。用两个 vector 维护，将 \(i+1\) 的所有不为零的状态用 vector 存起来，转移到对应的 \(f_{i,p}\) 里。再将 \(i\) 中不为零的状态用另一个 vector 存起来。

考虑按位计算答案，对于每个 \((i,v)\)，贡献为 \(i\times (c-1)\times f_{i,v}\)，乘法满足分配律，我们在转移的同时更新答案即可。

复杂度降到 \(O(n\sqrt V)\) 。

#include <bits/stdc++.h>

typedef long long i64;

const int mod = 998244353;

void Solve() {
	int n;
	std::cin >> n;

	std::vector<int> a(n + 1);

	int mx = 0;
	for(int i = 1; i <= n; i++) {
		std::cin >> a[i];
		mx = std::max(mx, a[i]);
	}

	std::vector<std::vector<int>> dp(2, std::vector<int> (mx + 1));
	std::vector<int> v[2];
	int op = 1;
	i64 ans = 0;
	for(int i = n; i >= 1; i--) {
		dp[op][a[i]] = 1;
		v[op].push_back(a[i]);
		int lst = a[i];
		for(auto x : v[op ^ 1]) {
			int cnt = (a[i] + x - 1) / x;
			int num = a[i] / cnt;
			ans = (ans + (i64)i * (cnt - 1) % mod * dp[op ^ 1][x]) % mod;
			dp[op][num] += dp[op ^ 1][x];
			if(num != lst) {
				v[op].push_back(num), lst = num;
			}
		}	
		for(auto x : v[op ^ 1]) {
			dp[op ^ 1][x] = 0;
		}
		v[op ^ 1].clear();
		op ^= 1;
	} 

	std::cout << ans << "\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
	
	int t;
	std::cin >> t;

	while(t--) Solve();

	return 0;
}