title: [APIO2017] 考拉的游戏

background:
### 特别提示

**在洛谷提交本题时的一些注意事项（与原题面不同之处请以此处为准）：**

1. 提交时请在程序里加入以下函数声明语句：

```cpp
void playRound(int*,int*);
```

2. 程序开头不用，也不应该包含 `koala.h` 头文件。
3. 仅支持 `C++`（含 `C++`，`C++11`，`C++14`，`C++17`）提交。

description:
Koala 发明了一个新游戏，来邀请你一起玩！游戏的开始，她会在桌上放 $N$ 个物品，物品从 $0$ 到 $N - 1$ 标号。接着，她会秘密地给每个物品分配一个 $1$ 到 $N$ 之间的整数权值，且任意两个物品不会被分配到相同的权值。其中，第 $i$ 个物品的权值为 $P_i$。她请你来确定由这些权值构成的序列 $P=P_0,P_1,\dots ,P_{N-1}$ 的一些特征。

为了回答她的问题，你可以请 Koala 玩若干轮游戏。每一轮中，你会得到 $W$ 个蓝色石子，Koala 会得到 $W$ 个红色石子。首先，你可以选择若干个物品，再把你的一些（或全部）石子放在这些物品的旁边。Koala 会观察你的石子分配，然后类似地把她的一些（或全部）石子放在若干个物品旁边。如果一个物品旁边的红色石子数严格大于蓝色石子数，那么，Koala可以获得这个物品。Koala 分配她的石子时，总会选择使她获得的物品的权值和最大的方案，如果有多种方案可以做到这一点，她会选择一种获得的物品数最多的方案，如果仍然有多种方案，她会选择其中任意一种。

Koala 非常懒，如果你和她玩太多轮游戏，她就会睡着。你的任务是通过尽可能少轮数的游戏，确定 Koala 的序列 $P$ 的相关特征。

### 任务

在这个任务中，你需要实现 $4$ 个函数：`minValue`, `maxValue`, `greaterValue` 和 `allValues`。

每个函数需要你确定序列 $P$ 的不同特征。我们强烈推荐在我们提供的模版的基础上进行作答。注意，即使你只想获得部分子任务的分数，你也必须为四个函数都提供一个实现（尽管一些函数的内部可能为空）。你的程序禁止从标准输入读数据、向标准输出写数据或与任何文件交互。

在每个函数中，参数 `N` 表示游戏中物品的个数，参数 `W` 表示你和 Koala 在每一轮游戏中拥有的石子数。

* `minValue(N, W)` --- 这个函数需要返回权值最小的物品的标号 $i$，即 $P_i=1$
* `maxValue(N, W)` --- 这个函数需要返回权值最大的物品的标号 $i$，即 $P_i=N$
* `greaterValue(N, W)` --- 这个函数需要比较物品 $0$ 和物品 $1$ 的权值，返回权值较大的物品的标号。具体来说，若 $P_0>P_1$，它应该返回 $0$ ，否则返回 $1$ 。
* `allValues(N, W, P)` --- 这个函数需要确定整个排列，并将其存放在给定的数组 $P$ 中：具体来说，$P[i]$ 应该保存物品 $i$ 的权值 $P_i (0 \leq i \leq N-1)$。

在每个测试点中，交互库会一次或多次调用这些函数中的一个。每次函数调用代表不同的任务，哪个函数会被调用、以及最多被调用多少次取决于子任务（见下文）。你可以认为 Koala 在每次函数调用前确定了她的序列 $P$，并且序列不会在一次函数的调用过程中改变。一次调用结束后，她可以在下次函数调用之前改变她的序列。

你实现的四个函数可以通过调用函数 `playRound` 来获取 Koala 的序列的相关信息。

* `playRound(B, R)`，请 Koala 和你玩一轮游戏。

数组 `B` 描述你在每个物品旁边放了多少蓝色石子。具体来说，对任意 $0 \leq i \leq N-1$，$B[i]$ 个蓝色石子将会被放在物品 $i$ 旁边。每个 $B[i]$ 必须是一个非负整数，且 $B[0]+B[1]+\cdots +B[N-1]$ 不能超过 $W$ 。

交互库会把 Koala 的回应存放在你提供的数组 `R` 中。具体来说，对任意 $0 \leq i \leq N-1$，Koala 会在物品 $i$ 旁边放 $R[i]$ 个红色石子。

每个子任务对你在每次游戏中调用 `playRound` 的次数有所限制。注意，调用次数越少你的得分可能会越高。（具体限制和评分方式参见下文）

hint:
### 子任务

#### 样例数据：$0$ 分

**因为特殊原因（不支持设置 $0$ 分测试点），评测时将不测样例**。

* 有 $5$ 个「样例数据」测试点，每个测试点恰好调用一次 $4$ 个函数中的某一个。请看下文的「样例」获取各测试点的详细信息。
* $N=6$
* $P=5,3,2,1,6,4$

每次游戏中，你可以调用 `playRound `至多 $3200$ 次。

#### 子任务 1：$4$ 分
* 在这个子任务中，交互库只会调用函数 `minValue`，每个测试点中，这个函数最多会被调用 $100$ 次。
* $N=100$
* $W=100$
* 每一次游戏中，你可以调用 `playRound` 至多 $2$ 次。

#### 子任务 2：$15$ 分
* 在这个子任务中，交互库只会调用函数 `maxValue`。每个测试点中，这个函数最多会被调用 $100$ 次。
* $N=100$
* $W=100$
* 每一次游戏中，你可以调用 `playRound` 至多 $13$ 次。
* 这个子任务中，一个测试点的分数取决于每一轮游戏中 `playRound` 被调用次数的最大值 $C_{max}$，具体来说，你的得分为：
  - 若 $C_{max}\leq 4$，获得 $15$ 分。
  - 若 $5 \leq C_{max} \leq 13$，获得 $7$ 分。

#### 子任务 3：$18$ 分
* 在这个子任务中，交互库只会调用函数 `greaterValue`。每个测试点中，这个函数最多会被调用 $1100$ 次。
* $N=100$
* $W=100$
* 每一次游戏中，你可以调用 `playRound` 至多 $14$ 次。
* 这个子任务中，一个测试点的分数取决于每一轮游戏中 `playRound` 被调用次数的最大值 $C_{max}$，具体来说，你的得分为：
  - 若 $C_{max}\leq 3$，获得 $18$ 分。
  - 若 $C_{max}=4$，获得 $14$ 分。
  - 若 $C_{max}=5$，获得 $11$ 分。
  - 若 $6 \leq C_{max}\leq 14$，获得 $5$ 分。

#### 子任务 4：$10$ 分
* 在这个子任务中，交互库只会调用函数 `allValues`，每个测试点中，这个函数会被调用恰好一次。
* $N=100$
* $W=200$
* 你可以调用 `playRound` 至多 $700$ 次。

#### 子任务 5：$53$ 分
* 在这个子任务中，交互库只会调用函数 `allValues`，每个测试点中，这个函数会被调用恰好一次。
* $N=100$
* $W=100$
* 你可以调用 `playRound` 至多 $3200$ 次。
* 这个子任务中，一个测试点的分数取决于 `playRound` 被调用的次数 $C$ ，具体来说，你的得分为：
  - 若 $C \leq 100$，获得 $53$ 分。
  - 若 $101 \leq C \leq 3200$，获得 $\lfloor 53-8 \log_2 (c/100) \rfloor$ 分。其中，$\lfloor x \rfloor$ 为不大于 $x$ 的最大整数。举例来说，若 $C=3200$，那么你的解答将获得 $13$ 分。

### 评分方式

- 和传统题一样，你的程序的运行时间和空间不能超过时间和空间限制。**交互库运行的时间和空间也会算入你的程序的总时间和空间当中**。当你估算这一部分的时空消耗时，你可以认为，在评测时使用的交互库与我们提供的样例交互库有**相同的函数**和**相似的实现**。
- 在一个测试点中，若你在调用 `playRound` 时传入了非法的数组 B，或调用 `playRound` 的总次数超过了上限，那么该测试点记 $0$ 分。
- 在一个测试点的任意一次游戏中，若一个函数没有正确地回答所要求的 Koala 的序列的特征，那么该测试点记 $0$ 分。
- 子任务 4 和子任务 5 均要求你实现函数 `allValues`，但在调用时传入了不同的 $W$。你可以利用两个子任务在这个参数上的不同，从而在你的实现中区分两个子任务。你可以参考你的语言的模板实现获取更详细的信息。
- 比赛时，你可以提交本题目最多 60 次，连续两次的提交至少间隔 2 分钟。
- **你在一个子任务上的得分，等于你在该子任务所有测试点中的最低得分**。

### 如何测试你的程序

在终端下输入如下命令进行编译：

```bash
g++ grader.cpp koala.cpp -o grader -g -Wall --std=c++11
```

样例交互库将按如下格式从标准输入读入数据：

第一行两个整数 $F,G$，其中 $F$ 代表交互库调用的函数类型，$G$ 代表调用函数的次数；

接下来 $G$ 行，每行开头两个整数 $N,W$，后跟 $N$ 个整数 $P_0,P_1,\ldots,P_{N-1}$。

$F$ 对应的样例交互库调用的函数类型如下表所示：

| $F$ | 调用的函数类型 |
| ----------- | ----------- |
| $1$ | `minValue` |
| $2$ | `maxValue` |
| $3$ | `greaterValue` |
| $4$ | `allValues` |

对于每次函数调用，样例交互库将向标准输出输出两行。第一行代表你调用 `playRound` 的次数，第二行代表函数调用后返回的结构（对于 $F=4$ 的情况，将输出调用 `allValues` 时返回的数组，对于其他情况，将输出函数的返回值）。

### 样例

考虑如下的排列：

| $i$ | 0 | 1 | 2 | 3 | 4 | 5 |
| ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- |
| $P_i$ | 5 | 3 | 2 | 1 | 6 | 4 |

下表展示了几次调用函数 `playRound` 的例子，以及交互库对每个调用的有效反馈（注意，一次 `playRound` 的调用，可能会有多种可能的有效反馈） 。

| $W$ | 调用 | 可能的交互库反馈 | 解释 |
| ----------- | ----------- | ----------- | ----------- |
| 6 | `playRound([0,3,0,2,1,0],R)` | `R=[1,1,1,0,2,1]` | Koala 获得了物品 $0,2,4,5$，总权值为 $17$，这是一种可能的权值最大的方案。 |
| 6 | `playRound([1,2,3,1,2,0],R)` | 非法调用 | 你总共放了 $9$ 个石子，超过了 $W$ 的限制。 |
| 12 | `playRound([0,3,0,2,1,0],R)` | `R=[2,3,0,2,3,1]` | 你不用放完 $W$ 个石子，Koala 也不用放完 $W$ 个石子。 |
| 6 | `playRound([0,1,0,0,1,0],R)` | `R=[1,0,1,1,2,1]` | 若 Koala 有多种方案最大化获得物品的权值，她会选择使自己获得物品最多的方案。因此 `R=[1,2,0,0,2,1]` 不是一个合法的返回值。 |

下面是样例数据的返回值，请注意在样例数据中，你可以调用 `playRound` 至多 $3200$ 次。

| # | 交互库调用 | 期望返回值 | 解释 |
| ----------- | ----------- | ----------- | ----------- |
| 1 | `minValue(6,6)` | 3 | $P_3=1$ |
| 2 | `maxValue(6,6)` | 4 | $P_4=6$ |
| 3 | `greaterValue(6,6)` | 0 | $P_0=5,P_1=3$ |
| 4 | `allValues(6,12,P)` | `P=[5,3,2,1,6,4]` | 注意 `allValues` 无返回值，而是将正确结果放入 P 中。 |
| 5 | `allValues(6,12,P)` | `P=[5,3,2,1,6,4]` | 同上。 |

### 附加文件

附加文件包含样例输入输出，C++ 样例交互库和程序模板，我们推荐您在模板的基础上实现您的程序。


title: 文具订购（加强版）

type: P

background: 感谢@肖然 的创意以及@Elegia @dengyaotriangle 对算法复杂度论证做出的贡献（我只是搬题的

description:
小明的班上共有 $n$ 元班费，同学们准备使用班费集体购买 $3$ 种物品：

1. 圆规，每个 $x$ 元。
2. 笔，每支 $y$ 元。
3. 笔记本，每本 $z$ 元。

小明负责订购文具，设圆规，笔，笔记本的订购数量分别为 $a,b,c$，他订购的原则依次如下：

1. $n$ 元钱必须正好用光，即 $ax+by+cz=n$。
2. 在满足以上条件情况下，成套的数量尽可能大，即 $a,b,c$ 中的最小值尽可能大。
3. 在满足以上条件情况下，物品的总数尽可能大，即 $a+b+c$ 尽可能大。

请你帮助小明求出满足条件的最优方案。数据保证 $x>y>z$。若有多组解，应输出 $(a, b, c)$ 字典序最小的答案。

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

接下来 $T$ 行每行四个整数，依次为班费数量 $n$ ，三种物品价格 $x,y,z$。

outputFormat:
对于每组数据，如果问题无解，请输出 $-1$。

否则输出一行三个用空格隔开的整数 $a, b, c$，分别代表圆规、笔、笔记本的个数。

hint: 对于全部的测试点，$1\leq T\leq 100$，$0\leq n\leq 10^9 $ ，$1\leq z<y<x\leq 10^9$


title: 「HMOI R1」地铁客流

background:
一座城市的地铁客流量是非常重要的指标，它体现了这座城市正在不断流动着的人口数量。无论通勤还是旅游，都会给这座城市的经济带来活力。

疫情期间各地地铁客流惨淡，甚至有部分城市地铁停运。现在疫情态势好转，各地陆续复工复产，地铁客流量大小也是判断城市复工复产、经济恢复率的重要参考。

description:
天穹市的地铁系统由 $M$ 条线路组成，共有 $N$ 座车站，**每座车站都会有线路停靠**。每条线路的相邻两站之间可视为由无向边连接。其中地铁 $i$ 号线上有 $k_i$ 座车站，**这些车站互不相同**。

这些线路会在一些车站相交，也就是说，一座车站可能有很多线路停靠。

现在，有 $P$ 位乘客分别想从 $s_j$ 号车站出发，去 $t_j$ 号车站，**保证这两座车站不同**。当这两座车站不在一条线路上时，他就会进行若干次换乘。作为天穹地铁的技术工作人员，你需要计算这些乘客贡献的客流量。

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

请注意，在这里使用的客流量计算方法和实际应用中的有所不同。

客流量 $=$ 进站客流 $+$ 换乘客流。进站客流即为乘客数；换乘客流为乘客的换乘次数。起终点之间可能会有多条路径可以选择，此时，地铁客流量与 **乘客选择的** 路径无关；计算时，我们只考虑 **换乘次数最少** 的路径。

---------

注意：

- 设从 $s$ 到 $t$ 最少进行 $\rm trans$ 次换乘，则此时要乘坐 $\rm trans + 1$ 条线路，贡献 $\rm trans + 1$ 的客流量。
- 当乘客不能从起点到达终点时，即 $s, t$ 之间没有通路，他就会去坐公交，此时客流量计为 $0$。

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

接下来 $M$ 行，每行表示一条地铁线路：
每行第一个整数为 $k_i\ (2 \le k_i \le N)$，为这条线的车站数；
后面 $k_i$ 个整数 $q\ (1 \le q \le N)$，为这条线路依次经过的车站编号。

接下来 $P$ 行，每行两个整数 $s_j, t_j\ (1 \le s_j, t_j \le N;\ s_j \neq t_j)$，表示一位乘客的出行起终点。

outputFormat: 仅一行一个整数，表示这些乘客贡献的客流量。

hint:
样例解释：

- 默认乘客会选择换乘次数最少的路径。
- 边上的数字表示所在地铁线路的编号。

样例 1 如图：
![](https://cdn.luogu.com.cn/upload/image_hosting/t97d5qmr.png)

乘客 $1$ 会乘坐 $1$ 号线从 $1$ 到 $3$，再乘坐 $2$ 号线从 $3$ 到 $6$；
乘客 $2$ 会乘坐 $3$ 号线从 $4$ 到 $2$，再乘坐 $1$ 号线从 $2$ 到 $3$；
乘客 $3$ 会乘坐 $4$ 号线从 $4$ 到 $8$；
乘客 $4$ 会乘坐 $2$ 号线从 $6$ 到 $3$，乘坐 $1$ 号线从 $3$ 到 $2$，再乘坐 $3$ 号线从 $2$ 到 $4$，最后乘坐 $4$ 号线从 $4$ 到 $7$。

如上，四个人分别贡献了 $2, 2, 1, 4$ 的客流量，答案为 $9$。

样例 2 如图：
![](https://cdn.luogu.com.cn/upload/image_hosting/i0lm9un9.png)

相比样例 1，
乘客 $2$ 可以选择另外一条路线，即乘坐 $4$ 号线从 $4$ 到 $8$，再乘坐 $2$ 号线从 $8$ 到 $3$，也是换乘一次的；
乘客 $4$ 可以选择另外一条换乘次数更少的的路线：乘坐 $4$ 号线从 $7$ 到 $8$，再乘坐 $2$ 号线从 $8$ 到 $6$，只换乘了一次。

总客流量为 $2 + 2 + 1 + 2 = 7$。

样例 3 如图：
![](https://cdn.luogu.com.cn/upload/image_hosting/a2afk5k5.png)

相比样例 1，乘客 $2$ 和 $4$ 的出行路径不是通路，不会计入客流量。

总客流量为 $2 + 0 + 1 + 0 = 3$。

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

设车站 $i$ 停靠的线路数为 $\mathrm{siz}_i$。
对于所有数据：

- $2 \le N \le 10^5$；
- $1 \le M \le 1000$；
- $1 \le P \le 100$；
- $1 \le \mathrm{siz}_i \le 50$。

--------

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

| No.  | Constraints              | Score |
| ---- | ------------------------ | ----- |
| $1$  | $N, P \le 5;\ M \le 3$   | $10$  |
| $2$  | $k_i = 2$                | $20$  |
| $3$  | $N, M \le 50;\ P \le 10$ | $20$  |
| $4$  | $M \le 500;\ P \le 10$   | $20$  |
| $5$  | No further constraints   | $30$  |

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

由于读入量较大，请勿不关流同步使用 `cin`。

你可以通过 `std::ios::sync_with_stdio(false)` 来关闭 `cin` 的流同步。

你也可以使用以下快速读入模板，支持读入 `int` 范围内的非负整数。

```cpp
int readInt() {
	int ret = 0; char o;
	while (!isdigit(o = getchar()));
	do ret = ret * 10 + (o ^ 48);
	while (isdigit(o = getchar()));
	return ret;
}
```
----------

- Idea: 南桥汽车站
- Solution: 南桥汽车站
- Code: 南桥汽车站
- Data: 南桥汽车站


title: 「PMOI-5」分力

description:
平面直角坐标系上有一个半径为 $1$、圆心在 $(0,0)$ 的圆。

这个圆上等距标记了 $n$ 个红点，存在一个点落在 $x$ 正半轴上。

NaCly\_Fish 也站在 $(0,0)$ 上，等概率随机对着一个红点，用 $1 \text N$ 的力去推。

设她的推力在 $x$ 和 $y$ 轴上的分力分别为 $F_x$、$F_y$，她想知道这两个随机变量的 $k$ 阶中心矩分别是多少。

对于随机变量 $x$，其 $k$ 阶中心矩定义为 $E((x-E(x))^k)$，$E(x)$ 为 $x$ 的期望值。

可以证明答案**一定是有理数**，所以将答案要对 $998244353$ 取模。

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

outputFormat: 输出一行两个整数，分别表示 $F_x$ 和 $F_y$ 的 $k$ 阶中心矩的值。

hint:
【样例一解释】
二阶中心矩就是方差。由于只能朝着 $x$ 的正负方向推，$F_y$ 总是零，方差也就是零；$F_x$ 可以是 $\pm 1$，概率相等，方差就是 $1$。

【数据范围】

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

- Subtask 1（7 pts）：$2\le n,k \le 20$；
- Subtask 2（14 pts）：$2\le n \le 100$；
- Subtask 3（19 pts）：$2\le n \le 10^3$；
- Subtask 4（23 pts）：$2\le k \le 10^7$；
- Subtask 5（37 pts）：无特殊限制。

对于 $100\%$ 的数据，$2\le n \le 3 \times 10^4$，$2\le k \le 10^9$。


title: 「EZEC-2」机器

background:
tlx 喜欢科幻小说。

>小宇宙中只剩下漂流瓶和生态球。漂流瓶隐没于黑暗里,在一千米见方的宇宙中,只有生态球里的小太阳发出一点光芒。在这个小小的生命世界中,几只清澈的水球在零重力环境中静静地飘浮着,有一条小鱼从一只水球中蹦出,跃入另一只水球,轻盈地穿游于绿藻之间。在一小块陆地上的草丛中,有一滴露珠从一片草叶上脱离,旋转着飘起,向太空中折射出一缕晶莹的阳光。
>$\qquad \qquad \qquad \qquad \qquad \qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad --$《三体》

在另一个宇宙，将是另一番奇景吧。

在那里，重力似乎变得微不足道了，引力机器成了司空见惯的东西。

引力机器装置内并没有重力，即若有物体在机器上运动，运动过程中只受机器给予的引力，这个力有一定几率使物体向施力物体快速移动，达到一定动力时就可以实现瞬移。

description:
一个引力机器由一个光滑圆轨道和 $2n$ 个小孔组成（小孔按**逆时针**从 $1$ 到 $2n$ 编号，每两个相邻的小孔所夹的**劣弧**度数为 $\dfrac{\pi}{n}$ ），每个小孔与和其夹角为 $\pi$ 的另一个小孔有通道相连，比如当 $n=2$ 时，$1$ 号孔和 $3$ 号孔相连。

当 $n=2$ 时，这个装置的构造大概是这样的：

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

现在我们在 $1$ 号孔处放一个小球，使它一直**沿逆时针方向做匀速圆周运动**，在不瞬移的情况下，每一秒恰好能从一个小孔运动至下一个小孔。

由于未来实验室构造奇特（内部的引力提供装置太神了！），每经过一个小孔时，有 $p$ 的概率**立刻瞬移**（即不花费时间）到通道对面的小孔并继续沿逆时针方向做匀速圆周运动，也就是有 $1-p$ 的概率继续沿圆周向下一个小孔运动。

值得注意的是，**每一单位时刻，小球只能瞬移一次**。

简单地说，若某一时刻小球在小孔 $i$，则下一时刻它可能运动到小孔 $i \bmod 2n + 1$ 或 $(i + n) \bmod 2n + 1$，概率分别为 $1-p$ 和 $p$。

现在 tlx 有两个一模一样的引力机器，两个小球同时从 $1$ 号孔开始运动。他会**随机**（所有可能选择的概率相同）选择一个二元组 $(i,j)( 1\leqslant i\leqslant 2n,0\leqslant j\leqslant t,i,j\in \mathbb Z$ ) 分别代表小孔编号和时间，你需要求出时间为 $j$ 时两个引力机器的小孔 $i$ **同时**有小球**停留（运动经过小孔但瞬移到对面了不算停留）** 的概率。

注意：**小球刚开始运动时也可能瞬移到对面的小孔。**

为方便计算，我们规定：所有概率都是在模 $10^9+7$ 意义下的。

inputFormat: 输入数据共一行，三个整数 $n,p,t$，分别代表引力装置的小孔数的一半，瞬移的概率对 $10^9+7$ 取模的结果，选择的时间的范围的上界。

outputFormat: 共一行，一个整数，代表两个小球同时经过所选位置的概率对 $10^9+7$ 取模的结果。

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

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

具体计分方式如下：

- Subtask $1$ ($7$ points)：满足 $p\in \{0,1\}$；
- Subtask $2$ ($13$ points)：满足 $t\leqslant 20,n\leqslant50$；
- Subtask $3$ ($20$ points)：满足 $t\leqslant 10^3,n\leqslant50$；
- Subtask $4$ ($10$ points)：满足 $t\leqslant 10^3$；
- Subtask $5$ ($10$ points)：满足 $t\leqslant 10^6$；
- Subtask $6$ ($15$ points)：满足 $n\leqslant50$；
- Subtask $7$ ($25$ points)：无特殊限制。

对于 $100\%$ 的数据，满足 $2\leqslant n\leqslant 500$，$0\leqslant p\leqslant 10^9+6$，$0\leqslant t \leqslant 10^9$。

**注意：不做说明的数据范围即为极限数据范围。**

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

$500000004$ 是模 $10^9+7$ 意义下的 $\dfrac{1}{2}$。

下面为了方便，记 $P(i,j)$ 为选择的二元组为 $(i,j)$ 时的概率。

所有概率不为 $0$ 的二元组有：
$P(1,0)=\dfrac{1}{4},P(3,0)=\dfrac{1}{4},P(2,1)=\dfrac{1}{4},P(4,1)=\dfrac{1}{4}$。

所有可以选择的二元组有：
$(1,0),(1,1),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1)$，共 $8$ 种。

所以总的概率：
$$P=\dfrac{1}{8}×\dfrac{1}{4}×4+\dfrac{1}{8}×0×4=\dfrac{1}{8}$$

在模 $10^9+7$ 意义下为 $125000001$，即为输出的答案。

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

**【其他提示】**

1. 如果你不了解分数取模，可以查看[这里](https://www.luogu.com.cn/problem/P2613)。

2. 如果你不明白题目中角度的表示方法，可以查看[弧度制](https://baike.baidu.com/item/弧度制/3315973?fr=aladdin)。


title: 「SWTR-8」美元巨大

background:
#### 输出不允许有前导零。

原题目名称为「美元巨大二的二的二的二的二」。

小 A 喜欢用形如
$$
\Huge 2 ^ {2 ^ {2 ^ {2 ^ {2}}}}
$$
的幂塔把小 T 的博客炸掉。

description:
小 A 有 $n$ 个 $2$ 的幂 $a_1, a_2, \cdots, a_n$。他要在这些数之间插入 $x$ 个异或运算符和 $y$ 个或运算符，组成一个表达式。保证 $x + y = n - 1$。

表达式越大，越有可能炸掉小 T 的博客。小 A 希望 **从左往右** 计算表达式时它的值最大。他想知道表达式最大可能的取值是多少，用二进制表示。他还希望你构造出这样的表达式，因为他懒得自己构造了。

若存在多组构造方案，输出任意一组。

多组测试数据。

inputFormat:
第一行一个整数 $S$，表示该测试点的编号。

第二行一个整数 $T$，表示数据组数。接下来 $T$ 组测试数据，每组数据形如：

- 第一行三个整数 $n, x, y$。
- 第二行 $n$ 个整数 $b_i$，表示 $a_i = 2 ^ {b_i}$。

outputFormat:
对于每组测试数据：

- 第一行输出一个二进制数表示答案。**不允许有前导零**，除非答案为 $0$。
- 第二行输出一个长为 $n - 1$ 的由 `^` 和 `|` 组成的字符串，其中 $s_i = \texttt{\,\,\^{}\,\,}$ 表示 $a_i$ 与 $a_{i + 1}$ 之间的运算符为异或，$s_i = \texttt |$ 表示该运算符为或。你需要保证 `^` 的个数为 $x$，`|` 的个数为 $y$。

hint:
**「评分方式」**

对于每组测试数据：

- 若你输出的第一行比标准答案劣，得 0 分。
- 若你输出的第一行比标准答案优，则 checker 将检查你的构造方案是否正确。若正确，则返回 `_fail`，表现为测试点 UKE；否则得 0 分。
- 否则，你输出的第一行和标准答案一样。若构造方案不正确，得 0.6 分；否则得 1 分。

每个测试点的得分为测试点内所有测试数据的得分的最小值乘以该测试点的分值。

注意，checker 能检测出你的答案比标准答案优的前提是输出完全符合格式。**一旦输出不符合格式，得 0 分**。格式限制包括但不限于：

- 第一行不得输出除 `0` 和 `1` 以外的字符。
- 第二行不得输出除 `^` 和 `|` 以外的字符，且字符串长度恰为 $n - 1$。
- `^` 的个数恰为 $x$，`|` 的个数恰为 $y$。

**「数据范围与约定」**

- 测试点 #1（10 points）：所有 $b_i$ 互不相等。
- 测试点 #2（20 points）：所有 $b_i$ 相等。
- 测试点 #3（30 points）：$n \leq 8$。
- 测试点 #4（25 points）：$n \leq 10 ^ 3$。
- 测试点 #5（15 points）：无特殊限制。

对于 $100\%$ 的数据：

- $1\leq T\leq 20$。
- $1 \leq n \leq 2.5 \times 10 ^ 4$。
- $0 \leq x, y < n$，$x + y = n - 1$。
- $1\leq a_i < 2 ^ {2 ^ {2 ^ {2 ^ 2}}}$，即 $0\leq b_i < 65536$。

**「帮助与提示」**

- 关于 [位运算](https://oi-wiki.org/math/bit/)。
- 请注意 IO 优化。

**「题目来源」**

- [Sweet Round 8](https://www.luogu.com.cn/contest/73382) B
- Idea & Solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。
- Tester：[chenxia25](https://www.luogu.com.cn/user/138400)。


title: [YsOI2020] 幼儿园

description:
Ysuperman 热爱在 TA 的幼儿园里散步，为了更方便散步， TA 把幼儿园抽象成 $n$ 个点，$m$ 条边的**有向图**。 散步得多了， TA 就给了每一条边**无与伦比**的亲密程度：$1,2,\cdots,m$，越大代表越亲密。 TA 也给了每一个点无与伦比的编号：$1,2,\cdots,n$，其中 $1$ 代表着幼儿园大门，但是每个**点是没有亲密程度的**。

接下来 $k$ 天，Ysuperman 每天会有一次散步计划。具体而言， TA 希望从 $x_i$ 号点出发，只经过**亲密程度属于区间 $[l_i,r_i]$ 的边**，走到幼儿园大门 $1$ 号点，期间经过的边的亲密程度必须**单调递减**，不然会因为 TA 有强迫症而不能回家。

Ysuperman 看着自己刚刚画的草稿脑子一团浆糊， TA 发现 TA 始终没有办法规划出这么多合理路线，现在 TA 想请你帮 TA 。具体而言，对于每一天的计划，如果可行，则输出 `1`，反之输出 `0`。

当然啦，有的时候 Ysuperman 很着急，需要你立马回复，有的时候 TA 可以等等你，先把所有问题问完再等你回复。

inputFormat:
第一行三个整数 $n,m,k,w$，分别表示节点个数、边个数、Ysuperman 的计划个数，和 Ysuperman 的焦急程度，此处的 $w$ 在后续输入中有用。

此后 $m$ 行的第 $i$ 行有两个整数 $u_i,v_i$，表示 Ysuperman 的幼儿园里有一条 $u_i$ 号点到 $v_i$ 号点的单向边，且**亲密程度为** $i$。

此后 $k$ 行的第 $i$ 行有三个整数 $x_i,l_i,r_i$，表示 Ysuperman 的第 $i$ 个计划。

此处如果 $w=0$，则 $x_i,l_i,r_i$ 为明文，可以直接使用。

如果 $w=1$，则 $x_i,l_i,r_i$ 为密文，你需要将它解密。解密操作是：令 $L$ 为之前所有询问的输出之和（没有询问过则为 $0$），你需要将 $x_i ,l_i,r_i$ 都异或 $L$。

outputFormat: $k$ 行，每行只可能是 `1` 或 `0`，第 $i$ 行的数表示第 $i$ 个计划是否可行。


title: 谷歌翻(sheng)译(cao)机

background:
小 L 最近沉迷用谷歌生草机生草一些奇奇怪怪的东西。

小 L 在生草出了各式各样的作品后便开始考虑这样一个问题。

description:
**注：为了方便描述，下文所有字符串起始位置都为 $1$，即都从 $1$ 开始标号。**

小 L 将每次生草前的原文和生草后的结果看作两个**仅由小写字母组成**的两个字符串 $A$ 和 $B$。

我们按如下方式定义「分割数列」和「分割串」：

- 对于一个长度为 $n$ 的字符串，定义它的一条「分割数列」为：存在长度为 $k+2$ 的数列 $p$，使得 $0=p_0<p_1<p_2<...<p_k<p_{k+1}=n+1$。对于一条「分割数列」，定义其「分割串」为 $p_i+1$ 到 $p_{i+1}-1$ 之间字符构成的子串（$i \in[0,k]$，可以为空串）。显然，对于一条长度为 $k+2$ 的分割数列，一共有 $k+1$ 个分割串。

- 对于同一个字符串，两条分割数列（$p$ 和 $q$）不同**当且仅当两条数列长度不同（$k_1\neq k_2$）**，或**存在 $i$ 使得 $p_i\neq q_i$**。

不同人对于同样的原文和结果，他们的理解方式都是不同的。我们按如下方式定义一种理解方式：

- 对于字符串 $A$ 和 $B$，我们为这两个字符串各找一条分割数列（$p$ 和 $q$），这两个分割数列满足以下要求：
1. 两个分割数列长度相等（$k_1=k_2$）。
1. 对于任意 $i$，有 $A[p_i]=B[q_i]$，即 **$A$ 第 $p_i$ 个位置的字符与 $B$ 第 $q_i$ 个位置的字符相同**。

- 定义这种理解方式的「生草程度」为**此时两个字符串的所有分割串长度的平方和**，即 $\sum\limits_{i=0}^{k_1}(p_{i+1}-p_i-1)^2+\sum\limits_{i=0}^{k_2}(q_{i+1}-q_i-1)^2$。

- 两种理解方式不同**当且仅当**两种理解方式的 $p$ 不同，或两种理解方式的 $q$ 不同。

小 L 想要知道所有理解方式的生草程度之和的结果。由于他不喜欢 $10^9+7$ 这个数，他不希望你告诉他的结果会是这个数，所以你要将结果对 $10^9+7$ 取模。

inputFormat:
第一行有两个正整数 $n,m$ 分别为 $A$ 和 $B$ 的长度。

接下来一行有一个长度为 $n$ 的字符串，表示字符串 $A$。

接下来一行有一个长度为 $m$ 的字符串，表示字符串 $B$。

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


title: [YsOI2020] 换寝室

background: 马上要开学了，Ysuperman 正在为给孩子们分配寝室忙得不可开交......

description:
幼儿园里面有 $n$ 个房间，这些房间由 $n-1$ 条双向道路连接着，第 $i$ 条道路连接着房间 $u_i$ 和 $v_i$ ，每条道路 Ysuperman 都可以选择开启或者是关闭，每个房间**在所有道路开启的前提下**都可以到达其他任意一个房间。

每个房间有一个差异值，其中，第 $i$ 个房间的差异值为 $h_i$ 。

在选择完关闭哪些道路后，整个寝室会被分成许多连通块，一个联通块内的小朋友的不满意值定义为连通块内差异值的**最大值减去最小值**，小朋友们的总不满意值定义为**所有联通块不满意值的最大值**。

寝室里有 $m$ 个寝室老师，每个老师晚上都要查寝，第 $i$ 个老师会从第 $x_i$ 个房间走到第 $y_i$ 个房间，如果老师在查寝时经过了某条被关闭的道路，TA就会很生气，一个老师的不满意值定义为**从 $x_i$ 走到 $y_i$ 经过的被关闭的道路数量**，老师的总不满意值定义为**所有老师的不满意值之和**。

Ysuperman 能承受的老师的总不满意值最大为 $k$ ，现在TA想知道小朋友们的总不满意值最小可以达到多少。

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

第一行三个整数 $n,m,k$，表示房间个数，寝室老师个数和Ysuperman 能承受的老师的总不满意值。

接下来一行，共 $n$ 个整数，第 $i$ 个整数是 $h_i$，表示第 $i$ 个房间的差异值。

接下来 $n-1$ 行，每行两个整数，第 $i+2$ 行是 $u_i$ 和 $v_i$，表示寝室 $u_i,v_i$ 之间有直接道路。

接下来 $m$ 行，每行两个整数，第 $i+n+1$ 行是 $x_i$ 和 $y_i$，表示第 $i$ 个老师的查寝路线。

outputFormat: 一行一个整数，即答案。

hint:
### 样例说明

#### 样例说明 $1$

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

Ysuperman选择关闭连接着 $1$ 和 $5$ 的道路，老师的总不满意值为 $0$，寝室被分为 $2$ 个连通块，小朋友们的总不满意值为 $3$。

#### 样例说明 $2$

图同样例一。

Ysuperman选择关闭连接着 $1$ 和 $5$ 的道路以及连接着 $1$ 和 $4$ 的道路，老师的总不满意值为 $1$，寝室被分为 $3$ 个连通块，小朋友们的总不满意值为 $2$。

------
### 数据范围

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

| Subtask | $n$ | $m$ | $k$ | 特殊性质 | 分数 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| 1 | $\le 20$ | $\le 10$ | $\le 80$ | 无 | 8 |
| 2 | $\le 150$ | $\le 10^3$ | $\le 8 \times 10^4$ | 无 | 13 |
| 3 | $\le 800$ | $\le 10^5$ | $\le 8 \times 10^7$ | 树为一条链 | 13 |
| 4 | $\le 800$ | $\le 10^5$ | $\le 8 \times 10^7$ | 树为一朵盛开的菊花 | 13 |
| 5 | $\le 800$ | $\le 10^5$ | $= 0$ | 无 | 13 |
| 6 | $\le 800$ | $\le 10^5$ | $\le 8 \times 10^7$ | 无 | 40 |

【一条链】定义为：所有点的度数 $\le2$。

【一朵盛开的菊花】定义为：存在一个点的度数为 $n-1$。

对于 $100\%$ 的数据，满足 $1\le h_i\le 10^9，0\le k \le 8\cdot 10^7,u_i\ne v_i$ 。


title: [POI2007] 堆积木KLO

description:
PinkRabbit 从他的 npy 那里得到了一个由 $n$ 块积木叠成的高塔，每块积木上都写有一个数字。我们记从下往上第 $i$ 块积木上面的数为 $a_i$，将一个满足积木上的数为 $a_1,a_2,\dots,a_n$ 的高塔用 $\{a_1,a_2,\dots,a_n\}$ 直接表示，则 PinkRabbit 认为高塔 $\{a_1,a_2,\dots,a_m\}$ 价值为 $\sum_{i=1}^m [a_i = i]$。

PinkRabbit 可以删除当前高塔中的若干个积木，其余的积木受重力影响会下落到不能下落为止。如果将高塔 $\{1,1,2,4,5\}$ 中从下往上第二个积木删去，那么可以得到高塔 $\{1,2,4,5\}$，新高塔的价值为 $2$。

PinkRabbit 想删除当前高塔中任意个积木，使得最终得到的高塔价值最大。由于他是人赢，所以他指定你来回答这个问题。

inputFormat:
第一行一个正整数 $n$，表示初始高塔的高度。
第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$，其中 $a_i$ 表示初始状态从下往上第 $i$ 个积木上的数字。

outputFormat: 一行一个整数，表示可以得到的最大价值。

hint:
**样例 1 解释**
初始状态 $\{1,1,2,5,4\}$ 仅有 $a_1$ 满足 $a_i=i$，总价值为 $1$。
删去从下往上第二个积木，得到状态 $\{1,2,5,4\}$，$a_1,a_2,a_4$ 均满足 $a_i=i$，总价值为 $3$。
容易证明不存在更优的方案。

**数据规模与约定**
对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le a_i \le 10^6$。


title: [Ynoi2019] 美好的每一天~ 不连续的存在

background:
3.0321

虽然外面能在空间上表现一个违反物理规律的事态

但是外面不能在空间上表现一个违反几何规律的事态。

Ludwig Josef Johann Wittgenstein【逻辑哲学论】

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

……

透明的…

透明的白色？

…不…不对

这不是什么透明的白色…

是白色的话就不是透明……那么…这是半透明的…

但是…这也…并不是半透明…

如果…要找个唯一能表达的词语的话…

那就是…

透明的白色…

这是…那个啥…这是

“光”

【光】

光？

这是

单纯的光

是的……就是这样……

这是——

——光

蝉的叫声……

这里是…屋顶？

环顾四周…那是司空见惯的风景…是A栋的屋顶

为什么…为什么会在这里…

间宫皆守为了保护羽咲跳了下去…然后…，

然后…，

然后发生了什么？

今天是几号？那个，现在是…

我确认了下手表，日期是2012年7月20日。

从那时起…整整一天…

到底发生了什么…

梦……据说即使是明晰梦也少有能感觉到疼痛的……

捏脸蛋能感觉到疼的话，就说明这里的景色是现实吗……

音无彩名…同学

“好久不见”

“怎么了？”

因为啊…离我们最后一次见面不是才只过了一天吗…

“…这样啊”

…我说

“怎么？”

间宫皆守怎么样了？

“为什么…要问那种事？”

那，那当然是因为很在意啊…而且说到底我也只是他创造出来的人格罢了…

“那么他不就是还活着吗？”

你说…什么

“假设1…如果你…是间宫皆守创造出来的人格之一的话，你存在的这件事本身，就是间宫皆守的肉体还存在着的理由了…”

但，但是…这样很奇怪对吧

“哪里奇怪？”

因为啊…他都受了那么重的伤了啊。才过一天怎么可能能跑到这种地方来

“这样啊…”

我即使出现，也是应该是在医院的床上的

“那么假设2…你的存在不是因为解离性同一障碍而引起的…”

“你的存在正是过去实际存在过的人物，水上由岐的灵魂。如果这个灵魂是寄宿
在间宫皆守身上的…你存在于这里的理由换言之即…”

“意味着间宫皆守的死…”

怎，怎么会…

“还有假设3…如果这里只是你做的梦的话…”

“你眼前的我…也只是梦的产物…这个假设具有充分的说服力…”

“那么…水上由岐小姐喜欢将其中哪一种作为现状说明呢？”

喜欢哪种…我觉得更不是这种问题吧…

“假设4…你只是我所看见的幻觉…是我创造出来的幻影…也就是说你并不存在”

啊哈哈哈…那么，现在正在思考的我又成了什么呢？

不是有正在思考的我存在吗

“只不过是将我的大脑活动…的其中一部分，作为别的人格在认知而已…”

“也就是说“你正在思考”这件事，并不能证明你存在…”

“根本不能否定现在存在与此的水上由岐…是我创造出来的另一种人格的可能
性”

“这件事，在一具肉体里创造出三个人格的你应该是最能理解的…”

“自己正在思考这件事…并不能成为自己存在的证明…”

我说啊…我想知道的是

“什么？”

所以说，是在那之后怎么样了？

“你想要知道的话就确认一下吧…打开屋顶的门，跑到外面的世界去就可以了…
仅仅只需要这样而已”

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

…

正如音无彩名所言。

要是真的那么在意的话…我只要从这里离开就好了。

从这片屋顶上跑开，去看看外面的世界就行了。

这样做的话，应该就能如我所愿地…得知一切的结果了。

但是…

只要出去就行…吗

“嗯”

虽然这也是一种方法…但能让我问个问题吗？

“问什么？”

今天是几号？

“2012年7月20日…”

也就是说…从明天开始就是暑假了？

“对…从明天开始就是暑假…”

昨天…应该是发生了集体自杀。

根本不是还能安心地照常放暑假的那种小事。

尽管如此…从屋顶看到的风景却…

是一如既往的日常…

走在走廊上的学生。

在教室里谈话的学生。

喊学生来找他的老师。

这是毫无变化的日常。

实在是看不出像是刚发生了那种事件…

“怎么了吗”

…彩名同学的假设…就这么多了吗？

“假设…你还想要吗？”

“说明的话你想要听多少都行…对这个世界的注释…人们想要多少就可以增加到
多少”

“如果那是你的愿望的话…无论多少…”

卓司君说说的“终之空”是什么？

那个啊…是不管是琴美的预言还是白莲华协会的预言里都不存在的词语哦…

“终之空…就是字面上的”终结的天空””

那个名字…是谁在什么时候起的呢…

“记忆…”

记忆？

“幽灵房间…终之空…”

唔

“呵呵…你还记得”

不是记得…那应该是我记错了吧…

“是这样吗？”

因，因为，那个…很奇怪对吧？

“哪里奇怪？”

因为啊…那个…是我被卷入高岛同学的自杀时做的梦吧？

所以不是很奇怪吗

“有什么奇怪的吗？”

因为啊…如果那是，我已经被卷入高岛的自杀的话…时间轴就完全乱套了啊…因
为在那之后我又一次体验了高岛同学的自杀

“假设5…直到现在，你还没有从那个梦中醒来…”

那个梦？

“被卷入高岛柘榴自杀的水上由岐…现在这个瞬间正是她所做的梦的延续”

梦，梦？你说现在？不…不过怎么想，说这是梦也太…

“是吗…那么假设6…”幽灵房间…终之空”的记忆是错误的记忆…”

“只是反复进行人格替换缩引起的记忆的混乱让你做了这样的梦…”

“跳楼的高岛柘榴并没有撞上水上由岐，只是单纯的记忆混乱”

那，那么，为什么卓司君会使用只在我梦中出现过的“终之空”这个词啊！

“因为两者共享一个大脑，这样没有什么不可思议的…”

那，那样的话…

“你很在意最后看到的风景…那片天空的存在吗？”

咕

最后看见的…那片天空…

间宫卓司君在跳楼的一刹那看到的那种风景。

我不知为何觉得那种风景似曾相识…

“不断重复的世界…从某个地点开始…”

唔

“可以确认一下吗？”

什，什么？

“称呼你，水上由岐同学…可以吗？”

事，事到如今怎么这样问…你不是一直都这么叫我的吗…

“由岐同学…水上由岐同学是谁？”

哎？

“由岐同学…是过去实际存在的人物，为了救间宫羽咲而死亡…在那之后，又作
为间宫皆守所产生的人格而存在…”

“那样的话…现在存在与此的由岐同学是谁？是已经死去的由岐同学？还是作为
间宫皆守创造出来的人格的由岐同学？”

就，就算你这么问…我也不知道…

“正因为你不知道…才会问我…”

“最后的注释…”

“向由岐同学提问…”

“这个世界上存在着多少个由岐同学呢？”

哎？

“一个，是在泽衣村出生…并在泽衣村死去的水上由岐…另一个是作为间宫皆守
创造出来的人格的水上由岐…以及现在正在与我对话的存在与此的水上由岐”

“那么请听题…请问你是第几位水上由岐小姐呢？”

那，那种事我怎么知道…而且我就是我，才没有那么多人

“在泽衣村死去的由岐同学，在皆守体内的由岐同学，还有现在在此的由岐同学
是一样的…”

“那么，其他还有可能存在的由岐小姐呢？”

其他还有可能存在的我？

“对…其他人格所产生的由岐同学…那也是由岐同学吗？”

那种事我怎么知道…再说了要是有那么多我怎么受得了

“但是事实上你并不是一个人…”

“被卷入高岛柘榴的自杀的由岐同学，在泽衣村死去的由岐同学，皆守君制造出
的由岐同学…以及现在存在于此的由岐同学…”

那，那种事情我才不管…我就是我…

“在“幽灵房间…终之空”中看到的景色…那是什么时候的景色？”

景色？

唔

这时不知为何…我想起了那个游乐设备里的薯片袋子上的保质期…

想起了挂在那的挂历上的日期…

虽然完全不清楚那到底是什么…

不知为何…想起了那个时候的事情。

虽然不知道那句话到底有没有意义。

只是，想起了那个日期…

“最后附加上的注释”

“假设7…所有的存在都是由一个灵魂所产生的…”

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

天空，到底延伸到哪里呢...

大概，

是和全世界的天空连在一起的吧...

那样的话...这天空和——

——终之空

是没有连在一起的

要问为什么的话，

那是因为，

那是不可以存在的东西——

但是——

这又是真的吗？

“————”

某处传来呼唤我的声音。

呼唤我的同班同学的声音……

所以我回过头去……

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

description:
音无彩名给你一个数组 $A$，以及一棵 $n$ 个节点的树，每个点有一个颜色，颜色为 $1$ 到 $x$ 的整数。

有 $m$ 次查询，每次查询树上只保留 $[l,r]$ 内的所有节点，设一个极大连通块中出现奇数次数的颜色个数为 $t$，则其对答案的贡献为 $A_t$ ，即答案是所有连通块贡献的和，询问间互相独立。

inputFormat:
第一行三个用空格隔开的数 $n,m,x$。

第二行 $n$ 个数表示每个点的颜色。

之后 $n-1$ 行每行两个用空格隔开的数 $x,y$ 表示一条边。

之后一行 $x+1$ 个数表示 $A_0$ 到 $A_x$ 。

之后 $m$ 行，每行两个用空格隔开的数 $l,r$ 表示一次询问。

outputFormat: 输出 $m$ 行，每行一个数表示这次询问的答案。

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

注意：本题采用**捆绑测试**，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

对于其中 $1\%$ 的数据，为样例 1。

对于另外 $9\%$ 的数据，$n,m\leq 200$。

对于另外 $19\%$ 的数据，$n,m\leq 2000$。

对于另外 $19\%$ 的数据，$x\leq 10$。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$1\leq x,A_i \leq 10^4$。


title: [BalticOI 2017] Cat in a tree

description:
小猫在一棵有 $n$ 个节点的树上，它通过标记节点来划分领地。
它标记的节点满足彼此距离不小于 $d$。
两节点之间的距离指的是两点间路径上节点的个数（包括端点）。
求小猫最多能标记多少个节点。

inputFormat:
第一行两个整数代表节点数 $n$ 和标记的节点不超过的距离 $d$。
第 $0$ 个节点就是根节点，节点的编号为从 $0$ 到 $n - 1$。
接下来 $n-1$ 行，第 $i$ 行代表第 $i$ 个节点与哪个节点相连，一个数 $x_i$ 代表编号为 $i$ 的节点与编号为 $x_i$ 的节点相连。

outputFormat: 一行一个整数代表猫最多能标记多少个节点。

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

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

- Subtask 1（11 pts）：$n \le 18$。
- Subtask 2（40 pts）：$n \le 1500$。
- Subtask 3（49 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,d \le 2 \times 10^5$，$0 \le x_i < i$。

#### 说明

**翻译自 [BOI 2017 D2](https://boi.cses.fi/files/boi2017_day2.pdf) T1 Cat in a tree。**
翻译者：@[一只书虫仔](https://www.luogu.com.cn/user/114914)。


title: [BalticOI 2017] Friends

background:
高中就是要交最棒的朋友！
乌姆里奇校长要调查霍格沃茨学校的交友情况了！

description:
学校里有 $n$ 个同学，他们的交友情况满足以下的条件：

- 如果 $a$ 与 $b$ 是朋友那么 $b$ 与 $a$ 也是朋友；
- 同学们可以分成组，每个同学都恰好只在一个组里面，且：
	- 每个组的人数至少 $1$ 个最多 $p$ 个；
    - 每组都有这样最多 $q$ 对朋友满足一个人在这个组，另一个人在别的组。

在同一个组里的两个同学不一定必须是朋友。
现在她来问您，想让您说出这些学生撒没撒谎。
如果没有撒谎的话，她想让您给出一个合理的分组模式。

inputFormat:
第一行三个整数 $n,p,q$ 代表学生数，组别内学生的限制，和组别内不同组别朋友的限制。
学生的编号为从 $0$ 到 $n - 1$。
接下来 $n$ 行，从第 $0$ 个学生开始，首先一个整数 $m_i$ 代表这个学生与多少个学生为朋友，接下来 $m_i$ 个整数代表有哪些朋友。

outputFormat:
如果这些学生撒谎了，输出 `detention` 并结束程序。
如果这些学生没撒谎，首先输出 `home`。
然后一个整数 $G$ 代表这些学生可以分成 $G$ 组。
接下来 $G$ 行每行首先一个整数 $G'$ 代表这一组有几个学生，然后 $G'$ 个整数 $g_i$ 代表这一组学生的编号。
**任意输出一种方式即可。**

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

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

- Subtask 1（20 pts）：$n \le 16$。
- Subtask 2（37 pts）：$n \le 250$，$q \le 2$。
- Subtask 3（12 pts）：$q \le 2$。
- Subtask 4（31 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 2500$，$p+q \le 15$，$\sum m_i \le 30000$，同学们不以自己为朋友。

**本题使用 Special Judge。**

**说明**

**翻译自 [BOI 2017 D2](https://boi.cses.fi/files/boi2017_day2.pdf) T2 Friends。**
翻译者：@[一只书虫仔](https://www.luogu.com.cn/user/114914)。

spj 提示信息说明：
- `Accepted`：答案正确。
- `Wrong Answer[0]`：判断错误。
- `Wrong Answer[1]`：某些组的大小不符合要求。
- `Wrong Answer[2]`：组里含有编号不在 $0$ 到 $n-1$ 内的人。
- `Wrong Answer[3]`：某些人属于多个组。
- `Wrong Answer[4]`：某些人不属于任何组。
- `Wrong Answer[5]`：分组不满足要求。

spj 作者：@[FZzzz](https://www.luogu.com.cn/user/174045)。


title: [BalticOI 2017] Plus Minus

background: 物理学家马修正在研究硅基矩形微芯片的量子电动力学。

description:
这一块芯片的大小为 $n \times m$ ，可以分成 $n \times m$ 个电子。
我们都知道电子的状态只有正电 `+` 和负电 `-`。
所以，每一个电子都只有一个状态，`+` 或者 `-`。
马修不知道每个电子的状态，但他可以进行 $k$ 次测量。
第 $i$ 次测量他可以得到 $(y_i,x_i)$ 这个电子的状态 $s_i$。
（$s_i$ 是 `+` 或者 `-`）
马修还知道，在任意一个 $2\times2$ 的大小的电子块中，拥有 `+` 的电子和拥有 `-` 的电子数量相等。
然后他找到了您，想让您给出有多少种电子排列的形式满足测量的结果和上述要求。
答案对 $10^9+7$ 取模。

inputFormat:
第一行三个整数 $n,m,k$ 代表芯片的大小和测量次数。
接下来 $k$ 行每行一个字符 $s_i$ 代表这次测量得到的状态和 $y_i,x_i$ 代表测量的位置。

outputFormat:
一行一个整数代表有多少种电子排布的形式。
答案对 $10^9+7$ 取模。

hint:
#### 样例说明

对于样例 $1$，有以下 $2$ 种情况：
```
+-+-
+-+-
```
和
```
+-+-
-+-+
```

#### 数据规模与约定

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

- Subtask 1（12 pts）：$n,m \le 5$。
- Subtask 2（42 pts）：$n,m \le 1000$。
- Subtask 3（46 pts）：无特殊限制。

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

#### 说明

**翻译自 [BOI 2017 D2](https://boi.cses.fi/files/boi2017_day2.pdf) T3 Plus Minus。**
翻译者：@[一只书虫仔](https://www.luogu.com.cn/user/114914)。


title: [BalticOI 2017] Political Development

description:
某个有 $n$ 个成员的政党想要发展一些全新的政策。为了做到这一点，这个政党计划为了新的政策的发展，建立一个委员会。显然，当所有委员会委员的意见都不一致，并且这个委员会尽量大的时候，政策得以最好地发展。
为了指出哪一对政治家的意见不一致以及哪一对意见一致，政党安排每一对可能的政治家讨论一个随机选择的话题。无论何时，如果两个政治家不能在指定的话题上达成统一意见，他们就会被记录在政党的功德册上。
带着这本书，你被指定去完成找出最大的委员会，使得所有的委员的意见都不一致的任务。然而，找到一个大的委员会是非常有挑战的。仔细的分析结果显示，对于任意一个由党员所组成的非空的小组，存在至少一个小组成员，使得小组中与他的意见不一致的成员严格少于 $k$ 个。那么显然委员会不能有多于 $k$ 个成员。但是能够选出一个这个大小的委员会吗？找到最大的委员会的大小，使得其中没有人的意见是一致的。

---

一句话题意：

给一个图，满足对于任意点导出子图，存在一个节点的度数小于 $k$，求原图的最大团。

inputFormat:
第一行包含两个整数 $n$ 和 $k$，$n$ 表示点的个数，$k$ 如上所述。
每个点用一个 $0$ 到 $n-1$ 之间的整数 $i$ 表示。
接下来的 $n$ 行，每行描述一个点 $i$，从 $i=0$ 开始。第 $i$ 行以一个整数 $d_i$ 开始，接下来是 $d_i$ 个整数，表示与第 $i$ 个点相连的点。

outputFormat: 输出仅一行一个整数，表示原图的最大团。

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

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

- Subtask 1（4 pts）：$k \le 2$，$n \le 5 \times 10^3$。
- Subtask 2（12 pts）：$k \le 3$，$n \le 5 \times 10^3$。
- Subtask 3（23 pts）：$d_i \le 10$。
- Subtask 4（38 pts）：$n \le 5 \times 10^3$。
- Subtask 5（23 pts）：$ k \le 5$。

对于 $100\%$ 的数据，$0 \le d_i<n\le 5 \times 10^4$，$1 \le k \le 10$。

#### 说明

**翻译自 [BOI 2017 D1](https://boi.cses.fi/files/boi2017_day1.pdf) T1 Political Development。**
翻译者：@[FZzzz](https://www.luogu.com.cn/user/174045)。
~~所以这题提供者为什么还是菜鸡书虫呢，小编也不知道，欢迎私下跟小编讨论吖~~


title: [BalticOI 2017] Railway

background:
Bergen 基础设施建设部在一年前就有了把所有的城市用道路连起来的想法。
可惜的是，过了一年了，这个计划烂尾了。
所以，基础设施建设部部长就准备重启这个计划，然后把它搞得简单亿点。

description:
原定的计划是有 $n$ 个城市用 $n-1$ 个道路连起来。
现在有 $m$ 个副部长，每个副部长都认为有一些城市是必须连起来的。
比如说这个副部长想把 $a$ 和 $c$ 连起来，有两条道路 $a - b$ 和 $b - c$，那么副部长的要求等价过来就是选择这两条道路。
现在要找出几条道路是至少 $k$ 个副部长选择的。
部长就找到了您，想让您找出这几条道路。

inputFormat:
第一行三个整数 $n,m,k$ 代表城市数，副部长数和最少需要满足多少个副部长。
接下来 $n-1$ 行每行两个整数 $a_i$ 和 $b_i$ 代表第 $i$ 条道路是 $a_i$ 和 $b_i$ 之间的。
这 $n-1$ 个道路的编号就是 $1$ 到 $n-1$。
接下来 $m$ 行首先一个整数 $s_i$ 代表这个副部长觉得有 $s_i$ 个城市需要相连，接下来 $s_i$ 个整数代表副部长觉得哪些城市需要相连。

outputFormat:
第一行一个整数 $r$ 代表至少满足 $k$ 个副部长的道路有多少个。
第二行 $r$ 个整数代表要搭建编号为哪些的道路的升序排列。

hint:
#### 样例说明

$3$ 个副部长的要求如下：

- $1-3,2-3,3-4,4-5$
- $3-4,4-6$
- $2-3$

至少满足 $2$ 个副部长的道路为 $2$ 号和 $3$ 号。

#### 数据范围

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

- Subtask 1（8 pts）：$n \le 10^4$，$\sum s_i \le 2 \times 10^3$。
- Subtask 2（15 pts）：$n \le 10^4$，$m \le 2 \times 10^3$。
- Subtask 3（7 pts）：每个城市最多是 $2$ 条道路的端点。
- Subtask 4（29 pts）：$k=m$，$s_i=2$。
- Subtask 5（16 pts）：$k=m$。
- Subtask 6（25 pts）：无特殊限制。

对于 $100\%$ 的数据，$2 \le s_i \le n \le 10^5$，$1 \le k \le m \le 5 \times 10^4$，$\sum s_i \le 10^5$。

#### 说明

**翻译自 [BOI 2017 D1](https://boi.cses.fi/files/boi2017_day1.pdf) T2 Railway。**
翻译者：@[一只书虫仔](https://www.luogu.com.cn/user/114914)。

应扶咕咕的要求已经删减 $1 \sim 5$ 子任务中的部分数据，保留了 $6$ 子任务中的极限数据。


title: [BalticOI 2017] Toll

background: 作为一个合格的货运公司，在送达货物的同时也要让花的钱最少。

description:
这座城市有 $n$ 个地点，这 $n$ 个地点之间有 $m$ 条边。
货运公司接到了 $o$ 个订单，他们要想方设法的让路途中花的钱最少。
对于每条路，都有三个信息：
- $a,b$ 代表从 $a$ 连到 $b$；
- $t$ 代表这条路需要多少钱。

并且对于每个订单，都给出 $a$ 和 $b$ 代表要把物品从 $a$ 运到 $b$ ，求每个订单需要花的最少的钱；如果无法送达就输出 $-1$。
特别的，对于两个编号为 $a,b$ 的路，一定满足：
$$\left\lfloor\dfrac{b}{k}\right\rfloor=1+\left\lfloor\dfrac{a}{k}\right\rfloor$$
（$k$ 是一个给定的常数）。

inputFormat:
第一行四个整数 $k,n,m,o$ 代表一个常数，地点的个数，边的个数，订单的个数。
点的编号为从 $0$ 到 $n - 1$。
接下来 $m$ 行每行三个整数 $a,b,t$ 代表从 $a$ 连向 $b$ 要花费 $t$，保证满足 $\left\lfloor\dfrac{b}{k}\right\rfloor=1+\left\lfloor\dfrac{a}{k}\right\rfloor$，并且两点之间连接的边数不超过 $1$ 条边。
接下来 $o$ 行每行两个整数 $a,b$ 代表要从 $a$ 运货到 $b$。

outputFormat: 对于每个订单，输出一行一个整数表示答案。

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

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

- Subtask 1（7 pts）：$k=1$。
- Subtask 2（10 pts）：每个订单中的 $a=0$。
- Subtask 3（8 pts）：$o \le 100$。
- Subtask 4（31 pts）：$o \le 3000$。
- Subtask 5（44 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 50000$，$1 \le o \le 10000$，$1 \le k \le 5$，$0 \le a < b < n$，$1 \le t \le 10000$。

#### 说明

**翻译自 [BOI 2017 D1](https://boi.cses.fi/files/boi2017_day1.pdf) T3 Toll。**
翻译者：@[一只书虫仔](https://www.luogu.com.cn/user/114914)。
**本题强制 $O2$ 优化。**


title: [清华集训2016] 温暖会指引我们前行

background:
寒冬又一次肆虐了北国大地

无情的北风穿透了人们御寒的衣物

可怜虫们在冬夜中发出无助的哀嚎

“冻死宝宝了！”

这时

远处的天边出现了一位火焰之神

“我将赐予你们温暖和希望！”

只见他的身体中喷射出火焰之力

通过坚固的钢铁，传遍了千家万户

这时，只听见人们欢呼

“暖气来啦！”

description:
虽然小 R 住的宿舍楼早已来了暖气，但是由于某些原因，宿舍楼中的某些窗户仍然开着（例如厕所的窗户），这就使得宿舍楼中有一些路上的温度还是很低。

小 R 的宿舍楼中有 $n$ 个地点和一些路，一条路连接了两个地点，小 R 可以通过这条路从其中任意一个地点到达另外一个地点。但在刚开始，小 R 还不熟悉宿舍楼中的任何一条路，所以他会慢慢地发现这些路，他在发现一条路时还会知道这条路的温度和长度。每条路的温度都是互不相同的。

小 R 需要在宿舍楼中活动，每次他都需要从一个地点到达另一个地点。小 R 希望每次活动时经过一条最温暖的路径，最温暖的路径的定义为，将路径上各条路的温度从小到大排序后字典序最大。即温度最低的路温度尽量高，在满足该条件的情况下，温度第二低的路温度尽量高，以此类推。小 R 不会经过重复的路。由于每条路的温度互不相同，因此只存在一条最温暖的路径。

对于小 R 的每次活动，你需要求出小 R 需要走过的路径总长度。如果小 R 通过当前发现的路不能完成这次活动，则输出  `−1`。

注意本题中的字典序与传统意义上的字典序定义有所不同，对于两个序列 $a,b(a≠b)$，若 $a$ 是 $b$ 的前缀则 $a$ 的字典序较大，同时可以推出空串的字典序最大。

inputFormat:
第一行两个正整数 $n,m$。表示小 R 的宿舍楼中有 $n$ 个地点，共发生了 $m$ 个事件。

接下来 $m$ 行，每行描述一个事件，事件分为三类。

- `find id u v t l` 表示小 R 发现了一条连接 $u$ 和 $v$ 之间的路，编号为id。相同id的边只会出现一次。
- `move u v` 表示小 R 要从 $u$ 到达 $v$，你需要计算出最温暖的路径的长度 ，若不能从 $u$ 到达 $v$，则输出 `−1`。
- `change id l` 表示从 $u$ 到 $v$ 这条边的长度变为了 $l$（保证在当前时间点这条边存在）。

outputFormat: 对于每个询问，输出一行整数，表示最温暖的路径长度。

samples:
8 19
find 0 0 2 7 2
find 1 2 4 4 4
find 2 4 6 10 1
find 3 6 7 8 6
move 2 7
move 1 6
find 4 2 5 3 4
move 0 5
change 0 12
find 5 4 5 5 10
find 6 2 3 6 9
move 3 5
find 7 0 1 12 1
move 1 6
find 8 1 7 11 100
move 1 6
move 3 7
move 5 6
move 2 2


title: [清华集训2016] Alice 和 Bob 又在玩游戏

description:
Alice 和 Bob 在玩游戏。

有 $n$ 个节点，$m$ 条边 $(0\le m\le n-1)$ ，构成若干棵有根树，每棵树的根节点是该连通块内编号最小的点。Alice 和 Bob 轮流操作，每回合选择一个没有被删除的节点 $x$，将 $x$ 及其所有祖先全部删除，不能操作的人输。

注：树的形态是在一开始就确定好的，删除节点不会影响剩余节点父亲和儿子的关系。比如：$1-3-2$ 这样一条链
，$1$ 号点是根节点，删除 $1$ 号点之后，$3$ 号点还是 $2$ 号点的父节点。

问有没有先手必胜策略。

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

第一行一个正整数 $T$，表示该测试点有 $T$ 组数据；接下来 $T$ 组数据。

对于每组数据：

输入第一行两个整数 $n, m$，分别表示点数和边数（节点从 $1$ 开始编号）。

接下来 $m$ 行，每行两个正整数 $a, b$，表示节点 $a$ 和节点 $b$ 之间有一条边，输入数据中没有重边。

outputFormat: 输出 $T$ 行，每行输出 Alice 先手并且 Alice 和 Bob 都足够聪明的情况下谁获胜。

hint:
#### 样例解释

第一组数据输入是一条链，Alice 可以一次性把所有节点都删掉。

第二组数据，Alice 先手第一步删除 $1$ 号点即可胜利。

#### 数据范围

对于 $100\%$ 的数据，$1≤T≤10$，$1≤n≤10^5$，$∑n≤2×10^5$，$0≤m≤n−1$，输入数据保证不会形成环，且每棵树的大小 $≤5×10^4$。


title: [NOI Online #3 入门组] 最急救助

description:
救助中心每天都要收到很多求救信号。收到求救信号后，救助中心会分析求救信号，找出最紧急的求救者给予救助。

求救信号是一个由小写英文字母组成的字符串，字符串中连续三个字符依次组成`sos`的情况越多（即包含子串`sos`的数目越多），代表着求救者情况越紧急。

现在请你帮助救助中心找出最紧急的求救者。注意字符串中包含的`sos`可以有重叠，例如`sosos`算作包含 $2$ 个`sos`。

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

第一行一个整数 $n$，表示求救者的数目。

接下来有 $2\times n$ 行，每行一个由小写英文字母组成的字符串。这 $2\times n$ 行中，第 $2\times i-1$（$1\le i\le n$）行的字符串表示第 $i$ 个求救者的名字，第 $2\times i$ 行的字符串表示第 $i$ 个求救者的求救信号。

outputFormat:
输出到标准输出。

输出共两行，第一行是最紧急求救者的名字。如果最紧急求救者有多个，则按照输入的顺序将他们的名字依次输出，相邻两个名字间用空格分隔。

第二行一个整数，表示最紧急求救者的求救信号中包含有多少个`sos`子串。

samples:
2
adam
ineedhelpsosineedhelpsos
mark
ineedmorehelpsoshelpmesossoshelpme

samples:
3
susan
sosososososos
jack
sossossossos
allen
soshelpsossossossossos

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

- 对于 $10\%$ 的数据，$n=1$。
- 对于所有数据，$1 \leq n\le 100$，求救者名字长度不超过 $20$，求救信号长度不超过 $200$。


title: [NOI Online #3 入门组] 观星

background: 脚造数据一组，欢迎hack

description:
Jimmy 和 Symbol 约好一起看星星，浩瀚的星空可视为一个长为 $N$、宽为 $M$ 的矩阵，矩阵中共有 $N\times M$ 个位置，一个位置可以用坐标 $(i,j)$（$1\le i\le N$，$1\le j\le M$）来表示。每个位置上可能是空的，也可能有一个星星。

对于一个位置 $(i,j)$，与其相邻的位置有左边、左上、上面、右上、右边、右下、下面、左下 8 个位置。相邻位置上的星星被视为同一个星座，这种关系有传递性，例如若 $(1,1),(1,2),(1,3)$ 三个
位置上都有星星，那么这三个星星视为同一个星座。包含的星星数量相同的星座被视为一个星系（一个星系中的星座不一定相邻），星系的大小为星系中包含的所有星星数量。

由于 Symbol 太喜欢星系了，他就想考一考 Jimmy，让 Jimmy 求出星空中有多少个星系，他还想知道，最大的星系有多大。

inputFormat:
第一行两个整数 $N,M$ 表示矩阵的长宽。

接下来 $N$ 行每行 $M$ 个字符，每个字符只可能是`.`或`*`。这 $N$ 行中第 $i$ 行的第 $j$ 个字符是`*`表示位置 $(i,j)$ 上有一个星星，否则表示它是空的。

outputFormat: 仅一行两个整数，用空格分隔开，分别表示星系的数量与最大星系的大小。

hint:
对于 $20\%$ 的数据，$N,M\le 20$，最大星系大小不超过 200。

对于 $50\%$ 的数据，$N,M\le 400$。

对于 $70\%$ 的数据，$N,M\le 1100$。

对于 $100\%$ 的数据，$2\le N,M\le 1500$，最大星系大小不超过 100000。


title: [NOI Online #3 入门组] 买表

description:
Jimmy 到 Symbol 的手表店买手表，Jimmy 只带了 $n$ 种钱币，第 $i$ 种钱币的面额为 $k_i$ 元，张数为 $a_i$ 张。Symbol 的店里一共有 $m$ 块手表，第 $i$ 块手表的价格为 $t_i$ 元。

Symbol 的手表店不能找零，所以 Jimmy 只能在凑出恰好的钱数时才能购买一块手表。现在对于店里的每块手表，Jimmy 想知道他能不能凑出恰好的钱数进行购买。

inputFormat:
第一行两个空格分隔的整数 $n$ 和 $m$ 表示钱币数与手表数。

接下来 $n$ 行每行两个空格分隔的整数 $k_i$ 和 $a_i$ 表示钱币的面额和张数。

第 $n+2$ 行，共 $m$ 个用空格分隔的整数 $t_i$，表示每块手表的价格。

outputFormat: 一共 $m$ 行，对于第 $i$ 行，如果能凑出恰好的钱数购买第 $i$ 块手表则输出 `Yes` 否则输出 `No`，注意只有首字母大写。

hint:
#### 样例 1 解释

- 第二块手表 $19=6 \times 3+1=6 \times 2+5+1 \times 2$，可以恰好凑出。
- 第四块手表 $1=1 \times 1$，可以恰好凑出。
- 第五块手表 $7=5+2\times 1=6 \times 1+1$，可以恰好凑出。

#### 数据规模与约定
- 对于 $50\%$ 的数据，保证 $n\leq 10$，$m \leq 60$，$a_i \leq 20$，$k_i \leq 5000$，$t_i \leq 250$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 200$，$1 \leq m \leq 10^5$，$1 \leq a_i \leq 1000$，$1 \leq k_i \leq 500000$，$0 \leq t_i \leq 500000$。

#### 说明

data provider：@皎月半洒花。


title: [NOI Online #3 提高组] 水壶

description:
有 $n$ 个容量无穷大的水壶，它们从 $1\sim n$ 编号，初始时 $i$ 号水壶中装有 $A_i$ 单位的水。

你可以进行不超过 $k$ 次操作，每次操作需要选择一个满足 $1\le x\le n-1$ 的编号 $x$，然后把 $x$ 号水壶中的水全部倒入 $x+1$ 号水壶中。

最后你可以任意选择恰好一个水壶，并喝掉水壶中所有的水。现在请你求出，你最多能喝到多少单位的水。

inputFormat:
第一行一个正整数 $n$，表示水壶的个数。

第二行一个非负整数 $k$，表示操作次数上限。

第三行 $n$ 个非负整数，相邻两个数用空格隔开，表示水壶的初始装水量 $A_1$, $A_2$, $\cdots$, $A_n$。

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

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

- 对于 $10\%$ 的数据，保证 $n \leq 10$。
- 对于 $30\%$ 的数据，保证 $n \leq 100$。
- 对于 $50\%$ 的数据，保证 $n \leq 10^3$。
- 对于 $70\%$ 的数据，保证 $n \leq 10^5$。
- 对于 $100\%$ 的数据，保证 $1\leq n\leq 10^6$，$0\leq k \leq n-1$，$0\le A_i\le 10^3$。


title: [NOI Online #3 提高组] 魔法值

description:
H 国的交通由 $n$ 座城市与 $m$ 条道路构成，城市与道路都从 $1$ 开始编号，其中 $1$ 号城市是 H 国的首都。H 国中一条道路将把两个不同城市直接相连，且任意两个城市间至多有一条道路。

H 国是一个信奉魔法的国家，在第 $j$ 天，$i$ 号城市的魔法值为 $f_{i,j}$。H 国的魔法师已观测到第 0 天时所有城市的魔法值 $f_{i,0}$，且他们还发现，之后的每一天每个城市的魔法值，都将会变为所有与该城市直接相连的城市的前一天魔法值的异或值，即

$$
f_{x,j}=f_{v_1,j-1}\oplus f_{v_2,j-1}\oplus \cdots\oplus f_{v_k,j-1}
$$

其中 $j\ge 1$，$v_1,v_2,\cdots,v_k$ 是所有与 $x$ 号城市直接相连的城市，$\oplus$ 为异或运算。

现在 H 国的国王问了你 $q$ 个问题，对于第 $i$（$1\le i\le q$）个问题你需要回答：第 $a_i$ 天时首都的魔法值是多少。

inputFormat:
第一行三个用空格分隔的整数 $n,m,q$，表示城市数、道路数与问题数。

第二行 $n$ 个用空格分隔的整数，第 $i$ 个整数表示 $f_{i, 0}$。

接下来 $m$ 行，每行两个用空格分隔的正整数 $u,v$，表示一条连接 $u$ 号城市与 $v$ 号城市的道路。

接下来 $q$ 行每行一个整数，第 $i$ 行的整数表示 $a_i$。

outputFormat: 按顺序输出 $q$ 行每行一个整数，表示对应问题的答案。

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

- 对于 $20\%$ 的数据，满足 $a_i \leq 100$。
- 对于 $40\%$ 的数据，满足 $n \leq 20$。
- 另有 $30\%$ 的数据，满足 $m=\frac{n(n-1)}{2}$。
- 对于 $100\%$ 的数据，满足 $1 \leq n,q \leq 100$，$1 \leq m \leq \frac{n(n-1)}{2}$，$1\leq a_i < 2^{32}$，$0\leq f_i < 2^{32}$。

#### 说明

data provider ：@一扶苏一，数据有锅请联系她。如果被朴素的快速幂水过去了也请联系她。


title: [NOI Online #3 提高组] 优秀子序列

description:
给定一个长度为 $n$ 的非负整数序列 $A=\{a_1,a_2,\cdots,a_n\}$，对于 $A$ 的一个子序列 $B=\{a_{b_1},a_{b_2},\cdots,a_{b_m}\}$（$0\le m\le n$，$1\le b_1<b_2<\cdots<b_m\le n$，下同），称 $B$ 是 $A$ 的优秀子序列当且仅当，其任意两个不同元素的按位与结果均为 $0$，即：$\forall 1\le i<j\le m$，满足：$a_{b_i}~\mathrm{and}~a_{b_j}=0$，其中 $~\mathrm{and}~$   是按位与运算。

对于子序列 $B=\{a_{b_1},a_{b_2},\cdots,a_{b_m}\}$，我们定义其价值为 $\varphi(1+\sum_{i=1}^m a_{b_i})$，其中 $\varphi(x)$ 表示小等于 $x$ 的正整数中与 $x$ 互质的数的个数。

现在请你求出 $A$ 的所有优秀子序列的价值之和，答案对 $10^9+7$ 取模。

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

第二行 $n$ 个用空格分隔的非负整数，表示 $a_1,a_2,\cdots,a_n$。

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


title: 「JYLOI Round 1」箭头调度

description: moyu_028 给了你一个有 $n$ 个点 $m$ 条边的无向图，现在要给每条边赋一个方向，现在请你求出一个赋方向的方案，使得按照这个方案能够生成一个拓扑序，且使得这个拓扑序是在所有可能的拓扑序中字典序第 $k$ 小的。

inputFormat:
输入的第 1 行有 3 个正整数 $n$、$m$、$k$，含义如题所述。

接下来有 $m$ 行，这 $m$ 行中的第 $i$ 行有两个正整数 $x_i$ 和 $y_i$，表示有一条从 $x_i$ 到 $y_i$ 的无向边。

outputFormat: 输出为一行一个长度为 $m$ 的 01 串，这个 01 串中的第 $i$ 个字符表示从 $x_i$ 和 $y_i$ 之间的无向边的方向，为 0 则表示这条边是从 $x_i$ 到 $y_i$，为 1 则表示这条边是从 $y_i$ 到 $x_i$。可以证明答案唯一，且数据保证有解。

hint:
## 提示

拓扑序：在一个 DAG（有向无环图）中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 $u$ 到 $v$ 的有向边 $(u,v)$，都可以有 $u$ 在 $v$ 的前面，则这样的序列称为拓扑序。

----------

## 样例解释

### 样例 1 解释

答案的图如下，根据图可得出答案。

![](https://i.loli.net/2020/05/23/3FK2n78JAYLrGMD.png)

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

## 数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 11, 1 \leq m \leq 2 \times 10^3, 1 \leq k \leq 10^8，1 \leq x_i, y_i \leq n, x_i \not= y_i$。

对于测试点 1（10 分）：$n = 1$。

对于测试点 2（30 分）：$n \leq 11, m \leq 20$。

对于测试点 3（30 分）：$n \leq 11, k = 1$。

对于测试点 4（30 分）：无特殊限制。

本题共 4 个测试点，总分为 100 分，单个测试点的时间限制为 5 秒。

## 题目来源

「JYLOI Round 1」 A

Idea：moyu_028 & abcdeffa

Solution：LiuXiangle

Data：abcdeffa


title: 图的存储与出边的排序

type: B

description:
给定一个 $n$ 个点 $m$ 条边的有向图 $G$，结点编号从 $1$ 至 $n$。对于 $u = 1, 2, 3, \dots n$，依次完成如下要求：
对于 $u$ 的所有出边（即从 $u$ 出发的边），按照**从小到大**的顺序输出出边所指向的节点编号。

**依次完成**的含义是，先按顺序输出 $u = 1$ 的出边所指向的点的编号，再按顺序输出 $u = 2$ 的出边所指向的点的编号……最后按顺序输出 $u = n$ 的出边所指向的点的编号。

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

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

对于每组数据的格式如下：
每组数据的第一行是两个整数，分别表示点的个数 $n$ 和边的个数 $m$。
接下来 $m$ 行，每行两个整数 $u, v$，表示一条由 $u$ 指向 $v$ 的边。

保证每组数据内不存在重边。

outputFormat:
对于每组数据：
输出 $n$ 行，每行若干个用空格隔开的整数。第 $i$ 行输出节点 $i$ 的出边所指向的节点编号。

**注意，如果一个结点不存在出边，你同样需要输出一个空行**。

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

对于全部的测试点，保证 $1 \leq T, n, m \leq 5 \times 10^5$，但同时各测试点的 $n$ 与 $m$ 之和均不超过 $5 \times 10^5$，即 $\sum n, \sum m \leq 5 \times 10^5$。且 $1 \leq u, v \leq n$，每组数据内不存在重边。

### 提示

请注意大量读入输出对程序效率造成的影响。


title: 【模板】栈

description:
请你实现一个栈（stack），支持如下操作：
- `push(x)`：向栈中加入一个数 $x$。
- `pop()`：将栈顶弹出。如果此时栈为空则不进行弹出操作，输出 `Empty`。
- `query()`：输出栈顶元素，如果此时栈为空则输出 `Anguei!`。
- `size()`：输出此时栈内元素个数。

inputFormat:
**本题单测试点内有多组数据**。
输入第一行是一个整数 $T$，表示数据组数。对于每组数据，格式如下：
每组数据第一行是一个整数，表示操作的次数 $n$。
接下来 $n$ 行，每行首先由一个字符串，为 `push`，`pop`，`query` 和 `size` 之一。若为 `push`，则其后有一个整数 $x$，表示要被加入的数，$x$ 和字符串之间用空格隔开；若不是 `push`，则本行没有其它内容。

outputFormat: 对于每组数据，按照「题目描述」中的要求依次输出。每次输出占一行。

samples:
2
5
push 2
query
size
pop
query
3
pop
query
size

hint:
### 样例 1 解释
对于第二组数据，始终为空，所以 `pop` 和 `query` 均需要输出对应字符串。栈的 size 为 0。

### 数据规模与约定

对于全部的测试点，保证 $1 \leq T, n\leq 10^6$，且单个测试点内的 $n$ 之和不超过 $10^6$，即 $\sum n \leq 10^6$。保证 $0 \leq x \lt 2^{64}$。

### 提示
- 请注意大量数据读入对程序效率造成的影响。
- 因为一开始数据造错了，请注意输出的 `Empty` 不含叹号，`Anguei!` 含有叹号。


title: [COCI2013-2014#6]  FONT

description:
我们定义测试句为包含所有小写英文字母的字符串。

现在给你 $N$ 个单词，请问这些单词最多能组成多少个测试句。

每个单词只能在测试句中使用一次，而单词在句子中的顺序不考虑，即 `uvijek jedem sarmu` 和 `jedem sarmu uvijek` 是相等的。

inputFormat:
输入的第一行包含整数 $N$，即单词个数。

接下来 $N$ 行，每行一个单词，其长度不超过 $100$ 。

保证所有单词不同。

outputFormat: 输出最多能组成多少个测试句。

samples:
9
the
quick
brown
fox
jumps
over
a
sleazy
dog

samples:
15
abcdefghijkl
bcdefghijklm
cdefghijklmn
defghijklmno
efghijklmnop
fghijklmnopq
ghijklmnopqr
hijklmnopqrs
ijklmnopqrst
jklmnopqrstu
klmnopqrstuv
lmnopqrstuvw
mnopqrstuvwx
nopqrstuvwxy
opqrstuvwxyz

hint:
#### 【数据范围与约定】
$1\le N\le 25$。
#### 【样例解释】

#### 样例 1 解释

除 `a` 外的所有单词都必须在测试句子中使用，因为每个单词都包含一个在其他单词中找不到的字母。因此，有两个方案。第一个是包含所有单词的句子，第二个是由除 `a` 之外的所有单词组成的句子。

#### 样例 3 解释
这个样例由英语小写连续字母组成。

#### 【说明】

**题目译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #6](https://hsin.hr/coci/archive/2013_2014/contest6_tasks.pdf) _T2  FONT。_**


title: [COCI2013-2014#6] KRUŽNICE

description: 现在有 $N$ 个以 $x$ 轴为中心的互不相交的圆，但圆周可以接触。请问这些圆把平面分成多少块？

inputFormat:
输入的第一行包含整数 $N$，即圆的数目。

下列n行中的每一个包含两个整数 $x_i$ 和 $r_i$， $x_i$ 表示第 $i$ 个圆的 $x$ 坐标，$r_i$ 表示第 $i$ 个圆的半径。

输入中的所有圆保证都是唯一的。

outputFormat: 输出这些圆把平面分成多少区域。

hint:
#### 【样例解释】
#### 样例 3 解释
该样例对应下图：

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

#### 【数据规模与约定】
- 对于 $40\%$ 的数据，$1 \le N \le 5\times 10^3$。
- 对于 $100\%$ 的数据，$1 \le N \le 3\times 10^5,-10^9 \leq x_i \leq 10^9$，$1 \leq r_i \leq 10^9$。
#### 【说明】
**题目译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #6](https://hsin.hr/coci/archive/2013_2014/contest6_tasks.pdf) _T4 KRUŽNICE。_**


title: [COCI2013-2014#6] GRAŠKRIŽJA（征集spj）

description:
有很多纵横交错的街道，街道均为双向。水平和垂直街道的交叉口称为十字路口。

现决定在 $N$ 个十字路口设红绿灯，若两个十字路口间的一条路无红绿灯则转弯危险，反之安全。

只要在每两个红绿灯之间有至少一条最短的路径是安全的就符合要求，你需要设置一些额外的红绿灯以满足要求。

inputFormat:
第一行输入由整数 $N$ 组成，即最初的红绿灯数。

接下来 $N$ 行，每行两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个红绿灯的坐标。

所有的红绿灯的坐标互不相同。

outputFormat: 输出新红绿灯的位置，允许在同一位置放置多个红绿灯，新增红绿灯数量必须少于 $7\times 10^5$ 个。

hint:
#### 【数据规模与约定】
- $2 \leq N \leq 5\times 10^4$。
- $1 \leq x_i,y_i \leq 5\times 10^4$。
#### 【说明】

**题目译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #6](https://hsin.hr/coci/archive/2013_2014/contest6_tasks.pdf) _T6 GRAŠKRIŽJA。_**


title: 选择题

background:
小 L 喜欢逻辑推理。

一天，他在一本由英国哲士沃·协德编写的《我也不知道为什么要叫这个名字的一本有关逻辑学的书》中翻到了一道奇特的问题，但他并不会做。他知道你善于用程序解决问题，于是决定让你来帮助他完成这些问题。

description:
这是一道有 $n$ 个选项的选择题，每个选项的内容都很独特。第 $i$ 个选项的内容的形式如下：

+ 第 $a_i$ 个选项是正确/错误的

小 L 认为这种题目的答案不一定是唯一的，所以他想问题这道题有多少种合法的答案（可以全部正确或全部错误）。他还想问你这么多答案中，正确选项最多和最少的答案分别有多少个正确选项。

当然，如果这道题不存在合法的答案，你可以直接回答小 L `No answer`。

inputFormat:
第一行有一个正整数 $n$，表示选项个数。

接下来 $n$ 行，每行有两个整数 $a_i,opt_i$，描述一个选项。其中当 $opt_i=1$ 时，表示这个选项的内容为 **第 $a_i$ 个选项是正确的**；当 $opt_i=0$ 时，表示这个选项的内容为 **第 $a_i$ 个选项是错误的**。

outputFormat:
如果没有答案满足这道选择题，输出`No answer`。

否则输出三行，每行一个正整数，分别为合法答案数及正确选项最多和最少的答案分别有多少个正确选项。其中合法答案数要对 $998244353$ 取模。

hint:
对于样例一，一共有下面 $2$ 种正确答案：

+ 第 $1,2,3$ 个选项是正确的。
+ 第 $4$ 个选项是正确的。

其中正确选项最多的答案有 $3$ 个选项正确，正确选项最少的答案有 $1$ 个选项正确。

### 数据范围
对于 $10\%$ 的数据，$n\leq 10$。
对于 $30\%$ 的数据，$n\leq 100$。
对于 $60\%$ 的数据，$n\leq 10^3$。
对于 $100\%$ 的数据，$n\leq 10^6,1\leq a_i\leq n,i\neq a_i,opt_i\in\{0,1\}$。


title: [Ynoi2015] 我回来了

background:
我遵守了...
约...约定
![](https://cdn.luogu.com.cn/upload/pic/45543.png)
【你非常努力啊】
我非常非常努力哦...
![](https://cdn.luogu.com.cn/upload/pic/45545.png)
【虽然昨天也说过这句话了...】
【欢迎回来，珂朵莉】
![](https://cdn.luogu.com.cn/upload/pic/45546.png)
我回来了...
终于说出口了...
【是啊，我终于听见了】
红色的头发，会不会奇怪？
【很漂亮的颜色，和你很搭哦】
是吗...
我...我已经没事了
【真的吗？身体状况没问题吗？】
【要是硬撑的话，我可不会饶过你啊】
没事的，做饭啊洗衣服啊，还留着很多活要干呢
【可别太拼了哦】
![](https://cdn.luogu.com.cn/upload/pic/45547.png)
哼，你就做好心理准备等着吧
![](https://cdn.luogu.com.cn/upload/pic/45548.png)

description:
珂朵莉在玩炉石传说的时候总是打不出教科书般的亵渎，于是他重新写了一个炉石传说’，并且将亵渎的描述改为：“等概率随机在 $[L,R]$ 中选出一个整数作为伤害值 $d$，对所有随从造成 $d$ 点伤害，如果有随从死亡，则再次施放该法术，但伤害值不重新随机；如果没有随从死亡，则停止释放”，还去掉了场面上随从上限和亵渎最多触发14次的限制。

珂朵莉不知道这个改版亵渎的效果怎么样，于是他打算进行一些测试，其中共进行 $m$ 次如下类型的操作：

1. 在场面上加入一个血量为 $h$ 的随从，这里随从的血量都不能超过 $n$；
2. 给定 $L, R$，询问亵渎期望触发多少次；

珂朵莉只会做操作1，于是他就把操作2交给你啦。

inputFormat:
第一行两个由空格分隔的整数 $n\;m$；

接下来 $m$ 行，每行表示一次操作，操作1表示为 $1\;h$，操作2表示为 $2\;L\;R$；

outputFormat: 为避免输出小数，对每次操作2，输出一个整数表示期望值与 $(R-L+1)$ 的乘积。

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

对于 $100\%$ 的数据，保证：
$1\le n\le 10^5$，每次1操作有 $1\le h\le n$，每次2操作有 $1\le L\le R\le n$；
$1\le m\le 10^6$；
以上所有数值均为整数。


title: 「JYLOI Round 1」性状

description:
小郭给你 $(n + 1)$ 个非负整数 $a_0 \sim a_n$，对于任意 $0 \leq i \leq n$ 有 $a_i \in \{0, 1, 2\}$，其中 $a_i$ 表示第 $i$ 个人的基因中控制双眼皮的显性基因个数，在下文中也代表着这个生物。

现在对于原序列中的任意一个子序列 $b_{c_1} \sim b_{c_m}$（其中 $1 \leq c_i < c_{i + 1} \leq m$，并且 $1 \leq i < m \leq n$），将 $a_0$ 和 $b_{c_1}$ 进行交配，得到子一代，并将子一代和 $b_{c_2}$ 交配，得到子二代，以此类推，最后将子 $(m - 1)$  代与 $b_{c_m}$ 进行交配，得到子 $m$ 代，我们定义这个子序列的价值为子 $m$ 代为双眼皮的概率。

由于他很忙，于是他现在请你帮他求出所有子序列的价值的平均值在模 $998244353$ 意义下的值。

**提示**：把 0、1、2 分别看作 ``aa``、``Aa``、``AA`` 三种字符串，两个生物进行交配，就是选择每个字符串间长度为 1 的子序列进行大写字母在前，小写在后的合并，其中这样的一个字符串为子代一种可能的基因组成。

其中大写字母开头的为显性性状，小写字母开头为隐性性状。双眼皮为显性性状，单眼皮为隐性性状，结果 ``aa``、``Aa``、``AA`` 分别再对应回数字 0、1、2。

**注意**，在本题中，我们认为眼皮的单双由位于常染色体上的一对等位基因 ``A`` 和 ``a`` 控制，其中 ``A`` 相对 ``a`` 为完全显性。且该性状的遗传遵循孟德尔的分离定律，并不考虑表观遗传、从性遗传、突变、基因表达的相互影响，所有基因型的配子和个体均无致死概率，所有个体均能产生可育配子。

inputFormat:
输入的第 1 行有一个正整数 $n$，中间用一个空格隔开，$n$ 的含义如题所述。

第二行有 $(n + 1)$ 个非负整数，这一行中的第 $i$ 个数表示 $a_i$。

outputFormat: 输出只有一行一个非负整数，表示答案。

hint:
## 样例 1 解释

子序列 $\{1\}$、$\{0\}$、$\{1, 0\}$ 的价值分别为 $1$、$1$ 和 $\dfrac{3}{4}$，平均价值为 $\dfrac{11}{12}$，对 $998244353$ 取模后的结果为 $415935148$。

## 数据范围

对于 $100\%$ 的测试数据，$1 \leq n \leq 5 \times 10^6, a_i \in \{0, 1, 2\}$。

对于测试点 1，$n = 1$。

对于测试点 2，$n = 2$。

对于测试点 3~5，$n \leq 5$。

对于测试点 6~10，$n \leq 7.5 \times 10^3$。

本题共有 20 个测试点，每个测试点 5 分，共 100 分。

## 题目来源

「JYLOI Round 1」 B

Idea：abcdeffa & LiuXiangle

Solution：LiuXiangle

Data：LiuXiangle


title: 【模板】二分图最大权完美匹配

background:
> $\rm Love ~of ~my ~life$
>
> $\rm U~are~far~from~me$
>
> $\rm U've ~ turned ~ me ~ on$
>
> $\rm and ~ now ~ I ~ try ~ to ~ catch ~ up ~ with ~ you$
>
> $\rm Love ~ of ~ my ~ life ~ can't ~ you ~ see$
>
> $\rm I'll ~ always ~ try, ~ always ~ try$
>
> $\rm U ~ are ~ the ~ brightest ~ star ~ to ~ me$
>
> $\rm No ~ matter ~ others ~ don't ~ know$
>
> $\rm what ~ it ~ means ~ to ~ me$
>
> ——  An adaptation of _Love of My Life_ by Queen

这是一道夹带私货的模板题。

description:
给定一张二分图，左右部均有 $n$ 个点，共有 $m$ 条带权边，且保证有完美匹配。

求一种完美匹配的方案，使得最终匹配边的边权之和最大。

inputFormat:
第一行两个整数 $n,m$，含义见题目描述。

第 $2\sim m+1$ 行，每行三个整数 $y,c,h$ 描述了图中的一条从左部的 $y$ 号结点到右部的 $c$ 号节点，边权为 $h$ 的边。

outputFormat:
**本题存在 Special Judge**。

第一行一个整数 $ans$ 表示答案。

第二行共 $n$ 个整数 $a_1,a_2,a_3\cdots a_n$，其中 $a_i$ 表示完美匹配下与**右部**第 $i$ 个点相匹配的左部点的编号。如果存在多种方案，请输出任意一种。

hint:
#### 数据规模与约定
- 对于 $10\%$ 的数据，满足 $n\leq 10$。
- 对于 $30\%$ 的数据，满足 $n\leq 100$。
- 对于 $60\%$ 的数据，满足 $n\leq 500$，且保证数据随机 。
- 对于 $100\%$ 的数据，满足 $1\leq n\leq 500$，$1\leq m\leq n^2$，$-19980731\leq h \leq 19980731$ 。且保证没有重边。

数据由善于出锅的出题人耗时好久制造完成。

善良的杨村花提醒你，别忘了仔细观察一下边权范围哦~

善良的杨村花又提醒你，你的复杂度可能只是「看起来」很对哦~


title: [YsOI2020] 归零

background:
Ysuperman 特别喜欢玩数数游戏。

~~其实本来这题想叫“亦旧亦久罢以龄”的，但是我见到其他的题目名称都是两个字，取这么长名称也不好。~~

description:
闲暇时光，Ysuerpman 选择用计算器打发时间。他输入了一个很长的十进制数 $S$。具体有多长呢？共 $n$ 位。为了方便解释，设从低到高第 $i$ 位上的数字是 $S_i$（下标从 $1$ 开始）。

Ysuerpman 每次会选择一个**非零**数字位进行「四舍五入」。具体来说，假设「四舍五入」的是第 $i$ 位：

- 如果 $S_i<5$，则让 $S$ 减去 $S_i \cdot 10^{i-1}$。
- 如果它 $S_i\ge5$，则让 $S$ 加上 $10^i$ 再减去 $S_i \cdot 10^{i-1}$。

经过若干次操作后，$S$ 总会变成 $0$。现在问题来了，请问有多少种使得 $S$ 变成 $0$ 的不同的方案？两个方案不同当且仅当某一次选择的操作位置不同。

inputFormat: 一个高精度数 $S$。

outputFormat: 使得 $S$ 变成 $0$ 的不同的方案数量，对 $998244353$ 取模。


title: [Ynoi2019] 魔法少女网站

background:
我每天都在想着死去

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

干脆死了算了吧

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

魔法少女网站？这是什么？

“真是不幸啊 真是不幸”

“给予这样的你——”

“魔法的力量吧”

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

雨谷小雨

唉，自我介绍真麻烦

你因为使用魔杖过度而倒下了，之后就一直没有意识

所以我治好了你

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

在未来的8月11日19时23分

在那一天，tempest将袭来——

Tempest将为这腐朽的世界带来终焉，打开通往新世界的大门
但在这过程中，大多数的人类估计都会死亡

Tempest的到来是不可避免的，但仅有一种方法可以获得救赎——

那就是填饱王的肚子

王以人类的负能量为食，只要献上这种能量，就能规避tempest带来的死亡

通过使用魔法少女网站给予的魔杖，就能够将负能量储存至魔杖中

只有尽可能多地使用魔杖，比其他魔法少女献上更多的负能量，这样才能成为tempest的赦免对象

如果想活下去，就将充斥着负能量的魔杖，在tempest那天交给我们魔法少女网站吧

最后祝你们迎来美好的终焉

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

去掉人类一切的负面情绪

Tempest必将席卷世界

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

description:
雨谷小雨给你一个长为 $n$ 的序列，定义区间 $[l,r]$ 的子区间为所有形如 $[l',r']$ 的区间，满足 $l',r'$ 为整数，且 $l \le l' \le r' \le r$。

有 $m$ 次操作：

`1 x y`：将 $x$ 位置的值修改为 $y$。

`2 l r x`：查询区间 $[l,r]$ 中有多少子区间的最大值小于或等于 $x$。

inputFormat:
第一行有两个整数 $n,m$，第二行有 $n$ 个整数表示这个序列。

接下来 $m$ 行，每行形如 `1 x y` 或者 `2 l r x` 表示每次操作。

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

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

对于 $100\%$ 的数据，$n,m \le 3 \times 10^5$，$1 \le l \le  r \le n$，$1 \le x, y \le n$，序列中每个元素都在 $[1,n]$ 中，所有数均为整数。


title: [POI2012] LIC-Bidding

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

**本题 checker 中含有正解, 故不下发**。

description:
A 和 B 两个人在玩一个游戏，这个游戏是他们轮流操作一对整数 $(x,y)$。

初始时 $(x,y)=(1,0)$，可以进行三种操作：

1. 将 $(x,y)$ 变成 $(1,x+y)$。
2. 将 $(x,y)$ 变成 $(2x,y)$。
3. 将 $(x,y)$ 变成 $(3x,y)$。

给定正整数 $n$。在 $x+y\ge n$ 时就不能进行后两种操作。如果某个人操作后 $y\ge n$，他就输掉了。

保证给出的 $n$ 为先手必胜的，你需要提供一种先手必胜的方案。例如 $n = 3$ 时，先手选择操作 3，后手只能选择操作 1 然后输，所以 $n = 3$ 时先手必胜。

**交互题**，你需要实现一个函数 ``extern "C" int _opt(int n, int x, int y)``，该函数的返回值是一个值为 $1$，$2$ 或 $3$ 的整数，表示现在数对是 $(x, y)$，参数是 $n$ 且轮到你操作时，你会选择的操作。

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

对于全部的测试点，保证 $1 \leq n\leq 30000$。

### 说明

样例交互库见附件。与选手程序在本地一起编译后可以通过标准输入来模拟 spj 与选手程序进行交互。
当交互库输出 `-2 -2` 并退出时，说明选手程序正确。


title: [Ynoi2019] Happy Sugar Life

background:
我不曾明白——

所谓温暖是什么样的感觉？

所谓温柔的是什么？

所谓的怜爱是什么？

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

更重要的是……

我不能理解什么是“爱”

但是，现在我明白了——

我终于明白了爱的真正含义

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

——这份闪闪发光的感情，就是爱吧

我发誓——

无论疾病还是健康

无论高兴还是悲伤

无论富有还是贫穷

直到死亡为止

我将砂糖视为最爱，至死分离

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

我从前没有爱过人

被人咬耳朵告白这种事——

倒是发生过许多次

但是，无论是甜言蜜语

还是做了什么事情

我都无法感受到

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

砂糖酱，痛吗

——我没事，不过……不能前往新的城堡了

——对不起

没事

果然我还是和砂糖酱在一起的时候最幸福了

——小盐……

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

呐，砂糖酱，我思考过——

那个时候，被妈妈抛弃的时候

我大概是死掉的状态

又悲伤，又痛苦

觉得一切都无所谓，世界一片空白——

但是砂糖酱出现了

遇到砂糖，一起生活，过得很幸福

——我也是哦，小盐

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

所以，我想要和砂糖酱在一起

想要和砂糖一起幸福到最后

所以，我们一起死吧，砂糖！

——小盐……

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

我原本都不知道

温暖是何种感受

温柔是何物

慈爱又是什么

最重要的是

我曾无法理解“爱”是什么

这多亏了小盐

因为那时小盐抓住了我的手

因为小盐为我指引道路

我才明白有生以来从未感受过的幸福的意义

我一直都不明白

原来教会我什么是爱的

也是小盐

小盐，转世之后也要对我告白哦

对不起

谢谢你

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

这就是我的

$\texttt {Happy Sugar Life}$

description:
砂糖和盐给你一个二维平面，记平面上两个点 $(x_1,y_1),(x_2,y_2)$ 构成支配对（记为$(x_1,y_1)\le (x_2,y_2)$）当且仅当 $x_1\le x_2,\;y_1\le y_2$。
平面上初始给定 $n$ 个不同的点 $\{(x_i,y_i)\}_{i=1}^n$。

你需要回答 $m$ 次询问，每次询问给出两个点 $(x,y),(x',y')$，问有多少二元组 $(i,j)$ 满足 $(x,y)\le (x_i,y_i)\le (x_j,y_j)\le (x',y')$ 且 $i \neq j$。

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

第二行 $n$ 个数，其中第 $i$ 个数 $p_i$ 表示平面上初始给定的第 $i$ 个点 $(i,p_i)$，保证 $p_i$ 为一个 $1$ 到 $n$ 的排列。

之后 $m$ 行，每行用四个空格隔开的数，分别表示 $x,x',y,y'$，表示一次询问，保证 $(x,y)\le (x',y')$。

outputFormat: 输出 $m$ 行，第 $i$ 行输出一行一个整数，表示第 $i$ 次询问的答案。


title: [CCC2019] Tourism

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

Shuchong 和您正在畅玩洛谷著名景点。
但是他因为太菜爽约了。
您只好独自去游览洛谷著名景点。

description:
您正在游览 $n$ 个景点，编号为 $1$ 到 $n$，并且因为 3k 的强硬要求，您必须按照 $1$ 到 $n$ 的顺序浏览。您一天最多可以游览 $k$ 个景点，因为剩下的时间您要用来爆切黑题，所以您想尽快浏览完这些景点。
每个景点对您的吸引度不同，第 $i$ 个景点对您的吸引度为 $a_i$，一天游览的这些景点的官方评分就是这天游览的景点的 $a_i$ 的最大值。最后，您需要把每天的官方评分加起来获得最后的评分。
因为您太着急想爆切黑题了，所以您提前计算好了浏览完所有景点最少需要多少天（假设它为 $t$），您想知道：

- 用 $t$ 天浏览
- 满足每天最多游览 $k$ 个景点
- 能得到的最后的评分最大是多少

inputFormat:
第一行两个整数 $n,k$ 代表景点数和最多游览景点数。
第二行 $n$ 个整数 $a_i$ 代表每个景点的吸引度。

outputFormat:
一行一个整数代表

- 用 $t$ 天浏览
- 满足每天最多游览 $k$ 个景点
- 能得到的最后的评分最大是多少

（$t$ 为浏览完所有景点最少需要多少天）

hint:
#### 样例说明

对于样例 $1$：

- 我们很容易就知道至少需要 $2$ 天就可以浏览完所有景点。
- 但是我们不能一天内浏览完所有景点。（$n>k$）
- 我们把景点尽量平分，有以下两种情况：
	- 如果第一天浏览 $2$ 个，第二天浏览 $3$ 个，最终的评分为 $5+7=12$。
    - 如果第二天浏览 $3$ 个，第二天浏览 $2$ 个，最终的评分为  $7+4=11$。
- 最后的答案为 $\max(12,11)=12$。

#### 数据规定与说明

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

- Subtask 1（20 pts）：$2k \ge n$。
- Subtask 2（20 pts）：$k \le 100$，$n \le 10^5$。
- Subtask 3（60 pts）：无特殊限制。

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

#### 说明

**翻译自 [CCC 2019](https://cemc.math.uwaterloo.ca/contests/computing/2019/index.html) Senior T4 [Tourism](https://cemc.math.uwaterloo.ca/contests/computing/2019/stage%201/seniorEF.pdf)。**
翻译者：@[一只书虫仔](https://www.luogu.com.cn/user/114914)。


title: [CCC2019] Triangle: The Data Structure

background:
在 Shuchong 的平行宇宙里，计算机学中的最重要的数据结构就是三角形。
注：因为原数据包太大，故这题缩减了一些数据，具体缩减的数据点如下：

- Subtask 1：1 ~ 10
- Subtask 2：1 ~ 10

所以此题拥有的测试点为：

- Subtask 1：11 ~ 26
- Subtask 2：11 ~ 24

若想测试本题没有的测试点请到 [此处](https://www.luogu.com.cn/problem/U120704) 测试。

description:
大小为 $m$ 的一个三角形由 $m$ 行组成，第 $i$ 行包含 $i$ 个元素。
并且，这些行必须排为等边三角形的形状。
比如说，以下是一个 $m=4$ 的三角形。
![](https://cdn.luogu.com.cn/upload/image_hosting/fdut4hrs.png)
每个三角形还包含子三角形。
比如说上面这个三角形，包含：
- $10$ 个大小为 $1$ 的三角形。
- $6$ 个大小为 $2$ 的三角形。
- $3$ 个大小为 $3$ 的三角形。

注意，每个三角形都是自身的子三角形。
现在给定一个大小为 $n$ 的三角形，求对于每个大小为 $k$ 的子三角形，子三角形内几个数的最大值的和。

inputFormat:
第一行两个整数 $n,k$ 代表三角形的大小和要求的子三角形的大小。
接下来 $n$ 行第 $i$ 行有 $i$ 个整数代表这个三角形。

outputFormat: 一行一个整数代表对于每个大小为 $k$ 的子三角形，子三角形内几个数的最大值的和。

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

- Subtask 1（25 pts）：$n \le 1000$。
- Subtask 2（75 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le k \le n \le 3000$，$0 \le $ 三角形内每个数 $\le 10^9$。

#### 说明

**翻译自 [CCC 2019](https://cemc.math.uwaterloo.ca/contests/computing/2019/index.html) Senior T5 [Triangle: The Data Structure](https://cemc.math.uwaterloo.ca/contests/computing/2019/stage%201/seniorEF.pdf)。**
翻译者：@[一只书虫仔](https://www.luogu.com.cn/user/114914)。


title: 「SWTR-5」Grid

background: **赛时提醒：格子可以重复经过，但分数只算一次。**

description:
小 A 有一个 $n\times m$ 的网格，每个格子上都写着一个数字。为方便描述，令左上角的网格为 $(1,1)$，右下角的网格为 $(n,m)$。

小 A 可以进入最下方第 $n$ 行的任意一个网格，并按照以下规则进行游戏：

- 设小 A **第一次进入第 $i$ 行**的位置为 $(i,r_i)$：
如果小 A 在 $(i,r_i)$，则他只能向左或向上跳。否则他可以向左，向右或向上跳。
- 小 A 不能跳出网格，除非他在第 $1$ 行，这代表结束整场游戏。

定义一局游戏的得分为所有小 A 经过的格子上的数字之和。小 A 想请你帮他求出得分的最小值。

inputFormat:
第一行两个整数 $n,m$，分别表示网格的行数和列数。

第二至 $n+1$ 行每行 $m$ 个整数 $a_{i,j}$，表示 $(i,j)$ 上的数。

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

hint:
「样例说明」

样例 $1$ 的解释如图所示：

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

「数据范围与约定」

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

- Subtask 1（3 points）：$a_{i,j}\leq 0$。
- Subtask 2（12 points）：$n,m\leq 5$。
- Subtask 3（15 points）：$n=2$。
- Subtask 4（18 points）：$n,m\leq 90$。
- Subtask 5（22 points）：$n,m\leq 400$。
- Subtask 6（30 points）：无特殊限制。

对于 $100\%$ 的数据：$1\leq n,m\leq 10^3$，$-10^6 \leq a_{i,j}\leq 10^6$。

---

「题目来源」

[Sweet Round 05](https://www.luogu.com.cn/contest/28195) A。
idea & solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。


title: 『JROI-4』傀影与猩红孤钻

background:
“水……”

在沙尘暴中跋涉许久，又整整一天没有饮水，身体已经逐渐支撑不住了。

凯尔希没有拿水瓶，而是冷冷地说了一句“再撑一会”，随后就自顾自继续向前赶路。

我们已经在沙暴里跋涉了多久？三个小时？还是五个小时？黄沙不停往衣物里涌，狂风则不停将沙尘甩在脸上，刮得眼睛都睁不开。但我们还不能停步，后面的萨卡兹雇佣兵还在紧追不舍，他们尽职尽责，即使是沙暴都阻挡不了他们的脚步。

至于水……或许早就喝完了吧。

听说沙漠里有在空水壶中灌沙来给人以希望的传统，可现在，沙子我已经喝够了，水，我只想喝口水，哪怕用身上所有的硬币去换，我也愿意。

只是在这荒野里，闪亮的金属毫无意义。

紧紧抱着银色的手提箱，我咬紧牙关继续迈步。

耳边都是凄厉的呼啸，像是亡者的哭号，又像是鬼魂的呼唤。索恩教授或许也在其中，呼唤着我的名字？

但我听不太清了。

脑中满是这样的响声，已经多久了？三分钟？三小时？还是三年？

沙尘遮蔽了天空，白天和黑夜已经毫无区别，时间似乎都已凝滞，只有在其中求生的人们，还在忍受着此间种种刑罚。

我只是想做研究，我只是想为科学进步奉献自己的力量，而不是像现在这样，倒在沙海里风干。

脑袋又酸又胀又痛，身体好像早就没了知觉，我是在行走吗，还是在看着这具名为艾利奥特的躯壳蠕动？

不……思考也成为了一种奢求，现在徘徊在脑袋里的，只有一个指令：移动。

移动……移动……移动……

……但沙海是无垠的。

“艾利奥特，张嘴。”

张嘴？

我下意识地放松肌肉，让嘴唇和牙齿露出一条通往口腔的通道。

一串沾满沙土的果实落到了口中。

有些酸涩？有些甘甜？哦，是水，是水。

是水啊。

……

不知从什么时候开始，耳边再也没有风声，大地回复了寂静，只有阳光，沙漠，和两个在沙丘间徒步的凡人。

……

我望向远方，除了黄沙，还是黄沙。

一眼望不到尽头，就像散落满地又被浸湿的皮鞋踩上几脚的技术文件，再也归不拢，再也理不齐。

我忿忿地踢了一脚沙子，看着它们从沙丘尖端翻滚滑落，然后重新融到沙漠中，好似什么都没有发生过。

沙子，沙子。

我生平第一次开始痛恨沙子。

“走吧，很快就能获得补给了。”

凯尔希打断了我的思绪。

可，很快？能有多快？

一些补给？又有多少呢？

呵，凯尔希从来不向人许诺希望。

但至少……

我似乎看见了一颗仙人掌。

description:
## 我们在题目描述的最下方提供了形式化题意，若您不想阅读整活部分可以直接跳到题目描述的最下方。

神在猩红剧团的探索中取回了自己一部分的力量，不多，但够用。

神见到了傀影。准备使用辉煌裂片对他进行审判。

但是傀影躲进了一个被分成 $d$ 层的 DAG 中。

具体地，DAG 上第 $i$ 层的节点只会连向第 $i+1$ 层的节点。

“那就陪你继续玩玩吧。”神心想。

神决定了一种审判的方式。

具体地，神最开始有一些辉煌裂片。神认为，多项式具有强大的力量，所以辉煌裂片就是多项式。~~我才不告诉你是我懒得编题面。~~

神有三种对辉煌裂片的操作：

1. “无度”

可以让辉煌裂片更加强大。具体地，对 $F(x)$ 进行这个操作就相当于令 $F(x)=F^2(x)$。

2. “文明的存续”

可以让“无度”后的辉煌裂片更加强大。具体地，对 $F(x)$ 进行这个操作就相当于令 $F(x)=F(x^2)$。

3. “夜骇”

可以让两个辉煌裂片进行融合，变得更加强大。具体地，如果对 $F(x)$ 和 $G(x)$ 进行这个操作会返回一个多项式为 $F(x)+G(x)$。

神决定这样对傀影进行审判：

在第一层的节点放置辉煌裂片。

当辉煌裂片进入一个节点前，对自身进行“无度”。

当两个辉煌裂片相遇，对这两个辉煌裂片进行“夜骇”，只会留下一个辉煌裂片为这两个辉煌裂片进行“夜骇”的结果。

辉煌裂片只会在连接该节点的所有边都有辉煌裂片通过后，才会离开该节点。当辉煌裂片离开一个节点时，辉煌裂片会对进行“文明的存续”，然后分裂成若干个和原辉煌裂片相同的辉煌裂片，留下一个辉煌裂片在该节点。然后，每条边都将通过恰好一个辉煌裂片。

若傀影在节点 $u$，而神有一个审判指数（execution points，EXP）$k$，该节点留下的辉煌裂片为 $F_u(x)$，那么傀影将会受到 $F_u(k)$ 伏特的电流。

现在神有一些提问。每个提问类似于，若傀影藏在节点 $u$，且审判指数为 $k$，那么傀影将会受到多少伏特的电流？

神是怜悯的。答案可能过大，他只要求你输出答案对 $7340033(2^{20}\times7+1)$（一个质数）取模后的结果。
### 形式化题意
给你一张分为 $d$ 层的 DAG，每个节点都有一个多项式 $F_u(x)$。**可能会有重边。**

这个 DAG 上第 $i$ 层的节点只会向第 $i+1$ 层的节点连边。

若 $S_u$ 包含所有连向点 $u$ 的节点，那么满足 $F_u(x)=\sum_{v \in S_u}F_v^2(x^2)$。

给出第一层节点的多项式，每次询问会给你 $u,k$，然后询问 $F_u(k)$ 对 $7340033(2^{20}\times7+1)$（一个质数）取模后的结果。

**请注意，重边算作一条边。**

inputFormat:
第一行一个整数 $d$，表示 DAG 的层数。

接下来一行会有 $d$ 个整数，第 $i$ 个数 $n_i$ 表示第 $i$ 层有 $n_i$ 个节点。

接下来 $n_1$ 行，第 $i$ 行有若干个数表示第一层的 $i$ 号节点的多项式。

具体地，每行第一个数 $p$ 表示多项式的最高次，接下来 $p+1$ 个数表示这个多项式的系数，若其中第 $i$ 个数（不包括 $p$）为 $f_{i-1}$，那么该多项式为 $\sum_{i=0}^pf_ix^i$。

接下来的输入分为 $d$ 段。第 $i$ 段的开头有两个数 $m,q$ 表示第 $i$ 层有 $m$ 条边，以及神在第 $i$ 层的点中有 $q$ 个询问。

接下来 $m$ 行，每行两个数 $u,v$ 表示第 $i$ 层编号为 $u$ 的点连接了第 $i+1$ 层编号为 $v$ 的点。

接下来 $q$ 行每行两个整数 $u,k$ 表示神询问当傀影在第 $i$ 层编号为 $u$ 的节点上时，且审判指数为 $k$ 时，傀影受到电流的伏特对 $7340033$ 取模后的结果。

outputFormat:
由于输出可能过大，你需要对输出加密。

具体地，对于第 $k$ 层的询问，若第 $i$ 个询问的答案为 $a_i$，你只需要输出 $(k \times \bigoplus_{i=1}^q(q-i) \times a_i)\bmod 2^{32}$ 即可。

请注意，输出一共 $d$ 行，每行一个数字。

hint:
- Subtask1（7pts）$1\leq d\leq 2$。
- Subtask2（20pts）$1\leq d\leq 10,\sum q=1$。
- Subtask3（13pts）$n_1=2$，且时间限制为 5s。
- Subtask4（60pts）无特殊限制。
- Subtack5（0pts）Hack 数据。

对于 $ 100\% $ 的数据，满足 $1\leq\sum n<5060$，$1\leq d\leq 10$，$\sum q\leq 1.5 \times 10^6$，$1\leq w,k<7340033$，$0 \leq p \leq 2$。

若第 $i$ 层有 $m_i$ 条边，对于 $i\neq d$ 保证有 $n_i<n_{i+1}\leq2\times n_i$ 和 $n_i\leq m_i\leq 3\times n_i$，且 $m_d=0,1 \leq n_1 \leq 5$。


title: 烷烃计数

description:
$n$ 个碳原子的烷烃共有多少种同分异构体（不考虑立体异构）？

提示：如果你不知道什么是烷烃，那么你可以认为这个问题等价于求 $n$ 个点的无标号无根树并满足每个点的度数 $\le 4$ 的树的个数。

inputFormat: 一个整数 $n$ 表示碳原子的个数。

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

hint:
#### 样例 1 解释

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

#### 数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 10^5$。


title: 谷歌翻(sheng)译(cao)机（加强版）

background:
本题由@[wolfind](https://www.luogu.com.cn/user/104593)提供。

[原题链接](https://www.luogu.com.cn/problem/P6693)（注意原题与加强版**有且仅有**`理解方式`中的**式子不同**、**模数不同**、**数据范围不同**）。

description:
**注：为了方便描述，下文所有字符串起始位置都为 $1$，即都从 $1$ 开始标号。**

小 L 将每次生草前的原文和生草后的结果看作两个**仅由小写字母组成**的两个字符串 $A$ 和 $B$。

我们按如下方式定义「分割数列」和「分割串」：

- 对于一个长度为 $n$ 的字符串，定义它的一条「分割数列」为：存在长度为 $k+2$ 的数列 $p$，使得 $0=p_0<p_1<p_2<...<p_k<p_{k+1}=n+1$。对于一条「分割数列」，定义其「分割串」为 $p_i+1$ 到 $p_{i+1}-1$ 之间字符构成的子串（$i \in[0,k]$）（可以为空串）。显然，对于一条长度为 $k+2$ 的分割数列，一共有 $k+1$ 个分割串。

- 对于同一个字符串，两条分割数列（$p$ 和 $q$）不同**当且仅当两条数列长度不同（$k_1\neq k_2$）**，或**存在 $i$ 使得 $p_i\neq q_i$**。

不同人对于同样的原文和结果，他们的理解方式都是不同的。我们按如下方式定义一种理解方式：

- 对于字符串 $A$ 和 $B$，我们为这两个字符串各找一条分割数列（$p$ 和 $q$），这两个分割数列满足以下要求：
1. 两个分割数列长度相等（$k_1=k_2$）。
1. 对于任意 $i$，有 $A[p_i]=B[q_i]$，即 **$A$ 第 $p_i$ 个位置的字符与 $B$ 第 $q_i$ 个位置的字符相同**。

- 定义这种理解方式的「生草程度」为**此时两个字符串的所有分割串长度的 $t$ 次方和**，即 $\sum\limits_{i=0}^{k_1}(p_{i+1}-p_i-1)^t+\sum\limits_{i=0}^{k_2}(q_{i+1}-q_i-1)^t$。

- 两种理解方式不同**当且仅当**两种理解方式的 $p$ 不同，或两种理解方式的 $q$ 不同。

小 L 想要知道所有理解方式的生草程度之和的结果。由于他（也）不喜欢 $998244353$ 这个数，他不希望你告诉他的结果会是这个数，所以你要将结果对 $998244353$ 取模。

inputFormat:
第一行有三个正整数 $n,m,t$。

接下来一行有一个长度为 $n$ 的字符串，表示字符串 $A$。

接下来一行有一个长度为 $m$ 的字符串，表示字符串 $B$。

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


title: 强迫症

background:
小 L 是一个严重的强迫症患者。

由于他严重的强迫症，所以他画图时总是要把点画在一个圆上。

description:
一天，他问了小 H 和小 W 这样一个问题：

如果在一个圆上有 $n$ 个不同的点，依次标号为 $1$ 到 $n$，有多少种方案能把它们连成一棵树？

小 H & 小 W：这不是sb题吗？

小 L：那如果**连边不能相交**呢？

小 H & 小 W：这不是sb题吗？

小 L：那如果把「树」换成「图」呢呢？

小 H & 小 W：这不是sb题吗？

小 L：那如果给每个点一个权值 $a_i$，连接 $(i,j)$ 的边权值为 $a_i\times a_j$，求**满足上面**的图的**期望所有边权值之和**呢？

小 H & 小 W：这不是sb题吗？

小 L 见自己辛苦做了许久都没写出的题目被 dalao 轻松秒杀后十分郁闷。为了安慰他，你需要帮他做出这个问题。

**注意**：
1. 两条边在端点处**不视作相交**。
1. **没有边的图（即只有 $n$ 个点，之间没有边相连）也合法**
1. 点**按顺时针从 $1$ 到 $n$** 编号。
1. 图中**不能有自环和重边**

inputFormat:
第一行一个正整数 $n$，意义如上。

接下来一行 $n$ 个非负整数，第 $i$ 个数为 $a_i$，表示第 $i$ 个点的点权。

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

hint:
对于样例一，全部 $64$ 张图如下：
![](https://cdn.luogu.com.cn/upload/image_hosting/zfa8hs0v.png)

其中左侧 $48$ 张图合法，右侧 $16$ 张图不合法，所有边的权值均为 $1$。

期望边权和为 $\dfrac{8}{3}$，模 $998244353$ 意义下结果为 $665496238$。

### 数据范围

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

- Subtask 1( $10\%$ )：$n\leq 6$。
- Subtask 2( $30\%$ )：$n\leq 3000$。
- Subtask 3( $60\%$ )：无特殊限制。

对于 $100\%$ 的数据，$2\leq n\leq 10^5,0\leq a_i\leq10^6$。

Subtask 1 和 Subtask 2 时限 $1s$，Subtask 3 时限 $2s$。

------------
如果你不知道如何对一个有理数取模，请自行百度「乘法逆元」


title: 炼金术（Alchemy）

description:
铃是一个爱玩游戏的女孩子。

她在游戏中想要炼制一种稀有合金 —— 这需要 $n$ 种金属来合成。

她准备好矿石后建造了 $k$ 个不同的熔炉，当熔炉启动时，会随机炼出这 $n$ 种金属中的一些（也可能什么都没有）。

如果把每个熔炉炼出的金属收集起来，有了全部 $n$ 种金属，就能造出合金了。澪对此很好奇，对铃说：「我考考你，有多少种情况可以炼出合金呢？」这个简单的问题铃很快就会做了，你能求出结果吗？

答案可能很大，请对 $998244353$ 取模（即除以 $998244353$ 的余数）后输出。

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

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


title: 出生点

background:
小 L、小 W 和小 H 在一起van♂游戏。

~~由于小 L 太菜了所以导致他一直在看着小 W 和小 H 打游戏。~~

description:
这款游戏的地图可以抽象成一张有 $n$ 行 $m$ 列的网格图，网格图上有 $k$ 个障碍点，相邻两点间边长为 $1$。游戏开始时~~小 L~~、小 W 和小 H 会**各自**随机出生在一个点。当然，他们**不会出生在障碍点**。

~~经常开局死的~~小 L 看着小 W 和小 H 每次在地图上汇合时经过的路径，很想知道他们每次出生后两个人之间的期望距离。（这里的距离指两点间[曼哈顿距离](https://www.luogu.com.cn/blog/xuxing/Distance-Algorithm)，即 $\left|x_1-x_2\right|+\left|y_1-y_2\right|$）

由于小 L 可以非常容易算出有多少种出生点安排方案，所以你实际上**只需要告诉他所有情况中他们两人距离之和**。

**注意**：小 W 出生在点 $A$，小 H 出生在点 $B$，跟小 W 出生在点 $B$，小 H 出生在点 $A$，这两种情况**视作同一种情况**。

inputFormat:
第一行有三个整数 $n,m,k$，分别表示地图行数、列数以及障碍物点数。

接下来有 $k$ 行，第 $i$ 行有两个正整数 $x_i,y_i$，表示第 $i$ 个障碍物的位置。

outputFormat:
一个整数，表示**所有情况中小 W 和小 H 两人出生点距离之和**。

由于小 L 十分无聊，所以他让你将答案对 $10^9+7$ 取模。


title: [Code+#7] 最小路径串

description:
$n$ 个点 $m$ 条边的无向图中，所有点用从 `0` 开始的 `6` 位数字串编号，即 `000000`、`000001`、`000002`、……直到 $n-1$ 对应的 $6$ 位数字串。保证 $n\le 10^6$，所以 $6$ 位的编号不会溢出。

对于除了 `000000` 以外的每个点，你需要找到一条从 `000000` 出发且不经过重复点的路径，使得路径上所有点的数字串顺次连接形成的串的字典序最小。比较两个不同的串的字典序的方法是：如果其中某个串是另一个的前缀，则较短的串字典序较小；否则，找出两个串从左往右扫描时遇到的首个不相等的位置，在这个位置上的数字较小的串字典序较小。

由于输出路径过于麻烦，你不需要完整地输出路径，只需要将路径上所有点的数字串视作一个整数，输出这个数对 $998244353$ 取模的结果。

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

第二行输入一个长度为 $12m$ 的数字串，依次表示每条边。每条边用 $12$ 个数字表示，其中前 $6$ 个与后 $6$ 个数字分别表示这条边所连接的两个点的编号。

注意，输入中可能会包含自环或重边。

outputFormat: 输出 $n-1$ 行，依次输出除了点 `000000` 本身以外，点 `000000` 到每个点的字典序最小的路径，视为整数后对 $998244353$ 取模的结果。如果点 `000000` 不可到达某个点，则在对应的行改为输出 $-1$。


title: 「PMOI-1」立方骑士

background: lhm 最近迷上了国际象棋，他对里面的骑士最感兴趣，于是就开辟了下面这个玩法。

description:
lhm 现在建立了一个大小为 $n \times m$ 的国际象棋棋盘，你作为白方要与黑方作战。棋盘上黑方只有一个国王，**国王位置不会移动**，而 lhm 有无穷无尽的骑士。现在你需要解出，最少派出几个骑士才能将死黑方国王，定义将死的标准为**黑方国王在不被吃掉的情况下不能移动为止**。

更形式化地讲：一个 $n\times m$ 的棋盘上有一个国王，你需要摆放尽可能少的骑士在棋盘上，使得对于每一个国王能走**正好一步**达到的且不在棋盘外的位置，都存在至少一个骑士能走**正好一步**达到。

棋子的移动方法：

国王每一步能向上、下、左、右、左上、右上、左下、右下八个方向移动一格。

骑士与国际象棋规则相同，每次可以走日字（即 $2\times3$ 长方形的对角线，详见样例）。**注意没有蹩马腿规则，也就是只要不走出棋盘且按照日字格行走，其他没有限制。**

lhm 太菜了，只好请聪明的你来帮他完成这个任务。

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

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

对于每组数据，一行四个整数 $n,m,x,y$，表示棋盘大小和黑方国王的坐标。

outputFormat: 输出共 $T$ 行，每行一个整数，表示最少派出骑士的个数。

hint:
【样例1解释】

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

一个类似上图的棋盘，$\text{K}$ 表示黑方国王，$\text{N}$ 表示白方骑士，$\color{red}{\times}$ 表示骑士可以到达的地方（其中 $(3,3)$ 的 $\text{N}$ 封住了 $(1,2)$ 和 $(2,1)$，$(1,4)$ 的 $\text{N}$ 封住了 $(2,2)$
，形如上图，$\text{K}$ 已经被封死了，所以两个骑士足矣。可以证明两个骑士是最小个数。

【数据范围】

- 对于 $30\%$ 的数据，保证国王的初始位置一定在棋盘最外面一圈。

- 对于 $100\%$ 的数据满足，$1 \leq t \leq 10$，$1 \leq x,y \leq 10^9$，$8 \leq n,m \leq 10^9$。


title: 「C.E.L.U-02」简易输入法

background: YQH 有一个伟大的梦想，他想成为全世界最强的男人。为了实现这一个目标，他准备从一个简易的输入法入手开始征程。

description:
这个简易输入法原先有一个词典 $\text{U}$，用户输入时，输入法从用户处读入一个字符串 $s$ ，以及一个整数 $x$ 对于这个字符串有以下几种情形：
设$s_i \in \text{U} $ 且 $s$ 为 $s_i$ 的前缀的个数为 $a$。

当 $a\ge x$ 时，请输出按照以输出次数从大到小为第一关键字，以字典序为第二关键字排序后的第 $x$ 个 $s_i$，并将其输出次数加 $1$。

当 $x>a>0$ 时，请输出按照以输出次数从大到小为第一关键字，以字典序为第二关键字排序后的最后一个 $s_i$，并将其输出次数加 $1$。

当 $a=0$ 时，输出 `404Error`。

inputFormat:
第$1$行输入一个整数 $n$，代表 $\text{U}$ 中原有 $n$ 个单词，每个原始存在的单词一开始输入次数都是 $0$。

第 $2$ 至 $n+1$ 行，每行输入一个字符串 $str$，代表一个词典中原来出现的单词。

第 $n+2$ 行输入一个整数 $m$，代表用户进行了 $m$ 次操作。

第 $n+3$ 至 $n+m+2$ 行，输入一个字符串 $s$ 和一个整数 $x$ ，含义在题目描述中已经说了。

outputFormat: 对于每一个用户的 $1$ 操作，输出一个字符串。

samples:
3
fan
fantasy
father
6
fat 1
fa 1
fan 1
fan 1
fa 1
fant 1

samples:
5
uva
usaco
usa
usssu
konjac
11
u 2
u 2
kkk 1
uv 2
us 3
u 4
u 1
u 2
k 1
u 3
usa 1

samples:
usaco
usa
404Error
uva
usssu
uva
uva
usa
konjac
usaco
usa


title: 「Wdsr-2」方分

description:
平面直角坐标系上有两个相离的正方形 $A$ 和 $B$。请找到任意一条直线把它们分隔到直线的两侧。

**注意：这条直线不应该和正方形有公共点。**

inputFormat:
**输入包含多组数据**。

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

对于每组数据，共有 $8$ 行，每行 $2$ 个实数，描述一个点的 $x$ 轴坐标和 $y$ 轴坐标。前四行表示正方形 $A$ 四个顶点的坐标，后四行表示正方形 $B$ 四个顶点的坐标。

保证这四个顶点坐标一定能构成一个正方形，但顺序可以是任意的。两个正方形一定是相离的。

**没有**保证正方形的边和坐标轴平行！

outputFormat: 对于每组数据，输出一行三个实数 $a,b,c$，表示你找到的直线方程是 $ax+by=c$。

hint:
$1\le T\le 10000$。

输入的坐标绝对值不超过 $10^3$，小数点后最多有 $3$ 位数字。

**SPJ 使用双精度浮点数计算验证你的答案，请尽可能地避免精度误差。**

避免精度误差的方式有：不要输出绝对值过大或过小的数字，输出尽可能多的小数点后位数，比较大小时使用 eps，等等。

赛后已加入 Hack 数据。


title: [ZJOI2020] 染色游戏

description:
Alice 和 Bob 在玩一个染色游戏。游戏在一张 $N$ 个点 $M(N −1 \le M \le N)$ 条边的连通图上进行，Bob 想要围住 Alice，而 Alice 想要逃出 Bob 的包围。

游戏开始时，Alice 将 $1$ 号点涂成了黑色表示占领了 $1$ 号点，Bob 将点集 $S$ 中的所有点涂成了白色表示占领了这 $|S|$ 个点，保证 $1$ 不在 $S$ 中。接下来两个人轮流进行操作，由 Alice 先 手，每轮中轮到的玩家可以从一个被自己占领的点出发 (对于 Alice 为黑色点对于 Bob 为白色 点)，选择一个相邻且未被染色的点，占领该点并染上自己的颜色。如果不存在可以染色的点， 那么这位玩家必须跳过这个回合。当所有点都被染完色时，游戏结束。

Alice 和 Bob 约定了一个图中的非空点集 $T$，如果游戏结束时 $T$ 中的点全都涂成白色，则代表 Bob 成功围住了 Alice，Bob 获胜。反之一定存在一个 $T$ 中的点被涂成黑色，那么 Alice 获胜。注意这里的 $T$ 可能会包含 $S$ 中的点和 $1$ 号点。

Alice 和 Bob 都会使用最优策略。Bob 注意到，在有些局面下，Alice 优势很大，如果能让 Alice 主动跳过 Alice 的一些行动回合来获得一个更加公平的局面，这个游戏会更有可玩性。 Bob 想知道，如果 Alice 跳过前 $k$ 个回合之后自己能够获胜，那么这个 $k$ 的最小值是多少。 Alice 只会跳过 Alice 的前 $k$ 个回合，并且在剩下的回合中采用最优策略，即你可以理解为 Bob 在 Alice 的第一回合行动之前额外行动了 $k$ 个回合。注意如果 Bob 在 Alice 跳过的一个回合中 没有合法行动，那么 Bob 仍需按照规则跳过自己的回合。如果在原图上就是 Bob 获胜那么输出 $0$。如果 $k = 1000000$ 时 Bob 也不能取胜，则输出 $1000000$。

由于这个图可能很大，我们用如下的方式生成。

- 首先生成一个含有标号为 $1$ 到 $n$ 一共 $n$ 个点的空图。
- 接下来加入 $m$ 条链，第 $i$ 条链记作 $(u_i,v_i,l_i)$，其中 $1 \le u_i,v_i \le n$ 且 $u_i \neq v_i$。
	- 首先我们加入 $l_i$ 个点，记作 $x_1^i,x_2^i,...,x_ {l_i}^i$。
	- 然后在 $(u_i,x_1^i),(x_1^i,x_2^i),(x_2^i,x_3^i),$ $...,(x_{l_i−1}^i,x_{l_i}^i),(x_{l_i}^i,v_i)$ 之间连上无向边。
	- 在这次操作之后，本轮中新加入的 $l_i$ 个点不会再与其他的点之间连边，即不同的链中的 $x_1^i ... x_{l_i}^i$ 均为互不相同的点。特别地，如果 $l = 0$，那么就不添加新点，直接在 $(u_i,v_i)$ 之间连上无向边。

保证 $S$ 集合以及 $T$ 集合的点均为一开始生成的 $n$ 个点之一。

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

- 第一行输入四个整数 $n,m,|S|,|T|$,$(1 \le|S|\le n−1,1 \le|T|\le n,n−1 \le m \le n)$。
- 接下来 $m$ 行每行输入 $3$ 个非负整数 $u_i,v_i,l_i$,$(1 \le u_i,v_i \le n,0 \le l_i \le 10^6)$，表示题面中的第 $i$ 条链。
- 接下来一行输入 $|S|$ 个数 $s_1 ... s_{|S|}$ 表示 $S$ 集合中的所有元素 ($2 \le s_i \le n$ 且不重复)。
- 接下来一行输入 $|T|$ 个数 $t_1 ... t_{|T|}$ 表示 $T$ 集合中的所有元素 ($1 \le t_i \le n$ 且不重复)。

即每组数据按照如下格式输入：

```
n m |S||T|
u_1 v_1 l_1
u_2 v_2 l_2
···
u_m v_m l_m
s_1 s_2 ··· s_|S|
t_1 t_2 ··· t_|T|
```

保证 $u_i \neq v_i$（即没有自环），保证没有相同的 $(u_i,v_i)$ 对（即没有重边），保证给出的图是一个连通图。

outputFormat: 输出 $C$ 行，对于每组测试数据，输出为了让 Bob 取胜 Alice 至少要跳过的回合数 $k$。如果在原图上就是 Bob 获胜那么输出 $0$。如果 $k = 1000000$ 时 Bob 也不能取胜，则输出 $1000000$。

hint:
![](https://cdn.luogu.com.cn/upload/image_hosting/ltfz1gns.png?x-oss-process=image/resize,m_lfit,w_500)

对于 $100\%$ 的数据，$m = n$ 或 $n−1$，$3 \le n \le 500$，$C = 10000$，$0 \le l_i \le 10^6$，$1 \le|S|\le n−1,1 \le|T|\le n$ 且保证图中不存在点数（只计算前 $n$ 个点的数量）大于 $100$ 的环，每个测试点中最多只有 $10$ 组数据满足 $n > 50$，最多只有 $1000$ 组数据满足 $n > 20$。


title: [ZJOI2020] 抽卡

description:
Bob 喜欢抽卡。

Bob 最近入坑了一款叫 “主公连结” 的抽卡游戏。游戏中共有 $n$ 个不同的角色，编号为 $1 \sim n$。当 Bob 获得其中的编号连续的 $k$ 张卡时，就可以组出理论最强阵容。

当期卡池中共有 $m$ 张不同的卡，每次抽卡，Bob 都可以等概率随机获得一张卡池中的卡。如果 Bob 抽到了一张他已经拥有的卡，那么什么事都不会发生，等于 Bob 浪费了这次抽卡机会。Bob 是个谨慎的人，他想知道，如果他不停地抽卡直到抽到编号连续的 $k$ 张卡时停止抽卡，期望需要抽多少轮。

inputFormat:
第一行输入两个整数 $m,k$。

第二行输入 $m$ 个两两不同的整数 $a_1,a_2,··· ,a_m$，表示卡池中有哪些角色。

题面中的 $n$ 即为最大的 $a_i$ 的值。

outputFormat: 输出一行一个整数，代表期望轮数对 $p = 998244353$ 取模后的结果。即，如果期望轮数的最简分数表示为 $\frac{a}{b}$，你需要输出一个整数 c 满足 $c \times b \equiv a \pmod{p}$

hint:
**样例解释 1**

如果第一轮抽到的是 $2$ 号卡，那么期望需要抽 $1 + \frac{3}{2}$ 轮；如果第一轮抽到的是 $1$ 号卡或 $3$ 号卡，那么期望需要抽 $1 + 3$ 轮。故答案为 $\frac{1}{3}(1 + \frac{3}{2}) + \frac{2}{3}(1 + 3) = 3.5$

**数据范围与约定**

对于前 $10\%$ 的数据，$m \le 10$。
对于另外 $10\%$ 的数据，$m \le 500$ 且 $k = m−1$。
对于另外 $10\%$ 的数据，$m \le 500$ 且保证有且仅有一组理论最强阵容。
对于另外 $10\%$ 的数据，$m \le 500$ 且保证任意两组可抽出的理论最强阵容不交。
对于前 $50\%$ 的数据，$m \le 500$。
对于前 $70\%$ 的数据，$m \le 5000$。
对于另外 $10\%$ 的数据，$k = 5$。
对于另外 $10\%$ 的数据，$k = 2000$。
对于 $100\%$ 的数据，$1 \le m \le 200000,1 \le a_i \le 2m,2 \le k \le m$，保证卡池中至少存在一组 可抽出的理论最强阵容（即编号连续的 $k$ 张卡）。


title: [ZJOI2020] 密码

description:
Bob 喜欢 Alice。

Alice 和 Bob 想要进行加密通信，于是他们自己设计了一套加密算法进行身份验证。你知道这个加密算法并不可靠，并截获了 Alice 和 Bob 之间的信息。现在你想要恢复出 Alice 的密钥。

Alice 和 Bob 约定了一个大质数 $p$，一个随机范围值 $err$ 和一个在 $0 \sim p - 1$ 之间均匀随机生成的整数密钥 $x$。其中 $p$ 和 $err$ 的值是公开的，而 $x$ 的值只有 Alice 和 Bob 知道。

当 Bob 想要确认 Alice 的身份时，Bob 会生成 $m$ 个在 $0\sim p-1$ 之间均匀随机生成的 $a_i$ 并发给 Alice。对于每个 $a_i$，Alice 会返回给Bob $a_i x$ 模 $p$ 的值。为了防止窃听，Alice 会给结果加上一个在 $-\lceil \frac {err}2 \rceil$ 到 $\lceil \frac {err}2 \rceil$ 之间均匀随机生成的扰动。

即，Alice 会返回给 Bob $m$ 组形如 $a_i x + b_i \equiv c_i \pmod p$ 的等式，其中 $b_i$ 为一个不公开的在 $-\lceil \frac {err}2 \rceil$ 到
$\lceil \frac {err}2 \rceil$ 之间均匀随机生成的数，$a_i$ 为随机生成的数，$a_i,p,err,c_i$ 为公开的数。

你获得了 Alice 返回的这 $m$ 组等式（即 $m$ 个 $a_i$ 和 $c_i$），你需要求出 $x$ 的值。

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

对于每组数据，第一行输入三个整数 $m,p,err$。接下来 $m$ 行，每行两个整数 $a_i,c_i$。符号的含义和题面中相同。

outputFormat:
输出 $T$ 行，
对于每组测试数据，输出一个 $0$ 到 $p - 1$ 之间整数表示答案。数据保证有解并且解唯一。

samples: 见下发文件。该样例满足题目中提到的所有随机生成的性质。


title: [CCO2020] A Game with Grundy

description:
**本题的所有讨论均在平面直角坐标系上进行。**

有 $N$ 个人，每个人有一个视野，同时每个人在 $(x_i,0)$ 的位置上。

视野可抽象为一个角。

**注意，组成角的两条射线未在视野内。**

现在，您可以站在 $(a,Y)$ 上，其中 $L\le a\le R$。

请求出，对于每个 $i(0\le i\le N)$，您可以站在多少个位置，使得您至多在 $i$ 个人的视野内。

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

第二行为三个整数 $L,R,Y$。

接下来 $N$ 行，每行三个整数，分别为 $x_i,v_i,h_i$，其中 $v_i$ 和 $h_i$ 表示，组成角的两条射线的斜率分别为 $\frac{v_i}{h_i},\frac{-v_i}{h_i}$，一端的端点为 $(x_i,0)$。

outputFormat: 共 $N+1$ 行，每行一个整数，第 $i$ 行的数表示您可以站在的位置个数，使得您至多在 $i-1$ 个人的视野内。

hint:
#### 样例解释
![](https://cdn.luogu.com.cn/upload/image_hosting/ksz1n28u.png?x-oss-process=image/resize,m_lfit,h_1700,w_2250)
#### 子任务
**本题采用捆绑测试。**
- Subtask 1（$60$ 分）：保证 $-10^6\le L\le R\le 10^6$。
- Subtask 2（$40$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $1\le N\le 10^5$，$-10^9\le L \le R\le 10^9$，$1\le Y\le 10^6$，$1\le x_i\le R$，$1\le v_i,h_i\le 100$。

#### 说明
本题译自 [Canadian Computing Olympiad 2020](https://cemc.math.uwaterloo.ca/contests/computing/2020/index.html) [Day 1](https://cemc.math.uwaterloo.ca/contests/computing/2020/cco/day1.pdf) T1 A Game with Grundy。


title: [CCO2020] Exercise Deadlines

description:
现在有 $N$ 个任务，第 $i$ 个任务需要在 $d_i$ 的时间前完成。

完成一个任务只需要 $1$ 的时间。

现在的完成顺序为 $1,2,3\ldots N$，但很显然，这种顺序有可能无法完成全部任务。

您可以交换任意**相邻**的任务序号来达到完成全部任务的结果。

举个例子：$1,2,3\ldots N\to 1,3,2\ldots N$。

您需要在保证所有任务完成的情况下，输出最小的交换次数。

如果无论如何都不能完成所有任务，请输出 `-1`。

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

第二行为 $N$ 个整数 $d_i$。

outputFormat:
仅一行一个整数，表示在保证所有任务完成的情况下，最小的交换次数。

如果无论如何都不能完成所有任务，请输出 `-1`。

hint:
#### 样例解释
#### 样例 1 解释
一种合法的完成顺序为 $1,4,3,2$，需要交换 $3$ 次。
#### 样例 2 解释
很明显，您不可能在同一时间内做完两项任务。

#### 子任务
**本题使用捆绑测试**
- Subtask 1（$68$ 分）：$N\le 5\times 10^3$。
- Subtask 1（$32$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $1\le N\le 2\times 10^5$，$1\le d_i\le N$。

#### 说明
本题译自 [Canadian Computing Olympiad 2020](https://cemc.math.uwaterloo.ca/contests/computing/2020/index.html) [Day 1](https://cemc.math.uwaterloo.ca/contests/computing/2020/cco/day1.pdf) T2 Exercise Deadlines。


title: [CCO2020] Mountains and Valleys

description:
有一个有 $N$ 个点 $M$ 条边，边有边权的无向图，图无重边、无自环，点的标号从 $0$ 开始。

共有 $N-1$ 条边的边权为 $1$，其余边的边权均 $\ge \lceil \frac{N}{3} \rceil$ 且 $\le N$，同时，如果仅考虑边权为 $1$ 的边，整个图会是一棵树。

现在您要遍历每个点一遍，且使经过的边权总和最小。

求最小的边权总和。

**提醒：**
- 您可以往返走一条边。
- 您可以任选一个点出发。
- 您只有一个人。

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

接下来 $M$ 行，一行三个整数 $x_i,y_i,w_i$，表示有一条从 $x_i$ 到 $y_i$，边权为 $w_i$ 的边。

outputFormat: 遍历每个点一遍，所需最小的边权总和。

hint:
#### 样例解释
![](https://cdn.luogu.com.cn/upload/image_hosting/5ftpjk6m.png?x-oss-process=image/resize,m_lfit,h_1700,w_2250)

最优路径为 $4\to 1\to 0\to 2\to 5\to 2\to 6\to 7\to 3\to 8$，边权和为 $1+1+1+1+1+1+3+1+1=11$。

#### 子任务
**本题使用捆绑测试。**
- Subtask 1（$4$ 分）：保证 $N\le 6$，$M\le 10$。
- Subtask 2（$8$ 分）：保证 $N\le 20$，$M\le 40$。
- Subtask 3（$8$ 分）：保证 $N\le 5\times 10^3$，$M\le 10^5$，$w_i=1$ 或 $\lceil\frac{N}{2}\rceil\le w_i\le N$。
- Subtask 4（$24$ 分）：保证 $N\le 100$，$M\le 200$。
- Subtask 5（$8$ 分）：保证 $N\le 500$，$M\le 10^3$。
- Subtask 6（$12$ 分）：保证 $N\le 5\times 10^3$，$M\le 10^5$。
- Subtask 7（$20$ 分）：保证 $N\le 8\times 10^4$，$M\le 1.6\times 10^5$。
- Subtask 8（$16$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $4\le N\le 5\times 10^5$，$N-1 \le M\le 2\times 10^6$，$0\le x_i,y_i\le N-1$，$w_i=1$ 或者 $\lceil \frac{N}{3}\rceil\le w_i\le N$。

#### 说明
本题译自 [Canadian Computing Olympiad 2020](https://cemc.math.uwaterloo.ca/contests/computing/2020/index.html) [Day 1](https://cemc.math.uwaterloo.ca/contests/computing/2020/cco/day1.pdf) T3 Mountains and Valleys。

因为本题数据点较多（$119$ 个），所以本题测试点有删减。


title: 【征集 SPJ】[COCI2019-2020#2] Slagalica

background:
## 本题征集 SPJ。但若您写的是正解，即，输出了字典序最小解，仍可获得 AC 的评测结果。

小斌喜欢玩拼图。

description:
小斌得到了一个由 $n$ 个部分组成的一维拼图游戏。他很快意识到每块拼图都属于以下类型之一：

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

另外，已知在这 $n$ 片拼图中，恰好有一个 $5$ 号拼图或 $6$ 号拼图（左边框）和一个 $7$ 号拼图或 $8$ 号拼图（右边框）。

小斌希望将所有块排列成一行，以使第一个（最左边的）拼图类型为 $5$ 号拼图或 $6$ 号拼图，而最后一个（最右边的）拼图类型为 $7$ 号拼图或 $8$ 号拼图。如果有两块拼图，则可以彼此相邻放置，并且仅当它们的相邻边框的形状不同时，即一个边框具有凹凸，而另一个边框具有一个凸出才可以相邻放置。

对于小斌来说，这个问题太简单了，因此他决定在每个部分上写一个唯一的正整数。现在，他想要寻找出字典序最小的方案。

注意：拼图不能旋转！

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

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

接下来，$n$ 行，包含两个整数 $x_i$ 和 $a_i$，它们表示 $i$ 的类型，$x_i$ 拼图编号，$a_i$ 表示 Fabian 在上面写的数字。数据保证所有 $a_i$ 不重复。

outputFormat:
输出数据共一行。

第一行，如果小斌无法解决拼图游戏，输出 `-1`。 否则，您应该输出拼图上数字按字典序排列最小的方案。

hint:
#### 样例 #1 解释
只有 $2$ 种解法，如下：

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

可以看出，第二种解法的字典序较小，所以输出 `1 3 7 5 4`。

#### 数据规模及约定

对于 $100\%$ 的数据，$2 \le n \le 10^5, 1 \le x_i \le 8, 1 \le a_i \le 10^9$。

没有给出字典序最小解而只构造一组解可以得到 $40\%$ 的分数。

#### 说明

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

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #2](https://hsin.hr/coci/archive/2019_2020/contest2_tasks.pdf) *T2 Slagalica*。**


title: [HNOI2016] 序列 加强版

background:
本题是 [P3246](https://www.luogu.com.cn/problem/P3246) 的数据加强版，扩大了询问次数的范围，增加了强制在线，并加入了一组构造数据。

本题的输入输出格式与原题略有不同。

description:
给定长度为 $ n $ 的序列：$ a_1, a_2, \cdots , a_n $，记为 $ a[1 \colon n] $。类似地，$ a[l \colon r] $（$ 1 \leq l \leq r \leq N$）是指序列：$ a_{l}, a_{l+1}, \cdots ,a_{r-1}, a_r $。若 $1\leq l \leq s \leq t \leq r \leq n$，则称 $ a[s \colon t] $是 $ a[l \colon r] $ 的子序列。

现在有 $ q $ 个询问，每个询问给定两个数 $ l $ 和 $ r $，$ 1 \leq l \leq r \leq n $，求 $ a[l \colon r] $ 的不同子序列的最小值之和。例如，给定序列
 $ 5, 2, 4, 1, 3 $，询问给定的两个数为 $ 1 $ 和 $ 3 $，那么 $ a[1 \colon 3] $ 有 $ 6 $ 个子序列 $a[1 \colon 1], a[2 \colon 2], a[3 \colon 3], a[1 \colon 2],a[2 \colon 3], a[1 \colon 3] $，这 $6 $ 个子序列的最小值之和为 $5+2+4+2+2+2=17$。

inputFormat:
第一行三个整数 $n$，$q$，$type$ 表示序列长度，询问数与输入方式。

第二行 $n$ 个整数表示这个序列。

若 $type=0$，接下来 $q$ 行，每行两个数 $l$，$r$，代表询问区间 $[l,r]$。

若 $type=1$，则数据按照如下代码生成：
```cpp
namespace gen{
	typedef unsigned long long ull;
	ull s,a,b,c,lastans=0;
	ull rand(){
		return s^=(a+b*lastans)%c;
	}
};
```
其中，`s`，`a`，`b`，`c` 的初始值在第三行给出，满足 `s`，`a`，`b` 均在 $[0,10^9]$ 之间，`c` 在 $[1,10^9]$ 之间。`lastans` 表示上次询问的答案转化为 `unsigned long long` 类型后的值，第一次询问时值为 $0$。

每次询问时，你可以通过下面的方式生成 $l$ 和 $r$：
```cpp
l=gen::rand()%n+1;
r=gen::rand()%n+1;
if(l>r) std::swap(l,r);
```

outputFormat: 一行一个整数，表示每次询问的答案转成 `unsigned long long` 类型后的异或和。


title: 一阶微分方程

background: 题目中 $F'(x)$ 右侧的式子可以换成其它的，这里为了方便测试，是固定的。

description:
已知多项式 $F(x),A(x),B(x)$，满足：

$$\frac{\text dF(x)}{\text dx} \equiv A(x)\text e^{F(x)-1}+B(x) \pmod{x^n}$$
且 $F(0)=1$。

给定 $A(x),B(x)$，请求出 $F(x)$ 的前 $n$ 次项系数。

答案对 $998244353$ 取模。

inputFormat:
第一行一个正整数 $n$，表示 $A(x),B(x)$ 的次数。
第二行 $n+1$ 个整数，由低到高表示 $A(x)$ 的系数。
第三行 $n+1$ 个整数，由低到高表示 $B(x)$ 的系数。

outputFormat: 输出一行 $n+1$ 个整数，由低到高表示 $F(x)$ 的系数。


title: [Code+#7] 蚂蚁

description:
在东西排布的两棵树之间悬挂着一条长为 $L$ 的细绳，有 $N$ 只蚂蚁在这条绳上。这些蚂蚁希望通过绳子爬到任何一棵树上，但这条绳太细了，导致两只蚂蚁不能并排爬行，也不能交错而过。

它们想到了一个方法：每只蚂蚁都以每单位时间移动一个单位距离的速度不断向前爬，当迎面碰到另一只蚂蚁时，两只蚂蚁都将立即掉头并继续向前爬。现在，蚂蚁们想知道自己是否能爬下绳子，如果能，它们还希望知道自己爬下绳子所花的时间。为了方便，我们按初始时位置从东到西的顺序对蚂蚁从 $1$ 开始编号。

inputFormat:
输入的第一行包含两个正整数 $N, L$，保证 $N\le 10^5, L\le 10^9$，且 $N<L$。

输入的第二行包含 $N$ 个正整数，第 $i$ 个数 $p_i$ 表示第 $i$ 只蚂蚁到东侧树木的距离，保证 $p_i$ 随 $i$ 增大严格递增，且 $0<p_i<L$。

输入的第三行包含 $N$ 个整数，第 $i$ 个数 $d_i$ 若为 $1$ 则表示第 $i$ 只蚂蚁一开始朝向西侧，为 $0$ 则表示朝向东侧。

outputFormat: 输出仅一行，包含 $N$ 个数，第 $i$ 个数表示第 $i$ 只蚂蚁爬下绳子所花时间，四舍五入保留到整数。若第 $i$ 只蚂蚁无法爬下绳子，则输出的第 $i$ 个数为 $-1$。

hint:
### 样例解释

第三只蚂蚁在爬行 $1$ 个单位时间后遇见第二只蚂蚁并掉头，再爬行 $2$ 个单位时间到西侧树木；

第二只蚂蚁在爬行 $1$ 个单位时间后遇见第三只蚂蚁并掉头，再爬行 $1$ 个单位时间后遇见第一只蚂蚁并掉头，再爬行 $3$ 个单位时间到西侧树木；

第一只蚂蚁在爬行 $2$ 个单位时间后遇见第二只蚂蚁并掉头，再爬行 $3$ 个单位时间到东侧树木。

### 子任务

子任务 $1$（$17$ 分）
- $1\le N\le 10, L\le 10^5$。

子任务 $2$（$19$ 分）
- $1\le N\le 100, L\le 10^9$。

子任务 $3$（$27$ 分）
- $1\le N\le 5000, L\le 10^9$。

子任务 $4$（$37$ 分）
- $1\le N\le 10^5, L\le 10^9$。


title: [Code+#7] 神秘序列

description:
E.Space 做了一个梦。

他梦到了一个神秘的序列，有人告诉他，这个序列和明天的考试有一些密切的关联。

他决心要把这个序列记住。可醒来之后，E.Space 发现自己没有记住这个序列，甚至连序列的长度都不记得了。不过，他记得这个序列有一个神奇的性质。

在梦中，E.Space 对它进行了一系列的操作。记这个序列为 $a_1, a_2, \dots, a_n$，开始时它满足 $\forall 1\le i\le n, a_i \ge 0$，并且 $a_n \neq 0$。

之后，E.Space 在每次操作时选择一个满足 $a_i=i$ 的 $i$，将 $a_i$ 变为 $0$，并且将 $a_1, a_2, \dots, a_{i-1}$ 分别变为原来的值加 $1$。

E.Space 记得，在 $n+k$ 次操作之后，这个序列变成了全 $0$ 序列，即 $a_1=a_2=\cdots =a_n= 0$。

E.Space 知道可能有多个序列满足这个性质，但是他还是希望你告诉他一种可能的情况，因为，说不定所有满足这个性质的序列都可以在考试时派上用场呢。

他的考试成绩就交给你了。

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

outputFormat:
如果你找到了满足 E.Space 描述的性质的序列，那么输出两行。

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

第二行 $n$ 个非负整数，$a_1, a_2, \dots, a_n$，其中 $a\neq 0$，表示这个神秘序列。

如果存在多种可能的神秘序列，只需输出任意一种。如果不存在这样的神秘序列，输出一行 `Daydream!` 来告诉 E.Space 他在做白日梦。


title: [Code+#7] 同余方程

description:
这就是一些朴素的二次同余方程:)

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

给出若干组正整数 $p$ 和 $x$，求方程 $a^2+b^2\equiv x {\pmod p}$ 关于 $a$ 和 $b$ **在模 $\boldsymbol p$ 意义下**解的组数，其中 $p$ 是奇数，且不包含平方因子。

inputFormat:
第一行包含一个正整数 $n$，表示询问个数。

接下来 $n$ 行每包含两个用空格分隔的正整数 $p$ 和 $x$，保证 $0 \le x \le p - 1$，$p$ 是一个奇数，且对任意奇素数 $q\mid p$，都有 $q^2 \nmid p$。

outputFormat: 输出包含 $n$ 行，第 $i$ 行包含一个正整数，表示第 $i$ 个方程解的组数。


title: [Code+#7] 六元环

description:
qwqwq。

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

给定序列 $a_0, a_1, \dots, a_n, a_{n+1}$；满足 $a_0 = a_{n+1} = +\infty$，$a_1, a_2, \dots, a_n$ 在输入中给出；

对 $1\le x\le n$，称 $\max_{0\le i<x, a_i\ge a_x} i$ 和 $x$ 是相邻的，且 $\min_{x< i\le n+1, a_i>a_x} i$ 和 $x$ 是**相邻**的；如果 $x$ 和 $y$ 相邻，则 $y$ 和 $x$ 也相邻；

如果 $0 \le b_1, b_2, b_3, b_4, b_5, b_6\le n+1$，且 $b_i$ 和 $b_{i+1}$ 相邻，$b_1$ 和 $b_6$ 相邻，$b_i$ 互不相同，则称集合 $\{b_1,b_2,b_3,b_4,b_5,b_6\}$ 是一个六元环（即判断两个六元环是否相同时，不考虑 $b_i$ 的顺序）。

共有 $m$ 次修改操作，每次修改操作给出 $x\ y$，将 $a_x$ 改为 $a_x + y$；每次修改后要求输出六元环的个数；

以上提到的所有数值为整数，且 $1\le n, m\le 5\times 10^5, 1\le x\le n,1\le a_i, y\le 10^9$。

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

第二行 $n$ 个整数表示 $a_1, a_2, \dots, a_n$；

第三行一个整数 $m$；接下来 $m$ 行，每行两个整数 $x\ y$ 表示一次修改操作。

outputFormat: 共 $m$ 行，每行一个整数，表示每次修改后的六元环个数。


title: [COCI2019-2020#2] Checker

background: > "...fool me once, shame on — shame on you. Fool me — you can't get fooled again." — W

description:
有一种规则多边形 ，它们的 $n$ 边分别用某三种颜色之一着色，并且其顶点按顺时针顺序从 $1$ 到 $n$ 表示。

多边形的三角剖分是指将其面积分解为一组不重叠的三角形的操作，这些三角形的边可能是多边形的边或其内对角线上。当然，在此任务中，用于多边形三角剖分的每条对角线也用三种颜色之一着色。

如果每个三角形的 $n\space−\space2$ 个三角形的所有三个面都具有不同的颜色，则称这样的三角剖分是“非常好”的。

您的任务是确定给定的对角线多边形是否被三角剖分以及该三角剖分是否非常好。

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

第一行，一个正整数 $T$，表示这个数据对应的 Subtask 编号。

第二行，一个正整数 $n$，含义见 **题目描述** 部分。

第三行，一个 $n$ 位数正整数，这些数字代表多边形边的颜色。更准确地说，第一个数字代表边 $(1, 2)$ 的颜色，第二个数字代表边 $(2, 3)$ 的颜色，第 $i$ 个数字表示边 $(i, i+1)$ 的颜色，**特别的**，第 $n$ 个数字表示边 $(n, 1)$ 的颜色。颜色用数字 $1, 2, 3$ 表示。

接下来的 $n-3$ 行，每一行都包含对一个对角线的描述，格式为 `x y c`，其中 $x$ 和 $y$ 是多边形顶点，$c$ 是对角线的颜色。数据保证顶点 $x$ 和 $y$ 既不相等也不相邻。

outputFormat:
输出数据共一行。

- 如果输入多边形没有正确三角剖分，则应输出 $\mathtt{neispravna \space triangulacija}$。
- 如果输入多边形有正确三角剖分，但三角剖分不是好的，则应输出 $\mathtt{neispravno \space bojenje}$。
- 否则，输出 $\mathtt{tocno}$。

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

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

| Subtask 编号 | Subtask 分数 | Subtask 数据规模及约定 |
| :----------- | :----------- | :----------- |
| $1$ | $12$ | $4 \le n \le 300$ |
| $2$ | $17$ | $4 \le n \le 2000$ |
| $3$ | $23$ | $4 \le n \le 2 \times 10^5$，数据保证输出为 $\mathtt{neispravna \space triangulacija}$ 或 $\mathtt{tocno}$ |
| $4$ | $23$ | $4 \le n \le 2 \times 10^5$，数据保证输出为 $\mathtt{neispravno \space bojenje}$ 或 $\mathtt{tocno}$ |
| $5$ | $35$ | $4 \le n \le 2 \times 10^5$ |

**特别的**，对于 $100\%$ 的数据，$1\le T\le 5$。

#### 说明

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

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #2](https://hsin.hr/coci/archive/2019_2020/contest2_tasks.pdf) *T3 Checker*。**


title: 「RdOI R1」序列(sequence)

description:
有一序列 $x$ ，长度为 $q$ ，序列中的每个数只出现一次。

即：序列 $x$ 是 $1$ 到 $q$ 的一个排列。

对于序列 $x$ 的操作只有一种：对于一个数 $x_i$ ，你可以使其与 $x_{2i}$ 或 $x_{2i+1}$ 交换位置(如果它们存在的话)。

现在请你使序列 $x$ 变为一个升序序列，并按顺序输出你进行的操作。

inputFormat:
输入数据共 $2$ 行。

第 $1$ 行， $1$ 个正整数，$q$。

第 $2$ 行， $q$ 个正整数， $x_{1～q}$。

outputFormat:
输出数据共 $ans$ 行， $ans$ 表示你的操作次数。

第 $1$ ~ $ans$ 行，每行两个整数，$i$ ，$j$ ，表示交换 $x_i$ 和 $x_j$ 的位置 $(i < j)$。

hint:
【样例说明】

样例#1说明：

交换 $2$ 和 $3$ ，序列变为：$2,1,3$。

再交换 $2$ 和 $1$ ，序列变为：$1,2,3$。

【数据范围】

对于 $40\%$ 的数据，$3 \le q \le 2^{10}$。

对于 $100\%$ 的数据，$3 \le q \le 2^{17}$，$1 \le x_i \le q$。

【提示】

- 使用 Special Judge。
- $q = 2 ^ p - 1(p \in \mathbb{N}^*)$
- 最多进行 $2q\times\lceil\log_2 q\rceil$ 次操作。
- 样例的输出数据只是众多方案中的一种。
- 因为是 `special judge` ，因此不提供附加样例。

---

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

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


title: 「C.E.L.U-01」超越维度

background: 代号为"S-Q"科技探索计划的成功实现使得小 Soup 和罗司机进入了一个虚拟的 $k$ 维空间中，它们准备对这个 $k$ 维空间进行一番创造。

description:
小 Soup 和罗司机给了你 $n$ 个操作。
操作$1$：小 Soup 向 $k$ 维空间中加入一个正 $k$ 维超立方体。
操作$2$：罗司机给出一个正 $k$ 维超立方体，求当前已存在的超立方体与这个正 $k$ 维超立方体的体积交，然后输出答案 $\text{mod}\ 1919810\ $的值。

inputFormat:
第一行两个数，$n,k$，含义已解释。
第$2\sim n+1$ 行，每行 $k+2$ 个数，第一个数代表操作编号，接下来 $k$ 个数代表这个正 $k$ 维超立方体的中心点在 $k$ 维坐标系中的坐标，最后一个数代表这个中心点与每个 $k-1$ 维超平面的距离（它们都是相等的）。

outputFormat: 对于每一个操作$2$，输出一个数。

hint:
**样例1解释：**
如图，橙色框为两个加入的正方形，绿色框为询问，绿色块为答案。
![](https://cdn.luogu.com.cn/upload/image_hosting/juqwca7d.png)

**样例3解释：**

如图（红色标出部分为询问2答案）（两个解释不是同一个人造的）：

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

**数据范围**

$\begin{array}{|c|c|c|}数据编号&n&k\\1&500&1\\2\sim3&500&2\\4\sim6&500&3\\7\sim10&500&\le6\end{array}$
输入输出的数在 $\text{long long}$ 范围内，保证数据随机（正k维超立方体较分散）。


title: [CCO2020] Travelling Salesperson

description:
有一个有 $N$ 个点的完全图，边权为 $1$，边是红色或蓝色。

对于每一个点，您需要构造从该点出发，经过每一个点至少一次且边权和最小的路径。

为了增大难度，我们要求您从一条边走到另一条异色的边需花费一张票，并且您只有一张票。

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

接下来 $N$ 行，一行一个字符串，第 $i$ 行的字符串为 $C_i=C_{i,1},C_{i,2}\ldots C_{i,i-1}$，如果 $C_{i,j}$ 为 `R`，说明从 $i$ 到 $j$ 的边为红色的，反之，则为蓝色。

outputFormat:
输出共 $2\times N$ 行。

对于 $2\times i-1(1\le i\le N)$ 行，您需要输出一个整数 $M_i$，表示您所构造的从 $i$ 出发的遍历每一个点的方案的长度。

对于 $2\times i (1\le i\le N)$ 行，您需要输出 $M_i$ 个整数，表示您的方案所遍历点的顺序。

hint:
#### 样例解释
![](https://cdn.luogu.com.cn/upload/image_hosting/j79801x8.png?x-oss-process=image/resize,m_lfit,h_170,w_225)

聪明的你一定发现了这个样例输出不是最优的。

从 $3$ 出发的话，有最优方案为 $3\to 1\to 2\to 4$，长度为 $4$，所以这个方案得 $\lfloor 8+8\times \frac{2\times 4-5}{4-1}\rfloor=16$ 分。

#### SPJ 计分策略
本题的每个测试点按您设计的路线计分。

对于您设计的第 $i$ 个方案，设其长度为 $M_i$，标准答案的第 $i$ 个方案长度为 $K_i$。

如果 $M_i>2\times K_i$ 或者您的方案错误，您会得 $0$ 分。

如果 $M_i=K_i$ 且您的方案合法，您会得 $25$ 分。

否则，如果您的方案合法，您会得 $\lfloor 8+8\times \frac{2\times K_i-M_i}{K_i-1}\rfloor$ 分。

这个测试点的分数为每个方案的得分的最小值。

您的提交得分为每个测试点得分的最小值。

**译者提醒：为了方便 SPJ 的编写和测试点的计分，每个测试点 $100$ 分，题目的计分策略里的所有分数会按比例计算。**

#### 数据范围及限制
对于 $100\%$ 的数据，保证 $1\le N\le 2\times 10^3$，$C_{i,j}$ 为 `R` 或 `B`。

#### 说明
本题译自 [Canadian Computing Olympiad 2020](https://cemc.math.uwaterloo.ca/contests/computing/2020/) [Day 2](https://cemc.math.uwaterloo.ca/contests/computing/2020/cco/day2.pdf) T1 Travelling Salesperson。

本题数据有删减。

感谢 @[tiger2005](https://www.luogu.com.cn/user/60864) 提供的 SPJ。


title: [清华集训2016] 数据交互

description:
一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据交互时，数据会经过连接这两个服务器的路径上的所有服务器（包括这两个服务器自身）。每个数据交互请求都有一个非负的重要度，越重要的请求显然需要得到越高的优先处理权。此外，如果在某一个时刻存在一条非常重要（可以看作重要度无穷大）、且数据量巨大的交互请求，则所有被该交互经过的服务器都会优先处理这条交互并阻塞，从而导致其他通过这些服务器的交互出现延迟。

现在，你作为一个网络系统的管理员，要监控整个系统的运行状态。系统的运行也很简单，在每一个时刻，只有可能出现下列二种事件中的一种：

- 在某两个服务器之间出现一条新的数据交互请求；
- 某个数据交互请求结束。

我们假设这些事件中的交互请求的数据量都足够小。你的任务是在每一个时刻的事件结束后，求出：如果突然出现一条非常重要、且数据量巨大的交互请求，那么因其造成延迟的数据交互请求的重要度之和最大可能是多少？

inputFormat:
输入的第一行包含二个正整数 $n,m$，分别表示服务器的个数、事件（时刻）的个数。

接下来 $n−1$ 行，每行两个整数 $u,v$，描述一条树边。$u$ 和 $v$ 是服务器的编号，服务器编号为 $1,…,n$。

接下来 $m$ 行，按发生时刻依次描述每一个事件；即第 $i$ 行（$i=1,2,3,…,m$）描述时刻 $i$ 发生的事件。事件的描述有两种：

- `+ u v w`：服务器 $u$ 和 $v$ 之间出现了一条重要度为 $w$ 的数据交互请求；
- `- t`：时刻 $t$ 出现的数据交互请求结束。

outputFormat: 输出 $m$ 行，每行一个整数，依次描述在每个事件后，如果突然出现一条非常重要、且数据量巨大的交互请求，那么因其造成延迟的数据交互请求的重要度之和的最大值。如果此时没有任何数据交互请求，输出 $0$。

hint:
对于 $30\%$ 的数据，有 $1≤n,m≤100$。

另有 $30\%$ 的数据，没有第二类事件，即所有请求都不会结束。

对于 $100\%$ 的数据，有 $1≤n,m≤10^5$，所有的输入数据均为 `int` 范围内的非负整数。

保证输入合法。


title: [清华集训2016] 如何优雅地求和

description:
有一个多项式函数 $f(x)$，最高次幂为 $x^m$，定义变换 $Q$：

$$Q(f,n,x)=∑_{k=0}^{n}f(k)\binom nkx^k(1−x)^{n−k}$$

现在给定函数 $f$ 和 $n,x$，求 $Q(f,n,x)\bmod998244353$。

出于某种原因，函数 $f$ 由点值形式给出，即给定 $a_0,a_1,⋯,a_m$ 共 $m+1$ 个数，$f(x)=a_x$。可以证明该函数唯一。

inputFormat:
第一行三个整数 $n,m,x$，意义如前所述。

第二行共 $m+1$ 个整数，表示 $a_0,a_1,⋯,a_m$。

outputFormat: 输出一行一个数表示答案，请对 $998,244,353$ 取模。


title: [清华集训2016] 连通子树

description:
小 M 至上主义者小 D 今天心情很好，准备给小 M 准备一个圣诞礼物。

他购买了一个圣诞树，这个圣诞树是一个有 $n$ 个点的树，点 $i$ 有一个颜色 $c_i$。小 D 觉得如果某种颜色太多就不好看了，所以最多会有 $5$ 个点有相同的颜色。

小 M 收到了礼物很高兴，但是她最近对计数问题很感兴趣，于是她有一些问题想要小 D 解决。每次小 M 会关心三种不同的颜色 $a,b,c$，她想要知道这个圣诞树有多少个不同的非空联通子图满足里面颜色为 $a,b,c$ 的点的个数分别为 $na,nb,nc$。由于数可能很大，输出关于对 $10^9+7$ 取模的余数就可以了。

小 D 当然轻松解决了这个问题，你虽然被喂了狗粮，但你也想锻炼你的实力，你能解决这个问题吗？

inputFormat:
第一行两个数 $n$ 和 $Q$，表示树的大小和询问的个数。

第二行 $n$ 个数，其中第 $i$ 个表示 $c_i$，为第 $i$ 个节点的颜色。

接下来 $n-1$ 行，每行两个数 $a$ 和 $b$，表示点 $a$ 和点 $b$ 之间有一条边。

接下来 $Q$ 行，其中每行有 $6$ 个数 $a,na,b,nb,c,nc$，表示如题目中所述的询问。

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

hint:
#### 限制与约定

$1≤i≤n$，$1≤c_i≤n$。

对于每个询问我们有：$0≤na,nb,nc≤5$，$1≤a,b,c≤n$ 以及 $a,b,c$ 两两不同。

对于 $10\%$ 的询问，$n,Q≤10$。

对于另 $10\%$ 的询问，$n≤15$，$Q≤50$。

对于另 $10\%$ 的询问，$n,Q≤1000$。

对于另 $5\%$ 的询问，$n,Q≤50000$，并且输入的树如果以点 $1$ 为根，最大深度不超过 $35$（点 $1$ 的深度为 $0$）。

对于另 $5\%$ 的询问，$n,Q≤100000$，并且输入的树如果以点 $1$ 为根，最大深度不超过 $35$（点 $1$ 的深度为 $0$）。

对于另 $20\%$ 的询问，$n,Q≤100000$，并且保证所有询问 $(na+1)^2(nb+1)^2(nc+1)^2$ 的和小于等于 $10^8$。

对于另 $40\%$ 的询问，$n,Q≤100000$，并且保证所有询问 $(na+1)(nb+1)(nc+1)$ 的和小于等于 $8\times 10^6$。


title: [清华集训2016] 组合数问题

description:
组合数 $C_n^m$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1,2,3)$ 三个物品中选择两个物品可以有 $(1,2),(1,3),(2,3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $C_n^m$ 的一般公式：

$$C_n^m=\dfrac{n!}{m!(n-m)!}$$

其中 $n!=1×2×⋯×n$。（额外的，当 $n=0$ 时，$n!=1$）

小葱想知道如果给定 $n,m$ 和 $k$，对于所有的 $0≤i≤n,0≤j≤\min(i,m)$ 有多少对 $(i,j)$ 满足 $C^j_i$ 是 $k$ 的倍数。

答案对 $10^9+7$ 取模。

inputFormat:
第一行有两个整数 $t,k$，其中 $t$ 代表该测试点总共有多少组测试数据。

接下来 $t$ 行每行两个整数 $n,m$。

outputFormat: $t$ 行，每行一个整数代表所有的 $0≤i≤n,0≤j≤\min(i,m)$ 中有多少对 $(i,j)$ 满足 $C^j_i$ 是 $k$ 的倍数。

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

在所有情况中，只有 $C_{2}^{1}=2$ 是 $2$ 的倍数。

#### 限制与约定

对于 $20\%$ 的测试点，$1≤n,m≤100$；

对于另外 $15\%$ 的测试点，$n≤m$；

对于另外 $15\%$ 的测试点，$k=2$；

对于另外 $15\%$ 的测试点， $m\le10$；

对于 $100\%$ 的测试点， $1≤n,m≤10^{18}$，$1≤t,k≤100$，且 $k$ 是一个质数。


title: [清华集训2016] 汽水

description:
牛牛来到了一个盛产汽水的国度旅行。

这个国度的地图上有 $n$ 个城市，这些城市之间用 $n−1$ 条道路连接，任意两个城市之间，都存在一条路径连接。这些城市生产的汽水有许多不同的风味，在经过道路 $i$ 时，牛牛会喝掉 $w_i$ 的汽水。牛牛非常喜欢喝汽水，但过量地饮用汽水是有害健康的，因此，他希望在他旅行的这段时间内，平均每天喝到的汽水的量尽可能地接近给定的一个正整数 $k$ 。

同时，牛牛希望他的旅行计划尽可能地有趣，牛牛会先选择一个城市作为起点，然后每天通过一条道路，前往一个没有去过的城市，最终选择在某一个城市结束旅行。

牛牛还要忙着去喝可乐，他希望你帮他设计出一个旅行计划，满足每天 $|P−k|$（$P$ 为平均每天喝到的汽水量）的值尽量小，请你告诉他这个最小值。

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

接下来 $n−1$ 行，每行三个正整数 $u_i,v_i,w_i$，表示城市 $u_i$ 和城市 $v_i$ 之间有一条长度为 $w_i$ 的道路连接。

同一行相邻的两个整数均用一个空格隔开。

outputFormat: 一行一个整数，表示答案的最小值的整数部分，即你只要将这个最小值向下取整然后输出即可。

hint:
#### 样例解释

在图中，路径 $5\to1\to3$ 是一条最合适的路线，总计喝到的汽水的量是 $27+12=39$, 平均每天喝到的汽水量是 $39÷2=19.5$, $|19.5−21|=1.5$，向下取整后得到 $1$，因此答案是 $1$。

#### 数据范围

对于 $20\%$ 的数据，$n≤1000$。

对于另外 $20\%$ 的数据，保证编号为 $i(1≤i≤n−1)$ 的节点和编号为 $i+1$ 的节点之间连接了一条边。

对于另外 $20\%$ 的数据，保证数据是以 $1$ 为根的完全二叉树（在完全二叉树中，节点 $i(2≤i≤n)$ 和节点 $⌊i÷2⌋$ 之间有一条道路）。

对于另外 $20\%$ 的数据，保证除节点 $1$ 以外，其他节点和节点 $1$ 之间都有一条道路。

对于 $100\%$ 的数据，$1≤n≤5×10^4$，$0≤w_i≤10^{13}$，$0≤k≤10^{13}$。


title: [CCO2020] Interval Collection

background: 本题题面来自 [LOJ](https://loj.ac/p/3321)。

description:
Altina 正进行区间收藏。一对满足 $l < r$ 的正整数 $[l, r]$ 为一个区间，我们称这样的区间的长度为 $r - l$。

我们称区间 $[l, r]$ 包含区间 $[x, y]$，当且仅当 $l \le x$ 并且 $y \le r$。特别地，每个区间都包含自身。

定义一个非空集合 $S$ 的**最大公共子区间**为被 $S$ 中每个区间都包含的区间中最长的那个，如果没有这样的区间则未定义。

定义一个非空集合 $S$ 的**最小公共超区间**为包含 $S$ 中每个区间的区间中最短的那个，注意这样的区间总是存在。

初始时，Altina 的收藏中没有任何区间。接下来会发生 $Q$ 个事件，对 Altina 的收藏产生改变。

1. Altina 往她的收藏中添加一个区间 $[l, r]$，如果此时收藏中已有 $[l, r]$，应该被算作不同的两个区间。
2. Altina 移除一个在收藏中已经存在的区间 $[l, r]$，如有多个只以移除恰好一个。

在每个事件发生后，Altina 选择一个她的收藏中的非空子集 $S$，并且满足如下条件：

- 在所有的选取方案中，她会选择最大公共子区间未定义的。如果不存在这样的方案，则她会选择最大公共子区间的长度最小的。
- 在所有的满足上述条件的集合 $S$ 中，她会选择最小公共超区间的长度最小的。

请你在每一个事件发生后，输出 Altina 会选择的集合 $S$ 的最小公共超区间的长度。

inputFormat:
第一行一个正整数 $Q$，表示将会发生的事件的个数。
接下来 $Q$ 行，每行描述一个事件，格式如下：

- $\mathtt{A}\;l\;r$：添加一个区间 $[l, r]$ 到 Altina 的收藏中。
- $\mathtt{R}\;l\;r$：从 Altina 的收藏中移除一个区间 $[l, r]$，保证这个区间在她的收藏中存在，且移除后她的收藏非空。

outputFormat: 输出 $Q$ 行，每行一个正整数表示每个事件发生后 Altina 会选择的集合 $S$ 的最小公共超区间的长度。

hint:
#### 样例解释
加入 $[1,5]$，选择 $[1,5]$ 最优，答案为 $4$。

加入 $[2,7]$，选择 $[1,5],[2,7]$ 最优，答案为 $7-1=6$。

加入 $[4,6]$，选择 $[1,5],[4,6]$ 最优，答案为 $6-1=5$。

加入 $[6,8]$，选择 $[4,6],[6,8]$ 最优，答案为 $8-4=4$。

删除 $[4,6]$，选择 $[1,5],[6,8]$ 最优，答案为 $8-1=7$。

#### 子任务
**本题使用捆绑测试**

- Subtask 1（$12$ 分）：$Q\le 500$。
- Subtask 2（$32$ 分）：$Q\le 1.2\times 10^4$。
- Subtask 3（$28$ 分）：$Q\le 5\times 10^4$。
- Subtask 4（$16$ 分）：对于任两个区间 $(l_1,r_1)$ 和 $(l_2,r_2)$，保证 $r_1<l_2$ 或者 $r_2<l_1$。
- Subtask 5（$12$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $1\le Q\le 5\times 10^5$，$1\le l,r\le 10^6$。

#### 说明
本题译自 [Canadian Computing Olympiad 2020](https://cemc.math.uwaterloo.ca/contests/computing/2020/) [Day 2](https://cemc.math.uwaterloo.ca/contests/computing/2020/cco/day2.pdf) T2 Interval Collection。

本题数据有所删减。


title: [CCO2020] Shopping Plans

description:
有 $N$ 个商品，每个商品有个种类 $a_i$，有个价格 $c_i$。

对于第 $j$ 个种类，必须购买个数位于 $[x_j,y_j]$ 的商品，即最少购买 $x_j$ 个，最多购买 $y_j$ 个该种类的商品。

您需要求出前 $K$ 种便宜的方案所需的价钱，如果没有这样的方案，请输出 `-1`。

特别的，如果有相同钱数，但是具体方案不相同的，算作两种方案。

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

接下来 $N$ 行，一行两个整数 $a_i,c_i$。

接下来 $M$ 行，一行两个整数 $x_j,y_j$。

outputFormat: 共 $K$ 行，一行一个整数，第 $i$ 行表示第 $i$ 便宜的方案所需的价钱。

hint:
#### 样例解释
共有 $5$ 个商品，$2$ 种类型。

类型 $1$：$\{3,5,6\}$，类型 $2$：$\{1,3\}$。

类型 $1$ 与类型 $2$ 均只能选择一个商品。

对于最便宜的方案，选择 $\{1,3\}$ 即可。

以此类推。

#### 子任务
**本题使用捆绑测试**

- Subtask 1（$20$ 分）：$x_j,y_j=1$，$N,M,K\le4\times 10^3$。
- Subtask 2（$20$ 分）：$x_j,y_j=1$，$N,M,c_i\le 4\times 10^3$。
- Subtask 3（$20$ 分）：$x_j,y_j=1$。
- Subtask 4（$20$ 分）：$x_j=0$。
- Subtask 5（$20$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $1\le N,M,K\le 2\times 10^5$，$1\le a_i\le M$，$1\le c_i\le 10^9$，$0\le x_j\le y_j\le N$。

#### 说明
本题译自 [Canadian Computing Olympiad 2020](https://cemc.math.uwaterloo.ca/contests/computing/2020/) [Day 2](https://cemc.math.uwaterloo.ca/contests/computing/2020/cco/day2.pdf) T3 Shopping Plans。

本题数据有所删减。


title: 「PMOI-5」肥宅快乐水

background:
lhm 喝肥宅快乐水的时候想到了这个 idea，于是就叫它肥宅快乐水。

~~此题为弱化版，强化版敬请期待 Ynoi。~~

特别感谢：验题人 双管荧光灯 吊打了此题的 std！

description:
lhm 的手中有 $n$ 个宽度为 $1$ 的矩形水平排列组成的多边形，其中第 $i$ 个矩形的高度为 $a_i$。现在他会进行 $k$ 次操作，每次使一个宽度为 $1$ 的矩形高度减 $1$，求他每次操作后的最大子矩形面积（显然，子矩形必须是连续的一块）。

**注意任何情况高度都大于等于 $0$。**

由于 lhm 太菜了，所以想要请聪明的你来帮他解决。

inputFormat:
输入数据共 $k+2$ 行。
第一行两个整数 $n,k$，含义如题所示。
第二行 $n$ 个整数 $a_i$，第 $i$ 个整数表示第 $i$ 个矩形的高度。
接下来 $k$ 行，每行一个整数 $\operatorname{id}'$，操作编号 $\operatorname{id}=\operatorname{id}'\bigoplus \operatorname{lastans}$。其中 $\operatorname{lastans}$ 为上一次询问的答案，最开始 $\operatorname{lastans}=0$。

outputFormat:
输出数据共 $k$ 行。
每行一个整数，表示每次询问所求答案。


title: 边三连通分量

background:
对于一张无向图 $G = (V, E)$。

- 我们称两个点 $u, v ~ (u, v \in V, u \neq v)$ 是边三连通的，当且仅当存在三条从 $u$ 出发到达 $v$ 的，相互没有公共边的路径。
- 我们称一个点集 $U ~ (U \subseteq V)$ 是边三连通分量，当且仅当对于任意两个点 $u', v' ~ (u', v' \in U, u' \neq v')$ 都是边三连通的。
- 我们称一个边三连通分量 $S$ 是极大边三连通分量，当且仅当不存在 $u \not \in S$ 且 $u \in V$，使得 $S \cup \{u\}$ 也是边三连通分量。

description: 给出一个 $n$ 个点，$m$ 条边的无向图 $G = (V, E)$，$V = \{1, 2, \ldots, n\}$，请求出其所有的极大边三连通分量。

inputFormat:
第一行输入两个整数 $n, m$，表示点数、边数。

接下来 $m$ 行，每行输入两个数 $u, v$，表示图上的一条边。

outputFormat:
第一行输出一个整数 $s$，表示极大边三连通分量个数。

接下来输出 $s$ 行，每行若干整数，表示一个极大边三连通分量内所有点。

对于单个极大边三连通分量，请将点按照标号升序输出。对于所有极大边三连通分量，请按照点集内编号最小的点升序输出。

hint:
#### 样例 1 解释

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

如图，$1 \to 3$ 共有 $(1, 2, 3)$，$(1, 3)$，$(1, 4, 3)$ 三条路径，它们互相都没有相交的边。因此 $1$ 与 $3$ 在同一个边三连通分量中。

由于 $2$，$4$ 点度都只有 $2$，不可能有三条边不相交的到其它点的路径，因此它们自己形成边三联通分量。

---

#### 数据范围

- 对于 $30\%$ 的数据，$n \le 100$，$m \le 200$。
- 对于 $50\%$ 的数据，$n \le 1000$，$m \le 2000$。
- 对于 $80\%$ 的数据，$n \le 10 ^ 5$，$m \le 2 \times 10 ^ 5$。
- 对于 $100\%$ 的数据，$1 \le n, m \le 5 \times 10 ^ 5$，$1 \le u, v \le n$。可能有重边和自环。

---

#### 来源

题目搬运自 [Three-Edge-Connected Components](https://judge.yosupo.jp/problem/three_edge_connected_components)。


title: [清华集训2016] 定向越野

description:
定向越野是一项集智力与体力为一体的体育运动，在这项活动中，选手需要从起点出发，在尽可能短的时间内到达指定的地点。

牛牛非常喜爱这项运动，但是他不知道怎么样才能更快到达终点。他听说来参加集训的你智力过人，于是他把定向越野的地图交给了你，希望你帮他解决一些问题。

牛牛给你的地图描述的是一块平地，地图上不仅清楚地标出了起点和终点的坐标，还标有若干个互不相交圆形区域，每个区域表示一个圆形的水域。对于不会游泳的牛牛来说，进入水域是根本不可能的。因此，牛牛的行动路线不能从水域中穿过。牛牛想知道这样的路线长度最小可以是多少。

inputFormat:
第一行包含四个实数 $S_x,S_y,T_x,T_y$ ，分别表示起点的坐标和终点的坐标。

第二行包含一个整数 $n$，表示水域的个数。

接下来 $n$ 行，每行 $3$ 个整数 $x_i,y_i,r_i$ 表示一片水域的圆心的坐标和半径。

保证起点和终点都不在水域的内部或边界上，起点和终点不重合。

outputFormat:
输出一行，包含一个实数，四舍五入精确到小数点后恰好 $1$ 位，表示答案。你的输出必须和标准输出完全一样才算正确。

测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于 $4×10^{−2}$。

（如果你不知道什么是浮点误差，这段话可以理解为：对于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊的处理）

hint:
#### 样例解释

这个地图如下图，其中画出的路径即是所求的最短路径。

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

#### 数据范围

所有数据满足 $0≤n≤500$，$−1000≤x_i,y_i,r_i,S_x,S_y,T_x,T_y≤1000$。


title: [清华集训2016] 你的生命已如风中残烛

description:
期中考试考完了，已经感到没有什么好害怕的六花今天决定不学数学了，于是和勇太打起了游戏王。

“你已空手空场，生命只剩一百，事到如今你还能做什么？”

“所累哇多卡纳！”

“纳尼？”

然而六花的卡组实在是太菜了，经过分析，六花发现在一回合内，她卡组中的牌并没有办法达成 OTK，除非主角光环附体：

**被封印的艾克佐迪亚**

**——包括这张卡在内，「被封印者的右足」「被封印者的左足」「被封印者的右腕」「被封印者的左腕」全在手牌的时候，获得决斗胜利。**

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

但是因为六花不是高贵的氪金玩家，她可以肯定，这五张牌中肯定有一张，在牌堆的底端。所以六花现在面临着一个难题：需要在一回合内将卡组抽完。

六花的牌堆一共有 $m+1$ 张牌，因为最后一张牌是固定的，所以我们现在只考虑前 $m$ 张牌。

在这 $m$ 张牌中，有 $n$ 张特殊牌和 $m-n$ 张普通牌，每一个特殊牌有一个属性值 $w_i$，表示在打出这张牌后，可以再摸 $w_i$ 张牌。幸运的是，六花发现这些牌刚好满足 $∑\limits_{i=1}^nw_i=m$，因此她可以放心的随意摸牌而不用担心爆牌。

因为这 $m$ 张牌是被打乱的，所以总共有 $m!$ 种不同的可能的牌堆。

现在这回合开始了，六花先从牌堆里抽出一张牌，接着六花不断的打出手中的牌，如果打出特殊牌，则又可以摸牌，直到摸到最后一张牌达成胜利条件或者打光自己的手牌结束自己的回合继而输掉比赛。

举例来说，如果牌堆是 $\{4,0,0,2,0,0,0\}$（用 $0$ 表示普通牌，其他数字表示 wi，其中最后一个 $0$ 是最后一个部件），那么六花打牌的过程可以为：

- 取一张牌，手中的牌为 $\{4\}$。
- 打出 $\{4\}$，再取四张牌，手中的牌为 $\{0,0,2,0\}$。
- 打出 $\{2\}$，还需要再取两张，这时已摸到最后一个部件，六花胜利。
- 而如果牌堆是 $\{2,0,0,4,0,0,0\}$，不难发现是勇太的胜利。

现在，六花想要知道这 $m!$ 种不同的牌堆中，有多少种能够让她胜利。

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

第二行 $n$ 个空格隔开的正整数 $w_i$。

通过输入你可以自己算出来 $m=∑w_i$。

outputFormat: 输出一个整数表示答案，答案可能很大，你只需要输出对 $998\,244\,353$ 取模后的结果。

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

所有可能的 $m!$ 种牌堆中，只有形如 $\{5,0,0,0,0,0\}$ 的 $24$ 个牌堆满足条件。

#### 数据范围

对于 $10\%$ 的数据，$m \leq 10$。

对于 $30\%$ 的数据，$n \leq 8$。

对于 $50\%$ 的数据，$n \leq 15$。

对于 $70\%$ 的数据，$n \leq 30$。

对于 $100\%$ 的数据，$n \leq 40$，$1 \leq w_i \leq 10^5$。同时保证有 $m-n \geq 4$，因为牌堆里毕竟要有这 $5$ 个部件嘛。


title: [清华集训2016] 石家庄的工人阶级队伍比较坚强

background:
B 君和 G 君在过街天桥上。

B 君：「又到冬天啦，算起来到大学已经三年多了」

G 君：「是呀」

B 君：「街上的情侣又多起来了，想想三年之前，我也是这样……」

G 君：「？？」

B 君：「……在天桥上看情侣的！」

G 君：「唔。」

B 君：「不过这次有你陪我了呢~」

G 君：「……」

B 君：「诶诶，我有个问题想问你~」

G 君：「问吧」

B 君：「假设 $n=3^m$ 个人一起玩 cei ding ke」

G 君：「啊咧？cei ding ke 是什么？」

B 君：「就是石头剪刀布~，我们也叫钉钢锤」

G 君：「你就问这个？」

B 君：「你等会，我还没说完呢」

description:
$n=3^m$ 个人在玩石头剪刀布， 一共有 $t$ 轮游戏，每轮有 $m$ 次石头剪刀布。

在同一轮的 $m$ 次游戏中，每个人的决策必须是提前确定的，也就是说不能采用随机策略，也不能根据前若干局的结果决定下一局的决策； 这样，显然一共有 $n=3^m$ 种决策。

这 $n=3^m$ 个人会采取两两不同的决策。 为了方便表达，对于第 $x$（$0≤x<n$）个人，将 $x$ 转换成三进制得到一个 $m$ 位的数。 其中 $0$ 表示剪刀，$1$ 表示石头，$2$ 表示布。就得到了第 $x$ 个人采取的策略。

由于编号是固定的，因此每个人在不同轮的 $m$ 次游戏中都会采取同一套决策。

第 $x$ 个人在最初时有一个分数 $f_{0,x}$。

在第 $i$ 轮中，他将和另一个人 $y$ 进行 $m$ 次的石头剪刀布的比赛。

我们用 $W(x,y)$ 表示 $x$ 在和 $y$ 的 $m$ 次比赛中赢的次数； 用 $L(x,y)$ 表示 $x$ 在和 $y$ 的 $m$ 次比赛中输的次数。

在第 $i$ 轮结束之后，第 $x$ 个人分数是：

$$f_{i,x}=∑_{0≤y<n}f_{i−1,y}b_{u,v}$$

其中 $u=W(x,y)=L(y,x),v=L(x,y)=W(y,x)$，平局不计入次数；$b_{u,v}$ 则是一个给定的评分数组。

注意即使 $y$ 和 $x$ 一样（自己转移到自己）也会乘上一个系数 $b_{0,0}$（即自己跟自己打全为平局）。

显然随着轮数越来越多，分数也会越来越大， 这个计分系统和我们平时用的计算机一样，也会溢出。 当要储存的分数 $f$ 大于等于 $p$ 的时候，就会变成 $f\bmod p$。

B 君想知道 $t$ 轮之后所有人的分数，也就是 $f_{t,0},f_{t,1},…,f_{t,n−1}$。

G 君：「诶，我发现这个数 $p$ 有特殊的性质诶！不存在两个正整数，使得他们倒数的和等于 $3/p$！」

B 君：「G 君好棒！不过这个题怎么做呢？」

inputFormat:
第一行三个整数，表示 $m,t,p$。

第二行有 $n=3^m$ 个整数，表示 $f_{0,0},f_{0,1},…,f_{0,n−1}$。保证 $0≤f_{0,i}<p$。

接下来的部分是一个数组 $b$，第 $1$ 行 $m+1$ 个数，第 $2$ 行 $m$ 个数……第 $m+1$ 行 $1$ 个数。

其中第 $i$ 行的第 $j$ 个数为 $b_{i−1,j−1}$（$i,j≥1,i+j−2≤m$），保证 $0≤b_{i,j}<p$。

不存在两个正整数，使得他们倒数的和等于 $3/p$。 即不存在正整数 $x,y>0$，使得 $1/x+1/y=3/p$。

outputFormat:
输出 $n=3^m$ 行，每行一个整数，表示每个人最终的得分。

其中第 $i$ 行表示第 $i$ 个人的得分 $f_{t,i}$。


title: [省选联考 2020 A/B 卷] 冰火战士

background:
A 卷 D1T1，B 卷 D1T3。

时限 3s，内存 512MB。

description:
一场比赛即将开始。

每位战士有两个属性：温度和能量，有两派战士：冰系战士的技能会对周围造成降温冰冻伤害，因而要求场地温度不低于他的自身温度才能参赛；火系战士的技能会对周围造成升温灼烧伤害，因而要求场地温度不高于他的自身温度才能参赛。

当场地温度确定时，双方能够参赛的战士分别排成一队。冰系战士按自身温度从低到高排序，火系战士按自身温度从高到低排序，温度相同时能量大的战士排在前面。首先，双方的第一位战士之间展开战斗，两位战士消耗相同的能量，能量少的战士将耗尽能量退出比赛，而能量有剩余的战士将继续和对方的下一位战士战斗（能量都耗尽则双方下一位战士之间展开战斗）。如此循环，直至某方战士队列为空，比赛结束。

你需要寻找最佳场地温度：使冰火双方消耗总能量最高的温度的最高值。

现在，比赛还处于报名阶段，目前还没有任何战士报名，接下来你将不断地收到报名信息和撤回信息。其中，报名信息包含报名战士的派系和两个属性，撤回信息包含要撤回的报名信息的序号。每当报名情况发生变化（即收到一条信息）时，你需要立即报出当前局面下的最佳场地温度，以及该场地温度下双方消耗的总能量之和是多少。若当前局面下无论何种温度都无法开展比赛（某一方没有战士能参赛），则只要输出 `Peace`。

inputFormat:
第一行一个数 $Q$，表示信息的数量。

接下来 $Q$ 行，每行为 `1 t x y` $(t \in \{0, 1\}$，$x$ 和 $y$ 都是正整数 $)$ 或 `2 k`（$k$ 是正整数）：

`1 t x y` 表示一条报名信息，$t = 0$ 时报名战士是冰系，$t = 1$ 时报名战士是火系，$x$ 表示战士的自身温度，$y$ 表示战士的能量。

`2 k` 表示一条撤回信息，撤回的是第 $k$ 条信息。被撤回的信息一定是报名信息，已被撤回的信息不会再次被撤回。

outputFormat: 共 $Q$ 行，每行有两个用空格隔开的正整数，分别表示当前局面下的最佳温度和该温度下冰火双方消耗的总能量之和。

hint:
#### 样例 1 解释
为说明方便，约定：若第 $k$ 条信息是报名信息，则该条报名信息对应战士 $k$。样例中含有战士 $1,2,3,4,6,7,8$，由于第 $5$ 条是撤回信息，所以没有战士 $5$。

下面逐个解释每个输出：

1. 只有火系战士：战士 $1$，无法比赛，输出 `Peace`。
2. 温度为 $100 \sim 103$ 都能消耗最多的能量 $200$：战士 $1$ 对阵战士 $2$ 消耗能量 $200$，最佳温度为 $103$。
3. 温度为 $100 \sim 103$ 都能消耗最多的能量 $200$：战士 $1$ 对阵战士 $2$ 消耗能量 $200$，最佳温度为 $103$。
4. 温度 $103$ 能消耗最多的能量 $300$：首先，战士 $1$ 对阵战士 $2$ 消耗能量 $200$；然后，战士 $1$ 对阵战士 $4$ 消耗能量 $100$，最佳温度为 $103$。
5. 从现在起战士 $1$ 不再存在。温度 $100 \sim 102$ 能消耗最多的能量 $200$：战士 $2$ 对阵战士 $3$ 消耗能量 $200$，最佳温度为 $102$。

#### 样例 2

见附加文件中 `icefire2.in` 与 `icefire2.ans`。

#### 数据范围

$10\%$ 的数据：$Q \leq 100$，$x \leq 10^3$。

另有 $20\%$ 的数据：$Q \leq 10^4$，$x \leq 5000$，不存在撤回信息，且输入的 $x$ 按顺序不降。

$60\%$ 的数据（包含上述 $20\%$，下同）：$Q \leq 2 \times 10^5$，$x \leq 2 \times 10^5$。

$90\%$ 的数据：$Q \leq 2 \times 10^6$，$x \leq 2 \times 10^6$。

$100\%$ 的数据：$1 \leq Q \leq 2 \times 10^6$，$1 \leq x \leq 2 \times 10^9$，所有 $y$ 之和不超过 $2 \times 10^9$，保证不存在 $t, x, y$ 完全相同的两个战士。


title: [省选联考 2020 A 卷] 组合数问题

background: 1s 512M

description:
众所周知，小葱同学擅长计算，尤其擅长计算组合数。小葱现在希望你计算
$$\left(\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\right)\bmod p$$
的值。其中 $n$, $x$, $p$ 为给定的整数，$f(k)$ 为给定的一个 $m$ 次多项式 $f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m$。$\binom{n}{k}$ 为组合数，其值为 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$。

inputFormat:
第一行四个非负整数 $n$, $x$, $p$, $m$。

第二行 $m + 1$ 个整数，分别代表 $a_0$, $a_1$, $\cdots$, $a_m$。

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


title: [省选联考 2020 A 卷] 魔法商店

background: 1s 512M

description:
笠笠和伦伦来到了一家魔法商店，这家商店内有 $n$ 件礼品，礼品从 $1 \sim n$ 编号，$i$ 号礼品的魅力值为 $c_i$，价格为 $v_i$。

两人希望购买一些礼品，但他们的要求比较奇怪：假设购买到的礼品集合为 $S=\{s_1,s_2,\dots,s_p\}(1\leq s_i\leq n)$，两人要求对于 $S$ 中任意的非空子集 $T=\{t_1,t_2,\dots,t_q\}$，它包含的所有礼品的魅力值异或和都不为零，即：$c_{t_1} \oplus c_{t_2} \oplus \cdots \oplus c_{t_q} \neq 0$。其中 $\oplus$ 是异或运算。在此基础上，两人还要求购买到的礼品数尽可能多。

例如：$c_1=1,c_2=2,c_3=5,c_4=6,c_5=7$。则 $S_1=\{2,3,5\}$ 不符合要求，因为 $c_2 \oplus c_3 \oplus c_5=0$。$S_2=\{1,2,3\}$ 与 $S_3=\{2,4,5\}$ 符合要求，其任意非空子集的异或和都不为零。$S_4=\{1,2\}$ 因为其包含的礼品数不是最多的。

满足两人要求的礼品集合可能很多，因此商店老板为两人挑选出了两个符合要求的礼品集合 $A$ 与 $B$（显然它们所含的礼品数相同），伦伦喜欢集合 $A$，但笠笠更喜欢集合 $B$。为了笠笠同意购买集合 $A$，伦伦决定使用魔法改变礼品价格。更具体地，伦伦能花费 $(x-v_i)^2$ 的魔力值，将 $i$ 号礼品的价格改为任意整数 $x$，每件礼品只能被改价一次。

伦伦希望改价后 $A$ 是所有符合要求的礼品集合之中价格总和最小的，且 $B$ 是所有符合要求的礼品集合之中价格总和最大的（一个礼品集合的价格总和为它包含的所有礼品的价格之和）。现在请你帮伦伦计算，他至少要花费多少魔力值才能完成他的目标。

inputFormat:
第一行两个整数 $n, m$，分别表示总礼品数与礼品集合 $A(B)$ 包含的礼品数。

第二行 $n$ 个整数 $c_i$，第 $i$ 个整数表示 $i$ 号礼品的魅力值。

第三行 $n$ 个整数 $v_i$，第 $i$ 个整数表示 $i$ 号礼品的价格。

第四行 $m$ 个整数 $a_i$，表示礼品集合 $A$ 包含的礼品的编号。数据保证 $a_i$ 两两不同。

第五行 $m$ 个整数 $b_i$，表示礼品集合 $B$ 包含的礼品的编号。数据保证 $b_i$ 两两不同。

数据保证 $1 \leq a_i, b_i \leq n$，且礼品集合 $A$ 和 $B$ 均符合两人的要求。

outputFormat: 仅一行一个整数，表示伦伦至少需要花费的魔力值。