No testdata at current.

题目描述

你是 $B$ 学校的一名教师。你有 $n$ 名学生，编号为 $1, 2, \dots, n$。在近期的一次测试中，编号为 $i$ 的学生的得分为 $a_i$。

你需要对学生们的得分抽样调查。一次抽样调查需要选出编号连续的若干名学生，我们称这一次抽样调查是准确的当且仅当选出的这些学生得分的平均数为整数。

你想知道在所有 $\frac{n(n+1)}{2}$ 种选出编号连续的学生的抽样调查方案中，有多少种方案能使这一次抽样调查是准确的。

---

输入格式

从标准输入读入数据。

第一行一个正整数 $n$。

第二行包含 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$。

---

输出格式

输出到标准输出。

输出一行一个正整数，表示所求的方案数。

---

样例输入

5
1 2 3 4 5

样例输出

8

样例解释

仅选出 $1$ 名学生的 $5$ 种方案都是准确的；

除此之外，选出的学生编号集合为 $\{3,4\}$、$\{2,3,4,5\}$ 与 $\{1,2,3,4,5\}$ 的方案也是准确的，共有 $8$ 种不同的方案。

---

数据范围

对于 $100\%$ 的数据，保证：

• $1 \le n \le 10^5$
• $1 \le a_i \le 100$

---

具体数据范围如下表：

测试点编号	$n$ 上限	特殊限制
1	$\le 5$	无特殊限制
2 $\sim$ 3	$\le 100$
4 $\sim$ 5	$\le 3000$
6 $\sim$ 7	$\le 10^5$	$a_i \le 2$
8 $\sim$ 10		无特殊限制

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
const int MAXN=1e7;
int n,a[N],b[N],ma,mi=0x3f3f3f3f,book[2*MAXN+10];
ll ans;
int main(){
	//freopen("ex_score2.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]>ma) ma=a[i];
		if(a[i]<mi) mi=a[i];
	}
	for(int t=mi;t<=ma;t++){
		for(int i=1;i<=n;i++){
			b[i]=b[i-1]+(a[i]-t);
			ans+=book[b[i]+MAXN];
			book[b[i]+MAXN]++;
			//cout<<b[i]<<" ";
		}
		ans+=book[MAXN];
		for(int i=1;i<=n;i++) book[b[i]+MAXN]=0;
		/*for(int i=0;i<=2*MAXN;i++){
			int s=book[i];
			if(s>1) ans+=book[i];
		}*/
		//cout<<endl;
	}
	printf("%lld",ans);
	return 0;
}