自动搬运

查看原文

来自洛谷，原作者为

	zjpwdyf 不场切绿不改个签 || 复健 OI 中

搬运于2025-08-24 22:57:15，当前版本为作者最后更新于2024-05-02 14:55:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

0. 前言

作为一道计数/优化枚举的题目，本题比 [NOIP2022] 种花 难不少，思维难度较大。

本题主要考察的知识点：前缀和、容斥、枚举。

1. 大致思路

（注：为了方便计算，接下来先抛去题目中 $i<j<k$ 的条件，最后输出时除以 $3!$ 即可。）

首先不考虑 “$3$ 个区间互不相同” 的条件（即区间可以重复），设方案数为 $A$。

接着考虑 $a$ 种总方案中，有多少种是不合法的（存在重复区间）。

第一类：三个区间均相同，设情况数为 $B$。

第二类：两个区间相同，第三个区间不同，设情况数为 $C$。

则最终答案为 $(A-B-C)/3!$。

2. 具体实现

先对数列 $a$ 做前缀和 $s$，这样可以做到 $O(1)$ 查询区间和。

下文设第 $i,j,k$ 个区间的和分别为 $t_1, t_2, t_3$。

计算 B：

由于三个区间全部相同，所以 $t_1=t_2=t_3$ 且 $t_1+t_2+t_3=0$，易得 $t_1=t_2=t_3=0$。

所以只需要统计 $a$ 数列有多少个子区间的和为 $0$ 即可，容易实现：

for(int l = 1; l <= n; l++)
	for(int r = l; r <= n; r++)
		cnt[a[r] - a[l - 1] + mv]++;
B = cnt[mv];

（注：代码中的变量名等会在文章最后有解释，可先去看，再回来理解该段代码）。

---

计算 C：

不失一般性的，假设 $i=j$，则易得 $t_1=t_2$。

则由此可得 $t_3 = 0-t_1-t_2=-2\cdot t_1$。

所以只需要枚举和为 $t_1$（或 $t_2$）的区间，再用一个桶统计第三个区间的方案数即可，给出这部分的代码：

for(int l = 1; l <= n; l++){
	for(int r = l; r <= n; r++){
		int sum = a[r] - a[l - 1];
		if(sum == 0) C += cnt[mv] - 1;
		else C += cnt[-2 * sum + mv];
	}
}
C *= 3;

Q1：当 $t_1=t_2=0$ 时，为什么方案数是 $cnt_0-1$？

A1：因为其中有 “三段区间均相同” 的一种情况，而该情况在 $B$ 中已经统计过了，所以在这里要把它去掉。

Q2：那为什么 $t_1 \ne 0$ 时，就不存在这种重复计算的可能呢：

A2：此时 $t_3=-2 \cdot t_1\ne t_1$，区间和都不相等，区间编号就更不可能相等啦~

Q3：为什么最后 $C$ 要乘以 $3$？

A3：在开头我们假设了 $i=j$。但实际上还有 $i=k$ 和 $j=k$ 这两种情况。

---

计算 A：

本题中最难，也是最巧妙的地方（前方高能！）。

不难想到枚举前两个区间，再根据 $t_3=-(t_1+t_2)$ 算出第三个区间的和，用桶加以统计。但是这样做的时间复杂度为 $O(n^4)$，需要优化。

这里给出教练 noip_1 的一种奇妙思路：

memset(cnt, 0, sizeof cnt);
for(int i = 1; i <= n; i++){
	for(int j = 1; j <= n; j++)
		for(int k = j; k <= n; k++)
			cnt[a[k] - a[j - 1] - a[i - 1] + mv]++;
	for(int j = 1; j <= n; j++)
		for(int k = j; k <= n; k++)
			A += cnt[-(a[k] - a[j - 1] + a[i]) + mv];
}

以下记三个区间分别为 $[l_1, r_1], [l_2, r_2], [l_3, r_3]$。

回到题目本身：这三个区间要满足 $t_1+t_2+t_3=0$。把等式稍微变形一下：

$$t_1+t_2+t_3=0$$ $$\downarrow$$ $$(s_{r_1} - s_{l_1-1})+(s_{r_2}-s_{l_2-1})+(s_{r_3} - s_{l_3-1})=0 $$$$\downarrow$$ $$-(s_{r_1}-s_{l_1-1}+s_{r_2})=s_{r_3}-s_{l_3-1}-s_{l_2-1} $$

现在懂了吧！上面的代码所做的工作就是：将等式右边的 $s_{r_3}-s_{l_3-1}-s_{l_2-1}$ 存入桶中，然后枚举等式左边的 $l_1,r_1,r_2$，根据等式进行匹配计数。时间复杂度能做到 $O(n^3)$。

回顾一下暴力做法：将 $t_1+t_2$ 存入桶的时间复杂度为 $O(n^4)$，枚举 $t_3$ 的时间复杂度为 $O(n^2)$。由于没有平衡好两者的关系，所以时间复杂度较高。

3. 代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 505, V = 4e7 + 5, mv = 2e7;
int n, a[N], cnt[V];
ll A, B, C, ans;
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i], a[i] += a[i - 1];
	
	for(int l = 1; l <= n; l++)
		for(int r = l; r <= n; r++)
			cnt[a[r] - a[l - 1] + mv]++;
	B = cnt[mv];
	for(int l = 1; l <= n; l++){
		for(int r = l; r <= n; r++){
			int sum = a[r] - a[l - 1];
			if(sum == 0) C += cnt[mv] - 1;
			else C += cnt[-2 * sum + mv];
		}
	}
	C *= 3;
	memset(cnt, 0, sizeof cnt);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++)
			for(int k = j; k <= n; k++)
				cnt[a[k] - a[j - 1] - a[i - 1] + mv]++;
		for(int j = 1; j <= n; j++)
			for(int k = j; k <= n; k++)
				A += cnt[-(a[k] - a[j - 1] + a[i]) + mv];
	}
	ans = (A - B - C) / 6;
	cout << ans;
	return 0;
}

注：

• cnt 为计数数组。由于可能出现负数，所以在存入桶前，要加上一个大数（即代码中的 mv）。

• 代码中为了方便，直接将 a 数组作为了前缀和。

• 记得开 long long！

4. 后记

这里 是我整理的此类题型的题单，持续更新中，大家有好题也可以在评论区推荐给我。

如果您觉得这篇题解对您有帮助的话，请点个赞，感谢 qwq。