#1475 : 数组分拆

描述

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

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

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

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

输入

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

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

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

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

输出

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

51 -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;}