0
被禁言
中级光能
题目描述 Description
飞翔的祖母一直和飞翔住在一起。老太太非常喜欢自己的孙子，在飞翔小时候经常给他讲故事。有的故事，会让飞翔非常开心；有的故事，会让飞翔非常悲伤。为了平复飞翔的心情，祖母讲完一个开心的故事，就会接着讲一个悲伤的故事；如果先讲了一个悲伤的故事，后面就会讲一个开心的故事。总之，开心的故事和悲伤的故事数量要一致，心情才能平复。祖母一共有n 个故事。现在按照顺序给出n 个故事的属性（1 表示开心，-1 表示悲伤），请你统计有多少种方案，是可以让飞翔保持心情平静的。故事的选取，必须是连续的。结果请对2019求余。
输入描述 Input Description
共2行：第一行为n，表示故事的个数；第二行为n 个用空格隔开的1和-1序列，表示故事是开心的，还是悲伤的。
输出描述 Output Description
一行，一个整数，方案数对2019 求余的结果。
样例输入 Sample Input
9
-1 1 -1 -1 -1 1 1 -1 -1
样例输出 Sample Output
8
数据范围及提示 Data Size & Hint
40%的数据1<=n<=1000， 100%的数据1<=n<=1000000。去年区赛就是这题没做出来
求思路
1
初级天翼
你不是学了前缀和吗？这个都写不出来？
0
初级天翼
前缀和+差分思想
0
高级光能
我们老师说去年区赛的题目有问题🤨泪奔啊
0
初级启示者
nasfsdaffsjandnfmsmafsmdnafmndmnfm
0
中级启示者
上次市赛我参加了，但是这题没做出来
0
缔造者之神
前缀和
0
缔造者之神
学了前缀和就简单了
0
高级守护
用前缀和做
0
新手天翼
我也没做出来
0
高级光能
0
中级光能
ding
0
中级守护
我给你一个思路，前缀和懂吗？
对于一个数组a[1005]，它的前缀和指的是，从第一个数字到第i个数字的和
前缀和的一个最直接的应用是快速计算一个子数组的和。如果要计算某一段子数组和，本来是需要循环求和。但是如果要多次计算时，时间复杂度是0(kn)。n是数组长度，k是计算次数。但是如果先预处理出每一-个位置结束的前缀和，那么每次子数组和的计算在0(1)的时间内就可以完成。时间复杂度为0(k+n)。
令f[i]表示a[1]–a[i]的和
状态转移方程是
sum[i]=sum[i-1]+a[i];
举个例子：
10 5 7 3 4 如果我要求第2个到第4个的数之和，如果用普通方法必定超时，所以我们可以先求出前缀和
分别是：10 15 22 25 29，而求出这个数列，就是运用这个状态转移方程，最终如何输出第2个到第4个的数之和呢？只要输出sum[4]-sum[2-1]就可以了，25-10=15，结果就是15，再用普通方法验证一下5+7+3=15，求采纳，打了那么多字，谢谢！
方晨顺在2020-07-24 23:09:23追加了内容
如果懂了前缀和，这题就不难了
