1202 子序列个数
- 1.0 秒
- 131,072.0 KB
- 20 分
- 3级题
子序列的定义：对于一个序列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的结果即可。
收起
输入
第1行：一个数N，表示序列的长度(1 <= N <= 100000) 第2 - N + 1行：序列中的元素(1 <= a[i] <= 100000)
输出
输出a的不同子序列的数量Mod 10^9 + 7。
输入样例
4 1 2 3 2
输出样例
13
我们知道如果不存在重复的数，那么dp[i]=dp[i-1]*2（含空集的情况）。现在考虑出现了重复的数。比如当前要取的数为a[i]，且a[i]最近一次在之前的j位置出现过了。那么有dp[i]=dp[i-1]*2-dp[j-1]。所以我们利用一个数组mark记录下a[i]出现的位置就好了，没有出现过为0。
#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 100000 + 11;const int mod = 1e9 + 7;int val[N], dp[N];
map<int, int> mp;
// dp[i] 截止到第i个数不重复的子序列的个数。
int main(){int n; scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d" ,&val[i]);}dp[0] = 1;for(int i = 1; i <= n; i++){dp[i] = dp[i - 1] << 1, dp[i] %= mod;if(mp[val[i]]) {dp[i] -= dp[mp[val[i]] - 1];dp[i] = (dp[i] % mod + mod) % mod;}mp[val[i]] = i;}printf("%d\n", dp[n] - 1);return 0;
}