本篇不适合当题解看

水位线技术

我们先利用推导dp公式，注意：这里因为dp公式的特殊性我们决定从前向后主动更新(类似dij)
然后我们会注意到这个dp很是特殊，她似乎整体都上升一个相同的数。
我们可以利用水位线思想：
我们不要一个个地上升数，我们下降水位线不就好了吗？
然后单独处理一些特殊的点。
如此，复杂度直接降低了一个维度

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int max_n = 2e5+100;
const ll mod = 1e9+7;
ll b[max_n];
int n;
ll Solve(){
    cin>>n;
    map<ll,ll> dp;
    for (int i=1;i<=n;++i)cin>>b[i];
    dp[b[1]]=1;
    ll lazy = 0,sum = 1;
    for (int i=1;i<n;++i){
        lazy-=b[i+1];
        ll ex = dp[b[i+1]+lazy];
        dp[b[i+1]+lazy]=sum;
        sum = (2*sum%mod-ex+mod)%mod;
    }
    return sum;
}
int main(){
    ios::sync_with_stdio(0);
    int t;cin>>t;
    while (t--)cout<<Solve()<<endl;
}