51nod 1202 子序列个数（dp）

4
1
2
3
2

13

思路：每次添加一个新数，如果之前出来过，应该减去重复，若没出来过就等于 2*dp[i-1] + 1;重复出在这里，如果输入一个x ，前面已经有一个 x 了，那么若前一个x前面有dp[x-1]个序列，若两个x挨着，那么0x和x0重复（0表示没有）重复的个数就是上面的dp[x-1] + 1; 因为还有两个单个的x重复。

#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll dp[100005];
int mk[100005];
int main()
{ll n,x;cin >> n;for(int i = 1; i <= n; i++){cin >> x;int tmp = mk[x];if(tmp) dp[i] = (dp[i-1]*2 - dp[tmp-1] + mod) % mod;else dp[i] = (dp[i-1]*2+1) % mod;mk[x] = i;}cout << dp[n] << endl;return 0;
}