题意：
子序列的定义：对于一个序列\(a=a[1],a[2], \cdots ,a[n]\)。则非空序列\(a'=a[p_1],a[p_2],\cdots,a[p_m]\)为a的一个子序列，其中\(1<=p_1<p_2<\cdots<p_m<=n\)。 例如4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子序列。对于给出序列a，有些子序列可能是相同的，这里只算做1个，请输出a的不同子序列的数量。由于答案比较大，输出\(mod 10^9 + 7\)的结果即可。
思路：
参考资料
假设子序列的前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)=2*d_{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],\cdots,a[t],\cdots,a[k-1],a[k])，a[t]==a[k]\)；我们已经知道序列\((a[1],a[2],\cdots,a[t])\)的序列个数为\(d_t\)，那么\(d_{t 1}\)就是重复的部分，这里需要自己做好思考，也是算法的关键部分，这里我要解释的地方是，为什么只需要找到离k最近的t使得\(a[t]=a[k]\)？给出的解释是：我们是从\(1\cdots 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}=2*d_3-d_1\)；当计算\(d_6\)的时候也有\(a[6]=a[4]=a[2]\)，但是由于我们前面已经把a[2]重复的部分减掉了，所以不需要再减，\(d_6=2*d_5-d_{4-1}=2*d_5-d_3\).
状态转移方程为：
\(d_k=2*d_{k-1}+1; \quad \quad a[k]!=a[i]，i=1,2,3,\cdots,k-1;\)
\(d_k=2*d_{k-1}-d_{t-1};\quad\) 从k往前存在离k最近的t，使得\(a[t]=a[k]\).
设数组ap记录每个数字最近出现的位置，利用上面的方程即可求解，注意在第二个方程要加上MOD再求余，因为有可能出现负数。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define FILEREAD freopen("input.txt", "r", stdin);
const int INF = 0x3f3f3f3f;
const int N = 100001;
const int MOD = 1e9 + 7;
int a[N], ap[N];
long long dp[N];
int main()
{
#ifndef ONLINE_JUDGE
FILEREAD
#endif
FIO
int n;
cin >> n;
for (int i{1}; i <= n; ++i)
cin >> a[i];
for (int i{1}; i <= n; ++i)
{
if (ap[a[i]] == 0)
{
dp[i] = (dp[i - 1] * 2 + 1) % MOD;
ap[a[i]] = i;
}
else
{
dp[i] = (dp[i - 1] * 2 - dp[ap[a[i]] - 1] + MOD) % MOD;
ap[a[i]] = i;
}
}
cout << dp[n] << endl;
return 0;
}