Sol.CF383D

可以看出本题可以使用DP。

可将前 \(i\) 个和为 \(j\) 的方案数表示为 \(f_{i,j}\) ,则每次状态转移需要考虑减 \(a_i\) 或加 \(a_i\)。

显而易见状态转移方程如下:

\(f_{i,j}=f_{i,j}+f_{i-1,j \pm a_i}\)

由于可能有负数，则需要平移。

具体代码如下:

#include<iostream>
using namespace std;
const int M=1000000007;
int n,m,f[1005][20005],ans;
int a[500005];
int main() {
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
		f[i][10000+a[i]]++;
		f[i][10000-a[i]]++;
        for (int j=0;j<=20000;j++){
			if(j-a[i]>=0){
				f[i][j]=(f[i][j]+f[i-1][j-a[i]])%M;
            }
            if(j+a[i]<=20000){
            	f[i][j]=(f[i][j]+f[i-1][j+a[i]])%M;
			}
        }
	}
    for(int i=1;i<=n;i++)ans=(ans+dp[i][10000])%M;
    printf("%d\n",ans);
    return 0;
}