首页 > 代码库 > 51nod1202 子序列个数
51nod1202 子序列个数
看到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;}
1202 子序列个数
题目来源： 福州大学 OJ
基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
收藏
关注子序列的定义：对于一个序列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，有些子序列可能是相同的，这里只算做1个，请输出a的不同子序列的数量。由于答案比较大，输出Mod 10^9 + 7的结果即可。
Input
第1行：一个数N，表示序列的长度(1 <= N <= 100000)第2 - N + 1行：序列中的元素(1 <= a[i] <= 100000)
Output
输出a的不同子序列的数量Mod 10^9 + 7。
Input示例
41232
Output示例
13
51nod1202 子序列个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。