Candy Distribution

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 499    Accepted Submission(s): 189

The first line contains an integer T<=11 which is the number of test cases.


Then T
cases follow. Each case contains two lines. The first line contains one integer n(1<=n<=200). The second line contains n integers ai(1<=ai<=200)

2

1

2

2

1 2

2

4

Hint

     Sample: a total of 4, (1) Ecry and lasten are not assigned to the candy; (2) Ecry and lasten each to a second kind of candy; (3) Ecry points to one of the first kind of candy, lasten points to a second type of candy; (4) Ecry points to a second type of candy, lasten points to one of the first kind of candy.

令f[cur][j]为当前状态,表示截至第cur类糖，A比B多j个糖的方案

f[cur][j]=f[cur-1][j]*(a[i]/2)+f[cur-1][j±1]*(a[i]-1)/2+...+f[cur][j±a[i]]*1

从系数上看

a[i]=1:

a[i]=2:

a[i]=3:

我们奇偶分类讨论，非常easy发现f[cur][j+1]-f[cur][j] = 某段区间奇(偶)数位区间和 - 某段区间偶(奇)数位区间和

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<functional>

#include<iostream>

#include<cmath>

#include<cctype>

#include<ctime>

using namespace std;

#define For(i,n) for(int i=1;i<=n;i++)

#define Fork(i,k,n) for(int i=k;i<=n;i++)

#define Forkstep(i,k,s,n) for(int i=k;i<=n;i+=s)

#define Rep(i,n) for(int i=0;i<n;i++)

#define ForD(i,n) for(int i=n;i;i--)

#define RepD(i,n) for(int i=n;i>=0;i--)

#define Forp(x) for(int p=pre[x];p;p=next[p])

#define Forpiter(x) for(int &p=iter[x];p;p=next[p])

#define Lson (x<<1)

#define Rson ((x<<1)+1)

#define MEM(a) memset(a,0,sizeof(a));

#define MEMI(a) memset(a,127,sizeof(a));

#define MEMi(a) memset(a,128,sizeof(a));

#define INF (2139062143)

#define F (1000000007)

#define MAXN (200+10)

#define MAXSA (40000+10)

typedef long long ll;

ll mul(ll a,ll b){return (a*b)%F;}

ll add(ll a,ll b){return (a+b+llabs(a+b)/F*F+F)%F;}

//ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}

void upd(ll &a,ll b){a=(a+b+llabs(a+b)/F*F+F)%F;}

void sub(ll &a,ll b){a=(a-b+llabs(a-b)/F*F+F)%F;}

int n;

const int M = 40500;

int a[MAXN];

ll dp[2][MAXSA*2+10000],sum[2][MAXSA*2+10000];

int main()

{

//	freopen("hdu5291.in","r",stdin);

//	freopen(".out","w",stdout);

	int T;cin>>T;

	while(T--) {

		MEM(dp) MEM(sum) MEM(a)

		cin>>n;

		For(i,n) scanf("%d",&a[i]);

		int cur=0,s=0,tot=0;

		dp[cur][M]=1;

		For(i,n)

		{

			if (a[i]==0) continue;

			int s=a[i];

			MEM(sum)

			Fork(k,1,M+tot+a[i]+a[i])

			{

				sum[k&1][k]=add(sum[ (k&1) ][k-1] ,dp[cur][k] );

				sum[(k&1)^1][k]=sum[(k&1)^1][k-1] ;

			} 

			tot+=a[i];

			cur^=1; MEM(dp[cur])

			int t=M-tot;

			dp[cur][t]=1;

			if (s%2==0)

				Fork(k,M-tot+1,M+tot)

					{

						dp[cur][k]=dp[cur][k-1];

						upd(dp[cur][k], sum[k&1][k+s]-sum[k&1][k-1] );

						sub(dp[cur][k], sum[(k&1)^1][k-1]-sum[(k&1)^1][k-1-s-1]);

					}

			else

				Fork(k,M-tot+1,M+tot)

					{

						dp[cur][k]=dp[cur][k-1];

						upd(dp[cur][k], sum[(k&1)^1][k+s]-sum[(k&1)^1][k-1] );

						sub(dp[cur][k], sum[k&1][k-1]-sum[k&1][k-1-s-1]);

					}

		} 

		printf("%lld\n",dp[cur][M]);

	}	

	return 0;

}