title: [蓝桥杯 2017 省 A] 油漆面积

description:
X 星球的一批考古机器人正在一片废墟上考古。

该区域的地面坚硬如石、平整如镜。

管理人员为方便，建立了标准的直角坐标系。

每个机器人都各有特长、身怀绝技。它们感兴趣的内容也不相同。

经过各种测量，每个机器人都会报告一个或多个矩形区域，作为优先考古的区域。

矩形的表示格式为 $(x_1,y_1,x_2,y_2)$，代表矩形的两个对角点坐标。

为了醒目，总部要求对所有机器人选中的矩形区域涂黄色油漆。

小明并不需要当油漆工，只是他需要计算一下，一共要耗费多少油漆。

其实这也不难，只要算出所有矩形覆盖的区域一共有多大面积就可以了。

注意，各个矩形间可能重叠。

本题的输入为若干矩形，要求输出其覆盖的总面积。

inputFormat:
第一行，一个整数 $n$，表示有多少个矩形 $(1 \le n<10000)$。

接下来的 $n$ 行，每行有 $4$ 个整数 $x_1$，$y_1$，$x_2$，$y_2$，空格分开，表示矩形的两个对角顶点坐标。

$(0 \le x_1,y_1,x_2,y_2 \le 10000)$。

outputFormat: 一行一个整数，表示矩形覆盖的总面积。

hint: 蓝桥杯 2022 省赛 A 组 J 题。


title: [蓝桥杯 2017 省 B] k 倍区间

type: P

description:
给定一个长度为 $N$ 的数列，$A_1,A_2, \cdots A_N$，如果其中一段连续的子序列 $A_i,A_{i+1}, \cdots A_j(i \le j)$ 之和是 $K$ 的倍数，我们就称这个区间 $[i,j]$ 是 $K$ 倍区间。

你能求出数列中总共有多少个 $K$ 倍区间吗？

inputFormat:
第一行包含两个整数 $N$ 和 $K$$(1 \le N,K \le 10^5)$。

以下 $N$ 行每行包含一个整数 $A_i$$(1 \le A_i \le 10^5)$。

outputFormat: 输出一个整数，代表 $K$ 倍区间的数目。

hint: 时限 2 秒, 256M。蓝桥杯 2017 年第八届


title: [蓝桥杯 2017 国 C] 小数第 n 位

description:
我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。

如果我们把有限小数的末尾加上无限多个 $0$，它们就有了统一的形式。

本题的任务是：在上面的约定下，求整数除法小数点后的第 $n$ 位开始的 $3$ 位数。

inputFormat: 一行三个整数：$a$，$b$，$n$，用空格分开。$a$ 是被除数，$b$ 是除数，$n$ 是所求的小数后位置（$0<a,b,n<10^9$）

outputFormat: 一行 $3$ 位数字，表示：$a$ 除以 $b$，小数后第 $n$ 位开始的 $3$ 位数字。

hint: 时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛


title: [蓝桥杯 2017 国 C] 分考场(假题：最小色数)

description:
$n$ 个人参加某项特殊考试。

为了公平，要求任何两个认识的人不能分在同一个考场。

求最少需要分几个考场才能满足条件。

inputFormat:
第一行，一个整数 $n(1<n<100)$，表示参加考试的人数。

第二行，一个整数 $m$，表示接下来有 $m$ 行数据。

以下 $m$ 行每行的格式为：两个整数 $a$，$b$，用空格分开 $(1 \le a,b \le n)$ 表示第 $a$ 个人与第 $b$ 个人认识（编号从 $1$ 开始）。

outputFormat: 一行一个整数，表示最少分几个考场。

hint: 时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛


title: [蓝桥杯 2017 国 C] 合根植物

description:
w 星球的一个种植园，被分成 $m \times n$ 个小格子（东西方向 $m$ 行，南北方向 $n$ 列）。每个格子里种了一株合根植物。

这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

inputFormat:
第一行，两个整数 $m$，$n$，用空格分开，表示格子的行数、列数（$1<m,n<1000$）。

接下来一行，一个整数 $k$，表示下面还有 $k$ 行数据 $(0<k<10^5)$。

接下来 $k$ 行，每行两个整数 $a$，$b$，表示编号为 $a$ 的小格子和编号为 $b$ 的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。

比如：$5 \times 4$ 的小格子，编号：

```
1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16
17 18 19 20
```

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

hint:
## 样例解释

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

时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛


title: [蓝桥杯 2017 国 B] 发现环

description:
小明的实验室有 $N$ 台电脑，编号 $1 \sim N$。原本这 $N$ 台电脑之间有 $N-1$ 条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。

不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了 BUG。

为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？

inputFormat:
第一行包含一个整数 $N$。

以下 $N$ 行每行两个整数 $a$ 和 $b$，表示 $a$ 和 $b$ 之间有一条数据链接相连。

输入保证合法。

outputFormat: 按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。

hint:
对于 $30\%$ 的数据，$1 \le N \le 1000$。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le a,b \le N$。

时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛


title: [蓝桥杯 2017 国 B] 对局匹配

description:
小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。

小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是 $K$ 的两名用户匹配在一起。如果两人分差小于或大于 $K$，系统都不会将他们匹配。

现在小明知道这个网站总共有 $N$ 名用户，以及他们的积分分别是 $A_1,A_2, \cdots A_N$。

小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来（任意两名用户积分差不等于 $K$）？

inputFormat:
第一行包含两个个整数 $N$ 和 $K$。

第二行包含 $N$ 个整数 $A_1,A_2, \cdots, A_N$。

outputFormat: 一个整数，代表答案。


title: [蓝桥杯 2017 国 B] 观光铁路

description:
跳蚤国正在大力发展旅游业，每个城市都被打造成了旅游景点。

许多跳蚤想去其他城市旅游，但是由于跳得比较慢，它们的愿望难以实现。这时，小 C 听说有一种叫做火车的交通工具，在铁路上跑得很快，便抓住了商机，创立了一家铁路公司，向跳蚤国王请示在每两个城市之间都修建铁路。

然而，由于小 C 不会扳道岔，火车到一个城市以后只能保证不原路返回，而会随机等概率地驶向与这个城市有铁路连接的另外一个城市。

跳蚤国王向广大居民征求意见，结果跳蚤们不太满意，因为这样修建铁路以后有可能只游览了 $3$ 个城市（含出发的城市）以后就回来了，它们希望能多游览几个城市。于是跳蚤国王要求小 C 提供一个方案，使得每只跳蚤坐上火车后能多游览几个城市才回来。

小 C 提供了一种方案给跳蚤国王。跳蚤国王想知道这个方案中每个城市的居民旅游的期望时间（设火车经过每段铁路的时间都为 $1$），请你来帮跳蚤国王。

inputFormat:
输入的第一行包含两个正整数 $n$、$m$，其中 $n$ 表示城市的数量，$m$ 表示方案中的铁路条数。

接下来 $m$ 行，每行包含两个正整数 $u$、$v$，表示方案中城市 $u$ 和城市 $v$ 之间有一条铁路。

保证方案中无重边无自环，每两个城市之间都能经过铁路直接或间接到达，且火车由任意一条铁路到任意一个城市以后一定有路可走。

outputFormat:
输出 $n$ 行，第 $i$ 行包含一个实数 $t_i$，表示方案中城市 $i$ 的居民旅游的期望时间。你应当输出足够多的小数位数，以保证输出的值和真实值之间的绝对或相对误差不超过 $10^{-9}$。

感谢 @[zhang_kevin](https://www.luogu.com.cn/user/679961) 提供 Special Judge.

hint:
对于 $10\%$ 的测试点，$n \le 10$；

对于 $20\%$ 的测试点，$n \le 12$；

对于 $50\%$ 的测试点，$n \le 16$；

对于 $70\%$ 的测试点，$n \le 19$；

对于 $100\%$ 的测试点，$4 \le k \le n \le 21$，$1 \le u,v \le n$。数据有梯度。

时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛


title: [蓝桥杯 2017 国 A] 填字母游戏

description:
小明经常玩 LOL 游戏上瘾，一次他想挑战 K 大师，不料 K 大师说：

“我们先来玩个空格填字母的游戏，要是你不能赢我，就再别玩 LOL 了”。

K 大师在纸上画了一行 $n$ 个格子，要小明和他交替往其中填入字母。

并且：

1. 轮到某人填的时候，只能在某个空格中填入 `L` 或 `O`。

2. 谁先让字母组成了 `LOL` 的字样，谁获胜。

3. 如果所有格子都填满了，仍无法组成 `LOL`，则平局。

小明试验了几次都输了，他很惭愧，希望你能用计算机帮他解开这个谜。

inputFormat:
本题的输入格式为：

第一行，数字 $n$（$n<10$），表示下面有 $n$ 个初始局面。

接下来，$n$ 行，每行一个串（长度 $<20)$，表示开始的局面。

比如：`******`，表示有 $6$ 个空格。

`L****`，表示左边是一个字母 $L$，它的右边是 $4$ 个空格。

outputFormat:
要求输出 $n$ 个数字，表示对每个局面，如果小明先填，当 K 大师总是用最强着法的时候，小明的最好结果。

`1` 表示能赢。

`-1` 表示必输。

`0` 表示可以逼平。

hint: 时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛


title: [蓝桥杯 2017 国 A] 数组操作

description:
给出一个长度为 $n$ 的数组 $\{A\}$，由 $1$ 到 $n$ 标号，你需要维护 $m$ 个操作。

操作分为三种，输入格式为：

`1 L R d`，将数组中下标 $L$ 到 $R$ 的位置都加上 $d$，即对于 $L \le i \le R$，执行 $A[i]\leftarrow A[i]+d$。

`2 L1 R1 L2 R2`，将数组中下标为 $L_1$ 到 $R_1$ 的位置，赋值成 $L_2$ 到 $R_2$ 的值，保证 $R_1-L_1=R_2-L_2$。

换句话说先对 $0 \le i \le R_2-L_2$ 执行 $B_i\leftarrow A_{L_2+i}$，再对 $0 \le i \le R_1-L_1$ 执行 $A_{L_1+i}\leftarrow B_i$，其中 $\{B\}$ 为一个临时数组。

`3 L R`，求数组中下标 $L$ 到 $R$ 的位置的和，即求出 $\sum\limits_{i=L}^{r}A_i$。

inputFormat:
从标准输入读入数据。

第一行一个整数 Case，表示测试点编号，其中 Case 为 $0$ 时表示该点为样例。

第二行包含两个整数 $n,m$。保证 $1 \le n,m \le 10^5$。

第三行包含 $n$ 个整数 $A_i$，表示这个数组的初值。保证 $0 \le A_i \le 10^5$。

接下来 $m$ 每行描述一个操作，格式如问题描述所示。

对于操作中提到每个数，满足 $0 \le d \le 10^5$，$1 \le L \le R \le n$，$1 \le L_1 \le R_1 \le n$，$1 \le L_2 \le R_2 \le n$，$R_1-L_1=R_2-L_2$。

outputFormat: 对于每次 3 操作输出一行一个数，表示求和的结果。


title: [蓝桥杯 2017 国 A] 区间移位

description:
数轴上有 $n$ 个闭区间：$D_1, \cdots ,D_n$。

其中区间 $D_i$ 用一对整数 $[a_i,b_i]$ 来描述，满足 $a_i<b_i$。

已知这些区间的长度之和至少有 $10000$。

所以，通过适当的移动这些区间，你总可以使得他们的“并”覆盖 $[0,10000]$ ——也就是说 $[0,10000]$ 这个区间内的每一个点都落于至少一个区间内。

你希望找一个移动方法，使得位移差最大的那个区间的位移量最小。

具体来说，假设你将 $D_i$ 移动到 $[a_i+c_i,b_i+c_i]$ 这个位置。你希望使得 $\max\limits_{i=1}^n\{|c_i|\}$ 最小。

inputFormat:
输入的第一行包含一个整数 $n$，表示区间的数量。

接下来有 $n$ 行，每行 $2$ 个整数 $a_i,b_i$，以一个空格分开，表示区间 $[a_i,b_i]$。

保证区间的长度之和至少是 $10000$。

outputFormat: 输出一个数字，表示答案。如果答案是整数，只输出整数部分。如果答案不是整数，输出时四舍五入保留一位小数。

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

样例 1：第一个区间往左移动 $10$；第二个区间往右移动 $20$。

样例 2：第 $2$ 个区间往右移 $0.5$；第 $3$ 个区间往左移 $0.5$ 即可。

**【数据范围】**

对于 $30\%$ 的评测用例，$1 \le n \le 10$；

对于 $100\%$ 的评测用例，$1 \le n \le 10000$，$0 \le a_i<b_i \le 10000$。


title: [蓝桥杯 2018 省 B] 日志统计

description:
小明维护着一个程序员论坛。现在他收集了一份“点赞”日志，日志共有 $N$ 行。其中每一行的格式是 `ts id`，表示在 $ts$ 时刻编号 $id$ 的帖子收到一个“赞”。

现在小明想统计有哪些帖子曾经是“热帖”。如果一个帖子曾在任意一个长度为 $D$ 的时间段内收到不少于 $K$ 个赞，小明就认为这个帖子曾是“热帖”。

具体来说，如果存在某个时刻 $T$ 满足该帖在 $[T,T+D)$ 这段时间内（注意是左闭右开区间）收到不少于 $K$ 个赞，该帖就曾是“热帖”。

给定日志，请你帮助小明统计出所有曾是“热帖”的帖子编号。

inputFormat:
第一行包含三个整数 $N$、$D$ 和 $K$。

以下 $N$ 行每行一条日志，包含两个整数 $ts$ 和 $id$。

outputFormat: 按从小到大的顺序输出热帖 $id$。每个 $id$ 一行。

hint:
对于 $50\%$ 的数据，$1 \le K \le N \le 1000$。

对于 $100\%$ 的数据，$1 \le K \le N \le 10^5$，$0 \le id, ts \le 10^5$。

时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛


title: [蓝桥杯 2018 省 AB] 全球变暖

description:
你有一张某海域 $N \times N$ 像素的照片，`.` 表示海洋、 `#` 表示陆地，如下所示：

```
.......
.##....
.##....
....##.
..####.
...###.
.......
```

其中 "上下左右" 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 $2$ 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。

例如上图中的海域未来会变成如下样子：

```
.......
.......
.......
.......
....#..
.......
.......
```

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

inputFormat:
第一行包含一个整数 $N$。$(1 \le N \le 1000)$。

以下 $N$ 行 $N$ 列代表一张海域照片。

照片保证第 $1$ 行、第 $1$ 列、第 $N$ 行、第 $N$ 列的像素都是海洋。

outputFormat: 一个整数表示答案。

hint: 时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛


title: [蓝桥杯 2018 省 A] 倍数问题

description: 众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 $n$ 个数，希望你从这 $n$ 个数中找到三个数，使得这三个数的和是 $K$ 的倍数，且这个和最大。数据保证一定有解。

inputFormat:
从标准输入读入数据。

第一行包括 $2$ 个正整数表示 $n$ 和 $K$。

第二行 $n$ 个正整数，代表给定的 $n$ 个数。

outputFormat: 输出一行一个整数代表所求的和。

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

选择 $2$、$3$、$4$。

**【数据约定】**

对于 $30\%$ 的数据，$n \le 100$。

对于 $60\%$ 的数据，$n \le 1000$。

对于另外 $20\%$ 的数据，$K \le 10$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le K \le 10^3$，给定的 $n$ 个数均不超过 $10^8$。

时限 1 秒，256M。蓝桥杯 2018 年第九届省赛。


title: [蓝桥杯 2018 省 A] 付账问题

description:
几个人一起出去吃饭是常有的事。但在结帐的时候，常常会出现一些争执。

现在有 $n$ 个人出去吃饭，他们总共消费了 $S$ 元。其中第 $i$ 个人带了 $a_i$ 元。幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？

为了公平起见，我们希望在总付钱量恰好为 $S$ 的前提下，最后每个人付的钱的标准差最小。这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 $1$ 分钱的整数倍。你需要输出最小的标准差是多少。

标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。形式化地说，设第 $i$ 个人付的钱为 $b_i$ 元，那么标准差为 $s=\sqrt{\frac{1}{n}\sum_{i=1}^n(b_i-\frac{1}{n}\sum_{i=1}^n b_i)}$

inputFormat:
第一行包含两个整数 $n$、$S$；

第二行包含 $n$ 个非负整数 $a_1,\cdots,a_n$。

outputFormat:
输出到标准输出。

输出最小的标准差，四舍五入保留 $4$ 位小数。

保证正确答案在加上或减去 $10^{-9}$ 后不会导致四舍五入的结果发生变化。

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

1. 每个人都出 2333/5 元，标准差为 0。

**【数据约定】**

对于 $10\%$ 的数据，所有 $a_i$ 相等；

对于 $30\%$ 的数据，所有非 $0$ 的 $a_i$ 相等；

对于 $60\%$ 的数据，$n \le 1000$；

对于 $80\%$ 的数据，$n \le 10^5$；

对于所有数据，$n \le 5 \times 10^5,0 \le a_i \le 10^9$。


title: [蓝桥杯 2018 国 AC] 约瑟夫环

description:
$n$ 个人的编号是 $1 \sim n$，如果他们依编号按顺时针排成一个圆圈，从编号是 $1$ 的人开始顺时针报数。

（报数是从 $1$ 报起）当报到 $k$ 的时候，这个人就退出游戏圈。下一个人重新从 $1$ 开始报数。

求最后剩下的人的编号。这就是著名的约瑟夫环问题。

本题目就是已知 $n$，$k$ 的情况下，求最后剩下的人的编号。

inputFormat: 题目的输入是一行，$2$ 个空格分开的整数 $n,k$。

outputFormat: 要求输出一个整数，表示最后剩下的人的编号。


title: [蓝桥杯 2018 国 C] 交换次数

description:
IT 产业人才需求节节攀升。业内巨头百度、阿里巴巴、腾讯（简称 BAT）在某海滩进行招聘活动。

招聘部门一字排开。由于是自由抢占席位，三大公司的席位随机交错在一起，形如：

`ABABTATT`，这使得应聘者十分别扭。

于是，管理部门要求招聘方进行必要的交换位置，使得每个集团的席位都挨在一起。即最后形如：

`BBAAATTT` 这样的形状，当然，也可能是：

`AAABBTTT` 等。

现在，假设每次只能交换 $2$ 个席位，并且知道现在的席位分布，

你的任务是计算：要使每个集团的招聘席位都挨在一起需要至少进行多少次交换动作。

inputFormat: 输入是一行 $n$ 个字符（只含有字母 `B`、`A` 或 `T`），表示现在的席位分布。

outputFormat: 输出是一个整数，表示至少交换次数。

hint:
输入字符串的长度 $n$ 不大于 $10^5$。

时限 1 秒, 256M。蓝桥杯 2018 年第九届国赛


title: [蓝桥杯 2018 国 C] 迷宫与陷阱

description:
小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由 $N \times N$ 个格子组成的二维迷宫。

小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。

每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。

迷宫中有些格子小明可以经过，我们用 `.` 表示；

有些格子是墙壁，小明不能经过，我们用 `#` 表示。

此外，有些格子上有陷阱，我们用 `X` 表示。除非小明处于无敌状态，否则不能经过。

有些格子上有无敌道具，我们用 `%` 表示。

当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续 $K$ 步。

之后如果再次到达该格子不会获得无敌状态了。

处于无敌状态时，可以经过有陷阱的格子，但是不会拆除 / 毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。

给定迷宫，请你计算小明最少经过几步可以离开迷宫。

inputFormat:
第一行包含两个整数 $N$ 和 $K$。$(1 \le N \le 1000，1 \le K \le 10)$。

以下 $N$ 行包含一个 $N\times N$ 的矩阵。

矩阵保证左上角和右下角是 `.`。

outputFormat: 一个整数表示答案。如果小明不能离开迷宫，输出 $-1$。

hint: 时限 3 秒, 256M。蓝桥杯 2018 年第九届国赛


title: [蓝桥杯 2018 国 B] 调手表

description:
小明买了块高端大气上档次的电子手表，他正准备调时间呢。

在 M78 星云，时间的计量单位和地球上不同，M78 星云的一个小时有 $n$ 分钟。

大家都知道，手表只有一个按钮可以把当前的数加一。在调分钟的时候，如果当前显示的数是 $0$，那么按一下按钮就会变成 $1$，再按一次变成 $2$。如果当前的数是 $n-1$，按一次后会变成 $0$。

作为强迫症患者，小明一定要把手表的时间调对。如果手表上的时间比当前时间多 $1$，则要按 $n-1$ 次加一按钮才能调回正确时间。

小明想，如果手表可以再添加一个按钮，表示把当前的数加 $k$ 该多好啊……

他想知道，如果有了这个 $+k$ 按钮，按照最优策略按键，从任意一个分钟数调到另外任意一个分钟数最多要按多少次。

注意，按 $+k$ 按钮时，如果加 $k$ 后数字超过 $n-1,$ 则会对 $n$ 取模。

比如，$n=10,k=6$ 的时候，假设当前时间是 $0$，连按 $2$ 次 $+k$ 按钮，则调为 $2$。

inputFormat: 一行两个整数 $n,k$，意义如题。

outputFormat: 一行一个整数。表示：按照最优策略按键，从一个时间调到另一个时间最多要按多少次。


title: [蓝桥杯 2018 国 B] 搭积木

description:
小明对搭积木非常感兴趣。他的积木都是同样大小的正立方体。

在搭积木时，小明选取 $m$ 块积木作为地基，将他们在桌子上一字排开，中间不留空隙，并称其为第 $0$ 层。

随后，小明可以在上面摆放第 $1$ 层，第 $2$ 层，……，最多摆放至第 $n$ 层。摆放积木必须遵循三条规则：

规则 $1$：每块积木必须紧挨着放置在某一块积木的正上方，与其下一层的积木对齐；

规则 $2$：同一层中的积木必须连续摆放，中间不能留有空隙；

规则 $3$：小明不喜欢的位置不能放置积木。

其中，小明不喜欢的位置都被标在了图纸上。图纸共有 $n$ 行，从下至上的每一行分别对应积木的第 $1$ 层至第 $n$ 层。每一行都有 $m$ 个字符，字符可能是 `.` 或 `X`，其中 `X` 表示这个位置是小明不喜欢的。

现在，小明想要知道，共有多少种放置积木的方案。他找到了参加蓝桥杯的你来帮他计算这个答案。

由于这个答案可能很大，你只需要回答这个答案对 $1000000007(10^9+7)$ 取模后的结果。

注意：地基上什么都不放，也算作是方案之一种。

inputFormat:
输入数据的第一行有两个正整数 $n$ 和 $m$，表示图纸的大小。

随后 $n$ 行，每行有 $m$ 个字符，用来描述图纸。每个字符只可能是 `.` 或 `X`。

outputFormat: 输出一个整数，表示答案对 $10^9+7$ 取模后的结果。

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

成功的摆放有（其中O表示放置积木）：

```
 1       2       3       4
..X     ..X     O.X     ..X
.X.     OX.     OX.     .XO
```

**【数据约定】**

对于 $10\%$ 的数据，$n=1$，$m \le 30$；

对于 $40\%$ 的数据，$n \le 10$，$m \le 30$；

对于 $100\%$ 的数据，$n \le 100$，$m \le 100$。

时限 1 秒, 256M。蓝桥杯 2018 年第九届国赛


title: [蓝桥杯 2018 国 A] 自描述序列

description:
小明在研究一个序列，叫 Golomb 自描述序列，不妨将其记作 ${G(n)}$。这个序列有 $2$ 个很有趣的性质：

1. 对于任意正整数 $n$，$n$ 在整个序列中恰好出现 $G(n)$ 次。

2. 这个序列是不下降的。

以下是 $G(n)$ 的前几项：

$n$|1|2|3|4|5|6|7|8|9|10|11|12|13
-|-|-|-|-|-|-|-|-|-|-|-|-|-
$G(n)$|1|2|2|3|3|4|4|4|5|5|5|6|6

给定一个整数 $n$，你能帮小明算出 $G(n)$ 的值吗？

inputFormat: 一个整数 $n$。

outputFormat: 输出一个整数，表示答案。


title: [蓝桥杯 2018 国 A] 采油

description:
LQ 公司是世界著名的石油公司，为世界供应优质石油。

最近，LQ 公司又在森林里发现了一大片区域的油田，可以在这个油田中开采 $n$ 个油井。

LQ 公司在这 $n$ 个油井之间修建了 $n-1$ 条道路，每条道路连接两个油井，路径中间不会路过任何油井，而且这些道路将所有油井连通。

建立油井的时候需要使用一台大型设备，运输起来非常麻烦，LQ 公司准备在其中的一个油井位置建立一个空运站，先将设备空运到空运站，之后每次经过他们建立的道路来运输这个大型设备以建立不同的油井，当油井建立完毕后再从空运站将大型设备运走。

为了减少运输的麻烦，公司要求大型设备在道路上运输的总路程是最短的。

在建立油井和采油的过程中需要花费一些人力，第 $i$ 个油井需要花费 $B_i$ 个人，而一旦油井建成，就需要 $S_i$ 个人一直坚守在油井上进行维护。

当然，如果一个人参与了油井的建设，他可以直接留下来维护油井，或者参与下一个油井的建设，但是在维护油井的人不能再参加后续油井的建设了。

现在 LQ 公司想知道，大型设备运输的总路径长度最短是多少？在保证总路径长度最短的情况下，LQ 公司至少需要花费多少人力才能完成所有油井的建立与维护。

inputFormat:
输入的第一行包含一个整数 $n$，表示油井的数量。油井由 $1$ 到 $n$ 依次标号。

第二行包含 $n$ 个整数，依次表示 $B_1,B_2,\cdots,B_n$，相邻的整数之间用一个空格分隔。

第三行包含 $n$ 个整数，依次表示 $S_1,S_2,\cdots,S_n$，相邻的整数之间用一个空格分隔。

接下来 $n-1$ 行描述油井之间的道路，其中的第 $i$ 行包含两个整数 $a$，$b$，用一个空格分隔，表示一条道路的起点为 $i+1$ 、终点为 $a$，长度为 $b$，道路是双向的，设备可以从任意一端运送到另一端，每条道路都可以经过任意多次。数据保证任意两个油井之间都可以通过道路连接。

outputFormat: 输出包含两个整数，用一个空格分隔，表示最优情况下大型设备需要运输的总路程，以及在总路程最短的情况下最少需要花费的人力数量。

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

有两种方案达到最优。

方案一：在油井 $2$ 建立空运站，先建立油井 $2$，再将大型设备运输到油井 $1$ 建立油井 $1$，最后将大型设备运回油井 $2$。

方案二：在油井 $1$ 建立空运站，先将大型设备运输到油井 $2$ 建立油井 $2$，再将大型设备运送到油井 $1$ 建立油井 $1$。

**【数据范围】**

对于 $20\%$ 的数据：$n$ 不超过 $10$；

另外 $20\%$ 的数据：每个油井最多和两个油井之间有道路直接连接；

另外 $10\%$ 的数据：有 $n-1$ 个油井只有一条道路与其他油井连接；

对于 $100\%$ 的数据：$1\le n\le10^5$，$B$、$S$、$c$ 均为不超过 $10000$ 的正整数。

时限 1 秒, 256M。蓝桥杯 2018 年第九届国赛


title: 最大公约数

background:
  “寻求最大公约数是人民民主的真谛。……”

  初秋，从枝丫滴下的阳光，柔和，在教室的窗棱溅起，润湿晨读的少女的脸颊。

  “阿绫，阿绫”，天依低俯身子，八字辫耷拉在竖起的课本沿，“我们的最大公约数是多少呢？”

  “一定不小吧”，左手悄悄捏捏天依的小臂，“比如呀，有一个公因子，叫做‘你喜欢我，我也喜欢你’。”

description:
相反，人际圈形形色色，公约数小得可怜，似乎很难保持自己的个性因而变成无趣的人呢。

现在把人际抽象成一个 $n \times m$ 的矩形，每个人初始的个性为 $a_{i,j}$。从第二天开始，每个人会与上下左右四个人（如果存在）建立人际关系，其个性变为昨天自己和四周人个性的最大公约数。那么对于第 $x$ 行第 $y$ 列的人，在多少天后他的个性会变为 $1$ 呢？

----

#### 简化题意

有一个 $n \times m$ 的矩阵 $a$。对一个矩阵进行变换，定义为将这个矩阵内的所有元素变为其上下左右四个元素（不存在则忽略）及自身的最大公约数。询问 $a_{x,y}$ 在进行最少多少次变换之后会变成 $1$。如果可以使 $a_{x,y}$ 经过若干次变换变成 $1$，输出其中最小的次数；否则输出 $-1$。

inputFormat:
第一行两个整数 $n,m$，表示矩阵的行数和列数。

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数 $a_{i,j}$ 描述了该位置的人的初始个性。

接下来一行两个整数 $x,y$，表示某个指定的人的位置。

outputFormat: 一行一个整数 $d$，表示第 $x$ 行第 $y$ 列的人的个性会在 $d$ 天后变为 $1$；**特别地**，若永远不会变为 $1$，应输出 $-1$。


title: 手势密码

background:
  众目睽睽之下被要求解锁另一个人的手机是一件非常恐怖的事。

  ——特别是密码关于自己的时候。

---

  被堆在讲台周围乌压压的同学围着，小灰毛表示自己真的很难。作为班长的阿绫被叫去开会，存着月考名次表的手机被交给天依保管。但消息不出意料地走漏，现在一班觊觎着分数数据的饿狼一致要求天依打开手机……

  “真不知道密码啊！”拖延着，心里早就猜到手势密码的答案。

  最后，试探而肯定地划出一个字母“Y”，解锁成功。什么意思呢？首先排除“依”的首字母。

  这个时候肯定有起哄的啦！

  “懂的都懂\~”“别问，问就是 [XX即是正义！](https://www.bilibili.com/video/BV1z741137vQ)”……

description:
乐正大小姐用的手机很高级，所以她的手势密码也很花哨。

具体地，现在有一棵 $n$ 个结点的树，对于两个结点 $u,v$，当且仅当 $(u,v)$ 是一条树边时，手势才能从其中一个点（$u$ 或 $v$）划向另一个点（$v$ 或 $u$）。更奇怪的是，这种手势密码不限制仅划一次，但每次划出的路径必须是树上的一条简单路径。

现在阿绫告诉了天依在她的密码中每个结点被手势划过的次数（作为手势的起点或终点也算划过一次），其中第 $i$ 个结点划过 $a_i$ 次。那么，天依至少要划多少次才能解开密码呢？

----

#### 简化题意

有一棵带点权的树。定义一次操作为选择树上的一条简单路径，并将这条简单路径上的所有点点权减去 $1$。问至少需要多少次操作，使树上所有点的点权**恰好**变为 $0$。

inputFormat:
第一行一个整数 $op$，表示数据输入方式类型。

如果 $op=1$：

第二行一个正整数 $n$，表示结点个数。

第三行 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$，表示每个结点的点权。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示一条连接结点 $u$ 和结点 $v$ 的树边。

如果 $op=2$：

我们将给出一个输入的模板：
```cpp
#include <cstdio>
int a[3000005], u[3000005],v[3000005];
namespace Generate{
	int n,seed;
	static const int mod=1e9;
	int Rand(int x){
		seed=(1ll*seed*0x66CCF+19260817ll)%x+1;
		seed=(1ll*seed*0x77CCF+20060428ll)%x+1;
		seed=(1ll*seed*0x88CCF+12345678ll)%x+1;
		seed=(1ll*seed*0x33CCCCFF+10086001ll)%x+1;
		return seed;
	}
	void RS(int* a, int* u, int* v){ //你需要传入三个参数，分别表示点权，一条边的两个端点
		int cnt=0;
		for(int i=1;i<=n;i++)a[i]=Rand(mod);
		for(int i=2;i<=n;i++){
			int fa=Rand(i-1);
			cnt++;
			u[cnt]=fa,v[cnt]=i;
		}
	}
};
int main () {
	int op;
	scanf("%d",&op);
	if(op==1){
		//直接输入
	}else{
		int n;
		scanf("%d %d",&Generate::seed,&n);//输入种子和n
		Generate::n=n;//记得赋值
		Generate::RS(a,u,v); //开始工作
	}
	return 0;
}
```

第二行两个整数 $seed$ 和 $n$，表示生成器的种子与结点个数。

outputFormat: 一行一个整数，表示最少的操作次数。


title: 「EZEC-6」分组

description: 给你 $n$ 个数，将它们分成任意组（可以不连续），将每个组内的数按位或，并将各组的结果累加，在保证其结果最小的情况下求最多分成的组数。

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

第二行输入 $n$ 个非负整数 $a_i$。

outputFormat: 一个正整数，最优解中最多分成的组数。


title: [BalticOI 2015] File Paths

description:
一个文件 $\tt file$ 都需要在一个包含很多文件 $\tt dir1,dir2,\cdots,dirj$ 的目录中，这个文件的 absolute file path 为 $\tt/dir1/dir2/\cdots/dirj/file$，根目录用 $\tt /$ 表示，每一个放在根目录下的文件的 absolute file path 的形式为 $\tt /file$。

符号链接指向一个已被命名的目录，可以看作一个快捷方式，他可以放置在任意目录下，注意，符号链接不能指向文件。比如，我们在 $\tt /$ 下放一个指向 $\tt /$ 的符号链接 $\tt hello$，那么，$\tt /dir/file$，$\tt /hello/dir/file$，$\tt /hello/hello/dir/dile$ 都指向同一个文件 $\tt file$。另比如，我们在 $\tt /dir$ 下放一个指向 $\tt /$ 的符号链接 $\tt hi$，那么，$\tt /dir/file$，$\tt /dir/hi/dir/file$，$\tt /dir/hi/dir/hi/dir/file$ 都指向同一个文件 $\tt file$。符号链接指向上一层，下一层，甚至同层都可以，但是不允许 $\tt ./$，$\tt ../$，$\tt //$ 之类的操作。

现在想问，是否能通过引入一个长为 $s$ 的符号链接使得找到一个文件的 absolute file path 长度恰好为 $k$？

inputFormat:
第一行三个整数 $n,m,k$ 代表除根目录之外的目录数，文件数和要求等于的路径长度。
第二行一个整数 $s$ 代表符号链接长。
接下来 $n$ 行每行两个整数 $p_i,l_i$ 描述一个目录，这个目录编号为 $l_i$，父目录编号为 $p_i$。
接下来 $m$ 行每行两个整数 $p_j,l_j$，描述一个文件，这个文件的长度为 $l_j$，父目录编号为 $p_j$。

outputFormat: $m$ 行每行一个字符串代表是否能通过引入一个长为 $s$ 的符号链接使得找到编号为 $j$ 的文件的 absolute file path 长度恰好为 $k$，如果是的话输出 $\tt YES$，否则输出 $\tt NO$。

hint:
#### 样例 1 解释

假设符号链接名字为 $\tt LL$，目录名字为 $\tt a$，$\tt bbbbb$，文件名字为 $\tt ccccccccccccc$，$\tt dddddddddd$，$\tt eee$，$\tt fffffff$，根目录下包含目录 $\tt a$ 和文件 $\tt fffffff$，目录 $\tt a$ 下包含目录 $\tt bbbbb$ 和文件 $\tt eee$，目录 $\tt bbbbb$ 包含文件 $\tt ccccccccccccc$ 和 $\tt dddddddddd$。下面是形象化的表述：

```plain
/
|-- a
| |-- bbbbb
| | |-- ccccccccccccc
| | +-- dddddddddd
| +-- eeee
+-- fffffff
```

- 对于第 $1$ 个文件，满足条件的路径为 $\tt /a/bbbbb/ccccccccccccc$。
- 对于第 $2$ 个文件，满足条件的路径为 $\tt /a/LL/bbbbb/dddddddddd$。
- 对于第 $3$ 个文件，满足条件的路径为 $\tt /a/LL/a/LL/a/LL/a/eeee$。
- 对于第 $4$ 个文件，无满足条件的路径。

#### 数据规模与约定

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

- Subtask 1（33 pts）：$n,m \le 500$。
- Subtask 2（33 pts）：$n,m \le 3 \times 10^3$，符号链接最多被调用一次。
- Subtask 3（34 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le k,s \le 10^6$，$1\le m,n\le 3\times 10^3$。

#### 说明

翻译自 [BalticOI 2015 Day2 A File Paths](https://boi.cses.fi/files/boi2015_day2.pdf)。


title: 任意模数 Chirp Z-Transform

description: 给定一个 $n$ 项多项式 $P(x)$ 以及 $c, m$，请计算 $P(c^0),P(c^1),\dots,P(c^{m-1})$。所有答案都对 $10^9+7$ 取模。

inputFormat:
第一行三个正整数 $n,c,m$。
第二行 $n$ 个非负整数 $a_0,a_1,\dots,a_{n-1}$，由低到高表示 $P(x)$ 的系数。

outputFormat: 一行 $m$ 个正整数，第 $i$ 个数表示 $P(c^{i-1})$。


title: 象棋与马

background:
Amazing John 做了一个梦，梦到他下辈子是个象棋大师。

因为人与人之间是不能一概而论的，马与象之间也不能相提并论。

Amazing John 在极度愤怒的情况下创造了一种新的棋：马棋。

“啊这，不会真有人不会下这种棋吧？”

现在他想请你来体验一下这种新棋。

description:
Amazing John 有一个无限大的棋盘来下马棋。

有一个马最开始在 $(0,0)$，它的每一步可以走一个 $a\times b$ 的矩形（ 即能够从$(x,y)$到达 $(x\pm a,y\pm b)$ 或 $(x\pm b,y\pm a)$ ）。

若马通过上述移动方式可以到达棋盘中任意一个点，那么 $p(a,b)=1$，否则 $p(a,b)=0$。

现在 Amazing John 给你 $T$ 组询问，每组询问他会给出一个正整数 $n$，他想知道

$$\left ( \sum_{a=1}^n\sum_{b=1}^np(a,b) \right )\bmod\ 2^{64}$$

的值。

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

输入的第一行为一个整数，表示数据组数 $T$。

接下来 $T$ 行，每行一个整数 $n$，表示一个询问。

outputFormat:
输出共 $T$ 行。

对于每组询问，输出一行一个整数，即
$$\left ( \sum_{a=1}^n\sum_{b=1}^np(a,b) \right )\bmod\ 2^{64}$$
的值。


title: 「PMOI-4」人赢

background:
众所周知，ducati 是人 win。

现在 lhm 也想成为人 win，于是 ducati 扔给了 lhm 下面这道题，并且 ducati 承诺在 lhm 完成此题后教他如何成为人 win。

description:
现在 lhm 手中有一个无穷长的衔尾数列 $a$，它满足：

- 对于数列中的每一个 $a_i(i>2)$，它总为 $a_{i-2} \times a_{i-1}$ 的**个位数**。

ducati 将给 lhm 衔尾数列的前两位 $a_1=n,a_2=m$ 与位置 $k$，它的任务是算出 $a_k$。

由于 lhm 太菜了并不会这道题，但他仍然想成为人 win，所以他只好请聪明的你来帮他完成这个问题。

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

outputFormat: 一行一个整数，表示数列中位置 $k$ 的数字。

hint:
【样例解释 $1$】

数列 $1$ 至 $10$ 位依次为：$1,6,6,6,6,6,6,6,6,\color{red}{6}$。所以答案为 $6$。

【样例解释 $2$】

数列 $1$ 至 $7$ 位依次为：$7,2,4,8,2,6,\color{red}{2}$。所以答案为 $2$。

【数据范围】

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

- Subtask 1（30pts）：$1 \leq k \leq 10^6$。
- Subtask 2（70pts）：无特殊限制。

对于 $100\%$ 的数据，$0 \leq n,m \leq 9$，$1 \leq k \leq 10^{12}$。


title: 深海少女与胖头鱼

background:
Amazing John 做了一个梦，梦到他上上辈子是个少女。

她跳入了 OI ~~炉石~~ 的海洋，成为了[深海少女](https://music.163.com/#/song?id=22677451)，维护着海洋的秩序。

某一天，海洋遭到了胖头鱼群的入侵。为了维护深海的安全，Amazing John 带着大佬们与胖头鱼们战斗了 $9$ 天 $9$ 夜，但是鱼的数量并没减少。

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

description:
经过漫长的战斗，Amazing John 发现了战胜胖头鱼的方法：

总共有 $n$ 条带 「圣盾」的「胖头鱼」和 $m$ 条不带圣盾的胖头鱼，每次等概率对一条存活的胖头鱼造成「剧毒」伤害。

现在 Amazing John 想知道，期望造成多少次伤害可以杀死全部胖头鱼？

答案对 $998244353$ 取模。

「圣盾」：当拥有圣盾的胖头鱼受到伤害时，免疫这条鱼所受到的本次伤害。免疫伤害后，圣盾被破坏。

「胖头鱼」：在一条胖头鱼的圣盾被破坏后，给予其他所有没有死亡且没有圣盾的胖头鱼圣盾。

「剧毒」：立即杀死没有圣盾的胖头鱼。

inputFormat: 输入共一行，包含两个非负整数 $n,m$，表示有 $n$ 条带圣盾的胖头鱼，有 $m$ 条不带圣盾的胖头鱼。

outputFormat:
输出共一行，一个非负整数 $s$，表示期望造成伤害次数对 $998244353$ 取模的值。

具体的，答案必然可以表示成 $\frac{p}{q}(p,q\in \mathbb{N},q\neq 0)$ 的形式，而你需要输出 $p×q^{-1}$ 在模 $998244353$ 意义下的值。


title: 梦中梦与不再有梦

background:
Amazing John 做了一个梦，梦到他做了很多梦。

记得最好的梦，是不再有梦。

description:
Amazing John 想要以自己的梦出一道题。

Amazing John 做了 $n$ 个梦。每两个梦之间都有且仅有一条桥梁直接相连，不会有桥梁从一个梦连向自身。

通过桥梁 $e_{u,v}$ 可以从梦 $u$ 到达 梦 $v$ 或从 $v$ 到达 $u$ ，并且获得 $1$ 点休息值。

对于每个桥梁 $e_{u,v}$ ，它只能被经过一次，无论是正向经过还是反向经过。

当到达一个梦且与它相连的所有桥梁都不能经过时， Amazing John 就会结束他的做梦。

现在 Amazing John 很困，他想知道从任意一个梦出发，最多可以获得多少休息值？

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

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

接下来有 $T$ 行，每行包含一个正整数 $n$ ，表示他做了 $n$ 个梦。

outputFormat:
输出共 $T$ 行。

对于每组数据，输出一行一个正整数 $ans$ ，表示最多可以获得的休息值。


title: 「EZEC-4.5」子序列

background:
作为唯一一道有背景的题，此题由出题人基于 @[Ecrade_](https://www.luogu.com.cn/user/322075) 的原创题“子集”拓展而来。

“子集”便是本题中 $k=n-1$ 的情况。

description:
给定一个有 $n$ 个元素的序列 $a$。

定义一个有 $x$ 个元素的序列 $s$ 的值为：
$$\sum \limits _{i=1} ^ x s_i \times \prod \limits _{i=1} ^ x s_i $$

将序列 $a$ 的一个有 $x$ 个元素的子序列表示为 $s = \{a_{p_1},a_{p_2},...,a_{p_x}\}$，其中 $p$ 为严格单调递增的序列，$1 \le p_1 \le p_x \le n$ 。

给定整数 $k$，定义序列 $a$ 的一个有 $x$ 个元素的合法的子序列 $s$ 需满足 $p_x - p_1 \le k$。

求序列 $a$ 的所有合法子序列的值之和对 $mod$ 取模的值。

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

第二行 $n$ 个整数，$a_i$。

outputFormat: 一行一个整数表示答案对 $mod$ 取模的值。


title: [IOI2020] 植物比较

background:
**这是一道交互题**。

本题仅支持 C++ 系列语言，提交时不需要包含 `plant.h` 头文件。

description:
植物学家 Hazel 参观过新加坡植物园的一个特别展览。在这次展览中，有 $n$ 棵 **高度互不相同** 的植物，它们排成了一个圆。这些植物按顺时针方向从 $0$ 到 $n-1$ 编号，植物 $n-1 $ 与植物 $0$ 是相邻的。

对于每棵植物 $i\ (0 \le i \le n-1$)，Hazel 将它与顺时针方向的后 $k-1$ 棵植物进行比较，记录下数值 $r[i]$ 以表示这 $k-1$ 棵植物中有多少棵的高度大于植物 $i$。因此，每个 $r[i]$ 的数值是由某段连续 $k$ 棵植物的相对高度决定的。

例如，假设 $n=5$，$k=3$，$i=3$。植物 $3$ 顺时针方向的后 $k-1=2$ 棵植物是植物 $4$ 和植物 $0$。如果植物 $4$ 比植物 $3$ 高，且植物 $0$ 比植物 $3$ 矮，那么 Hazel 将会记录 $r[3]=1$。

你可以假设 Hazel 记录的数值 $r[i]$ 都是正确的。也就是说，这些植物至少存在一组互不相同的高度符合 Hazel 所记录的数值。

本题要求你比较 $q$ 对植物的高度。由于你没有机会参观这次展览，你仅有的信息来源是 Hazel 的笔记本，其中记录了 $k$ 和序列 $r[0],\ldots, r[n-1]$ 的值。

对于每对需要比较的植物 $x$ 和 $y$（$x$ 和 $y$ 不同），判定它们符合以下哪种情况：

- 植物 $x$ 一定比植物 $y$ 高：对于任意一组符合数组 $r$ 且互不相同的高度 $h[0],\ldots h[n-1]$，都有 $h[x] > h[y]$。
- 植物 $x$ 一定比植物 $y$ 矮：对于任意一组符合数组 $r$ 且互不相同的高度 $h[0],\ldots h[n-1]$，都有 $h[x]<h[y]$。
- 该比较没有定论：以上两种情况都不成立。

#### 实现细节

要求你实现以下函数：
```cpp
void init(int k, std::vector<int> r)
```
- $k$：决定每个 $r[i]$ 数值的连续植物的棵数。
- $r$：一个大小为 $n$ 的数组，其中 $r[i]$ 是植物 $i$ 顺时针方向的后 $k-1$ 棵植物中比它高的棵数。
- 该函数恰好被调用一次，且在对 `compare_plants` 的任何调用前。
```cpp
int compare_plants(int x, int y)
```
- $x,y$ ：待比较的植物的编号。
- 该函数应该返回：
	- $1$，如果植物 $x$ 一定比植物 $y$ 高，
	- $-1$，如果植物 $x$ 一定比植物 $y$ 矮，
	- $0$，如果该比较没有定论。
- 该函数恰好被调用 $q$ 次。

hint:
#### 样例说明

#### 例 1

考虑以下调用：
```cpp
init(3, [0, 1, 1, 2])
```
假设评测程序调用了 `compare_plants(0, 2)`。由 $r[0]=0$ 可以推断植物 $2$ 不比植物 $0$ 高，因此该调用应该返回 $1$。

假设评测程序接下来调用了 `compare_plants(1, 2)`。由于对每组符合以上条件的植物高度，都有植物 $1$ 比物 $2$ 矮，因此该调用应该返回 $-1$。

#### 例 2

考虑以下调用：
```cpp
init(2, [0, 1, 0, 1])
```
假设评测程序调用了 `compare_plants(0, 3)`。由 $r[3]=1$ 可以推断植物 $0$ 比植物 $3$ 高，因此该调用应该返回 $1$。

假设评测程序接下来调用了 `compare_plants(1, 3)`。两组高度 $[3,1,4,2]$ 和 $[3,2,4,1]$ 都符合 Hazel 的观测记录，由于在第一种情况中植物 $1$ 比植物 $3$ 矮，而在第二种情况中它比植物 $3$ 高，因此该调用应该返回 $0$。

#### 约束条件

- $2\le k\le n\le 200\ 000$
- $1\le q\le 200\ 000$
- $0 \le r[i]\le k-1$（对所有 $0 \le i \le n-1$）
- $0\le x<y\le n-1$
- 存在一组或多组 **互不相同的高度** 符合数组 $r$ 记录的情况

#### 子任务

1. （5 分）$k=2$
2. （14 分）$n \le 5000,2 \cdot k > n$
3. （13 分）$2 \cdot k > n$
4. （17 分）每次 `compare_plants` 调用的正确答案是 $1$ 或 $-1$
5. （11 分）$n\le 300, q\le \frac{n\cdot (n-1)}{2}$
6. （15 分）每次调用 `compare_plants` 时有 $x=0$
7. （25 分）没有附加约束条件

#### 评测程序示例

评测程序示例以如下格式读取输⼊数据：

第 $1$ 行：$n\ k\ q$
第 $2$ 行：$r[0]\ r[1]\ \cdots\ r[n-1]$
第 $3+i\ (0\le i\le q-1)$ 行：$x\ y$，表⽰第 $i$ 次调用 `compare_plants` 时的参数

评测程序示例以如下格式打印你的答案：

第 $1+i\ (0\le i\le q-1)$ 行：第 $i$ 次调用 `compare_plants` 的返回值


title: [IOI2020] 连接擎天树

background:
**这是一道交互题。**

本题仅支持 C++ 系列语言，提交时**不需要**包含 `supertrees.h` 头文件，但**需要**在程序开头包含 `vector` 头文件以及声明函数 `void build(std::vector<std::vector<int> > b);`

description:
滨海湾花园是新加坡的一个大型自然公园。公园内有 $n$ 个塔，称之为“擎天树”。这些塔的编号为 $0$ 到 $n-1$。我们希望建立一个桥的集合（桥的数目大于等于 $0$）。每⼀座桥连接两个不同的塔，而且可以双向通行。没有两座桥连接相同的一对塔。

一条从塔 $x$ 到塔 $y$ 的路径是一个满足以下条件的塔序列（塔的数目大于等于 $1$）：

- 序列的第一个元素是 $x$，
- 序列的最后一个元素是 $y$，
- 序列中所有元素互不相同，

序列中每两个相邻元素（塔）都是被某一座桥连接起来的。

注意根据定义，一个塔到它自己有且仅有一条路径，并且从塔 $i$ 到塔 $j$ 的不同路径的数目和从塔 $j$ 到塔 $i$ 的不同路径的数目是一样的。

负责该项设计的首席设计师希望待建造的桥梁要符合：任意给定 $0 \le i,j \le n-1$，恰好有 $p[i][j]$ 条从塔 $i$ 到塔 $j$ 的不同路径，其中 $0 \le p[i][j] \le 3$。

请构造一个桥的集合来满足设计师的要求，或判定这样的桥梁集合不可能存在。

#### 实现细节

你需要实现下面的这个函数：

```cpp
int construct(std::vector<std::vector<int> > p)
```

- $p$：⼀个表示设计师要求的 $n \times n$ 数组。
- 如果这个建设方案是存在的，该函数应该恰好调用一次 `build`（见下文）来给出建设方案，然后应返回 $1$。
- 否则，该函数应该返回 $0$，并且不要调用 `build`。
- 该函数将被调用恰好一次。

函数 `build` 定义如下：

```cpp
void build(std::vector<std::vector<int> > b)
```

- $b$：一个 $n \times n$ 的数组，$b[i][j]=1$ 表示有一座桥连接塔 $i$ 和塔 $j$，否则 $b[i][j]=0$。
- 注意该数组必须满足：对所有 $0 \le i,j \le n-1$，$b[i][j]=b[j][i]$；并且对所有 $0 \le i \le n-1$，$b[i][i]=0$。

hint:
#### 样例说明

#### 例 1

考虑以下调用：

```cpp
construct([[1, 1, 2, 2], [1, 1, 2, 2], [2, 2, 1, 2], [2, 2, 2, 1]])
```

这表明从塔 $0$ 到塔 $1$ 恰好有一条路径。对于所有其他的塔对 $(x,y)(0 \le x<y \le 3)$, 恰好有两条不同的路径连接塔 $x$ 和塔 $y$。这可以通过建设 $4$ 座桥来实现：连接塔对 $(0, 1), (1, 2), (1, 3)$ 和 $(2,3)$。

为了给出这个解决方案，函数 `construct` 应该做以下调用：

```cpp
build([[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]])
  ```

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

函数应该返回 $1$。

对于这个例子，存在多种不同的建设方案来满足要求，所有这些方案都被认为是正确的。

#### 例 2

考虑以下调用：

```cpp
construct([[1, 0], [0, 1]])
```

  这表明无法在两个塔之间进行旅行。这只能通过不建设桥梁来满足。

因此，函数 `construct` 应该做以下调用：
```cpp
build([[0, 0], [0, 0]])
```
  然后，函数 `construct` 应该返回 $1$。

  #### 例 3

考虑以下调用：

```cpp
construct([[1, 3], [3, 1]])
```

这表明从塔 $0$ 到塔 $1$ 恰好有 $3$ 条路径。这些要求无法满足。因此，函数 `construct` 应该返回 $0$ 并且不要调用 `build`。

#### 约束条件

- $1\le n\le 1000$
- $p[i][i]=1$（对所有 $0 \le i \le n-1$）
- $p[i][j]=p[j][i]$（对所有 $0 \le i,j \le n-1$）
- $0 \le p[i][j] \le 3$（对所有 $0 \le i,j \le n-1$）

#### 子任务

1. （11 分）$p[i][j]=1$（对所有 $0 \le i,j \le n-1$）
2. （10 分）$p[i][j] \in \{0,1\}$（对所有 $0 \le i,j \le n-1$）
1. （19 分）$p[i][j] \in \{0,2\}$（对所有 $i \ne j,0 \le i,j \le n-1$）
1. （35 分）$0 \le p[i][j]\le 2$（对所有 $0 \le i,j \le n-1$）并且至少有一种建设方案满足要求
1. （21 分）$0 \le p[i][j] \le 2$（对所有 $0 \le i,j \le n-1$）
1. （4 分）没有额外约束条件

#### 评测程序示例

评测程序示例以如下格式读取输入数据：

第 $1$ 行：$n$
第 $2+i$ 行（$0 \le i \le n+1$）：$p[i][0]\ p[i][1]\ \ldots\ p[i][n]$

评测程序示例的输出格式如下：

第 $1$ 行: `construct` 的返回值。

如果 `construct` 的返回值为 $1$，评测程序示例会额外打印：

第 $2+i$ 行（$0 \le i \le n+1$）：$b[i][0]\ b[i][1]\ \ldots\ b[i][n]$


title: [IOI2020] 嘉年华奖券

background:
**本题为交互题。**

请在程序开头声明 `void allocate_tickets(std::vector<std::vector<int> > s);` 和使用 vector 头文件，并且请在调用函数前加上 `extern "C"`。

description:
Ringo 正在参加在新加坡举办的一个嘉年华活动。他的口袋里装有一些奖券，这些奖券可以在嘉年华的游戏展位使用。假设共有 $n$ 种颜色的奖券，每张奖券涂上了其中的一种颜色并且印上了一个非负整数。不同奖券上的数字可能相同。依据嘉年华活动的规则要求，$n$ 保证是偶数。

Ringo 每种颜色的奖券有 $m$ 张，也就是说他共有 $n \cdot m$ 张奖券。其中，第 $i$ 种颜色对应的第 $j$ 张奖券上印的数字为 $x[i][j]$（$0 \le i \le n-1$ 且 $0 \le j \le m-1$）。

一次奖券游戏要进行 $k$ 轮，轮次的序号从 $0$ 到 $k-1$。每一轮按照下面的方式进行：

- 首先，Ringo 从每种颜色的奖券中各选出一张奖券，形成一个 $n$ 张奖券的 **集合**。
- 随后，游戏负责人记录下这个集合中奖券上的数字 $a[0],a[1],\ldots,a[n-1]$。不需要考虑这 $n$ 个整数的顺序。
- 接下来，游戏负责人从一个幸运抽奖箱中抽取一张特殊卡片，上面印有整数 $b$。
- 对于上述集合中每一个奖券上的数字 $a[i](0\le i \le n-1)$，游戏负责人会计算 $a[i]$ 和 $b$ 的差的绝对值。让 $S$ 代表这 $n$ 个差的绝对值之和。
- 所得到的数字 $S$ 就是 Ringo 本轮能够获得的奖励数额。
- 一轮游戏结束后，本轮集合中的奖券全部被丢弃，不会在未来的轮次所使用。

当 $k$ 轮游戏结束后，Ringo 会丢弃口袋中的所有奖券。

通过仔细观察，Ringo 发现这个奖券游戏被操控了！实际上，幸运抽奖箱里面内置了一台打印机。在每一轮，游戏负责人首先找到一个能够最小化当前轮次游戏奖励的整数 $b$，然后将该数字打印在他所抽取的特殊卡片上。

知道了这些信息之后，Ringo 想要设计每轮游戏中的奖券分配方案，使得 $k$ 轮游戏中获得的总体奖励数额之和最大。

#### 实现细节

你需要实现下面这个函数：

```cpp
long long find_maximum(int k,std::vector<std::vector<int>> x)
```

- $k$：游戏的轮数。
- $x$：一个 $n \times m$ 的数组，记录了奖券上的数字。每种颜色的奖券按照上面的数字非递减顺序排序。
- 这个函数只会被调用一次。
- 这个函数应该只调用一次函数 `allocate_tickets`（参见下面的内容），它描述了 $k$ 轮游戏中的奖券分配方案，每一轮对应一个奖券集合。奖券的分配方案应该使得所获奖励数额之和达到最大。
- 这个函数需要返回能够获得的最大的奖励数额之和。

函数 `allocate_tickets` 按照如下的方式进行定义：

```cpp
void allocate_tickets(std::vector<std::vector<int>> s)
```

- $s$：一个 $n \times m$ 的数组。如果第 $i$ 种颜色的第 $j$ 张奖券如果被分配到了第 $r$ 轮游戏，那么 $s[i][j]$ 的值应该为 $r$；如果未被使用，应该为 $-1$。
- 对于 $0 \le i \le n-1$，在 $s[i][0],s[i][1],\ldots,s[i][m-1]$ 中，每个值 $0,1,\ldots,k-1$ 必须只出现一次，而其他元素应该为 $-1$。
- 如果存在多种奖券分配方案能够达到最优的奖励数值，可以给出其中任何一种最优方案。

hint:
#### 样例说明

#### 例 1

考虑下面的函数调用：

```cpp
find_maximum(2, [[0, 2, 5],[1, 1, 3]])
  ```
这意味着：

- 游戏共进行 $k=2$ 轮；
- 第 $0$ 种颜色奖券上的整数数字分别是 $0,2$ 和 $5$；
- 第 $1$ 种颜色奖券上的整数数字分别是 $1,1$ 和 $3$；

一种能够获得最优奖励数值的分配方案是：

- 在第 $0$ 轮，Ringo 选择第 $0$ 种颜色的第 $0$ 张奖券（印有整数 $0$）和第 $1$ 种颜色的第 $2$ 张奖券（印有整数 $3$）。本轮获得的最小奖励数额是 $3$。例如，游戏负责人可以选择 $b=1$：$|1-0| + |1-3| = 1+2 = 3$。
- 在第 $1$ 轮，Ringo 选择第 $0$ 种颜色的第 $2$ 张奖券（印有整数 $5$）和第 $1$ 种颜色的第 $1$ 张奖券（印有整数 $1$）。本轮能够获得的最小奖励是 $4$。例如，游戏负责人可以选择 $b=3$：$|3-1|+|3-5|=2+2=4$。
- 因此，本次游戏两轮的奖励之和为 $3+4=7$。

为了给出这个分配方案，函数 `find_maximum` 应该按照如下方式调用 `allocate_tickets`：

```cpp
allocate_tickets([[0, -1, 1], [-1, 1, 0]])
```

  最终，函数 `find_maximum` 应该返回数字 $7$。

#### 例 2

考虑下面的函数调用：

```cpp
find_maximum(1, [[5, 9], [1, 4], [3, 6], [2, 7]])
```

这意味着：

- 游戏只进行一轮；
- 第 $0$ 种颜色奖券上的数字分别是 $5$ 和 $9$；
- 第 $1$ 种颜色奖券上的数字分别是 $1$ 和 $4$；
- 第 $2$ 种颜色奖券上的数字分别是 $3$ 和 $6$；
- 第 $3$ 种颜色奖券上的数字分别是 $2$ 和 $7$；

一种能够获得最优奖励的分配方案是：

- 在第 $0$ 轮，Ringo 选择第 $0$ 种颜色的第 $1$ 张奖券（印有整数 $9$），第 $1$ 种颜色的第 $0$ 张奖券（印有整数 $1$），第 $2$ 种颜色的第 $0$ 张奖券（印有整数 $3$），第 $3$ 种颜色的第 $1$ 张奖券（印有整数 $7$）。本轮能够获得的最小奖励是 $12$。例如，游戏负责人可以选择 $b=3$：$|3-9| + |3-1| + |3-3| + |3-7| = 6 + 2 + 0 + 4 = 12$。

为了给出这个分配方案，函数 `find_maximum` 应该按照如下方式调用 `allocate_tickets`：

```cpp
allocate_tickets([[-1, 0], [0, -1], [0, -1], [-1, 0]])
```

最终，函数 `find_maximum` 应该返回数字 $12$。

#### 约束条件

- $2\le n\le 1500$ 且 $n$ 为偶数
- $1\le k\le m\le 1500$
- $0 \le x[i][j] \le 10^9$（对于所有的 $0 \le i \le n-1$ 且 $0 \le j \le m-1$）
- $x[i][j-1] \le x[i][j]$（对于所有的 $0 \le i \le n-1$ 且 $0 \le j \le m-1$）

#### 子任务

1. （11 分）$m=1$
2. （16 分）$k=1$
3. （14 分）$0 \le x[i][j] \le 1$（对于所有的 $0 \le i \le n-1$ 且 $0 \le j \le m-1$）
4. （14 分）$k=m$
5. （12 分）$n,m \le 80$
6. （23 分）$n,m \le 300$
7. （10 分）没有额外约束条件

#### 评测程序示例

评测程序示例按照下面的格式读入数据：

第 $1$ 行：$n\ m\ k$
第 $2+i$ 行（$0 \le i \le n-1$）：$x[i][0]\ x[i][1]\ \ldots \ x[i][m-1]$

评测程序示例按照下面的格式打印你的答案：

第 $1$ 行：`find_maximum` 的返回值
第 $2+i$ 行（$0 \le i \le n-1$）：$s[i][0]\ s[i][1]\ \ldots\ s[i][m-1]$


title: [JOI 2020 Final] 長いだけのネクタイ

description:
JOI 公司发明了一种领带，一共有 $N+1$ 条领带，编号为 $1$ 到 $N+1$，第 $i$ 条领带的长度为 $A_i$。

JOI 公司开了一个派对，派对中有 $N$ 名员工，第 $j$ 名员工刚开始戴了长度为 $B_j$ 的领带。

派对这样举行：

1. 首先，JOI 公司的老板 JOI 君选出一条领带拿走。
2. 然后，每个员工选一条领带，保证没有两名员工选了相同的领带。
3. 最后，他们取下最先戴的领带，戴上选择的领带。

如果一名员工刚开始戴的领带长度为 $b$，选择的领带长度为 $a$，那么他就会产生 $\max\{a-b,0\}$ 的奇怪感，整场派对的奇怪程度为所有员工的奇怪感的最大值。

于是 JOI 君定义 $C_k$ 为他选出第 $k$ 条领带后的最小奇怪程度。

JOI 君想知道 $C_k$ 的具体值。

inputFormat:
第一行一个整数 $N$ 代表员工数。
第二行 $N+1$ 个整数 $A_i$ 代表每个领带的长度。
第三行 $N$ 个整数 $B_j$ 代表每个人最开始戴的领带的长度。

outputFormat: 一行 $N+1$ 个整数 $C_k$ 代表选出每个领带后的最小奇怪程度。

hint:
#### 样例 1 解释

让我们假设 JOI 君选择了第 $4$ 条领带，那么员工们可以这么选择：

- 第 $1$ 名员工选择第 $1$ 条领带，产生奇怪感 $2$
- 第 $2$ 名员工选择第 $2$ 条领带，产生奇怪感 $0$
- 第 $3$ 名员工选择第 $3$ 条领带，产生奇怪感 $3$

奇怪程度为 $3$。

但我们还可以继续减小奇怪程度：

- 第 $1$ 名员工选择第 $2$ 条领带，产生奇怪感 $1$
- 第 $2$ 名员工选择第 $3$ 条领带，产生奇怪感 $1$
- 第 $3$ 名员工选择第 $1$ 条领带，产生奇怪感 $0$

奇怪程度为 $1$。

因此 $C_4=1$。

#### 数据规模与约定

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

- Subtask 1（1 pts）：$N \le 10$。
- Subtask 2（8 pts）：$N \le 2000$。
- Subtask 3（91 pts）：无特殊限制。

对于 $100\%$ 的数据：

- $1 \le N \le 2 \times 10^5$。
- $1 \le A_i \le 10^9$。
- $1 \le B_j \le 10^9$。

#### 说明

翻译自 [第19回日本情報オリンピック　本選](https://www.ioi-jp.org/joi/2019/2020-ho/index.html) [A 長いだけのネクタイ](https://www.ioi-jp.org/joi/2019/2020-ho/2020-ho-t1.pdf)。


title: [JOI 2020 Final] JJOOII 2

description:
定义有连续 $K$ 个 $\tt J$ 和连续 $K$ 个 $\tt O$ 和连续 $K$ 个 $\tt I$ 组成的字符串为 $K$ 阶 JOI 串。

比如，$\tt JJOOII$ 为 $2$ 阶 JOI 串，**但是，注意要有顺序**，比如 $\tt OOJJII$ 就不是 $2$ 阶 JOI 串。

现在，给定一个长度为 $N$ 的字符串 $S$，可以对他进行 $3$ 种操作：

- 操作 $1$：删除 $S$ 开头的字符
- 操作 $2$：删除 $S$ 结尾的字符
- 操作 $3$：删除 $S$ 除了开头和结尾之外的一个字符

我们要通过这些操作让 $S$ 变为 $K$ 阶 JOI 串。

但是，我们想让操作 $3$ 尽量的少。

所以我们想知道，变为 $K$ 阶 JOI 串操作 $3$ 最少需要进行多少次？

如果不能变为 $K$ 阶 JOI 串，那么输出 $-1$。

inputFormat:
第一行两个整数 $N,K$ 代表字符串长度和要构造的 JOI 串的阶数。
第二行 $N$ 个字符代表字符串 $S$。

outputFormat:
一行一个整数代表操作 $3$ 的最小进行次数。
如果不能变为 $K$ 阶 JOI 串，那么输出 $-1$。

hint:
#### 样例 1 解释

1. 进行一次操作 $1$，变为 $\tt JIJOIOIIJ$。
2. 进行一次操作 $2$，变为 $\tt JIJOIOII$。
3. 进行一次操作 $3$，删掉字符 $2$，变为 $\tt JJOIOII$。
4. 进行一次操作 $3$，删掉字符 $4$，变为 $\tt JJOOII$。

#### 样例 2 解释

$\tt JJJOOOIII$ 已经是 $3$ 阶 JOI 串了，所以不需要进行操作。

#### 样例 3 解释

$\tt IIIOOOJJJ$ 无法变为 $1$ 阶 JOI 串，无解。

#### 数据规模与约定

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

- Subtask 1（1 pts）：$N \le 21$。
- Subtask 2（12 pts）：$N \le 3000$。
- Subtask 3（87 pts）：无特殊限制。

对于 $100\%$ 的数据：

- $3 \le N \le 2 \times 10^5$。
- $1 \le K \le \dfrac{N}{3}$。
- $S$ 只包含 $\tt J$，$\tt O$，$\tt I$ 且长度为 $N$。

#### 说明

翻译自 [第19回日本情報オリンピック　本選](https://www.ioi-jp.org/joi/2019/2020-ho/index.html) [B JJOOII 2](https://www.ioi-jp.org/joi/2019/2020-ho/2020-ho-t2.pdf)。


title: [BJOI2016] 打字机

description:
小 J 在搬家的过程中发现了一台古老的打字机。 好奇的小 J 决定研究如何使用它。首先，需要将一条长度为 $m$
的纸带放入打字机。打字机上共有 26 个按键，分别是小写字母 `a` 到 `z` 。每当你按下一个按键时，打字机
就会立即在纸带上打印出那个字符，并将纸带平移一个单位距离。聪明的小 J 很快就掌握了这款打字机的使用技巧，并想尝试新的挑战。

他拿出了一本字典，挑选了 $n$ 个单词，并给每个单词设定了分数。纸带中每出现一次指定的单词，就会得到对应的分数。例如， 单词 `eye` 的分数为 $2$， `year` 的分数为 $3$，那么纸带 `eyeyeyear` 的分数为 $9$ 分。小 J 希望挑战自己，打出分数最高的纸带。

特别地，小 J 偶尔会手抖，按到自己不想输入的字符。由于这台古老的打字机没有退格（删除）功能，所以小 J 只能接受按错这个事实，重新规划在按错的情况下如何得最高分。倘若小 J 有可能在任意位置按错按键，并保证整个过程中按错的次数不超过 $k$ 次，那么请你算出他在最坏情况下的最高得分是多少。

inputFormat:
第一行包含 3 个非负整数 $n, m, k$，分别表示单词数量、纸带长度和最多按错次数。

接下来 $n$ 行，每行为一个字符串 $S$ 和正整数 $a_i$，由空格隔开，描述一个单词及其得分。

outputFormat: 仅一行，包含一个整数，表示最坏情况下的最大得分。

hint:
【样例解释】

以下是一种错误思路：

"共 $4$ 种情况，即第 $1$ 位按错、第 $2$ 位按错、第 $3$ 位按错和第 $4$ 位按错。
1. 第 $1$ 位按错（不妨假设按成 `x`，下同），最高得分为 `xwha`，得分为 $10$。
2. 第 $2$ 位按错，最高得分为 `wxha`，同样为 $10$ 分。
3. 第 $3$ 位按错，最高得分为 `haxw`，同样为 $10$ 分。
4. 第 $4$ 位按错，最高得分为 `hawx`，同样为 $10$ 分。

综上，最坏情况下最高得分为 $10$ 分。"

这种思路的错误之处在于，你不能根据哪一位按错决定你第一位按哪个键。 换种说法，你在哪一位按错，是在按下那个按键之后才能知道的事情。 正确的思路如下：

1. 第 $1$ 位先按 `h`，倘若按对， 跳至 2，倘若按错， 跳至 4；
2. 第 $2$ 位按 `a`，倘若按对， 跳至 3，倘若按错， 跳至 5；
3. 第 $3$ 位和第 $4$ 位都按 `w`， 结束。 至多错 1 次，最终纸带为 `hawx` 或 `haxw`，得分为 $10$ 分。
4. 后面三位依次按 `haw`， 结束。 因为不会再错， 最终纸带为 `xhaw`，得分为 $10$ 分。
5. 后面两位依次按 `ha`， 结束。因为不会再错， 最终纸带为 `hxha`，得分为 $9$ 分。

综上，最坏情况下，最高得分为 $9$ 分。

【数据范围】

测试点 $1,2$ 满足，$n = 1$ 或 $k = 0$；

测试点 $1\sim 6$ 满足，$n ≤ 100$，$m ≤ 500$，$∑|S| ≤ 500$，$a_i ≤1000$；

测试点 $7,8$ 满足，$k = 0$，$∑|S| ≤ 200$；

测试点 $9,10$ 满足，$∑|S| ≤ 50$，$a_i ≤1$。

对于 $100\%$ 的数据，$n ≤ 100$，$m ≤ 10^9$ ，$∑|S| ≤ 500$，$a_i ≤1000$，$k ≤ 5$。**请注意，每一个测试点都有相应特殊性质。**


title: [JOI 2020 Final] スタンプラリー 3

description:
给定一个周长为 $L$ 的圆，从一个点出发，有 $N$ 个黑白熊雕像，编号为 $1$ 到 $N$，第 $i$ 个雕像在顺时针 $X_i$ 米处，如果你没有在 $T_i$ 秒内收集到这个黑白熊雕像，那么这个雕像就会发出“唔噗噗噗”的声音然后爆炸。

现在 JOI 君在这个点，他每一秒可以移动一米，并且他可以顺时针或者逆时针的移动。

JOI 君想问，他最多能收集到多少个黑白熊雕像？

inputFormat:
第一行两个整数 $N,L$ 代表雕像数和圆的周长。
第二行 $N$ 个整数 $X_i$ 代表每个雕像在顺时针多少米处。
第三行 $N$ 个整数 $T_i$ 代表每个雕像需要在多少秒内拿到。

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

hint:
#### 样例 1 解释

JOI 君可以按照如下策略拿到 $4$ 个黑白熊雕像：

|方向|路程|总时间|第几个雕像|能否拿到|
|:-:|:-:|:-:|:-:|:-:|
|逆时针|$2$ 米|$2$ 秒|$6$|$\sqrt{}$|
|逆时针|$2$ 米|$4$ 秒|$5$|$\sqrt{}$|
|顺时针|$7$ 米|$11$ 秒|$1$|$\sqrt{}$|
|顺时针|$1$ 米|$12$ 秒|$2$|$\times$|
|顺时针|$3$ 米|$15$ 秒|$3$|$\sqrt{}$|

#### 样例 2 解释

JOI 君可以直接一直逆时针走。

#### 样例 3 解释

JOI 君无法得到任何一个雕像。

#### 数据规模与约定

**本题采用捆绑测试。**
- Subtask 1（5 pts）：$N \le 12$，$L \le 200$，$X_i \le 200$。
- Subtask 2（10 pts）：$N \le 15$。
- Subtask 3（10 pts）：$L \le 200$，$T_i \le 200$。
- Subtaks 4（75 pts）：无特殊限制。

对于 $100\%$ 的数据：

- $1 \le N \le 200$。
- $2 \le L \le 10^9$。
- $1 \le X_i<L$。
- $X_i < X_{i+1}$。
- $0 \le T_i \le 10^9$。

#### 说明

翻译自 [第19回日本情報オリンピック　本選](https://www.ioi-jp.org/joi/2019/2020-ho/index.html) [C スタンプラリー 3](https://www.ioi-jp.org/joi/2019/2020-ho/2020-ho-t3.pdf)。


title: [IOI2020] 装饼干

description:
Khong 阿姨在组织一场有 $x$ 位选手参加的竞赛，她打算给每位选手一 **袋饼干**。总共有 $k$ 种不同类型的饼干，编号为从 $0$ 到 $k-1$。类型为 $i(0 \le i \le k-1)$ 的每块饼干都有一个 **口味值** $2^i$。在 Khong 阿姨的食品储藏室里，有 $a[i]$（有可能为 $0$）块类型为 $i$ 的饼干。

对每种类型的饼干，Khong 阿姨在每个袋子都会装上 $0$ 或者多块。所有袋子里面类型为 $i$ 的饼干的总块数不能超过 $a[i]$。一个袋子里面所有饼干的口味值的总和，被称为这袋饼干的 **总口味值**。

请帮 Khong 阿姨算一下，究竟存在多少不同的 $y$ 值，使得她可以装出 $x$ 袋饼干，而且每袋饼干的总口味值都等于 $y$。

#### 实现细节

你需要实现下面的这个函数：

```cpp
int64 count_tastiness(int64 x, int64[] a)
```

- $x$：需要装的饼干袋的数量。
- $a$：长度为 $k$ 的数组。对 $0 \le i \le k-1$，$a[i]$ 表示在食物储藏室里类型为 $i$ 的饼干数量。
- 此函数应当返回不同 $y$ 值的数目，使得阿姨可以装出 $x$ 袋饼干，且每袋饼干的总口味值都为 $y$。
- 此函数会被调用 $q$ 次 (对于允许的 $q$ 值，详见约束条件和子任务部分)。每次调用应当被看成是独立的场景。

hint:
#### 样例说明

#### 例 1

考虑如下调用：

```cpp
count_tastiness(3, [5, 2, 1])
```

这意味着阿姨打算装 $3$ 袋饼干，而在食物储藏室里总共有 $3$ 种类型的饼干：

- $5$ 块类型为 $0$ 的饼干，每块的口味值为 $1$，
- $2$ 块类型为 $1$ 的饼干，每块的口味值为 $2$，
- $1$ 块类型为 $2$ 的饼干，其口味值为 $4$。

$y$ 能够取的值为 $[0,1,2,3,4]$。举例来说，为了装出总口味值均为 $3$ 的 $3$ 袋饼干，阿姨可以这样装：

- 一袋饼干里有 $3$ 块类型为 $0$ 的饼干，以及
- 两袋饼干，其中各有一块类型为 $0$ 的饼干和一块类型为 $1$ 的饼干。

由于总共有 $5$ 个可能的 $y$ 值，函数应当返回 $5$。

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

#### 例 2

考虑如下调用：

```cpp
count_tastiness(2, [2, 1, 2])
```

这意味着阿姨打算装 $2$ 袋饼干，而在食物储藏室里总共有 $3$ 种类型的饼干：

- $2$ 块类型为 $0$ 的饼干，每块的口味值为 $1$，
- $1$ 块类型为 $1$ 的饼干，其口味值为 $2$，
- $2$ 块类型为 $2$ 的饼干，每块的口味值为 $4$。

$y$ 能够取的值为 $[0,1,2,4,5,6]$。由于总共有 $6$ 个可能的 $y$ 值，函数应当返回 $6$。

#### 约束条件

- $1 \le k \le 60$
- $1 \le q \le 1000$
- $1 \le x \le 10^{18}$
- $0 \le a[i] \le 10^{18}$（对于所有的 $0 \le i \le k-1$）
- 对于 `count_tastiness` 的每次调用，食物储藏室里所有饼干的口味值总和都不会超过 $10^{18}$。

#### 子任务

1. (9 分) $q \le 10$，且对于 `count_tastiness` 的每次调用，食物储藏室里所有饼干的口味值总和都不会超过 $10^5$。
2. (12 分) $x=1,q \le 10$
3. (21 分) $x \le 10^4,q \le 10$
4. (35 分) 对于 `count_tastiness` 的每次调用，正确的返回结果都不会超过 $2 \times 10^5$。
5. (23 分) 没有附加限制条件。

#### 评测程序示例

评测程序示例将读取如下格式的输入数据。第一行包含一个整数 $q$。接下来是 $q$ 对这样的两行：它们按照下面的格式来描述一个单独的场景：

第 $1$ ⾏：$k\ x$
第 $2$ ⾏：$a[0]\ a[1]\ \ldots\ a[k-1]$

评测程序示例的输出结果的格式如下：

第 $i$ 行 ($1 \le i \le q$)：`count_tastiness` 对于输入数据中第 $i$ 个场景的返回值。


title: [IOI2020] 数蘑菇

description:
研究蘑菇的专家安德鲁在研究新加坡的本地蘑菇。

作为研究的一部分，安德鲁采集了 $n$ 个蘑菇，编号为 $0$ 到 $n-1$。每个蘑菇均为两种蘑菇种类之⼀，称为 $A$ 或 $B$。

安德鲁知道 **蘑菇 $0$ 属于种类 $A$**, 但是由于这两种蘑菇看起来很相似，他不知道蘑菇 $1$ 到 $n-1$ 属于哪一种。

幸运的是，安德鲁的实验室里有一台机器可以帮助他。在使用这台机器时，需要将两个或者多个蘑菇放到机器里，并摆成一排（以任意顺序），然后打开机器。接下来，这台机器会计算所有不属于同一种类的 **相邻** 蘑菇对的个数。例如，如果你把种类为 $[A,B,B,A]$ 的蘑菇（按照这个顺序）放到机器中，结果应该是 $2$。

但是，因为机器操作非常昂贵，机器只能使用有限的次数。此外，在机器的所有使用中，放置到机器中的蘑菇总数不能超过 $10^5$。请使用这台机器帮助安德鲁来数一数他采集了多少个种类为 $A$ 的蘑菇。

#### 实现细节

你需要实现以下函数：

```cpp
int count_mushrooms(int n)
```

- $n$: 安德鲁采集到的蘑菇数量。
- 该函数应该被调用恰好一次，而且要返回种类为 $A$ 的蘑菇的个数。

以上函数可以调用以下函数：

```cpp
int use_machine(int[] x)
```

- $x$: 一个长度介于 $2$ 和 $n$ 的数组（包括 $2$ 和 $n$)，按顺序给出放在机器中的蘑菇的编号。
- $x$ 的元素必须是在 $0$ 到 $n-1$ 之间（包括 $0$ 和 $n-1$) **互不相同** 的整数。
- 假设数组 $x$ 的长度为 $d$。那么，此函数返回不同的下标 $j$ 的个数，满足 $0 \le j \le d-2$ 并且 $x[j]$ 和 $x[j+1]$ 属于不同种类。
- 该函数最多可以被调用 $2 \times 10^4$ 次。
- 在对函数 `use_machine` 的所有调用中，所有被传到该函数 `use_machine` 的 $x$ 的总长度不能超过 $10^5$。

hint:
#### 样例说明

#### 例 1

考虑以下场景：有 $3$ 个蘑菇，种类依次为 $[A,B,B]$。函数 `count_mushrooms` 用以下方式调用

```cpp
count_mushrooms(3)
```

该函数可以调用 `use_machine([0, 1, 2])`，在该场景下调用返回 $1$。 函数接着调用 `use_machine([2, 1])`，该调用返回 $0$。

此时，已经有足够的信息来推出只有 $1$ 个 $A$ 类蘑菇。所以，函数 `count_mushrooms` 应该返回 $1$。

#### 例 2

考虑一个例子：有 $4$ 个蘑菇，种类依次为 $[A,B,A,A]$。函数 `count_mushrooms` 被调用如下：
```cpp
count_mushrooms(4)
```

该函数可以调用 `use_machine([0, 2, 1, 3])`，该调用返回 $2$。接着调用 `use_machine([1,2])`，该调用返回 $1$。

此时，已有足够的信息推出：有 $3$ 个 $A$ 类蘑菇。因此，函数 `count_mushrooms` 应该返回 $3$。

#### 约束条件

- $2 \le n \le 2 \times 10^4$

#### 计分

在所有测试用例中，如果对函数 `use_machine` 的调用不符合上面所述的要求，或者 `count_mushrooms` 的返回值不正确，你的解答得分将为 $0$。否则，令 $Q$ 为所有测试样例中对函数 `use_machine` 的最大调用次数。那么，得分将按照以下表格进行计算：

|条件|得分|
|:-:|:-:|
|$2 \times 10^4 \le Q$|$0$|
|$10010 < Q \le 2 \times 10^4$|$10$|
|$904 < Q \le 10010$|$25$|
|$226 < Q \le 904$|$\frac{226}{Q} \cdot 100$|
|$Q \le 226$|$100$|

在有些测试用例上，评测程序的行为是自适应的。也就是说，在这些测试用例中，评测程序并没有一个固定的蘑菇种类序列。相反，评测程序中所给出的回答可能依赖于此前对 `use_machine` 的调用。

但是可以保证，评测程序中所给出的回答满足：在每次交互之后，至少存在一个蘑菇种类序列，它能够与当前所给出过的所有回答都相符。

#### 评测程序示例

评测程序示例读入一个整数数组 $s$，该数组给出了蘑菇的种类。对于所有 $0 \le i \le n-1$，$s[i]=0$ 表示蘑菇 $i$ 的种类是 $A$，$s[i]=1$ 表示蘑菇 $i$ 的种类是 $B$。评测程序示例读取如下格式的输入数据：

第 $1$ 行: $n$
第 $2$ 行: $s[0]\ s[1]\ \ldots\ s[n-1]$

评测程序示例的输出为如下格式：

第 $1$ 行: `count_mushrooms` 的返回值。
第 $2$ 行: 调用 `use_machine` 的次数。

注意评测程序示例不是自适应的。


title: [IOI2020] 网络站点

description:
新加坡的互联网主干网由 $n$ 个网络站点组成，这些站点分配了从 $0$ 到 $n-1$ 的 **序号**。互联网中还有 $n-1$ 条双向链路，它们从 $0$ 到 $n-2$ 编号。每条链路连接两个不同的站点。被一条链路连接着的两个站点互相称作对方的邻居。

一个由互不相同的站点所组成的站点序列 $a_0,a_1,\ldots,a_p$ 被称作一条从站点 $x$ 到站点 $y$ 的路径，当且仅当 $a_0=x$，$a_p=y$，并且序列中每两个连续的站点都是邻居。保证从任意站点 $x$ 到任意其他站点 $y$ **有且仅有** 一条路径。

任意站点 $x$ 可以生成一个数据包，并把它发送给任意其他站点 $y$，站点 $y$ 称作这个数据包的 **目的站点**。数据包需要按下述规则在站点 $x$ 到站点 $y$ 的唯一路径上进行路由。假设数据包当前发送到了站点 $z$，其中 $y$ 是数据包的目的站点且 $z \ne y$，则站点 $z$ 会：

1. 执行 **路由函数**，找到 $z$ 到 $y$ 的唯⼀路径中 $z$ 的邻居。然后
2. 将数据包转发给这个邻居。

然而，站点有存储内存限制，可能无法存下路由函数中需要使用的完整的主干网链路列表。

你的任务是实现主干网的路由机制，它由两个函数组成。

- 第一个函数的输入参数为 $n$、主干网链路的列表和一个整数 $k \ge n-1$。该函数需要为每个站点分配一个独一无二的  **编号**，其大小在 $0$ 到 $k-1$ 之间（包括 $0$ 和 $k-1$）。
- 第二个函数是路由函数，它在站点编号分配好后部署到所有站点上。它的输入参数如下：
	- $s$，数据包当前所处的站点的 **编号**，
	- $t$，数据包的目的站点的 **编号** $(t \ne s)$，
	- $c$，表示 $s$ 的所有邻居站点的 **编号** 的列表。

该函数应该返回一个 $s$ 的邻居的 **编号**，表示数据包需要转发到的下个站点。

在每个子任务中，你的得分取决于所有站点被分配到的编号的最大值（通常来说，编号最大值越小越好）。

#### 实现细节

你需要实现下列函数：

```cpp
int[] label(int n, int k, int[] u, int[] v)
  ```

- $n$: 主干网中站点的数量。
- $k$: 可用的编号的最大值。
- $u$ 和 $v$: 大小为 $n-1$ 的数组，表示链路。对每个 $i(0 \le i \le  \le n-2)$，链路 $i$ 连接着序号为 $u[i]$ 和 $v[i]$ 的站点。
- 该函数应该返回一个大小为 $n$ 的数组 $L$。对每个 $i(0 \le i \le n-1)$，$L[i]$ 表示序号为 $i$ 的站点所分配到的编号。数组 $L$ 中的所有元素必须互不相同并且大小在 $0$ 到 $k$ 之间。

```cpp
int find_next_station(int s, int t, int[] c)
```

- $s$: 数据包当前所在站点的编号。
- $t$: 数据包目的站点的编号。
- $c$: 一个数组，包含 $s$ 的所有邻居的编号。数组 $c$ 按照元素大小升序排列。
- 该函数应该返回一个 $s$ 的邻居的编号，表示数据包需要转发到的下个站点。

每个测试用例包含一个或多个独立的场景（也就是不同的主干网描述）。 对于一个包含 $r$ 个场景的测试用例，调用上述函数的评测程序会按下列步骤运行恰好两次。

程序第一次运行期间：

- `label` 函数被调用 $r$ 次，
- 返回的编号将被评测系统保存，并且
- `find_next_station` 不会被调用。

程序第二次运行期间：

- `find_next_station` 会被调用若干次。对于每次调用，评测程序会选择任意某个场景，该场景中的 `label` 函数所返回的编号方式将用于本次 `find_next_station` 调用。
- `label` 不会被调用。
- 特别地，在评测程序第一次运行期间，保存在静态或全局变量中的信息将无法在 `find_next_station` 函数中使用。

hint:
#### 样例说明

#### 例 1

考虑下列调用：

```cpp
label(5, 10, [0, 1, 1, 2], [1, 2, 3, 4])
```

共有 $5$ 个站点和 $4$ 条链路，链路对应的站点序号对分别为 $(0,1)$, $(1,2)$, $(1,3)$ 和 $(2,4)$。编号的大小范围为 $0$ 到 $k=10$。

为了返回下列编号方案：

|序号|编号|
|:-:|:-:|
|$0$| $6$|
|$1$| $2$|
|$2$|$9$|
|$3$ |$3$|
|$4$ |$7$|

函数 `label` 应该返回 $[6,2,9,3,7]$。下图中的数字表示站点的序号（左图）与分配到的编号（右图）。

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

假设编号按照上图所示进行分配，考虑下列的调用：

```cpp
find_next_station(9, 6, [2, 7])
```

它表示数据包当前所处的站点编号为 $9$，其目的站点的编号为 $6$。从当前站点到目的站点的路径上，站点编号依次为 $[9,2,6]$。因此，函数应该返回 $2$，表示数据包应该转发给编号为 $2$ 的站点（其序号为 $1$）。

考虑另一个可能的调用：

```cpp
find_next_station(2, 3, [3, 6, 9])
  ```
该函数应该返回 $3$，因为目的站点（编号 $3$）是当前站点（编号 $2$）的邻居，因此目的站点直接接收到了数据包。

#### 约束条件

- $1 \le r \le 10$

对于 `label` 的每次调用：

- $2 \le n \le 1000$
- $k \ge n-1$
- $0 \le u[i],v[i] \le n-1$（对于所有 $0 \le i \le n-2$）

对于 `find_next_station` 的每次调用，其输入参数来自于任意选择的某次之前对 `label` 的调用。考虑它所产生的编号，

- $s$ 和 $t$ 是两个不同站点的编号。
- $c$ 是编号为 $s$ 的站点的所有邻居的编号的序列，升序排列。

对于每个测试用例，所有场景加到⼀起，传递给函数  `find_next_station` 的所有数组 $c$ 的总长度不超过 $10^5$。

#### 子任务

1. （5 分）$k=1000$，不会出现拥有多于 $2$ 个邻居的站点。
2. （8 分）$k=1000$，链路 $i$ 连接站点 $i+1$ 和 $\lfloor\frac{i}{2}\rfloor$。
3. （16 分）$k=10^6$，最多一个站点拥有多于 $2$ 个的邻居。
4. （10 分）$n \le 6$，$k \le 10^9$
5. （61 分）$k \le 10^9$

在子任务 5 中，你可以获得部分分。 令 $m$ 为所有场景中 `label` 返回的最大编号。 对于这个子任务，你的得分将根据下表计算得到：

|最大编号|得分|
|:-:|:-:|
|$m \ge 10^9$|$0$|
|$2000 \le m < 10^9$|$50 \cdot \log_{5 \cdot10^5}(\frac{10^9}{m})$|
|$1000 < m < 5000$|$50$|
|$m \le 1000$|$61$|

#### 评测程序示例

评测程序示例以如下格式读取输入数据：

第 $1$ 行：$r$

接下来是 $r$ 块内容，每块描述了一个单独的场景，格式如下：

第 $1$ 行：$n\ k$
第 $2+i(0 \le i \le n-2)$ 行：$u[i]\ v[i]$
第 $1+n$ 行：$q$，`find_next_station` 的调用次数
第 $2+n+j(0 \le j \le q-1)$ 行：$z[j]\ y[j]\ w[j]$，第 $j$ 次调用 `find_next_station` 时所涉及的站点的 **序号**。此时，数据包在站点 $z[j]$，目的站点为 $y[j]$，应该要转发给站点 $w[j]$。

评测程序示例以如下格式打印你的结果：

第 $1$ 行：$m$

接下来是 $r$ 块内容，分别对应输入中的场景。每块的格式如下：

第 $1+j(0 \le j \le q-1)$ 行：站点的 **序号**，它所对应的 **编号** 是第 $j$ 次调用 `find_next_station` 时返回的结果。

注意：评测程序示例每次执行时会同时调用 `label` 和 `find_next_station`。


title: 教材运送

background:
  “如果天依来当志愿者的话，说不定会被累死哟。”

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

  “七年三班又在什么鬼地方啊……”，不信这个邪的小灰毛喘息着抱怨。发丝凝着汗珠，慵懒地趴在白皙的后颈，粘黏感若有若无地在心里描画着燥热。数十本教材抵在胸口，大腿前伸直的双手托着艰难的重量，贴着扶手一步一步挪上漫长的台阶。

  背后，一撮可爱的棕色呆毛蹦蹦跳跳地跟了上来，“所以\~需要帮忙吗？”

description:
魔都中学的教学楼是一棵有 $n$ 个结点的树，结点 $i$ 对应编号为 $i$，人数为 $a_i$ 的教室。无向边 $i$ 描述为 $(u_i,v_i,b_i)$，对应连接教室 $u_i$ 和 $v_i$，垂直高差为 $b_i\ \text{m}$ 的台阶。

新学期开学，需要为同学们分发教材，不过传送系统的故障导致教材散落在各个教室。当天依在教室 $u$ 时，会随机抱起属于教室 $v~(v\in[1,n])$ 的 $a_v$ 本教材，并沿连接教室 $u,v$ 的唯一简单路径将这些教材送到教室 $v$。设天依走过的台阶高差为 $b_1,b_2,\cdots,b_m\ \text{m}$，每本教材重力为 $1\text{N}$，那么称此次运送中，天依的托举力做功的绝对值（上台阶取正功，下台阶取负功的绝对值）为 $W=a_v\left( \sum_{i=1}^{m} b_i \right)\text{J}$。换句话来说，一次运送的代价是**终点点权**与**走过路径边权之和**的乘积。

初始时，天依在 $1$ 号教室，但她不认识路，所以阿绫会带着天依运送教材，使得天依到达过每个教室至少一次。那么在达到这一目标之前，天依托举力做功的绝对值之和的期望为多少 $\text{J}$？

**由于答案可能是一个小数，为了避免损失精度，请输出答案在 $998244353$ 模意义下的值。**

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

#### 简化题意

给定一棵包含 $n$ 个点，有点权和边权的无根树。设当前位置 $s$（初始时 $s=1$），每次在 $n$ 个结点内随机选择目标结点 $t$，付出「$s$ 到 $t$ 的简单路径上的边权之和」$\times$「$t$ 的点权」的代价，标记（可以重复标记）点 $t$ 并把 $s$ 置为 $t$。求每个点至少被标记一次时（其中 $1$ 号结点一开始就被标记）代价之和的期望。答案对 $998244353$ 取模。

inputFormat:
第一行输入一个整数 $n$，含义如题所述。

第二行有 $n$ 个整数，表示每个教室的人数。

随后 $n-1$ 行，每行三个整数 $u_i,v_i,b_i$ 表示教室 $u_i$ 与教室 $v_i$ 之间有一垂直高差为 $b_i\ \text{m}$ 的台阶。

outputFormat: 一行一个整数，表示答案在 $998244353$ 模意义下的值。


title: 「TOCO Round 1」自适应 PVZ

background: 爆切今天的毒瘤三维计算几何后，$\color{black}\texttt{Q}\color{red}\texttt{wQcOrZ}$ 打开了某个有趣的 exe 文件。

description:
可怜的 $\color{black}\texttt Q\color{red}\texttt{wQcOrZ}$ 在草坪上遇到了 $n$ 只僵尸，第 $i$ 只僵尸在 $l_i$ 时刻出现，会在 $r_i$ 时刻走进房子。

$\color{black}\texttt Q\color{red}\texttt{wQcOrZ}$ 手头有 $m$ 个豌豆射手。若一个豌豆射手在 $l_i$ 至 $r_i$ 时刻（不包括两个端点）持续攻击 $i$ 僵尸则可以杀死 $i$ 僵尸，但在攻击过程中不能攻击另外两只僵尸且攻击的僵尸不能更换。

现在 $\color{black}\texttt Q\color{red}\texttt{wQcOrZ}$ 想知道在合理的安排下，最少有几只僵尸会进入他的房子。

inputFormat:
第一行两个整数 $n,m$ 表示僵尸数量和豌豆射手数量。

接下来 $n$ 行每行两个整数 $l_i$ 和 $r_i$ 表示僵尸 $i$ 的出现时刻和走进房子时刻。

hint:
对于 $30\%$ 的数据，$n,m\leq 6$。
对于 $60\%$ 的数据，$n,m\leq 10^3$。
对于另外 $20\%$ 的数据，$m\geq n$。
对于 $100\%$ 的数据，$1\leq n,m\leq 2\times 10^5$，$1\leq l_i<r_i\leq 10^9$。


title: [RC-03] 染色

background:
提示：输入文件很大，因此下载可能较慢（约需 3 分钟），请耐心等待。

**本题为提交答案题。** 输入数据请在[这里](http://119.27.163.117/images/files/input.zip)下载。

你提交的答案**最好**依次命名为：

- 01.out
- 02.out
- $\dots$
- 18.out

description: 给一个无向图，求尽量小的 $k$，使得能够把节点分为 $k$ 个集合，且同一集合的点间没有边。

inputFormat:
第一行三个整数：$n,m,k_0$，表示有 $n$ 个点，$m$ 条边，你的 $k$ 只要满足 $k\le k_0$ 就能得到满分。

接下来 $m$ 行，每行两个数 $x,y$，描述一条边 $(x,y)$。$(1\le x,y\le n,x\ne y)$

outputFormat:
两行，第一行为一个整数 $k$，为你的答案。$(1\le k\le n)$

第二行 $n$ 个整数，第 $i$ 个表示 $i$ 被分到的集合编号 $a_i$。$(1\le a_i\le k)$

hint:
对于每个测试点：

- 若你的输出不合法，你将得到 $0$ 分。
- 若 $k\le k_0$，你将得到满分。
- 否则你将得到（设该测试点满分为 $a$）：$\lfloor a \times \dfrac{k_0}{k}\rfloor$ 分。

本题共有 $18$ 个测试点，所有测试点均满足 $1\le n\le 10^5$，$1\le m\le 5\times 10^5$，且保证存在一种满足 $k\le k_0$ 的方案。以下是每个测试点的分值：

| 测试点编号 | 分值 |
| :----------: | :----------: |
| $1\sim 4$ | $4$ |
| $5\sim 6$ | $5$ |
| $7\sim 17$ | $6$ |
| $18$ | $8$ |


title: 「MCOI-03」诗韵

background:
$\texttt{And the game was over and the player woke up from the dream. }$

游戏结束了，玩家从梦中醒来。

$\texttt{And the player began a new dream. }$

并开始了新的梦境。

$\texttt{And the player dreamed again, dreamed better.}$

并再次沉入梦境中，沉入更好的梦。

$\texttt{And the player was the universe. And the player was love.}$

而玩家就是宇宙。而玩家就是爱。

$\texttt{You are the player.}$

你就是那个玩家。

$\texttt{Wake up.}$

该醒了。

description:
小 C 想要写首诗文，但是写诗需要押韵。

一首诗文是由需多句子组成，这些句子需要押韵。

但押韵也有优劣。小 C 对押韵有一个评分。评分定义为这些句子的最长公共后缀长度，而韵脚被定义为这些句子的公共后缀。韵脚可以为空串，一个集合的韵脚可以有多个。

最开始，小 C 一个句子也没有写出来。即最开始的记忆集合为空。

小 C 会思考 $M$ 个时刻。每个时刻，他会想出一个句子。即向记忆集合中加入一个新的句子。

小 C 可能会加入多个相同的句子，请只保留一个。因为他的记忆力很好，所以他想到的句子不会被遗忘。

但是他不想花太多心思去造句，所以他认为，只要有 **大于** $K$ 个句子，就能写成一首诗。所以每想出一个句子后，他会向你询问集合所有的元素个数 $>K$ 的子集的评分的最大值，和集合所有元素个数 $>K$ 的子集的韵脚的种类。注意：如果有多个不同的满足条件的集合韵脚相同，则这个韵脚只能计算一次。

由于小 C 很强，所以他造的所有句子的总长度可能非常大。为了方便告诉你这些句子，他造的每一个句子都是长度为 $N$ 的母串 $T$ 的子串。

**注意**：集合是满足特异性的，即集合中的元素应该互不相同，如果有相同元素仅保留一个。

inputFormat:
第一行包括三个整数 $N,M,K$。

第二行包括一个长度为 $N$ 的字符串，即母串 $T$。

接下来 $M$ 行，每行两个整数 $l,r$，表示当前时刻 小C 想起的句子是母串的 $[l,r]$ 子串。

outputFormat: $M$ 行每行两个整数。第一个整数指不同的韵脚个数，第二个整数指评分的最大值。


title: [RC-03] 难题

description: 求两个整数 $a,b$ $(1\le a,b\le n)$，使 $(a\ \mathrm{or}\ b)+(a\ \mathrm{xor}\ b)$ 最大。只需输出这个最大值。

inputFormat: 一个正整数 $n$。

outputFormat: 一个正整数，为答案。


title: 「dWoi R1」Password of Shady

background:
天海兰太郎被杀后，最原看到图书架后面刷卡器里的尘土并没有消散，陷入了沉思 ……

最原在想，黑幕是如何做到刷卡器的尘土没有消散但是还成功进入了黑幕的房间呢？然后他再次确认了刷卡器，发现了一个密码盘，密码盘下写着一行文字「真正的秘密总是被谎言欺骗，但黑幕不至于欺骗自己」，然后还有一道题，于是最原要用 1min 的时间解出这道题。

description:
这道题要求最原构造一个 $n$ 位数，并且满足以下两个要求：

- 「强者从不说废话」，代表着这个数没有前导零，$0$ 没有前导零且是一位数。
- 「强者善于成 $k$ 对合作」，代表着这个数的所有数位中有偶数个 $k$，$0$ 是偶数。

最原很快就让入间制作了一个造数器，但是造数器还需要输入有多少个满足要求的数，于是他就求助于了你，因为做造数器已经用了 59.5s，所以他想让你 0.5s 求出有多少个符合要求的数。

答案对 $998\ 244\ 353$ 取模。

inputFormat:
**本题多测**，测试组数为 $t$。
对于每组数据，一行两个整数 $n,k$。

outputFormat: 对于每组数据，一行一个整数代表答案。

hint:
#### 样例 1 解释

第一组数据，满足要求的数为：

- $0$ 个 $3$，$10\sim 12$，$14 \sim 22$，$24 \sim 29$，$40 \sim 42$，$44 \sim 52$，$54 \sim 62$，$64 \sim 72$，$74 \sim 82$，$84 \sim 92$，$94\sim 99$。
- $2$ 个 $3$，$33$。

第二组数据的样例解释写了 114514 行，但赛前 0.1s 不小心被黑白熊偷走了，书虫来不及补了。

#### 数据规模与约定

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

- Subtask 1（5 pts）：$n=1$。
- Subtask 2（25 pts）：$n \le 6$。
- Subtask 3（25 pts）：$t \le 100$。
- Subtask 4（45 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le k \le 9$，$1 \le t \le 10^6$。

---

后续：你用 0.5s 求出了答案，并且答案正确，但是最原将构造出的数输入密码盘发现错误了，所以这件事是一个谎言，最原还要去搜集言弹打学级裁判（


title: 『MdOI R4』Phoenix

background: 这是 $6$ 题中唯一一道没有题目背景的题。

description:
给定 $n$ 个**不可重**集合 $s_1\dots s_n$，集合中的数都是 $[1,m]$ 的范围内的整数。

现在请你求出有多少种 $1\sim n$ 的排列 $p$，使得

$(\sum\limits_{i=1}^n |s_i|)-(\sum\limits_{i=1}^{n-1} |s_{p_i}\bigcap s_{p_{i+1}}|)=|\bigcup\limits_{i=1}^n s_i|$

成立。

答案对 $998244353$ 取模。保证取模前的真实答案大于 $0$。

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

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

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

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，每个正整数代表一个状态压缩下的集合，若 $a_i$ 在二进制下从低位往高位的第 $k$ 位是 $1$，则 $s_i$ 包含 $k$，否则 $s_i$ 不包含 $k$。

outputFormat:
$T$ 行，每行对应一组测试数据。

对于每组数据，一行一个整数表示答案。

hint:
【样例解释 #1】

三个集合分别为 $\{1\},\{1,2\},\{1,2,3\}$。

共有四个排列符合条件，分别是 $(1,2,3),(1,3,2),(2,3,1),(3,2,1)$。

【数据规模与约定】

**本题采用捆绑测试**
|子任务编号|$n\le$|$m\le$|特殊性质|分值|
|:-|:-|:-|:-|:-|
|$1$|$10$|$20$|无特殊限制|$10$|
|$2$|$30$|无特殊限制|$a_i=2^i$|$10$|
|$3$|无特殊限制|无特殊限制|$a_i\operatorname{or}a_j=\max(a_i,a_j)$|$10$|
|$4$|无特殊限制|无特殊限制|每个集合恰好包含两个元素|$20$|
|$5$|无特殊限制|$20$|无特殊限制|$20$|
|$6$|无特殊限制|无特殊限制|无特殊限制|$30$|

对于 $100\%$ 的数据，$1 \le T \le 50$，$1\le \sum n\le  10^5$，$1\le m\le 60$，$0 \le a_i \le 2^m-1$，其中 $\sum n$  表示所有测试数据中 $n$ 的和。

【提示与帮助】

本题读入量较大，请选手选择较快的读入方式。

感谢 $\rm\textcolor{black}{J}\textcolor{red}{ohnVictor}$ 对此题的贡献。


title: [JOI 2020 Final] オリンピックバス

description:
给定一个 $N$ 点 $M$ 边的有向图，每条边从 $U_i$ 指向 $V_i$，经过这条边的代价为 $C_i$。

点编号为 $1$ 到 $N$。

我们可以翻转一条边，即让他从 $U_i$ 指向 $V_i$ 变为从 $V_i$ 指向 $U_i$，这时会有 $D_i$ 的代价产生。

你要从点 $1$ 到点 $N$，再从点 $N$ 回到点 $1$，你想知道，通过翻转一条边，或者不翻转，能得到的最小代价和为多少？

inputFormat:
第一行两个整数 $N,M$ 代表点数和边数。

接下来 $M$ 行每行四个整数 $U_i,V_i,C_i,D_i$ 代表一条边。

outputFormat: 一行一个整数代表最小代价和。无解输出 $-1$。

hint:
### 样例 1 解释

最优解为翻转第二条边，总代价为：

- 翻转的代价 $1$。
- 从点 $1$ 到点 $N$ 再返回的最短路径 $1 \to 2 \to 4 \to 3 \to 1$，代价为 $4+2+1+2=9$。

### 样例 4 解释

不一定需要翻转某条边。

### 样例 5 解释

从点 $4$ 到点 $3$ 的边有两条。

### 数据规模与约定

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

- Subtask 1（5 pts）：$M \le 1000$。
- Subtask 2（11 pts）：$M$ 为偶数，且 $U_{2i}=U_{2i-1}$，$V_{2i}=V_{2i-1}$，$C_{2i}=C_{2i-1}$。
- Subtask 3（21 pts）：$C_i=0$。
- Subtask 4（63 pts）：无特殊限制。

对于 $100\%$ 的数据：

- $2 \le N \le 200$。
- $1 \le M \le 5 \times 10^4$。
- $1 \le U_i \le N$。
- $1 \le V_i \le N$。
- $U_i \ne V_i$。
- $0 \le C_i \le 10^6$。
- $0 \le D_i \le 10^9$。

### 说明

翻译自 [第 19 回日本情報オリンピック　本選](https://www.ioi-jp.org/joi/2019/2020-ho/index.html) [D オリンピックバス](https://www.ioi-jp.org/joi/2019/2020-ho/2020-ho-t4.pdf)。


title: 「HMOI R1」50 块好兄弟

background: Polaris_Dane 非常菜，他不仅沉迷于计数，而且喜欢玩星际争霸 2。

description:
「我的好兄弟无穷无尽，而你的虫子每时每刻都在消亡」

作为新上任爱民如子的指挥官，Polaris_Dane 充分领悟了雷诺指挥官的智慧，决定将此战术贯彻到底。

有 $N$ 个兵营，依次编号为 $1,2,3\cdots N$。现在需要把它们排列在一条数轴中位于 $[1,M]$ 间的整点处。每一个兵营都有一个生产范围 $r_i$，若兵营放在点 $x\ (1 \le x \le M)$ 处，那么它会在区间 $[x - r_i + 1, x + r_i - 1]$ 生产好兄弟。

当 $\rm type = 0$ 时，生产好兄弟的范围必须被区间 $[1,M]$ 完全包含；当 $\rm type = 1$ 时，生产好兄弟的范围可以落在 $[1,M]$ 之外，但是兵营必须放在 $[1,M]$ 内。

Polaris_Dane 不能让好兄弟们太挤了，所以任何两个兵营的生产范围 **都不能相交**，他想知道有多少种方案满足该条件。

若两个方案中存在一个编号为 $i$ 的兵营，其在两个方案中的放置位置不同，则称这两个方案不同。

由于答案可能很大，所以 Polaris_Dane 想请你输出答案对 $998244353$ 取模后的结果。

inputFormat:
第一行三个整数 $N, M, \mathrm{type}$，其中 $\rm type \in \{0, 1\}$。

第二行 $N$ 个整数 $r_1, r_2, r_3, \ldots, r_n$。

outputFormat: 仅一行一个整数，为所求的答案对 $998244353$ 取模后的结果。


title: 『MdOI R4』Color

description:
小 M 同学有一张 $2$ 行 $n$ 列的方格纸，一开始所有格子都是白色的。

她决定对一些格子染色，具体地，每次她会选择两个**相邻的（四联通的，也就是有公共边的）白色**格子，其中一个染成红色，另一个染成蓝色。

她的目标是通过**任意次操作**让指定的一些格子变成红色，**对其他格子没有要求**。请你帮她判断一下，能否通过上述操作达成目标呢？

inputFormat:
**本题包含多组数据。** 第一行有一个正整数 $T$ 表示数据组数。

接下来 $T$ 组数据，每组数据三行，包括：
- 第一行，一个正整数 $n$ 表示方格纸列数。
- 第二行，一个 $01$ 串 $p_{1\ldots n}$，其中 $p_i=1$ 表示第 $1$ 行第 $i$ 列必须是红色，否则不作要求。
- 第三行，一个 $01$ 串 $q_{1\ldots n}$，其中 $q_i=1$ 表示第 $2$ 行第 $i$ 列必须是红色，否则不作要求。

outputFormat:
$T$ 行，每行对应一组数据。

对于每组数据，如果可以做到输出 `RP`，否则输出 `++`。


title: 『MdOI R4』Destiny

background: T5 的第一句话是假的。

description:
注意，本题中下标从 $0$ 开始。

一个长度为 $n$ 的序列 $\{a_i\}$ 的权值 $v(a)$ 定义为：
- $n=1$ 时为 $v(a)=a_0$。
- $n>1$ 时为它所有子区间的权值之和，也就是 $v(a_0,a_1,\ldots,a_{n-1})=\sum\limits_{i=0}^{n-2}\sum\limits_{j=0}^{n-i-1}v(a_j,a_{j+1},\ldots,a_{j+i})$.

给定一个序列，求出它的的权值，答案对 $998244353$ 取模。

这个序列是这样生成的：输入序列 $b_0,b_1,\cdots,b_{k-1}$，然后 $a_i=b_{i\bmod k}$。

inputFormat:
第一行为 $n,k$，表示序列 $a$ 的长和序列 $b$ 的长。

第二行为 $b_0,b_1,\cdots,b_{k-1}$，含义见题目描述。

outputFormat: 一行一个整数，表示序列 $a$ 的权值对 $998244353$ 取余的结果。


title: [JOI 2020 Final] 火事

background:
因为数据包过大，所以本题只测试 Subtask 4 & 5。

Subtask 1 & 2 & 3 请在 [这里](https://www.luogu.com.cn/problem/U132672) 测试。

description:
给定一个长为 $N$ 的序列 $S_i$，刚开始为时刻 $0$。

定义 $t$ 时刻第 $i$ 个数为 $S_i(t)$，那么：

$$\left\{
        \begin{array}{ll}
        S_0(t)=0\\S_i(0)=S_i\\S_i(t)=\max\{S_{i-1}(t-1),S_i(t-1)\}
        \end{array}
    \right.$$

你将对 $Q$ 个操作进行评估，第 $j$ 个操作让时刻 $T_j$ 时的区间 $[L_j,R_j]$ 全部变为 $0$。

执行一个操作需要一定的代价，执行第 $j$ 个操作需要以下的代价：

$$\sum\limits_{k=L_j}^{R_j}S_k(T_j)$$

求每个操作需要的代价。

注意：每个操作都是独立的。

inputFormat:
第一行两个整数 $N,Q$ 代表序列长度和操作数。
第二行 $N$ 个整数 $S_i$ 代表这个序列。
接下来 $Q$ 行每行三个整数 $T_j,L_j,R_j$ 代表一个操作。

outputFormat: $Q$ 行每行一个整数代表这个操作需要的代价。


title: [JOISC2020] 最古の遺跡 3

background: JOI 教授是一名研究 IOI 王国的历史学家。

description:
他发现了一行古代石柱的废墟及一份古代文献。

古代文献上的记载如下：
- 刚建造完成的时候，有 $2\times N$ 个石柱，对于 $1\le k\le N$ 均有两个石柱高度为 $k$，同时记第 $i$ 个石柱的高度为 $h_i$。
- 会发生 $N$ 次地震，每次地震会使一些石柱的高度 $-1$，其他石柱高度不变。
- 石柱 $i$ 地震时高度不变，当且仅当 $h_i\ge 1$ 并且对于 $j>i$ 都要有 $h_i\not=h_j$
- $N$ 次地震后，恰好只剩下了 $N$ 个石柱。

现在 JOI 教授找出了仅存的 $N$ 个石柱的位置 $A_1,A_2,\ldots,A_N$，他想让你求出，最初 $2\times N$ 个石柱高度的修建方案数 $\bmod~10^9+7$ 的值。

inputFormat:
第一行为一个整数 $N$。

接下来一行 $N$ 个数，表示 $A_1,A_2,\ldots,A_N$。

outputFormat: 仅一行一个整数，表示最初 $2\times N$ 个石柱高度的建造方案数 $\bmod~10^9+7$ 的值。


title: 「MCOI-03」金牌

background:
**这是一道交互题**。

书虫有很多块金牌！

description:
书虫正在整理他的 $n$ 块金牌，他发现所有金牌都是有磁性的！形式地说，每块金牌属于一种磁极，**磁极有很多种**。两块相邻的金牌磁极相同则相互排斥，不同则相互吸引。

书虫不知道每块金牌的磁极，他只能通过把两块金牌靠近的方式得知它们是相同磁极还是不同磁极。换句话说，你可以进行不超过 $Q$ 次交互，每次向交互库询问两个数 $x,y$，交互库会返回第 $x$ 块金牌和第 $y$ 块金牌是排斥还是吸引。金牌从 $0$ 到 $n-1$ 编号。

书虫希望把他的金牌排成一个排列，满足任意两块相邻的金牌都相吸引，请你帮他排出 **任意一个** 合法的排列，或者告诉他无解。

### 交互格式

**本题包含多组数据**。输入的第一行包含一个整数 $T$, 代表数据组数。

对于每一组数据，第一行读入两个整数 $n,Q$，代表金牌的数量和交互次数上限。

如果你需要向交互库发起询问，请向标准输出中输出一行以空格隔开的两个整数 $x,y$ 并 **清空缓冲区**。关于如何清空缓冲区，在下面的提示中有说明。接下来，从标准输入中读入一个整数 $ret$。如果 $ret=1$ 表示第 $x$ 块金牌和第 $y$ 块金牌吸引，如果 $ret=0$ 表示它们排斥。

如果你已经确定无解，请输出一行一个整数 $-1$ 并 **清空缓冲区**。然后本组数据结束，你应该接下来处理下一组数据。

如果你已经确定有解，请先输出一行一个整数 $n$，接下来一行输出 **任意一组** 合法的金牌排列，并 **清空缓冲区**。然后本组数据结束，你应该接下来处理下一组数据。

$T$ 组数据处理完之后你应该立即结束程序，多余的输出可能导致 RE。

inputFormat: 见「交互格式」。

outputFormat: 见「交互格式」。

hint:
### 样例 1 解释

样例中有两组数据。对于第一组数据，共有三块金牌，通过三次交互得知，它们的磁极都互不相同，那么任意一种排列都是正确的。

对于第二组数据，两块金牌的磁极相同，所以无解。

### 数据规模与约定

**本题使用捆绑测试**，数据范围如下表：

| 测试点编号 | $Q=$ | 特殊性质 | 得分 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $\frac{n(n-1)}{2}$ | $n\ge 4$ | $10$ |
| $2$ | $2n-2$ | 一种磁极最多只有 $2$ 块金牌 | $20$ |
| $3$ | $2n-2$ | 磁极的种类不超过 $3$ 种 | $20$ |
| $4$ | $3n$ | 无 | $20$ |
| $5$ | $2n-2$ | 无 | $30$ |

对于全部数据，$2\le n\le5\times10^4$，$1\le T\le 5\times 10^4$，$\sum Q\le 10^5$。

### 提示

你可以使用如下语句来清空缓冲区：

- 对于 C/C++：```fflush(stdout);```
- 对于 C++：```std::cout << std::flush;```
- 对于 Java：```System.out.flush();```
- 对于 Python：```stdout.flush();```
- 对于 Pascal：```flush(output);```
- 对于其他语言，请自行查阅对应语言的帮助文档。
- 特别的，对于 C++ 语言，在输出换行时使用 ```std::endl ``` 而不是 ```'\n'```，也可以自动刷新缓冲区。


title: [JOISC2020] ジョイッターで友だちをつくろう

background: Joitter 是一款交友软件。

description:
在 Joitter 你可以关注他人，但你不可以关注自己和关注他人两次，即如果关注他人多次只会算作一次。

共有 $N$ 名新用户，$M$ 天。

在第 $i$ 天，用户 $A_i$ 会关注用户 $B_i$。

同时在关注之后，会举办一场交友活动，活动内容如下：

1. 选择一个用户 $x$。
2. 选择一个被用户 $x$ 关注的用户 $y$。
3. 选择一个用户 $z$，要求 $z\not=x$，$x$ 未关注 $z$ 且 $y$ 和 $z$ 互关。
4. 让 $x$ 关注 $z$。
5. 重复 $1,2,3,4$，直到选不出合适的三元组 $(x,y,z)$。

您需要求出，对于每一个 $i$，第 $i$ 天过后的所有关注总数。

inputFormat:
第一行为两个整数 $N,M$。

接下来 $M$ 行，一行两个整数 $A_i,B_i$。

outputFormat: 输出共 $M$ 行，每一行一个数，第 $i$ 行表示经过第 $i$ 天之后的关注总数。

hint:
#### 子任务
对于 $100\%$ 的数据，保证 $2\le N\le 10^5$，$1\le M\le 3\times 10^5$，$1\le A_i,B_i\le N$，$A_i\not=B_i$，$(A_i,B_i)\not=(A_j,B_j)$。

| 子任务编号 | $N\le $ | 分值 |
|:-:|:-:|:-:
| $1$ | $50$ | $1$ |
| $2$ | $2\times 10^3$ | $16$ |
| $3$ | 无 | $83$ |

#### 说明
本题译自 [第 19 回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) Day 2 [T2 ジョイッターで友だちをつくろう](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day2/joitter2-en.pdf)。


title: NOI

background:
小 L 是一个菜鸡。

啥也不会的小 L 上了 NOI 考场。

description:
由于小 L 不会算数，现在小 L 告诉了你他每题的分数和队线，请你告诉他是否进队。

NOI 分数的计算方式是：

1. 笔试基础有 $50$ 分，每通过一题加 $1$ 分。
2. 实际得分是每题的分数加上笔试的分数。
3. 如果是 A 类，总分在此基础上再加 $5$ 分。

inputFormat: 输入 $9$ 个数 $a,b,c,d,e,f,g,h,i$，分别表示笔试通过题数, D1T1,D1T2,D1T3,D2T1,D2T2,D2T3 得分，是否 A 类（是 $1$，不是 $0$），集训队分数线。

outputFormat:
输出一行一个字符串。

如果进了集训队，则输出 `AKIOI`。

如果没进，输出 `AFO`。

hint:
#### 「样例解释」

样例第一个是退役菜鸡小 L 的 NOI2020 成绩。

第二个是某位队爷的 NOI2020 成绩。

~~这不是啥都没解释吗~~

---

#### 「数据范围与说明」

**本题采用捆绑测试**。仅有通过某个 Subtask 中所有测试点才能获得该 Subtask 的分数。

- Subtask 1(30 points)：$h = 0$，$a = 50$，$i = 700$；
- Subtask 2(30 points)：$h = 0$，$a = 50$；
- Subtask 3(40 points)：无特殊限制。

对于所有数据，$0\leq a \leq 50$，$0\leq b,c,d,e,f,g \leq 100$，$0 \leq h \leq 1$，$205\leq i \leq 705$。

此处不考虑第 $50$ 名同分的情况，可以认为如果同分小 L 优先。

不保证测试数据为真实成绩。


title: 双生独白

background:
我喜欢安静，你热爱喧闹；我忠于温暖，你酷爱凉爽。

如果任何事物都有反面，那拼接这个世界的颜色呢？

只有白与黑吗？

description:
为了形式化地描述颜色，我们引入 **RGB 颜色值**，用三元组 $(r,g,b)$ 表示一种颜色，其中 $r,g,b$ 分别为该颜色的 **R 值**、**G 值**、**B 值**，满足 $0 \le r,g,b \le 255$ 且皆为**十进制整数**。

显然，这套颜色系统一共可以表示 $256 \times 256 \times 256 = 16\,777\,216$ 种不同的颜色。对于颜色 $(r,g,b)$，定义其**反色**的 RGB 颜色值为 $(255-r,255-g,255-b)$。

然而人们发现，单纯地使用 RGB 颜色值很不方便，复制颜色时要复制三个值。

于是诞生了**十六进制颜色码**，即形如 `#EBA932` 长度为 $7$ 的字符串。具体而言：

- 字符串的第一位是 `#`，为颜色码标识符。
- 字符串的第二、三位是十六进制数码，拼成的十六进制数等于十进制下所示颜色的 R 值。
- 字符串的第四、五位是十六进制数码，拼成的十六进制数等于十进制下所示颜色的 G 值。
- 字符串的第六、七位是十六进制数码，拼成的十六进制数等于十进制下所示颜色的 B 值。

**十六进制数码**从小到大包含 `0`，`1`，`2`，`3`，`4`，`5`，`6`，`7`，`8`，`9`，`A`，`B`，`C`，`D`，`E`，`F`，注意 `A`，`B`，`C`，`D`，`E`，`F` 均为**大写**。

现在你收到了一组十六进制颜色码，请你输出其反色的十六进制颜色码。

*提示：颜色的 RGB 值与十六进制码之间可以相互转换（参考样例解释 #2）*

inputFormat: 一行，输入长度为 $7$ 的字符串，表示原色的十六进制颜色码。

outputFormat: 一行，输出长度为 $7$ 的字符串，表示反色的十六进制颜色码。

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

转换后原色的 RGB 值为 $(255,255,255)$，反色的 RGB 值为 $(0,0,0)$，对应十六进制码 `#000000`。

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

转换后原色的 RGB 值为 $(235,169,50)$，反色的 RGB 值为 $(20,86,205)$，对应十六进制码 `#1456CD`。

为避免理解偏差，此处特别解释 `#EBA932` 转换后 B 值为 $50$ 的原因：提取字符串的第六、七位，拼成的十六进制数为 $(32)_{16}$，则有 $(32)_{16} = 3 \times 16^1 + 2 \times 16^0 = 50$。

----

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

本题共有 10 个测试点，每通过一个测试点可获得 10 points。

对于 $10\%$ 的数据，为样例 #1。

对于另外 $30\%$ 的数据，输入与输出字符串均不包含大写字母。

对于所有的数据，保证给定字符串为合法十六进制颜色码。


title: 「SWTR-7」Spider Solitaire

background:
#### 题目描述下方有简化题意。

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

---

小 A 在玩蜘蛛纸牌。
为了方便你理解蜘蛛纸牌，小 A 给出了简化后的游戏规则：

- 一副牌有 $n$ 张，从小到大分别为 $1,2,\cdots,n$。
- 现有 $m$ 个牌堆，$1$ 副牌。每个牌堆中有 $0$ 张或多张牌。
- 定义「龙」$a_1,a_2,\cdots,a_d$ 为满足 $a_i-1=a_{i+1}\ (1\leq i<d)$ 的任意多张连续的牌。**一张牌也是一个「龙」。**
- 一组连续的牌可以移动，当且仅当这组牌形成了一个「龙」，且「龙」在牌堆的**最右边**。
- 一组连续的牌只能移动到一个**非空**牌堆的最右边，**且必须满足可以与该非空牌堆最右边的「龙」构成一条更大的「龙」**。
- 游戏胜利，当且仅当所有的 $n$ 张牌形成了一个「龙」。

---

例如当 $m=3$，$n=9$，局面为

```plain
9 8 4 3 2 1
7 5
6
```

时，第一个牌堆最右边的 `4 3 2 1` 形成了一个「龙」，所以 `4 3 2 1` 可以移动。将 `4 3 2 1` 移动到第二个牌堆的最右边，此时局面为

```plain
9 8
7 5 4 3 2 1
6
```

接下来将第二个牌堆右边的 `5 4 3 2 1` 移动到第三个牌堆的最右边，此时局面为

```plain
9 8
7
6 5 4 3 2 1
```

接下来将第三个牌堆的 `6 5 4 3 2 1` 移动到第二个牌堆的最右边，此时局面为

```plain
9 8
7 6 5 4 3 2 1
\
```

接下来将第二个牌堆的 `7 6 5 4 3 2 1` 移动到第一个牌堆的最右边，此时牌堆为

```plain
9 8 7 6 5 4 3 2 1
\
\
```

因为所有 $9$ 张牌形成了一个「龙」，所以游戏胜利。

description:
给定一个蜘蛛纸牌初始局面，小 A 想知道能否获得胜利。若能，请输出 $\texttt{YES}$ 以及**获胜所需的最小步数**。否则输出 $\texttt{NO}$。

小 A 还想知道，对于每张牌 $i$，如果要移动 $i$ 至少需要多少步，**包括移动 $i$ 的这一步**。如果无法移动输出 `-1`。

---

#### 「简化题意」

有 $m$ 个**横向**的数堆，数堆里共有 $n$ 个数，每个数堆里有 $0$ 或多个数。所有数堆里的数组成了 $1\sim n$ 中的所有数。

你可以将一个数堆**最右边递减且公差为 $-1$ 的**连续若干个数 $a_1,a_2,\cdots,a_c$ **按照原来的顺序移到另外一个非空数堆的最右边**，当且仅当该非空数堆最右边的一个数 $b=a_1+1$。

求将所有的 $n$ 个数都移动到同一个数堆且满足从左往右依次递减的最小步数。如果无解输出 $\texttt{NO}$。

**此外，你还需要对于每个数 $i$，输出如果要移动 $i$ 至少需要多少步。**

inputFormat:
第一行一个整数 $T$，表示子任务编号。
第二行两个整数 $n,m$，分别表示一副牌的张数和牌堆的个数。
接下来 $m$ 行，每行首先一个整数 $c$ 表示该牌堆中牌的个数，接下来 $c$ 个整数 $b_1,b_2,\cdots,b_c$ **从左到右**描述这个牌堆。

outputFormat:
如果能够获胜，在第一行输出 $\texttt{YES}$，**第二行输出最少步数**。否则输出一行 $\texttt{NO}$。

无论是否能够获胜，你还需输出 $n$ 行，第 $i$ 行一个**介于 $-1$ 与 $n$ 之间的整数**，表示移动 $i$ 至少需要多少步。

hint:
**「样例 1 说明」**

因为 1,2,3,4,5 可以直接移动，所以至少需要 1 步即可移动。
因为需要先将 5 移至 6 右侧，6 才能移动，所以至少需要 2 步即可移动。
因为需要先将 5 移至 6 右侧，再将 4,3,2,1 移至 5 右侧，7 才能移动，所以至少需要 3 步即可移动。
显然 8,9 无法移动。

**「Special Judge」**

本题使用 Special Judge，请**严格遵守输出格式**：

- 如果你正确输出对能否获胜的判定，且如果能够获胜，你正确输出最小步数，你将获得该测试点**至少** $40\%$ 的分数。
- **在上一部分的基础上**，如果你正确输出移动每张牌的最小步数，你将获得该测试点**剩下** $60\%$ 的分数。也就是说，如果你上一部分输出错误，你在这一部分也不会获得任何分数。
- **如果你的输出格式错误，你将获得该测试点 $0\%$ 的分数**，包括但不限于**只输出对能否获胜的判定**。
- 需要特别注意的是，如果你不能正确求出移动每张牌的最小步数，请**随机输出 $[-1,n]$ 之间的任意整数**，否则你将获得该测试点 $0\%$ 的分数。
- 每行结束后你都需要输出换行符，**包括最后一行**。

checker 将在题目最后给出。

**「数据范围与约定」**

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

- Subtask #0（0 points）：是样例。
- Subtask #1（15 points）：$n\leq 3\times 10^3$，$m=2$。
- Subtask #2（15 points）：$b_i>b_{i+1}\ (1\leq i<c)$，$n\leq 3\times 10^3$。
- Subtask #3（25 points）：$n\leq 14$，$m=3$。
- Subtask #4（30 points）：$n\leq 3\times 10^3$。
- Subtask #5（15 points）：无特殊限制。

对于 $100\%$ 的数据，$1\leq n,m\leq 5\times 10^4$。时间限制 1s，空间限制 512MB。

**「题目来源」**

[Sweet Round 07](https://www.luogu.com.cn/contest/51773) D。
idea & solution & data：[Alex_Wei](https://www.luogu.com.cn/user/123294)；验题：[chenxia25](https://www.luogu.com.cn/user/138400)。

---

以下是 checker，你需要有 testlib.h 才能成功编译。

```cpp
#include "testlib.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb emplace_back
#define mp make_pair
#define vint vector <int>
#define vpii vector <pii>
#define all(x) x.begin(),x.end()
#define sor(x) sort(all(x))
#define rev(x) reverse(all(x))
#define mem(x,v) memset(x,v,sizeof(x))

#define rint inf.readInt
#define reof inf.readEof()
#define reoln inf.readEoln()
#define rspace inf.readSpace()

// wrong answer : quitf(_wa,"The answer is wrong")
// accepted :  quitf(_ok,"The answer is correct")
// partly correct : quitp(0.5,"The answer is partly correct")

int main(int argc,char* argv[]){
	registerTestlibCmd(argc,argv);

	string jans=ans.readToken();
	string pans=ouf.readToken(jans);
	int sub=rint(),n=rint(),diff=0;

	if(jans=="YES"){
		int jstep=ans.readInt();
		int pstep=ouf.readInt();
		if(jstep!=pstep)quitf(_wa,"The answer is wrong");
	}

	for(int i=1;i<=n;i++){
		int jans=ans.readInt();
		int pans=ouf.readInt();
		if(jans!=pans)diff=1;
	}

	while(!ouf.seekEof())ouf.readToken();
	while(!inf.seekEof())inf.readToken();
	while(!ans.seekEof())ans.readToken();
	if(diff)quitp(0.4,"The answer is partially correct");
	else quitf(_ok,"OK, you AK IOI");

	return 0;
}
```


title: 天选之人

background:
暑假期间，学校不提供午餐，Gnar 只好找伙计们一起点外卖。

尴尬的是，外卖很快送到却没人乐意去校门口拿，毕竟户外可是 $35\degree\!\text{C}$ 高温！此时 Gnar 想到了好主意：“我给一人捏了一张纸团，其中一张写有记号，不如我们抓阄决定，谁抽到带记号的谁去拿！”

于是 Gnar 连续拿了六天的外卖。

这可让他不服又委屈：“换个规则！一人准备三张纸团，五张有记号，每人抽三张，记号最多的去拿！”

Gnar 紧张地展开手中的纸团，两个记号赫然映在眼前。大伙们刚想放声大笑他的非酋运气，有人缓缓举起三张纸片说道：“我也抽到了两个记号……”

description:
好奇的 Gnar 想研究一般情况下抽到最多记号的人数。他给参与抓阄的 $n$ 人一人准备了 $m$ 张捏好的纸团，一共 $nm$ 张，其中恰好 $k$ 张提前写了记号。随后每个人在均匀打乱的纸团中各抽 $m$ 张。

一个人抽到最多的记号，当且仅当没有人抽到的记号比他还多。请你帮 Gnar 判断是否可能会**恰好** $\boldsymbol{p}$ **个人**抽到最多的记号。Gnar 喜欢追根问底，所以如果有可能，你还需构造每个人抽的纸团中分别有多少带记号、有多少不带记号。

形式化地，假设第 $i$ 个人抽到了 $x_i$ 张带记号的纸团和 $y_i$ 张不带记号的纸团，你的构造应满足：

- $x_i, y_i \ge 0$，$x_i + y_i = m$。
- $\displaystyle \sum_{i = 1}^{n} x_i = k$。
- **有且仅有** $\boldsymbol{p}$ **个互不相同**的 $j$ 使 $\displaystyle x_j = \max_{i = 1}^{n} \{x_i\}$。

inputFormat: 输入四个整数 $n, m, k, p$，含义详见题目描述。

outputFormat:
第一行输出 `YES` 或 `NO`（不区分大小写，`yEs` / `No` 均可），表示是否会恰好 $p$ 个人抽到最多的记号。

如果第一行输出 `YES`，接下来 $n$ 行每行输出 $x_i, y_i$，表示每个人抽到带与不带记号的纸团个数。

因答案可能不唯一，本题采用 Special Judge，只要构造符合题面中的要求均视为正确。

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

样例给出了一种满足题述条件的构造。

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

不论如何，记号的分布从高到低只有三种情况：$\{3,0,0\}$，$\{2,1,0\}$，$\{1,1,1\}$，抽到最多记号的人数分别对应 $1$，$1$，$3$。因此无法构造 $p = 2$ 的方案。

----

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

**本题采用捆绑测试**。你必须通过 Subtask 中所有的测试点才能获得该 Subtask 的分数。

- Subtask #1 (15 points)：$n,m \le 8$。
- Subtask #2 (15 points)：$n,m \le 100$。
- Subtask #3 (20 points)：$n,m \le 10^5$。
- Subtask #4 (10 points)：$p = 1$。
- Subtask #5 (40 points)：无特殊限制。

对于所有的数据，保证 $1 \le p \le n \le {10}^5$，$1 \le m \le {10}^9$，$0 \le k \le n m$。


title: 移花接木

background:
遥远的圣地生长着一棵不为人知的灵树，或有万山之高。

但有一日，藏匿于根系的腐朽力量爆发，灵树已无法支撑往日屹立冲天的高度。

description:
灵树最初的形态可以看作一棵高度为 ${10}^{{10}^{{10}^{10}}}$ 的满 $a$ 叉树，高度定义为根结点到叶子结点之间的边数。

受腐朽力量影响，灵树只能维持高度**恰好**为 $h$ 的满 $b$ 叉树形态。为了转换至该形态，灵树有两种魔法：

- 移花：选择一条边 $u \to v$（$u$ 是 $v$ 的父结点），移除这条边以及以 $v$ 为根的**整棵子树**。
- 接木：选择一条边 $u \to v$（$u$ 是 $v$ 的父结点）和一个结点 $w$（$w$ 不能是 $v$ 子树中或已移除的结点），将这条边原先 $u$ 一端**改接**到 $w$。**该魔法只能在根结点到** $\boldsymbol{u}$ **之间的边数** $\le 10^{10^{10}}$ **时使用。**

灵树累积的魔法力量有限，它不得不用最少次数的魔法完成转换。这是个漫长的过程，即使次数最少也会显得异常大，你只需要求出最少次数对 $10^9 + 7$ 取模的结果。

inputFormat:
输入首行给定数据组数 $T$。

接下来 $T$ 行，每行包含三个整数 $a,b,h$，表示一组数据。

outputFormat: 对于每组数据输出一行一个整数，表示该数据的答案对 $10^9 + 7$ 取模的结果。

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

下为 $a=1$，$b=2$，$h=1$ 时的两步转换过程，图中高度极大的冗余子树已用省略号代替。

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

可以证明，该数据的答案不可能低于 $2$。

----

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

**本题采用捆绑测试**。你必须通过 Subtask 中所有的测试点才能获得该 Subtask 的分数。

- Subtask #1 (3 points)：$h = 0$。
- Subtask #2 (4 points)：$a = b$。
- Subtask #3 (8 points)：$a = 1$。
- Subtask #4 (8 points)：$b = 1$。
- Subtask #5 (17 points)：$h \le 10$。
- Subtask #6 (15 points)：$h \le 10^6$，各测试点存在 $\overline{a},\overline{b}$，其数据满足 $a=\overline{a}$，$b=\overline{b}$。
- Subtask #7 (15 points)：$h \le 10^6$。
- Subtask #8 (30 points)：无特殊限制。

所有测试点（样例除外）均含有 $10^6$ 组数据，即 $T = 10^6$。请务必采用较快的 IO（输入/输出）方式。

对于所有的数据，保证 $1 \le a,b \le 10^9$，$0 \le h \le 10^9$。


title: [JOISC2020] カメレオンの恋

background:
您可以在如下的代码模板中编写程序：

```cpp
#include<bits/stdc++.h>
using namespace std;
extern "C" int Query(const std::vector<int> &p);
extern "C" void Answer(int a, int b);
extern "C" void Solve(int N) {

}
```

description:
在 JOI 动物园中，有 $2\times N$ 只变色龙，有 $N$ 只的性别为 $\rm X$，另外 $N$ 只的性别为 $\rm Y$。

每一只变色龙均有其原始颜色，其约束如下：
- $\rm X$ 性别的变色龙颜色两两不同。
- 对于每一只 $\rm X$ 性别的变色龙，都有一只 $\rm Y$ 性别的变色龙颜色与之相同。

现在每一只变色龙都爱另一只变色龙了，具体规则如下：
- 每一只变色龙只爱异性变色龙。
- 每只变色龙与其喜欢的变色龙有不同的初始颜色。
- 不会存在两只变色龙爱一只变色龙。

现在您可以组织一些变色龙开会，对于每一只在会议中的变色龙 $s$，设 $s$ 爱的变色龙为 $t$。

- 若 $t$ 参加会议，则 $s$ 的皮肤颜色为 $t$ 的原始颜色。
- 否则，$s$ 的皮肤颜色为 $s$ 的原始颜色。

对于您组织的每次会议，您可以统计不同的肤色数量。

通过召开不超过 $2\times 10^4$ 次会议，您要确定初始颜色相同的每一对变色龙。

#### 交互细节
您需要在程序前声明两个函数：
- `int Query(const std::vector<int> &p)`。
- `void Answer(int a, int b)`。

您需要实现一个函数：`void Solve(int N)`。
- 每个测试样例仅调用一次。
- $N$ 的意义如题。

你的程序可以调用如下函数：
- `int Query(const std::vector<int> &p)`
   - 您可以调用此函数来组织变色龙会议。
       - $p$ 是参加会议的变色龙名单。
       - 这会返回参加会议的变色龙颜色的种数。
       - 所有 $p$ 内的数必须在 $1$ 到 $2\times N$ 之间，不然会返回 `Wrong Answer [1]`。
       - 所有 $p$ 内的数必须是两两不同的，不然会返回 `Wrong Answer [2]`。
       - 您只能调用此函数 $2\times 10^4$ 次，若超过，会返回 `Wrong Answer [3]`。

- `void Answer(int a, int b)`
   - 调用这个函数来提交一对原始颜色相同的变色龙。
       - 参数 $a$ 和 $b$ 表示变色龙 $a$ 和 $b$ 具有相同的初始颜色。
       - 您需要保证 $1\le a,b\le 2\times N$，否则会返回 `Wrong Answer [4]`。
       - 您需要保证每一次提交的变色龙不同，否则会返回 `Wrong Answer [5]`。
       - 如果您提交的 $a$ 和 $b$ 的初始颜色不同，会返回 `Wrong Answer [6]`。
       - 您需要调用 $N$ 次该函数，否则会返回 `Wrong Answer [7]`。

如果您在交互过程中均未违反限制，恭喜您 AC 了。

inputFormat:
交互库输入格式如下：

第一行为一个整数 $N$。

第二行为 $2\times N$ 个整数 $Y_i$，表示变色龙的性别，$Y_i=0$，则性别为 $\rm X$，$Y_i=1$，则性别为 $\rm Y$。

第三行为 $2\times N$ 个整数 $C_i$，$C_i$ 表示变色龙 $i$ 的颜色。

第四行为 $2\times N$ 个整数 $L_i$，$L_i$ 表示变色龙 $i$  稀饭变色龙 $L_i$。

outputFormat:
交互库输出格式如下：

若您 AC 了，则输出一行 `Accepted: x`，$x$ 是您调用 `int Query(const std::vector<int> &p)` 的次数。

若您 WA 了，则输出一行 `Wrong Answer [type]`，$type$ 是您 WA 的原因，可参照交互细节。


title: 『MdOI R4』Balance

background:
可怜的 $\rm\textcolor {grey}{JohnVictor}$ 玩的卡组在平衡性调整中被削弱了，现在他掉了很多杯，他想知道什么样的一个世界才是真正平衡的。

于是就有了这题。

description:
给定长度为 $n$ 的，由整数构成的数组 $a,b,p,q$，并定义函数 $f(i,j)=\dfrac{a_i+b_j}{p_i+q_j}(1\le i,j\le n)$。

再给定两个整数 $x,y$，你需要求出一对 $(i,j)$，使得 $f(i,j)$ 在所有 $f(i,t)(t=1,2,\cdots,n)$ 中是第 $x$ 小的，在所有 $f(s,j)(s=1,2,\cdots,n)$ 中是第 $y$ 小的。

在本题中，我们称一个数 $x$ 在序列 $c_{1\ldots n}$ 中是第 $k$ 小的，当且仅当在 $c$ 中有且仅有 $\alpha$ 个数 $y$ 满足 $y<x$，且有且仅有 $\beta$ 个数 $y$ 满足 $y\le x$，同时 $\alpha<k\le \beta$。

如果不存在这样的 $(i,j)$，请输出 `0 0`。

如果有多组这样的 $(i,j)$，输出任意一组即可。

由于平衡性的问题不是一次就能问清楚的，所以出题人会问你多次。

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

第一行一个整数 $T$ 表示数据组数，对于每组数据：

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

接下来 $n$ 行，每行 $4$ 个整数。第 $i$ 行的四个整数为 $a_i,b_i,p_i,q_i$。

outputFormat: $T$行，每一行两个整数，表示你找出的 $(i,j)$。


title: 晚秋绝诗

description:
在晚秋时分观赏 L 国举世闻名的佳景——藏雾山，无不是一件惬意之事。

藏雾山共有 $n$ 座山峰，从 $1$ 到 $n$ 编号。起初，$n$ 座山峰的山顶均被秋雾遮盖，因而无法辨别其高度。

同时，称第 $i$ 座山峰为**间峰**，当且仅当其高度恰好是第 $i-1$ 座与第 $i + 1$ 座高度的平均值（特别地，第 $1$ 座与第 $n$ 座**不算**间峰）。藏雾山一带向来会在**部分间峰**的山底悬挂旗帜，起初所有山峰的山底均无旗帜。

现有 $m$ 天，每天会发生以下之一的事件：

- 雾去/雾回：第 $x$ 座山峰山顶的秋雾散去，或重新聚集。
- 旗升/旗落：第 $x$ 座山峰山底的旗帜挂起，或被人卸下。
- 来客：一位登山爱好者造访藏雾山欲攀登第 $x$ 座山峰，他希望能当天知晓该山峰的海拔高度。

登山爱好者们将以两种方式知晓：直接观测出**未被秋雾遮盖**山峰的海拔高度，或是利用当天各山底旗帜给出的间峰信息，**尽可能地推算出其余**山峰的高度。除此之外，他们无法使用其他方式，包括但不限于与过往的来客交流分享信息等。

你能求出每位登山爱好者能否知晓目标山峰的高度吗？

inputFormat:
第一行包含两个正整数 $n$ 和 $m$，分别为藏雾山的山峰个数和事件持续的天数。

接下来 $m$ 行，每行包含两个正整数 $op, x$，其中 $op \in \{1,2,3\}$，具体地：

- 对于 $op=1$，保证 $1 \le x \le n$，表示若第 $x$ 座山峰的山顶有雾，则变为无雾状态；若第 $x$ 座山峰的山顶无雾，则变为有雾状态。
- 对于 $op=2$，保证 $2 \le x < n$，表示若第 $x$ 座山峰的山底无旗，则变为有旗状态；若第 $x$ 座山峰的山底有旗，则变为无旗状态。
- 对于 $op=3$，保证 $1 \le x \le n$，表示一位欲攀登第 $x$ 座山峰的登山爱好者造访。

outputFormat: 输出若干行，每行一个布尔值依次表示每位登山爱好者能否知晓高度，$1$ 则能，$0$ 则不能。

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

在没有任何间峰信息的情况下，第一个登山爱好者不可能知晓被秋雾遮盖山峰的高度。

第二个登山爱好者造访时已知山峰 $1$ 的高度、山峰 $3$ 的高度以及山峰 $2$ 为间峰，因此山峰 $2$ 的高度能通过平均值计算得到。

----

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

**本题采用捆绑测试**。你必须通过 Subtask 中所有的测试点才能获得该 Subtask 的分数。

- Subtask #1 (7 points)：$n \le 5$，$m \le 10$。
- Subtask #2 (13 points)：$n,m \le 100$。
- Subtask #3 (15 points)：$n,m \le 2000$。
- Subtask #4 (20 points)：$n,m \le 10^5$。
- Subtask #5 (20 points)：所有 $op = 1$ 事件在所有 $op = 2$ 事件后。
- Subtask #6 (25 points)：无特殊限制。

对于所有的数据，保证 $3 \le n \le 5 \cdot 10^5$，$1 \le m \le 5 \cdot 10^5$。


title: 青春有悔

background:
岁月奔波，已值青年的 Gnar 踏上了梦想与未来的征途。

他终失败而归。

description:
那是一次持续 $n$ 天的角逐，每天 Gnar 必须参加一场考试，受诸多因素影响第 $i$ 天 Gnar 理论得分上限为 $a_i$，实际他当天考试的得分为 $[0, a_i]$ 中**等概率随机的整数**（因时间不够、简单题丢分等）。$n$ 天后，官方将结算总分，并划定分数线，总分达到**分数线及以上**者方可入围。

无数个“凭什么”横生于脑海，似乎每天都有发挥的缺陷。“缺陷……要是能改写过往的遗憾……”

深夜，Gnar 开始了 $q$ 次幻想。每次幻想中 Gnar 重返了角逐的第 $p$ 天，以不同的状态参加考试，使当天得分变为 $[0,x]$ 中**等概率随机的整数**，其余 $n-1$ 天依旧在 $[0,a_i]$ 中随机。然而一些微妙的效应导致分数线变为了 $y$，入围的机会真能如所料高于现实吗？

请你求出每次幻想中的入围概率对 $998244353$ 取模的结果。容易证明答案可以表示为最简分数 $\frac{Q}{P}$，你输出的 $R$ 即满足 $R \cdot P \equiv Q \pmod{998244353}$ 的最小非负整数。

毕竟幻想，重返第 $p$ 天新的得分上限 $x$ 并不会改变现实 $a_p$ 的值，唯一萌生的只有对青春的悔恨。

inputFormat:
第一行包含两个正整数 $n$ 和 $q$，分别为天数和幻想次数。

第二行包含 $n$ 个整数 $a_1,a_2, \ldots ,a_n$，表示现实中每天的得分上限。

接下来$q$行，每行包含三个整数 $p,x,y$，分别为该次幻想的重返日期，新的得分上限以及新的分数线。

outputFormat: 输出 $q$ 行，每行一个整数，对应每次幻想中的入围概率对 $998244353$ 取模的结果。

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

第一次幻想，Gnar 重返了第一天，两天分别的得分情况在 $\{0,0\}$，$\{0,1\}$，$\{1,0\}$，$\{1,1\}$，$\{2,0\}$，$\{2,1\}$ 内等概率产生，其中只有后三种能够入围，故答案为 $\frac{1}{2}$。

第二次幻想，Gnar 重返了第二天，状态反而变差，即使拿满两天的得分上限也没机会入围。

----

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

**本题采用捆绑测试**。你必须通过 Subtask 中所有的测试点才能获得该 Subtask 的分数。

- Subtask #1 (10 points)：$n,q,a_i,x,y \le 100$。
- Subtask #2 (10 points)：$n,q,a_i,x,y \le 500$。
- Subtask #3 (10 points)：$a_i,x \le 1$。
- Subtask #4 (20 points)：$\sum a_i \le 10^5$。
- Subtask #5 (25 points)：$q = 1$。
- Subtask #6 (25 points)：无特殊限制。

对于所有的数据，保证 $1 \le n,q \le 10^5$，$1 \le p \le n$，$0 \le a_i,x,y \le 10^5$。


title: 交友问题

description:
洛谷上有 $n$ 位用户，这些用户组成了一个双向的网络。

洛谷的图片分享机制如下：如果第 $i$ 个用户向他的好友 $j$ 分享了一张照片，那么，$j$ 的所有好友 $k$ 就能看到这张照片。**$j$ 也可以看到这张照片。**

现在，用户 $u_i$ 想分享一张照片，但是TA不想让用户 $v_i$ 看到这张照片。在不发送给自己的情况下，TA想知道，他最多可以发送给多少位好友？

inputFormat:
第一行三个正整数 $n,m,q$，分别代表用户数，边数，询问数。

接下来 $m$ 行，每行两个数 $x_i,y_i$，表示用户 $x_i$ 与 $y_i$ 之间有一条双向边。

接下来 $q$ 行，每行两个数 $u_i,v_i$，表示第 $i$ 次询问。

outputFormat: 对于每一次询问，输出一行，包含一个数，答案。

hint:
对于 $20\%$ 的数据，满足 $1 \le n,q \le 2\times10^3$，$1\le m \le 8\times 10^3$；

对于 $60\%$ 的数据，满足 $1 \le n,q \le 2\times10^4$，$1\le m \le 5\times 10^4$；

对于 $100\%$ 的数据，满足 $1 \le n,q \le 2\times10^5$，$1\le m \le 7\times 10^5$。

**保证没有重边和自环**


title: 数上的树

background: **本题自动开启 O2 优化，时间限制 2s。**

description:
您需要构造一棵二叉树，根节点权值为 $n$，每个节点都有 $2$ 个或 $0$ 个儿子，且满足如下限制：

若该点有两个儿子，该点权值需等于两个儿子的权值之积。

若该点没有儿子，则该节点权值需为质数。

同时会给出 $m$ 条限制 $a_i$，表示树上的权值不能出现 $a_i$。

您构造的二叉树需要使：令 $k$ 为节点数， $\sum\limits_{i=1}^k\sum\limits_{j=i}^kval_{lca(i,j)}$ 最小，其中 $val_i$ 表示第 $i$ 个点的权值，$lca(i,j)$ 表示 $i,j$ 的最近公共祖先。

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

之后一行 $m$ 个数 $a_i$。

outputFormat:
一行一个数，表示最小的 $\sum\limits_{i=1}^k\sum\limits_{j=i}^kval_{lca(i,j)}$。

无解输出 `-1`。

hint:
样例解释：

样例 $1$：最优方案如下：

![](https://cdn.luogu.com.cn/upload/image_hosting/2dcec565.png?x-oss-process=image/resize,m_lfit,h_170,w_225)

其中，黑色数字代表权值，红色数字代表标号（您不需要对树标号，这里的标号只是为了更方便解释样例）。

$ans=val_{lca(1,1)}+val_{lca(1,2)}+val_{lca(1,3)}+val_{lca(2,2)}+val_{lca(2,3)}+val_{lca(3,3)}$

$~~~~~~~~=val_1+val_1+val_1+val_2+val_1+val_3$

$~~~~~~~~=4+4+4+2+4+2=20$

Subtask 1（5 分）： $n\leq 20$。

Subtask 2（12 分）：$n\leq 10^6$。

Subtask 3（28 分）：$n\leq 10^{12}$。

Subtask 4（20 分）：$m=0$。

Subtask 5（35 分）：$n\leq 10^{15}$。

对于所有数据 $2\leq n\leq 10^{15}$，$0\leq m\leq \min(n,10^5)$，$2\leq a_i\leq n$， 且答案不超过 $4\times 10^{18}$。


title: 「EZEC-5」树木的愤怒

background: 小 L 总是在卑微地被强大的人吊打，其中包括小 Y。

description:
小 L 和 小 Y 是好朋友。有一天，小 L 拿来了一棵 $n$ 个点的有权值的树。第 $u$ 个点的权值为 $a_u$。但是小 Y 讨厌树，所以二话不说直接把树上的一条边给断了。

小 L 很愤怒，但是为了保持该有礼貌，他决定做好事情后再把这条边连起来。但是，他总是操作失误，导致不但没法连起来，还会有另一条边被断掉。于是，这棵树就被分成了 $3$ 个连通块。

小 Y 看不下去了，于是在割掉边后，开始思考一个对他来说很难的问题。他想知道，在割掉第 $x$ 条边后，由于小 L 还会因为操作失误割掉一条边，则最后所形成的 **3 个连通块的权值和的乘积的所有情况的总和** 是多少。即设这三个连通块分别为 $a,b,c$，求在已经割掉一条边的情况下

$$
(\sum_{u\in a} a_u)\times (\sum_{u\in b} a_u) \times (\sum_{u\in c} a_u)
$$

的总和。

由于愤怒，每次你算好后，小 L 都会对你帮助小 Y 算出的答案不理不顾，于是小 Y 只好把图恢复到原来那棵树，再割掉一条边，你也得再帮助小 Y 算一次，即再进行一次可能不一样的询问。你需要这样帮助小 Y 一共 $q$ 次，即回答 $q$ 个询问。又因为小 L 和小 Y 都很讨厌太大的数，所以请你用输出这个总和对 $99991$ 取模的结果。又因为输出太耗费时间，你只需要输出所有询问的答案对 $99991$ 取模的总和以及异或和即可。

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

第二行 $n$ 个非负整数代表 $a_{1,2,...,n}$。

后面 $n-1$ 行中，第 $i$ 行两个正整数 $(u,v)$ 代表第 $i$ 条边 $(u,v)$。

后面 $q$ 个正整数，第 $i$ 个代表第 $i$ 次询问所割掉的边。注意，各个询问是独立的。

outputFormat:
输出一共两行。

第一行输出所有的答案对 $99991$ 取模后的和（注意，最终输出可能大于等于 $99991$）。

第二行输出所有的答案对 $99991$ 取模后的异或和。

hint:
**样例说明**

对于样例一的第一个询问。已经割掉了第一条边（即边 $(1,2)$）。若小 L 再割掉的边是 $(2,3)$，那么 3 个连通块的权值和的乘积为 $1\times 2\times (3+4)=14$。若小 L 再割掉的边是 $(3,4)$，那么 3 个连通块的权值和的乘积为 $1\times (2+3)\times 4=20$。所以输出为 $14+20=34$。

对于样例一的第二个询问。已经割掉了第二条边（即边 $(2,3)$）。若小 L 再割掉的边是 $(1,2)$，那么 3 个连通块的权值和的乘积为 $1\times 2\times (3+4)=14$。若小 L 再割掉的边是 $(3,4)$，那么 3 个连通块的权值和的乘积为 $(1+2)\times 3\times 4=36$。所以输出为 $14+36=50$。

同理，我们可以求出样例一的第三个询问，答案为 $20+36=56$。

所以三个答案的总和是 $140$，异或和是 $40$。

---
**数据规模**

$\texttt{Subtask 1 (1 pts) } a_i=0$。
$\texttt{Subtask 2 (5 pts) } n,q\le 300$。
$\texttt{Subtask 3 (14 pts) } n\le 300$。
$\texttt{Subtask 4 (20 pts) } n\le 5000$。
$\texttt{Subtask 5 (10 pts) } u=v-1$。
$\texttt{Subtask 6 (50 pts) }$ 没有特殊限制。

对于全部数据，满足 $2 \le n, q \le {10}^6$，$0 \le a_i \le {10}^6$。

---

idea by lgswdn
tested by LHQing, Karry5307


title: 『MdOI R4』Fun

background: 去 NOIP 考场时有两个优良传统：打狼和喝快乐水。这两项活动都能给同学们带来快乐。

description:
VG 的学校有 $n$ 个人要去考 NOIP。

每个人有一个交通方式，第 $i$ 个人的交通方式为 $t_i$，$t_i=1$ 表示这个人坐学校大巴，$t_i=0$ 表示这个人自己去考场。

每个人有一个颓废值，第 $i$ 个人的颓废值为 $q_i$，$q_i=1$ 表示这个人愿意打狼，$q_i=0$ 表示这个人不愿意打狼。

每个人去考场时会买一瓶快乐水，但如果坐大巴且愿意打狼的人数（即满足 $t_i=1$ 且 $q_i=1$ 的 $i$ 个数）$k$ 不小于 $m$，则这 $k$ 个人只需要买 $m$ 瓶快乐水。

现在，VG 统计出了所有人的交通方式和颓废值，他请你帮他求出最终所有人买快乐水的总瓶数。

inputFormat:
第一行三个整数 $n,m,type$。其中 $type$ 表示特殊限制编号，具体意义见数据范围。它可能可以帮助你获得部分分，但正解不依赖于此。

第二行 $n$ 个整数，第 $i$ 个整数为 $t_i$。

第三行 $n$ 个整数，第 $i$ 个整数为 $q_i$。

outputFormat: 一行一个整数，表示所有人最终买的快乐水总瓶数。


title: 「dWoi R1」Physics Problem

background: 面对白板上的物理题，王马陷入了沉思 ……

description:
有 $n$ 个状态，编号为 $1$ 到 $n$。这 $n$ 个状态之间有 $k$ 种转换关系，第 $i$ 个转换关系描述为：第 $u_i$ 个状态和第 $v_i$ 个状态可以进行转换。当两个状态之间没有直接的转换关系但有间接的转换关系时，那么这两个状态之间有升降华关系。

求有多少个升降华关系。

**王马不会做很难的物理题，所以保证一个状态一定可以通过直接或间接的转换为另一个任意状态。**

inputFormat:
第一行两个整数 $n,k$ 代表状态数和转换关系数。
接下来 $k$ 行每行两个整数 $u_i,v_i$ 代表这两个状态之间有转换关系。

outputFormat: 一行一个整数代表有多少个升降华关系。

hint:
#### 样例 1 解释

一共有 $3$ 个状态，编号为 $1,2,3$，第 $1$ 个状态和第 $2$ 个状态之间有转换关系，第 $2$ 个状态和第 $3$ 个状态之间有转换关系，第 $1$ 个状态和第 $3$ 个状态之间没有直接的转换关系，但可以用第 $2$ 个状态做桥梁进行转换，所以第 $1$ 个状态和第 $3$ 个状态之间有升降华关系。只有这一个升降华关系，输出 $1$。

#### 数据规模与约定

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

- Subtask 1（5 pts）：$n \le 2$。
- Subtask 2（10 pts）：$k=n-1$，$u_i+1=v_i$。
- Subtask 3（10 pts）：$k=n-1$，$u_i=1$。
- Subtask 4（25 pts）：$n,k \le 1000$。
- Subtask 5（50 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,k \le 10^7$，$1 \le u_i,v_i \le n$。

保证 $u_i \ne v_i$ 且不存在 $i \ne j ∧(u_i =u_j∧v_i=v_j)$ 和 $i \ne j∧(u_i=v_j∧u_j=v_i)$。

这句话也可以理解为无重边无自环。

#### 提示

注意，对于下面这种情况（`a - b` 代表 $a$ 能与 $b$ 互相转换）：

```cpp
1 - 2
2 - 3
1 - 3
```

第 $1$ 个状态和第 $3$ 个状态算有直接转换关系，即转换关系取“最短路”。


title: 简单数列

description:
给你一个数 $n$，你需要求出一个长度为 $n$ 的数组 $a$，（下标从 $1$ 开始，且元素都为 $1,2,3$ 或 $4$），使得：

* 对于第 $i$ 个数，对于所有的 $1 \le len \le \lfloor\frac{i}{2}\rfloor$, $a_{i-len+1\dots i}$ 与 $a_{i-len\times2+1\dots i-len}$ 不相同。（$\lfloor x \rfloor$ 表示对 $x$ 下取整）

* 说人话，就是没有任何连续的连续子串相同。

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

outputFormat: 一行，$n$ 个正整数，数组 $a$。

hint:
对于 $20\%$ 的数据，满足 $1 \le n \le 10$；

对于 $40\%$ 的数据，满足 $1 \le n \le 30$；

对于 $100\%$ 的数据，满足 $1 \le n \le 500$。


title: 「EZEC-5」修改数组

description:
给定一个长度为 $n$、元素由 $0$ 或 $1$ 组成的数组。

现在可以**选择若干（可以为 0）个值为 $0$ 的元素，将其修改为 $1$**。

记：

- $x$ 为数组中最长连续 $1$ 子段的长度（规定，若所有数均为 $0$，则 $x$ 为 $0$）；
- $y$ 为修改的元素的个数。

求要怎么修改才能使 $x-y$ **最大**，并构造一个方案（输出修改后的数组）。

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

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

接下来 $2\times T$ 行，每 $2$ 行表示一组数据。

在一组数据中，第一行一个整数 $n$，表示数组的长度；

第二行 $n$ 个整数（0 或 1），表示给定的数组。

outputFormat:
共 $2\times T$ 行，每 $2$ 行表示一组数据。

在一组数据中，第一行输出一个整数表示 $x-y$ 的最大值；

第二行 $n$ 个整数（0 或 1）表示修改以后的数组。**如有多个方案，任意输出一种即可。**

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

对于所有数据，保证 $T\le10,1\le n\le 10^5$，数组元素 $\in \{0,1\}$。

- Subtask 1(70 points)：保证 $1\le n\le 10$；
- Subtask 2(30 points)：无特殊限制。


title: [COCI2019-2020#1] Zoo

background:
$2010$ 年圣诞节的晚上，萨格勒布是一片雪的世界。

Zdravko 决定离开自己的城堡，并在 Maksimir 公园散步。不幸的是，一个美妙的冬夜竟被一个魔鬼所侵扰。Zdravko 将其吓走，但这声惊吓引起了动物园的骚动。更严重的是，一群老虎和公牛被逼的想要逃跑，并找一个安静的地方睡觉。

description:
在逃跑的过程中，动物们需要通过一个 $R \times C$ 的矩形区域。它们必须从这片区域的左上角进入，并从右下角离开。

为了更快地离开这里，动物们将一个接着一个地经过，并以一种随机的路径往四个方向（上、下、左、右）行走。也就是说，每一个动物并不一定选择最短路径，而且可能在同一位置停留数次（包括左上角和右下角）。

动物们每踏上一个格子，便会留下脚印。如果当前位置已经有了脚印，那么该动物会擦除当前的脚印，并留下自己的脚印。

你的任务是根据雪地脚印的情况，求出逃跑动物可能的最少数量。

inputFormat:
第一行包含题中所提到的两个整数 $R,C$。

接下来的 $R$ 行，每行有 $C$ 个字符，表示矩形的区域。其中，字符 `T` 表示老虎的脚印， `B` 表示公牛的脚印，`*` 表示没有行走痕迹的雪地。

你可以认为，至少有 $1$ 个动物经过了矩形区域，并且每个进入矩形区域的动物都最终离开了区域。

outputFormat: 输出逃跑动物可能的最少数量。

samples:
7 5
BT***
BTBBB
BTTTB
BBT*B
BBT*B
BBT**
*BBBB

hint:
#### 样例解释

下列是对第二个样例的图片解释：

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

#### 数据范围及约定

| Subtask | 分值 | 数据范围及约定 |
| :----------: | :----------: | :----------: |
| $1$ | $45$ | $2 \le R, C \le 100$ |
| $2$ | $65$ | $2 \le R, C \le 1000$ |

#### 说明

**本题分值按 COCI 原题设置，满分 $110$。**

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #1](https://hsin.hr/coci/archive/2019_2020/contest1_tasks.pdf)  _T5 Zoo_ 。**


title: Mivik 写书

background: Mivik 想当大作家。

description:
Mivik 的键盘上有 $m$ 个不同的按键，对应着 $m$ 个不同的字符。由于 Mivik 不会写文章，所以他只好**等概率**随机乱按了 $n$ 个键，打出了一篇文章。

Mivik 定义一篇文章的复杂度是这篇文章所有**非空**本质不同子串的数目。我们认为两个字符串本质不同当且仅当它们的长度不同或者它们有任意一位上的字符不同。例如，文章 `abaa` 的复杂度是 8，因为它一共有 `a`、`b`、`ab`、`ba`、`aa`、`aba`、`baa`、`abaa` 这 8 个非空的本质不同子串。

Mivik 现在想知道，这篇文章期望的复杂度是多少。由于 Mivik 不喜欢奇形怪状的小数，你只需要输出期望的复杂度对 $10^9+7$ 取模后的值。

inputFormat: 一行两个整数 $n$ 和 $m$，意义见题目描述。

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

hint:
### 样例解释

样例一：假设键盘上的字符分别为 `a` 和 `b`，那么可能打出来的文章一共有 `aa`、`ab`、`ba`、`bb` 四种，它们的复杂度分别为 2、3、3、2，因此答案为 $\frac{2+3+3+2}{4}=\frac{5}{2}$，对 $10^9+7$ 取模后得到 500000006。

### 数据范围

对于全部数据，有 $1\le n\le 20$，$1\le m\le 5\cdot 10^6$。

Subtask 1 (10 pts)：满足 $1\le n, m\le 7$。

Subtask 2 (20 pts)：满足 $1\le n\le 5$。

Subtask 3 (20 pts)：满足 $1\le n\le 10$。

Subtask 4 (50 pts)：无特殊限制。


title: Mivik 的标题

background: Mivik 现在已经写好了他的书，他现在准备给这本书起个书名去投稿。

description:
由于 Mivik 写书是乱敲键盘敲出来的，他准备对书名干同样的事情。Mivik 的键盘上有 $m$ 个不同的按键，对应着 $m$ 个不同的字符。Mivik 决定在这个键盘上**等概率**随机敲 $n$ 次敲出标题。但出于某些原因，Mivik 希望书名中要包含有一个人的名字 $S$。于是 Mivik 来问你，他随机敲出的标题有多大的概率包含有这个名字。

同样的，Mivik 并不喜欢奇形怪状的小数，所以你只需要输出这个概率对 $998244353$ 取模后的值。

inputFormat:
第一行三个整数 $n$、$m$、$|S|$，其中 $|S|$ 代表这个名字的长度。

第二行给出 $|S|$ 个整数 $a_i$，代表这个名字。

outputFormat: 一行一个整数，代表概率对 $998244353$ 取模后的值。

hint:
### 样例解释

样例一：为方便描述，我们定义键盘上两个按键为 `a` 和 `b`。那么长度为 3 的所有字符串共有 `aaa`、`aab`、`aba`、`abb`、`baa`、`bab`、`bba`、`bbb` 这 8 个，其中包含有指定名字 `aa` 的共有 `aaa`、`aab`、`baa` 这三个，则概率为 $\frac{3}{8}$，取模后得到 623902721。

### 数据范围

对于全部数据，有 $1\le |S|\le 10^5$，$|S|\le n\le |S|+10^5$，$1\le m\le 10^8$。

Subtask 1 (5 pts)：满足 $m=1$。

Subtask 2 (20 pts)：满足 $1\le n, m\le 250$。

Subtask 3 (30 pts)：满足 $1\le n, m\le 5000$。

Subtask 3 (45 pts)：无特殊限制。


title: 【模板】行列式求值

background:
模板题，无背景。

数据于 2020/12/5 更新，新增两组数据分别叉掉 [mrsrz](https://www.luogu.com.cn/user/6813) 和 [gxy001](https://www.luogu.com.cn/user/55707) 的提交。

数据于 2021/3/12 更新，新增数据叉掉 [wangrx](https://www.luogu.com.cn/user/104726) 的提交。

description: 给定一个 $n$ 阶行列式 $A$，求 $|A|$。结果对 $p$ 取模。

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

接下来共 $n$ 行，第 $i+1$ 行 $n$ 个正整数，其中第 $j$ 个表示 $A_{i,j}$。

outputFormat: 输出 $|A|$ 在模 $p$ 意义下的最小自然数值。

hint:
对于 $100\%$ 的数据，$1\le n\le 600$，$1\le a_{i,j}< 10^9+7$，$1\le p\le 10^9+7$。

存在部分测试点满足 $p$ 为素数、$\mu{(p)}\ne 0$ ，可以用于测试其他算法。~~对 CRT 能不能通过该测试点表示怀疑~~。

如果有错误做法过了可以私聊我，视情况更新数据。


title: 模法问题

background: 简单题，无背景。

description:
你有两个正整数 $a,b$。

你还有一个正整数 $q$，你要执行 $q$ 次询问。

对于每一次询问，你得到两个正整数 $l,r$。

你需要求出求 $\max\{(i \bmod a)+(i \bmod b) \}$，其中 $i$ 是正整数且 $i \in [l,r] $。

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

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

接下来 $q$ 行，每行两个正整数 $l,r$。

outputFormat: 对于每一次询问，输出一行，包含一个整数表示答案。


title: [Cnoi2021] 区间

background:
Cirno 有一个区间 $[a,b](1\le a \le b \le n)$，而你的任务是在规定的次数内帮 Rumia 猜出这个区间。

每次，你可向 Cirno 询问一个数字 $k$，而 Cirno 会告诉你这个数字与区间 $[a,b]$ 的关系。

description:
为了猜到这个区间，你需要实现一个函数 `std::pair<int,int> Guess(int n,int c)`，这个函数的作用是在不超过 $c$ 次询问中猜对 $[1,n]$ 中的一个子闭区间 $[a,b]$，返回值为你最终确定的区间，以 `std::pair<int,int>` 的形式返回。

你可以调用交互库中一个叫做 `Query` 的函数，其原型为 `int Query(int x)`，返回值为：

 - 若 $x < a$，返回 $-1$。
 - 若 $x \in [a,b]$，返回 $0$。
 - 若 $x > b$，返回 $1$。

你调用 `Query` 函数的次数不超过 $c$ 才能得到这个点的分数，否则这个点为 $0$ 分。有关该函数的调用请参考「说明/提示」部分。

在一个测试点中，你的 `Guess` 函数可能被调用多次，最多不超过 $5000$ 次。为了保证你的程序不会超时，你需要额外实现一个函数 `void init()`，这个函数只会在开始时被交互库调用一次。当然，它的实现可以为空。

由于 Rumia 的编译器只支持 C++，所以你只能使用 C++ 语言（包括 C++，C++11，C++14，C++17）来解决本题。

inputFormat: 样例中输入四个数字 $n$，$a$，$b$，$c$。这些数字你无法读取。

outputFormat: 样例中给输出三个数字 $l$，$r$，$q$。分别表示你猜的区间与 `Query` 调用测次数。这些你不用输出。

hint:
**样例解释**

需要求的区间是 $[2,3]$，区间左右端点可能的范围是 $[1,5]$，你最多猜 $5$ 次。

**数据范围与约定**

对于所有数据保证 $1 \le a \le b \le n$；除 SubtaskExtra 外，保证 $1\le n\le1500$。

**子任务**

Subtask1（$10$ points）：$c=n$。

Subtask2（$30$ points）：$c=30$。

Subtask3（$30$ points）：$c=22$。

Subtask4（$30$ points）：$c=20$。

**附加任务**

SubtaskExtra（$1$ point）：$1\le n\le 10^6$，$c=\lfloor\log_2 n\rfloor+\lfloor\log_2 \frac{4n}{3}\rfloor$。

本题使用 Special Judge，$100$ 与 $101$ 分均视作 Accepted.

**提示**

如果你不知道怎么解决交互题，可以参考[这题](https://www.luogu.com.cn/problem/P1947)。

本题模板程序与模板交互库见附件中的 `SampleProgram.cpp` 与 `SampleInteractor.cpp`。


title: 「EZEC-5」「KrOI2021」Chasse Neige

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

『我喜欢雪。』

『之前虽然讨厌寒冷，现在却是最喜欢了。』

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

description:
Rikka 给了你 $T$ 组询问，每组询问给定两个正整数 $n,k$，你需要告诉 Rikka 有多少个长度为 $n$ 的排列 $\pi$ 满足如下条件：

- $\pi_1<\pi_2$

- $\pi_{n-1}>\pi_{n}$

- 恰好存在 $k$ 个位置 $i(2\leq i\leq n-1)$ 满足 $\pi_{i-1}<\pi_{i}$ 且 $\pi_{i}>\pi_{i+1}$。

答案对 $998244353$ 取模。

inputFormat:
第一行两个整数 $T,r$，表示询问次数以及 $n$ 的值域。

接下来 $T$ 行，每行两个整数 $n,k$，意义如题意所示。

outputFormat: $T$ 行，每行一个正整数，表示答案对 $998244353$ 取模的值。


title: [ICPC2014 WF] Baggage

description:
An airline has two flights leaving at about the same time from ICPCity, one to city B and one to city A. The airline also has $n$ counters where passengers check their baggage. At each counter there is a pair of identical baggage bins, one for city B and one for city A.

Just before the flights depart, each pair of baggage bins is moved by a motorized cart to a sorting area. The cart always moves two bins at a time, one for city B and one for city A. After all the bins have been moved, they line up in the sorting area like this:

  B A B A B A ... B A

That is, there are $2n$ baggage bins in a row, starting with a bin for city B, then one for city A, and so forth. The task now is to reorder them so all the baggage bins for city A precede the baggage bins for city B. Then the bins can be loaded on the appropriate aircraft.

The reordering is done by moving pairs of adjacent baggage bins (not necessarily B then A), again via the motorized cart. For proper balance, the cart must always carry two bins, never just one. A pair of bins must always be moved to an empty space that is at least two bins wide. On the left of the first bin are some empty spaces that can be used as needed during the reordering.

When the reordering process begins, the bin locations are numbered from $1$ (initially containing the leftmost B baggage bin) to $2n$ (initially containing the rightmost A baggage bin). There are $2n$ initially empty spaces to the left of the bins, numbered from $0$ to $-2n+1$, as shown in Figure 1 for the case $n=4$.
![](https://cdn.luogu.com.cn/upload/image_hosting/fwkcv2gq.png)

   Figure 1: Initial configuration of bins and empty spaces for $n = 4$

Given $n$, find a shortest sequence of moves that will reorder the bins so that all the A bins are to the left of all the B bins. At the end of the process, it is possible that the leftmost A bin is at some location other than $1$, but the bins must be adjacent in a sequence of $2n$ locations.

inputFormat: The input consists of a single test case, which consists of the integer $n$ $(3 \leq n \leq 100)$.

outputFormat: Display a shortest sequence of moves that will correctly reorder the bins. Each move is of the form “$f$ to $t$”, where $f$ and $t$ are integers representing the movement of the bins in locations $f$ and $f + 1$ to locations $t$ and $t + 1$. If multiple solutions are possible, display any one of them.

translation:
有一无穷长的流水线 $a$，初始时 $\forall i\le0\text{ 和 } i>2n ,a_i=0$。**否则**，若 $i$ 为奇数，则 $a_i=2$；若 $i$ 为偶数，则 $a_i=1$。**也就是说，$a_i=2$ 和 $a_i=1$ 是交替出现的。**

现需要进行若干次 **如下** 操作，使得 $a$ 中的所有 **非零元素** 为 **连续** 的一段且所有的 $1$ 均在 $2$ **前面**。

选择两个位置 $p$ 和 $q$，满足 $a_p\ne0,a_{p+1}\ne0$ 且 $a_q=a_{q+1}=0$，将 $a_q$ 设为 $a_p$，$a_{q+1}$ 设为 $a_{p+1}$，并且将 $a_p$ 和 $a_{p+1}$ 均设为 $0$。**输出时将此操作表示为 ```p to q```（$p$  和 $q$ 是具体的值）**。

最小化操作步数，并输出操作序列，出题人将用 $\text{Special Judge}$ 来评判您的答案的正确性。

$\rm Translator:\;$[$\rm\color{black}h\color{red}hoppitree$](https://www.luogu.com.cn/user/183609)

hint:
Time limit: 1000 ms, Memory limit: 1048576 kB.

 International Collegiate Programming Contest (ACM-ICPC) World Finals 2014


title: [ICPC2014 WF] Buffed Buffet

description:
You are buying lunch at a buffet. A number of different dishes are available, and you can mix and match them to your heart’s desire. Some of the dishes, such as dumplings and roasted potatoes, consist of pieces of roughly equal size, and you can pick an integral number of such pieces (no splitting is allowed). Refer to these as “discrete dishes.” Other dishes, such as tzatziki or mashed potatoes, are fluid and you can pick an arbitrary real-valued amount of them. Refer to this second type as “continuous dishes.”

Of course, you like some of the dishes more than others, but how much you like a dish also depends on how much of it you have already eaten. For instance, even if you generally prefer dumplings to potatoes, you might prefer a potato over a dumpling if you have already eaten ten dumplings. To model this, each dish $i$ has an initial tastiness $t_ i$, and a rate of decay of the tastiness $\Delta t_ i$. For discrete dishes, the tastiness you experience when eating the $n^{th}$ item of the dish is $t_ i - (n-1)\Delta t_ i$. For continuous dishes, the tastiness you experience when eating an infinitesimal amount $d x$ grams of the dish after already having eaten $x$ grams is $(t_ i - x \Delta t_ i) d x$. In other words, the respective total amounts of tastiness you experience when eating $N$ items of a discrete dish or $X$ grams of a continuous dish are as follows:

$$\begin{aligned} \sum _{n=1}^{N} (t_ i - (n-1)\Delta t_ i) & &  \text {and} & & \int _{0}^ X (t_ i - x\Delta t_ i) dx  \end{aligned} $$

For simplicity, do not take into account that different dishes may or may not go well together, so define the total tastiness that you experience from a meal as the sum of the total tastinesses of the individual dishes in the meal (and the same goes for the weight of a meal – there are no food antiparticles in the buffet!).

You have spent days of painstaking research determining the numbers $t_ i$ and $\Delta t_ i$ for each of the dishes in the buffet. All that remains is to compute the maximum possible total tastiness that can be achieved in a meal of weight $w$. Better hurry up, lunch is going to be served soon!

inputFormat:
The input consists of a single test case. The first line of input consists of two integers $d$ and $w$ ($1 \le d \le {250}$ and $1 \le w \le {10\, 000}$), where $d$ is the number of different dishes at the buffet and $w$ is the desired total weight of your meal in grams.

Then follow $d$ lines, the $i^{th}$ of which describes the $i^{th}$ dish. Each dish description is in one of the following two forms:

A description of the form “D $w_ i$ $t_ i$ $\Delta t_ i$” indicates that this is a discrete dish where each item weighs $w_ i$ grams, with initial tastiness $t_ i$ and decay of tastiness $\Delta t_ i$.

A description of the form “C $t_ i$ $\Delta t_ i$” indicates that this is a continuous dish with initial tastiness $t_ i$ and decay of tastiness $\Delta t_ i$.

The numbers $w_ i$, $t_ i$, and $\Delta t_ i$ are integers satisfying $1 \le w_ i \le {10\, 000}$ and $0 \le t_ i, \Delta t_ i \le {10\, 000}$.

outputFormat: Display the maximum possible total tastiness of a meal of weight $w$ based on the available dishes. Give the answer with a relative or absolute error of at most $10^{-6}$. If it is impossible to make a meal of total weight exactly $w$ based on the available dishes, display impossible.

translation:
### 题目描述

自助餐厅里有 $n$ 种食物，分为两大类，为 “离散食物”和“连续食物”。你可以通过吃食物来获得收益。

离散食物用 $(w,t_0,\Delta t)$ 描述。对于这种食物，你只能吃整数个，每个重为 $w$。吃的第一个收益为 $t_0$，后面每吃一个收益减少 $\Delta t$。具体的，吃的第 $i$ 个这种食物 （从 $1$ 开始标号），收益为 $t_0-(i-1)\Delta t$。

连续食物用 $(t_0,\Delta t)$ 描述。对于这种食物，你可以吃任意食物的重量。如果你吃的重量为 $w$，获得的收益是 $t_0w-\dfrac{1}{2}\Delta t w^2$。

你现在要吃重量和 **恰好** 为 $W$ 的食物。最大化你的收益。

### 数据范围

$n\le 250,W\le 10000$。

对于离散食物，满足 $1\le w\le 10000$。

对于所有食物，满足 $0\le t_0,t\le 10000$。

### 输入格式

第一行是 $n,W$，接下来每行先来一个字母，如果是 C 表示连续食物，后面跟两个数表示 $t_0,\Delta t$；如果是 D 表示离散食物，后面跟三个数，表示 $w,t_0,\Delta t$。

### 输出格式

一行一个数表示答案。相对或绝对误差不超过 $1e-6$。

hint:
Time limit: 3000 ms, Memory limit: 1048576 kB.

 International Collegiate Programming Contest (ACM-ICPC) World Finals 2014


title: [ICPC2014 WF] Crane Balancing

description:
Wherever there is large-scale construction, you will find cranes that do the lifting. One hardly ever thinks about what marvelous examples of engineering cranes are: a structure of (relatively) little weight that can lift much heavier loads. But even the best-built cranes may have a limit on how much weight they can lift.

The Association of Crane Manufacturers (ACM) needs a program to compute the range of weights that a crane can lift. Since cranes are symmetric, ACM engineers have decided to consider only a cross section of each crane, which can be viewed as a polygon resting on the $x$-axis.

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

   Figure 1: Crane cross section

Figure 1 shows a cross section of the crane in the first sample input. Assume that every $1 \times 1$ unit of crane cross section weighs 1 kilogram and that the weight to be lifted will be attached at one of the polygon vertices (indicated by the arrow in Figure 1). Write a program that determines the weight range for which the crane will not topple to the left or to the right.

inputFormat: The input consists of a single test case. The test case starts with a single integer $n$ ($3 \le n \le 100$), the number of points of the polygon used to describe the crane’s shape. The following $n$ pairs of integers $x_ i, y_ i$ ($-2\, 000 \le x_ i \le 2\, 000, 0 \le y_ i \le 2\, 000$) are the coordinates of the polygon points in order. The weight is attached at the first polygon point and at least two polygon points are lying on the $x$-axis.

outputFormat: Display the weight range (in kilograms) that can be attached to the crane without the crane toppling over. If the range is $[a,b]$, display $\lfloor a \rfloor $ .. $\lceil b \rceil $. For example, if the range is $[1.5,13.3]$, display 1 .. 14. If the range is $[a,\infty )$, display $\lfloor a \rfloor $ .. inf. If the crane cannot carry any weight, display unstable instead.

translation:
无论哪里有大规模的施工，您都会发现起重机可以起重。人们几乎从未想过工程起重机的奇妙例子是什么：一种（相对）重量很小的结构，可以举起更重的负载。但即使是最好的起重机也可能对它们可以举起的重量有限制。

起重机制造商协会（ACM）需要一个程序来计算起重机可以提升的重量范围。由于起重机是对称的，ACM工程师决定只考虑每台起重机的横截面，这可以看作是一个多边形，位于x-轴。

图1显示了第一个样本输入中起重机的横截面。

假设每个1×1单位起重机横截面重1公斤，要提升的重量将附着在其中一个多边形顶点（如图1中的箭头所示）。编写一个程序，确定起重机不会向左或向右倾倒的重量范围。

输入由单个测试用例组成。测试用例以单个整数n开头,用于描述起重机形状的多边形的点数。以下n对整数是按顺序排列的点的坐标。权重附着在第一个多边形点上，并且至少有两个多边形点位于x-轴。

输出格式

显示可在起重机不倒塌的情况下连接到起重机的重量范围（以千克为单位）。如果范围是 [a,b], 显示⌊a⌋ .. ⌈b⌉. 例如，如果范围是[1.5,13.3], 显示 1 ..14. 如果范围是[a,∞), 显示⌊a⌋ .. inf. 如果起重机不能承载任何重量，请显示unstable.

说明/提示

时间限制： 1000 ms， 内存限制： 1048576 kB.

2014年国际大学生编程大赛（ACM-ICPC）世界总决赛


title: [ICPC2014 WF] Game Strategy

description:
Alice and Bob are playing a board game. The board is divided into positions labeled $a, b, c, d, \dots $ and the players use a gamepiece to mark the current position. Each round of the game consists of two steps:

Alice makes a choice. Depending on the current position, she has different options, where each option is a set of positions. Alice chooses one set $S$ among the available sets of positions.

Bob makes a choice. His choice is one position $p$ from the set $S$ that Alice chose in step 1. Bob moves the gamepiece to position $p$, which is the position for the start of the next round.

Prior to the first round, each player independently selects one of the positions and reveals it at the start of the game. Bob’s position is where the game starts. Alice wins the game if she can force Bob to move the gamepiece to the position she has chosen. To make things interesting, they have decided that Bob will pay Alice a certain amount if he loses, but Alice must pay Bob a certain amount after every round. The game now ends if Alice’s position is reached or when Alice runs out of cash.

Both Alice and Bob play optimally: Alice will always choose an option that will lead to her winning the game, if this is possible, and Bob will always try to prevent Alice from winning.

For all possible start and end positions, Alice would like you to determine whether she can win the game and if so, how many rounds it will take.

inputFormat: The input consists of a single test case. The first line contains the number of positions $n$ ($1 \leq n \leq 25$). The $n$ positions are labeled using the first $n$ letters of the English alphabet in lowercase. The rest of the test case consists of $n$ lines, one for each position $p$, in alphabetical order. The line for position $p$ contains the options available to Alice in position $p$. It starts with the number of options $m$ ($1 \leq m < 2^ n$), which is followed by $m$ distinct strings, one for each option. Each string contains the positions available to Bob if Alice chooses that option. The string has at least $1$ character, the characters (which correspond to valid board positions) are in alphabetical order, and no characters are duplicated. The total number of options for the test case is at most $10^6$.

outputFormat: For each position $p$ in alphabetical order, display one line. In that line, for each position $q$ in alphabetical order display the minimal number of rounds in which Alice can be guaranteed to arrive at position $q$ when starting the game in position $p$, or $-1$ if Alice cannot be guaranteed to reach $q$ from $p$.

translation:
### **题目描述**

Alice 和 Bob 正在玩一款棋盘游戏。棋盘被分成了标有 $a,b,c,d,...$ 的位置，玩家们使用游戏棋子来标记当前位置。游戏的每一轮包括两个步骤：

Alice 行动。根据当前位置，她有不同的选择，每个选择都是一组位置。Alice 将从可用的位置集合中选择一个集合 $S$。

Bob 行动。他的选择是集合 $S$ 中的一个位置 $p$。Bob 将游戏棋子移动到位置 $p$，这会是下一轮游戏的起始位置。

在第一轮之前，每个玩家独立选择一个位置并在游戏开始时公开位置。Bob 的位置是游戏开始的地方。如果 Alice 能够迫使 Bob 将游戏棋子移动到她选择的位置，Alice 就赢得了比赛。为了使事情更有趣，他们决定如果 Bob 输了，他将支付给 Alice 一定金额，但 Alice 必须在每轮之后向 Bob 支付一定金额。如果 Bob 到达 Alice 的位置或者 Alice 没钱了，游戏就结束了。Alice 和 Bob 都采取最佳策略：如果可能的话，Alice 总是选择会能让她赢得比赛的方案，而 Bob 总是试图阻止 Alice 获胜。对于所有可能的起始和结束位置，Alice 希望你确定她是否能够赢得比赛，如果可以，需要多少轮才能赢得比赛。

### **输入格式**

输入由单组数据组成。第一行包含位置数 $n$ $(1\le n\le 25)$，这些位置用英文小写字母的前 $n$ 个字母标记。接下来 $n$ 行，每行表示位置 $p$，按字母顺序排列。位置 $p$ 这一行包含 $Alice$ 在该位置的可选项。每行首先输入一个数 $m$ $(1 \le m < 2^n)$，后跟 $m$ 个不同字符串，每个字符串表示 Alice 选择该方案时 Bob 可移动到的位置。字符串至少包含 $1$ 个字符，这些字符（对应有效的棋盘位置）按字母顺序排列，没有重复字符。数据的方案总数最多为 $10^6$。

### **输出格式**

对于每一个 $p$ 单独输出一行。在该行中，按字母顺序输出每个位置 $q$ 表示 Alice 开始游戏时可以保证到达的最小轮次，或者如果 Alice 不能保证从 $p$ 到达 $q$，则显示 $-1$。

### **说明/提示**

时间限制： $5000$ ms，空间限制：$1048576$ kB。

来源：International Collegiate Programming Contest (ACM-ICPC) World Finals 2014

hint:
Time limit: 5000 ms, Memory limit: 1048576 kB.

 International Collegiate Programming Contest (ACM-ICPC) World Finals 2014