title: [BJOI2019] 勘破神机

description:
地灾军团的军师黑袍从潜伏在精灵高层的密探手中得知了神杖的情报，他对奥术宝石中蕴含的远古神秘力量十分感兴趣。他设计夺取了数块奥术宝石，并命令作为地灾军团首席科学家的你带领手下的研究人员全力破解。经过了一个月的艰苦尝试，你的研究团队终于破译了 “`2`” 型奥术宝石和 “`3`” 型奥术宝石的内部能量结构。

这两类结构有着一定的相似性，它们的内部具有 $k$ 个反应核心，“`2`” 型奥术宝石的每个核心都可以看成是一个 $2 \times n$ 的网格，而 “`3`” 型奥术宝石的每个核心都可以看成是一个 $3 \times n$ 的网格。（注意奥术宝石的 $k$ 和 $n$ 可能不同）当神力反应进行时，每个核心自动填充满神力颗粒。

形式化地描述，每个神力颗粒可以看成是一个 $1 \times 2$ 横置或竖置的方格，核心填满的定义为每个网格都恰好被一某个方格覆盖。若在两种填满反应核心的方案中存在一个方格放置的位置或方式不同，就认为方案不同。

如填满 $2×4$ 的网格有 $5$ 种不同的方案，填满 $3×2$ 的网格有 $3$ 种不同的方案。

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

如果奥术宝石的 $k$ 个核心的填充方式互不相同，它们就会组合出强大的咒术。黑袍想知道对于某个宝石一共有多少种不同的咒术（对于两种咒术组合，如果第一种咒术中每个核心 $a$ 的填充方式都可以找到第二种咒术的某个核心 $b$ ，使得 $a$ 和 $b$ 的填充方式完全相同，则认为这两种咒术组合相同）。

对于宽度为 $n$ 、反应核心个数为 $k$ 的 “`2`” 型奥术宝石，设不同的咒术为 $F(n,k)$  ；对于宽度为 $n$ 、反应核心个数为 $k$ 的 “`3`” 型奥术宝石，设不同的咒术为 $G(n,k)$  。例如 $F(4,1) = 5$ ，$F(4,2) = 10$ ，$G(2,2) = 3$ 。

地灾军团的科技水平还不能精准测量反应核心的长度 $n$ ，只能确定出核心长度的大致范围  $[l,r]$ 。你需要计算出反应核心长度在此区间内的平均咒术数，即

$$ans2 = \frac{1}{r-l+1}\sum_{n=l}^{r} F(n,k)$$
$$ans3 = \frac{1}{r-l+1}\sum_{n=l}^{r} G(n,k)$$

设最终答案的形式为 $\frac{A}{B}$，输出 $ A \times B^{-1} \bmod 998244353$ 的结果，其中 $B^{-1}$ 是 $B$ 在 $998244353$ 下的乘法逆元。

inputFormat:
第一行为两个正整数 $T$ 、$m$ ，表示数据组数和奥术宝石的类型（只可能为 $2$ 或 $3$ ）。

接下来 $T$ 行每行三个正整数 $l,r,k$ ，表示核心长度的范围与核心数量。

outputFormat: 对于每组数据，若 $m=2$ 则输出 $ans2$ ，$m=3$ 则输出 $ans3$ 。

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

对于所有数据，保证不存在 $r-l+1$ 是 $998244353$ 倍数的情况。

由于考场的电脑很慢，出题人更改数据后的所有 $T=1$。

注：本题数据范围有误，实际满足 $1\leq l\leq r\leq 6\times 10 ^ {18}$。


title: [BJOI2019] 送别

type: P

description:
法珞是个怕黑的女孩子。

傍晚了，法珞所参加的学术会议早已散会。黎瑟也下了课过来接法珞回火车站。

但是教学楼里突然断电了，法珞陷入了一片漆黑之中。

好在黎瑟已经到了教学楼的同一层。

然而由于教学楼的结构过于复杂，她们已经记不起教学楼的具体结构了。
黎瑟学校的教学楼每层的结构都非常工整。

形式化地说，教学楼的一层的平面结构可以画在二维平面上以 $(0,0)$ 为左上角顶点，$(n,m)$ 为右下角顶点的子矩形（记为 $(0,0) - (n,m)$  的矩形）里，这个子矩形的四条边是教学楼的楼体(或者说是四段已知一定存在的墙)。

**请注意，本题中的坐标系和普通的平面直角坐标系不同，$(0,0)$ 是左上角的顶点而 $(n,m)$ 是右下角的顶点。 $(i,j)$ 表示的是第 $i+1$ 行第 $j+1$ 列的顶点而不是横坐标为 $i$ 纵坐标为 $j$ 的顶点。**

每一段墙（无法通过的部分）是一条端点为 $(i,j)$ 和 $(i',j')$ 的线段，记作 $(i,j) - (i',j')$ 的墙，其中 $|i-i'| + |j-j'| =1$ 且 $i,i'$ 是 $[0,n]$ 中的整数， $j,j'$ 是 $[0,m]$ 中的整数（每当我们之后使用 $(i,j) - (i',j')$ 的记法，我们都保证满足上述所有条件）。

法珞知道，对于这种结构，有一种办法可能让她找到黎瑟：法珞用左手扶住墙，手臂和墙面垂直，保持这个状态向前方走，在转弯处也保持左手一直扶墙的状态。按照这个方法她就可以环绕一周，可能与黎瑟相遇。

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

上图是样例输入中第一次询问的法珞的行走方案，在行走过程中法珞的左手必须贴住墙。

法珞一开始会给你需要维护的初始的(这层楼的)结构，之后会给你 $q$ 个请求。

+ 操作 1 ： 读入格式形如 $1 \ x_0 \ y_0 \ x_1 \ x_2$：法珞请求在当前结构里添加一段 $(x_0,y_0) - (x_1,y_1)$ 的墙，保证此前这段墙不存在且这段墙不在 $(0,0) - (n,m)$ 的子矩形的四条边上。

+ 操作2： 读入格式形如 $2 \ x_0 \ y_0 \ x_1 \ x_2$：法珞请求在当前结构里删除一段 $(x_0,y_0) - (x_1,y_1)$ 的墙，保证此前这段墙存在且这段墙不在 $(0,0) - (n,m)$ 的子矩形的四条边上。

+ 操作3： 读入格式形如 $3\ x_0 \ y_0 \ x_1\ y_1\ d_0 \ x_2 \ y_2 \ x_3 \ y_3 \ d_1$ ：法珞当前在 $(x_0,y_0) - (x_1,y_1)$ 的墙的中点位置 $(\frac{x0+x1}{2},\frac{y_0 + y_1}{2})$ ， $d_0$ 是一个 $[0,1]$ 中的整数，用来描述法珞在墙的哪一侧， $d_0  = 0$ 代表法珞在墙的左方/上方， $d_0 = 1$ 代表右方/下方。黎瑟当前在 $(x_2,y_2) - (x_3,y_3)$ 的墙的中点位置  $(\frac{x2+x3}{2},\frac{y_2+y_3}{2})$ 。 $d_1$ 的格式和 $d_0$ 相同。保证 $(x_0,y_0) - (x_1,y_1)$ 和 $(x_2,y_2) - (x_3,y_3)$ 这两段墙存在，且法珞和黎瑟的位置都落在 $(0,0) - (n,m)$ 的子矩形的内部。求法珞按照题目所述的方法找到黎瑟要走过多少长度（ $(i,j) - (i',j')$  这段墙的长度为 $1$，半段墙（由于起点和终点都在墙的中点处）的长度是  $\frac{1}{2}$ ）。

inputFormat:
输入共 $2n+q$ 行。

第一行三个整数 $n$ 、$m$ 、$q$ ，意义如题目中所示。

接下来的 $n$ 行，每行 $m-1$ 个 $[0,1]$ 中的整数，第 $i$ 行第 $j$ 列的整数为 $1$ 表示 $(i,j) - (i-1,j)$ 这一段有墙，为 $0$ 则表示 $(i,j) - (i - 1,j)$ 这一段没有墙。

接下来的 $n-1$ 行，每行 $m$ 个 $[0,1]$ 中的整数，第 $i$ 行第 $j$ 列的整数为 $1$ 表示 $(i,j) - (i,j-1)$ 这一段有墙，为 $0$ 则表示 $(i,j) - (i,j-1)$ 这一段没有墙。

接下来的 $q$ 行，每行一个操作，格式如题目中所示。

outputFormat: 对于每个询问，输出法珞按照题目所述的方法找到黎瑟要走过多少长度，**如果法珞按照题目所述的方法无法找到黎瑟则输出 $-1$ 。**

hint:
对于 10% 的数据， $5 \le n,m \le 50$ ， $1 \le q \le  2000$ 。

对于另外 30% 的数据，没有 1 操作。

对于另外 30% 的数据，保证在任意时刻若法珞和黎瑟站在任意输入格式中合法的位置，法珞都可以和黎瑟相遇。

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


title: [BJOI2019] 排兵布阵

description:
小 C 正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵，可以向第 $i$ 座城堡派遣 $a_i$ 名士兵去争夺这个城堡，使得总士兵数不超过 $m$。

如果一名玩家向第 $i$ 座城堡派遣的士兵数**严格**大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 $i$ 分。

现在小 C 即将和其他 $s$ 名玩家两两对战，这 $s$ 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 $s$ 名玩家即将使用的策略，他想知道他应该使用什么策略来最大化自己的总分。

由于答案可能不唯一，你只需要输出小 C 总分的最大值。

inputFormat:
输入第一行包含三个正整数 $s,n,m$，分别表示除了小 C 以外的玩家人数、城堡数和每名玩家拥有的士兵数。
接下来 $s$ 行，每行 $n$ 个非负整数，表示一名玩家的策略，其中第 $i$ 个数 $a_i$ 表示这名玩家向第 $i$ 座城堡派遣的士兵数。

outputFormat: 输出一行一个非负整数，表示小 C 获得的最大得分。

hint:
**样例1解释：**
小 C 的最佳策略为向第 $1$ 座城堡和第 $2$ 座城堡各派遣 $5$ 名士兵。

**样例2解释：**
小 C 的最佳策略之一为向第 $1$ 座城堡派遣 $2$ 名士兵，向第 $2$ 座城堡派遣 $5$ 名士兵，向第 $3$ 座城堡派遣 $1$ 名士兵。

**数据范围：**
对于 $10\%$ 的数据： $s=1,n \le 3,m \le 10$
对于 $20\%$ 的数据： $s=1,n \le 10,m \le 100$
对于 $40\%$ 的数据： $n\le 10,m\le 100$
对于另外 $20\%$ 的数据： $s=1$
对于 $100\%$ 的数据：
$1\le s \le 100$
$1\le n \le 100$
$1\le m \le 20000$
对于每名玩家 $a_i \ge 0$，$\sum\limits_{i=1}^n a_i \le m$


title: [BJOI2019] 光线

description:
当一束光打到一层玻璃上时，有一定比例的光会穿过这层玻璃，一定比例的光会被反射回去，剩下的光被玻璃吸收。

设对于任意 $x$，有 $x \times a_i\%$ 单位的光会穿过它，有 $x \times b_i\%$ 的会被反射回去。
现在 $n$ 层玻璃叠在一起，有 $1$ 单位的光打到第 $1$ 层玻璃上，那么有多少单位的光能穿过**所有** $n$ 层玻璃呢？

inputFormat:
第一行一个正整数 $n$，表示玻璃层数。
接下来 $n$ 行，每行两个非负整数 $a_i,b_i$，表示第 $i$ 层玻璃的透光率和反射率。

outputFormat:
输出一行一个整数，表示穿透所有玻璃的光对 $10^9 + 7$ 取模的结果。
可以证明，答案一定为有理数。设答案为 $a/b$ ( $a$ 和 $b$ 是互质的正整数)，你输出的答案为 $x$，你需要保证 $a\equiv bx \space (\text{mod }10^9 + 7)$。

hint:
**样例1解释：**
![](https://cdn.luogu.com.cn/upload/pic/57125.png)
如图，光线从左上角打进来，有 $0.5$ 单位的光穿过第 $1$ 层玻璃，有 $0.2$ 单位的光被反射回去。这 $0.5$ 单位的光有 $0.4$ 单位穿过第 $2$ 层玻璃，有 $0.025$ 单位的光被反射回去。这 $0.025$ 单位的光有 $0.0125$ 单位穿过第 $1$ 层玻璃，有 $0.005$ 单位的光被反射回去。这 $0.005$ 单位的光有 $0.004$ 单位穿过第 $2$ 层玻璃……于是，穿过两层玻璃的光一共有$0.40404... = 40/99$ 单位。在模 $10^9+7$ 意义下等于 $858585865$。

**数据范围：**
对于 $5\%$ 的数据，$n=1$；
对于 $20\%$ 的数据，$n\le 2$；
对于 $30\%$ 的数据，$n\le 3$；
对于 $50\%$ 的数据，$n\le 100$；
对于 $70\%$ 的数据，$n\le 3000$；
对于 $100\%$ 的数据，$n\le 5\times 10^5$，$1\le a_i \le 100$，$0\le b_i \le 99$，$1\le a_i+b_i \le 100$。

每组 $a_i$ 和 $b_i$ 在满足上述限制的整数中随机生成。


title: [BJOI2019] 删数

description:
对于任意一个数列，如果能在有限次进行下列删数操作后将其删为空数列，则称这个数列可以删空。一次删数操作定义如下：
>记当前数列长度为 $k$ ，则删掉数列中所有等于 $k$ 的数。

现有一个长度为 $n$ 的数列 $a$，有 $m$ 次修改操作，第 $i$ 次修改后你要回答：
经过 $i$ 次修改后的数列 $a$，至少还需要修改几个数才可删空？

每次修改操作为单点修改或数列整体加一或数列整体减一。

inputFormat:
第一行两个正整数 $n,m$，分别表示数列长度、修改次数。
第二行有 $n$ 个正整数，表示数列 $a$，即输入的第 $i$ 个数表示数列 $a$ 的第 $i$ 个数 $a_i$。

接下来 $m$ 行，每行两个整数 $p,x$，表示一次修改操作。
当 $1\le p \le n$ 时，该操作为单点修改，将数列中第 $p$ 个数 $a_p$ 修改为 $x$
当 $p=0$ 时，该操作为数列整体加 $x$。

outputFormat: 输出 $m$ 行，每行一个整数，第 $i$ 行表示前 $i$ 次修改后的答案。

hint:
**样例解释(局部)：**
第一次修改后，数列为$1$ $2$ $3$，无需修改即可删空。
第四次修改后，数列为$4$ $5$ $6$，需要将三个数都改掉才可能删空。
第六次修改后，数列为$4$ $2$ $2$，将第一个数改成$3$即可删空。
第九次修改后，数列为$1$ $-1$ $-1$，可以将第二个数改成$2$、第三个数改成$3$来删空。

**数据范围：**
对于 $100\%$ 的数据：
$1\le n,m \le 150000$
$1\le a_i \le n$
$0\le p\le n$
$p>0$时，$1\le x \le n$
$p=0$时，$x=-1$ 或 $1$
![](https://cdn.luogu.com.cn/upload/pic/57129.png)


title: 【XR-1】逛森林

background:
NaCly_Fish 和 PinkRabbit 是好朋友。

有一天她去森林里游玩，回去跟 PinkRabbit 说：“我发现好多棵会动的树耶！”

PinkRabbit 动了动一只兔耳朵：“这有什么好稀奇的，我用一只兔耳朵就能维护每棵树的形态。”

NaCly_Fish 不服：“不止这样，我还看到有一些传送门，能从一条树枝跳到另一条树枝上呢！”

PinkRabbit 动了动另一只兔耳朵：“这有什么好稀奇的，我用两只兔耳朵就能统计每个传送门的信息。”

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

于是 NaCly_Fish 很郁闷，她向你求助，请帮帮她吧。

什么？你不愿意帮？

那她就不给你这题的分了。

description:
给你 $n$ 个节点的森林，初始没有边。

有 $m$ 个操作，分为两种：

$1\ u_1\ v_1\ u_2\ v_2\ w$：表示构建一个单向传送门，从 $u_1 \rightarrow v_1$ 简单路径上的所有节点，可以花费 $w$ 的代价，到达 $u_2 \rightarrow v_2$ 简单路径上的所有节点。若 $u_1$ 到 $v_1$ 或 $u_2$ 到 $v_2$ 不连通(由 $2$ 操作产生的边不连通)，则忽略此次操作。

$2\ u\ v\ w$：表示将 $u$ 和 $v$ 节点间连一条花费为 $w$ 的无向边，若 $u$ 和 $v$ 之间已连通(由 $2$ 操作产生的边连通)则忽略此次操作。

经过这 $m$ 次操作后，请你求出从 $s$ 节点出发，到每个节点的最小花费。

inputFormat:
第一行三个正整数 $n, m, s$，分别表示树的节点数、操作数、和起始节点。

接下来 $m$ 行，每行若干个正整数，表示一次操作。

outputFormat: 输出一行 $n$ 个整数，第 $i$ 个整数表示从 $s$ 节点出发，到 $i$ 节点的最小花费。特别地，若不能到达$i$节点，则输出 `-1`。

hint:
【样例说明】

这是样例中给出的树（严格来讲，这棵树也是一条链）：

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

有三个传送门，其中两个是这样的：

- 从 $1$ 号点可以花费 $2$ 的代价到达 $4 \rightarrow 9$ 简单路径上的所有节点（即 $4, 9$ 号点）。
- 从 $8 \rightarrow 5$ 简单路径上的所有节点（即 $8, 7, 6, 5$ 号点）可以花费 $1$ 的代价到达 $1 \rightarrow 6$ 简单路径上的所有节点（即 $1, 3, 5, 6$ 号点）。

容易看出从 $5$ 号节点出发，到达其它节点的最小花费分别为：$1, 1, 1, 1, 0, 1, 7, 9, 1$。

【数据规模与约定】

对于第 $1, 2$ 个测试点，$1 \le n \le 100$，$1 \le m \le 300$。

对于第 $3, 4$ 个测试点，$1 \le n \le 1000$，$1 \le m \le 3000$。

对于 $100\%$ 的数据，$1\le n \le 50000$，$1\le m \le 10^6$，$1\le u,v \le n$，$1\le w \le 100$。

对于第 $1$ ~ $10$ 个测试点，每个 $5$ 分。

对于第 $11, 12$ 个测试点，每个 $25$ 分。


title: [Cnoi2019] 数字游戏

description:
给定一个 $1\sim n$ 的排列 $\pi$，以及 $q$ 个询问，每个询问包含一个整数四元组 $( l, r, x, y )$，表示查询有多少个整数二元组 $( u, v )$ 满足：
 - $l\le u\le v\le r$；
 - 且对于任意 $\forall u\le i\le v$，有 $x\le\pi_i\le y$。

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

第二行 $n$ 个整数，表示 $\pi$。

以下 $q$ 行，每行一个四元组询问。

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

hint:
子任务 1（$34$ points）：$1\le n, q \le 3\times10^4$。

子任务 2（$66$ points）：$1\le n, q \le 2\times10^5$。


title: 树上后缀排序

description:
给定一棵以 $1$ 为根包含 $n$ 个节点的树，保证对于 $2 \sim n$ 的每个节点，其父亲的编号均小于自己的编号。

每个节点上有一个的字符，一个节点所代表的字符串定义为从当前节点一直到根节点的简单路径上经过的所有字符连起来形成的字符串。

请你给这些字符串按照字典序排序。

特别地，如果两个节点所代表的字符串完全相同，它们的大小由它们父亲排名的大小决定，即谁的父亲排名大谁就更大；如果仍相同，则由它们编号的大小决定，即谁的编号大谁就更大。

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

第二行包含 $n-1$ 个数 $f_{2 \dots n}$，其中 $f_i$ 表示 $i$ 的父亲。

第三行为一个包含 $n$ 个**小写字母**的字符串 $s$，其中 $s_i$ 表示编号为 $i$ 的节点上的字符。

outputFormat: 输出一行 $n$ 个正整数，第 $i$ 个正整数表示代表**排名第 $i$ 的字符串**的节点编号。


title: 草莓 Strawberry

background:
小 M 很喜欢草莓。

草莓可以抽象为一棵树 $T$。我也不知道为什么可以，但草莓甚至可以飞，抽象成一棵树想必问题也不大吧。

description:
给定一棵树 $T$，点和边均有权值。

一条简单路径是一条不重复经过任意一个点的路径。可以证明，两个节点 $u$ 和 $v$ 之间的简单路径是唯一的，我们将其记为 $P(u,v)$。一条路径的长度是它所包含的所有边的权值和。

你有两个集合 $S$ 和 $G$。

在一开始，你必须选择一个点作为 **当前点** 并且将其加入集合 $S$。接下来可以进行任意次操作，一次操作的形式如下：

假设你的 **当前点** 为 $u$，你可以选择一个节点 $v$，使得 $v \neq u$，然后将你的 **当前点** 更新为 $v$，并且将点 $v$ 加入集合 $S$，将路径 $P(u,v)$ 加入集合 $G$。

在你进行完所有操作之后，你得到的收益为 $S$ 中所有点的点权和 $\times$ $G$ 中所有路径的长度的最小值。如果 $G$ 为空，我们认为第二项的值为 $0$。

注意 $S$ 和 $G$ 都是 **不可重集**，这意味着，即使你多次将某个点加入集合 $S$，最终在计算点权时，也只会被计算一次。

求得到的收益的最大值。

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

接下来一行 $n$ 个整数 $a_1,a_2 \ldots a_n$，表示这 $n$ 个节点的点权。

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

outputFormat: 输出一个整数，所求最大收益。


title: 【XR-1】分块

background: xht37 喜欢分块，以至于对一道**不需要分块**的题也要分块做。

description:
有一个长度为 $n$ 的序列，xht37 现在想分块维护它。

PinkRabbit 要求他只准将序列分成 $PR$ 种长度的块。

NaCly_Fish 要求他只准将序列分成 $NF$ 种长度的块。

同一个人可能会要求 xht37 多次相同的块长。

xht37 想同时满足 PinkRabbit 和 NaCly_Fish 要求，只好使用两个人都允许的长度分块。

xht37 想知道，有多少种不同的分块方案，答案对 $10 ^ 9 + 7$ 取模。

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

第二行一个正整数 $PR$，表示 PinkRabbit 要求的分块长度的种类数。

第三行 $PR$ 个正整数，表示 PinkRabbit 要求的 $PR$ 种分块长度。

第四行一个正整数 $NF$，表示 NaCly_Fish 要求的分块长度的种类数。

第五行 $NF$ 个正整数，表示 NaCly_Fish 要求的 $NF$ 种分块长度。

outputFormat: 输出一行一个整数，表示不同分块方案的种类数对 $10 ^ 9 + 7$ 取模的值。

hint:
【样例 $1$ 说明】

PinkRabbit 和 NaCly_Fish 都允许的块长为 $\{1,2\}$。

长度为 $4$ 的序列分块，每块长度为 $\{1,2\}$ 的方案有：

- $1\ 1\ 1\ 1$
- $1\ 1\ 2$
- $1\ 2\ 1$
- $2\ 1\ 1$
- $2\ 2$

共 $5$ 种。

【数据规模与约定】

设最大块长为 $x$。

对于 $60 \%$ 的数据，$1 \le n \le 10 ^ 6$，$1 \le PR,NF,x \le 10$，保证同一个人不会要求多次相同的块长。

对于 $100 \%$ 的数据，$1 \le n \le 10 ^ {18}$，$1 \le PR,NF,x \le 100$。


title: 【XR-1】快乐肥宅

background: 小粉兔的机房里面有 $n$ 个快乐肥宅，但小粉兔自己并不是，他看着这些快乐肥宅，非常羡慕，于是他想研究一下这些快乐肥宅的体重。

description:
每个快乐肥宅第 $0$ 天的体重都等于 $1$。第 $i$ 个快乐肥宅的体重记作 $w_i$，则一开始 $w_i = 1$。

第 $i$ 个快乐肥宅有一个专属的快乐指数 $k_i$，这表示他每天刚起床后，体重会是上一天的体重的 $k_i$ 倍。

肥宅们是有觉悟的，第 $i$ 个肥宅有一个专属的觉醒体重 $g_i$，这表示一旦他的体重**大于** $g_i$，他就会去健身房健身，每次减掉自己 $g_i$ 的体重，直到体重小于等于 $g_i$。

健身后，肥宅们会在机房见面，他们发现有时各自的体重会变得很有趣。

有一天，肥宅们发现各自的体重形成了等差数列！

另一天，肥宅们发现各自的体重形成了等比数列！

肥宅们心想，如果 $n$ 个快乐肥宅的体重 $\{w_1, w_2, \ldots, w_n\}$ 恰好形成序列 $\{r_1, r_2, \ldots, r_n\}$，至少需要经过多少天呢？

不过如果肥宅们等了很久都没有等到这一天，他们会认为这是不可能的。

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

接下来 $n$ 行，每行三个正整数 $k_i, g_i, r_i$。分别表示第 $i$ 个肥宅的快乐指数、觉醒体重和序列中的体重。

outputFormat:
如果在第 $10^9$ 天结束前已经形成给定的序列，则输出一个数，表示至少需要经过的天数。

如果在第 $10^9$ 天结束前没有形成给定的序列，则输出 `Impossible`。

hint:
【样例 $1$ 说明】

下表是两个肥宅在第 $0$ 天至第 $7$ 天时的体重变化表：

| 天数 | 肥宅 $1$ 的体重 | 肥宅 $2$ 的体重 | 解释 |
| :--: | :--: | :--: | :--: |
| $0$ | $1$ | $1$ | 第 $0$ 天每个肥宅的体重都是 $1$ |
| $1$ | $4$ | $2$ | 肥宅 $1$ 的体重是上一天的 $4$ 倍，肥宅 $2$ 的体重是上一天的 $2$ 倍 |
| $2$ | $2$ | $4$ | 肥宅 $1$ 的体重是上一天的 $4$ 倍，为 $16$，他发现自己的体重超过了 $7$，于是去了两次健身房，把体重减少了 $2\times 7=14$ |
| $3$ | $1$ | $3$ | 这一天肥宅 $1$ 和肥宅 $2$ 都去了一次健身房 |
| $4$ | $4$ | $1$ | 肥宅 $2$ 去了一次健身房 |
| $5$ | $2$ | $2$ | 肥宅 $1$ 去了两次健身房 |
| $6$ | $1$ | $4$ | 肥宅 $1$ 去了一次健身房 |
| $7$ | $4$ | $3$ | 肥宅 $2$ 去了一次健身房 |

可以看出在第 $7$ 天时肥宅的体重形成了序列 $\{4, 3\}$。

【数据规模与约定】

Subtask 1（20 points）：$n \le 50$，$g_i \le 50$。
Subtask 2（20 points）：$g_i$ 为质数。
Subtask 3（20 points）：$g_i \le 10^3$。
Subtask 4（20 points）：$r_i \in \{1, g_i\}$。
Subtask 5（20 points）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^3$，$1 \le k_i, r_i \le g_i \le 10^7$。


title: 【XR-1】柯南家族

background:
xht37 最近沉迷于名侦探柯南。

在某集中，小兰又在怀疑柯南的真实身份了。为了让小兰不再怀疑，柯南编造出自己的家族背景来应对小兰的询问。

description:
这个家族一开始只有一个人，后来不断有人有了孩子，直到现在，这个家族有 $n$ 个人，第 $n$ 个人正是柯南。易知这个家族构成了一个 $n$ 个点的树形结构。

柯南为了使自己编造的家庭背景更加真实，他给家族中的每个人赋予了一个**智商值**。但是，一个人的**聪明程度**不仅仅只与他的**智商值**有关，还可能与他**祖先的聪明程度**及他**出生的时代**有关。

具体来说，在这个家族中，A 比 B 聪明**当且仅当** A 和 B 满足下面三种情况中的某一种：

1. A 的智商值比 B 的智商值高；
2. A 的智商值与 B 的智商值一样且 A 和 B 有不同的父亲，A 的父亲比 B 的父亲聪明；
3. A 的智商值与 B 的智商值一样且 A 和 B 的父亲是同一个人或某一个人没有父亲，A 比 B 后出生。

有一个很显然的结论是，这个家族中不会有两个人一样聪明。

柯南需要回答小兰的 $q$ 个询问。为了方便说明，假设第 $i$ 个出生的人编号为 $i$。

每个询问是下面三种情况中的某一种：

1. `1 x`：询问编号为 $x$ 的人在整个家族中聪明程度排第几。
2. `2 x k`：询问编号为 $x$ 的人及其祖先中第 $k$ 聪明的人的编号。
3. `3 x k`：询问编号为 $x$ 的人及其后代中第 $k$ 聪明的人的编号。

柯南还有许多案子要办，他不想在回答小兰的问题上浪费时间，他希望你能编程帮他回答小兰的所有询问。

inputFormat:
第 $1$ 行包含两个数 $n, q$，分别表示人数和询问次数。

第 $2$ 行包含 $n-1$ 个数 $f_{2 \dots n}$，其中 $f_i$ 表示 $i$ 的父亲。

第 $3$ 行包含 $n$ 个数 $a_{1 \dots n}$，其中 $a_i$ 表示 $i$ 的智商值。

接下来 $q$ 行每行两个或三个数表示一个合法询问，其中第一个数表示询问种类，后面一个或两个数为询问参数。

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

hint:
【样例说明】

形成的树如下：

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

首先比较编号为 $2,3$ 的两个人，由于** $3$ 号的智商值与 $2$ 号的智商值一样且他们的父亲是同一个人，$3$ 号比 $2$ 号后出生**满足第 $3$ 种情况，因此 $3$ 号比 $2$ 号聪明。

再比较编号为 $4,5$ 的两个人，由于** $4$ 号的智商值与 $5$ 号的智商值一样且他们有不同的父亲，$4$ 号的父亲 $3$ 号比 $5$ 号的父亲 $2$ 号聪明**满足第 $2$ 种情况，因此 $4$ 号比 $5$ 号聪明。

再比较编号为 $1,5$ 的两个人，由于** $5$ 号的智商值与 $1$ 号的智商值一样且 $1$ 号没有父亲，$5$ 号比 $1$ 号后出生**满足第 $3$ 种情况，因此 $5$ 号比 $1$ 号聪明。

再根据第 $1$ 种情况比较编号为 $2,4$ 的两个人，可对 $5$ 人的聪明程度排序：$3 > 2 > 4 > 5 > 1$。

【数据规模与约定】

一共 $10$ 个测试点。

对于前 $20\%$ 的数据，$1 \le n, q \le 10 ^ 3$，每个测试点 $7$ 分，时限 1s。

对于另 $20\%$ 的数据，保证一个人最多只有一个儿子，每个测试点 $9$ 分，时限 4s。

对于另 $20\%$ 的数据，$1 \le n, q \le 10 ^ 5$，每个测试点 $9$ 分，时限 1.5s。

对于另 $20\%$ 的数据，保证只有第一种询问，每个测试点 $12$ 分，时限 1.5s。

对于 $100\%$ 的数据，$1 \le n, q \le 5 \times 10 ^ 5$，$1 \le a_i \le 10 ^ 9$，每个测试点 $13$ 分，时限 2.5s。


title: 【XR-1】俄罗斯方块

background:
小粉兔最近沉迷一个名叫“俄罗斯方块”的游戏。

然而本题除了都有格子和颜色之外和俄罗斯方块没什么关系。

description:
有一个 $n \times m$ 的方格图，小粉兔打算在其中画线。

他可以画线若干次，也可以不画。每次画线必须从一个没有被画过的方格中心开始。

只能往上下左右四个方向画线，对应方向上的方格记作**目标方格**。

目标方格能被画，当且仅当下面三种情况：

1. 如果目标方格**没有被画过**，则可以经过两个方格公共边的中点，直接画到目标方格中心，此时**可以选择**结束本次画线；
2. 如果目标方格**已经被画过**，且这条画过的线是**贯穿整个方格的线**，则可以再画一条与这条线**垂直**的**贯穿整个方格的线**。对**贯穿整个方格的线**的定义为：这条线在方格中**没有改变方向**，**上下贯穿**或**左右贯穿**；
3. 如果目标方格是本次画线的**起笔方格**，则可以经过两个方格公共边的中点，直接画到目标方格中心，此时**必须**结束本次画线。

当然，不能画到整个方格图外面去。

虽然小粉兔制定了如此严苛的规则，但是他仍然有很多种颜色的笔，每次画线他可以选择 $c$ 种颜色中的任意一种用来画线。

不幸的是，方格图中有一些位置坏掉了，不能被经过，即在任意一次画线中不能画到坏掉的位置上。

小粉兔想知道，在这些限制下，最终能画出多少种本质不同的图呢？

小粉兔不想要求太多，当 $\mathrm{op}=0$ 时，两张图本质相同当且仅当不考虑坏掉的方格，它们看起来相同（每个位置上的线条方向和颜色均相同）。

而当 $\mathrm{op}=1$ 时，两张图本质相同当且仅当不考虑坏掉的方格，它们看起来相同，或旋转 $180 ^ {\circ}$ 后看起来相同。

因为答案可能很多，所以小粉兔只想知道答案对 $998244353$ 取模的结果。

inputFormat:
第一行三个正整数 $n,m,c$ 和一个非 $0$ 即 $1$ 的数 $\mathrm{op}$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，只包含 `.` 和 `#` 两种字符，描述方格图的情况。如果第 $i$ 行的第 $j$ 个字符为 `#` 则表示方格图中第 $i$ 行第 $j$ 列的方格坏掉了，否则没有坏掉。

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

hint:
【样例 $1$ 说明】

共有如下 $7$ 种本质不同的图：

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

【样例 $6$ 说明】

下面给出两种本质不同的图：

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

【数据规模与约定】

本题采用捆绑测试：

Subtask 1（12 points）：$n=1$，$\mathrm{op}=0$，没有坏掉的格子。
Subtask 2（13 points）：$c=1$，$\mathrm{op}=0$。
Subtask 3（12 points）：$c=1$，$\mathrm{op}=1$。
Subtask 4（14 points）：$m\le 5$，$\mathrm{op}=0$。
Subtask 5（25 points）：$\mathrm{op}=0$。
Subtask 6（8 points）：$n\bmod 2=0$，$\mathrm{op}=1$。
Subtask 7（8 points）：$n\bmod 2=1$，$m\bmod 2=0$，$\mathrm{op}=1$。
Subtask 8（8 points）：$n\bmod 2=1$，$m\bmod 2=1$，$\mathrm{op}=1$。

对于 $100\%$ 的数据，$1\le n,m\le 9$，$1\le c\le 10^6$，$\mathrm{op}\in\{0,1\}$。


title: [SNOI2019] 字符串

description:
给出一个长度为$n$的由小写字母组成的字符串$a$，设其中第$i$个字符为$a_i(1≤i≤n)$ 。

设删掉第$i$个字符之后得到的字符串为$s_i$，请按照字典序对$s_1,s_2,……,s_n$从小到大排序。若两个字符串相等，则认为编号小的字符串字典序更小。

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

第二行一个长为$n$的由小写字母组成的字符串$a$。

outputFormat: 输出一行$n$个整数$k_1,k_2,……,k_n$，用空格隔开。表示$s_{k_1}<s_{k_2}<……<s_{k_n}$。

hint:
对于所有数据，$1≤n≤10^6$。

对于10%的数据，$1≤n≤2000$；

对于另外20%的数据，$1≤n≤10^5$且任意两个相邻字符$a_i,a_{i+1}$不相等；

对于另外30%的数据，$1≤n≤10^5$；

对于余下40%的数据，无特殊限制。


title: [ZJOI2019] 开关

description:
九条可怜是一个贪玩的女孩子。

这天，她和她的好朋友法海哥哥去玩密室逃脱。在他们面前的是 $n$ 个开关，开始每个开关都是关闭的状态。要通过这关，必须要让开关达到指定的状态。目标状态由一个长度为 $n$ 的 $01$ 数组 $s$ 给出，$s_i = 0$ 表示第 $i$ 个开关在最后需要是关着的，$s_i = 1$ 表示第 $i$ 个开关在最后需要被打开。

然而作为闯关者，可怜和法海并不知道 $s$。因此他们决定采用一个比较稳妥的方法：瞎按。他们根据开关的外形、位置，通过一些玄学的方法给每一个开关赋予了一个权值 $p_i$（$p_i > 0$）每一次，他们会以正比于 $p_i$ 的概率（第 $i$ 个开关被选中的概率是 $\frac{p_i}{\sum^n_{j=1}p_j}$ 选择并按下一个开关。开关被按下后，状态会被反转，即开变关，关变开。**注意，每一轮的选择都是完全独立的。**

在按开关的过程中，一旦当前开关的状态达到了 $s$ 那么可怜和法海面前的门就会打开，他们会马上停止按开关的过程并前往下一关。作为一名欧皇，可怜在按了 $\sum^n_{i=1} s_i$ 次后，就打开了大门。为了感受一下自己的运气是多么的好，可怜想要让你帮她计算一下，用这种随机按的方式，期望需要按多少次开关才能通过这一关。

inputFormat:
第一行输入一个整数 $n$，表示开关的数量。
第二行输入 $n$ 个整数 $s_i$（$s_i\in \{0,1\}$），表示开关的目标状态。第三行同样输入 $n$ 个整数 $p_i$，表示每个开关的权值。

outputFormat: 输出一行一个整数，表示答案对 $998244353$ 取模后的值。即如果答案的最简分数表示为，$\frac{x}{y}$（$x \ge 0$，$y \ge 1$，$\gcd(x, y) = 1$），你需要输出 $x \times y^{-1} \bmod 998244353$。


title: [ZJOI2019] 语言

description:
九条可怜是一个喜欢规律的女孩子。按照规律，第二题应该是一道和数据结构有关的题。

在一个遥远的国度，有 $n$ 个城市。城市之间有 $n - 1$ 条双向道路，这些道路保证了任何两个城市之间都能直接或者间接地到达。

在上古时代，这 $n$ 个城市之间处于战争状态。在高度闭塞的环境中，每个城市都发展出了自己的语言。而在王国统一之后，语言不通给王国的发展带来了极大的阻碍。为了改善这种情况，国王下令设计了 $m$ 种通用语，并进行了 $m$ 次语言统一工作。在第 $i$ 次统一工作中，一名大臣从城市 $s_i$ 出发，沿着最短的路径走到了 $t_i$，教会了沿途所有城市（包括 $s_i, t_i$）使用第 $i$ 个通用语。

一旦有了共通的语言，那么城市之间就可以开展贸易活动了。两个城市 $u_i, v_i$ 之间可以开展贸易活动当且仅当存在一种通用语 $L$ 满足 $u_i$ 到 $v_i$ 最短路上的所有城市（包括 $u_i, v_i$），都会使用 $L$。

为了衡量语言统一工作的效果，国王想让你计算有多少对城市 $(u, v)$（$u < v$），他们之间可以开展贸易活动。

inputFormat:
第一行输入两个正整数 $n, m$，表示城市数和通用语的数量。

接下来 $n - 1$ 行，每行两个整数 $x_i, y_i$（$1 \le x_i, y_i \le n$），表示了一条连接城市 $x_i, y_i$ 的道路。

接下来 $m$ 行，每行两个整数 $s_i, t_i$（$1 \le s_i, t_i \le n$），表示一次语言普及工作。

outputFormat: 输出一行一个整数，表示可以开展贸易活动的城市对数量。


title: [ZJOI2019] 浙江省选

description:
九条可怜是一个喜欢出题的女孩子，这道题是一道有关浙江省选的硬核模拟题。

在 $9102$ 年，有 $n$ 名选手参加了浙江省选，其中第 $i$ 个选手的智力是 $a_i$，训练量是 $b_i$。作为
出题人，可怜可以自由选择这套题的风格是比较偏套路还是比较偏智力。举例来说，$\mathrm{ZJOI}2018$ 的题就比较偏智力，今年的题就比较偏套路。

为了定量衡量一套题的风格，可怜定义了反向选拔指数 $x$，$x$ 是一个**非负整数**。第 $i$ 个选手在反向选拔指数为 $x$ 的题目上的表现为 $a_ix+b_i$。在 $x$ 给定的情况下，第 $i$ 个人的排名为表现严格大于 $a_ix+bi$ 的人数再加一。

在 $9102$ 年浙江省队的人数为 $m$，因此只有排名小于等于 $m$ 的人才能够进入浙江省队。注意当有并列的情况时，进入浙江省队的人数可能多于 $m$。

不难发现，选手的排名和 $x$ 的关系非常大。现在，可怜想让你计算，第 $i$ 个选手有没有可能进入浙江省队，如果有可能，他最好的排名是多少。

inputFormat:
第一行输入两个整数 $n,m(m\leq n)$，表示选手总数以及浙江省队的人数。
接下来 $n$ 行每行两个整数 $a_i,b_i$，表示每个选手的属性值。

outputFormat: 输出一行 $n$ 个整数，如果第 $i$ 个选手进不了浙江省队，就输出 $-1$，否则输出他可能的最好排名。


title: [SNOI2019] 数论

description:
给出正整数 $P,Q,T$ ，大小为 $n$ 的整数集 $A$ 和大小为 $m$ 的整数集 $B$ ，请你求出：

$$
\sum_{i=0}^{T-1}[(i\bmod P) \in A \land (i\bmod Q) \in B]
$$

换言之，就是问有多少个小于 $T$ 的非负整数 $x$ 满足：$x$ 除以 $P$ 的余数属于 $A$ 且 $x$ 除以 $Q$ 的余数属于 $B$。

inputFormat:
第一行 $5$ 个用空格隔开的整数 $P,Q,n,m,T$。

第二行 $n$ 个用空格隔开的整数，表示集合 $A=\{A_1,A_2,\cdots,A_n\}$。保证 $A_i$ 两两不同，且 $0 \leq A_i<P$。

第三行 $m$ 个用空格隔开的整数，表示集合 $B=\{B_1,B_2,\cdots,B_m\}$。保证 $B_i$ 两两不同，且 $0 \leq B_i<Q$。

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

hint:
对于所有数据，$1 \leq n,m \leq 10^6 , 1 \leq P,Q \leq 10^6 , 1 \leq T \leq 10^{18}$。

对于10%的数据，$T \leq 10^6$。

对于另外20%的数据，$P,Q \leq 1000$。

对于另外10%的数据，$T$是$P,Q$的公倍数。

对于另外10%的数据，$P,Q$互质，且$P,Q \leq 10^5$。

对于另外10%的数据，$P,Q$互质。

对于另外10%的数据，$P,Q \leq 10^5$。

对于余下30%的数据，无特殊限制。

- 2023.11.17 添加三组 hack 数据。


title: [SNOI2019] 通信

description:
$n$ 个排成一列的哨站要进行通信。第 $i$ 个哨站的频段为 $a_i$。

每个哨站 $i$ 需要选择以下二者之一：

1. 直接连接到控制中心，代价为 $W$；
2. 连接到前面的某个哨站 $j$ ($j<i$)，代价为 $|a_i-a_j|$。
每个哨站只能被后面的至多一个哨站连接。

请你求出最小可能的代价和。

inputFormat:
第 $1$ 行两个自然数 $n,W$，分别表示哨站个数和连接到控制中心的代价；

第 $2$ 行 $n$ 个由空格分隔的自然数 $a_1,a_2,\ldots,a_n$ 依次表示每个哨站的频段。

outputFormat: 输出 $1$ 行 $1$ 个自然数表示答案。

hint:
对于所有数据，$1 \leq n \leq 1000$，$0 \leq W,a_i \leq 10^9$。

对于 $10\%$ 的数据，$n \leq 10$；

对于另外 $10\%$ 的数据，$n \leq 20$；

对于另外 $20\%$ 的数据，$n \leq 50$，$W \leq 5$，$a_i \leq 4$；

对于另外 $20\%$ 的数据，$n \leq 100$；

对于另外 $20\%$ 的数据，$n \leq 300$；

对于余下 $20\%$ 的数据，无特殊限制。


title: [SNOI2019] 网络

description:
有$n$个数据中心，编号为$1,2,……,n$。它们被$n-1$条光缆连通，形成一棵树。

每条光缆传输数据时有$1$单位时间的延迟，两个数据中心之间的延迟为连接它们的光缆的延迟之和。

现在要在这$n$个数据中心中选若干个作为通讯站，要求任意两个通讯站之间的延迟不超过$d$。设选出的通讯站为${w_1,w_2,……,w_k}$，则通讯总延迟为这$k$个通讯站两两之间的延迟之和。

现在有$q$次询问，每次选定一个数据中心$u$，你需要求出：如果 $u$是一个通讯站，最大可能的通讯总延迟是多少。

inputFormat:
第一行两个自然数$n,d$ ，分别表示数据中心的个数和两个通讯站之间最大允许的延迟。

接下来$n-1$行每行两个正整数$u,v$表示$u$和$v$之间有一条光缆。

接下来一行一个正整数$q$表示询问次数。

接下来$q$行每行一个正整数$u$表示询问中选定的通讯站。

outputFormat: 输出共$q$行，每行一个整数表示该次询问的答案。

hint:
对于所有数据，$1 \leq n \leq 5*10^5 , 0 \leq d<n , 0 \leq q \leq 10$。

对于10%的数据，$n \leq 15$；

对于另外10%的数据，$d=n-1$；

对于另外15%的数据，$n \leq 300$；

对于另外15%的数据，$n \leq 5000$；

对于另外20%的数据，$n \leq 10^5$；

对于余下30%的数据，无特殊限制。


title: [Celeste-A] Sever the Skyline

background:
> 废弃的城市里充满了机关和陷阱，而今晚，我们将

> ——划破这城市的天际线

description:
Madeline 来到了被废弃的城市，这座城市里满是机关，还有一台不知所谓的机器在向外发射着光信号。

通过 Madeline 强大的观察力，她发现光信号其实对应着某种冲刺顺序，按照顺序冲刺之后，她发现她冲刺的轨迹构成了这座废弃城市的天际线。

多年以后，当 Madeline 回忆她登山的旅途时，已经不记得这座城市的天际线长什么样了，只记得所有建筑高度的和为 $n$，并且每座建筑的高度可以表示为 $p^iq^j$，$p,q$ 为素数且 $i,j \geq 0,i+j\geq 1$。

Madeline 知道，这座城市的天际线是很有美感的，不存在两座建筑使得它们的高度成**整倍数**关系(1倍也是整倍数)，例如若存在一座高度为 $2$ 的建筑，就一定不能存在高度为 $4$ 的建筑。

由于 Madeline 的记忆相当模糊，所以她可能要求你多次对于一个特定的记忆给出一个合法的天际线。

inputFormat:
第一行为一个整数 $T$，表示 Madeline 的询问次数。

接下来 $T$ 行，一行三个整数 $n,p,q$，分别表示本次回忆中建筑高度的和与题目描述中所述的 $p,q$。

outputFormat:
对于每组回忆输出一行若干个整数，以空格分隔，表示一组合法的天际线。

每组数据保证有解，若有多组合法的解，请输出任意一组。

**请不要在行末增加多余空格，否则会 WA。(即，行末无空格)**

hint:
对于前 $30\%$ 的数据，保证 $n \leq 100$，

对于另外 $20\%$ 的数据，保证 $p,q \leq 3$

对于 $100\%$ 的数据，保证 $1 < n \leq 10^{18}, p,q \leq 40, p < q, T \leq 10000$

对于最后 $30\%$ 的数据，采用捆绑测试，仅当您通过了所有测试点才能得分。

保证数据的生成方式为：

均匀随机两个质数 $p,q$，随机选择若干个 $p^iq^j$，保证它们不成倍数，将 $p^iq^j$ 的和作为 $n$，若这组数据满足当前数据点的要求，则保留，若不满足，则重新生成。

对于最后 $30\%$ 数据点，对于 $n$ 要求 $n > 10^{17}$。

对于最后 $30\%$ 数据点中的部分测试点，要求至少选出 $4$ 个 $p^iq^j$ 来组成 $n$。

**本题 spj 认可的格式为：行末无空格，每组输出行末换行。**

**若格式不正确，您可能会获得 UKE**


title: [Celeste-A] Black Moonrise

background:
> 幽灵
>
> 不属于这个世界
>
>但因这个世界而诞生
>
>潜藏在秩序之外
>
>$$
>
> 醒来吧，我的心是堡垒
>
>在梦中我易受伤害

description:
在 Madeline 的梦境中，城市的边境是由大大小小的宇宙碎片构成的

每个宇宙碎片都有一定的能量值，由于碎片的大小有一定的差异，因此它们的能量值也有大有小

Madeline 很享受在碎片之间穿梭，她每次都会选择两个宇宙碎片，并获得它们能量值的最大公约数的愉悦值。注意这两个宇宙碎片可以相同

宇宙碎片构成了一段序列$a_1,a_2,\cdots,a_n$，每次 Madeline 都会选择它的一个区间，对于这个区间里面的任意两个宇宙碎片$(u,v)$，她都会进行一次穿梭。注意这里的$(u,v)$是有序对

形式化地，Madeline 每次获得的愉悦值为

$$\sum_{i=l}^r\sum_{j=l}^r \gcd(a_i,a_j)$$

当 Madeline 从她的梦中被唤醒时，她发现所有的宇宙碎片都消失了。她不记得在梦中每次穿梭时获得的愉悦值是多少，只依稀记得她选择的区间了。

于是她找到了你——一个信息学大佬，请你根据她每次选择的区间，还原她当时的愉悦值

inputFormat:
第一行两个正整数$n,q$，分别表示碎片个数以及询问数

第二行有$n$个正整数$a_1,a_2,\cdots,a_n$，表示每个碎片的能量值

接下来$q$行，每行两个整数$l_i,r_i$，表示第$i$次询问 Madeline 选择的区间

outputFormat: 对于每个询问输出一行，表示在这次询问中，Madeline 获得的愉悦值的总和

hint:
对于$10\%$的数据，满足$n,q\leq 200$

对于$20\%$的数据，满足$n,q\leq 2250$

对于$40\%$的数据，满足$n,q\leq 4000$

对于$100\%$的数据，满足$n,q,a_i\leq 10^5$

**保证数列和询问均为随机生成**


title: [JSOI2019] 精准预测

background: JYY 和他的火星探险队再次登录火星小镇，并且打算把机器学习的知识传授给火星人，从而提高火星人的生活效率。但智力有限的火星人纷纷表示不相信计算机科学。为了让火星人彻底信服，JYY 的探险队找到了他们之前关于火星详细的数据记录，并且训练了一个预测模型，这个模型能准确地预测出火星人在未来的生死情况。

description:
目前，火星小镇上有$n$个居民（编号$1,2,……,n$）。机器学习算法预测出这些居民在接下来$T$个时刻（编号$1,2,……,T$）的生死情况，每条预测都是如下两种形式之一：

- 难兄难弟$0$ $t$ $x$ $y$：在$t$时刻，如果$x$是死亡状态，那么在$t+1$时刻，$y$是死亡状态。（注意，当$x$在$t$时刻是生存状态时，该预测也被认为是正确的）；

- 死神来了$1$ $t$ $x$ $y$：在$t$时刻，如果$x$是生存状态，那么在$t$时刻，$y$是死亡状态。（注意，当$x$在$t$时刻是死亡状态时，该预测也被认为是正确的）。

注意本题是对某个时刻进行生死状态的预测，如果某个人在$t$时刻是生存状态，在$t+1$时刻是死亡状态，你可以认为是在$t$到$t+1$这段时间内发生了某个事件导致其死亡。

虽然 JYY 对自己从大数据中统计得到的模型非常自信，但火星人看到这些预测吓了一跳，表示实在难以接受这种设定，更是认为计算机科学是可怕的邪教，打破了他们平静的生活。为了安抚火星人的情绪， JYY 打算从这些预测结果中推导出一些火星人更容易接受的事实，从而安抚火星人的情绪。

具体来说，JYY 首先假设对火星人生死的预测全部正确，在此基础上，JYY 希望为小镇上的每个居民$k$分别计算有多少个火星人有可能和他一起活到第$T+1$时刻，换言之，JYY 希望为每个火星人$k$计算

$$\sum_{1 \leq i \leq n,i \neq k} \operatorname{Live}(k,i)$$

其中 $\operatorname{Live}(i,j)=1$ 表示编号为$i$和$j$的火星人有可能同时在第 $T+1$ 时刻处于生还状态，否则$\operatorname{Live}(i,j)=0$。

注意火星人是不能够复活的。一个火星人可能在时刻$1$就处于死亡状态，也有可能有预测未覆盖的死亡情况发生（火星人在任何时候都可能死亡，但任意时刻观察到火星人的状态要么活着，要么死亡）。最后，注意到$\operatorname{Live}$是为每一对火星人分别独立计算的，因此$\operatorname{Live}(x,y)=1,\operatorname{Live}(y,z)=1$并不意味着$\operatorname{Live}(x,z)=1$。

inputFormat:
输入第一行包含三个整数$T,n,m$。
接下来有$m$行，每行表示一条预言，每条预言第一个整数$c$表示预言的类型：

- $c=0$：接下来读入$t,x,y$；

- $c=1$：接下来读入$t,x,y$。

outputFormat: 输出$n$个数表示答案，用空格分割。


title: [JSOI2019] 神经网络

background: 火星探险队发现，火星人的思维方式与人类非常不同，是因为他们拥有与人类很不一样的神经网络结构。为了更好地理解火星人的行为模式，JYY 对小镇上火星人的大脑进行了扫描，得到了一些重要数据。

description:
火星人在出生后，神经网络可以看作是一个由若干无向树 $\{T_1(V_1, E_1), T_2(V_2, E_2),\ldots T_m(V_m, E_m)\}$ 构成的森林。随着火星人年龄的增长，神经连接的数量也不断增长。初始时，神经网络中生长的连接 $E^\ast = \varnothing$。神经网络根据如下规则生长：
- 如果节点 $u \in V_i, v \in V_j$ 分别属于不同的无向树 $T_i$ 和 $T_j$（$i \neq j$），则 $E^\ast$ 中应当包含边 $(u, v)$。

最终，在不再有神经网络连接可能生长后，神经网络之间的节点连接可以看成是一个无向图 $G(V,E)$，其中

$$V=V_1\cup V_2\cup \ldots \cup V_m,E=E_1\cup E_2\cup \ldots \cup E_m\cup E^\ast$$

火星人的决策是通过在 $G(V, E)$ 中建立环路完成的。针对不同的外界输入，火星人会建立不同的神经连接环路，从而做出不同的响应。为了了解火星人行为模式的复杂性，JYY 决定计算 $G$ **中哈密顿回路的数量**。

$G(V, E)$ 的哈密顿回路是一条简单回路，从第一棵树的第一个节点出发，恰好经过 $V$ 中的其他节点一次且仅一次，并且回到第一棵树的第一个节点。

inputFormat:
第一行读入 $m$，表示火星人神经网络初始时无向树的数量。
接下来输入有 $m$ 部分，第 $i$ 部分描述了树 $T_i$。
对于 $T_i$，输入的第一行是树 $T_i(V_i, E_i)$ 中节点的数量 $k_i$。假设 $V_i = \{v_1, v_2,\ldots ,v_{k_i}\}$。
接下来 $k_{i} - 1$ 行，每行两个整数 $x, y$，表示该树节点 $v_x, v_y$（$1 \le x, y \le k_i$）之间有一条树边，即 $(v_x, v_y) \in E_i$。

outputFormat: 因为哈密顿回路的数量可能很多，你只需要输出一个非负整数，表示答案对 $998244353$ 取模后的值。


title: [JSOI2019] 节日庆典

background: JYY 和探险队顺利完成了火星上的任务。在离开前，探险队正好赶上了火星人一年一度最盛大的节日「气球节」。然而，火星人遇到了每年一度的麻烦：怎样最美观地摆放气球。JYY 决定请你设计算法帮助火星人解决这个问题。

description:
在庆典开始前，火星人会把气球准备好并串在一根绳子上。气球按顺序排列可以看成是一个由小写字母组成的长度为$n$的字符串$S$。然后，火星人会按照字符串的顺序逐个把气球加入到一个庆典的圆环上，并且表演一个节目庆祝。

下图展示了一串气球 **cbbadbcd** 在进行到第$5$个节目时的情形，此时在庆典环上的气球是 **cbbad**。

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

为了让每个节目都更好看，火星人希望在每个节目开始前调整气球在环上的顺序，使得每个节目的气球排布都最美观。对于一组气球（一个字符串），火星人认为最美观的字符串是庆典圆环上按绳子方向读出**字典序最小的字符串**，例如对于 **cbbad**，共有$5$个读出字符串的位置：

- cbbad （$i=1$）；

- bbadc （$i=2$）；

- badcb （$i=3$）；

- adcbb （$i=4$）；

- dcbba （$i=5$）。

如果有多个字典序最小的字符串，火星人希望找出**离绳头最近**的那个(即最小的那个)。更严谨地说，对于字符串，定义

$$T_i=T[i……|T|]::T[1……i-1](1 \leq i \leq |T|)$$

其中$::$是字符串的拼接操作。定义$f(T)$为最小的$i$（$1 \leq i \leq |T|$）满足$T_i=min(T_1,T_2,……,T_{|T|})$。

JYY希望你帮助他设计一个算法，让火星人每个节目的气球排列都最美观，即对于给定字符串$S$的每一个前缀$S[1……i]$（$1 \leq i \leq |S|$），求出$f(S[1……i])$。

inputFormat: 输入只有一行，该行包括一个字符串$S$。

outputFormat: 在一行中对于每个$i$（$1 \leq i \leq |S|$），输出一个整数$f(S[1……i])$。输出的数字之间以空格分隔。

samples:
abaacaba
1 1 3 3 3 6 3 8


title: [Celeste-A] Good Karma

background:
> "我们永远不会忘记在这里的时光"

> "再也没有其他地方能让我感到平静。谢谢。"

> "很遗憾，Oshiro 先生，山庄要关门了。"

> "我会赶上他们，直到这里的一切都井然有序……"

> "在离开这个山庄之后，我应该去哪儿呢？"

description:
天空度假山庄是位于 Celeste 山半山腰上的一座山庄，这里已经被废弃许久。

当 Madeline 来到这座山庄之时，这里只剩下了一个幽灵，Oshiro 先生，独自管理这座山庄。

因为山庄有着神奇的魔力，里面凝聚着许多 Oshiro 先生不好的想法。

一个想法可能包含 $k$ 种不好的念头，诸如山庄倒闭，无人问津，无人体谅等等，每种念头对于 Oshiro 先生的重要度是不一样的，具体来讲，第 $i$ 种不好的念头对 Oshiro 先生的重要程度为 $2^{i-1}$。

有时，Oshiro 先生会抓起一堆糟糕的想法进行回忆，Oshiro 会一个一个挨着观看这些想法，并获得其中不好的念头。特别地，当 Oshiro 先生**两次看到同一种不好的念头**时，他就会认为这种念头没什么，下一瞬间就会**忘记自己曾经看到过这种念头**。

一次回忆对 Oshiro 先生的重要程度为 Oshiro 在看完这些想法之后**记住的念头**的重要程度和。

自然，在天空度假山庄里，Oshiro 先生对 Madeline 大吐苦水。

多年以后，当 Madeline 回忆她的登山之旅的时候，已经不记得 Oshiro 每个想法对于他的重要程度了，她只记得 Oshiro 先生的某几次回忆的重要程度以及天空度假山庄之中不好的想法的数量与每种想法中可能的不好的念头的数量。

你能帮助她找出有多少种合法的想法序列满足 Oshiro 先生的每次回忆吗？

特别地，一个想法也可能是一团浆糊，即里面什么都没有。

inputFormat:
第一行为三个整数 $n,q,k$，表示不好的想法的数量，Madeline 告诉了你 $q$ 条信息，以及每个想法中可能存在的不好的念头的数量。

接下来 $q$ 行，一行一条信息，首先是信息的类型 $op$。

若 $op = 0$， 则接下来是三个整数 $l,r,val$，表示 Madeline 想起在某次回忆中 Oshiro 先生抓起编号在 $[l,r]$ 区间的想法回忆，回忆结束后重要度是 $val$。

若 $op = 1$，则接下来是一个整数 $cnt$，表示 Madeline 纠正了**第 $cnt$ 条 $op = 0$ 的说法**，第 $cnt$ 条说法是她错误回忆起来的，保证第 $cnt$ 条说法存在并且没有被纠正过。(你可以认为，被纠正的说法就不再存在了)

若 $op = 2$，则你需要输出一个整数，表示有多少种合法的想法序列满足当前 Oshiro 先生的每次回忆，对 $998244353$ 取模。

outputFormat: 对于每次 $op = 2$，输出方案数，对 $998244353$ 取模。


title: [TJOI2019] 甲苯先生的字符串

background:
TJOI2019 D1T1

源文件名：str.*

时间限制: 1s 内存限制: 128M

description: 一天小甲苯得到了一条神的指示，他要把神的指示写下来，但是又不能泄露天机，所以他要用一种方法把神的指示记下来。神的指示是一个字符串，记为字符串$s_1$，$s_1$仅包含小写字母a − z。现在小甲苯想要写下神的指示，记为字符串$s_2$，$s_2$仅包含小写字母a − z，要求$s_1$中的相邻的两个字母不能在$s_2$中相邻地出现。现在给定$s_2$的长度，小甲苯想知道他有多少种方法可以将神的指示写下来。输出种类数结果对$10^9+7$取模。

inputFormat:
第一行只有一个正整数$n$，代表字符串$s_2$的长度，$n\le10^{15}$。

第二行是一个字符串，代表字符串$s_1$。$s_1$的长度不超过$100000$。

outputFormat: 输出一个整数，表示小甲苯可以写出的字符串的总数。结果对$10^9+7$取模

hint:
对于30%的数据$n\le100000$

对于100%的数据$n\le10^{15}$

说明：相邻要求顺序相同，如样例中的$s_2$里不能出现$ab$，且仅不能出现$ab$，但可以出现$ba$.


title: [TJOI2019] 甲苯先生的滚榜

description:
甲苯先生在制作一个 Online Judge，他发现做比赛的人们很关心自己的排名（显而易见）。

在 ACM 赛制的比赛中，如果通过题目数量不相等，则通过题目数量多的人排名更靠前；
如果通过题目数量相等，则罚时更少的人排名更高。

甲苯先生想让大家帮忙设计一个程序，每次有人通过之后，就告诉他排名在他的前面有多少人。
（不包括和他罚时题数都相同的同学）

inputFormat:
第一行输入一个整数 $T$ 表示测试样例的个数。

对于每一个样例，输入三个整数 $m, n, \text{seed}$。
$m$ 表示参赛总人数（编号 $1 \sim m$），$n$ 表示一共有 $n$ 次 AC（假设 AC 已经去重，即不存在相同人的相同题目提交）。
$\text{seed}$ 表示生成数据的种子。

接下来要求同学们使用之下的函数生成数据：
```cpp
typedef unsigned int ui ;
ui randNum( ui& seed , ui last , const ui m){
    seed = seed * 17 + last ; return seed % m + 1;
}
```
（$\texttt{last}$ 为上一次输出的结果，在没有输出结果时 $\texttt{last} = 7$，多组数据时 $\texttt{last}$ 不需要重新赋值）
要求每次生成两个数据 $\texttt{Ria}, \texttt{Rib}$，表示第 $\texttt{Ria}$ 个人 AC 了一道题目，他的罚时为 $\texttt{Rib}$。
（也就是说 $\texttt{Ria}$ 的题目数量 $+1$，罚时长度 $+\texttt{Rib}$）。

要求一共生成 $n$ 组数据，代表一共有 $n$ 次提交。

对于所有数据，保证罚时总和不超过 $1.5\times 10^6$。

outputFormat: 每次提交输出一行整数，表示在第 $\texttt{Ria}$ 个人 AC 后，比 $\texttt{Ria}$ 成绩高的有多少个选手。


title: [TJOI2019] 唱、跳、rap和篮球

background:
TJOI2019 D1T3

源文件名：queue.*

时间限制: 4s 内存限制: 128M

description: 大中锋的学院要组织学生参观博物馆，要求学生们在博物馆中排成一队进行参观。他的同学可以分为四类：一部分最喜欢唱、一部分最喜欢跳、一部分最喜欢rap，还有一部分最喜欢篮球。如果队列中$k$,$k + 1$,$k + 2$,$k + 3$位置上的同学依次，最喜欢唱、最喜欢跳、最喜欢rap、最喜欢篮球，那么他们就会聚在一起讨论蔡徐坤。大中锋不希望这种事情发生，因为这会使得队伍显得很乱。大中锋想知道有多少种排队的方法，不会有学生聚在一起讨论蔡徐坤。两个学生队伍被认为是不同的，当且仅当两个队伍中至少有一个位置上的学生的喜好不同。由于合法的队伍可能会有很多种，种类数对$998244353$取模。

inputFormat: 输入数据只有一行。每行$5$个整数，第一个整数$n$，代表大中锋的学院要组织多少人去参观博物馆。接下来四个整数$a$、$b$、$c$、$d$，分别代表学生中最喜欢唱的人数、最喜欢跳的人数、最喜欢rap的人数和最喜欢篮球的人数。保证$a+b+c+d \ge n$。

outputFormat: 每组数据输出一个整数，代表你可以安排出多少种不同的学生队伍，使得队伍中没有学生聚在一起讨论蔡徐坤。结果对$998244353$取模。


title: [THUSC2016] 补退选

description:
X 是 T 大的一名老师，每年他都要教授许多学生基础的 C++ 知识。在 T 大，每个学生在每学期的开学前都需要选课，每次选课一共分为三个阶段：预选，正选，补退选；其中「补退选」阶段最忙碌。
在补退选阶段，学生即可以选课，也可以退课。对于X老师来说，在补退选阶段可能发生以下两种事件：
1.一个姓名为 $S$ 的学生选了他的课（姓名将出现在 X 的已选课学生名单中）
2.一个姓名为 $S$ 的学生退了他的课（姓名将从 X 的已选课学生名单中移除）
同时，X 老师对于有哪些学生选了他的课非常关心，所以他会不定时的查询已选课学生名单，每次查询的格式如下：
```
最早在哪个事件之后，姓名以 S 为前缀的学生数量超过了 v
```
X老师看你骨骼惊奇，所以想用这个问题考考你，你当然不会畏惧，所以勇敢的接下了这个任务。
**注意1：学生的姓名可能相同，如果有$p$个姓名相同的学生都选了X老师的课，则他们的姓名将出现在X老师的名单上$p$次。**

**注意2：只有已经选了课的学生才会退课，如果姓名为$S$的学生退课，则在他退课之前X老师的名单上一定有姓名。**

**注意3：选课，退课和查询都被定义为「事件」，「事件」的编号从 1 开始**

inputFormat:
第一行包含一个正整数$n$ ，表示一共发生了$n$ 个事件。
接下来$n$行，每行描述一个事件；每行第一个正整数$k$表示事件类型
1.如果$k = 1$ ，表示选课事件，接下来一个字符串$S$ ，表示一个姓名为$S$的学生选了 X 老师的课

2.如果$k = 2$,表示退课事件，接下来一个字符串$S$，表示一个姓名为$S$的学生退了 X 老师的课

3.如果$k = 3$，表示查询事件，接下来一个字符串$S$以及三个非负整数$a,b,c$ .
表示X老师想知道最早在第几个事件之后，姓名以$S$为前缀的学生数量超过了$(a * |ANS| + b) mod c$ ，$|ANS|$ 表示上次查询事件的答案的绝对值，如果当前是第一次查询，则$|ANS|$ = 0 ；如果任何时刻都没有超过该值，则答案为 $-1$ 。
**注：输入中的所有字符串均只包含小写字母。**

outputFormat: 对于每个查询事件，输出一行表示该查询答案。

hint: $n ≤ 100000,|S| ≤  60$,输入中的所有字符串只会包含前$10$个小写字母


title: [THUSC2016] 成绩单

description:
期末考试结束了，班主任 L 老师要将成绩单分发到每位同学手中。L 老师共有 $n$ 份成绩单，按照编号从 $1$ 到 $n$ 的顺序叠放在桌子上，其中编号为 $i$ 的的成绩单分数为 $W_i$。
成绩单是按照批次发放的。发放成绩单时，L 老师会从当前的一叠成绩单中抽取连续的一段，让这些同学来领取自己的成绩单。当这批同学领取完毕后，L 老师再从剩余的成绩单中抽取连续的一段，供下一批同学领取。经过若干批次的领取后，成绩单将被全部发放到同学手中。
然而，分发成绩单是一件令人头痛的事情，一方面要照顾同学们的心理情绪，不能让分数相差太远的同学在同一批领取成绩单；另一方面要考虑时间成本，尽量减少领取成绩单的批次数。对于一个分发成绩单的方案，我们定义其代价为：
$$a \times k + b \times \sum_{i = 1} ^ k (max_i - min_i) ^ 2$$
其中 $k$ 是分发的批次数，对于第 $i$ 批分发的成绩单，$max_i$ 是最高分数，$min_i$ 是最低分数，$a$ 和 $b$ 是给定的评估参数。现在，请你帮助 L 老师找到代价最小的分发成绩单的方案，并将这个最小的代价告诉 L 老师。当然，分发成绩单的批次数 $k$ 是你决定的。

inputFormat: 第一行包含一个正整数 $n$，表示成绩单的数量。第二行包含两个非负整数 $a,b$，表示给定的评估参数。第三行包含 $n$ 个正整数，$w_i$ 表示第 $i$ 张成绩单上的分数。

outputFormat: 仅一个正整数，表示最小的代价是多少。


title: [Ynoi2017] 由乃的玉米田

description:
由乃在自己的农田边散步，她突然发现田里的一排玉米非常的不美。

这排玉米一共有 $N$ 株，它们的高度参差不齐。

由乃认为玉米田不美，所以她决定出个数据结构题

这个题是这样的：

给你一个序列 $a$，长度为 $n$，有 $m$ 次操作，每次询问一个区间是否可以选出两个数它们的差为 $x$，或者询问一个区间是否可以选出两个数它们的和为 $x$，或者询问一个区间是否可以选出两个数它们的乘积为 $x$ ，或者询问一个区间是否可以选出两个数它们的商为 $x$（没有余数） ，这四个操作分别为操作 $1,2,3,4$。

选出的这两个数可以是同一个位置的数。

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

后面一行 $n$ 个数表示 $a_i$。

后面 $m$ 行每行四个数 $opt,l,r,x$。

$opt$ 表示这个是第几种操作，$l,r$ 表示操作的区间，$x$ 表示这次操作的 $x$。

outputFormat: 对于每个询问，如果可以，输出 `yuno`，否则输出 `yumi`。

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

对于 $100\%$ 的数据，所有输入的数在 $[0,10^5]$ 内，序列中的元素在 $[1,10^5]$ 内。


title: [TJOI2019] 大中锋的游乐场

description:
大中锋正在一个游乐场里玩耍。游乐场里有 $n$ 个娱乐设施，娱乐设施之间相互有共 $m$ 条道路相连，经过每一条路都需要花费一定的时间。为了方便游客，每一个娱乐设施旁都会配有一个小卖部，一部分小卖部会销售可乐，另一部分会销售汉堡。

由于大中锋十分贪吃，所以每当他走到一个娱乐设施，他都会先去购买一杯可乐或一个汉堡，并把它们吃掉。但如果大中锋吃掉的汉堡数量比他喝掉的可乐数量多于 $k$ ，那他就会感到很渴；如果喝掉的可乐数量比吃掉的汉堡数量多于 $k$ ，那他就会感到很饿。

现在大中锋正在第 $a$ 个娱乐设施，他想前往第 $b$ 个娱乐设施，但在他前进的路途中他不希望自己很渴或很饿。大中锋想知道自己在路上少花费多少时间。但由于大中锋很懒惰，他不想思考这个问题。你能帮助他解决这个问题吗？

注意：大中锋非常贪吃，所以他到达每个点的第一件事是去吃(或者喝)，才考虑其他的事情，所以在起始点和终点他都会去买汉堡(可乐)，你也需要保证在这两个点他不会感到很饿或者很渴。

inputFormat:
输入的第一行是一个整数 $T$ 表示数据组数数，对于每组数据的格式如下：

第一行有三个整数，分别代表游乐场的娱乐设施个数 $n$，游乐场的道路数 $m$ ， 以及给出的参数 $k$，其含义见【题目描述】。

第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 代表编号为 $i$ 的娱乐设施旁的小卖部销售的物品，$1$ 表示可乐，$2$ 表示汉堡。

第 $3$ 到第 $(m + 2)$ 行，每行三个整数 $u, v, w$，代表从第 $u$ 个娱乐设施到第 $v$ 个娱乐设施有存在一条双向道路，通过该道路需要花费时间 $w$。

第 $m + 3$ 行有两个整数 $s, t$ ，代表大中锋想从娱乐设施 $s$ 前往娱乐设施 $t$。

outputFormat: 对于每组数据输出一行一个整数表示答案。如果无解，请输出 $-1$。

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

- 对于 $30\%$ 的数据，保证 $n\leq 50,m\leq 1000$。
- 对于 $100\%$ 的数据，保证 $1 \leq n\leq 10000$，$1 \leq m\leq 100000$，$1 \leq k\leq 10$，$1 \leq a_i \leq 2$，$1 \leq u, v,s, t \leq n$，$1 \leq w \leq 10000$。

对于所有数据，保证 $1 \leq T \leq 10$ ，且每个测试点的大数据不超过 $2$ 个。

#### 题目补充说明

- 路径不一定是简单路径。
- 大中锋可以多次经过一个节点，同时每次都会取得汉堡/可乐。


title: [TJOI2019] 甲苯先生和大中锋的字符串

background:
TJOI2019 D2T2

源文件名：substring.*

时间限制: 1s 内存限制: 128M

description:
大中锋有一个长度为 $n$ 的字符串，他只知道其中的一个子串是祖上传下来的宝藏的密码。但是由于字符串很长，大中锋很难将这些子串一一尝试。

这天大中锋找到甲苯先生算命，但是甲苯先生说：“天机不可泄漏”。

在大中锋的苦苦哀求下，甲苯先生告诉大中锋：“密码是在字符串中恰好出现了 $k$ 次的子串”。

但是大中锋不知道该怎么做，在大中锋再三的恳求下，甲苯先生看其真诚，又告诉他：“在恰好出现了 $k$ 次的子串中，你去按照字串的长度分类，密码就在数量最多的那一类里”。

大中锋为了尝试这个密码，想让你帮忙找出子串长度出现次数最多的长度数（如果有多个输出最长长度）。

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

接下来 $T$ 行每行包含一个字符串和一个正整数 $k$ 。

outputFormat: 一共输出 $T$ 行，每行一个整数表示在出现 $k$ 次的子串中出现次数的最多的长度。如果不存在子串出现 $k$ 次，则输出 $-1$ 。

samples:
6
aab 1
abc 1
aaaa 2
abab 2
ababacc 2
abab 4

hint:
### 数据说明 ###

对于第一个数据：其中子串 $b, aa, ab, aab$ 均只出现一次，其中长度为 $1$ 的子串出现了 $1$ 次，长度为 $2$ 的子串出现了 $2$ 次，长度为 $3$ 的子串出现了 $1$ 次。所以答案为 $2$ 。

对于第二个数据：其中子串 $a, b, c, ab, bc, abc$ 均只出现一次，其中长度为 $1$ 的子串出现了 $3$ 次，长度为 $2$ 的子串出现了 $2$ 次，长度为 $3$ 的子串出现了 $1$ 次。所以答案为 $1$ 。

对于第三个数据：其中子串 $aaa$ 出现二次，长度为 $3$ 的子串出现了 $1$ 次，其他长度均没有。所以答案为 $3$ 。

对于第四个数据：其中子串 $a, b, ab$ 出现二次，其中长度为 $1$ 的子串出现了 $2$ 次，长度为 $2$ 的子串出现了 $1$ 次。所以答案为 $1$ 。

对于第五个数据：其中子串 $b, c, ab, ba$ 出现二次，其中长度为 $1$ 的子串出现了 $2$ 次，长度为 $2$ 的子串出现了 $2$ 次。所以答案为 $2$ 。

对于第六个数据：其中子串没有出现四次。所以本题的本题的答案为 $-1$ 。

### 数据范围 ###

对于 $20\%$ 的数据， $1\leq k\leq n\leq 10$

对于 $100\%$ 的数据， $1\leq n\leq 10^5,1 \leq T \leq 100,\sum n \leq 3 * 10^6$ ，输入的字符串中仅包含小写英文字母。


title: [TJOI2019] 甲苯先生的线段树

background:
TJOI2019 D2T3

源文件名：segment.*

时间限制: 4s 内存限制: 128M

description:
大中锋走在路上见到正在战术后仰的甲苯先生。因为甲苯先生帮助他解决了祖传 `Hello word!` 的代码密码，大中锋想上前打个招呼。

甲苯先生突然举起喇叭说：「大家好，我是甲苯拦你斯特，是凯岩城的首席文化大使，七十二变显神通，百般武艺样样有，感受不一样的权游文化。」

这时甲苯先生看到了大中锋，激动的拉着大中锋说：「为了筹钱去北境打异鬼，我参加了今年下半年中外合写的 `stl+` 项目，我将在项目中担任线段树的主写人，但是改写不是乱写，在我写的时候，发现线段树是一个满二叉树，如果让根节点编号为 $1$，对于一个编号为 $x$ 的节点，令左孩子编号为 $2x$ ，右孩子编号为 $2x+1$ 时，现在在这个二叉树上有两个节点 $a,b$，现在我想知道节点 $a$ 到节点 $b$ 之间一条路径编号和最小为多少？你要是不会就直接给我 328，我不知道什么是暗影崛起，也不知道什么是怪盗军团。」

大中锋回答：「那不就是求一条简单路径直接算吗？」甲苯先生：「那你求这颗满二叉树中还有多少条简单路径等于这个值？不知道了吧，给我 328，我到北境打赢异鬼，回到凯岩城我就还你，我们拦你斯特，有债必偿。」

大中锋为了不给甲苯先生 328，请求作为好朋友的你写一个程序能解决甲苯先生的问题。

简单路径指的是路径上各个顶点均不重复的路径。

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

接下来 $T$ 行，每行包含 $4$ 个正整数 $d,a,b,c$。其中 $d$ 表示满二叉树的树高，$a，b $表示二叉树上的两个节点，$c$ 表示要回答甲苯先生的问题类别，$c=1$ 时，回答甲苯先生第一个问题（点 $a$ 到点 $b$ 的最小路径上的编号和），$c=2$ 时，回答甲苯先生的第二个问题，即回答除了从点 $a$ 到点 $b$ 的路径外与点 $a$ 到点 $b$ 的最小编号路径有相同编号和的简单路径的条数。

outputFormat: 对于每组输入，输出一行，每行包含一个正整数，表示甲苯先生问题的答案。

hint:
### 样例解释 ###

对于一颗深度为 $3$ 的满二叉树，含有节点 $1,2,3,4,5,6,7$ 。

节点 $1$ 到 $1$ 的路径编号和为 $1$ ，且没有其他路径编号和为 $1$ 。

节点 $1$ 到 $2$ 的路径编号和为 $1+2=3$ ，存在路径 3-3 编号和为 $3$。

节点 $2$ 到 $4$ 的路径编号和为 $2+4=6$ ，存在路径 2-1-3 和路径 6-6 编号和为 $6$ 。

节点 $1$ 到 $5$ 的路径编号和为 $1+2+5=8$ ，存在路径 8-8 编号和为 $8$ ，但是节点 $8$ 的深度为 $4$ 不满足条件。

### 数据范围 ###

对于 $20\%$ 的数据，仅存在 $c = 1$ 的情况

对于 $20\%$ 的数据， $d \leq 10$

对于 $30\%$ 的数据， $d \leq 20$

对于 $40\%$ 的数据， $d \leq 25$

对于 $50\%$ 的数据， $d \leq 30$

对于 $100\%$ 的数据， $d \leq 50,T \leq 10$


title: [Ynoi2017] 由乃打扑克

description:
由乃不太会打扑克

所以她出了一个数据结构题

给你一个长为 $n$ 的序列 $a$，需要支持 $m$ 次操作，操作有两种：

1. 查询区间 $[l,r]$ 的第 $k$ 小值。
2. 区间 $[l,r]$ 加上 $k$。

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

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

接下来 $m$ 行，每行四个数 $opt,l,r,k$，其中 $opt$ 代表是哪种操作。

outputFormat: 对于每个询问输出一个数表示答案，如果无解输出 $-1$。

hint:
Idea：nzhtl1477，

Solution：nzhtl1477( $O( msqrtn( \Delta + logn ) )$ ) solution，ccz181078( $O( msqrt(nlogn) )$ ) solution

Code：nzhtl1477( $O( msqrtn( \Delta + logn ) )$ ) code，ccz181078( $O( msqrtnlogn )$ ) code

，Data：nzhtl1477

$1\leq n,m\leq 10^5$，$-2\times 10^4\leq $ 每次加上的数和原序列的数 $\leq 2\times 10^4$。

---

$\text{upd 2022.8.18}$：新增加一组 Hack 数据。


title: 幼儿园篮球题

background: 众所周知，全民制作幼儿园园龄两年半的蔡徐坤同学喜欢唱、跳、rap 和篮球。而作为欧文的老师，他的篮球技术自然比 ikun 们要强得多。

description:
全民制作幼儿园的蔡徐坤专属篮球场上总共有 $N$ 个蔡徐坤专属篮球，而其中有 $M$ 个是没气的。鉴于蔡徐坤的高超技术，他投**没气的球一定能进**，而投**有气的球一定不能**。

蔡徐坤举办了 $S$ 场巡回篮球表演，第 $i$ 场表演 ikun 们会指定投球个数 $k_i$ ，ikun 们会从 $N$ 个蔡徐坤专属篮球中准备 $n_i$ 个球放在场地上，其中恰好有 $m_i$ 个是没气的。蔡徐坤会在这 $n_i$ 个蔡徐坤专属篮球中**随机**选出 $k_i$ 个投篮。如果投进了 $x$ 个，则这次表演的**失败度**为 $x^L$。ikun 们想知道这 $S$ 场表演的**期望失败度**对 $998244353$ 取模的结果。篮球表演之间**相互独立**。

inputFormat:
第一行，四个正整数，$N,M,S,L$，表示蔡徐坤专属篮球总个数，没气的篮球总个数，蔡徐坤巡回篮球表演场数，以及失败度参数。

接下来的第 $i+1$ 行，每行三个正整数 $n_i,m_i,k_i$，表示第 $i$ 场表演蔡徐坤专属篮球个数、没气的篮球个数和 ikun 们指定的投球个数。

outputFormat: 输出共 $S$ 行，第 $i$ 行为一个正整数，表示第 $i$ 场表演的期望失败度对 $998244353$ 取模的结果。

hint:
对于样例，我们作出如下解释：设失败度为 $X$，蔡徐坤有 $\frac{1}{3}$ 的概率投进 $2$ 个，有 $\frac{2}{3}$ 的概率投进 $1$ 个，期望失败度为 $E(x)=\frac{2^3}{3}+\frac{1^3*2}{3}=\frac{10}{3}$，$\frac{10}{3}\equiv 332748121\pmod{998244353}$。

子任务 1 ($15\%$)：$1\leq L\leq2$。

子任务 2 ($10\%$)：$1\leq N\leq10^5$。

子任务 3 ($75\%$)：无特殊限制。

对于全部数据，$1\leq S\leq200$，$1\leq L\leq2\times 10^5$，$1\leq M\leq N\leq2\times 10^7$。并且对于 $1\leq i\leq S$，有 $1\leq m_i,k_i\leq n_i\leq N$，$1\leq m_i\leq M$。


title: [JSOI2013] 快乐的 JYY

background:
JYY 在 JSOI 有很多很多的好朋友，比如 PUPPY，KFC 还有 PUPPUP 。因为
有了这么多的好朋友，所以 JYY 每天都很快乐。某天，JYY 发现好朋友之间关
系的好坏和名字有很大的关系，比如 PUPPY 和 PUPPUP 的关系就特别好，但是和 KFC 的关系就很一般。JYY 苦思冥想终于发现了其中的规律，现在 JYY 想知道两个朋友之间关系的好坏，你能帮助 JYY 么？

description:
给定两个字符串 $A$ 和 $B$，表示 JYY 的两个朋友的名字。我们用 $A(i,\,j)$ 表示 $A$
字符串中从第 $i$ 个字母到第 $j$ 个字母所组成的子串。同样的，我们也可以定义 $B(x,\,y)$ 。

JYY 发现两个朋友关系的紧密程度，等于同时满足如下条件的四元组 $(i,\,j,\,x,\,y)$
的个数：
1. $1\leq i\leq j\leq |A|$
2. $1\leq x\leq y\leq |B|$
3. $A(i,\,j)=B(x,\,y)$
4. $A(i,\,j)$ 是回文串

$|A|$ 表示字符串 $A$ 的长度。

JYY 希望你帮助他计算出这两个朋友之间关系的紧密程度。

inputFormat: 数据包行两行由大写字母组成的字符串 $A$ 和 $B$ 。

outputFormat: 包含一行一个整数，表示紧密程度，也就是满足要求的 $4$ 元组个数


title: 【模板】AC 自动机

background: 本题原为“AC 自动机（二次加强版）”。完成本题前可以先完成 [AC 自动机（简单版）](https://www.luogu.com.cn/problem/P3808) 和 [AC 自动机（简单版 II）](https://www.luogu.com.cn/problem/P3796) 两道题，为 AC 自动机更简单的应用。

description: 给你一个文本串 $S$ 和 $n$ 个模式串 $T_{1 \sim n}$，请你分别求出每个模式串 $T_i$ 在 $S$ 中出现的次数。

inputFormat:
第一行包含一个正整数 $n$ 表示模式串的个数。

接下来 $n$ 行，第 $i$ 行包含一个由小写英文字母构成的非空字符串 $T_i$。

最后一行包含一个由小写英文字母构成的非空字符串 $S$。

**数据不保证任意两个模式串不相同**。

outputFormat: 输出包含 $n$ 行，其中第 $i$ 行包含一个非负整数表示 $T_i$ 在 $S$ 中出现的次数。

hint: 对于 $100 \%$ 的数据，$1 \le n \le 2 \times {10}^5$，$T_{1 \sim n}$ 的长度总和不超过 $2 \times {10}^5$，$S$ 的长度不超过 $2 \times {10}^6$。


title: [SDOI2019] 快速查询

description:
给定一个长度为 $n$ 的整数数列，里面的元素依次编号为 $a_1,~a_2,~a_3,~\dots,~a_n$。初始的时候，所有元素都为零。现在按照时间顺序提供了若干次关于这个数列的修改或询问，每一次修改或询问一定为以下六种情况之一：

- **1 i val** ：将 $a_i$ 赋值为给定整数 $val$；

- **2 val** ：将所有元素同时加上 $val$；

- **3 val** ：将所有元素同时乘上 $val$；

- **4 val** ：将所有元素同时赋值为 $val$；

- **5 i** ：询问第 $i$ 个元素 $a_i$ 现在的值是多少；

- **6** ：询问现在所有元素的和。

inputFormat:
为了避免读入太大，输入文件采取如下的形式。

第一行给定整数 $n$，表示给定数列长度为 $n$。
 第二行给定整数 $q$，并且之后的 $q$ 行，每一行提供一个修改或询问，输入的格式与题目所述一致，请参见样例。
 我们称上述给定的修改或询问为标准操作。
 之后给定一个整数 $t$，并且之后的 $t$ 行每行给定两个正整数 $a_i$ 和 $b_i$，这里的下标 $i$ 依次记为 $1$ 到 $t$ 。

你需要对初始值全为零的长度为 $n$ 的序列做总计 $t\times q$ 次操作。
 其中第 $\Big((i-1)q+j\Big)$ 次操作形如第 $\Big((a_i + j b_i) \mod{q} + 1\Big)$ 个给定的标准操作（$1\le i\le t$ 且 $1\le j\le q$）。

outputFormat:
输出一个整数，表示所有询问答案的累计和。

因为答案可能很大，只要求输出其结果关于 $p=10^7+19$ 取模后的值。

注意：若最终的累计和 ans 小于零，你应该输出 $\big((ans \mod{p})+p\big)\mod{p}$。


title: [SDOI2019] 染色

description:
给定 $2 \times n$ 的格点图。其中一些结点有着已知的颜色，其余的结点还没有被染色。

 一个合法的染色方案不允许相邻结点有相同的染色。

现在一共有 $c$ 种不同的颜色，依次记为 $1$ 到 $c$。

 请问有多少对未染色结点的合法染色方案？

inputFormat:
第一行有两个整数$n$和$c$，分别描述了格点图的大小和总的颜色个数。

之后两行，每行有$n$个整数：如果是 $0$ 则表示对应结点未被染色，否则一定是一个$1$到$c$的整数表示对应结点已经染了某一种颜色。

outputFormat: 输出一个整数，为总的染色方案数对$10^9+9$取模后的值。

hint:
子任务$1$：（$44$分）$1\le n\le 10000$ 且 $5\le c\le 10000$；不存在一列有$2$个已染色结点；被染色结点全部位于第一行；第一列和最后一列均有结点已被染色。

子任务$2$：（$32$分）$1\le n\le 10000$ 且 $5\le c\le 10000$；不存在一列有$2$个已染色结点；第一列和最后一列均有结点已被染色。

子任务$3$：（$12$分）$1\le n\le 10000$ 且 $5\le c\le 10000$；第一列和最后一列均有结点已被染色。

子任务$4$：（$8$分）$1\le n\le 10000$ 且 $5\le c\le 10000$。

子任务$5$：（$4$分）$1\le n\le 100000$ 且 $5\le c\le 100000$。


title: [SDOI2019] 世界地图

description:
在遥远的艾莉芬特星球上，有着繁荣的艾莉芬特文明。和地球人一样，艾莉芬特人使用经纬度来标记星球上的每个位置。他们把艾莉芬特星球从北到南划分为$n$个纬度，从西到东划分为$m$个经度。在每条经线和纬线相交的地方都有一个国家，他们用$(i,j)$来表示纬度为$i$，经度为$j$的国家，显然一共有$n\times  m$个国家。

艾莉芬特人在任意两个经度或者纬度相邻的国家之间都修建了一条双向道路。

考虑经度相邻的情况：对于任意一个国家$(i,j)(1\leq i\leq n,1\leq j\leq m)$，它和国家$(i,j+1)$之间都有一条道路，特别地当$j=m$时，$(i,m)$和$(i,1)$之间也有一条道路。

考虑纬度相邻的情况：对于任意一个国家$(i,j)(1\leq i<n,1\leq j\leq m)$，它和国家$(i+1,j)$之间都有一条道路。注意：南北极并不相邻。

艾莉芬特星球并不和平，部分国家卷入了世界大战之中。在接下来$q$个世纪的第$i$个世纪里，经度在$[l_i,r_i]$之间的所有国家都卷入了该世纪发生的世界大战中。当世界大战发生时，被卷入战争的国家都很危险。如果一个国家未被卷入战争，那么它就是一个和平的国家；如果一条道路两端点都是和平的国家，那么它就是一条和平的道路。处于安全考虑，艾莉芬特联合政府会选择只开放一些和平的道路，使得任意两个和平的国家在战争期间都能仅通过这些开放的和平的道路直接或间接连通。

对于任意一条道路，将它保留下来所需的安保代价都不尽相同。请写一个程序，帮助联合政府找到安保代价之和最少的方案。

注意：一个世纪结束后，该世纪的世界大战将会结束，下一场战争的参战国与当前战争的参战国之间没有任何联系。

inputFormat:
第一行包含 $6$ 个正整数 $n,m,SA,SB,SC,lim$，其中$n$表示纬度的范围，$m$ 表示经度的范围。

为了减少输入量，每条道路的安保代价将由以下代码生成，其中 $\texttt{addedge(a,b,c,d,w)}$ 表示$(a,b)$和$(c,d)$之间道路的安保代价为$w$：

```cpp
unsigned int SA, SB, SC;int lim;
int getweight() {
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC^ = t ^ SA;
    return SC % lim + 1;
}
void gen() {
    scanf("%d%d%u%u%u%d", &n, &m, &SA, &SB, &SC, &lim);
    int i, j, w;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++) {
            w = getweight();
            if (j < m) {
                addedge(i, j, i, j + 1, w);
            } else {
                addedge(i, j, i, 1, w);
            }
        }
    for(i = 1; i < n; i++)
        for(j = 1; j <= m; j++) {
            w = getweight();
            addedge(i, j, i + 1, j, w);
        }
}
```

第二行包含一个正整数$q$，表示询问次数。

接下来 $q$ 行，每行 $2$ 个正整数 $l_i,r_i$，依次表示每个询问。

outputFormat: 输出 $q$ 行，每行一个整数，依次回答每个询问，即安保代价之和。


title: [SDOI2019] 热闹的聚会与尴尬的聚会

background: 小 Q 的生日快到了，他决定周末邀请一些朋友到他的新房子一起聚会！

description:
他的联系薄上有 $n$ 位好友，他们两两之间或者互相认识，或者互相不认识。小 Q 希望在周六办一个热闹的聚会，再在周日办一个尴尬的聚会。

- 一场热闹度为 $p$ 的聚会请来了任意多位好友，对于每一位到场的好友来说都有至少 $p$ 位他认识的好友也参加了聚会，且至少对于一位到场的好友来说现场恰好有 $p$ 位他认识的好友；
- 一场尴尬度为 $q$ 的聚会请来了恰好 $q$ 位好友，且他们两两互不认识。

两场聚会可能有重复的参与者，联系薄上也有可能有某些好友同时缺席了两场聚会。

小 Q 喜欢周六聚会的热闹度 $p$ 与周日聚会的尴尬度 $q$ 之间满足：$\left\lfloor \frac{n}{p+1} \right\rfloor\! \le q$ 且 $\left\lfloor \frac{n}{q+1} \right\rfloor\! \le p$。

请帮助小 Q 找出一个可行的邀请方案。

inputFormat:
**输入含有多组测试数据**，并在第一行给定一个整数 $T$，表示总共有多少组测试数据。之后依次给出每一组数据。

每一组测试数据第一行给定两个整数 $n$ 和 $m$，依次表示联系薄中好友的总数，以及有多少对互相认识的好友。

之后 $m$ 行每行给定两个正整数 $u$ 和 $v$，满足 $1\le u\neq v\le n$ ，表示第 $u$ 个好友与第 $v$ 个好友互相认识。

outputFormat:
对于每一组数据输出两行，依次描述周六热闹的聚会的参加人员，与周日尴尬的聚会的参加人员列表：

第一行先输出一个正整数表示总共邀请来了多少位好友参加周六的聚会，再之后输出若干个不同的整数，按照任意顺序描述被邀请的是哪些好友。

第二行先输出一个正整数表示总共邀请来了多少位好友参加周日的聚会，再之后以任意顺序输出若干个不同的整数，同样描述了周日被邀请的好友。

如果有多组方案，你可以输出其中任何一组。


title: [SDOI2019] 移动金币

description:
Alice和Bob将要进行如下的一场游戏。二人轮流操作，且Alice先行。
当轮到一个玩家的时候，他可以选择一枚金币，并将其向左移动任意多格，且至少移动一格。
金币不能被移出棋盘，也不能越过其它金币。

一个 $1\times n$ 的棋盘上最初摆放有 $m$ 枚金币。其中每一枚金币占据了一个独立的格子，任意一个格子内最多只有一枚金币。

如果轮到一个玩家的时候他已经无法做出任何有效操作了（显然这个时候$m$枚金币恰好落在最左侧的$m$个格子中），则被判定为输家。已经知道Alice和Bob都是极致聪明的人，他们在任何局面下总能做出最优的操作。那么有多少初始状态能保证Alice必胜呢？

inputFormat: 输入仅有一行并包含两个正整数，依次为$n$和$m$，如题目所述。

outputFormat: 输出一个整数，表示有多少初始状态可以保证Alice作为先手方能先手必胜。由于答案可能很大，请输出关于$10^9+9$取模后的值。


title: [SDOI2019] 连续子序列

description:
我们定义 $\textbf{T. M.}$ 序列$\{T_n\}$为如下形式得布尔序列：

- $T_0=0$；
- $T_{2n}=T_n$;
- $T_{2n+1}=1-T_n$。

这里我们给出$\textbf{T. M.}$序列得前若干项：$01101001100101101001011001101001\cdots$。

$\textbf{T. M.}$序列是一个无限长度的序列，它有很多连续子序列。
 例如$0$，$1$，$10100$，$10011$和$011001$都是它的连续子序列，然而$111$和$1000$却不是它的连续子序列。

现在给定一个布尔序列（01字符串）$S$和一个非负整数$k$，请统计一下一共有多少种$\textbf{T. M.}$序列的连续子序列$T$满足：

- $S$是$T$的前缀；

- $T$是由$S$额外在右侧添加了恰好$k$项形成的。

inputFormat:
第一行给定一个整数$T$，表示输入一共含有$T$组数据。

之后$T$行，每一行给定一个01字符串$S$（表示一个布尔序列）和一个非负正整数$k$，为给定的一组数据。

outputFormat: 对于每一组数据，输出一行并含有一个整数，表示满足条件的连续子序列个数。因为数值可能很大，请输出关于$10^9+9$取模后的值。

hint:
子任务$1$：（$20$分）$1\le T\le 100$，给定布尔序列长度不超过$100$，且$0\le k\le 100$。

子任务$2$：（$20$分）$1\le T\le 100$，给定布尔序列长度不超过$100$，且$0\le k\le 50000$。

子任务$3$：（$60$分）$1\le T\le 100$，给定布尔序列长度不超过$100$，且$0\le k\le 10^{18}$


title: [NOI Online #1 入门组] 跑步

description:
小 H 是一个热爱运动的孩子，某天他想给自己制定一个跑步计划。小 H 计划跑 $n$ 米，其中第 $i(i \geq 1)$ 分钟要跑 $x_i$ 米（$x_i$ 是正整数），但没有确定好总时长。

由于随着跑步时间增加，小 H 会越来越累，所以小 H 的计划必须满足对于任意 $i(i >1)$ 都满足 $x_i \leq x_{i-1}$。

现在小 H 想知道一共有多少个不同的满足条件的计划，请你帮助他。两个计划不同当且仅当跑步的总时长不同，或者存在一个 $i$，使得两个计划中 $x_i$ 不相同。

由于最后的答案可能很大，你只需要求出答案对 $p$ 取模的结果。

inputFormat: 输入只有一行两个整数，代表总米数 $n$ 和模数 $p$。

outputFormat: 输出一行一个整数，代表答案对 $p$ 取模的结果。


title: [PKUSC2018] 真实排名

description:
小 C 是某知名比赛的组织者，该比赛一共有 $n$ 名选手参加，每个选手的成绩是一个非负整数，定义一个选手的排名是：成绩不小于他的选手的数量（包括他自己）。例如如果 $3$ 位选手的成绩分别是 $[1 , 2 ,2]$ ，那么他们的排名分别是 $[3,2,2]$ 。

拥有上帝视角的你知道所有选手的实力，所以在考试前就精准地估计了每个人的成绩，设你估计的第 $i$ 个选手的成绩为$A_i$，且由于你是上帝视角，所以如果不发生任何意外的话，你估计的成绩就是选手的最终成绩。

但是在比赛当天发生了不可抗的事故（例如遭受到了外星人的攻击），导致有一些选手的成绩变成了最终成绩的两倍，即便是有上帝视角的你也不知道具体是哪些选手的成绩翻倍了，唯一知道的信息是这样的选手恰好有 $k$ 个。

现在你需要计算，经过了不可抗事故后，对于第 $i$ 位选手，有多少种情况满足他的排名没有改变。

由于答案可能过大，所以你只需要输出答案对 $998244353$ 取模的值即可。

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

第二行 $n$ 个非负整数 $A_1, A _ 2, \cdots, A_n$。

outputFormat: 输出 $n$ 行，第 $i$ 行一个非负整数 $ans_i$，表示经过不可抗事故后，第 $i$ 位选手的排名没有发生改变的情况数。

hint:
- 对于 $10\%$ 的数据，有 $1\leq n\leq 15$；
- 对于 $35\%$ 的数据，有 $1\leq n\leq 10^3$；
- 另有 $10\%$ 的数据，满足每个人的成绩都互不相同；
- 另有 $10\%$ 的数据，满足 $0\leq A_i\leq 10^5$；
- 另有 $10\%$ 的数据，满足 $k=85$，$0\leq A_i\leq 600$；
- 对于$100\%$的数据，有$1\leq k < n\leq 10^5$，$0\leq A_i\leq 10^9$。


title: [PKUSC2018] 最大前缀和

description:
小 C 是一个算法竞赛爱好者，有一天小 C 遇到了一个非常难的问题：求一个序列的最大子段和。

但是小 C 并不会做这个题，于是小 C 决定把序列随机打乱，然后取序列的最大前缀和作为答案。

小 C 是一个非常有自知之明的人，他知道自己的算法完全不对，所以并不关心正确率，他只关心求出的解的期望值，现在请你帮他解决这个问题，由于答案可能非常复杂，所以你只需要输出答案乘上 $n!$ 后对 $998244353$ 取模的值，显然这是个整数。

注：最大前缀和的定义：$\forall i \in [1,n]$，$\sum_{j=1}^{i}a_j$的最大值。

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

第二行 $n$ 个数，表示原序列 $a[1..n]$，第 $i$ 个数表示 $a[i]$ 。

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

hint:
对于$10\%$的数据，有$1\leq n\leq 9$。

对于$40\%$的数据，有$1\leq n\leq 15$。

另有$10\%$的数据，满足$a$中最多只有一个负数。

另有$10\%$的数据，满足$|a[i]|\leq 2$。

对于$100\%$的数据，满足$1\leq n\leq 20$，$\sum_{i=1}^{n}|a[i]|\leq 10^9$。


title: [PKUSC2018] 主斗地

description:
如果你参加过 NOIP 2015 和 PKUWC 2018，那么你一定对一道叫做斗地主的题印象深刻。为了致敬经典，我们又出了一道有关打牌的题。在本题中，牌型和斗地主**类似但不完全相同**，我们称本题中的扑克游戏为主斗地。

主斗地是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏，其中大小王各一张，其他数码牌各四张。在斗地主中，牌的大小关系根据牌的数码表示如下：$3<4<5<6<7<8<9<10(T)<J<Q<K<A<2< $小王 $(w)$ $<$ 大王 $(W)$，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由 $n$ 张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。为了简化题目，本题不考虑花色的影响，即**所有的相同的数码的牌都是被视为一样的**。

在这道题中，允许的出牌牌型有（**这一部分与传统的斗地主有所出入，请注意**）：

|   名称    |           解释           |      举例       |     注     |
| :-----: | :--------------------: | :-----------: | :-------: |
|   单牌    |         单独的一张牌         |       6       | 单张的王也是单牌  |
|   对子    |        相同数码的两张牌        |      66       |  大小王不是对子  |
|   三张牌   |        相同数码的三张牌        |      666      |           |
|   三带一   |     相同数码的三张牌带上一张单牌     |     666w      |           |
|   三带二   |  相同数码的三张牌带上一个另外数码的对子   |     66699     |           |
|   顺子    |    大小连续的 $5$ 张及以上单牌    |    3456789    | 不能含有大小王和2 |
|   连对    |   大小连续的 $3$ 对及以上的对子    |   33445566    | 不能含有大小王和2 |
|   三顺    |     大小连续的两组及以上的三张牌     |   333444555   | 不能含有大小王和2 |
|   四带二   |     四张相同数码的牌带上两张单牌     | 444456 444455 | 注意不能带两个对子 |
| 飞机（单翅膀） | 三顺带上相同数量的**数码两两不同的**单牌 | 33344455569J  |           |
| 飞机（双翅膀） | 三顺带上相同数量的**数码两两不同的**对子 |  3334446699   |           |

**注意**：

1. 在牌型中没有连炸这种牌型，但是形如 444455556666 的牌仍然是能出的，它将被视为 444555666 带 456 的飞机（单翅膀）牌型。
2. 大王和小王数码不同，即飞机带大小王是合法的，例如 333444wW
3. 容易验证，上述牌型的规则是合法的，即对于任意合法的牌，它都有唯一的牌型。
4. 在牌型中，没有炸弹。**炸弹将被视为三带一，且没有炸弹的效果**，即它不能压任何牌型。
5. 在牌型中，没有火箭。这意味着 wW 不再是一个合法的牌型。

两手牌是属于相同牌型的当且仅当他们的名称相同且包含牌的数量相同。相同牌型的牌之间存在着大小关系：

1. 三带一三带二的大小取决于那三张相同牌的数码
2. 飞机的大小取决于三顺的大小
3. 四带二的大小取决于四张相同牌的大小
4. 其他牌型的大小取决于牌中的最大的一张牌

下面是对主斗地的游戏过程的描述：

1. 在主斗地中，有两个玩家，他们是同一个阵营的，两个玩家要一同达成游戏目标。为了方便，我们假设第一个玩家是九条可怜，第二个玩家是××网友。
2. 游戏只会使用一副完整的扑克牌。在游戏开始的时候，**会先把所有的 $3$ 扔掉**。之后双方各从这一副牌中随机抽取 $17$ 张，余下的 $16$张被丢弃。你可以认为是随机洗牌后，九条可怜取前 $17$ 张，××网友后 $17$ 张，剩下的 $16$ 张被掉了。
3. 游戏分成若干轮，每一轮分为两步：
   1. 第一步，九条可怜从当前手牌中选择一个任意牌型任意大小的牌 $C$ 并打出。
   2. 第二步，××网友从当前手牌中选择一个和 $C$ 牌型相同且大小 **严格更大** 的牌 $C'$ 打出。如果不存在这样的牌则游戏失败。
4. 在某一轮结束后，如果九条可怜和××网友中有至少一个人没有手牌，则游戏结束。如果两个人都没有手牌，则游戏胜利，否则游戏失败。

下面是一个例子：

假设九条可怜的牌是 44445556789TJQKwW，××网友的牌是 666789TJQKAAAA222。那么一个可以获胜的方案是：

1. 第一轮九条可怜出 4444wW，××网友出 AAAA22。
2. 第二轮九条可怜出 6789TJQ，××网友出 789TJQK。
3. 第三轮九条可怜出 555K，××网友出 6662。

这个游戏很考验两个玩家之间的默契。但是因为九条可怜和××网友无法相互理解，于是他们打算以明牌的方式进行游戏，即双方都知道对方的牌。因为两个人都会按照最优策略行动，所以在牌下发的时候，游戏的胜负就已经确定了。

现在给出××网友的牌，你需要计算九条可怜有多少种不同的可能的手牌可以获得胜利。

注意：××网友和九条可怜的牌都来自于同一副扑克，且分牌的时候没有 $3$。

inputFormat: 每组数据输入一行，一个长度为 $17$ 的字符串表示××网友的牌。我们用 456789TJQKA2wW 来表示每一种牌。

outputFormat:
对每组数据，输出一个整数表示答案，满足条件的九条可怜的牌数。答案可能很大，请对 $998244353$ 取模输出。

**注意**，在这题中我们不考虑花色，如果两种手牌的数码组成完全相同，但是花色不同，他们也是会被视为同一种的。

hint:
因为种种原因，本题采用捆绑测试，一共有 $3$ 个 subtask:

| 子问题编号 |  分值  |       约定       |
| :---: | :--: | :------------: |
|   1   | $30$ | 每一种牌最多出现 $2$ 次 |
|   2   | $30$ | 每一种牌最多出现 $3$ 次 |
|   3   | $40$ | 每一种牌最多出现 $4$ 次 |

时间限制：2s

空间限制：512M


title: EntropyIncreaser 与 动态图

background:
话说 NaCly_Fish 在和  $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 吃饭时，问过她一个问题：“一个无向图，支持动态加边，求两点间割点数，怎么做？”

$\mathsf E \color{red} \mathsf{ntropyIncreaser}$ 想了几秒，说：“这不是sb题吗，随便怎么做都行吧。”然后三两句道出了一个算法。

而 NaCly_Fish 还是不会，请你来教教她这题怎么做吧。

description:
有一个 $n$ 个点的图，初始没有边。
有 $q$ 个操作，分为 $3$ 种，具体如下：

- `1 u v` 表示在 $u,v$ 之间连一条无向边
- `2 u v` 表示求 $u,v$ 间的割边数量
- `3 u v` 表示求 $u,v$ 间的割点数量

特别地，对于 $2$、$3$ 操作，若 $u,v$ 不连通，则输出 $-1$
****
为了防止有歧义，这里给出对两点间割边和割点数量的定义：
对于所有包含 $u,v$ 的路径的节点集合之交 $S$ ，定义 $S$ 中的元素数量为 $u,v$ 间的割点数。
对于所有包含 $u,v$ 的路径的边集合之交 $T$ ，定义 $T$ 中的元素数量为 $u,v$ 间的割边数。
****
**本题强制在线。**
从第二行开始，每次的输入的 $u,v$ 都需要异或上 $\text{last}$ ，才是实际操作的 $u,v$。
 $\text{last}$ 为最近一次**答案非 $-1$ 的**询问的答案，定义初始 $\text{last}=0$
ps：如果您不知道异或是什么意思，可以看这里：[xor](https://www.baidu.com/link?url=bhG_De1gZYsqrIq7dkhgGj8vP87xSSyoIwk0-5p1fyKmf58cznvq0oYJg0XGoyKNpuGk7EsvjUnyvgJ19_ZA3PhoMJ3hIufHZ5GXh1OaIoS&wd=&eqid=ab26bc160004324d000000035d1ed64e)

inputFormat:
第一行两个正整数 $n,q$，表示节点数和操作次数。
接下来 $q$ 行，每行三个整数，表示一次操作。

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


title: 【模板】康托展开

description: 求 $1\sim N$ 的一个给定全排列在所有 $1\sim N$ 全排列中的排名。结果对 $998244353$ 取模。

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

第二行 $N$ 个正整数，表示 $1\sim N$ 的一种全排列。

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


title: [SNOI2017] 礼物

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

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

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

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

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

已知 $N,K$，请输出第 $N$ 个朋友送的礼物个数对 $10^9+7$ 取模的结果。

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

outputFormat: 一个整数，表示第 $N$ 个朋友送的礼物个数对 $10^9+7$ 取模的结果。


title: [SNOI2017] 英雄联盟

description:
正在上大学的小皮球热爱英雄联盟这款游戏，而且打的很菜，被网友们戏称为「小学生」。

现在，小皮球终于受不了网友们的嘲讽，决定变强了，他变强的方法就是：买皮肤！

小皮球只会玩  $\text{N}$ 个英雄，因此，他也只准备给这 $\text{N}$ 个英雄买皮肤，并且决定，以后只玩有皮肤的英雄。

这 $\text{N}$ 个英雄中，第 $\text{i}$ 个英雄有 $K_i$ 款皮肤，价格是每款 $C_i$ Q 币（同一个英雄的皮肤价格相同）。

为了让自己看起来高大上一些，小皮球决定给同学们展示一下自己的皮肤，展示的思路是这样的：对于有皮肤的每一个英雄，随便选一个皮肤给同学看。

比如，小皮球共有 5 个英雄，这 5 个英雄分别有 $\text{0,0,3,2,4}$ 款皮肤，那么，小皮球就有 $3 \times 2 \times 4 = 24$ 种展示的策略。

现在，小皮球希望自己的展示策略能够至少达到  $\text{M}$ 种，请问，小皮球至少要花多少钱呢？

inputFormat:
第一行，两个整数 $\text{N,M}$。

第二行，$\text{N}$ 个整数，表示每个英雄的皮肤数量 $K_i$。

第三行，$\text{N}$ 个整数，表示每个英雄皮肤的价格 $C_i$。

outputFormat: 一个整数，表示小皮球达到目标最少的花费。

hint:
**样例解释**

每一个英雄都只有4款皮肤，每款皮肤2 Q币，那么每个英雄买3款皮肤，$3 \times 3 \times 3 \ge 24$，共花费 $6 \times 3$ Q币。

**数据范围**

共 10 组数据，第 $\text{i}$ 组数据满足：$\text{N} \le \max(5, \log_2^4i)$

$\text{100}\%$ 的数据：$\text{M} \le 10^{17}, 1 \le K_i \le 10, 1 \le C_i \le 199$。保证有解。


title: [SNOI2017] 遗失的答案

description:
小皮球在计算出答案之后，买了一堆皮肤，他心里很开心，但是一不小心，就忘记自己买了哪些皮肤了。= =|||

万幸的是，他还记得他把所有皮肤按照 $1 \sim \text{N}$ 来编号，他买来的那些皮肤的编号（他至少买了一款皮肤），最大公约数是 $\text{G}$，最小公倍数是 $\text{L}$。

现在，有 $\text{Q}$ 组询问，每组询问输入一个数字 $\text{X}$，请你告诉小皮球，有多少种合法的购买方案中，购买了皮肤 $\text{X}$？

因为答案太大了，所以你只需要输出答案 $\bmod{10^9+7}$ 即可。

inputFormat:
第一行，三个数字 $\text{N, G, L}$，如题意所示。

第二行，一个数字 $\text{Q}$，表示询问个数。

第三行， $\text{Q}$ 个数字，表示每个询问所问的 $\text{X}$。

outputFormat: 对于每一组询问，在一行中单独输出一个整数，表示这个询问的答案。


title: 【模板】扩展 KMP/exKMP（Z 函数）

description:
给定两个字符串 $a,b$，你要求出两个数组：

- $b$ 的 $z$ 函数数组 $z$，即 $b$ 与 $b$ 的每一个后缀的 LCP 长度。
- $b$ 与 $a$ 的每一个后缀的 LCP 长度数组 $p$。

对于一个长度为 $n$ 的数组 $a$，设其权值为 $\operatorname{xor}_{i=1}^n i \times (a_i + 1)$。

inputFormat: 两行两个字符串 $a,b$。

outputFormat:
第一行一个整数，表示 $z$ 的权值。

第二行一个整数，表示 $p$ 的权值。


title: 【模板】多项式复合函数

background:
有一天，NaCly_Fish看见 $\mathsf r \color{red} \mathsf{qy}$ 在群里说：“终于把多项式复合写完啦！qwq”
她便好奇地去问 $\mathsf r \color{red} \mathsf{qy}$：“这个东西怎么写啊？”

$\mathsf r \color{red} \mathsf{qy}$ 只丢给了她一份嘤文的 pdf，然而她根本看不懂。
于是她求助于你，希望你能帮她解决这个难题。

description:
给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$，你需要求一个 $n$ 次多项式 $H(x)$ ，满足条件：
$$H(x) \equiv F(G(x))\space (\text{mod }x^{n+1})$$
换种说法，你要求的多项式应满足：
$$H(x) \equiv \sum\limits_{i=0}^n [x^i]F(x)\times G(x)^i \space (\text{mod }x^{n+1})$$
将结果的各项系数对 $998244353$ 取模。

inputFormat:
第一行两个正整数 $n,m$ ，分别表示 $F(x)$ 和 $G(x)$ 的次数
第二行 $n+1$ 个非负整数 $f_i$，表示 $F(x)$ 的 $i$ 次项系数
第三行 $m+1$ 个非负整数 $g_i$，表示 $G(x)$ 的 $i$ 次项系数

outputFormat: 输出一行 $n+1$ 个非负整数，从低到高表示 $H(x)$ 的系数


title: [SNOI2019] 纸牌

description:
有一副纸牌。牌一共有 $n$ 种，分别标有 $1,2,...,n$ ，每种有 $C$ 张。故这副牌总共有 $nC$ 张。

三张连号的牌 $(i,i+1,i+2)$ 或三张相同的牌 $(i,i,i)$ 可以组成一**叠**。如果一组牌可以分成若干（包括零）**叠**，就称其为一组**王牌**。

你从牌堆中摸了一些初始牌。现在你想挑出一些牌组成一组王牌，请问有多少种可能组成的王牌呢？答案对 $998244353$ 取模。

两组牌相同当且仅当它们含有的每一种牌数量都相同。

inputFormat:
第 $1$ 行两个整数 $n,C$ 表示牌的种类数和每种的张数；

第 $2$ 行一个整数 $X$ 表示初始牌的种类数；

接下来 $X$ 行每行两个整数 $k_i,a_i$ ，表示初始牌中有 $a_i$ 张 $k_i$ 号牌。每行的 $k_i$ 依次递增。


title: [SNOI2019] 积木

description:
有一块 $n$ 行 $m$ 列的网格板， $n,m$ 都是奇数。网格上平铺着一些 $1\times 2$ 的积木。积木可以旋转，不能重叠。这些积木共有 $\frac{nm-1}{2}$ 块，也就是说，网格板上只有一格的空位。

你可以做两种操作：

1. 将一块与空白格相邻（指有公共边）的积木旋转 $90^\circ$ 到空白格中；
2. 将一块与空白格积木相邻的积木平移至空白格中。

如图所示（被移动的积木颜色较浅）：

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

请你用以上两种操作将给定的网格板变换为指定的状态。

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

接下来 $n$ 行，每行 $m$ 个字符，描述网格板的初始状态：

- `<`表示这个格子是一块积木的左半部分；
- `>`表示这个格子是一块积木的右半部分；
- `n`表示这个格子是一块积木的上半部分；
- `u`表示这个格子是一块积木的下半部分；
- `o`表示这个格子是空的。

接下来另外 $n$ 行，每行 $m$ 个字符，描述你需要将网格板变成的目标状态，格式同上。

outputFormat:
你需要输出一个字符串，按顺序表示你的操作：

- `L`表示你移动了空白格左侧的积木；
- `R`表示你移动了空白格右侧的积木；
- `U`表示你移动了空白格上方的积木；
- `D`表示你移动了空白格下方的积木。

当然，没有操作的话输出空串就好了。

hint:
#### 数据范围与说明

你输出的操作序列长度不能超过 $8\times 10^6$ 。

对于所有数据， $1\leq n,m\leq 2000$ 。

- 对于 $10\%$ 的数据， $n,m\leq 3$ ；
- 对于另外 $10\%$ 的数据， $n,m\leq 5$ ；
- 对于另外 $20\%$ 的数据， $m=3$ ；
- 对于另外 $20\%$ 的数据， $n,m\leq 50$ ；
- 对于另外 $20\%$ 的数据， $n,m\leq 200$ ；
- 对于余下 $20\%$ 的数据，无特殊限制。

#### SPJ 说明

参考 https://www.luogu.org/discuss/show/114298 ，感谢 @M_sea 的贡献。


title: [THUPC2019] 不用找的树

description:
给出一棵 $n$ 个节点的树，结点标号从 $1$ 到 $n$ 。

定义树上两点 $a,b$ 的距离 $d(a,b)$ 是最小的非负整数 $k$ ，满足存在结点序列 $v_0,v_1,...,v_k$ ，满足 $v_0=a,v_k=b$ ，且对于 $0\leq i\leq k-1$ 有 $v_i$ 和 $v_{i+1}$ 之间在树上有一条边相连。

有 $m$ 个询问，每个询问包含参数 $p_0,d_0,p_1,d_1$ ，求：

$$\sum\limits_{d(p_0,a)\leq d_0}\sum\limits_{d(p_1,b)\leq d_1}d(a,b)$$

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

接下来一行 $n-1$ 个整数 $f_2,f_3,...,f_n$ ，依次表示 $i$ 和 $f_i$ （ $1\leq f_i\leq i-1$ ）之间有一条边。

接下来一行一个整数 $m$ ，表示询问数目。

接下来 $m$ 行依次描述所有询问：每行四个证书 $p_0,d_0,p_1,d_1$ （ $1\leq p_0,p_1\leq n,0\leq d_0,d_1\leq n-1$ ）描述一组询问。

保证 $1\leq n\leq 10^5,1\leq m\leq 10^5$ 。

outputFormat: 共 $m$ 行，依次回答各组询问：每行输出一行一个整数表示这组询问的答案。

hint:
##### 版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

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


title: [THUPC2019] 组合数据结构问题

description:
> 众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。

小葱同学在学习了组合数的计算之后，开始了研究数据结构的道路。通过十五分钟的刻苦学习，小葱同学初步掌握了队列、栈和堆这三种数据结构。小葱同学发现这三种数据结构都支持两种操作：

1. 将某个数插入该数据结构。
2. 从该数据结构中按照数据结构的原理取出一个数。

小葱同学为了检验自己对这三种数据结构的理解，设计了一个类似的黑箱模型。该模型也支持两种操作，向黑箱中输入一个数或者从黑箱中输出一个数。现在小葱对该黑箱做了若干次操作，并给出每次输入和输出的数，问这个黑箱实现的是否可能是队列、栈、大根堆或者小根堆。

虽然小葱同学对这四种数据结构了如指掌，但他还是决定告诉你它们的分别是什么：

- 如果黑箱是**队列**：黑箱初始为空，输入时数将被放入黑箱，输出时当前黑箱内**最早被放入的**数将被输出并移出黑箱。
- 如果黑箱是**栈**：黑箱初始为空，输入时数将被放入黑箱，输出时当前黑箱内**最晚被放入的**数将被输出并移出黑箱。
- 如果黑箱是**大根堆**：黑箱初始为空，输入时数将被放入黑箱，输出时当前黑箱内**值最大的**数将被输出并移出黑箱。特别地，如值最大的数有多个，则仅将其中一个移出黑箱。
- 如果黑箱是**小根堆**：黑箱初始为空，输入时数将被放入黑箱，输出时当前黑箱内**值最小的**数将被输出并移出黑箱。特别地，如值最小的数有多个，则仅将其中一个移出黑箱。

inputFormat:
第一行一个整数 $N$  代表操作的个数。

接下来 $N$ 行每行两个整数 $\mathrm{opt},v$ 。如果 $\mathrm{opt}=1$ ，代表这次操作小葱同学向黑箱中插入 $v$ 了这个数；如果 $\mathrm{opt=2}$ ，代表小葱这次操作从黑箱中取出了 $v$ 这个数。

保证 $0\leq N\leq 10^5$ ，$-2^{31}\leq v<2^{31}$ ，$\mathrm{opt}\in\{1,2\}$  。

注意输入的数据仅保证在格式和范围上完全正确，不保证任何其他条件。

outputFormat: 共四行，每行可能是 `Yes` 或者 `No`，分别依次代表该黑箱是否可能是队列、栈、大根堆或者小根堆。


title: [THUPC2019] 过河卒二

description:
> 首先我们回忆一下经典难题过河卒问题：
>
> 棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向上、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点，因此称之为「马拦过河卒」。
>
> 棋盘用坐标表示，$A$ 点 $(1,1)$ 、$B$ 点 $(N,M)$ ，同样马的位置坐标是需要给出的。
>
> 现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
>
> **请注意，上述背景内容与本题无关！**

Kiana 喜欢玩象棋，尤其是喜欢用象棋玩过河卒的游戏。在传统的过河卒问题中，Kiana 需要控制一个卒从起点走到终点，在路中避开一个对方的马的攻击，然后假装不会算并询问你从起点到终点的路径总数。

在今天的过河卒二游戏中，Kiana 还是控制一个卒在一个 $N\times M$ 的棋盘上移动，初始时卒位于左下方坐标为 $(1,1)$ 位置，但为了增加难度，Kiana 对游戏规则做出了一些修改。传统的过河卒每步只能向上或向右移动 $1$ 格，Kiana 规定自己的过河卒二还可以在一步中向右上方移动 $1$ 格，即如果当前卒位于坐标 $(x,y)$ 处，则下一步可以走到 $(x+1,y)$ 、$(x,y+1)$ 或 $(x+1,y+1)$ 中的任意一格里面去，同时 Kiana 认为，如果两种移动方案在某一步时卒移动的方向（右、上或右上）不同，则两种方案就是不同的，例如从 $(1,1)$ 先走到 $(1,2)$ 再走到 $(2,2)$ 、从 $(1,1)$ 先走到 $(2,1)$ 再走到 $(2,2)$ 和从 $(1,1)$ 直接走到 $(2,2)$ 是三种不同的移动方案。

其次，过河卒二的终点不再是一个特定的位置，Kiana 规定卒可以从棋盘的上方或右方走出棋盘，此时就视为游戏成功。注意在走出棋盘时仍然有方向选择的不同，例如若过河卒位于 $(1,M)$ 处，则下一步它可以向右或者向右上用两种方式走出棋盘，若过河卒位于 $(N,M)$ 处，则下一步它可以向上、向右或者向右上用三种方式走出棋盘，以不同的方式走出棋盘仍然被算作是不同的移动方案。

此外，对方马的攻击范围不再是有规律的几个位置，而是 Kiana 规定好的 $K$ 个特定坐标，并要求过河卒在移动的过程中不能走到这 $K$ 个坐标的任何一个上，在除这些坐标以外的位置上过河卒都可以按规则自由移动。

现在 Kiana 想知道，过河卒二有多少种不同的移动方案可以走出棋盘，这个答案可能非常大，她只想知道方案数对 $59393$ 取模后的结果。由于她不会算，所以希望由你来告诉她。

inputFormat:
第一行包含三个整数 $N$ 、$M$ 和 $K$ ，分别表示棋盘的坐标范围与对方马的攻击格子数（即 Kiana 规定的不能经过的坐标数）。

接下来 $K$ 行，第 $i$ 行包含两个正整数 $X_i$ 和 $Y_i$ ，表示对方马的第 $i$ 个攻击坐标为 $(X_i,Y_i)$ 。

对于所有数据，保证 $1\leq N\leq 10^9,1\leq M\leq 10^5,0\leq K\leq 20,1\leq X_i\leq N,1\leq Y_i\leq M$，$(1,1)$ 一定不会被对方马攻击，且被攻击的格子中不存在两个坐标相同的格子。

outputFormat: 输出一行一个整数，表示过河卒走出棋盘的方案数对 $59393$ 取模后的结果。

hint:
### 样例解释

用 $\uparrow$ 表示过河卒向上移动了一格，用 $\rightarrow$ 表示过河卒向右移动了一格，用 $\nearrow$ 表示过河卒向右上移动了一格，由此可以简化样例解释的表述。

$24$ 种移动方案如下：

$(\uparrow\uparrow\uparrow)$、$(\uparrow\uparrow\nearrow)$、$(\uparrow\uparrow\rightarrow\uparrow)$、$(\uparrow\uparrow\rightarrow\nearrow)$、

$(\uparrow\uparrow\rightarrow\rightarrow\uparrow)$、$(\uparrow\uparrow\rightarrow\rightarrow\nearrow)$、$(\uparrow\uparrow\rightarrow\rightarrow\rightarrow)$、$(\uparrow\nearrow\uparrow)$、

$(\uparrow\nearrow\nearrow)$、$(\uparrow\nearrow\rightarrow\uparrow)$、$(\uparrow\nearrow\rightarrow\nearrow)$、$(\uparrow\nearrow\rightarrow\rightarrow)$、

$(\rightarrow\rightarrow\rightarrow)$、$(\rightarrow\rightarrow\nearrow)$、$(\rightarrow\rightarrow\uparrow\rightarrow)$、$(\rightarrow\rightarrow\uparrow\nearrow)$、

$(\rightarrow\rightarrow\uparrow\uparrow\rightarrow)$、$(\rightarrow\rightarrow\uparrow\uparrow\nearrow)$、$(\rightarrow\rightarrow\uparrow\uparrow\uparrow)$、$(\rightarrow\nearrow\rightarrow)$、

$(\rightarrow\nearrow\nearrow)$、$(\rightarrow\nearrow\uparrow\rightarrow)$、$(\rightarrow\nearrow\uparrow\nearrow)$、$(\rightarrow\nearrow\uparrow\uparrow)$。

### 版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

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


title: [THUPC2019] 鸽鸽的分割

description:
牛牛有一块蛋糕，他想把蛋糕分给小朋友们。蛋糕一开始是圆形的，牛牛会在圆周上选择 $n$ 个不重合的点，将这几个点两两用线段连接。这些线段将会把蛋糕分成若干块。

现在，牛牛想知道，蛋糕**最多**会被分成多少块，请你告诉他答案。

inputFormat: 输入包含至多 $20$ 行，每行一个整数 $n$，含义见「题目描述」。保证 $0\le n \le 64$。

outputFormat: 依次回答牛牛的每个问题，对于每个问题，输出一行，包含一个整数表示答案。

hint:
### 样例解释

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

##### 版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

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


title: [THUPC2019] 能量波

description:
> 有两个超级英雄在宇宙中战斗。英雄 A 为了击败对手英雄 B，使出了他的绝招，发出了一记能量光波。
>
> 英雄 B 有一些体力值，如果英雄 A 的能量光波对英雄 B 的伤害足够大，英雄 B 就会被击倒。否则英雄 A 就会因为耗尽能量而被英雄 B 抓住破绽，从而反而被英雄 B 击倒。所以英雄 A 迫切想知道自己的能量光波到底能够对英雄 B 造成多少伤害。

为了简化问题，英雄 B 可以被描述为空间中的多个凸多面体拼成的物体。这些凸多面体可能有重合的部分，重合部分作为英雄 B 的身体只会被计算一次。

英雄 A 发出的能量光波也可以被描述为空间中的另外一个凸多面体，这个光波在空间中每秒均匀移动一个向量 $\vec{v} = (v_x,v_y,v_z)$。能量光波可以穿过任何物体，并且在穿越的过程中对对方造成伤害。

在时刻 $t$, 假设英雄 A 的能量光波和英雄 B 的身体的交的体积为 $f(t) = V$，那么在这一瞬间，能量光波造成的瞬时伤害速率就恰好是 $V$。而所有时刻的总计伤害就可以被表示为

$$\int_{0}^{\infty} f(t) \mathrm{d}t$$

英雄 A 想要知道自己的能量光波对英雄 B 的身体造成了多大的总计伤害。

inputFormat:
第 $1$ 行一个正整数 $m_B$，表示英雄 B 的身体有多少个凸多面体组成。

接下来有 $m_B$ 个输入块，每块表示英雄 B 的身体的一个组成部分。

每个输入块开头第一行为一个正整数 $n$，表示这个凸多面体的顶点的个数，

接下来 $n$ 行每行一个三元组，其中第 $i$ 个 $(x_i,y_i,z_i)$ 表示第 $i$ 个点的坐标。

接下来一行一个正整数 $n_A$，表示英雄 A 的能量光波的对应凸多面体的顶点数，

接下来 $n_A$ 行每行一个三元组，其中第 $i$ 个 $(x_i,y_i,z_i)$ 表示第 $i$ 个点的坐标。

再接下来一行一个三元组 $(v_x,v_y,v_z)$，表示英雄 A 的能量光波的移动速度。

我们保证 $1 \le m_B \le 4,4\le n,n_A\le 8$ ，所有输入的点的坐标都是 $[-100,100]$ 内的整数。并且所有速度向量的分量都是 $[-10,10]$ 内的实数。所有凸多面体都是不退化的 （意思是这个凸多面体的体积非 $0$）。

输入中可能会出现四点共面或者三点共线的情况。

我们保证在第 $0$ 秒能量光波和英雄 B 是不相交的。并且在第 $10^4$ 秒之后交集的体积一直是 $0$。

outputFormat:
一行输出一个实数，表示总计伤害的值。

输出与标准答案的绝对误差或相对误差小于 $10^{-6}$ 就会被算作正确。


title: [THUPC2019] 令人难以忘记的题目名称

description:
现在有一个长度为 $N$ 的整数序列 $S$（下标从 $0$ 开始），Alice 和 Bob 在这个序列上博弈。

游戏按轮进行，每一轮中：

* Alice 给出一个长度为 $N$ 的正整数序列 $T$
* Bob 看到 Alice 给出的 $T$，然后选择 $[0, N-1]$ 里的一个整数 $x$
* 之后我们把 $S$ 转化为 $S'$，规则如下：

$${S'}_{i} = S_{i} + T_{(i+x)\bmod N}$$

* 以 $S'$ 作为新的 $S$，结束这一轮。

如果某一轮结束后，$S$ 中每个数都是一个给定质数 $P$ 的倍数，那么 Alice 胜利。

给定 $N$ 和初始序列 $S$，请问：Alice 是否能在有限步必胜，如果答案为是，最快可以在几轮内保证胜利。

inputFormat:
第一行两个非负整数 $N,P$，保证 $P$ 是一个质数。

接下来一行 $N$ 个空格隔开的整数，描述初始序列 $S$（$0\le S_i \le 10^9$）。

保证 $N\le 3\times 10^5$，$P\le 200$。

outputFormat: 输出一个整数，如果 Alice 不能在有限步必胜，输出 $-1$，否则输出一个整数 $x$ 表示 Alice 最快能在几轮内胜利。

hint:
### 样例解释

一种可能的游戏情形是：

* 第一轮 $T=[1, 0, 1, 0]$，$x=0$，转化后的  $S'=[1,1,1,1]$。
* 第二轮 $T=[1,1,1,1]$，无论 $x$ 取什么，转化后的 $S'=[2,2,2,2]$。

可以证明 $2$ 轮是最优的。

##### 版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

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


title: [THUPC2019] 鸭棋

description:
#### 题目背景

鸭棋是一种风靡鸭子界的棋类游戏。事实上，它与中国象棋有一些相似之处，但规则不尽相同。在这里，我们将为你介绍鸭棋的规则。

**同时，我们下发了一个模拟鸭棋规则的玩具，你可以结合这个玩具理解题目**（也可以在 AK 后与你的队友进行对弈）。详情请见「玩具使用说明」。

鸭棋在一个 $10\times 9$（$10$ 行 $9$ 列）的网格棋盘上进行，网格上的每个格点都可以有棋子停留。对弈双方一方执红（`red`）棋、另一方执蓝（`blue`）棋，双方轮流执行操作，轮到一位玩家操作时，他必须选择一枚自己的棋子，并按照规则进行一步移动。

鸭棋发明者鸭子德规定一局鸭棋由红方执先手，并设计了初始棋盘布局如下：

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

##### 棋子类型与走子规则

棋子分为 $7$ 类，下面介绍了它们的名字以及它们的移动规则。介绍移动规则时，我们默认棋子所处位置为 $\left( x,y\right)$（表示第 $x$ 行的第 $y$ 列，下同），并列出它可以到达的位置：

* **王**（`captain`)：可达的位置共 $4$ 个，包括 $\left(x\pm 1,y\right)$ 及 $\left(x,y\pm 1\right)$。
* **士**（`guard`）：可达的位置共 $4$ 个，包括 $\left(x\pm 1,y\pm 1\right)$ 及 $\left(x\pm 1,y\mp 1\right)$。
* **象**（`elephant`）：可达的位置至多 $4$ 个，对于任意 $s_x,s_y\in \left\{ 1,-1\right\}$，分别有：
    * 如果位置 $\left(x+s_x\times 1 ,y+ s_y\times 1\right)$ 上**无任意一方**的棋子停留，则 $\left( x+s_x \times 2,y+s_y \times 2\right)$ 为一个可达的位置。
* **马**（`horse`）：可达的位置至多 $8$ 个，对于任意 $s_x,s_y\in \left\{ 1,-1\right\}$，分别有：
    * 如果位置 $\left(x+s_x\times 1 ,y\right)$ 上**无任意一方**的棋子停留，则 $\left( x+s_x \times 2,y+s_y \times 1\right)$ 为一个可达的位置。
    * 如果位置 $\left(x ,y+ s_y \times 1 \right)$ 上**无任意一方**的棋子停留，则 $\left( x+s_x \times 1,y+s_y \times 2\right)$ 为一个可达的位置。
* **车**（`car`）：可在**不跨越其他棋子**的前提下，到达同行或同列的所有其他位置。
* **鸭**（`duck`）：可达的位置至多 $8$ 个，对于任意 $s_x,s_y\in \left\{ 1,-1\right\}$，分别有：
    * 如果位置 $\left(x+s_x\times 2 ,y+s_y \times 1\right),\left(x+s_x\times 1 ,y\right)$ 上均**无任意一方**的棋子停留，则 $\left( x+s_x \times 3,y+s_y \times 2\right)$ 为一个可达的位置。
    * 如果位置 $\left(x+s_x \times 1 ,y+ s_y \times 2 \right),\left(x ,y+ s_y \times 1 \right)$ 上均**无任意一方**的棋子停留，则 $\left( x+s_x \times 2,y+s_y \times 3\right)$ 为一个可达的位置。
* **兵**（`soldier`）：可达的位置共 $8$ 个，包括 $\left(x\pm 1,y\right)$ 及 $\left(x,y\pm 1\right)$ 及 $\left(x\pm 1,y\pm 1\right)$ 及 $\left(x\pm 1,y\mp 1\right)$。

**除上面描述的规则之外，棋子移动还有如下额外规则：**

* 不能将棋子移动到棋盘外的某个位置。
* 玩家不能将棋子移动到**已经停留了己方棋子**的位置。
* 如果玩家将棋子移动到了一个**已经停留了对方棋子**的位置，那么原本停留在该位置上的这个**对方棋子**将被移出游戏。

##### 胜利条件与将军局面

玩家在这个游戏中的目标是将对方的**王**移出游戏。一旦一方的**王**被移出游戏，则另一方立即宣告胜利。

对于一个棋盘的状态，如果存在一方有一步合法的操作能够将另一方的**王**移出游戏，则我们说当前局面是一个**将军**的局面。需要友情提示的是，根据定义，将军局面的形成包括（但不限于）如下这些可能：

1. 一方将一枚棋子移动到可以攻击对方**王**的位置

2. 在己方**王**受到威胁时不采取措施躲避

3. 主动将**王**移动至会受到攻击的位置

**除此之外，需要特别说明的是，游戏结束后，由于双方不可再操作，因此不可能出现将军局面，即便此时另一方王处于被「攻击」的位置。**

#### 题目描述

今年的 IDCC（International Duck Chess Competition，国际鸭棋大赛）正在如火如荼地进行着。你观摩了一场精彩绝伦的比赛，但你对对弈过程的记忆已经模糊不清了，只有系统留下的他们的**操作序列**，序列中的每个**操作**为当前操作者试图移动某个位置的棋子至另一个位置。你希望用这个序列，来复现出整局棋局的对弈过程。即，对于每步操作，你需要**首先判其是否合法**，若合法，则**进一步求出**：

1. 这步操作移动了哪个棋子。
2. 这步操作后，是否存在棋子被移出游戏，如有则还需求出被移出游戏的棋子。
3. 这步操作后，是否形成将军局面。
4. 这步操作后，游戏是否结束。

可能包含的不合法情况如下：

* 此步移动的初始位置无己方棋子停留。
* 此步移动的初始位置有己方棋子停留，但移动不符合规则。
* 游戏已经结束。

序列中的不合法操作是需要被忽略的。比如，如果轮到红方移动，此时序列中的当前操作恰好是不合法的，则这个操作将被忽略，序列中的下一步操作将成为红方这步的操作（如仍不合法则继续忽略，直至出现合法的操作）。

inputFormat:
第一行一个非负整数 $Q$，表示操作序列的长度。接下来依次描述每个操作。

接下来 $Q$ 行，每行 $4$ 个整数 $x_s, y_s, x_t, y_t$（$0\leq x_s,x_t < 10$，$0\leq y_s,y_t < 9$），描述一个欲将 $\left(x_s,y_s\right)$ 处棋子移动到 $\left(x_t,y_t\right)$ 的操作。在这里，我们规定左下角（即红方**车**摆放的位置，图见「题目背景」）为 $\left(0,0\right)$。

保证 $Q\leq 1000$。

outputFormat:
输出 $Q$ 行，对于每个操作依次输出复现结果。每行输出一个操作的结果：

* 如果该操作为不合法操作，则请输出 `Invalid command`。
* 如果为合法操作，则依次回答「题目描述」中的问题 $1\sim 4$：
    * 被移动的棋子用 `[颜色] [类型]`（注意中间包含空格）来描述，请使用它们的英文名称（见「题目背景」）。如，红象为 `red elephant`，蓝王为 `blue captain`。
    * 被移出游戏的棋子的描述方式与上面类似。特别地，**如果无棋子被移出游戏，则该问题的答案为 `NA`**。
    * 用 `yes`、`no` 分别表示形成、不形成将军局面。
    * 用 `yes`、`no` 分别表示游戏结束、游戏不结束。
    * 用 `;`（分号）将所有问题的答案隔开。
    * 比如，四个问题的答案分别为：被移动的棋子是蓝车，无棋子被移出游戏，形成将军局面，游戏未结束。则该行应输出 `blue car;NA;yes;no`。

samples:
Invalid command
Invalid command
Invalid command
Invalid command
red guard;NA;no;no
Invalid command
blue captain;NA;no;no
red soldier;NA;no;no
Invalid command
Invalid command
blue elephant;NA;no;no
red duck;NA;no;no
blue horse;NA;no;no
red duck;blue soldier;no;no
Invalid command
blue captain;NA;yes;no
red duck;blue captain;no;yes
Invalid command

hint:
##### 玩具使用说明

你可以在玩具所在目录下执行如下命令来运行玩具（链接: <https://pan.baidu.com/s/12MJGgZB9zKcE3qgRbRozGw> 提取码: 4d5c）：

```
./duckchess
```

特别地，在**初次运行前**，你需要执行如下命令为它添加运行权限：

```
chmod +x duckchess
```

##### 版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

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


title: [THUPC2019] 不等式

description:
> 时光回到 2017 年 6 月 7 日。午后，阳光正好。
>
> 现在的你，在考场中笔耕不辍。在刷刷声中，你填写着交给从前和未来的自己的答卷。
>
> 像无数次训练过的那样，你直接跳到了这张数学试卷的最后一道大题，二选一的题目直接选择了后者。快速地掠过了题目描述，紧缩的眉头渐渐放松。
>
> 「稳了。」
>
> 你一刻也不敢停留，又向你的梦想靠近了一小步。

已知两个 $n$ 维实向量 $\vec{a}=(a_1,a_2,\dots,a_n),\vec{b}=(b_1,b_2,\dots,b_n)$，定义 $n$ 个定义域为 $\mathbb{R}$ 函数 $f_1,f_2,\dots,f_n$：

$$f_k(x)=\sum_{i=1}^{k} \lvert a_ix+b_i\rvert \quad (k=1,2,\dots,n)$$

现在，对于每个 $k=1,2,\dots,n$，试求 $f_k$ 在 $\mathbb{R}$ 上的最小值。可以证明最小值一定存在。

inputFormat:
第一行一个整数 $n$，表示向量的长度及函数的个数。

接下来两行，每行 $n$ 个整数，分别描述向量 $\vec{a},\vec{b}$ 的各个分量，以空格隔开。

对于所有的输入数据，都满足 $1\le n\le 5\times 10^5,\lvert a_i\rvert ,\lvert b_i\rvert <10^5$。

outputFormat:
输出 $n$ 行，第 $i$（$i=1,2,\dots,n$） 行为一个实数，表示 $f_i$ 在 $\mathbb{R}$ 上的最小值。

输出与标准答案的绝对误差或相对误差小于 $10^{-6}$ 就会被算作正确。

hint:
### 样例解释

$f_1(x)=\lvert x+1\rvert$，显然在 $x=-1$ 处取到最小值 $0$；

$f_2(x)=\lvert x+1\rvert +\lvert x+2\rvert$，可以证明其在 $[-2,-1]$ 中任意位置取到最小值 $1$。

##### 后记

后来，全国三卷的考生们又回想起了被参数方程支配的恐惧。

##### 版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

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


title: [THUPC2019] 改善生活

description:
「改善生活」是小 Z 创建的一个群聊。在群聊里，小 Z 和他的 $n-1$ 个朋友们（共 $n$ 名群友，小 Z 的编号为 $1$，他的朋友们的编号从 $2$ 至 $n$）无话不说，畅谈甚欢。然而，经常水群会被冠以水王的名号，这让小 Z 头痛不已。

今天，小 Z 预见到了群里可能会有 $n$ 个话题（编号从 $1$ 至 $n$）。其中，第 $i$ 个话题是 $c_i$ 号群友（当然也有可能是小 Z 自己）感兴趣的话题，这意味着该话题如果出现，这位群友将会进行 $w_i$ 分钟的**激烈发言**。方便起见，你可以认为，除此之外，群友不会进行激烈发言。

所有 $n$ 个话题之间有 $m$ 组引导关系，每组引导关系的形式是一个二元组 $\left(u,v\right)$，它表示如果 $u$ 号话题出现，**必定**会导致 $v$ 号话题出现。

巧合的是，小 Z 发现，所有他自己的**不同**话题都不存在**直接或间接**的引导关系。

由于期中考试的临近，除小 Z 外的群友们都忙于复习，因此他们不会主动发起话题（发起话题指让一个话题出现，下同），也就是说，**所有** $c_i\neq 1$ **的话题都只能由引导关系直接或间接引出**。这让想要水群、却又希望摆脱水王名号的小 Z 左右为难。因此，他决定主动发起**一个或以上**的**自己感兴趣**的话题，来诱导其他话题的出现，致使**水群最多的另一位群友激烈发言的时间**与**小 Z 自己激烈发言的时间**的比值尽可能大。即最大化下面这个式子：

$$\frac{\max\limits_{k=2}^n \text{sum}\left(k\right)}{\text{sum}\left(1\right)}$$

其中，$\text{sum}\left(k\right)$ 表示所有**出现**且**群友 $k$ 感兴趣**的话题的 $w$ 值总和。

为避免精度误差，你只需要求出最大值**向下取整**的结果即可。

inputFormat:
第一行两个正整数 $n,m$，分别表示话题数（恰好也是群人数）、引导关系组数。

第二行 $n$ 个正整数 $c_1,\dots, c_n$（$1\leq c_i\leq n$），依次描述对各话题感兴趣的群友编号。保证至少存在一个$i$ 使得 $c_i=1$。

第三行 $n$ 个正整数 $w_1,\dots, w_n$（$1\leq w_i\leq 100$），依次描述各话题感兴趣的群友将激烈发言的时间。

接下来 $m$ 行描述引导关系，每行两个正整数 $u,v$（$1\leq u,v\leq n$），描述一组引导关系 $\left(u,v\right)$，具体意义见【题目描述】，**保证所有不同的 $c_i=1$ 的话题之间两两不存在直接或间接的引导关系**。

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

保证 $1\leq n\leq 700$，$1\leq m\leq 60000$。

outputFormat: 一行一个**整数**，表示所求式子最大值**向下取整**的结果，即不超过该值的最大整数。

hint:
### 样例解释

小 Z 可以选择发起编号为 3 和 4 的话题，这将致使编号为 5、6、7 的话题出现，并引发 3 号群友时长 $150$ 分钟的激烈发言、以及 4 号群友时长 $40$ 分钟的激烈发言。由于 $3$ 号群友激烈发言时间更长，且小 Z 自己的激烈发言时长为 $60$ 分钟，因此所求最大比值为 $\frac{150}{60}=2.5$，这个值向下取整的结果是 $2$。

可以证明小 Z 不存在更优的策略。

### 版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

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


title: [THUPC2019] 找树

description:
定义 $\otimes_1, \otimes_2, \otimes_3$ 分别为按位与、按位或、按位异或运算。记 $a_i$ 表示 $a$ 的从低位到高位的第 $i$ 个二进制位。定义一个作用在 $w$ 位二进制数上的新运算 $\oplus$，满足对于结果 $a\oplus b$ 的每一位 $(a\oplus b)_i$ 有 $(a\oplus b)_i = a_i \otimes_{o_i} b_i$。不难验证 $\oplus$ 运算满足结合律和交换律。

给出一张 $n$ 个点 $m$ 条边的无向图，每一条边的权值是一个 $w$ 位二进制数（即小于 $2^w$ 的非负整数）。请你找一棵原图的生成树。设你找出的生成树中的边边权分别为 $v_1,\cdots,v_{n-1}$，请你最大化 $v_1\oplus v_2\oplus\cdots\oplus v_{n-1}$。

inputFormat:
第一行两个正整数 $n,m$；

第二行一个长度为 $w$ 的串，串中的每个字符为 `&`、`|`、`^`  中的一个（分别代表与、或和异或），表示每一个 $\otimes_{o_i}$。

接下来 $m$ 行，每一行三个非负整数 $x,y,v$，表示一条连接 $x$ 和 $y$ 权值为 $v$ 的边，保证 $1\leq x,y\leq n$，$0\le v < 2^w$。

对于所有数据，$1\le n\le 70,1\le m\le 5000,1\le w \le 12$。

outputFormat: 输出一行一个数，表示答案。如果图不连通，输出 `-1`。

hint:
### 关于数据

由于一些原因，数据只保留了最后 $20$ 个点。

### 版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

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


title: [THUPC2019] 历史行程

background:
> 人生是怎么样的呢？我们是怎样活着的呢？
>
> 无论是谁，都是从黑暗中降生，最后再回归于黑暗。几年，几十年，短暂而漫长的时光。形形色色的人，形形色色的事，如过眼云烟，转瞬即逝。过眼繁花终有尽时，有些东西还能弥留于你的记忆之中，但更多的，早已无可寻觅。
>
> 但是，有个人，你不会忘记。
>
> 在你降生于黑暗之中时，那个人就一直陪在你身边。当你突破那黑暗，第一次见到世界的光明的时候，那个人也在你身边。
>
> 第一次的啼哭，第一次的说话，第一次的走路，第一次的奔跑。
>
> 每一次的成长，是你自己的一次飞跃。而对那个人来说，则是最纯真的喜悦和感动。
>
>在你不知道的时候，在你不知道的地方，那个人倾尽自己的一切，为你创造最好的一切，保护你的一切，为你指引走向未来的桥梁。
>
> 那个人每天都在期盼着，期盼着你能早点长大，变得拥有保护你自己的力量。
>
> 那个人每天都在担心着，担心着你与那个人分别那天，终究还是会来到。
>
> 你终究会一直成长，你终究会拥有自立自强的能力。那个人，也不能再像以前一样，保护你。
>
> 有一天，你将走向更宽阔的未来，你会拥有和以前完全不一样的一切。而那个人，已经不再能够保护你了。
>
> 而你和那个人之间能够拥有的时间，也就越来越短了。
>
> 五年，十年，二十年，你一天一天长大。
>
> 五年，十年，二十年，那个人一天天老去。
>
> 那个人已经不能保护你了，那么现在，该你，去保护那个人了。
>
> 也许那个人不能永远在你身边，也许那个人终将离你而去。
>
> 但你永远不会忘记那个人，因为那个人，始终在你身边。
>
> 今天，是那个人的节日。

description:
母亲节是一个为感谢母亲而庆祝的节日，而在世界各地的母亲节的日期有所不同。母亲们在这一天里通常会收到孩子们送的礼物；而在许多人心目中，康乃馨被视作最适于献给母亲的鲜花之一。

1913 年，美国国会确定将每年 5 月的第二个星期日作为法定的母亲节，这也是现代母亲节的起源。

给定一个年份，请你输出这一年的母亲节的日期。方便起见，你只需要输出它是这年 5 月的第几天即可。

inputFormat:
一行一个整数 $y$，表示年份。

保证 $1913\leq y\leq 2019$。

outputFormat: 一行一个整数，表示这年的母亲节是 5 月的第几天。（请注意**不要**输出多余的前导零）

hint:
### 样例解释

2019 年的母亲节是 5 月 12 日。

### 关于数据

由于一些原因数据只保留了随机的 $50$ 个点。

### 版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

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


title: 【模板】下降幂多项式乘法

background: 模板题，无背景。

description:
给定一个 $n$ 次下降幂多项式 $A(x)$ 和 $m$ 次下降幂多项式 $B(x)$，你要求出一个 $n+m$ 次下降幂多项式 $F(x)$ 满足 $F(x)=A(x)B(x)$。

由于结果会很大，你输出的多项式的系数应对 $998244353$ 取模。

inputFormat:
第一行两个正整数 $n,m$，表示下降幂多项式的次数。

第二行 $n+1$ 个非负整数 $a_0,a_1,a_2,\dots,a_n$，表示 $A(x)$ 的系数。即 $A(x)=a_0+a_1x+a_2x^{\underline 2}+\dots+a_nx^{\underline n}$。

第三行$m+1$个非负整数$b_0,b_1,b_2,\dots,b_m$，表示 $B(x)$ 的系数。即 $B(x)=b_0+b_1x+b_2x^{\underline 2}+\dots+b_mx^{\underline m}$。

outputFormat: 一行，共 $n+m+1$ 个非负整数，表示 $F(x)$ 的各项系数对 $998244353$ 取模后的结果。

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

对于 $100\%$ 的数据，$1\leqslant n,m\leqslant 10^5$，$a_i,b_i\in[0,998244353)$，$a_n,b_m \neq 0$。

## 提示

$x^{\underline n}=\left\{\begin{matrix}1 & n=0\\ x\times (x-1)^{\underline{n-1}} & n\geqslant 1 \end{matrix}\right.$

$\sum\limits_{i=0}^n a_ix^{\underline i},a_n\neq 0$ 是 $x$ 的 $n$ 次下降幂多项式。

容易证明 $n$ 次下降幂多项式唯一确定一个 $n$ 次多项式，所以下降幂多项式乘积的定义就是对应的多项式的乘积对应的下降幂多项式。


title: [Ynoi2018] 天降之物

background:
可曾做过这样的梦呢？

在我身边，有一个我从没见过的少女

我很喜欢她，她也很喜欢我

不过——

最后总是

在她被天空掳去的时候

迎来梦醒时分

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

人？

不对

不是人

没有人会...

长着翅膀

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

没有没有没有

哪里都没有

没有我可以回去的地方

我没有任何可以回去的地方！

哪里都没有...

我能回去的地方...无论哪里...无论哪里都没有...

我不想杀死任何人，不想伤害任何人！

为什么...为什么要制造出我...

不需要...我不需要这种力量...

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

幸福不足以形容我现在的心情

我该说什么才好呢

啊对了

我...爱你

我爱你...主人

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

神话中的伊卡洛斯，由于过于靠近太阳，用蜡粘住的羽毛融化后坠海而死

description:
伊卡洛斯给了你一个长为 $n$ 的序列 $a$。

你需要实现 $m$ 个操作，操作有两种：

1. 把序列中所有值为 $x$ 的数的值变成 $y$。
2. 找出一个位置 $i$ 满足 $a_i=x$，找出一个位置 $j$ 满足 $a_j=y$，使得 $|i-j|$ 最小，并输出 $|i-j|$。

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

之后一行 $n$ 个整数，表示序列 $a$。

之后 $m$ 行，每行三个数 $opt,x,y$。

如果 $opt$ 为 $1$，代表把序列中所有值为 $x$ 位置的值变成 $y$。

如果 $opt$ 为 $2$，代表找出一个位置 $i$ 满足 $a_i=x$，找出一个位置 $j$ 满足 $a_j=y$，使得 $|i-j|$ 最小，并输出 $|i-j|$，如果找不出这样的位置，输出 `Ikaros`。

本题强制在线，每次的 $x,y$ 需要 xor 上上次答案，如果输出 `Ikaros`，或者是第一次询问，则上次答案为 $0$。

共 $50$ 组数据，数据中保证 $n=m$。

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

如果无法找出满足题意的 $i,j$，则输出 `Ikaros`。

hint:
Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477( partially uploaded )

对于 $100\%$ 的数据，所有数在 $[1,10^5]$ 内，每次操作的值不超过 $n$。


title: 第二类斯特林数·行

description:
第二类斯特林数$\begin{Bmatrix} n \\m \end{Bmatrix}$表示把$n$个**不同**元素划分成$m$个**相同**的集合中（不能有空集）的方案数。

给定$n$，对于所有的整数$i\in[0,n]$，你要求出$\begin{Bmatrix} n \\i \end{Bmatrix}$。

由于答案会非常大，所以你的输出需要**对$167772161$（$2^{25}\times 5+1$，是一个质数）取模**。

inputFormat: 一行一个正整数$n$，意义见题目描述。

outputFormat:
共一行$n+1$个非负整数。

你需要按顺序输出$\begin{Bmatrix} n \\0 \end{Bmatrix},\begin{Bmatrix} n \\1 \end{Bmatrix},\begin{Bmatrix} n \\2 \end{Bmatrix},\dots,\begin{Bmatrix} n \\n \end{Bmatrix}$的值。

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

对于$100\%$的数据，$1\leqslant n\leqslant 2\times 10^5$。


title: 第二类斯特林数·列

background: **验题人提示：程序运行时间受评测压力影响较大，评测高峰可能会被卡常。**

description:
第二类斯特林数$\begin{Bmatrix} n \\m \end{Bmatrix}$表示把$n$个**不同**元素划分成$m$个**相同**的集合（不能有空集）的方案数。

给定$n,k$，对于所有的整数$i\in[0,n]$，你要求出$\begin{Bmatrix} i \\k \end{Bmatrix}$。

由于答案会非常大，所以你的输出需要对$167772161$（$2^{25}\times 5+1$，是一个质数）取模。

inputFormat: 一行两个正整数$n,k$，意义见题目描述。

outputFormat:
共一行$n+1$个非负整数。

你需要按顺序输出$\begin{Bmatrix} 0 \\k \end{Bmatrix},\begin{Bmatrix} 1 \\k \end{Bmatrix},\begin{Bmatrix} 2 \\k \end{Bmatrix},\dots,\begin{Bmatrix} n \\k \end{Bmatrix}$的值。

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

对于$100\%$的数据，$1\leqslant k,  n<131072$。


title: [Ynoi2018] GOSICK

background:
  ![](https://cdn.luogu.com.cn/upload/pic/58864.png)
洋...娃娃？

“终于来了啊”

“太慢了，伴随春天而来的死神”
   ![](https://cdn.luogu.com.cn/upload/pic/58865.png)
维多利...加？

你...手不疼吗

手通红的啊

“无路赛...振作一点”

“如果在这里放弃的话就永远绝交了，久城！”

“要一起回去”

“之前也说过的吧 一起...”

“我们俩分离的地方，不是这里吧”

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

“太慢了，伴随春天而来的死神”

别生气嘛 我这也是很赶时间了

信收到了吗

“嗯，因为都很认真写上地址了”

“运用智慧之泉，终于到达了这里”

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

无论世界如何改变

这次之后 将再不分离

description:
维多利加给了你一个序列 $a$，每次询问给一个区间 $[l,r]$。

查询 $l \leq i,j\leq r$，且 $a_i$ 是 $a_j$ 倍数的二元组 $(i,j)$ 的个数。

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

第二行 $n$ 个整数表示序列 $a$。

之后 $m$ 行，每行两个整数 $l,r$ 表示一次询问。

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

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

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


title: [Ynoi2018] 駄作

background:
以前在书上读到的皮格马利翁神话——

记得那在年幼的自己看来，非常滑稽。

那是一心一意地，

雕刻着自己理想中的女性的男人的故事。

对现实中的女性根本不看一眼。

不把人类放在眼里，只是一味地爱着无机物。

爱着没有灵魂的对象。

在当时的我看来，那行为是极为的愚蠢。

多么悲惨啊。

高举理想的旗帜、悲惨地制作着爱情的投影。

自导自演自我满足——那是失败者的作为。

最后那人得到了女神阿佛洛狄忒的同情，

令雕像拥有了灵魂。

是羞耻的极致。不会成为美谈。

被愚蠢的故事破坏了心情的我，

粗暴地丢下了那本书。

在那时。

我忽然感觉到了。

如同脚尖悬空般的微微的高昂感。

目光所不能直视的耀眼光晕。

心脏深处温柔且安静地紧揪着的感觉。

不知为何，温柔的心情在胸中弥漫。

这第一次体会到的心情是什么呢？

温暖、粘稠、浑浊。

舒适的小憩。

愚蠢的男人的故事。

毫无拯救价值的，蠢男人的恋爱观。

知道了这一点——

我——

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

“这种烦恼谁都没办法理解啊……”

“呜呜，好难过……”

……

“……嗯？怎么在发呆啊？”

哎？啊，不是。没什么啦。

总觉得……和我很相似。

因为是对谁也不能说出口的烦恼所以很辛苦。

现在的枢大概也是同样的心情吧。

枢还真是有着不为人知的艰辛啊。

“啊哈哈，算是吧。”

“因为我有性别认知障碍啊，身体和内心的性别是不一样的，所以没什么可以分
担苦恼的人。”

“像这种下半身的事情，怎么也不能和别的女孩子讨论呢。”

确实如此啊……

“啊，好想干脆让身体也变成女性啊……该怎么办才好呢。”

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

身体和内心的性别不一样吗……

我倒不是性别认知障碍……

不过，却非常理解枢的感受。

“男性和女性都不能理解的烦恼……

我就是个不完整的人吗……”

怎么说不完整，才没这回事。

“——是吗？”

……啊。

怎、怎么了……

刚才，枢的气氛突然变了……

“——我的烦恼啊，平时对谁也不会说的。”

……

“因为很难被理解啊，都当成是在开玩笑……根本没有谁真心想着帮我分担。”

这……确实是呢……

而我也是如此——

“不过呢……”

“——我挺想和由贵君商量的呢……”

原本我就对枢抱有亲近感。

心灵与身体的性别不一致的人。

枢有着男性的身体和女性的内心。

我也好枢也好……在旁人看来都是不完整的存在。

不过……我——只有我能理解。

——枢不是个不完整的人。

正因为是同样不完整的存在，我才能从心底完全理解。

我……对自己——想要枢理解我。

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

“我们五人永远都是朋友……

从前是……今后也是……”

在大家安稳的话声中，我闭上眼。

——不会消失。

不管是星星的光辉，还是大家的温暖。

已经牢牢地刻在了我的心中。

一定不会忘记，五人一起度过的日子。

我无论如何都不会忘记。绝不会忘记。

是吗，我在寻求着啊……

如此美好的羁绊……

从心底里……

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

枢惊讶的表情，慢慢地恢复了平静。

我紧张地盯着枢的嘴唇，

不知道他接下来要说什么。

厌恶吗？恐惧吗？

还是说勉强摆出生硬的笑容给我看？

……哪个都会让人伤心难受。

我很怕失去与枢之间的关系。

“……由贵君。”

心脏跳动着。

“我——”

枢所道出的话语，只有一句

“——能接受由贵君。”

我最期望着的话语——

很有聪明的枢的风格的、简洁而又完美的话语。

……谢谢。

“诶嘿嘿……不用客气。”

枢温柔的笑容包容着我。

被人接受这件事，原来是如此惬意的啊……

“……我说啊，由贵君”

“和由贵君有着不普通的身体一样，我也不是普通的。”

枢和我是不一样的……

“不……我也是异常的。

因为明明作为一个男性出生，却想成为女孩子。”

“身体是男性……也没有胸部，也没有女性器。

是真真正正的男性。”

“明明这样还是想变成女性……

我知道的。明明变不成……

明明知道越是想成为女性就越会变得扭曲……”

“即使如此我也想成为女性，不觉得我也是怪物吗？”

……

语塞了。

但是，我仍然只是继续沉默着。

这种时候，粉饰的话语也不会起什么作用。

我知道随便的安慰是没有意义的。

所以……我只是默默地凝视着枢。

“呵呵，由贵君真是温柔呢……

最清楚我是怎么想的。”

因为我明白……枢的心情啊。

听我如此说，枢便露出了发自内心的微笑。

“有人能‘真正’理解我，这还是第一次。”

我也是……终于遇见了能够接受自己的人。

在漫长艰险的旅途尽头，我们终于得到了救赎。

我也好，枢也好，都是与“普通”想去甚远的、

因此才一直非常痛苦……

不过我们终于——

——遇到了能够理解自己的同伴。

description:
菜菜子给了你一棵 $n$ 个节点的树，结点标号从 $1$ 到 $n$ 。

定义树上两点 $a,b$ 的距离 $d(a,b)$ 是最小的非负整数 $k$ ，满足存在结点序列 $v_0,v_1,...,v_k$ ，满足 $v_0=a,v_k=b$ ，且对于 $0\leq i\leq k-1$ 有 $v_i$ 和 $v_{i+1}$ 之间在树上有一条边相连。

有 $m$ 个询问，每个询问包含参数 $p_0,d_0,p_1,d_1$ ，求：

$$\sum\limits_{d(p_0,a)\leq d_0}\sum\limits_{d(p_1,b)\leq d_1}d(a,b)$$

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

接下来一行 $n-1$ 个整数 $f_2,f_3,...,f_n$ ，依次表示 $i$ 和 $f_i$ （ $1\leq f_i\leq i-1$ ）之间有一条边。

接下来一行一个整数 $m$ ，表示询问数目。

接下来 $m$ 行依次描述所有询问：每行四个整数 $p_0,d_0,p_1,d_1$ （ $1\leq p_0,p_1\leq n,0\leq d_0,d_1\leq n-1$ ）描述一组询问。

outputFormat: 共 $m$ 行，依次回答各组询问：每行输出一行一个整数表示这组询问的答案。

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

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


title: [CTS2019] 随机立方体

description:
有一个 $n\times m\times l$ 的立方体，立方体中每个格子上都有一个数，如果某个格子上的数比三维坐标**至少有一维**相同的其他格子上的数都要大的话，我们就称它是极大的。

现在将 $1\sim n\times m\times l$ 这 $n\times m\times l$ 个数等概率随机填入 $n\times m\times l$ 个格子（即任意数字出现在任意格子上的概率均相等），使得每个数恰出现一次，求恰有 $k$ 个极大的数的概率。答案对 $998244353$（一个质数）取模。

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

接下来 $T$ 行，每行一组数据，包含 $4$ 个正整数 $n,m,l,k$，表示一次询问。

outputFormat:
对于每次询问，输出一行一个整数，表示答案对 $998244353$ 取模的余数。

可以证明，答案一定为有理数。设其为 $a/b$（$a$ 和 $b$ 为互质的正整数，数据保证 $b$ 不为 $998244353$ 的倍数），则你需要保证输出的数 $x$ 满足 $0\le x < 998244353$ 且 $a\equiv bx \pmod{998244353}$。可以证明这样的 $x$ 唯一存在。


title: [CTS2019] 珍珠

background:
白云苍狗，沧海桑田。

白云的眼前只剩下了模糊的一片。

在若隐若现之中，它看到了一个个小小的珍珠，有一些发着五彩的光芒。这些珍珠是白兔留下来的，每颗珍珠有一个颜色，为 $D$ 种颜色中随机的一种。

白云想把这些珍珠放进一些小瓶子中，每个瓶子能恰好容纳两颗珍珠。不过它也有要求，每个瓶子必须装满，并且装的都是相同颜色的珍珠。

白云希望能得到至少 $m$ 个装满珍珠的瓶子，它想知道它的愿望能被实现的概率是多少呢？

description:
有 $n$ 个在范围 $[1,D]$ 内的整数均匀随机变量。

求至少能选出 $m$ 个瓶子，使得存在一种方案，选择一些变量，并把选出来的每一个变量放到一个瓶子中，满足每个瓶子都恰好装两个值相同的变量的概率。

请输出概率乘上 $D^n$ 后对 $998244353$ 取模的值。取模部分说明可参考第一题。

inputFormat: 输入仅一行，三个用空格隔开的整数 $D,n,m$。

outputFormat: 输出一个整数，表示所求概率乘上 $D^n$ 后对 $998244353$ 取模的结果。

hint:
#### 样例 1 解释
情况 $1$ : 第一个变量为 $1$，第二个变量为 $1$

情况 $2$ : 第一个变量为 $1$，第二个变量为 $2$

情况 $3$ : 第一个变量为 $2$，第二个变量为 $1$

情况 $4$ : 第一个变量为 $2$，第二个变量为 $2$

其中情况 $1$ 和 $4$ 可以把两个变量放到一个瓶子中

情况 $2$ 和 $3$ 中两个变量的值不相同，所以不能放到同一个瓶子中

#### 测试数据约定
![img](https://s2.ax1x.com/2019/05/17/Eq683D.png)

所有测试点均满足 $0 \leqslant  m \leqslant  10^9,1 \leqslant  n \leqslant  10^9,1 \leqslant  D \leqslant  10^5$。


title: [CTS2019] 无处安放

background:
寂寥深夜，朦朦胧胧的月光为一切都笼上一层轻纱，你漫步在幽径，时而低头沉
吟，时而凝望星空，只独孤与彷徨作伴，哪怕只言片语却也无人倾诉，万千思绪伴着你炽热的心，随风而动，无处安放……

description:
你整理出了 $n$ 条思绪，它们在你的心中是一个个矩形 $r_i$，你想要在心中用一个大矩形 $R$ 安放它们，也就是将 $r_i$ 放置在 $R$ 内部。为了保护这些思绪，它们安放的位置不能与其他思绪有重合部分，并且四条边要平行或垂直于 $R$ 的边。两个思绪有重合部分，指它们安放位置的重合面积大于零。

你有两种安放方式：
1. 将 $n$ 条思绪全部安放进R 中，希望令 $R$ 的面积尽量小。
2. 固定 $R$ 的大小，希望将尽量多的思绪安放进 $R$ 中。

现在我已知晓你整理好的思绪，为你选择了安放的方式，我想知道你心中最好的安放方案，请你告诉我。

inputFormat:
第一行两个整数 $type, n$，分别表示安放方式与思绪的个数。

若 $type = 2$，第二行两个整数 $W, H$，表示 $R$ 的边长。

接下来 $n$ 行每行两个整数 $w_i, h_i$，表示第 $i$ 个思绪即 $r_i$ 的边长。

同一行中输入的整数均以一个空格分隔开。

outputFormat:
为了方便，若 $R$ 的边长为 $W, H$，我们将安放方案视作一个 $(0, 0)\sim(W, H)$ 的直角坐标系。注意对于 $type = 2$ 的测试点，你应按输入，将其视作 $(0, 0)\sim(W, H)$ 的坐标系，而不是 $(0, 0) \sim (H, W)$ 的坐标系。

输出共有 $n$ 行，每行一或四个整数，描述第 $i$ 个思绪即 $r_i$ 的放置方案。

每行第一个整数 $c_i$，其中 $c_i = 1$ 表示 $r_i$ 被安放在 $R$ 中；$c_i = 0$ 表示 $r_i$ 未被安放在 $R$ 中。

若 $c_i = 1$, 则该行接下来应输出三个整数 $x_i$, $y_i$, $d_{ir_i}$。若 $d_{ir_i} = 0$，则 $r_i$ 放置在 $(x_i, y_i)\sim(x_i + w_i, y_i + h_i)$ 的矩形范围内；若 $d_{ir_i} = 1$，则 $r_i$ 放置在 $(x_i, y_i)\sim(x_i + h_i, y_i + w_i)$ 的矩形范围内。

请注意确保你的输出格式正确，且 $c_i, d_{ir_i} \in \{0, 1\}$。对于 $type = 1$ 的测试点，所有 $c_i$ 均应为 $1$。

同一行中输出的整数应以一个空格分隔开。

hint:
#### 评分方式

每个测试点设置了 $10$ 个评分参数 $a_1, a_2, ..., a_{10}$。若选手输出不合法，则得零分。

否则，对于安放方式 $1$，令 $val$ 为 $R$ 的面积，若 $val \leq a_i$，则你可获得 $i$ 分；对于安放方式 $2$，令 $val$ 为安放到 $R$ 中的思绪个数，若 $val \geq a_i$ 则你可获得 $i$ 分。满足多个得分条件，测试点得分取最高者。


title: [CTS2019] 田野

description:
> Last night I saw you running
In the open fields of grace
No longer were you broken or in pain
>
> 题面中的歌词来自 Jackie Evancho 的 Open Fields of Grace，作曲者为 Lisa Venkatrathnam 和 Paul Sumares。

你找到了一片一望无际的大田野，在这片田野中你忘记了曾经破碎、痛苦的过去。你像小孩一样在上帝的恩赐中奔跑。

然而你发现了一个问题，在这片田野中有若干条峡谷。你随时都有坠入峡谷中的危险。为了继续自由自在的奔跑，你决定用若干围栏将这些峡谷围起来。

我们可以忽视峡谷的宽度，将每一条峡谷看做一条线段。**这些线段可以相交**，而你的围栏必须是**一条或多条闭合不自交且两两不相交的曲线**，使得**任何一个峡谷都完全在某一条**闭合曲线围成的闭合区域之内。
当然，围栏需要消耗资源，消耗的资源和围栏的长度成正比，你希望最小化消耗的资源总量，所以你希望求出围栏总长度的**下确界**，换句话说，你希望找到一个最大的实数 $x$，使得不存在一个方案使得围栏总长度小于 $x$。

inputFormat:
输入文件的第一行为一个整数 $n$，表示峡谷的个数。

接下来 $n$ 行，第 $i$ 行四个整数 $a_i,b_i,c_i,d_i$，表示第 $i$ 条峡谷为一条连接点 $(a_i,b_i)$ 和点 $(c_i,d_i)$ 的线段。**保证两个端点不重合，不同的线段不会涉及到相同的点。保证任意三点不共线。**

outputFormat: 输出一行一个实数，表示围栏总长度的下确界。**你的答案和标准答案的绝对误差和相对误差的最小值不能超过** $10^{-6}$。

hint:
#### 样例 1 解释
一个四个端点分别为 $(−0.01,−0.01),(−0.01,1.01),(0.01,1.01),(0.01,−0.01)$ 的长方形完全包含输入的线段，且总长度为 $2.08$，略大于下确界。

我们可以证明，不存在长度恰好为 $2$ 的方案。我们可以通过将正方形无限向输入线段“缩紧”来构造一个长度为任意大于 $2$ 的方案。

#### 样例 2 解释
下图为输入的线段，注意线段可以相交：
![img1](https://s2.ax1x.com/2019/05/17/ELd6pj.png)

我们以通过无限“逼近”这些红色的曲线来构造任意总长度大于答案的方案。注意通过样例 1，我们很容易知道左上角的红色线段被算了两遍。

#### 样例 3 解释
答案为 $8+4\sqrt 2$。

解释如图：

![img2](https://s2.ax1x.com/2019/05/17/ELdINF.png)

我们可以通过无限“逼近”这些红色的曲线来构造任意总长度大于 $8+4\sqrt 2$ 的方案。

#### 测试数据约定
对于 $5\%$ 的数据，保证 $1\le n\le 1$。

对于 $10\%$ 的数据，保证 $1\le n\le 2$。

对于 $15\%$ 的数据，保证 $1\le n\le 10$。

对于 $30\%$ 的数据，保证 $1\le n\le 15$。

对于 $45\%$ 的数据，保证 $1\le n\le 30$。

对于 $55\%$ 的数据，保证 $1\le n\le 60$。

对于 $65\%$ 的数据，保证 $1\le n\le 120$。

对于 $75\%$ 的数据，保证 $1\le n\le 200$。

对于另外 $10\%$ 的数据，保证答案最多包含两条曲线。

对于 $100\%$ 的数据，保证 $1\le n\le 250$，$0\le |a_i|,|b_i|,|c_i|,|d_i|\le 10^9$。**保证两个端点不重合，不同的线段不会涉及到相同的点。保证任意三点不共线。**


title: [CTS2019] 重复

background:
贾樟柯在《山河故人》里说，“生活就是重复”。在生活中，人们总是喜欢重复自己做过的事情。语言就是一个很经典的例子。

比如，我们在表示疑问时，总不满足于使用一个问号“？”；使用一连串的问号“？？？？”总是显得比较有力。

在表示抱歉时，一句“对不起”总显得不够情愿；连着表示“对不起对不起”才足够表达自己的真诚。

description:
A 国就是一个喜欢重复的国家。在这个国家中，一个基本句子可以用一个长度恰好为 $m$ 的小写字母字符串表示。为了表达自己对重复的喜爱，A 国的人们总喜欢把自己想要表达的句子重复无限多次。

有时，这样的重复是充满意义的。A 国的人们把一个字典序小于给定的字符串 $s$，且长度和 $s$ 相同的小写字母字符串称为一个有意义的语义片段。他们想知道，有多少个不同的基本句子（即长度恰好为 $m$ 的小写字母字符串）在经过无限重复后，可以从中找出至少一个有意义的语义片段？

inputFormat: 输入文件的第一行为一个正整数 $m$，表示基本句子的长度；第二行为一个小写字母字符串 $s$，其含义详见题目描述。

outputFormat: 输出一行一个整数，为满足条件的基本句子的数量。为了避免答案过大，你只需要输出将答案对 $998244353$ 取模后的结果。

hint:
设字符串 $s$ 的长度为 $n$，则 $n$、$m$ 的范围遵循如下表格：

![img](https://s2.ax1x.com/2019/05/17/EL0fFU.png)

对于 $100\%$ 的数据，保证 $1\le n,m\le 2000$。


title: [CTS2019] 氪金手游

description:
小刘同学是一个喜欢氪金手游的男孩子。

他最近迷上了一个新游戏，游戏的内容就是不断地抽卡。现在已知：
- 卡池里总共有 $N$ 种卡，第 $i$ 种卡有一个权值 $W_i$，小刘同学不知道 $W_i$ 具体的值是什么。但是他通过和网友交流，他了解到 $W_i$ 服从一个分布。
- 具体地，对每个 $i$，小刘了解到三个参数 $p_{i,1},p_{i,2},p_{i,3}$，$W_i$ 将会以 $p_{i,j}$ 的概率取值为 $j$，保证 $p_{i,1}+p_{i,2}+p_{i,3}=1$。

小刘开始玩游戏了，他每次会氪一元钱来抽一张卡，其中抽到卡 $i$ 的概率为：
$$\frac{W_i}{\sum_j W_j}$$
小刘会不停地抽卡，**直到**他手里集齐了全部 $N$ 种卡。

抽卡结束之后，服务器记录下来了小刘**第一次**得到每张卡的时间 $T_i$。游戏公司在这里设置了一个彩蛋：公司准备了 $N-1$ 个二元组 $(u_i,v_i)$，如果对任意的 $i$，成立 $T_{u_i}<T_{v_i}$，那么游戏公司就会认为小刘是极其幸运的，从而送给他一个橱柜的手办作为幸运大奖。

游戏公司为了降低获奖概率，它准备的这些 $(u_i,v_i)$ 满足这样一个性质：对于任意的 $\varnothing\ne S\subsetneq\{1,2,\ldots,N\}$，总能找到 $(u_i,v_i)$ 满足：$u_i\in S,v_i\notin S$ **或者** $u_i\notin S,v_i\in S$。

请你求出小刘同学能够得到幸运大奖的概率，可以保证结果是一个有理数，请输出它对 $998244353$ 取模的结果。

inputFormat:
第一行一个整数 $N$，表示卡的种类数。

接下来 $N$ 行，每行三个整数 $a_{i,1},a_{i,2},a_{i,3}$，而题目给出的 $p_{i,j}=\frac{a_{i,j}}{a_{i,1}+a_{i,2}+a_{i,3}}$。

接下来 $N-1$ 行，每行两个整数 $u_i,v_i$，描述一个二元组（意义见题目描述）。

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

hint:
#### 样例 1 解释
$W_2$ 以 $\frac 12$ 的概率取 $1$ 或者 $2$：
- 如果 $W_2=1$，那么 $T_1<T_2$ 的概率为 $\frac 34$。
- 否则 $W_2=2$，$T_1<T_2$ 的概率为 $\frac 35$。

综合所有情况答案为 $\frac 12\left(\frac 34+\frac 35\right)=\frac{27}{40}$，你可以验证它对 $998244353$ 取模的结果确实是所给答案。

#### 测试数据约定
对于全部的测试数据，保证 $N\le 1000$，$a_{i,j}\le 10^6$。

- $20$ 分的数据，$N\le 15$。
- $15$ 分的数据，$N\le 200$，且每个限制保证 $|u_i−v_i|=1$。
- $20$ 分的数据，$N\le 1000$，且每个限制保证 $|u_i−v_i|=1$。
- $15$ 分的数据，$N\le 200$。
- $30$ 分的数据，无特殊限制。


title: 第一类斯特林数·行

description:
第一类斯特林数$\begin{bmatrix}n\\ m\end{bmatrix}$表示将$n$个**不同**元素构成$m$个圆排列的数目。

给定$n$，对于所有的整数$i\in[0,n]$，你要求出$\begin{bmatrix}n\\ i\end{bmatrix}$。

由于答案会非常大，所以你的输出需要对$167772161$（$2^{25}\times 5+1$，是一个质数）取模。

inputFormat: 一行一个正整数$n$，意义见题目描述。

outputFormat:
共一行$n+1$个非负整数。

你需要按顺序输出$\begin{bmatrix}n\\ 0\end{bmatrix},\begin{bmatrix}n\\ 1\end{bmatrix},\begin{bmatrix}n\\ 2\end{bmatrix},\dots,\begin{bmatrix}n\\ n\end{bmatrix}$的值。

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

对于$100\%$的数据，$1\leqslant n< 262144$。


title: 第一类斯特林数·列

background:
模板题，无背景。

**验题人提示：程序运行时间受评测压力影响较大，评测高峰可能会被卡常。**

description:
第一类斯特林数$\begin{bmatrix}n\\ m\end{bmatrix}$表示将$n$个**不同**元素构成$m$个圆排列的数目。

给定$n,k$，对于所有的整数$i\in[0,n]$，你要求出$\begin{bmatrix}i\\ k\end{bmatrix}$。

由于答案会非常大，所以你的输出需要对$167772161$（$2^{25}\times 5+1$，是一个质数）取模。

inputFormat: 一行两个正整数$n,k$，意义见题目描述。

outputFormat:
共一行$n+1$个非负整数。

你需要按顺序输出$\begin{bmatrix}0\\ k\end{bmatrix},\begin{bmatrix}1\\ k\end{bmatrix},\begin{bmatrix}2\\ k\end{bmatrix},\dots,\begin{bmatrix}n\\ k\end{bmatrix}$的值。

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

对于$100\%$的数据，$1\leqslant k,n< 131072$。


title: [YNOI2019] 排队

description: 小明所在的班级要举办一场课外活动，在活动开始之前老师告诉小明：“需要把男女生分成两队，并且每一队都要按照身高从矮到高进行排序”。但是由于小明的马虎，没有把老师的安排转达给同学，导致全班同学已经排成了一列。活动马上要开始了，小明的老师对此很困扰，你能帮帮她吗？

inputFormat:
每个输入文件包含多组数据。

输入文件的第一行，包含一个正整数 $T$，代表该输入文件中所含的数据组数。

接下来是 $T$ 组数据，每组数据的格式如下：

每组数据包含 $3$ 行；

第一行包含一个整数 $n$，代表班级的总人数，其中 $(0 < n \leq 2\times 10^{3})$；

第二行包含 $n$ 个整数，它们之间用一个空格隔开，代表已经排成的一列中每一位同学的性别。每一位整数只取 $0$ 或 $1$（$0$ 表示女生，$1$ 表示男生）；

第三行包含 $n$ 个浮点数，它们之间用一个空格隔开，与第二行中的数据一一对应，代表已经排成的一列中每一位同学的身高 $h(100 \leq h \leq 200)$。

outputFormat:
输出文件包含 $2T$ 行，分别对应 $T$ 组数据的答案，每组答案的格式如下：

每组答案包含 $2$ 行；

第一行按照从小到大的顺序输出所有女生的身高；

第二行按照从小到大的顺序输出所有男生的身高。

注意在输出身高时，请按照原来的身高保留对应的小数点位数。


title: [YNOI2019] 骑单车

description: 小明每天早晨上课都需要骑着单车经过 $n$ 段路，第i段路的长度为$w_i (m)$，限速为 $s_i (m/s)$（在路上骑行的速度不能超过限速），加速度的绝对值最大为 $a_i (m/s^{2})$（可以加速也可以减速）。初始速度为 $0(m/s)$，你的任务是计算小明通过这 $n$ 段路的最短时间。

inputFormat:
**本题包含多组数据。**

第一行，包含一个正整数 $T$，代表所含的数据组数。

接下来是 $T$ 组数据，每组数据的格式如下：

每组数据包含 $n+1$ 行；

第一行包含一个正整数 $n$，代表共有 $n$ 段路；

接下来的 $n$ 行，每一行包含三个正整数 $w_i,s_i,a_i$，分别代表第 $i$ 段路的长度、限速和最大加速度的绝对值。

outputFormat: 输出包含 $T$ 行，分别对应T组数据的答案，即小明通过 $n$ 条道路所需要的最短时间（只要你的答案和标准答案的绝对误差在 $10^{-5}$ 以内就算通过）。


title: [YNOI2019] 排序

description:
对于一个数列 $\{7, 1, 2, 3\}$ 进行排序，我们可以把 $7$ 从头移动到尾。但是这个操作的成本是 $7$，并不是最佳的。最佳的排序方式是将连续的 $1,2,3$ 移动到 $7$ 的前面。这样的话，总的操作成本就是 $1+2+3=6$，比之前的成本 $7$ 要小。

你的任务是，对于一个给定的数列，输出对这个数列进行排序的最小成本。

inputFormat:
输入文件名为sort.in。

每个输入文件包含多组数据。

输入文件的第一行，包含一个正整数 $T$，代表该输入文件中所含的数据组数。

接下来是 $T$ 组数据，每组数据的格式如下：

每组数据包含 $2$ 行；

第一行包含一个正整数 $n$，代表数列中元素的个数，其中 $0 < n \leq 10^2$；

第二行包含 $n$ 个整数，两个数之间以一个空格隔开，代表数列中的元素 $k_i$，其中$-10^{7} \leq k_i \leq 10^{7}$。

outputFormat:
输出文件名为sort.out。

输出文件包含 $T$ 行，分别对应 $T$ 组数据的答案，即对数列进行排序的最小成本。


title: [YNOI2019] 游戏

description:
在经历了漫长的烧脑之旅后，相信同学们的思维已经充分地活跃起来了。最后，让我们玩一个游戏来结束这次充满乐趣和挑战的冒险之旅！

有 $n$ 个人在玩游戏，游戏规则如下：

在游戏开始之前，将这 $n$ 个人按照 $1\sim n$ 的顺序唯一编号。游戏开始后，每一轮只允许 $4$ 个人进入游戏，其他人按照各自的编号组成等待队列，等待参加游戏。

游戏中每个人赢得比赛的机会是同等的，游戏举办多轮，每一轮的获胜者可以继续参加下一轮的比赛，输家将根据本轮比赛开始之前的顺序排在等待队列的末尾（如果本轮的输家中有人之前赢得过比赛，那么他将在等待队列中排在本轮所有输家的前面）。

例如，在某一轮比赛开始之前小明排在小红和小刚前面，如果在该轮比赛中小明、小红和小刚都没有赢，那么小明、小红和小刚将退出比赛排在等待队列的末尾，但是小明将会继续按照比赛开始之前的顺序排在小红和小刚前面。存在的特殊情况是，如果小刚在这轮比赛之前赢得过比赛，那么小刚将在等待序列中排在小明和小红的前面。

比赛中，如果有人连续赢了 $m$ 次，那么他就是这个游戏最后的赢家。你的任务是，预测第 $k$ 个人成为最终赢家的可能。

inputFormat:
**输入包含多组数据。**

第一行，包含一个正整数 $T$，代表该输入文件中所含的数据组数。

接下来是 $T$ 组数据，每组数据的格式如下：

每组数据仅一行，包含三个整数 $n,m,k$。

outputFormat: 输出包含 $T$ 行，分别对应 $T$ 组数据的答案，即第 $k$ 个人成为最终赢家的可能（结果保留 $6$ 位小数）。

hint:
#### 数据规模与约定
- 对于 $30\%$ 的数据：保证 $ n \le 5$，$m \le 5$。
- 对于 $60\%$ 的数据：保证 $n \le 8$，$m \le 8$。
- 对于100%的数据：保证 $4 \le n \le 10$，$0 < m \le 10$，$1\le k \le n$，$T=1$。


title: [CmdOI2019] 星际kfc篮球赛

background:
公元 $3100$ 年，地球联盟的银河系内 $N$ 个星球已经完成了道路大建设，从原来的 $N-1$ 条双向时空隧道变成了**无向完全图**。

Louis Paosen 是一个星际旅行家，上次你~~虐队的时候~~顺便帮他解决了难题，于是他又来请求你帮忙啦。

description:
仍然是出于资金的考虑，地球联盟没能将所有的道路都建造得尽善尽美。通过某条道路**对于飞船的性能有一定的要求**。

Louis Paosen 在联盟内举办了盛大的 kfc 三人篮球赛，一时间，许多来自不同星球的选手纷纷赶来参赛。

整个地球联盟的内部正在热卖三种飞船 (A/B/C 类)，由于收了广告费的缘故，组队的时候要求 $3$ 人中第一人使用 A，第二人使用 B，第三人使用 C (这样可以获得加分)。

现在有许许多多个三人小组准备参赛，他们准备好了飞船(符合加分条件)，但是他们可能来自不同的星球，由于飞船性能的限制，他们可能无法一起到达某个星球。

由于这三家公司制造工艺大相径庭，飞船对同一条道路环境的耐受力区别很大，而有奇怪的规律。

点 $u$ 有三组系数 $P_A[u],P_B[u],P_C[u]$ ，边 $u\leftrightarrow v$ 的通过难度为:

$$\begin{cases}\text{A形飞船通过难度}=P_A[u]\ {\rm xor}\ P_A[v]\\\text{B形飞船通过难度}=P_B[u]\ {\rm xor}\ P_B[v]\\\text{C形飞船通过难度}=P_C[u]\ {\rm xor}\ P_C[v]\end{cases}$$

当一个飞船的性能指数不低于某条边对应种类的通过难度时,这个飞船才能够通过 (具体见样例解释)。

Louis Paosen 在每个星球上都准备了比赛点，所以你只要对每个三人小组，给出其可行的集合点个数就好了。

inputFormat:
第一行：$n,q$。

第 2~4 行：$P_A[1\sim n],P_B[1\sim n],P_C[1\sim n]$。

后 $q$ 行：每行六个数 $h_A,u_A,h_B,u_B,h_C,u_C$ ，表示一个三人小队中每个人的飞船性能以及出发星球编号。

outputFormat: 对于每个三人小队，输出一行一个数，回答可行的集合点个数。


title: [CmdOI2019] 简单的数论题

description:
给出 $n,m$ 求下列式子的值 ：

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m \varphi\left(\dfrac{{\rm lcm}(i,j)}{\gcd(i,j)}\right) \bmod 23333$$

inputFormat:
第一行一个整数 $T$，表示询问数。

后 $T$ 行每行两个整数 $n,m$ ,表示一个询问。

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


title: 无标号无根树计数

background: 考虑到你谷还没有这类题，于是就放了这么个水题

description: 求 $n$ 个点的无标号无根树数量，答案对 $998244353$ 取模。

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

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

hint:
【数据范围】
对于 $30\%$ 的数据，$1\le n \le 1000$；
对于 $100\%$ 的数据，$1\le n \le 2\times 10^5$。

虽然 $\Theta(n \log^2 n)$ 也能过，但是没什么意义，建议写一下 $\Theta(n \log n)$ 的做法。


title: 有标号 DAG 计数

description:
对 $n$ 个点有标号的有向无环图进行计数，要求：弱连通图（所有的有向边替换为无向边后的图为连通图）。输出答案对
 $998244353$ 取模的结果。

inputFormat: 一个整数 $T$。

outputFormat: 共 $T$ 行，第 $i(1\le i\le T)$ 行输出 $n=i$ 时的答案。


title: [CTSC2016] 时空旅行

description:
2045年，人类的技术突飞猛进，已经找到了进行时空旅行的方法。小 R 得到了一台时空旅行仪，他想用它调查不同时空中人类的发展状况。

根据平行时空理论，宇宙中存在着很多独立的时空，每个时空在下一个时间点还会分化出若干个不同的时空。宇宙是一个三维空间，人类使用空间直角坐标系来描述空间中的一个位置，三维坐标分别是 $x,y,z$。

我们假设在初始的时空（编号为 $0$）中，人类存在于地球上（地球的坐标为 $(0,0,0)$），其他的时空都是从一个现有的时空发展而来的。一个时空发生一个时间之后会发展成为另外一个时空（原来的时空不发生任何变化）。会影响小 R 的时间包括两类：

1. 人类殖民了一个新的星球，该星球的状态变成“已被殖民”。
2. 人类放弃了一个已被殖民的星球，该星球的状态变成“未被殖民”。

每次进行时空旅行时，小 R 会先选定一个时空。在这个时空中，人类已经殖民了一些星球。小 R 只要到达该时空中任意一个已被殖民的星球，就能调查人类的发展状况。

小 R 的时空旅行仪出现了一些问题，调整 $x$ 坐标的按钮坏掉了，因此到达点的 $x$ 坐标被固定了（每次旅行的 $x$ 坐标值可能不同）。与此同时，他仍能任意调整到达点的 $y$ 坐标和 $z$ 坐标。

这个问题大大增大了小 R 的花费：因为时空旅行没有花费，但在太空中航行却需要花钱；同时，在不同星球进行调查也可能会产生不同的费用。

假设小 R 将时空旅行的终点设为 $A$，他要进行调查的星球为 $B$：如果 $A$ 与 $B$ 的欧几里得距离为 $d$，那么他太空航行的花费就是 $d^2$；又如果星球 $B$上进行调查的费用为 $c$，那么小 R 此次调查的总花费就是 $d^2+c$。

现在给定小 R 每次旅行到达的时空以及时空旅行仪上固定的 $x$ 坐标值，请你计算出小 R 每次旅行完成调查的最小总花费。

inputFormat:
输入的第一行包含三个非负整数 $n,m,c_0$，$n$ 表示平行时空数量，这些平行时空的编号为 $0$ 到 $n-1$ 的整数，初始时空的编号为 $0$。$m$ 表示小 R 进行的时空旅行的次数，$c_0$ 表示在地球进行调查的花费。保证 $0< n,m \leq 5 \times 10^5, 0 \leq c_0 \leq 10^{12}$。

接下来 $n-1$ 行，依次描述平行时空 $1$ 到 $n-1$，其中第 $i$ 行分两种情况：

1. $0 \ \mathrm{fr} \ \mathrm{id} \ x \ y \ z \ c$：表示编号为 $i$ 的平行时空由编号为 $\mathrm{fr}$ 的时空发展而来，人类殖民了一个编号为 $\mathrm{id}$ 的星球，该星球的坐标为 $(x,y,z)$，在该星球进行调查的花费为 $c$。数据保证给出星球的编号不重复，且 $0< \mathrm{id} < n$；保证 $|x|,|y|,|z| \leq 10^6, 0 \leq c \leq 10^{12}$。
2. $1 \ \mathrm{fr} \ \mathrm{id} $：表示编号为 $i$ 的平行时空由编号为 $\mathrm{fr}$ 的时空发展而来，人类放弃了编号为 $\mathrm{id}$ 的星球。数据保证该星球在编号为 $\mathrm{fr}$ 的时空中处于被殖民的状态；保证 $\mathrm{id} > 0$，即地球一定不会被放弃。

上述两种情况中，各参数均为正数，相邻整数之间均用一个空格隔开；均保证 $0 \leq \mathrm{fr} < i$。保证不会出现上述两种之外的情况。

接下来 $m$ 行，每行表示小 R 进行的一次时空旅行。每行包括两个正数 $s$ 和 $x_0$，表示小 R 到编号为 $s$ 的平行时空进行了一次时空旅行，时空旅行仪上的 $x$ 坐标被固定为了 $x_0$。保证 $0\le s\lt n$，$|x_0|\le 10^6$。

outputFormat: 输出 $m$ 行，分别表示每次旅行完成调查的最小总花费。

hint:
对于前 $5\%$ 的数据，$n,~m~\leq~100$

另有 $35\%$ 的数据，$n,~m~\leq~10^5$，其中有 $15\%$ 的数据，人类不会放弃星球，另有 $10\%$ 的数据，每次旅行的 $x$ 相同。

对于剩下的数据，$n,~m~\leq~5~\times~10^5$，其中有 $10\%$ 的数据，每次旅行的 $x$ 相同，$35\%$ 的数据，时空 $i$ 由时空 $i - 1$ 发展而来。在这 $35\%$ 的数据中有 $15\%$ 的数据，人类不会放弃星球。

由于文件压缩包过大无法上传，对于每一个子任务有且仅有一个测试点，为对应分值。


title: [CTSC2016] 萨菲克斯·阿瑞

description:
小 P 来到了 NOIP2044 的赛场上，他发现第二题的题目是这样的：给你一个长度为 $n$ 的字符串，该字符串由至多 $m$ 种不同的字符组成，其中第 $i$ 种字符的出现次数不超过 $c_i$，问你这个字符串的后缀数组是什么。

聪明的小 P 想到了一个新的问题希望你来帮忙解答：在题目给定的限制下，能有多少种不同的答案。也就是所有由 $m$ 种字符组成，其中第 $i$ 种字符出现次数不超过 $c_i$，且长度为 $n$ 的字符串，共有多少种不同的后缀数组。

由于答案很大，你只用输出答案对 $10^9+7$ 取模后的数。

对于一个字符串 $s=s_1s_2...s_n$，记 $\mathrm{suf}(i)$ 表示 $i$ 这个位置到末尾的子串。后缀数组为一个 $1$ 到 $n$ 的排列 $p_1,p_2,...,p_n$，满足 $\mathrm{suf}(p_1) <  \mathrm{suf}(p_2) <  \dots  <  \mathrm{suf}(p_n)$。对于两个字符串 $s$ 和 $t$，令 $i$ 为第一个使得 $s_i \neq t_i$ 的位置，那么我们 $s_i$ 和 $t_i$ 中小的对应的字符串更小，如果 $i$ 不存在，那么长度小的字符串更小。

对于字符串之间的大小关系，我们规定第 $1$ 个字符最小，第 $2$ 个字符次小，以此类推。

inputFormat:
输入的第一行包含两个正整数 $n,m$，表示字符串的长度为 $n$，共有 $m$ 种字符。

接下来一行，包含 $m$ 个非负整数 $c_1,c_2,...,c_m$，表示每种字符最多的出现次数。保证 $0 \leq c_1,c_2,...,c_m \leq n,c_1+c_2+...+c_m \geq n$。

outputFormat: 输出共一行，包含一个正数，表示答案。

hint:
### 样例一解释

我们记 $a$ 为第一种字符，$b$ 为第二种字符，那么共有 $aab,aba,abb,baa,bab,bba$ 这六种可能的字符串。它们的后缀数组为

$$(1,2,3),(3,1,2),(1,3,2),(3,2,1),(2,3,1),(3,2,1)$$

所以共有 $5$ 种不同的结果。

### 数据范围

对于前 $5\%$ 的测试点，$n, m \leq 6$

另有 $10\%$ 的测试点，$n, m \leq 10$

另有 $20\%$ 的测试点，$n, m \leq 500$，其中有 $5\%$ 的测试点 $m = 2$，$5\%$ 的测试点 $m = 3$，$10\%$ 的测试点 $c_1 = c_2 = \cdots = c_m = n$

另有 $15\%$ 的测试点，$n,m\leq 50$

另有 $20\%$ 的测试点，$n, m \leq 200$

另有 $30\%$ 的测试点，$n, m \leq 500$


title: [CTSC2016] NOIP十合一（数据疑似有误）

background: 这是一道 **提交答案题**。

description:
在 NOIP2044 的赛场上，小 D 遇到了这样一道题：

给出一个 $n$ 个点的图，其中有 $m$ 条带边权的有向边，有 $q$ 个询问，每个询问形如从 $u$ 号点走到 $v$ 号点，长度为 $w$ 的道路数量有多少？你只需要输出答案对 $P$ 取模的结果即可。

小 D 思考了良久也不会做这道题，悻悻离场后，他从官网上取得了这道题的数据，共有 $10$ 组数据。小 D 怎么也想做出来这道题，于是他开始寻求你的帮助，将 $10$ 组数据的输入给了你。聪明的你一定可以帮小 D 计算出每组数据的输出的！

inputFormat:
输入文件 noip1.in~noip10.in 已经在下载文件中。

每个输入文件的第一行包括 $4$ 个正整数 $n,m,q,P$，表示图中点数、边数、询问数目以及模数。点的编号为从 $1$ 到 $n$ 的整数。

接下来 $m$ 行每行描述 $m$ 条带权有向边，其中第 $i$ 行包含 $3$ 个整数 $a_i,b_i,c_i$，表示第 $i$ 条边的起点为 $a_i$，终点为 $b_i$，权值为 $c_i$。

接下来 $q$ 行描述询问，其中第 $k$ 行包含 $3$ 个整数 $u_k,v_k,w_k$，表示第 $k$ 个询问需要输出从 $u_k$ 号店走到 $v_k$ 号点，长度为 $w_k$ 的道路数量对 $P$ 取模的结果。

outputFormat:
输出文件为 noip1.out~noip10.out，分别对应相应的输入文件。

每个输出文件中不超过 $q$ 行，每行包含一个小于 $P$ 的非负整数，表示该测试点前 $q$ 个询问的答案。

hint:
### 样例一解释：

对于第一组询问，一共有两条从 $1$ 号点到 $3$ 号点、长度为 $5$ 的路径。假定边的编号从 $1$ 到 $4$，则这两条路径经过的边为：

第 $1$ 条：$2 \rightarrow 4$

第 $2$ 条：$1 \rightarrow 1 \rightarrow 3$。

### 有关其他样例

在测试数据下载中提供了每个测试点对应的sampleout，分别对应每个测试点第一个询问的正确输出

### 输入数据下载

[下载链接](https://share.weiyun.com/5sk5wqh)

### 评分办法

暂无spj，按照 **传统题** 评分办法进行评测，只有你的答案与标准输出 **完全相同** 才能得到测试点的分数

### 提示

本题可能用到的知识：

**特征多项式**：对于 $n \times n$ 的矩阵 $A$，定义以 $\lambda$ 为变量的 $n$ 次多项式 $f(\lambda)=\det(\lambda I-A)$，其中 $I$ 是 $n$ 阶单位矩阵，$\det$ 是行列式。称 $f(\lambda)$ 为 $A$ 的特征多项式。

**Cayley-Hamilton 定理**：对于方阵 $A$ 的特征多项式 $f(\lambda)$，一定有 $f(A)=0$。即将矩阵本身作为变量带入特征多项式，结果为零矩阵。


title: [CTSC2016] 单调上升序列

description:
对于一个带权无向图，我们可以考察它的单调上升路径。

一条路径被称为单调上升的，如果沿着它走时的权值是单调递增的。

注意，路径由多条首尾相连的边组成，且可经过同一顶点多次。路径的长度为它包含的边数。

举例来说：下图中 $v_2 \rightarrow v_4 \rightarrow v_1 \rightarrow v_2$ 是一条单调上升路径，因为每条边的权值为 $1,2,4$。这条路径的长度为 $3$。更进一步的，你可以验证下图中所有的单调上升路径的长度都不超过 $3$。

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

下面的结论指出在某些图中总会存在一个比较长的单调上升路径：

结论：假设带权无向图 $G$ 有 $100$ 个节点 $1000$ 条边，且所有权值各不相同。那么，$G$ 中一定存在一个单调上升路径，它的长度大于等于 $20$。

证明：假设每个节点上有一个探险家。我们按权值从小到大枚举所有的边，每次将该边连接的节点中的探险家的位置进行对调。可以知道，每个探险家都走的是一条单调上升路径。另外，由于共有 $100$ 个探险家，而探险家一共走了 $2000$ 步，所以有人走了 $20$ 步。证毕。

现在，我们的问题是：

给定一个完全图 $G$，它的顶点个数为一个偶数 $N$。

你的任务是给每条边选一个不同的权值，要使得最长的单调上升路径最短。

inputFormat: 输入仅一行一个正偶数 $N$。

outputFormat:
输出整数 $1$ 到 $\frac{N(N-1)}{2}$ 的一个排列，相邻的数之间用一个空格或换行隔开。

第一个数代表你给边 $(1,2)$ 选的权值；第二个数是给 $(1,3)$ 的权值，……，第 $N$ 个数是给 $(1,N)$ 的权值；然后是 $(2,3)$ 的权值，$(2,4)$ 的权值，……，$(2,N)$ 的权值；然后是 $(3,4)$ 到 $(3,N)$ 的权值；以此类推；最后是 $(N-1,N)$ 的权值。

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

- 对于 $20\%$ 的数据，满足 $N \leq 20$;
- 对于 $50\%$ 的数据，满足 $N \leq 100$;
- 对于 $100\%$ 的数据，满足 $2 \leq N \leq 500$。

#### 说明
除不同的测试点有不同特点外，每个测试点你也可能获得部分分。如果你的程序能正确结束并按输出格式输出，我们将用下列方式评分：

假设你的图中最长单调上升路径的长度为 $A$，正确答案为 $B$。
- 如果 $A=B$，你的得分为 $10$ 分；
- 如果 $B < A < 2B$，你的得分为 $3$ 分；
- 如果 $A \geq 2B$，你的得分为 $0$ 分。


title: [CTSC2016] 香山的树

description:
众所周知，香山的红叶非常著名。然而，CTSC 举行的时间是在 5 月，而红叶的季节是秋天，所以这个季节是看不到红叶的，于是我们在 CTSC 比赛中就只能讨论香山的树了。

s-quark 很喜欢这些树，他计划在每棵树上贴一个各不相同的标签。每个标签为条形，可以在树干上绕成一圈。为了区分每一棵树，s-quark 在每个标签上印了一个由小写英文字母组成的字符串。由于树干周长的限制，标签的长度也是有限的，因此这个字符串至多只能由N个字母组成。

但是，由于标签是在树干上围成一圈的，所以当标签在树上贴好以后，就不再能找到标签的起始位置了。所以，如果两棵树上的标签循环同构，例如分别为 " abc " 和 " cab " ，那么这两棵树就不再能通过标签区分了。针对这个问题，s-quark 想了一个巧妙的办法。对于一个已经在树上贴好的标签，s-quark 规定它的起始位置必须是能够使得字符串的字典序最小的起始位，即如果看到的字符串是 " aba "，那么就可以推断出从正确的起始位置开始看到的字符串应为 " aab "。

另外，对于有些标签，例如 " abab "，尽管符合字典序最小的规则，但是这样的起始位置不唯一，s-quark 认为这种情况也是不理想的。所以，这样的标签 s-quark 也会避免使用。s-quark 已经把所有的树都编好了顺序，准备在第一棵树上贴标签 " a "，之后按照字典序给每棵树贴上不同的标签。

以 $n=3$ 为例，s-quark将依次使用这些标签来标记这些树木： $a ,~aab ,~  aac , ~\dots~, ~ aaz ,  ~ab , ~ abb , ~\dots~, ~ abz , ~ ac , \dots~$

s-quark 知道，香山上的树总共有 $K$ 棵。他想知道他将在最后一棵树上贴的标签是什么。但是，这个问题显然太简单了。现在，s-quark 要问你，如果他在第一棵树上贴的标签是字符串 $S$，那么他将在最后一棵树上贴的标签是什么呢？

inputFormat:
输入的第一行两个正整数 $N$ 和 $K$，分别为字符串的长度和树的总数。

第二行一个由小写英文字母组成的字符串 $S$，表示在第一棵树上所贴的标签。$S$ 的长度不超过 $N$，并且保证是一个合法的标签。

outputFormat: 输出仅一行，输出一个字符串 $T$，表示 s-quark 将在最后一棵树上贴的标签，或输出 $-1$，表示剩余的合法标签数量不足以贴完所有的树。


title: [CTSC2016] 科学考察队

background: 这是一道 **提交答案题**

description:
今年正是五四青年节。在这样的大好日子里，青年探险家牛牛带着他的科学考察队去考察一片原始森林。

在考察开始前，牛牛获得了这片原始森林的地图。这片森林里有 $n$ 个集结点，编号为 $1$ 到 $n$ 的整数。在这些集结点之间，存在 $m$ 条路径，编号为 $1$ 到 $m$ 的整数。每条路径以一个集合点为起点，一个集结点为终点。

为了提高科学考察的效率，牛牛将他带领的考察队分为了 $p$ 个小队，每个小队都能够独立地完成一些工作。他们约定从编号为 $S$ 的集结点出发，最终在编号为 $T$ 的集结点汇合。在考察的过程中，会遇到重重困难，比如科考队员可以从悬崖的顶端缓缓下降到悬崖底部，却不能从悬崖底部直接攀爬到悬崖顶上，因此输入的路径都是单向的。

当一个小队沿着一条路径前进后，这个小队将会记录路径上的各种信息和数据。然而有的路径需要考察队自行开辟，开辟一条路径需要耗费一定的材料，将产生一些费用。由于装备数量有限，牛牛给各小队分配的装备也可能会不同，因此，有些条件困难的路径上，有些小队会因为装备不足而无法通过。但是，牛牛通过合理地分配装备，确保了每一支小队都能顺利到达编号为 $T$ 的集结点。

在他们都到达 $T$ 点汇合后，牛牛将会汇总所有的信息与数据，这些信息与数据的总价值即为这次科学考察行动的总收益。其中，如果有多支小队通过了同一条路径，由于他们记录到的关于这条路径的数据是重复的，因此价值只会计算一次。而开辟路径所花费的费用即为这次科学考察的总支出，同样，即使有多支考察队经过同一条需要开辟的路径，这条路径也只需要开辟一次。

现在，牛牛希望为他的 $p$ 个小队设计出合理的行动路径，使得总收益减去总支出的值最大。

inputFormat:
输入文件 expedition1.in~expedition10.in 已在试题目录下。

对于每组输入数据：

第一行 $5$ 个整数，依次为 $n,m,p,S,T$，意义如题所述。

接下来 $2m$ 行，每两行描述一条路径。

每条路径的第一行三个整数 $u,v,w$，表示这条路径起点为 $u$，终点为 $v$。若 $w~<~0$，则表示这条路径上的数据价值为 $w$，且不需要开辟。若 $w \leq 0$，则表示这条路径上数据价值为 $0$，且开辟的花费为 $-w$。

每条路径的第二行第一个整数 $k$，表示不能通过这条路径的小队数量。接下来 $k$ 个互不相同的整数，表示这 $k$ 个小队的编号。

outputFormat:
输入文件 expedition1.out~expedition10.out 已在试题目录下。

对于每组输入数据，你需要依次输出 $p$ 行。第 $i$ 行表示第 $i$ 个小队的行动顺序。

每行第一个数 $k$，表示这个小队总共走过了多少条路径。接下来 $k$ 个数，表示这个小队从 $S$ 前往 $T$ 的过程中依次走过的路径编号。

hint:
### 样例一解释

地图上有 $4$ 个集结点与 $4$ 条路径，其中第 $1$ 支小队能通过的路径有 $1、2、4$，第二支小队能通过的路径有 $2、3、4$。最终 $1$ 小队依次通过 $1、4$ 路径，$2$ 小队依次通过 $2、3、4$ 路径。获取的总收益为 $3+5+1=9$。总支出为 $2$。总收入减总支出的值为 $9-2=7$。

### 评分方法

每个测试点单独评分。每个测试点你还可能获得部分分。

对于每个测试点，我们设置了 $10$ 个评分参数 $a_1,a_2,a_3,…,a_9,a_{10}$。如果选手的输出不合法，则得零分。否则，在你的方案中，若考察总收益为 $w_{user}$，且存在一个最大的 $i$, 使得 $w_{user}~\geq~a_{i}$，则你获得 $i$ 分。

所有评分参数文件 expedition1.ans~expedition10.ans 已在试题目录下。
每个评分参数文件共 $10$ 行。其中第 $i$ 行一个非负整数，表示 $a_i$。

### 输入数据下载

[下载链接](https://share.weiyun.com/52vCCzr)