FZU 2129 子序列个数（DP）题解

题意：求子序列种数

思路：dp[i]代表到i的所有种数，把当前i放到末尾，那么转移方程dp[i] = dp[i – 1] + dp[i -1]，但是可能存在重复，比如1 2 3 2，在第2位置的时候出现12，但是在第4位置的时候，还是可能出现12，那么我们要减掉多出来的，就是减去dp[1]这里加2的部分。也就是减去相同数字的前一个的种数。

代码：

#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 5;
const int M = 50 + 5;
const ull seed = 131;
const int INF = 0x3f3f3f3f;
const ll MOD = 1000000007;
ll dp[maxn];
int a[maxn], pre[maxn];
int main(){
    int n;
    while(~scanf("%d", &n)){
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        dp[0] = 1;
        memset(pre, 0, sizeof(pre));
        for(int i = 1; i <= n; i++){
            dp[i] = (dp[i - 1] * 2) % MOD;
            if(pre[a[i]] != 0){
                dp[i] = (dp[i] - dp[pre[a[i]] - 1] + MOD) % MOD;
            }
            pre[a[i]] = i;
        }
        printf("%lld\n", dp[n] - 1);
    }
    return 0;
}