466C. Number of Ways

binary search/brute force/data structures/dp/two pointers, 1700, https://codeforces.com/problemset/problem/466/C

You've got array a[1], a[2], ..., a[n], consisting of n integers. Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same.

More formally, you need to find the number of such pairs of indices i, j (2 ≤ i ≤ j ≤ n - 1), that $\sum_{k = 1}^{i - 1} a_{k}$ = $\sum_{k = i}^{j} a_{k}$ = $\sum_{k = j + 1}^{n} a_{k}$

Input

The first line contains integer n (1 ≤ n ≤ 5·10^5^), showing how many numbers are in the array. The second line contains n integers a[1], a[2], ..., a[n] (|a[i]| ≤ 10^9^) — the elements of array a.

Output

Print a single integer — the number of ways to split the array into three parts with the same sum.

Examples

input

5
1 2 3 0 3

output

input

4
0 1 -1 0

output

input

2
4 1

output

【汤建浩，2020年秋】难点在于总和能除以三的部分。由于是分成连续的三部分，每部分一样，只需要对列表一项项地加下去。其中一些节点非常重要，如前缀和达到1/3 和达到2/3，此两项都要满足，且存在前缀和达到1/3先于前缀和达到2/3的情况，才能分成连续三份。出现一次前缀和达到1/3 不能说明什么，但我们要记录下来s++，在它之后出现前缀和2/3，我们就把这个情况ans += s
【王君宇，2020年秋】这道题的最大坑点就是分割是有序的...我因为没认真审题而半天毫无头绪。既然是有序的，我们可以遍历逐个求和。如果总和不是 3的倍数显然不能分割，否则我们先得到sum/3，之后是 2*sum/3. 因此我们可以分成两步。当我们得到第一个分割之后，每得到一种便相应将二级种数加一。得到第二个分割后就将之前分割的总种数加起来。这里运用了类似于乘法原理的分布计数思想。另外，我们求和的终点应当是倒数第二个元素，防止 sum==0时总种数出错。
【黄旭，2020年秋】将列表中的元素进行累加，由于要将其三等分，所以计算总和的三分之一以及三分之二，并应该将能得到三分之一的方法数乘以能得到三分之二的方法数从而得到方法总数，方法能想到就不难，不然可能要想很久很久（比如昨晚做到很晚）

双指针，同向右走，前缀和2/3的指针一定在前缀和1/3的右侧，所以正确。

例如：

3 3 -3 3 3

双指针向右走的过程

ans=1 ans+=s

=> =>

3 3 -3 3 3

-> -> ->

s=1 s=2

python

n = int(input())
a = [int(i) for i in input().split()]
s = sum(a)
x = 0
if s%3 == 0:
    d1 = s/3
    d2 = 2*d1
    z = t = 0
    for i in range(n-1):
        z += a[i]

        if z == d2:
            x += t
        if z == d1:
            t += 1
print(x)

解题思路：前缀和优化。当前缀和达到1/3时s++，达到2/3时候 ans += s

python

n = int(input())
a = [0]
a.extend([int(x) for x in input().split()])

prefix_sum = [0]*(n+1)

for i in range(1, n+1):
    prefix_sum[i] = prefix_sum[i-1] + a[i]
    
if (prefix_sum[n]%3) != 0:
    print(0)
else:
    s = ans = 0
    for i in range(1, n+1):         
        if i>1 and i<n and prefix_sum[i]==(prefix_sum[n]*2//3):
            ans += s
        
        if prefix_sum[i] == (prefix_sum[n]//3):
            s += 1
            
    print(ans)

解题思路：tutorial, https://codeforces.com/blog/entry/13758

First of all, notice that if sum of all elements is equal S then sum of each of three parts is equal $S / 3$ Therefore, if S is not divided by 3 — then answer is 0. Otherwise, let’s iterate the end of first part i (1 ≤ i ≤ n - 2) and if sum of 1..i elements is equal $S / 3$ then it means that we have to add to the answer the amount of such j (i + 1 < j) that the sum of elements from j-th to n-tn also equals $S / 3$ .

Let’s create an array $c n t []$ , where $c n t [i]$ equals 1, if the sum of elements from i-th to n-th equals $S / 3$ and 0 — otherwise. Now, to calculate the answer we have to find the sum cnt[j] + cnt[j+1] + ... + cnt[n] faster then O(n). There are a lot of required ways to do this, but the easiest one is to create a new additional array sums[] where in j-th element will be cnt[j] + cnt[j+1] + ... + cnt[n]. It is easy to calculate in such way: sums[n] = cnt[n], sums[i] = sums[i+1] + cnt[i] (i < n).

Thus, we receive very simple solution: for each prefix of initial array 1..i with the sum that equals $S / 3$ we need to add to the answer sums[i+2].

Complexity: O(n)

python

n = int(input())
a = [int(x) for x in input().split()]
s = sum(a)

if s%3 != 0:
    print(0)
else:
    s = s//3
    
    ss = 0
    cnt = [0]*1000010

    for i in range(n-1,-1,-1):
        ss += a[i]
        if ss == s:
            cnt[i] = 1

    for i in range(n-2,-1,-1):
        cnt[i] += cnt[i+1]

    ans = 0
    ss = 0
    for i in range(n-2):
        ss += a[i]
        if ss == s:
            ans += cnt[i+2]

    print(ans)

466C. Number of Ways ​

466C. Number of Ways