一句话题意：从长度为 $n$ 的数组 $a$ 中取出三个不相同的区间，问有多少种不同的取法使区间和之和为零（无序）。
根据题意，$b_x+b_y+b_z=0$，假设 $b_x$ 对应的区间为 $a_{i’+1} \cdots a_i$，$b_y$ 对应 $a_{j’+1} \cdots a_j$，$b_z$ 对应 $a_{k’+1} \cdots a_k$。我们可以使用前缀和优化这个式子：$s_i-s_{i’}+s_j-s_{j’}+s_k-s_{k’}=0$，其中 $s_x=\sum_{i=1}^x a_i$。
但是我们发现枚举式子右侧的六个变量时间复杂度为 $\mathcal{O}(n^6)$，无法接受，那么我们可以把三项移到右侧，将式子变为：$s_i-s_{i’}+s_j=s_{j’}-s_k+s_{k’}$。这样对两边的枚举时间复杂度均降为 $\mathcal{O}(n^3)$，可以分开枚举（注意实现时要保证 $j’<j$，对此我们可以在计算 $j$ 前更新一遍 $j’$，这样可以在不破坏效率的情况下维护 $j’<j$，具体可见代码）
但我们发现以上算法有两个问题：
无法保证 $x<y<z$，换句话说就是会重复计算。
可能会统计到不合法的答案（如两个相同的区间）
我们重新观察式子，发现：
当 $x,y,z$ 互不相等时，共会计算 $3!=6$ 次。
当 $x,y,z$ 中有且仅有两数相等时（不合法），会计算 $2$ 次。
当 $x=y=z$（不合法）时，会计算 $1$ 次。
于是我们可以再 $\mathcal{O}(n^2)$ 枚举相等的数，减掉不合法的情况；最终答案即为剩下的合法计数的 $\frac16$。如果对实现或思路有问题，可参考代码（作者太弱了降不太清楚 QAQ）。
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505,Mx=3e7+5;
int n,a[N],sum[N],f[Mx],base;
map<int,int> g;
inline int id(int x) {return max(x-base+1,0);}
int main() {
scanf("%d",&n);
int tmp=0;
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
base=max(base,sum[i]-tmp),tmp=min(tmp,sum[i]);
for(int i_=0;i_<i;i_++) g[sum[i]-sum[i_]]++;
}
base=tmp-base;
ll ans=0;
for(int j=1;j<=n;j++) {
int j_=j-1;
for(int k=1;k<=n;k++)
for(int k_=0;k_<k;k_++)
f[id(sum[j_]-sum[k]+sum[k_])]++;
for(int i=1;i<=n;i++)
for(int i_=0;i_<i;i_++)
ans+=(ll)f[id(sum[i]-sum[i_]+sum[j])];
}
for(int i=1;i<=n;i++)
for(int i_=0;i_<i;i_++) {
int s=sum[i]-sum[i_];
ans-=3LL*g[-2*s];
if(!s) ans+=2LL;
}
printf("%lld\n",ans/6LL);
return 0;
}
|