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;
}