title: 枚举子集（递归实现指数型枚举）

description:
今有 $n$ 位同学，可以从中选出任意名同学参加合唱。

请输出所有可能的选择方案。

inputFormat: 仅一行，一个正整数 $n$。

outputFormat:
若干行，每行表示一个选择方案。

每一种选择方案用一个字符串表示，其中第 $i$ 位为 `Y` 则表示第 $i$ 名同学参加合唱；为 `N` 则表示不参加。

需要以字典序输出答案。

hint: 对于 $100\%$ 的数据，保证 $1\leq n\leq 10$。


title: 枚举排列（递归实现排列型枚举）

type: B

description:
今有 $n$ 名学生，要从中选出 $k$ 人排成一列拍照。

请按字典序输出所有可能的排列方式。

inputFormat: 仅一行，两个正整数 $n, k$。

outputFormat: 若干行，每行 $k$ 个正整数，表示一种可能的队伍顺序。

hint: 对于 $100\%$ 的数据，$1\leq k\leq n \leq 10$。


title: 猫粮规划

description:
到中午了，机器猫要吃猫粮了。

机器猫掏出 $n$ 份食物，第 $i$ 份食物含有的能量为 $w[i]$。机器猫可以吃掉其中一些食物，获得这些食物的能量之和。

机器猫又不想变得太胖又不想变得太瘦，所以指定了一个目标区间 $[l, r]$。显然，可能有很多种选择食物的方式可以达成这个目标，因此机器猫想知道方案总数。

inputFormat:
第一行，三个正整数 $n, l, r$。

第二行，$n$ 个正整数，表示每一份食物含有的能量 $w[i]$。

outputFormat: 仅一行，一个整数，表示方案数。


title: [省选联考 2022] 预处理器

type: P

description:
宏是 C/C++ 语言的一项特性，它根据预先定义的规则进行文本替换（也被称为 “宏展开”），能够实现定义常量、简化代码重复输入等功能。例如：

```cpp
#define PI 3.14159
double area = PI * r * r;
```

以上代码经过宏展开后变为：

```cpp

double area = 3.14159 * r * r;
```

其中，宏定义命令变成了空行，而其他行中的宏被展开成了规则定义的文本。

C/C++ 语言代码在编译时对宏的处理由**预处理器**完成。你的任务是实现一个简化版的预处理器，要求如下：

- 代码由**行**组成，每行除行末的换行符外，均由可打印 ASCII 字符（ASCII 码范围 $32\sim 126$）组成。每行要么是**预处理命令**（以 `#` 开头），要么是**普通文本**（其他情况）。

- 预处理器逐行处理代码，
	- 如果是预处理命令，执行该命令，并输出一个空行。
    - 如果是普通文本，对其进行宏展开并输出结果。
- 预处理命令有两种，分别是宏定义命令 `#define` 和取消宏定义命令 `#undef`。
	- 宏定义命令的格式为 `#define <name> <content>`，其中第一部分 `#define` 是命令名，第二部分 `<name>` 是要定义的宏的名字，第三部分 `<content>` 是要定义的宏的展开内容。
    - 取消宏定义命令的格式为 `#undef <name>`，其中第一部分 `#undef` 是命令名，第二部分 `<name>` 是要取消的宏的名字。

    以上两种预处理命令中，相邻两部分之间都严格用一个空格分隔。`<name>` 是由大小写字母和数字以及下划线组成的**标识符**（一个或多个字符），`<content>` 可以包含任意可打印 ASCII 字符（零个或多个字符）。一个宏定义的**有效范围**是从它定义所在行开始到后续最近的宏名匹配的取消定义所在行为止（如果没有对应的取消定义，则有效范围一直覆盖到文件结束）。

对普通文本进行宏展开时，将一行文本中每段**连续极长**的大小写字母和数字以及下划线视为标识符（而不是其中一部分），其余为**其他字符**。从左到右依次对文本中的标识符进行宏展开：

1. 如果该标识符是有效的宏名，则用对应的展开内容替换它，此时该宏名进入正在展开的状态，直到本流程结束；否则原样保留宏名。例如，若宏 `A` 定义为 `b`，则文本 `A` 展开结果为 `b`（发生替换），文本 `B` 展开结果仍然为 `B`（未定义，不替换），文本 `AA` 展开结果仍然为 `AA`（`AA` 是不同于 `A` 的另一个标识符，未定义），而文本 `A*B` 展开结果为 `b*B`。

2. 替换发生后，如果展开内容中包含标识符，重复应用以上的展开操作，称为 “多次展开”。例如，若宏 `A` 定义为 `B`，宏 `B` 定义为 `c`，则文本 `A` 的展开结果为 `c`。

3. 如果待展开的宏名与正在进行展开的某个宏名相同，称为 “递归展开”，此时该宏名不再展开。本规则用来防止无限递归展开。例如，若宏 `A` 定义为 `B+a`，宏 `B` 定义为 `A+b`，则文本 `A` 展开结果为 `A+b+a`，由于最初的 `A` 处于正在展开状态，因此 `A+b+a` 里的 `A` 不再展开。

4. 其他字符原样保留。

注意：出于简化的目的，本题的要求与 C/C++ 语言标准里的描述不完全一致，请以上面的要求为准。最明显的区别是本题只有标识符和其他字符两类词法单元，没有数值、字符串、注释等。

inputFormat:
输入的第一行包含一个正整数 $n$，表示要处理的代码行数。

接下来的 $n$ 行是要处理的代码。

outputFormat: 输出 $n$ 行，为输入逐行预处理后的结果。

samples:
5
#define BEGIN {
#define END }
#define INTEGER int
class C BEGIN INTEGER x; END;
INTEGER main() BEGIN C c; END

samples:
见附件中的 preprocessor/preprocessor2.in
见附件中的 preprocessor/preprocessor2.ans

samples:
见附件中的 preprocessor/preprocessor3.in
见附件中的 preprocessor/preprocessor3.ans

hint:
**【数据范围】**

对 $20\%$ 的数据，不会出现宏定义命令 `#define` 和宏取消定义命令 `#undef`。

对另外 $20\%$ 的数据，不会出现多次展开的情况，且不会出现宏取消定义命令 `#undef`。

对另外 $20\%$ 的数据，不会出现多次展开的情况。

对另外 $20\%$ 的数据，不会出现递归展开的情况。

对其余数据，无特殊限制。

对 $100\%$ 的数据，$n \leq 100$，输入的每行字符数都不超过 $100$，且保证输出的每行字符数都不超过 $1000$（字符数均不计行末换行符）。保证输入数据中的预处理命令都是合法的，包含但不限于：

- `#` 字符只会出现在预处理命令所在行的第一个字符的位置，其他任何位置（包括预处理命令和普通文本）都不会出现 `#` 字符。
- 宏定义和取消定义命令的格式是正确的，严格遵循题面所描述的格式。
- 同一个宏在取消定义之前不会被再次定义。
- 要取消定义的宏在之前被定义过且还没有被取消过。

也就是说，**你不需要做任何语法和语义的错误检查**。

**【提示】**

本题进行输入时建议使用 C++ 语言的按行读入字符串功能，示例如下：

```cpp
#include <iostream>
#include <string>
using namespace std;
string line;
// 从 cin 读入一行，放入 line 中（换行符被舍弃）
getline(cin, line);
```

也可以使用 C 语言提供的 `fgets` 函数，示例如下：

```cpp
#include <stdio.h>
#define MAX_LEN 200
char line[MAX_LEN];
// 从 stdin 读入一行，放入 line 中（包含换行符）
fgets(line, MAX_LEN, stdin);
```

**注意**：在读取行数 $n$ 之后可能需要额外读取一行以忽略其后的换行符。


title: [省选联考 2022] 填树

background: 原题时限为 2s。

description:
有一棵 $n$ 个节点的无根树，刚开始树上每个节点的权值均为 $0$。KK 想对这棵树进行一些修改，他会任选一个节点作为初始的当前节点，然后重复以下动作：

1. 将当前节点 $i$ 的权值修改为一个**正整数** $x$，需满足 $l_i \leq x \leq r_i$。其中 $l_i, r_i$ 是输入中给出的两个正整数。
2. 结束修改过程，或移动到一个与当前节点相邻的权值为 $0$ 的节点（如果不存在这样的节点，则必须结束修改过程）。

现在 KK 有两个问题：

1. 在修改结束后，可以得到多少棵不同的树，满足树上**非零权值**的最大值和最小值的差小于等于 $K$？其中 $K$ 是输入中给出的一个正整数。

2. 这些满足条件的树的权值之和为多少？（树的权值定义为这棵树上所有节点的权值之和）

你需要输出这两个问题的答案模 $10^9 + 7$。我们认为两棵树不同当且仅当至少存在一个节点的权值不同。

温馨提示：

1. KK 至少会修改一个节点（初始节点）。
2. 实质上 KK 会修改树上的任意一条路径，最后需要满足这条路径上的点的权值最大值和最小值之差小于等于 $K$。

inputFormat:
第一行两个正整数 $n, K$，表示节点数和权值差的最大值。

接下来 $n$ 行，每行两个正整数 $l_i, r_i$，表示第 $i$ 个节点修改后权值的最小值和最大值。

接下来 $n - 1$ 行，每行两个正整数 $u_i, v_i$，表示节点 $u_i$ 和 $v_i$ 之间有一条边。数据保证形成一棵树。

outputFormat: 输出两行，每行一个整数，分别表示第一问和第二问的答案模 $10^9 + 7$ 的值。注意，如果你不打算回答第二问，请在第二行任意输出一个整数。如果输出文件只有一行，则可能会因格式不符合要求被判 $0$ 分。

samples:
见附件中的 tree/tree2.in
见附件中的 tree/tree2.ans

samples:
见附件中的 tree/tree3.in
见附件中的 tree/tree3.ans


title: [COCI2021-2022#5] Fliper

description:
现有一个包含 $n$ 块挡板的旧弹球机。

游戏在二维平面内进行，其中每块挡板与坐标轴所夹锐角总为 $45^\circ$，长度为 $1$ 个单位。挡板用其中心坐标 $(x_i,y_i)$ 和字符 / 或 \ 来表示。小球在碰到挡板后，其运动方向将会旋转 $90^\circ$。注意，挡板的两面都可使小球的运动方向发生偏转。

不难发现，当小球处于弹球机中时，它只有两种结局：

- 沿着某一方向一直运动下去而不碰到挡板
- 处于若干个挡板的循环之中

在翻新弹球机的过程中，有四种颜色的染料可供选择。现要将弹球机中的每个挡板进行染色，使得**每一个**循环内经过每一种颜色的次数相同且为偶数。

请给出一种符合题意的染色方式，或证明这样的染色方式不存在。如果不存在，输出 `-1`。

inputFormat:
第一行一个正整数 $n$，表示挡板的数量。

接下来的 $n$ 行，每行两个正整数 $x_i,y_i$ 和一个字符 $c_i$（/ 或 \），表示一个挡板。数据保证，挡板的位置不会相互重合。

outputFormat:
如果不存在符合题意的染色方式，输出 `-1`。

否则输出 $n$ 个整数 $1 \sim 4$，表示 $n$ 个挡板所选择的染料颜色。如果有多种符合题意的方式，输出任意一种。

hint:
**【样例 2 图解】**

![](https://cdn.luogu.com.cn/upload/image_hosting/ksajf2n4.png)

**【数据规模与约定】**

**本题采用捆绑测试。**

- Subtask 1（20 pts）：$1 \le n \le 40$。
- Subtask 2（20 pts）：最多存在一个循环。
- Subtask 3（70 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^5$，$0 \le |x_i|,|y_i| \le 10^9$。

**【说明】**

本题采用自行编写的 [Special Judge](https://www.luogu.com.cn/paste/g6cdziry)。如果对此有疑问或想要 hack，请[私信编写者](https://www.luogu.com.cn/chat?uid=137367)或[发帖](https://www.luogu.com.cn/discuss/lists?forumname=P8326)。

**【来源】[COCI 2021-2022#5](https://hsin.hr/coci/contest5_tasks.pdf) Task 3 Fliper。**


title: [省选联考 2022] 学术社区

background:
**小 I 的温馨提示：在题目描述中有形式化的题面，你可以选择跳过题目背景。同时请仔细将本题的除题目背景以外的所有内容进行完整阅读后再进行做题。**

小 I 是一个喜欢 OI 的选手，不过，与其说小 I 喜欢 OI，不如说小 I 喜欢的是他最经常使用的 OJ——FCCOJ——上的趣味功能：学术社区。虽说名字叫学术社区，但小 I 和网友们能够谈论的东西远不止学术。每天学术社区里总会出现不少吸引小 I 注意的帖子。今天小 I 在学术社区冲浪时发现了一个这样的帖子：

> `builtin_clz`：萌新求助，学术社区这题，本机 AC 提交 RE
>
> `builtin_ctz`：`builtin_clz` 楼下
>
> `jinkela`：`builtin_ctz` 楼下
>
> `builtin_ctz`：`builtin_clz` 楼上
>
> `builtin_clz`：能不能别魔怔了，大家正经回答问题
>
> `OrzTourist`：`builtin_clz` 楼下
>
> `OrzTourist`：`OrzTourist` 楼下
>
> `builtin_clz`：怎么没有人回答问题，我生气了！
>
> `builtin_clz`：`builtin_clz` 楼上
>
> `builtin_clz`：`builtin_clz` 楼下
>
> `builtin_clz`：`builtin_clz` 楼上
>
> `builtin_clz`：`builtin_clz` 楼下
>
> ……

虽然这个名叫 `builtin_clz` 的网友因为没有人回答他的学术问题被激怒了，但这个有趣的发言方式让小 I 乐呵了许久，这说明人类的悲欢并不相通。不过当小 I 刷新界面想要往下浏览大家的回复时，却发现学术社区的管理员因为这个帖子过于灌水把它删除了。

为了恢复这个有趣的帖子，小 I 对着网页缓存倒腾了许久，还原出了这个帖子的每条消息。然而因为神秘原因，消息的顺序被打乱了，且缓存中没有每条消息发送的时间，因而小 I 没有办法还原原始帖子中消息的顺序。

秉承 “遇到困难睡大觉” 精神的小 I 决定随便给帖子里的消息排个顺序，不过深受 “`XXX` 楼上” “`XXX` 楼下” 这种发言形式吸引的小 I 还是希望重排之后有尽可能多的这种形式的消息的表达是符合帖子的实际情况的。然而小 I 是一个只会水社区不会做题的 OI 选手，所以小 I 求助于你。

当然了，小 I 知道直接将帖子中的原始信息丢给你对你来说是不方便的，所以他对信息进行了一些规范化处理，详见题目描述中的形式化题意。**同时由于学术社区的特殊规定，帖子中的消息满足一定特殊限制，详见题目描述最后。**

description:
**以下涉及的所有字符串判等操作都对大小写敏感，例如 `1oushang`、`Loushang`、`LOUSHANG` 是互不相同的字符串。**

小 I 正在整理学术社区中的一个帖子。帖子中一共有 $N$ 个网友发过消息，他们的网名分别为 $n_1, n_2, \ldots, n_N$。帖子中总共有 $M$ 条消息，对于第 $i$ 条消息，我们用三个字符串 $s_{i,1}, s_{i,2}, s_{i,3}$ 构成的三元组描述它，其中 $s_{i,1}$ 表示这条消息发出者的网名，而 $s_{i,2}$ 和 $s_{i,3}$ 描述这条消息的内容。

对于第 $i$ 条消息，我们通过如下方式定义其属于**楼下型消息**、**楼上型消息**、**学术型消息**中的哪一种：

- 若字符串 $s_{i, 3}$ 为 `louxia`，且 $s_{i, 2}$ 恰好与给出的某个网名相同（注意 $s_{i,2} = s_{i,1}$ 是允许的），则称这条消息是**楼下型消息**，$s_{i,2}$ 对应这条消息提到的网友；
- 若字符串 $s_{i,3}$ 为 `loushang`，且 $s_{i,2}$ 恰好与给出的某个网名相同（注意 $s_{i,2} = s_{i,1}$ 是允许的），则称这条消息是**楼上型消息**，$s_{i,2}$ 对应这条消息提到的网友；
- 若以上两个条件都不满足，则称这条消息是**学术消息**。

定义一个对所有消息的重排方案为一个 $1$ 到 $M$ 的排列 $a_1, a_2, a_3, \ldots, a_M$，表示第一条消息是 $(s_{a_1,1}, s_{a_1,2}, s_{a_1,3})$，第二条消息是 $(s_{a_2,1}, s_{a_2,2}, s_{a_2,3})$，依此类推。

对于一个重排方案 $a_1, a_2, a_3, \ldots, a_M$ 中的第 $i$（$1 \le i \le M$）条消息 $(s_{a_i,1}, s_{a_i,2}, s_{a_i,3})$，如下定义其是否是**符合实际情况的**：

- 若这条消息是**楼下型消息**，则这条消息是**符合实际情况的**当且仅当 $i \ne 1$ 且 $s_{a_{i - 1}, 1} = s_{a_i, 2}$，即上一条消息存在且它的发出者与这条消息提到的网友一致。
- 若这条消息是**楼上型消息**，则这条消息是**符合实际情况的**当且仅当 $i \ne M$ 且 $s_{a_{i + 1}, 1} = s_{a_i, 2}$，即下一条消息存在且它的发出者与这条消息提到的网友一致。
- 若这条消息是**学术消息**，则无论如何这条消息一定不是符合实际情况的，这是因为小 I 只想灌水不想学术。

在以上定义下，小 I 希望找到一个重排方案，使得该重排方案中符合实际情况的消息数量最多。你需要帮他找到这个方案以及这个方案中符合实际情况的消息数量。

**为了方便你的解题，小 I 还告诉了你帖子中消息的一个特殊限制：因为学术社区会禁言在社区中只灌水不学术的人，所以在小 I 给出的帖子里，每一个在帖子中发过言的人都一定会在帖子中发出至少一条学术消息。**

inputFormat:
**本题有多组测试数据**。第一行一个整数 $T$ 表示测试数据组数，接下来分别输入 $T$ 组数据。

对于每组测试数据，第一行两个整数 $N, M$ 分别表示帖子中发过消息的网友数量以及帖子的消息数量。

接下来 $N$ 行每行一个字符串 $n$ 表示在帖子中发过消息的一个网友的网名。保证每个测试数据中输入的 $N$ 个网友的网名两两不同。

接下来 $M$ 行每行三个字符串 $s_1, s_2, s_3$ 描述一条消息，相邻的字符串之间用一个空格分隔，其中 $s_1$ 一定与输入中某个网友的网名相等。

输入的所有字符串仅由大小写英文字母、下划线（`_`）、英文问号（`?`）、英文感叹号（`!`）和英文句号（`.`）构成，且长度不超过 $12$。

对于每组测试数据，保证输入的 $N$ 个网名都发出过至少一条消息，**且至少发出过一条学术消息**。

同一组测试数据中可能存在多条消息内容完全一致，此时应将他们视为**多条**消息。

outputFormat:
对于每组测试数据输出两行。

第一行输出一个非负整数表示所有重排方案中最大的符合实际情况的消息数量。

第二行输出 $M$ 个整数 $a_1, a_2, \ldots, a_m$，表示符合实际情况的消息最多的重排方案。

若有多种合法的重排方案，**输出任意一个即可**。

samples:
2
4 15
builtin_clz
builtin_ctz
jinkela
OrzTourist
builtin_clz MengXin QiuZhu
builtin_ctz builtin_clz louxia
jinkela builtin_ctz louxia
builtin_ctz builtin_clz loushang
builtin_clz BieMoZheng YaoXueShu
OrzTourist builtin_clz louxia
OrzTourist OrzTourist louxia
builtin_clz Iam Angry!
builtin_clz builtin_clz loushang
builtin_clz builtin_clz louxia
builtin_clz builtin_clz loushang
builtin_clz builtin_clz louxia
builtin_ctz Xue Shu
jinkela Xue Shu
OrzTourist Xue Shu
1 9
builtin_clz
builtin_clz builtin_clz loushang
builtin_clz builtin_clz loushang
builtin_clz builtin_clz louxia
builtin_clz builtin_clz Loushang
builtin_clz builtin_clz LOUSHANG
builtin_clz Builtin_clz loushang
builtin_clz loushang louxia
builtin_clz builtin_clz builtin_clz
builtin_clz loushang builtin_clz

samples:
见附件中的 community/community2.in
见附件中的 community/community2.ans

hint:
**【样例解释 #1】**

第一个测试数据与题目背景中给出的例子基本一致，而不同的点在于：为了满足每个人至少发出一条学术消息的要求，在该组数据输入的最后有几条额外的学术消息。

第二个测试数据中，输入的前两条消息是楼上型消息，第三条消息是楼下型消息，其他消息是学术消息。

**【样例 #3】**

见附件中的 `community/community3.in` 与 `community/community3.ans`。

该组样例满足数据范围中的特殊性质 A、特殊性质 B、特殊性质 C。

**【样例 #4】**

见附件中的 `community/community4.in` 与 `community/community4.ans`。

该组样例满足数据范围中的特殊性质 C。

**【数据范围】**

设 $\sum M$ 为单个测试点中所有测试数据的 $M$ 的和。

对于所有测试点，$1 \le T \le 100$，$1 \le N \le M \le 77777$，$1 \le \sum M \le 2.5 \times {10}^5$。

| $T \le$ | $M \le$ | $\sum M \le$ | 测试点编号 | 特殊性质 A | 特殊性质 B | 特殊性质 C |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $5$ | $10$ | $50$ | $1$ | 无 | 无 | 无 |
| $10$ | $16$ | $160$ | $2$ | 无 | 无 | 无 |
| $30$ | $2222$ | $15000$ | $3 \sim 4$ | 有 | 有 | 有 |
| $30$ | $2222$ | $15000$ | $5 \sim 6$ | 有 | 无 | 有 |
| $30$ | $2222$ | $15000$ | $7 \sim 9$ | 无 | 有 | 有 |
| $30$ | $2222$ | $15000$ | $10 \sim 11$ | 无 | 无 | 有 |
| $30$ | $2222$ | $15000$ | $12 \sim 13$ | 无 | 无 | 无 |
| $100$ | $77777$ | $2.5 \times {10}^5$ | $14 \sim 15$ | 有 | 有 | 有 |
| $100$ | $77777$ | $2.5 \times {10}^5$ | $16$ | 有 | 无 | 有 |
| $100$ | $77777$ | $2.5 \times {10}^5$ | $17 \sim 19$ | 无 | 有 | 有 |
| $100$ | $77777$ | $2.5 \times {10}^5$ | $20 \sim 22$ | 无 | 无 | 有 |
| $100$ | $77777$ | $2.5 \times {10}^5$ | $23 \sim 25$ | 无 | 无 | 无 |

**注意：为了阅读方便，测试点编号在表格中的第四列。**

特殊性质 A：没有楼上型消息。**注意：这不意味着 $\bm{s_3}$ 不等于 `loushang`。**

特殊性质 B：对于每组测试数据，存在一个重排方案，使得每一条楼上型消息和楼下型消息都是符合实际情况的。

特殊性质 C：对于每组测试数据，若存在一条消息是 $s_1$ $s_2$ `loushang`，其中 $s_1, s_2$ 为任意字符串，则该组数据中一定不存在一条消息是 $s_2$ $s_1$ `louxia`。

**【评分方式】**

若一个测试点内所有测试数据的符合实际情况的消息数量都正确，你将获得该测试点 $50 \%$ 的分数；在此基础上，若一个测试点内所有测试数据的重排方案都正确，你将获得该测试点的所有分数。需要注意的是，**如果你只希望获得 $\bm{50 \%}$ 的分数，你也要保证在每组测试数据的第二行输出一个 $\bm{1}$ 到 $\bm{M}$ 的排列，否则实际分数与期望分数可能出现偏差**。

**【提示】**

因为这对你可能很重要，所以小 I 再一次强调：**因为学术社区会禁言在社区中只灌水不学术的人，所以在小 I 给出的帖子里，每一个在帖子中发过言的人都一定会在帖子中发出至少一条学术消息**。

本题输入规模较大，请使用较为快速的输入方式。


title: [COCI2021-2022#5] Radio

description:
克罗地亚有 $n$ 个初始状态下关闭的电台。当同时开启两个电台 $i,j$ 且 $i,j$ 不互质时，它们会互相干扰。

你需要写一个支持下列操作的程序：

1. `S x`：将电台的状态取反，即将原来开启的电台关闭，将原来关闭的开启。
2. `C l r`：检查在 $[l,r]$ 内是否存在互相干扰的现象。如果存在，输出 `DA`，否则输出 `NE`。

inputFormat:
第一行两个正整数 $n,q$，分别表示电台个数和操作次数。

接下来的 $q$ 行，具体输入格式见题目描述。

outputFormat: 对于每一次 C 操作，输出 `DA` 或者 `NE`。


title: [COCI2021-2022#5] Usmjeravanje

description:
永无岛有两条河流。每条河流沿岸分布有若干个城市，其中城市数量分别为 $a,b$。

对于位于同一条河流沿岸的 $i,j$ 两个城市，如果 $i \lt j$，那么可以通过水路从城市 $i$ 到城市 $j$。

永无岛的居民们已经决定修建 $m$ 条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线，但方向有待商榷。

当两个城市之间可以通过水路或航线互相到达时，则称它们是连通的。在所有的城市中，存在若干个城市集合，使得集合中没有任何一对城市是连通的。请为每条航线选择一个方向，使得所有集合中包含元素最多的集合元素个数最少。

inputFormat:
第一行两个正整数 $a,b$。

第二行一个正整数 $m$。

接下来的 $m$ 行，每行两个正整数 $x_i,y_i$，表示一条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线。数据保证没有重复的无序数对 $(x_i,y_i)$ 出现。

outputFormat:
第一行一个正整数，表示最大集合元素个数的最小值。

第二行 $m$ 个整数 $0$ 或 $1$。其中 $0$ 表示方向从第一条河流的城市 $x_i$ 到第二条河流的城市 $y_i$，$1$ 则相反。

如果有多种符合题意的方案，输出任意一种。

hint:
**【样例 1 解释】**

最优的方案可以使得每对城市都连通，因此答案为 $1$。

**【数据规模与约定】**

**本题采用捆绑测试。**

- Subtask 1（20 pts）：$1 \le a,b,m \le 15$。
- Subtask 2（30 pts）：$1 \le a,b \le 1000$。
- Subtask 3（60 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le a,b,m \le 2 \times 10^5$，$1 \le x_i \le a$，$1 \le y_i \le b$。

**【说明】**

本题采用自行编写的 [Special Judge](https://www.luogu.com.cn/paste/uv2vgxxa)。如果对此有疑问或想要 hack，请[私信编写者](https://www.luogu.com.cn/chat?uid=137367)或发帖。

**【来源】[COCI 2021-2022#5](https://hsin.hr/coci/contest5_tasks.pdf) Task 5 Usmjeravanje。**


title: [省选联考 2022] 卡牌

description:
小 A 有 $n$ 张卡牌，编号为 $1, 2, \ldots, n$。每张卡牌上写着一个正整数，第 $i$ 张卡牌上的正整数为 $s_i$。

现在有 $m$ 轮游戏，第 $i$ 轮游戏会给出 $c_i$ 个质数，小 A 需要选择任意多张卡牌，使得这些卡牌上面的正整数的乘积能被该轮游戏给出的每个质数整除。

这当然难不倒小 A，于是他开始思考一个更难的问题，对于每一轮游戏，他有多少种卡牌的选法。

这给小 A 整不会了，于是他只能来求助你，你只需要告诉他答案模 $998244353$ 的值即可。两种选法 A 和 B 互不相同当且仅当存在一张卡牌在 A 中被选择但在 B 中未被选择或者存在一张卡牌在 B 中被选择但在 A 中未被选择。注意：牌面上的数字相同但编号不相同的两张卡牌被视为不同的卡牌。

inputFormat:
第一行一个正整数 $n$，表示卡牌数量。

第二行 $n$ 个正整数 $s_i$，表示每张卡牌上写的数字。

第三行一个正整数 $m$，表示游戏轮数。

接下来 $m$ 行，每行第一个正整数 $c_i$，表示该轮游戏给出的质数个数，接下来 $c_i$ 个质数 $p_{i, j}$，表示该轮游戏给出的所有质数。数据保证 $\sum_i c_i \le 18000$，即所有 $c_i$ 之和不超过 $18000$。

outputFormat: 输出 $m$ 行，每行一个整数，第 $i$ 行表示第 $i$ 轮游戏的方案数模 $998244353$ 的值。

samples:
见附件中的 card/card2.in
见附件中的 card/card2.ans


title: [省选联考 2022] 序列变换

description:
你手里有一个长度为 $2 n$ 的合法括号序列 $s$。$s$ 的每一个左括号有一个权值。

在你眼中，不同的括号序列带来的视觉美感不尽相同。因此，你对具有某一种结构的括号序列特别喜欢，而讨厌具有其他一些结构的括号序列。你希望对 $s$ 进行一些变换，以消除掉一些自己不喜欢的结构。

具体而言，形如 $\texttt{(A()B)}$（其中 $\texttt{A}$、$\texttt{B}$ 均为合法括号序列，下同）的结构是你喜欢的，
而形如 $\texttt{(A)(B)}$ 的结构是你不喜欢的。你有两种操作来改变括号之间的位置。

这两种操作如下：
- 操作 1：交换形如 $\texttt{p(A)(B)q}$ 的串中 $\texttt{A}$ 和 $\texttt{B}$ 之间的两个括号，变换为 $\texttt{p(A()B)q}$（其中 $\texttt{p}$、$\texttt{q}$ 为任意串，可以为空，但不一定分别为合法括号序列，下同），它的代价为 $x$ 乘 $\texttt{(A)}$ 中第一个左括号的权值加上 $y$ 乘 $\texttt{(B)}$ 中第一个左括号的权值，其中 $x, y \in \{0, 1\}$；
- 操作 2：交换形如 $\texttt{pABq}$ 的串中的 $\texttt{A}$ 和 $\texttt{B}$，变换为 $\texttt{pBAq}$，这个操作不需要代价。

注意：交换的时候所有左括号的权值是跟着这个括号一起交换的。

你现在想知道的是，将 $s$ 变换为一个不包含你不喜欢的结构的括号序列至少需要多少代价？

inputFormat:
第一行三个整数 $n, x, y$。

第二行一个长度为 $2n$ 的合法括号序列，表示 $s$。

第三行 $n$ 个正整数，其中第 $i$ 个表示左数第 $i$ 个左括号的权值。

outputFormat: 一行一个整数，表示把 $s$ 变换为一个不包含你不喜欢的结构的括号序列至少需要的代价。

samples:
见附件中的 bracket/bracket3.in
见附件中的 bracket/bracket3.ans

hint:
**【样例解释 #1】**

最优方案是先使用操作 2 交换两对括号，然后使用操作 1（此时 $\texttt{A}$、$\texttt{B}$、$\texttt{p}$、$\texttt{q}$ 都是空串）交换中间的两个括号，代价为 $\texttt{B}$ 左边那个括号的权值，也就是 $1$。最后得到括号序列 $\texttt{(())}$，不包含你不喜欢的结构。

**【样例解释 #2】**

最优方案是直接使用操作 1，因为此时计算代价的方式不同了，这次只算 $\texttt{A}$ 左边的那个括号的权值作为代价。

**【数据范围】**

保证 $2 \le n \le 400000$，$0 \le x, y \le 1$。

保证所有的权值在 $[1, {10}^7]$ 之内。

| 测试点编号 | 特殊限制 |
|:-:|:-:|
| $1 \sim 3$ | $n \leq 8$ |
| $4 \sim 5$ | 所有权值均相等 |
| $6 \sim 8$ | $n \leq 20$ |
| $9 \sim 12$ | $x = 0$，$y = 1$ |
| $13 \sim 16$ | $n \le 2000$ |
| $17 \sim 25$ | 无特殊限制 |

**【提示】**

称一个字符串 $s$ 为合法括号序列，当且仅当 $s$ 仅由数量相等的字符 $\texttt{(}$ 和 $\texttt{)}$ 组成，且对于 $s$ 的每一个前缀而言，其中 $\texttt{(}$ 的数量均不少于 $\texttt{)}$ 的数量。特别地，空串也是合法括号序列。


title: [省选联考 2022] 最大权独立集问题

description:
小 E 喜欢出最大权独立集问题。

接下来，他还想了 $n$ 道最大权独立集问题。

小 E 有 $n$ 个 AI，编号为 $1 \sim n$。

开始时第 $i$ 个 AI 里面存有 $d_i$ 道小 E 事先出好的最大权独立集问题。

有些 AI 之间可以互相通信，对于所有的 $2 \leq i \leq n$ ，第 $i$ 个 AI 可以和第 $c_i$ 个 AI 互相通信。其中 $c_i < i$，且相同的 $c_i$ 出现不超过 $2$ 次。所以，这些 AI 连成了一个二叉树的形状。此外，其他对 AI 不可以互相通信。

小 E 需要暂时断开这些 AI 之间的连接。他只能逐一断开 AI 之间的连接。两个原本能够互相通信的 AI 在断开它们之间的连接之前，会互相交换存在里面的所有题目，具体请见样例。

小 E 希望在断掉所有连接之后，参与交换的题目数量最少。
他想叫你帮他解决这个问题，还说如果你成功解决了这个问题，那么在出那些最大权独立集问题的时候，他会帮你提交一份标程代码。

inputFormat:
第一行一个正整数 $n$。

第二行 $n$ 个整数，第 $i$ 个表示 $d_i$。

第三行 $n - 1$ 个正整数，第 $i$ 个表示 $c_{i+1}$。

outputFormat: 一行一个整数表示答案。

tags: 凸完全单调性, wqs 二分


title: 「REOI-1」渺茫的希望

background: 威廉在与妖精们相处的日子里，留下了不少幸福的记忆。

description:
其中有一件令威廉记忆颇深的事情，便是活泼的少女们会时常的“抓住”威廉，让他来与她们一起读书。每逢此时，威廉总要开玩笑说“我脑筋超棒的哦，只要是五百年以上的古书尽管找我念”云云。但一来二去终究还是拗不过少女们的请求，半推半就的讲述一些以前的故事。长此以往，威廉在讲故事之余，会间或的用那些五百年以前的文字来和少女们玩一些“文字游戏”，游戏的规则如下：

威廉会给出一串由小写英文字母组成的字符串 $S$ ，其中每一个古文字便是由它的子串构成——如果我们说两个古文字不同，那么当且仅当这两个子串长度不同或长度相同且有任意一位不同——当两个不同的古文字拼凑在一起组成一个词语时，其音律、词义等各方面也会有所不同，于是威廉为了方便，就定义了一个“意境值”来衡量拼凑成的词语的质量。意境值的计算公式便是这两个本质不同子串在 $S$ 中出现的次数之和加上这两个本质不同子串的最长公共前缀的长度。

而当少女们把所有这些古文字拼凑成了一个句子后，威廉惊讶的发现，这个句子可以视作为任意两个古文字连边形成的完全图的最小生成树。他于是一鼓作气，推理出了这个句子的意境值的公式——这些最小生成树（因为最小生成树可能不唯一）的边权和。

其中，两个古文字的边权与她们组成的词语的意境值在数值上相等。

现在，威廉又在和少女们玩文字游戏了，威廉现在给出了一个字符串 $S$ ，但由于这是他临时起意写出的，他也不知道如果将它拼凑成一个句子，意境值究竟是多少——于是乎，威廉将求助的目光投向了你。

----

简要题意：

给定一个由小写英文字母组成的字符串 $S$ ，设在两个本质不同子串之间连边的权值为两个子串在 $S$ 中出现的次数之和加上这两个子串的最长公共前缀的长度，求对所有本质不同子串做最小生成树的边权之和（不含空串）。

inputFormat:
第一行一个整数 $n$ 。
接下来一行 $n$ 个字符表示威廉给出的字符串 $S$ 。

outputFormat: 一行一个整数，表示这个句子的意境值。

hint:
#### 样例解释 #1
![](https://cdn.luogu.com.cn/upload/image_hosting/fqjg81g9.png)

如图所示为一种最小生成树，边权和为 $15$。

#### 数据范围
对于 $10\%$ 的数据，$|S|\le 100$。
对于 $30\%$ 的数据，$|S|\le 1000$。
对于 $100\%$ 的数据，$1\le|S|\le 10^5$。


title: 迷宫寻路

description:
机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 $n\times m$ 矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于 $(1, 1)$ 的位置，问能否走到 $(n, m)$ 位置。

inputFormat:
第一行，两个正整数 $n,m$。

接下来 $n$ 行，输入这个迷宫。每行输入一个长为 $m$ 的字符串，`#` 表示墙，`.` 表示空地。

outputFormat: 仅一行，一个字符串。如果机器猫能走到 $(n, m)$，则输出 `Yes`；否则输出 `No`。


title: 跳跃机器人

description:
地上有一排格子，共 $n$ 个位置。机器猫站在第一个格子上，需要取第 $n$ 个格子里的东西。

机器猫当然不愿意自己跑过去，所以机器猫从口袋里掏出了一个机器人！这个机器人的行动遵循下面的规则：

- 初始时，机器人位于 $1$ 号格子
- 若机器人目前在 $x$ 格子，那么它可以跳跃到 $x-1, x+1, 2x$ 里的一个格子（不允许跳出界）

问机器人最少需要多少次跳跃，才能到达 $n$ 号格子。

inputFormat: 仅一行，一个正整数，表示 $n$。

outputFormat: 仅一行，一个正整数，表示最少跳跃次数。

hint:
#### 样例解释

第一组样例：
$1\to 2 \to 4\to 8 \to 16 \to 15 \to 30$

第二组样例：
$1\to 2\to 3\to6\to12\to24\to25\to 50$

第三组样例：
$1\to 2\to4\to8\to16\to32\to64$

第四组样例：
$1\to 2\to4\to8\to16\to32\to31\to62\to63$

请注意在本组样例中，$63$ 不能通过 $64-1$ 得到，因为格子总数为 $63$，没有第 $64$ 个格子。

#### 数据规模与约定

对于 $100\%$ 的数据，有 $1\leq n \leq 1000000$。


title: [JRKSJ R6] 第七学区

background:
![](https://cdn.luogu.com.cn/upload/image_hosting/jswrnw5w.png)

这个题本来是要拿到 Tree Diagram 上算的，但是 Tree Diagram 被某组织的宇宙射线射爆了，所以这个问题交给了你。

不过你不需要计算出可能出现的最坏情况，只需要解决原问题就可以了。

description: 给你一个长度为 $n$ 的序列 $a$，求其所有子区间的按位或和的和。

outputFormat: 一个整数，表示答案。答案对 $2^{64}$ 取模。


title: 简单九连环

background:
**提示：此题有大样例。**

**提示：本题中的九连环与传统九连环不同。**

九连环是一种源于中国的传统智力游戏。如图所示，九个的圆环套在一把“剑”上，并且互相牵连。

![](https://cdn.luogu.com.cn/upload/pic/17568.png)

在传统的九连环中，第 $k(k\ge 2)$ 个环可以装上“剑”（记为 $1$）或拆下“剑”（记为 $0$），当且仅当第 $k-1$ 个环在剑上，且再之前的环不在剑上；特别地，第 $1$ 个环可以任意上下。

本题中我们将会讨论更一般的情形，虽然这种简单九连环不一定可以在物理意义上造出。

description:
一个简单九连环，可以看作两个 `01` 串——规则串 $s$ 和状态串 $t$，满足 $|s|=|t|-1$。其中 $t_i = \texttt 1$ 表示第 $i$ 个环是装上的，$t_i = \texttt 0$ 表示第 $i$ 个环是拆下的。

$s$ 在同一局游戏中是不变的，而 $t$ 每步会变化一个位置上的值（从 `0` 变成 `1` 或从 `1` 变成 `0`）。简单九连环被拆下，当且仅当 $t_i$ 全是 `0`；简单九连环被装上，当且仅当 $t_i$ 全是 `1`。

简单九连环规定，$t_i$ 可以变化，当且仅当 $t_{1\sim i-1}$ 是 $s$ 的一个**后缀**。可以看出，传统的九连环就是 $s$ 为 `00...01` 的特殊情形。

给出一个 $s$，问从拆下状态到装上状态至少需要几步，答案对 $10^9+7$ 取模。

inputFormat:
第一行一个整数 $n$，表示 $s$ 的长度。**注意不是环的数量。**

第二行一个 `01` 串 $s$。

outputFormat: 一行一个整数，表示答案对 $10^9+7$ 取模后的值。

samples:
见附件中的 samples/rings3.in
见附件中的 samples/rings3.ans

samples:
见附件中的 samples/rings4.in
见附件中的 samples/rings4.ans


title: [CoE R5] 斑马王子

background:
#### 注意：此题 Sub #4 中 $opt_i=3$，可视作 $opt_i=0$。数据将稍后修复，修复后将另行通知。

#### UPD: 已修复。

description:
**题意简述**

有一长度为 $k+1$ 的数组 $s$，下标依次为 $0$ 到 $k$，初始时有 $s_i = 0 \ (0 \leqslant i \leqslant k)$。
接下来给定 $n$ 个非负整数二元组 $(l_i,\ r_i)$，记 $T = \bigcup\limits_{i = 1}^n [l_i,\ r_i] $，将所有符合 $i \in T \bigcap \mathbb{Z}$ 的 $s_i$ 赋值为 $1$。
在任意时刻，记 $S =\{ x |x \in \mathbb{Z} \bigwedge x \in [0,\ k] \bigwedge s_x = 0 \}$。接下来给定 $m$ 个非负整数三元组 $(opt_i,\ a_i,\ b_i)$。

当 $opt_i = 0$ 时，求：

$$t_i = \sum\limits_{x = a_i}^{b_i} \min\limits_{y \in S}(x \oplus y)$$

当 $opt_i = 1$ 时，将所有符合 $i \in [a_i,\ b_i] \bigcap \mathbb{Z}$ 的 $s_i$ 赋值为 $1$。

当 $opt_i = 2$ 时，将所有符合 $i \in [a_i,\ b_i] \bigcap \mathbb{Z}$ 的 $s_i$ 赋值为 $0$。

符号 $\mathbb{Z}$ 表示全体整数，$\oplus$ 表示异或。

---

**原版题面**

『斑马王子』统治着无垠的草原。

一条小河无息地流淌在草原的中央，与河流源头距离为 $y$ 的草地被赋予了 $y \ (0 \leqslant y \leqslant k)$ 的『膜力』。

第 $x \ (0 \leqslant x \leqslant k)$ 天，『斑马王子』的『潜力智商』为 $x$。

他会来到一片自己心仪的草地用膳，并以 $x \oplus y$ 的『智商』开始新的一天。

有一种叫『猎人』的生物，热衷于剥夺草原居民的生命。

他们初始时设立了 $n$ 个形如 $(l_i,\ r_i) \ (0 \leqslant l_i \leqslant r_i \leqslant k)$ 的营地，用『枪』屠杀着所有在 $[l_i,\ r_i]$ 中驻足的生灵。

作为『斑马王子』的得力大臣，你需要回答他的若干个问题，以保证草原的安全。

在风云变幻的草原上，会依次发生 $m$ 个形如 $(opt_i,\ a_i,\ b_i) \ (0 \leqslant a_i \leqslant b_i \leqslant k , \ opt_i \in \{0,\ 1,\ 2\})$ 的事件。

当 $opt_i = 1$ 时，事件 $i$ 代表猎人在 $[a_i,\ b_i]$ 中全部驻扎了新营地。

当 $opt_i = 2$ 时，事件 $i$ 代表斑马王子英勇的部队摧毁了 $[a_i,\ b_i]$ 中的全部营地。

而当 $opt_i = 0$ 时，斑马王子向你发出了灵魂拷问：

每一个问题中，『斑马王子』希望从第 $a_i$ 到第 $b_i$ 天 $(0 \leqslant a_i \leqslant b_i \leqslant k)$，在非『猎人』营地的草地用膳。『斑马王子』希望知道从第 $a_i$ 到 $b_i$ 天，『智商』之和的最小可能值 $t_i$。

你苦思冥想，忽然，『枪』的吼叫声撕裂了空气，如果不在 $1 \ sec$ 内回答问题 $\dots \dots$

inputFormat:
第一行输入整数 $n, \ m, \ k$。

接下来 $n$ 行，每行两个整数 $l_i, \ r_i$，表示『猎人』的一个营地。

接下来 $m$ 行，每行三个整数 $opt_i,\ a_i,\ b_i$，表示一组操作。

outputFormat:
对于第 $i$ 组操作 $(1 \leqslant i \leqslant m)$，当 $opt_i = 1$ 或 $opt_i = 2$ 时，不需要输出。

当 $opt_i = 0$ 时，当所有草地都属于猎人的营地时，输出一行 ``Death``,否则输出一行一个整数，表示 $t_i$。

hint:
**数据范围**

**本题采用捆绑测试。**

$\texttt{Subtask 1 (5 pts)}$：对于 $5\%$ 的数据，保证 $0 \leqslant n,m,k \leqslant 20$。

$\texttt{Subtask 2 (5 pts)}$：对于 $5\%$ 的数据，保证 $0 \leqslant n,m,k \leqslant 500$。

$\texttt{Subtask 3 (15 pts)}$：对于 $15\%$ 的数据，保证 $0 \leqslant n,m,k \leqslant 4000$。

$\texttt{Subtask 4 (5 pts)}$：对于 $5\%$ 的数据，保证 $opt_i = 0$。

$\texttt{Subtask 5 (70 pts)}$：无特殊限制。

对于 $100 \%$ 的数据， $0 \leqslant n,\ m,\ k \leqslant 2 \times 10^5$，$0 \leqslant l_i \leqslant r_i \leqslant k$，$0 \leqslant a_i \leqslant b_i \leqslant k$，$opt_i \in \{0,\ 1,\ 2\}$。


title: 「Wdoi-6」走在夜晚的莲台野

background:
[![](https://cdn.luogu.com.cn/upload/image_hosting/8brkt9is.png)](https://thwiki.cc/%E8%8E%B2%E5%8F%B0%E9%87%8E%E5%A4%9C%E8%A1%8C)

在科学世纪中，科学昌明，信息科技高度发达，但与此同时，想象力灭绝了，而无法解释的事物则被当做一个错误抹煞，无法解释的神秘也被否定。

宇佐见莲子（莲子）与玛艾露贝莉·赫恩（梅莉）成立了一个社团——秘封俱乐部。作为秘封俱乐部的成员，她们寻找着幻想的境界，在逐渐被人们所遗忘的世界中追寻着真正的美好。

她们的第一个活动，是探寻莲台野的结界缺口。

description:
### 简要题意

有 $x$ 个金色木板，$y$ 个银色木板，还有一个可放下 $z$ 个木板的空容器。每向容器中放入一个金色木板**后**，会丢弃容器内所有银色木板（需要确保在放金色木板前，容器里至少还能再放得下一个木板）。问是否存在一种方式，使得所有木板都被**放进过**容器中。

------
### 原始题意

在莲台野的入口，莲子与梅莉想要穿过现实与虚幻的结界，进入幻想乡。然而，穿越结界是有一定要求的。

具体而言，在结界边上会有若干个细长木板，其中有 $x$ 个是金色的木板，$y$ 个是银色的木板。梅莉通过自己能够看见结界的能力，发现了一个能够容得下 $z$ 个木板的容器，并且通过自己的潜意识得知了规则：
- 如果她们放进了一个金色的木板（需要确保在放金色木板前，容器里至少还能再放得下一个木板），那么**在容器中所有**银色的木板将被丢弃。
- 最后需要**所有**的木板都被**放入过**容器，结界的大门才将会被打开，即她们能够进入幻想乡。

现在已经是凌晨 2 点 27 分 41 秒，只有在凌晨 2 点 30 分前完成这个问题，她们才能进入幻想乡。现在，莲子和梅莉把这个问题交给了你，希望你能尽快帮她们做出回答——是否存在一种方案，使得她们能否进入幻想乡呢？

由于莲子和梅莉担心你在大半夜糊弄她们，因此她们会一共询问你 $T$ 次。

inputFormat:
- 第一行输入一个正整数 $T$，表示数据组数。
- 第二行开始，往下 $T$ 行，每行三个正整数 $x,y,z$，含义如题目所述。

outputFormat: 对于每次询问，输出一行，表示答案。若存在一种方案，则输出 `Renko`，否则输出 `Merry`。

samples:
Renko
Merry
Renko
Renko
Renko
Merry
Merry
Merry
Merry
Renko

hint:
### 样例解释

#### 样例 \#1

- 对于第一次询问，存在如下的方案：
  - 先放三个银色木板；
  - 再放一个金色木板；
  - 再放两个银色木板；
  - 再放一个金色木板；
  - 再放一个银色木板。
- 这样就可以使得每个木板都被放入过容器中，莲子和梅莉可以进入幻想乡，故输出 `Renko`。
- 对于第二次询问，显然不存在方案。
- 对于第三次询问，可以先放进去十个金色木板，再放进去十个银色木板。

#### 样例 \#2

本组样例符合 $\textbf{subtask 2}$ 的要求。

### 数据范围

**本题采用捆绑测试。**

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|c|}\hline
\textbf{Subtask} & \textbf{\textsf{分值}} & \bm{T\le } & \bm{x\le} & \bm{y\le} & \bm{z\le} & \textbf{Subtask \textsf{依赖}}\cr\hline
1 & 20 & 1 & 10 & 10 & 10 &-\cr\hline
2 & 30 & 10 & 10^3 & 10^6 & 10^3 &1\cr\hline
3 & 20 & 100 & 10^6 & 10^9 & 10^6 &2\cr\hline
4 & 30 & 1000 & 10^9 & 5 \times10^{17} & 10^9 &3\cr\hline
\end{array}
$$

对 $100\%$ 的数据，保证 $1 \le T \leq 1000$，$1 \leq x,z \leq 10^9$，$1 \leq y \leq 5 \times 10^{17}$。


title: 「Wdoi-6」华胥之梦

description:
### 简要题意

给定长度为 $n$ 的序列 $a$ 和常数 $c$。构造点数为 $n$ 的有向完全图 $G$ 使得边 $i\to j$（$i\neq j$）的长度为 $a_i-2a_j+c$，保证所有边权**非负**。

接下来给出 $q$ 次询问，每次给出一个点集，试找出图 $G$ 的一条最短的简单路径，满足其经过点集中所有点，并输出它的长度。

---
### 原始题意

梅莉做了一个梦，梦到自己穿越到了幻想乡的迷途竹林之中。醒来之后，她希望能够和莲子一起再次穿越境界，进入幻想乡。

但是，这一次，她看到了 $n$ 个世界，其中，第 $i$ 个世界的结界强度为 $a_i$。而世界之间**两两都有**通道相连，莲子和梅莉便是通过这些通道来进行世界之间的穿梭的。

为了避免错过幻想乡所在的世界，因此她们每到达一个世界，都会穿越结界。莲子和梅莉从第 $i$ 个世界中，通过一条通道，再穿越结界进入第 $j$ 个世界，需要使用的灵能为 $a_i-2a_j+c$（保证所需消耗的灵能非负），其中 $c$ 是一个常数，是梅莉每次穿越结界需要的额外灵能消耗。注意，这也意味着，从第 $i$ 个世界到第 $j$ 个世界，与第 $j$ 个世界穿越到第 $i$ 个世界所消耗的灵能，**可能是不同的**。

为了能够高效地找到幻想乡，她们会对你进行 $q$ 次询问，每次询问的时候会给出一个**集合**，表示她们想要进入的世界。由于世界众多，她们希望能够节省灵能，因此她希望你能求出所有包含这些世界的简单路径（即：同一条世界间的通道不会被走多次）中，消耗灵能值之和最少的路径。你只需告诉她们消耗灵能值之和最少为多少。

inputFormat:
- 第一行三个整数 $n,c,q$。
- 第二行 $n$ 个整数表示数列 $a$。
- 接下来 $q$ 行。每行第一个整数 $|S|$，即集合 $S$ 的大小。后面 $|S|$ 个互不相同的整数表示集合 $S$。

outputFormat: - 输出共 $q$ 行，每行一个整数，表示询问的答案。

hint:
### 样例解释

#### 样例 \#1

![](https://cdn.luogu.com.cn/upload/image_hosting/x3r2ucsl.png)

每两个点之间的边权如图所示。为了便于选手观察，边权的颜色与它所对应的边的颜色相同。

对于第一个询问，可以找到路径 $4\to 1$
；对于第二个询问，可以找到路径 $3\to 2\to 1$；对于第三个询问，可以找到路径 $2\to 4 \to 1\to 5$。可以证明，这三个方案分别是对应询问的最优方案。
#### 样例 \#2

该样例符合 $\textbf{Subtask 1}$ 的限制。

### 数据范围

**本题采用捆绑测试。**

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|c|}\hline
\textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n\le } & \bm{q\le} & \bm{\sum |S|\le} & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\cr\hline
1 & 30 & 10 & 10 & 10 & - &-\cr\hline
2 & 20 & 10^5 & 10^5 & 10^5 & \mathbf{A}&- \cr\hline
3 & 20 & 10^5 & 10^5 & 10^5 & \mathbf{B}&-  \cr\hline
4 & 30 & 10^6 & 10^6 &  10^6& -&1,2,3 \cr\hline
\end{array}
$$

- 特殊性质 $\bf A$：$a_i$ 单调递增。
- 特殊性质 $\bf B$：$a_i$ 全部相等。

对于 $100\%$ 的数据，保证 $1 \leq S_i \leq n \leq 10^6, 1\leq \sum |S|,q \leq 10^6, 1 \le a_i,c \le 10^9$。


title: 「Wdoi-6」最澄澈的空与海

background:
[![](https://cdn.luogu.com.cn/upload/image_hosting/hiekh6t5.png)](https://thwiki.cc/%E5%8D%AF%E9%85%89%E4%B8%9C%E6%B5%B7%E9%81%93_%EF%BD%9E_Retrospective_53_minutes.)

广重号载着二人向东飞驰。毫无噪音，毫无摇摆，只是一个劲向东飞驰。在“万景幕”装置之下，尽管是全地下的卯酉东海道，乘客们也能饱览美丽的富士山和太平洋的景色。

但是，从这列卯酉新干线『广重』上看到的极富日本风味的美丽情景，对于梅莉来说，只不过是无趣的视觉刺激罢了。高动态范围的影像也好，极富日本风味的情景也好，都敌不过真正的天空的颜色。

身与华落，心将香飞。即便肉体会像花朵一样终有一天凋落，但心却可以如花香一般飘往远方。

「梅莉，你看，天上的星星呦。」

description:
### 简要题意

给定 $2n$ 个点、$m$ 条边的[二分图](http://oi-wiki.com/graph/bi-graph/#_1)（可能有重边），左部点与右部点个数相同，判断其完美匹配数量是否**恰好**为 $1$。是则输出 `Renko`，否则输出 `Merry`。

> **注**：完美匹配是指，从边集中选出 $n$ 条边，这些边的顶点组成的点集恰好覆盖了所有的 $2n$ 个点。

---
### 原始题意

在夜里，莲子与梅莉来到了东京的海边，躺在沙滩上，欣赏着澄澈的天空与大海，数起了天上的星星。

在这些星星之中，有 $n$ 个星星 $\{a_i\}$，是莲子先发现的，被称为莲子星；而又有 $n$ 个星星 $\{b_i\}$，是梅莉先发现的，被称为梅莉星。由于她们心有灵犀，这两批星星之间**不存在交集**。

她们发现，有一些莲子星，与一些梅莉星之间恰好存在运动关系。具体而言，这些关系一共有 $m$ 组，每一组关系形如 $(u_i,v_i)$，也就是说第 $u_i$ 颗莲子星与第 $v_i$ 颗梅莉星之间存在运动关系。这些运动关系有可能重复。

这让莲子和梅莉非常好奇。作为专攻超统一物理学的女大学生，莲子认为，如果认为这些星星的运动是**和谐**的，那么她应当能够从这 $m$ 个运动关系中，找出若干个运动关系，使得**每颗**星星**都被**这些运动关系**包含**的同时，不会有一颗星星**被包含在两个**运动关系之中。

然而，梅莉认为，**和谐**的运动可能是不存在的，更何况即使莲子找到了**和谐**的运动，莲子也无法确保这种和谐运动的**唯一性**。两种和谐运动不同，当且仅当选取出的两组运动关系中，存在至少一个运动关系，是不相同的。

因为意见不合，她们于是打情骂俏了一顿。莲子于是记下了她们所看到了星星和她们之间的运动关系，并且找到了已经证明了 P=NP 的你，希望你能告诉她们，最后是谁正确呢？

inputFormat:
第一行输入一个正整数 $T$ 表示数据组数，对于每一组数据：

- 第一行一个整数 $n$，代表莲子和梅莉每个人所先发现的星星的数量。
- 第二行一个整数 $m$，代表运动关系的数量。
- 接下来 $m$ 行，每行两个整数 $u_i,v_i$，表示第 $u_i$ 颗莲子星，与第 $v_i$ 颗梅莉星之间，存在运动关系。

outputFormat:
- 如果这些星星中存在唯一的和谐运动，输出 `Renko`。
- 如果这些星星中不存在和谐运动，或者有不唯一的和谐运动方式，输出 `Merry`。

hint:
### 样例解释

#### 样例 \#1

![](https://cdn.luogu.com.cn/upload/image_hosting/6skoily9.png)

如图所示，存在唯一的方案：$\{1\to 1,2\to 5,3\to 2,4\to 3,5\to 4\}$。

### 数据范围

**本题采用捆绑测试。**

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|}\hline
\textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n\le } & \bm{m\le} & \textbf{\textsf{特殊性质}} & \textbf{Subtask \textsf{依赖}}\cr\hline
1 & 10 & 10 & 10 & - & - \cr\hline
2 & 20 & 300 & 4\times 10^4 & - & 1\cr\hline
3 & 20 & 10^5 & 5 \times 10^5 & \mathbf{A} & - \cr\hline
4 & 20 & 10^5 & 2 \times 10^5 & \mathbf{B} & - \cr\hline
5 & 30& 10^6 & 2\times 10^6 & - & 2,3,4 \cr\hline
\end{array}
$$

- 特殊性质 $\mathbf{A}$：保证对于第 $i$ 颗莲子星，与第 $i$ 颗梅莉星之间存在运动关系。
- 特殊性质 $\mathbf{B}$：保证 $m=2n-1$。

对于 $100\%$ 的数据，保证 $1 \le u_i,v_i\le n \le 10^6$，$1 \le m \le 2 \times 10^6$，$1 \leq T \leq 5$ 且对于每个测试点，$\sum m \leq 4 \times 10^6$。

对于 $\rm Subtask\ 5$，时间限制为 $3$ 秒。其它测试点时间限制为 $1$ 秒。


title: 「Wdoi-6」未知之花魅知之旅

background:
[![](https://cdn.luogu.com.cn/upload/image_hosting/glirwa55.png)](https://thwiki.cc/%E6%9C%AA%E7%9F%A5%E4%B9%8B%E8%8A%B1_%E9%AD%85%E7%9F%A5%E4%B9%8B%E6%97%85)

位于太平洋板块和亚欧板块消亡边界的日本，是世界上最多发地震的一个国家之一。2011 年 3 月 11 日，日本时间下午 2 时 46 分 18 秒，一场里氏 9 级的地震袭击了这个国家，随之而来的，是超过 10 米高的巨大海啸。妻离子散，家破人亡，是对这一悲剧性事件的最好描述。

2011 年 5 月，东方 Project 的创作者 ZUN，为地震中的灾民谱写了一张专辑，叫做《未知之花，魅知之旅》，所筹得的善款都被捐赠用于救灾赈灾之中。

-----

而到了近未来的科学世纪，莲子和梅莉在一次聊天之中，又谈论到了这场大地震。这场地震对传统宗教的摧残程度也颇深，数千所神社不同程度遭受到了损毁，也有不少神社的主殿全毁或者半毁。甚至就连外界的博丽神社，也因此被摧毁。

莲子与梅莉决定动身，前往外界的博丽神社，进入幻想乡中，通报这一消息。

description:
### 简要题意

称一个长度为 $n$ 的正整数数列是「$k$ - 好」的，当且仅当它满足以下条件：

- 对于 $1< i< n$，满足 $a_{i-1},a_i,a_{i+1}$ 中最大的一个等于其他两个之和。
- 所有元素都不小于 $k$。

$T$ 组询问，每次询问给定 $(a_0,a_1,x,y,k)$，问是否存在「$k$ - 好」数列（长度不小于 $2$），前两项为 $a_0,a_1$ 并且有相邻两项依次为 $x,y$。

-----

### 原始题意

原本就门可罗雀的博丽神社，在地震之后，更显荒凉。莲子与梅莉紧赶慢赶来到了博丽神社，只看到了倒塌的鸟居。由于神社过于荒凉，莲子和梅莉决定先将神社给好好打扫一番，再进入幻想乡。

具体而言，神社中有若干个物件等待被整理，每个物件都有一个正整数魅力值。可以认为，每种魅力值的物件都有**足够多**个。从被遗落的绘马中，莲子得知了，在被地震摧毁前的博丽神社中的物件，应当具有如下特点：

- 每个物件都有一个**不小于** $k$ 的魅力值。
- 三个相邻物件的**最大**魅力值，是其他两个物件的魅力值**之和**。
- 前两个物件的魅力值分别为 $a_0, a_1$。
- 存在**相邻**的两个物件，魅力值依次为 $x, y$。

莲子和梅莉认为，如果能够从所有物件中选出一些进行排列，并满足如上特点的话，那么这样的神社是**美观**的，不会让她们一进入幻想乡就被灵梦退治。

很显然，由于物件的散佚，莲子和梅莉可能无法通过这些信息来使得神社变得**美观**。莲子和梅莉找到了你，希望你能告诉她们，在这样的规则下是否存在一种让神社变得**美观**的方案。

由于灵梦退治得太狠，她们担心自己的生命安全，因此她们会对你询问 $T$ 次，以确保你不是在糊弄她们。

inputFormat:
第一行输入一个正整数 $T$，表示数据组数，对于每一组数据：

- 每行输入 $5$ 个正整数，以空格隔开，分别为 $a_0,a_1,x,y,k$，含义如题目所述。

outputFormat: - 对于每一组数据，输出一行 `yes` 或 `no`，即是否存在一种可以使得神社变得**美观**的方法。

hint:
### 样例解释

- 针对第一次询问，$a_0=2,a_1=3$，莲子和梅莉可以将物件如下排列构造：$2,3,5,2,7,9,2,11,\dots$，其中 $a_5=7,a_6=9$，从而存在方案让神社变得美观。
- 针对第二次询问，$a_0=4,a_1=9$，莲子和梅莉可以将物件如下排列构造：$4,9,5,4,1,3,2,5,3,8,\dots$，其中 $a_6=2,a_7=5$，从而存在方案让神社变得美观。
- 针对第三次询问，由于要求 $a_i \geq k=2$，第二次询问中的方法失效，同时也可以证明不存在让神社变得美观的方法。
- 针对第四次询问，要求构造出的 $x=1,y=2$ 都小于等于 $3$，从而无法让神社变得美观。
- 针对第五次询问，显然 $a_0=7,a_1=9$ 就已经符合让神社变得美观的要求了。

### 数据范围

**本题采用捆绑测试。**

令 $n=\max(a_0,a_1,x,y,k)$。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|}\hline
\textbf{Subtask} & \textbf{\textsf{分值}} & \bm{T\le } & \bm{n\le }  & \textbf{\textsf{特殊性质}} & \textbf{Subtask \textsf{依赖}}\cr\hline
1 & 10 & 10 & 10  & - & - \cr\hline
2 & 20 & 300 & 1000 & \mathbf{A} & - \cr\hline
3 & 10 & 300 & 10^9 & \mathbf{B} & - \cr\hline
4 & 20 & 300 & 10^8 & \mathbf{C} & 1,2 \cr\hline
5 & 40 & 10^5 & 10^9 & - & 3,4 \cr\hline
\end{array}
$$

- 特殊性质 $\mathbf{A}$：每次询问的 $k$ 相同。
- 特殊性质 $\mathbf{B}$：$k=1$。
- 特殊性质 $\mathbf{C}$：$\sum n \leq 10^8$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^9,1 \leq T \leq 10^5$。


title: 「HGOI-1」Binary search

background: $\text{bh1234666}$ 正在学习[二分查找](https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/10628618?fr=aladdin)。

description:
众所周知二分查找的 $\text{mid}$ 在计算时可以取 $\lfloor\dfrac{l+r}{2}\rfloor$ 或者 $\lceil\dfrac{l+r}{2}\rceil$，于是有选择困难症的 $\text{bh1234666}$ 同学在自己的二分查找代码中加入了随机化，每次随机选取其中的一个作为 $\textit{mid}$。

注意，选取不同的 mid 其他参数也会受到影响，请以代码为准。

现在 $\text{bh1234666}$ 给你了二分查找使用的序列（保证为单调递增）以及他想要寻找的数（保证在序列内），他想知道在运气最好的情况下循环需要进行几次（即代码中 $\textit{cnt}$ 的可能的最终值的最小值）。

循环：
```cpp
int find(int *num,int x,int len)
{
	int l=0,r=len-1,mid,cnt=0,w;
	while(l<r)
	{
		cnt++;
		w=rand()%2;
		mid=(l+r+w)/2;
		if(num[mid]-w<x) l=mid+!w;
		else r=mid-w;
	}
	return mid;
}
```
递归：
```
int cnt;
int get(int *num,int x,int l,int r)
{
	if(l==r) return l;
	cnt++;
	int w=rand()%2;
	int mid=(l+r+w)/2;
	if(num[mid]-w<x) return get(num,x,mid+!w,r);
	else return get(num,x,l,mid-w);
}
int find(int *num,int x,int len)
{
	cnt=0;
	return get(num,x,0,len-1);
}
```
注：以上两代码完全等价。

在此对上述代码中的 $w$ 的作用做进一步阐释。

例如对于区间 $[0,7]$，有 $8$ 个成员。虽然 $mid$ 的取值会因为 $w$ 的取值改变而改变，但是最终确定的区间一定是 $[0,3]$ 或 $[4,7]$，选手可以就上述代码自行模拟。

对于区间 $[0,6]$，有 $7$ 个成员。$\textit{mid}$ 的取值与 $w$ 的取值无关，但是 $l$ 和 $r$ 的取值会受到 $w$ 的影响，最终确定的区间可能是 $[0,2]$，$[3,6]$（$w=1$）或 $[0,3]$，$[4,6]$（$w=0$）。

inputFormat:
第一行给出一个整数 $n$ 表示序列长度。

第二行给出单调递增的 $n$ 个整数表示 $\text{bh1234666}$ 的序列。

第三行一个整数 $q$ 表示询问的次数。

接下来 $q$ 行每行一个整数表示需要查询的数字。

outputFormat: 对于每个询问回答一个整数，表示最小的循环次数。

hint:
### 样例 1 解释

找 $4$：

取 $[1,5]$。

取 $[1,3]$。

取 $[3,3]$（退出循环）。

### 样例 2 解释

查询 $10$ 的位置。

$$
[1,13] \stackrel{w=0}{\longrightarrow} [1,7]\stackrel{w=0}{\longrightarrow}[5,7] \stackrel{w=1}{\longrightarrow} [5,5]
$$

### 数据范围及约定
本题采用**捆绑测试**，共有 $3$ 个 $\text{subtask}$，最终分数为所有 $\text{subtask}$ 分数之和。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{Task} & \textbf{Score} & \text{特殊限制} \cr\hline
1 & 25 & n \le 20 \cr\hline
2 & 35 & n=2^k(k \in \mathbf{N}) \cr\hline
3 & 40 &  \cr\hline
\end{array}
$$

对于 $100\%$ 的数据，保证 $1 \le n \le 2^{20}$，$1 \le q \le 100$，$1 \le num_i \le 10^9$。

本题有 [extra sub](https://www.luogu.com.cn/problem/P8487)。


title: 「SvR-1」Don't Mozheng. /oh

background:
**Problem Number:** $\textit{58}$

在 Guluo Academic 群中，大家正在魔怔。

![](https://cdn.luogu.com.cn/upload/image_hosting/iphmcxwz.png)

洛谷博客上的《魔怔导论》：<https://www.luogu.com.cn/blog/supervise/how-to-get-a-mz>。

需要《魔怔导论》（目前更新至 v1.1.1 版本）的 PDF 请于下方「**题目附件**」处下载。

description:
你得到了 $n$ 条信息，这些信息共有三种类型（注意 $\texttt<\textit{str}\texttt>$ 描述一个名为 $str$ 的字符串，**该字符串不含空格、字符 $\texttt:$ 与 $\texttt/$**，不含两边的尖角括号）：

1. 形如 $\texttt<\textit{str}\texttt{>:}$。意为**接下来一行的一条信息**是名为 $str$ 的用户发的。
2. 形如 $\texttt{/<}str\texttt>$。意为一条名称为 $str$ 的**表情信息**。
3. 形如 $\texttt<\textit{str}\texttt>$。意为一条内容为 $str$ 的文字信息。

你经过长期观察，发现名称为 $\texttt{oh}$ 和 $\texttt{hsh}$ 的**表情信息**具有魔怔的意味。

并且在一段对话中：

- 一个 $\texttt{oh}$ 表情会增加 $a$ 的魔怔值。
- 一个 $\texttt{hsh}$ 表情会增加 $b$ 的魔怔值。
- **其他的任何信息都不会影响魔怔值，魔怔值初始为 $0$**。

现在你需要对于这些信息，计算出总的魔怔值。

inputFormat:
第一行三个整数 $n,a,b$，表示共有 $n$ 条信息，$a,b$ 意义如题述。

接下来 $2\times n$ 行，描述每条信息：

- 第一行是第 1 类信息。
- 第二行是第 2 类**或**第 3 类信息。

outputFormat: 仅一行一个整数，即总的魔怔值。

samples:
7 1 2020
wop:
/yueliang
eoq:
wop_loushang
wop:
eoq_npy_when
eoq:
/oh
dek:
/oh
rif:
NOI2022_rp_++
rif:
/hsh

hint:
#### 样例 1 说明

![](https://cdn.luogu.com.cn/upload/image_hosting/mbfgnv8i.png)

如图所示。

#### 数据规模与约定

**本题采用捆绑测试。**

记 $l$ 表示输入中单行信息的最大长度。

$$
\newcommand{\arraystretch}{1.5}
\begin{array}{c|c|c|c}\hline\hline
\textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值} \\\hline
\textsf{1} & \le 10 & - & 20 \\\hline
\textsf{2} & \le 100 & - & 20 \\\hline
\textsf{3} & \text{无特殊限制} & \text A & 20 \\\hline
\textsf{4} & \text{无特殊限制} & - & 40 \\\hline\hline
\end{array}
$$

- 特殊性质 $\text{A}$：输入不含有第 3 类信息。

对于 $100\%$ 的数据，有 $1\le n\le 10^4$，$1\le l\le 50$，$1\le a,b\le 10^3$。


title: [ZJOI2022] 树

background:
一年一度的 ZJOI 又要举办了，但是老牌出题人九条可怜突然有急事要回趟英国。

“就交给你们啦！一定没有问题 desu！”，说完可怜就跑远了。

忍，爱丽丝，绫和阳子目送着远去的可怜，感到有点茫然，毕竞，ZJOI 只剩不到三星期了。

既然是可怜酱留下的任务，那我们一定要努力完成了，毕竟我才是姐姐”，爱丽丝说。

于是众人就开始热火朝天地出题了，“希望这是第一次也是最后一次了” 大家都不约而同地想。

同时，题目主角就定为九条可怜了！

description:
九条可怜是一个喜欢树的女孩子，她想生成两棵均有 $n$ 个节点的树。

第一棵树的生成方式是：

1. 节点 $1$ 作为树的根。
2. 对于 $i \in [2, n]$，从 $[1, i - 1]$ 中选取一个节点作为 $i$ 的父亲。

第二棵树的生成方式是：

1. 节点 $n$ 作为树的根。
2. 对于 $i \in [1, n - 1]$，从 $[i + 1, n]$ 中选取一个节点作为 $i$ 的父亲。

九条可怜希望对于任意 $i \in [1, n]$，若第一棵树中的节点 $i$ 为叶子，那么第二棵树中的节点 $i$ 为非叶子；若第一棵树中的节点 $i$ 为非叶子，那么第二棵树中的节点 $i$ 为叶子。一个节点被称为叶子当且仅当没有节点的父亲是它。

九条可怜希望你统计生成两棵树的方案数是多少。具体地，你需要对于所有 $n \in [2, N]$ 都计算方案数。两种方案不同当且仅当存在一棵树中的一个节点 $i$，两种方案中它的父亲不同。因为答案可能很大，你只需要输出答案对 $M$ 取模后的结果。

inputFormat: 第一行输入两个整数 $N, M$，表示树的节点上限以及模数。

outputFormat:
输出 $N - 1$ 行，每行一个整数。

具体地，第 $i$ 行输出 $n = i + 1$ 时的答案对 $M$ 取模后的值。

samples:
见附件中的 tree/tree_ex2.in
见附件中的 tree/tree_ex2.ans


title: [ZJOI2022] 众数

description:
九条可怜是一个有超能力的女孩子，但她的超能力只能作用于一些奇怪的事情上。

有一天，可怜得到了一个序列 $a_1, a_2, \ldots, a_n$，她可以对这个序列使用一次超能力: 选择一个区
间 $[l, r]$（$1 \le l \le r \le n$）和一个整数 $k \in [-{10}^9, {10}^9]$，将区间内的所有数 $a_l, a_{l + 1}, \ldots, a_r$ 加上 $k$。

九条可怜很喜欢长得比较一致的序列，因此她希望最终的序列众数的出现次数尽可能多。给出序列 $a$，你需要输出最终序列的众数出现次数的最大值，并输出这个众数的所有可能取值。注意对于一个序列，众数的取值可能不止一个。

inputFormat:
输入包含多组数据，第一行输入数据组数 $T$。

对于接下来的每组数据，第一行输入序列长度 $n$，第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

outputFormat:
对于每组数据，第一行输出最终序列众数的出现次数的最大值。

假设这个众数有 $k$ 种不同的可能取值，则接下来 $k$ 行，从小到大输出这些取值。

samples:
见附件中的 mode/mode_ex2.in
见附件中的 mode/mode_ex2.ans


title: [ZJOI2022] 简单题

description:
九条可怜是一个喜欢出简单题的女孩子。顾名思义，简单题就是题目里面出现了很多 “简单”。

可怜首先给出一张简单连通无向图，每条边有一个正整数边权。特别地，可怜保证图上任意两个简单环的边权和相等。

后来可怜想要隐藏图里美好的性质，她将其中一部分边的权值改成了新的权值。因此，修改之后原本美好的性质可能就不存在了。

现在她给出修改后的图，同时给出多组询问，每次询问两点 $S, T$ 间所有简单路径权值和。因为答案可能很大，你只需要输出答案对 $998244353$ 取模的结果。

具体地，简单图指不存在重边和自环，简单环和简单路径指不包含重复节点。

inputFormat:
第一行读入三个整数 $n, m, q$。

接下来 $m$ 行，每行三个整数 $u, v, w$，代表一条权值为 $w$ 的无向边 $(u, v)$。

接下来 $q$ 行，读入 $q$ 组询问，每组询问读入一行两个整数 $S, T$。

outputFormat: 对于每个询问，输出一行一个整数代表答案对 $998244353$ 取模后的结果。

samples:
见附件中的 simple/simple_ex2.in
见附件中的 simple/simple_ex2.ans

hint:
对于所有测试点，满足 $1 \le n, q \le 5 \times {10}^5$，$n - 1 \le m \le 6.4 \times {10}^5$，$1 \le u, v, S, T \le n$，$1 \le w \le {10}^6$，无重边自环，图连通。

每个测试点的具体限制见下表：

| 测试点编号 | 特殊限制 1 | 特殊限制 2 |
|:-:|:-:|:-:|
| $1$ | $m < n$ | 保证存在经过所有点的简单路径 |
| $2$ | $m < n$ | 无 |
| $3 \sim 5$ | 任意一个点不在 $\ge 2$ 个简单环上 | 保证存在经过所有点的简单路径 |
| $6 \sim 8$ | 任意一个点不在 $\ge 2$ 个简单环上 | 无 |
| $9 \sim 14$ | 无 | 保证存在经过所有点的简单路径 |
| $15 \sim 20$ | 无 | 无 |


title: 「FAOI-R1」完美的平方数 (C)

description: 给定一个正整数 $m$。现有 $Q$ 个询问，每个询问给定一个正整数 $n$，要求你从 $1,4,9,16,\ldots,m^2$ 中取出若干个数（**同一个数可以取出多次**），使它们的和**恰好**为 $n$。问最少取出多少个数？（如果无解，则输出 $-1$）

inputFormat:
**本题有多组数据。**

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

对于每组数据：

第一行，两个正整数 $m,Q$。

下面 $Q$ 行，每行一个正整数 $n$。

outputFormat: 对于每组数据的每个询问，输出一行一个正整数，表示答案。


title: [Ynoi2004] tars2

description:
你需要维护平面上的整点，每个点初始有点权 $0$，共 $m$ 次操作。

修改操作：给定 $x,y,d,w$，将满足 $|X-x|<d,|Y-y|<d$ 的整点 $(X,Y)$ 的点权增加 $w\cdot(d-\max(|X-x|,|Y-y|))$；

查询操作：给定 $x_1,x_2,y_1,y_2$，查询满足 $x_1\le X\le x_2,\;y_1\le Y\le y_2$ 的整点 $(X,Y)$ 的点权之和，答案对 $2^{30}$ 取模。

inputFormat:
第一行一个整数 $m$，接下来 $m$ 行，每行表示一个操作。

修改操作表示为 `1 x y d w`；

查询操作表示为 `2 x1 x2 y1 y2`。

outputFormat: 对每个查询操作，输出一行，包含一个整数，表示取模后的答案。


title: [Ynoi2004] 2stmst

description:
已知 $n$ 个顶点的有根树，以及 $m$ 个二元组 $(x_i,y_i)$，其中 $x_i,y_i$ 是树的顶点。

对于树的顶点 $a,b$，定义 $D(a,b)$ 为：在以 $a$ 为根的子树中，但不在以 $b$ 为根的子树中的顶点个数。

你需要求出以这些二元组为顶点的完全图的最小生成树，其中 $(x_i,y_i)$ 和 $(x_j,y_j)$ 之间的边权是 $D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i)$。

inputFormat:
第一行两个数表示 $n,m$。

之后一行 $n-1$ 个数，其中第 $i$ 个数表示编号为 $i+1$ 的节点的父亲 $f_{i+1}$，保证 $f_{i+1}< i+1$。

之后 $m$ 行，第 $i$ 行两个数 $x_i,y_i$，表示一个给定的二元组。

outputFormat: 输出一个整数，表示最小生成树的边权和。

hint:
Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078&djq_cpp，Data：ccz181078

样例解释：

最小生成树包含边 $(1,4,1),(2,3,3),(2,4,3)$，三元组表示第一个二元组的编号，第二个二元组的编号，边权。边权和为 $7$。

数据范围：

对于 $100\%$ 的数据，满足 $1\le n\le 10^6,1\le m\le 10^5$。对任意 $i=1,2,\dots n-1$，满足 $1\le f_{i+1}<i+1$。对任意 $i=1,2,\dots m$，满足 $1\le x_i,y_i\le n$。


title: [Ynoi2004] rsxc

description:
给定一个长为 $n$（$1\le n\le 6\times 10^5$）的非负整数序列 $a_0,a_1,\dots,a_{n-1}$（$0\le a_i<2^{30}$）。

有 $q$ 个询问（$1\le q\le 10^6$）。

每次询问给出两个整数 $l,r$（$0\le l\le r<n$），求有多少对整数 $(x,y)$ 满足：

 - $l\le x\le y\le r$；
 - $\forall i,j\in S\ :i\oplus j\in S$，其中 $S:=\{a_k\}_{k=x}^y$。

inputFormat:
由于本题数据较多，您不需要输入输出，请完善以下程序中的 `init(int, int, vector<int>)` 和 `solve(int, int)` 函数，并提交。正解不依赖于其模板。

```cpp
#include <bits/stdc++.h>
using namespace std;

void init(int n, int q, vector<int> a) {
  // implement...
}

long long solve(int l, int r) {
  // implement...
}

int main() {
  int n, q;
  uint64_t s;
  cin >> n >> q >> s;
  string r;
  cin >> r;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    for (int s = 5 * i; s < 5 * i + 5; s++)
      a[i] = (a[i] * 64 + (int)(r[s]) - (int)('0'));
  init(n, q, a);
  uint64_t state = 0;
  auto splitmix64 = [&](uint64_t v) {
    uint64_t z = (v + 0x9e3779b97f4a7c15);
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
    z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
    return z ^ (z >> 31);
  };
  mt19937_64 rng(s);
  for (int i = 0; i < q; i++) {
    int l = (rng() ^ state) % n;
    int r = (rng() ^ state) % n;
    long long ans = solve(min(l, r), max(l, r));
    state = splitmix64(state + ans);
    if ((i + 1) % (1 << 15) == 0)
      cout << state << endl;
  }
  cout << state << endl;
}
```

hint:
Idea：Powerless，Solution：ccz181078&noip&w33z，Code：w33z，Data：w33z

对于 $100\%$ 的数据，$1\leq n\le 6\times 10^5,1\le q\leq 10^6$，$0 \le a_i < 2^{30}$，$0 \le l \le r < n$。


title: [ZJOI2022] 面条

background:
忍，爱丽丝，绫和阳子一众千辛万苦地总算出好了第一试，按原先计划，可怜会出第二试。

“不好了，可怜给我发信息说她降落后被拉去隔离 30 天了，没有电脑，出不了题”，绫突然收到了不幸的消息。

“那咋办？没 idea 了，编不出来了啊！” 众人慌作一团。

看了看日期，离 ZJOI 还有一周。

欲知后事如何，请看下回分解。

description:
九条可怜是一个喜欢吃拉面的女孩子。

有一天她去吃拉面，她发现拉面师傅为她拉的是一个长度为 $n$ 的面条，$n$ 保证是偶数，一开始第 $i$ 个位置调料的数量是 $a_i$。

如下过程称为一次 “拉面”：

1. 将面条对折，面条的长度会变成 $\frac{n}{2}$，第 $i$ 个位置的调料数量会变为原来第 $i$ 个位置的调料与第 $n - i + 1$ 个位置的调料数量之和，如果新面条第 $i$ 个位置的调料数量为 $b_i$，那么满足 $b_i = a_i + a_{n - i + 1}$。
2. 将面条拉回原来的长度 $n$，每个位置会变为两个位置，并且调料数量会均分，如果现在的第 $i$ 个位置的调料数量是 $a'_i$，那么 $a'_i = \frac{1}{2} \times b_{\left\lceil \frac{i}{2} \right\rceil}$。

现在对于一个固定的 $x$，你需要回答 $q$ 个询问，每次面条经过 $k$ 次 “拉面” 后，第 $x$ 个位置的调料数量。你只需要求出答案对 $998244353$ 取模的结果。具体地，即如果答案的最简分数表示为 $\frac{a}{b}$，输出 $a \times b^{-1} \bmod 998244353$。

inputFormat:
第一行输入三个正整数 $test, T, seed$，代表测试点编号，数据组数和生成种子。

接下来输入 $T$ 组数据，每组数据包含两行。

第一行输入四个正整数 $n, q, x, k_{\mathrm{max}}$，代表这组数据中面条的长度，询问的个数，询问的位置和生成询问中 $k$ 的上限。

第二行输入 $n$ 个非负整数，第 $i$ 个整数 $a_i$ 代表初始面条第 $i$ 个位置的调料数量。

为了避免大量的输入与输出，$q$ 个询问由我们提供的一个生成器生成。具体地，我们提供一个由 C++ 书写的代码框架 `noodle_template.cpp` 供选手使用，见附录，同时在这里我们做一定量的说明：

首先我们从数据中依次读入两个 $32$ 位整型变量 $\mathit{test}, T$，一个无符号 $64$ 位长整型变量 $\mathit{seed}$。接下来循环 $T$ 次，代表 $T$ 组数据。

在每次循环中，我们对一组数据进行计算。首先依次读入三个 $32$ 位整型变量 $n, q, x$，一个 $64$ 位整型变量 $k_{\mathrm{max}}$。接下来读入 $n$ 个 $32$ 位整型变量放入数组 $a_1, \ldots, a_n$ 中。

接下来是生成 $q$ 个询问的部分，每次调用 `rd()` 函数，将 $\mathit{seed}$ 作为引用参数传入，将返回值（返回值为无符号 $64$ 位长整型）对 $k_{\mathrm{max}}$ 取模的结果作为该次询问的参数 $k$，注意到 $\mathit{seed}$ 也会被修改。

outputFormat: 输出 $T$ 行，每行一个整数代表该组数据的答案。具体地，假设该组数据有 $q$ 个询问，令第 $i$ 个询问的答案为 $\mathrm{Ans}_i$，那么需要你输出 $\bigoplus_{i = 1}^q (\mathrm{Ans}_i \cdot i)$，**注意这里不需要取模**。$\bigoplus$ 指按位异或运算符。

samples:
见附件中的 noodle/noodle_ex2.in
见附件中的 noodle/noodle_ex2.ans


title: [ZJOI2022] 计算几何

description:
九条可怜是一个喜欢计算几何的女孩子，她画了一个特别的平面坐标系，其中 $x$ 轴正半轴与 $y$ 轴正半轴夹角为 $60$ 度。

从中，她取出所有横纵坐标不全为偶数，且满足 $-2 a + 1 \le x \le 2 a - 1$，$-2 b + 1 \le y \le 2 b - 1$，$-2 c + 1 \le x + y \le 2 c - 1$ 的整点。

可怜想将其中一些点染色，但相邻的点不能同时染色。具体地，对于点 $(x, y)$，它和 $(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y), (x + 1, y - 1), (x - 1, y + 1)$ 六个点相邻，可结合样例解释理解。

可怜想知道在这个规则下最多能将多少点染色，以及染最多点的染色方案数。由于后者值可能很大，对于染色方案数，你只需要输出对 $998244353$ 取模后的结果。**注意不需要将最多染色点数取模。**

inputFormat:
第一行一个整数 $T$ 代表数据组数。

接下来 $T$ 行，每行三个整数 $a, b, c$ 代表一组数据。

outputFormat: 输出共 $T$ 行，每行两个整数，代表最多能染的点数（**不取模**）和方案数对 $998244353$ 取模的结果。


title: [ZJOI2022] 深搜

description:
九条可怜是一个喜欢算法的女孩子，在众多算法中她尤其喜欢深度优先搜索（DFS）。

有一天，可怜得到了一棵有根树，树根为 $\mathit{root}$，树上每个节点 $x$ 有一个权值 $a_x$。

在一棵树上从 $x$ 出发，寻找 $y$ 节点，如果使用深度优先搜索，则可描述为以下演算过程：

1. 将递归栈设置为空。
2. 首先将节点 $x$ 放入递归栈中。
3. 从递归栈中取出栈顶节点，如果该节点为 $y$，则结束演算过程；否则，如果存在未访问的直接子节点，则以均等概率随机选择一个子节点加入递归栈中。
4. 重复步骤 3，直到不存在未访问的直接子节点。
5. 将上一级节点加入递归栈中，重复步骤 3。
6. 重复步骤 5，直至当前一级节点为 $x$，演算过程结束。

我们定义 $f(x, y)$ 合法当且仅当 $y$ 在 $x$ 的子树中。它的值为从 $x$ 出发，对 $x$ 的子树进行深度优先搜索寻找 $y$ 期间访问过的所有节点（包括 $x$ 和 $y$）权值最小值的期望。

九条可怜想知道对于所有合法的点对 $(x, y)$，$\sum f(x, y)$ 的值。你只需要输出答案对 $998244353$ 取模的结果。具体地，如果答案的最简分数表示为 $\frac{a}{b}$，输出 $a \times b^{-1} \bmod 998244353$。

inputFormat:
输入包含多组数据，第一行输入数据组数 $T$。

对于接下来的每组数据，第一行两个整数 $n, \mathit{root}$，分别表示树的大小，树根的编号。

接下来一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示树上每个节点的权值。

接下来 $n - 1$ 行，每行包含两个整数 $u, v$，表示 $u$ 和 $v$ 之间有一条树边。

outputFormat: 对于每组数据，输出一行，包含一个整数，代表对于所有合法点对 $(x, y)$，$\sum f(x, y)$ 对 $998244353$ 取模的结果。

samples:
见附件中的 dfs/dfs_ex2.in
见附件中的 dfs/dfs_ex2.ans


title: Two Operations

background:
**本题时限较小，请采用较快的读入方式，以下是出题人提供的快读模板：**

```cpp
typedef long long LL;
inline LL read(){
	register LL x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
```

当然你也可以采用自己的读入方法。

description:
在一次聚会上，一共有 $n$ 名学生，他们的编号分别为 $1,2,3,\cdots,n$，他们被分成 $k$ 组，组的编号分别为 $1,2,3,\ldots,k$。

小 V 老师负责组织这场聚会，在聚会的开始，第 $i$ 名学生被分到了第 $a_i$ 组，并拿到了 $b_i$ 颗糖果。（小 V 既不属于任何组别，也没有任何糖果。在接下来的活动中，小 V 作为组织者的身份。）

这一次聚会一共有 $m$ 轮活动，对于每一轮活动，可能发生以下两种情况之一：

1.  `Change X Y`，表示把所有组别为 $X$ 的学生的组别改为 $Y$（修改后 $X$ 即为空组），并把组 $X$ **删除**。
2.  `Query`，表示小 V 想要知道，如果把**剩下**的组合并（定义见下） 成一大组，那么这一大组内**拥有最多糖果的学生的糖果数最少可能是多少**。

定义一个组 $G_i$ 的大小就是这个组内含有学生的个数，记为 $S_i$。

**合并**：将大小为 $S_1(S_1>0)$ 的组 $G_1$ 合并到大小为 $S_2(S_2>0)$ 的组 $G_2$，其中 $G_1$ 组内所有学生拥有糖果数之和为 $f$，则：

1. 第一步，将原先 $G_1$ 中所有学生的糖果数都变为 $0$，并将他们的组别改为 $G_2$。
2. 第二步，将目前 $G_2$ 中每位学生（包括原先 $G_1$ 中的学生）的糖果数加上 $\dfrac{f}{S_1+S_2}$（糖果数不一定为整数块）。

**注意：**

1. $G_1$ 合并到 $G_2$ 的最后结果可能会与 $G_2$ 合并到 $G_1$ 的最后结果不同。
2. `Query` 中的合并不会真实发生。即在这一次情况过后，所有学生的糖果数与所在组与此次操作未发生前一致。

请将每次 `Query` 中的答案对 $10^9+7$ 取模。（可能是分数取模，如果不知道如何取模请见**提示说明**）

inputFormat:
第一行三个整数 $n,m,k$。

第二行 $n$ 个整数 $a_{1\ldots n}$。

第三行 $n$ 个整数 $b_{1\ldots n}$。

接下来 $m$ 行，每行对应一种情况。具体格式参见题目描述或输入输出样例。

outputFormat: 输出若干行整数表示答案。

samples:
3 3 2
1 1 2
3 4 5
Query
Change 2 1
Query


title: 『MdOI R5』Many Minimizations

background:
本题不是多项式题，建议先做 E。

[![2.gif](https://i.postimg.cc/3JN9j60M/2.gif)](https://postimg.cc/xcrKn6Pg)

description:
小 L 遇到了一个经典题：给定一个长度为 $n$ 的**整数**序列 $a$，你需要在所有**单调不降**的**实数**序列中选出一个作为 $b$，最小化 $\sum\limits_{i=1}^n |a_i-b_i|$。可以证明答案是整数。

他一眼就秒了这个题：这不是保序回归板子吗！

他觉得这题太水了，于是决定加强一下：

对于所有长度为 $n$ 的且满足 $\forall i\in[1,n],a_i\in[1,m]$ 的**整数**序列 $a$，求出上面这个问题的答案的总和对**质数** $p$ 取模后的结果。其中 $n,m,p$ 是给定的常数。

这下小 L 不会了。为了不让你看出来他根本就不会，他随便写了一个数据范围就把这题扔给你做了。

现在压力来到了你这边，你能否顺利切掉这个题呢？

inputFormat: 共一行，三个整数，依次表示 $n,m,p$。

outputFormat: 共一行，一个整数，表示答案。

hint:
对于 $100\%$ 的数据，$1\le n\le 5\times 10^3$，$1\le m\le 10^9$，$10^9<p\le 1.01\times 10^9$，保证 $p$ 是质数。

$\operatorname{Subtask} 1(10\%)$：$n,m\le 7$。

$\operatorname{Subtask} 2(10\%)$：$m\le 2$。

$\operatorname{Subtask} 3(10\%)$：$n,m\le 50$。

$\operatorname{Subtask} 4(10\%)$：$n\le 50$。

$\operatorname{Subtask} 5(10\%)$：$n,m\le 500$。

$\operatorname{Subtask} 6(10\%)$：$n\le 500$。

$\operatorname{Subtask} 7(10\%)$：$m\le 5\times 10^3$。

$\operatorname{Subtask} 8(30\%)$：无特殊限制。

#### 样例说明 1

有以下 $8$ 种可能的情况：

$a=(1,1,1),b=(1,1,1),ans=0$。

$a=(1,1,2),b=(1,1,2),ans=0$。

$a=(1,2,1),b=(1,1,1),ans=1$。

$a=(1,2,2),b=(1,2,2),ans=0$。

$a=(2,1,1),b=(1,1,1),ans=1$。

$a=(2,1,2),b=(1,1,2),ans=1$。

$a=(2,2,1),b=(2,2,2),ans=1$。

$a=(2,2,2),b=(2,2,2),ans=0$。

因此答案为 $0+0+1+0+1+1+1+0=4$。

注意，对于一个固定的 $a$，最优的 $b$ 不一定唯一。上面只给出了一种可能的解。

$\operatorname{Bonus}$：在 $p$ 为 NTT 模数的情况下做到 $O(n\log n)$。实际上在本题正解的基础上这一部分并不困难。


title: [COI2009] IZBORI

description:
有 $V$ 个选民在为选举投票。这次选举有 $N$ 个党派参加，他们要共同争夺议会的 $M$ 个席位。

假设党派编号为 $1$ 至 $N$，且他们分别获得 $v_1,v_2,\cdots,v_n$ 票。席位分配如下：

1. 所有获得少于 $5\%$ 的票数的党派直接取消后续参选资格。

2. 一开始议会不会为任何党派预留名额。

3. 对于每个党派，计算 $Q_p=V_p\div(S_p+1)$，其中 $V_p$ 是党派获得的总票数，$S_p$ 是已经分配给该党派的席位数量。

4. $Q_p$ 最大的党派会获得一个席位。（相同则编号小的获得）

5. 重复第三四步直到满员。

现在已经清点了部分选票，知道了党派现在获得的票数，编写程序以求出在所有可能的情况下，各个党派可能获得的最多或最少席位。

inputFormat:
第一行三个正整数 $V,N,M$。

第二行 $N$ 个正整数，为各个党派目前获得的票数，保证其总和不超过 $V$。

outputFormat:
输出第一行 $N$ 个整数，为各个党派最多可能得到席位数。

输出第二行 $N$ 个整数，为各个党派最少可能得到席位数。

hint:
正确输出第一行获得 $20\%$ 的分数。正确输出第二行获得 $80\%$ 的分数。

$1\le V\le 10^7,1\le N\le 100,1\le M\le 200$。


title: 立方根

description: 给定正整数 $n$，求 $\sqrt[3]{n}$。答案向下取整。

inputFormat: 仅一行，一个正整数 $n$。

outputFormat: 仅一行，一个正整数，表示 $\sqrt[3]n$。向下取整输出。


title: 机器猫斗恶龙

description:
机器猫出门斗恶龙了！他需要通过 $n$ 个关卡。

每个关卡要么是与怪物战斗，扣除一定的血量；要么是营地，给机器猫增加一定的血量。

在旅途中，机器猫**任意时刻**的血量不能低于或等于 $0$。问机器猫至少需要多少的初始血量，才能完成任务。

血量为正整数。

inputFormat:
第一行，一个正整数 $n$，表示关卡数量。

第二行，共 $n$ 个整数 $a_i$，表示每个关卡。
- 若 $a_i>0$，则表示这个关卡是营地，增加 $a_i$ 的血量
- 若 $a_i<0$，则表示这个关卡是战斗，机器猫血量代价为 $a_i$

outputFormat: 仅一行，一个正整数，表示机器猫需要的初始血量。

hint:
**样例解释**

第二组样例：机器猫带着 $501$ 点血量出门，两场战斗之后剩下 $1$，恢复到 $1001$，两场战斗之后为 $801$，完成任务。

**数据规模与约定**

对于 $100\%$ 的数据，$n\leq 100000, 1\leq |a_i|\leq 1000$。


title: 吃冰棍

description:
机器猫喜欢吃冰棍。

买一根冰棍，吃完了会剩一个木棒；每三个木棒可以兑换一个冰棍。兑换出来的冰棍，吃完之后也能剩下一个木棒。

所以，如果机器猫买了 5 根冰棍，他可以吃完之后得到 5 个木棒；拿 3 个木棒兑换 1 根冰棍，余 2 个木棒；吃完兑换来的冰棍之后，手上有 3 个木棒，又能兑换一个冰棍。最后，机器猫实际上吃了 7 个冰棍。

机器猫想要吃到 $n$ 个冰棍，想问最开始至少需要去买多少根冰棍？

inputFormat: 仅一行，一个正整数，表示 $n$。

outputFormat: 仅一行，一个正整数，表示需要买的冰棍数量。


title: [PFOI Round1] Two Subsegments

background:
>洛谷知名网红，€€£官方团队团主 [€€£](https://www.luogu.com.cn/user/559616) 同志，因联合省选寄，医院抢救无效，于 4 月 17 日 g 了。

> [€€£](https://www.luogu.com.cn/user/559616) 是知名洛谷人，2021年加入洛谷，同年成立 €€£ 官方团队。在他在位期间勤勤恳恳，认真整活，发奋出题，为整活革命化、现代化、正规化建设作出了贡献。

对于 [€€£](https://www.luogu.com.cn/user/559616) 的退役，[Uvocde](https://www.luogu.com.cn/user/111084) 深感悲痛。这时，他想起了 [€€£](https://www.luogu.com.cn/user/559616) 对构造的深爱，于是便出了这道题来缅怀 [€€£](https://www.luogu.com.cn/user/559616)。

description:
有 $T$ 组询问，每组询问给出一个长为 $n$ 的序列 $a$，保证 $a$ 是 $1\sim n$ 的排列。

你可以选择一个数 $x$，然后你每次可以将一段长为 $x+1$ 或一段长为 $x-1$ 的序列在原序列中前移或后移 $x$ 位，将经过的部分移到空出来的地方。

请在 $80\times n$ 次内将 $a$ 排成升序。

inputFormat:
第一行一个正整数 $T$。

接下来 $2 \times T$ 行，每两行代表一组询问。

对于每组询问，格式为：先一行一个正整数 $n$，接下来一行 $n$ 个正整数，代表 $a_1,\ldots,a_n$。

outputFormat:
输出共 $T$ 组。

一组询问如果无解，仅输出一个 $-1$。

如果有解，则输出共 $m+2$ 行：

前两行每行一个数，分别是 $x,m$，其中 $m$ 表示操作次数，$x$ 如题意。

接下来 $m$ 行，每行三个数，第一个数表示方向（向左是 $0$，向右是 $1$），接下来两个数 $l,r$ 代表平移区间的左、右端点。

你的方案需要保证：

- $2\leq x\leq n$，$0\leq m\leq 80n$；
- 对每一次操作，有：
  - $1\leq l\leq r\leq n$；
  - $r-l+1=x-1$ 或 $r-l+1=x+1$；
  - 右移时 $r\leq n-x$，左移时 $l\geq x+1$。

本题采用 $\text{SPJ}$，只要调换操作正确或正确判断无解即可给分。


title: 「REOI-1」奶油蛋糕

background:
----------
早餐时间过后，小不点们都前往操场接受基础训练课程，威廉便趁机占据厨房了。
他在军服上披围裙，头上绑三角巾，还将清早从市场采买回来的大量材料摆到桌上。
接着，威廉烤了大量的奶油蛋糕。

威廉把奶油蛋糕摆放到桌子上，珂朵莉闻到了蛋糕的香味，迫不及待地扑到了餐桌前享受着这份饕餮盛宴，然而蛋糕的制作，似乎还差了那么最后一步……
“等一等哦，我还没有挤上奶油呢。”威廉说着，拿起了裱花袋。

可饥肠辘辘的珂朵莉哪里等得起全部的奶油都给挤好？
正当威廉还在忙着挨个给蛋糕挤上白花花的奶油的时候，珂朵莉已经偷偷的拿起了一块蛋糕……

description:
在桌子上的蛋糕可以看作是一个无限大的[平面直角坐标系](https://baike.baidu.com/item/%E5%B9%B3%E9%9D%A2%E7%9B%B4%E8%A7%92%E5%9D%90%E6%A0%87%E7%B3%BB/1296463?fr=aladdin)，每一个蛋糕都位于坐标系的整点上。

每一分钟，威廉会给每个蛋糕都涂上若干层奶油，规则如下：如果蛋糕连续第 $i$ 次没有被珂朵莉吃到，那么就会在蛋糕上挤上 $i$ 层奶油。

每次在威廉挤完所有蛋糕的奶油后，珂朵莉会拿起一块蛋糕，把这个蛋糕上的奶油给吃掉一层。特别的，如果珂朵莉吃掉了蛋糕上的一层奶油，威廉马上会贴心的再次给这个蛋糕补上一层，且不计入连续没有被吃到的次数里（即下一次的 $i$ 依旧为 $1$ ）。

由于蛋糕太多，珂朵莉实在不知道从何下手，所以她决定按照移动的吃法进行试吃。
总共 $m$ 个分钟，珂朵莉的吃蛋糕序列可以用一个长度为 $m$ 的字符串表达。第 $t$ 个字符可能为 `N`，`S`，`W`，`E`分别表示珂朵莉在第 $t+1$ 分钟会吃掉第 $t$ 分钟吃掉蛋糕的上，下，左，右方位的蛋糕。
珂朵莉第 $1$ 个分钟会拿起位于点 $(x,y)$ 的蛋糕，因为蛋糕目前没有被挤上奶油，所以珂朵莉既不会进行试吃，威廉也不会立刻给她补上奶油。

珂朵莉想知道在 $m$ 分钟后，这些蛋糕在最后都还剩多少层奶油。

本题中的上和右分别表示 $y$ 轴正方向和 $x$ 轴正方向。

---
简要题面：

有一个 $n\times n$ 的地块，一个连续 $i$ 分钟没人经过的地面在第 $i$ 分钟会落上 $i$ 个单位的灰，有人经过时不会落灰但灰也不会清零，在人走后第一分钟又会落上一个单位的灰，以此类推。有一个人在这个 $n\times n$ 的范围内移动，他的移动轨迹可以描述为一个由 $\text{N,S,W,E}$ 组成的字符串，每个字母分别表示上、下、左、右。这个人一开始在点 $(x,y)$，每一分钟移动一步。

求最后每一个位置上落下的灰的量。

保证这个人没有超过移动的范围。

inputFormat:
第一行四个正整数 $n,m,x,y$，含义如题面所示，其中 $x,y$ 表示横纵坐标，不是数组下标。
第二行一个长度为 $m$ 的字符串，表示珂朵莉的移动序列。

outputFormat: 共$n$ 行，每行 $n$ 个数，第 $i$ 行的第 $j$ 个数表示坐标 $(j,n-i+1)$ 上的灰的数量

samples:
10 70 2 2
NWSNSNNNSNNSSNNSENNNNEESNWSESESSWENNSEWESWWWESEEESENNSENWNESNWSNNNEESS

hint:
**本题 y 轴朝上，x 轴朝右，样例输出中的左下角表示 $(1,1)$，第一分钟珂朵莉在初始点处，第二分钟移动到相应的位置，第 $m+1$ 分钟移动到最后一个点，但是总共只有 $m$ 分钟，因此最后一个点不受移动的影响**

---
**样例 1 解释：**

珂朵莉的移动路径为 $(1,1)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(1,3)$，共 $4$ 分钟。

对于第 $1$ 分钟，$(1,1)$ 奶油层数不变，其余点被挤上了 $1$ 层奶油。

对于第 $2$ 分钟，$(1,2)$ 奶油层数不变，$(1,1)$ 被挤上了 $1$ 层奶油，其余点挤上 $2$ 层奶油。

对于第 $3$ 分钟，$(2,2)$ 奶油层数不变，$(1,1)$ 挤上 $2$ 层奶油，$(1,2)$ 挤上 $1$ 层奶油，其余点挤上 $3$ 层奶油。

对于第 $4$ 分钟，$(2,3)$ 奶油层数不变，$(1,1)$ 挤上 $3$ 层奶油，$(1,2)$ 挤上 $2$ 层奶油，$(2,2)$ 挤上 $1$ 层奶油，其余点挤上 $4$ 层奶油。

**注意最后珂朵莉移动到了 $(1,3)$，但是时间只有 $4$ 分钟，所以实际上不会对 $(1,3)$ 造成影响。初始点不一定在 $(1,1)$。**

$1\le n\leq 50,1\leq m\le 1000$。


title: 「REOI-p1」按摩

background:
![](https://cdn.luogu.com.cn/upload/image_hosting/iojg3sgx.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/5m1v3g37.png)

出题人：LinkyChristian

验题人：Legitimity

文案：小糯米

description:
无论是勇者还是妖精，在执行任务时，都难免会患上一些特有的“职业病”。其中，在这份“常见勇者职业病名单”上排名第一的，叫作“急性魔力中毒”。虽然魔力中毒在表面上只是类似于发高烧的症状，但倘若没有每次根除，就会变成痼疾，身体马上就会超出负荷极限。魔力中毒的治疗方案，说起来倒是颇为实在：找到魔力淤积的部位，用力按压，利用类似中医按摩的原理，将其淤积点给揉开。具体的治疗原理如下：

人体的魔力脉络，可以视作一个 $n \times n$ 的网格。与中医腧穴中的经穴、经外穴分类类似，魔力的作用“穴位”，亦可以大致上分为阴性和阳性。为了更直观的叙述，我们不妨将阳性的魔力穴位在网格上用黑点表示。而魔力出现淤积，大概率的情形下便是因使用魔力导致肌肉紧绷，从而使得本是阴性的穴位变为阳性，或者阳性变为阴性的结果。所谓的按摩，其实就是将其恢复到其应有的状态，从而疏通魔力。判断按摩是否完成的标志，便是在这个网格中，是否存在一个以黑点作为顶点的所有边均平行于网格的多边形。

现在，经过了一场激烈的战斗，珂朵莉因使用魔力过度，又出现了急性魔力中毒的症状。在给珂朵莉检查身体的时候，威廉发现，在珂朵莉的魔力脉络上，有 $m$ 个魔力穴位呈阳性反应。现在他要进行 $k$ 次按摩，每次的按摩都会给出一个点，如果该点的穴位呈阳性则变为阴性，反之则成为阳性。

威廉想知道，在每一次按摩结束后，他的治疗是否已经完成。

------------

形式化题面：给出一个  $n \times n$ 的网格，其中有 $m$ 个点为黑点。

共有 $k$ 个操作，每次操作使一个点黑白反转。判断在每次操作结束后是否存在一个以黑点作为顶点的所有边均平行于网格的多边形。

inputFormat:
第一行两个数：$n,m$。
接下来 $m$ 行，每行两个数 $x,y$，表示点 $(x,y)$ 为黑点。
下一行输入一个数 $k$ ，接下来 $k$ 行，每行两个数 $x,y$ ，表示对点 $(x,y)$ 进行一次操作(即按摩）。

outputFormat: 输出 $k$ 行，每行一个 `Yes` 或 `No` 表示该次操作后治疗是否完成，即在每次操作结束后是否存在一个以黑点作为顶点的所有边均平行于网格的多边形。

hint:
对于样例1，初始状态为

![](https://cdn.luogu.com.cn/upload/image_hosting/ykf02pm6.png)

之后每次操作后状态依次为

![](https://cdn.luogu.com.cn/upload/image_hosting/lilddgfo.png)

![](https://cdn.luogu.com.cn/upload/image_hosting/ml2qqt5d.png)

![](https://cdn.luogu.com.cn/upload/image_hosting/lilddgfo.png)

![](https://cdn.luogu.com.cn/upload/image_hosting/altczbf0.png)

![](https://cdn.luogu.com.cn/upload/image_hosting/uqvq4u0j.png)

对于 $5\%$ 的数据，$n\le 10,m\le 5,k\le 100$。
对于 $10\%$ 的数据，$n,k\le 100$。
对于 $20\%$ 的数据，$n,k\le 1000$。
对于 $80\%$ 的数据，$n,k\le 5\times10^4$。
对于另外 $10\%$ 的数据，$k=1$。
对于 $100\%$ 的数据，$m\le n \le 10^5,k\le 10^5$。


title: 「REOI-p1」回忆

background:
![](https://cdn.luogu.com.cn/upload/image_hosting/3uztip2k.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/rsmn7uez.png)

出题人：LinkyChristian

文案：小糯米

description:
“话虽如此，我们并没有四处游走让妖精一个一个地诞生。
只是在作为素材的巨大魂体上施予咒迹，好让她们带着接近人族的体格与人格自然诞生罢了。”

黄金妖精，自出生开始即刻下早夭诅咒之“人”，若非魔物无法抵御，是本不应在这茫茫尘世之中诞生之兵器。

每当前世之回忆涌上妖精之时，便是开启一朵含苞待放之花凋零倒计时之日。妖精的记忆，是由一条射线组成，为了便于叙述，我们不妨将射线当作数轴进行处理。在她们的记忆之中，会有若干个区间，在这个区间之内的回忆，是极易受到前世回忆的侵蚀的。但是由于生物的回忆本身自是不可探视分明之物，我们只能得知它们的 $m1$ 个开始区间 $[sl_i,sr_i]$ 与 $m2$ 个结束区间$[el_j,er_j]$ 。在这个回忆之内，会逐渐的有各种前世回忆涌出，侵蚀前期的记忆，当这些易于侵蚀的记忆区间全部被侵蚀殆尽后，黄金妖精便会就此“消失”。这些前世的回忆，可以看作成 $n$ 个不重叠的子段，这些子段的起点和终点恰好在一个开始区间和一个结束区间之内。而根据回忆的性质，不同的前世回忆的起点和终点自然是在不同的开始区间和结束区间内的。

记忆犹如湍急的小河，河水汩汩，顺流而下，搅动着石块与泥沙，不断地在水面上下浮沉。在上游之时，或许巉岩乱石，自有其沉重，因而水流清澈，自在澄明；越到入海口，石块逐渐的被泥沙所代替，哪怕只是微风逐浪，也会搅动其一片浑浊，将记忆都给摆弄的纠缠不清。每一次的记忆侵蚀，就如同翻腾的浪花，也许搅动的是泥沙，又或许只是将那些巨石推动了一隅。从数值上来叙述的话，第 $i$ 个起始区间被匹配能带来 $a_i$ 的贡献，第 $i$ 个结束区间被匹配能带来 $b_i$ 的贡献。当这些贡献达到了最大值，所谓的“侵蚀殆尽”，便会发生。那么现在这些妖精想知道，这个最大值究竟是多少。

特别的，如果数据本身无解，请输出 $-1$。

------------

简明题意：

给出 $m1$ 个开始区间 $[sl_i,sr_i]$ ，以及 $m2$ 个结束区间$[el_j,er_j]$ 。在数轴上选取不重叠的 $n$ 个子段，使得每个子段的起点和终点分别在一个开始区间和一个结束区间内。不同的子段的起点和终点需要在不同的开始区间和结束区间内。第 $i$ 个起始区间被匹配能带来 $a_i$ 的贡献，第 $i$ 个结束区间被匹配能带来 $b_i$ 的贡献。总贡献为选出的子段长度之和加上区间被匹配带来的贡献。求能最大总贡献是多少。

注意，将一个子段 $[l,r]$ 的长度定义为 $r-l$ ，这里的两个子段“重叠”定义为存在一个长度 > 0 的区间被同时包含在两个子段之内。

无解输出 $-1$。

inputFormat:
第一行三个整数 $n,m1,m2$

第二行 $2\times m1$ 个整数表示 $sl_1,sr_1,sl_2,sr_2,\dots , sl_{m1},sr_{m1}$，

第三行 $2\times m2$ 个整数表示 $el_1,er_1,el_2,er_2,\dots , el_{m2},er_{m2}$

第四行 $m1$ 个数表示 $a_1,a_2,\dots ,a_{m1}$

第五行 $m2$ 个数表示 $b_1,b_2,\dots ,b_{m2}$

outputFormat: 输出一个整数，表示最大的总贡献。


title: [JRKSJ R5] 1-1 B

background: 本题是 1-1 的较难版本，较易版本为 [1-1 A](https://www.luogu.com.cn/problem/P8847)。

description:
给出一个序列 $a$，$\forall i\in [1,n],a_i\in \{1,-1\}$。

询问有多少个将 $a$ 重排后的序列使得该序列的最大子段和最小化。

称两个序列不同，当且仅当这两个序列有任意一个位置上的数不同。

inputFormat:
第一行一个整数 $n$。

第二行 $n$ 个整数表示 $a$。

outputFormat: 一个整数表示答案。答案对 $998244353$ 取模。


title: [COI2009] PLAHTE

description:
地面上有 $N$ 条矩形床单，所有床单平行于坐标轴且没有任何一条床单覆盖 $(0,0)$。

在 $0$ 时刻的时候油覆盖了 $(0,0)$ 这个格子，且每过一个时刻，油会向八个方向扩散。当油扩散到一个有床单的格子上，油会污染这个格子上的所有床单（只污染被污染的格子，其他未受污染的不算）。

给定你一些时刻，在这些时刻上请你求出所有床单上被污染的格子的总面积。

inputFormat:
第一行一个正整数 $N$，为床单的数量。

接下来 $N$ 行，每行四个正整数 $x_1,y_1,x_2,y_2$，用 $(x_1,y_1)$ 与 $(x_2,y_2)$ 这两个坐标形成第 $i$ 条床单。

接下来一行一个正整数 $M$，为时刻的数量。

接下来一行 $M$ 个正整数，为时刻。

outputFormat: 输出 $M$ 行，第 $i$ 行为第 $i$ 个时刻被污染的床单的面积（两条床单重合的话算两个）。


title: [Aya Round 1 B] 甲（one）

description:
定义长度为 $5$ 的序列 $S$ 为「好的」，当且仅当存在长度为 $5$ 的排列 $P$，满足 $S_{P_1}-1=S_{P_2}=S_{P_3}+1$ 且 $S_{P_4}=S_{P_5}$。现有一长度为 $5$ 的整数序列 $a$，满足 $0\le a_i \le 9(1\le i \le 5)$。其中 $a_1 \sim a_4$ 给定。试判断是否存在 $a_5$ 满足 $a$ 为「好的」。

其中，长度为 $5$ 的排列 $P$，指的是一个长度为 $5$ 的数列，其中 $1,2,3,4,5$ 在这个数列中出现且只出现一次。

inputFormat:
**本题含有多组数据。**

- 第一行输入一个整数 $T$ 代表数据组数。
- 接下来 $T$ 行每行输入四个整数 $a_1,a_2,a_3,a_4$。表示一组数据。

outputFormat: - 输出共 $T$ 行。对于每组数据，若存在满足条件的 $a_5$，输出 $1$；否则输出 $0$。

hint:
### 附加样例

- 样例 $2$ 见下发文件中的 $\textbf{\textit{one2.in/one2.ans}}$。该样例满足测试点 $2$ 的限制。
- 样例 $3$ 见下发文件中的 $\textbf{\textit{one3.in/one3.ans}}$。该样例满足测试点 $5$ 的限制。

### 样例解释

#### 样例 \#1

- 对于第 $1$ 组数据，可以令 $a_5=8$。此时存在 $P=\{4,1,2,5,3\}$，满足 $a_{P_1}-1=a_{P_2}=a_{P_3}+1$ 且 $a_{P_4}=a_{P_5}$。故输出 $1$。
- 对于第 $2$ 组数据，可以令 $a_5=4$。此时存在 $P=\{3,2,1,4,5\}$，满足 $a_{P_1}-1=a_{P_2}=a_{P_3}+1$ 且 $a_{P_4}=a_{P_5}$。故输出 $1$。
- 对于第 $3$ 组数据，不存在可以使 $a$ 为「好的」的 $a_5$。

$$
\begin{aligned}
\fcolorbox{black}{#fbb}{3\ \ 2\ \ 8\ \ 4} + \fcolorbox{black}{yellow}{8} &\Rightarrow \fcolorbox{black}{#fbb}{2\ \ 3\ \ 4} + \fcolorbox{black}{yellow}{8\ \ 8}\ {\color{green}\sqrt{}}\\
\fcolorbox{black}{#fbb}{1\ \ 2\ \ 3\ \ 4} + \fcolorbox{black}{yellow}{4} &\Rightarrow \fcolorbox{black}{#fbb}{1\ \ 2\ \ 3} + \fcolorbox{black}{yellow}{4\ \ 4}\ {\color{green}\sqrt{}}\\
\fcolorbox{black}{#fbb}{1\ \ 9\ \ 4\ \ 9} +   \begin{cases}
\fcolorbox{black}{yellow}{0}\\
\fcolorbox{black}{yellow}{1}\\
\cdots\\
\fcolorbox{black}{yellow}{9}
\end{cases}&\Rightarrow
{\color{red}\xcancel{\color{black}
\begin{cases}
\fcolorbox{black}{#fbb}{1\ \ 9\ \ 4\ \ 9\ \ 0}\\
\fcolorbox{black}{#fbb}{1\ \ 9\ \ 4\ \ 9\ \ 1}\\
\cdots\\
\fcolorbox{black}{#fbb}{1\ \ 9\ \ 4\ \ 9\ \ 9}
\end{cases}}}
\end{aligned}
$$

### 数据范围

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|} \hline
\textbf{\textsf{测试点}} & \bm{{T\le}} & \textbf{\textsf{特殊性质}} \cr\hline
1 & 100 & \textbf{A} \cr\hline
2 & 100 & \textbf{B} \cr\hline
3 & 100 & - \cr\hline
4 & 1000 & - \cr\hline
5 & 10^5 & - \cr\hline
\end{array}
$$

- 特殊性质 $\bf A$：$a_1=a_2=a_3=a_4$。
- 特殊性质 $\bf B$：$a_1,a_2,a_3,a_4$ 互不相等。

对于 $100\%$ 的数据，$1\le T\le 10^5$，$0\le a_i \le 9$。


title: [Aya Round 1 E] 乙（two）

description:
定义由若干个边长为 $1$ 的正方体方块搭成的立体图形的「侧面积」为：对于所有方块，若它的前、后、左或右面没有紧贴着另一个方块，则该面计入侧面积。

维护长宽均无限的矩形地面，地面被划分为若干个边长为 $1$ 的格子。$n$ 次操作，每次选择一个格子 $(x_i,y_i)$ 在该位置向上堆叠 $z_i$ 个边长为 $1$ 的正方体方块。每次操作后，输出整个立体图形的「侧面积」。

inputFormat:
- 第一行输入一个整数 $n$。
- 接下来 $n$ 行，每行输入三个整数 $x_i,y_i,z_i$。

outputFormat: - 输出共 $n$ 行，每行输出一个整数。表示每次操作后立体图形的「侧面积」。

hint:
### 样例 1 解释

如图所示，建立空间直角坐标系。注意这里的空间直角坐标系和数学上常用的略有区别，其 $x$-轴向南、$y$-轴向东、$z$-轴向上。限于技术原因，此处仅给出斜二测画法的立体图形，请读者自行脑补立体图形其他角度的模样。图中绿色部分即为立体图形的侧面。

第一次操作后，在 $(1,1)$ 位置放入了一个高度为 $2$ 的立体图形，侧面积为 $8$。

![](https://cdn.luogu.com.cn/upload/image_hosting/ncd21a4f.png)

第二次操作后，在 $(1,3)$ 位置放入了一个高度为 $3$ 的立体图形，侧面积为 $12$。由于两个立体图形没有接触，因此可以直接加上第一次放上的立体图形的侧面积，总侧面积为 $20$。

![](https://cdn.luogu.com.cn/upload/image_hosting/hl9f45rq.png)

第三次操作后，在 $(1,2)$ 位置放入了一个高度为 $4$ 的立体图形。由于某些面发生了接触，这些面对应的面积不计入侧面积的计算范围内。容易发现，总侧面积为 $26$。

![](https://cdn.luogu.com.cn/upload/image_hosting/j8x2mtc8.png)

---

再强调下，每次堆叠操作是在对应位置上再加上 $z_i$ 个方块。例如下图，是先执行了 $\verb!2 2 1!$，再执行了 $\verb!2 2 3!$ 的结果。

![](https://cdn.luogu.com.cn/upload/image_hosting/3lgipl4z.png)

### 附加样例

- 样例 $3$ 见下发文件中的 $\textbf{\textit{two3.in/two3.ans}}$。该样例满足测试点 $4$ 的限制。
- 样例 $4$ 见下发文件中的 $\textbf{\textit{two4.in/two4.ans}}$。该样例满足测试点 $7$ 的限制。
- 样例 $5$ 见下发文件中的 $\textbf{\textit{two5.in/two5.ans}}$。该样例满足测试点 $10$ 的限制。
- 样例 $6$ 见下发文件中的 $\textbf{\textit{two6.in/two6.ans}}$。该样例满足测试点 $13$ 的限制。
- 样例 $7$ 见下发文件中的 $\textbf{\textit{two7.in/two7.ans}}$。该样例满足测试点 $20$ 的限制。

### 数据范围

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c||c|c|c|c|c|} \hline
\textbf{\textsf{\#}} & \bm{{n \le }} & \bm{{x,y \le}} & \bm{{z \le}} & \textbf{\textsf{特殊性质}} &
\textbf{\textsf{\#}} & \bm{{n \le }} & \bm{{x,y \le}} & \bm{{z \le}} & \textbf{\textsf{特殊性质}} \cr\hline
1 & 1 & 1 & 10 & - &
14 & 10^3 & 10^3 & 10^3 & - \cr\hline
2 & 2 & 5 & 10 & - &
15 & 10^3 & 10^3 & 10^9 & - \cr\hline
3 & 10 & 5 & 10 & - &
16 & 10^3 & 10^9 & 10^9 & - \cr\hline
4 & 100 & 100 & 100 & - &
17 & 10^5 & 10^9 & 10^9 & \textbf{AB} \cr\hline
5 & 10^3 & 10^3 & 10^3 & \textbf{AB} &
18 & 10^5 & 10^9 & 10^9 & \textbf{A} \cr\hline
6 & 10^3 & 10^3 & 10^9 & \textbf{AB} &
19 & 10^5 & 10^9 & 10^9 & \textbf{B} \cr\hline
7 & 10^3 & 10^9 & 10^9 & \textbf{AB} &
20 & 10^5 & 10^9 & 10^9 & - \cr\hline
8 & 10^3 & 10^3 & 10^3 & \textbf{A} &
21 & 2\times 10^5 & 10^9 & 10^9 & - \cr\hline
9 & 10^3 & 10^3 & 10^9 & \textbf{A} &
22 & 2\times 10^5 & 10^9 & 10^{12} & - \cr\hline
10 & 10^3 & 10^9 & 10^9 & \textbf{A} &
23 & 2\times 10^5 & 10^9 & 10^{13} & \textbf{A} \cr\hline
11 & 10^3 & 10^3 & 10^3 & \textbf{B} &
24 & 2\times 10^5 & 10^9 & 10^{13} & - \cr\hline
12 & 10^3 & 10^3 & 10^9 & \textbf{B} &
25 & 3\times 10^5 & 10^9 & 10^{13} & - \cr\hline
13 & 10^3 & 10^9 & 10^9 & \textbf{B} &&&&&\cr\hline
\end{array}
$$

- 特殊限制 $\bf A$：$\forall 1 \le i\le j \le n$，有 $x_i=x_j$。
- 特殊限制 $\bf B$：$\forall 1 \le i\le j \le n$，有 $(x_i,y_i) \ne (x_j,y_j)$。

对于 $100\%$ 的数据，保证 $1 \le n \le 3 \times 10^5$，$1 \le x,y \le 10^9$，$1\le z \le 10^{13}$。


title: [COCI2021-2022#6] Med

description:
今天是公开赛的最后一轮。人们知道这两个比赛采用相同的计分系统。更准确地说，两场比赛都有 $6$ 轮，每轮的积分在 $0$ 分到 $500$ 分之间，每轮比赛的分数会被加起来作为最后排名的总分。六轮比赛结束后，选手将根据总分进行排名。如果两个竞争对手得分相同，则字典序上较小的排名再字典序较大的人之前。没有两个竞争者有相同的名字。
养蜂人非常不耐烦，他们想提前知道他们的最终排名是多少。

每个养蜂人都想知道他们在最终排名中可能的最佳和最差位置。作为 $\rm{COCB}$ 比赛程序员，他们让你告诉他们第六轮后他们可能占据的排名。

inputFormat:
第一行包含一个正整数 $n(1≤n≤500)$，即养蜂人的数量。

接下来 $n$ 行，每行包含一个养蜂人的名称 $s_i(1 ≤|s_i|≤10)$ 和 $5$ 个数字 $b_1\cdots b_5$，表示第 $i$ 个养蜂人在前 $5$ 轮比赛的得分。

outputFormat:
输出 $n$ 行。

在第 $i$ 行中，输出第 $i$ 行的最佳排名和最差排名可能位置。

hint:
样例 2：到目前为止，$\rm{ante}$ 是 $1375$ 分，$\rm{mate}$ 是 $875$ 分。如果 $\rm{mate}$ 在最后一轮赢了 $500$ 分，并且 $\rm{ante}$ 是 $0$ 分，结果排名是持平的，他们都有 $1375$ 分。然而，既然是按字典排序，$\rm{ante}$ 比 $\rm{mate}$ 小，所以仍将排名领先。

### 数据范围：

对于 $20\%$ 的数据：$1\le n\le2$

对于 $100\%$ 的数据：$1\le n\le500$，$1\le |s_i|\le10$（保证每个人的名字互不相同），$1\le b_i \le500$

##### 本题分值与 [COCI 2021-2022#6](https://hsin.hr/coci/contest6_tasks.pdf) 分值相同，满分 $50$ 分


title: [AHOI2022] 排列

description:
对于一个长度为 $n$ 的排列 $P = (p_1, p_2, \ldots, p_n)$ 和整数 $k \ge 0$，定义 $P$ 的 $k$ 次幂

$$P^{(k)} = \left( p^{(k)}_1, p^{(k)}_2, \ldots, p^{(k)}_n \right),$$

该排列的第 $i$ 项为

$$p^{(k)}_i = \begin{cases} i, & k = 0, \\ p^{(k - 1)}_{p_i}, & k > 0. \end{cases}$$

容易证明任意排列的任意次幂都是一个排列。

定义排列 $P$ 的**循环值** $v(P)$ 为最小的**正整数** $k$ 使得 $P^{(k + 1)} = P$。

给出一个长度为 $n$ 的排列 $A = (a_1, a_2, \ldots, a_n)$，对于整数 $1 \le i, j \le n$，定义 $f(i, j)$：若存在 $k \ge 0$ 使得 $a^{(k)}_i = j$，则 $f(i, j) = 0$，否则设排列 $A_{i j}$ 为将排列 $A$ 的第 $i$ 项 $a_i$ 和第 $j$ 项 $a_j$ 交换后得到的排列，则 $f(i, j) = v(A_{i j})$。

求 $\sum_{i = 1}^{n} \sum_{j = 1}^{n} f(i, j)$ 的值。答案可能很大，你只需要输出其对 $({10}^9 + 7)$ 取模的结果。

inputFormat:
**本题有多组测试数据**。输入数据的第一行为一个整数 $T$，表示测试数据组数。

对于每组测试数据，第一行一个正整数 $n$ 表示排列的长度，接下来一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，描述输入的排列。

outputFormat: 对于每组数据输出一行一个整数，表示题目所求的答案对 $({10}^9 + 7)$ 取模的结果。

hint:
**【样例解释 #1】**

对于第一组测试数据，$f(1, 2) = f(2, 1) = f(2, 3) = f(3, 2) = f(1, 3) = f(3, 1) = 2$，其余的 $f(i, j)$ 均为 $0$。

对于第二组测试数据，所有的 $f(i, j)$ 均为 $0$。

**【样例 #2】**

见附件中的 `perm/perm2.in` 与 `perm/perm2.ans`。

该组样例中，第一个测试数据满足 $n \le 35$，前四个测试数据满足 $n \le 200$，所有测试数据满足 $n \le 2500$。

**【样例 #3】**

见附件中的 `perm/perm3.in` 与 `perm/perm3.ans`。

该组样例中，第一个测试数据满足特殊性质 A，第二个测试数据满足特殊性质 B，第三个测试数据满足特殊性质 C，前四个测试数据满足 $n \le {10}^5$，第五个测试数据满足 $n \le 5 \times {10}^5$。

特殊性质的具体内容参见数据范围部分。

**【数据范围】**

对于 $100 \%$ 的测试数据，$1 \le T \le 5$，$1 \le n \le 5 \times {10}^5$，$1 \le a_i \le n$。

| 测试点编号 | $n \le$ | 特殊性质 |
|:-:|:-:|:-:|
| $1 \sim 2$ | ${10}^5$ | A |
| $3$ | $35$ | 无 |
| $4$ | $200$ | 无 |
| $5$ | $2500$ | 无 |
| $6$ | ${10}^5$ | B |
| $7$ | ${10}^5$ | C |
| $8$ | ${10}^5$ | 无 |
| $9 \sim 10$ | $5 \times {10}^5$ | 无 |

特殊性质 A：$a_i = (i \bmod n) + 1$。
特殊性质 B：对于任意 $1 \le i \le n$，存在 $1 \le k \le 20$，$a^{(k)}_i = i$。
特殊性质 C：存在大小不超过 $10$ 的集合 $S$，使得对于任意 $1 \le i \le n$，存在 $x \in S, k \ge 0$，$a^{(k)}_x = i$。

**【提示】**

输入数据规模较大，请使用较为快速的输入方式。


title: [AHOI2022] 钥匙

description:
有 $n$ 座城市，编号为 $1, 2, \ldots, n$。这些城市由 $n - 1$ 条无向道路相连，每条无向道路连接两座城市，保证任意两个城市连通。即这 $n$ 座城市构成一棵树。

每座城市都有一件宝物。宝物分为两种：钥匙和宝箱。在一座城市里，要么有一把钥匙，要么有一个宝箱。钥匙和宝箱有不同的颜色，颜色为 $i$ 的钥匙只能打开颜色为 $i$ 的宝箱，打开宝箱后可以获得一枚金币，同时这把钥匙会损坏。

**由于某种特殊的原因，同一种的钥匙最多只有 $\bm{5}$ 把（同一种颜色的宝箱数量不限）。**

现在小 R 规划了 $m$ 次旅行，第 $i$ 次旅行的起点为 $s_i$，终点为 $e_i$。小 R 从 $s_i$ 沿最短路径走到 $e_i$。当他走到一座有钥匙的城市时，他可以将钥匙放入背包。当他走到一座有宝箱的城市时，如果他有相应颜色的钥匙，那么他就会打开这个宝箱并获得一个金币；如果他没有相应颜色的钥匙，那么他什么都不做（宝箱不能带走）。问每次旅行能获得多少枚金币。

**注意：旅行相互独立，即一次旅行完之后所有的钥匙和宝箱都会恢复到初始状态。**

inputFormat:
第一行两个正整数 $n, m$，表示城市数量和旅行数量。

接下来 $n$ 行，每行两个正整数 $t_i, c_i$，$t_i=1$ 表示第 $i$ 个城市里有一把钥匙，$t_i=2$ 表示有一个宝箱。$c_i$ 表示第 $i$ 座城市里钥匙或宝箱的颜色。数据保证每种颜色的钥匙都不超过 $5$ 把。

接下来 $n - 1$ 行，每行两个正整数 $u_i, v_i$，表示有一条连接 $u_i$ 和 $v_i$ 的无向道路。

接下来 $m$ 行，每行两个正整数 $s_i, e_i$ 表示一次旅行的起点和终点。

outputFormat: 输出 $m$ 行，每行一个整数，表示第 $i$ 次旅行能获得的金币数量。

samples:
见附件中的 keys/keys2.in
见附件中的 keys/keys2.ans

samples:
见附件中的 keys/keys3.in
见附件中的 keys/keys3.ans


title: [AHOI2022] 山河重整

description:
生活在 $998244353$ 号小宇宙的艾和兰收到了归零者的讯息，决定响应回归运动。他们需要把大部分的物质归还给大宇宙，只留下极少的物质用于在新宇宙重建自己的文明。

艾和兰的文明总共有 $n$ 个关键信息，编号为 $1, 2, \ldots, n$。他们需要保留的信息是这些关键信息的一个子集 $S$。对于一个编号为 $x$ 的信息，只要 $S$ 中一个子集的编号和等于 $x$，那么他们设计的漂流瓶就可以在新宇宙将 $x$ 还原出来。

艾和兰不禁想要思考，他们有多少种选择子集 $S$ 的方案，使得关键信息 $1, 2, \ldots, n$ 均能被还原？艾和兰自然是只用 $1$ 微秒就算出了方案数的精确数值，现在他们想让你帮忙验算。由于方案数可能很大，你只需要输出方案数对 $M$ 取模的结果。

inputFormat: 一行输入两个正整数 $N, M$。

outputFormat: 输出一行一个整数，表示答案对 $M$ 取模的结果。


title: [COCI2021-2022#6] Zemljište

description:
有一块地，大小为 $r \times s$，$\rm Matej$ 想买下它。这块地每个 $1\times1$ 的正方形都有不同的价格。

设一片非空子矩阵价格总和为 $m$，则这片子矩阵的权值为 $|m-a|+|m-b|$，您需要找到最小权值的子矩阵。

您只需要输出最小权值即可。

inputFormat:
第一行包含四个正整数 $r$, $s$ , $a$ 和 $b$ 。

下面 $r$ 行，第 $i$ 行，有 $s$ 个正整数，第 $j$ 个数表示 $c_{i,j}$，表示价格。

outputFormat: 一行一个整数 $v$，表示最小非空子矩阵的权值。

hint:
### 样例解释 2
![](https://cdn.luogu.com.cn/upload/image_hosting/2mzt4qih.png)

如图，总价格是$1 + 1 = 2$，这块地的权值是 $|3−2| + |4−2| =3$。

### 数据范围：

对于 $14\%$ 的数据：$1\le r,s\le20$

对于 $28\%$ 的数据：$1\le r,s\le100$

对于 $100\%$ 的数据：$1\le r,s\le500$，$1\le a,b,c_{i,j}\le10^9$

##### 本题分值与 [COCI 2021-2022#6](https://hsin.hr/coci/contest6_tasks.pdf) 分值相同，满分 $70$ 分


title: [AHOI2022] 回忆

background:
生活在题面里的他们，是一群怪异的少年。

对城市中修建道路需满足的基本物理限制熟视无睹，沉迷于十万个城市、百万条道路上的各种结构。

明明知道真正需要的数字庞大到无法计算，却偏要关心它模一个奇怪素数之后得到的结果。

如此智力超群的他们，却总是在自己提出的诡异的问题下败下阵来，把它们一股脑地丢给你们来做。

如今，他们长大了。他们学习到更普适的理论，习惯了更抽象的符号，不必再思考如此古怪的问题。但他们不曾料到，你们却以这些 “无用” 的问题为驱动，于计算机学科体系的一隅，开垦出了一片独属于 OI 的新天地。

有一天，他们各自回忆起了少年时期提出的问题。

description:
少年时，他们提出了 $n$ 个问题，从 $1$ 到 $n$ 编号。一个问题总由一个更基础的问题衍生而来，因此问题之间构成了一个树形的结构：$1$ 号问题是最基本的问题，也就是树的根节点，而其他问题都由其父亲节点对应的问题衍生而来。如果两个问题在树上相邻，则称这两个问题**彼此相关**。

少年时期的他们一共做了 $m$ 次研究，第 $i$ 次的研究从提出较为基本的问题 $s_i$ 开始，将它不断地修改、推广，最终提出问题 $t_i$。这些研究满足 $s_i \ne t_i$ 且 **$\bm{s_i}$ 必定是 $\bm{t_i}$ 的祖先**。即使研究的问题完全相同，从不同的角度研究会有不同的结果，因此**可能存在 $\bm{i \ne j, (s_i, t_i) = (s_j, t_j)}$ 的情形**。

现在，他们正一轮轮地回忆着少年时提出的问题。在他们每一轮对问题的回忆中，他们首先回忆到 $n$ 个问题中的任意一个。接下来，如果存在与当前回忆到的问题**彼此相关且在这轮回忆中没有被回忆到**的问题，那么他们可以将思绪从当前问题上切换到这些问题中的**任意一个**，并回忆到这个新的问题。他们可以不断地切换思绪，也可以在回忆到任何一个问题之后结束回忆。**每一轮回忆是独立的，也就是说一个问题可以被多轮回忆回忆起。**

如果在某一轮回忆中，他们**同时**回忆到了问题 $s_i$ 和问题 $t_i$，则称第 $i$ 次研究**被想起**。

为了更好地理解上述概念，考察以下例子：$n = 5$，问题 $1$ 与问题 $2, 3$ 相关，问题 $3$ 与问题 $4, 5$ 相关。一轮可能的回忆是：从问题 $2$ 开始回忆，切换思绪到问题 $1$，再切换到问题 $3$，最终切换到问题 $5$ 并结束回忆。如果 $m = 4$，$(s_1, t_1) = (1, 2), (s_2, t_2) = (1, 4), (s_3, t_3) = (s_4, t_4) = (3, 5)$，那么这轮回忆会让第 $1$ 次、第 $3$ 次和第 $4$ 次研究被想起，而第 $2$ 次研究不会被想起。

他们问你们的最后一个问题是：**如果每轮回忆的起点以及思绪的切换可以任意选择，最少需要多少轮回忆才能使所有的研究都被想起。**

inputFormat:
**本题有多组测试数据**。输入的第一行包含一个正整数 $T$，表示数据组数。

对于每组测试数据，第一行包含两个正整数 $n, m$，分别表示问题的个数和研究的个数。

接下来 $n - 1$ 行每行包含两个正整数 $u_i, v_i$，表示问题 $u_i$ 与问题 $v_i$ 相关。

接下来 $m$ 行每行包含两个正整数 $s_i, t_i$，描述一次研究。

outputFormat: 对于每组测试数据输出一行一个正整数，表示他们**最少**需要回忆的轮数使得 $m$ 次研究均被想起。

hint:
**【样例解释 \#1】**

样例中的第一组数据与题目描述所给的例子相同。一种可能的回忆方案为：

- 第一轮回忆中，从问题 $2$ 开始，依次切换思绪到问题 $1, 3, 5$。此时第 $1, 3, 4$ 次研究被想起，但第 $2, 5$ 次没有。
- 第二轮回忆中，从问题 $4$ 开始，依次切换思绪到问题 $3, 1$。此时第 $2, 5$ 次研究被想起。

第二组数据符合特性 A 的要求。一种可能的回忆方案为：第一次回忆依次回忆到 $2, 1, 3, 5, 6$，第二次回忆依次回忆到 $8, 7, 9, 10$。

**【样例 \#2】**

见附件中的 `memory/memory2.in` 与 `memory/memory2.ans`。

这组数据满足了测试点 $1 \sim 4$ 的条件。

**【样例 \#3】**

见附件中的 `memory/memory3.in` 与 `memory/memory3.ans`。

这组样例满足了特性 A 的条件。且除了后 $3$ 组数据外，其余样例均满足 $n, m \le 1000$。除了后 $30$ 组数据外，其余样例均满足 $n, m \le 30$。你也可以用这组样例完成对较小规模数据的测试。

**【样例 \#4】**

见附件中的 `memory/memory4.in` 与 `memory/memory4.ans`。

这组样例满足了测试点 $24 \sim 25$ 的条件。同样例 \#3，本样例满足：除了后 $3$ 组数据外，其余样例均满足 $n, m \le 1000$。除了后 $30$ 组数据外，其余样例均满足 $n, m \le 30$。你也可以用这组样例完成对较小规模数据的测试。

**【样例 \#5】**

见附件中的 `memory/memory5.in` 与 `memory/memory5.ans`。

这组样例满足了特性 B 的条件。

**【样例 \#6】**

见附件中的 `memory/memory6.in` 与 `memory/memory6.ans`。

这组样例满足了特性 C 的条件。

**【评分方式】**

对于每一组测试点，如果你的输出格式正确，且每一组数据输出的答案正确，那么你会获得 $4$ 分。

否则，如果你的输出格式正确，且对于每一组数据，你输出的答案**与正确答案相等或者比正确答案大 $\bm{1}$**，那么你将在此测试点上获得 $3$ 分。

**【数据范围】**

本题共 $25$ 个测试点。对于所有的测试点，$1 \le n, m \le 2 \times {10}^5$，$1 \le \sum n, \sum m \le
5 \times {10}^5$，$1 \le u_i, v_i, s_i, t_i \le n$，$s_i \ne t_i$。保证输入的 $(u_i, v_i)$ 构成一棵树，$s_i$ 在以 $1$ 为根的树上是 $t_i$ 的祖先。

| 测试点 | 规模限制 | 特殊性质 |
|:-:|:-:|:-:|
| $1 \sim 4$ | $T \le 3000$，$n \le 50$，$m \le 15$ 且最多有 $5$ 组数据满足 $m \ge 10$ | 无 |
| $5 \sim 6$ | $n, m \le 100$，$\sum n^3, \sum m^3 \le 3 \times {10}^7$ | A |
| $7$ | $n, m \le 100$，$\sum n^3, \sum m^3 \le 3 \times {10}^7$ | B |
| $8$ | $n, m \le 100$，$\sum n^3, \sum m^3 \le 3 \times {10}^7$ | C |
| $9$ | $n, m \le 100$，$\sum n^3, \sum m^3 \le 3 \times {10}^7$ | 无 |
| $10 \sim 11$ | $n, m \le 1000$，$\sum n^2, \sum m^2 \le 3 \times {10}^7$ | A |
| $12$ | $n, m \le 1000$，$\sum n^2, \sum m^2 \le 3 \times {10}^7$ | B |
| $13$ | $n, m \le 1000$，$\sum n^2, \sum m^2 \le 3 \times {10}^7$ | C |
| $14 \sim 16$ | $n, m \le 1000$，$\sum n^2, \sum m^2 \le 3 \times {10}^7$ | 无 |
| $17 \sim 18$ | $n, m \le 2 \times {10}^5$，$\sum n, \sum m \le 5 \times {10}^5$ | B |
| $19 \sim 20$ | $n, m \le 2 \times {10}^5$，$\sum n, \sum m \le 5 \times {10}^5$ | C |
| $21 \sim 23$ | $n, m \le 2 \times {10}^5$，$\sum n, \sum m \le 5 \times {10}^5$ | A |
| $24 \sim 25$ | $n, m \le 2 \times {10}^5$，$\sum n, \sum m \le 5 \times {10}^5$ | 无 |

特殊性质 A：保证 $n$ 为偶数，且树的结构为：对于任意正整数 $1 \le i \le \lfloor \frac{n}{2} \rfloor$，$2 i$ 的父亲为 $2 i - 1$；若 $i \ge 2$，则 $2 i - 1$ 的父亲为 $2 i - 3$。
特殊性质 B：保证对于所有的正整数 $1 \le i \le m$，$s_i$ 为 $t_i$ 的父亲。
特殊性质 C：保证对于所有的正整数 $1 \le i \le m$，$s_i = 1$。

请注意，**测试点的难度与编号并没有直接关系**。

**【提示】**

请注意，为了取得部分分，你必须保证输出格式正确，即：输出恰好有 $m$ 行，且每行是一个正整数。

此外，如果某组测试数据中你输出的结果比答案小 $1$ 而不是大 $1$，那么你**不能**在该测试点获得 $3$ 分。

本题部分测试点读入量较大。为了优化程序的总运行时间，我们建议你采用较为快速的读入方式。


title: [COCI2021-2022#6]  Naboj

description:
Šikić 先生是一位化学老师，他正在用 $n$ 个金属球和 $m$ 根铜导线做实验。他将一些对金属球用导线相连，使这些球（直接或间接地）与其他球都相连。他想要教学生关于电荷的知识，因此他将通过按顺序给金属球充电来演示它。

Šikić 先生可以让每个球带上正负电荷的一种。当一个金属球带负电荷时，与这个金属球相连的所有导线中的电子都将被排斥到与该导线相连的另一个金属球上。反过来，当一个金属球带正电荷时，与这个金属球相连的所有导线中的电子都将受这个金属球的吸引。无论导线的先前状态如何，给球充电对导线的影响都相同。

在刚上课的时候，所有的金属球都不带电，导线中的电子不动。对于每根导线，Šikić 先生都想让它其中电子的流向是某一个确定的方向。请帮他确定一个给金属球充电的顺序，使得最后电子的流向是他想要的。

inputFormat:
第一行两个数 $n$ 和 $m$，意义如题目描述。

接下来 $m$ 行每行两个整数 $a_i$ 和 $b_i$，表示金属球 $a_i$ 和 $b_i$ 之间有一根导线相连，并且这根导线中的电子应更靠近 $a_i$ 而不是 $b_i$。在一对金属球之间最多只有一条导线。所有的金属球都通过导线直接或间接相连。

outputFormat:
如果不可能让最后电子的流向是 Šikić 先生想要的，输出 $-1$。否则输出 $k$，表示需要充电的金属球数量。$k$ 必须小于等于 $200000$。

接下来 $k$ 行，每行输出两个整数 $c_i$ 和 $d_i(1 \leq c_i \leq n,0 \leq d_i \leq 1)$，分别表示第 $i$ 步 Šikić 先生需要充电的金属球的编号和是给这个金属球充正电荷（用 $d_i=1$ 表示）还是负电荷（用 $d_i=0$ 表示）。如果有多种方案，输出其中一种即可。

hint:
### 样例解释 1：

首先，我们给金属球 $2$ 充正电荷。金属球 $1,2$ 和金属球 $2,3$ 之间的导线中的电子现在更靠近 $2$。金属球 $1,3$ 之间的导线仍保持中性。

现在我们给金属球 $3$ 充负电荷。金属球 $2,3$ 之间的导线状态不变，金属球 $1,3$ 之间的导线中的电子更靠近金属球 $1$。

最后我们给金属球 $1$ 冲正电荷。金属球 $1,3$ 之间的导线状态不变，但金属球 $1,2$ 之间的导线现在将更靠近金属球 $1$，目标流向达成。

### 数据范围：

对于全部数据，$1 \le n\le 200000$，$1\le m\le 500000$，$1 \le a_i,b_ i\le n,a_i\neq b_i$

本题分值与 [COCI 2021-2022#6](https://hsin.hr/coci/contest6_tasks.pdf) 分值相同，满分 $110$ 分


title: [COCI2021-2022#6]  Palindromi

description:
给你一个长度为 $n$ 的 $\texttt{01}$ 序列，下标为 $1,2,\dots,n$。最初每个字符都代表了一个长度为 $1$ 的字符串。在一次连接中，需要选择两个字符串 $a$ 和 $b$，将它们删除后，换为字符串 $ab$，即在写下 $a$ 中的所有字符后写下字符串 $b$ 的所有字符。

这 $n$ 个初始字符串需要用 $n-1$ 次连接操作连成一个字符串。第 $i$ 次选择的字符串用一个下标对 $(a_i,b_i)$ 描述，表示要连接的字符串是包含下标为 $a_i$ 的字符的和包含下标为 $b_i$ 的字符的。保证下标为 $a_i$ 和 $b_i$ 的字符不在同一字符串中。

一些字符串 $w$ 的回文值被定义为 $w$ 中不同回文子串的个数。我们定义回文串为从左到右读和从右到左读相同的字符串。一个字符串的子串被定义为可以从字符串开头和（或）结尾开始删去一个或多个字符得到的字符串。

对于每次连接操作，输出每次连成的字符串的回文值。

inputFormat:
第一行包含一个整数 $n$，表示字符个数。

第二行一个长度为 $n$ 的 $01$ 字符串，表示初始字符串。

接下来 $n-1$ 行，每行两个整数 $a_i$，$b_i$，表示第 $i$ 次连接操作。

outputFormat: 输出 $n-1$ 行，表示每次连接操作得到的字符串的回文值。


title: [COCI2021-2022#6]  Superpozicija

description:
世界闻名的物理学家 Juraj 最近发现了一种新的基本粒子——括号子（parenthesision）。括号子可以有开（（）或关（））两种状态。使用 Juraj 自制的粒子加速器，他创造了 $t$ 个由 $n$ 个括号子组成的叠加态序列。这 $t$ 个序列中的 $n$ 个括号子都是两个不同的位置和（不必不同的）状态的叠加态。如果序列被观测的话，括号子的波函数就将坍缩，每个括号子的位置和状态就是确定的了。Juraj 想知道这些括号子是否可以坍缩为一个合法的括号序列。

Juraj M. 博士知道这些革命性的且完全有科学依据的粒子的量子物理学已经超出了 COCI 的参赛者的知识范围，所以他提供了一个正式的题面：

给你 $t$ 个长度为 $2n$ 且由左右括号构成的括号序列。每个括号都恰好是一对括号中的一个。一对中的括号可以是不同的，也可以都是左括号或右括号。Juraj 想知道是否可以在每对括号中选一个，使得最后组成的括号序列是一个合法的括号序列。此外，如果是可能的，他需要你输出如何才能获得一个合法的括号序列。一个括号序列是合法的，如果它是一个空串，或者可以写成 $(A)$ 或者 $AB$，其中 $A$ 和 $B$ 是任意的合法括号序列。

inputFormat:
第一行包含一个整数 $t$，表示括号序列数。接下来描述这 $t$ 个序列。

第一行包含一个整数 $n$，表示这个序列里的括号对数。

第二行包含一个长度为 $2n$ 的字符串 $z$，$z$ 只由字符 `(` 和 `)` 组成。

接下来 $n$ 行，每行包含两个整数 $a_i,b_i$，数字 $1,2,\dots,2n$ 在其中都只出现恰好一次。

outputFormat: 输出 $t$ 行，第 $i$ 行输出一个 $01$ 序列，表示可能的括号选择方案。如果第 $i$ 个序列中，第 $j$ 对括号下标为 $a_j$ 的一个被选中，输出 $0$，如果是 $b_j$ 被选中，输出 $1$。如果没有合法的选择方案，输出 $-1$。

hint:
### 样例解释 1：

从原序列 `()))((()` 中，只有加粗的部分会留下 **(**))**)(**((**)**，即 **()()**，它是一个合法的括号序列。

### 数据范围：

对于 $9\%$ 的数据：$1\le n \le 10$。

对于 $9\%$ 的数据：$z[a_i]=z[b_i]$。

对于 $18\%$ 的数据：$b_i=a_i+1$。

对于 $100\%$ 的数据：$1\le t \le 10^5,\sum n\le10^5,1\le n \le 10^5 ,1\le a_i \le b_i \le 2\times n$。

本题分值与 [COCI 2021-2022#6](https://hsin.hr/coci/contest6_tasks.pdf) 分值相同，满分 $110$ 分。


title: 「SiR-1」Bracket

background: > Everything that kills me makes me feel alive.

description:
Mirika 有一个长度为 $n$ 的括号序列 $s$。

对于一个括号序列 $S$，Mirika 可以执行两种操作：

- 变换：选择一个位置 $i$ 满足 $1 \leq i \leq \lvert S \rvert$，使得 $S$ 变为 $S_iS_{i+1}\cdots S_{\lvert S\rvert}S_1S_2\cdots S_{i-2}S_{i-1}$。
- 插入：在这个序列的 **任意位置** 插入一个括号（左右括号均可）。

Mirika 定义括号序列 $S$ 的权值 $f(S)$ 为能将这个括号序列变成一个合法括号序列所需的最小操作数。

其中，合法括号序列的定义为：

+ 空串为 合法括号序列。
+ 若 $\texttt A$ 为 合法括号序列，则 $\texttt{(A)}$ 为 合法括号序列。
+ 若 $\texttt A, \texttt B$ 均为 合法括号序列，则 $\texttt{AB}$ 也为 合法括号序列。

现在 Mirika 想要求出：

$\sum_{l=1}^n \sum_{r=l}^n f(s[l,r])$

其中 $s[l,r]$ 表示由 $s_l,s_{l+1},\cdots,s_r$ 形成的连续子序列。

但是 Mirika 太菜了不会算，于是只好求助于你。

inputFormat:
**本题每个测试点内有多组数据。**

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

对于每组数据，第一行一个正整数 $n$。

第二行一个长度为 $n$ 的括号序列 $s$。

outputFormat: 输出共 $T$ 行，第 $i$ 行一个整数表示第 $i$ 组测试数据的答案。

hint:
### 样例解释

对于 $s = \texttt{())(}$：

+ 考虑 $s[1,4]=\texttt{())(}$。执行变换操作 $i=4$，有 $\texttt{())(} \Rightarrow \texttt{(())}$，其中 $\texttt{(())}$ 是合法括号序列，故 $f(s[1, 4]) = 1$。可以证明不存在更优的策略。
+ 考虑 $s[2,4]=\texttt{))(}$。执行变换操作 $i=2$，再在序列开头插入一个左括号，有 $\texttt{))(} \Rightarrow \texttt{)()} \Rightarrow \texttt{()()}$，其中 $\texttt{()()}$ 是合法括号序列，故 $f(s[2, 4]) = 2$。可以证明不存在更优的策略。

### 数据规模与约定

**本题采用捆绑测试。**

+ Subtask 0（15 pts）：$n \leq 400$，$\sum n \leq 800$。
+ Subtask 1（20 pts）：$n \leq 2\times 10^3$，$\sum n \leq 4\times 10^3$。
+ Subtask 2（5 pts）：$s$ 内不含有右括号。
+ Subtask 3（10 pts）：对于所有整数 $1\le i < n$，有 $s_i \neq s_{i+1}$。
+ Subtask 4（30 pts）：$n \leq 2\times 10^5$，$\sum n \leq 5\times 10^5$。
+ Subtask 5（20 pts）：无特殊限制。

对于所有数据，$1 \leq T \leq 10000$，$1 \leq n \leq 2 \times 10^6$，$1 \leq \sum n \leq 2 \times 10^7$。


title: Two Hypercubes

background: 注：数据已经加强。

description:
$T$ 次询问，每次给定 $A,B,C$，求：

$$\Big(\sum_{x=1}^A\sum_{y=1}^B\sum_{z=1}^C[y^x=x^z]\Big)\bmod (10^9+7).$$

inputFormat:
第一行一个正整数 $T$。

接下来 $T$ 行，每行三个正整数 $A,B,C$。

outputFormat: $T$ 个整数 $\text{ans}$ 表示答案。以换行符隔开。


title: [PFOI Round1] Two Sequences

background: syzf2222 喜欢并查集！特别是路径压缩的并查集。

description:
```cpp
inline int find(int x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
	fx=find(x),fy=find(y);
	if(fx==fy)return;fa[fx]=fy;
}
```

这是他惯用的并查集代码，初始时对于每个 $x$ 有 `fa[x]=x`。

接下来的 $T$ 天中，每天小 h 都给了他一个 $n$，表示并查集的大小（每天的 $n$ 可能是不同的）。

调皮的小 x 见他不在机房，每天都在并查集上不断 `merge`。
注意到小 x 不喜欢 `==`，他觉得这特别像他的眼睛，于是他不会使 `merge` 函数在第二行的条件语句中被 `return`，否则他会十分气愤。

现在的已知信息就只有最终的 $fa$ 数组了。
而 syzf2222 希望还原小 x 的操作序列（即若干次按顺序进行的 `merge` 操作）。由于他名字里有很多个 2 而且本人也非常 2 ，他希望知道对于每一天，有多少个 $fa$ 数组**恰好**能被还原成**两种**操作序列，答案对 $998244353$ 取余数。

两个操作序列不同，当且仅当某次 `merge` 时的变量 `fx,fy` 至少有一个不同。

inputFormat:
第一行一个整数 $T$。

后面 $T$ 行，每行读入一个整数 $n$ 表示小 h 给的数。

outputFormat: $T$ 行，每行一个整数表示答案对 $998244353$ 取余数的结果。

hint:
【样例解释】

对于第一天，$n=3$，共有 $fa=[1,1,1],[2,2,2],[3,3,3]$ 这三种 $fa$ 数组使得恰有两种操作序列。

以 $fa=[1,1,1]$ 为例，两种操作序列分别为 `merge(2,1),merge(3,1)` 和 `merge(3,1),merge(2,1)`，其他 `merge` 参数不同的方案与上述两种的其中一种是本质相同的（每次的 `fx,fy` 都一样）。

---

【数据范围】

**「本题采用捆绑测试」**

- $\texttt{Subtask 1(10 pts)：}T=1,\ n\le 10$；
- $\texttt{Subtask 2(30 pts)：}T=10^2,\ n\le 10^3$；
- $\texttt{Subtask 3(60 pts)：}$无特殊限制。

对于 $100\%$ 的数据，满足 $1\le T\le 10^5,\ 1\le n\le 10^9$。


title: 「KDOI-02」一个网的路

background:
「{*^$&#$~!@ovo}（他们也有路网？有趣。）」
「{&%#@~akoio!@}（该干的活先干完吧，玩物丧志的东西待会再说。）」
「{!%_&#%@yw?}（您语文是不是没学好？）」
蔚蓝的天空下，人们还不知道危险的来临。

description:
敌对文明被惹怒了。他们想用一种有趣的方式摧毁地球的路网。地球的路网可以近似为一个含有 $n$ 个节点 $m$ 条无向边的**森林**。他们想用以下 $2$ 种操作：
- 炸毁一个城市 $u$ 向外连接的所有道路。
- 在城市 $u,v$ 间新建一条道路。

来将地球上的路网改成效率最低的形式：一条链。可惜的是，他们的智商都不怎么高。于是，他们抓住了你，要求你给出一种方案，使得他们操作的次数最少。可怜的你在万般无奈之下，决定写一个程序，帮助他们算出结果。

inputFormat:
从标准输入中读入数据。

输入的第一行包含 $2$ 个正整数 $n,m$。

接下来 $m$ 行，每行 $2$ 个正整数 $u,v$ ，表示在城市 $u,v$ 间有一条无向道路。

outputFormat:
输出到标准输出。

输出共一行一个整数，表示外星人的最少操作次数。

samples:
见附件中的 traffic2.in
见附件中的 traffic2.ans

samples:
见附件中的 traffic3.in
见附件中的 traffic3.ans

hint:
**【样例解释】**

+ **样例 1 解释：**
初始图：
![](https://cdn.luogu.com.cn/upload/image_hosting/2z6ava49.png)
对城市 $2,3$ 进行操作二。
![](https://cdn.luogu.com.cn/upload/image_hosting/lqhomfm5.png)
此时已经成为了一条链。

***

**【数据范围】**

对于 $100\%$ 的数据，$0\le m<n\le2\times10^6$ 且保证输入合法。

|测试点编号|$n\le$|特殊性质|
|:-:|:-:|:-:|
|$1\sim2$|$10$|A|
|$3\sim6$|$500$|无|
|$7\sim8$|$10^4$|A|
|$9$|$10^4$|B|
|$10\sim12$|$10^4$|无|
|$13\sim15$|$10^6$|无|
|$16\sim20$|$2\times10^6$|无|

+ 特殊性质 A：保证每个连通块都为二叉树。
+ 特殊性质 B：保证每个顶点的度数不超过 $2$。

**【提示】**

本题 I/O 量较大，推荐使用较快的 I/O 方式。


title: [SDOI/SXOI2022] 小 N 的独立集

description:
小 N 喜欢出最大权独立集问题。

有一天，他接到了一系列的出题任务，于是他顺手出了一系列最大权独立集问题。

为了同时给这一系列题目造数据，小 N 生成了一个 $n$ 个点的树，并选定了一个正整数 $k$。这样每生成一组数据时，他只需要对于每个点，随机生成一个在 $1 \sim k$ 之间的整数点权，就可以生成一个新的最大独立集问题。

小 N 把这些题给了他的好朋友，小 Ω。小 Ω 表示，这些题太多太乱了，他打算把所有的 $k^n$ 道题归类处理。一个自然的想法就是按答案（也就是最大权独立集中的点的权值之和）分类，显然这些最大权独立集问题的答案一定在 $1 \sim nk$ 之间，所以小 Ω 只需要将所有题目按照答案分成 $nk$ 类进行管理就行了。

在小 N 正式开始出题之前，小 Ω 先要算出每一类题目具体有多少道。稍加估计之后小 Ω 很快意识到自己并没有《诗云》中描述的那种存储器，于是断然拒绝了小 N 关于“先把所有可能的题目造好再慢慢分类统计数量”的建议，然后悲剧地意识到自己并不会计算这些数字。

他想叫你帮他解决这个问题，还说如果你成功解决了这个问题，那么在小 N 出那些最大权独立集问题的时候，他会帮你提交一份标程代码。

inputFormat:
第一行， $2$ 个正整数 $n$, $k$。

接下来 $n-1$ 行，每行 $2$ 个正整数 $u_i$, $v_i$，描述一条连接点 $u_i$ 和 $v_i$ 的边，保证这些边构成一棵树。

outputFormat: $nk$ 行，每行一个整数，第 $i$ 个整数表示在所有可能的题目中，最大权独立集大小为 $i$ 的有多少道，答案对 $10^9+7$ 取模。

hint:
**【样例解释】**

符合题意的最大权独立集题目一共有 $2^4=16$ 道。

可以证明，当点 $1$, $3$, $4$ 的权值均为 $1$ 时，最大权独立集为 $3$ ，这样的题目共有 $2$ 道；点 $1$, $3$, $4$ 的权值恰有一个为 $2$ 时，最大权独立集为 $4$ ，这样的题目共有 $6$ 道；对于最大权独立集为 $5$ 或 $6$ 的情况也是类似的。

**【数据范围】**

对于 $15 \%$ 的数据， $n \leq 8$；
对于 $30 \%$ 的数据， $n \leq 30$；
对于 $50 \%$ 的数据， $n \leq 100$；
对于另外 $10 \%$ 的数据， $k=1$；
对于另外 $15 \%$ 的数据， $k=2$；
对于 $100 \%$ 的数据， $n \leq 1000$，$k \leq 5$，$u_{i}, v_{i} \leq n$。

**【提示】**

最大权独立集问题是指：选择一个点集，使得任意两个被选择的点都没有边直接相连，并且使得所有被选择的点的点权之和最大。


title: [SDOI/SXOI2022] 无处存储

background: 滥用本题评测将封号。请注意本题非同寻常的时空限制和数据点个数。

description:
小 Ω 想出一个数据结构题，于是它先造了一棵点有点权的树：

给定一棵大小为 $n$ 的树，编号 $1$ 到 $n$，第 $i \in [2,n]$  个点的父节点记作 $f_i \in [1, i-1]$。另外，每个点 $i$ 有一个点权 $a_i$，初始点权由输入确定，具体方式见输入格式。

在数据结构题里面，需要有对应的修改和查询的操作，而树上最简单的两种非平凡操作当然是链加、链求和了。

因此你需要支持以下两种操作：

`0 x y v`：将树上从 $x$ 到 $y$ 的简单路径上的点的权值增加 $v$；

`1 x y`：求树上从 $x$ 到 $y$ 的简单路径上的点的权值和；

出完之后小 Ω 拿给小 N 看，小 N 表示：

……这也太简单了，这不是轻重链剖分模板题吗？！！

小 Ω 于是想到在刚刚接触 OI 的时候了解到的时间换空间的原理，因此他决定本题的空间限制为 **64 MB**。

inputFormat:
第一行输入三个正整数 $id$，$n$，$q$，其中 $id$ 为子任务编号，和四个非负整数 $A$，$B$，$C$，$a_0$。

$A$，$B$，$C$，$a_0$ 用于生成点权 $a_1, a_2, \dots, a_n$，具体方法是按照下式进行递推：
$$a_{i}=\left(A a_{i-1}^{2}+B a_{i-1}+C\right) \bmod 2^{32}$$

接下来一行 $n-1$ 个正整数表示 $f_2, \dots, f_n$。

接下来 $q$ 行，每行若干整数，形如 $0 \ x' \ y' \ v'$ 或者 $1 \ x' \ y'$，表示一次修改或查询。

其中 $x^{\prime}$，$y^{\prime}$，$v^{\prime}$ 用于**强制在线**，实际操作的 $x=x^{\prime} \operatorname{xor} P$，$y=y^{\prime} \operatorname{xor} P$， $v=v^{\prime} \operatorname{xor} P$，其中 $\operatorname{xor}$ 是 `C/C++` 中的按位异或运算符 `^`，$P = \text{lastans} \And \left(2^{20}-1\right)$，其中 $\text{lastans}$ 为上一次询问的答案（没有上次询问则记为 0），$\And$ 为 `C/C++` 中的按位与运算符 `&`。

outputFormat: 若干行，依次输出每个询问的答案对 $2^{32}$ 取模后的结果。


title: [SDOI/SXOI2022] 多边形

description:
给定一个正 $n$ 边形，除了这个正 $n$ 边形的 $n$ 个顶点，顺时针第 $i$ 条边上还有额外的 $a_i-1$ 个顶点等分这条线段，也就是说，第 $i$ 条边被顶点分成了长度相等的 $a_i$ 段。

你可以在顶点之间连接一些线段，但是连接完线段之后，图中的任意两条新添加的线段只能在端点处有交，此外，新的线段也不应该与多边形的边有所重合。

我们称添加了若干线段之后得到的图为一个三角剖分，当且仅当多边形内的每个面都是一个三角形，注意，三角形的边上可以有原来凸多边形边上的顶点。

给定这样一个凸多边形，其有多少种满足上述条件的三角剖分? 你只需要计算方案数模 $998244353$ 的答案就行。

inputFormat:
第一行输入一个正整数 $n$，表示凸多边形的边数。

第二行输入 $n$ 个正整数，其中第 $i$ 个正整数为 $a_i$，含义如题目描述中所示。

outputFormat: 输出一行一个整数，表示满足题目要求的三角剖分的方案数模 $998244353$ 的结果。

hint:
**【样例 1 解释】**

5 种方案如图所示。

![](https://cdn.luogu.com.cn/upload/image_hosting/v9hip98o.png)

**【数据范围】**

对于 $10 \%$ 的数据，保证 $\sum a_{i} \leq 300$。
对于 $50 \%$ 的数据，保证 $\sum a_{i} \leq 5000$。
对于 $100 \%$ 的数据，保证 $n \geq 3$，$a_{i} \geq 1$， $\sum a_{i} \leq 5 \times 10^{5}$。

注：本题无大样例下载


title: [SDOI/SXOI2022] 整数序列

description:
小 D 三岁就学会了出题。

小 D 有一个正整数序列 $a_1, a_2, \dots a_n$ 和一个整数序列 $b_1, b_2, \dots ,b_n$。

小 D 有 $q$ 次查询，每次给出 $x, y$，构造一个新的序列 $c_1,c_2,\dots ,c_n$，其中 $c_i=\begin{cases}1 & a_i=x \\-1 & a_i = y \\ 0 & \text{else}\end{cases}$。

保证 $c_i$ 中至少存在一个 $1$ 与一个 $-1$。他想让你帮他找到一个区间 $[l,r]$，满足 $\sum\limits_{i = l}^r c_i = 0$，并使得 $\sum\limits_{i = l}^r b_i \times [c_i \neq 0]$ 最大，并且区间里的 $c_i$ 不能都为 $0$。你需要输出这个最大值。

注：当条件 $[P]$ 为真时，$[P]=1$，否则 $[P]=0$。

inputFormat:
第一行有两个整数 $n, q$。
第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。
第三行有 $n$ 个整数，第 $i$ 个整数表示 $b_i$。
接下来 $q$ 行，每行两个整数 $x,y$，表示一次询问。

outputFormat: 对于每次询问，输出一行一个整数表示最大的 $\sum\limits_{i = l}^r b_i \times [c_i \neq 0]$。

samples:
见附加样例文件中的 ex_sequence2.in
见附加样例文件中的 ex_sequence2.out


title: [SDOI/SXOI2022] 进制转换

description:
小 D 两岁的时候就学会了进制转换。

所以他想问你，对于所有 $1\sim n$ 之间的数，这个数在二进制和三进制下的数位和分别是多少。

对于 $i$，记二进制和三进制的数位和分别为 $a(i)$ 和 $b(i)$。比如对于一个数 $i=114$，那么它二进制表示为 $(1110010)_2$，三进制表示为$(11020)_3$，那么 $a(i)$ 和 $b(i)$ 分别为 $4$ 和 $4$。

小 D 想知道你是不是真的能算对 $1$ 到 $n$ 里面所有数进制转换，所以想问你 $\sum\limits_{i = 1}^n x^i y^{a(i)} z^{b(i)}$ 是多少，由于答案很大，请输出答案对 $998244353$ 取模的结果。

inputFormat: 只有一行四个整数，依次表示 $n, x, y, z$。

outputFormat: 输出一行一个整数表示答案。


title: [SDOI/SXOI2022] 子串统计

description:
小 D 四岁半的时候学会了后缀自动机。

你有一个字符串 $S$，长度为 $n$。初始时，$T_0=S$。每次你可以从删除 $T_i$ 的开头或结尾的字符得到新的字符串 $T_{i + 1}$，经过 $n-1$ 次操作之后，我们会得到只有一个字符的串 $T_{n - 1}$，根据每次删除的选择，一共有 $2^{n - 1}$ 种可能的操作序列。注意，虽然可能会有一次操作，删除开头或结尾的字符得到相同的串，但是我们仍然把它当成两种不一样的操作序列。

对于一个串 $T$，我们记 $\operatorname{\textit{occ}}(T)$ 表示 $T$ 在 $S$ 中作为子串的出现次数，比如 $\operatorname{\textit{occ}}(\texttt{aaa},\texttt{aaaabaaa})=3$。

对于一个操作序列，记它贡献是

$$\prod_{i = 1}^{n - 1} \operatorname{\textit{occ}}(T_i)$$

求出所有操作序列的贡献和，由于答案很大，请输出答案对 $998244353$ 取模的结果。

inputFormat: 只有一行一个字符串 $S$，保证只包含小写字符。

outputFormat: 输出一行一个整数表示答案。

samples:
见附加样例文件中的 ex_substring3.in
见附加样例文件中的 ex_substring3.out

hint:
### 数据规模与约定

本题共 $20$ 个测试点。

- 对于测试点 $1\sim 5$，满足 $|S| \le 5000$。
- 对于测试点 $6\sim 8$，满足 $S$ 的每个字符均从 $\texttt a$ 和 $\texttt b$ 中等概率独立随机生成。
- 对于测试点 $9\sim 14$，满足 $|S| \le 6 \times 10^4$。

对于所有数据，$1 \le |S| \le 10^5$。$S$ 中只有小写英文字母。


title: 『JROI-8』对了，还有花，少女，银河

background:
![1663764189387.png](https://img-kysic-1258722770.file.myqcloud.com/9d24e2bd5b20f277e72914b1bc44543e/44b6413b44c70.png)

>「其一」\
即使化身白骨，也有不想忘记的东西

**已获得转载授权。**

description:
给定 $n$，请构造一个长度为 $n$ 的仅包含 $0,1$ 的数字串，满足 $01,00,10,11$ 出现的次数相等。或报告无解。

这里“出现”指与原字符串中连续的一部分完全相同。例如，在 $1011101$ 中，$01,00,10,11$ 分别出现了 $2,0,2,2$ 次。

**请注意，大样例不以文件附加形式给出，而直接放在题目的 输入输出样例 中的 样例 #3**

inputFormat: 一行一个正整数 $n$。

outputFormat:
若有解，输出一行一个长度为 $n$ 的满足条件的仅包含 $0,1$ 的数字串。

若无解，输出 `-1`。


title: 「WHOI-1」HanawoTori

background:
春天到了，花园里的花竞相开放。樱花、梅花、梨花、桃花、牡丹都开放了。

你需要在花园里采花。

日文版题面：[JP 版リンク](https://www.luogu.com.cn/problem/T239022)。

如果你只会 `cout << 1` 这样骗分，建议不要浪费时间在这里。

description:
这个花园是由位于最左边的两个 $\texttt{start}$ 格子加上 $2 \times n$ 个方格组成的一个长列。如下图，$n=6$：

![](https://i.bmp.ovh/imgs/2022/04/07/405bb9192e6cf6d9.png)

注意 $n$ 并不包括最左边的两个 $\texttt{start}$ 格子。每个格子里面都有一棵花，花的美丽程度（下称“**美丽值**”）用一个整数表示，在上图中已经写在格子里了。

从**最左边任选**一个 $\texttt{start}$ 格子开始，每个时刻，你可以走到当前格子**右**、**右上**或**右下**的格子（只要不走出界），并采走里面的花。当走到花园**尽头**时结束。

然后你需要把采到的花按照美丽程度**升序排列**，组成一串花。记**排序过后的**花串中第 $i$ 朵花的美丽值为 $f_i$，那么这串花的“和谐度”$F$ 等于：

$$F = \min_{i=1}^{n-1} \begin{cases} k \times |f_i-f_{i+1}| && |f_i-f_{i+1}| \bmod  b = a \\ |f_i-f_{i+1}| && |f_i-f_{i+1}| \bmod  b  \not = a\\\end{cases}$$

现在知道了花园中每个格子内的花的美丽值，你需要计算出可能的**最大** $F$。即在所有可能的行走方案中，可能出现的最大的 $F$ 值。

inputFormat:
第一行四个整数，代表 $n,a,b,k$；

接下来一行 $n$ 个整数，第 $i$ 个整数代表第 $1$ 行第 $i$ 格内花的美丽值;

接下来一行 $n$ 个整数，第 $i$ 个整数代表第 $2$ 行第 $i$ 格内花的美丽值;

outputFormat: 一行一个整数，表示所求答案。


title: 排队顺序

description: 有 $n(2 \le n\le 10^6)$ 个小朋友，他们的编号分别从 $1$ 到 $n$。现在他们排成了一个队伍，每个小朋友只知道他**后面**一位小朋友的编号。现在每个小朋友把他后面是谁告诉你了，同时你还知道排在队首的是哪位小朋友，请你从前到后输出队列中每个小朋友的编号。

inputFormat:
第一行一个整数 $n$，表示小朋友的人数。

第二行 $n$ 个整数，其中第 $i$ 个数表示编号为 $i$ 的小朋友后面的人的编号。如果这个数是 $0$，则说明这个小朋友排在最后一个。

第三行一个整数 $h$，表示排在第一个的小朋友的编号。

outputFormat: 一行 $n$ 个整数，表示这个队伍从前到后所有小朋友的编号，用空格隔开。


title: 「WHOI-2」Regex

background:
 _JP 版は下記のリンクをクリックしてダウンロードしてください。_

正则表达式是文本处理的一个有用的工具。

3022 年，你看到了你以前写过的一个 Python 程序，用来某插画交流网站上面下载图片。

你很感兴趣，决定试着运行一下。结果因为年代久远，里面的正则表达式损坏了。你得恢复这个正则表达式。

然而损坏的程度有点严重……

description:
在这里我们只考虑正则表达式的一个子集。

- **单字符**，即单独的—个字符，必须为小写字母或数字。

- **单元表达式**，指的是形如 `<x>-<y>` 的三个字符组成的字符串。其中的 `<x>` 和 `<y>` 为单字符。注意：`<x>` 和 `<y>` 必须**类型相同**，即均为数字或均为小写字母。并且 `<x>` 的 ASCII 码值必须**严格小于** `<y>`。比如 `3-5`、`a-d` 是合法的，而 `7-b`、`z-3`、`8-2` 是不合法的。

- **表达式**，指的是用**中括号**括起来的**一个或多个**单元表达式或单字符，比如 `[1-2]`、`[0-9a-f]`、
`[a-chg-k]`。在这里中括号**不允许嵌套**。在右括号后面可以有星号 `*` 或加号 `+` 修饰（两者最多只能有一个，**不能同时出现**）。比如 `[3-5]*`、`[pixi-v]+`。

- 一个合法的正则表达式由**一个或多个**表达式或单字符组成。比如 `0x[0-9af]*`、`1[3-7]2345`、`0[7-9]*1`。

现在你知道这个残缺的正则表达式，其中残缺的字符用问号 `?` 表示。

你需要计算出原来的正则表达式有多少种可能。
答案可能过大，对 $1000000007$ 取模即可。

inputFormat: 一行一个字符串，表示残缺的正则表达式。

outputFormat: 一行一个整数，表示所求方案数取模后的结果。


title: 「WHOI-2」彗星蜜月

background:
![](bilibili:BV11x411Q7PY)

看完这首 mv 的前奏之后你应该知道 $f$ 是什么鬼了（误）。

description:
定义 $f(x)$ 是 $x$ 的各位数码翻转以后形成的数。

例如：

- $f(12323)=32321$
- $f(114514)=415411$
- $f(250)=52$
---

给定一个 $n$。求最大的 $k$，使得对于所有处于 $[1,k]$ 区间中的正整数 $m$，有 $f(m)\leq n$。

inputFormat:
**本题多测**

第一行一个正整数 $T$ 表示测试点数目。

接下来每个测试点一个正整数 $n$。

outputFormat: $T$ 行，对应每个测试点的答案。


title: 「WHOI-2」D&D

background:
有没有发现少了什么？

我们的 miku 决定出门逛街了。但是好巧不巧的就是她家里的装饰物少的可怜，并且只有一些数字可以作为装饰。

但是 miku 发现如果有若干个装饰物组成的数集 $A$，那么 $A$ 的子集 $f(A)$ 是最好看的（尽管不知道为什么）。所以就有了这道题。

但是因为看到了标题，所以聪明的你应该知道 miku 要去哪里了（误）。

description:
给定**不重**集合 $A$，定义其 _装饰子集_

$$f(A)=\{a\in A|\forall b\in A-\{a\},a|b\not= b \}$$

这里的 $\texttt{“|”}$ 表示按位或；这里 $b\in A-\{a\}$ 表示 $b\in A$ 且 $b\not=a$。

miku 有一个长度为 $n$ 的正整数序列 $a_i$。你要给这个序列连续地划分为若干个（至少一个）连续子串。要求这些连续子串元素所组成的**不重集合**的 _装饰子集_ 相同。

求方案数对 $10^9+7$ 取模。

inputFormat:
第一行一个正整数表示 $n$。

接下来长度为 $n$ 的正整数序列表示 $a_i$。

outputFormat: 一行一个正整数表示答案。


title: [CoE R5] 暴龙的白菜

background: 暴龙爱吃白菜。

description:
给定一个字符串，由 $1$ 个 $\texttt{1}$，$2$ 个 $\texttt{2}$，$3$ 个 $\texttt{3}$，$4$ 个 $\texttt{4}$，$5$ 个 $\texttt{5}$，$6$ 个 $\texttt{6}$，$7$ 个 $\texttt{7}$，$8$ 个 $\texttt{8}$，$9$ 个 $\texttt{9}$，$10$ 个 $\texttt{10}$……以此类推，依次拼接而成。

询问字符串第 $l$ 位到第 $r$ 位的数字之和。

inputFormat:
**输入包含多组测试数据。**

第一行一个正整数 $T$。

接下来 $T$ 组问询，每次两个正整数 $l,r$。

outputFormat: $T$ 行，每行一个整数代表答案。


title: 单向链表

description:
实现一个数据结构，维护一张表（最初只有一个元素 $1$）。需要支持下面的操作，其中 $x$ 和 $y$ 都是 $1$ 到 $10^6$ 范围内的正整数，且保证任何时间表中所有数字均不相同，操作数量不多于 $10^5$：

- `1 x y` ：将元素 $y$ 插入到 $x$ 后面；
- `2 x` ：询问 $x$ 后面的元素是什么。如果 $x$ 是最后一个元素，则输出 $0$；
- `3 x`：从表中删除元素 $x$ **后面的那个元素**，不改变其他元素的先后顺序。

inputFormat:
第一行一个整数 $q$ 表示操作次数。

接下来 $q$ 行，每行表示一次操作，操作具体间题目描述。

outputFormat: 对于每个操作 2，输出一个数字，用换行隔开。


title: [SNOI2022] 垃圾回收

description:
通常的情况下，编程语言在管理内存时进行如下的选择：

- 让用户进行手动内存管理（C、C++、Rust 等），这会收获很好的性能，但是给用户提供了很大的编程负担。
- 使用垃圾回收系统（Java、Go 等），这需要维护一个运行时系统，并且在内存使用和程序性能方面造成了许多不可预测的负担。

尽管存在许多的问题，目前最通用的自动化内存管理手段始终为 Tracing Garbage Collector。这种做法的最基础的思路是维护对象间的引用关系，形成一张图，每次回收时通过扫描引用关系推导出已经无法被访问到的对象，释放它们占用的内存。而这种传统的做法最大的问题在于维护引用链需要造成很大的开销，并且随着维护的对象越多，扫描的代价也会越大。

小 L 是一个喜欢思考的女孩子，她发现维护 Garbage Collector 是一件非常复杂的事情，于是她决定考虑一个更简单的模型（注意它与任何现实中的 GC 规则可能是完全不同的！）。

对于一个 $n$ 个点 $m$ 条边的无向图，没有重边自环，点和边均从 $1$ 开始标号。其中每个节点代表一个占用了一定内存的对象，每条边对应一个引用关系（注意这里的引用关系是**无向**的），程序从第 $0$ 秒开始运行，在第 $q + 1$ 秒结束运行。对于 $i = 1, 2, 3, \dots, q$ 的每个时刻 $i$ 发生以下两种操作之一：

- DELETE $i$，删除边 $(x_i,y_i)$，保证不会删除已经被删除的边。
- GC， 进行一次内存回收，即杀死所有从起点出发不能访问到的点，释放它们占用的内存。（注意这里对节点的删除不会删除与这些点相连的边）

你可以认为这些操作是被瞬间执行完成的，在所有操作执行后，也就是第 $q + 1$ 秒，程序结束，删除所有剩余的节点（包括 $1$ 号点）。

第 $i$ 个点占用的内存为 $a_i$，现在请你求出 $\sum_{i = 1}^{n} a_i \cdot \mathit{alive}_i$，这里 $\mathit{alive}_i$ 表示第 $i$ 个点存活的时间，在第 $0$ 秒，所有节点都是存活的。

inputFormat:
输入的第一行是三个正整数 $n, m, q$，分别表示对象的个数，引用关系的个数，操作的个数。

接下来的 $m$ 行每行两个正整数 $x_i, y_i$ 表示第 $i$ 条引用关系的两个端点。

接下来的 $q$ 行每行为以下两种形式之一，第 $i$ 行表示在第 $i$ 秒发生的操作：

- 字符串 DELETE 和正整数 $x$，含义见【题目描述】。
- 字符串 GC，含义见【题目描述】。

接下来的一行有 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示每个对象占用的内存大小。

outputFormat: 输出一行一个整数表示答案，含义见【题目描述】。

samples:
6 6 8
1 2
2 3
2 4
1 4
2 5
1 6
GC
DELETE 5
DELETE 3
GC
DELETE 1
GC
DELETE 2
GC
1 2 3 4 5 6

samples:
样例 2 见附件 garbage2.in
本组数据满足测试点 6 的限制。

samples:
样例 3 见附件 garbage3.in
本组数据满足测试点 11 的限制。


title: [SNOI2022] 军队

description:
R 国的历史非常悠久。

R 国有 $n$ 个城市，国内有 $C$ 个党派，分别记为 $1,2,\dots,C$。由于 R 国的版图非常长，这 $n$ 个城市的位置可以近似为坐标轴上的 $n$ 个点。在历史的最初，记载了第 $i$ 个城市归属党派 $c_i$，城中有数量为 $a_i$ 的军队。

R 国的历史上，经常发生以下三种事件：

1. 党派 $y$ 进行了一次游说，使城市 $l$ 到城市 $r$ 的所有归属党派 $x$ 的城市全部归属了 $y$。

2. 党派 $x$ 进行了一次征兵，使城市 $l$ 到城市 $r$ 的所有归属党派 $x$ 的城市中的军队数量增加了 $v$。

3. 城市 $l$ 到城市 $r$ 之间的所有城市爆发了战争。这场战争的规模可以描述为两地之间的所有城市中的军队数量之和。注意战争不一定发生在不同党派之间，归属同一个党派的一些城市内部也可能发生内战。由于 R 国的医护系统足够先进，战争不会造成军队数量的减少。

小 N 是一个喜欢历史的女孩子，最近她想整理一下 R 国的战争史，特别是每场战争的规模。但是由于 R 国的历史实在太长了，她用纸和笔进行运算实在力不从心。于是她找到了你，希望你写一个程序，统计出 R 国历史上所有战争的规模。

inputFormat:
输入的第一行是三个正整数 $n,q,C$，分别表示城市的个数，事件的个数，和 R 国国内党派的个数。

接下来一行有 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示每个城市内初始的军队数。

接下来一行有 $n$ 个正整数 $c_1,c_2,\dots,c_n$，表示每个城市初始归属的党派。

接下来 $q$ 行，每行 $3$ 到 $5$ 个正整数，表示一次事件：

第一个正整数 $\mathit{op}$ 表示事件的类型。$\mathit{op}=1,2,3$ 分别表示【题目描述】中所述的游说，征兵和战争事件。

对于每个游说事件，接下来有 $4$ 个正整数 $l,r,x,y$，意义见【题目描述】。

对于每个征兵事件，接下来有 $4$ 个正整数 $l,r,x,v$，意义见【题目描述】。

对于每个战争事件，接下来有 $2$ 个正整数 $l,r$，意义见【题目描述】。

outputFormat: 对于每个战争事件，输出一行一个整数，表示此次战争的规模。

samples:
样例 2 见附件 military2.in
本组数据满足测试点 4 的限制。

samples:
样例 3 见附件 military3.in
本组数据满足测试点 14 的限制。

samples:
样例 4 见附件 military4.in
本组数据满足测试点 18 的限制。


title: [SNOI2022] 倍增

description:
小 Z 是一个喜欢编程的女孩子。

这天，她在做一道编程题的时候偶然发现了一个神奇的整数 $142857$。

$142857 \times 2 = 285714$，而 $285714$ 的所有数位恰好是 $142857$ 的一个排列。

她很好奇，有没有更大的满足这种性质的整数。

她写了一个搜索，发现了一些更大的有趣的数：

$26835741 \times 2 = 53671482$

$0987312654 \times 2 = 1974625308$

$\dots$

她不满足于解决十进制下这样的问题，于是她想知道，是否在 $B$ 进制下存在一个 $n$ 位正整数 $x$，满足 $2x$ 的所有数位在 $B$ 进制下是 $x$ 的所有数位的一个排列。

由于她讨厌数字 $0$，因此她还要求对于任意 $1 \leq i \leq n$，$x$ 和 $2x$ 在 $B$ 进制下的第 $i$ 位不能同时为 $0$。

inputFormat:
**输入包含多组数据。**

输入的第一行是一个正整数 $T$，表示数据组数。

接下来 $T$ 行，第 $i$ 行包含两个正整数 $n$ 和 $B$，表示第 $i$ 组数据。

outputFormat:
对于每组数据，输出一行。

若本组数据有解，按照从高位到低位的顺序输出 $n$ 个非负整数，表示你找到的答案在 $B$ 进制下的值。

否则只需要输出一个数 $-1$。

samples:
样例 2 见附件 double2.in
本组数据满足测试点 3 的限制。

samples:
样例 3 见附件 double3.in
本组数据满足测试点 17 的限制。

hint:
**【样例 1 解释】**

- 第一组数据的解释参见【题目描述】。
- 对于第二组数据，可以通过枚举所有的 $n$ 位 $B$ 进制数说明一定不能找到这样的正整数。
- 对于第三组数据，$2x$ 的 $7$ 进制表示为 $103635_{(7)}$，因此这是一个满足题意的答案。

注意此样例的答案文件仅表明了一种可能的合法答案，不表明答案文件恰好对应标准程序的输出。

**【样例 2/3 解释】**

注意此样例的答案文件仅表明了一种可能的合法答案，不表明答案文件恰好对应标准程序的输出。

**【提示】**

由于答案可能不唯一，我们下发了校验器 `checker.cpp` 和库文件 `testlib.h`。

可以使用以下命令编译 `checker.cpp`：

```
g++ -o checker checker.cpp -O2 -std=c++11
```

将 `checker.cpp` 编译得到可执行文件 `checker` 后你可以使用以下方式测试你的答案：

`checker <input> <output> <answer>`：利用选手目录下的 `double/double*.ans` 可以用来检验你的答案在样例测试点 `double/double*.in` 的正确性。

`checker <input> <output> <output>`：会检查你的所有有解输出是否符合题目要求。注意以此种方式测试的时候，输出无解总会被报告为合法，因为在此种运行方式下我们只会检查你报告的所有解。

**请选手注意多组数据之间的清空问题。**

**【数据规模与约定】**

对于全部数据，$1 \leq T \leq 10^4$，$2 \leq \sum B \leq 2 \times 10^5$，$1 \leq \sum n \leq 2 \times 10^5$，$n \geq 1$，$B \geq 2$。

具体的数据规模与约定见下表。

| 测试点编号 |    $n \leq$     |    $ B \leq$    | $T \leq$ | 特殊约定            |
| :--------: | :-------------: | :-------------: | :------: | ------------------- |
|    $1$     |       $8$       |       $8$       |   $10$   |                     |
|    $2$     |       $8$       |       $8$       |  $10^4$  |                     |
|    $3$     | $2 \times 10^5$ |       $8$       |   $10$   |                     |
|    $4$     | $2 \times 10^5$ |       $8$       |  $10^4$  |                     |
|    $5$     | $2 \times 10^5$ |       $8$       |  $10^4$  |                     |
|    $6$     |      $15$       |      $15$       |  $100$   |                     |
|    $7$     |      $40$       |      $40$       |  $100$   |                     |
|    $8$     |      $100$      |      $100$      |  $100$   |                     |
|    $9$     |      $300$      |      $300$      |  $100$   |                     |
|    $10$    |     $1000$      |     $1000$      |  $100$   |                     |
|    $11$    |     $3000$      |     $3000$      |  $100$   |                     |
|    $12$    |     $15000$     |     $15000$     |  $100$   |                     |
|    $13$    |     $50000$     |     $50000$     |  $100$   |                     |
|    $14$    | $2 \times 10^5$ | $2 \times 10^5$ |  $100$   |                     |
|    $15$    |      $200$      |      $200$      |  $10^4$  | $n \geq 100$        |
|    $16$    |     $5000$      |     $5000$      |  $10^4$  | $n \geq 100$        |
|    $17$    | $2 \times 10^5$ | $2 \times 10^5$ |  $10^4$  | $n \geq 100$        |
|    $18$    |      $300$      |      $300$      |  $10^4$  | $B=3k-1,k \in \N^*$ |
|    $19$    | $2 \times 10^5$ | $2 \times 10^5$ |  $10^4$  | $B=3k-1,k \in \N^*$ |
|    $20$    |      $300$      |      $300$      |  $10^4$  | $B=3k,k \in \N^*$   |
|    $21$    | $2 \times 10^5$ | $2 \times 10^5$ |  $10^4$  | $B=3k,k \in \N^*$   |
|    $22$    |      $100$      |      $100$      |  $10^4$  |                     |
|    $23$    |      $500$      |     $5000$      |  $10^4$  |                     |
|    $24$    | $2 \times 10^5$ | $2 \times 10^5$ |  $10^4$  |                     |
|    $25$    | $2 \times 10^5$ | $2 \times 10^5$ |  $10^4$  |                     |


title: [SNOI2022] 数位

description:
小 S 是一个喜欢数数的女孩子。

有一天，她在睡前躺在床上数数，当她数到 $977431$ 的时候，她终于困了，并且决定睡觉。但此时她突然发现这个数字的各位数码是单调不增的！她觉得这相当有趣，于是她又睡不着了。

她想知道有多少个数在 $L, R$ 之间，并且它的各位数码是单调不增的。但这个问题太无聊了。

她又想知道有多少数对 $(a, b)$ 在 $L, R$ 之间，并且 $(a + b)$ 的各位数码是单调不增的。但这个问题也太无聊了。

终于，她想到了一个有趣一些的问题：

给定整数 $L, R, k$，求有多少个 $k$ 维向量 $(a_1, a_2, ..., a_k)$ 满足 $(a_1 + a_2 + ... + a_k)$ 的数码是单调不增的，并且 $\forall i \in [1, k],  L \leq a_i \leq R$。

由于答案可能很大，请你输出它对 $998244353$ 取模的结果。

inputFormat:
输入的第一行是一个正整数 $L$，含义见【题目描述】

输入的第二行是一个正整数 $R$，含义见【题目描述】。

输入的第三行是一个正整数 $k$，含义见【题目描述】。

outputFormat: 输出一行一个整数表示合法的向量数，答案 $998244353$ 取模。

samples:
样例 4 见附件 digit4.in
样例 4 见附件 digit4.ans

samples:
样例 5 见附件 digit5.in
样例 5 见附件 digit5.ans


title: [PFOI Round1] 暴龙的火锅

background: 暴龙爱吃火锅。

description:
定义 $S(x)$ 表示 $x$ 的每一位的数字之和，例如：$S(14)=1+4=5$，$S(114514)=1+1+4+5+1+4=16.$

另外，定义 $fib(x)$ 代表斐波那契数列的第 $x$ 项，具体地：

$$fib(1)=fib(2)=1,\ fib(x)=fib(x-1)+fib(x-2)\ (x≥3).$$

现在给定 $n$，求出下式的值，其中 $\bmod 9$ 表示对 $9$ 取余数：

$$(S(fib(1))+S(fib(2))+S(fib(3))+...+S(fib(n))) \bmod 9.$$

inputFormat:
第一行一个整数 $T$。

接下来 $T$ 组问询，每次一个整数 $n$。

outputFormat: $T$ 行，每行一个整数代表答案。

hint:
【样例解释】

对于第一组询问，$n=7$，答案为：

$$
\begin{aligned}
& \ \ \ \ \ (S(fib(1))+S(fib(2))\ldots+S(fib(6))+S(fib(7)))\bmod 9 \\
& =(1+1+2+3+5+8+(1+3))\bmod 9 \\
& =6.
\end{aligned}
$$

---

【数据范围】

**「本题采用捆绑测试」**

- $\texttt{Subtask 1(10 pts)：}T=1,\ n\le 10$；
- $\texttt{Subtask 2(30 pts)：}T=10^2,\ n\le 10^3$；
- $\texttt{Subtask 3(60 pts)：}$无特殊限制。

对于 $100\%$ 的数据，满足 $1\le T\le 10^5,\ 1\le n\le 10^6$。


title: [POI2000] 条纹

description:
条纹游戏是一个双人的游戏。所需要的物品有一个棋盘以及三种颜色的长方形条纹，这三种颜色分别是红色、绿色和蓝色。所有的红色条纹的尺寸是 $c \times 1$，所有的绿色条纹的尺寸是 $z \times 1$，所有的蓝色条纹的尺寸是 $n \times 1$，这里 $c,z,n$ 是正整数。每种颜色的条纹每个游戏者都拥有无限多个。

一个棋盘是一个尺寸为 $p \times 1$ 的长方形，由 $p$ 个 $1 \times 1$ 的方格组成。

游戏者轮流走，每一步都是由一个游戏者任选一种长方形条纹覆盖到棋盘上，并要求遵循以下规则：

1. 条纹不能伸出棋盘之外。
2. 不能覆盖在已有的条纹之上（即使部分也不行）。
3. 条纹的边缘必须与棋盘方格的边缘相重叠。谁不能再走，谁就输了。

先手是指在游戏中第一个走的游戏者。那么是否不管后手怎么走，先手都有必胜策略呢？

请你编写一个程序：

1. 读入条纹的尺寸以及至少一个棋盘的尺寸。
2. 对每一个给出的棋盘判断先手是否必胜。
3. 将结果输出。

inputFormat:
第 $\text{1}$ 行包含三个整数 $c,z,n$，表示三种条纹的长度，依次为红色，绿色以及蓝色。每两个数之间都用空格隔开。

文件的第 $\text{2}$ 行包括一个整数 $m$ 表示需要考虑的不同棋盘个数。以下 $\text{3}$ 到 $\text{m+2}$ 行每行包括一个整数 $p$ ,第 $\text{i+2}$ 行表示第 $\text{i}$ 个棋盘的长度。

outputFormat:
应当包含 $m$ 行。只有一个数字应当被写入文件的第 $i$ 行：

如果对第 $i$ 个棋盘先手有必胜策略，输出 $1$，否则输出 $2$。


title: 种树

background: 小 Rf 不是很喜欢种花，但是他喜欢种树。

description:
路边有 $n$ 棵树，每棵树的 **高度** 均为正整数，记作 $p_1, p_2 \dots p_n$。

定义一棵树的 **宽度** 为它高度的正因数个数，这些树能覆盖的距离为它们宽度的乘积，你想请你的朋友们来乘凉，但你发现这些树能覆盖的距离不够多。

于是你买了总量为 $w$ 单位的神奇化肥。你可以施若干次肥，每次你可以使用 $k$ 单位化肥（**要求 $k$ 必须为当前化肥量的正因数**），让任意一棵树的高度乘上 $k$，同时你剩余的化肥量也会除以 $k$。每次施肥的树可任意选择，且每次施肥选择的树不需相同。

你需要最大化这些树所能覆盖的距离，并输出这个最大距离。答案对 $998244353$ 取模。

inputFormat:
从标准输入中读入数据。

第一行，两个正整数 $n$ 与 $w$。

第二行 $n$ 个正整数 $p_1, p_2 \dots p_n$。

outputFormat:
输出到标准输出。

仅一行一个整数，代表答案对 $998244353$ 取模后的结果。


title: 「SFCOI-3」进行一个列的排

background:
![](https://cdn.luogu.com.cn/upload/image_hosting/8v9kbxjs.png)

（其实这题原来叫 I must say No，不过出于某些显然的原因就改题目名了 /kk）

You must say Yes.

（题目背景图片来自 Phigros 曲绘，如有侵权，请告知出题人。）

description:
小 R 有一个长度为 $n$ 的排列 $p_1\dots p_n$。换句话说，$p_1\dots p_n$ 包含 $0 \sim (n - 1)$ 之间的数，并且满足对于 $0 \sim (n - 1)$ 这 $n$ 个数，每个数在 $p$ 中出现且仅出现一次。

小 R 有 $n$ 个限制，其中第 $i(0 \leq i \leq n - 1)$ 个用一个![](cnm,shabierLeasier)**正整数** $L_i$ 描述，表示至少有一个长度为 $L_i$ 的区间 $[l, r]$（即 $r - l + 1 = L_i$）满足 $\operatorname{mex}_{k=l}^r p_k = i$。

小 R 丢失了排列 $p_1\dots p_n$，不过幸运的是她仍然记得这 $n$ 条限制。请你帮她求出总共有多少个初始的合法排列，答案对 $998244353$ 取模。

inputFormat:
**本题每个测试点有多组数据。**

第一行一个整数 $T$ 表示数据组数。对于每组数据：

+ 第一行一个整数 $n$。
+ 第二行 $n$ 个整数依次表示 $L_0\dots L_{n-1}$。

outputFormat: 共 $T$ 行，每行一个整数表示答案。

hint:
### 定义

+ 一个序列的 $\operatorname{mex}$ 是其中没有出现过的最小非负整数，如 $\operatorname{mex}\{1, 3, 4\} = 0$，$\operatorname{mex}\{0, 1, 1, 2, 5\} = 3$，$\operatorname{mex}\{3, 1, 0, 2\} = 4$。

### 数据规模与约定

+ Subtask 0（10 pts）：$n \leq 10$。
+ Subtask 1（30 pts）：$n \leq 18$。
+ Subtask 2（15 pts）：$n \leq 300$。
+ Subtask 3（45 pts）：无特殊限制。

对于所有数据，$1 \leq T \leq 10$，$1 \leq n \leq 5 \times 10^3$，$1 \leq L_i \leq n$。


title: [POI2001] Goldmine

description:
$\text{Byteman}$ 作为 $\text{Byteland}$ 的 $\text{The Goldmine}$（某一公司厂矿）的最有功的雇员之一，即将在年末退休。

为了表示对他的认真勤恳的工作的承认，$\text{The Goldmine}$ 的管理层愿意奖励他一小块长方形的矿地，此矿地长和宽为 $s$  和 $w$ ，且平行于坐标系统的轴线。长方形矿地的位置可由他自己选。当然，这块地的价值会随着位置的不同而不同。其价值是指这块区域内天然金矿石的数量（若矿石位于这块地的边缘，我们同样认为他是属于这个区域的）。

你们的任务是计算出这块地的最大可能价值（即：为它选择最佳位置）。为简便起见，我们假定整个金矿的矿区是无穷的，但含有天然金矿石的区域却是有限的。

请你编写一个程序：

1. 读入天然金矿石的位置。

2. 计算这块地的最大可能价值（即：求给定大小的这块地所含的天然金矿石的最大数）。

inputFormat:
第一行输入两个正整数 $s,w$，各自代表着此矩形区域平行 $X$ 轴和 $Y$ 轴的边的长度。

第二行输入一个正整数 $n$，它表示此金矿矿区内天然矿石的数量。接下来的 $n$ 行，每行输入两个用单个空格隔开的整数 $x,y$，它们分别表示了某一天然金矿石的 $X$ 坐标和 $Y$ 坐标。

outputFormat: 输出一个整数，表示此块给定大小的矿地的最高价值。


title: [POI2001] 绿色游戏

description:
绿色游戏是一种两人游戏，双方分别称 $\text{Ann}$ 和$\text{Billy}$。游戏的内容主要是轮流在棋盘上移动一颗棋子。

棋盘上的点一部分是绿色的，其余是白色的。它们全部从 $1$ 至 $a+b$ 编号。编号 $1$ 至 $a$ 的点属于 $\text{Ann}$ ，编号 $a+1$ 至 $a+b$ 的点属于 $\text{Billy}$。每个点都有一些后继点，均可一步到达。属于 $\text{Ann}$ 的点的后继点一定属于 $\text{Billy}$，反之亦然。所有的点都至少有一个后继点，这样总可以往下走一步。

游戏开始时把棋子放在任意的一点 $P$ 上，然后双方轮流移动棋子至当前所在点（属于移动方）的一个后继点上（属于对手）。游戏由点 $P$ 的拥有者开始，结束时棋子第二次到达了某一点，称点 $Q$。如果在从点 $Q$ 至点 $Q$ 的一连串移动中，棋子至少一次被放到绿色点上，则 $\text{Ann}$ 赢。若从点 $P$ 开始，不管 $\text{Billy}$ 如何移动， $\text{Ann}$ 总能保证赢得这次游戏，则称 $\text{Ann}$ 对起始点 $P$ 有必胜的策略。

请你编写一个程序：

1. 读入对棋盘的描述。

2. 算出 $\text{Ann}$ 有必胜策略的起始点。

inputFormat:
首行有两个整数 $a$ 和 $b$ ，两个整数之间用一个空格分开，分别表示属于 $\text{Ann}$ 和 $\text{Billy}$ 的点数 $(1 \le a，b \le 3000)$。以下 $a+b$ 行是对各点的描述，先描述 $\text{Ann}$ 的点，再描述 $\text{Billy}$ 的点。

第 $i+1$ 行（$1 \le i \le a+b$） 以整数 $z，k$ 开始：$z$ 表示点 $i$ 的颜色（$O$－白色，$I$－绿色），$k$ 表示后继点的数目。然后是 $K$ 个整数（$2 \le k \leq a+b$），写在同一行，代表点 $i$ 后继点的编号，这些整数均用一个空格分开。绿点的个数不超过 $100$ ，所有点的后继点的个数之和不超过 $30000$ 。

outputFormat: 首行仅一个整数 $L$ ，代表 $\text{Ann}$ 有 $L$ 个有必胜策略的起始点。以下 $L$ 行按升序顺序依次给出这些点的编号。