title: [NOI2017] 蚯蚓排队

description:
蚯蚓幼儿园有 $n$ 只蚯蚓。幼儿园园长神刀手为了管理方便，时常让这些蚯蚓们列队表演。

所有蚯蚓用从 $1$ 到 $n$ 的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示，根据入园要求，所有蚯蚓的长度都不超过 $6$ 。神刀手希望这些蚯蚓排成若干个队伍，初始时，每只蚯蚓各自排成一个仅有一只蚯蚓的队伍，该蚯蚓既在队首，也在队尾。

神刀手将会依次进行 $m$ 次操作，每个操作都是以下三种操作中的一种：

1. 给出 $i$ 和 $j$ ，令 $i$ 号蚯蚓与 $j$ 号蚯蚓所在的两个队伍合并为一个队伍，具体来说，令 $j$ 号蚯蚓紧挨在 $i$ 号蚯蚓之后，其余蚯蚓保持队伍的前后关系不变。

2. 给出 $i$ ，令 $i$ 号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍，具体来说，在分离之后， $i$ 号蚯蚓在其中一个队伍的队尾，原本紧挨其后的那一只蚯蚓在另一个队伍的队首，其余蚯蚓保持队伍的前后关系不变。

3. 给出一个正整数 $k$ 和一个长度至少为 $k$ 的数字串 $s$ ，对于 $s$ 的每个长度为 $k$ 的连续子串 $t$ （这样的子串共有 $|s|-k+1$ 个，其中 $|s|$ 为 $s$ 的长度），定义函数 $f(t)$，询问所有这些 $f(t)$ 的**乘积**对 $998244353$ 取模后的结果。其中 $f(t)$ 的定义如下：

对于当前的蚯蚓队伍，定义某个蚯蚓的**向后 $k$ 数字串**为：从该蚯蚓出发，沿队伍的向后方向，寻找最近的 $k$ 只蚯蚓（包括其自身），将这些蚯蚓的长度视作字符连接而成的数字串；如果这样找到的蚯蚓不足 $k$ 只，则其没有**向后$k$数字串**。例如蚯蚓的队伍为 $10$ 号蚯蚓在队首，其后是 $22$ 号蚯蚓，其后是 $3$ 号蚯蚓（为队尾），这些蚯蚓的长度分别为 $4$ 、 $5$ 、 $6$ ，则 $10$ 号蚯蚓的**向后 $3$ 数字串**为 `456`， $22$ 号蚯蚓没有**向后 $3$ 数字串**，但其**向后 $2$ 数字串**为 `56`，其**向后 $1$ 数字串**为 `5`。

而 $f(t)$ 表示所有蚯蚓中，**向后 $k$ 数字串**恰好为 $t$ 的蚯蚓只数。

inputFormat:
输入文件的第一行有两个正整数 $n,m$ ，分别表示蚯蚓的只数与操作次数。

第二行包含 $n$ 个不超过 $6$ 的正整数，依次表示编号为 $1,2,\dots,n$ 的蚯蚓的长度。

接下来 $m$ 行，每行表示一个操作。每个操作的格式可以为：

* `1` $i$ $j$（$1 \leq i, j \leq n$）表示：令 $i$ 号与 $j$ 号蚯蚓**所在**的两个队伍合并为一个队伍，新队伍中， $j$ 号蚯蚓紧挨在 $i$ 号蚯蚓之后。保证在此操作之前， $i$ 号蚯蚓在某个队伍的队尾，$j$ 号蚯蚓在某个队伍的队首，且两只蚯蚓不在同一个队伍中。

* `2` $i$（$1 \leq i \leq n$）表示：令 $i$ 号蚯蚓与紧挨其后一个蚯蚓分离为两个队伍。保证在此操作之前， $i$ 号蚯蚓不是某个队伍的队尾。

* `3` $s$ $k$（$k$为正整数，$s$为一个长度至少为$k$的数字串）表示：询问 $s$ 的每个长度为 $k$ 的子串 $t$ 的 $f(t)$ 的乘积，对 998244353 取模的结果。 $f(t)$ 的定义见题目描述。

同一行输入的相邻两个元素之间，用恰好一个空格隔开。

输入文件可能较大，请不要使用过于缓慢的读入方式。

outputFormat: 依次对于每个形如 `3 s k` 的操作，输出一行，仅包含一个整数，表示询问的结果。


title: [NOI2017] 泳池

type: P

background:
久莲是个爱玩的女孩子。

暑假终于到了，久莲决定请她的朋友们来游泳，她打算先在她家的私人海滩外圈一块长方形的海域作为游泳场。然而大海里有着各种各样的危险，有些地方水太深，有些地方有带毒的水母出没。她想让圈出来的这一块海域都是安全的。

description:
经过初步分析，这块海域可视为一个底边长为 $N$ 米，高为 $1001$ 米的长方形网格。其中网格的底边对应着她家的私人海滩，每一个 $1\:\textrm{m}\times1\:\textrm{m}$ 的小正方形都代表着一个单位海域。她拜托了她爸爸明天去测量每一个小正方形是否安全。在得知了信息之后，她要做的就是圈出她想要的游泳场啦。

她心目中理想的游泳场满足如下三个条件：
- 必须保证安全性。即游泳场中的每一个单位海域都是安全的。
- 必须是矩形。即游泳场必须是整个网格中的一个 $a\times b$ 的子网格。
- 必须和海滩相邻。即游泳场的下边界必须紧贴网格的下边界。

例如：当 $N = 5$ 时，若测量的结果如下（因为 $1001$ 太大，这儿只画出网格最下面三行的信息，其他部分都是危险的）。

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

那么她可以选取最下面一行的 $1\times4$ 的子海域，也可以选择第三列的 $3\times1$ 的子海域。注意她不能选取最上面一行的 $1\times5$ 的子海域，因为它没有与海滩相邻。

为了让朋友们玩的开心，她想让游泳场的面积尽可能的大。因此她会选取最下面那一行的 $1\times4$ 的子海域作为最终方案。

虽然她要明天才能知道每一个单位海域是否安全，但是她现在就想行动起来估计一下她的游泳场面积有多大。经过简单的估计，她假设每一个单位海域都有独立的 $q$ 的概率是安全的，$1 − q$ 的概率是不安全的。她想要知道她能选择的最大的游泳场的面积**恰好**为 $K$ 的概率是多少。

然而久莲对数学并不感兴趣，因此她想让你来帮她计算一下这个数值。

inputFormat: 输入一行四个正整数 $N,K,x,y$，其中 $1 \leq x < y < 998\,244\,353$。$q$ 的取值为 $\dfrac{x}{y}$。

outputFormat:
输出一行一个整数表示答案在模 $998\,244\,353$ 意义下的取值。

即设答案化为最简分式后的形式为 $\dfrac{a}{b}$ ，其中 $a$ 和 $b$ 的互质。输出整数 $x$ 使得 $bx \equiv a \mod 998\,244\,353$ 且 $0 \leq x < 998\,244\,353$。可以证明这样的整数 $x$ 是唯一的。


title: [NOI2017] 游戏

background:
【本题原题时限 1s】

狂野飙车是小 L 最喜欢的游戏。与其他业余玩家不同的是，小 L 在玩游戏之余，还精于研究游戏的设计，因此他有着与众不同的游戏策略。

description:
小 L 计划进行 $n$ 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母 $A$、$B$、$C$ 表示。地图一共有四种，分别用小写字母 $x$、$a$、$b$、$c$ 表示。

其中，赛车 $A$ 不适合在地图 $a$ 上使用，赛车 $B$ 不适合在地图 $b$ 上使用，赛车 $C$ 不适合在地图 $c$ 上使用，而地图 $x$ 则适合所有赛车参加。

适合所有赛车参加的地图并不多见，最多只会有 $d$ 张。

$n$ 场游戏的地图可以用一个小写字母组成的字符串描述。例如：$S=\texttt{xaabxcbc}$ 表示小 L 计划进行 $8$ 场游戏，其中第 $1$ 场和第 $5$ 场的地图类型是 $x$，适合所有赛车，第 $2$ 场和第 $3$ 场的地图是 $a$，不适合赛车 $A$，第 $4$ 场和第 $7$ 场的地图是 $b$，不适合赛车 $B$，第 $6$ 场和第 $8$ 场的地图是 $c$，不适合赛车 $C$。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 $ (i, h_i, j, h_j) $ 来描述，表示若在第 $i$ 场使用型号为 $h_i$ 的车子，则第 $j$ 场游戏要使用型号为 $h_j$ 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。

如果无解，输出 `-1`。

inputFormat:
输入第一行包含两个非负整数 $n$, $d$。

输入第二行为一个字符串 $S$。

$n$, $d$, $S$ 的含义见题目描述，其中 $S$ 包含 $n$ 个字符，且其中恰好 $d$ 个为小写字母 $x$。

输入第三行为一个正整数 $m$ ，表示有 $m$ 条用车规则。

接下来 $m$ 行，每行包含一个四元组 $i,h_i,j,h_j$ ，其中 $i,j$ 为整数，$h_i,h_j$ 为字符 $A$ 、$B$ 或 $C$，含义见题目描述。

outputFormat:
输出一行。

若无解输出 `-1`。

若有解，则包含一个长度为 $n$ 的仅包含大写字母 A、B、C 的字符串，表示小 L 在这 $n$ 场游戏中如何安排赛车的使用。如果存在多组解，输出其中任意一组即可。


title: [NOI2017] 蔬菜

description:
小 N 是蔬菜仓库的管理员，负责设计蔬菜的销售方案。

在蔬菜仓库中，共存放有 $n$ 种蔬菜，小 N 需要根据不同蔬菜的特性，综合考虑各方面因素，设计合理的销售方案，以获得最多的收益。

在计算销售蔬菜的收益时，每销售一个单位第 $i$ 种蔬菜，就可以获得 $a_i$ 的收益。

特别地，由于政策鼓励商家进行多样化销售，第一次销售第 $i$ 种蔬菜时，还会额外得到 $s_i$ 的额外收益。

在经营开始时，第 $i$ 种蔬菜的库存为 $c_i$ 个单位。

然而，蔬菜的保鲜时间非常有限，一旦变质就不能进行销售，不过聪明的小 N 已 经计算出了每个单位蔬菜变质的时间：对于第 $i$ 种蔬菜，存在保鲜值 $x_i$，每天结束时会 有 $x_i$ 个单位的蔬菜变质，直到所有蔬菜都变质。（注意：每一单位蔬菜的变质时间是固定的，不随销售发生变化）

形式化地：对于所有的满足条件 $d\times x_i \leq c_i$ 的正整数 $d$ ，有 $x_i$ 个单位的蔬菜将在 第 $d$ 天结束时变质。

特别地，若 $(d - 1)\times x_i \leq c_i < d\times x_i$ ，则有 $c_i - (d - 1)\times x_i$ 单位的蔬菜将在第 $d$ 天结束时变质。

注意，当 $x_i = 0$ 时，意味着这种蔬菜不会变质。

同时，每天销售的蔬菜，总量也是有限的，最多不能超过 $m$ 个单位。

现在，小 N 有 $k$ 个问题，想请你帮忙算一算。每个问题的形式都是：对于已知的 $p_j$，如果需要销售 $p_j$ 天，最多能获得多少收益？

inputFormat:
第一行包含三个正整数 $n,m,k$，分别表示蔬菜的种类数目、每天能售出蔬菜总量上限、小 N 提出的问题的个数。

接下来 $n$ 行，每行输入四个非负整数，描述一种蔬菜的特点，依次为 $a_i,s_i,c_i,x_i$ ， 意义如上文所述。

接下来 $k$ 行，每行输入一个非负整数 $p_j$ ，意义如上文所述。

outputFormat: 输出 $k$ 行，每行包含一个整数，第 $i$ 行的数表示第 $i$ 个问题的答案。


title: [NOI2017] 分身术

description:
> “分！身！术！” —— 小 P

平面上有 $n$ 个小 P 的分身。定义一组分身占领的区域为覆盖这组分身的最小凸多边形。小 P 能力有限，每一时刻都会有若干分身消失。但在下一时刻之前，小 P 会使用分身术使得这些消失的分身重新出现在原来的位置。

小 P 想知道，每一时刻分身消失后，剩下的分身占领的区域面积是多少？

inputFormat:
输入第一行包含两个正整数 $n,m$，描述初始时分身的个数，和总时刻数。

接下来 $n$ 行，第 $i$ 行有两个整数 $x_i, y_i$ ，描述第 $i$ 个分身的位置。

接下来 $m$ 行，每行的第一个整数 $k$ 表示这一时刻有 $k$ 个分身消失。接下来有 $k$ 个非负整数 $c_1, c_2, \ldots, c_k$，用于生成消失的分身的编号。

生成方式如下：

设上一个时刻中，分身占领面积的**两倍**为 $S$。则该时刻消失的分身 $p_1, p_2, \ldots , p_k$ 的编号为：$p_i = [(S + c_i) \bmod n] + 1$。

特别的，在第一个时刻，我们认为上一个时刻中，$S = -1$，即：第一个时刻消失的分身$p_1, p_2, \ldots , p_k$的编号为：$p_i = [(−1 + c_i) \bmod n] + 1$。

outputFormat: 按给出时刻的顺序依次输出 $m$ 行，每行一个整数，表示该时刻剩余分身所占领区域面积的**两倍**。


title: [SHOI2012] 排序

background: SHOI2012 D2T2

description:
众所周知，1~n 的全排列包含 n!个排列。通常情况下，我们在生成全排列时都按照他们的字典序生成的。而在本题中，我们就将要考虑一种特殊的全排列生成方式。

具体的，生成的全排列的顺序是由一个生成器决定的。

(1) 生成器本身也是一个 1~n 的排列：$a_1$ , $a_2$ , …, $a_n$ 。

(2) 对于两个不相同的 1~n 的 $x_1$ , $x_2$ , …, $x_n$ 、$y_1$ , $y_2$ , …, $y_n$ 排列而言，首先找到最小的 i，使得 $x_{ai}$ 与 $y_{ai}$ 不相等。

(3) 根据(2)中选择的 i，如果 $x_{ai}$ 在排列 $a_1$ , $a_2$ , …, $a_n$ 中排在 $y_{ai}$ 之前，那么 $x_1$ ,$x_2$ , …, $x_n$ 就会在 $y_1$ , $y_2$ , …, $y_n$ 之前生成。

例如，当 n = 3，生成器为 132 时，1~n 的全排列的生成顺序为：123，132，321，312，231，213。

输入一个排列 $x_1$ , $x_2$, …, $x_n$ ，问，哪个生成器能使得这个排列在所有的排列中尽可能早的生成，哪个生成器能使得这个排列在所有的排列中尽可能晚的生成。

如果有多种生成器能达到要求，那么请输出字典序最小的符合要求的生成器。

inputFormat: 输入的第一行是整数 n，第二行是 1~n 的一个排列 $x_1$ , $x_2$ , …, $x_n$ 。

outputFormat:
输出的第一行是一个 1~n 的排列，表示让 $x_1$ , $x_2$ , …, $x_n$ 尽早输出的生成器。

输出的第二行是一个 1~n 的排列，表示让 $x_1$ , $x_2$ , …, $x_n$ 尽晚输出的生成器。

如果有多种生成器能达到要求，那么请输出字典序最小的符合要求的生成器。

hint:
对于 30%的数据，有 n ≤ 10；

对于 50%的数据，有 n ≤ 200；

对于 90%的数据，有 n ≤ 30000；

对于 100%的数据，有 n ≤ 500000。


title: [SHOI2012] 回家的路

background: SHOI2012 D2T1

description:
2046 年 OI 城的城市轨道交通建设终于全部竣工，由于前期规划周密，建成后的轨道交通网络由$2n$条地铁线路构成，组成了一个$n$纵$n$横的交通网。如下图所示，这$2n$条线路每条线路都包含$n$个车站，而每个车站都在一组纵横线路的交汇处。

出于建设成本的考虑，并非每个车站都能够进行站内换乘，能够进行站内换乘的地铁站共有$m$个，在下图中，标上方块标记的车站为换乘车站。已知地铁运行 1 站需要 2 分钟，而站内换乘需要步行 1 分钟。Serenade 想要知道，在不中途出站的前提下，他从学校回家最快需要多少时间（等车时间忽略不计）。

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

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

接下去$m$行每行两个整数$x,y$,表示第$x$条横向线路与第$y$条纵向线路的交

汇站是站内换乘站。

接下去一行是四个整数$x_1,y_1,x_2,y_2$。表示 Serenade 从学校回家时，在第 $x_1$条横向线路与第$y_1$条纵向线路的交汇站上车，在第$x_2$条横向线路与第$y_2$条纵向线路的交汇站下车。

outputFormat: 输出文件只有一行，即 Serenade 在合理选择线路的情况下，回家所需要的时间。如果 Serenade 无法在不出站换乘的情况下回家，请输出-1。


title: [SHOI2012] 火柴游戏

description:
小明非常喜欢玩火柴游戏：首先用火柴棒摆出一个可能是错误的等式，然后通过添加、删除或移动火柴棒，使得等式成立。下图展示每个数字的样子：

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

我们只考虑形如“A = B”的式子，其中 A 和 B 是两个具有相同位数的整数。

小明可进行三种操作：

1. 在任意位置添加一根火柴棒；

2. 从任意位置删除一根火柴棒；

3. 将任意一根火柴棒移动到另一个位置。

在完成所有操作后，等号两侧必须都是合法的数字，且完全相等。我们约定：

1. 小明不能消除任何数字，也就是说，可以删除一个数字的部分火柴，但不能令它消失；

2. 小明不能增加任何数字，也就是说，可以在一个已有的数字上添加火柴，或将火柴移动到一个已有的数字上，但不能凭空增加一个数字；

3. 小明不能拆分或者合并数字，比如将一个 8 变成两个 1，或者将两个 1合并成一个 8；

4. 其中代表 1 的火柴棒必须靠右边摆放，放在左边不是有效的数字。每种操作都有一定的代价：

 对一个添加操作，如果这是第$i$次进行添加操作，这一步的费用为 $p_1\times i+q_1$

 对一个删除操作，如果这是第$i$次进行删除操作，这一步的费用为$p_2\times i+q_2$

 对一个移动操作，如果这是第$i$次进行移动操作，这一步的费用为$p_3\times i+q_3$

例如，小明在游戏中添加了 3 根火柴，移动了 1 根火柴，删除了 2 根火柴，那么他总的花费为$[(p_1\times 1+q_1)+(p_1\times 2+q_1)+(p_1\times 3+q_1)]+(p_3\times 1+q_3)+[(p_2\times 1+q_2 )+(p_2\times 2+q_2)]$。

小明想知道，他如何才能用最少的花费使等式成立。你能写个程序帮助他吗？

inputFormat:
第 1 行，一个整数 L，表示等式中两个数的位数。

第 2-3 行，每行各一个长度为 L、仅由数字构成的字符串，表示等式两侧的数。

第 4 行，给出六个不超过 100 的非负整数$p_1,q_1,p_2,q_2,p_3,q_3$。

outputFormat: 输出一行，包含一个整数，为使等式成立的最小的操作代价。


title: [SHOI2012] 信用卡凸包

description:
信用卡是一个矩形，唯四个角作了圆滑处理，使它们都是与矩形的两边相切的 1/4 圆，如下图所示。现在平面上有一些规格相同的信用卡，试求其凸包的周长。注意凸包未必是多边形，因为它可能包含若干段圆弧。

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

inputFormat:
输入的第一行是一个正整数 n，表示信用卡的张数。第二行包含三个实数 a, b, r，分别表示信用卡（圆滑处理前）竖直方向的长度、水平方向的长度，以及 1/4 圆的半径。

之后 n 行，每行包含三个实数 x, y, θ，分别表示一张信用卡中心（即对角线交点）的横、纵坐标，以及绕中心 逆时针旋转的 弧度。

outputFormat: 输出只有一行，包含一个实数，表示凸包的周长，四舍五入精确到小数点后2 位。

hint:
样例1说明： ![](https://cdn.luogu.com.cn/upload/pic/6550.png)

本样例中的 2 张信用卡的轮廓在上图中用实线标出，如果视 1.5707963268为pi/2，那么凸包的周长为16+4sqrt(2)

样例2说明： ![](https://cdn.luogu.com.cn/upload/pic/6551.png)

样例3说明： ![](https://cdn.luogu.com.cn/upload/pic/6552.png)

其凸包的周长约为41.628267652。

本题可能需要使用数学库中的三角函数。不熟悉使用方法的选手，可以参考下面的程序及其输出结果：

```cpp
uses math;
const Pi = 3.141592653589793;
begin
writeln(sin(30.0 / 180.0 * Pi) : 0 : 10);
writeln(cos(60.0 / 180.0 * Pi) : 0 : 10);
writeln(tan(45.0 / 180.0 * Pi) : 0 : 10);
writeln(arcsin(1.0) : 0 : 10);
writeln(arccos(0.0) : 0 : 10);
writeln(arctan(1.0) : 0 : 10);
end.
```
```cpp
#include <iostream>
#include <math.h>
using namespace std;
const double Pi = 3.141592653589793;
int main()
{
cout.setf(ios::fixed);
cout.precision(10);
cout<<sin(30.0 / 180.0 * Pi)<<endl;
cout<<cos(60.0 / 180.0 * Pi)<<endl;
cout<<tan(45.0 / 180.0 * Pi)<<endl;
cout<<asin(1.0)<<endl;
cout<<acos(0.0)<<endl;
cout<<atan(1.0)<<endl;
return 0;
}
```
输出结果：0.5000000000

0.5000000000

1.0000000000

1.5707963268

1.5707963268

0.7853981634

数据范围：

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

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


title: [SHOI2012] 随机树

background: SHOI2012 D1T3

inputFormat: 输入仅有一行，包含两个正整数 q, n，分别表示问题编号以及叶结点的个数。

outputFormat: 输出仅有一行，包含一个实数 d，四舍五入精确到小数点后 6 位。如果 q = 1，则 d 表示叶结点平均深度的数学期望值；如果 q = 2，则 d 表示树深度的数学期望值。

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

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

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


title: 高兴的津津

description: 津津上高中了。她在自己的妈妈的魔鬼训练下，成为了一个神犇，每次参加一次 OI 比赛必拿 Au 虐全场。每次她拿到一个 Au 后就很高兴。假设津津不会因为其它事高兴，并且她的高兴会持续 $T$ 天（包含获奖当天。就算在高兴的时候再次拿到 Au，他的高兴也只能维持包括这次拿奖之日起 $T$ 天，而不是额外增加 $T$ 天的高兴时间，除非之后再拿奖）。请你帮忙检查一下津津接下来的的日程安排，要参加 $n$ 场比赛，看看接下来的几天，津津会累计开心多久？

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

接下来一行，$n$ 个单调递增整数 $t_i$，表示她在第 $t_i$ 天的时候拿了一个 Au。

outputFormat: 一个整数表示，津津累计开心多久。

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

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

- $1\le n\le2\times10^5$。
- $1\le T\le10^9$。
- $1\le t_i\le 10^9$，$t_i$ 单调递增。


title: 【模板】可持久化线段树 2

background:
这是个非常经典的可持久化权值线段树入门题——静态区间第 $k$ 小。

**数据已经过加强，请使用可持久化权值线段树。同时请注意常数优化**。

description: 如题，给定 $n$ 个整数构成的序列 $a$，将对于指定的闭区间 $[l, r]$ 查询其区间内的第 $k$ 小值。

inputFormat:
第一行包含两个整数，分别表示序列的长度 $n$ 和查询的个数 $m$。
第二行包含 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个元素 $a_i$。
接下来 $m$ 行每行包含三个整数 $ l, r, k$ , 表示查询区间 $[l, r]$ 内的第 $k$ 小值。

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

hint:
### 样例 1 解释

$n=5$，数列长度为 $5$，数列从第一项开始依次为$\{25957, 6405, 15770, 26287, 26465\}$。

- 第一次查询为 $[2, 2]$ 区间内的第一小值，即为 $6405$。
- 第二次查询为 $[3, 4]$ 区间内的第一小值，即为 $15770$。
- 第三次查询为 $[4, 5]$ 区间内的第一小值，即为 $26287$。
- 第四次查询为 $[1, 2]$ 区间内的第二小值，即为 $25957$。
- 第五次查询为 $[4, 4]$ 区间内的第一小值，即为 $26287$。

### 数据规模与约定

- 对于 $20\%$ 的数据，满足 $1 \leq n,m \leq 10$。
- 对于 $50\%$ 的数据，满足 $1 \leq n,m \leq 10^3$。
- 对于 $80\%$ 的数据，满足 $1 \leq n,m \leq 10^5$。
- 对于 $100\%$ 的数据，满足 $1 \leq n,m \leq 2\times 10^5$，$0\le a_i \leq 10^9$，$1 \leq l \leq r \leq n$，$1 \leq k \leq r - l + 1$。


title: 序列

description:
给定一个长度为 $n$ 的序列，给出 $q$ 个操作，形如：

$1~l~r~x$ 表示将序列下标介于 $[l,r]$ 的元素加上 $x$ （请注意，$x$ 可能为负）

$2~p~y$ 表示查询 $a_p$ 在过去的多少秒时间内不小于 $y$ （不包括这一秒，细节请参照样例）

开始时为第 $0$ 秒，第 $i$ 个操作发生在第 $i$ 秒。

inputFormat:
第一行两个整数 $n,q$，意义如描述所述。

接下来一行 $n$ 个整数 $a_i$，表示序列的每个元素的初始值。

接下来 $q$ 行，每行第一个数为 $\text{opt}$，表示这次操作的类型。如果 $\text{opt} = 1$，后面紧跟三个整数 $l, r, x$，意义如描述所述；如果 $\text{opt} = 2$，后面紧跟两个整数 $p, y$，意义如描述所述。

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

hint:
样例一说明：位置 $1$ 在第 $0$ 秒到第 $3$ 秒的值为 $1,1,-2,-2$。对于第一个查询，第 $0$ 到 $1-1=0$ 秒中时间不小于 $2$；对于第二个查询，第 $0$ 到第 $3-1=2$ 秒时间不小于 $1$，分别为第 $0$ 秒，第 $1$ 秒。

对于 $30\%$ 的数据，保证 $n,q \leq 1000$

对于 $70\%$ 的数据，保证 $n,q \leq 50000$

对于 $100\%$ 的数据，保证 $2 \leq n,q \leq 100000$， $1 \leq l \leq r \leq n$， $1 \leq p \leq n$，$-10^9 \leq x,y,a_i \leq 10^9$


title: [IOI2017] Nowruz

background: **[数据以及checker下载](http://pan.baidu.com/s/1o8jwPmy)**

description:
再过几天就是诺鲁孜节了（波斯人的新年），爷爷邀请他的全家人到他的花园来聚会。在众多的宾客中有$k$个小孩。为了让这些孩子们在聚会中更开心，爷爷打算让他们玩一个捉迷藏的游戏。

整个花园可以看成一个有$m\times n$个方格的网格。其中有一些（或许没有）方格被岩石堵住了，而剩下的方格就称为**空格**。如果两个格子共享同一条边，我们就称这两个格子是**邻居**。因此，每一个方格最多有$4$个邻居：两个水平方向的和两个垂直方向的。爷爷想把花园变成一个迷宫。为达此目的，他会在花园中的一些**空格**上种植灌木来堵住他们。而这些被灌木丛堵住的方格就不再是**空格**了。

一个迷宫必须具有下面所述的性质。在迷宫中的任意一对空格$a$和$b$之间都只会恰有唯一的一条简单路径相连。而这条由$a$到$b$的简单路径就是一个从空格$a$开始并以空格$b$结束的序列，序列中所有的方格必须是不同的，而且每个相连的方格都是邻居。

一个小孩能够躲藏的方格当且仅当这个方格是**空格**，而且它恰有唯一一个邻居是空格。同一个空格内只能躲藏一个小孩。

题目会给出整个花园的地图作为输入文件。你的任务就是帮助爷爷构造一个能够躲藏尽量多小孩的迷宫。

## 评分

一个**有效**的输出文件必须符合下列所有的条件：

- 除了把输入文件中的任意多个字母`.`修改成字母`X`（即被灌木堵塞）外，输出的地图必须和输入地图完全一样。

- 输出的地图必须符合在上文中提及的迷宫的所有性质。

对于某一个测试数据，如果你的输出不是**有效**的，你的这个测试数据的得分将会是$0$。反之，你的得分是$\min(10, 10\cdot l/k)$，向下取值至小数后二位，这里的$l$是指你输出的迷宫中能够最多藏着的小孩，而$k$则表示在输入文件中题目要求你躲藏的小孩数目。对于一个测试数据，你能够得到$10$分，当且仅当你的输入是一个能够躲藏$k$个或更多个小孩的迷宫。

对于每组测试数据都存在一个能得到$10$分的答案。

请注意如果你答案是有效的，但根据上述公式你的得分仍然是$0$分，则在评分系统中，现实的结果将会是'Wrong Answer'。

inputFormat:
这是一个提交答案型的题目，而且它有部份分。题目会给出$10$个描述爷爷花园的输入文件。对于每个输入文件你应该提交一个含有迷宫的地图作为输出文件我们会根据你提交的每个输入文件中的迷宫能够躲藏的小孩数目来给出你的分数。

这道题目你不需要提交任何源代码。

每个输入文件都描述了一个表示整个花园的网格，我们也会给出爷爷邀请的小孩数目$k$。格式如下：

第$1$行： $1 : \ \ m \ n \ k$

第$1+i\ (1 \leqslant i \leqslant m)$行： 网格中的第$i$行，它是一个长度为$n$的字符串，包含以下的字符（中间没有空格）：

- `.`： 一个空格，

- `#`： 一块岩石。

outputFormat:
第$i\ (1 \leqslant i \leqslant m)$行： 迷宫中的第$i$行（种植了树木的花园）。它是一个长度为$n$的字符串，包含以下字母（中间没有空格）：

\* `.` ： 一个空格，

\* `#`： 一块岩石，

\* `X`： 一个灌木（注意字母X必须为大写字母）。

hint:
样例输出是其中一个有效的输出。

对于这个输出，因为$l=4$个小孩能够这个迷宫中，所以这个解答能够得到$10 \cdot 4 / 5 = 8$分。小孩能够躲藏的方格如下以O所示：

```plain
OXOX#
.#.O#
...#X
XX.O#
```
以下的三个输出都不是有效的输出：

```plain
.XXX#    ...X#    XXXX#
.#XX#    .#.X#    X#XX#
...#.    ...#X    ..X#X
XX..#    XXXX#    ..XX#
```
在最左边的输出中，左上角的空格和最右列（位于右下方）的空格之间并没有一条简单路径。

在其他的两个输出中，对于任意两个空格之间都恰有两条简单路径相连。

## 限制条件

$1 \leqslant m,n \leqslant 1024$


title: [IOI2017] Wiring

background:
这是一道交互题。

本题仅支持 C++ 系列语言，提交时不需要包含 `wiring.h` 头文件，但需要在程序开头包含 `vector` 头文件以及声明函数 `long long min_total_length(std::vector<int> r, std::vector<int> b)`。

**由于不可名状的 BUG，使用 C++14 (GCC9) 提交会导致 CE，请不要使用其提交。**

description:
Maryam 是一位电机工程师。她正在为一座通讯塔设计接线方案。在这个塔上有一些分布在不同高度的连接点。一条电线可以用来将任何两个连接点连接起来。每一个连接点都可以接上任意数目的电线。而连接点共有两种：分别为红色连接点及蓝色连接点。

为了表述方便起见，通讯塔会被视为一条直线，而那些红色及蓝色连接点会被视为在这条直线上的一些非负整数坐标。一条电线的长度是该电线所连接的两个连接点间的距离。

你要做的是帮 Maryam 找出一个接线的方案，使得满足以下条件：

1. 每个连接点上最少有一条电线连接到一个不同颜色的连接点上

2. 所用的电线的总长为最短。

## 实现细节

你需要实现以下的子程序：

`long long min_total_length(std::vector<int> r, std::vector<int> b)`

- $r$：一个长度为 $n$ 的数组，其内以升序排列着所有红色连接点的位置。

- $b$：一个长度为 $m$ 的数组，其内以升序排列着所有蓝色连接点的位置。

- 这个子程序需返回在所有可能的连接方案中，最短电线总长度的那个方案的电线作为其返回值。

- 请注意这个子程序的返回值的类型为 `long long` 。

inputFormat: 你需要实现上面所述的子程序。

outputFormat: 返回一个 `long long` 值。

hint:
样例中函数传递参数：

`min_total_length([1, 2, 3, 7], [0, 4, 5, 9, 10])`

以下的图表表述了样例中的数据。

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

- 图中以水平的方式表示出相关的通讯塔。

- 因题目打印是黑白色的，所以红色接点以较深色来表示，而蓝色接点则以较浅色来表示。

- 图中有 $4$ 个红色的连接点，其位置分别为 $1,2,3$ 及 $7$ 。

- 图中有 $5$ 个蓝色的连接点，其位置分别为 $0,4,5,9$ 及 $10$ 。

- 该例的最优解的电线总长度为 $1+2+2+2+3=10$ ，所以子程序的返回值为 $10$ 。

- 请注意共有两条电线连接在位置为 $7$ 的连接点上。

## 限制条件

- $1 \leqslant n,m \leqslant 100000$

- $0 \leqslant r[i] \leqslant 10^9 $（对于所有$0 \leqslant i \leqslant n-1$）

- $0 \leqslant b[i] \leqslant 10^9$（对于所有$0 \leqslant i \leqslant m-1$）

- 数组$r$及数组$b$都已经按升序排好序。

- 在数组$r$及$b$内的所有$n+m$个值均是不同的。

## 子任务

1. ($7$ 分)  $n,m\leqslant 200$。

2. ($13$ 分)  所有红色接点的位置坐标小于任何蓝色接点的坐标。

3. ($10$ 分)  在每$7$个连续的（接续）的连接点内必有最少一个红色接点及蓝色接点。

4. ($25$ 分)  所有接点在$[1,n+m]$范围内有不同的位置坐标。

5. ($45$ 分)  没有任何附加的限制。


title: 数圈

description:
求 $n$ 个点的无向完全图删去一条边之后圈的个数，答案模 $998244353$。

注：圈指的是任选一个顶点为起点，沿着不重复的边，经过不重复的顶点为途径，之后又回到起点的闭合途径。

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

接下来 $T$ 行，每行一个整数 $n$，意义如描述所述。

outputFormat: 一共 $T$ 行，每行一个整数，表示答案。


title: 拆分

description: 给定一个整数 $n$，求将 $n$ 分解为互不相同的不小于 $2$ 的整数的乘积的方案数。答案模 $998244353$。

outputFormat: 一共 $T$ 行，每行一个整数，表示答案。

hint:
样例中，因为

$688 = 2 \times 4 \times 86= 2 \times 8 \times 43= 2 \times 344= 4 \times 172= 8 \times 86= 16 \times 43$

所以答案为 $6$

对于 $10\%$ 的数据，保证 $n$ 为质数

对于 $20\%$ 的数据，保证 $2 \leq n \leq 10^4$

对于 $50\%$ 的数据，保证 $ 2  \leq n \leq 10^7$

对于 $100\%$ 的数据， 保证 $ 2 \leq n \leq 10^{12}$

所有数据满足 $1 \leq T \leq 5$


title: 【模板】可持久化平衡树

background:
本题为题目 **普通平衡树** 的可持久化加强版。

**数据已经经过强化**

**感谢@Kelin 提供的一组hack数据**

description:
您需要写一种数据结构（可参考题目标题），来维护一个可重整数集合，其中需要提供以下操作（ **对于各个以往的历史版本** ）：

1、 插入 $x$

2、 删除 $x$（若有多个相同的数，应只删除一个，**如果没有请忽略该操作**）

3、 查询 $x$ 的排名（排名定义为比当前数小的数的个数 $+1$）

4、查询排名为 $x$ 的数

5、 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数，**如不存在输出** $-2^{31}+1$ ）

6、求 $x$ 的后继（后继定义为大于 $x$，且最小的数，**如不存在输出** $2^{31}-1$ ）

**和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本。（操作3, 4, 5, 6即保持原版本无变化）**

每个版本的编号即为操作的序号（版本0即为初始状态，空树）

inputFormat:
第一行包含一个正整数 $n$ ，表示操作的总数。

接下来 $n$ 行，每行包含三个整数，第 $i$ 行记为 $v_i, \text{opt}_i, x_i$。

$v_i$ 表示基于的过去版本号，$\text{opt}_i$ 表示操作的序号， $x_i$ 表示参与操作的数值

outputFormat: 每行包含一个整数，依次为各个 $3,4,5,6$ 操作所对应的答案


title: [IOI2017] Toy Train

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

### 由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。

description:
Arezou 和她的兄弟 Borzou 是双胞胎。他们收到的生日礼物是一套好玩的玩具火车。他们用它建了一下 $n$ 个车站和 $m$ 段单向轨道的铁路系统。这些车站的编号是从 $0$ 到 $n-1$。每段轨道都始于某一车站，然后终于同一车站或其他车站。每个车站至少会有一段轨道以它为起点。

其中有些车站是充电车站。无论何时，如果火车抵达某个充电车站。无论何时，如果火车抵达某个充电车站，它都会被充到满电。满电火车拥有足够的动力连续地试过 $n$ 段轨道，但是如果不再充电的话，在即将进入第 $n+1$ 段轨道时它就会因电已用光而停车。

每个车站都有一个轨道开关，可以扳向任一以该车站为起点的轨道。火车从某个车站驶出时，驶向的正是该车站的开关所扳向的轨道。

这对双胞胎打算用他们的火车玩个游戏。他们已经分完了所有的车站：每个车站要么归 Arezou，要么归 Borzou。游戏里面只有一列火车。游戏开始时，这列火车停在车站 $s$ ，并且充满了电。为启动游戏，车站 $s$ 的拥有者把车站 $s$ 的开关扳向某个以 $s$ 为起点的轨道。随后他们启动火车，火车也就开始沿着轨道行驶。无论何时，在火车首次进入某一车站时，该车站的拥有者都要扳定车站开关。开关一旦扳定，它就会保持状态不变直到游戏结束。因此，火车如果开到了一个曾经进过的车站，就会沿着与之前相同的轨道开出该车站。

由于车站数量是有限的，火车的行驶最终都会落入某个环路。环路是指一系列**不同**的车站 $c_0,c_1,\cdots ,c_{k-1}$，其中火车在离开车站 $c_i\ \ (0\leqslant i < k-1)$ 后驶上连向车站 $c_{i+1}$ 的轨道，在离开车站 $c_{k-1}$ 后驶上连向车站 $c_0$ 的轨道。一个环路可能只包括一个车站（此时 $k=1$），即火车从车站 $c_0$ 驶出后又驶上了连向车站 $c_0$ 的轨道。

如果火车能够连续行驶跑完，Arezou 就赢了。否则火车最后会把电用光而停车，这样 Borzou 就赢了。换句话说，如果 $c_0,c_1,\cdots ,c_{k-1}$中至少有一个充电车站，且使得火车能够不断地充电而沿着环路跑个没完，Arezou 赢。否则，它就会最终把电用光（有可能是在沿着环路跑好几圈后），Borzou 赢。

现在给你一个这样的铁路系统。Arezou 和 Borzou将会玩 $n$ 轮游戏。其中在第 $s$ 轮游戏中（$0\leqslant s \leqslant n-1$），火车最初停在车站 $s$ 上。你的任务是，对每一轮游戏，判断是否无论 Borzou 怎么玩，Arezou 都必胜。

## 实现细节

你需要实现下面的函数

(C++) `std::vector who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v)`

(Java) `int[] who_wins(int[] a, int[] r, int[] u, int[] v)`

- $a$：长度为 $n$ 的数组。如果 Arezou 拥有车站 $i$，则 $a_i=1$；否则 Borzou 拥有车站 $i$，且 $a_i=0$。

- $r$：长度为$n$的数组。如果车站$i$是充电车站，则$r[i]=1$。否则$r[i]=0$。

- $u$ 和 $v$：长度为 $m$ 的数组。对于所有 $0\leqslant i \leqslant m-1$，存在某一单向轨道，其起点为 $u_i$，终点为 $v_i$。

- 该函数需要返回一个长度为 $n$ 的数组  $w$。对于每个 $0\leqslant i \leqslant n-1$，如果在火车最初停在车站 $i$ 的游戏中，不管 Borzou 怎么玩，Arezou 都能赢，则 $w_i$ 的值应为 $1$。否则 $w_i$ 的值应为 $0$。

inputFormat: 你需要实现上述子程序。

outputFormat: 你的子程序需要返回一个合法的结果。

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

- 这里有 $2$ 个车站。Borzou 拥有充电车站 $1$。Arezou拥有充电车站 $1$，但是它不是充电车站。

- 这里有 $4$ 段轨道 $(0,0),(0,1),(1,0)$ 和 $(1,1)$，其中 $(i,j)$ 表示一个以车站 $i$ 为起点、车站$j$为终点的单向轨道。

- 考虑火车最初停在车站 $0$ 的游戏。如果 Borzou 将车站 $0$ 的开关扳向轨道 $(0,0)$，那么火车就会沿着这个环形轨道绕个没完（注意，车站 $0$ 是一个充电车站）。在这种情况下，Arezou 赢。否则，如果 Borzou 把车站 $0$ 的开关扳向轨道 $(0,1)$，Arezou 可以把车站 $1$ 的开关扳向轨道 $(1,0)$。这样的话，火车将会在两个车站之间绕个不停。Arezou 还是会赢，因为车站$0$是充电车站，火车将跑个没完。因此，无论 Borzou 怎么玩，Arezou 都会赢。

- 根据类似的逻辑，在火车最初停在车站 $1$ 的游戏中，无论 Borzou 怎么玩，Arezou 也都会赢。因此，函数应当返回 $[1,1]$。

## 数据范围和限制

- $1\leqslant n \leqslant 5000$
- $n \leqslant m \leqslant 20000$
- 至少会有一个充电车站。
- 每个车站至少会有一段轨道以它为起点。
- 可能会有某个轨道的起点和终点是相同的（即 $u_i=v_i$）。
- 所有轨道两两不同。也就是说，不存在这样的两个下标 $i$ 和 $j$（$0\leqslant i < j \leqslant m-1$），使得 $u_i=u_j$ 且 $v_i=v_j$。
- 对于所有 $0\leqslant i \leqslant m-1$，都有 $0\leqslant u_i,v_i \leqslant n-1$。

## 子任务

1. ($5$ 分) 对于所有 $0 \leqslant i \leqslant m-1$，都有 $v_i=u_i$ 或者 $v_i=u_i+1$。
2. ($10$ 分) $n\leqslant 15$。
3. ($11$ 分) Arezou 拥有所有车站。
4. ($11$ 分) Borzou 拥有所有车站。
5. ($12$ 分) 充电车站的数量为 $1$。
6. ($51$ 分) 无任何限制。


title: [IOI2017] The Big Prize

background:
这里是洛谷。如果有疑问，可以发帖求助。

如果你习惯于写函数式交互，以下内容可能对你有帮助：

```cpp
vector<int>ask(int i)
{
	printf("? %d\n",i);fflush(stdout);
	vector<int>ret(2);
	scanf("%d%d",&ret[0],&ret[1]);
	return ret;
}
int find_best(int n)
{
	//
}
main()
{
	int n;scanf("%d",&n);
	printf("! %d\n",find_best(n));
}
```

无论如何，你都不应引入额外的头文件。

description:
“大奖”是一个家喻户晓的 TV 游戏节目。这次你很幸运地进入到最后一轮。已知编号从 $0$ 到 $n-1$ 的 $n$ 个盒子从左到右排成一行，你就站在这排盒子的前面。每个盒子里面放有一个奖品，必须打开盒子才能看到是什么奖品。已知有 $v\leq5$ 种不同类型的奖品。这 $v$ 种类型按照奖品价值的降序从 $1$ 到 $v$ 排列。

类型 $1$ 的奖品是一块钻石，价值最高。所有盒子加起来刚好只有一块钻石。类型 $v$ 的奖品是一块棒棒糖，价值最低。为使得游戏更加激动人心，相对便宜的奖品数量远比价值昂贵的奖品数量要多。更具体一点，对于满足 $2\leq t \leq v$ 的所有 $t$，我们有： 如果类型 $t-1$ 的奖品有 $k$ 个，那么类型 $t$ 的奖品将严格多于 $k^2$ 个。

你的目标是赢得那块钻石。在游戏结束时，你必须打开一个盒子并收取盒子内的奖品。在选择要打开的盒子之前，你可以向节目主持人 Rambod 提一些问题。在每一个问题中，你选择就某个 $i$ 号盒子进行提问。Rambod 将给你一个包含两个整数的数组 $a$ 作为回答。这两个整数的意义如下：

- 在 $i$ 号盒子左面的盒子中，刚好有 $a[0]$ 个盒子中的奖品，价值比 $i$ 号盒子中的奖品价值要高。
- 在 $i$ 号盒子右面的盒子中，刚好有 $a[1]$ 个盒子中的奖品，价值比 $i$ 号盒子中的奖品价值要高。

例如，假设 $n=8$，在你的问题中，你选择就 $i=2$ 号盒子进行提问。Rambod 的回答是 $a=[1,2]$。这个回答的意义是：

- $0$ 号盒子和 $1$ 号盒子中恰好有一个盒子中的奖品比 $i$ 号盒子中的奖品更贵。
- 在 $3,4,\cdots,7$ 号盒子中恰好有 $2$ 个盒子中的奖品比 $2$ 号盒子中的奖品更贵。

你的任务就是通过问少量的问题找出包含钻石的盒子。

inputFormat:
你的程序开始运行时，应当读入一个正整数 $n$。

你可以按以下格式发起询问：

- `? i`
	意为你选择就 $i$ 号盒子进行提问。你需要保证 $0\leq i<n$。
	随后你应当读入两个整数 `a[0] a[1]`，是交互库对你的回答。

你可以按以下格式报告答案：

- `! i`
	意为你确定 $i$ 号盒子内有钻石。
    随后你应当立刻结束你的程序。

outputFormat:
在发起询问后，不要忘记刷新缓冲区。你可以使用：

- `fflush(stdout)` or `cout.flush()` in C++;
- `stdout.flush()` in Python;
- 对于其他语言，参阅其文档。

hint:
### 样例解释

```plain
8
3 2 3 1 3 3 2 3
```

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

上图阐释了这个例子。图中上半部分给出了每个盒子中奖品的类型。图中的下半部分阐释了询问 `? 2`。

### 限制

- $3\leq n \leq200000$.
- 每个盒子中奖品的类型介于 $1$ 和 $v$ 之间（含）。
- 类型 $1$ 的奖品恰有一个。
- 对于所有 $2\leq t \leq v$，如果类型 $t-1$ 的奖品有 $k$ 个，那么类型 $t$ 的奖品将严格多于 $k^2$ 个。

### 子任务与评分

1.  （$20$ 分）恰好有 $1$ 个钻石和 $n-1$ 个棒棒糖 （所以，$v=2$）。你可以询问最多 $10000$ 次。
2.  （$80$ 分）没有附加限制。

在子任务 2 中你可以获得部分分。令 $q$ 是在这个子任务的所有测试数据上发起询问的最大次数，那么你在这个子任务上的得分将按照下表计算：

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


title: [TJOI2013] 单词

description: 小张最近在忙毕设,所以一直在读论文。一篇论文是由许多单词组成但小张发现一个单词会在论文中出现很多次，他想知道每个单词分别在论文中出现了多少次。

inputFormat:
第一行一个整数 $N$，表示有 $N$ 个单词。

接下来 $N$ 行每行一个单词,每个单词都由小写字母 $a-z$ 组成。

outputFormat: 输出 $N$ 个整数,第 $i$ 行的数表示第 $i$ 个单词在文章中出现了多少次。

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

- $30\%$ 的数据， 单词总长度不超过 $10^3$。
- $100\%$ 的数据，$1 \leq n \leq 200$，单词总长度不超过 $10^6$。


title: [TJOI2009] 战争游戏

background: 小R正在玩一个战争游戏。游戏地图是一个M行N列的矩阵，每个格子可能是障碍物，也可能是空地，在游戏开始时有若干支敌军分散在不同的空地格子中。每支敌军都可以从当前所在的格子移动到四个相邻的格子之一，但是不能移动到包含障碍物的格子。如果敌军移动出了地图的边界，那么战争就失败了。

description: 现在你的任务是，在敌军开始移动前，通过飞机轰炸使得某些原本是空地的格子变得不可通行，这样就有可能阻止敌军移出地图边界（出于某种特殊的考虑，你不能直接轰炸敌军所在的格子）。由于地形不同的原因，把每个空地格子轰炸成不可通行所需的炸药数目可能是不同的，你需要计算出要阻止敌军所需的最少的炸药数。

inputFormat:
输入文件的第一行包含两个数M和N，分别表示矩阵的长和宽。接下来M行，每行包含用空格隔开的N个数字，每个数字表示一个格子的情况：若数字为-1，表示这个格子是障碍物；若数字为0，表示这个格子里有一支敌军；若数字为一个正数x，表示这个格子是空地，且把它轰炸成不可通行所需的炸药数为x。

地图上的敌军数量不为1，及地图上有多个0

outputFormat: 输出一个数字，表示所需的最少炸药数。数据保证有解存在。

hint:
对50%的数据，1 ≤ M,N ≤ 10

对100%的数据，1 ≤ M,N ≤ 30

矩阵里的每个数不超过100


title: [TJOI2009] 开关

description:
现有 $n$ 盏灯排成一排，从左到右依次编号为：$1$，$2$，……，$n$。然后依次执行 $m$ 项操作。

操作分为两种：

1. 指定一个区间 $[a,b]$，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开）；
2. 指定一个区间 $[a,b]$，要求你输出这个区间内有多少盏灯是打开的。

**灯在初始时都是关着的。**

inputFormat:
第一行有两个整数 $n$ 和 $m$，分别表示灯的数目和操作的数目。

接下来有 $m$ 行，每行有三个整数，依次为：$c$、$a$、$b$。其中 $c$ 表示操作的种类。

- 当 $c$ 的值为 $0$ 时，表示是第一种操作。
- 当 $c$ 的值为 $1$ 时，表示是第二种操作。

$a$ 和 $b$ 则分别表示了操作区间的左右边界。

outputFormat: 每当遇到第二种操作时，输出一行，包含一个整数，表示此时在查询的区间中打开的灯的数目。

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

对于全部的测试点，保证 $2\le n\le 10^5$，$1\le m\le 10^5$，$1\le a,b\le n$，$c\in\{0,1\}$。


title: 【模板】ST 表 && RMQ 问题

background:
这是一道 ST 表经典题——静态区间最大值

**请注意最大数据时限只有 0.8s，数据强度不低，请务必保证你的每次查询复杂度为 $O(1)$。若使用更高时间复杂度算法不保证能通过。**

如果您认为您的代码时间复杂度正确但是 TLE，可以尝试使用快速读入：

```cpp
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
```

函数返回值为读入的第一个整数。

**快速读入作用仅为加快读入，并非强制使用。**

description: 给定一个长度为 $N$ 的数列，和 $ M $ 次询问，求出每一次询问的区间内数字的最大值。

inputFormat:
第一行包含两个整数 $N,M$，分别表示数列的长度和询问的个数。

第二行包含 $N$ 个整数（记为 $a_i$），依次表示数列的第 $i$ 项。

接下来 $M$ 行，每行包含两个整数 $l_i,r_i$，表示查询的区间为 $[l_i,r_i]$。

outputFormat: 输出包含 $M$ 行，每行一个整数，依次表示每一次询问的结果。


title: [TJOI2009] 排列计数

description:
我们知道，1,2,...,N这个N个数的排列共有N!种情况。现在你的任务是，求出在这N!种排列中，任意相邻两数之差不超过K的排列共有多少个。

因为结果可能很大，你只需输出结果对1000000007取模后的值即可。

inputFormat: 输入文件只有一行，包含用空格隔开的两个数：N, K

outputFormat: 输出满足要求的排列个数对1000000007取模后的结果。

hint:
在30%的数据中，N ≤ 12

在100%的数据中，N ≤ 50，K ≤ 4

每个测试点时限10秒


title: [TJOI2009] 猜数字

description:
现有两组数字，每组 $k$ 个。

第一组中的数字分别用 $a_1,a_2,\cdots ,a_k$ 表示，第二组中的数字分别用 $b_1,b_2,\cdots ,b_k$ 表示。

其中第二组中的数字是两两互素的。求最小的 $n\in \mathbb{N}$，满足对于 $\forall i\in [1,k]$，有 $b_i | (n-a_i)$。

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

第二行 $k$ 个整数，表示：$a_1,a_2,\cdots ,a_k$。

第三行 $k$ 个整数，表示：$b_1,b_2,\cdots ,b_k$。

outputFormat: 输出一行一个整数，为所求的答案 $n$。

hint:
对于 $100\%$ 的数据：

$1\le k \le 10$，$|a_i|\le 10^9$，$1\le b_i\le 6\times 10^3$，$\prod_{i=1}^k b_i\le 10^{18}$。

每个测试点时限 $1$ 秒。

注意：对于 ```C/C++``` 语言，对 $64$ 位整型数应声明为 ```long long```。

若使用 ```scanf```，```printf``` 函数（以及 ```fscanf```，```fprintf``` 等），应采用 ```%lld``` 标识符。

tags: 扩展欧几里德算法,exgcd


title: [TJOI2009] 宝藏

description:
为了寻找传说中的宝藏，小明走进了一个迷宫，我们用一个 $r$ 行 $c$ 列的矩阵来描述这个迷宫，矩阵的每个位置表示一个方块区域：

- 字符 `.` 表示可以通过的方格。
- 字符 `#` 表示不能通过的方格。
- 在迷宫中有 $k$ 个机关，第 $i$ 个机关工作方式为：
  - 每当小明走上第 $r_i$ 行，$c_i$ 列的格子时，位于第 $R_i$ 行，$C_i$ 列的格子改变状态（如果这个格子此时可以通过，此后就变为不能通过；如果此时不能通过，此后可以通过。最左上角的格子是第 $1$ 行第 $1$ 列）。

现给出当前小明的位置，宝藏的位置，迷宫中每个格子的状态，以及所有机关的描述，问小明至少还要走多少步才能拿到宝藏（不能走出迷宫的边界，在开始时刻，小明和宝藏所在的位置都是可以通过的，机关不会出现在起点和终点，也不会影响这两个格子）。

inputFormat:
输入数据的第 $1$ 行是两个整数：$r$ 和 $c$。

输入数据的第 $2$ 行到第 $r+1$ 行，每行是一个长度为 $c$ 的字符串，描述迷宫的当前状态：`.` 表示此时可以通过的格子，`#` 表示此时不能通过的格子，`S` 表示起点，`T` 表示宝藏的位置。

输入数据的第 $r+2$ 行是一个整数 $k$，表示机关的数目。接下来有 $k$ 行，每一行包含 $4$ 个整数 $r_i,c_i,R_i,C_i$，用来描述一个机关。

outputFormat: 输出一个整数：小明最少需要走多少步才能拿到宝藏。测试数据保证可以找到宝藏。

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

对于全部数据，$5 \le r, c \le 30$，$0 \le k \le 10$，$1 \le r_i,R_i\le r$，$1 \le c_i,C_i \le c$。


title: [TJOI2010] 中位数

description:
给定一个由 $N$ 个元素组成的整数序列，现在有两种操作：

- $\texttt{1 add }\textit{a}$：在该序列的最后添加一个整数 $a$，组成长度为 $N + 1$ 的整数序列。
- $\texttt{2 mid}$：输出当前序列的中位数。

中位数是指将一个序列按照从小到大排序后处在中间位置的数。（若序列长度为偶数，则指处在中间位置的两个数中较小的那个）

例 $1$：$[1, 2, 13, 14, 15, 16]$ 中位数为 $13$。
例 $2$：$[1, 3, 5, 7, 10, 11, 17]$ 中位数为 $7$。
例 $3$：$[1, 1, 1, 2, 3]$ 中位数为 $1$。

inputFormat: 第一行为初始序列长度 $N$。第二行为 $N$ 个整数，表示整数序列，数字之间用空格分隔。第三行为操作数 $M$，即要进行 $M$ 次操作。下面为 $M$ 行，每行输入格式如题意所述。

outputFormat: 对于每个 $\verb!mid!$ 操作输出中位数的值。


title: [TJOI2010] 电影迷

description:
小A是一个电影迷，他收集了上百部的电影，打算从中挑出若干部在假期看完。他根据自己的口味和网上的介绍，对每部电影X都打了一个分数vX，表示自己喜欢的程度。这个分数的范围在-1000至1000之间，越大表示越喜欢。小A每看一部电影X，他的体验值就会加上vX。

另外，因为某些电影是组成一个系列的，比如著名的《终结者》系列、《黑客帝国》系列等等，如果小A只看了前一部而没有看后一部的话，他就会觉得不是很爽。准确来讲，对于任意两部不同的电影X,Y，他们可能存在一个依赖值dXY，表示如果小A看了X但是没看Y，他的体验值就会减少dXY。（注意与观看的顺序无关，只要两部都看过，就不会减少体验值）

现在他要选出若干电影来看，使得得到的总的体验值最大。如果他无法得到正的体验值，就输出0。

inputFormat: 输入的第一行是两个整数：电影总数N和依赖关系数目M。第二行包含用空格隔开的N个数，表示对每部电影的打分。接下来M行，每行包含三个整数X, Y, dXY，表示一个依赖关系。每个有序对(X,Y)最多出现一次。(1 ≤ X,Y ≤ N)

outputFormat: 输出一个整数，表示小A能得到的最大体验值。

hint:
如果小A只看电影1，体验值为100-49 = 51。如果只看电影2，体验值为-50-10 = -60。如果两部都看，体验值为100+(-50) = 50。所以应该只看电影1。

数据规模与约定

对于20%的数据，1 ≤ N ≤ 15

对于100%的数据，1 ≤ N ≤ 100, -1000 ≤ vX ≤ 1000, 0 < dXY ≤ 1000

每个测试点时限1秒


title: [TJOI2010] 天气预报

description: A 公司的天气预报系统的原理如下：用一个大于等于 $0$，小于等于 $4146$ 的整数来表示这一天的天气情况，在预测未来某一天的天气情况时，要根据此前 $n$ 天的天气情况来预测，如果用 $w_i$ 表示第 $i$ 天的天气情况（$i>n$），那么 $w_i=(a_1\times w_{i-1}+a_2\times w_{i-2}+\cdots+a_{n}\times w_{i-n})\mod4147$，其中 $a_1,a_2,\cdots ,a_n$ 是已知常数。现给出前 $n$ 天的天气情况，问第 $m$ 天的天气预测结果是什么。

inputFormat: 输入数据的第一行是两个正整数 $n$ 和 $m$，第二行有 $n$ 个非负整数，分别为 $w_n,w_{n-1},\cdots,w_1$。第三行又有 $n$ 个非负整数，分别表示 $a_1,a_2,\ldots,a_n$。

outputFormat: 输出一个整数，表示对第 $m$ 天的天气预测结果。


title: [TJOI2010] 砍树

background: 小 A 在果园里发现了一棵结满果子的树，于是他就打起了坏主意，他打算把树的一部分砍下来带回家。

description: 我们可以把这棵树表示成一个树型的结构，也就是说，任意两个点之间有且仅有一条路径。在每个点 $i$ 处都结着一个水果，每个水果有一个价值 $v_i$ 和重量 $w_i$。小 A 想带走树的一部分（或全部），包含至少 $K$ 个结点（也就是至少 $K$ 个水果），且这些水果的平均价值尽可能高。平均价值是指水果总的价值除以总的重量。注意小 A 砍下的树必须是在原来的树中连通的一部分。

inputFormat:
第一行包含两个数 $N$ 和 $K$，分别表示树的结点数和小 A 至少应带走的水果数。

第二行包含空格隔开的 $N$ 个数，分别表示每个结点处水果的价值 $v_i$。

第三行包含空格隔开的 $N$ 个数，分别表示每个水果的重量 $w_i$。

按下来 $N-1$ 行，每行包含两个数 $a_i$ 和 $b_i$（$1 \le a_i,b_i \le N$），表示在结点 $a_i$ 和 $b_i$ 之间有一条边。输入保证是一棵正确的树结构。

outputFormat: 输出一行，包含一个数，表示最大可能的平均价值。四舍五入到小数点后两位。


title: [TJOI2010] 被污染的河流

background: 有一座城市，城市里有许多条人工河，河流的流向都是水平或者竖直的。为了方便市民用水，政府将河流设计成网格状。在水平方向上和竖直方向上，相邻河流的距离都是 $1$ 公里。河流围出许多格子，每个格子就是一个社区，社区里的居民可以到社区周边四条河段中的任意一处打水喝。

description:
郁闷的是，不久之后，有些不法商人修建了工厂，污染了河流。河边许多居民喝了被污染的水，生病了。政府派出专员小强调查污染情况。地理专家小强行动迅速，很快给出了污染分布。他给出了一张污染清单。清单列出了被污染的河段，所有能喝到该河段水的居民都有可能生病（河段的端点处忽略不计）。但是，笨笨的小强怎么也算不出具体会有多少个社区的居民会生病，所以，他请你来帮帮忙。

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

inputFormat:
输入文件的第一行是一个整数 $N$，表示被污染的河段的数目。

接下来 $N$ 行，每行 $4$ 个整数 $x_1,y_1,x_2,y_2$，表示被污染河段的起始位置和结束位置。每行输入的两个位置保证不重合，并且满足 $x_1=x_2$ 或 $y_1=y_2$。

outputFormat: 输出一个整数 $A$，表示有 $A$ 个社区的居民会喝到被污染的水。


title: [TJOI2010] 数字序列

description:
考虑一个由数字0,1,2,3组成的长度为n的序列，如果它是一个合法序列，那么它应当满足以下两个条件：

1) 序列中任意相邻的两元素没有出现模式{'00', '11', '22', '33', '02', '20', '23', '32', '13', '31'}中的任一种;

2) 序列满足m个约束条件，每个约束条件的形式均为：{p1, p2, ... pL}，它表示序列中的p1, p2, ..., pL这些位置的值不同。例如约束条件{1, 5, 11}表示序列中的第一个，第五个和第十一个元素两两各不相同。

现在已知序列长度n，约束条件个数m以及这m个约束条件，问是否存在这样的合法序列。

inputFormat: 输入文件的第一行是一个正整数T，表示文件中包含T组测试数据。从文件的第二行开始，将依次给出所有的测试数据。每个测试数据的第一行是两个整数n和m，它们的涵义如上面题目描述中所示。接下来有m行，每行描述一个约束条件，其中在描述第i个约束条件的行中，第一个数字是表示这个约束条件包含多少个元素的正整数Li，后面由Li个正整数给出第i个约束的具体情况。

outputFormat: 共输出T行，对每组测试数据输出一行，如果存在满足条件的合法序列，输出"Yes"；否则，输出"No"。

hint:
T ≤ 10，1 ≤ n ≤ 100000，0 ≤ m ≤ 5000，1 ≤ Li ≤ 100，1 ≤ pi ≤ n

每个测试点时限1秒

第一组样例中，序列0103012是满足要求的一个合法序列。


title: [TJOI2010] 打扫房间

description:
学校新建了一批宿舍，值日生小A要把所有的空房间都打扫一遍。这些宿舍的布局很奇怪，整个建筑物里所有的房间组成一个N \* M的矩阵，每个房间的东南西北四面墙上都有一个门通向隔壁房间。另外有些房间是堆放杂物的，无需打扫。小A想设计若干条打扫路线，使得恰好进出每个需打扫的房间各一次，而且进出每个房间不能通过同一个门。要求每条路线都是一个闭合的环线，并且每条路线经过的房间数大于2。

如下面两图所示均为满足要求的打扫方案（灰色格子为放杂物的房间）：

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

小A发现对于某些房间布局是不存在这样的满足要求的方案的。他请你写一个程序计算一下，对于一种给定的房间布局，满足要求的方案是否存在。

inputFormat: 输入文件的第一行是一个整数T (1 ≤ T ≤ 10)，表示该文件中一共有T组数据。接下来依次是T组数据的信息。每组数据的第一行包含两个整数N和M，接下来的N行，每行包含M个字符，表示一个房间布局。字符'.'表示该房间需要打扫，'#'表示该房间是堆放杂物的，无需打扫。

outputFormat: 共输出T行，对每组数据输出一行，为"YES"或"NO"，表示打扫方案存在与否。

hint:
对50%的数据，3 ≤ N,M ≤ 12

对100%的数据，3 ≤ N,M ≤ 30

每个测试点时限1秒


title: [TJOI2010] 分金币

description:
现在有 $n$ 枚金币，它们可能会有不同的价值，第 $i$ 枚金币的价值为 $v_i$。

现在要把它们分成两部分，要求这两部分金币数目之差不超过 $1$，问这样分成的两部分金币的价值之差最小是多少？

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

输入的第一行是一个正整数 $T$，表示该测试点内数据组数。

对于每组测试数据的格式为：

每组测试数据占两行。

第一行是一个整数 $n$，表示金币的个数。

第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个金币的价值 $v_i$。

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

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

- 对 $30\%$ 的数据，保证 $1 \leq v_i \leq 1000$
- 对于 $100\%$ 的数据，保证 $1 \leq T \leq 20$，$1 \leq n \leq 30$，$1 \leq v_i \leq 2^{30}$。


title: [TJOI2010] 阅读理解

description: 英语老师留了 $N$ 篇阅读理解作业，但是每篇英文短文都有很多生词需要查字典，为了节约时间，现在要做个统计，算一算某些生词都在哪几篇短文中出现过。

inputFormat:
第一行为整数 $N$ ，表示短文篇数，其中每篇短文只含空格和小写字母。

按下来的 $N$ 行，每行描述一篇短文。每行的开头是一个整数 $L$ ，表示这篇短文由 $L$ 个单词组成。接下来是 $L$ 个单词，单词之间用一个空格分隔。

然后为一个整数 $M$ ，表示要做几次询问。后面有 $M$ 行，每行表示一个要统计的生词。

outputFormat: 对于每个生词输出一行，统计其在哪几篇短文中出现过，并按从小到大输出短文的序号，序号不应有重复，序号之间用一个空格隔开（注意第一个序号的前面和最后一个序号的后面不应有空格）。如果该单词一直没出现过，则输出一个空行。

samples:
3
9 you are a good boy ha ha o yeah
13 o my god you like bleach naruto one piece and so do i
11 but i do not think you will get all the points
5
you
i
o
all
naruto

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

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

每篇短文长度（含相邻单词之间的空格）$\le 5\times 10^3$ 字符，每个单词长度 $\le 20$ 字符。

每个测试点时限 $2$ 秒。

感谢@钟梓俊添加的一组数据。


title: [JLOI2008] 提示问题

description:
最近在 JLOI 网上的一个流行游戏中，选手要回答很难的问题。假如在规定时间内不能回答，系统将给出 $1$ 个提示，之后再依次给出第 $2,3$ 个提示。出现在答案中的是字母和下列字符：

$\verb|. , : ; ! ? - |$ 和空格（空格不会在开头和结尾出现）。

字母是指：小写字母 $\verb!a! \cdots \verb!z!$ 大写字母 $\verb!A! \cdots \verb!Z!$，其中 a e i o u A E I O U 是元音字母。

生成提示的规则：

- 第 $1$ 个提示：简单的将所有字母换成 $\verb!.!$ 即可；
- 第 $2$ 个提示：从第 $1$ 个提示而来，将所有字母的个数求出，再将总个数除以三，得到的最接近商的自然数 $N$，将第 $1$ 个提示中的前 $N$ 个字母显示；
- 第 $3$ 个提示：从第 $2$ 个提示而来，将剩下的元音字母显示。假如没有可显示的元音字母，则从第 $1$ 个提示而来，即我们将前 $2/3$ 的字母显示（同样如不能被 $3$ 整除则取最接近的整数）。

inputFormat: 仅一行，给出问题，问题字符数最多不超过 $50$。

outputFormat: 三行：按规则输出的三行提示。


title: [JLOI2008] CODES

description:
给定n个01编码串S1,S2,…,Sn，你的任务是寻找一个编码串T，使得它至少可以被分解为两种不同的Si的排列。

例如：

给定5个01编码串：S1=0110，S2=00，S3=111，S4=001100，S5=110。那么一个符合要求的编码串T是：001100110，它有以下两种分解方法：

 00+110+0110 (S2+S5+S1) 或 001100+110 (S4+S5)

而0110110就不符合要求，它只有一种分解方法 0110+110 (S1+S5)。

你要寻找长度最短的符合要求的编码串T。若有多个符合要求的最短编码串T，则输出字典顺序最小的。

inputFormat: 输入文件第一行包含一个整数n，n不超过20，表示01编码串总数。接下来的n行每行给出一个长度不超过20的01编码串。

outputFormat: 输出文件共有两行，第一行为要求的编码串T的长度，第二行输出编码串T。对所有的测试数据，问题总有解。


title: [JLOI2008] 将军

description:
刘先生最近在学习国际象棋，使用一个叫 jloi-08 的游戏软件。在这个游戏里，不但可以和电脑普通地对弈，还可以学习著名的棋局，还有针对初学者的规则指导等丰富功能。但是…大小却要 1.4G T\_T。

言归正传，在这个软件里，为了让玩家更好地理解和运用各个棋子，有很多趣味的游戏，比如以下就是一个：

给出一个棋盘和一些棋子，让你把这些棋子摆放在棋盘上，使得两两不互相攻击。你的得分由你摆放上去的棋子的个数与种类有关。

这个游戏很复杂，刘先生老是玩不到高分。于是电脑便降低了难度，替刘先生摆上了一些棋子，最后只给你任意多个 bishop（教主）。

现在刘先生便要考一考你，在电脑给出的这张棋盘上，最多能放几个 bishop。

国际象棋中一共有 6 种棋子：

- king（国王）；
- queen（皇后）；
- bishop（教主）；
- knight（骑士）；
- rook（车）；
- pawn（步兵）。

各棋子的攻击范围如下：

- queen 可以攻击与它在同一行，同一列，同一条对角线的棋子；
- knight 的攻击范围如下图所示：

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

- rook 攻击水平和垂直两条线上的所有格子；
- pawn 攻击前方两条斜线方向各一格(“前方”指 $x$ 递增的方向，$x$ 行 $y$ 列）；
- king 攻击周围 8 个方向各 1 格；
- bishop 攻击两条对角线上的所有格子。

除 knight 以外，所有棋子的攻击范围均会被别的棋子所阻挡。

可惜的是这个软件也不是顶优秀，给出的棋盘上的棋子可能互相会攻击，不过你不用理会这些，你只要保证你摆放的 bishop 不与它们以及不互相攻击就可以了。

inputFormat:
第一行是两个整数 $x,y$（$1 \leq x,y \leq 1024$）。

下面的 $x$ 行每行 $y$ 个字符表示棋盘。

其中：`K` – king，`Q` – queen，`B` – bishop，`N` – knight，`R` – rook，`P` – pawn，`.` – blank.

outputFormat: 仅一行一个数，表示最多能够摆放的 bishop 的个数。

hint:
```plain
BBN
...
...
```

```plain
BBN
...
B..
```

虽然看上去下面的方法比上面的优秀，但是 N 被第三行的 B 攻击了。也就是说，你需要避免的有 2 种情况： 你摆放的 bishop 之间的互相攻击以及你摆放的 bishop 与预先摆放好的棋子之间的互相攻击；但不用考虑预先摆放好的棋子之间的互相攻击。


title: [JLOI2008] 棋局定式

description:
在“jloi-08”游戏中，还存有非常非常多的棋局定式，也就是常会用到的下棋的组合。有时在学习一个著名棋局时，电脑会考一考刘先生：在这局棋里面，有多少个定式啊？分别是什么啊？

对于30~40步的普通棋局，刘先生还能回答出来，可是有时候2个实力相当的大牛下的棋局，2000000步都有可能。如果电脑对这样的棋局提上面的问题时，刘先生就必须写一个程序来帮助自己了。可是，刘先生在这方面却…，怎么写也写不对。你能帮助刘先生吗？

棋局是由很多step组成的，而step是由一个字符串组成的，比如Kh2或者是Nxb7。

前者表示K(king)移动至h2格，后者表示N(knight)移动至b7格并吃掉原有的棋子。

第一个字符可能有6种：K Q B N R P，而后面可能是一个坐标或者是字符x后跟一个坐标。

坐标是由一个小写英文字母(a~h)和一个数字(1~8)组成的。

如果一个棋局中完整地并连续地包含一个定式中所有的step，那么这个棋局便包含这个定式。

inputFormat:
第一行2个整数n, m，表示定式的个数(1<=n<=2000)以及这个棋局所包含的步数

下面的n个块(block)，每块包含：

第一行一个整数k表示定式包含的步数(1<=k<=100000, ∑k<=200000)

第二行一个字符串表示该定式的名称(长度不超过50)

下面的k行每行一个字符串表示定式中的一步

最后的m行每行一个字符串，表示棋局中的一步

outputFormat: 按照输入文件包含的定式的顺序，输出棋局包含的所有定式的名称，一个一行。

samples:
2 5
3
King's Knight Opening
Pe4
Pe5
Nf3
3
Nimzowitsch Variation
Pc4
Pe5
Nf3
Pe4
Pe5
Nf3
Nc6
Bb5

hint: 不保证给出的棋局和定式符合国际象棋的规则。


title: [JLOI2009] 二叉树问题

description:
如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：

- 深度：$4$
- 宽度：$4$
- 结点 8 和 6 之间的距离：$8$
- 结点 7 和 6 之间的距离：$3$

其中宽度表示二叉树上同一层最多的结点个数，节点 $u, v$ 之间的距离表示从 $u$ 到 $v$ 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。

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

给定一颗以 1 号结点为根的二叉树，请求出其深度、宽度和两个指定节点 $x, y$ 之间的距离。

inputFormat:
第一行是一个整数，表示树的结点个数 $n$。
接下来 $n - 1$ 行，每行两个整数 $u, v$，表示树上存在一条连接 $u, v$ 的边。
最后一行有两个整数 $x, y$，表示求 $x, y$ 之间的距离。

outputFormat: 输出三行，每行一个整数，依次表示二叉树的深度、宽度和 $x, y$ 之间的距离。

hint: 对于全部的测试点，保证 $1 \leq u, v, x, y \leq n \leq 100$，且给出的是一棵树。保证 $u$ 是 $v$ 的父结点。


title: [JLOI2009] F1一级方程式大赛

background: 众所周知，迈克尔·舒马赫 (Michael  Schumacher) 是当今车坛最伟大的王者，从 1991 年至 2006 年他一共参加了 260 多场比赛，获得近 100 次分站冠军，9 次年度冠军。舒马赫取得如此辉煌的战绩得益于他有一个非常优秀的智囊团。每次比赛之前他的智囊团将根据场地、气候、路况以及赛车状态，来为舒马赫制定比赛中的策略。

description:
我们知道，在 F1 大赛中，如果赛车的其他参数都相同，赛车的速度主要取决于其载油量。载油太多就会降低赛车的速度，也会增加汽油的消耗速度；但载油太少就需要在比赛中增加进站加油的次数。因此智囊团的一个关键任务就是在每次比赛前确定舒马赫的初始载油量以及进站加油的方案，使得舒马赫完成所有赛程的总时间尽量短。

作为智囊团的首席程序员刘博士，交给他的团队的任务是编写一个程序，为舒马赫确定比赛开始前的载油量以及比赛中进站加油的方案。

inputFormat:
输入数据包括以下 $1$ 个数：

- 比赛的总圈数（一个不超过 $1$ 的正整数）

- 理论上，没有油的空车跑一圈所需的时间（浮点数，单位为秒）

- 每增加 $1$ 公升汽油，赛车跑一圈所增加的时间（浮点数，单位为秒）

- 理论上，没有油的空车跑一圈所消耗的油量（浮点数，单位为公升）

- 每增加 $1$ 公升汽油，赛车跑一圈所增加的油量损耗（浮点数，单位为公升，且这个数严格小于 $1$）

- 每次进站所需花费的时间（浮点数，单位为秒，这个时间不包括加油所需花费的时间，加油所花费的时间由下一个输入参数决定）

- 每次进站后，每加 $1$ 公升汽油，所需花费的时间（浮点数，单位为秒）

我们总是把一整圈看作一个单位。赛车在跑一圈的过程中，汽油的变化量不做考虑。加油总是在一整圈跑完以后才可以进行。

outputFormat:
- 第一行包括三个数：

 1. 舒马赫的赛车跑完所有赛程所需的最短时间（浮点数，保留小数点后三位）；
 2. 舒马赫的赛车在比赛开始前的载油量（浮点数，保留小数点后三位）；
 3. 舒马赫在比赛过程中进站加油的次数 $m$（整数）；

- 接下来是 $m$ 行，每行包括两个数：

 1. 第 $i$ 次进站加油时已经完成的圈数（整数）；
 2. 第 $i$ 次进站加油所加的油量（浮点数，保留小数点后三位）；


title: [JLOI2009] 神秘的生物

description:
3206年5月，正在钻研ET专业的刘博士所在的OI团队发现：地球受到了来自外星球的生物人的侵袭。这些生物人采取了极秘的乘法加密电文，控制了具有大量武器的军火库，攻占了大量的城市，甚至出现了K弹计划……

刘博士所在的OI团队决定要发挥他们的科研机构作用（由于吉林省所在的地理位置具有特殊的优势，此科研机构全球只有吉林一处），以制伏这些外星球的生物人。他们想方设法捕获了几个外星球的生物人，经研究后发现，这些外星球的生物人在地球上的生存，取决于一个参数：生存度。他们要做的就是：找到这个参数的最大值！于是，他们开始了对这些外星球的生物人生长的研究。

每次实验前，他们把一个外星球生物人的细胞随机地放在一个N\*N的方形培养容器的一格中，并给容器的每个格子都标了一个数值，是生物在此单元的生存度（可正可负，数值越大表示越危险）。整个生物的生存度是生物所有占据格子的生存度之和。每次实验开始后，让生物自然生长。这个生物每一单位时间都选择其身体的一部分（某个格子），随机地向与之有公共边的空格生长，例如某次实验，一开始生物只占据一个格子，然后开始了生长：

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

刘博士所在的OI团队做了大量的实验，并且对数据进行了记录和统计。假设进行的实验次数足够多，问在实验进行的某一时刻，该生物达到的最大生存度是多少？

3206年9月，妄图破坏地球的外星球生物人终于被刘博士所在的OI团队制伏了……

inputFormat:
输入文件第一行包括一个正整数N，代表实验容器的边长。

接下来N行，每行N个用空格隔开的整数，代表外星球生物人在每一格的生存度。

outputFormat: 输出一行，代表实验过程中，生物达到的最大生存度。

hint:
对于40%的数据有N <= 6。

对于100%的数据有N <= 9。

所有数据每个格子生存度的绝对值不超过32767。


title: [GDOI2014] 世界杯

description:
3014 年世界杯足球赛就要开始了！作为卫冕冠军中国足球队的教练，手下每位球员都是猛将，如何摆出最强的 11 人阵容也是一件幸福的烦恼事啊。

众所周知，足球阵容里的11个球员都会被分配到场上某一个特别的位置，而这些位置主要分为守门员、后卫、中场和前锋四种，其中守门员有且只有一个，后卫、中场和前锋的人数取决于你安排的足球阵型。形容足球阵型的方法由后卫开始计算至前锋，但不把守门员计算在内。例如，3-5-2 阵型是指有三个后卫、五个中场及两名前锋。由于竞争激烈，每位球员只会培养其中一种位置所需要的技能，所以他们每个人都只能胜任四个位置中的其中一种。

作为一个对球员能力了如指掌的教练，你给每个球员的综合水平进行量化。为了将阵型安排得更好，你的教练团队决定使用以下策略安排球员：首先按照顺序提出 $Q$ 个阵型，分别代表第一阵型、第二阵型、……、第 $Q$ 阵型。然后对于每个阵型，从仍未选择的球员中选择最好的对应数量的守门员、后卫、中场和前锋。比如说，对于第一阵型，在所有球员中选择；对于第二阵型，在除了第一阵型外的所有球员中选择；对于第三阵型，在除了第一阵型和第二阵型外的所有球员中选择；以此类推。

现在 $Q$ 个阵型都已经确定，而你需要知道的，是每个阵型的平均综合水平分别是多少。

inputFormat:
第一行有四个整数 $K, D, M, F$，分别表示守门员、后卫、中场和前锋供挑选的球员人数。

第二行有 $K$ 个整数 $k_i$，分别表示每个守门员的综合水平值。

第三行有 $D$ 个整数 $d_i$，分别表示每个后卫的综合水平值。

第四行有 $M$ 个整数 $m_i$，分别表示每个中场的综合水平值。

第五行有 $F$ 个整数 $f_i$，分别表示每个前锋的综合水平值。

第六行有一个整数 $Q$，表示教练团队提出的阵型个数。

以下 $Q$ 行，第 $i$ 行三个整数 $A_i, B_i, C_i$，由空格间隔，表示第 $i$ 阵型是 $A_i - B_i - C_i$ 阵型。

outputFormat: 输出 $Q$ 行。对于第 $i$ 种阵型，输出一个实数，表示该阵型平均综合水平的最大值，并四舍五入到小数点后 $2$ 位。


title: [GDOI2014] 拯救莫莉斯

description:
莫莉斯·乔是圣域里一个叱咤风云的人物，他凭借着自身超强的经济头脑，牢牢控制了圣域的石油市场。

圣域的地图可以看成是一个 $n\times m$ 的矩阵。每个整数坐标点 $(x, y)$ 表示一座城市（$1\le x\le n,1\le y\le m$）。两座城市间相邻的定义为：对于城市 $(A_x, A_y)$ 和城市 $(B_x, B_y)$，满足 $(A_x - B_x)^2 + (A_y - B_y)^2 = 1$。

由于圣域的石油贸易总量很大，莫莉斯意识到不能让每笔石油订购单都从同一个油库里发货。为了提高效率，莫莉斯·乔决定在其中一些城市里建造油库，最终使得每一个城市 $X$ 都满足下列条件之一：

1. 该城市 $X$ 内建有油库.
2. 某城市 $Y$ 内建有油库，且城市 $X$ 与城市 $Y$ 相邻。

与地球类似，圣域里不同城市间的地价可能也会有所不同，所以莫莉斯想让完成目标的总花费尽可能少。如果存在多组方案，为了方便管理，莫莉斯会选择建造较少的油库个数。

inputFormat:
第一行两个正整数 $n,m$（$n \times m \le 50$ 且 $m\le n$），表示矩阵的大小。

接下来一个 $n$ 行 $m$ 列的矩阵 $F$，$F_{i, j}$表示在城市 $(i,j)$ 建造油库的代价。

outputFormat: 输出两个数，建造方案的油库个数和方案的总代价。

hint:
对于 $30\%$ 数据满足 $n \times m \le 25$;
对于 $100\%$ 数据满足 $n \times m \le 50,0 \le F_{i, j} \le 10 ^ 5$。


title: [GDOI2014] 吃

background: 感谢 @FFjet 提醒，第 8 个数据点损坏暂时删除。

description:
W师兄计划了很久，终于成功的在BG开了一家寿司店。

正当W师兄还在兴奋的时候，这时一个噩耗传来，吃货L师姐居然知道了这件事，而且正赶过来，W师兄瞬间心就冷了下去，但是机智的W师兄也瞬间想到了应付L师姐的策略.......

这时，L师姐到了寿司店，先四处望了望风景，发现现在只有L师姐一个顾客，下面是L师姐的选餐说明：

1.寿司店内的寿司被排在一行共N个盘子里，按从左到右编号为1~N。

2.每个位置上寿司的数量是确定的并且有玻璃窗保护。

3.每隔一段时间就会有一个选餐时间，L师姐可以在一个连续的区间[l, r]中选择其中一盘，然后在该区间之外选择另一盘（如果区间外有盘子）。

L师姐发现这家寿司店厨师的制作速度很快，总能在下一次选餐时间前将寿司数量恢复原样。

作为有尊严有追求的吃货，L师姐也有自己的规则，L师姐在选完两盘寿司后，会决定每口恰好吃D个寿司，且使得两盘寿司刚好可以分别吃完，不剩余任何寿司。比如两盘寿司数量为2和4,那么D=1或者D=2都可以恰好将两盘寿司分别吃干净，而两盘寿司数量为3和5时，那么只能D=1才行。

作为有特殊追求的L师姐才不在乎吃的数量，L师姐在乎的是一口吃多个寿司的感觉。于是，如果L师姐可以一口吃D个寿司，那么L师姐的愉悦值为D，但是L师姐没有选到两盘寿司，那么她的愉悦值为0。

现在L师姐知道每个盘子所放着的寿司数量，L师姐想知道每次选择时间过后她可以获得的最大愉悦值是多少？

inputFormat:
第一行输入一个整数N，表示寿司的盘子数量。

第二行输入N个整数a1,a2,…,aN，ai表示第i个盘子内的寿司数量。

第三行输入一个整数M，表示有多少个选餐时间。

接下来M行，每行两个整数li, ri (1 <= li <= ri <= N)，含义如题面所示。

outputFormat: 输出M行，第i行表示第i个选择时间师姐可能达到的最大愉悦值D。

hint:
###样例解释

样例1里的第一个选餐时间，可以选择2和4，这样L师姐就可以每次吃两个寿司，使得两个盘子都可以吃干净，第二个选餐时间，师姐不管选哪两个盘子，都只能每次吃一个。

样例2 里的第一个选餐时间，可以选择16和32,而第二个选餐时间，L师姐可以选择8和16或者8和32。

对于20%的数据，N <= 100, M <= 100, max(a1,a2,…,aN) <= 100。

对于50%的数据，N <= 10000, M <= 10000, max(a1,a2,…,aN) <= 10000。

对于100%的数据，N <= 100000, M <= 100000, max(a1,a2,…,aN) <= 100000。


title: [GDOI2014] 比特矩阵

background:
你知道矩阵乘法吗？

对于两个 $n\times n$ 的矩阵 A 和 B， 假设 $a_{i, j}$ 表示位于矩阵 A 的第 $i$ 行第 $j$ 列的元素， 同样对于B可以定义类似的 $b_{i,j}$。 那么如果 $C = A \times B$，则有 $c_{i, j}=\sum_{k=1}^{n} a_{ik} \times b_{kj}$。 其中 $ \sum$ 是序列求和符号，例如 $\sum_{i=1}^{n} i$ 表示 $1 + 2 + \cdots + n$。

description:
由于霍比特人的大热， L 的室友 X 最近热衷于研究它们所使用的货币。为了进行研究，X 需要了解一种叫比特矩阵的东西。 虽然比特矩阵也是矩阵，但是它的乘法和一般的矩阵有点不一样。

对于比特矩阵 $C = A \times B$， 意味着 $c_{i,j} = V_{k=1}^{n}a_{ik} \bigoplus b_{kj}$。其中 $V$ 是序列求按位或的符号，例如 $V_{i=1}^{n} i$ 表示 $1 \mid 2 \mid \cdots \mid n$。 $\mid$ 就是按位或的意思。 按位或是指从二进制的角度看两个数， 如果第 $i$ 位上两个数至少一个是1的话那结果的第 $i$ 位就是1， 否则第 $i$ 位就是 $0$。 $\bigoplus$ 表示按位异或运算， 即如果两个二进制数的第$i$位是不相同的话那么结果的第 $i$ 位就是 $1$，否则就是 $0$。

举个比特矩阵相乘的例子:

$$\begin{bmatrix}1&6\\3&5\end{bmatrix}\times\begin{bmatrix}3&6\\5&7\end{bmatrix}=\begin{bmatrix}3&7\\0&7\end{bmatrix}$$

现在 X 想要拜托你帮他算 $A^{m}$，其中 $A$ 是一个 $n\times n$ 的比特矩阵， 而 $A^{m}$ 表示 $m$ 个 $ A$ 相乘的结果。严谨地说:

- $A^{1}=A$；
- $A^{m}=A^{m-1}\times A,\ m>1$。

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

接下来 $n$ 行，每行包含 $n$ 个非负整数，这 $n$ 行中第 $i$ 行的第 $j$ 个数表示比特矩阵 $a_{i,j}$ 的元素 。

outputFormat: 根据输入，输出一个比特矩阵 $A^{m}$。即按照输入给出 $A$ 的方式输出一个比特矩阵。 具体参看样例输出。


title: [GDOI2014] 采集资源

description:
魔兽争霸3中，战略资源的采集通过使用农民、苦工、小精灵以及寺僧来进行。

在魔兽争霸4的开发中，玻璃渣觉得这种模式太过单一，于是他们想添加更多的单位来使采集的模式更加丰富。

在新的模式中，玩家可以建造更多种类的“苦工”，不同的“苦工”的工作效率不同，同时，建造不同的“苦工”所需要的资源也是不一样的。

玻璃渣出品的游戏以追求平衡著称，所以为了测试这种新的模式的平衡性，他们设计了一套检测的方法：在各种族的起始资源相同时，测量达到某一资源数量的时间，如果相同则可以认为设计是平衡的。

他们将数据给你，希望你能测试出设计是否平衡。

inputFormat:
第一行三个数，N, M, T, 表示苦工的种类、开始时拥有的资源数量以及需要达到的资源的数量。

接下来N行，每行2个数A, B, 表示生产这种苦工所需要的资源，以及这个苦工的效率，效率即为单位时间内产生的资源的数量。

outputFormat:
一个数字，表示资源数量达到T时的最少时间。

注意：与魔兽争霸3不同，魔兽争霸4中，生产苦工不需要时间。并且资源的采集并不连续，亦即如果一个苦工的效率为2，他会在时间为1的时候收获2点资源，而并不会在时间为0.5的时候收获1点资源。


title: [GDOI2014] OJ

description:
小 M 是一个勤奋的 ACMer，他利用课余时间刷了很多题目。但他是个很健忘的孩子，经常会忘记自己刷过一些什么题目，所以他想写一个 OJ 来管理自己做过的题目。

经过一个星期的努力，小 M 的 OJ 基本成型，只是还差一个 Contest 的模块没有实现。小 M 觉得这个模块很难实现，所以他希望找你来帮忙。

小 M 告诉你，一个 OJ 的基础元素包括：

1. 题目，可以用 pid 唯一标识，pid 为正整数；
2. 比赛，可以用 cid 唯一标识，cid 为正整数；
3. 用户，可以用 uid 唯一标识，uid 为正整数；
4. 提交状态，可以由 sid 唯一标识，sid 为正整数。

一个提交状态是由 sid、cid、pid、uid 和 result 组成的，分别表示本条状态的提交 ID，所属比赛 ID，题目 ID，用户 ID 以及评测结果。

简单起见，这里的 result 只有 AC、UNAC 和 WAIT 三种状态，分别表示通过、不通过和等待评测。

同时小 M 提出一个比赛模块需要实现以下请求：

1. `createContest cid t pid_1 pid_2 … pid_t`

表示要创建一个比赛，cid 是一个正整数，是这场比赛的唯一标识。

$t$ 表示这场比赛有 $t$（($1\le t\le1000$)）道题目，接下来 $t$ 个不同的整数，表示这场比赛的题目编号。

2. `submission sid cid pid uid result`

该条状态的 sid 要么之前没出现过，要么以前出现过，但是被 rejudge 了。

result 为 AC 或者 UNAC。

3. `getRank cid uid`

在一场比赛中，所有有提交的用户都应该算在排名内（包括被 rejudge 的提交），用户的排名按照通过的题目数从大到小排序，如果题目数相同，则按随机顺序排序。

该指令需要统计用户 uid 在 cid 这场比赛中的通过目数，最高排名以及最低排名。

值得注意的是，用户 uid 在 cid 这场比赛中同一道题目的多个通过记录只算一次。

输出格式为：`uid solved highest lowest`。

分别代表用户 ID，通过题目数量，最高排名以及最低排名，其中 $\mathit{highest}\le\mathit{lowest}$。

4. `rejudge sid`

重测以 sid 标识的提交记录，即将该记录的 result 改成 WAIT。

inputFormat:
第一行三个整数 $\mathit{pcnt}$、$\mathit{ucnt}$、$m$（$1\le\mathit{pcnt}\le5000,1\le\mathit{ucnt}\le5000,1\le m\le3\times10^5$），分别表示 OJ 有 pcnt 道题目，ucnt 个用户以及 m 条请求。

pid 的范围是 $1000\sim1000+\mathit{pcnt}-1$，uid 的范围是 $1\sim\mathit{ucnt}$，cid 的范围为 $1\sim50$，$1\le\mathit{sid}\le m$。

接下来有 $m$ 行，每行一个请求，请求为题述四种请求之一，请求需要按输入顺序执行。

你需要注意以下几点：

1. 对于 `createContest` 请求，保证 cid 不会与之前的 createContest 的 cid 重复。
2. 对于 `submission` 请求，在此请求前，保证比赛 cid 已经创建，题目 pid 是该场比赛的题目之一。
3. 对于 `getRank` 指令，在此请求前，保证比赛 cid 已经创建，用户 uid 至少在该比赛中有一个提交记录。
4. 对于 `rejudge` 指令，在此请求前，保证存在以 sid 标识的提交。

outputFormat: 对于每一个 `getRank` 请求，根据要求输出用户 ID，通过题目数量，最高排名以及最低排名，整数之间用一个空格隔开。

samples:
7 5 17
createContest 1 5 1001 1004 1002 1005 1006
submission 1 1 1001 1 AC
submission 2 1 1001 1 AC
submission 3 1 1001 2 UNAC
submission 4 1 1003 3 UNAC
getRank 1 1
getRank 1 2
getRank 1 3
rejudge 3
submission 3 1 1001 2 AC
getRank 1 2
submission 5 1 1006 2 AC
getRank 1 1
submission 6 1 1006 2 UNAC
getRank 1 2
rejudge 5
getRank 1 2

hint:
对于 $20\%$ 的数据，$1\le\mathit{pcnt},\mathit{ucnt},m\le100$；

对于 $50\%$ 的数据，$1\le\mathit{pcnt},\mathit{ucnt}\le2000,1\le m\le50000$；

对于 $100\%$ 的数据，$1\le\mathit{pcnt},\mathit{ucnt}\le5000,1\le m\le3\times10^5,1\le\mathit{cid}\le50$。


title: [GDOI2014] Beyond

description:
Jodie 慢慢地步入实验室，跟随在她身旁的灵体 Aiden 似乎有点不高兴，但还是形影不离地跟随着 Jodie。

今天 Jodie 要进行的实验在一个很大很大的圆环上面，圆环上有 $L$ 个格子，每个格子上都显示着一个小写英文字母，Jodie 从任意格子开始当她离开一个格子的时候那个格子的字母就会改变，这个改变是随机的，没有人知道会变成什么。Jodie 在这个环上不回头顺时针地走，每进入一个格子就会在本子上写下这个格子当前显示的字母。由于 Jodie 不能回头而且不知道这个圆环上有多少个格子，她并不知道自己什么时候会走到重复的点，所以她让 Aiden 在她下一步走进重复格子的时候提醒一下。但可能他们闹了矛盾，Aiden 发了脾气，决定在 Jodie 走了 $K$（$K \geq 0$）步重复的格子之后才告诉她。Jodie 进行了两次实验，记录了两次走的路径。第二次实验再进去之前，每个格子所显示的字母会被重设为第一次实验开始前的样子。Jodie 发现了 Aiden 的恶作剧，她只能把可能的最大的 $L$ 告诉实验人员。

为了帮助你更好的理解题目，请仔细分析一下例子：

假设 $L = 4$，$K = 1$

第一次实验开始前每个格子显示的字母如下图：

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

Jodie 从显示字母为 `a` 的格子开始走，Aiden 在她走了 $K$ 步重复的格子之后告诉她停止，所以 Jodie 一共走了 $5$ 步，每走一步，格子的变化如下（箭头指着 Jodie 所在的格子）：

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

Jodie 的第二次实验从显示字母为 `c` 的格子开始走，每走一步格子的变化如下（箭头指着 Jodie 所在的格子）：

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

Jodie 两次实验记录的路径分别为：

`abcdx`

`cdabz`

现在给出 Jodie 记录的两次路径的长度 $N$，以及 Jodie 所写的内容，但是并不知道 $K$ 是多少，希望你能帮忙求出一个最大的可能的 $L$。

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

第二行：包含一个长度为 $N$ 的字符串，字符串中只包含小写字母。

第三行：包含一个长度为 $N$ 的字符串，字符串中只包含小写字母。

outputFormat: 输出答案只包含一个数字 $L$，表示圆环最大可能有的格子数。


title: [GDOI2014] 传送

description:
有n个国家，编号分别为0到n-1。第i个国家包含mi个城市，编号分别为0到mi-1，其中编号为0的城市是该国家的首都。为了表示的方便，我们用(i,j)来表示第i个国家的第j个城市。同一个国家的城市之间有通路，这些通路构成一棵树，首都则是这棵树的根。而不同国家的城市之间没有通路，只能通过传送门。每个国家只有处于叶子节点的城市具有传送门，传送门的目的地可以是编号相邻的国家的任意一个处于叶子节点的城市，每次传送需要花费1个单位时间，并且每个传送门只能使用一次。如下图所示，如果出发地是(0,2)，目的地是(2,1)，则(0,2)->(1,1)->(1,0)->(1,2)->(2,1)是一条可行路径，而(0,2)->(1,1)->(2,1)则是非法的，因为(1,1)的传送门在(0,2)->(1,1)的时候被使用了一次，在(1,1)->(2,1)的时候又被使用了一次。

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

给定出发地和目的地，问最少需要多少时间。

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

接下来有n个模块，每块描述一个国家的情况。每个模块的第一行是一个正整数mi，表示编号为i的国家包含的城市个数，接下来mi-1行，每行包含三个整数u，v，t，表示从城市u到城市v有通路，需要花费的时间为t (1<=t<=1000)。

接下来一行有一个正整数q，表示查询的个数。接下来q行，每一行包含四个整数，s0，s1，e0，e1，其中，(s0,s1)为出发地，(e0,e1)为目的地。

outputFormat: 输出有q行，每行只包含一个整数。如果能从出发地到达目的地，输出最少时间，否则，输出-1。


title: [湖南集训] Hungry Rabbit

description:
可怕的洪水在夏天不期而至，兔子王国遭遇了前所未有的饥荒，它们不得不去外面的森林里寻找食物。

为了简化起见，我们假设兔子王国中有 $n$ 只兔子，编号为 $1$ 到 $n$。在救济粮到来之前的 $m$ 天中，每天恰好有 $k$ 只兔子需要去森林里寻找粮食。森林里居住着可怕的大灰狼，所幸兔子已经摸清了大灰狼捕食习惯，即狼们在每一天只会捕食特定编号的兔子。为了安全起见，兔子们需要保证每次出去觅食的 $k$ 只兔子都不会被狼捕食。

由于每天出去捕食的兔子都不尽相同，它们为每一天定义了一个生疏度 $p_i$ ，即第 $i$ 天出来寻找食物，但是第 $i−1$ 天却没有出来觅食的兔子个数。规定第 $1$ 天的生疏度为 $0$。

现在兔子们希望在保证安全的前提下，每天的生疏度不能超过 $l$，请为兔子们构造一个合法的方案。

inputFormat:
第一行包括四个整数 $n, m, k, l$。

接下来 $n$ 行，每行一个长度为 $m$ 的 $01$ 串。其中第 $i$ 行第 $j$ 个字符若为 $0$，则表示狼在第 $j$ 天会捕食编号为 $i$ 的兔子，为 $1$ 则表示不捕食。

outputFormat:
共 $m$ 行，每行 $k$ 个 $1$ 到 $n$ 之间互不相同的整数，代表这一天出去寻找食物的兔子编号。

如果没有合法方案，则输出一行 `−1` 即可。


title: [湖南集训] Clever Rabbit

description:
聪明的兔子定义了三个函数:

- $g(x)$ 表示将 $x$ 十进制表示中各位数字从高位到低位降序排列组成的数字。

- $l(x)$ 表示将 $x$ 十进制表示中各位数字从高位到低位升序排列组成的数字。

- $f(x)=g(x)-l(x)$。

如果一个数 $x$ 与 $f(x)$ 相等，兔子们称它为幸运数。现在兔子们希望计算在所有的 $n$ 位数字中，所有幸运数的平方的和。结果对 $p$ 取模后输出，注意这里数字可以包含前导 $0$。

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

outputFormat: 一行一个整数，表示所求的结果。

hint:
#### 数据规模与约定
- 对于 $20\%$ 的测试数据，保证 $1\leq n\leq 10$。
- 对于 $100\%$ 的测试数据，保证 $1\leq n\leq 30$，$1\leq p\leq 2\times 10^9$。


title: [湖南集训] Crazy Rabbit

description:
兔子们决定在自己的城堡里安排一些士兵进行防守。

给出 $n$ 个点的坐标，和城堡里一个圆心在原点的圆形的障碍，兔子们希望从中选出 $k$ 个兔子，使得它们两两**所在的直线**都不与圆相交。

兔子们希望知道最多能选出多少兔子。

inputFormat:
第一行两个整数 $n$ 和 $r$，表示兔子的个数和圆的半径。

接下来 $n$ 行，每行两个整数 $x_i$ 和 $y_i$，表示第 $i$ 只兔子的坐标

保证每只兔子都严格在障碍外部，且两两所在的直线不与圆相切。

outputFormat: 输出一行一个整数, 表示最多能选出多少兔子

hint:
#### 样例 1 解释

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

选择第 $1, 2, 6, 4$ 只兔子即可。

---

#### 数据规模与约定

- 对于 $10\%$ 的数据，保证 $1\leq n\leq 20$。
- 对于 $30\%$ 的数据，保证 $1\leq n\leq 100$。
- 对于 $100\%$ 的数据，保证 $1\leq n\leq 2000$，$1\leq r,x_i,y_i \leq 5000$。


title: [湖南集训] 大新闻

description:
有一个在 [0,n) 内等概率随机选择的整数，记其为 x。我们需要在 [0,n)内找到某一个整数 y，使得 x ⊕ y 达到最大值。这里 ⊕ 代表异或。

问题在于，有可能对 x 进行了加密。情报显示，没有被加密的概率为 p。我们决定采取这样的策略：如果 x 没有被加密，那么我们选出使得 x ⊕ y 最大的 y；否则，我们在 [0,n) 内等概率随机选择一个整数作为 y。

请求出 x ⊕ y 的期望值。

inputFormat: 输入文件仅包含一行，其中有一个正整数 n 和一个实数 p，含义如问题描述中所述。 p 至多精确到小数点后六位。

outputFormat: 输出一行，代表 x ⊕ y 的期望值。只有当你的输出与标准输出的相对误差不超过 $10^{-5}$ 时，你的输出才会被判为正确。建议保留至少六位小数。

hint:
考虑样例一。如果 x 没有被加密，那么可能的 x 与对应的 y 的取值如下：

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

此时的期望值为 8/3。

如果大新闻被加密了，那么可能的 x 和 y 的取值如下：

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

此时的期望值为 12/9 = 4/3。

所以总的期望值为 2。

所有测试点的数据规模如下：

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

对于全部测试数据，$1 \le n \le 10^{18}$。


title: [湖南集训] 更为厉害

description:
设 $\text T$ 为一棵有根树，我们做如下的定义：

- 设 $a$ 和 $b$ 为 $\text T$ 中的两个不同节点。如果 $a$ 是 $b$ 的祖先，那么称“$a$ 比 $b$ 更为厉害”。
- 设 $a$ 和 $b$ 为 $\text T$ 中的两个不同节点。如果 $a$ 与 $b$ 在树上的距离不超过某个给定常数 $x$，那么称“ $a$ 与 $b$ 彼此彼此”。

给定一棵 $n$ 个节点的有根树 $\text T$，节点的编号为 $1$ 到 $n$，根节点为 $1$ 号节点。
你需要回答 $q$ 个询问，询问给定两个整数 $p$ 和 $k$，问有多少个有序三元组 $(a,b,c)$ 满足：

1. $a,b,c$ 为 $\text T$ 中三个不同的点，且 $a$ 为 $p$ 号节点；
2. $a$ 和 $b$ 都比 $c$ 更为厉害；
3. $a$ 和 $b$ 彼此彼此。这里彼此彼此中的常数为给定的 $k$。

inputFormat:
输入文件的第一行含有两个正整数 $n$ 和 $q$，分别代表有根树的点数与询问的个数。

接下来 $n - 1$ 行，每行描述一条树上的边。每行含有两个整数 $u$ 和 $v$，代表在节点 $u$ 和 $v$ 之间有一条边。

接下来 $q$ 行，每行描述一个操作。第 $i$ 行含有两个整数，分别表示第 $i$ 个询问的 $p$ 和 $k$。

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

hint:
样例中的树如下图所示：

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

对于第一个和第三个询问，合法的三元组有 $(2,1,4)$、 $(2,1,5)$ 和 $(2,4,5)$。

对于第二个询问，合法的三元组只有 $(4,2,5)$。

所有测试点的数据规模如下（注意，洛谷并不按照以下方式评测）：

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

对于全部测试数据的所有询问，$1\le p,k \le n$。

- 2023.9.15 添加一组 hack 数据。


title: [湖南集训] 图森

description:
有一个字符串集合 $S$，此处集合的概念与数学中的集合不同，其中可以含有重复的元素。初始时 $S$ 包含 $n$ 个字符串 $s_1, s_2, \cdots, s_n$。有下面两种操作：

- 向 $S$ 中加入一个已经存在于 $S$ 中的字符串。
- 从 $S$ 中选出两个字符串，将这两个字符串拼接得到的字符串加入集合 $S$。

现在想要知道，进行任意多次操作之后，在 $S$ 中的所有字符串中，最长的回文子串可以有多长？如果发现长度可以是无穷大，这时你需要输出 $\text{Infinity}$。

inputFormat:
第一行含有一个整数 $n$，代表初始时集合的大小。

接下来的 $n$ 行，每行含有一个字符串。第 $i$ 行的字符串为 $s_i$。保证字符串中只含有小写英文字母。

outputFormat: 如果最长的回文子串的长度不为无穷大，则输出一个整数，代表其长度；否则输出 $\text{Infinity}$。

hint:
#### 样例解释

第一个样例中，将 $\text{ecab}$ 与 $\text{abacde}$ 拼接，得到 $\text{e}\underline{\text{cababac}}\text{de}$，其中下划线的部分就是最长的回文子串，长度为 $7$。可以证明不存在更长的回文子串。

第二个样例中，可以将任意多个 $\text{ha}$ 拼接起来，从而得到 $\underline{\text{h}}\text{a},$ $\underline{\text{hah}}\text{a},$ $\underline{\text{hahah}}\text{a}$ 等任意奇数长度的回文子串。因此答案为无穷大，输出 $\text{Infinity}$。

#### 数据规模与约定
![OvO](https://cdn.luogu.com.cn/upload/pic/55026.png)


title: 数列找不同

description: 现有数列 $A_1,A_2,\ldots,A_N$，$Q$ 个询问 $(L_i,R_i)$，询问 $A_{L_i} ,A_{L_i+1},\ldots,A_{R_i}$ 是否互不相同。

inputFormat:
第一行，两个整数$N,Q$。
第二行，$N$ 个整数$A_1, A_2, \ldots , A_N$。
接下来 $Q$ 行，每行两个整数 $L_i,R_i$。

outputFormat: 对每个询问输出一行，`Yes` 或 `No`。


title: 递增

description:
现有数 $A_1,A_2,\cdots,A_n$，修改最少的数字为**实数**，使得数列严格单调递增。

注：原题误表述为修改为整数，现已纠正为实数。本题数据确保按照修改为整数的做法也可以 AC（只是不能过样例）

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

第二行，$n$ 个整数$A_1,A_2,\cdots,A_n$

outputFormat: 1 个整数，表示最少修改多少个数字


title: 导弹拦截III

description:
很多年以前，A 国发明了一种导弹系统用来拦截敌对势力发射的导弹。

这个系统可以发射一颗导弹拦截从由到远、高度不增加的多个导弹。

但是现在，科学家们发现这个防御系统还不够强大，所以他们发明了另外一套导弹系统。

这个新系统可以发射一颗导弹由近到远的拦截更多的导弹。

当这个系统启动，首先选择一颗敌人的导弹进行拦截，然后拦截一颗更远的高度更低的导弹进行拦截，然后拦截比第二颗更远的但高度更高的导弹……以此类推，拦截的第奇数颗导弹比前一颗导弹更远、更高，拦截的第偶数颗导弹比前一个更远、更低。

现在，给你一个从近到远的导弹高度列表，计算新系统发射一颗导弹可以拦截的最多的导弹数目。

inputFormat: 第一行是一个整数 $n$，表示敌人发射的导弹数目。接下来的一行有 $n$ 个整数，表示由近到远的。

outputFormat: 仅一个整数，表示拦截的最多导弹的数量。


title: 三只小猪

background: 你听说过三只小猪的故事吗？这是一个经典的故事。很久很久以前，有三只小猪。第一只小猪用稻草建的房子，第二个小猪用木棍建的房子，第三个小猪则使用砖做为材料。一只大灰狼想吃掉它们并吹倒了稻草和木棍建的房子。但是砖盖的房子很结实，狼最终也没有破坏掉，最后小猪们战胜了大灰狼并把它尾巴烧掉了。

description:
为了自己的安全，小猪们又建造了一个新砖房。但是现在问题出现了，怎样把三个小猪分配到两个房子里呢？第三只小猪是三只小猪中最聪明的一只，为了不浪费任何一个房子，它总共考虑了三种方案，如下图

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

“但是将来怎么办呢？”第三只小猪知道将来随着成员的增多，它们将会盖更多的房子。它想知道给定了房子和猪的数目后，房子的分配方案有多少，但这个问题对于它来说，很明显有点难了，你能帮小猪解决这个问题吗？

inputFormat: 输入文件piggy.in，仅有一行，包含两个整数n和m，分别表示小猪的数目和房间数（1≤n≤50，0≤m≤50）。

outputFormat: 输出文件piggy.out，仅一个整数，表示将n只小猪安置在m个房间且没有房间空闲的方案数。


title: 道路重建

description: 从前，在一个王国中，在 $n$ 个城市间有 $m$ 条道路连接，而且任意两个城市之间至多有一条道路直接相连。在经过一次严重的战争之后，有 $d$ 条道路被破坏了。国王想要修复国家的道路系统，现在有两个重要城市 $A$ 和 $B$ 之间的交通中断，国王希望尽快的恢复两个城市之间的连接。你的任务就是修复一些道路使 $A$ 与 $B$ 之间的连接恢复，并要求修复的道路长度最小。

inputFormat:
输入文件第一行为一个整数 $n\ (2<n\le 100)$，表示城市的个数。这些城市编号从 $1$ 到 $n$。

第二行为一个整数 $m\ (n-1\le m\le \dfrac{1}{2}n(n-1))$，表示道路的数目。

接下来的 $m$ 行，每行 $3$ 个整数 $i,j,k\ (1 \le i,j \le n,i\neq j,0<k \le 100)$，表示城市 $i$ 与 $j$ 之间有一条长为 $k$ 的道路相连。

接下来一行为一个整数 $d\ (1\le d\le m)$，表示战后被破坏的道路的数目。在接下来的 $d$ 行中，每行两个整数 $i$ 和 $j$，表示城市 $i$ 与 $j$ 之间直接相连的道路被破坏。

最后一行为两个整数 $A$ 和 $B$，代表需要恢复交通的两个重要城市。

outputFormat: 输出文件仅一个整数，表示恢复 $A$ 与 $B$ 间的交通需要修复的道路总长度的最小值。


title: Geodetic集合

description:
图 $\text G$ 是一个无向连通图，没有自环，并且两点之间至多只有一条边。我们定义顶点 $v,u$ 的最短路径就是从 $v$ 到 $u$ 经过边最少的路径。所有包含在 $v-u$ 的最短路径上的顶点被称为 $v-u$ 的 Geodetic 顶点，这些顶点的集合记作 $I(v,u)$。

我们称集合 $I(v,u)$ 为一个 Geodetic 集合。

例如下图中，$I(2,5)=\{2,3,4,5\}$，$I(1,5)=\{1,3,5\}$，$I(2,4)=\{2,4\}$。

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

给定一个图 $\text G$ 和若干点对 $v,u$，请你分别求出 $I(v,u)$。

inputFormat:
第一行为两个整数 $n,m$，分别表示图 $\text G$ 的顶点数和边数（顶点编号为 $1\sim n$）。
接下来 $m$ 行，每行两个整数 $a,b$，表示 顶点 $a$ 和 $b$ 之间有一条无向边。
第 $m+2$ 行有一个整数 $k$，表示给定的点对数。
接下来 $k$ 行，每行两个整数 $v,u$，表示每个点对的起点和终点。

outputFormat: 共 $k$ 行，对于输入文件中每一个点对 $v,u$，按顶点顺序一行输出 $I(v,u)$ 里面的所有点的编号。

hint: 对于所有数据，满足 $1\leqslant n\leqslant 40$，$1\leqslant m\leqslant \frac{n(n-1)}2$。


title: 圈的异或

description:
给出无向图G，边$(A_i,B_i)$ 的权是$C_i$，判断下列性质是否成立：

对于任意圈C，其边权的异或和是0

inputFormat:
第1 行，1 个整数T，表示数据的组数。

每组数据第1 行，2 个整数$N,M$，表示图G 点和边的数量。

M 行，每行3 个整数$A_i,B_i,C_i$

outputFormat: 对每个数据输出一行，“Yes” 或者“No”


title: 数列之异或

description:
求$1 \bigoplus 2 \bigoplus\cdots\bigoplus N$ 的值。

$A \bigoplus B$ 即$A$ , $B$ 按位异或。

inputFormat: 1 个整数$N$。

outputFormat: 1 个整数，表示所求的值。


title: 异或之积

description:
对于$A_1,A_2,A_3,\cdots,A_N$，求

$$(6\times \sum_{i=1}^N\sum_{j=i+1}^N\sum_{k=j+1}^N A_i\times A_j\times A_k) \bmod (10^9+7)$$

inputFormat:
第 1 行，1 个整数$N$。

第 2 行，$N$ 个整数 $A_1,A_2,A_3,\cdots,A_N$。

outputFormat: 1 个整数，表示所求的值。


title: 纪念邮票

description:
邮局最近推出了一套纪念邮票，这套邮票共有 $N$ 张，邮票面值各不相同，按编号顺序为 $1$ 分，$2$ 分，……，$N$ 分。

小明是个集邮爱好者，他很喜欢这套邮票，可惜现在他身上只有 $M$ 分，并不够把全套都买下，但是他希望刚好花光所有的钱。作为一个集邮爱好者，小明也不想买的邮票编号断断续续，所以小明打算买面值 $a$ 分至 $b$ 分的 $b-a+1$ 张连续的邮票，且总价值刚好为 $M$ 分。

你的任务是求出所有符合要求的方案，以 $\left[a,b\right]$ 的形式输出。

inputFormat: 输入文件只有一行。包含两个整数 $N$ 和 $M$（$1\le N,M \le 10^9$），之间用空格隔开。

outputFormat: 输出文件每行包含一个合法方案：$\left[a,b\right]$，按 $a$ 值从小到大输出。


title: 最小公倍数之和

description:
对于$A_1,A_2,\cdots,A_N$，求

$\sum_{i=1}^N\sum_{j=1}^N \mathrm{lcm}(A_i,A_j)$

的值。

$\mathrm{lcm}(a,b)$ 表示 $a$ 和 $b$ 的最小公倍数。

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

第二行，$N$ 个整数 $A_1,A_2,\cdots,A_N$。

outputFormat: 一行一个整数，表示所求的值。


title: 素数个数

description: 求 $1,2,\cdots,N$ 中素数的个数。

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

outputFormat: 一行一个整数，表示素数的个数。


title: 车的攻击

description:
$N \times N$ 的国际象棋棋盘上有$K$ 个车，第$i$个车位于第$R_i$行，第$C_i$ 列。求至少被一个车攻击的格子数量。

车可以攻击所有同一行或者同一列的地方。

inputFormat:
第1 行，2 个整数$N,K$。

接下来K 行，每行2 个整数$R_i,C_i$。

outputFormat: 1 个整数，表示被攻击的格子数量。


title: 染色计数

description: 有一颗$N$个节点的树，节点用$1,2,\cdots,N$编号。你要给它染色，使得相邻节点的颜色不同。有$M$种颜色，用$1,2,\cdots,M$编号。每个节点可以染$M$种颜色中的若干种，求不同染色方案的数量除以($10^9 + 7$)的余数。

inputFormat:
第1 行，2 个整数$N,M$。

接下来$N$行，第$i$行表示节点$i$可以染的颜色。第1个整数$k_i$，表示可以染的颜色数量。接下来$k_i$个整数，表示可以染的颜色编号。

最后$N - 1$行，每行2个整数$A_i,B_i$，表示边$(A_i,B_i)$。

outputFormat: 1 个整数，表示所有的数。

hint:
• 对于30% 的数据，$1 \le N \le 10; 1 \le M \le 4$；

• 对于60% 的数据，$1 \le N \le 200; 1 \le M \le 200$；

• 对于100% 的数据，$1 \le N \le 5000; 1 \le M \le 5000$。


title: 树的分解

description: 给出 $N$ 个点的树和 $K$，问能否把树划分成 $\frac{N}{K}$ 个连通块，且每个连通块的点数都是 $K$。

inputFormat:
第一行，一个整数 $T$，表示数据组数。接下来 $T$ 组数据，对于每组数据：

第一行，两个整数 $N, K$。

接下来 $N - 1$ 行，每行两个整数 $A_i, B_i$，表示边 $(A_i, B_i)$。点用 $1, 2, \ldots, N$ 编号。

outputFormat: 对于每组数据，输出 `YES` 或 `NO`。


title: 图的遍历

description: 给出 $N$ 个点，$M$ 条边的有向图，对于每个点 $v$，求 $A(v)$ 表示从点 $v$ 出发，能到达的编号最大的点。

inputFormat:
第 $1$ 行 $2$ 个整数 $N,M$，表示点数和边数。

接下来 $M$ 行，每行 $2$ 个整数 $U_i,V_i$，表示边 $(U_i,V_i)$。点用 $1,2,\dots,N$ 编号。


title: 异或序列

description:
给出序列 $A_1,A_2,\cdots,A_N$，求

$$\sum_{1\le i\le j\le N} A_i\oplus A_{i+1}\oplus\cdots\oplus A_j$$

的值。其中，$\bigoplus$ 表示按位异或。

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

第二行，$N$个整数 $A_1,A_2,\cdots,A_N$。

outputFormat: 一个数，为表达式的值。


title: [国家集训队] 特技飞行

background:
1. wqs 爱好模拟飞行。

2. clj 开了一家神犇航空，由于 clj 还要玩游戏，所以公司的事务由你来打理。

注意：题目中只是用了这样一个背景，并不与真实/模拟飞行相符

description: 神犇航空开展了一项载客特技飞行业务。每次飞行长 $n$ 个单位时间，每个单位时间可以进行一项特技动作，可选的动作有 $k$ 种，每种动作有一个刺激程度 $c_i$。如果连续进行相同的动作，乘客会感到厌倦，所以定义某次动作的价值为(距上次该动作的时间) $ \times c_i$，若为第一次进行该动作，价值为 $0$。安排一种方案，使得总价值最大。

inputFormat:
第一行，两个整数，$n$ 和 $k$，如上所述；

第二行，$k$ 个整数，表示 $k$ 种动作的 $c_i$ 值。

outputFormat: 仅一行，一个整数，表示最大总价值。


title: 【模板】可持久化线段树 1（可持久化数组）

background:
**UPDATE : 最后一个点时间空间已经放大**

2021.9.18 增添一组 hack 数据 by @panyf

标题即题意

有了可持久化数组，便可以实现很多衍生的可持久化功能（例如：可持久化并查集）

description:
如题，你需要维护这样的一个长度为 $ N $ 的数组，支持如下几种操作

1. 在某个历史版本上修改某一个位置上的值

2. 访问某个历史版本上的某一位置的值

此外，每进行一次操作（**对于操作2，即为生成一个完全一样的版本，不作任何改动**），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

inputFormat:
输入的第一行包含两个正整数 $ N, M $， 分别表示数组的长度和操作的个数。

第二行包含$ N $个整数，依次为初始状态下数组各位的值（依次为 $ a_i $，$ 1 \leq i \leq N $）。

接下来$ M $行每行包含3或4个整数，代表两种操作之一（$ i $为基于的历史版本号）：

1. 对于操作1，格式为$ v_i \ 1 \ {loc}_i \ {value}_i $，即为在版本$ v_i $的基础上，将 $ a_{{loc}_i} $ 修改为 $ {value}_i $。

2. 对于操作2，格式为$ v_i \ 2 \ {loc}_i $，即访问版本$ v_i $中的 $ a_{{loc}_i} $的值，注意：**生成一样版本的对象应为 $v_i$**。

outputFormat: 输出包含若干行，依次为每个操作2的结果。


title: Calculating

description: 若 $x$ 分解质因数结果为 $x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$，令$f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)$，求 $\sum_{i=l}^rf(i)$ 对 $998\,244\,353$ 取模的结果。

inputFormat: 输入只有一行两个整数，分别表示 $l$ 和 $r$。

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


title: [SHOI2008] 循环的债务

description:
Alice、Bob和Cynthia总是为他们之间混乱的债务而烦恼，终于有一天，他们决定坐下来一起解决这个问题。不过，鉴别钞票的真伪是一件很麻烦的事情，于是他们决定要在清还债务的时候尽可能少的交换现金。

比如说，Alice欠Bob 10元，而Cynthia和他俩互不相欠。现在假设Alice只有一张50元，Bob有3张10元和10张1元，Cynthia有3张20元。一种比较直接的做法是：Alice将50元交给Bob，而Bob将他身上的钱找给Alice，这样一共就会有14张钞票被交换。但这不是最好的做法，最好的做法是：Alice把50块给Cynthia，Cynthia再把两张20给Alice，另一张20给Bob，而Bob把一张10块给C，此时只有5张钞票被交换过。

没过多久他们就发现这是一个很棘手的问题，于是他们找到了精通数学的你为他们解决这个难题。

inputFormat:
输入的第一行包括三个整数：$x_1$、$x_2$、$x_3$（-1,000≤$x_1$，$x_2$，$x_3$≤1,000），其中

$x_1$代表Alice欠Bob的钱（如果$x_1$是负数，说明Bob欠了Alice的钱）

$x_2$代表Bob欠Cynthia的钱（如果$x_2$是负数，说明Cynthia欠了Bob的钱）

$x_3$代表Cynthia欠Alice的钱（如果$x_3$是负数，说明Alice欠了Cynthia的钱）

接下来有三行，每行包括6个自然数：

a100，a50，a20，a10，a5，a1

b100，b50，b20，b10，b5，b1

c100，c50，c20，c10，c5，c1

a100表示Alice拥有的100元钞票张数，b50表示Bob拥有的50元钞票张数，以此类推。另外，我们保证有a10+a5+a1≤30，b10+b5+b1≤30，c10+c5+c1≤30，而且三人总共拥有的钞票面值总额不会超过1,000。

outputFormat: 如果债务可以还清，则输出需要交换钞票的最少张数；如果不能还清，则输出“impossible”（注意单词全部小写，输出到文件时不要加引号）。


title: [SHOI2013] 发牌

description:
在一些扑克游戏里，如德州扑克，发牌是有讲究的。一般称呼专业的发牌手为荷官。荷官在发牌前，先要销牌（burn card）。所谓销牌，就是把当前在牌库顶的那一张牌移动到牌库底，它用来防止玩家猜牌而影响游戏。

假设一开始，荷官拿出了一副新牌，这副牌有 $N$ 张不同的牌，编号依次为 $1$ 到 $N$。由于是新牌，所以牌是按照顺序排好的，从牌库顶开始，依次为 $1,2,\cdots,N$，$N$ 号牌在牌库底。为了发完所有的牌，荷官会进行 $N$ 次发牌操作，在第 $i$ 次发牌之前，他会连续进行 $R_i$ 次销牌操作，$R_i$ 由输入给定。请问最后玩家拿到这副牌的顺序是什么样的？

举个例子，假设 $N=4$，则一开始的时候，牌库中牌的构成顺序为 $1,2,3,4$。

- 假设 $R_1=2$，则荷官应该连销两次牌，将 $1$ 和 $2$ 放入牌库底，再将 $3$ 发给玩家。目前牌库中的牌顺序为 $4,1,2$。
- 假设 $R_2=0$，荷官不需要销牌，直接将 $4$ 发给玩家，目前牌库中的牌顺序为 $1,2$。
- 假设 $R_3=3$，则荷官依次销去了 $1,2,1$，再将 $2$ 发给了玩家。目前牌库仅剩下一张牌 $1$。
- 假设 $R_4=2$，荷官在重复销去两次 $1$ 之后，还是将 $1$ 发给了玩家，这是因为 $1$ 是牌库中唯一的一张牌。

inputFormat:
第一行，一个整数 $N$，表示牌的数量。

第二行到第 $N+1$ 行，在第 $i+1$ 行，有一个整数 $R_i$。

outputFormat: 共 $N$ 行，第 $i$ 行有一个整数，表示玩家收到的第 $i$ 张牌的编号。


title: 小学数学题

background:
露米娅：我来先考你一道小学数学题吧！

琪露诺：好！小学的题我肯定都会！

description:
露米娅：有 $ n $ 只妖精要跨过雾之湖，由于湖边大雾弥漫，妖精们看不清湖到底有多大，不想从边上绕过去。

湖上有一~~条船~~个传送器，且这个传送器每次只能载 $ r $ 只妖精跨过湖面（注意传送器可以同时把两侧的妖精分别运到对岸，但每次运送的总妖精数不能超过 $ r $ ）。

这些妖精还很喜欢搞事，所以在任何时刻，都需要满足一些条件，其中第一种条件有 $ m_1 $ 个，第二种条件有 $ m_2 $ 个。

第一种条件形如 妖精 $ a $ 和妖精 $ b $ 必须要在湖的同一侧；

第二种条件形如 当妖精 $ a $ 在湖的一侧时，妖精 $ b $ 和妖精 $ c $ 不能同时在湖的另一侧。

现在给出这些条件，求：

1. 至少需要传送器几次才能让所有妖精到湖的对岸

2. 在保证次数最少的前提下，求过河方案数

inputFormat:
第一行四个整数 $ n , m_1 , m_2 , r $

接下来 $ m_1 $ 行每行2个整数 $ a , b $，代表第一种条件

接下来 $ m_2 $ 行每行3个整数 $ a , b , c $， 代表第二种条件

outputFormat:
两个整数，分别为最少使用传送器次数和方案数，用空格分隔

若无法全部过河，输出"-1 0"（不含引号）

hint:
对于 $ 30 \% $ 的数据， $ n \leq 10 $

对于另外 $ 10 \% $ 的数据， $ m_1 = m_2 = 0 $

对于 $ 100 \% $ 的数据， $ a,b,c \leq n \leq 15 $， $ m_1 , m_2 \leq 50 $， $ r \leq 10^9 $

请不要相信洛谷评测机的速度，如果得了80分以上，可以等人少的时候再交一次。但如果得了60分以下，说明可能写的不是正解，就不要再虐萌萌哒评测机啦


title: 中学数学题

background:
琪露诺：我知道了！答案是-1 0，因为幻想乡没有传送器！

露米娅：真拿你没办法。。算了，再来一道中学数学题吧

说着，露米娅写下了一个数列

$ 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , \cdots , 2048 , 4096 , 8192 , 16384 , \cdots $

description:
露米娅：这个数列的通项公式是 $ x_n = 2^{n-1} $

那么你来求一下前 $ k+1 $ 项中有多少个第一位为4吧（比如4096）

输入经过“加密”

详细输入方式见【输入格式】

inputFormat:
一行两个正整数，$ t $ 和 $ k_0 $

若 $ t = 1 $ 说明实际的k就是 $ k_0 $

若 $ t = 0 $ 说明实际的k是 $ 10^{k_0} $

outputFormat: 一个整数 $ ans $ ，表示有多少个数第一位为 4


title: 大学数学题

background:
琪露诺：我知道了！答案一定是1！

露米娅：什么鬼啊（汗），你还是再想想去吧。。我先把最后一道题给你，这是一道大学数学题哦

description:
露米娅：大妖精想构造一个 $ n $ 元有限域，元素用 $ 0 \sim n - 1 $ 的整数表示

有限域需要满足以下条件

1.有加法单位元 $ o $ ，满足对于任意元素 $ a $ ， $ o + a = a + o = a $

2.对于任意元素 $ a $ ，存在加法逆元 $ a^{-1} $ ，使得 $ a + a^{-1} = a^{-1} + a = o $

3.有不同于加法单位元 $ o $ 的乘法单位元 $ i $ ，满足对于任意元素 $ a $ ， $ i \times a = a \times i = a $

4.对于任意非加法单位元元素 $ a $ ，存在乘法逆元 $ a^{-1} $ ，使得 $ a \times a^{-1} = a^{-1} \times a = i $

5.对于任意元素 $ x $ , $ y $ ，有加法交换律，即 $ x + y = y + x  $

6.对于任意元素 $ x $ , $ y $ ，有乘法交换律，即 $ x \times y = y \times x  $

7.对于任意元素 $ x $ , $ y $ , $ z $ ，有加法结合律，即 $ ( x + y ) + z = x + ( y + z ) $

8.对于任意元素 $ x $ , $ y $ , $ z $ ，有乘法结合律，即 $ ( x \times y ) \times z = x \times ( y \times z ) $

9.对于任意元素 $ x $ , $ y $ , $ z $ ，有乘法分配律，即 $ ( x + y ) \times z = x \times z + y \times z $

大妖精当然会做啦，但是他想考考你

在输出中加法单位元  $ o $ 即为 0，乘法单位元  $ i $ 即为 1

inputFormat:
一个正整数 $ n $

$ 2 \leq n \leq 350 $

outputFormat:
##第一行输出一个正整数 $ k $ ，若存在 $ n $ 元有限域则 $ k = 0 $ ，否则 $ k = -1 $

若 $ k = 0 $ 则

1.接下来 $ n $ 行输出一个 $ n $ 元有限域的加法表，第 $ i + 1 $ 行第 $ j + 1 $ 列上的数代表有限域中 $ i + j $ 的运算结果

2.接下来 $ n $ 行输出一个 $ n $ 元有限域的乘法表，第 $ i + 1 $ 行第 $ j + 1 $ 列上的数代表有限域中 $ i \times j $ 的运算结果

共输出 $ n \times 2 + 1 $ 行

upd1:SPJ非常严格，请不要在行末输出多余空格

（答案文件末尾的换行还是会自动忽略的）

upd2:正解文件比较大，洛谷可能会一直judging...

如果遇到这种情况请直接提交源代码


title: [WC2014] 紫荆花之恋

description:
强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。

仔细看看的话，这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点，每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物，每个小精灵 $i$ 都有一个感受能力值 $r_i$，小精灵 $i,j$ 成为朋友当且仅当在树上 $i$ 和 $j$ 的距离 $dist(i,j) \leq r_i+r_j$，其中 $dist(i,j)$ 表示在这个树上从 $i$ 到 $j$ 的唯一路径上所有边的边权和。

强强和萌萌很好奇每次新长出一个叶子节点之后，这个树上总共有几对朋友。

我们假定这个树一开始为空，节点按照加入的顺序从 1 开始编号。由于强强非常好奇，你必须在他每次出现新结点后马上给出总共的朋友对数，不能拖延哦。

inputFormat:
第一行包含一个整数，表示测试点编号。

第二行包含一个正整数 $n$，表示总共要加入的节点数。

我们令加入节点前的总共朋友对数是 $last\_ans$，在一开始时它的值为 0。

接下来 $n$ 行中第 $i$ 行有三个非负整数 $a_i,c_i,r_i$，表示结点 i 的父节点的编号为 $ai \; \oplus \; (last\_ans \; \bmod \; 10^9)$（其中 $\oplus$ 表示异或，数据保证这样操作后得到的结果介于 1 到 $i−1$ 之间），与父结点之间的边权为 $c_i$，节点 $i$ 上小精灵的感受能力值为 $r_i$。

注意 $a_1=c_1=0$，表示 1 号节点是根结点，对于 $i>1$，父节点的编号至少为 1。

outputFormat: 包含 $n$ 行，每行输出 1 个整数，表示加入第 $i$ 个点之后，树上有几对 friends。


title: aaa被续

background: HansBug持续无聊ing

description:
由于aaa没有完成HansBug的任务。所以HansBug开始计划着如何续aaa。

现在HansBug手里有 $ N $个aaa，每个aaa有一个码力值。一共存在 $ N - 1 $条连接两个aaa的边，故这 $ N $个aaa构成一棵**有根树**，根为1号aaa。

现在HansBug想要续了这 $ N $个aaa。HansBug所采用的策略是，对于第 $ i$个aaa，先让他和他的各级子aaa们~~乖乖♂站好~~成一队，然后依次续掉。

经过长期对于aaa码力值的研究，HansBug发现，**对于每一队aaa**，设有 $n$个，码力值依次为$ v_i $，则续了队伍里的第 $ i $个aaa所能获得的码力值为 $ v_1 + v_2 + \cdots + v_i $。

然而，aaa之间的关系树相当的复杂，HansBug的智商早已不够用，于是这个任务就交给了你。不过HansBug知道，任何一个aaa都不会有超过5个的直接子aaa

HansBug想要知道在每次排♂队方法最优的情况下，续了这些aaa最多可以获得的码力值~~，事成之后分给你100000 % 10点码力值~~。

inputFormat:
第一行包含一个正整数 $ N $，表示aaa的个数。

接下来 $ N-1 $行，每行包含两个正整数 $ u, v$，代表第 $u $个aaa和第 $ v $个aaa之间存在从属关系（最高级别的aaa编号为 $ 1$）

最后一行包含 $ N $个非负整数，依次代表第 $ i $个aaa的码力值。

outputFormat:
输出包含一个整数，打表HansBug续掉全部的aaa之后最多能获得的码力值。

**由于结果较大，所以请对 $ 1000000007 $ 取模 （$ {10} ^ 9 + 7 $）**

hint:
**样例解释：**

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

故续了5个aaa所得的最大总码力值为：118 + 9 + 10 + 4 + 48 = 189

**对1000000007取模后得到答案189**

**数据范围：**

对于30%的数据：$ 1 \leq N \leq 3 \cdot {10}^3 $

对于50%的数据：$ 1 \leq N \leq 2 \cdot {10}^4 $

对于70%的数据：$ 1 \leq N \leq {10}^5 $

对于100%的数据：$ 1 \leq N \leq 5 \cdot {10}^5 $

对于每一个aaa的码力值 $ a_i $，保证 $ 0 \leq a_i \leq {10}^8 $


title: 赛斯石（赛后强化版）

background:
```cpp
白露横江，水光接天，纵一苇之所如，凌万顷之茫然。——苏轼
```
真程海洋近来需要进购大批赛斯石，你或许会问，什么是赛斯石？

首先我们来了解一下赛斯，赛斯是一个重量单位，我们用$ si $作为其单位。比如$ 1 $赛斯就是$ 1si $。

而赛斯石有这样一个性质，它本来是一赛斯一赛斯单独存在的，但是用自然枪将其精化之后，它就会与其它经过精化的赛斯石进行合并，合并到合适的重量之后，便将其钝化，使其不再合并其它赛斯石，如果合错了，也可以用金刚刀将其切开（神奇的是你只能切成整数赛斯重量）。赛斯石的重量只能是**整数**赛斯重量，而不同赛斯重量的赛斯石的价格也是不一样的。

description:
现需上市$ Need $赛斯重量的赛斯石，卖家想算出这些赛斯石经过某种合并方式来获得的最大收益。然而目前有一个问题，市场在真程大殿附近（真程海洋中心位置），卖家需要租船送赛斯石过去（即不考虑卖家自己租船过去的费用），目前有十种船可以租，载重量从$ 1si $到$ 10si $，每艘船的租价也是有所不同的，如下表所示：

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

由于真程大殿附近有强烈的赛斯力，导致**无法对赛斯石进行任何操作**，商家将赛斯石运过来之后就只能按照之前合并好的卖。假设卖家不返回，且这些赛斯石全部能卖出去。现在卖家他要计算总盈利（设总盈利=赛斯石的总收益-租船所需总费用），请你设计一个程序，算出一种最佳方案，以获得**最大总盈利**。

inputFormat:
输入一共有两行

第一行有一个数据$ Need $（赛斯石的总量，单位：$ si $）

第二行有十个数据$ a_{1}\  ...\ a_{10} $（分别为$ 1si $到$ 10si $的赛斯石市场价格，单位：元）

outputFormat: 输出仅一行，包含一个整数，表示最大总盈利。

hint:
### 样例一说明：

将$ 11 $个单位赛斯石合并为一个$ 4si $的赛斯石和一个$ 7si $的赛斯石并且租两个载重分别为$ 4si $和$ 7si $的船，这样做为最佳方案，那么最大总盈利就是$ 32 $元。

### 注意：

对于所有输入数据，均在区间$ (0, 100000) $中，并且为整数；

保证卖家最大总盈利为正；

同一行中，每两个数据之间有一个空格。

赛后强化版于$ 2020 $年$ 10 $月$ 13 $日$ 19 $点$ 18 $分已强化完毕。


title: Chtholly Nota Seniorious

background:
经查，本题是原题，非常抱歉。

大样例下发链接: https://pan.baidu.com/s/1nuVpRS1 密码: sfxg

**こんなにも、たくさんの幸せをあの人に分けてもらった**

**だから、きっと**

**今の、私は**

**谁が何と言おうと**

##世界一、幸せな女の子だ

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

description:
——“假如……我是说假如喔。

万一我再过五天就会死，你能不能对我温柔一点？”

巨大的六号兽五天后将袭击浮游大陆。

无数次计算得到的残酷数据表明，只有圣剑瑟尼欧尼斯的适格精灵——珂朵莉·诺塔·瑟尼欧尼斯(Chtholly Nota Seniorious)开启妖精乡之门，才可以以生命为代价守住浮游岛。

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

“至少，我也希望自己不用消失，也想让别人记住。我也想留下羁绊啊。”

留给妖精少女珂朵莉的时间似乎已经不多了。

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

年轻的二等技官，妖精仓库的管理员，世界上最后一个人类——威廉·克梅**修**，数百年前曾经是一名准勇者，掌握着成为一名勇者所需要的所有知识。

大战在即，调整圣剑的状态成为了一项重要的任务。

```cpp
瑟尼欧里斯（セニオリス）
圣剑的其中之一，在现存的遗迹兵装中，拥有最强大的力量。
拥有非常特殊的资质，只有极少一部分的人才能使用。
由四十一个护符组成。能将所有事物包含不死者都回归「死亡」。
```
威廉需要调整圣剑的状态，因此他将瑟尼欧尼斯拆分护符，组成了一个$n$行$m$列的矩阵。

每一个护符都有自己的魔力值。现在为了测试圣剑，你需要将这些护符分成 A,B两部分。

要求如下：

1.  圣剑的所有护符，恰好都属于两部分中的一部分。

2.  每个部分内部的方块之间，可以通过上下左右相互到达，而且每个内部的方块之间互相到达，最多允许拐一次弯。

例如
```cpp
ＡＡＡＡＡ　　ＡＡＡＡＡ　　ＡＡＡＡＡ
ＡＡＢＡＡ　　ＢａＡＡＡ　　ＡＡＡＢＢ
ＡＢＢＢＡ　　ＢＢＡＡＡ　　ＡＡＡＢＢ
ＡＡＢＡＡ　　ＢａＡＡＡ　　ＡＢＢＢＢ
ＡＡＡＡＡ　　ＡＡＡＡＡ　　ＢＢＢＢＢ

　　(1)　　　　　(2)　　　　　(3)
```
其中(1)(2)是不允许的分法，(3)是允许的分法。在(2)中，a属于A区域，这两个a元素之间互相到达，没有办法最多只拐一次弯。

现在要问，所有合法的分法中，A区域的极差与B区域的极差 中间较大的一个的 **最小值** 是多少？

好心而可爱的在一旁默默观察奈芙莲悄悄地告诉你，极差就是区域内最大值减去最小值。

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

夜晚的风吹拂着，68号岛上的景色竟与地上的森林无异。转念又想，黄金妖精本身就是与森林之中出现，成长，消亡的神秘存在啊。

时间不早了，早上训练中落败的珂朵莉即将回来了。您要尽快和威廉一起调整好圣剑，千万不能迟哟。

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

接下来$n$行，每行$m$个自然数$A_{i,j}$表示权值

outputFormat: 一个整数表示答案。

hint:
样例解释

```cpp
1  12 6        11
11 4  2        14
10 1  9        20
4        17 13 10
```
分法不唯一，如图是一种合法的分法。左边部分极差12-1=11，右边一块极差20-10=10，所以答案取这两个中较大者11。没有别的分法，可以使答案更小。

**数据范围与约定**

测试点　　|n　　　　|m
-|-|-
#1-2      |$\le 10$ |$\le 10$
#3-4      |1        |$\le 2000$
#5-7      |$\le 200$|$\le 200$
#8-10     |$\le 2000$|$\le 2000$

对于所有的权值$1\le A_{i,j} \le 10^9$

《末日时在做什么？有没有空？可以来拯救吗？》

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


title: SAC E#1 - 一道中档题 Factorial

background:
# 数据已修改

SOL君（炉石主播）和SOL菌（完美信息教室讲师）是好朋友。

description:
SOL君很喜欢阶乘。而SOL菌很喜欢研究进制。

这一天，SOL君跟SOL菌炫技，随口算出了n的阶乘。

SOL菌表示不服，立刻就要算这个数在k进制表示下末尾0的个数。

但是SOL菌太菜了于是请你帮忙。

inputFormat: 每组输入仅包含一行：两个整数n，k。

outputFormat: 输出一个整数：n!在k进制下后缀0的个数。

hint:
对于20%的数据，n <= 1000000， k = 10

对于另外20%的数据，n <= 20， k <= 36

对于100%的数据，n <= 10^12，k <= 10^12

## update

1.一组数据

2.K不会==1

3.现在std没有爆long long

4.对数据有问题联系icy （建议大家不要面向数据编程）


title: SAC E#1 - 一道简单题 Sequence2

background: 小强和阿米巴是好朋友。

description:
小强喜欢数列。有一天，他心血来潮，写下了三个长度均为n的数列。

阿米巴也很喜欢数列。但是他只喜欢其中一种，波动数列。

阿米巴把他的喜好告诉了小强。小强便打算找出这三个数列内的最长波动数列。

也就是说，如果我们将三个数列记做a[n][3]，他必须要构造一个二元组序列：<p[i], q[i]>，使得对于任何 i>1 有：

p[i] > p[i-1]

若q[i] = 0，a[p[i]][q[i]] >= a[p[i-1]][q[i-1]]

若q[i] = 1，a[p[i]][q[i]] <= a[p[i-1]][q[i-1]]

若q[i] = 2，只要保持段内同向即可（就是对于连续的一段q[i]=2，要么都有a[p[i]][q[i]] >= a[p[i-1]][q[i-1]]，要么都有a[p[i]][q[i]] <= a[p[i-1]][q[i-1]]）。

小强希望这个二元组序列尽可能长。

提示：当q[i] != q[i-1]时，数列的增减性由q[i]而非q[i-1]决定。

**清晰版题目描述**

小强拿到一个3×n的数组，要在每一列选一个数（或者不选），满足以下条件：

1.如果在第一行选，那它必须大于等于上一个数

2.如果在第二行选，那么必须小于等于上一个数

3.如果在第三行选，对于连续的一段在第三行选的数，必须满足方向相同（都小于等于上一个数或者都大于等于上一个数）

inputFormat:
输入包含4行。

第一行一个数n，表示数列长度。

第2、3、4行，每行n个整数，分别表示三个数列。

outputFormat: 输出仅包含一个整数，即最长波动数列的长度。

hint:
对于20%的数据，n <= 10， m <= 1000

对于60%的数据，n <= 1000,  m <= 1000

对于100%的数据， n <= 100000， m <= 1000000000

其中m = max|a[i]|

样例解释：

取第三行1 2 3（增），然后取第1行6（增），然后取第三行5 4（减），长度为6。


title: SAC E#1 - 一道神题 Sequence1

background: 小强和阿米巴是好朋友。

description:
小强很喜欢数列。有一天，他心血来潮，写下了一个数列。

阿米巴也很喜欢数列。但是他只喜欢其中一种：波动数列。

一个长度为 $n$ 的波动数列满足对于任何 $i\ (1 \le i < n)$，均满足以下两个条件至少一个：

- $a_{2i-1} \le a_{2i}$ 且 $a_{2i} \ge a_{2i+1}$（若存在）。
- $a_{2i-1} \ge a_{2i}$ 且 $a_{2i} \le a_{2i+1}$（若存在）。

阿米巴把他的喜好告诉了小强。小强便打算稍作修改，以让这个数列成为波动数列。他想知道，能否通过仅修改一个数（或不修改），使得原数列变成波动数列。

inputFormat:
输入包含多组数据。

每组数据包含两行：

- 第一行一个整数 $n$ 表示数列的长度。
- 接下来一行，$n$ 个整数，表示一个数列。

outputFormat: 对于每一组输入，输出一行 `Yes` 或 `No`，含义如题目所示。

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

- 对于 $30\%$ 的数据，$1\le n \le 10$。
- 对于另外 $30\%$ 的数据，$1\le m \le 1000$。
- 对于 $100\%$ 的数据，$1\le n \le 10^5$，$m \le 10^9$。

其中 $m = \max|a_i|$（数列中绝对值的最大值）


title: SAC E#1 - 一道大水题 Knight

background: 毒奶色和F91是好朋友。

description:
他们经常在一起玩一个游戏，不，不是星际争霸，是国际象棋。

毒奶色觉得F91是一只鸡。他在一个n×n的棋盘上用黑色的城堡（车）、骑士（马）、主教（象）、皇后（副）、国王（帅）、士兵（卒）摆了一个阵。

然而F91觉得毒奶色是一只鸡。他发起了挑战：他要操纵一个白色骑士，不经过任何一个棋子的攻击范围（F91可以连续行动，而毒奶色的棋子不会动，除非白骑士进入了对方的攻击范围），并击杀毒奶色的国王（即进入黑国王所在的位置）。

请告诉F91他最少需要多少步骤来完成这一项壮举。

注意：

1.当F91的白骑士走到毒奶色的棋子所在的格子上的时候，会击杀（吃掉）该棋子。这个棋子也就不再对F91的白骑士有威胁了。

2.如果白骑士开场就在黑子的攻击范围内，则立刻被击杀、F91立刻失败。

3.即使白骑士在攻击王的瞬间进入了其他棋子攻击范围（即其他棋子“看护”着王所在的格子），依然算F91获胜。

攻击范围：

城堡：横、竖方向所有位置，直到被一个其他棋子阻拦。

```cpp
..#..
..#..
##C##
..#..
..#..
```

骑士：横2竖1或者横1竖2的所有位置（最多8个，类似日字）。

```cpp
.#.#.
#...#
..K..
#...#
.#.#.
```

主教：斜向（45°）所有位置，直到被一个其他棋子阻拦。

```cpp
#...#
.#.#.
..B..
.#.#.
#...#
```

皇后：城堡和主教的结合体（既能横/竖向攻击，也能45°角斜向攻击，直到被其他棋子阻挡）。

```cpp
#.#.#
.###.
##Q##
.###.
#.#.#
```

国王：身边8连通位置的8个格子。

```cpp
.....
.###.
.#X#.
.###.
.....
```

士兵：左下方/右下方（45°）的格子（最多2个）。

`````
.....
.....
..P..
.#.#.
.....
```

其中字母表示棋子类型，参考输入格式。

‘#’表示可攻击范围。

inputFormat:
输入包含多组数据。

每一组数据中，第一行一个整数n表示棋盘规模。

接下来n行，每行一个长度为n的字符串。描述棋盘的格局。

其中：

.表示空

O表示白骑士

C表示黑城堡

K表示黑骑士

B表示黑主教

Q表示黒皇后

X表示黑国王

P表示黑士兵

outputFormat:
对于每一个测试数据，每行输出一个整数，表示F91的最小步数。

如果无论F91如何行动也无法击杀黑国王，输出-1。

hint:
**输入最多包含5组数据。**

对于20%的数据，毒奶色只有国王。n <= 8。

对于30%的数据，毒奶色只有国王、骑士。n <= 8。

对于60%的数据，毒奶色只有国王、骑士、王后。n <= 50。

对于100%的数据，毒奶色可以有全套16颗棋子（2城堡，2骑士，2主教，1后，1王，8兵）。n <= 50。

温馨提示：

时间限制可能比想象之中还要更紧一点，请注意实现细节以保证性能。

样例2解释：

一种可行的做法是：

```cpp
......X.
.3..6...
.O5.....
4.2P.Q.C
1....B..
........
...K....
........
```


title: SAC E#1 - 一道难题 Tree

background: 冴月麟和魏潇承是好朋友。

description:
冴月麟为了守护幻想乡，而制造了幻想乡的倒影，将真实的幻想乡封印了。任何人都无法进入真实的幻想乡了，但是她给前来救她的魏潇承留了一个线索。

她设置了一棵树（有根）。树的每一条边上具有割掉该边的代价。

魏潇承需要计算出割开这棵树的最小代价，这就是冴月麟和魏潇承约定的小秘密。

帮帮魏潇承吧。

注：所谓割开一棵有根树，就是删除若干条边，使得任何任何叶子节点和根节点不连通。

inputFormat:
输入第一行两个整数 $n,\mathrm{root}$ 分别表示树的节点个数和树根。

接下来 $n-1$ 行每行三个整数 $a,b,c$，表示 $a,b$ 之间有一条代价为 $c$ 的边。

outputFormat: 输出包含一行，一个整数，表示所求最小代价。


title: 浮游大陆的68号岛

background:
浮游大陆的 $68$ 号岛，位于浮游大陆的边境地带。平时很少有人造访。

岛上被浓厚的森林覆盖。

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

在这座边境地区不起眼的浮游岛上，建立着神秘的”兵器“管理仓库——妖精仓库。

description:
妖精仓库里生活着黄金妖精们，她们过着快乐，却随时准备着迎接死亡的生活。

换用更高尚的说法，是随时准备着为这个无药可救的世界献身。

然而孩子们的生活却总是无忧无虑的，幼体的黄金妖精们过着天真烂漫的生活，自然也无暇考虑什么拯救世界之类的重任。

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

有一天小妖精们又在做游戏。这个游戏是这样的。

妖精仓库的储物点可以看做在一个数轴上。每一个储物点会有一些东西，同时他们之间存在距离。

每次他们会选出一个小妖精，然后剩下的人找到区间$[l,r]$储物点的所有东西，清点完毕之后问她，把这个区间内所有储物点的东西运到另外一个仓库的代价是多少？

比如储物点$i$有$x$个东西，要运到储物点$j$，代价为

$$x \times \mathrm{dist}( i , j )$$

dist就是仓库间的距离。

当然啦，由于小妖精们不会算很大的数字，因此您的答案需要对19260817取模。

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

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

第二行$n-1$个数，第$i$个数表示第$i$个储物点与第$i+1$个储物点的距离

第三行$n$个数，表示每个储物点的东西个数

之后$m$行每行三个数`x l r`

表示查询要把区间$[l,r]$储物点的物品全部运到储物点x的花费

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

hint:
对于30%的数据，$n , m \le 1000$

对于另外20%的数据，所有储物点间的距离都为1

对于另外20%的数据，所有储物点的物品数都为1

对于100%的数据 ,$ n , m \le 200000 ; a_i , b_i <= 2\cdot 10^9$


title: [TJOI2013] 松鼠聚会

description:
草原上住着一群小松鼠，每个小松鼠都有一个家。时间长了，大家觉得应该聚一聚。但是草原非常大，松鼠们都很头疼应该在谁家聚会才最合理。

每个小松鼠的家可以用一个点 $(x,y)$ 表示,两个点的距离定义为点 $(x,y)$ 和它周围的 $8$ 个点 $(x-1,y)$，$(x+1,y)$，$(x,y-1)$，$(x,y+1)$，$(x-1,y+1)$，$(x-1,y-1)$，$(x+1,y+1)$，$(x+1,y-1)$ 距离为 $1$。

inputFormat: 第一行是一个整数 $N$，表示有多少只松鼠。接下来 $N$ 行，第 $i$ 行是两个整数 $x$ 和 $y$，表示松鼠 $i$ 的家的坐标。

outputFormat: 一个整数，表示松鼠为了聚会走的路程和最小是多少。

hint:
### 样例解释

在第一个样例中，松鼠在第二只松鼠家 $(-1,-2)$ 聚会；在第二个样例中，松鼠在第一只松鼠家 $(0,0)$ 聚会。

### 数据范围

- $30\%$ 的数据，$0\le N \le 1000$；
- $100\%$ 的数据，$0\le N \le 10^5$，$-10^9 \le x, y \le 10^9$。


title: 龙盘雪峰信息解析器

background:
```cpp
薄雾笼罩，远方的雪峰无限迷人，感慨之间，阴影将至。
```
与真程海洋毗邻的龙盘雪山与我们保持着联系，但是龙盘雪山的通讯员常常把信息进行奇怪的加密，然后要我们来破译，很是谨慎。但是，久而久之，我们的通讯员不耐烦了，差点掀桌子砸凳子不干了。所以我们想做一个信息解析器，就是这样。

description:
龙盘雪峰传来的信息都加密成了复杂的代码，我们需要你来做一个程序，按照解析规则解密这些代码，翻译成文字信息，以下是其解析规则：

该代码应为一连串的二进制码（只存在$ 0 $和$ 1 $，做加法时满$ 2 $进$ 1 $，每个$ 0 $或$ 1 $占一个字符），每八个字符为一单元（这也是规则）。

每个单元都有这样的规则：一、若【前三个字符】为$ 101 $时表示需要转换为字母$ A-Z $，字母$ A $代码为$ 10100000 $，字母$ C $为$ 10100010 $，$ 26 $个**大写字母**以字母表顺序按照这种规律顺序排列，分别对应一个二进制代码。二、若【前三个字符】为$ 111 $，则该单元翻译为空格。三、若【第一个字符】为$ 0 $，则该单元表示一个数，待定**与下一个单元所表示的数做加法**。加法过程中，这两个单元应转换为十进制，然后除以$ 2 $并**舍弃余数**才相加，加法结束后，这两个单元做加法得到的结果即为这两个单元的翻译结果（翻译结果用十进制表示，**这两个单元**就都翻译完毕了，详见样例$ 3 $）。

由于保险，龙盘雪峰经常发送【假代码】，而假代码则不存在上述规则，如果是假代码，**仅**输出$ Error $。

inputFormat: 输入仅一行，包含一串连续的代码（长度不超过$ 171111 $个字符），中间不会出现空格，保证不出现空代码。

outputFormat:
输出仅一行，包含一个字符串，是二进制代码按照上述规则翻译后的文字信息。

若该二进制代码中存在假代码信息，则**只**输出$ Error $。

samples: IOIOOOOI Error

hint:
### 样例一说明：

$ 10100000 $代表$ A $，下一个单元开头为$ 111 $，那么翻译为空格，再下一个单元开头为$ 101 $，后接$ 01111 $，比$ A $多了$ 2^0+2^1+2^2+2^3=15 $，那么代表的就是$ P $了，以此类推，最后翻译为$ A\;PIG $。

### 注意：

对于规则一的解释：$ 26 $个大写字母按照字母表的顺序排列，以$ A=10100000 $开始，往后的每一个字母的二进制码的值都比前面一个字母的二进制码的值多$ 1 $（注意满二进一）；

此题目有误解题意的现象，请一定要看清楚题目，搞清楚逻辑关系，注意细节！


title: [Ynoi2016] 炸脖龙 I

background:
备餐时光，软泞蜥獾

草地中钻孔，日晷下打转

波若歌鹦苟延残喘，迷途绿龟嚎哮迷茫

“当心炸脖龙，我的孩子！

那锋爪利颚，能挠钩撕咬！

注意秋布秋布鸟，你需回避，

那暴躁冒烟恶怪大毛怪！”

手持宝剑鸣真理之语：寻觅强敌豪壮永不息——于噹噹树下稍事休憩，伫立良久，深陷思绪。

当思绪纷乱杂绪之际，炸脖龙双目如烔炬，从阴暗密林奔跃闯出，一路悲鸣低吟时啭啼！

一，二！一，二！一刺再刺，真理之语将敌斩成糜！

取其首级，置之死地，

伴随胜利，驰马归疾。

“真当是你把怪龙斩于马下？

奋勇吾儿！

来我怀里！奔走相告！衣锦还乡！

父喜不自禁窃鸣得意

波若歌鹦苟延残喘，

迷途绿龟嚎哮迷茫，

备餐时光，软泞蜥獾

草地中钻孔，日晷下打转

波若歌鹦苟延残喘，

迷途绿龟嚎哮迷茫”

——《炸脖龙之诗》

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

我喊了出来...却不成人话

只能，像在水中一边融化一边下沉的方糖一样...

失去自己的轮廓...一直沉向最低处

想要爬上去的子午

维持自己是自己的连续体...

溶解的渐渐七零八落的意识...

失去了用来挣扎的双手

失去了用来挣扎的双臂

向下，

向下，

一直沉下去

向着意识的底层

沉陷下去的自我...

逐渐消失的世界...

我看到了世界

失落的...世界...

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

```plain

   回归天空的话我就可以成为      了

  开什么玩笑，你才不是什么      ！

  吵死了！吵死了！我是      ！而且生来就是！

就是因为这个家伙我才失去      的资格的！

 呜呜呜，由岐姐姐，由岐姐姐！

  ...怎么会...由岐姐...

 卓司！你这家伙！

        吵死了吵死了！像你这样的普通人懂些什么！

   由岐的血慢慢在冰凉的水泥地上扩散开来

   抱在怀里的      在渐渐地流出来        本应成为      而出生

的我的被      妨碍了！

不出生的话我就没法拯救是这个世界！

            所以预言者说能当世界回归天空的此处就是尽头

   只要      回归天空的话！

 我有这么可怕吗？

              因为我是要对一切生物下达审判的存在！

       因为哥哥是凡人呢

    凡人与天才

                            救世主

   世界

                    救世主

                回天之门

  要死的是你！

            我不会死               不会死       诅咒你

       要死的是羽咲

         只要羽咲死了

                  间宫              皆

                                    守           由

                         岐

                                间宫羽咲

                          可能性

                                    和镜

                     终

                   终之空

                     空

```

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

一个婴儿出生了

谁的？

不知道

虽然不知道...
但确实有一个婴儿出生了

嗯...那个婴儿在哭...

呜嘎，呜嘎，地哭着...

听到这个哭声大家都笑了

大家都在为婴儿祝福

母亲也是...

父亲也是...

并且其他人也是...

为那个婴儿的出生...

衷心祝福

世界充满着生命的祝福

但是

但不是这样的

在那里

我

我一个人在那里恐惧着

非常恐惧...

要说为什么的话...

因为那是在对世界进行诅咒

没错...

他在诅咒着那个世界，那个刚出生的婴儿

诅咒着自己的出生

我

我当场全身僵硬

在大家的笑容之中

在祝福之中

独自一人...

我啊...

我摇摇晃晃地...

接近那个婴儿

然后想要让那个婴儿停止哭泣

我想着必须要那样做才行

为什么呢？

我自己也不明白...

那是

那是，自从出生以来

就悲惨地活到今天的我能做到的

我能做到的

唯一的

唯一的赎罪啊。

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

让我在这里了结了你吧…间宫卓司

这里是终之空的下面吧…这不刚好吗

跟我们的终结很相称不是吗…

这里，是只对你而言的，终结的天空…

这里就是终焉之地…

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

“不行！绝对不行！”

…为什么…跟过来了…

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

预定…调和吗…

原来如此…看来不管怎样对于你来说…我都已经毫无任何价值了对吧…

竟然被这家伙打倒了…真是没办法呐…

这也是现实吗…

那就接受吧…

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

不知为何，我好像看到了在夜空中挺立的向日葵…

只有一瞬间…

那株向日葵…

好像在某个地方…

向日葵…

跟羽咲一起…

是啊…

我是哥哥啊…

要是…能再多当当她的哥哥就好了……

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

咦……

刚才的…

那个是…那片风景…

是吗…那片风景…

我也是知道的啊…

在坡道途中的向日葵…

蔚蓝的天空和向日葵。

漂浮着大大的云朵…

羽咲戴着大大的帽子…

然后跟我走在一起…

走着走着…

为了…

两人一起…

爬上那个坡道…

因为…那个坡道的前面有很漂亮的景色…

description:
您正在打 galgame，然后您觉得这个 gal 不知所云，于是您弃坑了，开始写数据结构题：

给一个长为 $n$ 的序列，$m$ 次操作，每次操作：

1. 区间 $[l,r]$ 加 $x$；
2. 对于区间 $[l,r]$，查询：

$$a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \mod p$$

inputFormat:
第一行两个整数 $n,m$ 表示序列长度和操作数。

接下来一行，$n$ 个整数表示这个序列。

接下来 $m$ 行，可能是以下两种操作之一：

- $1\ l\ r\ x$ 表示区间 $[l,r]$ 加上 $x$；
- $2\ l\ r\ p$ 表示对区间 $[l,r]$ 进行一次查询，模数为 $p$。

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

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

对于100%的数据，$n , m \le 500000$ , 序列中每个数在$[1,2\cdot 10^9]$内，$p \le 2 \cdot 10^7 $, 每次加上的数在$[0,2\cdot 10^9]$内

共10组数据


title: Coloring

description:
$\text{Snakes}$正在玩游戏，他在一张画有$n*m$个格子的白纸上给方格染色。然而，杂乱无章的染色并不有趣，所以他想出了一个奇怪的问题：

在$n*m$的方格中用$c$种不同的颜色尝试将所有方格染色，不同的颜色用$1..c$间的整数表示。染色需要满足以下条件：

+ 每个方格只能且必须染一种颜色。

+ 第$i$种颜色最多可以且必须染$p_i$个格子，保证满足$\sum_{i=1}^cp_i=n*m$。

+ 将每个格子上下左右与其颜色相同的格子视为位于同一个联通块内，并定义不同联通块之间的方格边的条数为$q$。可参考样例说明。

现在，$\text{Snakes}$想知道，如果给出$n,m,c$以及$p_1..p_c$，你能够构造出的符合条件且$q$尽量小的染色方案。

inputFormat:
第一行，三个数，$n,m,c$。

第二行，$c$个数，第$i$个数为$p_i$。

outputFormat: 输出共$n$行，每行$m$个数，表示你构造出的$n*m$的$q$尽量少的染色方案。

hint:
```plain
   |   |
 2 | 3 | 1
   +   +---
 2 | 3   3
   |
```

对于样例，有$q=4$，其中三条竖边，一条横边。

#### 约定

本题为 Special Judge。

对于每个测试点，将会设置阈值$w$，并保证存在构造使得$q\leq w$。

对于程序输出的答案，我们将会以以下方式计算得分：

$$\begin{matrix}q&score&q&score\\\\ q \leq w&10&1.75w < q \leq 2w&5\\\\ w < q \leq 1.1w&9&2w < q \leq 2.3w&4\\\\ 1.1w < q \leq 1.25w&8&2.3w < q \leq 2.6w&3\\\\ 1.25w < q \leq 1.5w&7&2.6w < q \leq 3w&2\\\\ 1.5w < q \leq 1.75w&6&3w < q \leq 3.5w&1\end{matrix}$$

若$q > 3.5w$，将以 `Wrong Answer` 处理。

比赛时显示的得分即为最后得分。

#### 数据规模

对于$10\%$的数据，有$1\leq n,m\leq 3$，$c\leq 3$。

对于$30\%$的数据，有$1\leq n,m\leq 8$，$c\leq 6$。

对于$50\%$的数据，有$1\leq n,m\leq 15$，$c\leq 25$。

对于$100\%$的数据，有$1\leq n,m\leq 20$，$c\leq 50$，$p_i\leq 20$。


title: Changing

description:
有 $n$ 盏灯环形排列，顺时针依次标号为 $1\cdots n$。初始时刻为 $0$，初始时刻第 $i$ 盏灯的亮灭 $a_i$ 给定，$0$ 表示灭，$1$ 表示亮。下一时刻每盏灯的亮灭取决于当前时刻这盏灯与顺时针方向下一盏灯的亮灭。若两盏灯状态相同，则下一时刻该灯灭，否则该灯亮。

试求时刻 $t$ 第 $k$ 盏灯的状态。

inputFormat:
第一行，三个整数，分别为 $n, t, k$。

第二行，共 $n$ 个整数，分别为 $0$ 或 $1$，代表 $a_i$。

outputFormat: 共一行，一个数，$0$ 或 $1$，代表时刻 $t$ 第 $k$ 盏灯的状态。

hint:
- 对于 $25\%$ 的数据，有$1\leq t, k\leq n\leq 1000$。
- 对于 $60\%$ 的数据，有$1\leq t, k\leq n\leq 10^5$。
- 对于 $100\%$ 的数据，有$1\leq t, k\leq n\leq 3\times 10^6$。


title: [SHOI2013] 阶乘字符串

background:
shoi2013d1t2

（本题卡常数注意）

description:
给定一个由前 $n$ 个小写字母组成的串 $S$。串 $S$ 是阶乘字符串当且仅当前 $n$ 个小写字母的全排列（共 $n!$ 种）都作为的子序列（可以不连续）出现。

由这个定义出发，可以得到一个简单的枚举法去验证，但是它实在太慢了。所以现在请你设计一个算法，在 $1$ 秒内判断出给定的串是否是阶乘字符串。

inputFormat:
输入第 $1$ 行一个整数 $T$，表示这个文件中会有 $T$ 组数据。

接下来分 $T$ 个块，每块 $2$ 行：

- 第 $1$ 行一个正整数 $n$，表示 $S$ 由前 $n$ 个小写字母组成。
- 第 $2$ 行一个字符串 $s$。

outputFormat: 对于每组数据，分别输出一行。每行是 `YES` 或者 `NO`，表示该数据对应的串 $S$ 是否是阶乘字符串。

hint:
第一组数据中，`ab` 这个串没有作为子序列出现。

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


title: [SHOI2013] 超级跳马

description:
现有一个 $n$ 行 $m$ 列的棋盘，一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列，且跳到本行或相邻行。跳越期间，马不能离开棋盘。例如，当 $n = 3$，$m = 10$ 时，下图是一种可行的跳法。

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

试求跳法种数对 $30\,011$ 取模的结果。

inputFormat: 仅有一行，包含两个正整数 $n, m$，表示棋盘的规模。

outputFormat: 仅有一行，包含一个整数，即跳法种数模 $30\,011$ 后的结果。


title: [Ynoi2011] 初始化

background:
我呢…是什么时候开始存在于此的呢？

从何时开始…我成为了我呢？

仔细想想，我从出生开始似乎也没有什么记忆？

这么说明天的“我”和今天的“我”是同一个存在吗？

或者说…如何定义“我”这个存在呢？

“我”这个存在真的存在吗？

如果存在的话…意义又是什么呢？

等等…如何定义“意义”呢？

意义…意义…意义…意义…意义…意义…意义…意义…

…………………………………………

他当然想不通这些问题

于是自然而然地去问大人，就像一个小孩子应该做的一样

“爸爸，活着的意义是什么啊？”

“等你长大了就知道了，现在先好好学习吧”

“妈妈，活着的意义是什么啊？”

“小孩子想这些事干啥呢，先把成绩搞好再说”

“老师，活着的意义是什么啊？”

“好好学习，把成绩搞好，考上好大学，找个好工作，然后赚大钱”

原来如此啊，原来这就是意义呢

虽然这是意义，但是感觉真是无趣呢，真是可悲呢

但是，这是意义啊，不管多么的无趣，多么的可悲，既然是意义，那一定要努力
实现呢，因为这毕竟是意义啊~！

于是他开始好好学习了，由于天资还不错，所以考上了好的初中，进入了最好的
班级，似乎未来一片光明呢

实际上，他当时也确实是这么想的呢（笑

【记得配图，内容待定】

由于这是Ynoi，不是出题人拿来写傻逼的文字的地方，所以你需要做一个数据结构题：

description:
Mayuri 有 $n$ 颗星星，每颗星星都有一个明亮度 $A_{i}$ 。Mayuri 时常想知道一个区间 $[l,r]$ 内所有星星的明亮度的总和是多少。但是星星是会眨眼的，所以星星的明亮度是会变化的。有的时候，下标为 $y,y+x,y+2x,y+3x,\ldots,y+kx$ 的星星的明亮度会增加 $z$。保证 $y\leq x$。

Mayuri 不怎么会数学，请回答她的询问。答案要对 $10^{9}+7$ 取模。

inputFormat:
第一行两个整数 $n$ 和 $m$，分别表示星星的数量和操作的数量。

接下来一行 $n$ 个数字 $A_{i}$，表示初始的明亮度。

接下来 $m$ 行，每行先是一个整数表示操作类型，如果为 $1$ 则是修改操作，接下来 $3$ 个整数 $x,y,z$；如果是 $2$ 则为询问操作，接下来两个整数 $l,r$。

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

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

对于 $10\%$ 的数据，满足 $n,m\leq 1000$。

对于另外 $10\%$ 的数据，满足 $x>1000$。

对于另外 $10\%$ 的数据，满足 $x>300$。

对于另外 $10\%$ 的数据，满足 $n,m \leq 10^5$。

对于 $100\%$ 的数据，$1\leq n,m\leq 2\times 10^5$，$1\leq y\leq x\leq n$，$1\leq l\leq r\leq n$，$0\leq A_i,z \leq 10^{9}+7$。


title: 数据结构

background:
**引言**

数据结构学的好，未来工作没烦恼。

![](https://timgsa.baidu.com/timg?image&quality=80&size=b9999\_10000&sec=1508946101936&di=0c08b703e466d2a3b2d20dd8008821fc&imgtype=0&src=http%3A%2F%2Fjoymepic.joyme.com%2Farticle%2Fuploads%2Fallimg%2F201511%2F1446516425349678.gif)

Edgration 是一个喜欢乱搞数据结构的蒟蒻（以下简称edt），有一天，他作死想去刁难一下dalao：

edt想求一种数据结构，使得可以实现区间加，求出某一区间大于k的元素的个数

dalao1：sb线段树

dalao2：sb分块

dalao3：sb平衡树

edt: 不行，那就加上取模，求区间取膜mod后大于MIN小于MAX的元素个数

dalao1：线段树&……￥#&……%……&\*&%￥

dalao2：sb分块 &%￥……%#￥#&……&\*

dalao3：\*&……%&￥LCT维护SBT水题 &……%&……%

edt：那不仅取模，每个数乘上数组下标再取模

dalao：￥%￥￥&\*（#￥% 叽里呱啦叽里呱啦

edt：不行，在把取模的值丢到一棵树上，维护一棵仙人掌乘积方差的最小极差

dalao：替罪羊树上用sb块状链表维护Toptree上的最小费用最大流和可持久化仙人掌，算出来在基尔霍夫矩阵中反演后跑一遍fft维护的插头DP就好了，给我三分钟轻松水过。。

edt：mmp

description:
蒟蒻Edt把这个问题交给了你 ———— 一个精通数据结构的大犇，由于是第一题，这个题没那么难。。

edt 现在对于题目进行了如下的简化：

最开始的数组每个元素都是0

给出$n$，$opt$，$mod$，$min$，$max$，$mod$在int范围内

操作$A$，$Q$

$A$: $L$,$R$,$X$ 表示把$[l,R]$这个区间加上$X$

**（数组的从L到R的每个元素都加上X）**

$Q$: $L$,$R$ 表示询问$[L,R]$这个区间中元素T满足  $min<=(T*i$%$ mod)<=max$  的 T这样的数的个数（i是数组下标）

**（元素的值\*数组下标%mod在min到max范围内）**

由于 edt 请来了一位非三次元的仓鼠，他帮你用延后了部分问题，将这些询问打入了混乱时空，你的询问操作不会超过1000次，不幸的是，对于延后的询问操作可能有很多次（小于1e7次），但是保证这些延后的询问操作之后不会再次有修改操作

（就是在最后会有很多次询问，但不会进行修改）

inputFormat:
给出n，opt，mod，min，max表示序列大小，操作次数，取膜，最小值，最大值

下面opt行，给出

$A$: $L$，$R$，$X$表示区间加，保证X在int范围内(<2147483647）

$Q$：$L$，$R$表示区间查询满足条件的个数

再给出一个$Final$值，表示后面有$Final$个询问

下面$Final$行，给出

$L$，$R$表示询问区间$[L,R]$表示询问$[L,R]$之间满足条件的个数

outputFormat:
每行对于每个$Q$操作输出$Q$个数表示每次询问的值，

下面$Final$行表示$Final$个询问的值

hint:
## 样例说明

给出样例1的解释：

样例1中，$a$数组修改为$5$，$5$，$5$

每个$a[i]*i$%$4$ 的值为$1$,$2$,$3$

对于Final的询问

询问$[1$，$3]$中大于等于0小于等于2的个数为2个

剩下的询问类似

## 题目说明

**注意**：

### 1.关于负数取模问题，请以 c++ 的向0取整为标准，即如：

[ $ -7 $%$ 3 = -1 $ ]  [ $ 7 $%$ 3 = 1 $ ]

### 2.一共会有50个测试点，每个点分值为2分。

因为测试点数较多，请oier们自觉地不要故意多次提交来卡评测机，出题人 edt 在这里表示由衷的感谢

## 数据范围

如果你不能作对所有点，请尝试获得部分分，所有数据都是随机生成

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


title: 答案错误

background:
小 X 比较差，她（她？tan90°）有许多 WA 掉的题，所以她很难受。小 Z 决定去安慰她，可是他的提交记录里一道 WA 都没有（flag），于是他决定篡改一半题的署名，让小 X 觉得他们的错题相当，这样她会好受一些。

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

description:
每道 WA 了的题都会有一个分数，对于两个人的 WA 题程度是否相同，小X有这样一个评判方法：

无聊的她想了这样一个神奇的函数：

$$f(x)=a_1x^0+a_2x^1+a_3x^2+\cdots+a_{n}x^{n-1}$$

她认为，无论 $a_i$ 取什么值，两组 $f(x)$ 的和都相等，则这两组题的错误程度很相似。

假如有分值为 $A=\{1,4,6,7 \},B=\{2,3,5,8\}$ 的两份被篡改完成的 WA 题，当 $a_1=a_2=a_3=1$ 时，神奇的函数为：

$$f(x)=x^2+x+1$$

那么，$f(1)=3,f(2)=7,f(3)=13\cdots$

显然：$ f(1) + f(4) + f(6) + f(7) = 124 = f(2) + f(3) +f(5) +f(8)$。

对于这组系数，此分组方案是合法的，可以证明，$a_i$ 取任意值，按照以上方案分组都满足条件（两组的 $f(x)$ 和相同），不信可以手动枚举（#滑稽）。

所以，$A=\{1,4,6,7 \},B=\{2,3,5,8\}$。就是一种合法的分组。

inputFormat:
第一行一个整数 $n$，代表有 $2^n$ 道 WA 题，分值分别从$1$ 到 $2^n$，满足 $n\ge 2$。

第二行一个整数 $q$，表示有 $q$ 组询问。

最后一行 $q$ 个整数，询问分值为 $x$ 的 WA 题是谁的名字。

（因为小 X 比较菜，所以我们认为分值为 $1$ 的 WA 题是属于她的）

outputFormat: 一共 $q$ 行，每行一个字符 $\verb!X!$ 或 $\verb!Z!$，表示分值为 $x$ 的 WA 题是谁的署名。


title: 部落冲突

background:
在一个叫做 Travian 的世界里，生活着各个大大小小的部落。其中最为强大的是罗马、高卢和日耳曼。他们之间为了争夺资源和土地，进行了无数次的战斗。期间诞生了众多家喻户晓的英雄人物，也留下了许多可歌可泣的动人故事。

![](http://img4.dwstatic.com/coc/1602/320370032694/1456415099616.jpg)

其中，在大大小小的部落之间，会有一些道路相连，这些道路是 Travian 世界里的重要枢纽，简单起见，你可以把这些部落与部落之间相连的道路看作一颗树，可见每条道路对于 Travian 世界的重要程度。有了这些道路，建筑工人就可以通过这些道路进行友好外交啦。

然而，事情并不会像想象的那样美好，由于资源的匮乏，相邻的部落（由一条道路相连的部落）之间经常会发生大大小小的冲突事件，更有甚者，会升级为部落之间的大型战争。

为了避免误伤，每当两个相邻的部落之间发生大型战争之时，这两个部落间的道路是不允许通行的，对于一些强大的部落，甚至能与多个相邻的部落同时开战，同样的，这些战争地带的道路十分危险，是不可通行的。

天下之势，分久必合，当两个部落经历了不打不相识的苦战之后，他们可以签订停战协议（暂时停战，以后依旧可能再次开战），这样，两个部落之间的道路又会重新恢复为可通行状态，建筑工人们又可以经过此地购买最新的大本营设计图纸来强大自己的部落了。

为了简单起见，我们把各大战争事件按发起的时间顺序依次编号（最先发起的战争编号就为 $1$，第二次战争编号就为 $2$，以此类推），当两个部落停战之时，则会直接告诉你这场战争的编号，然后这场战争就载入了史册，不复存在了，当然，这并不会影响到其他战争的编号。

建筑工人十分讨厌战争，因为战争，想从一个部落到另一个部落进行友好交流的建筑工人可能就此白跑一趟。所以，在他们出发之前，都会向你问问能不能到达他们想去的部落。

description:
简单起见，你就是要处理下面三件事，所有的事件都是按照时间顺序给出的。

1. `Q p q` 从第 $p$ 个部落出发的建筑工人想知道能否到达第 $q$ 个部落了，你要回答的便是 `Yes` / `No`，注意**大小写**。

2. `C p q` 第 $p$ 个部落与第 $q$ 个部落开战了，保证他们一定是相邻的部落，且目前处于停战（未开战）状态。

3. `U x` 第 $x$ 次发生的战争结束了，它将永远的被载入史册，不复存在（保证这个消息不会告诉你多次）

inputFormat:
第一行两个数 $n$ 和 $m$， $n$ 代表了一共有 $n$ 个部落，$m$ 代表了以上三种事件发生的总数。

接下来的 $n - 1$ 行，每行两个数 $p, q$，代表了第 $p$ 个部落与第 $q$ 个部落之间有一条道路相连。

接下来的 $m$ 行，每行表示一件事，详见题目描述。

outputFormat: 每行一个 `Yes` 或者 `No`，表示从第 $p$ 个部落出发的建筑工人能否到达第 $q$ 个部落。

hint:
对于 $30\%$ 的数据，$n, m\leq 6\times10^3$。

对于另 $30\%$ 的数据，保证部落之间的地理关系是一条链，且 $i$ 与 $i + 1$ 之间有一条道路。

对于另 $30\%$ 的数据，$n, m\leq 10^5$。

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


title: [TJOI2013] 循环格

background: 一个循环格就是一个矩阵,其中所有元素为箭头,指向相邻四个格子。每个元素有一个坐标(行,列),其中左上角元素坐标为(0,0)。给定一个起始位(r,c),你可以沿着箭头方向在格子间行走。即:如果(r,c)是一个左箭头，那么走到(r,c-1);如果是一个右箭头,走到(r,c+1);如果是上箭头,走到(r-1,c);如果是下箭头,走到(r+1,c)。每一行和每一列都是循环的,即如果走出边界,你会出现在另一侧。比如在一个5\*5的循环格里,从(3,0)向左走会出现在(3,4)。

description:
一个完美的循环格是这样定义的:对于任意一个起始位置,你都可以沿着箭头最终回到起始位置。如果一个循环格不满足完美,你可以随意修改任意一个元素的箭头直到完美。例如下图,左边不是一个完美的循环格,因为只有从(1,1),(1,2),(2,0),(2,3)出发才会回到起始位置。通过修改其中两个箭头,可以得到右图,一个完美的循环格。

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

给定一个循环格,你需要计算最少需要修改多少个元素使其完美。

inputFormat: 第一行两个整数R和C,表示循环格的行和列。接下来R行,每一行包含C个字符LRUD表示左右上下

outputFormat: 一个整数,表示最少需要修改多少个元素使得给定的循环格完美。

hint:
### 数据范围

30%的数据，1 ≤ R, C ≤ 7

100%的数据，1 ≤ R, C ≤ 15


title: 肮脏的牧师

background: @Yumis 出题人在这里哦~

description:
Yumis最近在玩炉石传说。

在炉石传说中脏牧有一张一费卡片（一费就是使用要消耗1点法力水晶），叫做疯狂药水，这个的效果是将一个敌方场上攻击小于等于2的随从拉到自己的战场内。

还有一张四费卡片叫做暗影狂乱，这个的效果是将一个敌方场上攻击小于等于3的随从拉到自己的战场内。

还有一张一费卡片就是缩小药水，这个的效果是将敌人全场的随从攻击力下降3点。

你PY了炉石的GM所以你有了无数张的这三种卡片，但是GM告诉你缩小药水是这个牌比较不好创建，为了为GM着想你必须在使用**最少的缩小药水**的情况下A爆对手的脸。

现在你的对手场上有n个随从，每个随从的攻击力是ki点。

你的对手有m点血量。

而你现在要做的就是将敌方的场上的随从拉过来自己的场上并攻击对手（每一个随从只能攻击一次，攻击力为你拉过来的时候随从剩余的攻击力），A爆对面的脸（将对面的血打到0点及以下）。

inputFormat:
第一行用一个空格隔开的两个整数n,m分别代表敌方场上的随从数量和你对手的血量。

第二行n个整数每两个整数之间用一个空格隔开，分别代表敌方场上每一个随从的攻击力ki。

outputFormat:
一行如果可以A爆则输出**最少使用的缩小药水的数量**和此时使用的法力水晶，两个数据之间用一个空格隔开（如果有多个答案则输出消耗法力水晶最少的答案）。

否则输出“Human Cannot Win Dog”（没有双引号）

hint:
样例说明1：

敌方场上有3只随从，敌方有5点血量

我们把3攻随从和2攻随从拉过来花费0个缩小药水和5点耗费（一张疯狂药水一个暗影狂乱（1+4 = 5））伤害足够击杀对方。

样例说明2：

使用16个缩小药水（下面数据后面第一个括号指拉过来的时候伤害为多高 ，第二个括号表示拉过来的时候使用多少的缩小药水）

拿10（1）（3）、20（2）（6）、30（3）（9）、50（2）（16）攻的怪物总共造成8点伤害 刚好A爆！

Easy : 保证 0 < n <= 10  并且不存在用到暗影狂乱和缩小药水的情况    20%

Normal ：保证 0 < n <= 10  并且不存在用到缩小药水的情况           20%

Hard ：保证 0 < n <= 10                                                 30%

Extra：保证0 <= n <= 5000000(6个0)，最大攻击力小于30000                  30%

保证 0 < n <= 5000000     0 < ki <=30000    0<=m<=5000000 (6个0)


title: 三体问题【std 疑似有误】

background:
@FirstLight0521 出题人在这里哦~

三体人所居住的星系由于三体运动的不确定性而导致三体星人生活动荡不安，善良的人类程序员（也就是你了！伟大的英雄！）决定帮助愚蠢得连程序都不会写的三体星人模拟天体的运动轨迹。这时，无聊的“歌者”文明决定戏弄一下你，于是给三体星系添加了一些新的星体。

description:
输入 $N$ 个天体与他们在空间中的坐标 $(x_i,y_i,z_i)$、初速度 $(v_x,v_y,v_z)$ 与质量 $M_i$，已知三体世界受到“歌者”影响时间的流动不是连续的（每 $0.01$ 秒钟刷新一次），天体均视为质点，求 $t$ 时刻所有天体的坐标。

本题万有引力常数 $G$ 取 $6.67408 \times 10^{-11}$，在代码中可以写成：

```cpp
#define G 6.67408e-11
```

当你的答案与标准答案的相对误差不超过 $0.5 \%$ 的时候，你在本测试点得到 AC。也就是说，保留多少位小数你可以自行确定。标准答案将会保留 $12$ 位小数。本题开启 SPJ 判断你的答案是否正确。

inputFormat:
第一行一个正整数 $N$ 和一个非负实数 $t$，分别表示天体数与时刻。

接下来 $N$ 行，每行 $7$ 个实数 $x_i,y_i,z_i,M_i,v_x,v_y,v_z$，分别表示各天体坐标、质量与初速度（三个方向上的分速度）。

outputFormat: $N$ 行，每行为第 $i$ 个天体在 $t$ 时刻的坐标 $x_i,y_i,z_i$，以单个空格隔开。

hint: $3 \le N \le 30,0 \le t \le 100,-100 \le x_i,y_i,z_i \le 100$。$M_i$ 在 `long long` 范围内。


title: ことりのおやつ（小鸟的点心）

description:
这是2017年的冬天。（又到了白色相簿的季节2333）

![滑雪鸟](https://db.loveliv.es/png/navi/476/0)

滑完雪之后，ことり突然想吃点心啦！于是她去了甜品店。

日本的冬天经常下雪。不幸的是，今天也是这样，每秒钟雪的厚度会增加q毫米。

秋叶原共有n个地点，编号从1到n。每个地点在开始的时候的积雪高度为hi。

有m条**双向**道路连接这些地点，它们的长度分别为wi米。

雪太大，公共交通系统已经停摆了，所以ことり得走路回家。她走路的速度是1m/s。

为了方便地图的绘制，秋叶原的道路规划使得每条道路严格地连接两个不同的地点，并且不会有两条道路连接的地点相同。

每个地点都有一个极限雪高li，单位是毫米，如果到达这个地点的时候，这里的雪的高度高于li则会被困在这个点走不出去，无法成功地走到ことり家。

点心店这个地点的编号是s，ことり家的编号是t。

不考虑点心店和ことり家的雪。

ことり想在g秒内回到家吃点心，越快越好。如果在g秒之内，ことり无法到家，或者她被困在路上了，那么ことり会把wtnap变成她的点心( ・ 8 ・ )

inputFormat:
第1行6个整数，空格隔开，分别代表n，m，s，t，g，q。

以下n行，每行2个整数，空格隔开，分别表示这个地点的hi和li。

以下m行，每行3个整数，空格隔开，分别表示这条路连接的两个地点u, v和这条路的长度wi。

outputFormat:
输出1行1个整数，表示到达ことり家的最短用时。

如果wtnap变成了ことり的点心那么输出"wtnap wa kotori no oyatsu desu!"

输出时不含引号。

hint:
对于0%的数据，与样例一模一样；
对于40%的数据，q = 0。
对于上一行中50%的数据，所有wi < li。
对于100%的数据，1 ≤ s, t ≤ n;  0 ≤ g, q ≤ 10^9; 0 ≤ wi ≤ li ≤ 10^9。

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


title: 肝活动

background: Yume 最近在玩一个名为《LoveLive! School idol festival》的音乐游戏。他之所以喜欢上这个游戏，是因为这个游戏对非洲人十分友好，即便你脸黑到抽不出好卡，还可以通过在每个月举办的两次活动中达成一定的目标来获得奖励。

description:
Yume 很喜欢这一期活动奖励卡的卡面，于是他决定要肝这一期的活动，拿到活动奖励。这一期的活动规则很特殊，玩家需要在活动规定的结束时间前，完成所有指定的歌曲（**每首歌曲只能打一次**），并获得一定的分数，就可以拿到活动奖励。如果在规定的时间前没有完成所有的歌曲，或者分数不够奖励的分数线，则不能领取活动奖励。每首歌有一个限定的奖励开放时间，玩家如果在这段时间内完成了这首歌，便可以获得一定的分数（**获得的分数 = 开放时间 - 当前已用的总时间**）。如果超出了这段时间之后再完成这首歌，就不能获得分数了。

这样的规则对 Yume 这样的老玩家来说本应是轻而易举，但不巧的是 Yume 把活动的结束时间记成了活动的开始时间，以至于当他上线跃跃欲试的时候，惊恐地发现活动已经快要结束了。现在他想知道，在剩余的时间之内，他能否完成所有的歌、达成奖励的分数线拿到活动卡。为了节省时间，他把这个问题交给了你来解决。请你根据给定的数据，帮他计算出能否在剩余的时间内达成目标。如果能，请告诉他完成每首歌曲的顺序。

inputFormat:
输入的第一行是三个整数 $n,m,t$，分别表示规定完成的歌曲数目、获得奖励需要达到的最低分数和距离活动结束剩余的时间。

接下来有 $n$ 行，第 $i$ 行有一个字符串 $S_i$ 和两个整数 $T_i$ 和 $M_i$，表示第 $i$ 首歌的歌名为 $S_i$，完成第 $i$ 首歌所需要的时间为 $T_i$，第 $i$ 首歌的奖励开放时间剩余 $M_i$。保证 $T_i\le M_i$。其中数据已按 $S_i$ 的字典序给出。

outputFormat:
如果在活动结束前 Yume 可以完成指定的目标拿到奖励，则在第一行输出一个整数 $C$，表示在获得奖励的前提下，所能够获得的分数的最大值；

接下来的 $n$ 行中，按照完成歌曲的顺序输出第 $i$ 首歌的歌名。如果有多种可能性，则输出字典序最小的情况。

如果在活动结束前 Yume 不能完成所有的歌曲，输出 `No Answer`。

samples:
3 2 10
BokutachiwaHitotsunoHikari 3 8
Korekara 1 2
SnowHalation 2 5

samples:
6
SnowHalation
BokutachiwaHitotsunoHikari
Korekara

samples:
2 1 2
AoizoraJumpingHeart 1 2
TimeLapse 2 4

hint:
对于 $0\%$ 的数据，与测试数据完全相同。

对于 $20\%$ 的数据，满足 $n \le 5$。

对于 $40\%$ 的数据，满足 $n \le 9$。

对于 $70\%$ 的数据，满足 $n \le 15$。

另有 $10\%$ 的数据满足 $\sum\limits^{n}_{i=1} T_i < t$。

对于 $100\%$ 的数据，满足 $n \le 22$，$S_i$ 的长度不超过 $50$。保证 $m,t,M_i,T_i$ 及其相加的结果都在 `int` 最大范围内。


title: 大河的序列

background:
“唯有龙虎相伴 最是脉脉深情”

题目来源：[KingSann](https://www.luogu.org/space/show?uid=47111)

description:
大河有一些袜子，但经常十分散乱的堆放着。

有一天龙儿忍不住了，于是将袜子放到了一个序列上（称作袜子序列）。

每个袜子都有一个$dirty$值，定义袜子序列的$dirty$值为 $ \max  \left( (dirty_{l} \ bitand \ dirty_{l+1} \ bitand \ \cdots \ bitand \ dirty_{r}) + (dirty_{l} \ bitor \ dirty_{l+1} \ bitor \ \cdots \ bitor \ dirty_{r}) \right) $ ，其中 $ dirty_{i} $ 表示 第 $ i $ 只袜子 的 $ dirty $ 值，$bitand$表示按位与（C++中是`&`），$bitor$表示按位或（C++中是`|`）。

简而言之，就是找一段连续子序列，使得所有数字的按位与加上按位或最大。

如果这个袜子序列的$dirty$值达到了某个**阈**值，那么龙儿会讨厌大河的。

大河当然不希望这样了，于是她想知道这个袜子序列的$dirty$值是多少。

inputFormat:
第一行三个整数 $ n,b,p $ ，分别表示数列长度和输出相关的东西

第二行有 $ n $ 个整数，表示这个数列的初始数值


title: 珈百璃堕落的开始

background:
“恭喜你，珈百璃，你以学年首席的优秀成绩毕业。”

珈百璃，一位优秀的天使，今天她以学年首席的成绩毕业，从今往后，她将前往人间进行进一步修炼。

“我会努力给人类带来幸福的！”珈百璃憧憬着人间生活。

开学第一天，珈百璃就凭借着她极其可爱的外表，受到了班级成员的追捧，不仅长得可爱，成绩还很优秀，简直就是女神啊！

因为她的成绩优秀，所以她的作业也是很快就快要完成了，但是就在她快完成数学作业时，她的电脑传来了呼救的声音。

“救命啊！”

顺着这个呼救声，珈百璃望向了电脑。

“原来是游戏啊。”珈百璃看着屏幕里一位倒在地上的残血战士，注册了账号，选择了牧师职业，对这位战士进行了救治。在珈百璃开心的同时，越来越多的呼救声传来，珈百璃一个一个进行救治，但她的 level 才 1，mp 肯定不足，当她想要继续进行救治的时候，系统提示 mp 不足，并给出了氪金的提示：“屠龙宝刀，点击就送。”

“生活费天界学院倒是有给，但是……”珈百璃看着自己的存折，再看看屏幕，她纠结不已。

“救命啊！”“救……救命啊……”“救命啊！”珈百璃看着这些人一个个喊出救命，自己却无能为力，终于，她控制不住自己，点下了“氪金”按钮。

从此，珈百璃的堕落就开始了，她的作业，也停在了这道数学题上……

“薇奈特，帮我写一下作业嘛。”珈百璃央求着薇奈特。

“真是的，你好歹也是天使呢，也该自己做一点作业吧。”

“不要，我还要打游戏呢。”

“这怎么行，你是天使啊。”

“我已经决定做一位成天打游戏不学习的堕天使了。”

“真是服了你啊，那你好好打游戏吧，我帮你写。”

description: 这道题是这样的：给定一些 $\sin^2x$，$\cos^2x\ \left(x=\dfrac{\pi}{7}\right)$ 组成的式子，请你帮忙求出选择一些式子相加后得到的**最大整数答案**。

inputFormat:
第一行一个整数 $n$，表示 $n$ 个式子

接下来 $n$ 行每行一个字符串，由 $f(i)=\sin^2x,\cos^2x$ 和加号组成，$x=\dfrac{\pi}{7}$。

为了简化输入，我们以 `s` 代表 $\sin^2x$，以 `c` 代表 $\cos^2x$，并省略 `f(i)=`。

outputFormat: 一个数表示**最大整数答案**，计算全部为加法。

hint:
### 样例解释

三个式子都选，则加起来等于 $3$。

### 数据范围

设 `s` 和 `c` 的个数总和为 $m$。

$10\%$ 的数据 $n=1$。

另外 $20\%$ 的数据每行一个单项式。

另有 $20\%$ 的数据 $n\le20$。

$100\%$ 的数据 $n\times m\le5\times10^7,m\le10^6$。

### 提示

 - $\forall x, \sin^2x+\cos^2x=1$。


title: 萨塔尼亚的一生之敌

background:
“Trick or treat！”

万圣节到了，薇奈特、萨塔尼亚和菈菲尔敲开了珈百璃的门，但果然不出所料，珈百璃在打网游，真是颓废啊。

“干嘛，烦死了”珈百璃一脸嫌弃地看着她们

“珈百璃，好歹也出来玩玩嘛，天天待在家里打游戏，会烂掉的”薇奈特抢先说道

“哈？我每天都出去玩啊，去买泡面的时候顺路在家楼下逛了一圈啊”

“这只能算是去小卖部吧，根本不算是出去玩吧”

“对啊，而且万圣节到了，我们一起出去要糖果吃呀”

“哈？你几岁了？还玩这么无聊的游戏”

“不会啊，我觉得很有趣啊”三人异口同声

“真是的，好吧好吧，就陪你们玩玩”

于是珈百璃随着他们三个出去要糖果吃了

“那么，先去谁家呢？”

“我有提议！！”萨塔尼亚激动地抢着说

于是，她们一行人来到了某人家。

“咚咚咚”过了一会，门开了，走出来的，是一个光头吴克

“Trick or treat！”萨塔尼亚开心地叫倒。面前站的，就是她们的班主任。但是，除了萨塔尼亚在开心的要糖果，其他三个人早已经吓得瑟瑟发抖了

“呃。。班。。班主任。。。？老。。老师，这是有误会的。。。”薇奈特颤抖地说道

“哪有什么误会啊？班主任，Trick or treat！哦~再不给糖，就把你画成鬼~”萨塔尼亚依旧天不怕地不怕

“喂。。。”薇奈特微微后退了一步

但令人惊讶的是，老师居然进房间，拿了一袋礼品出来，其中包括萨塔尼亚最喜欢的限量版菠萝包

“啊！！！是限量版的！！！太好了！！！”当萨塔尼亚刚要伸手去拿菠萝包时，天使的走狗杀了出来，一把抢走了菠萝包。

“喂！！那是我的！！你给我回来”萨塔尼亚生气地望着天使的走狗，宣誓自己一定要抢回来

萨塔尼亚势力和天使的走狗势力占领着不同的区域，每个天使的走狗占领的区域都会有一个菠萝包，萨塔尼亚想抢回这些菠萝包，你能帮助她吗？

description:
详情是这样的，在萨塔尼亚强大的立场下，这个世界被分成了若干区域，有一些区域有连边。为了能够抢回菠萝包，萨亚尼亚将这些区域再分成了若干领域，使得每个领域由一些区域组成，萨塔尼亚占领了一些领域，并以这些领域为基础向走狗发起进攻。为了成功夺回所有菠萝包，萨塔尼亚决定让这些自己占领的领域满足以下性质

1、    为了能够及时支援友军，在自己占领的领域中，每两个存在于不同领域的两个点都要有连边

2、    为了能够灵活的进攻，自己的任意一个领域中的任意一个点和走狗占领的任意一个领域中的任意一个点都要有连边

当然走狗也不是吃干饭的，它为了羞辱萨塔尼亚，也选择了一些领域，这些领域满足的性质和萨塔尼亚选择的领域满足的性质一样，且走狗的领域和萨塔尼亚的领域互补

萨塔尼亚觉得，只要将领域分的越分散，胜利的几率就越大，于是想分尽可能多的领域，请问最多能分多少领域？每个领域有多少个区域组成？

\*特殊的，一个人可能占领不到任何一个领域，即占领的领域数量为0。如果你能告诉萨塔尼亚答案，萨塔尼亚就会占领最大的领域向走狗发起进攻，并最终失败。

inputFormat:
第一行两个整数n和m，表示n个区域m条边

接下来m行每行两个数a，b表示a和b之间有连边，保证没有自环和重边

outputFormat:
第一行输出一个整数s表示最多能分成领几个领域

第二行s个数从小到大输出每个领域由几个区域组成

hint:
样例解释：最多分成两个领域，区域1、3为一个领域，区域2为一个领域

请结合样例仔细读题！

对于40%的数据，n≤10^3，m≤5\*10^5

对于100%的数据，n≤10^5，m≤2\*10^6


title: 萨塔尼亚的期末考试

background:
“呐，珈百璃，我说，暑假我们去哪里玩呢？”薇奈特拍拍珈百璃的肩膀

“哈？暑假当然是在家里打游戏啦”珈百璃无精打采地回答道

“怎么能这样呢？你好歹也是天使啊，给我拿出天使的样子来啊”

“真麻烦”

“所以，暑假我们去海边玩吧？”

“赞成赞成！去海边玩的话，就可以好好调戏珈百璃了”菈菲尔不知道什么时候凑进来

“麻烦死了。”

这边一群人正讨论着暑假去哪玩，然而萨塔尼亚在旁边听得很纠结，因为没有人邀请她。。

“哼哼哼哼，吾乃神魔萨塔尼亚，怎么可能主动去加入呢，我必须等她们邀请我”萨塔尼亚心理打着小算盘

“呐，我说，萨塔尼亚貌似有点小不开心呀”

“已经不是貌似了吧，她这表情完全没有掩盖的意思啊。。”

“呐，我说，要不要邀请她去啊？”

拉菲尓说着，走向了萨塔尼亚。“萨塔尼亚桑，暑假我们要去海边玩哟~”

“哼哼哼，终于来邀请我了吗”萨塔尼亚心里有点小开心，小声嘀咕到

“萨塔尼亚桑就好好待在这里哟~”

“额。。。”萨塔尼亚受到了成吨的暴击，“喂，我说，哪有你这样的啊”

“恩？因为，萨塔尼亚桑，暑假如果要出去玩的话，就要通过期末考试哟，不然会被留下来补课的”

“补。。。补课。。。。”萨塔尼亚貌似意会到了什么，脸色大变，“补课。。。呐，拉菲尓。。你。。你能帮我。。补习吗？”

“恩？可以呀~但是期末考试如何就得看你自己了”

“谢谢，那帮我看看这些哪里错了吧？我完全不懂诶”

“我看看。。。” 拉菲尓丢下珈百璃和薇奈特独自给萨塔尼亚开始了补习。

终于，期末考来了，萨塔尼亚努力的这么久，就看这次考试了！经过长期的努力，期末考一切顺利，除了还没考的数学其他学科都及格啦！

终于到了最后一场考试——物理考试。很不错的是，萨塔尼亚已经答完了59分而且全对，但是她遇到了一道绝世难题，而且她很惊奇的发现，总分100分，这题41分，如果不写出来，就会挂科。“期末考如果有某人有挂科，那么那个人的暑假要参加补课以及补考！”班主任的话萦绕在她的耳旁，这可怎么办啊。。。

description:
这道题是这样的：

有一个由 $n$ 个点电荷形成的电场。假定每个点电荷放出的电场都是匀强电场而不是点电荷电场，第 $i$ 个点电荷的电场强度 $E_i=i$。

现放一个带负电的试探电荷到这个电场中，这个试探电荷只要触碰到任何一个点电荷就会和这个点电荷发生聚变放出巨大能量。

因为点电荷放出的电场强度不同，所以试探电荷被吸引到每个点电荷的概率也不同，点电荷给试探电荷的吸引力越大被吸到这个点电荷的概率就越大，且成正比。

我们假设最小的点电荷给试探电荷的吸引力为 $F$，那么对于其他点电荷给试探电荷和吸引力就是 $iF$，那么假设触碰最小的点电荷的概率为 $P$，则每个点的概率就是 $iP$，触碰到点电荷后发出的能量为 $\mathrm{Fib}(E_i)$。

求期望放出的能量。

好消息是，只要这道题拿到分，萨塔尼亚就能及格啦！

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

接下来 $T$ 行每行一个整数 $n$，表示有 $n$ 个点电荷。

outputFormat: 对于每次询问输出一行一个整数表示期望能量。为了避免精度问题，请输出答案对 $998{,}244{,}353$ 取模后的结果。

hint:
### 样例解释

$\dfrac{1}{3}\times \mathrm{Fib}(1)+\dfrac{2}{3}\times \mathrm{Fib}(2)=1$。

请结合样例仔细再仔细的读题！

### 数据范围

- 对于 $10\%$ 的数据 $T=1$，$n=2$；
- 对于 $30\%$ 的数据 $T≤10$，$1\le n\le 10^6$；
- 对于 $60\%$ 的数据 $T≤10^6$，$1\le n\le 10^6$；
- 对于 $100\%$ 的数据 $T≤10^6$，$1\le n\le 10^9$。

$\mathrm{Fib}(i)$ 为斐波那契数列。

$$\mathrm{Fib}(i)=\begin{cases}
1 & i\le 2 \cr
\mathrm{Fib}(i-1)+\mathrm{Fib}(i-2) & i > 2
\end{cases}$$


title: 琅泽难题

background:
```cpp
万事万物总是那么巧妙，数学海洋令我无限徜徉，在那一瞬，我又发现了美。
```
真程海洋的伟大数学家**琅泽**响应真程海洋殿主的号召，参与了这次出题。

根据他的思考与推算，出了一道有意思的题目，以下是他给你们的话：

description:
这个题目的灵感来自于这组数据：

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

这组数据采用**描述法**的规律，在第$ n+1 $层从左到右描述第$ n $层的数据，描述规律如下：从左到右描述第$ n $层的数据，从第一个数据开始，每当碰到连续的$ a_1 $个$ b_1 $时，将$ a_1\,b_1 $作为新的两个数据写在第$ n+1 $层的最后（这个最后是接在最后一个数据后面，如果第$ n+1 $层本来没有数据，则此时的最后即为开头），**紧接着**再描述接下来连续的$ a_2 $个$ b_2 $（$ b_1\neq b_2 $），往后亦如此，直到所有数据被描述完毕，则此时第$ n+1 $层也构造完毕，此处的$ n $为正整数。

现在，我有一个新的想法了，给定一个**初始数据** $ Q $（初始数据在第一层，且第一层仅有一个数据——初始数据$ Q $），按照**类似于**上述规律的规律（描述法）构造一组数据，称为“琅泽阵”。我定义的规律为：在奇数层遵循$ A $规律，在偶数层遵循$ B $规律。具体表现如下图：

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

上图是当初始数据为$ 1 $时呈现的部分琅泽阵，至于是什么规律，就需要你去探究。

### 但是！！！

这还不是最终目的，我要考的是，在第$ i $层中，有多少个$ x $（我们定义初始数据所在的层数为第一层）？

inputFormat:
输入仅一行，包含三个整数$ Q $和$ i $以及$ x $，每两个数据之间有一个空格。

$ Q $作为该琅泽阵的初始数据。

outputFormat:
输出仅一行，包含一个整数，表示在第$ i $层中，$ x $的数量。

由于输出数据较大，请将输出数据对$ 20171111 $取模（即原始输出数据除以$ 20171111 $后取其余数作为最终输出数据）。

hint:
### 样例一说明：

构建出来的琅泽阵（一小部分）为：

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

故第$ 2 $层中$ 2 $的数量为$ 1 $。

### 注意：

所有数据均为整数；

如果你毫无思路，你可以选择解决一些子问题；

以下是各个测试点中，输入数据的范围大小：

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


title: [NOIP2017 普及组] 棋盘

background: NOIP2017 普及组 T3

description:
有一个 $m \times m$ 的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。

任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 $1 $ 个金币。

另外， 你可以花费 $2$ 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。

现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？

inputFormat:
第一行包含两个正整数 $ m, n$，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。

接下来的 $ n $ 行，每行三个正整数 $ x, y, c$， 分别表示坐标为 $(x,y)$ 的格子有颜色 $ c$。

其中 $ c=1$ 代表黄色，$ c=0$ 代表红色。 相邻两个数之间用一个空格隔开。 棋盘左上角的坐标为 $(1, 1)$，右下角的坐标为 $( m, m)$。

棋盘上其余的格子都是无色。保证棋盘的左上角，也就是 $(1, 1)$ 一定是有颜色的。

outputFormat: 一个整数，表示花费的金币的最小值，如果无法到达，输出 `-1`。


title: [NOIP2017 普及组] 跳房子

background: NOIP2017 普及组 T4

description:
跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。

跳房子的游戏规则如下：

在地面上确定一个起点，然后在起点右侧画 $n$ 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：

玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。

现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 $d$。小 R 希望改进他的机器人，如果他花 $g$ 个金币改进他的机器人，那么他的机器人灵活性就能增加 $g$，但是需要注意的是，每 次弹跳的距离至少为 $1$。具体而言，当 $g<d$ 时，他的机器人每次可以选择向右弹跳的距离为 $d-g,d-g+1,d-g+2,\ldots,d+g-1,d+g$；否则当 $g \geq d$ 时，他的机器人每次可以选择向右弹跳的距离为 $1,2,3,\ldots,d+g-1,d+g$。

现在小 R 希望获得至少 $k$ 分，请问他至少要花多少金币来改造他的机器人。

inputFormat:
第一行三个正整数 $n,d,k$，分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数 之间用一个空格隔开。

接下来 $n$ 行，每行两个整数 $x_i,s_i$，分别表示起点到第 $i$ 个格子的距离以及第 $i$ 个格子的分数。两个数之间用一个空格隔开。保证 $x_i$ 按递增顺序输入。

outputFormat: 共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 $k$ 分，输出 $-1$。

hint:
**样例 1 说明**

花费 $2$ 个金币改进后，小 R 的机器人依次选择的向右弹跳的距离分别为 $ 2, 3, 5, 3, 4,3$，先后到达的位置分别为 $2, 5, 10, 13, 17, 20$，对应 $ 1, 2, 3, 5, 6, 7$ 这 $6$ 个格子。这些格子中的数字之和 $ 15$ 即为小 R 获得的分数。

**样例 2 说明**

由于样例中 $7$ 个格子组合的最大可能数字之和只有 $18$，所以无论如何都无法获得 $20$ 分。

**数据规模与约定**

本题共 10 组测试数据，每组数据等分。

对于全部的数据满足 $1 \le n \le 5\times10^5$，$1 \le d \le2\times10^3$，$1 \le x_i, k \le 10^9$，$|s_i| < 10^5$。

对于第 $1, 2$ 组测试数据，保证 $n\le 10$。

对于第 $3, 4, 5$ 组测试数据，保证 $n \le 500$。

对于第 $6, 7, 8$ 组测试数据，保证 $d = 1$。


title: [TJOI2013] 黄金矿工

description:
小 A 最近迷上了在上课时玩《黄金矿工》这款游戏。为了避免被老师发现，他必须小心翼翼，因此他总是输。

在输掉自己所有的金币后，他向你求助。每个黄金可以看做一个点（没有体积）。现在给出你 $N$ 个黄金的坐标，挖到它们所需要的时间以及它们的价值。有些黄金在同一条直线上，这时候你必须按顺序挖。你可以瞬间把钩子转到任意角度。

小 A 一开始在坐标 $(0,0)$，请你帮助小 A 算出在时间 $T$ 内他最多可以得到多少价值的金子。

inputFormat:
第一行两个整数 $N$ 和 $T$，表示黄金的个数和总时间。

接下来 $N$ 行，每行四个整数 $x$、$y$、$t$、$v$，分别表示黄金的坐标，挖到这个黄金的时间，以及这个黄金的价值。

outputFormat: 一个整数,表示你可以在 $T$ 时间内得到的最大价值。