题目链接: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; }