NKOJ 3792 分糖果（差值dp+前缀和优化）

发表于 |
字数统计: 700字 | 阅读时长 ≈ 3min

P3792分糖果

问题描述

有n种糖果（编号1到n）,第i号糖果有Ai颗，现需要将所有糖果分给两个小朋友，要求两个小朋友得到糖果数量相等，问有多少种分法？
（可以不必将所有糖果分完。如全部都不分，每人的糖果数量为0，也算是一种分法）

输入格式

第一行，一个整数n，表示糖果种类数量
第二行，n个空格间隔的整数，表示每种糖果的数量

输出格式

一行，一个整数，表示总的方案数，答案 mod 10^9+7后再输出。

样例输入 1

1
2

样例输出 1

2

样例输入 2

2
1 2

样例输出 2

4

提示

1<=n<=200
1<=Ai<=200

容易想到令$F[i][j][k]$表示分完第$i$中糖后，第一个小朋友有$j$颗糖，第二个小朋友有$k$颗糖的方案数。
再想发现，我们只关心他们分的糖是否相等，因此可以简化成令$F[i][j]$表示分完第$i$中糖，两人分的糖果的差值为$j$
那么,$F[i][j]=\sum F[i-1][j-k]*((A[i]-k)/2+1)$，这个递推式的复杂度是$O(n^4)$，我们需要优化
考虑$F[i][j]-F[i][j-1]$，讨论$A[i]$的奇偶，观察可以发现$F[i][j]$关于$F[i][j-1]$的递推式，这个式子可以前缀和优化。于是复杂度就降到了$O(n^3)$，鉴于递推式比较冗长，这里就不写了。
实际做的时候只需要取比较小的$A[i]$把$F[i][j]-F[i][j-1]$展开，观察一下就可以发现关于奇偶性的规律。
代码比较恶心，前缀和需要根据奇偶分开。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<stdio.h>
#include<iostream>
#include<algorithm>
#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;
}