题目描述：
芷萱姐姐有一个长度为 \(N\) 的数列 \(A_i\)。
你可以进行若干次，最多 \(N-1\) 次操作，选择相邻的两个数，删去他们，并在原位置放上他们两个的和。
现在你需要求出可能产生的序列个数。
数据范围：
- \(1 \le N \le 2 \times 10^5\)
- \(|A_i| \le 10^9\)
思路：
我们首先会发现一件事情，整个操作都是在总和不变的前提下进行的。
对于一个排列 a,b,c,d，合并 b,c 后就变成了 a,b+c,d，前缀和数组由 a,a+b,a+b+c,a+b+c+d 变为了 a,a+b+c,a+b+c+d
所以我们不难发现这个合并操作其实就是删掉前缀和数组中的一项。所以原题转换为：从数组中删掉一些数后，不同的序列个数。
即前缀和数组中不同的子序列个数。
转换完问题，考虑怎么求解这个问题。令 \(dp_i\) 表示到 \(1\sim i\) 的不同子序列个数。
首先肯定 \(dp_{i-1}\to dp_i\) ，然后我们发现，如果确定了 \(dp_{i-1}\) 中的子序列，则会有两种方式：
- 将 \(a_i\) 拼接到 \(dp_{i-1}\) 的序列后面
- 保持 \(dp_{i-1}\) 的序列不变
然后我们发现一件事情，如果记 \(1\sim i-1\) 中 \(a_i\) 出现的位置为 \(lst_{a_i}\)，则如果用 \(a_i\) 和 \(dp_{lst_{a_i}-1}\) 进行拼接的时候，和 \(dp_{lst_{a_i}-1}\to dp_{lst_{a_i}}\) 的拼接方式一样，所以重复的需要减掉。
这样可以列出转移方程：
\(dp_i=\left\{ \begin{aligned} &2\times dp_{i-1}+1 & & lst_{a_i}=0\cr &2\times dp_{i-1}-dp_{lst_{a_i}} & & lst_{a_i}\neq 0 \end{aligned} \right.\)
然后就是代码了
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+5;
const int mod=1e9+7;
int lst[maxn];
int n,a[maxn],b[maxn];
int dp[maxn];
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1],b[i]=a[i];
sort(b+1,b+n+1);
int m=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+m+1,a[i])-b;
dp[1]=1;
lst[a[1]]=1;
for(int i=2;i<=n;i++){
if(!lst[a[i]]){
dp[i]=(dp[i-1]*2%mod+1)%mod;
}
else{
dp[i]=(dp[i-1]*2%mod-dp[lst[a[i]]-1]+mod)%mod;
}
lst[a[i]]=i;
}
cout<<(dp[n-1]+1)%mod<<endl;
return 0;
}