#1475 : 数组分拆

时间限制:10000ms 单点时限:1000ms 内存限制:256MB

描述

小Ho得到了一个数组作为他的新年礼物，他非常喜欢这个数组！

在仔细研究了几天之后，小Ho成功的将这个数组拆成了若干段，并且每段的和都不为0！

现在小Ho希望知道，这样的拆分方法一共有多少种？

两种拆分方法被视作不同，当且仅当数组断开的所有位置组成的集合不同。

输入

每组输入的第一行为一个正整数N，表示这个数组的长度

第二行为N个整数A1~AN，描述小Ho收到的这个数组

对于40%的数据，满足1<=N<=10

对于100%的数据，满足1<=N<=105, |Ai|<=100

输出

对于每组输入，输出一行Ans，表示拆分方案的数量除以(109+7)的余数。

样例输入

5
1 -1 0 2 -2

样例输出

5


#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

const int mod = 1000000007;
int main()
{
	freopen( "/home/liyuanshuo/ClionPRoject/hihocoder8/in.in", "r", stdin);
	int n;
	cin>>n;
	vector<int> f( n, 0 );
	f[0] = 1;
	unordered_map<int , int > m;
	m.insert(make_pair(0,1));
	int s = 0, ss = 1;
	for (int i = 0 ; i < n ; ++i)
	{
		int x;
		cin>>x;
		s += x;
		f[i] = ( ss - m[s] + mod ) % mod;
		if ( m.count(s) )
			m[s] = ( m[s] + f[i] ) % mod;
		ss = ( ss + f[i] ) % mod;
	}
	cout<<f[n-1]<<endl;
	return 0;
}