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
|
#include<algorithm>
#include<cstring>
using namespace std;
namespace io{
#define re register
#define ll long long
#define inf 0x3f3f3f3f
#define il inline
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il void (ll &x){
x=0;ll f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=f;
}
il void read(int &x){
x=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=f;
}
}using namespace io;
#define N 100010
const int mod=1e9+9;
int n;
int c[N];
ll sum[N];
void dec(){
ll tmp[N];
for(re int i=1;i<=n;i++) tmp[i]=sum[i];
sort(tmp+1,tmp+n+1);
for(re int i=0;i<=n;i++) sum[i]=lower_bound(tmp+1,tmp+n+1,sum[i])-tmp+1;
}
il void add(int i,int val){
while(i<N){
c[i]=1ll*(c[i]+val)%mod;
i+=i&(-i);
}
}
il ll ask(int i){
ll res=0;
while(i>0){
res=1ll*(res+c[i])%mod;
i-=i&(-i);
}
return res;
}
int main(){
read(n);
for(re int i=1;i<=n;i++) readl(sum[i]),sum[i]+=sum[i-1];
dec();
add(sum[0],1);
ll ans;
for(re int i=1;i<=n;i++){
ans=ask(sum[i]);
add(sum[i],ans);
}
printf("%lld",ans);
return 0;
}
|
近期评论