codeforces1485 F. Copy or Prefix Sum(dp)

F. Copy or Prefix Sum

Venice technique 간략함은 게으름 표기 사상이다.접두사와 수조가 원수조와 일일이 대응하기 때문에 여기서 우리는 ai 를 선택합니다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는 전 ii 개수를 고려하고 구한 수조 ii 개 위치값은 jj의 방안수입니다.정답: ∑j=-3-∞+∞fn,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 -3 - 1과 a i = b i ai=b_i ai = bi da a i -3 - 1 = 0 a{i-1}=0 ai -3.1=0은 같은 상황이기 때문에 중복 계산을 제거해야 한다.
상술한 전이 방식에 따라 틀림없이 믿을 수 없을 것이다. 1차는 스크롤 수조로 최적화할 수 있음을 발견하기 어렵지 않다. 첫 번째 전이 식에 주의하면 전체 수조를 bib 로 평이하게 이동하는 것과 같다.ibi, 여기서 채택한 게으름 표기 사상은 아래 표시를 한다.
첫 번째 이동에 대해dd,fi,j=fi-3-1,j-3bi=fi-3-1,j+ad df 유지 보수{i,j}=f_{i-1,j-b_i}=f_{i-1, j+add} fi, j=fi -3 1, j -3 bi =fi -3 1, j+add, 매번add에서 bi b 를 빼면ibi는 수조에 대한 평이 조작, 즉 첫 번째 이동을 완성했다.
다음 중 하나는 원래 bi b 를 기억하기만 하면 된다i bi의 위치는 b i + a d bi+add bi+add 로 이동 가능

#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#pragma GCC optimize(2)
#include
#include
#include
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<<'
';
    }
    return 0;
}