C. Number of Ways

图片说明
Examples
input

5
1 2 3 0 3

output

2

input

4
0 1 -1 0

output

1

input

2
4 1

output

0

题意

给一个数组，让其分成三个连续的部分，3个部分的和相等，问有多少种分配方法？

解法

要平均分配成3个部分，肯定总和是3的倍数，然后记录一下其前缀和上x，2x，3x的个数。从前往后遍历，如果遇到了2x，就看前面有多少个x，加到结果中即可。

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}


//--------------------------------------------
int N;
ll a[maxn];
ll solve(){
    for(int i = 1;i<=N;i++) a[i] += a[i-1];
    ll cntx = 0;
    if(a[N] % 3) return 0;
    ll x = a[N]/3,ans = 0;
    for(int i = 1;i<=N-1;i++){
        if(a[i] == 2*x){
            ans += cntx;
        }
        if(a[i] == x){
            cntx++;
        }
    }
    return ans;
}
int main(){
    // debug_in;

    read(N);
    for(int i = 1;i<=N;i++) read(a[i]);
    ll ans = solve();
    printf("%lld\n",ans);

    return 0;
}

------