#P2344. [USACO11FEB] Generic Cow Protests G

    ID: 1354 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>前缀和动态规划dp树状数组离散化USACO2011

[USACO11FEB] Generic Cow Protests G

题目描述

Farmer John 的 NN 头奶牛(1N1051 \leq N \leq 10^5)排成一列,正在进行一场抗议活动。第 ii 头奶牛的理智度为 aia_i104ai104-10^4 \leq a_i \leq 10^4)。

FJ 希望奶牛在抗议时保持理性,为此,他打算将所有的奶牛隔离成若干个小组,每个小组内的奶牛的理智度总和都要不小于零。

由于奶牛是按直线排列的,所以一个小组内的奶牛位置必须是连续的。请帮助 FJ 计算一下,满足条件的分组方案有多少种。

输入格式

第一行一个整数 NN

接下来 NN 行,每行一个整数,第 ii 行的整数表示第 ii 头奶牛的理智度 aia_i

输出格式

输出满足条件的分组方案对 109+910^9+9 取模的结果。

4
2
3
-3
1
4

提示

所有合法分组方案如下:

  • (2 3 -3 1)\texttt{(2 3 -3 1)}
  • (2 3 -3) (1)\texttt{(2 3 -3) (1)}
  • (2) (3 -3 1)\texttt{(2) (3 -3 1)}
  • (2) (3 -3) (1)\texttt{(2) (3 -3) (1)}