[计数问题dp]子数列的个数

http://www.51nod.com/tutorial/course.html#!courseId=15

解题关键：主要是一种思想

　　　　$dp[i] = dp[i - 1]*2$ 如果a[i]不在之前出现
　　　　$dp[i] = dp[i - 1]*2 - dp[j - 1]$，如果a[i]最近在j的位置出现过。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll mod=1e9+7; 
 5 ll a[100002],have[100002],dp[100002];//have存的是位置 
 6 int main(){
 7     int n;
 8     cin>>n;
 9     for(int i=1;i<=n;i++){
10         cin>>a[i];
11     } //注意要从1开始读 
12     dp[0]=1;
13     for(int i=1;i<=n;i++){
14         dp[i]=dp[i-1]*2%mod;
15         if(have[a[i]]>0) dp[i]=(dp[i]-dp[have[a[i]]-1]+mod)%mod;
16         have[a[i]]=i;
17     }
18     printf("%lld
",(dp[n]-1+mod)%mod);
19 }