title: [BalkanOI2018] Zalmoxis

description:
**翻译自 [BalkanOI 2018](http://boi2018.ro) Day2 T3「[Zalmoxis](http://boi2018.ro/assets/Tasks/BOI/Day_2/zalmoxis/zalmoxis_en.pdf)」**

**「ZalPunch」** 是一种修改数列的方式，每次 ZalPunch 可以将数列中的任意一个正整数 $x$ 原地替换成两个 $(x-1)$。
* 正确示范：$[1, 1]\xrightarrow{ZalPunch}[0, 0, 1]$；
* 正确示范：$[1,23,3]\xrightarrow{ZalPunch}[1,22,22,3]$；
* 错误示范：$[1,3]\xrightarrow{ZalPunch}[2,1,2]$（第一个 2 不在原位）。

从数列 $[30]$ 开始，用 ZalPunch 修改该数列任意多次，所得到的所有数列都称为 **「ZalSequence」**（含数列 $[30]$）。
给你一个有 $N$ 项的数列 $S$，请在其中插入 $K$ 个数（不是使用 $K$ 次 ZalPunch），使之变成 ZalSequence。保证有解。

inputFormat:
第一行有两个整数 $N, K$。
第二行有 $N$ 个整数，表示数列 $S$。

outputFormat: 输出 $N+K$ 个整数，表示新数列。


title: [BalticOI 2018] 多角恋

type: P

description:
**题目译自 [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day1「[Love Polygon](https://boi18-day1-open.kattis.com/problems/boi18.polygon)」**

给一张 $N$ 个点的有向图，每个点的出度为 $1$。每次可以花费 $1$ 的代价修改图上的一条边的终点，也就是改变从一个点出发所到达的点。求最少需要花费多少代价，才能使这张图形成若干个两两不相交的二元环，并且图上的所有点都在某一个环里。

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

接下来的 $N$ 行每行包含两个字符串 $s$ 和 $t$，表示图中存在一条 $s\rightarrow t$ 的边。

字符串只包含小写英文字母，且长度不超过 $10$。

outputFormat: 输出一个整数，表示最少需要花费多少代价，才能使这张图形成若干个两两不相交的二元环，并且图上的所有点都在某一个环里。无解请输出 $-1$。

samples:
8
leonard emmy
ada emmy
isaac leonard
emmy pierre
pierre bernhard
bernhard emmy
sofia karl
karl sofia

samples:
3
rocky scarlet
scarlet patrick
patrick rocky

hint:
#### 样例 1 解释

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

唯一的最优解如上图所示，图的上半部分为原图，底色为粉色的三个点为需要修改的边的起点；图的下半部分表示修改后的情况。

#### 样例 2 解释

存在多组最优解。其中一种是分别改变一条以 ``a``、``b`` 和 ``d`` 为起点的边，使他们分别连接到 ``b``、``a`` 和 `c`。

#### 样例 3 解释

图中有 $3$ 个点，无论如何修改边的终点，总会有一个人不在环里。

| 子任务 | 分值 | 数据范围 | 附加限制 |
|:----------:|:-------:|:-------------:|:-------------:|
|$1$|$21$|$2\leqslant N\leqslant 20$|.|
|$2$|$25$|$2\leqslant N\leqslant 100\, 000$|每个点都有一条入边（可能有自环）|
|$3$|$29$|$2\leqslant N\leqslant 100\, 000$|不存在两个点或更多个点构成的环|
|$4$|$25$|$2\leqslant N\leqslant 100\, 000$|.|


title: [BalticOI 2018] 蠕虫之忧

description:
**题目译自 [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day1「[Worm Worries](https://boi18-day1-open.kattis.com/problems/boi18.worm)」**

**本题是一道交互题。**

在一个三维空间（我们限制大小为 $N\times M\times K$）内，每个点都有一个正整数参数，记这个参数为 $H[x,\, y,\, z]$（保证 $1$ $\leqslant$ $x$ $\leqslant$ $N$ $,$ $1$ $\leqslant$ $y$ $\leqslant$ $M$ $,$ $1$ $\leqslant$ $z$ $\leqslant$ $K$ 且每个参数都不超过 $10^9$）。你最多可以询问 $Q$ 次，找到一个点，使得这个点的参数大于它周围与它有公共边的所有点的参数，即：$H[x,\,y,\,z]\geqslant\max(H[x+1,\,y,\,z],$ $H[x-1,\,y,\,z],$ $H[x,\,y-1,\,z],$ $H[x,\,y-1,\,z],$ $H[x,\,y,\,z+1],$ $H[x,\,y,\,z-1]).$

特别地，当一个点不在空间直角坐标系的第一卦限内时，它的参数为 $0$。

inputFormat:
**请使用标准输入输出流**与交互库进行交互。你可以向交互库询问最多 $Q$ 次，每次可以询问一个点的参数。

输入的第一行包含四个整数 $N,\,M,\,K,\,Q$ （请忽略这一行的其他参数）。在此之后，你可以向交互器提出至多 $Q$ 行形如 ``? x y z`` 的询问，表示“询问坐标为 $(x,\,y,\,z)$ 的点的参数是多少”。对于每一组询问，交互器会输出一行一个整数表示坐标为 $(x,\,y,\,z)$ 的点的参数。

当你找到一组解时，输出一行 ``! x y z`` 表示你找到的答案是 $(x,\,y,\,z)$，并终止程序。此时交互器不会有任何输出。

所有坐标必须满足 $1\leqslant x\leqslant N,\, 1\leqslant y\leqslant M,\, 1\leqslant z\leqslant K$。如果不满足坐标的限制、询问不符合格式或询问超过了 $Q$ 行，交互器会输出 ``-1`` 并退出，此时你的程序也应该退出。否则你可能会得到 ``Runtime Error`` 或 ``Time Limit Exceeded`` 的判定结果。

请注意，你必须在每一次询问之后手动刷新缓存，否则你的程序将会超时，对于各语言，刷新缓存的方法如下：

 - Java: 调用 ``System.out.println()`` 会自动刷新缓存；
 - Python: 调用 ``print()`` 会自动刷新缓存；
 - C++: ``cout << endl`` 可以输出一个换行并刷新缓存。如果使用 ``printf``，请使用 ``fflush(stdout)``；
 - Pascal: 调用 ``Flush(Output)``。

为了帮助你更好地完成交互，我们提供了可以复制到你的程序里的可选代码。可选代码使用了较快的输入输出，可能会提高 IO 较慢的 Python 和 Java 语言的程序效率（只与最后两个子任务有关）。

交互器没有使用随机函数，这意味着，每组测试数据都是固定的，与你的程序的询问无关。

outputFormat:
为了使你更好地完成交互，下面给出一组交互的示例。在这个示例中，$N=3,\,M=3,\,K=1,\,Q=3$，这三个格子的参数为 $\{10,\,14,\,13\}$。以 ``JUDGE`` 开头的行表示交互库输出的内容（你的程序的标准输入的内容），以 ``YOU`` 开头的行表示你的程序的输出。

```
JUDGE:      3 1 1 3 123123 fixed 10 14 13
YOU  :      ? 3 1 1
JUDGE:      13
YOU  :      ? 2 1 1
JUDGE:      14
YOU  :      ? 1 1 1
JUDGE:      10
YOU  :      ! 2 1 1
```


title: [BalticOI 2018] 火星人的 DNA

description:
**题目译自 [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day1「[Martian DNA](https://boi18-day1-open.kattis.com/problems/boi18.dna)」**

给定一个字符集大小 $|\Sigma| = K$ 的长度为 $N$ 的字符串和 $R$ 个要求，每个要求为使子串中的字符 $B$ 至少出现 $Q$ 次。求出满足所有要求的最短子串长度。

inputFormat:
第一行包括三个整数 $N,\, K,\, R$，分别表示字符串的长度、字符集的大小和要求个数，保证 $1\leqslant R\leqslant K\leqslant N$。
第二行包含 $N$ 个用空格隔开的整数，表示这个字符串。字符从 $0$ 开始编号，每个字符集中的字符至少出现一次。
接下来的 $R$ 行，每行两个整数 $B$ 和 $Q$，表示一组要求，满足 $0\leqslant B < K,\, 1\leqslant Q\leqslant N$，同一个字符不会被重复要求两次。

outputFormat: 输出一个整数，满足所有要求的最短子串长度。特别地，如果不存在这样的子串，输出 "``impossible``"。

hint:
#### 样例 1 解释

有三个长度为 $2$ 的子串含有字符 $0$ 和 $1$ 各一个，分别为 ``0 1``、``1 0`` 和 ``0 1``，但是不存在长度为 $1$ 的子串满足要求，因此满足要求的最短子串的长度为 $2$。

#### 样例 2 解释

最短的满足要求的子串为 ``1 3 2 0 1 2 0``。

#### 样例 3 解释

在这个字符串中，``0`` 的数量不足。

| 子任务 | 分值 | 限制 |
|:--------:|:------:|:------:|
|$1$     |$16$  |$1\leqslant N\leqslant 100,\, R\leqslant 10$|
|$2$     |$24$  |$1\leqslant N\leqslant 4\, 000,\, R\leqslant 10$|
|$3$     |$28$  |$1\leqslant N\leqslant 200\, 000,\, R\leqslant 10$|
|$4$     |$32$  |$1\leqslant N\leqslant 200\, 000$|

感谢 Hatsune_Miku 提供的翻译


title: [YsOI2020] 计划

background:
相信大家已经知道了这样几个事实：
- Ysuperman 是很有钱。

- Ysuperman 一直都很善于制定计划。

- Ysuperman 管理着一个幼儿园。

- Ysuperman 收藏了一些零食。

- 每一天，TA 可能会心血来潮地想要有计划地吃掉 TA 的零食。

description:
Ysuperman 现在有 $n$ 份零食，对**每份**零食而言，TA 每一天有 $P$ 的概率对 TA 的这份零食做出计划，TA 每做出一份计划后的 $T$ 天后，TA 将会将这一份零食给吃掉。需要特殊说明的是，如果在Ysuperman制定计划前已经对该份零食做出计划，则实际会按照**第一份计划的时间**将零食吃掉。

不幸的是，幼儿园内贪吃的小朋友会破坏这一计划。  幼儿园内有 $m$ 个小朋友，TA 们觊觎着 Ysuperman 的零食。对于**每份**零食，每天会有 $p_i$ 的概率被第 $i$ 个小朋友偷吃。如果这份零食在某位小朋友偷吃之前被吃掉了，那么相应地，这位小朋友就偷吃不了。**如果有一份零食在计划完成前被偷吃，那么，相关计划就无法实现了。**

现在 Ysuperman 要对 TA 的计划进行风险评估，TA 悬赏了 $114514pts$ ，这个项目在经过层层转包后来到了您的手上，现在已经算出了各概率在模意义下的值。经过各方协商，您如果解决了这个问题，您可以获得 $ 100pts $ 。您需要告诉 TA **Ysuperman 能期望吃掉多少份零食，以及 Ysuperman 的零食期望在多少天后被吃完** 。

**如果一份零食被某位小朋友吃掉了，那么这份零食就不属于Ysuperman了。**

需要注意的是，Ysuperman每天制定计划的时间在小朋友偷吃糖果**之前**。

Ysuperman 认为浮点数的精度误差太大，所以你只需要输出答案**对 $998244353$ 取模**的结果。

inputFormat:
第一行包括三个正整数 $n,m,T$ ，含义如题目所述。

第二行包括一个正整数 $ P $ ，表示 $P$ 对 $998244353$ 取模后的结果。

第三行包括 $m$ 个正整数 $p_1,p_2,\cdots,p_m$ ，分别表示 $p_i$ 对 $998244353$ 取模后的结果。

outputFormat: 一行，两个自然数。 分别表示 Ysuperman 能期望吃掉多少份零食，以及 Ysuperman 的零食期望在多少天后被吃完，您需要输出答案对 $998244353$ 取模后的结果。


title: [AHOI2008] 矩形藏宝地

description: 欢乐岛上最著名的游戏是一个寻宝游戏，小可可来到宝藏的埋藏地，这是一块开阔地，宝藏被分散的埋藏在这块地下，现在要做的是一件件的把宝藏挖出来。为了提示宝藏的埋藏点，游戏的主办方把这块开阔地当作第一象限，将所有可能埋藏宝藏的地方划成一个个矩形的土地，并把这些矩形土地的坐标都告诉了参赛者。挖宝的提示很简单，只要某一个矩阵土地至少被另外一个矩阵土地所包含，那么这个矩阵土地里肯定埋有宝藏。其实这些宝藏都是一些精美的纪念品，如果谁挖出来了纪念品就归谁了，小可可很想为这次旅程画上完美的句号，有你的帮助他信心十足，你只要告诉他：有多少个矩形土地里肯定埋有宝藏就行了。胜利就在眼前，加油吧！

inputFormat:
第一行包含一个整数 $N\leq 200000$，表示矩形的个数。
接下来 $N$ 行，每行用 $4$ 个整数 $x_1,\,y_1,\,x_2,\,y_2$，描述了一个矩形。其中 $(x_1,\,y_1)$ 表示这个矩形左下角的坐标，$(x_2,\,y_2)$ 表示右上角的坐标，一个 $x$ 值或 $y$ 值最多出现一次。

outputFormat: 只包含一个整数，表示肯定埋有宝藏的矩形土地的个数。

hint:
$30\%$ 的数据中，$N\leq 5000$。

$70\%$ 的数据中，$N\leq 50000$。

$100\%$ 的数据中，$N\leq 200000$。

所有数据中，一个 $x$ 值或 $y$ 值最多出现一次。坐标范围 $2\times 10 ^ 6$。


title: [BalticOI 2018] 交流电

background: ### 滥用本题评测将封禁帐号

description:
**题目译自 [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day2「[Alternating Current](https://boi18-day2-open.kattis.com/problems/boi18.alternating)」**

给一个环，这个环可以被分为等长的 $N$ 段，分别标号为 $1\ldots N$。同时你可以通过 $M$ 个控制点将环的某一段染成红色或蓝色，这 $M$ 个控制点分别编号为 $1\ldots M$。

如何安排这 $M$ 个点控制的线段的颜色，使得轨道上每个点都被至少一条红色线段和至少一条蓝色线段覆盖。

保证这个环中不存在不能被染色的部分。

inputFormat:
第一行包含两个整数 $N$ 和 $M$，分别表示轨道段数和控制点个数。

接下来 $M$ 行，每行两个整数 $a$ 和 $b$，分别表示每一个控制点可以控制颜色的左右端点。特别地，若 $a=b$ 则这个控制点只控制 $a$ 这一条长度为 $1$ 的线段；若 $b < a$ 则说明这个控制点能控制编号在区间 $[a,\, N]\cup[1,\,b]$ 内的所有线段。

outputFormat:
输出一行 $M$ 个字符，每个字符是 ``0`` 或 ``1``，分别表示设置在第 $i$ 个控制点控制的线段上，染成红色还是蓝色。

如果有多组解请输出任意一组，如果无解请输出 ``impossible``。

hint:
#### 样例 1 解释
![](https://gitee.com/mingqihuang/pics/raw/master/alternatingfig.pdf.svg)

上图为样例 1 的一组解。注意可以将所有的箭头反向得到另一组合法解 ``11010``。

## 限制与提示

|子任务|分值|数据范围|附加限制|
|:----:|:--:|:------:|:------:|
|$1$   |$13$|$2\leqslant N,\,M\leqslant15$|.|
|$2$   |$20$|$2\leqslant N,\,M\leqslant100$|.|
|$3$   |$22$|$2\leqslant N,\,M\leqslant1000$|.|
|$4$   |$19$|$2\leqslant N,\,M\leqslant100\,000$|保证 $b\geqslant a$|
|$5$   |$26$|$2\leqslant N,\,M\leqslant100\,000$|　|

感谢 Hatsune_Miku 提供的翻译


title: [BalticOI 2018] 基因工程

description:
**题目译自 [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day2「[Genetics](https://boi18-day2-open.kattis.com/problems/boi18.genetics)」**

给定 $N$ 个长度为 $M$ 的只由 ``A``、``T``、``G`` 和 ``C`` 组成的字符串，分别编号为 $1\ldots N$，其中一个是模式串，其它 $N-1$ 个字符串与模式串都恰好有 $K$ 个字符不同，找到这个模式串。

inputFormat:
第一行包含三个整数 $N$, $M$ 和 $K$，满足 $1\leqslant K\leqslant M$。

接下来 $N$ 行，每行一个长度为 $M$ 的字符串。

数据保证模式串一定存在。

**警告：本题 IO 量较大，对于 Java 或 Python 语言，请使用较为快速的 IO 操作。**

outputFormat: 输出一个整数表示模式串的编号。


title: [BalticOI 2018] 路径

description:
**题目译自 [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day2「[Paths](https://boi18-day2-open.kattis.com/problems/boi18.paths)」**

给定一张 $N$ 个点 $M$ 条边的无向图，每个点有一个颜色，所有点的颜色共有 $K$ 种，编号为 $1\ldots K$。求图上有多少条长度至少为 $2$ 的简单路径，满足路径上的每一个点的颜色互不相同。

路径上的点的连接顺序不同看作不同的两条路径。

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

第二行包含 $N$ 个在 $1$ 到 $K$ 之间的整数，表示每个点的颜色。

接下来的 $M$ 行每行两个整数 $a$ 和 $b$，表示图的一条边。

数据保证图无自环无重边。

outputFormat: 输出一个整数表示每一个点颜色都不同的路径条数。保证答案不会超过 $10^{18}$。

hint:
#### 样例 1 解释
![](https://gitee.com/mingqihuang/pics/raw/master/pathsfig.pdf.svg)

样例 1 中表达的图如上图所示。每个点的底色分别为白色（颜色 $1$）、灰色（颜色 $2$）或黑色（颜色 $3$）。共有 $10$ 条路径满足路径上的所有点的颜色都不同。它们是：``1-2``, ``2-1``, ``2-3``, ``3-2``, ``2-4``, ``4-2``, ``1-2-4``, ``4-2-1``, ``3-2-4`` 和 ``4-2-3``。

注意 ``1`` 不能看作是一条路径，因为一条路径至少连接两个点。``1-2-3`` 也不满足条件，因为有两个点都是 $1$ 号颜色。

|子任务|分值|数据范围|
|:--:|:--:|:--:|
|$1$|$23$|$1 \leqslant N,M \leqslant 100, 1 \leqslant K \leqslant 4$|
|$2$|$20$|$1 \leqslant N,M \leqslant 300\,000, 1 \leqslant K \leqslant 3$|
|$3$|$27$|$1 \leqslant N,M \leqslant 300\,000, 1 \leqslant K \leqslant 4$|
|$4$|$30$|$1 \leqslant N,M \leqslant 100\,000, 1 \leqslant K \leqslant 5$|

感谢 Hatsune_Miku 提供的翻译


title: Tweetuzki 爱军训

description:
Tweetuzki 仍然记得，初一军训的时候，有关他们班的教官的一些事儿。

Tweetuzki 所在的班级有 $n$ 名学生，座号从 $1$ 到 $n$。有一次，教官命令班上的 $n$ 名学生按照座号顺序从左到右排成一排站好军姿，其中 $1$ 号学生在最左边，$n$ 号学生在最右边。

由于同学们站了很久，怨声载道，仁慈的教官又不希望大家一起解散导致混乱的局面，于是想了一个办法：教官从最左边——也就是 $1$ 号学生身旁出发，走到 $n$ 号学生右边后，再折返回到 $1$ 号同学旁边。在教官在从 $1$ 号同学走到 $n$ 号同学这段路上，当走到某位同学身边时，他可以选择让这位同学出列，也可以等到折返的时候再使这名同学出列。

但是有一些同学在军训过程中表现极坏，因此教官希望他们晚一些出列休息。对于 $i$ 号同学，定义他的“坏值”为 $w_i$。教官希望在一次往返过程中，使得所有学生出列，且最大化 $\sum_{i = 1}^n r_i \times w_i$ 的值，其中 $r_i$ 表示 $i$ 号同学是第 $r_i$ 位出列的学生。机智的教官一下子就想出了这个方案，Tweetuzki 大为惊讶，于是他去请教教官如何做到。可是他的胆子很小而且“坏值”很大，教官可能不会告诉他，所以他就找到了你。

inputFormat:
第一行一个整数 $n$ ( $5 \le n \le 10^6$ )。
第二行包含 $n$ 个整数，描述这 $n$ 个同学的坏值 $w_1, w_2, w_3, …, w_n$ $(0 \le w_i \le 10^6)$。

outputFormat:
第一行一个整数，表示最大值。
接下来一行包含 $n$ 个这个数，描述一个合理的出列顺序，输出的是对应同学的“坏值”，详见样例。如果有多个满足条件的出列顺序，请输出出列的人序号字典序最小的。

hint:
### 样例解释 1

在去的路上让 $3, 4, 5$ 号同学出列，回来时让 $2, 1$ 号同学出列。总的值为 $5 \times 7 + 4 \times 8 + 1 \times 1 + 2 \times 2 + 3 \times 5 = 87$，可以证明没有使得答案大于 $87$ 的方案。

### 数据范围

本题共设 $20$ 组测试点，每组测试数据 $5$ 分。

对于 $10\%$ 的数据，$n \le 8$。
对于 $30\%$ 的数据，$n \le 20$。
对于 $60\%$ 的数据，$n \le 1000$。
对于 $100\%$ 的数据，$5 \le n \le 10^6$，$0 \le w_i \le 10^6$。


title: 猜数

background: Iris 和 Beryl 两人在玩一个猜数的游戏。

description:
游戏是这样进行的：给定一个正整数 $n$，Iris 在 $S=\{1,2,...,n\}$ 中选择一个数 $m$。

然后，Iris 要如实回答 Beryl 的若干个问题，这些问题的形式是：“$m$ 是集合 $A$ 中的元素吗？”其中 $A\subseteq S$。
如果Iris回答“是”，则 Beryl 要给 Iris $a$ 元钱；否则，Beryl 要给 Iris $b$ 元钱。（数据保证 $a>b$）

那么，Beryl 至少准备多少钱，就一定能确定 Iris 心中的数字呢？

inputFormat:
第一行：两个正整数 $a$ 和 $b$ 以及数据组数 $t$。
接下来 $t$ 行，每行一个给定的正整数 $n$，意义如上所述。

outputFormat: $t$ 行，表示对于每一组数据，Beryl 需要准备的最小钱数。


title: [CEOI2015 Day1] 波将金的路径

description:
**译自 [CEOI2015](https://ceoi2015.fi.muni.cz/tasks.php) Day1 T1「[Potemkin cycle](https://ceoi2015.fi.muni.cz/day1/eng/day1task1-eng.pdf)」**

**简要题意** $\,$ 给一张无向图，$|V|=N,$ $|E|=R$。请找一条简单路径，设该路径的点集为 $V'$，要求：$|V'| \ge 4$，且 $V'$ 的导出子图只含该路径本身（也就是一条链）。

---

波将金公爵的领土可以视作一张无向图，他要求你找到一条路线，经过的结点以序列 $s_1,\dots,s_m$表示，且满足以下要求：

 - $m \geq 4$

- 经过的每个结点互不相同（即对于所有$i \neq j$满足$s_i \neq s_j$）

- 对于 $i = 1,\dots,m - 1$，满足 $s_i$ 与 $s_{i + 1}$ 直接连接，且 $s_m$ 与 $s_1$ 直接连接。

- 序列中的结点没有其他的边（即对于所有 $i < j$，使得 $j \neq i + 1$ 且 $i \neq 1$ 或者是 $j \neq m$，结点 $s_i$ 和 $s_j$ 之间没有边）。

inputFormat:
第一行，两个非负整数 $N$ 和 $R(0 \leq N \leq 1\ 000,0 \leq R \leq 100\ 000)$，分别表示结点的个数和道路的个数。

接下来 $R$ 行，其中第 $i$ 行包括两个不同的正整数 $a_i$ 和 $b_i(1 \leq a_i,b_i \leq N)$，表示结点 $a_i$ 与 $b_i$ 之间有一条边。

保证每两个结点最多有一条边连接。

outputFormat: 输出序列 $s_1,\dots,s_m$，表示问题描述的序列（如果有多解任意输出一个）。如果无解，输出`no`。


title: [CEOI2015 Day1] 卡尔文球锦标赛

description:
**译自 [CEOI2015](https://ceoi2015.fi.muni.cz/tasks.php) Day1 T2「[Calvinball championship](https://ceoi2015.fi.muni.cz/day1/eng/day1task2-eng.pdf)」**

一场卡尔文球比赛会有 $n$ 名选手参与，他们的编号分别为 $1\dots n$，分为若干个非空的球队。我们规定球队之间按照每个球队编号最小的选手的编号排序，并且以从 1 开始的连续整数编号。

举个栗子，譬如 1 号选手自己成一队，2, 3 和 5 号选手成一队，4 和 6 号选手成一队。

>\> $\ \texttt{1}$
>\> $\ \texttt{2 3 5}$
>\> $\ \texttt{4 6}$

那么 1 号选手的球队就是 1 号球队，2 号选手的球队就是 2 号球队，4 号选手的球队就是 3 号球队。

>\> $\ \texttt{1|1}$
>\> $\ \texttt{2|2 3 5}$
>\> $\ \texttt{3|4 6}$

每个人每天会选择不同的球队，我们可以在记录时省略选手的编号，仅记录每个位置对应选手所属球队编号的序列（上述例子为 `1 2 2 3 2 3`），因为每天的选手是一样的。当可能的选择方案全部被使用过后，锦标赛就结束了。

由于选择方案十分多，选择困难症患者纷纷表示力不从心。今年，我们决定根据记录的序列的字典序来选择方案。因此，第一天，所有人都在一个队 `1 1 1 1 1`；第二天，所有人都与 6 号针锋相对 `1 1 1 1 1 2`……在最后一天，所有人互相打响战争 `1 2 3 4 5 6`。

对于给定的球队记录，请你算出将会在未来的哪一天使用该记录。输出这个数字对 $1\ 000\ 007$ 取余的结果。

inputFormat:
第一行，一个正整数 $n(1 \leq n \leq 10\ 000)$。

第二行，$n$ 个以空格分隔的正整数，表示任务所给的球队记录。

outputFormat: 输出一个正整数，表示任务所给的球队记录将会被使用的天数对 $1\ 000\ 007$ 取余的结果。第一天的天数为 1。


title: [CEOI2015 Day2] 世界冰球锦标赛

description:
 **译自 [CEOI2015](https://ceoi2015.fi.muni.cz/tasks.php) Day2 T1「[Ice Hockey World Championship](https://ceoi2015.fi.muni.cz/day2/eng/day2task1-eng.pdf)」**

> 今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。

给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

inputFormat:
第一行，两个正整数 $N$ 和 $M(1 \leq N \leq 40,1 \leq M \leq 10^{18})$，表示比赛的个数和 Bobek 那家徒四壁的财产。

第二行，$N$ 个以空格分隔的正整数，均不超过 $10^{16}$，代表每场比赛门票的价格。

outputFormat: 输出一行，表示方案的个数。由于 $N$ 十分大，注意：答案 $\le 2^{40}$。


title: [CEOI2015 Day2] 核能国度

description:
核能国可以看作一个由 $W \times H$ 的方格组成的矩形。核能国有 $N$ 个核电站，每个核电站占用一个方格。不幸的是，核能国遭遇了百年一遇的特大地震，导致所有的核电站都发生了核泄漏。

每个核电站的核泄漏程度可以用两个整数 $a, b$ 来表示。如果位于 $P=[x_P,y_P]$ 的核电站爆炸，方格 $C=[x_C,y_C]$ 会增加 $\mathrm{max}(0,$ $a-b\times d(P,C))$ 贝克的辐射（贝克是单位），其中 $d(P,C)$ 是两个方格的切比雪夫距离，即 $d(P,C) =$ $\mathrm{max}(|x_P - x_C|,$ $|y_P - y_C|)$。

一个方格可能会受到多处核泄漏的影响。

例如，如果一个 $a = 7,$ $b = 3$ 的核电站爆炸了，所在的方格 $X$ 会受到 $7$ 贝克辐射（贝克是单位），满足 $d(X,Y) = 1$ 的 $8$ 个方格 $Y$ 会受到 $4$ 贝克辐射，满足 $d(X,Z) = 2$ 的 $16$ 个方格 $Z$ 会受到 $1$ 贝克辐射。

环保部门给了你 $Q$ 组询问，每组询问会划定核能国领土中的一个矩形，请回答：矩形区域内（每个方格）所受的平均辐射量为多少。

inputFormat:
第一行，两个正整数 $W$ 和 $H(W × H \leq 2.5×10^6)$，分别表示核能国的宽度与高度。

第二行，一个正整数 $N$，表示核电站的个数 $(1 \leq N \leq 2×10^5)$。

在接下来的 $N$ 行中，每行四个正整数 $x_i,y_i,a_i,b_i(1 \leq x_i \leq W,1 \leq y_i \leq H,1 \leq a_i,b_i \leq 10^9)$，表示有一个核电站位于方格 $[x_i,y_i]$，它的参数为 $a_i$ 与 $b_I$。每个格子最多有一个核电站。

第 $N+3$ 行，一个正整数 $Q$，表示询问的次数 $(1 \leq Q \leq 2×10^5)$。

在接下来的 $Q$ 行中，每行四个 正整数 $x_{1j},y_{1j},x_{2j},y_{2j}(1 \leq x_{1j} \leq x_{2j} \leq W,1 \leq y_{1j} \leq y_{2j} \leq H)$，表示该询问给出的矩形区域的左上角在 $[x_{1j},y_{1j}]$ 且它的右下角在 $[x_{2j},y_{2j}]$。

你可以假设核能国内的总辐射量少于 $2^{63}$。

outputFormat: 对于每个询问，输出一行表示给定矩形区域内所有方格的平均辐射量，四舍五入至整数。

hint:
以下为两次爆炸后对每个方格产生的辐射量：
```plain
7 6 3 2
4 6 5 2
1 3 3 2
```

 - $2^2$ 方形区域内的总辐射为 $14$，所以平均值为 $14\div 4=3.5$，四舍五入至 $4$。

 - 整个核能国的总辐射为 $44$，所以平均值为 $44\div 12 \approx 3.67$，四舍五入至 $4$。

 - 单个格子的平均辐射量就是它所受到的辐射量。

 - 最后一行的平均辐射量为 $9\div 4=2.25$，四舍五入至 $2$。

有 14 组测试数据。奇数的测试组只包含 $a$ 是 $b$ 的倍数的核电站。对每个子任务的进一步限制如下：

|测试组|进一步限制|分数|
|:-:|:-:|:-:|
|$1$|$H=1,N\cdot W \leq 10^8,Q \cdot W \leq 10^8$|$3$|
|$2$|$H=1,N\cdot W \leq 10^8,Q \cdot W \leq 10^8$|$2$|
|$3$|$N\cdot W \cdot H \leq 10^8,Q \cdot W \cdot H \leq 10^8$|$3$|
|$4$|$N\cdot W \cdot H \leq 10^8,Q \cdot W \cdot H \leq 10^8$|$2$|
|$5$|$H=1,N\cdot W \leq 10^8$|$6$|
|$6$|$H=1,N\cdot W \leq 10^8$|$4$|
|$7$|$N\cdot W \cdot H \leq 10^8$|$6$|
|$8$|$N\cdot W \cdot H \leq 10^8$|$4$|
|$9$|$H=1$|$15$|
|$10$|$H=1$|$10$|
|$11$|没有符合**界限**定义的爆炸事件|$15$|
|$12$|没有符合**界限**定义的爆炸事件|$10$|
|$13$|无|$12$|
|$14$|无|$8$|

如果核电站位于核能国的边境或是在离边境稍近的位置，那么爆炸可能也会影响到核能国之外的方格。影响到核能国外方格的爆炸被称作**界限**。


title: [CCO2015] 饥饿的狐狸

description:
**本题译自 [CCO 2015](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2015/index.html) Day1 T1「[Hungry Fox](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2015/stage%202/day1.pdf)」**

到你的宠物狐狸的晚餐时间啦！他的晚餐包含 $N$ 块饼干，第 $i$ 块饼干的温度是 $T_i$ 摄氏度。同时，在晚餐中还包含了一大盘 $W$ 摄氏度的水。

在喝了一口水之后，你的狐狸开始吃饭了。每当他吃一块饼干时，这块饼干的美味度为当前饼干与吃/喝的前一样食物（包括饼干和水）的温度的差的绝对值。它可以在任意时间喝水（保证水喝不完），或按任意顺序吃饼干。

最后狐狸获得的美味值为它吃下的每块饼干的美味度之和。请求出狐狸获得的最小和最大的美味值。

inputFormat:
第一行两个整数 $N,W$，表示饼干总数和水的温度。

接下来 $N$ 行，每行一个整数 $T_i(1\le i\le N)$ 表示第 $i$ 块饼干的温度。

outputFormat: 输出两个整数，分别为狐狸获得的最小和最大的美味值。

hint:
要得到最小美味值，一种可行的方案是，狐狸先喝水，然后吃第一块饼干，再吃第三块饼干，接着喝水，最后吃下第二块饼干，这样做，它所感受到的温度分别为 $20,18,18,20,25$ 摄氏度，总的美味度为 $2+0+5=7$。

要得到最大美味值，一种可行的方案是，狐狸先喝水，然后按顺序吃饼干，它所感受到的温度分别为 $20,18,25,18$ 摄氏度，总的美味度为 $2+7+7=16$。

对于 $30\%$ 及以上的数据， $W=0$；

对于 $100\%$ 的数据， $1\le N \le 100000, 0\le W \le 10^9, 0 \le T _ i \le 10 ^ 9$。


title: [CCO2015] 路短最

description:
**本题译自 [CCO 2015](https://cemc.math.uwaterloo.ca/contests/computing/2015/index.html) Day1 T2「[Artskjid](https://cemc.math.uwaterloo.ca/contests/computing/2015/stage%202/day1.pdf)」**

你可以通过许多的算法找到从一个地方到另外一个地方的最短路径。人们在他们的车上安装 GPS 设备然后他们的手机告诉他们最快的到达目的地的方式。然而，当在假期时，Troy 喜欢慢慢旅游。他想找最长的到目的地的路径以便他可以在路途中看许多新的以及有趣的地方。

因此，一个有效的路径包含一个不同城市的序列 $c_1,c_2,...,c_k$，并且对于每个 $1\le i<k$，有道路从 $c_i$ 通往 $c_{i+1}$。

他不想重复访问任何城市，请帮他找出最长路径。

inputFormat:
第一行输入包括两个整数 $n,m$，分别表示城市总数和连接城市间的道路数，两城市间至多有一条道路。城市编号从 $0$ 到 $n-1$，Troy 一开始在城市 $0$，城市 $n-1$ 是他的目的地。

接下来 $m$ 行每行三个整数 $s,d,l$，每个三元组表示这里有一条长为 $l$ 的从城市 $s$ 到城市 $d$ 的路。每条路都是有向的，只能从 $s$ 到 $d$，不能反向。保证有一条从城市 $0$ 到 $n-1$ 的路径。

outputFormat: 输出一个整数表示以城市 $0$ 为起点，以 $n-1$ 为终点的最长路径长度，并且其中不重复访问城市，路径长度是所经过的道路长度之和。

hint:
最短路为直接走城市 $0$ 至城市 $2$ 的道路，长度为 $5$ km。最长路为 $0$ 至 $1$ 至 $2$， 长度 $4+3=7$ km。

对于至少 $30\%$ 的数据，$n\le 8$；

对于 $100\%$ 的数据，有 $2\le n \le 18,$ $1\le m \le n^2-n,$ $0\le s,d \le n-1,$ $s\neq d,$ $1\le l\le 10000$。


title: [CCO2015] 太阳能飞行

background: **警告：滥用本题评测将被封号**

description:
**本题译自 [CCO 2015](https://cemc.math.uwaterloo.ca/contests/computing/2015/index.html) Day1 T3「[Solar Flight](https://cemc.math.uwaterloo.ca/contests/computing/2015/stage%202/day1.pdf)」**

航空的新纪元正在来临——第一个太阳能驱动的巨型喷气式飞机即将商用！然而，公众对前沿技术有一些在安全方面的焦虑，因为驱动飞机的阳光的光线可能会被其他在空中的物体挡住。因此，必须先进行一些统计和计算来规划第一次航行。

我们考虑一个包含 $N$ 个从一个城市到另外一个城市的航路组成的图。一架飞机可以被考虑成一个点。它穿过的天空可以被模型化为一个笛卡尔坐标系，其中 $X$ 轴表示从任意一个点向东出发的距离，$Y$ 轴表示高度。我们只考虑 $x$ 值的范围在 $[0,X]$，所有航路均为直线的部分。第 $i$ 架飞机从 $(0,A_i)$ 飞到 $(X,B_i)$。所有$A$值互不相同，对于$B$也如此。飞机以未知的，可能是非恒定的速度沿着航路行驶，所以任意时间点，飞机可能在航路的任意位置上。然而，已知的是飞机从不与其他飞机相撞，所以如果两个航道交错，两个飞机不会同时到达交点。

每个飞机 $i$ 同时也有一个干扰因素值 $C_i$，表示一个飞机影响它下面飞机太阳吸收能力的强弱。

各个飞机上的太阳能板非常奇怪，那些太阳能板只能收集飞机正上方的能量。这就意味着一个飞机能吸收的阳光可能会被其他与其的 $x$ 值相同，但是 $y$ 值比他大的飞机挡住。具体来说，太阳能板吸收的太阳光减少的值为挡住它的飞机的干扰因素值之和。

根据这些信息，以及一个距离常数 $K$，你要回答 $Q$ 个关于可能对太阳能板影响的询问。第 $i$ 个询问询问你在一个时刻飞机 $P_i$ 的太阳能板吸收的太阳光减少的值。在任意时刻飞机的 $x$ 值均在 $[S_i,S_i+K]$之间。

inputFormat:
第一行四个整数 $X,K,N,Q$，分别表示最大考虑的 $x$ 值，距离常数，航路总数，询问总数。

接下来 $N$ 行每行三个整数 $A_i,B_i,C_i(1\le i \le N)$，表示飞机 $i$ 初始 $y$ 值，终止 $y$值，干扰因素值。

接下来 $Q$ 行每行两个整数，$P_i, S_i(1\le i \le Q)$，表示根据 $P_i$ 和 $S_i$ 回答题目中的问题。

outputFormat: 输出 $Q$ 行，每行一个整数表示对于询问 $i(1\le i \le Q)$ 的回答。

hint:
飞机的航路示意图如下图所示。

![CCO2015D1T3Pic1](http://miao.su/images/2018/08/15/aaa7e400.png)

询问 $1$ 是对于 $2$ 号飞机在 $[1,5]$ 范围内所提出的询问，当飞机在 $x\le 4$ 时可能会被飞机 $3$ 挡住，但是绝不是飞机 $1$。然而，但是当它的 $x>4$ 时可能会被其他所有飞机挡住，因此，该询问的答案即其他所有飞机的影响因素值之和，为 $5+6=11$。

对于询问 $2$，当 $x<10$ 时飞机 $1$ 可能会被飞机 $3$ 挡住，并且当 $x\geq10$ 时不会被任何飞机盖住，因此只可能被飞机 $3$ 影响，即结果等于飞机 $3$ 的影响因素值 $6$。

对于询问 $3$，飞机 $1,2$ 都不能在飞机 $3$ 的正上方除非 $x$ 达到 $10$。所以该询问的答案为0。

对于 $40\%$ 的数据，$Q\le 1000$。

对于 $100\%$ 的数据，$1\le N\le 2000,$ $1\le K\le X,$ $1\le X,A_i,B_i,C_i\le 10^9,$ $0\le S_i\le X-K,$ $1\le Q \le 800000$。


title: [CCC2016] 生命中的圆

description:
**译自 [CCC2016](https://cemc.math.uwaterloo.ca/contests/computing/2016/index.html) Senior T5「[Circle of Life](https://cemc.math.uwaterloo.ca/contests/computing/2016/stage%201/seniorEn.pdf)」**

> 也许你听说过康威生命游戏（Conway's Game of Life）。康威生命游戏适用于方格组成的矩阵。但它可以产生十分复杂的结构。在这道题目中，我们将使用简化版的生命游戏来虐你。

这个游戏是 0 人游戏，换句话说，只要给定初始条件，这个游戏就能自己进行下去。

将一个圆环分为 $N$ 段，将这 $N$ 段顺时针依次编为 $1,\dots,N$ 号。每一段要么是活的（以 `1` 表示），要么是死的（以 `0` 表示）。

游戏会进行 $T$ 轮「变化」。如果一个方格**恰好**有一个相邻的方格在这次变化中存活，那么该方格会在下次变化中存活。否则，该方格会死亡。

给定圆环的初始状态，求经过 $T$ 次变化之后的状态。

inputFormat:
第一行，两个整数 $N$ 和 $T(3 \le N \le 100\ 000;1 \le T \le 10^{15})$。

第二行，一个长度为 $N$ 的字符串，表示 $N$ 个方格的初始状态。保证每个字符只有 `0` 或 `1` 两种可能。第 $i$ 位表示编号为 $i$ 的方格的初始状态。

outputFormat: 输出一个长度为 $N$ 的字符串，表示最终的状态。格式同输入。

hint:
#### 样例解释 1
方格 $1$ 和 $N - 1$ 和 $N$ 相邻，因此在一次变化后仍存活。

#### 样例解释 2
一次变化后，状态为 ` 00011`。

两次变化后，状态为 ` 10111`。

对于 $\frac{1}{15}$ 的数据，$N \le 15,T \le 15$。

对于另外的 $\frac{6}{15}$ 的数据，$N \le 15$。

对于另外的 $\frac{4}{15}$ 的数据，$N \le 4000,T \le 10\ 000\ 000$。

注意对于所有的数据，你需要使用 64 位整数。


title: [CCC2016] 合并饭团

description:
**译自 [CCC2016](https://cemc.math.uwaterloo.ca/contests/computing/2016/index.html) Senior T4「[Combining Riceballs](https://cemc.math.uwaterloo.ca/contests/computing/2016/stage%201/seniorEn.pdf)」**

Alphonse 有 $N$ 个美味的饭团，它们大小不一，摆放成一行。他想把最大的饭团让给自己的基友。他可以执行以下操作：

 - 如果两个**相邻的**饭团大小相同，Alphonse 可以把它们合并成一个新的饭团。新饭团的大小是两个原饭团大小之和。它将占据两个原饭团先前占据的位置。

 - 如果两个饭团大小相同，且它们之间只有一个饭团，Alphonse 也可以把它们合并成一个新的饭团。（中间的饭团大小没有规定。）新饭团的大小是三个原饭团大小之和，并占据三个原饭团先前的位置。

Alphonse 可以按照他的意愿执行任意次操作。

在执行 0 或更多次操作后，确定他应该把哪个饭团让给基友。

inputFormat:
第一行，一个整数 $N(1 \le N \le 400)$。

第二行，$N$ 个以空格分隔的整数，表示每个饭团的大小，按照从左到右的顺序给出。每个整数的上界为 $1\ 000\ 000$。

outputFormat: 输出 Alphonse 可以得到的最大的饭团大小。

hint:
#### 样例解释 1
有一种可能的合并方案为：合并大小同为 $12$ 的两个饭团，得到一个大小为 $24$ 的饭团。然后合并大小同为 $9$ 的两个饭团，得到一个大小为 $18$。接着合并大小为 $3,18$ 和 $3$ 的三个饭团，得到一个大小为 $24$ 的饭团。最后合并大小同为 $24$ 的两个饭团，得到一个大小为 $48$ 的饭团。

#### 样例解释 2
我们无法进行操作，所以答案为 $3$。

对于 $\frac1{15}$ 的数据，$N = 4$。

对于另外 $\frac2{15}$ 的数据，$N \le 10$。

对于另外 $\frac5{15}$ 的数据，$N \le 50$。


title: Roy&October之取石子II

background: Roy 和 October 两人在玩另一个取石子的游戏。（第一季请看 P4018）

description:
游戏规则是这样的：共有 $n$ 个石子，两人每次都只能取 $p^k$ 个（$p$ 为质数，$k=0$ 或 $1$，且 $p^k$ 小于等于当前剩余石子数），谁取走最后一个石子，谁就赢了。

现在 October 先取，问她有没有必胜策略。

若她有必胜策略，输出一行 `October wins!` ；否则输出一行 `Roy wins!`。

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

第 $2$ 行到第 $T+1$ 行，一行一个正整数 $n$，表示石子个数。

outputFormat: $T$ 行，每行分别为 `October wins!` 或 `Roy wins!`。

samples:
October wins!
October wins!
October wins!

hint:
对于 $30\%$ 的数据，$1 \le n \le 30$；

对于 $60\%$ 的数据，$1 \le n \le 10^6$；

对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^7，1 \le T \le 10^5$。

花絮：由于出题人懒得造数据，就把 P4018 的输入直接拿来了 ovo


title: 【模板】树同构（[BJOI2015]树的同构）

description:
树是一种很常见的数据结构。

我们把 $N$ 个点，$N-1$ 条边的连通无向图称为树。

若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。

对于两个树 $T_1$ 和 $T_2$，如果能够把树 $T_1$ 的所有点重新标号，使得树 $T_1$ 和树 $T_2$ 完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态。

现在，给你 $M$ 个无根树，请你把它们按同构关系分成若干个等价类。

inputFormat:
第一行，一个整数 $M$。

接下来 $M$ 行，每行包含若干个整数，表示一个树。第一个整数 $N$表示点数。接下来 $N$ 个整数，依次表示编号为 $1$ 到 $N$ 的每个点的父亲结点的编号。根节点父亲结点编号为 $0$。

outputFormat: 输出 $M$ 行，每行一个整数，表示与每个树同构的树的最小编号。

hint:
编号为 $1, 2, 4$ 的树是同构的。编号为 $3$ 的树只与它自身同构。

对于 $100\%$ 的数据，$1\leq N,M\leq 50$。


title: [CCC2017] 最小费用流

description:
 **译自 [CCC2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/index.html) Senior T4「[Minimum Cost Flow](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%201/seniorEF.pdf)」**

Watermoo 中有编号为 $1,2,\dots,N$ 的建筑物。其中还有 $M$ 条管道将建筑物两两连接。由于城市规划的疏漏，$1$ 号建筑是全市唯一的污水处理厂。每条管道可能是*活动的*或是*非活动的*。如果建筑 $1$ 通过活动管道直接或是间接地与其他每个建筑连通，则称活动管道集是一个有效的方案。（每条管道将两个建筑直接连接。如果建筑 $X$ 直接或间接连接建筑 $Y$，且建筑 $Y$ 直接或间接连接建筑 $Z$，那么我们说 $X$ 和 $Z$ 间接连接。）

Watermoo 的市政府正在使用一个 $N-1$ 条管道组成的显然有效的方案，但是这使得政府已经透支很多经费了！每条管道都有各自的月维修费，这是在其活动时必须支付的，一个有效方案的总成本为所有有效管道的维修费的总和。（非活动的管道不花费一分钱。）

此外，一个好消息是：Watermoo 大学的研究人员开发出了一种不完善的管道推进器，你可以在一条管道上使用它。它将从 $C$ 到 $\mathrm{max}(0,C-D)$ 降低该管道的维修成本，$D$ 为该推进器的强度。

市政府希望将成本降到最低，同时也希望你能尽快完成这个任务。每天，城市会允许你激活一条管道并关闭另一条管道。问：你需要多少天才能使一组活动管道形成一个有效方案并使其在所有有效方案和推进方案中费用最小？

请注意，在你规划的过程中方案可能会无效，但是到最后，他应该是一个有效的方案。

inputFormat:
第一行，三个整数 $N,M$ 和 $D(1 \le N \le 100\ 000,N - 1 \le M \le 200\ 000,0 \le D \le 10^9)$。

接下来 $M$ 行，每行三个整数 $A_i,B_i$ 和 $C_i$，表示有一条月维修成本为 $C_i$ 的管道从建筑 $A_i$ 连接到建筑 $B_i(1 \le A_i,B_i \le N,1 \le C_i \le 10^9)$。

前 $N-1$ 行表示 Watermoo 正在使用的有效方案。

保证数据没有重边和自环。

outputFormat: 输出一行，一个整数，表示完成任务的最小天数。如果初始方案即最优方案，输出`0`。

hint:
#### 样例解释 1
因为 $D=0$，所以管道推进器一无是处。

第一天，你应当关闭建筑 $2$ 到 $3$ 的管道并激活建筑 $4$ 到 $1$ 的管道。

#### 样例解释 2
一个可行的解为：首先在连接建筑 $1,2$ 的管道上安装推进器，使成本降低到 $3$。第一天，以连接 $1,3$ 的管道替换连接 $2,3$ 的管道。第二天，以连接 $1,5$ 的管道替换连接 $1,4$ 的管道。

此外，在连接 $1,3$ 或连接 $1,5$ 的管道上安装推进器毫无意义。这样做将会使得该管道的维修成本为 $0$，最优的费用为 $11$ （如你所见，我们已经找到了费用为 $10$ 的方案）。

#### 样例解释 3
初始的方案即最优方案。请注意整数上溢。

对于 $\frac3{15}$ 的数据，$N \le 8,M \le 28,D=0$。

对于另外 $\frac5{15}$ 的数据，$N \le 1\ 000,M \le 5\ 000,D=0$。

对于另外 $\frac3{15}$ 的数据，$D=0$。

对于另外 $\frac2{15}$ 的数据，$N \le 1\ 000,M \le 5\ 000$。


title: [CCC2017] 地铁交通

background: **滥用本题评测将被封号**

description:
 **译自 [CCC2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/index.html) Senior T5「[RMT](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%201/seniorEF.pdf)」**

RMT 地铁交通运行着一个不寻常的地铁系统。有 $N$ 个地铁站，从 $1$ 到 $N$ 编号。有 $M$ 条地铁线路，从 $1$ 到 $M$ 编号，每个地铁站只属于一条线路且每条线路至少经过一个地铁站。整个地铁网络呈圆形。也就是说，如果有一个编号为 $S$ 的地铁站，那么与它同一线路的下一个地铁站是下一个编号比它大的地铁站。除非 $S$ 是同线路中编号最大的地铁站，在这种情况下，它的下一个地铁站是同一线路中编号最小的地铁站。

RMT 正在以志愿者对他们的系统进行负载测试。测试从每一站以一列地铁列车开始，且对于每一个 $i$，会有 $A_i$ 个志愿者在第 $i$ 站的测试列车上。在整个测试期间，志愿者不会离开对应的列车。

测试过程中，RMT 会进行 $Q$ 个操作，每个操作只有两种可能：一种是询问第 $l$ 站到第 $r$ 站地铁上的志愿者人数；或是在线路 $x$ 运行所有的地铁。当有一列地铁在 $x$ 线路运行，它会前往线路中的下一站。

你是 RMT 的铁杆骨灰级粉丝，所以你自愿协助他们进行操作并告诉他们操作的结果。

inputFormat:
第一行，三个整数，$N,M$ 和 $Q(1 \le M \le N \le 150\ 000;1 \le Q \le 150\ 000)$。

第二行，$N$ 个整数 $L_1,L_2,\dots,L_N$，表示每个地铁站所属线路的编号。

第三行，$N$ 个整数 $A_1,A_2,\dots,A_N$，表示每个地铁站起始时刻的志愿者人数。

以下 $Q$ 行，每行只有以下其中一种形态：

 - `1 l r`，表示一个询问 $(1 \le l \le r \le N)$。

 -  `2 x`，表示 RMT 会在 $x$ 线路运行 $(1 \le x \le M)$。

outputFormat: 对于每个询问，输出一行，表示询问的答案。

hint:
### 样例解释 1
地铁系统如下图所示，地铁站编号为 $1$ 到 $5$，由编号为 $1$ 或 $2$ 的线路连接：

![](https://i.loli.net/2018/08/16/5b74e41916341.png)

开始时，每个地铁站的志愿者人数为 $\{1,2,3,4,5\}$。

第一个询问的答案为 $1+2+3+4+5=15$。

线路 $1$ 被运行之后，每个地铁站的志愿者人数为 $\{3,2,1,4,5\}$。

第二个询问的答案为 $1+4+5=10$。

线路 $2$ 被运行之后，每个地铁站的志愿者人数为 $\{3,5,1,2,4\}$。

第三个询问的答案为 $3+5+1=9$。

#### 样例解释 2
地铁系统如下图所示，地铁站编号为 $1$ 到 $3$，只有线路 $1$ 连接：

![](https://i.loli.net/2018/08/16/5b74e56617ad0.png)

第一次询问之前，每个地铁站的志愿者人数为 $\{114,101,109\}$。

第二次询问之前，每个地铁站的志愿者人数为 $\{109,114,101\}$。

第三次询问之前，每个地铁站的志愿者人数为 $\{101,109,114\}$。

第四次询问之前，每个地铁站的志愿者人数为 $\{114,101,109\}$。

对于 $\frac2{15}$ 的数据，$N \le 1\ 000,Q \le 1\ 000$。

对于另外 $\frac2{15}$ 的数据，$L_i \le L{i+1}(1 \le i < N)$。

对于另外 $\frac3{15}$ 的数据，$M \le 200$。

对于另外 $\frac3{15}$ 的数据，每条线路的地铁数量都不超过 $200$。


title: [CCC2018] 平衡树

description:
**题目译自 [CCC 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018/) S4「[Balanced Trees](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%201/seniorEF.pdf)」**

我们定义「完美平衡树」如下：

每棵完美平衡树都有一个正整数权值。权值为 $1$  的完美平衡树为只含有 $1$  个节点的树。否则，这棵树的权值为 $w(w\ge2)$，则这棵树为一棵含有 $k(2\le k\le w)$ 棵子树的有根树。所有的 $k$ 棵子树都必须是相同的，且它的所有 $k$ 棵子树必须完全相同，且自身是完美平衡的。

特别地，所有 $k$ 棵子树权值必须相同。它们的权值必须为 $\left\lfloor\frac{w}{k}\right\rfloor$ 。例如，如果一棵权值为 $8$ 的完美平衡树有 $3$ 棵子树，那么每棵子树的权值为 $2$，因为 $2+2+2=6\le8$。

给定 $N$，求出权值为 $N$ 的完美平衡树的数量。

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

outputFormat: 输出一个整数表示权值为 $N$ 的完美平衡树的数量。

hint:
#### 样例解释 1

合法的树如下：

 - 一棵以有 $4$ 棵权值为 $1$ 的子树为根的完美平衡树；
 - 一棵以有 $2$ 棵权值为 $2$ 的子树为根的完美平衡树；
 - 一棵以有 $3$ 棵权值为 $1$ 的子树为根的完美平衡树。

对于 $33\%$ 的数据，$N\le1000$；
对于另外 $13\%$ 的数据，$N\le5\times 10^4$；
对于另外 $13\%$ 的数据，$N\le10^6$；
对于全部的数据，$1\le N\le10^9$。


title: [CCC2018] 最大战略储备

description:
**题目译自 [CCC 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018/) S5「[Maximum Strategic Savings](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%201/seniorEF.pdf)」**

有 $N$ 个星球，编号为 $1\ldots N$。每个星球有 $M$ 座城市，编号为 $1\ldots M$。我们将 $e$ 星球上的城市 $f$ 记作 $(e,\,f)$。

有 $N\times P$ 条双向航线，对于每个星球 $e(1\le e\le N)$，有 $P$ 条航线，编号为 $1$ 到 $P$。第 $i$ 条航线连接城市 $(e,\,a_i)$ 和 $(e,\,b_i)$，且每天需要花费 $c_i$ 的代价维护。

有 $M\times Q$ 个双向港口。对于所有编号为 $f(1\le f\le M)$ 的城市，有 $Q$ 个港口，编号为 $1$ 到 $Q$。第 $j$ 个港口可以连接城市 $(x_j,\,f)$ 和 $(y_j,\,f)$，且每天需要花费 $z_j$ 的代价维护。

现在需要拆除一些港口和（或）取消一些航线，使得城市之间仍能保持联通，且节省的代价之和最大。

inputFormat:
第一行四个整数，分别为 $N,\,M,\,P,\,Q\ (0\le N,\,M,\,P,\,Q\le10^5)$。

接下来 $P$ 行，每行三个整数 $a_i,\,b_i,\,c_i(1\le a_i,\,b_i\le M,\,1\le c_i\le10^8)$。

再接下来 $Q$ 行，每行三个整数 $x_j,\,y_j,\,z_j(1\le x_j,\,y_j\le N,\,1\le z_j\le 10^8)$。

数据保证城市之间两两联通，可能有重边或自环。

outputFormat: 输出一行一个整数表示每天最多能节省的代价之和。


title: [COCI2014-2015#3] STOGOVI

description:
 **译自 [COCI 2014/2015 Contest 3](http://www.hsin.hr/coci/archive/2014_2015/) T5「STOGOVI」**

Mirko 正在玩栈。游戏开始时，他有一个编号为 $0$ 的空栈。在游戏中的第 $i$ 步，他会选择一个存在的编号为 $v$ 的栈，将它复制一份并进行以下其中一种操作：

 1. 将数字 $i$ 加入新栈的顶部。

 2. 将新栈顶部的数字删除。

 3. 选择另外一个编号为 $w$ 的栈，并统计有多少个不同的数同时存在于新栈与栈 $w$ 中。

新创建的栈编号为 $i$。

Mirko 不喜欢自己用栈模拟这个过程，所以他想要你替他写一个程序来执行这个过程。对于每个删除操作输出删除的数，且对于每个统计操作，输出统计的结果。

inputFormat:
第一行，一个整数 $N(1 \le N \le 300\ 000)$，表示这局游戏的步数。

游戏的步骤以时间顺序按前 $N$ 个整数编号。

以下 $N$ 行，第 $i$ 行表示游戏的第 $i$ 步，为以下三种格式之一：

 - `a v`，表示加入操作。

 - `b v`，表示删除操作。

 - `c v w`，表示统计操作。

操作所涉及的编号一定在 $[0,i-1]$ 中。

保证删除操作不会操作空栈。

outputFormat: 对于每个删除或统计操作，输出一行，表示请求的数字。按照输入文件给出的操作顺序排列。

hint:
#### 样例解释 1

开始时，我们有栈 $S_0 = \{\}$。

第一步，我们复制 $S_0$ 并将数字 $1$ 加入到顶部，$S_1 = \{1\}$。

第二步，我们复制 $S_1$ 并将数字 $2$ 加入到顶部，$S_2 = \{1,2\}$。

第三步，我们复制 $S_2$ 并删除数字，$2$，$S_3 = \{1\}$。

第四步，我们复制 $S_2$ 并编号为 $S_4$，统计有多少个不同的数同时存在于 $S_4$ 与 $S_3$ 中。唯一同时存在于两个栈中的数是 $1$，所以答案为 $1$。

第五步，我们复制 $S_4$ 并删除数字，$2$，$S_5 = \{1\}$。


title: [COCI2014-2015#3] KAMIONI

description:
 **译自 [COCI 2014/2015 Contest 3](http://www.hsin.hr/coci/archive/2014_2015/) T6「KAMIONI」**

有一条马路，我们将其视为一条数轴。马路上有 $N$ 辆卡车，开始时，卡车都在整点上。所有卡车一起开始移动，并且都以**同样的速率**移动。**没有卡车保持静止**。每辆卡车花 $1$ 分钟可以移动 $1$ 个单位距离。

给出每辆卡车的「路线」。路线用一个含有 $k$ 个元素的数组 $A_1,A_2,\dots,A_k$ 表示。该卡车首先 $A_1$ 开往 $A_2$，然后立即掉头开往 $A_3$，以此类推。忽略掉头的耗时。考虑到卡车会掉头，我们保证：

$$A_1 < A_2 > A_3 < A_4 > \dots\ \mathrm{or}\ A_1 > A_2 < A_3 > A_4 < \dots$$

一条可能的路线为 $2→5→1→7$（给出的点要么是起点，要么是终点，要么就是掉头的位置）。开始时卡车位于 $2$，出发 $3$ 分钟后到达位置 $5$，接着掉头。卡车继续行驶到位置 $1$ ，此时距出发已过去了 $7$ 分钟。卡车再次掉头，并行驶到位置 $7$，此时距出发已经经过了 $13$ 分钟。

当卡车到达路线终点后，会有神秘的 ~~Planet6174~~ 外星人出现并把它带回飞船。

给出这 $N$ 辆卡车的路线。现在有 $M$ 组询问，每组询问包含两辆卡车。对于每组询问，请回答这对卡车出现在同一位置的次数。位置不一定是整数，比如它们可以在位置 $2.5$ 相遇。

请注意，保证每一对**询问的**（而不是随便一对）卡车：

 - 其中一个被 ~~Planet6174~~ 外星人带走的时候，它们不会在同一位置。
 - 它们不会在初始时刻或是其中一个转弯的时候在同一位置。

> Planet6174：翻译这道题目的人已经被解决掉了（滑稽

inputFormat:
第一行，两个整数 $N$ 和 $M(1 \le N \le 10^5,1 \le M \le 10^5)$，表示卡车的数量和询问的卡车的对数。

以下 $N$ 行，其中第 $i$ 行表示第 $i$ 辆卡车的路线。
每行第一个整数 $K_i(1 \le K_i \le 3 \cdot 10^5)$ 表示路线的长度。紧接着是 $K_i$ 个整数 $A_j(1 \le A_j \le 10^9)$，表示卡车 $i$ 路线上的点。给出的点要么是起点，要么是终点，要么就是掉头的位置。
所有卡车移动的总路程之和不会超过 $3 \cdot 10 ^5$。

以下 $M$ 行，其中第 $i$ 行包含两个整数 $(a_i,b_i)$，表示第 $i$ 个询问的两辆卡车。

outputFormat: 输出 $M$ 行，第 $i$ 行包含我们询问的第 $i$ 对卡车相遇的次数。


title: [COCI 2014-2015#3] COCI

description:
 **译自 [COCI 2014/2015 Contest 3](http://www.hsin.hr/coci/archive/2014_2015/) T4「COCI」**

第三轮 COCI 来了！为了估分，我们猜测：如果选手 $\mathrm{A}$ 在前两轮比赛中分数都高于选手 $\mathrm{B}$，那么选手 $\mathrm{A}$ 第三轮的分数与选手 $\mathrm{B}$ 的分数**至少相等**。

在每轮比赛中（包括这一场）选手至少会为 $0$ 分，至多会得到 $650$ 分。在**总排行榜**中，选手们将会按照**三轮比赛的总得分**降序排列。如果有两名选手分数相同则排名相同，下一名分数更小的选手排名后移。
比如有 $5$ 名选手，总得分分别为 $1000,1000,900,900$ 和 $800$，那么对应的排名为 $\text{No.}\ 1,$ $\text{No.}\ 1,$ $\text{No.}\ 3,$ $\text{No.}\ 3$ 和 $\text{No.}\ 5$。

对于 $N$ 名选手中的每一名选手，我们知道他们的第一轮和第二轮得分。基于上述假设，请确定每名选手在经过三轮 COCI 之后可以获得的最高名次和最低名次。

inputFormat:
第一行，一个整数 $N(1 \le N \le 5\times 10^5)$，表示选手的个数。

以下 $N$ 行，每行两个整数，在 $[0,650]$ 范围内，表示每个选手第一场和第二场比赛的得分。

outputFormat: 对于每个选手，输出一行，两个整数，分别为他可能得到的最高名次和最低名次。

hint: $1 \le N \le 5\times 10^5$，所有的选手分数均在 $[0,650]$ 范围内。


title: 帕秋莉的手环

background:
帕秋莉是蕾米莉亚很早结识的朋友，现在住在红魔馆地下的大图书馆里。不仅擅长许多魔法，还每天都会开发出新的魔法。只是身体比较弱，因为哮喘，会在咏唱符卡时遇到麻烦。

她所用的属性魔法，主要是生命和觉醒的“木”，变化和活动的“火”，基础和不动的“土”，果实和丰收的“金”，寂静和净化的“水”，机动和攻击的“日”，被动和防御的“月”七种属性

没有窗户的图书馆或许充满了灰尘，不过她认为在书旁边才是自己，所以她不能从书的旁边离开。这样已经一百年了。

description:
经过数年魔法的沉淀，帕秋莉将她那浩瀚无边的魔法的一部分浓缩到了一些特质的珠子中。

由于帕秋莉爱好和平，她只把象征生命和觉醒的木属性魔法和果实和丰收的金属性魔法放入了珠子中。

她认为光要这些珠子没有什么用处，于是她想将这些珠子串成魔法手环，这样就好看多了。于是，她拿出来用来串这些珠子的线 - 雾雨灵径。

她将这些珠子串到一起之后发现了一些性质：一段雾雨灵径的颜色是由两边的珠子的属性决定的，当一段雾雨灵径连接的两个珠子中只要有一个是金属性的，那么这段雾雨灵径的颜色就为金色

帕秋莉想要一个全都是金色的手环，而且她还想知道一共有多少种方案。由于她还要研究新的魔法，她就把这件事交给了你。由于她的魔法浩瀚无边，她有无穷的珠子

她并不想看着好几十位的数字，于是你需要对 $1000000007$ 进行取模

inputFormat:
输入包含多组数据

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

之后每组数据有一个 $n$ 代表木属性珠子和金属性珠子的总个数

outputFormat: 对于每组数据，输出取模后的方案数


title: [USACO15DEC] High Card Low Card G

description:
Bessie the cow is a huge fan of card games, which is quite surprising, given her lack of opposable thumbs. Unfortunately, none of the other cows in the herd are good opponents. They are so bad, in fact, that they always play in a completely predictable fashion! Nonetheless, it can still be a challenge for Bessie to figure out how to win.

Bessie and her friend Elsie are currently playing a simple card game where they take a deck of $2N$ cards, conveniently numbered $1…2N$, and divide them into $N$ cards for Bessie and $N$ cards for Elsie. The two then play $N$ rounds, where in each round Bessie and Elsie both play a single card. In the first $N/2$ rounds, the player with the highest card earns a point, and in the last $N/2$ rounds, the rules switch and the player who plays the lowest card wins a point.

Given that Bessie can predict the order in which Elsie will play her cards, please determine the maximum number of points Bessie can win.

inputFormat:
The first line of input contains the value of $N$ ($2 ≤ N ≤ 50,000$; N will be even).

The next $N$ lines contain the cards that Elsie will play in each of the successive rounds of the game. Note that it is easy to determine Bessie's cards from this information.

outputFormat: Output a single line giving the maximum number of points Bessie can score.

translation:
有  $2N$  张牌，它们的点数分别为  $1$  到  $2N$ 。Bessie 拿了其中的  $N$  张，Elsie 拿了剩下的  $N$  张。
Bessie 和 Elsie 会进行  $N$  轮游戏，在每轮游戏中，Bessie 和 Elsie 各出一张牌。出了的牌不能收回。
在前  $N/2$  轮中，谁的牌点数大谁就赢；在后  $N/2$  轮中，谁的牌点数小谁就赢。
已知 Elsie 每一轮会出什么牌，试求 Bessie 最多能赢多少轮。
 $2≤N≤50000,$  保证  $N$  是偶数。

Translated by @Planet6174

hint:
Here, Bessie must have cards 2, 5, and 6, and 7 in her hand, and she can use these to win at most 2 points, by saving her '2' card until one of the hands in the second half of the game.

Problem credits: Brian Dean


title: [USACO15DEC] Fruit Feast G

description:
Bessie has broken into Farmer John's house again! She has discovered a pile of lemons and a pile of oranges in the kitchen (effectively an unlimited number of each), and she is determined to eat as much as possible.

Bessie has a maximum fullness of $T$ $(1 ≤ T ≤ 5,000,000)$. Eating an orange increases her fullness by $A$, and eating a lemon increases her fullness by $B$ ($1 ≤ A,B ≤ T$). Additionally, if she wants, Bessie can drink water at most one time, which will instantly decrease her fullness by half (and will round down).

Help Bessie determine the maximum fullness she can achieve!

inputFormat: The first (and only) line has three integers $T$, $A$, and $B$.

outputFormat: A single integer, representing the maximum fullness Bessie can achieve.

translation:
现在Bessie的饱食度为 $0$ ，她每吃一个橙子，饱食度就会增加 $A$ ；每吃一个柠檬，饱食度就会增加 $B$ 。Bessie还有一次喝水的机会，如果Bessie喝水前饱食度为 $x$ ，喝水后饱食度会变为 $\left\lfloor\dfrac{x}{2}\right\rfloor$ 。
Bessie的饱食度不能超过 $T$ ，否则肚子会爆炸。试求Bessie的饱食度最大能达到多少。

Translated by @Planet6174

hint: Problem credits: Nathan Pinsker


title: [USACO15DEC] Bessie's Dream G

description:
After eating too much fruit in Farmer John's kitchen, Bessie the cow is getting some very strange dreams! In her most recent dream, she is trapped in a maze in the shape of an $N×M$ grid of tiles $(1≤N,M≤1,000)$. She starts on the top-left tile and wants to get to the bottom-right tile. When she is standing on a tile, she can potentially move to the adjacent tiles in any of the four cardinal directions.

But wait! Each tile has a color, and each color has a different property! Bessie's head hurts just thinking about it:

- If a tile is **red**, then it is impassable.

- If a tile is **pink**, then it can be walked on normally.

- If a tile is **orange**, then it can be walked on normally, but will make Bessie smell like oranges.

- If a tile is **blue**, then it contains piranhas that will only let Bessie pass if she smells like oranges.

- If a tile is **purple**, then Bessie will slide to the next tile in that direction (unless she is unable to cross it). If this tile is also a purple tile, then Bessie will continue to slide until she lands on a non-purple tile or hits an impassable tile. Sliding through a tile counts as a move. **Purple tiles will also remove Bessie's smell.**

(If you're confused about purple tiles, the example will illustrate their use.)

Please help Bessie get from the top-left to the bottom-right in as few moves as possible.

inputFormat:
 The first line has two integers $N$ and $M$, representing the number of rows and columns of the maze.

The next $N$ lines have $M$ integers each, representing the maze:

- The integer '0' is a red tile

- The integer '1' is a pink tile

- The integer '2' is an orange tile

- The integer '3' is a blue tile

- The integer '4' is a purple tile

The top-left and bottom-right integers will always be '1'.

outputFormat: A single integer, representing the minimum number of moves Bessie must use to cross the maze, or -1 if it is impossible to do so.

translation:
有一个 $N\times M$ 的棋盘，Bessie 开始时在左上角的格子，她要移动到右下角的格子上。当 Bessie 位于一个格子上时，她只能移动到与之有公共边的相邻格子。棋盘上的格子按照颜色可分为红、粉、橙、绿、紫五类。

- 红色格子：不能通过。
- 粉色格子：可以自由通过。
- 橙色格子：可以自由通过，但 Bessie 通过橙色格子后会沾上橙子味。
- 绿色格子：当且仅当 Bessie 身上有橙子味时，Bessie才能通过绿色格子。
- 紫色格子：Bessie 会在上面漂移（除非她漂移的方向上有一个不能通过的格子），并且 Bessie 身上的橙子味会消失。举个例子，如果 Bessie 从紫色格子左边的格子移动到紫色格子上，
 * 如果右边是粉/橙色格子：Bessie 会滑到右边。
 * 如果右边是红/绿色格子，或者右边是边界：Bessie 会停在当前紫色格子上。
 * 如果右边仍然是紫色格子：Bessie 会滑到右边，然后继续根据这一规定来漂移。

请问 Bessie 最少需要移动多少步。

Translated by @Planet6174

hint:
In this example, Bessie walks one square down and two squares to the right (and then slides one more square to the right). She walks one square up, one square left, and one square down (sliding two more squares down) and finishes by walking one more square right. This is a total of 10 moves (DRRRULDDDR).

Problem credits: Nathan Pinsker, inspired by the game "Undertale".


title: [CCO2014] Troy 与三角形

description:
**本题译自 [CCO 2014](https://cemc.math.uwaterloo.ca/contests/computing/2014/index.html) Day1 T1「[Troyangles](https://cemc.math.uwaterloo.ca/contests/computing/2014/Stage%202/day1.pdf)」**

Troy 喜欢三角形，所以他也特别喜欢数三角形。他有一个由 `.` 和 `#` 组成的 $N\times N$ 的网格。帮他数数在网格中仅由 `#` 组成的三角的个数。三角形表示为如下形式：
```plain
          #
    #    ###
#, ###, #####, ...
```
更加形式化地说，一个高度为 $h$，有 $h$ 列的三角形，其中 $h$ 为正整数，第 $i$ 行有 $2i-1(1\le i \le h)$ 个 `#`，行在彼此上方居中，所以它们是关于它们的垂直中线对称的。

inputFormat: 第一行一个数 $N$ 表示网格大小，接下来 $N$ 行每行 $N$ 个字符表示这个网格。

outputFormat: 输出网格中的三角形个数。


title: [CCO2014] 国王格鲁夫

description:
**本题译自 [CCO 2014](https://cemc.math.uwaterloo.ca/contests/computing/2014/index.html) Day1 T2「[King Gruff](https://cemc.math.uwaterloo.ca/contests/computing/2014/Stage%202/day1.pdf)」**

狼国王格鲁夫统治着一个居住着可爱的狐狸的繁荣、快乐的领地。对狐狸们来说，不幸的是，他根本不是一个好国王，而且还想让他们的生活过得很惨。

他的国家有 $N$ 个城市，由 $M$ 条路连接，第 $i$ 条路可以让你从城市 $X_i$ 走到另一个城市 $Y_i$，并且只能往这个方向走，这条路的长度为 $L_i$，关闭费为 $C_i$，可能会有多条道路以相同的方向连接着两个相同的城市。

国王格鲁夫尤其不喜欢住在两个不同城市 $A$ 和 $B$ 里的狐狸并且想让他们从城市 $A$
 到城市 $B$ 很麻烦甚至根本行不通。具体来说，他将选择一个距离 $D$，并且同时关闭某些他王国里的路。关闭的条件是，如果这条路是城市 $A$ 到城市 $B$ 路径上的一部分且该路径总长不超过 $D$。对于每条这样的路，他将用皇家金库里的钱取支付它的关闭费。一个路径包含一个路的序列，除了第一条路外，每条路起点在前一条路的终点，并且可能多次访问同一个城市或走同一条路。

格鲁夫正在纠结选哪个 $D$，不管怎样，大一些的 $D$ 值可以使得他的狐狸子民更加不方便，但是可能花费他更多的钱！因此，他想了 $Q$ 个不同的值 $D_1,D_2,...,D_Q$，对于每一个值，他想知道需要花费多少来满足他的要求。因为你也不喜欢狐狸，你同意帮他写个程序计算最小花费。

inputFormat:
第一行包括四个由空格分隔的整数 $N,M,A,B$，城市数，道路数，开始城市，结束城市。

接下来 $M$ 行四个空格分隔的整数 $X_i,Y_i,L_i,C_i$，表示一条从 $X_i$ 到 $Y_i$ 的长为 $L_i$ 的路，它的关闭费为 $C_i$。

接下来一行一个数 $Q$，表示询问个数。

接下来 $Q$ 行包含一个数 $D_i$ 表示题中所述距离参数。

outputFormat: 输出包括 $Q$ 行，表示根据距离参数 $D_i(1\le i\le Q)$ 求出的关闭所有必要的路的总花费。

hint:
王国如下图所示，每条路只标注了长度。

![CCO2014D1T2Pic1](http://miao.su/images/2018/08/17/aaa51809.png)

如果 $D=8$，第一、三条路需要被关闭，他们都是从城市 $1$ 到 城市 $3$ 的长为 $7$ 的路径的一部分，总花费 $1+15=16$。

如果 $D=6$，不需要关闭任何路，因为没有从城市 $1$ 到城市 $3$ 的路长度小于或等于 $6$。

如果 $D=90$，前三条路都要被关闭。

如果 $D=94$，第四条路也要被关闭，因为它在城市 $1$ 到城市 $3$ 的路径上，该路径长度刚好为 $94$，路径为依次走第一、三、四、一、三条路。

王国如下图所示

![CCOD2T2Pic2](http://miao.su/images/2018/08/17/aaa81adf.png)

就像你所看到的一样，狐狸已经有麻烦了，因为这里根本没有从城市 $1$ 到城市 $2$ 的路径，因此对于任何 $D$ 格鲁夫国王都不需要关闭任何道路。

对于至多 $20\%$ 的数据，$1\le N\le 500$；

对于至多 $20\%$ 的数据，$Q=1$；

对于至多 $80\%$ 的数据，$1\le Q\le 20$；

对于 $100\%$ 的数据，$1\le X_i,Y_i,A,B\le N \le 10^5,$ $0\le M\le 10^5,$ $1\le L_i,C_i\le 10^4,$ $1\le Q\le 10^5,$ $1\le D\le 10^9$。


title: [CCO2014] 狼人游戏

description:
**本题译自 [CCO 2014](https://cemc.math.uwaterloo.ca/contests/computing/2014/index.html) Day1 T3「[Werewolf](https://cemc.math.uwaterloo.ca/contests/computing/2014/Stage%202/day1.pdf)」**

和往常一样，$N$ 个机器人在玩狼人游戏，机器人从 $1$ 到 $N$ 编号。$W$ 个机器人扮演狼人，剩下的扮演市民。虽然狼人游戏包括不同的角度，但我们将只着眼于其中一个角度。

机器人指控其他人是狼人并且防止其他机器人无辜地指控它。

狼人知道其他人的角色以及：

- 一个狼人从不指控其他狼人；

- 任何狼人机器人保护的都是其他狼人机器人。

市民可能会指控或保护任何类型的机器人。

其他的一些限制使得题目更简单：

- 没有机器人又被指控又被保护；

- 没有机器人被指控或保护一次以上；

- 如果有一个编号为 $A$ 机器人指控或保护编号为 $B$ 的机器人，那么我们保证$A<B$。

你将知道 $N$ 个机器人间的所有指控和保护关系，并且知道狼人数为 $W$。每个机器人所扮演的角色要么是狼人要么是市民。你的目标是计算出符合上述限制的角色安排方案数。

inputFormat:
第一行三个数 $N,W,M$，分别表示机器人数、狼人数、指控和保护关系数。

接下来 $M$ 行每行描述一个关系，接下来每行都是以下两个形式之一：
- `A a b`，表示机器人 $a$ 指控机器人 $b$ 是狼人。
- `D a b`，表示机器人 $a$ 保护机器人 $b$。

outputFormat: 输出满足以上条件的角色安排方案数量。可想而知，结果可能非常大，所以需要对 $10^9+7$ 取模。

hint:
#### 样例解释 1
如果机器人 $1$ 是狼人，机器人 $2$ 也必须是，那么狼人就太多了！唯一的可能是机器人 $2$ 是唯一的狼人。

#### 样例输出 2
没有额外的保护或指控信息的话，机器人 $1$ 和机器人 $2$ 都可能是狼人。

#### 样例解释 3
如果机器人 $1$ 是狼人，机器人 $2$ 将是市民，机器人 $3$ 也是狼人；或者机器人 $1$ 是市民，那么机器人 $2$ 和 $3$ 将是狼人。

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

对于 $100\%$ 的数据，$1\le N\le 200,$ $0\le W\le N,$ $0\le M<N$。


title: 不认识

background: 又是一年军训时，今年的军训有点不一样。小L和小K所在的班的同学来自五湖四海（才怪），原来互相都不认识。

description:
小K和小L的教官将同学们按随机顺序排成一列。教官发现所有同学互相之间竟然都不认识（小L和小K失忆了），于是教官决定让同学们互相认识一下。每次教官会令编号在闭区间$[l,r]$的所有同学两两互相认识。如果其中的一对同学在之前的操作中已经认识，那么他们不会再次认识。请问，在每次教官的操作（命令）之前，在教官指定的这个区间内有多少对同学是不认识的？

每对同学可以表示为$(u,v)[u<v]$。两对同学$(u_1,v_1)$和$(u_2,v_2)$不同当且仅当$u_1\neq u_2~or~v_1\neq v_2$。

inputFormat:
输入第一行为一个整数$n$和$q$，$n$表示小L和小K所在的班的学生数，$q$表示教官的操作数；

之后的$q$行，每行两个整数$l'$和$r'$，表示这次操作使得闭区间$[l',r']$的所有同学两两互相认识。

本题输入加密。输入的第三行至最后一行，输入的数字都按位异或（$\oplus$）了$lastans$，也就是上一个询问的输出。对于输入的第二行，你可以认为$lastans=0$。对于每个操作，你需要将$l',r'$通过某种方式解密得到真正的，即未加密过的$l,r$。

outputFormat: 输出共$q$行。每行对应输入中的一次操作，输出这次操作的答案。


title: [USACO15FEB] Censoring S

description:
Farmer John has purchased a subscription to Good Hooveskeeping magazine for his cows, so they have plenty of material to read while waiting around in the barn during milking sessions. Unfortunately, the latest issue contains a rather inappropriate article on how to cook the perfect steak, which FJ would rather his cows not see (clearly, the magazine is in need of better editorial oversight).

FJ has taken all of the text from the magazine to create the string $S$ of length at most 10^6 characters. From this, he would like to remove occurrences of a substring $T$ to censor the inappropriate content. To do this, Farmer John finds the **_first_** occurrence of $T$ in $S$ and deletes it. He then repeats the process again, deleting the first occurrence of $T$ again, continuing until there are no more occurrences of $T$ in $S$. Note that the deletion of one occurrence might create a new occurrence of $T$ that didn't exist before.

Please help FJ determine the final contents of $S$ after censoring is complete.

inputFormat: The first line will contain $S$. The second line will contain $T$. The length of $T$ will be at most that of $S$, and all characters of $S$ and $T$ will be lower-case alphabet characters (in the range a..z).

outputFormat: The string $S$ after all deletions are complete. It is guaranteed that $S$ will not become empty during the deletion process.

translation:
Farmer John为他的奶牛们订阅了Good Hooveskeeping杂志，因此他们在谷仓等待挤奶期间，可以有足够的文章可供阅读。不幸的是，最新一期的文章包含一篇关于如何烹制完美牛排的不恰当的文章，FJ不愿让他的奶牛们看到这些内容。

FJ已经根据杂志的所有文字，创建了一个字符串  $ S $  ( $ S $  的长度保证不超过  $ 10^6 $  )，他想删除其中的子串  $ T $  ,他将删去  $ S $ 中第一次出现的子串  $ T $  ，然后不断重复这一过程，直到  $ S $  中不存在子串  $ T $ 。

注意：每次删除一个子串后，可能会出现一个新的子串  $ T $ （说白了就是删除之后，两端的字符串有可能会拼接出来一个新的子串  $ T $ ）。

输入格式：第一行是字符串  $ S $  ，第二行输入字符串  $ T $ ，保证  $ S $  的长度大于等于  $ T $  的长度， $ S $  和  $ T $  都只由小写字母组成。

输出格式：输出经过处理后的字符串，保证处理后的字符串不会为空串。

Translated by @StudyingFather


title: [USACO15FEB] Cow Hopscotch S

description:
Just like humans enjoy playing the game of Hopscotch, Farmer John's cows have invented a variant of the game for themselves to play. Being played by clumsy animals weighing nearly a ton, Cow Hopscotch almost always ends in disaster, but this has surprisingly not deterred the cows from attempting to play nearly every afternoon.

The game is played on an $R$ by $C$ grid $(2 <= R <= 100,$ $2 <= C <= 100)$, where each square is labeled with an integer in the range $1...K (1 <= K <= R * C)$. Cows start in the top-left square and move to the bottom-right square by a sequence of jumps, where a jump is valid if and only if:

1. You are jumping to a square labeled with a different integer than your current square,

2. The square that you are jumping to is at least one row below the current square that you are on, and

3. The square that you are jumping to is at least one column to the right of the current square that you are on.

Please help the cows compute the number of different possible sequences of valid jumps that will take them from the top-left square to the bottom-right square.

inputFormat: The first line contains the integers $R, C,$ and $K$. The next $R$ lines will each contain $C$ integers, each in the range $1..K$.

outputFormat: Output the number of different ways one can jump from the top-left square to the bottom-right square, mod $1000000007$.

translation:
牛跳房子游戏在一个  $ R \times C $  的网格中进行，每个格子上有一个  $ 1 \cdots K $  的数字$(  1 \leq K \leq R \times C  )$。

牛从网格的左上角出发，跳到右下角。一次跳跃是合法的，当且仅当满足以下的所有条件：
1. 目标格子与当前所在格子的数字不同；
2. 目标格子至少应在当前格子下一行；
3. 目标格子至少应在当前格子右一列。

现在请你求出：从左上角跳到右下角的合法跳跃的方案数量。

输入格式：第一行输入三个数字，  $ R , C , K $  .接下来  $ R $  行每行输入  $ C $ 个数字来描述游戏地图。保证每个数字都在  $ 1 \leq K $  的范围内。

输出格式：输出总方案数  $\bmod$   $ 10^9+7 $  的结果。

Translated by @StudyingFather


title: [USACO15FEB] Superbull S

description:
Bessie and her friends are playing hoofball in the annual Superbull championship, and Farmer John is in charge of making the tournament as exciting as possible. A total of $N$ $(1 <= N <= 2000)$ teams are playing in the Superbull. Each team is assigned a distinct integer team ID in the range 1...2^30-1 to distinguish it from the other teams. The Superbull is an elimination tournament -- after every game, Farmer John chooses which team to eliminate from the Superbull, and the eliminated team can no longer play in any more games. The Superbull ends when only one team remains.

Farmer John notices a very unusual property about the scores in matches! In any game, the combined score of the two teams always ends up being the bitwise exclusive OR (XOR) of the two team IDs. For example, if teams 12 and 20 were to play, then 24 points would be scored in that game, since 01100 XOR 10100 = 11000.

Farmer John believes that the more points are scored in a game, the more exciting the game is. Because of this, he wants to choose a series of games to be played such that the total number of points scored in the Superbull is maximized. Please help Farmer John organize the matches.

inputFormat: The first line contains the single integer $N$. The following $N$ lines contain the N team IDs.

outputFormat: Output the maximum possible number of points that can be scored in the Superbull.

translation:
Bessie 和她的朋友们正在一年一度的 Superbull 锦标赛中打球，而 Farmer John 负责让比赛尽可能激动人心。总共有 $ N $ 支队伍（$1≤N≤2000$）参加了 Superbull 锦标赛。每个团队都有一个 $ 1$ 到 $2 ^ {30}  -1 $ 之间的团队 ID。

Superbull 是一场淘汰赛: 在每场比赛之后，FJ 选择淘汰其中一支球队，而被淘汰的球队再也无法参加任何比赛了。当只剩下一支球队时，比赛就结束了。

FJ 注意到一个不寻常的事情：在任何一场淘汰赛中，两个团队的总分是两个团队 ID 的按位异或（XOR）。例如，如果第 $ 12 $ 队和第 $ 20 $ 队将参加比赛，则该游戏的得分为 $ 24 $ 分，因为 01100 XOR 10100 = 11000。

FJ想要设计一种比赛方案，让所有比赛的得分总和最大。请帮助 Farmer John组织比赛。

输入格式：第一行包括一个整数 $N$ ，下面 $N$ 行每行包括一个队伍的ID。

输出格式：输出一个整数，代表比赛的最大总得分。

样例解释：让 $ 3 $ 队与 $ 9 $ 队进行比赛，并让 $ 9 $ 队晋级。然后他让 $ 6 $ 队和 $ 9 $ 队对决，让 $ 6 $ 队获胜。最后，第 $ 6 $ 队和第 $ 10 $ 队比赛， $ 10 $ 队获胜。总得分为：3 XOR 9+6 XOR 9+6 XOR 10=10+15+12=37。

hint:
OUTPUT DETAILS: One way to achieve 37 is as follows: FJ matches teams 3 and 9, and decides that 9 wins, so teams 6, 9, and 10 are left in the tournament. He then matches teams 6 and 9, and lets team 6 win. Teams 6 and 10 are then left in the tournament. Finally, teams 6 and 10 face off, and team 10 wins. The total number of points scored is (3 XOR 9) + (6 XOR 9) + (6 XOR 10) = 10 + 15 + 12 = 37.

NOTE: The bitwise exclusive OR operation, commonly denoted by the ^ symbol, is a bitwise operation that performs the logical exclusive OR operation on each position in two binary integers. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but is 0 if both bits are 0 or both are 1. For example: 10100 (decimal 20) XOR 01100 (decimal 12) = 11000 (decimal 24)

[Problem credits: Alex Yang, 2015]


title: hby与tkw的基情

background:
> 基情恒久远，一对永流传。

hby 和 tkw 是一对好基友，他们经常在一起做♂游♂戏 (/滑稽)。

description:
他们喜欢玩字符串游戏，尤其喜欢玩回文串。每次 hby 会给出一个数 $n$，那么 tkw 就需要给出 $Ans=\sum\limits_{i=1}^ni\times s[i]\times[i\bmod 2]$。其中 $s[i]$ 代表长度为 $i$ 的回文串的个数（只考虑小写字母），最后面是 bool 表达式

不过由于 tkw 最近学 ycz 找妹纸去了，于是他就将这个问题交给了你，如果你不能在 $1\rm s$ 内答出来，那么 hby 和 tkw 的基情将会破裂！~~（不过那样 tkw 就可以安心地找妹纸了）~~

由于答案会非常大，所以你只需要输出答案 $\bmod 10^9+7$ 的值即可

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

接下来 $T$ 行，每行一个数 $n$。

outputFormat: 共 $T$ 行，每行代表一个答案。


title: mzf的考验

background:
$mzf$立志要成为一个豪杰，当然，他也是一个$OIer$。
他希望自己除了会$OI$之外还会各种东西，比如心理学、吉他、把妹等等。
为了让自己有更大的魅力，他不驼背，不熬夜，整天锻炼，双目炯炯有神，是我们机房最不像$OIer$的人。
然而，在与我们格格不入若干天并且将《易经》研究透彻之后，承受不住我们对他另类的言论，他爆发了。
机房在那一刹那仿佛天塌地陷，世界末日。

description:
八卦有乾、坤、震、巽、坎、离、艮、兑；
两两组合，一上一下，形成了六十四卦，每卦六爻，一共三百八十四爻。
爻分阴阳，阳爻性属阳刚，阴爻性属阴柔。天下之大，无奇不有。千奇百怪，皆出此处。
$mzf$研究透彻了易经之后，画出了$n$个奇怪的图案。他说那是他改进出来的更强大的卜卦体系。
每一个图案有二十行，每一行要么是阴爻$(0)$，要么是阳爻$(1)$，作为一个$OIer$，我们可以将卦象看成一个个二进制串；
他将$n$个图案画在了符纸上，然后进行$m$次操作：

操作1：翻转区间$[l,r]$的图案，比如$(3,1,2,5)$变成$(5,2,1,3)$；

操作2：$mzf$画地为卦，将$[l,r]$之间的卦象都异或上新画的那个卦象；

操作3：$mzf$会询问机房里的其他人$[l,r]$之间卦象代表的二进制数权值和。

如果不能正确回答每个操作$3$，那么机房风水格局将会改变，我们都将...！

由于$mzf$疯狂之下将我们都捆♂绑♂了起来，所以只能求求你来帮我们解决这个问题。

inputFormat:
第一行两个正整数：$n$，$m$（$n$为序列长度，$m$为操作个数）

第二行$n$个正整数：$a[i]$ (用$10$进制数表示每个卦象)$(1<=i<=n)$

接下来$m$行：每行首先一个正整数$opt$表示操作类型

1. $opt=1$：两个正整数：$l,r$。请翻转区间 $[l,r]$；
2. $opt=2$：三个正整数：$l,r,d$。请将区间$[l,r]$中的所有卦象都异或卦象$d$。（$0\le d\lt 2^{20}$）
3. $opt=3$：两个正整数：$l,r$。请查询区间 $[l,r]$ 的卦象权值和。

outputFormat: 对于每个 $opt=3$ 的情况，输出一行答案。

hint:
对于 $20\%$ 的数据，$n\le1000$，$m\le 1000$。

对于另外 $20\%$ 的数据，不存在操作 $1$。

对于另外 $20\%$ 的数据，保证 $n$ 为 $2$ 的次幂，且在操作 $1$ 中，保证 $l=i\times(2^j)+1$，$r=(i+1)\times(2^j)$，其中 $i,j$ 为任意值。

对于 $100\%$ 的数据，$n\le 10^5$，$m\le 5\times 10^4$，$1\le l\le r\le n$，$0\le d<2^{20}$。


title: lty loves 96！

background: 众所周知，$lty$非常喜欢$96$这两个数字（想歪的现在马上面壁去），更甚于复读~~（人本复）~~！

description:
由于爱屋及乌，因此，$lty$对于那些含有$96$的数也非常喜欢，而这里的含有不是一般的含有，而是具有以下性质的含有（三条都需要满足）：
* 这个数为一个$N$位数，且没有前置零
* 这个数中至少要出现$M$次$9$和$6$（例：$986996$中出现了$5$次，$9$出现了$3$次，$6$出现了$2$次，共计$5$次）
* 这个数存在连续的三位$A$,$B$,$C$，满足下面任意一条
	* $A+B+C$为$9$或$6$
	* $(A^2+B^2)$%$C$为$9$或$6$，如果$C$为$0$，则该条件视为不满足

inputFormat: 一行，两个数$N$,$M$

outputFormat: 一个数，表示这样的数的个数


title: GodFly的寻宝之旅

background:
“蒹葭苍苍，白露为霜。所谓伊人，在水一方…”

怀着$a$ $burning$ $desire$，$GodFly$开启了他追寻学妹之路。

description:
我们把校园抽象成一个具有$n$个点的无向连通图，其中的$n$个结点分别编号为$1,2,3,...,n$。把$GodFly$经过的结点表示为一个路径集合$A=\left\{a_1,a_2,a_3,...,a_m\right\}$，表示他依次经过了编号为$a_1$、$a_2$、…、$a_m$的结点，由于集合的元素具有互异性，这意味着$GodFly$无法重复经过同一个结点。

$GodFly$现在要从第$1$个结点走到第$n$个结点，然而他的腿疾对他造成了许多不便。定义$GodFly$经过了$m$个结点，当前在点$a_m$，且路径集合$A=\left\{a_1,a_2,a_3...,a_{m-1}\right\}$（加入新结点$a_m$前）时，他的总体力耗费为$w_m=(w_{m-1}+a_m*sum(A))$%$2$，其中$w_{m-1}$表示上一个路径集合的体力耗费；且对于集合$A$，$sum(A)=a_1+a_2+...+a_{m-1}$。

对于$w=0$的情况，我们称$GodFly$处于“滑基态”，否则对于$w=1$的情况，我们称$GodFly$处于“对偶态”。现在$GodFly$想要知道，他走到$n$结点后处于滑基态或对偶态的方案数，由于这个数可能很大，你只需要输出它对$19260817$取膜（模）的结果；注意两个方案是不同的，当且仅当它们有至少一条经过的边不同，而非路径集合不同。

**注意：T3压缩包内第一个数据有误，以题面的样例为准。**

inputFormat:
第一行，两个数$n$，$k$，分别表示点数和边数；

接下来$k$行，每行两个数$u$、$v$，表示结点$u$与结点$v$之间有一条边。

输入的最后一行为一个数$c$，$c=0$表示求滑基态方案数，$c=1$表示求对偶态方案数。

outputFormat: 一行，一个数表示方案数，详见题面。

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

对于$30$%的数据，$n<=10$，$k<=45$，无重边及自环；

对于$60$%的数据，$n<=15$，$k<=300$；

对于$80$%的数据，$n<=15$，$k<=100000$；

对于$100$%的数据，$n<=18$，$k<=100000$；

样例数据在**data.zip\fantasy\**中。

**【样例说明】**

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

如图，初始时在$1$结点，路径集合为$\left\{1\right\}$，费用为$0$；

若从$1$走到$2$结点再走到$3$结点，到$2$结点时，费用为$(0+2*sum(\left\{1\right\}))$%$2=2*1$%$2=0$，并把$2$加入路径集合，则此时路径集合为$\left\{1,2\right\}$；到$3$结点时，因上一次费用为0，费用为$(0+3*sum(\left\{1,2\right\}))$%$2=3*(1+2)$%$2=1$；

若从$1$结点直接走到$3$结点，则费用为$(0+3*sum(\left\{1\right\}))$%$2=3*1$%$2=1$。

故最终走到$3$结点时费用为$1$的方案数为$2$。

**【提示】**

本题时限$3s$，且可以开启$O_2$优化，不必过分担心卡常数，但请确保算法足够优美。


title: [Cnoi2019] 须臾幻境

background: 这曾今有一个凄婉哀伤的故事，但是被出题人删档弄丢了。

description:
你有一个无向图 $G( V, E )$, $E$ 中每一个元素用一个二元组 $( u, v )$ 表示。

现在把 $E$ 中的元素排成一个长度为 $|E|$ 序列 $A$。

然后给你 $q$ 个询问二元组 $( l, r )$,

表示询问 图 $ G'\big( V, \mathop{\bigcup}\limits_{ i \in [l, r] } \{A_i\} \big) $ 的联通块的个数。

inputFormat:
第一行， 四个整数, 表示 $|V|$, $|E|$, $q$, $t$, 其中 $t$ 表示强制在线参数.

以下$|E|$行， 每行一个二元组 $( u, v )$ , 表示 $A$ 序列.

再以下$q$行， 每行一个二元组 $( l' , r' )$ 表示一组加密后的询问.

解密方式:

```
GetQuery( &l, &r, t, last_ans, |E| )
    IF t > 0 THEN
        l <- (l + t * last_ans) Mod |E| + 1
        r <- (r + t * last_ans) Mod |E| + 1
    IF l > r THEN Swap( l, r )
```
初始时 last_ans = 0.

outputFormat: $q$ 行，表示每个询问的答案。


title: [CmdOI2019] 黑白图

background: 你看见了一张奇怪的图。

description:
有一张 $n$ 个点，$m$ 条边的简单无向连通图，点可以染上黑色或者白色。

这个图比较稀疏，具体来讲有两种情况。

- $m=n-1$ ，此时是一棵树。

- $m=n$ ，此时是一颗基环树。

我们定义一张黑白图的权值为：其黑色**连通块大小**的 $k$ 次方和。

现在图的形态已经确定，但是每个点上的颜色尚未确定，对于第 $i$ 个点。其有**百分之** $p_i$ 的可能是黑色，反之则是白色。

求图的期望权值对 $998244353$ 取模的结果。

inputFormat:
第一行包括三个正整数 $n,m,k$ ，意义如题面所述。

接下来一行 $n$ 个数依次表示 $p_{1\sim n}$。

后 $m$ 行，每行两个数 $f,t$ ，表示图的一条无向边 $f\leftrightarrow t$ 。

outputFormat: 输出一个整数，表示图的期望权值对 $998244353$ 取模的结果。


title: [国家集训队] Crash 的文明世界

description:
Crash 小朋友最近迷上了一款游戏——文明5 (Civilization V)。在这个游戏中，玩家可以建立和发展自己的国家，通过外交和别的国家交流，或是通过战争征服别的国家。

现在 Crash 已经拥有了一个 $n$ 个城市的国家，这些城市之间通过道路相连。由于建设道路是有花费的，因此 Crash 只修建了 $n-1$ 条道路连接这些城市，不过可以保证任意两个城市都有路径相通。

在游戏中，Crash 需要选择一个城市作为他的国家的首都，选择首都需要考虑很多指标，有一个指标是这样的：

$$S(i) = \sum_{j = 1}^{n}{\rm dist}(i, j) ^ k$$

其中 $S(i)$ 表示第 $i$ 个城市的指标值，${\rm dist}(i, j)$ 表示第 $i$ 个城市到第 $j$ 个城市需要经过的道路条数的最小值，$k$ 为一个常数且为正整数。

因此 Crash 交给你一个简单的任务：给出城市之间的道路，对于每个城市，输出这个城市的指标值，由于指标值可能会很大，所以你只需要输出这个数 $\bmod\ 10007$ 的值。

inputFormat:
输入的第一行包括两个正整数 $n$ 和 $k$。

接下来有 $n-1$ 行，每行两个正整数 $u, v$（$1\le u, v\le n$），表示第 $u$ 个城市和第 $v$ 个城市之间有道路相连。这些道路保证能符合题目的要求。

outputFormat: 输出共 $n$ 行，每行一个正整数，第 $i$ 行的正整数表示第 $i$ 个城市的指标值 $\bmod\ 10007$ 的值。


title: [MtOI2018] 衣服？身外之物！

background: gcd 有许多件衣服，每件衣服有不同的颜色。

description:
gcd 共有 $n$ 件衣服，编号为 $A_1,A_2,\cdots A_n$。

每一件衣服分别拥有颜色值和清洗时间，他在每一件衣服穿完以后都会将其送去清洗，而这件衣服当天所拥有的舒适感取决于当天的天气与他的衣服颜色值的乘积，天气值存在负数。

现给出共 $m$ 天的天气情况，求最大舒适值。

如果**必定**有一天 gcd 没有衣服穿，输出 "gcd loves her clothes!"（不含引号）。

inputFormat:
输出共 $4$ 行。

第 $1$ 行输入 $n,m$。

第 $2$ 行输入 $x_1,x_2\cdots x_n$表示衣服的颜色值。

第 $3$ 行输入 $y_1,y_2\cdots y_n$表示衣服的清洗时间。

第 $4$ 行输入 $z_1,z_2\cdots z_m$表示当天的天气值。

outputFormat: 输出共 $1$ 行，输出 $m$ 天穿衣的最大舒适值或输出 "gcd loves her clothes!"。


title: GodFly的求导工具

background: “求得导中导，方为人上人。”作为一名铁头娃，$GodFly$已不满足于简单的求导了。

description:
$GodFly$为了证明自己的头铁，决定挑战一项任务：求一个具有大整数系数的$n$次多项式函数的$k$阶导。现在他希望聪明的你能够…静静地坐在那里看他求导。要知道，他可是能与神威-太湖之光匹敌的男人。

作为$GodFly$的朋友，$xhx$希望你能帮他写一个程序，与$GodFly$一同计算导函数及导数。如果你的程序能跑过他的手算，$xhx$会敲一下$GodFly$的铁头。

*关于导数的几个运算法则：

若$f(x)=ax^n$，则$f'(x)=anx^{n-1}$；

若$F(x)=f(x)+g(x)$，则$F'(x)=f'(x)+g'(x)$；

其中$f'(x)$，$g'(x)$，$F'(x)$分别表示$f(x)$，$g(x)$，$F(x)$的导函数。

**不要被导数吓到，本题考点不在此**

**设$g(x)=ax^3+bx^2+c$，则$g(x_0)=ax_0^3+bx_0^2+c$。**

**$k$阶导即求$k$次导数。**

**新样例：https://pan.baidu.com/s/1w64WmnnGtKyAluxrX3PkNg； 数据已更新。**

inputFormat:
第一行，两个整数$n$、$k$，含义见题面；

接下来一行，一个字符串表示函数，为“$f(x)=a_{n}x^n+a_{n-1}x^{n-1}+....+a_0x^0$”，其中对于任意$i$，$a_ix^i$的项可能不出现，也可能出现多次，且$a_i$均为正整数，但系数为$1$的项不输入$a_i$，只输入$x^i$；

接下来一行一个数$m$，表示询问个数；

接下来$m$行，每行一个数**$x_0$**，表示求$f(x)$的$k$阶导在$x_0$处的导数，**换句话说，假设$g(x)$为$f(x)$的$k$阶导函数，求$g(x_0)$**。

不存在多余空格及空行。

outputFormat: $m$行，每行一个数表示所求的导数值。

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

对于$30$%的数据，$n<=5$，$a_i<=100$，$x_0<=100$，且对于任意$0<=i<=n$，$a_ix^i$出现有且仅有一次，且保证数据以$i$为关键字降序排列；

另有$10$%的数据，$k=0$；

另有$10$%的数据，$k=1$；

另有$10$%的数据，$n=k$；

对于$100$%的数据，$n<=100$，$k<=n$，$m<=10$，$a_i<=10^5$，$x_0<=10^5$；

样例数据在**data.zip\derivative\**中。

**【样例说明】**

对$f(x)$求导，则一阶导$f'(x)=3x^2+4x+1$；求二阶导，即对$f'(x)$再求导，得$f''(x)=6x+4$；故所求$f(0)=6*0+4=4$，$f(1)=6*1+4=10$。

**【提示】**

$PS$：担心大家抱怨代码量大（出题人懒），较原题简化了许多。

如果你提前$AK$了，不妨看看一段铁头娃之间的对决：

《冯所长三导导死郑拔蚌》

冯所长······扑的只一导，正导在分式上，导得郑蚌头晕眼花，参数歪在半边，却便似开了个初等函数表，平方，根号，对勾一发都导出来。郑铁头算不过来，那把答案也丢在一边，口里只叫：“导得好！”冯所长骂道：“铁头娃！还敢应口！”提起笔来就分子只一导，导得火星四溅，头破血流，也似开了个二项式定理，三次、四次、五次都绽将出来。
两边看的人惧怕冯所长，谁敢向前来劝。

郑蚌导不出，讨饶。冯所长喝道：“咄！你是个铁头娃！若只和俺分类讨论到底，洒家倒饶了你！你如今对俺讨饶，洒家偏要分离参数！”又只一导，新函数上正着，却似做了一个常用导数表，指数，对数，分子分母一齐响。所长看时，只见郑蚌倒在地上，口里只有出的气，没了入的气，动弹不得。

冯所长假意道：“你这厮诈死，洒家再导！”只见头渐渐的没了。所长寻思道：“俺只指望消费这厮一顿，不想三导真个导死了他。洒家须扣分，又没题做，不如及早撒开。”拔步便走，回头指着试卷道：“这废题，洒家跳过！”一头算，一头大踏步去了。


title: [BalticOI 2009 Day1] 甲虫

description:
**译自 [BalticOI 2009](http://www.csc.kth.se/contest/boi/tasks.php) Day1 T1「[Beetle](http://www.csc.kth.se/contest/boi/beetle.pdf)」**

有一只甲虫处于一根水平的树枝。因为他沉迷数学无法自拔，所以他觉得很像是在 $x$ 轴上。

在同一根树枝上，还有 $n$ 滴露水。每滴露水占用 $m$ 个单位的水分。相对于甲虫的位置，他们的坐标分别是 $x_1,x_2,\dots,x_n$。

显然，这一天将会骄阳似火。每过一个时间单位，就会有一个单位的水分从每一滴露水流失。这只甲虫受尽了烈阳的折磨，以至于每当它碰到一滴露水都能瞬间喝完。在每个时间单位中它能移动一个单位的距离。

所以你要写一个程序，根据露水的坐标，计算出甲虫**最多**能喝到的水。

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

以下 $n$ 行，每行一个整数，表示露水的坐标 $x_1,x_2,\dots,x_n$。

outputFormat: 输出一行，表示甲虫最多能喝到的水


title: [MtOI2018] 崩坏3？非酋之战！

background:
原题面因为太丑，被 disangan233 于 2019/09/26 修改。

在 2018 年暑假的时候，disangan233 肝了一个暑假的崩坏 3，他的帐号终于 $50$ 级啦！他终于把他的逆神巫女肝到 S 啦！

因为庆祝崩坏 3 登上 APP Store Top1，米忽悠给全服玩家发放了 $5$ 张扩充补给卡。

在玄学233聊天室发送了 "怒 grass 大伟出奇迹！" 之后就……单抽出律化娜了。

![Screenshot_20180804-124812.png](https://i.loli.net/2019/08/24/3s2AKqOQNUMGLcF.png)

description:
在崩坏 3 中有一个叫做天命基地的地方，女武神们将在基地中~~开派对~~与敌人们厮杀。

女武神们的攻击力为 $atk$，她们将进行资源保卫战！

天命基地中有 $1$个 boss，boss 的血量为 $hp$，boss 不会攻击女武神。

现在有一条长度为 $n$ 的道路，道路的一头是 boss，另外一头是女武神需要保卫的资源，最开始 boss 每秒将会向资源移动 1 个单位长度。女武神们需要保护资源，所以她们要攻击 boss。

我们将整条道路分成 $n$ 个格子，最开始资源在第 $n$ 格，女武神在第 $1$ 格，boss 在第 $0$ 格。

因为女武神的手太短了，所以只有当 boss 到达女武神当前那一格的时候，女武神才会攻击 boss，攻击完之后女武神会后退一格。

女武神有以下 $8$ 种攻击方式（每一格只能使用一种攻击方式）

* 技能，造成 $80\% atk$ 的伤害，并使 boss 获得 $1$ 层燃烧 buff，在之后的每秒钟额外受到 $10\% atk$ 的伤害。(燃烧buff可以叠加)
* 闪避，造成 $70\% atk$ 的伤害，并使 boss 时间暂停 $5s$。（$5s$ 内 boss 无法移动且仍会受到燃烧伤害）
* 大招，造成 $120\% atk$ 的伤害，使 boss 时间暂停 $5s$。
* 分支攻击，造成 $70\% atk$ 的伤害，并使 boss 时空减速，使 boss 经过每一个格子的时间增加 $1s$。
* 爱酱的炸弹，使 boss 获得 $1$ 层燃烧 buff，并使 boss 愤怒，移速 $+50\%$。
* 犹大的誓约，造成 $60\% atk$ 的伤害，如果 boss 有燃烧 buff 则减少 1 层，使 boss 时间暂停 $4s$。
* 奥托之光，造成 $10\% atk$ 的伤害，如果 boss 有燃烧 buff 则清除 buff，使 boss 时间暂停 $10s$。
* 律者之力，造成 $80\% atk$ 的伤害，使 boss 的移动速度 $+100\%$。

现在给你所有的信息，让你帮助 disangan233 蒟蒻算一下，他的女武神能否在 boss 触碰到资源前战胜 boss。

如果可以，输出 boss 死亡时距离资源最远的格子编号。如果不可以，请输出对 boss 造成的最大伤害。

inputFormat:
输入共 $2$ 行。

第 $1$ 行输入 $1$ 个正整数 $n$。

第 $2$ 行输入 $2$ 个正整数，表示 boss 的血量 $hp$ 和女武神的攻击力 $atk$ 。

outputFormat:
输出共 $2$ 行。

第 $1$ 行输出 boss 死亡时距离资源最远的格子编号或者最大伤害值 $\max Atk$。

如果 boss 死亡，请在第 $2$ 行输出 "Tech Otakus Save The World!"。

如果 boss 到达了资源所在格子，请在第 $2$ 行输出 "MiHoYo Was Destroyed!"。

注：数据保证没有 boss 在资源所在格子死亡的情况。

hint:
#### 样例解释 $3$

开局 1 个技能，再来 1 个大招。

#### 样例解释 $4$

开局 1 个技能，再来 2 个大招。

### 子任务

对于 $10\%$ 的数据，保证：

$$
n\leq 10 \qquad  \max Atk\leq 10^{7}-1
$$

对于 $20\%$ 的数据，保证：

$$
n\leq 300 \qquad \max Atk\leq 2^{32}-1
$$

对于 $40\%$ 的数据，保证：

$$
n\leq 1,000 \qquad \max Atk\leq 2^{63}-1
$$
对于 $70\%$ 的数据，保证：

$$
n\leq 5,000 \qquad \max Atk\leq 2^{63}-1
$$

对于 $100\%$ 的数据，保证：

$$
n\leq 10,000 \qquad atk\equiv 0(\bmod\ 10)\qquad  atk\leq 10,000\qquad \max Atk\leq 2^{64}-1
$$

### 题目来源

[MtOI2018 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T4

出题人：disangan233

验题人：CYJian

72679


title: [MtOI2018] 刷题？作业狂魔！

background:
在临听到暑假的尾声以后，神奇的 cz 终于发觉自己的作业不能完成了。

在他写完作业之前，你需要将他做作业的顺序告诉给他听，这样你们就可以一起玩了。

description:
你拥有 $T$ 分钟的时间。

做作业的顺序可以根据重要度 $v_i$ 来排序，但可能这不是最佳方案。且每项作业可能不止有一项，所以每项作业还有一个数量 $c_i$，每项 $t_i$ 分钟可以完成。

而在做某作业之前可能要先写完某个作业，所以还给出 $M$ 个关系，每个关系包含两个数 $a$，$b$ ，代表 $a$ 是 $b$ 完成的前提，不存在 $a=b$ 的情况。

关系不排除环的情况，cz 不想重做一遍作业，只好不做在环上的作业。

当某作业做到一半但时间结束，则失去该作业重要度；当该作业只做了 $k$ 个，但 $k\leq c_i$ ,则得到 $k\times v_i$ 重要度 , 如果该作业没把 $c_i$ 个做完，则不得做其他作业。

可存在 $b$ 有多个 $a$，但请注意一个作业的 **一个** 前提被做了以后，该作业就可以被做了。但cz非常专注，他写完一个作业以后就必须写**以该作业为前提的**作业。

inputFormat:
输入共 $N+M+2$ 行

第 $1$ 行输入 $2$ 个正整数 $N,T$。

接下来共 $N$ 行输入，第 $i$ 行输入 $3$ 个正整数 $v_i,c_i,t_i$。

第 $N+2$ 行输入 $1$ 个正整数 $1$ 行。

接下来共 $M$ 行输入，意义同上。

outputFormat: 输出共 $1$ 行 $1$ 个数，表示价值（重要度）最大值。

hint:
### 子任务

对于 $100\%$ 的数据，$1<=N<=10000,1<=M<=100000$

其他值均在$long long$范围内。

### 题目来源

[MtOI2018 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T1

出题人：Doubleen

56432


title: 灭顶之灾

background: 请将题目名称拼音首字母连起来读

description:
Scarlet 有一张 $n\times m$ 的神秘表格。现在 Scarlet 向表格中填数字，她会从 **第一行** 中的某个格子起，按照 **从左往右，从上往下** 的顺序依次填写 **从 $1$ 开始的正整数**，直至 **填满最后一行**。

为了让你确定这个表格，Scarlet 会告诉你表格中的 $s$ 组 **同行连续数字。** 之后，Scarlet 会对你发起 $q$ 次询问，你需要依次回答每个数字被填在第几行第几列中。

inputFormat:
第一行 $4$ 个正整数分别代表 $n,m,s,q$

接下来 $s$ 行，每行两个正整数 $a_i,b_i$，代表整数 $a_i$ 到 $b_i$ 在表格中处于同一行且连续

接下来 $q$ 行，每行一个正整数 $A_i$，表示每个询问的数字

outputFormat:
如果符合数据的表格不存在，输出一行 `Impossible!`

再如果符合数据的表格不唯一，输出一行 `Uncertain!`

~~ 否则输出 $q$ 行，每行两个正整数，代表每个被询问的数字被填在第几行第几列，如果该数字不在表格内，输出 `0 0`~~

Scarlet 为了减小输出文件，以轻易地上传测试数据至服务器，她现在只需要你输出所有行列数据的异或和（包括前文的 `0 0`）。


title: [USACO14DEC] Cow Jog G

description:
Farmer John's $N$ cows $(1 <= N <= 100,000)$ are out exercising their
hooves again, jogging along an infinite track.  Each cow starts at a
distinct position on the track, and some cows run at different speeds.

The track is divided into lanes so that cows may move past each other.
No two cows in the same lane may ever occupy the same position.
Farmer John doesn't want any cow to have to change lanes or adjust
speed, and he wonders how many lanes he will need to accomplish this
if the cows are going to run for $T$ minutes $(1 <= T <= 1,000,000,000).$

inputFormat:
The first line of input contains $N$ and $T$.

The following $N$ lines each contain the initial position and speed of a
single cow.  Position is a nonnegative integer and speed is a positive
integer; both numbers are at most 1 billion.  All cows start at
distinct positions, and these will be given in increasing order in the
input.

outputFormat:
A single integer indicating the minimum number of lanes necessary so
that no two cows in the same lane ever occupy the same location
(including at time $T$).

translation:
Farmer John 的 $ N $ 头奶牛 $ ( 1 ≤ N ≤ 10^5 ) $ 正在一条长度无限的跑道上慢跑，每头奶牛都有一个不同的开始位置，以及不同的跑步速度。

为了方便奶牛们互相超越，整个跑道被分成了若干条赛道。在同一时刻，不可能有在同一条赛道上的两头奶牛占据相同的位置。

现在奶牛们要跑 $ T $ 分钟，在跑步过程中，他们不会改变自己所在的赛道和自己跑步的速度。FJ想要知道，为了奶牛间不会发生冲突，他需要至少准备多少条赛道。

输入格式：第一行包括两个整数 $ N $ 和 $ T $ 。接下来 $ N $ 行，每行两个整数 $ p_i $ 和 $ v_i $ $ ( p_i , v_i ≤ 10^9 ) $，分别代表奶牛的初始位置和速度。保证了初始位置不相同且为升序排列。

输出格式：一个整数，代表最少需要的跑道数目。


title: [USACO14OPEN] Fair Photography G

description:
FJ's $N$ cows $(1 <= N <= 100,000)$ are standing at various positions along a long one-dimensional fence.  The $ith$ cow is standing at position $x_i$ (an integer in the range 0...1,000,000,000) and has breed $b_i$ (an integer in the range 1..8).  No two cows occupy the same position.

FJ wants to take a photo of a contiguous interval of cows for the county fair, but we wants all of his breeds to be fairly represented in the photo. Therefore, he wants to ensure that, for whatever breeds are present in the photo, there is an equal number of each breed (for example, a photo with $27$ each of breeds $1$ and $3$ is ok, a photo with $27$ of breeds $1, 3,$ and $4$ is ok, but $9$ of breed $1$ and $10$ of breed $3$ is not ok). Farmer John also wants at least $K (K >= 2)$ breeds (out of the 8 total) to be represented in the photo. Help FJ take his fair photo by finding the maximum size of a photo that satisfies FJ's constraints.  The size of a photo is the difference between the maximum and minimum positions of the cows in the photo.

If there are no photos satisfying FJ's constraints, output $-1$ instead.

inputFormat:
* Line 1: $N$ and $K$ separated by a space

* Lines $2..N+1$: Each line contains a description of a cow as two integers separated by a space; $x(i)$ and its breed id.

outputFormat: * Line 1: A single integer indicating the maximum size of a fair photo. If no such photo exists, output -1.

translation:
FJ 的 $N\ (1\le N\le 10^5)$ 只奶牛站在一条一维的栅栏旁边。第 $i$ 只奶牛站在位置 $x_i\ (0 \le x_i \le10^9)$ 处，它的品种是 $b_i\ (1\le b_i\le 8)$。奶牛的位置两两不同。

现在 FJ 要选出 **位置上连续（不是输入顺序上）** 的一段奶牛拍照，要求选中的奶牛中至少包含 $K$ 个品种，且各品种的出现次数相等。照片的尺寸定义为其坐标最大的奶牛的坐标减去最小的坐标，求最大照片尺寸。无解时输出 $-1$。

hint:
INPUT DETAILS:

Breed ids: 1 2 3 - 1 1 2 3 1  - ...  -   1
Locations: 1 2 3 4 5 6 7 8 9 10 ... 99 100

OUTPUT DETAILS:

The range from x = 2 to x = 8 has 2 each of breeds 1, 2, and 3. The range from x = 9 to x = 100 has 2 of breed 1, but this is invalid because K = 2 and so we must have at least 2 distinct breeds.


title: [USACO14MAR] The Lazy Cow G

description:
It's a hot summer day, and Bessie the cow is feeling quite lazy. She wants to locate herself at a position in her field so that she can reach as much delicious grass as possible within only a short distance.

There are $N$ patches of grass $(1 <= N <= 100,000)$ in Bessie's field. The $ith$ such patch contains $g_i$ units of grass $(1 <= g_i <= 10,000)$ and is located at a distinct point $(x_i, y_i)$ in the field $(0 <= x_i,$ $y_i <= $ $1,000,000)$.  Bessie would like to choose a point in the field as her initial location (possibly the same point as a patch of grass, and possibly even a point with non-integer coordinates) so that a maximum amount of grass is within a distance of $K$ steps from this location $(1 <= K <= 2,000,000)$.

When Bessie takes a step, she moves 1 unit north, south, east, or west of her current position.  For example, to move from $(0,0)$ to $(3,2)$, this requires 5 total steps.  Bessie does not need to take integer-sized steps -- for example, 1 total step could be divided up as half a unit north and half a unit east.

Please help Bessie determine the maximum amount of grass she can reach, if she chooses the best possible initial location.

inputFormat:
* Line 1: The integers $N$ and $K$.

* Lines 2..1+N: Line $i+1$ describes the $ith$ patch of grass using 3 integers: $g_i, x_i, y_i.$

outputFormat: * Line 1: The maximum amount of grass Bessie can reach within $K$ steps, if she locates herself at the best possible initial position.

translation:
```
  Bessie的田里有N(1<=N<=100,000)块草地，每块草地的坐标是 (xi, yi) (0<=xi,yi<=1,000,000),上面长着gi(1<=gi<=10,000)个单位的牧草。
  Bessie可以向东南西北方向走，一次走一步（一个单位长度）。如她从（0,0）走到（3,2）需要5步。她最多可以一次走k (1<=k<=2,000,000) 步。
  现在她想找一个位置，使她从该位置出发可以得到最多单位的牧草(她可以走多次，但每次都从该位置出发)。
  输入格式：
  第1行：两个整数N和K
  第2~N+1行：三个整数gi，xi，yi
  输出格式：
  第1行：Bessie所能获得的最多单位牧草数
```

hint:
INPUT DETAILS:

Bessie is willing to take at most 3 steps from her initial position.  There
are 4 patches of grass.  The first contains 7 units of grass and is located
at position $(8,6)$, and so on.

OUTPUT DETAILS:

By locating herself at $(3,0)$, the grass at positions $(0,0)$, $(6,0)$, and
$(4,2)$ is all within $K$ units of distance.


title: [USACO14FEB] Cow Decathlon G

description:
Farmer John's $N$ cows $(1 <= N <= 20)$, conveniently labeled $1...N$ as always, are preparing for a decathlon that has $N$ different events (so perhaps it would be better called an N-athlon instead of a decathlon, which traditionally has exactly 10 events).

Cow i has a skill level of $s_ij$ $(1 <= s_ij <= 1000)$ when competing in event j.  Each cow must compete in one and only one event, and each event must have some cow competing in it.

The total score for all cows is the sum of their skill levels for the events in which they are competing.  However, the event judges can also give out bonus points if they are particularly impressed.  There are $B$ bonuses $(1 <= B <= 20)$ that the judges can give out. Bonus i has three parts: if the cows obtain at least $P_i$ points $(1 <= P_i <= 40,000)$ for the first $K_i$ events (including other bonuses involving just those events), they will get an additional $A_i$ points $(1 <= A_i <= 1000)$.

For example, let us consider $N = 3$ cows with the following skills:

```
      E V E N T
     | 1 | 2 | 3
   --+---+---+--
C  1 | 5 | 1 | 7
   --+---+---+--
O  2 | 2 | 2 | 4
   --+---+---+--
W  3 | 4 | 2 | 1
```
For example, cow 1 would earn the team 7 points if she participates in event 3.

Suppose the judges offer a bonus (B = 1), such that if the if the cows score at least 7 points in the first two events, they will get an  additional 6 points.  Here, the optimal assignment would be to assign cow 1 to event 1, cow 2 to event 3 and cow 3 to event 2.  For the first two events, cow 1 will score 5 points and cow 3 will score 2 points giving them 7 points, which is enough to satisfy bonus 1.  Therefore, the total points that they score will be 5+2+4+6=17.

Please help decide which events the cows should attempt to maximize their total score.

inputFormat:
* Line 1: Two space-separated integers: $N, B$

* Lines 2..B+1: Line i+1 will contain the information for bonus i which is three space- separated integers: $K_i, P_i, A_i$.

* Lines B+2..B+N+1: Line B+1+j will contain the information on how cow j will perform at each  of her events. This will be given in $N$ space-separated integers: $s_j1...s_jN.$

outputFormat: * Line 1: The maximum amount of points that the cows can receive, including bonuses.

translation:
题目大意
约翰有N头奶牛，组成了一直队伍参加全能比赛。比赛一共有N项，每头奶牛必须参加一项比赛，每项比赛也必须有一头奶牛参加。任何一头奶牛可以胜任任何一项比赛，但得分不一样。如果第i头奶牛参加第j项比赛，在比赛结束的时候，可以为团体总分增加Si,j。
比赛是按照顺序依次进行的。除了上述获得分数的方法之外，还有B种奖励分。获得奖励的方法是在前几项比赛里获得足够的分数。具体来说，第i项奖励会在第Ki项比赛结束的时候检查，如果 当时的总分大于或等于Pi，奶牛们就可以立即获得额外的Ai 分。如果有多项奖励在同一时刻检查，奶牛可以自由安排检查和加分的顺序。请问约翰应该如何安排奶牛参加比赛，才能让它们获得最高的分数？

输入输出格式
输入格式
第一行：两个整数N和B，1≤N≤20 , 1≤B≤20
第二行到第B+1行：第i+1行有三个整数Ki，Pi和Ai，1≤Ki≤N ,1≤Pi≤40000 , 1≤Ai≤1000
第B+2行到第B+N+1行：第i+B+1 行有N个整数，代表Si,1到Si,N，对每个1≤j≤N , 1≤Si,j≤1000。

输出格式
单个整数：表示奶牛们可以获得的最大得分

样例输入
3 1
2 7 6
5 1 7
2 2 4
4 2 1

样例输出
17

提示：
第一项比赛由第一头奶牛参加，第二项比赛由第三头奶牛参加，第三项比赛由第二头奶牛参加。

translator：2018_RNG丶妖夢

hint: Cow 1 will perform event 1, cow 3 will perform event 2, and cow 2 will  perform event 3.


title: GodFly求解法向量

background:
“遇到函数无脑求导，遇到几何无脑建系。”是铁头娃的公共特征。

作为喜欢建系的一个铁头娃，$GodFly$经常需要计算法向量。

description:
定义平面$\alpha$内有两相交向量$\overrightarrow a=(x_1,y_1,z_1)$，$\overrightarrow b=(x_2,y_2,z_2)$，若$\overrightarrow z=(x,y,z)$为平面$\alpha$的法向量，则：

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

现给出$\overrightarrow a$及$\overrightarrow b$的坐标，求出一个法向量$\overrightarrow z$，并输出其坐标。

**SPJ已更新**

inputFormat: 本题有多组数据；对于每组数据，一行六个数，分别为$x_1,y_1,z_1,x_2,y_2,z_2$。

outputFormat:
对于每组数据，三个数，$x,y,z$，之间用空格隔开。

**每组数据之间用空行隔开。**

**法向量的坐标不可都为$0$。**

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

所有坐标（包括答案）均在$32$位**整数**范围内。

对于$30$%的数据，只有单组输入；

对于$100$%的数据，输入组数$<=5*10^4$，且输入的坐标均为绝对值不超过$5*10^4$的正整数；

样例数据在**data.zip\vector\**中。

**【提示】**

本题有$Special$ $Judge$，输出任意一组解即可。


title: [MtOI2018] 情侣？给我烧了！

background:
FFF

本题加强版：[P4931](https://www.luogu.com.cn/problem/P4931)

description:
有 $n$ 对情侣来到电影院观看电影。在电影院，恰好留有 $n$ 排座位，每排包含 $2$ 个座位，共 $2×n$ 个座位。

现在，每个人将会随机坐在某一个位置上，且恰好将这 $2 × n$ 个座位坐满。

如果一对情侣坐在了同一排的座位上，那么我们称这对情侣是和睦的。

你的任务是求出当 $k = 0, 1, ... , n$ 时，共有多少种不同的就坐方案满足**恰好**有 $k$ 对情侣是和睦的。

两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，一共会有 $(2n)!$ 种不同的就坐方案。

由于结果可能较大，因此输出对 $998244353$ 取模的结果。

inputFormat:
输入包含多组数据。

输入的第 $1$ 行包含 $1$ 个正整数 $T(1 \leq T \leq 1000)$，表示数据的组数。

接下来 $T$ 行，每行包含 $1$ 个正整数 $n(1 \leq n \leq 1000)$。

outputFormat: 对于每组输入数据，输出共 $n + 1$ 行，每行包含 $1$ 个整数，分别表示 $k = 0, 1, ..., n$ 时满足恰好有 $k$ 对情侣是和睦的就坐方案数。

hint:
### 子任务

本题只有一个 $T=1000$ 的数据点。。。暴力还是算了吧！

### 题目来源

[MtOI2018 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T2

出题人：Imagine

50167


title: [IOI2009] Raisins

background: IOI2009 D1T4

description:
普罗夫迪夫的著名巧克力大师 Bonny 需要切开一板带有葡萄干的巧克力。巧克力是一个包含许多相同的方形小块的矩形。小块沿着巧克力的边排列成 $N$ 行 $M$ 列，共有 $N\times M$ 块。每个小块上有 $1$ 个或多个葡萄干，没有葡萄干在小块的边上或者跨过两个小块。

最开始，巧克力是一整块。Bonny 需要把它切成上述的 $N\times M$ 个独立的小块。因为 Bonny 很忙，她需要她的助手 Sly Peter 帮她切。
Peter 只能从一端到另一端切直线，并且他要为他的每一刀得到报酬。Bonny 手头没有钱，但是她有足够的葡萄干，所以她提出用葡萄干付给 Peter。Sly Peter 同意接受葡萄干，但是有下面的条件：每次他把给定的一块巧克力切成两小块，他都要得到和那块给定的巧克力上葡萄干数目相同的葡萄干。

Bonny 想要付给 Peter 尽可能少的葡萄干。她知道这 $n\times m$ 个小块中每一个小块上葡萄干的数目。她可以选择递给 Peter 的巧克力的顺序，也可以告诉 Peter 如何切（横切还是竖切）以及从哪里切。请告诉 Bonny 如何把巧克力切成一个个独立的小块，使她能够付给 Sly Peter 尽可能少的葡萄干。

**任务**：编写一个程序，给定每个小块上葡萄干的数目，计算出 Bonny 要付给 Sly Peter 的最少的葡萄干的数目。

inputFormat:
第一行两个由空格隔开的整数 $N, M$，分别表示巧克力的行数和列数。

接下来 $N$ 行描述了每个小块上葡萄干的数目。其中第 $k$ 行描述了第 $k$ 行小块的巧克力。每行包含 $m$ 个整数，分别以一个空格隔开。这些整数描述了该行从左到右的小块。第 $k$ 行的第 $p$ 个整数表示位于第 $k$ 行第 $p$ 列的小块上的葡萄干数目 $R_{k, p}$。

outputFormat: 一行一个整数，表示 Bonny 要付给 Sly Peter 的最少的葡萄干的数目。

hint:
### 样例解释

一种可能的代价为 $77$ 的切割方案如下所示：

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

第一次切割将第三列和剩下来的巧克力分开了。Bonny 需要付给 Peter $29$ 个葡萄干。

接下来 Bonny 把较小的那一块巧克力（有两小块，每一块都有 $5$ 个葡萄干）给 Peter，要求 Peter 切成两半并支付 $10$ 个葡萄干。

在此之后，Bonny 给 Peter 剩下来的最大块（分别有 $2,  7, 1, 9$ 个葡萄干在它的四个小块上）。Bonny 要求 Peter 水平切割这一块，将第一行和第二行分开并付给他 $19$ 个葡萄干。

此后 Bonny 给 Peter 左上角的块，支付 $9$ 个葡萄干。最后 Bonny 要求 Peter 将左下角的块分开，支付 $10$ 个葡萄干。

Bonny 的总代价是 $29 + 10 + 19 + 9 + 10 = 77$ 个葡萄干。没有其它安排切割的方案有更小的代价。

### 数据范围与约定

- 对于 $25\%$ 的数据，$n,m\leq 7$。
- 对于 $100\%$ 的数据，$1\leq n,m\leq 50$，$1\leq R_{k, p}\leq 1000$。


title: PION贪吃蛇

background:
NOIP2018原创模拟题 T3

NOIP DAY1 T3 or DAY 2 T2 难度

贪吃蛇大家都玩过吧，当然不同版本有不同规则。下面介绍PION贪吃蛇。

description:
![图A](https://cdn.luogu.com.cn/upload/pic/31298.png)

***表示方法：***

该题中贪吃蛇存在于一个n行m列的矩形中，用 ‘.’ 表示空地，用 '#’ 表示蛇身，用 ‘@’表示蛇头，用‘&’表示食物
例如：图一表示 $5*6$ 的矩形，有一条蛇，蛇长度为 $7$，有两个食物

***基本规则：***

1.蛇头每一秒就会移动一格，身体自然会跟着移动，用W表示向上，S表示向下，A表示向左，D表示向右

2.蛇每吃一个食物就长度就会加一，而增加的长度体现在食物所在的地方，你可以把吃食物理解成食物变成了蛇头，之前的蛇头变成了蛇身，这一秒不移动

例如：图二的三幅图展示了第一秒，第二秒，和第三秒的情况

3.蛇如果死亡，身体（包括头）一定会全部变成食物

4.PION贪吃蛇的蛇头碰到自己或别的蛇的身体就会死亡

例如：图三的三幅图展示了第二条蛇撞在别人身体上死亡的过程

5.蛇头撞在边界上也会引起死亡，但蛇头刚好现在边界上不会

例如：图四第二幅图虽然蛇头在边界上，但是只是刚好，如果此时进行D操作蛇就会死亡，如果进行W或S就不会

6.如果有操作使蛇头向相反方向运动，之后如果与身体重合蛇也会死亡（比如：图二第一幅图使用A操作,蛇就会死亡，此时在原地成为三个食物，你也可以理解为蛇下一秒不行动而自杀了）

7.两条蛇蛇头相撞，主动撞上的死亡

8.蛇的移动按编号由小到大进行（编号的含义见下文）

inputFormat:
第一行三个数 $n,m,k$ 表示 $n*m$ 的矩形，$k$ 表示操作次数

接下来 $n$ 行每行 $m$ 个字符，表示地图

再接下来 $c$ 行（注意：图中有几条蛇就有几行），每行 $k$ 个字符，表示有 $k$ 个操作（如果执行了某个操作蛇死了，就忽略后面的操作）

我们将蛇编号：按每条蛇蛇头的坐标从小到大编号为 $1，2，...，c$（越靠近上边的坐标越小，如果相同越靠近左边的坐标越小）

例如：图三第一幅图两条蛇的蛇头坐标分别为（$4,3）,（3,7）$所以较长的蛇编号为 $2$，较短的蛇编号为 $1$

outputFormat:
$c+1$ 行，输出 $k$ 次操作后每一条蛇的长度，编号；每一行第一个为长度，第二个数为编号

最后一行输出剩下食物的总个数

注意：输出按长度由大到小排序（长度相同按编号由小到大排序），死亡的蛇长度为 $0$

hint:
***样例说明：***

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

图五，图六展示了从第 $0$ 秒开始之后每一秒地图的状态，请看图理解（样例二图四有点小错误）

***数据范围：***

$10\%$ 数据满足 $n,m\leq 5,c=1,k\leq3$

$30\%$ 数据满足 $n,m\leq 10,c\leq 2,k\leq 5$

$50\%$ 数据满足 $n,m\leq 50,c\leq 5,k\leq 20$

$70\%$ 数据满足 $n,m\leq 100,c\leq 7,k\leq 50$

$100\%$ 数据满足 $n,m\leq 200,c\leq 20,k\leq 100$，且图中的蛇不会引起混淆（对于任意蛇头，最多只有一块蛇身于其相连，而蛇身最多为二连块）,且数据保证图中的蛇均可以判断身体与头的对应关系，不会造成蛇身形态多解


title: [USACO14JAN] Cross Country Skiing S

description:
The cross-country skiing course at the winter Moolympics is described by an $M * N$ grid of elevations (1 <= M,N <= 500), each elevation being in the range 0 .. 1,000,000,000.

Some of the cells in this grid are designated as waypoints for the course.  The organizers of the Moolympics want to assign a difficulty rating $D$ to the entire course so that a cow can reach any waypoint from any other waypoint by repeatedly skiing from a cell to an adjacent cell with absolute elevation difference at most $D$.  Two cells are adjacent if one is directly north, south, east, or west of the other.  The difficulty rating of the course is the minimum value of $D$ such that all waypoints are mutually reachable in this fashion.

inputFormat:
* Line 1: The integers $M$ and $N$.

* Lines 2..1+M: Each of these $M$ lines contains $N$ integer elevations.

* Lines 2+M..1+2M: Each of these $M$ lines contains $N$ values that are either $0$ or $1$, with $1$ indicating a cell that is a waypoint.

outputFormat: The ski course is described by a 3 x 5 grid of elevations.  The upper-left, upper-right, and lower-right cells are designated as waypoints.

translation: 乡村越野滑雪比赛在一个 m×n (1<=m,n<=500）的二维表格中进行，每个格子的海拔在 0 至 1000000000 之间。滑雪者可以从一个格子滑到相邻格子，（可以从高处滑到低处，也可以从低处滑到高处），难度值 D 是两者之间的海拔差的绝对值。相邻的格子是指有公共边的格子。一条路径的难度值是指该路径上相邻两格子的难度值的最大值。现在给出若干个关键格子，求所有这些关键格子相互可达的最小的难度值 D。

hint: If D = 21, the three waypoints are reachable from each-other.  If D < 21, then the upper-right waypoint cannot be reached from the other two.


title: 快递员

description:
Bob 的城市里有 $n$ 个邮递站，由于经济考虑，这些邮递站被 $n - 1$ 条带权无向边相连。即：这 $n$ 个邮递站构成了一棵树。

Bob 正在应聘一个快递员的工作，他需要送 $m$ 个商品，第 $i$ 个商品需要从 $u$ 送到 $v$。由于 Bob 不能带着商品走太长的路，所以对于一次送货，他需要先从快递中心到 $u$，再从 $u$ 回到快递中心，再从快递中心到 $v$，最后从 $v$ 返回快递中心。换句话说，如果设快递中心是 $c$ 号点，那么他的路径是 $c \rightarrow u \rightarrow c \rightarrow v \rightarrow c$。

现在 Bob 希望确定一个点作为快递中心，使得他送货所需的最长距离最小。显然，这个最长距离是个偶数，你只需要输出最长距离除以 $2$ 的结果即可。

inputFormat:
第一行输入两个数 $n, m$，意义如上。

接下来 $n-1$ 行，每行三个数 $u_i, v_i, w_i$，表示一条连接 $u_i, v_i$，长度为 $w_i$ 的边。

接下来 $m$ 行，每行两个整数 $u_i, v_i$，表示商品的起止位置。

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

hint:
对于 $25\%$ 的数据，满足 $1 \leq n, m \leq 1000$。

对于 $100\%$ 的数据，满足 $1 \leq n, m \leq 10^5, 1 \leq w_i \leq 1000$。


title: 密室

background:
NOIP2018 原创模拟题 T2

NOIP DAY1 T2 or DAY2 T2 难度

题目背景改编自小说《哈利波特与密室》。

description:
**密室被打开了。**

哈利与罗恩进入了密室，他们发现密室由n个小室组成，所有小室编号分别为：$1,2,...,n$ 。所有小室之间有 $m$ 条通道，对任意两个不同小室最多只有一条通道连接，而每通过一条通道都需要 $C_i$ 的时间。

开始时哈利与罗恩都在编号为 $1$ 的小室里，他们的目标是拯救金妮和寻找日记，但是他们发现金妮和日记可能在两个不同的小室里，为了尽快发现真相，他们决定以最少的时间到达两个目标小室。但是某些小室只有会与蛇对话的人才能进入，也就是只有哈利一个人可以进入。

现在，哈利告诉你密室的结构，请你计算他们到达两个目标小室的最短时间。

inputFormat:
第一行 $n,m,k$ 表示有 $n$ 个小室 $m$ 条通道，$k$ 间小室只有哈利可以进入。

第二行 $k$ 个数，表示只有哈利可以进入的小室的编号。（若 $k=0$，不包含该行）

接下来 $m$ 行，每行 $3$ 个数：$a,b,c$ 表示 $a$ 小室与 $b$ 小室之间有一条需要花费 $c$ 时间的通道。

最后一行，两个数 $x,y$ 表示哈利与罗恩需要去的小室的编号

outputFormat: 一行，输出一个数，表示到达两个密室的最短时间。


title: 多少个 1？

description:
给定整数 $K$ 和质数 $m$，求最小的正整数 $N$，使得 $ 11\cdots1$（$N$ 个 $1$）$\equiv K \pmod m$。

说人话：就是 $111\cdots 1111 \bmod m = K$。

inputFormat: 第一行两个整数，分别表示 $K$ 和 $m$。

outputFormat: 一个整数，表示符合条件最小的 $N$。


title: 崂山白花蛇草水

description:
神犇 Aleph 在 SDOI Round2 前立了一个 flag：如果进了省队，就现场直播喝崂山白花蛇草水。凭借着神犇 Aleph 的实力，他轻松地进了山东省省队，现在便是他履行诺言的时候了。蒟蒻 Bob 特地为他准备了 999,999,999,999,999,999 瓶崂山白花蛇草水，想要灌神犇 Aleph。神犇 Aleph 求（跪着的）蒟蒻 Bob 不要灌他，由于神犇 Aleph 是神犇，蒟蒻 Bob 最终答应了他的请求，但蒟蒻 Bob 决定将计就计，也让神犇 Aleph 回答一些问题。

具体说来，蒟蒻 Bob 会在一个宽敞的广场上放置一些崂山白花蛇草水（可视为二维平面上的一些整点），然后询问神犇 Aleph 在矩形区域 $x_1\le x\le x_2,y_1\le y\le y_2$ 中，崂山白花蛇草水瓶数第 $k$ 多的是多少。为了避免麻烦，蒟蒻 Bob 不会在同一个位置放置两次或两次以上的崂山白花蛇草水，但蒟蒻 Bob 想为难一下神犇 Aleph，希望他能在每次询问时立刻回
答出答案。

神犇 Aleph 不屑于做这种问题，所以把这个问题交给了你。

inputFormat:
输入的第一行为两个正整数 $n$，$q$，表示横纵坐标的范围和蒟蒻 Bob 的操作次数（包括放置次数和询问次数）。

接下来 $q$ 行，每行代表蒟蒻 Bob 的一个操作，操作格式如下：
首先第一个数字 $\mathrm{type}$，表示操作种类。$\mathrm{type}=1$ 表示放置，$\mathrm{type}=2$ 表示询问。
若 $\mathrm{type}=1$，接下来会有三个正整数 $x, y, v$，表示在坐标整点 $(x, y)$ 放置v瓶崂山白花蛇草水。
若 $\mathrm{type}=2$，接下来会有五个正整数 $x_1, y_1, x_2, y_2, k$，表示询问矩形区域 $x_1\le x\le x_2,y_1\le y\le y_2$ 中，崂山白花蛇草水瓶数第 $k$ 多的是多少。

为了体现程序的在线性，你需要将每次读入的数据（除了 $\mathrm{type}$ 值）都异或 $\mathrm{lastans}$，其中 $\mathrm{lastans}$ 表示上次询问的答
案。如果上次询问的答案为 `NAIVE!ORZzyz.`（见样例输出），则将 $\mathrm{lastans}$ 置为 $0$。初始时的 $\mathrm{lastans}$ 为 $0$。
初始时平面上不存在崂山白花蛇草水。

outputFormat:
对于每个 $\mathrm{type}=2$ 的操作，一行输出崂山白花蛇草水瓶数第 $k$ 多的是多少。若不存在第 $k$ 多的瓶数，
请输出 `NAIVE!ORZzyz.`。


title: [1007] 梦美与线段树

background:
欢迎大家光临星象馆

这里有着无论何时永远不会消失

美丽的无穷光辉

满天的星星等候着大家的到来

description:
梦美为了研究星象馆的星星，用巨型投影机——耶拿将星星排成了一个序列，接着梦美将这个星星序列建成了一棵线段树。

这是一棵维护区间和的线段树，每个节点的权值是该节点所对应的区间中，所有星星的权值和。有的时候梦美会从这棵线段树的根节点开始在星空游历。当她要进入子节点的时候，假设左右子树对应区间的权值和分别为 $sum_l$  和 $sum_r$，当前节点的权值为 $sum_{cur}$ ，梦美会以 $\frac{sum_l}{sum_{cur}}$ 的概率进入左子树，否则进入右子树。

游历的时候，梦美会把她经过的节点的权值累加起来，现在她希望您帮她设计一个算法求出这个权值期望下是多少。

当然，如果星星都是不变的梦美会觉得很没有意思，因此她会发出一些指令，每个指令是，对下标在 $[l,r]$ 的星星，权值加上 $v$ 。不过由于馆里的工作人员全都离开了，因此没有人教梦美在线段树上维护懒标记，所以梦美的每次指令都会实时更新所有的线段树节点。

为了解决线段树写法不一的问题，此处给出梦美维护这个问题时的部分代码：
```cpp
const int N = 100010, MOD = 998244353;
int a[N], sum[N << 2];
#define lson (o << 1)
#define rson (o << 1 | 1)
void pushup(int o) {
	sum[o] = (sum[lson] + sum[rson]) % MOD;
}
void build(int o, int l, int r) {
	if (l == r) {
		sum[o] = a[l];
	} else {
		int mid = (l + r) >> 1;
		build(lson, l, mid);
		build(rson, mid + 1, r);
		pushup(o);
	}
}
void change(int o, int l, int r, int q, int v) {
	if (l == r) {
		sum[o] = (sum[o] + v) % MOD;
		return;
	}
	int mid = (l + r) >> 1;
	if (q <= mid) change(lson, l, mid, q, v);
	else change(rson, mid + 1, r, q, v);
	pushup(o);
}
void add_to_interval(int l, int r, int v) {
	for (int i = l; i <= r; i ++) {
		change(1, 1, n, i, v);
	}
}
```
其中 `a` 数组表示每个星星的权值，`sum` 数组表示每个线段树节点的权值，`add_to_interval` 函数表示一次操作。

inputFormat:
第一行两个整数 $n,m$，表示序列长度和操作次数。

第二行 $n$ 个整数，表示这个序列。

接下来 $m$ 行，每行为

$1 \ l \ r \ v$，表示区间 $[l,r]$ 的节点加上了 $v$；

$2$ ，表示一次询问。

outputFormat: 对于每一个 $2$ 操作，输出一个答案。令答案化成最简分数为 $\frac{p}{q}$（保证 $q$ 不是 $998244353$ 的倍数），则输出 $p\cdot q^{-1}\mod 998244353$。

hint:
对于 $30\%$ 的数据，保证 $1 \leq n,m\leq 100$；

对于另外 $20\%$ 的数据，满足所有操作 1 中 $l=r$；

对于 $100\%$ 的数据，保证 $1\leq n,m \leq 10^5,1 \leq a_i,v \leq 10^9,1\le l\le r\le n$。

样例答案实际是 $\frac{94}{5}$ 和 $\frac{303}{13}$。


title: 食堂

background:
我CYJian就是死，死外边，从这跳下去，也不会吃食堂一口饭。

$$\color{white}\text{真香。。}$$

description:
食堂第$i$天有$i$道菜.$CYJian$觉得第$i$天的第$j$道菜的美味程度为$\lbrace \frac{i}{j} \rbrace$({}就是取小数部分),当然,$CYJian$是一个勇于尝试的人,所以每一道菜都会吃那么一点.

现在CYJian有$T$个问题,每一个问题都是从第$A_i$天到第$B_i$天得到的美味值的总和.现在请你帮他算一算吧!请输出答案模$998244353$的值.

inputFormat:
第一行一个数T。

接下来T行，每一行一共两个数，表示每一次询问的$A$和$B$。

outputFormat: T行，每行一个正整数表示美味值之和.**如果答案可以表示成$\frac{P}{Q}$的形式,则需要找到任意一个$x$使得$Q \times x \equiv P (\bmod\ 998244353)$,并且输出$x \bmod 998244353$**


title: 排队

background:
$CYJian$班的这个队形...是梯形么??

$\color{white}\text{信息竞赛班的女生能有多少??}$

description:
教官觉得$CYJian$班上的队形~~不是很美观~~很不美观..所以教官决定要重排一下队形..

教官先让所有同学按照学号排好序站成一列,然后每一次把当前队列第1,2,3,5,8,13...(差不多就是斐波那契数列了..)个人拉出来,直到没有人能拉出来为止..然后这些人组成一行,排到上一行的后面..

举个栗子,如果一共有10个人,大概就是这样子的:(加粗表示当前选到的人)

1: **1** **2** **3** 4 **5** 6 7 **8** 9 10

取走后: 4 6 7 9 10

2: **4** **6** **7** 9 **10**

取走后: 9

3: **9**

最后的队形长这样:

第一行: 1 2 3 5 8

第二行: 4 6 7 10

第三行: 9

(教官排的队形当然得说好看了..)

我们现在定义一行的美观度: 这一行所有人学号的乘积能分解的质因子的个数..(~~特别的~~,1分解质因子不能得到任何质因子,所以个数为0)

比如第二行,$4 \times 6 \times 7 \times 10=1680=2 \times 2 \times 2 \times 2 \times 3 \times 5 \times 7 \rightarrow 7$

年级一共有$T$个班级,每一个班级都要排一次队形..

现在给出第$i$个班级人数$N_i$和一个正整数$K_i$,需要你求出第$i$个班级排队形后第$K_i$行的队伍的美观度..

特别的,如果排的队形中没有第$K_i$行则输出-1..

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

接下来$T$行每行两个正整数$N_i$和$K_i$..

变量的意义详见题面描述..

outputFormat: $T$行,每行一个正整数表示所求的美观度..

hint:
$Subtask$ $1$($30$ $pts$): $ K_i = 1, 1 \leqslant N_i, T \leqslant 1000 $

$Subtask$ $2$($30$ $pts$): $ 1 \leqslant K_i \leqslant 100 \ \ \ \  1 \leqslant N_i \leqslant 10000  \ \ \ \  1 \leqslant T \leqslant 5000  $

$Subtask$ $3$($40$ $pts$): $ 1 \leqslant K_i \leqslant 10000 \ \ \ \ \  1 \leqslant N_i \leqslant 5*10^6 \ \ \ \ \  1 \leqslant T \leqslant 10^6 $

数据不保证存在全是-1的测试点..

注意:**本题捆绑测试**


title: 乘积

background: $CYJian$在经过多次加强后的题目..

description:
给出$A$,$B$,求下面的式子的值.

$$\prod_{i=A}^{B}\prod_{j=1}^{i}(\frac{i}{j})^{\lfloor \frac{i}{j} \rfloor}\ (\bmod \ 19260817)$$

包含$T$组询问.

------

听说有许多人看不懂公式？？

好吧。。这里给出伪代码：

```
for i=A to B
  for j=1 to i
    res = res * power(i/j, floor(i/j))
res = solve(res)
```

最后的solve表示处理成分数取模的形式。。

不保证这样精度不会原地起爆。。

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

接下来$T$行每行两个正整数表示这一组询问的$A$,$B$

outputFormat: $T$行,每行一个正整数表示这一组询问的答案.


title: 整数校验器

description:
有些时候需要解决这样一类问题：判断一个数 $x$ 是否合法。

$x$ 合法当且仅当其满足如下条件：

- $x$ 格式合法，一个格式合法的整数要么是 $0$，要么由一个可加可不加的负号，一个 $1$ 到 $9$ 之间的数字，和若干个 $0$ 到 $9$ 之间的数字依次连接而成。
- $x$ 在区间 $[l,r]$ 范围内（即 $l \le x \le r$）。

你需要实现这样一个校验器，对于给定的 $l, r$，多次判断 $x$ 是否合法。

inputFormat:
第一行三个整数 $l,r,T$，表示校验器的校验区间为 $[l,r]$，以及需要校验的 $x$ 的个数。

接下来 $T$ 行，每行一个 $x$，表示要校验的数，保证 $x$ 长度至少为 $1$ 且仅由 '0'~'9' 及 '-' 构成，且 '-' 只会出现在第一个字符。

outputFormat:
输出共 $T$ 行，每行一个整数，表示每个 $x$ 的校验结果。

校验结果规定如下：$0$ 表示 $x$ 合法；$1$ 表示 $x$ 格式不合法；$2$ 表示 $x$ 格式合法且不在 $[l,r]$ 区间内。

hint:
对于 $100\%$ 的数据，$0 \le T \le 512$，$l,r$ 在 $64$ 位有符号整型范围内（即 $-2^{63}\le l \le r \le 2^{63}-1$）。

保证输入文件大小不超过 $\text{128KB}$。数据在 linux 下生成，没有 '\r' 字符。

以下为部分特殊限制（互不包含）：

- 有 $5\%$ 的数据，$T=0$。
- 有 $25\%$ 的数据，保证 $x$ 格式一定合法。
- 有 $30\%$ 的数据，保证如果 $x$ 格式合法，那么 $x$ 一定在 $64$ 位有符号整形范围内。

其中有一个不计分的hack测试点，用于考察long long边界数字的判断，如果是100分UnAC的话，那么可能是你没有考虑这一种情况。


title: [RC-02] 求和

description:
小 Q 给你了几行字符串，字符串中间包含有一些整数，整数之间可能会有其他字符。你需要输出每行中所有整数的和。如果一个行里面一个数都没有则不要输出。**每两个整数之间一定有间隔字符（见样例 $3$）。**

请注意，题目中的整数都是简单的整数，即：整数前面没有多余的符号。假如数据中有 `.`，视作分隔符。

inputFormat: 每行一个字符串。

outputFormat: 对于每一个包含了整数的字符串，输出一行一个数，即其中数的和。

samples:
su57jdkjth54hjsns-321d 8 ejre
erg(&-^%

weruy4uhnd-

hint:
【样例解释】

- 第一个样例中，第一行有 $57,54,-321,8$ 几个数，和为 $-202$；第二、三行没有数字；第四行只有一个 $4$，输出 $4$。
- 第二个样例中只有一行，有两个数，和为 $4532893$。
- 第三个样例的第一行，由于每两个整数之间一定有间隔字符，所以把 `-` 视为间隔字符，输出 $2$。第五行，第一个数为 $-1$，因此把第二个 `-` 视为间隔字符，和为 $-1+1=0$。第七行，将 `.` 视为间隔字符，和为 $-2+3=1$。

【数据范围】

说明：「条件 A」指数据中不存在除数字、空格、换行、水平制表符之外的其他字符；「条件 B」指每两个数之间一定用且只用一个空格隔开。

**由于数据在 Windows 下制造，行末可能有多余的 `\r` 字符。请注意。**

对于 $10\%$ 的数据，满足条件 A 和 B，每行一定有且仅有 $10$ 个数；

对于 $40\%$ 的数据，满足条件 A 和 B，且不存在空行；

对于 $50\%$ 的数据，满足条件 A 和 B；

对于 $70\%$ 的数据，满足条件 A；

对于 $100\%$ 的数据，不存在除水平制表符、空格、换行外的不可见字符，每行不超过 $1000$ 个字符，每行最多包含 $200$ 个整数，不超过 $100$ 行，每个整数均 $\in[-10^7,10^7]$。


title: 礼物

background: 由于你出色的完成了前面两道题目，善良的 __stdcall 决定给你一个小礼物，给拼搏在 AK 这套题之路上的你，一个有力的援助。

description:
__stdcall 决定给你 $n$ 个礼物，每个礼物有一个魔力值 $a_i$。

这些礼物的魔力值都是独一无二的，两两互不相同。这些礼物都有着神奇的魔力，如果两个礼物 $i, j$ 的魔力值满足 $a_i \operatorname{bitand} a_j \ge \min(a_i, a_j)$，那么这两个礼物的魔力将会相互抵消，因此它们不能放在一个箱子里。

这里的 $\operatorname{bitand}$ 表示按位与运算，如果你对这一运算不够了解，请参考：<https://baike.baidu.com/item/%E6%8C%89%E4%BD%8D%E4%B8%8E/9601818>。

作为发礼物苦力的 ljt12138 的箱子并不多，不过幸运的是，每个箱子都足够大。现在他请求你帮助他合理分配，用**尽可能少**的箱子装下所有礼物。换言之，使得每个礼物都被恰好装入一个箱子中，且同一个箱子中的礼物魔力不会相互抵消。如果有多种合法的方案，你只需要给出**任意一种**。

ljt12138 十分善良，如果你只能求出所需要的箱子数，也可以获得该测试点 $60\%$ 的分数，关于这一点，请参考下面的提示与说明。

inputFormat:
- 第一行两个数 $n$ 和 $k$，$n$ 为礼物总数，$k$ 为一个参数，方便你进行计算。
- 第二行 $n$ 个两两不同的数$a_i$，满足 $0\le a_i < 2^k$，表示礼物的魔力值。

outputFormat:
- 第一行输出一个数。如果你不希望输出方案，请输出0；如果你希望输出方案，请输出 $1$。**如果你在这一行输出了不符合要求的信息，将被判为 WA**。
- 第二行一个数 $m$，表示你将礼物装到了 $m$ 个箱子里。
- 如果你在第一行输出了 $1$，接下来 $m$ 行，每行表示一个箱子：首先一个数 $s_i$，表示当前箱子中礼物的个数；接下来 $s_i$ 个数，表示当前子集。


title: 浏览器

background: \_\_stdcall在用Edge玩slay的时候，鼠标会经常失灵，这让她十分痛苦，因此她决定也要让你们感受一下Edge制造的痛苦。

description:
\_\_stdcall给了你n个点，第i个点有权值x[i]，对于两个点u和v，如果x[u] xor x[v]的结果在二进制表示下有奇数个1，那么在u和v之间连接一个Edge，现在\_\_stdcall想让你求出一共有多少个Edge。

如果你没能成功完成任务，那么\_\_stdcall会让你痛苦一下，你这个测试点就没分了。

inputFormat:
一行六个整数，n，a，b，c，d，x[0]。

n是点的个数，每个点的权值需要用如下的方式生成。

你需要使用a，b，c，d和x[0]生成一个数组x，生成方式是这样的。

$x_i = (ax_{i-1}^2 + bx_{i-1} + c) \mod d$

x[i]就是第i个点的权值，点的标号是1到n。

outputFormat: 输出一个整数，表示一共有多少个Edge。

hint:
我们用v表示权值中的最大值。

对于前20%的数据，n<=10。

对于前40%的数据，n<=100。

对于前60%的数据，n<=1000。

对于前80%的数据，n<=1e6。

对于前90%的数据，v<=1e6。

对于100%的数据，n<=1e7，v<=1e9。

保证a，b，c，d，x[0]都是int内的非负整数。


title: 大师

background: 建筑大师最近在跟着数学大师 ljt12138 学数学，今天他学了等差数列，ljt12138 决定给他留一道练习题。

description:
ljt12138 首先建了 $n$ 个特斯拉电磁塔，这些电塔排成一排，从左到右依次标号为 $1$ 到 $n$，第 $i$ 个电塔的高度为 $h[i]$。

建筑大师需要从中选出一些电塔，然后这些电塔就会缩到地下去。这时候，如果留在地上的电塔的高度，从左向右构成了一个等差数列，那么这个选择方案就会被认为是美观的。

建筑大师需要求出，一共有多少种美观的选择方案，答案模 $998244353$。

注意，如果地上只留了一个或者两个电塔，那么这种方案也是美观的。地上没有电塔的方案被认为是不美观的。

同时也要注意，等差数列的公差也可以为负数。

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

第二行 $n$ 个非负整数，第 $i$ 个整数是第 $i$ 个电塔的高度 $h[i]$。

outputFormat: 输出一个整数，表示美观的方案数模 $998244353$ 的值。

hint:
设 $v$ 为最高的电塔高度。

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

对于前 $60\%$ 的数据，$n \le 100$，$v \le 2 \times 10^3$。

对于另外 $20\%$ 的数据，所有电塔的高度构成一个等差数列。

对于 $100\%$ 的数据，$n \le 10^3$，$v \leq2 \times 10^4$。


title: 抓住czx

background: 蒟蒻 lty 出了一道题，但是由于太弱了，所以希望喜欢鸽子的 czx 来帮他写一个 std 。由于 czx 又放鸽子去了，所以没有写 std。蒟蒻 lty 觉得受到了学长的鄙视，所以决定去 czx 放鸽子的地方找他。

description:
 czx 放鸽子的地方是一个公园，公园珂以看作是由 $n$ 个点 $m$ 条边组成的无向图(保证无自环）， lty 将从公园的入口（ $b$ 号节点）进去寻找 czx ， czx 刚开始的位置为 $e$ ，而 czx 会在 $a_i$ 个单位时间时变化位置到第 $x$ 个节点去，在此之前 lty 已经知道了 czx 的具体位置和接下来他位置的变化方案，蒟蒻 lty 现在想知道他至少需要花多少时间找到 czx 。

UPD:

保证图联通， czx 最后会待在一个地方不动

inputFormat:
第一行四个整数$n$,$m$,$b$,$e$,$b$和$e$的意义如题面所示。

接下来$m$行，每行三个整数$x,y,z$，表示 $x$ 到 $y$ 之间有一条双向边， lty 走这条边要花费 $z$ 的时间。

第 $m+1$ 行一个整数 $T$，表示 czx 位置变化的次数。

接下来 $T$ 行，每行两个整数 $a_i$ 和 $x$，表示 czx 将在第$a_i$ 个单位时间时移动到第 $x$ 个点上去。

outputFormat: 一个整数表示最短所需时间。

hint:
**样例解释：**

在开始的时候就直接走到 $2$ 号节点，然后等到 czx过来。总花费时间 $9$ 个单位时间。

对于 30% 的数据，$n\le 100,m\le 1000,T\le 100$

对于另外 30% 的数据，$T=0$

对于 100% 的数据，$n \le 10^5,m \le 5\times10^5,T \le 10^5$

数据保证所有时间在 int 范围内

注意：在任意一个 czx 开始移动的时间点，都是 czx 先瞬移，然后 lty 再行走，也就是说， lty 不能在 czx 瞬移的时候到他瞬移前的点抓住他，但是 lty 可以在他瞬移到的点等着抓他。


title: 鬼故事

background:
### _给大家讲个鬼故事_
有一天晚上，下着大暴雨。小 K 正在他那小小的书房里做着老师给他布置的、数也数不完的信息题目。关着门，关着窗难免有些闷热。小 K 起身，将书桌前的窗子打开一个小小的细缝，小到没有雨点能透过缝隙飘进来。

今天正是农历七月十五日，中元节，俗称鬼节。小 K 从来都没有在这种日子这么晚睡过，因为小 K 迷信，害怕午夜之后，便有鬼怪出没。然而今天，小 K 无可奈何。

小 K 看了看时间：$23:54$。看到 $4$，小 K 皱了皱眉眉头。$4$，谐音是“死”，特别不吉利。在这种日子看到这样的字眼，往往都是不祥之兆。

小 K 的眼皮在打架。他从来都不会做毒瘤题。他索性趴到了书桌上面，两只眼睛渐渐朦胧了起来。

“那儿有一个本子。”他想着。不知道何时，他的书桌靠窗的一角上，静静地躺着一个湿漉漉的本子，好像是刚刚淋过雨。“它是怎么进来的？”小 K 喃喃道。他下意识地翻开那本本子，看到里面有写了一些字。不知道为什么，那些字在发黄的纸页上看起来也那么红。

左边的那一页写着：

 $$4^{4-4}\le M\le N\le 4^{4^{(4+4-\frac{4}{4})}},\sqrt{4}\le K\le 4^{\sqrt{4}}\times(4-\frac{4}{4})+\sqrt{4}$$

右边的那一页写着的似乎比左边的要长：

 $$a_{\frac{4}{4}}=a_{\sqrt{4}}=\frac{4}{4},a_n=\frac{\sqrt{4}}{\sqrt{4}}\times a_{n-\frac{4}{4}}+4^{4-4}\times a_{n-\sqrt{4}}(n\ge \sqrt{4}+\frac{4}{4})$$

$$b_n=\prod^{n+K-\frac{4}{4}}_{i=n}a_i$$

求 $\sum\limits_{i=m}^n b_i$

角落里还有一行小字：**_ 不要翻到最后一页，不然会有可怕的事情发生 _**。但是在这个时候，小 K 早已经闭上了双眼，鼾声和远处的雷声混成一片。

一阵微风吹来，轻轻地，谁也没有意识到。本子的一角被风扬起，滑过一个优美的弧线，落在了本子的另一边。风一阵一阵的吹来，拂过本子发黄的书页。渐渐地，右边的书页少了，左边的书页多了。风停了，本子的倒数第二页停在半空中。在一刹那，似乎一切都静止了。然后，它轻轻地落在了其它书页的最上面。

最后一页上，赫然用鲜红色的歪歪扭扭的大字写着：

# 这道题你已经拖了一个月了！限明天之前做完！

这时候，你夜观天象，预测到了小 K 的这场劫难。时间已是 $23:59:59:400$，如果在这 $1000-400=600$ 毫秒内没有做完，小 K 的检讨将在劫难逃。身为小 K 的好朋友，你能帮他解决这个问题吗？

description:
给定 $k,m,n$，求：

$$\sum_{i=m}^n \prod_{j=i}^{i+k-1} a_j$$

答案对 $10^9 + 7$ 取模。
其中 $\{ a\}$ 为 fibonacci 数列。

inputFormat: 三个正整数，分别表示 $k,m,n$。

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


title: [USACO05DEC] Layout G

background: 14组数据，前10组为原数据，后4组为hack数据

description:
Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1..N standing along a straight line waiting for feed. The cows are standing in the same order as they are numbered, and since they can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate).

Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.

Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.

inputFormat:
Line 1: Three space-separated integers: N, ML, and MD.

Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.

Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.

outputFormat: Line 1: A single integer. If no line-up is possible, output -1. If cows 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between cows 1 and N.

translation:
正如其他物种一样，奶牛们也喜欢在排队打饭时与它们的朋友挨在一起。FJ 有编号为 $1\dots N$ 的 $N$ 头奶牛 $(2\le N\le 1000)$。开始时，奶牛们按照编号顺序来排队。奶牛们很笨拙，因此可能有多头奶牛在同一位置上。

有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。

给出 $M_L$ 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 $M_D$ 对情敌的编号，以及它们希望彼此之间的距离大于等于多少 $(1\le M_L,$ $M_D\le 10^4)$。

请计算：如果满足上述所有条件，$1$ 号奶牛和 $N$ 号奶牛之间的距离最大为多少。

## 输入输出格式

### 输入格式

第一行：三个整数 $N, M_L, M_D$，用空格分隔。

第 $2\dots M_L+1$ 行：每行三个整数 $A, B, D$，用空格分隔，表示 $A$ 号奶牛与 $B$ 号奶牛之间的距离须 $\le D$。保证 $1\le A<B\le N,$ $1\le D\le 10^6$.

第 $M_L+2\dots M_L+M_D+1$ 行：每行三个整数 $A, B, D$，用空格分隔，表示 $A$ 号奶牛与 $B$ 号奶牛之间的距离须 $\ge D$。保证 $1\le A<B\le N,$ $1\le D\le 10^6$.

### 输出格式

一行，一个整数。如果没有合法方案，输出 `-1`. 如果有合法方案，但 $1$ 号奶牛可以与 $N$ 号奶牛相距无穷远，输出 `-2`. 否则，输出 $1$ 号奶牛与 $N$ 号奶牛间的最大距离。

hint:
Explanation of the sample:

There are 4 cows. Cows #1 and #3 must be no more than 10 units apart, cows #2 and #4 must be no more than 20 units apart, and cows #2 and #3 dislike each other and must be no fewer than 3 units apart.

The best layout, in terms of coordinates on a number line, is to put cow #1 at 0, cow #2 at 7, cow #3 at 10, and cow #4 at 27.


title: [COCI2007-2008#4] VAUVAU

description:
在一个小村子里，邮递员、送奶工、垃圾清理工每天早晨都面临着同样的难题：18 号房子的门前有两条看门狗。他们所不知道的是，这两条狗的表现是有迹可循的。

当一天开始时，其中一条狗会先暴躁 $a$ 分钟，然后安静 $b$ 分钟，而另一条狗则会先暴躁 $c$ 分钟，然后安静 $d$ 分钟。这两条狗在一天中会无限地重复上述行为。

给定这三个人到达 18 号房子的时刻，请求出该时刻有几条狗是处于暴躁状态的。

inputFormat:
第一行有四个整数，分别表示 $a, b, c, d$，其意义见【题目描述】。

第二行有三个整数，分别表示邮递员到达的时刻 $p$，送奶工到达的时刻 $m$ 和垃圾清理工到达的时刻 $g$。

outputFormat:
输出三行每行一个字符串，依次表示邮递员、送奶工、垃圾清理工到达时有几条狗处于暴躁状态。

- 如果没有狗处于暴躁状态，输出 `none`。
- 如果恰好有一条狗处于暴躁状态，输出 `one`。
- 如果两条狗都处于暴躁状态，输出 `both`。

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

对于全部的测试点，保证 $1 \leq a, b, c, d, p, m, g \lt 10^3$。

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #4](https://hsin.hr/coci/archive/2007_2008/contest4_tasks.pdf) *T1  VAUVAU***。


title: [COCI2007-2008#4] VECI

description: 给定一个正整数 $x$，请找到一个最小的数字 $y$，使得数字 $0$ 到 $9$ 在 $y$ 中的出现次数与在 $x$ 中的出现次数分别对应相等，且 $x \lt y$。

inputFormat: 输入只有一行一个整数，表示 $x$。

outputFormat: 输出一行一个整数表示答案。若这样的 $y$ 不存在请输出 $0$。

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

对于全部的测试点，保证 $1 \leq x \lt 10^6$。

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #4](https://hsin.hr/coci/archive/2007_2008/contest4_tasks.pdf) *T2   VECI***。


title: [COI2008] GLASNICI

description:
一条直线上有 $n$ 个信使，将他们按照从左至右的顺序以 $1$ 至 $n$ 编号。换句话说，设 $i$ 号信使的的坐标为 $d_i$，则对于 $1 \leq i \lt n$， $d_i \leq d_{i + 1}$。

信使传递一条消息的方法如下：

- 在任意时刻（不一定是整数时刻），任一信使（无论是否已知消息）都可以自由选择向左移动或者向右移动或者原地不动。其移动的速度为每秒 $1$ 单位长度。
- 当两个信使相距不超过一给定实数 $k$ 时，双方可以进行消息传递，也即如果两人中有一人已知该消息，则两人都知道了该消息。消息传递是瞬间发生的，不消耗时间。

现在 $1$ 号信使得到了一条消息，请求出最小的让所有信使都得到该消息的用时。

inputFormat:
第一行有一个实数，表示可以进行消息传递的最大距离 $k$。

第二行有一个整数，表示信使的个数 $n$。

第 $3$ 到第 $(n + 2)$ 行，每行一个实数，第 $(i + 2)$ 行的实数 $d_i$ 表示信使 $i$ 的坐标。

outputFormat:
**本题使用 Special Judge**。

输出一行一个实数表示答案。当你的输出与标准答案相差不超过 $10^{-3}$ 即可得到对应测试点的分数。因此建议您**至少保留四位小数**。

hint:
#### 样例 1 解释

在前 $1.5$ 秒，$1$ 号信使向右走，$2$ 号信使向左走。

第 $1.5$ 秒时，$1$ 号信使在坐标 $1.5$ 处，$2$ 号信使在坐标 $4.5$ 处，二者距离不超过 $3$，可以进行消息传递。

#### 数据规模与约定

对于全部的测试点，保证：

- $1 \leq n \leq 10^5$，$0 \leq k \leq 10^6$。
- $0 \leq d_i \leq 10^9$，且对于任意的 $1 \leq i \lt n$，都有 $d_i \leq d_{i + 1}$。
- 输入的实数小数点后均有 $3$ 位数字。

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [COI2008](https://hsin.hr/coci/archive/2007_2008/olympiad_tasks.pdf) *T1 GLASNICI***，翻译与 SPJ 均来自[一扶苏一](https://www.luogu.com.cn/user/65363)。


title: 全村最好的嘤嘤刀

background: **重阳节**到了，我们最好的八重樱拥有全村最好的嘤嘤刀……

description:
在绯玉丸力量的影响下，八重村成了一条长度为 $n$ 的八重街，并且绯玉丸可以带着八重樱出现在街上的任意地点。而我们的八重樱则会在街上任意穿梭来获取某一地点上的嘤嘤嘤能量，用以升级她的嘤嘤刀。

**出题人：March_H**

在每个时刻，都会发生以下 $3$ 个事件：

$1$ $x$ $val$ 表示在 $x$ 地点出现了携带着 $val$ 点嘤嘤嘤能量的绯狱丸，并且绯狱丸会吞噬该点的嘤嘤嘤能量，使得该点的嘤嘤嘤能量变为 $ val - a_i$ 点，$a_i$ 为出现绯狱丸的前一刻，该点所存在的嘤嘤嘤能量。

$2$ $l$ $r$ 表示绯玉丸会带着八重樱出现在[ $l$ , $r$ ]间的任意一点。八重樱为了尽快升级她的嘤嘤刀，会获取该区间上最大的嘤嘤嘤能量。特殊的，为了保卫八重村，当 $l$ , $r$ 之间存在绯狱丸时，八重樱会优先用她的嘤嘤刀对付绯狱丸，并获得绯狱丸此时拥有的 $a_i$ 点嘤嘤嘤能量。

$3$ $l$ $r$ $val$ 绯玉丸会嘤嘤嘤，使得[ $l$ , $r$ ]上的每一个地点的嘤嘤嘤能量增加 $val$ 点(包括绯狱丸)。

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

第二行为 $n$ 个数，分别表示八重街上每个地点的初始嘤嘤嘤能量。

接下来 $m$ 行，每行会发生 $3$ 个事件中的一个，输入格式为题目描述中的格式。

outputFormat:
对于每一个事件 $2$ ，你应当输出八重樱在该事件中获取的嘤嘤嘤能量并换行。

当所有事件结束时，如果嘤嘤刀积累的能量小于 $10000$ ，你应当输出 $QAQ$ 。

如果在[ $10000$ , $10000000$ )间，你应当输出 $Sakura$。

如果都不符合，请输出 $ice$。

hint:
对于所有的数据：

最终答案都会在 $[0,2^{31}-1]$ 范围内；

$n$ , $m$ $\leqslant$ $100000$。

值得注意的是，无论八重樱是获取了某一地点的嘤嘤嘤能量还是击败了某一地点的绯狱丸，该地点的嘤嘤嘤值都应当清零而不是保留原来的数值。

对于事件 $2$ ，题目保证每个事件中最多出现 $1$ 只绯狱丸。如果出现多个最大值，在每次比较时，请选择靠右的(std默认的)。


title: Tweetuzki 爱等差数列

description:
Tweetuzki 特别喜欢等差数列。尤其是公差为 $1$ 且全为正整数的等差数列。

显然，对于每一个数 $s$，都能找到一个对应的公差为 $1$ 且全为正整数的等差数列各项之和为 $s$。这时，Tweetuzki 想知道，满足这样条件的等差数列，最小的首项是多少。

由于 Tweetuzki 的数学非常差，尤其是因式分解，所以请你告诉他结果。

inputFormat: 输入仅包含一行一个整数 $s$ $(1 \le s \le 10^{12})$.

outputFormat: 输出两个正整数，分别表示这个等差数列的首项和末项。请注意输出最小的首项。


title: 毒瘤之神秘通道

background:
~~Viston就是一个小蒟蒻 By CYJian（自己YY出来的）~~
Viston最喜欢冒险了。

description:
~~（假的算法标签）~~
Viston发现了一个巨大的城堡，他走了进去，城堡里有一个巨大的房间，Viston进去打算参观参观，然后.......他就被困在里面了。   Viston发现了在房间里有很多同样冒险者和一个个通道，冒险者们一个个冲向了不同的**通道**，而Viston一脸懵逼。

Viston动用他莫大的蒟蒻之力摸清了这些**通道**是什么东东~~厉害吧~~，他们是一些单向**通道**，而这些**通道**会把你传送到另一些房间里，一个房间里有一个传送到另一个房间里的传送门。

已知所有的房间最后都通向一个地方，那就是出口。但传送门把你传送到另一个房间也是需要时间的，这个时间取决于之前有多少人使用过这个传送门，计算公式是
$$T=M$$,其中$M$表示传送门的使用人数。 ~~（你前面发啥呆啊，其他人早走光了。）~~

Viston记得每个通道有多少人进入，也探测出了每个房间里的传送门通向哪里，他想知道他从哪个通道进入初始房间才能最快的到达出口，~~毕竟Viston还想着颓金拱门呢。~~

### 注意:只有使用传送门消耗时间,而通道（即到达初始房间）不消耗时间!!!

inputFormat:
第一行输入两个整数$M$,$N$,其中$M$表示有多少个房间(编号为$1-M$),$N$表示有多少个初始的通道。
接下来的$2-------M+1$行,每行输入一个整数$P$,表示第$i$个房间通过一个传送门通向哪个房间,其中$0$号节点表示出口。数据保证是一棵树。
第$M+2-------M+N+1$行,每行输入两个整数$A,B$,表示这个**通道**通向房间$A$,之前有$B$个人进入其中。
### 不同**通道**可能通向相同房间。

outputFormat:
输出只有一行，$c,d$其中$c$表示Viston选择通过通道到达**哪个**初始房间所需时间最短,$d$表示需要多少时间。

当然,如果有多个初始房间时间最短,就输出编号最大的**通道**通向的初始房间..

hint:
## 样例解释
（用的WindowsXP画图画的不好请见谅）
![](https://i.loli.net/2018/10/05/5bb7632fb40f4.jpg)

对于1-5号测试点(10 pts): $1 \leq N, M \leq 50$

对于6-10号测试点(20 pts): $1 \leq N, M \leq 5000$

对于11-15号测试点(30 pts): $1 \leq N, M \leq 100000$

对于16-20号测试点(40 pts): $1 \leq N, M \leq 1000000$

对于5，10，15，20号测试点，给定的树为随机生成。

保证答案都在long long范围内..

$\color{white}\text{这样你才能看出来随机树强度有多低}$

@[Viston](https://www.luogu.org/space/show?uid=107101)

$\color{white}\text{（还想卡树剖的）}$


title: Never·island

background: 您一觉醒来，发现已经到了20000年后的未来。

description:
为了寻找传说中的Avalon，island派出了 $n$ 个考察队。为了保持island的稳定，island有一个通向外界的大门。

这 $n$ 个考察队都需要出一次门进行考察，其中第 $i$ 支考察队会在 $l_i$ 时刻离开，并且在第 $r_i$ 时刻回来。我们保证这些值都是互不相等的。

每当一支考察队离开时，island的大门会变成开的。但是如果这支考察队得到了钥匙，那么他就可以决定关门或者不关门。同时每一个考察队回来的时候要么门本来就是开的（由于island是已知唯一的生活区，因此island内部人员不会主动为任何人开门），要么他必须拥有一把钥匙把门打开。注意，回来的时候无论有没有钥匙，那么这支考察队都可以选择把门关上。

由于一些奇怪的原因，island的设计者只设计了 $k$ 把钥匙，只能分给 $k$ 支考察队。得到钥匙证明了island上层对考察队的信任，因此考察队不会把钥匙交给任何人。

为了防止island下层居民逃出island，上层希望门处于开的时间越短越好。希望您帮他算出最短门会开多久。

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

第二行开始共 $n$ 行，每行两个数，描述 $l_i,r_i$

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


title: [MtOI2018] gcd？人生赢家！

background: gcd 是一个热爱游戏的人。

description:
gcd 最近在玩一个有趣的游戏。

我们把这个游戏抽象成一张图，图上有 $n$ 个点，gcd 需要寻找总计 $m$ 件宝物，它们分布在图上。

对于每件宝物而言，将会有一个前置集合 $S$。只有当取得所有前置宝物时，才能获得该宝物。

gcd 拥有一件神器，这件神器具有传送功能，它可以使用 $k$ 次，可以传送到一个任意节点。

对于游戏而言，肯定会有额外的成就，这些成就会奖励一定的传送次数，成就的达成是满足集合 $S$ 的一瞬间。

现在 gcd 想知道能最快通关的方法，请你求出通关的最少时间。

inputFormat:
输入共 $s+m+e+6$ 行。

第 $1$ 行输入 $3$ 个正整数 $n,m,k$。

第 $2$ 行输入 $1$ 个正整数 $s$ 表示成就的数量。

以下 $s$ 行每行输入 $1$ 个非负整数 $num$ 表示需求多少个宝物，然后输入 $num$ 个数，为所需宝物编号。

第 $s+3$ 行输入 $s$ 个正整数 $a_1,a_2,\cdots a_s$ 表示成就的奖励次数。

第 $s+4$ 行输入 $m$ 个正整数 $p_1,p_2,\cdots p_m$ 表示宝物的位置。

第 $s+5$ 行输入 $1$ 个正整数 $e$ 表示边的总数。

以下 $e$ 行每行输入 $3$ 个正整数 $x,y,z$ 表示 $x$ 与 $y$ 之间有一条边权为 $z$ 的无向边连接。

以下 $m$ 行每行输入 $1$ 个非负整数 $num$ 表示宝物前置要求个数，然后输入 $num$ 个数，为要求的编号。

最后一行输入 $1$ 个正整数 $st$ 表示起点。

outputFormat: 输出共 $1$ 行 $1$ 个正整数，输出最少时间。

hint:
### 子任务

对于 $20\%$ 的数据，$s=0$。

对于 $100\%$ 的数据，$n\leq 200$，$m\leq 12$，$k\leq 4$，$s\leq 8$，$e\leq 20000$ ，奖励次数总和不超过 $8$，保证每两个宝物的位置不相同，可能有重边，保证有解。

### 题目来源

[MtOI2018 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T5

出题人：b2019dy

78488


title: 三去矩阵

background: 无

description: 现在小Y有个$l \times l$的正方形字母矩阵，现在他想进行$q$次询问，每次询问最长的以$(x_i,y_i)$为中心的在一条水平或竖直的直线上的回文串的长度。

inputFormat:
第一行输入两个整数$l,q$，分别表示矩阵的边长和询问的个数。

接下来的$l$行，每行$l$个字母，表示这个矩阵上的字母。

接下来的$q$行，每行两个整数$x_i,y_i$，表示第$i$个询问为在询问矩阵中最长的以$(x_i,y_i)$为中心的在一条直线上的回文串的长度。

outputFormat: 输出$q$行，第$i$行为对于第$i$个询问的回答。

samples:
5 5
abcba
bcdcb
cdedc
bcdcb
abcba
1 1
1 2
1 3
2 3
3 3

hint:
对于$20\%$的数据，$1 \le l \le 2$

另有$20\%$的数据，$q = 1$

另有$20\%$的数据，字母矩阵中心对称，上下对称，左右对称且对角线对称。

对于$100\%$的数据，$1 \le l,q \le 2000$，字母只有小写字母。