title: [PA2024] Grupa permutacji

background: PA 2024 2A

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 2 [Grupa permutacji](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/gru/)**

在本题中，我们将处理 $n$ 个元素的排列。$n$ 个元素的排列是由 $1$ 到 $n$（包含两端）的 $n$ 个不同的自然数组成的序列。将排列 $a_1,a_2,\ldots,a_n$ 和排列 $b_1,b_2,\ldots,b_n$ 复合起来，会得到排列 $a_{b_1},a_{b_2},\ldots,a_{b_n}$。我们称任意满足 $i<j$ 且 $p_i>p_j$ 的数对 $(i,j)$ 为排列 $p_1,p_2,\ldots,p_n$ 的逆序对。

Bytie 是 $n$ 个元素的排列的忠实粉丝。他非常喜欢它们，并且其中有一些是他最喜欢的。他决定开始在一张纸上写下通过复合他最喜欢的排列（以任何顺序，也许多次使用其中一些排列）能得到的所有排列，并小心翼翼地保证不写出任何排列超过一次。

毫无疑问，他很快就用完了纸张。然后 Bytie 有一个问题：如果他列出所有可能的排列，它们平均会有多少个逆序对？

帮他写一个程序来计算这个值。更具体地说，输出答案对 $10^9+7$ 取模后的值（详见「输出格式」部分）。

inputFormat:
第一行包含两个整数 $n$ 和 $k\ (1\le n,k\le 3\,000)$，分别表示排列的长度和 Bytie 最喜欢的排列个数。

接下来 $k$ 行，第 $i$ 行包含 $n$ 个互不相同的整数 $a_{i,1},a_{i,2},\ldots,a_{i,n}\ (1\le a_{i,j}\le n)$，表示 Bytie 第 $i$ 个最喜欢的排列。

outputFormat:
输出一行一个整数，表示 Bytie 可能写下的所有排列中逆序对数的平均值模 $10^9+7$ 后的结果。

形式化地说，令结果为 $\frac{p}{q}$，其中 $q\neq 0$ 且 $\gcd(p,q)=1$。则输出 $p\cdot q^{-1}\pmod{10^9+7}$，其中 $q^{-1}$ 表示在 $1,2,\ldots,10^9+6$ 中唯一满足 $q\cdot q^{-1}\equiv 1\pmod{10^9+7}$ 的整数。

可以证明，对于所有满足条件的测试数据，其结果是一个有理数，其不可约形式的分母不能被 $10^9+7$ 整除。

hint:
在第一组样例中，Bytie 会写下排列 $\{1,2,3\}$（有 $0$ 个逆序对），排列 $\{2,3,1\}$（有 $2$ 个逆序对）和排列 $\{3,1,2\}$（有 $2$ 个逆序对）。因此平均逆序对个数为 $\frac{4}{3}$。且 $3^{-1}\equiv 333333336\pmod{10^9+7}$，因此答案为 $333333336\cdot 4\equiv 1333333344\equiv 333333337\pmod{10^9+7}$。

在第二组样例中，Bytie 会写下 $5$ 个元素的所有排列。容易证明它们平均有 $5$ 个逆序对。


title: [PA2024] Alchemik Bajtazar

type: P

background: PA 2024 2B

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 2 [Alchemik Bajtazar](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/alc/)**

Byteasar 是一位著名的炼金术士，为了解决材料的嬗变问题，他暂时放下了制造贤者石的尝试。具体来说，Byteasar 想把一种分子转化成另一种。Byteasar 所拥有的分子由 $n$ 个 bytonium 原子组成（在 Byteotia，bytonium 是最常用的化学元素之一，主要用于生产食品和隐形眼镜），这些原子从 $1$ 到 $n$ 编号。某些原子对之间可能存在键，但每对原子之间最多只有一个键。这些分子形成了一个连贯的整体——从每个原子出发，通过一个或多个键就可以到达其他任何原子。

Byteasar 描述了他希望得到的 $n$ 个原子的分子中的键——对于每一对原子，他都知道是否希望它们最终由键连接。目标分子满足同样的条件——它形成一个连贯的整体，每对原子最多由一个键连接。不幸的是，Byteasar 的分子可能与目标分子不同。为了解决这个问题，他可以使用自己的炼金术能力。他可以随时进行两种可能的操作之一：

- Byteasar 可以选择没有键连接的两个不同原子 $a$ 和 $b$，并在它们之间形成键。由于 bytonium 的高度不稳定性，只有当前存在与 $a$ 和 $b$ 都成键的原子 $c$（不同于 $a$ 和 $b$），他才可以这样做。
- Byteasar 可以选择通过键连接的两个不同原子 $a$ 和 $b$，并移除连接它们的键。出于类似的原因，只有当前存在与 $a$ 和 $b$ 都成键的原子 $c$（不同于 $a$ 和 $b$），他才可以这样做。

Byteasar 不想在转化上花费太多时间。请编写一个程序，帮助他将自己的分子转化为目标分子，并在最多 $200\, 000$ 次操作中完成。

注意：原子两两不同，可以区分。

inputFormat:
第一行一个整数 $n\ (2\le n\le 30\,000)$，表示 Byteasar 拥有的分子和目标分子中原子的个数。

第二行一个整数 $m_s\ (n-1 \le m_s \le 50\, 000)$，表示 Byteasar 拥有的分子中的键数。

接下来 $m_s$ 行，每行两个整数。其中第 $i$ 行的整数 $a_i$ 和 $b_i\ (1 \le a_i , b_i \le n, a_i \neq b_i)$ 表示通过键连接的原子编号。可以保证 Byteasar 的分子是一个连贯的整体，并且每两个原子最多只通过一个键相连。

接下来一行一个整数 $m_d\ (n-1\le m_d\le 50\,000)$，表示目标分子中的键数。

接下来 $m_d$ 行包含对这些键的描述，格式与目前已拥有的分子相同。

outputFormat:
输出第一行包含总操作数 $r$。必须保证 $0\le r\le 200\,000$。

接下来每行包含对操作的描述。 如果你想在第 $i$ 次移动中连接原子 $x_i$ 和 $y_i$，第 $i$ 行应该以 `+` 号开头，在一个空格之后输出编号 $x_i$ 和 $y_i$，也用一个空格分隔。 相反，如果想删除连接 $x_i$ 和 $y_i$ 原子的键，则该行应以 `-` 开头，然后类似地，输出编号 $x_i$ 和 $y_i$。

输出的操作序列必须满足题目描述中给出的条件——当选择原子 $x_i$ 和 $y_i$ 时，必须有另一个原子与它们连接。执行一系列动作后，最终的分子必须与目标分子相同，即对于每对原子 $i, j\ (1 \le i < j \le n)$，如果编号为 $i$ 和 $j$ 的原子在目标分子中被一条键连接，最终状态中这对原子也应该被一条键连接。

注意，你不必最小化移动次数，你只需要最多进行 $200\,000$ 次操作即可。可以证明，总可以进行不超过 $200\,000$ 次操作来实现转化。

hint: 请注意，Byteasar 无法立即连接第一个原子与第四个原子，因为当时没有原子与它们两个相连。通过在第一个和第三个原子之间建立临时键，Byteasar 就使该原子成为了第三个原子。


title: [PA2024] Znaczki pocztowe

background: PA 2024 2C

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 2 [Znaczki pocztowe](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/zna/)**

Byteasar 曾经收集了大量邮票。然而，他对邮票的兴趣已不如年轻时，因此他决定将自己的邮集赠送给更年轻的集邮爱好者。不过，他希望尽可能公平地完成这项工作，为此他需要你的帮助。

Bytesar 的邮集由 $n$ 张邮票组成，其中第 $i$ 张来自城市 $a_i$。为简单起见，我们用整数表示这些城市。Byteasar 打算在报纸上刊登一则公告，宣布他计划赠送自己的收藏的邮票。如果有 $k$ 个人愿意接收，他将在如下条件下向每个人赠送一个邮票的子集：每个人都必须收到相同的邮票多重集。这就意味着，对于每两个申请人和每个城市，两个申请人都必须从该城市获得相同数量的邮票。特别地，这可能意味着 Byteasar 将不发放任何邮票。

Byteasar 不知道会有多少人前来接收。因此，对于 $1$ 到 $n$ 范围内的每个数 $k$，你需要找出如果有 $k$ 个人愿意接收，Byteasar 最多可以分发多少张邮票。

inputFormat:
第一行一个整数 $n\ (1\le n\le 300\,000)$，表示 Byteasar 收藏的邮票数量。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (1\le a_i\le 10^9)$，表示 Byteasar 的邮票所来自城市的编号。

outputFormat: 输出一行 $n$ 个整数，第 $k$ 个整数表示如果有 $k$ 个人愿意接收 Byteasar 的邮票，Byteasar 最多能分发多少张邮票。

hint:
如果有一个人愿意接收，Byteasar 可以把所有邮票都给他。

如果有两个人，Byteasar 可以给他们每人两张 $1$ 号城镇的邮票、一张 $42$ 号城镇的邮票和一张 $777$ 号城镇的邮票，即总共 $8$ 张邮票。

如果有四个人，Byteasar 可以给他们每人一张 $1$ 号城市的邮票。

如果愿意接收的人数超过四人，Byteasar 将无法送出任何邮票。


title: [PA2024] Splatanie ciągów

background: PA 2024 3A

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 3 [Splatanie ciągów](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/spl/)，感谢 Macaronlin 提供翻译**

定义一个数组的稳定性是最长严格单调递增或递减的连续子区间的长度。如数组 $[8,6,1,3,5,7,4,2]$ 的稳定性为 $4$，因为有一个连续递增子区间 $[1,3,5,7]$，并且没有比其更长的严格单调的连续子区间了。

定义 $A\ \text{i}\ B$ 是 $A$ 和 $B$ 按某个方式归并形成的新数组（即新数组可以划分为两个不交叉子序列，且分别是 $A$ 和 $B$），如 $A=[1,2,3],B=[4,5]$，则 $A\ \text{i}\ B$ 可以是 $ [1, 4, 2, 5, 3], [4, 5, 1, 2, 3]$ 或者 $[4, 1, 5, 2, 3]$，但不可能是 $[1,2,3,4,3]$ 或 $[1,2,3,5,4]$。

令 $f(A,B)$ 表示 $A\ \text{i}\ B$ 的最小稳定性。

给你一个长度为 $n$ 的数组 $A$ 和长度为 $m$ 的数组 $B$。令 $A'$ 是 $A$ 的非空子区间，$B'$ 是 $B$ 的非空子区间。对于所有在区间 $[1,n+m]$ 的整数 $x$，求有多少对 $(A',B')$ 满足 $f(A', B')=x$。答案对 $10^9+7$ 取模。

inputFormat:
第一行两个整数 $n$ 和 $m\ (1\le n,m\le 300\,000)$，分别表示 $A$ 数组和 $B$ 数组的长度。

第二行 $n$ 个整数 $A_1,A_2,\ldots,A_n\ (1\le A_i\le n+m)$，表示 $A$ 数组。

第三行 $m$ 个整数 $B_1,B_2,\ldots,B_m\ (1\le B_i\le n+m)$，表示 $B$ 数组。

保证 $A$ 数组和 $B$ 数组中所有整数两两不同。也就是说 $A\ \text{i}\ B$ 一定是 $1$ 到 $n+m$ 的整数的一个排列。

outputFormat: 输出一行 $n+m$ 个整数，第 $i$ 个整数表示 满足 $f(A', B')=i$ 的 $(A',B')$ 对数，对 $10^9+7$ 取模。


title: [PA2024] Żelki

background: PA 2024 3B

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 3 [Żelki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/zel/)，感谢 Macaronlin 提供翻译**

共有 $n$ 种糖豆，有 $k$ 种颜色，第 $i$ 种糖豆颜色是 $k_i$，重量是 $m_i$，价格 $c_i$。现在要去购买糖豆，购买的糖豆需要包含所有 $k$ 种颜色，且每种颜色购买的数量相同。

问对于在区间 $[0,m-1]$ 的每个整数 $r$，满足购买的糖豆总重量对 $m$ 取模为 $r$ 的购买方案中最小花费是多少？如果不存在满足条件的购买方案，则输出 $-1$。

inputFormat:
第一行三个整数 $n,k$ 和 $m\ (1\le n,k,m\le 7\,000)$，分别表示糖豆种类数，颜色数和参数。

接下来 $n$ 行，每行三个整数 $k_i,m_i$ 和 $c_i\ (1\le k_i\le k,1\le m_i\le m,1\le c_i\le 10^9)$，分别表示第 $i$ 种糖豆的颜色，重量和价格。

outputFormat: 输出 $m$ 行，第 $i$ 行表示满足购买的所有糖豆总重量对 $m$ 取模为 $i-1$ 的情况中花费的最小值。如果不存在这样的情况，输出 $-1$。

hint:
在第一组样例中：

- 为了使糖豆的总重量能被 $m = 6$ 整除，可以不买任何糖豆，这样就不用花钱了。
- 为了使糖豆的总重量除以 $6$ 的余数为 $1$，应购买一颗第一种糖豆，两颗第二种糖豆，一颗第三种糖豆。这样花费为 $10$，得到两种颜色各两颗的糖豆，总重量等于 $7$。
- 为了使糖豆总重量除以 $6$ 的余数等于 $5$，应该买两颗第一种糖豆、三颗第二种糖豆和一颗第三种糖豆。

第二个样例中没有第二种颜色的糖豆，所以唯一可行的方案是不买任何糖豆。


title: [PA2024] Obrazy

background: PA 2024 3C

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 3 [Obrazy](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/obr/)，感谢 Macaronlin 提供翻译**

给定尺寸为 $h\times w$ 的矩形墙面，以及 $n$ 种尺寸的正方形画框，每种尺寸画框都有无穷多个。对于任意两种不同尺寸的画框，其中一个尺寸的边长总能整除另一个尺寸的边长。

现用这些画框完全覆盖墙面，而且画框之间不能重叠，只能边缘相接，请求出最少需要购买多少个画框？如果不可能完全覆盖墙面，则程序应输出 $-1$。

inputFormat:
第一行两个整数 $h$ 和 $w\ (1\le h,w\le 10^9)$，表示墙面大小。

第二行一个整数 $n\ (1\le n\le 30)$，表示画框个数。

第三行 $n$ 个整数 $d_1,d_2,\ldots,d_n\ (1\le d_i\le 10^9,d_i<d_{i+1})$，表示每个正方形画框的大小，保证 $d_{i+1}$ 能被 $d_i$ 整除。

outputFormat: 输出一行一个整数，如果可以完全覆盖墙面，输出最少要购买多少画框，否则输出 $-1$。

hint:
在第一个样例中，Byteasar 可以用九个画框（六个 $1\times 1$、两个 $3\times 3$ 和一个 $6\times 6$）覆盖一面墙，具体如下：

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

在第二个样例中，无法完全覆盖墙面。


title: [PA2024] Kolorowy las

background: PA 2024 4A

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 4 [Kolorowy las](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/kol/)，感谢 Macaronlin 提供翻译**

给定 $n$ 个点的森林（无向无环图），点从 $1$ 到 $n$ 编号，有正整数边权，每个点有颜色，初始所有点颜色为 $0$。

有 $4$ 种共 $q$ 个操作：

- $1\ a_i\ b_i\ d_i$：在 $a_i$ 和 $b_i$ 之间添加一条边权为 $d_i$ 的边（保证添加之后图中仍无环）；
- $2\ a_i\ b_i$：删除 $a_i$ 和 $b_i$ 之间的边；
- $3\ v_i\ z_i\ k_i$：把所有可以到达 $v_i$ 且到 $v_i$ 的距离小于等于 $z_i$ 的顶点染色为 $k_i$；
- $4\ u_i$：查询点 $u_i$ 的颜色。

inputFormat:
第一行三个整数 $n,m,q\ (2\le n\le 200\,000,0\le m\le n-1,1\le q\le 200\,000)$，分别表示点数，边数和操作数。

接下来 $m$ 行，每行三个整数 $a_i,b_i,d_i\ (1\le a_i,b_i\le n,1\le d_i\le 10^9)$，表示点 $a_i$ 和 $b_i$ 之间有一条长度为 $d_i$ 的边。

接下来 $q$ 行描述操作，格式如题目描述。保证 $1\le a_i,b_i,v_i,u_i\le n$，$1\le d_i\le 10^9$，$0\le z_i\le 10^{15}$，$1\le k_i\le 10^9$。

保证给定的 $m$ 条边形成一个合法的森林，图在经过修改后仍然形成一个合法的森林，并且保证不会删除图中不存在的边。

此外，还保证至少存在一个操作 $4$。

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

hint:
- 在某些子任务中，不存在操作 $1$ 和 $2$，且 $m=n-1$；
- 在某些子任务中，操作 $3$ 中均有 $z_i=10^{15}$。

对于上述每种附加限制，都至少有一个子任务能满足。满足两种附加限制的子任务集合可能相交，也可能不相交。


title: [PA2024] Desant 3

background: PA 2024 4B

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 4 [Desant 3](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/des/)，感谢 Macaronlin 提供翻译**

$n$ 个士兵，从左到右编号为 $1$ 到 $n$。每个士兵有两种状态：准备好和未准备好。现对这些士兵下发 $m$ 条命令，第 $i$ 条命令会使得在 $a_i$ 位置和 $b_i$ 位置的士兵交换位置，但只有 $a_i$ 位置的士兵准备好并且 $b_i$ 位置的士兵没有准备好时才能交换，否则无效。

问对于 $1$ 到 $n$ 中的每个整数 $k$，考虑 $\binom{n}{k}$ 种士兵的初始准备情况，其中有 $k$ 个士兵已准备好，求有多少种准备情况可以在进行 $m$ 条命令后，满足所有准备好的士兵形成一段连续区间。你只需要输出种类数对 $2$ 取模后的值即可。

inputFormat:
第一行两个整数 $n$ 和 $m\ (2\le n\le 35,1\le m\le 1\,000)$，分别表示士兵数和命令数。

接下来 $m$ 行，每行两个整数 $a_i$ 和 $b_i\ (1\le a_i,b_i\le n,a_i\neq b_i)$，描述一条命令。

outputFormat: 输出一行 $n$ 个整数，其中第 $k$ 个整数表示有 $k$ 个士兵准备好的所有初始情况中，可以在进行 $m$ 条命令后使得所有准备好的士兵形成一段连续区间的情况数。输出对 $2$ 取模。

hint:
如果一开始只有一名士兵准备好，那么无论如何操作，最终准备好的士兵一定形成一个连续的区间。

考虑这样一种情况：除了队列中的第二名士兵外，其他士兵都已准备好。第一个命令不会影响士兵的位置。第二道命令下达后，由于队列中的第一名士兵已准备好，而第二名士兵尚未准备好，他们将交换位置。第三道命令同样没有影响。由于现在队列中的第一名士兵还没有准备好，而队列中的第四名士兵已经准备好，因此他们不会因为最后一道命令而交换位置。最终只有排在第一位的士兵没有准备好。这是 $k = 3$ 时唯一一种满足条件的初始情况。

未取模前的答案为 $[4,0,1,1]$。


title: [PA2024] Łamigłówka 3

background: PA 2024 4C

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 4 [Łamigłówka 3](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/lam/)**

Bytie 喜欢玩手机游戏。然而让他感到恼火的是游戏中经常有其他游戏的广告，并且其中玩游戏的人表现得非常糟糕，广告这样做的目的是让看广告的人感到沮丧，从而产生玩下去的欲望。Bytie 对其中一个广告印象尤为深刻（你可能也看过）。

![lam1.png](https://img.loj.ac.cn/2024/03/24/d2a22d1aa2488.png)

由于可以从任何事物中汲取灵感，Bytie 决定在上述游戏的基础上出道题。他将选择一块大小为 $n\times m$ 的目标图案，游戏在一块 $n\times m$ 的网格上进行，其中没有任何区域被染色。在一次操作中，他可以选择一行或一列，并将这一行（或列）中的**所有方格**（注意，这比上面图片中的游戏更自由，因为在上面的游戏中，重复涂色同一单元格时颜色会混合）重新涂成自己选择的颜色。为了使题目更形式化，他还用大写英文字母标注了所有颜色。你能帮他写一个程序，对于他给出的每个网格，给出正确得到目标图案的操作顺序吗？你可以假设输入中最多可以用 $n+m$ 步操作得到目标图案。

inputFormat:
第一行两个整数 $n$ 和 $m\ (1\le n,m\le 2\,000)$，分别表示网格的行数和列数。

接下来 $n$ 行，每行一个长为 $m$ 的字符串。字符串由大写字母组成，第 $i$ 个字符串的第 $j$ 个字符表示目标图案中第 $i$ 行第 $j$ 列单元格的颜色。

保证给定的目标图案可以通过最多 $n+m$ 次染色操作得到。

outputFormat:
输出第一行包含一个整数 $r\ (1\le r\le n+m)$，表示要进行的操作次数。接下来 $r$ 行描述操作。

为了描述一次操作，首先应输出 `R` 或者 `K`，表示你希望对某行还是某列重新涂色（`R` 表示对某行重新涂色，`K` 表示对某列重新涂色）。接下来空一格，输出你希望重新涂色的行或列的编号，行按从上到下的顺序从 $1$ 到 $n$ 编号，列按从左到右的顺序从 $1$ 到 $m$ 编号。然后再空一格，输出一个大写英文字母，表示你希望对这行或这列重新涂成的颜色。

注意你不需要最小化操作次数——只需要最多操作 $n+m$ 次即可。

samples:
10
R 1 Z
K 4 A
K 2 P
R 5 P
R 4 A
R 3 A
R 1 A
K 5 A
K 3 P
K 1 A

hint:
假设 `P` 代表绿色，`A` 代表黄色，`Z` 代表蓝色。样例 1 中的操作序列如下图所示：

![lam2.png](https://img.loj.ac.cn/2024/03/24/7f9371fee9091.png)


title: [PA2024] Autostrada 2

background:
PA 2024 5A1
（缺 SPJ）

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Autostrada 2](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/aut/)**

经过多年毫无意义的战争之后，Byteotia 和 Bitotia 终于签署了和平条约。作为最终协议的标志，两国首府之间修建了一条高速公路。而你则被任命为这条高速公路从 Byteotia 到 Bitotia 方向的管理者（至于从 Bitotia 到 Byteotia 方向，你并不感兴趣，它由~~不~~友好国家的管理者管理）。

高速公路上目前有 $m$ 个收费站，编号为 $1$ 到 $m$。在一天的不同时段，通过某个收费站的费用会有所不同。一天分为 $n$ 个小时，编号为 $1$ 到 $n$。目前，在第 $i$ 个小时通过第 $j$ 个收费站的花费为 $c_{i,j}$ bytealerts。其中一些成本可能为 $0$（此时收费站免费），甚至为负（此时司机通过收费站会获得 $-c_{i,j}$ bytealerts）。

整条高速公路很短，一小时就能走完。当然，你也不必如此匆忙，你可以在行驶过程中随意停车。不过，你不能在高速公路上过夜，必须在当天通过所有收费站。

当然，司机希望以尽可能低的花费通过高速公路。对于 $1 \le i \le j \le n$，我们用 $f(i,j)$ 表示司机在第 $i$ 小时通过第一个收费站，并在第 $j$ 小时通过最后一个收费站的情况下，通过整条高速公路的最小可能花费。所有 $f(i,j)$ 都是被两国政府的和平条约提前设置好的，作为高速公路管理者你不能更改他们。

但是，只要保证保留第一个和最后一个收费站，$f(i, j)$ 的值保持不变，并且设置的所有费用都是 $1$ bytealert 的整数倍的情况下，你可以自由修改通过各个收费站的花费，甚至取消某些收费站。

为了最小化高速公路维护的费用，你希望取消尽可能多的收费站。确定为了满足条约内容，最少需要保留多少收费站。

收费计划重组项目将分为两个阶段。在第一阶段，即初步设计阶段，只需找到最佳的收费站数量即可。但在第二阶段，即项目实施阶段，你还需要提供一份完整的收费站价格表计划。

inputFormat:
第一行三个整数 $n,m,q\ (2\le n,m\le 30\,000,n\cdot m\le 300\,000,q\in \{0,1\})$，分别表示一天中的小时数，收费站数和描述项目阶段的一位。$q=0$ 表示项目处于第一阶段（初步设计），$q=1$ 表示项目处于第二阶段（实施阶段）。

接下来 $n$ 行描述目前的收费情况，第 $i$ 行包含 $m$ 个整数 $c_{i,1},c_{i,2},\ldots,c_{i,m}\ (-10^6\le c_{i,j}\le 10^6)$，意义如题目描述。

outputFormat:
第一行输出一个整数 $k\ (2\le k\le m)$，表示最少需要保留多少收费站，才能满足没有 $f(i,j)$ 改变。如果 $q=0$，输出仅包含这一行一个整数。

如果 $q=1$，接下来 $n$ 行输出满足题目条件的最优价格计划。第 $i$ 行包含 $k$ 个整数 $d_{i,1},d_{i,2},\ldots,d_{i,k}\ (-10^{12}\le d_{i,j}\le 10^{12})$。$d_{i,j}$ 表示在第 $i$ 小时通过第 $j$ 个收费站的新花费。

可以从题目限制知道，总可以确定一个绝对值不超过 $10^{12}$ 且花费均为整数的计划。


title: [PA2024] Monety

background: PA 2024 5A2

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Monety](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/mon/)**

Natalia 和 Cezary 喜欢玩游戏，尤其是他们自己发明的游戏。他们决定在自己面前放置一些堆硬币，硬币从上到下排成类似栈的样子，每堆有 $m$ 枚硬币，每枚硬币要么是蓝色的，要么是红色的。轮到 Natalia 时，她可以选择一枚蓝色硬币，并将其连同其上方的所有硬币一起从硬币堆中移除。同样，在轮到 Cezary 时，他可以选择一枚红色硬币，并将其连同其上方的所有硬币一起从硬币堆中移除。 玩家将轮流操作，不能采取合法操作的玩家就输了——也就是说，当一位玩家操作的所有硬币都已被移除时。

现在他们知道了规则，他们必须确定游戏的初始状态——$d$ 堆硬币，每堆恰好包含 $m$ 个硬币。Natalia 和 Cezary 都不希望拥有不公平的优势，因此他们一致认为硬币的顺序应该是公平的。假设 Natalia 和 Cezary 都采取最优策略，后手赢得游戏，则称初始状态是公平的。因此，如果 Natalia 先手，则采用最优策略的 Cezary 将获胜，反之亦然：如果 Cezary 先手，Natalia 将获胜。

两人已经摆好了前 $k$ 堆 $m$ 个硬币。现在他们正在思考如何完成这一系列硬币堆。他们已经得出结论，游戏中拥有超过 $n$ 堆硬币是没有意义的。

帮助他们，对于区间 $[k, n]$ 中的每个整数 $d$，告诉他们有多少种不同的由 $d$ 堆 $m$ 枚硬币组成的公平初始状态，这些初始状态从他们已经摆好的硬币堆开始。如果存在 $i\in [1, d]$ 和 $j\in [1, m]$，当第 $i$ 堆中的第 $j$ 个硬币在一种排列方式中为蓝色，在另一种为红色，则认为这两个初始排列方式是不同的。

由于答案可能很大，输出答案对 $10^9+7$ 取模后的值即可。

inputFormat:
第一行三个整数 $n,m$ 和 $k\ (1\le n\le 32,1\le m\le 24,0\le k\le n)$，分别表示硬币堆的最大值，每堆中硬币个数和已经摆好的硬币堆数。

接下来 $k$ 行描述已经摆好的硬币堆，第 $i$ 行包含一个仅由 `N` 和 `C` 组成且长度为 $m$ 的字符串，表示从底部起第 $i$ 堆硬币的摆放方式。如果第 $j$ 个字符为 `N`，则第 $i$ 堆硬币自底向上数第 $j$ 个硬币为蓝色，否则，这个字符为 `C`，表示硬币为红色。

outputFormat: 输出一行 $n-k+1$ 个整数，第 $i$ 个整数表示再摆 $i-1$ 堆硬币，以满足最终摆放方式是公平的最终摆放方式数。输出对 $10^9+7$ 取模。

hint:
对于第一组样例，如果我们不添加任何硬币堆，则最初局面不是公平的。然而，我们可以加一堆排列为 `NNC` 的硬币——这样两堆硬币的初始状态就是公平的了。我们可以以三种方式添加两堆硬币：`[CCN, NNN]`，`[NNN, CCN]` 和 `[NCN, NCN]`。

**数据范围与提示**

- 在某些子任务中，满足 $k=n$。
- 在某些子任务中，满足 $n\le 8,m\le 8$。
- 在某些子任务中，满足 $n\le 12,m\le 13$。
- 在某些子任务中，满足 $n\le 16,m\le 19$。

上述每个子任务至少描述了之前子任务中没有出现的一组。


title: [PA2024] Kraniki

background: PA 2024 5B2

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Kraniki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/kra/)**

*Radek and Friends* 公司的负责人 Radek 试图淹没竞争对手 *Mati and Company* 公司的所有货架。为了进行完美的破坏，他让他的朋友，水管工 Janusz 在每个架子都上安装了小水龙头。

为简单起见，*Mati and Company* 公司中的货架可以用平面上的线段来表示。每个货架都是一对点 $(l_i,h_i)$ 和 $(r_i,h_i)$ 之间的线段。水管工安装的水龙头是坐标为 $(\frac{l_i+r_i}{2}, h_i + 0.5)$ 的点。这个房间的地面用 $OX$ 轴表示。

只要打开第 $i$ 个货架上方的水龙头，该货架就会被水淹没。之后水会自然开始从货架的两端垂直向下滴落，并有可能淹没更多的货架，或自然滴落到地面上。

![kra.png](https://img.loj.ac.cn/2024/03/26/cb8c5a3492932.png)

在第二组样例中，当打开一个水龙头时，水流的可视化效果.

Radek 会按某个确定的顺序看水龙头的情况。当他看到第 $i$ 个水龙头时，当且仅当第 $i$ 个货架没被水淹，他才会打开这个水龙头。

Radek 还没确定他看水龙头的顺序。它会从 $n!$ 种顺序中均匀随机选择一种。Radek 想知道他平均会打开多少个水龙头。

你的任务是回答 Radek 的问题，给出答案对 $10^9+7$ 取模后的值。形式化地，令答案为 $\frac{p}{q}$，其中 $q\neq 0$ 且 $\gcd(p,q)=1$。你需要输出 $p\cdot q^{-1}\pmod{10^9+7}$，其中 $q^{-1}$ 是集合 $1,2,\ldots,10^9+6$ 中唯一满足 $q\cdot q^{-1}\equiv 1\pmod{10^9+7}$ 的整数。

可以证明对于所有满足题目条件的数据，结果是可测的，不可约形式的分母不会被 $10^9+7$ 整除。

inputFormat:
第一行一个整数 $n\ (1\le n\le 500\,000)$，表示 Mati 公司的货架数。

接下来 $n$ 行，第 $i$ 行有两个整数 $l_i,r_i\ (1\le l_i<r_i\le 2\cdot n)$，表示第 $i$ 个货架。为了简单，我们假设 $h_i=i$。

你可以假设所有 $l_i,r_i$ 两两不同——整数 $l_i,r_i$ 形成了一个 $1$ 到 $2\cdot n$ 的排列。

outputFormat: 输出一行一个整数，表示 Radek 平均需要打开多少水龙头。答案对 $10^9+7$ 取模后输出。

hint:
**样例解释 1**

让我们考虑在第一个样例中 Radek 看水龙头的所有顺序：

- 按 $1,2,3$ 的顺序，他会打开所有 $3$ 个水龙头。
- 按 $1,3,2$ 的顺序，他会先打开水龙头 $1$ 和 $3$。当他准备打开水龙头 $2$ 时，水已经淹了第 $2$ 个货架，所以他不需要打开水龙头 $2$ 了。
- 按 $2,1,3$ 的顺序，他会打开所有 $3$ 个水龙头。
- 按 $2,3,1$ 的顺序，他会先打开水龙头 $2$ 和 $3$。当他准备打开水龙头 $1$ 时，水已经淹了第 $1$ 个货架，所以他不需要打开水龙头 $1$ 了。
- 按 $3,1,2$ 或 $3,2,1$ 的顺序，由于打开水龙头 $3$ 后，所有货架都会被淹，因此就不需要再打开剩下的两个水龙头了。

Radek 平均需要打开 $\frac{1}{6}\cdot(3+2+3+2+1+1)=2$ 个水龙头。

**样例解释 2**

第二组样例中 Radek 瓶颈要打开 $\frac{91}{30}$ 个水龙头，由于 $30^{-1}\equiv 233333335\pmod{10^9+7}$，所以输出 $91\cdot 233333335\equiv 21233333485\equiv 233333338\pmod{10^9+7}$。


title: [PA2024] Bardzo Ulubiony Ciąg

background: PA 2024 5C1

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Bardzo Ulubiony Ciąg](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/buc/)，感谢 Macaronlin 提供翻译**

给定长度为 $n$ 的整数数组 $a$，$a$ 的所有子区间和形成长度为 $\frac{n(n+1)}{2}$ 的数组 $b$，子区间和按区间开始下标的递增顺序排列，如果区间开始下标相同，则按区间结束递增顺序排列。

对于新形成的数组 $b$，求满足 $b_i+b_j+b_k=0\ (i<j<k)$ 的 $(i,j,k)$ 对数。

inputFormat:
第一行一个整数 $n\ (1\le n\le 500)$，表示数组 $a$ 的长度。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (|a_i|\le 20\,000)$，表示数组 $a$。

outputFormat: 一行一个整数，表示数组 $b$ 中满足 $b_i+b_j+b_k=0\ (i<j<k)$ 的 $(i,j,k)$ 对数。


title: [PA2024] Żarówki

background: PA 2024 5C2

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Żarówki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/zar/)，感谢 Macaronlin 提供翻译**

有 $n$ 个灯泡，每个灯泡有两种状态：开和关，初始状态是给定的。有 $m$ 个开关，每个开关控制两个灯泡，按下开关可以使这两个灯泡变为与目前状态相反的状态，只有在两个灯泡有相同状态时才起作用，否则不起作用。

你可以随意安排开关的使用顺序和使用次数，问利用这些开关可以实现多少种配置方案。灯泡在一种配置中打开而在另一种配置中关闭，则两种配置被视为不同。

inputFormat:
第一行两个整数 $n$ 和 $m\ (1\le n\le 200\,000,0\le m\le 400\,000)$，表示灯泡和开关的个数。

第二行 $n$ 个整数 $c_i\ (c_i\in \{0,1\})$，如果 $c_i=1$，则初始时第 $i$ 个灯泡是打开的，如果 $c_i=0$，则初始时第 $i$ 个灯泡是关闭的。

接下来 $m$ 行，每行两个整数 $a_i,b_i\ (1\le a_i,b_i\le n,a_i\neq b_i)$，描述一个开关。

保证开关会影响不同的无序灯泡对。形式化地，$\forall i,j \in \{1,2,\ldots,m\},i\neq j$，都有 $(a_i,b_i)\neq (a_j,b_j)$ 且 $(a_i,b_i)\neq (b_j,a_j)$。

outputFormat: 输出一行一个整数，表示利用这些开关可以实现多少种配置方案。输出对 $10^9+7$ 取模。


title: 『STA - R6』inkar-usi

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

（题目背景图片来自 Arcaea 曲绘，如有侵权，请告知出题人。）

description:
给一个 $n\times m$ 的字符矩阵，有些位置有障碍（记为字符 `#`），需要在矩阵上找出一条起始点任意的路径（可以重复经过某个格子），使得字典序最大。

可以证明答案一定是有限的或者是由某个长度有限的字符串 $S$ 不断重复得到的。如果答案是有限的，直接输出之；如果答案是无限的，只需输出它的最短循环节。

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

后 $n$ 行，每行一个长度为 $m$ 的字符串，描述矩阵的第 $n$ 行。

outputFormat: 一行一个字符串，表示答案。

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

数据范围：
- Subtask 1 (20pts)：字符矩阵中除了障碍就是字母 `A`。
- Subtask 2 (30pts)：$n,m\le 3$。
- Subtask 3 (50pts)：无特殊限制。

对于全部数据，$1\le n,m\le 10^3$，所有非障碍字符都是大写字母，矩阵至少有一个非障碍格。


title: [语言月赛 202404] 游乐场

type: B

description:
小明喜欢去游乐场玩，他尤其喜欢旋转木马。**每次**乘坐旋转木马，都需要花费 $8$ 元。每次去游乐场，可能会乘坐多次旋转木马。

妈妈每天会给小明 $1$ 元零花钱。第 $0$ 天时，小明没有零花钱。当小明手里的零花钱达到了 $50$ 元，妈妈将不再给他零花钱。

妈妈计划带小明去游乐场 $n$ 次，分别在第 $a_1,a_2,\cdots,a_n$ 天。一天可以去多次游乐场，因此 $a_i$ 可能相同。每次去游乐场，他会把手上的零花钱全部用来乘坐旋转木马，直到零花钱不足 $8$ 元。

请问，小明去完 $n$ 次游乐场后，他一共乘坐了几次旋转木马？

inputFormat:
第一行包含一个整数 $n$，表示计划去游乐场的次数。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示小明去游乐场的日期。

数据保证 $a_1 \le a_2\le \cdots \le a_n$。

outputFormat: 输出一行一个整数，表示小明乘坐旋转木马的次数。

hint:
### 样例解释

- 最开始时（第 $0$ 天），小明手上没有钱。
- 第 $1$ 天时，小明手上有 $1$ 元。他去了游乐场，但钱不够乘坐旋转木马。
- 第 $17$ 天时，小明手上有 $17$ 元。他去游乐场可以玩 $2$ 次旋转木马。还剩 $1$ 元。
- 第 $70$ 天时，小明手上有 $50$ 元（其实到第 $66$ 天，他就攒了 $50$ 元，但接下来这几天，妈妈就不给他零花钱了）。他去游乐场可以玩 $6$ 次旋转木马。还剩 $2$ 元。
- 第 $75$ 天时，小明手上有 $7$ 元。他去了游乐场，但钱不够玩旋转木马。
- 第 $79$ 天时，小明手上有 $11$ 元。他去游乐场可以玩 $1$ 次旋转木马。还剩 $3$ 元。

他一共玩了 $9$ 次旋转木马。

### 数据规模与约定

- 对于 $40\%$ 的测试数据，$n\le 10$，$a_i\le 50$；
- 对于 $70\%$ 的测试数据，$n\le 100$，$a_i\le 500$；
- 对于 $100\%$ 的测试数据，$1 \leq n\le 10^5$，$1 \leq a_i\le 10^9$。


title: 「LAOI-6」Radiation

background: [English statement](https://www.luogu.com.cn/problem/T503655). You must submit your code at the Chinese version of the statement.

description:
小 T 和 小 U 在一个 $n \times m$ 的初始为空的棋盘上玩游戏。小 T 先在上面摆 $k$ 个石头，然后小 U 会使用宇宙射线毁掉所有石头。但是小 U 的宇宙射线威力有限，只能每次销毁一行或一列的石头。

小 U 不想过多用他的宇宙射线发射器，所以他会按照最优策略销毁石头。反之，小 T 偏偏想让小 U 发射最多的宇宙射线，所以他会摆放石头以做到这一点。问题来了：小 T 不会摆放了。你能够找到一种方法帮助小 T 达到目标吗？

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

第一行一个整数 $T$。

然后 $T$ 行，每行 $n,m,k$ 三个整数，表示这组数据的游戏设定。

outputFormat:
对于每组数据，输出 $n$ 行 $m$ 列共 $nm$ 个字符，第 $i$ 行第 $j$ 个字符如果为 `S` 那么代表棋盘的第 $i$ 行第 $j$ 列有石头；如果为 `.` 那么代表棋盘的第 $i$ 行第 $j$ 列没石头。

你需要保证每组数据中输出的字符 `S` 的个数为 $k$。

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

子任务 1（$20$ 分）：保证 $k \leq \min(n,m)$。

子任务 2（$12$ 分）：保证 $n = 2$。

子任务 3（$18$ 分）：保证 $T,n,m \leq 10$。

子任务 4（$20$ 分）：保证 $T \leq 10$，$n,m \leq 300$。依赖子任务 $3$。

子任务 5（$30$ 分）：无特殊限制。依赖子任务 $1 \sim 4$。

对于所有数据，保证 $1 \leq T \leq 10^4$，$1 \leq n,m \leq 2 \times 10^3$，$0 \leq k \leq nm$，$\sum nm \leq 5 \times 10^6$。


title: [语言月赛 202404] 天上的气球

description:
现在有一块很大的草原，这个草原分成了 $n$ 行 $m$ 列。
在这块草原的天空中，飘着 $k$ 个气球。第 $i$ 个气球，位置在第 $x_i$ 行第 $y_i$ 列上空，距离地面高度 $h_i$，气球的颜色为 $c_i$。

从一个位置向上看，只能看到这个位置正上方的，距离地面最近的气球。小明想知道，从每个位置向上看，能看到的气球的颜色分别是什么。如果这个位置上空没有气球，则输出 $0$。

inputFormat:
第一行，包括三个整数 $n,m,k$，表示草原大小为 $n$ 行 $m$ 列，天空中有 $k$ 个气球。

接下来的 $k$ 行，每行包括四个整数：$x_i,y_i,h_i,c_i$，表示第 $i$ 个气球，位置在第 $x_i$ 行第 $y_i$ 列上空，距离地面高度 $h_i$，气球的颜色为 $c_i$。

outputFormat: 共包含 $n$ 行，每行 $m$ 个数字。其中第 $i$ 行第 $j$ 个数字表示从这个位置向上看能看到的气球的颜色。如果这个位置上空没有气球，则输出 $0$。


title: [入门赛 #22] 非众数 Hard Version

background: 本题是「非众数」的 Hard Version，$1 \le n \le 10^5$，感谢 @[yummy](https://www.luogu.com.cn/user/101694) 的贡献。

description:
给定一个长度为 $n$ 的字符串 $s$，保证 $s$ 仅包含小写字母，求 $s$  的**非空子串**中**非众数串**的个数。

> **定义：非空子串**
>
> 用 $s_i$ 表示 $s$ 中的第 $i$ 个字符（$1 \leq i \leq n$）。任取两个整数 $i, j$（$1 \leq i \leq j \leq n$），将 $s_i, s_{i + 1}, \cdots, s_{j}$ 截取出来按原序排列作为一个新的字符串，则这个字符串叫做 $s$ 的非空子串。
例如，当 $s = \texttt{abcde}$ 时，$\texttt{ab}, \texttt{bcde}, \texttt{c}, \texttt{abcde}$ 都是 $s$ 的非空子串，而 $\texttt{acd}, \texttt{f}, \texttt{ngioasd}, \texttt{" "}$ 都不是 $s$ 的非空子串。

> **定义：非众数串**
>
> 若字符串 $a$ 中出现次数最多的字符出现的次数不超过 $\lfloor \frac{|a|}{2} \rfloor$，则称字符串 $a$ 为一个**非众数**串。其中 $\lfloor x \rfloor$ 代表 $\leq x$ 的最大整数，$|a|$ 代表 $a$ 的长度。

inputFormat: 一行一个字符串，表示 $s$。

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

hint:
### 样例 1 解释

其中 $\texttt{ab,aabb}$ 是**非众数**非空子串。

### 数据范围

对于 $100\%$ 的数据，$1 \le n \le 10^5$，字符串由小写字母组成。


title: Fractal

description:
A fractal is an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales. The object need not exhibit exactly the same structure at all scales, but the same "type" of structures must appear on all scales.

A box fractal is defined as below :

-  A box fractal of degree $1$ is simply X
-  A box fractal of degree $2$ is
```
X X
 X
X X
```
- If using $B(n - 1)$ to represent the box fractal of degree $n - 1$, then a box fractal of degree $n$ is defined recursively as following
```
B(n - 1) B(n - 1)
     B(n - 1)
B(n - 1) B(n - 1)
```
Your task is to draw a box fractal of degree $n$.

inputFormat: The input consists of several test cases. Each line of the input contains a positive integer $n$ which is no greater than $7$. The last line of input is a negative integer $-1$ indicating the end of input.

outputFormat: For each test case, output the box fractal using the 'X' notation. Please notice that 'X' is an uppercase letter. Print a line with only a single dash after each test case.

translation:
**【题目描述】**

分形是在各种尺度上以某种技术意义上显示自相似性的对象或数量。对象不需要在所有尺度上展现完全相同的结构，但在所有尺度上必须出现相同的“类型”结构。

盒子分形定义如下：

- 度为 $1$ 的盒子分形简单地是 X
- 度为 $2$ 的盒子分形是
```
X X
 X
X X
```
- 如果用 $B(n - 1)$ 表示度为 $n - 1$ 的盒子分形，那么度为 $n$ 的盒子分形可以递归地定义如下
```
B(n - 1) B(n - 1)
     B(n - 1)
B(n - 1) B(n - 1)
```
你的任务是绘制度为 $n$ 的盒子分形。

**【输入格式】**

输入包含多个测试用例。输入的每一行包含一个不大于 $7$ 的正整数 $n$。输入的最后一行是一个负整数 $-1$，表示输入的结束。

**【输出格式】**

对于每个测试用例，使用 'X' 符号输出盒子分形。请注意，'X' 是一个大写字母。在每个测试用例之后打印一行仅包含单个破折号。

翻译来自于：ChatGPT。

samples:
X
-
X X
 X
X X
-
X X   X X
 X     X
X X   X X
   X X
    X
   X X
X X   X X
 X     X
X X   X X
-
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
   X X               X X
    X                 X
   X X               X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
         X X   X X
          X     X
         X X   X X
            X X
             X
            X X
         X X   X X
          X     X
         X X   X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
   X X               X X
    X                 X
   X X               X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
-


title: Number Base Conversion

description:
Write a program to convert numbers in one base to numbers in a second base. There are $62$ different digits:

$\{ 0\sim 9, A\sim Z,a\sim z \}$

HINT: If you make a sequence of base conversions using the output of one conversion as the input to the next, when you get back to the original base, you should get the original number.

inputFormat: The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines will have a (decimal) input base followed by a (decimal) output base followed by a number expressed in the input base. Both the input base and the output base will be in the range from $2$ to $62$. That is (in decimal) $A = 10, B = 11, \dots, Z = 35, a = 36, b = 37, \dots, z = 61$ ($0\sim 9$ have their usual meanings).

outputFormat: The output of the program should consist of three lines of output for each base conversion performed. The first line should be the input base in decimal followed by a space then the input number (as given expressed in the input base). The second output line should be the output base followed by a space then the input number (as expressed in the output base). The third output line is blank.

translation:
**【题目描述】**

编写一个程序，将一个进制中的数字转换为另一个进制中的数字。有 $62$ 个不同的数字：

${ 0\sim 9, A\sim Z,a\sim z }$

提示：如果你连续进行一系列的进制转换，将一个转换的输出作为下一个转换的输入，当你回到原始的进制时，你应该得到原始的数字。

**【输入格式】**

输入的第一行包含一个正整数，表示接下来有多少行输入。接下来的每一行都包含一个输入进制（十进制表示）和一个输出进制（十进制表示），然后是以输入进制表示的数字。输入进制和输出进制都将在 $2$ 到 $62$ 的范围内。也就是说（十进制表示）$A = 10, B = 11, \dots, Z = 35, a = 36, b = 37, \dots, z = 61$，（$0\sim 9$ 的意思与平常一样）。

**【输出格式】**

程序的输出应该包括每次进制转换的三行输出。第一行应该是以十进制表示的输入进制，然后是一个空格，接着是以输入进制表示的输入数字。第二行输出是输出进制，然后是一个空格，接着是以输出进制表示的输入数字。第三行输出是空白行。

翻译来自于：ChatGPT。

hint: 题目保证 $1\le T\le 100$，要转换的数字是不超过 $10^{110}$ 的自然数。


title: Raid

description:
After successive failures in the battles against the Union, the Empire retreated to its last stronghold. Depending on its powerful defense system, the Empire repelled the six waves of Union's attack. After several sleepless nights of thinking, Arthur, General of the Union, noticed that the only weakness of the defense system was its energy supply. The system was charged by $N$ nuclear power stations and breaking down any of them would disable the system.

The general soon started a raid to the stations by $N$ special agents who were paradroped into the stronghold. Unfortunately they failed to land at the expected positions due to the attack by the Empire Air Force. As an experienced general, Arthur soon realized that he needed to rearrange the plan. The first thing he wants to know now is that which agent is the nearest to any power station. Could you, the chief officer, help the general to calculate the minimum distance between an agent and a station?

inputFormat:
The first line is a integer T representing the number of test cases.

Each test case begins with an integer $N (1 \leq N \leq 100000)$.

The next $N$ lines describe the positions of the stations. Each line consists of two integers $X (0 \leq X \leq 10^9)$ and $Y (0 \leq Y \leq 10^9)$ indicating the positions of the station.

The next following N lines describe the positions of the agents. Each line consists of two integers $X (0 \leq X \leq 10^9)$ and $Y (0 \leq Y \leq 10^9)$ indicating the positions of the agent.

outputFormat: For each test case output the minimum distance with precision of three decimal placed in a separate line.

translation:
**【题目描述】**

在连续的对抗联盟失败后，帝国撤退到了最后的要塞。依靠其强大的防御系统，帝国击退了联盟的六波攻击。经过几个不眠之夜的思考，联盟将军亚瑟注意到防御系统唯一的弱点是其能源供应。该系统由 $N$ 个核电站供电，破坏其中任何一个都会使系统失效。

将军很快派出了 $N$ 名特工突袭这些电站，他们被空投到了要塞内。不幸的是，由于帝国空军的袭击，他们未能着陆到预期的位置。作为一名经验丰富的将军，亚瑟很快意识到他需要重新安排计划。他现在想知道的第一件事是，哪个特工距离任何一个电站最近。作为首席官员，你能帮助将军计算特工与电站之间的最小距离吗？

**【输入格式】**

第一行是一个整数 $T$，表示测试用例的数量。

每个测试用例以一个整数 $N (1 \leq N \leq 100000)$ 开始。

接下来的 $N$ 行描述了电站的位置。每行包含两个整数 $X (0 \leq X \leq 10^9)$ 和 $Y (0 \leq Y \leq 10^9)$，表示电站的位置。

接下来的 $N$ 行描述了特工的位置。每行包含两个整数 $X (0 \leq X \leq 10^9)$ 和 $Y (0 \leq Y \leq 10^9)$，表示特工的位置。

**【输出格式】**

对于每个测试用例，输出距离最小值，保留三位小数，单独占一行。

翻译来自于：ChatGPT。


title: [GESP202403 五级] 成绩排序

description:
有 $n$ 名同学，每名同学有语文、数学、英语三科成绩，你需要按照如下规则对所有同学的成绩从高到低排序：

1. 比较总分，高者靠前；
2. 如果总分相同，则比较语文和数学两科的总分，高者靠前；
3. 如果仍相同，则比较语文和数学两科的最高分，高者靠前；
4. 如果仍相同，则二人并列。

你需要输出每位同学的排名，如遇 $x$ 人并列，则他们排名相同，并留空后面的 $x - 1$ 个名次。例如，有 $3$ 名同学并列第 $1$，则后一名同学自动成为第 $4$ 名。

inputFormat:
第一行一个整数 $N$，表示同学的人数。
接下来 $N$ 行，每行三个非负整数 $c_i, m_i, e_i$ 分别表示该名同学的语文、数学、英语成绩。

outputFormat:
输出 $N$ 行，按输入同学的顺序，输出他们的排名。
**注意：请不要按排名输出同学的序号，而是按同学的顺序输出他们各自的排名。**

hint:
- 对 $30\%$ 的数据，$N \leq 100$，且所有同学总分各不相同。
- 对全部的测试数据，保证 $2 \leq N \leq 10^4$，$0 \leq c_i, m_i, e_i \leq 150$。


title: 「ALFR Round 2」D 超立方体

background:
>  映入眼帘的是一棵硕大的樱花树。
>
> 树下站着一个少女，她正抬头仰望着那棵樱花树。
> 我想：她是位新生吧，大概和我一样也是溜出来的。
> 我也抬着头望了望那棵樱花树。模模糊糊的花色遮住了天空。
> 刮起一阵风，飘舞着的樱花花瓣将少女裹住。
> 少女也看到了我……

description:
那是你与米尔嘉最初的邂逅。

一如既往，米尔嘉又给你出了一道数列题。
洁白的信封上留着柑橘的芳香，
你小心翼翼地拆开信封阅读。

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

在三维中，我们有三维立方体。
它的 $2^3$ 个点的坐标都可以写成 $(x,y,z)$ 的形式。

同理在 $n$ 维中，我们有 $n$ 维超立方体，它有 $2^n$ 个点。
其棱长为 $1$，且所有顶点的各维坐标都是非负整数。

我们从点 $(0,0,\dots,0)$ 出发，走过 $m$ 条棱，求到达点 $(1,1,\dots,0)$ 的方案总数。

其中要到达的点的坐标中有 $l$ 个数字 $1$。

由于答案可能很大，你只需要输出方案数对 $998244353$ 取模后的结果就可以了。

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

接下来 $T$ 行，每行三个非负整数 $n,m,l$。

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


title: Tree

description:
Give a tree with n vertices,each edge has a length(positive integer less than 1001).

Define dist(u,v)=The min distance between node u and v.

Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.

Write a program that will count how many pairs which are valid for a given tree.

inputFormat:
The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.

outputFormat: For each test case output the answer on a single line.


title: Task

description:
Today the company has $m$ tasks to complete. The $i-$th task need $x_i$ minutes to complete. Meanwhile, this task has a difficulty level $y_i$. The machine whose level below this task’s level $y_i$ cannot complete this task. If the company completes this task, they will get $(500\times x_i+2\times y_i)$ dollars.

The company has $n$ machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.

The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.

inputFormat:
The input contains several test cases.

The first line contains two integers $N$ and $M$. $N$ is the number of the machines.M is the number of tasks $(1 \leq N \leq 100000, 1\leq M\leq 100000)$.

The following $N$ lines each contains two integers $x_i(0<x_i<1440),y_i(0\leq yi\leq 100)$. $x_i$ is the maximum time the machine can work. $y_i$ is the level of the machine.

The following $M$ lines each contains two integers $x_i(0<x_i<1440),y_i(0\leq y_i\leq 100)$. $x_i$ is the time we need to complete the task. $y_i$ is the level of the task.

outputFormat: For each test case, output two integers, the maximum number of the tasks which the company can complete today and the money they will get.

translation:
**【题目描述】**

今天公司有 $m$ 项任务要完成。第 $i$ 项任务需要 $x_i$ 分钟来完成。同时，这个任务有一个困难级别 $y_i$。级别低于该任务级别 $y_i$ 的机器无法完成这项任务。如果公司完成了这项任务，他们将获得 $(500\times x_i+2\times y_i)$ 美元。

公司有 $n$ 台机器。每台机器都有最大工作时间和一个级别。如果任务的时间超过机器的最大工作时间，则该机器无法完成这个任务。每台机器一天只能完成一项任务。每项任务只能由一台机器完成。

公司希望最大化今天他们可以完成的任务数量。如果存在多个解决方案，他们希望使收益最大化。

**【输入格式】**

第一行包含两个整数 $N$ 和 $M$。$N$ 是机器的数量。$M$ 是任务的数量 $(1 \leq N \leq 100000, 1\leq M\leq 100000)$。

接下来的 $N$ 行每行包含两个整数 $x_i(0<x_i<1440),y_i(0\leq y_i\leq 100)$。$x_i$ 是机器可以工作的最长时间。$y_i$ 是机器的级别。

接下来的 $M$ 行每行包含两个整数 $x_i(0<x_i<1440),y_i(0\leq y_i\leq 100)$。$x_i$ 是完成任务所需的时间。$y_i$ 是任务的级别。

**【输出格式】**

对于每个测试用例，输出两个整数，分别是公司今天可以完成的最大任务数量和他们将获得的收益。

翻译来自于：ChatGPT。


title: [GESP202403 五级] B-smooth 数

description:
小杨同学想寻找一种名为 $ B $-smooth 数的正整数。

如果一个正整数的最大质因子不超过 $ B $，则该正整数为 $ B $-smooth 数。小杨同学想知道，对于给定的 $ n $ 和 $ B $，有多少个不超过 $ n $ 的 $ B $-smooth 数。

inputFormat: 第一行包含两个正整数 $ n $ 和 $ B $，含义如题面所示。

outputFormat: 输出一个非负整数，表示不超过 $ n $ 的 $ B $-smooth 数的数量。


title: Interval GCD

description:
给定一个长度为 $N$ 的数列 $A$，以及 $M$ 条指令，每条指令可能是以下两种之一：

1. `C l r d`，表示把 $A[l],A[l+1],…,A[r]$ 都加上 $d$。
2. `Q l r`，表示询问 $A[l],A[l+1],…,A[r]$ 的最大公约数(GCD)。

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

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

第二行 $N$ 个整数 $A[i]$。

接下来 $M$ 行表示 $M$ 条指令，每条指令的格式如题目描述所示。

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

每个答案占一行。

hint: 对于所有测试数据满足 $N \le 500000$，$M \le 100000$， $1 \le A[i] \le 10^{18}$，$|d| \le 10^{18}$，保证数据在计算过程中不会超过 long long 范围。


title: 占卜DIY

description:
lyd 学会了使用扑克 DIY 占卜。方法如下：一副去掉大小王的扑克共 $52$ 张，打乱后均分为 $13$ 堆，编号 $1\sim 13$，每堆 $4$ 张，其中第 $13$ 堆称作“生命牌”，也就是说你有 $4$ 条命。这里边，$4$ 张 $K$ 被称作死神。

初始状态下，所有的牌背面朝上扣下。

流程如下：

- 抽取生命牌中的最上面一张（第一张）。
- 把这张牌翻开，正面朝上，放到牌上的数字所对应编号的堆的最上边。(例如抽到 $2$ ，正面朝上放到第 $2$ 堆牌最上面，又比如抽到 $J$，放到第 $11$ 堆牌最上边，注意是正面朝上放)
- 从刚放了牌的那一堆最底下（最后一张）抽取一张牌，重复第 $2$ 步。（例如你上次抽了 $2$ ，放到了第二堆顶部，现在抽第二堆最后一张发现是 $8$，又放到第 $8$ 堆顶部……）
- 在抽牌过程中如果抽到 $K$，则称死了一条命，就扔掉 $K$ 再从第 $1$ 步开始。
- 当发现四条命都死了以后，统计现在每堆牌上边正面朝上的牌的数目，只要同一数字的牌出现 $4$ 张正面朝上的牌（比如 $4$ 个 $A$），则称“开了一对”，当然 $4$ 个 $K$ 是不算的。
- 统计一共开了多少对，开了 $0$ 对称作"极凶"，$1\sim 2$ 对为“大凶”，$3$ 对为“凶”，$4\sim 5$ 对为“小凶”，$6$ 对为“中庸”，$7\sim 8$ 对“小吉”，$9$ 对为“吉”，$10\sim11$ 为“大吉”，$12$ 为“满堂开花，极吉”。

如果还不明白，请参考样例。

inputFormat:
一共 $13$ 行，为每堆牌的具体牌是什么(不区分花色只区分数字)，每堆输入的顺序为从上到下。

为了便于读入，用 $0$ 代表 $10$。

outputFormat: 输出一共开了多少对。

hint:
注解：第一条命死后前 $12$ 堆牌变成了这个样子：
```
A A A 8
K 5 3 2
3 9 6 0
4 4 3 4
5 5 3 4
6 6 5 6
7 7 7 7
8 8 8 9
9 9 0 0
0 K J J
J Q A Q//抽到这里的K死掉了
J Q 2 2
```
第二条命由于 $K$ 在生命牌中，所以直接死掉，不变。

第三条命死后前 $12$ 堆牌变成了这个样子：
```
A A A A
2 2 2 K
3 3 3 3
4 4 4 4
5 5 5 5
6 6 6 6
7 7 7 7
8 8 8 8
9 9 9 9
0 0 0 0//抽到这里的K死掉了
J J J Q
Q Q J Q
```
第四条命死后前 $12$ 堆牌变成了这个样子：
```
A A A A
2 2 2 2//抽到这里的K死掉了
3 3 3 3
4 4 4 4
5 5 5 5
6 6 6 6
7 7 7 7
8 8 8 8
9 9 9 9
0 0 0 0
J J J Q
Q Q J Q
```
最后发现在所有已经正面朝上的牌中，$A\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 10$这 $9$ 对牌“开”了，（注意，第 $9$ 堆牌中的最后一张虽然也是 $9$，但是并没有被翻开！所以不能算）因此输出 $9$。


title: 防线

description:
lsp 学习数学竞赛的时候受尽了同仁们的鄙视，终于有一天……受尽屈辱的 lsp 黑化成为了黑暗英雄 Lord lsp。就如同中二漫画的情节一样，Lord lsp 打算毁掉这个世界。数学竞赛界的精英 lqr 打算阻止 Lord lsp 的阴谋，于是她集合了一支由数学竞赛选手组成的超级行动队。由于队员们个个都智商超群，很快，行动队便来到了 Lord lsp 的黑暗城堡的下方。

但是，同样强大的 Lord lsp 在城堡周围布置了一条“不可越过”的坚固防线。防线由很多防具组成，这些防具分成了 $N$ 组。我们可以认为防线是一维的，那么每一组防具都分布在防线的某一段上，并且同一组防具是等距离排列的。也就是说，我们可以用三个整数 $S$，$E$ 和 $D$ 来描述一组防具，即这一组防具布置在防线的 $S,S + D,S + 2D，\dots，S + KD$（$K\in \Z，S + KD\leq E，S + (K + 1)D>E$） 位置上。

黑化的 Lord lsp 设计的防线极其精良。如果防线的某个位置有偶数个防具，那么这个位置就是毫无破绽的（包括这个位置一个防具也没有的情况，因为 $0$ 也是偶数）。只有有奇数个防具的位置有破绽，但是整条防线上也最多只有一个位置有奇数个防具。作为行动队的队长，lqr 要找到防线的破绽以策划下一步的行动。但是，由于防具的数量太多，她实在是不能看出哪里有破绽。作为 lqr 可以信任的学弟学们，你们要帮助她解决这个问题。

inputFormat:
输入文件的第一行是一个整数 $T$，表示有 $T$ 组互相独立的测试数据。

每组数据的第一行是一个整数 $N$。

之后 $N$ 行，每行三个整数 $S_i$，$E_i$，$D_i$，代表第 $i$ 组防具的三个参数。

outputFormat:
对于每组测试数据，如果防线没有破绽，即所有的位置都有偶数个防具，输出一行 `There's no weakness.`。

否则在一行内输出两个空格分隔的整数 $P$ 和 $C$，表示在位置 $P$ 有 $C$ 个防具。当然 $C$ 应该是一个奇数。


title: [BeiJing2011] Matrix 矩阵哈希

description:
给定一个 $M$ 行 $N$ 列的 $01$ 矩阵，以及 $Q$ 个 $A$ 行 $B$ 列的 $01$ 矩阵，你需要求出这 $Q$ 个矩阵哪些在原矩阵中出现过。

所谓 $01$ 矩阵，就是矩阵中所有元素不是 $0$ 就是 $1$。

inputFormat:
输入文件的第一行为 $M,N,A,B$，参见题目描述。

接下来 $M$ 行，每行 $N$ 个字符，非 $0$ 即 $1$ ，描述原矩阵。

接下来一行为你要处理的询问数 $Q$。

接下来 $Q$ 个矩阵，一共 $Q\times A$ 行，每行 $B$ 个字符，描述 $Q$ 个 $01$ 矩阵。

outputFormat: 你需要输出 $Q$ 行，每行为 $0$ 或者 $1$，表示这个矩阵是否出现过，$0$ 表示没有出现过，$1$ 表示出现过。


title: [USACO03FALL] Milking Grid（数据加强版）

description:
Every morning when they are milked, the Farmer John's cows form a rectangular grid that is $R (1 \leq R \leq 10,000)$ rows by $C (1 \leq C \leq 75)$ columns. As we all know, Farmer John is quite the expert on cow behavior, and is currently writing a book about feeding behavior in cows. He notices that if each cow is labeled with an uppercase letter indicating its breed, the two-dimensional pattern formed by his cows during milking sometimes seems to be made from smaller repeating rectangular patterns.

Help FJ find the rectangular unit of smallest area that can be repetitively tiled to make up the entire milking grid. Note that the dimensions of the small rectangular unit do not necessarily need to divide evenly the dimensions of the entire milking grid, as indicated in the sample input below.

inputFormat:
- Line $1$: Two space-separated integers: $R$ and $C$

- Lines $2\dots R+1$: The grid that the cows form, with an uppercase letter denoting each cow's breed. Each of the $R$ input lines has $C$ characters with no space or other intervening character.

outputFormat: - Line 1: The area of the smallest unit from which the grid is formed

translation:
**【题目描述】**

每天早上挤奶时，农夫约翰的奶牛们排成一个 $R (1 \leq R \leq 10,000)$ 行乘 $C (1 \leq C \leq 75)$ 列的矩形网格。众所周知，约翰农夫是一个相当擅长牛行为的专家，目前正在撰写一本关于奶牛饲养行为的书。他注意到，如果每头奶牛都标有一个表示其品种的大写字母，那么奶牛在挤奶时形成的二维图案有时似乎是由更小的重复矩形图案组成的。

帮助约翰农夫找到可以重复铺设以组成整个挤奶网格的最小面积的矩形单元。请注意，小矩形单元的尺寸不一定需要完全整除整个挤奶网格的尺寸，如下面的示例输入所示。

**【输入格式】**

- 第一行：两个用空格分隔的整数：$R$ 和 $C$
- 第 $2\dots R+1$ 行：奶牛形成的网格，每个奶牛的品种用大写字母表示。每个 $R$ 输入行有 $C$ 个字符，没有空格或其他间隔字符。

**【输出格式】**

第一行：形成网格的最小单位的面积

**【提示说明】**

整个挤奶网格可以由图案 AB 的重复构建。

翻译来自于：ChatGPT。

hint: The entire milking grid can be constructed from repetitions of the pattern `AB`.


title: Necklace

description:
有一天，袁同学绵了一条价值连城宝石项链，但是，一个严重的问题是，他竟然忘记了项链的主人是谁！在得知此事后，很多人向同学发来了很多邮件，都说项链是自己的，要求他归还（显然其中最多只有一个人说了真话）。袁同学要求每个人都写了一段关于自己项链的描述：

项链上的宝石用数字 $0$ 至 $9$ 来表示。一个对于项链的表示就是从项链的某个宝石开始：顺指针绕一圈，沿途记下经过的宝石，比如如下项链：

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

它的可能的四种表示是 $0123$、$1230$、$2301$、$3012$。

袁同学现在心急如焚，于是他找到了你，希望你能够编一个程序，判断两个给定的描述是否代表同一个项链（注意，项链是不会翻转的）。

inputFormat: 输入文件只有两行，每行一个由 $0$ 至 $9$ 组成的字符串，描述一个项链的表示（保证项链的长度是相等的）。

outputFormat: 如果两条项链不可能同构，那么输出 `No`，否则的话，第一行输出一个 `Yes` 第二行输出该项链的字典序最小的表示。

hint: 设 $L =$ 项链长度，则 $1\leq L \leq 1000000$。


title: Subway tree systems

description:
Some major cities have subway systems in the form of a tree, i.e. between any pair of stations, there is one and only one way of going by subway. Moreover, most of these cities have a unique central station. Imagine you are a tourist in one of these cities and you want to explore all of the subway system. You start at the central station and pick a subway line at random and jump aboard the subway car. Every time you arrive at a station, you pick one of the subway lines you have not yet travelled on. If there is none left to explore at your current station, you take the subway line back on which you first came to the station, until you eventually have travelled along all of the lines twice,once for each direction. At that point you are back at the central station. Afterwards, all you remember of the order of your exploration is whether you went further away from the central station or back towards it at any given time, i.e. you could encode your tour as a binary string, where 0 encodes taking a subway line getting you one station further away from the central station, and 1 encodes getting you one station closer to the central station.

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

inputFormat: On the first line of input is a single positive integer n, telling the number of test scenarios to follow.Each test scenario consists of two lines, each containing a string of the characters '0' and '1' of length at most 3000, both describing a correct exploration tour of a subway tree system.

outputFormat: exploration tours of the same subway tree system, or the text "different" if the two strings cannot be exploration tours of the same subway tree system.

translation:
**【题目描述】**

一些主要城市的地铁系统采用树状结构，即在任何两个车站之间，只有一条且仅有一条地铁线路。此外，大多数这些城市都有一个独特的中央车站。想象一下，你是这些城市中的一名游客，你想要探索整个地铁系统。你从中央车站出发，随机选择一条地铁线路，跳上地铁列车。每当你到达一个车站，你就会选择一条你尚未乘坐过的地铁线路。如果在当前车站没有其他要探索的地铁线路了，你就会乘坐第一次到达该车站的地铁线路返回，直到最终你沿着所有的线路都行驶了两次，即每个方向都行驶了一次。在那时，你回到了中央车站。之后，你所记得的探索顺序只是在任何给定时间是否向中央车站更远或更近，也就是说，你可以将你的旅程编码为一个二进制字符串，其中 0 表示乘坐一条地铁线路使你离中央车站更远一站，而 1 表示使你离中央车站更近一站。

**【输入格式】**

输入的第一行是一个正整数 $n$，表示接下来要跟随的测试方案的数量。每个测试方案包括两行，每行包含一个长度最多为 $3000$ 的由字符 '0' 和 '1' 组成的字符串，描述了地铁树系统的正确探索旅程。

**【输出格式】**

对于每个测试方案，如果两个字符串可以表示相同地铁树系统的探索旅程，则输出 "same"；如果两个字符串不能表示相同地铁树系统的探索旅程，则输出 "different"。

翻译来自于：ChatGPT。


title: 匹配统计

description:
阿轩在纸上写了两个字符串，分别记为 $A$ 和 $B$。利用在数据结构与算法课上学到的知识，他很容易地求出了"字符串 $A$ 从任意位置开始的后缀子串“与“字符串 $B$”匹配的长度。

不过阿轩是一个勤学好问的同学，他向你提出了 $Q$ 个问题：在每个问题中，他给定你一个整数 $X$，请你告诉他有多少个位置，满足“字符串 $A$ 从该位置开始的后缀子串"与 $B$ 匹配的长度恰好为 $X$。

例如：A=aabcde，B=ab，则 $A$ 有 aabcde、abcde、bcde、cde、de、e 这 $6$ 个后缀子串，它们与 $B=ab$ 的匹配长度分别是 $1,2,0,0,0,0$。因此 $A$ 有 $4$ 个位置与 $B$ 的匹配长度恰好为 $0$，有 $1$ 个位置的匹配长度恰好为 $1$，有 $1$ 个位置的匹配长度恰好为 $2$。

inputFormat:
第一行三个整数 $N,M,Q$，表示 $A$ 串长度、$B$ 串长度、问题个数。

第二行是字符串 $A$，第三行是字符串 $B$。

接下来 $Q$ 行每行 $1$ 个整数 $x$，表示一个问题。

outputFormat: 共 $Q$ 行，依次表示每个问题的答案。

hint: 数据保证，$1\leq N,M,Q,X\leq 200000$。


title: 括号画家

description:
Candela 是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。这一天，刚刚起床的 Candela 画了一排括号序列，其中包含小括号 `()`、中括号 `[]` 和大括号 `{}`，总长度为 $N$。这排随意绘制的括号序列显得杂乱无章，于是 Candela 定义了什么样的括号序列是美观的：

1. 空的括号序列是美观的；
2. 若括号序列 A 是美观的，则括号序列 `(A)`、`[A]`、`{A}` 也是美观的；
3. 若括号序列 A、B 都是美观的，则括号序列 `AB` 也是美观的；

例如 `[(){}]()` 是美观的括号序列，而 `)({)[}](` 则不是。

现在 Candela 想在她绘制的括号序列中，找出其中连续的一段，满足这段子序列是美观的，并且长度尽量大。你能帮帮她吗？

inputFormat: 第一行一个长度为 $N$ 的括号序列。

outputFormat: 一个整数，表示最长的美观的连续子序列的长度。


title: 生日礼物

description:
ftiasch 18 岁生日的时候，lqp18_31 给她看了一个神奇的序列 $A _ 1$, $A _ 2$, ..., $A _ N$。 她被允许选择不超过 $M$ 个连续的部分作为自己的生日礼物。

自然地，ftiasch 想要知道选择元素之和的最大值。你能帮助她吗?

inputFormat:
第 1 行，两个整数 $N$ ($1 \le  N \le 10 ^ {5}$ ) 和 $M$ ($0 \le M \le 10 ^ 5$)，表示序列的长度和可以选择的部分。

第 2 行， $N$ 个整数 $A_1$, $A_2$, ..., $A_N$ ($0 \le \mid A_i\mid \le 10^4$)，表示序列。

outputFormat: 一个整数，表示最大的和。


title: 表达式计算4

description:
给出一个表达式，其中运算符仅包含 +，-，*，/，^，要求求出表达式的最终值。

数据可能会出现括号情况，还有可能出现多余括号情况。

数据保证不会出现超过 int 范围的数据，数据可能会出现负数情况。

inputFormat: 仅一行一个字符串，即为表达式。

outputFormat: 仅一行，既为表达式算出的结果。

hint: 表达式总长度不超过 $30$。


title: Bloxorz II

description:
由于大灾难的发生，科学院已经连续有很多年没有新生了(这个世界中的科学院其实也 有大学的职能)。于是这一年的新生测试就有里程碑一样的意义。作为科学院的顶级信息专 家，这一任务自然落到了你的头上。思来想去，你决定出这样的一个题，那就是 Bloxorz 游戏。

所谓 Bloxorz 游戏，如下图所示，就是在一个平台上有一个作为目标的 1×1 的洞，以 及一个大小为 2×1×1 的长方体。长方体可以沿着边在平台上滚动，但是不能与平台失去接触面。

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

下面这张图反映了上图中的长方体向右滚动之后的局面。
![](https://cdn.luogu.com.cn/upload/image_hosting/6kgp8841.png)

而下面这张图就反映了向前方滚动之后的局面。

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

任务就是让长方体进入目标洞。当然，这时长方体应该是竖立的。

滚动一次叫做一步。你的题目就是对于一个给定的局面，计算至少需要多少步才能把长 方体滚到目标洞里面去。自然，对于新生来说这个题是一个很难的题。

  被你虐了的新生感到很不服气。于是他们想了一个更难的题来让你做:

有一个无限大的平台以及一个建立在上面的坐标系。现在目标洞在(0, 0)处，长方体的 位置和状态(竖立、与 x 轴平行还是与 y 轴平行)给定，计算至少需要多少步才能使长方体 进洞。

  作为顶级信息专家......这当然难不倒你了。

inputFormat:
输入文件包含多组测试数据。

每组测试数据在一行内，格式为 C x y。其中 C 为一个字母，x 和 y 是两个整数。 这表示长方体覆盖住了平台上的格子(x, y)，且其状态为 C。

若 C 为字母 U，表明长方体是竖立的。

若 C 为字母 V，表明长方体与 x 轴平行，且其覆盖的另一个格子为(x + 1, y)。

若 C 为字母 H，表明长方体与 y 轴平行，且其覆盖的另一个格子为(x, y + 1)。 输入文件以 EOF 结束。

outputFormat: 对于每组测试数据，在单独的一行内输出答案。

hint:
对于 20% 的数据，$ \mid x \mid , \mid y \mid \le 100$。
对于 100% 的数据，$\mid x\mid , \mid y\mid \le 10^9$，输入数据不超过 100 组。


title: Missile Defence System

description:
To play against the threats of malicious countries nearby, Country R has updated their missile defence system. The new type system can bring down a series of missiles as long as they are coming in ascending order by altitude or descending order by altitude.

Given the heights of a sequence of coming missiles, the general wants to know how many sets of the new type systems are needed to bring down all of them.

inputFormat: The input consists of several test cases. The first line of each test case contains an integer $n (1 \le n \le 50)$. The next line contains n different integers indicating the heights.

outputFormat: For each test case output a single line containing the number of systems needed.For each test case output a single line containing the number of systems needed.

translation:
### 题目描述

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直严格单调上升要么一直严格单调下降。

例如，一套系统先后拦截了高度为 $3$ 和高度为 $4$ 的两发导弹，那么接下来该系统就只能拦截高度大于 $4$ 的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

### 输入格式

输入包含多组测试用例。

对于每个测试用例，第一行包含整数 $n$，表示来袭导弹数量。

第二行包含 $n$ 个不同的整数，表示每个导弹的高度。

当输入测试用例 $n=0$ 时，表示输入终止，且该用例无需处理。

### 输出格式

对于每个测试用例，输出一行，一个整数，表示所需的防御系统数量。

### 说明与提示

#### 样例解释
对于样例，需要两套系统。一套击落 $3,4$ 号导弹，另一套击落 $5,2,1$ 号导弹。

#### 数据规模与约定
$1 \leq n \leq 50$。

hint: Two sets of systems are needed for the sample. One brings down 3, 4 and the other brings down 5, 2, 1.


title: [USACO02FEB] Power Hungry Cows

description:
FJ's cows would like to be able to compute integer powers P (1 <= P <= 20,000) of numbers very quickly, but need your help. Because they're going to be computing powers of very large numbers, they can only keep around two work variables for intermediate results.

The first of those work variables is initialized to the number (denoted x) for which they are calculating the power; the other is initialized to 1. The cows can both multiply and divide any pair of the work variables and store the result in any work variable, but all results are stored as integers.

For example, if they want to compute x^31, one way to perform the calculation is:

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

Thus, x^31 can computed in six operations. Given the power to be computed and the the number of work variables, find the minimum number of operations to calculate the power.

inputFormat: A single line with one integer: P.

outputFormat: A single line with a single integer that is the minimum number of operations it requires to compute the pow

translation:
**【题目描述】**

FJ 的奶牛们希望能够快速计算整数幂 $P$（$1 \leq P \leq 20000$），但她们需要你的帮助。因为她们将要计算非常大的数的幂，所以她们只能保留两个工作变量来存储中间结果。

这两个工作变量中的第一个被初始化为正在计算幂的数字（表示为 $x$）；另一个被初始化为 $1$。奶牛们可以对任意一对工作变量进行乘法和除法运算，并将结果存储在任意一个工作变量中，但所有结果都存储为整数。

例如，如果她们想要计算 $x^{31}$，一种进行计算的方法是：

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

因此，$x^{31}$ 可以在六次操作中计算出来。给定要计算的幂和工作变量的数量，找出计算该幂所需的最少操作数。

**【输入格式】**

一行，一个整数：$P$。

**【输出格式】**

一行，一个整数，表示计算幂所需的最小操作数。

翻译来自于：[ChatGPT](https://chatgpt.com/)

tags: 启发式迭代加深搜索,IDA*


title: [IOI1994] The Buses

background: 0x29 搜索 总结与练习

description:
A man arrives at a bus stop at 12:00. He remains there during 12:00-12:59. The bus stop is used by a number of bus routes. The man notes the times of arriving buses. The times when buses arrive are given.

-  Buses on the same route arrive at regular intervals from 12:00 to 12:59 throughout the entire hour.
- Times are given in whole minutes from 0 to 59.
- Each bus route stops at least 2 times.
- The number of bus routes in the test examples will be <=17.
- Buses from different routes may arrive at the same time.
- Several bus routes can have the same time of first arrival and/or time interval. If two bus routes have the same starting time and interval, they are distinct and are both to be presented.

Find the schedule with the fewest number of bus routes that must stop at the bus stop to satisfy the input data. For each bus route, output the starting time and the interval.

inputFormat: Your program is to read from standard input. The input contains a number n (n <= 300) telling how many arriving buses have been noted, followed by the arrival times in ascending order.

outputFormat: Your program is to write to standard output. The output contains one integer, which is the fewest number of bus routes.

translation:
**【题目描述】**

一个人在 12:00 到达一个公交车站。他在 12:00 到 12:59 期间一直待在那里。这个公交车站被多条公交线路使用。这个人记录了公交车到达的时间。给出了公交车到达的时间。

- 同一条路线的公交车在整个小时内从 12:00 到 12:59 以固定的时间间隔到达。
- 时间以整分钟给出，从 0 到 59。
- 每条公交线路至少停靠 2 次。
- 测试示例中的公交线路数量将 $\leq 17$。
- 不同路线的公交车可能同时到达。
- 几条公交线路的首次到达时间和/或时间间隔可能相同。如果两条公交线路的起始时间和间隔相同，则它们是不同的，并且都需要呈现。

找出满足输入数据的必须停靠在公交车站的公交线路数量最少的时间表。对于每条公交线路，输出起始时间和间隔。

**【输入格式】**

你的程序需要从标准输入中读取。输入包含一个数字 $n$（$n \leq 300$），表示已经记录的到达公交车的数量，后跟按升序排列的到达时间。

**【输出格式】**

你的程序需要写入标准输出。输出包含一个整数，即最少的公交线路数量。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: Weather Forecast

description:
You are the God of Wind.

By moving a big cloud around, you can decide the weather: it invariably rains under the cloud, and the sun shines everywhere else.

But you are a benign God: your goal is to give enough rain to every field in the countryside, and sun to markets and festivals. Small humans, in their poor vocabulary, only describe this as "weather forecast".

You are in charge of a small country, called Paccimc. This country is constituted of 4 x 4 square areas, denoted by their numbers.

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

Your cloud is of size 2 x 2, and may not cross the borders of the country.

You are given the schedule of markets and festivals in each area for a period of time.

On the first day of the period, it is raining in the central areas (6-7-10-11), independently of the schedule.

On each of the following days, you may move your cloud by 1 or 2 squares in one of the four cardinal directions (North, West, South, and East), or leave it in the same position. Diagonal moves are not allowed. All moves occur at the beginning of the day.

You should not leave an area without rain for a full week (that is, you are allowed at most 6 consecutive days without rain). You don't have to care about rain on days outside the period you were given: i.e. you can assume it rains on the whole country the day before the period, and the day after it finishes.

inputFormat:
The input is a sequence of data sets, followed by a terminating line containing only a zero.

A data set gives the number N of days (no more than 365) in the period on a single line, followed by N lines giving the schedule for markets and festivals. The i-th line gives the schedule for the i-th day. It is composed of 16 numbers, either 0 or 1, 0 standing for a normal day, and 1 a market or festival day. The numbers are separated by one or more spaces.

outputFormat: The answer is a 0 or 1 on a single line for each data set, 1 if you can satisfy everybody, 0 if there is no way to do it.

translation:
**【题目描述】**

你是风之神。

通过移动一朵大云，你可以决定天气：云下必定下雨，其他地方阳光普照。

但你是一个仁慈的神：你的目标是给乡间的每个田地带来足够的雨水，给市场和节日带来阳光。小人类用他们贫乏的词汇，只能将这称为“天气预报”。

你负责管理一个名为 Paccimc 的小国家。这个国家由 $4 \times 4$ 的方块区域组成，用它们的编号表示。

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

你的云的大小为 $2 \times 2$，不得越过国家的边界。

给出了一段时间内每个区域的市场和节日的安排。

在该时段的第一天，无论安排如何，在中心区域（6-7-10-11）都会下雨。

在接下来的每一天，你可以将你的云向四个基本方向之一（北、西、南和东）移动 $1$ 或 $2$ 个方格，也可以将其保持在原位。不允许对角线移动。所有移动均发生在一天开始时。

你不应该让一个区域连续一周没有雨水（也就是说，你允许最多连续 $6$ 天没有雨）。你不必在你获得的时间段之外的日子里考虑雨水：也就是说，你可以假设在时间段之前的整个国家都下雨，在它结束后的一天也是如此。

**【输入格式】**

输入一个数据集序列，后跟一个仅包含零的终止行。

一个数据集在单独的一行上给出了期间中的天数 $N$（不超过 $365$），然后是 $N$ 行，给出了市场和节日的安排。第 $i$ 行给出了第 $i$ 天的安排。它由 $16$ 个数字组成，要么是 $0$ 要么是 $1$，$0$ 表示正常日，$1$ 表示市场或节日。数字之间用一个或多个空格分隔。

**【输出格式】**

对每个数据集的单行输出，如果你能满足每个人，则输出 $1$，否则输出 $0$。

**【样例解释】**

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: [USACO09NOV] The Chivalrous Cow B

background: 农民 John 有很多牛，他想交易其中一头被 Don 称为 The Knight 的牛。这头牛有一个独一无二的超能力，在农场里像 Knight 一样地跳（就是我们熟悉的象棋中马的走法）。虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个 $x，y$ 的坐标图来表示。

description:
这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了 The Knight 的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。现在你的任务是，确定 The Knight 要想吃到草，至少需要跳多少次。The Knight 的位置用 `K` 来标记，障碍的位置用 `*` 来标记，草的位置用 `H` 来标记。

这里有一个地图的例子：
```
             11 | . . . . . . . . . .
             10 | . . . . * . . . . .
              9 | . . . . . . . . . .
              8 | . . . * . * . . . .
              7 | . . . . . . . * . .
              6 | . . * . . * . . . H
              5 | * . . . . . . . . .
              4 | . . . * . . . * . .
              3 | . K . . . . . . . .
              2 | . . . * . . . . . *
              1 | . . * . . . . * . .
              0 ----------------------
                                    1
                0 1 2 3 4 5 6 7 8 9 0
```
The Knight 可以按照下图中的 $A,B,C,D...$ 这条路径用 $5$ 次跳到草的地方（有可能其它路线的长度也是 $5$）：
```
             11 | . . . . . . . . . .
             10 | . . . . * . . . . .
              9 | . . . . . . . . . .
              8 | . . . * . * . . . .
              7 | . . . . . . . * . .
              6 | . . * . . * . . . F<
              5 | * . B . . . . . . .
              4 | . . . * C . . * E .
              3 | .>A . . . . D . . .
              2 | . . . * . . . . . *
              1 | . . * . . . . * . .
              0 ----------------------
                                    1
                0 1 2 3 4 5 6 7 8 9 0
                ```

inputFormat:
第一行$：$ 两个数，表示农场的列数$（\le 150）$ 和行数$（\le150）$

第二行$..$结尾$：$如题目描述的图。

outputFormat: 一个数，表示跳跃的最小次数。

hint: Hint：这类问题可以用一个简单的先进先出表（队列）来解决。


title: 233 Matrix

description: In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 ... in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333... (it means $a _ {0,1} = 233$, $a_{0,2} = 2333$, $a_{0,3} = 23333$...) Besides, in 233 matrix, we got $a_{i,j} = a_{i-1,j} +a_{i,j-1}( i,j \neq 0)$. Now you have known $a_{1,0},a_{2,0},\dots,a_{n,0}$, could you tell me $a_{n,m}$ in the 233 matrix?

inputFormat:
There are multiple test cases. Please process till EOF.

For each case, the first line contains two postive integers $n,m(n \le 10,m \le 10^9)$. The second line contains n integers, $a_{1,0},a_{2,0},...,a_{n,0}$ ($0 \le a_i,0 < 2^{31}$).

outputFormat: For each case, output $a_{n,m}$ mod 10000007.

translation:
**【题目描述】**

在我们的日常生活中，我们经常用 233 来表达我们的情感。实际上，我们可能会说 2333、23333 或者 233333... 都表示同样的意思。现在有一个问题：假设我们有一个称为 233 矩阵。在第一行，它可能是 233、2333、23333...（表示 $a _ {0,1} = 233$，$a_{0,2} = 2333$，$a_{0,3} = 23333$...）。此外，在 233 矩阵中，我们有 $a_{i,j} = a_{i-1,j} +a_{i,j-1}( i,j \neq 0)$。现在已知 $a_{1,0},a_{2,0},\dots,a_{n,0}$，你能告诉我 233 矩阵中的 $a_{n,m}$ 吗？

**【输入格式】**

有多个测试用例，请处理直到 EOF。

对于每个案例，第一行包含两个正整数 $n,m(n \le 10,m \le 10^9)$。第二行包含 n 个整数，$a_{1,0},a_{2,0},...,a_{n,0}$（$0 \le a_i,0 < 2^{31}$）。

**【输出格式】**

对于每个案例，输出 $a_{n,m}$ 模 10000007。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: Dropping Test

description:
在某个课程中，你需要进行 $n$ 次测试。

如果你在共计 $b_i$ 道题的测试 $i$ 上的答对题目数量为 $a_i$，你的累积平均成绩就被定义为

$$100\times \dfrac{\displaystyle \sum_{i=1}^n a_i}{\displaystyle \sum_{i=1}^n b_i}$$

给定您的考试成绩和一个正整数 $k$，如果您被允许放弃任何 $k$ 门考试成绩，您的累积平均成绩的可能最大值是多少。

假设您进行了 $3$ 次测试，成绩分别为 $5/5,0/1$ 和 $2/6$。

在不放弃任何测试成绩的情况下，您的累积平均成绩是

$$100\times \frac{5+0+2}{5+1+6}=50$$

然而，如果你放弃第三门成绩，则您的累积平均成绩就变成了

$$100\times \frac{5+0}{5+1}\approx 83.33\approx 83$$

inputFormat:
输入包含多组测试用例，每个测试用例包含三行。

对于每组测试用例，第一行包含两个整数 $n$ 和 $k$。

第二行包含 $n$ 个整数，表示所有的 $a_i$。

第三行包含 $n$ 个整数，表示所有的 $b_i$。

当输入用例 $n=k=0$ 时，表示输入终止，且该用例无需处理。

outputFormat:
对于每个测试用例，输出一行结果，表示在放弃 $k$ 门成绩的情况下，可能的累积平均成绩最大值。

结果应四舍五入到最接近的整数。


title: Georgia and Bob

description:
Georgia and Bob decide to play a self-invented game. They draw a row of grids on paper, number the grids from left to right by $1 , 2 , 3 , \cdots ,$ and place $N$ chessmen on different grids, as shown in the following figure for example:

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

Georgia and Bob move the chessmen in turn. Every time a player will choose a chessman, and move it to the left without going over any other chessmen or across the left edge. The player can freely choose number of steps the chessman moves, with the constraint that the chessman must be moved at least ONE step and one grid can at most contains ONE single chessman. The player who cannot make a move loses the game.

Georgia always plays first since "Lady first". Suppose that Georgia and Bob both do their best in the game, i.e., if one of them knows a way to win the game, he or she will be able to carry it out.

Given the initial positions of the $n$ chessmen, can you predict who will finally win the game?

inputFormat: The first line of the input contains a single integer $T (1 \leq T \leq 20)$, the number of test cases. Then $T$ cases follow. Each test case contains two lines. The first line consists of one integer $N (1 \leq N \leq 1000)$, indicating the number of chessmen. The second line contains $N$ different integers $P_1, P_2 \dots P_n (1 \leq P_i \leq 10000)$, which are the initial positions of the $n$ chessmen.

outputFormat: For each test case, prints a single line, "Georgia will win", if Georgia will win the game; "Bob will win", if Bob will win the game; otherwise 'Not sure'.

translation:
**【题目描述】**

有一个无限长的棋盘，从左到右编号为 $1,2,3,\cdots$。有 $n$ 个棋子在棋盘上，定义一次操作为把一枚棋子向左移动至少一格，不可以逾越其他棋子，不可与其他棋子重合，不可移出棋盘。

告诉你这 $n$ 个棋子的位置（不保证顺序且保证没有棋子重合），Georgia 和 Bob 轮流进行操作，Georgia 先手，谁无法操作谁输。问最后谁会赢？

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

**【输入格式】**

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

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

对于每组数据：

第一行一个整数 $n$。

接下来一行 $n$ 个整数，表示每个棋子的位置。

**【输出格式】**

对于每组数据，若 Georgia 胜输出 `Georgia will win`，若 Bob 胜输出 `Bob will win`，若平局则输出 `Not sure`。


title: Matrix Power Series

description: Givena $n×n$ matrix $A$ and apositive integer $k$，find the sum $S=A+A^2 +A^3 +...+A^k$.

inputFormat: The input contains exactly one test case. The first line of input contains three positive integers $n$ ($n \le 30$), $k$ ($k \le 10^9$) and $m$ ($m < 10^4$). Then follow n lines each containing $n$ non negative integers below 32,768, giving $A$’s elements in row-major order.

outputFormat: Output the elements of $S$ modulo $m$ in the same way as $A$ is given.

translation:
**【题目描述】**

给定一个 $n×n$ 矩阵 $A$ 和一个正整数 $k$，找出和 $S=A+A^2 +A^3 +...+A^k$。

**【输入格式】**

输入包含一个测试用例。输入的第一行包含三个正整数 $n$（$n \le 30$）、$k$（$k \le 10^9$）和 $m$（$m < 10^4$）。接下来的 $n$ 行每行包含 $n$ 个小于 32,768 的非负整数，按行主序给出 $A$ 的元素。

**【输出格式】**

以与给定 $A$ 相同的方式输出 $S$ 的元素对 $m$ 取模。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: 守卫者的挑战

description:
打开了黑魔法师 Vani 的大门，队员们在迷宫般的路上漫无目的地搜寻着关押 applepi 的监狱的所在地。突然，眼前一道亮光闪过。“我，Nizem，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……”瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为K的包包。

擂台赛一共有 $N$ 项挑战，各项挑战依次进行。第 $i$ 项挑战有一个属性 $a_i$，如果 $a_i\geq 0$，表示这次挑战成功后可以再获得一个容量为 $a_i$ 的包包；如果 $a_i=-1$，则表示这次挑战成功后可以得到一个大小为 $1$ 的地图残片。地图残片必须装在包包里才能带出擂台，包包没有必要全部装满，但是队员们必须把 【获得的所有的】地图残片都带走（没有得到的不用考虑，只需要完成所有N项挑战后背包容量足够容纳地图残片即可），才能拼出完整的地图。并且他们至少要挑战成功 $L$ 次才能离开擂台。

队员们一筹莫展之时，善良的守卫者 Nizem 帮忙预估出了每项挑战成功的概率，其中第 $i$ 项挑战成功的概率为 $p_i\%$。现在，请你帮忙预测一下，队员们能够带上他们获得的地图残片离开擂台的概率。

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

第二行 $N$ 个实数，第 $i$ 个实数 $p_i$ 表示第 $i$ 项挑战成功的百分比。

第三行 $N$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 项挑战的属性值.

outputFormat: 一个整数，表示所求概率，四舍五入保留 $6$ 位小数。

hint:
在第一个样例中，若第三项挑战成功，如果前两场中某场胜利，队员们就有空间来容纳得到的地图残片，如果挑战失败，根本就没有获得地图残片，不用考虑是否能装下；若第三项挑战失败，如果前两场有胜利，没有包来装地图残片，如果前两场都失败，不满足至少挑战成功1次的要求。因此所求概率就是第三场挑战获胜的概率。

对于 $100\%$ 的数据，保证 $0\leq K\leq 2000$，$0\leq N\leq 200$，$-1\leq a_i\leq 1000$，$0\leq L\leq N$，$0\leq p_i\leq 100$。


title: 魔法珠

description:
Freda 和 rainbow 是超自然之界学校（Preternatural Kingdom University，简称 PKU）魔法学院的学生。为了展示新学的魔法，Ta 们决定进行一场对弈~~~

起初 Freda 面前有 $n$ 堆魔法珠，其中第 $i$ 堆有 $a_i$ 颗。 Freda 和 rainbow 可以轮流进行以下操作：

1.选择 $n$ 堆中魔法珠数量大于 $1$ 的任意一堆。记该堆魔法珠的数量为 $p$，$p$ 有 $b_1,b_2 \cdots b_m$ 这 $m$ 个小于 $p$ 的约数。

2.施展魔法把这一堆魔法珠变成 $m$ 堆，每堆各有 $b_1$、$b_2 \cdots b_m$ 颗魔法珠。

3.选择这m堆中的一堆魔法珠，施展魔法令其消失。

注意一次操作过后，魔法珠的堆数会增加m-2，各堆中魔法珠数量的总和可能会发生变化。

当轮到某人操作时，如果每堆中魔法珠的数量均为1，那么ta就输了。

Freda 和 rainbow 都采取最好的策略，从 Freda 开始。请你预测一下，谁能获胜呢？

inputFormat:
本题仅有一个测试点，包含多组数据，以 EOF 结尾。

每组数据的第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_i$。

outputFormat: 对于每组数据，在两人均采取最佳策略的前提下，若 Freda 能获胜，输出 freda；若 Rainbow 能获胜，输出 rainbow。

hint: 对于所有测试数据满足 $1\le n\le100$，$1\le a_i\le 1000$。


title: Buy Tickets

description:
> Railway tickets were difficult to buy around the Lunar New Year in China, so we must get up early and join a long queue…

The Lunar New Year was approaching, but unluckily the Little Cat still had schedules going here and there. Now, he had to travel by train to Mianyang, Sichuan Province for the winter camp selection of the national team of Olympiad in Informatics.

It was one o’clock a.m. and dark outside. Chill wind from the northwest did not scare off the people in the queue. The cold night gave the Little Cat a shiver. Why not find a problem to think about? That was none the less better than freezing to death!

People kept jumping the queue. Since it was too dark around, such moves would not be discovered even by the people adjacent to the queue-jumpers. “If every person in the queue is assigned an integral value and all the information about those who have jumped the queue and where they stand after queue-jumping is given, can I find out the final order of people in the queue?” Thought the Little Cat.

inputFormat:
There will be several test cases in the input. Each test case consists of N + 1 lines where N (1 ≤ N ≤ 200,000) is given in the first line of the test case. The next N lines contain the pairs of values Posi and Vali in the increasing order of i (1 ≤ i ≤ N). For each i, the ranges and meanings of Posi and Vali are as follows:

- Posi ∈ [0, i − 1] — The i-th person came to the queue and stood right behind the Posi-th person in the queue. The booking office was considered the 0th person and the person at the front of the queue was considered the first person in the queue.
_ Vali ∈ [0, 32767] — The i-th person was assigned the value Vali.

There no blank lines between test cases. Proceed to the end of input.

outputFormat: For each test cases, output a single line of space-separated integers which are the values of people in the order they stand in the queue.


title: Fotile 模拟赛 L

description:
FOTILE 得到了一个长为 $N$ 的序列 $A$，为了拯救地球，他希望知道某些区间内的最大的连续 $\rm XOR$ 和。

即对于一个询问，你需要求出

$$
\max_{l\le i\le j\le r}\bigoplus_{k=i}^{j} a_k
$$

为了体现在线操作，对于一个询问 $(x,y)$：

- $l = \min ( ((x+{\rm lastans}) \bmod N)+1 , ((y+{\rm lastans}) \bmod N)+1)$.
- $r = \max ( ((x+{\rm lastans}) \bmod N)+1 , ((y+{\rm lastans}) \bmod N)+1)$.

**其中 $\rm lastans$ 是上次询问的答案，一开始为0。**

inputFormat:
第一行两个整数 $N$ 和 $M$。

第二行有 $N$ 个正整数，其中第 $i$ 个数为 $A_i$，有多余空格。

后 $M$ 行每行两个数 $x$, $y$ 表示一对询问。

outputFormat: 共 $M$ 行，第 $i$ 行一个正整数表示第 $i$ 个询问的结果。

hint: 对于所有的测试数据满足 $N=12000$，$M=6000$，$x$，$y$，$a_i$ 均在 signed int 范围内。


title: 进制

background:
为了提供更加良好的区分度，相较于蓝桥杯国赛，本场比赛的所有程序设计题添加了额外样例，请在附件处下载。

其中，后缀名为 $\bf{.in}$ 的文件为输入文件，$\bf{.out}$ 的文件为输出文件。您可以使用这些额外样例检验自己的程序正确性。但我们不保证通过额外样例一定能取得您期望的分数。

此外，我们提供了相较蓝桥杯国赛更多档的部分分，以确保分数分布更为科学合理。

description:
小洛正在学习三进制。他定义三进制数为每一位只包括 $0,1,2$ 三种数的**无穷长的**数字串 $a$。

与一般的三进制数不同的是，小洛的三进制数从左往右书写。例如，在常规表述下，$4$ 的三进制表示为 $(0000\ 0011)_3$，而在小洛的三进制数表示下为 $(1100\ 0000 \cdots)_3$。

小洛特别喜欢从 $0$ 开始计数，因此他规定三进制的第 $0$ 位为最左侧的那一数位。

下表给出了小洛的三进制数表示下，数字 $37$ 的最低的 $8$ 位数位以及位权：

| 三进制数表示 | $1$ | $0$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| 位数 | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
| 位权 | $3^0$ | $3^1$ | $3^2$ | $3^3$ | $3^4$ | $3^5$ | $3^6$ | $3^7$ |

现在小洛有一个十进制正整数 $V$（显然，需要将其转化为小洛的三进制数表示），并且给定三种操作：

- 操作一，将第 $i$ 位上的数进行操作：$0$ 变为 $1$，$1$ 变为 $2$，$2$ 变为 $0$。
- 操作二，将第 $i$ 位上的数进行操作：$0$ 变为 $2$，$1$ 变为 $0$，$2$ 变为 $1$。
- 操作三，将第 $i$ 位上的数进行操作：$1$ 变为 $2$，$2$ 变为 $1$，$0$ 不变。

小洛一共要进行 $q$ 次操作。每次操作后，小洛需要得到三进制串代表的数值。请你告诉他。

如果对题意有不清晰之处，请查看样例解释。

inputFormat:
第一行输入两个正整数 $V,q$。

接下来 $q$ 行，每行一个操作，形如 `op i`。

请注意，你需要将 $V$ 转化为三进制串并作为初始的三进制串。

outputFormat: 输出共 $q$ 行，第 $i$ 行表示第 $i$ 个操作后的答案。

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

初始时，$V=4$，转化为小洛的三进制数为 $\texttt{1100 0000} \cdots$，接下来进行了 $3$ 次操作：

- 将第 $1$ 位上的数位从 $1$ 变为 $2$，三进制数变为 $\texttt{1200 0000} \cdots$，十进制下为 $7$。
- 将第 $0$ 位上的数位从 $1$ 变为 $0$，三进制数变为 $\texttt{0200 0000} \cdots$，十进制下为 $6$。
- 将第 $2$ 位上的数位从 $0$ 变为 $1$，三进制数变为 $\texttt{0210 0000} \cdots$，十进制下为 $15$。

**【数据范围】**

- 对于 $30\%$ 的数据，保证 $V\leq 10^9$。
- 对于另外 $30\%$ 的数据，保证不含操作三。

对于所有数据，保证 $0\leq V\leq 10^{18}$，$1\leq q\leq 10^5$，任意获取到的答案不超过 $2\times 10^{18}$。


title: [GESP202403 六级] 游戏

description:
你有四个正整数 $n,a,b,c$，并准备用它们玩一个简单的⼩游戏。

在一轮游戏操作中，你可以选择将 $n$ 减去 $a$，或是将 $n$ 减去 $b$。游戏将会进行多轮操作，直到当 $n \leq c$ 时游戏结束。

你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某
一轮游戏操作中，一种操作序列选择将 $n$ 减去 $a$，而另一种操作序列选择将 $n$ 减去 $b$。如果 $a=b$，也认为将 $n$ 减去 $a$ 与将 $n$ 减去 $b$ 是不同的操作。

由于答案可能很⼤，你只需要求出答案对 $10^9 + 7$ 取模的结果。

inputFormat: 一行四个整数 $n,a,b,c$。

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

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

- 对 $20\%$ 的数据，$a=b=c=1$，$n \leq 30$。
- 对 $40\%$ 的数据，$c = 1$，$n \leq 10^3$。
- 对全部的测试数据，保证 $1 \leq a,b,c \leq n \leq 2 \times 10^5$。


title: [GESP202403 六级] 好斗的牛

description:
你有 $10^9$ 个牛棚，从左到右一字排开。你希望把 $n$ 头牛安置到牛棚里。麻烦的是，你的牛很好斗，如果他们附近有其他的牛，他们就会不安分地去挑事。其中，第 $i$ 头牛的攻击范围是 $(a_i, b_i)$，这意味着，如果他的左边 $a_i$ 个牛棚或者右边 $b_i$ 个牛棚有其他牛，它就会去挑事。

你想留下一段连续的牛棚，并把其他牛棚都卖掉。请问您最少需要留下多少牛棚，才能保证至少存在一种方案能够把所有的 $n$ 头牛都安置进剩余的牛棚里，且没有牛会挑事？

inputFormat:
第一行一个正整数 $n$。
第二行 $n$ 个正整数 $a_1, a_2, \dots a_n$。
第三行 $n$ 个正整数 $b_1, b_2, \dots b_n$。

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

hint:
### 样例 1 解释

留下第 1、2、3、4 个牛棚，并在第 $1$、$4$ 两个牛棚分别放下两头牛。

### 数据规模与约定
- 对 $20\%$ 的数据，保证 $n = 2$。
- 另有 $20\%$ 的数据，保证 $n = 3$。
- 对 $80\%$ 的数据，保证 $n \leq 8$。
- 对于所有的测试数据，保证 $1 \leq n \leq 9$，$1 \leq a_i, b_i \leq 10^3$。


title: [语言月赛 202405] 数字取模

description:
小 S 的生日就要到了，小 Q 决定送给小 S 数字 $x$ 当做礼物。为此，她首先准备了一个四位数 $x$。

但是，小 S 并不喜欢 $\geq k$ 的数字。因此，小 Q 要将 $x$ 的**每一位**上的数字分别变成这一位数字除以 $k$ 得到的余数。

请你告诉小 Q 最终 $x$ 会变成什么样子。

inputFormat: 一行，两个用空格隔开的正整数 $x, k$，其中 $x$ 表示小 Q 准备的数字，保证是一个**四位正整数**。$k$ 的含义参照题目描述。

outputFormat: 一行，一个非负整数，表示 $x$ 每一位对 $k$ 取余后的数字。

hint:
### 样例 1 解释

数字 $7$ 对 $3$ 取余等于 $1$，数字 $4$ 对 $3$ 取余等于 $1$，因此最后 $x$ 会变成 $1102$。

### 样例 2 解释

两个 $7$ 对 $7$ 取余后都变为 $0$，于是整个数字都变成 $0$，注意不要输出多余的前导 $0$。样例 4 同理。

### 样例 3 解释

数字 $1, 2, 3, 4$ 都 $< 9$，所以整个数字不变。

### 数据范围

对于前 $30 \%$ 的数据，保证 $x$ 的十位、百位、千位都 $< k$。
对于另 $30 \%$ 的数据，保证 $x$ 的个位、十位、百位都 $< k$。
对于 $100 \%$ 的数据，保证 $1000 \leq x \leq 9999$，$1 \leq k \leq 9$。


title: [语言月赛 202405] 闰年

description:
当小 S 上网查资料时，她发现了一种叫做**真闰年**的年份。她发现，如果一个年份：

- 不是 $4$ 的倍数，则**不是真闰年**；
- 是 $4$ 的倍数，但不是 $100$ 的倍数，则**是真闰年**；
- 是 $100$ 的倍数，但不是 $400$ 的倍数，则**不是真闰年**；
- 是 $400$ 的倍数，但不是 $3200$ 的倍数，则**是真闰年**；
- 是 $3200$ 的倍数，但不是 $172800$ 的倍数，则**不是真闰年**；
- 是 $172800$ 的倍数，则**是真闰年**。

小 S 很好奇一些年份是否是**真闰年**。现在，她将给你一个年份 $y$，请你告诉她这一年是否为**真闰年**。

inputFormat: 一行，一个正整数 $y$，表示询问的年份。

outputFormat: 一行，一个字符串。若 $y$ 是真闰年，输出 `Yes`，否则输出 `No`。

hint:
### 样例解释

$2024$ 满足第 $1$ 条规则，所以是真闰年。
$2100$ 满足第 $2$ 条规则，所以不是真闰年。
$2400$ 满足第 $3$ 条规则，所以是真闰年。
$6400$ 满足第 $4$ 条规则，所以不是真闰年。
$518400$ 满足第 $5$ 条规则，所以是真闰年。

### 数据范围

对于前 $30 \%$ 的数据，保证 $y < 3200$；
对于另 $30 \%$ 的数据，保证 $y < 172800$；
对于 $100 \%$ 的数据，保证 $1 \leq y \leq 10^9$。


title: [语言月赛 202405] 小 S 大战小 Q

description:
小 S 和小 Q 带领着各自的队伍走上战台，一场激烈的战斗在所难免。在此开战之际，你作为观众，非常想要预测战斗的结果。

战斗规则是这样的：双方队伍各 $n$ 个人，比赛共 $n$ 局，第 $i$ 局双方都会派出自己的第 $i$ 名队员。

用 $a_i$ 来表示小 S 队伍中第 $i$ 名队员的战斗力，用 $b_i$ 来表示小 Q 队伍中第 $i$ 名队员的战斗力。那么对于第 $i$ 局比赛，战斗力**更大**的队员所在的一方获胜。如果两位队员战斗力相同，则该局**没有获胜方**。

最终：

- 如果小 S 队伍获胜的局数**大于**小 Q 队伍获胜的局数，则小 S 获得最终胜利；
- 如果小 S 队伍获胜的局数**小于**小 Q 队伍获胜的局数，则小 Q 获得最终胜利；
- 如果小 S 队伍获胜的局数**等于**小 Q 队伍获胜的局数，双方平局。

请你依次输出小 S 队伍获胜的局数和小 Q 队伍获胜的局数的值，并判断哪方获得最终胜利或双方平局。

inputFormat:
第一行，一个正整数 $n$，表示双方队员人数和战斗局数。
第二行，$n$ 个非负整数 $a_i$，表示小 S 队伍队员的战斗力。
第三行，$n$ 个非负整数 $b_i$，表示小 Q 队伍队员的战斗力。

outputFormat:
第一行，输出两个非负整数，依次表示小 S 队伍和小 Q 队伍获胜的局数。
第二行输出一个字符串。若小 S 队伍获胜，输出 `S`；若小 Q 队伍获胜，输出 `Q`；否则，输出 `Tie`。

hint:
### 样例 1 解释

三局的胜方分别是：小 S、小 S、小 Q。因此 小 S 队伍获胜 $2$ 次，小 Q 队伍获胜 $1$ 次，总获胜方是小 S。

### 样例 2 解释

除第 $4$ 局为小 Q 获胜外，其余局均为平局，所以小 S 队伍获胜 $0$ 次，小 Q 队伍获胜 $1$ 次，总获胜方是小 Q。

### 样例 3 解释

四局的胜方分别是：小 S、小 Q、小 Q、小 S。因此小 S 队伍获胜 $2$ 次，小 Q 队伍获胜 $2$ 次，双方总比分平局。

### 数据范围

对于前 $30 \%$ 的数据，保证双方总比分相等；
对于另 $30 \%$ 的数据，保证小 S 队伍获胜的局数**小于**小 Q 队伍获胜的局数；
对于 $100 \%$ 的数据，保证 $1 \leq n \leq 10^6, 0 \leq a_i, b_i \leq 10^9$。


title: [语言月赛 202405] 二进制

description:
在介绍十进制转二进制的篇目中，我们总会看到这样的方法：

- 求出这个数字除以 $2$ 的**商**和**余数**，然后将余数写在右侧，用商替换原来的数字；
- 重复以上过程直到这个数字变为 $0$；
- 最后将右侧的所有余数**倒序**排列，得到的就是原数字的二进制形式。

小 S 也在学习二进制，不过她很懒，不想计算那么多次除法。于是她找到了你，希望你能为她写一个程序，帮助她得到上述过程中所有的**商**和**余数**。

inputFormat: 一行，一个正整数 $n$，表示她想要转成二进制的数字。

outputFormat: 输出若干行，每一行两个数字 $x_i$ 和 $y_i$，表示第 $i$ 次除法得到的商和余数。你应该保证 $y_i$ 是 $0$ 或 $1$。

hint:
### 样例 1 解释

首先，$9 = 2 \times 4 + 1$，所以第一行输出 `4 1`，并令 $9$ 变为 $4$；
然后，$4 = 2 \times 2 + 0$，所以第二行输出 `2 0`，并令 $4$ 变为 $2$；
接着，$2 = 2 \times 1 + 0$，所以第三行输出 `1 0`，并令 $2$ 变为 $1$；
最后，$1 = 2 \times 0 + 1$，所以第四行输出 `0 1`，并令 $1$ 变为 $0$。过程结束。

### 样例 2 解释

首先，$22 = 2 \times 11 + 0$，所以第一行输出 `11 0`，并令 $22$ 变为 $11$；
然后，$11 = 2 \times 5 + 1$，所以第二行输出 `5 1`，并令 $11$ 变为 $5$；
接着，$5 = 2 \times 2 + 1$，所以第三行输出 `2 1`，并令 $5$ 变为 $2$；
再然后，$2 = 2 \times 1 + 0$，所以第四行输出 `1 0`，并令 $2$ 变为 $1$；
最后，$1 = 2 \times 0 + 1$，所以第五行输出 `0 1`，并令 $1$ 变为 $0$。过程结束。

### 数据范围

对于前 $30 \%$ 的数据，保证 $n$ 为若干个 $2$ 的乘积，且 $1 \leq n \leq 10^9$；
对于另 $30 \%$ 的数据，保证除法最多只进行 $3$ 次；
对于 $100 \%$ 的数据，保证 $1 \leq n \leq 10^{18}$。


title: Rochambeau

description: $N$ children are playing Rochambeau (scissors-rock-cloth) game with you. One of them is the judge. The rest children are divided into three groups (it is possible that some group is empty). You don’t know who is the judge, or how the children are grouped. Then the children start playing Rochambeau game for M rounds. Each round two children are arbitrarily selected to play Rochambeau for one once, and you will be told the outcome while not knowing which gesture the children presented. It is known that the children in the same group would present the same gesture (hence, two children in the same group always get draw when playing) and different groups for different gestures. The judge would present gesture randomly each time, hence no one knows what gesture the judge would present. Can you guess who is the judge after after the game ends? If you can, after how many rounds can you find out the judge at the earliest?

inputFormat: Input contains multiple test cases. Each test case starts with two integers $N$ and $M (1 \le N \le 500, 0 \le M \le 2,000)$ in one line, which are the number of children and the number of rounds. Following are M lines, each line contains two integers in $[0, N)$ separated by one symbol. The two integers are the IDs of the two children selected to play Rochambeau for this round. The symbol may be “=”, “>” or “<”, referring to a draw, that first child wins and that second child wins respectively.

outputFormat: There is only one line for each test case. If the judge can be found, print the ID of the judge, and the least number of rounds after which the judge can be uniquely determined. If the judge can not be found, or the outcomes of the M rounds of game are inconsistent, print the corresponding message.

translation:
### 题目描述

$N$ 个小朋友（编号为 $0,1,2,…,N−1$）一起玩石头剪子布游戏。

其中一人为裁判，其余的人被分为三个组（有可能有一些组是空的），第一个组的小朋友只能出石头，第二个组的小朋友只能出剪子，第三个组的小朋友只能出布，而裁判可以使用任意手势。

你不知道谁是裁判，也不知道小朋友们是怎么分组的。

然后，孩子们开始玩游戏，游戏一共进行 $M$
 轮，每轮从 $N$ 个小朋友中选出两个小朋友进行猜拳。

你将被告知两个小朋友猜拳的胜负结果，但是你不会被告知两个小朋友具体使用了哪种手势。

比赛结束后，你能根据这些结果推断出裁判是谁吗？

如果可以的话，你最早在第几轮可以找到裁判？

### 输入格式

输入可能包含多组测试用例。

每组测试用例第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含两个整数 $a,b$，中间夹着一个符号(`>`,`=`,`<`)，表示一轮猜拳的结果。

两个整数为小朋友的编号，`a>b` 表示 $a$ 赢了 $b$，`a=b` 表示 $a$ 和 $b$ 平手，`a<b` 表示 $a$ 输给了 $b$。

### 输出格式

每组测试用例输出一行结果。

+ 如果有且仅有一个人可能是裁判，则输出 `Player x can be determined to be the judge after y lines`，其中 $x$ 为裁判编号，$y$ 为确定裁判的最少轮数。

+ 如果无法确定裁判是谁，即裁判的人选多于 $1$ 个，则输出 `Can not determine`。

+ 如果在仅有一个裁判的情况下无法完成所有回合，则输出 `Impossible`。

### 数据范围

$1 \le N \le 500$，$1 \le M \le 2000$。

samples:
Can not determine
Player 1 can be determined to be the judge after 4 lines
Impossible
Player 0 can be determined to be the judge after 0 lines


title: SuperMemo

description:
Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, $A_1, A_2, \ldots A_n$. Then the host performs a series of operations and queries on the sequence which consists:

  * `ADD x y D`: Add $D$ to each number in sub-sequence $A_x \ldots A_y$. For example, performing "ADD 2 4 1" on $1, 2, 3, 4, 5$ results in $1, 3, 4, 5, 5$
  * `REVERSE x y`: reverse the sub-sequence ${A_x \ldots A_y}$. For example, performing "REVERSE 2 4" on $1, 2, 3, 4, 5$ results in $1, 4, 3, 2, 5$
  * `REVOLVE x y T`: rotate sub-sequence ${A_x \ldots A_y}$ $T$ times. For example, performing "REVOLVE 2 4 2" on $1, 2, 3, 4, 5$ results in $1, 3, 4, 2, 5$
  * `INSERT x P`: insert $P$ after $A_x$. For example, performing "INSERT 2 4" on $1, 2, 3, 4, 5$ results in $1, 2, 4, 3, 4, 5$
  * `DELETE x`: delete $A_x$. For example, performing "DELETE 2" on $1, 2, 3, 4, 5$ results in $1, 3, 4, 5$
  * `MIN x y`: query the participant what is the minimum number in sub-sequence $A_x \ldots A_y$. For example, the correct answer to "MIN 2 4" on $1, 2, 3, 4, 5$ is $2$

To make the show more interesting, the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.

inputFormat:
The first line contains $n$ ($n \leq 100000$).

The following $n$ lines describe the sequence.

Then follows $M$ ($M \leq 100000$), the numbers of operations and queries.

The following $M$ lines describe the operations and queries.

outputFormat: For each "MIN" query, output the correct answer.


title: [语言月赛 202405] 更好的交换

description:
小 S 有一个奇怪的机关拼图。这个拼图可以看作一个 $n$ 行 $n$ 列的方阵 $A$，第 $i$ 行第 $j$ 列的位置上有一个正整数 $A_{i, j}$。

与寻常拼图不同的是，这个机关拼图上的数字不能随意移动，必须按照如下规则**之一**操作：

- 选择拼图上的第 $x$ 行和第 $y$ 行，交换这两**行**；
- 选择拼图上的第 $x$ 列和第 $y$ 列，交换这两**列**。

为了复原这个拼图，小 S 将会操作共 $m$ 次，每次操作格式如下：

- `1 x y`，表示交换第 $x$ 行和第 $y$ 行；
- `0 x y`，表示交换第 $x$ 列和第 $y$ 列；

请你输出复原后的拼图。

inputFormat:
第一行，两个正整数 $n$ 和 $m$，分别表示拼图的行数、列数和总操作次数。
接下来 $n$ 行，每行 $n$ 个正整数 $A_{i, j}$，表示拼图上第 $i$ 行，第 $j$ 列上的数字。
接下来 $m$ 行，每行三个正整数 $op, x, y$，其中 $op$ 表示操作类型，$x, y$ 代表被操作的行号或列号。

outputFormat: 输出共 $n$ 行，每行 $n$ 个正整数，表示复原后的拼图。

hint:
### 样例 1 解释

第一次操作，交换了第 $2$ 列和第 $3$ 列；第二次操作，没有发生变化。

### 样例 2 解释

第一次操作，交换第 $2$ 行和第 $3$ 行，拼图变为：
$$
\begin{aligned}
11 \ 12 \ 13\\
\textcolor{red}{31 \ 32 \ 33}\\
\textcolor{blue}{21 \ 22 \ 23}
\end{aligned}
$$

第二次操作，交换第 $2$ 列和第 $3$ 列，拼图变为：
$$
\begin{aligned}
11 \ \textcolor{red}{13} \ \textcolor{blue}{12} \\
31 \ \textcolor{red}{33} \ \textcolor{blue}{32} \\
21 \ \textcolor{red}{23} \ \textcolor{blue}{22}
\end{aligned}
$$

### 数据范围

对于前 $30 \%$ 的数据，保证每一行数字相同；
对于前 $60 \%$ 的数据，保证 $1 \leq m \leq 3 \times 10^3$。
对于 $100 \%$ 的数据，保证 $1 \leq m \leq 10^6, 1 \leq n, A_{i, j} \leq 10^3, 1 \leq x, y \leq n$，$0 \leq op \leq 1$。


title: Computer

description:
A school bought the first computersome time ago(so this computer's id is 1). During the recent years the schol bought N-1 new computers. ach new computer wasconnected to one ofsetled eartier. Managers ofschool are anxious about slow finctioning ofthe net and want to know the maximum distance si for which i-thcomputer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.

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

Hint: he example input is coresponding to this graph. And from the graph, you can se that the computer 4 is farthest one from 1, so S1 =3. Computer 4 and 5 are the farthest ones from 2, so S2=2. Computer 5 is the farthest one from3.so S3=3. We also get S4=4，S5-4.

inputFormat: Input file contains multiple test cases.in each case there is natural number N (N<=1000) in the first line, folowed by (N-1) lines with descriptions of computers. ithline contains two natural numbers - number of computer.to which i-th computer is conected and leneth ofcable used for connection. "otaleneth of cable doe notexceed 10^9. Numbers in lines ofinput are separated by a space.

outputFormat: For each case output N lines. i-th line must contain number Si for i-th computer (1<-i<=N)


title: 『SpOI - R1』Lamborghini (Demo)

description:
给你一棵无根树，每个点 $i$ 有两个属性 $t_i,v_i$。

定义有向路径 $i\to j$ 的 $f_{i,j}$ 为：

- 若 $i\to j$ 上 $t_x$ 最小的点为 $x$ 且 $v_j\leq v_x\leq v_i$，则 $f_{i,j}=x$。
- 否则，$f_{i,j}=0$。

求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^n f_{i,j}$。

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

第二行 $n$ 个以空格分隔的整数，第 $i$ 项表示点 $i$ 的 $t_i$。

第三行 $n$ 个以空格分隔的整数，第 $i$ 项表示点 $i$ 的 $v_i$。

接下来 $n-1$ 行，每行两个整数 $a,b$，表示一条树边 $a\leftrightarrow b$。

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


title: K-Anonymous Sequence

outputFormat: For each test, output one line containing a single integer-the minimal cost

translation:
# K-Anonymous 序列

## 题目描述
各种应用领域中爆炸式增长的网络数据引发了相关个人的隐私问题。最近的研究表明，在发布图形/社交网络数据之前简单地删除节点的身份并不能保证隐私。图本身的结构及其基本形式——节点度，可以揭示个体的身份。
为了解决这个问题，我们研究了一个特定的图匿名化问题。我们称一个图为$k-anonymous$，如果对于每个节点$v$，图中至少存在$k-l$个与$v$具有相同程度的其他节点。我们感兴趣的是在具有最少图修改操作的图上实现$k-anonymous$。
我们简化了这个问题。从整个图$G$中选取$n$个节点，并按升序列出它们的度数。我们定义一个序列$k-anonymous$，如果对于每个元素$s$，序列中至少存在$k-1$个等于$s$的其他元素。要让给定的序列$k-anonymous$，你只能做一个操作——减少序列中的一些数字。我们定义了修改的成本，即你修改的所有数字的差值。例如，$k=3$的序列$2,2,3,4,4,5,5$可以修改为$2,2,2,4,4,4,4,4$，满足$3-anonymous$，修改的成本为$|3-2|+|5-4|+|5-4|=3$。
给出一个按升序排列的数字和$k$的序列，我们想知道在所有调整欧速序列$k-anonymous$的修改中，成本最小的修改。

## 输入格式
输入文件的第一行包含一个整数$T$$（1≤T≤20）$——输入文件中的测试数。每个测试都从包含两个数字$n$$（2≤n≤50000）$的行开始——序列中的数字数量和$k$$（2≤k≤n）$。它后面是$n$个整数的一行，即按升序排列的度数序列。序列中的每个数字$s$都在$[0,5000000]$范围内。

## 输出格式
对于每个测试，输出一行包含一个整数——最小成本。

---
翻译提供者：[csyc5586](https://www.luogu.com/user/668156)


title: Largest Submatrix

description: Now here is a matrix with letter 'a','b','c','w','x','y','z' and you can change 'w' to 'a' or 'b', change 'x' to 'b' or 'c', change 'y' to 'a' or 'c', and change 'z' to 'a', 'b' or 'c'. After you changed it, what's the largest submatrix with the same letters you can make?

inputFormat: The input contains multiple test cases. Each test case begins with $m$ and $n (1 <m,n< 1000)$ on line. Then come the elements of a matrix in row-major order on m lines each with n letters. The input ends once EOF is met.

outputFormat: For each test case, output one line containing the number of elements of the largest submatrix of all same letters.

translation:
### 题目描述

现在你有一个有 $n$ 行，$m$ 列的矩阵，它的每个元素都是 `a`，`b`，`c`，`w`，`x`，`y`，`z`，中的一个。现在你可以进行无限次如下操作：

- 将 `w` 替换为 `a` 或 `b`。
- 将 `x` 替换为 `b` 或 `c`。
- 将 `y` 替换为 `a` 或 `c`。
- 将 `z` 替换为 `a` 或 `b` 或 `c`。

在你操作结束后，这个矩阵最大的全部元素都相同的子矩阵的元素个数最多是多少？

### 输入格式

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

对于每组测试数据，第一行是两个整数 $n,m$，分别代表初始矩阵的行、列数。

之后的 $n$ 行，每行 $m$ 个字符，表示初始的矩阵。

### 输出格式

对于每组测试数据，输出一行，表示你操作结束后这个矩阵最大的全部元素都相同的子矩阵的元素个数的最大值。

### 样例解释

操作后的矩阵可以是这个样子：

```
abcw
wccc
```


title: [IOI2000] 邮局（原始版）

description:
高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。

邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

inputFormat:
第一行包含两个整数：第一个是村庄 $V$ 的数量，第二个是邮局的数量 $P$。

第二行包含 $V$ 个整数。这些整数是村庄的位置。

outputFormat: 第一行包含一个整数 $S$，它是每个村庄与其最近的邮局之间的所有距离的总和。

hint: 数据保证，$1 \le V \le 300$，$1 \le P \le 30$，$P \le V$，$1 \le X \le 10000$。


title: SUBSTRACT


title: 划分大理石

description: 有价值分别为 $1,2,\dots,6$ 的大理石各 $a_1,a_2,\dots,a_6$ 块，现要将它们分成两部分，使得两部分价值之和相等，问是否可以实现。其中大理石的总数不超过 $20000$。

inputFormat:
本题有多组数据，每组数据以单独的一行 $6$ 个整数呈现，分别表示 $a_1,a_2,\dots,a_6$。如果一行中 $6$ 个整数均为 $0$，表示输入文件结束。

对于每一个测试点，有效测试数据组数不超过 $100$ 组。

outputFormat: 对于每一组数据，如果划分成功，输出 `Can`，否则输出 `Can't`。


title: 扑克牌

description:
一副不含王的扑克牌由52张牌组成，由红桃、黑桃、梅花、方块4组牌组成，每组13张不同的面值。现在给定52 张牌中的若干张，请计算将它们排成一列，相邻的牌面值不同的方案数。

牌的表示方法为XY，其中X为面值，为2、3、4、5、6、7、8、9、T、J、Q、K、A中的一个。Y为花色，为S、 H、D、C中的一个。如2S、2H、TD等。

inputFormat:
第一行为一个整数T，为数据组数。

之后每组数据占一行。这一行首先包含一个整数N，表示给定的牌的张数，接下来N个由空格分隔的字符串，每个 字符串长度为2，表示一张牌。每组数据中的扑克牌各不相同。

outputFormat:
对于每组数据输出一行，形如"Case #X: Y"。X为数据组数，从1开始。Y为可能的方案数，由于答案可能很大，
请输出模 $2^{64}$ 之后的值。

samples:
5
1 TC
2 TC
5 2C 4 AC 6 AC
TS
AD AC JC JH
KC QC JC
AD AS JC JD KD


title: Cashier Employment

description:
A supermarket in Tehran is open 24 hours a day every day and needs a number of cashiers to fit its need. The supermarket manager has hired you to help him, solve his problem. The problem is that the supermarket needs different number of cashiers at different times of each day (for example, a few cashiers after midnight, and many in the afternoon) to provide good service to its customers, and he wants to hire the least number of cashiers for this job.

The manager has provided you with the least number of cashiers needed for every one-hour slot of the day. This data is given as R(0), R(1), ..., R(23): R(0) represents the least number of cashiers needed from midnight to 1:00 A.M., R(1) shows this number for duration of 1:00 A.M. to 2:00 A.M., and so on. Note that these numbers are the same every day. There are N qualified applicants for this job. Each applicant i works non-stop once each 24 hours in a shift of exactly 8 hours starting from a specified hour, say ti (0 <= ti <= 23), exactly from the start of the hour mentioned. That is, if the ith applicant is hired, he/she will work starting from ti o'clock sharp for 8 hours. Cashiers do not replace one another and work exactly as scheduled, and there are enough cash registers and counters for those who are hired.

You are to write a program to read the R(i) 's for i=0..23 and ti 's for i=1..N that are all, non-negative integer numbers and compute the least number of cashiers needed to be employed to meet the mentioned constraints. Note that there can be more cashiers than the least number needed for a specific slot.

inputFormat: The first line of input is the number of test cases for this problem (at most 20). Each test case starts with 24 integer numbers representing the R(0), R(1), ..., R(23) in one line (R(i) can be at most 1000). Then there is N, number of applicants in another line (0 <= N <= 1000), after which come N lines each containing one ti (0 <= ti <= 23). There are no blank lines between test cases.

outputFormat: For each test case, the output should be written in one line, which is the least number of cashiers needed. If there is no solution for the test case, you should write No Solution for that case.

translation:
## 题目描述
翻译：

德黑兰的一家超市每天24小时营业，需要聘请一定数量的收银员来满足其需求。超市经理想聘请你帮助他解决一个问题。这个问题是，超市在每天的不同时间段需要不同数量的收银员（例如，午夜后需要少量收银员，而在下午则需要很多）以向顾客提供良好的服务，他希望尽可能少聘请的收银员。
经理为你提供了每天每个一小时时段所需的最少收银员的数量。这些数据以 R(0) , R(1), ..., R(23)的形式给出：R(0)代表从午夜到凌晨1:00所需的最少收银员数量，R(1)表示从凌晨1:00到凌晨2:00所需的最少收银员数量，依此类推。请注意，这些数字每天都是一样的。有N名符合这项工作的申请人。每个申请人 **i** 每天工作一次，每次工作8小时，从指定的时间 **ti（0 <= ti <= 23）** 开始，即从提到的整点开始。也就是说，如果第 **i** 名申请人被聘用，他/她将从 **ti** 点整开始工作 **8** 小时。且 **收银员之间不互相替换，严格按照预定时间工作，并且超市为被聘用的人提供了足够的收银台和柜台。**

你需要编写一个程序来读取 **R(i)（i=0..23）和ti（i=1..N），** 这些都是 **非负整数** ，并计算出为满足上述约束条件所需聘用的 **最少** 收银员数量。请注意，**对于某个特定时段，实际聘用的收银员数量可能会多于该时段所需的最少收银员数量。**
## 输入格式
输入的第一行表示这个问题的测试用例数量（最多20个）。每个测试用例都以一行中的24个整数开始，这些整数分别代表R(0), R(1), ..., R(23)，即超市在每天每个一小时时段所需的最少收银员数量（R(i)的最大值为1000）。紧接着是另一行，包含一个整数N，表示申请这份工作的人数（0 <= N <= 1000）。之后是N行，每行包含一个ti（0 <= ti <= 23），表示第i名申请人开始工作的时间（以午夜为起点的小时数，精确到整点）。不同测试用例之间没有空行分隔。

对于每个测试用例，输出应该是一行，包含满足超市在每个时段对收银员需求所需的最少收银员数量。如果某个测试用例没有解决方案（即，即使使用所有申请人也无法满足超市在所有时段的收银员需求），则应该为该测试用例输出"No Solution"。
## 输出格式
对于每个测试用例，输出应该是一行，包含满足超市在每个时段对收银员需求所需的最少收银员数量。如果某个测试用例没有解决方案（即，无论如何安排收银员的工作时间，都无法满足超市在所有时段的收银员需求），则应该为该测试用例输出"No Solution"。


title: GF和猫咪的玩具

description:
GF 同学和猫咪得到了一个特别的玩具，这个玩具由 $n$ 个金属环（编号为 $1 \sim n$）和 $m$ 条绳索组成，每条绳索连接两个不同的金属环，并且长度相同。GF 左手拿起金属环 $L$，猫咪右手(或者说:爪)拿起金属环 $R\ (L \ne R)$，然后尽量的向两边拉，他希望选择合适的 $L$ 和 $R$，使得被拉紧的绳索尽量的多。

注：如果像样例那样 $1 \to 2 \to 4 \to 3 \to 5 \to 6 \to 1$ 构成了一个环，我们认为拉 $1$ 和 $3$ 时只能拉紧一边（$1 \to 2 \to 4 \to 3$ 或 $3 \to 5 \to 6 \to 1$）而不算全部拉紧。通俗地说，也就是当两个环之间有几个绳索数相等的连接方法时，只算其中一条连接方法拉紧，不算全部拉紧。

inputFormat:
第一行包含两个正整数 $n,m$（$n \le 100$）；

接下来的 $m$ 行包含两个正整数 $a,b$，表示有一条绳索连接了 $a$ 和 $b$ 的绳索。

outputFormat: 仅包含一个整数，表示最多能拉紧的绳索数。


title: Going Home

inputFormat:
There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H's and
'm's on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.

outputFormat: For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.

translation:
# 回家

## 题目描述
在网格地图上有 $n$ 个人和 $n$ 个房子。在每个单位时间里，每个人都可以在相邻的点上水平或垂直移动一个单位步。对于每个人，你需要为他每走一步支付 $1$ 美元的旅行费，直到他进入一所房子。由于每栋房子只能容纳一个人，这项任务很复杂。
你的任务是计算你需要支付的最低金额，以便将这 $n$ 个人送到那 $n$ 个不同的房子里。输入是场景的地图，`.` 表示空白空间，`H`表示该点上的房子，`m`表示在该点上有一个人。
你可以把网格地图上的每个点想象成一个相当大的正方形，所以它可以同时容纳 $n$ 个人物；此外，如果一个人在没有进入房子的情况下踩在有房子的网格上，也没关系。

## 输入格式

输入中有一个或多个测试用例。每种情况都以一行给出两个整数 $N$ 和 $M$ 开始，其中 $N$ 是映射的行数，$M$ 是列数。其余的输入将是描述地图的 $N$ 行。你可以假设 $N$ 和 $M$ 都在 $2$ 到 $100$ 之间，包括 $2$ 和 $100$。将有相同数量的 $H$ 和 $m$ 在地图上；最多有 $100$ 栋房子。$N$ 和 $M$ 的输入将以`0 0`终止。

## 输出格式

对于每个测试用例，输出一行带有单个整数的代码，这是您需要支付的最小金额（美元）。

---
翻译提供者：[csyc5586](https://www.luogu.com/user/668156)


title: Going from u to v or from v to u?

description: In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?

inputFormat:
The first line contains a single integer T, the number of test cases. And followed T cases.
The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.

outputFormat: The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.

translation:
# 从u到v还是从v到u？

### 题目描述

为了让儿子们变得勇敢，Jiajia 和 Wind 带他们去了一个大山洞。这个洞穴有 $n$ 个房间，还有连接一些房间的单向走廊。每次，Wind 都会选择两个房间 $x$ 和 $y$，并让他们的一个小儿子从一个房间走到另一个房间。儿子可以从 $x$ 到 $y$，也可以从 $y$ 到 $x$。Wind 承诺她的任务都是可能的，但她实际上不知道如何决定一个任务是否可能。为了让她的生活更轻松，Jiajia 决定选择一个洞穴，每一对房间都是一个可能的任务。给定一个洞穴，你能告诉 Jiajia 和 Wind 是否可以随意选择两个房间而不必担心任何事情吗？

### 输入格式

第一行包含一个整数 $T$ ，即测试用例的数量。
每种情况的第一行包含两个整数 $n，m$$（0<n<1001，m<6000）$，洞穴中的房间和走廊数量。接下来的$m$行各包含两个整数 $u$ 和 $v$，表示有一条走廊直接连接房间 $u$ 和房间 $v$。

### 输出格式

输出应包含 $T$ 行。如果洞穴具有上述属性，请写“`Yes`”，否则写“`No`”。


title: Place the Robots

description:
Robert is a famous engineer. One day he was given a task by his boss. The background of the task was the following:

Given a map consisting of square blocks. There were three kinds of blocks: Wall, Grass, and Empty. His boss wanted to place as many robots as possible in the map. Each robot held a laser weapon which could shoot to four directions (north, east, south, west) simultaneously. A robot had to stay at the block where it was initially placed all the time and to keep firing all the time. The laser beams certainly could pass the grid of Grass, but could not pass the grid of Wall. A robot could only be placed in an Empty block. Surely the boss would not want to see one robot hurting another. In other words, two robots must not be placed in one line (horizontally or vertically) unless there is a Wall between them.

Now that you are such a smart programmer and one of Robert's best friends, He is asking you to help him solving this problem. That is, given the description of a map, compute the maximum number of robots that can be placed in the map.

inputFormat:
The first line contains an integer T (<= 11) which is the number of test cases.

For each test case, the first line contains two integers m and n (1<= m, n <=50) which are the row and column sizes of the map. Then m lines follow, each contains n characters of '#', '*', or 'o' which represent Wall, Grass, and Empty, respectively.

outputFormat: For each test case, first output the case number in one line, in the format: "Case :id" where id is the test case number, counting from 1. In the second line just output the maximum number of robots that can be placed in that map.

translation:
### 题目描述

罗伯特是一位著名的工程师。一天，他的老板给了他一个任务。任务的背景如下：给定一个方格地图。地图上有三种可以放置的方块：墙方块、草方块和空地。老板希望在地图上可以尽可能多地放置机器人。每个机器人都配备了激光武器，可以同时向四个方向（东南西北，可以理解为上下左右）发射激光。机器人必须待在同一位置（也就是一开始放置的位置）且只能放在空地上不断地发射激光。激光束可以穿过草方块，但不能穿过墙方块。显然，老板不希望看到一个机器人伤害另一个机器人。换句话说，两个机器人不能放置在同一行或同一列上，除非它们之间有一堵墙。作为罗伯特的好朋友和聪明的程序员，他请你帮忙解决这个问题。也就是请你根据给定地图的描述，计算在地图上可以放置的最大机器人数量。

### 输入格式

 第一行包含一个整数 T ,表示测试用例的数量。对于每个测试用例，第一行包含两个整数 m 和 n ，分别表示地图的行数和列数。接下来是 m 行，每行包含 n 个字符，分别是 ‘#’, ‘*’, 或 ‘o’，表示墙方块、草方块和空地。

### 输出格式

 对于每个测试用例，首先输出一行，格式为：```Case :id```，其中 id 是测试用例编号，从 1 开始计数。1第二行输出在该地图上可以放置的最大机器人数量。

### 说明/提示

#### 数据范围

$T \leq 11$，$1 \leq m , n \leq 50$


title: Sightseeing

description:
Tour operator Your Personal Holiday organises guided bus trips across the Benelux. Every day the bus moves from one city S to another city F. On this way, the tourists in the bus can see the sights alongside the route travelled. Moreover, the bus makes a number of stops (zero or more) at some beautiful cities, where the tourists get out to see the local sights.

Different groups of tourists may have different preferences for the sights they want to see, and thus for the route to be taken from S to F. Therefore, Your Personal Holiday wants to offer its clients a choice from many different routes. As hotels have been booked in advance, the starting city S and the final city F, though, are fixed. Two routes from S to F are considered different if there is at least one road from a city A to a city B which is part of one route, but not of the other route.

There is a restriction on the routes that the tourists may choose from. To leave enough time for the sightseeing at the stops (and to avoid using too much fuel), the bus has to take a short route from S to F. It has to be either a route with minimal distance, or a route which is one distance unit longer than the minimal distance. Indeed, by allowing routes that are one distance unit longer, the tourists may have more choice than by restricting them to exactly the minimal routes. This enhances the impression of a personal holiday.

For example, for the above road map, there are two minimal routes from S = 1 to F = 5: 1 → 2 → 5 and 1 → 3 → 5, both of length 6. There is one route that is one distance unit longer: 1 → 3 → 4 → 5, of length 7.

Now, given a (partial) road map of the Benelux and two cities S and F, tour operator Your Personal Holiday likes to know how many different routes it can offer to its clients, under the above restriction on the route length.

inputFormat:
The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:

- One line with two integers N and M, separated by a single space, with 2 ≤ N ≤ 1,000 and 1 ≤ M ≤ 10, 000: the number of cities and the number of roads in the road map.
- M lines, each with three integers A, B and L, separated by single spaces, with 1 ≤ A, B ≤ N, A ≠ B and 1 ≤ L ≤ 1,000, describing a road from city A to city B with length L.The roads are unidirectional. Hence, if there is a road from A to B, then there is not necessarily also a road from B to A. There may be different roads from a city A to a city B.

- One line with two integers S and F, separated by a single space, with 1 ≤ S, F ≤ N and S ≠ F: the starting city and the final city of the route. There will be at least one route from S to F.

outputFormat: For every test case in the input file, the output should contain a single number, on a single line: the number of routes of minimal length or one distance unit longer. Test cases are such, that this number is at most 109 = 1,000,000,000.

translation:
中文标题：观光旅游

### 题目描述

旅游运营商 Your Personal Holiday 组织比荷卢经济联盟的导游巴士旅行。每天，巴士都会从一个城市 $S$ 行驶到另一个城市 $F$。在这条路上，巴士上的游客可以看到沿途的景点。此外，公共汽车在一些美丽的城市停靠了几站（零站或更多站），游客们可以在那里下车欣赏当地的风景。

不同的游客群体可能对他们想看的景点有不同的偏好，因此对从 $S$ 到 $F$ 的路线也有不同的喜好。因此，Your Personal Holiday 希望为客户提供许多不同路线的选择。由于酒店已提前预订，出发城市 $S$ 和最终城市 $F$ 是固定的。如果从城市 $A$ 到城市 $B$ 至少有一条道路是一条路线的一部分，而不是另一条路线，则认为从 $S$ 到 $F$ 的两条路线是不同的。

游客可以选择的路线有限制。为了在车站有足够的时间观光（并避免使用过多的燃料），公共汽车必须从 $S$ 到 $F$ 走一条短途路线。它必须是一条距离最小的路线，或者是一条比最小距离长一个距离单位的路线。事实上，通过允许延长一个距离单位的路线，游客可能比将他们限制在最短的路线上有更多的选择。这增强了个人假期的印象。

例如，对于上述路线图，从 $S=1$ 到 $F=5$ 有两条最小路线：$1→2→5$ 和 $1→3→5$，长度均为 $6$ 。有一条路线长一个距离单位：$1→3→4→5$，长度为 $7$。

现在，给定比荷卢经济联盟和两个城市 $S$ 和 $F$ 的部分路线图，旅游运营商 Your Personal Holiday 想知道在上述路线长度限制下，它可以为客户提供多少条不同的路线。

### 输入格式

输入文件的第一行包含一个数字：要遵循的测试用例的数量。每个测试用例都有以下格式：

- 一条由两个整数 $N$ 和 $M$ 组成的线，用一个空格隔开，$2≤N≤1000$，$1≤M≤10000$：路线图中的城市数量和道路数量。
- $M$ 条线，每条线有三个整数 $A$、$B$ 和 $L$，由单个空格分隔，$1≤A,B≤N$，$A \ne B$，$1≤L≤1000$，描述了一条从 $A$ 市到 $B$ 市的长度为 $L$ 的道路。这些道路是单向的。因此，如果有一条从 $A$ 到 $B$ 的路，那么从 $B$ 到 $A$ 就不一定也有路。从 $A$ 市到 $B$ 市可能有不同的路。

- 一条有两个整数 $S$ 和 $F$ 的线，用一个空格隔开，$1≤S,F≤N$，$S \ne F$ ：路线的起点城市和终点城市。从 $S$ 到 $F$ 至少有一条路线。

### 输出格式

对于输入文件中的每个测试用例，输出应该在一行上包含一个数字：最小长度或更长一个距离单位的路由数量。测试用例是这样的，这个数字最多为 $10^9=1000000000$。

---
翻译提供者：[csyc5586](https://www.luogu.com/user/668156)


title: 升降梯上

description:
开启了升降梯的动力之后，探险队员们进入了升降梯运行的那条竖直的隧道，映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄。

$Nescafé$ 之塔一共有 $N$ 层，升降梯在每层都有一个停靠点。

手柄有 $M$ 个控制槽，第 $i$ 个控制槽旁边标着一个数 $C_i$，满足 $C_1 < C_2 < C_3 <\dots< C_M$。

如果 $C_i>0$，表示手柄扳动到该槽时，电梯将上升 $C_i$ 层；如果 $C_i<0$，表示手柄扳动到该槽时，电梯将下降 $-C_i$ 层；并且一定存在一个 $C_i=0$，手柄最初就位于此槽中。

注意升降梯只能在 $1 \sim N$ 层间移动，因此扳动到使升降梯移动到 $1$ 层以下、$N$ 层以上的控制槽是不允许的。

电梯每移动一层，需要花费 $2$ 秒钟时间，而手柄从一个控制槽扳到相邻的槽，需要花费 $1$ 秒钟时间。

探险队员现在在 $1$ 层，并且想尽快到达 $N$ 层，他们想知道从 $1$ 层到 $N$ 层至少需要多长时间？

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

第二行 $M$ 个整数 $C_1,C_2,\dots C_M$。

outputFormat:
输出一个整数表示答案，即至少需要多长时间。

若不可能到达输出 $-1$。


title: 四叶草魔杖

description:
魔杖护法 Freda 融合了四件武器，于是魔杖顶端缓缓地生出了一棵四叶草，四片叶子幻发着淡淡的七色光。

圣剑护法 rainbow 取出了一个圆盘，圆盘上镶嵌着 $N$ 颗宝石，编号为 $0 \sim N-1$。

第 $i$ 颗宝石的能量是 $A_i$。

如果 $A\_i > 0$，表示这颗宝石能量过高，需要把 $A\_i$ 的能量传给其它宝石；如果 $A\_i < 0$，表示这颗宝石的能量过低，需要从其它宝石处获取 $-A\_i$ 的能量。

保证 $\sum A_i = 0$。

只有当所有宝石的能量均相同时，把四叶草魔杖插入圆盘中央，才能开启超自然之界的通道。

不过，只有 $M$ 对宝石之间可以互相传递能量，其中第 $i$ 对宝石之间无论传递多少能量，都要花费 $T_i$ 的代价。

探险队员们想知道，最少需要花费多少代价才能使所有宝石的能量都相同？

inputFormat:
第一行两个整数 $N、M$。

第二行 $N$ 个整数 $A_i$。

接下来 $M$ 行每行三个整数 $p\_i,q\_i,T\_i$，表示在编号为 $p\_i$ 和 $q\_i$ 的宝石之间传递能量需要花费 $T\_i$ 的代价。

数据保证每对 $p\_i、q\_i$ 最多出现一次。

outputFormat: 输出一个整数表示答案，无解输出 `Impossible`。


title: 太鼓达人

description:
太鼓达人的鼓坏了，现在 vani 来修鼓。

鼓的主要元件是 $M$ 个围成一圈的传感器。

每个传感器都有开和关两种工作状态，分别用 $1$ 和 $0$ 表示。

显然，从不同的位置出发沿顺时针方向连续检查 $K$ 个传感器可以得到 $M$ 个长度为 $K$ 的 $01$ 串。

Vani 知道这 $M$ 个 $01$ 串应该是互不相同的。

而且鼓的设计很精密，$M$ 会取到可能的最大值。

现在 Vani 已经了解到了 $K$ 的值，他希望你求出 $M$ 的值，并给出字典序最小的传感器排布方案。

inputFormat: 一个整数 $K$。

outputFormat:
一个整数和一个二进制串，由一个空格分隔，分别表示可能的最大的 $M$ 以及字典序最小的排布方案。

字符 $0$ 表示关，$1$ 表示开，你输出的串的第一个字和最后一个字是相邻的。


title: 最优高铁环

background:
幻影国建成了当今世界上最先进的高铁，该国高铁分为以下几类：

  * $S$—高速光子动力列车—时速 $1000km/h$
  * $G$—高速动车—时速 $500km/h$
  * $D$—动车组—时速 $300km/h$
  * $T$—特快—时速 $200km/h$
  * $K$—快速—时速 $150km/h$

该国列车车次标号由上述字母开头，后面跟着一个正整数($\le 1000$)构成。

description:
由于该国地形起伏不平，各地铁路的适宜运行速度不同。

因此该国的每一条行车路线都由 $K$ 列车次构成。

例如：$K=5$ 的一条路线为：$T120-D135-S1-G12-K856$。

当某一条路线的末尾车次与另一条路线的开头车次相同时，这两条路线可以连接起来变为一条更长的行车路线。

显然若干条路线连接起来有可能构成一个环。

若有 $3$ 条行车路线分别为:

$x\_1-x\_2-x_3$
$x\_3-x\_4$
$x\_4-x\_5-x_1$

$x\_1 \sim x\_5$ 车次的速度分别为 $v\_1 \sim v\_5$。

定义高铁环的值为(环上各条行车路线速度和)的平均值，即：

$[(v\_1+v\_2+v\_3)+(v\_3+v\_4)+(v\_4+v\_5+v\_1)]/3$

所有高铁环的值的最大值称为最优高铁环的值。

给出 $M$ 条行车路线，求最优高铁环的值。

inputFormat:
第一行为行车路线条数 $M$。

接下来 $M$ 行每行一条行车路线，由若干车次构成，各车次之间用 `-` 号隔开，车次的标号方式如上所述。

数据保证输入的合法性。

outputFormat:
输出最优高铁环的值，四舍五入到最接近的整数。

若不存在这样的环，输出 $-1$。

hint:
样例解释：
[(200+300+1000)+(1000+500)+(500+150+200)]/3=1283

数据范围：
50%的数据：0<M<=1000
100%的数据，0<M<=50000
每条行车路线车次个数不超过20.

输入数据较大，请使用read和scanf。数据不保证使用cin者不超时。
为避免精度问题，请使用double类型。
数据保证结果不超过2147483647.


title: 聚会

description:
$Y$ 岛风景美丽宜人，气候温和，物产丰富。

$Y$ 岛上有 $N$ 个城市（编号 $1,2,\dots,N$），有 $N-1$ 条城市间的道路连接着它们。

每一条道路都连接某两个城市。

幸运的是，小可可通过这些道路可以走遍 $Y$ 岛的所有城市。

神奇的是，乘车经过每条道路所需要的费用都是一样的。

小可可，小卡卡和小 $YY$ 经常想聚会，每次聚会，他们都会选择一个城市，使得 $3$ 个人到达这个城市的总费用最小。

由于他们计划中还会有很多次聚会，每次都选择一个地点是很烦人的事情，所以他们决定把这件事情交给你来完成。

他们会提供给你地图以及若干次聚会前他们所处的位置，希望你为他们的每一次聚会选择一个合适的地点。

inputFormat:
第一行两个正整数，$N$ 和 $M$，分别表示城市个数和聚会次数。

后面有 $N-1$ 行，每行用两个正整数 $A$ 和 $B$ 表示编号为 $A$ 和编号为 $B$ 的城市之间有一条路。

再后面有 $M$ 行，每行用三个正整数表示一次聚会的情况：小可可所在的城市编号，小卡卡所在的城市编号以及小 $YY$ 所在的城市编号。

outputFormat: 一共有 $M$ 行，每行两个数 $Pos$ 和 $Cost$，用一个空格隔开，表示第 $i$ 次聚会的地点选择在编号为 $Pos$ 的城市，总共的费用是经过 $Cost$ 条道路所花费的费用。


title: 逃不掉的路

description:
现代社会，路是必不可少的。

共有 $n$ 个城镇，$m$ 条道路，任意两个城镇都有路相连，而且往往不止一条。

但有些路年久失修，走着很不爽。

按理说条条大路通罗马，大不了绕行其他路呗——可小撸却发现：从 $a$ 城到 $b$ 城不管怎么走，总有一些逃不掉的必经之路。

他想请你计算一下，$a$ 到 $b$ 的所有路径中，有几条路是逃不掉的？

inputFormat:
第一行是 $n$ 和 $m$，用空格隔开。

接下来 $m$ 行，每行两个整数 $x$ 和 $y$，用空格隔开，表示 $x$ 城和 $y$ 城之间有一条长为 $1$ 的双向路。

第 $m+2$ 行是 $q$。

接下来 $q$ 行，每行两个整数 $a$ 和 $b$，用空格隔开，表示一次询问。

outputFormat:
对于每次询问，输出一个正整数，表示 $a$ 城到 $b$ 城必须经过几条路。

每个输出占一行。

hint:
$1\le n \le 10^5$，$1\le m \le 2\times 10^5$，$1\le q \le 10^5$
对于全部的数据，$1 \le x,y,a,b \le n$；对于任意的道路，两端的城市编号之差不超过 $10^4$；
任意两个城镇都有路径相连；同一条道路不会出现两次；道路的起终点不会相同;查询的两个城市不会相同。


title: 合并香蕉

description:
有 $n$ 条大香蕉，第 $i$ 条大香蕉可简化为一个正整数二元组 $(a_i,k_i)$，其中 $2\le k_i\le 10$。

初始时有 $n$ 堆大香蕉，第 $i$ 堆只包含第 $i$ 条大香蕉。

每次可以选择不同的两堆合并，合并时会损耗香蕉的大小。

具体地，如果第 $i$ 条香蕉**参与了合并**，则其大小 $a_i$ 会变为原来的 $\frac{1}{k_i}$ 倍。

**参与了合并**：合并前在两堆香蕉中的某一堆中。

你想把大香蕉们合为一堆，由于香蕉越大越好，你需要让操作结束后所有的 $a_i$ 之和**越大越好**。

考虑到求出最优解可能会比较困难，你只需要**尽可能接近标准答案**即可，具体参见**评分标准**。

为了防止你乱输出一个数，你还需要**输出方案**，具体参见**输出格式**。

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

接下来 $n$ 行，每行两个正整数代表 $a_i,k_i$。

outputFormat:
输出 $n-1$ 行，每行两个数 $x,y$ 代表合并第 $x$ 堆和第 $y$ 堆。

对于第 $i$ 次合并，我们记新形成的香蕉堆是第 $n+i$ 堆，而原来的两个香蕉堆（第 $x$ 堆、第 $y$ 堆）从此将**被视为不存在** ，所以之后的合并中不允许调用 $x$ 和 $y$，否则你将会爆零。


title: [GESP202403 七级] 交流问题

description:
来自两所学校 $A$、$B$ 的 $n$ 名同学聚在一起相互交流。为了方便起见，我们把这些同学从 $1$ 至 $n$ 编号。他们共进行了 $m$ 次交流，第 $i$ 次交流中，编号为 $u_i, v_i$ 的同学相互探讨了他们感兴趣的话题，并结交成为了新的朋友。

由于这次交流会的目的是促进两校友谊，因此只有不同学校的同学之间会交流。同校同学并不会互相交流。

作为 $A$ 校顾问，你对 $B$ 校的规模非常感兴趣，你希望求出 $B$ 校至少有几名同学、至多有几名同学。

inputFormat:
第一行两个正整数，表示同学的人数 $n$、交流的次数 $m$。
接下来 $m$ 行，每行两个整数 $u_i, v_i$，表示一次交流。

outputFormat: 输出一行两个整数，用单个空格隔开，分别表示 $B$ 校至少有几名同学、至多有几名同学。

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

- 对 $30\%$ 的数据，保证 $n \leq 17$，$m \leq 50$。
- 对 $60\%$ 的数据，保证 $n \leq 500$，$m \leq 2000$。
- 对全部的测试数据，保证 $1 \leq u_i, v_i \leq n \leq 10^5$，$1 \leq m \leq 2\times 10^5$，输入是合法的，即交流一定是跨校开展的。


title: [GESP202403 七级] 俄罗斯方块

description:
小杨同学用不同种类的俄罗斯方块填满了一个大小为 $n \times m$ 的网格图。

网格图由 $n \times m$ 个带颜色方块构成。小杨同学现在将这个网格图交给了你，请你计算出网格图中俄罗斯方块的种类数。
如果两个同色方块是四连通（即上下左右四个相邻的位置）的，则称两个同色方块直接连通；若两个同色方块同时与另一个同色方块直接或间接连通，则称两个同色方块间接连通。一个俄罗斯方块由一个方块和所有与其直接或间接连接的同色方块组成。定义两个俄罗斯方块的种类相同当且仅当通过**平移**其中一个俄罗斯方块可以和另一个俄罗斯方块重合；如果两个俄罗斯方块颜色不同，仍然视为同一种俄罗斯方块。

例如，在如下情况中，方块 $1$ 和方块 $2$ 是同一种俄罗斯方块，而方块 $1$ 和方块 $3$ **不是**同一种俄罗斯方块。

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

inputFormat:
第一行包含两个正整数 $n$ 和 $m$，表示网格图的大小。
对于之后的 $n$ 行，第 $i$ 行包含 $m$ 个正整数 $a_{i1}, a_{i2}, \dots a_{im}$，表示该行 $m$ 个方块的颜色。

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


title: 64位整数乘法

description: 求 $a$ 乘 $b$ 对 $p$ 取模的值。

inputFormat: 第一行输入整数 $a$，第二行输入整数 $b$，第三行输入整数 $p$。

outputFormat: 输出一个整数，表示 `a*b mod p` 的值。


title: 最短 Hamilton 路径

description:
给定一张 $n$ 个点的带权无向图，点从 $0 \sim n-1$ 标号，求起点 $0$ 到终点 $n-1$ 的最短 Hamilton 路径。

Hamilton 路径的定义是从 $0$ 到 $n-1$ 不重不漏地经过每个点恰好一次。

inputFormat:
第一行输入整数 $n$。

接下来 $n$ 行每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示点 $i-1$ 到 $j-1$ 的距离（记为 $a[i-1,j-1]$）。

对于任意的 $x,y,z$，数据保证 $a[x,x]=0，a[x,y]=a[y,x]$ 并且 $a[x,y]+a[y,z] \ge a[x,z]$。

outputFormat: 输出一个整数，表示最短 Hamilton 路径的长度。

hint: 对于所有测试数据满足 $1 \le n \le 20$，$0 \le a[i,j] \le 10^7$


title: 不等关系 加强版

background: 本题是[不等关系](https://loj.ac/p/575)的加强版，建议大家先做原题后再来挑战加强版。

description:
对于一个字符串 $s_1,s_2,\cdots ,s_n$，仅包含 `<` 和 `>` 两种字符。

设 $f(s)$ 为「使得 $p_i<p_{i+1}$ 当且仅当 $s_i$ 为 `<` 的排列 $p_1,p_2,\cdots ,p_{n+1}$」的数量。

现在请你求出，对于所有 $2^n$ 种长度为 $n$ 的字符串 $s$，$f(s)$ 之和是多少。

由于答案可能有点大，因此你只需要输出它对 $998244353$ 取模的结果。

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

outputFormat: 输出一行一个整数，表示满足要求的排列数量对 $998244353$ 取模的结果。


title: Fire and Big

description:
小 F 要和其他人玩游戏，但他不想输，所以来找你帮他研究策略。

有 $m$ 个石子，小 F 和小 B 轮流取石子，小 F 先开始取，不能取的人输。

给定正整数 $n$，每次取石子的个数 $k$（$k$ 是正整数） 必须满足如下两个条件**之一**：

- $k$ 是 $n$ 的倍数。
- $k$ 是 $<n$ 的完全平方数。

他们要玩 $T$ 局游戏，不过每一局游戏的 $n$ 不变，只有石子个数 $m$ 会变。

对于每一局，假设两人足够聪明，问谁有必胜策略。

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

第二行，$T$ 个正整数 $m$，表示每一局游戏的石子个数。

outputFormat: 输出一行一个长为 $T$ 的字符串，每个字符为 `F` 或者 `B`，分别表示这一局游戏先手必胜与后手必胜。


title: 组合型枚举

description: 从 $1 \sim n$ 这 $n$ 个整数中随机选出 $m$ 个，输出所有可能的选择方案。

inputFormat: 两个整数 $n, m$ ,在同一行用空格隔开。

outputFormat:
按照从小到大的顺序输出所有方案，每行 $1$ 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 `1 3 5 7` 排在 `1 3 6 8` 前面）。

hint: 对于所有测试数据满足 $0 \le m \le n$ ,  $ n+(n-m) \le 25 $。