title: [CTSC2010] 性能优化

description:
程序员小明正在开发一套大型软件，软件中有一段核心程序，用伪代码描述如下（假设所有变量初值均为 $0$，并且假定其中的数据类型均不会出现溢出）：

~~~cpp
Input a[0], a[1], ... , a[n - 1], b[0], b[1], ... , b[n - 1], C
For i: 0 to n - 1
	x[0, i] = a[i]
For i: 0 to C - 1
	For j: 0 to n - 1
		For k: 0 to n - 1
			x[i + 1, (j + k) mod n] = x[i + 1, (j + k) mod n] + b[k]x[i, j]
Output x[C, 0] mod (n + 1), x[C, 1] mod (n + 1), ... , x[C, n - 1] mod (n + 1)
~~~

但是，这段程序的效率非常低，它的时间复杂度高达 $\Theta(n^2C)$。他想让你帮忙优化一下这个程序，当然要求输出相同的结果。为了使问题更简单，他保证输入的 $n$ 能表示成若干个不超过 $10$ 的正整数的乘积，并且 $n + 1$ 是质数。

inputFormat:
规范起见，以下将下标统一写到数组名称的右下角。例如： $a_1$ 对应伪代码中的 `a[1]`，$x_{C, 0}$ 对应伪代码中的 `x[C, 0]`。

输入的第一行包含两个非负整数 $n, C$。

接下来一行包含 $n$ 个非负整数 $a_0, a_1, \cdots , a_{n - 1}$。

接下来一行包含 $n$ 个非负整数 $b_0, b_1, \cdots , b_{n - 1}$。

outputFormat: 输出包含 $n$ 行，每行包含一个数。第 $i$ 行为 $x_{C, i}\bmod (n + 1)$ 的值。你需要保证输出的数在 $0 \sim n$ 之间。


title: [USACO18JAN] Lifeguards P

type: P

description:
Farmer John has opened a swimming pool for his cows, figuring it will help them relax and produce more milk.

To ensure safety, he hires $N$ cows as lifeguards, each of which has a shift that covers some contiguous interval of time during the day. For simplicity, the pool is open from time $0$ until time $10^9$ on a daily basis, so each shift can be described by two integers, giving the time at which a cow starts and ends her shift. For example, a lifeguard starting at time $t = 4$ and ending at time $t = 7$ covers three units of time (note that the endpoints are "points" in time).

Unfortunately, Farmer John hired $K$ more lifeguards than he has the funds to support. Given that he must fire exactly $K$ lifeguards, what is the maximum amount of time that can still be covered by the shifts of the remaining lifeguards? An interval of time is covered if at least one lifeguard is present.

inputFormat: The first line of input contains $N$ and $K$ ($K \leq N \leq 100,000, 1 \leq K \leq 100$). Each of the next $N$ lines describes a lifeguard in terms of two integers in the range $0 \ldots 10^9$, giving the starting and ending point of a lifeguard's shift. All such endpoints are distinct. Shifts of different lifeguards might overlap.

outputFormat: Please write a single number, giving the maximum amount of time that can still be covered if Farmer John fires $K$ lifeguards.

translation:
给定 $n$ 个左开右闭区间 $(l_i,r_i]$，求去除其中的 $k$ 个后剩下的区间的并集最多可以覆盖多少个整数。

$1\le n\le 10^5,1\le k\le \min(n,100),0\le l_i\le r_i\le 10^9$，保证 $r_i$ 互不相同。

hint: In this example, FJ should fire the lifeguards covering $1 \ldots 8$ and $7 \ldots 15$.


title: [USACO18JAN] Cow at Large P

description:
Cornered at last, Bessie has gone to ground in a remote farm. The farm consists of $N$ barns ($2 \leq N \leq 7 \cdot 10^4$) and $N-1$ bidirectional tunnels between barns, so that there is a unique path between every pair of barns. Every barn which has only one tunnel is an exit. When morning comes, Bessie will surface at some barn and attempt to reach an exit.

But the moment Bessie surfaces at some barn, the law will be able to pinpoint her location. Some farmers will then start at various exit barns, and attempt to catch Bessie. The farmers move at the same speed as Bessie (so in each time step, each farmer can move from one barn to an adjacent barn). The farmers know where Bessie is at all times, and Bessie knows where the farmers are at all times. The farmers catch Bessie if at any instant a farmer is in the same barn as Bessie, or crossing the same tunnel as Bessie. Conversely, Bessie escapes if she reaches an exit barn strictly before any farmers catch her.

Bessie is unsure at which barn she should surface. For each of the $N$ barns, help Bessie determine the minimum number of farmers who would be needed to catch Bessie if she surfaced there, assuming that the farmers distribute themselves optimally among the exit barns.

Note that the time limit for this problem is slightly larger than the default: 4 seconds for C/C++/Pascal, and 8 seconds for Java/Python.

inputFormat: The first line of the input contains $N$. Each of the following $N-1$ lines specify two integers, each in the range $1 \ldots N$, describing a tunnel between two barns.

outputFormat: Please output $N$ lines, where the $i$th line of output tells the minimum number of farmers necessary to catch Bessie if she surfaced at the $i$th barn.

translation:
贝茜在一棵有 $n$ 个节点的树上，每个度为 $1$ 的结点是出入口。开始时，每个出入口都可能有一个农民。每个时刻，贝茜和农民都可以移动到相邻的一个结点。如果在她到达一个出口前，农民与贝茜相遇了（在边上或点上均算），则贝茜将被抓住。过程中，农民们与贝茜均知道对方在哪个结点。

请问：对于每个结点 $i$，如果开始时贝茜在该结点，最少有多少农民，她才会被抓住。

#### 输入

第一行包含 $N$  。

在接下来的 $N-1$  行中，每行有两个在 $1\sim N$   范围内的整数，表示一条边。

#### 输出

输出 $N$   行，第 $i$   行表示如果开始时贝茜在结点 $i$   ，最少有多少农民，她才会被抓住。

Translated by @Planet6174


title: [USACO18JAN] Sprinklers P

description:
Farmer John has a large field, and he is thinking of planting sweet corn in some part of it. After surveying his field, FJ found that it forms an $(N-1) \times (N-1)$ square. The southwest corner is at coordinates $(0,0)$, and the northeast corner is at $(N-1,N-1)$.

At some integer coordinates there are double-headed sprinklers, each one sprinkling both water and fertilizer. A double-heading sprinkler at coordinates $(i,j)$ sprinkles water on the part of the field north and east of it, and sprinkles fertilizer on the part of the field south and west of it. Formally, it waters all real coordinates $(x,y)$ for which $N \geq x \geq i$ and $N \geq y \geq j$, and it fertilizes all real coordinates $(x,y)$ for which $0 \leq x \leq i$ and $0 \leq y \leq j$.

Farmer John wants to plant sweet corn in some axis-aligned rectangle in his field with integer-valued corner coordinates. However, for the sweet corn to grow, all points in the rectangle must be both watered and fertilized by the double-headed sprinklers. And of course the rectangle must have positive area, or Farmer John wouldn't be able to grow any corn in it!

Help Farmer John determine the number of rectangles of positive area in which he could grow sweet corn. Since this number may be large, output the remainder of this number modulo $10^9 + 7$.

inputFormat:
The first line of the input consists of a single integer $N$, the size of the field ($1 \leq N \leq 10^5$).

The next $N$ lines each contain two space-separated integers. If these integers are $i$ and $j$, where $0 \leq i,j \leq N-1$, they denote a sprinkler located at $(i,j)$.

It is guaranteed that there is exactly one sprinkler in each column and exactly one sprinkler in each row. That is, no two sprinklers have the same $x$-coordinate, and no two sprinklers have the same $y$-coordinate.

outputFormat: The output should consist of a single integer: the number of rectangles of positive area which are fully watered and fully fertilized, modulo $10^9 + 7$.

translation:
农夫约翰有块田，这块田可视为一个 $N×N$  的正方形网格。西南角为 $(0,0)$ ，东北角为 $(N-1, N-1)$ 。
在某些格子中有双头喷头，每一个都能够同时喷洒水和肥料。一个位于 $(i,j)$  的双头喷头会
* 将水洒在所有满足 $N≥x≥i,$  $N≥y≥j$  的格子 $(x,y)$  上；
* 将肥料洒在所有满足 $0≤x≤i$  和 $0≤y≤j$  的格子 $(x,y)$  上。

农民约翰想在这块田里切割出一个矩形种甜玉米。矩形的边不能把格子切开。矩形内的所有格子都必须能由双头喷头灌溉和施肥。
求切割矩形的方案数。由于这个数字可能很大，所以输出对 $10^9+7$  取模。
输入

第一行包含一个整数 $N$ ，表示农场的大小。
接下来的 $N$  行，每行有两个由空格分隔的整数 $i, j$ 。这表示有一个双头喷头位于 $(i, j)$ 。
保证每列都有一台喷头，每排正好有一台喷头。换句话说，没有两个喷头有相同的横坐标或纵坐标。
输出

输出包含一行，表示方案数，对 $10^9+7$  取模。


title: [USACO18JAN] MooTube G

background: *本题与 [银组同名题目](/problem/P6111) 在题意上一致，唯一的差别是数据范围。*

description:
在业余时间，Farmer John 创建了一个新的视频共享服务，他将其命名为 MooTube。在 MooTube 上，Farmer John 的奶牛可以录制，分享和发现许多有趣的视频。他的奶牛已经发布了 $N$ 个视频（$1 \leq N \leq 10^5$），为了方便将其编号为  $1 \ldots N$ 。然而，FJ 无法弄清楚如何帮助他的奶牛找到他们可能喜欢的新视频。

FJ 希望为每个 MooTube 视频创建一个“推荐视频”列表。这样，奶牛将被推荐与他们已经观看过的视频最相关的视频。

FJ 设计了一个“相关性”度量标准，顾名思义，它确定了两个视频相互之间的相关性。他选择 $N-1$ 对视频并手动计算其之间的相关性。然后，FJ 将他的视频建成一棵树，其中每个视频是节点，并且他手动将 $N-1$ 对视频连接。为了方便，FJ 选择了 $N-1$ 对，这样任意视频都可以通过一条连通路径到达任意其他视频。 FJ 决定将任意一对视频的相关性定义为沿此路径的任何连接的最小相关性。

Farmer John 想要选择一个 $K$ 值，以便在任何给定的 MooTube 视频旁边，推荐所有其他与该视频至少有 $K$ 相关的视频。然而，FJ 担心会向他的奶牛推荐太多的视频，这可能会分散他们对产奶的注意力！因此，他想设定适当的 $K$ 值。 Farmer John希望得到您的帮助，回答有关 $K$ 值的推荐视频的一些问题。

inputFormat:
第一行输入包含 $N$ 和 $Q$（$1 \leq Q \leq 10^5$）。

接下来的 $N-1$ 行描述了 FJ 手动比较的一对视频。 每行包括三个整数  $p_i$，$q_i$ 和 $r_i$（$1 \leq p_i, q_i \leq N$，$1 \leq r_i \leq 10^9$），表示视频 $p_i$ 和 $q_i$ 已连接并且相关性为 $r_i$。

接下来的 $Q$ 行描述了 Farmer John 的 $Q$ 个问题。每行包含两个整数，$k_i$ 和 $v_i$（$1 \leq k_i \leq 10^9$，$1 \leq v_i \leq N$），表示 FJ 的第 $i$ 个问题询问中当 $K = k_i$ 时，第 $v_i$ 个视频推荐列表中将推荐的视频数。

outputFormat: 输出 $Q$ 行。在第 $i$ 行，输出 FJ 的第 $i$ 个问题的答案。


title: [USACO18JAN] Cow at Large G

description:
Cornered at last, Bessie has gone to ground in a remote farm. The farm consists of $N$ barns ($2 \leq N \leq 10^5$) and $N-1$ bidirectional tunnels between barns, so that there is a unique path between every pair of barns. Every barn which has only one tunnel is an exit. When morning comes, Bessie will surface at some barn and attempt to reach an exit.

But the moment Bessie surfaces, the law will be able to pinpoint her location. Some farmers will then start at various exit barns, and attempt to catch Bessie. The farmers move at the same speed as Bessie (so in each time step, each farmer can move from one barn to an adjacent barn). The farmers know where Bessie is at all times, and Bessie knows where the farmers are at all times. The farmers catch Bessie if at any instant a farmer is in the same barn as Bessie, or crossing the same tunnel as Bessie. Conversely, Bessie escapes if she reaches an exit barn before any farms catch her.

Bessie is unsure about her chances of success, which depends on the number of farmers that the law is able to deploy. Given that Bessie surfaces at barn $K$, help Bessie determine the minimum number of farmers who would be needed to catch Bessie, assuming that the farmers distribute themselves optimally among the exit barns.

inputFormat: The first line of the input contains $N$ and $K$. Each of the following $N-1$ lines specify two integers, each in the range $1 \ldots N$, describing a tunnel between two barns.

outputFormat: Please output the minimum number of farmers needed to ensure catching Bessie.

translation:
## 题目描述
最后，Bessie 被迫去了一个远方的农场。这个农场包含 $N$ 个谷仓（$2 \le N \le 10^5$）和 $N-1$ 条连接两个谷仓的双向隧道，所以每两个谷仓之间都有唯一的路径。每个只与一条隧道相连的谷仓都是农场的出口。当早晨来临的时候，Bessie 将在某个谷仓露面，然后试图到达一个出口。

但当 Bessie 露面的时候，她的位置就会暴露。一些农民在那时将从不同的出口谷仓出发尝试抓住 Bessie。农民和 Bessie 的移动速度相同（在每个单位时间内，每个农民都可以从一个谷仓移动到相邻的一个谷仓，同时 Bessie 也可以这么做）。农民们和Bessie 总是知道对方在哪里。如果在任意时刻，某个农民和 Bessie 处于同一个谷仓或在穿过同一个隧道，农民就可以抓住 Bessie。反过来，如果 Bessie 在农民们抓住她之前到达一个出口谷仓，Bessie 就可以逃走。

Bessie 不确定她成功的机会，这取决于被雇佣的农民的数量。给定 Bessie 露面的谷仓K，帮助 Bessie 确定为了抓住她所需要的农民的最小数量。假定农民们会自己选择最佳的方案来安排他们出发的出口谷仓。

## 输入格式

输入的第一行包含 $N$ 和 $K$。接下来的 $N – 1$ 行，每行有两个整数（在 $1\sim N$ 范围内）描述连接两个谷仓的一条隧道。

## 输出格式

输出为了确保抓住 Bessie 所需的农民的最小数量。

由 @Marser 提供翻译


title: [USACO18JAN] Stamp Painting G

description:
Bessie has found herself in possession of an $N$-unit long strip of canvas ($1 \leq N \leq 10^6$), and she intends to paint it. However, she has been unable to acquire paint brushes. In their place she has $M$ rubber stamps of different colors ($1 \leq M \leq 10^6$), each stamp $K$ units wide ($1 \leq K \leq 10^6$). Astounded by the possibilities that lie before her, she wishes to know exactly how many different paintings she could conceivably create, by stamping her stamps in some order on the canvas.

To use a stamp, it must first be aligned with exactly $K$ neighboring units on the canvas. The stamp cannot extend beyond the ends of the canvas, nor can it cover fractions of units. Once placed, the stamp paints the $K$ covered units with its color. Any given stamp may be used multiple times, once, or even never at all. But by the time Bessie is finished, every unit of canvas must have been painted at least once.

Help Bessie find the number of different paintings that she could paint, modulo $10^9 + 7$. Two paintings that look identical but were painted by different sequences of stamping operations are counted as the same.

For at least 75% of the input cases, $N,K \leq 10^3$.

inputFormat: The first and only line of input has three integers, $N$, $M$, and $K$. It is guaranteed that $K \leq N$.

outputFormat: A single integer: the number of possible paintings, modulo $10^9 + 7$.

translation:
Bessie想拿$M$  种颜色的长为$K$  的图章涂一个长为$N$  的迷之画布。假设他选择涂一段区间，则这段区间长度必须为$K$  ，且涂完后该区间颜色全变成图章颜色。他可以随便涂，但是最后必须把画布画满。问能有多少种最终状态，$N\leq 10^6,M\leq 10^6,K\leq 10^6$

对于$75\%$  的数据，$N,K\leq 10^3$

输入输出格式

输入格式：

一行3个整数$N,M,K$

输出格式：

一个整数表示答案（模$10^9+7$  ）

输入输出样例

说明

如果两个图章叫A,B，合法方案如下:AAB,ABB,BAA,BBA,AAA,BBB

Translated by @ComeIntoPower

hint: If the two stamps have colors A and B, the possible paintings are AAA, AAB, ABB, BAA, BBA, and BBB.


title: [USACO18JAN] Lifeguards S

description:
Farmer John has opened a swimming pool for his cows, figuring it will help them relax and produce more milk.

To ensure safety, he hires $N$ cows as lifeguards, each of which has a shift that covers some contiguous interval of time during the day. For simplicity, the pool is open from time $t=0$ until time $t = 1,000,000,000$ on a daily basis, so each shift can be described by two integers, giving the time at which a cow starts and ends her shift. For example, a lifeguard starting at time $t = 4$ and ending at time $t = 7$ covers three units of time (note that the endpoints are "points" in time).

Unfortunately, Farmer John hired 1 more lifeguard than he has the funds to support. Given that he must fire exactly one lifeguard, what is the maximum amount of time that can still be covered by the shifts of the remaining lifeguards? An interval of time is covered if at least one lifeguard is present.

inputFormat: The first line of input contains $N$ ($1 \leq N \leq 100,000$). Each of the next $N$ lines describes a lifeguard in terms of two integers in the range $0 \ldots 1,000,000,000$, giving the starting and ending point of a lifeguard's shift. All such endpoints are distinct. Shifts of different lifeguards might overlap.

outputFormat: Please write a single number, giving the maximum amount of time that can still be covered if Farmer John fires 1 lifeguard.

translation:
FJ 为他的奶牛们建造了一个游泳池，FJ 认为这将有助于他们放松身心以及生产更多牛奶。

为了确保奶牛们的安全，FJ 雇佣了 $N$ 头牛，作为泳池的救生员，每一个救生员在一天内都会有一定的事情，并且这些事情都会覆盖一天内的一段时间。为了简单起见，泳池从时间 $t=0$ 时开门，直到时间 $t=10^9$ 关门，所以每个事情都可以用两个整数来描述，给出奶牛救生员开始以及结束事情的时间。例如，一个救生员在时间 $t=4$ 时开始事情并且在时间 $t=7$ 时结束事情，那么这件事情就覆盖了 $3$ 个单位时间。（注意：结束时间是“点”的时间）

不幸的是，FJ 多雇佣了一名的救生员，但他没有足够的资金来雇佣这些救生员。因此他必须解雇一名救生员，求可以覆盖剩余救生员的轮班时间的最大总量是多少？如果当时至少有一名救生员的事情已经开始，则这个时段被覆盖。

### 输入格式

输入的第一行包括一个整数 $N\ ( 1 \le N \le 100000)$。接下来 $N$ 行中，每行告诉了我们一个救生员在 $0 \sim 10^9$ 范围内的开始以及结束时间。所有的结束时间都是不同的。不同的救生员的事情覆盖的时间可能会重叠。

### 输出格式

输出一行一个整数，如果 FJ 解雇一名救生员仍能覆盖的最大时间。


title: [USACO18JAN] Rental Service S

description:
Farmer John realizes that the income he receives from milk production is insufficient to fund the growth of his farm, so to earn some extra money, he launches a cow-rental service, which he calls "USACOW" (pronounced "Use-a-cow").

Farmer John has $N$ cows ($1 \leq N \leq 100,000$), each capable of producing some amount of milk every day. The $M$ stores near FJ's farm ($1 \leq M \leq 100,000$) each offer to buy a certain amount of milk at a certain price. Moreover, Farmer John's $R$ ($1 \leq R \leq 100,000$) neighboring farmers are each interested in renting a cow at a certain price.

Farmer John has to choose whether each cow should be milked or rented to a nearby farmer. Help him find the maximum amount of money he can make per day.

inputFormat: The first line in the input contains $N$, $M$, and $R$. The next $N$ lines each contain an integer $c_i$ ($1 \leq c_i \leq 1,000,000$), indicating that Farmer John's $i$th cow can produce $c_i$ gallons of milk every day. The next $M$ lines each contain two integers $q_i$ and $p_i$ ($1 \leq q_i, p_i \leq 1,000,000$), indicating that the $i$th store is willing to buy up to $q_i$ gallons of milk for $p_i$ cents per gallon. Keep in mind that Farmer John can sell any amount of milk between zero and $q_i$ gallons to a given store. The next $R$ lines each contain an integer $r_i$ ($1 \leq r_i \leq 1,000,000$), indicating that one of Farmer John's neighbors wants to rent a cow for $r_i$ cents per day.

outputFormat: The output should consist of one line containing the maximum profit Farmer John can make per day by milking or renting out each of his cows. Note that the output might be too large to fit into a standard 32-bit integer, so you may need to use a larger integer type like a "long long" in C/C++.

translation:
Farmer John 有 $N$ ($1 \leq N \leq 100,000$) 头牛，他想赚更多的钱，所以他准备买牛奶和出租牛。有 $M$ ($1 \leq M \leq 100,000$) 家商店想买牛奶，每家商店的进货价不同。有 $R$ ($1 \leq R \leq 100,000$) 户邻居想租牛，每户人家的租价不同。 问他最多能赚多少钱。

输入：输入的第 $1$ 行包含 $n$，$m$，$r$ 三个整数。紧接着的 $n$ 行每一行有1个整数 $C_i$ ($1 \leq C_i \leq 1,000,000$)，表示第 $i$ 头牛产出 $C_i$ 加仑奶。再下面的 $m$ 行每行有两个整数 $Q_i$ 与 $P_i$ ($1 \leq Q_i, P_i \leq 1,000,000$)，表示第 $i$ 个商店最多以 $P_i$ 美分每加仑的价格购买 $Q_i$ 加仑牛奶。Farmer John 可销售 $0 \sim Q_i$ 加仑牛奶到一个商店。接下来的 $r$ 行每行有一个整数 $R_i$，表示 Farmer John 的第 $i$ 个邻居想以 $R_i$ ($1 \leq R_i \leq 1,000,000$) 的价格租一头牛。

输出：仅一行。表示一天最多获得多少钱。

注意：int 类型不够大！！！

说明：Farmer John 需要挤一号和四号奶牛的奶，共可得牛奶 $13$ 加仑。他可以先买给出价最高的 $10$ 加仑，赚 $250$ 美分，然后把剩下的按每加仑 $15$ 美分去卖，共有 $295$ 美分的利润。 然后，他要把其他三头以 $250$, $80$ 和 $100$ 美分的价格分别卖出，赚 $430$ 美分。所以他一共可得 $725$ 美分/日的利润。

---by 风格雨关、WuYongxuan、毕沁露

hint:
Farmer John should milk cows #1 and #4, to produce 13 gallons of milk. He should completely fill the order for 10 gallons, earning 250 cents, and sell the remaining three gallons at 15 cents each, for a total of 295 cents of milk profits.

Then, he should rent out the other three cows for 250, 80, and 100 cents, to earn 430 more cents. (He should leave the request for a 40-cent rental unfilled.) This is a total of 725 cents of daily profit.


title: [CTSC2010] 三国围棋擂台赛

description:
一年一度的“农心杯”三国围棋擂台赛是世界上最高水平的围棋比赛，也是中日韩三国围棋界最激动人心的较量。本题就是建立在这一比赛的规则之上。

三国围棋擂台赛是三个国家的代表队之间的比赛，下面简要介绍一下比赛的规则：

1.不妨设三个国家分别为$A$、$B$和$C$，每个国家各有$n$名选手（在上述的实际比赛中$n = 5$），分别称其为$A_1$，$A_2$，…，$A_n$，$B_1$，$B_2$，…，$B_n$，$C_1$，$C_2$，…，$C_n$。

2.每场比赛都能分出胜负。每场比赛的负者遭到淘汰。

3.每队第一位出场的选手都已经确定为每队的第$n$位选手，即$A_n$、$B_n$和 $C_n$。

4.通过抽签等概率地选出一支队伍。该队将在第一轮中轮空，而剩下的两支队伍的第$n$位选手将进行第一场比赛。

5.第一场比赛的胜者（这里的胜者是指赢得该局比赛的选手，下同）与轮空队伍的第$n$位选手进行第二场比赛。比如在第一场比赛中$C_n$战胜了$A_n$，则第二场则由$C_n$对阵$B_n$。

6.从第三场比赛开始，前一场比赛未参加的队伍将选出一个未被淘汰的选手与上一场比赛的胜者进行下一场比赛。

7.这个过程将一直进行，直到某个队伍的全部参赛选手都被淘汰为止。

8.当只有两支队伍的时候，每场比赛后，由负方选择一位未被淘汰的选手与胜者进行下一场比赛。

9.当两支队伍中的任意一队的全部选手均被淘汰后比赛结束，余下的那支队伍将获得农心杯。

新一届的比赛就要开始了。你作为$A$队的领队，在比赛开始前已经统计了这$3n$位选手之间的胜率——即对于来自不同队伍的两个选手$Q$和$R$，我们已知$Q$战胜$R$的概率为$p$（$0 \leq p \leq 1$），且$R$战胜$Q$的概率为$1-p$。

由于你所在的国家实力超群，可以认为剩下的两只队伍都将矛头对准了你。$B$、$C$队的每个决策，即派出选手的顺序的目的都是使你所在的国家（$A$队）夺冠的概率尽可能小，而$A$队的决策的目的必然是使最后夺冠的概率尽可能大。你要做的事情就是计算出在这种极为不利的情况下，在三方都做出最优决策的前提下，$A$队夺冠的期望$E_A$。

关于期望的计算：设现在在场上比赛的人是$Q$和$R$，$Q$胜$R$的概率为$p$，则此时$A$队胜率的期望

$E_A = p$ × $E_1 + (1 - p)$ × $E_2$

其中$E_1$为$Q$胜$R$后$A$队夺冠的期望，$E_2$为$R$胜$Q$后$A$队夺冠的期望。$E_1$、$E_2$则同样使用上式递归计算。

$A$队的决策会尽可能使这个期望尽可能大，而$B$、$C$队则会使这个期望尽可能小。当$B$、$C$队的全部选手都被淘汰后夺冠期望为$1$，$A$队所有队员被淘汰后期望为$0$。

例如当每队有$3$位参赛选手时，相互之间的胜率由如下的$3$个$3*3$的矩阵给出，其中矩阵中的每个数值$p$为所在行选手对于所在列选手的胜率，所在列选手对于所在行选手的胜率为$1-p$。

![QQ20180130165331.png](https://www.z4a.net/images/2018/01/30/QQ20180130165331.png)

三支队的第三位选手的水平相同，在第两局比赛后，三支队的选手获胜的概率是相同的。假设第二局获胜的是$B_3$，第三局轮到$A$队出场。这时我们可以派出$A_1$和$A_2$两种选择。

如果派出$A_2$，虽然第三局一定可以战胜$B_3$（胜率为$100 \%$），但是$C$队会在第四场比赛中派出$C_2$，$A_2$对于$C_2$必败（胜率为$0$），第五场中$B$队会让$B_1$出场，第六场$A_1$只能出场，这时对$A_1$必胜的$B_2$还未登场，因此$A_1$迟早会遭到淘汰，$A$队夺冠的概率就为$0$。

如果派出$A_1$，虽然本局对于$B_3$比赛只有$50 \%$的胜率，但是夺冠的概率为$6.25 \%$；因此在第三场应该派出$A_1$。

根据第三场比赛的参赛选手的六种情况，最后夺冠的期望为：

$$ \dfrac{(6.25\%+3.125\%+18.75\%+25\%+60.9375\%+50\%)}{6} = 27.34375\%$$

inputFormat:
输入文件为go.in。

第一行包括一个整数$n$，表示每队的选手数。

第二行到第$n + 1$行每行包含$n$个实数，整体为一个$n*n$的矩阵，表示$A$队对$B$队的胜率。其中第$i + 1$行的第$j$个数表示选手$A_i$对选手$B_j$时的胜率。

第$n + 2$行为空行。

第$n + 3$行到第$2n + 2$行每行包含$n$个实数，同样为一个$n*n$的矩阵，表示$A$队对$C$队的胜率。其中第$i + n + 2$行的第$j$个数表示选手$A_i$对选手$C_j$时的胜率。

第$2n + 3$行为空行。

第$2n + 4$行到第$3n + 3$行每行包含$n$个实数，整体为一个$n*n$的矩阵，表示$B$队对$C$队的胜率。其中第$i + 2n + 3$行的第$j$个数表示选手$B_i$对选手$C_j$时的胜率。

outputFormat: 输出文件go.out仅包含一个实数，保留$6$位小数，表示$A$队获得冠军的概率。

hint:
$30\%$的数据中，$n \leq 4$。

$40\%$的数据中，$n \leq 5$。

$100\%$的数据中，$n \leq 7$。

对于$10\%$的数据有三个胜率矩阵中，每个矩阵的元素都相同，但不同矩阵的数字可能不同。


title: [NOI2006] 最大获利

description:
新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。

在前期市场调查和站址勘测之后，公司得到了一共 $N$ 个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第 $i$ 个通讯中转站需要的成本为 $P_i$（$1 \leq i \leq N$）。

另外公司调查得出了所有期望中的用户群，一共 $M$ 个。关于第 $i$ 个用户群的信息概括为 $A_i$，$B_i$ 和 $C_i$ ：这些用户会使用中转站 $A_i$ 和中转站 $B_i$ 进行通讯，公司可以获益 $C_i$。（$1 \leq i \leq M$，$1 \leq A_i, B_i \leq N$）

THU 集团的 CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）

inputFormat:
输入文件中第一行有两个正整数 $N$ 和 $M$。

第二行中有 $N$ 个整数描述每一个通讯中转站的建立成本，依次为 $P_1 , P_2 , …,P_N$。

以下 $M$ 行，第 $i + 2$ 行的三个数 $A_i , B_i$ 和 $C_i$ 描述第 $i$ 个用户群的信息。

所有变量的含义可以参见题目描述。

outputFormat: 你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。

hint:
样例：选择建立 $1,2,3$ 号中转站，则需要投入成本 $6$，获利为 $10$，因此得到最大收益 $4$。

$100\%$ 的数据中：$N \leq 5\,000$，$M \leq50\,000$，$0 \leq C_i \leq 100$，$0 \leq P_i  \leq 100$。


title: [CTSC2008] 网络管理

description:
M 公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的 $n$ 个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。

该网络的结构由 $n$ 个路由器和 $n-1$ 条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信。

高速光缆的数据传输速度非常快，以至于利用光缆传输的延迟时间可以忽略。但是由于路由器老化，在这些路由器上进行数据交换会带来很大的延迟。而两个路由器之间的通信延迟时间则与这两个路由器通信路径上所有路由器中最大的交换延迟时间有关。

作为 M 公司网络部门的一名实习员工，现在要求你编写一个简单的程序来监视公司的网络状况。该程序能够随时更新网络状况的变化信息（路由器数据交换延迟时间的变化），并且根据询问给出两个路由器通信路径上延迟第 $k$ 大的路由器的延迟时间。
****
【任务】
你的程序从输入文件中读入 $n$ 个路由器和 $n-1$ 条光缆的连接信息，每个路由器初始的数据交换延迟时间 $t_i$，以及 $q$ 条询问（或状态改变）的信息。并依次处理这 $q$ 条询问信息，它们可能是：

1. 由于更新了设备，或者设备出现新的故障，使得某个路由器的数据交换延迟时间发生了变化。

2. 查询某两个路由器 $a$ 和 $v$ 之间的路径上延迟第 $k$ 大的路由器的延迟时间。

inputFormat:
第一行为两个整数 $n$ 和 $q$，分别表示路由器总数和询问的总数。

第二行有 $n$ 个整数，第 $i$ 个数表示编号为i的路由器初始的数据延迟时间 $t_i$。

紧接着 $n-1$ 行，每行包含两个整数 $x$ 和 $y$。表示有一条光缆连接路由器 $x$ 和路由器 $y$。

紧接着是 $q$ 行，每行三个整数 $k,a,b$。

如果 $k=0$，则表示路由器 $a$ 的状态发生了变化，它的数据交换延迟时间由 $t_a$ 变为 $b$。

如果 $k>0$，则表示询问 $a$ 到 $b$ 的路径上所经过的所有路由器（包括 $a$ 和 $b$）中延迟第 $k$ 大的路由器的延迟时间。注意 $a$ 可以等于 $b$，此时路径上只有一个路由器。

outputFormat:
对于每一个第二种询问（即 $k>0$ ），输出一行。
包含一个整数为相应的延迟时间。如果路径上的路由器不足 $k$ 个，则输出信息 `invalid request!`。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n,q \le 80000$，$0 \le k \le n$，任意一个路由器在任何时刻都满足延迟时间小于 $10^8$。


title: [HNOI2006] 花仙子的魔法

description: 相传，在天地初成的远古时代，世界上只有一种叫做“元”的花。接下来，出现了一位拥有魔法的花仙子，她能给花附加属性，从此，“元”便不断变异，产生了大千世界千奇百怪的各种各样的花。据说，花仙子既可存在于二维空间（平面），又可存在于三维空间（立体），还可存在于 $n$ 维空间（想象）。二维空间的点可用向量 $\left(x_1,x_2\right)$ 表示，三维空间的点可用向量 $\left(x_1,x_2,x_3\right)$ 表示，一般来说，$n$ 维空间的点可用向量 $\left(x_1,x_2,\cdots,x_n\right)$ 表示。而 $n$ 维空间中两点 $\left(x_1,x_2,\cdots,x_n\right)$ 与 $\left(w_1,w_2,\cdots,w_n\right)$ 之间的距离定义为$\sqrt{\sum_{i=1}^{n}(X_i-W_i)^2}$。 在 $n$ 维空间中，花仙子每实施魔法就要选择一个参考点 $\left(w_1,w_2,\cdots,w_n\right)$ 和一个作用半径 $r$，并且参考点的位置和作用半径的大小可以任意选择。这时，$n$ 维空间中所有与参考点 $\left(w_1,w_2,\cdots,w_n\right)$ 之间的距离小于作用半径 $r$ 的花都会受到这次魔法的影响。每次魔法都会给受到影响的花带来不同的属性，且的效 果可以叠加。一般来说，若花仙子总共实施了 $m$ 次魔法，则 $n$ 维空间中处于某点的花所具有的属性可用长度为 $m$ 的二进制串 $\left(a_1,a_2,\cdots,a_n\right)$ 来描述，其中对 $1\le i\le m$，若该花受到第 $i$ 次魔法的影响，则 $a_i$ 的值为 $1$,否则为 $0$。显然，不同的属性对应不同的花。 现在的问题是：花仙子在 $n$ 维空间中实施了 $m$ 次魔法后，最多能得到多少种不同的花？

inputFormat: 包含两个整数，并用一个空格隔开，第一个整数表示实施魔法的次数 $m$，第二个整数表示空间的维数 $n$。其中，$1\le m\le 100$，$1 \le n \le 15$。

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


title: [CEOI2008] order

description:
有 $N$ 个工作，$M$ 种机器，每种机器可以租或者买。每个工作包括若干道工序，每道工序需要某种机器来完成。

你需要最大化利益。

inputFormat:
第一行给出 $N,M$。

接下来若干行描述一个工作，对于每个工作，第一行给定 $x_i$ 和 $t_i$，分别表示此工作的收入和工序数。

后面 $t_i$ 行，每行两个整数 $a_{ij}$ 和 $b_{ij}$，分别表示此工序需要的机器和此工作租用此机器的费用。

最后 $M$ 行，每行一个正整数表示购买机器的费用 $y_i$。

outputFormat: 最大利润


title: Tree

description: 给定一棵 $n$ 个节点的树，每条边有边权，求出树上两点距离小于等于 $k$ 的点对数量。

inputFormat:
第一行输入一个整数 $n$，表示节点个数。

第二行到第 $n$ 行每行输入三个整数 $u,v,w$ ，表示 $u$ 与 $v$ 有一条边，边权是 $w$。

第 $n+1$ 行一个整数 $k$ 。

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

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

对于全部的测试点，保证：

- $1\leq n\leq 4\times 10^4$。
- $1\leq u,v\leq n$。
- $0\leq w\leq 10^3$。
- $0\leq k\leq 2\times 10^4$。


title: [CQOI2010] 鼹鼠

description:
Hilbert鼹鼠住在Hilbert地洞里——地洞的边界是一条$n$阶Hilbert曲线${H_n}$。Hilbert曲线的定义如下：${H_1}$是一个上端缺口的单位正方形；$H_n$由四份${H_n}-1$组成，其中左下和右下两份没有任何变化，而左上的那一份逆时针旋转了90度，而右上的那一份顺时针旋转了90度。这四份$H_n-1$用三条单位长度的线段连接起来构成了$H_n$。$H_1$~$H_4$如下图所示：

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

你想捉一只Hilbert鼹鼠来玩，所以往地洞里使劲倒水想把它们赶出来。不过，由于地洞里有空气，无论你怎么倒水，有些地方总是淹不到的（假设水和空气都不可压缩）。输入Hilbert曲线

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

的阶数 $n$ 和地面的倾斜角 $α$ ，你的任务是计算能淹没到的面积。

注意，只有当水位严格高于一个障碍物时，水才能越过它往下流。更多细节可以参考下面的例子。

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

inputFormat: 输入仅包含两个整数$n$，$α$。

outputFormat: 输出仅一行，即被淹没的面积，输出保留小数点后6位。


title: [BJWC2010] 严格次小生成树

description:
小 C 最近学了很多最小生成树的算法，Prim 算法、Kruskal 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是 $E_M$，严格次小生成树选择的边集是 $E_S$，那么需要满足：($value(e)$ 表示边 $e$ 的权值) $\sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e)$。

这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

inputFormat:
第一行包含两个整数 $N$ 和 $M$，表示无向图的点数与边数。

接下来 $M$ 行，每行 $3$ 个数 $x,y,z$ 表示，点 $x$ 和点 $y$ 之间有一条边，边的权值为 $z$。

outputFormat: 包含一行，仅一个数，表示严格次小生成树的边权和。

hint:
数据中无向图**不保证无自环**。

对于 $50\%$ 的数据， $N\le 2000$，$M\le 3000$。

对于 $80\%$ 的数据， $N\le 5\times 10^4$，$M\le 10^5$。

对于 $100\%$ 的数据， $N\le 10^5$，$M\le 3\times10^5$，边权  $\in [0,10^9]$，数据保证必定存在严格次小生成树。


title: 采摘毒瘤

background: Salamander见到路边有如此多的毒瘤，于是见猎心喜，从家里拿来了一个大袋子，准备将一些毒瘤带回家。

description:
路边共有$n$种不同的毒瘤，第$i$种毒瘤有$k_i$个，每个需要占据$d_i$的空间。Salamander的袋子能装下的最大体积为$m$。

Salamander是一个很贪心的人，不过他也**不要求**带尽可能多或是总体积尽可能大的毒瘤回家，他只要求袋子里**再也装不下剩余的任何一种毒瘤**。

Salamander想知道有多少种不同的装毒瘤的方案。两种方案不同当且仅当取的毒瘤种类不同或者至少有一种毒瘤取的数量不同。由于方案数可能太多，请输出答案对$19260817$取模后的结果。

inputFormat:
第一行包括两个正整数$n$、$m$，表示毒瘤的种类数和袋子的大小。

接下来的$n$行，每行两个正整数$k_i$、$d_i$，表示一种毒瘤。

outputFormat: 一行，表示不同的方案数对$19260817$取模后的结果。

hint:
###样例解释：

两种方案如下：

1.取1个第一种毒瘤和2个第二种毒瘤。

2.取3个第二种毒瘤。

$~$
$~$

对于10%的数据，$1\leq n,k_i,d_i\leq 10$，$1\leq m\leq 100$；

对于30%的数据，$1\leq n,k_i,d_i\leq 50$，$1\leq m\leq 5000$；

对于另外20%的数据，$k_i=1$；

对于100%的数据，$1\leq n,k_i,d_i\leq 500$，$1\leq m\leq 10^5$。


title: 树上的毒瘤

background: Salamander开心地把一大袋毒瘤带回了家，把他们染上了不同的颜色，并把他们挂在了院子里的树上。

description:
这棵树上有$n$个节点，由$n-1$条树枝相连。初始时树上都挂了一个毒瘤，颜色为$c_i$。接下来Salamander将会进行$q$个操作。

Salamander有时会修改树上某个点到另外一个点的简单路径上所有毒瘤的颜色。

对于给定的树上**某个点集$S$**，Salamander还定义了某个点的权值：

$$W_i=\sum_{j\in S}T(i,j)$$

其中$T(i,j)$表示$i$到$j$的路径上毒瘤颜色的**段数**，比如$i$到$j$的路径上毒瘤颜色为$1223312$时，颜色段数为$5$。

Salamander对树上的毒瘤们的状态很感兴趣，所以有时会指定树上$m$个节点作为点集，询问这$m$个节点的权值。

inputFormat:
第一行包括两个正整数$n$、$q$，表示树上的节点数和操作个数。

第二行包括用空格隔开的$n$个正整数$c_i$，表示树上每个节点初始的毒瘤颜色。

接下来$n-1$行，每行两个正整数$u$、$v$，表示树上有一条连接$u$和$v$的边。

接下来描述$q$个操作：

- 1 若给出的第一个整数等于$1$，那么接下来将会有三个正整数$u$、$v$、$y$，表示将树上编号为$u$的点到编号为$v$的点的简单路径上的毒瘤颜色全都改为$y$。

- 2 若给出的第一个整数等于$2$，那么接下来将会有一个正整数$m$，表示指定的树上节点个数。下一行将会有$m$个用空格隔开的互不相同的正整数，表示当前询问给定的$m$个节点。

outputFormat: 若干行，对于每个$2$操作输出对应的答案。

hint:
保证输入数据合法。

对于30%的数据，有$1\leq n,q\leq 1000$，$\sum m\leq 5000$。

对于60%的数据，有$1\leq n,q\leq 20000$，$\sum m\leq 100000$。

对于100%的数据，有$1\leq n,q\leq 100000$，$c_i,y\leq 10^9$，$\sum m\leq 200000$，$m\leq n$。


title: 旅行规划

description:
OIVillage 是一个风景秀美的乡村，为了更好的利用当地的旅游资源，吸引游客，推动经济发展，xkszltl 决定修建了一条铁路将当地 $n$ 个最著名的经典连接起来，让游客可以通过火车从铁路起点（1 号景点）出发，依次游览每个景区。为了更好的评价这条铁路，xkszltl 为每一个景区都哦赋予了一个美观度，而一条旅行路径的价值就是它所经过的景区的美观度之和。不过，随着天气与季节的变化，某些景点的美观度也会发生变化。

xkszltl 希望为每位旅客提供最佳的旅行指导，但是由于游客的时间有限，不一定能游览全部景区，然而他们也不希望旅途过于短暂，所以每个游客都希望能在某一个区间内的车站结束旅程，而 xkszltl 的任务就是为他们选择一个终点使得旅行线路的价值最大。可是当地的景点与前来观光的旅客实在是太多了，xkszltl 无法及时完成任务，于是找到了准备虐杀 NOI2011 的你，希望你能帮助他完成这个艰巨的任务。

inputFormat:
第一行给出一个整数 $n$，接下来一行给出 $n$ 个景区的初始美观度。

第三行给出一个整数 $m$，接下来 $m$ 行每行为一条指令：

1. `0 x y k`：表示将 $x$ 到 $y$ 这段铁路边上的景区的美观度加上k；

2. `1 x y`：表示有一名旅客想要在 $x$ 到 $y$ 这段（含 $x$ 与 $y$）中的某一站下车，你需要告诉他最大的旅行价值。

outputFormat: 对于每个询问，输出一个整数表示最大的旅行价值。


title: 数字

description:
小 D 喜欢的数有这样的性质：
令 $n$ 为正整数，$S(n)$ 为 $n$ 的各位数字之和，令

$$D(n)\begin{cases}\displaystyle S(n), S(n)<10 \\\displaystyle D(S(n)), S(n)>10\end{cases}$$

小 D 喜欢的数一定能表示成 $x×D(x)$ 这种形式（即若一个数 A 是被喜欢的，则存在一个数 $x$，使得 $A=x\times D(x)$）。
小 D 想知道在区间 [L, R] 中，有多少个数是他喜欢的。

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

以下每一行两个数L、R（保证区间合法），代表询问[L, R]。

outputFormat:
输出T行，每行一个数，表示在这个区间内小D喜欢的数出现了多少次。

你的输出当且仅当和标准输出一样才能得该测试点满分。


title: 矩阵

description:
给定一个整数矩阵 $A[n\times m]$，求一个矩阵 $B[n\times m]$，满足 $\forall 1\le i\le n,1\le j\le m,B_{i,j}\in[L,R]$，且使下式值最小：

$$\max\begin{cases}\displaystyle\max_{1\le j\le m}\left\{\left|\sum_{i=1}^n\left(A_{i,j}-B_{i,j}\right)\right|\right\}\\\displaystyle\max_{1\le i\le n}\left\{\left|\sum_{j=1}^m\left(A_{i,j}-B_{i,j}\right)\right|\right\}\end{cases}$$

inputFormat:
第一行两个整数 $n$，$m$，表示矩阵的大小。

接下来 $n$ 行，每行 $m$ 个整数，描述矩阵 $A$。

最后一行有两个整数 $L$，$R$。

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


title: 【模板】扩展 BSGS/exBSGS

background: 题目来源：SPOJ3105 Mod

description: 给定 $a,p,b$，求满足 $a^x≡b \pmod p$ 的最小自然数 $x$ 。

inputFormat:
每个测试文件中包含若干组测试数据，保证 $\sum \sqrt p\le 5\times 10^6$。

每组数据中，每行包含 $3$ 个正整数 $a,p,b$ 。

当 $a=p=b=0$ 时，表示测试数据读入完全。

outputFormat:
对于每组数据，输出一行。

如果无解，输出 `No Solution`，否则输出最小自然数解。

hint:
对于 $100\%$ 的数据，$1\le a,p,b≤10^9$ 或 $a=p=b=0$。

2021/5/14 加强 by [SSerxhs](https://www.luogu.com.cn/user/29826)。
2021/7/1 新添加[一组 Hack 数据](https://www.luogu.com.cn/discuss/391666)。


title: [CQOI2006] 凸多边形 /【模板】半平面交

description:
逆时针给出 $n$ 个凸多边形的顶点坐标，求它们交的面积。例如 $n=2$ 时，两个凸多边形如下图：

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

则相交部分的面积为 $5.233$。

inputFormat: 第一行有一个整数 $n$，表示凸多边形的个数，以下依次描述各个多边形。第 $i$ 个多边形的第一行包含一个整数 $m_i$，表示多边形的边数，以下 $m_i$ 行每行两个整数，逆时针给出各个顶点的坐标。

outputFormat: 输出文件仅包含一个实数，表示相交部分的面积，保留三位小数。


title: Peaks

description:
在 Bytemountains 有 $n$ 座山峰，每座山峰有他的高度 $h_i$。有些山峰之间有双向道路相连，共 $m$ 条路径，每条路径有一个困难值，这个值越大表示越难走。

现在有 $q$ 组询问，每组询问询问从点 $v$ 开始只经过困难值小于等于 $x$ 的路径所能到达的山峰中第 $k$ 高的山峰，如果无解输出 $-1$。

inputFormat:
第一行三个数 $n,m,q$。
第二行 $n$ 个数，第 $i$ 个数为 $h_i$。

接下来 $m$ 行，每行三个整数 $a,b,c$，表示从 $a \to b$ 有一条困难值为 $c$ 的双向路径。
接下来 $q$ 行，每行三个数 $v,x,k$，表示一组询问。

outputFormat: 对于每组询问，输出一个整数表示能到达的山峰中第 $k$ 高的山峰的高度。


title: 楼房重建

description:
小 A 的楼房外有一大片施工工地，工地上有 $N$ 栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。

为了简化问题，我们考虑这些事件发生在一个二维平面上。小 A 在平面上 $(0,0)$ 点的位置，第 $i$ 栋楼房可以用一条连接 $(i,0)$ 和 $(i,H_i)$ 的线段表示，其中 $H_i$ 为第 $i$ 栋楼房的高度。如果这栋楼房上存在一个高度大于 $0$ 的点与 $(0,0)$ 的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。

施工队的建造总共进行了 $M$ 天。初始时，所有楼房都还没有开始建造，它们的高度均为 $0$。在第 $i$ 天，建筑队将会将横坐标为 $X_i$ 的房屋的高度变为 $Y_i$（高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做）。请你帮小 A 数数每天在建筑队完工之后，他能看到多少栋楼房？

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

接下来 $M$ 行，每行两个正整数 $X_i,Y_i$。

outputFormat: $M$ 行，第 $i$ 行一个整数表示第 $i$ 天过后小 A 能看到的楼房有多少栋。


title: 万径人踪灭

background:
保先生是个好司机，总是开车带学生们上山玩。但是保先生去年开了最后一趟车后，由于一些奇奇怪怪的原因转行了。半年间，再也没有从这条路上山的人了。

当 VFleaKing 再次来到这座山玩的时候，发现已经没有往日的来来往往的游人了。算了，过去保先生还在的时候，来山上玩的人，也不全是来欣赏山上的风景的。

description:
如果机房马上要关门了，或者你急着要走，请直接跳到第六个自然段。

VFleaKing 注意到了这条上山下山的土路，有些地方能欣赏到美景，有些地方则不能。把上山的道路每 $10$ cm 分为一小段，则对于每一小段，用 `a` 表示能欣赏到美景，用 `b` 表示不能欣赏到美景，就能得到一个只含 `a`、`b` 的字符串 $s$。当然由于下山和上山是一条路，所以下山的道路的字符串就是将上山的道路的字符串反过来。

设上山字符串长度为 $n$，每个字符依次为 $s_1, s_2 .…, s_n$。在上山和下山的路上，VFleaKing 会选择某些小段查看旁边的景色，其他时间低头走路。即 VFleaKing 会选择 $k$ 个小段 $x_1, x_2 …x_k$，且 $k >0$，$1\le x_1<x_2<…<x_k\le n$，VFleaKing 上山和下山的过程中会在这些地方查看景色。

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

VFleaKing 希望，上山下山时看到的美景的情况相同。也就是说，VFleaKing 上山时是否看到了美景的情况是： $s_{x_1},s_{x_2},\cdots,s_{x_k}$ 记为字符序列 $T_1$，下山时是否看到了美景的情况是：$s_{x_k},s_{x_{k-1}},\cdots,s_{x_1}$ 记为字符序列 $T_2$。VFleaKing 希望 $T_1=T_2$。

VFleaKing 还希望，上山下山时查看景色的间隔相等。也就是说，上山时查看景色的间隔为：$x_2-x_1,x_3-x_2,x_k-x_{k-1}$，记为数列 $P_1$。下山时查看景色的间隔为：$x_k-x_{k-1},x_{k-1}-x_{k-2},…,x_2-x_1$，记为数列 $P_2$。VFleaKing 希望 $P_1=P_2$。

VFleaKing 觉得，如果第一次查看景色和最后一次查看景色这段时间里，没有一次低头看路他就会摔倒。也就是说，如果对于所有 $1\le i\le k$ 都有$x_i=x_1+i- 1$，VFleaKing 就会摔倒，VFleaKing不希望发生这样的情况。

就是要在一个只含 `a`、`b` 的字符串中选取一个子序列，使得:

1. 位置和字符都关于某条对称轴对称。
2. 不能是连续的一段。

以 $s = \texttt{"abaaaaabbabbabaa"}$ 为例。如果我们用符号 $[a_1, a_2,…,a_k]$ 表示一个序列，那么 $[1,4]$ 就是一个合法的序列 $x$，$[5,8,10,12,15]$ 也是，$[4,5,8,9,10,11,12,15,16]$ 也是。但是 $[1,2]$ 不满足 VFleaKing 第一个希望和第三个希望，所以不是。$[1,2,4]$ 不满足第二个希望，所以不是。$[9,10,11]$ 不满足第三个希望，所以不是。

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

给你字符串 $s$，现在 VFleaKing 想知道，有多少个合法的 $x$。答案可能很大，VFleaKing 想知道对 $1000000007$ 取模的值。

inputFormat: 一行，一个只包含 `a`、`b` 的两种字符的字符串。

outputFormat: 一行，一个非负整数表示问题的答案。


title: 千山鸟飞绝

description:
话说有一天 doyouloveme 和 vfleaking 到山里玩。谁知 doyouloveme 刚刚进山，所有的鸟儿竟被他的神犇气场给惊得全部飞走了。vfleaking 顿时膜拜不已。

这时鸟王用鸟语说道：「!@#\$%…?」，安抚了一下众鸟的情绪。鸟王生性好斗，作出了一个决定：要排鸟布阵把刚才吓到它们的人类赶出山去。

每只鸟都有一个编号，都有一个威武值。每秒钟鸟王都会发一个命令，编号为 $v$ 的鸟飞到 $(x,y)$ 去（坐标系原点是山顶，坐标单位为鸟爪）。鸟飞得很快，一秒之内就飞到了，可以看作是瞬间移动。如果编号为 $v$ 的鸟和编号为 $u$ 的鸟某一时刻处在同一位置，它们就会互相鼓励，增加各自的士气值和团结值。一只鸟的士气值等于此刻与它处在同一位置的鸟中的威武值的最大值，团结值等于此刻与它处在同一位置的鸟的只数。如果每一时刻都没有鸟与它处在同一位置，则士气值和团结值都为 $0$。要注意自己不能鼓励自己，计算士气值和团结值时不能算上自己。

$t$ 秒钟后，doyouloveme 目测出了现在每只鸟的战斗力，于是感叹了一句：「不妙，我们得走了。」

正所谓团结的鸟儿一个顶俩，所以 doyouloveme 这样描述战斗力：一只鸟战斗力值等于它在 $0$ 到 $t$ 秒中士气值的最大值与团结值的最大值的乘积。注意不是乘积的最大值，而是最大值的乘积。

vfleaking 很想知道现在每只鸟的战斗力，但是他当然不会啦，于是他把这个任务交给了你来完成。

inputFormat:
第一行一个整数 $n$，代表鸟的只数。（鸟王那家伙你可以完全忽视掉）

接下来 $n$ 行，每行三个整数 $w,x,y$ 描述每只鸟的威武值和初始坐标。第 $i+1$ 行描述编号为i的鸟。

接下来一行有一个整数 $t$，代表经过时间 $t$ 秒。

接下来 $t$ 行，每行三个整数 $v,x,y$ 描述鸟王每秒的命令。

outputFormat: 一共 $n$ 行，每行一个数，代表每只鸟的战斗力。


title: [NOI2008] 设计路线

description:
Z 国坐落于遥远而又神奇的东方半岛上，在小 Z 的统治时代公路成为这里主要的交通手段。Z 国共有 $N$ 座城市，一些城市之间由双向的公路所连接。非常神奇的是 Z 国的每个城市所处的经度都不相同，并且最多只和一个位于它东边的城市直接通过公路相连。Z 国的首都是 Z 国政治经济文化旅游的中心，每天都有成千上万的人从 Z 国的其他城市涌向首都。

为了使 Z 国的交通更加便利顺畅，小 Z 决定在 Z 国的公路系统中确定若干条规划路线，将其中的公路全部改建为铁路。

我们定义每条规划路线为一个长度大于 $1$ 的城市序列，每个城市在该序列中最多出现一次，序列中相邻的城市之间由公路直接相连（待改建为铁路）。并且，每个城市最多只能出现在一条规划路线中，也就是说，任意两条规划路线不能有公共部分。

当然在一般情况下是不可能将所有的公路修建为铁路的，因此从有些城市出发去往首都依然需要通过乘坐长途汽车，而长途汽车只往返于公路连接的相邻的城市之间，因此从某个城市出发可能需要不断地换乘长途汽车和火车才能到达首都。

我们定义一个城市的“不便利值”为从它出发到首都需要乘坐的长途汽车的次数，而 Z 国的交通系统的“不便利值”为所有城市的不便利值的最大值，很明显首都的“不便利值”为 $0$。小 Z 想知道如何确定规划路线修建铁路使得 Z 国的交通系统的“不便利值”最小，以及有多少种不同的规划路线的选择方案使得“不便利值”达到最小。当然方案总数可能非常大，小 Z 只关心这个天文数字 $\bmod\ Q$ 后的值。

注意：规划路线 $1-2-3$ 和规划路线 $3-2-1$ 是等价的，即将一条规划路线翻转，依然认为是等价的。两个方案不同当且仅当其中一个方案中存在一条规划路线不属于另一个方案。

inputFormat:
第一行包含三个正整数 $N,M,Q$，其中 $N$ 表示城市个数， $M$ 表示公路总数，$N$ 个城市从 $1 \sim N$ 编号，其中编号为 $1$ 的是首都。$Q$ 表示上文提到的设计路线的方法总数的模数。

接下来 $M$ 行，每行两个不同的整数 $a_i,b_i(1 \le a_i,b_i \le N)$，表示有一条公路连接城市 $a_i$ 和城市 $b_i$。

输入数据保证一条公路只出现一次。

outputFormat:
应包含两行。

第 $1$ 行为一个整数，表示最小的“不便利值”。

第 $2$ 行为一个整数，表示使“不便利值”达到最小时不同的设计路线的方法总数 $\bmod\ Q$ 的值。

如果某个城市无法到达首都，则输出两行 $-1$。


title: [NOI2008] 奥运物流

description:
2008 北京奥运会即将开幕，举国上下都在为这一盛事做好准备。为了高效率、 成功地举办奥运会，对物流系统进行规划是必不可少的。

物流系统由若干物流基站组成，以 1…N 进行编号。每个物流基站 i 都有且 仅有一个后继基站 Si，而可以有多个前驱基站。基站 i 中需要继续运输的物资都 将被运往后继基站 Si，显然一个物流基站的后继基站不能是其本身。编号为 1 的 物流基站称为控制基站，从任何物流基站都可将物资运往控制基站。注意 控制基 站也有后继基站，以便在需要时进行物资的流通。在物流系统中，高可靠性与低 成本是主要设计目。对于基站 i，我们定义其“可靠性” () R i 如下：
设物流基站 i 有 w 个前驱基站 P1,P2,...,Pw ，即这些基站以 i 为后继基站，则基 站 i 的可靠性 R(i)满足下式：
$$R(i)=C_i+k \sum_{j=1}^{w}R(P_j)$$

其中 Ci和 k 都是常实数且恒为正，且有 k 小于 1。

整个系统的可靠性与控制基站的可靠性正相关，我们的目标是通过修改物流 系统，即更改某些基站的后继基站，使得控制基站的可靠性 R(1)尽量大。但由于 经费限制，最多只能修改 m 个基站的后继基站，并且，控制基站的后继基站不 可被修改。因而我们所面临的问题就是，如何修改不超过 m 个基站的后继，使 得控制基站的可靠性 R(1)最大化。

inputFormat:
第一行包含两个整数与一个实数，N, m, k。其中 N 表示基 站数目，m 表示最多可修改的后继基站数目，k 分别为可靠性定义中的常数。

第二行包含 N 个整数，分别是 S1, S2…SN，即每一个基站的后继基站编号。

第三行包含 N 个正实数，分别是 C1, C2…CN，为可靠性定义中的常数。

outputFormat: 仅包含一个实数，为可得到的最大 R(1)。精确到小数点两 位。

hint:
【样例说明】
原有物流系统如左图所示，4 个物流基站的可靠性依次为 22.8571，21.4286， 25.7143，10。

最优方案为将 2 号基站的后继基站改为 1 号。

此时 4 个基站 的可靠性依次为 30，25，15，10。
本题的数据，具有如下分布：

测试数据编号|N|M
-|-|-
1|≤6|≤6
2|≤12|≤12
3|≤60|0
4|≤60|1
5|≤60|N-2
6~10|≤60|≤60

 对于所有的数据，满足 m ≤ N ≤ 60，Ci ≤ 106，0.3 ≤ k < 1，请使用双精度实 数，无需考虑由此带来的误差。


title: [NOI2008] 糖果雨

description:
有一个美丽的童话：在天空的尽头有一个"糖果国"，这里大到摩天大厦，小 到小花小草都是用糖果建造而成的。更加神奇的是，天空中飘满了五颜六色的糖 果云，很快糖果雨密密麻麻从天而落，红色的是草莓糖，黄色的是柠檬糖，绿色 的是薄荷糖，黑色的是巧克力糖……这时糖果国的小朋友们便会拿出大大小小的 口袋来接天空中落下的糖果，拿回去与朋友们一起分享。

对糖果情有独钟的小 Z 憧憬着能够来到这样一个童话的国度。所谓日有所 思，夜有所梦，这天晚上小 Z 梦见自己来到了"糖果国"。他惊喜地发现，任何时 候天空中所有的云朵颜色都不相同，不同颜色的云朵在不断地落下相应颜色的糖 果。更加有趣的是所有的云朵都在做着匀速往返运动，不妨想象天空是有边界的， 而所有的云朵恰好在两个边界之间做着往返运动。每一个单位时间云朵向左或向 右运动一个单位，当云朵的左界碰到天空的左界，它会改变方向向右运动；当云 朵完全移出了天空的右界，它会改变方向向左运动。

我们不妨把天空想象为一个平面直角坐标系，而云朵则抽象为线段(线段可 能退化为点)：

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

如上图，不妨设天空的左界为 0，右界为 len。图中共有 5 片云朵，其中标 号为 1 的云朵恰好改变方向向右运动，标号为 2 的云朵恰好改变方向向左运动。

忽略云朵的纵坐标，它们在运动过程中不会相互影响。

小 Z 发现天空中会不断出现一些云朵(某个时刻从某个初始位置开始朝某个 方向运动)，而有的云朵运动到一定时刻就会从天空中消失，而在运动的过程中 糖果在不断地下落。小 Z 决定拿很多口袋来接糖果，口袋容量是无限的，但袋 口大小却是有限的。例如在时刻 T 小 Z 拿一个横坐标范围为[L, R]的口袋来接糖 果，如果[L, R]存在一个位置 x，该位置有某种颜色的糖果落下，则认为该口袋可 接到此种颜色的糖果。极端情况下，袋口区间可能是一个点，譬如[0,0]、[1,1]，但仍然可以接到相应位置的糖果。通常可以接到的糖果总数会很大，因而小 Z 想知道每一次(即拿出口袋的一瞬间)他的口袋可以接到多少种不同颜色的糖果。

糖果下落的时间忽略不计。

inputFormat:
输入文件第一行有两个正整数 n, len，分别表示事件总数以及天空 的“边界”。

    接下来 n 行每行描述一个事件，所有的事件按照输入顺序依次发生。每行的 第一个数 k（k = 1，2，3）分别表示事件的类型，分别对应三种事件：插入事件， 询问事件以及删除事件。输入格式如下：

事件类型|输入格式|说明
-|-|-
插入事件 (天空中出现了一片 云朵)|`1 Ti Ci Li Ri Di`|时刻 Ti，天空中出现了一片 坐标范围为[Li, Ri]，颜色为 Ci的 云朵，初始的时候云朵运动方向 为向左(Di = -1)或向右(Di = 1)。满足 0 ≤ Li ≤ Ri ≤ len，Di = -1 或 1。数据保证任何时刻空中不 会出现两片颜色相同的云朵。
询问事件 (询问一个口袋可以 接到多少种不同颜 色的糖果)|`2 Ti Li Ri` |时刻 Ti，小 Z 用一个坐标范 围为[Li, Ri]的大口袋去接糖果， 询问可以接到多少种不同的糖 果。满足 0 ≤ Li ≤ Ri ≤ len。
删除事件 (天空中一片云朵消 失了)|`3 Ti Ci` |时刻 Ti，颜色为 Ci的云朵从 天空消失中。数据保证当前天空 中一定存在一片颜色为 Ci的云 朵。

outputFormat: 对于每一个询问事件，输出中应包含相应的一行，为该次询 问的答案，即口袋可以接到多少种不同的糖果。

hint:
【样例说明】

共 10 个事件，包括 3 个插入事件，5 个询问事件以及 2 个删除事件。

时刻 0，天空中出现一片颜色为 10 的云朵，初始位置为[1, 3]，方向向左。

时刻 1，范围为[0, 0]的口袋可以接到颜色为 10 的糖果(云朵位置为[0, 2])。

 时刻11，范围为[0,10]的口袋可以接到颜色为10的糖果(云朵位置为[10, 12])。
 时刻 11，范围为[0, 9]的口袋不能接到颜色为 10 的糖果(云朵位置为[10, 12])。
 时刻 11, 天空中出现一片颜色为 13 的云朵, 初始位置为[4, 7], 方向向右。

时刻 13，范围为[9, 9]的口袋可以接到颜色为 10(云朵的位置为[8, 10])和颜色 为 13(云朵的位置为[6, 9])两种不同的糖果。

时刻 13，范围为[10, 10]的口袋仅仅可以接到颜色为 10 的一种糖果(云朵的位 置为[8, 10])，而不可以接到颜色为 13 的糖果(云朵的位置为[6, 9]),。

时刻 100, 颜色为 13 的云朵从天空中消失。

时刻 1999999999，颜色为 10 的云朵从天空中消失。

时刻 2000000000，天空中又出现一片颜色为 10 的云朵，初始位置为[0, 1]， 方向向右。

【数据范围】

对于所有的数据，0 ≤ Ti ≤ 2000000000，1 ≤ Ci ≤ 1000000。

数据保证{Ti}为非递减序列即 T1 ≤ T2 ≤ … ≤ Tn-1 ≤ Tn。

对于所有的插入事件，令 Pi = Ri – Li，即 Pi表示每片云朵的长度。

数据编号|n|len|Pi|数据编号|n|len|Pi
-|-|-|-|-|-|-|-
1|20|10|≤len|6|150000|1000|≤3
2|200|100|≤len|7|200000|1000|≤3
3|2000|1000|≤len|8|100000|1000|≤len
4|100000|10|≤len|9|150000|1000|≤len
5|100000|100|≤2|10|200000|1000|≤len


title: [NOI2006] 神奇口袋

description:
Pòlya 获得了一个奇妙的口袋，上面写着人类难以理解的符号。Pòlya 看得入了迷，冥思苦想，发现了一个神奇的模型（被后人称为 Pòlya 模型)。为了生动地讲授这个神奇的模型，他带着学生们做了一个虚拟游戏：游戏开始时，袋中装入 $a_1$ 个颜色为 $1$ 的球，$a_2$ 个颜色为 $2$ 的球，……，$a_t$ 个颜色为 $t$ 的球，其中 $a_i \in \mathbb Z^+$（$1 \le i \le t$）。

游戏开始后，每次严格进行如下的操作：

从袋中随机的抽出一个小球（袋中所有小球被抽中的概率相等），Pòlya 独自观察这个小球的颜色后将其放回，然后再把 $d$ 个与其颜色相同的小球放到口袋中。

设 $c_i$ 表示第 $i$ 次抽出的小球的颜色（$1 \le C_i \le t$），一个游戏过程将会产生一个颜色序列（$c_1, c_2, \ldots, c_n, \ldots$）。Pòlya 把游戏开始时 $t$ 种颜色的小球每一种的个数 $a_1, a_2, \ldots, a_t$ 告诉了所有学生。然后他问学生：一次游戏过程产生的颜色序列满足下列条件的概率有多大？

$$c_{x_1}=y_1, c_{x_2}=y_2, \ldots, c_{x_n}=y_n$$

其中 $0 < x_1 < x_2 < \cdots < x_n$，$1 \le y_i \le t$。换句话说，已知 $(t, n, d, a_1, a_2, \ldots, a_t, x_1, y_1, x_2, y_2, \ldots, x_n, y_n)$，你要回答有多大的可能性会发生下面的事件：“对所有 $k$（$1 \le k \le n$），第 $x_k$ 次抽出的球的颜色为 $y_k$”。

inputFormat:
第一行有三个正整数 $t, n, d$；

第二行有 $t$ 个正整数 $a_1, a_2, \ldots, a_t$，表示游戏开始时口袋里 $t$ 种颜色的球，每种球的个数。

以下 $n$ 行，每行有两个正整数 $x_i, y_i$，表示第 $x_i$ 次抽出颜色为的 $y_i$ 球。

outputFormat: 要求用分数形式输出（显然此概率为有理数）。输出文件包含一行，格式为：`分子/分母`。同时要求输出最简形式（分子分母互质）。特别的，概率为 $0$ 应输出 `0/1`，概率为 $1$ 应输出 `1/1`。

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

初始时，两种颜色球数分别为 $(1, 1)$，取出色号为 $1$ 的球的概率为 $1/2$；第二次取球之前，两种颜色球数分别为 $(2, 1)$，取出色号为 $2$ 的球的概率为 $1/3$；第三次取球之前，两种颜色球数分别为 $(2, 2)$，取出色号为 $1$ 的球的概率为 $1/2$，所以三次取球的总概率为 $1/12$。

**【数据规模和约定】**

对于 $100 \%$ 的数据，$1 \le t, n \le 1000$，$1 \le a_k, d \le 10$，$1 \le x_1 < x_2 < \cdots < x_n \le 10000$，$1 \le y_k \le t$。


title: [NOI2005] 智慧珠游戏

description:
智慧珠游戏拼盘由一个三角形盘件和 12 个形态各异的零件组成。拼盘的盘 件如图 1 所示
![](https://cdn.luogu.com.cn/upload/pic/13767.png)
![](https://cdn.luogu.com.cn/upload/pic/13768.png)
![](https://cdn.luogu.com.cn/upload/pic/13769.png)
对 于 由珠子构成的零件，可以放到盘件的任一位置，条件是能有地方放，且 尺寸合适，所有的零件都允许旋转(0º、90º、180º、270º)和翻转(水平、竖直)。

现给出一个盘件的初始布局，求一种可行的智慧珠摆放方案，使所有的零件 都能放进盘件中。

inputFormat:
文件中包含初始的盘件描述，一共有 10 行，第 i 行有 i 个字符。如果第 i 行 的第 j 个字符是字母”A”至”L”中的一个，则表示第 i 行第 j 列的格子上已经放了 零件，零件的编号为对应的字母。如果第 i 行的第 j 个字符是”.”，则表示第 i 行 第 j 列的格子上没有放零件。
输入保证预放的零件已摆放在盘件中。

outputFormat:
如果能找到解，向输出文件打印 10 行，为放完全部 12 个零件后的布局。其 中，第 i 行应包含 i 个字符，第 i 行的第 j 个字符表示第 i 行第 j 列的格子上放的 是哪个零件。 如果无解，输出单独的一个字符串‘No solution’(不要引号，请注意大小写)。
 所有的数据保证最多只有一组解

samples:
B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF


title: [NOI2005] 聪聪与可可

description:
在一个魔法森林里，住着一只聪明的小猫聪聪和一只可爱的小老鼠可可。虽然灰姑娘非常喜欢她们俩，但是，聪聪终究是一只猫，而可可终究是一只老鼠，同样不变的是，聪聪成天想着要吃掉可可。

一天，聪聪意外得到了一台非常有用的机器，据说是叫 GPS，对可可能准确的定位。有了这台机器，聪聪要吃可可就易如反掌了。于是，聪聪准备马上出发，去找可可。而可怜的可可还不知道大难即将临头，仍在森林里无忧无虑的玩耍。小兔子乖乖听到这件事，马上向灰姑娘报告。灰姑娘决定尽快阻止聪聪，拯救可可，可她不知道还有没有足够的时间。

整个森林可以认为是一个无向图，图中有 $N$ 个美丽的景点，景点从 $1$ 至 $N$ 编号。小动物们都只在景点休息、玩耍。在景点之间有一些路连接。

当聪聪得到 GPS 时，可可正在景点 $M$（$M \le N$）处。以后的每个时间单位，可可都会选择去相邻的景点（可能有多个）中的一个或停留在原景点不动。而去这些地方所发生的概率是相等的。假设有 $P$ 个景点与景点 $M$ 相邻，它们分别是景点 $R$、景点 $S$、……、景点 $Q$，在时刻 $T$ 可可处在景点 $M$，则在 $(T+1)$ 时刻，可可有 $1/(1 +P)$ 的可能在景点 $R$，有 $1/(1 +P)$ 的可能在景点 $S$，……，有 $1/(1 +P)$ 的可能在景点 $Q$，还有$1/(1 +P)$的可能停在景点 $M$。

我们知道，聪聪是很聪明的，所以，当她在景点 $C$ 时，她会选一个更靠近可可的景点，如果这样的景点有多个，她会选一个标号最小的景点。由于聪聪太想吃掉可可了，如果走完第一步以后仍然没吃到可可，她还可以在本段时间内再向可可走近一步。

在每个时间单位，假设聪聪先走，可可后走。在某一时刻，若聪聪和可可位于同一个景点，则可怜的可可就被吃掉了。

灰姑娘想知道，平均情况下，聪聪几步就可能吃到可可。而你需要帮助灰姑娘尽快的找到答案。

inputFormat:
数据的第 1 行为两个整数 $N$ 和 $E$，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。

第 2 行包含两个整数 $C$ 和 $M$，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。

接下来 E 行，每行两个整数，第 $i+2$ 行的两个整数 $A_i$ 和 $B_i$ 表示景点 $A_i$ 和景点 $B_i$ 之间有一条路。所有的路都是无向的，即：如果能从 A 走到 B，就可以从 B 走到 A。

输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有路直接或间接的相连。

outputFormat: 输出 1 个实数，四舍五入保留三位小数，表示平均多少个时间单位后聪聪会把可可吃掉。

hint:
【样例说明 1】

开始时，聪聪和可可分别在景点 1 和景点 4。

第一个时刻，聪聪先走，她向更靠近可可(景点 4)的景点走动，走到景点 2， 然后走到景点 3；假定忽略走路所花时间。

可可后走，有两种可能： 第一种是走到景点 3，这样聪聪和可可到达同一个景点，可可被吃掉，步数为 $1$，概率为$0.5$。

第二种是停在景点 4，不被吃掉。概率为 $0.5$。

到第二个时刻，聪聪向更靠近可可(景点 4)的景点走动，只需要走一步即和 可可在同一景点。因此这种情况下聪聪会在两步吃掉可可。 所以平均的步数是 $1\times 1/2 + 2\times 1/2 =1.5$ 步。

【样例说明 2】

森林如下图所示：

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

对于 50%的数据，$1≤N≤50$。
对于所有的数据，$1≤N,E≤1000$。


title: [NOI2005] 月下柠檬树

description:
李哲非常非常喜欢柠檬树，特别是在静静的夜晚，当天空中有一弯明月温柔地照亮地面上的景物时，他必会悠闲地坐在他亲手植下的那棵柠檬树旁，独自思索着人生的哲理。

李哲是一个喜爱思考的孩子，当他看到在月光的照射下柠檬树投在地面上的影子是如此的清晰，马上想到了一个问题：树影的面积是多大呢？

李哲知道，直接测量面积是很难的，他想用几何的方法算，因为他对这棵柠檬树的形状了解得非常清楚，而且想好了简化的方法。

李哲将整棵柠檬树分成了 $n$ 层，由下向上依次将层编号为 $1,2,...,n$。从第 $1$ 到 $n-1$ 层，每层都是一个圆台型，第 $n$ 层(最上面一层)是圆锥型。对于圆台型， 其上下底面都是水平的圆。对于相邻的两个圆台，上层的下底面和下层的上底面重合。第 $n$ 层(最上面一层)圆锥的底面就是第 $n-1$ 层圆台的上底面。所有的底面 的圆心(包括树顶)处在同一条与地面垂直的直线上。李哲知道每一层的高度为 $h_1,h_2,...,h_n$，第 $1$ 层圆台的下底面距地面的高度为 $h_0$，以及每层的下底面的圆的半径 $r_1,r_2,...,r_n$。李哲用熟知的方法测出了月亮的光线与地面的夹角为 $\mathrm{alpha}$。

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

为了便于计算，假设月亮的光线是平行光，且地面是水平的，在计算时忽略树干所产生的影子。李哲当然会算了，但是他希望你也来练练手。

inputFormat:
第一行包含一个整数 $n$ 和一个实数 $\mathrm{alpha}$，表示柠檬树的层数和月亮 的光线与地面夹角（单位为弧度）。

第二行包含 $n+1$ 个实数 $h_0,h_1,h_2,...,h_n$ 表示树离地的高度和每层的高度。

第三行包含 $n$ 个实数 $r_1,r_2,...,r_n$ 表示柠檬树每层下底面的圆的半径。

同一行相邻的两个数之间用一个空格分隔。

输入的所有实数的小数点后可能包含一至十位有效数字。

outputFormat: 输出一个实数，表示树影的面积，四舍五入保留两位小数。


title: [SCOI2015] 情报传递

description:
奈特公司是一个巨大的情报公司，它有着庞大的情报网络。情报网络中共有 $n$ 名情报员。每名情报员可能有若干名 (可能没有) 下线，除 $1$ 名大头目外其余 $n-1$ 名情报员有且仅有 $1$ 名上线。奈特公司纪律森严，每名情报员只能与自己的上、下线联系，同时，情报网络中任意两名情报员一定能够通过情报网络传递情报。

奈特公司每天会派发以下两种任务中的一个任务：

1. 搜集情报：指派 $T$ 号情报员搜集情报；
2. 传递情报：将一条情报从 $X$ 号情报员传递给 $Y$ 号情报员。

情报员最初处于潜伏阶段，他们是相对安全的，我们认为此时所有情报员的危险值为 $0$；一旦某个情报员开始搜集情报，他的危险值就会持续增加，每天增加 $1$ 点危险值 (开始搜集情报的当天危险值仍为 $0$，第 $2$ 天危险值为 $1$，第 $3$ 天危险值为 $2$，以此类推)。传递情报并不会使情报员的危险值增加。

为了保证传递情报的过程相对安全，每条情报都有一个风险控制值 $C$。奈特公司认为，参与传递这条情报的所有情报员中，危险值大于 $C$ 的情报员将对该条情报构成威胁。现在，奈特公司希望知道，对于每个传递情报任务，参与传递的情报员有多少个，其中对该条情报构成威胁的情报员有多少个。

inputFormat:
第一行包含一个正整数 $n$，表示情报员个数。
笫二行包含 $n$ 个非负整数，其中第 $i$ 个整数 $P_i$ 表示 $i$ 号情报员上线的编号。特别地，若 $P_i=0$，表示 $i$ 号情报员是大头目。
第三行包含一个正整数 $q$，表示奈特公司将派发 $q$ 个任务 (每天一个)。

随后 $q$ 行，依次描述 $q$ 个任务。每行首先有一个正整数 $k$。

- 若 $k=1$，表示任务是传递情报，随后有三个正整数 $X_i$、$Y_i$、$C_i$，依次表示传递情报的起点、终点和风险控制值。
- 若 $k=2$，表示任务是搜集情报，随后有 $1$ 个正整数 $T_i$，表示搜集情报的情报员编号。

outputFormat: 对于每个传递情报任务输出一行，包含两个整数，分别是参与传递情报的情报员个数和对该条情报构成威胁的情报员个数。

hint:
样例解释：

对于 $3$ 个传递情报任务，都是经过 $5$ 名情报员，分别是 $4$ 号、$2$ 号、$1$ 号、$3$ 号和 $7$ 号。

- 第 $1$ 个任务，所有情报员 (危险值为 $0$) 都不对情报构成威胁；
- 第 $2$ 个任务，有 $2$ 名情报员对情报构成威胁，分别是 $1$ 号情报员 (危险值为 $3$) 和 $4$ 号情报员 (危险值为 $2$)，$7$ 号情报员 (危险值为 $1$) 并不构成威胁；
- 第 $3$ 个任务，只有 $1$ 名情报员对情报构成威胁。

数据范围：

$n\leqslant 2\times 10^5,Q\leqslant 2\times 10^5,0<P_i,C_i\leqslant N,1\leqslant T_i,X_i,Y_i\leqslant n$。


title: [JSOI2008] 最小生成树计数

description: 现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两棵最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对 $31011$ 的模就可以了。

inputFormat:
第一行包含两个数，$n$ 和 $m$，其中 $1 \le n \le 100$，$1 \le m \le 1000$，表示该无向图的节点数和边数。每个节点用 $1 \sim n$ 的整数编号。

接下来的 $m$ 行，每行包含两个整数：$a,b,c$，表示节点 $a,b$ 之间的边的权值为 $c$，其中 $1 \le c \le 10^9$。

数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过 $10$ 条。

outputFormat: 输出不同的最小生成树有多少个。你只需要输出数量对 $31011$ 的模就可以了。

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

对于全部数据，$1 \le n \le 100$，$1 \le m \le 1000$，$1\leq c_i\leq 10^9$。


title: 学习小组

description: 共有 $n$ 个学生，$m$ 个学习小组，每个学生只愿意参加其中的一些学习小组，且一个学生最多参加 $k$ 个学习小组。每个学生参加学习小组财务处都收一定的手续费，不同的学习小组有不同的手续费。若有 $a$ 个学生参加第 $i$ 个学习小组，财务处支付奖励 $C_i \times a^2$ 元。在参与学生（而不是每个学习小组的人数总和）尽量多的情况下，求财务处最少要支出多少钱。

inputFormat:
输入有若干行，第一行有三个用空格隔开的正整数 $n,m,k$。

接下来的一行有 $m$ 个正整数，表示每个 $C_i$。

第三行有 $m$ 个正整数，表示参加每个学习小组需要交的手续费 $F_i$。

再接下来有一个 $n$ 行 $m$ 列的矩阵，表若第 $i$ 行 $j$ 列的数字是 $1$，则表示第 $i$ 个学生愿意参加第 $j$ 个学习小组，若为 $0$，则为不愿意。

outputFormat: 输出只有一个整数，为最小的支出。

hint: 对于 $100\%$ 的数据，$0＜n\le 100，0＜m≤90，0＜k\le m，0＜C_i\le 10，0＜F_i\le 100。$


title: 土地划分

description: $Y$ 国有 $N$ 座城市，并且有 $M$ 条双向公路将这些城市连接起来，并且任意两个城市至少有一条路径可以互达。$Y$ 国的国王去世之后，他的两个儿子 A 和 B 都想成为新的国王，但他们都想让这个国家更加安定，不会用武力解决问题。于是他们想将这个国家分成两个小国家 A 国和 B 国。现在，A 拥有 $1$ 号城市，B 拥有 $N$ 号城市，其他的城市还尚未确定归属哪边（划分之后的国家内部城市可以不连通）。由于大家都想让国家变得更好，而某些城市的人民愿意国王的 A 儿子作为他们的领袖，而某些城市更看好 B，而为了交通的便捷，如果划分后的公路连接两个同一个国家的城市，那么更利于城市之间的交流。于是大臣们设计了一种对土地划分的评分机制，具体如下：对于城市 $i$，如果它划分给 A 国，将得到 $\mathit{VA}_i$ 的得分；划分给 B 国，将得到 $\mathit{VB}_i$ 的得分。对于一条公路 $i$，如果它连接两个 A 国的城市，将得到 $\mathit{EA}_i$ 的得分；连接两个 B 国的城市，将得到 $\mathit{EB}_i$ 的得分；否则，这条公路将失去意义，将扣除 $\mathit{EC}_i$ 的得分。现请你找到最优的土地划分，使得这种它的评分最高。

inputFormat: 第一行包含两个整数 $N$，$M$，含义如问题描述所示。接下来一行 $N-2$ 个非负整数，表示 $\mathit{VA}_2,\mathit{VA}_3,\cdots,\mathit{VA}_{N-1}$。接下来一行 $N-2$ 个非负整数，表示 $\mathit{VB}_2,\mathit{VB}_3,\cdots,\mathit{VB}_{N-1}$。接下来 $M$ 行，每行五个非负整数描述一条公路：$X,Y,\mathit{EA}_i,\mathit{EB}_i,\mathit{EC}_i$，含义如问题描述所示。

outputFormat: 输出有且仅有一个整数，表示最高评分。

hint:
对于全部数据，$n \le 10^4$，$m \le 4\times 10^4$。

保证运算过程中及最终结果不超过 $32$ 位带符号整数类型的表示范围。


title: [LNOI2014] LCA

description:
给出一个 $n$ 个节点的有根树（编号为 $0$ 到 $n-1$，根节点为 $0$）。

一个点的深度定义为这个节点到根的距离 $+1$。

设 $dep[i]$ 表示点 $i$ 的深度，$\operatorname{LCA}(i, j)$ 表示 $i$ 与 $j$ 的最近公共祖先。

有 $m$ 次询问，每次询问给出 $l, r, z$，求 $\sum_{i=l}^r dep[\operatorname{LCA}(i,z)]$ 。

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

接下来 $n-1$ 行，分别表示点 $1$ 到点 $n-1$ 的父节点编号。

接下来 $m$ 行，每行 $3$ 个整数，$l, r, z$。

outputFormat: 输出 $q$ 行，每行表示一个询问的答案。每个答案对 $201314$ 取模输出。


title: 外太空旅行

description:
在人类的触角伸向银河系的边缘之际，普通人上太空旅行已经变得稀松平常了。某理科试验班有 $n$ 个人，现在班主任要从中选出尽量多的人去参加一次太空旅行活动。
可是 $n$ 名同学并不是和平相处的。有的人，比如小 A 和小 B 整天狼狈为奸，是好朋友；但还有的人，比如（政治敏感）和（政治敏感）就水火不相容。这 $n$ 名同学，由于是理科生，都非常的理性，所以“朋友的朋友就是朋友”和“敌人的朋友就是敌人”这两句话对这些同学无效。换句话说，有可能小 A 和小 B 是朋友，小 B 和小 C 是朋友，但是小 A 和小 C 两人势如水火。
任意两个人之间要不就是敌人，要不就是朋友。
因为在太空船上发生人员斗殴事件是很恶劣也很危险的，因此选出来参加旅行活动的同学必须互相之间都是朋友。你的任务就是确定最多可以选多少人参加旅行。

inputFormat:
第一行一个整数 $n(1 \le n \le 50)$。所有的同学按照 $1 \sim n$ 编号。
接下来若干行，每行两个用空格隔开的整数 $a, b(1 \le a,b \le n)$，表示 $a$ 和 $b$ 是朋友。
注意：如果一个数对 $(x,y)$（或者 $(y,x)$）没有在文件中出现，那么编号为 $x$ 和 $y$ 的两个同学就是敌人。

outputFormat: 一个数，即最多可以选多少人参加活动。


title: 【模板】杜教筛

description:
给定一个正整数，求

$$ans_1=\sum_{i=1}^n\varphi(i)$$

$$ans_2=\sum_{i=1}^n \mu(i)$$

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

输入的第一行为一个整数，表示数据组数 $T$。

接下来 $T$ 行，每行一个整数 $n$，表示一组询问。

outputFormat: 对于每组询问，输出一行两个整数，分别代表 $ans_1$ 和 $ans_2$。

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

对于全部的测试点，保证 $1 \leq T \leq 10$，$1 \leq n \lt 2^{31}$。


title: [CERC2015] Juice Junctions

description:
你被雇佣升级一个旧果汁加工厂的橙汁运输系统。系统有管道和节点构成。每条管道都是双向的，且每条管道的流量都是 $1$ 升每秒。管道可能连接节点，每个节点最多可以连接 $3$ 条管道。节点的流量是无限的。节点用整数 $1$ 到 $n$ 来表示。在升级系统之前，你需要对现有系统进行分析。对于两个不同节点 $s$ 和 $t$，$s-t$ 的流量被定义为：当 $s$ 为源点，$t$ 为汇点，从 $s$ 能流向 $t$ 的最大流量。

以下面的第一组样例数据为例，$1-6$ 的流量为 $3$，$1-2$ 的流量为 $2$。

计算每一对满足 $a<b$ 的节点 $a-b$ 的流量的和。

inputFormat:
第一行包括 $2$ 个整数 $n$ 和 $m$（$2\leq n\leq 3\times 10^3$，$0\leq m\leq 4500$），表示节点数和管道数。

接下来 $m$ 行，每行包括两个相异整数 $a,b$（$1\leq a,b\leq n$），表示一条管道连接节点 $a,b$。

每个节点最多连接 $3$ 条管道，每对节点最多被一条管道连接。

outputFormat: 输出一个整数——每对满足 $a<b$ 的节点 $a-b$ 的流量之和。


title: 踩气球

description:
六一儿童节到了，SHUXK 被迫陪着 $m$ 个熊孩子玩一个无聊的游戏：有 $n$ 个盒子从左到右排成一排，第 $i$ 个盒子里装着 $a_i$ 个气球。

SHUxK 要进行 $Q$ 次操作，每次从某一个盒子里拿出一个没被踩爆的气球，然后熊孩子们就会立刻把它踩爆。

这 $m$ 个熊孩子每个人都指定了一个盒子区间 $[l_i,r_i]$。如果某一个时刻，一个熊孩子发现自己选定的盒子区间 $[l_i,r_i]$ 中的所有气球都已经被踩爆了，他就会非常高兴（显然之后他一直会很高兴）。

为了不辜负将自己的任务强行塞给 SHUXK 的那个人的期望，SHUXK 想向你询问：

- 他每次操作过后会有多少个熊孩子很高兴。

inputFormat:
第一行包含两个正整数 $n$ 和 $m$，分别表示盒子和熊孩子的个数。

第二行包含 $n$ 个正整数 $a_i$（$1 \le a_i \le 10^5$），表示每个盒子里气球的数量。

以下 $m$ 行每行包含两个正整数 $l_i,r_i$（$1 \le l_i \le r_i \le n$），分别表示每一个熊孩子指定的区间。

以下一行包含一个正整数 $Q$，表示 SHUXK 操作的次数。

以下 $Q$ 行每行包含一个正整数 $x$，表示这次操作是从第 $x$ 个盒子里拿气球。为了体现在线，我们对输入的 $x$ 进行了加密。

假设输入的正整数是 $\hat{x}$，那么真正的 $x=(\hat{x}+\mathit{lastans}-1)\bmod n+1$。其中 $\mathit{lastans}$ 为上一次询问的答案。对于第一个询问，$\mathit{lastans}=0$。

outputFormat: 包含 $Q$ 行，每行输出一个整数，表示 SHUXK 一次操作后询问的答案。答案的顺序应与输入数据的顺序保持一致。

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

对于全部数据，$1\le n \le 10^5$，$1\le m \le 10^5$，$1\le Q \le 10^5$。

输入数据保证 $1 \le \hat{x} \le 10^9$，且第 $x$ 个盒子中有尚未被踩爆的气球。


title: Hash?

background:
**zhoutb2333**学习了哈希算法，他于是去统计给定一些字符串，其中有多少个本质不同的字符串。

但是**zhoutb2333**突发奇想，如果哈希采用的$base$每次随机，那么结果会变成什么样呢？

**辣鸡出题人又出锅了！subtask3的数据有问题，现在统一将模数改为65537**

题目来源：[zhoutb2333](https://www.luogu.org/space/show?uid=31564)

description:
他通过某种办法，获得了一个函数:$int \ Rand(int  \ x)$，它会等概率地返回一个$[0,x)$中的整数。

他写下了这样的代码：
``` cpp
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int x=10,maxn=35,maxlen=16010;
ll HASH[maxn];
const ll p=65537;
char str[maxlen];
ll Hash(){
    int base=Rand(x);
    ll ret=0;
    for(int i=1;str[i];i++)
        ret=(ret*base+str[i]-'a'+1)%p;
    return ret;
}
int main(){
    int ans=0,n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s",str+1),HASH[i]=Hash();
    sort(HASH+1,HASH+n+1);
    HASH[0]=-1;
    for(int i=1;i<=n;i++)
        ans+=(HASH[i]!=HASH[i-1]);
    printf("%d\n",ans);
    return 0;
}
```
**zhoutb2333**想问你，给定一些字符串和参数$x$，答案$ans$的期望是多少呢？

$65537= 2^{16}+1$**是质数**

**参数$x$在这个程序中是确定的$10$，但是每次输入会给定。**

inputFormat:
第一行三个整数$x,N$，表示$base$生成的参数和字符串的个数

接下来$N$行每行一个字符串，字符串仅由小写字母组成。

outputFormat:
一行一个小数，表示答案$ans$的期望，**模$65537$输出**。

即：如果你的答案为$\frac{q}{p}$（$gcd(p,q)=1$），那么输出使得$px \equiv q \ (mod \ 65537$的最小正整数$x$。可以证明答案$ans$一定为正有理数，并且这样的$x$一定存在。

hint:
本题由$3$个$subtask$组成，设$M$为这$N$个字符串中，每个字符串长度的最大值。

对于$subtask \ 1$：$1 \le N \le 8 , M \le 10,x \le 4$，分值为$20$，时间限制为$1s$。

对于$subtask \ 2$：$1 \le N \le 30 , M \le 500,x \le 500$，分值为$50$，时间限制为$1s$。

对于$subtask \ 3$：$1 \le N \le 5 , M \le 16000,x \le 16000$，分值为$30$，时间限制为$4.5s$。

**样例#1解释：**

参数$x=2$，那么可能的哈希$base$为$0,1$。

如果哈希第一个`aa`采用的$base$和第二个`aa`的$base$相同，那么答案为$1$。

如果两个$base$不相同，那么答案为$2$。

分析发现这两种情况发生的概率相同，都是$\frac{1}{2}$，那么答案$ans$的期望为$1 * \frac{1}{2} + 2 * \frac{1}{2}=\frac{3}{2}$。使得$2x \equiv 3 \ (mod \ 65537)$的最小正整数$x$为$32770$。

**样例#2解释：**

求得答案为$\frac{53}{9}$。使得$9x \equiv 53 \ (mod \ 65537)$的最小正整数$x$为$58261$。

**注意：本题允许手动开$O2$优化以避免被卡常数，方法如下：**
``` cpp
%:pragma GCC optimize(2)
/*程序*/
```


title: [CTSC2010] 产品销售

description:
A 公司正在热销某计算机产品，作为 A 公司 CEO 的小 A 打算为接下来连续的 $N$ 个销售季度制定一份具体的生产和销售方案。 已知第 $i$ 个销售季度该产品的订购量为 $D_i$，在第 $i$ 个季度，A 公司会通过如下几种方式来解决用户的订购需求：

○ 在第 $i$ 个季度生产新的产品来销售。

○ 若在第 $i$ 个季度以前库存还有多余的产品，则可以直接在第 $i$ 个季度销售(注意第一个季度之前没有任何库存产品)。

○ 在第 $i$ 个季度可以不完成全部的订购需求，而将未完成的订购需求推迟，归入到下一个季度$(i + 1)$的产品订购需求中。

A 公司需要考虑以下几种耗费： 生产新产品的成本耗费、库存产品的额外储存耗费以及推迟订购需求而需要赔偿给用户的损失费。另外由于劳力和资源的限制，每个销售季度能够生产新产品的数量是有限的，各季度的耗费和可以生产的产品上限数也不尽相同，具体如下：

○ 在第 $i$ 个季度最多可以生产 $U_i$ 件新的产品，每一件的成本为 $P_i$。

○ 第 $i$ 个季度保存下来的产品，可以用于以后季度的销售。对于每一件产品，若从第 $i$ 季度保存到第 $i + 1$ 季度， 需要额外支付 $M_i$ 的存储费用(注意产品保存到下个季度后可能再次库存)。

○ 对于第 $i$ 个季度需要推迟而归入到下一个季度订购需求的每一件产品， A
公司需要赔偿给用户损失费 $C_i$(注意延迟到下个季度可能再次被延迟, 费
用按后面季度的延迟费用计)。

在第 $N$ 个季度结束后， A 公司必须解决之前所有的用户订单。可以保证， A公司能够生产的产品总数不会低于总订购量， 也就是说一定存在一组生产和销售方案使得满足所有的用户订购需求。小 A 想知道如何来安排产品的生产和销售，使得在满足所有订购需求的前提下公司总的耗费最小。

inputFormat:
输入文件 $\tt{product.in}$ 第一行是一个正整数 $N$，表示有 $N$ 个销售季度。

第二行有 $N$ 个非负整数 $D_1$, $D_2$, .., $D_N$，表示第 $i$ 个季度的订购量。

第三行有 $N$ 个非负整数 $U_1$, $U_2$, .., $U_N$，表示第 $i$ 个季度最多可以生产的新的产品数。

第四行有 $N$ 个非负整数 $P_1$, $P_2$, .., $P_N$，表示第 $i$ 个季度生产一件新产品的成本。

第五行有 $N - 1$ 个非负整数 $M_1$, $M_2$, ..,$M_{N-1}$，表示将一件产品从第 $i$ 个季度保存到第 $i +1$ 个季度所需要的额外的耗费。

第六行有 $N-1$ 个非负整数 $C_1$, $C_2$, .., $C_{N-1}$，表示一件产品的订购需求在第 $i$ 个季度没有完成而归入到第 $i +1$ 个季度的订购量中，需要赔偿给用户的损失费。

outputFormat: 输出文件 $\tt{product.out}$ 仅包含一个非负整数，表示公司的最小总耗费。

hint:
【样例说明】

第一个季度生产 $2$ 件产品，第二个季度生产 $5$ 件产品，第三个季度不生产产品，第四个季度生产 $1$ 件产品，成本为 $2 * 5 + 5 * 1 + 0 * 5 + 1 * 5 = 20$。

因为第一个季度最多只能生产 $2$ 件产品，无法满足 $3$ 件的订购量，因此将 $1$件产品的订购量推迟到第二个季度，赔偿给用户的损失费为 $5$。

第二个季度由于第一个季度推迟了一件产品的订购需求， 因而订购量变为 $3$。该季度生产了 $5$ 件产品，剩下的 $2$ 件保存下来。第三个季度直接销售库存的产品，再多出来的 $1$ 件产品继续储存到第四个季度，加上第四个季度生产了 $1$ 件产品，因此满足了所有订单需求。总的储存费用为 $2 * 2 + 1 * 1 = 5$。

总的费用为 $20 + 5 + 5 = 30$。

【数据规模】

对于 $30\%$的数据， $N \leq 1,000$。

对于 $100\%$的数据， $1 \leq N \leq 100,000$， $1 \leq D_i, U_i, P_i, M_i,C_i \leq  10,000$。


title: [CTSC2010] 珠宝商

description:
Louis.PS 是一名精明的珠宝商，他出售的项链构造独特，很大程度上是因为他的制作方法与众不同。每次 Louis.PS 到达某个国家后，他会选择一条路径去遍历该国的城市。在到达一个城市后，他会使用在这个城市流行的材料制作一颗珠子，并按照城市被访问的顺序将珠子串联做成项链，为了使制作出来的项链不会因为城市之间的竞争而影响销量，路径中同一个城市不会重复出现（因为如果项链中 $A$ 城市的材料比 $B$ 城市的材料使用的多，则项链在 $B$ 城市的宣传可能会受到影响）。经过多年对消费者的调查，Louis.PS 已经掌握了判断一条项链吸引消费者程度的方法，具体来说，Louis.PS 经过调查得出了受消费者欢迎的项链的特征，并基于此制作了一个长项链（Louis.PS 称之为特征项链）。对于一条待售的项链，这条项链在特征项链里出现的次数越多，这条项链就越受消费者欢迎。

考虑到现实情况的复杂性，我们对条件做出适当的简化。对于每个国家，在某些城市间存在道路直接相连，对于两个不同的城市，有且仅有一条路径连接这两个城市（即国家是连通的，且不存在一个环）。对于每个城市，我们用一个小写字母来表示在这个城市流行的材料类型。这样，我们就可以用一个仅包含小写字母的字符串来表示一条项链，我们将特征项链所对应的字符串称作特征字符串，设为 $\mathit{EigenString}[1\ldots M]$，$M$ 为特征项链的长度。对于一条项链，假设其对应字符串为 $P[1\ldots L]$，$L$ 为这条项链的长度。如果存在一个正整数 $K$，使 $\mathit{EigenString}[K\ldots K+L-1]=P[1\ldots L]$，称这条项链在特征项链中出现了一次。满足上述条件的正整数 $K$ 的个数即为这条项链在特征项链的出现次数，记为 $\mathit{Popularity}(P)$。

Louis.PS 使用数学中的期望概念来评价一个国家是否适合珠宝的采集,对于一个包含 $N$ 个城市的国家，令 $\mathit{Str}_{u,v}$ 表示沿着从 $u$ 开始,至 $v$ 结束的路径所得到的项链的对应字符串。（$\mathit{Str}_{u,v}$ 与 $\mathit{Str}_{v,u}$ 表示的串一般不相同），则

$$
\mathit{Expectation}=\frac{\sum_{u,v}{\mathit{Popularity}(\mathit{Str}_{u,v})}}{N^2}
$$

对于如下的例子（图中实线表示两端点的国家有直接道路相连）：

$N=3$，所流行的材料类型分别为 $\tt{a,a,b}$。

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

$$
\mathit{Expectation}=\frac{3+1+2+1+3+1+1+1+2}{9}=\frac53
$$

对于一个国家，Louis.PS 想知道其 $\mathit{Expectation}$ 的值，但苦于计算期望的工作量太大。作为珠宝店的学徒，你当然不愿放过难得在老板面前展示自己的机会。

inputFormat:
输入第一行包含两个整数 $N,M$，表示城市个数及特征项链长度。

接下来的 $N-1$ 行，每行两个整数 $x,y$，表示城市 $x$ 与城市 $y$ 有直接道路相连。城市由 $1\sim N$ 进行编号。

接下来的一行，包含一个长度为 $N$，仅包含小写字母的字符串，第 $i$ 位的字符表示在城市 $i$ 流行的原料类型。

最后一行，包含一个长度为 $M$，仅包含小写字母的字符串， 表示特征字符串。


title: [BJOI2014] 大融合

description:
小强要在 $N$ 个孤立的星球上建立起一套通信系统。这套通信系统就是连接 $N$ 个点的一个树。

这个树的边是一条一条添加上去的。

在某个时刻，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。

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

例如，在上图中，现在一共有了 $5$ 条边。其中，$(3,8)$ 这条边的负载是 $6$，因为有六条简单路径 $2-3-8$,$2-3-8-7$,$3-8,3-8-7$,$4-3-8$,$4-3-8-7$ 路过了 $(3,8)$。

现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。

inputFormat:
第一行包含两个整数  $N, Q$,表示星球的数量和操作的数量。星球从 $1$ 开始编号。

接下来的 $Q$  行，每行是如下两种格式之一：

 - ```A x y``` 表示在 $x$ 和 $y$ 之间连一条边。保证之前 $x$ 和 $y$ 是不联通的。
 - ```Q x y```表示询问 $(x,y)$ 这条边上的负载。保证 $x$ 和 $y$ 之间有一条边。

outputFormat: 对每个查询操作，输出被查询的边的负载。


title: [CSP-S 2022] 策略游戏

description:
小 L 和小 Q 在玩一个策略游戏。

有一个长度为 $n$ 的数组 $A$ 和一个长度为 $m$ 的数组 $B$，在此基础上定义一个大小为 $n \times m$ 的矩阵 $C$，满足 $C_{i j} = A_i \times B_j$。所有下标均从 $1$ 开始。

游戏一共会进行 $q$ 轮，在每一轮游戏中，会事先给出 $4$ 个参数 $l_1, r_1, l_2, r_2$，满足 $1 \le l_1 \le r_1 \le n$、$1 \le l_2 \le r_2 \le m$。

游戏中，小 L 先选择一个 $l_1 \sim r_1$ 之间的下标 $x$，然后小 Q 选择一个 $l_2 \sim r_2$ 之间的下标 $y$。定义这一轮游戏中二人的得分是 $C_{x y}$。

小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。

请问：按照二人的最优策略，每轮游戏的得分分别是多少？

inputFormat:
第一行输入三个正整数 $n, m, q$，分别表示数组 $A$，数组 $B$ 的长度和游戏轮数。

第二行：$n$ 个整数，表示 $A_i$，分别表示数组 $A$ 的元素。

第三行：$m$ 个整数，表示 $B_i$，分别表示数组 $B$ 的元素。

接下来 $q$ 行，每行四个正整数，表示这一次游戏的 $l_1, r_1, l_2, r_2$。

outputFormat: 输出共 $q$ 行，每行一个整数，分别表示每一轮游戏中，小 L 和小 Q 在最优策略下的得分。


title: [USACO22DEC] Barn Tree S

description:
Farmer John 的农场有 $N$ 个牛棚 $(2 \le N \le 2 \times 10^5)$，编号为 $1 \cdots N$。有 $N−1$ 条道路，每条道路连接两个牛棚，并且从任一牛棚均可通过一些道路到达任一其他牛棚。目前，第 $j$ 个牛棚中有 $h_j$ 个干草捆 $(1 \le h_j \le 10^9)$。

为使他的奶牛们满意，Farmer John 想移动这些干草，使得每个牛棚都有相同数量的干草捆。他可以选择任何一对由一条道路连接的牛棚，并命令他的农场工人将不超过第一个牛棚中干草捆数量的任意正整数个干草捆从第一个牛棚移动到第二个牛棚。

请求出一个 Farmer John 可以发出的命令序列，以尽可能少的命令数完成这一任务。输入保证存在符合要求的命令序列。

inputFormat:
输入的第一行包含整数 $N$。

第二行包含空格分隔的整数 $h_j$，其中 $j=1\cdots N$。

最后 $N−1$ 行每行包含两个空格分隔的牛棚编号 $u_i,v_i$，表示有一条双向道路连接 $u_i$ 和 $v_i$。

outputFormat:
输出命令的最小数量，然后输出该数量的命令序列，每行输出一条命令。

每条命令的格式应为三个空格分隔的正整数：出发牛棚，目标牛棚，以及从出发牛棚移动到目标牛棚的干草捆数量。

如果有多组解，输出任意一组。

hint:
### 样例 1 解释

在这个例子中，共有十二个干草捆和四个牛棚，这意味着每个牛棚最后必须有三个干草捆。输出样例中的命令顺序可以用以下的自然语言表述：

1. 从牛棚 $3$ 到牛棚 $2$，移动 $1$ 个干草捆。
2. 从牛棚 $4$ 到牛棚 $2$，移动 $2$ 个干草捆。
3. 从牛棚 $2$ 到牛棚 $1$，移动 $1$ 个干草捆。

### 测试点性质

- 测试点 $2-8$ 满足 $N \le 5000$。
- 测试点 $7-10$ 满足 $v_i=u_i+1$。
- 测试点 $11-16$ 没有额外限制。


title: [USACO22DEC] Circular Barn S

description:
Farmer John 和他的死对头 Farmer Nhoj 在一个环形牛棚内玩游戏。牛棚内有 $N(1 \le N \le 10^5)$ 个房间，第 $i$ 个房间初始时内有 $a_i$ 头奶牛 $(1 \le a_i \le 5 \times 10^6)$。游戏玩法如下：

- 两位农夫将总是在同一个房间里。进入一个房间后，每位农夫各执行一次行动，Farmer John 在先。两位农夫在游戏开始时进入房间 $1$。
- 如果当前房间中的奶牛数量为零，则此时执行行动的农夫即失败。否则，执行行动的农夫选择一个整数 $P$，其中 $P$ 为 $1$ 或一个不超过当前房间中奶牛的数量的质数，并从当前房间中移除 $P$ 头奶牛。
- 两位农夫均完成行动之后，两位农夫移动到环形牛棚的下一间房间。也就是说，如果农夫们在房间 $i$，那么他们会移动到房间 $i+1$，除非他们在房间 $N$，在这种情况下他们会移动到房间 $1$。

当两位农夫均采用最优策略时，求获胜的农夫。

inputFormat:
输入包含 $T$ 个子测试用例。输入的第一行包含 $T(1 \le T \le 1000)$。下面是 $T$ 个子测试用例。

每个子测试用例的第一行包含 $N$，第二行包含 $a_1, \cdots ,a_N$。

输入保证所有 $N$ 之和不超过 $2 \times 10^5$。

outputFormat: 对于每一个子测试用例，输出获胜的农夫，为 `Farmer John` 或 `Farmer Nhoj` 之一。

samples:
Farmer Nhoj
Farmer John
Farmer John
Farmer John
Farmer Nhoj

hint:
### 样例 1 解释

对于第一个子测试用例，Farmer John 可以从第一个房间中移除 $1$、$2$ 或 $3$ 头奶牛。无论他移除多少头奶牛，Nhoj 都可以移除剩余的奶牛，迫使 FJ 在他们绕回第一个房间时失败。

对于第二个子测试用例，FJ 可以移除 $5$ 头奶牛，迫使 Nhoj 面对剩下的 $4$ 头奶牛。现在，Nhoj 可以移除 $1$、$2$ 或 $3$ 奶牛。现在的情况类似于第一个子测试用例。

对于第三个和第四个子测试用例，FJ 可以立即移除第一个房间的所有奶牛，使 Nhoj 失败。

对于第五个子测试用例，FJ 可以从第一个房间中移除 $1$
、$2$ 或 $3$ 奶牛，然后 Nhoj 可以随后移除余下的奶牛。当他们绕回第一个房间时，FJ 将会失败。

### 测试点性质

- 测试点 $2-4$ 满足 $N=1$。
- 测试点 $1,2,5-7$ 满足 $a_i \le 1000$。
- 测试点 $8-20$ 没有额外限制。


title: [USACO22DEC] Range Reconstruction S

description: Bessie 有一个数组 $a_1, \cdots, a_N$，其中 $1 \le N \le 300$ 并对于所有 $i$ 有 $0 \le a_i \le 10^9$。她不会告诉你数组 $a$ 本身，但她会告诉你 $a$ 的每个子数组的全距。也就是说，对于每对索引 $i \le j$，Bessie 告诉你 $r_{i,j}= \max a[i \cdots j]− \min a[i \cdots j]$。给定这些 $r$ 的值，构造一个可以作为 Bessie 的原始数组的数组。你的数组中的数值应在 $[−10^9,10^9]$ 范围内。

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

以下 $N$ 行，第 $i$ 行包含整数 $r_{i,i},r_{i,i+1}, \cdots ,r_{i,N}$。

输入保证存在某个数组 $a$，其中的数值在 $[0,10^9]$ 范围内，满足对于所有的 $i \le j$，有 $r_{i,j}= \max a[i \cdots j]−\min a[i\cdots j]$。

outputFormat: 输出一行，包含 $N$ 个整数 $b_1,b_2, \cdots ,b_N$，在 $[−10^9,10^9]$ 范围内，表示你的数组。这些数需要满足对于所有的 $i \le j$ 有 $r_{i,j}= \max a[i \cdots j]−\min a[i\cdots j]$。

hint:
### 样例 1 解释

例如，$r_{1,3}=\max a[1 \cdots 3]−\min a[1\cdots 3]=3−1=2$。

### 样例 2 解释

这个样例满足子任务 $1$ 的限制。

### 样例 3 解释

这个样例满足子任务 2 的限制。

### 测试点性质

- 测试点 $5$ 满足 $r_{1,N} \le 1$。
- 测试点 $6-8$ 满足对于所有 $1 \le i<N$ 均有 $r_{i,i+1}=1$。
- 测试点 $9-14$ 没有额外限制。


title: [CSP-S 2022] 数据传输

background: **请勿滥用本题评测，违者可能处以封号处罚。**

description:
小 C 正在设计计算机网络中的路由系统。

测试用的网络总共有 $n$ 台主机，依次编号为 $1 \sim n$。这 $n$ 台主机之间由 $n - 1$ 根网线连接，第 $i$ 条网线连接个主机 $a_i$ 和 $b_i$。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率，主机 $a$ 能够直接将信息传输给主机 $b$ 当且仅当两个主机在可以通过不超过 $k$ 根网线直接或者间接的相连。

在计算机网络中，数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机 $a$ 传输到主机 $b$（$a \neq b$），则其会选择出若干台用于传输的主机 $c_1 = a, c_2, \ldots, c_{m - 1}, c_m = b$，并按照如下规则转发：对于所有的 $1 \le i < m$，主机 $c_i$ 将信息直接发送给 $c_{i + 1}$。

每台主机处理信息都需要一定的时间，第 $i$ 台主机处理信息需要 $v_i$ 单位的时间。数据在网络中的传输非常迅速，因此传输的时间可以忽略不计。据此，上述传输过程花费的时间为 $\sum_{i = 1}^{m} v_{c_i}$。

现在总共有 $q$ 次数据发送请求，第 $i$ 次请求会从主机 $s_i$ 发送数据到主机 $t_i$。小 C 想要知道，对于每一次请求至少需要花费多少单位时间才能完成传输。

inputFormat:
输入的第一行包含三个正整数 $n, Q, k$，分别表示网络主机个数，请求个数，传输参数。数据保证 $1 \le n \le 2 \times {10}^5$，$1 \le Q \le 2 \times {10}^5$，$1 \le k \le 3$。

输入的第二行包含 $n$ 个正整数，第 $i$ 个正整数表示 $v_i$，保证 $1 \le v_i \le {10}^9$。

接下来 $n - 1$ 行，第 $i$ 行包含两个正整数 $a_i, b_i$，表示一条连接主机 $a_i, b_i$ 的网线。保证 $1 \le a_i, b_i \le n$。

接下来 $Q$ 行，第 $i$ 行包含两个正整数 $s_i, t_i$，表示一次从主机 $s_i$ 发送数据到主机 $t_i$ 的请求。保证 $1 \le s_i, t_i \le n$，$s_i \ne t_i$。

outputFormat: $Q$ 行，每行一个正整数，表示第 $i$ 次请求在传输的时候至少需要花费多少单位的时间。


title: [WC2018] 通道

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

description:
11328 年，C 国的科学家们研发了一种高速传送通道，可以在很短的时间内把居民从通道的一端送往另一端，这些通道都是双向的。

美中不足的是，这种传送通道需要进行大量的维护和检修。经过规划，C 国总统决定在 M 城中新建这种通道，在 M 城中，建立了 $n$ 个传送站和 $3\times(n-1)$ 条传送通道，这些传送通道被分为 $3$ 组，每一组都包含了 $(n-1)$ 条通道。

当任意一组通道运行时，居民都可以通过这组通道从任意一个传送站前往任意的另一个传送站。也就是说，所有的传送站都会被通道所连通。

三组通道按照 $1$、 $2$、 $3$ 的顺序轮流运行，循环反复。在任意一个时刻，都有且只有一组传送通道可以使用。形式化地，在第 $i$ 天中，有且只有第 $((i-1)\bmod 3+1)$ 组通道运行。

C 国著名科学家 Access Globe 正在进行一项社会调查实验：调查两个传送站之间的传送通道使用者的信息。 Access Globe 的计划是这样的：

- 选定两个传送站 $a, b$
- 第一天，他从 $a$ 出发，使用正在运行的这组通道沿最短路径到达 $b$，并调查经过的所有通道上使用者的信息
- 第二天，他从 $b$ 出发，使用正在运行的这组通道沿最短路径到达 $a$，并调查经过的所有通道上使用者的信息
- 第三天，他从 $a$ 出发，使用正在运行的这组通道沿最短路径到达 $b$，并调查经过的所有通道上使用者的信息

Access Globe 知道每一条传输线路在运行时的使用者人数。他希望找出一对 $a, b$，使得在整个实验过程中所有经过的通道的使用者数量之和最大。

Access Globe 希望参加 CCF NOI 2018 冬令营的你帮他解决这个简单的小问题。如果你成功地解决了这个问题， Access Globe 会送你一份小礼物——$100$ 分！

inputFormat:
输入文件的第 $1$ 行包含一个正整数 $n$，表示传送站的个数，传送站从 $1$ 到 $n$ 编号；

输入文件的第 $2$ 到第 $n$ 行，每行包含 $3$ 个数 $u,v,w$，表示第一组通道中有一条连接 $u,v$ 的通道，其运行时使用者数量为 $w$ 人；

输入文件的第 $(n+1)$ 到第 $(2n-1)$ 行，每行包含 $3$ 个数 $u,v,w$，表示第二组通道中有一条连接 $u,v$ 的通道，其运行时使用者数量为 $w$ 人；

输入文件的第 $2n$ 到第 $(3n-2)$ 行，每行包含 $3$ 个数 $u,v,w$，表示第三组通道中有一条连接 $u,v$ 的通道，其运行时使用者数量为 $w$ 人。

outputFormat: 输出文件共 $1$ 行，包含一个整数，表示最大的使用者数量之和。

hint:
【样例$1$说明】

下图为样例中 $M$ 城的传送站和传输线路情况。其中点和虚线交替的线条、虚线条和实线条分别表示第一组、第二组和第三组通道。
![QQ20180209195844.png](https://www.z4a.net/images/2018/02/09/QQ20180209195844.png)
一种可行的方案是选择 $a=2,b=5$，这样的使用者数量之和为 $(3)+(8+5+1)+(2+1+7)=27$。

【子任务】

对于所有数据， $2 \leq n \leq 10^5,0 \leq w \leq 10^{12}$。

特殊性质 $0$：任意两组通道构成完全相同。

特殊性质 $1$：第二组通道和第三组通道构成完全相同。

特殊性质 $2$：对于第二组的每一个传送站，最多只有两个通道可以到达它，且编号为 $x,y$ 的传送站之间通过一条通道直接连接充要条件是 $|x-y|=1$。

特殊性质 $3$：对于第三组的每一个传送站，最多只有两个通道可以到达它。

特殊性质 $4$： $n \leq 3000$。

![QQ20180209201418.png](https://www.z4a.net/images/2018/02/09/QQ20180209201418.png)
本题共 $31$ 个测试点，每个子任务对应测试点如下：

- 子任务 $0$ 对应测试点 $1-7$；
- 子任务 $1$ 对应测试点 $8$；
- 子任务 $2$ 对应测试点 $9-11$；
- 子任务 $3$ 对应测试点 $12-14$；
- 子任务 $4$ 对应测试点 $15-17$；
- 子任务 $5$ 对应测试点 $18-21$；
- 子任务 $6$ 对应测试点 $22-25$；
- 子任务 $7$ 对应测试点 $26-31$；

【提示】

- 在两组通道中，可能都包含了连接传送站 $x,y$ 的通道，此时我们认为这两条通道是不同的。
- 特殊性质中，A 组通道和 B 组通道的『构成完全相同』是指：如果在 A 组中 $u,v$ 之间存在一条使用人数为 $w$ 的通道，那么在 B 组中 $u,v$ 之间一定也存在一条使用人数为 $w$ 的通道。是否相同与描述方式与描述顺序均无关。即在构成完全相同的两组通道 A 和 B 中，通道输入的顺序不一定相同，每条通道的端点的输入顺序也不一定相同（对于 A、B 组中一条连接 $u,v$ 的使用人数为 $w$ 的通道，一种可能出现的输入为： A 组通道中输入 $u\ v\ w$，而 B 组通道中输入 $v\ u\ w$）。


title: [WC2018] 州区划分

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

description:
小 S 现在拥有 $n$ 座城市，第 $i$ 座城市的人口为 $w_i$，城市与城市之间可能有双向道路相连。

现在小 S 要将这 $n$ 座城市划分成若干个州，每个州由至少一个城市组成，每个城市在恰好一个州内。

假设小 S 将这些城市划分成了 $k$ 个州，设 $V_i$ 是第 $i$ 个州包含的所有城市组成的集合。定义一条道路是一个州的内部道路，当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同，不经过任何不属于这个州的城市，且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径（路径长度可以为 $0$），则称这个州是不合法的。

定义第 $i$ 个州的满意度为：第 $i$ 个州的人口在前 $i$ 个州的人口中所占比例的 $p$ 次幂，即：

$$\left(\dfrac{\sum _ {x \in V _ i} w _ x}{\sum _ {j = 1} ^ i \sum _ {x \in V _ j} w _ x}\right) ^ p$$

定义一个划分的满意度为所有州的满意度的乘积。

求所有合法的划分方案的满意度之和。

答案对 $998244353$ 取模。
两个划分 $\{V_1, V _ 2, \cdots, V_k\}$ 和 $\{C_1, C _ 2, \cdots, C_s\}$ 是不同的，当且仅当 $k \neq s$，或存在某个 $1 \leq i \leq k$，使得 $V_i \neq C_i$。

inputFormat:
输入第一行包含三个整数 $n,m,p$，表示城市个数、城市之间的道路个数以及题目描述中的常数 $p$。

接下来 $m$ 行，每行两个正整数 $u,v$，描述一条无向的道路，保证无重边无自环。

输入第 $m+2$ 行有 $n$ 个正整数，第 $i$ 个正整数表示 $w_i$。

outputFormat:
输出一行一个整数表示答案在模 $998244353$ 意义下的取值。

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

hint:
【提示】

$x^{p-1} \equiv 1 \pmod p$，其中 $p$ 为质数， $x \in [1,p)$。

保证对于所有数据有：$0 \leq n \leq 21$， $0 \leq m \leq \dfrac{n\times (n-1)}{2}$ ， $0 \leq p \leq 2$， $1 \leq w_i \leq 100$。


title: [清华集训2017] 简单数据结构

description:
参加完IOI2018之后就是姚班面试。而你，由于讨厌物理、并且想成为乔布斯一样的创业家，被成功踢回贵系。

转眼，时间的指针被指向2019，大二，12月初，考试周。

你早听学长说，数据结构期中考很难，对竞赛生不友好，集训队选手做不完卷子。

你冷笑。哼，堂堂国际金，这点难度的考试算什么。

两小时，你看完习题解析前五章所有内容，并且倒背如流；

一小时，你看了500页的讲义，并且记忆犹新；

十分钟，你骑车到考场，自信的你只带了一把水笔，虽然考试让带资料；

现在，摊开传说中神级卷子，你定神一看——

给出一个长度为 $N$ 的序列 $A_1,A_2,\cdots,A_N$，如果 $A$ 中的一个子序列         $B_1,B_2,\cdots,B_M$，满足条件：

$1 \le M \le N$

∀$1 \le i \le M$，$B_i$|$B_{i+1}$

那么称 $B$ 为 $A$ 的上升倍数子序列。

现在有一个长度为 $N$ 的序列 $A$ 被初始化为 $A_{1},A_{2},\cdots,A_{N}$，以及 $Q$ 次对序列 $A$ 的操作。此处要求实现如下四种操作：

0 x：在序列 $A$ 的最左端插入一个数字 $x$；

1 x：在序列 $A$ 的最右端插入一个数字 $x$；

2：移除序列 $A$ 最左端的一个数字；

3：移除序列 $A$ 最右端的一个数字；

在初始化序列 $A$ 和每次操作之后，请计算此时序列 $A$ 中最长上升倍数子序列的长度 $\mathrm{MaxLen}$，以及所有长度为 $\mathrm{MaxLen}$ 的上升倍数子序列的不同的开头数 $\mathrm{Cnt}$，输出 $\mathrm{MaxLen}$ 和 $\mathrm{Cnt}$。

为了大幅度降低题目难度，保证在任意时刻序列 $A$ 非空，其中的元素互不相等，并且均为 $1\sim M$ 之间的正整数；同一个数字最多只会被插入 $C$ 次。

inputFormat:
输入第一行包含三个正整数 $N,M,Q$，具体含义见上，保证 $1\le N \le 10^5$，$N \le M \le 10^6$，$0\le Q \le 10^5$；

输入第二行包含 $N$ 个正整数，为 $A_1,A_2,\cdots,A_N$，保证 $1\le A_i\le M$，并且序列 $A$ 中的元素互不相等；

接下来共 $Q$ 行输入，每行输入格式形如0 x或者1 x或者2或者3，具体含义见上。

outputFormat: 输出共 $Q+1$ 行，在初始化和每次对序列 $A$ 操作后，输出 $A$ 中最长上升倍数子序列的长度 $\mathrm{MaxLen}$ 和所有长度为 $\mathrm{MaxLen}$ 的上升倍数子序列的不同的开头数 $\mathrm{Cnt}$，用一个空格隔开。

hint:
**样例解释**

表格中以//隔开不同开头的最长上升子序列。

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

对于所有的数据，有 $1\le N \le 10^5$，$N\le M \le 10^6$，$0\le Q \le 10^5$，$1\le A_i\le M$，$C=10$。

下表展示了某些数据点的一些特殊约束，其中只有1表示只有形如1 x的操作，其他表述同理。

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

后记

“奋战两小时，考个四五十”的表情包占领了你的朋友圈：

    “啊，感觉自己人生完全了”
    “但愿……我真的能拿到四五十”
    “我考完了……考完了……完了”
    “曾经以为是开玩笑的，原来我还是naïve了”

你冷笑。提前半小时交卷，你自然觉得，数据结构，满分，正常。


title: [清华集训 2017] 福若格斯

background: 小d是4xx9小游戏高手。

description:
有一天，小d发现了一个很经典的小游戏：跳青蛙。

游戏在一个5个格子的棋盘上进行。在游戏的一开始，最左边的两个格子上各有一个向右的青蛙，最右边的两个格子上各有一个向左的青蛙。

![0](https://i.loli.net/2017/12/14/5a32622508ea9.png)

每次移动可以选取一个青蛙，向这只青蛙的前方移动一格到空格子中或跳过前方的一个不同朝向的青蛙并移动到空格子中。

![1](https://i.loli.net/2017/12/14/5a3262250ca07.png)

![2](https://i.loli.net/2017/12/14/5a3262250e38a.png)

为了使你更好地理解这个游戏，我们下发了一个游戏demo作为参考（注意：这个demo中的棋盘大小和题目中并不相同）。

这个游戏本身当然难不倒小d，小d轻松地就解决了这个游戏。但是一个人玩游戏实在是太寂寞了，于是小d找到了小m和他一起玩耍。小d规定，自己只能操控向右的青蛙，小m只能操控向左的青蛙。

小d很快发现，这个游戏想要做到双方轮流行动，就无法达到交换所有青蛙的游戏结局。于是，小d打开了m个游戏，并规定双方轮流行动，每次选择其中一个游戏并控制自己的青蛙行动一步（不能不动）。小d发现，这么做的话就能够使大部分的游戏最终都交换所有的青蛙了。

由于小d是坑队友高手，所以他们玩了一会之后，就开始互相坑害对方，都希望使对方无法行动。他们约定，当轮到一方行动时，若其所有的青蛙都无法行动，则对方获得游戏的胜利。正当博弈论大师小d计算着谁会成为最后的胜者时，电脑卡死了。小d发现，只能kill掉一些游戏才能使剩下的游戏进行下去了。由于电脑已经卡死了，小d无法自由选择kill掉哪些游戏，只能运行系统自带的随机kill小程序。具体来说，小d运行这个随机kill小程序之后，每个游戏有 1/2 的概率被kill掉，有 1/2 的概率能够继续下去。游戏之间被kill掉的概率是独立的。

小d思考了一番，决定如果运行小程序之后他的胜率过低，就直接重启电脑。这时，小d突然发现自己已经不记得刚才轮到谁行动了，于是他决定综合考虑自己先手和后手的胜率。

小d并不擅长概率论，他想让你告诉他运行小程序后，剩下的局面为小d必胜、小m必胜、先手必胜、后手必胜的概率各为多少，这样他才能更好地决定是否重启电脑。

为了避免精度问题，输出答案乘$2^m$之后对$998244353$取模的结果。

注意：题目并不保证输入的所有m个状态中小m和小d之前的总行动步数相差不超过1，但是保证不会出现起始状态无法到达的状态。

inputFormat:
从标准输入读入数据。

我们使用一个长度为5的字符串来表示一个状态，其中，L表示面朝右的青蛙，R表示面朝左的青蛙，_（下划线）表示空格子。例如，初始状态为LL_RR。

本题含有多组数据，第一行两个整数$T,C$($1\leq C\leq 100$)分别表示测试点编号和数据组数。

对于每组数据，第一行一个整数$n$($1\leq n\leq 23$)表示不同状态的棋盘个数，接下来n行每行一个长度为5的字符串$s_i$和一个正整数$a_i$($1\leq a_i\leq 10^6$)，分别表示棋盘的状态和在该状态下的棋盘的个数。

保证输入的字符串合法且不重复。

outputFormat:
输出到标准输出。

定义$m=\sum a_i$。

对于每组数据，输出一行四个整数，分别表示小d必胜（即L的控制方必胜）、小m必胜（即R的控制方必胜）、先手必胜、后手必胜的概率乘$2^m$之后对$998244353$取模的结果。

hint:
**样例1解释**
对于样例1，若该游戏没有被kill，双方唯一可能的操作序列为LL_RR -> L_LRR -> LRL_R -> LR_LR -> LRRL_ -> LRR_L -> L胜，小m先手时同理，故该情况为先手必胜。若该游戏被kill了，双方都没有合法行动，后手必胜。

**样例2解释**
对于样例2，令这三个棋盘的状态从上到下为A,B,C，则$\{A,B,C\},\{A,B\},\{A,C\},\{A\}$,$\{A\}$为小d必胜，$\{C\},\{B,C\}$为小m必胜，$\{B\},\{\}$为后手必胜。

保证数据中不会出现从LL_RR状态无法到达的状态（如RLLR_），故合法的状态共有23种。

定义 $k-$不可达点 为从LL_RR操作$k$次（双方加起来一共操作$k$次，顺序任意）后依然无法到达的合法状态，如 1-不可达点 为 ：全集{LL_RR,L_LRR,LLR_R} 共20个， 5-不可达点 为{RLR_L,RRL_L,RR_LL,R_LRL,R_RLL}。

对于100%的数据，$1\leq n\leq 23,1\leq m\leq 10^6,1\leq C\leq 100$，所有可能出现在该数据点的状态均为等概率出现（也就是说你可以认为最后一个点中每种状态的$a_i$之和大约为$10^8/23$。

![12](https://cdn.luogu.com.cn/upload/pic/14334.png)
![13](https://cdn.luogu.com.cn/upload/pic/14335.png)


title: 避难所

background:
“B君啊，你当年的伙伴都不在北京了，为什么你还在北京呢？”

“大概是因为出了一些事故吧，否则这道题就不叫避难所了。”

“唔，那你之后会去哪呢？”

“去一个没有冬天的地方。”

description:
对于一个正整数 $n$，我们定义他在 $b$ 进制下，各个位上的数的乘积为 $p=F(n,b)$。

比如 $F(3338,10)=216$。

考虑这样一个问题，已知 $p$ 和 $b$，求最小的 $n$ 满足 $p=F(n,b)$。

这是一个非常有趣的问题，对于一些 $b$ 来说，我们可以贪心来做，比如如果 $b=10,p=216$。

我们可以从 $b-1$ 到 $2$ 试除，直到 $p$ 为 $1$ 为止，答案是 $389$，可以验证 $389$ 是满足 $p=F(n,b)$ 最小的 $n$。

但是对于一些进制 $b$，是不能用贪心做的，比如 $b = 9, p = 216$。使用贪心得到的解是 $3338$，而最优解是 $666$。(均为 $9$ 进制下的。)

本题便是在给定进制 $b$ 的情况下，举出一个这样的反例，或指出这样的反例不存在。

由于计算资源所限，反例中所有数字的乘积不能超过 $10^{18}$。如果最小的反例中所有数字的乘积超过了 $10^{18}$，那么也应该输出 $-1$。

inputFormat:
从标准输入读入数据。

第一行一个整数 $t$，表示一共有 $t$ 组数据。

接下来每行一个整数 $b$，表示进制。

outputFormat:
输出到标准输出。

如果不存在反例，输出一行一个整数 $-1$。

如果存在反例，首先输出一个整数 $k$，表示反例 $n$ 的位数，接下来在同一行输出 $k$ 个十进制整数，表示任意一个反例的最优解。

hint:
对于第 $1$ 个测试点，分值为 $30$，$1 \leq n \leq 32$；

对于第 $2$ 个测试点，分值为 $40$，$1 \leq n \leq 100$；

对于第 $3$ 个测试点，分值为 $30$，$1 \leq t \leq 200, 1 \leq n \leq 100000$。


title: [清华集训2017] 我的生命已如风中残烛

background: # 警告，滥用本题者封号!

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

这天她在一堵墙钉了 $n$ 个钉子，第 $i$ 个钉子的坐标是 ($x_i,y_i$)。接着她又在墙上钉上了 $m$ 根绳子，绳子的一端是点 $s_i$($sx_i,sy_i$)，绳子经过点 $t_i$($tx_i,ty_i$)，同时绳子的长度是 $L_i$。其中 $s_i$ 点是粘在墙上的，而另一个端点是可以移动的。初始情况下绳子是紧绷的一条直线段。

接着，对每一根绳子可怜都进行了一次游戏。在第 $i$ 次游戏中，可怜会捏着第 $i$ 根绳子的活动端点进行顺时针移动，移动过程中每时每刻绳子都是紧绷的。

不难发现绳子每时每刻都在以某一个位置为圆心作顺时针的圆周运动。初始情况下圆心是绳子的固定端点 $s$，但是在运动的过程中圆心可能会不断发生变化，如下图所示：

![0](https://i.loli.net/2017/12/14/5a32671628367.png)

图中左侧红点为钉子所在的点，右侧红点为绳子的固定端点，其他颜色的点为虚拟点，活动端点为紫点；绳子从紫点开始运动，在运行到蓝点时绳子绕上左侧红点的钉子，因此活动端点更换了圆心和半径，继续作顺时针的圆周运动。接着活动端点会运行到绿点，并且接下来活动端点会一直绕左侧钉子不停地做圆周运动。

不难发现绳子的运动是不会停止的，因此可怜在她感觉累了之后就会停下来。但是作为一个好奇心满满的女孩子，可怜决定对每一根绳子计算一下如果绳子无限的运行下去，那么它的圆心会切换多少次（包括初始的圆心）。不难发现这个数值一定是有限的。

这里对游戏过程进行一定程度的假设来简化问题：

1.活动端点在运动的过程中距离每一个钉子的欧几里得距离始终大于等于 $9 \times 10^{-4}$。
2.钉子的坐标两两不同但可能有**多点共线**。
3.钉子的体积以及绳子的体积可以忽略不计。在游戏的过程中每一段绳子之间不会互相影响。
4.初始情况下绳子距离每一个钉子的最近欧几里得距离大于等于 $9 \times 10^{-4}$。
5.每一根绳子初始粘着的端点**不会**影响绳子的运动，即**绳子不会绕回端点上**。

inputFormat:
从标准输入读入数据。

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

每组数据第一行为两个整数 $n,m$，表示钉子数和绳子数。

接下来 $n$ 行，每行两个整数 $x_i,y_i$ 表示钉子的坐标。

接下来 $m$ 行，每行五个整数 $sx_i,sy_i,tx_i,ty_i,L_i$ 表示一段绳子，含义如上所述。

outputFormat:
输出到标准输出。

对于每组数据的每组询问，输出一行一个整数表示运行的过程中圆心变化了多少次。

不同数据组数之间**无需**空行隔开。


title: [清华集训2017] 榕树之心

background:
深秋。冷风吹散了最后一丝夏日的暑气，也吹落了榕树脚下灌木丛的叶子。相识数年的Evan和Lyra再次回到了小时候见面的茂盛榕树之下。小溪依旧，石桥依旧，榕树虽是历经荣枯更迭，依旧亭亭如盖，只是Evan和Lyra再也不是七八年前不经世事的少年了。

……

“已经快是严冬了，榕树的叶子还没落呢……”

“榕树是常绿树，是看不到明显的落叶季节的……”

“唉……想不到已经七年了呢。榕树还是当年的榕树，你却不是当年的你了……”

“其实又有什么是一成不变的呢，榕树常绿，翠绿树冠的宏观永恒，是由无数细小树叶的荣枯更迭组成的。在时间的流逝中一切都在不断变化着呢……”

“但你看这榕树，日日如此，季季如此，年年如此，仿佛亘古不变般，盘根错节，郁郁葱葱。我在想，或许成为一棵树更好吧，任时间从枝叶间流过，我只守这一片绿荫就好。”

“榕树固然长久，但在这无限的时光里，终归是要湮灭于尘土的。与其像榕树一般，植根于一方泥土中感受年复一年的四季更替。倒不如在有限的时间里看过尽可能多的世界吧。再说了，榕树虽生长缓慢，却依旧会在每年春天抽出一根新的枝条去向外探索的呢……”

“真的吗，榕树在她漫长的一生里，就是这样往外一步步探索的吗？”

“毕竟就算树冠看起来一成不变，榕树也会随着时间周期变化，春天到了自然就是生长的时候了，她也应当做出对应的表现吧……”

“相比于对季节更替做出本能的生长，我倒宁愿相信，榕树有一颗活跃的的，探索的心。”

“其实榕树是有心的，榕树刚刚种下的时候，心就在根的地方发芽了。以后每年春天榕树长出新枝条的时候，心就会向着新枝条的方向移动一点，这样就能更靠近外面的世界了。你看这头顶上的枝条，纵横交错，其实心已经在这枝杈间，移动了数十载了呢……”

“哇，也就是说，这密密麻麻的树杈中的某个地方，藏着这棵榕树的心吗？”

“没错，可是要知道它在哪，就得另花一番功夫了……”

“呀，这时候想想，一株树还是不如一个人好……比如你，要是这样贴上去的话，就能听到跳动的声音呢……”

……

description:
一棵榕树可以抽象成一棵$n$个结点的有根树，其中结点编号为$1 \sim n$，而$1$号点就是根节点。初始时，树只有一号点，而心也在一号点。之后每一步，树都会长出一个新结点，即某个和当前已经存在的某个结点相邻的结点被加入了树中，之后，心会沿着心到新加结点的简单路径移动一步。这棵$n$个结点的树有很多种生长的顺序，不同的顺序可能会导致最终心的位置不同。现在，Evan和Lyra想知道，哪些结点可能是心在生长过程结束时停留的位置呢？

例如一棵大小为$4$的树，连边为$\{<1,2>,<1,3>,<1,4>\}$，我们有三种不同的生长顺序可以让心分别停留在$2,3,4$号节点上：

最终停留在$2$号点：

    从1生长出3，心从1移动到3,
    从1生长出4，心从3移动回1,
    从1生长出2，心从1移动到2.

最终停留在$3$号点：

    从1生长出2，心从1移动到2,
    从1生长出4，心从2移动回1,
    从1生长出3，心从1移动到3.

最终停留在$4$号点：

    从1生长出2，心从1移动到2,
    从1生长出3，心从2移动回1,
    从1生长出4，心从1移动到4.

而我们可以证明，不存在任何一种可能的生长顺序使得心停留在$1$号点。

inputFormat:
从标准输入读入数据。

输入第一行一个两个正整数$W,T$，分别表示子任务编号（在样例中$W=0$）和数据组数，接下来是$T$组数据的描述，对于每组数据：

第一行一个正整数$n$表示树上结点的个数。

接下来$n-1$行，每行两个正整数$a_i,b_i$，表示编号$a_i,b_i$的结点间有一条树边，保证$a_i \neq b_i$并且输入的$n-1$条边恰好构成了一棵树。

outputFormat:
输出到标准输出。

若输入的$W$不等于$3$，对于每组数据输出一行一个长度为$n$的$01$字符串，表示编号为$1 \sim n$的结点是否有可能是心最后所在的位置，若$01$字符串对应位是$1$则表示可能，为$0$则表示不可能。

若输入的$W$等于$3$，则对每组数据输出一个字符表示$1$号点的答案。

hint:
**TestPoint 1[10pts]**

$T \leq 50; n \leq 15$。

**TestPoint 2[10pts]**

$T \leq 20; n \leq 10^5$。除了$1$号点之外，每个点度数（包括父亲）不超过$2$。

**TestPoint 3[10pts]**

$T \leq 200; n \leq 100$。只输出一个字符表示$1$号点答案，即保证$1$号点答案正确即可。

**TestPoint 4[35pts]**

$T \leq 20; n \leq 10^3$。

**TestPoint 5[35pts]**

$T \leq 20; n \leq 10^5$。


title: 某位歌姬的故事

description:
IA 是一名会唱歌的女孩子。

IOI2018 就要来了，IA 决定给参赛选手们写一首歌，以表达美好的祝愿。这首歌一共有 $n$ 个音符，第 $i$ 个音符的音高为 $h_i$。IA 的音域是 $A$，她只能唱出 $1\sim A$ 中的正整数音高。因此 $1\le h_i\le A$。

在写歌之前，IA 需要确定下这首歌的结构，于是她写下了 $Q$ 条限制，其中第 $i$ 条为：编号在 $l_i$ 到 $r_i$ 之间的音符的最高音高为 $m_i$。在确定了结构之后，她就可以开始写歌了。不过她还是想知道，一共有多少种可能的歌曲满足她的所有限制？她听说你还有 9 个月就要去 IOI 了，于是希望你帮她计算一下这个值。

inputFormat:
从标准输入读入数据。

输入的第一行包含一个整数 $T$($T\le 20$)，代表测试数据的组数。

每组数据的第一行包含三个正整数 $n,Q,A$。接下来 $Q$ 行，每行三个整数 $l_i,r_i,m_i$，表示一条限制。保证 $1\le l_i\le r_i\le n, 1\le m_i\le A$。

outputFormat:
输出到标准输出。

输出文件只有一行，表示可能的歌曲数目。这个数可能很大，请将答案模 $998244353$ 输出。


title: [CQOI2012] 编号

description:
你需要给一批商品编号，其中每个编号都是一个 $7$ 位 $16$ 进制
数（由 $0$ 至 $9$, $a$ 至 $f$ 组成）。

为了防止在人工处理时不小心把编号弄错，要求任意两个编号至少有三个位置对应的数字不相同。

第一个编号为 $0000000$，第二个编号为不违反上述规定的前提下最小的编号，…，每次分配一个新编号时，总是选择不和前面编号冲突的最小编号（注意到编号都是 $16$ 进制数，可以比较大小）。

按此规律，前面若干编号分别是：

$$0000000,0000111,0000222,…,0000fff,0001012,0001103,0001230,00
01321,0001456,…$$

输入 $k$，你的任务是求出第 $k$ 小的编号。

inputFormat: 一行一个数，为整数 $k$。

outputFormat: 输出第 $k$ 小的编号（字母均为小写）。输入保证这个编号存在。


title: [NOI2006] 聪明的导游

background:
输入数据下载地址：

https://pan.baidu.com/s/1jJX0E3c

数据由1584432137提供。

Upd on 2022.8.7：输入文件在附件。

description:
小佳最近迷上了导游这个工作，一天到晚想着带游客参观各处的景点。正好 M 市在举行 NOI，来参观的人特别的多。不少朋友给小佳介绍了需要导游的人。

M 市有$n$个著名的景点，小佳将这些景点从$1$至$n$编号。有一些景点之间存在双向的路。小佳可以让游客们在任何一个景点集合，然后带着他们参观，最后也可以在任何一个景点结束参观。不过，来参观的游客们都不愿去已经参观过的地方。所以，小佳不能带游客们经过同一个景点两次或两次以上。

小佳希望你帮助他设计一个方案, 走可行的路线, 带游客们参观尽可能多的地方。

inputFormat: 输入文件为 guide1.in~guide10.in，第一行为两个整数$n,m$，分别表示景点数和路的条数。接下来$m$行，每行两个整数$a,b$，表示景点$a$和景点$b$之间有一条双向路。

outputFormat:
你需要将答案输出到 guide1.out~guide10.out 中，guide?.out 为对应 guide?.in

的答案。输出的第一行为$p$，表示你能找到的路径所经过的景点个数。接下来$p$ 行，每行一个整数，按顺序表示你所找到的路径上的每一个景点。


title: 最小差值生成树

description: 给定一个点标号从 $1$ 到 $n$ 的、有 $m$ 条边的无向图，求边权最大值与最小值的差值最小的生成树。图可能存在自环。

inputFormat:
第一行有两个整数，表示图的点数 $n$ 和边数 $m$。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示存在一条连接 $u, v$ 长度为 $w$ 的边。

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

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

- 对于 $30\%$ 的数据，保证 $n \leq 100$，$m \leq 10^3$。
- 对于 $97\%$ 的数据，保证 $n \leq 500$，$m \leq 10^5$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 5 \times 10^4$，$1 \leq m \leq 2 \times 10^5$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^4$。


title: 期望逆序对

background: WXH大定理定律n

description:
mcfx领导的修道院试图通过古老的膜法阵召唤出传说中的膜法处佬WXH。在他把召唤用具准备齐全后，mcfx在众人的键盘声中启动了召唤阵。

这时，天地突然暗了下来，膜法阵中心电闪雷鸣。一道金光从天而降，金色的代码飘在了半空中。不一会，一个登陆界面显现了出来。mcfx仔细观察后发现上面有如下文字：

"WXHCoder是过去到未来所有的题目都有的题库。如果想要登陆它，你们必须解决接下来这道题。"

这道题目是这样子的：给你一个长为$n$的排列，有$k$次操作，每次随机选择两个不同的数交换，问期望逆序对数乘${{n}\choose{2}}^k$的结果。

mcfx发现数据范围是$n,k≤10^{20010910}$，他打算先探究更小的$n,k$。

${n}\choose{2}$表示在$n$个球中选两个的方案数

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

第二行一个$1$到$n$的排列

outputFormat: 输出期望逆序对数乘${{n}\choose{2}}^k$的结果模$10^9+7$


title: [USACO22DEC] Cow College B

description:
Farmer John 计划为奶牛们新开办一所大学！

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

有 $N(1 \le N \le 10^5)$ 头奶牛可能会入学。每头奶牛最多愿意支付 $c_i$ 的学费 $(1 \le c_i \le 10^6)$。 Farmer John 可以设定所有奶牛入学需要支付的学费。如果这笔学费大于一头奶牛愿意支付的最高金额，那么这头奶牛就不会入学。Farmer John 想赚尽可能多的钱，从而可以给他的讲师提供一笔可观的工资。请求出他能赚到的钱的数量，以及此时应当收取多少学费。

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

第二行包含 $N$ 个整数 $c_1,c_2, \cdots,c_N$，其中 $c_i$ 是奶牛 $i$ 愿意支付的最高学费金额。

outputFormat:
输出 Farmer John 可以赚到的最大金额以及最优情况下他应该收取的学费。如果有多个解，输出收取学费最小的解。

**注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，Java 中的 "long"，C/C++ 中的 "long long"）。**

hint:
### 样例 1 解释

如果 Farmer John 收费 $4$，那么 $3$ 头奶牛将会入学，从而使他赚取 $3 \times 4=12$ 的金额。

### 测试点性质

- 测试点 $2-4$ 满足 $c_i \le 1000$。
- 测试点 $5-8$ 满足 $N \le 5000$。
- 测试点 $9-12$ 没有额外限制。


title: [NOIP2022] 比赛

description:
小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP！小 P 会作为裁判主持竞赛。小 N 和小 O 各自率领了一支 $n$ 个人的队伍，选手在每支队伍内都是从 $1$ 到 $n$ 编号。每一个选手都有相应的程序设计水平。具体的，小 N 率领的队伍中，编号为 $i$（$1 \leq i \leq n$）的选手的程序设计水平为 $a _ i$；小 O 率领的队伍中，编号为 $i$（$1 \leq i \leq n$）的选手的程序设计水平为 $b _ i$。特别地，$\{a _ i\}$ 和 $\{b _ i\}$ 还分别构成了从 $1$ 到 $n$ 的排列。

每场比赛前，考虑到路途距离，选手连续参加比赛等因素，小 P 会选择两个参数 $l, r$（$1 \leq l \leq r \leq n$），表示这一场比赛会邀请两队中编号属于 $[l, r]$ 的所有选手来到现场准备比赛。在比赛现场，小 N 和小 O 会以掷骰子的方式挑选出参数 $p, q$（$l \leq p \leq q \leq r$），只有编号属于 $[p, q]$ 的选手才能参赛。为了给观众以最精彩的比赛，两队都会派出编号在 $[p, q]$ 内的、程序设计水平值最大的选手参加比赛。假定小 N 派出的选手水平为 $m _ a$，小 O 派出的选手水平为 $m _ b$，则比赛的精彩程度为 $m _ a \times m _ b$。

NOIP 总共有 $Q$ 场比赛，每场比赛的参数 $l, r$ 都已经确定，但是 $p, q$ 还没有抽取。小 P 想知道，对于每一场比赛，在其所有可能的 $p, q$（$l \leq p \leq q \leq r$）参数下的比赛的精彩程度之和。由于答案可能非常之大，你只需要对每一场答案输出结果对 $2 ^ {64}$ 取模的结果即可。

inputFormat:
第一行包含两个正整数 $T, n$，分别表示测试点编号和参赛人数。如果数据为样例则保证 $T = 0$。

第二行包含 $n$ 个正整数，第 $i$ 个正整数为 $a _ i$，表示小 N 队伍中编号为 $i$ 的选手的程序设计水平。

第三行包含 $n$ 个正整数，第 $i$ 个正整数为 $b _ i$，表示小 O 队伍中编号为 $i$ 的选手的程序设计水平。

第四行包含一个正整数 $Q$，表示比赛场数。

接下来的 $Q$ 行，第 $i$ 行包含两个正整数 $l _ i, r _ i$，表示第 $i$ 场比赛的参数 $l, r$。

outputFormat: 输出 $Q$ 行，第 $i$ 行包含一个非负整数，表示第 $i$ 场比赛中所有可能的比赛的精彩程度之和对 $2 ^ {64}$ 取模的结果。

samples:
见附件下的 match/match2.in。
见附件下的 match/match2.ans。

samples:
见附件下的 match/match3.in。
见附件下的 match/match3.ans。


title: [USACO22DEC] Feeding the Cows B

description:
Farmer John 有 $N(1 \le N \le 10^5)$ 头奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。她们沿水平方向排成一行，奶牛们占据的位置编号为 $1 \cdots N$。

由于奶牛们都饿了，FJ 决定在 $1 \cdots N$ 中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草，所以如果 Farmer John 决定在某个位置种草，他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。

每头奶牛愿意移动至多 $K(0 \le K \le N-1)$ 个位置以前往一个草地。求出喂饱所有奶牛所需种植的最小草地数量。此外，输出一种使用最小草地数量喂饱所有奶牛的种植方案。任何满足上述条件的方案均视为正确。

inputFormat:
每个测试用例包含 $T$ 个子测试用例，为一种奶牛的排列。输入的第一行包含 $T(1 \le T \le 10)$。以下是 $T$ 个子测试用例。

每个子测试用例的第一行包含 $N$ 和 $K$。第二行包含一个长度为 $N$ 的字符串，其中第 $i$ 个字符表示第 $i$ 头奶牛的品种（G 表示更赛牛，H 表示荷斯坦牛）。

outputFormat: 对于 $T$ 个子测试用例中的每一个，输出两行。第一行输出喂饱所有奶牛所需的最小草地数量。第二行输出一个长度为 $N$ 的字符串，表示一种使用最小草地数量喂饱所有奶牛的种植方案。第 $i$ 个字符表示第 $i$ 个位置，若不种草则为 $\texttt{.}$，若种植喂饱更赛牛的草则为 $\texttt{G}$，若种植喂饱荷斯坦牛的草则为 $\texttt{H}$。任何合法的方案均可通过。

samples:
6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH

hint:
### 样例 1 解释

注意对于某些子测试用例，存在多种可通过的方案使用最小数量的草地。例如，在第四个子测试用例中，以下是另一个可以通过的答案：

$$\texttt{.GH..}$$

这个方案在第二个位置种植一块喂饱更赛牛的草地以及在第三个位置种植一块喂饱荷斯坦牛的草地。这使用了最小数量的草地并确保了所有奶牛都在她们喜欢的草地的 $3$ 个位置以内。

### 测试点性质

- 测试点 $2-4$ 满足 $N \le 10$。
- 测试点 $5-8$ 满足 $N \le 40$。
- 测试点 $9-12$ 满足 $N \le 10^5$。


title: 连环病原体

background:
###（一）洞穴

顺着狭窄倾斜的溶洞向下走，这里，真有一番地心探险的感觉呢。

告诉你啊，地底有一片广阔的大世界，叫做旧地狱。

那里居住着被地面上的人厌恶的妖怪们。

虽然听着比较吓人，但实际上在地狱废弃后，一切都是井井有条的。

前方有一片开阔的空间啊，好像有人。

"地面上的来客吗,你好啊"

终于遇到地底的居民了。

眼前的两只妖怪是黑谷山女和琪斯美。

琪斯美呆在一个小桶里，悬挂在空中，和山女讨论着什么。

"哇，你们在讨论什么啊"

"嗯，有关病毒的问题，你们不懂的"

忘记说了，山女可以操纵疾病，所以谈论这样的话题自然也就很平常了。

不过好奇心很难抵挡啊，那就假装自己能帮上忙，然后接着问下去吧。

"好吧，你们要是能帮上忙的话就再好不过了"

"嗯，主要是，想知道病原体之间的相互作用，会对疾病产生什么影响呢。你看啊，把不同种的病原体看做点，相互作用看成连接这些点的线，如果产生了环，那么病毒的威力就会大幅加强，我把它叫做加强环。"

"病原体之间的相互作用也有很多种呢，我想研究的是，每种相互作用在产生加强环的过程中有多么重要。"

啊，听起来好复杂，不过如果帮了她的忙，地底的妖怪们大概会对我们友善一些吧。

而且，点，边，环？这些名词似乎见过呢，说不定我真的能帮上忙？

那么，继续详细地询问吧。

嗯，问出来的信息已经记录在这张纸上了。

description:
问题摘要:

有n 种病原体，它们之间会产生$m$种无方向性的影响，第$i$种影响发生在$u_i$,$v_i$ **两种**病原体之间。

我们把所有的**影响**按编号顺序排成一个序列，如果某一个区间包含有环，那么这个区间被称作加强区间。

求每种影响分别在多少个加强区间中出现过。

那么，到底怎样做才能高效的得出结果呢？

(后续剧情见本题题解，接下来请看T2)

inputFormat:
第一行一个数$m$
接下来$m$行每行两个数$u_i$,$v_i$，用空格分隔

outputFormat: 一行$m$个数字，第$i$个数字代表第$i$种影响在多少个加强区间内出现过，数字之间用空格分隔

hint:
###样例解释：

第一种影响在[1,4]和[1,5]两个加强区间内出现

第二种影响在[1,4]、[1,5]和[2,5]三个加强区间内出现

第三种影响在[1,5]、[1,4]和[2,5]三个加强区间内出现

第四种影响在[1,4]、[2,5]和[1,5]三个加强区间内出现

第五种影响在[2,5]和[1,5]两个加强区间内出现

注意：加强区间是由“影响”构成的，而不是由“病原体”构成的

$n\leqslant2m\leqslant400000$

测试点1~2总分10分，$m\leqslant5$

测试点3~6总分20分，$m\leqslant200$

测试点7~12总分30分，$m\leqslant5000$

测试点13~15总分15分，$m\leqslant50000$

测试点16~18总分15分，$m\leqslant50000$，捆绑测试

测试点19~22总分10分，$m\leqslant200000$，捆绑测试

by oscar


title: 三步必杀

background:
### （三）旧都

离开狭窄的洞穴，眼前豁然开朗。

天空飘着不寻常的雪花。

一反之前的幽闭，现在面对的，是繁华的街市，可以听见酒碗碰撞的声音。

这是由被人们厌恶的鬼族和其他妖怪们组成的小社会，一片其乐融融的景象。

诶，不远处突然出现了一些密密麻麻的小点，好像大颗粒扬尘一样。

离得近了点，终于看清楚了。

长着角的鬼们聚在一起，围观着另一只鬼的表演。

那”扬尘”，其实都是弹幕。

勇仪的招数之一，三步之内，所到之处弹幕云集，几乎没有生存可能。

为了强化这一技能，勇仪将对着一排柱子进行攻击。

旧地狱的柱子虽然无比坚固，但保险起见还是先要了解一下这样一套攻击对柱子有多少损伤，顺带也能检验练习的效果。

勇仪决定和其它鬼们商量商量...

“我知道妖怪之山的河童一族有一种叫做计算机的神奇道具，说不定可以借来用用”，萃香说道。

于是旧地狱的鬼族就决定请河城荷取来帮忙了。

“要记录【所有柱子的损伤程度】吗”，荷取问道。

经过进一步的询问，荷取发现他们仅仅需要【所有攻击都完成后】柱子的损伤程度。

任务了解地差不多了，荷取将其中的重要部分提取了出来，记录在了她的工作笔记本上：

(记录的内容见题目描述)

那么实验就这样开始了。

在惊天动地的碰撞声中，勇仪每完成一轮攻击，荷取都忠实地记录下对每根柱子产生的伤害。而此时勇仪就在旁边等待着记录完成，然后再进行下一轮的攻击。

地面上，天色渐晚。

“不想在这里留到深夜啊，不然就回不了家了”，荷取这样想着，手中依然在重复地向计算机中输入新产生的信息。

“真的必须一次一次地记录下每轮攻击对每个柱子产生的伤害吗？有没有更高效的方法？”这一念头在荷取的心中闪过...

（后续剧情在题解中，接下来请看T3）

description:
### 问题摘要：

$N$个柱子排成一排，一开始每个柱子损伤度为0。

接下来勇仪会进行$M$次攻击，每次攻击可以用4个参数$l$,$r$,$s$,$e$来描述：

表示这次攻击作用范围为第$l$个到第$r$个之间所有的柱子(包含$l$,$r$)，对第一个柱子的伤害为$s$，对最后一个柱子的伤害为$e$。

攻击产生的伤害值是一个等差数列。若$l=1$,$r=5$,$s=2$,$e=10$，则对第1~5个柱子分别产生2,4,6,8,10的伤害。

鬼族们需要的是所有攻击完成之后每个柱子的损伤度。

inputFormat:
第一行2个整数$N$,$M$，用空格隔开，下同。

接下来$M$行，每行4个整数$l$,$r$,$s$,$e$，含义见题目描述。

数据保证对每个柱子产生的每次伤害值都是整数。

outputFormat:
由于输出数据可能过大无法全部输出，为了确保你真的能维护所有柱子的损伤度，只要输出它们的异或和与最大值即可。

（异或和就是所有数字按位异或起来的值）

（异或运算符在c++里为^）

hint:
### 样例解释：

样例1：

第一次攻击产生的伤害:2 4 6 8 10

第二次攻击产生的伤害:0 1 1 1 0

所有攻击结束后每个柱子的损伤程度:2 5 7 9 10。

输出异或和与最大值，就是3 10。

样例2：

没有打到第六根柱子，答案不变

### 数据范围：

本题满分为100分，下面是4个子任务。(x/y)表示(得分/测试点数量)

妖精级(18/3):$1\leqslant n$,$m\leqslant1000$。这种工作即使像妖精一样玩玩闹闹也能完成吧？

河童级(10/1):$s=e$,这可以代替我工作吗？

天狗级(20/4):$1\leqslant n\leqslant10^5$,$1\leqslant m\leqslant10^5$。小打小闹不再可行了呢。

鬼神级(52/2):没有特殊限制。要真正开始思考了。

以上四部分数据不相交。

对于全部的数据:$1\leqslant n\leqslant10^7$,$1\leqslant m\leqslant3\times 10^5$，$1\leqslant l<r\leqslant n$.

所有输入输出数据以及柱子受损伤程度始终在$[0,9\times 10^{18}]$范围内。

### 提示：

由于种种原因，时间限制可能会比较紧，C++选手请不要使用cin读入数据。

by orangebird


title: 无意识之外的捉迷藏

background:
### （五）心与心的对话

旧都还在下着雪。

不知道走了多远的路，已经远离街市了。

眼前隐隐约约能看到一座巨大的宫殿。

那就是，地灵殿吗？

心里突然紧张了起来。

这里住着旧地狱最可怕的觉妖怪。

古明地觉，她拥有读心的能力。人类，妖怪，甚至是怨灵，站在她面前的时候都如同赤身裸体，没有任何秘密可言。而且，听说在战斗中，她还会使用催眠术不断激起对手内心深处的恐怖回忆，从心灵上打垮对手。这样的妖怪自然会被人讨厌啦。

不过，此次地底之旅可不能因为要遇到可怕的妖怪而就此结束。

咚咚咚，敲了敲地灵殿的大门。

“来客吗，真是少见呢。”

眼前，站着一个少女，穿着蓝色的衣服，粉红色的裙子，头发也是粉红色的。

在她的胸前，悬着一只红色的大眼睛，通过眼睛周围的六根管子连接着身体。

她看起来很温柔的样子，完全不像听说的那样恐怖。

“来地底旅行的外面世界的人类吗？真是非常少见呢，居然找到了这里”

“看起来没有别的想法，就是想来转转呢，那就进来吧”

走进大门。

不愧是地灵”殿”，真的是好大的一个宫殿，桃红色和黑色相间的地板，印有花纹的窗户。

眼前是一组很宽的台阶，通向二楼，然后分成左右两个通道。

“很漂亮吧，这里空间大，宠物们都很喜欢呢。”

就这样，我跟着觉进入了她工作的房间，我们坐在沙发上聊了很久，虽然我很少说话。

在聊天的过程中，我了解到她还有一个妹妹古明地恋，由于不愿让别人因为自己会读心而讨厌自己，闭上了觉之瞳。觉为了开导妹妹，经常和宠物陪着她玩。

地灵殿，觉和妹妹，宠物们，一直在过着平静又温馨的生活。

“既然来这里了，就和我们一起玩吧。”觉邀请我们参与她们的游戏。

地底的妖怪会玩怎样的游戏呢？

于是，就这样，我就答应参与觉和恋的“无意识的捉迷藏”了。

说是”捉迷藏”，其实和普通的捉迷藏区别很大，更类似于”捉人游戏”。

就是觉和恋一开始分别站在两个地方，觉要捉到恋就算赢了。

但为什么又说是”捉迷藏”呢？

原来恋恋可以无意识地行动，也就是可以让周围人在潜意识里忽略她的存在，类似隐身，但又不是隐身。真是有趣的能力呢，是不是闭上了觉之瞳的缘故？

我们玩得很开心。有时无意识碰到了恋恋的手，还吓了一跳呢。

一段时间后，姐妹俩累了，觉还有工作要处理，就先回去了。

宠物们似乎意犹未尽，她们还想继续。

“可是在这个旧地狱啊，除了主人的妹妹恋以外，哪里又有妖怪能够操纵无意识呢？

算了,干脆玩普通的捉人游戏吧。”阿燐提议道。

于是宠物们很快又忘我地投入了”无意识之外的捉迷藏”中。

不知什么时候，我感到背后一凉，回过头一看，原来是恋恋。

我们就这样站在这里看着宠物们玩。

虽然不知道为什么能耐心地看那么长时间，但几个小时过去了，我们依然站在这里。

恋恋好像有一些疑问，在经过简单的交流后，我把她的疑问做了一个总结。

(见题目描述)

这个问题对无意识的恋恋来说果然无法解决啊。

能和姐妹俩聊得这么开心，真是很感激呢，那就尽自己的努力思考一下这个问题吧。

(后续剧情见题解，接下来请看T4)

description:
###问题摘要：

在一个有向无环图上，阿燐和阿空第0个时刻分别站在编号为$s_r$,$s_k$的节点，二人都知道双方的初始位置，对地图完全了解。

从第1个时刻起，每个时刻阿燐和阿空都可以选择站着不动，也可以选择移动到相邻的节点，二人每时刻的移动是同时开始的，并且不能中途改变方向。

阿燐被阿空捉住时，游戏立即结束。如果阿空一直没有捉住阿燐，第$t$个时刻结束后两人就不能再继续移动了，游戏将在第$t+1$个时刻结束。

阿空的目的是尽快捉住阿燐(捉住的定义是与阿燐同一时刻站在同一节点)，而阿燐的目的是尽可能更长时间不被阿空捉住。具体而言，若一场游戏进行了$t_0$时刻，阿燐的得分是$t_0$，阿空的得分是$-t_0$，双方都希望自己得分(或得分的期望值)更高。

我们认为在这个过程中阿燐和阿空随时都能知道对方的位置。两人在第$t$个时刻不能看出第$t+1$个时刻对方要走到哪里。

恋恋想知道，在双方最优决策的情况下，游戏结束时刻的期望值是多少。

inputFormat:
第一行5个整数$n$,$m$,$s_r$,$s_k$,$t$，用空格隔开，下同。

$n$表示地图点数，$m$表示边数。

接下来$m$行，每行两个整数$a$,$b$，表示从$a$到$b$有一条单向边(不存在重边)。

outputFormat:
一个实数，四舍五入保留3位小数，表示游戏结束时刻的期望值。

你的答案必须和标准答案完全相同才算正确。

hint:
###样例解释：

样例1：阿燐只要一直不动，阿空在前$t$单位时间内就无法抓到阿燐，答案为$t+1$，即```11.000```

样例2：无可奉告

###数据范围：

对于30%的数据 $n\leqslant3$，捆绑测试

对于100%的数据 $n,t\leqslant20$，前40%的数据和后30%的数据分别捆绑测试

###提示：
本题主要考察你能否使用正确的方法算出答案，对算法运行耗时要求不高。

by orangebird


title: 射命丸文的笔记

background:
### （七）再见，地底世界的朋友们

在地灵殿住了许多天了呢。

这些日子里，觉分享了很多旧地狱的故事。

此次地底旅行，可以说是非常充实了。

虽然仍旧有些不舍，不过人类总是要见太阳的，再说这样麻烦觉姐姐招待我们也有些过意不去呢。

那么，和觉，恋，阿燐，阿空，以及其他宠物们说再见吧。

......

旧地狱的街市，依旧飘着雪。

已经能看到溶洞了。

环境又变得幽闭起来。

诶，前面不是山女吗？

“啊，你们要回地面了吗，玩的怎样？”

“很开心呢，对了，剩下的问题已经解决了”

我们向山女解释了从荷取那里听到的方法。

“谢谢!”

“不客气，那么再见了~”

世界一片白茫茫的...

阳光是那么的刺眼，以至于几分钟后我们才能睁开眼睛看清楚地面的景色。

沿着魔法森林中的小路向神社走去，这次的旅行也在我们的脚步声中走向了尾声。

前方的地面上忽然出现了一页破损的笔记。

捡起来一看，发现是从文文的笔记本上脱落下来的。

射命丸文，作为（不靠谱的）新闻记者，观察到最近地灵殿里的宠物们偶尔会互相打架，于是将每场决斗的胜负关系写在了她的笔记本上。刚刚捡起来的这页笔记，上面就记录着几场“单循环赛”。

每场循环赛被抽象成一张竞赛图，其中顶点代表参加循环赛的宠物，从顶点 $u$ 指向顶点 $v$ 的边代表在一场比赛中宠物 $u$ 战胜了宠物 $v$。

观察到这页笔记上所有的竞赛图中都至少存在一条经过所有顶点的回路，我们猜想文文只会记录这样的循环赛。

可能是因为文文不清楚宠物们谁能打过谁，于是在那页笔记的最下面留下了一个这样的问题...

(见题目描述)

这最后一个问题，就留给你来解决啦。

博丽大结界，已经在我们身后了。

希望这次地底旅行，能给你留下美好的记忆~

(全文完)

description:
如果一个竞赛图含有哈密顿回路，则称这张竞赛图为值得记录的。

从所有含有 $n$ 个顶点（顶点互不相同）的，值得记录的竞赛图中等概率随机选取一个。

求选取的竞赛图中哈密顿回路数量的期望值。

由于答案可能过大/丢失精度，只需要输出答案除以 $998244353$ 的余数。

即：设答案为 $\frac{q}{p}$，则你需要输出一个整数 $x$，满足 $px\equiv q \mod 998244353$ 且 $0\leqslant x<998244353$，可以证明恰好存在一个这样的 $x$。

若不存在这样的竞赛图，输出 `-1`。

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

outputFormat: $n$ 行，第 $i$ 行一个数字，代表输入为 $i$ 时的答案

hint:
### 样例解释：

$n=1$ 时只有一种满足条件的竞赛图，就是一个点。

$n=2$ 时竞赛图中只有一条边，不能形成哈密顿回路。

$n=3$ 时有两种满足条件的竞赛图，分别为 $1\to2\to3\to1$ 和 $1\to3\to2\to1$，都只有 $1$ 条哈密顿回路，随机取出后期望值为 $1$。

$n=4$ 时有很多种满足条件的的竞赛图，这里写不下了，但是所有满足条件的竞赛图都是同构的，所以随机取出后期望值为 $1$。

### 数据范围：

测试点 1~3 中 $n\leqslant7$。

测试点 4~6 中 $n\leqslant10$。

测试点 7~10 中 $n\leqslant1000$。

测试点 11~16 中 $n\leqslant10000$。

测试点 17~25 中 $n\leqslant100000$。

数据有梯度，每个测试点 $4$ 分。

为防止卡常，最后两个点开 2s 时限。

### 名词解释：

[竞赛图](https://en.wikipedia.org/wiki/Tournament_(graph_theory))：指任意两个顶点间恰有一条有向边的有向图。

[哈密顿回路](https://en.wikipedia.org/wiki/Hamiltonian_cycle)：指除起点和终点外经过所有顶点恰好一次且起点和终点相同的路径。

by oscar


title: [Ynoi2011] ODT

background: 【先咕咕咕

description:
给你一棵树，边权为 $1$，有点权。

需要支持两个操作：

- `1 x y z`：表示把树上 $x$ 到 $y$ 这条简单路径的所有点点权都加上 $z$。
- `2 x y`：表示查询与点 $x$ 距离**小于等于** $1$ 的所有点里面的第 $y$ 小点权。

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

第二行 $n$ 个整数表示每个点的点权。

之后 $n-1$ 行，每行两个整数 $x,y$ 表示 $x$ 和 $y$ 之间连有一条边。

之后 $m$ 行，每行为 `1 x y z` 或者 `2 x y` 形式，意义如上述。

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

数据保证每次询问都存在答案。

hint:
Idea：nzhtl1477，

Solution：nzhtl1477( $O( n\log^2n/ \log\log n )$ solution )，negiizhao( $O( n\log n\log\log\log n )$ solution )，ccz181078( $O( n\log n )$ solution )，

Code：nzhtl1477( $O( n\log^2 n/ \log\log n )$ code )

Data：nzhtl1477( partially uploaded )

subtask 1：$20\%$ $n,m\leq 1000$。

subtask 2：$10\%$ 树为一条链。

subtask 3：$20\%$ $n,m\leq 10^5$。

subtask 4：$30\%$ $n,m\leq 4\times 10^5$。

subtask 5：$20\%$ $n,m\leq 10^6$。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^6$，$0\leq $ 每次加的数 $\leq 2000$，$0\leq $ 初始的点权 $\leq 2000$。


title: 扑克

background: lsq邀请wzt去他家打扑克牌

description:
lsq的扑克没有大小王，共计有n张，由于wzt沉迷于幂运算无法自拔，wzt提出要每次抽a^2张牌（这里“^”是乘方的意思），lsq觉得这样抽真没意思，于是改成了每次抽a^k（k是一个自然数，由游戏者自由选择）张牌。**由lsq开始**，每个人轮流按上述规则摸牌，谁先摸到最后一张牌谁就赢。

由于时间充裕，lsq和wzt一共会玩q盘游戏，每一盘都有不同的a和n。wzt怒敲了一波代码，竟然可以算出当确定了a和n的值后，若能必胜如何下。lsq在见识过你的~~毒瘤~~操作后，希望你也帮他写出一个程序，能判断确定了a和n的值后他是否能赢，lsq当然知道怎么下最优，所以不需要你算出如何下

**注意：此题中两方的打牌决策都是若有必胜决策则必用必胜决策**

此题中k是一个每次抽牌都可由抽牌者自己决定的一个非负整数，可以结合下面的样例加以理解

inputFormat:
第一行一个数q， 表示有q局游戏
接下来q行，每行两个整数a,n，意义如上

outputFormat:
输出共q行
若lsq能赢，输出“lsq Win”
若wzt能赢，输出“wzt Win”

hint:
对于30%的数据，满足q<=30，a<=30，n<=1e8

对于50%的数据，满足q<=50，a<=30，n<=1e12

对于100%的数据，满足q<=50000，a<=20000，n<=1e500

样例一解释：
询问1：lsq必胜，lsq先抽2^1=2，接下来无论wzt抽2^1=2或2^0=1，lsq只要把牌抽完；其他抽法同上（只是顺序不同）

询问2：wzt必胜，若lsq先抽2^0=1，则wzt抽2^3=8；若lsq先抽2^1=2，则wzt抽2^2=4，接下来无论lsq抽2^1=2或2^0=1，wzt只要把牌抽完；其他抽法同上（只是顺序不同）

询问3：lsq必胜，lsq只需拿走3^2=9即可

By [Broadway](https://www.luogu.org/space/show?uid=33509)


title: 荒芜的海洋

background:
在一个渺远的海洋中，一场世纪大战级别的游戏上演了。

感谢 [lsq](https://www.luogu.org/space/show?uid=26556) 本人参与验题

description:
这块海洋上有n个小岛，小岛有m座石桥相连。有一些小岛上有wzt埋下的奖赏，它们非常诱人。它们的诱惑力用整数ki描述。而一些小岛上有lsq的雇佣兵，他们有一个价格，用整数bi描述。lsq必须花钱，他的雇佣兵才会帮他寻找奖赏。

雇佣兵的价格并不会变。对于每一个雇佣兵，在寻找过程中，他会越过一座座的桥，这过程中，他的价格会 **加上他所经过的所有桥的长度** 。

遗憾的是，不只有桥的阻挡，每座岛上有许多猛兽，虽然雇佣兵们都英勇无比，但驱逐猛兽的过程会让人很不爽。因此，对于每一个雇佣兵，价格会 **加上他所经过的所有岛（包括出发岛）上的猛兽数量之和**。

lsq了解这里的一切情况，他需要做出决策，即决定他的每个雇佣兵应该去找哪个奖赏。lsq的目的是找到所有奖赏，并取得最大收益。每个雇佣兵只能雇佣一次。

收益的定义为： **所有奖赏的诱惑力减去lsq花的所有的钱**

lsq的决策异常艰难，于是只好请 ~~AK过NOI~~ 的你来帮忙。

inputFormat:
第一行4个数，n（小岛总数）,m（桥总数）,a（lsq的雇佣兵总人数）,b（奖赏总数）

接下来一行n个数，表示每个小岛上的猛兽数量

接下来m行，每行三个数u,v,w，表示u号小岛与v号小岛之间有一座长度为w的桥相连

接下来a行，每行两个数qi,pi，表示i号雇佣兵价格为qi，初始位置为pi号小岛

接下来b行，每行两个数ki,qi，表示i号奖赏的诱惑力为ki，位置为qi号小岛

outputFormat:
如果能找到所有奖赏，输出“Yes”，并在下一行输出能达到的最大满意度。

如果不能找到所有奖赏，输出“No”，并在下一行输出最多能找到多少奖赏。

hint:
对于30% 的数据，满足n<=200，m<=200，b<=a<=30

对于50% 的数据，满足n<=500，m<=800，b<=a<=100

对于100% 的数据，满足n<=1000，m<=15000，b<=a<=300，其余数据保证不会爆int(Pascal语言为longint)

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

By [Ebola](https://www.luogu.org/space/show?uid=20158)


title: 【模板】多项式乘法逆

background: 注意：本题并不属于中国计算机学会划定的提高组知识点考察范围。

description: 给定一个多项式 $F(x)$ ，请求出一个多项式 $G(x)$， 满足 $F(x) * G(x) \equiv 1 \pmod{x^n}$。系数对 $998244353$ 取模。

inputFormat:
首先输入一个整数 $n$， 表示输入多项式的项数。
接着输入 $n$ 个整数，第 $i$ 个整数 $a_i$ 代表 $F(x)$ 次数为 $i-1$ 的项的系数。

outputFormat: 输出 $n$ 个数字，第 $i$ 个整数 $b_i$ 代表 $G(x)$ 次数为 $i-1$ 的项的系数。保证有解。


title: 任意模数多项式乘法逆

description:
给定一个多项式 $F(x)$ ，请求出一个多项式 $G(x)$ ， 满足 $F(x) * G(x) \equiv 1 ( \mathrm{mod\:} x^n )$
 。系数对 $10^9+7$ 取模。

inputFormat:
首先输入一个整数 $n$， 表示输入 $F(x)$ 为 $n-1$ 次。
接着输入 $n$ 个整数，第 $i$ 个整数 $a_i$ 代表 $F(x)$ 次数为 $i-1$ 项的系数。

outputFormat: 输出 $n$ 个数字，第 $i$ 个整数 $b_i$ 代表 $G(x)$ 次数为 $i-1$ 的项的系数。


title: [JSOI2009] 等差数列

background: “一个长度为$l$的数列$a_i$，若相邻两数间的差$a_i - a_{i-1} \ (2 \leq i \leq l)$全部相同，则这个数列为等差数列。”火星特级数学老师jyy，正在给他的火星学生们上数学课。

description:
为了检验学生的掌握情况，jyy布置了一道习题：给定一个长度为$N$（$1 \leq N \leq 100,000$）的数列，初始时第$i$个数为$v_i$（$v_i$是整数，$-100,000 \leq v_i \leq 100,000$），学生们要按照jyy的给出的操作步骤来改变数列中的某些项的值。操作步骤的具体形式为：`A s t a b` （$s, t, a, b$均为整数，$1 \leq s \leq t \leq N$，$-100,000 \leq a, b \leq 100,000$），它表示，在序列的$[s, t]$区间上加上初值为$a$，步长为$b$的等差数列。即$v_i$变为$v_i + a + b \times (i - s)$（对于$s \leq i \leq t$）。

在焦头烂额地计算之余，可怜的火星学生们还得随时回答jyy提出的问题。问题形式为：`B s t`（$s, t$均为整数，$1 \leq s \leq t \leq N$），表示jyy询问当前序列的$[s, t]$区间最少能划分成几段，使得每一段都是等差数列。比如说`1 2 3 5 7`最少能划分成$2$段，一段是`1 2 3`，另一段是`5 7`。询问是需要同学们计算出答案后，作为作业交上来的。

虽然操作数加问题数总共只有$Q$（$1 \leq Q \leq 100,000$）个，jyy还是觉得这个题很无聊很麻烦。于是他想让你帮他算一份标准答案。

inputFormat:
第$1$行：$1$个整数$N$，第$2 \cdots N + 1$行：每行一个整数。第$i + 1$行表示$v_i$。

第$N + 2$行：$1$个整数$Q$，第$N + 3 \cdots N + Q + 2$行：每行描述了一个操作或问题，格式如题中所述，不含引号。

outputFormat: 若干行，每行一个整数，表示对一个问题的回答。请按照输入中的顺序依次给出回答。

hint:
**样例说明：**

原数列`1 3 -1 -4 7`。经过操作之后，数列变为`1 2 3 5 7`。如题中所述，最少能划分成$2$段。

**数据规模：**

对$30\%$的数据，$N, Q \leq 5000$。

对$100\%$的数据，$1 \leq N, Q \leq 100,000$。

其他数据范围见题面。


title: [SHOI2008] 仙人掌图 II

background:
题目这个II是和[SHOI2006的仙人掌图](https://www.luogu.org/problemnew/show/P4129)区分的，bzoj没有。
**但是实际上还是和bzoj1023是一个题目的**。

description:
如果某个无向连通图的任意一条边至多只出现在一条简单回路（simple cycle）里，我们就称这张图为仙人掌图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。

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

举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两个的简单回路里。另外，第三张图也不是仙人图，因为它并不是连通图。显然，仙人图上的每条边，或者是这张仙人图的桥（bridge），或者在且仅在一个简单回路里，两者必居其一。定义在图上两点之间的距离为这两点之间最短路径的距离。定义一个图的直径为这张图相距最远的两个点的距离。**现在我们假定仙人图的每条边的权值都是1，你的任务是求出给定的仙人图的直径**。

inputFormat: 输入的第一行包括两个整数n和m（1≤n≤50000以及0≤m≤10000）。其中n代表顶点个数，我们约定图中的顶点将从1到n编号。接下来一共有m行。代表m条路径。每行的开始有一个整数k（2≤k≤1000），代表在这条路径上的顶点个数。接下来是k个1到n之间的整数，分别对应了一个顶点，相邻的顶点表示存在一条连接这两个顶点的边。一条路径上可能通过一个顶点好几次，比如对于第一个样例，第一条路径从3经过8，又从8返回到了3，但是我们保证所有的边都会出现在某条路径上，而且不会重复出现在两条路径上，或者在一条路径上出现两次。

outputFormat: 只需输出一个数，这个数表示仙人图的直径长度。

hint:
对第一个样例的说明：6号点和12号点的最短路径长度为8，所以这张图的直径为8。

【注意】使用Pascal语言的选手请注意：你的程序在处理大数据的时候可能会出现栈溢出。
如果需要调整栈空间的大小，可以在程序的开头填加一句：{\$M 5000000}，其中5000000即指代栈空间的大小，请根据自己的程序选择适当的数值。


title: [JSOI2016] 最佳团体

description:
JSOI 信息学代表队一共有 $N$ 名候选人，这些候选人从 $1$ 到 $N$ 编号。方便起见，JYY 的编号是 $0$ 号。每个候选人都由一位编号比他小的候选人$R_i$ 推荐。如果 $R_i = 0$，则说明这个候选人是 JYY 自己看上的。

为了保证团队的和谐，JYY 需要保证，如果招募了候选人 $i$，那么候选人 $R_i$ 也一定需要在团队中。当然了，JYY 自己总是在团队里的。每一个候选人都有一个战斗值 $P_i$ ，也有一个招募费用 $S_i$ 。JYY 希望招募 $K$ 个候选人（JYY 自己不算），组成一个性价比最高的团队。也就是，这 $K$ 个被 JYY 选择的候选人的总战斗值与总招募费用的比值最大。

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

接下来 $N$ 行，其中第 $i$ 行包含三个整数 $S_i$ , $P_i$ , $R_i$ ,
表示候选人 $i$ 的招募费用，战斗值和推荐人编号。

outputFormat: 输出一行一个实数，表示最佳比值。答案保留三位小数。


title: 【模板】任意模数多项式乘法

background: 模板题，无背景

description:
给定 $2$ 个多项式 $F(x), G(x)$ ，请求出 $F(x) * G(x)$。

**系数对 $p$ 取模**，且**不保证** $p$ 可以分解成 $p = a \cdot 2^k + 1$ 之形式。

inputFormat:
输入共 $3$ 行。
第一行 $3$ 个整数 $n, m, p$，分别表示 $F(x), G(x)$ 的次数以及模数 $p$ 。
第二行为 $n+1$ 个整数，第 $i$ 个整数 $a_i$ 表示 $F(x)$ 的 $i-1$ 次项的系数。
第三行为 $m+1$ 个整数，第 $i$ 个整数 $b_i$ 表示 $G(x)$ 的 $i-1$ 次项的系数。

outputFormat: 输出 $n+m+1$ 个整数， 第 $i$ 个整数 $c_i$ 表示 $F(x) * G(x)$ 的 $i-1$ 次项的系数。


title: [SHOI2008] 堵塞的交通

description:
有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可以被看成是一个 $2$ 行 $C$ 列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有 $2C$ 个城市和 $3C-2 $条道路。

小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通，直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事，部长听说你来自一个科技高度发达的世界，喜出望外地要求你编写一个查询应答系统，以挽救已经病入膏肓的小人国交通系统。 小人国的交通部将提供一些交通信息给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式：

- `Close r1 c1 r2 c2`：相邻的两座城市 $(r_1, c_1)$ 和 $(r_2, c_2)$ 之间的道路被堵塞了；
- `Open r1 c1 r2 c2`：相邻的两座城市 $(r_1, c_1)$ 和 $(r_2, c_2)$ 之间的道路被疏通了；
- `Ask r1 c1 r2 c2`：询问城市 $(r_1, c_1)$ 和 $(r_2, c_2)$ 是否连通。如果存在一条路径使得这两条城市连通，则返回 `Y`，否则返回 `N`。

*注：$r_i$ 表示行数，$c_i$ 表示列数，$1 \leq r_i \leq 2, 1 \leq c_i \leq C$。*

inputFormat: 第一行只有一个整数 $C$，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行 `Exit` 作为结束。我们假设在一开始所有的道路都是堵塞的。我们保证 $C$ 小于等于 $100000$，信息条数小于等于 $100000$。

outputFormat: 对于每个查询，输出一个 `Y` 或 `N`。

samples:
2
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit


title: [AHOI2013] 差异

description:
给定一个长度为 $n$ 的字符串 $S$，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求

$$\displaystyle \sum_{1\leqslant i<j\leqslant n}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j)$$

其中，$\text{len}(a)$ 表示字符串 $a$ 的长度，$\text{lcp}(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。

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

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

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

- 对于 $100\%$ 的数据，保证 $2\le n\le 500000$，且 $S$ 中均为小写字母。


title: [清华集训2012] 序列操作

background: **滥用评测功能将被封号。**

description:
有一个长度为 $n$ 的序列，有三个操作：

1. `I a b c` 表示将 $[a,b]$ 这一段区间的元素集体增加 $c$；
2. `R a b`表示将 $[a,b]$ 区间内所有元素变成相反数；
3. `Q a b c` 表示询问 $[a,b]$ 这一段区间中选择 $c$ 个数相乘的所有方案的和 $\mod 19940417$ 的值。

inputFormat:
第一行两个数 $n, q$ 表示序列长度和操作个数。

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

接下来 $q$ 行每行输入一个操作 `I a b c` 或者 `R a b` 或者 `Q a b c`，意义如题目描述。

outputFormat: 对于每个询问，输出选出 $c$ 个数相乘的所有方案的和 $\mod 19940417$ 的值。

hint:
**样例说明：**

做完第一个操作序列变为 `1 3 4 4 5`。

第一次询问结果为 $3 \times 4+3 \times 4+4 \times 4=40$。

做完 `R` 操作变成 `-1 -3 -4 -4 -5`。

做完 `I` 操作变为 `-2 -4 -5 -4 -5`。

第二次询问结果为 $-2-4-5-4-5=-20$。

**数据范围：**

对于 $100\%$ 的数据，$n \leq 50000, q \leq 50000$。初始序列的元素的绝对值 $\leq 10^9$，保证 $[a,b]$ 是一个合法区间，`I` 操作中 $|c| \leq 10^9$，`Q` 操作中 $1 \leq c \leq \min(b-a+1,20)$。


title: [WC2007] 剪刀石头布

description:
在一些一对一游戏的比赛（如下棋、乒乓球和羽毛球的单打）中，我们经常会遇到 $A$ 胜过 $B$，$B$ 胜过 $C$ 而 $C$ 又胜过 $A$ 的有趣情况，不妨形象的称之为剪刀石头布情况。有的时候，无聊的人们会津津乐道于统计有多少这样的剪刀石头布情况发生，即有多少对无序三元组 $(A,B,C)$，满足其中的一个人在比赛中赢了另一个人，另一个人赢了第三个人而第三个人又胜过了第一个人。注意这里无序的意思是说三元组中元素的顺序并不重要，将 $(A, B, C)$、$(A, C, B)$、$(B, A, C)$、$(B, C, A)$、$(C, A, B)$ 和 $(C, B, A)$ 视为相同的情况。

有 $N$ 个人参加一场这样的游戏的比赛，赛程规定任意两个人之间都要进行一场比赛：这样总共有 $\frac{N*(N-1)}{2}$ 场比赛。比赛已经进行了一部分，我们想知道在极端情况下，比赛结束后最多会发生多少剪刀石头布情况。即给出已经发生的比赛结果，而你可以任意安排剩下的比赛的结果，以得到尽量多的剪刀石头布情况。

inputFormat:
输入文件的第 $1$ 行是一个整数 $N$，表示参加比赛的人数。

之后是一个 $N$ 行 $N$ 列的数字矩阵：一共 $N$ 行，每行 $N$ 列，数字间用空格隔开。

在第 $(i+1)$ 行的第 $j$ 列的数字如果是 $1$，则表示 $i$ 在已经发生的比赛中赢了 $j$；该数字若是 $0$，则表示在已经发生的比赛中 $i$ 败于 $j$；该数字是
 $2$，表示 $i$ 和 $j$ 之间的比赛尚未发生。数字矩阵对角线上的数字，即第 $(i+1)$ 行第 $i$ 列的数字都是 $0$，它们仅仅是占位符号，没有任何意义。

输入文件保证合法，不会发生矛盾，当 $i \neq j$ 时，第 $(i+1)$ 行第 $j$ 列和第 $(j+1)$ 行第 $i$ 列的两个数字要么都是 $2$，要么一个是 $0$ 一个是 $1$。

outputFormat:
输出文件的第 $1$ 行是一个整数，表示在你安排的比赛结果中，出现了多少剪刀石头布情况。

输出文件的第 $2$  行开始有一个和输入文件中格式相同的 $N$ 行 $N$ 列的数字矩阵。第 $(i+1)$ 行第 $j$ 个数字描述了 $i$ 和 $j$ 之间的比赛结果，$1$ 表示 $i$ 赢了 $j$，$0$ 表示 $i$ 负于 $j$，与输入矩阵不同的是，在这个矩阵中没有表示比赛尚未进行的数字 $2$；对角线上的数字都是 $0$。输出矩阵要保证合法，不能发生矛盾。

hint:
### 【评分标准】
对于每个测试点，仅当你的程序的输出第一行的数字和标准答案一致，且给出了一个与之一致的合法方案，你才能得到该测试点的满分，否则该测试点得 $0$ 分。
### 【数据范围】
$30\%$ 的数据中，$N \leq 6$；

$100\%$ 的数据中，$N \leq 100$。


title: [SCOI2015] 小凸想跑步

description:
小凸晚上喜欢到操场跑步，今天他跑完两圈之后，他玩起了这样一个游戏。

操场是个凸 $n$ 边形， $n$ 个顶点按照逆时针从 $0$ ∼ $n - 1$ 编号。现在小凸随机站在操场中的某个位置，标记为 $p$ 点。将 $p$ 点与 $n$ 个顶点各连一条边，形成 $n$ 个三角形。如果这时 $p$ 点， $0$ 号点， $1$ 号点形成的三角形的面
积是 $n$ 个三角形中最小的一个，小凸则认为这是一次正确站位。

现在小凸想知道他一次站位正确的概率是多少。

inputFormat:
第 $1$ 行包含 $1$ 个整数 $n$, 表示操场的顶点数和游戏的次数。

接下来有 $n$ 行，每行包含 $2$ 个整数 $x_i, y_i$，表示顶点的坐标。

输入保证按逆时针顺序输入点，所有点保证构成一个凸多边形。所有点保证不存在三点共线。

outputFormat: 输出 $1$ 个数，正确站位的概率，保留 $4$ 位小数。


title: [SCOI2015] 小凸玩矩阵

description: 小凸和小方是好朋友，小方给了小凸一个 $n$ × $m$ $(n \leq m)$ 的矩阵 $A$，并且要求小凸从矩阵中选出 $n$ 个数，其中任意两个数都不能在同一行或者同一列。现在小凸想知道，选出的 $n$ 个数中第 $k$ 大的数的最小值是多少。

inputFormat:
第 $1$ 行读入 $3$ 个整数 $n, m, k$。

接下来 $n$ 行，每一行有 $m$ 个数字，第 $i$ 行第 $j$ 个数字代表矩阵中第 $i$ 行第 $j$ 列的元素 $A_{i,j}$。

outputFormat: 输出包含一行，为选出的 $n$ 个数中第 $k$ 大数的最小值。

hint:
对于 $20$% 的数据， $1 \leq n \leq m \leq 9$

对于 $40$% 的数据， $1 \leq n \leq m \leq 22, 1 \leq n \leq 12$

对于 $100$% 的数据， $1 \leq k \leq n \leq m \leq 250, 1 \leq A_{i,j} \leq 10^9$


title: 变化的道路

description:
小 w 和小 c 在 H 国，近年来，随着 H 国的发展，H 国的道路也在不断变化着

根据 H 国的道路法，H 国道路都有一个值 $w$，表示如果小 w 和小 c 通过这条道路，那么他们的 L 值会减少 $w$，但是如果小 w 和
小 c 在之前已经经过了这条路，那么他们的 L 值不会减少

H 国有 $N$ 个国家，最开始 H 国有 $N-1$ 条道路，这 $N-1$ 条道路刚好构成一棵树

小 w 将和小 c 从 H 国的城市 1 出发，游览 H 国的所有城市，总共游览 32766 天，对于每一天，他们都希望游览结束后 L 值还是一个正数，
那么他们出发时 L 值至少为多少

H 国的所有边都是无向边，没有一条道路连接相同的一个城市

inputFormat:
输入第 1 行，一个整数$N$

输入第 2 至第 $N$ 行，每行三个正整数$u, v, w$，表示城市 $u$ 与城市 $v$ 有一条值为 $w$ 道路

输入第 $N+1$ 行，一个整数 $M$，表示 H 国有 $M$ 条正在变化的道路

输入第 $N+2$ 行到第 $N+M+1$ 行，每行 5 个整数 $u, v, w, l, r$，表示城市 $u$ 到城市 $v$ 有一条值为 $w$ 的道路，
这条道路存在于第 $l$ 天到第 $r$ 天

outputFormat: 输出共 32766 行，第 $i$ 行表示第 $i$ 天游览的 L 值至少为多少

samples:
7
9
13
由于版面原因，仅显示三行，接下来32763行都是13


title: [JSOI2008] Blue Mary 开公司

background: Blue Mary 最近在筹备开一家自己的网络公司。由于他缺乏经济头脑，所以先后聘请了若干个金融顾问为他设计经营方案。

description:
万事开头难，经营公司更是如此。开始的收益往往是很低的，不过随着时间的增长会慢慢变好。也就是说，**对于一个金融顾问 $i$，他设计的经营方案中，每天的收益都比前一天高，并且均增长一个相同的量 $P_i$。**

由于金融顾问的工作效率不高，**所以在特定的时间，Blue Mary 只能根据他已经得到的经营方案来估算某一时间的最大收益**。由于 Blue Mary 是很没有经济头脑的，所以他在估算每天的最佳获益时完全不会考虑之前的情况，而是直接从所有金融顾问的方案中选择一个在当天获益最大的方案的当天的获益值，例如：

有如下两个金融顾问分别对前四天的收益方案做了设计：

|   | 第一天 | 第二天 | 第三天 | 第四天 | $P_i$ |
| :-: | :-: | :-: | :-: | :-: | :-: |
| 顾问 1 | $1$ | $5 $| $9$ | $13$ | $4$ |
| 顾问 2 | $2$ | $5$ | $8$ | $11$ | $3$ |

在第一天，Blue Mary 认为最大收益是 $2$（使用顾问 2 的方案），而在第三天和第四天，他认为最大收益分别是 $9$ 和 $13$（使用顾问 1 的方案）。而他认为前四天的最大收益是：$2 + 5 + 9 + 13 = 29$。

现在你作为 Blue Mary 公司的副总经理，会不时收到金融顾问的设计方案，也需要随时回答 Blue Mary 对某天的“最大收益”的询问（这里的“最大收益”是按照 Blue Mary 的计算方法）。**一开始没有收到任何方案时，你可以认为每天的最大收益值是 0**。下面是一组收到方案和回答询问的例子：

- 询问 $2$，回答 $0$。
- 收到方案：$0\ 1\ 2\ 3\ 4\ 5\ \cdots$
- 询问 $2$，回答 $1$。
- 收到方案：$2\ 2.1\ 2.2\ 2.3\ 2.4\ \cdots$
- 询问 $2$，回答 $2.1$。

inputFormat:
第一行 ：一个整数 $N$，表示方案和询问的总数。

接下来 $N$ 行，每行开头一个单词 `Query` 或 `Project`。

若单词为 `Query`，则后接一个整数 $T$，表示 Blue Mary 询问第 $T$ 天的最大收益。

若单词为 `Project`，则后接两个实数 $S, P$，表示该种设计方案第一天的收益 $S$，以及以后每天比上一天多出的收益 $P$。

outputFormat: 对于每一个 `Query`，输出一个整数，表示询问的答案，并精确到整百元（以百元为单位，例如：该天最大收益为 $210$ 或 $290$ 时，均应该输出 $2$）。没有方案时回答询问要输出 $0$。

hint:
**数据范围**

$1 \leq N \leq 10 ^ 5$，$1 \leq T \leq 5\times 10 ^ 4$，$0 < P < 100$，$|S| \leq 10 ^ 5$。

**提示**

本题读写数据量可能相当巨大，请选手注意选择高效的文件读写方式。


title: [SCOI2015] 小凸玩密室

description: 小凸和小方相约玩密室逃脱，这个密室是一棵有 $n$ 个节点的完全二叉树，每个节点有一个灯泡。点亮所有灯泡即可逃出密室。每个灯泡有个权值 $a_i$，每条边也有个权值 $b_i$。点亮第一个灯泡不需要花费，之后每点亮一个新的灯泡 $v$ 的花费，等于上一个被点亮的灯泡 $u$ 到这个点 $v$ 的距离 $D_{u,v}$，乘以这个点的权值 $a_v$。在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。请告诉他们，逃出密室的最少花费是多少。

inputFormat:
第 $1$ 行包含 $1$ 个数 $n$，代表节点的个数

第 $2$ 行包含 $n$ 个数，代表每个节点的权值 $a_i$。 $(i = 1, 2,$……$, n)$

第 $3$ 行包含 $n - 1$ 个数，代表每条边的权值 $b_i$，第 $i$ 号边是由第 $(i+1)/2$ 号点连向第 $i + 1$ 号点的边。$(i = 1, 2,$……$, n - 1)$

outputFormat: 输出包含 $1$ 个数，代表最少的花费。


title: 可爱の#10数字划分

background: 可可可可可可爱的付公主 qwq 有 $n$ 个数，$1\sim n$，每个数都有价值 $V_i$，你要将它们划分成若干个集合，每个数属于一个集合。

description:
我们这里规定:

1. 质数只能和质数分在同一个集合。
2. 合数只能和合数分在同一个集合（$1$ 也算在合数内）。
3. 我们假设目前所有质数集合的并集为 $U$（也就是之前所有质数集合以及 $S$ 的并集），每个质数集合 $S$ 的价值定义如下：
$$V_S=\frac {(\sum_{i\in S}V_i)^p} {\prod_{i\in U}V_i}$$

4. 我们定义每个合数集合 $S$ 的价值如下:

令 $k=|S|$，我们用这 $k$ 个数分别作为 $k$ 条边的权值，连接 $k+1$ 个点，构成一棵树。对于一个排列 $P(1\sim k+1)$，价值为：

$$V_P=\sum_{i=1}^{n-1} f(P_i,P_{i+1})$$

其中 $f(u,v)$ 为路径 $(u,v)$ 上最大的边权。

集合 $S$ 的价值为：

$$V_S=E(\min\{V_P\})\times|S|$$

其中 $E(X)$ 代表 $X$ 的数学期望，期望是针对所有可能的有标号无根树，$\min$ 是针对所有可能的 $P$。这时集合内所有元素都不同，也就是所有边不同。

5. 一个划分方案的价值定义为所有集合的价值的乘积。
6. 两个划分方案相同当且仅当它们中所有集合对应相同，且质数集合的相对顺序相同。

现在给定 $n,p$ 和 $V_i$，请你求出所有合法的不同划分方案的价值之和。

结果对 $10^9+7$ 取模，除法请使用乘法逆元。

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

第二行输入 $n$ 个正整数 $V_i$。

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