title: [LNOI2022] 吃

description:
小 A 很喜欢吃东西。

小 A 面前有 $n$ 份食物，第 $i$ 份有参数 $a_i$ 和 $b_i$。小 A 可以按照**任意顺序**吃掉这 $n$ 份食物。当她吃掉编号为 $i$ 的食物时，她可以选择将自己的体重乘以 $a_i$ 或者将自己的体重加上 $b_i$。每份食物只能吃恰好一次。

小 A 的初始体重为 $1$，请求出她吃完 $n$ 份食物后能达到的**最大**体重。答案可能很大，你只需要输出其对 $({10}^9 + 7)$ 取模后的结果。

**注意：你需要最大化体重并将该最大值对 $\bm{({10}^9 + 7)}$ 取模，而非最大化体重对 $\bm{({10}^9 + 7)}$ 取模的结果。**

inputFormat: 第一行输入一个整数 $n$ 表示食物的数量。第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，第三行 $n$ 个整数 $b_1, b_2, \ldots, b_n$，表示每份食物的参数。

outputFormat: 输出一个整数，表示小 A 可以得到的最大体重对 $({10}^9 + 7)$ 取模后的结果。

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

以下方案可以达到最大体重：

- 吃掉第一份食物并选择将体重增加 $100$，体重变为 $101$；
- 吃掉第二份食物并选择将体重增加 $200$，体重变为 $301$；
- 吃掉第三份食物并选择将体重乘 $3$，体重变为 $903$；
- 吃掉第四份食物并选择将体重乘 $4$，体重变为 $3612$；
- 吃掉第五份食物并选择将体重乘 $5$，体重变为 $18060$。

**【样例 #2】**

见附件中的 `food/food2.in` 与 `food/food2.ans`。

该组样例满足 $n \le 10$ 和特殊性质 E。

**【样例 #3】**

见附件中的 `food/food3.in` 与 `food/food3.ans`。

该组样例满足 $n \le 20$ 和特殊性质 E。

**【样例 #4】**

见附件中的 `food/food4.in` 与 `food/food4.ans`。

该组样例满足 $n \le 2000$。

**【样例 #5】**

见附件中的 `food/food5.in` 与 `food/food5.ans`。

该组样例满足特殊性质 A。

**【样例 #6】**

见附件中的 `food/food6.in` 与 `food/food6.ans`。

该组样例满足特殊性质 C。

**【样例 #7】**

见附件中的 `food/food7.in` 与 `food/food7.ans`。

该组样例满足特殊性质 D。

**【样例 #8】**

见附件中的 `food/food8.in` 与 `food/food8.ans`。

该组样例满足特殊性质 B。

**【样例 #9】**

见附件中的 `food/food9.in` 与 `food/food9.ans`。

**【数据范围】**

对于 $100 \%$ 的测试数据，$1 \le n \le 5 \times {10}^5$，$1 \le a_i, b_i \le {10}^6$。

| 测试点编号 | $n \le $ | 特殊性质 |
|:-:|:-:|:-:|
| $1$ | $10$ | DE |
| $2$ | $10$ | E |
| $3$ | $10$ | AE |
| $4$ | $10$ | E |
| $5$ | $20$ | DE |
| $6$ | $20$ | E |
| $7$ | $20$ | E |
| $8$ | $20$ | E |
| $9$ | $2000$ | D |
| $10$ | $2000$ | 无 |
| $11$ | $2000$ | 无 |
| $12$ | $2000$ | 无 |
| $13$ | $5 \times {10}^5$ | BD |
| $14$ | $5 \times {10}^5$ | B |
| $15$ | $5 \times {10}^5$ | C |
| $16$ | $5 \times {10}^5$ | C |
| $17$ | ${10}^5$ | 无 |
| $18$ | ${10}^5$ | 无 |
| $19$ | $5 \times {10}^5$ | 无 |
| $20$ | $5 \times {10}^5$ | 无 |

特殊性质 A：$a_i = 1$。
特殊性质 B：$a_i \ge b_i$。
特殊性质 C：$a_i, b_i$ 在 $[1, {10}^6]$ 内独立均匀随机生成。
特殊性质 D：$a_i \ge 2$。
特殊性质 E：$a_i \le 4$。


title: [LNOI2022] 题

type: P

description:
给定长度为 $3 n$、值域为 $[0, 3]$ 的整数序列 $S = s_1 s_2 \cdots s_{3 n}$。你需要首先将 $S$ 中的每个 $0$ 替换为 $[1, 3]$ 中的任意一个整数，得到序列 $T = t_1 t_2 \cdots t_{3 n}$，然后给出 $n$ 个长度为 $3$ 的整数序列 ${\{ a_{i, 1}, a_{i, 2}, a_{i, 3} \}}_{1 \le i \le n}$，使得

- $\forall 1 \le i \le n$，$1 \le a_{i, 1} < a_{i, 2} < a_{i, 3} \le 3 n$；
- $\forall (i_1, j_1) \ne (i_2, j_2)$，$a_{i_1, j_1} \ne a_{i_2, j_2}$；
- $\forall 1 \le i \le n$，$\{ t_{a_{i, 1}}, t_{a_{i, 2}}, t_{a_{i, 3}} \}$ 是 $\{ 1, 2, 3 \}$ 的一个排列且逆序对数为奇数。

认为两个方案本质不同当且仅当序列 $T$ 不同或存在 $a_{i, j}$（$1 \le i \le n$，$1 \le j \le 3$）不同，求以上操作的本质不同的方案数，对 $({10}^9 + 7)$ 取模。

inputFormat:
**本题有多组测试数据**。输入的第一行包含一个正整数 $C$ 表示测试数据组数。

对于每组测试数据，第一行一个整数 $n$，接下来一行一个长度为 $3 n$ 的字符串描述序列 $S$。

outputFormat: 对于每组测试数据输出一行一个整数表示方案数对 $({10}^9 + 7)$ 取模的结果。


title: [LNOI2022] 盒

description:
有 $n$ 个不同的盒子排成一排。在初始状态下，第 $i$ 个盒子放有 $a_i$ 个货物，总货物数量为 $S = \sum_{i = 1}^{n} a_i$。对于非负整数数组 $(b_1, b_2, \ldots, b_n)$ 满足 $\sum_{i = 1}^{n} b_i = S$，考察以下问题：

你想让第 $i$ 个盒子中拥有恰好 $b_i$ 个货物，为此你可以做如下操作若干次：对两个相邻的盒子，把其中一个盒子的**恰好一个**货物移动至另一个。对 $i, i + 1$（$1 \le i < n$）号盒子做**一次**操作的代价为 $w_i$。**注意：将 $\bm{i}$ 号盒子的一个货物移动到 $\bm{i + 1}$ 号盒子和将 $\bm{i + 1}$ 号盒子的一个货物移动到 $\bm{i}$ 号盒子的代价都是 $\bm{w_i}$**。你需要保证在操作中不存在盒子中的货物数量是负数。

在以上问题下，定义从初始状态达到第 $i$ 个盒子拥有恰好 $b_i$ 个货物的状态的最小代价为 $\operatorname{val}(b_1, b_2, \ldots, b_n)$，你需要求出对所有满足 $\sum_{i = 1}^{n} b_i = S$ 的非负整数数组 $(b_1, b_2, \ldots, b_n)$，$\operatorname{val}(b_1, b_2, \ldots, b_n)$ 的和。输出这个答案对 $998244353$ 取模后的结果。

inputFormat:
**本题有多组测试数据**。输入的第一行包含一个正整数 $T$，表示测试数据组数。

对于每组数据，输入共三行。第一行一个正整数 $n$ 表示盒子的个数，第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ 描述初始状态，第三行 $n - 1$ 个正整数 $w_1, w_2, \ldots, w_{n - 1}$ 描述移动货物的代价。

outputFormat: 对于每组测试数据输出一行一个整数，表示对于所有满足 $\sum_{i = 1}^{n} b_i = S$ 的非负整数数组，达到目标的代价的最小值之和模 $998244353$ 的结果。

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

对于第一组数据，一共有六种需要考虑的情形，它们的 $b_1$ 和 $b_2$ 构成的二元组 $(b_1, b_2)$ 分别为 $(0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)$。

对于第一种情形，需要至少 $2$ 次移动，代价最小值为 $65472 \times 2 = 130944$。

对于第二种情形，需要至少 $1$ 次移动，代价最小值为 $65472$。

对于第三种情形，不需要做任何操作，代价最小值为 $0$。

对于第四种情形，需要至少 $1$ 次移动，代价最小值为 $65472$。

对于第五种情形，需要至少 $2$ 次移动，代价最小值为 $65472 \times 2 = 130944$。

对于最后一种情形，需要至少 $3$ 次移动，代价最小值为 $65472 \times 3 = 196416$。

因此，最小代价之和为 $130944 + 65472 + 0 + 65472 + 130944 + 196416 = 589248$。

**【样例 \#2】**

见附件中的 `box/box2.in` 与 `box/box2.ans`。

这个样例满足测试点 $5 \sim 8$ 的限制。

**【样例 \#3】**

见附件中的 `box/box3.in` 与 `box/box3.ans`。

这个样例满足测试点 $9 \sim 12$ 的限制。

**【样例 \#4】**

见附件中的 `box/box4.in` 与 `box/box4.ans`。

这个样例满足测试点 $13 \sim 14$ 的限制。

**【样例 \#5】**

见附件中的 `box/box5.in` 与 `box/box5.ans`。

这个样例满足测试点 $15 \sim 16$ 的限制。

**【样例 \#6】**

见附件中的 `box/box6.in` 与 `box/box6.ans`。

这个样例满足测试点 $17 \sim 18$ 的限制。

**【数据范围】**

保证对于任何测试点的任何一组数据，有 $2 \le n \le 5 \times {10}^5$，$1 \le S \le 2 \times {10}^6$，$a_i \ge 0$，$0 \le w_i < 998244353$。

| 测试点编号 | $T \le$ | $n \le$ | $S \le$ | 特殊性质 |
|:-:|:-:|:-:|:-:|:-:|
| $1 \sim 2$ | $1000$ | $5$ | $5$ | A |
| $3 \sim 4$ | $5$ | $9$ | $9$ | 无 |
| $5 \sim 8$ | $10$ | $2000$ | $2000$ | 无 |
| $9 \sim 12$ | $10$ | $2000$ | $2 \times {10}^5$ | 无 |
| $13 \sim 14$ | $2$ | $2 \times {10}^5$ | $2 \times {10}^5$ | B |
| $15 \sim 16$ | $2$ | $2 \times {10}^5$ | $2 \times {10}^5$ | AC |
| $17 \sim 18$ | $2$ | $2 \times {10}^5$ | $2 \times {10}^5$ | 无 |
| $19 \sim 20$ | $5$ | $5 \times {10}^5$ | $2 \times {10}^6$ | 无 |

特殊性质 A：对于任意 $1 \le i < n$，$w_i = 1$。
特殊性质 B：对于任意 $1 \le i < n - 20$，$a_i = 0$。
特殊性质 C：最多只有 $20$ 个 $i \in [1, n]$ 满足 $a_i \ne 0$。

**【提示】**

本题有读入量较大的测试点，为了优化程序运行的时间，我们建议你采用较为快速的读入方式。


title: [LNOI2022] 串

description:
为了让你更好地理解题面，给出若干关于字符串的定义：

- 对于一个字符串 $S = s_1 s_2 \cdots s_n$，定义其长度为 $\lvert S \rvert = n$。
- 对于两个字符串 $S = s_1 s_2 \cdots s_n$ 和 $T = t_1 t_2 \cdots t_m$，称 $T$ 为 $S$ 的子串，若 $m = 0$（即 $T$ 为空串）或者 $\exists 1 \le i \le j \le n$，$T = s_i s_{i + 1} \cdots s_j$。若 $m = 0$ 或上述判断条件中 $i$ 可以取到 $1$，则称 $T$ 为 $S$ 的前缀；若 $m = 0$ 或上述判断条件中 $j$ 可以取到 $n$，则称 $T$ 为 $S$ 的后缀。

给定一个英文小写字母构成的字符串 $S$，你需要找到一个尽可能长的字符串序列 $(T_0, T_1, \ldots, T_l)$，满足：

- $T_0$ 是 $S$ 的子串；
- $\forall 1 \le i \le l$，$\lvert T_i \rvert - \lvert T_{i - 1} \rvert = 1$；
- $\forall 1 \le i \le l$，存在 $S$ 的一个长度为 $\lvert T_i \rvert + 1$ 的子串 $S'_i$，使得 $S'_i$ 的长度为 $\lvert T_{i - 1} \rvert$ 的前缀为 $T_{i - 1}$，长度为 $\lvert T_i \rvert$ 的后缀为 $T_i$。

输出这样的字符串序列的长度的最大值（即 $l$ 的最大值）。

inputFormat: **本题有多组测试数据**。输入的第一行为一个整数 $T$，表示测试数据组数。对于每组测试数据，输入一行一个英文小写字母构成的字符串 $S$。

outputFormat: 对于每组测试数据输出一行一个整数，表示题目描述中字符串序列长度的最大值。

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

下文中使用符号 $\epsilon$ 表示空串。

对于第一组测试数据，可以找到如下字符串序列：$T_0 = \epsilon, T_1 = \texttt{b}, T_2 = \texttt{cd}$，其中 $S'_1 = \texttt{ab}, S'_2 = \texttt{bcd}$。

对于第二组测试数据，可以找到如下字符串序列：$T_0 = \epsilon, T_1 = \texttt{b}, T_2 = \texttt{ab}, T_3 = \texttt{bab}$，其中 $S'_1 = \texttt{ab}, S'_2 = \texttt{bab}, S'_3 = \texttt{abab}$。

对于第三组测试数据，可以找到如下字符串序列：$T_0 = \epsilon$。

**【样例 \#2】**

见附件中的 `string/string2.in` 与 `string/string2.ans`。

该组样例中的字符串长度有一定梯度，你可以利用该组样例对程序进行检查。

**【样例 \#3】**

见附件中的 `string/string3.in` 与 `string/string3.ans`。

该组样例满足特殊性质 A。

**【数据范围】**

设 $\sum |S|$ 表示测试点中所有测试数据的字符串长度和。

对于 $100 \%$ 的测试数据，$T \ge 1$，$1 \le \lvert S \rvert \le 5 \times {10}^5$，$1 \le \sum \lvert S \rvert \le 1.5 \times {10}^6$。

| 测试点编号 | $\lvert S \rvert \le$ | $\sum \lvert S \rvert \le$ | 特殊性质 |
|:-:|:-:|:-:|:-:|
| $1 \sim 2$ | $30$ | $150$ | 无 |
| $3 \sim 5$ | $200$ | $800$ | 无 |
| $6 \sim 8$ | $1000$ | $3000$ | 无 |
| $9 \sim 11$ | $5 \times {10}^5$ | $1.5 \times {10}^6$ | A |
| $12 \sim 15$ | $6 \times {10}^4$ | $3 \times {10}^5$ | 无 |
| $16 \sim 20$ | $5 \times {10}^5$ | $1.5 \times {10}^6$ | 无 |

特殊性质 A：字符串中的每个字符在小写字母中独立均匀随机生成。

**【提示】**

本题输入输出量较大，请使用较为快速的输入输出方式。

例如，若你的代码使用了 `cin` 和 `cout` 作为输入输出方式，你可以选择在代码的**输入输出重定向语句**（`freopen` 语句、 `fopen` 语句等）**之后**加入以下语句加速输入输出速度。

```cpp
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
```

**加入该语句后不建议同时使用 `cin, cout` 和其他输入输出方式。**


title: 集合运算 1

type: B

background:
集合是数学中的一个概念，用通俗的话来讲就是：一大堆数在一起就构成了集合。

集合有如下的特性：

- 无序性：任一个集合中，每个元素的地位都是相同的，元素之间是无序的。

- 互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。

- 确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。

元素 $a$ 属于集合 $A$ 记作 $a\in A$，反之则记作 $a\notin A$。

若一个集合中不存在任何元素，则称该集合为空集，记作 $\varnothing$。空集是所有集合的子集。

一个集合内的元素个数称为该集合的大小。$A$ 集合的大小可记作 $|A|$。

集合 $C$ 是集合 $A$ 与 $B$ 的交集，当且仅当对于任何元素 $a\in C$，有 $a\in A$ 且 $a\in B$，并且对于任何元素 $b\notin C$，有 $b\notin A$ 或 $b\notin B$。记作 $C=A\cap B$。

集合 $C$ 是集合 $A$ 与 $B$ 的并集，当且仅当对于任何元素 $a\in C$，有 $a\in A$ 或 $a\in B$，并且对于任何元素 $b\notin C$，有 $b\notin A$ 且 $b\notin B$。记作 $C=A\cup B$。

简单地说，交集是由所有同时属于两个集合的元素所构成的，就像两个集合相交；而并集是由所有属于其中任意一个集合的元素所构成的，就像两个集合合并。

特别地，对于形如 $\{x|a\le x\le b\}$ 的集合，可以记作 $[a,b]$。其中，如果左侧符号改为小于号，则左侧中括号改为小括号。右侧同理。

description:
现在给予两个集合 $A$ 和 $B$，均由 $0$ 到 $63$ 之间的整数组成。

请依次求出：

- $|A|$
- $A\cap B$
- $A\cup B$

inputFormat:
输入四行。

第一行一个整数 $x(0\le x \le 63)$，表示集合 $A$ 的元素个数。

第二行 $x$ 个整数 $a_1,...a_x$，表示集合 $A$ 的各个元素，保证不重复。如果 $A$ 是空集，则这一行没有数字。

第三行一个整数 $y(0\le y \le 63)$，表示集合 $B$ 的元素个数。

第四行 $y$ 个整数 $b_1,...b_x$，表示集合 $B$ 的各个元素，保证不重复。如果 $B$ 是空集，则这一行没有数字。

outputFormat:
输出三行。

第一行输出一个整数，表示 $|A|$。

第二行输出若干个整数，表示 $A\cap B$ 中对应元素，从小到大输出，用空格隔开。如果是空集，则这一行什么也不输出，保留换行。

第三行输出若干个整数，表示 $A\cup B$ 中对应元素，从小到大输出，用空格隔开。如果是空集，则这一行什么也不输出，保留换行。


title: 集合运算 2

background:
集合是数学中的一个概念，用通俗的话来讲就是：一大堆数在一起就构成了集合。

集合有如下的特性：

- 无序性：任一个集合中，每个元素的地位都是相同的，元素之间是无序的。

- 互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。

- 确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。

元素 $a$ 属于集合 $A$ 记作 $a\in A$，反之则记作 $a\notin A$。

如果对于任意集合 $A$ 内的元素 $a$，都有 $a\in B$，则称 $A$ 为 $B$ 的子集，记作 $A\subseteq B$。

若集合 $A$，$B$ 满足集合 $A$ 中的元素都能够在 $B$ 中找到，且集合 $B$ 中的元素都能在 $A$ 中找到，则称集合 $A$ 与 $B$ 相等，记作 $A=B$。

若一个集合中不存在任何元素，则称该集合为空集，记作 $\varnothing$。空集是所有集合的子集。

一个集合内的元素个数称为该集合的大小。$A$ 集合的大小可记作 $|A|$。

集合 $C$ 是集合 $A$ 与 $B$ 的交集，当且仅当对于任何元素 $a\in C$，有 $a\in A$ 且 $a\in B$，并且对于任何元素 $b\notin C$，有 $b\notin A$ 或 $b\notin B$。记作 $C=A\cap B$。

集合 $C$ 是集合 $A$ 与 $B$ 的并集，当且仅当对于任何元素 $a\in C$，有 $a\in A$ 或 $a\in B$，并且对于任何元素 $b\notin C$，有 $b\notin A$ 且 $b\notin B$。记作 $C=A\cup B$。

简单地说，交集是由所有同时属于两个集合的元素所构成的，就像两个集合相交；而并集是由所有属于其中任意一个集合的元素所构成的，就像两个集合合并。

设集合 $A\subseteq U$，称集合 $B$ 为集合 $A$ 关于集合 $U$ 的补集，当且仅当 $B$ 集合内的所有元素恰好为所有属于 $U$ 集合但不属于 $A$ 集合的元素。记作 $B=\complement_UA$。显然可以得到这样的一个式子：$|U|=|A|+|\complement_UA|$，对于任何 $A \subseteq U$ 成立。

简单地说，补集就是与一个集合互补的集合，每个元素恰好在其中两者之一。

特别地，对于形如 $\{x|a\le x\le b\}$ 的集合，可以记作 $[a,b]$。其中，如果左侧符号改为小于号，则左侧中括号改为小括号。右侧同理。

description:
现在给予两个集合 $A$ 和 $B$，均由 $0$ 到 $63$ 之间的整数组成。全集 $U=\{x|0\le x\le 63,x\in \mathbb{Z}\}$。

请依次求出：

- $|A|$
- $A\cap B$
- $A\cup B$
- $\complement_UA$
- $A=B$ 是否成立
- $A\subseteq B$ 是否成立
- $0 \in A$ 是否成立

outputFormat:
输出七行。

第一行输出一个整数，表示 $|A|$。

第二行输出若干个整数，表示 $A\cap B$ 中对应元素。

第三行输出若干个整数，表示 $A\cup B$ 中对应元素。

第四行输出若干个整数，表示 $\complement_UA$ 中对应元素。

第五至第七行，各输出一个整数，分别表示$A=B$、$A\subseteq B$、$0 \in A$ 是否成立。如果成立则本行输出 $1$，否则输出 $0$。

输出一个集合对应的元素时，从小到大输出，用空格隔开。如果是空集，则这一行什么也不输出，保留换行。


title: 「KDOI-03」构造数组

description:
你现在有一个长度为 $n$ 的数组 $a$。一开始，所有 $a_i$ 均为 $0$。给出一个同样长度为 $n$ 的目标数组 $b$。求有多少种方案，使得通过若干次以下操作，可以让 $a$ 数组变成 $b$。

* 选出两个**不同的**下标 $1\leq i<j\leq n$，并将 $a_i$ 和 $a_j$ 同时增加 $1$。

两种方案被称之为不同的，当且仅当存在一个 $x$ 使得一种方案中第 $x$ 次操作选择的两个下标 $(i,j)$ 与另一种方案中的不同。

**答案对 $\bm{998244353}$ 取模。**

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

输入数据一共包含两行。

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

第二行包含 $n$ 个正整数，表示 $b_1,b_2,\ldots,b_n$。

outputFormat:
输出到标准输出。

输出一行一个正整数，表示将 $a$ 数组通过若干次操作变成 $b$ 数组的方案数对 $998244353$ 取模后的结果。


title: [POI2004] Gra

description:
让我们考虑一个在 $m \times 1$ 的板子上玩的游戏,板子被从 $1$ 到 $m$ 编号。

现在板子上有 $n$ 个棋子，每个都严格占据板子上的一个格子，没有一个棋子占据格子 $m$。

每个单独的移动遵循以下原则：移动的人选择一个棋子把它移动到比它大的格子中第一个未被占据的格子里去。两个选手交替移动，谁先占据格子 $m$ 谁赢。

我们在当且仅当他移动以后令一选手无论如何都无法赢他的时候说当前选手的移动称作 $\text{winning}$ 操作。

我们想知道先手有多少个移动是 $\text{winning}$ 操作。

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

然后接下来 $n$ 个上升的整数表示初始被占据的格子编号。

outputFormat: 输出先手有多少移动是 $\text{winning}$ 操作。

hint:
对于 $100$ % 的数据：$2 \le m \le 10^{9}, 1 \le n \le 10^{6}$ ，且有 $n + 1 \le m$ 。

下面是一个例子：

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

在 $m = 7$ 的时候，一个选手可以把 $2$ 移到 $4$，把 $3$ 移到 $4$ 或者把 $6$ 移动到 $7$。


title: [JRKSJ R6] Eltaw

background:
![](https://cdn.luogu.com.cn/upload/image_hosting/at23jtmh.png?x-oss-process=image)

你在月下独自行走，不禁想起了一道简单题。

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

description: 给你 $k$ 个长为 $n$ 的序列 $a_{1\dots k,1\dots n}$，有 $q$ 次询问，每次询问给出一个区间 $[l,r]$，要求出 $\displaystyle\max_{i=1}^k\sum_{j=l}^ra_{i,j}$，即求出所有序列中区间 $[l,r]$ 的和的最大值。

inputFormat:
第一行三个整数 $n,k,q$。\
接下来 $k$ 行，每行 $n$ 个整数 $a_{i,j}$。\
接下来 $q$ 行，每行两个整数 $l,r$ 表示一次询问。

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

hint:
Idea：cyffff，Solution：cyffff，Code：cyffff，Data：cyffff

**Eltaw - Fl00t (Insane14.4)**

**本题输入输出文件较大，请使用恰当的输入输出方式。**
### 数据规模
本题采用捆绑测试。

| $\text{Subtask}$ | $n\le$ | 特殊限制 | $\text{Score}$ |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $5\times10^3$ | $k\le 100$ | $20$ |
| $2$ | $5\times10^5$ | 保证 $l=1$ | $30$ |
| $3$ | $5\times10^5$ | 无 | $50$ |

对于 $100\%$ 的数据，$1\le n,k,q\le5\times 10^5$，$1\le n\times k\le 5\times10^5$，$1\le l\le r\le n$，$0\le a_{i,j}\le 10^9$。
### 数据更新记录
$\text{upd 2022.10.05}$：更新了两组数据，分别卡掉了两种时间复杂度错误的做法。感谢 @[二叉苹果树](https://www.luogu.com.cn/user/270854) 指出。

$\text{upd 2022.10.08}$：更新了一组数据，卡掉了记忆化不正确的做法。感谢 @[SweetOrangeOvO](https://www.luogu.com.cn/user/236862) 指出。

如果你能通过现在的所有测试点，说明你的代码复杂度极可能是正确的。如果你仍认为你的复杂度是错误的，请联系出题人。


title: [POI2004] Bra

description:
让我们考虑一个包含 $n$ 个门的电路。

门从 $0$ 到 $n-1$ 编号，每个门都包含若干个输入和一个输出。

每一个输入和输出都只可能是 $0,1,\dfrac{1}{2}$ 三种状态，每个输入都连接着某个门的输出，输入的状态就等于它连接的输出的状态值，而每个输出可能连接着任意多个输入。

$0$ 和 $1$ 是很特殊的两个门。门 $0$ 的输出永远为 $0$，门 $1$ 的输出永远为 $1$。

一个门有效的输出状态条件如下:

1. 它的输入中 $0$ 的个数多于 $1$ 的个数那么输出状态为 $0$。

2. 它的输入中 $0$ 的个数等于 $1$ 的个数那么输出状态为 $\dfrac{1}{2}$。

3. 它的输入中 $0$ 的个数少于 $1$ 的个数那么输出状态为 $1$。

4. 对于门 $0$ 和 $1$，他们分别输出 $0$ 和 $1$。

现在给出电路信息，请你编写一个程序，确定所有可以确定状态的门的状态分别是什么。

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

接下来 $n-2$ 行表示门的连接信息，第 $i$ 行描述第 $i$ 个门的输入端，一个数 $k_i$ 表示它的输入端个数，接下来 $k_i$  个数分别表示每个输入端的门的编号。

outputFormat: 输出 $n$ 行，表示 $n$ 个门的输出状态。如果确定，请输出具体状态值，否则输出 $?$ 。

hint: 对于全部数据，$2 \le n \le 10000,k_i \ge 1$，数据保证所有门的输入端总数不超过 $200000$。


title: [POI2004] SZN

description:
$\text{String-Toys joint-stock}$ 公司需要你帮他们解决一个问题。

他们想制造一个没有环的连通图模型，每个图都是由一些顶点和特定数量的边构成。每个顶点都可以连向许多的其他顶点。一个图是连通且无环的，图是由许多的线做成的。一条线是一条连接图中两个顶点之间的路径。

由于一些技术原因，两条线之间不能有重叠的部分，要保证图中任意一条边都被且仅被一条线所覆盖。

做一个这样的图的模型的费用取决于用了多少条线以及最长的那条的长度(每条边的长度都为 $1$ )。

现在给你对应的图，请你编写一个程序，求出最少能用多少条线以及在用最少线的情况下最长的那根线最短可以为多少。

inputFormat:
第一行仅包含一个数 $n$ ，表示顶点的总数。顶点从 $1$ 到 $n$ 进行编号。

接下来的 $n - 1$ 行描述这些边，每行两个数 $a$ 和 $b$,表示顶点 $a$ 和顶点 $b$ 之间有一条边。

outputFormat: 输出两个数,最少用多少条线以及在用最少线的情况下最长线最短可以为多少.

hint:
对于 $100$ % 的数据：$2 \le n \le 10000,1 \le a,b \le n$ 。

样例解释：

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


title: 「WHOI-2」ぽかぽかの星

background:
![](bilibili:BV16J411x7nS)

你在雪洞里喝着热可可数星星。但这次，星星换成了数列，不过聪明的你一定能数清楚数列的吧。

description:
有多少个长度为 $n$ 的**正整数**数列 $a_i$ 满足：

- $0<a_1\leq a_2\leq a_3\dots \leq a_n\leq k$。
- $\forall i\not = j,a_i+a_j\not = k+1$。

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

inputFormat:
**本题多测**

第一行一个正整数表示 $T$。

接下来 $T$ 行，每行两个正整数表示 $n,k$。

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

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

- $\text{subtask1(20pts)}:T=5,1\leq n,k\le5$。
- $\text{subtask2(80pts)}:$ 无特殊限制。

对于 $100\%$ 的数据，$T\leq100,1\le n,k\le 5\times 10^6,1\leq  \sum n,  \sum  k\le6\times 10^7$。


title: 「GMOI R2-T4」电子木鱼

background:
运营电子资本，招聘赛博佛祖，积累虚拟功德。

功德无量，随喜赞叹。

**【Upd 2023/04/05 22:27】增加了两组来自 @[嘉然今天吃什么](/user/559835) 的 hack 数据。**

description:
给你 $n$，表示一共有 $n$ 位赛博佛祖，编号依次为 $1 \sim n$。

第 $i\ (1 \leq i \leq n)$ 位赛博佛祖可以对应为一个二元组 $\langle S_i, d_i \rangle$，其中 $S$ 在任意时刻均为 $\{1, 2, 3, \dots, m\}$ 的一个子集（可以为空），而 $d_i$ 为 $1 \sim m$ 间的整数。

如果在某一时刻，存在一位赛博佛祖的 $S_i$ 为空集，佛祖会感到很开心而给你加功德。具体地，他会敲响第 $d_i$ 个木鱼，并 **在下一时刻同时** 影响所有的 $n$ 位赛博佛祖（包括他自己）。对第 $j(1 \leq j \leq n)$ 位赛博佛祖，如果 $d_i \in S_j$，那么将从 $S_j$ 内删去 $d_i$；否则向 $S_j$ 内加入 $d_i$。如果有多位赛博佛祖的 $S_i$ 为空集，取编号最小的 $i$ 为你加功德。

现在作为电子资本家的你，想要功德无量。你想知道，最少再请来几位赛博佛祖，可以使得你的这些佛祖们 **源源不断地** 为你加功德。假设这个答案是 $s$（可以为 $0$），那么新的佛祖们的编号依次为 $(n+1) \sim (n+s)$。

**因为你是个资本家，有时候你不想请那么多佛祖**。所以你有许多组询问，对于一组 $l, r$，设 $f(l, r)$ 表示如果初始只有 $[l, r]$ 之间的佛祖，答案将会是多少，注意，每组询问相互独立，上一次添加的佛祖不会延续到以后的询问中。

为了避免太多的输出，你只需要输出：

$$\sum\limits_{l=1}^n\sum\limits_{r=l}^n f(l,r)\times2^l$$

即可，答案对 $10^9 + 7$ 取模。

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

接下来 $n$ 行，第 $i$ 行首先一个整数描述 $d_i$，接着一个长度为 $m$ 的 $\texttt{01}$ 字符串表示 $S_i$。如果第 $j$ 个字符为 $1$，表示 $j \in S_i$；否则 $j \notin S_i$。

outputFormat: 一行，表示最终答案取模后的值。

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

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

- Subtask 0（10 pts）：$n \leq 10$，$m \leq 5$。
- Subtask 1（10 pts）：$n \leq 300$，$m \leq 10$。
- Subtask 2（15 pts）：$n \leq 1024$，$m \leq 10$。保证每个 $S_i$ 均不同。
- Subtask 3（15 pts）：$n \leq 10^4$。
- Subtask 4（10 pts）：每个 $S_i$ 均在 $2^m$ 种情况中等概率随机生成，$d_i$ 均在 $m$ 种情况中等概率随机生成。
- Subtask 5（40 pts）：无特殊限制。

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


title: [JRKSJ R7] 技巧性的块速递推

background:
充分必要，切比雪夫。

原来还是，不需要了。

description:
一个 $n\times m$ 的棋盘，对每个格子染上黑白两色之一。

询问有多少种染色方式，使得不存在横、竖、斜连续四个格子中存在至少三个相同颜色的格子，并且不存在横、竖、斜连续三个格子的颜色相同。

若设棋盘的左上角为 $(1,1)$，右下角为 $(n,m)$，则称 $\{(x,y),(x+1,y),(x+2,y)\}$ 为横的连续三个格子，$\{(x,y),(x,y+1),(x,y+2)\}$ 为竖的连续三个格子、$\{(x,y),(x+1,y+1),(x+2,y+2)\}$ 和 $\{(x,y),(x+1,y-1),(x+2,y-2)\}$ 为斜的连续三个格子（以上格子均在棋盘内）。

连续四个格子同理。

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

第一行一个整数 $T$ 表示数据组数。\
接下来 $T$ 行，每行两个整数 $n,m$ 表示一次询问。

outputFormat: 共 $T$ 行，每行一个整数表示答案。答案对 $998244353$ 取模。


title: [APIO2022] 火星

background:
本题只支持 C++ 提交，提交时不需要包含 `mars.h` 头文件，只需要将附件中的 `mars.h` 中的内容粘贴到代码的开头即可。

请使用 C++14、C++17 等语言，**而不是 C++14 (GCC 9)**，因为一些未知原因这个语言下 SPJ 会 CE。

**【注】：洛谷暂不支持题面中所说的评测方式，我实现了一个洛谷支持的简易版本的交互库，但不能对传递数据进行有效限制，请各位自觉。**

description:
你们晓得，法老们是最先去过外太空的人。他们发射过首次登陆行星图特摩斯一世（Thutmus I，现在一般叫它火星）的飞船。行星的表面可以建模成由方形单元构成的 $(2n + 1) \times (2n + 1)$ 网格，其中每个单元中或者为陆地、或者为水域。对于第 $i$ 行第 $j$ 列（$0 \le i, j \le 2 \cdot n$）的单元，如果单元中为陆地，则其状态表示为 $s[i][j] = \texttt{1}$；如果单元中为水域，则表示为 $s[i][j] = \texttt{0}$。

如果在两个陆地单元之间存在某条仅由陆地单元构成的路径，而且路径中每两个连续的前后单元都有公共边，则称这两个陆地单元是连通的。行星上的岛屿被定义为两两连通的陆地单元的极大集合。

飞船的任务是统计该行星上岛屿的数量。然而，考虑到飞船的上古电脑，这事儿并不容易。电脑的内存储器 $h$ 以一个 $(2n + 1) \times (2n + 1)$ 的二维数组的形式存储数据，且数组的每个位置上可以保存长度为 $100$ 的字符串，串中的每个字母为 $\texttt{0}$（ASCII 码 $48$）或 $\texttt{1}$（ASCII 码 $49$）。初始时，存储器的每个位置的第 $0$ 位记录的是上述网格中每个单元的状态，即 $h[i][j][0] = s[i][j]$（对所有 $0 \le i, j \le 2 \cdot n$）。$h$ 中的其他位在初始时都被置为 $\texttt{0}$（ASCII 码 $48$）。

在处理存储器中的数据时，电脑只能访问存储器中的 $3 \times 3$ 区块，并且改写该区块左上角位置的值。说得更正式一点，电脑可以访问 $h[i \dots i + 2][j \dots j + 2]$（$0 \le i, j \le 2 \cdot (n - 1)$）中的值，并且改写 $h[i][j]$ 中的值。在
下文中，该过程被叫做**处理单元** $(i, j)$。

为了解决电脑能力的局限，法老们搞出了下面的套路：

- 电脑可以分成 $n$ 个阶段来操作存储器。
- 在阶段 $k$（$0 \le k \le n - 1$），令 $m = 2 \cdot (n - k - 1)$， 电脑将对所有的 $0 \le i, j \le m$，按照 $i$ 的升序以及每个 $i$ 上 $j$ 的升序，处理单元 $(i, j)$。换句话说，电脑将按照如下顺序处理这些单元：$(0, 0), (0, 1),\cdots , (0, m), (1, 0), (1, 1),\cdots , (1, m),\cdots , (m, 0), (m, 1),\cdots , (m, m)$。
- 在最后一个阶段（$k = n - 1$），电脑仅处理单元 $(0, 0)$。该阶段结束后，写入到 $h[0][0]$ 的值应该等于行星上的岛屿数量，而且该值应以字符串的形式表示成二进制，其中最低有效位对应于字符串的首字符。

下图给出了电脑操作某个 $5 \times 5$（$n = 2$）存储器的方式。蓝色单元表示该单元正在被改写，而着色的单元则表示被处理的子数组。

在阶段 $0$，电脑将以如下顺序处理下面的子数组：

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

在阶段 $1$，电脑将仅处理一个子数组：

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

你的任务是给出一个方法，让电脑能在给定的操作方式下，统计出行星图特摩斯一世上的岛屿数量。

## 实现细节

你需要实现下面的函数：

```cpp
string process(string[][] a, int i, int j, int k, int n)
```

- $a$：一个 $3 \times 3$ 数组，表示正在被处理的子数组。特别说明，有 $a = h[i \dots i + 2][j \dots j + 2]$，这里 $a$ 中的每个元素均为长度恰好为 $100$ 的字符串，而且串中的字符为 $\texttt{0}$（ASCII 码 $48$）或 $\texttt{1}$（ASCII 码 $49$）。
- $i, j$：电脑当前正在处理的单元的行号和列号。
- $k$：当前阶段的序号。
- $n$：阶段总数，同时也是行星表面的大小，此时行星表面包含 $(2n + 1) \times (2n + 1)$ 个单元。
- 该函数应返回一个长度为 $100$ 的二进制表示字符串。返回值将保存在电脑存储器中的 $h[i][j]$ 处。
- $k = n - 1$ 时，是该函数的最后一次调用。在此次调用中，函数应以字符串的形式返回行星上的岛屿数量的二进制表示，其最低有效位对应下标 $0$ 处的字符（二进制字符串的首字符），次低有效位对应下标 $1$ 处的字符，以此类推。
- 该函数必须独立于任何的静态或全局变量，且其返回值应仅依赖于传递给该函数的参数。

每个测试用例包括 $T$ 个独立的场景（也就是说，不同的行星表面情形）。你的函数在每个场景上的行为，必须与这些场景的顺序无关，因为对同一场景的 `process` 函数调用可能不是连续发生的。但是，可以确保对每个场景，会按照题面所描述的顺序来调用函数 `process`。

此外，对每个测试用例，你的程序可能会同时运行多个实例。内存限制和 CPU 用时限制将施加在所有这些实例的总和上。任何故意在这些实例之间偷偷传递数据的行为，都将被认定为作弊，选手可能会因此被取消比赛资格。

**【注】：洛谷暂不支持这种评测方式，我实现了一个洛谷支持的简易版本的交互库，但不能对传递数据进行有效限制，请各位自觉。**

特别说明，在调用函数 `process` 时保存在静态或全局变量中的信息，不保证在下次调用时可以读出。

inputFormat:
评测程序示例读取如下格式的输入：

- 第 $1$ 行：$T$。
- 第 $i$ 个区块（$0 \le i \le T - 1$）：该区块表示第 $i$ 个场景。
	- 第 $1$ 行：$n$。
	- 第 $2 + j$ 行（$0 \le j \le 2 ⋅ n$）：$s[j][0]\ s[j][1]\ \dots\ s[j][2 \cdot n]$。

outputFormat:
评测程序示例将按照如下格式打印出结果：

- 第 $1 + i$ 行（$0 \le i \le T - 1$）：在第 $i$ 个场景上，函数 `process` 最后一次的返回值的十进制表示。


title: [APIO2022] 游戏

background: 本题只支持 C++ 提交，提交时不需要包含 `game.h` 头文件，只需要将附件中的 `game.h` 中的内容粘贴到代码的开头即可。

description:
法老们发现了标号从 $0$ 到 $n - 1$ 的 $n$ 个星球，并且在它们之间建立了一个**单向传输系统**。在这个传输系统中，每个传送器连接一个起始星球和一个目的星球。当游客从一个起始星球使用传送器，就可以到达对应的目的星球。需要注意的是，起始星球和目的星球有可能是同一个星球。我们使用 $(u, v)$ 表示一个起始于星球 $u$ 到达星球 $v$ 的传送器。

为了促进传输系统的广泛使用，法老们设计了一个供游客们在乘坐传送系统时可以进行的游戏。一名游客可以从任一星球出发。标号 $0, 1,\dots , k - 1$（$k \le n$）的星球被称为**特殊星球**。当游客每次进入一个特殊星球，就可以获得一枚邮票。

目前，对于每个星球 $i$（$0 \le i \le k - 2$），都建立了一个传送器 $(i, i + 1)$。这 $k - 1$ 个传送器叫做**起始传送器**。

传送器随着时间不断建立。随着传送器的建立，一名游客也许有可能获得无穷多枚邮票。准确来说，这种情况会在存在一个满足如下条件的星球序列 $w[0], w[1],\dots , w[t]$ 时发生：

- $1 \le t$。
- $0 \le w[0] \le k - 1$。
- $w[t] = w[0]$。
- 对于每个星球 $i$（$0 \le i \le t - 1$），存在一个传送器 $(w[i], w[i + 1])$。

注意一名游客能够使用起始传送器和任何一个目前已经建立的传送器。

你的任务是，帮助法老验证在每次加入新的传送器后，一位游客是否能够拿到无穷多枚邮票。

## 实现细节

你需要实现下述函数：

```cpp
init(int n, int k)
```

- $n$：星球数量。
- $k$：特殊星球数量。
- 这个函数只会被调用一次，早于任何一次 `add_teleporter` 调用。

```cpp
int add_teleporter(int u, int v)
```

- $u$ 和 $v$：被加入传送器的起始和目的星球。
- 这个函数至多被调用 $m$ 次（$m$ 的取值范围参阅“约束条件”部分的内容）。
- 如果当传送器 $(u, v)$ 被加入后游客能够获得无穷多枚邮票，函数需要返回 $1$。否则，这个函数应该返回 $0$。
- 一旦函数返回了 $1$，你的程序将会被终止。

inputFormat:
评测程序示例按照如下的格式读取输入数据：

- 第 $1$ 行：$n\ m\ k$。
- 第 $2 + i$ 行（$0 \le i \le m - 1$）：$u[i]\ v[i]$。

评测程序示例首先调用 `init`，然后按照 $i = 0, 1,\dots , m - 1$ 的顺序调用 `add_teleporter`：$u = u[i]$ 和 $v = v[i]$。

outputFormat:
程序需要打印多次调用 `add_teleporter` 中首次返回 $1$ 的调用索引（$0$ 到 $m - 1$，包含 $0$ 和 $m - 1$）；当所有 `add_teleporter` 调用中都返回 $0$ 时，你的程序需要返回 $m$。

如果某次 `add_teleporter` 调用返回了 $0$ 和 $1$ 之外的整数，评测程序示例会打印 $-1$，你的程序会被马上终止。

hint:
## 例子

### 例 $1$

考虑下面的函数调用：

```cpp
init(6, 3)
```

在这个例子里，有 $6$ 个星球和 $3$ 个特殊星球，标号为 $0,1,2$ 的星球是特殊星球。起始传送器是 $(0,1)$ 和 $(1,2)$。

假设评测程序执行下述调用：

- (0) `add_teleporter(3, 4)`：应该返回 $0$。
- (1) `add_teleporter(5, 0)`：应该返回 $0$。
- (2) `add_teleporter(4, 5)`：应该返回 $0$。
- (3) `add_teleporter(5, 3)`：应该返回 $0$。
- (4) `add_teleporter(1, 4)`：在这种情况下，是可能获得无穷多枚邮票的。例如，游客可以从星球 $0$ 出发，按照 $1, 4, 5, 0, 1, 4, 5, 0,\dots$ 这个顺序进行。因此，函数需要返回 $1$，进一步你的程序会被终止。

下图对于这个例子进行了说明。特殊星球和起始传送器都使用粗体字表示。通过 `add_teleporter` 加入的传送器，按照顺序被标记为 $0$ 到 $4$。

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

### 例 $2$

考虑下面的函数调用：

```cpp
init(4, 2)
```

在这个例子里，有 $4$ 个星球和 $2$ 个特殊星球。标号为 $0$ 和 $1$ 星球是特殊星球。起始传送器是 $(0, 1)$。

假设评测程序执行下述调用：

- `add_teleporter(1, 1)`：当加入传送器 $(1, 1)$ 后，我们就能够获得无穷多枚邮票。例如，游客从星球 $1$ 出发，可以使用传送器 $(1, 1)$ 到达星球 $1$ 无限次。因此，函数需要返回 $1$，然后你的程序被终止。

附件包里还包含了另一个样例输入输出。

## 约束条件

- $1\le n\le 3\times 10^5$；
- $1\le m\le 5\times 10^5$；
- $1\le k\le n$。

对于每次调用 `add_teleporter` 函数：

- $0\le u\le n-1$ 和 $0\le v\le n-1$；
- 在传送器 $(u,v)$ 加入之前，不会有从星球 $u$ 到星球 $v$ 的传送器。

## 子任务

1. （$2$ 分）$n=k$，$n\le 100$，$m\le 300$；
2. （$10$ 分）$n\le 100$，$m\le 300$。
3. （$18$ 分）$n\le 10^3$，$m\le 5\times 10^3$。
4. （$30$ 分）$n\le 3\times 10^4$，$m\le 5\times 10^4$，$k\le 10^3$。
5. （$40$ 分）没有额外的约束条件。


title: [APIO2022] 排列

background: 本题只支持 C++ 提交，提交时不需要包含 `perm.h` 头文件，只需要将附件中的 `perm.h` 中的内容粘贴到代码的开头即可。

description:
法老们利用行星的引力来加速飞船。假设飞船将依次以 $p[0], p[1],\dots , p[n - 1]$ 的轨道速度飞掠 $n$ 颗行星。飞掠每颗行星时，法老科学家可以选择是否利用它来加速飞船。为了节省能量，当飞船以轨道速度 $p[i]$ 飞掠一颗行星并完成加速后，它将不能再在以轨道速度 $p[j] < p[i]$ 飞掠行星时进行加速。也就是说，选择用来加速的行星构成 $p[0], p[1],\dots , p[n - 1]$ 的一个**递增子序列**。$p$ 的子序列是从 $p$ 中删除零个或多个元素得到的序列。例如，$[0]$、$[ ]$、$[0, 2]$ 和 $[0, 1, 2]$ 是 $[0, 1, 2]$ 的子序列，但 $[2, 1]$ 不是。

科学家已经确认，总共有 $k$ 种方案来选择行星对飞船进行加速，但是他们弄丢了轨道速度的记录信息（甚至包括 $n$ 的大小）。不过他们记得 $(p[0], p[1],\dots , p[n - 1])$ 是 $0, 1,\dots , n - 1$ 的一个排列。这里的排列是包含从 $0$ 到 $n - 1$ 每个整数恰好一次的序列。 你的任务是找出一个长度尽量小且符合要求的排列 $(p[0], p[1],\dots , p[n - 1])$。

你要对 $q$ 艘不同的飞船来解决该问题。对每艘飞船 $i$，你会得到一个整数 $k_i$，表示选择行星加速飞船的不同方案数。你的任务是找出长度 $n$ 足够小的轨道速度序列，使得从中恰好可以选出 $k_i$ 个轨道速度递增的行星子序列。

## 实现细节

你要实现以下函数：

```cpp
int[] construct_permutation(int64 k)
```

- $k$ 是应有的递增子序列的数量。
- 该函数要返回有 $n$ 个元素的数组，每个元素是 $0$ 到 $n - 1$ 之间（包括 $0$ 和 $n - 1$）的数。
- 返回的数组必须是恰好有 $k$ 个递增子序列的合法排列。
- 该函数总共被调用 $q$ 次。每次调用被视为一个独立的场景。

inputFormat:
评测程序示例按以下格式读取输入：

- 第 $1$ 行：$q$。
- 第 $2+i$ 行（$0\le i\le q-1$）：$k_i$。

outputFormat: 评测示例程序对每个 $k_i$ 打印一行，包含对应 `construct_permutation` 调用的返回值。如果出错则打印错误信息。

hint:
## 例子

### 例 $1$

考虑以下调用：

```cpp
construct_permutation(3)
```

该函数应该返回一个恰好有 $3$ 个递增子序列的排列。一种可能的答案是 $[1,0]$，它的递增子序列有 $[]$（空的子序列）、$[0]$ 和 $[1]$。

### 例 $2$

考虑以下调用：

```cpp
construct_permutation(8)
```

该函数应该返回一个恰好有 $8$ 个递增子序列的排列。一种可能的答案是 $[0,1,2]$。

## 约束条件

- $1\le q\le 100$。
- $2\le k_i\le 10^{18}$（对所有 $0\le i\le q-1$）。

## 子任务

1. （$10$ 分）$2\le k_i\le 90$（对所有 $0\le i\le q-1$）。如果你给出的所有排列长度至多为 $90$ 且结果正确，你将获得 $10$ 分，否则获得 $0$ 分。
2. （$90$ 分）没有额外的约束条件。对该子任务，令 $m$ 为你在所有场景中给出的排列的最大长度，则你的得分按下表来计算：

|条件|得分|
|:-:|:-:|
|$m\le 90$|$90$|
|$90 < m\le 120$|$90-\dfrac{m-90}{3}$|
|$120 < m\le 5000$|$80-\dfrac{m-120}{65}$|
|$m > 5000$|$0$|


title: [PA2021] Od deski do deski

description:
给定 $n$，$m$，求满足以下限制的长度为 $n$ 的序列数目：

1. 每个元素在 $[1,m]$ 之间；
2. 一次操作定义为删除一个长度至少为 $2$ 且区间两端相等的区间，该序列需要在若干次操作内被删空。

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

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

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


title: [CCC2022 S1]  Good Fours and Good Fives

description:
$\rm Finn$ 非常喜欢 $4$ 和 $5$，他认为所有的数都可以用 $4$ 和 $5$ 进行相加得出。

例：

$14=5+5+4$

$20=4+4+4+4+4$ 或 $20=5+5+5+5$

$40=4+4+4+4+4+4+4+4+4+4$ 或 $40=4+4+4+4+4+5+5+5+5$ 或 $40=5+5+5+5+5+5+5+5$

当然，$4$ 和 $5$ 的顺序并不重要，重要的是他们的个数。

给你一个正整数 $n$，问有多少种方法可以用 $4$ 和 $5$ 拼凑成 $n$。

inputFormat: 一行，一个整数 $n$，表示要被拼凑的数。

outputFormat: 一行，表示方法的数量。如果这个数不能被拼凑，请输出 $0$。

hint:
对于 $20\%$ 的数据：$1\le n\le 10$

对于另外 $15\%$ 的数据：$1\le n\le10^5$ 并且保证
$n\equiv0$ $\pmod 4$

对于另外 $15\%$ 的数据：$1\le n\le10^5$ 并且保证
$n\equiv0$ $\pmod 5$

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


title: [CCC2022 S2] Good Groups

background:
请注意：这道题是 [CCO 2022 J4  Good Groups](https://www.luogu.com.cn/problem/P8403) 的加强版。

管理备注：似乎没有加强。

description:
一个班级会被分成 $g$ 个组，每个组有三个人，这种分组方式可能会违反两种规定：

1. 一些学生必须在同一小组；
2. 一些学生必须不在同一小组。

现在校长找到了你，问学生违反了多少个规定。

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

接下来 $x$ 行，每行两个学生名字 $name1_1,name1_2$ ，表示这两个学生必须被分配到同一个小组。

接下来一个整数 $y$。

接下来 $y$ 行，每行两个学生名字 $name2_1,name2_2$ ，表示这两个学生必须不在同一个小组。

接下来一个整数 $g$。

接下来 $g$ 行，每行三个学生名字 $name3_1,name3_2,name3_3$，表示这三个学生现在被分在一个小组。

outputFormat: 输出一个整数，表示学生违反了多少个规定。

samples:
1
ELODIE CHI
0
2
DWAYNE BEN ANJALI
CHI FRANCOIS ELODIE

samples:
3
A B
G L
J K
2
D F
D G
4
A C G
B D F
E H I
J K L

hint:
### 样例 2 解释：

1. $\rm A$ 和 $\rm B$ 必须在同一组，这一点违反了。
2. $\rm G$ 和 $\rm L$ 必须在同一组，这一点违反了。
3. $\rm J$ 和 $\rm K$ 必须在同一组，这一点没有违反。
4. $\rm D$ 和 $\rm F$ 必须不在同一组，这一点违反了。
5. $\rm D$ 和 $\rm G$ 必须不在同一组，这一点没有被违反。

以上 $5$ 条共违反 $3$ 条，所以输出 $3$。

对于 $20\%$ 的数据：$1\le g\le 50$，$1\le x\le 50$，$y=0$。

对于另外 $35\%$ 的数据：$1\le g\le 50$，$1\le x\le 50$，$1\le y\le 50$。

对于 $100\%$ 的数据：$1\le g\le 10^5$，$1\le x\le 10^5$，$1\le y\le 10^5$。


title: [CCC2022 J4] Good Groups

background:
请注意：这道题是 [CCO 2022 S2  Good Groups](https://www.luogu.com.cn/problem/P8396) 的弱化版

管理备注：似乎没有弱化

description:
一个班级会被分成 $g$ 个组，每个组有三个人，这种分组方式可能会违反两种规定：

1. 一些学生必须在同一小组；
2. 一些学生必须不在同一小组。

现在校长找到了你，问学生一共违反了多少个规定。

inputFormat:
第一行一个整数 $x$。紧接着 $x$ 行，每行两个学生名字 $name_1,name_2$ ，表示这两个学生必须被分配到同一个小组。

接下来一个整数 $y$。紧接着 $y$ 行，每行两个学生名字 $name_1,name_2$ ，表示这两个学生必须不在同一个小组。

接下来一个整数 $g$。紧接着 $g$ 行，每行三个学生名字$name_1,name_2,name_3$，表示这三个学生现在被分在一个小组。

outputFormat: 输出一个整数，表示学生一共违反了多少个规定。

hint:
### 样例2解释：

1. $\rm A$ 和 $\rm B$ 必须在同一组，这一点违反了。
2. $\rm G$ 和 $\rm L$ 必须在同一组，这一点违反了。
3. $\rm J$ 和 $\rm K$ 必须在同一组，这一点没有违反。
4. $\rm D$ 和 $\rm F$ 必须不在同一组，这一点违反了。
5. $\rm D$ 和 $\rm G$ 必须不在同一组，这一点没有被违反。

以上 $5$ 条共违反 $3$ 条，所以输出 $3$。

对于 $25\%$ 的数据：$1\le g\le 50 , 1\le x\le 50,y=0$

对于另外 $60\%$ 的数据：$1\le g\le 50 , 1\le x\le 50,1\le
 y\le 50$

对于 $100\%$ 的数据：$1\le g\le 10^5,1\le x\le 10^5,1\le y\le 10^5$


title: [POI 2003] Smugglers

description: Byteotia 因为它丰富的金矿资源而闻名世界. 所以在和它的邻国 Bitland 的边界上每年都有大量的金矿交易。不幸的是由于税务的繁重，商人带着矿产穿过边境时都要交纳矿产价格的 $50\%$ 作为关税。但是幸运的是，有一些炼金术士已经发明了一些方法能把某一种矿产转化成另一种的矿物。于是这样在交易时就可以先把昂贵的矿产转化成便宜的，等到带过边境以后在转换回来。但是由于这项工作费时费力，炼金术士对于每种转换都要收取相应的费用。现在有个商人想将 $1$ kg 金子带过边境，他想知道最少的花费是多少。

inputFormat:
第一行仅一个数 $n$ 表示有多少种金属矿产。

接下来 $n$ 行，表示每种金属 $1$ kg 的单价。第 $k+1$ 行的数 $p_k$ 为第 $k$ 种金属的单价。我们假设金子的标号为 $1$。接下来一个正数 $m$ 表示一共有 $m$ 种转换方式。接下来 $m$ 行每行描述一个转换，它由三个数 $a$，$b$，$c$ 表示把 $1$ kg 的 $a$ 金属转换为 $1$ kg 的 $b$ 金属需要 $c$ 的代价。对于特定的金属对 $a$ 和 $b$ 最多只会出现一次。

outputFormat: 输出一行，表示把 $1$ kg 的金子带过边境的最小花费。


title: [COI2021] Autobahn

description:
**译自 [COI 2021](https://hsin.hr/coci/archive/2020_2021/) T1「[Autobahn](https://hsin.hr/coci/archive/2020_2021/olympiad_tasks.pdf)」**

有 $N$ 个人在赛车场疾驰，第 $i$ 个人从第 $l_i$ 小时初疾驰到第 $r_i$ 小时末。

鉴于赛车场要恰钱，每疾驰一小时交一块钱，然而这 $N$ 个人都只付了前 $t_i$ 个小时的钱。

管理员十分仁慈，他们只会在有多余 $K$ 个人在赛车场上疾驰时来收额外的钱。

赛车场搞活动，要求划分出一个长为 $X$ 小时的时间段，在这个时间段内如果有人需要被补交钱，则他不需要补交对应时间段欠的钱。

赛车场希望活动使这 $N$ 个人不需要补交的钱最多，求出这个钱数。

inputFormat:
第一行三个整数 $N$，$K$，$X$。

接下来 $N$ 行，一行三个整数 $l_i$，$t_i$，$r_i$。

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


title: [CCC2022 S3] Good Samples

description:
注意：乐谱中的音符就是数字。

我们把子乐谱定义为 “非空的连续音符序列”。也就是说，把一个序列排序去重之后，相邻的两个的值相差 $1$ 。

比如说：
$(3,4,2),(1,2,3,4,2),(4)$ 是 $(1,2,3,4,2)$ 的子乐谱。

注意 $(1,3)$ 不是子乐谱。

如果两个子乐谱在作品中开始或结束的位置不同，我们称之为“不同的子乐谱”。

如果一个子乐谱中任意两个位置的数互不相同，我们称之为“好的子乐谱”。

表演的演奏者非常讨厌，他们对乐谱提出了以下要求：

1. 所有的音符必须低于 $m$ 。
2. 子乐谱中有 $k$ 个好的子乐谱。

现在他们找到了你，问是否能完成这些操作。

inputFormat: 第一行输入三个整数 $n,m,k$ ，具体意义见题目描述。

outputFormat:
一行，$n$ 个整数，表示演奏者想要的乐谱。

如果有一个或多个符合要求的乐谱，请输出字典序最小的一个；如果不能组成演奏这想要的乐谱，则输出 `-1` 。


title: [COI2021] Cigle

description:
**译自 [COI 2021](https://hsin.hr/coci/archive/2020_2021/) T2「[Cigle](https://hsin.hr/coci/archive/2020_2021/olympiad_tasks.pdf)」**

您是一位设计师，现在您正在思考您的下一个设计是什么。

您可以使用 $N$ 块分别长为 $d_i$ 宽为一个单位长度的砖来建造一个多行的砖墙，每行长一个单位长度，具体方式是：

- 首先，从第 $1$ 行，即最底下一行开始，从左到右放置一些砖块。
- 紧接着，在第 $2$ 行，即第 $1$ 行上面一行从右到左放置一些砖块，使得中间一行最右边的砖块与最底下一行最右边的砖块右边边缘对齐。
- 然后，在第 $3$ 行从左到右放置剩下所有的砖块，使得中间一行最左边的砖块与最上面一行最左边的砖块左边边缘对齐。
- 以此类推。

由于砖是神奇的，所以砖可以浮空。

对于一座砖墙，他的美丽度被定义为被四个砖块共顶点的顶点个数。

按砖块的放置顺序给定每块砖的长度，求出最大美丽度。

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

接下来一行 $N$ 个整数 $d_i$。

outputFormat: 输出一行一个整数，表示最大美丽度。


title: [COI2021] Izvanzemaljci

description:
**译自 [COI 2021](https://hsin.hr/coci/archive/2020_2021/) T3「[Izvanzemaljci](https://hsin.hr/coci/archive/2020_2021/olympiad_tasks.pdf)」**

在二维平面上有 $N$ 个整点 $(x_i,y_i)$，请找出 $K$ 个不相交的正方形，使得所有整点在正方形内或在正方形上，如有多解，求出在所有构造方案中面积最大的正方形面积最小的那一种，如果还有多解，输出任意一组即可。

两个正方形如果没有边相交或相碰，并且没有一个正方形完全被另一个正方形包含的情况，则这两个正方形不相交。

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

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

outputFormat:
共 $K$ 行，每行三个整数 $a_i$，$b_i$，$l_i$，表示有一个左下角为 $(a_i,b_i)$，边长为 $l_i$ 的正方形。

您需要保证 $0\le |a_i|,|b_i|\le 3\times 10^9$，$1\le l_i\le 2\times 10^9$。


title: [COI2021] MalnaRISC

description:
**译自 [COI 2021](https://hsin.hr/coci/archive/2020_2021/) T4「[MalnaRISC](https://hsin.hr/coci/archive/2020_2021/olympiad_tasks.pdf)」**

您需要使用 MalnaRISC 这一神奇的处理器来解决知名问题——排序！

MalnaRISC 仅支持一种命令 `CMPSWP` $R_i$ $R_j$，其含义为，比较 $R_i$ 与 $R_j$ 的大小，若 $R_i>R_j$，交换他们。

MalnaRISC 最厉害的是，他可以同时运行多个不同的写在一行的程序，只要他们互不冲突，也就是说，`CMPSWP` 所接参数必须仅在同一行使用一次。

现在，请写一个处理长度为 $N$ 的序列的排序问题（按单调不降的顺序）的 MalnaRISC 程序，我们将根据您的程序长度进行评分。

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

outputFormat:
第一行为一个整数 $t$，表示您的代码长度。

接下来 $t$ 行，每行表示您的一行代码。

samples:
3
CMPSWP R1 R2
CMPSWP R1 R3
CMPSWP R2 R3

samples:
4
CMPSWP R1 R3
CMPSWP R2 R4
CMPSWP R1 R2 CMPSWP R3 R4
CMPSWP R2 R3


title: [CCC2022 S4] Good Triplets

description:
$\rm Andrew$ 是十分好奇的学生，一天他在纸上画了一个圆，圆心在 $(0,0)$ 。设周长为 $C$ ，圆上每一个点的坐标为：

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

现在 $\rm Andrew$ 在圆上画了 $n$ 个点，第 $i$ 的点画在 $p_i$ 上，$\rm Andrew$ 可能在一个位置上画多个点。

现在一个好的三角形 $（a,b,c)$ 的定义为：

- $1\le a<b<c\le n$
- 原点 $（0，0）$ 严格位于顶点在 $p_a$，$P_b$ 和 $p_c$ 的三角形内。特别注意的是，原点不在三角形的周长上。

$\rm Andrew$ 问你有多少个好的三角形。

inputFormat:
第一行两个整数 $n,c$ ，表示点的个数和圆的周长。

接下来一行，有 $n$ 个整数，具体意义见题目描述。

outputFormat: 输出一个整数 $x$ ，表示有 $x$ 个好的三角形。

hint:
样例 $1$ 解释：

$\rm Andrew$ 画了下面的图：

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

原点严格地位于顶点为 $p_1$、$p_2$ 和 $p_5$ 的三角形内，所以 $（1，2，5）$ 是一个好的三角形。其他五个好三联体是$（2，3，6），（2，4，6），（2，5，6），（2，5，7）$ 和$（2，5，8）$。

对于 $20\%$ 的数据：$3\le n\le 200,3\le c\le10^6$

对于另外 $20\%$ 的数据：$3\le n\le 10^6,3\le c\le6000$

对于 $40\%$ 的数据：$3\le n\le 10^6,3\le c\le10^6$ 且所有点的位置互不相同。

对于 $100\%$ 的数据：$3\le n\le 10^6,3\le c\le10^6$


title: [CCC2022  S5] Good Influencers

description:
给定一棵**树**，点 $i$ 的点权是 $c_i$，上面有的点是蓝点 `Y` ，有的点是白点 `N` 。每次操作可以选定一个**蓝**点，将和这个蓝点直接相连的白点染成蓝色，代价是选定的蓝点的点权。

求将整个树染成蓝色的最小代价。

数据保证存在至少一个白点和至少一个蓝点。

inputFormat:
第一行一个整数 $n$ 表示树的大小。

接下来 $n-1$ 行每行两个整数 $a_i$,$b_i$，表示 $a_i$ 和 $b_i$ 直接相连。

接下来一行 $n$ 个字符表示每个点初始颜色。

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

outputFormat: 一行，表示最小花费。


title: [CCC2022 J1] Cupcake Party

description:
幼儿园有 $28$ 个小朋友，因此需要 $28$ 个蛋糕。

一个大盒子可以装 $8$ 块蛋糕，一个小盒子可以装 $3$ 块蛋糕。现在有 $n$ 个大盒子和 $m$ 个小盒子，现在给每个小朋友一块蛋糕，问能剩下几个？

inputFormat: 一行，两个整数 $n,m$ ，具体意义见题目描述。

outputFormat: 一行，表示剩余蛋糕的数量。

hint: 对于全部数据：$0\le n,m\le100$


title: [CCC2022 J2] Fergusonball Ratings

description:
现在有一个球队需要你评价。

球队中的第 $i$ 个人进了 $a_i$ 个球，犯规了 $b_i$ 次。

所以第 $i$ 个人的分数就是 $5\times a_i-3\times b_i$ 。

如果第 $i$ 个人的分数大于 $40$ ，那么这个人就是一个黄金球员。

相对应的，如果这个球队的所有人都是黄金球员，那么这个球队就是一个黄金球队。

inputFormat:
第一行一个整数 $n$ ，表示球队的人数。

接下来 $2n$ 行，第 $2 i - 1$ 行表示 $a_i$，第 $2 i$ 行表示 $b_i$ 。

outputFormat: 共一行，表示黄金球员的数量。如果这是一个黄金球队，请再输出一个 `+` 。

hint: 对于全部数据：$1\le n\le 20,1\le a_i,b_i\le2000$


title: [CCC2022 J3]  Harp Tuning

description:
现在有一个竖琴，像其他乐器一样，它可以走调。

一个有音乐倾向的计算机科学学生写了一个聪明的计算机程序来帮助竖琴调音。

这个程序程序分析了竖琴产生的声音，并提供指令来修复每根失调的弦。

每条指令包括一组琴弦，它们是应该收紧还是松开，以及转多少圈。

例如，单行的 $AFB+8HC-4$ 实际上包含两条调谐指令。

$AFB+8$ 和 $HC-4$。

第一条指令表示竖琴的 $A、F、B$ 弦应收紧 $8$ 圈。

第二条指令表示，竖琴的 $H、C$ 弦应该松开 $4$ 圈。

你的工作是把单行的调音指令，变得更容易阅读。

inputFormat: 一行，输入一个字符串 $s$，具体意义见题目描述。

outputFormat:
输出若干行。

对于每个指令，第一行输出琴弦的大写字母；如果原指令中是 `+`，输出 `tighten`，否则输出 `loosen`；最后输出转数 $x$（用空格间隔开）。

samples:
AFB tighten 8
SC loosen 4
H loosen 2
GDPE tighten 9


title: [CCC2022 J5] Square Pool

description:
罗恩想在他的 $n\times n$ 的正方形院子里建一个正方形游泳池，但他的院子里有 $T$ 棵树。

你的任务是确定他可以建造的最大的方形游泳池的边长。

inputFormat:
第一行一个整数 $n$ ，具体意义见题目描述。

第二行一个整数 $T$ ，具体意义见题目描述。

接下来 $T$ 行，每行两个整数 $x,y$ ，表示在 $(x,y)$ 上有一棵树。

outputFormat: 一行，表示游泳池的最大边长。

hint:
样例 $1$ 解释：

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

样例 $2$ 解释：

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

对于 $20\%$ 的数据：$1\le n\le 50,T=1$

对于 $35\%$ 的数据：$1\le n\le 50,1\le T\le 10$

对于 $25\%$ 的数据：$1\le n\le 5\times 10^5,1\le T\le 10$

对于 $100\%$ 的数据：$1\le n\le 5\times 10^5,1\le T\le 100$


title: 最大公约数和最小公倍数

description: 给定两个正整数 $a,b$，求他们的最大公约数（gcd）和最小公倍数（lcm）。这两个整数均在 int 范围内。

inputFormat: 两个整数 $a$ 和 $b$，用空格分隔。

outputFormat: 两个整数表示答案，用空格隔开。


title: [BalticOI 2022 Day1] Event Hopping

description:
有 $n$ 个区间，第 $i$ 个区间为 $[l_i,r_i]$。

你可以在区间之间跳跃。当你在第 $x$ 个区间上时，你可以跳到一个覆盖右端点 $r_x$ 的区间 $y$ 上，即从 $x$ 能跳到 $y$ 当且仅当 $[r_x \in [l_y,r_y]]$。

有 $q$ 次询问，每次你一开始在第 $s_i$ 个区间，你需要跳到第 $t_i$ 个区间。你需要输出你至少需要跳多少次。如果不能跳到，输出 `impossible`。

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

接下来 $n$ 行，每行两个整数 $l_i$，$r_i$。

接下来 $q$ 行，每行两个整数 $s_i$，$t_i$。

outputFormat: 输出 $q$ 行，第 $i$ 行输出第 $i$ 次询问的答案。如果无解输出 `impossible`。

hint:
- 子任务 $1$ ($10$ 分)：每一个区间可以跳到至多一个其他区间。

- 子任务 $2$ ($10$ 分)：$n≤ 1000$，$q ≤100$。

- 子任务 $3$ ($15$ 分)：$n≤5000$。

- 子任务 $4$ ($15$ 分)：$q ≤100$。

- 子任务 $5$ ($20$ 分)：不存在两个区间 $i,j$ 满足 $[l_i, r_i] \subseteq [l_j,r_j]$。

- 子任务 $6$ ($30$ 分)：没有特殊限制。

对于所有数据，满足 $1≤n,q ≤100000$，$1≤l_i<r_i≤10^9$，$1≤s_i,t_i≤n$。


title: [BalticOI 2022 Day1] Uplifting Excursion

description:
有 $2m+1$ 种物品，重量分别为 $-m,-m+1,\ldots, m-1,m$。重量为 $i$ 的物品有 $a_i$ 个。

你需要拿走若干物品，使得这些物品重量之和恰好为 $l$。在此基础上，你需要拿尽可能多的物品。

问在物品重量之和恰好为 $l$ 的基础上，你最多能拿多少物品。

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

第二行 $2m+1$ 个数，分别为 $a_{-m},a_{-m+1},\ldots, a_{m-1},a_m$。

outputFormat: 一行一个数表示答案。若不存在方案，输出 `impossible`


title: [BalticOI 2022 Day2] Stranded Far From Home

description:
你就是不能放任不管……实际上你进行了闯入行动，并且最初所有事情就像计划一样进行。然而，你和你的助手之间的通讯情况变得十分糟糕（这是符合预期的，不是吗？）你没有安全返回吕贝克，而是被困在一个小岛上，并且你的潜艇没有燃料了。

为了及时返回参加 BOI 的颁奖仪式，你现在必须去岛的另一边坐船。然而，当地居民有着奇怪的传统。领带对他们来说非常重要，每个村庄都有自己喜欢的领带颜色，并且这个颜色可能会随着时间的推移而改变。

一份互联网上的报告显示，不同的村庄最初喜欢不同的领带颜色。不幸的是，这份报告已经相当过时了。从那时起，每个星期都有恰好一个村庄说服一个相邻的村庄喜欢和他们一样的领带颜色（如果两个村庄有公路直接相连，它们就是相邻的）。然而，只有当整个岛上喜欢第一个村庄的领带颜色不比喜欢第二个村庄的领带颜色的人少时，这种情况才会发生。足够长的时间过去了，所以现在所有的岛民都喜欢同样的领带颜色。

你基本可以肯定，如果你不戴符合他们喜好的领带，岛民就不会让你通过。因此，为了去渡口，你计划戴上岛民可能喜欢的每种颜色的领带。然而，戴太多的领带会让你看起来很可疑。编写一个程序，使用对岛屿的描述来计算你必须戴哪些领带。

inputFormat:
第一行包含两个整数 $n$，$m$。$n$ 表示村庄的个数，$m$ 表示岛上道路的条数。村庄从 $1$ 到 $n$ 编号。

接下来一行包含 $n$ 个整数 $s_1,\dots,s_n$，$s_i$ 表示村庄 $i$ 的居民数。

接下来 $m$ 行，每行两个整数 $a$，$b(1\le a,b\le n,a\neq b)$，表示村庄 $a$ 和 $b$ 之间有一条道路。所有村庄通过道路直接或间接相连。

outputFormat: 输出一个长度为 $n$ 的 $01$ 字符串。第 $i$ 位为 $1$ 当且仅当有可能所有的岛民现在都喜欢村庄 $i$ 最初喜欢的领带颜色。

hint:
【样例解释】

样例 #1 解释：

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

【数据范围】

对于所有数据，满足 $1\le n\le 2\times 10^5$，$0\le m \le 2\times 10^5$，$1 \le s_ i\le 10^9$。


title: [BalticOI 2022 Day2] Boarding Passes

description:
在成功遵守当地的风俗之后，你正好赶上了轮船的出发时间。然而，你没有想到会有那么多人前往吕贝克！由于你不想在颁奖仪式上迟到（你还需要一些时间将你所有偷来的艺术品存放在旅店里），你想加快轮船的登船速度。

船上有一排 $n$ 个座位，共 $n$ 名乘客预订了所有座位。每位乘客都有一张船票，上面写着他们的指定座位和 $g$ 个登船组中的一组。

登船时，一次会叫一个组的乘客登船。每个登船组内的乘客将以随机顺序登船，即对于所有可能的登船顺序，出现概率相等。每位乘客可以在第一个座位的前面或最后一个座位的后面登船，然后在另一位乘客登船前移到他们的指定座位。

你确定这个过程中，当一个乘客要经过已经入座的乘客时最耗时（装有所有这些领带的行李在过道上是一个相当大的障碍）。幸运的是，你在附近的储物柜里发现了一件工作人员的制服，所以你可以决定各组乘客的登船顺序，并在登船开始前告诉每位乘客，是要从所有座位的前面还是后面登船。

编写一个程序，利用船票信息计算出在登船过程中，如果你确定了登船组的登船顺序，并将乘客分配到最前面和后面时，一个乘客要经过已经入座的乘客的次数的最小值的期望。

### 注意

给定一个登船组的登船顺序，并将乘客分配到最前面和后面时，一个乘客要经过已经入座的乘客的次数的期望被定义为：
$$1\cdot p_1+2\cdot p_2+3\cdot p_3+\ldots$$
其中 $p_k$ 是登船时一个乘客要经过已经入座的乘客的次数恰好为 $k$ 的概率。换句话说，这是每个登船组中所有可能的乘客登船顺序中一个乘客要经过已经入座的乘客的平均次数。

inputFormat: 输入包含一个由 $n$ 个字符组成的字符串 $s_1 \dots s_n$，其中 $s_i$ 是前 $g$ 个大写英文字母中的一个，表示坐在第  个座位的乘客所属的登船组（最前面的座位为 $1$ 号座位）。

outputFormat:
输出一个实数，表示确定了登船组的登船顺序，并将乘客分配到最前面和后面时，一个乘客要经过已经入座的乘客的次数的最小值的期望。

如果你的输出与答案的绝对误差不大于 $0.001$，则认为你的输出是正确的。

hint: 对于所有数据，满足 $1\le g\le 15$，$1\le n \le 10^5$。


title: 硬币问题

description:
今有面值为 1、5、11 元的硬币各无限枚。

想要凑出 $n$ 元，问需要的最少硬币数量。

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

outputFormat: 仅一行，一个正整数，表示需要的硬币个数。

hint:
#### 样例解释

对于样例数据 1，最佳方案是 $15=5+5+5$，使用到 3 枚硬币。

对于样例数据 2，最佳方案是 $12=11 + 1$，使用到 2 枚硬币。

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $n\leq 10^6$。


title: 文字工作

description:
机器猫要在电脑前打字。一共需要打 $n$ 个字，但现在文档里只有一个字。

机器猫有两种操作可以做。假设现在已经有 $x$ 个字，机器猫可以选择：

- 往文档最后加一个字。字数变成 $x+1$。
- 把文档复制粘贴一遍。字数变成 $2x$。

问机器猫至少需要多少次操作，才能得到恰好 $n$ 个字。

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

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

hint:
#### 样例解释

样例数据1，$1\to 2\to 4\to8\to 16$，共 4 步。

样例数据2，$1\to 2\to 4\to 5$，共 3 步。

#### 数据规模与约定

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


title: [LSOT-1] 记忆崩塌

background:
“铃铃铃”，上课铃打响。一阵眩晕，小 H 突然倒在地上。只是隐约间，感受到周围有人赶过来。

“这是哪里？我不是在上课吗？”小 H 望向周围。

“欢迎来到 OI 世界。我负责带你熟悉 OI 世界。”一个奇怪的人走到这里来。

“OI 世界？”

“对。这里没有文化课，你可以在这里尽情学习 OI。”那人解释道。

紧接着，那人将小 H 带到了一个自称是心理学家的人面前。

“你在干什么？”小 H 望着那个心理学家。他正准备把一个奇怪的东西戴到小 H 头上。

“这个可以帮你恢复你在 whk 世界的记忆。”心理学家淡淡地说。

仪器戴到头上后，小 H 大喊：“我什么都想起来了！”

然而，真的什么都想起来了吗……

从那个人带着小H前往OI世界观光开始，这一切，全都乱了……

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

小 H 失忆了。

现在，小 H 过去的记忆化成了 $n$ 个记忆碎片。医生拥有 $n$ 种长度的取样条（长度为 $1\dots n$）。记忆碎片会与长度为 $i$ 的取样条发生大小为 $\gcd(n,i)$ 的情感共鸣。

医生有一个机器，可以测出长度为 $i$ 的取样条与小 H 产生的情感共鸣大小。现在你可以用这个机器测量一定的次数，医生希望你能告诉他若用完 $n$ 种长度的取样条小 H 总共会发生多大的情感共鸣。

### 交互格式
你可以用以下格式来询问医生你想知道的东西：

`TheSame? m`：下接 $m$ 行，每行两个数 $p_i,k_i$，医生会告诉你数小 H 的记忆碎片数量是否与 $\displaystyle\prod_{i=1}^mp_i^{k_i}$ 相等。`Yes` 代表相同或 `No` 代表不同。

`GetGCD. m`：下接 $m$ 行，每行两个数 $p,k$ ，医生会告诉你$\displaystyle\prod_{i=1}^mp_i^{k_i}$  与小 H 的记忆碎片产生的情感共鸣大小。

所有询问的 $p_i$ 为素数，$k_i$ 为正整数，不符合上述限制的交互不保证交互库会做出预期行为。

***

你可以用以下格式来告诉医生你知道的东西：

`IFoundTheAnswer! m`：以此来告诉评测器我已经知道了小 H 总共产生的情感共鸣大小为 $m$，并评判是否正确。

***

你一共可以与医生交互 $1050$ 次。交互库的所有输出与你输出的答案均应对 $998244353$ 取模。

***

你需要从**标准输出**中输出，代表你询问的内容。

每一次询问后都应当**清空缓冲区**，不然你会无缘无故 TLE。

你可以使用如下语句来清空缓冲区：

- 对于 C/C++：`fflush(stdout)`；
- 对于 C++：`std::cout << std::flush`；
- 对于 Java：`System.out.flush()`；
- 对于 Python：`stdout.flush()`；
- 对于 Pascal：`flush(output)`；
- 对于其他语言，请自行查阅对应语言的帮助文档。

特别的，对于 C++ 语言，在输出换行时如果你使用 `std::endl` 而不是 `'\n'`，也可以自动刷新缓冲区。

然后你需要从**标准输入**中输入，代表评测机返回的结果。

inputFormat: 见「交互格式」。

outputFormat: 见「交互格式」。

samples:
GetGCD. 0
TheSame?  0
GetGCD. 1
2 1
TheSame? 1
2 1
IFoundTheAnswer! 3

hint:
【数据范围】

**「本题采用捆绑测试」**

- $\texttt{Subtask 1(10 pts)：}1 \le\ n\le 500$；
- $\texttt{Subtask 2(25 pts)：}1 \le\ n\le 10^6$；
- $\texttt{Subtask 3(25 pts)：}$保证 $n$ 的唯一分解形式仅有前 $100$ 个质数；
- $\texttt{Subtask 4(40 pts)：}$无特殊限制。

对于 $100\%$ 的数据，满足 $n$ 的唯一分解形式质数数量不超过 $1000$，且质因子最大不超过 $7919$（注：$7919$ 为第 $1000$ 个质数），且质数的次数不超过 $10000$。

【其他提示】

因为交互库的效率较低，所以附件中给出交互库的代码。如果你想利用下面的交互库代码进行调试，你可以在官方的 [SPJ 说明](https://www.luogu.com.cn/blog/luogu/special-judge) 中下载 ```testlib.h``` 头文件后将两个程序的输出输入到另一个程序中。当然，你也可以模拟交互库的计算来手动输入到你的程序中。


title: 最长上升子序列

description:
这是一个简单的动规板子题。

给出一个由 $n(n\le 5000)$ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的**最长上升子序列**的长度。

最长上升子序列是指，从原序列中**按顺序**取出一些数字排在一起，这些数字是**逐渐增大**的。

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

第二行有 $n$ 个整数，表示这个序列。

outputFormat: 一个整数表示答案。


title: 射命丸文的取材之旅

background: 射命丸文（Syameimaru Aya）是一只鸦天狗。她不定期制作名为「文文。新闻」的报纸，而为此，她需要对她收集到的新闻进行剪裁。

description:
射命丸文现在收集到了 $2n$ 条新闻。她想要将其刊登于自己的报刊之上。然而，自己的报刊最多只能刊登 $n$ 条新闻。

为了能在 $n$ 条新闻的篇幅中让自己的报刊得到最大的吸引力，她将这 $2n$ 条新闻**等分**成**两份**，即每一份中均有 $n$ 条新闻。

每一条新闻自然有着其吸引力。在**第一份**中，第 $i$ 条新闻有着吸引力 $a_i$，而在**第二份**中，第 $i$ 条新闻有着吸引力 $b_i$。这两份新闻的划分在输入时已经给定。

现在射命丸文要从中选取新闻放入自己的报刊。报刊上的第 $i$ 条新闻，将选择**第一份**新闻的第 $i$ 条或**第二份**新闻的第 $i$ 条。这样，报刊上的新闻就可以构成一个长度为 $n$ 的序列，第 $i$ 项也就是第 $i$ 条新闻有着吸引力 $c_i \in \{a_i,b_i\}$。

而这样的一份报刊有着其综合影响力。根据射命丸文的经验，对于她这样的一份含有 $n$ 条新闻的报刊，其综合影响力为：

$$\max\{r-l+1-\operatorname{mex}\{c_l,c_{l+1},\dots, c_{r-1},c_r\}\}(1\le l\le r\le n)$$

其中 $\operatorname{mex}\{c_l,c_{l+1},\dots,c_{r-1},c_r\}$ 指的是 $c_l,c_{l+1},\dots,c_{r-1},c_r$ 中没有出现过的**最小非负整数**。

现在她希望知道，在进行这些操作之后，自己的报刊的**最大**的综合影响力会是多少呢？由于她还要继续取材，因此她把这个任务交付给了你。

【形式化题意】

给定序列 $\{a_n\},\{b_n\}$，求一个序列 $\{c_n\}$ 满足 $\forall i\in[1,n],c_i\in\{a_i,b_i\}$，最大化

$$\max\{r-l+1-\operatorname{mex}\{c_l,c_{l+1},\dots, c_{r-1},c_r\}\}(1\le l\le r\le n)$$

并输出该式子可能的最大值。

inputFormat:
第一行一个正整数 $n$，表示**每一份**新闻中的新闻条数。

第二行 $n$ 个**非负整数**表示第一份新闻中每一条新闻的吸引力，即 $a_1,a_2\dots ,a_{n-1},a_n$。

第三行 $n$ 个**非负整数**表示第二份新闻中每一条新闻的吸引力，即 $b_1,b_2\dots ,b_{n-1},b_n$。

outputFormat: 输出一个整数，表示报刊的**最大**的综合影响力会是多少。

hint:
**【样例解释和说明】**

射命丸文可以让自己的 $5$ 条新闻分别取第二份的第 $1$ 条，第一份的第 $2$ 条，第一份的第 $3$ 条，第一份的第 $4$ 条和第二份的第 $5$ 条。这样一来，她的报刊每条新闻的吸引力 $c_i$ 分别为 $0,1,0,1,0$。令 $l=1,r=5$，则 $\operatorname{mex}\{c_1,c_2,c_3,c_4,c_5\}=2$，$r-l+1-\operatorname{mex}\{c_1,c_2,c_3,c_4,c_5\}=3$，不难证明其为数列 $c$ 的综合影响力，也是**所有的可能的** $c$ 的最大综合影响力。

**【数据范围】**

对于 $20\%$ 的数据，满足 $1 \leq n\leq 10$。

另外 $40\%$ 的数据满足 $a_i=b_i$。

对于 $100\%$ 的数据，满足 $1 \leq n\le 10^6$，$0
\leq a_i,b_i\leq n$。


title: 「GMOI R1-T4」Rain

background:
> **求雨**
>
>玉皇爷爷也姓张，
>
>为啥为难俺张*昌？
>
>三天之内不下雨，
>
>先扒龙皇庙，
>
>__再用大炮轰你娘。__

如果再不下雨，张大帅就会轰掉全亚洲所有的宗教场所！

博丽神社因为可以在外界被看到，自然也无法幸免于难，灵梦十分着急，准备使用祖传秘法求雨……

description:
为了防止神社被“大炮开兮轰他娘”，灵梦需要求雨。

求雨需要在一条笔直的路上建 $n$ 个法阵，编号为 $1,2,\cdots,n$。

给定一个长度为 $n$ 的数组 $a$，表示在 $a_1$ 到 $a_n$ 的位置建法阵，你要干的是给法阵编号。

灵梦需要来检测法阵效果，她会从 $1$ 号法阵走到 $2$ 号，从 $2$ 号再走到 $3$ 号，直到走到 $n$ 号，再从 $n$ 号走回 $1$ 号。

由于法阵的特殊效果，从 $i$ 个走到 $i+1$ 个的距离是 $\left|a_i\times p-a_{i+1}\times q\right|$。特别的，从 $n$ 号走回到 $1$ 号的距离是 $\left|a_n\times p-a_1\times q\right|$。$p,q$ 是给定的两个常数，$a_i,a_{i+1}$ 是两个法阵的位置。

灵梦希望你来求一下最大的行走距离，并输出对应法阵从 $1$ 号到 $n$ 号的位置排列。（多个只需输出一个即可）

inputFormat:
第一行一个整数 $n$，表示法阵数量。

第二行两个整数 $p,q$，表示法阵的倍率常量。

第三行 $n$ 个整数，表示数组 $a$。

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

第二行 $n$ 个整数，表示对应位置 $a$ 的排列，按照编号从 $1$ 到 $n$ 输出。


title: [COCI2009-2010#5] CHUCK

description:
给你一个 $R$ 行 $C$ 列的矩阵 $a$，$|a_{i,j}| \le 10^4$。请使用若干次下述操作（次数尽量少），使得矩阵中 $\sum_i \sum_j a_{i,j}$ 尽可能大。

![](https://s1.ax1x.com/2022/06/17/XLkErD.png)

inputFormat:
第一行：$r,c$。
接下来 $r$ 行：矩阵 $a$。

outputFormat:
第一行包含两个整数，第一个整数为 $\sum_i \sum_j a_{i,j}$ 的最大值，第二个数为操作数量 $t$。
接下来 $t$ 行，每行包含一组操作。

hint:
$1 \le R,C \le 100$，$|A_{i,j}|s \le 10^4$

#### 评分标准
若你求了个错误的最大和，或是执行的操作中有无效的，该测试点不得分，否则：

若 $t \le 5 \cdot RC$，你将得到该点的所有分数；

若 $5\cdot RC<T<10^5$，你将得到该点 $50\%$ 的分数；

若 $t > 10^5$，你将得不到该点的任何分数。

本题分值按 COCI 原题设置，满分 $130$。


title: [COCI2009-2010#6] GREMLINI

description:
有 $n$ 种小妖精，我们给这 $n$ 类小妖分别编号为 $1,\dots,n$。

$t$ 年前，一次事故造出了 $n$ 只小妖（视为刚出生的，而非成熟的），这些小妖的种类互不相同。

第 $i$ 种小妖出生后需要 $y_i$ 年成熟，成熟后会立即产下 $k_i$ 个蛋（小妖是无性繁殖的生物）然后死亡。将它的蛋编号为 $1.\dots,k$，其中，第 $j$ 个蛋需要 $h_{i,j}$ 年孵化，孵出的小妖的类型为 $g _ {i, j}$。

请问，现在和祖先关系最远的小妖到了多少代，不考虑暂未孵出的。假设祖先是 $1$ 代，其子辈为第 $2$ 代，孙辈为第 $3$ 代，以此类推。

inputFormat:
第一行：$n,t$。
接下来 $3n$ 行，每三行为一组。

每组的第一行：$k_i,y_i$。
每组的第二行：$g_{ i,1},\ldots,g_{i,k_i}$。
每组的第三行：$h_{ i,1},\ldots,h_{i,k_i}$。

outputFormat: 一行，一个整数，表示现在和祖先关系最远的小妖到了多少代。

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

事故发生 $10$ 年后，最开始的那只小妖（$1$ 代）产下了一个蛋，然后死亡。事故发生 $15$ 年后，蛋孵化出了新的一只小妖（$2$ 代）。事故发生 $25$ 年后，$2$ 代小妖产下了一个蛋，然后死亡。事故发生 $30$ 年后，蛋孵化出了新的一只小妖（$3$ 代）。事故发生 $40$ 年后，$3$ 代小妖产下了一个蛋，然后死亡。事故发生 $42$ 年后，这个蛋仍未孵化，因此不计。

**【数据范围】**

$1 \le n \le 100,1 \le t \le 10^{15},1 \le k_i, y_i, h_{i,j} \le 1000,1 \le g_{i,j} \le n$。

本题分值按 COCI 原题设置，满分 $130$。


title: 「SWTR-8」15B03

background: 15B03 获得了 ION2064 的承办权。

description:
15B03 的座位非常拥挤，可以看成一张 $n\times m$ 的网格，每个小正方形 $(i, j)$ 代表一张桌子。

根据规定，考场上任何两张桌子不得相邻。这里相邻指含有 **公共点**。严格定义两张桌子 $(i, j)$ 和 $(i', j')$ 相邻当且仅当 $|i - i'|\leq 1$ 且 $|j - j'|\leq 1$。

布置考场的任务落在小 A 头上，他希望撤去最少的桌子满足上述要求。

小 A 认为这样太简单了，因此他添加了限制：在保证撤去桌子最少的前提下，最大化剩余每张桌子到距离它最远的桌子的距离之和。这里距离指 **欧几里得** 距离：桌子 $(a, b)$ 和 $(c, d)$ 的距离为 $\sqrt{(a - c) ^ 2 + (b - d) ^ 2}$。

平行时空中 15B03 的规模不尽相同：多组测试数据。

**请选手认真阅读本题的评分方式。**

inputFormat:
第一行一个整数 $S$，表示该测试点的编号。

第二行一个整数 $T$，表示数据组数。接下来 $T$ 组测试数据，每组数据形如：

- 一行两个整数 $n, m$。

outputFormat:
对于每组测试数据：

- 输出一个整数和一个实数，由空格隔开。分别表示最少撤去的桌子数量以及每张桌子到距离它最远的桌子的距离之和的最大值。

实数比较按绝对误差或相对误差不超过 $10 ^ {-9}$：令你输出的答案为 $a$，标准答案为 $b$，你的答案被判为正确当且仅当 $\frac{|a - b|}{\max(1, |b|)} \leq 10 ^ {-9}$。

hint:
**「样例解释」**

对于第一组询问，选择 $(1, 1), (1, 3), (3, 1)$ 和 $(3, 3)$ 最优。撤去了 $3\times 3 - 4 = 5$ 张桌子，且每张桌子到距离它最远的桌子的距离均为 $\sqrt{2 ^ 2 + 2 ^ 2} = 2\sqrt 2$，因此第二问答案为 $8\sqrt 2$。如下图所示：

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

对于第二组询问，选择 $(1, 1)$ 和 $(2, 4)$ 最优。撤去了 $2\times 4 - 2 = 6$ 张桌子，且每张桌子到距离它最远的桌子的距离均为 $\sqrt{1 ^ 2 + 3 ^ 2} = \sqrt {10}$，因此第二问答案为 $2\sqrt {10}$。

如果选择 $(1, 1)$ 和 $(2, 3)$，则第二问答案为 $2\sqrt 5$，不优。

**「评分方式」**

对于每组测试数据：

- 若你第一问的答案错误，得 0 分。
- 否则，若你第二问的答案错误，得 0.8 分。
- 否则，得 1 分。

每个测试点的得分为测试点内所有测试数据的得分的最小值乘以该测试点的分值。

注意，**若你输出的格式错误，得 0 分**。因此，如果你只希望获得第一问的分数，请在第二问输出任意合理范围内的实数。

**「数据范围与约定」**

- 测试点 #1（15 points）：$n, m$ 均为奇数。
- 测试点 #2（20 points）：$n = 1$。
- 测试点 #3（25 points）：$n = 2$。
- 测试点 #4（30 points）：$n$ 为奇数。
- 测试点 #5（10 points）：无特殊限制。

对于 $100\%$ 的数据：

- $1\leq T\leq 57$。
- $1\leq n, m\leq 1064$。

**「帮助与提示」**

- 你可以使用 `cmath` 中的 `sqrt(x)` 函数计算 $x$ 的平方根。它返回 `double` 类型的值。`sqrtl(x)` 精度更高，它返回 `long double` 类型的值。

**「题目来源」**

- [Sweet Round 8](https://www.luogu.com.cn/contest/73382) A
- Idea & Solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。
- Tester：[chenxia25](https://www.luogu.com.cn/user/138400)。


title: 「SWTR-8」地地铁铁

background: D_T_ : D_tt : ddT_ : ddtt = 9 : 3 : 3 : 1.

description:
给定一张 $n$ 个点，$m$ 条边的无向连通图。每条边标有 `D` 或 `d`。

定义无序点对 $(x, y)$ 是「[铁的](https://loj.ac/p/3398)」，当且仅当 $x \neq y$ 且 $x, y$ 之间存在同时出现 `D` 和 `d` 的简单路径。

小 A 深知自由组合定律 DdTt 的重要性，所以他让你对这样的点对计数。

注意：

- 简单路径定义为不经过重复 **节点** 的路径。
- 保证图无自环，可能有重边。

inputFormat:
第一行一个整数 $S$，表示该测试点的 Subtask 编号。

第二行两个整数 $n, m$。

接下来 $m$ 行，每行两个整数 $x, y$ 以及字母 $c$，表示一条连接 $x, y$ 且标有 $c$ 的无向边。

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

hint:
**「数据范围与约定」**

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

- Subtask #1（6 points）：$n \leq 8$，$m \leq 20$。
- Subtask #2（16 points）：$n\leq 15$，$m\leq 822$。依赖 Subtask #1。
- Subtask #3（17 points）：$m = n - 1$。
- Subtask #4（18 points）：$m = n$。
- Subtask #5（19 points）：$n\leq 1064$，$m\leq 10 ^ 4$。依赖 Subtask #2。
- Subtask #6（24 points）：无特殊限制。依赖 Subtask #3，#4，#5。

对于 $100\%$ 的数据：

- $2\leq n \leq 4\times 10 ^ 5$，$n - 1\leq m\leq  10 ^ 6$。
- $1\leq x, y\leq n$。
- $c\in \{\texttt{D}, \texttt{d}\}$。
- 保证图无自环，可能有重边。

**「帮助与提示」**

请注意 IO 优化。

**「题目来源」**

- [Sweet Round 8](https://www.luogu.com.cn/contest/73382) E
- Idea & Solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。
- Tester：[asmend](https://www.luogu.com.cn/user/21658)。


title: 「SWTR-8」幂塔方程

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

图片来自于 Solara570 的 B 站视频 [轻易相信简单直观的结论究竟有多危险？](https://www.bilibili.com/video/BV1PW41177Vb)。

很久以前的某一天，小 A 在 B 站上无意间刷到了这个视频。视频中的无穷幂塔方程及其「简单直观，但暗藏陷阱」的解法令他影响深刻。
$$
\Huge x ^ {x ^ {x ^ {x ^ {x}}}}
$$

description:
如果小 A 是一个，一个一个一个毒瘤，他会让你求解套了十层甚至九层的幂塔方程，但他不是。

他想让你求解：
$$
x ^ x\equiv D \pmod n
$$

保证 $n$ 的最大质因子不超过 $10 ^ 5$，且 $D$ 与 $n$ 互质。

你需要保证得到的解 $x$ 为 $[0, 2 ^ {125}]$ 范围内的整数。若该范围内无解，输出 $-1$；若存在多解，输出任意一个。

多组测试数据。

inputFormat:
第一行一个整数 $S$，表示该测试点的 Subtask 编号。

第二行一个整数 $T$，表示数据组数。接下来 $T$ 组测试数据，每组数据形如：

- 第一行两个整数 $n, D$。
- 第二行若干递增的质数 $p_1, p_2, \cdots, p_k$，表示 $n$ 的所有质因子。

hint:
**「数据范围与约定」**

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

- Subtask #1（5 points）：$n\leq 20$。
- Subtask #2（8 points）：$n\leq 400$。依赖 Subtask #1。
- Subtask #3（11 points）：$n$ 是质数，$T\leq 10 ^ 4$。
- Subtask #4（15 points）：$\mu(n) \neq 0$，$T\leq 100$。
- Subtask #5（9 points）：$\mu(n) \neq 0$，$T\leq 10 ^ 4$。依赖 Subtask #4。
- Subtask #6（13 points）：$n = p ^ k(p \in \mathrm{prime})$，$T\leq 100$。
- Subtask #7（7 points）：$n = p ^ k(p \in \mathrm{prime})$，$T\leq 10 ^ 4$。依赖 Subtask #3，#6。
- Subtask #8（6 points）：$n$ 的最大质因子不超过 $ 1064$。依赖 Subtask #2。
- Subtask #9（16 points）：$n\leq 10 ^ 9$，$T\leq 10 ^ 4$。
- Subtask #10（10 points）：无特殊限制。依赖 Subtask #5，#7，#8，#9。

对于 $100\%$ 的数据：

- $1\leq T\leq 4\times 10 ^ 4$。
- $2\leq n \leq 10 ^ {18}$。
- $1\leq D < n$，$D\perp n$。
- $2\leq p_1 < p_2 < \cdots < p_k \leq 10 ^ 5$。

**「帮助与提示」**

选手可以通过边读入边试除的方式判断何时停止读入 $n$ 的质因子。

**「题目来源」**

- [Sweet Round 8](https://www.luogu.com.cn/contest/73382) F
- Idea & Solution：[demonlover923](https://www.luogu.com.cn/user/152997) & [codecode](https://www.luogu.com.cn/user/119526)。
- Tester：[Alex_Wei](https://www.luogu.com.cn/user/123294)。

tags: 扩展欧几里德算法,exgcd


title: [LSOT-1] 暴龙的土豆

background: 暴龙爱吃土豆。

description:
给定一个正整数 $n$。

每次操作可以选两个素数 $y,z$，其中要求 $z$ 是奇素数。

令 $x=y^z$，如果 $x$ 能除尽 $n$ 则计为一次有效操作，$n$ 变为 $\dfrac nx$。

现在需要你回答，对于 $n$ 最多能够进行多少次有效操作。

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

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

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

outputFormat: 对于每组数据，输出答案。

hint:
【样例解释】

对于样例一：$16$ 可以变成 $2^3 \times 2$，可以进行一次操作。但是 $9$ 只能变成 $3^2$，所以不能进行操作。

【数据范围】

**「本题采用捆绑测试」**

- $\texttt{Subtask 1(10 pts)：}1 \le\ n\le 10^2，1 \le\ T\le 10^2$；
- $\texttt{Subtask 2(20 pts)：}1 \le\ n\le 10^6，1 \le\ T\le 10^2$；
- $\texttt{Subtask 3(30 pts)：}1 \le\ n\le 10^{12}，1 \le\ T\le 10^2$；
- $\texttt{Subtask 4(40 pts)：}$无特殊限制。

对于 $100\%$ 的数据，满足 $1\le n\le 10^{18}$，$1\le T\le 10^2$。


title: 『MdOI R5』Squares

background:
本题不是数据结构题，建议先做 F。

[![1.gif](https://i.postimg.cc/7ZV6xBX6/1.gif)](https://postimg.cc/HrrHz9qD)

description:
给定平面上的 $n$ 个点，定义平面上的一个区域是好的当且仅当它是一个**边与坐标轴平行的正方形**并且不存在任何一个给定的点被它**严格包含**。再给定 $m$ 次询问，每次给出一个点 $(x,y)$，求出**严格包含** $(x,y)$ 的最大的好区域的边长。如果可以无限大则输出 $-1$。

点 $A$ 被区域 $B$ **严格包含**当且仅当 $A$ 在 $B$ 的内部且不在边界上。

为了减少奇奇怪怪的细节，我们保证所有的 $n+m$ 个点都满足横坐标互不相同，纵坐标互不相同。

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

接下来 $n$ 行，每行两个整数 $x,y$，表示一个给定的点 $(x,y)$。

接下来 $m$ 行，每行两个整数 $x,y$，表示一组询问中给定的点 $(x,y)$。

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

hint:
对于 $100\%$ 的数据，$1\le n,m\le 3\times 10^5$，$0\le x,y\le 10^8$。

$\operatorname{Subtask} 1(10\%)$：$n,m\le 10$。

$\operatorname{Subtask} 2(10\%)$：$n,m\le 100$。

$\operatorname{Subtask} 3(20\%)$：$n,m\le 10^3$。

$\operatorname{Subtask} 4(20\%)$：$n,m\le 5\times 10^4$。

$\operatorname{Subtask} 5(20\%)$：$n,m\le 10^5$。

$\operatorname{Subtask} 6(20\%)$：无特殊限制。

#### 样例说明 1

对于第一组询问，左下角为 $(0,0)$，边长为 $4$ 的正方形是严格包含 $(2,2)$ 的好区域中边长最大的。

对于第二组询问，左下角为 $(4,4)$，边长为 $+\infty$ 的正方形是严格包含 $(5,5)$ 的好区域中边长最大的。


title: [THUPC2022 决赛] 简单的卡牌游戏

description:
Alice 和 Bob 最近玩了很多复杂的游戏，于是他们想玩点简单的游戏放松一下。

他们想起来有一种非常简单的游戏叫“憋七”，这种游戏只需要一副扑克牌就能玩。传统的“憋七”玩法稍微有点复杂，所以 Alice 和 Bob 打算玩一种简化版的“憋七”。

在游戏中用到的扑克牌包括黑桃（Spades）、红桃（Hearts）、梅花（Clubs）和方块（Diamonds）四种花色，每种花色的 1 点至 13 点各 1 张，共计 52 张牌。

简化版的游戏规则如下：

1. 首先将一副 52 张的扑克牌平均分成两份，每份各 26 张，Alice 和 Bob 各拿一张；

2. 拥有黑桃 7 的一方将手中的黑桃 7 置于场上；

3. 接着，从另外一方开始轮流操作，每一轮玩家需要从自己持有的牌中挑选一张置于场上，可以打出的牌需要满足以下两个条件之一：

   - 这张牌的点数为 7；

   - 当前场上的牌中，有一张牌与将要打出的牌花色相同，点数恰好差 1。

4. 如果当前进行操作的玩家不能按照规则打出一张牌，则判该玩家负，另一位玩家胜；否则，如果双方都打出了手上的所有牌，则判平局。

由于该游戏中不同花色的接龙是独立的，游戏时玩家常常将不同花色的 7 对成一竖排列，并在 7 的两侧接龙，将同花色的牌排成一行。

已知 Alice 和 Bob 都足够聪明。现在给出 Alice 和 Bob 的初始手牌，请计算当二人都按最优策略出牌时，游戏的结果。

inputFormat:
由于可以从一个人的手牌推断出另一个人的手牌，因此输入仅包含 Alice 的所有手牌。

输入仅一行，包括 26 个用空格隔开的字符串，每个字符串表示 Alice 手上的一张牌。

每张牌的输入格式为 花色 + 点数。其中，花色由一个字符表示，`S` 表示黑桃，`H` 表示红桃，`C` 表示梅花，`D` 表示方块；点数由对应的一位或两位的数字表示，数字最小为 `1`，最大为 `13`，均不含前导 0。例如，黑桃 7 对应字符串 `S7`。

outputFormat: 输出仅一行，包括一个字符串，表示游戏的结果。如果 Alice 能赢得这局游戏则输出 `Alice`；如果 `Bob` 能赢得这局游戏则输出 `Bob`；如果平局则输出 `Draw`。

hint: 对于 $100\%$ 的数据，保证输入的牌符合输入格式中描述的格式，且输入的 26 张牌各不相同。


title: [THUPC2022 决赛] pmrmscxip

description:
给序列 $a_1,\dots,a_n$ 和排列 $b_1,\dots,b_n$，共有 $m$ 次操作：

修改操作：给定 $x,y$，将 $a_x$ 改为 $y$；

查询操作：给定 $l,r,x$，查区间 $[l,r]$ 内最长的子区间 $[l',r']$（即满足 $l\le l'\le r'\le r$），使得对 $l'\le i<r'$ 有 $a_{i+1}=b_{a_i}$，且存在 $l'\le i\le r'$ 使得 $a_i=x$。需要输出满足条件的 $r'-l'+1$ 的最大值，若不存在则输出 $0$。

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

第二行 $n$ 个整数依次表示 $a_1,\dots,a_n$；

第三行 $n$ 个整数依次表示 $b_1,\dots,b_n$；

接下来 $m$ 行，每行 $1,x,y$ 或 $2,l,r,x$ 表示进行一次修改操作或查询操作。

输入的所有数值为整数。

outputFormat: 对每个查询操作，输出一行，表示相应的答案。

hint:
$1\le n,m\le 10^6$；

$1\le a_i\le n$；

$1\le b_i\le n$，$b_i$ 互不相同；

对修改操作，满足 $1\le x,y\le n$；

对查询操作，满足 $1\le l\le r\le n$，$1\le x\le n$。


title: [THUPC2022 决赛] 拯救还是毁灭

description:
*有人说，它拯救了世界；也有人说，它毁灭了世界。*

这个世界危在旦夕！秩序已然一片混乱。

秩序可以抽象成一个 $n\times n$ 的矩阵，矩阵中是一个 $1\sim n^2$ 的排列。你想要拯救世界，于是请来了神，来帮忙把秩序恢复原状。然而神也不是万能的，它只能做到交换矩阵中同一行或者同一列中的两个数。而且，它并不知道要怎么交换才能复原，得听你的指导。

幸好，你不一定需要在最少的交换次数之内完成复原。你只需要不比最糟糕的情况差就好。也就是说，如果你的交换次数为 $k$，且对于所有 $1\sim n^2$ 的排列，最小交换次数的最大值为 $k_0$，你只需要满足 $k\le k_0$。

注：复原指的是将矩阵变为如下的一个矩阵：

$\begin{matrix} 1 & 2 & 3 & \cdots & n \\ n+1 & n+2 & n+3 & \cdots & 2n \\ 2n+1 & 2n+2 & 2n+3 & \cdots & 3n\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ (n-1)n+1 & (n-1)n+2 & (n-1)n+3 & \cdots & n^2 \end{matrix}$

inputFormat: 接下来 $n$ 行，每行 $n$ 个正整数，表示这个 $n\times n$ 的矩阵。保证 $1\sim n^2$ 中的每个数恰好出现一次。

outputFormat:
第一行一个非负整数 $k$，表示你的交换次数。

接下来 $k$ 行，每行四个正整数 $x_1,y_1,x_2,y_2$，表示将第 $x_1$ 行 $y_1$ 列的数与第 $x_2$ 行 $y_2$ 列的数交换。

你需要保证 $x_1=x_2$ 或 $y_1=y_2$。

hint:
【样例 1 解释】

可以证明这是交换次数最少的方案之一，显然它符合条件。

【样例 2 解释】

对于这个输入来说，这个样例输出的方案不是交换次数最少的方案，但是我们知道存在一个 $1\sim n^2$ 的排列（即上一个样例）需要至少 $3$ 次的交换，所以这个方案也是可行的。

【样例 3 解释】

我们允许出现 $(x_1,y_1)=(x_2,y_2)$ 的情况。

【样例 4 解释】

注意 $k$ 可以等于 $0$。

【数据范围与约定】

保证 $1\le n\le 1000$。

保证输入的矩阵中 $1\sim n^2$ 恰好各出现一次。


title: [THUPC2022 决赛] 高性能计算导论集群登录密码复杂性策略

background: 高性能计算导论是 T 大学 C 系开设的一门专业选修课。这门课程讲述了高性能计算的基本概念和原理，常见并行编程模型及并行程序的基本编写思路，程序性能分析和优化的基本方法，以及计算机体系结构和程序性能的关系。为了让同学们能够实际体验并行程序的编写、性能分析和优化，课程为同学们提供了五台服务器组成的集群，每台服务器上都配置了 2 socket × 14 core 的处理器和 1 块 GPU。选课的同学可以在集群上进行基于消息传递的并行编程、基于共享内存模型的并行编程和 CUDA 编程。为了防止宝贵的计算资源被滥用（比如偷偷用服务器挖矿），课程在集群使用上有很多的规定，其中就包括要求选课同学使用高强度的集群登录密码。

description:
为了确保选课同学使用了较强的集群登录密码，课程组在集群上配置了密码复杂性策略。所有选课的同学在学期初会收到随机生成的初始密码。在使用初始密码登录集群后，集群会要求同学输入新的密码，密码更改完毕后才能正常访问集群。在本题中，我们假设密码复杂性策略为：

- 密码至少包含 $L$ 个字符，且至少包含一个数字和一个字母；

- 密码不能包含**连续** $A$ 个**重复**字符，如 `2333` 包含了连续 3 个重复字符；

- 密码不能包含**连续** $B$ 个字符组成的上升序列或下降序列，其中定义上升序列为 `0123456789`，`ABCDEFGHIJKLMNOPQRSTUVWXYZ` 和 `abcdefghijklmnopqrstuvwxyz` 三个字符串中某一个串的**连续**子串，下降序列为这三个字符串中某一个串的**连续**子串的反向串，例如：

  - `6789` 是长度为 4 的上升序列，`FED` 是长度为 3 的下降序列；

  - `90`、`AZ`、`az` 不是上升序列或下降序列；

  - `GPU` 不是上升序列，因为它不连续；

  - `Def` 不是上升序列，因为字母大小写不一致（但它包含长度为 2 的上升连续子序列 `ef`）；

  - `1112345678999` 不是上升序列，但它的子序列 `123456789` 是上升的。

假设密码仅由数字及大小写字母构成。求在长度不超过 $R$ 的所有密码中，有多少个密码满足密码复杂性策略。

inputFormat: 输入仅一行，包括四个正整数 $L, R, A, B$，含义如题目描述中所述。

outputFormat: 输出一个非负整数，表示满足密码复杂性策略且长度不超过 $R$ 的密码数量对 $1,000,000,007$ 取模的结果。

hint:
【样例 1 解释】

因为密码必须至少包含一个数字和一个字母，所以满足要求的密码有 $2\times 10 \times (26\times 2) = 1040$ 种。

【数据范围与约定】

保证 $1\le L\le R\le 10^9$，$2\le A\le 6$，$2\le B\le 26$。

【提示】

如果你不想记住又长又复杂的密码，不想每次登录时手动输入密码，也可以配置公钥进行 SSH 登录。


title: [THUPC2022 决赛] 倍增路径

description:
对于任意一张 DAG $G=(V,E)$ 和图中的一个起始点 $s_1\in V$，倍增小游戏的规则为：

- 在第 $i$ 轮操作（$i=1,2,\cdots$）中，玩家选取一条起点为 $s_i$ 的**非空**路径 $p_i$，使得所有属于这条路径的边的边权和恰为 $(i+1)$ 的倍数。如果无法选择出满足倍数要求的路径，则称游戏失败，玩家将不会获得任何分数；否则，本轮操作成功，并记 $p_i$ 的终点为 $s_{i+1}$。

- 在第 $i$ 轮操作成功后，玩家可以选择结束游戏或者继续第 $(i+1)$ 轮操作。如果选择结束游戏，则称选择出的 $i$ 条路径 $p_1, \cdots, p_i$ 为倍增路径，并计算得分。

如果游戏没有失败，则在结束游戏时，对于选出的倍增路径 $p_1, \cdots, p_k$，定义游戏的分数为 $\sum_{i=1}^k a_i \left|p_i\right|/k$，其中 $|p_i|$ 表示路径 $p_i$ 包含的边数，$a_i$ 是输入给定的权值。显然，无论如何选取路径，最多也只能选出 $(n-1)$ 条路径，因此输入中只给出了 $a_1, \cdots, a_{n-1}$。

为了设置每张图的通关要求，请对给出的 DAG 和起始点，计算该游戏的最大分数。

inputFormat:
输入的第一行包含三个由空格隔开的正整数 $n$，$m$，$s_1$，表示给出的图中点的数量、边的数量及起始点的编号。保证 $2\le n \le 100$，$1\le m\le \frac{n(n-1)}{2}$，$1\le s_1\le n$。

输入的第二行包含 $(n-1)$ 个由空格隔开的正整数 $a_1, \cdots, a_{n-1}$，表示计算分数时的权重。保证 $1\le a_1\le a_2\le\cdots\le a_{n-1}\le 10^9$。

接下来 $m$ 行，每行输入三个由空格隔开的正整数 $u_i, v_i, w_i$，描述图中一条由 $u_i$ 连向 $v_i$，权值为 $w_i$ 的单向边。保证 $1\le u_i, v_i\le n$，$u_i\ne v_i$，$1\le w_i\le 10^9$，图是连通的且没有重边。

outputFormat:
输出仅一行，包括两个整数，由空格隔开。

如果可以选出至少一条路径，则存在一种最优的选取方案使得分数最大，记这个最优分数的最简分数表示为 $p/q$（当最优分数恰为整数时认为 $q=1$），则输出 $p$，$q$。否则，如果无论如何选取都无法选取出至少一条路径，则输出 `-1 -1`。

hint:
【样例 1 解释】

选出的倍增路径为 $p_1 = ((1, 2)), p_2 = ((2, 5))$。

【数据范围与约定】

对于 $100\%$ 的数据，保证 $2\le n\le 100$，$1\le m\le \frac{n(n-1)}{2}$，$1\le s_1, u_i, v_i\le n$，$1\le a_1 \le \cdots\le a_{n-1}\le 10^9$，$1\le w_i\le 10^9$，输入的图是连通的且没有重边。


title: [THUPC2022 决赛] riapq

description:
给出排列 $a_1,\dots,a_n$，你需要维护序列 $b_1,\dots,b_n$，初值为0。

共 $m$ 次操作：

修改操作：给出 $l,r$，对每个 $(i,j)$ 满足 $l\le i\le j\le r,\;a_i\le a_j$，将 $b_j$ 增加1；

查询操作：给出 $x$，查 $b_x$。

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

第二行 $n$ 个整数依次表示 $a_1,\dots,a_n$；

接下来 $m$ 行，每行 $1,l,r$ 或 $2,x$ 表示修改操作或查询操作。

输入的所有数值为整数。

outputFormat: 对每个查询操作，输出一行，包含一个整数，表示答案。

hint:
$1\le n,m\le 2\times 10^5$；

$1\le a_i\le n$，$a_i$ 互不相同；

$1\le l\le r\le n$；

$1\le x\le n$。


title: [THUPC2022 决赛] 匹配

description: 定义“匹配项”是一个长度为 $L$ 的字符串，每一位要么是 0，要么是 1。现在有 $N$ 个这样的“匹配项”，我们希望设计一个“方案”，“方案”同样是长度为$L$的字符串，每一位要么是 0，要么是 1。定义每个“匹配项”的错误值为“方案”与“匹配项”不同位的个数，比如“匹配项”是 `101`，“方案”是 `000`，那么两者的第一位和第三位是不同的，所以该“方案”对于该“匹配项”的错误值为 2。我们希望找到一个“方案”，使得这 $N$ 个“匹配项”的错误值之和最小。此外，有 $M$ 个互不相同的禁用“方案”，我们要求找到的“方案”不能是禁用“方案”之一。

inputFormat:
输入的第一行包含三个正整数 $N,M,L$。

接下来输入 $N$ 行,每行为一个长度为 $L$ 的字符串，之后 $M$ 行，每行为一个长度为 $L$ 的字符串。

outputFormat: 输出一个整数，表示满足要求的“方案”得到的这$N$个“匹配项”的最小错误值之和。


title: [THUPC2022 决赛] rsraogps

description:
给序列 $a_1,\dots,a_n$，$b_1,\dots,b_n$，$c_1,\dots,c_n$，

定义区间 $[l,r]$ 的价值为 $a_l,\dots,a_r$ 按位与，$b_l,\dots,b_r$ 按位或，$c_l,\dots,c_r$ 的最大公因数，这三者的乘积；

$m$ 次查询，每次查询给出区间 $[l,r]$，查询满足 $l\le l'\le r'\le r$ 的 $[l',r']$ 的价值之和。

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

第二行 $n$ 个整数 $a_1,\dots,a_n$；

第三行 $n$ 个整数 $b_1,\dots,b_n$；

第四行 $n$ 个整数 $c_1,\dots,c_n$；

接下来 $m$ 行，每行两个整数 $l,r$ 表示一次查询。

outputFormat: 共 $m$ 行，每行一个整数，表示对应的答案，答案对 $2^{32}$ 取模后输出。

hint:
$1\le n\le 10^6$

$1\le m\le 5\times 10^6$

$1\le a_i,b_i,c_i\le n$

$1\le l\le r\le n$

建议使用高效的输入输出方式。


title: [THUPC2022 决赛] 德州消消乐

background:
众所周知小 c 是开心消消乐的高手，而小 z 玩这种稍微需要动一点脑子的游戏都很不在行。正值五一假期，小 c 闲得无聊就打算来教小 z。

经过五天五夜不间断教学，小 z 终于领悟了一点门道（小 z 内心 os：但凡能拿出一点热情来学概率论……），然而他俩都忽略了这玩意是会玩上瘾的，更关键的是小 z 来自山东，于是他打算融入一点家乡特色……

小 z：”……众所周知德州在山东，那我们就叫它‘德州消消乐’吧！“

小 c 连忙制止道你快算了吧，上次的大杂糅棋局你忘了？再说此德州非彼德州啊喂，这次你要搞就自己搞吧别拉我下水了。

话还没说完，小 z 转手把规则甩给了小 c。

小 c：“真香”。

description:
给定大小为 $n \times m$ 的棋盘，记左上角坐标为 $(1,1)$ ，右下角坐标为 $(n,m)$ 。有不同颜色的棋子共 $k$ 种，颜色编号为 $1\sim k$ 。最初每个格子都有一个棋子。

共有 $q$ 次操作，每次操作形如交换相邻（在上、下、左、右方向）的两个棋子。在此之后，在同一行或同一列的连续至少 $3$ 个相同颜色的棋子会被消除。

消除后，所有棋子会遵循重力下落，这一列的最上方变成空位。所有棋子下落完成后，如果又产生了能消除的情况，则会触发连锁反应继续消除，直到无法消除为止。称一次消除+一次下落为“一轮消除”，由此可以定义一次操作触发的消除“轮数”。

其中，有些棋子具有特殊属性，被消除时会触发特殊效果，一共有以下 $6$ 类：

- 1、消除时将同一行的全部棋子消除；
- 2、消除时将同一列的全部棋子消除；
- 3、消除时将同一行和同一列的全部棋子消除；
- 4、消除时将以之为中心 $3 \times 3$ 的正方形范围内的棋子全部消除；
- 5、消除时将以之为中心 $5 \times 5$ 的正方形范围内的棋子全部消除；
- 6、消除时将与之颜色相同的棋子全部消除；

触发一个棋子的特殊效果时可能连锁触发其他棋子的特殊效果，但是这些都是在同一轮消除内触发的（即连锁反应触发的过程中不会引起下落）。

游戏中，每次操作都要求必须有效，即操作的两个位置相邻且均不为空位，且在操作之后能进行棋子的消除。若某此操作并非有效，则直接跳过这一次操作。所有 $q$ 次操作结束后游戏结束。

定义一次有效操作的“主颜色”为通过交换而直接被消除的颜色（即不包括特殊效果触发和下落引起的消除），容易发现一次有效操作的主颜色至少有 $1$ 种，最多有 $2$ 种。

游戏中，玩家要通过操作来获取尽可能多的得分。得分的规则有如下 $5$ 种：消除奖分+连锁奖分+组合奖分+牌型奖分+终局奖分。

- 消除奖分：每次有效操作中，第 $i$ 轮消除的消除奖分为这一轮中所有被消除的棋子的颜色编号之和的 $i$ 倍。
- 连锁奖分：设某次有效操作的总消除轮数为 $x$ ，则有连锁奖分 $80(x-1)^2$ 。
- 组合奖分：某一轮消除中，在仅考虑由“同一行或同一列至少连续 $3$ 个相同颜色”引发的消除的情况下（即不考虑所有特殊效果引起的消除），设某个被消除的同色四连通块大小为 $x$ ，则有组合奖分 $50(x-3)^2$ 。如： $4$ 个同色棋子组成四连的组合奖分为 $50$ ，$5$ 个同色棋子组成五连、十字或T字等形状的组合奖分为 $200$ ，$2\times3$ 的方形同色棋子的组合奖分为 $450$ 。
 - 牌型奖分：每 $5$ 次有效操作计算一次牌型奖分，取之前 $5$ 次有效操作的主颜色（若某次操作有多个主颜色，取能按照以下规则计算出的最大奖分的主颜色），按照如下牌型规则计算奖分：

   - 高牌： $5$ 种颜色全部不同，奖 $50$ 分 + 所有牌中最大的颜色编号；
   - 一对： $2$ 个相同颜色 + $3$ 个不同颜色，奖 $100$ 分 + 一对的颜色编号 $\times 2$ ；

   - 两对： $2$ 对相同颜色 + $1$ 个其他颜色，奖 $200$ 分 + 两对中较大的颜色编号 $\times 2$ + 两对中较小的颜色编号；
   - 三条： $3$ 个相同颜色 + $2$ 个不同颜色，奖 $300$ 分 + 三条的颜色编号 $\times 3$ ；
   - 葫芦： $3$ 个相同颜色 + 另外 $2$ 个相同颜色，奖 $500$ 分 + 三个相同的颜色编号 $\times 3$ + 两个相同的颜色编号；
   - 四条： $4$ 个相同颜色 + $1$ 个其他颜色，奖 $750$ 分 + 四条的颜色编号 $\times 5$ ；
   - 五条： $5$ 个颜色全部相同，奖 $1000$ 分 + 五条的颜色编号 $\times 10$ 。
 - 终局奖分：若所有 $q$ 次操作均有效，在终局时额外获得 $1000$ 分终局奖分；若游戏结束时棋盘被全部清空，额外获得 $10000$ 分的终局奖分。

给定一局游戏的初始局面和玩家的每一次操作，你需要计算玩家的总得分。

inputFormat:
第 $1$ 行： $4$ 个正整数 $n,m,k,q$ 。

接下来 $n$ 行，每行 $m$ 个正整数 $a_{i,j}$ ，表示初始状态下，从上往下第 $i$ 行、从左往右第 $j$ 列的棋子的颜色。

接下来 $n$ 行，每行 $m$ 个非负整数 $b_{i,j}$ ，表示初始状态下，从上往下第 $i$ 行、从左往右第 $j$ 列的棋子的特殊效果，含义如题面所述。特别地， $b_{i,j}=0$ 表示没有特殊效果。

接下来 $q$ 行，每行 $4$ 个正整数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$ ，表示交换坐标 $(x_{i,1},y_{i,1})$ 和 $(x_{i,2},y_{i,2})$ 位置的棋子。

outputFormat: 输出一行，一个非负整数表示终局时的总得分。

hint:
【样例 1 解释】

每次操作后，前 $3$ 类奖分的和分别为：$315,\ 417,\ 429,\ 435,\ 482$ 。第 $5$ 次操作后计算牌型奖分，最优牌型为 $(1\ 2\ 4\ 2\ 4)$ ，奖分为 $200 + 4\times 2 + 2 \times 1 = 210$ 。终局时两种终局奖分均可获得，故总分为 $11692$ 。

【样例 2 解释】

与上一组样例相比，增加了 $3$ 次无效操作，且最后不能实现全消，因此得不到终局奖分。

【数据范围与约定】

$n,m\leq 50,\ k \leq 100,\ q \leq 1000,\ a_{i,j} \leq k,\ b_{i,j} \leq 6,\ x_{i,1},x_{i,2} \leq n,\ y_{i,1},y_{i,2} \leq m$ 。

保证初始局面没有可以直接消除的情况。


title: [THUPC2022 决赛] 想象

description:
长颈鹿是一名想象学竞赛（Olympiad in Imaginics） 的选手。特别是出生在风井省内，若要从千百高手中脱颖而出，争夺进入全国决赛的门票，为自己上大学取得升学优势，更需要无穷无尽的想象力。

风井省的赛题风格自古便与其他省份截然不同，因此即便在 3022 年，风井省也保持着自己的独立作风，没有与其他省一同进行统考，仍是独立命卷。

长颈鹿深知风井省赛题所需的想象力之深厚：在往年，赛题的空间限制、数据组数甚至是题目大意，都可能需要选手自行想象。有些一眼看就没有多项式做法的题目，只要加以想象，也可以通过简单的输出通过。而真正的博弈，往往在赛前就开始，风井省总是会从网络各地原汁原味搬运题目，对于没有在赛前就做到原题的选手，想象力的匮乏是不可避免的。

但想象学竞赛的魅力就在于，你永远想象不到会发生的事。

在风井省选前半个月，长颈鹿的教练便为学生们布置了两道在 CodeFancy 上非常冷门的练习题目，但没让长颈鹿想到的是，这竟与正式赛题完全一致！长颈鹿十分钦佩教练的想象力，更深刻理解了“做干净的奥赛”为何意。最终，在这次风井省选中，长颈鹿的学校名列前茅，即便代价是另一些有一定水平的选手没有得到理想的名次。

黑盒测试，是想象学竞赛区别于别的竞赛的最大特点。排除了人为的评判，将所有程序一视同仁，因此在以前，想象学竞赛被称为“最公平的竞赛”。可在冰冷冷的现实面前，所谓公平的表象，也只是一种想象。

幸好，发生过的事情无需想象，我们都还能用双眼直视真相，理解发生了什么，并将之铭记。就像你也无需对本文描述的故事进行想象，简单的换词游戏不会屏蔽真义。现在就请你输出，长颈鹿在风井省参与的比赛的是什么？用缩写名称输出。

例：真卷省的省级选拔赛，缩写名称为 ZJOI。

inputFormat: 本题的输入对于你的输出没有意义，你可以无需读入。

outputFormat:
本题仅有一个唯一的输出答案。

输出一行，四个大写字母，表示风井省的省级选拔赛缩写名称。

hint: 请不要妄加想象，认真阅读题目要求，正确输出，以避免在本题出错罚时。


title: 【模板】点双连通分量

description: 对于一个 $n$ 个节点 $m$ 条无向边的图，请输出其点双连通分量的个数，并且输出每个点双连通分量。

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

接下来 $m$ 行，每行两个整数 $u, v$，表示一条无向边。

outputFormat:
第一行一个整数 $x$ 表示点双连通分量的个数。

接下来的 $x$ 行，每行第一个数 $a$ 表示该分量结点个数，然后 $a$ 个数，描述一个点双连通分量。

你可以以任意顺序输出点双连通分量与点双连通分量内的结点。


title: [北大集训 2021] 末日魔法少女计划

background: CTT2021 D1T1

description:
对于给定的 $n,k$，你需要构造一个只含 $0,1$ 的矩阵 $A_{i,j}$，$0\le i,j\le n$，满足：

1. $A_{i,i}=1$；
2. $A_{i,i+1}=1$；
3. 对 $i>j$ 有 $A_{i,j}=0$；
4. 若 $A_{i,j}=1$，$j-i>1$，则存在 $i<t<j$，满足 $A_{i,t}=A_{t,j}=1$；
5. 对 $i\le j$ 有 $(A^k)_{i,j}>0$。

你需要输出满足 $A_{i,j}=1$ 且 $j-i>1$ 的每个 $(i,j)$，设这样的 $(i,j)$ 共有 $m$ 个。

若输出不满足要求，则不能得到该测试点的任何分数。若输出满足要求，则根据 $m$ 进行评分。

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

outputFormat: 第一行一个整数 $m$，接下来 $m$ 行，每行两个整数 $i,j$，依次表示每个满足 $A_{i,j}=1$ 且 $j-i>1$ 的二元组 $(i,j)$。


title: [北大集训 2021] 魔塔 OL

background: CTT2021 D1T2

description:
比特游戏公司最近发布了一款新游戏《魔塔 Online》，玩家可以操控勇士在游戏世界中与怪物进行搏斗。在游戏发布之初，魔塔里没有任何怪物，接下来将依次发生 $q$ 个事件，每个事件是以下三种之一：

* `+ x y z a b`：表示游戏发布了新版本，在游戏中新增了一只怪物。如果这是第一只新增的怪物，那么它的编号为 $1$；否则它的编号为最后一只新增的怪物的编号 $+1$。这只怪物位于魔塔的第 $x$ 层，它的等级为 $y$ 级，它的难度为 $z$。如果玩家选择击杀这只怪物，那么需要消耗 $a$ 点血量，在击杀成功后，玩家将得到一支可以恢复 $b$ 点血量的药剂并立即使用。
* `- k`：表示游戏发布了新版本，编号为 $k$ 的怪物由于平衡性问题下架，它将不会出现在魔塔中。请注意：下架的怪物**仍然保留它们的编号**，未来新增的怪物**不会复用**被下架怪物的编号。
* `? g l d`：表示一个询问。某玩家希望击杀魔塔前 $g$ 层中**所有**等级**不超过** $l$ 且难度**不超过** $d$ 的怪物。玩家可以按照**任意顺序**去击杀这些怪物，登上新的一层**不需要杀光**当前层的所有怪物，且作战过程中不会受到别的怪物的干扰。你的任务是帮助该玩家计算出征前勇士的血量**最少**是多少。如果某个时刻勇士的血量是**负数**，那么游戏结束，你一定要防止这种情况的发生。

请写一个程序，依次回答每个询问。注意：每个询问只是玩家的一个思考，**不会真正击杀**任何一只怪物。

inputFormat:
输入的第一行包含一个整数 $q$，表示事件数。

接下来 $q$ 行，每行开头一个字符，随后是几个整数，依次描述每个事件。

输入数据保证 $1\leq q\leq 150\,000$，怪物总数不超过 $50\,000$，询问数量不超过 $50\,000$。

对于新增怪物操作，保证 $1\leq x,y,z\leq 10\,000$，且 $0\leq a,b\leq 10^9$。

对于下架怪物操作，保证操作合法，且每只怪物不会被重复下架。

对于询问，保证 $1\leq g,l,d\leq 10\,000$。

outputFormat: 对于每个询问，输出一行一个整数，即出征前勇士的血量的最小值。

hint:
1. （3 分）怪物总数不超过 $8$，询问数量不超过 $8$。
2. （7 分）怪物总数不超过 $5\,000$，询问数量不超过 $5\,000$。
3. （10 分）药剂不会回血，且所有怪物的难度都是 $1$。即 $b=0$，且 $z=d=1$。
4. （17 分）$1\leq x,y,z,g,l,d\leq 5$。
5. （30 分）所有怪物的等级和难度都是 $1$。即 $y=z=l=d=1$。
6. （33 分）无其他限制。


title: [北大集训 2021] 基因编辑

background: CTT2021 D1T3

description:
人类目前已经研究出了多种基因编辑技术，其中最传统的一种技术需要用到“限制性核酸内切酶”（简称限制酶）。这种酶能够识别特定的核苷酸序列，并在指定的位点上切割连接相邻核苷酸的磷酸二酯键，产生被称为“末端”的序列切口。只有相匹配的末端才能用 DNA 连接酶进行连接。

假设现在要用基因片段 $A$ 去替换某一载体 $V$ 上的基因片段 $B$。在使用限制酶的编辑技术中，通常需要进行以下操作：

1. 在基因 $A$ 的两端各选择一种限制酶识别位点。这两处识别位点在基因 $B$ 的两端也应当相应存在。
2. 用所选择的识别位点对应的限制酶对基因 $A$ 进行处理，使得其两端产生相应的末端。将处理后的基因 $A$ 提纯。
3. 用同样的限制酶切断载体 $V$ 上的识别位点，使得基因 $B$ 与载体 $V$ 断开。纯化出去除了基因 $B$ 的载体 $V'$。
4. 将载体 $V'$ 与基因 $A$ 混合，并在 DNA 连接酶的帮助下将断开的磷酸二酯键重新接上。

值得一提的是，如果两处识别位点断开后产生了相同的末端，那么在第 4 步中载体 $V'$ 有可能单独连接起来，产生了不包含基因 $A$ 或 $B$ 的载体；也有可能基因 $A$ 反向接入 $V'$，同样产生错误的载体。因此，在实际运用中，通常选取产生不同末端的限制酶对基因 $A$ 和载体 $V$ 进行处理。

公元 3032 年，人类发现了一种掌握了基因编辑技术的外星文明 HD1048576d。当然，这种基因编辑的技术仅限于居住在 HD1048576d 这颗行星上的外星生物的基因。我们人类掌握的基因编辑技术可识别的最小单位是 DNA 序列上的单个碱基，而外星文明的基因编辑技术可识别的最小单位是其基因序列上的单个 noicleobase。出于方便起见，我们可以将单个 noicleobase 用从 $1$ 开始的正整数表示，那么一段外星生命的基因序列就可以被表示成相应的正整数序列。

对于一段长度为 $n$ 的外星生命的基因序列（不妨记其正整数表示为 $s_1, s_2, \cdots, s_n$），外星文明 HD1048576d 的基因编辑过程如下：

1. 选择一段要编辑的区域 $[l, r]$，即原位替换原序列中 $s_l, s_{l+1}, \cdots, s_r$ 这部分子序列；
2. 挑选一对跨过待替换区域的下标 $(i, j)$（即 $1\le i<l$ 且 $r<j\le n$），批量生产出 $s_i, \cdots, s_j$ 这段子序列在编辑后对应的新序列 $s_i, \cdots, s_{l-1}, t_1, \cdots, t_k, s_{r+1}, \cdots, s_j$；
3. 通过对应的特异性识别工具，将 $s_i, \cdots, s_j$ 这段子序列从原序列中断开，并将 $s_i, \cdots, s_{l-1}, t_1, \cdots, t_k, s_{r+1}, \cdots, s_j$ 接到序列中，即可得到目标基因序列。

需要注意的是，在步骤 2 中，挑选的这对下标必须对应唯一的 noicleobase 组合。也就是说，能够满足 $s_{i'}=s_i, s_{j'} = s_j$ 且 $i<j$ 的有序对 $\left(i', j'\right)$ 必须是唯一的（即为 $(i, j)$），否则特异性识别工具可能切割下其它区段的基因序列；另外，$s_i\ne s_j$，否则特异性识别工具可能只切割下单个 noicleobase。

另外，由于替换时需要生产新的基因序列，而生产这样的序列需要不小的开销，所以外星文明希望能够最小化需要生产的基因序列长度。显然，最小化这一长度等价于最小化被切割下来的基因子序列的长度，所以实践中一般是通过最小化被切割下来的基因子序列长度来计算最优解的。

现在，他们想考考人类文明的智力水平，于是你被他们从众多高中生中挑选出来解决这一问题。

inputFormat:
输入的第一行包含三个正整数 $n, l, r$，表示待编辑的基因序列的长度，需要编辑的区域的左端点，和需要编辑的区域的右端点。保证 $3\le n\le 10^6$ 且 $1<l\le r < n$。

输入的第二行包含 $n$ 个正整数 $s_1, \cdots, s_n$，表示用正整数表示的待编辑的基因序列。保证每个 noicleobase 的编号 $s_i$ 都在 $[1, 10^6]$ 中。

outputFormat: 如果存在满足外星文明的基因编辑技术限制的基因序列切割方案，则输出一个正整数，表示输出所有方案中，被切割下来的基因子序列的最小值。否则，输出 `-1`，表示不存在满足限制的切割方案。

hint:
最优方案为切割 `1 4 7 4 8 3`。可以证明，没有比这更优秀的满足技术限制的切割方案。

一种比该方案切割长度更短的方案是 `4 7 4 8 3`，但是在这种方案中特异性识别工具可能会断开 `4 8 3`，从而导致产生的目标基因序列出现意外的突变，因此这种切割方案不满足技术限制。

---

对于 $100\%$ 的数据，保证 $3\le n \le 10^6$，$\forall 1\le i\le n, 1\le s_i\le 10^6$，且 $1<l\le r<n$。

本题共有 5 个子任务，你需要通过一个子任务中的所有测试点才能获得该子任务的相应分数。下表为各子任务的数据规模及性质。

| 子任务编号 | 对应分数 | $n\le$ | $s_i\le$ | 特殊性质 |
| :--------: | :------: | :----: | :------: | :------: |
|    $1$     |   $5$    | $1000$ |  $1000$  | $\times$ |
|    $2$     |   $10$   | $1000$ |  $10^6$  | $\times$ |
|    $3$     |   $25$   | $10^6$ |  $1000$  | $\times$ |
|    $4$     |   $30$   | $10^6$ |  $10^6$  | $\surd$  |
|    $5$     |   $30 $   | $10^6$ |  $10^6$  | $\times$ |

上表中的“特殊性质”为：$s_1, \cdots, s_{l - 1}$ 各不相同，且 $s_{r + 1}, \cdots, s_n$ 各不相同。


title: [北大集训 2021] 简单数据结构

background: CTT2021 D2T1

description:
小 D 是一位数据结构大师，他特别喜欢研究形式简单的数据结构，今天他想到了这样一道题目：

你有一个长度为 $n$ 的序列 $a$，下面你要进行 $q$ 次修改或询问。

1. 给定 $v$，将所有 $a_i$ 变为 $\min(a_i, v)$。
2. 将所有 $a_i$ 变为 $a_i + i$。
3. 给定 $l, r$，询问 $\sum_{i=l}^r a_i$。

顶级数据结构大师小 D 轻松的解决了这个问题，现在他打算来考考即将参加 IOI2022 的你，相信你也可以轻松解决这个问题。

inputFormat:
第一行两个正整数 $n, q$，表示序列的长度与修改/询问的个数。

下面一行 $n$ 个整数 $a_i$，表示初始序列 $a$。

下面 $q$ 行，每行第一个正整数 $op_i$ 表示第 $i$ 次修改/询问的类型。

若 $op_i = 1$，则下面紧跟一个整数 $v_i$，表示进行一次修改 1。

若 $op_i = 2$，则表示进行一次修改 2。

若 $op_i = 3$，则下面紧跟两个正整数 $l_i, r_i$，表示进行一次询问 3。

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


title: [北大集训 2021] 随机游走

background: CTT2021 D2T3

description:
给定一张 $n$ 个点的有向图，点标号为 $1,2,\dots,n$，初始时对 $\forall i\in\{1,2,\dots,n-1\}$，从 $i$ 到 $i+1$ 有一条有向边。

你可以在其中再加入 $m$ 条有向边（起点终点任意），允许有重边和自环。

小 A 会从 $1$ 出发，以随机游走的形式行动，直到抵达 $n$。你希望最大化小 A 从 $1$ 移动到 $n$ 的期望步数。

定义随机游走是这样的一种移动方式：设小 A 当前在点 $x$，$x$ 有 $d$ 条出边，则小 A 会从这 $d$ 条出边中**等概率**随机选择一条走过去。

inputFormat:
输入的第一行包含一个正整数 $T$，表示数据组数，保证 $T \le 10^5$。

接下来 $T$ 行，每行包含三个整数 $n,m,p$，分别表示有向图的点数、你添加的边数以及答案的模数，保证 $1 \leq n \leq 10^9$，$0 \leq m \leq 10^{18}$，$2\leq p\leq 10^9+7$ 且 $p$ 是质数。

outputFormat: 输出 $T$ 行，第 $i$ 行一个整数 $ans$ 表示第 $i$ 组数据中最大的期望步数对 $p$ 取模后的值（可以证明答案是有理数，设其用最简分数表示为 $\frac{a}{b}$，则你需要满足 $ans \cdot b \bmod p=a$，保证这样的 $ans$ 存在）。


title: [北大集训 2021] 小明的树

background: CTT2021 D3T1

description:
小明有一棵以 $1$ 为根的 $n$ 个节点的树，树上每一个非根节点上有一盏灯，他有一个 $2 \thicksim n$ 的排列 $a_1,a_2,\dots,a_{n-1}$。他还有一个计数器，初始为 $0$。

他会按照排列依次点亮这 $n-1$ 盏灯，每进行一次点灯操作后，他会检查整个树是否是美丽的，如果是美丽的，计数器会加上此时点灯的节点形成的连通块的个数。

$n-1$ 次点灯后计数器的值，记为这棵树的答案。

一个树是美丽的当前仅当对于每一个被点亮的节点，这个节点子树内的节点都是点亮的。

小明认为这个问题太简单了，他觉得应该让树动起来。

在初始查询后，他会删掉树中一条边并加上一条边，保证修改后还是一棵树，他想知道每一次修改后将计数器清零后重新点灯并计数，这棵树的答案是多少。

inputFormat:
第一行两个数 $n,m$ ,表示树的节点数为 $n$，有 $m$ 次修改。

接下来 $n-1$ 行，每行 $2$ 个数，表示一条边。

下一行 $n-1$ 个数 $a_i$，表示一个 $2 \thicksim n$ 的排列。

接下来 $m$ 行每行四个数，$x_1,y_1,x_2,y_2$ 表示断开 $x_1,y_1$ 间的边并连接 $x_2,y_2$，保证数据合法。

outputFormat:
共 $m+1$ 行，第一行表示初始树的答案。

接下来 $m$ 行，表示每次修改后树的答案。


title: [北大集训 2021] 出题高手

background: CTT2021 D3T2

description:
Alice 是一个出题高手。

Alice 每天都会出一道题，这样 $n$ 天过去，她就出了 $n$ 道题了。

第 $n+1$ 天，Alice 没有出题，她打算从之前的 $n$ 道题中选择若干道组成一个比赛。方便起见，她决定这些选择的题目得是**连续**的一个时间段出的，也就是这些题目必须形如：第 $l$ 天到第 $r$ 天出的所有题目（$1\le l \le r \le n$）。

Alice 还给每个题目一个评分，第 $i$ 个题目的评分为 $a_i(-1000 \le a_i \le 1001)$ ，评分越高代表这道题越偏智商，评分越低说明这道题越偏码力。

Alice 希望组成的比赛具备特色，也即整体偏向代码或者整体偏向智商。一场以 Alice 第 $l$ 天到第 $r$ 天出的题目组成的比赛的特色程度定义为 $\Large \frac{(\sum_l^r a_i)^2}{r-l+1}$ ，Alice 想要**最大化**这个特色程度。

现在，对于 $m$ 个形如 $ql_i,qr_i$ 的询问，你需要回答如果将 Alice  能选择的题目限定在第 $ql_i$ 到 $qr_i$ 天出的题，Alice 能组成的特色程度最大的比赛的特色程度是多少，你需要以分数的形式输出这个特色程度。

由于 Alice 出题的水平过于高超，你可以认为每道题的评分是**随机生成**的。

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

输入的第二行包含 $n$ 个整数 $a_1 \dots a_n$，代表 Alice 对第 $i$ 天所出的题的评分。

输入的第三行包含一个正整数 $m$。

接下来 $m$ 行，每行输入两个正整数 $ql_i,qr_i$，表示询问。

outputFormat: 共 $m$ 行，每行两个整数 $p_i,q_i$，满足 $\gcd(p_i,q_i)=1$，表示答案为 $\frac{p_i}{q_i}$，若答案为 $0$，则 $p_i=0$，$q_i=1$。


title: [北大集训 2021] 扑克比大小

background: CTT2021 D3T3

description:
小 $Z$ 和小 $A$ 在玩扑克比大小。

他们玩的扑克比大小规则如下：

- 在游戏开始前，系统会给小 $Z$ 和小 $A$ 各发一堆手牌（两堆牌数量可能不相同），其中每张牌上写有一个小写字母。

- 在游戏的每一轮，小 $Z$ 和小 $A$ 同时翻开**牌堆顶**的第一张牌，若两人翻开的牌不同，则牌上对应小写字母**更小**的那一方获胜；若两人翻开的牌相同，则他们会将翻开的牌塞入**牌堆底**，继续游戏，直到某方获胜为止。

而系统实际上是从一个巨大的牌库里面发牌的，具体来说，假设牌库共有 $n$ 张牌，分别是 $a_1,a_2,\cdots,a_n$，则系统会随机选择第 $l$ 张到第 $r$ 张牌发给玩家，换言之，玩家**从牌堆顶到牌堆底**的牌分别是 $a_l,a_{l+1},\cdots,a_r$。

现在小 $Z$ 和小 $A$ 一共要进行 $q$ 轮游戏，并且小 $Z$ 通过某种方式得知了系统在第 $i$ 轮发给小 $A$ 的牌为 $a_{l_i},a_{l_i+1},\cdots,a_{r_i}$，小 $Z$ 想知道他一共有多少种可能的手牌能赢小 $A$。两堆手牌视为不同当且仅当两堆手牌数量不同，或存在一个位置 $d$ 使得两堆手牌中距离堆顶为 $d$ 的牌不同。

inputFormat:
输入的第一行包含一个只包含小写字母的字符串 $a$ 。

输入的第二行包含一个正整数 $q$ 和一个整数 $type$，其中 $type$ 表示数据类型。

接下来 $q$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$。

outputFormat: 输出 $q$ 行，每行一个整数表示小 $Z$ 有多少种可能的手牌能赢小 $A$。


title: [北大集训 2021] 算术

background: CTT2021 D4T1

description:
今天，生活在 14 进制世界的小 Q 学习了一种判断给定的大数是否是 9 的倍数的方法。我们以 $(1BB40)_{14} = (70812)_{10}$ 作为例子描述该方法，下面设 $b=14$，$p=9$，下面的方法中所有的运算在 $b$ 进制下进行。

1. 从低位往高位，将每个连续的 $k=2$ 位划分为一段。例子中，$(1BB40)_{b}$ 被划分为 $1 \mid BB \mid 40$ 三段。
2. 从低位往高位从 $0$ 开始给每一段编号。例子中，第 $0$ 段为 $40$，第 $1$ 段为 $BB$，第 $2$ 段为 $1$。
3. 对于第 $i$ 段计算出值 $b_i$：设第 $i$ 段在 $b$ 进制下的值为 $a_i$，如果 $i$ 为奇数则 $b_i$ 为满足 $(a_i+b_i) \equiv 0 \pmod p$ 的最小非负整数 $b_i$，如果 $i$ 为偶数则 $b_i$ 为满足 $(a_i-b_i) \equiv 0 \pmod p$ 的最小非负整数 $b_i$。例子中有 $b_0=2$，$b_1=6$，$b_2=1$。
4. 将 $b_i$ 按照**下标大的在低位，下标小的在高位**的顺序顺次拼接，形成一个 $b$ 进制数并输出。例子中输出结果为 $(261)_{b} = (477)_{10}$。容易验证 $477$ 和 $70812$ 都是 $p$ 的倍数。

可以证明上述方法输入和输出的数要么同时是 $p$ 的倍数，要么同时不是 $p$ 的倍数。而且数字的位数变少了，所以多做几次就可以得到一个很小的数，然后就可以简单地判断了。

小 Q 深深地被这个算法吸引了，所以他想给出一个 $b,p$ 不同于 $14,9$ 时的通用方法。但是他发现，当上面的方法中 $b,p$ 的取值变化时，$k$ 不一定等于 $2$：有时会是 $1$，有时会大于 $2$，有时甚至不存在满足条件的 $k$。所以对于给定的 $b, p$，小 Q 想知道在 $b$ 进制下上述方法的第一步中**正整数** $k$ 的最小值，使得无论输入如何，输入和对应的输出要么同时是 $p$ 的倍数，要么同时不是 $p$ 的倍数，或者报告这样的 $k$ 不存在。

注意 $p$ 不一定是质数。

inputFormat:
**测试点有多组测试数据，保证同一测试点下的 $p$ 相同**。输入的第一行包含两个正整数 $T,p$，保证 $1 \le T \le 10^5$，$2 \leq p \le 10^{15}$，分别表示该组测试点的测试数据组数与方法的 $p$ 参数。

接下来 $T$ 行每行输入一行一个整数 $b$ 表示每组测试数据的进制。保证 $2 \leq p < b \leq 10 \times p$。

**输入中的所有数字按照十进制给出。**

outputFormat: 对于每组数据输出一行，若不存在合法的 $k$ 输出 `-1`，否则输出最小的满足条件的**正整数** $k$。


title: [北大集训 2021] 经典游戏

background: CTT2021 D4T2

description:
某天，`C` 和 `K` 觉得很无聊，于是决定玩一个经典小游戏：

在一棵有 $n$ 个结点的有根树上，标号为 $i$ 的节点上有 $a_i$ 个棋子。游戏时玩家轮流操作，每次可以将任意一个节点 $u$ 上的一个棋子放置到任意一个点 $v \in U(u)$上，其中 $U(u)=subtree\{u\}\setminus\{u\}$ ，表示 $u$ 的子树内（不包含 $u$ 本身）的点组成的集合。不能进行操作者失败。

而 `C` 和 `K` 作为 `P**` 和 `T**` 的在读学生，这种一眼就能找出必胜策略的游戏实在是索然无味，于是两人觉得，每个人给自己一个特殊能力可能会比较有趣：

`C` 在开始游戏之前，**可以选择**将当前树的树根 $R$ 换到与 $R$ 相邻的任意一个点 $R^{\prime}$ 上。定义两个点相邻当且仅当这两个点有边直接相连。

`K` 在开始游戏之前，**必须选择**树上的一个节点，在上面加上一颗棋子。

`C` 和 `K` 决定玩 $m$ 局游戏。每局游戏的流程如下：

1. 游戏开始前，`C` 和 `K` 会商量好，先在标号为 $x$ 的节点上放上一个棋子，然后将树根设为 $y$。
2. 之后 `C` 可以选择是否发动特殊能力，`C` 决策完之后 `K` 可以选择是否发动特殊能力。
3. 特殊能力的决策结束后，会在这棵树上进行一局 `C` 先手、`K` 后手的游戏。游戏完成后会将树上棋子的状态**还原到流程 `1` 结束后的状态**。

`C` 觉得这个游戏可以出成一个简单题，于是他决定考考你：`C` 在每局游戏的第二步的时候，有多少种决策方式使得不管 `K` 如何进行特殊能力的操作，开始游戏时都存在**必胜策略**？两种决策方式不同，**当且仅当**两种决策**更换的树根** $R^{\prime}$ **不同**，或者**两者中仅有一个没有发动特殊能力**。

inputFormat:
第一行包括一个整数，表示该测试点所在的子任务的分数。你可以使用这个信息判断该测试点满足的特殊性质。特别的，下发样例中此行使用 $0$ 代替。

第二行包含两个用空格隔开的正整数 $n, m$，表示树的节点数目以及游戏的轮数。树上的节点从 $1$ 到 $n$ 编号。

接下来 $n-1$ 行，每行包含两个用空格隔开的正整数 $u_i,v_i$，满足 $1 \le u_i,v_i \le n$，表示编号为 $u_i$ 和 $v_i$ 的节点之间有边直接相连。

接下来一行包含 $n$ 个用空格隔开的整数 $a_1,a_2,\ldots,a_n$，满足 $0 \leq a_1,a_2,\ldots,a_n \leq 10^9$。

接下来 $m$ 行，每行包含两个用空格隔开的正整数 $x, y$ 描述一局游戏，满足 $1 \le x,y \le n$。

outputFormat: 你需要输出 $m$ 行，其中第 $i$ 行应当包含一个非负整数 $x$ 表示第 $i$ 局游戏中，`C` 存在多少种使用特殊能力的决策方案，使得 `C` 在这局游戏中存在必胜策略。注意，**不使用特殊能力**也是一种**可能可行**的决策方案。


title: [北大集训 2021] 随机数据

background: CTT2021 D4T3

description:
有 $n$ 件物品，用 $0, \cdots, n-1$ 对它们编号，规定物品 $i$ 的价值为 $v_i$。

A 和 B 正在轮流玩一个游戏，该游戏会进行多轮。

每轮开始时，如果所有可用的物品都已经被取走，游戏将立刻结束。否则，A 必须选择一件未被取走的物品，将其取走。

假设 A 取走的物品编号为 $i$。接下来，B 可以选择从物品 $(i - d + n) \bmod n$ 和物品 $(i + d) \bmod n$ 中选取一件未被取走的物品，将其取走；或者他可以选择跳过本次操作。随后游戏进入到下一轮。特别地，如果这两件物品都已经被取走了，B 只能选择跳过本次操作。

A 和 B 都想最大化自己取走的物品的价值之和，我们假定 A 与 B 都采取了最优策略。

此外，在游戏开始前，有一些物品可能是不可用的。在游戏过程中，不可用的物品将会被忽略，即：A 和 B 都不能取走不可用的物品；当所有可用的物品都已经被取走时，游戏立刻结束。

初始时，所有物品都是可用的。你的程序需要支持 $q$ 次操作，每次操作的内容为：给定一个 $x$，如果物品 $x$ 是不可用的，它将变为可用的；如果它是可用的，它将变为不可用的。每次操作后，你需要回答：假设从当前状态开始游戏，游戏结束时 B 取走的物品的价值之和。

不幸的是，这是一道 IO 题，**物品的数量可能会达到 $10^{16}$**。身为一个 OIer，你无法处理如此大规模的数据，因此 $v_i$ 将会用一种**特殊的方法**生成：给定一个长度为 $m$ 的数组 $w$，$v_i = w_{i \bmod m}$。

inputFormat:
输入的第一行包含四个**正整数** $n, d, m, q$，保证 $1 < n \le 10^{16}, 1\le d < n, 1 \le m \le 2\times 10^4, q \le 10^5$。

输入的第二行包含 $m$ 个整数，第 $i$ 个整数表示 $w_{i-1}$ 的值，保证 $1 \le w_i \le 400$。

接下来的 $q$ 行，每行包含一个整数 $x$，表示一次对物品 $x$ 的操作。保证 $0 \le x < n$。

outputFormat: 输出 $q$ 行，每行一个整数，对应一次操作之后的答案。

hint:
Subtask 1 (5 pts) : $n \le 20, q = 1$

Subtask 2 (10 pts) : $n \le 10^5, q = 1$

Subtask 3 (15 pts) : $n, q \le 10^5$

Subtask 4 (30 pts) : $q = 1$

Subtask 5 (40 pts) : 无特殊限制。

如有需要，可以使用 `__int128` 处理 `long long` 乘法取模，下面是一个使用 `__int128` 计算 $a \times b \bmod m$ 的例子：

```cpp
long long a = 1e15;
long long b = 1e15;
long long m = 12345678910;
long long c = ((__int128) a * b) % m;
```


title: 毕业后

background:
毕业后，同学们都在热烈讨论高中的计划。所有人总是难以避开一个话题——学考。

在浙江，高中生除了要参加普通高等学校招生全国统一考试（简称高考）以外，还要参加普通高中学业水平考试（简称学考）。学生要在高一下、高二上和高二下各参加一次学考。

description:
**注意：题目中的部分描述可能和现实有所出入。**

学考会考查高中所有科目，并根据成绩分层评级，自高到低为 A~E。每门科目都会按照一个确定的比率 $w$（所有学科都相同）确定 E 等人数。如果学考有**大于一门**科目拿到了 E 等（不合格），该学生将不能毕业。

在另一个平行世界里，高中总共有 $a$ 门科目。全省共有 $b$ 名考生。如果 E 等的分数线过高，可能会导致总存在某些人毕不了业的情况。现在，考试院院长找到了你，希望你确定学考 E 等占所有考生的**最大**比例（即，最大化 $w$ 的值），使得**存在**至少一种方案，能使浙江所有考生都能毕业。

如果按照某个比例算出来的 E 等考生数不为整数，则将考生数**向上**取整。

inputFormat: 一行，输入两个正整数 $a,b$。

outputFormat:
输出一个浮点数，表示 E 等级的最大占比。

本题使用自定义校验器，与标准答案之间的绝对误差在 $10^{-6}$ 以内的结果都算作正确答案。

hint:
#### 样例 1 解释

将 E 等比率设成 $\frac{1}{2}$，此时每门科目都恰好有一名考生不合格。当第一名考生在第一门科目不合格，第二名考生在第二门科目不合格时，所有考生都能毕业。所以 $\frac{1}{2}$ 是满足要求的。

可以证明不存在更优的方案。

### 数据规模与约定

对于所有数据，$1\le a, b\le 10000$。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|}\hline
\bf{测试点} & \bf{特殊性质}
\\
\hline
1\sim3 & b=1\\\hline
4\sim6 & a=b \\\hline
7\sim10 & /\\\hline
\end{array}
$$

做完这道题，你能否说明，为什么现实中，浙江 E 等不能超过 $5\%$ 呢？


title: 『JROI-7』hibernal

background:
我也不知为何会想说这个故事，我也确实不太理解小丑和厨师有什么关系，但既然他们此时此刻排列在我的草稿本上【附图】，那我也只能试着说说了。

呃呃，你说的很对，我也确实想不出他们的关系了。

唔，小丑会出现在这里或许多半是因为他的出场总伴着诡异。

但我还是觉得厨师这个角色有趣。

但是，但是，这和【hibernal】有什么关系吗。

啊，还是来说说厨师吧。食材还是让人觉得有趣的。

欸，其实蔬菜能提供比肉类丰富的多的口感，但是似乎大家都不认同我的观点，你呢？

英文字母和汉字之间要加空格，让我检查检查。

【AI绘画】少女，裸背，颈控。

啊，我知道了。这似乎可以是个有趣的故事。唔，写起来可能很花时间，你还是先过了这题再来催我吧 qwq.

最后是不是要说点什么以示礼貌啊。那就祝大家身体健康吧，好耶！

description:
有 $n$ 个苹果，第 $i$ 个编号为 $i$，其中有恰好 $2$ 个是金苹果。

每次询问可以把 $n$ 个苹果分为两个集合 $S_1,S_2$，要求每个苹果恰好被分到一个集合中。

设 $x$ 为 $S_1$ 中金苹果的个数，$y$ 为 $S_2$ 中金苹果的个数，交互库会返回 $x\times y$ 的值。

请在不超过 $19$ 次询问内求出两个金苹果的编号。

**交互库自适应，即两个金苹果的编号可能会随着询问而改变，但是始终满足所有已经发生过的询问（见样例）。**

inputFormat:
本题多测，第一行一个正整数 $T$，表示数据组数，接下来 $T$ 行每行一个正整数 $n$，表示本组数据里数的个数。

本题采用 IO 交互模式。

### 交互格式
- `? k a1 a2 a3 ... ak` 将这 $k$ 个苹果放入一个集合，其他 $n-k$ 个苹果放入另一个集合，交互库会返回一个整数 $x$ 表示答案。**请务必保证 $0<k<n$。**
- `! x y` 输出答案。**请务必保证 $x<y$。**

请注意：在每组数据中，请保证第一种操作的次数总和不超过 $19$ 。

需要注意的是，在每一次操作后，需要调用以下函数刷新缓存：
- 对于 C/C++：`fflush(stdout);`
- 对于 C++：`std::cout << std::flush;`
- 对于 Java：`System.out.flush();`
- 对于 Python：`stdout.flush();`
- 对于 Pascal：`flush(output);`

对于其他语言，请自行查阅对应语言的帮助文档。

outputFormat: 见「交互格式」。

hint:
**样例仅供理解交互过程，可能不符合逻辑。**

【样例解释】

初始的两个金苹果为 $3,5$。

第一次询问，两个集合各有 $1$ 个金苹果，返回 $1$，金苹果的编号不发生改变。

第二次询问，一个集合有 $2$ 个金苹果，另一个集合没有，返回 $0$。接下来两个金苹果从 $3,5$ 变成了 $1,5$，容易发现，虽然金苹果的编号发生了变化，前两个询问的答案仍然是符合的。

回答 $1,5$，答案正确，交互结束。

---
### 数据范围
| 分数 | $n=$ | $T=$ |
| -----------: | -----------: | -----------: |
| $10$ | $2$ | $200$ |
| $10$ | $18$ | $200$ |
| $10$ | $64$ | $200$ |
| $20$ | $512$ | $200$ |
| $50$ | $1000$ | $200$ |
### 计分方式
对于每组测试数据，取 $200$ 组测试中进行询问次数最大的一组，若超过 $19$ 次，计 $0$ 分，否则计满分。

保证正常情况下交互库用时不超过 0.1s。

如果您的输出不合法，将会出现 TLE/WA 等情况。


title: 『JROI-7』T2nz.

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

description:
小 X 陷入了一个奇怪的梦。在梦境里，她在和小 Q 下一种奇怪的棋。

这是一个 $2^{2n}\times 2n$ 的棋盘，小 X 执黑先行，小 Q 执白后行。

每次操作，需要**在当前未满的第一行内**，任意选择一格下棋。一格内只能有一个棋子。

下满之后，共有 $2^{2n}$ 行棋子，小 X 的得分为本质不同的行数。

小 X 想最大化她的得分，但小 Q 想最小化小 X 的得分。

你的任务是，扮演小 X 或小 Q，最大化或最小化得分。

**若你是小 X，在满足最大化得分 $ans$ 的同时，你也要最大化前 $ans$ 行中本质不同的行数**。

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

### 交互格式

你要先从标准输入读入一行两个整数 $T,tp$，表示数据组数和你扮演的角色。保证 $tp\in\{0,1\}$。若 $tp=0$，表示你扮演小 Q（后手）；若 $tp=1$，表示你扮演小 X（先手）。

接下来每一组数据，你要先从标准输入读入一行一个正整数 $n$，含义见题目描述。

接下来会进行 $2^{2n}\times n$ 次交互。

在每次交互中：

- 若 $tp=0$，你要先从标准输入读入一行一个正整数 $x$，表示小 X 下了黑棋在当前未满的第一行的第 $x$ 列，接下来你要向标准输出输出一个正整数 $y$，表示你下了白棋在当前未满的第一行的第 $y$ 列；
- 若 $tp=1$，你要先向标准输出输出一个正整数 $x$，表示你下了黑棋在当前未满的第一行的第 $x$ 列，接下来你要从标准输入读入一行一个正整数 $y$ 表示小 Q 下了白棋在当前未满的第一行的第 $y$ 列。

你的输出都要**换行并清空缓存区**。

你需要保证你下棋的位置不能已有棋子。同时，交互库也会保证其下棋的位置不会已有棋子。

inputFormat: 见「交互格式」。

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

读入的 $n=1$，因此棋盘的大小是 $4\times 2$ 的。两人模拟如[动图](https://i.ibb.co/ChCxHQH/e.gif)所示。最终结果如下图所示：

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

可以观察发现，最终本质不同的行数为 $2$。容易发现，这是小 X 能最大化的得分。同时，前 $2$ 行中本质不同行数为 $2$，显然无法达到更大的值。

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

**【数据范围与规模】**

| 测试点编号 | $n \le$ | $tp=$ |
|:-:|:-:|:-:|
| $1$ | $3$ | $0$ |
| $2\sim 3$ | $7$ | $0$ |
| $4$ | $3$ | $1$ |
| $5$ | $4$ | $1$ |
| $6$ | $5$ | $1$ |
| $7 \sim 8$ | $6$ | $1$ |
| $9 \sim 10$ | $7$ | $1$ |

对于所有的数据，保证 $1 \le n \le 7$，$1 \le T \le 3$，$tp\in\{0,1\}$。

------------
**【提示】**

- 您可以使用如下语句来清空缓冲区：

	- 对于 C/C++：`fflush(stdout)`；
	- 对于 C++：`std::cout << std::flush`；
	- 对于 Java：`System.out.flush()`；
	- 对于 Python：`stdout.flush()`；
	- 对于 Pascal：`flush(output)`；
	- 对于其他语言，请自行查阅对应语言的帮助文档。
	- 特别的，对于 C++ 语言，在输出换行时使用 `std::endl` 而不是 `'\n'`，也可以自动刷新缓冲区。

- 我们保证交互库耗时在 $1.5\text{s}$ 内，空间消耗可以忽略不计。


title: gcd.

background: 与你借星火，容我题山河。

description:
$T$ 组数据，每一组数据给定 $l,r,x$，试求：$\gcd(\lfloor \frac{l}{x}\rfloor,\lfloor \frac{l+1}{x}\rfloor,\cdots,\lfloor \frac{r}{x}\rfloor)$ 的值。

- 其中 $\gcd$ 表示求最大公约数，例如 $\gcd(6,9)=3$，$\gcd(2,4,8)=2$，$\gcd(5,6,7)=1$。特别地，我们定义一个正整数的最大公约数是它自身。
- $\lfloor x \rfloor$ 表示 $x$ 向下取整，例如 $\lfloor 3.14 \rfloor=3$。

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

对于每一组数据，输入一行三个正整数 $l,r,x$，以空格隔开。

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

hint:
**【样例解释和说明】**

样例中的 $T=4$，说明有 $4$ 组数据。

- 对于第一组数据，$l=3,r=6,x=1$，即求 $\gcd(\lfloor \frac{3}{1}\rfloor,\lfloor \frac{4}{1} \rfloor, \lfloor \frac{5}{1}\rfloor,\lfloor \frac{6}{1}\rfloor)=1$。
- 对于第二组数据，$l=8,r=11,x=4$，即求 $\gcd(\lfloor \frac{8}{4} \rfloor,\lfloor \frac{9}{4} \rfloor,\lfloor \frac{10}{4}\rfloor,\lfloor \frac{11}{4}\rfloor)=\gcd(2,2,2,2)=2$。
- 对于第三组数据，$l=4,r=4,x=3$，即求 $\gcd(\lfloor \frac{4}{3}\rfloor)=1$。
- 对于第四组数据，类似可得结果是 $1$。

**【数据范围】**

- 对于 $10\%$ 的数据，$x=1$。
- 另有 $10\%$ 的数据，$l=r$。
- 另有 $20\%$ 的数据，$r-l \leq 10^5$。
- 对于上述的前 $40\%$ 的数据，$1 \leq x \leq l \leq r \leq 10^9$。
- 对于所有数据，$1 \leq x \leq l \leq r \leq 10^{18}$，$1 \leq T \leq 10$。


title: Aleph-0 (Fan-made LGC 7)

background:
Rolling_Code 是一个喜欢音游的女孩子。

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

Rolling_Code 打 $\aleph_0$ 的成绩如下：

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

~~然而这并不是 IN。~~

慢报：Rolling_Code 将 Aleph-0 [IN 15(15.7)] All Perfect 了！

description:
LeaF 作为数学教师开办了一系列完美数学课堂，参加的学生包括了：Rolling_Code，你，美穗。助教：琪露诺。

第一节课，考试。

做出这道题目的同学可以获得特殊版 $\aleph_0$ 的率先游玩机会哦！——LeaF

~~Aleph-0 (Legacy - SP Lv.?)~~

Rolling_Code 对音游非常感兴趣，所以也非常想要获得这首曲子。但是它打开题面的时候震惊了：

> $f(x)=\begin{cases}0&x=0\\1&x=1\\2f(\frac{x}{2})&2|x\operatorname{and} x>0 \\ 2f(\frac{x-1}{2})+\frac{2}{x-1}f(\frac{x-1}{2})+x&\text{otherwise}\end{cases}$

求 $S=\left(\sum\limits_{i=0}^{r} f^k(i)\right)\bmod (10^9+7)$。

其中 $f^k(i)=(f(i))^k$。

本来是想要求 $r\rightarrow\aleph_0$ 的答案，可惜了啊，没有被定义，那就把 $r$ 范围放小一点吧。——LeaF

由于某些原因，LeaF 定义 $0^0=1$。

为了增加趣味，LeaF 还增加了多次对于 $r,k$ 的询问。

Rolling_Code 不会做，因此找你求助。

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

第一行一个数字 $t$，代表数据组数。

接下来 $t$ 行每行两个数字 $r_i,k_i$，表示第 $i$ 次询问中的 $r,k$。

outputFormat: 每行一个数字 $S_i$，表示第 $i$ 次询问的答案。

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

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

对于 $100\%$ 的数据，保证 $1\le t\le 10^3,1\le r\le 2^{63}-1,0\le k\le 30$。

Subtask 1：对于 $5\%$ 的数据，保证 $1\le t\le 100,1\le r\le 10^4$。

Subtask 2：对于 $10\%$ 的数据，保证 $1\le t\le 1000,1\le r\le 10^5$，**依赖于 Subtask 1**。

Subtask 3：对于 $10\%$ 的数据，保证 $1\le t\le 1000,1\le r\le 10^6,k$ 为定值。

Subtask 4：对于 $25\%$ 的数据：保证 $k=2$。

Subtask 5：对于最后 $50\%$ 的数据，无特殊限制，**依赖于 Subtask 1，2，3，4**。

---

### 样例解释

$f_0=0,f_1=1,f_2=2,f_3=6,f_4=4$。

对于 $r=4,k=2$ 的情况，$\text{Ans}=0^2+1^2+2^2+6^2+4^2=57$。


title: [Aya Round 1 D] 文文的数学游戏

background: 在解决了上一题之后，琪露诺觉得自己仿佛就是天才。于是，射命丸文又给了她一道简单的数学题。

description:
给定长度为 $n$ 的整数序列 $a$，你需要构造一个长度为 $n$ 的整数序列 $b$ 满足对于所有 $1\le i\le n$，有 $1\le b_i \le a_i$。且 $\gcd(b_1,b_2,\cdots,b_n)$ 最大，其中 $\gcd$ 表示最大公因数。试求出能得到的最大值和取得最大值时，不同的数列 $b$ 的个数，对 $10^9+7$ 取模。

定义两个长度为 $L$ 的数列 $c,d$ 不同，当且仅当存在整数 $i(1 \le i \le L)$，使得 $c_i \ne d_i$。

inputFormat:
- 第一行一个输入整数 $n$。
- 第二行输入 $n$ 个整数，表示序列 $a$。

outputFormat: - 输出一行两个整数。分别表示能得到到的最大 $\gcd(b_1,b_2,\cdots,b_n)$ 和对应的不同的 $b$ 的个数，对 $10^9+7$ 取模。


title: [JOI Open 2022] 跷跷板（Seesaw）

background: **译自 [JOI Open 2022](https://contests.ioi-jp.org/open-2022/index.html) T1. [シーソー](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/seesaw/2022-open-seesaw-statement.pdf) / [Seesaw](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/seesaw/2022-open-seesaw-statement-en.pdf)。**

description:
一根长度为 ${10}^9$ 的直杆从左到右水平放置。你可以忽略这根杆的重量。共有 $N$ 个砝码挂在这根杆上，每个砝码的质量为一单位。这 $N$ 个砝码的位置两两不同。第 $i$（$1 \le i \le N$）个砝码的位置为 $A_i$。即，第 $i$ 个砝码到直杆最左端的距离为 $A_i$。

最开始，我们有一个宽度为 $w$ 的箱子。我们可以把这根杆子放在箱子上，支撑起杆从 $l$ 到 $r$（$0 \le l < r \le {10}^9$）的部分（包括两端），即，从杆上位置为 $l$ 到杆上位置为 $r$ 的区间。这里需要满足 $r = l + w$。之后我们不可以改变 $l$ 和 $r$ 的值。

接下来，我们去掉挂在杆上最左端或最右端的砝码。我们需要重复这个操作 $N - 1$ 次。在这个过程中，包括初始状态和最终状态，挂在杆上的所有砝码重心都需要保持在 $l$ 到 $r$ 之间（包括两端）。如果杆上挂有 $m$ 个砝码，位置分别为 $b_1, b_2, \ldots, b_m$，那么重心位置为 $\frac{b_1 + b_2 + \cdots + b_m}{m}$。

给定 $N$ 和这 $N$ 个砝码的位置 $A_1, A_2, \ldots, A_N$，写一个程序计算箱子的最小可能宽度 $w$。

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

第二行，$N$ 个非负整数 $A_1, A_2, \ldots, A_N$。

outputFormat: 输出箱子的最小可能宽度 $w$。只要你的输出与标准答案之间的绝对误差或相对误差小于等于 ${10}^{-9}$，你的程序就会被判为正确。

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

可让箱子的宽度为 $\frac{5}{6}$。我们令 $l = \frac{3}{2}, r = \frac{7}{3}$。进行如下操作：

- 最初，重心位置为 $\frac{7}{3}$。
- 第一次操作，我们去掉最右端的砝码（位置为 $4$ 的砝码）。重心位置变为 $\frac{3}{2}$。
- 第二次操作，我们去掉最左端的砝码（位置为 $1$ 的砝码）。重心位置变为 $2$。

在这个过程中，重心始终保持在 $l$ 到 $r$ 范围中。

因为箱子的宽度不会小于 $\frac{5}{6}$，因此输出 $\frac{5}{6}$ 的小数形式。

这组样例满足所有子任务的限制。

----

**【样例解释 \#2】**

这组样例满足所有子任务的限制。

----

**【数据范围】**

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

- 子任务 1（1 分）：$N \le 20$。
- 子任务 2（33 分）：$N \le 100$。
- 子任务 3（33 分）：$N \le 2000$。
- 子任务 4（33 分）：无特殊限制。

对于所有数据，满足 $2 \le N \le 2 \times 10^5$，$0 \le A_1 < A_2 < \cdots < A_N \le {10}^9$。


title: [JOI Open 2022] 长颈鹿（Giraffes）

background: **译自 [JOI Open 2022](https://contests.ioi-jp.org/open-2022/index.html) T2. [キリン](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/giraffes/2022-open-giraffes-statement.pdf) / [Giraffes](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/giraffes/2022-open-giraffes-statement-en.pdf)。**

description:
IOI 动物园以长颈鹿而闻名。IOI 动物园中有 $N$ 只长颈鹿，按身高递增顺序编号为 $1 \sim N$。长颈鹿的身高两两不同。共有 $N$ 个笼舍排成一排，从左到右编号为 $1 \sim N$。每个笼舍居住一只长颈鹿。笼舍 $i$ 中居住长颈鹿 $P_i$。

APIO 先生是 IOI 动物园园长。他正担心 IOI 动物园的评级问题。IOI 动物园因“长颈鹿的观感很糟”的原因收到了差评。具体来说，当一个游客和长颈鹿拍照时，游客会选择两个整数 $l, r$（$1 \le l \le r \le N$）并给在笼舍 $l, l + 1, \ldots, r$ 的长颈鹿拍照。那么，只要下列两个条件**都满足**，这些长颈鹿的观感就是差的。

- 存在一只长颈鹿，满足这只长颈鹿比两端的长颈鹿都高。换句话说，存在一个整数 $k$（$l < k < r$）满足 $P_l < P_k > P_r$。
- 存在一只长颈鹿，满足这只长颈鹿比两端的长颈鹿都矮。换句话说，存在一个整数 $k$（$l < k < r$）满足 $P_l > P_k < P_r$。

APIO 先生将重新排列这些长颈鹿，满足对于游客对任意 $l, r$（$1 \le l \le r \le N$）的选择，长颈鹿的观感都不会是差的。因为将一只长颈鹿从一个笼舍挪到另一个笼舍很费功夫，他想要最小化移动长颈鹿的只数。当然，在移动之后，每个笼舍应仍只有一只长颈鹿居住。

给定目前长颈鹿的信息，写一个程序计算最少要移动多少只长颈鹿。因为 APIO 先生目前的长颈鹿排布是随机的，你可以假设 $P_i$（$1 \le i \le N$）的值是随机生成的（见【**数据生成**】一节了解详细信息）。

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

第二行，$N$ 个正整数 $P_1, P_2, \ldots, P_N$。

outputFormat: 输出一行一个整数，表示最少要移动多少只长颈鹿。

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

IOI 动物园中共有 $6$ 只长颈鹿。长颈鹿 $5,4,6,1,3,2$ 按从左到右的顺序居住在各自的笼舍中。这样排列的话，如果游客对 $l = 2, r = 5$ 的长颈鹿拍照的话，观感就是差的。两个条件按如下方式满足。

- 住在笼舍 $3$ 的长颈鹿比住在最左（笼舍 $2$）和最右（笼舍 $5$）笼舍的长颈鹿都高。
- 住在笼舍 $4$ 的长颈鹿比住在最左（笼舍 $2$）和最右（笼舍 $5$）笼舍的长颈鹿都矮。

如果 APIO 先生将长颈鹿 $1$ 从笼舍 $4$ 移到笼舍 $1$，然后将长颈鹿 $5$ 从笼舍 $1$ 移动到笼舍 $4$，那么对于游客的任意选择，观感都不会是差的。APIO 先生通过移动 $2$ 只长颈鹿达成了目标。因为这是移动只数的最小值，所以输出 $2$。

这组样例满足所有子任务的限制。

----

**【样例解释 \#2】**

IOI 动物园中共有 $4$ 只长颈鹿。长颈鹿 $4, 1, 3, 2$ 按从左到右的顺序居住在各自的笼舍中。这样排列的话，对于游客的任意选择，观感都不会变差。APIO 先生不需要移动长颈鹿，因此输出 $0$。

这组样例满足所有子任务的限制。

----

**【样例解释 \#3】**

以 APIO 先生将长颈鹿 $3, 5, 6, 7, 4, 2, 1$ 按从左到右的顺序居住在各自笼舍中为例。对于游客的任意选择，观感都不会变差。APIO 先生通过移动 $2$ 只长颈鹿达成了目标。因为这是移动只数的最小值，所以输出 $2$。

这组样例满足所有子任务的限制。

----

**【样例解释 \#4】**

这组样例满足子任务 2、3、4 的限制。

----

**【数据范围】**

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

- 子任务 1（10 分）：$N \le 7$。
- 子任务 2（22 分）：$N \le 13$。
- 子任务 3（27 分）：$N \le 300$。
- 子任务 4（41 分）：无特殊限制。

对于所有数据，满足 $1 \le N \le 8000$，$1 \le P_i \le N$，$P_i$ 两两不同，保证 $P_i$ 是随机生成的（见【**数据生成**】一节了解详细信息）。

----

**【数据生成】**

在本题，除了样例输入，有 $10$ 组数据满足子任务 1、2、3、4 的限制，有 $10$ 组数据满足子任务 2、3、4 的限制，有 $10$ 组数据满足子任务 3、4 的限制，有 $10$ 组数据满足子任务 4 的限制。包括样例，总计有 $44$ 组数据用于评分。所有 $44$ 组数据按如下方式生成：

1. 首先，生成满足子任务的 $N$。
2. 然后，在 $N! = 1 \times 2 \times \cdots \times N$ 个满足限制的排列 $(P_1, P_2, \ldots, P_N)$ 中，等概率随机选择一个作为 $P_1, P_2, \ldots, P_N$。


title: [JOI Open 2022] 放学路（School Road）

background:
**译自 [JOI Open 2022](https://contests.ioi-jp.org/open-2022/index.html) T3. [通学路](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/school_road/2022-open-school_road-statement.pdf) / [School Road](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/school_road/2022-open-school_road-statement-en.pdf)。**

----

在洛谷上，本题测试点和子任务配置可能导致评测结果页面难以理解。具体地，将评测结果页面中的子任务编号 $x$ 转为二进制后，从低到高第 $i$ 位为 $1$ 就表示子任务内所有测试点均满足题目中的子任务 $i$ 的限制。

description:
河狸国由 $N$ 座城市组成，编号为 $1 \sim N$。共有 $M$ 条道路连接这些城市，道路编号为 $1 \sim M$。道路 $i$（$1 \le i \le M$）双向连接城市 $A_i$ 和 $B_i$，并且道路 $i$ 的长度为 $C_i$。保证经过一定数量的道路，均可以从任意一座城市到达任意其他城市。

Bitaro 是一只住在城市 $1$ 的河狸。他要去城市 $N$ 上学。他上学通常都走一样的路线。他的上学路线满足如下条件。

- 令 $L$ 为从城市 $1$ 到城市 $N$ 的最短距离。
- Bitaro 的上学路是一条连接城市 $1$ 和城市 $N$ 且长度为 $L$ 的路径。

因为今天天气好，Bitaro 决定绕路回家。也就是说，他会选择一条从城市 $N$ 到城市 $1$ 且长度大于 $L$ 的路径。因为 Bitaro 很容易厌倦，他不想经过同一座城市多于一次。因此，当他绕远路回家时，不允许经过同一座城市多于一次，并且不允许走回头路。

给定河狸国的城市和道路的信息，写一个程序确定是否存在一条从学校到 Bitaro 的家的远路。

**赛时提醒：Bitaro 不允许在回家途中经过相同的城市超过一次，但是并不禁止经过在他上学路线中经过的城市。**

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

接下来 $M$ 行，第 $i$ 行三个正整数 $A_i, B_i, C_i$。

outputFormat: 输出一行，一个数。如果存在一条到 Bitaro 家的，长度大于 $L$ 且不经过同一座城市多于一次的路径，输出 $1$，否则输出 $0$。

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

在这组样例中，从城市 $1$（Bitaro 家）到城市 $4$（学校）的最短距离是 $5$。

有两条到 Bitaro 家并且不经过同一座城市多于一次的路径。

- 按顺序经过道路 $3 \to 1$，长度为 $5$ 的路径，按 $4 \to 2 \to 1$ 的顺序经过城市。
- 按顺序经过道路 $4 \to 2$，长度为 $5$ 的路径，按 $4 \to 3 \to 1$ 的顺序经过城市。

因为不存在到 Bitaro 家的，长度大于 $5$ 且不经过同一座城市多于一次的路径，因此输出 $0$。

这组样例满足所有子任务的限制。

----

**【样例解释 \#2】**

在这组样例中，从城市 $1$（Bitaro 家）到城市 $4$（学校）的最短距离是 $5$。

有两条到 Bitaro 家并且不经过同一座城市多于一次的路径。

- 按顺序经过道路 $3 \to 1$，长度为 $5$ 的路径，按 $4 \to 2 \to 1$ 的顺序经过城市。
- 按顺序经过道路 $4 \to 2$，长度为 $6$ 的路径，按 $4 \to 3 \to 1$ 的顺序经过城市。

因为存在到 Bitaro 家的，长度大于 $5$ 且不经过同一座城市多于一次的路径，因此输出 $1$。

这组样例满足所有子任务的限制。

----

**【样例解释 \#3】**

这组样例满足子任务 1、2、3、5 的限制。

----

**【样例解释 \#4】**

这组样例满足所有子任务的限制。

----

**【样例解释 \#5】**

这组样例满足子任务 1、2、3、5 的限制。

----

**【数据范围】**

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

- 子任务 1（7 分）：$M \le 40$。
- 子任务 2（15 分）：$N \le 18$。
- 子任务 3（23 分）：$M - N \le 13$。
- 子任务 4（35 分）：对于任意三座不同的城市 $a, b, c$，均存在一条从城市 $a$ 到城市 $c$ 且不经过城市 $b$ 的路径。
- 子任务 5（20 分）：无特殊限制。

对于所有数据，满足 $2 \le N \le {10}^5$，$1 \le M \le 2 \times {10}^5$，$1 \le A_i < B_i \le N$，$1 \le C_i \le {10}^9$，保证经过一定数量的道路，均可以从任意一个城市到达任意其他城市。


title: 【模板】边双连通分量

description: 对于一个 $n$ 个节点 $m$ 条无向边的图，请输出其边双连通分量的个数，并且输出每个边双连通分量。

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

接下来 $m$ 行，每行两个整数 $u, v$，表示一条无向边。

**不保证图为简单图，图中可能有重边和自环。**

outputFormat:
第一行一个整数 $x$ 表示边双连通分量的个数。

接下来的 $x$ 行，每行第一个数 $a$ 表示该分量结点个数，然后 $a$ 个数，描述一个边双连通分量。

你可以以任意顺序输出边双连通分量与边双连通分量内的结点。


title: 二叉树的遍历

description:
有一个 $n(n \le 10^6)$ 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 $n$），建立一棵二叉树（根节点的编号为 $1$），如果是叶子结点，则输入 `0 0`。

建好树这棵二叉树之后，依次求出它的前序、中序、后序列遍历。

inputFormat:
第一行一个整数 $n$，表示结点数。

之后 $n$ 行，第 $i$ 行两个整数 $l$、$r$，分别表示结点 $i$ 的左右子结点编号。若 $l=0$ 则表示无左子结点，$r=0$ 同理。

outputFormat:
输出三行，每行 $n$ 个数字，用空格隔开。

第一行是这个二叉树的前序遍历。

第二行是这个二叉树的中序遍历。

第三行是这个二叉树的后序遍历。


title: [LSOT-2] 胜者组

background:
进入胜者组就算胜利吗...

至少人们都这样说。

description:
小 H 的学校在 noip 结束后要决定踢出一些学生回去学文化课。

具体的，学校一共有 $n$ 个同学，留下了最多 $m$ 个学习信息学的名额。

学校里的同学组成了 $k$ 个小团体，其中第 $i$ 个同学属于第 $c_i$ 个小团体。

你每次可以钦定两个处于同一小团体的学生学习文化课。若你让学生 $i,j(c_i=c_j)$ 去学习文化课，学生会产生 $a_i+a_j+x\times|i-j|$ 的不满意度。这里 $x$ 是输入一开始给定的常数。

你需要让学生的不满意度最小化，或报告无法留下不多于 $m$ 个学习信息学的学生。

inputFormat:
第一行四个正整数 $n,m,k,x$。

接下来两行每行 $n$ 个整数分别表示 $a_i,c_i$。

outputFormat: 一行一个整数表示最小的不满意度。或输出 `Impossible` 表示无解。

hint:
样例解释：

分别钦定 $(1,2)$ 和 $(4,6)$ 学习文化课，不满意度为 $(2+5+3\times|1-2|)+(2+7+3\times|4-6|)=25$。

需要注意的是，一个同学不可以被钦定多次。

**「本题采用捆绑测试」**

- $\texttt{Subtask 1(15pts)：}n\le20$。
- $\texttt{Subtask 2(15pts)：}x=0$。
- $\texttt{Subtask 3(15pts)：}k=1$。
- $\texttt{Subtask 4(20pts)：}n\le 300$。
- $\texttt{Subtask 5(35pts)：}$无特殊性质。

对于全部的数据，$0\le a_i,x\le10^5$，$1\le c_i\le k\le n\le 5000$，$0\le m\le n$。


title: [LSOT-1] Crosspain

description:
令 $S_0=\varnothing$，维护一个数据结构，要求支持以下操作：
- `1 hoc s`，令 $S_i=S_{hoc}\cup\{s\}$，其中 $s$ 是字符串（保证操作前 $s\notin S_{hoc}$） .
- `2 hoc s`，令 $S_i=S_{hoc}$，并查询 $S_i$ 中的所有字符串在给出的字符串 $s$ 中出现的次数之和 .

inputFormat:
第一行包含一个正整数 $q$，表示询问次数 .

接下来 $q$ 行，每行一个操作，格式见题目描述 .

outputFormat: 对于每个操作 2，输出一行答案 .

samples:
5
1 0 abc
2 0 abc
1 2 def
2 3 defg
2 1 abcd

hint:
### 样例解释

第三行中，询问版本 $0$ 中的串在 `abc` 中出现几次，因为版本 $0$ 为空，所以出现 $0$ 次 .

第五行中，询问版本 $3$ 中的串在 `defg` 中出现几次，因为版本 $3$ 有字符串 `def`，所以出现 $1$ 次 .

第六行中，询问版本 $1$ 中的串在 `abcd` 中出现几次，因为版本 $1$ 有字符串 `abc`，所以出现 $1$ 次 .

### 数据范围及约定

**「本题采用捆绑测试」**

- $\texttt{Subtask 1(10 pts)：} \displaystyle \sum|s_i|\le 1000$；
- $\texttt{Subtask 2(20 pts)：}$所有添加的字符串长度相同；
- $\texttt{Subtask 3(20 pts)：}$所有添加的字符串只包含一种字符；
- $\texttt{Subtask 4(20 pts)：}q\le 10^3$；
- $\texttt{Subtask 5(30 pts)：}$无特殊限制。

对于全部数据，$1\le q\le  5\times10^5$，$\displaystyle 1\le \sum_i|s_i|\le 10^6$ . 所有字符串仅含小写字母 .


title: 图的存储

description: 给定一个 $n$ 个顶点 $m$ 条边的无向图。请以邻接矩阵和邻接表的形式输出这一张图。

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

第二行开始，往后 $m$ 行，每行输入两个以空格隔开的正整数 $u,v$，表示 $u,v$ 顶点之间有一条边直接相连。

outputFormat:
首先输出 $n$ 行 $n$ 列的矩阵，以空格隔开每一行之间的数表示邻接矩阵。第 $i$ 行第 $j$ 列的数为 $1$ 则表示顶点 $i,j$ 之间有一条边直接相连；若为 $0$ 则表示没有直接相连的边。

再往后输出 $n$ 行。第 $i$ 行首先先输出一个整数 $d_i$，表示这个顶点的度数，再按照从小到大的顺序，依次输出与顶点 $i$ 直接相连的所有顶点。

hint:
样例的图如图所示：

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

数据保证，对于所有数据，$1 \leq n \leq 1000$，$1 \leq m \leq 10^5$，且图无重边无自环。


title: 【模板】拓扑排序 / 家谱树

description: 有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。

inputFormat: 第 $1$ 行一个整数 $N$（$1 \le N \le 100$），表示家族的人数。接下来 $N$ 行，第 $i$ 行描述第 $i$ 个人的后代编号 $a_{i,j}$，表示 $a_{i,j}$ 是 $i$ 的后代。每行最后是 $0$ 表示描述完毕。

outputFormat: 输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可。


title: 「WHOI-4」yadiw. Slua, gassp, lhtubs.

background: > If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

description:
小 F 有一个奇妙的数组 $a$，$a$ 中没有重复的元素，长度为 $n$，他使用`std::sort`将他排序了，认为它是有序的，所以他正在使用这样的方法进行二分查找。显然，能否查到只和数列的离散化结果有关，所以你可以直接把 $a$ 看作 $1\sim n$ 的一个排列。

```cpp
int search(int key) {
  int l = 1, r = n;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (a[mid] < key)
      l = mid + 1;
    else if (a[mid] == key)
      return mid;
    else
      r = mid - 1;
  }
  return -1;
}
```

不幸的是，小 W 为了让他戒掉万能头，在`bits/stdc++.h`中写了`#define sort random_shuffle`，这意味着 $a$ 实际是一个随机的排列。

现在，对于所有在 $1$ 到 $N$ 范围内的 $n$，以及所有在 $1$ 到 $n$ 范围内的 $k$，在 $a$ 数列的所有排列中，有几个可以正确地找到第 $k$ 小的元素 $key$（即返回值非 $-1$）？由于答案可能过大，请输出它对给定模数 $p$ 取模的结果。

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

outputFormat: $N$ 行，第 $n$ 行 $n$ 个正整数，代表在 $n$ 个元素中找 $k$ 能找到的方案数。

hint:
**数据范围**

**本题采用 Subtask 评测。**

- Subtask 1（$10$ pts）：$N=10$，$ p\ge998244352$；
- Subtask 2（$25$ pts）：$N=100$，$p\ge1009$ **且为素数**；
- Subtask 3（$25$ pts）：$N=400$，$p\ge1009$ **且为素数**；
- Subtask 4（$40$ pts）：$N=400$。

对于所有数据，$10\le N\le 400$，$ 2\le p\le998244353$。


title: 黑暗（Darkness）

description:
铃在一个黑暗的三维空间内寻找澪。这个空间可以表示为 $\{(x,y,z) \mid x \in[0,A],y \in [0,B],z\in [0,C] \}$。铃初始站在坐标为 $(A,B,C)$ 处，澪站在 $(0,0,0)$ 处。假设铃在 $(x,y,z)$ 处，她每次移动会**均匀随机**地尝试移动到 $(x-1,y,z)$ 或 $(x,y-1,z)$ 或 $(x,y,z-1)$。

这个空间的外围是墙壁，不可穿过。由于空间内很暗，铃并不知道自己是否走到了墙边。也就是说，她在随机选择三种方向尝试移动时，有可能撞在墙上。

铃想要知道，自己在第一次撞墙时，「到澪的曼哈顿距离（在本题中的情况就是 $x,y,z$ 坐标之和）」的 $k$ 次方的期望值。

你只需要求出答案对 $998244353$ 取模的结果。

inputFormat: 输入一行四个正整数 $A,B,C,k$。

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


title: [JRKSJ R8] C0mp0nents

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

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

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

description:
小 I 有一张 $n$ 个点、$m$ 条边的无向图，保证图无重边、无自环。初始时第 $i$ 个点的点权 $a_i = i$。小 I 有一个额外的常量 $k$。

小 R 可以进行很多很多次操作。每次操作，她选择图上两个相邻的节点 $x, y$ 满足 $\lvert a_x - a_y \rvert = k$，随后小 I 会将 $a_x$ 设为 $a_y$。

对每个 $1 \leq s \leq n$，**如果在过程中不修改 $\bm{a_x = s}$ 的节点 $\bm x$ 的权值**，小 I 想知道：若干次操作后，图上最多有多少个点满足 $a_i = s$。

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

接下来 $m$ 行，每行两个整数 $u, v$，依次表示一条连接 $u, v$ 的边。

outputFormat: 一行 $n$ 个整数，第 $i$ 个整数表示 $s = i$ 时的答案。

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

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

- Subtask 0（0 pts）：样例；
- Subtask 1（5 pts）：$n \leq 200$，$m \leq 400$；
- Subtask 2（20 pts）：$n \leq 5000$，$m \leq 10^4$；
- Subtask 3（25 pts）：$n \leq 10^5$，$m \leq 3\times 10^5$；
- Subtask 4（50 pts）：无特殊限制。

对于所有数据，满足 $1 \leq k \leq n \leq 4\times 10^5$，$1 \leq u, v \leq n$，$0 \leq m \leq 10^6$，保证图无重边、无自环。


title: 「WHOI-4」折纸

background: 吉尼斯记录：一张纸（如果接近 $4$ 公里的卫生纸可以算作一张纸）最多可以对折 $13$ 次。小 X 吹牛说打破了这个记录，但是吹太大了。

description:
小 X 向吉尼斯世界纪录组织申请了这个记录，但是他正好隔离在家，无法证明。他只好允许他们问 $t$ 个问题，确认他确实打破了记录。

他们每个问题可以要求小 X 把一张纸按照一个给定 $01$ 串 $s$ 的规则对折 $n$ 次后展开。对于第 $i$ 次折叠，如果 $s_i=0$，将纸从左到右对折，使左边对齐右边；如果 $s_i=1$，将纸从右到左对折，使右边对齐左边。对折全部是从上方翻。**接下来将会展开，展开后纸片在原位，只是保留了折痕。看看自己是否实现了这一点。**

他们想要知道，从左往右数第 $k$ 个折痕是峰折（向上突起的折痕）还是谷折（向下凹陷的折痕）。如果该询问的答案是峰折，输出 `Up`；否则输出 `Down`。请你帮帮可怜的小 X。

峰折，谷折的图示见样例解释。

inputFormat:
**本题采用多测。**

第一行一行一个正整数 $t$，代表数据组数。

接下来 $2t$ 行，每两行是一组数据。每组数据，第一行两个正整数 $n,k$。接下来一行一个长度为 $n$ 的 $01$ 串，代表 $s$。

outputFormat: $t$ 行，每行一个字符串，代表该组数据的答案。

hint:
**样例解释**

样例 #1 解释：

动态地址：[here](https://img-blog.csdnimg.cn/c68f2ba917504417b109eb1606f4a3a5.gif)。不知道为什么洛谷显示不了了。

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

由于技术原因，动图帧数略低。

样例 #2 请手动模拟。

**数据范围**

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

- Subtask 1（$20$ pts）：$t=10$，$1\le n\le5$；
- Subtask 2（$80$ pts）：$t=10^5$。

对于 $100\%$ 的数据，有 $1\le t\le 10^5$，$1\le n\le60$，$1\le k<2^n$。


title: [Ynoi2001] 雪に咲く花

background:
 何もいらない
 不再奢求什么
 あなたがいればいい
 只要有相伴
 そっと橫顏 息を殺す
 悄悄地侧着脸 屏住呼吸
 まばたきすれば
 似乎一眨眼
 消えてしまいそうで
 就会突然消失一般
 凝視(みつ)めさせて 好きだよ
 凝视着我喜欢的你

 あぁ 木々が震え 降り出した雪
 啊啊 树影摇曳 落雪纷纷
 足跡 ふたつ 白く
 唯留两行白色的足迹
 時よ 積もれ
 时光 点点堆积
 時よ 積もれ
 时光 点点堆积
 髪に 胸に ふたりだけの夢に
 在发间 在心中 只属于你我的梦中
 咲けない花の種は
 无法开出花朵的种子
 雪に抱かれ 寄り添うの
 在雪的怀抱中 相依相偎
 靜かに忘れられたい
 只想静静地被遗忘
![](https://cdn.luogu.com.cn/upload/image_hosting/g60pi7fc.png)

description:
给序列 $a_1,\dots,a_n$，$b_1,\dots,b_n$，$c_1,\dots,c_n$，

定义区间 $[l,r]$ 的价值为 $a_l,\dots,a_r$ 按位与，$b_l,\dots,b_r$ 按位或，$c_l,\dots,c_r$ 的最大公因数，这三者的乘积；

$m$ 次查询，每次查询给出区间 $[l,r]$，查询满足 $l\le l'\le r'\le r$ 的 $[l',r']$ 的价值之和。

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

第二行 $n$ 个整数 $a_1,\dots,a_n$；

第三行 $n$ 个整数 $b_1,\dots,b_n$；

第四行 $n$ 个整数 $c_1,\dots,c_n$；

接下来 $m$ 行，每行两个整数 $l,r$ 表示一次查询。

outputFormat: 共 $m$ 行，每行一个整数，表示对应的答案，答案对 $2^{32}$ 取模后输出。

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

对于 $100\%$ 的数据，满足

$1\le n\le 10^6$

$1\le m\le 5\times 10^6$

$1\le a_i,b_i,c_i\le n$

$1\le l\le r\le n$

建议使用高效的输入输出方式。


title: 数列前缀和 2

description: 给定一个长度为 $n$ 的数列 $a$，请回答 $q$ 次询问，每次给定 $l, r$，请求出 $\prod\limits_{i = l}^r a_i \bmod p$ 的值，其中 $p = 1,145,141$。

inputFormat:
第一行是两个整数，依次表示数列长度 $n$ 和询问次数 $q$。
第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。
接下来 $q$ 行，每行两个整数 $l, r$，表示一次询问。

outputFormat: 为了避免大量数据输出导致超时，请输出一行一个整数表示所有询问的答案的按位异或和。

hint:
### 样例 1 解释

三次询问的答案依次为 $6, 12, 24$，按位异或和为 $18$。

### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $n,q \leq 10^3$。
- 对于 $60\%$ 的数据，保证 $n, q \leq 10^5$。

对于全部的测试点，保证 $1 \leq n, q \leq 10^6$，$1 \leq l \leq r \leq n$，$1 \leq a_i < p$。

### 提示
你可以在[这里](https://www.luogu.com.cn/problem/P3811)学习如何线性求逆元，请尽可能做到 $O(1)$ 回答单次询问。


title: 数列前缀和 3

description:
给定模质数 $p$ 域上的 $k$ 阶非奇异矩阵列 $a$，给定 $q$ 次询问，每次给出 $l, r$，求 $\prod \limits_{i = l}^r a_i$。$p = 1145141$。

注：模 $p$ 域上的非奇异矩阵指：矩阵乘法加法均在模 $p$ 下进行，矩阵（在实数域下）的行列式值对 $p$ 取余不为 $0$。

inputFormat:
输入第一行有三个数，依次表示矩阵列长度 $n$、矩阵阶数 $k$ 以及询问数 $q$。

接下来 $n \times k$ 行，每行 $k$ 个整数，依次表示 $n$ 个 $k$ 阶矩阵，详见样例。

接下来 $q$ 行，每行两个整数 $l, r$，表示一次询问。

outputFormat: 为了避免输出过大，请输出一行一个整数，表示所有询问的答案的所有矩阵元素的按位异或和。


title: 送别（Farewell）

background:
还是到了离别的时候呢...... 相聚的时间很短暂，不知是否给了你一次美好的经历呢？

我举办这场比赛，还是想给自己留下一些珍贵的回忆。虽然自己的水平并不高，但这对我还是很有纪念意义。

经过长时间的准备，在这送别之际，应当更隆重一些的 —— 可惜我并没有那样的能力。若不然，也不会只能以这种程度的题目来压轴。

既然如此，就不要让此次分别成为永别...... 我将全力以赴，为了我们下次再会。这是我自私的请求，但请你等着我回来！

我这贫乏的语言，难以表述心中的情感。不如我们就这样，在离别前静静地享受这段时光吧。

description:
铃来到了一个奇妙的 Gnilrits 星球，上面生活着一种奇妙的 Gnilrits 人。

这种生物有除了 $k$ 个寿命无限但不能繁殖的个体以外，设其它人的总数在第 $i$ 年为 $a_i$，她得知有规律 $a_i=qa_{i-1}-a_{i-2}$，其中 $a_0=0$，$a_1=1$。

在第 $i$ 年，若 $a_i > k$，则星球上都会依次发生如下事件：

1. 全部 $a_i+k$ 个人被分配到 $a_i$ 个**相同的**住房内，不能有空房（每个人都是不同的）。

2. 每个房屋都修建一条单向道路，连接另一个房屋（可以是自己）；且对任意房屋，都要有一条连向它的道路。最终形成 $a_i-k$ 个环，包括自环。

需要注意的是，在第一步后因为房屋有不同的人居住，它们之间也就是不同的了。

铃想到了一个问题：设第 $i$ 年分配房屋并修建道路的总方案数为 $b_i$（若 $a_i \leq k$ 则 $b_i=0$），则 $i\in [0,n]$ 的所有 $b_i$ 之和是多少呢？

铃在思考这个问题时，她突然惊醒了过来 —— 原来刚才的只是一场梦。她正想和澪分享梦中的见闻，才想起以往在她身边的澪，如今已经离开了。

没有办法，但铃还是想知道问题的答案，请你帮忙求出来吧。结果可能很大，你只需要告诉她答案对 $998244353$ 取模的结果即可。

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

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

hint:
【样例 $1$ 解释】

在 $i \leq 2$ 时 $b_i=0$。

对于 $i=3$ 的情况，$a_i=3$。首先要将 $5$ 个不同的人分配入 $3$ 个相同的房屋，有 $25$ 种方案；再把 $3$ 个变得不同的房屋用环路连接，形成 $1$ 个环，只有 $2$ 种方案，故 $b_3 = 25 \times 2 = 50$。
（更具体的解释见[此处](https://www.luogu.com.cn/paste/usa2ggb4)）

对于 $i=4$，$a_i=4$，将 $6$ 个人分入 $4$ 个房屋有 $65$ 种方案；在 $4$ 个房屋间修路形成 $2$ 个环有 $11$ 种方案，总方案数为 $65\times 11 = 715$。

故答案为 $50+715=765$。

【数据范围】

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

Subtask 1（7 pts）：$1\le n\le 1000$，$1\le k \le 3$；
Subtask 2（11 pts）：$1\le n,k \le 100$；
Subtask 3（13 pts）：$1 \le k \le 1000$；
Subtask 4（19 pts）：$1\le k \le 32000$，$q=2$；
Subtask 5（23 pts）：$1\le k \le 16000$，$q \neq 2$；
Subtsak 6（27 pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le n \le 10^9$，$1\le k \le 64000$，$2\le q \le 10^9$。

【提示】
此题并不难，但可能需要一定程度的常数优化。