title: [COCI2011-2012#3] D’HONDT

background: $12$ 月初，某国举行议会选举。这个国家被分为十个选区，每个选区要选出 $14$ 名议会代表。每个选民都投票支持少数政党中的一个。投票后，选区代表用 D'Hondt 分配原理选出。

description:
某一个选区里面有 $x$ 个选民，并有 $n$ 个政党参加议会选举。运用 D'Hondt 分配原理，我们先选出选票**至少占选民总数的 $5\%$** 的政党。然后对于某一个政党的票数分别除以 $1,2,\dots,14$，并将 $14$ 个除得的**实数**作为这个政党的分数分配给这个政党。然后，我们从拥有最高得分的政党中选出第一个代表，拥有第二高得分的政党中选出第二个代表，以此类推。注意，在本题中，我们默认**选举代表的方式总是唯一的，即所有分数都不相同。**

现在，请你编写一个程序，给定选民的总数和每个政党得到的选票个数。请求出得到的选票至少占选民总数的 $5\%$ 的所有政党中，每一个政党能够选出的代表数。

inputFormat:
输入共 $n+2$ 行。

第一行一个整数 $x$，表示选民的个数。
第二行一个整数 $n$，表示参加议会选举的政党数。
随后 $n$ 行，每行一个大写字母和一个整数 $g$，分别表示政党的标识符和该政党拥有的选票数。

outputFormat:
输出若干行，每行一个大写字母和一个整数，分别代表一个得到的选票至少占选民总数的 $5\%$ 的政党的标识符和能够选出的代表数。

得到的选票至少占选民总数的 $5\%$ 的所有政党按照标识符在字母表中的位置升序排列。

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

对于 $30\%$ 的数据，保证输入中所有政党拥有的票数都至少占选民总数的 $5\%$。
对于所有数据，$1\leqslant x\leqslant 2.5\times 10^6$，$0\leqslant n\leqslant 10$，$1\leqslant g\leqslant 2.5\times 10^5$。

**【题目来源】**

本题来源自 **_[COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST 3](https://hsin.hr/coci/archive/2011_2012/contest3_tasks.pdf) T2 D'HONDT_**，按照原题数据配置，满分 $80$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2011-2012#3] POGODAK

type: P

background: Mirko 不喜欢拉丁文作业，所以他和 Slavko 打了个赌。输的人将在整个月内写他们两个人的作业。Mirko 想赢，所以他设计了这个问题用来打赌。

description:
在他的桌子上，他发现了一个立方体，如图中所示。

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

在这个立方体中，两个对立面的点数之和等于 $7$。这意味着，$6$ 在 $1$ 的对面，$5$ 在 $2$ 的对面，$4$ 在 $3$ 的对面。Mirko 将立方体放在了一个 $r\times c$ 的矩阵的左上方，最初立方体的方向是上侧显示 $1$，右侧显示 $3$。Mirko 现在依次重复以下动作：

1. 向右滚动立方体，直到它到达最后一列；
2. 向下滚动到下一行；
3. 向左滚动立方体，直到它到达第一列；
4. 像第二步一样，向下滚动到下一行。

Mirko 不停地重复这些步骤，直到立方体不能够再滚动为止。当一个立方体到达某一格时，Mirko 在这个格子中写下立方体的顶部的数字。最后他把他写的所有数字加起来。Mirko 与 Slavko 打了个赌，赌他能毫无差错地算出这个和。帮助 Slavko 算出这个和以验证 Mirko 的答案。

inputFormat: 输入仅一行，两个整数 $r,c$，分别表示矩阵的行数和列数。

outputFormat: 输出仅一行一个整数，表示最终矩阵里面填入的所有数字的和。

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

对于样例 $1$，最终矩阵里面填入的数字如下所示：

| $1$ | $4$ |
| :----------: | :----------: |
| $1$ | $5$ |
| $3$ | $5$ |

因此最终的和为 $1+4+1+5+3+5=19$。

**【数据范围】**

对于 $50\%$ 的数据，满足 $r,c\leqslant 100$。
对于所有数据，$1\leqslant r,c\leqslant 10^5$。

**【题目来源】**

本题来源自 **_[COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST 3](https://hsin.hr/coci/archive/2011_2012/contest3_tasks.pdf) T3 POGODAK_**，按照原题数据配置，满分 $100$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2011-2012#3] ROBOT

background: Mirko 创造了一个新的机器人，并决定在一个巨大的测试轨道上测试它。

description:
我们不妨把测试轨道想象成一个二维坐标系。机器人从 $(0,0)$ 开始，接收一组由 `S`、`J`、`I`、`Z` 表示的指令，每一个指令都标志着机器人应该在哪个方向移动。具体地，如果机器人当前位于 $(x,y)$：

- 指令 `S` 意味着它应该移动到 $(x,y+1)$。
- 指令 `J` 意味着它应该移动到 $(x,y-1)$。
- 指令 `I` 意味着它应该移动到 $(x+1,y)$。
- 指令 `Z` 意味着它应该移动到 $(x-1,y)$。

当机器人接受指令并在测试轨道上移动时，Mirko 以下列方式验证其位置：

测试轨道上有 $n$ 个固定的控制点，每个控制点都会测量与机器人的**曼哈顿距离**，并将所有距离的和发送给 Mirko。假设机器人完全按照指令移动，请你计算执行每条指令后所有控制点距离机器人的曼哈顿距离之和。

inputFormat:
输入共 $n+2$ 行。

第一行，两个整数 $n,m$，分别表示控制点的数量和指令的数量。
第 $2\sim n+1$ 行，每行两个整数 $(x_i,y_i)$，分别表示每个控制点的横坐标和纵坐标。
第 $n+2$ 行一个长度为 $m$ 的字符串，表示机器人将接收到的指令。

outputFormat: 输出共 $m$ 行，每行一个整数，表示执行每条指令后所有控制点距离机器人的曼哈顿距离之和。

hint:
**【前置知识】**

- 曼哈顿距离：设有两个点 $(a,b)$ 和 $(c,d)$，则这两个点的曼哈顿距离为 $|a-c|+|b-d|$。

**【数据范围】**

对于所有数据，$1\leqslant n\leqslant 10^5$，$1\leqslant m\leqslant 3\times 10^5$，$|x_i|,|y_i|\leqslant 10^6$，指令仅包含 `S`、`I`、`J`、`Z` 四个字符中的一个。

**【题目来源】**

本题来源自 **_[COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST 3](https://hsin.hr/coci/archive/2011_2012/contest3_tasks.pdf) T4 ROBOT_**，按照原题数据配置，满分 $120$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2011-2012#3] PLAĆE

background: Mirko 喜欢汽车，他终于成功地开办了自己的汽车工厂。

description: 工厂有 $n$ 个员工，每个人都有一个上司（除了 Mirko 默认为每个人的上司）。Mirko 用 $1$ 号表示，其余员工用 $2\sim n$ 号表示。每个员工都可以提高或降低他所有下属（包括直接下属和等级树上的下属）的工资。Mirko 的职责是防止这种权力的滥用，所以他不时地想知道某个雇员的工资。他要求你写一个程序，给定一系列命令（见输入格式部分），帮助他监控工资的变化。注意：在任何时候，所有的工资都是正整数，并适合于标准的 $32$ 位整数类型（C/C++ 中的 `int`，Pascal 中的 `longint`）。

inputFormat:
输入共 $n+m+1$ 行。

第一行，两个整数 $n,m$，分别表示员工的总数和指令的个数。
第 $2\sim n+1$ 行，第 $i$ 行两个整数分别表示第 $i-1$ 号员工的初始工资和他的直属上司（注意，Mirko 并没有上司，因此输入他的信息的那一行仅输入他的初始工资）。
第 $n+2\sim n+m+1$ 行，每行先输入一个字符表示命令类型，接下来的输入如下所述：

- 如果字符为 `p`，接下来两个整数 $a,x$，表示员工 $a$ 将它的所有下属（包括**直系下属**和**他能够间接控制到的所有下属**）的工资变化了 $x$。
- 如果字符为 `u`，接下来仅一个整数 $a$，表示 Mirko 想知道员工 $a$ 的工资。

outputFormat: 对于每一个 `u` 操作，输出一行一个整数，表示被询问的员工的工资。

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

对于所有数据，$1\leqslant n,m\leqslant 5\times 10^5$，$1\leqslant a\leqslant n$，$-10^4\leqslant x\leqslant 10^4$。

**【题目来源】**

本题来源自 **_[COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST 3](https://hsin.hr/coci/archive/2011_2012/contest3_tasks.pdf) T5 PLAĆE_**，按照原题数据配置，满分 $140$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2011-2012#3] TRAKA

description:
Mirko 的工厂里面有 $n$ 个工人。他们以流水线方式在传送带上制造汽车。工人从左往右编号为 $1\sim n$，其中工人 $1$ 即为 Mirko。汽车生产从工人 $1$（Mirko）开始，在他完成所有他的工作后，工人 $2$ 接手他的任务。之后工人 $3$ 再接手工人 $2$ 的任务，以此类推。当工人 $n$ 完成他的工作后，一辆汽车就生产完成了。

Mirko 和他的工人们必须生产 $m$ 辆汽车，且必须按 $1\sim m$ 的顺序生产。对于第 $i$ 个工人，他完成他的工作的时间为 $t_i$。对于第 $j$ 辆汽车，它装配的复杂度为 $f_j$。工人 $i$ 在汽车 $j$ 上完成他的工作所需时间为 $t_i\cdot f_j$。

根据公司政策，一个工人完成他的工作后，他必须立即将工作交给下一个工人，不得拖延。因此，下一个工人此时不能够在其他汽车上工作。为了满足这个条件，Mirko 必须等到一个好的时机开始制造一辆新车。为了提高效率，他将等待最少的时间，直到他确定能够满足所有条件。

编写一个程序，给定每个工人完成他的工作的时间和每辆车装配的复杂度，求生产所有汽车所需的总时间。

inputFormat:
输入共 $n+m+2$ 行。

第一行，两个整数 $n,m$，分别代表工人的个数和需要生产的汽车的辆数。
随后 $n$ 行，每行一个整数 $t_i$，表示第 $i$ 个工人完成他的工作的时间。
随后 $m$ 行，每行一个整数 $f_j$，表示第 $j$ 辆车装配的复杂度。

outputFormat: 输出仅一行一个整数，表示生产所有汽车所需的总时间。

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

对于样例 $1$，$4$ 个单位的时间后，工人 $1$ 完成了第一辆车的工作。他可能会立即开始在第二辆车上工作，但这违反了汽车必须在完成后立即传递给下一个工人的条件（$7$ 个单位的时间后第二个工人将完成他在第二辆车上的工作，但是第三个工人不能接手，因为他仍然在第一辆车上工作）。因此，第二辆车在 $5$ 个单位的时间后才能开始生产。$7$ 个单位的时间后开始生产第三辆汽车。第一辆车在 $8$ 个单位的时间后完成，第二辆车在 $9$ 个单位的时间后完成，第三辆车在 $11$ 个单位的时间后完成。因此总时间是 $11$。

**【数据范围】**

对于 $40\%$ 的数据，满足 $n,m\leqslant 1000$。
对于所有数据，$1\leqslant n,m\leqslant 10^5$，$1\leqslant t_i,f_j\leqslant 10^4$。

**【题目来源】**

本题来源自 **_[COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST 3](https://hsin.hr/coci/archive/2011_2012/contest3_tasks.pdf) T6 TRAKA_**，按照原题数据配置，满分 $160$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [Ynoi2077] 3dmq

background:
这道题是 2077 年的 Ynoi 题，在 2077 年 77 岁的老爷爷 Ynoi 出题人无药可救，把数据范围开大了 $10^{100}$ 倍卡掉了所有高复杂度的算法。

2076 年，苏联自觉已经无法与盟军势力抗衡，末代领导人夫尔巴乔戈发动了对盟军的战争，他们幻想着像 80 年代的军事演习一样，先核弹开路，再钢铁洪流，在一周内将红旗插遍英吉利海峡，然而苏联的科技进步缓慢，在 2076 年，苏军动员兵还在使用波波沙冲锋枪，引以为傲的天启坦克也不敌盟军新开发出的光棱坦克......

在战败后，夫尔巴乔戈被民众吊在了路灯上继续发光发热，很快于 2077 年红旗落地，曾经庞然大物的苏联解体了。战争的刺激导致盟军开发出了大量的新科技，为了对付苏联人的核弹，盟军一直在秘密研发超时空传送仪，盟军利用超时空传送装置进行了很多随机传送测试，在一场测试中，一位前苏联的间谍突然开枪打死了实验的工程师，牺牲自己，将这道题传送到了 2021 年。这道题的意义极其重大，因为超时空传送本质上就是对高维空间的修改查询，能理解高维空间修改查询就能实现超时空传送！

2021 年的苏联科学家接收到他们在 2077 年战败后苏联解体的消息，他们的心中充满了对无名英雄的敬佩以及对未来世界的恐慌，然而当 2021 年的苏联人解密来自 2077 年的信息后，他们惊恐地发现现有的评测机不能支持如此大规模的评测，所以只能开小数据范围。欢迎大家考虑使用高复杂度的算法来通过此题，来帮助苏联人打败盟军。

description:
给定一个三维空间上 $n$ 个点，每个点有坐标 $X,Y,Z$，权值 $a,b$，$b$ 初始为 $0$。

有 $m$ 个操作：

`x y z w`：求所有 $X_i\le x,Y_i\le y,Z_i\le z$ 的 $i$ 的 $b_i$ 的和，求和结束后，将所有 $X_i\le x,Y_i\le y,Z_i\le z$ 的点 $i$，其 $b$ 权值加上 $a_i\times w$。

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

之后 $n$ 行，每行四个数 $X,Y,Z,a$ 意义如上述。

之后 $m$ 行，每行四个数 $x,y,z,w$，意义如上述。

outputFormat:
对每个操作，输出一行一个数表示答案。

由于答案可能很大，所以只需要输出答案对 $2^{64}$ 取模的结果即可。

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

对于 $100\%$ 的数据，满足 $1\le n,m\le 5\times 10^5$，初始点集以及权值为均匀随机生成，$X,Y,Z$ 为 $1$ 到 $n$ 的排列，$0\le a,w\le n$，操作为均匀随机生成，每次操作有 $0.8$ 的概率其 $w$ 为 $0$。

本题按照你的程序正确回答的询问个数给分，若你的程序正确回答了前 $x$ 个询问，若 $2x\le m$，你将得到 $\lfloor\frac{100x}{m}\rfloor\%$ 的分数，否则你将得到 $\lfloor50+50\times(\frac{2x-m}{m})^2\rfloor\%$ 的分数。spj 将会在读取到第一个错误的答案或读取到输出末尾或读取完前 $m$ 行时终止读取，之后的信息将被忽略，请勿在行末添加空格。

**注意：若你的程序 TLE，你将会得到 0 分。**


title: [CoE R4 E] 伪随机

description:
很久很久以前，小明生成了一些数据。

他的数据生成器使用了以下两个函数生成随机数：

```plain
定义函数 srand(32 位无符号整数 seed)
	将 x 赋值为 seed

定义函数 rand()
	将 x 赋值为 x 异或 (x 左移 13 位)
	将 x 赋值为 x 异或 (x 右移 17 位)
	将 x 赋值为 x 异或 (x 左移 5 位)
	返回 x
```

小明在调用 $\text{srand(seed)}$ 后，连续调用了 $n$ 次 $\text{rand()}$，并且记录下了每次 $\text{rand()}$ 的返回值对 $p$ 取模时得到的余数 $a_i$。

很久很久以后，只有数据生成器依然残存（实现见下发文件的 `generator.cpp`），但生成器的参数 $\text{seed}$ 和 $p$ 已经消失。

小明想要从数据中恢复这两个参数。即给定序列 $a_i$，需要找到任意一组 $\text{seed}$ 和 $p$ 的可能的值。你能帮帮他吗？

---

**简要描述**

小明的数据生成器是下发文件的 `generator.cpp`。你需要根据生成器的输出，反推出生成器的输入。

inputFormat:
输入的第一行包含一个整数 $n$。

第二行包含 $n$ 个 $32$ 位无符号整数 $a_1, a_2, \cdots, a_n$，为小明生成的数据。

outputFormat:
输出仅包含两个 $32$ 位无符号整数 $\text{seed}$ 和 $p$，为你的答案。你需要保证 $0 < \text{seed}, p < 2^{32}$。

如果有多组解，你可以输出任意一组。

samples:
见下发文件的 sample.in
见下发文件的 sample.out

hint:
### 数据规模

本题共有 $50$ 个测试点，每个测试点 $2$ 分。

对于所有数据，保证 $n = 10^5$，$\text{seed}$ 是随机选取的，且至少存在一组解。


title: [COCI2012-2013#3] SAHOVNICA

background: Mirko 已经成为一个铁杆爱国者，所以他要求你给他画一个克罗地亚棋盘。

description: 棋盘由红色格子和白色格子组成。棋盘左上角的格子是红色。其余的格子在棋盘中交替显示成白色和红色。我们在本题中用 `X` 表示红色区域，用 `.` 表示白色区域。Mirko 的棋盘应该由 $r\times c$ 的格子组成，并且每个格子是由字符 `X` 和 `.` 组成的 $a\times b$ 的字符矩阵。请你帮助他画出这个棋盘。

inputFormat:
输入共两行。

第一行两个整数 $r,c$，分别表示棋盘的行数和列数。
第二行两个整数 $a,b$，分别表示每个格子中的字符矩阵行数和列数。

outputFormat: 输出共 $r\times a$ 行，每行 $c\times b$ 个字符，描述最终画出来的棋盘。

samples:
XXX...XXX...XXX
XXX...XXX...XXX
...XXX...XXX...
...XXX...XXX...
XXX...XXX...XXX
XXX...XXX...XXX
...XXX...XXX...
...XXX...XXX...
XXX...XXX...XXX
XXX...XXX...XXX

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

对于所有数据，$1\leqslant r,c,a,b\leqslant 10$。

**【题目来源】**

本题来源自 **_[COCI 2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST 3](https://hsin.hr/coci/archive/2012_2013/contest3_tasks.pdf) T1 SAHOVNICA_**，按照原题数据配置，满分 $50$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2012-2013#3] POREDAK

background:
Mirko-wan 刚刚收到历史考试的成绩。其中一个问题是把著名的历史事件按时间顺序排列。正确的顺序是：

1. _Blockade of Naboo_
2. _Battle of Geonosis_
3. _Battle of Yavin_
4. _Battle of Hoth_
5. _Battle of Endor_

Mirko-wan 相对地用功备考，所以除了 _Blockade of Naboo_ 外，他记得所有事件的确切年份。他对于 _Blockade of Naboo_ 什么都不记得了，所以他随机把它放在最后而不是第一个，得到的顺序是：

1. _Battle of Geonosis_
2. _Battle of Yavin_
3. _Battle of Hoth_
4. _Battle of Endor_
5. _Blockade of Naboo_

由于 Mirko-wan 的顺序在任何指标上都不符合正确的解决方案，尽管他知道五分之四的正确顺序，但令他失望的是，他在这个问题上的得分是 $5$ 分中的 $0$ 分！这就引出了公平评分问题。

description:
上面给出的例子表明，通过计算正确绝对位置的项目数来得分是不公平的。有更好的方法吗？一种可能是找到正确排序的项目的最长子序列（不一定是连续的）。这也不是最好的解决方案：如果一个项目从正确的顺序中只被替换了一个位置，那么尽管排序几乎正确，它的分数就会降到零。Mirko-wan 因此向他的历史老师建议以下评分方法：

对于 $n$ 个条目中的每两个条目，如果两个条目的顺序相互正确，学生将得到 $1$ 分。换句话说，分数是学生正确排列的条目对的数目。当然，最大分数是条目对的总数，等于 $\dfrac{n(n-1)}{2}$。

请你通过这种方法，给定 $n$ 个条目的正确顺序和 Mirko-wan 给出的顺序，求出 Mirko-wan 可以得到的分数。

inputFormat:
输入共三行。

第一行一个整数 $n$，表示条目的个数。
第二行 $n$ 个字符串，表示 $n$ 个条目的正确顺序。
第三行 $n$ 个字符串，表示 Mirko-wan 给出的 $n$ 个条目的顺序。

outputFormat:
输出格式为 `a/b`，其中：

- $a $ 表示 Mirko-wan 按照输入给定顺序和新的计算得分的方式可以得到的分数。
- $b$ 表示按照新的计算得分的方式最大可以得到的分数。

请注意，在本题中，请**不要对答案进行约分**。

samples:
5
naboo geonosis yavin hoth endor
geonosis yavin hoth endor naboo

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

对于样例 $1$，能够使 Mirko-wan 得到分数的条目对为 $(\texttt{alpha},\texttt{beta})$ 和 $(\texttt{alpha},\texttt{gamma})$。

**【数据范围】**

对于所有数据，$2\leqslant n\leqslant 2500$。字符串的长度在 $[3,15]$ 之间，仅包含小写英文字母且所有条目是互不相同的。

**【题目来源】**

本题来源自 **_[COCI 2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST 3](https://hsin.hr/coci/archive/2012_2013/contest3_tasks.pdf) T2 POREDAK_**，按照原题数据配置，满分 $80$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: 「RdOI R3」学习算法

background: 暑假中，MLE 决定学习一下 OI 算法。

description:
暑假一共有 $n$ 天，我们假设 MLE 每天都有足够的时间学 OI。MLE 列出了可供选择的 $m$ 个算法。MLE 每天只能且必须学习一个算法。

而且，MLE 长时间学同一种算法会厌倦，所以每一种算法不能连续学习太多天，第 $i$ 种算法最多可以连续学习 $a_i$ 天。**MLE 没有必要学习全部的算法。**

MLE 想知道，自己有多少种不同的学习安排来度过这 $n$ 天。两种学习安排不同仅当这两种安排中有至少一天学习的算法不同。因为方法可能过多，你只需要输出方案数对 $10^9+7$ 取模即可。

inputFormat:
第一行为两个整数 $n,m$。
第二行 $m$ 个整数 $a_1,a_2,\cdots,a_m$。

outputFormat: 输出一行一个整数，方案数对 $10^9+7$ 取模的结果。


title: [COCI2013-2014#2] VOLIM

background: 本游戏改编自克罗地亚电视节目《我爱克罗地亚》中的游戏 _I love my country_。

description:
有 $8$ 个人坐成一圈，如图所示。

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

他们中的某一个人会拿着一个箱子，这个箱子会在比赛开始后 $210$ 秒爆炸。

主持人会问拿箱人问题，拿箱人可以选择以下方式：

- 若跳过或回答错误，主持人会接着问下一个问题。
- 若回答正确，则拿箱人把箱子传递给他**左手边**第一个人，这个人成为新的拿箱人。

现在你知道对于每个问题，回答该问题的人所用的时间与回答情况。

给定游戏开始时拿箱人的编号与问题的数量，求出箱子爆炸时拿箱人的编号。

箱子传递时间与两个问题之间的时间**忽略不计**，数据保证箱子爆炸时箱子在某个人手上，且问题没有问完。

inputFormat:
第一行一个整数 $K$，表示游戏开始时拿箱人的编号。

第二行一个整数 $N$，表示问题的数量。

接下来 $N$ 行，每行有一个整数 $T$ 与一个字符，表示回答该问题的人所用的时间与回答情况：

- 该字符为 $\tt T$，表示回答正确。
- 该字符为 $\tt N$，表示回答错误。
- 该字符为 $\tt P$，表示跳过。

outputFormat: 仅一行一个整数，即箱子爆炸时拿箱人的编号。

hint:
#### 数据规模与约定

对于 $100\%$ 的数据，有 $1\le K\le 8$，$1\le N,T\le 100$。

#### 来源

**本题译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 2](https://hsin.hr/coci/archive/2013_2014/contest2_tasks.pdf) _T1 VOLIM_。**

按照原题数据配置，本题满分 $50$ 分。


title: [COCI2013-2014#2] MISA

description:
一个 $R\times S$ 的方格，每个人坐在一个方格中，可能存在空位。

每个人都会与自己周围的**八个方格**中的人握手（可能不满 $8$ 人）。

Mirko 是最晚到场的，他按照如下的方式就坐：

- 若有空位，他会坐在一个能使他能与最多的人握手的空位上。
- 若没有空位，他会离开。

求出 Mirko 就坐后人们的握手次数。

inputFormat:
第一行两个整数 $R,S$。

接下来一个 $R$ 行 $S$ 列的字符矩阵，描述就坐情况：

- `.` 表示空位。
- `o` 表示有人入座。

outputFormat: 仅一行一个整数，即 Mirko 就坐后人们的握手次数。

hint:
#### 样例 1 说明

```plain
..o
oo.
```

是满足要求的一种最终就坐方式。

#### 数据规模与约定

- 对于 $20\%$ 的数据，有 $R=1$。
- 对于另外 $20\%$ 的数据，有 $R=2$。
- 对于另外 $20\%$ 的数据，座位坐满了。
- 对于 $100\%$ 的数据，有 $1\le R,S\le 50$。

#### 来源

**本题译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 2](https://hsin.hr/coci/archive/2013_2014/contest2_tasks.pdf) _T2 MISA_。**

按照原题数据配置，本题满分 $80$ 分。


title: [COCI2013-2014#2] SLOM

description:
Martin 眼睛出问题了。

对于一个单词，他每次眨眼，在他眼中这个单词的字母便会发生如下的变化（下述「倒数第 $k$ 个」「第 $k$ 个」等都是对于**变化前**的单词而言的）：

- 最后一个字母移动到第 $1,2$ 个字母之间。
- 倒数第二个字母移动到第 $2,3$ 个字母之间。
- $\ldots\ \ldots$
- 倒数第 $k$ 个字母移动到第 $k,k+1$ 个字母之间。

例如，单词 $\tt abcdef$ 在他眨眼后会变成 $\tt afbecd$。

如果 Martin 再次眨眼后，相同的事情仍会发生。

给定 Martin 眨眼的次数 $X$ 和他看到的单词 $s$，求出原本的单词。

inputFormat:
第一行一个整数 $X$，表示 Martin 眨眼的次数。

第二行一个字符串 $s$，表示 Martin 看到的单词。

outputFormat: 仅一行一个字符串，即原本的单词。

hint:
#### 样例 1 说明

变化过程为：$\tt abcdef\to afbecd\to adfcbe\to aedbfc\to acefdb$。

#### 数据规模与约定

- 对于 $50\%$ 的数据，有 $1\le X\le 100$。
- 对于 $100\%$ 的数据，有 $1\le X\le 10^9$，$3\le |s|\le 10^3$。

#### 来源

**本题译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 2](https://hsin.hr/coci/archive/2013_2014/contest2_tasks.pdf) _T3 SLOM_。**

按照原题数据配置，本题满分 $100$ 分。


title: [COCI2013-2014#2] PUTNIK

description:
销售员 Sept 有一个任务，即游览 $N$ 座城市（从 $1$ 到 $N$ 编号），每座城市只能游览**恰好一次**。

这 $N$ 座城市中，每两座之间都有一列航班。Sept 追求效率，所以他希望在飞行上消耗的时间最少。为此，他可以调整这些城市的游览顺序。

但 Sept 对这个游览顺序有一个奇怪的要求：

- 对于城市 $1$ 没有要求。
- 如果要游览城市 $K(K\in[2,N])$，则所有编号小于 $K$ 的城市，要么都在游览城市 $K$ 前游览完，要么都在游览城市 $K$ 后游览完。\
  换句话说，对于两个城市 $X,Y(1\le X,Y< K)$，不能在城市 $K$ 前游览城市 $X$ 而在城市 $K$ 后游览城市 $Y$。

在这些限制下，给定每两座城市之间乘坐航班所需的时间，求出 Sept 在飞行上消耗的最少时间。

inputFormat:
第一行一个整数 $N$，即城市的数量。

接下来 $N$ 行 $N$ 列整数。我们令 $(A,B)$ 表示第 $A$ 行的第 $B$ 个数，则有

- $(A,B)$ 表示城市 $A,B$ 之间乘坐航班所需的时间。
- 若 $A=B$，$(A,B)=0$。
- $(A,B)=(B,A)$。

outputFormat: 仅一行一个整数，即 Sept 在飞行上消耗的最少时间。

hint:
#### 样例 1 说明

顺序 $\tt2,1,3$ 或 $\tt3,1,2$ 都是可以的。

注意到 $\tt1,3,2$ 用时更短，但不符合 Sept 的奇怪要求。

#### 样例 2 说明

顺序 $\tt3,1,2,4$ 或 $\tt4,2,1,3$ 都是可以的。

#### 数据规模与约定

**本题不采用捆绑测试，在评测中也不会体现 Subtask。**

- Subtask 1 $\tt(40pts)$：$2\le N\le 10$。
- Subtask 2 $\tt(20pts)$：$2\le N\le 20$。
- Subtask 3 $\tt(60pts)$：无特殊限制。

对于 $100\%$ 的数据，有 $2\le N\le 1500$，$0\le (A,B)\le 10^3$。

#### 来源

**本题译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 2](https://hsin.hr/coci/archive/2013_2014/contest2_tasks.pdf) _T4 PUTNIK_。**

按照原题数据配置，本题满分 $120$ 分。


title: [COCI2013-2014#2] PALETA

description:
Mirko 有 $k$ 种颜色和 $n$ 个图像需要上色。图像编号从 $1$ 到 $n$，他决定用 $k$ 种颜色中的一种来填充每个图像。

为此，他选择了 $n$ 个数字 $f_i$，并决定按照如下方法涂色：

- 若 $f_i\ne i$，则图像 $i$ 与图像 $f_i$ 的颜色不应该相同。
- 若 $f_i=i$，他可以在满足所有其他条件的基础上，将图像 $f_i$ 涂成任何颜色。

你需要求出上色的可能方法的数量。

**由于输出可能非常大，你只需要输出答案对 $\bm{10^9+7}$ 取模后的结果。**

inputFormat:
第一行两个整数 $n,k$，表示图像的数量与颜色的数量。

接下来 $n$ 行，即 $f_i$。

outputFormat: 仅一行一个整数，即给书着色的可能方法的数量对 $10^9+7$ 取模后的结果。

hint:
#### 样例 1 说明

共有 $3$ 种颜色，并且图像 2 的颜色不能与图像 1 相同。可能的上色方案为 $(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)$，其中括号中两个数字分别表示两个图像的颜色。

#### 样例 4 说明

共有 $4$ 种颜色。

- 对于图像 1，可以涂成任何颜色。
- 对于图像 2，颜色不能与图像 1 相同。
- 对于图像 3，颜色不能与图像 2 相同。

即图像 2 可以用除了图象 1 外的 $3$ 种颜色着色，图像 3 可以用除了图象 2 外的 $3$ 种颜色着色。

答案为 $4\times 3\times 3=36$。

#### 数据规模与约定

- 对于 $50\%$ 的数据，有 $f_i\ne f_j(1\le i\ne j\le n)$。
- 对于 $100\%$ 的数据，有 $1\le n,k\le 10^6$。

对于所有合法的 $f_i$，有 $1\le f_i\le n$。

#### 来源

**本题译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 2](https://hsin.hr/coci/archive/2013_2014/contest2_tasks.pdf) _T5 PALETA_。**

按照原题数据配置，本题满分 $140$ 分。


title: [COCI2013-2014#2] LINIJE

background: Mirko 和他忠实的朋友 Slavko 有一天真的很无聊，于是他们创造了一个新游戏。

description:
在游戏开始时，他们在一个坐标系中绘制 $N$ 个点。

玩家轮流操作，Mirko 先操作。他画一条平行于坐标系的一个轴的直线 $l_1$，并通过 $N$ 个点之一。

在第 $i(i\ge2)$ 次操作中，玩家画一条直线 $l_i$，该直线平行于坐标系的一个轴，并通过位于 $l_{i-1}$ 的 $N$ 个点之一。

**不能画两条重合的直线。**

失败者是不能继续操作的玩家。

给定这 $N$ 个点的坐标，确定谁有必胜策略。

inputFormat:
第一行一个整数 $N$，表示点的数量。

接下来 $N$ 行，每行两个整数 $X,Y$，表示该点的坐标。

outputFormat: 仅一行一个字符串，即有必胜策略的人的名字，$\tt Mirko$ 或是 $\tt Slavko$。

hint:
#### 样例 1 说明

- 如果 Mirko 画线 $y=1$ 经过点 $(1,1)$，Slavko 必须画 $x=1$ 经过 $(1,1)$，此外，该直线还同时经过 $(1,2)$。
- 然后 Mirko 画线 $y=2$ 经过 $(1,2)$，Slavko 剩下的唯一一步是再次画 $x=1$，这是不允许的。
- Mirko 必胜。

#### 数据规模与约定

**为了方便判分，本题判分方法比较特殊。**

本题共 $40$ 个测试点，

- 其中 $16$ 个测试点满足 $1\le N\le 10$。
- 其他 $24$ 个测试点无特殊限制。
- 前 $20$ 个测试点一个 $4$ 分。
- 后 $20$ 个测试点一个 $8$ 分。

对于 $100\%$ 的数据，有 $1\le N\le 10^4$，$1\le X,Y\le 500$。

#### 来源

**本题译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 2](https://hsin.hr/coci/archive/2013_2014/contest2_tasks.pdf) _T6 LINIJE_。**

按照原题数据配置，本题满分 $160$ 分。


title: [COCI2012-2013#3] MALCOLM

background: 自从 Herkabe 老师开始对他的学生进行排名以来，他班上的朋友对数急剧下降。排名靠后的学生已经开始嫉妒排名靠前的学生，而排名靠前的学生则开始看不起那些排名靠后的学生。

description:
根据 Malcolm 的观察，班上一共有 $n$ 名学生。如果两个学生的排名**最多相差 $k$**，那么他们就是**朋友**。如果有两个学生是**朋友**并且它们的名字长度相等，那么他们就是**好朋友**。

现在给定这个班上 $n$ 名学生的名字及排名，求这个班上一共有多少对**好朋友**。

inputFormat:
输入共 $n+1$ 行。

第一行，两个整数 $n,k$，分别表示班上的学生人数和朋友的排名之间最多相差的名次。
随后 $n$ 行，第 $i+1$ 行一个字符串，表示在班上排第 $i$ 名的学生的名字。

outputFormat: 输出仅一行一个整数，表示班上**好朋友**的对数。

samples:
6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

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

对于所有数据，$3\leqslant n\leqslant 3\times 10^5$，$1\leqslant k\leqslant n$，字符串的长度在 $[2,20]$ 之间且仅包含大写英文字母。

**【题目来源】**

本题来源自 **_[COCI 2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST 3](https://hsin.hr/coci/archive/2012_2013/contest3_tasks.pdf) T3 MALCOLM_**，按照原题数据配置，满分 $100$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2012-2013#3] AERODROM

description:
由 $m$ 人组成的某国代表团正前往澳大利亚参加 2013 年的 IOI。他们目前正在机场排队等候办理登机手续。有 $n$ 个办理登机手续的服务台开放。一些官员的工作效率比其他官员高，所以服务台的运作速度不同。在第 $k$ 个服务台，完成一名乘客的登机手续需要 $t_k$ 秒，而我们的代表团成员恰好知道确切的数字。在开始时，所有的服务都做好接受下一名乘客的准备，而现在只允许我们的代表团成员排队。一个人只有在所有排在他前面的人都已经离开队列（**开始办理登机手续，不一定要完成**）时，才能占据一个可用的服务台开始办理登机手续。这时，这个人可以立即占据一张空闲的服务台（如果有的话），但也可以选择等待另一个办理登记手续更快的服务台变成空闲。

我们的代表团成员是计算机科学怪才，他们决定让他们所有人都尽快完成签到，你的任务是找到完成签到所需要花费的最短时间。

inputFormat:
输入共 $n+1$ 行。

第一行两个整数 $n,m$，分别表示服务台的个数和代表团的人数。
随后 $n$ 行，每行一个整数 $t_k$，表示第 $k$ 个服务台办理一名乘客的登记手续需要花费的时间。

outputFormat: 输出仅一行一个整数，表示完成签到所需要花费的最短时间（单位为秒）。

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

对于样例 $1$，有两个服务台，处理时间分别为 $7$ 秒和 $10$ 秒。在代表团的六个人中，前两个人立即占据了这两个服务台。在第 $7$ 秒，第一张桌子变成空闲，第三个人占据了它。在第 $10$ 秒，第四个人占据了第二个服务台。在第 $14$ 秒，第五个人占据了第一个服务台。在第 $20$ 秒，第二张桌子再次变成空闲，但第六个人决定再等一秒钟（至第 $21$ 秒），让第一张桌子空出来，然后占据它。这样一来，签到只要花费 $28$ 秒就能完成了。如果第六个人没有等待更快的服务台，签到将花费 $30$ 秒。

**【数据范围】**

本题一共 $8$ 个测试点。各个测试点的数据范围如下表所示：

| 测试点编号 | $n\leqslant$ | $m\leqslant$ | $t_k\leqslant $ |
| :-----------: | :-----------: | :-----------: | :-----------: |
| $1\sim 5$ | $10^5$ | $3\times 10^5$ | $10^9$ |
| $6\sim 8$ | $10^5$ | $10^9$ | $10^9$ |

**【题目来源】**

本题来源自 **_[COCI 2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST 3](https://hsin.hr/coci/archive/2012_2013/contest3_tasks.pdf) T4 AERODROM_**，按照原题数据配置，满分 $120$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2012-2013#3] HERKABE

background: Herkabe 老师决定再次对他的学生进行排名。

description:
这一次，Herkabe 老师希望他的排行榜在审美上也是令人愉快的，所以他决定有相同前缀的名字必须在名单上彼此相邻。因此，他制定了一个规定：**对于名单上每两个有相同前缀的名字，在排行榜上他们之间的所有名字也应当有这一个前缀**。

现在，给定 $n$ 个学生的名字，求 Herkabe 老师能制作出多少个不同的排行榜以满足上述规则。由于结果可能很大，你只需要输出这个答案对 $10^9+7$ 取模的结果。

inputFormat:
输入共 $n+1$ 行。

第一行一个整数 $n$，表示学生的个数。
随后 $n$ 行，每行一个字符串，表示每个学生的名字。

outputFormat: 输出仅一行，表示 Herkabe 老师能制作出不同的排行榜的个数模 $10^9+7$ 的值。

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

本题一共 $7$ 个测试点，各个测试点的数据范围如下表所示：

| 测试点编号 | $n\leqslant$ |
| :-----------: | :-----------: |
| $1\sim 3$ | $10$ |
| $4\sim 7$ | $3000$ |

对于所有数据，字符串的长度在 $[1,3000]$ 之间，仅包含大写英文字母且保证互不相同。

**【题目来源】**

本题来源自 **_[COCI 2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST 3](https://hsin.hr/coci/archive/2012_2013/contest3_tasks.pdf) T5 HERKABE_**，按照原题数据配置，满分 $140$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2012-2013#3] PROCESOR

description:
Mirko 收到了一份有趣的作业：设计一个他自己的小处理器。这个处理器有编号从 $1$ 到 $n$ 的 $n$ 个寄存器，每一个寄存器上面以二进制形式保存一个无符号的 $32$ 位整数（可能的数值在 $[0,2^{32}-1]$ 之间）。

除此以外，这个处理器还要求完成以下两种操作：

- `1 k m`： 将寄存器 $k$ 上的数的二进制表示的后 $m$ 位整体提到最前面，然后将得到的新数字重新写入寄存器 $k$。例如：
$$\begin{aligned}&00000000000000000010001111111011\\\xrightarrow{m=10}&11111110110000000000000000001000\end{aligned}$$
- `2 k l`：计算寄存器 $k$ 上的数和寄存器 $l$ 上的数异或的结果并将结果输出到系统上。例如：
$$\begin{aligned}&00000000000000000000001111000111\\\underline\text{XOR }&\underline{00000000000001111100000000000111}\\\text{= }&00000000000001111100001111000000\end{aligned}$$

Mirko 直到他建立了这个处理器模型才意识到他忘记实现一个读取寄存器内容的操作。因此，他现在唯一能做的就是大量执行操作 $1$ 和操作 $2$，并从结果中推断寄存器内容。在执行了一系列命令之后，他要求您帮助他推导出与获得的结果一致的初始寄存器内容的组合。

如果初始寄存器状态组合有多种可能，则你需要求**按字典顺序排列的最小值的组合**（如果两个组合在前 $k–1$ 个寄存器中具有相等的值，而在寄存器 $k$ 中具有不同的值，则按字典顺序排列的较小组合就是在寄存器 $k$ 中具有较小值的组合）。

inputFormat:
输入共若干行。

第一行，两个整数 $n,e$，分别表示寄存器总数和操作次数。
接下来若干行用来描述每一个操作。对于一个操作，先输入一行三个整数 $\textit{op},k,l$，分别表示操作类型和该操作类型的两个参数。如果 $op=2$，则接下来应再输入一行一个整数，表示上一行的操作 $2$ 得到的结果，然后再在下一行进入下一个操作的输入。否则下一行直接进入下一个操作的输入。

如果您不能很好地理解输入格式，请参照样例以对这一部分有更好的理解。

outputFormat: 如果不存在与输入一致的初始寄存器内容组合，则仅输出一行一个整数 $-1$。否则输出一行 $n$ 个整数，第 $i$ 个整数表示一开始第 $i$ 个寄存器上的数。

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

对于 $40\%$ 的数据，满足 $n,e\leqslant 1000$。
对于所有数据，$2\leqslant n\leqslant 10^5$，$1\leqslant e\leqslant 10^5$。且满足：
- $op=1$ 时，$1\leqslant k\leqslant n$，$0\leqslant l\leqslant 32$。
- $op=2$ 时，$1\leqslant k,l\leqslant n$。

**【题目来源】**

本题来源自 **_[COCI 2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST 3](https://hsin.hr/coci/archive/2012_2013/contest3_tasks.pdf) T6 PROCESOR_**，按照原题数据配置，满分 $160$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2016-2017#6] Hindeks

description: 给出一个数列，请你求出一个最大的整数 $H$，使原数列中至少有 $H$ 个数 $\ge H$。

inputFormat:
第一行，一个正整数 $N$，表示数列中数的个数；

第二行，$N$ 个整数 $A_i$，表示数列中的数。

outputFormat: 一行，一个整数 $H$，表示符合条件的最大整数。

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

比 $2$ 大的数有 $2$ 个，分别是 $4$ 和 $8$。

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

比 $4$ 大的数有 $4$ 个，分别是 $8$，$5$，$4$ 和 $10$。

**【数据范围】**

对于 $100\%$ 的数据，$1\le N\le 5\times 10^5$，$0\le A_i\le 1\times 10^6$。

**【说明】**

本题分值按 COCI 原题设置，满分 $50$。

题目译自 [COCI2016_2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #6](https://hsin.hr/coci/archive/2016_2017/contest6_tasks.pdf) _**T1 HINDEKS**_


title: [COCI2016-2017#6] Telefoni

description:
一个办公室有 $N$ 张桌子从左至右排列，有些桌子上放了电话。

当第 $j$ 个桌子上的电话响了后，第 $i$ 个桌子上的电话也会响，当且仅当 $|j-i|\le D$。

现在给出电话的摆放情况，请你求出最小需要添加几个电话，能使最后一个桌子上的电话响起。

保证第一张桌子和最后一张桌子有电话放置。

inputFormat:
第一行包含两个正整数 $N$ 和 $D$，分别表示桌子个数和最大距离。

第二行包含 $N$ 个整数 $A_i$。如果 $A_i=1$，那么表示这个桌子上有电话，如果 $A_i=0$，则表示没有。

outputFormat: 一行，一个整数，表示最小需要添加电话个数，

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

在 $2$ 号桌子上添加一个电话，即可使 $4$ 号桌子上的电话响起。

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

在 $3$ 号桌子上添加一个电话，即可使 $5$ 号桌子上的电话响起。

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

在 $4$ 号桌子和 $7$ 号桌子上各添加一个电话，即可使 $8$ 号桌子上的电话响起。

**【数据范围】**

对于 $50\%$ 的数据，$1\le N\le 20$；

对于 $100\%$ 的数据，$1\le D\le N\le 3\times 10^5$。

**【说明】**

本题分值按 COCI 原题设置，满分 $80$。

题目译自 [COCI2016_2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #6](https://hsin.hr/coci/archive/2016_2017/contest6_tasks.pdf) _**T2 TELEFONI**_


title: [COCI2016-2017#6] Turnir

description:
给定一个由 $2^N$ 个正整数组成的数列。每一轮将这些数字按照给定的顺序进行比大小，大的数字留下，小的数字淘汰，直至只剩下最后一个数字为止。

现在给你这 $2^N$ 个数字的初始排列顺序，请你求出每个数字能活到的最大的轮数。

inputFormat:
第一行，一个整数 $N$；

第二行，$2^N$ 个整数 $A_i$，表示数列中的数。

outputFormat: 一行，$2^N$ 个整数，分别表示第 $i$ 个数能活到的轮数。

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

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

**【数据范围】**

对于 $100\%$ 的数据，$1\le N\le 20$，$0\le A_i\le 1\times 10^9$。

**【说明】**

本题分值按 COCI 原题设置，满分 $100$。

题目译自 [COCI2016_2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #6](https://hsin.hr/coci/archive/2016_2017/contest6_tasks.pdf) _**T3 TURNIR**_


title: [COCI2016-2017#6] Savrsen

description:
一个数是完美的，仅当它等于它的因数中比它小的所有数之和。

例如：$28=1+2+4+7+14$，所以 $28$ 是完美的。

由此我们可以定义一个数的不完美值 $F(N)$，代表 $N$ 和比 $N$ 小的所有 $N$ 的因数之和的差的绝对值。

例如：$F(6)=|6-1-2-3|=0$，

$F(11)=|11-1|=10$，

$F(24)=|24-1-2-3-4-6-8-12|=|-12|=12$。

现在给出两个正整数 $A$ 和 $B$，请你求出 $F(A)+F(A+1
)+...+F(B)$。

inputFormat: 一行，两个整数 $A$ 和 $B$，含义如上。

outputFormat: 一行，一个整数，表示 $F(A)+F(A+1)+...+F(B)$。


title: [COCI2016-2017#6] Sirni

description:
有 $N$ 张卡片，每张卡片上写有一个数值 $P_i$。

可以连接任意两张卡片，但需要花费 $\min(P_a\bmod P_b, P_b\bmod P_a)$。

请你求出连接所有卡片所需要的最小花费。

inputFormat:
第一行，一个整数 $N$，代表有 $N$ 张卡片；

接下来 $N$ 行，每行一个正整数 $P_i$，代表第 $i$ 张卡片上写的数值。

outputFormat: 一行，一个整数，代表最小花费。

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

连接卡片 $1$ 和卡片 $2$，花费 $\min(2\bmod 6,6\bmod 2)=0$；

连接卡片 $2$ 和卡片 $3$，花费 $\min(3\bmod 6,6\bmod 3)=0$；

连接卡片 $1$ 和卡片 $4$，花费 $\min(2\bmod 11,11\bmod 2)=1$。

总共花费 $0+0+1=1$。

**【数据范围】**

对于 $30\%$ 的数据，$1\le N\le 10^3$；

对于另外 $40\%$ 的数据，$1\le P_i\le 10^6$；

对于 $100\%$ 的数据，$1\le N\le 10^5$，$1\le P_i\le 10^7$。

**【说明】**

本题分值按 COCI 原题设置，满分 $140$。

题目译自 [COCI2016_2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #6](https://hsin.hr/coci/archive/2016_2017/contest6_tasks.pdf) _**T5 SIRNI**_


title: 「LCOI2022」 Cow Merger

background:
Bessie 来到她的新家之后，Farmer John 突然意识到自己农场的大小不够了！

所以，Farmer John 需要把所有的奶牛合并到一个牛棚里。

description:
Farmer John 的农场里本来有 $n$ 个牛棚，第 $i$ 个牛棚里住着 $a_i$ 只牛。

我们定义一次合并 $i,j(a_i\ge a_j)$ 两个牛棚的操作为：从 $i$ 号牛棚中拿出 $a_j$ 头牛，放入 $j$ 号牛棚中。如果在合并结束后 $a_i=0$，那么可以看做 $a_i$ 被合并了，接下来的操作也与 $a_i$ 无关。

由于时间不够了，他决定最多你 $1$ 秒的时间。

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

对于第 $t$ 组数据:

第 $2t$ 行包含一个整数 $n$。

第 $2t+1$ 行包含 $n$ 个整数，第 $i$ 个整数为 $a_i$。

outputFormat:
对于每组数据：

如果你发现自己不可能达到目标，输出 `NO`，否则输出 `YES`。

接下来一行，输出一个整数 $m$ 表示操作次数。

接下来 $m$ 行，每行输出两个数 $i$ 和 $j$（注意操作时应满足 $a_i \ge a_j$）。

**有多解时可输出任意一组解。**

hint:
【数据范围与约定】

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


title: [COCI2016-2017#6] Gauss

description:
给出 $K$ 个整数 $F(1),F(2),...,F(K)$，并定义 $i>K$ 的 $F(i)=0$；又给出 $T$ 个幸运整数 $X_i$ 和它的价格 $C(X_i)$，$M$ 个整数 $L_1,L_2,...,L_M$。

一开始黑板上有一个整数 $A$，可以进行如下的两种操作：

- 令当前黑板上的数是 $N$，则可以写下 $N$ 的因数中任意一个小于 $N$ 的因数 $M$，花费 $F(d(N\div M))$。其中 $d(N\div M)$ 表示正整数 $N\div M$ 的因数个数（包括 $N/M$）。

- 如果 $N$ 是一个幸运整数，可以将 $N$ 留在黑板上，花费 $C(N)$。

定义 $G(A,B,L)$ 为以 $A$ 为起始的数，进行了 $L$ 次操作，最终留下 $B$ 的最小花费，请你根据给定的 $A$ 和 $B$，求出 $G(A,B,L_1)+G(A,B,L_2)+...+G(A,B,L_M)$。

inputFormat:
第一行，一个正整数 $K$；

第二行，$K$ 个正整数 $F(1),F(2),...,F(K)$；

第三行，一个正整数 $M$；

第四行，$M$ 个正整数 $L_1,L_2,...,L_M$；

第五行，一个正整数 $T$；

接下来 $T$ 行，每行两个正整数 $X_i$ 和 $C(X_i)$，代表 $X_i$ 是一个幸运数且它的价格为 $C(X_i)$；

第 $T+5$ 行，一个正整数 $Q$，表示询问的个数；

接下来 $Q$ 行，每行两个正整数 $A$ 和 $B$。

outputFormat: 对于输入的每个询问，输出 $G(A,B,L_1)+G(A,B,L_2)+...+G(A,B,L_M)$。

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

因为 $L_1=1$，所以将 $4$ 替换成 $2$，花费 $G(4,2,1)=F(d(2))=1$；

因为 $L_2=2$，所以有两种方法将 $4$ 变成 $2$：

- 将 $4$ 替换成 $2$，又因为 $2$ 是幸运数字，所以第二轮留下 $2$。花费 $F(d(4\div 2))+C(2)=1+5=6$；

- 因为 $4$ 是幸运数字，所以第一轮留下 $4$，第二轮将 $4$ 替换成 $2$。花费 $C(4)+F(d(4\div 2))=11+1=12$。

第一种方案花费更少，所以选择第一种方案。

所以答案是 $G(4,2,1)+G(4,2,2)=1+6=7$。

**【数据范围】**

对于 $100\%$ 的数据，$1\le K\le 10^4$，$1\le F(i)\le 10^3$，$1\le M\le 10^3$，$1\le L_i\le 10^4$，$1\le T\le 50$，$1\le X_i\le 10^6$，$1\le C(X_i)\le 10^3$，$1\le Q\le 5\times 10^4$，$1\le A,B\le 10^6$。

**【说明】**

本题分值按 COCI 原题设置，满分 $160$。

题目译自 [COCI2016_2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #6](https://hsin.hr/coci/archive/2016_2017/contest6_tasks.pdf) _**T6 GAUSS**_


title: [Cnoi2021] 未来试题

background:
在 Cnoi2021 验题查重环节中，Cirno 发现在遥远的未来，2077 年蚯蚓科技大学（某不知名外界学校）的新生赛中的一道题竟然意外地与这套试题的某题有着 $9\%$ 的相似度。

>给你一个正整数 $n$，求等概率生成一个长度为 $n$ 的全排列时，全排列中逆序对数量的期望在$\bmod 10^9+7$ 的意义下的答案。（2077-xidian-freshman-online Problem.D）

答案显然是 $\frac{n(n-1)}{4}$。

作为算术天才，Cirno 一眼就看了出来。

但无需担忧，与未来试题相撞不算撞题，所以这道题便出现在了你的面前。

description:
给你两个正整数 $n,k$。

对 $\forall i \in [0,k)$，求等概率生成一个长度为 $n$ 的全排列时，全排列中逆序的个数对 $k$ 取模后，余数为 $i$ 的概率，答案对 $998244353$ 取模。

inputFormat: 一行，输入两个整数 $n,k$。

outputFormat: 一行，$k$ 个整数，用空格隔开，第 $i$ 个表示全排列中逆序的个数对 $k$ 取模后，余数为 $i-1$ 的概率。


title: [Cnoi2021] 数学练习

background: 「Cnoi2021」Cirno's Easy Round II 热身赛开始了。

description:
为了让选手们重视文化课，Cirno 特意加入了一道 Kamishirasawa Keine 老师的数学练习：

> 求将一个集合 $\texttt{U}=\{1,2,3,\cdots,n\}$ 划分成两个子集 $S,T$，使得 $|S|\notin S,|T|\notin T$ 的方案数。

由于选手都不会高精度，所以答案只需要对 $998244353$ 取模即可。

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

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


title: 「RdOI R3」RBT

description:
你有一棵以 $1$ 为根，编号为 $1\sim n$ 的有根树，第 $i$ 号节点上有一个整数权值 $a_i$。同时每一个点都被染上了红色或蓝色。初始所有点全是红色点。你需要维护这棵树，进行 $q$ 次操作。操作分若干种，具体格式如下：

- `1 x v` ：使 $x$ 节点的子树中的每个节点的权值增加 $v$ 并对 $p$ 取模。
- `2 x v`：将 $a_x$ 赋值为 $v$。**注意不是赋值整棵子树。**
- `3 x`：将 $x$ 号点染成蓝色，设 $j$ 节点为 $x$ 号节点在它的**红色**兄弟节点中**编号**（不是权值）排名的前驱，将 $x$ 节点连接父亲的边删除。然后将 $x$ 节点作为儿子节点接到 $j$ 节点上，如果 $x$ 节点没有红色兄弟节点或 $x$ 节点的红色兄弟节点的编号均比 $x$ 大则什么都不做。
- `4 x`：设 $S$ 为 $x$ 的子树中的节点的权值中出现次数为奇数的数组成的集合。输出集合中的每个数的 $k$ 次方之和，对 $998244353$ 取模。即 $(\sum_{z\in S}z^k)\bmod 998244353$。

特别的，数据保证每个点只能被执行 $3$ 操作至多 $1$ 次。也就是说不会出现对一个蓝色点进行 $3$ 操作的情况。

inputFormat:
第一行四个整数 $n,q,p,k$。
第二行 $n$ 个整数，代表初始的 $a_1,a_2,\cdots,a_n$。
接下来 $n-1$ 行，每行两个整数 $f,t$。表示一条连接 $f \leftrightarrow t$ 的双向树边。
接下来 $q$ 行，每行两个或三个整数 $op,x(,v)$。

outputFormat: 对于每个询问操作，输出一行一个整数表示答案。


title: 『JROI-3』Reversi

background:
**赛时提醒：如果您始终是 30pts，且使用了题目给的快速读入，请重新拷贝修改后的快速读入。**

**赛时提醒：本题如果解法正确，快读可能无法起到优化作用。**

	这个恐怕是将存在乃至于记忆切割成三十二颗的争夺黑白棋。

    双方剩下的棋子数字都很小——也就是重要性很高吧。

				......

    ——哥哥为什么会让自己落单呢？她原本对此感到疑惑。

    不过，在得知答案之后，那可以说是理所当然的做法。

    首先，第一个理由极为单纯。

    故意将记忆托付给对方，暂时屈居败势的目的是——

    「……那种事……白……做不到啊……」

    想像了一下，白露出悲伤的笑容，做出这个结论。

    哥哥做的这些事，如果由白执行……白不觉得自己的精神能够保持正常。

    自己仅仅因为哥哥从身旁消失，就甚至一度怀疑哥哥的存在。

    ——被忘掉的话还好。

    ——忘掉哥哥的话——白确信自己的精神会无法保持正常。

				......

    （……这里……哥哥在……这里……）

    即使是空无一物的空间，但是白确信，她感觉得到哥哥的位置。

    白顿时眼眶一热，不过她强行忍住，继续思考。

    （……然后这就是……第二个……同时也是……最大的……理由。）

    白将写着【参】的棋子白色面朝上，用手指夹住。

    哥哥是『白色还是黑色』，这个问题也不需要犹豫。

    因为既然他将最后的棋局托付给『白』——那他当然是持白棋。

    这个现在看不见，甚至无法认知的棋局。

    既没有开始的记忆，也不知道盘面的经过如何。

    不过哥哥故意下输，并且为了让白能获胜所可能下的棋步……

    而对方看到之后，完全中了哥哥的计谋，被诱导而下的棋步……

    然后，为了逆转，哥哥可能选择的所有位置分布。

    将这些全部推测分析——仅用三步棋反败为胜。

				......

    然后——原先失去一天半的记忆——逆流了回来——

description:
**白**在和森精种玩黑白棋，但黑白棋的规则有所改变。

有 $n$ 个黑白棋子，第 $i$ 个棋子编号为 $i$。棋子初始全为黑，游戏中，仅由**白**一人操作，**白**希望尽可能多的把棋子变成白色。

**白**要求第 $k$ 个棋子和第 $k \times p$ 个不能同时变成白色。

**白**共玩了 $T$ 次，每次**白**想知道最多能把多少棋子变成白色。**每次游戏独立。**

为避免混淆，加粗的**白**是人名。

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

下面 $T$ 行每行两个整数 $n,p$，同题意。

outputFormat: 共 $T$ 行，每行一个正整数，表示**白**最多能把多少枚棋子变为白色。

hint:
#### 样例 1 解释

可以选择第 $2,3$ 个棋子变色。

#### 数据规模与约定

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

- Subtask 1（5 pts）：$T \le 5$，$n \le 2$；
- Subtask 2（5 pts）：$T \le 5$，$n \le 10$；
- Subtask 3（20 pts）：$T \le 5$，$n \le 10^6$；
- Subtask 4（70 pts）：无特殊限制。

对于 $100\%$ 的数据满足，$1 \le T \le 10^6$，$0 \le n \le 10^{18}$，$1 \le p \le 10^{9}$。

```
//快读模板
//赛时提醒：快读没有太大必要使用
inline long long read(){
   long long s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}
```


title: [Cnoi2021] 矩阵

background:
Rumia 喜欢矩阵快速幂，而 Cirno 觉得这是平凡的。

为了说服 Rumia，Cirno 提出了这样一个问题。

description:
给定两个长度为 $n$ 的序列 $\{a_n\}$，$\{b_n\}$ 与一个整数 $k$。

设矩阵 $A$ 满足 $A_{ij}=a_i\times b_j$，求 $A^k$ 的所有元素的和在模 $998244353$ 意义下的结果。

inputFormat:
第一行两个整数 $n$，$k$。

第二行 $n$ 个整数，用空格隔开，表示 $\{a_n\}$。

第三行 $n$ 个整数，用空格隔开，表示 $\{b_n\}$。

outputFormat: 一行，一个整数，表示 $A^k$ 的所有元素的和在模 $998244353$ 意义下的结果。

hint:
**数据范围**

对于 $100\%$ 的数据保证 $1 \le n \le 10^5$，$0\le k < 998244353$，$|a_i|,|b_i| \le 10^9$。

**子任务**

Subtask1（10 points）：$n, k \le 50$。

Subtask2（20 points）：$n \le 100$。

Subtask3（20 points）：$n \le 1000$。

Subtask4（50 points）：无特殊限制。

**提示**

矩阵乘法的定义参考[百度百科](https://baike.baidu.com/item/%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95/5446029?fr=aladdin)页面。

本题中 $A^0$ 表示[单位矩阵](https://baike.baidu.com/item/%E5%8D%95%E4%BD%8D%E7%9F%A9%E9%98%B5/8540268?fr=aladdin)。


title: [Cnoi2021] 符文破译

background: Cirno 想要解读一本古老的魔法书。

description:
为了保护魔法书中记载的禁忌的魔法，撰写者将符咒的魔法词缀不加空格地连接在一起，形成一个符文串，记作 $\texttt{S}$。

而构成符文串的所有魔法词缀都被记载在更远古的先知所编写的魔法辞典中，记作 $\texttt{T}$。具体地，$\texttt{T}$ 的所有非空前缀均是一个合法的魔法词缀。

简洁是魔法书撰写的第一要务，所以使用的魔法词缀应该尽可能少。所以在破译魔法书时，将 $\texttt{S}$ 分解成的魔法词缀数越少，破译正确的可能性就越高。

Cirno 想知道，这本魔法书最少的魔法词缀划分段数是多少。

特别地，如果不存在一种合法的划分方案，则表明这本魔法书是假的。Cirno 将得到一个字符串 `Fake`。

inputFormat:
第一行，两个整数，表示 $|\texttt{T}|$，$|\texttt{S}|$。

第二行，一个字符串 $\texttt{T}$。

第三行，一个字符串 $\texttt{S}$。

outputFormat: 一行，一个整数或一个字符串 `Fake`，表示答案。

hint:
**数据范围与约定**

对于 $100\%$ 的数据，保证 $1\le |\texttt{S}|,|\texttt{T}|\le 10^7$，$\texttt{S}_x,\texttt{T}_x \in [\texttt{a},\texttt{z}]$。

**子任务**

Subtask1（$10$ points）：$\texttt{T}_x=\texttt{a}$。

Subtask2（$20$ points）：$|\texttt{S}|\le1000$。

Subtask3（$30$ points）：$|\texttt{S}|\le 10^6$。

Subtask4（$40$ points）：无特殊限制。


title: [Ynoi2007] tmpq

description:
给定三个长为 $n$ 的数组 $a,b,c$, 满足 $1\le a_i,b_i,c_i\le n$ 且为整数。

你需要进行 $m$ 次操作，每次操作为：

`1 k x`：代表将 $a$ 序列的第 $k$ 个位置改为 $x$，即 $a_k := x$。

`2 r`：代表查询有多少个三元组 $(i,j,k)$, 满足 $1\le i<j<k\le r$, 且 $b_{a_i}=a_j=c_{a_k}$。

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

第二行 $n$ 个数，按顺序表示序列 $a$ 中的元素。

第三行 $n$ 个数，按顺序表示序列 $b$ 中的元素。

第四行 $n$ 个数，按顺序表示序列 $c$ 中的元素。

之后 $m$ 行，每行形如 `1 k x` 或 `2 r`，意义如上述。

outputFormat: 对每个 $2$ 操作，输出一行一个数表示答案。

hint:
Idea：Forever_Pursuit&nzhtl1477&w33z8kqrqk8zzzx33，

Solution：nzhtl1477&w33z8kqrqk8zzzx33，

Code：w33z8kqrqk8zzzx33，

Data：w33z8kqrqk8zzzx33&nzhtl1477

对于 $100\%$ 的数据，满足 $1\le n\le 2\times 10^5$，$1\le m\le 5 \times 10^4$，$1\le a_i,b_i,c_i,x,k,r\le n$。

对于第一个操作，满足条件的三元组为：

- $ i=1 $ , $ j=2 $ , $ k=3 $
- $ i=2 $ , $ j=3 $ , $ k=4 $
- $ i=3 $ , $ j=4 $ , $ k=5 $

对于第三个操作，没有满足条件的三元组。

对于第四个操作，满足条件的三元组为：

- $ i=2 $ , $ j=4 $ , $ k=5 $
- $ i=3 $ , $ j=4 $ , $ k=5 $


title: [Ynoi2003] 博丽灵梦

description:
矩形颜色数，带权。

给定一个有 $n$ 个点的二维平面，每个点坐标为 $(i,p_i)$ ，其有权值 $a$。

给定一个长为 $n$ 的数组 $b$，其下标从 $1$ 到 $n$。

有 $m$ 次查询，每次查询给定一个矩形 $l_1,r_1,l_2,r_2$，定义集合 $S=\{a_i|l_1\le i\le r_1 \land l_2\le p_i\le r_2\}$，求对于集合 $S$ 中所有元素 $j$，$b_j$ 的和。

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

接下来一行 $n$ 个数，第 $i$ 个数表示 $p_i$。

接下来一行 $n$ 个数，第 $i$ 个数表示 $a_i$。

接下来一行 $n$ 个数，第 $i$ 个数表示 $b_i$。

接下来一行一个整数 $m$。

接下来 $m$ 行，每行 $4$ 个数分别表示 $l_1,r_1,l_2,r_2$，是一组询问。

outputFormat: 对每个询问，输出一行，包含一个整数，表示答案，答案对 $2^{32}$ 进行取模后输出。


title: [Ynoi2007] TB5x

description:
这是一道交互题。

二维平面上初始有 $n$ 个点 $(i,p_i)$，每个点有权值 $d_i$，$0\le i<n$；

共 $m$ 次操作，操作编号为 $0$ 到 $m-1$，按编号升序执行；

编号为 $w$ 的操作给出 $x_1,x_2,y_1,y_2$，满足 $0<x1<x2<n$，$0<y1<y2<n$。

一个点 $(x,y)$ 的网格坐标被定义为 $([x\ge x1]+[x\ge x2],[y\ge y1]+[y\ge y2])$。

依次进行以下步骤：

1. 查询网格坐标为 $(X,Y)$ 的点的权值之和，记录在 $ans[X][Y]$。
2. 对每个网格坐标为 $(X,Y)$ 的点，进行修改 $o[X][Y]$。
3. 所有点的坐标同时发生改变，对于一个网格坐标为 $(X,Y)$ 的点，它的坐标从 $(x,y)$ 变为 $(x+dx[X],y+dy[Y])$；
    其中
    $dx[0]=0$，$dx[1]=n-x2$，$dx[2]=x1-x2$。
    $dy[0]=0$，$dy[1]=n-y2$，$dy[2]=y1-y2$。
    $x1,x2,y1,y2,o,ans$ 都是数组，下标对应操作的编号。

其中 $d_i$ 属于抽象的数据类型 $D$，$o[X][Y]$ 属于抽象的数据类型 $O$；

$D$ 上定义了抽象的运算 $+:D\times D\to D$；

$D,O$ 上定义了抽象的运算 $\cdot:O\times D\to D$；

$O$ 上定义了抽象的运算 $\cdot:O\times O\to O$；

$\epsilon_D$ 是 $D$ 中的一个特殊的元素，称为单位元；

$\epsilon_O$ 是 $O$ 中的一个特殊的元素，称为单位元；

这些操作满足性质：

对任意 $a,b,c\in D$，有 $a+b=b+a$，$(a+b)+c=a+(b+c)$，$a+\epsilon_D=\epsilon_D+a=a$；

对任意 $u,v,w\in O$，有$(u\cdot v)\cdot w=u\cdot(v\cdot w)$，$u\cdot\epsilon_O=\epsilon_O\cdot u=u$；

对任意 $u,v\in O$，$a,b\in D$，有$(u\cdot v)\cdot a=u\cdot (v\cdot a)$，$u\cdot (a+b)=(u\cdot a)+(u\cdot b)$，$\epsilon_O\cdot a=a$，$u\cdot \epsilon_D=\epsilon_D$；

执行每次 $+$ 或 $\cdot$ 运算有一定的代价，具体地，在计算 $a+b$ 或 $a\cdot b$ 时如果 $a,b$ 都不是 $\epsilon_D$ 或 $\epsilon_O$，则代价为 $1$，否则代价为 $0$。你需要保证每个答案正确，且总代价不能超过当前子任务的**代价上限**。

### 实现细节

头文件中定义了数据类型 `Data` （$D$）和 `Operation` （$O$），你可以使用以下已定义的成员函数对类型为 `Data` 和 `Operation` 的数据进行操作：

```c++
void Data::add_eq(const Data &a)
```

`w.add(a)` 计算 $w+a$，并将结果保存在 $w$，每次调用的代价在 $w,a$ 都不是单位元时为 $1$，否则为 $0$；

```c++
void Data::add(const Data &a,const Data &b)
```

`w.add(a,b)` 计算 $a+b$，并将结果保存在 $w$，每次调用的代价在 $a,b$ 都不是单位元时为 $1$，否则为 $0$；

```c++
void Data::clr()
```

`w.clr()` 可以将 $\epsilon_D$ 保存在 $w$，每次调用的代价为 $0$；

```c++
bool Data::empty()const
```

`w.empty()` 判断 $w$ 是否为 $\epsilon_D$，若是则返回 $\mathrm{true}$，否则返回 $\mathrm{false}$，每次调用的代价为 $0$；

```c++
void Operation::apply(Data &a)const
```

`w.apply(a)` 计算 $w\cdot a$，并将结果保存在 $a$，每次调用的代价在 $w,a$ 都不是单位元时为 $1$，否则为 $0$；

```c++
void Operation::apply(Operation &u)const
```

`w.apply(u)` 计算 $w\cdot u$，并将结果保存在 $u$，每次调用的代价在 $w,u$ 都不是单位元时为 $1$，否则为 $0$；

```c++
void Operation::clr()
```

`w.print()` 可以将 $\epsilon_O$ 存储在 $w$，每次调用的代价为 $0$；

```c++
bool Operation::empty()const
```

`w.empty()` 判断 $w$ 是否为 $\epsilon_O$，若是则返回 $\mathrm{true}$，否则返回 $\mathrm{false}$，每次调用的代价为 $0$；

另外，你还可以使用 `Data` 或 `Operation` 类型的赋值运算符、拷贝构造函数或无参构造函数，以 `Data` 类型为例：

`w=u` 可以将 $u$ 复制一份存储在 $w$，每次调用的代价为 $0$；

`Data w(u);` 或 `Data w=u;` 可以将 $u$ 复制一份存储在新定义的 $w$，每次调用的代价为 $0$；

`Data w;` 可以将 $\epsilon_D$ 存储在新定义的 $w$，代价为 $0$；

`Operation w;` 可以将 $\epsilon_O$ 存储在新定义的 $w$，代价为 $0$；

除了以上描述的对 `Data` 或 `Operation` 的操作外，其余操作根据情况可能被视为攻击评测系统。

`sizeof(Data)` 和 `sizeof(Operation)` 都不超过 $64$，此外交互库还需要不超过 64MB 的空间。时间和空间限制包括交互库使用的时间和空间。仅使用赋值、构造函数、`apply` 和 `add` 就可以写出正确的程序，其它函数可能可以提供便利。

你需要实现以下函数：

```c++
void solve(
	const int n,
	const int m,
	const int p[],
	const Data d[],
	const int x1[],
	const int x2[],
	const int y1[],
	const int y2[],
	const Operation o[][3][3],
	Data ans[][3][3])
```

- $n$：点的个数；
- $m$：操作的个数；
- $p$：$(i,p[i])$ 表示每个点的坐标，$0\le i<n$；
- $d$：$d[i]$ 表示每个点的初始权值，$0\le i<n$；
- $x1,x2,y1,y2,o,ans$：$x1[i],y1[i],x2[i],y2[i],o[i]$ 表示每次操作的输入，你需要将相应的答案存储到 $ans[i]$，$0\le i<m$。

为了您的方便，这里提供模板。请完善以下代码：

```cpp
/* BEGIN HEADER: */
class Data {
  friend class Operation;
  friend int main();

private:
  unsigned int x, sz, T, flag;
  void read();
  void print() const;

public:
  Data() { clr(); }
  void add_eq(const Data &a);
  void add(const Data &a, const Data &b);
  void clr();
  bool empty() const;
};

class Operation {
  friend int main();

private:
  unsigned int a, b, L, R, flag;
  void read();

public:
  Operation() { clr(); }
  void apply(Data &w) const;
  void apply(Operation &w) const;
  void clr();
  bool empty() const;
};

void solve(const int n, const int m, const int p[], const Data d[],
           const int x1[], const int x2[], const int y1[], const int y2[],
           const Operation o[][3][3], Data ans[][3][3]);
/* END HEADER. */

#include <bits/stdc++.h>

void solve(const int n, const int m, const int p[], const Data d[],
           const int x1[], const int x2[], const int y1[], const int y2[],
           const Operation o[][3][3], Data ans[][3][3]) {
  // complete this
}
```

由于洛谷的交互方法比较奇怪，所以提交的时候需要把本地的代码复制过来，放在这个 solve 函数这里，和前面的 HEADER 一起提交。提交时不引用 "data.h" 头文件。

inputFormat:
下发的交互库以如下格式读取输入数据：

- 第一行：$n$
- 接下来 $n$ 行：$p_i\;d_i$（$d_i$ 由两个整数表示）
- 第 $n+2$ 行：$m$
- 接下来 $m$ 行：$x1_i\;x2_i\;y1_i\;y2_i\;o_i$（$o_i$ 由 $9 \times 4$ 个整数表示）

$D$ 中的元素是 $2\times 1$ 的矩阵，$O$ 中元素是 $2\times 2$ 的矩阵，矩阵中的元素是对 $2^{32}$ 取模的整数；

$+$ 对应矩阵加法，$\cdot$ 对应矩阵乘法，具体可以参考下发的交互库的实现；

实际评测环境中输入输出格式以及 $D,O$ 等可能有不同的定义；

outputFormat:
下发的交互库以如下格式打印你的答案：

- 对每个询问，输出 $13$ 行，其中第 $1 , 2 , 3 , 5 , 6 , 7 , 9 , 10 , 11$ 行有两个整数，依次表示这次询问对应的$ans[0][0],ans[0][1],ans[0][2],ans[1][0],ans[1][1],ans[1][2],ans[2][0],ans[2][1],ans[2][2]$，其余为空行；
- 向 stderr 打印总代价，以及在总代价超过代价上限时进行提示。

hint:
Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

Special thanks：w33z8kqrqk8zzzx33 修改交互库使得能在洛谷上运行。

对于 $100\%$ 的数据，满足 $n\le 10^5,m\le 2\times 10^4$。

共 10 组数据，满足 $n=10^5$；

每组数据的 $m$ 分别为 $10,100,1000,2000,5000,10000,12500,15000,17500,20000$；

所有数据的代价上限为 $10^8$。

每组数据对应 $10$ 分。


title: 「JZOI-2」信号塔

background:
团员们满脑子都是办周年庆，但小僖只想摸鱼。

小僖想看电视，但是发现没信号了，于是他去修理信号塔了。

description:
在一条有 $10^{999}+1$ 个点的直线上，满足直线上相邻两点间的距离相等，每个点上建立都建立了一个信号塔，从左到右编号为 $0\sim 10^{999}$，其中 $0$ 号塔是电视节目发送点。

由于小僖只想看电视，所以这里的信号只会从左往右传输。假设一个信号塔的强度为 $x$，那么它的信号最多能往右传输 $\lfloor\frac{x-1}{k}\rfloor$ 的距离。

现在小僖要给每个信号塔设置一个强度，但由于信号塔太多了，他忙不过来，于是他交给了笨笨机器人来做。

笨笨机器人按照以下方式给每个信号塔设置一个强度。

首先先将 $0$ 号塔的强度设为 $10^{30}$，然后从左到右，从 $1$ 号信号塔开始一直做到 $10^{999}$ 号信号塔。对于每个信号塔，在其左边寻找离它最近的一个信号塔 $a$，满足 $a$ 信号塔的信号可以传送到该信号塔，然后将该信号塔的信号强度赋值为这两个信号塔之间的距离。

这里定义 $i$ 号信号塔和 $j$ 号信号塔之间的距离为 $|i-j|$。

例如当 $k=2$ 的时候 $1\sim5$ 号的信号塔的强度分别为 $1,2,3,1,5$。

但小僖还是不放心笨笨机器人，所以他想知道第 $n$ 个信号塔的强度。

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

具体意义见题面。

outputFormat: 一行，一个整数，表示编号为 $n$ 信号塔的强度。


title: 远古档案馆（Ancient Archive）

background:
为了揭开月光能量背后的秘密，你来到了地下的远古档案馆。

远古一族的秘密与遗忘的知识悉数贮藏于这片被尘封的迷宫中，你能成功解谜，获知远古的知识吗？

description:
远古档案馆的中心是一个解谜：

- 有一个 $2\times 2$ 的网格，每个格子中要么有一个正整数，要么是空的；

- 你可以进行若干次操作：每次操作中，你选择一个**有正整数的格子**和一个**与之相邻的空格子**，将正整数移到那个空格子中；

- 给定网格的初始状态和最终状态，保证初始状态和最终状态中包含的正整数个数相同（设为 $k$ 个），且它们就是前 $k$ 个不同的正整数，问是否可以通过有限次操作从初始状态到达最终状态？

下图展示了一个包含三个正整数的网格经过两次操作的情况：

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

只有完成解谜，才能获得遗忘的知识，因此你希望尽快解决这个问题。

**注意：网格中可能没有正整数，也可能没有空格。**

inputFormat:
输入共包括四行，每行两个整数。

前两行描述了初始状态，后两行描述了最终状态，用 $0$ 表示空格子。

outputFormat: 如果可以从初始状态到达最终状态，输出 `Yes`，否则输出 `No`。

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

如题目描述中图所示。

---

**【样例 2 解释】**

没有可移动的正整数，所以无法从初始状态到达与之不相等的最终状态。

---

**【数据范围】**

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

所有数据符合题目描述所述。

- Subtask 1（40 points）：不存在空格。
- Subtask 2（60 points）：无特殊限制。

---

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


title: 珍珠帝王蟹（Crab King）

background: 在一次航程中，你偶然发现了被一片礁石环绕的帝王蟹，被月岛能量侵蚀的它又与月光有着怎样的联系呢？似乎只有击败它才能见分晓。

description:
帝王蟹可以通过镶嵌宝石触发战斗，不同的宝石效果不同，但奇特的是，镶嵌宝石的顺序有时也会影响它的强度。

帝王蟹有一个初始为 $0$ 的强度值，每个宝石有属性 $op$ 和 $v$，表示：

- 若 $op$ 为 `+`，则镶嵌后帝王蟹的强度值将会加上 $v$；

- 若 $op$ 为 `*`，则镶嵌后帝王蟹的强度值将会乘上 $v$。

由于宝石的效果十分奇异，所以 $v$ 可能是负数。

作为一个有挑战精神的冒险者，你希望采取某种镶嵌方式，将**每个宝石**都镶嵌**恰好一遍**，且使得帝王蟹的强度值最大。

你只需要输出最大的强度值对 $998244353$ 取模的结果，注意这是一个 $[0, 998244353)$ 中的数。

也就是说，如果答案为 `ans`，按照 C++ 语法，你需要输出 `(ans % P + P) % P`，其中 `P = 998244353`。

inputFormat:
第一行，一个整数 $n$，表示宝石数量。

接下来 $n$ 行，每行有用空格隔开的一个字符 $op$ 和一个整数 $v$，描述一个宝石。

outputFormat: 输出一行一个整数，表示最大的强度值对 $998244353$ 取模的结果。


title: 天体探测仪（Astral Detector）

background: 通过远古档案馆的探索，你成功制出了天体探测仪，你需要用它发现潜藏的天体科技。

description:
想要找到天体科技，你需要先得到一串天体密码——它是一个 $1 \sim n$ 的**排列**。

天体探测仪允许对于给定的长度 $l$，返回密码中一个长度为 $l$ 的**区间的最小值**。

不幸的是，所有长度为 $l$ 的区间最小值混在了一起，你得到的只是 $n$ 个**可重集合** $S_1, \ldots , S_n$：

- $S_i$ 表示所有长度为 $i$ 的区间最小值构成的可重集合。

你需要根据这些 $S_i$，还原出一种可能的天体密码，保证至少存在一种正确的天体密码。

inputFormat:
第一行，一个整数 $n$，表示天体密码的长度。

接下来 $n$ 行，其中第 $i$ 行包含 $n - i + 1$ 个整数（长度为 $i$ 的区间共有 $n - i + 1$ 个），表示可重集 $S_i$ 中的每个元素，注意元素的顺序是**任意的**，而不一定是按照区间从左到右的顺序。

outputFormat:
输出一行 $n$ 个整数 $p_1, p_2, \ldots , p_n$，表示你还原出的天体密码。

如有多种可行解，可以输出任意一种。


title: 风暴之眼（Eye of the Storm）

background:
通过月岛，帝王蟹和天体探测仪，你成功拼合了三个天体科技，接下来你要做的，就是来到风暴之眼的中心，准备那个神秘实验的最后一步。

最终的真相近在咫尺，你能否成功通过这场考验呢？

description:
天体风暴中的气象瞬息万变。

风暴中的道路构成一棵 $n$ 个结点的**无根树**，第 $i$ 个结点有初始权值 $w_i$（$w_i$ 为 $0$ 或 $1$）和类型 $t_i$。

结点的类型分为两种：$\texttt{AND}$ 型结点和 $\texttt{OR}$ 型结点。

对于 $\texttt{AND}$ 型结点，每一秒结束后它的权值将变为**它与它所有邻居上一秒权值的 $\texttt{AND}$ 和**；

对于 $\texttt{OR}$ 型结点，每一秒结束后它的权值将变为**它与它所有邻居上一秒权值的 $\texttt{OR}$ 和**。

现在，已知从某一时刻起，所有结点的权值都不再发生任何变化，将此时点 $i$ 的权值称为 $a_i$。

现不知每个点的初始权值和类型，只知道最终每个点的权值 $a_i$，求出有多少种可能的初始权值和类型的组合，答案对 $998244353$ 取模。

inputFormat:
第一行，一个整数 $n$，表示树的结点数。

第二行，$n$ 个整数 $a_1, a_2, \ldots , a_n$，表示每个结点最终的权值。

接下来 $n-1$ 行，每行两个整数 $x,y$，描述无根树中的一条边。

outputFormat: 输出一行一个整数，表示可能的初始权值和类型的组合数量。


title: 旧神归来（Return of Them）

background:
随着虚影与暗影的决战、月岛祭坛的完工、天体风暴的出现、天界捍卫者的到来，一切月球与远古的秘密仿佛已经行至终局。

旧神即将归来！

description:
月岛上的一棵普通的树在月光侵蚀的影响下不断生长，随着月面风暴的来临变得更加无限制。

具体地，生长规则如下：

- 初始有一棵包含 $n$ 个结点的以 $1$ 为根的**有根树** $T_0$；

- 在第 $i$ 天，树将从 $T_{i - 1}$ 生长为 $T_i$，生长规则为：令 $v$ 是 $T_{i - 1}$ 中**深度最小的叶结点**（若有多个则任意选择一个），以 $v$ 这个点替换成 $T_{i - 1}$ 本身。

本题中一个结点的深度定义为它到根结点的简单路径所经过的**边数**，注意这可能与常规定义不同。

下图展示了一个从 $T_{i-1}$ 生长到 $T_i$ 的例子：

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

除了面对天界捍卫者，对于环境效应的估计也是重要的，所以你需要计算：

- 对于每个整数 $d \in [1, m]$，求出 $S_d$ 表示最小的天数，满足 $T_{S_d}$ 中深度最小的叶结点深度**大于** $d$。

答案对 $998244353$ 取模。

inputFormat:
第一行，两个整数 $n, m$，分别表示 $T_0$ 的结点数和要求答案的深度范围。

接下来 $n - 1$ 行，每行两个整数 $x, y$，表示 $T_0$ 中结点 $x, y$ 间有一条边。

outputFormat: 输出 $m$ 行，第 $i$ 行输出一个整数表示 $S_i$。

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

如图展示了 $T_0$ 至 $T_3$ 的形态，最浅的叶子由红色标出，上一次生长出的部分用蓝色标出。

可以看到，$T_1$ 中深度最小的叶子深度大于 $1$，$T_3$ 中深度最小的叶子深度大于 $2$，而再操作一次后得到的 $T_4$ 中深度最小的叶子深度就会大于 $3$（应为 $4$），这是对样例输出前三行的一个解释：

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

---

**【数据范围】**

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

对于 $100 \%$ 的数据：$2 \le n, m \le {10}^5$。

| 子任务编号 | 分值 | $n, m \le$ | 特殊限制 |
|:-:|:-:|:-:|:-:|
| $1$ | $12$ | $10$ | $T_0$ 为二叉树 |
| $2$ | $8$ | ${10}^5$ | $T_0$ 为以 $1$ 为一端的链 |
| $3$ | $25$ | ${10}^5$ | $T_0$ 为二叉树，且每个非叶结点都有两个子结点 |
| $4$ | $10$ | $100$ | 无 |
| $5$ | $12$ | $1000$ | 无 |
| $6$ | $15$ | $30000$ | 无 |
| $7$ | $18$ | ${10}^5$ | 无 |

---

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


title: [COCI2009-2010#2] FAKTOR

background:
本题为[$\texttt{COCI 2009-2010}\ 2^\texttt{nd}\ \texttt{round}\ \text{T1 FAKTOR}$](https://hsin.hr/coci/archive/2009_2010/contest2_tasks.pdf)。

分值按原题设置，满分 $30$。

description: 给定 $A,I$，求一个最小的 $N$，使得$\lceil\frac{N}{A}\rceil\geq I$。

inputFormat: 一行两个整数 $A,I$。

outputFormat: 一行一个整数 $N$。

hint: $1\leq A,I\leq 100$。


title: [COCI2009-2010#2] RIMSKI

background:
本题为[$\texttt{COCI 2009-2010}\ 2^\texttt{nd}\ \texttt{round}\ \text{T2 RIMSKI}$](https://hsin.hr/coci/archive/2009_2010/contest2_tasks.pdf)。

分值按原题设置，满分 $50$。

description: 给定一个罗马数字 $B$，把 $B$ 的字符重新排列，要求让排列后的数字最小。

inputFormat: 一行一个罗马数字 $B$。

outputFormat: 一行一个罗马数字，为你重排后能得到的最小的数字。

samples: VIII VIII

samples: VI IV

samples: III III

samples: LI LI

hint:
$1\leq B< 100$。

注意，在本题中`I`如果在大数字之前，它只能在`V` 、`X`之前。输入遵循同样的规则。（这就是样例 $4$ 的输出为什么是 `LI` 而不是 `IL`。）


title: [COCI2022-2023#1] Iksevi

background: 写了十年的代码后，Vinko 决定转行做一名陶艺家。他在新工作的第一天就接到了一项艰巨的任务。

description:
Vinko 需要使用正方形瓷砖铺满音乐厅的地板。他不会让瓷砖的边与墙壁平行；相反，他选择让瓷砖的对角线与墙壁平行。

Vinko 还没有决定他将使用的瓷砖大小，但他知道所有瓷砖必须大小相同，而且对角线的长度必须是一个正偶数。

Vinko 铺下的第一块瓷砖的角将与左侧和后方的墙接触。此后他铺下的每一块瓷砖都与至少一块已铺好的瓷砖有一条边重合。他将重复这以一过程，直到铺满整个 $10^7 \times 10^7$ 平方毫米的地面。

除了程序员和陶艺家，Vinko 也是一个优秀的音乐家。正因为如此，他知道地板上有 $n$ 个点对大厅的音响效果至关重要。如果瓷砖的角落位于 $n$ 个点中的一个，大厅的声学效果将显著改善。

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

如图，左图为瓷砖对角线长度为 $4$ 的铺装，在此条件下，点 $(2,4)$ 在瓷砖的角落上，此时它满足条件，使得音响效果大为改善，但点 $(4,3)$ 和 $(5,1)$ 不满足条件。右图则为瓷砖对角线长度为 $2$ 的铺装，此时点 $(4,3)$ 在四块瓷砖的角落，而点 $(2,4)$ 和 $(5,1)$ 不在。

帮助 Vinko 确定对于 $n$ 个点中的每个点，有多少种瓷砖尺寸可以使铺满地面后第 $i$ 个点位于瓷砖的角落上。

inputFormat:
第一行包含一个整数 $n$，即声学关键点的数目。

接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个声学关键点与左侧墙壁与后方墙壁的距离。

outputFormat:
输出 $n$ 行，每行一个整数。

第 $i$ 行表示能使 $i$ 号声学关键点位于瓷砖角落的瓷砖尺寸数。


title: [COCI2009-2010#2] KUTEVI

background:
本题为[$\texttt{COCI 2009-2010}\ 2^\texttt{nd}\ \texttt{round}\ \text{T3 KUTEVI}$](https://hsin.hr/coci/archive/2009_2010/contest2_tasks.pdf)。

分值按原题设置，满分 $70$。

description:
给定 $N$ 个角（第 $i$ 个角记作 $a_i$），作为初始角，另给定 $M$ 个角（第 $i$ 个角记作 $b_i$），作为目标角。

请求出对于每个 $b_i$，它是否能被若干个 $a_i$ 之间的加、减运算得到。

注意同一个 $a_i$ 可以用多次，也可以不用。

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

第二行 $N$ 个正整数，第 $i$ 个数为 $a_i$。

第三行 $M$ 个正整数，第 $i$ 个数为 $b_i$。

outputFormat: 共 $M$ 行，在第 $i$ 行，如果 $b_i$ 能被若干个 $a_i$ 之间的加、减运算得到，输出`YES`，否则输出`NO`。


title: [COCI2009-2010#2] VUK

background:
本题为[$\texttt{COCI 2009-2010}\ 2^\texttt{nd}\ \texttt{round}\ \text{T4 VUK}$](https://hsin.hr/coci/archive/2009_2010/contest2_tasks.pdf)。

分值按原题设置，满分 $100$。

description:
一匹狼 Vjekoslav 正在逃离一批残暴的猎人的追捕。

这些猎人非常凶残，经常躲在树后面，但 Vjekoslav 并不知道哪棵树后有猎人。为了保险，Vjekoslav 希望在逃回它舒适的窝的过程中离树越远越好。

森林可以抽象为 $N\times M$ 的矩阵。每个格子可能是空的（用`.`表示），也有可能有一棵树在中心位置（用`+`表示）。Vjekoslav在`V`标示的地方而它的窝在`J`标示的地方。定义 Vjekoslav 与某棵树的距离为它们所在格的曼哈顿距离（即这两个格子所在行、列之差的绝对值之和）。

Vjekoslav 每次可以往东南西北中的任一方向移动，**即使它下一步移动到的格子有树（此题树并不会阻挡 Vjekoslav）**。帮忙找出这样一条从`V`到`J`的路径，使得 Vjekoslav 在途中离它最近的树的距离的最小值最大。

**注意 Vjekoslav 的窝并不占据整块格子，因此你的路径中必须包含`J`。**

inputFormat:
第一行两个整数 $N,M$。

接下来 $N$ 行每行 $M$ 个字符，描述这片森林。

在这片森林的描述中，只会有一个`V`与一个`J`，且保证至少有一个`+`。

outputFormat: 一行一个整数，Vjekoslav 在逃回窝的途中最大可能的离它最近的树的距离的最小值。

hint: $1\leq N,M\leq500$。


title: [AHOI2007] 石块地板

description:
小可可来到了宫殿的正厅中。大厅的地面是由一块块大小一致的正方形石块组成的，这些石块分为黑、白两色，组成了一个   $m×n$ 的矩形，在其中一个石块的下面就是通往藏宝库的通道。小可可不可能一个一个石块的尝试，因为有些石块安装了机关，一碰就会触发，整个宫殿也随之倒塌。根据藏宝图记载，通道在某一特定的区域中，这个区域是一个由数个石块组成的面积不为 $0$ 的小矩形，它的四条边与大厅地面的边平行。如果对整个大厅地面任意划分矩形，那么在所有矩形中，这个区域的黑色石块数目减去白色石块数目所得的差是最大的。

小可可希望和你分工，由他来选择区域，你来计算黑、白两色石块的数目差 $S$ 。这样就能快速而准确的确认通道所在的区域。藏宝图上说这个区域中的石块都没有安装机关，只要确定了区域，就一定能找到通道。宝藏就在眼前了，加油吧！

（假设用 $1$ 表示黑色石块，用 $0$ 表示白色石块）

inputFormat:
输入文件的第一行为两个整数 $m,n$。

以下 $m$ 行，每行 $n$ 个字符，每个字符都是 $0$ 或 $1$。

outputFormat: 输出文件仅一个数，表示所有可能的区域中 $S$ 值（见前文描述）最大的一个，输出这个值即可。


title: [Ynoi2005] rmscne

description: 给定长为 $n$ 的序列，$q$ 次询问区间 $[l,r]$ 的最短子区间 $[l',r']$，满足所有在 $[l,r]$ 中出现的数也在 $[l',r']$ 中出现. 你只需要输出 $[l',r']$ 的长度 $r'-l'+1$。

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

接下来一行有 $n$ 个正整数，表示序列的元素。

接下来一行有一个正整数 $q$

接下来 $q$ 行，每行两个正整数 $l,r$ 表示一个询问。

outputFormat: $q$ 行，每行一个正整数表示答案。

hint:
Idea：qwaszx，Solution：qwaszx，Code：qwaszx，Data：qwaszx

对于 $20\%$ 的数据，满足 $n,q,a_i\leq 5\times 10^3$。

对于 $50\%$ 的数据，满足 $n,q,a_i\leq 5\times 10^4$。

对于 $100\%$ 的数据，满足 $1\leq n,q\leq 2\times 10^6$，$1\leq a_i\leq n$。


title: 「JZOI-2」猜数列

background:
团员们满脑子都是办周年庆，但小僖只想摸鱼。

于是小僖拿出了最喜欢的数列来考考你。

description:
小僖有一个乱序的等差数列 $A$。

你可以发出两种询问：

1. 询问原序列下标为 $x,y$ 的数在等差数列（非模意义下）中的大小关系。
1. 询问原序列下标为 $x$ 的数在等差数列（模意义下）中的值。

但由于交互库出了点问题，你的询问 $2$ 最多能询问 $q$ 次。

给定等差数列的长度 $n$ 和询问次数 $q$，和固定的模数 $p=10^{9}+7$，求这个等差数列的公差 $d$。

**总询问次数不得超过 $2n$ 次。交互完成后请立刻输出答案。**

**交互方式：**

输入数列的长度 $n$ 和询问次数 $q$ 以开始交互。

交互过程中，您可以进行题目描述中的两种询问。

对于第一种询问，交互库将会返回 $1$ 代表 $>$ 或 $0$ 代表 $<$ 。询问格式为 `> x y`。

对于第二种询问，交互库将会返回一个正整数 $A_i$。询问格式为 `? x`。

在您确定答案后，请以 `! d` 的形式输出一行，停止交互。

在您输出一行后，请清空缓冲区：

在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。

在 Pascal 中，使用 `flush(output)`。

在 Python 中，使用 `stdout.flush()`。

其它语言请自行查阅文档。

**请遵循题目完成交互，发出不合法询问可能会出现 TLE，WA 等问题。**

inputFormat: 见交互方式。

outputFormat:
见交互方式。

数据保证不会有多种可能的 $d$。


title: 【模板】传递闭包

type: B

description:
给定一张点数为 $n$ 的有向图的邻接矩阵，图中不包含自环，求该有向图的传递闭包。

一张图的邻接矩阵定义为一个 $n\times n$ 的矩阵 $A=(a_{ij})_{n\times n}$，其中

$$ a_{ij}=\left\{
\begin{aligned}
1,i\ 到\ j\ 存在直接连边\\
0,i\ 到\ j\ 没有直接连边 \\
\end{aligned}
\right.
$$

一张图的传递闭包定义为一个 $n\times n$ 的矩阵 $B=(b_{ij})_{n\times n}$，其中

$$ b_{ij}=\left\{
\begin{aligned}
1,i\ 可以直接或间接到达\ j\\
0,i\ 无法直接或间接到达\ j\\
\end{aligned}
\right.
$$

inputFormat:
输入数据共 $n+1$ 行。

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

第 $2$ 到 $n+1$ 行每行 $n$ 个整数，第 $i+1$ 行第 $j$ 列的整数为 $a_{ij}$。

outputFormat:
输出数据共 $n$ 行。

第 $1$ 到 $n$ 行每行 $n$ 个整数，第 $i$ 行第 $j$ 列的整数为 $b_{ij}$。


title: 【模板】特征多项式

background: 这是一道模板题。

description: 给出 $n$ 和一个 $n\times n$ 的矩阵 $A$，在模 $998244353$ 意义下求其特征多项式。

inputFormat:
第一行一个正整数 $n$。\
接下来 $n$ 行每行 $n$ 个非负整数，表示矩阵 $A$。

outputFormat: 输出一行 $n+1$ 个正整数，表示其特征多项式 $p_A(x)$ 从低到高的系数。

hint:
对于一个 $n\times n$ 的矩阵 $A$，设其特征多项式为 $p_A(x)$，满足
$$p_A(x)=\det(xI_n-A)$$
其中，$I_n$ 为一个 $n\times n$ 的单位矩阵。

对于 $10\%$ 的数据，$1\le n\le 5$；\
对于 $40\%$ 的数据，$1\le n\le 50$；\
对于另外 $10\%$ 的数据，$\forall1\le i\le n,1\le j\le i-1,A_{i,j}=0$，即 $A$ 为上三角矩阵；\
对于另外 $20\%$ 的数据，$\forall1\le i\le n,1\le j\le i-2,A_{i,j}=0$，即 $A$ 为上海森堡矩阵；\
对于 $100\%$ 的数据，$1\le n\le 500$，$A_{i,j}\in[0,998244352]$。


title: 「JZOI-2」填问卷

background:
团员们满脑子都是办周年庆，但小僖只想摸鱼。

于是小僖打开了他心爱的游戏。

description:
玩了这么久这款游戏了，今天小僖想参加活动，填一下问卷来看看自己对这款游戏的了解程度。

问卷上一共有 $n$ 道判断题，可怜的小僖发现自己一题也不会，他决定问一下他的队友来解决。

他的队友是游戏的一位资深用户，他全部题都会做，所以小僖决定向队友求助。具体的，小僖每次都会以以下格式询问：

`int ask(int m,vector<int> w,vector<bool> ans)`

其中 $m$ 表示这一次询问的题目的总数，$w_i$ 表示询问的第 $i$ 题的题目编号（你需要保证单次询问的 $w_i$ 互不相同，毕竟队友很没有耐心），$ans_i$ 表示小 X 认为的第 $i$ 题的正确答案（$0\le i<m$）。队友会告诉他这次他有多少题**答对**了。

例如，现在有三道题，如果答案分别是 $\{0,1,1\}$，小 $X$ 现在调用 `ask(2,[1,3],[1,1])`，那么返回值为 $1$，因为第一道题答错了，第三道题答对了。

由于题目有点多，小僖需要你写一个程序来帮助他得到所有题的正确答案。

你不需要实现主函数，你现在只需要实现 `vector<bool> work(int n)`，返回值是题目 $1\sim n$ 的答案，考虑到 `vector<bool>` **下标从 0 开始**，所以你需要将你的答案数组**左移 1 位。**

当然，询问很费劲，所以小僖希望询问次数越少越好，询问次数的评分标准会在提示说明中给出。另外，虽然每一次询问的题目数没有限制，但你还是要注意，如果询问题目数过多，你可能会获得 **TLE**，题目保证每次询问的时间复杂度是 $O(m)$ 的。

为了方便，这里用 $1$ 表示选对，$0$ 表述选错。

inputFormat:
样例数据属于第一部分，按照以下格式输入：
$n\\a_{1...n}$
其中 $a_i$ 表示第 $i$ 题的正确答案。

outputFormat:
下面给出`grader.cpp`的错误信息 $\text{Wrong[x]}$：
1. 询问中的 $w_i$ 大于 $n$ 或小于 $1$。
2. 询问中出现了相同的 $w_i$。
3. 询问中 $m$ 和 $w$ 或 $ans$ 的长度不匹配。
4. 答案错误或返回数组格式不正确。

之后，`grader.cpp`会返回你的询问次数。

hint:
### 样例解释
下面给出一种 $2$ 次的可行的询问方案

`ask(1,[2],0)`，返回值为 $1$，表明第二题的答案是 $0$.
`ask(2,[1,3],[0,1])`，返回值为 $2$，~~这也许是因为运气太好，一蒙就对~~，所以可以得出第一题和第三题的答案分别是$0,1$。
于是你可以返回 $\{0,0,1\}$ 了，这时询问次数为 $2$。

当然，如果第二次询问结果是 $1$，那么你就不能直接得出答案了，所以，蒙题有风险。
### 数据范围
对于所有数据，保证 $n\le2^{17}$。

问卷的出题人为了保证用户们答题的质量，为了防止用户做判断题一蒙全对，他会精心构造每一道题的答案。

当然，这里保证答案在问卷出好后就已经存在，不会根据你的询问来构造。

对于每组数据假设你询问了 $Q$ 次，下面给出评分标准。
| $Q$ 的取值范围 | 得分 |
| :----------: | :----------: |
| $(2^{17},+\infty)$ | $0$ |
| $2^{17}$ | $10$ |
| $(64000,2^{17})$ | $\min(90,\lfloor\frac{2^{17}-Q}{2^{16}}\times100\rfloor)$ |
| $(63000,64000]$ | $95$ |
| $[0,63000]$ | $100$ |

注意，本题有多组测试点，得分取所有数据中测出的得分最少的那组数据。

实现细节：请务必加上 `extern "C"`，你可以选择补全 `problem.cpp` 中的函数中的内容，当然也可以自己实现。编译的时候直接编译和运行 `grader.cpp` 即可。

温馨提示：如果你的乱搞做法打得太劣，虽然你的询问次数小于 $2^{17}$，但你的得分可能小于 $10$ 分。


title: 「MCOI-06」Distinct Subsequences

description:
给定一个由小写字符构成的字符串 $S$。

令一个字符串的价值为该串的**本质不同**非空子序列个数，其中子序列可以为整体。

求 $S$ **所有**子序列的价值和。答案对 $10^9+7$ 取模。

inputFormat: 第一行一个由小写字符构成的字符串 $S$。

outputFormat: 输出一行，为答案。

hint:
#### 数据规模与约定

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

 - Subtask 1（5 pts）：$|S|\le 11$。
 - Subtask 2（10 pts）：$|S|\le 22$。
 - Subtask 3（20 pts）：$|S|\le 100$ 并 $S$ 仅由 `a`，`b` 两个字符构成。
 - Subtask 4（30 pts）：$|S|\le 5000$。
 - Subtask 5（35 pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le |S|\le 10^6$，保证 $S$ 仅由小写字符构成。


title: 「CGOI-1」大师选徒

background:
最近有好多人来丑国学习 bc。bc 大师 ac 和 mc 要从所有学生选出一些来传授 bc 技艺。

###### 2021.8.29：添加了一组 hack

description:
有 $n$ 个学生站成一排，每个学生有一个丑值 $a_i$。现在 ac 和 mc 要**各自**从学生中选取**连续**的一段传授 bc。

由于 ac 和 mc 关系很♂好，所以两人选出的学生必须人数相同，并且**对应位置**上的学生丑值之和均为 $s$。

（比方说，如果 ac 选第 $1$、$2$、$3$ 号学生，mc 选 $3$、$4$、$5$ 号学生，必须满足 $a_1+a_3=a_2+a_4=a_3+a_5=s$）

但 ac 并不知道 mc 所选的学生以及 $s$ 是多少，所以他会给出若干个询问。对于每个询问，你需要回答对于特定的 $s$ 以及 mc 选出的一段学生，ac 是否可以选出另一段学生满足上述要求。

**简化版题意：**

给出 $n$ 及 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$；

$q$ 次询问，每次给出 $s,l,r$，问是否存在 $b$，满足 $\forall k \in [0, r-l]$，$a_{l+k}+a_{b+k}=s$。

inputFormat:
第一行输入两个整数 $n,\,q$，分别表示学生的人数与询问的个数。

第二行输入 $n$ 个整数，第 $i$ 个数 $a_i$ 表示第 $i$ 个学生的丑值。

接下来 $q$ 行，每行输入三个整数 $s,\,l,\,r$，分别表示丑值之和，mc 所选的第一个学生的下标和最后一个学生的下标。

outputFormat: 对于每一个询问，如果可以选出符合条件的学生，输出 `Yes`，否则输出 `No`。每个输出占一行。

hint:
#### 样例说明：

对于样例 1：

第一个询问，mc 选择的是第三个学生，ac 可以选择第一个学生。

第二个询问，mc 选择的第二个学生丑值为 $1$，而总和也为 $1$，但不存在丑值为 $0$ 的学生，故不能满足条件。

第三个询问，mc 选择的是第四个到第六个，那么 ac 选择第二个到第四个，对应位置的学生丑值之和 $a_2+a_4=a_3+a_5=a_4+a_6=5$，满足条件。

第四个询问，mc 选择第一个和第二个，那么 ac 也选择第一个和第二个，满足条件。

---

#### 数据范围：

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

对于全部数据，有 $1\le n,\,q\le 4\times10^5$，$1\le a_i \le n$，$1\le s\le 2n$，$1\le l\le r\le n$。
* Subtask 0（10 points）：$n,\,q\le 500$。
* Subtask 1（20 points）：$n,\,q\le 8\times10^3$。
* Subtask 2（20 points）：保证所有 $s$ 相同。
* Subtask 3（50 points）：无特殊限制。


title: 「EZEC-11」Sequence

description:
已知数列 $f$ 满足 $f_n=a_nf_{n-1}+b_n\ (n\ge 1)$。

问是否存在非负整数 $f_0$，使得 $\forall 1\le i\le k$，$f_i$ 为**质数** $p_i$ 的倍数。

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

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

对于每组测试数据：

- 第一行一个整数 $k$。
- 第二行 $k$ 个整数 $a_1,a_2,\dots,a_k$。
- 第三行 $k$ 个整数 $b_1,b_2,\dots,b_k$。
- 第四行 $k$ 个整数 $p_1,p_2,\dots,p_k$，**保证 $p$ 为质数**。

outputFormat:
对于每组测试数据：

- 一行一个字符串，若存在满足条件的 $f_0$ 则输出 `Yes`，否则输出 `No`。

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

对于第一组测试数据，一个可行的解为 $f_0=1$，此时 $f_1=3,f_2=5,f_3=7$。

对于第二组测试数据，没有满足条件的 $f_0$。

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

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

-  Subtask 1（10 points）：$k=1$。
-  Subtask 2（20 points）：$k\le 2$。
-  Subtask 3（20 points）：$k\le 5$，$p_i\le 20$。
-  Subtask 4（50 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le 10$，$1\le k\le 10^3$，$0\le a_i,b_i\le 10^9$，$2\le p_i\le 10^9$，**$p$ 为质数**。


title: 「Wdoi-3」夜雀 singing

background:
“唉，今天可真是多事的一天呢。不过一晚的忙碌结束了，接下来就是我尽展歌喉的时刻啦！”

作为幻想乡妖精中的一份子，米斯蒂娅在闲暇之余（也就是夜雀食堂闭店之后）也会去参加由夜雀们自发组织而成的夜雀歌会。夜雀们会按照一种约定好的方式进行歌唱。在今夜的歌会中，米斯蒂娅成为了歌会的组织者。

然而因为大家都是夜雀，因此所谓的“舞台”其实是由若干个高度不一的树组成的。夜雀都会飞（显然），因此它们可以不断地变换自己的位置。

然而，由于夜雀的数目实在是太多，以至于作为组织者的米斯蒂娅搞不清楚活动的组织方案了。你能帮帮她吗？

description:
我们可以将这 $n$ 棵树从 $1$ 到 $n$ 编号。其中，在 $m$ 个点上分布着参加舞会的夜雀。第 $i$ 棵树的高度为 $h_i$ 。

夜雀们的歌会一共会进行 $t$ 时刻。第 $i$ 个时刻，夜雀们**只能**在高度严格大于 $i$ 的树上唱歌。因为这些树木都是事先被选择好的，因此总是有 $\max\{h_i\}>t$。夜雀们每个时刻，**可以选择站着不动**，或移动到**编号相邻**的一棵树上（例如，原先在编号为 $i$ 的树上的夜雀，下个时刻可以移动到编号为 $i-1$ 或者 $i+1$ 的树上。不过，她们不能移动到编号为 $0$ 或 $n+1$ 的树上）。初始时为第 $0$ 时刻。也就是说，假使一个夜雀初始时在高度为 $1$ 的树上，那么她下一时刻不得不去高度大于 $1$ 的树上。

但这样一些夜雀可能无法顺利完成歌会，会遇到“无处可走”的情况，于是夜雀们决定选择若干个大树作为飞行点。如果一个夜雀到达了某个飞行点，那么下一时刻她除了能移动到编号相邻的树上，还能**到达其他的飞行点**。

然而，飞行点太多容易使得歌会变得非常混乱。因此，米斯蒂娅希望最小化飞行点的数目。你能帮帮她吗？

inputFormat:
第一行三个整数 $n,m,t$。含义如题面所示。
第二行 $n$ 个整数，第 $i$ 个整数表示 $h_i$。
第三行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 只夜雀的位置 $p_i$。

outputFormat: 输出一行，一个整数，表示最少的飞行点数量。

hint:
#### 样例 1 解释

一个最优方案是，分别在第 $2,5$ 棵树建立飞行点，下表为各夜雀的一个可行移动方案：

$$\def{\arraystretch}{1.8}
\begin{array}{|c|c|c|c|} \hline
\textsf{\textbf{夜雀编号}} & \textsf{\textbf{时刻 $0$ 所在位置}} & \textsf{\textbf{时刻 $1$ 所在位置}} & \textsf{\textbf{时刻 $2 \sim 4$ 所在位置}} \cr\hline
\textsf1 & 5 & 5 & 5 \cr\hline
\textsf2 & 3 & 2 & 5 \cr\hline
\textsf3 & 2 & 5 & 5 \cr\hline
\end{array}$$

可以证明不存在更优解。

---

#### 数据范围及约定

$$
\def{\arraystretch}{1.6}
\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值} \cr\hline
1 & 16 & - & 15 \cr\hline
2 & 5\times 10^5 & \text{A} & 5 \cr\hline
3 & 5\times 10^5 & \text{B} & 15 \cr\hline
4 & 10^3 & - & 25 \cr\hline
5 & 5\times 10^5 & - & 20 \cr\hline
6 & 5\times 10^6 & - & 20 \cr\hline
\end{array}$$

- 特殊性质 A：$\min(h_i) > t$。
- 特殊性质 B：$t > n$ 且 $h_i \in \{1,t-1,t+1\}$。

对于 $100\%$ 的数据，满足 $1 \le n,m \le 5 \times 10^6$，$1 \le h_i,t \le 10^9$，$1 \le p_i \le n$。保证 $p$ 互不相同，且 $\max(h_i) > t$。

---

#### 提示

显然你可以将所有位置都作为飞行点，然后在第 1 时刻让所有夜雀都飞到一棵 $h_i > t$ 的树来得到一组答案为 $n$ 的合法解。因此本题不会存在无解情况。


title: 「PMOI-4」可怜的团主

description:
lnlhm 被塞给了一张 $n$ 个点 $m$ 条边的**简单无向连通**图。很快，他就被 ducati 和 b6e0 盯上了。

ducati 希望能够从中找到**恰好** $\left \lceil \frac n 6 \right \rceil$ 条**不同**的路径，使得所有的点都被至少一条路径经过。

b6e0 希望找到一个大小**恰好**为 $\lfloor \frac n 3 \rfloor$ 的节点集合，使得它们之间**两两没有边**。

lnlhm 知道，如果他没有满足某个人的要求，那么他就会被揍。因此，他向你求助：是否存在一种选择边或点的方案，使得**最多被一个人揍**？

inputFormat:
第一行两个正整数 $n,m$，表示点数以及边数。

下面 $m$ 行，每行两个点 $u,v$，描述一条**无向边**。

outputFormat:
若想要满足 ducati 的需求，在第一行输出 $1$，并在下面的 $\left \lceil \frac {n} 6 \right \rceil$ 行中，每行输出一条路径，你需要保证这些路径两两不同（例如，不能同时输出 $5 \to 3 \to 1$ 和 $1 \to 3 \to 5$）。输出一条路径的格式如下：

- 先输出一个正整数 $k(1\le k\le n)$，表示路径经过的节点数。

- 接下来 $k$ 个正整数，表示路径上的点，点之间用空格隔开。你需要保证，每相邻两个点之间有连边，不存在一个点被**某条**路径经过不少于两次，且每个点均被至少一条路径经过。

若想要满足 b6e0 的需求，在第一行输出 $2$，并在第二行中输出 $\lfloor \frac n 3 \rfloor$ 个点表示选出的独立集，之间用空格隔开。

特别的，若两个人的要求一个也无法满足，那么输出一行 `Poor lnlhm!`。

hint:
【样例解释】

对于第一组样例，我们只需要为 b6e0 选出节点集合 $\{1,4\}$ 即可。注意，$\{1,5\}\{1,6\}\{2,4\}\{2,6\}\{3,4\}\{3,5\}\{3,6\}$ 同样合法。

对于第二组样例，我们只需要为 ducati 选出路径 $1 \to 2 \to 3 \to 4 \to 5 \to 6$ 即可。

【数据范围】

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

- Subtask 1（20pts）：$n,m\le10$。
- Subtask 2（20pts）：保证图为一棵树。
- Subtask 3（60pts）：无特殊限制。

对于 $100\%$ 的数据满足，$3\le n\le10^3$，$3\le m\le\dfrac{n(n-1)}2$，保证给定的图为简单无向连通图。

**温馨提示: 输入量较大，请使用较快的读入方式。**


title: [NOI2021] 轻重边

description:
小 W 有一棵 $n$ 个结点的树，树上的每一条边可能是轻边或者重边。接下来你需要对树进行 $m$ 次操作，在所有操作开始前，树上所有边都是轻边。操作有以下两种：
1. 给定两个点 $a$ 和 $b$，首先对于 $a$ 到 $b$ 路径上的所有点 $x$（包含 $a$ 和 $b$），你要将与 $x$ 相连的所有边变为轻边。然后再将 $a$ 到 $b$ 路径上包含的所有边变为重边。
2. 给定两个点 $a$ 和 $b$，你需要计算当前 $a$ 到 $b$ 的路径上一共包含多少条重边。

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

第一行包含两个整数 $n$ 和 $m$，其中 $n$ 表示结点数量，$m$ 表示操作数量。

接下来 $n - 1$ 行，每行包含两个整数 $u\ v$，表示树上的一条边。

接下来 $m$ 行，每行包含三个整数 ${\mathit{op}}_i\ a_i\ b_i$，描述一个操作，其中 ${\mathit{op}}_i = 1$ 表示第 $1$ 类操作，${\mathit{op}}_i = 2$ 表示第 $2$ 类操作。

数据保证 $a_i \neq b_i$。

outputFormat: 对于每一次第 $2$ 类操作，输出一行一个整数表示答案。

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

第 $1$ 次操作后，重边有：$(1, 3)$，$(3, 6)$，$(6, 7)$。

第 $2$ 次操作，包含的重边有：$(1, 3)$。

第 $3$ 次操作，包含的重边有：$(1, 3)$，$(3, 6)$，$(6, 7)$。

第 $4$ 次操作，首先 $(1, 3)$，$(3, 6)$ 变为轻边，之后 $(1, 3)$，$(3, 5)$ 变为重边。

第 $5$ 次操作，包含的重边有：$(1, 3)$，$(6, 7)$。

第 $6$ 次操作，首先 $(1, 3)$ 变为轻边，之后 $(1, 2)$ 变为重边。

第 $7$ 次操作，包含的重边有：$(6, 7)$。

**【样例 #2】**

见附件 `edge/edge2.in` 与 `edge/edge2.ans`。

该样例约束与测试点 $3 \sim 6$ 一致。

**【样例 #3】**

见附件 `edge/edge3.in` 与 `edge/edge3.ans`。

该样例约束与测试点 $9 \sim 10$ 一致。

**【样例 #4】**

见附件 `edge/edge4.in` 与 `edge/edge4.ans`。

该样例约束与测试点 $11 \sim 14$ 一致。

**【样例 #5】**

见附件 `edge/edge5.in` 与 `edge/edge5.ans`。

该样例约束与测试点 $17 \sim 20$ 一致。

**【数据范围】**

对于所有测试数据：$T \le 3$，$1 \le n, m \le {10}^5$。

| 测试点编号 | $n, m \le $ | 特殊性质 |
|:-:|:-:|:-:|
| $1 \sim 2$ | $10$ | 无 |
| $3 \sim 6$ | $5000$ | 无 |
| $7 \sim 8$ | ${10}^5$ | A，B |
| $9 \sim 10$ | ${10}^5$ | A |
| $11 \sim 14$ | ${10}^5$ | B |
| $15 \sim 16$ | $2\times {10}^4$ | 无 |
| $17 \sim 20$ | ${10}^5$ | 无 |

特殊性质 A：树的形态是一条链。

特殊性质 B：第 $2$ 类操作给出的 $a_i$ 和 $b_i$ 之间有边直接相连。


title: [NOI2021] 路径交点

description:
小 L 有一个有向图，图中的顶点可以分为 $k$ 层，第 $i$ 层有 $n_i$ 个顶点，第 $1$ 层与第 $k$ 层**顶点数相同**，即 $n_1 = n_k$，且对于第 $j$（$2 \leq j \leq k-1$）层，$n_1 \leq n_j \leq 2n_1$。对于第 $j$（$1 \leq j < k$）层的顶点，以它们为起点的边只会连向第 $j + 1$ 层的顶点。没有边连向第 $1$ 层的顶点，第 $k$ 层的顶点不会向其他顶点连边。

现在小 L 要从这个图中选出 $n_1$ 条路径，每条路径以第 $1$ 层顶点为起点，第 $k$ 层顶点为终点，并要求**图中的每个顶点至多出现在一条路径中**。更具体地，把每一层顶点按照 $1,2,\ldots,n_i$ 进行编号，则每条路径可以写为一个 $k$ 元组 $(p_1,p_2,\ldots,p_k)$，表示这条路径依次经过第 $j$ 层的 $p_j$（$1 \leq p_j \leq n_j$）号顶点，并且第 $j$（$1 \leq j < k$）层的 $p_j$ 号顶点有一条边连向第 $j+1$ 层的第 $p_{j+1}$ 号顶点。

小 L 把这些路径画在了纸上，发现它们会产生若干个交点。对于两条路径 $P,Q$，分别设它们在第 $j$ 层与第 $j+1$ 层之间的连边为 $(P_j,P_{j+1})$ 与 $(Q_j,Q_{j+1})$，若，

$$(P_j-Q_j)\times(P_{j+1}-Q_{j+1})<0$$

则称它们在第 $j$ 层后产生了一个交点。两条路径的交点数为它们在第 $1, 2,\ldots,k - 1$ 层后产生的交点总数。对于整个路径方案，它的交点数为**两两不同路径间交点数之和**。例如下图是一个 $3$ 条路径，共 $3$ 个交点的例子，其中红色点是交点。

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

小 L 现在想知道有偶数个交点的路径方案数比有奇数个交点的路径方案数多多少个。两个路径方案被视为相同的，当且仅当它们的 $n_1$ 条路径按第一层起点编号顺序写下的 $k$ 元组能对应相同。由于最后的结果可能很大，请你输出它对 $998244353$（一个大质数）取模后的值。

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

第一行一个正整数 $k$，表示一共有 $k$ 层顶点。

第二行包含 $k$ 个整数 $n_1,n_2,\ldots,n_k$，依次表示每一层的顶点数量。保证 $n_1=n_k$，且 $n_1 \leq n_i \leq 2n_1$（$2 \leq i \leq k-1$）。

第三行包含 $k-1$ 个整数 $m_1,m_2,\ldots,m_{k-1}$，依次表示第 $j$ 层顶点到第 $j+1$ 层顶点的边数。保证 $m_j \leq n_j \times n_{j+1}$。

接下来有 $k-1$ 段输入。第 $j$（$1 \leq j < k$）段输入包含 $m_j$ 行，每一行两个整数 $u,v$，表示第 $j$ 层的 $u$ 号顶点有一条边连向第 $j+1$ 层的 $v$ 号顶点。

数据保证图中不会出现重边。

outputFormat: 输出共 $T$ 行，每行一个整数，表示该组数据的答案对 $998244353$ 取模后的值。


title: [NOI2021] 庆典

description:
C 国是一个繁荣昌盛的国家，它由 $n$ 座城市和 $m$ 条有向道路组成，城市从 $1$ 到 $n$ 编号。如果从 $x$ 号城市出发，经过若干条道路后能到达 $y$ 号城市，那么我们称 $x$ 号城市可到达 $y$ 号城市，记作 $x\Rightarrow y$。C 国的道路有一个特点：对于三座城市 $x$，$y$，$z$，若 $x\Rightarrow z$ 且 $y\Rightarrow z$，那么有 $x\Rightarrow y$ 或 $y\Rightarrow x$。

再过一个月就是 C 国成立的千年纪念日，所以 C 国的人民正在筹备盛大的游行庆典。目前 C 国得知接下来会有 $q$ 次游行计划，第 $i$ 次游行希望从城市 $s_i$ 出发，经过若干个城市后，在城市 $t_i$ 结束，且在游行过程中，**一个城市可以被经过多次**。为了增加游行的乐趣，每次游行还会**临时**修建出 $k$（$0 \le k \le 2$）条有向道路专门供本次游行使用，即其它游行计划不能通过本次游行修建的道路。

现在 C 国想知道，每次游行计划可能会**经过多少座城市**。

注意：临时修建出的道路**可以不满足 C 国道路原有的特点**。

inputFormat:
第一行包含四个整数 $n,m,q,k$，分别表示城市数、道路数、游行计划数以及每次游行临时修建的道路数。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示一条有向道路 $u\rightarrow v$。

接下来 $q$ 行，每行前两个整数 $s_i,t_i$，表示每次游行的起点与终点；这行接下来有 $k$ 对整数 $a,b$，每对整数表示一条临时添加的有向道路 $a\rightarrow b$。

数据保证，将 C 国原有的有向道路视为无向道路后，所有城市可以互达。

outputFormat: 对于每次询问，输出一行一个整数表示答案。如果一次游行从起点出发无法到达终点，输出 $0$ 即可。

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

第 $1$ 次计划，起点为 $1$ 号点，终点为 $4$ 号点，临时修建道路为 $5\rightarrow1$，最终可能经过的城市编号为 $\{1,2,4,5\}$。

第 $2$ 次计划，起点为 $2$ 号点，终点为 $3$ 号点，临时修建道路为 $5\rightarrow3$，最终可能经过的城市编号为 $\{2,3,4,5\}$。

第 $3$ 次计划，起点为 $1$ 号点，终点为 $2$ 号点，临时修建道路为 $5\rightarrow2$，最终可能经过的城市编号为 $\{1,2,4,5\}$。

第 $4$ 次计划，起点为 $3$ 号点，终点为 $4$ 号点，临时修建道路为 $5\rightarrow1$，最终从 $3$ 号点出发无法到达 $4$ 号点。

**【样例 #2】**

见附件 `celebration/celebration2.in` 与 `celebration/celebration2.ans`。

该样例约束与测试点 $5 \sim 7$ 一致。

**【样例 #3】**

见附件 `celebration/celebration3.in` 与 `celebration/celebration3.ans`。

该样例约束与测试点 $10 \sim 11$ 一致。

**【样例 #4】**

见附件 `celebration/celebration4.in` 与 `celebration/celebration4.ans`。

该样例约束与测试点 $15 \sim 16$ 一致。

**【样例 #5】**

见附件 `celebration/celebration5.in` 与 `celebration/celebration5.ans`。

该样例约束与测试点 $20 \sim 25$ 一致。

**【数据范围】**

对于所有测试点，$1 \le n,q \le 3 \times {10}^5$，$n - 1 \le m \le 6 \times {10}^5$，$0 \le k \le 2$。

| 测试点编号 | $n, q \le$ | $k$ | 特殊性质 |
|:-:|:-:|:-:|:-:|
| $1 \sim 4$ | $5$ | $= 0$ | 无 |
| $5 \sim 7$ | $1000$ | $\le 2$ | 无 |
| $8 \sim 9$ | $3 \times {10}^5$ | $= 0$ | $m = n - 1$ |
| $10 \sim 11$ | $3 \times {10}^5$ | $= 1$ | $m = n - 1$ |
| $12 \sim 14$ | $3 \times {10}^5$ | $= 2$ | $m = n - 1$ |
| $15 \sim 16$ | $3 \times {10}^5$ | $= 0$ | 无 |
| $17 \sim 19$ | $3 \times {10}^5$ | $= 1$ | 无 |
| $20 \sim 25$ | $3 \times {10}^5$ | $= 2$ | 无 |


title: 「RdOI R3」race

description: 某足球赛事上，A 国队和 B 国队共进行了 $n$ 场比赛。比赛采用积分赛制，胜者队伍得 $a$ 分，败者队伍得 $b$ 分，若打平则双方各得 $c$ 分。现已知 A 国队总进球数 $d$ 球，B 国队总进球数 $e$ 球，求 A 国队的最大可能得分和最小可能得分。

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

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

对于每组数据，输入一行六个整数 $n,a,b,c,d,e$。

outputFormat: 对于每组数据，输出一行两个整数，用空格分隔，表示最大可能得分和最小可能得分。


title: [NOI2021] 量子通信

background: 由于评测性能差异，本题时限 +0.5s。

description:
小 Z 正在自学量子计算机相关知识，最近他在研究量子通信章节，并遇到了一个有趣的问题。在该问题中，Alice 和 Bob 正在进行量子通信，它们的通信语言是一个大小为 $n$ 的字典 $S$，在该字典中，每一个单词 $s_i$（$1 \le i \le n$）都可以用一个 $\boldsymbol{256}$ **位的** $\boldsymbol{01}$ **串**来表示。在本题中 $s_i$ 可以通过调用函数 `gen` 来生成，选手可以在题目目录下的 `gen.cpp` 中查看，该函数的参数 `n`、`a1`、`a2` 将由输入数据给出。

Alice 和 Bob 接下来要进行 $m$ 次通信，每次通信由 Alice 向 Bob 传输**恰好一个**字典中的单词。然而，两人使用的通信信道并不可靠，会受到噪音的干扰。更具体地，对于第 $i$ 次传输，记 Alice 传输的原单词为 $x_i$，该 $01$ 串会受噪音干扰而**翻转最多** $\boldsymbol{k_i}$ **位**。换句话说，记 Bob 这次收到的 $01$ 串为 $y_i$，它与 $x_i$ 相比，可能有最多 $k_i$ 位是不同的，并且 $y_i$ 可能不在字典 $S$ 中出现。

与此同时，Bob 得知坏人 Eve 也潜入了两人的通信信道，并准备干扰两人的通信。他的干扰方式是将 Bob 收到的 $01$ 串变为任意的 $256$ 位 $01$ 串，并且这个串可能不在字典 $S$ 中出现。Eve 非常狡猾，他**不一定**会对每次通信都进行干扰。

现在 Bob 找来了你帮忙，对于接下来的每次通信，你需要根据 Bob 最终收到的 $01$ 串以及这次通信的噪音干扰阈值 $k_i$（$0 \le k_i \le 15$），判断这次通信是否有可能没有受到 Eve 的干扰（即 Bob 收到的 $01$ 串可以由字典中的某个单词翻转至多 $k_i$ 位后得到）。本次通信如果有可能没受到 Eve 干扰，请你输出 $1$，否则输出 $0$。Bob 很信任你的能力，所以你需要**在线地回答结果，具体要求见输入格式**。

为了降低读入用时， Bob 收到的串将用**长度为** $\boldsymbol{64}$ **的** $\boldsymbol{16}$ **进制串**给出，$16$ 进制串中包含数字字符 $\texttt{0} \sim \texttt{9}$ 与大写英文字母 $\texttt{A} \sim \texttt{F}$，其中字符 $\texttt{A} \sim \texttt{F}$ 依次表示数值 $10 \sim 15$。

$16$ 进制串可以逐位转化为 $01$ 串，例如：`5` 对应 `0101`，`A` 对应 `1010`，`C` 对应 `1100`。

inputFormat:
输入数据第一行包含四个非负整数 $n, m, a_1, a_2$，分别表示字典大小，通信次数，以及 `gen` 函数中参数 `a1` 和 `a2` 的初始值。

选手需要在自己的程序中调用题目描述中提到的 `gen` 函数生成单词表，选手可以复制并使用 `gen.cpp` 中的代码，程序中的布尔数组 `s[N+1][256]` 即为所有的单词。

接下来 $m$ 行，每行包含一个长度为 $64$ 的 $16$ 进制串和一个非负整数 $k_i$，分别表示第 $i$ 次通信 Bob 最终收到的 $01$ 串和噪音干扰阈值。

为了强制选手**在线地回答询问**，选手根据 $16$ 进制串还原出 $256$ 位 $01$ 串后，将 $01$ 串每一位异或上 ${\mathit{lastans}}$ 才能得到这次通信中 Bob 收到的真实 $01$ 串，其中 ${\mathit{lastans}} \in \{ 0, 1 \}$ 表示上一次询问的答案，第一个询问前 ${\mathit{lastans}}$ 初始值为 0。

注意：使用 `scanf` 和 `printf` 函数读入或输出 `unsigned long long` 类型变量时，对应的占位符为 `llu`。

outputFormat: 输出共 $m$ 行，每行一个整数 $0$ 或 $1$ 表示当前询问的答案。

samples:
见附件中的 qi/qi1.in
见附件中的 qi/qi1.ans

samples:
见附件中的 qi/qi2.in
见附件中的 qi/qi2.ans

samples:
见附件中的 qi/qi3.in
见附件中的 qi/qi3.ans


title: [NOI2021] 密码箱

description:
Yelekastee 是 U 国著名的考古学家。在最近的一次考古行动中，他发掘出了一个远古时期的密码箱。经过周密而严谨的考证，Yelekastee 得知密码箱的密码和某一个数列 $\{ a_n \}$ 相关。数列 $\{ a_n \}$ 可以用如下方式构造出来：

1. 初始时数列长度为 $2$ 且有 $a_0 = 0, a_1 = 1$；
2. 对数列依次进行若干次操作，其中每次操作是以下两种类型之一：
  - `W` 类型：给数列的**最后一项**加 $1$。
  - `E` 类型：若数列的**最后一项**为 $1$，则给倒数第二项加 $1$；否则先给数列的**最后一项**减 $1$，接着在数列尾再加两项，两项的值都是 $1$。

受到技术限制，密码箱并没有办法完整检查整个数列，因此密码箱的密码设定为数列 $\{ a_n \}$ 经过函数 $f$ 作用后的值，其中 $f$ 的定义如下：

$$ f(a_0, \ldots , a_{k - 1}, a_k) = \begin{cases} a_0, & k = 0 \\ f \! \left( a_0, a_1, \ldots , a_{k - 2}, a_{k - 1} + \frac{1}{a_k} \right) \! , & k \ge 1 \end{cases} $$

Yelekastee 并不擅长运算，因此他找到了你，希望你能根据他提供的操作序列计算出密码箱的密码。不幸的是，他的记性并不是很好，因此他会随时对提供的操作序列做出一些修改，这些修改包括以下三种：

- `APPEND c`，在现有操作序列后追加一次 `c` 类型操作，其中 `c` 为字符 `W` 或 `E`。
- `FLIP l r`，反转现有操作序列中第 $l$ 个至第 $r$ 个（下标从 $1$ 开始，修改包含端点 $l$ 和 $r$，下同）操作，即所有 `W` 变为 `E`，所有 `E` 变为 `W`。
- `REVERSE l r`，翻转现有操作序列中第 $l$ 个至第 $r$ 个操作，也就是将这个区间中的操作逆序。

inputFormat:
输入第一行包含两个正整数 $n, q$，分别表示初始的操作序列长度和修改的次数。

第二行包含一个长为 $n$ 且仅包含大写字母 `W` 和 `E` 的字符串，表示初始操作序列。

接下来 $q$ 行，每行表示一次修改。每种修改的格式如【题目描述】所述。

outputFormat:
输出共 $q + 1$ 行，每行两个整数，其中第一行表示初始操作序列对应的密码，接下来 $q$ 行则分别输出每次修改之后的操作序列对应的密码。

容易发现密码一定是正有理数。若真实的密码为 $\frac{a}{b}$，其中 $a, b > 0$ 且 $\gcd(a, b) = 1$，则你需要在对应的行内顺次输出 $a$ 和 $b$ 模 $998244353$ 后的余数。

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

| | 操作序列 | 数列 $\{ a_n \}$ | 密码 |
|:-:|:-:|:-:|:-:|
| 初始 | `WE` | $(0, 1, 1, 1)$ | $\frac{2}{3}$ |
| 第一次修改后 | `WEE` | $(0, 1, 2, 1)$ | $\frac{3}{4}$ |
| 第二次修改后 | `EWE` | $(1, 1, 1, 1)$ | $\frac{5}{3}$ |
| 第三次修改后 | `EEW` | $(2, 2)$ | $\frac{5}{2}$ |

**【样例 #2】**

见附件 `code/code2.in` 与 `code/code2.ans`。

该样例与测试数据 $1 \sim 4$ 满足同样的约束条件。

**【样例 #3】**

见附件 `code/code3.in` 与 `code/code3.ans`。

该样例与测试数据 $5 \sim 7$ 满足同样的约束条件。

**【样例 #4】**

见附件 `code/code4.in` 与 `code/code4.ans`。

该样例与测试数据 $8 \sim 10$ 满足同样的约束条件。

**【样例 #5】**

见附件 `code/code5.in` 与 `code/code5.ans`。

该样例与测试数据 $15 \sim 20$ 满足同样的约束条件。

**【数据范围】**

对于所有测试点：$1 \le n \le {10}^5$，$1 \le q \le {10}^5$。

对于 `APPEND` 修改，保证给出的 `c` 为大写英文字母 `W` 或 `E`。

对于 `FLIP` 和 `REVERSE` 修改，保证 $1 \le l \le r \le L$，其中 $L$ 是当前操作序列的长度。

请注意由于有 `APPEND` 操作，操作序列的长度最大可能有 $2 \times {10}^5$。

| 测试点编号 | $n, q \le$ | 特殊限制 |
|:-:|:-:|:-:|
| $1 \sim 4$ | $2000$ | 无 |
| $5 \sim 7$ | ${10}^5$ | A |
| $8 \sim 10$ | ${10}^5$ | B，C |
| $11 \sim 14$ | ${10}^5$ | C |
| $15 \sim 20$ | ${10}^5$ | 无 |

特殊限制 A：保证在任意时刻操作序列中不会出现连续相同的两个字符。

特殊限制 B：保证没有 `FLIP` 修改。

特殊限制 C：保证没有 `REVERSE` 修改。


title: [NOI2021] 机器人游戏

description:
小 R 有 $m$（$1 \le m \le 1000$）个机器人和 $m$ 张纸带，第 $i$（$1 \le i \le m$）个机器人负责对第 $i$ 张纸带进行操作。对于每张纸带，它们都被从左到右分成了 $n$（$1 \le n \le 32$）个格子，依次编号为 $0, 1, \ldots , n - 1$。每个格子有 $3$ 种状态：1. 格子上写有数字 $0$；2. 格子上写有数字 $1$；3. 格子是一个空格子。

在任意时刻，机器人**必须**站在纸带上的一个格子中。在设定好机器人在纸带上的初始位置后，第 $i$ 个机器人会依次执行预先设定的操作序列 $S_i$，操作由 `R`、`0`、`1`、`*` 四种字符组成，其中：

1. `R` 表示机器人向右走一格，如果右边没有格子，则机器人会原地爆炸；
2. `0` 表示如果机器人所在格子非空，则将该格子上的数字改为 $0$，否则不修改；
3. `1` 表示如果机器人所在格子非空，则将该格子上的数字改为 $1$，否则不修改；
4. `*` 表示如果机器人所在格子非空，则将格子上的数字 $x$ 改为 $1 - x$，否则不修改。

第 $i$ 张纸带的状态可以用一个长度为 $n$ 的序列表示，每个元素为 `0`、`1` 或 `-`（空格子），依次表示其每个格子的状态。第 $i$ 张纸带的初始状态称为机器人 $i$ 的输入 $X_i$，操作执行完成后纸带的状态称为机器人 $i$ 的输出 $Y_i$。注意，如果机器人爆炸了，那么这个机器人就没有输出。

可以发现，如果一个格子为空，那么机器人永远不会修改它。所以每个机器人都有如下特性：如果第 $i$ 个机器人所在的纸带上的**所有格子**都为空，那么它就不会执行任何操作，它的输出即为所有格子都为空。

现在小 R 给定了每一个机器人的输入 $X_i$（即每张纸带的初始状态）以及目标输出 $Y_i$。小 R 希望小 D 找到一个位置 $p$（$0 \le p < n$），使得**所有机器人**都能以其所在纸带的第 $p$ 个格子为初始位置，在不爆炸的情况下执行完所有操作，并且满足第 $i$ 个机器人的输出为 $Y_i$。

小 D 花了几毫秒解决了问题，现在他想知道，有多少个输入和输出的组合方式使得上述问题有解，即有多少种为每个机器人设定输入 $X_0, X_1, \ldots , X_{m - 1}$ 和目标输出 $Y_0, Y_1, \ldots , Y_{m - 1}$ 的方式，使得至少存在一个位置 $p$（$0 \le p < n$），使得所有机器人都能以其所在纸带的第 $p$ 个格子为起点，在不爆炸的情况下执行完所有操作，且满足第 $i$ 个机器人的输出为 $Y_i$。请你帮助小 D 解决这个问题，由于最终的答案可能很大，请你输出答案对 ${10}^9 + 7$ 取模后的余数。

两个组合方式不同当且仅当，存在至少一个机器人，它的输入或是目标输出在两个方式中不同。

inputFormat:
第一行包含两个正整数 $n, m$，分别表示每张纸带上的格子数和纸带数量。

接下来 $m$ 行，第 $i$ 行输入一个仅包含 `R` `0` `1` `*` 这四种字符的字符串 $S_i$，表示第 $i$ 个机器人的操作序列。

outputFormat: 仅一行一个正整数，表示答案模 ${10}^9 + 7$ 后的余数。

samples:
见附件中的 robot/robot3.in
见附件中的 robot/robot3.ans

samples:
见附件中的 robot/robot4.in
见附件中的 robot/robot4.ans

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

| 方案编号 | 输入 $X_0$ | 目标输出 $Y_0$ | 可行初始位置 $p$ |
|:-:|:-:|:-:|:-:|
| $1$ | `--` | `--` | $0, 1$ |
| $2$ | `0-` | `1-` | $0$ |
| $3$ | `1-` | `1-` | $0$ |
| $4$ | `-0` | `-1` | $0$ |
| $5$ | `-1` | `-0` | $0$ |
| $6$ | `00` | `11` | $0$ |
| $7$ | `10` | `11` | $0$ |
| $8$ | `01` | `10` | $0$ |
| $9$ | `11` | `10` | $0$ |

表中 `-` 表示空格子，注意方案 $1$ 中的输入和输出中有两个空格子。

当输入全为空时，初始位置可以是 $0$ 或 $1$，因为根据题意，输入全为空时机器人不会执行任何操作。

当输入不全为空时，初始位置只能为 $0$，如果初始位置为 $1$ 机器人一定会爆炸。所以此时实际执行的操作是将第一格的数字改为 $1$，并将第二格的数字 $x$ 改为 $1 - x$。

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

可以用容斥原理来计算这个样例。

1. 初始位置 $p = 0$ 可以使得执行完所有操作后满足条件。那么第一个机器人的纸带 $0$ 号格子要么输入输出都是空，要么目标输出是 $1$（输入无所谓），所以有 $3$ 种方案；$1$ 号格子要么输入输出都是空，要么目标输出是 $0$，也是 $3$ 种方案；$2$ 号格子要么输入输出都是空，要么输入和目标输出相同（因为没有对该格子执行任何操作），同样是 $3$ 种方案，共 $27$ 种方案。第二个机器人的 $0$ 号格子要么输入输出都是空，要么输入和目标输出不同，是 $3$ 种方案，$1$ 号和 $2$ 号格子也都是 $3$ 种方案，共 $27$ 种方案。所以总共 $27 \times 27 = 729$ 种方案。
2. 初始位置 $p = 1$ 可以使得执行完所有操作后满足条件。那么第一个机器人的纸带三个格子都是 $3$ 种方案，其中 $0$ 号格子要么输入输出都为空，要么相同；$1$ 号格子要么输入输出都为空，要么目标输出是 $1$；$2$ 号格子的输入输出要么都为空，要么输出是 $0$，共 $27$ 种方案。第二个机器人的 $1$ 号格子要么输入输出都是空，要么输入和目标输出不同，是 $3$ 种方案；$0$ 号和 $2$ 号格子要么输入输出都为空，要么输入输出相同，也都是 $3$ 种方案，共 $27$ 种方案。总共 $27 \times 27 = 729$ 种方案。
3. 初始位置 $p = 2$ 可以使得执行完所有操作后满足条件。那么第一个机器人的纸带必须输入输出全为空（否则爆炸），只有 $1$ 种方案。第二个机器人是 $27$ 种方案，总共 $27$ 种方案。
4. 初始位置 $p = 0, 1$ 都满足条件。这要求第一个机器人的 $1$ 号格子输入输出都为空；$0$ 号格子的输入输出都为空或都为 $1$；$2$ 号格子的输入输出都为空或都为 $0$，所以第一个机器人的纸带有 $4$ 种方案。第二个机器人 $0$ 号格子和 $1$ 号格子都为空，$2$ 号格子有 $3$ 种方案，第二个机器人的 $0$ 号和 $1$ 号格子必须都为空，$2$ 号格子要么输入输出都为空，要么输入和输出相同，有 $3$ 种方案。总共 $12$ 种方案。
5. 初始位置 $p = 0, 2$ 都满足条件。那么第一个机器人的纸带必须输入输出全为空（否则爆炸），只有 $1$ 种方案。第二个机器人 $0$ 号和 $2$ 号格子都为空，$1$ 号格子有 $3$ 种方案。总共 $3$ 种方案。
6. 初始位置 $p = 1, 2$ 都满足条件。那么第一个机器人的纸带必须输入输出全为空，只有 $1$ 种方案。第二个机器人 $1$ 号和 $2$ 号格子都为空，$0$ 号格子有 $3$ 种方案。总共 $3$ 种方案。
7. 初始位置 $p = 0, 1, 2$ 都满足条件。那么两个机器人的输入输出必须都为空，总共 $1$ 种方案。

根据容斥原理，最后的答案为 $729 + 729 + 27 - 12 - 3 - 3 + 1 = 1468$。

**【数据范围】**

对于所有测试点：$1 \le n \le 32$，$1 \le m \le 1000$，$1 \le \lvert S_i \rvert \le 100$。

| 测试点编号 | $n \le$ | $m \le$ | 特殊限制 |
|:-:|:-:|:-:|:-:|
| $1 \sim 2$ | $1$ | $1$ | 无 |
| $3$ | $8$ | $1$ | 无 |
| $4$ | $16$ | $1$ | 无 |
| $5 \sim 6$ | $32$ | $1$ | 无 |
| $7$ | $16$ | $5$ | 无 |
| $8 \sim 10$ | $32$ | $5$ | 无 |
| $11 \sim 12$ | $16$ | $1000$ | 无 |
| $13 \sim 15$ | $32$ | $1000$ | A |
| $16 \sim 21$ | $32$ | $1000$ | B |
| $22 \sim 25$ | $32$ | $1000$ | 无 |

特殊限制 A：操作序列中不存在 `R`。

特殊限制 B：每个操作序列中，`R` 的数量至多 $15$ 个。


title: [JRKSJ R2] Upper

description:
有 $n$ 张扑克，第 $i$ 张扑克上写有一个正整数 $a_i$。

现在要把扑克划分成若干个合法的连续子段，其中，一个连续子段 $[l,r]$ “合法”当且仅当这个子段同时满足两个条件：

* $a_l< a_r$
* $\gcd(a_l,a_r)>1$

请问最多能划分多少段。如果没有合法的划分方案，输出 $-1$ 即可。

如果您不知道 $\gcd$ 是什么意思，请看“提示”部分。

inputFormat:
第一行一个整数 $n$。\
第二行 $n$ 个整数表示序列 $a$。

outputFormat: 一个整数，如题目描述所示。


title: 「PMOI-5」破译

background: 2077 年，穿越的 Lanuxhem 为与 2021 年的 Silver187 联系，发明了一种图形转数字的密码。

description:
lhm 现在有一个边长为 $1$ 的正方形，现在要进行 $k$ 次分割，每次分割需要把位于图形中右下角的矩形继续分割成 $n \times n$ 的矩形。分割完成后所有矩形的个数即为破译后的答案。lhm 需要聪明的你帮助他解决这个问题。

注：由于题面形容比较困难，请移步至样例解释便于理解题意。

inputFormat:
输入数据共一行。
一行两个整数 $n,k$，含义如题目所示。

outputFormat:
输出格式共一行。
一行一个整数，表示最终答案。
由于答案可能过大，请把答案取模 $998244353$ 后输出。

hint:
### 样例解释

对于样例 #1，进行 $2$ 次分割，每次将右下角矩形分割为 $2\times 2$ 的矩形。

第一次分割，由于只有一个矩形，所以右下角矩形即为此矩形。分割前后如下：

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

变为

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

接下来进行第二次分割，将右下角矩形进行分割，分割为如下图形：

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

此图形包含 $7$ 个矩形，因此答案为 $7$。

### 数据规模与约定

对于 $10\%$ 的数据，$k=1$。
对于另 $20\%$ 的数据，$1 \leq n,k \leq 10$。
对于 $100\%$ 的数据，$1 \leq n,k \leq 10^9$。

---

$2022.7.10$：新增加一组 $\text{Hack}$ 数据。


title: 【模板】欧拉路径

description: 求有向图字典序最小的欧拉路径。

inputFormat:
第一行两个整数 $n,m$ 表示有向图的点数和边数。

接下来 $m$ 行每行两个整数 $u,v$ 表示存在一条 $u\to v$ 的有向边。

outputFormat:
如果不存在欧拉路径，输出一行 `No`。

否则输出一行 $m+1$ 个数字，表示字典序最小的欧拉路径。

hint:
对于 $50\%$ 的数据，$n,m\leq 10^3$。

对于 $100\%$ 的数据，$1\leq u,v\leq n\leq 10^5$，$m\leq 2\times 10^5$。

保证将有向边视为无向边后图连通。

[数据生成器](https://www.luogu.com.cn/paste/9oswk47n)


title: 「MCOI-08」Fast Enumeration

description:
Technoblade 将 Skyblock 抽象为一张 $n$（$n\le 50$）节点 $m$ 条边的简单有向图。他需要求出该图 **所有** 哈密尔顿回路，即所有排列 $p_1,p_2,\dots,p_n$ 使得 $p_1=1$ 并且 $p_1\to p_2\to \dots\to p_{n-1}\to p_n\to p_1$ 为一个合法路径。

**数据保证哈密尔顿回路数量非零并小于 $10^4$**。

**数据从所有合法数据随机采样。**

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

接下来 $m$ 行，每行两个正整数 $u,v$。

outputFormat: 输出若干行；每行输出 $n$ 个正整数，为一个哈密尔顿回路。按照递增字典序输出。

hint:
#### 样例 1 解释

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

有 $1$ 个哈密尔顿回路：

 - $1\to2\to3\to1$。

#### 样例 2 解释

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

有 $1$ 个哈密尔顿回路：

 - $1\to3\to4\to2\to1$。

#### 样例 3 解释

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

有 $2$ 个哈密尔顿回路：

 - $1\to2\to3\to4\to5\to1$；
 - $1\to2\to5\to3\to4\to1$。

#### 样例 4 解释

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

有 $2$ 个哈密尔顿回路：

 - $1\to2\to3\to4\to5\to1$；
 - $1\to3\to5\to2\to4\to1$。

#### 样例 5 解释

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

有 $3$ 个哈密尔顿回路：

 - $1\to5\to2\to3\to4\to6\to1$；
 - $1\to5\to2\to4\to6\to3\to1$；
 - $1\to5\to3\to4\to6\to2\to1$。

#### 样例 6 解释

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

有 $2$ 个哈密尔顿回路：

 - $1\to3\to2\to4\to6\to5\to1$；
 - $1\to5\to4\to6\to3\to2\to1$。

#### 样例 7 解释

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

有 $1$ 个哈密尔顿回路：

 - $1\to6\to5\to2\to4\to3\to1$。

#### 样例 8 解释

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

有 $12$ 个哈密尔顿回路：

 - $1\to2\to5\to4\to6\to3\to1$；
 - $1\to2\to5\to6\to3\to4\to1$；
 - $1\to5\to2\to3\to6\to4\to1$；
 - $1\to5\to2\to4\to6\to3\to1$；
 - $1\to5\to4\to6\to2\to3\to1$；
 - $1\to5\to4\to6\to3\to2\to1$；
 - $1\to5\to6\to2\to3\to4\to1$；
 - $1\to5\to6\to3\to2\to4\to1$；
 - $1\to5\to6\to3\to4\to2\to1$；
 - $1\to5\to6\to4\to2\to3\to1$；
 - $1\to6\to3\to2\to5\to4\to1$；
 - $1\to6\to3\to4\to2\to5\to1$。

#### 数据规模与约定

对于固定 $n$ 和 $P$，任意一张 $m$ 条边的图权重为 $\left(\frac{1}{P}\right)^m\left(\frac{P-1}{P}\right)^{n^2-n-m}$。

 - Subtask 1（1 pts）：为样例。
 - Subtask 2（16 pts）：$n=15$。
 - Subtask 3（20 pts）：$n=30$。
 - Subtask 4（26 pts）：$n=40$。
 - Subtask 5（37 pts）：$n=50$。


title: 冰魄吐息

background: [$\text{加强版}\Leftarrow$](/problem/U174529)

description:
$N$ 个点，第 $i$ 个点坐标为 $(x_i,y_i)$。

定义一束激光：$y=kx$，若点 $i$ 满足到该条直线距离 $\le d$，认为被激光击中。

求使用至多 $K$ 束激光，击毁图中所有点的最小代价 $d$。

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

第 $2 \sim N+1$ 行，每行两个非负整数 $x_i,y_i$，表示第 $i$ 个点的坐标。

outputFormat: 第一行输出最小代价 $d$，保留到小数点后 $2$ 位。

hint:
#### 样例说明

| ![](https://cdn.luogu.com.cn/upload/image_hosting/3a8bw1ub.png) | ![](https://cdn.luogu.com.cn/upload/image_hosting/3oih7er9.png) |
| :----------- | :----------- |
| 样例 $\#1$ 中两蓝色点坐标分别为 $(2,3)$ 和 $(6,3)$，到直线 $y=\frac{3}{4}x$ 的距离均为 $\frac{6}{5}=1.2$，因此输出 `1.20`。 | 样例 $\#2$ 中坐标为 $(4,0),(4,2)$ 的点与斜率为 $\frac{1}{4}$ 的直线之间距离为 $\frac{4}{17}\sqrt{17}\approx0.97014\dots$，因此输出 `0.97`。 |

可以证明两个样例中的方案是最优的，因此所求的 $d$ 是最小的。

#### 提示

1. 可能会用到的公式：点 $(x_0,y_0)$ 到直线 $y=kx$ 的距离是 $\dfrac{|y_0-kx_0|}{\sqrt{k^2+1}}$。
2. 对于 C++ 选手，**建议使用** 变量类型 `long double` 进行数值计算。
输出时请用形如 `printf("%.2Lf",ans)` 的形式输出答案，注意 `%.2Lf` 中的 L 是大写。
3. 本题中存在的浮点数运算可能较多，虽然已经增大时限，但仍然请注意常数因子对程序效率的影响。

#### 数据范围

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

记 $M$ 为所有 $x_i,y_i$ 的最大值。

| Subtask | Score | $M\le$ | $K\le$ |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $30$ | $10$ | $1$ |
| $2$ | $30$ | $1.5\times10^4$ | $1$ |
| $3$ | $40$ | |  |

对于 $100\%$ 的数据：$1\le N,M,K\le2.5\times10^4$。

所有数据均保证不存在相同的 $(x_i,y_i)$ 出现多次。

---

### 后记

冰魄战龙我吹爆 $\sim$

如果您也热爱 ddt，请在比赛结束后找到出题人，并把他虐一顿。

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

出题人推荐阅读题解：（优点：显然）https://www.luogu.com.cn/blog/_post/362493


title: 魔力滋生

background:
Source：[八仙敬酒](/paste/78f1vlm0)，这是可以点的。

- 吕洞宾——醉酒提壶力千钧；
- 铁拐李——旋肘膝撞醉还真；
- 汉钟离——跌步抱坛兜心顶；
- **蓝采和——单提敬酒拦腰破**；
- 张果老——醉酒抛杯踢连环；
- 曹国舅——仙人敬酒锁喉扣；
- 韩湘子——擒腕击胸醉吹箫；
- 何仙姑——弹腰献酒醉荡步。

description:
现有一个 $n$ 个点的树 $T$，满足任意一个结点的所连接的结点个数不超过 $2$。

现在依次对结点 $u=1\sim n$ 进行操作：

- 随机一个整数 $x(\ge k)$；
- 新建 $x$ 个结点，每个结点与 $u$ 之间连一条边。

显然操作完成后仍是一棵树 $T'$，其结点数为 $m=n+\sum x$。

已知操作后的树 $T'$ 及其结点数 $m$，请还原原树 $T$，若有多种方案，输出 **任意一组** 使得 $\color{black}n$ **最大** 的。

值得注意的是，我们进行还原和输出时，只关心树的形状，而不关心结点的相对编号。

inputFormat:
第一行输入两个正整数 $m,k$，表示树 $T'$ 的结点数、随机数 $x$ 的下限。

第 $2\sim m$ 行，每行输入两个正整数 $u,v$，表示树 $T'$ 中的一条边。

outputFormat:
第一行输出一个正整数 $n$，表示构造出树 $T$ 的结点数。

第 $2\sim n$ 行，每行输出两个正整数 $u,v$，表示树 $T$ 中的一条边。

输出的 $u,v$ 必须满足：$1\le u,v\le n$。

hint:
#### 样例说明

样例 $\#1$ 中，只有结点 $1$ 可能在树 $T$ 中：它对应的 $x$ 是 $4$。

样例 $\#2$ 中，结点 $1,2,3$ 在树 $T$ 中：结点 $1$ 对应的 $x$ 是 $4$，结点 $2,3$ 对应的 $x$ 是 $0$。

样例 $\#3$ 中，结点 $1,2,3$ 在树 $T$ 中：它们随机的 $x$ 均为 $2$。

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

样例 $\#3$ 给出一张示意图，图中红色结点表示树 $T$ 中的结点，图中所有结点都在树 $T'$ 上。

#### 数据范围

| Subtask | Score | $x=$ |
| :----------: | :----------: | :----------: |
| $1$ | $30$ | $0$ |
| $2$ | $30$ | $1$ |
| $3$ | $40$ |  |
| $4$ | $0$ | Hack |

说明：Subtask4 为不计分 Hack 数据，只有通过全部的 Subtask $1\sim4$ 才算 AC。

对于 $100\%$ 的数据：$1\le m\le10^5,k\in[0,m)$，数据输入保证有解。

---

### 后记

极光魔花好可爱 $\sim$

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


title: [CoE R5] 罚球

description:
有 $n$ 个人在玩罚球游戏，游戏规则如下：
- 每个人编号为 $1,2,\dots,n$，最开始由 $1$ 号罚球，接下来让下一个没有出局的人罚球。特殊地，$n$ 号的下一个是 $1$ 号。
- 如果罚球者没有碰到篮板，那么直接出局。
- 如果罚球者碰到篮板但没有进球，那么如果上一个人进球了，这个人就会出局，否则不会出局。
- 游戏结束的条件是最后只剩下一个人。

注意最开始的那个人碰到篮板但没有进球不出局。

这 $n$ 个人中，第 $i$ 个人碰不到篮板的概率为 $\dfrac{a_i}{1000}$，碰到篮板但没有进球的概率为 $\dfrac{b_i}{1000}$，求游戏结束时所有人总共罚球数量的期望值。

inputFormat:
第一行两个整数 $n,t$，为人数和子任务编号。
接下来 $n$ 行，每行两个整数，为 $a_i,b_i$，保证 $0\le a_i+b_i\le1000$。

outputFormat: 输出一行，为所有人总共罚球数量的期望值，如果永远不会结束，那么输出 $-1$。否则，输出对 $10^6+33$ 取模的值。


title: [COCI2014-2015#7] TETA

background: 你发现自己扮演的是一位在食堂担任收银员的好女士。这位女士被所有学生认为是好人的多种原因之一是，她关心你在访问食堂时尽可能少花钱。

description:
她是如何做到这一点的呢？策略其实很简单。在食堂里可以买到各种饭菜，其价格也是众所周知的。每天都会提供一份**套餐**。一份套餐包括 $4$ 份饭菜（通常是汤、主菜、配菜和甜点），但它的价格 $x$ 小于或等于其组成部分的价格总和。当这位女士注意到，如果你拿了套餐中的个别东西，并且如果按照一整个套餐的费用会花更少的钱，那么她就**一定会这样做**，而你会满载而归，口袋里剩下比原来更多的钱。

你拿着托盘站在收银台前，想知道你要付多少钱。写一个方案来确定它吧!

请注意：女士可以用多个套餐向你收费，这样价格会更便宜。

inputFormat:
输入共六行。

第一行输入一个整数 $k$，表示食堂今天供应的餐品总数。
第二行输入 $k$ 个整数，第 $i$ 个整数 $c_i$ 表示第 $i$ 个餐品的价格。
第三行输入一个整数 $x$，表示套餐的价格。
第四行输入 $4$ 个整数 $p_1,p_2,p_3,p_4$，分别表示套餐里面包含的 $4$ 种餐品。**保证 $p_i$ 互不相同**。
第五行输入一个整数 $t$，表示你点的餐品的个数。
第六行输入 $t$ 个整数，第 $i$ 个整数 $s_i$ 表示你点的餐品的编号。**不保证 $s_i$ 互不相同**。

outputFormat: 输出仅一行，一个整数，表示你今天在食堂的花费。

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

你点了 $1,3,4$ 这三个在套餐中的餐品，这三个餐品单点的总价为 $10+8+9=27$，大于套餐的价格 $14$，因此收银的女士会将这些餐品按照 $14$ 元收费。除此之外的 $6,7$ 两个餐品不在套餐中，因此单独收费。故总花费为 $14+5+3=22$。

**【样例 2 解释】**

你点了 $1,2$ 这两个在套餐中的餐品，这两个餐品单点的总价为 $12+4=16$，大于套餐的价格 $14$，因此收银的女士会将这些餐品按照 $14$ 元收费。此外还剩下一个 $1$ 号餐品和两个 $6$ 号餐品。由于一个 $1$ 号餐品的价格是 $12$，小于套餐的 $14$，而另外两个 $6$ 号餐品又不在套餐里出现，因此剩下的一个 $1$ 号餐品和两个 $6$ 号餐品都只能单独收费。因此总花费为 $14+12+3\times 2=32$。

**【数据范围】**

对于所有数据，$1\leqslant k,t\leqslant 20$，$1\leqslant c_i\leqslant 250$，$1\leqslant x<1000$，$1\leqslant p_i,s_i\leqslant k$。

**【题目来源】**

本题来源自 **_[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST 7](https://hsin.hr/coci/archive/2014_2015/contest7_tasks.pdf) T1 TETA_**，按照原题数据配置，满分 $50$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2014-2015#7] KRIZA

background: 某国的经济状况很糟糕，冰冻灾害袭击了整个国家，人们正在失去工作。然而，Sisyphus，本题的主角，已经为自己找到了一份新工作。从下周一开始，Sisyphus 将成为一家酒店的助理锁匠。当然，他首先需要向锁匠头子展示他的开锁能力。

description:
这就是锁匠头子给了 Sisyphus $n$ 把钥匙，放在一个大圆坠子上，蒙住他的眼睛并把他带进一个大房间的原因。这个房间里恰好有 $n$ 扇锁着的门，用 $1$ 到 $n$ 的数字表示。吊坠上的每一把钥匙都正好能打开一扇门，其中第 $i$ 把钥匙能打开第 $v_i$ 扇门。Sisyphus 的工作是将每一扇门解锁并再次上锁。他这样做的方式是沿着墙壁移动，不改变方向，直到他到达一扇门。当他走到一扇门前时，他尝试用从当前左数第一把钥匙来解锁。如果钥匙没有开锁，Sisyphus 就把它丢到最右边，并再用当前最左边的那一把钥匙再试一次，重复这个过程，直到他找到正确的钥匙为止。当他所有的门解锁时，他的工作就完成了。Sisyphus 打开的第一扇门用 $1$ 表示，下一扇用 $2$ 表示，后一扇用 $3$ 表示，以此类推......

Sisyphus 不知道的是，锁匠头子其实是在考验他的耐力，所以把他领到了一个圆形的房间。因此，Sisyphus 在解开并锁上最后一扇门后，会再次去解开并锁上第一扇门。因为他是一个勤奋而执着的家伙，Sisyphus 一直在做这项工作，几个小时都没有说一句话。只有在第 $k$ 次成功开锁和锁门后，他才开口说话："如果我知道到目前为止我把一把错误的钥匙放在门锁里有多少次就好了！" 你的任务是回答他的问题。

inputFormat:
输入共 $n+1$ 行。

第一行输入两个整数 $n,k$，分别表示 Sisyphus 拥有的的钥匙数量和他当前为止成功开锁和锁门的次数。
随后 $n$ 行，每行一个整数 $v_i$，表示第 $i$ 把钥匙对应能开的门的编号。

outputFormat: 输出仅一行，表示 Sisyphus 把一把错误的钥匙放在门锁里的次数。

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

以下是 Sisyphus 使用钥匙的情况，其中一个标红的数字表示他把错误的钥匙放在门锁里一次：

- 对第 $1$ 扇门进行开锁和锁门操作：$\color{Red}4~2~\color{default}1~3$
- 对第 $2$ 扇门进行开锁和锁门操作：$\color{Red}1~3~4~\color{default}2$
- 对第 $3$ 扇门进行开锁和锁门操作：$\color{Red}2~1~\color{default}3~4$
- 对第 $4$ 扇门进行开锁和锁门操作：$\color{Red}3~\color{default}4~2~1$
- 对第 $1$ 扇门进行开锁和锁门操作：$\color{Red}4~2~\color{default}1~3$
- 对第 $2$ 扇门进行开锁和锁门操作：$\color{Red}1~3~4~\color{default}2$

因此他把错误的钥匙放在门锁里的次数一共是 $2+3+2+1+2+3=13$。

**【数据范围】**

对于 $40\%$ 的数据，保证 $1\leqslant n,k\leqslant 1000$。
对于 $60\%$ 的数据，保证 $1\leqslant k\leqslant 5\times 10^4$。
对于所有数据，$1\leqslant v_i\leqslant n\leqslant 10^5$，$1\leqslant k\leqslant 10^9$。

**【题目来源】**

本题来源自 **_[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST 7](https://hsin.hr/coci/archive/2014_2015/contest7_tasks.pdf) T2 KRIZA_**，按照原题数据配置，满分 $80$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2014-2015#7] ACM

background: Zagreb 大学的团队的成员 Stjepan、Ivan 和 Gustav 正在摩洛哥参加 ACM 国际大学生程序设计竞赛的世界决赛。他们的技术指导 Goran 想出了一个无敌的策略，用于解决决赛中的题目。

description:
在一开始，每个团队成员迅速估计 $n$ 道题目中每题的难度。这些难度用 $1$ 到 $5$ 的数字描述，数字越大，难度也就越大。

在这之后，他们之间将分配任务。为了简单起见，任务阵列将被分成三部分，以便每个团队成员得到一个**非空**的连续任务序列来思考。这种分配是为了使估计的难度之和最小，而只计算被分配到该任务的团队成员的估计难度值。你的任务是计算这个最小的可能总和。

inputFormat:
输入共四行。

第一行输入一个整数 $n$，表示问题的数量。
第二到第四行，第 $i+1$ 行 $n$ 个整数 $d_{i,1},d_{i,2},\dots,d_{i,n}$，表示第 $i$ 号成员对于这 $n$ 道题目估计的难度。

outputFormat: 输出仅一行，一个整数，表示最小可能的估计难度总和。

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

给第 $1$ 号成员分配第 $1$ 题，给第 $2$ 号成员分配第 $3$ 道题，给第 $3$ 号成员分配第 $2$ 道题。这样分配的难度总和为 $1+1+2=4$。可以证明没有难度总和更小的分配方案。

**【数据范围】**

对于所有数据，$3\leqslant n\leqslant 1.5\times 10^5$，$1\leqslant d_{i,j}\leqslant 5$。

**【题目来源】**

本题来源自 **_[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST 7](https://hsin.hr/coci/archive/2014_2015/contest7_tasks.pdf) T3 ACM_**，按照原题数据配置，满分 $100$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2014-2015#7] JANJE

description:
年轻的 Bojan 现在是一名成功的电气工程专业学生，从小就喜欢涂色。想起童年时漫不经心的日子，他决定买一本涂色书和 $k$ 种颜色的颜料，然后开始工作。有趣的是，Bojan 不喜欢五颜六色的图片，所以他决定**每张图片最多使用三种不同的颜色着色**。此外，Bojan **永远不会用同一种颜色给两个相邻的区域上色**，如果两个区域的边缘至少有一个连接点，则被视为相邻。例如，下图用 $4$ 和 $3$ 表示的区域是相邻的，而区域 $1$ 和 $2$ 则不是。此外，下面这张图片的着色方式符合 Bojan 的所有要求。

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

在开始给一张图片上色之前，Bojan 会问自己有多少种方法可以给这张图上色，从而满足他的所有条件。鉴于 Bojan 是学电气工程的，可以理解的是，组合学不是他的强项，所以他向你寻求帮助。

inputFormat:
输入仅一行两个整数 $n,k$，分别代表涂色书里面的图片编号和 Bojan 的颜料拥有的颜色数量。

涂色书将会在附件中给出（即文件 `Happy coloring book.pdf`），涂色书里面的图片按照先后顺序依次编号为 $1$ 到 $8$。

outputFormat: 输出仅一行一个整数，代表 Bojan 在满足自己所有要求的上色方式的个数。

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

对于所有数据，$1\leqslant n\leqslant 8$，$1\leqslant k\leqslant 1000$。

**【题目来源】**

本题来源自 **_[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST 7](https://hsin.hr/coci/archive/2014_2015/contest7_tasks.pdf) T4 JANJE_**，按照原题数据配置，满分 $120$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2014-2015#7] PROSJEK

description: 给定一个有 $n$ 个整数的数列 $a$。请找出一个长度至少为 $k$ 的连续子序列，使这个子序列的所有数的平均值最大。

inputFormat:
输入共 $2$ 行。

第一行输入两个整数 $n,k$。
第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示数列 $a$ 的所有数。

outputFormat:
输出仅一行，一个实数，表示长度至少为 $k$ 的连续子序列的数的最大平均值。

在每个测试点中，只要你的程序给出的答案和标准答案的相对误差不超过 $10^{-3}$，你的程序就可以通过该测试点。

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

对于 $30\%$ 的数据，保证 $n\leqslant 5000$。
对于所有数据，$1\leqslant k\leqslant n\leqslant 3\times 10^5$，$1\leqslant a_i\leqslant 10^6$。

**【题目来源】**

本题来源自 **_[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST 7](https://hsin.hr/coci/archive/2014_2015/contest7_tasks.pdf) T5 PROSJEK_**，按照原题数据配置，满分 $140$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2014-2015#7] POLICE

description:
在图书管理员 Jurica 的图书馆里有 $n$ 个书架，每个书架有 $m$ 个位置，从左往右编号为 $1$ 到 $m$，并且每个位置上都可以放一本书。Jurica 是一个好的图书管理员，所以他决定对图书馆进行清点，如果有必要，就把不在自己位置上的书放回原来的位置。具体来说，现在第 $i$ 个书架上的第 $j$ 个位置上面摆着编号为 $a_{i,j}$ 的书（如果 $a_{i,j}=0$ 说明这个位置上面现在没有书），而原来在这个位置上摆着编号为 $b_{i,j}$ 的书（如果 $b_{i,j}=0$ 说明这个位置上面原来没有书）。他以下列操作移动书籍：

- 操作 $1$：如果左边或右边有空位，可以在书架上向左或向右移动图书。
- 操作 $2$：从书架上取下一本书，放在该书架或其他书架的空位上。

细心的 Jurica 如果手中有书，就不能移动书。此外，他**不能同时拿多于一本书**。

自从他不得不把维基百科印刷版的所有书卷从一楼搬到二楼后，Jurica 就一直背痛。因为他的背很疼，所以现在他想把所有的书放好，尽量少搬。请告诉他需要的执行**操作 $2$ 的次数**最少是多少，或者告诉他根本不可能把这些书搬回原来的位置。

inputFormat:
输入共 $2n+1$ 行。

第一行输入两个整数 $n,m$，分别表示书架个数和每个书架上的位置个数。
第 $2$ 到 $n+1$ 行，每行输入 $m$ 个整数 $a_{i,j}$，描述现在书架上摆书的情况。
第 $n+2$ 到 $2n+1$ 行，每行输入 $m$ 个整数 $b_{i,j}$，描述原来书架上摆书的情况。

**输入保证原来和现在出现的书籍完全相同。**

outputFormat:
如果 Jurica 根本不可能把这些书搬回原来的位置，则仅输出一个整数 $-1$。

否则，输出一行一个整数，表示执行**操作 $2$ 的最少次数**。

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

以下是 Jurica 的操作序列：

1. 操作 $1$：把 $1$ 号书籍移动到它右边的位置，也就是它所在书架上的第二个位置。
2. 操作 $2$：把 $2$ 号书籍搬到它所在书架上的第一个位置。
3. 操作 $2$：把 $5$ 号书籍搬到它所在书架上的第二个位置。

可以证明没有更少执行操作 $2$ 的方案。

**【数据范围】**

对于 $50\%$ 的数据，保证每本书在初始和最终状态下都会在同一个书架上。
对于所有数据，$1\leqslant n,m\leqslant 1000$。

**【题目来源】**

本题来源自 **_[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST 7](https://hsin.hr/coci/archive/2014_2015/contest7_tasks.pdf) T6 POLICE_**，按照原题数据配置，满分 $160$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: 「C.E.L.U-03」100%不公平的游戏

background: 今天 ice 出去玩了。原准备与 Alice 玩游戏的 Bob 只能和 Al 玩一场博弈游戏。

description:
这个游戏是在树上进行的。Bob 先手。Bob 和 Al 轮流进行以下操作，首先无法操作者判负。

- 在树上标记一条未被标记过的边。满足在每一次操作之后，存在一条简单路径遍历所有标记过的边。注意：这条简单路径**可以经过未标记过的边**。

如果给定的树对于 Bob 有必胜方案，输出 `Play now`，否则输出 `Restart`。

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

对于每组测试数据，第一行输入一个整数 $n$ 表示树的节点数。

接下来 $n-1$ 行，每行输入两个整数 $u,v$ 表示 $(u,v)$ 是树上的一条边。

outputFormat: 对于每组测试数据，输出一个字符串，大小写敏感。

hint:
**样例数据也可见附件** $\textbf{\textit{game.in}/\textit{game.out}}$。

### 样例解释 1

**第一组数据：**

先手选择边 $(2,5)$ 必胜：
若后手选择 $(1,2)$，先手选择 $(5,6)$ 可以获胜。
若后手选择 $(2,3)$，先手选择 $(5,9)$ 可以获胜。
若后手选择 $(3,4)$，先手选择 $(5,9)$ 可以获胜。
若后手选择 $(5,6)$，先手选择 $(1,2)$ 可以获胜。
若后手选择 $(5,9)$，先手选择 $(3,4)$ 可以获胜。
若后手选择 $(7,9)$，先手选择 $(2,3)$ 可以获胜。
若后手选择 $(8,9)$，先手选择 $(3,4)$ 可以获胜。
综上，无论后手选那一条边，都不会获得胜利。

**第二组数据：**

先手不存在必胜策略：
若先手选择 $(1,2)$，后手选择 $(2,3)$ 获胜。
若先手选择 $(2,3)$，后手选择 $(1,2)$ 获胜。

### 样例解释 2

各组数据详见下图，其中前两组数据与样例一相同。

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

---

### 数据范围

$2\leq n\leq5\times10^5$

$1\leq T\leq10^4$

$\sum n\leq1.5\times10^6$

数据保证给定的图是一棵树。

### 子任务
1. （8分）$n\leq6$。
2. （18分）$n\leq12,T\leq10$。
3. （6分） $n\leq28,T\leq10$。
4. （8分）$n\leq200,T\leq10$。
5. （30分）$n\leq2000,T\leq10$。
6. （6分）最多存在两个节点度数大于 $2$。
7. （12分）树的形态是一棵完全二叉树。
8. （12分）无特殊性质。


title: 「EZEC-9」GCD Tree

background: 规定 $\gcd(x,y)$ 表示 $x,y$ 的最大公约数，$\operatorname{lca}(x,y)$ 表示 $x$ 号节点和 $y$ 号节点的最近公共祖先。

description:
给你 $n$ 个点，编号分别为 $1,2,\ldots,n$，点权分别为 $a_1,a_2,\ldots,a_n$。

请你用这 $n$ 个点构造一棵树，使得 $\forall 1 \le i < j \le n$，$\gcd(a_i, a_j) = a_{\operatorname{lca}(i, j)}$。

若无解，报告之，否则输出树的形态。

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

第二行 $n$ 个整数 $a_1, a_2, \ldots , a_n$。

outputFormat:
若无解，输出 `-1`;

否则输出一行 $n$ 个整数，第 $i$ 个数表示 $i$ 号节点的父节点编号。特别地，若 $i$ 号节点为根节点则输出 `0`。

若有多解，输出任意一解即可。

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

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

-  Subtask 1（5 points）：$n = 2$。
-  Subtask 2（5 points）：所有 $a_i$ 均相等。
-  Subtask 3（5 points）：$n \le 5$。
-  Subtask 4（10 points）：保证有解。
-  Subtask 5（15 points）：$n \le 100$。
-  Subtask 6（15 points）：$n \le 10^3$。
-  Subtask 7（15 points）：$n \le 3 \times 10^3$。
-  Subtask 8（30 points）：无特殊限制。

对于 $100 \%$ 的数据，$2 \le n \le 10^5$，$1 \le a_i \le 10^6$。


title: [Aya Round 1 G] 咕噜论坛（post）

description:
「咕噜论坛」的一篇帖子下，有若干个不同的人对其进行了回复，这些评论形成了一个 $n\times m$ 的矩阵。

论坛管理员 prAB 发现这些评论者的名字颜色只有灰名、紫名和棕名三种，他决定「动用神权」来增加这些评论的整齐度。但是论坛站长超氧化铯（CsO2）可能会因为他「滥用神权」导致论坛「臭名昭著」而踢掉他的管理身份。所以 prAB **最多**只能动用 $k$ 次神权。已知他的神权有两种：

- 「暴政警告」：送一个灰名进陶片使他变成棕名。
- 「放人一马」：将一个棕名解封使他变成灰名。

由于「咕噜论坛」的管理员是至高无上的，对于评论中的紫名他无能为力。

prAB 认为在这些评论者的名字颜色中，最大的颜色相同的子矩阵的大小能代表这篇帖子评论的整齐度。所以他想知道，他动用完神权后评论的整齐度的最大值。

inputFormat:
- 第一行输入三个整数 $n,m,k$。
- 接下来 $n$ 行，每行输入一个长度为 $m$ 的字符串，代表评论矩阵中每个人名字的颜色。其中 `B` 代表棕名，`G` 代表灰名，`P` 代表紫名。

outputFormat:
- 第一行输出一个整数，表示整齐度的最大值。
- 下面 $n$ 行，每行输出一个长度为 $m$ 的字符串，格式同「输入格式」。代表修改完后每个人名字的颜色。如有多种方案输出则任意一种即可。

hint:
### 数据范围及约定

对于 $100\%$ 的数据，$1 \le n,m\le 500$，$0 \le k \le nm$。字符矩阵中只会出现大写字母 `B`、`G` 和 `P`。


title: [Ynoi2006] rsrams

description:
给定一个长度 $n$ 的序列 $a_1,\dots,a_n$，你需要处理 $m$ 次查询，每次查询给出 $l,r$，对应答案为：

$\sum\limits_{L=l}^r \sum\limits_{R=L}^r \sum\limits_{c=1}^n c\cdot \left[R-L+1<2\sum\limits_{i=L}^R [a_i=c] \right]$。

其中 $[\mathrm{cond}]$ 表示如果括号中的条件表达式为真，则对应 $[\mathrm{cond}]=1$，否则对应 $[\mathrm{cond}]=0$。

inputFormat:
第一行两个整数 $n,m$；

第二行 $n$ 个整数 $a_1,\dots,a_n$

接下来 $m$ 行，每行两个整数 $l,r$ 表示一次查询。

outputFormat: 共 $m$ 行，每行一个整数，表示每次询问的答案。

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

对于 $100\%$ 的数据，满足 $1\le n\le 10^6$，$1\le m\le 10^6$，$1\le a_i\le n$，$1\le l\le r\le n$。


title: 谜

background:
$\text{我需要你给我方向}$

$\text{哪怕要我独自穿过人海茫茫}$

$\text{为了你尝风霜}$

$\text{我流浪远方}$

$\text{需要你给我力量}$

$\text{无论如何我会坚强}$

$\text{只要你给我希望}$

[Source](https://www.kugou.com/song-36/1y5t3b.html)

description:
在一个大小为 $N$ 的数字三角形中：

- 第 $1$ 行为 $1$；
- 第 $2$ 行为 $2\sim3$；
- 第 $3$ 行为 $4\sim6$；
- 第 $4$ 行为 $7\sim10$；
- $\cdots~\cdots$
- 第 $N$ 行包含 $N$ 个数字，为 $\frac{N(N-1)}{2}+1\sim\frac{N(N+1)}{2}$。

下图展示了一个 $N=5$ 的数字三角形。

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

---

记 $(i,j)$ 表示第 $i$ 行第 $j$ 个数字。

已知 $(i,j)$ 能直接到达 $(i+1,j)$ 或 $(i+1,j+1)$，反之，$(i+1,j)$ 或 $(i+1,j+1)$ 也能直接到达 $(i,j)$。

现在任选一个数字作为起点，求 **连续** 地经过 $K$ 个 **不同** 的数字时，这 $K$ 个数的和的最大值，对 $10^9+7$ 取模。

inputFormat:
**本题包含多组数据测试。**

第一行，输入一个正整数 $T$，表示询问组数。

接下来 $T$ 行，每行输入两个正整数 $N,K$。

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


title: 「MCOI-06」Existence of Truth

description:
可能存在一个非负整数数序列 $a_1,a_2,\dots,a_n$ 使得 $0\le a_i<10^9+7$。

给定 $x_1,x_2,\dots,x_n$，$y_1,y_2,\dots,y_n$，$z_1,z_2,\dots,z_n$，已知对于 $1\le i\le n$ 满足：

$$x_i\left(\sum_{j=1}^ia_j\right)+y_i\left(\sum_{j=i}^na_j\right)\equiv z_i\pmod{10^9+7}$$

求 $a_1,a_2,\dots,a_n$。

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

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

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

接下来 $n$ 行，每行三个正整数 $x_i,y_i,z_i$。

outputFormat:
对于每一组数据，依次输出：

第一行一个非负整数 $k$，为合法解数量。

如果 $k=1$，第二行输出 $n$ 个非负整数，依次为 $a_1,a_2,\dots,a_n$。

hint:
#### 数据规模与约定

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

 - Subtask 1（10 pts）：$n=1$。
 - Subtask 2（19 pts）：$\sum n\le100$。
 - Subtask 3（19 pts）：$x_i=y_i=1$。
 - Subtask 4（22 pts）：保证有**唯一解。**
 - Subtask 5（30 pts）：无特殊限制。

对于所有数据：

 - $1\le n,\sum n\le 2\times10^5$；
 - $1\le x_i,y_i<10^9+7$；
 - $0\le z_i<10^9+7$。


title: [COCI2015-2016#6] BELA

description:
有一个叫 $\text{Belote}$ 的纸牌游戏，游戏只用到 `A`，`K`，`Q`，`J`，`T`，`9`，`8`，`7` 共八种纸牌。
游戏规则就是将所有纸牌的值加起来，看看谁的值较大，谁就赢。每种纸牌的值都有两种，当其为**特殊牌**时有一个值，**非特殊牌**时也有一个值。每种卡牌的值见下表：

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

现在 $\text{Mirko}$ 有 $4\times N$ 张纸牌，并已知特殊牌的属性为 $B$，请计算 $\text{Mirko}$ 所有纸牌值的总和。

inputFormat:
第一行包含整数 $N$ 和字符 $B$。

接下来 $4\times N$ 行，每行包含两个字符。第一个字符为这张纸牌的种类，第二个字符为这张纸牌的属性。若这张纸牌的属性 $=B$，则说明这张纸牌为特殊牌。

outputFormat: 输出一个整数，为 $\text{Mirko}$ 所有纸牌值的总和。

samples:
4 H
AH
KH
QH
JH
TH
9H
8H
7H
AS
KS
QS
JS
TS
9S
8S
7S

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

纸牌值总和为 $11 + 4 + 3 + 20 + 10 + 14 +
0 + 0 + 11 + 4 + 3 + 2 + 10 + 0 + 0 + 0 = 92 $。

**【数据范围】**

对于 $100\%$ 的数据，$1\le N\le 100$，$B$ 和所有纸牌的属性都属于 `S`，`H`，`D`，`C` 四种字符中的一种，所有纸牌的种类都属于 `A`，`K`，`Q`，`J`，`T`，`9`，`8`，`7` 共八种纸牌中的一种。

**【题目来源】**

**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #6](https://hsin.hr/coci/archive/2015_2016/contest6_tasks.pdf) T1 BELA**。

**本题分值按 COCI 原题设置，满分 $50$**。


title: [COCI2015-2016#6] PUTOVANJE

description:
$\text{Mislav}$ 最喜欢在森林里度过时光，因为森林里有各种各样的水果，吃了每种水果都能获得一定的饱食度。但他不会使自己的总饱食度超过 $C$。

现在森林里有一条小径，小径旁顺次种了 $N$ 个水果，每个水果都有一个饱食度 $w_i$。$\text{Mislav}$ 可以选择从任意一个水果的位置开始，往第 $N$ 个水果前进。在前进的过程中，如果吃下当前位置的水果，总饱食度不会超过 $C$，他就**一定会吃下该水果**。否则，他就会**跳过该水果**，继续前进。

请问 $\text{Mislav}$ 能吃掉的水果个数最多是多少？

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

第二行包含 $N$ 个整数 $w_i$，为第 $i$ 个水果的饱食度。

outputFormat: 输出一个整数，为 $\text{Mislav}$ 能吃掉的最多水果个数。

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

如果 $\text{Mislav}$ 决定从第 $1$ 个水果开始吃，那么他可以吃到第 $1$、$2$、$4$ 个水果，一共吃了 $3$ 个。如果他从第 $2$ 种水果开始吃，那么他可以吃到第 $2$、$3$、$4$、$5$ 共 $4$ 个水果。

**【数据范围】**

对于 $100\%$ 的数据，$1\le N\le 1000$，$1\le C\le 10^6$，$1\le w_i\le 1000$。

**【题目来源】**

**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #6](https://hsin.hr/coci/archive/2015_2016/contest6_tasks.pdf) T2 PUTOVANJE**。

**本题分值按 COCI 原题设置，满分 $80$**。


title: [COCI2015-2016#6] PIANINO

description:
$\text{Mirka}$ 是个业余钢琴家，她正在学习一首乐曲。但她不太能找准音，因此她会采用一种特殊的技巧。

这首乐曲中有 $N$ 个音符，每个音符都有一个标准音 $a_i$。$\text{Mirka}$ 能准确地弹出第一个音，接下来她会确定一个值 $K$。

- 如果下一个音符的标准音大于当前音符的标准音，她就会将自己当前弹的音升高 $K$。
- 如果下一个音符的标准音小于当前音符的标准音，她就会将自己当前弹的音降低 $K$。
- 如果下一个音符的标准音等于当前音符的标准音，她不会改变当前弹的音。

如果当前弹的音等于当前字符的标准音，就算 $\text{Mirka}$ 弹准了一个音。请帮她确定一个非负整数 $K$，使得她弹准的音最多。

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

第二行包含 $N$ 个整数 $a_i$，其中 $a_i$ 为第 $i$ 个音符的标准音。

outputFormat:
第一行输出一个整数，为 $\text{Mirka}$ 最多能弹准的音。

第二行输出一个非负整数，为 $K$ 的值。您只需输出**任意一种满足条件**的 $K$ 即可。

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

当 $K=2$ 时，她弹出的音为 **1**，3，1，**3**，**1**，共弹准了 $3$ 个音。

注意 $K=1$ 也是一种可行的方案。

**【样例 2 解释】**

当 $K=4$ 时，她弹出的音为 **2**，-2，**-6**，**-2**，2，**6**，**10**，共弹准了 $5$ 个音。

**【数据范围】**

对于 $100\%$ 的数据，$2\le N\le 10^6$，$-10^9\le a_i\le 10^9$。

**【评分方式】**

本题启用非官方的自行编写的 [Special Judge](https://www.luogu.com.cn/paste/i91dcbr2)，也可在附件中获取。欢迎大家 Hack（可私信或直接发帖）。Hack 数据作为测试点单独放在最后，对应测试点分数均为 0 分。

**【题目来源】**

**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #6](https://hsin.hr/coci/archive/2015_2016/contest6_tasks.pdf) T3 PIANINO**。

**本题分值按 COCI 原题设置，满分 $100$**。


title: [COCI2015-2016#6] PAROVI

description:
$\text{Mirko}$ 和 $\text{Slavko}$ 在玩一个游戏，先由 $\text{Mirko}$ 在 $1\dots N$ 中选出几组互质的数。例如当 $N=5$ 时，$\text{Slavko}$ 可以选择 $\big\{\{1,2\},\{3,4\},\{2,5\},\{3,5\},\cdots\big\}$ 中的几组。

然后轮到 $\text{Slavko}$。他需要找到一个 $x\in \big[2,n\big]$ 使得对于每组 $\{a,b\}$ 都满足以下两个条件之一：

- $a$，$b<x$

- $a$，$b\ge x$

例如，如果 $\text{Mirko}$ 选了 $\big\{\{1,2\},\{3,4\}\big\}$，那么 $x$ 可以等于 $3$。

如果 $\text{Slavko}$ 找不到满足条件的 $x$ 值，则表示 $\text{Mirko}$ 获得胜利。现在请你求出 $\text{Mirko}$ 获胜的不同情况的总数，在对 $10^9$ 取模后告诉他。

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

outputFormat: 第一行输出一个整数，为 $\text{Mirko}$ 获胜的不同情况的总数对 $10^9$ 取模后的值。

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

$\text{Slavko}$ 只有一种取法 $\big\{\{1,2\}\big\}$。

**【样例 2 解释】**

$\text{Slavko}$ 的其中一种取法为 $\big\{\{1,2\},\{1,3\}\big\}$。

**【数据范围】**

对于 $100\%$ 的数据，$1\le N\le 20$。

**【题目来源】**

**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #6](https://hsin.hr/coci/archive/2015_2016/contest6_tasks.pdf) T4 PAROVI**。

**本题分值按 COCI 原题设置，满分 $120$**。


title: [COCI2015-2016#6] KRUMPIRKO

description:
$\text{Mr. Potato}$ 开了两家新店卖土豆。他买了 $N$ 袋土豆，其中第 $i$ 袋价值为 $c_i$，袋里有 $a_i$ 个土豆。他打算把这 $N$ 袋土豆整袋整袋地分在两个店里。

在每家店中，土豆的平均价格等于这家店里**所有袋的土豆的总价比上土豆的个数**。（注意是个数而不是袋数！）

设 $P_1$ 为第一家店的土豆平均价格，$P_2$ 为第二家店的土豆平均价格。$\text{Mr. Potato}$ 希望在至少有一家店里土豆袋数**正好等于 $L$ 袋**的情况下，最小化 $P_1\times P_2$ 的值。

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

第二行包含 $N$ 个整数 $a_i$。

第三行包含 $N$ 个整数 $c_i$。

outputFormat: 第一行输出一个浮点数，为 $P_1\times P_2$ 的最小值，保留到小数点后三位。

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

对于 $30\%$ 的数据，$2\le N\le 20$。

对于 $100\%$ 的数据，$2\le N\le 100$，$1\le L< N$，$1\le a_i\le 100$，$1\le c_i\le 10^6$，$\sum\limits_{i=1}^{N} a_i\le 500$。

**【题目来源】**

**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #6](https://hsin.hr/coci/archive/2015_2016/contest6_tasks.pdf) T5 KRUMPIRKO**。

**本题分值按 COCI 原题设置，满分 $140$**。


title: [COCI2015-2016#6] SAN

description:
$\text{Anica}$ 有一张神秘的无限表，表里有无限行和无限列。有趣的是，表中的每个数字出现的次数是有限的。

定义函数 $\mathrm{rev}(i)$，返回 $i$ 在十进制下翻转后得到的新数字。例如 $\mathrm{rev}(213)=312$，$\mathrm{rev}(406800)=008604=8604$。

表中第 $i$ 行第 $j$ 列的数字 $A(i,j)$ 由以下方式得到：

- $A(i,1)=i$

- $A(i, j) = A(i, j − 1)+\mathrm{rev}\big(A(i,j-1)\big)$，$j>1$

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

现在 $\text{Anica}$ 给出 $Q$ 个询问，每个询问给出两个整数 $L$ 和 $R$，请你求出无限表中有多少个数的大小在 $\big[L,R\big]$ 中。

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

接下来 $Q$ 行，每行包含两个整数 $L$ 和 $R$。

outputFormat: 输出包含 $Q$ 行，每行一个整数，其中第 $i$ 行为第 $i$ 个问题的答案。

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

对于 $50\%$ 的数据，保证 $1\le L,R\le 10^6$。

对于 $100\%$ 的数据，保证 $1\le Q\le 10^5$，$1\le L,R\le 10^{10}$。

**【题目来源】**

**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #6](https://hsin.hr/coci/archive/2015_2016/contest6_tasks.pdf) T6 SAN**。

**本题分值按 COCI 原题设置，满分 $160$**。


title: [CoE R4 D] 01 串

description:
定义一个好的 $01$ 串 $\mathcal{S}$ 满足以下条件：

+ $\mathcal{S}$ 非空。

+ $\mathcal{S}$ 的任意一个前缀 $\mathcal {S}$$ [1\dots p](p\in [1,|$$\mathcal S$$|])$ 中，$0$ 的数量都不多于 $1$ 的数量。
+ $\mathcal{S}$ 的任意一个后缀 $\mathcal S$$[p\dots |$$\mathcal{S}$$|](p\in [1,|$$\mathcal S$$|])$ 中，$0$ 的数量都不多于 $1$ 的数量。

现在你得到了一个长度为 $n$ 的 $01$ 串 $\mathcal{T}$，有 $q$ 次询问，每次询问给定一对 $l,r$，求 $\mathcal{T}[l\dots r]$ 中的最长的好的 $01$ **子序列** 的长度。若没有好的 $01$ 子序列，则输出 $-1$。

注意：**子序列** 是指去除某些元素但不破坏余下元素的相对位置而形成的新序列。

inputFormat:
第一行两个整数 $n,q$，分别表示 $01$ 串的长度和询问次数。

第二行一个长度为 $n$ 的 $01$ 串，表示 $\mathcal{T}$。

接下来 $q$ 行，每行两个整数 $l,r$，表示一次询问。

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


title: 「EVOI-RD1」飞鸟和蝉

background:
你骄傲地飞远，我栖息的叶片。
听不见的宣言，重复过很多年。
沧海月的想念羽化我昨天，
在我成熟的笑脸，
你却未看过一眼。

description:
蝉 Charlie 要去寻找他的好朋友飞鸟了。

具体来说，Charlie 和他的好朋友生活的地方可以看作一个 $n \times m$ 的网格，左上角为 $(1,1)$，右下角为 $(n,m)$。每个格子 $(i,j)$ 有一个海拔高度 $h_{i,j}$。Charlie 的目标是从他的家 $(x_0,y_0)$ 出发，不重不漏地经过网格中的每个格子**恰好一次**，**最终回到自己的家** $(x_0,y_0)$。Charlie 有两种移动方式：

1. 跳跃。用这种方式，Charlie 可以到达上下左右 $4$ 个相邻格子中**海拔严格低于当前格子**的一个格子。注意跳跃不消耗体力。
2. 飞行。用这种方式，Charlie 可以从当前格子 $(x,y)$ 到达网格中**任意一个**格子 $(x',y')$，并消耗 $h_{x',y'}-h_{x,y}$ 个单位的体力。**注意飞行所消耗的体力值可以是负数**。

Charlie 希望用尽量少的飞行次数完成目标，**在此前提下**再令消耗的体力最少。由于网格实在太大了，Charlie 希望你能帮助他。

inputFormat:
第一行四个整数，分别代表 $n,m,x_0,y_0$，含义如上所述。
接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个数代表格子 $(i,j)$ 的海拔 $h_{i,j}$。

outputFormat: 一行两个整数，分别代表“飞行的最少次数”与“飞行次数最少的前提下消耗的最少体力值”。

hint:
**本题采用捆绑测试**

样例 1 解释：从 $(1,1)$ 飞到 $(2,2)$，再绕一圈即可。

样例 2 解释：一种最佳方案为：$(2,3)-(1,3)-(1,2)-(1,1)=(2,1)-(3,1)=(2,2)=(3,2)=(3,3)=(2,3)$，其中 $=$ 代表飞行。

- Subtask 1 (10 pts)：满足 $1 \leq n,m \leq 3$。
- Subtask 2 (20 pts)：满足 $1 \leq n,m \leq 5$。
- Subtask 3 (20 pts)：保证至多有两种不同的海拔高度。
- Subtask 4 (50 pts)：无特殊限制。

对于 $100\%$ 的数据：
- $1 \leq n,m \leq 50$。

- $1 \leq x_0 \leq n,1 \leq y_0 \leq m,1 \leq h_{i,j} \leq 10^9$。

出题人：[冷月葬T魂](https://www.luogu.com.cn/user/340903)