title: [JSOI2011] Apple 的美食

description:
Apple 很喜欢吃巧克力，但它是一头挑剔的猪，有的品种的巧克力并不能满足它的胃口。如果主人给它的巧克力它不喜欢吃，它就会很不开心。主人并不知道，什么样的巧克力 Apple 喜欢吃，但她知道巧克力的可可含量是巧克力
口感的重要因素，因此她决定根据巧克力的可可含量来判断什么样的巧克力拿给 Apple 吃，什么样的巧克力不拿给 Apple 吃。

假设一块巧克力的可可含量有 $1\sim N$ 种不同的计量，则她认为可可含量在 $[a,b]$ 的范围内的巧克力是好吃的
。不过她不知道的这个范围到底是多少，需要你来帮忙确定这个范围，使得她可以让 Apple 吃到最多的喜欢吃的巧克力。

设 $pos_i$ 是可可脂含量为 $i$，且 Apple 认为是好吃的巧克力的数量，$neg_i$ 是可可脂含量为 $i$，且 Apple 认为是不好吃的巧克力的数量。这两个序列由以下方法生成：
$$\begin{cases}pos_i=a_{2i-1}\\neg_i=a_{2i}\end{cases}$$

其中，$a_i=(p_1a_{i-1}+p_2)\bmod M(i>1)$。

设 $TP$ 是 Apple 认为好吃的、且被主人认为是好吃的巧克力数量，$TN$ 是Apple 认为不好吃的、且被主人认为是不好吃的巧克力数量，$FP$ 是 Apple 认为不好吃的、且被主人认为是好吃的巧克力数量，$FN$ 是 Apple 认为好吃的、且被主人认为是不好吃的巧克力数量。

设 $r$ 为被正确判断为好吃的巧克力数占所有好吃的巧克力的比率，$p$ 为被正确判断为好吃的巧克力占所有被判定为好吃的巧克力数的比率，则

$$\begin{cases}r=\frac{TP}{TP+FN}\\p=\frac{TP}{TP+FP}\end{cases}$$

请你帮助 Apple 求出一个范围，使得 $f=\frac{2pr}{p+r}$ 最大。

inputFormat:
输入由若干行组成，每行是一组数据：$N,a_1,p_1,p_2,M$，中间用空格分开。

输入以一个 $0$ 结束，数据组数不超过 $1000$。

outputFormat: 每组数据输出一行，为 $f$ 的最大值（四舍五入保留 $6$ 位小数）。

hint:
### 数据范围

对于 $100\%$ 的数据，$1\leq N\leq 10^6,a_1,p_1,p_2<M\leq 20$，保证至少有一块 Apple 认为好吃的巧克力。


title: 「JYLOI Round 1」让

type: P

description:
Alice 和 Bob 在玩游戏。

现在有多堆石子，其中第 $k$ 堆石子有 $p_k$ 个，先后手轮流操作。取石子时，可以选任意一堆进行操作。若记 $i$ 为在这次取之前这堆石子的个数，$j$ 为这次要取的石子数，$R$ 为给定的常数，则需满足以下条件：

$$1 \leq i + j \leq R,i \geq j \geq 1$$

使对方无法操作者即为胜者。游戏时，双方都采用最优策略。

有多次游戏，具体来说，共有 $T$ 个操作，分为两类：

1. “``change x``” 表示将 $R$ 更改为 $x$。

2. “``query n``” 表示进行一次游戏，接下来有 $n$ 行，这 $n$ 行中的第 $i$ 行有两个正整数 $l_i$ 和 $r_i$，表示这次游戏的石子的堆数和个数可以用这 $n$ 个区间来表示。第 $i$ 个区间表示这次游戏的石子的堆数新增了 $(r_i - l_i + 1)$ 堆，并且其中这个区间所表示的第 $j(1 \leq j \leq r_i - l_i + 1)$ 堆的石子个数为 $(l_i + j - 1)$。

	例如当这次游戏的 $n = 2$，并且两个区间分别为 $[1, 7]$ 和 $[2, 3]$ 的时候，这次游戏一共有 $[(7 - 1 + 1) + (3 - 2 + 1)] = 9$ 堆石子，这 $9$ 堆石子的个数分别为 $1, 2, 3, 4, 5, 6, 7, 2, 3$。

由于 Bob 和 Alice 都非常聪明，而 Bob 希望不赢太多次，在适当的时候让让 Alice。因而他希望你帮他编写一个程序，对于每次游戏，如果先手有必胜策略输出“``1``”，否则输出“``0``”，你能做到吗？

inputFormat:
第一行有一个正整数 $T$，表示操作的个数。

接下来有 $T$ 个操作，格式如题所述。

outputFormat: 输出共一行，为一个长度小于 $T$ 的由字符 0 和 1 组成的字符串，含义如题所述。

samples:
5
change 3
query 1
2 2
change 4
query 1
2 2
change 2

hint:
### 样例 1 说明

共有 $T=5$ 个操作。

第 1 个操作将 $R$ 改成了 3。

第 2 个操作表示进行了一次游戏，这次游戏的 $n=1$，区间为 $[2, 2]$，表示这次游戏共有 $(2 - 2 + 1) = 1$ 堆石子，这 1 堆石子的个数为 $(2 + 1 - 1) = 2$。因为 $R=3$，因此先手最多只能够取 1 个。若取 2 个则不满足 **题目描述** 中的条件 $1 \leq i + j \leq R$，若取 3 个及以上则不满足 **题目描述** 中的条件 $1 \leq i + j \leq R,i \geq j \geq 1$，其中 $i$、$j$、$R$ 的含义如题所述。先手取完后唯一的一堆只剩下 1 颗石子，因为后手取了 1 颗石子后使先手无法操作，所以先手落败，又因为这是唯一的一种取法，所以先手必败，因此先手无必胜策略，输出“``0``”。

第 3 个操作将 $R$ 改成了 4。

第 4 个操作表示进行了一次游戏，这次游戏的 $n=1$，区间为 $[2, 2]$，表示这次游戏共有 $(2 - 2 + 1) = 1$ 堆石子，这 1 堆石子的个数为 $(2 + 1 - 1) = 2$。先手最多可以取 2 颗石子，因为当先手取 3 颗或以上时，不满足 **题目描述** 中的条件 $1 \leq i + j \leq R,i \geq j \geq 1$，其中 $i$、$j$、$R$ 的含义如题所述。因为当先手选择取 2 颗石子时，先手取完了所有石子，使后手无法操作，所以先手必胜，输出“``1``”。

第 5 个操作将 $R$ 改成了 2。

____________

### 数据范围

对于 $100\%$ 的数据，满足 $1 \leq T \leq 10^5, 2 \leq R \leq 10^{15}, 0 \leq l_i \leq r_i < R, 1 \leq \sum{n} \leq 5 \times 10^5$，并且第一个操作一定是第 1 类操作。

对于测试点 1~2 ，满足 $T \leq 10, l_i \leq r_i \leq 3$，并且在一轮游戏中石子的堆数不会超过 4。

对于测试点 3~6 ，满足 $T \leq 100, R \leq 100, \sum{n} \leq 100$。

对于测试点 7~10 ，满足 $T \leq 10, R \leq 10^5, \sum{n} \leq 50$。

对于测试点 11~12 ，满足 $R \leq 5 \times 10^3, \sum{n} \leq 5 \times 10^5$，并且只有一次修改操作。

对于测试点 13~16 ，满足 $T \leq 10^5,R \leq 10^5,\sum{n} \leq 5 \times 10^5$。

共 20 个测试点，每个测试点 5 分。

## 题目来源

「JYLOI Round 1」 E

Idea / Solution / Data：abcdeffa


title: [CTSC2000] 采矿

background: 一架人类的航天飞机将人类基地建在了一个荒芜的星球上。面对紧缺的能源，他们只能在最短的时间内用 $\text{SCV}$ （一种智能机器人）采集必须的矿藏。对于这个艰巨的任务，他们希望得到编程高手们的帮助。

description:
在这个星球上，有着两种不同的矿。一种被称为“冰矿”，是一种类似 $\text{H}_{2}\text{O}$ 的凝固物的蓝色高能矿藏。另一种被称为“气矿”，是四氯化碳的一种异态形式。

人类通过这两种矿的提炼，获得可供生存的能源。 $\text{SCV}$ 是一种唯一可以采集这两种矿的智能机器人。他们每采集一次冰矿需要花费 $t_{1}$ 的时间，每采集一次气矿需要花费 $t_{2}$ 的时间。采集结束后，将得到 $8$ 个冰矿或者 $8$ 个气矿单位。**每一次 $\text{SCV}$ 只能采集冰矿或者是气矿中的一种**。

 $\text{SCV}$ 可以通过主基地制造。每制造一个 $\text{SCV}$ ，主基地将花费 $50$ 单位的冰矿。而主基地由于制造能力有限，在同一时间只能制造**一个** $\text{SCV}$ 。制造一个 $\text{SCV}$ 需要 $t_{3}$ 的时间。

在开始时，人类拥有 $50$ 个单位的冰矿和 $4$ 个 $\text{SCV}$ 。他们需要采集到 $p_{1}$ 单位的冰矿和 $p_{2}$ 单位的气矿。请计算出他们需要的**最短时间**。

outputFormat: 输出文件只包含一个数字，表示可以达到目标的最少时间。


title: 选择客栈 加强版

description:
丽江河边有 $n$ 家很有特色的客栈，客栈按照其位置顺序从 $1$ 到 $n$ 编号。

每家客栈都按照某一种色调进行装饰（总共 $k$ 种，用整数 $0 \sim k-1$ 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。

两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。

晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 $p$ 。

他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 $p$ 元的咖啡店小聚。

inputFormat:
输入共 $n+1$ 行。

第一行三个整数 $n,k,p$，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值。

接下来的 $n$ 行，第 $i+1$ 行两个整数，之间用一个空格隔开，分别表示 $i$ 号客栈的装饰色调和 $i$ 号客栈的咖啡店的最低消费。

outputFormat: 输出一行一个整数，表示可选的住宿方案的总数。

hint:
【样例解释】

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|}\hline
\textsf{客栈编号} & \text{①} & \text{②} & \text{③} & \text{④} & \text{⑤} \\\hline
\textsf{色调} & 0 & 1 & 0 & 1 & 1 \\\hline
\textsf{最低消费} & 5 & 3 & 2 & 4 & 5 \\ \hline
\end{array}$$

二人要住同样色调的客栈，所有可选的住宿方案包括：住客栈①③，②④，②⑤，④⑤。

但是若选择住 ④⑤ 号客栈的话，④⑤ 号客栈之间的咖啡店的最低消费是 $4$，而两人能承受的最低消费是 $3$ 元，所以不满足要求。因此只有前 $3$ 种方案可选。

【数据范围】
对于 $25\%$ 的数据，$n\leq 100$；
对于 $40\%$ 的数据，$n\leq 1000$；
对于 $80\%$ 的数据，$n\leq 2 \times 10^5$，$k \leq 50$；
对于 $100\%$ 的数据，$2\leq n\leq2\times 10^6$，$1 \le k\leq 10^4$，$0\leq p\leq 100$，$0\leq$ 最低消费 $\leq 100$ 。


title: [CTSC2000] 快乐的蜜月

background: 位于某个旅游胜地的一家宾馆里，有一个房间是总统套房。由于总统套房价格昂贵，因此常常无人光临。宾馆的经理为了创收，决定将总统套房改建为专门为新婚夫妇服务的蜜月房。宾馆经理不仅大幅度降低了蜜月房的价位，而且还对不同身份的顾客制定了不同的价位，以吸引不同身份、不同消费水平的游客。比如对于来订蜜月房的国内来宾、海外旅客、港澳台同胞等，区别收取费用。宾馆经理的举措获得了不同凡响的效果。由于蜜月房环境幽雅，服务周到，因此生意红火。

description:
宾馆经理在每年年底都会收到第二年的所有蜜月房预订单。每张预订单包括以下几个必要的信息：**到达日期、离去日期和顾客身份**。

由于宾馆**只有一间蜜月房，只能同时接待一对新婚夫妇**。因此并不是所有的预订要求都能得到满足。

当一些预订要求**在时间上发生了重叠**的时候，我们就称这些预订要求发生了冲突。

对于那些不与任何其他预订要求发生冲突的预订单，它们**必然会被接受**。因为这对宾馆和顾客双方面来说都是件好事。

而对于发生冲突的预订要求，宾馆经理则**必须拒绝其中的一部分**，以保证宾馆有秩序地运转。

显然，对于同一时间内发生冲突的预定要求，宾馆经理**最多只能接受其中的一个**。经理也有可能**拒绝同一时间段内的所有预定要求**，因为这样可以避免顾客间发生争执。

经理在做出决策后，需要将整个计划公布于众，以示公平。这是一个必须慎重的决定，因为它牵涉到诸多方面的因素。经理首先考虑的当然是利润问题。他必然希望获得尽可能多的收入。可是宾馆在获得经济效益的同时，同时也应该兼顾到社会效益，不能太惟利是图，还必须照顾到顾客们的感情。如果宾馆经理单从最大获利角度出发来决定接受或拒绝顾客的预订要求的话，就会引起人们的不满。

经理有一个学过市场营销学的顾问。顾问告诉经理，可以采取一种折中的做法，放弃牟利最大的方案，而采纳获利第 $k$ 大的方案。他还通过精确的市场分析，找到了 $k$ 的最佳取值点，告诉了宾馆经理。

现在请你帮助宾馆经理，从一大堆预订要求中，在上述原则下寻找到获利第 $k$ 大的方案。宾馆经理将根据此方案来决定接受和拒绝哪些预订要求。

当然，可能有若干种方案的获利是一样大的。这时候，它们同属于获利第 $i$ 大的方案而不区分看待。例如，假如有 $3$ 种方案的收入同时为 $3$ ，有 $2$ 种方案的收入为 $2$ ，则收入为 $3$ 的方案都属于获利最大，收入为 $2$ 的方案都属于获利第二大。依次类推。

假设所有的住、离店登记都在中午 $12$ 点进行。

inputFormat:
输入文件的第一行是两个数，$k$ 和 $t$ 。其中 $k$ 表示需要选择获利第 $k$ 大的方案； $t$ 表示顾客的身份共划分为 $t$ 类。

第二行是一个数 $y$ ，表示下一年的年份。

第三行是一个数 $r$ ，表示共有 $r$ 个预订要求。

以下 $r$ 行每行是一个预订要求，格式为：`m1/d1 TO m2/d2 id`；

其中 $m_1,d_1$ 和 $m_2,d_2$ 分别表示到达和离去日期。 $id$ 是一个整数 （$1 \leq id \leq t$） ，用来标识预订顾客的身份。

最后 $t$ 行每行为一个整数 $P_{i}$ ($1 \leq i \leq t$）表示蜜月房对于身份代号为 $i$ 的顾客的日收费标准。

例：某对顾客于 $6$ 月 $1$ 日到达， $6$ 月 $3$ 日离去，对他们的日收费标准为 $m$ 元/天，则他们共住店两天，需付钱 $2m$ 元。

outputFormat: 输出文件仅包含一个整数 $p$ ，表示在获利第 $k$ 大的方案下，宾馆的年度总收入额。如果获利第 $k$ 大的方案不存在，则输出 $-1$ 。


title: [CTSC2000] 逻辑范式

description:
逻辑学是对命题以及命题真假性进行研究的一门科学。命题一般用一个小写字母表示，任何命题的值非真即假。我们用 `T` 表示命题的值为真，用 `F` 表示命题的值为假。

命题间的运算符称为命题操作联结词，简称联结词。逻辑系统中最基本的三个联结词是非、且和或，为了简便，我们用 $!$ 表示联结词非，用 $\&$ 表示联结词且，用 $|$ 表示联结词或。

联结词非是一个一元联结词，对于任意命题 $p$ ，$!p$ 的真值总是和 $p$ 相反。

联结词且又称合取，是一个二元联结词，对于任意命题 $p$ 和 $q$ ，当且仅当 $p$ 和 $q$ 同为真时， $p\&q$ 为真，否则 $p\&q$ 为假。

联结词或又称析取，是一个二元联结词，对于任意命题 $p$ 和 $q$ ，当且仅当 $p$ 和 $q$ 同为假时， $p|q$ 为假，否则 $p|q$ 为真。

下面给出三个基本命题运算联结词的真值表：

| 命题 $p$ | 命题 $q$ | $!p$ | $p\&q$ | $p\|q$   |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| T | T | F | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | T | T | F | T |
| F | F | T | F | F |

逻辑表达式是由命题、联结词和括号组成的。它的定义如下：

`<表达式>      ::=<合取式> or <析取式> or <否定式> or (<表达式>) or <元素>`

`<合取式>      ::=<表达式>&<表达式>`

`<析取式>      ::=<表达式>|<表达式>`

`<否定式>      ::=!<表达式>`

`<元素>      ::=<命题>`

注：其中 <命题> 是 $a$ 到 $z$ 的小写字母，`::=` 表示定义为， `or` 表示或。

对表达式的求值过程是根据表达式中各命题的值和真值表进行命题运算操作的过程。运算优先级为 $()$ 、 $!$ 、 $\&$ 和 $|$ 。$\&$ 和 $|$ 的优先级相同。相同优先级从左到右运算。

与或非逻辑范式（这里简称为范式）是一种逻辑表达式，它能够符合特定的真值表。例如一般逻辑里定义的蕴涵运算 $\rightarrow$ 的真值表为：

| 命题 $p$ | 命题 $q$ | $p \rightarrow q$ |
| :----------: | :----------: | :----------: |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |

我们可以用表达式 $!p|q$ 来表示这个蕴涵运算。表达式  $!p|q$ 的真值表为：

| 命题 $p$ | 命题 $q$ | $!p\|q$ |
| :----------: | :----------: | :----------: |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |

这样，我们就说 $p \to q$ 的范式为 $!p|q$ 。

完备定理告诉我们，对于任意一个 $n$ 元逻辑运算函数 $A$ ，已知 $A$ 的真值表，总可以求出 $A$ 的范式。范式只含命题、三个基本联结词和括号。例如，下面是一个三元运算 $A(p,q,r)$ 的真值表：

| 命题 $p$ | 命题 $q$ | 命题 $r$ | $A(p,q,r)$ |
| :----------: | :----------: | :----------: | :----------: |
| T | T | T | T |
| T | T | F | T |
| T | F | T | T |
| T | F | F | F |
| F | T | T | T |
| F | T | F | F |
| F | F | T | F |
| F | F | F | F |

也就是说，在命题 $p,q,r$ 有两个或两个以上为真时， $A$ 为真；反之 $A$ 为假。

当然，范式并不是唯一的。假设存在一种 $A$ 的范式为 $(p\&q\&r)|(!p\&q\&r)|(p\&!q\&r)|(p\&q\&!r)$ ， 表达式 $(p\&q)|(q\&r)|(p\&r)$ 也是 $A$ 的范式，并且它的长度比前式更短。

我们的要求是：给定 $n$ 元函数 $A$ 的真值表，求 $A$ 的范式，并要求范式尽可能短。

inputFormat: 输入文件第一行为 $n$（$n \leq 6$），表示 $A$ 是 $n$ 元函数。随后有 $2^n$ 行，每行为一个长度为 $n+1$ 的字符串。字符串仅包含字符 `T` 和 `F` 。前 $n$ 个依次表示第 $n$ 个命题的值，最后一个表示当 $n$ 个命题按此取值时 $A$ 的值。

outputFormat: 输出文件包含一行，为你给出的范式。命题依次用小写字母 $a, b, c, d, \ldots $表示。

samples:
3
TTTT
TTFT
TFTT
TFFF
FTTT
FTFF
FFTF
FFFF

hint:
**评分标准**：

- 如果你给定的范式错误或者在规定时间内没有出解，该测试点得 $0$ 分。
- 如果你给定的范式长度小于等于标准答案的长度，该测试点得满分。
- 如果你给定的范式长度大于等于标准答案长度的两倍，该测试点得 $0$ 分。
- 如果你给定的范式长度大于标准答案的长度，小于标准答案长度的两倍，该测试点得分计算公式为：

$$
Score=FullScore \times \frac{2L_{std}-L}{L_{std}}
$$

其中 $FullScore$ 为该测试点满分， $L_{std}$ 为标准答案长度， $L$ 为你的答案长度。

**感谢 [tiger2005](https://www.luogu.com.cn/user/60864) 提供 SPJ ！**


title: [NOIP2004 提高组] 合并果子 加强版

background: 本题除【数据范围与约定】外与 [P1090](https://www.luogu.com.cn/problem/P1090) **完  全  一  致**。

description:
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $(n - 1)$ 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 $3$ 堆果子，数目依次为 $1,~2,~9$。可以先将 $1$、$2$ 堆合并，新堆数目为 $3$，耗费体力为 $3$。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$，耗费体力为 $12$。所以多多总共耗费体力为 $3+12=15$。可以证明 $15$ 为最小的体力耗费值。

inputFormat:
输入的第一行是一个整数 $n$，代表果子的堆数。\
输入的第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 堆果子的个数 $a_i$。

outputFormat: 输出一行一个整数，表示最小耗费的体力值。

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

**本题采用多测试点捆绑测试，共有四个子任务**。

- Subtask 1（10 points）：$1 \leq n \leq 8$。
- Subtask 2（20 points）：$1 \leq n \leq 10^3$。
- Subtask 3（30 points）：$1 \leq n \leq 10^5$。
- Subtask 4（40 points）：$1 \leq n \leq 10^7$。

对于全部的测试点，保证 $1 \leq a_i \leq 10^5$。

**【提示】**

- 请注意常数因子对程序效率造成的影响。
- 请使用类型合适的变量来存储本题的结果。
- 本题输入规模较大，请注意数据读入对程序效率造成的影响。


title: 『MdOI R1』Decrease

description:
给定一个 $n \times n$ 的矩阵，你可以进行若干次操作。

每次操作，你可以将一个 $k \times k$ 的 **连续** 子矩阵里的所有数全都加上 $1$ 或者全都减去 $1$。

初始时，矩阵中有 $m$ 个位置上的数不为 $0$，其它位置上的数均为 $0$。

请你求出至少需要多少次操作，可以将矩形中所有数都变为 $0$。

inputFormat:
第一行三个整数 $n,m,k$，分别表示矩阵大小，非 $0$ 格数和每次修改的连续子矩阵大小。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示初始时矩阵的第 $x$ 行第 $y$ 列上的数为 $z$。

outputFormat:
一行一个整数，表示最少操作次数。

特别地，如果无法使矩阵中所有数都变为 $0$，输出 `-1`。


title: [RC-02] GCD

background:
小 A：数论题真是无聊呢，一天到晚枚举二元组、三元组，太无聊了。

小 B：对呀对呀，都是套路。

小 A：要不我们试试枚举四元组？

小 B：......

于是就有了这道题。

description:
给出 $N$，求：

$$
\sum_{i=1}^N\sum_{j=1}^N\sum_{p=1}^{\lfloor\frac{N}{j}\rfloor}\sum_{q=1}^{\lfloor\frac{N}{j}\rfloor}[\gcd(i,j)=1][\gcd(p,q)=1]
$$

答案模 $998244353$。

$[]$ 是条件表达式。当括号里面的式子成立时值为 $1$，否则为 $0$。

inputFormat: 仅一行一个整数，为 $N$。

outputFormat: 输出一个整数，为所求答案模上 $998244353$ 的值。

hint:
对于所有数据，保证 $1\le N\le 2\times10^9$，所有测试点的时限均为 $1\text{s}$，空间限制均为 $500\text{MB}$。

| 测试点编号 | $N$               |
| ---------- | ----------------- |
| $1$          | $\le 100$         |
| $2$          | $\le 400$         |
| $3,4,5,6$ | $\le10^6$ |
| $7,8$       | $\le 2\times10^7$ |
| $9$          | $\le 2\times10^8$ |
| $10$         | $\le 2\times10^9$ |

这题其实可以搞一个测试点多组数据，但良心的出题人为了多给你们一点部分分，就决定只来一组数据。

idea 源自 @Fee_cle6418，题目的题面，标算，数据源自 @FangZeLi。


title: [CEOI2004] Sweets

description: John 得到了 $n$ 罐糖果。不同的糖果罐，糖果的种类不同（即同一个糖果罐里的糖果种类是相同的，不同的糖果罐里的糖果的种类是不同的）。第 $i$ 个糖果罐里有 $m_{i}$ 个糖果。John 决定吃掉一些糖果，他想吃掉至少 $a$ 个糖果，但不超过 $b$ 个。问题是 John 无法确定吃多少个糖果和每种糖果各吃几个。有多少种方法可以做这件事呢？

inputFormat:
输入共 $n+1$ 行：

第一行读入 $n$，$a$，$b$。

接下来 $n$ 行，一行一个数，代表 $m_{i}$。

outputFormat: 仅一行，表示 John 能够选择的满足以上条件的吃掉糖果的方法数，答案对 $2004$ 取模。

hint:
#### 数据范围及限制
对于 $100\%$ 的数据，保证 $1\leq n \leq 10$，$0\leq a \leq b \leq 10^7$，$0 \leq m_{i} \leq 10^6$。

#### 说明
本题译自 [Central European Olympiad
in Informatics 2004](https://www.oi.edu.pl/old/php/ceoi2004.php?module=show&file=news) [Day 1](https://www.oi.edu.pl/old/php/ceoi2004.php?module=show&file=tasks) [T2 Sweets](https://www.oi.edu.pl/old/ceoi2004/problems/swe.pdf)。


title: [PA2013] Konduktorzy

description:
一辆无限长的列车，有 $k$ 个检票员。每个检票员一次检验 $a_i$ 个车厢，初始时所有检票员在 $0$ 号车厢。

列车长每次命令最靠左的编号最小的检票员向右走 $a_i$ 步，一共发出 $n$ 个命令，输出每个售票员走的最后一步是列车长的第几次命令。

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

第二行 $k$ 个数，表示每个检票员一次检验的长度 $a_i$。

outputFormat: 一行 $k$ 个整数，每个整数表示这个售票员走到最后一步是列车长的第几次命令。


title: [PA2013] Karty

description: 给定 $n\times m$ 的矩形，每个点仅可能为 `_` 或 `X`， 选出一个最大的 $r\times c$ 的矩形，使得多个 $r\times c$ 的矩形能够(可以重叠的)覆盖全部 `X` 部分，不覆盖 `_` 部分。

inputFormat:
第一行 $n,m$ 如题意所述。

接下来 $n$ 行，每行一个长为 $m$ 的字符串描述这个矩阵。

outputFormat:
输出一行，两个数 $r,c$，用空格隔开。

同时有多个面积最大的要输出 $r$ 最小的那个。


title: [PA2013] Euler

description: 给定 $n$ 求所有满足 $\varphi(x)=n$ 的 $x$。

inputFormat:
第一行一个数 $T$。

接下来 $T$ 行，每行一个数 $n$。

outputFormat:
输出共 $2\times T$ 行。

每组一个数 $m$ 表示满足的个数。

接下来一行升序输出 $m$ 个数 $x_i$，若 $m$ 为 $0$ 则输出一个空行。


title: [PA2014] Bohater

description:
在一款电脑游戏中，你需要打败 $n$ 只怪物（从 $1$ 到 $n$ 编号）。

为了打败第 $i$ 只怪物，你需要消耗 $d_i$ 点生命值，但怪物死后会掉落血药，使你恢复 $a_i$ 点生命值。

任何时候你的生命值都不能降到 $0$（或 $0$ 以下）。

请问是否存在一种打怪顺序，使得你可以打完这 $n$ 只怪物而不死掉。

inputFormat:
第一行两个整数 $n,z$，分别表示怪物的数量和你的初始生命值。

接下来 $n$ 行，每行两个整数 $d_i,a_i$。

outputFormat:
第一行为 `TAK`（是）或 `NIE`（否），表示是否存在这样的顺序。

如果第一行为 `TAK`，则第二行为空格隔开的 $1\sim n$ 的排列，表示合法的顺序。

如果答案有很多，你可以输出其中任意一个。（**本题使用 SPJ**）


title: [P5087] 数学 加强版

background: [原题链接](https://www.luogu.com.cn/problem/P5087)

description:
小奔热衷于乘法，他最喜欢做的事情是：从一个有 $n$ 个元素的可重集中选出 $k$ 个数，并把这 $k$ 个数的乘积作为这个组合的分数。

小奔想试遍所有的这些组合，然后算出所有这些组合的分数之和。但是他还要出模拟赛虐爆我们这些蒟蒻，所以他只好把这个任务交给了你。

作为不良心的出题人，这题你还要将答案对 $10^9 + 7$ 取模。

inputFormat:
第一行两个正整数 $n,k$。
第二行 $n$ 个正整数 $a_i$，表示可重集中的元素。

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

hint:
【样例二解释】
有四种选择方案，一种是 $\{1,1,1\}$ 和三种都是 $\{1,1,2\}$，分数之和为 $7$。

【数据范围】
对于 $100\%$ 的数据，$1\le k \le n \le 1.2\times 10^5$，$1\le a_i \le 10^8$。


title: [PA2014] Fiolki

description:
化学家吉丽想要配置一种神奇的药水来拯救世界。

吉丽有 $n$ 种不同的液体物质，和 $n$ 个药瓶（均从 $1$ 到 $n$ 编号）。初始时，第 $i$ 个瓶内装着 $g_i$ 克的第 $i$ 种物质。

吉丽需要执行一定的步骤来配置药水，第 $i$ 个步骤是将第 $a_i$ 个瓶子内的所有液体倒入第 $b_i$ 个瓶子，此后第 $a_i$ 个瓶子不会再被用到。瓶子的容量可以视作是无限的。

吉丽知道某几对液体物质在一起时会发生反应产生沉淀，具体反应是 $1$ 克 $c_i$ 物质和 $1$ 克 $d_i$ 物质生成 $2$ 克沉淀，一直进行直到某一反应物耗尽。生成的沉淀不会和任何物质反应。

当有多于一对可以发生反应的物质在一起时，吉丽知道它们的反应顺序。每次倾倒完后，吉丽会等到反应结束后再执行下一步骤。

吉丽想知道配置过程中总共产生多少沉淀。

inputFormat:
第一行三个整数 $n,m,k$，分别表示药瓶的个数（即物质的种数），操作步数，可以发生的反应数量。

第二行有 $n$ 个整数 $g_1,g_2,…,g_n$，表示初始时每个瓶内物质的质量。

接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示第 $i$ 个步骤。保证 $a_i$ 在以后的步骤中不再出现。

接下来 $k$ 行，每行是一对可以发生反应的物质 $c_i,d_i$，按照反应的优先顺序给出。同一个反应不会重复出现。

outputFormat: 输出总共产生的沉淀质量。

hint: 对于 $100\%$ 的数据，$0\le m<n\le 2\times 10^5$，$0\le k\le 5\times 10^5$，$1\le g_i\le 10^9$，$1\le a_i,b_i,c_i,d_i\le n$，$a_i\ne b_i$，$c_i\ne d_i$。


title: [Ynoi2009] rprmq1

background:
我谔谔

本题读入量约 13 MB，输出量约 7 MB，请选择合适的输入输出方法

description:
有一个 $n \times n$ 的矩阵 $a$，初始全是 $0$，有 $m$ 次修改操作和 $q$ 次查询操作，先进行所有修改操作，然后进行所有查询操作。

一次修改操作会给出 $l_1,l_2,r_1,r_2,x$，代表把所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $a_{i,j}$ 元素加上一个值 $x$。

一次查询操作会给出 $l_1,l_2,r_1,r_2$，代表查询所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $a_{i,j}$ 元素的最大值。

inputFormat:
第一行三个由空格分隔的整数 $n,m,q$。

之后 $m$ 行，每行给出五个整数 $l_1,l_2,r_1,r_2,x$，表示一次修改操作。

之后 $q$ 行，每行给出四个整数 $l_1,l_2,r_1,r_2$，表示一次查询操作。

outputFormat: 输出 $q$ 行，对每次查询操作输出一行一个数表示答案。

hint:
Idea：apiadu，Solution：ccz181078，Code：apiadu，Data：apiadu&nzhtl1477

注意：本题采用**捆绑测试**，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

对于其中 $1\%$ 的数据，为样例 1。

对于另外 $9\%$ 的数据，$n=1$。

对于另外 $19\%$ 的数据，$n,m\leq 500$。

对于另外 $19\%$ 的数据，$n\leq 2000$，$q\leq 2\times 10^5$。

对于另外 $19\%$ 的数据，$m,q\leq 2000$。

对于 $100\%$ 的数据，$1\leq n,m\leq 5\times 10^4$，$1\leq q \leq 5\times 10^5$，$1\leq x\leq 2147483647$，$1\leq l_1\leq r_1\leq n$，$1\leq l_2\leq r_2\leq n$。


title: [PA2014] Parking

description:
你的老板命令你将停车场里的车移动成他想要的样子。

停车场是一个长条矩形，宽度为 $w$。我们以其左下角顶点为原点，坐标轴平行于矩形的边，建立直角坐标系。停车场很长，我们可以认为它一直向右边伸展到无穷远处。

车都是边平行于坐标轴的矩形，大小可能不同。你可以将车任意地平移（但不能旋转），只要他们不超出停车场的边界，且不能互相碰撞，但紧挨着是允许的（即任意时刻任两辆车的重叠面积为 $0$）。

你知道目前各辆车的摆放位置，以及老板心中所想的位置。你需要判断是否可以办到老板的任务。

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

inputFormat:
第一行为一个整数 $t$，表示测试数据数量。

对于每组测试数据，第一行两个整数 $n,w$，分别表示车的数量和停车场的宽度。

接下来 $n$ 行，第 $i$ 行有四个整数 $x_1,y_1,x_2,y_2$，表示编号为 $i$ 的车的当前位置是由 $x_1,y_1,x_2,y_2$ 确定的矩形。

（注意：数据有可能出现 $x_1>x_2$ 或 $y_1>y_2$）

再接下来 $n$ 行，格式和意义同上，表示车的目标位置。

outputFormat: 输出 $t$ 行，第 $i$ 行为 `TAK`（是）或 `NIE`（否），表示第 $i$ 组测试数据中能否按照要求进行移动。


title: [PA2015] Siano

description:
农夫 Byteasar 买了一片 $n$ 亩的土地，他要在这上面种草。

他在每一亩土地上都种植了一种独一无二的草，其中，第 $i$ 亩土地的草每天会长高 $a_i$ 厘米。

Byteasar 一共会进行 $m$ 次收割，其中第 $i$ 次收割在第 $d_i$ 天，并把所有高度大于等于 $b_i$ 的部分全部割去。

Byteasar 想知道，每次收割得到的草的高度总和是多少，你能帮帮他吗？

inputFormat:
第一行包含两个正整数 $n,m$，分别表示亩数和收割次数。

第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $a_i$，依次表示每亩种植的草的生长能力。

接下来 $m$ 行，每行包含两个整数 $d_i,b_i$，依次描述每次收割。

outputFormat: 输出 $m$ 行，每行一个整数，依次回答每次收割能得到的草的高度总和。


title: [PA2015] Fibonacci

background: 更新：输出任意满足条件的 $k$ 即可，感谢 @[Karry5307](https://www.luogu.com.cn/user/60990) 的修正和 spj。

description:
众所周知，斐波那契数列 $F$ 满足：
$$F_0=0,F_1=1,F_m=F_{m-1}+F_{m-2}(2\le m)$$
现在给出一个数字串 $S$，请找到一个**最小**的 $k$ 使得 $F_k$ 以 $S$ 为结尾。

inputFormat: 包含一行一个数字串 $S$。

outputFormat:
输出满足条件的最小数字 $k$。

若无解，输出 `NIE`。


title: [PA2015] Hazard

background: ~~赌博有害健康请不要模仿。~~

description:
有 $n$ 个人在轮流玩赌博机，一开始编号为 $i$ 的人有 $a_i$ 元钱。赌博机可以抽象为一个长度为 $m$ 的仅包含 $1$ 和 $-1$ 的序列，若抽到 $1$，那么你将得到 $1$ 块钱；若抽到 $-1$，你将输掉 $1$ 块钱。

第 $1$ 局，第 $1$ 个人会抽到序列中的第 $1$ 项；第 $2$ 局，第 $2$ 个人会抽到序列中的第 $2$ 项；第 $3$ 局，第 $3$ 个人会抽到序列中的第 $3$ 项......即：第 $i$ 个人抽完后轮到第 $i+1$ 个人去抽，特别地，第 $n$ 个人抽完后轮到第 $1$ 个人去抽。序列第 $i$ 项被抽到之后，下一个被抽到的将会是第 $i+1$ 项，特别地，序列第 $m$ 项被抽到之后，下一个被抽到的将会是第 $1$ 项。

如果在某一轮，有个人输光了所有的钱，那么这场赌博游戏就会结束，请求出游戏在哪一轮结束，或者判断这个游戏会永远进行下去。

inputFormat:
第一行包含一个正整数 $n$，表示玩家的个数。

第二行包含 $n$ 个正整数 $a_1,a_2,...,a_n$，依次表示每个玩家一开始持有的钱数。

第一行包含一个正整数 $m$，表示序列的长度。

第四行包含一个长度为 $m$ 的仅包含 `W` 和 `P` 的字符串，表示这个序列，其中 `W` 表示 $1$，`P` 表示 $-1$。

outputFormat: 若游戏会永远进行下去，输出 `-1`。否则输出游戏在哪一轮结束。


title: [PA2011] Prime prime power 质数的质数次方

description: 对于给定的数 $n$，求第 $k$ 小的 $a^b$（$a,b$ 都为质数），使得它的值大于 $n$。

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

outputFormat: 一行一个整数为答案。


title: [加油武汉] 疫情调查

description:
W 市爆发了严重的肺炎疫情。为了应对疫情，W 市需要对下属每一个社区进行巡回调查。

W市共有 $n$ 个街区，街区之间由 $m$ 条不相同的有向道路相连，没有任何一条道路是自己通向自己的，并且是保证弱联通的。通过每条道路需要消耗一定的燃油费用。

现在你需要派出一些工作人员来寻访每个街区。对于每个工作人员，你需要给他分派一些街区，之后工作人员会按照给定的顺序在这些街区反复循环，每周循环一次。请注意，工作人员只会检查你给他分配的街区，在分配的街区之间经过的街区，工作人员并不会下车。同时为了防止人员浪费，任何一个街区只能接受一位工作人员的检查。当然，如果必要，他也会经过重复的街区。

工作人员的花费是这样的：若是某个工作人员只分配到了一个街区 $u$，那么他需要每周消耗 $a_u$ 的停留费用。若是被分配到了多于一个的街区，那么他的花费就是环绕这些点一圈最后回到起点的道路燃油费用之和。

现在你需要知道，在工作人员数量无限的情况下，每周最少需要多少费用可以将整个 W 市完全巡查。

inputFormat:
第一行两个整数 $n,m$，意义如题。

第二行 $n$ 个整数，为数组 $a$。

接下来 $m$ 行，每行三个整数 $u_i,v_i,w_i$ 表示存在一条连接 $u_i,v_i$ 的**有向边**，通行时付出的代价为 $w_i$。

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


title: [CEOI2018] toy

description:
Johnny 喜欢收藏玩具。他收藏的玩具有很多不同的种类，每种玩具有很多个，而种类相同的两个玩具是无法区分的。

Emma 问 Johnny 他有几个玩具。然而 Johnny 并不愿意回答这个问题。

他告诉 Emma，如果他从所有玩具中选择一些不同的玩具，他可以玩 $n$ 天。换言之，这 $n$ 天中任意两天选择的玩具，存在一种玩具选择的数量不同。同时，选择的玩具集合是空集也是允许的。

Emma 并不想亲自计算这个答案，因此她把这个问题交给了你。你需要告诉她 Johnny 拥有的玩具的所有可能数量。

inputFormat: 输入仅包含一个整数 $n$。

outputFormat:
第一行输出一个整数 $r$，表示共有 $r$ 种 Johnny 拥有的玩具数量。

接下来一行，输出 $r$ 个递增的整数，代表 Johnny 一种可能拥有的玩具的数量。

hint:
对于 $100\%$ 的数据， $1\le n\le 10^9$。

-----

**题目翻译By @StudyFather。**


title: [EER2] 谔运算

background: 在某个谔谔的一天中，CYJian 做到一道谔运算的谔谔题，CYJian 发现他不会做，于是决心从头开始研究令人谔谔的谔运算。

description:
首先，CYJian 写出了一个长度为 $n$ 的数列 $a$。

然后他灵光一动，写出了下面这个谔谔的式子：

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n} (a_i\ {\rm or}\ a_j)\ {\rm xor}\ (a_k\ {\rm and}\ a_l)$$

CYJian 觉得这个是一个谔运算的简单式子，摁计算器花了 $114514{\rm s}$ 就算出来了答案。

为了证明你吊打 $114514$ 个 CYJian，请你在 $1{\rm s}$ 内算出来这个式子的值吧。你只需要给出答案对 $2^{32}$ 取模的值即可。

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

第二行 $n$ 个非负整数，第 $i$ 个数表示 $a_i$。

outputFormat: 一行一个非负整数，表示题目描述中给出式子的值。


title: [EER2] 出言不逊

background: 你出言不逊是！！

description:
珂愛想出公开赛，但每次都被拒绝。

珂愛很生气，于是学会了出言不逊。

珂愛用一个字符串 $S$ 存储了她想说的话，但这句话太逊了。为了出言不逊，珂愛要对字符串进行操作。每次操作，珂愛可以选择一个字符 $c$，若 $c$ 在字符串 $S$ 中出现了 $x$ 次，则珂愛会将 $x$ 个字符 $c$ 补到 $S$ 的尾部。

珂愛认为，这个字符串长度至少为 $L$ 时，她才能出言不逊。珂愛想要知道，她至少需要操作多少次，才能让这个字符串的长度**大于等于** $L$。

如果你不告诉珂愛，珂愛会对你出言不逊。

inputFormat:
第一行一个字符串 $S$。

第二行一个正整数 $L$。

意义见题目描述。

outputFormat: 一行一个整数，表示最小操作次数。

hint:
### 样例解释

第一次操作，选择字符 `7`，字符串变为 `nzhtl147777`，长度为 $11$。

第二次操作，选择字符 `7`，字符串变为 `nzhtl1477777777`，长度为 $15$。

### 限制与约定

对于 $100\%$ 的数据，$1\leq |S|\leq 10^6$，$1\leq L\lt 2^{64}$，$S$ 中只可能出现大、小写英文字母和数字，共 $62$ 种不同字符。

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

本题共有 $4$ 个子任务，每个子任务的限制如下：

子任务 1（$15$ 分）：保证 $|S|=L-1$。

子任务 2（$20$ 分）：保证 $S$ 中只出现字符 `d`。

子任务 3（$30$ 分）：$L\leq 10^6$。

子任务 4（$35$ 分）：没有特殊限制。

### 提示

**请注意 $L$ 的上限**。

**数据在 Windows 下生成，请注意每行的行末是 `\r\n` 而非 `\n`。**


title: 论如何玩转 Excel 表格

description:
有一个 $2 \times n$ 的表格，表格内不重不漏地填有 $1 \sim 2 \times n$ 这些数字。你可以进行若干次操作，每次操作可以选择一个 $2 \times 2$ 的正方形区域，然后旋转 $180\degree$。

给出现在的状态以及目标状态。问是否可以达到目标状态。如果能，最少操作次数是多少。

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

接下来两行，每行 $n$ 个正整数表示表格现在的状态。

接下来两行，每行 $n$ 个正整数表示目标状态。

outputFormat:
若无解，输出一行 `dldsgay!!1`。

否则，输出一个整数，表示最少的操作次数。

hint:
#### 子任务

本题采用捆绑测试。

对于 $100\%$ 的数据：$1 \leq n \leq 10^6$。

本题共 $10$ 个子任务，各子任务的分值和限制如下：

子任务 $1$（$1$ 分）：保证输出一定为 `dldsgay!!1`。
子任务 $2$（$1$ 分）：保证目标状态与现在状态一致。
子任务 $3$（$4$ 分）：$n=1$。
子任务 $4$（$5$ 分）：$n=2$。
子任务 $5$（$14$ 分）：$1 \leq n \leq 20$。
子任务 $6$（$19$ 分）：$1 \leq n \leq 100$。
子任务 $7$（$19$ 分）：$1 \leq n \leq 1000$。
子任务 $8$（$8$ 分）：保证目标状态第一行依次为 $1 \sim n$，第二行依次为  $n + 1 \sim 2n$。
子任务 $9$（$10$ 分）：保证不存在无解情况。
子任务 $10$（$19$ 分）：无特殊限制。


title: [加油武汉] 传染病研究

description:
在得知 W 市爆发的肺炎之后，科学家们立刻投入了紧锣密鼓的研究之中。

（下面的部分非严谨科学，大家做题以外切勿当真）

假设某种病毒在第 $x$ 天的传播能力为 $D(x)$，该函数的含义为 $x$ 的约数个数。例如 $D(6)=4, D(7)=2$。

现在给定你总的传播天数 $n$ 和一个影响常数 $k$，你需要计算 $\sum_{i=1}^n D(i^k)$ 也就是 $D(1^k)+D(2^k)+D(3^k)+ \cdots +D(n^k)
$。

由于答案可能很大，请对 $998244353$ 取模。

inputFormat:
本题有多组数据。

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

接下来每行两个整数 $n,k$，意义如题所示。

outputFormat: 共 $T$ 行，表示每组数据的答案。


title: [JSOI2015] 子集选取

description:
给定 $n$ 个元素的集合 $S= \left\{1,2,\cdots,n \right\}$ 和整数 $ k$，现在要从 $S$ 中选出若干子集 $A_{i,j}\ (A \subseteq S$，$1 \le j \le i \le k)$ 排成下面所示边长为 $k$ 的三角形（因此总共选出了 $\frac{1}{2} k(k+1)$ 个子集）。
$$\begin{matrix}
A_{1,1}\\
A_{2,1}&A_{2,2}\\
A_{3,1}&A_{3,2}&A_{3,3}\\
\vdots&\vdots&\vdots&\ddots\\
A_{k,1}&A_{k,2}&A_{k,3}&\cdots&A_{k,k}
\end{matrix}   $$

此外，JYY 对选出的子集之间还有额外的要求：选出的这些子集必须满足
$A_{i,j} \subseteq A_{i,j-1}$ 且 $A_{i,j} \subseteq A_{i-1,j}$。
JYY 想知道，求有多少种不同的选取这些子集的方法。因为答案很大，JYY 只关心输出答案模 $1{,}000{,}000{,}007$ 的值。

对于两种选取方案 $A = \left\{ A_{1,1} , A_{2,1} ,\cdots, A_{k,k} \right\}$ 和 $B = \left\{ B_{1,1} , B_{2,1} ,\cdots, B_{k,k} \right\}$ 只要存在 $i,j$ 满足 $A_{i,j} \neq B_{i,j}$，我们就认为 $A$ 和 $B$ 是不同的方案。

inputFormat: 输入包含一行两个整数 $n$ 和 $k$。

outputFormat: 一行一个整数，表示不同方案数目模 $1,000,000,007$ 的值。


title: [JSOI2015] 染色问题

description:
萌萌家有一个棋盘，这个棋盘是一个 $n \times m$ 的矩形，分成 $n$ 行 $m$ 列共 $n \times m$ 个小方格。
现在萌萌和南南有 $C$ 种不同颜色的颜料，他们希望把棋盘用这些颜料染色，并满足以下规定：

1. 棋盘的每一个小方格既可以染色（染成 $C$ 种颜色中的一种），也可以不染色。
2. 棋盘的每一行至少有一个小方格被染色。
3. 棋盘的每一列至少有一个小方格被染色。
4. 每种颜色都在棋盘上出现至少一次。

以下是一些将 $3  \times 3$ 棋盘染成 $C=3$ 种颜色（红、黄、蓝）的例子（下图已更新）：

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

请你求出满足要求的不同的染色方案总数。只要存在一个位置的颜色不同，即认为两个染色方案是不同的。

inputFormat: 输入只有一行，为 $3$ 个整数 $n,m,c$。

outputFormat:
输出一个整数，为不同染色方案总数。
因为总数可能很大，只需输出总数对 $1,000,000,007$ 取模的值。


title: [JSOI2015] salesman

description:
某售货员小 T 要到若干城镇去推销商品,由于该地区是交通不便的山区，任意两个城镇之间都只有唯一的可能经过其它城镇的路线。 小 T 可以准确地估计出在每个城镇停留的净收益。这些净收益可能是负数，即推销商品的利润抵不上花费。由于交通不便，小 T 经过每个城镇都需要停留，在每个城镇的停留次数与在该地的净收益无关，因为很多费用不是计次收取的，而每个城镇对小 T 的商品需求也是相对固定的，停留一次后就饱和了。每个城镇为了强化治安，对外地人的最多停留次数有严格的规定。

请你帮小 T 设计一个收益最大的巡回方案,即从家乡出发，在经过的每个城镇停留，最后回到家乡的旅行方案。你的程序只需输出最大收益，以及最优方案是否唯一。方案并不包括路线的细节，方案相同的标准是选择经过并停留的城镇是否相同。因为取消巡回也是一种方案，因此最大收益不会是负数。小 T 在家乡净收益是零，因为在家乡是本地人，家乡对小 T 当然没有停留次数的限制。

inputFormat:
输入的第一行是一个正整数 $n$，表示城镇数目。城镇以 $1$ 到 $n$ 的数命名。小 T 的家乡命名为 $1$。

第二行和第三行都包含以空格隔开的 $n-1$ 个整数。第二行的第 $i$ 个数表示在城镇 $i+1$ 停留的净收益。第三行的第 $i$ 个数表示城镇 $i+1$ 规定的最大停留次数。所有的最大停留次数都不小于 $2$。

接下来的 $n-1$ 行，每行两个 $1$ 到 $n$ 的正整数 $x,y$，之间以一个空格
隔开，表示 $x,y$ 之间有一条不经过其它城镇的双向道路。输入数据保证所有城镇是连通的。

outputFormat: 输出有两行。第一行包含一个自然数，表示巡回旅行的最大收益。如果该方案唯一，在第二行输出 `solution is unique`，否则在第二行输出 `solution is not unique`。


title: 随机红包

background: 出题人准备发一个微信红包给一些人，他很好奇如何随机分配里面的钱。

description:
出题人蒟蒻的红包里有着 $1$ 块钱，他要把这块钱随机分给 $n$ 个人。

为了随机，他设计了以下算法进行分配：（用伪代码表示）
```
a[0]=0,a[n]=1
for i=1 to n-1 do{
    a[i]=rand()
}
sort(a)
for i=1 to n do{
    money[i]=a[i]-a[i-1]
}
```
这里的 `rand()` 函数会等概率随机返回一个 $[0,1]$ 之间的实数值，`sort()` 函数会将一个数组从小到大排序。

现在，出题人蒟蒻很好奇得到钱数第 $k$ 少的人得到的钱的期望。

由于他要根据这个值去推算他要发多少个红包，所以他要问你 $T$ 次。

为了避免精度丢失，答案对 $998244353$ 取模。

为了避免输出量过大，输出所有答案的异或和。

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

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

对于每组数据，一行两个整数 $n,k$。

outputFormat: 共一行一个整数，表示所有询问的答案的异或和。

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

第一个问题，$n=k=1$，答案是 $1$。

第二个问题，较大的数在 $[\dfrac{1}{2},1]$ 上均匀分布，期望为 $\dfrac{3}{4}$，取模后为 $249561089$。

第三个问题，较小的数在 $[0,\dfrac{1}{2}]$ 上均匀分布，期望为 $\dfrac{1}{4}$，取模后为 $748683265$。

异或和为 $574619649$。

------

**【数据范围】**

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

$\text{Subtask 1 (4 pts)}$：$n \le 10$，$k=1$。

$\text{Subtask 2 (16 pts)}$：$n \le 5 \times 10^3$。

$\text{Subtask 3 (20 pts)}$：$k=1$。

$\text{Subtask 4 (28 pts)}$：$n \le 10^5$。

$\text{Subtask 5 (32 pts)}$：没有任何额外限制。

对于 $100\%$ 的数据，$1 \le k \le n \le 10^7$，$1 \le T \le 2 \times 10^5$。


title: 封锁

background:
震惊！zbw 竟从 B 城监狱逃出！

作为 B 城的警察局长，你必须在 zbw 逃出你的管辖范围之前抓住他。

description:
B 城可视为一个 $n \times n$ 的方阵，其中监狱在 $(1,1)$，B 城唯一出城的出口在 $(n,n)$。每两个相邻的点（横坐标之差的绝对值 $+$ 纵坐标之间的绝对值 $=1$）之间都有一条**无向的**道路（没有斜着的道路）。你需要在一些道路上部下防守，使得无论 zbw 怎么走，都至少会经过其中的一条道路。

在一条 $(i,j)$ 到 $(i,j+1)$ 的道路上部下防守的花费是 $r_{i,j}$，在一条 $(i,j)$ 到 $(i+1,j)$ 的道路上部下防守的花费是 $d_{i,j}$，同时，在道路上部下防守会对人民的生活造成影响，在一条 $(i,j)$ 到 $(i,j+1)$ 的道路上部下防守对人民的生活造成的影响是 $x_{i,j}$，在一条 $(i,j)$ 到 $(i+1,j)$ 的道路上部下防守对人民的生活造成的影响是 $y_{i,j}$。

定义总花费为 $w$ ，总影响为 $e$ ，作为一名优秀的警察局长，你需要最小化 $w \times e$。

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

之后的 $n \times (n-1)$ 行，第 $i$ 行两个整数 $r_{i/n+1,(i-1)\bmod n+1}$， $x_{i/n+1,(i-1)\bmod n+1}$。

之后的 $n \times (n-1)$ 行，第 $i$ 行两个整数 $d_{i/n+1,(i-1)\bmod n+1}$ ，$y_{i/n+1,(i-1)\bmod n+1}$。

也就是说，先从上往下给从左往右给出竖边的信息，再从上往下给从左往右给出横边的信息。

如果不理解请见样例解释。

outputFormat: 一行一个整数，表示 $w \times e$ 的最小值。


title: 调和级数求和

description:
给定 $n,p$，求：

$$\sum_{i=1}^n \frac 1i $$

对 $p$ 取模的值。

如果你不知道怎么对分数取模，可以看[这题](https://www.luogu.com.cn/problem/P2613)。
保证答案在模 $p$ 意义下存在。

为了方便你的计算，这里将给出 $p$ 的最小原根 $g$。

inputFormat:
输入第一行一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行三个正整数 $n,p,g$。

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

hint:
【数据范围】
对于 $30\%$ 的数据，$1\le n \le 10^6$；
对于 $100\%$ 的数据，$1 \le n < p < 2^{30}$，$1\le T \le 20$。
保证 $p$ 为质数，且 $p-1$ 可以被 $2^{19}$ 整除。

注：时限为 std 的三倍，如果过不去请确认时间复杂度正确，并优化常数。


title: [JSOI2010] 排名

background:
在植树节那天，小 L，小 H，小 X 却要面对繁忙的考试。

考完后，按照惯例，他们讨论起了成绩。小 L 非常八卦，他向全班 $N$ 个同学问了他们的成绩情况。当然，就如你想象的那样，每个人也不愿意透露太多信息，每个人值说了他的分数比哪一个同学低，也有些人没说任何信息。

勤奋的小 H 和爱偷懒的小 X 对于班上所有同学的成绩排名都有一个“心理期望”，也就是说，小 H 可能认为 XX 会排第 $1$，YY 会排第 $2$……但小 X 却会认为 XX 应该排最后 $1$ 名，YY 会排倒数第 $2$ 名。

不过理想和现实总是有差距的，通过小 L 打探到的情报， XX 不能排在第 $1$ 了，但是，小 H 仍然觉得 XX 应该排在尽可能前。

小 L 由此想到了一个问题，他想知道小 H 和小 X 知道他打探到的情报之后，对班上同学的心里排名是什么样的。

每个同学的编号即为小 H 的心理排名，也就是说，小 H 希望编号越靠前的同学排名也尽量靠前，而小 X 希望希望编号越靠前的同学排名尽量靠后。（注意不是越后面的同学排名越靠前）

description:
给定一个长度为 $N$ 的数列 $A$，其中 $A_i$ 表示第 $i$ 个同学的分数比第 $A_i$ 个同学的分数低（或者说，第 $i$ 个同学的排名在第 $A_i$ 个同学之后）。当然，$A_i$ 有可能等于 $0$，则表明没有关于第 $i$ 个同学的信息。

你需要得到一个长度为 $N$ 的数列 $H$，表示班上同学的排名。这个排名要求是满足所有 $A_i$ 构成的约束的排名中字典序最小的哪一个。

同时，你还需要得到一个数列 $X$，表示班上同学的排名。这个排名要求是满足所有 $A_i$ 构成的约束的排名中字典序最大的哪一个。

inputFormat:
第 $1$ 行一个正整数 $N$，表示班上同学的个数。

第 $2$ 行包含 $N$ 个用空格隔开的非负整数，第 $i$ 个数表示 $A_i$。

outputFormat: 两行，每行 $N$ 个正整数，用空格隔开。其中，第 $1$ 行为小 L 的心理排名，第 $2$ 行为小 X 的心理排名。

hint:
### 样例解释

共有 $3$ 种排名满足大小关系：

```plain
4 1 3 2
4 1 2 3
3 1 2 4
```

其中，`3 1 2 4` 字典序最小，`4 1 3 2` 字典序最大。

### 数据范围

对于 $10\%$ 的数据，$N\leq 10$。

对于 $20\%$ 的数据，$N\leq 20$。

对于 $40\%$ 的数据，$N\leq 2\times 10^3$。

对于 $100\%$ 的数据，$1 \leq N\leq 2\times 10^5,A_i\leq N$。其中，第 $5$ 组数据保证 $N=1.2\times 10^4$。


title: 岛屿 Island

background:
> 从前有些岛，岛旁有些桥；桥连着岛，岛连着桥。
>
> 有一天，桥倒了，岛翘了；从此桥没了岛，岛也没了桥。

description:
茫茫大海中央，有一个庞大的群岛体系，坐落着 $n$ 座岛屿。为了方便记录，我们把它们编号为岛屿 $1$ 到 $n$，其中，岛屿 $1$ 是唯一一个有人居住的岛。

这些群岛间，有 $m$ 架摇摇欲坠的小桥。第 $i$ 架桥连接着 $u_i, v_i$ 两座 **不同** 的岛，**没有两座岛之间架有两架桥**。

脆弱的小桥已经荒废了，每架桥都只能容一个人走一遍就会倒塌。

一天，你心血来潮，前来这个庞大的群岛探险。作为探险家的你，知道一条安全的岛屿探险路径 **可以多次踏足同一个岛屿**，但 **绝不能走倒塌的桥**；

一条有趣的岛屿探险回路是一条 **以同一个岛屿为起点和终点** 的安全岛屿探险路径，并且它至少踏足两个不同的岛屿。

但特别的，**有趣的岛屿探险回路除了起点能经过两次以外，其它的岛屿都只能经过一次**（显然，你当然不觉得重复探访你已经踏足过的岛屿很有趣）。

为了保证你的安全，你做足了功课，拿到了群岛的地图。仔细研究这个古老的地图，你发现每两个岛之间都有至少一条路可以抵达，并且第 $i$ 架桥上竟然藏着价值为 $w_i$ 的宝藏！

然而，你又发现群岛间的桥是非常稀少的，这些桥总是满足一个规律：**以同一个岛屿为起点的不同的有趣探险回路一定不会经过相同的一架桥**。

你将可以空降到任意一个岛屿开始你的探险，途中你可以收集宝藏，但最终你 **必须回到岛屿** $1$，才能安全地返回。

现在，你想知道在 **确保自己安全** 的情况下最大的能收集到的宝藏的价值和。

inputFormat:
第一行两个正整数 $n, m$，表示小岛的数量和连接小岛的桥梁的总数量；

接下来的 $m$ 行，每行共三个正整数，其中第 $i$ 行为 $u_i, v_i, w_i$ ，含义如题。

outputFormat: 一行共一个整数，表示在 **确保自己安全** 的情况下最大的能收集到的宝藏的价值和。

hint:
本题采用 **捆绑测试**，开启 **O2优化**。

$\text{Subtask 1 (3 pts)}:$ 保证不存在有趣的探险回路；

$\text{Subtask 2 (7 pts)}:$ 保证 $1 \le n \le 10$；

$\text{Subtask 3 (10 pts)}:$ 保证没有两个有趣的探险回路经过同一个岛屿；

$\text{Subtask 4 (10 pts)}:$ 保证 $w_i = 1$；

$\text{Subtask 5 (20 pts)}:$ 保证 $1 \le n \le 2000$；

$\text{Subtask 6 (20 pts)}:$ 保证 $1 \le n \le 10^5$；

$\text{Subtask 7 (30 pts)}:$ 没有特殊限制。

对于所有数据，满足 $1 \le n \le 3\times10^5$，$1 \le m \le10^6$，$1 \le w_i \le 10^9$。

---

#### 样例 #1 解释

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

> 上为群岛的地图，圆圈代表岛屿，圆圈间的线代表桥，
>
> 圆圈中的数字是岛屿的编号，线旁的数字是桥上宝藏的价值。

![合法解](https://cdn.luogu.com.cn/upload/image_hosting/4jyob32q.png)

从 $7$ 号岛屿出发，沿着上图的方向和顺序走，收集到的宝藏价值和为 $15$，即为答案。


title: 【模板】原根

description:
给定整数 $n$，求它的所有原根。

为了减小你的输出量，给出输出参数 $d$，设 $n$ 的所有原根有 $c$ 个，从小到大分别为 $g_1,\ldots,g_c$，你只需要依次输出 $g_d,g_{2d},\ldots,g_{\lfloor\frac{c}{d}\rfloor\times d}$。

---

如果你不了解原根的定义，可以自行查找资料或阅读下列定义：

正整数 $g$ 是正整数 $n$ 的原根，当且仅当 $1\leq g\leq n-1$，且 $g$ 模 $n$ 的阶为 $\varphi(n)$。

inputFormat:
**本题包含多组数据**。

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

接下来 $T$ 行：每行两个整数 $n,d$，表示一组询问数据。

outputFormat:
对于每组数据：

第一行输出一个整数 $c$，表示 $n$ 的原根个数，第二行输出 $\lfloor\dfrac{c}{d}\rfloor$ 个数，按照题目描述中要求输出。

注意：即使 $\lfloor\dfrac{c}{d}\rfloor=0$，也需要输出一个空行。

hint:
【样例解释】

对于第 $1,2,4,6$ 组数据，给出的 $n$ 的所有原根都出现在输出中。

对于第 $3$ 组数据，$25$ 的原根集合为 $\{2,3,8,12,13,17,22,23\}$。

对于第 $5$ 组数据，$9$ 的原根集合为 $\{2,5\}$。

【数据范围】

对于 $100\%$ 的数据，$1\leq T\leq 10$，$2\leq n\leq 10^6$，$1\leq d\leq 200$，保证输出的数的总个数不超过 $10^5$。


title: [JSOI2013] 侦探 JYY

description:
JSOI 的世界里一共有 $N$ 个不同的事件（依次由 $1$ 到 $N$ 编号），以及 $M$ 条线索。每一条线索对应一个二元组 $(x,y)$，表示事件 $x$ 发生会导致事件 $y$ 发生。

**注意： 线索是单向的，也就是如果 $y$ 发生了，并不代表 $x$ 一定会发生。**

线索是有传递性的， 即如果存在线索 $(x,y)$ 以及 $(y,z)$， 那么 $x$ 发生则会导致 $z$ 发生。

同时由于世界是合理的，任意一个事件 $x$ 一定不会通过某些线索导致事件 $x$ 本身发生。

另外，整个世界仅包含这 $M$ 条线索， 我们不认为一些事件会凭空发生（就像福尔摩斯永远不会认为诡异的凶杀案是源于神的谴责）。具体而言，对于某个事件 $x$， 如果 $x$ 发生了，并且存在某个事件可能导致 $x$ 发生，那么一定至少有一个可能导致 $x$ 发生的事件发生了。

现在已知世界上的 $M$ 条线索，以及 $D$ 个已经发生的事件，那么由此推断，
哪些事件一定已经发生了呢？

inputFormat:
第一行包含用空格隔开的三个整数，分别为 $N$，$M$ 和 $D$。

接下来 $M$ 行，每行两个整数 $x$，$y$ 表示线索 $(x,y)$， 满足 $1\leq x,y\leq N$。

接下来 $D$ 行为 $D$ 个 $1$ 到 $N$ 之间不同的整数， 表示已知的已经发生的事件。

outputFormat: 包含一行至少 $D$ 个由空格隔开的严格递增的正整数， 表示根据 $M$ 条线索以及 $D$ 个已知事件 JYY 所能推断出的一定发生了的事件。

hint:
### 样例解释

在第一个样例中，由于事件 $1$ 和事件 $2$ 这两个事件中的任何一个发生都会导致事件 $3$ 发生，所以我们并不能确定到底哪个事件发生了。

在第二个样例中，由于事件 $4$ 发生了，所以事件 $2$ 和事件 $3$ 中至少有一个发生了。而不论哪一个发生了，都可以推出事件 $1$ 发生了。

最终由于事件 $1$ 发生了，使得我们可以推断出，所有 $4$ 个事件都必然发生了。

### 数据范围

对于 $100\%$ 的数据，$1\leq D\leq N\leq 10^3,1\leq M\leq 10^5$。


title: 简单题

background: zbw 遇上了一道题，由于他急着去找 qby，所以他想让你来帮他做。

description:
给你 $n,k$ 求下式的值：

$\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^kf(\gcd(i,j))\gcd(i,j)$

其中 $\gcd(i,j)$ 表示 $i,j$ 的最大公约数。

$f$ 函数定义如下：

如果 $k$ 有平方因子 $f(k)=0$，否则 $f(k)=1$。

**Update:平方因子定义 如果存在一个整数 $k(k>1),k^2|n$ 则 $k$ 是 $n$ 的一个平方因子**

**请输出答案对 $998244353$ 取模的值。**

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

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


title: [国家集训队] 文学

description:
巨酱和主席是一对好朋友。他们都很喜欢读书，经常一起阅读相关领域书籍，进行系统的学习。一天主席列出了一份列表，里面共 $p$ 本书，其中不乏《约翰克里斯多夫》，《名人传》等名著。作为一名在文学上有很高修养的知名青年，巨酱打算用尽量少的时间把这份列表中的所有书籍都读完。

作为一名文化人，巨酱阅读书籍的方式也与一般人不同。他使用一种叫做“批量阅读”的阅读方式。首先他根据自己的喜好，对每本书给出了个参数 $x,y$，其中 $i$ 本书的两个参数为 $x_i,y_i$。当然，由于巨酱独特的口味，可能有两本不同的书，它们的 $x,y$ 参数均相同。而每次阅读的时候，他会设置三个系数 $a, b, c$，所有满足 $a \times x+b \times y \leq c$ 的书籍都可以通过这次“批量阅读”读完，这次批量阅读总共需要 $w$ 的时间。
现在，巨酱有 $n$ 种 “批量阅读”的方案，第 $i$ 种“批量阅读”三个参数为 $a_i,b_i,c_i$，需要的时间为 $w_i$。现在巨酱打算从这 $n$ 种“批量阅读”中选出若干，使得巨酱可以用尽量少的时间读完所有的书。现在我们想知道，巨酱最少用多少时间？

inputFormat:
第一行两个正整数 $n,p$，分别表示“批量阅读”的方案数以及书的数量。

接下来 $n$ 行，每行四个整数，其中第 $i$ 行包含四个整数 $a_i,b_i,c_i,w_i$，表示第 $i$ 种“批量阅读”的方案。

接下来 $p$ 行，每行两个整数，其中第 $i$ 行包含两个整数 $x_i,y_i$，表示第 $i$ 本书的参数。

outputFormat: 一行一个整数，表示最少需要的时间。若无论如何也无法读完全部书籍，则输出 $−1$。

hint: 对于 $100\%$ 的测试数据，$1 \leq n,p \leq 100，−10^6 \leq a_i,b_i,c_i,x_i,y_i \leq 10^6， 0 \lt w_i \leq 10^6$，且保证对于任何一种“批量阅读”方案，其 $a_i$ 与 $b_i$ 不会同时为 $0$。且不存在 $i, j$（$i$ 不等于 $j$）使得 $a_i \times b_j=a_j \times b_i$。


title: [加油武汉] SIR 模型

background:
SIR 模型将总人口分为以下三类：

- 易感者(susceptibles)，其数量记为 $s(t)$ ，表示 $t$ 时刻未染病但有可能被该类疾病传染的人数；
- 染病者(infectives)，其数量记为 $i(t)$，表示 $t$ 时刻已被感染成为病人而且具有传染力的人数；
- 恢复者(recovered)，其数量记为 $r(t)$，表示 $t$ 时刻已从染病者中移出的人数。

设总人口为$N(t)$，则有$N(t)=s(t)+i(t)+r(t)$。

SIR模型的建立基于以下三个假设：

1. 不考虑人口的出生、死亡、流动等种群动力因素。人口始终保持一个常数，即 $N(t) \equiv K $。
2. 一个病人一旦与易感者接触就必然具有一定的传染力。假设 $t$ 时刻单位时间内，一个病人能传染的易感者数目与此环境内易感者总数 $s(t)$ 成正比，比例系数为 $\beta$，从而在t时刻单位时间内被所有病人传染的人数为 $\beta s(t)i(t)$。
3. $t$ 时刻，单位时间内从染病者中移出的人数与病人数量成正比，比例系数为$\gamma$，单位时间内移出者的数量为 $\gamma i(t)$。

description:
我们将这个模型简化一下，初始有感染者 $I$ 人和易感者 $S$ 人，对于每一天当前有 $I_i$ 个感染者，$S_i$ 个易感者，$R_i$ 个恢复者，则每天会有 $\lceil \beta S_iI_i \rceil$ 人被感染（由易感者变成感染者），有 $\lceil \gamma I_i \rceil$ 人被治愈（由感染者变成恢复者） 。

其中 $\beta$ 为感染系数 $\gamma$ 为恢复系数 $\lceil \rceil$ 为上取整符号。

求 $n$ 天后，有多少易感者 $S$，感染者 $I$，和恢复者 $R$ 。

注: 感染者和恢复者都是每天结算的，结算的结果只和当天开始的时候的值有关，即感染者当天恢复不影响他当天感染别人。

若计算被感染人数超过易感者人数则全员被感染。

inputFormat:
第一行三个正整数，分别表示第 $0$ 天易感者人数 $S_0$ 和感染者人数$I_0$，以及天数 $n$（刚开始恢复者数 $R_0=0$）。

第二行两个浮点数，分别表示感染系数 $\beta$ 和恢复系数 $\gamma$。

outputFormat: 一行三个整数，分别表示 $n$ 天后的易感者人数 $S$ 、感染者人数 $I$ 和恢复者$R$。


title: [加油武汉] 体温调查

background:
在疫情扩散后，疾控中心的医护人员对来自武汉的人员进行了家庭访问，对体温进行测量。医护人员从疾控中心出发，按照一定顺序对所有家庭进行访问，然后汇总数据。

家庭列表上记录着类似于`A街道B小区C号楼D户`一样的住址，按照字典顺序排列，因此每个区域中的家庭在列表中总是相邻的。医护人员在访问完某个区域（比如B1小区）的所有家庭后，需要将数据送至上一层（比如A街道）的管理机构中，然后继续访问（比如B2小区）中的家庭。

也就是说，医护人员的移动路径类似一颗**树**，其中树根代表疾控中心，树叶代表家庭，而中间的结点代表一层一层的管理区域。结点的孩子代表下一层的区域（或者家庭），是有序的。从根到某个家庭的路径上所有的点正好组成了这个家庭的地址。

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

如图，4家的地址分别为（按顺序）
- A1-B1-C1-Z1
- A1-B1-C1-Z2
- A1-B1-Z3
- A2-B2-C3-Z4

箭头仅代表归属关系，所有路均可双向通行。

本质上，题目给出的树就是住址构成的 **字典树**/**Trie树** 。

description:
给出一颗树，根结点编号为$1$。有一名医护人员从根出发，沿着树边移动，去每个叶子采集信息，最后返回根。他的采集顺序是固定的，每当走到一个结点$u$，他会先走向编号最小的孩子，并访问完其中所有的家庭并回到$u$，然后再走向编号第二小的孩子，依此直到访问完$u$子树中所有的家庭返回上一层。可以发现访问叶子的顺序也正好是家庭住址列表上的顺序。

沿着树边移动需要一定时间，为了节约时间，可以将家庭列表分成连续的$k$段，并让$k$个医护人员同时从根出发，每人访问一个区间中的家庭然后返回。请你计算出统计完所有家庭的体温所需要的最短时间。

inputFormat:
第一行两个整数$n, k$，分别表示树中的结点数和医护人员数。

接下来$n-1$行，每行三个整数$u, v, w$，表示一条从$u$到$v$，经过花费时间$w$的边。

outputFormat: 一行一个整数，表示统计完所有家庭的最短时间。

hint:
对 $30\%$ 的数据，$1 \le n \le 20$

对另外 $10 \%$ 的数据，$k = 1$

对另外 $20 \%$ 的数据，$k = 2$

对 $100\%$ 的数据，$1 \le n \le 2*10^5, 1 \le k \le m, 1 \le u, v \le n, 0 \le w \le 10^9$，$m$为叶子数。

### 样例说明
图示见题目背景。

第一个人的路径为RT->Z1->Z2->RT，耗时66。

第二个人的路径为RT->Z3->Z4->RT，耗时32。

让一个人访问Z2，另一个人访问Z1、Z3、Z4的方案是不合法的。


title: 洪水

description: 小 A 走到一个山脚下，准备给自己造一个小屋。这时候，小 A 的朋友（`op`，又叫管理员）打开了创造模式，然后飞到山顶放了格水。于是小 A 面前出现了一个瀑布。作为平民的小 A 只好老实巴交地爬山堵水。那么问题来了：我们把这个瀑布看成是一个 $n$ 个节点的树，每个节点有权值（爬上去的代价）。小 A 要选择一些节点，以其权值和作为代价将这些点删除（堵上），使得根节点与所有叶子结点不连通。问最小代价。不过到这还没结束。小 A 的朋友觉得这样子太便宜小 A 了，于是他还会不断地修改地形，使得某个节点的权值发生变化。不过到这还没结束。小 A 觉得朋友做得太绝了，于是放弃了分离所有叶子节点的方案。取而代之的是，每次他只要在某个子树中（和子树之外的点完全无关）。于是他找到你。

inputFormat:
输入文件第一行包含一个数 $n$，表示树的大小。

接下来一行包含 $n$ 个数，表示第 $i$ 个点的权值。

接下来 $n-1$ 行每行包含两个数 $fr,to$ 。表示树中有一条边 $(fr,to)$ 。

接下来一行一个整数，表示操作的个数。

接下来 $m$ 行每行表示一个操作，若该行第一个数为 $Q$，则表示询问操作，后面跟一个参数 $x$ ，表示对应子树的根；若为 $C$ ，则表示修改操作，后面接两个参数 $x,t$ ，表示将点 $x$ 的权值加上 $t$。

outputFormat: 对于每次询问操作，输出对应的答案，答案之间用换行隔开。

hint:
$1 \leq n \leq 200000,1 \leq fr,to \leq n,1 \leq x \leq n$，权值和 $t$ 均在 `int` 范围内且非负。

BZOJ4712


title: [SNOI2013] Quare

description:
4.20 四川芦山地震发生后，抗震救灾委员会接到一个紧急任务，四川省给该委员会发了一份地图，这份地图给出了该省一些城市的情况：任两个城市是用一条或多条公路连接起来的，也可以没有公路连接，但是每个城市都可以直接或间接地到达另外的城市，注意这些公路是可以双向行驶的。由于最近余震、暴雨造成泥石流倾泻，使得车辆在这些公路上行驶很不安全，于是四川省决定尽快对部分公路进行抢修，以保障救援车辆行车安全。

该省对所有的公路情况都进行了勘察，分析估计了抢修某段公路所需要花费的时间，并记录在地图中。现在该省希望抗震救灾委员会能找到一个方案，该方案决定出哪些公路需要抢修，使得抢修后的公路仍能保证任意两个城市之间都能直接或间接地相连，同时为了安全起见，即使某一条抢修的公路被泥石流阻断了，任意两城市仍能保持这个性质。由于时间紧迫，抗震救灾委员会还需保证找到的这个方案总抢修时间最短。

inputFormat:
第一行为一个整数 $T$，为数据总数，接下来按顺序给出每个数据的描述。

首先是两个整数 $n, m$ 分别表示城市数量和公路数量，下面 $m$ 行每行三个整数 $x, y, c$ 描述了一条公路的情况：$x$ 城市与 $y$ 城市之间的一条公路，抢修该公路需要 $c$ 个单位时间。

注意上面所说的两城市间可能有多条公路。

outputFormat: 按顺序输出每个数据的结果，如果找不到一条合适的方案，则输出一行 `impossible`，否则输出一个整数，为抢修的最优方案所需要的总时间。

hint: 对于 $100\%$ 的数据，$1 \leq n \leq 12$，$1 \leq m \leq 40$。


title: 「StOI-1」IOI计数

description:
给定一个长度为 $n$ 字符串 $S$ ，同时进行 $m$ 次操作：
操作1：$1$ $x$ $c$ 表示将第 $x$ 个字符改为 $c$（ $c$ 只会为 `I` 或 `O` ）。
操作2：$2$ $l$ $r$ 询问字符串 $S$ 中有多少对三元组 $(i,j,k)$ 满足：
$S_{i}=$ `I` ,$S_{j}=$ `O` ,$S_{k}=$ `I` 并且 $l≤i<j<k≤r$ 。

inputFormat:
输入第一行两个正整数 $n$ 和 $m$ 。
接下来一行是长度为 $n$ 的字符串 $s$ ，接下来 $m$ 行是操作。
含义均如题。

outputFormat: 输出若干行：对于所有操作2，输出查询的答案，要求每个答案之间换行。


title: 无向图三元环计数

background: 无向图 $G$ 的三元环指的是一个 $G$ 的一个子图 $G_0$，满足 $G_0$ 有且仅有三个点 $u, v, w$，有且仅有三条边 $\langle u, v \rangle, \langle v, w \rangle, \langle w, u \rangle$。两个三元环 $G_1, G_2$ 不同当且仅当存在一个点 $u$，满足 $u \in G_1$ 且 $u \notin G_2$。

description: 给定一个 $n$ 个点 $m$ 条边的简单无向图，求其三元环个数。

inputFormat:
每个测试点有且仅有一组测试数据。

输入的第一行是用一个空格隔开的两个整数，分别代表图的点数 $n$ 和边数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行两个用空格隔开的整数 $u, v$，代表有一条连接节点 $u$ 和节点 $v$ 的边。

outputFormat: 输出一行一个整数，代表该图的三元环个数。

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

共有 $5$ 个三元环，每个三元环包含的点分别是 $\{1, 2, 4\}, \{2, 3, 4\}, \{2, 3, 5\}, \{2, 4, 5\}, \{3, 4, 5\}$。

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

**本题采用多测试点捆绑测试，共有两个子任务**。

- Subtask 1（30 points）：$n \le 500$，$m \le {10}^3$。
- Subtask 2（70 points）：无特殊性质。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le m \le 2 \times {10}^5$，$1 \le u, v \le n$，给出的图不存在重边和自环，**但不保证图连通**。

**【提示】**

- 请注意常数因子对程序效率造成的影响。


title: [USACO05JAN] Muddy Fields G

description:
大雨侵袭了奶牛们的牧场。

牧场是一个 $R \times C$ 的矩形，其中 $1 \leq R,C \leq 50$。大雨将没有长草的土地弄得泥泞不堪，可是小心的奶牛们不想在吃草的时候弄脏她们的蹄子。为了防止她们的蹄子被弄脏，约翰决定在泥泞的牧场里放置一些木板。每一块木板的宽度为 $1$ 个单位，长度任意，每一个板必须放置在平行于牧场的泥地里。

约翰想使用最少的木板覆盖所有的泥地．一个木板可以重叠在另一个木板上，但是不能放在草地上。

inputFormat:
第一行两个整数 $R,C$。

接下来 $R$ 行，每行 $C$ 个字符，描述牧场，其中 `*` 为泥地，`.` 为草地。

outputFormat: 输出一个整数，最少需要多少木板。


title: [USACO05JAN] The Wedding Juicer G

description:
约翰的奶牛们找到了一份不错的兼职一设计冲压式榨汁机．榨汁机设计如下：

一个 $W \times H$ 的底座（$3\leq W,H \leq 300$），每一个 $1 \times 1$ 的方格上都放有一个高度为 $B$（$1 \leq B \leq 10^9$）的柱子，用来榨汁。假设柱子之间都被完美地粘合了，这样水不会顺着柱子与柱子之间的空隙流走。

但是约翰一直不知道，这么一个榨汁机，到底能装多少果汁？假设榨汁机周围没有任何东西，也就是说，边界上的水都会流走，有些榨汁机则根本不能装下任何的果汁。

inputFormat:
第一行两个整数 $W$ 和 $H$。

接下来 $H$ 行，每行 $W$ 个数字，代表了高度。

outputFormat: 输出最多能装多少果汁。


title: [USACO05JAN] Naptime G

description:
贝茜是一只非常缺觉的奶牛．她的一天被平均分割成 $N$ 段（$3 \leq N \leq 3830$），但是她要用其中的 $B$ 段时间（$2 \leq B \lt N$）睡觉。每段时间都有一个效用值 $U_i$（$0 \leq U_i \leq 2 \times 10^5$），只有当她睡觉的时候，才会发挥效用。

有了闹钟的帮助，贝茜可以选择任意的时间入睡，当然，她只能在时间划分的边界处入睡、醒来。

贝茜想使所有睡觉效用的总和最大。不幸的是，每一段睡眠的第一个时间阶段都是“入睡”阶段，而旦不记入效用值。

时间阶段是不断循环的圆（一天一天是循环的嘛），假如贝茜在时间 $N$ 和时间 $1$ 睡觉，那么她将得到时间 $1$ 的效用值。

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

接下来 $N$ 行，每行一个整数，表示第 $i$ 个时段的效用值。

outputFormat: 输出最大效用值。

hint: 从第 $4$ 个时段入睡，到第 $1$ 个时段结束醒来。


title: [USACO05JAN] Sumsets S

description: 给出一个整数 $N$，将 $N$ 分解为若干个 $2$ 的次幂的和，共有多少种方法？

inputFormat: 输入一个整数 $N$（$1 \leq N \leq 10^6$）。

outputFormat: 输出方案数对 $10^9$ 取模的结果。


title: [USACO05JAN] Watchcow S

description:
Farmer John 有 $N$ 个农场（$2 \leq N \leq 10^4$），这些农场由 $M$ 条道路连接（$1 \leq M \leq 5 \times 10^4$）。不保证没有重边。

Bassie 从 $1$ 号农场开始巡逻，每条路必须从两个方向各走**恰好一遍**，最后回到 $1$ 号农场。

请输出一条满足上述要求的路径。

保证这样的路径存在。如果有多条路径，任意输出一条即可。

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

接下来 $M$ 行，每行两个整数 $u,v$，描述一条 $u$ 到 $v$ 的道路。

outputFormat: 输出经过的农场，一行一个。


title: [USACO05JAN] Moo Volume S

description:
Farmer John 的农场上有 $N$ 头奶牛（$1 \leq N \leq 10^5$），第 $i$ 头奶牛的位置为 $x_i$（$0 \leq x_i \leq 10^9$）。

奶牛很健谈，每头奶牛都和其他 $N-1$ 头奶牛聊天。第 $i$ 头奶牛和第 $j$ 头奶牛聊天时，音量为 $|x_i-x_j|$。

请您求出所有奶牛聊天音量的总和。

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

接下来 $N$ 行，每行一个整数 $x_i$。

outputFormat:
输出总音量。

**保证答案在 64 位带符号整数的表示范围内。**

hint:
- 子任务 1（原测试数据，1 分）：$N \leq 10^4$；
- 子任务 2（99 分）：无特殊限制。


title: 「Stoi2031」黑色毛衣

background: > 看着那白色的蜻蜓 在空中忘了前进 还能不能 重新编织 脑海中起毛球的记忆 再说我爱你 可能雨也不会停 黑色毛衣 藏在哪里 就让回忆永远停在那里 ——《黑色毛衣》

description: 让想起了和雨在一起的时候。由于雨是一个爱玩的女孩子，所以他们有很多玩具，其中就有一种像 **白色蜻蜓** 一样的玩具，现在留在了让的身边，共有 $n$ 只。每只 **白色蜻蜓** 的翅膀长度分别是 $1,2,\dots,n$，并且可以张开成 $(0,\pi)$ 之间的任意角度。让认为使其中 $m$ 只 **白色蜻蜓** 分别张开翅膀使双翅末端的距离都为整数且互不相同的场景是在 **编织** 一份 **记忆**。他认为两份 **记忆** 相同当且仅当可以将 $m$ 只 **白色蜻蜓** 按某种方式重排后一一对应使对应的蜻蜓翅膀长度和双翅距离都相等。他想请你告诉他能编织出多少份不同的记忆。你只需要求出答案 $ans\bmod{p}$ 的值。

inputFormat: 一行三个正整数 $n,m,p$。

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


title: [BalticOI2007] Escape

description:
战犯们企图逃离监狱，他们详细地计划了如何逃出监狱本身，逃出监狱之后他们希望在附近的一个村子里找到掩护。

村子（下图中的 B）和监狱（图中的 A）中间有一个峡谷，这个峡谷也是有士兵守卫的。守卫峡谷的士兵们坐在岗哨上很少走动，每个士兵的观察范围是 $100$ 米。士兵所处位置决定了战犯们能否安全通过峡谷，安全通过的条件就是在任何时刻战犯们距离最近的士兵大于 $100$ 米。

给定峡谷的长、宽和每个士兵在峡谷中的坐标，假定士兵的位置一直保持不变，请你写一个程序计算战犯们能否不被士兵发现，顺利通过峡谷。

如果不能，那么战犯们最少需要消灭几个士兵才能安全通过峡谷（无论士兵是否被另一个士兵看到，他都可以被消灭）。

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

inputFormat:
第一行有三个整数 $l$，$w$ 和 $n$，分别表示峡谷的长度、宽度和士兵的人数。

接下来的 $n$ 行，每行两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个士兵在峡谷的坐标，坐标以米为单位，峡谷的西南角坐标为 $(0, 0)$，东北角坐标为 $(l, w)$，见上图。

注意：通过峡谷可以从 $(0, ys)$，（其中 $ys$ 满足 $0\leq ys \leq w$） 到 $(l, ye)$（其中 $ye$ 满足 $0 \leq ye \leq w$），其中 $ys$， $ye$ 不一定是整数。

outputFormat: 只有一行，为一个整数，即安全通过峡谷需要消灭的士兵的人数，如果不需要消灭任何士兵，则输出 $0$。

hint: 对于 $100\%$ 的数据，满足：$1 \leq w \leq 5\cdot 10^4$，$1\leq l \leq 5\cdot 10^4$，$1\leq n \leq 250$，$0 \leq x_i \leq l$，$0 \leq y_i \leq w$。


title: [EER2] 相同的数字

description:
每天早上在黑板上会写有 $n$ 个固定的数字，但是这些数字太无序了，所以每天晚上兔子想把他们变成相同的数字。

有两种操作 :

* 选择一个下标 $k$，将 $a_k$ 替换为 $a_k+1$。一次操作花费 $c_1$ 的时间。

* 选择一个下标 $k$，将 $a_k$ 替换为大于 $a_k$ 的最小质数。一次操作花费 $c_2$ 的时间。

兔子很懒，所以他不想花费太多的时间，你需要帮他计算出将所有数变相同的最小时间。

总共会有 $q$ 天。兔子每天的状态不同，所以每一天会有不同的 $c_1$ 和 $c_2$。但是黑板上的数不会变。

第一天花费的时间当然会影响第二天的状态。每天真实的 $c_1 = c'_1\oplus
 (T \times (lastans \bmod 2^{17}))$，$c_2 = c'_2 \oplus
 (T\times (lastans \bmod 2^{17}))$。其中 $\oplus$ 为 $\operatorname{xor}$ 运算，$lastans$ 为上一次的答案，最初 $lastans = 0$。

inputFormat:
第一行三个整数 $n, q, T$，表示黑板上数的个数、总天数和一个参数。

第二行 $n$ 个整数 $a_i$，表示黑板上的数。

接下来 $q$ 行，每行两个整数 $c'_1, c'_2$，表示每天操作花费的参数。

outputFormat: 共 $q$ 行，每行一个整数，表示一天的最小时间。


title: [Ynoi2010] y-fast trie

background:
谔谔我

本题读入量约 6 MB，输出量约 5 MB，请选择适合的输入输出方法

description:
给定一个常数 $C$，你需要维护一个集合 $S$，支持 $n$ 次操作：

- 操作1：给出 $x$，插入一个元素 $x$，保证之前集合中没有 $x$ 这个元素
- 操作2：给出 $x$，删除一个元素 $x$，保证之前集合中存在 $x$ 这个元素

每次操作结束后，需要输出 $\max\limits_{\substack{ i, j \in S \\ i \ne j }} \bigl( (i+j) \bmod C \bigr)$，即从 $S$ 集合中选出两个不同的元素，其的和 $\bmod~C$ 的最大值，如果 $S$ 集合中不足两个元素，则输出 `EE`。

本题强制在线，每次的 $x$ 需要 $\operatorname{xor}$ 上上次答案 ，如果之前没有询问或者输出了  `EE`，则上次答案为 $0$。

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

接下来 $n$ 行，每行有两个整数 $1~x$ 或 $2~x$，表示第一类或第二类操作。

outputFormat: 输出 $n$ 行，第 $i$ 行表示第 $i$ 次操作结束后的答案。

hint:
Idea：zhouwc，Solution：ccz181078&nzhtl1477，Code：ccz181078&nzhtl1477，Data：nzhtl1477

注意：本题采用**捆绑测试**，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

对于其中 $1\%$ 的数据，为样例 1。

对于另外 $9\%$ 的数据，集合中元素个数 $\le 1$。

对于另外 $19\%$ 的数据，$n\leq 500$。

对于另外 $19\%$ 的数据，$n\leq 10^4$。

对于另外 $19\%$ 的数据，$1\leq n,C \leq 10^5$。

对于 $100\%$ 的数据，$1\leq n \leq 5\times 10^5$，$1\leq C\leq 1073741823$，$0\leq x\leq 1073741823$。


title: 『MdOI R3』Yoshino

background:
『变成了精灵确实是遭遇了许多难过的事情，也遭遇了许多悲伤的事情。但是——我也得到了比这些难过和悲伤多得多的快乐与开心。』

『——我觉得，虽然澪小姐想要使用我的生命，但是作为交换，她不是也让我活了更长的时间了吗？』

『对了——差点忘了。四糸奈，……稍微一会儿，可以吗。』

『那么，正式介绍一下呢，——妈妈。』

『这位是七罪小姐，我——最重要的朋友。』

『这位是士道先生，是我——最喜欢的人。』

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

description:
Yoshino 给了你一个长度为 $n$ 的序列，第 $i$ 项为 $a_i$。

现在 Yoshino 会对数列进行 $m$ 次操作。

操作分成两种：

 - $1\  l\  r\  x$ Yoshino 把数列下标在 $[l,r]$ 区间内的数修改为了一个从 $x$ 开始公差为 $1$ 的等差数列。

 - $2$ Yoshino 需要查询整个数列中的逆序对个数。逆序对的定义为数对 $(i,j)$ 满足 $i<j$ 且 $a_i>a_j$。

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

第二行 $n$ 个整数，第 $i$ 个为 $a_i$。

接下来 $m$ 行，每行代表一个操作，含义见上。

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


title: 有趣的游戏

background: 小 A 和小 B 正在玩一个有趣的电脑游戏。

description:
游戏在一棵大小为 $n$ 的树上进行。其中每个点都有点权，第 $i$ 个点的点权为 $w_i$。

每一次系统会给出一条链，小 A 可以从这条链上找出两个**点权不同**的点 $x,y$，他的得分是 $w_x\bmod w_y$。然后小 B 会从**整棵树**中选取两个**小 A 没有选过**的点，计分方式同小 A。

为了保持游戏难度，系统有时会增加一个点的权值。

当然，小 A 会尽可能使自己得分最大，他想知道这个值是多少。同时，他想知道，在自己得分最大的情况下，小 B 的最大得分是多少。

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

接下来 $n-1$ 行，每行两个整数 $a,b$，表示 $a,b$ 之间有一条边。

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

接下来一行一个整数 $q$。

接下来 $q$ 行，每行三个整数 $opt,x,y$。

若 $opt=0$，将  $w_x$ 增加 $y$。

若 $opt=1$，表示系统给出一条从 $x$ 到 $y$ 的链。

outputFormat:
对于每一次 $opt=1$，输出一行两个整数 $suma,sumb$ 。分别表示小 A 的最大得分和在这情况下小 B 的最大得分 。

**如果小 A 无法选出两个权值不同的点，那么只输出一个数 $-1$。**

hint:
样例解释：

第一次：小 A 选择点 $3$ 和点 $2$，得分为 $3\bmod 4=3$，小 B 选择点 $6$ 和点 $1$ 得分为 $4\bmod 5=4$。

第二次：小 A 选择点 $2$ 和点 $1$，得分为 $4\bmod 5=4$，小 B 选择点 $7$ 和点 $6$ 得分为 $3\bmod 4=3$。

第三次：小 A 选择点 $2$ 和点 $1$，得分为 $4\bmod 5=4$，小 B 选择点 $7$ 和点 $6$ 得分为 $3\bmod 4=3$。

第四次：第 $2$ 个点点权变为 $5$。

第五次：小 A 选择点 $5$ 和点 $1$，得分为 $1\bmod 5=1$，小 B 选择点 $6$ 和点 $2$ 得分为 $4\bmod 5=4$。

第六次：小 A 可以选的点只有 $1,2$ ，点权都是 $5$，没有可以选的方案。

**本题采用捆绑测试。**
| Subtasks |$n,q$  |特殊性质  |分数  |
| :----------: | :----------: | :----------: | :----------: |
|Subtask1  |$\leq10^3$  |无  |$10$  |
|Subtask2  |$\leq10^5$  |树的形态，点权随机  |$15$  |
|Subtask3  |$\leq10^5$  |最多有 $5$ 种不同的点权，且没有修改 |$15$  |
|Subtask4  |$\leq10^5$  |树为一条链，且第 $i$$(i>1)$ 个点的父亲为 $i-1$ |$25$  |
|Subtask5  |$\leq10^5$  |无  |$35$  |

对于所有数据 $1 \leq n,q \leq 10^5$，$1 \leq w_i \leq 10^4$，增加的数为不大于 $10^3$ 的正整数，且输入为一棵合法的树。**保证任何时候不同种类的数大于等于 $4$。**


title: [EER1] 代价

background:
> 个人的遭遇，命运的多舛都使我被迫成熟，这一切的代价都当是日后活下去的力量。
——  三毛

小 Z 喜欢玩数字游戏。

description: 给出一个长度为 $n+2$ 的序列 $a_i$，其中第 $1$ 个数和第 $n+2$ 个数固定为 $1$。你每次可以选择序列中间的一个数删除（不能是第一个和最后一个），删除位置 $p$ 上的数的代价为 $a_{p-1} \times a_p \times a_{p+1}$。你需要执行这个操作直到无法操作为止。求最小的代价和。

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

第二行 $n$ 个正整数，第 $i$ 个数表示 $a_{i+1}$。

outputFormat: 一行一个正整数，表示最小的代价和。

hint:
样例一解释：

先删除 $3$，代价为 $6$，再删除 $2$，代价为 $2$，再删除 $1$，代价为 $1$。

总代价为 $6+2+1=9$。

---

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

对于 $100\%$ 的测试点：$1 \leq n \leq 10^6$，$1 \leq a_i \leq 10^4$。

本题共 $6$ 个子任务，各子任务的分值及约定如下：

子任务 $1$（$1$ 分）：$a_i = 1$。

子任务 $2$（$14$ 分）：$1 \leq n \leq 10$。

子任务 $3$（$5$ 分）：$1 \leq a_i \leq 2$。

子任务 $4$（$14$ 分）：$1 \leq n \leq 40$。

子任务 $5$（$26$ 分）：$1 \leq n \leq 500$。

子任务 $6$（$40$ 分）：无特殊限制。

#### 特别感谢

idea：smrsky

solu：CYJian

data：iostream


title: 最小路径

description: 一棵 $n$ 个点的树，每个点两个点权 $a_i$ 和 $b_i$，找一条长度为 $m$ 的简单路径，使 $\frac{\sum a_i}{\sum b_i}$ 最小。无解输出 $-1$。

inputFormat:
第一行两个正整数 $n$ 和 $m$。
第二行 $n$ 个正整数 $a_i$。
第三行 $n$ 个正整数 $b_i$。
以下 $n-1$ 行，每行两个正整数 $u,v$，为一条边的两个端点。

outputFormat: 输出最小值，**保留两位小数**。


title: [USACO06MAR] Milk Team Select G

description:
Farmer John 的 $N(1 \le N \le 500)$ 头奶牛打算参加一场世界级的产奶比赛 （Multistate Milking Match-up，MMM），他们已经摸清了其他队的实力。他们的总产奶量只要大于等于 $X$ 加仑（$1 \leq X \leq 10^6$），就能赢得胜利。

每头奶牛都能为全队贡献一定量的牛奶，数值在 $-10^4$ 到 $10^4$ 加仑之间（为啥有负数？因为有些奶牛会打翻其他奶牛产的牛奶）。

MMM 的目标是通过合作，增进家庭成员间的默契。为了支持比赛精神，奶牛们希望在赢得比赛的前提下，有尽可能多对奶牛间存在直系血缘关系。当然，所有奶牛都是女性，因此这里的直系血缘关系就是母女关系。

现在 FJ 摸清了所有奶牛间的血缘关系，希望算出一个团队在赢得胜利的前提下，最多有多少对奶牛存在血缘关系。注意：如果一个团队由某头奶牛和她的母亲和外祖母组成的话，这个团队只有两对血缘关系（她和她的母亲，她的母亲和外祖母）。

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

接下来 $N$ 行，每行两个整数，第一个整数是它能为团队贡献的产奶量，第二个整数为它的母亲的编号，如果她的母亲不在牛群里，这个数字为 $0$。

保证血缘关系不会出现环。

outputFormat:
输出在获胜的前提下，一个团队中最多存在多少血缘关系。

特别地，如果不存在一个团队能获胜，输出 $-1$。

hint:
最优的队伍包含 $1,2,3,5$ 这四头奶牛，总产奶量为 $9$ 加仑，共有两对血缘关系（$1,2$ 和 $1,3$）。

虽然 $2,3,5$ 这个组合产奶量更大，但是这个组合里没有血缘关系。


title: [USACO05DEC] Cow Patterns G

description:
Farmer John 的 $N$（$1 \leq N \leq 10^5$）头奶牛中出现了 $K$（$1 \leq K \leq 25000$）只坏蛋！这些坏蛋在奶牛排队的时候总站在一起。现在你需要帮助 FJ 找出他们。

为了区分，FJ 给每头奶牛发了号牌，上面写着一个 $1 \ldots S$ 之间的数字（$1 \leq S \leq 25$），虽然这不是个完美的方法，但也有一定作用。现在 FJ 记不得坏蛋们的具体号码，但他给出了一个模式串。原坏蛋的号码相同，模式串中的号码依旧相同，模式串中坏蛋号码的大小关系也和原号码相同。

例如模式串：$1,4,4,3,2,1$，原来的 $6$ 只坏蛋，最前面和最后面的号码相等且最小（不一定是 $1$），位置 $2,3$ 的坏蛋号码相同且最大（不一定是 $4$）。

现在有这样一个队列：$5, 6, 2, 10, 10, 7, 3, 2, 9$，它的子串 $2, 10, 10, 7, 3, 2$ 匹配模式串的相等关系和大小关系，这就可能是一个坏蛋团伙。

请找出所有团伙的可能情况。

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

接下来 $N$ 行，每行一个整数，代表第 $i$ 奶牛的编号。

接下来 $K$ 行，每行一个整数，表示模式串中第 $i$ 个位置的号码。

outputFormat:
第一行输出一个整数 $B$。

接下来 $B$ 行，每行一个整数，为一种可能的坏蛋团伙的起始位置。

所有位置按升序输出。


title: [USACO05DEC] Barn Expansion G

description:
Farmer John 有 $N$（$1 \leq N \leq 25000$）个矩形牛棚，它们的墙与坐标轴平行，且坐标在 $[0,10^6]$ 范围内。保证任意两个牛棚不重叠，但可能有公共的墙。

由于奶牛数量不断增加，FJ 打算扩张牛棚。一个牛棚是可以扩张的，当且仅当它的墙与其他牛棚的墙没有公共部分。如果两个牛棚有一个公共角，这两个牛棚均不可扩张。

请你求出有多少牛棚是可以扩张的。

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

接下来 $N$ 行，每行四个整数，分别代表牛棚左下角坐标和右上角坐标。

outputFormat: 输出可以扩张的牛棚数量。

hint: 前两个牛棚可以扩张。


title: [QkOI#R1] Quark and Equations

description:
给定 $n,m$，求有几组正整数对 $(i,j)$ 满足下列方程组：

$$
\begin{cases}
   i+j=n \\
   \lfloor\frac{i}{j}\rfloor+\lceil\frac{j}{i}\rceil=m
\end{cases}
$$

上式中，$\lfloor x\rfloor$ 表示对 $x$ 向下取整，$\lceil x\rceil$ 表示对 $x$ 向上取整。

inputFormat:
**本题单个数据点含多组数据。**

第一行一个整数 $T$ 表示这个数据点有几组数据。

接下来 $T$ 行每行两个整数 $n,m$ ，含义如题面所述。

outputFormat:
你的输出应有 $T$ 行。

对于每一组数据，输出一行一个整数表示你的答案。

hint:
### 样例解释

当 $n=m=2$ 时，只有 $(1,1)$ 满足条件。
当 $n=2,m=1$ 时，无解。
当 $n=6,m=2$ 时，只有 $(2,4),(3,3)$ 满足条件。

---

### 数据范围

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

- Subtask 1（10 pts）：$T,n,m\le 500$。
- Subtask 2（40 pts）：$T,n,m\le 5000$。
- Subtask 3（5 pts）：$m=1$。
- Subtask 4（5 pts）：$m>n$。
- Subtask 5（5 pts）：$m\in[n-1,n]$。
- Subtask 6（35 pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le n,m\le 10^{7}$。


title: [EER2] 直接自然溢出啥事没有

description:
给定一个整数 $n$，问有多少个长度为 $n$ 的字符串，满足这个字符串是一个“程序片段”。

具体定义如下：

单个分号 `;` 是一个“语句”。

空串 ` ` 是一个“程序片段”。

如果字符串 `A` 是“程序片段”，字符串 `B` 是“语句”，则 `AB` 是“程序片段”。

如果字符串 `A` 是“程序片段”，则 `{A}` 是“语句块”。

如果字符串 `A` 是“语句块”，则 `A` 是“语句”，`[]A` 和 `[]()A` 都是“函数”。

如果字符串 `A` 是“函数”，则 `(A)` 是“函数”，`A` 和 `A()` 都是“值”。

如果字符串 `A` 是“值”，则 `(A)` 是“值”，`A;` 是“语句”。

**注意：`A` 是 `B` 并不代表 `B` 是 `A`**。

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

hint:
### 样例一解释

合法的“程序片段”有：`;;;;`，`;;{}`，`;{;}`，`;{};`，`{;;}`，`{;};`，`{{}}`，`{};;`，`{}{}`。

注意：本题采用**捆绑测试**，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

子任务 1（$20$ 分）：$n\leq 10$。

子任务 2（$20$ 分）：$n\leq 100$。

子任务 3（$20$ 分）：$n\leq 2500$。

子任务 4（$40$ 分）：没有特殊限制。

对于 $100\%$ 的数据，$0\leq n\leq 10^4$。


title: [JSOI2015] symmetry

description:
张老师正在课堂上讲解正方形的对称模式。为了简单起见，他用 $01$ 方阵代表一个正方形图形，即把正方形分解成 $n\times n$ 的方格阵，$0$ 代表一个白色方格，$1$ 代表一个黑色方格。

首先讲到的是容易辨别的轴对称，正方形有 $4$ 个对称轴，分别是水平中线，竖直中线和两条对角线。如果一个正方形图形以某个对称轴做反射变换后保持不变，就称为轴对称图形。例如下面的两个图形都是轴对称图形。

```plain
100  010
100  101
111  000
```

张老师继续讲解正方形的旋转对称。如果一个正方形图形以中心点旋转 $180$ 度后保持不变，就称为 $180$ 度对称图形。如果以中心点顺时针旋转 $90$ 度后保持不变，就称为 $90$ 度对称图形，例如下面的两个图形左边是 $180$ 度对称图形，右边是 $90$ 度对称图形。

```plain
0011  1011
1110  1110
0111  0111
1100  1101
```

张老师接着说，如果一个正方形图形具有两个互相垂直的对称轴，就称为 $4$ 对称图形，如果关于 $4$ 个对称轴全部对称，就称为 $8$ 对称图形。按照定义，$90$ 度对称图形也是 $180$ 度对称图形，$8$ 对称图形也是 $4$ 对称图形。当正方形图形的边长为偶数时，该图形的中心是最中间 $4$ 个方格的公共顶点，当正方形图形的边长为奇数时，该图形有一个中心方格，该图
形的中心也是它的中心方格的中心。边长为 $1$ 的图形显然是 $8$ 对称图形。

张老师给学生证明了两个定理。

- 定理 $1$：一个正方形图形是 $4$ 对称图形当且仅对它是 $180$ 度对称图形和轴对称图形。
- 定理 $2$：一个正方形图形是 $8$ 对称图形当且仅对它是 $90$ 度对称图形和轴对称图形。

最后是练习时间，张老师要求学生寻找在大正方形图形中出现的各种对称图形。请你编程实现这个要求。设输入一个 $01$ 方阵，输出满足 $8$ 对称，$90$ 度对称，$4$ 对称，$180$ 度对称和轴对称的最大子连续方阵的边长。子连续方阵是指选择若干相邻行列的子方阵，代表在大图形中出现的小图形。

inputFormat: 输入的第一行是一个正整数 $n$，表示大正方形图形的边长。然后是 $n$ 行长度为 $n$ 的 $01$ 字符串。

outputFormat: 输出有一行，包含 $5$ 个以空格隔开的自然数，分别表示在输入中出现的最大 $8$ 对称，$90$ 度对称，$4$ 对称，$180$ 度对称和轴对称的子连续方阵的行数。

hint:
#### 样例说明

大图形有水平对称轴，左上角有一个 $2\times 2$ 的 $8$ 对称图形，中间 $3$ 行最右 $3$ 列构成 $4$ 对称图形。

---

#### 数据范围

对于 $100\%$ 的数据，$5\leq n\leq 500$。


title: [JSOI2015] isomorphism

description:
一个无向树的度数为 $2$ 的结点称为假结点，其它结点称为真结点。一个无向树的简化树其结点由原树的全体真结点组成，两个真结点之间有边当且仅当它们在原树中有边，或者在原树中有一条联结这两个结点的路，其中间节点全是假结点。两个无向树各自的简化树如果同构，即存在结点之间的一一对应，使得在一个树中的任意两个结点之间有边当且仅当它们的对应结点在另一个树中有边，则称原来的两个无向树实质同构。

给定若干个无向树，将相互实质同构的无向树只保留一个其余删除。统计剩下的相互不实质同构的无向树个数，并将它们的简化树结点个数从小到大输出。

inputFormat:
第一行只有一个正整数 $m$。

后面依次输入 $m$ 棵无向树，每棵无向树先用一行输入结点个数 $n$，结点就用 $1$ 到 $n$ 表示，然后用 $n-1$ 行输入 $n-1$ 条无向边，每行有两个 $1$ 到 $n$  之间的不同的正整数，用一个空格隔开，代表这两个结点之间有无向边。两棵树之间无空行。

outputFormat:
第一行输出一个正整数，即输入中不计实质同构包含无向树的个数 $m_0\ (1\leq m_0\leq m)$。

第二行包含不严格递增的 $m_0$ 个正整数，表示这 $m_0$ 棵无向树的简化树结点个数。相邻两数用一个空格隔开。


title: [JSOI2013] 吃货 JYY

background:
作为 JSOI 的著名吃货，JYY 的理想之一就是吃遍全世界的美食。要走遍全世界当然需要不断的坐飞机了。而不同的航班上所提供的餐食是很不一样的：比如中国的航班会提供中餐，英国的航班有奶茶和蛋糕，澳大利亚的航班有海鲜，新加坡的航班会有冰激凌……

JYY 选出了一些他特别希望品尝餐食的航班，希望制定一个花费最少的旅游计划，能够从南京出发，乘坐所有这些航班并最后回到南京。

description:
世界上一共有 $N$ 个 JYY 愿意去的城市，分别从 $1$ 编号到 $N$。JYY 选出了 $K$ 个他一定要乘坐的航班。除此之外，还有 $M$ 个 JYY 没有特别的偏好，可以乘坐也可以不乘坐的航班。

一个航班我们用一个三元组 $(x,y,z)$ 来表示，意义是这趟航班连接城市 $x$ 和 $y$，并且机票费用是 $z$。每个航班都是往返的，所以 JYY 花费 $z$ 的钱，既可以选择从 $x$ 飞往 $y$，也可以选择从 $y$ 飞往 $x$。

南京的编号是 $1$，现在 JYY 打算从南京出发，乘坐所有 K 个航班，并且最后回到南京，请你帮他求出最小的花费。

inputFormat:
输入数据的第一行包含两个整数 $N$ 和 $K$。

接下来 $K$ 行，每行三个整数 $x,y,z$ 描述必须乘坐的航班的信息，数据保证在这 $K$ 个航班中，不会有两个不同的航班在同一对城市之间执飞。

第 $K+2$ 行包含一个整数 $M$，接下来 $M$ 行，每行三个整数 $x,y,z$ 描述可以乘坐也可以不乘坐的航班信息。

outputFormat: 输出一行一个整数，表示最少的花费。数据保证一定存在满足 JYY 要求的旅行方案。

hint:
### 样例解释

一个可行的最佳方案为 $1\rightarrow 2\rightarrow 3\rightarrow 5\rightarrow 4\rightarrow 1$。

机票所需的费用为 $1000+1000+300+500+300=3100$。

### 数据范围

对于 $100\%$ 的数据，$2\leq N\leq 13,0\leq K\leq 78,2\leq M\leq 200,1\leq x,y\leq N,1\leq z\leq 10^4$。


title: 环 Rings

background:
> 一九二九不出手，三九四九冰上走，五九六九隔河看杨柳；
>
> 七九河开，八九雁来，九九加一九，耕牛遍地走。

「九」自古以来就是一个奇妙的数字，而你今天要解决的问题，也与「九」有关。

description:
你有一个 $n$ 连环，和你熟知的九连环有着相同的结构。

![这是一个九连环](https://cdn.luogu.com.cn/upload/image_hosting/x68krf0v.png)

> 上图是一个九连环。

顾名思义，$n$ 连环有一个长长的横梁，上面挂着 $n$ 个 **彼此影响** 的环。

我们给这 $n$ 个环编号，其中最靠横梁头部的环为第 $1$ 个环，其次为第 $2$ 个环，以此类推……最靠横梁尾部的环为第 $n$ 个环；

定义 $f_i$ 表示第 $i$ 个环的状态，其中 $f_i = 1$ 表示这个环在横梁上，$f_i = 0$ 表示这个环不在横梁上；

定义 **拆装一个环** 为使环的状态 **取反**，即状态从 $1$ 变成 $0$ 或从 $0$ 变成 $1$。

这些环的合法拆装规则如下：

1. 第 $1$ 个环随时可以单独拆装；
2. 第 $k+1$ 个环可以单独拆装，当且仅当 $f_k=1$ 且 $\forall i < k$，都有 $f_i = 0$；
3. 若 $f_1 = f_2$，则第 $1,2$ 两个环可以一起拆装。

现在你需要解决的问题是：已知一个 $n$ 连环的初始状态，请你求出拆除这个 $n$ 连环的最少拆装步数。

inputFormat:
本题数据量较大，故采取 **特殊** 输入方式。

第一行一个正整数 $n$。

第二行一个正整数 $m$；

接下来 $m$ 行输入描述了初始状态：

第 $i + 2$ 行有两个整数 $len_{i}, st_{i}$，表示往初始的 $n$ 连环的尾部连续添加 $len_{i}$ 个状态为 $st_{i}$ 的环。

outputFormat:
一行共一个整数，表示从拆下这个 $n$ 连环所需要的最少拆装次数。

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

hint:
本题采用 **捆绑测试**，开启 **O2优化**。

$\text{Subtask 1 (10 pts)}:$ 保证 $1 \le n \le 20$；

$\text{Subtask 2 (15 pts)}:$ 保证 $1 \le n\le 1000$；

$\text{Subtask 3 (15 pts)}:$ 保证初始状态中 **只有** $1$ 个 $1$；

$\text{Subtask 4 (30 pts)}:$ 保证 $1 \le n \le 10^7$；

$\text{Subtask 5 (30 pts)}:$ 没有特殊限制。

对于所有数据，满足 $1 \le n \le 10^{18}$，$1 \le m \le 10^5$，$st_{i} \in \{0, 1\}$，$len_{i} \ge 1$

数据保证 $\sum\limits_{i=1}^m len_{i} = n$。

---

#### 样例 #1 解释

样例描述的是 $4$ 连环，初始状态为 `1101`。

用最少合法拆装次数完成的方法如下：

```plain
1. 1101 -> 1100
2. 1100 -> 0100
3. 0100 -> 0111
4. 0111 -> 0110
5. 0110 -> 0010
6. 0010 -> 0011
7. 0011 -> 0000
```

共 $7$ 步。

---

#### 题外话

本题中 $n$ 连环的第 $3$ 条拆装规则，在大部分的九连环玩法说明中都没有提到，但它确实是一个真实可行的操作呢！


title: 【模板】Prufer 序列

description:
请实现 Prüfer 序列和无根树的相互转化。

为方便你实现代码，尽管是无根树，我们在读入时仍将 $n$ 设为其根。

对于一棵无根树，设 $f_{1\dots n-1}$ 为其**父亲序列**（$f_i$ 表示 $i$ 在 $n$ 为根时的父亲），设 $p_{1 \dots n-2}$ 为其 **Prüfer 序列**。

另外，对于一个长度为 $m$ 的序列 $a_{1 \dots m}$，我们设其**权值**为 $\operatorname{xor}_{i = 1}^m i \times a_i$。

inputFormat:
第一行两个整数 $n,m$，表示树的点数和转化类型。

若 $m = 1$，第二行一行 $n-1$ 个整数，表示父亲序列。
若 $m = 2$，第二行一行 $n-2$ 个整数，表示 Prufer 序列。

outputFormat:
若 $m = 1$，一行一个整数，表示给出的父亲序列对应的 Prüfer 序列的权值。
若 $m = 2$，一行一个整数，表示给出的 Prüfer 序列对应的父亲序列的权值。


title: How Many of Them

description:
在无向连通图中，若一条边被删除后，图会分成不连通的两部分，则称该边为割边。

求满足如下条件的无向连通图的数量：

1. 由 $n$ 个结点构成，结点有标号。

2. 割边不超过 $m$ 条。

3. 没有重边和自环。

答案对 $10^{9}+7$ 取模。

inputFormat: 仅一行，两个整数 $n$ 和 $m$。

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

hint:
$2≤n≤50,0≤m≤\dfrac{n(n-1)}{2}$

Source: Gennady Korotkevich (tourist), ITMO University.


title: [JSOI2015] 送礼物

background:
JYY 和 CX 的结婚纪念日即将到来，JYY 来到萌萌开的礼品店选购纪念礼物。

萌萌的礼品店很神奇，所有出售的礼物都按照特定的顺序都排成一列，而且相邻
的礼物之间有一种神秘的美感。于是，JYY 决定从中挑选连续的一些礼物，但究
竟选哪些呢？

description:
假设礼品店一共有 $N$ 件礼物排成一列，每件礼物都有它的美观度。排在第 $i\ (1\leq i\leq N)$ 个位置的礼物美观度为正整数 $A_i$。JYY 决定选出其中连续的一段，即编号为 $i,i+1,\cdots,j-1,j$ 的礼物。选出这些礼物的美观程度定义为

$$\frac{M(i,j)-m(i,j)}{j-i+K}$$

其中 $M(i,j)$ 表示 $\max\{A_i,A_{i+1},\cdots,A_j\}$，$m(i,j)$ 表示 $\min\{A_i,A_{i+1},\cdots,A_j\}$，$K$ 为给定的正整数。
由于不能显得太小气，所以 JYY 所选礼物的件数最少为 $L$ 件；同时，选得太多也不好拿，因此礼物最多选 $R$ 件。JYY 应该如何选择，才能得到最大的美观程度？由于礼物实在太多挑花眼，JYY 打算把这个问题交给会编程的你。

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

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

每组数据包含两行。第一行四个非负整数 $N,K,L,R$。第二行包含 $N$ 个正整数，依次表示 $A_1,A_2,\cdots,A_n$。

outputFormat:
输出 $T$ 行，每行一个非负实数，依次对应每组数据的答案，数据保证答案不
会超过 $10^3$。输出四舍五入保留 $4$ 位小数。

hint: 对于 $100\%$ 的数据，$T\leq 10$，$N,K\leq 5\times 10^4$，$1\leq A_i\leq 10^8$，$2\leq L,R\leq N$。


title: [JSOI2015] 字符串树

background:
萌萌买了一颗字符串树的种子，春天种下去以后夏天就能长出一棵很大的字符串树。字符串树很奇特，树枝上都密密麻麻写满了字符串，看上去很复杂的样
子。

description:
字符串树本质上还是一棵树，即 $N$ 个节点 $N-1$ 条边的连通无向无环图，节点从 $1$ 到 $N$ 编号。与普通的树不同的是，树上的每条边都对应了一个字符串。萌萌和 JYY 在树下玩的时候，萌萌决定考一考 JYY。每次萌萌都写出一个字符串 $S$ 和两个节点 $U,V$，JYY 需要立即回答 $U$ 和 $V$ 之间的最短路径（即 $U,V$ 之间边数最少的路径，由于给定的是一棵树，这样的路径是唯一的）上有多少个字符串以 $S$ 为前缀。

JYY 虽然精通编程，但对字符串处理却不在行。所以他请你帮他解决萌萌的难题。

inputFormat:
输入第一行包含一个整数 $N$，代表字符串树的节点数量。

接下来 $N-1$ 行，每行先是两个数 $U,V$，然后是一个字符串 $S$，表示节点 $U$ 和节点 $V$ 之间有一条直接相连的边，这条边上的字符串是 $S$。输入数据保证给出的是一棵合法的树。

接下来一行包含一个整数 $Q$，表示萌萌的问题数。

接下来 $Q$ 行，每行先是两个数 $U,V$，然后是一个字符串 $S$，表示萌萌的一个问题是节点 $U$ 和节点 $V$ 之间的最短路径上有多少字符串以 $S$ 为前缀。

outputFormat: 输出 $Q$ 行，每行对应萌萌的一个问题的答案。

hint: 对于 $100\%$ 的数据，$1\leq N,Q\leq 10^5$，输入所有字符串长度不超过 $10$ 且只包含 `a~z` 的小写字母。


title: [JSOI2015] 非诚勿扰

background: JYY 赶上了互联网创业的大潮，为非诚勿扰开发了最新的手机 App 实现单身大龄青年之间的“速配”。然而随着用户数量的增长，JYY 发现现有速配的算法似乎很难满足大家的要求，因此 JYY 决定请你来调查一下其中的原因。

description:
应用的后台一共有 $N$ 个女性和 $N$ 个男性，他们每个人都希望能够找到自己的合适伴侣。为了方便，每个男性都被编上了 $1$ 到 $N$ 之间的一个号码，并且任意两个人的号码不一样。每个女性也被如此编号。

JYY 应用的最大特点是赋予女性较高的选择权，让每个女性指定自己的“如意郎君列表”。每个女性的如意郎君列表都是所有男性的一个子集，并且可能为空。如果列表非空，她们会在其中选择一个男性作为自己最终接受的对象。

JYY 用如下算法来为每个女性速配最终接受的男性：将“如意郎君列表”中的男性按照编号从小到大的顺序呈现给她。对于每次呈现，她将独立地以 $P$ 的概率接受这个男性（换言之，会以 $1-P$ 的概率拒绝这个男性）。如果她选择了拒绝，App 就会呈现列表中下一个男性，以此类推。如果列表中所有的男性都已经呈现，那么中介所会重新按照列表的顺序来呈现这些男性，直到她接受了某个男性为止。显然，在这种规则下，每个女性只能选择接受一个男性，而一个男性可能被多个女性所接受。当然，也可能有部分男性不被任何一个女性接受。

这样，每个女性就有了自己接受的男性（“如意郎君列表”为空的除外）。现在考虑任意两个不同的、如意郎君列表非空的女性 $a$ 和 $b$，如果 $a$ 的编号比 $b$ 的编号小，而 $a$ 选择的男性的编号比 $b$ 选择的编号大，那么女性 $a$ 和女性 $b$ 就叫做一对不稳定因素。

由于每个女性选择的男性是有一定的随机性的，所以不稳定因素的数目也是有一定随机性的。JYY 希望你能够求得不稳定因素的期望个数（即平均数目），从而进一步研究为什么速配算法不能满足大家的需求。

inputFormat:
输入第一行包含 $2$ 个自然数 $N,M$，表示有 $N$ 个女性和 $N$ 个男性，以及所有女性的“如意郎君列表”长度之和是 $M$。

接下来一行一个实数 $P$，为女性接受男性的概率。

接下来 $M$ 行，每行包含两个整数 $a,b$，表示男性 $b$ 在女性 $a$ 的“如意郎君列表”中。

outputFormat: 输出 $1$ 行，包含一个实数，四舍五入后保留到小数点后 $2$ 位，表示不稳定因素的期望数目。

hint:
对于 $100\%$ 的数据，$1\leq N,M\leq 5\times 10^5$，$0.4\leq P<0.6$。

输入保证每个女性的“如意郎君列表”中的男性出现且仅出现一次。


title: [CEOI2019] 立方填词

description:
立方填词是一种特殊的填词游戏。填词之前，你需要选择立方体的边长 $a$ ，然后你就可以建立一个有 $a^3$ 个单位立方体的立方体了。这个大立方体有 $12$ 条边。然后，你去掉所有没有接触大立方体边的单位立方体。下图展示了当 $a=6$ 时建立的最终立方体。

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

最后，你需要给剩下的每个单位立方体填上一个字母。对于这个立方体，填词之后，每条边上的单词都应该是有意义的。每条边都可以双向阅读，只要从一个方向读起来有意义即可。

下图展示了当 $a=6$ 时的一个立方体。一些单位立方体已经填上了字母。你已经可以沿这个大立方体的三条边读到 **SUBMIT**，**ACCEPT** 和 **TURING** 三个单词了。

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

给定一系列有意义的单词，每个单词可以在合法的立方体的任意一条边上出现。求可以构造多少种不同的立方体对 $998244353$ 取模。

即使一个立方体可以通过旋转和镜像操作变成另一个立方体，也认为这两个立方体**是不同的**。

inputFormat:
第一行一个整数 $n$ ，表示单词的个数。

接下来 $n$ 行，每行一个单词，表示可以在大立方体的边上出现的单词。单词长度大于等于 $3$ ，并且小于等于 $10$ 。

保证所有单词都不同。

outputFormat: 输出一个整数，表示可以构造的不同立方体数对 $998244353$ 取模后的结果。

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

第一个样例中，唯一一种可能是立方体的所有边上的单词均为 **radar**。

#### 样例解释#2

第二个样例中，有两种立方体，其中一个旋转后可以得到另一个立方体。立方体所有边上的单词都是 **robot**，两个立方体的不同之处在于左下角的字母是 **r** 还是 **t**。

#### 样例解释#3

第三个样例与第二个类似，注意阅读方向不会影响答案。

#### 样例解释#4

第四个样例中，如果把 **bob** 填在立方体的每条边上，有一种立方体。还有 $2^
{12} = 4096$ 种立方体，每条边都填 **baobab**（对于 $12$ 条边中的一条，我们有两种可能的阅读顺序）。

#### 数据范围

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

详细子任务限制及分值如下表：

| 子任务编号 | 限制 | 分值 |
| :----------: | :----------: | :----------: |
| 1 | 单词中只包含小写的 `a` 到 `f` | $21$ |
| 2 | 单词中只包含小写的 `a` 到 `p` | $29$ |
| 3 | 单词中包含小写的 `a` 到 `p` 和大写的 `A` 到 `P` | $34$ |
| 4 | 单词中包含小写的 `a` 到 `z`，大写的 `A` 到 `Z` 和数字 `0` 到 `9`  | $16$ |


title: [CEOI2012] 工作规划

description:
CEOI 在 $N$ 天内收到了 $M$ 个任务，每个任务需要 $1$ 台机器工作 $1$ 天来完成。CEOI 有很多台机器，每台机器一天只能完成一个任务。 CEOI 要求每个任务最多只能推迟 $D$ 天完成。换言之，如果一个客户在第 $S$ 天提交了一个任务，CEOI 必须在第 $S+D$ 天之前完成它。

请你写程序求出每个任务最多推迟 $D$ 天的前提下，最少需要多少台机器才能按要求完成所有任务。

inputFormat:
第一行输入包含三个整数， $N$ 是 CEOI 接受任务的天数， $D$ 是每个任务最多可以推迟的天数。$M$ 是任务的个数。

第二行是 $M$ 个被空格分隔的整数。第 $i$ 个数代表收到第 $i$ 个任务时间。第 $N-D$ 天之后均没有任务。所有的任务按照输入顺序从 $1$ 到 $N$ 依次编号。

outputFormat: 输出一个整数，即能完成任务的最少机器数。


title: [JSOI2015] 套娃

background: 刚从俄罗斯旅游回来的 JYY 买了很多很多好看的套娃作为纪念品！JYY 由于太过激动，把所有的套娃全部都打开了。而由于很多套娃长得过于相像，JYY 现在不知道该如何把它们装回去了（他实在搞不清，应该把哪个套娃装到哪个里面去了）。

description:
JYY 一共有 $N$ 个拆开的套娃，每个套娃从 $1$ 到 $N$ 编号。编号为 $i$ 的套娃有一个外径 $Out_i$ 和一个内径 $In_i$（$In_i<Out_i$）。

对于套娃 $i$ 和套娃 $j$，如果满足 $Out_i<In_j$，那么套娃 $i$ 就可以装到套娃 $j$ 里面去。

注意，一个套娃内部，不允许并排的放入多个套娃。

也就是说，如果我们将 $i$ 装到 $j$ 的内部之后，还存在另一个套娃 $k$，也满足 $Out_k<In_j$，我们此时是不允许再将 $k$ 放到 $j$ 内部的（因为 $j$ 的内部已经放入了 $i$）。但是，如果 $k$ 还满足 $Out_k<In_i$，那么我们允许先将 $k$ 放到 $i$ 的内部，然后再把 $k$ 和 $i$ 作为一个整体放入 $j$ 的内部。

JYY 认为一套好的套娃，内部的空隙一定是尽量少的。如果套娃 $j$ 内部装入了套娃 $i$，那么我们认为，套娃 $j$ 内部产生的空隙为 $In_j-Out_i$；如果套娃 $j$ 的内部什么也没有装，那么套娃 $j$ 的空隙则就是 $In_j$。

JYY 也希望，那些长得更加好看的套娃，里面可以填的尽量满一些；而相对
那些不那么好看的套娃，JYY 也就相对不那么介意一些。为此 JYY 对于编号为 $i$ 的套娃设置了一个好看度 $B_i$，如果这个套娃内部还存在 $K$ 的空隙，那么 JYY 对于这个套娃就会产生 $K\times Bi$ 的不满意度。

JYY 对于一个套娃安装方案的不满意度，就是每个套娃产生的不满意度的总
和。JYY 希望找出一个，不满意度最小的套娃安装方案。

inputFormat: 第一行包含一个正整数 $N$。接下来 $N$ 行，每行包含三个正整数 $Out_i,In_i,B_i$，表示 $i$ 号套娃的外径，内径，以及好看度。

outputFormat: 输出文件包含一行一个整数，表示不满意度的最小值。

hint: 对于 $100\%$ 的数据，$N\leq 2\times 10^5$，$1\leq In_i<Out_i\leq 10^4$，$1\leq B_i\leq 10^9$。


title: [JSOI2015] 圈地

background:
JYY 在火星买了一大块矩形的地皮做房地产开发。由于地皮实在是太大了，JYY 把这块地皮划分成了 $N$ 行 $M$ 列的小方格，并在每一格中建造一栋房子。历时若干年，开发终于宣告结束，JYY 也可以把这些房子挂牌出售了。现在他找到了两位非同寻常的土豪买家：南南和强强。

麻烦的是，南南和强强是水火不容的。为了保证他们俩不发生矛盾，JYY 需要把卖给他们俩的房子用墙隔开。不过造墙是需要钱的，JYY 作为倒卖地皮的专家，自然想挣尽可能多的钱，因此他邀请到你帮他设计最优的出售方案。

description:
JYY 把这块地皮划分成了 $N$ 行 $M$ 列的矩形，且矩形的每一格中建造一栋房子。现在，南南和强强已经将他们的购买意见提交给了 JYY。对于每一栋房子，南南和强强已经给定了他们的出价（不想购买，或愿意以一定价格购买），并且由于他们已经协商好了各自的势力范围，因此不存在两个人同时想买一栋房子的情况。JYY 可以选择每一栋房子是否出售（因为不存在两个人同时想买一栋房子的情况，若 JYY 选择出售一栋房子，它的买家就是确定的）。房子卖给强强和南南以后，JYY 就能获得卖出房子出价的总和。

不过，作为售后服务，JYY 需要通过造墙（将两栋相邻的房子用一堵墙隔开）把两个人的房子完全隔开。所谓完全隔开，就是指造出的墙以及四周的边界将整个区域划分成若干个不连通的部分，每个部分里面只有一个人的房子。当然，造墙也是需要钱的，而且价格不菲。不过 JYY 当初在宣传时声称造墙完全免费，所以这部分钱只好由 JYY 自己出了。

JYY 请你为他规划每幢房子是否要卖出以及建造哪些围墙，才能使得卖房子的收益减去造围墙的花费最大。另外一个好消息是整个地皮的四周已经建好了墙，因此 JYY 可以利用这些建好的墙达到目的。下图就是用墙将区域划分成 $3$ 个不连通的部分的例子。格子中的数字代表出价（数字的含义参考输入格式），边上的数值代表造墙的价格。四周的墙（边界）本来就有，不需要 JYY 花额外的代价去建造。

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

inputFormat:
输入第一行包含两个用空格隔开的自然数 $N$ 和 $M$。

接下来 $N$ 行，每行 $M$ 个整数，第 $i$ 行第 $j$ 列的整数 $a$ 描述了位于 $(i,j)$ 房子的出售信息。如果 $a=0$，说明强强和南南都不想买这个位置上的房子；如果 $a>0$，说明强强想以价格 $a$ 买这个位置上的房子。如果 $a<0$，说明南南想以价格 $-a$ 买这个位置上的房子。

接下来 $N-1$ 行，每行 $M$ 个整数。第 $i$ 行第 $j$ 列的数表示第 $i$ 行第 $j$ 列的房子与第 $i+1$ 行第 $j$ 列的房子之间的墙的造价。

接下来 $N$ 行，每行 $M-1$ 个整数。第 $i$ 行第 $j$ 列的数表示第 $i$ 行第 $j$ 列的房子与第 $i$ 行第 $j+1$ 列的房子之间的墙的造价。

outputFormat: 输出仅有一行包含一个整数，表示 JYY 的最大收益。

hint: 对于 $100\%$ 的数据，$1\leq N,M\leq 200$，任何价格都不超过 $1000$。


title: [JSOI2015] 串分割

background:
JYY 每天都会在地铁上度过很长的时间。

为了打发时间，JYY 随手写下了一个很长的环形的数字字符串，并且陷入了沉思。

description:
JYY 写下了一个长度为 $N$ 的，仅包含 `1`，`2`，……，`9` 这 $9$ 种不同字符的环形字符串 $S$。JYY 希望把 $S$ 进行 $K$ 次切割，并分成 $K$ 个非空的子串。对于每一个子串，由于其仅包含数字，我们可以将其看成一个十进制数——因此
经过 $K$ 次切割，JYY 可以得到 $K$ 个不同的十进制数。JYY 希望他得到的这 $K$ 个数中，最大的那一个尽量小。

inputFormat:
第一行包含两个整数 $N$ 和 $K$。

第二行包含一个长度为 $N$ 的字符串 $S$。

outputFormat: 输出一行包含一个正整数，表示最佳分割方案中，JYY 所得到的那 $K$ 个数中，最大的那一个。

hint: 对于 $100\%$ 的数据，$3\leq N\leq 2\times 10^5$，$2\leq K\leq N$。


title: [JSOI2015] 地铁线路

description:
JSOI 王国的地铁又涨价了！正在 JSOI 旅游的 JYY 非常不开心。这次票价改革后，乘客并不是按照乘坐的距离收费，而是按照换乘次数进行收费的！JYY 也要按此更新他的线路搜索软件了。JYY 心想，在支付同样票价的前提下，岂不
是坐的站数越多，自己就赚的越多嘛！于是 JYY 希望开发一个线路搜索软件，使得自己总能够“赚”的最多！

JSOI 地铁一共有 $N$ 条线路 $S$ 个车站。第 $i$ 条地铁线路包含 $L_i$ 个站。所有地铁线路都是一条从首发站到终点站的直线型线路（不存在例如北京地铁 2 号线或者 10 号线那样奇葩的环线）。同时，每一条地铁线路都是双向运行的。如果有不同的线路经过同一个地铁站，那么乘客就可以在那个地铁站进行换乘。根据 JSOI 地铁的最新收费方式，每当乘客进入一列正在运行的地铁列车，都需要支付 $1$ 的费用。因此，假设乘客一共换乘了 $x$ 次，那么就需要总共支付 $x+1$ 的乘车费用。由于地铁线路都是双向运行的，因此在任意一站都可以换乘该线地铁反方向运行的列车。不过，需要注意的是，即使是换乘同样线路的反方向列车，也是需要付费的（因为总是需要先下车，再重新上车的）。

JYY现在要从 $A$ 站坐地铁前往 $B$ 站。假设对于任意一条地铁线路，相邻两站间地铁的运行时间均为 $1$ 分钟，并且列车停站和换乘均不耗时间，JYY想知道

1. 他最少需要支付的票价是多少钱；
2. 在支付最少票价的前提下，他最多可以乘坐多少分钟的地铁。

inputFormat:
第一行包含两个正整数 $N$ 和 $S$。

第二行包含 $S$ 个由空格隔开的字符串，表示 $S$ 个站点的站名。

接下来 $N$ 行，每行描述一条地铁线路。对于其中第 $i$ 行，首先包含一个正整数 $L_i$，接下来 $L_i$ 个字符串，表示这条地铁线路上的站点名称。一条线路允许多次停靠同一个站点。

第 $N+3$ 行，包含两个不同的字符串 $A$ 和 $B$，表示 JYY 目前在 $A$ 站，希望坐地铁前往 $B$ 站。

outputFormat:
第一行包含一个整数 $C$，表示 JYY 最少需要支付的乘车费用。

第二行包含一个整数 $T$，表示 JYY 在花费 $C$ 的前提下，可以乘坐地铁的最长时间。

如果不存在两个站点之间的路线，第一行输出`-1`，第二行输出 `0`。

hint:
对于 $100\%$ 的数据，$2\leq N\leq 4\times 10^5$，$S\leq 3\times 10^5$，$\sum L_i\leq 8\times 10^5$。

保证输入所有字符串的长度不超过 $40$，且仅包含字母、数字以及横线 `-`。


title: 「HMOI R1」可爱的德丽莎

background: Polaris_Dane 非常菜，他不仅沉迷于数论，而且喜欢玩崩坏 3。

description:
可爱的德丽莎希望你能帮她求出

$$
\sum_{x = 1}^n\sum_{y = 1}^n\sum_{i = 1}^x[x \bot k_1][i \bot x]\cdot i\cdot \sum_{j = 1}^y[y \bot k_2][j \bot y]\cdot j
$$
的结果。

其中 $[x \bot y] = \begin{cases}1 & \operatorname{gcd}(x,y)=1 \\ 0 & \operatorname{gcd}(x,y)\neq 1\end{cases}$

德丽莎这么可爱，你怎么能不答应她呢？

由于答案可能很大，所以德丽莎只想知道它对 $998244353$ 取模后的结果。

inputFormat: 共一行三个整数 $n, k_1, k_2$。

outputFormat: 仅一行一个数，为所求的答案对 $998244353$ 取模后的结果。


title: 查找 Search

background:
>   也许，同学间最好的结局就是朋友吧。

$\mu ry$ 是一个可爱的女孩子。

在她所住的小区里有排成一排的 $n$ 个垃圾桶，从左至右第 $i$ 个垃圾桶里都装着编号为 $a_i$ 的垃圾。

$\mu ry$ 不喜欢无序，于是就想把社区里编号和为 $w$ 的垃圾都清在一起。

但是调皮的 $\text{LeverImmy}$ 可能会把某个垃圾桶里的垃圾偷换成另一种。

生气的 $\mu ry$ 想考考 $\text{LeverImmy}$ 一个区间 $[l, r]$ 内是否存在编号和为 $w$ 的垃圾。

但 $\text{LeverImmy}$ 也不会解决这个问题，于是他找到了聪明的你。

description:
给定 $n$ 个垃圾桶，你需要维护一个数据结构，支持以下操作：

-   `1 pos val` 表示将 第 $pos$ 个垃圾桶里的垃圾的编号换成 $val$；

-   `2 l r` 询问在 $[l\oplus cnt, r\oplus cnt]$ 内是否存在垃圾编号和为 $w$ 的 **两个** 垃圾桶。

其中 $\oplus$ 表示异或运算，$cnt$ 表示在 **此次询问之前**，答案为 `Yes` 的个数。

对于每个操作 2，若存在请输出 `Yes`，不存在请输出 `No`。

值得注意的是，对于所有询问， $w$ 为 **同一个数**。

inputFormat:
第一行共三个整数 $n, m, w$，表示序列长度、接下来的操作个数与 $w$。

第二行共 $n$ 个整数 $a_1, a_2, \cdots, a_n$ 描述了这个每个垃圾桶内垃圾的编号 $a$。

接下来的 $m$ 行，每行三个整数，格式为 `opt x y`。

outputFormat:
令操作 2 的次数为 $t$，输出数据共 $t$ 行。

第 $i$ 行表示第 $i$ 个操作 2 的结果，即 `Yes` 或 `No`。

hint:
本题采用 **捆绑测试**，开启 **O2优化**。

$\text{Subtask 1 (7 pts)}:$ 保证 $1 \le n, m, w \le 2\cdot10^3$，**时限 $1\text{s}$**；

$\text{Subtask 2 (20 pts)}:$ 保证 $1 \le n, m, w \le 1\cdot10^5$，$opt = 2$，**时限 $2\text{s}$**；

$\text{Subtask 3 (30 pts)}:$ 保证 $1 \le n, m, w \le 1\cdot10^5$，**时限 $2\text{s}$**；

$\text{Subtask 4 (43 pts)}:$ 没有特殊限制，**时限 $4\text{s}$**；

对于所有数据， $1 \le n, m, w \le 5\cdot10^5$，$0 \le a_i \le w$。

数据保证对于每个操作，$1 \le pos \le n$，$0 \le val \le w$，$1 \le l \le r \le n$。

由于输入输出量较大，建议使用更快的输入输出方式。

---

#### 输入 #1 解释

第一次操作，询问区间 $[1, 4]$ 中是否有两个数加起来为 $6$，显然有$a_1 + a_4 = 6$，因此输出 `Yes`；

第二次操作，修改 $a_4$ 为 $1$，则序列变为 $[1, 3, 2, 1, 5, 6]$；

第三次操作，询问区间 $[1, 4]$ 中是否有 **两个** 数加起来为 $6$，无，因此输出 `No`。

第四次操作，询问区间 $[2, 6]$ 中是否有两个数加起来为 $6$，显然有 $a_4 + a_5 = 6$，因此输出 `Yes`。


title: 【模板】子集卷积

background: 这是一道模板题。

description:
给定两个长度为 $2^n$ 的序列 $a_0,a_1,\cdots,a_{2^n-1}$ 和 $b_0,b_1,\cdots,b_{2^n-1}$，你需要求出一个序列 $c_0,c_1,\cdots,c_{2^n-1}$，其中 $c_k$ 满足：

$$c_k=\sum_{\substack{{i \& j=0}\\{i~\mid~ j=k}}} a_i b_j$$

其中$~\mid~$表示按位或，$\&$表示按位与。

答案对 $10^9+9$ 取模。

inputFormat:
第一行输入一个正整数 $n$ ，表示集合的大小。

第二行有 $2^n$ 个整数，描述了 $a$。

第三行有 $2^n$ 个整数，描述了 $b$。

outputFormat: 输出一行 $2^n$ 个整数，表示 $c$。

tags: 快速莫比乌斯变换 FMT


title: [Ynoi2010] Self Adjusting Top Tree

description:
平面上有 $n$ 条线段。

共 $m$ 次询问，每次询问给出一个边平行于坐标轴的矩形，问 每条与矩形有交的线段与矩形的交的长度之和 与 所有线段的长度之和 的 比值，要求输出与标准答案的相对误差或绝对误差不超过 $10^{-6}$。

线段以 $x_1\;y_1\;x_2\;y_2$ 的形式给出，表示以 $(x_1,y_1),(x_2,y_2)$ 为端点的线段，保证任意两条线段没有交点或重合部分，且 $x_1\ne x_2,y_1\ne y_2$。

矩形以 $x_1\;y_1\;x_2\;y_2$ 的形式给出，表示矩形 $\{(x,y)|x_1\le x\le x_2,y_1\le y\le y_2\}$，保证 $x_1< x_2, y_1< y_2$。

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

接下来 $n$ 行，每行四个由空格分隔的整数 $x1,y1,x2,y2$，表示线段。

接下来一行一个整数 $m$。

接下来 $m$ 行，每行四个由空格分隔的整数 $x1,y1,x2,y2$，表示询问的矩形。

outputFormat: 对每个询问，输出一行，一个介于 $0$ 和 $1$ 之间的十进制小数，表示答案

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

对于 $100\%$ 的数据，$1\le n,m\le 10^5, 1\le x_1,y_1,x_2,y_2\le 10^6$。


title: [Ynoi2010] Worst Case Top Tree

description:
给定序列 $a_0,a_1,a_2\dots,a_n,a_{n+1}$；

满足 $a_0=a_{n+1}=+\infty$，$a_1,a_2,\dots,a_n$ 在输入中给出；

对 $1\le x \le n$，称 $\max_{0\le i<x,a_i\ge a_x} i$ 和 $x$ 是**相邻**的，且 $\min_{x<i\le n+1,a_i>a_x} i$ 和 $x$ 是**相邻**的；

如果 $x$ 和 $y$ 相邻，则 $y$ 和 $x$ 也相邻；

如果 $0\le b_1,b_2,b_3,b_4,b_5,b_6\le n+1$，且 $b_i$ 和 $b_{i+1}$ 相邻，$b_1$ 和 $b_6$ 相邻，$b_i$ 互不相同，则称集合 $\{b_1,b_2,b_3,b_4,b_5,b_6\}$ 是一个六元环（即判断两个六元环是否相同时，不考虑 $b_i$ 的顺序）。

共有 $m$ 次修改操作，每次修改操作给出 $x\;y$，将 $a_x$ 改为 $a_x+y$；

每次修改后要求输出六元环的个数；

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

第二行 $n$ 个整数表示 $a_1\;a_2\;\dots\;a_n$；

第三行一个整数 $m$；

接下来 $m$ 行，每行两个整数 $x\;y$ 表示一次修改操作。

outputFormat: 共 $m$ 行，每行一个整数，表示每次修改后的六元环个数。

hint:
Idea：ccz181078，Solution：ccz181078，Code：ccz181078&zx2003，Data：nzhtl1477&zx2003

对于 $100\%$ 的数据，以上提到的所有数值为整数，且 $1\le n,m\le 5\cdot 10^5;\;1\le x\le n;\;1\le a_i,y\le 10^9$。


title: [USACO19FEB] Painting the Barn G

description:
Farmer John 不太擅长多任务处理。他经常分心，很难完成一些长期的项目。目前，他正在谷仓的一侧刷油漆，但他一直忙着在很小的区域涂抹油漆，然后由于抚育母牛的需要而陷入困境，使谷仓的某些部分比其他部分涂有更多的油漆。

我们将谷仓的墙描述为一个 X-Y 平面，每次涂油漆的区域都是一个矩形。FJ 在这个平面上绘制了 $N$ 个矩形，每个矩形的边均与坐标轴平行。因此我们用矩形的左下角和右上角坐标来描述一个矩形。

FJ 想在谷仓里涂几层油漆，这样就不需要在不久的将来再次重新涂油漆。但是，他不想浪费时间涂过多的油漆。事实证明，$K$ 层涂料是最佳用量。但是因为涂油漆的面积太小了，FJ 并不太高兴。他决定最多再绘制两个**不相交**的矩形（这里的相交指两个矩形交的面积大于零，即如果两个矩形仅共用一条边或一个点，则不视为相交）来增加面积。当然不绘制新矩形或仅绘制一个新矩形也是允许的。

inputFormat:
第一行两个整数 $N,K$（$1 \leq N,K \leq 10^5$）。

接下来 $N$ 行，每行四个整数 $x_1,y_1,x_2,y_2$（$0 \leq x_1,y_1,x_2,y_2 \leq 200$），描述一个矩形。其左下角坐标为 $(x_1,y_1)$，右上角坐标为 $x_2,y_2$。保证所有矩形面积为正，即其不会退化为线段或点。

和现有的矩形一样，新绘制的矩形，其左下角和右上角坐标也必须是整数，且坐标必须在 $0 \sim 200$ 之间，面积也必须为正。

outputFormat: 输出被涂油漆恰好 $K$ 次区域的最大面积。


title: 直接自然溢出啥事没有 加强版

background:
[原题链接](https://www.luogu.com.cn/problem/P6103)
本题与原题的区别，只有模数和数据范围不同。

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

description:
给定一个正整数 $n$，问有多少个长度为 $n$ 的字符串，满足这个字符串是一个「程序片段」。

具体定义如下：

单个分号 `;` 是一个「语句」。

空串 是一个「程序片段」。

如果字符串 `A` 是「程序片段」，字符串 `B` 是「语句」，则 `AB` 是「程序片段」。

如果字符串 `A` 是「程序片段」，则 `{A}` 是「语句块」。

如果字符串 `A` 是「语句块」，则 `A` 是「语句」，`[]A` 和 `[]()A` 都是「函数」。

如果字符串 `A` 是「函数」，则 `(A)` 是「函数」，`A` 和 `A()` 都是「值」。

如果字符串 `A` 是「值」，则 `(A)` 是「值」，`A;` 是「语句」。

**注意：`A` 是 `B` 并不代表 `B` 是 `A`。**

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

outputFormat: 输出一行一个整数表示答案，作为良心出题人，你只需要对 $998244353$ 取模。


title: [USACO18JAN] MooTube S

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

description:
在业余时间，Farmer John 创建了一个新的视频共享服务，他将其命名为 MooTube。在 MooTube 上，Farmer John 的奶牛可以录制，分享和发现许多有趣的视频。他的奶牛已经发布了 $N$ 个视频（$1 \leq N \leq 5000$），为了方便将其编号为  $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 5000$）。

接下来的 $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: 【模板】一般图最大匹配

background: 模板题，无背景。

description: 给出一张 $n$ 个点 $m$ 条边的无向图，求该图的最大匹配。

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

接下来 $m$ 行，每行两个正整数 $u$ 和 $v$，表示图中存在一条连接 $u$ 和 $v$ 的无向边。

outputFormat:
第一行一个整数，表示最大匹配数。

第二行 $n$ 个整数，第 $i$ 个数表示与结点 $i$ 匹配的结点编号，若该结点无匹配则输出 $0$。

如有多解输出任意解即可。

hint:
对于 $50\%$ 的数据，$n\le500$。

对于 $100\%$ 的数据，$2\le n\le10^3$，$1\le m\le5\times10^4$。

本题有 5 组 extra test。

####  提示
为了方便你调试你的程序，出题人在[这里](https://www.luogu.com.cn/paste/vf7dlo6r)为你提供了一个~~写的很丑的~~数据生成器。


title: [JOI 2019 Final] 珍しい都市

background:
JOI 2019 Final T5

由于数据点较多，本题只评测其中的部分数据。

description:
JOI 国有 $N$ 个城市，城市从 $1$ 到 $N$ 编号。这些城市被 $N-1$ 条双向道路连接，第 $i$ 条路连接两个城市 $A_i$ 和 $B_i$。从任何城市出发，可以到达所有城市。

JOI 国有些特产，每种特产的编号都在 $1$ 到 $M$ 之间（包括 $1$ 和 $M$），但是 $1$ 到 $M$ 的某些整数可能不代表 JOI 国的特产。JOI 国的每个城市都产一种特产。$j$ 城产的特产是 $C_j$。多个城市可能产相同的特产。

我们定义两个城市之间的距离为从一个城市到另一个城市需要经过的最少道路数，对于城市 $x$，我们定义城市 $y$（$y\neq x$）是**独特的城市**当且仅当对于任何一个城市 $z$（$z\neq x,z\neq y$），$x$ 与 $y$ 间的距离不等于 $x$ 与 $z$ 之间的距离。

JOI 国交通部部长 K 先生想知道对于城市 $j$ 的**独特的城市**一共能产多少种特产。

给出 JOI 国的道路信息与每个城市产的特产，写一个程序计算对于每个城市的**独特的城市**，一共能产多少种特产。

inputFormat:
第一行两个整数 $N,M$，意义如题目描述。

接下来 $N-1$ 行，每行两个整数 $A_i,B_i$，意义如题目描述。

最后一行 $N$ 个正整数，第 $i$ 个为 $C_i$，意义如题目描述。

outputFormat: 输出 $N$ 行，第 $i$ 行表示对于城市 $i$ 的独特的城市一共能产多少种特产。

hint:
样例解释 $1$：

对于城市 $1$，它的独特城市是城市 $2,3$，城市 $2$ 产特产 $2$，城市 $3$ 产特产 $3$，一共产两种特产，因此答案是 $2$；

对于城市 $2$，没有独特城市，因此输出 $0$；

对于城市 $3$，它的独特城市是城市 $1$，城市 $1$ 产特产 ，因此答案是 $1$；

对于城市 $4$，它的独特城市是城市 $1,3$，城市 $1,3$ 均产特产 $1$，因此答案是 $1$；

对于城市 $5$，它的独特城市是城市 $1,3$，城市 $1,3$ 均产特产 $1$，因此答案是 $1$。

注意：没有城市产特产 $3$。

对于 $4\%$ 的数据，$N\le 2000$。

另有 $32\%$ 的数据，$M=1$。

另有 $32\%$ 的数据，$M=N,C_j=j(1\le j \le N)$。

对于 $100\%$ 的数据，$1\le N \le 2\times 10^5,1\le M,A_i,B_i \le N,A_i \neq B_i,1\le C_j \le M$。


title: [JOI 2019 Final] コイン集め

background:
JOI 2019 Final T4

由于数据点较多，本题只评测其中的部分数据。

description:
JOI 先生的收藏室里有一张巨大的桌子，上面有许多稀有的硬币。为了清理桌子，他要重新摆放硬币。

桌面可视为 $(2\times 10^9+1)\times (2\times 10^9+1)$ 的网格。JOI 先生有 $2N$ 枚硬币。初始时，第 $i$ 枚 $(1\le i\le 2N)$ 硬币被放在坐标为 $(X_i,Y_i)$ 的格子里。JOI 先生的目标是在每个满足 $1\le x \le N,1\le y\le 2$ 的格子 $(x,y)$ 上恰好放一枚硬币。为了不损坏硬币，他能做的唯一一个操作是钦定一枚硬币然后将其移动到相邻的一个格子中（我们说两个格子相邻，当且仅当这两个格子有公共边）。在移动硬币的过程中，允许两个硬币处在同一个格子中。JOI 先生希望通过尽量少的操作次数完成目标。

现在给出硬币的数量和初始时所在的位置，编写一个程序，计算完成 JOI 先生目标所需的最少操作次数。

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

接下来 $2N$ 行，第 $i$ 行为两个整数 $X_i$ 和 $Y_i$。

outputFormat: 输出一行一个整数，表示完成目标所需的最少操作次数。

hint:
样例解释 $1$:

一种合法的移动方案是：

第一枚硬币：$(0,0)\rightarrow(1,0)\rightarrow(1,1)\rightarrow(1,2)$

第二枚硬币：$(0,4)\rightarrow(1,4)\rightarrow(1,3)\rightarrow(2,3)\rightarrow(3,3)\rightarrow(3,2)$

第三枚硬币：$(4,0)\rightarrow(4,1)\rightarrow(3,1)$

第四枚硬币：不动

第五枚硬币：$(2,5)\rightarrow(2,4)\rightarrow(2,3)\rightarrow(2,2)$

第六枚硬币：$(-1,1)\rightarrow(0,1)\rightarrow(1,1)$

可以证明 JOI 先生不能用少于 $15$ 次移动完成目标。

对于 $8\%$ 的数据，$N\le 10$。

对于 $37\%$ 的数据，$N\le 1000$。

对于 $100\%$ 的数据，$N\le 10^5,-10^9\le X_i,Y_i\le 10^9$。


title: [JOI 2019 Final] たのしいたのしいたのしい家庭菜園

background:
JOI 2019 Final T3

由于数据点较多，本题只评测其中的部分数据。

description:
家庭菜园专家 JOI 先生在他的家庭菜园中种植了一种叫 Joy 草的植物。在他的菜园里，有 $N$ 个花盆自东向西摆放，第 $i$ 个编号为 $i$。每个花盆中有一株 Joy 草。

春天到了，JOI 先生注意到 Joy 草如他期望地长出了各种颜色的叶子，但他也发现 Joy 草的生长速度没有他期望的那么快。他查阅了书籍，找到了草的以下特点：

 - Joy 草有三种品种，分别会长出红色、绿色和黄色的叶子。

 - 如果两株同一颜色的 Joy 草紧密相邻，它们的生长速度就会减慢。

因此，JOI 先生决定重新摆放花盆，使得没有两株相邻的 Joy 草颜色相同。

花盆非常沉重，因此 JOI 先生每次只能交换相邻的两个花盆。形式化的说，JOI 先生每次操作可以选择一个 $i$，然后交换花盆 $i$ 和花盆 $i+1$。

请编写一个程序，计算最少的交换次数。

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

接下来一行一个长度为 $N$ 的字符串 ，每个字符为 `R`,`G`,`Y` 中的一个，表示 Joy 草的颜色。

outputFormat: 输出一行一个整数，表示完成目标所需的最少操作次数。如果无解，输出 $-1$。

hint:
样例解释 $1$:

一种合法的方案是：

第一步：交换第三个花盆和第四个花盆。

第二步：交换第二个花盆和第三个花盆。

可以证明，不存在次数更少的方案

样例解释 $2$：

可以证明，无论如何移动，均不可达到目标。

对于 $5\%$ 的数据，$N\le 15$。

对于 $60\%$ 的数据，$N\le 60$。

另有 $15\%$ 的数据，字符串仅包含 `R`,`G`。

对于 $100\%$ 的数据，$N\le 400$。


title: [USACO17FEB] Why Did the Cow Cross the Road II G

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

description:
Farmer John 饲养了 $N$ 种奶牛，编号从 $1$ 到 $N$。一些品种的奶牛和其他奶牛间相处良好，事实证明，如果两个品种的奶牛编号分别为 $a,b$，当 $|a-b| \leq 4$ 时，这两个品种的奶牛能友好相处，否则不能友好相处。

一条长长的道路贯穿整个农场，道路的左侧有 $N$ 个牧场（每个品种的奶牛恰好占据一个牧场），道路的右侧也有 $N$ 个牧场（每个品种的奶牛恰好占据一个牧场）。为了让奶牛们安全穿过马路，Farmer John 希望能在马路上画出一些人行道（牛行道？），要求这些人行道满足如下条件：

1. 人行道从左侧的某个牧场出发，连接到右侧的某个牧场；
2. 人行道连接的两个牧场的奶牛要能友好相处；
3. 人行道不能在道路中间相交；
4. 每个牧场只能与一条人行道相连。

你需要帮 FJ 求出最多能有多少条人行道。

inputFormat:
输入第一行一个整数 $N$（$1 \leq N \leq 1000$）。

接下来 $N$ 行，每行一个整数 $a_i$，代表道路左侧第 $i$ 个牧场的奶牛品种编号。

接下来 $N$ 行，每行一个整数 $b_i$，代表道路右侧第 $i$ 个牧场的奶牛品种编号。

outputFormat: 输出最多能画多少条人行道。


title: [USACO17JAN] Hoof, Paper, Scissor S

background: *本题与 [金组同名题目](/problem/P3609) 在题意上一致，唯一的差别在于对变手势次数的限制。*

description:
你可能玩过“石头，剪刀，布”，这个游戏在奶牛中同样流行，不过它的名字变成了“蹄子，剪刀，布”。

“蹄子，剪刀，布”和“石头，剪刀，布”的规则十分类似，两只奶牛数到三，然后出一个代表蹄子，剪刀或布的手势。蹄子胜过剪刀，剪刀胜过布，布胜过蹄子。特别地，如果两只奶牛的手势相同，则视为平局。

现在 FJ 和 Bassie 要进行 $N$ 轮对抗。Bassie 已经预测了 FJ 每一轮要出的手势。然而 Bassie 很懒，她最多只想变换一次手势。

现在请你帮 Bassie 求出她最多能赢多少轮。

inputFormat:
第一行输入一个整数 $N$（$1 \leq N \leq 10^5$）。

接下来 $N$ 行，每行一个字母，代表 FJ 这一轮出的手势。`H` 代表蹄子（Hoof），`S` 代表剪刀（Scissors），`P` 代表布（Paper）。

outputFormat: 输出一个整数，代表 Bassie 在最多变换一次手势的前提下最多赢多少轮。


title: 【模板】Lyndon 分解

description:
这是一道模板题。

读入一个由小写英文字母组成的字符串 $s$ ，请把这个字符串分成若干部分 $s=s_1s_2s_3\cdots s_m$，使得每个 $s_i$ 都是 [$\text{Lyndon Word}$](https://en.wikipedia.org/wiki/Lyndon_word)，且 $\forall 1\le i<m:s_i\ge s_{i+1}$。输出 $s_1$ 到 $s_m$ 这些串长度的右端点的位置。位置编号为 $1$ 到 $n$。

一个字符串 $s$ 是一个 $\text{Lyndon Word}$，当且仅当 $s$ 是其所有后缀中最小的字符串。

为了减小输出量，你只需要输出所有右端点的异或和。

inputFormat: 一行一个长度为 $n$ 的仅包含小写英文字母的字符串 $s$。

outputFormat: 一行一个整数，表示所有右端点的异或和。

hint:
第一组样例的答案为 `2 4 5`。

第二组样例的答案为 `1 2 4 6 9 13 18`。

- 对于 $20\%$ 的数据，保证 $1\le n\le 1000$；
- 对于 $100\%$ 的数据，保证 $1\le n\le 5\times 10^6+1$。


title: 修改

description:
给定一个长度为 $n$ 的整数序列 $a_i$，再给定一个长度为 $n$ 的整数序列 $b_i$。

你可以进行一些修改，每次你可以将一个 $a_i$ 增加 $1$，花费为 $b_i$，你需要使所有的 $a_i$ 不相等，且同时满足花费最少。

但 zbw 认为太过简单，于是他规定，你可以在修改前进行**无限**次如下操作：交换 $b_i,b_j(1 \leq i,j \leq n)$。

求最小的花费。

**由于答案可能很大，请输出答案对  $2^{64}$ 取模后的值。**

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

第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$。

第三行 $n$ 个整数，第 $i$ 个数表示 $b_i$。

outputFormat: 输出一行一个整数，表示答案对 $2^{64}$ 取模的值。


title: [USACO16OPEN] Landscaping P

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

description:
Farmer John 打算修建一座花园，他需要移动不少泥土。

花园由 $N$ 个花坛组成（$1 \leq N \leq 10^5$），其中花坛 $i$ 包含 $A_i$ 单位的泥土。FJ 希望花坛 $i$ 包含 $B_i$ 单位的泥土，保证 $0 \leq A_i,B_i \leq 10$。

为了达到这个目标，他可以做这几件事情：

- 购买一单位的泥土，放在指定的花坛中，费用为 $X$。
- 从任意一个花坛中移走一单位泥土，费用为 $Y$。
- 从花坛 $i$ 运送一单位泥土到花坛 $j$，费用为 $Z|i-j|$。

请你帮 FJ 计算移动泥土的最小开销。

inputFormat:
第一行四个整数 $N,X,Y,Z$（$0 \leq X,Y \leq 10^8$，$0 \leq Z \leq 1000$）。

接下来 $N$ 行，第 $i$ 行两个整数 $A_i,B_i$。

outputFormat: 输出移动泥土的最小开销。

hint:
按下面的方案，最小花费为 $210$，可以证明不存在开销更小的方案。

- 移除 $4$ 号花坛的一单位泥土，花费 $200$。
- 将 $4$ 号花坛的三单位泥土移到 $1$ 号花坛，花费 $3 \times 3=9$。
- 将 $3$ 号花坛的一单位泥土移到 $2$ 号花坛，花费 $1 \times 1=1$。


title: [USACO16OPEN] Closing the Farm G

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

description:
FJ 和他的奶牛们正在计划离开小镇做一次长的旅行，同时 FJ 想临时地关掉他的农场以节省一些金钱。

这个农场一共有被用 $M$ 条双向道路连接的 $N$ 个谷仓（$1 \leq N,M \leq 2 \times 10^5$）。为了关闭整个农场，FJ 计划每一次关闭掉一个谷仓。当一个谷仓被关闭了，所有的连接到这个谷仓的道路都会被关闭，而且再也不能够被使用。

FJ 现在正感兴趣于知道在每一个时间（这里的“时间”指在每一次关闭谷仓之前的时间）时他的农场是否是“全连通的”——也就是说从任意的一个开着的谷仓开始，能够到达另外的一个谷仓。注意自从某一个时间之后，可能整个农场都开始不会是“全连通的”。

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

接下来 $M$ 行，每行两个整数 $u,v$（$1 \leq u,v \leq N$），描述一条连接 $u,v$ 两个农场的路。

最后 $N$ 行每行一个整数，表示第 $i$ 个被关闭的农场编号。

outputFormat:
输出 $N$ 行，每行包含 `YES` 或 `NO`，表示某个时刻农场是否是全连通的。

第一行输出最初的状态，第 $i$ 行（$2 \leq i \leq N$）输出第 $i-1$ 个农场被关闭后的状态。


title: [NEERC2016] Mole Tunnels

description:
鼹鼠们在底下开凿了 $n$ 个洞，由 $n-1$ 条隧道连接，对于任意的 $i>1$，第 $i$ 个洞都会和第 $\frac{i}{2}$（取下整）个洞间有一条隧道，第 $i$ 个洞内还有 $c_i$ 个食物能供最多 $c_i$ 只鼹鼠吃。一共有 $m$ 只鼹鼠，第 $i$ 只鼹鼠住在第 $p_i$ 个洞内。

一天早晨，前 $k$ 只鼹鼠醒来了，而后 $m-k$ 只鼹鼠均在睡觉，前 $k$ 只鼹鼠就开始觅食，最终他们都会到达某一个洞，使得所有洞的 $c_i$ 均大于等于该洞内醒着的鼹鼠个数，而且要求鼹鼠行动路径总长度最小。现对于所有的 $1 \le k \le m$，输出最小的鼹鼠行动路径的总长度，保证一定存在某种合法方案。

inputFormat:
第一行两个数 $n,m$，表示有 $n$ 个洞，$m$ 只鼹鼠。
第二行 $n$ 个整数 $c_i$ 表示第 $i$个洞的食物数。
第三行 $m$ 个整数 $p_i$ 表示第 $i$只鼹鼠所在洞 $p_i$。

outputFormat: 输出一行 $m$ 个整数，第 $i$ 个整数表示当 $k=i$ 时最小的鼹鼠行动路径总长度。

hint: $1 \le n,m \le 10^5$，$0 \le c_i \le m$，$1 \le p_i \le n$。


title: [NEERC2016] Hard Refactoring

description:
对于一个变量 $x$，给出一些约束条件，形如 $x \geq a$，$x \le a$
这些约束条件之间用```||```连接，然后你需要将这些约束条件简化，最后输出简化后的约束条件。

inputFormat:
输入不超过 $10^3$ 行，每行要么是两个用 ```&&``` 连接的约束条件，要么就是单个的约束条件。

如果一行有两个约束条件，第一个约束条件总是 $x \geq a$ 的形式，第二个约束总是 $x \leq a$ 的形式。

除了输入的最后一行，每一行末尾都有一个 ```||```。

并且所有的字符（除了`>=`，`<=`，`&&`，`||`）之间均由空格隔开，且没有多余的前置、后置空格。

outputFormat:
输出若干行，表示最简的约束条件的形式（也就是使输出的行数尽量少），其余格式与输入格式保持一致。

输出的若干行可以不按照特定的顺序输出。

特别地，如果对于任意的 $x∈[-32768,32767]$，$x$均能满足约束条件，仅输出一行```true```，反之，若对于任意的 $x∈[-32768,32767]$，$x$均不能满足约束条件，仅输出一行```false```。


title: [NEERC2015] Binary vs Decimal

description:
一个正数 $A$，如果它只包含 `0` 或 `1`，且它转成二进制后的 $B$，$A$ 是 $B$ 的后缀，这个数就是我们所要的。

现在给出数字 $N$，求第 $N$ 个这样的数。

inputFormat: 一行一个数 $N$。

outputFormat: 一行一个数，第 $N$ 个数。


title: 【模板】整式递推

background:
话说上次菜菜的 NaCly\_Fish 想教后辈做常系数线性齐次递推，奈何智商不够，见识短浅，被机房同学轮番吊打。

之后她又听说了整式递推这种东西，便去请教中国队长 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$。然而 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 觉得这个东西太简单了，只回应了一句：“你不看候选队论文么？”

NaCly\_Fish 终于找来论文，但她完全看不懂。于是她只能找又强又热心的你来教她这个问题。

description:
对于无限数列 $a$，已知 $\forall n \ge m$ 都满足
$$\sum_{k=0}^m a_{n-k} P_k(n) = 0$$
其中 $P_k$ 为不超过 $d$ 次的多项式。
给定所有 $P_k$ 的系数，和 $\{ a_i \}_{i=0}^{m-1} $，求 $a_n$。

由于答案可能很大，所以要对 $998244353$ 取模。

inputFormat:
第一行三个正整数 $n,m,d$。
第二行 $m$ 个非负整数，表示 $\{ a_i \}_{i=0}^{m-1} $。
接下来 $m+1$ 行，每行 $d+1$ 个非负整数；第 $k+3$ 行由低到高地给出 $P_k$ 的系数。

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

hint:
【样例一解释】
这里的递推式就是 $a_n \equiv (n-1)(a_{n-1}+a_{n-2}) \pmod{998244353}$，容易计算得 $a_5 \equiv 44 \pmod{998244353}$。

【数据范围】
对于 $30\%$ 的数据，$1\le n \le 10^6$。
对于 $100\%$ 的数据，$1\le m,d \le 7$，$1 \le n \le 6 \times 10^8$。

所有输入不超过 $6 \times 10^8$。
$\forall x \in [m,n] \cap \mathbb Z \text{ s.t. } P_0(x) \not \equiv 0 \pmod{998244353}$。

欢迎加入 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 粉丝群：747262201


title: [JSOI2009] 有趣的游戏

description:
小阳阳发明了一个有趣的游戏：有 $n$ 个玩家，每个玩家都有一个长度为 $l$ 的字母序列，任何两个玩家的字母序列不同。共有 $m$ 种不同的字母，所有的字母序列都由这 $m$ 种字母构成。为了方便，我们取大写字母的前 $m$ 个字母。
例如 $m=3,l=4,\texttt{ABAA}$ 和 $\texttt{CBCA}$ 是两个合法的字母序列。
现在由小阳阳来操控一台神奇的机器，每个时刻机器会随机产生一个字母，其中第 $i$ 种字母随机出来的概率为 $\dfrac{p_i}{q_i}$ ，显然 $\sum \limits_{k=1}^m \dfrac{p_i}{q_i}=1$。
这样 $T$ 个时刻后机器会产生一个长度为 $T$ 的字母序列。
如果某个时刻某个玩家发现自己的字母序列在机器产生的字母序列中出现了，“出现”的定义是玩家的字母序列是机器产生的字母序列中连续的一段，那么我们称这个玩家获胜，游戏结束。
现在小阳阳感兴趣的一个问题是，每个玩家分别有多大的概率能获得这场游戏的胜利呢？

inputFormat:
第一行有三个正整数 $n,l,m$ 表示有 $n$ 个人，每个字母的序列长度均为 $l$，共有 $m$ 个字母。
接下来 $m$ 行，每行有两个非负整数 $p, q$，表示随机到第 $i$ 个字母的概率为 $\frac{p}{q}$。
接下来 $n$ 行，每行有一个长度为 $l$ 的字母序列，表示第 $i$ 个人的字母序列。

outputFormat: 包含 $n$ 行，每行一个实数，表示第 $i$ 个人获胜的概率，输出结果四舍五入到两位小数。

hint: $1 \leq n,l,m \leq 10$，$0 \leq p_i \leq q_i \leq 10$ 且 $\gcd(p,q) = 1$。


title: [EER1] 礼物

background:
### Update：

时限扩大到 3 秒。

description:
小 Z 送了你一个数列，具体的，有 $a_1=1$，$a_2=2$，$a_i=2a_{i-1}+ka_{i-2}(3\le i\le n)$，其中 $n$ 是数列的长度，$k$ 是她设定的一个正整数参数。

小 Z 告诉你一个秘密，这个数列是她精心挑选的，有着一种奇妙的性质 "Prime-smooth"—— 即对于 $n$ 以内的任何一个**质数** $p$，满足 $p\mid a_p$（$\mid$ 是整除记号）。

你很好奇是不是真的有这回事，于是你写了一个质数发生器，进行了长达三天三夜的尝试，终于发现了几个反例：有 $m$ 个质数 $p_i$ 竟然不满足小 Z 所说的性质！

由于你已经随机了很久，你相信别的质数 **一定满足** 性质。

为了表明你和小 Z 心有灵犀，你现在想猜出小 Z 当时设定的参数 $k$，由于答案很大，你只需要求出最小的 $k$ 对一个质数 $c$ 取模即可。

inputFormat:
第一行三个非负整数 $n,m,c$，它们与题面中含义相同。

接下来 $m$ 行，每行一个正整数 $i$，表示对于从小到大数第 $i$ 个质数 $p_i$，不满足 $p_i\mid a_{p_i}$。我们保证这个质数 $p_i\le n$。注意：**不保证**这 $m$ 个数两两不同。

outputFormat:
一行一个整数，为最小的 $k$ 对 $c$ 取模后的值。

特别的，如果出现无解的情况，输出 $-1$。


title: [JSOI2012] 始祖鸟

description:
最近，进香河地带出现了一家“始祖鸟专卖店”，然而这并不只是一时的心血来潮。

早在远古时期，进香河地带就以其秀美的环境和适宜的温度吸引了成群的始祖鸟。始祖鸟是一种团结的鸟类，它们总是通过各种方式来增强种群内部的交流，聚会则是其中之一。因为聚会不但可以增强朋友之间的友谊，而且可以认识新的朋友。

现在有 $N$ 只始祖鸟，我们从 $1$ 开始编号。对于第 $i$ 只始祖鸟，有 $M_i$ 个认识的朋友，它们的编号分别是 $F_{i,1}，F_{i,2}，…，F_{i,M_i}$。朋友的认识关系是单向的，也就是说如果第$s$只始祖鸟认识第 $t$ 只始祖鸟，那么第 $t$ 只始祖鸟不一定认识第 $s$ 只始祖鸟。

聚会的地点分为两处，一处在上游，一处在下游。对于每一处聚会场所，都必须满足对于在这个聚会场所中的始祖鸟，有恰好有偶数个自己认识的朋友与之在同一个聚会场所中。当然，每一只始祖鸟都必须在两处聚会场所之一。

现在需要你给出一种安排方式。你只需要给出在上游的始祖鸟编号，如果有多组解，请输出任何一组解。

inputFormat:
输入数据包含 $N+1$ 行，第一行是数字 $N$，代表始祖鸟的个数。
接下来 $N$ 行，第 $i+1$ 行的第一个数字是 $M_i$，表示第 $i$ 只鸟的朋友个数。之后有 $M_i$ 个数字依次为 $F_{i,1},F_{i,2},…,F_{i,M_i}$ 表示第$i$只始祖鸟朋友的标号。

outputFormat: 输出数据包含 $2$ 行，第一行有一个非负整数 $k$，表示在上游参加聚会的始祖鸟个数。第二行有 $k$ 个正整数，表示在这个 $k$ 只始祖鸟的编号，你可以以任意顺序输出这些编号。如果无法满足要求，只输出一行`Impossible`。


title: [JSOI2012] 幼儿园的游戏

description:
公元 $1770$ 年，纪昀先生途经进香河，与百姓谈说人世，谈说友善。他所告诉人们的为友之道，流传至今，深深影响着当地的人们，甚至是幼儿园的孩童。
一天，多诺达新幼儿园的孩子们与老师们排排坐，形成了一个 $n \times m$ 的矩形队列，一共有 $k$ 个老师，他们融入在了这个矩形队列之中，与小朋友们欢乐地唱着歌。“手拉手，我们永远都是好朋友！”于是老师要求每一位小朋友都和四周(即上下左右四个方向)的任意两个小朋友牵手。
作为幼儿园里最聪明的小朋友，你马上意识到这并不是单纯的游戏，而是一个非常有意义的问题。你非常希望知道一共有多少种不同的牵手方案，满足每一位小朋友都可以和四周恰好两位小朋友牵手。当然，每一位小朋友都只能和小朋友牵手，不能去和老师牵手。任何一位小朋友都不允许自己和自己牵手(即左手拉右手)。
你所需要知道的只是方案个数，因为答案可能太大，所以需要对 $1000000007$ 取模。

inputFormat:
第一行有三个整数，分别是 $n$,$m$ 和 $k$。如题。
接下来 $k$ 行，每一行有 $2$ 个整数 $x$ 和 $y$，描述了一位老师的位置。

outputFormat: 你只需要输出一个整数，表示答案关于 $10^9+7$ 取模后的结果。


title: [JSOI2012] 铁拳

background:
经过了可怕的第三次世界大战后，国家政府崩溃，各大财团趁机夺取掌控世界。长年战争后，八大财团幸存并割据一方，其中最强的当属掌控北美的铁拳。
在铁拳财团所维护的文明区域中，有一项最为光荣、重要的赛事——`Iron Fist`，也就是铁拳大赛。$IF$中云集了世界各地各财团鼎力资助的世外高手，只为了赢得`IF Champion`，得到无上的荣耀，当然还有随之而来的权力。本来一切秩序井然，但一个来自贫民窟的少年风间仁意外地在海选中赢了 $IF$ 正式选手，获得了决赛资格，从此格局被打乱……
为了应对这突如其来的变数， $IF$ 管理层决定先对联盟中所有的选手进行评估，以更好地掌握大局。

description:
已知最近 $m$ 届比赛出现过的 $n$ 位选手，背后都有着各自财团的资助，并且签下了合同。由于这是各财团的高度机密，合同的具体细节无从得知，但铁拳财团的间谍们通过各种渠道得知了每个选手的薪金范围（显然薪金是非负数）。
对于最近 $m$ 届的 $IF$ 比赛（从 $1$ 开始编号），每一届联盟都会进行清算，通过国际金融手段准确计算出这一届联盟选手身价总和的变化。每一届中，会有一些新选手加入，也会有部分选手在比赛中丧失了战斗能力，而被踢出联盟，流放到贫民窟。
现在给出联盟中 $n$ 位选手的身价范围，以及他们 进入联盟的届数（ $0$ 表示在 $m+1$ 届以前就已经是联盟选手） 和 离开联盟的届数（ $0$ 表示是现役选手）。同时给出最近 $m$ 届中，每一届联盟选手身价总和减去上一届的值。
请你根据现有信息，尽可能准确地给出每个选手可能的薪金范围。各选手之间的薪金范围可以不同时成立，但对于一位选手的范围中的每一个数，都必须至少存在一种合法方案使该选手能得到相应薪金，而且这个范围跨度要尽可能大。
如果输入信息有误，请输出`-1`，表示无解。

inputFormat:
第一行一个正整数 $m$，意义同上。
第二行包含 $m$ 个整数，第 $i$ 个表示第 $i$ 届中 选手身价总和 的变化情况。
第三行一个正整数 $n$。
接下来 $n$ 行，每行包含四个整数，分别表示 身价下限 、 身价上限 、 出道届数 、 退役届数，细节请参照上文。
保证出道时间严格比退役时间小（ $0$ 除外）。

outputFormat:
如果输入信息有误，仅输出一行一个整数`-1`。
否则输出 $n$行，每行两个实数，第 $i$ 行表示第 $i$ 个选手实际身价的准确范围，并保留两位小数。

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

第二届只有 $3$ 号离开了，可以锁定 $3$ 号的薪金是 $1$。

如此一来， $1$ 号和 $2$ 号薪金之和为 $4$，那么 $1$ 号最少能拿 $1$，最多能拿 $2$；$2$ 号最少能拿到 $2$，最多能拿到 $3$。

#### 数据范围

对于 $100\%$的数据，$1 \le n \le 200,1 \le m \le 100$，给定薪金范围不超过 $20000$。


title: [SBCOI2020] 归家之路

background:
时光流逝，岁月无痕。
小镇的夜空中，缀满了无数宝石一般的闪烁星辰。
依旧是那片星空，依旧是那个小镇。
......
“好久不见啊。”
“不知不觉，竟然已经过去了那么久了...”
“但是，这座小镇还是曾经的那个小镇啊。”
“只不过，我们都不再是过去的自己了呢。”
“你还记得吗，我们曾经一起在这里看雪，一起玩游戏...”
“可是游戏结局明明一开始就已经决定了...真是太坏了...”
“嘿嘿，说起来你还从来没赢我过呢......”
“我还记得，你以前说过，每当世界上有一份思念，便会化成一片雪花在这里飘落...”
“嗯，我只要看着冬天的雪便能想起你了。我知道，这一定是你的思念吧...”
“我也看到了，如同雪花般飘落的记忆......”

天空中，点点滴滴的光芒融合在一起，清澈而宁静。眼前的风景是那么熟悉又陌生。
![](https://cdn.luogu.com.cn/upload/image_hosting/ic5htl18.png)

“我们再待一会儿如何，就像以前一样......”
“和你，和小镇，和星空......”

description:
天空中一共有 $2^n$ 颗星，依次编号为 $0,1,...,2^n-1$。每颗星都有一个亮度值。初始时第 $i$ 颗星的亮度值为 $a_i$。

对于两个正整数 $a,b$ 我们定义一种布尔类型运算 $a\otimes b$ 。如果在 $a$ 的**二进制**表示中，满足每一个 $a$ 是 $1$ 的位，$b$ 的对应位也是 $1$，那么  $a\otimes b$ 为 `True` , 否则 $a\otimes b$ 为 `False`。
若两数在二进制表示下的位数不同，则将两数 **右对齐** 后在左侧补0。例如两个数是 $1$ 和 $11$ （二进制），$1$ 会变成 $01$。

对于这些星的亮度值有两种操作：

第一种：$1$ $a$ $b$ $k$。对于所有的满足 $a\otimes c$ 值为 `True` 以及 $c\otimes b$ 值为 `True` 的 $c$，将第 $c$ 颗星的亮度值加上 $k$。

第二种：$2$ $a$ $b$。若第 $c$ 颗星的编号 $c$ 满足 $a\otimes c$ 值为 `True` 以及 $c\otimes b$ 值为 `True`。求出所有第 $c$ 颗星的亮度总和，答案对 $2^{32}$ 取模。

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

第二行 $2^n$ 个整数，用空格隔开，表示 $a_0,a_1,\cdots,a_{2^n-1}$。

接下来 $q$ 行，每行代表一个操作，格式见【题目描述】。

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

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

第一次是询问，$0$ 的二进制表示为 $000$， $7$ 的二进制表示为 $111$ 。此时，所有数都满足，即求的是所有数之和，为 $36$。

第二次是修改，$1$ 的二进制表示为 $001$，$5$ 的二进制表示为 $101$，发现 $c=1,5$ 满足，二进制表示分别为 $001$，$101$所以 $a_1,a_5$ 的值从 $2,6$ 变为 $3,7$。

第三次是询问，$1$ 的二进制表示为 $001$，$7$ 的二进制表示为 $111$，发现 $c=1,3,5,7$ 满足，二进制表示分别为 $001$，$011$，$101$，$111$。求的是 $a_1,a_3,a_5,a_7$ 的和 $3+4+7+8=22$。

**【数据范围】**

**本题捆绑测试，共有 $4$ 个子任务**。

$Subtask 1(1\%)$：答案为样例。

$Subtask 2(9\%)$：$n \le 12,m \le 2\times 10^3$。

$Subtask 3(15\%)$：所有 $2$ 操作都在 $1$ 操作之后。

$Subtask 4(75\%)$：没有任何额外限制。

对于 $100\%$ 的数据，$1 \le n \le 16,1 \le m \le 2\times 10^5, 0 \le a,b \le 2^n-1,0 \le a_i,k \le 2^{32}-1$。

**【温馨提示】**

对 $2^{32}$ 取模，可以直接用无符号 `32` 位整形的数据类型进行运算。在 `c++` 中就是 `unsigned int`。

~~也就是【直接自然溢出啥事没有】。~~


title: 『MdOI R2』Mayuri

background:
「万由里……怎么会？为什么你要……」

『我是灵力的结晶体，实施了封印，我当然会消失，不是吗？』

「封印？但是你和我……」

『第一次见面不能封印吗？笨蛋，我可是从大家的灵力里出生的，怎么可能讨厌你？从一出生，我就爱着你。』

「万由里……」

『虽然我竭力不让自己去想，但我一定是很羡慕大家……』

「等一下，万由里，不要消失……」

『但是我还是有一件能向大家炫耀的事，只有我和士道一样……』

「一样？」

『我已经不再是只为了消失而出生的生命。因为我遇见了你……已经足够了。』

「万由里……」

『谢谢你，士道。 』

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

description:
在离开这个世界前，万由里想要寻找属于她的 Lucky Number。

万由里会给出一个数 $a$，以及一个长度为 $b$ 的 01 串 $S$。

简单的说，她的 Lucky Number 是满足以下条件的**正整数** $n$：

 - $n$ 的位数为 $b$ 且不含前导 $0$。

 - 若 $S$ 的第 $i$ 位为 $1$，则 $n$ 的前 $i$ 位组成的数是 $a$ 的倍数，否则 $n$ 的前 $i$ 位组成的数不是 $a$ 的倍数。

对于一个数，前 $i$ 位组成的数是指这个数前 $i$ 个数码依次拼接形成的数。例如 $312311$ 前 $3$ 位组成的数为 $312$，前 $5$ 位组成的数为 $31231$。

现在，请你帮助万由里计算一下，她的 Lucky Number 是多少。

由于满足条件的数可能会有多个，你需要输出**最小**的一个。若不存在，则请输出 `-1`。

inputFormat:
输入数据由两行构成。

第一行两个整数 $a,b$，意义见题目描述。

第二行一个长度为 $b$ 的字符串 $S$。

outputFormat: 一行，满足条件的**最小**的数 $n$。如果不存在满足条件的数，输出 `-1`。

hint:
【帮助与提示】

为方便选手测试代码，本题额外提供一组附加样例供选手使用。

[样例输入](https://www.luogu.com.cn/paste/5gnn8mg0) [样例输出](https://www.luogu.com.cn/paste/sgxjkbjd)

------
【样例解释】

对于样例一，$10$ 是 $2$ 位数，且 $10$ 的前 $1$ 位组成的数 $1$ 不是 $2$ 的倍数，而前 $2$ 位组成的数 $10$ 是 $2$ 的倍数。由于 $10$ 已经是最小的两位数，故不存在比 $10$ 更小的满足条件的数。

对于样例二，我们需要构造一个 $1$ 位数，满足这个 $1$ 位数整除 $10$。显然，这样的数不存在。

---

【数据范围】

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

| 子任务编号 | $a \leq$ | $b\le$  | 分值   |
| ---------- | -------- | :------ | ------ |
| Subtask 1  | $10$     | $ 1$    | $20$   |
| Subtask 2  | $10 $    | $2$     | $20$  |
| Subtask 3  | $10 $    | $ 6$    | $20$  |
| Subtask 4  | $ 2$     | $ 18$   | $20$ |
| Subtask 5  | $ 10$    | $ 10^5$ | $20$ |

对于全部数据，保证 $2\le a\le 10$，$1\le b\le 10^5$，$S$ 中只包含 `0` 和 `1`。


title: 『MdOI R2』Resurrection

background: 如果你不清楚本题的某些定义，可以阅读【说明/提示】部分。

description:
有一棵包含 $n$ 个节点的树 $T$，它的所有边依次编号为 $1$ 至 $n-1$。

保证对于 $T$ 中任意一个节点 $u$ ，从 $u$ 到 $n$ 号节点的简单路径都不经过任何编号小于 $u$ 的节点。

按照如下步骤生成一张包含 $n$ 个节点的无向图 $G$：

选取一个 $1 \sim n-1$ 的排列 $p$，然后依次进行 $n-1$ 次操作。在进行第 $i$ 次操作时，首先删除树 $T$ 中编号为 $p_i$ 的边 $(a,b)$，然后，记 $u$ 和 $v$ 分别为当前树 $T$ 中与 $a,b$ 联通的所有点中，编号最大的点，并在图 $G$ 的 $u$ 号点和 $v$ 号点之间连一条边。

求对于给定的树 $T$，按上述方式一共可以生成多少种本质不同的图 $G$。图 $G_1$ 和 $G_2$ 本质不同当且仅当存在 $u$ 和 $v$ 满足在 $G_1$ 中不存在边 $(u,v)$，而 $G_2$ 中存在。

因为答案可能很大，你只需要求出答案对 $998244353$ 取模的值。

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

接下来 $n-1$ 行，第 $i$ 行两个整数 $u,v$，表示在 $T$ 中编号为 $i$ 的边是 $(u,v)$。

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

hint:
【帮助与提示】

为方便选手测试代码，本题额外提供一组附加样例供选手使用。

[样例输入](https://www.luogu.com.cn/paste/09anxo5k) [样例输出](https://www.luogu.com.cn/paste/3idipkty)

---

【样例解释】

样例一中可能生成的图 $G$ 如图所示：

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

当 $p = \{1,2,3\},\{2,1,3\},\{2,3,1\}$ 时将生成右侧的图，否则将生成左侧的图。

对于样例二，我有一个绝妙的解释，只可惜这里空白的位置太小，写不下。

---

【数据范围】

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

对于全部数据，保证 $1 \leq n \leq 3 \times 10^3$，$1 \leq u,v \leq n$。

保证，输入的边形成一棵树，且对于任意一个节点 $u$ ，从 $u$ 到 $n$ 号节点的简单路径都不经过任何编号小于 $u$ 的节点。

| 子任务编号 | $n\leq$ |         特殊性质          | 分值 |
| :--------: | :-----: | :-----------------------: | :--: |
| Subtask 1  |   $5$   |            无             | $32$ |
| Subtask 2  |  $14$   |            无             | $16$ |
| Subtask 3  | $10^3$  | 所有节点都与 $n$ 号点直接相连 | $1$  |
| Subtask 4  | $10^3$  |     树的形态是一条链      | $7$  |
| Subtask 5  |  $50$   |            无             | $22$ |
| Subtask 6  | $3 \times 10^3$  |            无             | $22$ |

---

下面是本题用到的一些定义：

- 一棵树是一张有 $n$ 个节点，$n-1$ 条边的无向连通图。

- 边 $(u,v)$ 表示连接点 $u$ 和点 $v$ 的一条边。

- 一条路径是一个序列 $p_1,p_2 \ldots p_k$ ，满足对于任意 $1 \leq i < k$，边 $(p_i,p_{i+1})$ 都存在于 $T$ 中，且 **没有被之前的操作删除**。

- 点 $u$ 和 $v$ 联通当且仅当存在一条路径 $p_1,p_2 \ldots p_k$ 满足 $p_1=u$ 且 $p_k=v$。任何一个点都和自己联通。


title: 『MdOI R2』Quo Vadis

background:
「终于……终于要到离别的时候了呢。」

『好吧。这一次过去之后，我们可能就再也不能相会了呢……』

「无论如何，还是要离别的……」

『我理解你。感谢你这些天陪伴在我身旁。』

「我也一样。如果可以的话，我真希望能继续陪伴在你身边。」

『分别之后，我也不是现在的我了……』

『至少不像现在这样。』

「离开你之后，我也不会像现在这样了……」

『君往何处？君欲往何处？君莫走，君莫走！若要走，请带上我！』

……

「所以……所以现在我们该怎么办？」

『就让我们纵然歌舞于其中吧！』

耳畔响起了小提琴和手风琴的声音，它是那么熟悉，而又那么陌生……

description:
在小 M 离别之前，他给小 K 留了一张纸条——

如果你能完成他的话，我将有可能会再次与你相遇。

给定一个**无限大**的矩阵 $A$，其中 $A_{i,j}=ij\gcd(i,j)$。

接下来有 $m$ 个操作，每行 $1$ 至 $3$ 个整数，意义如下：

$1$：对矩阵 $A$ 进行高斯消元，使之成为一个上三角矩阵。

**注意**：这里，高斯消元中只允许将一行的某一个倍数加到另一行上，不允许交换任意两行，不允许将某行乘上一个倍数，保证这样之后仍然可以得到上三角矩阵，并且保证消元之后的矩阵的每个元素均为非负整数。

$2\ x\ y$：求出当前矩阵的 $A_{x,y}$。

$3\ x$：求出 $\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{x}A_{i,j}$。

$4\ x$：设 $B$ 是一个 $x$ 阶矩阵，其中 $B_{i,j}=A_{i,j}$，你需要求出 $\det B$。

**上述所有答案对 $998244353$ 取模**。

如果你不知道什么是行列式，请点[这里](https://oi-wiki.org/math/gauss/#_12)，其中 $\text{det}$ 表示求矩阵的行列式。

~~在你完成了小 M 给小 K 的任务之后，你可以来看小提琴和手风琴的谱子。~~

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

接下来 $m$ 行，每行 $1\sim 3$ 个整数，表示操作。

outputFormat: 若干行，表示你的答案对 $998244353$ 取模后的值。


title: 『MdOI R2』Little Goth

background: 小 M 和小 B 是一对好朋友，她们很喜欢爬山。

description:
山可以抽象为一个长为 $n$ 的字符串 $S$，串中仅包含小写字母。

对于一个字符串 $S$，我们定义 $|S|$ 表示串的长度，$S_{L\ldots R}$ 表示由 $S$ 中从左往右数，第 $L$ 个字符到第 $R$ 个字符依次连接形成的字符串。

小 M 一开始的位置是 $i$，她想要到达位置在 $k$ 处的山顶，而小 B 则要帮助她。为此，她们需要进行一系列操作。

她们**必须**在所有操作之前使用**一次**位于 $p$ 处的传送法阵，通过施展法术，可以使小 B 的位置变为任意满足 $j \geq i$ 且 $S_{i \ldots j} = S_{p \ldots p + (j-i)}$ 的 $j$。但同时，她们需要付出 $n-j$ 的代价。保证这样的 $j$ 存在。

之后，假设小 M ，小 B 的位置分别为 $i$ 和 $j$，她们可以任意次进行下列操作中的一种：

- 让小 M 爬，即令 $i=i+1$ 或 $i = i-1$。如果这一步操作之后 $i>j$，则 令 $j=i$。

- 让小 B 爬，即令 $j=j+1$ 或 $j=j-1$。如果这一步操作之后 $i>j$，则令 $i=j$。

- 使用螺旋升天，具体而言，选择两个下标 $l$ 和 $r$，满足 $S_{l \ldots r} = S_{i \ldots j}$，然后令 $i=l,j=r$。

出于某些原因，任何一次操作结束后，需要保证 $1 \leq i , j \leq n$。进行一次上述任意一种操作，都需要付出 $1$ 的代价。

爬山是很累的，因此她们想知道，至少需要付出多少代价才能让小 M 到达山顶，也就是让 $i=k$。又因为她们很喜欢爬山，她们有很多组询问要问你。

inputFormat:
第一行两个整数，$n$ 和 $q$，表示串 $S$ 的长度和询问的个数。

第二行一个长度为 $n$ 的字符串 $S$，仅包含小写字母。

接下来 $q$ 行，每行三个整数 $i,p$ 和 $k$，表明小 M 的位置，传送法阵位置和山顶的位置。

outputFormat: 共 $q$ 行，第 $i$ 行一个整数，表示对于第 $i$ 个询问给定的 $i,p$ 和 $k$，至少需要付出多少代价，才能让小 M 到达山顶，也就是，让小 M 的位置 $i=k$。

hint:
【帮助与提示】

为方便选手测试代码，本题额外提供一组附加样例供选手使用。

[样例输入](https://www.luogu.com.cn/paste/j7u8z9ir) [样例输出](https://www.luogu.com.cn/paste/fh19p0a4)

--------
【样例解释】

对于样例的第一组询问，使用传送法术时，只能令 $j=5$，付出 $8-5=3$ 的代价。之后，首先使用一次第三种操作，选择 $l=2,r=2$，令 $i=l,j=r$，然后使用一次第一种操作，令 $i-1$，即可使 $i=k$，一共付出 $5$ 的代价。

对于第二组询问，可以选择 $j=2$，付出 $8-2=6$ 的代价，然后使用一次第三种操作，选取 $l=4,r=5$ 并使 $i=l,j=r$，然后进行一次第一种操作，令 $i+1$ 即可使 $i=k$。一共付出 $8$ 的代价。

---

【数据范围】

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

对于全部数据，保证 $1 \leq n,q \leq 3\times 10^4$，$S$ 中仅包含小写字母。

| 子任务编号 |      $n\leq$      |     $q \leq$      |      特殊性质       | 分值 | 时间限制 |
| :--------: | :---------------: | :---------------: | :-----------------: | :--: | :------: |
| Subtask 1  |       $15$        |       $15$        |         无          | $3$  |    1s    |
| Subtask 2  |       $80$        |       $80$        |         无          | $14$ |    1s    |
| Subtask 3  |  $2 \times 10^4$  |  $2 \times 10^4$  |   $S$ 中仅包含`a`   | $8$  |    3s    |
| Subtask 4  |  $2 \times 10^4$  |  $2 \times 10^4$  |        $S_1$        | $7$ |    3s    |
| Subtask 5  |       $400$       |       $400$       |         无          | $9$  |    1s    |
| Subtask 6  |  $2\times 10^4$   |  $2 \times 10^4$  | 所有询问的 $k$ 相同 | $10$ |    3s    |
| Subtask 7  |      $10^3$       |      $10^3$       |         无          | $10$ |    2s    |
| Subtask 8  | $1.5 \times 10^4$ | $1.5 \times 10^4$ |         无          | $11$ |    3s    |
| Subtask 9  |  $3 \times 10^4$  |  $3 \times 10^4$  |         无          | $28$ |    3s    |

性质 $S_1$ 是，对于给定的 $p$，满足条件的 $j$ 唯一。


title: [QkOI#R1] Quark and Tree

description:
给定一棵包含 $n$ 个节点的树，每个节点上有一个点权，点的编号为 $1\sim n$，请加一条不存在于给定的树中的边（且不能为自环），使加边后得到的基环树上所有点的深度与该点点权乘积之和最大。

我们认为基环树上的点的深度指该节点到环上的最短距离，特别地，环上的节点深度为 $0$。

形式化地，你需要添加一条不存在于给定的树中的边（且不能为自环），并最大化：

$$\sum_{i=1}^nw_i\times dep_i$$

其中 $w_i$ 为节点 $i$ 的权值，$dep_i$ 为节点 $i$ 在基环树中的深度。

inputFormat:
第一行包含一个整数 $n$，表示树中点的个数。

第二行包含 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的点权 $w_i$。

接下来 $n-1$ 行，一行两个整数 $a_i,b_i$，表示 $a_i$ 和 $b_i$ 在树中有一条边连接。

outputFormat: 输出包含一行一个整数，表示加边后生成的基环树中，各个节点的深度与其点权乘积之和的最大值。

hint:
### 样例解释

样例 1 给出的树如下图所示：

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

可以添加边 $(1,5)$，则新生成的基环树如下图所示：

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

各节点深度见下表：

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

### 数据范围

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

对于所有数据，$3 \le n \le 10^6$，$-10^3 \le w_i \le 10^3$，$1 \le a_i,b_i \le n$。

+ 子任务 $1$（$10$ 分）：$n \le 200$。
+ 子任务 $2$（$20$ 分）：$n \le 10^3$。
+ 子任务 $3$（$40$ 分）：$w_i \ge 0$。
+ 子任务 $4$（$30$ 分）：无特殊限制。


title: [USACO11NOV] Cow Beauty Pageant S

description:
听说最近流行表皮有三个斑点的奶牛，Farmer John 迅速购买了不少这样的奶牛。但流行趋势也在改变，最近改为流行只有一个斑点的奶牛了。

FJ 决定在他的奶牛上涂色，从而把三个斑点合并成一个。牛皮由一个 $N \times M$ 的矩阵来表示，像这样：

```plain
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....
```

每个 `X` 表示斑点的一部分。如果两个 `X` 在竖直或水平方向上相邻，则它们属于同一个斑点（对角线相邻不算）。因此上面表示的是一头具有三个斑点的奶牛。

FJ 可以通过将一些 `.` 涂成 `X` 来改变牛身上的图案。他希望使用尽可能少的涂料将三个斑点合并为一个斑点。对于上图，下面是一种消耗涂料最少的方案（只涂了 4 个格子，新涂的格将用 `*` 表示）：

```plain
................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
...*....XXXXX...
..XXX....XXX....
```

现在请你帮 FJ 算出将三个斑点合并为一个斑点最少需要涂多少格子。

inputFormat:
第一行两个整数 $N,M$（$1 \leq N,M \leq 50$）。

接下来 $N$ 行，每行 $M$ 个字符（`*` 或 `X`），描述牛表皮的斑点分布情况。保证这头牛恰好有三个斑点。

outputFormat: 输出将三个斑点合并为一个斑点最少需要涂多少格子。


title: [集训队互测 2019] 简单计数

background:
## 警告，滥用本题者将被封号。

$\mathsf C \color{red}\mathsf{auchySheep}$ 近期优化了他的 快速数论变换 (NTT) 模板的常数，现在他能在 $0.1\text s$ 内轻松跑过 $n=10^9$ 了，所以他准备用下面的这个简单计数题也考验一下你的常数优化水平。

description:
传说，在很久很久以前，有一张 $n$ 个点的带标号**有向无环**图。每条边有一个颜色，为 $k$ 种不同颜色中的一种。这张图满足如下性质：

- 每个点有不超过 $1$ 条出边
- 每个点的入边条数在集合 $S$ 中

由于某种原因，你想知道这样的图的个数。由于这样的图可能很多，你只要输出答案对 $998244353$ 取模的值。

两个图不同当且仅当存在一条从某个点 $a$ 到某个点 $b$ 的有向边，它只在恰好一个图中出现，或在两个图中都出现但颜色不同。

inputFormat:
第一行输入三个正整数 $n, k, |S|$。
第二行从小到大输入 $|S|$ 个不同的非负整数，表示 $S$ 集合中的元素。

outputFormat: 输出一行一个 $[0,998244352]$ 的整数，表示符合题意的图的个数对 $998244353$ 取模的值。


title: 蛋糕 Cake

background:
>   道不同不相为谋。

$\text{.cilohocohc}$ 喜欢吃蛋糕，尤其是巧克力蛋糕。

$\text{LeverImmy}$ 送了一个超级大的巧克力蛋糕给她做生日礼物，蛋糕上面点缀着许多巧克力布丁。

$\text{.cilohocohc}$ 一个人肯定是吃不完那么大一个蛋糕的，于是她要 $\text{LeverImmy}$ 帮她蛋糕切成两块，使得两块蛋糕上的布丁数之比为 $a : b$。

蛋糕可以抽象为一个二维平面；而做蛋糕的作坊很缺心眼，因此每个布丁都很小，可以看成二维平面上的一个 **整点**。

$\text{LeverImmy}$ 的刀技非常高超，所以他准备秀一下，他只会以一个 **斜率不小于 $1$ ，不大于 $10^{12}$ 的一次函数图像** 为轮廓在蛋糕上划一刀。

他想考考聪明的你，如果是你，你会怎么划？

description:
已知 $n$ 以及 $a, b$，求一个一次函数 $f(x) = k(x - x_0) + y_0 (1 \le k \le 10^{12})$，使得 $f(x)$ 将平面内的 $n$ 个点恰好分为个数之比 $a : b$ 的两部分。

如果你不知道一次函数为什么要这样表示，这里有 [点斜式](https://baike.baidu.com/item/%E7%82%B9%E6%96%9C%E5%BC%8F/921468?fr=aladdin) 的定义。

inputFormat:
第一行三个整数 $n, a, b$，表示点的个数以及你要分成两部分的比例。

接下来的 $n$ 行，第 $i$ 行两个整数 $x_i, y_i$ 表示平面上的点 $(x_i, y_i)$。

数据保证 **任意两个点不重合**。

outputFormat:
输出数据共一行三个整数，分别表示题目中的 $k, x_0, y_0$。

请务必保证 $1 \le k \le 10^{12}, -10^5 \le x_0, y_0 \le 10^{5}$。

如果有点 **恰好** 落在你给的直线上，我们视作其位于直线 **上方**。

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

$\text{Subtask 1 (10 pts)}:$ 保证 $n \in \{2, 3\}$；

$\text{Subtask 2 (30 pts)}:$ 保证 $\left|x_i\right|, \left|y_i\right| \le 10$；

$\text{Subtask 3 (60 pts)}:$ 保证 $2 \le n \le 10^5$，$0 \le \left|x_i\right|, \left|y_i\right| \le 10^5$。

对于所有数据，保证 $(a + b) | n$ 且 $ab \neq 0$。

---

#### Special Judge

**本题采用 $\text{Special Judge}$。**

spj 返回信息一览：

`Your answer is correct!`：你的结果是正确的；

`Your answer is wrong, expected ratio as a : b, found A : B.`：你的函数有问题，它把所有的点分割成了 $A : B$ 的两部分而不是 $a : b$ 的两部分；

`Oops, data out of range!`：你所给出的点的横纵坐标，或是斜率，在题目要求的范围外。

注意，你在 **赛时** 并不能看到 Special Judge 的返回结果。


title: [JSOI2015] 最小表示

background: 还记得去年 JYY 所研究的强连通分量的问题吗？去年的题目里，JYY 研究了对于有向图的“加边”问题。对于图论有着强烈兴趣的 JYY，今年又琢磨起了“删边”的问题。

description:
对于一个 $N$ 个点（每个点从 $1$ 到 $N$ 编号），$M$ 条边的有向图，JYY 发现，如果从图中删去一些边，那么原图的连通性会发生改变；而也有一些边，删去之后图的连通性并不会发生改变。

JYY 想知道，如果想要使得原图任意两点的连通性保持不变，我们最多能删掉多少条边呢？

为了简化一下大家的工作量，这次 JYY 保证他给定的有向图一定是一个有向无环图（JYY：大家经过去年的问题，都知道对于给任意有向图的问题，最后都能转化为有向无环图上的问题，所以今年 JYY 就干脆简化一下大家的工作）。

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

接下来 $M$ 行，每行包含两个 $1$ 到 $N$ 之间的正整数 $x_i$ 和 $y_i$，表示图中存在一条从 $x_i$ 到 $y_i$ 的有向边。

输入数据保证，任意两点间只会有至多一条边存在。

outputFormat: 输出一行包含一个整数，表示JYY最多可以删掉的边数。

hint:
### 样例解释

一种合法方案为删去 $1\rightarrow 5$ 和 $1\rightarrow 3$。容易证明没有比 $2$ 更优的答案。

### 数据范围

对于 $100\%$ 的数据，$1 \leq N\leq 3\times 10^4$，$0 \leq M\leq 10^5$。