可以看出本题可以使用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;
}