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
#include <bits/stdc++.h>
using namespace std;
constexpr int maxN = 3e5+7, Mod = 1e9+7, Base = 512*1024;

int n,prefix[maxN],ska_prefix[maxN];
long long t[2*Base][2],dp[maxN]; /// 0 - parzyste, 1 - nieparzyste
pair<int,int>para[maxN];

void insert(int v, long long val, bool co)
{
    v += Base;
    while(v)
    {
        t[v][co] += val;
        v /= 2;
    }
}

long long query(int va, int vb, bool co)
{
    va += Base, vb += Base;
    long long wyn = t[va][co];
    if(va != vb)
        wyn += t[vb][co];
    while(va/2 != vb/2)
    {
        if(va % 2 == 0)
            wyn += t[va+1][co];
        if(vb % 2 == 1)
            wyn += t[vb-1][co];
        va/=2, vb/=2;
    }
    return wyn;
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin>>n;
for(int i=1;i<=n;i++)
{
    int a;
    cin>>a;
    prefix[i] = prefix[i-1]+a;
    if(prefix[i] >= Mod)
        prefix[i] -= Mod;
    para[i] = {prefix[i], i};
}
sort(para+1, para+1+n);
int K = 0;
for(int i=1;i<=n;i++)
{
    if(para[i].first > para[i-1].first)
        K++;
    ska_prefix[para[i].second] = K;
}

insert(0,1,0);
for(int i=1;i<=n;i++)
{
    if(prefix[i] % 2 == 0)
    {
        dp[i] = (query(0,ska_prefix[i],0) + query(ska_prefix[i]+1,K,1))%Mod;
        insert(ska_prefix[i], dp[i], 0);
    }
    else
    {
        dp[i] = (query(0,ska_prefix[i],1) + query(ska_prefix[i]+1,K,0))%Mod;
        insert(ska_prefix[i], dp[i], 1);
    }
}

cout<<dp[n]%Mod;
}

/*

4
1000000006 1 5 1000000004

*/