题意：子序列的定义：对于一个序列a=a[1],a[2],......a[n]。则非空序列a'=a[p1],a[p2]......a[pm]为a的一个子序列，其中1<=p1<p2<.....<pm<=n。

例如4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子序列。

对于给出序列a，请输出不同的子序列的个数。(由于答案比较大，请将答案mod 1000000007)

思路：设前i个数字的子序列数为f(i)。

           1.如果第i个数字在前i个数字里都没有出现过，那么，原来i-1个数字里面的子序列也是前i个数字的子序列，总共是f(i-1)，而在原来i-1个数字的子序列每个的背后加一个a[i]也是新的子序列，总共是f(i-1)个，然后最后一个数字单独也可以组成一个新的子序列，是1个，因此这时f(i)=f(i)+f(i)+1。

           2.如果第i歌数字在前面i个数字里面出现过，那么f(i)=f(i)+f(i)-f(a[i]最后一次出现的位置-1)。因为这时候，单独一个a[i]的情况已经被计算过，于是没有了+1，而往a[i]最后一次出现的位置-1加上一个a[i]的情况也已经被计算过，一次要减掉。

注意：遇到减号的时候取模时要加MOD再取模。

 

#include
     
      #include
      
       #define MOD 1000000007#define MAXN 1000005typedef long long LL;LL f[MAXN];int last[MAXN],a,n;int main(){	while(~scanf("%d",&n))	{		memset(last,0,sizeof(last));		f[0]=0;		for(int i=1;i<=n;++i)		{            scanf("%d",&a);			f[i]=(f[i-1]<<1)%MOD;			if(!last[a]) last[a]=i,f[i]++;			else f[i]=(f[i]-f[last[a]-1]+MOD)%MOD,last[a]=i;		}		printf("%I64d\n",f[n]%MOD);	}	return 0;}