51nod 1202 子序列个数

1202 子序列个数 51nod 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示例

Output示例

13

dp[i] 代表以v[i]为尾的不同子序列个数
当v[i]没出现过，那么dp[i] = dp[i-1}*2 + 1; 
// 前面的可构成序列的个数 *(2 往尾部添加与否) +（1 这个数单独作为子序列）
当v[i]出现过，  那么dp[i] = dp[i-1]*2 - dp[pos[v[i]]-1];  
// 这个数 前面出现过 那么排除之前以这个数字为尾的所有情况 即(dp[pos[v[i]]-1]-1),然后重新算上dp[i-1]*2+1 1和1抵消就是上面的式子了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = +;

const int mod = 1e9+;

ll v[N],dp[N];

int n, pos[N];

int main ()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%lld", &v[i]);

    for(int i=;i<=n;i++) {

        if(pos[v[i]]==) {

            dp[i] = dp[i-]* + ;

            dp[i] %= mod;

        }else {

            dp[i] = (dp[i-]* -dp[pos[v[i]]-]);

            dp[i] = (dp[i]+mod)%mod;

        }

        pos[v[i]]=i;

    }

    cout << dp[n]<<endl;

    return ;

}

参考资料：https://www.cnblogs.com/Roni-i/p/9003459.html

秒客网

51nod 1202 子序列个数

相关文章