CF1575C 题解

First Post:

Last Update:

赛时想着用卷积处理散块，但不知道如何避免重复统计的问题，赛后看到题解做法大受震撼，故记录一下。有时一个观察能帮你省掉很多东西。

我们先考虑固定右端点 ，计算所有左端点的答案。

一个关键但显然的观察是， 和 的答案是相同的，这意味着我们只需计算 的答案，最后把答案乘 即可。

设 ，即 序列的前缀和。如果 不大的话，我们大可以预处理出 表示满足 的 的个数。然后扫描 ，每次先让 减 ，再提取出 作为 的答案，再将 加 。容易发现，上述过程正确地统计了所有 和 的子段，可以手算验证。

我们发现，上述做法的瓶颈在于，如何快速地预处理 。

如果 ，处理起来比较容易。

否则，我们希望对于每个 ，我们能把 的贡献一起加入到 中，即需要对于 ，令 自增 。事实上，考虑一张图，对于每个点 ，连边 ，最后会形成一个长度为 的环（因为 是质数），那么我们的操作相当于对环上连续的一段进行区间加。维护差分数组即可做到 。

事实上，对于 不是质数的情况，上述做法也是可行的，只不过可能会形成若干个环，我们要对每个环分开考虑。

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
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,P = 1e9 + 7;
int n,m,k,sum[N];
int cnt[N];
int Id[N]; // 环上各点的编号
int dif[N]; // 差分数组
int main()
{
	cin >> n >> m >> k;
	for(int i = 1;i <= n;i++)
		cin >> sum[i],(sum[i] += sum[i - 1]) %= k;
	int sall = 1ll * sum[n] * m % k;
	int sn = sum[n];
	if(!sn)
	{
		int res = 0;
		for(int i = 1;i <= n;i++) (res += cnt[sum[i]]++) %= P;
		int ans = (1ll * ((res << 1ll) + n) % P * m % P * m % P - (1ll * n * m % P) + P + 1) % P;
		cout << ans << endl;
		return 0;
	}
	Id[0] = 1;
	for(int i = sn,j = 2;i;i = (i + sn) % k,++j)
		Id[i] = j;
	for(int i = 1;i <= n;i++)
	{
		int vl = sum[i],vr = (sum[i] + 1ll * m * sn % k) % k; // [vl,vr)
		vl = Id[vl];vr = Id[vr];
		(dif[1] += m / k) %= P;
		if(vl <= vr) dif[vl]++,dif[vr]--;
		else dif[vl]++,dif[1]++,dif[vr]--;
	}
	for(int i = 1;i <= k;i++)
		(dif[i] += dif[i - 1]) %= P;
	// for(int i = 1;i <= n;i++) printf("%d ",sum[i]);printf("\n");
	// for(int i = 0;i < k;i++) printf("%d ",Id[i]);printf("\n");
	// for(int i = 1;i <= k;i++) if(dif[i]) printf("%d,%d ",i,dif[i]);printf("\n");
	int ans = 0;
	//(dif[Id[sall]] += 1) %= P;
	for(int r = 1;r <= n;r++)
	{	
		(dif[Id[sum[r]]] += P - 1) %= P;
		(ans += dif[Id[(sum[r] + sall) % k]]) %= P;
		(dif[Id[(sum[r] + sall) % k]] += 1) %= P;
	}
	ans = 1ll * ans * m % P;
	if(!sall) ans = (ans + 1) % P;
	cout << ans << endl;
	return 0;
}
≡