思路：乘法原理+哈希表

我们可以从1开始枚举$k$

$k=1$，其实就是数组中元素值为1的个数

$k=2$，根据乘法原理可知，就是数组中元素值为1的个数$\times$数组中元素值为2的个数

以此内推，因此使用一个哈希表统计数组中元素的个数，然后按照上述方式枚举$k$即可

代码

C++

#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e5 + 5;
const int mod = (int) 1e9 + 7;
unordered_map<int, int> mp;
int n;
int main() {
    cin >> n;
    int a;
    for (int i = 0; i < n; i ++) {
        cin >> a; mp[a] ++;
    }
    long long ans = 0, temp = 1;
    for (int i = 1; i <= n; i ++) {
        if (mp.find(i) == mp.end()) break;
        temp = (temp * mp[i]) % mod;
        ans = ans + temp;
    }
    cout << ans % mod << "\n";
    return 0;
}

Java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int mod = 1000000007;
        long ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Long> cnt = new HashMap<>();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        Arrays.sort(nums);
        int start = 0;
        while (start < n) {
            if (nums[start] == 1) {
                long tmp = map.get(1);
                cnt.put(1, tmp);
                ans = (ans + tmp) % mod;
                while (start < n && nums[start] == 1) {
                    start++;
                }
            }
            else {
                if (!map.containsKey(nums[start] - 1)) {
                    break;
                }
                int cur = nums[start];
                long tmp = map.get(cur) * cnt.get(cur - 1);
                tmp = tmp % mod;
                cnt.put(cur, tmp);
                ans = (ans + tmp) % mod;
                while (start < n && nums[start] == cur) {
                    start++;
                }
            }
        }
        System.out.println(ans % mod);
    }
}

Python

from collections import defaultdict
n = int(input())
mod = 1E9+7
hash_tb = defaultdict(int)
for x in input().split():
    x = int(x)
    hash_tb[x] += 1
ans = 0
cur = 1
for i in range(1, n + 1):
    if hash_tb[i] == 0:
        break
    cur = (cur * hash_tb[i]) % mod
    ans = (ans + cur) % mod
print(int(ans))

题目内容

给定一个长度为$n$的数组，求出这个数组有多少个子序列是一个$k$排列。$k\in[1,n]$

子序列:对数组删除若干个元素所得到的数组

$k$排列:一个长度为$k$的数组并且里面$[1,k]$ 每个整数恰好出现一次，例如$1,3,2,4$ 是一个$4$排列

输入描述

第一行输入一个整数$n(1\leq n\leq 10^5)$

第二行输入一个整数$a(1\leq a_i \leq 10^9)$

输出描述

一行一个整数，表示有多少个子序列是一个$k$ 排列 , $k \in[1,n]$ 。

由于答案过大，请对$10^9+7$取模。

示例1

输入

5
1 2 1 3 4

输出

8

方案为:

$[1],[1],[1,2],[2,1],[1,2,3],[2,1,3],[1,2,3,4],[2,1,3,4]$