本篇不适合当题解看
水位线技术
我们先利用推导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; }