子序列个数（不要求连续子序列、重复的子序列不重复计算【dp+双指针】）

子序列个数（不要求连续子序列、重复的子序列不重复计算）

输入样例

4
1
2
3
2

输出样例

13

要时刻谨记，不是序列中不含重复元素，而是序列不能重复，即两个相同元素不要出现在序列中同一位置，却当作两种结果
比如 a[j]==a[i], a[1~j-1], a[j], a[i+1] 和 a[1~j-1], a[i], a[i+1] 不要当作两个子序列

如果不存在重复的元素，当然不存在以上情况 直接一个公式就能输出结果

举个例子更好理解题意

对于第一个3会有 1 3 ，2 3，3 ，但是在尽可能多组合子序列不考虑重复子序列
的假设下 对与第二个3，同时会有 会有 1 3 ，2 3，3 ，因此需要减去重复的

如果不存在重复的数，那么dp[i]=dp[i-1]*2（含空集的情况）。
现在考虑出现了重复的数。比如当前要取的数为a[i]，且a[i]最近一次在之前的j位置出现过了。那么有dp[i]=dp[i-1]*2-dp[j-1]。所以我们利用一个数组mark记录下a[i]出现的位置就好了，没有出现过为0。

#include<bits/stdc++.h>
using namespace std;
#define int long long int
int n;
const int N=1e5+10;
const int mod=1e9+7;
int dp[N];//a[1~i]这一段能产生多少子序列
map<int,int> mp;
int a[N];
signed main(){
	cin>>n;

	dp[0]=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i]=dp[i-1]<<1;//【1，i-1】产生的每个子序列分别再和a[i]组合
		dp[i]%=mod;
		if(mp.count(a[i])){
			int j=mp[a[i]];
			dp[i]=(dp[i]-dp[j-1]+mod)%mod;
			//a[j]==a[i], a[j]和[1,j-1]组合了dp[j-1]个子序列
//			(dp[j]子序列包括[1,j-1]自身组合的dp[j-1]个子序列和搭配a[j]组成的
		}
		mp[a[i]]=i;
	}
	cout<<dp[n]-1;//减去空集
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long int
int n;
const int N=1e5+10;
const int mod=1e9+7;
int dp[N];//以a[i]结尾的子序列  
//a[1~i-1]组成的所有字符串个数(此时的sum) 
//分别和a[i]搭配  再加上s[i]本身(和空集搭配)

int a[N];
signed main(){
	cin>>n;

	dp[0]=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];	
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		int pre=dp[a[i]];//以上一个a[i]结尾的子序列个数
		dp[a[i]]=(sum+1+mod)%mod;//假设没有重复的元素，即可以再多产生dp[a[i]]个子序列
		sum=(sum+dp[a[i]])%mod;
		
		sum=(sum-pre+mod)%mod;//有重复的元素，pre就不为0， 1 2 3 4 5 3
//		对于第一个3会有 1 3 ，2 3，3 ，但是在尽可能多组合子序列不考虑重复子序列
//		的假设下 对与第2个3，同时会有 会有 1 3 ，2 3，3 ，因此需要减去重复的
		
//		谨记题意， 3 3是新的子序列，ok的
	}
	cout<<sum;
	return 0;
}