这道题的分析方法我很需要学习学习。
一开始我想的是f[i][j]表示前i个数子序列长度为j的个数
然后发现新加入一个数的时候会和前面的重复，这个时候不知道该怎么处理这种重复。
其实我再继续往下想就可以想到，这些重复的序列都有一个特征，结尾都是新加入的这个数
那么这就启示我们可以利用前面算出的结果来算出这个值而舍去
然后题解的分析是这样。
先考虑暴力该怎么做，然后再想怎么优化
暴力的话显然是枚举每一位去或者不取，然后去重复。不算去重的话时间复杂度为2^n
然后我们尝试用动态的思想来优化，最后的答案可以从前面的哪个状态推过来？
我们看最后一位取或者不取，前面是2^(n-1)，这一位取或者不取两种情况，乘以2
就是2^n
那么我们可以尝试设一下f[i]表示前i项子序列的长度
那么有f[i] = f[i-1] * 2
但是很显然怎么去重复是个很大的问题。
重复的子序列的结尾一定是当前的这个数
那么以当前这个数为结尾的子序列为多少呢？
根据定义可以得知为f[j-1]，j为前i-1项里面当前项a[i]最后一次出现的位置
因为j前面的所有子序列加上一个j就是以当前这个数为结尾的个数
如果j不存在，那么就不用减去。
要注意这里j是最后一个，因为后面的位置包含了前面的位置的结果。
最后要注意f[0] = 1，这样方便我们来更新值，同时最后输出答案的时候减去1
以后学习动规的时候看题解一定要看是怎么推出来的，自己为什么没想到
#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112345;
const int MOD = 1e9 + 7;
int a[MAXN], f[MAXN], path[MAXN], n;int main()
{scanf("%d", &n);REP(i, 1, n + 1) scanf("%d", &a[i]);f[0] = 1;REP(i, 1, n + 1){f[i] = (f[i-1] << 1) % MOD;if(path[a[i]] > 0) f[i] = (f[i] - f[path[a[i]] - 1] + MOD) % MOD;path[a[i]] = i;}printf("%d\n", f[n] - 1);return 0;
}