子序列的定義：對于一個序列a=a[1],a[2],…a[n]。則非空序列a’=a[p1],a[p2]…a[pm]為a的一個子序列，其中1<=p1<p2<…<pm<=n。
例如4,14,2,3和14,1,2,3都為4,13,14,1,2,3的子序列。對于給出序列a，有些子序列可能是相同的，這裡隻算做1個，請輸出a的不同子序列的數量。由于答案比較大，輸出Mod 10^9 + 7的結果即可。
輸入
第1行：一個數N，表示序列的長度(1 <= N <= 100000)
第2 - N + 1行：序列中的元素(1 <= a[i] <= 100000)
輸出
輸出a的不同子序列的數量Mod 10^9 + 7。
輸入樣例
4
1
2
3
2
輸出樣例
13
我們知道如果不存在重複的數，那麼dp[i]=dp[i-1]*2（含空集的情況）。現在考慮出現了重複的數。比如目前要取的數為a[i]，且a[i]最近一次在之前的j位置出現過了。那麼有dp[i]=dp[i-1]*2-dp[j-1]。是以我們利用一個數組mark記錄下a[i]出現的位置就好了，沒有出現過為0。
假設子序列的前k個數的子序列個數為d(k)，那麼前k - 1個子序列的個數就為d(k - 1)個子序列，從k - 1 到k的變化是怎樣的呢？
1、假設數組a[N]第k個數為a[k]，如果a[k] 與前面的k - 1個數都不相同，那麼就有 : d(k) = d(k - 1) + 【d(k - 1) + 1】 = 2d(k - 1) + 1，為什麼呢？可以這樣想，對于前k- 1項的子序列個數為d(k - 1)，那前k個數，無非就是在前k - 1項的基礎上多加了一個數a[k]（a[k]與前k - 1個數任意一個都相等），那就在原來的組合上加上a[k]，就有d(k - 1)個，還有一個a[k]自己構成一個子序列，是以還要加1；
2、假設a[k] 與前面的k - 1個數其中一個相等，那依舊加上前k - 1個子序列個數 d(k - 1)，但是由于前面有與a[k]相等的數，是以要減掉重複的部分，如何找到重複的部分呢，假設離k最近的一個與a[k]相等的數為第t個a[t] = a[k]，即序列(a[1], a[2], ……,a[t],……,a[k - 1],a[k])，a[t] = a[k]；我們已經知道序列(a[1], a[2], ……,a[t])的序列個數為d(t)，那麼d(t - 1)就是重複的部分，這裡需要自己做好思考，也是算法的關鍵部分，這裡我要解釋的地方是，為什麼隻需要找到離k最近的t使得a[t] = a[k]？給出的解釋是：我們是從1 - n對數組進行周遊的，計算d(i)的i就是從1到n依次計算的，那麼第一次遇到a[k] = a[t]的情況滿足條件：有且僅有一個t使得a[t] = a[k]，比如序列(1, 2, 3, 2, 4, 2)，分别計算d(1),d(2),d(3),d(4),d(5),d(6)；我們在計算d(4)的時候發現a[4] = a[2]（假設下标從1開始），是以d(4) = 2*d(3) - d(2 -1) = 2d(3) - d(1)；當計算d(6)的時候也有a[6] = a[4] = a[2]，但是由于我們前面已經把a[2]重複的部分減掉了，是以不需要再減，d(6) = 2 * d(5) - d(4 - 1) = 2d(5) - d(3).
過程繁瑣，我總結一下結論：
狀态轉移方程為：
d(k) = 2 * d(k - 1) + 1; a[k] != a[i]，i = 1,2,3……k - 1;
d(k) = 2 * d(k - 1) - d(t - 1); 從k往前搜尋，存在離k最近的t，使得a[t] = a[k].
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 5;
int a[maxn], dp[maxn], mark[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if (mark[a[i]]) {
dp[i] = 2 * dp[i - 1] - dp[mark[a[i]] - 1];
dp[i] = (dp[i] % mod + mod) % mod;
} else {
dp[i] = 2 * dp[i - 1] % mod;
}
mark[a[i]] = i;
}
cout << ((dp[n] - 1) % mod + mod) % mod << endl;
return 0;
}