看到a[i]<=100000觉得应该从这个方面搞。
如果a[x]没出现过,f[x]=f[x-1]*2;否则f[x]=f[x-1]*2-f[pos[a[x]]-1];ans=f[n]-1,然后WA了 ？
修改了一下f[x]=f[x-1]*2+1 否则f[x]=f[x-1]*2-f[pos[a[x]]-1];ans=f[n];
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
int read(){
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();
return x;
}
const int nmax=1e5+5;
const int mod=1e9+7;
int a[nmax],dp[nmax];
int main(){
int n=read(),u,v,d;dp[1]=1;a[u=read()]=1;
rep(i,2,n){
u=read();
if(!a[u]) dp[i]=(dp[i-1]*2%mod+1)%mod;
else dp[i]=(dp[i-1]*2%mod-dp[a[u]-1]+mod)%mod;
a[u]=i;
}
printf("%d\n",dp[n]);
return 0;
}
收藏
关注第1行：一个数N，表示序列的长度(1 <= N <= 100000) 第2 - N + 1行：序列中的元素(1 <= a[i] <= 100000)
输出a的不同子序列的数量Mod 10^9 + 7。
4 1 2 3 2
13
原文：http://www.cnblogs.com/fighting-to-the-end/p/5873121.html
