P2344 奶牛抗议

显然，如果一个区间$[l,r]$能分成一组，则$sum[r]>=sum[l-1]$ 用$f[i]$表示前i头奶牛的方案数，则 $f[i]=sigma(f[j], j<i $&&$ Sum(j+1,i)>=0 )$ 然后直接这样做呢。。不一定能卡过 可以用树状数组优化：用$c[x]$表示$i$之前$sum==x$的$f$值之和 则$f[i]$为小于$sum[i]$的所有$f$之和 进而可以求出小于$sum[i]$的区间和 由于a数组有正有负，所以$sum$可能为0 在树状数组中需要偏移一下（就是整体+1） ~~离散化一下也是可以的~~ ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; typedef long long ll; const int N=1e5+5,mod=1e9+9; int n,a[N],cnt,sum[N],val[N],maxn=-2e9,c[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline int getpos(int x) { return lower_bound(val,val+cnt+1,x)-val; } inline int lowbit(int x) { return x&(-x); } inline void add(int x,int k) { ++x; while (x<=maxn+1) { c[x]=(c[x]+k)%mod; x+=lowbit(x); } } inline int getsum(int x) { int res=0; ++x; while (x) { res=(res+c[x])%mod; x-=lowbit(x); } return res; } int main() { n=read(); for (reg int i=1;i<=n;i++) { a[i]=read(); sum[i]=sum[i-1]+a[i]; maxn=max(maxn,sum[i]); } sort(sum,sum+n+1); for (reg int i=1;i<=n;i++) if (sum[i]!=sum[i-1]) val[++cnt]=sum[i]; add(getpos(0),1); int tot=0,ans=0; for (reg int i=1;i<=n;i++) { tot+=a[i]; ans=getsum(getpos(tot))%mod; add(getpos(tot),ans); } printf("%d\n",ans); return 0; } ```