codeforces1485 F. Copy or Prefix Sum（dp）

F. Copy or Prefix Sum

Venice technique簡要就是懶標記思想，
由于前綴和陣列和原陣列一一對應，這里我們選擇求 a i a_i ai?的前綴和陣列的方案數（下面 a i a_i ai?表示原題陣列的前綴和）

不難得知原題目的兩個條件即

• b i = a i ? a i ? 1 → a i = b i + a i ? 1 b_i=a_i-a_{i-1} \to a_i=b_i+a_{i-1} bi?=ai??ai?1?→ai?=bi?+ai?1?
• b i = a i → a i = b i b_i=a_i \to a_i=b_i bi?=ai?→ai?=bi?

狀態表示： f i , j f_{i,j} fi,j?考慮前 i i i個數，所求陣列第 i i i個位置值是 j j j的方案數，
答案即是： ∑ j = ? ∞ + ∞ f n , j \sum_{j=-\infty}^{+\infty}f_{n,j} ∑j=?∞+∞?fn,j?

狀態轉移：

• f i , j = f i ? 1 , j ? b i f_{i,j}=f_{i-1,j-b_i} fi,j?=fi?1,j?bi??
• f i , b i = ∑ j = ? ∞ + ∞ f i ? 1 , j ? ( f i ? 1 , 0 ) f_{i,b_i}=\sum_{j=-\infty}^{+\infty}f_{i-1,j}-(f_{i-1,0}) fi,bi??=∑j=?∞+∞?fi?1,j??(fi?1,0?)

a i = b i + a i ? 1 a_i=b_i+a_{i-1} ai?=bi?+ai?1?和 a i = b i a_i=b_i ai?=bi?當 a i ? 1 = 0 a_{i-1}=0 ai?1?=0時是同一種情況，因此需要把重復計算的去掉，

按照上述轉移方式肯定不可信，不難發現第一維可以用滾動陣列優化掉，注意第一個轉移式子，相當于將整個陣列平移 b i b_i bi?，這里采用的懶標記的思想做一個下標映射，

對于第一種轉移，維護一個add， f i , j = f i ? 1 , j ? b i = f i ? 1 , j + a d d f_{i,j}=f_{i-1,j-b_i}=f_{i-1,j+add} fi,j?=fi?1,j?bi??=fi?1,j+add?，如果每次讓add減去 b i b_i bi?就完成了對陣列的平移操作也就是第一種轉移，

而下面一種轉移，只需要記住原來 b i b_i bi?的位置是 b i + a d d b_i+add bi?+add即可轉移

#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#pragma GCC optimize(2)
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long;
constexpr int N=100010;
constexpr ll mod=1e9+7;
int n;
map<ll,ll> dp;
int main()
{
    IO;
    int T=1;
    cin>>T;
    while(T--)
    {
        cin>>n;
        dp.clear();
        dp[0]=1;
        ll sum=1,add=0;
        for(int i=1;i<=n;i++)
        {
            ll b;cin>>b;
            ll pre=sum-dp[0+add]; pre=(pre%mod+mod)%mod;
            add-=b;
            sum+=pre; sum%=mod;
            dp[b+add]+=pre; dp[b+add]%=mod;
        }
        cout<<sum<<'\n';
    }
    return 0;
}