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
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
// kody zaczerpnięte ze strony https://cp-algorithms.com/algebra/fft.html

#include<iostream> 
#include<algorithm>
#include<vector>
#include<cmath>
#include<ctime>
#include<cstring>
#include<limits>
#include<complex>
using namespace std;

using cd = complex<long double>;
const long double PI = acos(-1);

void fft(vector<cd> & a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        long double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd & x : a)
            x /= n;
    }
}

vector<long long> multiply(vector<long long> const& a, vector<long long> const& b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) 
        n <<= 1;
    fa.resize(n);
    fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++)
        fa[i] *= fb[i];
    fft(fa, true);

    vector<long long> result(n);
    for (int i = 0; i < n; i++)
        result[i] = round(fa[i].real());
    return result;
}

int main() {
	ios::sync_with_stdio(0);
	//cout<<fixed<<numeric_limits<double>::max();
	int N,S[501];
	cin>>N;
	for(int i=0; i<501; ++i) S[i] = 0;
	vector<int> V;
	for(int i=1; i<=N; ++i) {
		int a;
		cin>>a;
		S[i] = S[i-1] + a;
	}
	for(int i=1; i<=N; ++i)
	for(int j=i; j<=N; ++j) {
		V.push_back(S[j] - S[i-1]);
	}
	sort(V.begin(),V.end());
	long long pom = 0;
	for(int i=0; i<V.size(); ++i) if(V[i] == 0) pom++;
	for(int i=0; i<V.size(); ++i)
	for(int j=i+1; j<V.size(); ++j) {
		if(V[i]*2 + V[j] == 0) pom += 3;
		if(V[i] + V[j]*2 == 0) pom += 3;
	}
	int Min = V[0];
	if(Min > 0 || V[V.size()-1] < 0) { cout<<0<<endl; return 0; }
	int R = V.size();
	vector<long long> P;
	for(int i=0; i<(V[R-1] - V[0] + 1); ++i) P.push_back(0);
	for(int i=0; i<R; ++i) P[V[i] - Min] += 1;
	vector<long long> ans;
	ans = multiply(P,P);
	long long out = 0;
	for(int i=-Min; i<P.size(); ++i) if(2 * (-Min) - (i + Min) >= 0) out += (long long)P[i] * (long long)ans[2 * (-Min) - (i + Min)];
	for(int i=-Min-1; i>=0; --i) if(2 * (-Min) + (-Min - i) < ans.size()) out += (long long)P[i] * (long long)ans[2 * (-Min) + (-Min - i)];
	cout<<(out-pom) / 6<<endl;
	
	return 0;
}