title: [COCI2015-2016#3] ESEJ

description:
小 M 要写一篇文章。

- 这篇文章至少 $a$ 个词，最多 $b$ 个词，
- 每个单词至少 $1$ 个字母，最多 $15$ 个字母。
- 文章至少包含 $\dfrac{b}{2}$ 个不同的单词。

小 M 昨晚熬夜打 Codeforces，所以请你帮他写作文。

作文只能有一段（只有一行），只能使用英文字母的小写字母和空格。

**注：作文的句意可以不通顺，语法也可以不正确，只要符合要求的作文，均可以 $\color{green}\texttt{AC}$。**

inputFormat: 第一行两个正整数 $a, b$。

outputFormat: 一行，一篇作文。

samples:
2 7
this shakespeare fella is good

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

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

#### 说明
- 样例 #2 和样例 #3 由于输出过长放置在了这里：[样例 #2 与样例 #3](https://www.luogu.com.cn/paste/we9k25k1)。
- 翻译自 [COCI 2015-2016 #3 B ESEJ](https://hsin.hr/coci/archive/2015_2016/contest3_tasks.pdf)，满分 80。
- 感谢 @[tiger2005](https://www.luogu.com.cn/user/60864) 提供的 checker.cpp。


title: [COCI2015-2016#3] SLON

type: P

description:
小 Q 在学校里非常调皮。

他上课时总是很无聊，他总是把课堂弄得一团糟。老师希望让他冷静下来，所以给他出了一道很难的数学题。

老师给小 Q 一个算术表达式 $A$、整数 $P$ 和 $M$，小 Q 要回答的是以下问题：

> 求最小非负整数  $x$，使含  $x$ 的表达式  $A$ 除以  $M$ 余数等于  $P$。

注意每一个运算符均会连接两个数或是变量。每一个乘号都不会省略且不允许连接两个含有 $x$ 的表达式。括号均合法，可能存在括号内容仅有一个数或变量的情况。

题目保证原表达式化简后一定能写成一个形如 $kx+b$ 的一元一次式。

inputFormat:
第一行，一行表达式 $A$。

第二行，两个正整数 $P, M$。

outputFormat: 第一行，一个正整数 $x$。

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

对于 $100\%$ 的数据：
- 令 $|A|$ 为字符串 $A$ 的长度，那么 $1 \le |A| \le 10 ^ 5$。
- 表达式 $A$ 中仅会有 $\texttt{+}$，$\texttt{-}$，$\texttt{*}$，$\texttt{(}$，$\texttt{)}$，$\texttt{x}$，和 $\texttt{0}$ $\sim$ $\texttt{9}$。
- $0 \le P \le M - 1$。
- $1 \le M \le 10 ^ 6$。

#### 说明
翻译自 [COCI 2015-2016 #3 D SLON](https://hsin.hr/coci/archive/2015_2016/contest3_tasks.pdf)，满分 120。


title: [COCI2015-2016#3] NEKAMELEONI

background:
> 「嘿，亲爱的！我要去给 $11$ 月 $28$ 日的 Croatian Open Competition In Informatics 出 T5。」
> 「去吧，去吧……」
> 「…」
> _____
> 「这题怎么样？」
> 「唔……这太难了……会把那些小可爱难住的，换个简单些的吧……」
> 于是可爱的出题人便出了这道题。
> ______
> 嘿！我会 $O(n^6)$ 的做法，$ n$ 的范围是什么？？

description:
给你一个 $n$ 个元素的数组。你需要处理 $q$ 个查询。

- 第一种查询需要你将数组中的第 $p$ 个数字改为 $v$。
- 第二种查询需要你确定当前数组中最短的连续子数组的长度，这个子数组必须要包含从 $1$ 到 $k$ 的所有数字。

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

第二行，$n$ 个正整数，用空格隔开，表示数组中的数。

接着，$m$ 行，表示 $m$ 个查询，每个查询有以下两种形式。
- $\texttt{1 p v}$：将数组中的第 $p$ 个数字改为 $v$。
- $\texttt{2}$：确定并输出当前数组中最短的连续子数组的长度，这个子数组必须要包含从 $1$ 到 $k$ 的所有数字。

outputFormat:
仅查询 $2$ 有输出。

对于每个查询 $2$，输出当前数组中最短的连续子数组的长度（这个子数组必须要包含从 $1$ 到 $k$ 的所有数字），若没有输出 $\texttt{-1}$。

hint:
#### 数据范围及约定
- 对于 $30\%$ 的数据，$1\le n, m \le 5 \times 10 ^ 3$。
- 对于 $100\%$ 的数据，$1 \le n, m \le 10^5$，$1\le k \le 50$，$1 \le p \le n$，$1\le v \le k$。

#### 说明
翻译自 [COCI 2015-2016 #3 E NEKAMELEONI](https://hsin.hr/coci/archive/2015_2016/contest3_tasks.pdf)，满分 140。


title: [COCI2015-2016#3] DOMINO

background:
「誕生日おめでとう！!」

小 M 收到了他女朋友的生日祝福和一份礼物。

description:
小 M 的女朋友送小 M 了一张 $n \times n$ 的表格作为生日礼物，在表格的每个单元格中都写有一个非负整数。

不幸的是，有些单元格里数字太大了，小 M 不喜欢它们，所以他将在表格上面放置 $k$ 张骨牌，将覆盖那些数字太大的单元格。

更准确地说，小 M 按照以下规则放置骨牌。

- 骨牌为 $1\times 2$ 的矩形，不能拆开放置。
- 骨牌不重叠（但可以接触）。
- 所有可见（未覆盖）字段的总和需要尽可能的小。

您的任务是确定最小可见区域的数字的总和。数据保证可防止 $k$ 个骨牌且无重叠。

inputFormat:
第一行，$2$ 个正整数 $n,k$，$n$ 表示表格的尺寸， $k$ 表示骨牌的数量。

接下来 $n$ 行，每一行都有 $n$ 个整数 $a_i$。这些 $n \times n$ 的数字的数字描述了 Mirko 的表格。

outputFormat: 一行一个整数，最小可见区域的数字的总和。

hint:
#### 数据规模及约定
对于 $100\%$ 的数据，$1\le n \le 2 \times 10 ^ 3$，$1\le k \le 8$，$0 \le a_i \le 10 ^ 3$。

#### 说明
翻译自 [COCI 2015-2016 #3 F DOMINO](https://hsin.hr/coci/archive/2015_2016/contest3_tasks.pdf)，满分 160。


title: 「MCOI-04」Dream SMP

background:
**本题为提交答案题。**

链接：https://pan.baidu.com/s/1D3ytb0626EKZ_emw3gLwVQ
提取码：inbj

description:
Dream SMP 可以看做 $n$ 个编号为 $0,1,\dots,n-1$ 的地区。
Dream 希望将这 $n$ 个地区划分为 $8$ 个编号为 $0,1,\dots,7$ 的国家。每一个地区都所在恰好一个国家，但国家可以不包含任何地区。
地区提出 $m$ 组对划分方案的条件，其中第 $i$ 组条件用四个参数 $(u_i,a_i,v_i,b_i)$ 表示。某个划分方案合法当且仅当对所有条件，$u_i$ 号地区不属于 $a_i$ 号国家 **或者** $v_i$ 号地区不属于 $b_i$ 号国家。这里 **或者** 是逻辑或。
Dream 保证存在至少一个合法划分方案，请你构造一个合法划分方案。

inputFormat:
第一行两个正整数 $n$ 和 $m$。
接下来 $m$ 行，每行四个正整数 $u_i,a_i,v_i,b_i$。

outputFormat:
输出一个长度为 $n$ 的字符串。
字符串的第 $i$ 位为 $i$ 号地区所属的国家。

hint:
#### 样例 1 解释

23322，23332，23333 均是合法方案。

#### 数据规模与约定

对于 $100\%$ 的数据，$1 \le n\le10^5$，$1 \le m\le10^6$。
具体特性请自行参考输入数据。

[点击下载输入数据。](https://gitee.com/w33z8kqrqk8zzzx33/dream-oi-extra/raw/master/down.zip)

如果上面这个下载不了看下面这个：

链接：https://pan.baidu.com/s/1D3ytb0626EKZ_emw3gLwVQ
提取码：inbj

#### 说明

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


title: Something Comforting

background:
![Something Comforting](https://mivik.gitee.io/image/nurture/something_comforting.png)

> Cause getting made you want more
>
> And hoping made you hurt more
>
> Someone tell me
>
> Something comforting

description:
Porter Robinson 花了五年的时间制作了 Something Comforting 这首歌，Mivik 花了五天时间造出了一道和括号序列相关的题。但 Mivik 并不开心，因为他发现他不会造数据了！

Mivik 需要随机生成一个 **合法** 的括号序列，于是 Mivik 想了一会，写出了下面的算法：

```cpp
#include <algorithm>
#include <string>

std::string generate(int n) { // 生成一个长度为 n * 2 的括号序列
	const int len = n * 2;
	bool arr[len]; // 0 代表左括号，1 代表右括号
	for (int i = 0; i < n; ++i) arr[i] = 0;
	for (int i = n; i < len; ++i) arr[i] = 1;
	std::random_shuffle(arr, arr + len); // 随机打乱这个数组
	for (int i = 0, j, sum = 0; i < len; ) {
		sum += arr[i]? -1: 1;
		if (sum < 0) { // 出现了不合法的位置
			for (j = i + 1; j < len; ++j) {
				sum += arr[j]? -1: 1;
				if (sum == 0) break;
			}
			// 现在 i 是第一个不合法的位置，j 是 i 后面第一个合法的位置
			// ( ( ) ) ) ) ( ( ( ) ( )
			//         i     j
			for (int k = i; k <= j; ++k)
				arr[k] ^= 1; // 把这段区间全部反转
			i = j + 1;
		} else ++i;
	}
	std::string ret;
	for (int i = 0; i < len; ++i)
		ret += arr[i]? ')': '(';
	return ret;
}
```

P.S. 为了给其它语言用户带来做题体验，[这里](https://www.luogu.com.cn/paste/wof8zjn8) 提供了多种语言对该算法的描述。

Mivik 十分开心，因为这个算法总能生成合法的括号序列。但不一会儿他就发现这个算法生成的括号序列并不均匀，也就是说，当 $n$ 固定时，所有合法的括号序列出现的概率并不均等。例如，Mivik 发现当 $n=3$ 时，`()()()` 被生成的概率要远大于 `((()))`。

现在 Mivik 给了你一个 $n$ 和一个长度为 $2n$ 的 **合法** 括号序列，假设 `std::random_shuffle` （对于其它语言来说，`shuffle`）能够均匀随机地打乱一个数组，他想问问你这个括号序列通过上文的算法被生成的概率是多少。由于 Mivik 不喜欢小数，你需要输出这个概率对 $998244353$ 取模的结果。如果你不知道如何将一个有理数对质数取模，可以参考 [有理数取模](https://www.luogu.com.cn/problem/P2613)。

inputFormat:
第一行一个整数 $n$，意义同题面。

接下来输入一个长度为 $2n$ 的合法括号序列，意义同题面。

outputFormat: 输出一行一个整数，代表这个概率对 $998244353$ 取模的结果。

hint:
### 样例解释

样例一：$n$ 为 1 时，无论怎样都只可能会生成 `()` 这一种合法的括号序列，因此概率为 1。

### 数据范围

对于全部数据，有 $1\le n\le 5\cdot 10^5$，且输入的括号序列合法。

Subtask 1（20 pts）：保证 $1\le n\le 5$。

Subtask 2（30 pts）：保证 $1\le n\le 1000$。

Subtask 3（50 pts）：无特殊限制。


title: [COCI2019-2020#4] Holding

background:
Ivica 有一个由 $N$ 家克罗地亚公司组成的集团，但他的集团正面临着困难。他的企业承受着觉的负债，所以政府派遣律师没收了他的一切财产。

但我们发现，尽管他有巨额债务在身，他依然与政府达成协议，留住了部分企业。他留住的是哪些？我们也知道了。

description:
律师们把 Ivica 的公司的 $N$ 份债务文件摆在桌上。第一家公司的债务为 $A_1$ ，第二家公司的债务为 $A_2$ ，依次类推。

Ivica 与政府达成协议，使它留下桌上 $[L,R]$ 区间的所有文件所对应的公司，但他需要承担 $A_L,A_{L+1}\ldots A_R$ 的所有债务，其中 $L$ 和 $R$ 代表桌子上一系列文件中的位置。

幸运的是，律师们也是腐败。他们可以让他以 $|i-j|$ 的价格交换当前放在位置 $i$ 和位置 $j$ 的文件。

Ivica 有点绝望。他口袋里只有 $K$ 元钱，他现在想把这些钱花在这里，使得他的需要承担的债务尽可能少。

请帮他达成目标。

inputFormat:
第一行四个整数 $N,L,R,K$。

第二行 $N$ 个整数，第 $i$ 个表示 $A_i$。

outputFormat: 一行一个整数，表示花不超过 $K$ 元后负债的最小值。


title: [COCI2019-2020#4] Klasika

description:
开始时，你有一个编号为 $1$ 的节点，它代表着一棵树的根。你的任务对树进行 $Q$ 次操作。

操作分为两类：

- $\texttt{Add x y}$，给树上编号为 $x$ 的节点加入一个儿子，该儿子的编号为加入该节点后树的大小，它与 $x$ 的边的边权为 $y$。
- $\texttt{Query a b}$，查找从 $a$ 出发，到 $b$ 节点子树内某个节点（包括 $B$ ）的路径中边权异或和最大的一条，并输出其异或和。

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

加下来 $Q$ 行，每行一个字符串和两个数字，描述一次操作。

outputFormat: 对于每个 $\texttt{Query}$ 操作，一行一个整数表示答案。

samples:
6
Add 1 5
Add 2 7
Add 1 4
Add 4 3
Query 1 1
Query 2 4

samples:
10
Add 1 4
Add 1 9
Add 1 10
Add 2 2
Add 3 3
Add 4 4
Query 4 2
Query 1 3
Add 6 7
Query 1 3


title: [COCI2015-2016#3] MOLEKULE

description:
有 $N$ 个点和 $N-1$ 条无向边，定义一张有向图的代价为一条在这张有向图上的最长通路长度。

现在把这 $N-1$ 条无向边指定方向，使得形成的有向图代价最小。

求一种指定方向的方案。

inputFormat:
第一行一个整数 $N$ 代表点数。
接下来 $N-1$ 行每行两个整数 $a_i,b_i$ 代表一条边。

outputFormat:
$N-1$ 行每行一个整数 $r$：

- 如果 $r=1$ 代表从 $a_i$ 连向 $b_i$。
- 如果 $r=0$ 代表从 $b_i$ 连向 $a_i$。

hint:
#### 样例 1 解释

如下图所示：

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

这张图的代价为 $1$，注意 $0\ 1$ 也是一组最优解。

#### 样例 2 解释

如下图所示：

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

#### 数据规模与约定

对于 $30\%$ 的数据，$N \le 20$。
对于 $100\%$ 的数据，$2 \le N \le 10^5$，$1 \le a_i,b_i\le N$。

**本题采用 Special Judge。**
你只需要输出任意一种合法方案。

#### 说明

翻译自 [COCI 2015-2016 #3 C MOLEKULE](https://hsin.hr/coci/archive/2015_2016/contest3_tasks.pdf)。


title: Get Your Wish

background:
![Get Your Wish](https://mivik.gitee.io/image/nurture/get_your_wish.png)

> So, tell me how it felt when you walked on water
>
> Did you get your wish?

description:
Porter 在浅水上完成了他的 MV，但他很快发现了事情不对：他的话筒进水了。

Porter 的话筒内部的关键电子元件可以被看作一个 $n\times m$ 的二维平面。我们用一张 $n\times m$ 的字符画来表示 Porter 的话筒内部状况，其中有三种不同的字符：

- `.`：表示空位

- `x`：表示关键电子原件

- `o`：表示水滴

水滴会沿着重力方向一直流动，直到流出边界或者流到电子原件上。当水滴流到任意一个电子原件上时，Porter 的话筒就会坏掉。Porter 慌忙把话筒转过来，改变了话筒内部的重力方向。重力方向用四种字符之一表示：`^v<>`，分别对应上下左右。

Porter 想知道，在这种重力方向下，他的话筒过一会儿会不会 GG。

inputFormat:
第一行两个正整数和一个字符，分别代表 $n$、$m$ 和重力方向。

接下来 $n$ 行，每行 $m$ 个字符，分别对应代表该点状态。

outputFormat: 输出一行一个字符串。`GG` 代表 Porter 的话筒会坏掉，`OK` 代表不会。

hint:
### 样例解释

样例一：第一行第二列的水滴向下流到了最后一行第二列的电子原件上，因此话筒坏掉了。

样例二：第二行第一列的水滴向右流到了第二行最后一列的电子原件上，因此话筒坏掉了。

样例三：第一行第二列的水滴直接向上流出话筒，因此 Porter 的话筒不会坏掉。

### 数据范围

对于全部数据，保证 $1\le n,m\le 100$，且输入数据合法。

Subtask 1 (10 pts)：话筒中没有 `x`（即电子原件）。

Subtask 2 (10 pts)：话筒中没有 `o`（即水滴）。

Subtask 3 (30 pts)：保证重力方向总是 `v`（向下）。

Subtask 4 (50 pts)：无特殊限制。


title: Mirror

background:
![Mirror](https://mivik.gitee.io/image/nurture/mirror.png)

> And it’s not the voice of all the others
>
> You’ve only said it to yourself
>
> I know what you want from me, from me
>
> I know what you’re thinking

description:
> Porter Robinson: We all have these avatars that we give to our critical inner voices - we might imagine a scornful parent telling us we’ll fail, or a critic telling us our work comes up short, or a society telling us that we aren’t good enough - it’s about recognizing that most of this criticism is self-inflicted.

Mivik 在镜中看见了自己的 Inner Voice ——不过是在一个镜子般对称的迷宫中。这个迷宫很特殊：它有无穷多行和无穷多列，行和列都从 $0$ 开始标号。一个格子 $(i,j)$ 能通过（没有障碍）当且仅当 $(i\&j)=0$，其中 $\&$ 指按位与运算（Bitwise And，[百度百科](https://baike.baidu.com/item/%E6%8C%89%E4%BD%8D%E4%B8%8E/9601818)）。下图给出了这个迷宫的 $0\sim63$ 行和 $0\sim 63$ 列的图像：

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

Mivik 想抓到并消灭那个给予自己负面声音的 Inner Voice，但他找不到路了。Mivik 和 Inner Voice 最初处在迷宫中的两点。Mivik 想知道，在 Mivik 的 Inner Voice 一直不移动的情况下，他至少需要走过多少个方格才能抓到他的 Inner Voice（Mivik 的起始格不算）。

但是... 游戏并不会像 Mivik 想象的一样简单。邪恶的 ggy 在这个迷宫中的某些格子布下了许多炸弹，Mivik 需要拆除它们才能踏上这些格子。Mivik 需要你告诉他，在他走过的方格数最少的情况下，他至少需要拆除哪些炸弹。

**请注意炸弹可能会重合，而你只有拆除一个格子上的所有炸弹才能通过这个格子。保障炸弹不与起点重合。**

inputFormat:
第一行一个整数 $n$，代表 ggy 设下的炸弹个数。

接下来 $n$ 行，**其中的**第 $i$ 行两个非负整数，代表 $i$ 号炸弹的坐标（从 1 开始编号）。

接下来一行两个非负整数 $sx$ 和 $sy$，代表 Mivik 位于哪一行哪一列。

接下来一行两个非负整数 $ex$ 和 $ey$，代表 Mivik 的 Inner Voice 位于哪一行哪一列。

outputFormat:
第一行一个整数，代表 Mivik 至少需要走少格才能抓到他的 Inner Voice。

接下来一行，给出一个长度为 $n$ 的 01 串，第 $i$ 个字符为 `1` 代表 Mivik 必须拆除第 $i$ 号炸弹，`0` 代表不需要。

hint:
### 样例解释

样例一：显然由于没有任何炸弹，Mivik 向右走两格就能抓到他的 Inner Voice。

样例二：Mivik 的最短路径如图所示：

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

其中，图片左上角为 $(0,0)$，蓝色代表 Mivik 的起始位置，绿色代表 Inner Voice 的位置，红色代表 Mivik 的最短路径，黄色代表炸弹，橙色（其实是黄色 + 红色）代表 Mivik 必须拆除的炸弹。

### 数据范围

对于全部数据，有 $1\le n\le 2\cdot 10^5$，$(sx,sy)\ne(ex,ey)$，并保证对于给出的任何坐标 $(x,y)$ 都有 $x\&y=0$ 且 $0\le x,y\le 10^{18}$。

Subtask 1 (10 pts)：保证 Mivik 可以直线（只向 上/下/左/右 走）抓到他的 Inner Voice。

Subtask 2 (15 pts)：保证 $sx=sy=0$。

Subtask 3 (20 pts)：保证 $0\le(\text{任意 x,y 坐标})\le 100$。

Subtask 4 (25 pts)：保证 $n=0$。

Subtask 5 (30 pts)：无特殊限制。


title: [JSOI2014] 支线剧情 2

description:
宅男 JYY 非常喜欢玩 RPG 游戏，并且 JYY 总是想花费最少的时间看完所有的支线剧情。最近JYY买了一款新的正版 RPG 游戏,所以 JYY 总算可以“读档”和“存档”了！

JYY 现在所玩的 RPG 游戏中，一共有 $n$ 个剧情点，由 $1$ 到 $n$ 编号，第 $i$ 个剧情点可以根据 JYY 的不同的选择，而经过不同的支线剧情，前往 $k_i$ 种不同的新的剧情点。当然如果 $k_i$ 为 $0$，则说明 $i$ 号剧情点是游戏的一个结局了。

JYY 观看一个支线剧情需要一定的时间。JYY—开始处在 $1$ 号剧情点，也就是游戏的开始。JYY 买的这款游戏很特殊，从游戏开始到达任何一个剧情点的支线路径都是唯一的。而且，任何一个剧情点都是从 $1$ 号剧情点可达的。

与上一款 RPG 游戏一样，JYY 可以在任意时刻选择重新开始游戏，即回到 $1$ 号剧情点。不过有些不同的是，这次 JYY 买的是正版软件，每当 JYY 到达一个剧情点，JYY 都可以进行“存档”和“读档”。但是很遗憾的是，JYY 的 RPG 游戏只有一个存档的位置：每次“存档”操作都会覆盖之前的存档。比如，如果 JYY 在 $x$ 号剧情点进行了“存档”操作，那么此后当 JYY 到达任何一个剧情点（包括结局）都可以“读档”并立即回到 $x$号剧情点。但是如果之后 JYY 在 $y$ 号剧情点又进行了“存档”，那么 JYY 再进行“读档”，就只能回到 $y$ 号剧情点了。

一开始存档位置里没有存储任何信息，所以 JYY 只有在进行一次“存档”操作之后才可以进行“读档”操作，并且“读档”，“存档”和“重新开始”都是不需要花费时间的。

重复观看己经看过的剧情是很痛苦的，JYY 希望花费最少的时间，看完所有不同的支线剧情。

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

接下来 $n$ 行，第 $i$ 行为第 $i$ 号剧情点的信息。

每一行第一个非负整数为 $k_i$。接下来 $k_i$ 个整数对，$b_{i,j}$ 和 $t_{i,j}$，表示从剧情点 $i$ 可以前往剧情点 $b_{i,j}$，并且观看这段支线剧情需要花费 $t_{i,j}$ 的时间。

outputFormat: 一行一个整数，表示 JYY 看完所有支线剧情所需要的最少时间。

hint:
### 样例解释 1

最佳路线为：

从 $1$ 前往 $5$，然后重新开始。

从 $1$ 前往 $2$，在 $2$ 处存档，再前往 $6$，并读档。

从 $2$ 前往 $3$，在 $3$ 处存档，再前往 $7$，并读档。

从 $3$ 前往 $4$，在 $4$ 处存档，再前往 $8$，并读档。

最后前往 $9$，花费时间为 $8$。可以证明没有比 $8$ 更小的答案。

### 数据范围

对于 $100\%$ 的数据，$n\leq 10^6,1\leq t_{i,j}\leq 10^4,\sum\limits_{i=1}^{n}k_i=n-1$。


title: [JSOI2014] 电信网络

description:
JYY 创建的电信公司，垄断着整个 JSOI 王国的电信网络。JYY在 JSOI 王国里建造了很多的通信基站。目前所有的基站都是使用 2G 网络系统的。而现在 3G 时代已经到来了，JYY 在思考，要不要把一些基站升级成 3G 网络的呢？

JSOI王国可以被看作为一个无穷大的二维平面，JYY 一共建造了 $n$ 个通信基站，第 $i$ 个基站的坐标是 $(x_i,y_i)$。每个基站有一个通信范围 $r_i$。第 $i$ 号基站会向所有到其距离不超过 $r_i$ 的基站发送信息。

每个基站升级到 3G 网络都会有一个收益 $s_i$，这个收益可能是正数（比如基站附近有个大城市，用户很多，赚的流量费也就很多了），也可能是负数（比如基站周围市场不佳，收益不能填补升级基站本身的投资）。此外，由于原有的使用 2G 网络系统的基站无法解析从升级成 3G 网络系统的基站所发来的信息（但是升级之后的基站是可以解析未升级基站发来的信息的），所以JYY必须使得在升级工作全部完成之后，所有使用3G网络的基站，其通信范围内的基站，也都是使用 3G 网络的。

由于基站数量很多，你可以帮助 JYY 计算一下，他通过升级基站，最多能获得的收益是多少吗？

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

接下来 $n$ 行，每行 $4$ 个整数 $x_i,y_i,r_i,s_i$，表示处在 $(x_i,y_i)$ 的基站的通信范围是 $r_i$，升级可以获得的收益是 $s_i$。

数据满足任意两个基站的坐标不同。

outputFormat: 一行一个整数，表示可以获得的最大收益。

hint:
### 样例解释 1

将前三座基站升级可以获得最大收益。

### 数据范围

$1\leq n\leq 500,1\leq r_i\leq 2\times 10^4,-10^4\leq x_i,y_i,s_i\leq 10^4$，保证所有基站坐标两两不同。


title: [JSOI2014] 歌剧表演

description:
文艺青年 JYY 非常喜欢观看歌剧表演。

JYY 知道所有演员的长相和名字，但是却对不上号，JYY 希望有一天能够知道每一个演员到底是谁。

JSOI 歌剧团一共有 $n$ 个演员，并进行了 $m$ 次演出。所有演员由 $1$ 到 $n$ 编号，并且第 $i$ 次演出共有 $k_i$ 位演员参加。

JYY看过所有 $n$ 个演员的照片(即知道这 $n$ 个演员的长相)，也看过演员的名单(即知道这 $n$ 个演员的姓名，假设没有同名的情况)，并且仔细观摩了所有的 $m$ 次演出：每次演出 JYY 都知道有哪些演员参加了本次表演并且能够分辨出他们的长相。

现在JYY想知道，看完这 $m$ 次演出之后，他是不是能够把所有演员的名字和长相都一一对应了呢？

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

接下来 $m$ 行，每行首先包含一个整数 $k_i$，接下来 $k_i$ 个不同的 $1$ 到 $n$ 之间的整数，表示参与此次演出的演员编号。

outputFormat:
一行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示编号为 $i$ 的演员在第 $a_i$ 场演出之后 JYY 就可以将他的编号和长相对应起来。

如果 $m$ 次演出之后 JYY 仍然不能认出这个演员，则 $a_i$ 为 $0$。

hint:
### 样例解释 1

每一场演出可以确定一个演员的长相，而 $4$ 号演员是唯一一直没有参加过演出的。
由于 JYY 一开始知道所有演员的长相，所以第三场演出后 JYY 也可以确认 $4$ 号演员的长相。

### 数据范围

$1\leq n,m\leq 10^5,\sum\limits_{i=1}^{n}k_i\leq 10^5$。


title: [JSOI2014] 打兔子

description:
勤劳的 JYY 在花园里面种了好多胡萝卜！可是，今天早上 JYY 发现一大群从 JSOI 王国里面跑来的兔子把他的花园全部占满了！兔子们把胡萝卜吃光了，JYY 靠什么过冬呢！忍无可忍的 JYY 决定取出他的强力猎枪来消灭这些兔子。

JYY 的花园是一个由 $n$ 块小菜地顺次连接所形成的圆环，编号为 $1$ 到 $n$。第 $i$ 号菜地和第 $i+1$ 号菜地是相邻的。由于花园是环形的，所以 $1$ 号菜地和 $n$ 号菜地也是相邻的。

现在，第 $i$ 号菜地上有 $r_i$ 只兔子。JYY 的猎枪有 $k$ 发子弹，每次 JYY 可以选择一块菜地打一枪，然后这块菜地上的兔子就全部都被消灭了。但是由于 JYY 的猎枪威力太大，会吓到相邻菜地上的兔子，所以，如果 JYY 朝 $i$ 号菜地打了一枪，那么 $i+1$ 号菜地上的兔子就会跑到 $i+2$ 号菜地上去，同样的，$i-1$ 号菜地上的兔子也会跑到 $i-2$ 号菜地上去。JYY 想知道，如何用这 $k$ 发子弹，消灭尽量多的兔子呢？

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

第二行 $n$ 个整数，第 $i$ 个为 $r_i$。

outputFormat: 一行一个整数，表示 JYY 最多可以消灭的兔子个数。

hint:
### 样例解释

先朝 $1$ 号菜地打一枪，变成 $0\ 0\ 6\ 7\ 0$，再朝 $4$ 号菜地打一枪。可以证明没有比 $13$ 大的答案。

### 数据范围

对于 $100\%$ 的数据，$3\leq n\leq 4000,0\leq k\leq 4000,r_i\leq 10^5$


title: [JSOI2011] 棒棒糖

description:
Coffee 的世界里也是有棒棒糖卖的，Coffee 买了 $n$ 只连着的棒棒糖。这 $n$ 只棒棒糖包裹在小塑料袋中，排成
一列，相邻的两只棒棒糖的塑料袋是接起来的。为了方便，我们把棒棒糖从左到右编号为$1\cdots n$。

每只棒棒糖有一种口味。第 $i$ 只的口味是 $c_i$。两只棒棒糖 $i,j$ 的口味相同，当且仅当 $c_i=c_j$。Coffee 对 $m$ 只棒棒糖总体口味的评价比较奇怪。如果这 $m$ 只棒棒糖中，有一种口味 $c_0$ 的数量严格大于总数的一半，那么 Coffee 认为这 $m$ 只棒棒糖主要是 $c_0$ 口味的。Coffee 知道，这里的 $c_0$ 如果存在就一定是唯一的。而当 $c_0$ 不存在时，Coffee 认为这 $m$ 只棒棒糖是混合口味的。

Coffee 暂时舍不得吃棒棒糖，它在想一些好玩的问题。如果考虑棒棒糖序列的一个连续子序列 $s\cdots t(1\leq s\leq t\leq n)$，包括棒棒糖 $s$ 和 $t$。那么这 $t-s+1$ 只棒棒糖的总体口味是什么呢？

Coffee有一堆这样的问题，一共 $m$ 个。第 $i$ 个问题是棒棒糖子序列 $s_i\cdots t_i$ 的总体口味，请你帮忙解决。

inputFormat:
第一行两个用空格隔开的整数，分别表示 $n,m$。

接下来 $n$ 行，每行一个整数，表示 $c_i$。

接下来 $m$ 行，每行两个整数，表示 $s_i,t_i$。

outputFormat: $m$ 行，每行一个整数，表示每个询问的总体口味。如果总体口味为混合口味则输出 $0$。

hint:
### 样例解释 1

在第一个询问中，口味 $1$ 出现 $3$ 次，大于总数的一半，所以总体口味为 $1$。

在第二个询问中，没有一种口味出现次数大于总数的一半，所以为混合口味。

在第三个询问中，口味 $2$ 出现 $2$ 次，大于总数的一半，所以总体口味为 $2$。

### 数据范围

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


title: [JSOI2014] 强连通图

description:
JYY 最近痴迷于图的强连通性，所以对于任何有向图，JYY 都希望增加一些边使得这个图变成强连通图。JYY现在得到了一个 $n$ 个点 $m$ 条边的有向图，所有点从 $1$ 到 $n$ 编号。

JYY 想知道：

- 在给定的图中，最多能选出多少个点，使得这些点在原图中两两可达？

- 在给定的图中，最少增加多少条边，可以使得这个图变成强连通图？

其中，一个有向图 $G(V,E)$是强连通的，当且仅当任意顶点 $a,b\in V,a\neq b$之间都存在 $a\to b$ 和 $b\to a$ 的路径。

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

接下来 $m$ 行，每行两个整数 $x$ 和 $y$，表示图中有一条从 $x$ 到 $y$ 的有向边。

outputFormat: 两行，第一行表示第一个问题的答案，第二行表示第二个问题的答案。

hint:
### 样例解释 1

对于第一个问题，无法选出互相连通两个点，答案为 $1$。

对于第二个问题，一种加边数最小的方案为 $(3,1)$ 和 $(4,2)$，答案为 $2$。

### 数据范围

对于 $100\%$ 的数据，$1\leq n\leq 10^5,1\leq m\leq 3\times 10^5$。


title: 「PMOI-1」抽奖

description:
活动奖池中共有 $n$ 种道具，dead_X 有 $m$ 张兑奖券。一张兑奖券可以兑换成一次抽奖机会或 $114514$ 金币。

dead_X 决定将一部分兑奖券拿来抽奖，并将剩下的兑奖券兑换成金币。

在一次抽奖机会中，dead_X 会等概率得到所有奖池中一款道具的 $1919810$ 秒**体验卡**。

由于 dead_X 在活动中买了 VIP 卡，他可以在所有抽奖结束后选择一款**抽奖得到**的体验卡，将所有这种类型的体验卡上交，并得到对应种类的**永久道具**。

注意，dead_X 可以不使用这个功能，但是不可以使用多于一次。

有选择困难症的 dead_X 想知道，有多少种可能的**活动结果**。

两种活动结果不同，当且仅当 dead_X 获得的金币不同，或者在任何一次抽奖中获得的体验卡不同（即抽到体验卡形成的序列不同），或者获得的永久道具不同。

注意，抽奖中获得的都是体验卡，最后选择的永久道具和体验卡在哪一次抽出没有关系。

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

Update 2023.11.16：出题人看自己好几年前写的题面绷不住了，补一份形式化题面。

定义一个序列的权值是其不同元素个数 $+1$，例如 $[1,9,2,6,8,1,7]$ 的权值是 $7$。

对于所有长度 $\in[0,m]$，每个数 $\in [1,n]$ 的整数序列，求其权值和对 $10^9+7$ 取模的值。

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

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

对于每组数据，输入两个正整数 $n,m$，分别表示道具的种数和兑奖券的张数。

outputFormat: 输出共 $T$ 行，每行输出一个正整数，代表方案数对 $10^9+7$ 取模的值。

hint:
【样例解释】

以下为第二组测试数据所有可能的方案：

假设两种物品分别为 $A$ 和 $B$。

1. 兑换 $229028$ 金币。
1. 兑换 $114514$ 金币，获得 $A$ 体验卡。
1. 兑换 $114514$ 金币，获得 $B$ 体验卡。
1. 兑换 $114514$ 金币，获得 $A$ 永久道具。
1. 兑换 $114514$ 金币，获得 $B$ 永久道具。
1. 第一次获得 $A$ 体验卡，第二次获得 $A$ 体验卡。
1. 第一次获得 $A$ 体验卡，第二次获得 $B$ 体验卡。
1. 第一次获得 $B$ 体验卡，第二次获得 $A$ 体验卡。
1. 第一次获得 $B$ 体验卡，第二次获得 $B$ 体验卡。
1. 第一次获得 $A$ 体验卡，第二次获得 $A$ 体验卡，指定 $A$ 为永久道具。
1. 第一次获得 $A$ 体验卡，第二次获得 $B$ 体验卡，指定 $A$ 为永久道具。
1. 第一次获得 $B$ 体验卡，第二次获得 $A$ 体验卡，指定 $A$ 为永久道具。
1. 第一次获得 $A$ 体验卡，第二次获得 $B$ 体验卡，指定 $B$ 为永久道具。
1. 第一次获得 $B$ 体验卡，第二次获得 $A$ 体验卡，指定 $B$ 为永久道具。
1. 第一次获得 $B$ 体验卡，第二次获得 $B$ 体验卡，指定 $B$ 为永久道具。

【数据范围】
- Subtask1（10pts）：$n,m\leq5,T\le25$；
- Subtask2（10pts）：$n=1$；
- Subtask3（10pts）：$m=1$；
- Subtask4（20pts）：$n,m\leq1000,T\leq 5$；
- Subtask5（20pts）：$\sum m\leq10^6$；
- Subtask6（30pts）：无特殊限制。

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


title: 计树

description: 求有多少不同的包含 $n$ 个点的有标号无根树，满足：对于任何一个点 $x$，都存在点 $y$ 使得 $x$ 和 $y$ 之间有一条边且 $|x - y| = 1$。答案对 $998244353$ 取模。

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

outputFormat: 一行一个整数，所求答案。


title: 送给好友的礼物

background: 小 M 和小 B 是一对好朋友，她们很喜欢草莓。

description:
给定一棵包含 $n$ 个结点的树 $T$，结点从 $1 \sim n$ 顺序编号。

小 M 和小 B 在时刻 $0$ 都在 $1$ 号结点。从时刻 $1$ 开始的每个时刻初，小 M 和小 B 都可以选择：移动到一个和自己所在结点直接相连的结点，或者停留在当前所在的结点。

树上有 $k$ 个草莓，它们分布在 $k$ 个不同的结点上。小 M 和小 B 想要收集到所有的草莓，任何一个时刻末，如果小 M 或者小 B 在某一个草莓所在的结点上，那么这个草莓就被收集了。

她们不想花费太多的时间，因此你需要回答：至少在第几时刻末，小 M 和小 B 可以收集到所有的草莓，并且都回到结点 $1$。

inputFormat:
第一行两个整数 $n, k$（$1 \leq k \leq n \leq 415$），分别表示树的结点个数和草莓的个数。
接下来 $n - 1$ 行，每行两个整数 $u$ 和 $v$，表示树上有一条从 $u$ 到 $v$ 的边。
接下来一行 $k$ 个互不相同的整数 $a_1, a_2, \ldots , a_k$，分别表示这 $k$ 个草莓所在的结点。

outputFormat: 一行一个整数，所求答案。

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

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

小 M 的路线是：$1 \to 2 \to 3 \to 2 \to 4 \to 2 \to 1$。

小 B 的路线是：$1 \to 5 \to 6 \to 7 \to 6 \to 5 \to 1$。

---

**【数据范围】**

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

- Subtask 1（$6$ 分）：$n \leq 3$。
- Subtask 2（$1$ 分）：$k = 1$。
- Subtask 3（$11$ 分）：$n \leq 7$。
- Subtask 4（$17$ 分）：$k \leq 20$。
- Subtask 5（$42$ 分）：$n \leq 90$。
- Subtask 6（$23$ 分）：无特殊限制。

对于 $100 \%$ 的数据，$1 \leq k \leq n \leq 415$，$1 \leq u, v \leq n$。


title: 草地

description:
给定一 $n \times m$ 的网格，其中每个格子均有颜色，可以为黑色或白色。

现可以进行若干次操作。一次操作中，你需选定上、下、左和右中的一个方向，然后，对于每个黑色的格子，若其指定方向上对应的位置不为网格的边界，则对应的那个格子变为黑色。

求：至少进行几次操作，才能使任意两个黑色格子八连通。八连通的定义可参考【提示/说明】部分。

inputFormat:
第一行两个整数 $n,m$（$1 \leq n,m \leq 10^3$），表示网格的大小。
接下来 $n$ 行，每行一个长为 $m$ 的 01 字符串，第 $i$ 个串的第 $j$ 位为 $1$ 则表示第 $i$ 行 $j$ 列的格子是黑色，否则是白色。

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

hint:
----

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

对于第一组样例，一开始的网格如图（1）所示。

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

（1）

进行一次操作，选择下方向，网格会变为图（2）所示的样子（标红的是新变为黑色的格子），此时任意两个黑格都八连通。

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

（2）

----

**【数据范围】**

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

- Subtask 1（$10$ 分）：保证 $n, m\leq 3$。
- Subtask 2（$10$ 分）：保证 $n, m \leq 80$。
- Subtask 3（$5$ 分）：保证黑色格子的数量不超过 $20$。
- Subtask 4（$5$ 分）：保证 $m = 1$。
- Subtask 5（$25$ 分）：保证 $n, m \leq 300$。
- Subtask 6（$45$ 分）：没有特殊限制。

对于 $100 \%$ 的数据，保证 $1 \leq n,m \leq 10^3$，至少有一个黑色格子。

**八连通的定义**

两个黑色格子八连通，当且仅当在它们之间有公共顶点或公共边，或存在一个黑色格子同时与它们八连通。

用比较通俗的话说，就是它们在只能向周围相邻的八个格子行走，且只能经过黑色格子的条件下相互可达。


title: ix35 的等差数列

background: 等差数列是指从第二项起，每一项与它的前一项的差等于同一个常数的一种数列，并称这个常数为公差。特别地，认为只有一项的数列也是等差数列，其公差视为 $0$。

description:
给定一包含 $n$ 项的正整数列 $a_1, a_2, \ldots , a_n$，满足 $1 \leq a_i \leq w$。

现可以进行若干次修改，一次修改可将数列的任意一项修改为任意 $\leq w$ 的正整数。

求：至少进行多少次修改，才能使得原数列变为一公差为非负整数的等差数列。

inputFormat:
第一行两个整数 $n, w$。
接下来一行 $n$ 个整数 $a_1, a_2, \ldots , a_n$。

outputFormat: 一行一个整数，所求答案。

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

将 $a_3$ 修改为 $3$，$a_5$ 修改为 $5$。

---

**【数据范围】**

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

- Subtask 1（$20$ 分）：$n = 2$，$w = 2$。
- Subtask 2（$20$ 分）：$n, w \leq 100$。
- Subtask 3（$10$ 分）：$a_i = 1$。
- Subtask 4（$20$ 分）：$n, w \leq 1000$。
- Subtask 5（$30$ 分）：没有特殊限制。

对于 $100 \%$ 的数据，$1 \leq n, w \leq 3 \times 10^5$。

---

原始 idea：ix35。


title: 磁控法则

background:
>那只不过是别人的不幸。

诺顿进入了一个结构复杂的洞穴。在之前的勘察中，他已经得知了这个洞穴里有他梦寐以求的宝藏。

然而这个洞穴是如此的黑暗与复杂，以至于他探索了许久都没有找到宝藏的所在地。但宝藏强大的吸引力仍驱使着他继续搜寻。然而很快他就意识到了不对劲，因为那股吸引力不仅作用在他脑海中，也作用在他身体上——宝藏的防御机关正释放巨大的磁力试图驱逐外来者。

「果然，这就是它自带的保护机制吗？」诺顿笑了笑，拿出了一小块散发着奇特光芒的金属。

「不过，我也是有准备的。」

description:
诺顿所在的洞穴可以看作是由 $n$ 个洞窟和 $n-1$ 条通道形成的树状结构，诺顿在石窟 $s$，宝藏在石窟 $t$。在宝藏所在的石窟里有一块拥有强大磁场的特殊的磁铁，诺顿身上也有一块小型的同样材质的磁铁。宝藏石窟里的磁铁**只有一个磁极**（N 或 S），并且**磁极不会发生变化**。诺顿身上的磁铁也**只有一个磁极**（N 或 S），但**每个时刻开始时会有 $p$ 的概率切换磁极**（N 变成 S，S 变成 N）。

每个时刻诺顿的移动方式由宝藏石窟磁铁的磁极和诺顿身上磁铁的磁极决定：

1. 两块磁铁磁极不同。此时两块磁铁会触发「吸引」效果。诺顿会因为磁铁间的吸引力移动到与 $s$ 相连的石窟中到 $t$ 距离 $-1$ 的石窟中（即**以 $t$ 为根时 $s$ 的父亲**）。

2. 两块磁铁磁极相同。此时两块磁铁会触发「弹射」效果。诺顿会因为磁铁间的排斥力**等概率**移动到与 $s$ 相连的石窟中到 $t$ 距离 $+1$ 的石窟（即**以 $t$ 为根时 $s$ 的任意一个儿子**）。如果没有满足的石窟，将触发「眩晕」效果，下个时刻诺顿将**不进行任何的移动，也不会进行任何的磁极切换**。

经过一段时间的勘察，诺顿已经知道了整个洞穴的结构以及磁极切换的概率 $p$。为了更好的寻找宝藏，他每次会向你提出询问，你需要回答他如果一开始诺顿在石窟 $x$，身上磁铁磁极为 $c_1$，宝藏在石窟 $y$，石窟内磁铁磁极为 $c_2$，期望在多少时刻后诺顿可以找到宝藏。

inputFormat:
第一行三个整数 $n,q,p$，分别表示石窟数，询问数和磁极切换概率。其中磁极切换概率为在 $998244353$ 取模意义下的概率。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示石窟 $u$ 和石窟 $v$ 之间存在一条通道。保证最后结构为一棵树。

接下来 $q$ 行，每行**依次**有一个正整数 $x$，一个字符 $c_1$，一个正整数 $y$，一个字符 $c_2$，表示一个询问，各自意义如上。保证 $c_1,c_2$ 为 `N` 或 `S`。

outputFormat: $q$ 行，每行一个非负整数，表示询问答案对 $998244353$ 取模后的结果。

hint:
#### 样例一解释
每个时刻磁极切换概率为 $\dfrac{1}{2}$。

洞窟结构如下：
![](https://cdn.luogu.com.cn/upload/image_hosting/od4ixuog.png)

对于询问 $1$，诺顿在第 $1$ 个时刻有 $\dfrac{1}{2}$ 的概率移动到 $1$，有 $\dfrac{1}{2}$ 的概率触发「眩晕」进入第 $3$ 个时刻。在第 $3$ 个时刻同样有 $\dfrac{1}{2}$ 的概率移动到 $1$，有 $\dfrac{1}{2}$ 的概率触发「眩晕」进入第 $5$ 个时刻……期望结果为 $1\times\dfrac{1}{2}+3\times\left(\dfrac{1}{2}\right)^2+5\times\left(\dfrac{1}{2}\right)^3+\ldots=3$。

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

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

+ Subtask 1 ( $10\%$ )：$n,q\leq15$。
+ Subtask 2 ( $20\%$ )：$n\leq10^3$。
+ Subtask 3 ( $25\%$ )：对于所有询问，保证 $y=1$。
+ Subtask 4 ( $45\%$ )：无特殊限制。

对于所有数据，$2\leq n\leq5\times 10^5,1\leq q\leq5\times10^5,1\leq u,v,x,y\leq n,x\neq y,2\leq p\leq998244352$。

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


title: Choose

background:
[加强版](https://www.luogu.com.cn/problem/U397746)

对于一个长度为 $n$ 的序列 $a$ ，定义 $a$ 的极差表示 $a$ 中最大值与最小值之差；定义 $C(a,l,r)$ 表示 $a$ 的**连续**子序列 $[a_l,a_{l+1},\dots,a_r]$，其中 $1\le l\le r\le n$。

description:
给定一个长度为 $n$ 的序列 $a$。

你需要选出 $a$ 的 $k$ 个长度均为 $L$ $(1\le L\le n-k+1)$ 的不同**连续**子序列
$C(a,l_1,l_1+L-1),C(a,l_2,l_2+L-1),\dots,C(a,l_k,l_k+L-1)$，其中 $1\le l_1<l_2< \dots< l_k\le n-L+1$。

记这 $k$ 个子序列中极差的最小值为 $X$，你需要求出 $X$ 的最大值。同时，你还需要求出，在满足 $X$ 最大的情况下  $L$ 的最小值。

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

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

对于每组测试数据：

- 第一行两个整数 $n,k$。
- 第二行 $n$ 个整数 $a_1,a_2,...,a_n$。

outputFormat:
对于每组测试数据：

- 一行两个整数 $X,L$，表示所求极差和子序列长度。


title: 「MCOI-Zero / AC6-M15」 Chandelier

background:
「不，还没完……」

「什么！？」

「炮管打开了。
　那个丑陋的东西开始通过炮管散热了！」

「它的关键区域就在炮管后面。」

「Talisman……
　……我们可以信任你，对吗？」

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 15} \\\Large\text{Chandelier}\\\tiny -\textit{ To All Things }
-$$

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

description:
Chandelier 的核心可以被描述为一个 $n\times m$ 的矩阵。初始时，矩阵中的每一个格子都是一个独立的空间。

如果在核心中存在两个空间使得它们在矩阵上的并是一个矩形，则这两个空间可以合并为一个空间，合并出的空间就是原先两个空间的并。

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

如果不存在任何两个空间的并是矩形，则我们称核心达到了稳定状态。

如果一个空间的长达到了 $n$ 或者宽达到了 $m$，那么核心将会短路，引发爆炸。**注意这里空间的长指的是和原矩阵的长为 $n$ 的边平行的边的长度，宽类似。也就是说如果平行于 原矩形的长为 $n$ 的边 的边长达到了 $m$ 且 $m<n$，那么这是合法的。**

核心达到了稳定状态后，你才能攻击并摧毁它，需要的攻击次数就是剩下的空间数。

你剩下的弹药不多了，所以只能攻击 $10$ 次。

你需要合理地控制空间的合并，使得核心在不短路的情况下达到稳定状态，且需要的攻击次数 $\leq 10$。

求出一种可能合并出来的形态。如果核心无法在不短路的情况下达到稳定或者无法合并为 $\leq 10$ 个空间，输出 $-1$。

inputFormat: 一行用空格分割的两个整数 $n,m$。

outputFormat:
如果无解，输出一行 `-1`。

如果有解，在第一行输出一个整数 $x$，表示空间数量。

然后输出一个 $n\times m$ 的矩阵 $a$，满足 $1\leq a_{i,j}\leq x$。$a_{i,j}$ 表示 $(i,j)$ 属于哪一个空间。相同的数代表相同的空间，不同的数代表不同的空间。

如果有多解，输出任意一个即可。

hint:
- Subtask 1（20 pts）：$n,m\leq 2$。
- Subtask 2（40 pts）：$n,m\leq 4$。
- Subtask 3（40 pts）：无特殊限制。

对于 $100\%$ 的数据，满足 $1\leq n,m\leq 10^{3}$。

idea：Sol1，solution：Sol1，code：Sol1，data：Sol1

---

「我看见大炮终于完了……」

「全机注意，
　战争结束了。」

……

「Talisman 看，太阳升起来了。」

「尽管黑夜是如此漫长，但终将迎来黎明的曙光。」

「我们失去的战友，都把他们的生命之火
　献给了破晓之光。」

「我们尽最大努力存活——
　就是对他们的最好悼念。」

「现在，来吧。」

「让我们回家吧。」


title: 「小窝 R3」自傷無色

background:
> こんな僕が生きてるだけで
何万人のひとが悲しんで
誰も僕を望まない
そんな世界だったらいいのにな
——[《自傷無色》](https://music.163.com/song?id=29124091)

description:
给定一棵 $n$ 个节点的树，根节点为 $1$，有边权。约定树上 $u,v$ 两点间路径长度 $d(u,v)$ 为 $u,v$ 间路径上的边权和。

对于一个无序二元组 $(u,v)$，定义一个「树三角」当且仅当同时满足：

- $u,v$ 的最近公共祖先 $w\neq u$ 且 $w\neq v$。
- 以 $d(u,w),d(v,w)$ 和某个正整数 $x$ 为边长，能构成一个三角形。$x$ 是任意选取的，因此一对 $(u,v)$ 可能会产生多个树三角。

此时 $d(u,w)+d(v,w)+x$ 即为这个树三角的大小。具体例子参考样例解释。

定义两个树三角不同，只需满足下列条件中的**一条**：

- 无序二元组 $(u,v)$ 不同。
- 树三角的大小不同。

对于一个带边权的树 $T$，定义其正弦值 $\sin T$ 为 $T$ 中所有树三角大小的和与 $T$ 中不同树三角总数量的比值。

小 H 给出了 $T$，希望你能求出 $\sin T$。为了避免误差，结果对 $10^9+7$ 取模。特别地，若 $T$ 中不存在树三角，则 $\sin T=0$。

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

接下来 $n-1$ 行，每行三个正整数 $u,v,w$：表示节点 $u,v$ 之间有一条权值为 $w$ 的边。

outputFormat: 共一行，为 $\sin T$ 的值对 $10^9+7$ 取模。数据保证 $T$ 中不同树三角总数量不是 $10^9+7$ 的倍数。


title: [JRKSJ R1] 吊打

description:
给出 $n,m$ 表示有 $n$ 个数，$m$ 次操作，$a_i$ 表示序列中第 $i$ 个数。

你需要写一种数据结构，支持两种操作：
- `1 l r`，表示将所有 $i\in[l,r]$，将 $a_i\gets\left\lfloor\sqrt{a_i}\right\rfloor$。
- `2 l r`，表示将所有 $i\in[l,r]$，将 $a_i\gets{a_i}^2$。

最后需要输出 $\sum_{i=1}^na_i$ 表示你维护了这个序列。

inputFormat:
输入共 $m+2$ 行。\
第一行输入两个正整数 $n,m$，意义如上。\
第二行输入 $n$ 个整数 $a_i$，意义如上。\
接下来 $m$ 行，每行 $3$ 个正整数，表示一次操作，格式如上。

outputFormat:
输出一行一个整数表示 $\sum_{i=1}^na_i$。\
答案对 $998244353$ 取模。


title: [JRKSJ R1] 1+1

description:
### 玩法简介

「1+1」 是一款双人对抗游戏。两名玩家各自拥有两个数，每次一名玩家可以用自己的一个数加上对方的一个数，如果大于 $9$ 则取个位。双方轮流执行此步骤。如，下面记录了游戏的几个回合，玩家双方分别为 `a` 和 `b`：

在下面的局面解释中，第一个局面标 `*` 的是先手。

```
a:1 1*（初始局面）
b:1 2

a:1 3（1+2）
b:1 2

a:1 3
b:1 5（2+3）

a:6 3（1+5）
b:1 5
```
---

### 特殊局面

我们把下面的情况称为「攻击」：

```
3 3
5 3
6 1
9 1
```
这些攻击的「攻击度」为 $1$ ，除了 `9 1`。`9 1` 的攻击度为 $2$ 。

下面的情况称为「防御」：

```
5 1
5 5
```
这些防御的「防御度」为 $1$ ，除了 `5 5`。`5 5`的 防御度为 $2$ 。

当然，所有的攻击或防御不分两个数的顺序，如 `5 1` 和 `1 5` 都视作防御，而
 `9 1` 和 `1 9` 也都视为攻击，而攻击/防御度不变。

如果玩家 `a` 持有防御，而玩家 `b` 在下一步走成了攻击，如下面的情况：

```
a:1 5
b:1 1*

a:1 5
b:6 1
```
那么此时 `a` 持有防御度为 $1$ 的 `1 5`， `b` 持有攻击度为 $1$ 的 `6 1`，此时应该将 `a` 持有的数变成 `1 1` 而 `b` 的此次攻击无效。

也就是说，如果 `a` 的攻击的攻击度与 `b` 的防御的防御度相等，则将 `b` 的两个数变为 `1 1` 而 `a` 的此次攻击视作无效。

我们认为不属于上面的攻击/防御的攻击/防御度为 $0$ （如 `3 4` 等。）

特别的，如果遇到下面这种情况：

```
a:5 5
b:1 1*

a:5 5
b:1 6
```
`a` 的防御度为 $2$ 而 b 的攻击度为 $1$ 。此时应该把 `a` 变成 `5 1` 而 `b` 的此次攻击作废。

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

### 胜利条件

如果一方走完一步后，他的攻击度严格大于另一方的防御度，则这一方获胜。此时不应该做任何改动，即使要把另一方变成 `1 1` 或 `5 1`。

下面给出了一个例子：

```
a:1 1
b:6 3*

a:1 1
b:6 4

a:1 5
b:6 4

a:1 5
b:6 9

a:1 1
b:6 9

a:1 1
b:6 0

a:1 7
b:6 0

a:1 7
b:6 1

（ b 胜）
```
为了消除歧义，下面再给出一些例子：

```
a:5 5
b:1 4*

a:1 1
b:1 9

a:1 0（ 1+9=10 ，个位为 0 ）
b:1 9

a:1 0
b:1 9（注意这里， b 用 1 （或 9 ）加了 a 的 0 ，这样也算一次新的攻击）

（ b 胜）
```

```
a:1 1*
b:1 4

a:1 5
b:1 4

a:1 5（因为是最后一步，无须变成“1 1”）
b:1 9（这里 b 的“1 9”直接碾压了 a 的“1 5”）

（ b 胜）
```

现在，你被要求写一个程序，作为先手通过交互的方式和 mcyl35 的程序玩这个游戏。

inputFormat:
第一行五个整数 $p_0,p_1,c_0,c_1,P$，分别表示你的两个数，mcyl35 的两个数和测试点编号。

下面每行两个整数 $x,y$，表示 mcyl35 的第 $x$ 个数加上了你的第 $y$ 个数。

本题使用 IO 交互，具体可见 [P1733 猜数（IO交互版）](https://www.luogu.com.cn/problem/P1733)。

outputFormat: 每行两个整数 $x,y$，表示你的第 $x$ 个数加上了 mcyl35 的第 $y$ 个数。

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

对于测试点 $1$，保证玩家可以一步获胜。

对于测试点 $2$，保证 mcyl35 的程序随机走步。

对于其他测试点，无特殊约定。

对于 $100\%$ 的数据，$0\le p_0,p_1,c_0,c_1\le 9$。

#### 评分标准

* 有不合法的输出（如输出中含有除了 $0,1$ 之外的数），得 $0$ 分。

* 获胜或走了 $100$ 步及以上本测试点可以获得满分。

* 否则获得 $\lfloor \dfrac {st} {20} \rfloor$ 分，$st$ 表示走的步数，一步表示 mcyl35 走一步。

#### 提示

当交互库没有返回数时，说明结果已经被判定了。

#### 样例解释

```
pl:1 1*
cp:1 2

pl:2 1
cp:1 2

pl:2 1
cp:1 3

pl:5 1
cp:1 3

pl:5 1
cp:1 8

pl:6 1(胜)
cp:1 8
```


title: [JRKSJ R1] 异或

description:
给你 $n,k$ 和序列 $a_{1,2\dots n}$，选出 $k$ 个**不交**区间 $[l_i,r_i]\subseteq[1,n]$，求出
$$\max_{l_i,r_i}\sum_{i=1}^k\bigoplus_{j=l_i}^{r_i}a_j$$

式中 $\oplus$ 表示二进制异或运算。

**保证数据随机。**

inputFormat:
输入共 $2$ 行。\
第 $1$ 行输入两个数 $n,k$。\
第 $2$ 行输入 $n$ 个非负整数代表序列 $a$。

outputFormat: $1$ 行输出一个非负整数，代表这个式子的最大值。


title: 「EZEC-9」Yet Another Easy Problem

description:
给定 $n,m$，你需要输出一个长度为 $n$ 的排列，满足该排列进行不超过 $m$ 次操作可以得到的最小的字典序最大。

定义一次操作为交换排列中的两个数。

若有多个符合要求的排列，输出任意一个均可。

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

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

对于每组数据，一行 $2$ 个整数 $n,m$。

outputFormat:
对于每组数据：

一行 $n$ 个正整数，表示你构造的排列。

hint:
【样例 $1$ 说明】

使得字典序最小的操作方案为:

$4\ 3\ 1\ 2\to1\ 3\ 4\ 2\to1\ 2\ 4\ 3$。

可以证明无法得到更小的字典序，以及其他初始排列无法得到更大的最小字典序。

【样例 $2$ 说明】

显然可以通过操作得到任何排列，输出任意长度为 $3$ 的排列均可。

【数据规模与约定】

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

- Subtask 1（10 points）：$m=0$。
- Subtask 2（10 points）：$m\ge n-1$。
- Subtask 3（25 points）：$m=1$。
- Subtask 4（25 points）：$T\le100$，$n\le6$。
- Subtask 5（30 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le n\le10^5$，$0\le m\le n$，$\sum n\le10^5$。


title: 「PMOI-1」中位数

description:
给定一棵以 $1$ 为根的包含 $n$ 个节点的**有根树**。第 $i$ 个节点有点权 $a_i$。

定义函数 $f(u,v)$ 表示从 $u$ 到 $v$ 经过的所有节点的点权的**可重集**的中位数。

请注意，**本题中的中位数的定义与数学中的定义略有不同**：这里一个长度为 $t$ 的序列的中位数定义为这个序列第 $\left\lceil\frac{t+1}2\right\rceil$ 小的数。

定义函数 $\text{cover}(x_1,y_1,x_2,y_2)$ 表示从 $x_1$ 到 $y_1$ 的路径是否完全覆盖了从 $x_2$ 到 $y_2$ 的路径。如果完全覆盖，则 $\text{cover}(x_1,y_1,x_2,y_2)=1$，否则  $\text{cover}(x_1,y_1,x_2,y_2)=0$。

你需要依次处理 $q$ 次操作，按照以下格式给出：

`1 u`：表示一次操作，需要你将点 $u$ 的点权对 $1$ **异或**；

` 2 u v`：表示一次询问，需要你求出 $\max\limits_{1\le i\le n,1\le j\le n}\{\text{cover}(i,j,u,v)f(i,j)\}$。

对于第二类操作，保证每次询问均满足 $u$ 不是 $v$ 的祖先且 $v$ 不是 $u$ 的祖先，且 $u \neq v$。

你需要对于每个第二类操作，输出对应的值。

inputFormat:
第一行两个正数 $n$ 和 $q$ ，分别表示树的节点数与询问次数。

第二行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个节点的点权 $a_i$。

下面 $n-1$ 行，每行两个整数 $x,y$ ，描述一条连接 $x$ 与 $y$ 的边。

下面 $q$ 行，每行先输入一个整数 $opt$ ，表示本次是是操作还是询问。 若 $opt=1$ ，则这是一次操作，且接下来会输入一个整数 $u$ ；若 $opt=2$ ，则这是一次询问，且接下来会输入两个整数 $u,v$ 。其具体意义见【题目描述】。

outputFormat: 对于每次询问输出一行，即对应询问的答案。

hint:
【样例解释】

第一次是询问。显然，只有 $(i=4,j=8)$ 满足 $\text{cover}(i,j,u,v)=1$。此时 $f(i,j)=3$。

第二次是操作。将 $3$ 号节点的点权改为了 $2$。

第三次是询问。当 $i=4,j=3$ 时，$\text{cover}(i,j,u,v)=1$ 且 $f(i,j)=4$ 。不难发现，对于其他所有满足 $\text{cover}(i,j,u,v)=1$ 的节点对 $(i,j)$，均没有 $f(i,j) >4$。

【数据范围】
- Subtask1（8pts）：$n,q\le50$；
- Subtask2（12pts）：$n,q\le2\times10^3$；
- Subtask3（16pts）：$n,q\le4\times10^4$；
- Subtask4（10pts）：保证树的形态随机生成；
- Subtask5（12pts）：保证没有 $1$ 操作；
- Subtask6（12pts）：保证每次询问的 $u,v$ 都是叶子节点；
- Subtask7（30pts）：无特殊限制。

Subtask4 的随机方式为 ：随机生成一个的排列 $p$，对于 $i\in[2,n]$，$p_i$ 向 $p_1,p_2,...,p_{i-1}$ 中等概率随机的一个点连边。

对于 $100\%$ 的数据满足，$1\le n,q,a_i \le 10^5$，保证每次询问均满足 $u$ 不是 $v$ 的祖先且 $v$ 不是 $u$ 的祖先，且 $u \neq v$ 。


title: [JRKSJ R1] JFCA

description:
给出一个环，上面有 $n$ 个点，每个相邻的点对之间的距离为 $1$。

每个点有两个属性 $a_i$ 和 $b_i$，对于点 $i$，定义 $f_i$ 为它与满足 $a_j\ge b_i$ 的最近的点 $j$ 与 $i$ 在环上距离较短一边的长度，其中 $i\ne j$。如果没有满足条件的 $j$，其 $f_i=-1$。

inputFormat:
输入共 $3$ 行。\
第 $1$ 行 $1$ 个整数 $n$ 。\
第 $2$ 行 $n$ 个整数，其中第 $i$ 个表示 $a_i$，意义同上。\
第 $3$ 行 $n$ 个整数，其中第 $i$ 个表示 $b_i$，意义同上。

outputFormat: 输出 $1$ 行 $n$ 个整数，其中第 $i$ 个表示 $f_i$，意义同上。


title: 「EZEC-7」维护序列

background:
[![](https://cdn.luogu.com.cn/upload/image_hosting/lo9tuyl9.png)](https://www.luogu.com.cn/paste/tdqr0sto)

可怜的 dead_X 收不了歌，于是他出了个水题并给参赛者送了 $100$ 分。

2022 Update: 已经收了，很水。

description:
你需要维护一个序列。

这个序列开始时有 $2^n$ 个数，下标从 $0$ 开始。第 $i$ 个数初始值为 $i$，需要支持以下三种操作：

* 定义 $a$ 为所有下标为偶数的数组成的子序列，$b$ 为所有下标为奇数的数组成的子序列，将 $a,b$ 连接，构成新的序列。
* 定义 $a$ 为所有下标为奇数的数组成的子序列，$b$ 为所有下标为偶数的数组成的子序列，将 $a,b$ 连接，构成新的序列。
* 查询下标为 $x$ 的数。

总共将进行 $m$ 次操作。

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

接下来输入 $m$ 行，每行输入两个非负整数 $op,x$，代表一次操作。

如果 $op=1$，若 $x=0$，代表第一种操作，若 $x=1$，代表第二种操作。

如果 $op=2$，代表第三种操作，参数 $x$ 即为输入的 $x$。

outputFormat: 对于每个 $op=2$ 输出一行，即对应的数。


title: 「C.E.L.U-02」学术精神

description:
提供 **一句话题意** 阅读。

某地有 $n$ 个小朋友，每个小朋友都有一个**独特的**  idea，其中第 $i$ 个小朋友的 idea 的 **编号** 为 $i$。老师让这个每一个小朋友在一组编号分别为 $1\sim n$ 的卡片中随机抽一个，**抽完后把卡片放回去**，这个小朋友会和编号为卡片上数字的小朋友**交换** idea（交换指**两人**把**所有**自己知道的 idea 告诉对方）。因为自己和自己交换 idea 在他们眼中也许是一件很傻的事情，所以如果**卡片上的编号与自己的相同**，他将再抽一次（此时他已经把卡片放回去了），**直到编号不是自己**的为止。

不久，每个小朋友都抽完了一遍，每个小朋友将把收集到的**所有** idea 出成一场比赛，因为有 idea 的交换，有很多比赛之间都是**有联系**的。

如果两场比赛中存在 idea **相同**的题目，我们认为这两场比赛是有联系的。「联系」具有**传递性**：**如果比赛 $\mathbf A$、$\mathbf B$ 有联系，比赛 $\mathbf B$、$\mathbf C$ 有联系，则比赛 $\mathbf A$、$\mathbf C$ 也有联系**。为了避免理解错误，在这举一个例子：

若仅有四场比赛：比赛一出现了 idea $1$、$2$；比赛二出现 idea $2$、$5$ ；比赛三出现 idea $3$、$5$、$8$，比赛四出现 idea $4$、$7$。则比赛一、二之间有**直接联系**。比赛一、三之间虽然没有公共 idea，但它们之间是**有联系**的。比赛四与其他所有比赛没有联系。

而所有有联系的比赛都将属于同一个比赛集，没有联系的比赛处在不同的比赛集。

上例中比赛一、二、三属于一个比赛集，比赛四属于另一个。

求所有人**抽球卡片的次数和**的期望 $E_0$ 和比赛集的个数 $s$ 的期望 $E_1$。

---

**一句话题意：**

对于每个点 $i$ 随机与 $[1,n]$ 中的一点连无向边，若连向自己，则保留该边并再次连边，一直重复至连到别的点上为止，求边数与连通块个数期望。

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

outputFormat:
第一行输出一个数 $E_0$ ，第二行输出一个数 $E_1$ ，可以证明它们都是**有理数**。

为了避免精度误差，您只需要输出它们对质数 $998244353$ 取模的结果即可，如果您不会分数取模，您可以查找关于费马小定理与乘法逆元的相关资料。

如果输出格式错误或两问答案均错误，该测试点得 $0$ 分；

如果仅答对第一问，该测试点得 $3$ 分；

如果仅答对第二问，该测试点得 $7$ 分；

如果两问均正确，该测试点得 $10$ 分。

**请务必输出两个整数。**


title: 既见君子

background:
友情客串：wygz（无忧公主）

wygz 每次从进校到机房，都要尽量避开“屠夫”老师。然而，有一天，她忽然发现一些门上居然贴了“请勿从此门进出”的标签！

description:
校园可以抽象成一张 $n$ 个点 $m$ 条无向边（可能有重边，无自环）的**连通**无向图，点从 $1$ 标号到 $n$。校门在 $1$ 号点，而机房在 $n$ 号点，屠老师的办公室在点 $z$（$z\ne 1,n$）。

然而，工作人员（~~其实是樱初音~~）封锁了其中的 $m-n+1$ 条边，使得剩余的图（包括所有点以及剩余的边）仍然连通，此时任意两点之间有且仅有一条简单路径。工作人员会**等概率地**选择一种封锁方案。（若 $m=n-1$ 则不封锁任何边，保持不变）

wygz 当然不希望屠老师的办公室出现在她的必经之路上。她希望你算出从校门到机房的路径**必须**经过屠老师的办公室的概率。答案对 $998244353$ 取模。

inputFormat:
第一行三个正整数 $n$、$m$ 和 $z$，表示点数、边数和屠老师的办公室的位置。

以下 $m$ 行，每行两个正整数 $u$、$v$，表示一条连接 $u$ 和 $v$ 的无向边。

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


title: [COCI2020-2021#4] Pizza

background: 在一个漫长而痛苦的一天快要结束时，Mirko 决定订一个比萨来提神。在他书桌的一堆纸中，他找到了一个附近比萨店的传单。

description:
比萨店提供 $m$ 种不同的比萨。比萨的配料使用正整数来编号。第 $i$ 个比萨有 $k_i$ 种配料，编号分别为 $b_{i,1},b_{i,2},\cdots,b_{i,k_i}$。

Mirko 在食物面前格外挑剔。他不喜欢其中的 $n$ 种配料，即编号为 $a_1,a_2,\cdots,a_n$ 的配料，因此他想订购一个没有上述配料的比萨。求 Mirko 能订购的比萨的数量。

inputFormat:
第一行输入一个整数 $n$，表示 Mirko 不喜欢的配料的种数。接下来输入 $n$ 个互不相同的整数 $a_i$，表示 Mirko 不喜欢配料所对应的编号。

第二行输入一个整数 $m$，表示比萨的数量。

接下来的 $m$ 行，第 $i$ 行输入一个整数 $k_i$，表示第 $i$ 个比萨的配料数量。接下来输入 $k_i$ 个互不相同的整数 $b_{i,j}$，表示该比萨的配料编号。

不会出现两个具有完全相同配料的比萨。

outputFormat: 输出 Mirko 能订购的比萨的数量。

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

对于 $40\%$ 的数据，$n=k_1=k_2=\cdots=k_m=1$。

对于 $100\%$ 的数据，$1 \le n,m,a_i,k_i,b_{i,j} \le 100$。

#### 说明

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

**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf)  _T1 Pizza_。**


title: [COCI2020-2021#4] Vepar

description: 给定两组正整数 $\{a,a+1,\cdots,b\}$ 和 $\{c,c+1,\cdots,d\}$。判断 $c \cdot (c+1)\cdots d$ 能否被 $a \cdot (a+1)\cdots b$ 整除。

inputFormat:
第一行输入一个整数 $t$，表示数据组数。

接下来的 $t$ 行，输入四个整数 $a_i,b_i,c_i,d_i$。

outputFormat: 输出共 $t$ 行。对于第 $i$ 行，如果 $c_i \cdot (c_i+1)\cdots d_i$ 能够被 $a_i \cdot (a_i+1)\cdots b_i$ 整除，就输出 `DA`，否则输出 `NE`。

hint:
#### 样例 1 解释

按照题意分别相乘得到 $9 \times 10=90$ 和 $3 \times 4 \times 5 \times 6=360$。由于 $90$ 能被 $360$ 整除，因此输出 `DA`。

我们得到 $2 \times 3 \times 4 \times 5=120$ 和 $7 \times 8 \times 9=504$。而 $120$ 不能被 $504$ 整除，因此输出 `NE`。

#### 数据规模与约定

本题**不采用捆绑评测**，通过对应测试点就可以拿到对应的分数，但有若干个约束。

| 约束编号 | 分值 | 数据范围及约定 |
| :----------: | :----------: | :----------: |
| $1$ | $10$ | $a_i,b_i,c_i,d_i \le 50$ |
| $2$ | $20$ | $a_i,b_i,c_i,d_i \le 1000$ |
| $3$ | $10$ | $a_i=1$ |
| $4$ | $30$ | 无 |

对于 $100\%$ 的数据，$1 \le t \le 10$，$1 \le a_i \le b_i \le 10^7$，$1 \le c_i \le d_i \le 10^7$。

#### 说明

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

**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf)  _T2 Vepar_。**


title: [COCI2020-2021#4] Hop

background: > 杰瑞米是一个牛蛙，是我的一个好朋友。

description:
有 $n$ 片百合花，它们分别从 $1$ 到 $n$ 依次编号。第 $i$ 片上有一个整数 $x_i$，而序列 $(x_i)_{1 \le i \le n}$ 单调递增。

三只青蛙到来。

每对满足 $a \lt b$ 的百合 $(a,b)$ 必须属于青蛙 $1,2$ 或 $3$ 中的其中一只。

当百合 $(i,j)$ 属于一只青蛙且 $x_j$ 能被 $x_i$ 整除时（$j \gt i$），该青蛙可以从 $i$ 号百合跳动到第 $j$ 号。

请找出一种分类方案，使得任何一只青蛙都不会连续跳动 $3$ 次。

inputFormat:
第一行输入一个正整数 $n$，表示百合花的数量。

第二行输入 $n$ 个正整数 $x_i$，表示百合花上的整数。

outputFormat: 输出 $n-1$ 行。第 $i$ 行输出 $i$ 个整数，其中该行第 $j$ 个整数表示 $(j,i+1)$ 所归属的青蛙。

hint:
#### 样例 1 解释

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

青蛙 $1,2,3$ 分别用蓝、绿和红色代替。

蓝蛙可以从 $x_1=3$ 跳动到 $x_4=9$，再跳动到 $x_7=36$，再到 $x_8=72$。该青蛙只能进行 $3$ 次连续的跳动。

绿蛙可以从 $x_2=4$ 跳动到 $x_5=12$，再跳动到 $x_7=36$。该青蛙只能进行 $2$ 次连续的跳动。

红蛙不能从 $x_2=4$ 跳动到 $x_3=6$，因为 $6$ 不能被 $4$ 整除。

#### 数据规模与约定

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

| Subtask | 分值 | 数据范围及约定 |
| :----------: | :----------: | :----------: |
| $1$ | $10$ | $n \le 30$ |
| $2$ | $100$ | 无 |

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le x_i \le 10^{18}$。

#### 评分方式

在输出方案中，如果其中一只青蛙可以连续跳动 $k$ 次，其中 $k \gt 3$，而没有青蛙可以连续跳动 $k+1$ 次，则对应测试点的分数为 $f(k)·x$ 分，其中：

$$f(k)=\dfrac{1}{10}·
\begin{cases}
11-k & (4 \le k \le 5) \cr
8-\lfloor {\dfrac{k}{2}} \rfloor & (6 \le k \le 11) \cr
1 & (12 \le k \le 19) \cr
0 & (k \ge 20) \cr
\end{cases}$$

而 $x$ 为对应子任务的总分。每个子任务的得分等于该子任务中所有测试点得分的最小值。

因本题的评分方式特殊，因而启用非官方的自行编写的 [Special Judge](https://www.luogu.com.cn/paste/mfhbmugl)，也可以在附件中下载。欢迎大家 hack（可私信或直接发帖）。

#### 说明

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

**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf)  _T3 Hop_。**


title: [COCI2020-2021#4] Janjetina

background:
疫情封禁期间，克罗地亚的所有餐厅均被关闭。

Malnar 先生为此十分伤感。但他不久发现并没有必要感到如此伤心，因此他决定将在封禁结束后周游克罗地亚，并在最好的餐厅中享用最美味的羊肉。

description:
Malnar 先生将访问 $n$ 个城市，分别用整数 $1$ 到 $n$ 表示。同时，他经过调研发现，有 $n-1$ 条连接其中两个城市的双向路。

每条路上均有一家提供羊肉的餐厅，同时给定每个餐厅可以订购的最大羊肉的重量。

他将选择两个城市 $x$ 和 $y$，并以最短路径（指经过的最少的路）从 $x$ 到达 $y$。他将且仅将在一家餐厅停留，且这家餐厅为可提供羊肉重量最多的一家（如果有多家这样的餐厅，他将会选择任意一家），并将订购的羊肉全部吃光。

如果通过一种长度为 $l$ 的路径可以吃到 $w$ 千克的羊肉，且 $w-l \ge k$，那么 Malnar 先生就称之为**满意的**。一种路径的长度等同于其经过路的条数。

求有多少个有序数对 $(x,y)$，使得从 $x$ 到 $y$ 的最短路径是满意的。

inputFormat:
第一行输入整数 $n,k$，其中 $n$ 表示城市的个数。

接下来的 $n-1$ 行，每行输入三个整数 $x,y,w$，表示有一条连接城市 $x,y$ 的路，且这条道路有一家提供 $w$ 千克羊肉的餐厅。

outputFormat: 输出满足题意的有序数对的个数。


title: [COCI2020-2021#4] Patkice II

description:
Netflix 的经商人员想要制作一个有关三只鸭子之旅的系列改编。

在 COCI20/21 的第一轮中，鸭子们位于一个洋流的地图中，鸭子们一同出行。鸭子们的起始岛屿用 `o` 表示。鸭子们可以往四个方向进行旅行，分别是：西 $\to$ 东（`>`），东 $\to$ 西（`<`），北 $\to$ 南（`v`） 和南 $\to$ 北（`^`）。当鸭子们位于洋流的点上时，它们将会向洋流的方向移动一个单位。

平静的海面用 `.` 表示。如果洋流把鸭子们带到了平静的海面、到达地图之外或者回到起始小岛处，它们就会停止旅行。鸭子们想要前往的目的地岛屿用 `x` 表示。

为了让情节更加吸引人，Netflix 进行了改编：现在海面上可能会出现旋涡（鸭子们可能会困在其中）和可把鸭子带到地图之外的洋流。

因此，原先地图被迫改变。但在即将到来的截止期的情况下，导演犯了几个错误：鸭子们不能再通过洋流到达目的地岛屿。

Netflix 导演是非常重要的人，因此他们并不花时间思考情节漏洞。你的任务是替换地图中的几个字符，使得鸭子们能够从起始岛屿到达目的地岛屿。

因情节需要，字符 `o` 和 `x` 不能被修改。其他字符（`<>v^.`）分别表示洋流和平静的海面。你可以用 `<>v^.` 中的任意字符来替换原先地图中 `<>v^.` 的任意字符。

inputFormat:
第一行输入两个整数 $r$ 和 $s$，分别表示地图的行数和列数。

接下来的 $r$ 行，每行包含 $s$ 个字符，字符必为 `o<>v^.x` 中的其中一个。保证地图上分别只有一个 `o` 和 `x`，并且它们不相邻。

outputFormat:
第一行输出 $k$，表示需要进行改变的字符的最少数量。

接下来的 $r$ 行，每行输出 $s$ 个字符，表示改变后的地图。

如果有多种符合题意的地图，请输出任意一种。

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

**本题采用捆绑评测，自动开启 O2 优化。**

| Subtask | 分值 | 数据范围及约定 |
| :----------: | :----------: | :----------: |
| $1$ | $30$ | $3 \le r,s \le 20$ |
| $2$ | $80$ | 无 |

对于 $100\%$ 的数据，$3 \le r,s \le 2000$。

#### 评分方式

如果一个子任务中的所有数据中，第一行均正确，那么可以得到该子任务一半的分数。

本题启用非官方的自行编写的 [Special Judge](https://www.luogu.com.cn/paste/d4nbx1ua)，也可以在附件中下载。欢迎大家 hack（可私信或直接发帖）。

#### 说明

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

**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf)  _T5 Patkice II_。**


title: [Ynoi Easy Round 2020] TEST_8

description:
给出一个长度为 $n$ 的 $01$ 串 $S$（一个由 $0$ 和 $1$ 组成的序列，下标为 $1$ 到 $n$ 的整数）。

支持以下几种操作：

操作1：给出 $l,r,k$，将 $01$ 串下标为 $l$ 到 $r$ 的一段重复 $k$ 次并放回原位；

操作2：给出 $l,r,k$，将 $01$ 串下标为 $l$ 到 $r$ 的一段带翻转地重复 $k$ 次（具体地说，第 $i$（$1\leq i\leq k$）次重复时，若 $i-1$ 的二进制表示中有奇数个 $1$，则这次重复时要左右反转，否则不变），最后放回原位；

操作3：给出 $l,r$，将 $01$ 串下标为 $l$ 到 $r$ 的一段删除；

操作4：给出 $k$，求 $01$ 串中从左到右第 $k$ 个 $1$ 的位置，若 $k$ 超过 $01$ 串中 $1$ 的个数，则输出 $-1$。

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

接下来一行，一个长度为 $n$ 的 $01$ 串。

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

接下来 $m$ 行，每行第一个整数 $op$ 表示操作类型。

若 $op=1$ 或 $op=2$，这一行接下来有三个整数 $l,r,k$。

若 $op=3$，这一行接下来有两个整数 $l,r$。

若 $op=4$，这一行接下来有一个整数 $k$。

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


title: [COCI2018-2019#1] Nadan

description:
Nadan 是一个成功的商人。他经常对软件开发者进行投资。

今年，他决定将 $K$ 库纳（克罗地亚货币）分配给 $N$ 个项目，使得每个项目能分配至少 $1$ 库纳，并且两两之间得到的数量互不相等且均为正整数。数据保证，这样的分配方式一定存在。

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

第二行输入正整数 $N$。

outputFormat: 输出共 $N$ 行，其中第 $i$ 行表示第 $i$ 个项目所分配的金额。

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

对于 $50\%$ 的数据，$N=5$。

对于 $100\%$ 的数据，$100 \le K \le 10^6$，$1 \le N \le 100$。

#### 评分方式

如果一组数据中，存在相同的分配金额，但总和正确，则可以获得该数据满分 $5$ 分中的 $3$ 分。

本题启用非官方的自行编写的 [Special Judge](https://www.luogu.com.cn/paste/g6huzk80)，也可在附件中获取。由于 Special Judge 的原因，请在输出的最后一个数字后添上一个换行符。欢迎大家 hack（可私信或直接发帖）。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #1](https://hsin.hr/coci/archive/2018_2019/contest1_tasks.pdf)  _T1 Nadan_。**


title: 「EZEC-5」暴力出奇迹

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

description:
给定一个平面，有 $n$ 个竖直线段，第 $i$ 条的端点是 $(i,a_i)$ 和 $(i,b_i)$。

有 $m$ 次查询，每次查询给定 $l,r,x,y$，查询对所有 $(x,i)$ 和 $(y,i)$ 连接成的水平线段，满足 $l\le i\le r$，其最多能与多少竖直线段相交，定义端点为 $(i,a_1)$ 和 $(i,a_2)$ 的竖直线段与端点为 $(b_1,j)$ 和 $(b_2,j)$ 的水平线段相交，当且仅当 $a_1\le j\le a_2$ 且 $b_1\le i\le b_2$，注意当线段两端点重合时，如果有其他线段经过这个重合点，仍然算作相交。

inputFormat:
第一行一个数表示 $n$。

之后 $n$ 行，第 $i$ 行两个数 $a_i,b_i$ 表示 第 $i$ 条竖直线段的两个端点，保证 $a_i \le b_i$。

之后一行一个数表示 $m$。

之后 $m$ 行，每行四个数表示一次询问的 $l,r,x,y$。

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

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

对于 $100\%$ 的数据，$1\le n\le 5\times 10^5,1\le m\le 9\times 10^5$，$1\le l,r,x,y,a_i,b_i\le n$。

---

## 以下为旧数据范围

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

对于另外 $14\%$ 的数据，$m=1$。

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

对于另外 $14\%$ 的数据，$n\leq 500$。

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

对于另外 $19\%$ 的数据，$n\leq 20000$。

对于 $100\%$ 的数据，$1\le n\le 5\times 10^4,1\le m\le 5\times 10^5$，$1\le l,r,x,y,a_i,b_i\le n$。


title: [COCI2018-2019#1] Zamjena

description:
Vlatko 喜欢与整数数组打交道。

他在纸上写下了两个分别包含 $N$ 个元素的数组，其中每个元素是一个整数，或者是表示一个变量的字符串（字符串仅包含小写字母）。

一个变量可以被任何一个整数替换，而两个数组中可能会多次出现同一变量。假如这种情况出现，则替换时需要将该变量出现过所有位置均替换会为待替换整数。

Vlatko 好奇能不能将所有变量替换为特定的整数，使得两个数组相等。当两个数组所有位置处的整数均对应相等，则两个数组相等。

inputFormat:
第一行输入正整数 $N$，表示每个数组中元素个数。

第二行输入第一个数组的 $N$ 个元素。

第三行输入第二个数组的 $N$ 个元素。

数组中的每个元素为下列二者之一：

- 一个小于 $1000$ 的正整数
- 一个长度不超过 $10$ 的仅包含小写字母的字符串，表示一个变量。

outputFormat: 如果有方案能在替换后使得两个数组相等，则输出 `DA`，否则输出 `NE`。

hint:
#### 样例 3 解释

当把 $x,y,z$ 分别替换为 $2,3,3$ 时，两个数组相等，均为 $(2,3,2,3,3)$。

#### 数据规模与约定

对于 $20\%$ 的数据，每个变量在两个数组中仅出现一次。

对于另外 $20\%$ 的数据，数组中只包含两个变量 $x,y$。

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

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #1](https://hsin.hr/coci/archive/2018_2019/contest1_tasks.pdf)  _T2 Zamjena_。**


title: [COCI2018-2019#1] Cipele

description:
在各种各样的项目上消耗经费之后，Nadan 决定为软件开发者提供高质量的鞋子。

Nadan 在地下室找到了 $N$ 只左脚鞋和 $M$ 只右脚鞋。因为它们的来源未知，因此鞋子的大小也不尽相同。

Nadan 想让你配对尽可能多的鞋子（即在所有鞋子配对完毕后不能继续配对）。每一对应当包含一只左脚鞋和一只右脚鞋。当穿上一双鞋时，应当使得鞋子的丑陋度最小化。一双鞋子的丑陋度定义为：所有配对的鞋子中，左脚和右脚大小之差的绝对值的最大值。

inputFormat:
第一行输入正整数 $N,M$，分别表示左脚鞋和右脚鞋的数量。

第二行输入 $N$ 个整数 $L_i$，表示左脚鞋的大小。

第二行输入 $M$ 个整数 $R_i$，表示右脚鞋的大小。

outputFormat: 输出所有配对方式中丑陋度的最小值。

hint:
#### 样例 2 解释

Nadan 的左脚鞋有 $4$ 只，右脚鞋有 $3$ 只，最多可以配成 $3$ 对。一种配对方式为：**39-46**，41-42，45-39，第一双的两只鞋大小之差的绝对值最大，因而丑陋度为 $7$。

一种更好的配对方式为：39-39，41-42，45-46。该配对方式的丑陋度为 $1$，为所有配对方式中，丑陋度最小的。

#### 数据规模与约定

对于 $20\%$ 的数据，$N=M$。

对于另外 $50\%$ 的数据，$N,M \le 5000$。

对于 $100\%$ 的数据，$1 \le N,M \le 10^5$，$1 \le L_i,R_i \le 10^9$。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #1](https://hsin.hr/coci/archive/2018_2019/contest1_tasks.pdf)  _T3 Cipele_。**


title: [COCI2018-2019#1] Strah

background: 任何人都会对某事感到害怕。有些怕黑，有些怕高，还有些惧怕 Vinnie Jones……

description:
Mirko 最害怕的是寻找合适的土地来种植草莓。他的土地可以用一个 $N \times M$ 的矩阵来表示。土地中有些田地适合种植草莓，而有些不适合，因为那里杂草丛生。

Mirko 正在寻找一块合适矩形。当土地中有一块矩形区域包含的所有田地均适合种植草莓，则该矩形被称为合适矩形。

Mirko 还对所有田地的潜力值感兴趣。一块田地的潜力值定义为包含该田地的合适矩形的个数。

求 Mirko 所有田地的潜力值之和。

inputFormat:
第一行输入正整数 $N,M$，表示土地的规模。

接下来的 $N$ 行，每行输入 $M$ 个字符。其中 `.` 表示该块田地适合种植草莓，而 `#` 表示不适合。

outputFormat: 输出 Mirko 所有田地的潜力值之和。


title: [COCI2018-2019#1] Teoretičar

description:
Alan 为了避免感到无聊，便让 Goran 给他出一道有趣的题目。由于他忙于准备考试，Goran 的回忆里只有一个巨大的二分图。他把二分图递给 Alan，让他用尽可能少的颜色涂满所有边，使得同种颜色的边没有公共点。

Goran 看到 Alan 的复杂方法后，决定大发慈悲，给定了一个简化版本：令 $C$ 为上述问题的答案，$X$ 为不小于 $C$ 的最小的 $2$ 的正整数次幂。仅需给出一种方案，使得颜色个数不超过 $X$。

请帮助 Alan 解决该题。

注：二分图是一种能够被分成两个集合的图，使得每条边连接的两个点都属于不同集合。

inputFormat:
第一行输入正整数 $L,R,M$，分别表示二分图其中第一个集合的点的个数、第二个集合的点的个数和边的个数。

接下来的 $M$ 行，每行输入两个正整数 $a_i,b_i$，表示第一个集合的第 $a_i$ 个点和第二个集合的第 $b_i$ 个点之间有一条边。数据保证，没有重边。

outputFormat:
第一行输出一个正整数 $K$，表示使用的颜色个数。

接下来的 $M$ 行，每行输出一个正整数 $c_i$（$1 \le c_i \le K$），表示第 $i$ 条边所用颜色。

hint:
#### 样例 2 解释

使用颜色最少个数为 $3$。然而，使用 $4$ 种颜色也是可行的。因为 $4$ 是不小于 $3$ 的最小的 $2$ 的正整数次幂。

#### 数据规模与约定

对于 $20\%$ 的数据，$L,R \le 100$。

对于另外 $20\%$ 的数据，$L,R \le 5000$。

对于 $100\%$ 的数据，$1 \le L,R \le 10^5$，$1 \le M \le 5 \times 10^5$，$1 \le a_i \le L$，$1 \le b_i \le R$。

#### 说明

**这里只选取其中具有梯度的 $10$ 个测试点进行评测，因此满分由 $130$ 调整为 $100$。**

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #1](https://hsin.hr/coci/archive/2018_2019/contest1_tasks.pdf)  _T5 Teoretičar_。**


title: 「EZEC-5」「KrOI2021」Chasse Neige 加强版

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

『我喜欢雪。』

『之前虽然讨厌寒冷，现在却是最喜欢了。』

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

description:
**本题与原题的区别是 $r$ 的范围扩大了，应该能卡掉 $O(n\log^2n)$ 的分治 FFT 做法，如果有分治 FFT 能过请联系我。同时，如果你的做法是 $O(n\log n)$ 的话，请注意常数优化。**

Rikka 给了你 $T$ 组询问，每组询问给定两个正整数 $n,k$，你需要告诉 Rikka 有多少个长度为 $n$ 的排列 $\pi$ 满足如下条件：

- $\pi_1<\pi_2$

- $\pi_{n-1}>\pi_{n}$

- 恰好存在 $k$ 个位置 $i(2\leq i\leq n-1)$ 满足 $\pi_{i-1}<\pi_{i}$ 且 $\pi_{i}>\pi_{i+1}$。

答案对 $998244353$ 取模。

inputFormat:
第一行两个整数 $T,r$，表示询问次数以及 $n$ 的值域。

接下来 $T$ 行，每行两个整数 $n,k$，意义如题意所示。

outputFormat: $T$ 行，每行一个正整数，表示答案对 $998244353$ 取模的值。


title: [COCI2018-2019#2] Preokret

description:
假如我们正在观看一场未来的球赛，比赛双方是 A 队和 B 队。我们知道两队的得分和每次得分的准确时间。在一秒内，不可能有超过一次得分。

King James 想要得到两个问题的答案：

1. 上半场总共得了多少分？（整场比赛持续 $4 \times 12$ 分钟）
2. 发生多少次反超？（一次反超定义为一支队伍在得分小于对方后，经过投球使得得分超过对方）

inputFormat:
第一行输入正整数 $A$，表示 A 队的得分。

接下来的 $A$ 行，每行输入正整数 $A_s$，表示 A 队第 $s$ 次得分的时间。

接下来的一行，输入正整数 $B$，表示 B 队的得分。

接下来的 $B$ 行，每行输入正整数 $B_s$，表示 B 队第 $s$ 次得分的时间。

outputFormat: 输出两行，每行分别输出题目描述中对应问题的答案。


title: [COCI2018-2019#2] Kocka

background: 在儿童游乐场里，编者被一个由金属横杠组成的立方体所吸引，于是他想出了一个有趣的问题。这里是二维的版本。

description:
给定一个 $N \times N$ 的矩阵。有些区域被堵塞，而有些区域是空白的。在观察的过程中，他从 $4$ 个方向对该矩阵进行观察。先从左侧开始，记录下每一行的第一个堵塞处前有几排是空出的。如果没有堵塞，则记下 $-1$。接着他如法炮制，分别从右侧、上方和下方进行观察并记录。

这样，他总共写下了 $4N$ 个数字，其中每个方位均写下了 $N$ 个数字。然而，未知的恶棍摧毁了矩阵，他所剩的只有他写下的数字。

编者想问你他写的数字是否存在错误，即是否可以通过这些数字还原出一个 $N \times N$ 的矩阵。

inputFormat:
第一行输入正整数 $N$，表示矩阵的规模。

第二行包含 $N$ 个整数 $L_i$，表示从左侧观察所记下的数字。

第三行包含 $N$ 个整数 $R_i$，表示从右侧观察所记下的数字。

第四行包含 $N$ 个整数 $U_i$，表示从上方观察所记下的数字。

第五行包含 $N$ 个整数 $D_i$，表示从下方观察所记下的数字。

outputFormat: 如果给定的数字可以还原出一个 $N \times N$ 的矩阵，则输出 `DA`，否则输出 `NE`。

hint:
#### 样例 1 解释

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

#### 数据规模与约定

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

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$-1 \le L_i,R_i,U_i,D_i \lt N$。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #2](https://hsin.hr/coci/archive/2018_2019/contest2_tasks.pdf)  _T2 Kocka_。**


title: [COCI2018-2019#2] Deblo

description:
给定一个包含 $n$ 个结点的树，其中每个结点都有一个权值。一条路径的权值定义为该路径经过的所有结点的权值异或后的结果。

你的任务是求出所有路径的权值之和。

inputFormat:
第一行输入正整数 $N$，表示树的结点个数。

第二行输入 $N$ 个用空格分隔的整数 $v_i$，第 $i$ 个整数表示结点 $i$ 的权值。

接下来的 $N-1$ 行，每行输入整数 $a_j,b_j$，表示 $a_j,b_j$ 之间有一条边。

outputFormat: 输出所有路径的权值之和。

hint:
#### 样例 1 解释

路径 $1 \to 1$ 的权值为 $1$；

路径 $1 \to 2$ 的权值为 $1⊕2=3$；

路径 $1 \to 3$ 的权值为 $1⊕2⊕3=0$；

路径 $2 \to 2$ 的权值为 $2$；

路径 $2 \to 3$ 的权值为 $2⊕3=1$；

路径 $3 \to 3$ 的权值为 $3$。

所有路径的权值之和为 $1+3+0+2+1+3=10$。

#### 数据规模与约定

对于 $30\%$ 的数据，$N \le 200$。

对于 $50\%$ 的数据，$N \le 1000$。

对于另外 $20\%$ 的数据，$x=1,2,\cdots,N-1$ 中的每个结点都和结点 $x+1$ 之间有一条边。

对于 $100\%$ 的数据，$1 \le a_j,b_j \le N \le 10^5$，$0 \le v_i \le 3 \times 10^6$。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #2](https://hsin.hr/coci/archive/2018_2019/contest2_tasks.pdf)  _T3 Deblo_。**


title: [COCI2018-2019#2] Maja

description:
蜜蜂 Maja 在一个神奇的牧场里为花朵传粉。牧场可用一个 $N \times M$ 的矩阵表示。在第 $i$ 行第 $j$ 列有 $C_{i,j}$ 朵未传粉的花。

Maja 从位于第 $A$ 行第 $B$ 列的蜂巢出发，并前往牧场的一些区域后返回。Maja 可以在 $1$ 步内从当前区域前往相邻的区域（即位于原区域的左、右、上或下方的区域），但不会离开牧场。每当 Maja 经过一个区域，它将会将该区域所有未传粉的花全部进行传粉。但牧场是神奇的！Maja 在离开区域 $(i,j)$ 后，所有传过粉的花将全部消失，而紧接着将会有 $C_{i,j}$ 朵未传粉的花重新生长。

由于 Maja 不能一直飞下去，因此它将在 $K$ 步后感到劳累。Maja 在 $K$ 步内从蜂巢出发并返回的途中，最多能为多少朵花传粉？

inputFormat:
第一行输入正整数 $N,M,A,B,K$。

接下来的 $N$ 行，每行输入 $M$ 个整数表示区域 $(i,j)$ 的花的数量 $C_{i,j}$。

蜂巢所在区域不会有任何花朵生长。

outputFormat: 输出 Maja 在 $K$ 步内从蜂巢出发并返回的途中，被传粉的花的最大数量。

hint:
#### 样例 1 解释

Maja 从 $(1,1)$ 开始，先向下飞行，为 $2$ 朵花传粉，然后再返回。

#### 样例 2 解释

Maja 从 $(1,1)$ 开始，依次向右、下、上、左飞行。由于 Maja 经过了 $(1,2)$ 两次，因而它每经过一次，便可为 $5$ 朵花传粉。

#### 数据规模与约定

对于 $40\%$ 的数据，$K \le 10^4$。

对于 $100\%$ 的数据，$2 \le N,M \le 100$，$1 \le A \le N$，$1 \le B \le M$，$2 \le K \le 10^9$，$0 \le C_{i,j} \le 10^9$，$K \bmod 2=0$。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #2](https://hsin.hr/coci/archive/2018_2019/contest2_tasks.pdf)  _T4 Maja_。**


title: [COCI2018-2019#2] Sunčanje

description:
Slavko 做了一个不寻常的梦。在一个晴朗的早上，$N$ 个白色的矩形一个接着一个爬上了 Slavko 家的屋顶，并在屋顶上晒太阳。每个矩形在屋顶都选定了一个位置，使得它的边与屋顶的棱角平行。有些矩形可能会覆盖在其它矩形所在的位置上。每个矩形的长、宽分别为 $A_i,B_i$，其与屋顶左方和下方的棱角的距离分别为 $X_i,Y_i$。

日落后，矩形们从屋顶上下来，并睡了一觉。次日，它们发现，有些矩形变成了黄色，而有些仍为白色。变为黄色的矩形都是完全暴露在阳光下的。

请判断每个矩形是否变为了黄色。

inputFormat:
第一行输入正整数 $N$，表示矩形的个数。

接下来的 $N$ 行，每行输入整数 $X_i,Y_i,A_i,B_i$。输入顺序与登上屋顶的顺序一致。

outputFormat: 输出 $N$ 行。其中，若第 $i$ 个矩形变为黄色，则在第 $i$ 行输出 `DA`，否则在该行输出 `NE`。

hint:
#### 样例 1 解释

矩形 $1,3$ 没有完全暴露在阳光下，因而它们没有变为黄色：

![](https://cdn.luogu.com.cn/upload/image_hosting/pzfz7o9i.png?x-oss-process=image/resize,m_lfit,h_320,w_362)

#### 数据规模与约定

对于 $10\%$ 的数据，$N \le 10^4$。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le X_i,Y_i \le 10^9$，$1 \le A_i,B_i \le 10^9$。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #2](https://hsin.hr/coci/archive/2018_2019/contest2_tasks.pdf)  _T5 Sunčanje_。**


title: [COCI2018-2019#3] Magnus

background:
Magnus 下国际象棋输给了 Kile，所以他开始痴迷于编程。他决定前往 COCI 竞赛试试运气。

Kile 得知 Magnus 想要参加 COCI 后，便给他出了这道热身题。

description: 给定一个长度为 $N$ 的单词。在单词中删除任意个字母，使得能够组成尽可能多的 `HONI`。

inputFormat: 输入一个长度为 $N$ 的只包含英文字母的字符串，作为给定的单词。

outputFormat: 输出能够组成的 `HONI` 的最大数量。

hint:
#### 样例 2 解释

可以将 `H`，`O`，`N`，`I` 四个字母各从原单词中删除最早出现的 $3$ 个，得到 `HONI`。

#### 数据规模与规定

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

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #3](https://hsin.hr/coci/archive/2018_2019/contest3_tasks.pdf)  _T1 Magnus_。**


title: [COCI2018-2019#3] Pismo

description:
给定一个包含 $N$ 个整数的数组 $A$。

该数组中一个区间 $[L,R]$ （$L \lt R$）的值定义为 $\max(A[L],A[L+1],\cdots,A[R])-\min(A[L],A[L+1],\cdots,A[R])$。

求该数组中所有区间值的最小值。

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

第二行输入 $N$ 个整数 $A_i$，表示数组中的数。

outputFormat: 输出所有区间值的最小值。

hint:
#### 样例 3 解释

符合题意的区间为 $[1,5]$，该区间的值为 $\max(1,2,1,2,1)-\min(1,2,1,2,1)=2-1=1$，为所有区间中值最小的。

#### 数据规模与规定

对于 $20$ 分的数据，$N \le 100$。

对于 $40$ 分的数据，$N \le 2000$。

对于 $100\%$ 的数据，$2 \le N \le 10^5$，$|A_i| \lt 10^9$。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #3](https://hsin.hr/coci/archive/2018_2019/contest3_tasks.pdf)  _T2 Pismo_。**


title: 三遣救援

background:
>就像第一块多米诺骨牌，那个人的出现开启了后面的故事。

穆罗在家里养了许多猪。在他的训练下，这些猪都十分乖巧。当然，有的时候这些猪也会变得十分调皮……

description:
一天早上，穆罗发现自己私存的一块蛋糕被偷吃了！他立即猜到某只猪吃了这块蛋糕，于是迅速赶到猪圈决定找出这只猪进行惩罚。

猪圈里有 $n$ 只猪，猪的序号是 $1$ 到 $n$ 之间的整数。除了偷吃了蛋糕的那只猪，其他所有猪**一样重**，而那只偷吃了蛋糕的猪会比其他猪**略重一些**（你可以假设原本猪是 $5\text{kg}$ 的，那只吃了蛋糕的猪是 $5.1\text{kg}$ 的）。穆罗无法肉眼判断是哪只猪吃了蛋糕。

幸运的是穆罗有一个天平，可以将猪赶上天平两侧，从而比较出哪边的猪更重。不过这个天平不是很大，每侧最多只能有 $m$ 只猪，否则天平就会损坏导致无法使用（偷吃蛋糕的猪**不会使天平一侧可放置的猪的数目减少**，即**无论猪是否偷吃，每侧都最多只能有 $m$ 只猪**）。

穆罗不想花费太多的时间，所以他希望知道在**天平不损坏**的前提下，**至少需要使用几次天平称量才能保证找出这只偷吃了的猪**。他希望你能求出这个数。

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

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

hint:
#### 样例一解释：

穆罗先让 $1$ 号猪和 $2$ 号猪分别上天平两侧，再让 $3$ 号猪和 $4$ 号猪分别上天平两侧，此时一定能找出偷吃了的猪，使用天平次数为 $2$。显然只使用一次天平无法保证能找出那只偷吃了的猪。

#### 样例三解释：

天平两侧最多都只能放两只猪，所以至少需要三次才能保证找出。

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

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

+ Subtask 1 ( $10\%$ )：$n,m\leq10$。
+ Subtask 2 ( $25\%$ )：$n,m\leq10^6$。
+ Subtask 3 ( $15\%$ )：$n\leq m$。
+ Subtask 4 ( $50\%$ )：无特殊限制。

对于所有数据，$1\leq n,m\leq10^{15}$。


title: 干杯！再会！

background:
>酒酣之时，等待你的会是……

黛米和哥哥在一个小城镇里经营着一家小酒吧。靠着哥哥调制的多夫林酒，这间小酒吧的生意也逐渐兴隆起来。

description:
这家小店有 $n$ 位常驻顾客。第 $i$ 位顾客来到这家小店时都会带上一瓶美味度为 $a_i$ 的底酒和一份美味度为 $b_i$ 的调料。这些顾客会让黛米帮忙调酒。对于一瓶美味度为 $x$ 的底酒和一份美味度为 $y$ 的调料，如果黛米将它们调制在一起，就能得到一瓶美味度为 $\gcd(x,y)$ 的美酒（我们认为美味度数值越低代表酒越好喝）。

这一天，这些顾客同时来到了这家小店想要黛米帮忙调酒。然而黛米在前一天喝了太多的酒导致意识错乱了，这导致她将调料加入到了错误的底酒里。不过好在这些顾客并不在意，他们只想知道对于**所有**黛米加入调料的情况下，他们将会拿到的酒的美味度的**方差**的**和**在对 $10^9+7$ 取模意义下是多少。如果你能回答出他们的问题，那么他们会很愿意帮你支付酒钱。

------------
#### 简要题意：
给定 $n$ 以及两个长度为 $n$ 的序列 $a,b$。对于一个 $1$ 到 $n$ 的排列 $p$，记 $c_i=\gcd(a_i,b_{p_i})$，$\sigma(c)$ 表示序列 $c$ 中所有元素的**方差**（方差公式详见提示），求：

$$\sum\limits_{p}\sigma(c)$$

对 $10^9+7$ 取模。

inputFormat:
第一行一个整数 $n$，意义如上。

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

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

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


title: 四方喝彩

background:
>念出他们的名字，让他们，再次回到舞台。

麦克要在月亮河马戏团表演全新的杂技节目了！

description:
麦克一共有 $n$ 个新节目，每个节目的惊险值为 $a_i$。

接下来麦克可以通过若干次操作来对每个节目的惊险值进行变换：

+ 麦克使用冰球，对于所有的 $l\leq i\leq r$，第 $i$ 个节目的惊险值会增加 $x$。

+ 麦克使用土球，对于所有的 $l\leq i\leq r$，第 $i$ 个节目的惊险值会乘以 $x$。

+ 麦克使用火球，对于所有的 $l\leq i\leq r$，第 $i$ 个节目的惊险值在接下来的 $x$ 个操作中**不会受到冰球和土球的影响**。火球效果**不会被替换**。

当然观众对每个节目的惊险值也很好奇，所以你需要在操作过程中帮麦克回答对于所有 $l\leq i\leq r$，第 $i$ 个节目的惊险值之和。当然观众不希望惊险值过大，所以你需要将结果对 $10^9+7$ 取模。

------------
#### 简要题意：

给你一个长度为 $n$ 的数组 $a$，你需要支持如下几个操作：

1. `l r x`：对所有 $l\leq i\leq r$，令 $a_i$ 增加 $x$。
2. `l r x`：对所有 $l\leq i\leq r$，令 $a_i$ 乘上 $x$。
3. `l r x`：对所有 $l\leq i\leq r$，在接下来的 $x$ 个操作内，$a_i$ 将会被封锁，**不会受到操作 1 和操作 2 的影响**（设本次操作为第 $k$ 次操作，则第 $k+1,k+2,\cdots,k+x$ 次操作中的所有操作 1和操作 2 不会对区间 $\left[l,r\right]$ 产生影响）。已有的封锁效果**不会被替换**（即假设第 $3$ 次有一个操作 3 对某个位置进行封锁，封锁时间为 $5$，第 $5$ 次操作同样对这个位置进行封锁，封锁时间为 $2$ 那么实际上这个位置在第 $4$ 次操作到第 $8$ 次操作的时间内都会被封锁）（感性理解就是后面时间短的封锁不会使前面时间长的封锁失效）。
4. `l r`：询问 $\sum\limits_{l\leq i\leq r}a_i$，对 $10^9+7$ 取模。

inputFormat:
第一行有两个正整数 $n,m$，分别表示数组长度和操作数。

第二行会有 $n$ 个整数 $a_i$，表示数组 $a$。

接下来 $m$ 行，每行有三个整数 $opt,l,r$ 表示操作编号以及这次操作的 $l,r$，如果 $opt\leq 3$，那么还会有一个整数 $x$，表示这次操作的 $x$。

outputFormat: 对于所有的操作 4，一行一个整数表示结果，对 $10^9+7$ 取模。

hint:
#### 样例一解释
一开始数组为 $\{1,5,4,3,6\}$。

+ 执行第 $1$ 次操作，此时数组变为 $\{1,8,7,6,6\}$。
+ 执行第 $2$ 次操作，此时数组不变。
+ 执行第 $3$ 次操作，询问结果为 $27$。
+ 执行第 $4$ 次操作，因为此时 $a_2$ 在第 $2$ 次操作中被封锁还未解除，所以这次操作只对 $a_3$ 产生影响，数组变为 $\{1,8,28,6,6\}$。
+ 执行第 $5$ 次操作，询问结果为 $37$。

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

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

+ Subtask 1 ( $25\%$ )：$n,m\leq2\times10^3$。
+ Subtask 2 ( $8\%$ )：没有操作 3。
+ Subtask 3 ( $17\%$ )：对于所有操作 4，保证 $l=r$。
+ Subtask 4 ( $50\%$ )：无特殊限制。

对于所有数据，$1\leq n,m\leq 2\times 10^5,0\leq a_i<10^9+7,1\leq l\leq r\leq n$，对于所有操作 1 和操作 2，保证 $0\leq x<10^9+7$，对于所有操作 3，设其为第 $k$ 次操作，保证 $0\leq x\leq m-k$。


title: [COCI2018-2019#3] Sajam

background:
原时限 5s，这里设为 1s，经测试正确算法可以正常通过。

Milo 组织了一场圣诞游园会。结束后，他想通过 LEET 来实现熄灯。

description:
每个区域都由 $N$ 行组成，其中每行有 $N$ 个摊位。现有 $3$ 种操作方式改变发光状态指将原来发光的灯改为熄灭，反之亦然）：

1. LEET 将选定一整行，并自动将这行所有的灯改变发光状态。
2. LEET 将选定一整列，并自动将这列所有的灯改变发光状态。
3. Milo 将选定一个摊位，并手动将该摊位的灯改变发光状态。

是否有方案使得 Milo 能在最多进行 $K$ 次操作 3 的情况下，将所有灯全部熄灭？

inputFormat:
第一行输入整数 $N,K$。

接下来的 $N$ 行，每行有 $N$ 个字符 `x` 或 `o`，表示圣诞游园会对应摊位灯的发光状态。其中 `x` 指熄灭，`o` 指发光。

outputFormat: 如果有符合题意的方案，则输出 `DA`，否则输出 `NE`。

hint:
#### 样例 3 解释

一种符合题意的方案：

- 执行操作 $2$，选定第 $1$ 列。
- 执行操作 $3$，选定 $(2,2)$。
- 执行操作 $1$，选定第 $2$ 行。
- 执行操作 $2$，选定第 $4$ 列。
- 执行操作 $3$，选定 $(3,3)$。

#### 数据规模与规定

对于 $15$ 分的数据，$K=0$。

对于另外 $15$ 分的数据，$N \le 100$。

对于另外 $30$ 分的数据，$K \lt \dfrac{N}{2}$。

对于 $100\%$ 的数据，$1 \le N \le 1000$，$0 \le K \le N$。

#### 说明

**本题分值按 COCI 原题设置，满分 $90$。这里只选取其中具有梯度的 $18$ 个测试点进行评测。**

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #3](https://hsin.hr/coci/archive/2018_2019/contest3_tasks.pdf)  _T3 Sajam_。**


title: [COCI2018-2019#3] NLO

description:
给定一个 $N \times M$ 的矩形麦田。麦田的每个区域都生长有一定量的草。所有区域的初始草量均为 $1$。

在 $K$ 天内，圆形的 UFO 将降落在麦田上并画圆。在第 $i$ 天早上，一个半径为 $R_i$ 的 UFO 将降落在区域 $(X_i,Y_i)$，并使得以该区域为圆心，$R_i$ 的半径内的所有区域将会受到影响。如果一个区域 $(x,y)$ 受到影响，且 $(X_i-x)^2+(Y_i-y)^2 \le R_i^2$，则该区域的草量将降为 $0$。在新的一天到来时，每个区域的草量都会增加 $1$。

求在第 $K$ 天晚上，所有区域的草量之和。

inputFormat:
第一行输入正整数 $N,M$，表示麦地规模。

第二行输入正整数 $K$，表示天数。

接下来的 $K$ 行中的第 $i$ 行，输入正整数 $X_i,Y_i,R_i$，表示降落的区域和 UFO 的半径。

outputFormat: 输出草的总量。


title: [COCI2018-2019#3] Praktični

description:
给定一个包含 $N$ 个结点和 $M$ 条边的无向图。每条边有一个小于 $10^9$ 的权值。

当一个环上的所有边的权值的异或和为 $0$，该环被称作好环。

可以对无向图进行若干次操作。每次操作包含下列步骤：

- 选定一个整数 $x$。
- 选定一个包含若干条边的非空集合。
- 给该集合中每条边都异或上 $x$。

请在尽可能少的操作次数之下使得无向图中的所有简单回路都是好环。请求出最少操作次数，并输出对应的操作参数。

inputFormat:
第一行输入正整数 $N,M$，分别表示结点和边的数量。

接下来的 $M$ 行中的第 $i$ 行，输入 $a_i,b_i,p_i$，分别表示第 $i$ 条边连接的结点和边的权值。保证图联通，且无重边。

outputFormat:
第一行输出 $K$，表示需要操作的最少次数。

接下来的 $K$ 行，每行输出若干个数，用空格分开：

- 第一个数为选定的数 $x$。
- 第二个数位 $B$，表示选定的边的数量。
- 接下来输出 $B$ 个数 $E_i$（$1 \le E_i \le M$），表示选定的边的序号。这 $B$ 个数必须按照从小到大的顺序输出。

输出的所有数必须小于等于 $2 \times 10^9$。

hint:
#### 样例 1 解释

图的初始和结束状态（在初始状态的基础上给前三条边的权值异或上 $12$）分别如下方左图和右图所示：

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

#### 样例 2 解释

该无向图无环，因此题意已经满足，不需要进行修改，因此最少操作次数为 $0$。

#### 数据规模与约定

对于 $20\%$ 的数据，$K=1$。

对于另外 $40\%$ 的数据，输入的所有数均小于等于 $10^6$。

对于 $100\%$ 的数据，$1 \le N,M \le 10^5$，$1 \le a_i,b_i \le N$，$a_i \neq b_i$，$0 \le p_i \le 10^9$。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #3](https://hsin.hr/coci/archive/2018_2019/contest3_tasks.pdf)  _T5 Praktični_。**


title: [NOI1998] 免费的馅饼

description:
SERKOI 最新推出了一种叫做“免费馅饼”的游戏：游戏在一个舞台上进行。舞台的宽度为 $w$ 格（从左到右依次用 $1$ 到 $w$ 编号），游戏者占一格。开始时游戏者可以站在舞台的任意位置，手里拿着一个托盘。下图为天幕的高度为 $4$ 格时某一个时刻游戏者接馅饼的情景。

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

游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动。

当馅饼在某一时刻恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。当馅饼落在一个游戏者不在的格子里时该馅饼就消失。

写一个程序，帮助我们的游戏者收集馅饼，使得所收集馅饼的分数之和最大。

inputFormat:
第一行是用空格隔开的两个正整数，分别给出了舞台的宽度 $w$ 和馅饼的个数 $n$。

接下来 $n$ 行，每一行给出了一块馅饼的信息。

由三个正整数组成，分别表示了每个馅饼落到舞台上的时刻 $t_i$，掉到舞台上的格子的编号 $p_i$，以及分值 $v_i$。

游戏开始时刻为 $0$。

输入文件中同一行相邻两项之间用一个空格隔开。

输入数据中可能存在两个馅饼的 $t_i$ 和 $p_i$ 都一样。

outputFormat: 一个数，表示游戏者获得的最大总得分。


title: [COCI2018-2019#4] Elder

description:
Nikola 在一周内看完八部哈利波特电影之后，体会到了老魔杖的威力之大。如果老魔杖目前效忠于巫师 A，而巫师 A 被巫师 B 击败，则老魔杖会开始效忠于巫师 B。

现在若干位巫师将进行 $N$ 次决斗。已知老魔杖最初效忠的巫师和 $N$ 次决斗的结果，求：

1. 在 $N$ 次决斗之后，老魔杖效忠的对象。
2. 老魔杖曾经效忠于几位巫师？

inputFormat:
第一行输入一个大写字母，表示老魔杖最初效忠的巫师。

第二行输入整数 $N$，表示决斗的次数。

接下来的 $N$ 行中的第 $i$ 行，输入两个用空格分开的大写字母 $Z_1$ 和 $Z_2$，表示第 $i$ 次决斗，巫师 $Z_1$ 击败了巫师 $Z_2$。

outputFormat:
第一行输出一个大写字母，表示问题 1 的答案。

第二行输出一个整数，表示问题 2 的答案。

hint:
#### 样例 1 解释

老魔杖最初效忠于巫师 A。第一次决斗之后，老魔杖开始效忠于 B。第二次决斗之后，老魔杖开始效忠于 C。此后的第三次对老魔杖的效忠对象无影响。

#### 数据规模与约定

对于 $100\%$ 的数据，$1 \le N \le 100$。

#### 评分方式

每组数据第一行计 $2$ 分，第二行计 $3$ 分，每组数据共 $5$ 分。如果只想获得其中一行的分数，也请在另一行随意输出一个数，否则将无法正常评判。

评分所需要借助的 Special Judge 详见附件。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #4](https://hsin.hr/coci/archive/2018_2019/contest4_tasks.pdf)  _T1 Elder_。**


title: [COCI2018-2019#4] Wand

background: Kile 看到了 Nikola 的题目之后有了灵感，便创作出了自己的版本。

description:
$N$ 位分别用 $1,2,\cdots,N$ 表示的巫师将参与 $M$ 次决斗。

现有一个魔杖。如果魔杖目前归属于巫师 A，而巫师 A 被巫师 B 击败，则魔杖将归属于巫师 B。魔杖最初归属于巫师 $1$。

Kile 想知道，在只调整决斗的顺序的条件之下，魔杖最终可能会归属于谁。

inputFormat:
第一行输入正整数 $N,M$。

接下来的 $M$ 行输入正整数 $X_i,Y_i$，表示巫师 $X_i$ 将击败巫师 $Y_i$。

outputFormat: 输出 $N$ 个字符，其中若魔杖最终可能归属于巫师 $k$，则在第 $k$ 个字符处输出 $1$，否则在此处输出 $0$。

hint:
#### 样例 1 解释

如果巫师 $1,3$ 先进行决斗，然后轮到巫师 $2,3$，魔杖将最终归属于巫师 $2$。

如果巫师 $2,3$ 先进行决斗，然后轮到巫师 $1,3$，魔杖将最终归属于巫师 $3$。

#### 数据规模与约定

对于 $20\%$ 的数据，$1 \le N,M \le 10$。

对于 $100\%$ 的数据，$1 \le N,M \le 10^5$，$1 \le X_i,Y_i \le N$，$X_i \neq Y_i$。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #4](https://hsin.hr/coci/archive/2018_2019/contest4_tasks.pdf)  _T2 Wand_。**


title: [COCI2018-2019#4] Kisik

description:
CAIN 组织决定建立为 $K$ 个家庭在火星上一个新的小镇，因此将建立 $K$ 幢楼房，每家一幢。对于每个家庭，CAIN 提供了 $N$ 种不同的楼房设计可供选择。

楼房都互相紧挨着，以便让它们底部在同一直线上。在建设之后，城市需要进行充气，并让其保存在一个玻璃墙内。玻璃墙只能围住一片矩形区域，因此充气的范围也是一个矩形区域。

求出所需最少的充气量。

inputFormat:
第一行输入整数 $N,K$。

接下来的 $N$ 行，每行输入整数 $W_i,H_i$，表示第 $i$ 幢楼房的宽度和高度。保证无重复的 $(W_i,H_i)$。

outputFormat: 输出所需最少的充气量。

hint:
#### 样例 1 解释

该方案只需 $20$ 个单位的充气量，为最少充气量：

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

#### 数据规模与约定

对于 $40$ 分的数据，$N \le 1000$。

对于 $100\%$ 的数据，$1 \le K \le N \le 10^6$，$1 \le W_i,H_i \le 10^6$。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #4](https://hsin.hr/coci/archive/2018_2019/contest4_tasks.pdf)  _T3 Kisik_。**


title: [RC-05] 迷失自我

description:
对于两个只包含 $7,9$ 的数字串 $S,T$，如果：

- $S,T$ 长度均为 $n$；
- $S$ 的字典序小于 $T$；
- 对于任意 $[l_1,r_1]$ 和 $[l_2,r_2]$（$1\le l_1\le r_1\le n$，$1\le l_2\le r_2\le n$，$l_1,r_1,l_2,r_2$ 为整数，两个区间不相同），设 $A_S$ 为将 $S$ 的第 $l_1\sim r_1$ 个字符顺次排列得到的十进制数，$A_T$ 为将 $T$ 的第 $l_1\sim r_1$ 个字符顺次排列得到的十进制数，$B_S$ 为将 $S$ 的第 $l_2\sim r_2$ 个字符顺次排列得到的十进制数，$B_T$ 为将 $T$ 的第 $l_2\sim r_2$ 个字符顺次排列得到的十进制数，有 $\gcd(A_S,B_S)=\gcd(A_T,B_T)$。

那么，就称 $(S,T)$ 是无法辨识的一对。比如，$S=7977$ 和 $T=7979$ 不是无法辨识的，因为取 $[l_1,r_1]=[1,4]$，$[l_2,r_2]=[2,2]$，则 $\gcd(A_S,B_S)=\gcd(7977,9)=3$，$\gcd(A_T,B_T)=\gcd(7979,9)=1$，有 $3\ne 1$。

求长度为 $n$ 的只含 $7,9$ 的数字串中有几对无法辨识。你只需求出答案对 $998244353$ 取模的值。

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

第一行是一个整数，为数据组数 $T$。

接下来一行，每行一个整数，为询问的 $n$。

outputFormat: $T$ 行，每行一个整数，为这组数据的答案对 $998244353$ 取模的值。


title: [COCI2018-2019#4] Slagalica

description:
Jurica 创造了一个谜图游戏，它是一个 $N$ 行 $M$ 列的平行四边形，由若干个结点组成。

谜图中，行从 $1$ 到 $N$，顺序为从下到上；列从 $1$ 到 $M$，顺序为从左到右。每个结点用 $(x,y)$ 表示，其中 $x,y$ 分别为行和列。每个结点有一个在 $[1,N \times M]$ 内的唯一的整数权值。

当谜图的第 $i$ 行从左到右的结点的权值分别为 $M(i-1)+1 \sim Mi$ 时，谜图就被认为是解开了。

当 $N=3,M=4$ 时，谜图如下图所示：

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

谜图中可以进行两种操作：

1. 选取单位大小的菱形，其中包含结点 $(x,y),(x+1,y),(x+1,y+1),(x,y+1)$，并将其顺时针旋转。

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

2. 选取单位大小的等边三角形，其中包含结点 $(x,y),(x+1,y),(x,y+1)$，并将其顺时针旋转。

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

Jurica 进行了若干次操作，将其称为一个大操作。并将该大操作（即一系列操作）重复进行了若干次，竟然将谜图解开了。

给定谜图的规模和大操作重复次数 $K$，判断是否有一种大操作，从解开的谜题开始，使得在 $K$ 次重复该大操作之后，首次再回到解开的状态。如果能解开，请输出组成大操作的操作。

inputFormat: 输入整数 $N,M,K$。

outputFormat:
如果没有符合题意的大操作，则输出 `-1`。

否则，输出任意一种符合题意的大操作，Special Judge 见附件。

若有符合题意的大操作，则在第一行输出大操作的操作次数 $B$，并在接下来的 $B$ 行以下方格式输出：

- $\texttt{R x y}$，表示调用操作 1；
- $\texttt{T x y}$，表示调用操作 2；

其中输出的 $x,y$ 为对应操作选定的坐标 $(x,y)$。

输出必须满足 $1 \le B \le 5 \times 10^5$，$1 \le X \lt N$，$1 \le y \lt M$。

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

对于 $40\%$ 的数据，$N,M \le 3$，$K \le 20$。

对于 $100\%$ 的数据，$2 \le N,M \le 100$，$2 \le K \le 10^{12}$。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #4](https://hsin.hr/coci/archive/2018_2019/contest4_tasks.pdf)  _T4 Slagalica_。**


title: 「EZEC-6」游戏

description:
Alice 和 Bob 玩游戏。

Alice 初始有 $n$ 个石子，Bob 初始有 $m$ 个石子，他们进行若干轮游戏，第 $i$ 轮游戏的输者给赢者 $i$ 个石子，当某一轮输者的石子不足时，停止游戏。

给定 $n,m$，求出游戏最多进行的轮数（不包含结束轮），并构造一个只包含 `A` 与 `B` 的胜负序列，满足该序列的长度为你的答案，并且任何时刻每个人手里的石子数非负。

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

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

对于每组数据：

一行 $2$ 个非负整数 $n,m$。

outputFormat:
对于每组数据：

第一行一个整数，表示游戏最多进行的轮数，记你的答案为 $x$；

第二行一个长度为 $x$ 的字符串，表示胜负序列。

若第 $i$ 轮 Alice 赢，则你的胜负序列的第 $i$ 位为 `A`，若第 $i$ 轮 Bob 赢，则你的胜负序列的第 $i$ 位为 `B`。

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

- Subtask 1（6 points）：$n+m\le15$。
- Subtask 2（8 points）：$n=m$。
- Subtask 3（8 points）：$\sum n+m\le10^3$。
- Subtask 4（8 points）：$\sum n+m\le2\times10^4$。
- Subtask 5（25 points）：$\sum n+m\le4\times10^5$。
- Subtask 6（45 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le10^3$，$0\le n,m\le2\times10^7$，$1\le n+m\le2\times10^7$，$\sum n+m\le2\times10^7$。

如果你答对了最多进行的轮数，而你构造的胜负序列不合法，你将得到该测试点 $20\%$ 的分数（下取整）。

注意，若你无法构造胜负序列，也请输出一个长度不为零的字符串。

**本题输出量较大，请使用较快的输出方法。**


title: 「PMOI-2」子序列

background: 看到这个时限，大家不必恐慌，本题不卡常。

description:
给你一个长度为 $n$ 的序列 $a_i$（**下标从 $1$ 开始**），你需要选出一个 $\{1,2,3,\cdots,n\}$ 的**任意长度非空**的子序列 $p$，设 $p$ 的长度为 $l$，定义 $a_0=p(0)=a_{n+1}=0,p(l+1)=n+1$，你需要最大化：

$$\sum_{i=0}^{l}(a_{p(i+1)}-a_{p(i)})(p(l-i+1)-p(l-i))$$

求出这个最大值。

若 $a$ 是 $b$ 的子序列，则从 $b$ 中删除 $0$ 或多个元素，**按照原顺序**可以得到 $a$，比如 $\{1,4\}$ 是 $\{1,2,3,4\}$ 的子序列，$\{3,1,5\}$ 是 $\{3,1,5\}$ 的子序列，$\{1,2\}$ 不是 $\{3,2,1\}$ 的子序列。

inputFormat:
第一行输入一个正整数 $n$，表示 $a$ 的长度。

第二行输入 $n$ 个整数，第 $i$ 个数表示 $a_i$。


title: [USACO21JAN] Spaced Out S

description:
Farmer John 想要拍摄一张他的奶牛吃草的照片挂在墙上。草地可以用一个 $N$ 行 $N$ 列正方形方格所组成的方阵表示（想象一个 $N \times N$ 的棋盘），其中 $2 \leq N \leq 1000$。在 Farmer John 最近拍摄的照片中，他的奶牛们太过集中于草地上的某个区域。这一次，他想要确保他的奶牛们分散在整个草地上。于是他坚持如下的规则：

 - 没有两头奶牛可以位于同一个方格。
 - 所有 $2 \times 2$ 的子矩阵（共有 $(N-1) \times (N-1)$ 个）必须包含恰好 2 头奶牛。

例如，这一放置方式是合法的：

```
CCC
...
CCC
```

而这一放置方式是不合法的，因为右下的 $2 \times 2$ 正方形区域仅包含 1 头奶牛：

```
C.C
.C.
C..
```

没有其他限制。你可以假设 Farmer John 有无限多的奶牛（根据以往的经验，这种假设似乎是正确的……）。

Farmer John 更希望某些方格中包含奶牛。具体地说，他相信如果方格 $(i, j)$ 中放有一头奶牛，照片的美丽度会增加 $a_{ij}$（$0 \leq a_{ij} \leq 1000$）单位。

求合法的奶牛放置方式的最大总美丽度。

inputFormat: 输入的第一行包含 $N$。以下 $N$ 行每行包含 $N$ 个整数。从上到下第 $i$ 行的第 $j$ 个整数为 $a_{ij}$ 的值。

outputFormat: 输出一个整数，为得到的照片的最大美丽度。

hint:
在这个样例中，最大美丽度可以在如下放置方式时达到：

```
CC..
..CC
CC..
..CC
```

这种放置方式的美丽度为 $3 + 3 + 3 + 1 + 3 + 3 + 3 + 3 = 22$。

测试点性质：

 - 测试点 2-4 满足 $N \le 4$。
 - 测试点 5-10 满足 $N\le 10$。
 - 测试点 11-20 满足 $N \le 1000$。

供题：Hankai Zhang，Danny Mittal


title: [USACO21JAN] No Time to Paint S

description:
Bessie 最近收到了一套颜料，她想要给她的牧草地一端的栅栏上色。栅栏由 $N$ 个 1 米长的小段组成（$1≤N≤10^5$）。Bessie 可以使用 26 种不同的颜色，她将这些颜色由浅到深用字母 'A' 到 'Z' 标号（'A' 是很浅的颜色，'Z' 是很深的颜色）。从而她可以用一个长为 $N$ 且每个字符均为字母的字符串来描述她想要给栅栏的每一小段涂上的颜色。

初始时，所有栅栏小段均未被上色。Bessie 一笔可以给任意连续若干小段涂上同一种颜色，只要她不会在较深的颜色之上涂上较浅的颜色（她只能用较深的颜色覆盖较浅的颜色）。

例如，一段长为 4 的未被涂色的栅栏可以按如下方式上色：

`.... -> BBB. -> BBLL -> BQQL`

由于时间紧迫，Bessie 认为她可能需要放弃为栅栏上某个连续的区间上色！现在，她正在考虑 $Q$ 个候选的区间（$1≤Q≤10^5$），每个区间用满足 $1≤a≤b≤N$ 的两个整数 $(a,b)$ 表示，为需要不上色的小段 $a…b$ 的两端点位置。

对于每个候选区间，将所有区间外的栅栏小段都涂上所希望的颜色，并且区间内的栅栏小段均不涂色，最少需要涂多少笔？注意在这个过程中 Bessie 并没有真正进行任何的涂色，所以对于每个候选区间的回答是独立的。

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

下一行包含一个长为 $N$ 的字符串，表示每个栅栏小段所希望的颜色。

以下 $Q$ 行，每行包含两个空格分隔的整数 $a$ 和 $b$，表示一个不涂色的候选区间。

outputFormat: 对于 $Q$ 个候选区间的每一个，输出一行，包含答案。

hint:
在这个样例种，除去目标颜色 `BAAB` 所对应的区间，涂上颜色需要四笔，而除去 `ABBA` 仅需三笔。

`.... -> AA.. -> ABBB -> ABCB`

#### 测试点性质：

 - 测试点 1-4 满足 $N,Q≤100$。
 - 测试点 5-7 满足 $N,Q≤5000$。
 - 测试点 8-13 没有额外限制。

供题：Andi Qu，Brian Dean


title: [USACO21JAN] Dance Mooves S

description:
Farmer John 的奶牛们正在炫耀她们的最新舞步！

最初，所有的 $N$ 头奶牛（$2≤N≤10^5$）站成一行，奶牛 $i$ 排在其中第 $i$ 位。舞步序列给定为 $K$ （$1≤K≤2\times10^5$）个位置对 $(a_1,b_1),(a_2,b_2),…,(a_K,b_K)$。在舞蹈的第 $i=1…K$ 分钟，位置 $a_i$ 与 $b_i$ 上的奶牛交换位置。同样的 $K$ 次交换在第 $K+1…2K$ 分钟发生，在第 $2K+1…3K$ 分钟再次发生，以此类推，无限循环。换言之，

 - 在第 $1$ 分钟，位置 $a_1$ 与 $b_1$ 上的奶牛交换位置。
 - 在第 $2$ 分钟，位置 $a_2$ 与 $b_2$ 上的奶牛交换位置。
 - ……
 - 在第 $K$ 分钟，位置 $a_K$ 与 $b_K$ 上的奶牛交换位置。
 - 在第 $K+1$ 分钟，位置 $a_1$ 与 $b_1$ 上的奶牛交换位置。
 - 在第 $K+2$ 分钟，位置 $a_2$ 与 $b_2$ 上的奶牛交换位置。
 - 以此类推……

对于每头奶牛，求她在队伍中会占据的不同的位置数量。

inputFormat: 输入的第一行包含 $N$、$K$。以下 $K$ 行分别包含 $(a_1,b_1)…(a_K,b_K)$（$1≤a_i<b_i≤N$）。

outputFormat: 输出 $N$ 行，第 $i$ 行包含奶牛 $i$ 可以到达的不同的位置数量。


title: [USACO21JAN] Dance Mooves G

description:
Farmer John 的奶牛们正在炫耀她们的最新舞步！

最初，所有的 $N$ 头奶牛（$2≤N≤10^5$）站成一行，奶牛 $i$ 排在其中第 $i$ 位。舞步序列给定为 $K$ （$1≤K≤2\times10^5$）个位置对 $(a_1,b_1),(a_2,b_2),…,(a_K,b_K)$。在舞蹈的第 $i=1…K$ 分钟，位置 $a_i$ 与 $b_i$ 上的奶牛交换位置。同样的 $K$ 次交换在第 $K+1…2K$ 分钟发生，在第 $2K+1…3K$ 分钟再次发生，以此类推，周期性地持续共 $M$ 分钟（$1≤M≤10^{18}$）。换言之，

 - 在第 $1$ 分钟，位置 $a_1$ 与 $b_1$ 上的奶牛交换位置。
 - 在第 $2$ 分钟，位置 $a_2$ 与 $b_2$ 上的奶牛交换位置。
 - ……
 - 在第 $K$ 分钟，位置 $a_K$ 与 $b_K$ 上的奶牛交换位置。
 - 在第 $K+1$ 分钟，位置 $a_1$ 与 $b_1$ 上的奶牛交换位置。
 - 在第 $K+2$ 分钟，位置 $a_2$ 与 $b_2$ 上的奶牛交换位置。
 - 以此类推……

对于每头奶牛，求她在队伍中会占据的不同的位置数量。

注意：本题每个测试点的时间限制为默认限制的两倍。

inputFormat: 输入的第一行包含 $N$、$K$ 和 $M$。以下 $K$ 行分别包含 $(a_1,b_1)…(a_K,b_K)$（$1≤a_i<b_i≤N$）。

outputFormat: 输出 $N$ 行，第 $i$ 行包含奶牛 $i$ 可以到达的不同的位置数量。


title: [USACO21JAN] Telephone G

description:
Farmer John 的 N 头奶牛，编号为 $1…N$，站成一行（$1≤N≤5⋅10^4$）。第 $i$ 头奶牛的品种编号为 $b_i$，范围为 $1…K$，其中 $1≤K≤50$。奶牛们需要你帮助求出如何最优地从奶牛 $1$ 传输一条信息到奶牛 $N$。

从奶牛 $i$ 传输信息到奶牛 $j$ 花费时间 $|i−j|$。然而，不是所有品种的奶牛都愿意互相交谈，如一个 $K×K$ 的方阵 $S$ 所表示，其中如果一头品种 $i$ 的奶牛愿意传输一条信息给一头品种 $j$ 的奶牛，那么 $S_{ij}=1$，否则为 $0$。不保证 $S_{ij}=S_{ji}$，并且如果品种 $i$ 的奶牛之间不愿意互相交流时可以有 $S_{ii}=0$。

请求出传输信息所需的最小时间。

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

下一行包含 $N$ 个空格分隔的整数 $b_1,b_2,…,b_N$。

以下 $K$ 行描述了方阵 $S$。每行包含一个由 $K$ 个二进制位组成的字符串，从上往下第 $i$ 个字符串的第 $j$ 位为 $S_{ij}$。

outputFormat: 输出一个整数，为需要的最小时间。如果不可能从奶牛 $1$ 传输信息至奶牛 $N$，输出 $−1$。

hint:
最优传输序列为 $1→4→3→5$。总时间为 $|1−4|+|4−3|+|3−5|=6$。

#### 测试点性质：

 - 测试点 1-5 满足 $N≤1000$。
 - 测试点 6-13 没有额外限制。

供题：Dhruv Rohatgi


title: [USACO21JAN] Uddered but not Herd G

description:
一个鲜为人知的事实是，奶牛拥有自己的文字：「牛文」。牛文由 26 个字母 'a' 到 'z' 组成，但是当奶牛说牛文时，可能与我们所熟悉的 'abcdefghijklmnopqrstuvwxyz' 不同，她会按某种特定的顺序排列字母。

为了打发时间，Bessie 的表妹 Mildred 在反复哼唱牛文字母歌，而 Farmer Nhoj 好奇她唱了多少遍。

给定一个小写字母组成的字符串，为 Farmer Nhoj 听到 Mildred 唱的字母，计算 Mildred 至少唱了几遍完整的牛文字母歌，使得 Farmer Nhoj 能够听到给定的字符串。Farmer Nhoj 并不始终注意 Mildred 所唱的内容，所以他可能会漏听 Mildred 唱过的一些字母。给定的字符串仅包含他记得他所听到的字母。

注意：本题每个测试点的时间限制为默认限制的两倍。

inputFormat: 输入仅一行，包含一个小写字母组成的字符串，为 Farmer Nhoj 听到 Mildred 唱的字母。字符串的长度不小于 $1$ 且不大于 $10^5$。

outputFormat: 输出 Mildred 所唱的完整的牛文字母歌的最小次数。

hint:
Mildred 至少唱了三遍牛文字母歌。有可能 Mildred 只唱了三遍牛文字母歌，如果牛文字母表以 "mildre" 开头，并且 Farmer Nhoj 听到了以下被标记为大写的字母。

```
MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyz
```

#### 测试点性质：

 - 测试点 1-5 中，Farmer Nhoj 仅听到出现在 Mildred 或 Bessie 的名字中的字母。
 - 测试点 6-16 中，Farmer Nhoj 从未听到任何出现在 Mildred 名字中的字母。

供题：Nick Wu，Brian Dean


title: [USACO21JAN] Paint by Letters P

description:
Bessie 最近收到了一套颜料。画布可以用一个 $N×M$ 的矩形方阵表示，其中行从上往下编号为 $1…N$，列从左往右编号为 $1…M$（$1≤N,M≤1000$）。被涂色的方格的颜色可以用一个 `A` 到 `Z` 的大写字母表示。初始时，所有方格均未被涂色，每个方格至多只能被涂色一次。

Bessie 指定了每个方格她所希望的颜色。她一笔可以将一些组成连通分量的方格涂上颜色，也就是说这些方格之间可以通过相邻方格互相到达。如果两个方格有公共边则认为它们是相邻的。

例如，$3×3$ 的画布

```
AAB
BBA
BBB
```

可以用如下四笔完成涂色：

```
...    ..B    AAB    AAB    AAB
... -> ... -> ... -> BB. -> BBA
...    ...    ...    BBB    BBB
```

使用少于四笔不可能得到最终结果。

作为一名先锋派艺术家，Bessie 只会对这个画布中的一个子矩形进行涂色。现在，她正在考虑 $Q$
个候选子矩形（$1≤Q≤1000$），每一候选给定四个整数 $x_1$、$y_1$、$x_2$ 和 $y_2$，表示由第 $x_1$ 行到第 $x_2$ 行及第 $y_1$ 列到第 $y_2$ 列的所有方格组成的子矩形。

对于每个候选子矩形，将所有子矩形内的方格都涂上所希望的颜色，并且子矩形外的方格均不涂色，最少需要涂多少笔？注意在这个过程中 Bessie 并没有真正进行任何的涂色，所以对于每个候选的回答是独立的。

注意：本题每个测试点的时间限制为默认限制的 1.5 倍，且内存限制为默认限制的 2 倍，为 512MB。

inputFormat:
输入的第一行包含 $N$、$M$ 和 $Q$。

以下 $N$ 行每行包含一个由 $M$ 个大写字母组成的字符串，表示画布每行所希望的颜色。

以下 $Q$ 行每行包含四个空格分隔的整数 $x_1,y_1,x_2,y_2$，表示一个候选子矩形（$1≤x_1≤x_2≤N$, $1≤y_1≤y_2≤M$）。

outputFormat: 对于 $Q$ 个候选子矩形的每一个，输出一行，包含答案。

hint:
#### 样例 1 解释

第一个候选由整个画布组成，可以用六笔完成涂色。

第二个候选的子矩形所希望的颜色为

```
ABBA
```

可以用三笔完成涂色。注意，尽管在考虑整个画布时方格 $(3,5)$ 和 $(3,8)$ 可以用一笔涂上颜色 $A$，但如果仅考虑子矩形内的方格则并非如此。

#### 测试点性质：

 - 测试点 1-2 满足 $N,M≤50$。
 - 测试点 3-5 中，画布不包含由单一颜色所组成的环。也就是说，不存在由不同方格所组成的序列 $c_1,c_2,c_3,…,c_k$ 满足以下条件：
   - $k>2$
   - 所有的 $c_1,…,c_k$ 颜色相同。
   - 对于所有的 $1≤i<k$，$c_i$ 与 $c_i+1$ 相邻。
   - $c_k$ 与 $c_1$ 相邻。
   注意，问题描述中的 3×3 画布包含单一颜色所组成的环（左下角的四个 B）。
 - 测试点 6-8 中，每个由相同期望颜色的方格组成的连通分量均能够被一个四边平行于坐标轴的两行两列的正方形所包含。问题描述中的 $3×3$ 画布不符合这一性质（由五个 B 组成的连通分量不能被一个两行两列的正方形包含）。
 - 测试点 9-11 中，每个由相同期望颜色的方格组成的连通分量均能够被一个四边平行于坐标轴的三行三列的正方形所包含。问题描述中的 $3×3$ 画布符合这一性质。
 - 测试点 12-20 没有额外限制。

供题：Andi Qu


title: [USACO21JAN] Minimum Cost Paths P

description:
Farmer John 的牧草地可以看作是一个$N×M$（$2≤N≤10^9, 2≤M≤2⋅10^5$）的正方形方格组成的二维方阵（想象一个巨大的棋盘）。对于 $x∈[1,N],y∈[1,M]$，从上往下第 $x$ 行、从左往右第 $y$ 列的方格记为 $(x,y)$。此外，对于每一个 $y∈[1,M]$，第 $y$ 列拥有一个代价 $c_y$（$1≤c_y≤10^9$）。

Bessie 从方格 $(1,1)$ 出发。如果她现在位于方格 $(x,y)$，则她可以执行以下操作之一：

-  如果 $y<M$，Bessie 可以以 $x^2$ 的代价移动到下一列（$y$ 增加一）。
- 如果 $x<N$，Bessie 可以以 $c_y$ 的代价移动到下一行（$x$ 增加一）。

给定 $Q$（$1≤Q≤2⋅10^5$）个独立的询问，每个询问给定 $(x_i,y_i)$（$x_i∈[1,N],y_i∈[1,M]$），计算 Bessie 从 $(1,1)$ 移动到 $(x_i,y_i)$ 的最小总代价。

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

第二行包含 $M$ 个空格分隔的整数 $c_1,c_2,…,c_M$。

第三行包含 $Q$。

最后 $Q$ 行每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。

outputFormat:
输出 $Q$ 行，为每个询问的答案。

注意本题计算中所使用的整数大小可能需要使用 64 位整数型（例如，C/C++ 中的 long long）。


title: [USACO21JAN] Sum of Distances P

description: Bessie 有一些无向连通图 $G_1,G_2,…,G_K$（$2≤K≤5⋅10^4$）。对于每一个 $1≤i≤K$，$G_i$ 有 $N_i$（$N_i≥2$）个编号为 $1…N_i$ 的结点与 $M_i$（$M_i≥N_i−1$）条边。$G_i$ 可能含有自环，但同一对结点之间不会存在多条边。 现在 Elsie 用 $N_1⋅N_2⋯N_K$ 个结点建立了一个新的无向图 $G$，每个结点用一个 $K$ 元组 $(j_1,j_2,…,j_K)$ 标号，其中 $1≤j_i≤N_i$。若对于所有的 $1≤i≤K$，$j_i$ 与 $k_i$ 在 $G_i$ 中连有一条边，则在 $G$ 中结点 $(j_1,j_2,…,j_K)$ 和 $(k_1,k_2,…,k_K)$ 之间连有一条边。 定义 $G$ 中位于同一连通分量的两个结点的 *距离* 为从一个结点到另一个结点的路径上的最小边数。计算 $G$ 中结点 $(1,1,…,1)$ 与所有与其在同一连通分量的结点的距离之和，对 $10^9+7$ 取模。

inputFormat:
输入的第一行包含 $K$，为图的数量。

每个图的描述的第一行包含 $N_i$ 和 $M_i$，以下是 $M_i$ 条边。

为提高可读性，相邻的图之间用一个空行隔开。输入保证 $∑N_i≤10^5$ 以及 $∑M_i≤2⋅10^5$。

outputFormat: 输出结点 $(1,1,…,1)$ 与所有该结点可以到达的结点的距离之和，对 $10^9+7$ 取模。


title: 「RdOI R2」数(number)

description:
试求出两两不同的三个正整数 $x,y,z(x\gt y\gt z)$ 使得其中的任意两个数的和能被第三个数整除。

现在给出你下面的几种要求：

- 给出你 $x-y$ 的值，求出 $x,y,z$。
- 给出你 $x-z$ 的值，求出 $x,y,z$。
- 给出你 $y-z$ 的值，求出 $x,y,z$。

inputFormat:
一共 $T+1$ 行。

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

接下来 $T$ 行，每行两个内容：

1. 一个字符串，可能是 $x-y,x-z,y-z$ 表示给出的数是由哪两个数做差得到的。
2. 一个数，这个差的值。

outputFormat:
一共 $T$ 行。

每一行三个正整数 $x,y,z$（如上文所述）。题目保证有解。


title: 「EZEC-8」游戏蛇

description:
小 A 和小 B 是两条蛇，他们正在一棵特殊的树上做游戏。

这棵树的结构如下：首先有一条长度为 $n$ 的链，称为“主链”。主链由 $1$ 至 $n$ 这 $n$ 个节点构成。在主链上，编号相邻的点有边相连，否则则没有。

主链上的每一个点都挂着一条链，称为“副链”。主链上的第 $i$ 个点挂的副链长度（链上的点数）为 $x_i$。

小 A 和小 B 初始时都在主链上，具体而言，小 A 的**蛇尾**在点 $a$，**蛇头**在点 $b$，小 B 的**蛇头**在点 $c$，**蛇尾**在点 $d$。满足 $1\le a<b<c<d\le n$。

他们的游戏规则如下：
- 小 A 和小 B 轮流移动，小 A 先手。
- 每条蛇移动时，他会尝试整体向某一方向移动一个节点，**但不能向原来蛇尾方向移动，也就是蛇不能倒退**。需满足移动后蛇头不得与另外一条蛇的任意部分重合。
- 当一条蛇无法移动时，游戏结束，对手获胜。

现在有 $q$ 次询问，每次询问给定 $a,b,c,d$，请求出当两条蛇都采取最优策略时，哪一条蛇会获胜。

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

第二行 $n$ 个正整数，表示 $x_i$。

接下来 $q$ 行，每行四个正整数表示此次询问的 $a,b,c,d$。

outputFormat:
输出共 $q$ 行。

对于每组询问，输出 `A` 或 `B`，表示最终能获胜的蛇。

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

-  Subtask 1（10 points）：$n,q \le500$。
-  Subtask 2（10 points）：$n\le10^5$，$q\le500$。
-  Subtask 3（5 points）：所有 $x_i$ 都相等。
-  Subtask 4（10 points）：所有询问中小 A 和小 B 的长度总和不超过 $5\times10^7$。
-  Subtask 5（15 points）：$x_i$ 在 $[1,10^9]$ 内随机生成。
-  Subtask 6（20 points）：$n\le5\times10^3$。
-  Subtask 7（30 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le n,q\le5\times10^5$，$1\le x_i\le10^9$，$1\le a<b<c<d\le n$。

小 A 的长度定义为 $b-a+1$，小 B 的长度定义为 $d-c+1$。


title: 「TOCO Round 1」History

description:
这里有一棵 $n$ 个结点根为 $1$ 号结点的树，每个结点上都有一盏灯，初始状态都是关闭。现在有 $m$ 次事件发生，有以下几种情况：

`1 x` 将 $x$ 位置上的灯打开或关闭（原来如果打开就关闭，否则打开）。

`2 x y` 询问树上与 $x$ 相同深度的点中与 $x$ 结点距离为 $y$ 的点中开着的灯的个数。

`3 x` 回到第 $x$ 次事件发生之后的状态。

对于每个 $2$ 询问请给出回答。

inputFormat:
第一行一个数 $n$ 。
接下来 $n-1$ 行每行两个数 $u,v$ 表示 $u$ 与 $v$ 之间一条边。接下来一个数 $m$，下面的 $m$ 行每行二或三个数表示事件的发生。

outputFormat: 对于每次 $2$ 询问，给出答案。

hint:
**本题采用打包测评。**

* Subtask 1（10 pts）：满足所有询问中 $y \bmod 2=1$。

* Subtask 2（20 pts）：$n,m\leq 10$。

* Subtask 3（30 pts）：$n,m\leq 10^3$。

* Subtask 4（40 pts）：$n,m\leq 10^5$。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$3$ 操作保证 $0 \leq x$。


title: 「小窝 R3」心の記憶

background:
> 淡い夕暮れ飲み込まれて
「君」の消えかけて姿を
忘れさせるように走ってた
新しい平和の世界に
——[《心の記憶》](https://music.163.com/song?id=1847928316)

description:
- 本题中「**子串**」的定义如下：

字符串 $S$ 的子串是 $S$ 中**连续**的任意个字符组成的字符串。$S$ 的子串可用起始位置 $l$ 与终止位置 $r$ 来表示，记为 $S(l,r)$（$1 \leq l \leq r \leq |S |,|S|$ 表示 $S$ 的长度）。

- 本题中「**子序列**」的定义如下：

对于字符串 $S$ 和一个长度为 $n$ 的严格单调递增数列 $k_1,k_2,\cdots,k_n(\forall 1\le i\le n,1\le k_i\le |S|)$，$S_{k_1},S_{k_2},\cdots,S_{k_n}$ 所组成的字符串即为 $S$ 的子序列。

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

现有 $T$ 次询问。
每次询问给定一个长度为 $n$ 的 01 串，记为 $A$。回答应是一个字符串 $B$，满足：

- $B$ 是长度为 $m$ 的 01 串。
- $B$ 中不存在任意一个**子串**与 $A$ 相同。
- $B$ 中存在**至少**一个**子序列**与 $A$ 相同。

输出任意一个满足要求的字符串 $B$ 即可。

inputFormat:
第一行，一个正整数：$T$，表示询问次数。

对于每一次询问，第一行两个正整数： $n,m(n\le m)$，分别表示 01 串 $A,B$ 的长度。

第二行，一个长度为 $n$ 的 01 串 $A$。

outputFormat: 共 $T$ 行，每行一个长度为 $m$ 的 01 串 $B$。无解则输出 `-1`。


title: 「PMOI-2」拆分

background:
### 如果您不看样例解释中的提示，那么您极可能做不出来！

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

description:
lhm 手中有一个字符串 $a$ 和它的子串 $b$，现你需要拆分字符串 $a$。

设 $c(s,b)$ 表示从字符串 $s$ 中选出一些互不重叠的、与 $b$ 相同的子串的最大子串数量。

若将 $a$ 拆分为 $k$ 组，第 $i$ 组记为 $p_i$，你需要保证：
- $k \geq 2$，
- $c(p_{i+1},b)>c(p_i,b)\ (i \in[1,k-1])$，
- $c(p_1,b)\geq 1$。

两种拆分方案不同当且仅当拆分出的组数不等或 $\exist i$，对应的 $c(p_i,b)$ 不等。

求不同的拆分方案总数，答案对 $899678209$ 取模。

inputFormat:
输入数据共两行。

第一行一个字符串 $a$，含义如题所示。

第二行一个字符串 $b$，含义如题所示。

outputFormat:
输出数据共一行。

一行一个整数，表示拆分的方案数对 $899678209$ 取模的结果。

hint:
【样例解释】

拆分的方式分别为：

`noi noinonoi noiionoinoinoionoi`，个数分别为 $1,2,5$。

`noi noinonoin oiionoinoinoionoi`，个数分别为 $1,2,4$。

`noino inonoinoiion oinoinoionoi`，个数分别为 $1,2,3$。

`noi noinonoinoi ionoinoinoionoi`，个数分别为 $1,3,4$。

`noi noinonoinoiionoinoinoionoi`，个数分别为 $1,7$。

`noinoi nonoinoiionoinoinoionoi`，个数分别为 $2,6$。

`noinoinonoi noiionoinoinoionoi`，个数分别为 $3,5$。

`noin oinonoinoiionoinoinoionoi`，个数分别为 $1,6$。

`noinoinono inoiionoinoinoionoi`，个数分别为 $2,5$。

`noinoinonoin oiionoinoinoionoi`，个数分别为 $3,4$。

**提示：样例解释足以说明可以拆分子串**。

【数据规模与约定】

请仔细阅读本栏。

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

设 $n = c(a,b)$，$|a|=l_1$，$|b|=l_2$。

| Subtask | 特殊性质 | 空间限制 | 分值 |
| :----------: | :----------: | :----------: | :----------: |
| 1 | $l_1\leq 30$ | 256MiB | 9 |
| 2 | $n \le 300$ | 256MiB | 11 |
| 3 | $n \le 2000$ | 256MiB | 17 |
| 4 | $n \le 25000$ | 256MiB | 37 |
| 5 | 无 | 64MiB | 26 |

对于 $100\%$ 的数据，$0\le n\le2\times10^5$，$2\le l_2\le l_1\le10^6$，$b_1 \neq b_{l_2}$，$a$ 和 $b$ 只包含小写字母。


title: [JSOI2010] 挖宝藏

description:
JP 不好好训练，又喜欢上了另一个游戏——寻宝。

游戏里有 $n$ 处宝藏，它们被埋在一个无限大的二维网格中。每个宝藏都有价值 $P_i$，位置是 $(x_i,y_i)$。

如果网格 $(x,y)$ 满足下面两个条件之一，则它是可挖掘的：

- $y=-1$。

- $(x-1,y+1),(x,y+1),(x+1,y+1)$ 这三个方格都已经被挖掘了。

挖掘一个方格的代价为 $1$。当一个宝藏被挖掘出来时，就认为已经获得了它的价值。请你帮 JP 求出所能得到的最大利润，也即价值减代价。（可能一个宝藏也不挖，利润为 $0$）

inputFormat:
第一行为 $n$，表示宝藏数量。

接下来 $n$ 行，每行三个整数 $x_i,y_i,P_i$ 表示宝藏的位置和价值。

outputFormat: 一行一个整数，表示最大利润。

hint:
### 样例解释 1

挖 $1,2,4,5$ 号宝藏，价值为 $8$，花费代价为 $4$，所以利润为 $4$。可以证明没有更优的方案。

### 数据范围

对于 $30\%$ 的数据，$n\leq 15$。

对于 $50\%$ 的数据，$-10^3\leq y_i\leq 0$。

对于 $100\%$ 的数据，$n\leq 10^3,-10^4\leq x_i\leq 10^4,-10^4\leq y_i<0,1\leq P_i\leq 10^6$。


title: [JSOI2010] 游戏

description:
JSOI 集训队的小 L，小 H，小 X 在紧张的训练之余，总是喜欢玩一个称之为“取数”的游戏来调节自己：

这是一个人玩的游戏，仅仅需要一张白纸和一支笔。玩家在纸上随机写下一行共 $n$ 个整数，形成一个数列，就可以开始游戏了。

每次玩家从原数列最左端或最右端选择一个数，将它从原数列中划去，并写在下一行。当原数列的数全部被划去后，在第二行就出现了一个新的长度为 $n$ 的数列，记为 $S$。将按照如下方式计算数列 $S$ 的分数 $P$：

$$P=S_1\times 5^0+S_2\times 5^1+\cdots+S_n\times 5^{n-1}$$

算出分数 $P$ 后，将其转为二进制表示，如果末三位数字是  $011$ 的话，玩家就取得了游戏的胜利，否则就失败了。

在玩了很多次这个游戏后，小 L，小 H，小 X 发现一个重要的事实：对于某些随机写下的数列，是无论如何也无法取得游戏胜利的，这样的数列被称为“刁列”，其它的数列则被
称为“良列”。

这个游戏虽然趣味性极强，但有一个弊端：每次游戏前需要花很多时间来写出这个随机数列，这一点一直深深困扰着小 L，小 H 和小 X。

直到在今年省选前的那天晚上，小 L 想出了一个惊为天人的创意，一举攻克了这个难题：他们先在纸上画出一颗庞大的无根树（共 $m$ 个结点），每个结点上写下一个整数。当想要玩游戏时，玩家只需随便选择两个结点，通过找出连接这两个结点的那条唯一的路径，将路径上所有结点（包括两个端点）上标注的整数按路径的顺序列出来，就得到了一个数列，然后就可以在这个数列上玩游戏了。如果选择的两个端点分别是树上结点 $v_i$ 和结点 $v_j$，得到的数列就简记为 $i\sim j$。当然，如前所述，$i\sim j$ 这个数列也有“良列”和“刁列”两种可能。

他们发现这样改进以后真的方便了很多！不仅如此，还给游戏带来了一些新的趣味。比如小 X 就声称他发现了一个重要的规律：数列的属性是具有传递性的，即：对于任意互不相同的 $i,j,k$ 有：

- 如果 $i\sim j$ 是良列，$j\sim k$ 是良列，则 $i\sim k$ 是良列。

- 如果 $i\sim j$ 是刁列或 $j\sim k$ 是刁列，则 $i\sim k$ 是刁列。

这个结论出奇地优美，但很快就被小 H 找到了反例，这让小 X 心情沮丧。小 L 为了安慰小 X，说：不如我们来看看你这个结论在多少情况下是成立的吧。

小 X 振作了起来，大家一起投入了繁重的工作中。他们要找出存在多少个三元组 $(i,j,k)$，其中 $i<j<k$，使得 $i,j,k$ 满足小 X 发现的传递性结论。

inputFormat:
第一行一个整数 $m$，代表无根树的节点个数。

接下来 $m$ 行，每行两个整数 $f_i,x_i$，其中 $f_i<i$。$f_i$ 表示节点 $v_i$ 的父节点编号，如果 $f_i=0$ 则该节点为根，$x_i$ 表示节点 $v_i$ 上写的数。

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

hint:
### 数据范围

对于 $10\%$ 的数据，$1\leq m\leq 5$。

对于 $30\%$ 的数据，$1\leq m\leq 100$。

对于 $50\%$ 的数据，$1\leq m\leq 10^3$。

对于 $100\%$ 的数据，$1\leq m\leq 10^5$。


title: [JSOI2013] 哈利波特与死亡圣器

description:
伏地魔的黑暗势力控制了魔法部与霍格沃茨魔法学校之后，哈利与罗恩、赫敏不得不逃亡在外，隐形遁迹。为了完成校长邓布利多的遗命，一直在暗中寻机销毁伏地魔魂器的哈利，意外地获悉如果他们能够拥有传说中的三件死亡圣器，伏地魔将必死无疑。

在凤凰社成员的帮助下，哈利一行人重新掌控了霍格沃茨。然而此举激怒了伏地魔，他很快率领大批食死徒和黑暗生物向霍格沃茨进军。麦格教授紧急疏散了霍格沃茨的学生，并开始了守卫霍格沃茨的战斗。

霍格沃茨魔法学校的主要建筑共有 $n$ 处，我们编号为 $1$ 到 $n$，这些建筑间由魔法道路连接，整体呈树状分布，即任意两个建筑间有且仅有一条路径相连（路径可以是一条或多条道路组成）。霍格沃茨历经多年风雨，每个建筑自身有许多保护魔法，比如“石墩触动咒”、“降敌陷阱咒”、“统统加护咒”等，只需有人前往施用咒语即能保卫建筑。

现在，伏地魔大军已经到达 $1$ 号建筑——学校大门，凤凰社成员也已经在大门迎战，并且已经启用了大门的保护魔法。然而伏地魔大军势力壮大，保护魔法只能延缓大军的进攻锋芒，他们仍能用一个小时攻克一个建筑，随后整个大军便随机前往与之相邻的另一个建筑（兵贵神速，大军移动过程不需要时间；兵法无常，他们有可能前往已经攻克的建筑）。

目前除了 $1$ 号建筑，其他建筑的保护魔法都尚未被启用，凤凰社决定派出一些成员去其他建筑施用咒语来启动保护魔法。每个凤凰社成员可以瞬间达到任意一个建筑，并用一个小时完成对该建筑保护魔法的启用，之后可以再前往其他的建筑。他们的任务是，保证不论伏地魔大军如何行动，大军所到建筑的保护魔法都已经启用。为了集中更多力量直接打击伏地魔大军，凤凰社希望派出施用咒语的成员数尽可能少。

请你计算，至少需要派出多少位成员。

注：

- 伏地魔大军到达 $1$ 号建筑开始攻击的同时，凤凰社派出成员去其他建筑施咒。

- 当大军攻克某个建筑后，凤凰社成员可以在知道大军下一个小时去哪个建筑的情况下，再决定他们去哪些建筑施咒。这个过程也不需要时间。

- 已经启用过保护魔法的建筑无需再施咒，即便大军攻克该建筑以后某个时候又回到这个建筑，大军也会在这个建筑持续攻击一个小时后再离开。

inputFormat:
第一行一个整数 $n$，表示建筑的数量。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示建筑 $u$ 和建筑 $v$ 之间有一条魔法道路。

outputFormat: 一行一个整数，表示最少需要派出施用咒语的成员数。

hint:
### 数据范围

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^5$。


title: [JSOI2013] 投影面积

description:
为了简单期间，投影屏幕对应二维平面中的一条平行与 $x$ 轴，连接点 $(x_1^s,y^s)$ 和点 $(x_2^s,y^s)$ 的线段。

JYY 的投影仪位于原点，朝向 $y$ 轴正方向，发出对称于 $y$ 轴并且张角度数为 $ang$ 的光束（$ang$ 是角度制），如图所示（粗线条为投影屏幕，黄色区域为投影仪射出的光束）。

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

实验室内一共有 $n$ 的障碍物，每个障碍物都对应于二维平面中的一条线段（我们认为这些障碍物的厚度为 $0$）。

有一些障碍物是不能反光的，因此光线只要射到这些线段上，就会被完全吸收（比如投影屏幕就是不会反光的）；其他障碍物则是双面可以反光的，光线如果射到这些线段上，就会按照基本光学原理进行反射。

所有的障碍物都相互不接触，并且也不会与投影屏幕，或者坐标原点接触。

光线在空气中传播会有损耗，因此在 JYY 的实验室中，光线在传播了 $len$ 的距离之后，就会消失。

现在 JYY 想知道，投影屏幕上被照亮的区域占投影屏幕总长度的比率。

inputFormat:
第一行一个正整数和两个正实数，为 $N,ang,len$。

接下来 $n$ 行，每行 $5$ 个整数 $x_1,x_2,y_1,y_2,r$，表示 JYY 的实验室内存在一个连接点 $(x_1,y_1)$ 和点 $(x_2,y_2)$ 的障碍物，$r$ 为 $0$ 或者 $1$。当 $r=0$ 时表示这个障碍物不反光，$r=1$ 则表示这个障碍物双面反光。

接下来一行四个整数 $x_1^s,y^s,x_2^s,y^s$，表示投影屏幕的位置，保证第二个和第四个整数相同。

outputFormat: 一行一个 $0$ 到 $1$ 之间的实数，表示屏幕上被照亮部分的长度与屏幕总长的比值，结果精确到小数点后 $4$ 位。

hint:
### 样例解释 1

如图。

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

### 数据范围

对于 $100\%$ 的数据，$0\leq n\leq 10,0<ang\leq 150,0<len\leq 10^3$，任意输入坐标绝对值不超过 $10^3$。

输入数据保证 $y^s>0,x_1^s<x_2^s$，并且对于任意障碍物满足 $\vert y_2\vert<y^s$。

输入数据还保证对于一条光线在消失或被吸收之前至多反射 $30$ 次。


title: [JSOI2014] 学生选课

description:
进入大学以后，学生们将面临选课，有 $n$ 个学生需要选课，学校里有三个老师 JYY，YJY，YYJ。

第一年里，每个学生们都选择了其中一位老师。经过了一年的学习，学生之间相互都有一定的印象，每个同学会根据自己的印象给另外 $n-1$ 个学生从好到坏排序。第二年的选课开始了，每个学生需要选择老师，可能是因为被坑多了，每一位同学都想换一个老师。这时需要你来调度同学们选课，使得上同一堂课的学生之间印象最坏的最好。

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

接下来 $n$ 行，每行 $n$ 个正整数，其中第 $i+1$ 行提供第 $i$ 个同学的信息。其中第一个整数 $A_i$，值为 $0,1,2$ 中的一个，表示第一年第 $i$ 个同学选的老师。
接下来 $n-1$ 个数字，是 $1,2,\cdots,i-1,i+1,\cdots,n$ 的一个排列，表示第 $i$ 个同学对其他同学印象从好到坏的排序。

outputFormat:
一行一个整数，为最小的非负整数 $T$，满足：

- 所有同学选择了和第一年不同的老师。

- 所有选择同一个老师的学生间彼此印象都是前 $T$ 好的。

hint:
### 样例解释 1

六名同学分别选择老师 $1,2,0,0,2,0$。

此时老师 $0$ 的课中同学 $6$ 对同学 $4$ 的印象为第 $4$ 好，所以答案 $T$ 为 $4$，并且找不到更小的 $T$。

### 数据范围

对于 $100\%$ 的数据，$n\leq 1000$。


title: [JDWOI-2] 01 串

background: 小 K 和小 M 写了一个 01 串。

description:
小 K 和小 M 写了一个 01 串 $S$，串的**结尾**包含 2 个连在一起的空格（用 `.` 表示）。

小 M 定义一个 01 串是美观的，当且仅当串中没有逆序对，即没有 1 出现在 0 的前面。

为了满足小 M 的上述要求，小 K 决定对这个 01 串进行一些修改。每一次修改，小 K 可以选择串中两个连续的非空格字符，并把他们移动到空格的位置，并且不改变相对位置。这样，被移动的字符处会变成空格，而原来的空格会被这两个字符填起来。

小 K 为了尽快让字符串变美观，希望在 $10000$ 步以内完成。现在，请求出需要用多少步使得 01 串变美观，并输出方案。如果无法使串美观，或者步数必须超过 $10000$ ，请输出 `-1`。

**注：你并不需要最小化修改步数，并且最终空格的位置随便。**

inputFormat: 一行一个 01 字符串，保证输入符合题意。

outputFormat:
第一行一个整数 $m$，表示修改的步数。

接下来 $m$ 行，每行两个整数 $x,y$，表示将 $(x,x+1)$ 位置上的两个数移动到 $(y,y+1)$。

hint:
**本题采用 Special Judge 和子任务评测。**

【样例解释 1】

$\texttt{1100..} \rightarrow \texttt{..0011}$

【样例解释 2】

可以发现无论如何移动都无法实现小 M 要求的 01 串。

【数据范围和子任务分数】

Subtask1(20pts)：$3 \leq |S| \leq 10$；
Subtask2(30pts)：$3 \leq |S| \leq 100$；
Subtask3(50pts)：$3 \leq |S| \leq 2000$。


title: [JRKSJ R4] Salieri

background:
![a358071f95cad1c8ccd29cc83a3e6709c83d518e.jpg](https://s2.loli.net/2021/12/24/Oi251TnFP7SflQp.jpg)

~~【记得到番里面去把“萨列里谱不出莫扎特的曲子”这句话找到】~~ 最终还是没能找到，哪位看过《命运石之门0》的兄弟能帮我找找？

description:
Salieri 发现了 $n$ 种制作音乐的模式，他将第 $i$ 种模式表示为一个字符串 $s_i$，这种模式所带来的初始优美度为 $v_i$。
Salieri 现在想制作 $m$ 首乐曲，每次他的灵感可以被表示成一个字符串 $S$。设 $cnt_i$ 为 $s_i$ 在 $S$ 中的出现次数，则采用 $i$ 模式制作的乐曲最终的优美度 $w_i=cnt_i\times v_i$。
Salieri 当然希望制作出来的乐曲最终优美度越大越好，但是他发现此灵感下前 $k-1$ 优美的乐曲已经被 Mozart 制作过了，他只能制作第 $k$ 优美的乐曲。请你求出这个最终优美度。

形式化题意：给出 $n$ 个字符串 $s_i$，每个字符串有一个权值 $v_i$。$m$ 次询问每次给出一个字符串 $S$ 和一个常数 $k$。设 $cnt_i$ 为 $s_i$ 在 $S$ 中的出现次数，求 $cnt_i\times v_i$ 第 $k$ 大的值。

inputFormat:
第一行两个数，$n,m$。
接下来 $n$ 行每行一个字符串 $s_i$ 和一个数 $v_i$。
接下来 $m$ 行每行一个字符串 $S$ 和一个数 $k$。

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

samples:
15 4
ba 18
cbc 74
aac 54
ba 77
a 66
c 96
cdb 47
dc 45
cb 62
db 88
dda 93
db 34
b 81
acd 100
da 80
bcaacbbdcbabcda 4
bccac 3
abdbaca 5
cbdaaaacaaca 3


title: 「EZEC-6」0-1 Trie

background:
> $\mathbf{000111}$，这就是简单中所蕴含的优美。

众所周知，tlx 不会字符串。

description:
现在 tlx 有 $n$ 个 $\mathbf{1}$ 和 $m$ 个 $\mathbf{0}$，你需要把它们排列，但要保证任意的 $\mathbf{1}$ 互不相邻且第一个位置是 $\mathbf{0}$、最后一个位置是 $\mathbf{1}$，现在把所有可以构造出的串放到一棵 0-1 Trie 上，需要多少个节点？

**注意：节点计数时，不计算最开始的空节点，只计算代表“ $\mathbf{0}$ ”、“ $\mathbf{1}$ ”的节点。**

**在本题中，我们认为用节点存储字符而非边， Trie 基本原理不变。**

因为答案可能很大而且询问较多，所以请在最后输出所有询问的答案对 $18888913$ （放心，是个质数）取模的结果的异或和（**异或和不再进行取模**）。

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

接下来 $T$ 行，每行两个正整数 $n,m$，分别代表 $\mathbf{1,0}$ 的个数。

outputFormat: 共一行一个整数，代表所有结果的异或和。

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

可以发现，所有能构造出的串有：

$$\mathbf{000101}$$
$$\mathbf{001001}$$
$$\mathbf{010001}$$

构造 0-1 Trie，如图：

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

共需 $15$ 个节点。

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

两次询问的答案分别为 $34$ 和 $4487317$。

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

**【数据规模与提示】**

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

具体约束如下：

Subtask $1$（$10\%$）：满足 $T\leq 10$，$n,m\leq 5$；

Subtask $2$（$20\%$）：满足 $T \leq 10$，$n,m\leq 1\times 10^3$；

Subtask $3$（$30\%$）：满足 $T\leq 10$，$n,m\leq 5\times 10^5$;

Subtask $4$（$40\%$）：无特殊限制。

对于 $100\%$ 的数据，满足 $1\le T \le 2\times10^6$，$1\le n,m\le 5\times 10^{18}$。

**本题输入量较大，建议采用较为快速的读入方式并注意常数因子对程序效率带来的影响。**

------------
 0-1 Trie 是一种特殊的 Trie ，只有 $\mathbf{0,1}$ 两种字符。

 如果你不了解 Trie，可以查看：[OI Wiki--Trie](https://deploy-preview-980--oi-wiki.netlify.app/string/trie/)。


title: 「PMOI-2」城市

description:
P 国有 $N$ 座城市和 $M$ 条无向道路，其中 $1$ 号城市是首都，且任意两座城市都能通过道路互相到达。

现在 P 国要在首都召开 ION。为了建设比赛场地，每个城市都要向首都提供原材料，其中第 $i$ 座城市可以提供类型为 $c_i$ 的原材料。每座城市都会有货车从该城市出发，**沿简单路径**前往首都。如果从城市 $A$ 出发的货车必须经过城市 $B$ ，那么我们称城市 $B$ 在城市 $A$ 到首都的必经之路上。如果对于城市 $A,B,C$，从 $B$ 到 $A$ 的**任意简单路径**与 $C$ 到 $A$ 的**任意简单路径**没有公共边，那么我们称城市 $B$ 和城市 $C$ 关于城市 $A$ 互不影响。

记 $f(A,k)$ 为满足下列所有条件的 $k$ 元集合 $\{B_1,B_2,\cdots B_k\}$ 的个数：

1. 对于任意 $1\leq i \leq k$ 满足 $A\neq B_i$，**城市 $A$ 在城市 $B_i$ 到首都的必经之路上**且城市 $B_i$ 供应的材料与城市 $A$ **不同**。

2. 对于任意 $1\leq i < j \leq k$ 满足 **$B_i$ 与 $B_j$ 关于 $A$ 互不影响**，且 $B_i$ 和 $B_j$ 供应的原材料**相同**。

定义举办 ION 的吸引力为$\sum_{i=1}^N\sum_{k=1}^Kf(i,k)$，其中 $K$ 是给定的常数。

现在，你作为 P 国的首脑，你想要知道这次 ION 的吸引力。

**由于答案可能很大，所以请将答案对 $998244353$ 取模**。

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

第二行 $N$ 个整数，第 $i$ 个数第 $i$ 座城市供应的原材料类型 $c_i$。

接下来 $M$ 行，每行两个整数 $u,v$ ，表示 $P$ 国的一条道路。保证**没有重边，没有自环**。（$1\leq u, v \leq N, u\neq v$）

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

hint:
【样例解释】

样例中 P 国的地图如下：

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

下表中，第 $i$ 行第 $j$ 列表示 $f(i,j)$。

| $4$ | $0$ | $0$ | $0$ |
| -----------: | -----------: | -----------: | -----------:
| $4$ | $0$ | $0$ | $0$ |
| $2$ | $1$ | $0$ | $0$ |
| $1$ | $0$ | $0$ | $0$ |

所以吸引力为 $4+4+2+1+1=12$。

【数据范围】

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

- Subtask1（10pts）：$N,K \le 8$；
- Subtask2（10pts）：$K=1$；
- Subtask3（15pts）：$K=2$；
- Subtask4（15pts）：保证图的形态为一棵树；
- Subtask5（15pts）：$N \le 2000$；
- Subtask6（15pts）：$N \le 4\times 10^4$；
- Subtask7（20pts）：无特殊限制。

对于 $100\%$ 的数据满足，$1\leq N\leq 5\times 10^5$， $1\leq M \leq \min(10^6,\frac{N\times(N-1)}{2})$，$1 \le K \le 20$，$1 \le c_i \le 10^9$。

**温馨提示**：输入量较大，请使用较快的读入方式。


title: 「JZOI-1」红包

background: 新年到了，小僖收到了叔叔寄给他的红包，这个红包里面有很多很多的钱。

description:
小僖收到的红包总额是这样的：

所有 $K$ 元组满足每个元素都是正整数且 $\le N$，总额就是这些 $K$ 元组的最小公倍数的乘积。

但由于叔叔并没有那么多的钱，所以结果还要对 $998244353$ 取模。

小僖花了 $10^{-16}$ 秒就算了出来，但他想验证一下是否正确，于是找上了你（别问我为什么他不直接拆开红包看）。

换句话讲，题目只需要你求：
$$\prod_{i_1=1}^N\prod_{i_2=1}^N...\prod_{i_K=1}^N{\rm lcm}(i_1,i_2...i_K)\mod 998244353$$
保证 $K>1$，其中，${\rm lcm}(i_1,i_2...i_K)$，表示 $i_1,i_2...i_K$ 的最小公倍数。

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

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

接下来 $T$ 行，每行两个数，$N,K$，表示每组询问。

outputFormat: $T$ 行，每行一个数，表示答案，记得对 $998244353$ 取模。


title: 「MCOI-04」重型管制巡航机

background:
这是一个作战部署命令。

我们已经从国家安全局获得了有关敌方重型指挥巡洋舰的部分机密情报。

敌方巡航机的正式名称已被确认为 P-1112 Aigaion。

空中舰队中包含一种 Kottos 中型巡航机负责电子支援，还有一种 Gyges 中型巡航机负责近程防空。

Aigaion，作为指挥机，负责一切与巡航导弹相关的事务。

在获得这些情报之后，我们可以草拟一个摧毁 Aigaion 的计划。

仔细听好了。

Aigaion 只能在机体前部接受空中加油。

多架加油机必须同时处在 Aigaion 前方才能进行加油作业。

当加油机在 Aigaion 前部进行加油时，Aigaion 的雷达探测能力会暂时削弱。

这里就是关键点了。

Aigaion 在进行加油时，其雷达基本完全无法探测在其前方飞行的物体。

如果你们能维持在一个固定航线并在一个特定高度上飞行，你们就能在不被敌军发现的情况下，从空中接近 Aigaion。

所以我们解决掉这只怪物的最佳时机就是它进行空中加油的时候。

Aigaion 的预定航线图也包含在这份情报中。

简报结束后，我们将在机库再次检查航线图。

快去准备吧。

…………

Garuda 队，交战！

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 09} \\\Large\text{Heavy Command Cruiser}\\\tiny -\ The\ Dead\ Sea\ -$$

description:
在平面上给定一棵有根树，树根为 $1$，根的深度为 $0$。

对于深度为 $x$ 的节点，其 **纵坐标** 为 $n-x+1$。

对于一个节点的所有子节点，**从左到右按照编号升序排列**。每条边都是一条 **连接两个点的线段**。

每一个叶子节点都有一条 **平行于 $y$ 轴且向 $y$ 轴负方向无限延伸的射线**，根节点有一条 **平行于 $y$ 轴且向 $y$ 轴正方向无限延伸的射线**。

**任意两条线段或射线只在树的节点处相交。**

如果你不理解这个树是怎么画的，可以阅读样例 1 解释。

给定 $q$ 组 $u,v$，你现在要从点 $u$ 开始在平面上自由移动，但是你不能经过除 $u,v$ 以外的任何一个点，且每经过一条线段或射线就会产生 $1$ 的代价。

你的目标是移动到点 $v$，你需要求出移动过程产生的最小代价。

inputFormat:
由于直接输入会造成巨大的输入量，所以本题采用特殊的输入方式。

给定如下随机数生成器：

```cpp
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
```

第一行三个整数 $n,q,s$。

接下来一行 $n-1$ 个整数描述树的结构。第 $i$ 个数代表 $i+1$ 号节点的父亲的编号 $f_i$。

接下来，如果 $s=-1$，则标准输入中的接下来 $q$ 行每行会有两个空格分隔的整数，代表询问的 $u'$ 和 $v'$；设上一次询问的答案为 $\text{lastans}$，你真正要处理的询问是 $u=u'\oplus \text{lastans}$ 和 $v=v'\oplus \text{lastans}$，其中 $\oplus$ 表示异或运算。如果这是第一次询问，则 $\text{lastans}=0$。

否则，你需要先调用一次 $(\text{read}()\oplus \text{lastans})\bmod n+1$ 得到询问的 $u$，再调用一次 $(\text{read}()\oplus \text{lastans})\bmod n+1$ 得到询问的 $v$。

outputFormat:
如果 $s=-1$，则输出 $q$ 行，每行是对应询问的答案。

如果 $s\geq 0$，则输出两个空格分隔的整数，分别表示所有答案的异或和和所有答案的和。

hint:
**For the enhanced version, see [P7434](https://www.luogu.com.cn/problem/P7434).**

#### 样例 1 解释

第二次实际是询问 $u=6,v=3$，其他询问都满足 $u'=u,v'=v$。

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

- 可以看出，从 $4$ 到 $7$ 需要经过一条线；
- 从 $6$ 到 $3$ 不需要经过直线；
- 从 $5$ 到 $2$ 不需要经过直线；
- 从 $4$ 到 $8$ 需要经过一条线；
- 故答案分别为 $1,0,0,1$。

#### 数据规模与约定

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

- Subtask 1（1 pts）：$f_i=i-1$，$s=-1$。
- Subtask 2（9 pts）：$f_i=1$，$s=-1$。
- Subtask 3（10 pts）：$n,q\leq 2\times 10^3$，$s=-1$。
- Subtask 4（20 pts）：$f_i=\left\lfloor\dfrac{i}{2}\right\rfloor$，$s=-1$。
- Subtask 5（59 pts）：$s=-1$。
- Subtask 6（1 pts）：无特殊限制。

对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^5$，$1\leq q\leq 5\times 10^6$，$1\leq u,v\leq n$，$1\leq f_i<i$，$-1\leq s\leq 10^9$，且 $s=-1$ 时 $q\leq 5\times 10^5$。

**对于 $99\%$ 的数据，保证 $s=-1$。**

**IO 量可能很大，请选择合适的读入输出方式。**

#### 说明

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

---

你问为什么 MCOI 里面混入了 AC6？
很简单，因为 ClCN 不玩 MC。


title: 「JZOI-1」旅行

background: 新年快到了，小僖要做一个长远的旅行，至于从哪里开始，到哪里，他还没有想好。

description:
这次旅行是在一个由 $N$ 个城市和 $(N-1)$ 条双向道路组成的一个国家中，其中保证任意两个城市可以互达。

为了美化环境，所有道路都是沿河修建的，这意味着小僖可以自己制造一艘船，然后划船通过这条路，所以小僖每走一条边都可以从陆上走过去，也可以划船通过。

当然，因为顺流和逆流的原因，所以有一个参数 $z_i$，换句话讲，如果从陆上走过这条边所花费的时间为 $a_i$，那么顺流而下划船所花费的时间为 $a_i-z_i$ (保证结果大于 $0$)，逆流而上花费的时间为 $a_i+z_i$。不过，造船需要 $L$ 的时间，且人一旦上了岸，就必须放弃这条船只。

现在小僖想你帮忙算一下从 $u$ 走到 $v$ 的最短时间。

注意：一条船可以连续走多段水路（只要你不下船）

inputFormat:
第一行三个数，$N,L,T$。

接下来 $(N-1)$ 行，每行五个数，$x_i,y_i,a_i,z_i,type_i$，其中 $type_i=1$ 表示水从 $x_i$ 流向 $y_i$，$type_i=0$ 表示水从 $y_i$ 流向 $x_i$。

接下来 $T$ 行，每行两个数 $u_i,v_i$，表示每个计划的起点和终点。

outputFormat: $T$ 行，每行一个数，表示每一个询问的答案。

hint:
### 样例1解释
图长这样：

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

对于第一组询问，也就是从 $2$ 到 $3$，我们可以在 $2$ 号节点造船，花费 $2$ 的时间，然后从节点 $2$ 顺流而下到 $1$，花费 $2-1=1$，在顺流而下到 $3$，花费 $3-2=1$，所以总花费为 $2+1+1=4$。
## 数据范围
对于 $10\%$ 的数据，$N,T\leq10^3$。

对于另外 $10\%$ 的数据，树的形态随机。

对于另外 $20\%$ 的数据，所有的 $u$ 或所有的 $v$ 都相等。

最后一个测试点给出了一条链。

对于 $100\%$ 的数据，$N,T\leq2\times10^5$，且 $0
<a_i,L\leq10^5$。


title: [COCI2018-2019#5] Titlovi

description:
现有一个 `.SRT` 类型的文件，其由若干段字幕组成，用来再观看时载入。每段字幕又由三部分组成：

- 第一行：该字幕的编号
- 第二行字幕开始播放时间 --> 字幕结束播放时间
- 接下来的若干行：字幕内容

下面是一段字幕的例子：

```plain
1
00:00:01,600 --> 00:00:04,200
Good day!

2
00:00:05,900 --> 00:00:07,999
Good day to you too!
Here you go!

3
00:00:10,000 --> 00:00:14,000
May I please have ten garlic sausages?
```

时间均以 `HH:MM:SS,TTT` 格式给出，分别表示小时、分钟、秒和毫秒。规定 $1$ 秒 $=1000$ 毫秒。

有时观看时会出现时间上的差异，因此在载入字幕时需要将所有字幕调快 / 调慢一个特定的时间，并输出调整后的 `.SRT` 文件。

inputFormat:
输入不超过 $100$ 行，表示 `.SRT` 类型文件的内容。

每一段字幕的第一行，输入字幕编号。对于字幕编号，若第一段的编号为 $X$，则第 $i$ 段的必定为 $X+i-1$。

每一段字幕之间用一个空行隔开。字幕内容包含英文字母、空格和字符 `,.?!.` 等。

最后一段字幕的最后一行之后的一行，将包含一个字符 `#`，表示字幕部分结束。

接下来的一行 / 输入的最后一行，输入整数 $T$，表示需要调整的时间。如果 $T \ge 0$，则表示要将字幕时间向后调整 $T$ 毫秒。否则，表示要将字幕时间向前调整 $-T$ 毫秒。

outputFormat: 输出调整时间后的 `.SRT` 文件。

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

对于 $100\%$ 的数据，$-10^4 \le T \le 10^4$。

#### 说明

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

注：经测试，官方输入文件中可能含有 `\r` 等 Windows 下产生的字符。请大家在处理的过程中留意！

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #5](https://hsin.hr/coci/archive/2018_2019/contest5_tasks.pdf)  _T1 Titlovi_。**


title: [COCI2018-2019#5] Jarvis

description:
Ivan 拥有 $N$ 架无人机，每架无人机均有一个出厂属性值和一个出战需求属性值。他可以选定一个整数 $X$（$X$ 不一定为正整数），将所有无人机在出厂属性值的基础上加上 $X$。

求能够出战（即属性值与出战需求属性值相等）的无人机的最大数量。

inputFormat:
第一行输入整数 $N$，表示无人机的数量。

第二行输入 $N$ 个整数 $A_i$，表示无人机的出厂属性值。

第三行输入 $N$ 个整数 $B_i$，表示无人机的出战需求属性值。

outputFormat: 输出能够出战的无人机的最大数量。

hint:
#### 样例 3 解释

若选定 $X=3$，则属性值分别变为 $1+3=4$ 和 $2+3=5$，则只有第二架可以出战。若 $X=4$，则属性值分别 $5$ 和 $6$，则只有第一架可以出战。可以证明，没有能够使得两架都能出战的整数 $X$。

#### 数据规模与规定

对于 $40\%$ 的数据，$-10 \le A_i,B_i \le 10$。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$-10^6 \le A_i,B_i \le 10^6$。

#### 说明

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

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #5](https://hsin.hr/coci/archive/2018_2019/contest5_tasks.pdf)  _T2 Jarvis_。**


title: 「EZEC-8」凑数

description: 给定 $1$ 到 $n$ 这 $n$ 个正整数，请问能否恰好选择 $k$ 个数，使选中的数之和为 $s$（每个数只能用 $1$ 次）。

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

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

对于每组数据，一行 $3$ 个正整数 $n,k,s$。

outputFormat:
对于每组数据：

输出一行，一个字符串，`Yes` 或 `No`，表示是否可以恰好选择 $k$ 个数，使选中的数之和为 $s$。

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

-  Subtask 1（15 points）：$n\le5$。
-  Subtask 2（15 points）：$n\le15$。
-  Subtask 3（20 points）：$n\le100$。
-  Subtask 4（15 points）：$k=1$。
-  Subtask 5（15 points）：$s\le15$。
-  Subtask 6（20 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le10^3$，$1\le k\le n\le10^9$，$1\le s\le10^{18}$。


title: [WC2021] 括号路径

description:
给定一张 $n$ 个点 $2 m$ 条边的有向图，图中的每条边上都有一个标记，代表一个左括号或者右括号。共有 $k$ 种不同的括号类型，即图中可能有 $2 k$ 种不同的标记。点、边、括号种类均从 $1$ 开始编号。

图中的每条边都会和另一条边成对出现。更具体地，若图中存在一条标有第 $w$ 种括号的左括号的边 $(u, v)$，则图中一定存在一条标有第 $w$ 种括号的右括号的边 $(v, u)$。同样地，图中每条标有右括号的边将对应着一条反方向的标有同类型左括号的边。

现在请你求出，图中共有多少个点对 $(x, y)$（$1 \le x < y \le n$）满足：图中存在一条从 $x$ 出发到达 $y$ 的路径，且按经过顺序将路径各条边上的标记拼接得到的字符串是一个合法的括号序列。

inputFormat:
第一行三个整数 $n, m, k$，分别表示图中的点数，边对数和括号类型数。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示一条从 $u$ 到 $v$ 的有向边，其标记为第 $w$ 种括号的左括号；以及一条从 $v$ 到 $u$ 的有向边，其标记为第 $w$ 种括号的右括号。

输入给出的图中，任意两个不同的顶点间可以有多条有向边相连，但图中不存在连向自身的有向边，即 $u \ne v$。

outputFormat: 输出仅一行一个整数，表示满足条件的点对数量。

samples:
见附件中的 bracket/bracket3.in
见附件中的 bracket/bracket3.ans

samples:
见附件中的 bracket/bracket4.in
见附件中的 bracket/bracket4.ans


title: [WC2021] 表达式求值

description:
定义二元操作符 `<`：对于两个长度都为 $n$ 的数组 $A, B$（下标从 $1$ 到 $n$），$A$`<`$B$ 的结果也是一个长度为 $n$ 的数组，记为 $C$。则有 $C[i] = \min(A[i], B[i])$（$1 \le i \le n$）。

定义二元操作符 `>`：对于两个长度都为 $n$ 的数组 $A, B$（下标从 $1$ 到 $n$），$A$`>`$B$ 的结果也是一个长度为 $n$ 的数组，记为 $C$。则有 $C[i] = \max(A[i], B[i])$（$1 \le i \le n$）。

现在有 $m$（$1 \le m \le 10$）个长度均为 $n$ 的整数数组 $A_0, A_1, \ldots , A_{m-1}$。给定一个待计算的表达式 $E$，其满足 $E$ 中出现的每个操作数都是 $A_0, A_1, \ldots , A_{m-1}$ 其中之一，且 $E$ 中只包含 `<` 和 `>` 两种操作符（`<` 和 `>` 的运算优先级相同），因此该表达式的结果值也将是一个长度为 $n$ 的数组。

特殊地，表达式 $E$ 中还可能出现操作符 `?`，它表示该运算符可能是 `<` 也可能是 `>`。因此若表达式中有 $t$ 个 `?`，则该表达式可生成 $2^t$ 个可求确定值的表达式，从而可以得到 $2^t$ 个结果值，你的任务就是求出这 $2^t$ 个结果值（每个结果都是一个数组）中所有的元素的和。你只需要给出所有元素之和对 ${10}^9 + 7$ 取模后的值。

inputFormat:
第一行两个整数 $n, m$，分别表示数组长度与数组个数。

第 $2 \sim m + 1$ 行每行 $n$ 个用空格分隔的整数，第 $i$ 行第 $j$ 个元素代表 $A_{i-2}[j]$（$2 \le i \le m + 1$，$1 \le j \le n$）。

最后一行一个字符串 $S$，表示表达式 $E$。$S$ 中只包含字符 `0` 到 `9`、`(`、`)`、`<`、`>`、`?`，数字字符表示操作数的下标，例如字符 `2` 表示表达式中的操作数为 $A_2$。

outputFormat: 仅一行一个整数，表示所有 $2^t$ 个表达式的结果，它们的元素之和模 ${10}^9 + 7$ 的值。

samples:
见附件中的 expr/expr4.in
见附件中的 expr/expr4.ans


title: [WC2021] 斐波那契

description:
众所周知，小葱同学擅长计算，尤其擅长计算组合数。但是对组合数有了充分研究的小葱同学对组合数失去了兴趣，而开始研究数列。

我们定义 $F_0 = a$，$F_1 = b$，$F_i = (F_{i-1} + F_{i-2}) \bmod m$（$i \ge 2$）。

现在给定 $n$ 组询问，对于每组询问请找到一个最小的整数 $p$，使得 $F_p = 0$。

inputFormat:
第一行两个整数 $n, m$，代表询问的组数和每组计算中的模数。

接下来 $n$ 行每行两个整数 $a, b$，代表一组询问中 $F_0$ 和 $F_1$ 的值。

outputFormat: 对于每组询问，输出一行一个整数 $p$ 代表答案。如果这样的 $p$ 不存在，输出 `-1`。

samples:
见附件中的 fib/fib3.in
见附件中的 fib/fib3.ans

samples:
见附件中的 fib/fib4.in
见附件中的 fib/fib4.ans


title: 「JZOI-1」窗花

background: 小蔡和小僖在比赛剪窗花。

description:
小蔡和小僖的制作水平都很高，换句话讲，他们都能制作出好看度为 $1\dots n$ 的窗花，但是两个人的熟练度不一样，小蔡的熟练度可以用一个数组 $a_{1\dots n}$ 组成，换句话讲，他剪出一个好看度为 $k(1\le k\le n)$ 的窗花的概率为 $\frac{a_k}{\sum_{i=1}^na_i}$。同理，小僖的熟练度可以用数组 $b_{1\dots n}$ 组成，他剪出一个好看度为 $k(1\le k\le n)$ 的窗花的概率为 $\frac{b_k}{\sum_{i=1}^nb_i}$。

现在两个人正在比赛剪窗花，如果某个人剪出的窗花的好看度比另一个人的大，那么这个人取胜，如果比另一个人的小，那么这个人失败，如果一样，则为平局。

现在，小蔡用一个计数器记录他的情况，如果他赢了，那么计数器 $+1$，如果他输了，那么计数器 $-1$，如果平了，那么不加不减。但由于计数器不支持负数，所以如果结果 $\le0$ 那么会自动变成 $0$，如果计数器显示的数 $=m$，那么比赛结束。

作为新时代的大神，小蔡花了 $10^{-6}$ 秒就算出来了比赛结束所经过的期望局数，但他想让你帮忙检验一下……

inputFormat:
第一行输入两个整数 $ n, m $，详细见题目。
第二行输入 $ n $ 个整数 $ a_i $，表示第一个人的熟练度。
第三行输入 $ n $ 个整数 $ b_i $，表示第二个人的熟练度。

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


title: Dream and the Multiverse REMATCH

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

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

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

*- do I win.*

description:
Dream abstracts the fabric of spacetime as a directed rooted tree (arborescence) with $N$ nodes (numbered $1$ through $N$). Node $1$ is the root and for each $i$ ($1 \le i \le N-1$), the parent of node $i+1$ is $f_i$. All edges of this tree are directed away from the root.

Then, Dream employs a magical superpower and adds $M$ directed edges to this tree in such a way that the resulting directed graph remains acyclic (a DAG).

Let's call a node of this DAG an *event* and further call a simple path on this DAG an *era*. Dream considers a pair of events $(i,j)$ to be *plausible* if there is an era whose first event is $i$ and last event is $j$. Note that $i \lt j$ does not have to hold for a plausible pair.

Dream now wants you to answer $Q$ queries. In each query, he gives you two positive integers $l$ and $r$, where $l \leq r$, and he wishes to know the number of plausible pairs of events $(i,j)$ such that $l \leq i \lt j \leq r$.

inputFormat:
The first line of the input contains two space-separated integers $N$ and $M$.

The second line contains $N-1$ space-separated integers $f_1, f_2, \ldots, f_{N-1}$.

$M$ lines follow. Each of these lines contains two space-separated integers $u$ and $v$ describing an additional edge from node $u$ to node $v$.

The following line contains a single integer $Q$.

$Q$ lines follow. Each of these lines contains two space-separated integers $l$ and $r$ describing a query.

outputFormat: For each query, print a single line containing one integer ― the number of plausible pairs $(i,j)$ such that $l \leq i \lt j \leq r$.

hint:
 - $2 \leq N \leq 7 \cdot 10^5$
 - $1 \leq Q \leq 7 \cdot 10^5$
 - $0 \leq M \leq 20$
 - $1 \le f_i \le N$ for each valid $i$
 - $1 \le u, v \le N$
 - the graph described on the input is acyclic
 - $1 \le l \le r \le N$

### Subtasks

**Subtask #1 (17 points):** $N,Q\le3\cdot 10^5$

**Subtask #2 (83 points):** original constraints