NOI2026省选题目DAY1

[省选联考 2026] 找寻者 / recollector

题目背景

时过境迁，小 B 回到了他梦寐以求，却又折戟沉沙的省选赛场。但他关于算法竞赛的记忆还有多少呢？其中又有多少最为珍贵的记忆值得去珍惜呢？小 B 是一个对算法竞赛充满热情，乐于探索的人。而对他来说，最珍贵的记忆便是学习算法时对其进行各种修改、实验，尝试得到一些新成果的日子吧。

小 B 想请你陪他一起，去找寻这些珍贵的记忆。

题目描述

给定一棵包含 $n$ 个结点的无根树，结点的编号为 $1 \sim n$。

定义一种轻重链剖分方案如下：

• 首先指定某个结点作为树根，得到一棵有根树；
• 对于树上的每个非叶结点，选择恰好一个儿子作为重儿子，并将连接该结点与重儿子的边划分为重边，与其他儿子的连边划分为轻边；
• 此时，树上的所有重边及其端点构成了若干条极长简单路径，每条路径上的所有结点构成一条重链。定义一条重链的长度为其包含的结点数量。特别地，未与任何重边相连的结点单独构成一条长度为 $1$ 的重链。

小 B 回想起，多年前在学习轻重链剖分时，他曾提出过一种随机链剖分的算法，具体流程如下：

• 首先指定结点 $1$ 作为树根；
• 对树上的每个非叶结点自底向上地选择重儿子：对于非叶结点 $u$ ($1 \le u \le n$)，设其有 $k$ 个儿子 $v_1, v_2, \dots, v_k$。在递归确定出所有儿子的重儿子后，设 $v_1, v_2, \dots, v_k$ 各自所在的重链的长度分别为 $l_1, l_2, \dots, l_k$。则 $u$ 会以正比于重链长度的概率进行选择，即选择 $v_i$ ($1 \le i \le k$) 作为重儿子的概率为 $\frac{l_i}{\sum_{j=1}^{k} l_j}$。

小 B 知道，轻重链剖分的时间复杂度与各个结点到根结点的简单路径所包含的轻边数量密切相关。你需要帮助他求出，在上述随机链剖分算法下，对于每一个结点 $x$ ($1 \le x \le n$)，从结点 $x$ 到根结点 $1$ 的简单路径所包含的轻边数量的期望之和。由于答案可能较大，你只需求出其对 $998244353$ 取模后的结果。

期望的定义如下：设随机变量 $X$ 所有可能的取值分别为 $x_1, \dots, x_m$，其中 $X = x_i$ ($1 \le i \le m$) 的概率为 $p_i \in [0,1]$，且 $\sum_{i=1}^{m} p_i = 1$，则 $X$ 的期望为

$$\mathbb{E}[X] = \sum_{i=1}^{m} p_i x_i.$$

输入格式

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 $n$，表示结点的数量。
• 第 $i+1$ ($1 \le i \le n-1$) 行包含两个正整数 $u_i, v_i$，表示连接结点 $u_i$ 与结点 $v_i$ 的一条树边。

输出格式

对于每组测试数据，输出一行一个非负整数，表示所有结点到根结点的简单路径所包含的轻边数量的期望之和对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

0 2
5
1 2
1 3
2 4
2 5
8
1 2
1 3
2 4
2 5
2 6
5 7
3 8

输出 #1

665496238
549034400

说明/提示

【样例 1 解释】

该样例共包含两组测试数据。对于第一组测试数据：

• 结点 $2$ 将以均等的概率选择结点 $4$ 与结点 $5$ 作为重儿子；
• 结点 $1$ 将分别以 $2/3, 1/3$ 的概率选择结点 $2, 3$ 作为重儿子。

因此，

• 结点 $1$ 到根结点的简单路径所包含的轻边数量的期望为 $0$；
• 结点 $2$ 到根结点的简单路径所包含的轻边数量的期望为 $(2/3) \cdot 0 + (1/3) \cdot 1 = 1/3$；
• 结点 $3$ 到根结点的简单路径所包含的轻边数量的期望为 $(2/3) \cdot 1 + (1/3) \cdot 0 = 2/3$；
• 结点 $4$ 到根结点的简单路径所包含的轻边数量的期望为 $(2/3) \cdot (1/2) \cdot 0 + (2/3) \cdot (1/2) \cdot 1 + (1/3) \cdot (1/2) \cdot 1 + (1/3) \cdot (1/2) \cdot 2 = 5/6$；
• 结点 $5$ 到根结点的简单路径所包含的轻边数量的期望为 $5/6$。

故答案为 $0 + 1/3 + 2/3 + 5/6 + 5/6 = 8/3 \equiv 665496238 \pmod{998244353}$。

【样例 2】

见选手目录下的 recollector/recollector2.in 与 recollector/recollector2.ans。

该样例满足测试点 $3 \sim 5$ 的约束条件。

【样例 3】

见选手目录下的 recollector/recollector3.in 与 recollector/recollector3.ans。

该样例满足测试点 $6, 7$ 的约束条件。

【样例 4】

见选手目录下的 recollector/recollector4.in 与 recollector/recollector4.ans。

该样例满足测试点 $8 \sim 10$ 的约束条件。

【样例 5】

见选手目录下的 recollector/recollector5.in 与 recollector/recollector5.ans。

该样例满足测试点 $11, 12$ 的约束条件。

【样例 6】

见选手目录下的 recollector/recollector6.in 与 recollector/recollector6.ans。

该样例满足测试点 $13 \sim 16$ 的约束条件。

【样例 7】

见选手目录下的 recollector/recollector7.in 与 recollector/recollector7.ans。

该样例满足测试点 $17 \sim 25$ 的约束条件。

【数据范围】

对于所有测试数据，均有：

• $1 \le t \le 5$；
• $1 \le n \le 5,000$；
• 对于所有 $1 \le i \le n-1$，均有 $1 \le u_i, v_i \le n$，且 $(u_1, v_1), \dots, (u_{n-1}, v_{n-1})$ 构成一棵树。

::cute-table{tuack}

测试点编号	$n \le$	特殊性质
$1, 2$	$8$	无
$3 \sim 5$	$20$	^
$6, 7$	$500$	A
$8 \sim 10$	^	无
$11, 12$	$1,500$	B
$13 \sim 16$	^	无
$17 \sim 25$	$5,000$	^

• 特殊性质 A：对于所有 $1\le i\le n-1$，均有 $u_i=i$ 且 $v_i=i+1$。
• 特殊性质 B：对于所有 $1\le x\le n$，结点 $1$ 到结点 $x$ 的简单路径所包含的结点数量均不超过 $100$。

[省选联考 2026] 摩卡串 / string

题目背景

小摩卡是个天才，尤其在字符串理论方面有着异于常人的天赋。为了赞颂她的才华，人们常常将那些满足特定优美性质的字符串命名为“摩卡串”。

题目描述

小 H 有一个长度为 $n$ 的 01 串 $s$ 和一个正整数 $k$。他定义一个长度为 $m$ 的 01 串 $t = t_1 \dots t_m$ 为摩卡串，当且仅当 $t$ 满足以下两个条件：

• $s$ 是 $t$ 的子串，即存在 $1 \le l \le r \le m$ 使得 $s = t_l \dots t_r$；
• $t$ 中恰好有 $k$ 个子串的字典序严格小于 $s$。两个子串不同当且仅当两个子串的长度不同或位置不同。形式化地，存在恰好 $k$ 对 $(l, r)$ 满足 $1 \le l \le r \le m$ 且 $t_l \dots t_r$ 的字典序严格小于 $s$。

由于符合条件的摩卡串可能有很多，小 H 希望从中找出一个长度最短的摩卡串。你需要帮助他找出其中任意一个。

输入格式

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含两个正整数 $n, k$。
• 第二行包含一个长度为 $n$ 的 01 字符串 $s$。

输出格式

对于每组数据，输出一行一个 01 字符串，表示任意一个长度最短的摩卡串。特别地，若不存在摩卡串，则输出 Impossible。

输入输出样例 #1

输入 #1

0 5
1 1
1
1 1
0
3 9
101
4 17
1100
4 20
1100

输出 #1

10
Impossible
0101
011100
001100

说明/提示

【样例 2】

见选手目录下的 string/string2.in 与 string/string2.ans。

该样例满足测试点 $4 \sim 6$ 的约束条件。

【样例 3】

见选手目录下的 string/string3.in 与 string/string3.ans。

该样例满足测试点 $7 \sim 9$ 的约束条件。

【样例 4】

见选手目录下的 string/string4.in 与 string/string4.ans。

该样例满足测试点 $10 \sim 12$ 的约束条件。

【样例 5】

见选手目录下的 string/string5.in 与 string/string5.ans。

该样例满足测试点 $13 \sim 15$ 的约束条件。

【样例 6】

见选手目录下的 string/string6.in 与 string/string6.ans。

该样例满足测试点 $16 \sim 18$ 的约束条件。

【样例 7】

见选手目录下的 string/string7.in 与 string/string7.ans。

该样例满足测试点 $19, 20$ 的约束条件。

【数据范围】

对于所有测试数据，均有：

• $1 \le t \le 5$；
• $1 \le n \le 200$，$1 \le k \le 3,000$；
• 对于所有 $1 \le i \le n$，均有 $s_i \in \{0, 1\}$。

::cute-table{tuack}

测试点编号	$n \le$	$k \le$	特殊性质
$1 \sim 3$	$15$	$200$	A
$4 \sim 6$	$50$	$2,000$	B
$7 \sim 9$	^	^	C
$10 \sim 12$			D
$13 \sim 15$		$500$	无
$16 \sim 18$	$150$	$2,000$	^
$19, 20$	$200$	$3,000$

• 特殊性质 A：若存在摩卡串，则存在长度不超过 $15$ 的摩卡串。
• 特殊性质 B：对于所有 $1\le i\le n$，均有 $s_i=0$。
• 特殊性质 C：对于所有 $1\le i\le n$，均有 $s_i=1$。
• 特殊性质 D：存在正整数 $p\in [1,n]$ 满足 $s_1=\dots =s_p=0$ 且 $s_{p+1}=\dots =s_n =1$。

[省选联考 2026] 夜空 / night

题目背景

传说在很久以前，小怪兽 Nexus 作恶多端，大法师便将其封印于夜空之中。为了完成封印，大法师施展法术重排了星辰，令夜空呈现出特定的星象。

据说这道封印一直留存至今，再无人知晓它昔日的全貌。

题目描述

小 H 在阅读古籍时发现，夜空中的星辰可以抽象为一个非负整数序列。远古时期的星辰序列为 $A = [a_1, \dots, a_n]$，而如今所观测到的序列则为 $B = [b_1, \dots, b_m]$。

古籍中还记载了大法师重排星辰时使用的两种法术。具体而言，对于当前长度不小于 2 的星辰序列，大法师可以施展以下两种法术之一：

1. 删除序列最左侧的两个元素，并在最右侧插入它们的异或和；
2. 删除序列最右侧的两个元素，并在最左侧插入它们的异或和。

可以发现，每施展一次法术，星辰序列的长度都会恰好减少 1。小 H 猜测，或许大法师当年仅使用了这两种法术，恰好施展 $n - m$ 次，就将最初的序列 $A$ 变成了如今的序列 $B$。你需要帮助他判断这是否可能；若可能，还需找出一组具体的施法方案。

输入格式

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含两个正整数 $n, m$。
• 第二行包含 $n$ 个非负整数 $a_1, \dots, a_n$。
• 第三行包含 $m$ 个非负整数 $b_1, \dots, b_m$。

输出格式

对于每组测试数据：

• 第一行输出一个字符串 Yes 或 No，表示大法师是否可能仅施展了这两种法术就将序列 $A$ 变成了序列 $B$。
• 若可能，则第二行输出 $n - m$ 个 $\{1, 2\}$ 中的正整数，分别表示大法师每次施展的法术种类。

正确回答上述第一项即可获得部分分数，具体评分规则请参见【评分方式】。

输入输出样例 #1

输入 #1

0 5
2 2
1 2
1 2
3 2
3 4 2
6 3
5 3
2 3 4 5 6
6 1 1
6 1
1 2 3 4 5 6
0
7 2
3 3 5 6 1 2 8
11 3

输出 #1

Yes

Yes
2
Yes
1 1
No
Yes
2 1 2 1 1

说明/提示

【样例 1 解释】

该样例共包含五组测试数据。

对于第一组测试数据，序列 $A$ 与序列 $B$ 相同，因此无需施展任何法术。

对于第二组测试数据，施展一次第 $2$ 种法术后，删除了序列 $A$ 最右侧的 $4$ 和 $2$，并在最左侧插入 $4 \operatorname{xor} 2 = 6$，得到序列 $B$。

对于第三组测试数据，

• 施展一次第 $1$ 种法术后，删除了序列 $A$ 最左侧的 $2$ 和 $3$，并在最右侧插入 $2 \operatorname{xor} 3 = 1$，得到序列 $[4, 5, 6, 1]$；
• 再次施展一次第 $1$ 种法术后，删除了最左侧的 $4$ 和 $5$，并在最右侧插入 $4 \operatorname{xor} 5 = 1$，得到序列 $B$。

对于第四组测试数据，可以证明，仅施展这两种法术无法将序列 $A$ 变成序列 $B$。

【样例 2】

见选手目录下的 night/night2.in 与 night/night2.ans。

该样例满足测试点 $1, 2$ 的约束条件。

【样例 3】

见选手目录下的 night/night3.in 与 night/night3.ans。

该样例满足测试点 $4$ 的约束条件。

【样例 4】

见选手目录下的 night/night4.in 与 night/night4.ans。

该样例满足测试点 $7 \sim 9$ 的约束条件。

【样例 5】

见选手目录下的 night/night5.in 与 night/night5.ans。

该样例满足测试点 $12 \sim 14$ 的约束条件。

【数据范围】

对于所有测试数据，均有：

• $1 \le t \le 10^3$；
• $1 \le m \le n \le 250$；
• 对于所有 $1 \le i \le n$，均有 $0 \le a_i < 2^{30}$；
• 对于所有 $1 \le i \le m$，均有 $0 \le b_i < 2^{30}$。

::cute-table{tuack}

测试点编号	$n \le$	$m \le$	$T \le$	特殊性质
$1,2$	$16$		$10^3$	无
$3$	$250$	$1$	$30$	^
$4$	^	$2$	^
$5,6$		^		A
$7 \sim 9$	$50$			B
$10,11$	$250$		$30$	^
$12 \sim 14$	$50$			C
$15,16$	$250$		$30$	^
$17 \sim 19$	$50$			D
$20,21$	$250$		$30$	^
$22,23$	$50$			无
$24,25$	$250$		$30$	^

定义序列 $S = [s_1, \dots, s_k]$ 是奇异的，当且仅当 $k \ge 3$，且 $s_1 = s_2 = s_3 = 1$，且对于所有 $4 \le i \le k$，均有 $2 \mid s_i$。

定义序列 $S = [s_1, \dots, s_k]$ 的循环移位如下：对于正整数 $p$ ($1 \le p \le k$)，序列 $[s_p, s_{p+1}, \dots, s_k, s_1, \dots, s_{p-1}]$ 是序列 $S$ 的一个循环移位。

• 特殊性质 A：$3 \mid n$。
• 特殊性质 B：序列 $A, B$ 都是奇异的。
• 特殊性质 C：序列 $A$ 与序列 $B$ 各自存在一个循环移位是奇异的。
• 特殊性质 D：$2m \ge n$。

【评分方式】

本题包含两个小问。对于每个测试点：

• 小问 1：对该测试点中每组测试数据，正确判断可行性，即可获得该测试点 $50\%$ 的分数；
• 小问 2：在此基础上，若对每组答案为 Yes 的测试数据还能正确给出一组合法的施法方案，即可获得该测试点另外 $50\%$ 的分数。

注意：对于答案为 Yes 的测试数据，无论选手是否尝试给出正确的施法方案，都需要在第二行输出 $n - m$ 个 $\{1, 2\}$ 中的正整数，以满足输出格式。

【提示】

本题目录下提供了一份 checker.cpp 用于检验施法方案的可行性。注意：提供的 checker.cpp 只会检验答案为 Yes 的测试数据中施法方案的正确性，而不会检查可行性判断的正确性。

选手可以在本题目录下使用如下命令编译得到可执行程序：

g++ checker.cpp -o checker -std=gnu++14 -O2 -static

编译得到可执行程序后，选手可以在本题目目录下使用如下命令进行测试：

./checker <input_file> <output_file>

其中 <input_file> 与 <output_file> 分别表示输入文件与输出文件的路径。

注意：选手提供的输入文件需满足题目给定的输入格式与数据范围，输出文件需满足给定的输出格式，否则不保证检验结果的正确性，并可能发生无法预料的错误。