笔试时间：2023年9月15日 秋招

备注：第五题暂无题解

第一题

题目：子序列计数

给定一个长度为n的数组，求有多少子序列满足: 子序列中元素种类数=子序列长度。

由于答案可能很大，请输出答案取模998244353后的结果。

输入描述

第一行一个整数n,1<= n <=10^5

第二行n个整数，a1,a2,...,an(1 <= ai <= 10^5)

输出描述

一行一个整数，表示答案。

样例输入

示例一：

3

2 3 3

示例二：

3

1 3 4

样例输出

示例一：

5

提示: 符合条件的子序列有(按照下标方式给出)

{1},{1,2},{1,3},{2},{3}

示例二：

7

提示: 符合条件的子序列有(按照下标方式给出)

{1},{1,2},{1,2,3},{1,3},{2},{2,3},{3}

参考题解

求出a有多少个子序列，其元素各不相同，使用乘法原理进行计数，每个数的选择是它的出现次数再加上1。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <map>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> numbers(n);
    for (int i = 0; i < n; i++) {
        std::cin >> numbers[i];
    }
    
    const int mod = 998244353;
    std::map<int, int> counter;
    
    for (int i = 0; i < n; i++) {
        counter[numbers[i]]++;
    }
    
    long long ans = 1;
    for (const auto& pair : counter) {
        ans = (ans * (pair.second + 1)) % mod;
    }
    
    ans = (ans - 1 + mod) % mod;
    std::cout << ans << std::endl;
    
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = scanner.nextInt();
        }

        final int mod = 998244353;
        HashMap<Integer, Integer> counter = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int num = numbers[i];
            counter.put(num, counter.getOrDefault(num, 0) + 1);
        }

        long ans = 1;
        for (int value : counter.values()) {
            ans = (ans * (value + 1)) % mod;
        }

        ans = (ans - 1 + mod) % mod;
        System.out.println(ans);
    }
}

第二题

题目：盲盲盒

最近盲盒活动非常火热，商家A和商家B打算进一步增加盲盒的"盲”，于是在各自的仓库，即仓库A和仓库B里面进行盲盒交换。

具体操作如下:

(1) 首先仓库A里面有k个普通盲盒以及1个超珍稀盲盒，仓库B里面有k + 1个普通盲盒；

(2)每次从两个仓库里面以均匀分布抽样出一个盲盒，并进行交换；经过n次盲盒交换之后，超珍稀盲盒仍然在仓库A的概率为p/q(最简分数)，那么p +q模10的数值是多少?

输入描述

第一行为测试组数T，接下来有T行数据，每行数据是交换次数n和盲盒数量K。

1 < n < 1000，1< T < 20, 1 < k < 100

输出描述

经过n次盲盒交换之后，超珍稀盲盒仍然在仓库A的概率为p/q(最简分数)，那么p + q模10的数值。

样例输入

4

2 5

2 6

3 7

3 9

样例输出

1

6

9

9

参考题解

可以使用暴力做法直接过。

Python：[此代码未进行大量数据的测试，仅供参考]

# 暴力做法
from fractions import Fraction

def solve2(n, k):
    f = Fraction((k + 1) ** n + (k - 1) ** n, 2* (k + 1) ** n)
    return (f.nume