USACO 奶牛抗议 Generic Cow Protests
Description
约翰家的N头奶牛聚集在一起,排成一列,正在进行一项抗议活动。第i头奶牛的理智度 为Ai,Ai可能是负数。约翰希望奶牛在抗议时保持理性,为此,他打算将所有的奶牛隔离成 若干个小组,每个小组内的奶牛的理智度总和都要大于零。由于奶牛是按直线排列的,所以 一个小组内的奶牛位置必须是连续的。
请帮助约翰计算一下,存在多少种不同的分组的方案。由于答案可能很大,只要输出答 案除以1,000,000,009的余数即可。
Input Format
第一行:单个整数:N,1 ≤ N ≤ 10^6
第二行到N + 1行:在第i + 1行有一个整数:Ai,表示第i头奶牛的理智度,−10^5 ≤ Ai ≤ 10^5
Output Format
第一行:单个整数,表示分组方案数除以(1,000,000,009)的余数
Sample Input
4
2
3
-3
1
Sample Output
4
Hint
分别是[2 3 − 3 1],[2 3 − 3][1], [2][3 − 3 1],[2][3 − 3] [1]
Solution
本题很容易想到一个(O(n^2))的DP,用(f[i])表示前i个奶牛有几种分组方案,然后枚举(j),如果区间([j+1,i])里的奶牛理智和大于零(f[i])就加上(f[j])即:
设(s[i])为前i头奶牛的理智和
[f[i]=sum ^{i-1}_{j=0}[s[i]-s[j]>=0]*f[j]
]
实际上(f[i])等于所有满足(j<i,s[j]<=s[i])的(f[j])的总和。
求解(f[i])时位置编号是有序的顺序处理即可,但(s)却是无序的且值很大无法解决。
可以发现位置编号很小,如果(s)有序而位置编号无序的话可以用树状数组解决。那怎样才能让位置编号无序,(s)有序?按(s)从小到大排序即可。
Code
#include <cstdio>
#include <algorithm>
#define lowbit(x) ((x)&(-x))
#define LL long long
inline int read(){
int num=0,k=1;char c=getchar();
while (c<'0'||c>'9'){if (c=='-')k=-1;c=getchar();}
while (c>='0'&&c<='9') num=(num<<1)+(num<<3)+c-48,c=getchar();
return num*k;
}
struct info{
LL sum;
int id;
}ox[1000007];
bool cmp(info a,info b){return a.sum<b.sum||(a.sum==b.sum&&a.id<b.id);}
const LL mod=1000000009;
LL n,ans,c[1000007],f[1000007];
int main(){
n=read()+1;
for (int i=2;i<=n;++i)
ox[i].sum=read()+ox[i-1].sum,ox[i].id=i;
ox[1].sum=0,ox[1].id=1;f[1]=1;
std::sort(ox+1,ox+n+1,cmp);
for (int i=1;i<=n;++i){
for (int p=ox[i].id;p;p-=lowbit(p))
f[ox[i].id]=(f[ox[i].id]+c[p])%mod;
for (int p=ox[i].id;p<=n;p+=lowbit(p))
c[p]=(c[p]+f[ox[i].id])%mod;
if (ox[i].id==n) break;
}
printf("%lld
",f[n]);
}