F. Copy or Prefix Sum

Venice technique簡要就是懶標(biāo)記思想。
由于前綴和數(shù)組和原數(shù)組一一對應(yīng)，這里我們選擇求$a_i$的前綴和數(shù)組的方案數(shù)（下面$a_i$表示原題數(shù)組的前綴和）

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

• $b_i=a_i?a_{i?1}\to a_i=b_i+a_{i?1}$
• $b_i=a_i\to a_i=b_i$

狀態(tài)表示：$f_{i,j}$考慮前$i$個數(shù)，所求數(shù)組第$i$個位置值是$j$的方案數(shù)。
答案即是：${\sum }_{j=?\infty }^{+\infty }{f}_{n,j}$

狀態(tài)轉(zhuǎn)移：

• $f_{i,j}=f_{i?1,j?b_i}$
• $f_{i,b_i}={\sum }_{j=?\infty }^{+\infty }{f}_{i?1,j}?(f_{i?1,0})$

$a_i=b_i+a_{i?1}$和$a_i=b_i$當(dāng)$a_{i?1}=0$時是同一種情況，因此需要把重復(fù)計算的去掉。

按照上述轉(zhuǎn)移方式肯定不可信，不難發(fā)現(xiàn)第一維可以用滾動數(shù)組優(yōu)化掉，注意第一個轉(zhuǎn)移式子，相當(dāng)于將整個數(shù)組平移$b_i$，這里采用的懶標(biāo)記的思想做一個下標(biāo)映射。

對于第一種轉(zhuǎn)移，維護(hù)一個add，$f_{i,j}=f_{i?1,j?b_i}=f_{i?1,j+add}$，如果每次讓add減去$b_i$就完成了對數(shù)組的平移操作也就是第一種轉(zhuǎn)移。

而下面一種轉(zhuǎn)移，只需要記住原來$b_i$的位置是$b_i+add$即可轉(zhuǎn)移

#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; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的codeforces1485 F. Copy or Prefix Sum（dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。