FZU 2129 子序列个数

题目链接：子序列个数

思路：使用一个数组(map超时了)记录一个数字在之前出现的位置，然后状态转移方程有两个，如果一个数字在之前出现过：dp[i] = (dp[i - 1] * 2 - dp[index[temp] - 1] + MOD) % MOD;，如果没有出现过：dp[i] = (dp[i - 1] * 2 + 1) % MOD;，这里注意减法取余需要加上MOD，否则可能出现负数。

dp这种东西，看比想容易的多了...23333我看懂了.....

#include <stdio.h>
#include <string.h>
#include <iostream>
#define mod 1000000007
using namespace std;

int index[1000010];
long long dp[1000010];

int main() {
    int n;
    while(~scanf("%d", &n)) {
        memset(index, -1, sizeof(index));
        memset(dp, 0, sizeof(dp));
        dp[1] = 1;
        int temp;
        scanf("%d", &temp);
        index[temp] = 1;
        for (int i=2; i<=n; ++i) {
            scanf("%d", &temp);
            if (index[temp] == -1) {
                dp[i] = (((dp[i-1]%mod)*2)%mod+1)%mod;
            }
            else {
                dp[i] = (((dp[i-1]%mod)*2)%mod-dp[index[temp]-1]+mod)%mod;
            }
            index[temp] = i;
        }
        printf("%d
", dp[n]);
    }
    return 0;
}