TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3049
  • 题目
  • P3049三分数组
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    给出一个有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*10^5)
    接下来n 行,每行1 个整数,表示a[i](|a[i]| <= 10^9)

    输出格式

    第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