2021北京师范大学保研上机真题
北京师范大学夏令营保研上机真题
在线测评链接：https://pgcode.cn/problem

分数序列-AI夏令营

题目描述

Luhhy最近在教小朋友练习算术，从最简单的加法练起。

为了节省出题时间的同时又能让大家得到充足的训练，Luhhy想到了这样一种方法：

她先在纸上写下了两个分数， $\frac{1}{0}$ 和 $\frac{0}{1}$（其中 $\frac{1}{0}$ 被视为无穷大），作为第0层。之后每一层，将相邻两个分数的分子和分母分别相加，得到的新分数插入其中。例如：

• 第1层：$\frac{0}{1}$, $\frac{1}{1}$, $\frac{1}{0}$
• 第2层：$\frac{0}{1}$, $\frac{1}{2}$, $\frac{1}{1}$, $\frac{2}{1}$, $\frac{1}{0}$
• 第3层：$\frac{0}{1}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{1}{1}$, $\frac{3}{2}$, $\frac{2}{1}$, $\frac{3}{1}$, $\frac{1}{0}$

在第1层中新产生了1个分数，共有3个分数。

在第2层中新产生了2个分数，共有5个分数。

在第3层中新产生了4个分数，共有9个分数。

第 $n$ 层新产生 $2^{n-1}$ 个分数，共有 $2^n+1$ 个分数。

以此类推，就可以无限地写下去。 Luhhy留的问题是第 $n$ 层从左数第 $m$ 个分数是多少。这里 $n$ 从 1 数起， $m$ 从0数起，也就是说每一层第0个总是 $\frac{0}{1}$。

输入格式

输入包含多组测试数据。

第一行一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行两个整数 $n$ 和 $m$，表示询问第 $n$ 层第 $m$ 个分数。

输出格式

对于每组测试数据，输出一行两个整数，分别为所求分数的分子和分母，用空格隔开。

输入样例1

4
1 0
2 1
1 2
2 2

输出样例1

0 1
1 2
1 0
1 1

数列比较-AI夏令营

题目描述

考虑两个等长的正整数组 $a[1,\dots ,n]$ 和 $b[1,\dots ,n]$，如果满足以下条件则称这两个序列耦合：

对任何整数 $i,j\in [1,n]$，如果 $a[i]<a[j]$ 则 $b[i]\le b[j]$。（显然，这等价于对任何整数 $i,j\in [1,n]$，如果 $b[i]<b[j]$ 则 $a[i]\le a[j]$）。

现在要求判断两个正整数组是否耦合。

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个正整数，用空格隔开，表示 $a$。

第三行，$n$ 个正整数，用空格隔开，表示 $b$。

输出格式

输出一行：如果耦合，输出 “YES”，否则输出 “NO”。

输入样例1

3
1 2 3
2 4 6

输出样例1

YES

矩阵乘法-AI夏令营

题目描述

存在这样的情况（如图）：

$$\left(\begin{array}{cc}2& 3\\ 6& 9\end{array}\right)\times \left(\begin{array}{cc}2& 3\\ 6& 9\end{array}\right)=\left(\begin{array}{cc}22& 33\\ 66& 99\end{array}\right)$$

$$\left(\begin{array}{cc}2& 2\\ 8& 7\end{array}\right)\times \left(\begin{array}{cc}4& 2\\ 8& 9\end{array}\right)=\left(\begin{array}{cc}24& 22\\ 88& 79\end{array}\right)$$

在十进制下，满足这种要求的情况有一百种。那么在别的进位制下呢？形式化地说，考虑整数 $ n \geq 2 $，以及整数 $ a, b, c, d \in [1, n-1] $ 以及 $ e, f, g, h \in [0, n-1] $，满足：

$$\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]\left[\begin{array}{cc}e& f\\ g& h\end{array}\right]=\left[\begin{array}{cc}an+e& bn+f\\ cn+g& dn+h\end{array}\right]$$

求满足以上条件的情况的数量。图中的矩阵乘法就是线性代数里的矩阵乘法。

输入格式

输入包含一个整数 $ n $（$ 2 \leq n \leq 100 $），表示进位制的基数。

输出格式

输出一个整数，表示满足条件的情况的数量。

数据范围

$ 2 \leq n \leq 100 $

输入样例1

10

输出样例1

100

猴子打字-AI夏令营

题目描述

BNU正在做一个猴子打字实验。现有一只能随机打字的猴子和一个只有前$k$个小写拉丁字母的键盘，研究人员想知道这只猴子在这个键盘上敲$n$次后得到的字符串包含"bnu"作为子串的概率是多少。

假设这个概率为$p$，则可以证明，$p\times k^n$是一个整数。事实上，$p\times k^n$即为有多少个仅由前$k$个小写拉丁字母组成的字符串，满足该字符串包含"bnu"作为子串。由于这个整数会很大，请输出它模$998244353$后的结果。

输入格式

第一行一个正整数$T$，表示有$T$组数据。

接下来$T$行，每行两个正整数$n$和$k$，用空格分开。

输出格式

输出$T$行，每行一个整数表示答案。

输入样例1

3
3 3
4 2
10 26

输出样例1

1
2
999643214