51nod 1202 子序列个数

题目链接  https://www.51nod.com/Challenge/Problem.html#!#problemId=1202

思路：我们一个串的子序列个数  如果不考虑重复 显而易得是2的n次方（包含空集）

那么我们的dp递推公式就很好推了

当这个数字原来没有出现的时候 dp[i] = dp[i - 1] * 2；

当这个原来出现的时候我门序要减去多加的部分就是原来以这个数字结尾的子序列,

假设原来这个数字出现的位置是j，那么递推公式是

dp[i] = dp[i - 1] * 2 - dp[j - 1];

代码如下

#include <bits/stdc++.h>
#define gcd __gcd
#define endl '\n'
typedef long long ll;
typedef long double ld;
  
using namespace std;
  
const ll maxn = 1e6 + 7;
const ll mod = 1e9 + 7;

ll a[maxn];
ll dp[maxn],vis[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    
    ll n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
    	cin >> a[i];
	}
	
	dp[0] = 1;
	for(int i = 1; i <= n; i ++)
	{
		if(vis[a[i]])dp[i] = (dp[i - 1] * 2 % mod - dp[vis[a[i]] - 1] % mod + mod) % mod;
		else dp[i] = dp[i - 1] * 2 % mod;
		vis[a[i]] = i;
	}
	
	cout << dp[n] - 1 << endl;
	
	return 0;
}