3173 小朋友吃糖果
有种糖果（编号
到
）,第
号糖果有
颗，现需要将所有糖果分给两个小朋友，要求两个小朋友得到糖果数量相等，问有多少种分法？
（可以不必将所有糖果分完。如全部都不分，每人的糖果数量为，也算是一种分法）
输入
第一行，一个整数n，表示糖果种类数量
第二行，n个空格间隔的整数，表示每种糖果的数量输出
一行，一个整数，表示总的方案数，答案 mod 1e9+7后再输出。数据范围
10% 2 <= n,ai <= 10
30% 2 <= n,ai <= 30
60% 2 <= n,ai <= 80
100% 2 <= n,ai <= 200输入样例
样例输入 1
1
2
样例输入 2
2
1 2输出样例
输出样例1：
2
输出样例2：
4这里不给解析，直接放代码：
#include<bits/stdc++.h>
#define ll long long
#define N 123456
using namespace std;
ll F[N],S[2][N],A[N],n,m,p,mod=1e9+7;
int main()
{ll i,j,k,t;scanf("%lld",&n);for(i=1;i<=n;i++)scanf("%lld",&A[i]),m+=A[i];F[m]=1;p=m*2;for(i=1;i<=n;i++){S[0][0]=F[0];S[1][0]=0;for(j=1;j<=p;j++)//先处理出前缀和{k=j&1;S[k][j]=(S[k][j-1]+F[j])%mod;S[k^1][j]=S[k^1][j-1];}for(j=0;j<=A[i];j++)F[0]=(F[0]+F[j]*((A[i]-j>>1)+1))%mod;//先算出F[0]for(j=1;j<=p;j++)//递推{k=(A[i]+j)&1;//判断需要的前缀和数组的奇偶F[j]=(F[j-1]+S[k][j+A[i]]-S[k][j-1])%mod;if(j-A[i]-2<0)t=0;else t=S[k^1][j-A[i]-2];F[j]=(F[j]-S[k^1][j-1]+t)%mod;}}cout<<(F[m]+mod)%mod;return 0;
}
