思路：
- 可以想到，结果每个位置由两种可能的值，所以理想结果应该是 2 n − 1 2^{n-1} 2n−1。但是不一定，原因是 ∑ 1 i − 1 a i = 0 ∑^{i-1}_1a_i=0 ∑1i−1ai=0，导致两种取法得到的结果一样。所以我们得用动态规划的方法去重。
- 直观的动态规划思路肯定是 d p [ i ] [ j ] dp[i][j] dp[i][j]代表前缀 i i i，前缀和为 j j j时候能得到的 h y b r i d hybrid hybrid数组数目。转移就是 d p [ i ] [ j ] + = d p [ i − 1 ] [ j − b [ i ] ] , d p [ i ] [ b [ i ] ] + = d p [ i ] [ j ] dp[i][j]+=dp[i-1][j-b[i]],dp[i][b[i]]+=dp[i][j] dp[i][j]+=dp[i−1][j−b[i]],dp[i][b[i]]+=dp[i][j]，不过很明显这样转移复杂度较高。我们考虑怎么通过动态规划求出重复的部分。
- 定义 D P [ i ] DP[i] DP[i]为对于长度为 i i i的前缀存在多少个 h y b r i d hybrid hybrid数组， d p [ i ] [ j ] dp[i][j] dp[i][j]为长度为 i i i前缀中，满足 ∑ x = 1 i ( a x − b x ) = j ∑^i_{x=1}(a_x-b_x)=j ∑x=1i(ax−bx)=j的方案数为 d p [ i ] [ j ] dp[i][j] dp[i][j]。当 b [ i ] = a [ i ] b[i]=a[i] b[i]=a[i]时， d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j]=dp[i-1][j] dp[i][j]=dp[i−1][j]，当 b [ i ] = a [ i ] − ∑ x = 1 i − 1 a x b[i]=a[i]-∑^{i-1}_{x=1}a_x b[i]=a[i]−∑x=1i−1ax时， d p [ i ] [ ∑ x i − 1 ( − b x ) ] = D P [ i − 1 ] dp[i][∑^{i-1}_x(-b_x)]=DP[i-1] dp[i][∑xi−1(−bx)]=DP[i−1]。因为只有一次转移，其他部分都是直接继承，使用 m a p map map则可以 n l o g ( n ) nlog(n) nlog(n)的维护出 d p dp dp数组。
- 注意到，当长度 i i i的前缀和为 ∑ x i − 1 ( − b x ) ∑^{i-1}_x(-b_x) ∑xi−1(−bx)时，可以得到此时 ∑ x i − 1 ( a x ) = 0 ∑^{i-1}_x(a_x)=0 ∑xi−1(ax)=0，所以这就等于我们第一点中说的重复取值的部分。设 s u m = ∑ x i − 1 ( − b x ) sum=∑^{i-1}_x(-b_x) sum=∑xi−1(−bx)，则 D P [ i ] = D P [ i − 1 ] ∗ 2 − d p [ i − 1 ] [ s u m ] DP[i]=DP[i-1]*2-dp[i-1][sum] DP[i]=DP[i−1]∗2−dp[i−1][sum]，这就维护出了 D P DP DP数组。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;
typedef long long ll;
map<ll,ll>mp;
ll a[maxn];
int main() {
int T;scanf("%d",&T);
while(T--) {
int n;scanf("%d",&n);
for(int i = 1;i <= n;i++) {
scanf("%lld",&a[i]);
a[i] += a[i - 1];
}
mp.clear();
mp[0] = 1;
ll ans = 1;
for(int i = 1;i <= n;i++) {
ll tmp = mp[-a[i - 1]];
mp[-a[i - 1]] = ans;
ans = (ans * 2 - tmp) % mod;
if(ans < 0) ans += mod;
}
printf("%lld\n",ans);
}
return 0;
}