codeforces 466 C. Number of Ways
http://codeforces.com/problemset/problem/466/C 题意：给定一个序列。要将序列分成三个非零的连续部分，使得三部分的和相等。问有多少中分法。 思路：首先可以知道，如果是序列的和不为3的倍数，那么一定无解，输出0.设序列的和为sum,那么每一部分的和就应该为sum/3。我们可以预处理出从1开始的和为sum/3的点（我开了数组表示前缀和。。想了下其实不用。。我只需要点的信息。。所以用一个变量表示即可），将点的下标存在p[i]里。对于每一个p[i]，我想要知道比p[i]大且补与p[i]相邻的点中，有多少个j，使得从j到n的和为sum/3。因为如果有两部分的和都为sum/3，那么剩下的那部分也一定为sum/3.然后要知道有多少个满足题意的j,我们可以从后往前扫一遍，标记从n开始往前扫，和为sum/3的点，可以用一个0,1数组表示。如果和为sum/3，那么标记为1，否则为0.然后再用一个类似前缀和的思路。再开一个数组c记录从j到n有的和为多少，也就是从j到n有多少个点满足该点到n的和为sum/3.
预处理完这些之后。只需要从前往后扫一遍p[i]，然后ans+=c[p[i]+2]即可。
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月15日 星期二 20时28分44秒
4File Name :code/cf/problem/466C.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=5E5+7;
34int n;
35int a[N];
36LL sum[N],rsum[N];
37int p[N],rp[N];
38int cnt,rcnt;
39int b[N];
40int c[N];
41LL ans;
42LL solve()
43{
44 LL total = sum[n];
45 if (total%3!=0) return 0;
46 LL ave = total/3;
47 cnt = 0 ;
48 for ( int i = 1 ; i <= n ; i++)
49 {
50 if (sum[i]==ave)
51 {
52 cnt++;
53 p[cnt] = i;
54 // cout<<"i:"<<i<<endl;
55 }
56 }
57 ms(b,0);
58 for ( int i = n ; i >= 1 ; i--)
59 {
60 if (rsum[i]==ave)
61 {
62 b[i] = 1; //b[i]为1表示可以，为0表示不可以。
63 }
64 }
65 c[n] = b[n]; //c[i]表示i..n一共有多少个b[i]可以。
66 for ( int i = n-1 ; i >= 1 ; i--)
67 {
68 c[i] = c[i+1] + b[i];
69 }
70
71
72 LL res = 0 ;
73 for ( int i = 1 ; i <= cnt ; i++)
74 {
75 res+= c[p[i]+2]; //中间至少隔一个，因为要分成三组。
76 }
77 return res;
78
79}
80int main()
81{
82 #ifndef ONLINE_JUDGE
83 freopen("code/in.txt","r",stdin);
84 #endif
85
86 cin>>n;
87 sum[0] = 0 ;
88
89 for ( int i = 1 ; i <= n ; i++)
90 {
91 scanf("%d",&a[i]);
92 sum[i] = sum[i-1] + a[i];
93 }
94 rsum[n+1] = 0 ;
95 for ( int i = n ; i >= 1 ; i --)
96 {
97 rsum[i] = rsum[i+1] + a[i];
98 }
99 ans = solve();
100 cout<<ans<<endl;
101
102
103 #ifndef ONLINE_JUDGE
104 fclose(stdin);
105 #endif
106 return 0;
107}