title: [CEOI 2009] Harbingers

description:
给定一颗树，树中每个结点有一个邮递员，每个邮递员要沿着唯一的路径走向 capital（$1$ 号结点），每到一个城市他可以有两种选择：

1. 继续走到下个城市；
2. 让这个城市的邮递员替他出发。

每个邮递员出发需要一个准备时间 $W_i$，他们的速度是 $V_i$，表示走一公里需要多少分钟。现在要你求出每个城市的邮递员到 capital 的最少时间（不一定是他自己到 capital，可以是别人帮他）？

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

接下来 $N-1$ 行，每行三个正整数 $A,B,C$，表示结点 $A$ 和 $B$ 之间有一条长度为 $C$ 的边；

再接下来 $N-1$ 行，每行 $2$ 个整数 $W_i,V_i$。

outputFormat: 输出每个城市的邮递员到 capital 的最少时间。

hint:
对于 $20\%$ 的数据，$N\leq 2500$；

对于 $50\%$ 的数据，树是一条链；

对于所有数据，$3\leq N\leq 10^5$，$0\leq W_i,V_i\leq 10^9$，每条边长度不超过 $10^4$。


title: BZOJ4372 烁烁的游戏

type: P

background:
题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。

---

烁烁很喜欢爬树，这吓坏了树上的皮皮鼠。

给定一颗 $n$ 个节点的树，边权均为 $1$，初始树上没有皮皮鼠。

烁烁他每次会跳到一个节点 $u$ ，把周围与他距离不超过 $d$ 的节点各吸引出 $w$ 只皮皮鼠。皮皮鼠会被烁烁吸引，所以会一直待在节点上不动。

烁烁很好奇，在当前时刻，节点 $u$ 有多少个他的好朋友——皮皮鼠。

description:
题目背景可以被抽象成这个问题：

给一棵 $n$ 个结点的树，边权均为 $1$，初始点权均为 $0$。进行 $m$ 次操作：
- $\text{Q x}$：询问结点 $x$ 的点权。
- $\text{M x d w}$：将树上与结点 $x$ 距离不超过 $d$ 的节点的点权均加上 $w$。

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

接下来的 $n-1$ 行，每行三个正整数 $u,v$，代表 $u,v$ 之间有一条边。

接下来的 $m$ 行，每行给出上述两种操作中的一种。

outputFormat: 对于每个 $Q$ 操作，输出当前 $x$ 结点的点权。

hint: 对于所有数据，保证 $1\leq n,m\leq 10^5$，$|w|\leq 10^4$。注意：$w$ 不一定为正整数，


title: BZOJ4317 Atm 的树

background:
题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。

---

Atm 有一段时间在虐 qtree 的题目，于是，他满脑子都是 tree，tree，tree……

description:
于是，一天晚上他梦到自己被关在了一个有根树中，每条路径都有边权，一个神秘的声音告诉他，每个点到其他的点有一个距离，他需要对于每个点回答：从这个点出发的第 $k$ 小距离是多少；

如果 atm 不能回答出来，那么明天 4019 的闹钟将不会响，4019 全寝可能就迟到了，所以 atm 希望你帮帮他。

inputFormat:
第一行两个整数 $n,k$，表述询问的树的结点个数，以及题目中的 $k$。

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

outputFormat: 共 $n$ 行，第 $i$ 行表示从结点 $i$ 出发的第 $k$ 小距离为多少。

hint: 对于所有数据，$1\leq n\leq 15000$，$1\leq k\leq 5000$，$1\leq w\leq 10$。树的根为结点 $1$。


title: [Baltic2001] Box of Mirrors

description:
数学家 Andris 有一个小盒子，其底部是 $n\times m$ 的格子，每个格子可以放一面 $45$ 度朝向的镜子。

在盒子的边界，每行每列的两端，有一些孔，光线可以从中射入盒子，也可以射出。

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

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

如上图所示，从孔 $2$ 射进盒子的光线经过两次反射后又从孔 $7$ 射出。

Andris 想请你设计一个盒子，使得从每个孔射入的光线都会从指定的孔射出。

例如，如果他希望从 $10$ 个孔里射入的光线分别由孔 $9,7,10,8,6,5,2,4,1,3$ 射出，则上图也是一个满足要求的盒子。

注意，孔的编号如图从 $1$ 到 $2\times (n+m)$ 编号。

inputFormat:
第一行两个整数 $n,m$，表示盒子的大小。

接下来 $2\times (n+m)$ 行，第 $i+1$ 行一个整数 $a_i$，表示从第 $i$ 个孔射入的光线要从第 $a_i$ 个孔中射出。

outputFormat: 输出一个 $n\times m$ 的矩阵，对于每个位置，$0$ 表示不放镜子，$1$ 表示放镜子，需要满足对应的要求。数据保证一定有解。

hint: 对于 $100\%$ 的数据，$1\leq n,m\leq 100$，$1\leq a_i\leq 2\times (n+m)$。


title: [PA2008] Cliquers

description:
统计结点个数为 $n$，且每一个连通分量都是完全图的本质不同的图的个数 $x$。

求 $m^x \bmod P$，其中 $P=10^9-401$ 为一个质数。

inputFormat: 一行两个整数，分别为 $n,m$。

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

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

当 $n=3$ 时，$3$ 种情况如下图所示。注意您应当输出的是 $m^x \bmod P=2^3 \bmod (10^9-401)$ 的值。

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

**【数据范围】**

对于所有数据，$1\leq n,m\leq 2\times 10^5$。


title: [ICPC2013 WF] Self-Assembly

description:
Automatic Chemical Manufacturing is experimenting with a process called self-assembly. In this process, molecules with natural affinity for each other are mixed together in a solution and allowed to spontaneously assemble themselves into larger structures. But there is one problem: sometimes molecules assemble themselves into a structure of unbounded size, which gums up the machinery.

You must write a program to decide whether a given collection of molecules can be assembled into a structure of unbounded size. You should make two simplifying assumptions: 1) the problem is restricted to two dimensions, and 2) each molecule in the collection is represented as a square. The four edges of the square represent the surfaces on which the molecule can connect to other compatible molecules.

In each test case, you will be given a set of molecule descriptions. Each type of molecule is described by four two-character *connector labels* that indicate how its edges can connect to the edges of other molecules. There are two types of connector labels:

- An uppercase letter $(A, \dots , Z)$ followed by $+$ or $−$. Two edges are compatible if their labels have the same letter but different signs. For example, $A+$ is compatible with $A-$ but is not compatible with $A+$ or $B-$.
- Two zero digits $00$. An edge with this label is not compatible with any edge (not even with another edge labeled $00$).

Assume there is an unlimited supply of molecules of each type, which may be rotated and reflected. As the molecules assemble themselves into larger structures, the edges of two molecules may be adjacent to each other only if they are compatible. It is permitted for an edge, regardless of its connector label, to be connected to nothing (no adjacent molecule on that edge).

Figure A.1 shows an example of three molecule types and a structure of bounded size that can be assembled from them (other bounded structures are also possible with this set of molecules).

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

inputFormat: The input consists of a single test case. A test case consists of two lines. The first contains an integer $n(1 \leq n \leq 40 000)$ indicating the number of molecule types. The second line contains $n$ eight-character strings, each describing a single type of molecule, separated by single spaces. Each string consists of four two-character connector labels representing the four edges of the molecule in clockwise order.

outputFormat:
Display the word `unbounded` if the set of molecule types can generate a structure of unbounded size.
Otherwise, display the word `bounded`.

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

自动化化学制造正在试验一种称为自组装的过程。在这个过程中，具有天然亲和力的分子被混合在一起，并允许它们自发地组装成更大的结构。但有一个问题：有时分子会自组装成无限大的结构，导致设备故障。

你必须编写一个程序来决定给定的分子集合是否可以组装成一个无限大的结构。你应该做两个简化假设：1）问题仅限于二维，2）集合中的每个分子表示为一个正方形。正方形的四个边代表分子可以连接到其他兼容分子的表面。

在每个测试用例中，你将得到一组分子描述。每种类型的分子由四个两个字符的*连接标签*描述，指示其边缘如何连接到其他分子的边缘。有两种类型的连接标签：

- 一个大写字母 $(A, \dots , Z)$ 后跟 $+$ 或 $−$。如果两个边的标签具有相同的字母但符号不同，则它们是兼容的。例如，$A+$ 与 $A-$ 兼容，但与 $A+$ 或 $B-$ 不兼容。
- 两个数字 $00$。带有此标签的边与任何边都不兼容（即使是另一个标记为 $00$ 的边也不兼容）。

假设每种类型的分子都有无限供应，并且可以旋转和反射。随着分子自组装成更大的结构，两个分子的边只有在兼容时才可以相邻。允许边缘（无论其连接标签如何）不连接到任何东西（该边没有相邻分子）。

图 A.1 显示了三种分子类型的示例以及可以从中组装的有限大小结构（使用该分子集也可以组装其他有限结构）。

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

**【输入格式】**

输入由一个测试用例组成。一个测试用例由两行组成。第一行包含一个整数 $n(1 \leq n \leq 40 000)$，表示分子类型的数量。第二行包含 $n$ 个八字符的字符串，每个字符串描述一种分子的类型，单个空格分隔。每个字符串由四个两个字符的连接标签组成，按顺时针顺序表示分子的四个边。

**【输出格式】**

如果这组分子类型可以生成一个无限大的结构，则显示单词 `unbounded`。否则，显示单词 `bounded`。

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


title: [ICPC2013 WF] Hey, Better Bettor

background:
> “In the casino, the cardinal rule is to keep them playing and to keep them coming back. The
longer they play, the more they lose, and in the end, we get it all.”
> (from the 1995 film *Casino*)

description:
Recent recessions have not been kind to entertainment venues, including the gambling industry. Competition is fierce among casinos to attract players with lots of money, and some have begun to offer especially sweet deals. One casino is offering the following: you can gamble as much as you want at the casino. After you are finished, if you are down by any amount from when you started, the casino will refund $x\%$ of your losses to you. Obviously, if you are ahead, you can keep all of your winnings. There is no time limit or money limit on this offer, but you can redeem it only once.

For simplicity, assume all bets cost $1$ dollar and pay out $2$ dollars. Now suppose $x$ is $20$. If you make $10$ bets in total before quitting and only $3$ of them pay out, your total loss is $3.2$ dollars. If $6$ of them pay out, you have gained $2$ dollars.

Given $x$ and the percentage probability $p$ of winning any individual bet, write a program to determine the maximum expected profit you can make from betting at this casino, using any gambling strategy.

inputFormat: The input consists of a single test case. A test case consists of the refund percentage $x (0 \leq x < 100)$ followed by the winning probability percentage $p (0 \leq p < 50)$. Both $x$ and $p$ have at most two digits after the decimal point.

outputFormat: Display the maximum expected profit with an absolute error of at most $10^{-3}$.

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

> “在赌场里，首要规则是让他们继续玩，让他们不断回来。他们玩得越久，输得越多，最终，我们会赢得一切。”
> （摘自 1995 年电影《赌场》）

最近的经济衰退对包括赌博业在内的娱乐场所并不友好。赌场之间竞争激烈，以吸引有钱的玩家，一些赌场开始提供特别优厚的优惠。其中一个赌场提供以下优惠：你可以在赌场里随意赌博。当你结束时，如果你比开始时输了任何金额，赌场将退还你损失的 $x\%$。显然，如果你赢钱了，你可以保留所有的奖金。此优惠没有时间限制或金额限制，但你只能兑现一次。

为了简化，假设所有赌注的成本为 $1$ 美元，并支付 $2$ 美元。现在假设 $x$ 是 $20$。如果你在退出前总共下注 $10$ 次，只有 $3$ 次获胜，你的总损失是 $3.2$ 美元。如果 $6$ 次获胜，你就赚了 $2$ 美元。

给定 $x$ 和赢得任何单个赌注的概率百分比 $p$，编写一个程序来确定你在这个赌场下注所能获得的最大期望利润，使用任何赌博策略。

输入由一个单一的测试用例组成。测试用例包含退款百分比 $x (0 \leq x < 100)$，随后是赢得概率百分比 $p (0 \leq p < 50)$。$x$ 和 $p$ 的小数点后最多有两位数字。

显示最大期望利润，绝对误差不超过 $10^{-3}$。

**【输入格式】**

输入由一个单一的测试用例组成。测试用例包含退款百分比 $x (0 \leq x < 100)$，随后是赢得概率百分比 $p (0 \leq p < 50)$。$x$ 和 $p$ 的小数点后最多有两位数字。

**【输出格式】**

输出最大期望利润，绝对误差不超过 $10^{-3}$。

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


title: [ICPC2013 WF] Surely You Congest

description:
You are in charge of designing an advanced centralized traffic management system for smart cars. The goal is to use global information to instruct morning commuters, who must drive downtown from the suburbs, how best to get to the city center while avoiding traffic jams.

Unfortunately, since commuters know the city and are selfish, you cannot simply tell them to travel routes that take longer than normal (otherwise they will just ignore your directions). You can only convince them to change to different routes that are equally fast.

The city’s network of roads consists of intersections that are connected by bidirectional roads of various travel times. Each commuter starts at some intersection, which may vary from commuter to commuter. All commuters end their journeys at the same place, which is downtown at intersection 1. If two commuters attempt to start travelling along the same road in the same direction at the same time, there will be congestion; you must avoid this. However, it is fine if two commuters pass through the same intersection simultaneously or if they take the same road starting at different times.

Determine the maximum number of commuters who can drive downtown without congestion, subject to all commuters starting their journeys at exactly the same time and without any of them taking a suboptimal route.

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

In Figure C.1, cars are shown in their original locations. One car is already downtown. Of the cars at intersection 4, one can go along the dotted route through intersection 3, and another along the dashed route through intersection 2. But the remaining two cars cannot reach downtown while avoiding congestion. So a maximum of 3 cars can reach downtown with no congestion.

inputFormat: The input consists of a single test case. The first line contains three integers $n, m,$ and $c$, where $n (1 \leq n \leq 25 000)$ is the number of intersections, $m (0 \leq m \leq 50 000)$ is the number of roads, and $c (0 \leq c \leq 1 000)$ is the number of commuters. Each of the next $m$ lines contains three integers $x_i, y_i$, and $t_i$ describing one road, where $x_i$ and $y_i (1 \leq x_i, y_i \leq n)$ are the distinct intersections the road connects, and $t_i (1 \leq t_i \leq 10 000)$ is the time it takes to travel along that road in either direction. You may assume that downtown is reachable from every intersection. The last line contains $c$ integers listing the starting intersections of the commuters.

outputFormat: Display the maximum number of commuters who can reach downtown without congestion.

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

你负责设计一个先进的集中交通管理系统，以便为智能汽车提供服务。目标是利用全局信息指导早晨从郊区驾车前往市中心的通勤者，帮助他们避免交通拥堵。

不幸的是，由于通勤者了解城市且自私，你不能简单地让他们走比平时更慢的路线（否则他们会忽略你的指示）。你只能说服他们改变到同样快的不同路线。

城市的道路网络由连接双向道路的交叉口组成，各条道路的行驶时间不同。每个通勤者从某个交叉口出发，这些交叉口因人而异。所有通勤者的行程终点都是市中心的 1 号交叉口。如果两名通勤者同时在同一方向上行驶在同一条道路上，会造成拥堵；你必须避免这种情况。然而，如果两名通勤者同时经过同一个交叉口或者在不同时间使用同一条道路，这是允许的。

确定在所有通勤者同时开始旅程且没有任何人走次优路线的情况下，最多有多少通勤者可以在不拥堵的情况下开车到市中心。

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

**【输入格式】**

输入由一个单独的测试用例组成。第一行包含三个整数 $n, m, c$，其中 $n (1 \leq n \leq 25 000)$ 表示交叉口的数量，$m (0 \leq m \leq 50 000)$ 表示道路的数量，$c (0 \leq c \leq 1 000)$ 表示通勤者的数量。接下来的 $m$ 行中的每一行包含三个整数 $x_i, y_i, t_i$，描述了一条道路，其中 $x_i$ 和 $y_i (1 \leq x_i, y_i \leq n)$ 是道路连接的不同交叉口，$t_i (1 \leq t_i \leq 10 000)$ 是沿该道路行驶的时间。最后一行包含 $c$ 个整数，列出了通勤者的起始交叉口。

**【输出格式】**

显示最多有多少通勤者可以在不拥堵的情况下到达市中心。

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


title: [ICPC2013 WF] Factors

description:
The fundamental theorem of arithmetic states that every integer greater than $1$ can be uniquely represented as a product of one or more primes. While unique, several arrangements of the prime factors may be possible. For example:

- $10=2\times 5=5\times 2$；
- $20=2\times 2\times 5=2\times 5\times 2=5\times 2\times 2$；

Let $f(k)$ be the number of different arrangements of the prime factors of $k$. So $f(10) = 2$ and $f(20) = 3$.

Given a positive number $n$, there always exists at least one number $k$ such that $f(k) = n$. We want to know the smallest such $k$.

inputFormat: The input consists of at most $1 000$ test cases, each on a separate line. Each test case is a positive integer $n < 2^{63}$.

outputFormat: For each test case, display its number $n$ and the smallest number $k > 1$ such that $f(k) = n$. The numbers in the input are chosen such that $k < 2^{63}$.

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

算术基本定理指出，每个大于 $1$ 的整数都可以唯一表示为一个或多个素数的乘积。虽然表示是唯一的，但素数因子的排列可能有多种。例如：

- $10=2\times 5=5\times 2$；
- $20=2\times 2\times 5=2\times 5\times 2=5\times 2\times 2$；

令 $f(k)$ 为 $k$ 的素数因子不同排列的数量。因此，$f(10) = 2$ 且 $f(20) = 3$。

给定一个正整数 $n$，总是至少存在一个数字 $k$ 使得 $f(k) = n$。我们想知道最小的这样的 $k$。

**【输入格式】**

输入包含最多 $1 000$ 个测试用例，每个测试用例占一行。每个测试用例是一个正整数 $n < 2^{63}$。

**【输出格式】**

对于每个测试用例，输出其数字 $n$ 以及最小的 $k > 1$ 使得 $f(k) = n$。输入中的数字选择使得 $k < 2^{63}$。

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


title: [ICPC2013 WF] Harvard

description:
The term “Harvard architecture” applies to a computer that has physically separate memories for instructions and data. The term originated with the Harvard Mark I computer, delivered by IBM in 1944, which used paper tape for instructions and relays for data.

Some modern microcontrollers use the Harvard architecture – but not paper tape and relays! Data memory is organized in banks, each containing the same number of data items. Each data-referencing instruction has a byte offset $f$ to a bank, and a bit $a$ that is used to select the bank to be referenced. If $a$ is $0$, then bank $0$ is referenced. If $a$ is $1$, then the value in a *bank select register* (BSR) identifies the bank to be used. Assume each instruction takes the same time to execute, and there is an instruction that can set the BSR’s value.

For example, suppose there are $4$ banks of $8$ bytes each. To access location $5$, either use a single instruction with $a = 0$ and $f = 5$, or set the BSR to $0$ in one instruction and then use an instruction with $a = 1$ and $f = 5$. The first approach is faster since it does not require setting the BSR.

Now suppose (with the same memory) the location to access is $20$. Only one approach will work here: execute an instruction that sets the BSR to $2$ (unless the BSR already has the value $2$) and then use an instruction with $a = 1$ and $f = 4$.

A program is a sequence of operations. Each operation is either

- a variable reference, written as V$i$, where $i$ is a positive integer, or
- a repetition, written as R$n$ `<program>` E, where $n$ is a positive integer and `<program>` is an arbitrary program. This operation is equivalent to n sequential occurrences of `<program>`.

Your problem is to determine the minimum running time of programs. In particular, given the number and size of the memory banks and a program to be executed, find the minimum number of instructions (which reference memory location and possibly set the BSR) that must be executed to run the program. To do this you must identify a mapping of variables to memory banks that yields the smallest execution time, and report that execution time – that is, the number of memory references and BSR register settings required. The BSR’s value is initially undefined, and changes only when an instruction explicitly sets its value.

inputFormat:
The input consists of a single test case. A test case consists of two lines. The first line contains two integers $b$ and $s$, where $1 \leq b \leq 13$ is the number of memory banks and $1 \leq s \leq 13$ is the number of variables that can be stored in each memory bank. The second line contains a non-empty program with at most $1 000$ space-separated elements (each R$n$, V$i$, and E counts as one element).

You may assume the following:
- In a repetition R$n$, the number of repetitions satisfies $1 \leq n \leq 10^6$.
- In a loop operation R$n$ `<program>` E, the loop body `<program>` is not empty.
- In a variable reference V$i$, the variable index satisfies $1 \leq i \leq \min(b \times s, 13)$.
- The total number of variable references performed by an execution of the program is at most $10^{12}$.

outputFormat: Display the minimum number of instructions that must be executed to complete the program.

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

“哈佛架构”一词适用于指令和数据具有物理上分开的存储器的计算机。该术语起源于哈佛 Mark I 计算机，由 IBM 于 1944 年交付，该计算机使用纸带作为指令，使用继电器作为数据。

一些现代微控制器使用哈佛架构——但不使用纸带和继电器！数据存储器被组织成多个存储区（bank），每个存储区包含相同数量的数据项。每条引用数据的指令都有一个字节偏移量 $f$ 和一个位 $a$，用于选择要引用的存储区。如果 $a$ 为 $0$，则引用存储区 $0$。如果 $a$ 为 $1$，则在*存储区选择寄存器*（BSR）中的值标识要使用的存储区。假设每条指令执行时间相同，并且存在可以设置 BSR 值的指令。

例如，假设有 $4$ 个存储区，每个存储区有 $8$ 个字节。要访问位置 $5$，可以使用 $a = 0$ 和 $f = 5$ 的单条指令，或者在一条指令中将 BSR 设置为 $0$，然后使用 $a = 1$ 和 $f = 5$ 的指令。第一种方法更快，因为它不需要设置 BSR。

现在假设（使用相同的存储器）要访问的位置是 $20$。这里只能使用一种方法：执行一条指令将 BSR 设置为 $2$（除非 BSR 已经是 $2$），然后使用 $a = 1$ 和 $f = 4$ 的指令。

程序是操作的序列。每个操作可以是

- 变量引用，写作 V$i$，其中 $i$ 是正整数，或
- 重复，写作 R$n$ `<program>` E，其中 $n$ 是正整数，`<program>` 是任意程序。此操作相当于 `<program>` 的 n 次连续出现。

你的任务是确定程序的最小运行时间。具体来说，给定内存存储区的数量和大小以及要执行的程序，找出必须执行的最小指令数（引用内存位置和可能设置 BSR），以运行程序。为此，你必须确定将变量映射到存储区的方式，以产生最小的执行时间，并报告该执行时间——即完成程序所需的内存引用和 BSR 寄存器设置的数量。BSR 的值最初未定义，仅在指令显式设置其值时更改。

**【输入格式】**

输入包含一个测试用例。测试用例包含两行。第一行包含两个整数 $b$ 和 $s$，其中 $1 \leq b \leq 13$ 是存储区的数量，$1 \leq s \leq 13$ 是每个存储区可以存储的变量数。第二行包含一个非空程序，最多包含 $1 000$ 个用空格分隔的元素（每个 R$n$, V$i$ 和 E 都算作一个元素）。

你可以假设以下几点：
- 在重复 R$n$ 中，重复次数满足 $1 \leq n \leq 10^6$。
- 在循环操作 R$n$ `<program>` E 中，循环体 `<program>` 不为空。
- 在变量引用 V$i$ 中，变量索引满足 $1 \leq i \leq \min(b \times s, 13)$。
- 程序执行的总变量引用数最多为 $10^{12}$。

**【输出格式】**

显示完成程序所需执行的最小指令数。

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


title: [ICPC2013 WF] Low Power

description:
You are building advanced chips for machines. Making the chips is easy, but the power supply turns out to be an issue since the available batteries have varied power outputs.

Consider the problem of $n$ machines, each with two chips, where each chip is powered by $k$ batteries. Surprisingly, it does not matter how much power each chip gets, but a machine works best when its two chips have power outputs as close as possible. The power output of a chip is simply the smallest power output of its $k$ batteries.

You have a stockpile of 2nk batteries that you want to assign to the chips. It might not be possible to allocate the batteries so that in every machine both chips have equal power outputs, but you want to allocate them so that the differences are as small as possible. To be precise, you want to tell your customers that in all machines the difference of power outputs of the two chips is at most $d$, and you want to make $d$ as small as possible. To do this you must determine an optimal allocation of the batteries to the machines.

Consider Sample Input $1$. There are $2$ machines, each requiring $3$ batteries per chip, and a supply of batteries with power outputs $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12$. You can, for instance, assign the batteries with power outputs $1, 3, 5$ to one chip, those with power $2, 4, 12$ to the other chip of the same machine, those with power $6, 8, 9$ to the third chip, and those with power $7, 10, 11$ to the fourth. The power outputs of the chips are $1, 2, 6,$ and $7$, respectively, and the difference between power outputs is $1$ in both machines. Note that there are many other ways to achieve this result.

inputFormat: The input consists of a single test case. A test case consists of two lines. The first line contains two positive integers: the number of machines $n$ and the number of batteries per chip $k (2nk \leq 10^6)$. The second line contains $2nk$ integers $p_i$ specifying the power outputs of the batteries $(1 \leq p_i \leq 10^9)$.

outputFormat: Display the smallest number $d$ such that you can allocate the batteries so that the difference of power outputs of the two chips in each machine is at most $d$.

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

你正在为机器制造先进的芯片。制造芯片很容易，但电源供应却成为了一个问题，因为现有电池的输出功率各不相同。

考虑 $n$ 台机器的问题，每台机器有两个芯片，每个芯片由 $k$ 块电池供电。出人意料的是，每个芯片获得的电量多少并不重要，但机器在两个芯片的功率输出尽可能接近时工作效果最佳。芯片的功率输出仅为其 $k$ 块电池中输出功率最小的那块电池的输出。

你有一堆共 $2nk$ 块电池，你需要将它们分配给这些芯片。可能无法分配这些电池使得每台机器的两个芯片的功率输出都相等，但你希望尽量减小它们之间的差异。具体来说，你希望告诉客户，所有机器中两个芯片的功率输出差异至多为 $d$，并且你希望使 $d$ 尽可能小。为此，你必须确定电池分配给机器的最优方案。

考虑样例输入 $1$。有 $2$ 台机器，每个芯片需要 $3$ 块电池，有一组功率输出为 $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12$ 的电池。你可以例如将输出功率为 $1, 3, 5$ 的电池分配给一个芯片，将输出功率为 $2, 4, 12$ 的电池分配给同一机器的另一个芯片，将输出功率为 $6, 8, 9$ 的电池分配给第三个芯片，将输出功率为 $7, 10, 11$ 的电池分配给第四个芯片。芯片的功率输出分别为 $1, 2, 6, 7$，两台机器中功率输出的差异分别为 $1$。注意，还有许多其他方式可以实现这一结果。

**【输入格式】**

输入包含一个测试用例。测试用例包含两行。第一行包含两个正整数：机器的数量 $n$ 和每个芯片所需的电池数 $k$ $(2nk \leq 10^6)$。第二行包含 $2nk$ 个整数 $p_i$，指定电池的功率输出 $(1 \leq p_i \leq 10^9)$。

**【输出格式】**

输出一个最小的数字 $d$，使你可以分配这些电池，使每台机器中两个芯片的功率输出差异至多为 $d$。

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


title: BZOJ3864 Hero meet devil

description:
给定一个字符集为 `ACGT` 的字符串 $S$。定义 $\text{LCS}(S,T)$ 为两个字符串 $S,T$ 的最长公共子序列。

对于每个 $0\leq i \leq |S|$，求有多少个长度为 $m$，字符集 `ACGT` 的字符串 $T$，满足 $|\text{LCS}(S,T)|=i$，答案对 $10^9+7$ 取模。

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

对于每组数据，第一行一个字符串 $S$，第二行一个整数 $m$。

outputFormat: 对于每组数据，输出 $i=0,1,\dots,|S|$ 时的答案，每个占一行。

hint: 对于 $100\%$ 的数据，保证 $1\leq T\leq 5$，$1\leq |S| \leq 15$，$1\leq m\leq 1000$。


title: [ICPC2013 WF] Map Tiles

description:
Publishing maps is not an easy task. First you need some appropriate transformation to display the earth’s spherical shape in a two-dimensional plane. Then another issue arises – most high-quality maps are too large to be printed on a single page of paper. To cope with that, map publishers often split maps into several rectangular tiles, and print each tile on one page. In this problem, you will examine this “tiling” process.

The International Cartographic Publishing Company (ICPC) needs to cut their printing costs by minimizing the number of tiles used for their maps. Even with a fixed tile size (determined by the page size) and map scale, you can still optimize the situation by adjusting the tile grid.
The left side of Figure G.1 shows 14 map tiles covering a region. The right side shows how you can cover the same region with only 10 tiles, without changing the tile sizes or orientation.

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

Your task is to help the ICPC find the minimum number of tiles needed to cover a given region. For simplicity, the region will be given as a closed polygon that does not intersect itself.

Note that the tiles must be part of a rectangular grid aligned with the $x$-axis and $y$-axis. That is, they touch each other only with their whole sides and cannot be rotated. Also note that although all input coordinates are integers, tiles may be located at non-integer coordinates.

The polygon may touch the edges of marginal lines (as in Sample Input 2). However, to avoid floatingpoint issues, you may assume the optimal answer will not change even if the polygon is allowed to go outside the map tiles by a distance of $10^{-6}$.

inputFormat: The input consists of a single test case. The first line of a test case contains three integers: $n, x_s$, and $y_s$. The number of polygon vertices is $n (3 \leq n \leq 50)$, and $x_s$ and $y_s (1 \leq x_s, y_s \leq 100)$ are the dimensions of each tile. Each of the next $n$ lines contains two integers $x$ and $y (0 \leq x \leq 10x_s, 0 \leq y \leq 10y_s)$, specifying the vertices of the polygon representing the region (in either clockwise or counter-clockwise order).

outputFormat: Display the minimal number of tiles necessary to cover the whole interior of the polygon.

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

出版地图并非易事。首先，你需要进行适当的变换，以在二维平面上显示地球的球形形状。接着出现另一个问题——大多数高质量的地图都太大，无法印在一页纸上。为了解决这个问题，地图出版商通常将地图分割成若干个矩形块，并在每页上打印一个块。在这个问题中，你将研究这种“瓦片化”过程。

国际制图出版公司（ICPC）需要通过最小化用于其地图的瓦片数量来削减印刷成本。即使固定了瓦片大小（由页面大小决定）和地图比例，你仍然可以通过调整瓦片网格来优化情况。图 G.1 的左侧显示了覆盖一个区域的 14 个地图瓦片。右侧显示了如何在不改变瓦片大小或方向的情况下，仅用 10 个瓦片覆盖相同的区域。

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

你的任务是帮助 ICPC 找出覆盖给定区域所需的最少瓦片数量。为简化起见，该区域将给出为不自相交的闭合多边形。

请注意，瓦片必须是与 $x$ 轴和 $y$ 轴对齐的矩形网格的一部分。也就是说，它们只能用完整的边接触，不能旋转。另外，尽管所有输入坐标都是整数，瓦片的位置可以是非整数坐标。

多边形可能接触边界线的边缘（如样例输入 2 中所示）。但是，为避免浮点数问题，可以假设即使允许多边形超出地图瓦片的距离为 $10^{-6}$，最优答案也不会改变。

**【输入格式】**

输入包含一个测试用例。测试用例的第一行包含三个整数：$n, x_s$ 和 $y_s$。多边形的顶点数为 $n (3 \leq n \leq 50)$，$x_s$ 和 $y_s (1 \leq x_s, y_s \leq 100)$ 是每个瓦片的尺寸。接下来的 $n$ 行中的每一行包含两个整数 $x$ 和 $y (0 \leq x \leq 10x_s, 0 \leq y \leq 10y_s)$，指定表示区域的多边形的顶点（按顺时针或逆时针顺序）。

**【输出格式】**

输出覆盖多边形的整个内部所需的最少瓦片数量。

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


title: [ICPC2013 WF] Matryoshka

description:
Matryoshkas are sets of traditional Russian wooden dolls of decreasing size placed one inside the other. A matryoshka doll can be opened to reveal a smaller figure of the same sort inside, which has, in turn, another figure inside, and so on.

The Russian Matryoshka Museum recently exhibited a collection of similarly designed matryoshka sets, differing only in the number of nested dolls in each set. Unfortunately, some over-zealous (and obviously unsupervised) children separated these sets, placing all the individual dolls in a row. There are $n$ dolls in the row, each with an integer size. You need to reassemble the matryoshka sets, knowing neither the number of sets nor the number of dolls in each set. You know only that every complete set consists of dolls with consecutive sizes from $1$ to some number $m$, which may vary between the different sets.

When reassembling the sets, you must follow these rules:
- You can put a doll or a nested group of dolls only inside a larger doll.
- You can combine two groups of dolls only if they are adjacent in the row.
- Once a doll becomes a member of a group, it cannot be transferred to another group or permanently separated from the group. It can be temporarily separated only when combining two groups.

Your time is valuable, and you want to do this reassembly process as quickly as possible. The only time-consuming part of this task is opening and subsequently closing a doll, so you want to minimize how often you do this. For example, the minimum number of openings (and subsequent closings) when combining group $[1, 2, 6]$ with the group $[4]$ is two, since you have to open the dolls with sizes $6$ and $4$. When combining group $[1, 2, 5]$ with the group $[3, 4]$, you need to perform three openings.

Write a program to calculate the minimum number of openings required to combine all disassembled matryoshka sets.

inputFormat: The input consists of a single test case. A test case consists of two lines. The first line contains one integer $n (1 \leq n \leq 500)$ representing the number of individual dolls in the row. The second line contains $n$ positive integers specifying the sizes of the dolls in the order they appear in the row. Each size is between $1$ and $500$ inclusive.

outputFormat: Display the minimum number of openings required when reassembling the matryoshka sets. If reassembling cannot be done (some of the kids might have been excessively zealous and taken some dolls), display the word `Impossible`.

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

套娃是俄罗斯传统木制玩具，由一组逐渐变小的娃娃组成，依次放置在另一个娃娃内部。一个套娃可以打开，露出一个更小的类似玩偶，而这个玩偶内部又有另一个玩偶，以此类推。

俄罗斯套娃博物馆最近展出了一系列设计相似的套娃，不同之处仅在于每套娃娃中嵌套的数量不同。不幸的是，一些过于热心（显然没有得到监督）的孩子把这些套娃拆散了，并将所有的单个娃娃排成一行。现在这一行中有 $n$ 个娃娃，每个都有一个整数大小。你需要重新组装这些套娃，既不知道套娃的数量，也不知道每套娃娃中娃娃的数量。你只知道每套完整的套娃由大小从 $1$ 到某个数字 $m$ 的连续大小的娃娃组成，而这个数字 $m$ 在不同的套娃中可能有所不同。

在重新组装套娃时，你必须遵循以下规则：
- 你只能将一个娃娃或一个嵌套的娃娃组放入一个更大的娃娃中。
- 你只能合并两个在行中相邻的娃娃组。
- 一旦一个娃娃成为一个组的成员，它不能被转移到另一个组或永久地从组中分离。它只能在合并两个组时暂时分离。

你的时间非常宝贵，你希望尽快完成这个重新组装过程。这个任务中唯一耗时的部分是打开和随后关闭一个娃娃，因此你希望尽量减少这样的操作次数。例如，当将组 $[1, 2, 6]$ 与组 $[4]$ 合并时，最少需要进行两次开关操作，因为你必须打开大小为 $6$ 和 $4$ 的娃娃。而当将组 $[1, 2, 5]$ 与组 $[3, 4]$ 合并时，需要进行三次开关操作。

编写一个程序计算重新组装所有拆散的套娃所需的最少开关次数。

**【输入格式】**

输入包含一个测试用例。测试用例由两行组成。第一行包含一个整数 $n (1 \leq n \leq 500)$，表示行中单个娃娃的数量。第二行包含 $n$ 个正整数，按照它们在行中出现的顺序指定娃娃的大小。每个大小在 $1$ 到 $500$ 之间（包括 $1$ 和 $500$）。

**【输出格式】**

输出重新组装套娃所需的最少开关次数。如果重新组装无法完成（可能有些孩子过于热心，带走了一些娃娃），则输出 `Impossible`。

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


title: [ICPC2013 WF] Pirate Chest

description:
Pirate Dick finally had enough of fighting, marauding, theft, and making life miserable for many on the open seas. So he decided to retire, and he found the perfect island to spend the rest of his days on, provided he does not run out of money. He has plenty of gold coins now, and he wants to store them in a chest (he is a pirate after all). Dick can construct a rectangular chest with integer dimensions of any size up to a specified maximum size for the top but with an arbitrary integer height. Now he needs a place to hide the chest. While exploring the island, he found the perfect solution.

Dick will hide his chest by submerging it in a murky pond. The pond has a rectangular surface, and it completely fills the bottom of a valley that has high vertical rocky walls. Dick surveyed the pond and knows its depth for each of the squares of a Cartesian coordinate grid system placed on the pond surface. When Dick submerges the chest, it will sink as far as possible until it touches the bottom. The top of the chest will remain parallel to the pond’s surface and the chest will be aligned with the grid squares. The water displaced by the submerged chest will raise the level of the pond’s surface (this will occur even if there is no space around the chest for the displaced water to rise). The walls of the valley are high enough that the water can never splash out of the valley. Of course, since the chest must be invisible, its top must be strictly below the surface of the pond. Your job is to find the volume of the largest chest that
Pirate Dick can hide this way.

In Figure I.1, the leftmost image shows a pond, the middle image shows a possible placement of a chest of volume 3, and the rightmost image shows a placement of a chest of volume 4, which is the maximum possible volume. Note that if the second chest were made one unit taller, its top would be visible because it would be at exactly the same height as the surface of the water.

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

inputFormat: The input consists of a single test case. A test case starts with a line containing four integers $a, b, m$, and $n (1 \leq a, b, m, n \leq 500)$. The pond’s surface dimensions are $m \times n$ and the maximum size of the top (and bottom) of the chest is $a \times b$. In addition, $a$ and $b$ are small enough that it is not possible to cover the entire pond with a chest with top size $a \times b$. Each of the remaining $m$ lines in a test case contains $n$ integers $d_{i,j}$ specifying the pond’s depth at grid square $(i, j)$, where $0 \leq d_{i,j} ≤ 10^9$ for each $1 \leq i \leq m$ and $1 \leq j \leq n$.

outputFormat: Display the maximum volume of a rectangular chest with integer dimensions (where one of the dimensions of the top is bounded by $a$ and the other is bounded by $b$) that can be completely submerged below the surface of the pond. If no chest can be hidden in the pond, display $0$.

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

海盗迪克终于厌倦了战斗、抢劫、偷窃，以及在开阔海域上给许多人带来的痛苦。因此，他决定退休，并找到了一个完美的岛屿，打算在那里度过余生，只要他不用尽光金币就行。他现在有大量的金币，想要把它们存放在一个箱子里（毕竟他是海盗）。迪克可以制造一个整数尺寸的矩形箱子，顶部尺寸的大小可以高达指定的最大尺寸，但高度可以是任意整数。现在他需要一个地方来隐藏这个箱子。在探索岛屿时，他找到了一个完美的解决方案。

迪克将把他的箱子藏在一个混浊的池塘中。池塘有一个矩形的表面，并完全填满了一个有高垂直岩壁的山谷底部。迪克调查了池塘，并了解到每个笛卡尔坐标网格系统方格的深度。当迪克将箱子浸入水中时，它将尽可能沉入，直到触及底部。箱子的顶部将保持与池塘表面平行，并且箱子将与网格方格对齐。被浸入水中的箱子所排开的水将抬高池塘表面的水平（即使周围没有空间供排开的水升起）。山谷的岩壁足够高，以至于水永远不会溅出山谷。当然，由于箱子必须看不见，它的顶部必须严格低于池塘表面。你的任务是找出海盗迪克能够用这种方式隐藏的最大箱子的容积。

在图 I.1 中，最左边的图像显示了一个池塘，中间的图像显示了一个容积为 3 的箱子的可能摆放方式，最右边的图像显示了容积为 4 的箱子的摆放方式，这是可能的最大容积。请注意，如果第二个箱子的高度再增加一个单位，它的顶部将会可见，因为它的高度与水表面正好相同。

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

**【输入格式】**

输入包含一个测试用例。测试用例以一行四个整数 $a, b, m, n (1 \leq a, b, m, n \leq 500)$ 开始。池塘表面的尺寸为 $m \times n$，箱子顶部（和底部）的最大尺寸为 $a \times b$。此外，$a$ 和 $b$ 足够小，不能用顶部尺寸为 $a \times b$ 的箱子覆盖整个池塘。在测试用例的其余部分，每个深度的 $m$ 行中包含 $n$ 个整数 $d_{i,j}$，指定网格方格 $(i, j)$ 处的池塘深度，其中对于每个 $1 \leq i \leq m$ 和 $1 \leq j \leq n$，$0 \leq d_{i,j} \leq 10^9$。

**【输出格式】**

显示能够完全浸入池塘表面以下的最大矩形箱子的容积。如果无法在池塘中隐藏箱子，则显示 $0$。

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


title: [ICPC2013 WF] Pollution Solution

description:
As an employee of Aqueous Contaminate Management, you must monitor the pollution that gets dumped (sometimes accidentally, sometimes purposefully) into rivers, lakes and oceans. One of your jobs is to measure the impact of the pollution on various ecosystems in the water such as coral reefs, spawning grounds, and so on.

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

The model you use in your analysis is illustrated in Figure J.1. The shoreline (the horizontal line in the figure) lies on the $x$-axis with the source of the pollution located at the origin $(0,0)$. The spread of the pollution into the water is represented by the semicircle, and the polygon represents the ecosystem of concern. You must determine the area of the ecosystem that is contaminated, represented by the dark blue region in the figure.

inputFormat: The input consists of a single test case. A test case starts with a line containing two integers n and $r$, where $3 \leq n \leq 100$ is the number of vertices in the polygon and $1 \leq r \leq 1 000$ is the radius of the pollution field. This is followed by $n$ lines, each containing two integers $x_i, y_i$, giving the coordinates of the polygon vertices in counter-clockwise order, where $-1 500 \leq x_i \leq 1 500$ and $0 \leq y_i \leq 1 500$. The polygon does not self-intersect or touch itself. No vertex lies on the circle boundary.

outputFormat: Display the area of the polygon that falls within the semicircle centered at the origin with radius $r$. Give the result with an absolute error of at most $10^{-3}$.

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

作为水污染管理公司的员工，你必须监测被排放到河流、湖泊和海洋中的污染物（有时是意外的，有时是故意的）。你的工作之一是测量污染对水中各种生态系统的影响，如珊瑚礁、产卵场所等。

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

你在分析中使用的模型如图 J.1 所示。岸线（图中的水平线）位于 $x$ 轴上，污染源位于原点 $(0,0)$ 处。污染物在水中的扩散由半圆表示，多边形表示了关注的生态系统。你需要确定被污染的生态系统区域的面积，即图中的深蓝色区域。

**【输入格式】**

输入包含一个测试用例。测试用例以一行两个整数 $n$ 和 $r$ 开始，其中 $3 \leq n \leq 100$ 是多边形顶点的数量，$1 \leq r \leq 1,000$ 是污染场的半径。接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$，表示多边形顶点的坐标，顺时针给出，其中 $-1,500 \leq x_i \leq 1,500$ 且 $0 \leq y_i \leq 1,500$。多边形不自相交或自交。没有顶点位于半圆边界上。

**【输出格式】**

显示位于以原点为中心、半径为 $r$ 的半圆内的多边形的面积。结果的绝对误差不超过 $10^{-3}$。

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


title: [ICPC2013 WF] Up a Tree

description:
Anatoly Cheng McDougal is a typical student in many ways. Whenever possible he tries to cut and paste code instead of writing it from scratch. Unavoidably this approach causes him problems. For example, when he first learned about preorder, inorder and postorder traversals of trees, and was given code for a preorder print of a tree (shown on the left below), he simply cut and pasted the code, then moved the print statement to the correct location and renamed the procedure. However, he forgot to rename the procedure calls inside the code, resulting in the defective inorder print and postorder print code shown below.

```cpp
void prePrint(TNode t)
{
    output(t.value);
    if (t.left != null)
        prePrint(t.left);
    if (t.right != null)
        prePrint(t.right);
}
void inPrint(TNode t)
{
    if (t.left != null)
        prePrint(t.left);
    output(t.value);
    if (t.right != null)
        prePrint(t.right);
}
void postPrint(TNode t)
{
    if (t.left != null)
        prePrint(t.left);
    if (t.right != null)
        prePrint(t.right);
    output(t.value);
}
```

At this point, Anatoly did not behave like a typical student. He actually tested his code! Unfortunately, when the results were not correct, he reverted back to typical student behavior. He panicked and started randomly changing calls in all three procedures, hoping to get things right. Needless to say, the situation became even worse now than when he started.

Anatoly’s professor tested the code on a random tree of characters. When she looked at the output of his three print routines, she correctly guessed what had happened. However, instead of going directly to his code, she decided to try to reconstruct Anatoly’s code just by observing the output. In order to do this, she correctly made the following assumptions:

1. The output statement in each print routine is in the correct location (for example, between the two recursive calls in the inPrint routine).
2. Among the six recursive calls made by the three routines, exactly two calls are to prePrint, exactly two are to inPrint, and exactly two are to postPrint, though potentially in the wrong routines.

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help her find all possible reconstructions of Anatoly’s code. In addition, for each such reconstruction, you are to find the alphabetically first tree (as described in the output section) giving the observed output.

inputFormat: The input consists of a single test case. A test case consists of three strings on three separate lines: the observed output of Anatoly’s `prePrint`, `inPrint` and `postPrint` routines (in that order) on some test tree. Each of these strings consists of $n$ uppercase letters $(4 \leq n \leq 26)$, with no repeated letters in any string. The test case is guaranteed to have at least one solution.

outputFormat:
Display all possible reconstructions for the test case, ordered as described in the last paragraph below. The output for each reconstruction consists of two parts. The first part is a single line and describes the six calls in Anatoly’s routines: first the two (recursive) calls in Anatoly’s `prePrint` routine, followed by the calls in his `inPrint` routine, and finally the calls in his `postPrint` routine. The calls are described by the words `Pre`, `In`, and `Post`, separated by spaces. For example, if Anatoly’s routines were correct, the resulting output of the first part of the reconstruction would be `Pre Pre In In Post Post`.

The second part consists of three lines and describes the first test tree that could have generated the observed outputs. The first line is the *correct* preorder print of the tree, and the second and third lines contain the correct inorder and postorder prints, respectively. The first tree is the one with the alphabetically first preorder print. If there are multiple such trees, the first of these is the one with the alphabetically first inorder print.

Every reconstruction is a sequence of $6$ tokens chosen from `Pre`, `In`, and `Post`. The ordering of reconstructions is lexicographic with respect to the following ordering of tokens: Pre < In < Post.

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

Anatoly Cheng McDougal 在许多方面都是典型的学生。每当可能时，他都会尝试剪切和粘贴代码，而不是从头开始编写。不可避免地，这种方法给他带来了问题。例如，当他第一次学习树的前序、中序和后序遍历，并获得了前序打印树的代码（如下面左侧所示），他只是简单地剪切和粘贴代码，然后将打印语句移动到正确的位置并重命名过程。然而，他忘记了在代码内部重命名过程调用，导致了下面有缺陷的中序打印和后序打印代码。

```cpp
void prePrint(TNode t)
{
    output(t.value);
    if (t.left != null)
        prePrint(t.left);
    if (t.right != null)
        prePrint(t.right);
}
void inPrint(TNode t)
{
    if (t.left != null)
        prePrint(t.left);
    output(t.value);
    if (t.right != null)
        prePrint(t.right);
}
void postPrint(TNode t)
{
    if (t.left != null)
        prePrint(t.left);
    if (t.right != null)
        prePrint(t.right);
    output(t.value);
}
```

此时，Anatoly 不像典型的学生那样行事。他实际上测试了他的代码！不幸的是，当结果不正确时，他又恢复了典型的学生行为。他慌乱了，开始随机更改所有三个过程中的调用，希望能弄对。不用说，现在的情况比他刚开始时更糟糕了。

Anatoly 的教授在一个随机的字符树上测试了代码。当她查看他三个打印例程的输出时，她正确猜测到发生了什么。然而，她没有直接查看他的代码，而是决定仅通过观察输出来重建Anatoly的代码。为了做到这一点，她正确地做出了以下假设：

1. 每个打印例程中的输出语句在正确的位置（例如，在 `inPrint` 例程中的两个递归调用之间）。
2. 在三个例程中进行的六次递归调用中，恰好有两次调用 `prePrint`，两次调用 `inPrint` 和两次调用 `postPrint`，尽管它们可能在错误的例程中。

不久，教授意识到从Anatoly的输出重建代码和测试树并不是一件简单的任务，结果可能是模棱两可的。你需要帮助她找出所有可能的Anatoly代码重建方式。此外，对于每种重建方式，你需要找出字母顺序最早的树（如下面输出部分所描述的）。

**【输入格式】**

输入包含一个测试用例。一个测试用例由三行字符串组成：Anatoly 的 `prePrint`、`inPrint` 和 `postPrint` 例程在某个测试树上的观察输出（按顺序）。每个字符串由 $n$ 个大写字母组成（$4 \leq n \leq 26$），每个字符串中没有重复的字母。保证测试用例至少有一种解决方案。

**【输出格式】**

显示测试用例的所有可能重建方式，按照以下最后一段中描述的顺序排序。每种重建方式的输出分为两部分。第一部分是单行描述Anatoly例程中的六次调用：首先是Anatoly的 `prePrint` 例程中的两次（递归）调用，然后是 `inPrint` 例程中的调用，最后是 `postPrint` 例程中的调用。调用由单词 `Pre`、`In` 和 `Post` 描述，用空格分隔。例如，如果Anatoly的例程是正确的，则重建方式的第一部分的输出将是 `Pre Pre In In Post Post`。

第二部分包括三行，描述能够生成观察输出的第一棵树。第一行是树的正确前序遍历打印，第二行和第三行分别包含正确的中序遍历和后序遍历打印。第一棵树是按字母顺序最早的前序打印树。如果有多棵这样的树，则选择其中前序打印字母顺序最早的树。

每种重建方式都是从 `Pre`、`In` 和 `Post` 中选择的六个标记的序列。重建方式的排序是按照以下标记的词法顺序：`Pre` < `In` < `Post`。

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

samples:
Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH

samples:
In Pre In Post Post Pre
BLNFKMEHAGPCODIJ
NLBAGHPEODCMIJKF
NLGAPHDOCEJIMKFB
Post Pre In In Post Pre
BLNFKICPGAHEODMJ
NLBGAPHCODEIJMKF
NLAGHPDOECJMIKFB


title: [JOI Open 2024] 考试 2

description:
JOI 君在 IOI 高中上学，期末考试即将来临。考试的内容是计算 **IOI 函数**。IOI 函数是将 $[1,10^9]$ 之间的整数映射到布尔值（即 $\texttt{True}/\texttt{False}$）的函数。IOI 函数可以从以下六条 IOI 高中规定的规则中构造：

1. 设 $a$ 为 $[1,10^9]$ 之间的整数，则 $\texttt{[a]}$ 是一个 IOI 函数。它将不小于 $a$ 的整数映射成 $\texttt{True}$，将小于 $a$ 的整数映射成 $\texttt{False}$。

2. 记 $\texttt{f}$ 为 IOI 函数，则 $\texttt{(f)}$ 是一个 IOI 函数，它的映射规则与 $\texttt{f}$ 的映射规则相同。

3. 记 $\texttt{f}$ 为 IOI 函数，则 $\texttt{!f}$ 是一个 IOI 函数。设 $x$ 为整数，若 $\texttt{f}$ 将 $x$ 映射为 $\texttt{True}$，则 $\texttt{!f}$ 将 $x$ 映射为 $\texttt{False}$；否则 $\texttt{!f}$ 将 $x$ 映射为 $\texttt{True}$。

4. 记 $\texttt{f},\texttt{g}$ 为 IOI 函数，则 $\texttt{f\&g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\texttt{f\&g}$ 将 $x$ 映射为 $\texttt{True}$，当且仅当 $\texttt{f},\texttt{g}$ 都将 $x$ 映射为 $\texttt{True}$。

5. 记 $\texttt{f},\texttt{g}$ 为 IOI 函数，则 $\texttt{f\^ g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\texttt{f\^ g}$ 将 $x$ 映射为 $\texttt{True}$，当且仅当 $\texttt{f},\texttt{g}$ 中恰好有一个将 $x$ 映射为 $\texttt{True}$。

6. 记 $\texttt{f},\texttt{g}$ 为 IOI 函数，则 $\texttt{f|g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\texttt{f|g}$ 将 $x$ 映射为 $\texttt{True}$，当且仅当 $\texttt{f},\texttt{g}$ 中至少有一个将 $x$ 映射为 $\texttt{True}$。

如果某个 IOI 函数用多条规则构造出，数字更大的规则将决定函数值。例如，对于 $\texttt{[1]\&[2]|[3]}$ 应当应用规则 6，其中 $\texttt{f} = \texttt{[1]\&[2]},\texttt{g} = \texttt{[3]}$（而非应用规则 4，其中 $\texttt{f} = \texttt{[1]},\texttt{g} = \texttt{[2]|[3]}$）。额外地，对于规则 4，5，6，应当最大化 $\texttt{f}$ 的长度。例如，对于 $\texttt{[4]ˆ[5]ˆ[6]}$，应当在 $\texttt{f} = \texttt{[4]ˆ[5]},\texttt{g} = \texttt{[6]}$ 上应用规则 5（而非 $\texttt{f} = \texttt{[4]},\texttt{g} = \texttt{[5]ˆ[6]}$）。

为备战期末考试，JOI 君准备好了一个长度为 $N$ 的 IOI 函数 $S$。他打算用 $Q$ 个整数 $X_1,X_2,\cdots,X_Q$ 来练习他的计算技能。于是他找来了你——能够熟练处理 IOI 函数的人，来解决这个问题。

你需要写一个程序。给定 $N,Q,S$ 以及 $X_1,X_2,\cdots,X_Q$，对于 $i=1,2=\cdots,Q$，回答 IOI 函数 $S$ 会将 $X_i$ 映射成 $\texttt{True}$ 还是 $\texttt{False}$。

outputFormat: 输出 $Q$ 行，第 $i$ 行为 $\texttt{True}$ 或者 $\texttt{False}$，即 $X_i$ 被 $S$ 映射成的值。

hint:
### 样例解释

样例 $1$ 解释如下：

| $X_i$ | $\texttt{![2]}$ | $\texttt{[3]}$ | $\texttt{![2]\|[3]}$ | $\texttt{![4]}$ | $\texttt{(![2]\|[3])\&![4]}$ |
| :--: | :--: | :--: | :--: | :--: | :--: |
| $1$ | $\texttt{True}$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{True}$ |
| $2$ | $\texttt{False}$ | $\texttt{False}$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{False}$ |
| $3$ |  $\texttt{False}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{True}$ |
| $4$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{False}$ | $\texttt{False}$ |
| $5$ |  $\texttt{False}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{False}$ | $\texttt{False}$ |

样例 $1$ 满足子任务 $3,6,7$ 的条件。

样例 $2$ 满足子任务 $1,3,5\sim 7$ 的条件。

样例 $3$ 满足子任务 $3,4,6,7$ 的条件。

### 数据范围

- $1 \le N \le 1\,000\,000$；
- $1 \le Q \le 200\,000$；
- $S$ 为长度为 $N$ 的 IOI 函数；
- $1 \le X_i \le 10^9$（$1 \le i \le Q$）；
- $N, Q, X_i$（$1 \le i \le Q$）均为整数。

### 子任务

1. （$5$ points）$S$ 中不含 $\texttt{\&}$ 和 $\texttt{|}$；
2. （$20$ points）$Q = 1$；
3. （$10$ points）$N \le 10\,000$；
4. （$6$ points）$S$ 中不含 $\texttt{!}$ 和 $\texttt{ˆ}$；
5. （$12$ points）当应用规则 4 或 6 来构造 $S$ 时，$\texttt{f}$ 和 $\texttt{g}$ 中至少有一个是用规则 1 得到的；
6. （$20$ points）$N \le 400\, 000$；
7. （$27$ points）无额外约束。

*赛时公告：如果你复制题面中的 LaTeX，可能会得到 `ˆ`，但实际上是 `^`。请特别注意。

由 Starrykiller 根据英文题面翻译。


title: [JOI Open 2024] 中暑

description:
JOI 岛由 $L$ 个区组成，从西到东依次编号为 $1$ 到 $L$。岛上有 $(L-1)$ 条路，编号为 $1$ 到 $L-1$。第 $i$ 条路（$1\le i\le L-1$）双向连接着区 $i$ 和区 $i+1$。

现在，IOI 20XX 计划在 JOI 岛上举行！然而，令人担心的是，JOI 岛以其“火炉”称号而闻名于世。在岛上中暑风险较高，尤其是对于不适应 JOI 岛炎热气候的外国人。所以，IOI 的组织者决定采取以下措施：

- 对于每一个 $1\le i\le L$，在区 $i$ 上有一个容量为 $C_i$ 人的医院。注意，$C_i$ 可以为 $0$。

- 在 IOI 活动中，当有人在第 $x$ 条路（$1\le x\le L-1$）上中暑时，中暑者将以以下的程序送医：
    - 将中暑者送往区 $x$ 或者区 $x+1$ 上的未满员的医院。如果两个区上的医院都未满员，则送往哪一个医院都可以。如果两个医院都满员了，用直升机将中暑者送往岛外的医院。

由于动用直升机花销不小，组织者们想要估计可能的需要动用直升机的病人数量的**最大值**。他们考虑如下的情境：

- 在 IOI 活动之前，医院中没有病人；
- 在 IOI 活动中，有 $N$ 个人会依次中暑。第 $j$ 个（$1\le j\le N$）人在第 $X_j$ 条路上中暑；
- 对于任意 $1\le j\le N-1$，当第 $(j+1)$ 个人中暑时，第 $1,2,\cdots,j$ 个人已经送达医院。由于中暑症状较为严重，在 IOI 活动中无人出院。

你需要写一个程序。给定区的数量，医院的信息和中暑者的信息，在上述情境下，计算可能的需要动用直升机的病人数量的最大值。

outputFormat: 输出一行一个数，即可能的需要动用直升机的病人数量的最大值。

hint:
### 样例解释

对于样例 $1$，考虑如下的情况：

- 将第一个中暑者送往区 $2$ 上的医院。此时，三个区上的医院的病人数量分别为 $0,1,0$；
- 将第二个中暑者送往区 $3$ 上的医院。此时，三个区上的医院的病人数量分别为 $0,1,1$；
- 对于第三个中暑者，由于区 $2,3$ 上的医院均已满员，所以只能用直升机送出岛。

此时共有 $1$ 人动用直升机送出岛。可以证明这是最大值。

对于样例 $2$，考虑如下的情况：

- 将第一个中暑者送往区 $2$ 上的医院。此时，六个区上的医院的病人数量分别为 $0,1,0,0,0,0$；
- 将第二个中暑者送往区 $4$ 上的医院。此时，六个区上的医院的病人数量分别为 $0,1,0,1,0,0$；
- 将第三个中暑者送往区 $5$ 上的医院。此时，六个区上的医院的病人数量分别为 $0,1,0,1,1,0$；
- 对于第四个中暑者，由于区 $4,5$ 上的医院均已满员，所以只能用直升机送出岛。
- 将第五个中暑者送往区 $3$ 上的医院。此时，六个区上的医院的病人数量分别为 $0,1,1,1,1,0$；
- 对于第六个中暑者，由于区 $2,3$ 上的医院均已满员，所以只能用直升机送出岛。
- 对于第七个中暑者，由于区 $3,4$ 上的医院均已满员，所以只能用直升机送出岛。

此时共有 $3$ 人动用直升机送出岛。可以证明这是最大值。

样例 $1$ 满足子任务 $1\sim 8$ 的条件。

样例 $2$ 满足子任务 $2\sim 8$ 的条件。

样例 $3$ 满足子任务 $1,5\sim 8$ 的条件。

样例 $4,5$ 满足子任务 $5\sim 8$ 的条件。

### 数据范围

- $2 \le L \le 8\,000$；
- $0 \le C_i \le 8\,000$（$1 \le i \le L$）；
- $1 \le N \le 8\,000$；
- $1 \le X_j \le L − 1$（$1 \le j \le N$）；
- 输入数字全为整数。

【子任务】

1. （$6 $ points）$X_1 \le X_2 \le\cdots\le X_N$；
2. （$7 $ points）$L \le 18, N \le 18, C_i = 1 $（$1 \le i \le L$）；
3. （$7 $ points）$L \le 18, N \le 100, C_i = 1 $（$1 \le i \le L$）；
4. （$25$  points）$L \le 100, N \le 100, C_i = 1$ （$1 \le i \le L$）；
5. （$25$  points）$L \le 100, N \le 100$；
6. （$10$  points）$L \le 600, N \le 600$；
7. （$15$  points）$L \le 3\,500, N \le 3\,500$；
8. （$5 $ points）无额外约束。

由 Starrykiller 根据英文题面翻译。


title: [JOI Open 2024] 图书馆 3

background:
由于洛谷评测系统的限制，实际提交时，不需要引入 $\texttt{library3.h}$。你需要在代码中添加：

```cpp
void answer(std::vector<int>);
int query(std::vector<int>);
```

请使用 C++ 20 提交，不保证使用其他标准提交能够通过。

description:
几百年的时光弹指一瞬，JOI 城已然是一片废墟。IOI 酱——一个探险家，正在探索图书馆的故址。由探索结果得知：

- JOI 城的图书馆中有一个水平的书架，上面有 $N$ 个**位置**来放书，从左到右依次编号为 $0\sim N-1$。一个位置只能放一本书。
- 有 $N$ 本书放在书架上，编号为 $0\sim N-1$。
- 定义 $N$ 本书的一个**摆放**为一种将 $N$ 本书放在 $N$ 个位置上的方式。
- 存在 $N$ 本书的一个**正确摆放**，其中第 $B_i$（$0\le i\le N-1$）本书放在位置 $i$ 上，其中 $B_i$ 两两不同。

书的摆放总会改变，而这个图书馆是通过不断重复以下步骤来将书还原成正确摆放的：

> **操作** 令 $x$ 是最左边的书，满足 $x$ 的位置与它在正确摆放中的位置不同。令 $y$ 为 $x$ 正确位置上的书，交换 $x,y$。

尽管 IOI 酱找到了许多旧书，她无法得知书的正确摆放。然而，她发现了一台旧机器，可以执行上面的操作。如果指定一个摆放并向机器发起询问，机器就会回答从当前摆放到正确摆放，需要重复执行多少次操作。IOI 酱想要利用这台机器，获得书的正确摆放。由于机器过于老旧，她最多只能询问 $5\, 000$ 次。

你需要写一个程序。给定书架的信息，通过最多 $5\,000$ 次询问，找出书的正确摆放。

【实现细节】

**这是一道交互题，你只需要提交一个文件（`library3.cpp`）。**

你需要在文件中引入 `library3.h`，并实现以下函数：

- `void solve(int N)`\
该函数在每个测试点中被调用恰好一次。
    - 参数 $N$ 代表书的数量。

在 `library3.cpp` 中，你可以调用以下函数：

- `int query(const std::vector<int> a)`\
IOI 酱用这个函数向机器发起询问。
    - 参数 `a` 为一个长度为 $N$ 的数组，即要询问的摆放。也就是说，在指定的摆放中，第 `a[i]` 本书（$0\le i\le N-1$）被放在位置 $i$。
    - 返回值为一个整数，即从指定的摆放到正确摆放，需要重复执行多少次操作。
    - 参数中，数组 `a` 的长度必须为 $N$。如果不满足这个条件，你的程序将被判为 **Wrong Answer[1]**。
    - 参数中，数组 `a` 中的每个元素都必须在 $0$ 到 $N-1$ 之间。如果不满足这个条件，你的程序将被判为 **Wrong Answer[2]**。
    - 参数中，数组 `a` 中的元素必须两两不同。如果不满足这个条件，你的程序将被判为 **Wrong Answer[3]**。
    - 该函数最多只能被调用 $5\,000$ 次。如果超出调用次数，你的程序将被判为 **Wrong Answer[4]**。

- `void answer(std::vector<int> b)`\
你的程序用这个函数回答正确摆放。
    - 参数 `b` 为一个长度为 $N$ 的数组，即正确摆放。也就是说，在正确摆放中，第 `b[i]` 本书（$0\le i\le N-1$）被放在位置 $i$。
    - 参数中，数组 `b` 的长度必须为 $N$。如果不满足这个条件，你的程序将被判为 **Wrong Answer[5]**。
    - 参数中，数组 `b` 中的每个元素都必须在 $0$ 到 $N-1$ 之间。如果不满足这个条件，你的程序将被判为 **Wrong Answer[6]**。
    - 参数中，数组 `b` 中的元素必须两两不同。如果不满足这个条件，你的程序将被判为 **Wrong Answer[7]**。
    - 如果你回答的摆放并不是正确摆放，你的程序将被判为 **Wrong Answer[8]**。
    - 该函数必须被调用恰好一次。如果超出调用次数，你的程序将被判为 **Wrong Answer[9]**。如果未调用，你的程序将被判为 **Wrong Answer[10]**。

【注意事项】

你的程序可以定义其他函数，也可以使用全局变量。

你的程序不得使用标准输入输出流，不得以任何形式读写其他文件。但是，你的程序可以使用标准错误流来输出调试信息。

【编译运行】

可以从附件中获取 sample grader。Sample grader 即为文件 `grader.cpp`。将 `grader.cpp`，`library3.cpp`，`library3.h` 放置在同一目录下，运行以下命令即可编译你的程序。你也可以运行文件 `compile.sh` 来编译程序。

> 编译命令：`g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp`

编译成功的话，会生成可执行文件 `grader`。注意，实际评测时用的 grader 与 sample grader 是不同的。Sample grader 会以单进程方式执行，从标准输入流中读取数据，输出结果到标准输出流。

*赛时公告：Sample grader 是非适应性的。实际评测时使用的 grader 是否适应是未知的。

inputFormat:
Sample grader 按照以下方式读取输入：

> $N$\
> $B_0$ $B_1$ $\cdots$ $B_{N-1}$

在正确摆放中，第 $B_i$（$0\le i\le N-1$）本书放在位置 $i$ 上。

outputFormat:
Sample grader 会输出以下结果：

- 如果你的程序被评为正确的，返回调用 `query` 函数的次数。例如：`Accepted: 3000`。
- 否则，如果你的程序满足任一形式的错误，则按照题目描述中的错误类型输出。例如：`Wrong Answer[3]`。

如果你的程序同时满足多种错误的条件，只会输出一种错误。

hint:
如下是一种可能的交互过程：

| 调用 | 调用 | 返回值 |
| :--: | :--:| :--: |
| `solve(4)` | | |
| | `query([0, 1, 2, 3])` | `3` |
| | `query([1, 3, 0, 2])` | `2` |
| | `query([3, 0, 1, 2])` | `2` |
| | `query([2, 0, 3, 1])` | `0` |
| | `answer([2, 0, 3, 1])` | |

考虑调用 `query([0, 1, 2, 3])`。操作将会按照如下方式进行：

- 交换第 $0$ 本书和第 $1$ 本书的位置。于是，第 $1,0,2,3$ 本书分别被放在位置 $0,1,2,3$ 上。
- 交换第 $1$ 本书和第 $3$ 本书的位置。于是，第 $3,0,2,1$ 本书分别被放在位置 $0,1,2,3$ 上。
- 交换第 $3$ 本书和第 $2$ 本书的位置。于是，第 $2,0,3,1$ 本书分别被放在位置 $0,1,2,3$ 上。

在 $3$ 次操作后，将指定的摆放还原成了正确的摆放，所以返回值为 `3`。

样例满足所有子任务的限制条件。

### 数据范围

- $2 \le N \le 500$；
- $0 \le B_i \le N - 1$（$0 \le i \le N - 1$）；
- $B_i\neq B_j$（$0 \le i < j \le N - 1$）；
- 输入数字全为整数。

### 子任务

1. （$2 $ points）$N \le 6$；
2. （$19$ points）$N \le 100$；
3. （$79$ points）无额外约束。

由 Starrykiller 根据英文题面翻译。


title: [JOI Open 2017] 推土机

description:
**译自 [JOI Open 2017](https://contests.ioi-jp.org/open-2017/index.html) T2 「ブルドーザー / Bulldozer」**

平面上有 $N$ 个点，点 $i\:(1≤i≤N)$ 位于 $(X_i, Y_i)$，点 $i\:(1≤i≤N)$ 的权值为非零整数 $W_i$（可能为负数）。
在平面上画两条平行线，所得的总价值为平行线之间（压线也算）所有点的权值之和。求总价值至多不超过多少。

inputFormat:
第一行包含一个整数 $N$。
在接下来的 $N$ 行中，第 $i$ 行包含三个用空格分隔的整数 $X_i,Y_i,W_i$。

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


title: [JOI Open 2017] 高尔夫

description:
**译自 [JOI Open 2017](https://contests.ioi-jp.org/open-2017/index.html) T3 「ゴルフ / Golf」**

平面的第一象限上有 $N$ 个矩形障碍，矩形的两组对边分别平行于 $x$ 轴和 $y$ 轴。矩形 $i(1\le i\le N)$ 的左下角是 $(A_i, C_i)$，右上角是 $(B_i, D_i)$。任意两个矩形（包括边界）不相交。
JOI 君需要将一个高尔夫球从 $(S,T)$ 打到 $(U,V)$，保证这两点不同，保证这两点不在障碍内或障碍的边界上。
JOI 君只能朝平行于 $x$ 轴或平行与 $y$ 轴的方向击球（JOI 君可以跟着移动）。球可以经过边界，但不能进入障碍物内部。球撞进障碍物后会停下（JOI 君仍然可以朝远离障碍物的方向击球）。
求最少要击球多少次，才能将高尔夫球打进 $(U,V)$。

inputFormat:
第一行有四个整数 $S, T, U, V$。
第二行有一个整数 $N$。
在接下来的 $N$ 行中，每行有四个整数 $A_i, B_i, C_i, D_i$。

outputFormat: 输出一行，一个整数，表示最少击球次数。


title: Normal

description:
某天 WJMZBMR 学习了一个神奇的算法：树的点分治！

这个算法的核心是这样的：

```cpp
time = 0
Solve(Tree a) {
  time += a.size;
  if (a.size == 1) return;
  else {
    select x in a;
    delete a[x];
  }
}
```

```
消耗时间 = 0
Solve(树 a)
  消耗时间 += a 的大小
  如果 a 中 只有 1 个点
    退出
  否则
    在 a 中选一个点x
    在 a 中删除点x
```

那么 $a$ 变成了几个小一点的树，对每个小树递归调用 `Solve`。

我们注意到的这个算法的时间复杂度跟选择的点 $x$ 是密切相关的，如果 $x$ 是树的重心，那么时间复杂度就是 $O(n \log n)$。

WJMZBMR 决定随机在 $a$ 中选择一个点作为 $x$，Sevenkplus 告诉他这样做的最坏复杂度是 $O(n^2)$，但是 WJMZBMR 就是不信，于是 Sevenkplus 花了几分钟写了一个程序证明了这一点，你也试试看吧。

现在给你一颗树，你能告诉 WJMZBMR 他的算法需要的期望消耗时间吗（以给出的 `Solve` 函数中的为标准）？

inputFormat:
第一行一个整数 $n$，表示树的大小；接下来 $n-1$ 行每行两个整数 $a,b$，表示 $a$ 和 $b$ 之间有一条边。

树的结点从 $0$ 开始编号。

outputFormat: 一行一个浮点数表示答案，并四舍五入到小数点后 $4$ 位。

hint: 对于所有的数据，保证 $1\leq n\leq 30000$。


title: BZOJ2989 数列/BZOJ4170 极光

description:
给定一个长度为 $n$ 的正整数数列 $a_i$，两个位置的 $\text{graze}$ 值为两者位置差与数值差的和：$\text{graze}(x,y)=|x-y|+|a_x-a_y|$。

你必须支持两种操作（$k$ 都是正整数）：
- `Modify x k`，表示将第 $x$ 个数的值修改为 $k$；
- `Query x k`，表示询问有几个 $i$ 满足 $\text{graze}(x,i) \leq k$；

询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的 $a_x$ 的 $\text{graze}$ 值 $\leq k$ 的对数。（某位置多次修改为同样的数值，按多次统计。）

inputFormat:
第一行两个整数 $n,q$，表示数列长度与操作数；

第二行 $n$ 个正整数，代表初始数列。

第 $3\sim q+2$ 行，每行一个操作。

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

samples:
3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1

hint: 对于所有数据，保证 $1\leq n\leq 6\times 10^4$，$1\leq$ 修改操作数 $\leq 5\times 10^4$，$1\leq$ 询问次数 $\leq 6\times 10^4$，$1\leq a_i$ 的所有历史版本的最大值 $\leq 10^5$。


title: BZOJ2372 music

description:
最近 A、B 两国发生了一场战争。dick 作为 A 国的军事总指挥，最近非常头痛于己方的情报问题。因为 B 国最近雇佣了 Easy 这一位密码专家来给他们的所有通讯加密。

Easy 非常喜欢唱歌，于是他决定将所有的信号都变成旋律储存起来，比如说 $11556654433221$ 就可能是一段加过密的音符，我们用一个等长度的序列来表示它，就变成了 $1,1,5,5,6,6,\dots$。为了增加密码的保密性，他把加密的乐谱又调整了一下，把某些音调改变了，将原序列 $A$ 变成 $B$，有 $|A|=|B|$，且对于 $a_i=a_j$ 有 $b_i=b_j$，对于 $a_i<a_j$ 有 $b_i<b_j$，对于 $a_i>a_j$ 有 $b_i>b_j$。例如：`11221` 和 `55775` 就可能代表了同一段音符。

最近，dick 截获了一段信号，这段信号中可能包含了某些重要信息。根据以往的经验，dick 已经知道了某些旋律所代表的意义。于是 dick 想知道，对于一段已知的旋律，能不能判断它是否在这段截获的旋律中出现？如果出现了，能否找出它出现的次数及位置呢？

「任务」判断给定旋律在截获旋律中出现的次数及位置。

inputFormat:
第一行三个正整数 $n,m,s$，$n$ 是截获旋律的长度，$m$ 是已知旋律的长度，所有的旋律都是 $1\sim s(s\leq 25)$ 的正整数。

接下来 $n$ 行，每行一个整数描述截获的旋律 $A$；

接下来 $m$ 行，每行一个整数描述已知的旋律 $B$；

outputFormat:
第一行一个整数 $t$ 表示出现的次数。

然后 $t$ 行，按照从小到大给出出现时的起始位置 $p$，即：$A[p\dots p+m-1]$ 等价于 $B$。

hint: 对于所有数据，保证 $1\leq n \leq 10^5$，$1\leq m \leq 25000$。


title: BZOJ3517 翻硬币

description: 有一个 $n$ 行 $n$ 列的棋盘，每个格子上都有一个硬币，且 $n$ 为偶数。每个硬币要么是正面朝上，要么是反面朝上。每次操作你可以选定一个格子 $(x,y)$，然后将第 $x$ 行和第 $y$ 列的所有硬币都翻面。求将所有硬币都变成同一个面最少需要的操作数。

inputFormat: 第一行包含一个正整数 $n$。接下来 $n$ 行，每行包含一个长度为 $n$ 的 $01$ 字符串，表示棋盘上硬币的状态。

outputFormat: 仅包含一行，为最少需要的操作数。

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

对 $(2,3)$ 和 $(3,1)$ 进行操作，最后全变成 $1$。

**【数据范围】**

对于所有数据，$1\leq n \leq 1000$。


title: BZOJ3518 点组计数

description:
平面上摆放着一个 $n\times m$ 的点阵，如下图是一个 $3\times 4$ 的点阵图：

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

现问，有多少个三元点对组 $(a,b,c)$ 满足 $a,b,c$ 三点共线，顺序无关紧要，例如 $(a,b,c)$ 与 $(b,c,a)$ 算一组。答案对 $10^9+7$ 取模。

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

outputFormat: 一行一个整数，表示答案对 $10^9+7$ 取模后的结果。

hint: 数据保证，$1\leq n,m\leq 5\times 10^4$。


title: BZOJ4262 Sum

description:
给定一个长度为 $10^5$ 的整数序列 $a_i$，现进行 $t$ 次询问，每次询问给出 $l_1,l_2,r_1,r_2$ 四个值，要求出：

$$\sum_{l \in [l_1,r_1]} \sum_{r \in [l_2,r_2]} (\max_{i \in [l,r]} a_i-\min_{i\in [l,r]} a_i)$$

的值。不要求强制在线。

本题中的序列 $a_i$ 由如下代码给定生成：

```cpp
const int mod = 1e9;
long long fst = 1023, sec = 1025;
for (int i = 1; i <= 100000; i++) {
	a[i] = fst ^ sec;
	fst = fst * 1023 % mod;
	sec = sec * 1025 % mod;
}
```

inputFormat:
第一行一个数 $t$，表示询问组数。

接下来 $t$ 行，每行四个整数 $l_1, r_1, l_2, r_2$。

outputFormat: 一共 $t$ 行，每行一个数 $\text{Sum}$，表示答案。


title: BZOJ4355 Play with sequence

description:
维护一个长度为 $n$ 的整数序列 $a$，支持三种操作：

- `1 u v c`，对于 $\forall i \in [u,v]$，将 $a_i$ 更改为 $c$；
- `2 u v c`，对于 $\forall i \in [u,v]$，将 $a_i$ 更改为 $\max(a_i+c,0)$；
- `3 u v`，输出 $\sum \limits_{i=u}^v [a_i=0]$ 的值。

inputFormat:
第一行输入两个正整数 $n,m$，表示序列长度和操作个数。

第二行输入 $n$ 个整数 $a_i$，表示序列的初始状态。

第三行开始，往下 $m$ 行，每行表示一个操作。

outputFormat: 输出若干行，每行一个整数，依次回答每个操作 $3$ 的问题。

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

- 对于操作 $1$，保证 $0\leq c\leq 10^9$。
- 对于操作 $2$，保证 $|c| \leq 10^9$。

且对于所有操作，保证 $1\leq u\leq v\leq n$。


title: BZOJ4695 最佳女选手

description:
给定一个长度为 $n$ 的序列，要求支持以下 $6$ 种操作：
- 给一个区间 $[l,r]$ 加上一个整数 $x$；
- 把一个区间 $[l,r]$ 内小于 $x$ 的数都变成 $x$；
- 把一个区间 $[l,r]$ 内大于 $x$ 的数都变成 $x$；
- 求区间 $[l,r]$ 的和；
- 求区间 $[l,r]$ 的最大值；
- 求区间 $[l,r]$ 的最小值；

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

第二行 $n$ 个整数 $a_i$ 表示初始序列。

第三行一个整数 $m$ 表示操作个数。

接下来 $m$ 行，每行三或四个整数，表示一个题目中所描述的操作。

outputFormat: 对于每个 $4,5,6$ 类型的操作输出一行一个整数表示答案。

hint:
数据保证，$1\leq n,m\leq 5\times 10^5$，$|a_i|\leq 10^8$。

当进行 $1$ 操作时，$|x| \leq 1000$；

当进行 $2$ 操作时，$|x| \leq 10^8$。


title: BZOJ2356 不等式

description:
数学中有很多不等式，比如，当 $x,y>0$ 时：

$$x^2+y^2 \geq 2xy$$

$$x^3+y^3 \geq x^2y+xy^2$$

输入两个分别齐次且系数非负的二元多项式 $f(x,y)$ 和 $g(x,y)$，判断是否存在 $A,r>0$，满足对于任意 $x,y>0$，都有 $f(x,y)\geq Ag(x,y)^r$。

inputFormat:
包含多组数据，相邻两组数据之间用一个空行隔开。

每组数据包含两行。

第一行包括 $n+2$ 个非负整数 $n,a_0,a_1,\dots,a_n$，其中 $a_i$ 不全为 $0$，表示 $f(x,y)=a_0x^n+a_1x^{n-1}y+\dots+a_ny^n$。

第二行包括 $m+2$ 个非负整数 $m,b_0,b_1,\dots,b_m$，其中 $b_i$ 不全为 $0$，表示 $g(x,y)=b_0x^m+b_1x^{m-1}y+\dots+b_my^m$。

outputFormat: 对于每组数据，输出一行，若存在则输出 `YES`，否则输出 `NO`。

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

- 对于第一组样例，$x+y \geq \sqrt{2xy}$。
- 对于第二组样例，$x^2+xy+y^2\geq \sqrt[3]{(x^3+y^3)^2}$，展开易证。
- 对于第三组样例，反设 $x^5+x^2y^3 \geq A(x^3y^2+y^5)^r$，对于所有正数 $x,y$ 都成立。取 $x=y$，得 $2x^5\geq A(2x^5)^r$，若 $r>1$，则 $x$ 取充分大时不等式不成立，若 $r<1$，则 $x$ 取足够小时不等式不成立，所以 $r=1$。再取 $x=1$，得 $1+y^3 \geq A(y^2+y^5)$，即 $1\geq Ay^2$，不可能对所有正数 $y$ 成立，故不存在 $A,r$。

**【数据范围】**

最多包含 $100$ 组数据，且 $1\leq n,m\leq 100$，系数大小不超过 $10^4$。


title: BZOJ3252 攻略

background:
众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略 $k$ 部游戏。

今天他得到了一款新游戏《XX 半岛》，这款游戏有 $n$ 个场景，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同时攻略 $k$ 次该游戏，问他观赏到的场景的价值和最大是多少？（同一场景观看多次是不能重复得到价值的）

>“为什么你还没玩就知道每个场景的价值呢？”
>“我已经看到结局了。”

description: 给定一个有 $n$ 个结点的树，树有点权且点权为正整数。现选取 $k$ 条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。

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

第二行输入 $n$ 个正整数 $w_i$，表示每个结点的点权。

第三行输入 $n-1$ 行，每行 $2$ 个正整数 $u,v$，表示结点 $u$ 是结点 $v$ 的父亲。

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

hint: 对于所有数据，保证 $1\leq n\leq 2\times 10^5$，$1\leq w_i\leq 2^{31}-1$。


title: 「SFMOI Round I」Strange Dino Game

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

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

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

Watersphere 同学在家没网了，只好玩起了 dino 游戏，但是他很菜，一玩到后面就头晕眼花，所以想让你编个程序帮助他拿到更高分，于是有了这题。

本题的游戏背景是 [Dino](https://dinosaur.game)。可以考虑点击链接游玩，以便更好理解题意。

description:
我们将问题放在二维平面上描述。我们给出一些游戏要素：

- 玩家：Dino。可以将其视为一个点。
- 障碍物：
    - 仙人掌：形如 $(x_i',0),(x_i',h_i)$ 的线段。
    - 飞鸟：形如 $(x_i,d_i),(x_i,u_i)$ 的线段。
- 游戏结束：Dino 与障碍物上的任意一点（包括线段端点）重合时，游戏结束。
- 起点：原点 $(0,0)$。
- 终点：使游戏结束的位置，位于第一象限（或 $x$ 轴上）。可能不存在（即游戏能无限进行）。
- 游戏分数：终点的 $x$ 坐标。终点不存在时定义为无穷大。
- 跳跃参数：正整数 $d,h$。
- 步行：Dino 在 $x$ 轴上沿着 $x$ 轴正方向移动。
- 跳跃：当 Dino 在 $x$ 轴上时，可以进行一次跳跃。以起跳点为原点，跳跃轨迹为
    $$f(x) = \begin{cases}
    \displaystyle  \frac{h}{d}x & x\in [0, d)  \\
    \displaystyle-\frac{h}{d}x+2h  & x\in [d, 2d)  \\
    \end{cases}$$
    - 需要注意的是，由上述定义可以推出：**在一次跳跃后落地的瞬间进行第二次跳跃是合法的。**
    - 需要注意的是，可以在任意**实数点**（只要在 $x$ 轴上）处开始跳跃。也就是说，跳跃不一定在整点开始。

下图展示了 $d=2,h=6$ 时的一次跳跃。

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

在一局游戏中，Dino 从起点出发向 $x$ 轴正方向移动。目标是最大化得分，即尽量避开障碍物，使自己移动的距离尽量长。

每一时刻，Dino 只能做一件事：步行，或跳跃。当且仅当 Dino 在 $x$ 轴上时可以进行跳跃。

形式化地说，Dino 的行为可以被描述为一个长度为 $(k+1)$ 的实数二元组序列 $[(x_0,t_0),(x_1,t_1),\cdots,(x_k,t_k)]$，满足：

- $x_0=0$；
- $t_i\in \{0,1\}$；
- $\forall 0\le i\lt k$, $x_i\lt x_{i+1}$；
- $t_i=1,i\lt k\implies x_{i+1}-x_i\ge 2d$；(二段跳是不允许的)
- $\forall 0\le i\lt k$, $t_i=t_{i+1}\implies t_i=t_{i+1}=1$。

当 $t_i=0$ 时，我们定义 Dino 在 $x_i$ **进入步行状态**，否则定义 Dino 在 $x_i$ **进入跳跃状态**。

当 Dino 与障碍物重合时，游戏结束。此时 Dino 在的位置为终点，得分为终点的 $x$ 坐标。

已知有 $b$ 只飞鸟和 $c$ 个仙人掌，求出 Dino 的最大得分。特别地，得分可以为无穷大。

可参阅样例解释的图片。

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

第一行，一个正整数 $T$，代表游戏次数。

接下来依次描述 $T$ 组数据：

- 每组数据第一行，两个正整数 $d,h$，表示 dino 的跳跃参数。
- 每组数据第二行，两个整数 $b,c$，表示飞鸟个数与仙人掌个数。
- 接下来 $b$ 行，每行三个正整数 $x_{i},u_i,d_i$，描述第 $i$ 只飞鸟。
- 接下来 $c$ 行，每行两个正整数 $x'_{i},h_{i}$，描述第 $i$ 株仙人掌。

outputFormat:
对于每组数据输出一行，表示得分的最大值。

特别地，如果得分为正无穷，输出 `Dino!`。

hint:
样例 $1$ 解释：

- 对于第 $1$ 组数据，dino 无论如何也无法跳过连续的两株高为 $2$ 的仙人掌，答案即为第二株仙人掌的 $x$ 轴坐标。
- 对于第 $2$ 组数据，dino 可以在原点直接起跳跳过唯一的一只鸟，也完全可以不起跳从飞鸟下方走过。

其中第一组数据的解释如下所示，红线代表飞鸟，绿线代表仙人掌，粉线代表 Dino 的轨迹。

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

### 数据范围

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

- Subtask 1（5 pts）：$c=0$；
- Subtask 2（5 pts）：$b,c \le 10$；
- Subtask 3（20 pts）：$b=0$；
- Subtask 4（20 pts）：$1 \le d,h,x_{b_i},d_i,u_i,x_i',h_i \le 10^5$;
- Subtask 5（40 pts）：无特殊限制。
- Subtask 6（10 pts）：无特殊限制。

对于 $100\%$ 的数据，保证：
- $1 \le T \le 10$；
- $0 \le b,c \le 2\times 10^4$；
- $1 \le d,h,x_{b_i},d_i,u_i,x_i',h_i\le 10^9$；
- $d_i\le u_i$。


title: [洛谷 202406GESP 模拟 四级] 小苏的键盘

type: B

description:
小苏同学有一个文本编辑器和一个奇怪的键盘。这个键盘有 26 个小写英文字母和退格键(backspace)，一共 27 个键。

每次当她按下任何一个小写英文字母的键的时候，文本编辑器就会在当前编辑文本的末端添加对应的字母。
例如，假设当前文本是 `luog`，当她按下 `u` 键时，文本就会变成 `luogu`。

当她按下退格键的时候，文本编辑器就会删除当前文本的**最后一个**字母。如果当前文本是空的，则什么都不会发生。
例如，如果当前文本是 `luogu`，当她按下退格键后，文本就会变成 `luog`。

现在，给定小苏的按键情况，已知在初始时文本为空，请你求出小苏按完给定的所有键后的文本是什么。

inputFormat:
第一行是一个整数 $n$（$1 \leq n \leq 100$），表示按键的次数。
第二行是 $n$ 个用空格隔开的字符串，依次表示小苏按下的每个按键。

输入的每个字符串要么是一个小写字母，表示对应的按键，要么是字符串 `<bs>`，表示退格键。

outputFormat: 输出一行一个字符串，表示小苏按完给定的所有按键后的文本。**数据保证输出不是空串**。


title: [洛谷 202406GESP 模拟 四级] 锣鼓工厂

description:
小苏同学是锣鼓工厂的厂长。锣鼓工厂共有 $n$ 台机器，第 $i$ 台机器工作一天可以生产 $a_i$ 个锣鼓。因为环保、资金和保养问题，在接下来的 $n$ 天里，每天只能使用一台机器进行生产，每台机器在 $n$ 天里只能被使用一次。

同时，小苏接到了 $n$ 笔订单，第 $i$ 笔订单要求交付 $b_i$ 个锣鼓。小苏同学想知道，是否存在一种合理安排机器使用和交付订单的顺序，使得她在接下来的 $n$ 天里，每天都能交付一个订单？

inputFormat:
**本题单个测试点内有多组测试数据**。第一行是一个整数 $T$（$1 \leq T \leq 10$），表示数据组数。对每组数据，按如下格式输入：

每组数据第一行是一个整数 $n$（$1 \leq n \leq 10^3$），表示机器数和订单数。
第二行有 $n$ 个整数 $a_1, a_2, \dots a_n$（$1 \leq a_i \leq 10^4$），依次表示每台机器工作一天可以生产的锣鼓数量。
第三行有 $n$ 个整数 $b_1, b_2, \dots b_n$（$1 \leq b_i \leq 10^4$），依次表示每个订单要求交付的锣鼓数量。

outputFormat:
对每组数据，输出一行或三行：

- 如果不存在一种方案使得她在接下来的 $n$ 天里，每天都能交付一个订单，输出一行一个字符串 `No`。
- 否则输出三行：
  + 第一行输出 `Yes`。
  + 第二行输出 $n$ 个整数，$x_1, x_2, \dots x_n$，其中 $x_i$ 表示在第 $i$ 天使用的机器的**编号**。
  + 第三行输出 $n$ 个整数，$y_1, y_2, \dots y_n$，其中 $y_i$ 表示在第 $i$ 天交付的订单的**编号**。

$x_i$ 和 $y_i$ 必须是 $1 \sim n$ 范围内的整数，且每个数字在 $x_i, y_i$ 中**恰好**出现一次。

对于输出 `Yes` 的情况，可能有多种合理的方案，你可以**输出任意一种**。只要你输出的方案是正确且合理的即可得分。

hint:
### 样例 1 解释

- 在第一天使用编号为 $1$ 的机器生产了 $3$ 个锣鼓，交付编号为 $3$ 的订单 $3$ 个锣鼓。
- 在第二天使用编号为 $2$ 的机器生产了 $2$ 个锣鼓，交付编号为 $1$ 的订单 $2$ 个锣鼓。
- 在第三天使用编号为 $3$ 的机器生产了 $1$ 个锣鼓，交付编号为 $1$ 的订单 $1$ 个锣鼓。

### 样例 2 解释

我们解释第二组数据：

- 在第一天使用编号为 $2$ 的机器，生产了 $20$ 个锣鼓。交付编号为 $1$ 的订单 $15$ 个，剩余 $5$ 个；
- 在第二天使用编号为 $1$ 的机器，生产了 $10$ 个锣鼓，加上上一天的 $5$ 个，共 $15$ 个锣鼓，交付编号为 $2$ 的订单 $15$ 个，剩余 $0$ 个。
- 在第三天使用编号为 $3$ 的机器，生产了 $30$ 个锣鼓，共 $30$ 个锣鼓，交付编号为 $2$ 的订单 $15$ 个，剩余 $15$ 个。

### 提示

样例输出不唯一，仅供参考。


title: 【MX-J1-T3】『FLA - III』Anxiety

background: I came. I saw. I had anxiety. I left.

description:
给定一棵拥有 $2^n-1$ 个节点的二叉树，节点 $i$ 的权值为 $w_i$，节点 $1$ 为根节点。对于所有非根节点 $i$ 都有一条双向边连接节点 $i$ 和节点 $\left\lfloor \frac{i}{2} \right\rfloor$。请注意 $\left\lfloor X \right\rfloor$ 表示不大于 $X$ 的最大整数。

定义节点 $u,v$ 的距离为从节点 $u$ 到节点 $v$ 最少需要经过的边数。给定 $m$ 组询问，第 $i$ 组询问给定三个正整数 $x_i,y_i,k_i$，你需要输出树上与 $x_i,y_i$ 两个节点的距离都不超过 $k_i$ 的节点的权值之和。

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

第二行输入 $2^n-1$ 个正整数，第 $i$ 个正整数为 $w_i$。

接下来 $m$ 行，第 $i$ 行输入三个正整数 $x_i,y_i,k_i$。

outputFormat: 输出 $m$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 组询问的答案。


title: [NordicOI 2022] 嬉皮爵士 Hipster Jazz

background:
译自 Nordic Olympiad in Informatics 2022  [Hipster Jazz](https://noi22.kattis.com/contests/noi22/problems/hipsterjazz)。如果发现 SPJ 锅了请联系搬题人 qvq。

$\texttt{1s,1G}$。

description:
爵士学校里，新班级诞生了。这个班级里有 $N$ 名学生，其中有 $M$ 对朋友关系。每个学生要选择一种主修乐器：钢琴，或者萨克斯。当然，所有的学生都希望成为有创意的爵士音乐家，所以他们想要保证，至少有一半朋友主修的乐器和自己主修的乐器不一样。

学生们发现，选择乐器是一件很困难的事情。于是他们找来了你，希望你能够为每个同学选择一个主修乐器，满足上述条件。

数据保证至少存在一种方案。

inputFormat:
第一行，两个正整数 $N,M$，含义见题面。

接下来 $M$ 行，每行两个数 $a,b$，表示 $a,b$ 是朋友。

保证同一对朋友不会被列出两次。保证至少存在一种方案。

outputFormat: 输出一行含 $N$ 个字符的字符串。第 $i$ 个字符为 `P`，代表第 $i$ 名学生选择钢琴；第 $i$ 个字符为 `S`，代表第 $i$ 名学生选择萨克斯。


title: [NordicOI 2022] 能源网格 Power Grid

background:
译自 Nordic Olympiad in Informatics 2022  [Power Grid](https://noi22.kattis.com/contests/noi22/problems/powergrid)。如果发现 SPJ 锅了请联系搬题人 qvq。

$\texttt{5s,1G}$。**请不要滥用本题评测。**

description:
有一座城市，由 $N$ 行 $M$ 列共 $N\times M$ 个方格组成。方格 $(i,j)$ 的电力消耗是未知的，不妨记为 $A_{i,j}$。由于方格中可能建有发电厂，或者那里压根就没有建筑物，所以 $A_{i,j}$ 可以为正数，负数或者 $0$。

先前，多亏了廉价的太阳能，该城市拥有着几乎无限制的能源供应。然而，在数以百万计的通信卫星碰撞的事故后，只有一半的阳光能够照射到地球，发电厂不得不使用更昂贵的能源来源。因此，能源公司必须开始向客户收取电费，但不幸的是，没有人安装了合适的电表。

在缺乏有效的对单个方格的测量方法的情形下，发电厂用一行和一列的用电数据来估计单个方格的耗电量。具体地说，对于方格 $(i,j)$，有

$$C_{i, j} = \left|
    \sum _{k=1}^ N A_{k, j} - \sum _{k=1}^ M A_{i, k} \right| $$

即，一行的总用电量与一列的总用电量的差值的绝对值。

给定所有的 $C_{i,j}$，你能否构造出一组合法的 $A_{i,j}$？

数据保证至少存在一组解。

inputFormat:
第一行，两个正整数 $N,M$，含义见题面。

接下来 $N$ 行，第 $i$ 行第 $j$ 个数为 $C_{i,j}$，含义见题面。

保证至少存在一组解。

outputFormat:
输出 $N$ 行 $M$ 列，第 $i$ 行第 $j$ 个数为 $A_{i,j}$。

多解时，任意输出一组解均可。

你需要保证 $-2^{31}\le A_{i,j}\lt 2^{31}$。


title: [NordicOI 2022] 夸克显微镜 Quark Microscopy

background:
译自 Nordic Olympiad in Informatics 2022  [Quark Microscopy](https://noi22.kattis.com/contests/noi22/problems/quarkmicroscopy)。如果发现交互库锅了请联系搬题人 qvq。

$\texttt{1s,1G}$。

description:
这下可惨了！Niels 珍爱的原子被宇宙射线击中，分裂成了许多夸克。Niels 迫切地想要找到这些夸克，然后将它们拼起来。所以，他找来了你来帮忙。

这 $N$ 个夸克分布在一条 $1$ 米（$10^{18}$ 阿米）长的线段上。幸运的是，你有一个很精确，但有点奇怪的夸克显微镜，它能够检测并测量邻近的夸克。然而由于量子效应，它无法直接告诉你离测量位置最近的夸克的位置，而是会告诉你离测量位置第二近的夸克的位置，以及离测量位置第二近的夸克的数量。

更为准确地说，你可以在线段上的位置 $x$ 处进行测量。对于每次测量，每个夸克距 $x$ 的距离将会被测出并升序排序，记为 $d_1,d_2,\cdots,d_N$。你会得到 $d_2$，和满足 $d_i=d_2$ 的 $i$ 的数量（只会是 $1$ 或 $2$）。在进行足够多次测量后，你需要回答每个夸克所在的位置。

每个夸克的位置都是介于 $[1,10^{18}]$ 间的正整数（单位：阿米），从线段的起始位置开始计算。由于 Pauli 不相容原理，夸克的位置不会重合。

inputFormat:
你的程序与交互库通过标准输入输出流交互。

第一行，两个正整数 $N,T$，表示夸克的数量和子任务编号。

接下来，你的程序开始与交互库交互：

- `? x`：询问离 $x$ 第二远的夸克。交互库会返回两个整数 $r,m$，其中 $r$ 是第二远夸克的距离，$m$ 是距离 $x$ 为 $r$ 的夸克的数量（只会是 $1$ 或 $2$）。你需要保证 $-10^{18}\le x\le 2\times 10^{18}$。

- `!` $a_1$ $a_2$ $\cdots$ $a_N$：回答夸克的位置。你可以以任意顺序给出这些夸克的位置。回答后，不应有多余的询问。你需要保证 $1\le a_i\le 10^{18}$。

**注意：在交互过程中，你需要在输出后刷新缓存区。**
下面是一些常见语言的刷新缓存区方式：

- C++：`fflush(stdout)` 或 `cout.flush()`。特别地，利用 `std::endl` 换行也会刷新缓冲区。
- C：`fflush(stdout)`。

outputFormat: 见【输出格式】。


title: 「SFMOI Round I」Strange Cake Game

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

小 $\mathcal{W}$ 和 小 $\mathcal{M}$ 在 CF 庄园里分蛋糕。

description:
有一块面积为 $n\times m$ 的矩形蛋糕。记其左上角顶点为 $(0,0)$，右下角顶点为 $(n,m)$，右上角顶点为 $(0,m)$。

蛋糕上分布着 $k$ 块巧克力，第 $i$ 块的位置为 $(x_i-0.5,y_i-0.5)$。**一个点上可能有不止一块巧克力。**

小 M 和 小 W 要切蛋糕。蛋糕刀起初在 $(0,0)$，小 W 先手，轮流移动蛋糕刀。设蛋糕刀在 $(x,y)$，则它可以被移动到 $(x,y+1)$ 或 $(x+1,y)$。

在若干步后，蛋糕会被切割轨迹完全分成两个部分——右上角的部分归小 W，左下角的部分归小 M。小 W 和小 M 都想吃到最多的巧克力，请帮他们计算：如果双方都按照最优策略行动，小 W 能分到几块巧克力。

如下是蛋糕的示例和一种可能的切蛋糕的方式。

![蛋糕示例](https://cdn.luogu.com.cn/upload/image_hosting/er9wuv91.png?x-oss-process=image/resize,m_lfit,h_500)
![切蛋糕示例](https://cdn.luogu.com.cn/upload/image_hosting/9o6ntvlb.png?x-oss-process=image/resize,m_lfit,h_500)

inputFormat:
第一行，两个正整数 $n,m$，含义见题面。

第二行，一个整数 $k$ ，表示巧克力块数。

接下来 $k$ 行，每行两个正整数 $x_i,y_i$，表示第 $i$ 块巧克力的坐标为 $(x_i-0.5,y_i-0.5)$。

注意：第 $i$ 块巧克力的坐标为 $(x_i-0.5,y_i-0.5)$。**一个格子上可能有多块巧克力。**

outputFormat: 输出一个整数，代表小 W 最多能拿到的巧克力块数。

hint:
### 数据范围

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

- Subtask 1（5 pts）：$n=m=1$；
- Subtask 2（10 pts）：$1 \le n \times m \le 60$；
- Subtask 3（15 pts）：$1 \le n \times m \le 10^5$；
- Subtask 4（20 pts）：$k=1$；
- Subtask 5（50 pts）：无特殊限制。

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

- $0 \le k \le 2 \times 10^5$；
- $1 \le n,m \le 10^{18}$；
- $1 \le x_i \le n$，$1 \le y_i \le m$。


title: Hide And Seek

description:
Drifty 在和 hgcnxn 玩躲猫猫。

整个地图有 $n$ 个房间，由 $n-1$ 条走廊连接（保证对于任意的两个房间都能互相抵达）。

对于游戏的每一回合，hgcnxn 先走一步，Drifty 后走一步（特别的，hgcnxn 必须走一步，而 Drifty 可以不动）。

hgcnxn 从编号为 $p$ 的房间开始，任务是要抓到 Drifty，hgcnxn 通过雷达，得知了 Drifty 一开始所在的房间编号 $q$，hgcnxn 会预先设计一条尽可能优的抓捕方案，并按照计划抓捕 Drifty。**但 hgcnxn 并不知道接下来的回合中 Drifty 的位置。**

但是，Drifty 更加狡猾，他提前预知了 hgcnxn 的整个计划，并采用了最优的方案尝试去避开 hgcnxn。但是鉴于地图的原因，Drifty 可能还是会被抓到。

特别的，hgcnxn 并不知道 Drifty 能够提前知道他的整个计划。

现在给你 $n, p, q$ 和地图，问你在有限的回合内，hgcnxn 是否可能抓到 Drifty。

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

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

对于每组数据：

第一行三个整数 $n, p, q$。

接下来 $n-1$ 行，每行两个节点 $u, v$，表示一条走廊连接的两个房间。

outputFormat:
对于每组数据：

一个字符串，若 hgcnxn 可能抓到 Drifty，输出 `hgcnxn`，若 hgcnxn 不可能抓到 Drifty，输出 `Drifty`。

特别的，对于答案的判定，我们不区分大小写。

如果应输出 `Drifty`，但您输出了 `driFtY`，您将被判定作正确。

hint:
#### 【数据范围】

设 $\sum n$ 表示单个测试点中 $n$ 的和。

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

- $3\le \sum n\le 2\times 10^5$
- $1\le p,q\le n$
- $1\le T\le 10^3$。

以下是部分分的具体分配：

|$\text{Subtask}$|$\sum n\leq$|分值| 特殊性质 |
|:-:|:-:|:-:|:-:|
|$0$|$2\times 10^5$|$1$| A |
|$1$|$2\times 10^5$|$2$| B |
|$2$|$7$|$3$| 无 |
|$3$|$2\times 10^5$|$9$| C |
|$4$|$2\times 10^5$|$85$| 无 |

- 特殊性质 A：保证所有给定的地图的形态均为一条链。
- 特殊性质 B：保证所有给定的地图的形态均为菊花图（即地图中 $n-1$ 个房间度数为 $1$）。
- 特殊性质 C：保证地图中只存在一个度数为 $3$ 的房间，且其余的房间度数均 $\le 2$。

其中，一个房间的度数被定义为连接该房间的走廊数。


title: 【MX-X1-T6】「KDOI-05」简单的图上问题

description:
给你一个 $n$ 个点 $m$ 条边的边双连通图，并且给定了每个点的坐标，保证每条边不相交或者只在端点处重合。

给定 $k$ 个图上的简单环 $C_1,C_2,\dots,C_k$，定义 $G_i$ 为只考虑 $C_i$ 内部的点和边所组成的图。

对 $S\subseteq\{1,2,\dots,k\},S=\{s_1,s_2,\dots,s_t\}$，定义 $f(S)$ 表示所有 $G_{s_i}$ 交的连通块数量。

有 $q$ 个询问，每次给出一个 $z$，输出 $\sum_{S\subseteq\{1,2,\dots,k\},|S|=z}f(S)$。对 $998244353$ 取模。

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

接下来 $n$ 行，每行两个整数 $(x_i,y_i)$ 表示第 $i$ 个点的坐标。保证所有 $1\leq i<j\leq n$，都有 $x_i\neq x_j,y_i\neq y_j$。

接下来 $m$ 行，每行两个正整数 $u_i,v_i$，表示一条连接 $(u_i,v_i)$ 的无向边。

接下来 $k$ 行，每行第一个正整数 $l_i$ 表示环的大小，接下来 $l_i$ 个正整数 $C_{i,1},C_{i,2},\dots,C_{i,l_i}$ 表示一个原图的简单环，保证 $C_{i,j}$ 按顺序连接可以得到原图上的一个环。

接着一行一个正整数表示 $q$。

最后 $q$ 行，每行一个正整数表示询问的 $z_i$。

outputFormat: 输出 $q$ 行，每行一个整数表示 $\sum_{S\subseteq\{1,2,\dots,k\},|S|=z}f(S)$ 对 $998244353$ 取模后的值。

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

样例 $1$ 的数据如图：

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

**【数据范围】**

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

| 子任务编号 | 分值 | $n\leq$ | 特殊性质 |
|:--:|:--:|:--:|:--:|
| $1$ | $15$ | $10$ | 无 |
| $2$ | $30$ | $1000$ | 无 |
| $3$ | $30$ | $4\times10^4$ | 保证平面图是一个凸包的三角剖分 |
| $4$ | $15$ | $4\times10^4$ | 无 |
| $5$ | $10$ | $10^5$ | 无 |

对于 $100\%$ 的数据：$1\leq n,\sum l_i\leq10^5$，$1\leq m\leq 3n-6$，$3\leq l_i$，$0\leq |x_i|,|y_i|\leq 10^9$，$1\leq q\leq 20$，$1\leq u_i,v_i\leq n$，$u_i\neq v_i$，$1\leq z_i\leq k$。保证所有 $1\leq i<j\leq n$，都有 $x_i\neq x_j,y_i\neq y_j$。保证每条边不相交或者只在端点处重合，保证图是一个边双连通分量。


title: [洛谷 202406GESP 模拟 三级] 小洛的数字游戏

description:
小洛有一个正整数 $n$，他会进行若干次下列操作：

- 取出正整数 $n$ 的末位，记作 $x$；
- 将 $x$ 平方之后，保留个位，放于 $n$ 的首位之前（如果是 $0$，则数字不保留前导 $0$）；

上述两步合计为一次操作。例如有一个正整数 $142$，它可以进行如下操作：

- 取出末尾的 $2$，原正整数变为 $14$；
- $2^2=4$，放于 $14$ 首位之前成为 $414$，第一次操作完成；
- 取出末尾的 $4$，原正整数变为 $41$；
- $4^2=16$，保留个位的 $6$，放于 $41$ 的首位成为 $641$，第二次操作完成；
- 以此类推……

现在小洛想知道，对于一个正整数 $n$，能否进行**不超过 $q$ 次**操作让其变为正整数 $m$。请你帮帮他。

inputFormat: 输入三个正整数 $n,m,q$。

outputFormat: 如果能进行不超过 $q$ 次操作让正整数 $n$ 变为正整数 $m$，则输出若干行，第 $i$ 行输出一个正整数表示进行第 $i$ 次操作后的正整数 $n$ 的值。否则输出一行一个整数 $-1$。

hint:
对于 $30\%$ 的数据，保证小洛实际只需要不超过 $5$ 次操作即可得到 $m$；

对于所有数据，数据保证 $1\leq n,m\leq 10^9$，$1 \leq q \leq 10^6$。


title: [洛谷 202406GESP 模拟 三级] 小洛的字符串分割

description:
对于一个字符串 $S$，小洛定义它为 **回文** 的，当且仅当字符串 $S$ 从左往右读和从右往左读一样，例如 $\tt abcba$ 是回文的，而 $\tt abcca$ 不是。

小洛现在有一个字符串 $S$，他想将这个字符串分为若干段，段长度分别为 $1,2,3,\dots$。具体而言，他会先将第一个字符拿出来作为字符串 $S_1$，再将第 $2,3$ 个字符拿出来作为 $S_2$，再将第 $4,5,6$ 个字符拿出来作为 $S_3$，以此类推……最后若还有多余的字符，则单独作为一段。

例如说，对于字符串 $\tt aaababcaacd$，会被分为如下的五个字符串：

- $S_1=\tt a$；
- $S_2=\tt aa$；
- $S_3=\tt bab$；
- $S_4=\tt caac$；
- $S_5=\tt d$；

字符串 $\tt aaababcaacd$ 分割出的 $5$ 个字符串都是回文的。

小洛想要知道，对于读入的字符串 $S$，这些被分割出来的字符串，有**多少个**是回文的呢？

inputFormat: 输入一行，一个字符串 $S$。

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

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

- 对于第 $1$ 组样例，已经在题面中进行表述；
- 对于第 $2$ 组样例，$S_1=\tt a$，$S_2=\tt ba$，$S_3=\tt cdc$，$S_4=\tt aaba$，其中 $S_1$ 与 $S_3$ 为回文字符串。

**【数据范围】**

假定记号 $|S|$ 表示字符串 $S$ 的长度。

- 对于 $10\%$ 的数据，字符串至多包含一种字母；
- 对于 $30\%$ 的数据，字符串至多包含两种字母；
- 对于 $70\%$ 的数据，$|S|\leq 1000$；
- 对于所有数据，$1 \leq |S| \leq 10^6$，字符串仅包含英语小写字母。


title: 「SFMOI Round I」Strange Train Game

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

SFM 团队又断网了，于是玩起了 Mini Metro，结果发现游戏更新了，列车要自己组装，于是有了这题。

description:
**提示**：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

SFM 号列车由 $n$ 节车厢组成，编号为 $1\sim n$。每节车厢有一个舒适度 $a_i\in \{0,1\}$，$0$ 代表不舒适，$1$ 代表舒适。管理组想要让舒适的车厢的编号尽量小，也就是说，让 $a$ 的字典序最大。

为此，管理组运来了一辆 $n$ 节车厢的备用车，舒适度表示为 $b_i\in \{0,1\}$。共有 $m$ 个可进行的操作，第 $i$ 个操作的操作参数为 $l_i,r_i$，表示 $\forall l_i\le k\le r_i$，交换 $a_k,b_k$。

可以**从小到大依次**决定是否执行每个操作，但是一共有 $2^m$ 种方案，于是，管理组找来了你，帮忙选出一种最优的方案，最大化 $a$ 的字典序。只需要输出最终得到的 $a$ 即可。

**形式化地**：给定长度为 $n$ 的 $01$ 串 $a,b$，给定 $2m$ 个正整数 $l_i,r_i$。对于 $i=1,2,\cdots,m$，**依次**执行以下操作：
- 选择是否执行第 $i$ 次操作。
    - 如果执行，则对于 $k=l_i,l_{i}+1,\cdots,r_i$，交换 $a_k,b_k$。

最大化 $a$ 的字典序并输出最终的结果。

inputFormat:
第一行，两个正整数 $n,m$，表示字符串的长度和操作次数。

第二行，一个长度为 $n$ 的 $01$ 串 $a$。

第三行，一个长度为 $n$ 的 $01$ 串 $b$。

接下来 $m$ 行，每行两个正整数 $l_i,r_i$，描述第 $i$ 个操作。

outputFormat: 输出一行长度为 $n$ 的 $01$ 串，表示最优操作后的 $a$。

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

- Subtask 1（20 pts）：$1\le n,m\le 20$；
- Subtask 2（30 pts）：$l_i$ 互不相同，$a_i \ne b_i$；
- Subtask 3（30 pts）：$1 \le n ,m \le 10^3$；
- Subtask 4（20 pts）：无限制；

对于 $100\%$ 的数据，保证：
- $1\le n,m\le 2\times 10^5$；
- $1\le l_i\le r_i\le n$。


title: 【MX-S1-T1】壁垒

description:
给定一个长度为 $n$ 的仅包含正整数的数列 $a$，保证 $n$ 是偶数。你需要重排 $a$，满足对于 $a$ 的每个长度为偶数的前缀，出现的数字种类数是偶数，或断定这样的重排方式不存在。

如果有多种重排方式满足条件，输出任意一种即可。

inputFormat:
第一行一个正整数 $n$，保证 $n$ 是偶数。

第二行一个 $n$ 个正整数，描述数列 $a$。

outputFormat:
无解时输出 $-1$，否则输出一行 $n$ 个整数，描述重排后的数列 $a$。

本题使用**自定义校验器**检验你的答案是否正确，如果有多种重排方式满足条件，输出任意一种即可。


title: 【MX-S1-T2】催化剂

description:
小朋友们很喜欢糖果。

现在，小 K 有一些糖果，每个糖果上有一个数字代表它的种类。

有 $q$ 次事件，每次事件会加入一个糖果、或删除一个糖果、或提出一次询问。

每次询问会给出一个 $k$，表示小 K 现在需要将所有糖果分给 $k$ 个小朋友，并且每个小朋友都需要得到至少一个糖果。同时，小朋友们不喜欢得到相同的糖果。具体的，在一个小朋友得到了糖果 $i$ 时，如果 Ta 在这个糖果之前就已经获得过糖果 $i$，那么 Ta 就会感到非常生气，Ta 的愤怒值就会增加 $1$。

小 K 不喜欢看到小朋友们生气，但小 K 无法解决这么困难的问题，所以你需要帮小 K 求出一种分糖果的方式，最小化所有小朋友的愤怒值之和。

保证存在一种分糖果的方案，使得每个小朋友都分到至少一个糖果。

每次询问并没有真正的分糖果，即每次询问后小 K 拥有的糖果不会改变。

注意，分糖果的过程可以理解为将小 K 拥有的所有糖果划分到 $k$ 个非空序列，可以重排。

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

第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$，描述初始时小 K 拥有的糖果。

接下来 $q$ 行，每行两个正整数，描述一次操作，共有三种可能的输入：

`1 x`：表示小 K 又拥有了一个种类为 $x$ 的糖果。

`2 x`：表示小 K 丢失了一个种类为 $x$ 的糖果，保证此时小 K 拥有至少一个种类为 $x$ 的糖果。

`3 k`：表示此时小 K 需要把糖果分给 $k$ 个小朋友，你需要求出最小的所有小朋友的愤怒值之和。令 $S$ 表示此时小 K 拥有的糖果数量，保证 $1\le k\le S$。

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


title: 【MX-S1-T4】先见之明

description:
给定 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$。有 $q$ 次询问，每次询问：

- 给定一个非负整数 $k$，你需要从 $2^{a_1}, \ldots, 2^{a_n}$ 中取出一部分（即一个子集，可以为空），使得它们的和 $\ge k$。
- 在保证和 $\ge k$ 的前提下，你需要最小化它们的和。你只需求出这个最小化的和。
- $k$ 以二进制的形式给出，具体地，以 $k = \sum_{i = 1}^{m} 2^{p_i}$ 的形式给出，保证 $p_i$ 均为非负整数且严格单调递减，即 $p_i > p_{i + 1}$。

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

若无法从 $2^{a_1}, \ldots, 2^{a_n}$ 中取出一部分使得它们的和 $\ge k$，该询问输出 $-1$。

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

第二行 $n$ 个非负整数 $a_1,a_2,\dots,a_n$。

接下来 $q$ 行，每行第一个非负整数为 $m$，接下来 $m$ 个非负整数为 $p_1,p_2,\dots,p_m$，表示询问的 $k=\sum_{i=1}^m 2^{p_i}$。保证 $p_i$ 严格单调递减，即 $p_i>p_{i+1}$。

outputFormat: 共 $q$ 行，每行一个整数，表示答案对 $998244353$ 取模后的结果，或输出 $-1$ 表示无解。

samples: 见下发文件。 见下发文件。


title: 【MX-S1-T3】电动力学

description:
给定一张包含 $n$ 个点 $m$ 条边的简单无向连通图，点的编号为 $1\sim n$。

你需要求出有多少集合对 $S,T\sube \{1,2,\dots,n\}$，满足对于任意的 $i\in S$，要么 $i$ 也 $\in T$，要么存在 $x,y\in T$（$x\neq y$），满足存在一条从 $x$ 到 $y$ 的简单路径经过 $i$。

注意，集合对 $S,T$ 可以为空集。

输出答案对 $998244353$ 取模后的结果。

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

接下来 $m$ 行，每行两个正整数 $u_i,v_i$，描述图上的一条边。保证图连通，无自环、重边。

outputFormat: 共一行一个整数，表示满足题目条件的集合对 $S,T$ 的数量对 $998244353$ 取模后的结果。


title: [SNCPC2024] chmod

description:
$\text{chmod}$ 是一个用于更改文件或目录权限的命令，它是 Linux 和其他类 Unix 操作系统中的常用命令之一。$\text{chmod}$ 命令允许用户为文件或目录设置不同的权限，以控制谁可以读取，写入或执行这些文件。

在 Linux 系统中，每个文件或目录都有与之相关联的权限, 这些权限决定了谁可以对文件进行何种操作。用户被分为三类：所有者（owner），所属组（group）和其他人（others）。每类用户又都有读 （r），写（w）和执行（x）三种权限。这 $9$ 种权限可以分别指定。我们称**权限字符串**是一个长度为 $9$ 的字符串，按顺序分别对应以上提到的 $9$ 种权限，如果具有此权限，则为 $\text{r}$，$\text{w}$，$\text{x}$ 中相应的那一个，否则为 $\text{-}$。

例如**权限字符串** $\text{rwxr-x-}\text{-x}$ 说明，该文件对于所有者具有全部权限，对于所属组用户只具有读和执行权限，而对于其他人只具有执行权限。

使用 $\text{chmod}$ 命令时，你可以提供模式串来修改权限。在本题，我们只考虑长度为 $3$ 的由不大于 $7$ 的数字组成的模式串，其三个数字从左往右依次代表所有者（owner），所属组（group）和其他人（others）的权限。对于每个数字，其最低三个二进制位从高向低分别表示了该类用户是否具有读（r），写（w）和执行（x）权限。

例如：执行 $\text{chmod 760 file.txt}$ 后, 表示文件的**权限字符串**为 $\text{rwxrw-}\text{-}\text{-}\text{-}$。

给出若干合法的模式串，每次读入一条模式串后，你需要输出修改后文件的**权限字符串**。

inputFormat:
第一行一个正整数 $T$ ($1 \le T \le 100$)，表示数据组数。

接下来 $T$ 行，每行一条 $\text{chmod}$ 模式串。

outputFormat: 共 $T$ 行，表示模式串对应的**权限字符串**。


title: [SNCPC2024] 表达式矩阵

description:
一个 $n \times m$ 的字符矩阵 $a_{ij}$，被称为合法的表达式矩阵，当且仅当其满足如下条件：

- 矩阵只包含 '1'，'+'，'*' 字符。

- 对于矩阵的每行从左向右组成的字符串，均为合法的表达式。

- 对于矩阵的每列从上向下组成的字符串，均为合法的表达式。

一个合法的表达式矩阵的权值定义为，每行从左向右组成的字符串和每列从上向下组成的字符串共 $n + m$ 个表达式求值后的值求和的结果。

求所有 $n \times m$ 的合法表达式矩阵中，权值最小的那一个。如果有多个最小的答案，你可以给出任意一个。

我们定义字符串 $s$ 是合法表达式如下：

- 如果 $s = \overbrace{111\dots111}^{\text{至少一个 }1}$，则 $s$ 是合法表达式。

- 如果 $s$ 和 $t$ 均为合法表达式，则 $s$ * $t$ 也是合法表达式。

- 如果 $s$ 和 $t$ 均为合法表达式，则 $s$ + $t$ 也是合法表达式。

inputFormat: 输入仅一行两个整数 $n, m$ ($3 \leq n, m \leq 9$)，由空格隔开，为矩阵的行数和列数。

outputFormat:
输出共 $n$ 行，每行 $m$ 个字符，其中第 $i$ 行的第 $j$ 个字符为 $a_{ij}$，为权值最小的矩阵。

如果有多个最小的答案，你可以给出任意一个。

hint: 对于样例，此时矩阵的权值为 $4488$，可以证明不存在权值更小的矩阵。


title: [SNCPC2024] 换座位

description:
树王国在筹备着举办一次盛大的庆典！

Shirost 作为树王国的庆典设计师，准备邀请 $n$ 个嘉宾来参加本次庆典。庆典上一共准备了 $2n$ 个座位，**一个座位最多只能坐一个人且一个人恰好坐一个座位**。Shirost 初步计划将第 $i$ 个嘉宾安排在第 $i$ 个座位上。但是总统调查了这 $n$ 个嘉宾的意愿，第 $i$ 个嘉宾的心仪座位为第 $a_i$ 个座位。但除非能坐到心仪座位上，否则他们只愿意坐在原来的座位上。总统希望 Shirost 能够修改计划，使得尽可能多的嘉宾坐在他们的心仪座位上。

形式化的讲，你需要找到长为 $n$ 的数组 $b_i$ ($1 \leq i \leq n, 1 \leq b_i \leq 2n$) 满足 $\forall i \neq j,b_i \neq b_j$ 且 $\forall i, b_i=i$ 或 $b_i=a_i$。且最大化 $b_i = a_i$ 的个数。

你只需要输出最多的个数即可。

inputFormat:
输入第一行为一个整数 $n$ ($1 \leq n \leq 10^{5}$)，表示总人数。

第二行 $n$ 个整数 $a_i$ ($1 \leq a_i \leq 2n$)，由空格隔开，表示每个人的心仪座位。

outputFormat: 输出仅一行一个整数，表示最多有多少嘉宾坐在他们的心仪座位上。

hint: 所有人都可以换到自己的心仪座位。


title: [SNCPC2024] 双子序列

description:
小 L 看到不喜欢的字符串就很难受！看到它作为子序列出现也是！

给定一个长字符串 $S$ 表示小 L 要阅读的文本，以及恰好两个短字符串 $s_1$，$s_2$ 表示小 L 不想看到的字符串，三个字符串均由小写字母组成。

小 L 很反感这两个字符串作为子序列在文本内同时出现，他认为，一个字符串 $T$ 的反感度为：$s_1$ 作为 $T$ 的子序列的出现次数，和 $s_2$ 作为 $T$ 的子序列的出现次数之积。

由于他要读 $S$ 的每个子串，所以现在需要你求出 $S$ 的所有子串的反感度值之和。由于答案可能过大，你只需要输出对 $998244353$ 取模的结果。

定义一个字符串 $H$ 是 $T$ 的子串，当且仅当 $H$ 由 $T$ 删除最前面的若干字符和最后面的若干字符获得（前缀后缀可以一个字符都不删除，也可以把整个串全删除得到空串）。

定义一个字符串 $H$ 是 $T$ 的子序列，当且仅当 $H$ 由 $T$ 删除若干字符后获得（可以一个字符都不删除，也可以全删除后得到空子序列）。

inputFormat:
输入包括三行，每行一个仅由小写字母组成的字符串。

第一行的字符串代表 $S$，第二行代表 $s_1$，第三行代表 $s_2$。其中 $1\le |S|\le 1\times 10^5$，$1\le |s_1|,|s_2|\le 20$。

outputFormat: 输出一个整数代表求得的答案。


title: [SNCPC2024] 商路

description:
一个圆周被 $K$ 个点等分，这些点按照顺时针编号为 $1, 2, \cdots, K$。其中点 $a_1, a_2, \cdots, a_n$ 分别建造有一座市场 $M_1, M_2, \cdots, M_n$。

一条从市场 $i$ 出发，目标是市场 $j$ 的商路是有向线段 $M_i M_j$ ($i \neq j$) 且必须满足以下条件：

- 市场 $j$ 必须是距离市场 $i$ 最远的市场（如果有多个距离相同的最远的市场,那么任意一个均可）。

- 商路线段 $M_i M_j$ 不能与其他商路线段在起点或者终点以外的地方相交或重合。

最多可以存在多少条商路？

inputFormat:
第一行包含两个整数 $K, n$ ($3 \leq K \leq 10^9, 3\leq n \leq \min(K,10^5) $)，由空格隔开，表示有 $n$ 个市场分布在圆周的 $K$ 等分点上。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1\leq a_1 < a_2 < \cdots < a_{n-1} < a_n \leq K$)，为建有市场的点的编号。

outputFormat: 输出一个整数表示最多可以存在的商路的数量。

hint:
对于第一个样例，其中两种可能的答案如下图所示：

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

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


title: [SNCPC2024] 写都写了，交一发吧

description:
MCPlayer542 正在做一道题。

由于题目太难，他不能直接写出正解，而是写出了 $n$ 份不同的代码，其中第 $i$ 份代码可以获得 $g_i$ 的分数。

时间紧迫，MCPlayer542 打算直接胡乱把代码交上去了。然而这时候他发现：由于这场比赛的特殊规则，他必须提交两次代码，且他得到的总分将会是两次提交得分的按位与运算结果。和你正在参加的比赛类似，两次不同提交的代码可以是同一份，也可以不同。

形式化地，如果他分别在两次提交中提交了第 $i$ 和第 $j$ 份代码，则得分为 $g_i \& g_j$，其中 $\&$ 表示按位与运算。

他想知道他能得到的最高分是多少。

inputFormat:
输入包含多组测试数据，数据的第一行包含一个整数 $t$ ($1\le t\le 2\times 10^5$)，表示数据组数。

每组数据的第一行包含一个整数 $n$ ($1\le n \le 2\times 10^5$)，表示代码份数。

随后一行输入 $n$ 个整数 $g_1,\ g_2,\ \ldots,\ g_n$ ($0 \le g_i<2^{30}$)，用单个空格分隔，含义见题目描述。

数据保证所有 $n$ 之和不超过 $2\times 10^5$。

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

hint:
对于第一组数据，只需将第三份代码提交两次即可。

对于第二组数据，提交前两份代码即可。


title: [SNCPC2024] 消失的数字

description:
uuku 正在学习数位 DP！

但某一天，他发现 $1,2,\ldots,9$ 这九个数字中的 $x$ 消失了，也就是说所有包含 $x$ 这个数字的数都消失了。

这让他非常惊慌，因为这对统计数的个数有很大的影响。

现在，他希望你能帮助他求出这种情况下数 $n$ 在未消失的自然数中从小到大排在第几位。

inputFormat:
本题有多组测试数据，输入第一行为一个整数 $T$（$1 \leq T \leq 10^5$），表示测试数据的组数。

对于每组测试数据：

共一行两个整数 $n, x$ ($0 \leq n \leq 10^{18},1 \leq x \leq 9$)，由空格隔开，含义如题目描述所述。

数据保证 $n$ 中不包含数字 $x$。

outputFormat: 对于每组测试数据：输出一行一个整数，表示数 $n$ 的排名。


title: [SNCPC2024] 最大流

description:
给定一个 $n$ 个点 $m$ 条边的有向无环图，图中每条边的容量为 $1$。对点 $1$ 以外的每个点 $i$，设从点 $1$ 到点 $i$ 的最大流为 $f_i$，试求出 $\min\{f_i,\ k\}$。

在边容量为 $1$ 的图上，一个从点 $1$ 到点 $i$ 的流即为一条从点 $1$ 到点 $i$ 的路径。如果从点 $1$ 到点 $i$ 最多能同时有 $f_i$ 个不交的流（即没有一条边同时属于两个流），则我们认为点 $1$ 到点 $i$ 的最大流是 $f_i$。

inputFormat:
输入第一行为三个整数 $n, m, k$ ($2 \leq n \leq 10^5, 1 \leq m \leq 2 \times 10^5, 1 \leq k \leq 50$)，由空格隔开，为图的点数，边数和参数。

接下来 $m$ 行，每行两个整数 $x_i,y_i$ ($1 \leq x_i, y_i \leq n, x_i \neq y_i$)，由空格隔开，描述一条有向边。

图中保证没有自环，但是可能存在重边，保证给出的是一个有向无环图。

outputFormat: 输出仅一行 $n-1$ 个整数，由空格隔开。对于第 $i$ 个整数，如果从结点 $1$ 到结点 $i+1$ 的最大流不超过 $k$，则为最大流的值，否则为 $k$。

hint:
第一个样例所述图如下：

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

我们可以找到 $4$ 条从点 $1$ 到点 $7$ 的不相交路径：

$\text{1->7}$

$\text{1->5->7}$

$\text{1->3->6->7}$

$\text{1->2->4->7}$

我们无法找到更多条从点 $1$ 到点 $7$ 的不相交路径：

所以点 $1$ 到点 $7$ 的最大流为 $f_7=4$，但是因为 $k=3$，所以答案的第六个整数为 $3$。


title: [SNCPC2024] 猜质数 I

description:
**这是一道交互题。**

MCPlayer542 手上有一个神秘的**奇质数** $p$，但他并不想让你知道这个数是多少。

他打算用一个函数 $f(x)$ 来加密他的数，其值为 $x$ 在十进制下的各位数字之和，例如 $f(5)=5$，$f(542)=5+4+2=11$，$f(1024)=1+0+2+4=7$。

**然而考虑到你太聪明，他想了想，决定把加密函数改成：**
$$g(x)=f(f(f(f(f(f(f(f(f(f(x))))))))))$$
**即连续应用 $10$ 次 $f(x)$，并把手上的 $p$ 换成了 $q=p^k$。**

现在他准备给你 $n$ 个整数 $g(q^{a_1}),\ g(q^{a_2}),\ \ldots,\ g(q^{a_n})$，并希望你能告诉他
$$q^{a_1}\bmod (m\cdot a_1),\ q^{a_2}\bmod (m\cdot a_2),\ \ldots,\ q^{a_n}\bmod (m\cdot a_n)$$
分别是多少。**他觉得你肯定猜不到，所以决定让你自己选择 $m$ 和 $a_1,\ a_2,\ \ldots,\ a_n$**。你能完成这个任务吗？

**注意：$m$ 的范围有特殊限制。**

inputFormat:
输入包含多组测试数据。数据的第一行包含一个整数 $t$ ($1\le t\le 500$)，表示数据组数。每组数据的交互流程在下文中描述。

在每组数据中，输入的第一行包含两个整数 $n$ 和 $k$ ($1\le n\le 50, \ 1\le k\le 10^9$)，用单个空格分隔，含义见题目描述。

接下来每次交互，输出一行一个整数 $a_i$ ($1\le a_i\le 10^{18},a_i$ **互不相同**)，表示要询问的 $q$ 的幂次。

给出一个询问后，你应该读入一个整数，即 $g(q^{a_i})$。

你需要在进行完 $n$ 轮交互之后输出一行一个整数 $m$ ($m\ge 35,1\le m\cdot a_i\le 10^{18}$)，再输出一行 $n$ 个数，即 $q^{a_1}\bmod (m\cdot a_1), \ q^{a_2}\bmod (m\cdot a_2), \ \ldots, \ q^{a_n}\bmod (m\cdot a_n)$，用单个空格分隔，表示答案。

**你必须进行恰好 $n$ 轮交互，随后输出答案并结束程序，否则你可能得到无法预测的结果。**

注意在你的程序每轮输出结束时（即，每一次交互输出 $a_i$ 时和最后输出 $m$ 与答案时）需要输出回车并刷新输出缓冲区，否则你将会得到 $\text{Idleness Limit Exceeded}$。

- C 的 $\text{fflush(stdout)}$；
- C++ 的 $\text{cout.flush()}$；
- Java 的 $\text{System.out.flush()}$；
- Python 的 $\text{stdout.flush()}$；

来刷新输出缓冲区。

**保证在每组数据中的奇质数** $p$ ($2<p\le 10^{18}$) **都是在交互前确定的，即不会随着你的输入而变化。**

如果你最后输出的答案正确，你会得到 $\text{Accepted}$；

如果你输出的 $m$ 或 $a_i$ 不符合题目范围要求，或最后输出的答案不正确，你会得到 $\text{Wrong Answer}$。

此外，其他的评测结果仍会在评测过程中根据通常情况返回。


title: [SNCPC2024] 猜质数 II

description:
为了悄悄准备一个神秘的质数，MCPlayer542 伤透了脑筋。

随后他发明了一种~~聪明~~愚蠢的办法，并起名为“质数分”。

他准备了 $n$ 个不同的数 $a_1,\ a_2,\ \ldots,\ a_n$ 作为测试点，并定义“质数分” $score(x,l,r)$ 如下：

$$score(x,l,r)=\sum_{i=l}^r{f(x,a_i)}$$
其中
$$f(x,y)=\left\{\begin{array}{rcl}u-y, & x=1 \\ u, & 1<x\le y,\ \gcd(x,y)=1 \\ -x\cdot y, & x\neq 1,\ \gcd(x,y)=x \\ 0, & \text{otherwise} \end{array}\right.$$

可见质数的“质数分”通常会比较高~~但还是没什么卵用~~。

于是 MCPlayer542 急了，现在他只想暴力乱测，并得到一个得分和 $\sum_{i=1}^{10^6}{score(i,l,r)}$。他打算测试 $q$ 次，每次测试给定 $u$ 和 $l$，其中 $u$ 为函数 $f(x,y)$ 的参数。

对于每次询问，他想知道所能得到的最大得分和以及能得到这个最大得分和的最小 $r$ 是多少。

inputFormat:
输入数据的第一行包含两个整数 $n,\ q$ ($1\le n,\ q\le 5\times 10^5$)，用单个空格分隔。

第二行包含 $n$ 个整数 $a_1,\ a_2,\ \ldots,\ a_n$ ($1\le a_i\le 10^6$)，用单个空格分隔，表示测试点的数据。

接下来 $q$ 行，每行两个整数 $u_i,\ l_i$ ($1\le u_i \le 1.8\times 10^7,\ 1\le l_i\le n$)，用单个空格分隔，表示一次询问。

outputFormat: 对每个询问输出一行两个数，即对应询问的最大得分和以及能获得该得分的最小 $r_i$ ($l_i\le r_i\le n$)，用单个空格分隔。


title: [SNCPC2024] 致命公司

description:
Shirost 最近沉迷于一款名为《致命公司》的游戏。

在游戏中，玩家将作为“公司”的合同工，从废弃的工业星球收集废料。在探索的过程中，Shirost 将遇到一个名为弹簧头的怪物，弹簧头会在无人注视它时快速移动，但在被注视时则会保持不动。一旦接近，弹簧头就会立刻杀死 Shirost。

现在 Shirost 站在 $n$ 个无限长的通道的交汇点，他知道有 $m$ 个弹簧头，分别会在 $t_i$ 时刻出现在 $x_i$ 号通道距离他 $y_i$ 米远处。

对于每个时刻 $j$，以下三个事件将会依次发生：

1. 在该时刻开始时，满足 $t_i = j$ 的弹簧头会出现在  $x_i$ 号通道距离 Shirost $y_i$ 米远处。

2. Shirost 选择凝视任意一个通道。

3. 该通道内的所有弹簧头无法移动，而其他通道中**已经出现**的弹簧头会向他移动 $k$ 米，如果某个弹簧头到达他所在位置，则他将在时刻 $j$ 死亡。

Shirost 想知道他最晚可以活到哪个时刻。换句话说，如果 Shirost 最晚在时刻 $j$ 死亡，那么你需要输出 $j-1$。如果他不会死亡，则输出 $-1$。

inputFormat:
输入第一行为三个整数 $n,m,k$ ($1 \leq n \leq 5 \times 10^5, 1 \leq m \leq 5 \times 10^5, 1 \leq k \leq 10^{18}$)，由空格隔开，为无限长通道的个数，弹簧头的个数，弹簧头每时刻移动的距离。

接下来 $m$ 行，每行三个整数 $t_i,x_i,y_i$ ($1 \leq t_i \leq 10^{18}, 1 \leq x_i \leq n, 1 \leq y_i \leq 10^{18}$)，由空格隔开，描述弹簧头出现的时刻，出现的通道编号，距离 Shirost 有多远。

outputFormat: 输出仅一行一个整数，表示 Shirost 最晚可以活到哪个时刻。如果他不会死亡，则输出 $-1$。


title: [SNCPC2024] 下棋

description:
LNC 喜欢所有 $k$ 进制下所有数位的乘积为自身因子的数。他称之为 LNC 数。例如：

当 $k = 10$ 时，$y = (36)_{10}$ 是 LNC 数，因为 $(3 \times 6) \mid 36$。

当 $k = 4$ 时，$y = (12)_4$ 是 LNC 数，因为转换成十进制后 $(12)_4 = (6)_{10}$，而 $(1 \times 2) \mid 6$。

当 $k = 2$ 时，$y = (1101)_2$ 不是 LNC 数，因为转换成十进制后 $(1101)_2 = (13)_{10}$，而 $0$ 不是 $13$ 的因子。

LNC 在和 LJJ 玩一个游戏，LJJ 给出 $x$ 枚棋子，然后 LNC 选定一个整数 $k$ ($k \geq 2$)。随后他们交替取走若干枚棋子，要求取走的棋子数量是 $k$ 进制意义下的 LNC 数。LNC 先手，先取完的获胜。两个人都绝顶聪明，故都会选择最优的策略。

LJJ 觉得这个游戏很不公平，他们一共玩了 $T$ 局游戏，对于每局游戏他给出的 $x$，他希望知道最小的 $k$ 使得 LNC 先手必胜。

inputFormat:
输入第一行一个正整数 $T$ ($1 \le T \le 1 \times 10^2$)，表示数据组数。

接下来 $T$ 行每行一个正整数 $x$ ($3 \le x \le 10^{18}$)，表示 LJJ 给出的数 $x$。

outputFormat: 输出 $T$ 行每行一个正整数 $k$，表示每个询问的最小的 $k$，使 LNC 先手必胜。

hint:
当 $x=5$ 的时候，LNC 可以选择 $k=2$。$x=(5)_{10}=(101)_2$。

LNC 先手拿掉 $(11)_2$，此时 $x=(10)_2$，LJJ 只能拿走 $(1)_2$，LNC 拿走最后的 $(1)_2$ 获胜。

又因为 $k=2$ 已经不能再小了，所以最终答案为 $k=2$。


title: [SNCPC2024] 窗花

description:
有一扇 $100 \text{cm} \times 100 \text{cm}$ 的窗户和 $n$ 个对角线长为 $2 \text{cm}$ 的正方形窗花。建立坐标系，以窗户左下角的坐标为原点 $(0,0)$，右上角坐标为 $(100,100)$，第 $i$ 个窗花中心被贴在非边缘的整坐标点 $(x_i,y_i)$ ($1 \leq x_i,y_i \leq 99$) 上，窗花的对角线与坐标轴平行。

问窗户有多大的面积被至少一片窗花覆盖。

inputFormat:
第一行一个整数 $n$ ($1 \leq n \leq 10000$)。

接下来 $n$ 行，每行两个整数 $x_i,y_i$ ($1 \leq x_i,y_i \leq 99$)，含义如上所述。

outputFormat:
输出仅一行一个实数，为被至少一片窗花覆盖的面积。

你的答案被认为正确当且仅当其相对误差或绝对误差不超过 $10^{−4}$。形式化地说，假设你的答案是 $a$，标准答案是 $b$。你的答案被认为正确当且仅当 $\frac{|a−b|}{\max (1,|b|)} \leq 10^{−4}$。


title: 「ROI 2017 Day 2」存储器

description:
给定一个字符串 $S$，设其长度为 $n$，每个字符要么是 `+` 要么是 `-`。

定义一个**片段**为 $S$ 的一个子串 $S[l,r]$ 满足下面三个条件：

- $l=1$ 或者 $S_{l-1} \ne S_l$。
- $r=n$ 或者 $S_{r+1} \ne S_r$。
- $S_l=S_{l+1}=\dots=S_{r-1}=S_r$。

定义一次**变换**为：

- 选择 $S$ 的两个**相邻**且**长度不同**的片段，改变长度较小的那个片段的所有字符为其相反字符。（`+` 变为 `-`，`-` 变为 `+`）

现在有 $q$ 次询问，每次询问给出只包含 `+` 和 `-` 并且长度相同的字符串 $S_i,T_i$，请你判断 $S_i$ 是否能够通过若干次变换得到 $T_i$。

inputFormat:
第一行一个整数 $q$ 表示询问次数。

接下来 $q$ 行每行两个字符串 $S_i,T_i$，含义如题所示。

outputFormat: 对于每次询问输出一行一个字符串 `Yes` 或 `No` 表示是否可以完成题目所给要求。


title: 「ROI 2017 Day 1」排序幻觉

description:
给定长度为 $n$ 的整数数列 $a$，如果一个整数 $b$ 满足：

$$
(a_1 \operatorname{xor} b) \le (a_2 \operatorname{xor} b) \le \dots \le (a_n \operatorname{xor} b)
$$

则称 $b$ 是 $a$ 数列的**幻数**。

接下来有 $q$ 次修改，每次修改一个数 $a_{u_i}$ 为整数 $k_i$，每次修改都会对后面的询问产生影响。你需要求出第一次修改前以及每次修改后这个数列的最小的幻数是多少，特别的，如果不存在幻数请输出 $-1$。

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

第二行 $n$ 个整数表示整数数列 $a$。

第三行一个整数 $q$ 表示询问次数。

接下来 $q$ 行每行两个整数 $u_i,k_i$，表示将 $a_{u_i}$ 修改为 $k_i$。

outputFormat: 共 $(q+1)$ 行，每行一个整数表示当前数列最小的幻数，如果没有幻数请输出 $-1$。


title: 「ROI 2017 Day 1」前往大都会

description:
ROI 国有 $n$ 个城市，以及 $m$ 条铁路，每条铁路都是**单向**运行的，第 $i$ 条铁路依次经过 $v_{i,1},v_{i,2},\dots,v_{i,l_i+1}$ 号城市并停靠，其中 $v_{i,j} \to v_{i,j+1}$ 的铁路长度是 $t_{i,j}$。

如果多条铁路经过 $u$ 号城市，那么你可以在 $u$ 号城市换乘其他铁路。（每条铁路都可以在停靠点任意上车/下车）

你需要找到一条从 $1$ 号城市到 $n$ 号城市的路径，这条路径需要满足其总长度最小，并且在此条件上路径上相邻两个**换乘点**间**火车上**距离的平方和最大。

注：起点和终点都是换乘点，题目保证有解。

inputFormat:
第一行两个整数 $n,m$ 表示有 $n$ 个城市，$m$ 条铁路。

接下来 $m$ 行，每行先是一个整数 $l_i$ 表示铁路长度，接下来 $2l_i+1$ 个整数形如 $v_{i,1},t_{i,1},v_{i,2},\dots,v_{i,l_i},t_{i,l_i},v_{i,l_i+1}$，含义如题所示。

outputFormat: 一行两个整数，第一个数表示最短路径长度，第二个数表示平方和最大值。


title: 「ROI 2017 Day 2」水星上的服务器

description:
水星上有 $n$ 个服务器，有 $n-1$ 根数据线，第 $i$ 根双向连接 $i$ 号服务器和 $i+1$ 号服务器。

假设 $j$ 号服务器收到了地球发来的信息。你需要尽快将信息传输到其他服务器。

一台服务器 $i$ 收到地球发来的信息后可以直接存储一份到它的数据库中，然后在缓冲区滞留 $t_i$ 秒后删除。

由于一些外界因素，第 $i$ 根数据线只能在 $[l_i,r_i]$ 时间段内传输信息。当某根数据线接通后，若这根数据线两边的服务器有一台的缓冲区还存有信息，那么另一台也可以得到这个信息。（每个服务器会在其接收到信息后能传递的**第一时间**把信息传递出去）

你可以任意选择地球发给服务器 $j$ 信息的时刻，要求最后所有服务器都收到这个信息，问最早可以在多久发送信息，如果不存在可行解，请输出 $-1$。

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

第二行 $n$ 个整数 $t_1,t_2,\dots,t_n$。

在接下来的 $n-1$ 行中，每行两个整数 $l_i,r_i$。

outputFormat: 输入 $n$ 行，每行一个整数，第 $i$ 行的数表示当 $j=i$ 时的答案，如果不可能输出 $-1$。


title: 「ROI 2017 Day 2」反物质

description:
你研发出了 $n$ 种获得反物质的实验，你无法控制生成的数量，但是可以保证第 $i$ 种获得的反物质在区间 $[l_i,r_i]$ 内，并且成本为 $c_i$，每种实验可以使用多次。

生成的反物质均会放在一个容器中，每次实验结束后，你可以得知容器中反物质的质量。容器中的反物质不能超过 $a$ 克（超过了就会爆炸）。

如果第 $i$ **次**实验一共获得了 $t_i$ 单位的反物质，你可以将其卖给军方获得 $(10^9t_i-c)$ 卢布的利润，其中 $c$ 是该实验的成本。

在保证安全的前提下，你想要知道你最坏情况下利润至少是多少。

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

接下来的 $n$ 行中，每行三个整数 $l_i,r_i,c_i$。

outputFormat: 输出一行，一个整数，表示你最多可以保证获得多少利润。

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

对于样例组 #1：

我们只能使用实验 $1$，如果实验一次，得到的反物质区间在 $[4,6]$ 内；实验两次，区间在 $[8,12]$，如果此时得到了 $12$ 单位的反物质就不能继续做实验了，因为如果下一次得到 $6$ 单位的话，容器就会爆炸；其他情况我们可以继续做第三次实验，可能的区间是 $[12,17]$。

这个时候无论如何都不能继续做实验了，原因同上，所以最坏情况下我们只能得到 $12$ 单位的反物质并且需要做三次实验，此时收益为 $3 \times (10^9 \times 4-10)=11999999970$。

#### 【数据范围】

本题仅放了部分数据，如需评测完整数据请左转 [LOJ P2772](https://loj.ac/p/2772)。

对于所有数据，$1 \le c_i \le 100$，$1 \le l_i \le r_i \le a$。

| 子任务编号 | 分值 | $1 \le n \le$ | $1 \le a \le$ | 特殊限制 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $10$ | $1$ | $10^3$ | 无 |
| $2$ | $10$ | $10$ | $10^3$ | $l_i=r_i$ |
| $3$ | $20$ | $10$ | $10^3$ | 无 |
| $4$ | $20$ | $100$ | $5 \times 10^4$ | 无 |
| $5$ | $40$ | $100$ | $2 \times 10^6$ | 无 |

注：原题有 $15$ 个子任务，方便起见，最后若干组除 $a$ 数据范围外相同的子任务合并为 $1$ 组子任务。


title: 「ROI 2017 Day 2」学习轨迹

description:
THU 和 PKU 同时开设了一批课程，THU 有 $n$ 节课，PKU 有 $m$ 节课。

其中 THU 第 $i$ 节课类别是 $a_i$，乐趣度是 $x_i$；PKU 第 $i$ 节课类别是 $b_i$，乐趣度是 $y_i$。保证 $a$ 中元素互不相同，$b$ 中元素互不相同，但是 $a$ 和 $b$ 之间可能有相同元素。

你可以选择听 THU 的 $l_1 \sim r_1$ 节课，收获到的乐趣度为所有你听的课的乐趣度的和；同时可以在 PKU 听 $l_2 \sim r_2$ 节课，收获到的乐趣度也是所有你听的课的乐趣度的和。（当然你也可以选择只听一所大学的课甚至不听）

同一类别的课你不能听两次，也就是如果 $a_{l_1 \sim r_1}$ 中有元素与 $b_{l_2 \sim r_2}$ 相同，那么这个听课方案就不能满足你的胃口。

你需要求出可能的听课方案中乐趣度最大的是多少以及具体的安排。

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

接下来四行，每行一个整数序列，分别表示题目中的 $a,x,b,y$，这四个序列长度分别为 $n,n,m,m$。

outputFormat:
第一行一个整数表示最大乐趣度。

第二行两个整数 $l_1,r_1$，如果你不打算在 THU 听课，输出 `0 0`。

第三行两个整数 $l_2,r_2$，如果你不打算在 PKU 听课，输出 `0 0`。


title: 「ROI 2017 Day 1」四轴飞行器编程

background:
### 题面

系统中隐藏了一个只含 `(` 和 `)` 的**合法括号字符串** $S$。

你每次可以向系统询问一个 $S$ 的子区间 $S[l,r]$，系统会返回这个子区间是否是一个合法括号字符串。

请编写一个程序，与系统进行交互，并最终输出 $S$ 的具体信息。

关于合法括号字符串的定义：

- 空串是合法括号字符串。

- 设 $\text{A}$ 是合法括号字符串，那么 $\text{(A)}$ 也是合法括号字符串。

- 设 $\text{A}$ 和 $\text{B}$ 是合法括号字符串，那么 $\text{AB}$ 也是合法括号字符串。

### 交互过程

~~你可以编写一个函数 `getProgram()` 并在程序开始包含 `grader.h` 来完成交互过程。该函数无返回值，也没有参数。~~
请直接编写一个完整程序来完成交互。

你需要先从标准输出流中获得一个整数 $n$，表示系统字符串的长度。

你可以向标准输出中输出询问和回答，形式如下：

- 对于询问一段子串是否合法，你需要先输出一个字符 `?`，后跟两个整数 $l,r$，表示选择 $S[l,r]$，字符，整数之间用一个空格隔开。如果 $S[l,r]$ 为合法括号字符串，交互库会向标准输出中输出 $\texttt{Yes}$，否则会输出 $\texttt{No}$；

- 对于回答整个程序，你需要先输出一个字符 `!`，后跟一个长度为 $n$ 的合法括号字符串。`!` 与序列之间用一个空格隔开。

在回答之后，你应该结束程序。保证四轴飞行器程序在交互过程中不会改变。

交互过程中，你的询问数不能超过一个值 $k$。


title: BZOJ4998 星球联盟

description:
在遥远的 S 星系中一共有 $n$ 个星球，编号为 $1\sim n$。其中的一些星球决定组成联盟，以方便相互间的交流。但是，组成联盟的首要条件就是交通条件。

初始时，在这 $n$ 个星球间有 $m$ 条太空隧道。每条太空隧道连接两个星球，使得它们能够相互到达。若两个星球属于同一个联盟，则必须存在一条环形线路经过这两个星球，即两个星球间存在两条没有公共隧道的路径。为了壮大联盟的队伍，这些星球将建设 $p$ 条新的太空隧道。这 $p$ 条新隧道将按顺序依次建成。一条新轨道建成后，可能会使一些星球属于同一个联盟。

你的任务是计算出，在一条新隧道建设完毕后，判断这条新轨道连接的两个星球是否属于同一个联盟，如果属于同一个联盟就计算出这个联盟中有多少个星球。

inputFormat:
第一行三个整数 $n,m,q$，分别表示总星球数，初始时太空隧道的数目和即将建设的轨道数目。

第 $2\sim m+1$ 行，每行两个整数，表示初始时的每条太空隧道连接的两个星球编号。

第 $m+2$ 行到第 $m+p+1$ 行，每行两个整数，表示新建的太空隧道连接的两个星球编号。

这些太空隧道按照输入的顺序依次建成。

outputFormat:
输出共 $p$ 行：

- 如果这条新的太空隧道连接的两个星球属于同一个联盟，就输出一个整数，表示这两个星球所在联盟的星球数。
- 如果这条新的太空隧道连接的两个星球不属于同一个联盟，就输出 No。

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

数据保证，$1\leq n,m,p \leq 2\times 10^5$。


title: BZOJ2959 长跑

background: 某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”，同学们纷纷离开寝室，离开教室，离开实验室，到操场参加 $3000$ 米长跑运动。一时间操场上熙熙攘攘，摩肩接踵，盛况空前。

description:
为了让同学们更好地监督自己，学校推行了刷卡机制。学校中有 $n$ 个地点，用 $1\sim n$ 的整数表示，每个地点设有若干个刷卡机。

有以下三类事件：
1. 修建了一条连接 $A$ 地点和 $B$ 地点的跑道；
2. $A$ 地点的刷卡机台数变为了 $B$；
3. 进行了一次长跑。问一个同学从 $A$ 地点出发，最后到达 $B$ 地点最多可以刷卡多少次。具体的要求如下：
   - 当同学到达一个地点时，他可以在这里的每一台刷卡机上都刷卡。但每台刷卡机只能刷卡一次，即使多次到达同一地点也不能多次刷卡。为了安全起见，每条跑道都需要设定一个方向，这条跑道只能按照这个方向单向通行。最多的刷卡次数即为在任意设定跑道方向，按照任意路径从 $A$ 地点到 $B$ 地点能刷卡的最多次数。

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

第二行输入 $n$ 个正整数，第 $i$ 个正整数为第 $i$ 个地点的刷卡机个数。

接下来 $m$ 行，每行包含三个非负整数 $P,A,B$ 代表一个事件，$P$ 为事件类型，$A,B$ 为事件的两个参数。

outputFormat: 对于每个 $P=3$ 的事件输出一行，包含一个整数，为按照任意路径从 $A$ 地点到 $B$ 地点能刷卡的最多次数。如果不能到达，输出 $-1$。

hint:
对于所有数据，$1\leq m\leq 5n$，$1\leq n\leq 1.5\times 10^5$。

保证最初所有地点之间都没有跑道。

每行相邻的两个数之间均用一个空格隔开。

表示地点编号的数均在 $1$ 到 $n$ 之间，每个地点的刷卡机台数始终不超过 $10^4$，$P \in \{1,2,3\}$。


title: BZOJ3159 决战

description:
Katharon 国有 $n$ 个城市，编号为 $1\sim n$。出于勤俭节约，不铺张浪费的考虑，城市间只连有 $n-1$ 条道路，使得可以从一个城市出发沿着道路走到另一座城市。

现在 X 国的飞船降落在了某个城市，并把它改造成了自己的据点。X 国占领其他国家的一贯做法是，在据点里造一堆工厂生产战斗机器人，然后沿着被侵略国的道路运送到其他城市。X 国的司令向来不走回头路，而且崇尚团结与绝对的公平，因此运送战斗机器人时，会先选择一个终点，再在从据点到终点的路径上选择一个起点，然后把机器人均匀分配到起点到终点路径上的每个城市。同时，为了重新分配机器人，X 国的司令还会下令，按照与运送机器人相同的方法选择起点和终点，然后翻转这条路径上城市的机器人的数量。比如，选定的路径上的城市的机器人数依次为 $1,2,3,4,5$，翻转之后就变成了 $5,4,3,2,1$。

Kanari 国王手中的圆盘上浮现出了 Katharon 国的地图。不仅如此,上面还标出了 X 国据点在 $r$ 号城市，并显示出了 X 国司令刚刚下达的指令。“太好了！”国王欢呼，“我们能第一时间掌握敌人的布局，就一定能击退 X 国的侵略者！”

但是还有一个问题没有解决。圆盘上只显示了指令，却没有标出每个城市的机器人数量，这让国王很是头疼。于是他找到了你，想让你帮忙设计一个程序来回答国王的询问。国王只关心某两个点之间路径上的城市的机器人和、最大值以及最小值，以便确定兵力部署、攻击要点和敌方的薄弱点。

X 国司令的指令和 Kanari 国王的询问如下：

1. `Increase x y w` 运送一批机器人到从 $x$ 到 $y$ 的路径上的城市，并分配给每个城市 $w$ 个机器人；
2. `Sum x y` 询问从 $x$ 到 $y$ 的路径上的城市的机器人数量之和。
3. `Major x y` 询问从 $x$ 到 $y$ 的路径上的城市的机器人数量的最大值。
4. `Minor x y` 询问从 $x$ 到 $y$ 的路径上的城市的机器人数量的最小值。
5. `Invert x y` 翻转从 $x$ 到 $y$ 的路径上的城市的机器人数量。

对于 X 国司令的指令，保证给定的 $x,y$ 满足上文所述的要求。对于 Kanari 国王的询问，**不**保证给定的 $x,y$ 满足上述要求。

inputFormat:
第一行有三个整数 $n,m,r$，分别表示树的节点数、指令和询问总数，以及 X 国的据点。

接下来 $n-1$ 行，每行两个整数 $x$ 和 $y$，表示 Katharon 国的一条道路。

接下来 $m$ 行，每行描述一个指令或询问，格式见题目描述。

outputFormat: 对于每个询问操作，输出所求的值。

samples:
5 8 1
1 2
2 3
3 4
4 5
Sum 2 4
Increase 3 5 3
Minor 1 4
Sum 4 5
Invert 1 3
Major 1 2
Increase 1 5 2
Sum 1 5

hint: 数据保证，$1\leq n,m\leq 5\times 10^4$，且对于运送操作 $1\leq w\leq 10^3$。


title: BZOJ2759 一个动态树好题

description:
有 $n$ 个未知数 $x_1,x_2,\dots,x_n$ 和 $n$ 个等式组成的同余方程组：$x_i\equiv k_i\times x_{p_i} + b_i \pmod {10007}$。

你需要进行 $q$ 次操作，每次操作为下列两种情况之一：
- `A a`，询问当前 $x_a$ 的解，无解输出 `-1`，多解输出 `-2` 否则输出 $x_a$。
- `C a x y z`，修改一个等式 $k_a \gets x,p_a \gets y,b_a \gets z$。

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

接下来 $n$ 行，每行三个整数 $k_i,p_i,b_i$。

接下来一行一个整数 $q$。

再接下来 $q$ 行，每行一个操作，见题意所述。

outputFormat: 对每个询问，输出一行一个整数。

hint: 对于所有数据，$k_i,b_i,x_i \in [0,10007) \cap \Z$。$1\leq n\leq 3\times 10^4$，$0\leq q\leq 10^5$，其中询问操作占总操作数的约 $80\%$。

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


title: BZOJ3779 重组病毒

background: 黑客们通过对已有的病毒反编译，将许多不同的病毒重组，并重新编译出了新型的重组病毒。这种病毒的繁殖和变异能力极强。为了阻止这种病毒传播，某安全机构策划了一次实验，来研究这种病毒。

description:
实验在一个封闭的局域网内进行。局域网内有 $n$ 台计算机，编号为 $1\sim n$。一些计算机之间通过网线直接相连，形成树形的结构。局域网中有一台特殊的计算机，称之为核心计算机。根据一些初步的研究，研究员们拟定了一个一共 $m$ 步的实验。实验开始之前，核心计算机的编号为 $1$，每台计算机中都有病毒的一个变种，而且每台计算机中的变种都不相同。实验中的每一步会是下面中的一种操作：

- `RELEASE x`。在编号为 $x$ 的计算机中植入病毒的一个新变种。这个变种在植入之前不存在于局域网中。
- `RECENTER x`。将核心计算机改为编号为 $x$ 的计算机。但是这个操作会导致原来核心计算机中的病毒产生新变种，并感染过来。换言之，假设操作前的核心计算机编号为 $y$，相当于在操作后附加了一次 `RELEASE y` 的操作。

根据研究的结论，在植入一个新变种时，病毒会在局域网中搜索核心计算机的位置，并沿着网络中最短的路径感染过去。

而第一轮实验揭露了一个惊人的真相：病毒的不同变种是互斥的。新变种在感染一台已经被旧变种感染的电脑时，会把旧变种完全销毁之后再感染。但研究员发现了实现过程中的漏洞。如果新变种在感染过程中尚未销毁过这类旧变种，需要先花费 $1$ 单位时间分析旧变种，才能销毁。如果之前销毁过这类旧变种，就可以认为销毁不花费时间。病毒在两台计算机之间的传播亦可认为不花费时间。

研究员对整个感染过程的耗时特别感兴趣，因为这是消灭病毒的最好时机。于是在 $m$ 步步实验之中，研究员有时还会做出如下的询问：

- `REQUEST x`。询问如果在编号为 $x$ 的计算机的关键集合中的计算机中植入一个新变种，平均感染时间为多长。编号为 $y$ 的计算机在编号为 $x$ 的计算机的关键集合中，当且仅当从 $y$ 沿网络中的最短路径感染到核心计算机必须经过 $x$。由于有 `RECENTER` 操作的存在，这个集合并不一定是始终不变的。

至此，安全机构认为已经不需要实际的实验了，于是他们拜托你编写一个程序，模拟实验的结果，并回答所有的询问。

inputFormat:
输入的第一行包含两个整数 $n$ 和 $m$，分别代表局域网中计算机的数量，以及操作和询问的总数。

接下来 $n-1$ 行，每行包含两个整数 $x$ 和 $y$，表示局域网中编号为 $x$ 和 $y$ 的计算机之间有网线直接相连。

接下来 $m$ 行，每行包含一个操作或者询问，格式如问题描述中所述。

outputFormat: 对于每个询问，输出一个实数，代表平均感染时间。输出与答案的绝对误差不超过 $10^{-6}$ 时才会被视为正确。

samples:
8 6
1 2
1 3
2 8
3 4
3 5
3 6
4 7
REQUEST 7
RELEASE 3
REQUEST 3
RECENTER 5
RELEASE 2
REQUEST 1


title: BZOJ4202 石子游戏

description:
石子游戏是大家都很喜欢玩的一类游戏，这类游戏通常与石子的移动和取舍有关，往往可以让人在游戏中获得不少的乐趣。

有一类树上石子游戏的规则是这样的：在一棵有根树上，每个结点都有着一定数目的石子，两个玩家轮流进行游戏。每次，每个玩家可以把不超过 $m$ 个的石子移动到它的父亲上，一次只能移动一个结点上的石子。显然，根结点没有父亲，故每个石子一旦移动到根结点便无法再次移动。问题是以某个结点为根的子树进行这样的游戏，是否存在先手必胜策略。

为了增加这个游戏的难度，我们对这个游戏进行一些小小的修改。现在，我们的这棵树可能会长出新的结点。同时，每个结点上的石子数目可能会变化。请问，以某个节点为根的子树进行这样的石子游戏，是否存在先手必胜策略。本题要求强制在线。

inputFormat:
第一行包含两个整数 $n,m$，表示初始时有 $n$ 个结点，每次移动不能超过 $m$ 个石子。

第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示初始时候的石子数量，其中 $1$ 号结点为根结点。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示有一条从 $u$ 到 $v$ 的边。

接下来一行一个正整数 $t$，表示操作的数目。

接下来 $t$ 行，每行代表一个操作，每行的第一个数字代表操作类型，其中：

- 若为 $1$，后跟一个整数 $v$，表示询问在 $v$ 的子树中做游戏先手是否必胜。
- 若为 $2$，后跟两个整数 $x,y$，表示将结点 $x$ 的石子数修改为 $y$。
- 若为 $3$，后跟三个整数 $u,v,x$，表示为 $u$ 结点添加一个儿子 $v$，其初始石子数为 $x$。

outputFormat:
对于每一个询问，若先手必胜输出 `Yes`，否则输出 `No`。

注：数据进行了强制在线处理，对于每一个操作，除类型名外，都需要异或之前回答为 `Yes` 的数目。

hint: 对于 $100\%$ 的数据，$1\leq n,t\leq 5\times 10^4$，同时，保证任何时刻树中节点数目和编号都不会超过 $10^5$。其余数据的范围皆在 int 范围内。


title: 『DABOI Round 1』Blessings Repeated

background:
@[cyh20100812](https://www.luogu.com.cn/user/1051692) 因其很有实力被尊称为圣母。

> 圣母好闪，拜谢圣母！

description:
圣母是一名辩论家，即 ENTP。

她在进行一次辩论时的观点是字符串 $S$，她为了让对方信服她的观点她会强调 $k$ 次，所以她的辩词即为 $k$ 个字符串 $S$ 依次首尾相接。

你作为反驳的人可能不能听清楚她说的所有话，所以你只能抓取关键词 $T$，你需要求出 $k$ 个首尾相接的 $S$ 中有多少个子序列（不一定连续）为 $T$，答案对 $998244353$ 取模。

---

**【形式化题意】**

给定一个正整数 $k$ 和两个字符串 $S,T$。

设字符串 $s$ 为 $k$ 个字符串 $S$ 首尾相接得到的字符串，$n=\vert s \vert , m=\vert T \vert$。

设答案集合 $P=\{ (i_0,i_1,\dots,i_{m-1})  \mid 0\le i_0 < i_1 < \dots < i_{m-1} < n, \forall~0 \le j < m, s_{i_j}=T_j \}$，请求出 $\vert P \vert \bmod 998244353$。

inputFormat:
输入共 $3$ 行。

第 $1$ 行 $1$ 个整数，表示 $k$。

第 $2$ 行 $1$ 个字符串，表示 $S$。

第 $3$ 行 $1$ 个字符串，表示 $T$。

outputFormat: 输出共 $1$ 行 $1$ 个整数，表示答案。


title: BZOJ4833 最小公倍佩尔数

background: 题目来自 BZOJ 2017 年 4 月月赛。

description:
令 $(1+\sqrt{2})^n=e(n)+\sqrt{2}f(n)$，其中 $e(n),f(n)$ 都是整数，显然有 $(1-\sqrt{2})^n=e(n)-\sqrt{2}f(n)$。令 $g(n)=\operatorname{lcm}(f(1),f(2),\dots,f(n))$。

给定两个正整数 $n,p$，其中 $p$ 是质数，并且保证 $f(1),f(2),\dots,f(n)$ 在模 $p$ 意义下均不为 $0$，请计算 $\sum \limits_{i=1}^n i\times g(i)$ 模 $p$ 的值。

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

接下来是测试数据。每组测试数据只占一行，包含两个正整数 $n$ 和 $p$。

outputFormat: 对于每组测试数据，输出一行一个非负整数，表示这组数据的答案。


title: BZOJ3328 PYXFIB

description:
给定整数 $n,k,p$，要求计算下列式子对 $p$ 取模的值：

$$\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} C_n^{i\times k}\times F_{i\times k}$$

其中：
- $p$ 为质数，且 $p$ 除以 $k$ 的余数为 $1$。
- $C$ 为组合数，即 $C_m^n=\frac{n!}{m!(n-m)!}$。
- $F_n$ 为斐波那契数列，即 $F_0=1$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$。

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

接下来 $T$ 行，每行三个正整数 $n,k,p$。

outputFormat: 输出 $T$ 行，每行一个整数，表示结果。

hint: 对于 $100\%$ 的数据，保证 $1\leq n\leq 10^{18}$，$1\leq k \leq 20000$，$1\leq T\leq 20$，$1\leq p\leq 10^9$，$p$ 为质数，且 $p$ 除以 $k$ 的余数为 $1$。


title: [AMPPZ2013] Bytehattan

description:
比特哈顿镇有 $n\times n$ 个格点，形成了一个网格图。一开始整张图是完整的。

有 $k$ 次操作，每次会删掉图中的一条边 $(u,v)$，你需要回答在删除这条边之后 $u$ 和 $v$ 是否仍然连通。

inputFormat:
第一行包含两个正整数 $n,k(2\leq n\leq 1500,1\leq k\leq 2n(n-1))$，表示网格图的大小以及操作的个数。

接下来 $k$ 行，每行包含两条信息，每条信息包含两个正整数 $a,b(1\leq a,b\leq n)$ 以及一个字符 $c$（$c$ 为 `N` 或者 `E`）。

如果 $c$ 为 `N`，表示删除 $(a,b)$ 到 $(a,b+1)$ 这条边；如果 $c$ 为 `E`，表示删除 $(a,b)$ 到 $(a+1,b)$ 这条边。

数据进行了加密，对于每个操作，如果上一个询问回答为 TAK 或者这是第一个操作，那么只考虑第一条信息，否则只考虑第二条信息。数据保证每条边最多被删除一次。

outputFormat: 输出 $k$ 行，对于每个询问，如果仍然连通，输出 TAK，否则输出 NIE。

hint: 数据保证，$2\leq n\leq 1500$，$1\leq k\leq 2n(n-1)$，$1\leq a,b\leq n$。


title: BZOJ2712 [Violet 2] 棒球

description:
棒球中一项最原始简单的技术参数就是「安打率」。所谓「安打」，就是指打击手把投手投出来的球，击出到界内，使打者本身能至少安全上到一垒的情形。由于只有队员跑回本垒才能得分，安打是得分的最重要的途径。因此，安打率对于打击手来说也是非常重要的数据。顾名思义，安打率为安打数与打数的比值。如果一名打击手在 $5$ 次打击中出现了 $1$ 次安打，那么他的安打率就是 $0.2$。

Uruto 是一位业余棒球爱好者。有一次，他在训练中看到了自己的安打率数据。他发现这个数据是一个被四舍五入到了 $n$ 位小数的一个值。Uruto 想知道，他至少打击了多少次才有可能得到这样的安打率。

inputFormat:
输入文件包含多个测试点。
- 每个测试点占一行，包含一个整数 $n$ 和浮点数 $r$。其中 $r$ 是一个 $n$ 位小数，表示 Uruto 安打率的近似值。

outputFormat: 对于每个测试点，在单独的一行内输出一个整数，表示 Uruto 最小可能的打击次数。

hint:
对于 $20\%$ 的数据，保证答案在 $1000$ 以内；

对于所有数据，保证 $0<n\leq 15$，测试点的数目在 $500$ 以内。

如果一个棒球运动员的安打率在 $30\%$ 以上，那么他就绝对是球队的栋梁了。出于这方面的考虑，保证所有的数据中 $0\leq r<1$。