题解 CF466C 【Number of Ways】

我们有一个数组 a。我们要将其分成三份，使得这三份的和相等。我们用 kk 代表每一份的和。

很明显，$O(n^2)$的枚举一定会超时。这里我们考虑分别枚举之后统计答案。

考虑记录 bool 数组$b1_i$和$b2_i$。

当$\sum_{k=1}^ia_k=kk$时，令$b1_i=1$，否则，$b1_i=0$。

当$\sum_{k=i}^na_k=kk$时，令$b2_i=1$，否则，$b2_i=0$。

这样的话，我们就可以统计答案了！对于每个$b2_i=1$，可以与其对应的分割方案数量即为在 i-1 左侧的$b1_i=1$的数量。前缀和维护即可。

#include<iostream>
#define int long long
using namespace std;
int a[500005];
bool b1[500005],b2[500005];
int c[500005];
signed main(){
	int n,sum=0,kk;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
	if(sum%3!=0){
		cout<<0;
		return 0;
	}//特判出局
	kk=sum/3;
	sum=0;
	for(int i=1;i<=n;i++){
		sum+=a[i];
		if(sum==kk)b1[i]=1;
	}//统计b1数组
	sum=0;
	for(int i=n;i>0;i--){
		sum+=a[i];
		if(sum==kk)b2[i]=1;
	}//统计b2数组
	for(int i=1;i<=n;i++){
		c[i]=c[i-1]+b1[i];
	}//前缀和
	int ans=0;
	for(int i=3;i<=n;i++){
		ans+=b2[i]*c[i-2];
	}//统计答案
	cout<<ans;
	return 0;
}