1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define I if
#define E else
#define W while
#define F for
#define R return
#define S scanf
#define P printf


using namespace std;const int mod=1000000007;const int mod2=mod*2;int
arr[300000];int pref[300001];int dp[300001];int tree[2][1<<20];int
r[2];map <int,int> mapa[2];int sumRange(int v,int vl,int vr,int sl,int
sr,int j){I(vr<sl || sr<vl)R 0;I(sl<=vl && vr<=sr)R tree[j][v];R
(sumRange(v*2,vl,(vl+vr)/2,sl,sr,j)+sumRange(v*2+1,(vl+vr+1)/2,vr,sl,sr,j))%mod;}int
main(){int
n,i,j,v,a,b;S("%d",&n);F(i=0;i<n;i++)S("%d",&arr[i]);F(i=0;i<n;i++)pref[i+1]=((long
long)pref[i]+arr[i])%mod2;mapa[0][0]=0;mapa[0][mod2-2]=0;mapa[1][1]=0;mapa[1][mod2-1]=0;F(i=0;i<=n;i++)I(mapa[pref[i]%2].find(pref[i])==mapa[pref[i]%2].end())mapa[pref[i]%2][pref[i]]=0;F(j=0;j<2;j++){i=0;F(auto
ai=mapa[j].begin();ai!=mapa[j].end();ai++){ai->second=i++;}r[j]=1;W(r[j]<i)r[j]*=2;}mapa[0][-1]=-1;mapa[1][-1]=-1;dp[0]=1;tree[0][r[0]]=1;v=r[0]/2;W(v>0){tree[0][v]=1;v/=2;}F(i=0;i<n;i++){a=((long
long)mod2+pref[i+1]-(mod-1))%mod2;b=pref[i+1];F(j=0;j<2;j++){I(a<b){dp[i+1]+=sumRange(1,0,r[(j+pref[i+1])%2]-1,mapa[(j+pref[i+1])%2].lower_bound(a)->second,(--mapa[(j+pref[i+1])%2].upper_bound(b))->second,(j+pref[i+1])%2);}E{dp[i+1]+=(sumRange(1,0,r[(j+pref[i+1])%2]-1,0,(--mapa[(j+pref[i+1])%2].upper_bound(b))->second,(j+pref[i+1])%2)+sumRange(1,0,r[(j+pref[i+1])%2]-1,mapa[(j+pref[i+1])%2].lower_bound(a)->second,mod2-1,(j+pref[i+1])%2))%mod;}dp[i+1]%=mod;a=(pref[i+1]+1)%mod2;b=((long
long)mod2+pref[i+1]-mod)%mod2;}j=pref[i+1]%2;v=r[j]+mapa[j][pref[i+1]];tree[j][v]+=dp[i+1];tree[j][v]%=mod;v/=2;W(v>0){tree[j][v]=(tree[j][v*2]+tree[j][v*2+1])%mod;v/=2;}}P("%d\n",dp[n]);}