多校实在高能
题意：有n中糖果，每种糖果有ai个。分给A,B两个人。两人的糖果要一样多，可以都是0,1......m个。同一种糖果没有区别。
问有几种分法。
定义dp[i]表示两人之间相差i个糖果的情况数。对每种糖果进行处理 *dp[i]表示新计算得到的dp值
当当前有ai个i种糖果时。处理*dp[j]
*dp[j] = dp[j]*(ai/2+1) + dp[j-1]*((ai-1)/2+1) + dp[j+1]*((ai-1)/2+1)
............+dp[j-ai]*((ai-ai)/2+1) + dp[j+ai]*((ai-ai)/2+1)
表示dp[j-k]*((ai-k)/2+1)表示原来A,B相差j-k个糖果，但是通过分第i种糖果，先给A分了k个糖果，让后剩下的糖果再平等
地分给A,B。那么分完之后就相差j个糖果了。由于提前给A，k个糖果，那么剩下ai-k个糖果，平分剩下糖果的情况有（ai-k)/2+1种。+1是两
个人人都分0个。
假设ai = 2 j = 0, 那么dp[0] =
dp: dp[-2] dp[-1] dp[0] dp[1] dp[2]
系数：1 1 2 1 1
算出*dp[0]之后，算*dp[1] = *dp[0] + dp[1] + dp[3] - dp[0] - dp[-2]
可以发现此时只要把[j+1,j+1+ai]的奇数位置的dp值加起来 - [j-ai,j]偶数位置的dp值 + *dp[0] = *dp[1]
转移变成O(1)的了。
假设ai = 3 j = 0, 那么dp[0] =
dp: dp[-3] dp[-2] dp[-1] dp[0] dp[1] dp[2] dp[3]
系数：1 1 2 2 2 1 1
同ai = 2相反。找规律即可。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define ll long long
int dp[],sum[][];
int mod = ;
int modx = -mod;
int num[];
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int total = ;
for(int i = ; i <= n; i++){
scanf("%d",&num[i]);
total += num[i];
}
if(total & ) total++;
memset(dp,,sizeof(dp));
memset(sum,,sizeof(sum));
dp[total] = ;
int tt = total*;
for(int i = ; i <= n; i++)
{
sum[][] = dp[];
sum[][] = ;
for(int j = ;j <= tt; j++)
{
sum[][j] = sum[][j-];
sum[][j] = sum[][j-];
sum[j&][j] += dp[j];
sum[j&][j] %= modx;
}
ll ans = ;
for(int j = ;j <= num[i]; j++){
ans += (ll)dp[j]*((num[i]-j)/+);
ans %= mod;
}
int p = (num[i]&)^;
int res = ans;
for(int j = ;j <= tt; j++)
{
dp[j] = res;
int u = j-num[i]-;
u = max(u,);
res += (sum[p][j++num[i]] - sum[p][j])%mod;
res %= mod;
p ^= ;
res -= (sum[p][j] - sum[p][u])%mod;
res %= mod;
}
}
int res = dp[total];
res %= mod;
res = (res+mod)%mod;
cout<<res<<endl;
}
return ;
}