title: [传智杯 #3 练习赛] 儒略历

description:
在 1582 年之前，以 4 为倍数的年份为闰年。正常情况下，一年中一月到十二月的天数分别是 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 天。如果这年是闰年，那么二月则有 29 天。

但某位教皇发现这么做其实不够准确，会造成误差，因此规定从 1582 年开始，以 4 为倍数的年份，除了以 100 为倍数且不为 400 的倍数年份，才是闰年。同时为了消除误差，规定 1582 年 10 月 4 日的下一天是 1582 年 10 月 15 日，中间的日期就当作不存在了。

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

现在给出日期，计算这个日期到公元 1 年 1 月 1 日经过的天数。

inputFormat:
按照 `日月年` 的格式输入数据，其中日是 1 到 31 之间的整数，月是三个大写字母，年是 1 到 9999 之间的整数。保证这个日期是合法且存在的。

月份的大写字母：

- 1月：JAN
- 2月：FEB
- 3月：MAR
- 4月：APR
- 5月：MAY
- 6月：JUN
- 7月：JUL
- 8月：AUG
- 9月：SEP
- 10月：OCT
- 11月：NOV
- 12月：DEC

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


title: 「Stoi2031」枫

type: P

background: > 缓缓飘落的枫叶像思念 为何挽回要赶在冬天来之前 爱你穿越时间 两行来自秋末的眼泪 让爱渗透了地面 我要的只是你在我身边 ——《枫》

description: 冬很喜欢枫叶。她家门前有一棵枫树，树上落下了 $n$ 片叶子。冬将它们编号为 $1$ 到 $n$。她希望这些枫叶不要这样被人踩碎后烂在地里，所以决定把它们捡起来。她称将剩余未捡起来的枫叶按编号从小到大或从大到小的顺序排序后，先捡起第一片枫叶，然后每隔 $k$ 片捡起一片称为一次 **挽回**。她会一直进行 **挽回**，第一次 **挽回** 从小到大，之后每次 **挽回** 的顺序都和上次不同（即上次从小到大这次就从大到小，反之亦然），直到最后一片枫叶也被捡起。她认为最后一片捡起的枫叶代表了 **思念**，能带来幸福。她希望获得更多的幸福，所以她会很多次地问你 $n$ 和 $k$ 取某两个值时她得到的 **思念** 的编号。

inputFormat:
第一行为数据组数 $t$，满足 $t=i$，$i$ 为数据点编号。

第 $2$ 到 $t+1$ 行，每行开头两个数 $q,m$，表示她要取 $q$ 次，每次的枫叶数 $n$ 不超过 $m$。接着输入 $q$ 个数表示每次的枫叶数 $n$。第 $x$ 行的所有询问中 $k=x-1$。

outputFormat: 对于每行输出 $q$ 个数，表示每次询问的答案。


title: [CERC2014] Can't stop playing

description:
Some computer games are extremely fun and this problem may be about one of these.

You are given a sequence of one dimensional blocks, each of length that is a power of two.
The goal of the game is to merge all the blocks into one big block. The blocks are presented
one by one, and for each one you have to decide whether to stick it immediately to the left or
immediately to the right of the previous blocks.

Every time two blocks of the same size are adjacent, they merge into one block that is twice
as long as each of them. Note that, as long as possible, the resulting blocks immediately merge
with adjacent ones. For example, if the current sequence of blocks is $2, 4, 16$, then sticking $2$ on
the left side leads to $8, 16$, while sticking it on the right side gives $2, 4, 16, 2$. Note that at any
moment there is at most one mergeable pair of blocks.

You have lost the game (again!) and you are wondering whether there was any way to win at all. Analyze the sequence to find out.

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

Each test case consists of two lines. The first one contains a positive integer $n \leq 1 000$ – the
length of the sequence. The next line contains a sequence of $n$ block lengths, each a power of two. The sum of all the lengths does not exceed $2^{13}$.

outputFormat: For each test case, output one line containing the word $\texttt{no}$ if winning the game is not possible. Otherwise, output a word consisting of $n$ letters $\texttt{l}$ and $\texttt{r}$, denoting whether the corresponding block should be stuck to the left or to the right. Note that for the first block it does not matter.

translation:
### 题目描述
你有一个双端队列，同时给定一个长度为 $n$ 的序列 $a$ ，满足序列中的元素为 2 的非负整数幂

从前到后遍历整个序列，每次对于 $a_i$ 可以选择将它放入双端队列的队头或者队尾，如果队列中存在相邻两个元素大小相同，那么它们将合并为一个新的元素，元素大小为先前两个元素之和

求是否存在一个合法的方案使得队列最后只剩下一个元素，若存在，输出方案，不存在输出 $no$

多组数据

### 读入格式

首先读入一个 $t$ 表示数据组数

对于每一组数据第一行读入一个 $n$ 表示序列长度，下一行读入 $n$ 个元素，$a_1$ 到 $a_n$

### 输出格式

若存在合法方案输出一个字符串，其中第 $i$ 个字符若为 $l$ 表示放入队头，$r$ 表示放入队尾,其中第一个元素 $l,r$ 任意

若不存在合法方案，输出 `no`


title: 「HMOI R1」文化课

background:
有一群人在参加 CPS0202。由于作弊可以使得省队名额减一，所以他们准备作弊祸害他人，然后高考考全省第二。

但是由于他们非常菜，高考考不到全省第二，所以他们需要你来指导他们作弊。

fz 编不下去了，恳请 PD 帮他写个崩 3 的背景。

description:
$n$ 个人正在会考。由于他们假装自己退役了，所以下午的 CPS0202 跟他们没啥关系。

目前第 $i$ 个人有一个得分 $a_i$，想要及格需要拿到 $l_i$ 分。而为了不被老师怀疑，他的分数不能超过 $r_i$。

你可以组织若干场作弊。这些作弊是同时进行的，所以不能有人同时参加两场或以上的作弊。每场作弊在连续的一段考生中进行，他们的分数都变为他们中分数最高的人的分数。

求最多能使多少人及格且不被怀疑。

inputFormat:
第一行一个整数 $n$，表示有 $n$ 个人。

第二行 $n$ 个用空格隔开的整数，第 $i$ 个数 $a_i$ 代表第 $i$ 个人的初始得分。

接下来 $n$ 行每行两个整数，第 $i$ 行的数为 $l_i$ 和 $r_i$，意义见题目描述。

outputFormat: 一行一个整数，代表最多能使多少人及格且不被老师怀疑。

hint:
在 $[2,3]$ 组织一场作弊，可以使所有人满足条件。

本题采用捆绑测试。
- Subtask 1（$5$ 分）：$n\le5$；
- Subtask 2（$5$ 分）：$n\le100$；
- Subtask 3（$10$ 分）：$n\le8\times10^3$；
- Subtask 4（$30$ 分）：$l_i=r_i$；
- Subtask 5（$20$ 分）：$a_i\le a_{i+1}$；
- Subtask 6（$30$ 分）：无特殊性质。

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le a_i\le n$，$1\le l_i\le r_i\le n$。

-------

- Idea: FZzzz
- Solution: FZzzz
- Code: FZzzz
- Data: FZzzz


title: [RC-04] 子集积

description:
给出 $n$ 个整数 $a_1\sim a_n$，它们构成的多重集中，有几个子集的元素积大于 $m$？（空集的元素积等于 $1$）

两个子集不同，当且仅当它们中包含元素的 **下标** 不同。

答案很大，因此请输出它对 $998244353$ 取模的值。

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

接下来一行 $n$ 个正整数 $a_1\sim a_n$，描述这个多重集。

outputFormat: 一行一个整数，为答案对 $998244353$ 取模的值。


title: [CTSC2002] 灭鼠行动

description:
最近，有一些繁殖力很强的老鼠在下水道非常猖獗，灭鼠特工队正在计划消灭这些老鼠。下水道只有东西方向和南北方向的管道，如图所示。

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

灭鼠特工队的队员拥有强大的武器。他们将在某些时刻 $t$ 在某些位置 $(x,y)$ 放置武器。他们所使用的武器包括：

1. 强力炸弹：它的攻击范围限定在管道内部，是沿竖直和水平方向，离 $(x,y)$ 的距离不超过 $L$ 的区域，但是不能穿透下水道壁。它将在放置之后立刻爆炸，且攻击范围内的老鼠将被全部炸死。

2. 神秘射线：它的攻击范围是以 $(x,y)$ 为圆心，半径为 $R$ 的圆，而且可以穿透下水道壁。射线在时刻 $t$ 施放后，将使攻击范围内的所有老鼠立刻陷入昏迷状态，失去知觉，停止一切生理活动，待到第 $t+3$ 时刻才能恢复（保持失去知觉前的朝向）。如果在昏迷状态中再次受到射线攻击，那么它将再推迟 $3$ 个时刻恢复。例如，若老鼠在时刻 $t$ 和时刻 $t+1$ 个受到一次射线的攻击，则它要昏迷到第 $t+3+3$ 时刻才能恢复知觉。恢复知觉以后，老鼠将继续以前的生理活动。

3. 定时炸弹：它的攻击范围仅包括 $(x,y)$。它在时刻 $t$放置后，将在第 $t+3$ 时刻爆炸，爆炸时处在 $(x,y)$ 点的老鼠将全部被炸死。

4. 生物炸弹：它的攻击范围仅包括 $(x,y)$。它将在放置之后立刻爆炸，使处在 $(x,y)$ 点的所有老鼠的性别改变（无论大小，雌变成雄，雄变成雌），但不影响老鼠的正常生理活动。

虽然特工队的实力很强，但是老鼠的实力也不容忽视。

我们定义，相邻两个时刻之间是一个时间单位。从 $t=0$ 时刻开始，每只老鼠就从初始位置向某一初始方向运动。只要前方有管道，如上图中沿方向 $\texttt{N}$ 到达点 $\texttt{A}$，老鼠就会一直向前走，运动速度为 $1$。否则，如果只有左边或者只有右边有管道，如上图中沿方向 $\texttt{E}$ 到达点 $\texttt{B}$ 时，再不能沿原方向继续前进，它就会花费一个时间单位朝该方向原地转动 $90$ 度，即它将改变方向朝向 $\texttt{S}$。如果它左边和右边都有管道，如上图中沿方向 $\texttt{W}$ 到达点 $\texttt{C}$，老鼠会回忆这是第几次处于这种情况。如果是第奇数次遇到，它会向左转，第偶数次就向右转。如果它处于一条死路的尽头，如上图中沿方向 $\texttt{W}$ 到达点 $\texttt{D}$，那么它会花费两个时间单位连续向右转两次，即它将改变方向朝向E。

   如果在 $t$ 时刻某点恰好只有两只老鼠，一只为成年雄老鼠，一只为成年雌老鼠，则它们将会因为进行繁殖而在该点停留两个单位时间，$t+2$ 时刻会在该点对每个有管道的方向生出一只朝着该方向的小老鼠，南北方向为雄小老鼠，东西方向为雌小老鼠。如上图中的 $\texttt{C}$ 点，$t$ 时刻恰好只有两只老鼠，它们都已成年且性别相异，那么在第 $t+2$ 时刻就会在该点生出三只小老鼠，它们分别朝向 $\texttt{N}$、$\texttt{S}$、$\texttt{E}$，性别分别是雄性、雄性、雌性。小老鼠一出生就立刻开始移动，而成年老鼠需要再休息一个时间单位，即在 $t+3$ 时刻继续活动（两只老鼠都保持生育前的朝向）。小老鼠需要成长 $5$ 个时间单位才会长成为成年老鼠。

   特工队现在制定了一套灭鼠计划，其中包括在下水管道放置武器的位置、时间和类型。你需要帮他们计算灭鼠行动的效果，如果在该计划实施的过程中，老鼠的数量超过了某个限定值，就会爆发鼠疫。

inputFormat:
第一行为 $4$ 个整数 $L, R, m, n(0\le L,R\le 10,1\le m,n\le 50)$，其中 $L$ 代表强力炸弹的有效攻击距离，$R$ 代表神秘射线的作用半径，$m$ 和 $n$ 代表下水道平面图的规模。$x$ 坐标的范围为 $[1,m]$, $y$ 坐标的范围为 $[1,n]$。

从第 $2$ 行到第 $m+1$ 行为下水道结构图。我们用方向数 $1$ 代表 $\texttt{N}$ (北)，用方向数 $2$ 代表$\texttt{E}$ (东)，用方向数 $4$ 代表 $\texttt{S}$ (南)，用方向数 $8$ 代表 $\texttt{W}$ (西)。第 $i+1$ 行的第 $j$ 个数字 $c_{i,j}$ 代表点 $(i,j)$ 处有管道连接的所有方向数之和，如上图中的点 $\texttt{B}$ 的方向数之和为 $12$。

第 $m+2$ 行为一个整数 $K（1\le K\le 50）$，代表时刻 $0$ 时老鼠的个数（此时老鼠都是成年的）。

第 $m+3$ 行到第 $m+K+2$ 行每行描述一只老鼠，包括该老鼠的初始坐标 $(x,y), (1\le x\le m, 1\le y\le n)$，朝向（’$\texttt{E}$’,’$\texttt{S}$’,’$\texttt{W}$’,’$\texttt{N}$’）以及性别（’$\texttt{X}$’=雄，’$\texttt{Y}$’=雌）。输入保证每个老鼠都在水管内。

第 $m+K+3$ 行为两个整数 $P，Limit(1\le P, Limit\le 100)$，分别表示特工队准备使用的武器个数以及控制鼠疫发生的老鼠数量的极限。

第 $m+K+4$ 行到第 $m+K+P+3$ 行每行描述一个武器，包括该武器的类型($1$-强力炸弹，$2$-神秘射线，$3$-定时炸弹，$4$-生物炸弹)，放置的时刻 $t(t\ge 1)$，放置的坐标 $(x,y) (1\le x\le m, 1\le y\le n)$，输入保证武器放置在管道内。武器按照放置的时间不降序排列。

最后一行包含一个整数 $Time(1\le Time\le 1000)$，表示模拟的结束时刻。$Time$ 保证比所有武器的放置时刻大。

outputFormat: 包含一个整数。如果爆发了鼠疫，该整数为 $-1$，否则该整数为时刻 $Time$ 的老鼠数目。

hint:
### 样例解释

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


title: 「RdOI R1」变换(turn)

description:
有 $n$ 个变换，其中第 $i$ 个有两个属性值 $p_i$ 和 $q_i$，当这个变换作用到 $x$ 时，$x$ 将会变成 $f_i(x),f_i(x)$ 的定义为：

$$f_i(x)=\left\lfloor\dfrac{x}{p_i}\right\rfloor+q_i$$

给定 $m$ 条操作，操作分两种：

**修改**操作可以修改某个变换的属性值；

**查询**操作将会给定 $x$ 以及两个序号 $s$ 和 $t$，你需要计算并输出：

$$f_{t}(f_{t-1}(\cdots f_{s+1}(f_{s}(x))))$$

inputFormat:
第一行：两个正整数表示 $n$ 和 $m$。

第二行：$n$ 个整数，表示 $p_1,p_2,\cdots,p_n$。

第三行：$n$ 个整数，表示 $q_1,q_2,\cdots,q_n$。

接下来 $m$ 行，每行表示一个操作：

修改 操作以字母 `m` 开头，后接三个参数 $i,p',q'$，表示将第 $i$ 个变换的属性值修改成 $p',q'$。保证任何时候属性都满足 $1\leq p_i\leq 1000, 0\leq q_i\leq 1000$。

查询 操作以字母 `q` 开头，后接三个参数 $x,s,t$，意义见题面，保证 $s\leq t, 0\leq x\leq 10^6$。

outputFormat: 对每个询问操作，输出一个整数，表示所求的答案，以换行分隔。

samples:
见附件中的 turn-big-sample1.in
见附件中的 turn-big-sample1.out

hint:
【数据范围】

- 对于 $20\%$ 的数据，$1 \le n \le 10^3,1 \le m \le 10^4$。
- 对于另外 $30\%$ 的数据，$1 \le n \le 10^4,1 \le m \le 10^5$。
- 对于 $100\%$ 的数据，$1 \le n \le 10^5,1 \le m \le 2 \times 10^5$。

---

【文件读入读出】**（模拟，提交代码时不需使用）**

- 文件名：`turn.cpp`
- 读入文件名：`turn.in`
- 读出文件名：`turn.out`


title: 滴水不漏

background: 这是一道 IO 交互题。

description:
Gnar 购买了 $n$ 个水缸，其中第 $i$ 个水缸的容积为 $i$ 且因不明原因初始装有 $a_i$（$0 \le a_i \le i$）单位的水。

好奇的 Gnar 想知道每个水缸装有的水量，但肉眼观察显然不可行，他希望你能帮他计算解决这个难题。

Gnar 唯一能替你执行的操作是，由你先指定 $i, j$（$1 \le i, j \le n$），然后：

- 若 $i \neq j$，滴水不漏地将第 $i$ 个水缸的水往第 $j$ 个水缸倒，直到第 $i$ 个水缸的水被倒完或第 $j$ 个水缸已满。Gnar 会告诉你操作后第 $j$ 个水缸是否是满的。注意倒水的影响会**保留**而不是恢复到操作前。
- 若 $i = j$，Gnar 做不到让一个水缸的水往自己倒，他会直接告诉你当前第 $j$ 个水缸是否是满的。

Gnar 只肯接受**最多** $20000$ 次操作，否则他会认为你在调戏他！

你的任务是利用不超过 $20000$ 次操作 Gnar 告诉的结果，完整求出最初的 $a_1,a_2,\ldots,a_n$。

当然 Gnar 不会动手脚，你所求的 $a_1,a_2,\ldots,a_n$ 在操作前已经存在，不随操作动态生成。

inputFormat: 输入单个正整数水缸个数 $n$ 以开始交互。

outputFormat:
在你确定答案后，用 `! a1 a2 ... an` 的形式输出一行以结束交互。

### 交互格式

交互过程中，用 `? i j` $(1 \le i,j \le n)$ 的形式输出一行以执行一次操作。然后你应输入一个布尔值，即操作的返回值 $x$。若 $x = 0$，表示第 $j$ 个水缸未满；若 $x = 1$，表示第 $j$ 个水缸已满。

上述的所有输入都应从**标准输入**中读入，所有输出都应向**标准输出**中输出。输出一行后必须**清空缓冲区**，否则你的评测将被判为 Time Limit Exceeded。清空缓冲区方式如下：

- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。
- 在 Pascal 中，使用 `flush(output)`。
- 在 Python 中，使用 `stdout.flush()`。
- 其他语言请自行查阅文档。

如果你的输出格式错误，或执行超过 $20000$ 次操作，你的评测将被判为 Wrong Answer。

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

样例示意了一种可能的交互过程。

初始两个水缸中分别装有 $0,1$ 单位的水。

第一次操作，由于 $i = j$，你直接得知 $x = 0$ 即第一个水缸未满。

第二次操作后两个水缸装有水量分别为 $1,0$，而你得知 $x=1$ 即第一个水缸当前已满。

第三次操作后两个水缸装有水量分别为 $0,1$，而你得知 $x=0$ 即第二个水缸当前未满。

注意过程中确切水量并不传达给你，但是通过返回值 $x$ 你足够唯一确定 $a_1 = 0$，$a_2 = 1$。

----

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

**本题采用捆绑测试**。你必须通过 Subtask 中所有的测试点才能获得该 Subtask 的分数。

- Subtask #1 (8 points)：$n = 2$。
- Subtask #2 (17 points)：$n \le 10$。
- Subtask #3 (15 points)：$n \le 100$。
- Subtask #4 (15 points)：$a_i \le 1$。
- Subtask #5 (25 points)：$n \le 500$。
- Subtask #6 (20 points)：无特殊限制。

对于所有的数据，保证 $2 \le n \le 1000$，$0 \le a_i \le i$。


title: Chino 的比赛

description:
Chino 想要用现在手里有的 $n$ 道题出成一套模拟赛。一开始，这 $n$ 道题按照由易到难的顺序排列。

但是因为 Chino 是一个可爱的妹子，所以她会将这些题目的顺序打乱。具体地，她会执行恰好奇数次操作，每次操作她会将其中两道题的位置交换。一套可能的模拟赛就是这些题的一个排列。

Chino 为了评估一套模拟赛的可爱程度，她定义 $s$ 表示使得开始时的题目顺序变为这套模拟赛的题目顺序的最少操作次数，定义 $t$ 表示开始时与这套模拟赛中位置相同的题目数量，那么这套模拟赛的可爱程度就是 $s/\left(t+1\right)$。

按照套路，你现在应该帮 Chino 计算某一套模拟赛的可爱程度。Chino 觉得这不够可爱，所以她想让你计算所有可能的模拟赛的可爱程度的两倍和。可以发现这一定是一个非负整数。为了避免答案过大，你只需要输出其对质数 $p$ 取模后的结果即可。

形式化地，对于置换 $\pi$，令 $\nu\left(\pi\right)$ 表示其不动点个数，设 $\upsilon\left(\pi\right)$ 为其能够被分解成为的最少个数对换乘积的对换数目。设 $n$ 元对称群为 $S_n$，$n$ 元交错群为 $A_n$，求
$$
2\sum_{\pi\in S_n\land\pi\notin A_n}\frac{\upsilon\left(\pi\right)}{\nu\left(\pi\right)+1}.
$$

这一定是一个非负整数。答案对质数 $p$ 取模后输出。

inputFormat: 输入一行两个正整数 $n,p$。

outputFormat: 输出一行一个非负整数，表示所有可能的 $n$ 道题的模拟赛的可爱程度之和对 $p$ 取模后的结果。


title: 「C.E.L.U-02」苦涩

background: 回想起自己的过往的人生，YQH 觉得心中充满了苦涩。如果人生能再来一次，我一定会少做一些傻事，少真香几次，然后大胆地去追寻自己的爱。可惜没有这样一个机会了。

description:
在 YQH 的梦中，他看到自己过去的记忆正在不断浮现在自己脑中。这些记忆带给他的是满满的苦涩。他想要强行忘记一些来减轻自己的苦涩。
YQH 的脑中可以被分成 $n$ 个片区，每个片区相当于一个存放记忆的可重集，初始为空。他将进行 $m$ 次这三种操作：
操作 1：区间 $l\sim r$ 的片区中都浮现了一个苦涩值为 $k$ 的记忆。
操作 2：YQH 开始清理 $l\sim r$ 片区的记忆。如果一个片区 $k\in[l,r]$ 且 $k$ 中苦涩值最大的记忆与 $l\sim r$ 片区中苦涩值最大的记忆相等，则将这个苦涩值最大的记忆忘记。如果在同一个片区有多个相同的苦涩值最大的记忆，则只忘记一个。如果这些片区内没有记忆，则无视。
操作 3：YQH 想知道，$l\sim r$ 片区中苦涩值最大的记忆的苦涩值是多少，如果不存在，输出`-1`。

inputFormat:
第一行两个数，$n,m$。
接下来 $m$ 行，第一个数代表操作种类 $op$，对于操作 1，有三个数 $l,r,k$，对于操作 2 或 3，有两个数 $l,r$。

outputFormat: 对于每个操作 3 输出一行，代表答案。


title: 小 P 的星空

background:
>星依云渚溅溅，露零玉液涓涓，宝砌哀兰剪剪。碧天如练，光摇北斗阑干。
>
>—— 【元】孟昉《天净沙 · 星依云渚溅溅》

小 P 漫步于星空之下。

“摘下星星送给你，你就是我的全世界”。

“今夜，我不关心人类，我只想你”。

description:
将星空看作一个平面直角坐标系，小 P 所在的位置为 $(0,0)$，即坐标原点。天上共有 $n$ 颗星星，第 $i$ 颗星星的坐标为 $(x_i,y_i)$。

小 P 最初面向点 $(1,0)$，然后小 P 会进行 $m$ 次原地转动，第 $i$ 次转动后会面向点 $(u_i,v_i)$。

他可以选择逆时针转动或顺时针转动，当面向此次旋转最终将要面向的方向时，此次转动立即停止。

他相信，在转动过程中，越多的星星出现在他正前方，他【数据删除】。

小 P 想知道，每一次转动过程中他最多可以让多少星星出现在他正前方（包括转动初始方向和结束方向正前方看到的星星）。

inputFormat:
总共包括 $n+m+1$ 行。

第一行包含两个正整数 $n,m$，分别表示星星颗数和转动次数。

接下来的 $n$ 行，每行两个整数 $x_i,y_i$。

接下来的 $m$ 行，每行两个整数 $u_i,v_i$，意义如【题目描述】中所述。

每行的两个数字间由单个空格隔开，数据为 Linux 格式，行末保证没有多余空格。

outputFormat: $m$ 行，每行一个整数。第 $i$ 行的整数表示第 $i$ 次转动的答案。

samples:
见下发文件 ex_star2.in
见下发文件 ex_star2.out

samples:
见下发文件 ex_star3.in
见下发文件 ex_star3.out

hint:
样例1示意图如下：

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

橙色点为星星，绿色点小 P 第一次的转动位置。第一次转动，从 $(1,0)$ 转到 $(-1,1)$。若顺时针转动(蓝色区域，包括边界)，$(1,0)$, $(-2,-1)$，共计 $2$ 颗星星；而逆时针转动(绿色区域，包括边界)，$(1,0)$, $(1,1)$,$(2,2)$,$(-1,2)$，共计 $4$ 颗星星。

第二次转动，从 $(-1,1)$ 转到 $(-1,2)$，逆时针转动，$5$ 颗星星都会在转动过程中出现在小 P 正前方。

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

除测试点 $24$ 和 $25$ 外，其他测试点保证所有坐标的绝对值 $\le 1000$。

对于前 $12$ 个测试点，保证原点到任意星星形成的射线上没有其他星星。

除 $23,25$ 测试点外，对于所有编号为奇数的测试点，保证小 P 初始面向方向和每次转动目标方向上没有任何星星。

除 $22,24$ 测试点外，对于所有编号为偶数的测试点，保证小 P 初始面向方向和每次转动目标方向上至少有一颗星星。

对于 $100\%$ 的数据，保证星星的坐标互不相同，保证坐标不会出现 $(0,0)$，保证不会出现转动初始方向等于结束方向。

样例 $3$ 满足偶数测试点的限制。


title: 小 B 的面包

background:
本题是一道**函数式交互题**。

小 B 获得了很多面包，小 Y 很愤怒，他想抢夺面包。

小 Y 提出要和小 B 玩一个有趣的游戏，如果小 B 输了，小 B 就要被抢走所有面包。

小 B 还要到【数据删除】江边散步，所以他把这个任务交给了你。

聪明的你能帮小 B 守卫他宝贵的面包吗？

description:
**本题建议使用 `c++` 语言编程**。

小 Y 把 $9$ 个面包依次放在了桌子上，第 $i$ 个面包的质量为 $i$。

小 Y 与你轮流选取面包，谁选取的面包中，任意三个面包的总质量先恰好达到 $15$，谁就获胜，另外一方则落败。**每个面包只能取一次，一个人取了某个面包后另一个人就不能再选取了，选取面包后不能再放回**。

如果最后面包全部选取完后双方未均达到，则为平局。

---

本题中，你需要且只需要实现以下三个函数（可以在其中调用或访问你的自写函数或全局变量）：

```cpp
extern "C" int choose(int x);
extern "C" void init();
extern "C" void newgame(bool f);
/* 注意以上三个函数之前的 extern "C" 不可省略 */
```

评测时，交互库将首先调用一次你所实现的 `init()` 函数。`init()` 函数的作用为方便你最开始初始化，之后不会再次调用，如果你不需要初始化也请加入 `extern "C" void init() {}`。

接下来交互库会调用你所实现的 `newgame(bool f)` 函数，交互库调用 `newgame(bool f)` 函数表示开始一场新游戏，传入的 `f` 若等于 $1$ 表示是由交互库先选择，否则由你先选择。

接下来交互库将会不断调用你实现的 `choose(int x)` 函数，传入的 $x$ 表示小 Y 选取了第 $x$ 个面包，此函数运行结束后你需要返回一个整数 $y(1 \le y \le 9)$，表示你选取了第 $y$ 个面包，即：

```cpp
extern "C" int choose(int x) { /*x为交互库选取的面包 */
    /* 你的代码 */
    return y; /* y为你选取的面包 */
}
```

特别地，当传入的 $x=0$ 时，表示是由你先选取面包。如果你 `choose(int x)` 函数返回了不合法的值，该场游戏立即结束，且结果为交互库获胜。

不停调用 `choose(int x)` 函数直到某一方胜利或平局，即该场游戏结束。接着，交互库又会调用 `newgame(bool f)` 函数，开始一场新游戏。交互库一共会调用 $1800$ 次 `newgame(bool f)` 函数，表示进行 $1800$ 场游戏。

详细可查看`template_game.cpp`。

---

在附加文件中，有以下一个文件：

`template_game.cpp`——你将在其中实现上述三个函数，内含详细注释，也包括交互库参考代码，请仔细阅读，**建议在此基础上答题**。

本地可直接在 IDE 中编译。

inputFormat: 无

outputFormat:
对于本地交互库，**交互库**最后会输出两行：

第一行两个数 $w,d$ ，分别表示你获胜的场数和平局的场数；

第二行为你的得分。

hint:
**保证交互库采用完全随机选取策略，即每次均会从未选取的面包中等概率选取一个面包**

$1800$ 场游戏中，有 $600$ 场是由你的程序先选取，有 $1200$ 场是由交互库先选取。

具体来说，对于第 $i$ 场游戏，若 $i \bmod 3 =0$ ，则由你的程序先选取，否则由交互库先选取。

本题首先会受到和传统题相同的限制，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。

你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

**本题只有一个测试点，你的得分按如下规定判定：**

设你程序获胜了 $x$ 场，平局为 $y$ 场，你最终的得分用计分函数 $f(x,y)$ 表示为：

$$
f(x,y)=\lfloor (\frac{x+y}{6}-200) \cdot \min((\frac{x}{x + y})^2+0.2,1) \rfloor
$$

最低得分为 $0$ 分。

**实际评测的交互库与下发的不相同，选手的程序应不依赖于交互库实现**。

详细可查看`template_game.cpp`。


title: 光棱碎片

background:
碎片在少年的世界里四处飘散。
最后被少年收集起，成为一列仿若无意义的字符。

description:
少年只剩一个字符串 $S$，它的长度为 $n$，下标以 $1 \dots n$ 编号；
以及一个数组 $a_{1\dots n}$。

少年写出了两个数 $L,R$ 并尝试寻找那些被光芒照耀过的碎片：
对于 $S$ 中两个出现位置不同而本质相同的子串 $(S_{l_1\dots r_1},S_{l_2\dots r_2})$，若 $L \le (a_{r_1} \oplus a_{r_2}) + (r_1 - l_1 + 1) \le R$，则这两个子串之间存在光芒。
其中 $S_{l\dots r}$ 表示 $S$ 的下标在 $[l,r]$ 内的字符顺次连接构成的子串，$\oplus$ 表示按位异或运算。

少年试图寻找，有多少对子串之间存在光芒。
子串对是无序的。具体地，$(S_{l_1\dots r_1},S_{l_2\dots r_2})$ 和 $(S_{l_2\dots r_2},S_{l_1\dots r_1})$ 视为一个子串对。
而你只需要将答案对 $998244353$ 取模之后告诉他就行了。

inputFormat:
第一行，一个正整数 $n$。
第二行，一个字符串 $S$。
第三行，$n$ 个非负整数 $a_{1\dots n}$。
第四行，两个非负整数 $L,R$。

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

hint:
对于 $20\%$ 的数据，$n \le 100$；
对于 $50\%$ 的数据，$n \le 10^3$；
对于 $100\%$ 的数据，$1 \le n \le 10^5$, $0 \le a_i,L,R \le 10^5$, $L \le R$, $S$ 只包含小写字母。

**「出题人的馈赠」**
勇敢一点。相信某算法的常数。你想到的可能就是垃圾标算。


title: 「EZEC-6」造树

background:
> 成体系的结论会产出“低猜想水平”的机械推导，但更多的题目中需要“高猜想水平”的灵感。

——command_block 《考前小贴士》

[](https://cdn.luogu.com.cn/upload/image_hosting/1m9hce9x.png)无脑选手出思维题。

description:
你要帮 djy 造一棵树，满足以下条件：

- 由 $n$ 个点组成。

- $i$ 号点的度数为 $a_i$。

定义一条边 $(i,j)$ 的价值为 $b_i\times b_j$，你要在满足上述两个条件下，使所有边的价值和最大。

保证存在这样的树。

inputFormat:
第一行一个整数 $type$，表示数据生成方式。

若 $type=0$：

第二行一个整数 $n$。

第三行 $n$ 个整数，第 $i$ 个数表示 $a_i$。

第四行 $n$ 个整数，第 $i$ 个数表示 $b_i$。

若 $type=1$：

给出一个数据生成器模板：

```cpp
int a[10000005],b[10000005];
unsigned seed;
unsigned rnd(unsigned x){
	x^=x<<13;
	x^=x>>17;
	x^=x<<5;
	return x;
}
int rad(int x,int y){
	seed=rnd(seed);
	return seed%(y-x+1)+x;
}
void init_data(){
	cin>>seed;
	for(int i=1;i<=n;i++)
		a[i]=1,b[i]=rad(1,500000);
	for(int i=1;i<=n-2;i++)
		a[rad(1,n)]++;
}
```

第二行一个整数 $n$。

之后调用 `init_data()`。

第三行一个整数 $seed$。

outputFormat: 一行一个整数 $ans$，表示最大的价值和。

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

- Subtask0 (10 pts)：$n\le 6$，$type=0$；
- Subtask1 (20 pts)：$n\le 10^3$，$type=0$；
- Subtask2 (10 pts)：$n\le5\times10^5$，$b_i\le2$，$type=0$；
- Subtask3 (20 pts)：$n\le10^5$，$type=0$；
- Subtask4 (20 pts)：$n\le5\times10^5$，$type=0$；
- Subtask5 (20 pts)：$type=1$。

对于 $100\%$ 的数据，$2\le n\le10^7$，$1\le a_i\le n$，$1\le b_i\le5\times10^5$，$type\in\{0,1\}$，$0\le seed<2^{31}$。


title: 【DSOI 2021】吟唱的金色花海

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

在很久很久以前，有一片开满了白色郁金香的花海。某一天，绽放了一朵金色郁金香，从此，这片花海开始了它永生的吟唱……

>   _(Dutch) $\textit{\textcolor{blue}{Het\ universum\ zingt\ voor\ mij!}}$_

description:
在某一时刻，在某处出现了一朵金色郁金香。然后接下来每一秒，每朵金色郁金香会向其上下左右四个点中所有白色郁金香吟唱，使其变为金色郁金香。

现在告诉你一个点 $(x_0,y_0)$，以及它自第一朵金色郁金香出现起，刚变成金色郁金香的那一秒 $t$，你需要找出最初出现的金色郁金香的位置。

每次你可以输出一行 `0 x y`,然后程序会返回一个值 $0$ 或 $1$，$0$ 表示 $(x,y)$ 在第 $t$ 秒是白色郁金香， $1$ 表示 $(x,y)$ 在第 $t$ 秒是金色郁金香。
你可以输出一行 `1 x y` 告知程序最初出现最初出现的金色郁金香的位置为 $(x,y)$ 以结束程序。

inputFormat:
**本题有多组数据。**\
第一行输入一个正整数 $Q$ ,表示有 $Q$ 组数据。\
对于每组数据，输入四个整数 $t,x_0,y_0,k$ 开始交互。数据用单个空格隔开，代表第 $t$ 秒时位于 $(x_0,y_0)$ 处的郁金香刚变成了金色。你最多可以询问的次数为 $k$。

outputFormat:
对于每一组数据，在你确定答案之后，输出一行 `1 x y` 以结束本组数据，代表你判断 $(x,y)$ 是金色郁金香最开始出现的地方。

### 交互格式

交互过程中，用 `0 x y` 的形式输出一行以执行一次操作。然后你应输入一个布尔值，即操作的返回值 $x$。若 $x=0$ ，表示 $(x,y)$ 在第 $t$ 秒是白色郁金香；若 $x=1$ ，表示 $(x,y)$ 在第 $t$ 秒是金色郁金香。

上述的所有输入都应从**标准输入**中读入，所有输出都应向**标准输出**中输出。输出一行后必须**清空缓冲区** ，否则你的评测有可能被判为**Time Limit Exceeded**。清空缓冲区方式如下：

* 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。
* 在 Pascal 中，使用 `flush(output)`。
* 其他语言请自行查阅文档。


title: 「MCOI-07」Dream and Discs

background: **均匀随机** 指对所有可行的结果随机选一个结果，其中所有可行结果等概率被选择。

description:
Dream 有 $n$ 片音乐盘，编号为 $1$ 到 $n$。所有盘都存恰好一首歌，其中编号为 $i$ 的盘所存储歌由正整数 $a_i$ 表示。$a_i$ 满足 $1\le a_i\le n$。
Dream 打算**均匀随机**选择一个编号区间 $P_1$ 和一个歌曲区间 $S_1$，其中 $P_1\subseteq [1,n]$，$S_1\subseteq [1,n]$，并且所有区间端点均为正整数。
Dream 取完两个区间，他会选择尽量多的盘，使得盘编号在 $P_1$ 里，歌曲在 $S_1$ 里，并且所有歌曲互不相同。他准备把这集音乐盘给 Tommy。
Dream 构造完集合发现他选了太多音乐盘，决定由以上选区间方法再次**均匀随机**选取两个区间 $P_2$ 和 $S_2$，其中 $P_2\subseteq P_1$ 并 $S_2\subseteq S_1$。这次，他构造的音乐盘集需要满足编号在 $P_2$ 里，歌曲在 $S_2$ 里。Dream 仍然会选尽量大，歌曲互不相同的集合。
**Dream 永远不会选空区间。**
现在 Tommy 感觉 Dream 给他的音乐盘太少了。请帮 Tommy 计算 Dream 第二次选取 **平均** 导致的集合大小减少量。
这里，平均对所有合法 $(P_1,S_1,P_2,S_2)$ 选取方案等权重平均。

inputFormat:
第一行一个正整数 $n$。
第二行 $n$ 个正整数，依次表示 $a_1,a_2,\dots,a_n$。

outputFormat: 假设答案可以表示为 $p/q$，其中 $p$ 和 $q$ 互质。请输出 $p\cdot q^{-1}\pmod{10^9+7}$。


title: 「MCOI-07」Dream and More Discs

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

description:
Dream 将 Tommy 的所有音乐盘分为 $n$ 类，其中第 $i$ 类有 $2^m-1$ 片音乐盘。所有盘都有一个唯一的正整数重要度。
现在 Dream 已经把所有类之内的音乐盘按照重要度递增排序。Dream 想知道**所有**盘中重要度第 $k$ 小是哪个盘。

由于音乐盘数量实在太多，Dream 不能直接给你所有音乐盘的重要度。在寻找答案时，Dream 允许你访问第 $i$ 类重要度第 $j$ 小的盘重要度值。

inputFormat:
交互开始时，评测机输入第一行为四个正整数 $n$，$m$，$k$，和 $Th$，其中 $Th$ 为最多应用访问次数。
每一次访问，评测机会回复所访问位置的音乐盘重要度。

outputFormat:
你的程序可以进行两个操作：

 1. `? i j`，表示访问第 $i$ 类型第 $j$ 小音乐盘重要度。评测机会回复这位置重要度。
 2. `! i j`，表示报告全局第 $k$ 小音乐盘为第 $i$ 类的第 $j$ 小音乐盘。


title: 「MCOI-07」Dream and Evaluation

description:
George 在学位运算。他编了一个位运算表达式，但是他不会高效计算这个表达式的值，于是他找 Dream 帮他计算。
George 的表达式有 $64$ 个 01 变量，分别编号为 $0$ 到 $63$。他提供了该表达式的[后缀表示法](https://baike.baidu.com/item/%E5%90%8E%E7%BC%80%E8%A1%A8%E7%A4%BA%E6%B3%95/20835385?fr=aladdin)。
后缀表示法里可能含有以下符号：

 - $0,1,\dots,63$，代表对应变量
 - `!&|^`，代表对应位运算

现在 Dream 有 $m$ 个情况。每一个情况固定所有 $64$ 个变量的值。他需要你对每一个情况计算给定表达式的值。
为了方便输入，这些情况进行压缩。定义 $a_{i,j}$ 为第 $i$ 情况里的第 $j$ 变量值，其中 $a_{i,j}\in\{0,1\}$；他会给你

$$b_i=\sum_{j=0}^{63}a_{i,j}2^j$$

可以证明，如果 $0\le b_i<2^{64}$，则 $b_i$ 唯一对应一组 $a_{i,0},a_{i,1},\dots,a_{i,63}$。

inputFormat:
第一行一个正整数 $n$，表示后缀表示法的长度。
接下来一行 $n$ 个符号，表示 George 的表达式。
接下来一行一个正整数 $m$。
接下来一行 $m$ 个整数，依次代表 $b_1,b_2,\dots,b_m$。

outputFormat: 输出 $m$ 个 01 字符，其中第 $i$ 输出字符代表第 $i$ 情况时，表达式的值。

hint:
#### 样例 1 解释

如果 $x=1$，则变量 $0$ 为 $1$，其余变量为 $0$。
如果 $x=9$，则仅变量 $0$ 和 $3$ 为 $1$。

#### 数据规模与约定

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

 - Subtask 1（7 pts）：$n,m\le10^3$。
 - Subtask 2（11 pts）：$b_i\in[0,2^{8}-1]$。
 - Subtask 3（41 pts）：$n,m\le5\times10^4$。
 - Subtask 4（41 pts）：没有额外限制。

对于所有数据，$1\le n,m\le10^5$，$0\le b_i<2^{64}$。


title: 「MCOI-07」Dream and Machine Learning

description:
Dream 构造了一个红石计算机来验证 $b^e\equiv r\pmod m$ 形式的公式。
Dream 固定了 $b$ 和 $m$ 并且构造了 $n$ 对满足以上条件的 $(e,r)$ 正整数对。
可惜，Dream 忘记了 $m$ 的具体值。现在他给了你 $b$ 和这 $n$ 对数。请替代 Dream 的计算机，回答 $q$ 组 $b^{a_i}\pmod m$ 形式的询问。

inputFormat:
第一行三个正整数，分别代表 $b$，$n$，和 $q$。
接下来 $n$ 行，每行两个正整数，分别代表一对 $e$ 和 $r$。
接下来 $q$ 行，每行一个正整数，代表一个 $a_i$。

outputFormat: 输出 $q$ 行，对应询问的答案。

samples:
请见附件 sample.in
请见附件 sample.out

hint:
#### 样例 1 解释

可以唯一确定 $m=97$。
样例 1 仅仅说明题意，并不代表任何 subtask 的任何测试点。

#### 数据规模与约定

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

 - Subtask 1（5 pts）：$m\le10^3$
 - Subtask 2（19 pts）：$m\le10^9$
 - Subtask 3（19 pts）：$m\le10^{19}$
 - Subtask 4（19 pts）：$m\le10^{29}$
 - Subtask 5（19 pts）：$m\le10^{99}$
 - Subtask 6（19 pts）：$m\le10^{199}$

对于 $100\%$ 的数据，$b\in\{2,3\}$，$1\le q\le100$，$2\le e,a_i\le 10^9$，$n=10^5$。
**保证** $m$ 为质数。
**保证** 所有 $e$ 互不相同。
**保证** 数据随机。


title: 「MCOI-07」Dream Fourier Transform

background:
Dream 的红石计算机升级为 Dream 平台了。
一个“Dream 程序”为一个在 Dream 平台下执行的程序。
Dream 平台的内存由 $5\times2^{17}$ 个非负整数构成，这些内存位置依次标号为 $0,1,\dots,5\times2^{17}-1$。初始所有内存位置均为 $0$。
Dream 平台有一个特性：第 $x$ 运算的结果在第 $x$ 内存位置存储，其中运算从 $0$ 编号。
Dream 程序为若干运算的有序序列，运算类型为：

 1. `>`，表示输入一个非负整数，结果为输入值。
 2. `< x`，表示输出内存位置 `x` 所含的值，结果为这个值。
 3. `S c`，表示结果为常量非负整数 $c$，其中 $0\le c<998244353$。
 4. `+ x y`，表示结果为内存位置 `x` 的值 加 内存位置 `y` 的值。
 5. `- x y`，表示结果为内存位置 `x` 的值 减 内存位置 `y` 的值。
 6. `* x y`，表示结果为内存位置 `x` 的值 乘 内存位置 `y` 的值。

其中所有运算在模 $998244353$ 意义下计算。

description:
Dream 有一个长度为 $n$ 的序列 $a_0,a_1,\dots,a_{n-1}$。

Dream 要支持两个操作：

 1. `1 i x`，表示将 $a_i$ 乘 $x$。
 2. `2 k`，表示定 $x=63912897^k$，并且求

$$\sum_{i=0}^{n-1}a_ix^i\pmod{998244353}$$

---

由战争及时，Dream 无法提供序列 $a$。他只能预测他会进行的操作。请构造一个“Dream 程序”，读入数组 $a$ 并且输出对应询问答案。

inputFormat:
第一行两个正整数，分别代表 $n$ 和 $q$。
接下来 $q$ 行，每行描述一个操作，由 `1 i x` 或 `2 k` 格式表示。

outputFormat:
第一行一个非负整数 $L$，代表所构造的 Dream 程序长度。
接下来 $L$ 行，每行描述一个运算。
你需要保证 $L\le5\times2^{17}$。

hint:
#### 温情提示

$$63912897\equiv3^{\frac{998244352}{2^{12}}}\pmod{998244353}$$

#### 样例解释

当 Dream 程序输入为序列 `[1,2,3]`，输出为序列 `[6,347675984]`，符合要求。

#### 数据规模与约定

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

 - Subtask 1（11 pts）：$n,q\le2^8$
 - Subtask 2（19 pts）：所有询问操作在修改操作后面。
 - Subtask 3（23 pts）：$n,q\le2^{10}$
 - Subtask 4（47 pts）：没有特殊限制。

对于 $100\%$ 的数据，$1\le n,q\le2^{12}$，$0\le i<n$，$0\le x,k<998244353$。


title: 【DSOI 2021】电子跃迁

background:
> “如果能证明大统一理论，这个世界将焕然一新。”\
“量子……量子……就差一点……”\
“嘶……哦。**我想我明白了**。”

description:
在你的视野下，出现了一排电子，他们分别拥有不同的能量。你需要做的是通过**将相邻电子互换**的方法，将电子排的有序。**有序**是指：能量最小的电子放到最靠近原子核的左边，将第二小的电子放在第二……将能量最大的电子放在最右边。\
可是，你发现电子轨道之间忽然出现了 $m$ 个奇怪的力，使位于第 $x_i$ 个位置的电子和位于第 $x_i+1$ 个位置的电子无法进行交换。

你深信这个力将会颠覆当下的物理理论。你需要做的是将现在的一排电子排得**尽量有序**以发现其中规律。

**尽量有序**是指：**在条件下**，能量最小的电子尽量放到左边直至出现屏障，以此类推。

inputFormat:
第一行输入两个整数 $n,m$ ，分别表示电子数量和力的数量。\
第二行输入 $n$ 个整数，表示初始电子排列，其中第 $i$ 个数 $a_i$ 代表第 $i$ 个电子拥有的能量。\
第三行包含 $m$ 个整数。其中第 $i$ 个整数 $x_i$ 表示位于第 $x_i$ 个位置的电子和位于第 $x_i+1$ 个位置的电子无法进行交换的。

outputFormat: 输出一行 $n$ 个整数，表示在这种情况下尽量有序的排列结果。


title: 【DSOI 2021】归零

background:
![](https://img-blog.csdnimg.cn/20201202201332449.png?x-oss-process=image)

能和强欲魔女谈话的机会，对其他人来说是不可多得的 。

进行问答只需要彼此而已，多余的闲功夫就省了吧 ，只有言语就够了 。

![](https://img-blog.csdnimg.cn/20201202200411570.png?x-oss-process=image)

你的求知欲、好奇心、强欲，我都给予肯定 。

说吧，你想问什么 ？

是关于为振救苍生免于饥饿，违背天命而创造出的野兽 $\left \lceil \right. $ 暴食魔女 $\left. \right \rfloor$ 达芙妮的事吗 ？

是那个打算用爱填满世界，而赐予非人之物情感 $\left \lceil \right. $ 色欲魔女 $\left. \right \rfloor$ 卡蜜拉的事吗？

是一边哀叹着世界充满争斗，却用暴力治愈所有人 $\left \lceil \right. $ 愤怒魔女 $\left. \right \rfloor$ 密涅瓦的事吗？

是仅仅为了追求安稳，就把龙赶到大瀑布彼端 $\left \lceil \right. $ 怠惰魔女 $\left. \right \rfloor$ 塞赫麦特的事吗？

是仗着年幼天真，却毫无慈悲地制裁世人 $\left \lceil \right. $ 傲慢魔女 $\left. \right \rfloor$ 缇丰的事吗？

是为了渴求世上一切智慧，就连死后的世界都舍不得放弃 那位知识欲望的化身 $\left \lceil \right. $ 强欲魔女 $\left. \right \rfloor$ 艾姬多娜的事吗？

还是说，是消灭所有魔女做自己的食粮，并与世界为敌的 $\left \lceil \right. $ 嫉妒魔女 $\left. \right \rfloor$ 那位令人忌讳的 $\left \lceil \right. $ 她 $\left. \right \rfloor$？

![](https://img-blog.csdnimg.cn/20201202200421879.png?x-oss-process=image)

description:
#### （ **若觉得题意不清，请造访 “输入格式” 查看简明化题意。**）

#### （ **请查看题目保证以确保能 solve the problem .**）

我想问的只有 ....

如果我有一串长度为 $n$ 的序列 $a$ ，编号从 $1\rightarrow n $ , $a_i$ 表示第 $i$ 个数.

我共将进行 $m$ 次四种类型的操作，其编号为给出的顺序 ：

$\left \lceil \right. $ 如果我有 $x$ 、$y$ 两值，我会用阴魔法将序列中所有下标 $i \equiv 0 \pmod{x} $ 的 $a_i$  异或上 $y$ 。$\left. \right \rfloor$

$\left \lceil \right. $ 同时我也会三省自身，问问自己序列中 $a_x$ 的值 。$\left. \right \rfloor$

$\left \lceil \right. $ 多次轮回让我明白，只有完美把握住每一次机遇，我才可以占据更大的有利因素。因而我将估量 $a_x$ 和我的预期 $y$ ，如果 $a_x \le y$ ，我将轮回并执行编号为 $u \rightarrow v$ 的操作中的 **阴魔法操作** 。$\left. \right \rfloor$

$\left \lceil \right. $ 另外，为了防止遗忘，我还会轮回执行编号为 $x$ 的操作。$\left. \right \rfloor$

你也知道，轮回的存档点是不能交错的，所以我的轮回是不会相交的。

请问你，能否帮我，回答我心中的问答？

inputFormat:
第一行两个数 $n$ ，$m$ ，表示序列长度和操作数。\
第二行 $n$ 个数 $a_i$ ，表示初始序列。\
接下来有 $m$ 行，有若干数字，第 $i + 2$ 行表示编号为 $i$ 的操作，第一个数 $op$ 为 $1 \rightarrow$ 4 的一个 :
- $op = 1$ : 读入 3 个数 $1$ , $x$ , $y$ , 对 $\forall$ $i \equiv 0 \pmod{x} $（ 也就是 $x$ , $2x$ … $kx $，$k \in  Z^+ $ 且 $k \times x \le n$ ）, $a_i = a_i \oplus y$（$\oplus$ 表示异或）。
- $op = 2$ : 读入 2 个数 $2$ , $x$ ，输出 $a_x$ 。
- $op = 3$ : 读入 5 个数 $3$ , $x$ , $y$ , $u$ , $v$  , 若 $a_x \le y$，执行编号为 $u \rightarrow v$  内所有 $op = 1$ 的操作，否则无视此操作。保证 $u \le v < i$ 。
- $op = 4$ : 读入 2 个数 $4$ , $x$ ， 执行编号为 $x$ 的操作。保证 $x < i$ 。

 因为轮回不交错：题目保证，若 $op_i = 3$，**则编号为 $u\rightarrow i-1$ 的操作，类型一定不为 $3$ or $4$ ；** 同时，若 $op_i = 4$ ，**则编号为 $x+1\rightarrow i-1$ 的操作，类型一定不为 $3$ or $4$ （ 但是 $x$ 位置可为 $3$ 、 $4$ 类型操作，即可以调用 ）。**

 用数学语言就是：**若 $op_i = 3$ ，则 $[u , i)$ 一定没有 $3$ or $4$ 操作 ; 若 $op_i = 4$ , 则 $(x, i)$ 一定没有 $3$ or $4$ 操作。**

outputFormat:
输出若干行。\
每一行为 $op=2$ 类型操作的询问结果或 $op = 4$ 类型操作调用的询问操作的询问结果。


title: 迷失森林

description:
首先给出一棵以 $1$ 为根，$n$ 个结点的树，定义为「单位树」。

现有 $n$ 个结构与「单位树」完全相同的树，要将 $n$ 个树再用 $n-1$ 条边连接起来。

为方便叙述，用符号 $(a,b)$ 表示结点 $a$ 所代表树中，编号为 $b$ 的结点。

连接方式如下：

1. 将 $n$ 棵树按照「单位树」的结构摆放好。

2. 对于每个 $i(1<i\leq n)$，连接结点 $(i,1)$ 和 $(f_i,f_i)$。其中 $f_i$ 表示「单位树」中结点 $i$ 的父亲。

求将 $n$ 棵树连接后，整棵包含 $n^2$ 个结点的树中，树上两点简单路径所包含的 **结点** 个数的最大值。

inputFormat:
第一行输入一个正整数 $n$，表示「单位树」的结点数。

接下来输入 $n-1$ 行，每行两个正整数 $u,v$，表示「单位树」中的一条边。

outputFormat: 输出一行一个正整数，表示树上两点简单路径所包含的 **结点** 个数的最大值。

hint:
#### 样例说明

样例 #1 ![](https://i.loli.net/2021/10/24/QRqkpeC7u4dYA5o.png)

样例 #2 如下图，以 $(3,4)$ 和 $(4,4)$ 为两端的路径包含 $9$ 个结点，长度为 $9$。

![](https://i.loli.net/2021/10/24/2IVR9ZXuNcdzTQp.png)

样例 #3 如下图，取 $(6,6)$ 和 $(9,9)$，包含 $11$ 个结点。

![](https://i.loli.net/2021/10/24/th8CWcbxQEGVXRm.png)

事实上，任取两个最近公共祖先为 $1$ 的橙色结点，答案均为 $11$。

#### 数据范围

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

| 子任务编号 | 分值 | $n\le$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $10$ | $10$ | $\times$ |
| $2$ | $12$ | $10^6$ | $v=u+1$ |
| $3$ | $6$ | $10^6$ | $u=1$ |
| $4$ | $18$ | $=2^k(k\in\mathbf{Z})$ | $u=\left\lfloor\dfrac{v}{2}\right\rfloor$ |
| $5$ | $27$ | $10^3$ | 树的形态随机 |
| $6$ | $27$ | $10^6$ | $\times$ |

对于 $100\%$ 的数据：$1\leq n\leq10^6$，结点编号介于 $1\sim n$ 之间。

**本题可能略微卡常。**

时限缩短为 1s，原因如下：

- 讨论区认为本题撞原，为防止所谓「加强版」的 $O(n\log n)$ 做法直接冲过本题，时限缩短。

- 最优解能跑进 200ms 以内。

- 由于出题人懒惰，懒得 $n\le10^6\rightarrow n\le10^7$ 只能通过缩短时限来卡掉所谓原题做法（实际上是错解）。


title: [NOIP2020] 排水系统

description:
对于一个城市来说，排水系统是极其重要的一个部分。

有一天，小 C 拿到了某座城市排水系统的设计图。排水系统由 $n$ 个排水结点（它们从 $1 \sim n$ 编号）和若干个单向排水管道构成。每一个排水结点有若干个管道用于汇集其他排水结点的污水（简称为该结点的汇集管道），也有若干个管道向其他的排水结点排出污水（简称为该结点的排出管道）。

排水系统的结点中有 $m$ 个污水接收口，它们的编号分别为 $1, 2, \ldots , m$，污水只能从这些接收口流入排水系统，并且这些结点没有汇集管道。排水系统中还有若干个最终排水口，它们将污水运送到污水处理厂，没有排出管道的结点便可视为一个最终排水口。

现在各个污水接收口分别都接收了 $1$ 吨污水，污水进入每个结点后，会均等地从当前结点的每一个排出管道流向其他排水结点，而最终排水口将把污水排出系统。

现在小 C 想知道，在该城市的排水系统中，每个最终排水口会排出多少污水。该城市的排水系统设计科学，管道不会形成回路，即不会发生污水形成环流的情况。

inputFormat:
第一个两个用单个空格分隔的整数 $n, m$。分别表示排水结点数与接收口数量。
接下来 $n$ 行，第 $i$ 行用于描述结点 $i$ 的所有排出管道。其中每行第一个整数 $d_i$ 表示其排出管道的数量，接下来 $d_i$ 个用单个空格分隔的整数 $a_1, a_2, \ldots , a_{d_i}$ 依次表示管道的目标排水结点。
保证不会出现两条起始结点与目标结点均相同的管道。

outputFormat: 输出若干行，按照编号从小到大的顺序，给出每个最终排水口排出的污水体积。其中体积使用分数形式进行输出，即每行输出两个用单个空格分隔的整数 $p$，$q$，表示排出的污水体积为 $\frac{p}{q}$。要求 $p$ 与 $q$ 互素，$q = 1$ 时也需要输出 $q$。

samples:
见附件中的 water/water2.in
见附件中的 water/water2.ans

samples:
见附件中的 water/water3.in
见附件中的 water/water3.ans

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

$1$ 号结点是接收口，$4, 5$ 号结点没有排出管道，因此是最终排水口。
$1$ 吨污水流入 $1$ 号结点后，均等地流向 $2, 3, 5$ 号结点，三个结点各流入 $\frac{1}{3}$ 吨污水。
$2$ 号结点流入的 $\frac{1}{3}$ 吨污水将均等地流向 $4, 5$ 号结点，两结点各流入 $\frac{1}{6}$ 吨污水。
$3$ 号结点流入的 $\frac{1}{3}$ 吨污水将均等地流向 $4, 5$ 号结点，两结点各流入 $\frac{1}{6}$ 吨污水。
最终，$4$ 号结点排出 $\frac{1}{6} + \frac{1}{6} = \frac{1}{3}$ 吨污水，$5$ 号结点排出 $\frac{1}{3} + \frac{1}{6} + \frac{1}{6} = \frac{2}{3}$ 吨污水。

**【数据范围】**

| 测试点编号 | $n \le$ | $m \le$ |
|:-:|:-:|:-:|
| $1 \sim 3$ | $10$ | $1$ |
| $4 \sim 6$ | ${10}^3$ | $1$ |
| $7 \sim 8$ | ${10}^5$ | $1$ |
| $9 \sim 10$ | ${10}^5$ | $10$ |

对于全部的测试点，保证 $1 \le n \le {10}^5$，$1 \le m \le 10$，$0 \le d_i \le 5$。

数据保证，污水在从一个接收口流向一个最终排水口的过程中，不会经过超过 $10$ 个中间排水结点（即接收口和最终排水口不算在内）。


title: [NOIP2020] 微信步数

description:
小 C 喜欢跑步，并且非常喜欢在微信步数排行榜上刷榜，为此他制定了一个刷微信步数的计划。

他来到了一处空旷的场地，处于该场地中的人可以用 $k$ 维整数坐标 $(a_1, a_2, \ldots , a_k)$ 来表示其位置。场地有大小限制，第 $i$ 维的大小为 $w_i$，因此处于场地中的人其坐标应满足 $1 \le a_i \le w_i$（$1 \le i \le k$）。

小 C 打算在接下来的 $P = w_1 \times w_2 \times \cdots \times w_k$ 天中，每天从场地中一个新的位置出发，开始他的刷步数计划（换句话说，他将会从场地中每个位置都出发一次进行计划）。

他的计划非常简单，每天按照事先规定好的路线行进，每天的路线由 $n$ 步移动构成，每一步可以用 $c_i$ 与 $d_i$ 表示：若他当前位于 $(a_1, a_2, \ldots , a_{c_i}, \ldots, a_k)$，则这一步他将会走到 $(a_1, a_2, \ldots , a_{c_i} + d_i, \ldots , a_k)$，其中 $1 \le c_i \le k$，$d_i \in \{-1, 1\}$。小 C 将会不断重复这个路线，直到他走出了场地的范围才结束一天的计划。（即走完第 $n$ 步后，若小 C 还在场内，他将回到第 $1$ 步从头再走一遍）。

小 C 对自己的速度非常有自信，所以他并不在意具体耗费的时间，他只想知道 $P$ 天之后，他一共刷出了多少步微信步数。请你帮他算一算。

inputFormat:
第一行两个用单个空格分隔的整数 $n, k$。分别表示路线步数与场地维数。
接下来一行 $k$ 个用单个空格分隔的整数 $w_i$，表示场地大小。
接下来 $n$ 行每行两个用单个空格分隔的整数 $c_i, d_i$，依次表示每一步的方向，具体意义见题目描述。

outputFormat:
仅一行一个整数表示答案。答案可能很大，你只需要输出其对 ${10}^9 + 7$ 取模后的值。
若小 C 的计划会使得他在某一天在场地中永远走不出来，则输出一行一个整数 $-1$。

samples:
见附件中的 walk/walk3.in
见附件中的 walk/walk3.ans

samples:
见附件中的 walk/walk4.in
见附件中的 walk/walk4.ans


title: [NOIP2020] 字符串匹配

description:
小 C 学习完了字符串匹配的相关内容，现在他正在做一道习题。

对于一个字符串 $S$，题目要求他找到 $S$ 的所有具有下列形式的拆分方案数：

$S = ABC$，$S = ABABC$，$S = ABAB \ldots ABC$，其中 $A$，$B$，$C$ 均是非空字符串，且 $A$ 中出现奇数次的字符数量不超过 $C$ 中出现奇数次的字符数量。

更具体地，我们可以定义 $AB$ 表示两个字符串 $A$，$B$ 相连接，例如 $A = \texttt{aab}$，$B = \texttt{ab}$，则 $AB = \texttt{aabab}$。

并递归地定义 $A^1=A$，$A^n = A^{n - 1} A$（$n \ge 2$ 且为正整数）。例如 $A = \texttt{abb}$，则 $A^3=\texttt{abbabbabb}$。

则小 C 的习题是求 $S = {(AB)}^iC$ 的方案数，其中 $F(A) \le F(C)$，$F(S)$ 表示字符串 $S$ 中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 $A$、$B$、$C$ 中有至少一个字符串不同。

小 C 并不会做这道题，只好向你求助，请你帮帮他。

inputFormat:
本题有多组数据，输入文件第一行一个正整数 $T$ 表示数据组数。

每组数据仅一行一个字符串 $S$，意义见题目描述。$S$ 仅由英文小写字母构成。

outputFormat: 对于每组数据输出一行一个整数表示答案。

samples:
5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

samples:
见附件中的 string/string3.in
见附件中的 string/string3.ans

samples:
见附件中的 string/string4.in
见附件中的 string/string4.ans

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

对于第一组数据，所有的方案为

1. $A=\texttt{n}$，$B=\texttt{nr}$，$C=\texttt{nnr}$。
2. $A=\texttt{n}$，$B=\texttt{nrn}$，$C=\texttt{nr}$。
3. $A=\texttt{n}$，$B=\texttt{nrnn}$，$C=\texttt{r}$。
4. $A=\texttt{nn}$，$B=\texttt{r}$，$C=\texttt{nnr}$。
5. $A=\texttt{nn}$，$B=\texttt{rn}$，$C=\texttt{nr}$。
6. $A=\texttt{nn}$，$B=\texttt{rnn}$，$C=\texttt{r}$。
7. $A=\texttt{nnr}$，$B=\texttt{n}$，$C=\texttt{nr}$。
8. $A=\texttt{nnr}$，$B=\texttt{nn}$，$C=\texttt{r}$。

**【数据范围】**

| 测试点编号 | $\lvert S \rvert \le$ | 特殊性质 |
|:-:|:-:|:-:|
| $1 \sim 4$ | $10$ | 无 |
| $5 \sim 8$ | $100$ | 无 |
| $9 \sim 12$ | $1000$ | 无 |
| $13 \sim 14$ | $2^{15}$ | $S$ 中只包含一种字符 |
| $15 \sim 17$ | $2^{16}$ | $S$ 中只包含两种字符 |
| $18 \sim 21$ | $2^{17}$ | 无 |
| $22 \sim 25$ | $2^{20}$ | 无 |

对于所有测试点，保证 $1 \le T \le 5$，$1 \le |S| \le 2^{20}$。


title: [NOIP2020] 移球游戏

description:
小 C 正在玩一个移球游戏，他面前有 $n + 1$ 根柱子，柱子从 $1 \sim n + 1$ 编号，其中 $1$ 号柱子、$2$ 号柱子、……、$n$ 号柱子上各有 $m$ 个球，它们自底向上放置在柱子上，$n + 1$ 号柱子上初始时没有球。这 $n \times m$ 个球共有 $n$ 种颜色，每种颜色的球各 $m$ 个。

初始时一根柱子上的球可能是五颜六色的，而小 C 的任务是将所有同种颜色的球移到同一根柱子上，这是唯一的目标，而每种颜色的球最后放置在哪根柱子则没有限制。

小 C 可以通过若干次操作完成这个目标，一次操作能将一个球从一根柱子移到另一根柱子上。更具体地，将 $x$ 号柱子上的球移动到 $y$ 号柱子上的要求为：

1. $x$ 号柱子上至少有一个球；
2. $y$ 号柱子上至多有 $m - 1$ 个球；
3. 只能将 $x$ 号柱子最上方的球移到 $y$ 号柱子的最上方。

小 C 的目标并不难完成，因此他决定给自己加加难度：在完成目标的基础上，使用的操作次数不能超过 $820000$。换句话说，小 C 需要使用至多 $820000$ 次操作完成目标。

小 C 被难住了，但他相信难不倒你，请你给出一个操作方案完成小 C 的目标。合法的方案可能有多种，你只需要给出任意一种，题目保证一定存在一个合法方案。

inputFormat:
第一行两个用空格分隔的整数 $n, m$。分别表示球的颜色数、每种颜色球的个数。
接下来 $n$ 行每行 $m$ 个用单个空格分隔的整数，第 $i$ 行的整数按自底向上的顺序依次给出了 $i$ 号柱子上的球的颜色。

outputFormat:
本题采用自定义校验器（special judge）评测。
你的输出的第一行应该仅包含单个整数 $k$，表示你的方案的操作次数。你应保证 $0 \le k \le 820000$。
接下来 $k$ 行每行你应输出两个用单个空格分隔的正整数 $x, y$，表示这次操作将 $x$ 号柱子最上方的球移动到 $y$ 号柱子最上方。你应保证 $1 \le x, y \le n + 1$ 且 $x \ne y$。

samples:
见附件中的 ball/ball2.in
见附件中的 ball/ball2.ans

samples:
见附件中的 ball/ball3.in
见附件中的 ball/ball3.ans

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

柱子中的内容为：按自底向上的顺序依次给出柱子上每个球的颜色。

| 操作 | $1$ 号柱子 | $2$ 号柱子 | $3$ 号柱子 |
|:-:|:-:|:-:|:-:|
| 初始 | $1\ 1\ 2$ | $2\ 1\ 2$ | |
| $1\ 3$ | $1\ 1$ | $2\ 1\ 2$ | $2$ |
| $2\ 3$ | $1\ 1$ | $2\ 1$ | $2\ 2$ |
| $2\ 3$ | $1\ 1$ | $2$ | $2\ 2\ 1$ |
| $3\ 1$ | $1\ 1\ 1$ | $2$ | $2\ 2$ |
| $3\ 2$ | $1\ 1\ 1$ | $2\ 2$ | $2$ |
| $3\ 2$ | $1\ 1\ 1$ | $2\ 2\ 2$ | |

**【数据范围】**

| 测试点编号 | $n \le$ | $m \le$ |
|:-:|:-:|:-:|
| $1 \sim 2$ | $2$ | $20$ |
| $3 \sim 5$ | $10$ | $20$ |
| $6 \sim 8$ | $50$ | $85$ |
| $9 \sim 14$ | $50$ | $300$ |
| $15 \sim 20$ | $50$ | $400$ |

对于所有测试点，保证 $2 \le n \le 50$，$2 \le m \le 400$。

**【校验器】**

为了方便选手测试，在附件中的 `ball` 目录下我们下发了 `checker.cpp` 文件，选手可以编译该程序，并使用它校验自己的输出文件。但请注意它与最终评测时所使用的校验器并不完全一致。你也不需要关心其代码的具体内容。

编译命令为：`g++ checker.cpp −o checker -std=c++11`。

`checker` 的使用方式为：`checker <inputfile> <outputfile>`，参数依次表示输入文件与你的输出文件。

若你输出的数字大小范围不合法，则校验器会给出相应提示。若你的输出数字大小范围正确，但方案错误，则校验器会给出简要的错误信息：

1. `A x`，表示进行到第 $x$ 个操作时不合法。
2. `B x`，表示操作执行完毕后第 $x$ 个柱子上的球不合法。

若你的方案正确，校验器会给出 `OK`。


title: 「MCOI-04」Dream and the Multiverse

background:
[Link](https://youtu.be/tylNqtyj0gs?t=2388)

*I have gone over the scenarios in my head,*

*and there are 6.96969 billion outcomes, and only one of them -*

*- do I win.*

description:
Dream 将时空抽象为一颗 $n$ 节点有向有根树，其中树根为节点 $1$ 并且所有边的方向都为浅往深。
Dream 用他的超能力在这颗树上额外添加 $m$ 条有向边，但最终的图仍然是无环图。
Dream 进而将一个事件抽象为图上的一个节点，将一个时代抽象为图上的一个简单路径。
Dream 认为一对事件 $(i,j)$ **可行** 当且仅当存在一个时代，使得时代的首事件是 $i$，末事件是 $j$。
Dream 现在有 $q$ 组询问。第 $i$ 组询问用两个正整数 $l_i$ 与 $r_i$ 表示，其中 $l_i\le r_i$。
Dream 想知道，对每一组询问，有多少对 **可行** 事件 $(i,j)$，使得 $i,j\in[l,r]$。

inputFormat:
第一行两个整数 $n,m$。
接下来一行 $n-1$ 个正整数描述树的结构。第 $i$ 个数代表 $i+1$ 号节点的父亲的编号 $f_i$，也就是说存在一个 $f_i$ 往 $i$ 的一条边。
接下来 $m$ 行，每行两个正整数 $u,v$，表示一条 $u$ 往 $v$ 额外添加的边。
接下来一个正整数 $q$。
接下来 $q$ 行，每行两个正整数 $l,r$，表示一组询问。

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

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

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

 - Subtask 1（1 pts）：树形成一条链。
 - Subtask 2（11 pts）：$n,q,m\le1000$。
 - Subtask 3（7 pts）：$m\le 5$。
 - Subtask 4（23 pts）：$n,q,m\le5\times10^4$。
 - Subtask 5（17 pts）：$q\le 10^5$。
 - Subtask 6（41 pts）：没有特殊限制。

对于 $100\%$ 的数据，$2\le n\le 10^5$，$0\le m\le10^5$，$1\le q\le 10^6$。
**保证** 额外添加的边不会形成环，给定的 $f_i$ 形成一颗根为 $1$ 的树。
**保证** $l\le r$。

#### 说明

[Minecraft OI Round 4](https://www.luogu.com.cn/contest/33344) C
idea & solution：w33z8kqrqk8zzzx33 check：ClCN


title: [NEERC2016] Indiana Jones and the Uniform Cave

background: 这是一道 IO 交互题。

description:
Indiana Jones has stuck in the Uniform Cave. There are many round chambers in the cave, and all of them are indistinguishable from each other. Each chamber has the same number of one-way passages evenly distributed along the chamber’s wall. Passages are indistinguishable from each other, too. The Cave is magical. All passages lead to other chambers or to the same one. However, the last passage, after all passages are visited, leads to the treasure. Even the exact number of chambers is a mystery. It is known that each chamber is reachable from each other chamber using the passages.

Dr. Jones noticed that each chamber has a stone in the center. He decided to use these stones to mark chambers and passages. A stone can be placed to the left or to the right of one of the passages. When Indiana Jones enters the chamber all that he can observe is the location of the stone in the chamber. He can move the stone to the desired location and take any passage leading out of the chamber.

Your task is to help Indiana Jones to visit every passage in the Uniform Cave and find the treasure.

inputFormat:
First, the testing system writes the integer m — the number of passages in each chamber ($2 \leq m \le 20$).

Dr. Jones enters the chamber and sees, in the next line, where the stone is placed: either in the “center” of the chamber or to the “left”, or to the “right” of some passage. On the first visit to the chamber, the stone is in the center.

Your solution shall output his actions: the number and the side of the passage to place the stone to, and the number of the passage to take. Both numbers are relative to the passage marked by the stone, counting clockwise from 0 to m − 1. If the stone is in the center of the chamber, the origin is random.

For example, “3 left 1” tells that Dr. Jones moves the stone three passages clockwise and places it to the left of the passage, then he takes the passage to the right of the initial stone position.

After each move testing system tells either the location of the stone in the next chamber or “treasure”, if Indiana Jones had found it. The testing system writes “treasure” when all the passages are visited.

If Dr. Jones does not find the treasure room after 20 000 passages are taken, he starves to death, and your solution receives the “Wrong Answer” outcome. You also receive this outcome if your solution terminates before all passages are taken.

The total number of chambers in the cave is unknown, but you may assume that it does not exceed 20, and that each chamber is reachable from every other chamber.

translation:
现在在一个洞穴里寻宝。这个洞穴有 $n$ 个房间。房间是不可区分的。每个房间都引出 $m$ 个单向道路，终点可以是自己也可以是其它房间。这些单向道路的入口均匀地分布在房间的墙壁上，且每条单向道路也是不可区分的。保证整个有向图是强连通的。你一开始在某一个房间，如果遍历了所有的边，就能找到宝藏。

每个房间有一个石子，这也是你区分房间和道路的唯一工具。一开始石子是在这个房间的某一个通道的入口前，并且是放在中央的。你每到一个房间，可以选择将石子移动到某个通道前，把它放在通道左边或者右边（不能是中间），然后再从某个通道走出去。你不可以把石子带出房间。你并没有携带过多的食物，所以如果你走了超过 $20000$ 条边，你就会因为食物耗尽而饿死。你要在规定步数之内找到宝藏。

### 输入格式

共 $m$ 行，每行一个字符串，表示该房间内石头被放置的位置为某个通道的 $"center"$，$"left"$ 或 $"right"$。当第一次到达一个墓室时，石头处在中间(center)。

### 输出格式

每行一个非负整数 $st$，表示将石头放在原所在位置顺时针方向第 $st$ 个通道入口；一个字符串，表示将它放在该通道入口 $dir$ 的位置（$"center"$，$"left"$ 或 $"right"$）；一个非负整数 $pa$ ，表示从石子的原来位置顺时针方向第 $pa$ 个通道走出。

通道顺时针从 $0$ 到 $m−1$ 编号。如果石头一开始是在中间（$center$），它会位于随机一个通道入口处。

每走一步，评测机会返回该房间的石头的位置或者 $"treasure"$ （如果您找到了宝藏且所有的通道都被走过时，就会反馈 $"treasure"$ ）。

**举个栗子**：`3 left 1` 表示将石头顺时针移动了 $3$ 个通道，并将其放置在该通道的左侧，然后走向最初石头所在位置的右侧的通道。

你最多可以进行 $20000$ 次操作。

samples:
2
center
left
center
left
right
treasure

samples:
0 left 0
1 left 1
1 right 0
0 left 0
1 right 0

hint: Dr. Jones enters the example cave and sees that the stone in the first chamber is in the center. He marks the chamber by placing the stone to the left of some passage and takes it. He sees the chamber where the stone is to the left of the passage, so he is in the first chamber again. He moves the stone clockwise and takes the passage marked by it. This passage leads to the second chamber. He marks it by placing the stone to the right of some passage and takes another one. He is in the first chamber again, so he returns to the second chamber and takes the remaining passage. This passage leads to the treasure.


title: 『JROI-4』淘气的猴子

background:
众所周知，jockbutt 是一个可爱的女孩纸。
![](https://cdn.luogu.com.cn/upload/image_hosting/73du6v88.png)

description:
jockbutt 有一个正整数序列，长度为 $n$，分别为 $a_1,a_2...a_n$，她非常喜欢这个序列，平时都非常爱惜它们。

可是有一天，当 jockbutt 在和你约会的时候，有一只淘气的小猴子改变了这个序列。

猴子操作了 $m$ 次。

猴子的操作有两种类型：

- $\texttt{1 x y}$ 表示第 $x$ 个元素加上第 $y$ 个元素。
- $\texttt{2 x y}$ 表示第 $x$ 个元素乘上第 $y$ 个元素。

特别且显然地，当 $x=y$，新的 $x$ 就等于原来的 $x$ 的两倍或平方。

序列最后结果形如 $b_1,b_2...b_n$。

等到 jockbutt 回来时，全洛谷的人都在看猴子。$\colorbox{white}{\color{white}{\text{其实 jockbutt 才是他们看的猴子吧}}}$

jockbutt 非常生气，希望你能告诉她这个序列最初的形态，也就是 $a_1,a_2,a_3,...,a_n$，否则她就会嘤嘤嘤...

inputFormat:
一共有 $m+2$ 行。

第一行输入两个数 $n,m$。

第二行输入 $n$ 个数 $b_1,b_2,\cdots,b_n$，表示经过操作后的序列。

第 $3\sim m+2$ 行每一行输入 $3$ 个数 $k,x,y$ ，分别表示操作类型，以及操作中的 $x$ 和 $y$。

outputFormat: 一行，$n$ 个整数 $a_1,a_2...a_n$，表示序列最初的样子。


title: 【DSOI 2021】积木

background:
"你听说过死亡游戏吗？就是将你关在一个暗无天日的房间里，给你一些琢磨不透的线索，倘若你不能解决问题，就给予你死亡的馈赠。

“嗯？慌什么，你现在仅仅是在这个不透风的房间里，我所要你回答的，也仅仅是个简单的问题而已。

“有意见吗？那好的，游戏开始。”

description:
“现在，你所拥有的是若干个棱长均为 $1$ 的正方体积木。而我，游戏的所有者，将会告诉你最终搭成的立体图形的主视图和左视图。你以为要你搭成这样的图形？别慌，游戏还远远没有这么简单。我将在这个图形中将主视图的其中几列给隐藏掉，如此一来，你就无法观察到他们的高度了。

“为了让这个游戏变得更有意思，我规定这些你无法观察到的数列的高度是任意的——这可以由你来决定。

“想必我亲爱的玩家，你小学时便知道，仅有主视图和左视图是无法确定一个图形的形状的，何况还有一部分被我隐藏了。因此，我们记 $k$ 为能够搭出我给出的图形的积木数，请你告诉我，最多有多少个整数 $k$ 能够满足我的要求呢？ ”（即，请你**先自行决定好未知数列的取值**，**再根据这一取值来求出** $k$，你需要先决定高度使 $k$ 能取的值最多）

inputFormat:
**本题有多组数据。**\
第一行输入一个整数 $T$，表示数据组数。\
对于每一组数据：\
第一行输入两个整数 $n,m$，表示最终积木形状的长和宽。\
第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示主视图从左至右第 $i$ 列所看到的方块的高度。特别的，若 $a_i=-1$，则表示这一列的高度是任意的。\
第三行包含 $m$ 个整数，第 $i$ 个整数 $b_i$ 表示左视图从后至前第 $i$ 列所看到的方块的高度。保证不存在高度未知的列。

outputFormat: 对于每一组数据，输出一行一个整数，表示最多的能够满足要求的整数 $k$ 的数量。特别的，如果没有满足条件的整数 $k$，输出 $0$。

hint:
**【样例解释】**\
对于第一组数据：\
可行的 $k$ 值分别为：$6,7,8$。
对于每一个 $k$ 值，给出一种可能的构造如下（给出俯视图，数字表示该格的高度）：
![](https://cdn.luogu.com.cn/upload/image_hosting/t968uvlx.png)\
对于第二组数据：\
当未知列的高度取 $2$ 时，满足要求的 $k$ 的数量最多，共有 $5$ 个，分别为：$4,5,6,7,8$。

**【数据范围和限制】**\
**本题采用捆绑测试。** 你必须通过 Subtask 中所有的测试点才能获得该 Subtask 的分数。

| Subtask | 分值  | $n,m,a_i,b_i \le$ |               特殊性质                |
| :-----: | :---: | :---------------: | :-----------------------------------: |
|    1    | 7pts  |        $3$        |                  无                   |
|    2    | 8pts  |       $10$        | 保证数列 $a$ 中 $-1$ 的数量不大于 $4$ |
|    3    | 8pts  |      $1000$       |           保证 $a_i \ne -1$           |
|    4    | 12pts |   $2\times10^4$   |           保证 $a_i \ne -1$           |
|    5    | 7pts  |      $1000$       |          保证所有 $b_i$ 相等          |
|    6    | 8pts  |   $2\times10^4$   |          保证所有 $b_i$ 相等          |
|    7    | 15pts |      $1000$       |                  无                   |
|    8    | 35pts |   $2\times10^4$   |                  无                   |

对于 $100\%$ 的数据，满足 $1 \le n,m \le 2\times10^4,-1 \le a_i \le 2\times10^4,0 \le b_i \le 2\times10^4,0 \le T \le 100$。

本题读入数据量较大，请用**较快的读入方式**。


title: 「dWoi R1」Sweet Fruit Chocolate

background:
[事情来源 ……](https://www.bilibili.com/video/BV19Z4y1K7dH)

我们的东条妈妈在残害了梦野之后，还想继续她的事业，残害可怜的最原。她发现最原很喜欢吃甜甜的巧克力，另外还有一种东西叫做西西弗水果，他富含营养但没那么好吃，因此，她想把这些巧克力淋在西西弗水果上。

description:
东条把想淋的巧克力做成了一个巧克力喷泉树。巧克力喷泉树是一棵 $n$ 个节点的树。每个节点都有一个西西弗水果。对于每一个节点 $u$，你有两种选择：你可以在节点 $u$ 放置 $a_u$ 个水果，也可以一个水果都不放。然后，东条会在根节点往下淋巧克力汁。节点 $u$ 给最原带来的营养值是 $u$ 及其子树中所放置的西西弗水果的数量。东条想要知道，对于所有 $2^n$ 个放水果方案，最原所获得的营养值之和的总和是多少。答案对 $998244353$ 取余。

树的根节点为 $1$。

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

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

后面 $n-1$ 行每行两个正整数 $u,v$ $(1\le u,v\le n)$，代表有树中一条边 $(u,v)$。

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


title: [Ynoi2008] stcm

background:
w33z 是良心出题人！

请使用高效输出方式，本题最多需要输出 50MB。

description:
给定一棵树，你可以维护一个集合，支持三种操作：

1. 当前集合中插入一个节点 $x$
2. 撤回上一次插入操作
3. 将当前点集标为第 $i$ 个点的子树补信息

一个点 $x$ 的子树补信息定义为，树的点集除去 $x$ 的子树（包括 $x$）内的点得到的集合；
需要保证每个点的子树补信息都是正确的。

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

一组测试数据格式为：

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

之后一行 $n-1$ 个正整数，第 $i$ 个数表示 $i+1$ 节点的父亲节点 $j$，保证 $j<i+1$。

请读入至 EOF。

outputFormat:
对每一组数据，输出一个字符串，从左往右，每个"+x"形式的子串代表进行一次 1 操作，对象为编号 $x$ 的节点，每个"-"子串代表进行一次 2 操作，每个"=x"形式的子串代表进行一次 3 操作，对象为编号 $x$ 的节点，每个"!"子串代表全部操作都已结束，在其后面的任何输入会被忽略，字符串必须以"!"表示结束。

输出的字符串中不允许以任何空白字符分隔。

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

对于 $100\%$ 的数据，满足 $1\le n\le 10^5$，$1\le T\le 3$。

题目采用 Special Judge 评测。

允许进行的 1 操作次数为 $4.5 \times 10^6$ 次，不允许插入一个当前集合中存在的元素。

当最后一次未被撤回的插入操作不存在时，不允许进行 2 操作。

对每个点，必须对其进行**恰好一次** 3 操作。

**所有测试数据输出独立检验。**


title: B Highbit & lowbit

description:
定义一个正整数的 $\mathrm{highbit}$ 为该数在二进制表示下的最高二进制位的位值，如 $\mathrm{highbit}(22_{(10)})=\mathrm{highbit}(10110_{(2)})=10000_{(2)}=16_{(10)}$。

定义一个正整数的 $\mathrm{lowbit}$ 为该数在二进制表示下的最低非零二进制位的位值，如 $\mathrm{lowbit}(22_{(10)})=\mathrm{lowbit}(10110_{(2)})=10_{(2)}=2_{(10)}$。

再定义两种操作：

- 操作 $1$：将一个正整数 $x$ 变为 $x+\mathrm{lowbit}(x)$。
- 操作 $2$：将一个正整数 $x$ 变为 $x+\mathrm{highbit}(x)$。

现给定一个操作序列和 $q$ 次询问，每次询问包含 $3$ 个正整数 $l,r,x$，表示将 $x$ 从左到右依次执行 $l\sim r$ 的操作，请输出 $x$ 的值，由于答案可能很大，请输出答案对 $10^9+7$ 取模的值。

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

接下来一行一个字符串 $s$，长度为 $n$，其中仅含有 `0`，`1`。

若第 $i$ 个字符为 `0`，则表示一个 $1$ 操作，即 $x=x+\mathrm{lowbit}(x)$。

若第 $i$ 个字符为 `1`，则表示一个 $2$ 操作，即 $x=x+\mathrm{highbit}(x)$。

之后 $q$ 行，每行 $3$ 个正整数 $l,r,x$，表示一次询问。

outputFormat: 对于每一个询问，输出一行一个数表示答案对 $10^9+7$ 取模的结果。

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

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

对于所有测试点，满足 $1\leq n,q\leq 5\times 10^5$，$1\leq x<2^{30}$。详细数据范围如下：

- Subtask #1 (12 pts): $n,q\le 10$，$x\le 32767$。
- Subtask #2 (23 pts): $n,q\le 10^3$。
- Subtask #3 (11 pts): $n,q\leq 10^5$，字符串中仅含有 `1`。
- Subtask #4 (11 pts): $n,q\leq 10^5$，字符串中仅含有 `0`。
- Subtask #5 (6 pts): $n,q\leq 10^5$，保证每次询问的 $x$ 均可以表示为 $2^a$ 的形式，$a$ 为非负整数。
- Subtask #6 (15 pts): $n,q\leq 10^5$，保证每次询问的 $x$ 均可以表示为 $2^a+2^b$ 的形式，$a,b$ 均为非负整数。
- Subtask #7 (10 pts): $n,q\le 10^5$。
- Subtask #8 (12 pts): 没有任何附加限制。


title: [Ynoi2008] rdCcot

description:
给一棵边权为 $1$ 的树和一个常数 $C$，节点用 $1$ 到 $n$ 的整数表示。

定义 $dist(a,b)$ 为节点 $a,b$ 在树上的距离，即 $a$ 到 $b$ 的简单路径上的边权和，特别地，$dist(a,a) = 0$。

每次查询的时候给出一个区间 $[l,r]$，查询有多少个 C-块，定义如下：

对任意两个节点 $a,b$，定义 $a,b$ 是 C-连通的，当且仅当存在一个长为 $t$ 的节点序列 $\{v_i\}$，满足：

1. $v_1=a$
2. $v_t=b$
3. 对任意 $1\le i\le t-1$，$dist(v_i,v_{i+1})\le C$
4. 对任意 $1\le i\le t$，$l\le v_i\le r$

定义“C-块”为一个点集 $S$，满足：

1. 对任意 $a$ 属于 $S$，$b$ 属于 $S$ 的补集，$a,b$ 不 C-连通
2. 对任意 $a,b$ 属于 $S$，$a$ 和 $b$ C-连通
3. 对任意 $a$ 属于 $S$，有 $l\le a \le r$

inputFormat:
第一行三个数 $n$，$m$，$C$ 依次表示树的节点个数，询问次数，还有常数 $C$；

第二行共 $n-1$ 个数 $p_2\;p_3\;\dots\;p_n$，表示对于 $2 \le i\le n$ 的整数 $i$，$i$ 和 $p_i$ 之间有一条无向边；

保证输入的数据构成一棵树；

之后 $m$ 行，每行两个数 $l\;\;r$，表示这次询问的区间是 $[l,r]$，保证 $l \le r$；

保证 $1 \le n\le 3\cdot 10^5,1 \le m\le 6\cdot 10^5$。

outputFormat: 共 $m$ 行，依次回答各组询问：每行输出一行一个整数表示这组询问的答案。

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

本题有多个子任务，每个子任务可能包含多个测试点，只有通过了一个子任务中的所有测试点才能得到该子任务的分数。

每个子任务的测试点满足一些特殊的限制，具体如下表：

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

其中，性质1、性质2的含义如下：

性质1：存在一个点 $w$ 使得 $dist(1,w)=n-1$；

性质2：$n=m$，且第 $i$ 次询问为 $l=1,\;r=i$。


title: [传智杯 #3 初赛] 课程报名

description:
传智播客推出了一款课程，并进行了一次促销活动。具体来说就是，课程的初始定价为 $v$ 元；每报名 $m$ 个学员，课程的定价就要提升 $a$ 元。由于课程能够容纳的学生有限，因此报名到 $n$ 人的时候就停止报名。

现在老师想知道，当课程停止报名时，一共可以获得多少学费呢？

inputFormat: 一行四个使用空格隔开的整数，分别为 $n,v,m,a$。

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

hint:
### 样例解释
每卖出 $1$ 个课程，价格就会提高 $1$ 元，所以总共获得 $1+2+3+4+5=15$ 元。

### 数据规模与约定
对于 $50\%$ 的数据，满足 $1 \leq n,m,v,a\leq 10$；

对于额外 $20\%$ 的数据，满足 $a=0$；

对于 $100\%$ 的数据，满足 $0 \leq n,m,v,a \leq 1000$。

然而，由于本次比赛是 ACM 赛制，因此您必须通过 $100\%$ 的数据才能够获得本题的得分，后题同。


title: [传智杯 #3 初赛] 期末考试成绩

description:
传智专修学院的 Java 程序设计课程的评价体系是这样的：

首先，所有学生会有一个卷面得分，这个得分一定是一个 $[0,100]$ 之间的整数。

如果卷面得分在 $90$ 分及以上，那么他的 GPA（加权平均成绩） 就是满分 $4.0$。

如果卷面得分在 $60 \sim 89$ 之间，那么他每比 $90$ 分少 $1$ 分，那么他的分数就会在 $4.0$ 的基础上减少 $0.1$。

如果卷面得分不到 $60$ 分，那么善良的老师会给他照顾。具体来说，如果他的分数为 $x$ ，那么老师会把他的分数调整为 $\sqrt{x}\times 10$（向下取整） ，再计算他的 GPA。

如果经过调整该学生的得分依旧没满 $60$ ，那么他就挂科了，GPA 就是 $0$ 分。

现在给你一个人的期末卷面得分，请你输出他的最终 GPA

inputFormat: 一行一个整数 $x$，表示该人的期末得分。

outputFormat:
一个小数点后只有一位的浮点数，表示该同学获得的GPA。

请注意，如果有 $.0$ 请保留。

hint:
对于 $20\%$ 的数据，满足 $90 \leq x \leq 100$；
对于额外 $30\%$ 的数据，满足 $60 \leq x \leq 100$；
对于 $100\%$ 的数据，满足 $0 \leq x \leq 100$。


title: [传智杯 #3 初赛] 志愿者

description:
传智专修学院总共召集了 $n$ 位志愿者来负责打扫活动，现在需要你负责帮忙统计每位志愿者的工作情况，用来制作光荣榜，给他们发小花花。

第 $i$ 位志愿者有一个工作时长 $t_i$ ，以及他负责的工作的难度系数 $k_i$ ，一名志愿者的贡献度可以用 $k_i \times t_i$ 确定。

现在要为这些志愿者的贡献度从大到小排个序，请你完成这个任务。相同贡献度的志愿者以工作时长较长的排在前面。如果贡献和时长一样，那么编号小的志愿者排在前面。

inputFormat:
一行一个整数 $n$ ，表示志愿者的数量。

接下来 $n$ 行，每行两个使用空格隔开的整数 $t_i,k_i$ ，表示第 $i$ 名志愿者的时间和难度系数。

outputFormat:
一行，共 $n$ 个整数，第 $i$ 个数表示排名为 $i$ 的志愿者的序号，从 $1$ 开始编号。

请注意本题时限为 5s，输入输出规模较大，请注意常数因素对耗时的影响，我们不会给使用 Java 和 Python 的选手增加额外的运行时间。

hint:
对于 $40\%$ 的数据，满足 $1 \leq n \leq 100$；
对于额外 $20\%$ 的数据，满足 $k_i=1$；
对于 $100\%$ 的数据，满足 $1 \leq n \leq 5 \times 10^5,1 \leq k_i,t_i \leq 1000$。

然而，由于本次比赛是 ACM 赛制，因此您必须通过 $100\%$ 的数据才能够获得本题的得分，后题同。


title: [传智杯 #3 初赛] 终端

description:
有一天您厌烦了电脑上又丑又没用的终端，打算自己实现一个 Terminal。

具体来说，它需要支持如下命令:

1. `touch filename`：如果名为 `filename` 的文件不存在，就创建一个这样的文件，如果已经存在同名文件的话则不进行任何操作。

2. `rm name`：删除名为 `name` 的文件。如果不存在这样的文件，就不进行任何操作。

3. `ls`：按**创建时间为顺序**，显示当前已经存在的未被删除的所有文件。
4. `rename xxx yyy`：将名为`xxx`的文件名字改为 `yyy` 。如果不存在这样的文件，或者已经存在文件名为 `yyy` 的文件，则不做任何操作。

这里所有涉及的文件名都仅由大写或者小写的英文字母构成，且文件名区分大小写。

inputFormat:
第一行一个整数 $n$ ，表示总共要执行的操作数。

接下来 $n$ 行，每行一个字符串，表示一条命令。

outputFormat:
对于每个 `ls` 命令，请输出若干行，每行一个字符串，表示一个文件，如果当前并没有任何文件，则什么都不输出。

请注意本题时限为 3s，输入输出规模较大，请注意常数因素对耗时的影响，我们不会给使用 Java 和 Python 的选手增加额外的运行时间。

samples:
6
touch yyh
touch yyhtql
rename yyh yyhnb
touch qwq
rename qwq qaq
ls

hint:
对于 $20\%$ 的数据，只存在 $1,3$ 操作

对于另外 $20\%$ 的数据，只存在 $1,2,3$ 操作

对于另外 $20\%$ 的数据，只存在 $1,3,4$ 操作

对于 $100\%$ 的数据，满足 $1 \leq n \leq 1000$

保证所有命令的长度不超过 $2000$ 个字符。


title: [传智杯 #3 初赛] 森林

background: YYH Land（Yoauld, Youthful & Happy Land）是位于炽蓝仙野的一片神奇的国度，那里的人们过着无拘无束的的快乐生活。

description:
清蒸鱼是一个尽职尽责的 YYH Land 护林者。他负责每天维护 YYH Land 的森林。在最开始的时候，YYH Land 只有一棵具有 $n$ 个节点的树，每个节点有一个灵力值 $v$。

由于 YYH Land 是一片神奇的国度，YYH Land 的树也有一些神奇的能力，具体来说它满足如下操作：

- `1 e`
编号为 $e$ 的边突然消失，使得它所在的那棵树变成了两棵树。

- `2 u val`
编号为 $u$ 的节点的灵力值变成了 $val$。

- `3 u`
清蒸鱼进行了一次查询，查询 $u$ 所在的那棵树的灵力值之和。

现在你需要帮助清蒸鱼，来模拟上述事件，以了解森林的变迁。

inputFormat:
第一行为 $n, m$，如上所述。
第二行有 $n$ 个数，为 $n$ 个结点的初始权值，在 $10^3$ 以内。
下面 $n-1$ 行，每行一组 $u, v$，表示一条边。（保证初始为一棵树）
下面 $m$ 行有 $m$ 个操作：
先读入一个$opt$，表示操作类型。
$opt=1$ 时，读入 $e$，表示删掉读入的第 $e$ 条边。（保证第 $e$ 条边存在）
$opt=2$ 时，读入 $u,val$，表示把结点 $u$ 的权值改成 $val$（$val \le 1000$）。
$opt=3$ 时，读入 $u$，表示查询 $u$ 所在的那棵树的结点权值和。

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

hint:
对于 $30\%$ 的数据，满足 $1 \leq n,m \leq 10$；
对于 $50\%$ 的数据，满足 $1 \leq n,m \leq 1000$；
对于另外 $20\%$ 的数据，满足只有 $2,3$ 操作；
对于 $100\%$ 的数据，满足 $1 \leq n,m \leq {10}^5$，$1 \leq v,val \leq 1000$。


title: [传智杯 #3 初赛] 游戏（征集数据）

description:
清蒸鱼是一个从未被击败的炽蓝仙野游戏者。有一天他遇到了这么一个游戏：

给定一个长度为 $n$ 的数组 $a$。同时定义 $count(x)$ 为 $x$ 在二进制下的 $1$ 的个数。

现在清蒸鱼每次可以进行如下两种操作：

- 选择两个数 $a_i, a_j$，并且必须满足 $count(a_i \operatorname{xor} a_j)=1$，将它们中的任意一个从数组中消去，代价为 $C_1$。

- 选择两个数 $a_i, a_j$，并且必须满足 $count(a_i \operatorname{xor} a_j) > 1$，将它们中的任意一个从数组中消去，代价为 $C_2$。

现在你想知道，最少付出多少的代价，能让这个数组被消到只剩一个数。

inputFormat:
第一行一个整数 $n$，表示数组大小。
第二行两个整数 $C_1, C_2$，意义如题所示。
第三行共 $n$ 个整数，描述了数组 $a$。

outputFormat: 一行一个整数，表示最小代价。

hint:
对于 $20\%$ 的数据，满足 $n = 10$；
对于另外 $20\%$ 的数据，满足 $a$ 中的元素为一个 $[1, n]$ 的排列；
对于 $100\%$ 的数据，满足 $1 \leq n \leq {10}^4$，$1\le C_1, C_2, a \le {10}^9$，$a$ 中的元素互不相同。


title: [传智杯 #3 初赛] 运气

background: YYH Land(Yoauld,Youthful & Happy Land) 是位于炽蓝仙野的一片神奇的国度，那里的人们过着无拘无束的的快乐生活。

description:
哈兰·斯威提是 YYH Land 远近闻名的注铅骰子爱好者。有一天他碰到了这么一个问题：

你有一枚 $6$ 个面的骰子，分别写了 $1,2,3,4,5,6$ ，每一面朝上的概率是均等的。

现在哈兰想知道，如果他投掷 $n$ 次，并且将结果按顺序写在纸上成为一个数。（比如说如果哈兰扔了 $3$ 次，分别是 $3,2,5$ ，那么他最后得到的数就是 $325$）他现在想知道这个数是 $k$ 的倍数的可能情况有多少种，其中 $k$ 是一个特定的数。

由于这个方案数可能会很大，所以请你输出结果对 $10^9+7$ 取模的结果。

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

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


title: 纯洁憧憬

background:
少年对他的憧憬，简直连续不断。
少年的思绪，如同许多数字的排列一般凌乱。

description:
对于一个 $n$ 阶排列 $p_1,\dots,p_n$ 和一个区间 $[l,r]$，若 $\max\limits_{l\le i\le r} p_i - \min\limits_{l\le i\le r} p_i = r - l$，则称 $[l,r]$ 为一个**连续段**。

对于一个连续段 $[l,r]$，若其满足 $2 \le r - l + 1 < n$，则称 $[l,r]$ 为一个**非平凡连续段**。

**少年的思绪**可以抽象成一个**至少存在一个**长度大于 $k$ 的非平凡连续段的排列。

少年会给定 $n,k$，并询问你有多少 $n$ 阶排列可能是少年的思绪。答案对 $10^9 + 7$ 取模。

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

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


title: 「HMOI R1」概率

background: “傻子才相信概率。”

description:
fz 退役之后正在学文化课。

fz 见到一个题，这个题是这样的：

给定区间 $[a, b]$ 和 $[c, d]$，求从其中各等概率选择一个整数，和等于 $e$ 的概率。

fz 本来想把 “等于 $e$” 改成 “$\in [e,f]$”，但是这样他就会变成辣鸡分类讨论出题人，所以他决定不改。

为了方便，你只需输出答案乘 $(b-a+1)(d-c+1)$ 的结果。可以证明这个数是一个整数。

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

接下来 $T$ 行，每行五个整数 $a, b, c, d, e$。

outputFormat: 共 $T$ 行，每组数据一行一个自然数，表示对应的答案。


title: [THUPC2021 初赛] 方格游戏

description:
小 F 和小 H 在玩游戏。今天，他们在一个 $N\times M$ 的棋盘上玩游戏。小 H 想考考小 F 的数学能力，但小 F 天生数学就不好，所以想请你帮忙。为了加大难度，小 $H$ 会在棋盘里面加入 $P$ 个矩形障碍物。每个矩形障碍物用 $U$、$D$、$L$、$R$ 来表示，即在第 $U$ 行到第 $D$ 行以及在第 $L$ 列到第 $R$ 列之间的所有格子都变成了障碍物。小 H 保证所有矩形障碍物互不相交，并且所有非障碍物格子之间都能够直接或者间接互达，若两个非障碍物格子有公共边，那么它们直接互达并且它们的距离为 $1$。

现在每一局游戏中，小 F 在棋盘中挑选一个非障碍物格子 $X$，小 H 也挑另外一个非障碍物格子 $Y$，这一局游戏 $(X,Y)$ 的得分就是 $X$ 到 $Y$ 的最短路径。小 F 需要计算出所有可能的游戏中的得分和，答案模 $1,000,000,007$。注意两局游戏中只要挑选的两个格子相同则视为同一局游戏，即 $(X, Y)$ 等同于 $(Y,X)$。

inputFormat:
第一行三个整数 $N$（$1 \le N \le 1,000,000,000$），$M$（$1 \le M \le 1,000,000,000$），$P$（$0 \le P \le 100,000$）。
接下来有 $P$ 行，每行四个正整数，$U_i, D_i$（$1 < U_i \le D_i < N$），$L_i, R_i$（$1 < L_i \le R_i < M$），表示第 $i$ 个矩形障碍物。对于任意两个不同的矩形障碍物 $i$ 和 $j$，都满足 $D_i + 1 < U_j$ 或者 $D_j + 1 < U_i$，以及 $R_i + 1 < L_j$ 或者 $R_j + 1 < L_i$。

outputFormat: 只有一行一个正整数，即所有游戏的得分和模 $1,000,000,007$。

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

距离为 $1$ 的有 $8$ 种。
距离为 $2$ 的有 $8$ 种。
距离为 $3$ 的有 $8$ 种。
距离为 $4$ 的有 $4$ 种。
总共得分为 $64$。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2021-pre> 查看。


title: [THUPC2021 初赛] 切切糕

description:
Kiana 喜欢吃甜点，某天她从商店中买回来 $N$ 块切糕与 Tinytree 共同分享，其中第 $i$ 块切糕的大小用一个数 $A_i$ 来表示。

因为每块切糕的风味都不同，所以 Kiana 和 Tinytree 决定将每块切糕都切成两份，两人各选一份品尝。但切切糕是一个自古以来的大难题，经过商议，Kiana 打算执刀来切切糕，而 Tinytree 有 $M$ 次“优先选糕权”，可以获得一些切糕切开后的优先选择权，具体来说，两人按照如下流程进行操作：

步骤一：Kiana 从还没切的切糕中按自己的想法选一块出来，并将其切成两份，其中**每份切糕的大小可以是任意正实数，也可以是 $\mathbf{0}$，且两份切糕的大小之和与切之前的大小相同**。

步骤二：Tinytree 观察完 Kiana 切出的两份切糕大小后，如果还有“优先选糕权”次数剩余，则可以决定是否消耗 $1$ 次“优先选糕权”来进行优先选择。

步骤三：如果 Tinytree 选择使用“优先选糕权”，则她可以从两份切糕中任选一份，另一份则归 Kiana，如果 Tinytree 选择不使用或者已经用完了 $M$ 次“优先选糕权”，则 Kiana 从两份切糕中任选一份，另一份则归 Tinytree，然后两人回到步骤一，直到所有的切糕都切完。

假设 Kiana 和 Tinytree 都足够聪明，在自己可以操作时总是想办法**让自己最终获得的切糕总大小尽可能大**，且开始切第一块切糕之前 $N$ 块切糕的大小是两人都已知的，“优先选糕权”不要求全部用完。现在 Kiana 想知道，自己能获得的切糕总大小是多少，由于 Kiana 自己不会算，所以希望你能够帮助她。

inputFormat:
第一行包含两个正整数 $N$ 和 $M$（$1 \le M \le N \le 2500$），分别表示切糕的总数和 Tinytree 初始时“优先选糕权”的次数。
第二行包含 $N$ 个正整数，其中第 $i$ 个数 $A_i$（$1 \le A_i \le 50000$）表示第 $i$ 块切糕的大小。

outputFormat: 输出共一行，包含一个实数，表示**Kiana 最终能获得的切糕总大小**，所有输出精确到小数点后六位。

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

在这个样例中总共有 $4$ 块切糕，大小分别为 $4,3,2,1$，Tinytree 的“优先选糕权”一共有三次，两人可以按照如下顺序和方式来分配切糕：

第一块：Kiana 选择大小为 $3$ 的切糕，将其切成大小为 $1.25$ 和 $1.75$ 的两部分，Tinytree 使用一次“优先选糕权”选走 $1.75$ 的部分，Kiana 目前总共获得大小 $1.25$ 的切糕。

第二块：Kiana 选择大小为 $1$ 的切糕，将其切成大小为 $0$ 和 $1$ 的两部分，Tinytree 不使用“优先选糕权”，Kiana 独得此糕，目前总共获得大小 $2.25$ 的切糕。

第三块：Kiana 选择大小为 $2$ 的切糕，将其切成大小为 $1$ 和 $1$ 的两部分，Tinytree 使用一次“优先选糕权”选走 $1$ 的部分，Kiana 目前总共获得大小 $3.25$ 的切糕。

第四块：Kiana 选择大小为 $4$ 的切糕，将其切成大小为 $2$ 和 $2$ 的两部分，Tinytree 使用一次“优先选糕权”选走 $2$ 的部分，Kiana 目前总共获得大小 $5.25$ 的切糕。

综上所述，该样例输出 $5.250000$，且可以证明在这个方案中如果任意一人改变自己的策略，其获得的切糕总大小不可能变得更大。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2021-pre> 查看。


title: [THUPC2021 初赛] 非欧几何

description:
ustze 喜欢几何，他认为几何是数学竞赛中最简单的一环，在征服了数学以后，ustze 决定将自己的天赋带到计算几何中，并与传统的欧氏几何展开较量。

作为欧氏几何的捍卫者，Tinytree 在三维空间中建立了一个**球心在原点、半径为** $\boldsymbol R$ **的球面**，其中坐标为 $(0,0,R)$ 的点称为北极点，显然北极点处于球面上。Tinytree 回忆在欧氏几何中，三点可以唯一确定空间中的一个圆，因此 Tinytree 在球面上确定了 $N$ 个点对，其中每个点对和北极点一起就确定了一个球面上的圆，我们保证这些圆的**半径严格小于** $\boldsymbol R$，因此每个圆会将球面分成面积不相等的两部分，我们**称球面上面积较小的部分是该圆的内部，面积较大的部分是该圆的外部**，而这 $N$ 个圆的内部受到 Tinytree 的保护，**它们的并构成安全区域**。

作为非欧几何的狂热者，ustze 认为球面上的圆其实是“直线”，他在球面上确定了 $M$ 个点对，其中每个点对和北极点一起也确定了一个球面上的圆，这些圆的**半径也是严格小于** $\boldsymbol R$ 的，这 $M$ 个圆的内部受到 ustze 的威慑，**它们的并构成危险区域**。

正当 Tinytree 和 ustze 对峙时，球面上一般路过一个 Kiana，她见到这幅景象十分害怕，开始在球面上东躲西藏。现在 Kiana 初步确定了 $T$ 个球面上的点，她想知道这些点是否在安全区域或危险区域中，以便自己跑路，由于 Kiana 自己不会算，所以希望你能够帮助她。

inputFormat:
第一行包含三个正整数 $N, M$ 和 $T$（$1 \le N, M \le 5000$，$1 \le T \le 1.5 \times {10}^5$），分别表示 Tinytree 确定的点对数、ustze 确定的点对数和 Kiana 确定的跑路点数。

第二行包含一个正整数 $R$（$1 \le R \le {10}^3$），表示球面的半径大小。

接下来 $N$ 行，第 $i$ 行依次输入 $A_i, B_i, X_i, C_i, D_i, Y_i$（$1 \le |A_i|, |B_i|, |C_i|, |D_i| \le R$，$1 \le A_i^2 + B_i^2, C_i^2 + D_i^2 \le R^2$），其中 $A_i, B_i$ 表示 Tinytree 确定的第 $i$ 个点对中第一个点的横坐标和纵坐标，而 $X_i$ 为 `+` 表示第一个点的竖坐标大于 $0$，为 `-` 表示第一个点的竖坐标小于 $0$，如果竖坐标等于 $0$ 则 $X_i$ 是在 `+` 和 `-` 中随机选择的，$C_i, D_i$ 表示 Tinytree 确定的第 $i$ 个点对中第二个点的横坐标和纵坐标，$Y_i$ 表示竖坐标的正负，含义与 $X_i$ 相同。

接下来 $M$ 行，第 $j$ 行依次输入 $A_j, B_j, X_j, C_j, D_j, Y_j$（$1 \le |A_j|, |B_j|, |C_j|, |D_j| \le R$，$1 \le A_j^2 + B_j^2, C_j^2 + D_j^2 \le R^2$），表示 ustze 确定的第 $j$ 个点对坐标，点的表示方式与之前相同。

接下来 $T$ 行，第 $k$ 行包含两个实数 $A_k, B_k$（$1 \le |A_k|, |B_k| \le R$，$1 \le A_k^2 + B_k^2 \le R^2$）和一个字符 $X_k$，表示 Kiana 确定的第 $k$ 个跑路点，点的表示方式与之前相同。

数据保证合法，且输入中没有两个点是相同的，所有实数保留到小数点后三位，**Kiana 的跑路点和任意一个给定圆周的最小直线距离不小于** $\boldsymbol{{10}^{-6}}$。

outputFormat: 输出共 $T$ 行，每行包含一个字符串，若 Kiana 的第 $k$ 个跑路点在安全区域中则在第 $k$ 行输出 `Safe`，如果不在安全区域中但也不在危险区域中则在第 $k$ 行输出 `Passer`，如果不在安全区域中且在危险区域中则在第 $k$ 行输出 `Goodbye`（所有输出不含引号）。

hint:
在三维空间中，我们可以用一个有序的实数三元组 $(x, y, z)$ 来描述一个点的位置，其中 $x, y, z$ 分别称作这个点的横坐标、纵坐标和竖坐标。

三维空间中一个球心在 $(x_0, y_0, z_0)$、半径为 $R$ 的球面是指空间中所有满足 $(x - x_0)^2 + (y - y_0)^2 + (z - z_0)^2 = R^2$ 的点 $(x, y, z)$ 构成的点集，对于该球面上给定的两个不同点 $(x_1, y_1, z_1), (x_2, y_2, z_2)$，如果它们不是一对对踵点（两个点是对踵点当且仅当它们之间的距离为 $2 R$），则它们和球心不在同一直线上，这三个点唯一确定了一个平面，这个平面与球面的交线被这两个点分成了两个部分，其中较短部分的长度称为这两点在该球面上的距离，如果这两个点是对踵点，则定义它们之间的距离为 $\pi R$，球面上的一个圆指到球面上某点的球面距离等于一个常数的球面上的点的集合，可以证明球面上的任意三个不同点唯一确定了一个球面上的圆。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2021-pre> 查看。


title: [THUPC2021 初赛] 区间矩阵乘法

description:
给定长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$；共 $m$ 组询问，每次询问给出 $d,p_1,p_2$，求

$$ \sum_{i=0}^{d-1} \sum_{j=0}^{d-1} \sum_{k=0}^{d-1} a_{p_1+d\cdot i+j} a_{p_2 + d\cdot j + k} $$

inputFormat:
输入的第一行包含一个数 $n$。
之后一行 $n$ 个数，表示 $a$ 这个序列。
之后一行一个数 $m$。
之后 $m$ 行，每行三个数 $d, p_1, p_2$ 表示一次询问。

$1 \le n, m, a_i \le 2 \times {10}^5$，所有数值为 $[1,{10}^9]$ 以内的整数，询问保证 $a$ 的下标在 $[1,n]$ 内。

outputFormat: 输出共 $m$ 行，表示每个询问对应的答案，答案对 $2^{32}$ 取模。

hint:
**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2021-pre> 查看。


title: [THUPC2021 初赛] 棋盘

description:
有一个 $n$ 行 $m$ 列的棋盘，共有 $n m$ 个格子。请你在格子内放入棋子（每个格子可以放入至多一个棋子），使得对于所有 $1 \le i \le m$，第 $i$ 列里恰好包含 $a_i$ 个棋子。另外，棋盘上的任意两颗棋子都不能边相邻。

请判断是否存在一种合法方案。如果存在，请输出任意一个合法方案。

inputFormat:
输入的第一行包含两个正整数 $n, m$，保证 $n \le 300, m \le 300$。
输入的第二行包含 $m$ 个非负整数 $a_1, a_2, \ldots , a_m$，保证 $0 \le a_i \le n$。

outputFormat:
如果无解，输出一个字符串 `No`。
如果有解，第一行输出一个字符串 `Yes`，接下来 $n$ 行每行输出一个长度为 $m$ 的字符串，表示你构造的棋盘方案。其中 `0` 表示空格，`1` 表示放入棋子的格子。


title: [THUPC2021 初赛] 密集子图

description:
有一天，魔法师小 L 看到了一个有向完全图。

图中所有边的长度都是 $1$，且所有边都是白色的。

现在小 L 要对这个图施展魔法，图中每条有向边分别都有一定概率变成黑色。

小 L 认为一个图是“密集的”，当且仅当只经过黑色边时，点 $1$ 到其余所有点的最短路径长度都不超过 $k$（特别地，若两个点不连通则它们之间最短路径的长度视为 $+ \infty$）。

小 L 想要知道，此时这个有向完全图有多大的概率是“密集的”呢？请你输出此概率对 $998,244,353$ 取模的结果。

inputFormat:
第一行两个正整数 $n$（$2 \le n \le 12)$，$k$（$1 \le k \le n - 1$）。
接下来 $n \times (n - 1)$ 行，每行 $4$ 个正整数 $x, y, p, q$，表示点 $x$ 到点 $y$ 的有向边变成黑色的概率为 $\frac{p}{q}$。保证 $1 \le x \le n$，$1 \le y \le n$，$x \ne y$，$0 \le p \le q < 998,244,353$，$q > 0$，每组合法的 $(x, y)$ 恰好出现一次。

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

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

这个有向完全图是“密集的”，当且仅当点 $1$ 到点 $2$ 的有向边和点 $1$ 到点 $3$ 的有向边同时变成黑色，这种情况出现的概率 $= \frac{1}{2} \times \frac{1}{3} = \frac{1}{6}$，$\frac{1}{6} \bmod 998,244,353 = 6^{998,244,351} \bmod 998,244,353 = 166,374,059$。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2021-pre> 查看。


title: [THUPC2021 初赛] 线段树

description:
线段树是小 L 最喜欢的数据结构，它能高效地解决许多实际问题。

给定一个正整数 $n$，小 L 构建出一棵下标属于整数区间 $[1, n]$ 的线段树：

- 初始线段树只有一个结点 $[1, n]$。
- 对于结点 $[L, R]$，若 $L < R$，则令 $mid = \left[ \frac{L + R}{2} \right]$（$[x]$ 表示不超过 $x$ 的最大整数），小 L 对这个结点建出两个子结点 $[L, mid]$、$[mid + 1, R]$。

小 L 定义了一个函数 $cover(a, b)$（$1 \le a \le b \le n$），表示用若干个线段树结点不重不漏地覆盖区间 $[a, b]$，则使用的线段树结点个数的最小值。

小 L 尝试使用这棵线段树解决某个复杂问题，并想要粗略地评估这棵线段树的性能。

具体来说，区间 $[1, n]$ 有 $\frac{n (n + 1)}{2}$ 个不同的子区间，如果小 L 从这 $\frac{n (n + 1)}{2}$ 个子区间中等概率随机地选取一个，将其记为 $[A, B]$，则小 L 认为 $cover(A, B)$ 的期望值可用于评估此线段树的性能。

小 L 想请你帮他计算出 $cover(A, B)$ 的期望值与 $\frac{n (n + 1)}{2}$ 的乘积对 $1, 000, 000, 007$ 取模的结果，可以发现此结果一定是一个整数。

inputFormat:
第一行一个正整数 $T$（$1 \le T \le 1000$）表示数据组数。
接下来 $T$ 行，其中第 $i$（$1 \le i \le T$）行一个正整数 $n$（$1 \le n \le {10}^{18}$）表示第 $i$ 组数据。

outputFormat: $T$ 行，第 $i$（$1 \le i \le T$）行一个整数表示第 i 组数据的答案。

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

$cover(1, 1) = 1$，$cover(2, 2) = 1$，$cover(3, 3) = 1$，$cover(1, 2) = 1$，$cover(2, 3) = 2$，$cover(1, 3) = 1$，故 $cover(A, B)$ 的期望 $= \frac{1 + 1 + 1 + 1 + 2 + 1}{6} = \frac{7}{6}$。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2021-pre> 查看。


title: [THUPC2021 初赛] 狗蛋和二五仔

background:
**那女孩对我说**
**代价为十辆铲车**

description:
小 E 喜欢和老师变换着花样玩牌。最近，他们又发明了一种叫做“狗蛋和二五仔”的玩法。

规则是这样的：

游戏开始时小 E 和老师各有 $30$ 点体力值，手上各有 $2$ 张牌。所有的牌是完全相同的。每个玩家的面前都可以放置牌，开始时双方面前没有任何牌。

双方轮流进行操作。玩家在每个自己的回合开始时先抽一张牌。“抽一张牌”的操作指的是，如果手上的牌的数量小于 $3$ 张，则再抓一张牌放在手上；如果手上恰好有 $3$ 张牌，则不能再抓牌。操作分为 $4$ 种类型。

- 技能。让自己的体力值 $- 2$，然后抽一张牌。
- 攻击。具体地，玩家可以选择一张放在自己面前的**本回合还未攻击过**的牌，选择对方面前的一张牌同归于尽，或者选择一张放在自己面前的**本回合还未攻击过**的牌，让对方的体力值 $- 3$。如果是后者，则将这张选择的牌标记为已攻击。
- 打牌。如果你面前的牌的数量小于 $4$ 张，且手上有牌才能进行此操作。先进行下面的过程 $3$ 次：
  - 随机选择一个角色，让它的体力值 $- 1$。这个角色可以是自己、对方或者某一方面前的一张牌。如果双方场上的牌一共有 $k$ 张，那么选择到任何一个角色的概率为 $\frac{1}{k + 2}$。如果该角色是一张牌且体力值变为了 $0$，那么将它摧毁；如果该角色是一个玩家且体力值变为了 $0$，那么该玩家直接输掉游戏。

  在进行完 $3$ 次后将手上的一张牌放在自己面前。牌的体力值为 $2$。这张牌在本回合中被认为已攻击过。
- 结束回合，接下来轮到对方的回合。

一回合中，玩家可以进行多次操作，但是技能和打牌的操作次数**之和**不能超过 $O$。除了结束回合，这些操作没有顺序限制，比如你可以先打一张牌，然后使用技能，然后再打一张牌。在结束回合之前，玩家需要进行至少一次任意的操作才能结束回合。

在任何时刻如果有玩家的体力值小于或等于 $0$，那么该玩家输掉游戏。

游戏进行了几个回合后，现在轮到了小 E 的回合开始前。小 E 想让你帮他分析，如果双方都采用最优策略，那么现在自己赢的概率是多少。

inputFormat:
第一行一个正整数 $T, O$，分别表示数据组数和每回合中技能和打牌的操作次数上限。
对于每组数据，第一行两个正整数 $E, S$，分别表示小 E 和老师现在的体力值。保证 $1 \le E, S \le 20$。
第二行一个非负整数 $c$，然后跟着 $c$ 个正整数 $a_1, \ldots , a_c$，表示老师面前有 $c$ 张牌，它们的体力值分别为 $a_1, \ldots , a_c$。保证 $0 \le c \le 4$，$1 \le a_i \le 2$。
第三行一个非负整数 $p$，然后跟着 $p$ 个正整数 $e_1, \ldots , e_p$，表示小 E 面前有 $p$ 张牌，
它们的体力值分别为 $e_1, \ldots , e_p$。保证 $0 \le p \le 4$，$1 \le e_i \le 2$。
第四行两个 $[0, 3]$ 之间的非负整数，分别表示老师和小 E 的手牌数。
在你到来之前老师可能作了弊，你不需要判断输入的情况是否真的是游戏进行了几个回合后的情况。

outputFormat: 对于每组数据输出一行一个实数，表示小 E 在双方采用最优决策时获胜的概率。你的输出的和标准答案的绝对误差不超过 ${10}^{-6}$ 时算作正确。

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

回合开始，小 E 抽一张牌。此时小 E 手上有 $2$ 张牌，老师手上没有牌，双方的面前都没有牌。双方的体力值均为 $1$。这时，最优策略下，小 E 不能使用技能，因为使用后会因为自己的体力值小于等于 $0$ 而输掉游戏；小 E 不能攻击，因为自己面前没有牌；小 E 也不能结束回合，因为本回合他还没有进行任何操作。所以小 E 的最优策略是打一张牌，这时会随机选到小 E 或者老师中的一个角色，让他体力值 $- 1$ 然后输掉游戏。所以小 E 的获胜概率为 $0.5$。

**【子任务】**

保证 $1\le T\le 351493,3\le O \le 5$ 。

**【后记】**

最后小 E 还是战胜了老师。

**“老师你术士玩多了就知道怎么玩了，你打得还不够多。”**

**“吹牛现在都流行这么吹的吗？兄弟你知道我术士多少胜场嘛，啊？我跟你说全世界没有一个人术士比我胜场多的。”**

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2021-pre> 查看。


title: [THUPC2021 初赛] 合法序列

description:
对于一个长度为 $n$ 的 $\text{0-1}$ 序列 $s$，我们将它的位从左到右、从零开始编号，记为 $s_0, s_1, \ldots , s_{n-1}$。

给定一个正整数 $k$，从 $s$ 中取出某个长度为 $k$ 的子段。将这个子段解释为一个左侧为高位、右侧为低位的 $k$ 位二进制数，记为 $t$，则有 $0 \le t < 2^k$。

$s$ 有 $n - k + 1$ 个长度为 $k$ 的子段，如果对于其中的每一个子段，如上解释为二进制数 $t$ 后，$s$ 的编号为 $t$ 的位（即 $s_t$）都是 $1$，则说 $s$ 是合法的。保证 $2^k \le n$，即 $t$ 作为 $s$ 的下标不会越界。

给定 $n, k$，求合法的 $s$ 的数量。由于方案数可能较大，只需给出方案数模 $998, 244, 353$ 的结果作为答案。

inputFormat:
输入有一行，包含两个用空格隔开的正整数 $n, k$。

保证 $1 \le k \le 4$，$2^k \le n \le 500$。

outputFormat: 输出一行，包含一个非负整数，即合法方案数模 $998, 244, 353$ 的结果。

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

有两个满足要求的序列：$0, 1, 1, 1$ 和 $1, 1, 1, 1$。

**【题目来源】**

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2021-pre> 查看。


title: [THUPC2021 初赛] 独立

background: feecle6418 备注：可以认为本题的数据是随机生成的。

description:
给定一张 $n$ 个点 $m$ 条边的无向图。

对于 $\{1, 2, \ldots , n\}$ 的某个子集 $A$，$A$ 的分数为：

1. 初始分数为 $0$；
2. 对于所有 $i \in A$，分数加 $a_i$；
3. 对于所有边 $(u, v, k)$（代表从 $u$ 到 $v$ 值为 $k$ 的边）满足 $u \in A$ 并且 $v \in A$，分数减 $k$；

现在请你计算出所有的 $A$ 中，分数最高是多少。

inputFormat:
令 $q = 101$，$b = 137$，$p = 1, 000, 000, 007$。

第一行包含六个整数 $n, m, x_0, y_0, a_0, z_0$（$1 \le n \le 100000$，$0 \le m \le \frac n2$，$0 \le x_0, y_0, a_0, z_0 < P$）。

对于 $1 \le i \le n$，有 $a_i = (q \times a_{i - 1} + b) \bmod p$。

对于 $1 \le i \le m$, 有 $x_i = (q \times x_{i − 1} + b) \bmod p$，$y_i = (q \times y_{i − 1} + b) \bmod p$，$z_i = (q \times z_{i − 1} + b) \bmod p$。对于每一组 $(x_i, y_i, z_i)$ 描述了一条连接 $(x_i \bmod n) + 1, (y_i \bmod n) + 1$ 的值为 $z_i$ 的边，如果 $x_i = y_i$ 或者之前出现过连接 $x_i$ 和 $y_i$ 的边，则忽视这条边（即这条边不存在）。

outputFormat: 输出一行一个整数表示最高分数。


title: [THUPC2021 初赛] 麻将模拟器

description:
麻将是一种休闲的四人博弈游戏。你的任务是写一个模拟器来模拟一局游戏的进程。

接下来将详细介绍游戏规则和每个玩家的决策。注意：为了实现方便和使游戏更加有趣味，这里介绍的规则和主流的几种麻将规则均略有不同。

**基础规则：**

- 一副麻将由 $148$ 张牌组成，其中包含 $37$ 种不同的牌，每种各 $4$ 张。
- 这 $37$ 种牌分别是：一万到九万（`1M ~ 9M`）、一筒到九筒（`1P ~ 9P`）、一索到九索（`1S ~ 9S`）、东（`E`）、南（`S`）、西（`W`）、北（`N`）、白（`B`）、发（`F`）、中（`Z`），以及 $3$ 种特殊牌：跳过（`PASS`），反向（`REVERSE`），双重回合（`DOUBLE`）。
- 游戏共有 $4$ 名玩家，不妨称其为 `A`，`B`，`C`，`D`。
- 游戏开始前，将 $148$ 张牌随机洗乱后摆成一排，称为牌堆。此后玩家摸牌一定是从牌堆中摸取最靠前的一张牌。
- 从 `A` 开始按照 `ABCDABCD...` 的顺序，每人依次从牌堆中摸一张牌，直到每人都有 $13$ 张牌，这些牌组成每个玩家的手牌。
- 再从 `A` 开始按照 `ABCDABCD...` 的顺序，依次进入每人的回合：
- 在一个回合中，玩家先摸一张牌进入自己的手牌，再从自己的手牌中打出一张牌。
- 依次进行直到有人和牌或者无牌可摸时游戏结束。

**特殊牌：**

- 跳过（`PASS`）：在出牌时打出这张牌，可以指定一名玩家，跳过他的下一个回合。
- 反向（`REVERSE`）：在出牌时打出这张牌，反转进行回合的顺序，即由 `ABCDABCD...` 变为 `ADCBADCB...` 或由 `ADCBADCB...` 变为 `ABCDABCD...`。出牌后即按照反转后的顺序，从出牌者原先的上家开始进行回合。
- 双重回合（`DOUBLE`）：在出牌时打出这张牌，该名玩家立即进入一个额外的回合。

**牌型：**有如下 $3$ 种牌型：

- 顺子：$3$ 张数字连续的万，或 $3$ 张数字连续的筒，或 $3$ 张数字连续的索，如 `4P 5P 6P`。
- 刻子：$3$ 张完全一样的非特殊牌，如 `B B B`。
- 对子：$2$ 张完全一样的非特殊牌，如 `9M 9M`。

**吃、碰：**

- 当一名玩家打出一张非特殊牌时，其他玩家可以进行吃或碰：
- 吃（`CHOW`）：当打出的这张牌跟自己的手牌中的某两张牌能组成一个顺子时，可以将手牌中能与之组成顺子的其余两张牌取出，与这张牌一起摆在旁边。
- **注意只有上一名出牌玩家的下家（按当前顺序原本应在下一个进行回合的玩家）才能吃。**
- 碰（`PONG`）：当打出的这张牌跟自己的手牌中的某两张牌能组成一个刻子时，可以将手牌中能与之组成刻子的其余两张牌取出，与这张牌一起摆在旁边。
- 碰没有吃的上述限制，任意其他玩家都能碰。
- 如果既有玩家能吃又有玩家能碰，则碰优先于吃。
- 吃（或碰）不是强制性的，也就是说玩家满足吃（或碰）的条件时，可以选择不吃（或碰）。
- 吃和碰统称为副露。为方便起见，不将副露视为手牌的一部分。
- 在任意一名玩家吃（或碰）后，跳过从上一名出牌的玩家到这名玩家之间的所有玩家的回合，直接从当前玩家开始进行新的回合。但该玩家在这一回合中**跳过摸牌直接出牌**，在下一回合（如果没有吃碰的话）恢复正常。
- **注意在本规则中不能杠。**

**胡牌规则：**

- 称一名玩家的牌能和，当且仅当满足如下条件：
  - 牌数为 $14 - 3 n$，其中 $n$ 为该玩家副露（即吃碰）的个数；
  - 这些牌中无特殊牌；
  -  这些牌能够被分成 $(5 - n)$ 组，其中 $(4 - n)$ 组均为 $3$ 张且均为顺子或刻子，其余一组为 $2$ 张且为对子。
- **注意本规则中不支持七对子、十三幺、全不靠等特殊的和牌规则。**
- 另外，定义一组包含 $13 - 3 n$ 张牌的手牌的和牌距离为最小的 $x$，使得向这些牌中加入特定的 $x$ 张牌，再去掉 $x - 1$ 张手牌后，每种牌仍不超过 $4$ 张且能和。
- 定义一组包含 $14 - 3 n$ 张牌的手牌的和牌距离为最小的 $x$，使得向这些牌中加入特定的 $x$ 张牌，再去掉 $x$ 张手牌后，每种牌仍不超过 $4$ 张且能和。
- 特别地，一手能和的牌的和牌距离为 $0$；和牌距离为 $1$ 的牌称为听牌。
- 注意这里的“**每种牌仍不超过** $\boldsymbol{4}$ **张**”的限制：如果一手牌是 `1M 1M 1M 1M` 且副露数为 $3$，再向其中加入一张 `1M` 就能和，但是由于有 $5$ 张 `1M` 所以是不被允许的，故不认为其和牌距离为 $1$。
- 但如果一手牌是 `1M` 且副露数为 $4$，但是曾进行过一次 `1M 1M 1M` 的碰，仍然认为其和牌距离为 $1$（虽然缺的这张 `1M` 永远也等不到）。

**终局：**

- 荣和（`RON`）：当一名玩家出牌后，某名其他玩家的手牌加上这张牌能和，则称这名玩家荣和。荣和优先于吃碰。
- 如果有多名玩家同时达到荣和的标准，规定只有从上一名出牌玩家开始，沿回合进行顺序的第一名能荣和的玩家才能荣和，其余玩家荣和不了，称这种情况为截和。
- 自摸（`SELFDRAWN`）：一名玩家摸牌后其手牌能和，称这名玩家自摸。
- 一旦有一名玩家荣和或自摸，游戏立即结束，该名玩家胜利。
- 如果某名玩家摸牌时发现牌堆中已经无牌可摸，游戏立即结束，称此种情况为流局。

**出牌策略：**每名玩家的出牌策略相同且固定：

- 出牌时，若手里有特殊牌一定会优先出，且如果有多种特殊牌，按照 `PASS`、`REVERSE`、`DOUBLE` 的优先顺序；出的 `PASS` 一定指定下家。
- 出牌时若手里没有特殊牌，则会对于每一种可能的出牌方法计算出完牌后的和牌距离，选择和牌距离最小的一种方案。如果有并列最小，按照 `Z`，`F`，`B`，`N`，`W`，`S`，`E`，`9S`，`8S`，……，`1S`，`9P`，……，`1P`，`9M`，……，`1M` 的优先顺序出牌。
- 同一个人能吃且能碰时，优先考虑碰；因为每种牌只有 $4$ 张所以不会有两名玩家同时可以碰的情况；当且仅当吃（或碰）后能使得和牌距离严格减小才会去吃（或碰）；如果有多种吃的方案使得和牌距离严格减小，优先选择数字较大的方案。
-  能荣和一定荣和（除非被截和），能自摸一定自摸，不会拒和（能和时故意选择不和）。

inputFormat:
输入共 $148$ 行，按照牌堆从前到后的顺序输入每一张牌。
每行输入一个字符串表示这一张牌。
用 `1M`，`2M`，……，`9M` 代表万，`1P`，`2P`，……，`9P` 代表筒，`1S`，`2S`，……，`9S` 代表索，`E`，`S`，`W`，`N`，`B`，`F`，`Z` 分别代表东、南、西、北、白、发、中，`PASS` 代表跳过，`REVERSE` 表示反向，`DOUBLE` 表示双重回合。

outputFormat:
按照如下几条规则进行输出：

- 当任意一名玩家摸牌时（**包括游戏最开始的摸牌**），输出一行：
  `x IN y`
  其中 `x` 为玩家名称，`y` 为摸到的牌。
- 当任意一名玩家出牌时，如果出的牌不是 `PASS`，输出一行：
  `x OUT y`
  其中 `x` 为玩家名称，`y` 为出的牌。
  如果出的牌是 `PASS`，应当输出一行：
  `x OUT PASS z`
  其中 `z` 为 `PASS` 指定的对象。
- 当任意一名玩家吃时，输出一行：
  `x CHOW y1 y2 y3`
  其中 `x` 为玩家名称，`y1`，`y2`，`y3` 为吃涉及到的 $3$ 张牌，按数字递增的顺序输出。
- 当任意一名玩家碰时，输出一行：
  `x PONG y1 y2 y3`
  其中 `x` 为玩家名称，`y1`，`y2`，`y3` 为碰涉及到的 $3$ 张牌，根据碰的规则，`y1`，`y2`，`y3` 应相同。
- 当任意一名玩家荣和时，输出一行：
  `x RON`
  其中 `x` 为玩家名称。
- 当任意一名玩家自摸时，输出一行：
  `x SELFDRAWN`
  其中 `x` 为玩家名称。
- 游戏的最后，如果某名玩家获得胜利，输出一行：
  `x WIN`
  其中 `x` 为玩家名称。
  如果出现流局，输出一行：
  `DRAW`

**需要特别注意的是，输入输出中出现的英文字母均为大写。**

samples:
8M
Z
E
9P
3P
9S
5P
W
3M
8P
DOUBLE
5P
Z
2P
3M
8S
2S
5P
5M
E
6M
9S
6P
5S
7M
4S
3S
6M
3S
2M
9M
5S
Z
7P
5P
8M
3M
F
7M
2S
N
4P
3S
S
PASS
1P
6S
3P
9P
9S
4M
8P
N
Z
N
5M
DOUBLE
REVERSE
S
3P
4M
4S
1S
PASS
4P
6S
7S
7P
6S
9M
REVERSE
3P
7P
DOUBLE
B
9P
4S
5S
7S
7S
7P
6S
9S
B
9M
S
F
2P
1P
PASS
9P
DOUBLE
4P
PASS
5S
2M
2P
6P
W
1M
8S
REVERSE
8M
6M
5M
F
4M
F
8P
2S
1M
2M
3M
7M
3S
B
7S
1S
REVERSE
8P
6M
4S
2M
B
1M
S
6P
5M
W
7M
2S
8S
8M
1S
4P
E
4M
9M
1M
8S
1S
1P
2P
1P
W
6P
N
E

samples:
A IN 8M
B IN Z
C IN E
D IN 9P
A IN 3P
B IN 9S
C IN 5P
D IN W
A IN 3M
B IN 8P
C IN DOUBLE
D IN 5P
A IN Z
B IN 2P
C IN 3M
D IN 8S
A IN 2S
B IN 5P
C IN 5M
D IN E
A IN 6M
B IN 9S
C IN 6P
D IN 5S
A IN 7M
B IN 4S
C IN 3S
D IN 6M
A IN 3S
B IN 2M
C IN 9M
D IN 5S
A IN Z
B IN 7P
C IN 5P
D IN 8M
A IN 3M
B IN F
C IN 7M
D IN 2S
A IN N
B IN 4P
C IN 3S
D IN S
A IN PASS
B IN 1P
C IN 6S
D IN 3P
A IN 9P
B IN 9S
C IN 4M
D IN 8P
A IN N
A OUT PASS B
C IN Z
C OUT DOUBLE
C IN N
C OUT Z
A PONG Z Z Z
A OUT 9P
B CHOW 7P 8P 9P
B OUT Z
C IN 5M
C OUT N
A PONG N N N
A OUT 3P
B CHOW 3P 4P 5P
B OUT F
C IN DOUBLE
C OUT DOUBLE
C IN REVERSE
C OUT REVERSE
B IN S
B OUT S
A IN 3P
A OUT 3P
D IN 4M
D OUT W
C IN 4S
C OUT E
B IN 1S
B OUT 4S
A RON
A WIN


title: 「C.E.L.U-02」划分可重集

description:
给你一个长度为 $n$ 的数列 $v$，请你将其划分成两个可重集 $a$ 和 $b$。你将从左至右开始划分，每个数必须至少被划分进一个可重集中。
一个数 $v_i$ 可以被划分进 $a$ 当且仅当 $j<i \ and\ v_j\le v_i-k$ 的 $v_j$ 都没有被划分进当前的 $a$。一个数 $v_i$ 可以被划分进 $b$ 当且仅当 $j<i\ and\ v_j\ge v_i+k$ 的 $v_j$ 都没有被划分进当前的 $b$。
同时给出了 $m$ 组关系，每组关系代表 $u$ 和 $v$ 不能划分进同一个可重集里。求能使划分成功的最小的 $k$。如果不存在合法划分，请输出 `-1`。

inputFormat:
第一行两个数 $n,m$，意义在题目描述中。
接下来一行共 $n$ 个数，代表 $v$。
下面 $m$ 行每行两个数，表示一组关系。

outputFormat: 仅一个数，答案。


title: [USACO20DEC] Cowntagion S

description:
Farmer John 和他的农民团队为了控制牛传染病 COWVID-19 在他们农场间的传播而夜以继日地工作。

他们共同监控着 $N$ 个农场（$1≤N≤10^5$），编号为 $1…N$。农场间由 $N−1$ 条道路连接，使得每个农场都可以从农场 $1$ 出发经过一些道路到达。

很不幸，农场 $1$ 中的一头奶牛的 COWVID-19 检测呈阳性。暂时这个农场的其他奶牛以及其他农场的所有奶牛都还没有染上疾病。然而，根据这个疾病通过接触传播的特性，Farmer John 推测每一天都会有以下不利的事件之一发生：

(1) 在一个农场内，「超级传播者」导致该农场感染 COWVID-19 的奶牛数量翻倍；或者

(2) 一头感染 COWVID-19 的奶牛从一个农场沿道路去往了一个相邻的农场。

Farmer John 担心疫情会很快爆发。请帮助 Farmer John 求出每个农场内均有至少一头奶牛感染疾病所需经过的最小天数。

inputFormat: 输入的第一行包含一个整数 $N$。以下 $N−1$ 行每行包含两个空格分隔的整数 $a$ 和 $b$，表示一条农场 $a$ 与 $b$ 之间的道路。$a$ 和 $b$ 均在 $1…N$ 范围内。

outputFormat: 输出疫情爆发至所有农场所需经过的最小天数。

hint:
该样例对应的一个可能的事件序列如下：农场 $1$ 内染病的奶牛数量翻倍再翻倍，使得两天后农场 $1$ 内有 $4$ 头染病的奶牛。在此后 $3$ 天，分别有一头染病的奶牛从农场 $1$ 去往农场 $2$、$3$ 和 $4$。$5$ 天过后每个农场均有至少 $1$ 头染病的奶牛。

 - 测试点 1-4 中，每个农场均直接与农场 $1$ 相连（除农场 $1$ 外）。
 - 测试点 5-7 中，农场 $2…N$ 均至多与两条道路相连。
 - 测试点 8-15 没有额外限制。

供题：Dhruv Rohatgi


title: [USACO20DEC] Rectangular Pasture S

description:
Farmer John 最大的牧草地可以被看作是一个由方格组成的巨大的二维方阵（想象一个巨大的棋盘）。现在，有 $N$ 头奶牛正占据某些方格（$1≤N≤2500$）。

Farmer John 想要建造一个可以包围一块矩形区域的栅栏；这个矩形必须四边与 $x$ 轴和 $y$ 轴平行，最少包含一个方格。请帮助他求出他可以包围在这样的区域内的不同的奶牛子集的数量。注意空集应当被计算为答案之一。

inputFormat: 输入的第一行包含一个整数 $N$。以下 $N$ 行每行包含两个空格分隔的整数，表示一头奶牛所在方格的坐标 $(x,y)$。所有 $x$ 坐标各不相同，所有 $y$ 坐标各不相同。所有 $x$ 与 $y$ 的值均在 $0…10^9$ 范围内。

outputFormat: 输出 FJ 可以包围的奶牛的子集数量。可以证明这个数量可以用 64 位有符号整数型存储（例如 C/C++ 中的long long）。

hint:
共有 $2^4$ 个子集。FJ 不能建造一个栅栏仅包围奶牛 $1$、$2$、$4$，或仅包围奶牛 $2$、$4$，或仅包围奶牛 $1$、$4$，所以答案为 $2^4-3=16-3=13$。

 - 测试点 2-3 满足 $N≤20$。
 - 测试点 4-6 满足 $N≤100$。
 - 测试点 7-12 满足 $N≤500$。
 - 测试点 13-20 没有额外限制。

供题：Benjamin Qi


title: [USACO20DEC] Stuck in a Rut S

description:
Farmer John 最近扩大了他的农场，从奶牛们的角度看来这个农场相当于是无限大了！奶牛们将农场上放牧的区域想作是一个由正方形方格组成的无限大二维方阵，每个方格中均有美味的草（将每个方格看作是棋盘上的一个方格）。Farmer John 的 $N$ 头奶牛（$1≤N≤1000$）初始时位于不同的方格中，一部分朝向北面，一部分朝向东面。

每一小时，每头奶牛会执行以下二者之一：

 - 如果她当前所在的方格里的草已经被其他奶牛吃掉了，则她会停下（并从这个时刻开始一直保持停止）。
 - 吃完她当前所在的方格中的所有草，并向她朝向的方向移动一个方格。

经过一段时间，每头奶牛的身后会留下一条被啃秃了的轨迹。

如果两头奶牛在一次移动中移动到了同一个有草的方格，她们会分享这个方格中的草，并在下一个小时继续沿她们朝向的方向移动。

当 Farmer John 看到停止吃草的奶牛时会不高兴，他想要知道谁该为他停止吃草的奶牛受到责备。如果奶牛 $b$
停在了之前奶牛 $a$ 吃过草的一个方格，我们就称奶牛 $a$ 阻碍了奶牛 $b$。进一步地，如果奶牛 $a$ 阻碍了奶牛 $b$ 且奶牛 $b$ 阻碍了奶牛 $c$，我们认为奶牛 $a$ 也阻碍了奶牛 $c$（也就是说，「阻碍」关系具有传递性）。每头奶牛受到责备的程度与这头奶牛阻碍的奶牛数量一致。请计算每头奶牛受到责备的数量——也就是说，每头奶牛阻碍的奶牛数量。

inputFormat:
输入的第一行包含 $N$。以下 $N$ 行，每行描述一头奶牛的起始位置，包含一个字符 N（表示朝向北面） 或 E（表示朝向东面），以及两个非负整数 $x$ 和 $y$（$0≤x≤10^9$，$0≤y≤10^9$）表示方格的坐标。所有 $x$ 坐标各不相同，所有 $y$ 坐标各不相同。

为了使方向和坐标尽可能明确，如果一头奶牛位于方格 $(x,y)$ 并向北移动，她会到达方格 $(x,y+1)$。如果她向东移动，她会到达方格 $(x+1,y)$。

outputFormat: 输出 $N$ 行。输出的第 $i$ 行包含输入中的第 $i$ 头奶牛受到的责备的数量。

hint:
在这个样例中，奶牛 3 阻碍了奶牛 2，奶牛 4 阻碍了奶牛 5，奶牛 5 阻碍了奶牛 6。根据传递性，奶牛 4 也阻碍了奶牛 6。

 - 测试点 2-5 中，所有坐标不超过 $2000$。
 - 测试点 6-10 没有额外限制。

供题：Brian Dean


title: [USACO20DEC] Replication G

description:
在网上观看太多机械 DIY 视频的后果就是，Farmer John 偶然在他的农场上制造了一个可以自我复制的机器人！

农场可以用一个 $N×N$ 的方阵表示（$3≤N≤1000$），其中每个方格是空的或有岩石，并且所有边界上的方格均有岩石。某些没有岩石的方格被指定为机器人可能的起始位置。

Farmer John 初始将机器人放置在可能的起始位置之一。在之后的每一个小时，机器人的所有副本会沿着相同的方向移动一格，向北、向南、向东或向西。每 $D$ 个小时（$1≤D≤10^9$）之后，机器人的每个副本会进行自我复制——在方格 $(x,y)$ 进行自我复制的机器人会在方格 $(x+1,y)$、$(x−1,y)$、$(x,y+1)$ 以及 $(x,y−1)$ 产生机器人的新的副本；原本的机器人仍然位于 $(x,y)$。一段时间过后，同一方格内可能会有多个机器人。

如果移动或复制会使得任何一个机器人撞到岩石，那么所有的机器人均立刻停止行动。注意这意味着所有机器人最终必然会停下，由于农场的边界都是岩石。

请帮助奶牛们求出可能在某个时刻含有机器人的空的方格数量。

inputFormat:
输入的第一行包含两个空格分隔的整数 $N$ 和 $D$。以下 $N$ 行每行包含 $N$ 个字符。每个字符均为 '.'、'S' 和 '#' 之一。'.' 和 'S' 均表示空的方格，且 'S' 表示一个可能的机器人起始位置。'#' 表示一块岩石。

所有第一行、最后一行、第一列、最后一列的字符均为 '#'。

outputFormat: 输出一个整数，表示可能在某个时刻含有机器人的方格数量。


title: [USACO20DEC] Bovine Genetics G

description:
Farmer John 在对他的奶牛进行基因组测序之后，他现在要进行基因组编辑了！我们知道，基因组可以用一个由 A、C、G、T 组成的字符串来表示。Farmer John 考虑的基因组的最大长度为 $10^5$。

Farmer John 从一个基因组开始，通过下列步骤对其进行编辑：

 1. 在所有连续相同字符之间的位置将当前基因组切开。
 2. 反转所有得到的子串。
 3. 按原先的顺序将反转的子串进行联结。

例如，如果 FJ 从基因组 AGGCTTT 开始，他会执行下列步骤：

 1. 在连续的 G 和 T 之间切开，得到 AG | GCT | T | T。
 2. 反转每一子串，得到 GA | TCG | T | T。
 3. 将这些子串联结起来，得到 GATCGTT。

不幸的是，在对基因组进行编辑之后，Farmer John 的计算机崩溃了，他丢失了他开始时的基因组序列。此外，编辑后的基因组的部分位置遭到了破坏，这些位置用问号代替。

给定编辑后的基因组序列，请帮助 FJ 求出可能的开始时的基因组序列的数量，对 $10^9+7$ 取模。

inputFormat: 一个非空字符串，其中每个字符为 A、G、C、T 和 ? 之一。

outputFormat: 输出可能的开始时的基因组序列的数量模 $10^9+7$ 的结果。

hint:
### 样例 2 解释：

除了在之前说明过的 AGGCTTT 之外，还有两种可能的开始时的基因组。

`AGGATTT -> AG | GAT | T | T -> GA | TAG | T | T -> GATAGTT`

`TAGGTTT -> TAG | GT | T | T -> GAT | TG | T | T -> GATTGTT`

### 测试点性质：

 - 测试点 1-4 中，基因组的长度不超过 $10$。
 - 测试点 5-11 中，基因组的长度不超过 $10^2$。
 - 测试点 12-20 没有额外限制。

供题：Benjamin Qi


title: [USACO20DEC] Square Pasture G

description:
Farmer John 最大的牧草地可以被看作是一个由方格组成的巨大的二维方阵（想象一个巨大的棋盘）。现在，有 $N$ 头奶牛正占据某些方格（$1≤N≤200$）。

Farmer John 想要建造一个可以包围一块正方形区域的栅栏；这个正方形必须四边与 $x$ 轴和 $y$ 轴平行，最少包含一个方格。请帮助他求出他可以包围在这样的区域内的不同的奶牛子集的数量。注意空集应当被计算为答案之一。

inputFormat:
输入的第一行包含一个整数 $N$。以下 $N$ 行每行包含两个空格分隔的整数，表示一头奶牛所在方格的坐标 $(x,y)$。所有 $x$ 坐标各不相同，所有 $y$ 坐标各不相同。所有 $x$ 与 $y$ 的值均在 $0…10^9$ 范围内。

注意尽管所有奶牛所在的方格坐标均非负，但围成的正方形区域可以包含坐标为负的方格。

outputFormat: 输出 FJ 可以包围的奶牛的子集数量。可以证明这个数量可以用 32 位有符号整数型存储。

hint:
 - 测试点 1-5 中，所有奶牛所在的方格的坐标均小于 20 。
 - 测试点 6-10 中，$N≤20$。
 - 测试点 11-20 没有额外限制。

供题：Benjamin Qi


title: [USACO20DEC] Sleeping Cows P

description:
Farmer John 有 $N$（$1≤N≤3000$）头各种大小的奶牛。他原本为每头奶牛量身定制了牛棚，但现在某些奶牛长大了，使得原先的牛棚大小不够用。具体地说，FJ 原来建造了 $N$ 个牛棚的大小为 $t_1,t_2,…,t_N$，现在奶牛的大小为 $s_1,s_2,…,s_N$（$1≤s_i,t_i≤10^9$）。

每天晚上，奶牛们都会按照某种方式寻找睡觉的牛棚。奶牛 $i$ 可以睡在牛棚 $j$ 中当且仅当她的大小可以进入牛棚（$s_i≤t_j$）。每个牛棚中至多可以睡一头奶牛。

我们称奶牛与牛棚的一个匹配是极大的，当且仅当每头奶牛可以进入分配给她的牛棚，且对于每头未被分配牛棚的奶牛无法进入任何未分配的空牛棚。

计算极大的匹配的数量模 $10^9+7$ 的结果。

inputFormat:
输入的第一行包含 $N$。

第二行包含 $N$ 个空格分隔的整数 $s_1,s_2,…,s_N$。

第三行包含 $N$ 个空格分隔的整数 $t_1,t_2,…,t_N$。

outputFormat: 输出极大的匹配的数量模 $10^9+7$ 的结果。


title: [USACO20DEC] Spaceship P

description:
奶牛 Bessie 外星人绑架了，现在被关在了一艘外星人的飞船里！飞船有 $N$（$1≤N≤60$）间房间，编号为 $1…N$，其中某些房间之间由单向通过的门所连接（由于使用了奇怪的外星技术，一扇门甚至可能从一间房间通回这间房间本身！）。然而，没有两扇门具有完全相同的出发和到达房间。此外，Bessie 有一个遥控器，上有编号为 $1…K$ （$1≤K≤60$）的按钮。

如果 Bessie 能够完成一个怪异的任务，外星人就会释放她。首先，他们会选择两间房间 $s$ 和 $t$（$1≤s,t≤N$），以及两个整数 $b_s$ 和 $b_t$（$1≤b_s,b_t≤K$）。他们会将 Bessie 放在房间 $s$ 内，并令她立刻按下按钮 $b_s$。然后 Bessie 需要继续在飞船内穿梭，同时按下按钮。有一些 Bessie 的行动需要遵守的规则：

 - 在每间房间内，在按下恰好一个按钮后，她必须选择从某扇门离开去往另一间房间（可能会回到同一间房间）或停止行动。
 - 一旦 Bessie 按下某个按钮，她再次按下这个按钮即为非法，除非在此之间她按下过编号更大的按钮。换句话说，按下编号为 x 的按钮会使得这个按钮变为非法，同时所有编号 $<x$ 的按钮会被重置为合法。
 - 如果 Bessie 按下非法的按钮，任务即失败，外星人就会把她关起来。

仅当 Bessie 停止行动时位于房间 $t$，她最后按下的按钮是 $b_t$，并且没有按下过非法按钮时，Bessie 才会被释放。

Bessie 担心她可能无法完成这一任务。对于 $Q$
（$1≤Q≤60$）个询问，每个询问包含一组 Bessie 认为可能的 $s,t,b_s$ 以及 $b_t$，Bessie 想要知道可以使她得到释放的通过房间与按键序列的数量。由于答案可能非常大，输出对 $10^9+7$ 取模的结果。

inputFormat:
输入的第一行包含 $N,K,Q$。

以下 $N$ 行每行包含 $N$ 个二进制位（$0$ 或 $1$）。如果从房间 $i$ 到房间 $j$ 存在一扇门，则第 $i$ 行的第 $j$ 位为 1，如果没有这样的门则为 0。

以下 $Q$ 行，每行包含四个整数 $b_s$、$s$、$b_t$、$t$，分别表示起始按钮、起始房间、结束按钮、结束房间。

outputFormat: 对 $Q$ 个询问的每一个，在一行内输出操作序列的数量模 $10^9+7$ 的结果。

hint:
门连接了房间 $1→2$、$2→3$、$3→4$、$4→5$ 以及 $6→6$。

对于第一个询问，Bessie 必须在按下第一个按钮后立刻停止行动。

对于第二个询问，答案显然为零，因为无法从房间 3 前往房间 1。

对于第三个询问，Bessie 的唯一选择是从房间 1 移动到房间 2 到房间 3，同时按下按钮 1、2 和 3。

对于第四个询问，Bessie 的移动方式是唯一的，她有三种可能的按键序列：

 - (1,2,3,2,1)
 - (1,2,1,3,1)
 - (1,3,1,2,1)

对于最后一个询问，Bessie 有五种可能的按键序列：

 - (2)
 - (2,3,2)
 - (2,3,1,2)
 - (2,1,3,2)
 - (2,1,3,1,2)

### 测试点性质：

 - 测试点 4-7 中，$K≤5$ 且 $(b_s,s)$ 在所有询问中均相同。
 - 测试点 8-11 中，对所有询问有 $b_s=K−1$ 以及 $b_t=K$。
 - 测试点 12-15 中，$N,K,Q≤20$。
 - 测试点 16-23 没有额外限制。

供题：Benjamin Qi


title: [USACO20DEC] Cowmistry P

description:
Bessie 的化学作业已经拖了很久，现在需要你的帮助！她需要用三种不同的化学品制造一种混合物。所有聪明的奶牛都知道，某些化学品之间不能进行混合，否则会产生爆炸。具体地说，两种标号为 $a$ 和 $b$ 的化学品当 $a⊕b≤K$ （$1≤K≤10^9$） 时可以出现在同一种混合物中。

注：这里，$a⊕b$ 表示非负整数 $a$ 与 $b$ 的「异或」。这一运算等价于在二进制下将每一对应位相加并且舍弃进位。例如，
$$0⊕0=1⊕1=0$$
，
$$1⊕0=0⊕1=1$$
，
$$5⊕7=101_2⊕111_2=010_2=2$$
。

Bessie 有 $N$ 盒化学品，第 $i$ 个盒子内有标号从 $l_i$ 到 $r_i$ 的化学品（$0≤l_i≤r_i≤10^9$）。没有两个盒子中含有同一种化学品。她想要知道她可以得到多少种由三种不同的化学品混合而成的混合物。如果至少一种化学品出现在一种混合物中而没有出现在另一种中，则认为这两种混合物是不同的。由于答案可能非常大，输出对 $10^9+7$ 取模的结果。

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

以下 $N$ 行，每行包含两个空格分隔的整数 $l_i$ 和 $r_i$。保证所有化学品盒子按其中内容的升序给出；也就是说，对所有 $1≤i<N$ 有 $r_i<l_{i+1}$。

outputFormat: 输出 Bessie 可以由三种不同化学品制造的混合物的数量，对 $10^9+7$ 取模。

hint:
我们可以将所有化学品分为不能交叉混合的 $13$ 组：$(0 \ldots 15)$，$(16 \ldots 31)$，… $(192 \ldots 199)$。前 $12$ 组每组贡献了 $352$ 种混合物，最后一组贡献了 $56$ 种（因为所有 $\binom{8}{3}$ 种 $(192 \ldots 199)$ 中三种不同化学品的组合均可行），总共为 $352 \cdot 12 + 56 = 4280$。

 - 测试点 3-4 满足 $\max(K, r_N) \le {10}^4$。
 - 测试点 5-6 对某个 $k \ge 1$ 满足 $K = 2^k - 1$。
 - 测试点 7-11 满足 $\max(K, r_N) \le {10}^6$。
 - 测试点 12-16 满足 $N \le 20$。
 - 测试点 17-21 没有额外限制。

对于所有测试点，满足 $1 \le N \le 2 \times {10}^4$。

供题：Benjamin Qi


title: 「RdOI R2」风雨(rain)

background:
经历过风雨的洗礼，小 Soup 才更懂得珍惜。他认为所有的一切对他来说都有重要的意义。为了能让这一切被自己牢牢铭记，小 Soup 决定用一些手段将它们记录下来。

[$\text\color{white}{真正的题目背景}$](https://z3.ax1x.com/2021/03/29/c9xbLj.gif)

description:
小 Soup 在这段时间中记录了 $n$ 个有意义的东西，他把它们用字符串表示了出来，第 $i$ 个东西被表示成 $s_i$，并定义了它的价值 $a_i$。下面，小 Soup 会进行 $m$ 次操作。
操作 $1$：小 Soup 将区间 $l,r$ 里的 $a_i$ 都加上一个常数 $k$。
操作 $2$：小 Soup 将区间 $l,r$ 里的 $a_i$ 都赋值成一个常数 $k$。
操作 $3$：小 Soup 给出了一段回忆，这段回忆形成了一个字符串 $S$，他想求 $S$ 在区间 $l,r$ 中的意义有多大。定义 $cnt_i$ 为 $s_i$ 在 $S$ 中的出现次数，则 $S$ 在区间 $l,r$ 中的意义为 $\sum\limits_{i=l}^r cnt_i\times a_i$。

inputFormat:
第一行两个数，$n,m$。
接下来 $n$ 行第 $i$ 行一个字符串 $s_i$ 和一个数 $a_i$。
接下来 $m$ 行每行一个操作，先有三个数，$op,l,r$。其中 $op$ 代表操作类型。$op=3$ 时，多输入一个字符串 $S$，否则多输入一个数 $k$。

outputFormat: 对于每个 $3$ 操作输出一个数，代表总价值。

samples:
6 6
aba 3
ba 2
aa 2
c 1
abac 4
ab 2
3 2 5 abac
2 3 5 3
3 4 6 abc
1 2 3 1
3 1 3 aabaa
3 2 5 aabac

samples:
6 3
b 1
aa 8
cc 9
cac 8
ab 10
a 7
2 1 3 2
3 1 4 acac
3 1 6 ccaba


title: 「PMOI-1」游戏

background:
> 大眼观察乃交互题第一要义

——command_block 《考前小贴士》

djy 的同桌和 djy 玩五子棋玩腻了，就发明了一个~~更无聊的~~新游戏，因为 djy 太菜了，所以你要帮这个蒟蒻想出必胜策略。

description:
**这是一个 IO 交互题。**

这个游戏在一个平面直角坐标系的**原点，$x,y$ 正半轴**和**第一象限**中进行。

交互程序黑棋，你白棋，黑棋先开始，**保证交互库第一步下 $(0,0)$**。**黑白棋都只能下在 $x,y$ 坐标都为自然数的点**。

若出现**横竖斜任意一个方向**有连续的 `黑白白白`，则白棋赢，若你用了 $x$ 步胜利，且 $x\le 13$，你得到 $\frac{\min(14-x,10)}{10}$ 占比的分数。

### 交互方式

先输入一个整数 $T$ 表示进行 $T$ 次游戏。

接下来的 $T$ 次游戏，执行以下过程：

**第一步交互库走的 $(0,0)$ 无需输入。**

然后重复执行以下两步直到你下了 $14$ 步棋或者你获胜：

1.你输出一行两个数 `x y`，表示你下的棋的坐标是 $(x,y)$。

2.你读入一行两个数 `x y`，表示交互库下的棋的坐标是 $(x,y)$。**若你在走完上一步就已经获胜，则不会读入这两个数，而是直接进入下一局游戏。**

**特殊地，为了方便交互，你所有下的棋的坐标必须在 $100$ 以内，否则会直接判你 $14$ 步，立即结束这局游戏。同时交互库所有下棋的坐标也保证在 $100$ 以内。同时，如果下在已有棋子上**，则视为你这次下到了一个很远的地方，**即放弃这次下棋的机会。如果想主动放弃，也可以采用这种方式。请注意交互库也可能选择放弃某次下棋的机会。**

你的得分比为 $T$ 次游戏的得分比**最小值**。

inputFormat:
上述的所有输入都应从标准输入中读入，所有输出都应向标准输出中输出。输出一行后必须清空缓冲区，否则你的评测将被判为 Time Limit Exceeded。清空缓冲区方式如下：

- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。
- 在 Pascal 中，使用 `flush(output)`。
- 在 Python 中，使用 `stdout.flush()`。
- 其他语言请自行查阅文档。

outputFormat: 如题目描述。$T$ 组交互结束后不应有任何多余的输出。

hint:
【样例解释】

黑棋一直选择放弃，白棋下了 $(0,1),(0,2),(0,3)$ ，与黑棋的 $(0,0)$ 在竖着的方向形成了``黑白白白``。从而白棋胜利。

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

- Subtask1（10pts）：保证交互库随机下在一个点上。
- Subtask2（10pts）：保证交互库除了在你下一步必胜时，均选择放弃下棋。
- Subtask3（20pts）：$T=5$。
- Subtask4（60pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le 10^3$。


title: 平凡点滴

background:
少年看见他的桌上有一本书。
翻开着其中一页。
上面只有一道题。

description:
他写下一个函数 $f(n)$。
它是这么定义的：
记 $n$ 的质因子分解式中每个质因子的最大次数为 $g(n)$，例如 $g(2)=1,g(12)=2$。
**注意**：本题中假设 $g(1)=1$。样例及数据已修正。
则 $f(n) = \max(m-g(n)+1,0) n^k$。
其中 $m,k$ 都是他将给定你的参数。

他希望你求出
$$
\sum\limits_{i=1}^n \sum\limits_{j=1}^n f(\gcd(i,j))
$$

并对 $998244353$ 取模。

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

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


title: [COCI2020-2021#2] Euklid

description:
对于正整数 $a, b$，定义 $R(a, b)$ 为：

 $\begin{cases}R(b,a)&a<b\\R\left(\left\lfloor\dfrac{a}{b}\right\rfloor,b\right)&1<b\leq a\\a&1=b\leq a\end{cases}$

给定正整数 $g, h$，求正整数 $a, b$ 使得 $\gcd(a,b)=g$，$R(a,b)=h$。

inputFormat:
第一行一个整数 $T$，代表数据组数。
接下来 $T$ 行每行两个正整数 $g_i, h_i$。

outputFormat:
输出 $T$ 行，每行两个满足题意的正整数 $a_i, b_i$。
要求 $a, b$ 均不超过 $10^{18}$。
可以证明一定有满足题意的 $a, b$，若有多组解输出任意一组即可。

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

$\gcd(99,23)=1$，$R(99,23)=4$

**【数据范围】**

对于 $100\%$ 的数据，$1 \leq g \leq 200,000$，$2 \leq h \leq 200,000$。

Subtask #1（$4$ pts）：$g=h$。
Subtask #2（$7$ pts）：$h=2$。
Subtask #3（$7$ pts）：$g=h^2$。
Subtask #4（$14$ pts）：$g,h \leq 20$。
Subtask #5（$36$ pts）：$g,h \leq 2000$。
Subtask #6（$32$ pts）：无附加约束。

**【说明】**

译自 [Croatian Open Competition in Informatics 2020 ~ 2021 Round 2 C Euklid](https://hsin.hr/coci/contest2_tasks.pdf)。


title: [COCI2020-2021#2] Sjekira

description: 有一棵 $n$ 个结点的树，每个结点有一个权值，删除一条边的费用为该边连接子树中结点权值最大值之和。问以任意顺序删除树中所有边的最小花费。

inputFormat:
第一行一个整数 $n$，表示结点数。
第二行 $n$ 个整数 $t_1, t_2, \ldots , t_n$，其中第 $i$ 个数表示结点 $i$ 的权值。
接下来 $n-1$ 行，每行两个整数 $x, y$，表示 $x$ 和 $y$ 之间有一条边。

outputFormat: 输出一个数，代表最小花费。

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

先删 $(2,3)$，再删 $(1,2)$，花费为 $5+3=8$。

**【数据范围】**

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

Subtask #1（$10$ pts）：$n \leq 10$。
Subtask #2（$10$ pts）：$i$ 与 $i-1$ 有边直接相连。
Subtask #3（$30$ pts）：$n \leq 1000$。
Subtask #4（$50$ pts）：无附加限制。

**【说明】**

译自 [Croatian Open Competition in Informatics 2020 ~ 2021 Round 2 D Sjekira](https://hsin.hr/coci/contest2_tasks.pdf)。


title: [COCI2020-2021#2] Svjetlo

description:
有一个呈树状结构的吊灯，由 $n$ 个灯泡组成，这些灯泡之间有 $n-1$ 根电线连接。每个灯泡有一个按钮，能使灯泡的状态发生改变，即把打开的灯泡关闭，关闭的灯泡打开。你需要把所有的灯泡打开。

你可以选择一个序列，序列中两两相邻位置的灯泡相邻，灯泡可以在序列中出现多次。你可以依次改变序列中的灯泡的状态。

你需要计算出最短的符合题目要求的灯泡序列。保证至少有一个灯泡在开始时处于关闭状态。

inputFormat:
第一行一个整数 $n$，表示灯泡的数量。
第二行一个长为 $n$ 的 01 序列，表示灯泡的状态，其中“0”代表关闭，“1”代表打开。
接下来 $n - 1$ 行每行两个整数 $x, y$，表示 $x$ 与 $y$ 之间有边。

outputFormat: 输出序列的最小长度。可以证明这样的序列一定存在。

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

序列可以为 $1, 2, 3, 2$。

**【数据范围】**

对于 $100\%$ 的数据，$2 \leq n \leq 500,000$。

Subtask #1（$19$ pts）：$n \leq 100$。
Subtask #2（$27$ pts）：每个灯泡最多与两个灯泡相连。
Subtask #3（$27$ pts）：一开始所有灯泡均处于关闭状态。
Subtask #4（$27$ pts）：无附加限制。

#### 说明

译自 [Croatian Open Competition in Informatics 2020 ~ 2021 Round 2 E Svjetlo](https://hsin.hr/coci/contest2_tasks.pdf)。


title: [COCI2020-2021#3] Knjige

description:
Tin 认为书籍不按顺序摆放是最讨厌的。Ante 决定帮助他。在排序的过程中，每一步可以执行下列二者操作之一：

- 若对应手上无书，则可从**堆顶**取下一本书并放在左手或右手上。
- 将一本在其手上的书放置到书架顶端。

Ante 希望你能找到一种方法，能使**左侧**书架的书能从顶部到底端依次对应从薄到厚。

inputFormat:
第一行包含一个整数 $n$，表示左侧书架上书的数目。

第二行包含 $n$ 个整数 $d_i$，依次按从顶部到底端顺序表示书籍的厚薄程度。

outputFormat:
第一行输出一个整数 $k$，表示你的方法所需执行操作的步数。

接下来的 $k$ 行，按照 `INSTRUCTION HAND SHELF` 格式输出：

- `INSTRUCTION`：若 Ante 应从书架顶端取下一本书，则输出 `UZMI`；若他应往一个书架顶端放置一本书，则输出 `STAVI`。
- `HAND`：若使用左手，则输出 `L`，否则输出 `D` 表示使用右手。
- `SHELF`：若涉及到左侧书架，则输出 `L`，否则输出 `D` 表示涉及到右侧书架。

你的方案**不一定**与最少操作次数相等，但总操作次数必须不超过 $100000$。可以证明，在满足数据条件的情况下，必定有至少一种方案。

samples:
8
UZMI L L
STAVI L D
UZMI L L
UZMI D L
STAVI L L
UZMI L D
STAVI L L
STAVI D L

hint:
#### 样例 1 解释

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

#### 数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 100$，$1 \le d_i \le 1000$，$0 \le k \le 10^5$。

#### 说明

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

本题使用自行编写的非官方 [Special Judge](https://www.luogu.com.cn/paste/enzsg1cn)，欢迎大家 hack（可私信或直接发帖）。注意，Special Judge 对输出格式敏感，每行末尾请不要输出多余空格。

**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf)  _T1 Knjige_。**


title: [COCI2020-2021#3] Vlak

description:
Nina 和 Emilija 在纸上做游戏。刚开始，纸是空白的。在一个回合里，一个玩家将一个字母加入到纸上一个单词的末尾。接着，二者交替顺序。规定 Nina 为先手。

玩家们选择字母时必须遵循这样的原则：每一次添加字母**后**的单词必须是该玩家最喜爱歌曲中某个单词的前缀。如果某个玩家无法继续执行它的回合，那么她就输了。

如果两位玩家选择的策略都是最佳的，请判断谁是赢家。

inputFormat:
第一行包含一个正整数 $n$，表示 Nina 最喜爱歌曲中的单词数量。

接下来的 $n$ 行，每一行输入 Nina 最喜爱歌曲中的一个单词。

接下来的一行包含一个正整数 $m$，表示 Emilija 最喜爱歌曲中的单词数量。

接下来的 $m$ 行，每一行输入 Emilija 最喜爱歌曲中的一个单词。

输入的单词都只包含小写字母，且单词长度总和不超过 $200000$。

outputFormat: 输出获胜的玩家，`Nina` 或 `Emilija`。

hint:
#### 样例 1 解释

如果 Nina 先写下字母 `b`，那么 Emilija 将必须写下 `b`，然后 Nina 将继续写下 `b`。则当前的单词为 `bbb`，而 Emilija 将无法继续执行下一步，因此 Nina 获胜。

如果 Nina 先写下字母 `a`，那么 Emilija 将写下 `b`。单词将变成 `ab`，因此 Nina 将无法继续执行下一步，因此她将输掉。

#### 数据规模与约定

对于其中 $40$ 分的数据，单词长度总和不超过 $2000$。

对于 $100\%$ 的数据，单词长度总和不超过 $200000$。

#### 说明

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

**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf)  _T2 Vlak_。**


title: [COCI2020-2021#3] Sateliti

background: 为了得到进一步的探索进展，阿雷西博望远镜将拍下土星的卫星。研究团队必须区分卫星图像并将它们按卫星分组，但由于卫星从不同角度拍摄，因此并不容易。

description:
捕捉到的图像可以以一个 $n \times m$ 的矩阵呈现，其中 `*` 表示火山，而 `.` 表示平地。我们认为两个图像属于同一颗卫星，当且它们能**环形地互相通过向上下或左右平移得到**。

科研工作者想要找到**字典序最小**的与给定图像属于同一颗卫星的图像。我们把图像的所有行依次连接组成字符串，再判断字符串的字典序即可。

inputFormat:
第一行包含两个整数 $n,m$，表示图像的规模。

接下来的 $n$ 行，每行输入 $m$ 个字符，表示图像所对应的矩阵。

outputFormat: 输出共 $n$ 行，每行有 $m$ 个字符，表示满足要求的字典序最小的图像。

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

所有可能的情况：

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

**【数据范围】**

| Subtask | 分值 | 数据范围及约定 |
| :----------: | :----------: | :----------: |
| $1$ | $10$ | $1 \le n,m \le 50$ |
| $2$ | $40$ | $1 \le n,m \le 300$ |
| $3$ | $60$ | 无 |

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

**【说明】**

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

**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf)  _T3 Sateliti_。**


title: [COCI2020-2021#3] Selotejp

background: 在 Mirko 看来，没有比找到一卷新的胶带纸要更令人快乐，而今天他格外开心，因为他找到 Slavko 的基督日历。

description:
基督日历可以被一个 $n$ 行 $m$ 列的表格所表示。每个方格包含一个小窗口，而每个小窗口后有一块巧克力。Slavko 已经打开了部分窗口，而其他的处于关闭状态。

Mirko 打算用他的胶带纸去把所有的窗口粘贴，使它们处于关闭状态。胶带纸长度无限大，并且宽度与一个窗口吻合。Mirko 可以撕下一部分胶带纸来将 **一横排或一纵列连续的窗口** 合上，使其关闭。他不想放太多胶带纸，因为他仍旧想做 Slavko 的朋友。

他想知道将**所有**窗口都关闭所需的**最少**胶带纸的数量。

inputFormat:
第一行输入两个整数 $n,m$，表示基督日历的规模。

接下来的 $n$ 行，每行包含 $m$ 个字符，表示基督日历的各个方格。`.` 表示关闭的窗口，`#` 表示打开的窗口。

outputFormat: 输出关闭所有窗口所需胶带纸数量的最小值。

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

一种符合题意的方案：分别在第一列整列、第三列整列和第二行第二列处使用胶带纸。

**【数据范围】**

| Subtask | 分值 | 数据范围及约定 |
| :----------: | :----------: | :----------: |
| $1$ | $35$ | 每个窗口与至多两个已关闭的窗口相邻 |
| $2$ | $35$ | $1 \le n \le 10$ |
| $3$ | $40$ | 无 |

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

**【说明】**

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

**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf)  _T4 Selotejp_。**


title: [COCI2020-2021#3] Specijacija

description:
给定一个正整数 $n$ 个一个满足 $\frac{i(i-1)}{2} \lt a_i \le \frac{i(i+1)}{2}$ 的正整数序列 $a_1, a_2, \cdots, a_n$。

该序列是一棵包含 $\frac{(n+1)(n+2)}{2}$ 个节点的树参数化而来的，它包括 $n+1$ 层，每层分别包括 $1, 2, \cdots, n+1$ 个节点，如图所示：

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

它由 $a=(1,2,6)$ 参数化而来。

第 $i$ 层包含节点 $\frac{i(i-1)}{2}+1, \cdots, \frac{i(i+1)}{2}$。节点 $a_i$ 有两个孩子，而其他同层的节点都只有一个孩子。

请回答 $q$ 个询问，求 $x,y$ 的最大公共祖先，即既是 $x$ 的祖先，又是 $y$ 的祖先且权值最大的节点。

inputFormat:
第一行包含三个整数 $n,q,t$，分别表示参数的数量、询问次数和用来决定节点权值的参数。

第二行输入一个长度为 $n$ 的序列 $a$（其中对于每一个数 $a_i$ 有 $\frac{i(i-1)}{2} \lt a_i \le \frac{i(i+1)}{2}$）。

接下来的 $q$ 行中的第 $i$ 行包含两个整数 $\tilde x_i$ 和 $\tilde y_i$（$1 \le \tilde x_i, \tilde y_i \le \frac{(n+1)(n+2)}{2}$），用来决定询问时节点的权值。

设 $z_i$ 为第 $i$ 次询问的结果，规定 $z_0=0$。第 $i$ 次询问的权值为：

$$x_i=[(\tilde x_i-1+t \times z_{i-1}) \bmod \frac{(n+1)(n+2)}{2}]+1$$

$$x_i=[(\tilde y_i-1+t \times z_{i-1}) \bmod \frac{(n+1)(n+2)}{2}]+1$$

注：当参数 $t=0$ 时，满足 $x_i=\tilde x_i$，$y_i=\tilde y_i$。当 $t=1$ 时，权值应通过先前的答案来决定。

outputFormat: 输出共 $q$ 行，其中第 $i$ 行，输出 $x_i$ 和 $y_i$ 的最大公共祖先。


title: [IOI2019] 折线

background: 您可以在此处下载[输入文件](https://cowtransfer.com/s/9b9c30ef6dc74d)。

description:
阿塞拜疆因地毯而闻名。作为一位地毯设计大师，你在做新设计时想画一条**折线**。一条折线是二维平面上包含 $t$ 条线段的线段序列，而这些线段由包含 $t+1$ 个点 $p_0,\ldots,p_t$ 的点序列按照下述规则定义给出：对所有的 $0\le j\le t- 1$，都有一条线段连接点 $p_j$ 和 $p_{j+1}$。

为完成这个新设计，你已经标出了二维平面中的 $n$ 个**小圆点**。小圆点 $i$（$1 < i < n$）的坐标为 $(x_i,y_i)$。**不存在 $x$ 坐标或 $y$ 坐标相同的两个小圆点**。

现在你想要找到一个点序列 $(sx_0,sy_0),(sx_1, sy_1)\ldots (sx_k, sy_k)$，由该点序列定义给出的折线需满足：
- 该折线从 $(0,0)$ 开始（即 $sx_0=0$ 且 $sy_0=0$），
- 该折线经过所有的小圆点（它们不必是线段的端点），以及
- 该折线仅包括水平线段和竖直线段（对于定义该折线的连续两个点，其 $x$ 坐标或 $y$ 坐标相等）。

折线可以以任意的方式自相交或自重叠。正式地来说，平面上的每个点可以属于折线中任意数量的线段。

本题是一个有部分分的提交答案型题目。将会给你 $10$ 个输入文件， 这些文件给出了小圆点的位置。对每个输入文件，你需要提交一个答案文件，描述满足要求的折线。对每个给出合法折线的输出文件，你的得分将依赖于折线中的**线段数量**（参见下面的计分方式一节）。

你不需要为本题提交任何源代码。

inputFormat:
每个输入文件的格式如下：
- 第 $1$ 行：$n$。
- 第 $1+i$ 行（这里 $1<i\le n$）：$x_i\ y_i$。

outputFormat:
每个输出文件必须按照如下格式：
- 第 $1$ 行： $k$。
- 第 $1+j$ 行（这里 $1\le j\le k$）： $sx_j\ sy_j$。

注意，第二行应包含 $sx_1$ 和 $sy_1$ （也就是说，输出**不应当**包含 $sx_0$ 和 $sy_0$）。所有的 $sx_j$ 和 $sy_j$ 均应为整数。


title: [CTSC2002] 购房计划

description:
$\text{Bill}$ 和 $\text{Scott}$ 是商业对手。他们都计划在 $\text{Javaville}$ 城市购买一幢房子，但是他们希望自己的住宅尽量远离对方的住宅。由于 $\text{Javaville}$ 是一座新兴的城市，所以暂时还没有地图，于是，他们只能从当地人的口中搜集信息，这些信息包括建筑物的位置和建筑物之间的距离。尽管这些信息并不完整，但是它们都是正确的。

$\text{Javaville}$ 的街道是一个矩形网格，包含 $m$ 条东西走向的街道，依次用大写字母$\text{A},\text{B},\text{C},\cdots$标识，$n$ 条南北走向的街道，依次用数字 $0,1,2,\cdots$ 标识。我们把两条街道的交点称为交叉路口，两个交叉路口之间的一段街道称为街区。所有的建筑物都位于交叉路口处，每个交叉路口至多只有一座建筑物。建筑物之间的距离定义为从一座建筑物到另一座建筑物所需经过的最少的街区数。

例如，$\text{Bill}$ 和 $\text{Scott}$ 搜集了以下这些信息：
- 城市中有 $5$ 条东西走向的街道和 $5$ 条南北走向的街道；
- 住宅 $1$ 位于交叉路口 $A0$；
- 邮局位于交叉路口 $A4$；
- 学校与住宅 $1$ 距离 $4$ 个街区；
- 住宅 $2$ 与邮局距离 $6$ 个街区；
- 学校与邮局距离 $6$ 个街区；
- 住宅 $3$ 与邮局距离 $6$ 个街区；

![](https://darkbzoj.tk/JudgeOnline/upload/201112/1(4).jpg)

根据以上信息，我们可以得到 $\text{Javaville}$ 城市可能的两种布局。我们发现：住宅 $1$，邮局和学校的位置都已经确定了，而住宅 $2$ 可以位于 $C0$ 或 $E2$，住宅 $3$ 可以位于 $C0$ 或$E2$。于是，城市中总是存在两座住宅相距 $6$ 个街区（地图 $1$ 中的 $h1$ 与 $h3$，地图 $2$ 中的 $h1$ 与 $h2$）。但是，对于确定的两座住宅，我们可以保证的最长距离只有 $4$ 个街区 ($h2$ 与 $h3$ 的距离总是 $4$ 个街区)。于是，我们要告诉 $\text{Bill}$ 和 $\text{Scott}$，尽管总是存在两座相距 $6$ 个街区的住宅，然而最安全的建议是：一人购买住宅 $2$，另一人购买住宅 $3$。

下面给出所求数值的严格定义：

- 一个可行的城市布局 $S$ 的直径 $d(S)$ 定义为该布局中距离最远的两座住宅之间的距离。

- 对于确定的两座住宅 $i, j$，它们的安全系数 $e[i, j]$ 定义为在所有可行的城市布局中，住宅 $i, j$ 之间的距离的最小值。

$\text{Bill}$ 和 $text{Scott}$ 希望你编写一个程序，根据他们所搜集到的信息，计算出 $D$ 和$E$。其中：$D=\min\{d(S)\}$；$E=\max\{e[i, j]\}$。同时你还要给出最安全的购房建议，即所有满足 $e[i, j]=E$ 的住宅 $i, j$。

对于上面的例子，第一种布局的 $d(S_1)=6$，第二种布局的 $d(S_2)=6$。每两座住宅之间的安全系数是：$e[1,2]=2，e[1,3]=2，e[2,3]=4$。于是：$D=min{d(S1),d(S2)}=6，E= max{e[1,2],e[1,3],e[2,3]}=4$，最安全的购房建议是：住宅 $2$ 与住宅 $3$。

inputFormat:
第一行包含两个正整数 $m, n（1\le m, n\le 10）$，分别表示东西走向的街道数目和南北走向的街道数目。第二行包含一个整数，表示所搜集到的信息条数 $t(1\le t\le 50)$。文件从第三行开始每行描述一条所搜集到的信息，每条信息都是以下两种形式之一：
- `name  LOCATION  r  c`

或者

- `name  DISTANCE  d  name2`

这两种形式分别描述建筑物的位置和建筑物之间的距离。

其中，$\text{name}$ 和 $\text{name2}$ 是仅包含数字和小写字母的字符串，长度不超过 $20$，表示建筑的名称。$r$ 是 $\text{A}$ 到 $\text{J}$ 之间的大写字母，$c$ 是一个数字，表示建筑物所位于的交叉路口。$d$ 是一个正整数，表示两座建筑物之间的距离。如果建筑物名称的前五个字符是小写字母 $\text{“house”}$，那么表示这是一座可以购买的住宅，否则表示一座非民用的建筑物。如果信息是第二种形式，那么其中的 $\text{name2}$ 一定在前面的信息中出现过。

这组信息中至少包含两座可以购买的住宅，至多包含 $25$ 座不同的建筑物。

outputFormat: 第一行包含两个整数，分别表示 $D$ 和 $E$，之间用一个空格隔开

samples:
5 5
6
house1 LOCATION A 0
postoffice LOCATION A 4
school DISTANCE 4 house1
house2 DISTANCE 6 postoffice
school DISTANCE 6 postoffice
house3 DISTANCE 6 postoffice

hint: 所有数据范围均在输入格式中提到。


title: [CTSC2002] 玩具兵

description:
小明的爸爸给他买了一盒玩具兵，其中有 $K$ 个步兵，$K$ 个骑兵和一个天兵，个个高大威猛，形象逼真。盒子里还有一个$M\times N$棋盘，每个格子 $(i,j)$ 都有一个高度$H_{i,j}$，并且大得足以容纳所有的玩具兵。小明把所有的玩具兵都放到棋盘上去，突然想到了一种很有趣的玩法：任意挑选 $T$ 个不同的格子，并给每个格子 $i$ 规定一个重要值$R_i$，游戏的目标就是每次沿东南西北之一的方向把一个玩具兵移动到其相邻的格子中（但不能移动到棋盘外面去），最终使得每个挑选出的格子 $i$ 上恰好有 $R_i$ 个玩具兵。小明希望所有的玩具兵都在某个选定的格子中，因此他总是使选出的T个格子的重要值之和等于玩具兵的个数。为了增加难度，小明给玩具兵们的移动方式做了一些规定：

- 步兵只会往高处爬，因此如果两个格子A和B相邻，当且仅当格子A的高度小于或等于B，步兵才可以从A移动到B。

- 骑兵只会往低处跳，因此如果两个格子A和B相邻，当且仅当格子A的高度大于或等于B，骑兵才可以从A移动到B。

- 天兵技术全面，移动不受任何限制。

可是没玩几次，小明就发现这个游戏太难了，他常常玩了好半天也达不到目的。于是，他设计了一种“超能力”，每使用一次超能力的时候，虽然不能移动任何一个玩具兵，但可对它们进行任意多次交换操作，每次交换两个玩具兵。等这次超能力使用完后又可和平常一样继续移动这些玩具兵。借助强大的超能力，这个游戏是容易玩通的，但是怎样才能让使用超能力的次数最少呢？

inputFormat:
第一行包含四个整数：$M,N,K,T (2\le M,N\le 100, 1\le K\le 50, 1\le T\le 2K+1)$

第二行包括 $2K+1$ 个数对 $(x_i,y_i)$，代表各个玩具兵的初始位置。前 $K$ 个代表步兵，接下来的 $K$ 个代表骑兵，最后一个代表天兵。

第三行包含 $T$ 个三元组 $(x_i,y_i,r_i)$，第 $i$ 组代表第 $i$ 个目标格的位置和重要值。

以下 $M$ 行，每行 $N$ 个整数。其中第 $i$ 行第 $j$ 个数为即格子的高度 $H_{i,j}$。高度是不超过 $100$ 的正整数，注意：不同玩具兵的初始位置可能相同。输入数据保证无错，选定的 $T$ 个格子的重要值之和保证等于 $2K+1$。

outputFormat: 仅包含一行，即使用超能力的最小次数 $T$。

hint: 所有数据范围均在输入格式内。


title: [BalticOI 2012 Day1] 括号

description:
一个合法括号序列的定义如下：

- () 和 [] 是合法括号序列
- 若 A 是合法括号序列，则 (A) 和 [A] 也是合法括号序列
- 若 A 和 B 都是合法括号序列，则 AB 也是合法括号序列

在包含至少一对方括号的合法括号序列中，我们可以将 [ 和 ] 都用 ( 代替，这样就能够得到一个不合法括号序列。

例如 (( 和 ((((())) 都是不合法括号序列，前者可以由合法括号序列 \[] 转化而来，后者可以通过 \[]((()))，(\[](()))，((\[]())) 和 (((\[]))) 这四种合法括号序列转化而来。

现在给出一个不合法括号序列，求有多少种合法括号序列，在将其中的方括号用 ( 代替后，可以得到给定的括号序列。

inputFormat:
第一行一个正整数 $n$，表示给出的不合法括号序列的长度。
第二行一个长度为 $n$ 的字符串，代表给出的序列，只包含 ( 和 )。

outputFormat: 输出符合要求的合法括号序列总数对 $10^9+9$ 取模后的结果。

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

满足条件的合法括号序列有两种：\[]() 和 ([])。

**【数据范围】**

- 对于 20% 的数据，满足 $n \leq 50$
- 对于 50% 的数据，满足 $n \leq 1000$
- 对于 100% 的数据，满足 $2\leq n \leq 30000$

**【说明】**

译自 [BalticOI 2012 Day1 T1. Brackets](http://www.boi2012.lv/data/day1/eng/brackets.pdf)


title: [BalticOI 2012 Day1] 移动网络

description: 有一条线段与若干个点，求线段上的点离最近的点最远的距离。

inputFormat:
第一行两个整数 $n$，$l$，代表总共有 $n$ 个点，线段端点为 $(0,0)$ 与 $(l,0)$。
接下来每行两个整数 $(x,y)$，描述了点的横纵坐标，保证没有两个点坐标相同。
给出点的坐标以横坐标为第一关键字，纵坐标为第二关键字升序排序。

outputFormat:
输出最远距离。

本题开启 SPJ，你的答案与标准答案与标准答案误差不超过 $10^{-3}$ 即为正确。

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

距离最远的点在两个点的中垂线与线段的交点处。

**【数据范围】**

- 对于 25% 的数据，满足 $n \leq 5000$
- 对于 50% 的数据，满足 $n \leq 10^5$
- 对于 100% 的数据，满足 $1\leq n \leq 10^6$，$1 \leq l \leq 10^9$，$-10^9 \leq x_i,y_i \leq 10^9$

**【说明】**

译自 [BalticOI 2012 Day1 T2. Mobile](http://www.boi2012.lv/data/day1/eng/mobile.pdf)


title: [BalticOI 2012 Day2] 城市烟花

description:
这是一座有着无限网格状街道的城市，有一些市民住在网格的交点处。(可能会有两个市民住在相同的地方)

现在你需要选择某个竖直街道与水平街道 $0$ 的交点处进行烟花表演，市民需要赶到这个地点所在的水平街道或竖直街道上来观看，同时他们离燃放地点的距离不能小于 $S$。你需要选择一个燃放地点以最小化市民们的移动距离。

inputFormat:
第一行两个整数 $N$，$S$，分别代表市民总数和最小距离。

接下来 $N$ 行每行两个整数 $H_i$，$V_i$，表示这位市民住在水平街道 $H_i$ 与 竖直街道 $V_i$ 交点处。

outputFormat: 输出移动距离和的最小值。

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

注意水平街道 $-4$ 与竖直街道 $8$ 交点处有两个人居住。

最优解是选择竖直街道 $8$，此时距离取最小值 $9$。

**【数据范围】**

- 对于 $20\%$ 的数据，满足 $0 \leq V_i \leq 5000$
- 对于 $40\%$ 的数据，满足 $N \leq 5000$
- 对于 $100\%$ 的数据，满足 $1 \leq N \leq 10^5$，$1 \leq S \leq 10^6$，$-10^9 \leq H_i,V_i \leq 10^9$

**【说明】**

译自 [BalticOI 2012 Day2 T1. Fireworks in RightAngleles](http://www.boi2012.lv/data/day2/eng/fire.pdf)


title: [BalticOI 2012 Day1] 山峰

description:
有一个 $N \times M$ 大小的岛屿，每个点有不同的海拔。定义相邻为两个点横纵坐标差均不超过 $1$。定义路径为任意两个连续点都相邻的序列。定义平坦的区域是一组联通的海拔相同的点的极大集合，山峰是一个不与任何海拔更高的点相邻的平坦区域。

给出这个岛屿上每个点的海拔，你需要求出岛屿上所有的山峰与前往比其高度更高的山峰所需经过的最低点的海拔的最大值。

inputFormat:
第一行两个整数 $N,M$，代表地图的长和宽。

接下来 $N$ 行，每行 $M$ 个整数 $E_{i,j}$ ，描述了 $(i,j)$ 的海拔。

outputFormat:
第一行一个整数 $P$，代表岛上的山峰数。

接下来 $P$ 行，每行两个整数 $h_0,h_1$，代表某座山峰的海拔，以及从该山峰出发到达更高的山峰所需经过的最低点的海拔的最大值。

输出应以 $h_0$ 为第一关键字，$h_1$ 为第二关键字降序排列，特别的，对于最高峰，$h_1=0$

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

![](https://cdn.luogu.com.cn/upload/image_hosting/flr0h9rs.png)
如上图所示，其中圆圈圈出的为山峰，从海拔为15的山峰前往其他山峰的一条路径用深色标出。

**【数据范围】**

- 对于 15% 的数据，满足 $\min (N,M)\leq 2$
- 对于 50% 的数据，满足 $P \leq 500$
- 对于 80% 的数据，满足 $P \leq 5000$
- 对于 100% 的数据，满足 $1 \leq N,M \leq 2000$，$N \times M \leq 10^5$，$1 \leq E_{i,j} \leq 10^6$

**【说明】**

译自 [BalticOI 2012 Day1 T3. Peaks](http://www.boi2012.lv/data/day1/eng/peaks.pdf)


title: [BalticOI 2012 Day2] 旋律

description:
有一种不为人知的乐器，这种乐器有 $S$ 个孔，可以通过十种不同的方式 $(0$ ～ $9)$ 覆盖这些孔来弹奏出 $N$ 个音符。你不能采取除了这 $N$ 个音符以外的孔的覆盖方式。

现在你要弹奏一首乐曲，但是由于这种乐器每两个音符之间不能有超过 $G$ 个孔的覆盖方式不同，所以你可能不得不弹错一些音符。你希望最小化你弹错音符的数目。

inputFormat:
第一行三个整数 $N, S, G\ (0 \le G < S \le 100)$，含义如上文所述。

接下来 $N$ 行，每行一个长度为 $S$ 的字符串（只包含数字），表示弹奏这个音符时孔的覆盖方式。

接下来一行一个整数 $L$，表示乐曲中包含的音符的数目。

最后一行 $L$ 个整数，表示乐曲中音符的编号。

outputFormat:
第一行一个整数，表示你能取到的弹错音符数目的最小值。

接下来一行 $L$ 个整数，表示你的任意一种构造方案。

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

音符 $1$ 和音符 $5$ 在四个孔上的弹奏方式都不同，所以你不能在弹奏完音符 $1$ 后弹奏音符 $5$。

**【数据范围】**

- 对于 $40\%$ 的数据，$L \leq 100$；
- 对于 $65\%$ 的数据，$L \leq 5000$；
- 对于 $100\%$ 的数据，$1 \leq N \leq 100$，$1 \le L \le 10 ^ 5$。

**【说明】**

译自 [BalticOI 2012 Day2 T2. Melody](http://www.boi2012.lv/data/day2/eng/melody.pdf)。


title: [BalticOI 2012 Day2] 俄罗斯方块

description:
这是一个和俄罗斯方块较为类似的游戏。游戏中一共有一下几个碎片：

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

游戏有一个 $9 \times 9$ 的区域。对于每个下落的碎片，你可以指定这个碎片最左边的方块（即图片中做标记的方块）下落的列。如果碎片没有完全落在区域内，游戏结束。此时如果有被方块完整填满的行，这一行的所有方块将被清除，上面的方块则相应向下移动。

游戏一共有 $N$ 个碎片，你需要使尽量多的碎片成功下落。

注意本游戏中碎片不能旋转。

inputFormat:
输入文件请点击附件下载。

第一行一个整数 $N$，代表游戏共有 $N$ 个碎片。

接下来 $N$ 行每行一个整数，表示下落碎片的编号。

数据保证有解。

outputFormat:
对于输入文件请提交相应的输出文件。

输出文件最多包含 $N$ 行，每行一个整数，表示该下落的碎片最左边方块落在的列的编号。

hint:
**【提示】**

每个测试点 $20$ 分。

如果你能使 $A$ 个碎片正常下落，那你能够获得该测试点 $\dfrac{A}{N}$ 的分数。

**【说明】**

译自 [BalticOI 2012 Day2 T3. Tiny](http://www.boi2012.lv/data/day2/eng/tiny.pdf)


title: 「MCOI-04」纯水精灵

background: 轻策的净水之主——「纯水精灵」洛蒂娅是一个掉水元素角色突破材料的 BOSS。今天你想刷点材料，所以……

description:
洛蒂娅所在的水面上有 $n$ 块平台，初始时均未沉没。有 $m$ 对不同的平台彼此相连。洛蒂娅与敌人战斗了 $k$ 个回合。每一回合，她可以选择一些未沉没的平台，让这些平台沉没（可以不选，但不可以让全部平台沉没）。然后她会选择最多的平台，满足任意两块选择的平台之间都相连，在每块平台上召唤一种不同的水之幻形。$k$ 回合结束后，洛蒂娅对敌人的伤害就是每回合召唤的水之幻形数量之和。洛蒂娅想知道，对于她的所有不同选择方案，伤害的总和是多少。两种方案被视为不同当且仅当存在一回合，使得两种方案在这一回合沉没的平台不同，而与召唤水之幻形的平台无关。由于答案可能很大，你需要输出它对 $10^9+7$ 取模的结果。

简要题意：给定无自环无重边的无向图，$k$ 回合中每回合可以删去现有点集的任意真子集，求所有方案中每回合后剩下的图最大团大小之和模 $10^9+7$。

inputFormat:
第一行输入三个整数 $n,m,k$，分别表示平台数，相连的平台对数，回合数。

接下来 $m$ 行每行两个整数 $x,y$，表示 $x$ 号平台和 $y$ 号平台相连。平台从 $0$ 到 $n-1$ 编号。保证没有自环和重边。

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


title: Look At The Sky

background:
![Look At The Sky](https://mivik.gitee.io/image/nurture/look_at_the_sky.jpeg)

> Look at the sky, I'm still here
>
> I'll be alive next year
>
> I can make something good, oh
>
> Something good

本题加强版：[U148588](https://www.luogu.com.cn/problem/U148588)

description:
Mivik 又把 $(x+y)^2$ 当成 $(x^2+y^2)$ 来算了！蒟蒻的他望向天空，看见朵朵白云飘散又融合，忽然来了灵感，写下了一个序列 $S$ 的 $k$ 阶平均数的定义：
$$
avg_k(S)=\frac{\sum_{i=1}^{|S|}{S_i^k}}{\left(\sum_{i=1}^{|S|}S_i\right)^k}
$$
Mivik 想起 2020 年发生的一切，对他而言很重要的一共有 $n$ 件。例如，举办了自己的第一场比赛、见证了 Porter Robinson 时隔一年后重新在音乐界活跃、和那个人相遇... 其中有一些事件之间相互有联系，也就是说它们形成了一张无向图。Mivik 把这个无向图的所有极大连通块的大小依次写在了一张白纸上，认为这代表了他 2020 年所经历的一切。或美好、或悲伤，Mivik 现在把这张白纸折成了纸飞机准备放飞它。不过在此之前，Mivik 想要求一下这个白纸上的数的 $k$ 阶平均数，并作为 2020 年的纪念记录在日记本上。

可惜的是，Mivik 的记性不太好：他只记得一共发生了 $n$ 件大事，但却记不清它们之间的关系了。Mivik 干脆让你求出在所有可能的情况下，这个白纸上的数的 $k$ 阶平均数之和。实际上，Mivik 并不在意 $k$ 是什么，他只在意最终的答案写在日记本上是否美观，于是他干脆让你对所有 $k\in [0,K]$ 算出上面的值，这样他好选出一个。

两种情况本质不同，当且仅当存在两件事情，它们在一种情况中没有联系而在另一种情况中有。

形式化题意：记一张无向图的连通块集合 $f(G)$ 为这张图所有极大连通块的大小形成的任意顺序的序列，要求对所有 $k\in [0,K]$ 求：
$$
\sum_{G\in S(n)}\frac{\sum_{i=1}^{|f(G)|}{f(G)_i^k}}{\left(\sum_{i=1}^{|f(G)|}f(G)_i\right)^k}
$$
$S(n)$ 为所有大小为 $n$ 的无向图形成的集合。答案对 $998244353$ 取模。如果你不知道如何将一个有理数对质数取模，可以参考 [有理数取模](https://www.luogu.com.cn/problem/P2613)。

inputFormat: 一行两个正整数，代表 $n$ 和 $K$，意义同题面。

outputFormat: $K+1$ 行，第 $i$ 行一个整数，代表 $k=i-1$ 时的答案。


title: [COCI2015-2016#3] POT

description:
老师给同学们发了一封电子邮件，任务如下。

> 写一个程序，给你 $n$ 个数，输出 $X$。
> $$X = num_1^{p_1} + num_2^{p_2} + \cdots + num_n^{p_n}$$
> $num_1$，$num_2$，$\cdots$，$num_n$ 都是整数，$p_1$，$p_2$，$\cdots$，$p_n$ 都是一位数。

但是出现了一些玄学错误，使得 $X$ 变成了：
$$X = q_1 + q_2 +... + q_n$$

注：$q_i = num_i \times 10 + p_i$。

例如，原来的 $X$ 为 $21^2+125^3$，但现在变成了 $212+1253$。请帮助老师编写一个程序，输出原来 $X$ 的值。

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

接下来 $n$ 行，每行一个整数 $q_i$。

outputFormat: 仅一行一个整数，$X$ 的值。

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

对于 $100\%$ 的数据，$1 \le n \le 10$，$10 \le p_i \le 9.999 \times 10 ^ 3$，$1 \leq X \leq 10 ^ 9$。

#### 说明
翻译自 [COCI 2015-2016 #3 A POT](https://hsin.hr/coci/archive/2015_2016/contest3_tasks.pdf)，满分 50。