【题解】
我们可以轻松想到朴素的状态转移方程，但直接这样做是n^2的。所以我们考虑采用树状数组优化。写法跟求逆序对很相似，即对前缀和离散化之后开一个权值树状数组，每次f[i]+=query(sum[i])，再把f[i]加入到sum[i]位置上。这样可以保证每次f[i]加上的是在它前面的、sum小于它的位置的f值。
1 #include<cstdio> 2 #include<algorithm> 3 #define N 200010 4 #define rg register 5 #define Mod (1000000009) 6 using namespace std; 7 int n,m,f[N]; 8 long long a[N],b[N],t[N]; 9 inline int read(){ 10 int k=0,f=1; char c=getchar(); 11 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 12 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 13 return k*f; 14 } 15 inline void add(int x,int y){ 16 for(;x<=n+10&&x>0;x+=(x&-x)){t[x]+=y; t[x]%=Mod;} 17 } 18 inline int query(int x){ 19 int ret=0; for(;x;x-=x&-x){ret+=t[x]; ret%=Mod;} return ret%Mod; 20 } 21 int main(){ 22 n=read(); 23 for(rg int i=1;i<=n;i++) a[i]=read()+a[i-1],b[i]=a[i]; a[0]=b[0]=0; 24 sort(b,b+1+n); int n2=unique(b,b+1+n)-b-1; 25 for(rg int i=0;i<=n;i++) a[i]=lower_bound(b,b+1+n2,a[i])-b+1; 26 // for(rg int i=0;i<=n;i++) printf("%lld ",a[i]); puts(""); 27 add(a[0],f[0]=1); 28 for(rg int i=1;i<=n;i++){ 29 f[i]+=query(a[i]); f[i]%=Mod; 30 add(a[i],f[i]); 31 } 32 printf("%d ",f[n]%Mod); 33 return 0; 34 }