11289: 【原1289】扑克牌分组

题目

题目描述

author: Xutong Chen 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1289

Description

cxt的扑克牌越来越先进了，这回牌面的点数还可以是负数， 这回cxt准备给扑克牌分组，他打算将所有的牌分成若干个堆,每堆的牌面总和和都要大于零。由于扑克牌是按顺序排列的,所以一堆牌在原牌堆里面必须是连续的。请帮助cxt计算一下,存在多少种不同的分牌的方案。由于答案可能很大,只要输出答案除以1,000,000,009的余数即可。

Input Format

第一行:单个整数:N,1 ≤ N ≤ 10^6

第二行到N + 1行:在第i + 1行有一个整数:Ai, 表示第i张牌牌面的值。

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]

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！