title: 【模板】差分约束

description:
给出一组包含 $m$ 个不等式，有 $n$ 个未知数的形如：

$$ \begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases}$$

的不等式组，求任意一组满足这个不等式组的解。

inputFormat:
第一行为两个正整数 $n,m$，代表未知数的数量和不等式的数量。

接下来 $m$ 行，每行包含三个整数 $c,c',y$，代表一个不等式 $x_c-x_{c'}\leq y$。

outputFormat: 一行，$n$ 个数，表示 $x_1 , x_2 \cdots x_n$ 的一组可行解，如果有多组解，请输出任意一组，无解请输出 `NO`。

hint:
**样例解释**

$\begin{cases}x_1-x_2\leq 3 \\ x_2 - x_3 \leq -2 \\ x_1 - x_3 \leq 1 \end{cases}$

一种可行的方法是 $x_1 = 5, x_2 = 3, x_3 = 5$。

$\begin{cases}5-3  = 2\leq 3 \\ 3 - 5 = -2 \leq -2 \\ 5 - 5  = 0\leq 1 \end{cases}$

**数据范围**

对于 $100\%$ 的数据，$1\leq n,m \leq 5\times 10^3$，$-10^4\leq y\leq 10^4$，$1\leq c,c'\leq n$，$c \neq c'$。

**评分策略**

你的答案符合该不等式组即可得分，请确保你的答案中的数据在 `int` 范围内。

如果并没有答案，而你的程序给出了答案，SPJ 会给出 `There is no answer, but you gave it`，结果为 WA；
如果并没有答案，而你的程序输出了 `NO`，SPJ 会给出 `No answer`，结果为 AC；
如果存在答案，而你的答案错误，SPJ 会给出 `Wrong answer`，结果为 WA；
如果存在答案，且你的答案正确，SPJ 会给出 `The answer is correct`，结果为 AC。


title: [USACO19OPEN] Compound Escape P

type: P

description:
Bessie和她的朋友们被抓走并关在了远离农场的一个秘密房屋，现在该是Bessie站出来策划脱逃的时候了！这一房屋包含 $ NK $ 个排列成 $ N \times K $ 矩形方阵的囚室，水平和垂直方向相邻的囚室之间有门互通。每个囚室中有一头奶牛。

Bessie黑进了系统，可以解锁任意一部分的门，但是每个门均有其代价。为了使奶牛们能够脱逃，Bessie必须打开足够多的门使得所有的奶牛可以聚集在一个房间内（这样她们就能拥有足够的力量挖地洞通向外面！）。Bessie想要使得总的解锁花费最小。

但是这次行动异常关键，Bessie不能满足于仅仅一个脱逃方案：她还需要后备方案。帮助她计算最小代价脱逃方案的数量；如果某一扇门在一个方案中被解锁了而在另一个方案中没有，那么这两个方案就被认为是不同的。

由于这个数字可能非常大，只需输出该数对 $ 10^9+7 $ 取模后的结果。

inputFormat:
输入的第一行包含两个空格分隔的整数 $ N $ 和 $ K $ （ $ 2 \leq N \leq 30000 ,2 \leq K \leq 6 $ ）。

以下 $ N $ 行每行包含 $ K-1 $ 个空格分隔的整数，为解锁一条水平边上的每扇门需要花费的代价。

以下 $ K $ 行每行包含 $ N-1 $ 个空格分隔的整数，为解锁一条垂直边上的每扇门需要花费的代价。

所有的花费均在 $ 1 $ 到 $ 10^9 $ 之间。

outputFormat: 一个整数：最小花费的逃脱方案的数量，对 $ 10^9+7 $ 取模。


title: [USACO19OPEN] Valleys P

description:
Bessie 喜欢观光，而今天她正在寻找景色优美的山谷。

她感兴趣的是一个 $ N \times N $ 的方阵，其中每个格子都有一个高度。所有在此正方形方阵之外的格子的高度可以被看作是无限大。

山谷指的是一块连续、不含洞的一块区域，并且每个相邻的包围该区域的格子都高于这块区域中的所有格子。

更形式化地说：

* 一组格子被称作是“沿边相邻的”，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右方向的移动，到达其中所有其他格子。
* 一组格子被称作是“沿点相邻的”，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右、对角线方向的移动，到达其中所有其他格子。
* 一个“区域”指的是一组非空并且沿边相邻的格子。
* 一个区域被称作是“有洞的”，如果这个区域的补集（包括在 $ N \times N $ 方阵之外的无限高格子）不是沿点相邻的。
* 区域的“边界”指的是所有与该区域内的某个格子正交相邻（上、下、左、右），但本身不在该区域内的格子。
* 一个“山谷”指的是某个非有洞区域，满足区域内的任意格子的高度低于该区域边界上任意格子的高度。

Bessie 的目标是求出所有山谷的大小之和。

### 一些例子

这是一个区域：

```
oo.
ooo
..o
```

这不是一个区域（中间的格子和右下角的格子不沿边相邻）：

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

这是一个非有洞区域：

```
ooo
o..
o..
```

这是一个有洞的区域（“甜甜圈”中间的格子与区域外的格子不沿点相邻）：

```
ooo
o.o
ooo
```

这是另一个非有洞区域（中间的格子与右下角的格子沿点相邻）：

```
ooo
o.o
oo.
```

inputFormat:
输入的第一行包含 $ N $ ，其中 $ 1 \leq N \leq 750 $ 。

以下 $ N $ 行每行包含 $ N $ 个整数，为方阵每个格子的高度。所有高度 $ h $ 满足 $ 1 \leq h \leq 10^6 $ 。所有高度均为不同的整数。

outputFormat: 输出一个整数，为所有山谷的大小之和。

hint:
在这个例子中，有三个大小为1的山谷：

```
o.o
...
o..
```

一个大小为2的山谷：

```
...
...
oo.
```

一个大小为3的山谷：

```
ooo
...
...
```

一个大小为6的山谷：

```
ooo
o..
oo.
```

一个大小为7的山谷：

```
ooo
o.o
oo.
```

以及一个大小为9的山谷：

```
ooo
ooo
ooo
```

所以，答案为1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30。

### 子任务

对于至少19%的测试数据， $ N \leq 100 $ 。


title: [USACO19OPEN] Snakes G

description:
传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以Bessie要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。

Bessie装备了一个捕网，用来捕捉 $ N $ 组排成一行的蛇（ $ 1 \leq N \leq 400 $ ）。Bessie必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当Bessie抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。

一个大小为 $ s $ 的捕网意味着Bessie可以抓住任意包含 $ g $ 条的一组蛇，其中 $ g \leq s $ 。然而，每当Bessie用大小为 $ s $ 的捕网抓住了一组 $ g $ 条蛇，就意味着浪费了 $ s-g $ 的空间。Bessie可以任意设定捕网的初始大小，并且她可以改变 $ K $ 次捕网大小（ $ 1 \leq K<N $ ）。

请告诉Bessie她捕捉完所有组的蛇之后可以达到的总浪费空间的最小值。

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

第二行包含 $ N $ 个整数 $ a_1, \ldots ,a_N $ ，其中 $ a_i $ （ $ 0 \leq a_i \leq 10^6 $ ）为第 $ i $ 组蛇的数量。

outputFormat: 输出一个整数，为Bessie抓住所有蛇的总浪费空间的最小值。

hint: Bessie可以设置她的捕网开始时大小为7。当她抓完第一组蛇之后，她将她的捕网的大小调整为9，保持这个大小直到抓完第4组蛇，再将捕网大小调整为3。总浪费空间为 $ (7-7)+(9-9)+(9-8)+(3-2)+(3-3)+(3-2)=3 $ 。


title: [USACO19OPEN] I Would Walk 500 Miles G

description:
Farmer John想要将他的编号为 $ 1 \ldots N $ 的 $ N $ 头奶牛（ $ N \leq 7500 $ ）分为非空的 $ K $ 组（ $ 2 \leq K \leq N $ ），使得任意两头来自不同组的奶牛都需要走一定的距离才能相遇。奶牛 $ x $ 和奶牛 $ y $ （其中 $ 1 \leq x<y \leq N $ ）愿意为了见面走 $ (2019201913x+2019201949y) \mod 2019201997 $ 英里。

给定一个将 $ N $ 头奶牛分为 $ K $ 个非空小组的分组方案，令 $ M $ 为任意两头来自不同组的奶牛愿意为了见面行走的英里数的最小值。为了测试奶牛们相互之间的忠诚度，Farmer John想要将 $ N $ 头奶牛以最佳的方式分为 $ K $ 组，使得 $ M $ 尽可能大。

inputFormat: 输入仅有一行，包含 $ N $ 和 $ K $ ，用空格分隔。

outputFormat: 输出最优的 $ M $ 。

hint: 在这个例子中，奶牛1和奶牛2愿意为了见面走2019201817英里。奶牛2和奶牛3愿意走2019201685英里。奶牛1和奶牛3愿意走2019201769英里。所以，将奶牛1单独分为一组，奶牛2和奶牛3分为一组， $ M=min(2019201817,2019201769)=2019201769 $ （这是我们在这个问题中能够达到的最佳结果）。


title: [USACO19OPEN] Balancing Inversions G

description:
Bessie和Elsie在一个长为 $ 2N $ 的布尔数组 $ A $ 上玩游戏（ $ 1 \leq N \leq 10^5 $ ）。Bessie的分数为 $ A $ 的前一半的逆序对数量，Elsie的分数为 $ A $ 的后一半的逆序对数量。逆序对指的是满足 $ A[i]=1 $ 以及 $ A[j]=0 $ 的一对元素，其中 $ i<j $ 。例如，一段0之后接着一段1的数组没有逆序对，一段 $ X $ 个1之后接着一段 $ Y $ 个0的数组有 $ XY $ 个逆序对。

Farmer John偶然看见了这一棋盘，他好奇于可以使得游戏看起来成为平局所需要交换相邻元素的最小次数。请帮助Farmer John求出这个问题的答案。

inputFormat: 输入的第一行包含 $ N $ ，第二行包含 $ 2N $ 个为0或1的整数。

outputFormat: 输出使得游戏成为平局最少需要的移动次数。

hint: 在这个例子中，初始时前一半有1个逆序对，后一半有3个逆序对。交换了第5和第6个数之后，两个子数组均有0个逆序对。


title: [USACO19OPEN] Left Out S

description:
Farmer John正在尝试给他的牛群拍照。根据以往的经验，他知道这一工作往往结果不怎么样。

这一次，Farmer John购买了一台昂贵的无人机，想要拍一张航拍照。为了使照片尽可能好看，他想让他的奶牛们在拍照时都朝向同一个方向。奶牛们现在在一块有围栏的草地上排列成 $ N \times N $ （ $ 2 \leq N \leq 1000 $ ）的方阵，例如：

```
RLR
RRL
LLR
```

这里，字符'R'表示一头朝右的奶牛，字符'L'表示一头朝左的奶牛。由于奶牛们都挤在一起，Farmer John没办法走到某一头奶牛面前让她调转方向。他能做的只有对着某一行或某一列的奶牛喊叫让她们调转方向，使得被叫到的这一行或列内的所有L变为R，R变为L。Farmer John可以对任意多的行或列发号施令，也可以对同一行或列多次发令。

就如同Farmer John想象的，他发现他不可能让他的奶牛们都朝向同一个方向。他最多能做的是让所有奶牛中除了一头之外都朝向相同的方向。请找出这样的一头奶牛。

inputFormat: 输入的第一行包含 $ N $ 。以下 $ N $ 行描述了奶牛方阵的第 $ 1 \ldots N $ 行，每行包含一个长度为 $ N $ 的字符串。

outputFormat: 输出一头奶牛的行列坐标，满足这头奶牛被调转方向的话，Farmer John就可以使他的所有奶牛都朝向同一个方向。如果不存在这样的奶牛，输出-1。如果存在多头这样的奶牛，输出其中行坐标最小的，如果多头这样的奶牛具有相同的行坐标，输出其中列坐标最小的。

hint: 在这个例子中，位于第1行第1列（左上角）的奶牛是那头令人讨厌的奶牛，因为Farmer John可以喊叫第2行和第3列来让所有奶牛都面向左侧，只有这一头奶牛面向右侧。


title: [USACO19OPEN] Cow Steeplechase II S

description:
在过去，Farmer John曾经构思了许多新式奶牛运动项目的点子，其中就包括奶牛障碍赛，是奶牛们在赛道上跑越障碍栏架的竞速项目。他之前对推广这项运动做出的努力结果喜忧参半，所以他希望在他的农场上建造一个更大的奶牛障碍赛的场地，试着让这项运动更加普及。

Farmer John为新场地精心设计了 $ N $ 个障碍栏架，编号为 $ 1 \ldots
 N $ （ $ 2 \leq N \leq 10^5 $ ），每一个栏架都可以用这一场地的二维地图中的一条线段来表示。这些线段本应两两不相交，包括端点位置。

不幸的是，Farmer John在绘制场地地图的时候不够仔细，现在发现线段之间出现了交点。然而，他同时注意到只要移除一条线段，这张地图就可以恢复到预期没有相交线段的状态（包括端点位置）。

请求出Farmer John为了恢复没有线段相交这一属性所需要从他的计划中删去的一条线段。如果有多条线段移除后均可满足条件，请输出在输入中出现最早的线段的序号。

inputFormat: 输入的第一行包含 $ N $ 。余下 $ N $ 行每行用四个整数 $ x_1,y_1,x_2,y_2 $ 表示一条线段，均为至多 $ 10^9 $ 的非负整数。这条线段的端点为 $ (x_1,y_1) $ 和 $ (x_2,y_2) $ 。所有线段的端点各不相同。

outputFormat: 输出在输入中出现最早的移除之后可以使得余下线段各不相交的线段序号。

hint: 注意：由于线段端点坐标数值的大小，在这个问题中你可能需要考虑整数类型溢出的情况。


title: [USACO19OPEN] Fence Planning S

description:
Farmer John 的 $ N $ 头奶牛，编号为 $ 1 \ldots N $ （ $ 2 \leq N \leq 10^5 $ ），拥有一种围绕“哞网”，一些仅在组内互相交流却不与其他组进行交流的奶牛小组，组成的复杂的社交网络。

每头奶牛位于农场的二维地图上的不同位置 $ (x,y) $ ，并且我们知道有 $ M $ 对奶牛( $ 1 \leq M<10^5 $ )会相互哞叫。两头相互哞叫的奶牛属于同一哞网。

为了升级他的农场，Farmer John 想要建造一个四边与 $ x $ 轴和 $ y $ 轴平行的长方形围栏。Farmer John 想要使得至少一个哞网完全被围栏所包围（在长方形边界上的奶牛计为被包围的）。请帮助 Farmer John 求出满足他的要求的围栏的最小可能周长。有可能出现这一围栏宽为 $0$ 或高为 $0$ 的情况。

inputFormat: 输入的第一行包含 $ N $ 和 $ M $ 。以下 $ N $ 行每行包含一头奶牛的 $ x $ 坐标和 $ y $ 坐标（至多 $ 10^8 $ 的非负整数）。以下 $ M $ 行每行包含两个整数 $ a $ 和 $ b $ ，表示奶牛 $ a $ 和 $ b $ 之间有哞叫关系。每头奶牛都至少存在一个哞叫关系，并且输入中不会出现重复的哞叫关系。

outputFormat: 输出满足 Farmer John 的要求的围栏的最小周长。


title: [SNOI2017] 礼物 加强版

background: 原题链接 [P5364](https://www.luogu.org/problemnew/show/P5364)

description:
热情好客的**小猴子**请森林中的朋友们吃饭，他的朋友被编号为 $1\sim n$，每个到来的朋友都会带给他一些礼物：**大香蕉**。其中，第一个朋友会带给他 $1$ 个**大香蕉**，之后，每一个朋友到来以后，都会带给他之前所有人带来的礼物个数再加他的编号的 $k$ 次方那么多个。所以，假设 $k=2$，前几位朋友带来的礼物个数分别是：

$1,5,15,37,83,\ldots$

假设 $k=3$，前几位朋友带来的礼物个数分别是：

$1,9,37,111,\ldots$

现在，**小猴子**好奇自己到底能收到第 $n$ 个朋友多少礼物，因此拜托于你了。

已知 $n,k$，请输出第 $n$ 个朋友送的礼物个数 $\bmod \ 10^9+7$。

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

outputFormat: 一个整数，表示第 $n$ 个朋友送的礼物个数 $\bmod \ 10^9+7$。


title: 【模板】模意义下的乘法逆元 2

description:
给定 $n$ 个正整数 $a_i$ ，求它们在模 $p$ 意义下的乘法逆元。

由于输出太多不好，所以将会给定常数 $k$，你要输出的答案为：
$$\sum\limits_{i=1}^n\frac{k^i}{a_i}$$

答案对 $p$ 取模。

inputFormat:
第一行三个正整数 $n,p,k$，意义如题目描述。
第二行 $n$ 个正整数 $a_i$，是你要求逆元的数。

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

hint:
对于 $30\%$ 的数据，$1\le n \le 10^5$。

对于 $100\%$ 数据，$1\le n \le 5\times 10^6$，$2\le k < p \le 10^9$，$1\le a_i < p$，保证 $p$ 为质数。

提示：本题时间限制较为严格，请注意使用较快的 IO 方式。


title: [MtOI2019] 灵梦的计算器

background:
**注: 该背景部分改编自 disangan233 中考前买计算器的真实事件。**

博丽 灵梦 (Hakurei Reimu) 在成功抢回八云 紫 (Yakumo Yukari) 用隙间偷走的香火钱后，她和依神 紫苑 (Yorigami Shion) 去香霖堂买东西啦！

灵梦想买一个计算器来计算神社的香火钱，但是因为香霖堂的东西太贵了，她选择使用河童重工网络 (Kawashiro Nitori's Network,KNN) 网购一个 Casio 计算器。

但出人意料的是，灵梦使用 KNN 买回来的 Casio 是个假货，最多只能显示整数部分（即向下取整）。

灵梦很苦恼，因为这个计算器可能会导致一些特别大的误差。所以灵梦想让拥有外界的式神(指电脑)的你帮她解决一个问题。

description:
灵梦得到了3个实数 $n$ ，$a$ ，$b$ ( $4\le n\le 5,5 \le a,b \le 10$ ) ，她成功地计算了 $n^a+n^b$，得到了一个只显示整数部分的结果。

灵梦想知道，若存在一个实数 $n'(n' \geq 0)$，使得 ${n'}^a+{n'}^b$ 的结果在计算器上与 $n^a+n^b$ 的结果显示出来**完全一致**时，$n'$ 的变化范围，即 $n'$ 的最大值与最小值之差。

如果你不知道如何计算 $n^k$，请使用`cmath`库的`pow()`函数，`pow(n,k)`的结果即为 $n^k$ 的结果。

---

为了提高本题的难度，灵梦给你设置了 $T$ 组询问。而为了在某种程度上减少你的输入和输出量，我们采用以下的代码来生成询问(代码来自河童重工)：

~~~cpp
namespace Mker
{
//  Powered By Kawashiro_Nitori
//  Made In Gensokyo, Nihon
	#define uint unsigned int
	uint sd;int op;
	inline void init() {scanf("%u %d", &sd, &op);}
	inline uint uint_rand()
	{
		sd ^= sd << 13;
		sd ^= sd >> 7;
		sd ^= sd << 11;
		return sd;
	}
	inline double get_n()
	{
		double x = (double) (uint_rand() % 100000) / 100000;
		return x + 4;
	}
	inline double get_k()
	{
		double x = (double) (uint_rand() % 100000) / 100000;
		return (x + 1) * 5;
	}
	inline void read(double &n,double &a, double &b)
	{
		n = get_n(); a = get_k();
		if (op) b = a;
		else b = get_k();
	}
}
~~~

在调用 `Mker::init()` 函数之后，你第 $i$ 次调用 `Mker::read(n,a,b)` 函数后得到的便是第 $i$ 次询问的 $n_i$, $a_i$ 和 $b_i$。

为了减少你的输出量，令第 $i$ 次询问的答案为 $s_i$，你只需要输出 $\sum^{T}_{i=1} s_i$ 。如果你的答案与标准答案的绝对误差在 $10^{-2}$ 以内，你的答案则被视为是正确答案。

本题数据的生成采用时间复杂度**远远劣于**普通算法的高 (da) 精 (bao) 度 (li) 算法来保证精度，本题数据保证**单次询问的误差**小于 $10^{-10}$，**所以本题的SPJ范围对于正解来说是完全足够的。**

---

为了让你更好地做题，这里给出了关于 $op$ 的说明：

* 当 $op=1$ 时，有 $a=b$，否则无特殊限定。

inputFormat: 输入共一行，包含 $3$ 个正整数  $T$，$seed$，$op$，含义见题目描述。

outputFormat: 输出共一行，输出题目描述中要求输出的答案。

hint:
### 子任务

![QQ图片20190707214000.png](https://i.loli.net/2019/07/07/5d21f64bc09c827059.png)

### 题目来源

[迷途之家2019联赛](https://www.luogu.org/contest/20135)(MtOI2019) T2

出题人：disangan233

验题人：suwakow


title: 基于值域预处理的快速 GCD

background: 模板题，无背景。

description:
给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$，再给定 $n$ 个正整数 $b_1,b_2,\dots,b_n$，你需要对每对 $(i,j)$ 求出 $a_i$ 与 $b_j$ 的最大公因数。

不难发现你的输出应有 $n^2$ 个正整数。为了减少输出对程序的运行效率的影响，你只需要输出 $n$ 行，每行一个整数 $A_i$。

其中对于 $i\in[1,n]$，$A_i=\sum_{j=1}^{n}i^j\gcd(a_i,b_j)$。由于答案可能过大，你只需要输出模 $998,244,353$ 后的结果即可。

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

第二行 $n$ 个正整数，表示 $a_1,a_2,\dots,a_n$。

第三行 $n$ 个正整数，表示 $b_1,b_2,\dots,b_n$。

outputFormat: 共 $n$ 行，第 $i$ 行应输出一个非负整数 $A_i$。意义见题目描述。

hint:
对于 $20\%$ 的数据，$1\leqslant n\leqslant 500$。

对于 $100\%$ 的数据，$1\leqslant n\leqslant 5000;1\leqslant a_i,b_i\leqslant 10^6$。

**请注意常数因子对程序运行效率的影响**


title: A/B Problem（高精度除法）

description:
给你两个正整数 $a,b$，求 $\lfloor a/b \rfloor$。
为了卡掉一些乱搞做法，你需要对答案进行如下处理：
设答案为 $r$，构造一个多项式 $F(x)$：

$$ F(x) = \sum\limits_{i=0}^{\lfloor \lg r \rfloor} (\lfloor 10^{-i}r \rfloor \bmod 10) \cdot x^i$$

简单地说，就是从 $r$ 的低位到高位，每一位对应 $F(x)$ 一项的系数。

设 $F(x)$ 的最高非零次数为 $n$，你需要求出一个 $n$ 次多项式 $G(x)$，使得：
$$ F(x) \cdot G(x) \equiv 1 \pmod{x^{n+1}}$$
将 $G(x)$ 的系数对 $998244353$ 取模，然后升幂输出 $G(x)$ 的系数即可。

保证满足条件的 $G(x)$ 存在。

inputFormat: 两行，每行一个正整数，分别为 $a$ 和 $b$。

outputFormat: 输出一行 $n+1$ 个整数，为 $G(x)$ 的系数


title: 月宫的符卡序列

description:
**update：重新构造了两组数据，数据已加强**

辉夜原本是生活在月宫的月之公主

辉夜在淸理永远亭的仓库时，发现了一个古老的符卡序列 $S$，可能是很久很久以前的辉夜仍生活在月宫时创造的，但现在的她已经回忆不起来了。

于是辉夜便决定对这个符卡序列进行研究，$S$ 中的符卡从0开始标号，并且辉夜创造它时使用的卡组大小不超过26,因此符卡被表示成了字母 $a$ 到字母 $z$。

辉夜对从左往右读和从右往左读都一样的序列很感兴趣，对于$S$的某个满足上述条件连续子序列$a$,其价值为$a$在$S$中的所有出现位罝中点（即若a出现在$l...r$，那么中点为$\lfloor  \frac{l+r}{2} \rfloor $）的异或值。

辉夜想知道对于所有满足条件的$a$，最大的价值是多少

inputFormat:
第一行一个整数$num$($≤5$)，表示数据组数

每组数据占一行，有一个仅有小写字母的字符串$S$，表示符卡序列

outputFormat: 对于每组数据，输出一行，表示辉夜想知道的答案


title: 有标号荒漠计数

background: 众所周知 仙人掌计数 是一种很简单的计数，所以我们要加强它.jpg

description:
仙人掌是一张无向连通图，在一个仙人掌上，任意一条边至多只会出现在一个环上。同时，在本题定义的仙人掌中，仙人掌应当**无重边**、**无自环**。
荒漠是一张无向图，一个荒漠的每个极大连通分量都是一个仙人掌

---
给出一个整数 $n$ ，请求出有多少种不同的含有 $n$ 个点的荒漠。（点有标号）

由于答案可能太大，您只需要将您的结果对 $998244353$ 取模后输出即可。

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

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

hint:
对于样例，所有可能的情况如下：
![Picture](https://s2.ax1x.com/2019/06/13/Vf6SGF.png)
可以发现，不存在更多的荒漠

---
对于 $30\%$ 的数据： $n\leqslant5000$
对于 $100\%$ 的数据： $3\leqslant n\leqslant100000$


title: 【XR-2】缘分

background: > 世间万物都置身于缘分编织的大网中。缘分未到，虽历经千劫，却不能相遇。缘分到了，在草原上都能等到一艘船。——《一禅小和尚》

description:
一禅希望知道他和师父之间的缘分大小。可是如何才能知道呢？

一禅想了个办法，他先和师父约定一个正整数 $n$，接着他们各自在心里想一个不超过 $n$ 的正整数。

一禅认为，他和师父心里想的这两个数的**最小公倍数**越大，则意味着他和师父之间的缘分越大。

师父觉得这个办法很合适，不过他想知道这两个数的最小公倍数最大会是多少。

师父的数学不太好，于是问一禅。一禅也觉得这个问题很困难，他希望你能告诉他答案。

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

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

接下来的 $T$ 行，每行一个正整数 $n$，表示一禅和师父约定的正整数。

outputFormat: 对每组数据，一行一个正整数，表示答案。

hint:
【样例 $1$ 说明】

不超过 $3$ 的两个正整数的最小公倍数的最大值为 $\mathrm{lcm}(2,3) = 6$。

【数据规模与约定】

对 $50\%$ 的数据，$1 \le T,n \le 100$。

对 $100\%$ 的数据，$1 \le T \le 100, 1 \le n \le 10^9$。


title: 【XR-2】奇迹

background: > 相信奇迹的人，本身就和奇迹一样了不起。——笛亚 《星游记》

description:
我们称一个**日期**为一个八位数，第 1~4 位构成年，第 5~6 位构成月，第 7~8 位构成日，不足位数用 0 补足。同时，要求日期所代表的这一天真实存在，且年的范围为 1~9999。

出现奇迹的日期都存在相同的特点：由“日”组成的两位数，由“月+日”组成的四位数，由“年+月+日”组成的八位数均为**质数**。但并不是所有存在这样特点的日期都一定会出现奇迹。

现在，你得到了一个可能会出现奇迹的日期，然而不幸的是这个日期却是残缺的，八位中可能有若干位无法确定。你需要知道这个日期有多少种可能，这样你才能做好充足的准备去迎接奇迹的到来。

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

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

接下来的 $T$ 行，每行一个八位字符串。其中第 $i$ 位如果为 `-`，则表示日期的第 $i$ 位无法确定，否则表示日期的第 $i$ 位为字符串中第 $i$ 位上的数字。

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


title: 【XR-2】伤痕

background: > 长日尽处，我来到你的面前，你将看见我的伤痕，你会知晓我曾受伤，也曾痊愈。——泰戈尔《深爱你这城》

description:
X 国经历了一场前所未有的大地震，人们伤痕累累，整个国家破碎不堪。

为了帮助人们痊愈，也为了让 X 国能够生存下去，X 国国王决定重建 X 国。

国王决定先建造 $n$ 座城市，由于国王喜欢奇数，所以 $n$ 为奇数。

城市建造完后，需要给每两座城市之间都修建一条道路，即一共需要修建 $\frac{n(n-1)}{2}$ 条道路。

不过，修建双向道路的成本太高了，建造完 $n$ 座城市后剩下的经费最多只够修建 $n$ 条双向道路，而其余的道路只能修建成单向的。好在方向并不会影响修建单向道路所需的费用，因此所有单向道路的方向可以任意决定。

另外，等到重建完成后，国王决定将 $4$ 座城市钦定为 X 国的核心城市。为促进 X 国的发展，这 $4$ 座核心城市中的任意两座城市，必须能够在不经过非核心城市的情况下相互到达。

国王希望，你能够给他一种道路修建方案，使重建完成后选择 $4$ 座核心城市的方案数最大化。

inputFormat: 一行一个正整数 $n(1 \le n \le 99)$，保证 $n$ 为奇数，表示有 $n$ 座城市。

outputFormat:
第一行包含一个整数，表示最大的选择 $4$ 座核心城市的方案数。

接下来的 $n$ 行每行 $n$ 个正整数描述一个邻接矩阵，表示你的道路修建方案。

具体来说，第 $i$ 行的第 $j$ 个数为 $1$ 表示第 $i$ 座城市可以通过一条道路到达第 $j$ 座城市，为 $0$ 表示第 $i$ 座城市无法通过一条道路到达第 $j$ 座城市。我们分为 $3$ 种情况详细说明：

1. $i, j$ 之前的道路为一条 $i$ 到 $j$ 的单向道路，则邻接矩阵的第 $i$ 行第 $j$ 个数为 $1$，第 $j$ 行第 $i$ 个数为 $0$。
2. $i, j$ 之间的道路为一条双向道路，则邻接矩阵的第 $i$ 行第 $j$ 个数和第 $j$ 行第 $i$ 个数均为 $1$，你需要保证最多修建 $n$ 条双向道路。
3. $i = j$，则第 $i$ 行第 $j$ 个数（第 $j$ 行第 $i$ 个数）为 $0$。

hint:
【样例 $1$ 说明】

由于一共只有 $3$ 个点，所以选择 $4$ 座核心城市的方案数一定为 $0$，那么只需要保证修建方案满足条件即可。

【样例 $2$ 说明】

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

显然，在 $5$ 个点中任意选 $4$ 个点，都满足核心城市的条件，因此方案数最大为 $5$。

【数据规模与约定】

本题一共有 $50$ 个测试点，每个测试点 $2$ 分。对于第 $i$ 个测试点，$n = 2i - 1$。

对于每个测试点，有五种可能的结果：

1. 输出格式错误，包括：没有输出最大方案数、没有输出邻接矩阵、输出了多余的信息等。你将无法得到该测试点的任何分数，同时我们无法确定 Special Judge 的返回结果。
2. 没有正确计算最大方案数，即使构造的道路修建方案是正确的。你将得到该测试点 $0\%$ 的分数（即 $0$ 分），Special Judge 将会返回 WA 的结果，同时输出 “The answer is wrong.”
3. 正确计算了最大方案数，但是构造的道路修建方案不满足条件，包括：邻接矩阵中有不为 $0$ 或 $1$ 的数、有自环、有两座城市中没有道路、有多于 $n$ 条双向道路等。你将得到该测试点 $50\%$ 的分数（即 $1$ 分），Special Judge 将会返回 WA 的结果，同时输出 “The answer is correct, but your plan breaks the rules.”
4. 正确计算了最大方案数，构造的道路修建方案满足条件但没有将选择 $4$ 座核心城市的方案数最大化。你将得到该测试点 $50\%$ 的分数（即 $1$ 分），Special Judge 将会返回 WA 的结果，同时输出 “The answer is correct, but your plan is wrong.”
5. 正确计算了最大方案数，同时正确构造了道路修建方案。你将得到该测试点 $100\%$ 的分数（即 $2$ 分），Special Judge 将会返回 AC 的结果，同时输出 “The answer is correct.”


title: 【XR-2】约定

background:
>「小圆，不要走！这一分离，我们何时才能重逢？」
>
>「小焰，我们一定还会相见的！在那之前，我们只是短暂的离别啊......」

description:
只因为那一句约定，小焰开始了看不到尽头的等待。

约定在小焰心中幻化成了一张 $n$ 个点的图。一开始，这是一张完全图，其中点的编号从 $1$ 到 $n$，连接点 $i,j$ 的边的权值为 $(i+j)^k$。

然而等待的过程中，岁月也在逐渐消磨着她的信仰，因此图中的一些边被随机地删掉了。最终，图变成了一棵 $n$ 个点的树，永远地留在了小焰的心中。

很久很久以后，小焰的魔力耗尽，在痛苦与绝望之中濒临崩溃。而就在这时，小圆终于来找小焰了。为了拯救自己唯一的朋友，她必须知道这棵树边权和的期望值对 $998244353$ 取模的结果是多少。

你能帮小圆求出答案，让她完成那个约定吗？

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

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

hint:
【样例 $1$ 说明】

这个完全图有 $3$ 个节点，$3$ 条边，形成了一个环。
这些边的权分别为：$3,4,5$
最后形成的树也有 $3$ 种可能，权值分别为：$7,8,9$
期望值为 $8$。

【数据规模与约定】

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

Subtask 1（5 points）：$1 \le n \le 5$，$1\le k \le 10$。
Subtask 2（11 points）：$k = 1$。
Subtask 3（11 points）：$1 \le n,k \le 20000$。
Subtask 4（13 points）：$1 \le n,k \le 10^5$。
Subtask 5（23 points）：$1 \le k \le 10^5$。
Subtask 6（37 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le n \le 998244352,1\le k \le 10^7$。
****
>「抱歉，让你久等了...... 你一直努力到了今天吧......」
>
>「小圆......」
>
>「来，我们走吧。今后我们永不分离......」
>
>「是啊，我等这一刻——望眼欲穿。」


title: 【XR-2】记忆

background: > 过去就像攥在手中的一把干沙，自以为攥得很紧，其实早就从指缝中流光了。记忆是一条早已干涸的河流，只在毫无生气的河床中剩下零落的砾石。——刘慈欣 《三体》

description:
你的记忆被歌者拿走了。

临走前，歌者告诉你，你的记忆中有一个序列，而且这个序列是所有 $l \le x \le r$ 的整数 $x$ 形成的一个排列。

歌者想了想，决定再告诉你一点信息：

如果把一个序列的权值定义为这个序列中相邻两个数的乘积为完全平方数的数量，那么你记忆中的这个序列是所有 $l \le x \le r$ 的整数 $x$ 形成的排列中**权值最大**的排列。

歌者希望你能够把你记忆中的这个序列的权值告诉他，他才会把属于你的记忆还给你。

inputFormat: 一行两个正整数 $l,r$。

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

hint:
【样例 $1$ 说明】

一个满足权值为 $2$ 的排列为 $\{8,2,4,9,3,10,7,5,6\}$，其中 $8 \times 2 = 16, 4 \times 9=36$ 为完全平方数。这也是所有 $2 \le x \le 10$ 的整数 $x$ 形成的排列中权值最大的排列。

【数据规模与约定】

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

Subtask 1（3 points）：$r \le 10$。
Subtask 2（7 points）：$r \le 100$。
Subtask 3（15 points）：$r \le 100000$。
Subtask 4（11 points）：$l = 1$。
Subtask 5（8 points）：$l \le 10$。
Subtask 6（19 points）：$l \le 1000000$。
Subtask 7（37 points）：无特殊限制。

对于 $100\%$ 的数据，$1 \le l \le r \le 10^{14}$。


title: 【XR-2】永恒

background: > 我一直认为这世界没有永恒，如果非要说永恒，宇宙间唯一的永恒就是——所有的一切都会随着时光消失。——梧桐《那片星空，那片海》

description:
有一颗 $n$ 个点的永恒的树，树中每个点 $x(1 \le x \le n)$ 上都有一个永恒的字符串 $S(x)$。

但这世界没有永恒，所有的一切都会随着时光消失。我们只能给每个所谓永恒的东西定义一个永恒值 $f$。这个值本身没有意义，只是一个象征罢了。

- 一个字符串 $S$ 的永恒值 $f(S)$ 定义为它的长度 $\mathrm{Len}(S)$，即：

$$f(S) = \mathrm{Len}(S)$$

- 树上的一条无向路径 $K = [u, v](u < v)$ 指的是 $u,v$ 之间的简单路径（包括 $u, v$），其永恒值 $f(K)$ 定义为路径上所有不同的无序点对 $(x, y)(x \in K, y \in K, x < y)$ 上的字符串 $S(x), S(y)$ 的最长公共前缀 $\mathrm{LCP}(S(x), S(y))$ 的永恒值 $f(\mathrm{LCP}(S(x), S(y)))$ 之和，即：

$$f(K) = \sum_{x \in K, y \in K, x < y} f(\mathrm{LCP}(S(x), S(y)))$$

- 一颗树 $T$ 的永恒值 $f(T)$ 定义为树上所有的无向路径 $[u, v](u \in T, v \in T, u < v)$ 的永恒值之和，即：

$$f(T) = \sum_{u \in T, v \in T, u < v} f([u,v])$$

特别的是，树中每个点上的字符串都来自一颗永恒的以点 $1$ 为根的 Trie 树，即每个树中的点都对应着一个 Trie 树中的点，点上的字符串就是 Trie 树中从根节点到其对应的点形成的字符串。

你需要求出这棵树的永恒值，答案对 $998244353$ 取模。

inputFormat:
第一行包含两个正整数 $n,m$，分别表示树的节点数和 Trie 树的节点数。

第二行包含 $n$ 个非负整数，第 $i$ 个数为 $a_i$，表示点 $i$ 在树上的父亲节点为 $a_i$，对于树的根节点 $root$，保证 $a_{root} = 0$。

第三行包含 $m$ 个非负整数，第 $i$ 个数为 $b_i$，表示点 $i$ 在 Trie 树上的父亲节点为 $b_i$，保证 $b_i < i$，$b_1=0$。

第四行为一个由 $m$ 个字符构成的字符串，第 $i$ 个字符 $c_i$ 表示 Trie 树上点 $i$ 与它的父亲节点 $b_i$ 之间的边所代表的字符，保证 $c_1=\texttt{0}$，$c_i(2 \le i \le m)\in[\texttt{a},\texttt{z}]$。

第五行包含 $n$ 个正整数 $d_i$，表示树上的点 $i$ 对应着 Trie 树上的点 $d_i$，保证 $2 \le d_i \le m$。

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

hint:
【样例 $1$ 说明】

所有的 $S(x)$ 为：

$S(1) = \texttt{"mayqueen"}$

$S(2) = \texttt{"mayking"}$

$S(3) = \texttt{"market"}$

所有的 $f(\mathrm{LCP}(S(x), S(y)))$ 为：

$f(\mathrm{LCP}(S(1), S(2))) = f(\mathrm{LCP}(\texttt{"mayqueen"}, \texttt{"mayking"})) = f(\texttt{"may"}) = \mathrm{Len}(\texttt{"may"}) = 3$

$f(\mathrm{LCP}(S(1), S(3))) = f(\mathrm{LCP}(\texttt{"mayqueen"}, \texttt{"market"})) = f(\texttt{"ma"}) = \mathrm{Len}(\texttt{"ma"}) = 2$

$f(\mathrm{LCP}(S(2), S(3))) = f(\mathrm{LCP}(\texttt{"mayking"}, \texttt{"market"})) = f(\texttt{"ma"}) = \mathrm{Len}(\texttt{"ma"}) = 2$

所有的 $f([u, v])$ 为：

$f([1,2]) = f(\mathrm{LCP}(S(1), S(2))) = 3$

$f([1,3]) = f(\mathrm{LCP}(S(1), S(2))) + f(\mathrm{LCP}(S(1), S(3))) + f(\mathrm{LCP}(S(2), S(3))) = 3 + 2 + 2 = 7$

$f([2,3]) = f(\mathrm{LCP}(S(2), S(3))) = 2$

所以：

$f(T) = f([1,2]) + f([2,3]) + f([1,3]) = 3 + 7 + 2 = 12$

【数据规模与约定】

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

Subtask 1（3 points）：$n, m \le 10$，时限 1s。
Subtask 2（5 points）：$n, m \le 100$，时限 1s。
Subtask 3（9 points）：$n, m \le 1000$，时限 1s。
Subtask 4（7 points）：$n, m \le 5000$，时限 2s。
Subtask 5（9 points）：$n, m \le 20000$，时限 3s。
Subtask 6（11 points）：$n, m \le 10^5$，时限 4s。
Subtask 7（19 points）：$m=2$，时限 3s。
Subtask 8（37 points）：无特殊限制，时限 10s。

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


title: [MtOI2019] 埋骨于弘川

background:
在幻想乡中，冥界的樱花一年又一年地往复开放。

在 Yuyuko 的心中，出现了一棵樱花树，一个与花朵息息相关的序列，和一个伤感的问题。

那些曾经奋斗过的 OIer 们啊，如今又在何方呢？

description:
在幻想乡，西行寺 幽幽子(Yuyuko)是一个以贪吃著名的亡灵，她拥有操纵死亡的能力。

Yuyuko 通过外界的式神——电脑，对OI进行了深刻的研究 ，她发现了一些惊人的事实：

* OIer 们放弃了太多其他同学们拥有的东西，在题海中寻求自己的梦想。

* 但是 AFO 的 OIer 们，跟死亡又有什么区别呢？他们或许已经失去了自己的梦想……

这时幽幽子发现，天空中飘舞的樱花组成了两个整数 $n$，$k$。于此同时，在樱花树下，出现了一个函数 $f(x,y)$ 的描述：

$$f(x,y) = \begin{cases} 2 & , x=1 \\ 2^x& , 2\le x \le 42,y = 0 \\ \prod\limits_{i=1}^{42} f(x-i,y)^i & , x \ge 43,y = 0 \\ f(x-1,y)f(x,y-1) & , x\ge 2,y \ge 1\end{cases}$$

幽幽子想让你计算出 $f(n,k) \bmod 998244353$，她认为这个函数象征着OIer们......

inputFormat: 两个整数 $n,k$

hint:
【样例 $1$ 解释】

根据定义，$f(1,1926)=2$。

【数据范围与约定】

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

Subtask 1 (7 points)：$1\le n,k \le 1000$
Subtask 2 (11 points)：$1\le n \le 10^{18}$，$k=0$
Subtask 3 (13 points)：$1\le n \le 10^{18}$，$k=1$
Subtask 4 (29 points)：$1\le n \le 10^{18}$，$0\le k \le 1000$
Subtask 5 (40 points)：无特殊限制

对于 $100\%$ 的数据：$1\le n \le 10^{18}$，$0\le k \le 30000$

### 题目来源

[迷途之家2019联赛](https://www.luogu.org/contest/20135)(MtOI2019) T6

出题人：NaCly_Fish

验题人：Imagine

题面：disangan233

**此题稍有卡常，请注意优化代码常数。**


title: [Cnoi2020] 线形生物

background:
> 为了能够在冥界过上这种愉快的生活而不是被判入地狱，人类们摒弃了自行结束生命的做法，拼尽全力地生活着。如此看来，人类似乎也显得有些积极与可爱了呢。  （射命丸 文）

线形生物沿着一维的阶梯向着冥界单向地前行着。

照这样的话，它只需要一级一级地，走 $n$ 步就能够到达白玉楼。

但 Cirno 觉得这样太单调了，于是，一维的壁垒被打破，链状的道路生出了花椰菜状的枝桠。

description:
线形生物要从 $1$ 号台阶走到 $n+1$ 号台阶。

最开始，$1,2,3,\ldots,n$ 号台阶都有一条连向下一台阶的有向边 $i\rightarrow i+1$。

之后 Cirno 加入了 $m$ 条**返祖边** $u_i \rightarrow v_i (u_i \ge v_i)$，它们构成了一个**返祖图**。

线形生物每步会 **等概率地** 选取当前台阶的一条出边并走向对应的台阶。

当走到 $n+1$ 号台阶时，线形生物就会停止行走。

同时，Cirno 会统计线性生物总共走的步数，记作 $\delta$。

Cirno 想知道 $E(\delta)$（即 $\delta$ 的**数学期望**）对 $998244353$ 取模后的结果。

inputFormat:
第一行三个整数 $id$，$n$，$m$。

以下 $m$ 行，每行两个整数 $u_i$，$v_i$。

$id$ 表示 subtask 编号，其它字母含义同上文。

outputFormat: 一行，一个整数 $E(\delta)$，字母含义同上文。

hint:
## 后置数学知识
 - **可能用到的幂级数求和** : 若 $x>1$，则有 $\sum\limits_{i=1}^{\infty}\big(\frac{1}{x}\big)^i=\frac{1}{x}+\frac{1}{x^2}+\frac{1}{x^3}+\cdots=\frac{1}{x-1}$。
 - **数学期望** : 随机试验中每次可能结果的概率乘以其结果的总和，反映随机变量平均取值的大小。
 - **离散期望公式** : $E(x)=\sum\limits_{k=1}^{\infty}x_kp_k$。

## 数据范围与约定

对于 $100\%$ 的数据，保证：$id \in \{1,2,3,4,5\}$，$0 < n,m \le 10^6$，$1 \le v_i \le u_i \le n$。

#### 子任务「本题采用捆绑测试」

 - Subtask1（$10\%$）: 返祖图中所有点都有自环且所有边均为自环(未画出)，总图形如 :
 ![](https://cdn.luogu.com.cn/upload/image_hosting/6fikv6ft.png)

 - Subtask2（$10\%$）: 返祖图中所有点均向且仅向自己的前驱连边，特别地，$1$ 号节点的前驱是 $1$ 号节点，总图形如 :
   ![](https://cdn.luogu.com.cn/upload/image_hosting/6rc9dazb.png)

 - Subtask3（$10\%$）: 返祖图中所有点均向且仅向 $1$ 号节点连边，总图形如 :
 ![](https://cdn.luogu.com.cn/upload/image_hosting/wup1ctvu.png)

 - Subtask4（$10\%$）: $n \le 100$，$m \le 1000$。

 - Subtask5（$60\%$）: 无特殊限制。

 ## 后记

  题目名称出自 th17 东方鬼形兽 6 Boss 埴安神袿姬 Hard / Lunatic 难度符卡 線形「リニアクリーチャー」。


title: [THUPC2018] 绿绿和串串

background: 绿绿和 Yazid 是好朋友。他们在一起做串串游戏。

description:
绿绿有一个由小写字母组成的非空字符串 $R$，但 Yazid 不知道它具体是什么。

我们定义**翻转**的操作：把一个串以最后一个字符作对称轴进行翻转复制。形式化地描述就是，如果他翻转的串为 $R$，那么他会将前 $\left| R\right|-1$ 个字符倒序排列后，插入到串的最后。

举例而言，串`abcd`进行翻转操作后，将得到`abcdcba`；串`qw`连续进行 **$2$ 次**翻转操作后，将得到`qwqwq`；串`z`无论进行多少次翻转操作，都不会被改变。

贪玩的绿绿进行了若干次（可能为 $0$ 次）翻转操作。

淘气的绿绿又展示出了一个非空串 $S$，并表示 $S$ 是**最终**的串 $R$ 的前缀。现在，他想考考 Yazid，**初始**的串 $R$ 的长度可能是多少。

Yazid 找到了正在参加清华校赛的你，请你来帮他解决这个问题。但聪明的 Yazid 发现，所有超过 $\left| S\right|$ 的整数都一定是 $R$ 的可能长度，因此你只需要告诉他不超过的 $\left| S\right|$ 的 $R$ 的可能长度即可。

为了帮助你理解问题，Yazid 还将对一些概念和记号做出解释：

- 对于一个串 $S$，$\left| S\right|$ 表示的是该串的长度。
- 对于一个串 $S$，我们定义串 $T$ 是它的前缀，当且仅当 $\left| T\right|\leq\left| S\right|$，且对于任意整数 $i$ 满足 $1\leq i\leq\left| T\right|$，都有 $T$ 的左起第 $i$ 个字符与 $S$ 的左起第 $i$ 个字符相同。（形象地理解，即 $T$ 在 $S$ 的前部出现）
  - 如：`abc`是`abcdefg`的前缀，`aba`**不**为`abba`的前缀，`z`为`z`的前缀，空串为任意一个串的前缀。

inputFormat:
输入包含多组数据，第一行一个整数 $T$ 表示数据组数。接下来依次描述每组数据，对于每组数据：

* 一行一个仅由小写字母组成的非空字符串 $S$。

outputFormat:
对于每组数据，输出 $1$ 行：

* 从小到大输出 $\left| R\right|$ 的所有不超过 $\left| S\right|$ 的可能值，所有值之间用单个空格隔开。

hint:
### 数据范围

保证 $\left| S\right|\leq 10^6$，$\sum\left| S\right|\leq 5\times 10^6$。

$\sum\left| S\right|$ 表示的是单个测试点中所有数据 $\left| S\right|$ 的总和。

### 提示

* 读入规模较大，请注意读入效率。

* 样例中的最后一个字符串是什么意思呢？

### 版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai/) 对此次比赛的支持。

题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。


title: [THUPC2018] 赛艇

description:
Lavender、Caryophyllus、Jasmine、Dianthus现在在玩一款名叫“赛艇”的游戏。

这个游戏的规则是这样的：

1. 玩家自由组成两队，一个人当赛艇的艇长，另一个人当侦察兵；
2. 每次游戏开始时，双方均拥有由系统生成的某张地图，该地图以01矩阵的形式表示，`1`表示有障碍物，无法通行，`0`表示水域空旷，可以通行；
3. 第一回合，双方的赛艇艇长都要在地图上指定一个出发点，该出发点不能是障碍物，也就是只能为`0`；
4. 在每个回合中，艇长可以指挥自己的赛艇向上/下/左/右四个方向的某一方向的空旷水域移动一个单位的距离，也就是说只能移向四个方向上的某个`0`上（当然，不能移动出地图之外）；在该操作完成之后，**必须向对方说出自己在该回合移动的方向**；
5. 双方的侦察兵负责记录每一回合对方赛艇的移动方向，并负责推断此时对方赛艇可能的位置；如果某方的侦察兵推测出对方赛艇此时的精确位置，那么可以向其发射导弹，该侦察兵所在的一方胜利；

现在，Jasmine记录了一些对方赛艇的路径，她想确定一下此时对方所有可能的位置共有几种。由于她不是很擅长计算，所以这个任务就交给你了。

inputFormat:
输入第一行包含三个正整数 $n$，$m$，$k$，分别表示地图为 $n$ 行 $m$ 列，当前游戏已经进行了 $k$ 轮。保证 $2\le n,m \le 1500$，$1\le k\le 5\times 10^6$。

输入第二行到第 $n+1$ 行为一个 $n$ 行 $m$ 列的 01 矩阵，无任何分隔符号，表示地图的具体信息，具体含义如上所示。

输入的最后一行为一个长度为 $k$ 的字符串 $s$，仅由字母 `w`、`a`、`s`、`d` 构成，从前往后第 $i$ 个字符 $s_i$ 表示对方在第 $i$ 轮中，对方赛艇向上/左/下/右移动一个单位距离。

outputFormat: 输出一行一个正整数，表示在第 $k$ 轮游戏回合的时候，对方赛艇可能的位置的种数。对于所有输入数据，**保证有合法解**。

hint:
### 样例解释

![](https://i.loli.net/2018/05/14/5af98ebcd79df.png)

上图显示了路径序列可视化之后的结果，下图用蓝色标出了此时对方赛艇可能的位置。

![](https://i.loli.net/2018/05/14/5af98ed39a602.png)

### 版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai/) 对此次比赛的支持。

题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。


title: [THUPC2018] 好图计数

background:
这道题目非常简单，它甚至没有题目背景、没有任何故事。

但为了能让你顺利理解题目，善良的 Yazid 将为你介绍一些概念。

* 简单图：不存在重边、自环的图。（重边即为两条完全相同的边，自环即为两端点为同一节点的边）

* 补图：一个图 $G$ 的补图有与 $G$ 完全相同的节点，且任意两点之间有边当且仅当他们在 $G$ 中不相邻。

description:
我们归纳定义一个无向简单图是**好的**：

1. 一个单点是好的。

2. 若干个好的图分别作为联通块所形成的图是好的。

3. 一个好的图的补图是好的。

给定一个正整数 $n$。

求 $n$ 个点的本质不同的好的图的数量对质数 $P$ 取模的结果。（这里的 $P$ 是一个常数，具体见【输入格式】）

两个好的图的被认为是**本质不同的**，当且仅当无论如何将一个图重标号，它都不能与另一个图完全相同。

inputFormat:
输入包含多组数据，第一行 $2$ 个用空格隔开的整数 $T,P$ 分别表示数据组数、以及模数。接下来依次描述每组数据，对于每组数据：

* 一行一个整数 $n$，表示希望统计数目的好的图的节点数。

outputFormat:
对于每组数据，输出 $1$ 行：

* 一个整数，表示 $n$ 个节点的好的图的数目对 $P$ 取模的结果。

hint:
### 样例解释

下面是 $3$ 个点的所有好的图：

![](https://i.loli.net/2018/05/14/5af990dbcfbc0.png)

### 数据范围

保证 $T\leq 233$，$n\leq 23333$，$2^{29} < P < 2^{30}$ 且保证 $P$ 为质数。

### 提示

能够通过本题的算法的时间复杂度可能比你想象的要糟糕一些、也可能比你想象的要优秀一些。

### 版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai/) 对此次比赛的支持。

题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。


title: [Ynoi2010] Fusion tree

background:
题目背景和题意无关，可以跳过

## 1.前言：
Fusion Tree，中文译作融合树，是一种亚log的数据结构，与1993年由Michael L.Fredman和Dan E.Willard提出。

用途：$O( \log n/ \log w+ \log w )$时间复杂度支持插入，删除，前驱，后继，min，max，以及用于整数排序。

信息论断言对$n$个数的排序在最坏情况下需要$n\log n$次比较，不过对这个界我们还需要一些研究。

有人证明了任意unit cost RAM算法，其中只包含加法，减法，乘法，和0比较（但是不包含除法和位运算）最坏情况下需要$\Omega(n\log n)$的时间去对$n$个数排序。

如果允许使用除法和位运算，他们有一个线性时间复杂度的算法，但是这个算法对unit cost滥用。

这里我们规定我们使用的计算模型的字长是w，每个输入的数都是在$[0,2^w-1]$中的整数。

## 2.一些记号：
对于一个集合$S$和一个整数$x$，定义$rank(S,x)$为S集合中$\le x$的元素个数。
对于一些非负整数$a$，定义$bin(a_1,...,a_n)=2^{a_i}+...+2^{a_n}$。

对于两个非负整数$a,b$，定义$msb(u,v)$为$u$和$v$最高的不相同的位。

## 3.概述：
Fusion Tree大概可以看做是一棵特殊的B-Tree，特性：

1. 叉数$B=O(w^{1/5})$

2. 在一次搜索时，每个在搜索路径上的节点的正确的儿子可以被$O(1)$确定

从这些特性我们可以看出Fusion Tree单次操作的时间复杂度是$O( \log _w(n) + \log w) = O( \log n/\log w +\log  w)$的，比$O( \log n )$低。

但是由于其实现方式，Fusion Tree每次对内部节点的更新复杂度是$O( B^4 )$的。
为了控制Fusion Tree均摊的更新复杂度，我们将这棵B-Tree的每对叶子节点之间的部分替换为一个大小大约为$O( B^4 )$的Weight Balanced Tree，只在WBT根节点发生变化的时候更新Fusion Tree的内部节点。

具体来说，我们B-Tree维护的是一个排序后的数组的分块，其中每个块都由一棵平衡二叉搜索树维护，fusion tree上只维护一个值来表示块边界，用途是指引每次插入，删除，查询在哪个块中。

可以发现这样我们把内部节点的变化次数除掉了一个$B^4$。

## 4.压缩key的表示：

如何$O(1)$确定搜索路径上的一个节点的正确的儿子：

考虑一个B-Tree的节点，其上面包含了$k$个key，其中$B/2 \le k \le B$，记作$S={u_1,u_2,...u_k}$。

然后我们定义出$B(S)$表示"有区别的位的位置"，用人话来说就是我们把这$k$个key的trie建出来，然后所有有超过$1$个儿子的节点的高度构成的集合
（当然这里我们不用把trie建出来，只是这么解释比较直观，而且更能反映出其的一些性质）。

再定义一个集合$K(S)$，为$S$只保留$B(S)$中那些位之后的值，记作$K(S)={u'_1,u'_2,...u'_k}$，发现这个压缩操作对于原集合是保序的。

对于一个任意的$w-bit$的数$u$，我们记$u'(S)$表示$u$只保留$B(S)$中那些位，即把非$B(S)$中的位都置为$0$之后的值。

下面引理表达了一个压缩key的重要性质：

### 引理1：
设$B(S)$排序后为$c_1<c_2<...<c_r$，定义边界$c_0=-1,c_{r+1}=b$。

定义$u'_i$为$K(S)$中任意的一个压缩后的key。

对于一个任意的$w-bit$的数$u$，满足$u \neq u_i$，

设$msb(u'(S),u'_i)=c_m$，即$u$和$u_i$在bit位置$c_{m+1},...,c_r$位置处相等，但是在$c_m$处不相等，如果$u'(S)=u'_i$，则我们记$m=0$。

如果$u$和$u_i$不同的最高位$p$满足$p>c_m$，那么我们可以通过：

1. 唯一的一个区间$[c_{j-1},c_j]$满足$p$属于这个区间

2. $u$和$u_i$的大小关系

来确定$rank(S,u)$的值。

证明平凡，把trie画出来，显然可以画成一个平面图，然后可以发现这两个可以唯一地确定出一个平面区域，这个区域中的$S$集合元素个数就是$rank(S,u)$（感觉这种东西光写一堆自然语言也不能说明正确性，需要形式化证明一下？）。

注意到这个引理虽然是对任意$u_i$成立的，但是要求$u$和$u_i$不相同的最高位不是$B(S)$中的一个点，可以发现这个$u_i$其实必须在$u$"脱离"这个trie的位置，也就是$p$的父亲子树中。

引理$1$使得我们可以将$rank(S,u)$的计算规模降低到$rank(K(S),u'(S))$，通过计算$rank(K(S),u'(S))$，我们可以确定$u'(S)$在$K(S)$中的前驱后继$u'_j$和$u'_{j+1}$（这两个值不一定存在，但经过平凡的讨论就可以解决。

如果$u_j \le u \le u_{j+1}$，那我们已经解决了这个问题
否则我们令$i=j$或者$i=j+1$，计算出$msb(u_i,u)=p$，然后只要我们知道了包含$p$的区间$[c_j,c_{j+1}]$，我们就可以通过引理$1$来确定出$rank(S,u)$的值。

这里如果我们$u_j \le u \le u_{j+1}$，那我们已经达成了目的，不用继续考虑了。

否则如果不满足$u_j \le u \le u_{j+1}$，也就是说我们在这个sketch的过程中丢失了信息，即说明保留$K(S)$这些位的信息是不够的，那么$p$一定不在$K(S)$中，也就是说$i=j$和$i=j+1$中$p$较小的$i$满足$p>c_m$，故可以使用引理$1$。

计算$K(S)$和$u'(S)$：
我们发现没有平凡的方法可以将一个$w-bit$的数$u$在$O(1)$时间把$B(S)$那些位提取出来之后放到连续的一段中（可能可以通过硬件支持实现？），即使经过了一定预处理。

其实我们不需要做到这个，可以用具有：

1. 将需要提取出的位提取出，并放到（可以不连续）的更短的一段中

2. 保序性

的其他变化来实现我们需要的效果。

我们可以通过一次恰当的乘法和一次与运算来实现这个：

沿用引理$1$的定义，设我们需要从$u$中提取这些位，令$C=bin(c_1,...,c_r)$。

假设我们已经算出了$C$，我们先通过令$v=u\;\mathrm{AND}\;C$来将$u$中不需要的那些位置$0$。

然后我们将$v$乘以一个量$M$，从而把$v$中我们需要的那些$bit$转化到一个狭窄的范围内，然后再通过一次$\mathrm{AND}$来清除掉不需要的位置
这里给出对一个量$M$的存在性证明和构造：

记$M=bin(m_1,...,m_r)$，如果我们暂时忽略交叉和进位造成的影响，那么可以认为$v$乘$M$是把$c_1,...c_r$这些位置的位重新定位到了。

$c_1+m_1,...,c_r+m_r$上。

如果对任意$1 \le i,j \le r$，这$r^2$个$c_i+m_j$都是不同的，那么就不会发生交叉和进位了。

我们现在的目标是构造一个整数集合${m_1,...,m_r}$，使得：

1. $c_1+m_1<c_2+m_2<...<c_r+m_r$

2. 对任意$1 \le i,j \le r$，$c_i+m_j$都是两两不同的。

3. 变换后的区间$[c_1+m_1,c_r+m_r]$"相对较小"，这里的相对较小其实只要是$O( poly(r) )$的即可，因为这样我们可以通过调整树的叉数来满足后续的条件。

### 引理2：

给一个$r$个整数的序列，$c_1<...<c_r$，存在一个$r$个整数的序列，$m_1,...m_r$，满足：

1. $c_1+m_1<c_2+m_2<...<c_r+m_r$

2. 对任意$1 \le i,j \le r$，$c_i+m_j$都是两两不同的。

3. $(c_r+m_r)-(c_1+m_1) \le r^4$

证明：

先考虑证明存在整数序列$m'_1,...,m'_r$，使得对任意$i,j,a,b$，$m'_i+c_a$与$m'_j+c_b$在模$r^3$的意义下不同余。

如果我们找到了这样的整数序列，那么所有$r^2$个$c_i+m'_j$都是两两不同的，并且由于这个是在模$r^3$意义下两两不同的，所以我们可以对第$i$个$c_i+m'_i$加上$(i-1)*r^3$，这样就可以保证对所有$i$满足$c_i+m'_i<c_{i+1}+m'_{i+1}$了。

关于$m'_1,...,m'_r$的存在性：

使用数学归纳法来证明，显然我们可以找到$m'_1$，这个平凡。

假设结论对$t$成立，即我们已经找到了$m'_1,...,m'_t$，满足对任意$1 \le i,j \le t$，$a,b$,有$m'_i+c_a$与$m'_j+c_b$在模$r^3$的意义下不同余。
可以观察到$m'_{t+1}+c_i \equiv m'_s+c_j (\mod r^3\;)$，即$m'_{t+1} \equiv m'_s+c_j-c_i (\mod r^3\;)$。

我们可以令$m'_{t+1}$是$[0,r^3)$中最小的和所有$m'_s+c_j-c_i$不同余的数，这里$1 \le s \le t,1 \le i,j \le r$。

由鸽巢原理，由于$t*r^2<r^3$，所以我们一定可以找到$m'_{t+1}$。

故当$t+1 \le s$时，结论对$t+1$成立
由数学归纳法知结论对$s$成立，同时我们这里给出了一个暴力的$O( r^4 )$的构造算法（$r$轮，每轮最坏枚举$O( r^3 )$个位置）。

## 5.融合：
融合树的"融合"即指将每个节点上的key放到同一个$w-bit$的word上，通过对这个word进行运算来一起处理这些key。

沿用之前$u_i$和$B(S)=\{c_i\}$的记号：

我们这个B-Tree的每个节点存了$C=bin(c_1,...c_r)$和$M=bin(m_1,...,m_r)$这两个量，用于计算$u'(S)$，同时还存了$D=bin(c_1+m_1,...,c_r+m_r)$这个量，用于清空$u'(S)$的计算中不需要的位。

同时还需要两个数组，存排序后的$u_i$和$u'_i$，和一个表$f[i][j][2]$表示引理$1$中，如果知道了$u_i$和$j$，还有$u$和$u_i$的大小关系，我们唯一确定的答案是多少。

回顾之前的内容，当我们算出了$j=rank(K(S),u'(S))$后，如果$u$不在$[u_j,u_{j+1}]$的区间中，那么我们把$u'(S) \;\mathrm{XOR}\; u'_j$和$u'(S) \;\mathrm{XOR}\; u'_{j+1}$比较一下，较小的值所对应的$u'_h$，$h=j$或$j+1$，和$u$有更长的公共前缀，即$msb$更小。

令$m=msb(u,u_h)$，然后我们需要知道$m$被哪个$B(S)$中的区间$[c_i,c_{i+1}]$包含，所以需要进行一次$i=rank(B(S),m)$的计算
还需要进行一次$u$和$u_h$的比较，这个平凡，当这些都做完了，我们查一下表$f$即可得到$rank(S,u)$。

可以发现fusion tree的每个内部节点需要存下$O( B^2 )$大小的表，内部节点个数是$O( n/B^4 )$个，所以是$O( n )$空间的。

下面给出对

1. $rank(K(S),u'(S))$

2. $rank(B(S),m)$，其中$m$是在$[0,w]$中的整数

3. 两个$w-bit$的整数$u,v$，$msb(u,v)$

的计算方法：

### $O(1)$计算$rank(K(S),u'(S))$：
我们把每个$K(S)$中的元素前面补一个$1$，然后从小到大拼到一起来，这个拼起来的操作就是所谓的"融合"。

由于我们$K(S)$中有$k$个元素，每个元素有$r^4$位，所以这里总共用了$k(r^4+1)$位，由于$B/2 \le k \le B$，所以我们总的位数是$O( B^5 )$的，由于$B=O( w^{1/5} )$，所以总的位数是$O( w )$的。

所以我们拼起来的这个东西是$O( 1 )$个word的，这里将其定义为$A$。

令$C=\sum \limits _{i = 0} ^ {B} 2^{(r^4+1)i}$
通过$u'(S) \times C$，可以将$u'(S)$前面补一个$0$之后复制$B$遍，然后拼到一起
通过$A-u'(S) \times C$，可以发现对每个$A$中补$1$的位置，其对应的那个$u_i(S)$如果$<u'(S)$，则这个$1$变成$0$，否则$1$不变
所以我们通过$(A-u'(S) \times C)\&C$，然后对这个word数$1$的个数即可知道$rank(K(S),u'(S))$。

由于这个word只在$2^{(r^4+1)i}$这样的位置有$1$，我们可以通过一次对$2^{r^4+1}-1$的取模来得到其中$1$的个数，虽然对常数取模可以用乘法和位运算$O(1)$实现，但我们这里可以给出一个更合适的构造。

我们可以通过将其乘$C \& (2^{(r^4+1)k}-1)$，这样相当于把其叠加了$k$次之后加起来，可以发现其中有一个长为$r^4+1$的段，这段的二进制表示的值等于这个word在$2^{(r^4+1)i}$这些位置的元素的和。

通过位移和$\mathrm{AND}$我们可以取出这个长$r^4+1$的段，于是就完成了。

答案即$((((A-u'(S) \times C) \& C) \times (C \& (2^{(r^4+1)k}-1))) \& C)>>((k(r^4+1)-1)$

### $O(1)$计算$rank(B(S),m)$，$m$是在$[0,w]$中的整数：

由于我们可以$O(1)$计算$rank(K(S),u'(S))$，所以把这个查出来然后判断那一个数的大小，并且进行一次查表即可。

### $O(1)$计算$msb(u,v)$：
等价于求$u \;\mathrm{XOR}\; v$的最高位$1$的位置，设$A=u \;\mathrm{XOR}\; v$。

我们将$A$分为$r^c$大小的块，总共$r$块，这里$c$是一个常数,$c>1$
令$C=(100...0100...0......)_2$，这里每两个$1$之间有$r-1$个$1$，$C$是一个常数。

注意到：

$((100...0)_2-0)\&(1<<(r^c)-1)=(1<<(r^c)-1)$

$((100...0)_2-y)\&(1<<(r^c)-1)=0$，这里$y>0$

先考虑对每个块去掉首位，块内是否有$1$。

我们用$A\& \sim C$可以去掉每一块的首位。

然后用$C-(A\& \sim C)$可以使得每一块中除首位外如果有$1$，则其在该块首位为$0$，否则为$1$。

然后用$(C-(A\& \sim C))\&C$去掉了$C-(A\& \sim C)$中每一块中除首位外的部分。

然后用$(C-((C-(A\& \sim C))\&C))$可以得到：如果一块中除首位外有$1$，则块首位为$1$，否则为$0$，且块首位外所有位置都是$0$的一个数
再考虑对每个块只保留首位，块内是否有$1$。

这个用$A\&C$即可。

最后$(A\&C)|(C-((C-(A\& \sim C))\&C))$可以得到：如果一块中有$1$，则块首位为$1$，否则为$0$，且块首位外所有位置都是$0$的一个数。

令$D= \sum \limits _{k=0}^{r-1} 2^{k(r^c-1)}$，

通过$(((A\&C)|(C-((C-(A\& \sim C))\&C))) \times D)>>(w-r)$可以将每块首位的数字拼到一个长$r$的二进制数中。

然后我们可以使用前面的$O(1)$计算$rank$的方法，令$B'(S)={2^i}$，$i$在$[0,r-1]$间，是整数。

通过$rank(B'(S),(((A\&C)|(C-((C-(A\& \sim C))\&C))) \times D)>>(w-r))$就可以得到这个长$r$的二进制数中第一个非0的首位的位置了。

我们知道了第一个非$0$位在哪个块中，然后查这个块里面第一个非$0$位的位置就可以了。

由于我们每个块是$r^c$的大小，所以对一个大小为$r^c$，包含了$2^i$的集合用一次rank即找到了块内第一个非$0$的首位位置。

取$c=4,r=w^{1/5}$，$r^c=w^{4/5}$，我们便$O(1)$查询，$O(w^{4/5})$预处理时间复杂度解决了这个问题，由于预处理次数是$O( n/B^4 )$，所以这里也是线性的。

综上所述，我们得到了一个单次操作复杂度$O( \log n/\log w + \log w )$的数据结构，这里**据说**可以通过一些优化做到$O( \log n/\log w )$，但在这里由于我还没看所以暂时不做介绍。

## 6.一些拓展
如果我们允许下列中的一个：

1. 放松线性空间的限制

2. 保留线性空间的限制，但是使用随机化和整数除法

那么我们可以得到一个$O( \sqrt{ \log n } )$的动态搜索的时间复杂度上界。

当$n$超过$2^{(\log w)^2/36}$时（这里$1/36$的常数是论文中给出的，由于我的部分细节和论文中不同，可能是不同的常数），

对于1的case，可以通过使用vEB树来实现，对于2的case，可以通过使用Y-fast trie实现。

对于这样的$n$，这两个数据结构可以在$O( \log \log U )=O( \log w )=O( \sqrt{\log n} )$的时间完成一次搜索操作。

当$n$小于这个数时，

对于较小的$n$，我们使用fusion tree，通过调节$B=Θ(2^ {\sqrt{\log n}})$。

在这个$B$下，我们的时间复杂度是$O( \log n/\log B + \log B ) = O( \sqrt{\log n} )$。

综上所述，如果引入随机化和整数除法，可以$O( n \sqrt{\log n} )$时间，线性空间整数排序。

## 7.总结
由信息论可以证明基于比较的排序下界是$\Omega( n\log n )$的，但整数排序其实是非常复杂的一个问题，还有待研究。

description:
魔法森林里有一颗大树，下面经常有小孩召开法。

大树可以看做一个有 $n$ 个节点，$n - 1$ 条边的无向连通图。大树的每个节点都有若干瓶矿泉水，初始第 $i$ 个节点有 $a_i$ 瓶矿泉水。

麦杰斯住在大树顶端，有一天他想改造一下大树，方便他巨大多喝水之后可以垃圾分类矿泉水瓶。

麦杰斯喜欢二进制运算，所以他会有以下三种操作：

1. 将树上与一个节点 $x$ 距离为 $1$ 的节点上的矿泉水数量 $+1$。这里树上两点间的距离定义为从一点出发到另外一点的最短路径上边的条数。
2. 在一个节点 $x$ 上喝掉 $v$ 瓶水。
3. 询问树上与一个节点 $x$ 距离为 $1$ 的所有节点上的矿泉水数量的异或和。

麦杰斯共有 $m$ 次操作，他希望你在每次 $3$ 操作后告诉他答案。

inputFormat:
第一行两个正整数 $n,m$，分别表示树的节点个数和麦杰斯的询问个数。

第二行到第 $n$ 行，每行两个整数表示有一条连接这两个节点的边。

第 $n + 1$ 行 $n$ 个整数，第 $i$ 个整数表示初始第 $i$ 个节点上的矿泉水数量。

第 $n + 2$ 行到第 $n + m + 1$ 行，每行先读入一个整数 $opt$ 表示操作类型。

如果 $opt = 1$ 或 $3$ ，接下来读入一个整数 $x$ 表示麦杰斯操作的节点标号。

否则接下来读入两个整数 $x, v$ 表示麦杰斯操作的节点标号和他喝的水的数量。

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

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

对于 $30\%$ 的数据，满足 $n \le 10^3$，$m\le 10^3$。

对于 $60\%$ 的数据，满足 $n \le 10^5$，$m \le 10^5$。

对于另外 $10\%$ 的数据，存在一个点满足所有点到该节点的距离 $\le 1$。

对于 $100\%$ 的数据，满足 $1\le n \le 5\times 10^5$，$1\le m \le 5\times 10^5$，$0\le a_i \le 10^5$，$1 \le x \le n$，$opt\in\{1,2,3\}$。

保证任意时刻每个节点的矿泉水数非负。

温馨提示：矿泉水瓶不是干垃圾也不是湿垃圾，而是可回收垃圾。


title: [APIO2019] 奇怪装置

description:
考古学家发现古代文明留下了一种奇怪的装置。该装置包含两个屏幕，分别显示两个整数 $x$ 和 $y$ 。

经过研究，科学家对该装置得出了一个结论：该装置是一个特殊的时钟，它从过去的某个时间点开始测量经过的时刻数 $t$，但该装置的创造者却将 $t$ 用奇怪的方式显示出来。若从该装置开始测量到现在所经过的时刻数为 $t$，装置会显示两个整数：$x = ((t + \lfloor \frac {t}{B} \rfloor) \bmod A)$，与 $y=(t \bmod B)$。这里 $\lfloor x \rfloor$ 是下取整函数，表示小于或等于 $x$ 的最大整数。

考古学家通过进一步研究还发现，该装置的屏幕无法一直工作。实际上，该装置的屏幕只在 $n$ 个连续的时间区间段中能正常工作。第 $i$ 个时间段从时刻 $l_i$ 到时刻 $r_i$。现在科学家想要知道有多少个不同的数对 $x,y$ 能够在该装置工作时被显示出来。

两个数对 $(x_1,y_1)$ 和 $(x_2,y_2)$ 不同当且仅当 $x_1 \neq x_2$ 或 $y_1 \neq y_2$。

inputFormat:
第一行包含三个整数 $n$，$A$ 与 $B$。
接下来 $n$ 行每行两个整数 $l_i$，$r_i$ 表示装置可以工作的第 $i$ 个时间区间。

outputFormat: 输出一行一个整数表示问题的答案。


title: [APIO2019] 桥梁

background: 圣彼得堡市内所有水路长度总和约 $282$ 千米，市内水域面积占城市面积的 $7\%$。——来自维基百科

description:
圣彼得堡位于由 $m$ 座桥梁连接而成的 $n$ 个岛屿上。岛屿用 $1$ 到 $n$ 的整数编号，桥梁用 $1$ 到 $m$ 的整数编号。每座桥连接两个不同的岛屿。有些桥梁是在彼得大帝时代建造的，其中一些是近期建造的。这导致了不同的桥梁可能有不同的重量限制。更具体地，只有重量不超过 $d_i$ 的汽车才能通过第 $i$ 座桥梁。有时圣彼得堡的一些桥梁会进行翻新，但这并不一定会使桥梁承重变得更好，也就是说，进行翻新的桥梁的 $d_i$ 可能会增加或减少。你准备开发一个产品，用于帮助公民和城市客人。目前，你开发的模块要能执行两种类型的操作：

1. 将桥梁 $b_j$ 的重量限制改为 $r_j$。

2. 统计一辆重为 $w_j$ 的汽车从岛屿 $s_j$ 出发能够到达多少个不同的岛屿。

请你回答所有第二种操作的答案。

inputFormat:
第一行包含两个整数 $n$ 和 $m$—— 表示圣彼得堡的岛屿数量与桥梁数量。

接下来 $m$ 行，每行三个整数 $u_i,v_i,d_i$。第 $i$ 行的整数描述了一座连接岛屿 $u_i$ 和 $v_i$，初始时重量限制为 $d_i$ 的桥梁。

接下来一行一个整数 $q$—— 表示操作的数量。

接下来 $q$ 行按顺序每行描述一个操作。

每行第一个整数 $t_j$ 表示操作类型：

- 若 $t_j=1$，则该操作是第一种类型，该行接下来给定两个整数 $b_j$ 和 $r_j$，表示桥梁 $b_j$ 的重量限制将变为 $r_j$。

- 若 $t_j=2$，则该操作是第二种类型，该行接下来给定两个整数 $s_j$ 和 $w_j$，表示一辆重为 $w_j$ 的汽车将要从第 $s_j$ 个岛屿出发。

outputFormat: 对于每个第二种类型的询问，输出一行一个整数表示答案。

hint:
对于全部数据，$1 \leq n \leq 5\times 10^4$，$0 \leq m \leq 10^5$，$1 \leq q \leq 10^5$。保证 $1 \leq u_i$，$v_i$, $s_j \leq n$，$u_i \neq v_i$，$1 \leq d_i$, $r_j$, $w_j \leq 10^9$，$1 \leq b_j \leq m$，$t_j \in {1,2}$。

详细子任务附加限制与分值如下表 **（注：这里给出的子任务与本题在这里的最终评测无关，仅供参考）**

| 子任务 | 附加限制 | 分值 |
| :----------: | :----------: | :----------: |
| 1 | $n$, $m\leq 10^3$，$q\leq 10^4$ | 13 |
| 2 | 岛屿和桥梁将形成一个树结构；$m=n-1$，$u_i=i$，$v_i=i+1$；（$1\leq i\leq m$） | 16 |
| 3 | 岛屿和桥梁将形成一个完全二叉树结构；$n=2^k-1$，$m=n-1$，$u_i=\frac{i+1}{2}$，$v_i=i+1$；（$1\leq k\leq 15$，$1\leq i\leq m$） | 17 |
| 4 | 所有 $t_i$ 均为 $2$ | 14 |
| 5 | 岛屿和桥梁将形成一个树结构 | 13 |
| 6 | 无特殊限制 | 27 |


title: [APIO2019] 路灯

description:
一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 $n+1$ 个停车站点，它们将街道划分成了 $n$ 条路段。每一路段都拥有一个路灯。当第 $i$ 个路灯亮起，它将照亮连接第 $i$ 与第 $i+1$ 个站点的路段。否则这条路段将是黑暗的。

安全起见，出租车只能在被照亮的路段上行驶。换言之，出租车能从站点 $a$ 出发到达站点 $b (a<b)$ 的条件是：连接站点 $a$ 与 $a+1$，$a + 1$ 与 $a+2$，……，$b-1$ 与 $b$ 的路段都被照亮。

在经过一些意外故障或修理之后，街道上的路灯可能是亮起的，也可能是熄灭的。

现在给定 $0$ 时刻时，街道上路灯的初始状态。之后 $1,2,\ldots,q$ 时刻，每时刻会发生下列两种事件之一：

- $\text{toggle} \ i$：切换第 $i$ 个路灯的状态。具体地说，若路灯原来亮起，则现在将熄灭；若路灯原来熄灭，则现在将亮起。

- $\text{query}  \  a  \  b$：出租车部门的负责人想知道，从 $0$ 时刻起到当前时刻，有多少个时刻满足：出租车能够从站点 $a$ 出发到达站点 $b$。

请你帮助出租车部门的负责人回答他们的问题。

inputFormat:
第一行包含两个整数 $n$ 和 $q$，表示路灯的数量与时刻数。

第二行包含一个字符串 $s$ 表示路灯的初始状态，$s_i$ 为 $1$ 表示第 $i$ 个路灯初始时亮起；$s_i$ 为 $0$ 表示第 $i$ 个路灯初始时熄灭。

接下来 $q$ 行每行描述一个时刻的事件。第 $i$ 行描述时刻 $i$ 所发生的事件：

- $\text{toggle} \ i$：该时刻切换了第 $i$ 个路灯的状态。

- $\text{query} \ a \ b$：计算从 $0$ 时刻起到该时刻，共有多少个时刻满足：出租车能从站点 $a$ 出发到达站点 $b$。

至少有一个时刻的事件是 $\text{query}$。

outputFormat: 对于每个 $\text{query}$ 的事件，输出一行单个整数，表示该问题的答案。

samples:
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6

hint:
对于全部数据，$1 \leq n,q \leq 3\times 10^5$，$|s|=n$，$1 \leq i \leq n$，$1 \leq a < b \leq n+1$。

详细子任务附加限制与分值如下表 **（注：这里给出的子任务与本题在这里的最终评测无关，仅供参考）**

| 子任务 | 附加限制 | 分值 |
| :----------: | :----------: | :----------: |
| 1 | $n$, $q\leq 100$ | 20 |
| 2 | 对于所有 $\text{query}\ a\ b$ 事件，满足 $a=b-1$ | 20 |
| 3 | 对于所有 $\text{toggle}\ i$ 事件，第 $i$ 个路灯将被点亮 | 20 |
| 4 | 所有 $\text{toggle}$ 事件都发生在第一个 $\text{query}$ 事件之前 | 20 |
| 5 | 无特殊限制 | 20 |


title: 赦免战俘

background: 借助反作弊系统，一些在月赛有抄袭作弊行为的选手被抓出来了！

description:
现有 $2^n\times 2^n (n\le10)$ 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。

给出 $n$，请输出每名作弊者的命运，其中 0 代表被赦免，1 代表不被赦免。

inputFormat: 一个整数 $n$。

outputFormat: $2^n \times 2^n$ 的 01 矩阵，代表每个人是否被赦免。数字之间有一个空格。


title: X龙珠

description:
“X龙珠”是一款益智小游戏。游戏中有 $n(2|n)$ 个编号互不相同龙珠按照给定的顺序排成一个队列，每个龙珠上面都有一个编号。每次操作时，选择并取出龙珠队列中**相邻**的两个龙珠，放到目标队列的末尾（目标队列最开始是空的，且这两个龙珠的前后顺序不变），然后去除原龙珠队列的空隙。反复多次，直到原龙珠队列为空。可见，因为决策不一样导致目标队列顺序不一样。现在请求出所有方案中、目标队列字典序最大的方案。只需要给出目标队列即可。

例如，当原龙珠队列是 [1,3,2,4] 时，可以先取出 3 和 2，此时目标队列是 [3,2]，原龙珠队列是 [1,4]；再将剩下两个龙珠放入目标队列，得到目标队列是 [3,2,1,4]

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

接下来一行，每行 $n$ 个整数，表示原龙珠队列的编号。

outputFormat: 一行，$n$ 个整数。

hint:
对于 20% 的数据，$n\le10$。
对于 60% 的数据，$n\le10^3$。
对于 100% 的数据，$n\le10^5$，龙珠编号不超过 n。


title: 小鱼比可爱（加强版）

description:
人比人，气死人；鱼比鱼，难死鱼。小鱼最近参加了一个“比可爱”比赛，比的是每只鱼的可爱程度。参赛的鱼被从左到右排成一排，头都朝向左边，然后每只鱼会得到一个整数数值，表示这只鱼的可爱程度，很显然整数越大，表示这只鱼越可爱，而且任意两只鱼的可爱程度可能一样。由于所有的鱼头都朝向左边，所以每只鱼只能看见在它左边的鱼的可爱程度，它们心里都在计算，在自己的眼力范围内有多少只鱼不如自己可爱呢。请你帮这些可爱但是鱼脑不够用的小鱼们计算一下。

和之前的要求不一样，比赛组委会关心的是这个排列的“总得意值”。一共有 $n$ 只小鱼，总共有 $\frac{n(n+1)}2$ 个不同的区间。每个区间的得意值等于这个区间中符合“左边的一只鱼的可爱值比右边的一只鱼可爱值更大”的对数（其实就是区间逆序对数啦）。总得意值就是所有区间的“得意值”的和。现在要求输出“总得意值”是多少。

inputFormat:
第一行输入一个整数 $n$，表示鱼的数目。

第二行内输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$，用空格间隔，依次表示从左到右每只小鱼的可爱程度。

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


title: 缩小社交圈

description:
社交圈子里有 $n$ 个人，每个人都有一个 SAN 值范围 $[l_i,r_i]$。当两个人的 SAN 值交集不为空时，这两个人有 PY 关系。

现在希望从社交圈子里面挑选出一些人组成一个集合 $S$，如果将所有集合内的人中有 PY 关系的那一对人都连上边，则 $S$ 刚好成为一个树（森林不行哦）。

请问，有多少种可以选择的方案？由于答案可能很大，请对 $10^{9}+7$ 取模。

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

接下来 $n$ 行，每行 2 个整数，表示这个人的 SAN 值区间。

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

hint:
对于20%的数据，满足 $n \leq 18$ 。

对于40%的数据，满足 $n \leq 50$

对于60%的数据，满足 $n \leq 200$

对于100%的数据，满足 $n \leq 2000,1 \leq l_{i} <r_{i} \leq 4000 $


title: 【XR-2】约定 (加强版)

background:
原题链接：[P5437](https://www.luogu.org/problemnew/show/P5437)

其实在比赛时就想放上这个加强版了qwq
但是团队成员都强烈反对，于是就在赛后放上来啦

description:
有一个 $n$ 个点的完全图，编号从 $1$ 到 $n$。
连接 $i$ 和 $j$ 节点的边，权值为 $(i+j)^k$。
定义一棵树的权值为其所有边的权值和。
从这个图的所有生成树中随机选择一个，求其权值的期望。
需要将答案对 $998244353$ 取模。

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

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


title: [JSOI2015] 最大公约数

description:
给定一个长度为 $N$ 的正整数序列 $A_i$ 。

对于其任意一个连续的子序列 $A_l,A_{l+1},...,A_r$ ，我们定义其权值 $W(L,R)$ 为其长度与序列中所有元素的最大公约数的乘积，即 $W(L,R) = (R-L+1) × \gcd (A_l,...,A_r)$。

`JYY` 希望找出权值最大的子序列。

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

接下来一行，包含 $N$ 个正整数，表示序列 $A_i$ 。

outputFormat: 输出文件包含一行一个正整数，表示权值最大的子序列的权值。


title: [JSOI2011] 柠檬

description:
$\text{Flute}$ 很喜欢柠檬。它准备了一串用树枝串起来的贝壳，打算用一种魔法把贝壳变成柠檬。贝壳一共有 $n$ $(1≤n≤100000)$ 只，按顺序串在树枝上。为了方便，我们从左到右给贝壳编号 $1..n$ 。每只贝壳的大小不一定相同，贝壳 $i$ 的大小为 $s_i(1≤s_i≤10000)$ 。

变柠檬的魔法要求$:\ \text{Flute}$ 每次从树枝一端取下一小段连续的贝壳，并选择一种贝壳的大小 $s_0$。如果这一小段贝壳中大小为 $s_0$ 的贝壳有 $t$ 只，那么魔法可以把这一小段贝壳变成 $s_0t^2$ 只柠檬。$\text{Flute}$ 可以取任意多次贝壳，直到树枝上的贝壳被全部取完。各个小段中，$\text{Flute}$ 选择的贝壳大小 $s_0$ 可以不同。而最终 $\text{Flute}$ 得到的柠檬数，就是所有小段柠檬数的总和。

$\text{Flute}$ 想知道，它最多能用这一串贝壳
变出多少柠檬。请你帮忙解决这个问题。

inputFormat:
第 $1$ 行：一个整数，表示 $n$ 。
第 $2..n+1$ 行：每行一个整数，第 $i+1$ 行表示 $s_i$。

outputFormat: 仅一个整数，表示 $\text{Flute}$ 最多能得到的柠檬数。

hint: $\text{Flute}$ 先从左端取下 $4$ 只贝壳，它们的大小为 $2, 2, 5, 2$。选择 $s_0=2$，那么这一段里有 $3$ 只大小为 $s_0$ 的贝壳，通过魔法可以得到 $2×3^2 = 18$ 只柠檬。再从右端取下最后一只贝壳，通过魔法可以得到 $3×1^2 = 3$ 只柠檬。总共可以得到 $18+3=21$ 只柠檬。没有比这更优的方案了。


title: [JSOI2011] 分特产

description:
JYY 带队参加了若干场 $\text{ACM/ICPC}$ 比赛，带回了许多土特产，要分给实验室的同学们。

JYY 想知道，把这些特产分给 $n$ 个同学，一共有多少种不同的分法？当然，JYY 不希望任何一个同学因为没有拿到特产而感到失落，所以每个同学都必须至少分得一个特产。

例如，JYY 带来了 $2$ 袋麻花和 $1$ 袋包子，分给 $A$ 和 $B$ 两位同学，那么共有 $4$ 种不同的
分配方法：

 $A$：麻花， $B$：麻花、包子

 $A$：麻花、麻花， $B$：包子

 $A$：包子， $B$：麻花、麻花

 $A$：麻花、包子， $B$：麻花

inputFormat:
输入数据：

第一行是同学的数量 $n$ 和特产的数量 $m$。

第二行包含 $m$ 个整数，表示每一种特产的数量。

$n, m$ 不超过 $1000$ ，每一种特产的数量不超过 $1000$。

outputFormat:
输出一行，不同分配方案的总数。

由于输出结果可能非常巨大，你只需要输出最终结果
$\bmod\ {10^9+7}$ 的数值就可以了。


title: [THUPC2018] 《算法与数据结构》小助教招募通知

background:
T 大学和 U 大学是 W 国最好的两个大学。《算法与数据结构》是 U 大学的一门经典课程，曾连续百余年获得“U 大学一级精品课程”的荣誉。

小 O 是这门课明年的助教。由于这门课过于火爆，他一个人忙不过来，所以他正在招募这门课的小助教。不过，招募的条件有点奇怪……

description:
《算法与数据结构》课程的内容共分为 $n$ 个知识点，而每个知识点均有配套的的 $m$ 道练习题。每道题有两个属性值，第 $i$ 个知识点的第 $j$ 道练习题可以让做这道题的学生的算法能力提高 $a_{i, j}$，数据结构能力提高 $d_{i, j}$。这些属性值均为整数，但是可能为负数，甚至可能存在两个属性均为负的练习题。（不要问这种题是怎么被加进题库的…）

明年的《算法与数据结构》课共有 $q$ 个学生注册。通过对每个学生以前学习情况的考察，小 O 决定对每个学生进行“因材施教”。具体方法是，对于第 $k$ 个学生、第 $i$ 个知识点，小 O 希望这个学生完成这个知识点的恰好 $c_{k, i}$ 道练习题。

其实小 O 和 T 大学关系密切，希望在 U 大学搞点事情。对于每个学生，设为该学生选出的所有练习题对于算法能力与数据结构能力的提升分别为 $A$ 与 $D$，小 O 的目标是最大化 $A^2+D^2$，这样无论这个学生在哪个方面能力提升或降低的程度很大，都是小 O 所期望的。

请对于每个学生计算这个目标的最大值。

inputFormat:
每个输入文件仅包含一个测试数据。

* 第一行包含三个正整数 $n, m, q$。

* 接下来 $n$ 行，每行包含 $m$ 个整数；其中第 $i$ 行的第 $j$ 个整数为 $a_{i, j}$。

* 接下来 $n$ 行，每行包含 $m$ 个整数；其中第 $i$ 行的第 $j$ 个整数为 $d_{i, j}$。

* 接下来 $q$ 行，每行包含 $n$ 个整数；其中第 $k$ 行的第 $i$ 个整数为 $c_{k, i}$。

对于输入的每一行，如果有多个数输入，则相邻两个数用恰好一个空格隔开。

outputFormat: 输出 $q$ 行，每行 1 个整数：第 $k$ 行的整数表示第 $k$ 个学生的 $A^2+D^2$ 的最大值。

hint:
### 样例解释

有 2 个知识点，每个知识点有 4 道练习题；有 4 个学生。

以第 2 个学生为例，我们需要为该学生在第 1 个知识点中选择恰好 2 道练习题，在第 2 个知识点中选择恰好 1 道练习题。一种最优的方案是，在第 1 个知识点中选择第 1 道题和第 3 道题，在第 2 个知识点中选择第 1 道题。这些题目对于算法能力的提高为 $A=a_{1,1}+a_{1,3}+a_{2,1}=1+(-1)+0=0$，对于数据结构能力的提高为 $D=d_{1,1}+d_{1,3}+d_{2,1}=1+1+10=12$，此时 $A^2+D^2=144$，并且不存在更优的方案。

### 数据范围

$1 \leq n \leq 6$，$1 \leq m \leq 666$，$1 \leq q \leq 666$，所有的 $a_{i, j}$ 与 $d_{i, j}$ 均在 $[-10^9,10^9]$ 范围内。
对于最终测试数据，所有的 $c_{k, i}$ 均在 $[0, m]$ 范围内**独立、均匀**随机生成。

### 提示

输出的每个数可能非常大，甚至可能超过64位整数的范围。

* C++语言可以使用`__int128_t`类型表示带符号128位整数，或使用`__uint128_t`类型表示无符号128位整数；这两种数据类型无法直接进行输入/输出。

* Java语言可以使用`BigInteger`类。

### 版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai/) 对此次比赛的支持。

题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。


title: [THUPC2018] 淘米神的树

description:
可爱的 Tommy 有一棵树。这棵树上只有点 $a$ 和 $b$ 是黑色，其它的点都是白色。

每次，Tommy 可以将一个黑色 $p$ 的点染成红色，然后把和 $p$ 相邻的所有白色的点染成黑色。最后，所有的点都会被染成红色。

设第 $i$ 个点是第 $t_i$ 个被染成红色的，那么 $t_i$ 是一个 $1$ 到 $n$ 的排列。Tommy 希望你帮他求出，有多少种不同的 $t_i$。

inputFormat:
每个输入文件仅包含一个测试数据。

* 第一行三个用空格隔开的正整数 $n,a,b$，表示树的点数和初始的黑色点的编号；

* 接下来 $n-1$ 行，每行两个正整数 $x,y$ 描述树上的一条边 $\left( x,y\right)$。

树上的节点从 $1$ 开始编号。

outputFormat:
输出 $1$ 行：

* 一个整数，表示不同的排列 $t_i$ 的个数除以 $998,244,353$ 的余数。

hint:
### 数据范围

保证 $a,b\le n\le 234,567$。

### 版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai/) 对此次比赛的支持。

题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。


title: [THUPC2018] 密码学第三次小作业

background:
1977年，罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）提出了RSA 加密算法。RSA 加密算法是一种非对称加密算法，其可靠性由极大整数因数分解的难度决定。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就肯定会极度下降。

RSA 的基本原理如下：

- 公钥与私钥的产生
  1. 随机选择两个不同大质数 $p$ 和 $q$，计算 $N=p\times q$
  2. 根据欧拉函数性质，求得 $r=\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)$
  3. 选择一个小于 $r$ 的正整数 $e$，使 $e$ 和 $r$ 互质。并求得 $e$ 关于 $r$ 的乘法逆元 $d$，有 $ed\equiv 1 \pmod r$
  4. 将 $p$ 和 $q$ 的记录销毁。此时，$(N,e)$ 是公钥，$(N,d)$ 是私钥。
- 消息加密：首先需要将消息 $m$ 以一个双方约定好的格式转化为一个小于 $N$，且与 $N$ 互质的整数 $n$。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：

$$
n^{e}\equiv c\pmod N
$$

- 消息解密：利用密钥 $d$ 进行解密

$$
c^{d}\equiv n\pmod N
$$

description:
现在有两个用户由于巧合，拥有了相同的模数 $N$，但是私钥不同。设两个用户的公钥分别为 $e_1$ 和 $e_2$，**且两者互质**。明文消息为 $m$，密文分别为：

$$\begin{matrix}c_1=m^{e_1}\bmod N\\c_2=m^{e_2}\bmod N\end{matrix}$$

现在，一个攻击者截获了 $c_1$ ，$c_2$，$e_1$，$e_2$，$N$，请帮助他恢复出明文 $m$ 。

inputFormat:
输入包含多组数据，第一行一个整数 $T$ 表示数据组数，保证 $1\le T\le 10^4$ 。接下来依次描述每组数据，对于每组数据：

* 一行包含五个正整数 $c_1$，$c_2$，$e_1$，$e_2$，$N$，保证 $2^{8}< N < 2^{63}$，$N$ 有且仅有两个素因子，其余数据严格按照上述RSA算法生成。

outputFormat:
对于每组数据，输出 $1$ 行：

- 一个非负整数 $m$，请选手务必在输出时保证 $0\le m<N$。答案 $m$ 保证与 $N$ 互质。

hint:
### 版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai/) 对此次比赛的支持。

题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。


title: [THUPC2018] 琪亚娜之墙

description:
那一天，人类终于回想起，曾经一度被她们支配的恐惧，还有被囚禁于鸟笼中的那份耻辱。

为了守护最珍视之物，Kiana建立起了 $n$ 座围墙，每一座围墙都闭合形成了一个**凸多边形**，不同的围墙**互不相交**。出于特别的目的，围墙分为两种：用砖瓦和岩石砌成的**工匠之墙**、用树木和荆棘形成的**自然之墙**。

只依靠墙壁并不使人放心，Kiana还派遣了两类士兵在墙内巡逻：

**追魂猎人**：他们从小与大自然为伴，可以自由穿越自然之墙，但无法通过工匠之墙。

**天马骑士**：他们拥有在天空中飞行的能力，可以自由飞越工匠之墙，但由于某些信仰的缘故，无法通过自然之墙。

只依靠墙壁和士兵任然难以让人放心，但Kiana还拥有神之力量，在某段时间内，她发挥了 $m$ 次这股力量，以完成两类事件：

1. 将某座工匠之墙转化为自然之墙，或将某座自然之墙转化为工匠之墙。

2. 将一位追魂猎人或天马骑士直接传送到坐标 $(x,y)$ 处，保证这个坐标不位于围墙之上，且与最近的围墙相距至少 $10^{-3}$。

在每一次传送士兵完成后，Kiana希望知道这名士兵可以自由活动的区域**面积**有多大。由于她不会做，所以希望你来告诉她答案。

inputFormat:
输入第一行包含两个正整数 $n$ 和 $m$，分别表示围墙的数量和Kiana发动神之力量的次数，数据保证 $n\leq 3\times 10^4$且 $m\leq 10^5$。

接下来 $n$ 行，第 $i$ 行用于描述第 $i$ 座围墙的情况，首先有两个正整数 $k_i$ 和 $r_i$，分别表示这座围墙的顶点数和类型，若 $r_i=1$ 表示这是工匠之墙，若 $r_i=2$ 表示这是自然之墙，接下来 $2k_i$ 个实数，第 $2p-1$ 和第 $2p$ 个数表示这座围墙上第 $p$ 个顶点的横、纵坐标，所有的顶点按照在多边形上逆时针排列的顺序输入，数据保证 $3\leq k_i\leq 100$ 且 $\sum_{i=1}^{n}k_i\leq 10^5$。

接下来 $m$ 行，第 $j$ 行用于描述Kiana第 $j$ 次使用神之力量的情况，首先有一个正整数 $op$，表示Kiana发动的神之力量类型，若：

$op=1$：这一行还有一个正整数 $u$，表示Kiana转换了第 $u$ 座围墙的类型（若本来为工匠之墙，则转化为自然之墙，若本来为自然之墙，则转化为工匠之墙），数据保证 $1\leq u\leq n$。

$op=2$：这一行还有一个正整数 $v$ 与两个实数 $x$ 和 $y$，若 $v=1$，表示Kiana将一名追魂猎人传送到了 $(x,y)$ 处，若 $v=2$，表示Kiana将一名天马骑士传送到了 $(x,y)$ 处。

数据保证所有的 $r_i$、$op$ 和 $v$ 的取值仅为 $1$ 或 $2$，所有的实数保留到小数点后两位且绝对值小于 $2\times 10^5$，任意两个的多边形之间的距离至少为 $10^{-3}$，任意两个输入顶点的横坐标之差与纵坐标之差的绝对值不小于 $10^{-3}$。

outputFormat: 输出由若干行组成，对于每个 $op=2$ 的输入，输出一行一个实数 $S$（保留到小数点后 $4$ 位），表示该名士兵可以自由活动的区域面积，数据保证这个面积是有限的。

hint:
来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai/) 对此次比赛的支持。

题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。


title: [THUPC2018] 组合数问题

background: **友情提示：本题篇幅较长。**

description:
众所周知，小葱同学擅长计算，尤其擅长计算组合数。

于是现在我们有了一个 $N\times M$ 的棋盘，棋盘上有些地方会有障碍物的存在。在棋盘上有 $K$ 枚棋子，每枚棋子要么属于红队要么属于蓝队。此外，每枚棋子有两个属性值，第 $i$ 枚棋子的两个属性记为 $a_i,b_i$ 并且保证 $a_i\geq b_i$。既然有了两支队伍那么小葱同学就要来玩游戏，这个游戏一共有 $R$ 个回合。每个回合内，每枚棋子会按照如下顺序进行游戏：

0. 回合开始，记当前是第 $H$ 回合。若现在为游戏的开始时刻，则 $H=1$。

1. 对于所有能够移动的棋子，沿着自己当前的方向移动一格。每枚棋子的朝向一定是上下左右中的一种。如果棋子发现自己不能移动，即前方格子为棋盘外部或者障碍物，那么则不向前移动，而是将自己的方向旋转一百八十度，即进行向后转的操作（注意此时转了之后棋子这回合内并不会进行移动）。

2. 对于所有棋子，每个棋子都拥有且仅拥有一种技能。此时所有棋子按照编号从小到大依次释放技能，如果不能释放技能则跳过。技能总共分为以下几种：

	1. 重锤火花（toolihai）：以自身为中心，制造出绚丽的烟花，令人赏心悦目，无任何效果。

	2. 面子之王（faceking）：该棋子充满了面子，所有棋子都要听其号令，使得所有棋子的方向强制向左（逆时针）转九十度。该技能的效果持续时间为永久。

	3. 头发掉光（onepunch）：头发掉光之后，王队长变得更强了，使该枚棋子的属性大幅度提升。即若当前棋子 $i$ 的属性为 $\left(a_i,b_i\right)$，属性的提升值为 $v$，那么该棋子的属性则变为 $\left(a_i+v,b_i\right)$。该技能的效果能持续 $l$ 个回合，若当前回合为 $H$，则该技能效果会在第 $H+l$ 回合开始的时候消失。若在技能消失前棋子 $i$ 的属性为 $\left(a_i,b_i\right)$，则技能效果消失后其属性会变为 $\left(\max\left(a_i-v,0\right),\min\left(b_i,\max\left(a_i-v,0\right)\right)\right)$。注意再该技能效果消失前该技能可能被再次释放，则多次释放的技能效果叠加，但技能效果消失的时间分开计算。（详见样例第二组数据）

	4. 拉比哩比（rabiribi）：挥动真正的重锤，制造火花，击退前方扇形区域的所有敌方单位。该技能所能影响到的范围为前方大小为 $v$ 的扇形区域，所谓扇形区域可见下图：

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

        从上图我们可以看出，在图的最下方有正在释放技能的棋子，其技能朝向为上，所以其技能方向也为上。则上方的所有区域则为其技能所影响到的扇形区域，该扇形区域大小为 $5$，即 $v=5$。注意到棋盘上某些位置会有障碍物，障碍物的存在会影响到该技能的影响范围。如果一个障碍物存在于技能范围之内，那么以障碍物开始的处于技能范围内的扇形区域也都不会受到技能的影响。如上图可见，所有黑色格子的最下方格子即为障碍物的位置，所有黑色格子即为受到障碍物影响所不能被技能效果影响的格子。

        另一方面，击退效果的定义为将受到技能影响效果的棋子沿着技能释放方向强制移动一格，即从图中 $p_2$ 被击退到 $p_3$ 的位置。如果被击退方向是障碍物或者棋盘边界，则按一下规则进行：

        - 如果下一位置为障碍物，则被击退到该障碍物后面，即从图中的 $p_0$ 击退到 $p_1$。
        - 如果下一位置为棋盘外部，如当前在第一行并且要被击退到第零行，则被击退到第 $N$ 行对应的同一列的位置。

        重复以上过程直到被击退到一个不是障碍物和棋盘外部的位置，则该击退过程结束。（详见样例第一组数据）

	5. 退学花火（firework）：退学之后，有了更多的时间来挖坑。使得上一个释放重锤火花的棋子在接下来 $l$ 回合内无法移动。如果不存在这样的棋子，则使自己在接下来 $l$ 回合内无法移动。

	6. 救乌干达（viuganda）：使用vim，拯救阵亡的棋子，复活距离自身最远的阵亡的己方棋子。若己方没有阵亡棋子，则复活对方距离自身最近的阵亡棋子。如果对方也没有阵亡棋子，则什么也不做。我们这里使用的距离为曼哈顿距离，即若第 $i$ 枚棋子处于位置 $\left(x_i,y_i\right)$， 第 $j$ 枚棋子处于位置 $\left(x_j,y_j\right)$，那么此时两枚棋子的距离为 $\left|x_i-x_j\right|+\left|y_i-y_j\right|$。如果同时有多枚棋子距离当前棋子的曼哈顿距离一样，那么我们选择其中编号最大的棋子即可。棋子被复活后如果当前回合可以释放技能并且仍然没有被跳过，则会释放技能。

	7. 降维打击（2dsaigao）：利用超时空武器，向自己右前方发射动感光波，使得某个区域内的单位不能释放技能。该动感光波发射之后，遇到棋盘边缘或者障碍物则会发生方向改变的现象，如下图所示：

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

        中间格子为当前棋子所处的位置，其方向向左。每当该光波会进入一个有障碍物的格子或者棋盘边缘的时候，该光波就会改变自己的方向顺时针旋转 $90^\circ$。该光波每从一个格子的中心到达另一个格子的中心时我们称该光波走了 $1$ 的距离。当光波走了 $o$ 的距离之后，光波就会以当前格子为中心发生爆炸，使得所有距离当前格子曼哈顿距离不超过 $v$ 的棋子在接下来 $l$ 回合的时间内都不能释放技能，即从现在到第 $H+l$ 回合开始的这段时间内都不能释放技能。（详见样例第一组数据）

	8. 咕咕咕咕（gugugugu）：做人，绝不能普普通通的鸽了别人；要鸽，必须带着大家一起鸽。该技能效果为使得己方所有当前回合还没有释放技能的棋子全部跳过技能释放的环节，即使得己方还未释放技能的棋子当前回合不能释放技能。

	9. 反向传播（backward）：让时间暂停，让游戏倒流，让自身回到过去，回到之前的某个回合。若当前为第 $H$ 回合，该技能效果是回到 $l$ 回合前，则当前棋子 $i$ 会回到第 $H-l$ 回合。所谓回到第 $H-l$ 回合，即当前棋子的一下所有值都会变回第 $H-l$ 回合开始的时候的值：

        - 位置及方向。
        - 属性。
        - 是否存活以及复活时间。
        - 受到的技能影响的效果以及剩余时间。

        注意此时棋子 $i$ 的技能刷新时间并不会回到第 $H-l$ 回合的时间。（详见样例第三组数据）（技能刷新时间的规则会在下面说明）

	10. 葱之礼赞（hupraise）：葱的到来，使得今天变为了一个神圣的日子，要将红蓝双方的棋子进行配对。每个红方棋子可以和任何一个蓝方棋子进行配对，并且每个棋子都最多只能和对面一个棋子进行配对。第 $i$ 枚棋子 和第 $j$ 枚棋子能够配对的条件为两个棋子属于不同阵营并且 $a_i\oplus a_j$ 是 $3$ 的倍数（该符号为异或）。现在每当该技能发动时，你需要求出最多能够配多少对。

	**技能刷新规则**：对于所有技能，当前为第 $H$ 回合，如果第 $i$ 枚棋子释放了技能，那么在第 $H+z_i$ 回合的时候该技能才回复完毕，才能再次释放技能。如果第 $i$ 枚棋子在当前回合中了一个持续时间为 $l$ 回合的技能，那么该技能的影响将在第 $H+l$ 回合开始的时候消除。对于所有棋子，若其首轮技能回复时间为 $f_i$，技能回复时间为 $z_i$，则若没有其他棋子的影响，其第一次将在第 $f_i$ 回合释放技能，之后每 $z_i$ 回合再次释放技能。

3. 对于棋盘上所有格子，如果一个格子内既有红队棋子又有蓝队棋子，那么此时这个格子内的棋子便会发生交战。交战的规则如下：

    我们规定第 $i$ 枚棋子的战斗力为 $\binom{a_i}{b_i}$（该式子等价于 $C_{a_i}^{b_i}$）。在交战时，每次由红蓝双方派出己方在这个格子战力最大的棋子进行交战。假设红方派出第 $i$ 枚棋子，蓝方派出第 $j$ 枚棋子。如果红方蓝方两枚棋子战斗力一样，那么派出的两枚棋子均阵亡。若战斗力不一样，假设第 $i$ 枚棋子战力更高，那么第 $j$ 枚棋子阵亡，同时第 $i$ 枚棋子的两个属性变为 $\max\left(a_i-a_j,0\right),\max\left(b_i-a_j,0\right)$。不断重复以上操作直到一方棋子全部阵亡。若第 $i$ 枚棋子在当前回合即第 $H$ 回合阵亡，那么第 $i$ 枚棋子会在第 $H+r_i$ 回合开始的时候复活。第 $i$ 枚棋子复活之后将其两个属性将变为游戏开始时候的属性值，并且移除所有当前棋子身上的技能效果，其移动方向保持阵亡前的移动方向。棋子阵亡期间其技能正常回复，但是不能移动和释放技能，并且不受到其他任何技能的影响。

现在小葱告诉你所有与这游戏相关的东西，希望你按照游戏规则来进行游戏，并输出游戏结束之后每个棋子的位置。

inputFormat:
输入包含多组数据，第一行一个整数 $T$ 表示数据组数。接下来依次描述每组数据，对于每组数据：

* 第一行四个整数 $N,M,K,R$。

* 接下来 $N$ 行每行 $M$ 个数。对于第 $i$ 行第 $j$ 列的数，如果等于 $0$ 则代表第 $i$ 行第 $j$ 列的格子为普通格子，否则为障碍物。

* 接下来 $K$ 行，每行一开始有九个整数 $x_i,y_i,a_i,b_i,c_i,d_i,f_i,z_i,r_i$。代表第 $i$ 枚棋子一开始的位置位于第 $x_i$ 行 第 $y_i$ 列，其属性值为 $a_i,b_i$ 并且所属的阵营为 $c_i$。如果 $c_i=0$ 则为红方否则为蓝方。棋子 $i$ 一开始的朝向为 $d_i$，$d_i=0,1,2,3$ 分别表示上下左右四个方向。$f_i$ 为技能首轮回复时间，$z_i$ 为技能回复时间，即第 $i$ 枚棋子若在没有受到其他棋子影响的情况下，第一次将在第 $f_i$ 回合释放技能，之后每 $z_i$ 回合再次释放技能。$r_i$ 为其复活时间。接下来一个字符串 $s_i$ 为其技能的英文名字，已在每个技能后面注明了其对应的英文名字。对于不同的技能种类，会在当前行增加一定的输入值，具体如下：

	1. 重锤火花（toolihai），无增加的输入。

	2. 面子之王（faceking），无增加的输入。

	3. 头发掉光（onepunch），增加输入 $v_i,l_i$，代表该技能的增益效果和持续时间。

	4. 拉比哩比（rabiribi），增加输入 $v_i$ 代表技能的范围。

	5. 平安花火（firework），增加输入 $l_i$ 代表技能的影响时间。

	6. 救乌干达（viuganda），无增加的输入。

	7. 降维打击（2dsaigao），增加输入 $y_i,v_i,l_i$，代表光波能移动的距离、光波爆炸后能影响的范围以及技能的影响持续时间。

	8. 咕咕咕咕（gugugugu），无增加的输入。

	9. 反向传播（backward），增加输入 $l_i$，表示回到 $l_i$ 回合之前，数据保证不会回到游戏开始之前。

	10. 葱之礼赞（hupraise），无增加的输入。

outputFormat:
对于每组数据：

* 每当技能 $10$ 发动时，输出一行一个整数。

* 在游戏结束之后，输出 $K$ 行，每行两个整数代表第 $i$ 枚棋子现在处于哪一行哪一列。

hint:
### 样例解释

对于第一组数据，在左上方释放技能 $7$ 时，是朝着角落里射出的动感光波，所以碰到角落返回回射出点时，此时距离为 $1$，正好原地爆炸，使得技能 $2$ 无法放出。而右下方是在释放技能 $4$ 时，将对方击穿了地图的例子。

对于第二组数据，第一枚棋子每次向右走一步就会释放一次技能。第一回合走到 $(1,2)$，释放技能后属性变为 $(3,2)$，和对方交战后属性变为 $(2,1)$。第二回合走到 $(1,3)$，释放技能后属性变为 $(3,1)$，和对方交战后属性变为 $(3,0)$。第三回合走到 $(1,4)$，由于之前第一回合释放的技能效果消失，属性变回 $(2,0)$，再重新释放技能变为 $(3,0)$，然后被对手痛殴致死。所以最后停留在了 $(1,4)$。

对于第三组数据，该棋子每走两次就会释放技能跳回两回合前的状态，不断循环这样的过程。

### 数据范围

保证 $1\leq T\leq 20$，$1\leq N,M\leq 100$，$1\leq K\leq 200$，$1\leq R\leq 1000$。

保证所有的附加输入除了技能 $3,5,7$ 的影响时间大于 $0$ 以外，剩下均大于等于 $0$。

保证棋子一开始不在障碍物上，一开始以及增幅的属性值均不超过 $1000$（但不保证增幅后的属性超过 $1000$）

保证技能的首轮回复时间、之后的回复时间以及复活时间均大于 $0$。

### 版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai/) 对此次比赛的支持。

题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。


title: [THUPC2018] 城市地铁规划

description:
经过选拔，Kiana成为了可乐城的市长，为了兑现选举承诺，她决定在可乐城的 $n$ 个重要地标之间修建地铁。

可乐城的交通状况并不复杂，在任意两个地标之间修建一条地铁轨道都是可行的，但是地铁轨道并不是越多越好，如果有太多地铁从一个地标处经过，该地标的拥堵程度将大幅增加。为此，Kiana决定给每个地标一个便利度来衡量拥堵程度，如果有 $d$ 条地铁轨道经过了某个地标，那么该地标的便利度为 $f(d)\mod 59393$，其中 $f(x)=\sum_{i=0}^{k}a_ix^i$ 是Kiana指定的一个 $k$ 次多项式。

因为修建地铁有一定的成本，所以Kiana希望新建的地铁轨道尽可能少，但任意两座地标之间都需要能通过地铁相互到达。Kiana想知道在给定的条件下，什么样的修建方案可以使得地标的便利度之和最大。由于她不会做，所以希望你来告诉她答案。

inputFormat:
输入第一行包含两个正整数 $n$ 和 $k$，分别表示可乐城的地标总数和Kiana指定的多项式次数，地标的编号依次为 $1$ 至 $n$，数据保证 $n\leq 3000$且 $k\leq 10$。

输入第二行包含 $k+1$ 个非负整数 $a_0\sim a_k$，即Kiana指定的多项式的系数，数据保证所有的 $a_i\leq 50$。

outputFormat:
输出由若干行组成，第一行包含两个用空格隔开的正整数 $m$ 和 $S$，分别表示你的方案中修建的地铁轨道数量与最终的便利度之和。

接下来 $m$ 行，每行包含两个用空格隔开的正整数 $u$ 和 $v$，表示在第 $u$ 和第 $v$ 个地标之间修建了一条地铁轨道。

本题将采用Special Judge，如果有多种方案使得地标的便利度之和最大，输出其中任意一种即可。

hint:
### 备注

本题因为一些原因只保留了后 $50$ 组数据。

### 版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai/) 对此次比赛的支持。

题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。


title: [THUPC2018] 弗雷兹的玩具商店

background: 物是人非事事休，欲语泪先流。

description:
弗雷兹在 C 市有一个玩具店，店里有 $n$ 种玩具，编号依次为 $1,2,\dots, n$，编号为 $i$ 的玩具的单价为 $c_i$ 元，一个该玩具提供的愉悦度为 $v_i$ 。

突然有一天，C市来了 $m$ 个小朋友。据可靠消息，这些小朋友会在一些时刻一起来店里买东西，其中第 $i$ 个小朋友每次都会带 $i$ 元（ $1\leq i\leq m$ ）。

由于某些玩具特别优秀，所以每次小朋友们都会在特定的编号范围内挑选玩具。

除此之外，由于小朋友们在一年前的清华校赛中就愉悦得无法自拔，所以弗雷兹放弃了对他们的治疗，于是小朋友们就可以无限制地购买玩具了。也就是说，对于任意玩具，每个小朋友在每次的购买件数都可以是任意的非负整数。

时代飞速发展，玩具的受欢迎程度和价格也会随着时代的发展而改变。

为了方便你处理这些信息，Yazid 进行了整理，发现这些日子里，弗雷兹的玩具商店里共发生了 $Q$ 个事件。

对于每个事件，都有 $3$ 个基本参数 $op,l,r$ 。其中 $op$ 为 $1$ 至 $3$ 之间的整数，代表了事件的类别：

1. 对于 $op=1$ 的事件，Yazid 还会给你一个额外参数 $d$ ，表示这是一个**价格调整**事件：将编号在区间 $[l,r]$ 内的玩具的单价 $c$ 全部增加 $d$ 元。为了防止单价超过 $m$ 元导致玩具永远无法被小朋友们购买，弗雷兹会将所有超过 $m$ 的单价减去 $m$。（保证 $d$ 为不超过 $m$ 的正数）

2. 对于 $op=2$ 的事件，Yazid还会给你一个额外参数 $b$ ，表示这是一个**愉悦修正**事件：将编号在区间 $[l,r]$ 内的玩具的愉悦度 $v$ 全部增加 $b$ 。（需要注意这里的 $b$ 可能是负数）

3. 对于 $op=3$ 的事件，表示**购买**事件：所有的 $m$ 个小朋友来到弗雷兹的玩具商店，在编号范围在 $[l,r]$ 内的玩具中进行随意地购买。

现在，对于每一次的购买事件，你想知道：

1. 所有小朋友所能获得的最大愉悦度之和。

2. 所有小朋友所能获得的最大愉悦度的异或和（异或运算是 $\mathrm{xor}$ 运算，即 C++/Java/Python 中的 `^` 运算）。

inputFormat:
* 第 $1$ 行 $2$ 个正整数 $n,m$，分别表示玩具数量、以及小朋友的数量。

* 第 $2$ 行 $n$ 个正整数 $c_1,\dots,c_n$，依次描述各玩具的单价。

* 第 $3$ 行 $n$ 个正整数 $v_1,\dots,v_n$，依次描述各玩具的愉悦度。

* 第 $4$ 行 $1$ 个非负整数 $Q$，表示事件的数量。

* 接下来 $Q$ 行依次描述所有事件，每行描述一个事件。每行的开头是 $3$ 个整数 $op,l,r$，意义见题目描述。

	* 如果 $op=1$，接下来跟随 $1$ 个该事件的额外参数（整数） $d$，意义见题目描述。

	* 如果 $op=2$，接下来跟随 $1$ 个该事件的额外参数（整数） $b$，意义见题目描述。

	* 如果 $op=3$，接下来无任何额外参数。

	* 保证 $1\leq l\leq r\leq n$。

对于每一行，如果包含多个数，则用单个空格将它们隔开。

outputFormat: * 对于每个购买事件，输出一行 $2$ 个用空格隔开的整数，依次表示所有小朋友所能获得的最大愉悦度之和、以及所有小朋友所能获得的最大愉悦度的异或和。

hint:
### 样例解释

对于第 $1$ 个购买事件，各位小朋友（编号从小到大，即从 $1$ 至 $10$）能够获得的最大愉悦度依次为：$100,300,400,600,700,2333,2433,2633,2733,2933$。

对于第 $2$ 个购买事件，各位小朋友（编号从小到大，即从 $1$ 至 $10$）能够获得的最大愉悦度依次为：$100,200,300,400,500,2333,2433,2533,2633,2733$。

对于第 $3$ 个购买事件，各位小朋友（编号从小到大，即从 $1$ 至 $10$）能够获得的最大愉悦度依次为：$666,1332,1998,2664,3330,3996,4662,5328,5994,6660$。

对于第 $4$ 个购买事件，各位小朋友（编号从小到大，即从 $1$ 至 $10$）能够获得的最大愉悦度依次为：$0,0,300,300,300,600,733,733,900,1033$。

根据这些信息，你将很容易计算出答案。

### 数据范围

保证 $1\le n\leq 200,000$，$1\le m\leq 60$，$0\le Q\leq 30,000$。

保证 $1\leq c_i,d\leq m$。

保证 $0\leq v_i\leq 10^7$，$\left| b\right|\leq 10^3$。

### 提示

这个提示本不该有，但善良的出题人还是想提醒你：所有小朋友所能获得的最大愉悦度之和有可能超过 $32$ 位有符号整数的范围。

### 版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai) 对此次比赛的支持。

题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。


title: [THUPC2018] 蛋糕

description:
最近，菲菲学会了做蛋糕，她做了一个 **4D** 的蛋糕送给牛牛，这个蛋糕的大小是： $a \times b \times c \times d$。

蛋糕所有的表面都抹着奶油，牛牛想把蛋糕沿着与表面平行的超平面，切成 $1 \times 1 \times 1 \times 1$ 的小块。

现在，牛牛想知道，在这些小块蛋糕中，有 $0$ 个、$1$ 个、$2$ 个……$8$ 个表面抹着奶油的有分别有多少块。

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

接下来依次描述每组数据，对于每组数据：

* 一行 $4$ 个正整数 $a$、$b$、$c$、$d$。（四个正整数都在 $10^6$ 以内）

outputFormat:
对于每组数据，输出 $1$ 行：

* 一行输出 $9$ 个整数，分别表示有 $0$ 个、$1$ 个、$2$ 个……$8$ 个表面抹着奶油的小块蛋糕数量，所有值之间用单个空格隔开。为了防止答案过大，你只需要输出答案除以 $2148473648$ 的余数。

hint:
### 样例解释

对于第一组数据，把 $2 \times 2 \times 2 \times 3$ 的蛋糕切成小块后，共形成了 $24$ 个小立方体，其中有 $16$ 个小块分别与其他 $4$ 个小块相邻，因此它们有 $4$ 个面涂有奶油，而另外 $8$ 个小块分别与其他 $5$ 个小块相邻，因此它们有 $3$ 个面涂有奶油。

### 版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai) 对此次比赛的支持。

题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。


title: [THUPC2018] 生生不息

description:
生命游戏是一个经典的零玩家游戏。

游戏在一块 $n \times m$ 的方格棋盘上进行，初始时，棋盘上的一些格子中有生命，另一些格子中没有生命。

在新的一天开始时，如果一个格子周围的 $8$ 个（边界上的格子也许不到 $8$ 个）格子中，在前一天有恰好$2$个或$3$个格子中有生命，则这个格子上的生命可以继续生存，如果周围的格子中恰好有$3$个格子在前一天有生命且这个格子中前一天没有生命，则会在这个格子中诞生新的生命。在其他情况下，该格子中原有的生命则会死去且不会产生新的生命。

如果在某一天，棋盘上所有的格子里都没有生命，显然，在接下来的时间里，所有的格子中再也不会有生命了，我们就说这些生命灭绝了。

现在，牛牛希望让菲菲来决定游戏开始时棋盘上的每个格子中是否有生命。

而他想知道，在游戏开始时，菲菲有多少种不同的方法使得棋盘上的生命永远也不会灭绝。

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

接下来依次描述每组数据，对于每组数据：

* 一行 $2$ 个正整数 $n$、$m$。（$n,m<=5$）

outputFormat:
对于每组数据，输出 $1$ 行：

* 一行输出 $1$ 个整数，表示问题的答案。

hint:
来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 [Pony.ai](http://pony.ai) 对此次比赛的支持。

题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。


title: [BJOI2016] 水晶

background:
不用惊慌，今天的题都不是小强出的。

——融入了无数心血的作品，现在却不得不亲手毁掉，难以体会他的心情啊。

——那也是没有办法的事情，能量共振不消除的话……

望着已经被装上炸药的水晶，02放下了望远镜，看向了手中的共振分析报告。

还是会有一些水晶，幸存下来的…… 也许吧。

description:
地图由密铺的六边形单元组成，每个单元与其他六个单元相邻。

为了方便起见，我们用坐标 $(x,y,z)$ 描述一个单元的位置，表示从原点开始按如图所示的 $x,y,z$ 方向各走若干步之后到达的地方。

有可能有两个坐标描述同一个单元，比如 $(1,1,1)$ 和 $(0,0,0)$ 描述的都是原点。

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

显然 $(x,y,z)$ 单元和 $(x+1,y,z)$，$(x-1,y,z)$ ，$(x,y+1,z)$，$(x,y-1,z)$，$(x,y,z+1)$，$(x,y,z-1)$ 相邻。

有 $N$ 块水晶位于地图的单元内，第 $i$ 块水晶位于坐标 $(x_i, y_i, z_i)$ 所表示的单元中，并拥有 $c_i$ 的价值，每个单元内部可能会有多块水晶。

地图中，有一些单元安装有能量源。如下图，任何满足 $x+y+z$ 是 $3$ 的整数倍的坐标所描述的单元内都安装有能量源。

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

有能量源的单元中的水晶价值将会额外增加 $10\%$。如果三块水晶所在的单元满足特定排列，那么它们将会引发共振。

共振分两种，$a$ 共振和 $b$ 共振。

$a$ 共振：如果三块水晶所在的单元两两相邻地排成一个三角形，那么会引起 $a$ 共振。

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

图中每一个三角形表示这三个单元各有一块水晶将会发生一个 $a$ 共振。

$b$ 共振：如果三块水晶所在的单元依次相邻地排成一条长度为 $2$ 的直线段，且正中间的单元恰好有能量源，那么会引起b共振。

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

图中粉红色线段表示这三个单元各有一块水晶将会发生一个 $b$ 共振，黑色线段表示即使这三个单元有水晶也不会发生 $b$ 共振。

现在你要炸掉一部分水晶，使得任何共振都不会发生的前提下，剩余水晶的价值总和最大。

inputFormat:
第一行一个正整数 $N$，表示水晶数量。
接下来 $N$ 行，每行四个整数用空格分开的整数 $x_i,y_i,z_i,c_i$，表示一个水晶的位置和价值。
有可能有水晶的位置重合。

outputFormat: 一行一个实数，表示剩余水晶的价值总和，四舍五入保留 $1$ 位小数。

hint:
【样例 $1$ 说明】

四块水晶排成一个菱形，没有 $b$ 共振，有 $2$ 处 $a$ 共振，分别是 $1,2,4$ 号水晶和 $1,3,4$ 号水晶形成的三角形。
因此，为了消除两处 $a$ 共振，有如下 $3$ 种方案：

1. 炸掉 $1$ 号水晶，留下 $2,3,4$ 号水晶，总剩余价值 $5+7+13=25$
2. 炸掉 $4$ 号水晶，留下 $1,2,3$ 号水晶，总剩余价值 $11 \times(1+10\%)+5+7=24.1$
3. 炸掉 $2,3$ 号水晶，留下$1,4$ 号水晶，总剩余价值 $11 \times (1+10\%)+13=25.1$

因此我们采用第三种方案，最大总剩余价值为$25.1$。

【数据范围】

$1\le N \le 50000$
$1\le c_i \le 1000$
$-1000 \le x_i,y_i,z_i \le 1000$


title: [BJOI2016] 回转寿司

description:
酷爱日料的小Z经常光顾学校东门外的回转寿司店。在这里，一盘盘寿司通过传送带依次呈现在小Z眼前。

不同的寿司带给小Z的味觉感受是不一样的，我们定义小Z对每盘寿司都有一个满意度。

例如小Z酷爱三文鱼，他对一盘三文鱼寿司的满意度为 $10$；小Z觉得金枪鱼没有什么味道，他对一盘金枪鱼寿司的满意度只有 $5$；小Z最近看了电影《美人鱼》，被里面的八爪鱼恶心到了，所以他对一盘八爪鱼刺身的满意度是 $-100$。

特别地，小Z是个著名的吃货，他吃回转寿司有一个习惯，我们称之为“狂吃不止”。具体地讲，当他吃掉传送带上的一盘寿司后，他会毫不犹豫地吃掉它后面的寿司，直到他不想再吃寿司了为止。

今天，小Z再次来到了这家回转寿司店，$N$ 盘寿司将依次经过他的面前。其中，小Z对第 $i$ 盘寿司的满意度为$a_i$。

小Z可以选择从哪盘寿司开始吃，也可以选择吃到哪盘寿司为止。他想知道共有多少种不同的选择，使得他的满意度之和不低于 $L$，且不高于 $R$。

注意，虽然这是回转寿司，但是我们不认为这是一个环上的问题，而是一条线上的问题。即，小Z能吃到的是输入序列的一个连续子序列；最后一盘转走之后，第一盘并不会再出现一次。

inputFormat:
第一行三个正整数 $N,L,R$，表示寿司盘数，满意度的下限和上限。
第二行包含 $N$ 个整数 $a_i$，表示小Z对寿司的满意度。

outputFormat: 一行一个整数，表示有多少种方案可以使得小Z的满意度之和不低于 $L$ 且不高于 $R$。


title: [BJOI2016] IP地址

description:
路由表中每一项对应了一个形如 1011101????????????????????????? 的规则，会匹配指定的前缀为给定形式的 $\texttt{ip}$。

当有多个规则匹配时，前缀最长的生效。同一时刻不会有多个匹配的规则的前缀一样长。每一个时刻，会有一条规则被加入，或者之前被加入的某条规则会过期。

给一系列 $\texttt{ip}$，问每一个 $\texttt{ip}$ 在一个给定的时间区间内匹配到的生效规则变了几次？

例如，有一系列事件：

$\texttt{Add}$ $110$
$\texttt{Add}$ $11$
$\texttt{Del}$ $110$
$\texttt{Del}$ $11$
$\texttt{Add}$ $110$

那么，$\texttt{ip}$ 地址 11011101001001010101011101000010 在这五个时刻之后匹配到的生效规则分别是：

$110$ (第一条)，
$110$ (第一条)，
$11$ (第二条)，
空，
$110$ (第三条)。

其中，在第二个事件后到第五个事件后的这段过程中，一共变了 $3$ 次。

inputFormat:
第一行两个正整数 $n,q$，表示事件数有询问数。
接下来 $n$ 行，每行描述一个事件，格式为：

$\texttt{Add}$ $s$ 表示新建一个规则，匹配前缀为 $s$ 的所有 $\texttt{ip}$。
$\texttt{Del}$ $s$ 表示把当前前缀 $s$ 对应的规则删掉(过期)。保证之前有这样的一条规则还没被删。

接下来 $q$ 行，每行一个 $\texttt{ip}$ 与两个正整数 $a,b$，表示查询在第 $a$ 个事件后到第 $b$ 个事件的这段时间里，这个 $\texttt{ip}$ 匹配到的生效规则变化的次数。 $\texttt{ip}$ 用01字符串来表示。

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

hint:
【数据范围】

$1\le n,q \le 10^5$


title: 区间本质不同子串个数

description:
给定一个长度为 $n$ 的仅包含小写字母的字符串 $S$，$m$ 次询问由 $S$ 的第 $L$ 到第 $R$ 个字符组成的字符串包含多少个本质不同的非空子串。

定义两个字符串 $a,b$ 相同当且仅当 $|a|=|b|$ 并且对于 $i\in[1,|a|]$ 都有 $a_i=b_i$。

inputFormat:
第一行一个长度为 $n$ 的字符串 $S$。

第二行一个整数 $m$，表示询问次数。

接下来 $m$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，描述第 $i$ 次询问。

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

hint:
#### 样例 1 解释

- 第一次询问，字符串为 $\texttt{aa}$，包含 $\texttt{a}$,$\texttt{aa}$ 共 $2$ 种本质不同子串。
- 第二次询问，字符串为  $\texttt{aba}$，包含  $\texttt{a},\texttt{b},\texttt{ab},\texttt{ba},\texttt{aba}$, 共  $5$ 种本质不同子串。
- 第三次询问，字符串为 $\texttt{babc}$，包含 $\texttt{a}$,$\texttt{b}$,$\texttt{c}$,$\texttt{ab}$,$\texttt{ba}$,$\texttt{bc}$,$\texttt{bab}$,$\texttt{abc}$,$\texttt{babc}$ 共 $9$ 种本质不同子串。

#### 数据规模与约定

- 对于 $20\%$ 的数据，满足 $n\leq 3\times 10^3$，$m\leq 3\times 10^3$。
- 对于 $100\%$ 的数据，满足 $1\leq n\leq 10^5$，$1\leq m\leq 2\times 10^5$，$1\leq l_i\leq r_i\leq n(i\in[1,m])$。


title: [PKUSC2018] 星际穿越

description:
有 $n$ 个星球，它们的编号是 1 到 $n$，它们坐落在同一个星系内，这个星系可以抽象为一条数轴，每个星球都是数轴上的一个点，特别地，编号为 $i$ 的星球的坐标是 $i$。

一开始，由于科技上的原因，这 $n$ 个星球的居民之间无法进行交流，因此他们也不知道彼此的存在。现在，这些星球独立发展出了星际穿越与星际交流的工具。对于第 $i$ 个星球，他通过发射强力信号，成功地与编号在 $[l_i,i-1]$ 的所有星球取得了联系(编号为 1 的星球没有发出任何信号)，取得联系的两个星球会建立 **双向** 的传送门，对于建立了传送门的两个星球 $u,v$，$u$ 上的居民可以花费 1 单位时间传送到 $v$，$v$ 上的居民也可以花费 1 单位时间传送到 $u$ ，我们用 $dist(x,y)$ 表示从编号为 $x$ 的星球出发，通过一系列星球间的传送门，传送到编号为 $y$ 的星球最少需要花费的时间。

现在有 $q$ 个星际商人，第 $i$ 个商人初始所在的位置是 $x_i$, 他的目的地是 $[l_i,r_i]$ 中的其中一个星球，保证 $l_i<r_i<x_i$ 。他会在这些星球中等概率挑选一个星球 $y$ (每个星球都有一样的概率被选中作为目的地)，然后通过一系列星球的传送门，**花费最少的时间**到达星球 $y$ 。商人想知道他花费的期望时间是多少？也就是计算 $\frac{1}{r_i-l_i+1}{\sum_{y=l_i}^{r_i}{dist(x_i,y)}}$ 。

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

第二行 $n-1$ 个正整数，第 $i$ 个正整数为  $l_{i+1}$ ，表示编号在 $[l_{i+1},i]$ 区间内所有星球已经与编号为 $i+1$ 的星球取得了联系，并且可以通过花费 1 单位进行彼此的传输。保证 $l_{i+1}\leq i$

第三行一个正整数 $q$ ，表示询问组数。

接下来 $q$ 行，每行三个数字 $l_i,r_i,x_i$ ，表示在 $[l_i,r_i]$ 这个区间中等概率选择一个星球 $y$，$dist(x_i,y)$ 的期望。保证 $l_i<r_i<x_i$

outputFormat:
对于每组询问，注意到答案必然是一个有理数，因此以 $p/q$ 的格式输出这个有理数，要求 $\gcd(p,q)=1$ 。

如果答案为整数 $m$ ，输出 $m/1$ 。

hint:
样例对应的无向图如下：![ex](https://cdn.luogu.com.cn/upload/pic/63831.png)

对于 $20\%$ 的数据，满足 $n \leq 100$。

对于另 $25\%$ 的数据，满足 $n\leq 2000$

对于另 $25\%$ 的数据，满足 $n\leq 5000$

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


title: [PKUSC2018] 神仙的游戏

description:
小 D 和小 H 是两位神仙。他们经常在一起玩神仙才会玩的一些游戏，比如 “口算一个 4 位数是不是完全平方数” 。

今天他们发现了一种新的游戏：首先称 $s$ 长度为 $len$ 的前缀成为 border 当且仅当 $s[1\dots len ] = s[|s|-len + 1\dots |s|]$ 。给出一个由 $\texttt{01?}$ 组成的字符串 $s$，将 $s$ 中的问号用 $\texttt{01}$ 替换，对每个 $len$ 口算是否存在替换问号的方案使得 $s$ 长度为 $len$ 的前缀成为 border，把这个结果记做 $f(len)\in \{0,1\}$。如果 $s$ 长度为 $len$ 的前缀能够成为 border 那么 $f(len) = 1$，否则 $f(len) = 0$。

由于小 D 和小 H 是神仙，所以他们计算的 $s$ 的长度很长，因此把计算的结果一一比对会花费很长的时间。为了方便比对，他们规定了一个校验值：$(f(1)\times 1^2)~\operatorname{xor}~(f(2)\times 2^2)~\operatorname{xor}~(f(3)\times 3^2)~\operatorname{xor}~\dots~\operatorname{xor}~(f(n)\times n^2)$ 来校验他们的答案是否相同。$\operatorname{xor}$ 表示按位异或。但是不巧，在某一次游戏中，他们口算出的校验值并不一样，他们希望你帮助他们来计算一个正确的校验值。当然，他们不强迫你口算，可以编程解决。

inputFormat: 一个串 $s$，保证每个字符都是 $\texttt 0$，$\texttt 1$ 或者 $\texttt ?$。

outputFormat: 输出字符串的校验值， 即 $(f(1)\times 1^2)~\operatorname{xor}~(f(2)\times 2^2)~\operatorname{xor}~(f(3)\times 3^2)~\operatorname{xor}~\dots~\operatorname{xor}~(f(n)\times n^2)$。


title: [PKUSC2018] PKUSC

description:
九条可怜是一个爱玩游戏的女孩子。

最近她在玩一个无双割草类的游戏，平面上有 $n$ 个敌人，每一个敌人的坐标为 $x_i,y_i$。可怜有一个技能是在平面上画一个 $m$ 个点的简单多边形，并消灭所有**严格**在多边形内部的敌人。

不难发现如果想要快速的消灭敌人的话，只要画一个足够大的简单多边形就行了。但是这样的游戏性就太差了。于是可怜打算为游戏增加一定的随机性。

可怜在平面上随便画了一个 $m$ 个点的简单多边形 $(a_i,b_i)$。接下来可怜打算按照 $[-\pi,\pi)$ 上的均匀分布随机选取数字 $\alpha$（可以理解为等概率选取），并把这个简单多边形绕原点逆时针旋转 $\alpha$ 的角度（弧度制）。

现在可怜给你了每一个点的坐标，多边形的坐标，你的任务是帮助可怜计算在随机旋转后她期望可以消灭多少个敌人。

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

接下来 $n$ 行每行两个整数 $x_i,y_i$ 描述了一个敌人的坐标。

接下来 $m$ 行每行两个整数 $a_i,b_i$ 按照逆时针的顺序描述了简单多边形的每一个顶点。

outputFormat: 输出一行一个整数表示期望值，保留五位小数。同时保证所有数据的小数点后第 $6$ 位在舍入前不会是 $4$ 和 $5$。

hint:
### 样例解释

如果你对概率与期望不怎么了解，这儿给出一些 Hint:

1. 设 $P_i$ 为旋转之后恰好能消灭 $i$ 个敌人的概率，那么期望就是 $\sum_{i=1}^n iP_i$.
2. 计算 $P_i$ 的一个方法是，在所有 $[-\pi,\pi)$ 范围内的旋转角度中，旋转后恰好消灭 $i$ 个敌人的角度构成了 $t_i$ 个区间 $(l_j,r_j)$（开闭不影响），那么 $P_i=\frac{\sum_{j=1}^{t_i}(r_j-l_j)}{2\pi}$.

在这题中：能消灭 $0$ 个敌人的区间是 $[\frac{\pi}{2},\pi),[-\pi,-\frac{\pi}{2}]$，能消灭 $1$ 个敌人的区间是 $(-\frac{\pi}{2},0),(0,\frac{\pi}{2})$。于是 $P_0 = P_1=\frac{1}{2}$。所以答案为 $\frac{1}{2}=0.50000$.

### 数据范围

对于 $30\%$ 的数据，$n,m \leq 15$。

对于另外 $30\%$ 的数据，选择的简单多边形是一个凸多边形。

对于 $100\%$ 的数据，$n \leq 200, m \leq 500, |x|,|y| \leq 10^6$.


title: 差分与前缀和

description:
给定一个长为 $n$ 的序列 $a$，求出其 $k$ 阶差分或前缀和。
结果的每一项都需要对 $1004535809$ 取模。

inputFormat:
第一行三个整数 $n,k,t$，若 $t=0$ 表示求前缀和，$t=1$ 表示求差分。
第二行 $n$ 个整数，表示序列 $a$。

outputFormat: 输出一行 $n$ 个整数，表示 $a$ 的 $k$ 阶差分或前缀和。


title: [NOI2019] 回家路线

background: 本题原题数据强度较低，若想要测试较强数据可以去 [P6302](https://www.luogu.com.cn/problem/P6302)，除数据范围外均与原题相同。

description:
猫国的铁路系统中有 $n$ 个站点，从 $1 - n$ 编号。小猫准备从 $1$ 号站点出发，乘坐列车回到猫窝所在的 $n$ 号站点。它查询了能够乘坐的列车，这些列车共 $m$ 班，从$1 - m$编号。小猫将在 $0$ 时刻到达 $1$ 号站点。对于 $i$ 号列车，它将在时刻 $p_i$ 从站点 $x_i$ 出发，在时刻 $q_i$ 直达站点 $y_i$，小猫只能在时刻 $p_i$ 上 $i$ 号列车，也只能在时刻 $q_i$ 下 $i$ 号列车。小猫可以通过多次换乘到达 $n$ 号站点。一次换乘是指对于两班列车，假设分别为 $u$号与 $v$ 号列车，若 $y_u = x_v$ 并且 $q_u \leq p_v$，那么小猫可以乘坐完 $u$ 号列车后在 $y_u$ 号站点等待 $p_v - q_u$ 个时刻，并在时刻 $p_v$ 乘坐 $v$ 号列车。

小猫只想回到猫窝并且减少途中的麻烦，对此它用烦躁值来衡量。

- 小猫在站点等待时将增加烦躁值，对于一次 $t (t \geq 0)$ 个时刻的等待，烦躁值将增加 $At^2 + Bt + C$，其中 $A, B,C$ 是给定的常数。注意：小猫登上第一班列车前，即从 $0$ 时刻起停留在 $1$ 号站点的那些时刻也算作一次等待。

- 若小猫最终在时刻 $z$ 到达 $n$ 号站点，则烦躁值将再增加 $z$。

形式化地说，若小猫共乘坐了 $k$ 班列车，依次乘坐的列车编号可用序列 $s_1, s_2, \cdots , s_k$表示。该方案被称作一条可行的回家路线，当且仅当它满足下列两个条件：

1. $x_{s1} = 1$ , $y_{sk} = n$

2. 对于所有 $j (1 \leq j < k)$，满足 $y_{sj} = x_{s_{j+1}}$ 且 $q_{sj}\leq p_{s_{j+1}}$

对于该回家路线，小猫得到的烦躁值将为：

$$q_{s_k}+(A\times p_{s_1}^2+B\times p_{s_1}+C)+\sum_{j=1}^{k-1}(A(p_{s_{j+1}}-q_{s_j})^2+B(p_{s_{j+1}}-q_{s_j})+C)$$

小猫想让自己的烦躁值尽量小，请你帮它求出所有可行的回家路线中，能得到的最
小的烦躁值。题目保证至少存在一条可行的回家路线。

inputFormat:
第一行五个整数 $n, m, A, B,C$，变量意义见题目描述。

接下来 $m$ 行，第 $i$ 行四个整数 $x_i, y_i, p_i, q_i$，分别表示 $i$ 号列车的出发站、到达站、出发时刻与到达时刻。

outputFormat: 输出仅一行一个整数，表示所求的答案。


title: [NOI2019] 机器人

background: 时限 3 秒，内存 512MB

description:
小 R 喜欢研究机器人。

最近，小 R 新研制出了两种机器人，分别是 `P` 型机器人和 `Q` 型机器人。现在他要测试这两种机器人的移动能力，测试在从左到右排成一排的 $n$ 个柱子上进行，柱子用$1 - n$ 依次编号，$i$ 号柱子的高度为一个正整数 $h_i$。机器人**只能在相邻柱子间移动**，即：若机器人当前在 $i$ 号柱子上，它只能尝试移动到 $i - 1$ 号和 $i + 1$ 号柱子上。

每次测试，小 R 会选取一个起点 $s$，并将两种机器人均放置在 $s$ 号柱子上。随后它们会按自己的规则移动。

`P` 型机器人会一直**向左**移动，但它**无法**移动到比起点 $s$ **更高**的柱子上。更具体地，`P` 型机器人在 $l (l \leq s)$ 号柱子停止移动，**当且仅当**下列两个条件均成立：

- $l = 1$ 或 $h_{l-1} > hs$。

- 对于满足 $l \leq j \leq s$ 的 $j$，有 $h_j \leq h_s$。

`Q` 型机器人会一直**向右**移动，但它**只能**移动到比起点 $s$ **更低**的柱子上。更具体地，`Q` 型机器人在 $r (r \geq s)$ 号柱子停止移动，**当且仅当**下列两个条件均成立：

- $r = n$ 或 $h_{r+1} \geq h_s$。

- 对于满足 $s < j \leq r$ 的 $j$，有 $h_j < h_s$。

现在，小 R 可以设置每根柱子的高度，$i$ 号柱子可选择的高度范围为 $[A_i, B_i]$，即$A_i \leq h_i \leq B_i$。小 R 希望**无论**测试的起点 $s$ 选在哪里，两种机器人移动过的柱子数量的差的绝对值都**小于等于**$2$。他想知道有多少种柱子高度的设置方案满足要求，小 R 认为两种方案不同当且仅当存在一个 $k$，使得两种方案中 $k$ 号柱子的高度不同。请你告诉他满足要求的方案数模 $10^9 + 7$ 后的结果。

inputFormat:
第一行一个正整数 $n$，表示柱子的数量。

接下来 $n$ 行，第 $i$ 行两个正整数 $A_i, B_i$，分别表示 $i$ 号柱子的最小和最大高度。

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


title: [NOI2019] 序列

description:
给定两个长度为 $n$ 的正整数序列 $\{a_i\}$ 与 $\{b_i\}$，序列的下标为 $1, 2, \cdots , n$。现在你需要分别对两个序列各指定**恰好** $K$ 个下标，要求**至少**有 $L$ 个下标在两个序列中都被指定，使得这 $2K$ 个下标在序列中对应的元素的总和**最大**。

形式化地说，你需要确定两个长度为 $K$ 的序列 $\{c_i\}, \{d_i\}$，其中
$1 \leq c_1 < c_2 < \cdots < c_K \leq n , 1 \leq d_1 < d_2 < \cdots < d_K \leq n$

并要求 $\{c_1, c_2, \cdots , c_K\} \cap \{d_1, d_2, · · · , d_K\}\geq L$

目标是最大化 $\sum^{K}_{i=1} a_{c_i} +\sum^{K}_{i=1} b_{d_i}$

inputFormat:
**本题输入文件包含多组数据**。

第一行一个正整数 $T$ 表示数据组数。接下来每三行表示一组数据。

每组数据第一行三个整数 $n, K, L$，变量意义见题目描述。

每组数据第二行 $n$ 个整数表示序列 $\{a_i\}$。

每组数据第三行 $n$ 个整数表示序列 $\{b_i\}$。

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


title: [CCO2015] 冰上车

description:
**本题译自 [CCO 2015](https://cemc.math.uwaterloo.ca/contests/computing/2015/index.html) Day2 T1「[Cars on Ice](https://cemc.math.uwaterloo.ca/contests/computing/2015/stage%202/day2.pdf)」**

在圣诞夜守卫银行是一件非常无聊的事情。这就是 Barry 想要去停车场附近溜冰的原因。然而因为其他守卫把车停在了那里，停车场并不是空的。所以 Barry 决定把他们的车推出停车场。他注意到那些停着的车面对的方向是东南西北之一。因为停车场结冰了，所以推一辆车将会使得他滑行直至离开停车场或撞上其他的车。这些车只能朝他们面向的方向推。为了不撞车，Barry 找你帮忙，让你帮他计算出将车推出停车场的顺序，以便他清空停车场。

inputFormat:
第一行包括两个整数 $N,M$，表示停车场的行列数。
接下来 $N$ 行每行 $M$ 个字符，描述一个停车场。其中 `.` 代表这是一个空的车位，而 `N`, `E`, `W`, `S` 表示一辆车，分别表示这辆车面朝北、南、东、西。

outputFormat:
输出在不发生撞车的情况下将车推出的顺序，每辆车按格式 $(r,c)$ 输出，其中 $(r,c)$ 是车在停车场中的坐标，$(0,0)$ 为左上角，$(N-1,M-1)$ 为右下角。
保证至少有一个有效解，如果有多个解，输出任意一个。

hint:
#### 样例解释 1

唯一一辆在开始时没有被其他车挡住的是在 $(4,3)$ 的车，当这架车被推到停车场右边后，在它上面的车（在 $(1,3)$ 的车）可以被推出，然后是在 $(1,1)$ 的车，最后是在 $(4,1)$ 的车，停车场得以清空。

#### 样例解释 2

两辆车都可以作为第一个被推出停车场的车，所以样例输出 2 是正确的，同时顺序与其相反的输出也是正确的。

#### 数据范围

对于 $70\%$ 的数据，$1\le N,M \le 100$；

对于 $100\%$ 的数据，$1\le N,M \le 2000$。


title: [CCO2015] 定音鼓手

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

计算机科学家不常帮助打击乐家，但今天，这将改变。既然我们没法同时帮助所有打击乐家，那么就先设法帮助定音鼓手。

定音鼓是一种能被调整至特定音调的大鼓。定音鼓手用编号为 $1\dots D$ 的 $D$ 个定音鼓演奏。现在，他们在演奏一个有 $N$ 个音符的小节，第 $i$ 个音符演奏 $T_i$ 秒，它的音调是 $P_i$，而 $P_i$ 属于 $\{\text{F},$ $\text{F}^♯,$ $\text{G,}$ $\text{G}^♯,$ $\text{A},$ $\text{A}^♯,$ $\text{B},$ $\text{C},$ $\text{C}^♯,$ $\text{D},$ $\text{D}^♯,$ $\text{E}\}$ 这 12 个音符中的一个音符。

在一个时刻，一个定音鼓必须先被调到某个音调，才能用来弹奏这个音调，因此定音鼓手能演奏音符 $i$ 当且仅当这个定音鼓在时间 $T_i$ 调到了音调 $P_i$。

在这个片段当中的每个音符都是在一个八度的范围内，从 $\text{F}$ 上至 $\text{E}$，这就意味着上面可能的音符的音调是升序排序的。为了使你的计算更加方便，我们将使用整数 $1$ 到 $12$ 来表示这十二个音符。

| 1 | 2 | 3 |4 | 5 | 6 |7 | 8 |9 |10 | 11 | 12 |
| ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |
| $\text{F}$ | $\text{F}^♯$ | $\text{G}$|$\text{G}^♯$ |$\text{A}$ | $\text{A}^♯$ |$\text{B}$| $\text{C}$ |$\text{C}^♯$ |$\text{D}$ | $\text{D}^♯$ |$\text{E}$ |

以上是所有定音鼓能调到的音调。

在演奏开始前，定音鼓手可以随意调整各个定音鼓到任意他们想要的音调。然而，在演奏时，他们可能需要在音符间隙快速地调整他们，这样他们才能在正确的时候演奏出正确的音符。这些鼓从 $1$ 到 $D$ 编号，在任意时刻，鼓 $i+1$ 的音调必须比鼓 $i$ 的音调高。鼓手必须在（当前时刻）不需要演奏时才能调整一个鼓的音高，并且鼓手一次只能调整一个鼓的音高（假设没有人帮他调节）。

因此，这并不是一件简单的事，定音鼓手想要让他们有尽可能多的时间调节。具体来说，他们想要最大化在演奏过程中的调整时间以便使他们可以在演奏中以最快速度做必要的音调调节。

inputFormat:
第一行两个整数 $N,D$，分别表示被弹奏的音符和鼓的数量。

接下来 $N$ 行每行两个整数 $T_i$ 和 $P_i$，表示第 $i$ 个音符演奏的时间和音调。

outputFormat: 输出一行包含一个实数，下取整至两位小数，表示最大的调整时间。输出 $0.00$ 表示没有必要重新调节。

hint:
> 【样例解释 1】

> 如果只有一个鼓，定音鼓手为了可以演奏下一个音符，必须在每个音符弹奏后重新调节。

> 如果有两个鼓，答案应该是 $10.00$，当留下高音鼓调到音调 $12$ 时达到这个答案。

> 【样例解释 2】

> 前六个音符里只有四个音调：$1$，$3$，$5$，$6$，类似的，最后六个音符里只有 $1$，$3$，$6$，$8$ 四个音调。

> 一个最佳策略是，预先调整四个鼓到 $1$，$3$，$5$，$6$，在第六个音符后，定音鼓手可以花 $4.50$ 秒调整最高音的鼓到音调 $8$，然后另外 $4.50$ 秒调整次高音鼓到音调 $6$，完成时刚好是时候去弹奏第七个音符。

> 【样例解释 3】

> 则是一个更为典型的定音鼓片段，只包含一个音符，因此不需要重新调节。

【数据范围】

对于 $60\%$ 的数据，$1\le N \le 50,1\le D\le 3$；

对于 $100\%$ 的数据，$1\le N \le 100,$ $1\le D\le 4,$ $0\le T_1<T_2<...<T_{N-1}<T_N\le 10^9,$ $1\le P_i \le 12(1\le i \le N)$。


title: [CCO2015] 挖掘

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

度假时间到了！你厌倦了 C shell（编程语言），所以你决定去收集贝壳（Seashell，与 C Shell 同音）。

你决定去游览 Cartesia 国的岛度假。该岛以拥有优美的方形沙滩而著名。该沙滩被划分成 $N\times N$ 的矩阵组成，你带上了你可靠的铲子，你可以用铲子在岛上挖最多 $K\times K$的正方形子矩阵。为了保证你的铲子是可靠的，你所挖的正方形子矩阵要保证所挖的 $K\times K$ 的范围都在沙滩上。

在岛下，有 $M$ 种未探索过的贝壳种类。具体来说，对于每个贝壳种类 $i$，有 $S_i$ 个贝壳在不同的位置。对于每个不同的种类的贝壳，你把它挖出来，然后带回家，然后以每个 $1$ 美元的价格卖给一个科学家。多个同种类的贝壳没有附加价值。

麻烦的是，一种华丽的渡渡鸟在沙滩上跑来跑去。在一个给定时刻，他可能会在一个网格里埋一个蛋，包括那些已经有蛋或者网格的网格。坏消息是，如果你铲子挖出来的 $K\times K$ 的子正方形矩阵里包含渡渡鸟的蛋，科学家会因为你正在危害濒危物种而非常着急，因此没人会给你钱。

想到这些，你决定坐下来，开始写程序，进行模拟挖掘。你将会去计算你的挖掘的可能性，当你在不同时间点以均等可能性选择一个挖掘方案时，需要保证至少一个收入值来偿还你的学生贷款。谁想白忙活一场呢？

inputFormat:
第一行包括两个整数 $N,K$，表示岛和铲子的尺寸

第二行一个数 $M$，表示贝壳种类数。接下来 $M$ 行每行表示一个种类 $i$，包含一个整数 $S_i$，接着 $2\times S_i$ 个数，为一些在 $(1,1)$ 与 $(N,M)$ 之间的坐标，表示 $S_i$ 个贝壳埋的位置。

接下来 $T$ 行每行表示一个时间点，按时间由最远到最近排序，每行为如下格式之一：
- $1$ $A_i$ $B_i$，表示渡渡鸟在 $(A_i,B_i)$ 下了一个蛋
- $2$ $V_i$，表示我们想计算一个在该时间点获利 $\geq V_i$ 的随机挖掘的可能性。注意贝壳和蛋在计算时都没有没有被真正地挖出来。

outputFormat: 对于每个询问，输出一行表示一次获得至少指定利润的随机挖掘的可能性。你的答案与标准答案之间的差值的绝对值不能大于 $10^{-4}$。

hint:
【样例解释】

初始时，贝壳的排布如下所示：

![CCO2015D2T3Pic1](http://miao.su/images/2018/08/16/aaa6d86f.png)

我们将用铲子挖至多 $2\times 2$ 的格子，因此我们有 $9$ 种可能的挖掘。
当没有蛋出现时，$8$ 种挖掘包含至少两种贝壳，$3$ 种挖掘包含三种贝壳。

一个蛋掉进了有贝壳 $1,2$ 的方格。

在这种情况下，$\frac{4}{9}$ 的挖掘包含至少两种贝壳且没有蛋，仅有一种挖掘会包含所有种类的贝壳并且没有蛋，那就是挖掘左下角。最终输出指明没有任何一种挖掘包含四种贝壳。

【数据范围】

对于至少 $15\%$ 的数据，$1\le N \le 40$；

对于另外 $25\%$ 的数据，所有的更新操作在询问操作前出现；

对于 $100\%$ 的数据，$1\le K \le N\le 2500,$ $0\le M \le 10^5,$ $1\le S_i\le 4,$ $0\le T\le 10000,$ $1\le A_i,B_i \le N,$ $1\le V_i\le 10^9$。


title: [NOI2019] 斗主地

background: 时限 4 秒 内存 512MB

description:
小 S 在和小 F 玩一个叫“斗地主”的游戏。

可怜的小 S 发现自己打牌并打不过小 F，所以他想要在洗牌环节动动手脚。

一副牌一共有 $n$ 张牌，从上到下依次标号为 $1 \sim n$。标号为 $i$ 的牌**分数**是 $f(i)$。在本题，$f(i)$ 有且仅有两种可能：$f(i) = i$ 或 $f(i) = i^2$。

洗牌的方式和我们日常生活中的比较类似，以下我们用形式化的语言来定义： 洗牌环节一共分 $m$ 轮，这 $m$ 轮洗牌依次进行。第 $i$ 轮洗牌时：

1. 小 S 会拿出从最上面往下数的前 $A_i$ 张牌。这样这副牌就被分成了两堆：第一堆 是最上面的 $A_i$ 张牌，第二堆是剩下的 $n-A_i$ 张牌，且这两堆牌内相对顺序不变。 特别地，当$A_i = n$ 或 $A_i = 0$ 时，有一堆牌是空的。
2. 接下来对两堆牌进行合并，从而产生新的第三堆牌。当第一堆牌还剩下 $X$ 张，第二堆牌还剩下 $Y$ 张的时候，以 $\dfrac{X}{X+Y}$ 的概率取出第一堆牌的最下面的牌，并将它 放入新的第三堆牌的最上面， $\dfrac{Y}{X+Y}$  的概率取出第二堆牌的最下面的牌，并将它放入新的第三堆牌的最上面
3. 重复操作 $2$，一直取到两堆牌都为空为止。这样我们就完成了一轮洗牌。

因为洗牌过程是随机的，所以小 S 发现自己没法知道某个位置上具体是哪张牌。但小 S 想问你在经历了这 $m$ 轮洗牌后，某个位置上的牌的**期望分数**是多少。小 S 一共会问你 $Q$ 个这样的问题。

inputFormat:
输入的第一行包含三个正整数 $n, m, type$，分别表示牌的数量，洗牌的轮数与 $f(i)$ 的类型。当 $type = 1$ 时，$f(i) = i$。当 $type = 2$ 时，$f(i) = i^2$。

接下来一行，一共 $m$ 个整数，表示 $A_1 \sim A_m$。

接下来一行一个正整数 $Q$，表示小 S 的询问个数。 接下来 $Q$ 行，每行一个正整数 $c_i$，表示小 S 想要知道从上往下第 $c_i$ 个位置上的牌的**期望分数**。

保证 $1 \leq c_i \leq n$。

outputFormat:
输出一共 $Q$ 行，每行一个整数，表示答案在模 $998244353$ 意义下的取值。

即设答案化为最简分式后的形式为 $\dfrac{a}
{b}$，其中 $a$ 和 $b$ 互质。输出整数 $x$ 使得 $bx \equiv a \pmod{998244353}$ 且 $0 ≤ x < 998244353$。可以证明这样的整数 $x$ 是唯一的。


title: [NOI2019] 弹跳

background:
原题时限 2s

内存 128MB

description:
跳蚤国有 $n$ 座城市，分别编号为 $1 - n$，$1$ 号城市为首都。所有城市分布在一个$w \times h$ 范围的网格上。每座城市都有一个整数坐标 $(x, y) (1 \leq x \leq w, 1 \leq y \leq h)$，不同城市的坐标不相同。

在跳蚤国中共有 $m$ 个弹跳装置，分别编号为 $1 - m$，其中 $i$ 号弹跳装置位于 $p_i$ 号城市，并具有参数 $t_i, L_i, R_i, D_i, U_i$。利用该弹跳装置，跳蚤可花费 $t_i (t_i > 0)$ 个单位时间，从 $p_i$ 号城市跳至坐标满足 $L_i \leq x \leq R_i, D_i \leq y \leq U_i (1 \leq L_i \leq R_i \leq w, 1 \leq D_i \leq U_i \leq h)$ 的任意一座城市。需要注意的是，一座城市中可能存在多个弹跳装置，也可能没有弹跳装置。

由于城市间距离较远，跳蚤们必须依靠弹跳装置出行。具体来说，一次出行将经过
若干座城市，依次经过的城市的编号可用序列 $a_0, a_1, \cdots , a_k$ 表示；在此次出行中，依次利用的弹跳装置的编号可用序列 $b_1, b_2, \cdots , b_k$ 表示。其中每座城市可在序列 $\{a_j\}$ 中出现任意次，每个弹跳装置也可在序列 $\{b_j\}$ 中出现任意次，且满足，对于每个 $j (1 \leq j \leq k)$，编号为 $b_j$ 的弹跳装置位于城市 $a_{j-1}$，且跳蚤能通过该弹跳装置跳至城市 $a_j$。我们称这是一次从城市 $a_0$ 到城市 $a_k$ 的出行，其进行了 $k$ 次弹跳，共花费 $\sum^k_{i=1} t_{b_{i}}$ 个单位时间。

现在跳蚤国王想知道，对于跳蚤国除首都（$1$ 号城市）外的每座城市，从首都出发，到达该城市最少需要花费的单位时间。跳蚤国王保证，对每座城市，均存在从首都到它的出行方案。

inputFormat:
第一行包含四个整数 $n, m,w, h$，变量的具体意义见题目描述。

接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i, y_i$，表示 $i$ 号城市的坐标。

接下来 $m$ 行，第 $i$ 行包含六个整数 $p_i, t_i, L_i, R_i, D_i, U_i$，分别表示 $i$ 号弹跳装置所在的城市编号、弹跳所需的时间、可到达的矩形范围。这些整数的具体意义见题目描述。

outputFormat: 输出 $n - 1$ 行，第 $i$ 行包含一个整数，表示从跳蚤国首都到 $i + 1$ 号城市最少需要花费的单位时间。


title: [NOI2019] I 君的探险

background:
附加文件可在页面底部「附件」中下载。

### 特别提示

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

1. 与原题不同的是，你不需要，也不应该在程序开头包含 `explore.h` 头文件。

2. 为了确保程序正常编译，你需要在你提交的程序开头加上如下函数声明语句：

```cpp
void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);
```

3. 本题仅支持 C++ 语言（包括 `C++`，`C++11`，`C++14`，`C++17`）提交。

description:
时隔半年，I 君的商店终于开不下去了，他决定转让商店，做一名探险家去探索未知的广阔世界。

根据古书记载，他在一个大荒漠的腹地找到了未知文明创造的地下宫殿，宫殿由 $N$ 个大型洞穴和 $M$ 条连接这些洞穴的双向通路构成。I 君能借助古书分辨所处的洞穴，但书中并没有记录 $M$ 条通路的连接结构，因此他难以搜寻传说中藏在宫殿里的无尽财宝。

不过现在 I 君发现了一个神秘机关，通过它可以获知宫殿的信息，I 君决定利用这个机关来得到宫殿的连接结构，请你来协助他。

地下宫殿可以抽象成一张 $N$ 个点、$M$ 条边的无向简单图（简单图满足任意两点之间至多存在一条直接相连的边），洞穴从 $0 \sim n - 1$ 编号。目前你并不知道边有哪些。

每个洞穴都拥有一个光源，光源有开启、关闭两种状态，只有当光源处于开启状态时它所在的洞穴才会被照亮。初始时所有的光源都处于关闭状态，而光源的状态只能用I 君发现的神秘机关改变。更具体的，使用神秘机关可以进行如下四种操作：

1. 向机关给定一个编号 $x$，机关将会改变$x$ 号洞穴，以及与$x$ 号洞穴有通路直接相连的洞穴的光源状态。即原来开启的光源将会关闭；原来关闭的光源将会开启。

2. 向机关给定一个编号 $x$，机关将会显示当前$x$ 号洞穴光源的状态。

3. 向机关给定两个编号 $x, y$，表示你确定有一条连接 $x$ 号洞穴与 $y$ 号洞穴的通路，并让机关记录。

4. 向机关给定一个编号 $x$，机关将会判断与 $x$ 号洞穴相连的通路是否都已被记录。

机关在完成上一次操作后才能进行下一次操作。机关不能随意使用，因此每种操作的使用次数都有限制，分别为 $L_m, L_q, M, L_c$。你的任务是，编写一个程序，帮助 I 君决定如何合理利用神秘机关，从而正确地找到这 $M$ 条通路。

### 实现细节

你不需要，也不应该实现主函数，你只需要实现函数 `explore(N, M)`，这里的 $N$和 $M$ 分别表示洞穴和通路的个数。你可以通过调用如下四个函数来和交互库进行交互：

1. `modify(x)`

- 这个函数可以令机关执行操作 $1$，给定的编号为 $x$。

- 你需要保证 $0 \leq x < N$，这个函数没有返回值。

2. `query(x)`

- 这个函数可以令机关执行操作 $2$，给定的编号为 $x$。

- 你需要保证 $0 \leq x < N$，这个函数返回 $0$ 或 $1$，表示目前 $x$ 号洞穴的光源为关闭（$0$ 表示）或开启（$1$ 表示）状态。

3. `report(x, y)`

- 这个函数可以令机关执行操作 $3$，给定的编号为 $x, y$。

- 你需要保证 $0 \leq x, y < N$ 且 $x \neq y$，这个函数没有返回值。

4. `check(x)`

- 这个函数可以令机关执行操作 $4$，给定的编号为 $x$。

- 你需要保证 $0 \leq x < N$，这个函数返回 $0$ 或 $1$，其中返回 $1$ 当且仅当与 $x$ 号洞穴相连的所有通路都已通过操作 3 被记录。

评测时，交互库会恰好调用 `explore` 一次。

本题保证所使用的图在交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。

数据保证在调用次数限制下，交互库运行所需的时间不超过1s；交互库使用的内存大小固定，且不超过128MB。

### 实现方法

选手工作目录下已经提供了一个 `template_explore.cpp/c/pas`，请将这个文件拷贝一份，重命名为 `explore.cpp/c/pas`，然后在其基础上答题。

1. 对 C++ / C 语言选手

- 请确保你的程序开头有
```
#include "explore.h"。
```
- 你需要实现的函数 `explore` 的接口信息如下：
```
void explore(int N, int M);
```
- 你可以调用的交互函数的接口如下：
```
void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);
```

2. 对 Pascal 语言选手

- 注意：Pascal 的代码中实现接口的语法较为复杂，请选手直接在下发的.
`template_explore.pas` 的基础上进行答题，而不是自己从头实现代码。

- 你需要实现的函数 `explore` 的接口信息如下：
```
procedure _explore(N, M : longint);
```
- 注意：这里的函数名称是`_explore` 而非`explore`，如果使用`explore` 将导致编译失败。

- 你可以调用的交互函数的接口如下：
```
procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;
```

试题目录下的 `grader.cpp/c` 以及 `graderhelperlib.pas` 是我们提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

1. 对 `C/C++` 语言的选手：

- 你需要在本题目录下使用如下命令编译得到可执行程序：

- 对于 C 语言：
```
gcc grader.c explore.c -o explore -O2 -lm
```
- 对于 C++ 语言：
```
g++ grader.cpp explore.cpp -o explore -O2 -lm
```

2. 对于 `Pascal` 语言的选手：

- 你需要在本题目录下使用如下命令编译得到可执行程序：
```
fpc grader.pas -o"explore" -O2
```

3. 对于编译得到的可执行程序：

- 可执行文件将从标准输入读入以下格式的数据：

第一行包含三个整数 $L_m, L_q, L_c$ ，第二行包含两个整数 $N, M$，意义如题面描述。

接下来 $M$ 行，每行两个整数 $x, y$，描述一条连接 $x$ 号洞穴与 $y$ 号洞穴的通路。

- 读入完成之后，交互库将调用恰好一次函数 `explore`，用输入的数据测试你的函数。你的函数正确返回后，交互库会判断你的计算是否正确，若正确则会输出 `Correct` 和交互函数调用次数相关信息，否则会输出相应的错误信息。

hint:
数据第一行的三个整数分别表示三种操作的调用次数限制，即 `modify(x)` 调用次数不能超过 $100$，`query(x)` 调用次数不能超过 $200$，`check(x)` 调用次数不能超过 $300$。

数据第二行的两个整数分别表示洞穴数和通路条数，即 $N = 3 , M = 2$。

`report(x, y)` 调用次数不能超过 $M$，该例子中即不超过 $2$ 次。

下面是一个正确的交互过程：

| 选手程序 | 交互库 | 说明 |
| :----------: | :----------: | :----------: |
|  | 调用 $\text{explore}(3,2)$ | 开始测试 |
| 调用 $\text{modify}(0)$ |  | 对 $0$ 号洞穴做操作 $1$ |
| 调用 $\text{query}(2)$ | 返回 $0$ | 目前 $2$ 号洞穴的光源状态是关闭 |
| 调用 $\text{report}(0,1)$ |  | 发现了道路 $(0,1)$ 并记录 |
| 调用 $\text{check}(0)$ | 返回 $1$ | 与 $0$ 号洞穴相关的道路都已被记录 |
| 调用 $\text{report}(2,1)$ |  | 发现了道路 $(2,1)$ 并记录 |
| 运行结束并返回 | 向屏幕打印 $\text{Correct}$ | 交互结束，结果正确 |

### 下发文件说明

在本试题目录下：

1. `grader.cpp/c` 以及 `graderhelperlib.pas` 是我们提供的交互库参考实现。

2. `explore.h` 和 `grader.pas` 是头文件，选手不用关心具体内容。

3. `template_explore.cpp/c/pas` 是我们提供的样例解题源代码。

4. `explore1.in`、`explore2.in`、`explore3.in` 是样例输入，可供测试。

选手注意对所有下发文件做好备份。评测只收取本试题目录下的`explore.c/cpp/pas`，并且对该程序以外的文件的修改无效。

最终评测只会收取 `explore.cpp/c/pas`，修改选手目录下其他文件对评测无效。

本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

在上述条件基础上，在一个测试点中，你得到满分，当且仅当：

1. 你的每次函数调用均合法，且调用 `modify`、`query` 和 `check` 的次数分别不超过$L_m, L_q, L_c$。

2. 由于 `report` 的调用次数限制为 $M$，你的每次调用都必须记录一条新的且存在的边；即每次调用 `report(x, y)` 时，应满足：有一条连接 $x$ 号洞穴和 $y$ 号洞穴的通路，且在这次调用之前从未调用过 `report(x, y)` 或 `report(y, x)`。

3. 你实现的函数 `explore` 正常返回。

4. 在 `explore` 函数返回时，你已经通过调用 `report` 记录了全部 $M$ 条通路。

本题共 $25$ 个测试点，每个测试点 $4$ 分。每个测试点的数据规模和相关限制见下表。
| 测试点编号 | $N=$ | $M=$ | $L_m=$ | $L_q=$ | $L_c=$ | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $3$ | $2$ | $100$ | $100$ | $100$ | 无 |
| $2$ | $100$ | $10\times N$ | $200$ | $10^4$ | $2\times M$ | 无 |
| $3$ | $200$ | $10\times N$ | $200$ | $4\times 10^4$ | $2\times M$ | 无 |
| $4$ | $300$ | $10\times N$ |$299$  | $9\times 10^4$ | $2\times M$ | 无 |
| $5$ | $500$ | $10\times N$ | $499$ | $1.5\times 10^5$ | $2\times M$ | 无 |
| $6$ | $59998$ | $\frac{N}{2}$ | $17\times N$ | $17\times N$ | $0$ | $A$ |
| $7$ | $99998$ | $\frac{N}{2}$ | $18\times N$ | $18\times N$ | $0$ | $A$ |
| $8$ | $199998$ | $\frac{N}{2}$ | $19\times N$ | $19\times N$ | $0$ | $A$ |
| $9$ | $199998$ | $\frac{N}{2}$ | $19\times N$ | $19\times N$ | $0$ | $A$ |
| $10$ | $99997$ | $N-1$ | $18\times N$ | $18\times N$ | $0$ | $B$ |
| $11$ | $199997$ | $N-1$ | $19\times N$ | $19\times N$ | $0$ | $B$ |
| $12$ | $99996$ | $N-1$ | $10^7$ | $10^7$ | $2\times M$ | $C$ |
| $13$ | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2\times M$ | $C$ |
| $14$ | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2\times M$ | $C$ |
| $15$ | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2\times M$ | $D$ |
| $16$ | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2\times M$ | $D$ |
| $17$ | $199995$ | $N-1$ | $10^7$ | $10^7$ | $2\times M$ | $D$ |
| $18$ | $1004$ | $2\times 10^3$ | $10^7$ | $5\times 10^4$ | $2\times M$ | 无 |
| $19$ | $1004$ | $3\times 10^3$ | $10^7$ | $5\times 10^4$ | $2\times M$ | 无 |
| $20$ | $1004$ | $3\times 10^3$ | $10^7$ | $5\times 10^4$ | $2\times M$ | 无 |
| $21$ | $5\times 10^4$ | $2\times N$ | $10^7$ | $10^7$ | $2\times M$ |  无|
| $22$ | $10^5$ | $2\times N$ | $10^7$ | $10^7$ | $2\times M$ | 无 |
| $23$ | $1.5\times 10^5$ | $2\times 10^5$ | $10^7$ | $10^7$ | $2\times M$ | 无 |
| $24$ | $2\times 10^5$ | $2.5\times 10^5$ | $10^7$ | $10^7$ | $2\times M$ | 无 |
| $25$ | $2\times 10^5$ | $3\times 10^5$ | $10^7$ | $10^7$ | $2\times M$ | 无 |

再次提醒，题目保证测试所使用的图在交互开始之前已经完全确定，而不会根据和你的程序的交互动态构造。

表中特殊性质栏中变量的含义如下：

A：保证每个点的度数恰好为 $1$。

B：保证对于每个 $x > 0$，存在恰好一个 $y < x$ 的 $y$ 使得 $x$ 号洞穴与 $y$ 号洞穴有通路直接相连。

C：存在 $0 \sim N - 1$ 的一个排列 $p_0, p_1, \cdots , p_{N-1}$，使得对任意 $1 \leq i < N$，存在一条连接洞穴编号分别为 $p_{i-1}$ 与 $p_i$ 的通路。

D：保证图连通。

- 提示：你的程序可以通过判断传入的 $N$ 的个位来区分上述不同的数据类型。


title: 旅行

background:
> 光阴似箭。如烟火，只许刹那芳华；似九月，夜幕昙花一闪而散。
> 辉煌已逝。步征夫，辗转行路之洼；立孤叶，夙夜漂泊四海之旅。
——《旅行》

description:
行走与尘世之间，charine 是一位旅行家。踏入城市的喧嚣，他开始了辗转于城市的旅行……

这是一个具有 $n$ 个城市的城市群，每两个点可以互相到达。现代交通技术飞速发展，大大缩短了航程，距离已显得不在那么重要：

城市群里，道路已经没有长长短短之说，**每一条道路由于时间的不断缩短都可视为等长**，把它们以一个单位计量，可以容易的视其为 $1$ zm。

正是由于城市群的庞大，未脱离于城市的 charine 亦有牵绊，这使他不可能无限遨游于这宽广的城市群里。这使 charine 极为郁闷，他决定选择尽可能短的时间走遍整个城市群。

具体而言，charine 不会因为在某个城市里而耽误他遨游天下的决心，他走访的每一个城市，都会在极短的时间里将其印在脑海里。

charine 的行走速度不会很快，这意味着他只能在一个单位时间内行走 $1$ zm。

这却使他更着急着找到足够旅行更多城市的方法……

为了去除他在每一个岔路口的犹豫时间，charine 亦是聪明的提前了他的旅行计划。对于走出城市 $i$ 的那几个路口，charine 给这个城市定义了一个通路 $a_i$，他相信自己的计划，就一定会踩着通路向前走。**走访完城市 $i$ 的他会给自己的下一个城市目标定为 $a_i$**。

处理完这些以后，他便是再也找不出继续缩短时间的办法了，于是他开始执行了自己的旅行计划。

charine 有 $m$ 个季度都有出行的机会，对于第 $i$ 个季度，charine 将会从 $S_i$ 出发，他告诉你，他会准备 $t$ 单位时间去旅行。

为了能及时的看到他的身影，你要知道，**$t$ 单位时间后 charine 会出现在哪个城市……**

**注意“道路”与“通路”的定义问题。**

inputFormat:
输入数据的第一行为一个正整数 $n$，表示城市数。

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

接下来一个整数 $m$，表示 $m$ 个季度。

第 $4$ 到 $m+3$ 行，描述一次旅行，每行 $3$ 个整数，$S_i,t_1,t_2$，描述见题面，其中，$t=t_1^{t_2}$。

outputFormat: 对于每个季度输出一行，表示答案。


title: 封锁

background: Steve 带领队伍准备去 M 星消灭黑暗势力，即将降落时被 M 星上空的无人机拦截了。

description:
为了突破封锁，成功降落， Steve 使用了电磁干扰仪，使无人机开始自相残杀。

然而，情况很快就变得混乱，无法了解当前的情况。

幸好 Steve 的部队已经记录了开始混战前的状况，并设法获得了无人机执行操作的顺序。

每架无人机有 $5$ 项属性 $atk,def,mat,mdf,fix$ ，当前生命值 $hp$ ，当前坐标 $(x,y,z)$ ，当前水平朝向 $f$( 范围 0-7) 和竖直朝向 $h$( 范围 0-4) 。

每一时刻，所有存活的无人机会**先**向正前方移动一格。

随后，存活的无人机会**按编号从小到大**依次执行下列操作之一：

无操作 (N)

上下转向 (U/D) ：改变 $h$ 的值，上为增加，下为减少，如果超过了范围就是无效操作，忽略。

左右转向 (L/R) ：改变 $f$ 的值，左为增加，右为减少，循环（分别对应从上面看的逆时针，顺时针）。

例如：当 $h=4$ 时操作 U 无效，当 $f=0$ 时操作 R 会使
 $f$ 变为 $7$ 。

修复 (F) ：使 $hp$ 增加 $fix$ 点。

子弹 (A) ：使位于这架无人机正前方**最近**的飞机受到伤害，伤害的值为当前飞机的 $atk$ 值与目标的 $def$ 值之差（差为负则不会造成伤害），**如果多架飞机处于同一位置，那么只有编号最小的飞机会受到伤害**。

激光 (M) ：使位于这架无人机正前方的**所有**飞机受到伤害，伤害的值为当前飞机的 $mat$ 值与目标的 $mdf$ 值之差（差为负则不会造成伤害）。

注意：与开火飞机重叠的飞机不会受到伤害

如果受到伤害后， $hp\leq 0$ ，那么这架飞机就会坠毁。

对于 $f$ 和 $h$ ，它的“正前方”是这样定义的：

首先，根据 $f$ 确定 $x,y$ 方向，如下图。

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

随后，根据 $h$ 进一步确定方向。

对于 $h=0$ 或 $h=4$ ，正前方是正下或正上（ $x,y$ 不变， $z$ 变化）。

对于 $h=1$ 或 $h=3$ ，在上面方向的基础上再向下/上移动一格。

对于 $h=2$ ，正前方为水平方向（ $x,y$ 如上所述， $z$ 不变）。

（有人反馈看不懂方向，这里直接给出 $f,h$ 和正前方
 $(x,y,z)$ 的对应表）

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

现在， Steve 告诉你了所有飞机初始的状态和之后执行的操作。

你需要告诉他，经过 $t$ 个时刻的混战之后，每架飞机的位置和生命值。

inputFormat:
第一行两个整数 $n,t$ ，表示飞机数和时刻数。

接下来 $n$ 行，每行 $11$ 个整数和一个长为 $t$ 字符串，按编号顺序描述无人机。

这 $11$ 个整数分别为 $x,y,z,h,f,atk,def,mat,mdf,hp,fix$ ，其中 $hp$ 为初始生命值。

字符串的每一个字符均为大写字母，依次表示这 $t$ 个时刻的操作。

outputFormat:
$n$ 行，每行 $4$ 个整数 $x,y,z,hp$ 。

如果这架飞机没有坠毁，则输出坐标和最终的生命值。

否则，输出坠毁前的坐标， $hp$ 输出 $0$ 。

hint:
两架飞机移动并改变朝向后互相面对，随后它们分别向对面疯狂开火，最终 1 号飞机率先击落 2 号飞机，因为 2 号飞机已经坠毁，所以 1 号飞机不会被击落。

而它们身后分别跟着两架飞机， 2 号飞机使用激光，所以 3 号飞机也会受到伤害， 1 号飞机使用子弹，所以 4 号飞机不会受到伤害，直到 2 号飞机坠毁后， 1 号飞机发出最后一颗子弹，对 4 号飞机造成了一点伤害。同时两架飞机前三次操作分别进行了三次修复， $hp$ 增加了 $3$ 。

测试时，每个 Subtask 包括 3 个测试点，全部通过才能得到该 Subtask 的分数

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

样例 2 解释：<https://www.luogu.com.cn/discuss/582252>

---

数据范围：

$1\leq n,t\leq 100$

输入的所有数字大小在合理范围内，且绝对值均不大于 $100$ 。

其中 $atk,def,mat,mdf,fix$ 为非负整数。

$hp$ 为正整数。

$x,y,z$ 为整数。

$h$ 为 $0,1,2,3,4$ 中的一个。

$f$ 为 $0,1,2,3,4,5,6,7$ 中的一个。

字符串仅包含 $NFLRUDAM$ $8$ 种字符。

另外，对于前 3 个 subtask ，保证任何时刻飞机的 z 坐标为
 $0$ 。

Subtask | 分值 | 出现的操作
:-: | :-: | :-:
1| 12| N
2| 14| NF
3| 15| NFLR
4| 17| NFLRUD
5| 19| NFLRUDM
6| 23| NFLRUDMA


title: 机关

background: Steve成功降落后，在M星上发现了一扇大门，但是这扇大门是锁着的

description:
这扇门上有一个机关，上面一共有12个旋钮，每个旋钮有4个状态，将旋钮的状态用数字$1$到$4$表示

每个旋钮只能向一个方向旋转（状态：1->2->3->4->1），在旋转时，会引起另一个旋钮也旋转一次（方向相同，不会引起连锁反应），同一旋钮在不同状态下，可能会引起不同的旋钮旋转（在输入中给出）

当所有旋钮都旋转到状态1时，机关就打开了

由于旋钮年久失修，旋转一次很困难，而且时间很紧迫，因此Steve希望用最少的旋转次数打开机关

这个任务就交给你了

inputFormat:
$12$行，每行$5$个整数，描述机关的状态

第$i$行第一个整数$s_i$表示第$i$个旋钮的初始状态是$s_i$

接下来$4$个整数$a_{i,j},j=1,2,3,4$表示这个旋钮在状态$j$时旋转，会引起第$a_{i,j}$个旋钮旋转到下一个状态

outputFormat:
第一行一个整数$n$，表示最少的步数

第二行$n$个整数，表示依次旋转的旋钮编号

数据保证有解


title: 寻宝

background: Steve成功打开了机关，发现机关后是一个巨大的迷宫

description:
这个迷宫一共有$n$个洞穴，洞穴之间有很多单向隧道，很难数清

但经过分析，发现：

这些隧道可以分为$m$组，对于每一组，编号在区间$[s_l,s_r]$内的每一个洞穴，与编号在区间$[t_l,t_r]$内的每一个洞穴之间，都有一条隧道，每组内共有$(s_r-s_l+1)\cdot (t_r-t_l+1)$条隧道，通过同组内每一条隧道的时间都相等

为了进一步节约时间，Steve可以挖掘新的隧道

但是，每个洞穴的性质不同，导致挖掘隧道的难度不同，有些洞穴甚至无法挖掘隧道

具体来说，第$i$个洞穴有一个值$v_i$，$v_i=0$表示无法挖掘隧道，对于其它值，表示从第$i$个洞穴开始，挖掘一条到第$j$个洞穴的隧道，并到达第$j$个隧道，需要花费$|i-j|*v_i$时间

Steve希望在最短时间内到达第$n$个洞穴，决定不限制挖掘隧道的数量

现在，你需要告诉Steve最少需要用的时间

如果可能，你应帮助Steve求出一种最优方案

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

接下来一行$n$个整数$v_1,v_2,...,v_n$

接下来$m$行，每行描述一组隧道

每行$5$个整数$s_l,s_r,t_l,t_r,w$，其中$w$表示通过时间

outputFormat:
如果无解，则只需输出一行一个整数"-1"(不含引号)

如果有解，则按下列格式输出：

第一行一个整数$t$，表示最少花费的时间

如果你无法给出方案，在第二行输出一个整数$0$

如果你可以给出方案，在第二行输出一个整数$c$，在第三行输出$c$个整数，依次表示一种最优方案经过的洞穴编号

你并不需要告诉Steve经过的隧道是否为挖掘出来的，或者属于哪一组

hint:
样例1：1号到2号走第一组隧道，2号到6号挖掘隧道，用时$1*(6-2)=4$

样例2：1号到3号走第一组隧道，3号到4号挖掘隧道，用时$2*(4-3)=2$，4号到6号走第二组隧道

每个Subtask包括两个测试点，取较低分

对于每个测试点：

如果输出格式错误，那么，该测试点得0分

如果你没有给出正确的用时，那么，该测试点得0分

如果你给出正确的用时，但没有给出方案，那么你可以得到该测试点一半的分数（每个测试点得分向下取整）

如果你给出了错误方案，那么你可能可以得到该测试点一半的分数，或者得0分

如果你给出了正确的方案，那么你可以得到该测试点全部的分数

上面两个输出都可以得到满分，还有一种方案是$1 2 4 6$

如果你输出：

```
9
0
```
那么你可以得到该测试点一半的分数

数据范围：

$1\le w,v_i \le 10^9$

Subtask | 分值| n | m| 特殊性质
:-: | :-: | :-: | :-: | :-:
1 | 5| 100| 100| |
2| 10| 3000| 3000| |
3| 11| 50000| 50000| 2,3|
4| 10| 50000| 50000| 1|
5| 12| 50000| 0| |
6| 12| 50000| 1| |
7| 13| 50000| 20|3 |
8| 13| 50000| 20| |
9| 14| 50000| 50000| |

特殊性质1：所有$v_i=0$

特殊性质2：所有$v_i \in \{0,k\}$，$k$为常数

特殊性质3：所有$s_l=s_r,t_l=t_r$

保证存在到达$n$号洞穴的方案

关于输出错误方案：

如果输出的$2\leq c\leq n$，经过的点以$1$开头，以$n$结尾，且中间的点都是在$(1,n)$的整数，则这组解可能是一组最优解，可以得到一半分数

否则，得0分

~~不用担心spj会TLE/MLE~~


title: [LnOI2019] 真正的 OIer 从不女装

background:
题目提供者：朝田诗乃

众所周知，女装只有零次和无数次。

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

有如下定义：若一个序列中所有数字都一样，那么这个序列被称作“诗乃序列”。

对于每次询问，给定 $l$ 和 $r$，求序列 $a$ 中**左右端点都在 $[l,r]$ 中**的最长“诗乃序列”长度。

这题难倒了 Abbi。Abbi 决定女装。当 Abbi 女装时，序列会出现神奇的变化：它可以**在询问的区间 $[l,r]$ 中**挑一个它喜欢的位置 $p$，将区间 $[l,p]$ 和 $(p,r]$ **分别**翻转。

Abbi 想知道，**最多**进行 $k$ 次女装后（可选择进行不足 $k$ 次或不进行女装），能得到的最长的“诗乃序列”的长度是多少？

inputFormat:
第一行，$n$、$m$，表示序列长度和操作个数。

第二行，$n$ 个数，第$i$个数表示序列初始值 $a_i$。

接下来 $m$ 行，每行描述一个操作，格式如下：

1. $R$ $l$ $r$ $x$：表示将区间 $[l,r]$ 上的数字全部变成 $x$。
2. $Q$ $l$ $r$ $k$：表示询问在 $[l,r]$ 中进行最多 $k$ 次女装所能得到的最长“诗乃序列”长度。

**注意：询问独立，即每次询问后会将序列复原，不实际执行反转操作。**

outputFormat: 对于每个 Q 操作，输出询问答案。

hint:
**时空限制**：1s/512MB。

**数据范围：**

- 对于 $20\%$ 的数据，$1 ≤ n,m ≤ 100$。
- 对于另外 $10\%$ 数据，所有询问的 $k=0$。
- 对于另外 $10\%$ 数据，没有 R 操作。
- 对于 $100\%$ 的数据，$1≤n,m≤200000$，$0≤k≤1000$，$1≤a_i,x≤10^9$，$1≤l≤r≤n$。

特殊限制：对于后 $80\%$ 的数据，保证能卡飞 ODT。

**样例解释：**

对于第一次询问，询问的区间为：

```
3 3 3 3 2 3
```

女装 $1$ 次，将区间 $[1,4]$ 和 $[5,6]$ 分别翻转，得到：

```
3 3 3 3 3 2
```

此时可得到最长“诗乃序列”，长度为 $5$。可以证明没有别的女装方法能得到更长的“诗乃序列”。

此后询问以此类推。

**建议使用读入优化。**


title: 派遣

background: Steve在洞穴里发现了一张地图，上面标识出了黑暗势力的据点，他决定派遣一些士兵前去

description:
然而，这些士兵不一定具有与黑暗势力作战的能力，因而最终被派遣的士兵是未知的

为了尽量了解派遣的士兵的情况，Steve需要你帮忙计算一些值

Steve一共有$t$支军队，每支军队的人数都不同

每支军队可以按一定标准排成$n \times k$的方阵，每个士兵的位置可以用坐标$(x,y)$表示，其中$0\le x < n,0 \le y <k$，这个士兵的编号就是$x\cdot k+y$

位于$(0,0)$位置的士兵是队长，无论任何情况都会被派遣

对于其余的士兵，可以派遣，也可以不派遣

一支$n \times k$的军队的能力值是这样定义的：

如果所有士兵都被派遣，那么能力值是$1$

如果位于$(x,y)$位置的士兵(编号为$i$)未被派遣，那么能力值变为原来的$\frac{x}{i-x}$

例如，对于一支$2\times 2$的军队，如果$(1,1)$位置的士兵(编号为$3$)未被派遣，其他士兵都被派遣，那么能力值为$\frac{1}{3-1}=\frac{1}{2}$

如果$(1,1)$位置的士兵(编号为$3$)和$(0,1)$位置的士兵(编号为$1$)都未被派遣，那么能力值为$\frac{1}{3-1} \times \frac{0}{1-0} = 0$

如果$(1,1)$位置的士兵(编号为$3$)和$(1,0)$位置的士兵(编号为$2$)都未被派遣，那么能力值为$\frac{1}{3-1} \times \frac{1}{2-1} = \frac{1}{2}$

现在，Steve需要你为每一支军队，计算出所有可能派遣方案的能力值之和

为了避免出现分数，输出结果是模$1145141$意义下的值

如果这个值不存在，那么输出$-1$

也就是，如果你的答案为既约分数$\frac{p}{q}$，你需要找到一个最小的非负整数$a$，满足$p\equiv q\cdot a(mod 1145141)$，并输出这个值，如果不存在这样的整数，就输出$-1$

提示：$1145141$是质数

inputFormat:
第一行一个整数$t$

接下来$t$行，每行两个整数$n,k$

outputFormat: $t$行，每行一个整数表示答案


title: 水晶

background:
2019/12/27 修改最后一个点的数据范围

Steve带领军队到达了黑暗势力的据点

然而，他发现黑暗势力正在使用水晶保护自己

为了突破防御，Steve开始用武器攻击水晶

description:
黑暗势力的水晶已经排成了一排，而且数量很多

水晶可分为$n$组，第$i$组内有$a_i$个水晶，并且防御力均为$na_i$

Steve的武器也已经排成了一排，而且数量也很多

武器也可分为$n$组，第$i$组内有$b_i$个武器，并且攻击力均为$nb_i$

每一轮攻击中，黑暗势力会选择一个水晶，Steve会选择一个武器

如果这个武器的攻击力大于水晶的防御力，这次攻击就有效

然而，水晶和武器数量太多了，Steve很难知道具体选择了哪个水晶，哪个武器

现在Steve希望知道：

1.对于所有可能的情况，有多少种选法是一次有效的攻击

2.如果已经知道选用水晶的防御力在第$x$组水晶的防御力和第$y$组水晶的防御力之间，且选用武器的攻击力在第$z$组武器的攻击力和第$u$组武器的攻击力之间，那么，有多少种选法是一次有效的攻击

也就是，选择的水晶防御力不小于第$x$组水晶和第$y$组水晶防御力的较小值，不大于两者的较大值，武器同理

两个选法不同，当且仅当选用的水晶或武器不同（可以在同一组）

由于战事紧迫，你需要迅速回答问题才能让Steve作出下一轮攻击的决策

因此，部分测试点强制在线

为了避免答案过大，答案对$998244353$取模

inputFormat:
由于输入输出规模较大，使用下面的模板完成数据生成，具体格式请看模板和样例

评测时，所有测试点都只会输入5个数，输出1个数，因此你不需要输入输出优化

为便于调试，该模板可以手动指定数据，并输出每一个询问的答案，只需要输入的$k=0$

对于所有测试点，保证调用交互库消耗的时间不超过300ms
```
#include<cstdio>
using namespace std;
#define u32 unsigned int
#define u64 unsigned long long
int cl;
const int N=2500007;
const long long M=998244353LL;
int n,q,k;
int a[N],na[N],b[N],nb[N];
int x,y,z,u;
namespace lib{
    u64 read(){
        u64 n=0;
        char c=getchar();
        while(c<'0'||c>'9')c=getchar();
        while(c>='0'&&c<='9'){
            n=n*10+c-'0';
            c=getchar();
        }
        return n;
    }
    char r[30];
    void write(u64 num){
        if(num==0){
            putchar('0');
            return;
        }
        int t=0;
        while(num){
            r[t++]=num%10+'0';
            num/=10;
        }
        while(t)putchar(r[--t]);
    }
    u64 s;
    u64 rand(u64 l,u64 r){
        s=s*19260817+1;
        return ((s>>8)%(r-l+1)+l);
    }
    int ra,t;
    void init(){
        n=read();k=read();
        if(k<2){
            for(int i=1;i<=n;i++){
                a[i]=read();na[i]=read();
            }
            for(int i=1;i<=n;i++){
                b[i]=read();nb[i]=read();
            }
        }else{
            s=read();ra=read();
            u64 bacs=s;
            for(int i=1;i<=n;i++){
            	s=s*19260817+1;
        		a[i]=((s>>8)%ra+1);
                //a[i]=rand(1,ra);
                s=s*19260817+1;
        		//na[i]=((s>>8)%(M-1)+1);
                //na[i]=rand(1,M-1);
            }
            s=bacs;
            for(int i=1;i<=n;i++){
            	s=s*19260817+1;
        		//a[i]=((s>>8)%ra+1);
                //a[i]=rand(1,ra);
                s=s*19260817+1;
        		na[i]=((s>>8)%(M-1)+1);
                //na[i]=rand(1,M-1);
            }
            bacs=s;
            for(int i=1;i<=n;i++){
                s=s*19260817+1;
        		b[i]=((s>>8)%ra+1);
                //a[i]=rand(1,ra);
                s=s*19260817+1;
        		//nb[i]=((s>>8)%(M-1)+1);
            }
            s=bacs;
            for(int i=1;i<=n;i++){
                s=s*19260817+1;
        		//b[i]=((s>>8)%ra+1);
                //a[i]=rand(1,ra);
                s=s*19260817+1;
        		nb[i]=((s>>8)%(M-1)+1);
            }
        }
        q=read();
    }
    u64 lastans;
    u64 res;
    void reply(u64 num){
        if(k<2){
            write(num);putchar('\n');
        }else{
            res=res*233+num;
        }
        lastans^=num;
    }
    void query(){
        if(k<2){
            x=read();y=read();z=read();u=read();
        }else{
        	s=s*19260817+1;
        	x=((s>>8)%n+1);
        	s=s*19260817+1;
        	y=((s>>8)%n+1);
        	s=s*19260817+1;
        	z=((s>>8)%n+1);
        	s=s*19260817+1;
        	u=((s>>8)%n+1);
            //x=rand(1,n);y=rand(1,n);z=rand(1,n);u=rand(1,n);
        }
        if(k&1){
        	int t=lastans%n+1;
        	if((x+=t)>n)x-=n;
        	if((y+=t)>n)y-=n;
        	if((z+=t)>n)z-=n;
        	if((u+=t)>n)u-=n;
            /*x=(x+lastans)%n+1;
            y=(y+lastans)%n+1;
            z=(z+lastans)%n+1;
            u=(u+lastans)%n+1;*/
        }
    }
    void stop(){
        if(k>=2){write(res);putchar('\n');}
    }
}
int main(){
	lib::init();
	//现在你可以使用生成的a,na,b,nb

    //回答第一问

	lib::reply(233);

	for(int i=1;i<=q;i++){
		lib::query();

		//回答第二问

		lib::reply(233);
	}
	lib::stop();
}
```

outputFormat:
如果$k=0$，则会分别输出每一问的答案

否则，只会输出一个整数用于检查结果是否正确

hint:
样例1解释：

当选择第二组武器时，一定能进行一次有效攻击

当选择第一组武器时，只有选择第一组水晶才能进行一次有效攻击

因而，不难求出每一问的答案

建议根据样例进一步理解题意

样例5与样例6一致

数据范围：

对于所有数据，满足$1\le x,y,z,u \le n$，$1\le a_i,b_i\le 10^9$，$1\le na_i,nb_i\le 998244352$

如未特别说明，$k=3$，即：由模板生成数据，强制在线

如果$k=2$，那么这组数据仍由生成器生成，但不强制在线，也就是你可以在不回答询问的情况下得到下一个询问的真实值，随后按顺序回答即可

测试点| 分值| n | q| 特殊性质
:-: | :-: | :-: | :-: | :-:
1| 4| 100| 100| $k=2$|
2| 14| 3000| 3000| $k=2$|
3| 11| 100000| 100000| $a_i,b_i\le 100$|
4| 10| 15| 4000000| |
5| 12| 100| 4000000| |
6| 14| 5000| 4000000| |
7| 16| 100000| 100000| |
8| 19| 2500000| 4000000| |


title: 决战

background: Steve 成功突破了水晶防御，即将和黑暗势力进行决战。

description:
然而黑暗势力具有改变地形的能力，给军队的前进造成了很大困难

为了使军队更快前进，Steve 将核武器带到了前线，用来破坏地形

另外，Steve 很关心当前的地形情况

具体地说，前线的地形可分为 $n$ 段，初始高度为 $0$，决战时会发生 $m$ 个事件，事件可以是：

1. Steve 询问区间 $[l,r]$ 内，有几段小于给定的高度 $h$。
2. Steve 使用核武器，使得区间 $[l,r]$ 内高度大于 $h$ 的段的高度减少到 $h$。
3. 黑暗势力改变地形，使得区间 $[l,r]$ 内高度小于 $h$ 的段的高度增加到 $h$。

由于战事非常紧迫，所以部分测试点强制在线。

对于 $k=1$ 的测试点，设上次事件 1 的答案为 $lastans$，你需要将 $l,r,h$ 分别与 $lastans$ 取异或后得到实际数值，如果还没有回答过事件 1，那么 $lastans=0$。

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

接下来 $m$ 行，每行 $4$ 个整数，描述一个事件。

第一个整数 $opt$ 表示事件种类，接下来 $3$ 个整数 $l,r,h$，含义如题所述。

**数据中存在 $l>r$ 的情况，此时请直接忽略这次操作。**

outputFormat: 对于每个事件 1，输出一行一个整数，表示询问的答案。


title: [LnOI2019] Abbi并不想研学

background: 题目提供者：XuKaFy

description:
【原版题目】

给定一颗$n$个节点的树，树的叶节点全部是数字，非叶节点全部是符号`+`或者`*`。

请先对该树进行树链剖分。注意：若出现子树大小相同的情况，请选择编号较小的子节点作为重儿子。

一个节点的权值这样计算：若该节点为叶节点，数值即为节点数值；若该节点非叶节点，则该点的权值为【【【该点的【所有不在该点所在重链上】的子节点】所在重链的所有节点权值】相`+`或者相`*`的结果（操作取决于该节点的符号）】。

另一种表示方式是：设某一节点$i$的儿子集合为$D_{i}$，节点$i$的父亲为$F_{i}$，节点$i$的所在重链节点集合为$P_{i}$。

我们设：
$$Charge_{i}=\cup_{k\in D_{i},\ k\not\in P_{i}}P_{k}$$

令$C_{i}$为这个节点的符号，这个节点的权值就是：
$$
V_{i}=
\begin{cases}
\sum_{j\in Charge_{i}}V_{j} &C_{i}=`+'\\
\prod_{j\in Charge_{i}}V_{j} &C_{i}=`\times'
\end{cases}
$$

数据不保证每一个非叶节点都有至少一个非链上儿子，若没有合法的儿子则忽略该节点。

你需要支持这三种操作：

- $1$.改变某一叶节点的数值；

- $2$.改变某一非叶节点的符号为`+`或者`*`；

- $3$.查询某一节点所在重链所有节点权值相`+`与相`*`的值。

为防止溢出，请将所有权值$mod\ 99991$。

inputFormat:
第一行输入两个数$n$与$m$表示学生数量与要求数量。

接下来输入$1$行，$n-1$个数，表示第$i+1$个节点的父亲为$a$。

接下来一行$n$个数，分别为每个节点的信息：若该节点为叶节点，则是一个数字表示$V_{i}$，否则为一个数，`0`表示`+`，`1`表示`*`。

接下来输入$m$行，每行一个数字$c$与编号$k$，表示要求类型为$c$，操作的节点编号为$k$。若$c=1$，那么再输入一个数$V_{i}$表示新的权值。

outputFormat: 对于每一个$3$操作，请输出一行，该行包括两个数$a$、$b$，分别表示将本节点所在重链的所有节点权值相加**与**相乘的结果。


title: [BJOI2015] 骑士的旅行

background:
在一片古老的土地上，有一个繁荣的文明。

这片大地几乎被森林覆盖，有N座城坐落其中。巧合的是，这N座城由恰好N-1条双向道路连接起来，使得任意两座城都是连通的。也就是说，这些城形成了树的结构，任意两座城之间有且仅有一条简单路径。

在这个文明中，骑士是尤其受到尊崇的职业。任何一名骑士，都是其家族乃至家乡的荣耀。Henry从小就渴望成为一名能守护家乡、驱逐敌人的骑士。勤奋训练许多年后，Henry终于满18岁了。他决定离开家乡，向那些成名已久的骑士们发起挑战！

description:
根据Henry的调查，大陆上一共有 $M$ 名受封骑士，不妨编号为 $1$ 到 $M$。第 $i$ 个骑士居住在城 $P_i$，武力值为 $F_i$。

Henry计划进行若干次旅行，每次从某座城出发沿着唯一的简单路径前往另一座城，同时会挑战路线上武力值最高的 $K$ 个骑士（Henry的体力有限，为了提高水平，当然要挑战最强的骑士）。如果路线上的骑士不足 $K$ 人，Henry会挑战遇到的所有人。

每次旅行前，可能会有某些骑士的武力值或定居地发生变化，Henry自然会打听消息，并对计划做出调整。

为了在每次旅行时做好充分准备，Henry希望你能帮忙在每次旅行前计算出这条路线上他将挑战哪些对手。

inputFormat:
第一行，一个整数 $N$ ，表示有 $N$ 座城，编号为 $1 \sim N$。

接下来 $N-1$ 行，每行两个整数 $u_i$ 和 $v_i$，表示城 $u_i$ 和城 $v_i$ 之间有一条道路相连。

第 $N+1$ 行，一个整数 $M$，表示有 $M$ 个骑士。

接下来M行，每行两个整数 $F_i$ 和 $P_i$ 。按顺序依次表示编号为 $1 \sim M$ 的每名骑士的武力值和居住地。

第 $N+M+2$ 行，两个整数 $Q,~K$，分别表示操作次数和每次旅行挑战的骑士数目上限。

接下来 $Q$ 行，每行三个整数 $T_i,~X_i,~Y_i$ 。$T_i$ 取值范围为 $\{1,~2,~3\}$，表示操作类型。

一共有以下三种类型的操作：

$T_i=1$ 时表示一次旅行，Henry将从城 $X_i$ 出发前往城市 $Y_i$；

$T_i=2$ 时表示编号为 $X_i$ 的骑士的居住地搬到城 $Y_i$；

$T_i=3$ 时表示编号为 $X_i$ 的骑士的武力值修正为 $Y_i$。

outputFormat:
输出若干行，依次为每个旅行的答案。

对每个 $T_i=1$ 的询问，输出一行，按从大到小的顺序输出Henry在这次旅行中挑战的

所有骑士的武力值。如果路线上没有骑士，输出一行，为一个整数 $-1$。

hint: 100%的数据中，$1 \leq N,~M \leq 40,000,~1 \leq Ui,~Vi,~Pi \leq N,~1\leq Q \leq 80,000,~1 \leq K \leq 20$，旅行次数不超过 40,000 次，武力值为不超过1,000的正整数。