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
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
map <int,int> m;
const int MAXN = 1e5 * 3 + 10;
const long long int mod = 1e9 + 7;
int n,t[MAXN],last=1;
int pref[MAXN];
vector <int> g1,g2;
void add(int x, int val , vector <int> &k){
    for(; x < k.size(); x = x | (x + 1))
        k[x] = (k[x] + val) % mod;
}
int sum(int x, vector <int> &k){
    int cnt = 0;
    for (; x >= 0; x = (x & (x + 1)) - 1)
        cnt = (cnt + k[x]) % mod;
    return cnt;
}
int segment(int beg, int end, vector <int> &k){
    int res = sum(end,k) - sum(beg,k);
    if(res < 0)
        res += mod;
    res = res % mod;
    return res;
}
int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> t[i];
        pref[i] = (pref[i-1] + t[i]) % mod;
    }
    sort(pref + 1,pref + n + 1);
    for(int i = 1; i <= n; i++)
        if(!m[pref[i]])
            m[pref[i]] = ++last;
    g1.resize(last + 2,0); g2.resize(last + 2,0);
    add(1,1,g1);
    long long dp = 0;
    long long pom = 0;
    for(int i = 1; i <= n; i++){
        dp = 0;
        pom = (pom + t[i]) % mod;
        if(pom % 2 == 0){
            dp = segment(0,m[pom],g1);
            dp = (dp + segment(m[pom],last+1,g2) ) % mod;
            add(m[pom],dp,g1);
        }else{
            dp = segment(0,m[pom],g2);
            dp = ( dp + segment(m[pom],last+1,g1) ) % mod;
            add(m[pom],dp,g2);
        }
        //cout << dp << "\n";
    }cout << dp << endl;
}