题目

给定一个长度为 n的数组 a1,a2,…,an。

现在，要将该数组从中间截断，得到三个非空子数组。

要求，三个子数组内各元素之和都相等。

请问，共有多少种不同的截断方法？

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

输出一个整数，表示截断方法数量。

数据范围

前六个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤1e5，−10000≤ai≤10000。

输入样例1：

4
1 2 3 34
1 2 3 3

输出样例1：

1

输入样例2：

5
1 2 3 4 5

输出样例2：

0

输入样例3：

2
0 0

输出样例3：

0

思路：

1.分为三个数组，并且和相等，也就意味着每个部分都是总和的1/3

2.总和必须能整除3

3.相当于要在数组上找两个位置，第一个位置 sum/3，第二个位置 (sum/3)*2

4.这两个位置可取的点都有若干个，那么它们的全部组合为（第一个位置可取的点）*（第二个位置可取的点）

//注意数据范围

代码：

#include<iostream>
using namespace std;
long long sum[100005];
long long n, tmp,ans;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> sum[i];
        sum[i] += sum[i - 1];
    }
    if (sum[n] % 3 != 0)ans = 0;
    else
    {
        long long cnt = 0;
        tmp = sum[n] / 3;
        for (int i = 1; i < n; i++)
        {
            if (sum[i] == 2 * tmp)ans += cnt;
            if (sum[i] == tmp)cnt++;
        }
    }
    cout << ans;
}