A2025. Generic Cow Protests G
编程题
提高+/省选-
知识点
题目描述
Farmer John 的 $N$ 头奶牛（$1 \leq N \leq 10^5$）排成一列，正在进行一场抗议活动。第 $i$ 头奶牛的理智度为 $a_i$（$-10^4 \leq a_i \leq 10^4$）。
FJ 希望奶牛在抗议时保持理性，为此，他打算将所有的奶牛隔离成若干个小组，每个小组内的奶牛的理智度总和都要不小于零。
由于奶牛是按直线排列的，所以一个小组内的奶牛位置必须是连续的。请帮助 FJ 计算一下，满足条件的分组方案有多少种。
FJ 希望奶牛在抗议时保持理性，为此，他打算将所有的奶牛隔离成若干个小组，每个小组内的奶牛的理智度总和都要不小于零。
由于奶牛是按直线排列的，所以一个小组内的奶牛位置必须是连续的。请帮助 FJ 计算一下，满足条件的分组方案有多少种。
输入格式
第一行一个整数 $N$。
接下来 $N$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 头奶牛的理智度 $a_i$。
接下来 $N$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 头奶牛的理智度 $a_i$。
输出格式
输出满足条件的分组方案对 $10^9+9$ 取模的结果。
输入输出样例
输入 #1
4 2 3 -3 1
输出 #1
4
说明/提示
所有合法分组方案如下：
- $\texttt{(2 3 -3 1)}$
- $\texttt{(2 3 -3) (1)}$
- $\texttt{(2) (3 -3 1)}$
- $\texttt{(2) (3 -3) (1)}$
- $\texttt{(2 3 -3 1)}$
- $\texttt{(2 3 -3) (1)}$
- $\texttt{(2) (3 -3 1)}$
- $\texttt{(2) (3 -3) (1)}$