上海计算机学会2022年1月月赛C++乙组T1相等子序列
发布时间
阅读量：
阅读量
相等子序列
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个序列 a1,a2,⋯,an，请计算它有多少种不同的相等子序列。由于答案可能很大，输出方案数量模 1,000,000,007 的余数。
子序列是指从原序列中去除部分数字组成的序列（且留下的数字应保持原序列的顺序），空集不算子序列，原序列本身算是自身的一种子序列。
两个子序列相等，是指他们的长度相同，且对应的每一个数字都相等。比如对于序列 1,2,1,2,3 来说，第一个 1,21,2 与 第二个 1,2 就是相等的子序列。
输入格式
第一行：单个整数 n，代表序列长度
第二行：n 个整数 ，代表 a1 到 an
输出格式
单个整数：表示不相等子序列的数量模 10^9+7 的余数。
数据范围
- 对于 30% 的数据，保证 1≤n≤15；
- 对于 50% 的数据，保证 1≤n≤10^3；
- 对于 100% 的数据，保证 1≤n≤10^6；
- 1≤ai≤10^6
样例数据
输入:
4
1 2 3 2
输出:
13
解析：递推法，
如果当前数之前没有出现过，那么前边的所有子序列都可以加上当前数，组成新的子序列，加上原来的子序列数量，即为原来子序列数量的2倍；
如果当前数之前出现过，那么以之前以当前数结尾的子序列会重复，去掉即可。
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[1000005];
int p[1000005];//数字i上次出现的位置
int dp[1000005];//前i个数字不同子序列的数量
int mod=1e9+7;
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[0]=1;
for(int i=1;i<=n;i++){
//如果当前数字之前没有出现过，之前的所有子序列都可以加上当前数，即2倍
if (p[a[i]]==0){
dp[i]=dp[i-1]*2%mod;
}else{//如果之前出现过
//之前出现位置之前的都重复，减掉dp[p[a[i]]-1]
dp[i]=((dp[i-1]*2%mod-dp[p[a[i]]-1])%mod+mod)%mod;
}
p[a[i]]=i;//记录当前数字最后出现的位置
}
cout<<dp[n]-1;//去掉空序列
return 0;
}
全部评论 (0)
还没有任何评论哟~