P3049三分数组 | ||
|
问题描述
给出一个有n 个整数的数组a[1],a[2],...,a[n], 有多少种方法把数组分成3 个连续的子序列,使得各子序列的元素之和相等。也就是说,有多少个下标对i,j (2≤i≤j≤n-1), 满足:sum(a[1]..a[i-1]) = sum(a[i]..a[j]) = sum(a[j+1]..a[n])
输入格式
第1 行:1 个整数n(1 <= n <= 5*105)
接下来n 行,每行1 个整数,表示a[i](|a[i]| <= 109)
输出格式
第1 行:1 个整数,表示答案,如果不能3 等分,输出0
样例输入 1
Sample1:
5
1 2 3 0 3
Sample2:
4
0 1 -1 0
Sample3:
2
4 1
样例输出 1
Sample1:
2
Sample2:
1
Sample3:
0
样例输入 2
5
1 2 3 0 3
样例输出 2
2
样例输入 3
4
0 1 -1 0
样例输出 3
1
样例输入 4
2
4 1
样例输出 4
0