子序列个数
发布日期:2022-02-02 02:58:04
浏览次数:12
分类:技术文章
本文共 1115 字,大约阅读时间需要 3 分钟。
Problem Description
子序列的定义:对于一个序列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)
Input
输入包含多组数据。每组数据第一行为一个整数n(1<=n<=1,000,000),表示序列元素的个数。
第二行包含n个整数a[i] (0<=a[i]<=1,000,000)表示序列中每个元素。
Output
输出一个整数占一行,为所求的不同子序列的个数。由于答案比较大,请将答案mod 1000000007。
Sample Input
41 2 3 2
Sample Output
13
代码:
#include#include #define N 1000005#define mod 1000000007#define ll long longusing namespace std;int a[N],b[N];ll dp[N];int main(){ int n; while(cin>>n) { int max=-1; for(int i=1; i<=n; i++) { cin>>a[i]; if(a[i]>max) max=a[i]; } for(int i=0; i<=max; i++) b[i]=-1; b[a[1]]=1; dp[1]=1; for(int i=2; i<=n; i++) { if(b[a[i]]==-1) { dp[i]=(2*dp[i-1]+1)%mod; } else { dp[i]=(2*dp[i-1]-dp[b[a[i]]-1]+mod)%mod;//如出现负值,处理 } b[a[i]]=i; } cout< <
转载地址:https://blog.csdn.net/u010368749/article/details/13339785 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年03月28日 18时16分19秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
草蟒 Python 中文 API 与 IDE 支持尝鲜
2019-04-26
一种改进中文 API 可读性的方法:参数不限于在末尾
2019-04-26
中文编程开发工具的生存模式探讨
2019-04-26
写给木兰编程语言研发团队的公开信
2019-04-26
为什么要急着为「木兰」编程语言贴上“造假”的标签?
2019-04-26
编程语言国产化的关键一战——对肆意污名化“木兰”编程语言说“不”
2019-04-26
各大媒体对「木兰」编程语言的不当言论盘点
2019-04-26
戳破针对「木兰」编程语言的拙劣谣言
2019-04-26
为「木兰」编程语言添加对中文命名标识符的支持
2019-04-26
悬赏万元,重现「木兰」编程语言编译器
2019-04-26
跳出编程语言本身看中文编程语言设计
2019-04-26
RPLY 入门例程中文化
2019-04-26
木兰编程语言入门教程之一——浅介
2019-04-26
木兰编程语言入门教程之二——控制走向
2019-04-26
基于「木兰」编译器,加十行代码实现 ∈ (属于集合)语法
2019-04-26
创建安卓键盘演示——“好不”
2019-04-26
木兰编程语言入门教程之三——函数和类型
2019-04-26
基于「木兰」逆向工程用 pyinstaller 生成可执行文件
2019-04-26
从微盟事件看商业数据公开化的必然趋势
2019-04-26
为新语言编写Visual Studio Code语法高亮插件
2019-04-26