题目链接：1202
转自：51nod 教程
假设dp[i]表示前i项形成的子序列（含空）的个数。下标从1开始，初值是dp[0] = 1，对应代表空子序列。
我们考虑第i项，如果所有的数都不相等，应该有dp[i] = dp[i – 1] * 2，其实就是考虑把第i个数放到最后或者不放到最后的情况。
因为有可能有相同的数，我们假设第i个数出现之前最近的在j (j < i)位置也出现过，那么实际上我们这种简单＊2会有重复，哪些子序列重复呢？
我们设数列为a, 并且下标从1开始。原来恰好以第j个数结尾的那些被我们算了两次，因为以第j个数结尾可以换成以第i个数结尾是一样的。
如何计算出这个数的个数呢？ 其实这个数等于dp[j – 1]，因为前面(j – 1)个数的子序列最后跟上第j个数就可以了。
所以递推公式就为：
dp[i] = dp[i – 1] * 2 如果a[i]不在之前出现 dp[i] = dp[i – 1] * 2 – dp[j – 1]，如果a[i]最近在j的位置出现过。
注意取余---
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long mod=1000000007,dp[100100],shu[100100],yi[100100]; int main() { int n;scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&shu[i]); memset(yi,0,sizeof(yi)); dp[0]=1; for (int i=1;i<=n;i++) if (yi[shu[i]]) { dp[i]=(dp[i-1]*2-dp[yi[shu[i]]-1])%mod; yi[shu[i]]=i; } else { dp[i]=(dp[i-1]*2)%mod; yi[shu[i]]=i; } printf("%d\n",(dp[n]+mod-1)%mod); return 0; }