第二题（卡码网周赛第二十六期（23年阿里淘天笔试真题））

题目链接
第二题（卡码网周赛第二十六期（23年阿里淘天笔试真题））

题目描述

讨厌鬼有一个长度为 n （1 < n < 10^5）的数组，他想知道这个数组有多少个子序列是一个排列?
子序列的定义: 数组删除若干个元素(也可以不删)后得到的新数组。
排列的定义: 长度为 m 的数组，1 到 m 每个元素都出现过，且恰好出现 1 次。

输入

第一行输入一个整数 n。
第二行输入 n 个正整数，a1, a2, …, an。（$1<=ai<=10^9$）

输出

一行一个整数，表示有多少个子序列是一个排列。由于答案过大，请将答案对 $10^9+7$取模后输出

样例输入

6
1 1 5 2 3 4

样例输出

10

提示

符合要求的子序列有：{1}，{1}，{1，2}，{1，2}，{1，2，3}，{1，2，3}，{1，2，3，4}，{1，2，3，4}，{1，5，2，3，4}，{1，5，2，3，4}共 10 个

题解1（C++版本）

// 贪心
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
const LL MOD = 1e9 + 7;

int n, a[N];
LL dp[N]; // dp[i]表示排列以i结尾的子序列个数
unordered_map<int, int> cnt; /// cnt[key] = val, 表示出现key的次数是val

/*
6
1 1 5 2 3 4
10

11
7 6 10 9 3 1 4 2 10 5 8
11
*/

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        if(a[i] > n) continue;
        if(cnt.count(a[i]) == 0) cnt[a[i]] = 1;
        else cnt[a[i]]++;
    }
    dp[0] = 1;
    LL ans = 0;
    sort(a + 1, a + n + 1);
    // 获取去重后数组的新长度
    int len = unique(a + 1, a + n + 1) - a - 1;
    for(int i = 1; i <= len; i++){
        if(a[i] > n) continue;
        dp[a[i]] = (cnt[a[i]] * dp[a[i] - 1]) % MOD;
        ans = (ans + dp[a[i]]) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}