TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3049
  • Problem
  • P3049三分数组
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Judgment Tips : 0.5s
    Description

    给出一个有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])

    Input Format

    第1 行:1 个整数n(1 <= n <= 5*105)
    接下来n 行,每行1 个整数,表示a[i](|a[i]| <= 109)

    Output Format

    第1 行:1 个整数,表示答案,如果不能3 等分,输出0

    Sample Input 1

    Sample1:
    5
    1 2 3 0 3

    Sample2:
    4
    0 1 -1 0

    Sample3:
    2
    4 1

    Sample Output 1

    Sample1:
    2
    Sample2:
    1
    Sample3:
    0

    Sample Input 2

    5
    1 2 3 0 3

    Sample Output 2

    2

    Sample Input 3

    4
    0 1 -1 0

    Sample Output 3

    1

    Sample Input 4

    2
    4 1

    Sample Output 4

    0