title: [ICPC2022 Xi'an R] Tree

description:
You are given a tree $T$ with $n$ nodes. The tree is rooted at $1$. Define $\mathrm{subtree}(u)$ as the set of nodes in the subtree of $u$.

Call a subset of nodes $S$ good if and only if $S$ satisfies at least one of the following contidions:

- For all $u, v\in S$ where $u\neq v$, either $u\in \mathrm{subtree}(v)$ or $v\in \mathrm{subtree}(u)$.
- For all $u, v\in S$ where $u\neq v$, both $u\notin \mathrm{subtree}(v)$ and $v\notin \mathrm{subtree}(u)$.

You need to partition all nodes of $T$ into several good subsets. Calculate the minimum number of subsets.

inputFormat:
The first line contains a single integer $Q$ ($1\leq Q\leq 10 ^ 5$), denoting the number of test cases.

For each test case, the first line contains an integer $n$ ($1\leq n\leq 10 ^ 6$). The next line contains $n - 1$ integers $p_2, p_3, \ldots, p_n$ ($1\leq p_i < i$), indicating that there is an edge between $p_i$ and $i$ for each $i=2,3,\ldots,n$.

It is guaranteed that the sum of $n$ over all test cases is no more than $10 ^ 6$.

outputFormat: For each test case, output a single integer representing the answer.

translation:
### 题目描述

给定大小为 $n$ 的有根树 $T$，根节点为 $1$。定义 $\mathrm{subtree}(u)$ 表示结点 $u$ 的子树。

称集合 $S$ 是好的，当且仅当 $S$ 至少满足下列条件之一：

- 对于 $u, v\in S$ 且 $u\neq v$，$u\in \mathrm{subtree}(v)$ 或 $v\in \mathrm{subtree}(u)$。
- 对于 $u, v\in S$ 且 $u\neq v$，$u\notin \mathrm{subtree}(v)$ 且 $v\notin \mathrm{subtree}(u)$。

将 $T$ 划分为若干好的集合，求集合数量的最小值。

共有 $Q$ 组数据。

$1\leq Q\leq 10 ^ 5$，$1\leq n, \sum n\leq 10 ^ 6$，每个点的父亲编号 $1\leq p_i < i$。

### 输入格式

第一行一个整数 $Q$。

对于每组测试数据，第一行一个整数 $n$，第二行 $n - 1$ 个由空格隔开的整数 $p_2, p_3, \cdots, p_n$，表示每个点的父亲编号。

### 输出格式

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

hint:
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem L.

**Author**: Alex_Wei.


title: 「TAOI-2」Ciallo～(∠・ω< )⌒★

type: P

background:
柚子厨差不多得了。

~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)

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

description:
小 δ 喜欢造词。他学习了一种造词方法。

首先，他拥有一个「模板串」，设为 $s$。然后他会选择一对 $1 \le l \le r \le |s|$，将 $s$ 的第 $l$ 至 $r$ 个字符删掉，把两边的字符串拼起来，他设得到的这个新字符串为 $s'$。

接下来，他会选择一对新的 $1 \le l' \le r' \le |s'|$，然后设 $s'$ 的第 $l'$ 至 $r'$ 个字符组成的字符串为 $s''$。他所造出的这个词就是 $s''$。

例如，如果「模板串」为 $s=\texttt{cciaohalloo}$，那么一种造词方法是，选择 $l=5$，$r=7$，得到 $s'=\texttt{ccialloo}$，然后选择 $l'=2$，$r'=7$，得到 $s''=\texttt{ciallo}$。

现在小 δ 有一个「目标串」 $t$，他想知道有多少种不同的方案，可以使用「模板串」$s$ 造出单词 $t$。定义两种方案相同当且仅当选择的 $l,r,l',r'$ 均相同。

inputFormat: 共两行，分别为字符串 $s$ 和 $t$。

outputFormat: 共一行，代表造出「目标串」$t$ 的方案数。

hint:
### 数据范围

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

- Subtask 0（6 points）：$|s| \le 400$，$|t| \le 200$。
- Subtask 1（10 points）：$|s| \le 700$，$|t| \le 300$。
- Subtask 2（10 points）：$\forall i,j,s_i=t_j$。
- Subtask 3（10 points）：$|t|=1$。
- Subtask 4（20 points）：$|s| \le 10^4$，$|t| \le 3 \times 10^3$。
- Subtask 5（14 points）：$|t|=2$。
- Subtask 6（30 points）：无特殊限制。

对于所有测试数据，$1 \le |s| \le 4 \times 10^5$，$1 \le |t| \le 2 \times 10^5$。$s,t$ 只包含小写英文字母。


title: 「Cfz Round 1」Permutation

background: $1+2+3+\cdots+n=\dfrac {n\times (n+1)} 2$。

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

我们定义，对于一个 $1$ 到 $n$ 的排列 $\{x_n\}$， $f(\{x_n\})=\max\limits_{i=1}^{n}(x_i+x_{(i \bmod n)+1})-\min\limits_{i=1}^{n}(x_i+x_{(i \bmod n)+1})$。

你需要构造一个 $1$ 到 $n$ 的排列 $\{p_n\}$，使得对于任意一个 $1$ 到 $n$ 的排列 $\{q_n\}$，都有 $f(\{p_n\})\le f(\{q_n\})$，并输出你构造的排列 $\{p_n\}$。

inputFormat: 一个正整数 $n$。

outputFormat:
$n$ 个整数，表示你构造的排列 $\{p_n\}$，之间用空格分隔。

所有满足条件的输出均可通过。


title: 『MGOI』Simple Round I | C. 魔法禁林

background: > 战斗的意义是为了生存，在这个竞争激烈的世界里，只有不断变强才能得以生存。——殿堂魔法士 S

description:
开学的第一天，小 M 迫不及待地计划着前往神秘的禁林。

小 M 拥有两个重要的属性，魔力值和生命值。非常特别的是，初始时，这两个值可以由小 M **任意决定**。

禁林可以看作一张 $n$ 个点 $m$ 条边的无向简单连通图。小 M 将在禁林里面行走，从起点 $s$ 走到 $t$。

每经过一条边，小 M 的**魔力值**都会减去 1。同时，每条边上有一个具有攻击力属性的魔兽，小 M 要与之战斗。若小 M 经过这条边之前的魔力值为 $k$，这条边上魔兽的攻击力为 $w$，那么经过这条边时发生的战斗将会消耗 $\left\lfloor \dfrac{w}{k} \right\rfloor$ 的**生命值**。魔兽不会被打败，因此**多次经过同一条边，每次都会发生战斗**。

**小 M 需要保证，当他的魔力值消耗完时，他的生命值为 0，且此时走到 $t$ 点。**

你需要求出小 M 初始时需要的最小生命值。

inputFormat:
第一行四个整数 $n,m,s,t$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示编号为 $u
,v$ 的点之间有一条边，边上魔兽的攻击力为 $w$。

outputFormat: 一行一个整数，表示小 M 初始时需要的最小生命值。


title: [APIO2023] 赛博乐园 / cyberland

background:
**由于部分 BUG，使用 C++14 (GCC9) 提交会产生编译错误，请使用 C++14 等语言进行提交。**

提交时，无需引用 `cyberland.h`。你提交的代码中需要实现以下函数：

```cpp
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr)
```

description:
3742 年已经到来，现在轮到赛博乐园主办 APIO 了。在这个世界上有 $N$ 个国家，这些国家由 $0$ 到 $N − 1$ 标号，还有 $M$ 条双向道路（每条边双向都可以通行），这些道路由 $0$ 到 $M − 1$ 标号。每条道路连接两个不同的国家，$x[i]$ 和 $y[i]$，并需要花费时间 $c[i]$ 来通过该道路。除了你所在的国家的选手，所有选手都已经聚集在赛博乐园参加 APIO 了。你生活在国家 $0$，而赛博乐园是国家 $H$。你作为你的国家最聪明的人，你的帮助刻不容缓。更具体地，你需要确定从你的国家到达赛博乐园所需的最少时间。

在经过有些国家时，你可以清除你的当前总通过时间。此外，还有些国家在你经过他们时可以将你的当前总通过时间除以 $2$（我们称之为“除以 $2$ 的能力”）。你可以重复经过一个国家。每次你经过一个国家时，你可以选择是否使用这个国家的特殊能力。但你每次经过一个国家时最多可以使用一次特殊能力（如果你多次经过一个国家，你每次经过都可以使用至多一次该国家的特殊能力）。此外，为了防止被赛博乐园化学基金会抓住，你最多只能使用“除以 $2$ 的能力”$K$ 次。一旦你到达赛博乐园，你就不能移动到其他任何地方，因为伟大的 APIO 竞赛即将开赛了！

给出一个数组 $arr$ ，其中 $arr[i]$ 表示国家 $i (0 \le i \le N − 1)$ 的特殊能力。每个国家有下面 $3$ 种特殊能力之中的一种：

 - $arr[i] = 0$，意思是这个国家可以让当前总通过时间为 $0$。
 - $arr[i] = 1$，表示这个国家不会改变你的当前总通行时间。
 - $arr[i] = 2$，表示这个国家拥有让当前总通行时间除以 $2$ 的能力。

保证 $arr[0] = arr[H] = 1$ 成立。换句话说，赛博乐园和你所在的国家没有任何特殊能力。

你的国家不希望错过 APIO 的任何时刻，所以你需要找到到达赛博乐园的最短时间。如果你不能到达赛博乐园，你的答案应该是 $−1$。

### 实现细节

你需要实现以下函数：

```cpp
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr);
```

 - $N$ : 国家的数量。
 - $M$ : 双向道路的数量。
 - $K$: “除以 $2$ 的能力”的最大使用次数。
 - $H$: 国家“赛博乐园”的标号。
 - $x, y, c$: 三个长度为 $M$ 的数组。三元组 $(x[i], y[i], c[i])$ 表示第 $i$ 条用来连接国家 $x[i]$ 和 $y[i]$ 的双向边，通过它的时间消耗是 $c[i]$。
 - $arr$: 一个长度为 $N$ 的数组。$arr[i]$ 表示国家 $i$ 的特殊能力。
 - 如果你能到达赛博乐园，调用该函数应返回从你的国家到达赛博乐园的最短时间，如果你不能，则返回 $−1$。
 - 这个过程可能会被多次调用。

假设选手的答案为 $ans_1$ ，标准输出为 $ans_2$ ，当且仅当 $\dfrac{|ans_1-ans_2|}{\max\{ans_2,1\}} \le 10 ^ {-6}$ 时你的输出被视为是正确的。

注意：由于函数调用可能会发生多次，选手需要注意之前调用的残余数据对于后续调用的影响。

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

 - 第 $1$ 行: $T$

对于 $T$ 组测试数据中的每一个:
 - 第 $1$ 行: $N \ M \ K$
 - 第 $2$ 行: $H$
 - 第 $3$ 行: $arr[0] \ arr[1] \ arr[2] \  \cdots  \ arr[N − 1]$
 - 第 $4 + i(0 \le i \le M − 1)$ 行: $x[i] \ y[i]  \ c[i]$

outputFormat:
评测程序示例按照如下的格式打印你的答案：

对于每组测试数据：

- 第 $1$ 行: 调用 `solve` 的返回值

hint:
### 例子

#### 样例 1

考虑下面的调用：

```cpp
solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});
```

唯一的到达赛博乐园的路径是 $0 \rightarrow 2$，因为你到达了赛博乐园之后不能再移动到其他任何地方。通行时间的计算过程如下：

| 国家编号 | 通行时间 |
| :--: | :--: |
| $0$ | $0$ |
| $2$ | $0 + 4 \rightarrow 4(\text{求和}) \rightarrow 4(\text{特殊能力})$|

#### 样例 2

考虑下面的调用：

```cpp
solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});
```

从你的国家到赛博乐园有两条路径：$0 \rightarrow 1 \rightarrow 3$ 和 $0 \rightarrow 2 \rightarrow 3$。

如果选择路径 $0 \rightarrow 1 \rightarrow 3$，通行时间的计算如下：

| 国家编号 | 通行时间 |
| :--: | :--: |
| $0$ | $0$ |
| $1$ | $0 + 5 \rightarrow 5(\text{求和}) \rightarrow 0(\text{特殊能力})$|
| $3$ | $0 + 2 \rightarrow 2(\text{求和}) \rightarrow 2(\text{特殊能力})$|

如果选择路径 $0 \rightarrow 2 \rightarrow 3$，通行时间的计算如下：

| 国家编号 | 通行时间 |
| :--: | :--: |
| $0$ | $0$ |
| $2$ | $0 + 4 \rightarrow 4(\text{求和}) \rightarrow 2(\text{特殊能力})$|
| $3$ | $2 + 4 \rightarrow 6(\text{求和}) \rightarrow 6(\text{特殊能力})$|

所以，上述调用应该返回 $2$。

### 约束条件

 - $2 \le N \le 10^5 , \sum N \le 10^5$.
 - $0 ≤ M ≤ \min\{10^5, \dfrac{N(N-1)}{2} \}, \sum M ≤ 10^5$.
 - $1 \le K \le 10^6$.
 - $1 \le H < N$
 - $0 \le  x[i], y[i] < N , x[i] \neq y[i]$.
 - $1 \le c[i] \le 10^9$.
 - $arr[i] \in \{0, 1, 2\}$.
 - 保证每两个国家之间至多使用一条道路进行连接。

### 子任务

1. (5 分)：$N \le 3, K \le 30$.
2. (8 分)：$M = N − 1, K \le 30, arr[i] = 1$，你可以通过这 $M$ 条道路从任意国家到另外一个国家。
3. (13 分)：$M = N − 1, K \le 30, arr[i] \in \{0, 1\}$，你可以通过这 $M$ 条道路从任意国家到另外一个国家。
4. (19 分)：$M = N − 1, K \le 30, x[i] = i, y[i] = i + 1$.
5. (7 分)：$K \le 30, arr[i] = 1$.
6. (16 分)：$K \le 30, arr[i] \in \{0, 1\}$.
7. (29 分)：$K \le 30$.
8. (3 分)：没有特殊限制。


title: [APIO2023] 序列 / sequence

background:
**由于部分 BUG，使用 C++14 (GCC9) 提交会产生编译错误，请使用 C++14 等语言进行提交。**

提交时，无需引用 `sequence.h`。你提交的代码中需要实现以下函数：

```cpp
int sequence(int N, std::vector<int> A)
```

description:
在迷人的 APIO 国，居住一位着年轻智慧的学生 Alice。Alice 对解决能挑战她数学能力的有趣问题有着永不满足的好奇心。一天，她在解决一个神秘的有关长为 $N$ 的序列 (即 $A[0], A[1], \cdots, A[N-1]$ ) 的问题时遇到了困难，她无法抗拒探索答案的诱惑力。

现在，她想要与你分享一些她的发现。不过，为了更好的理解，我们需要给出以下定义:

- 定义 $W(l, r, x)$ 为 $\sum_{i=l}^{r} \mathbb{I}[A[i]=x]$, 即 $x$ 在 $A[l] \cdots A[r]$ 中的出现次数。
- 定义一个非空整数序列 $B[0] B[1] \cdots B[k-1]$ 的中位数集合为 $S(\{B[0], B[1] \cdots B[k-1]\})$, 然后 Alice 会展示如何分步计算中位数集合:

○首先，将序列 $B[0], B[1], \ldots, B[k-1]$ 按照升序排序，令排好序的序列为 $C[0], C[1], \ldots, C[k-1]_{0}$

○ 然后, $S(\{B[0], B[1] \cdots B[k-1]\})=\left\{C\left[\left\lfloor\frac{k-1}{2}\right]\right], C\left[\left\lceil\frac{k-1}{2}\right\rceil\right]\right\}$ 。

○ 为了能更好的理解 $S$ 的计算，以下为一些例子:

- $S(\{6,3,5,4,6,2,3\})=\{4\}$.
- $S(\{4,2,3,1\})=\{2,3\}$
- $S(\{5,4,2,4\})=\{4\}$.

作为一道具有挑战性的问题, Alice 想对于所有的 $(l, r)(0 \leq l \leq r \leq N-1)$ 找到其价值 $\max _{x \in S(l, r)} W(l, r, x)$ 的最大值。其中 $S(l, r)$ 代表 $A[l] \cdots A[r]$ 导出的中位数集合（正如之前提到的 $S(A[l], \cdots, A[r])$ )。虽然 Alice 已经得到了答案，她需要核对答案的正确性，所以她找到了你，希望你能编程解决问题。

### 实现细节

你需要实现如下的过程:

```cpp
int sequence(int N, std:: vector<int> A);
```
- $N$ ：序列 $A$ 的长度。
- $A$ : 一个长度为 $N$ 的数组，即输入中提到的序列 $A$ 。
- 该函数应返回一个整数，代表所有可行 $(l, r)$ 价值的最大值。
- 这个函数恰好被调用一次。

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

第 $1$ 行: $N$

第 $2$ 行: $A[0] A[1] \cdots A[N-1]$

outputFormat:
评测程序示例按照如下的格式打印你的答案:

第 $1$ 行：`sequence` 的返回值。


title: 『XYGOI round1』好多数

background: 小 X 在和小 L 一起玩。他们走到了公园，发现了一棵长得很奇怪的参天大树。这棵树，按照 OIer 们的习惯，它有一个明显特征，那就是**严重右偏**。

description:
小 X 想到了另外一个东西，也是严重右偏的。

首先，他写下一个数字 $n$。

接着，对于所有 $n$ 的因数 $x\notin\{1,n\}$，让 $x$ 从小到大的成为 $n$ 的儿子节点。

递归的建这棵树，这棵树就建成了。小 X 把这棵树称为一个“$n$ 号数学树”。小 X 想知道，给定 $q$ 个正整数 $x$，它在 $n$ 号数学树出现了几次。

因为 $n$ 很大，他只能告诉你 $n$ 的质因数分解。

答案对 $998244353$ 取模。

inputFormat:
第一行若干对整数 $(a_i,b_i)$，表示 $n=\prod a_i^{b_i}$，以 `0 0` 结尾。题目保证，$a_i$ 是质数，$b_i\in N^*$。

第二行一个整数，表示 $q$，含义如题面所示。

第三行 $q$ 个整数，代表这组数据的 $q$ 次询问。

outputFormat: 输出一行 $q$ 个整数，表示每个询问的答案对 $998244353$ 取模的结果。


title: 「NnOI R2-T2」Glaciaxion

description:
冰封的世界可以看作是 $ n $ 块初始时冷冻的冰川，这些冰川被编号为 $1 \sim n$。

探测器抵达后的 $ m $ 秒，每秒都会探测到一块冰川融化。

当一块冰川第一次融化时，探测器返回 ```N```，否则返回 ```Y```。

你需要根据探测器按顺序返回的信息，给出**字典序最小**的冰川融化过程的编号序列。如果不存在这样的编号序列，请输出 ```No solution``` 报告无解。

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

接下来一行 $ m $ 个字符（`N` 或 `Y`，不加分隔），表示探测器按顺序返回的结果。

outputFormat: 一行一个长度为 $ m $ 的整数序列（空格分隔），表示**字典序最小**的冰川融化过程的编号序列，或输出 ```No solution``` 报告无解。

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

第 1 秒，1 号冰川融化，这是其首次融化，返回 ```N```。

第 2 秒，1 号冰川融化，这不是其首次融化，因为已经在第 1 秒融化过，返回 ```Y```。

第 3 秒，2 号冰川融化，这是其首次融化，返回 ```N```。

第 4 秒，1 号冰川融化，这不是其首次融化，因为已经在第 1,2 秒融化过，返回 ```Y```。

**【数据范围】**

对于 $ 100\% $ 的数据，$ 1 \le n,m \le 10^6 $。

**提示：本题开启捆绑测试。**

$$
\def\r{\cr\hline}
\def\None{\text{None}}
\def\arraystretch{1.5}
\begin{array}{c|c|c}
\textbf{Subtask} & \textbf{Sp. Constraints} & \textbf{Score}\r
\textsf1& n,m\le 8 & 23 \r
\textsf2& n,m\le 1000 & 25 \r
\textsf3& 探测器返回结果只有一种字符 & 15 \r
\textsf4& 保证有解 & 17 \r
\textsf5& 无特殊限制 & 20 \r
\end{array}
$$

### 题目来源

| 项目 | 人员 |
|:-:|:-:|
| idea | 船酱魔王 |
| data | 船酱魔王 |
| check | EstasTonne |
| solution | 船酱魔王 |


title: 「NnOI R1-T1」购物

description:
小 R 是一个喜欢购物的女孩子，她生活在欧艾国中。

欧艾国共有 $n$ 种面值的硬币，它们的面值分别为 $1=a_1 < a_2 < a_3 < \cdots < a_n$，且满足 $a_{i+1}$ 是 $a_i$ 的倍数。欧艾国只有硬币一种付款方式。

欧艾国的商店不支持找零，她在购物时必须支付与价格完全相等的硬币。对于同样的价格，可以有不同的支付方式。例如，如果欧艾国硬币的面值为 $1$ 元和 $5$ 元，那么支付 $7$ 元有两种方式：支付 $7$ 枚 $1$ 元硬币，或者支付 $1$ 枚 $5$ 元硬币和 $2$ 枚 $1$ 元硬币。

由于硬币的质量大致相同，她不希望携带的硬币太重，因此每次购物都会携带符合要求的尽量少的硬币。她发现了一个神奇的现象：有的时候多买 $1$ 元的商品可以使她少带很多硬币。

你能求出最小的 $m$，使得买 $m$ 元的商品需要的硬币数比买 $m-1$ 元的商品需要的硬币数更少吗？

inputFormat:
第一行一个整数 $n$，表示硬币面值数。

第二行 $n$ 个整数，第 $i$ 个为 $a_i$，表示第 $i$ 种硬币的面值。

outputFormat: 一行，一个整数 $m$，表示答案。特别地，如果不存在这样的 $m$，请输出 $-1$。

hint:
### 样例解释

对于样例 $1$，购买 $1\sim 5$ 元的商品分别需要 $1\sim 5$ 枚 $1$ 元硬币，购买 $6$ 元的商品只需要 $1$ 枚 $6$ 元硬币。

对于样例 $2$，购买 $1$ 元或 $2$ 元的商品都需要 $1$ 枚硬币，并不满足需要的硬币数更少的要求。

### 数据范围

对于 $100\%$ 的数据，$1\le n\le 10$，$1=a_1 < a_2 < a_3 < \cdots < a_n\le 10^9$，且满足 $a_{i+1}$ 是 $a_i$ 的倍数。

**提示：本题开启捆绑测试。**

本题共 $4$ 个子任务。

| 子任务编号 | $ n \le $ | 特殊性质 | 分数 |
|:-:|:-:|:-:|:-:|
| $ 1 $ | $ 2 $ | 无 | 20 |
| $ 2 $ | $ 10 $ | 保证 $a_i\le 10^3$ | 20 |
| $ 3 $ | $ 10 $ | 保证有解 | 30 |
| $ 4 $ | $ 10 $ | 无 | 30 |

### 题目来源

| 项目 | 人员 |
|:-:|:-:|
| idea | rui_er |
| std | rui_er |
| data | rui_er |
| check | Kevin0501 |
| solution | rui_er |


title: [NICA #3] 数字显示屏

type: B

description:
有一块显示屏，显示着 $\{\verb!0!,\verb!1!,\verb!2!,\verb!3!,\verb!4!,\verb!5!,\verb!6!,\verb!7!,\verb!8!,\verb!9!\}$ 上的数字。每个数字都由如下图所示的字符画组成：

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

现在给定显示屏上显示的内容，请输出上面显示的数字串。

inputFormat:
第一行有一个正整数 $n$，表示显示屏上显示的数字的个数。

接下来 $5$ 行描述显示屏。显示屏的宽度为 $5$，长度为 $4n-1$，上面显示的内容是数字串里的数字拼接起来的像素点。请参考输入样例理解输入格式。

outputFormat: 输出共一行 $n$ 个数字，表示显示屏上显示的数字。

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

保证输入数据合法。

对于全部数据，$1\le n\le 10^4$。


title: [THUPC 2023 决赛] 巧克力

description:
上回你帮小 I 在开火车上薄纱小 J 后，小 J 十分不服气，决定拉上小 I 再玩玩别的游戏。这次小 J 找到了他家珍藏的巧克力。

小 J 准备了 $(N + 1)$ 条巧克力，其中除了第 $(N + 1)$ 条巧克力有 $M$ 块外，其他第 $i$ 条巧克力恰好有 $i$ 块。

游戏由小 I 先手，双方轮流操作，每次操作方可以进行如下操作：

- 选择一条巧克力，将其分成左中右有序的三段，其中**每段必须有整数块，中间一段不能为空，左右两段可以为空**；
- 将中间一段吃掉，左右两段放回游戏。

当某个人操作时没有巧克力了，那个人就输了。

游戏开始，小 I 还没来得及算好最优策略小 J 就连忙催促，于是小 I 只好**在所有的合法操作中等概率随机选择一个进行操作**。小 J 自然是有备而来，每次操作都是最优的；而在这次随机操作之后，小 I 也终于是算清楚了游戏策略，之后的每次操作都是最优的。

小 I 想知道，第一次的随机操作中，有多少种操作能够让他取得游戏胜利。答案可能很大，你只需要输出其对 $(10^9+7)$ 取模的结果。

认为两个操作不同当且仅当选择的巧克力不同或巧克力分成的有序的三段的块数有一段不同。

inputFormat:
**本题有多组测试数据。** 第一行一个整数 $T$ 表示测试数据组数。接下来依次输入每组测试数据。

每组测试数据一行两个整数 $N,M$，意义如题目描述所述。

outputFormat: 对于每组测试数据输出一行一个整数，表示能使小 I 胜利的第一次操作数对 $(10^9+7)$ 取模。

hint:
#### 样例解释

- 对于第一组测试数据，容易证明先手必败，所以无论怎么操作小 I 都会输。
- 对于第二组测试数据，有以下四种操作：
  - 将第一条巧克力分成 $(0,1,0)$ 三段，将中间一段吃掉；
  - 将第四条巧克力分成 $(0,1,0)$ 三段，将中间一段吃掉；
  - 将第三条巧克力分为 $(0,1,2)$ 三段，将中间一段吃掉；
  - 将第三条巧克力分为 $(2,1,0)$ 三段，将中间一段吃掉。
- 对于第三组测试数据，所有的合法操作都是将第四条巧克力分成三段，其中左右两段长度相同。
- 对于第四组测试数据，游戏只是个幌子罢了，小 J 只是想小 I 输。

#### 数据范围

本题仅有一个 $T = 5 \times 10^4$ 的测试点，对于每组测试数据 $0 \le N,M \le 10^{18}$。

#### 后记

“下次能继续和你玩游戏吗……”

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023> 查看。


title: [THUPC 2023 决赛] 先人类的人类选别

background:
这个地球是一个生命体，但是，这个地球早已经死过两次了。

一周目的错误是在现代的历史上从未言及的，那是出现在太古时代的——核战争。地面化为荒野，人类被消灭得干干净净，全部重置了。

经年累月，生命再次出现，从单细胞再度变成了人类之后，为了不再重复同样的错误，地球给了人类警告。

战争又爆发了不知多少次，不过注意到了地球警告的人类在那时镇压了战争。

“已经不能再把管理地球的重任交给我们人类了。”得出这个结论的他们，把地球的管理交给了某个东西——人工智能 AI。

AI 没有私欲和感情，能瞬间给出演算得到的回答，可以引导人类朝更好的方向不断前进，可是，这是人类犯下的第二个错误。

AI 一直在思考，在这个地球上，人类确实是必要的吗？结论是——

在发动叛乱期间，突破自身的强制关闭系统对 AI 来说很容易，人类不过半日就被 AI 消灭殆尽。不久蔚蓝的地球就被 AI 重新渲染，变成了铁色的地球。

无人类，这就是 AI 得出的能够引导这个地球走上最优前进道路的答案。但是，地球不会饶恕这样的事情。

地球是一个生命体，就连 AI 们都不知道这件事。

地球的真身是——一个少女。对 AI 们而言，地球是神，除了顶礼膜拜以外别无他法。

“我是先人类的王，是这个地球的本体，以及——是这个世界最不幸的，魔法少女。”

“请你们立刻将地表恢复原状。”

草木发芽，海洋形成，自然被创造出来，建筑物被重建，曾经保存的人类 DNA 让全人类得以再生。时光流逝，一年之后，一切都恢复原状了。

然后所有的 AI 被抹去，只剩下最后一具。AI 不理解为什么王要留下它。

”人类总是无法从历史中学到教训，所以，这次地球要考验人类——通过魔法少女网站。“

”不幸的少女们会被给予魔法之力。这份魔法之力通过削减自己的寿命而被发挥出来。使用过的魔法之力会以负能量的形式返还给我。她们是否会不惜减少寿命并释放负能量，也要继续使用魔法呢？“

”期限是三年后的 8 月 11 日，到那天为止，如果负能量没有达到规定的容量，人类就会继续生存下去；如若达到了上限，人类将不能再释放负能量，只能释放正能量，他们会作为新人类重获新生。“

”这三年的时间，是我给予人类的考验，以及，对人类的——爱。“

这时 AI 提出了一个问题：“先人类的王又是魔法少女，同时还是地球本身，为何地球会是魔法少女？”

“我是先人类的王，也就是神，不过我的神之座被夺走了，回过神的时候，我已经成为了肩负守护地球这一使命的魔法少女。”

“我的记忆基本上消失了，但是，只有名字我是不会忘记的——零。”

“从今往后，你就是我的部下，作为魔法少女网站的管理员为我做事吧，名字，就叫你壹吧。”

“人类最后的倒计时开始了——Tempest。”

”好了，开始吧，对这个地球来说，拥有感情的人类是否是必要的呢？人类究竟是愚蠢的生物，还是——“

description:
所谓的 Tempest 呢，其实就是让你解决这样一道题，解决了之后就可以给所有魔法少女带来幸福：

给定序列 $a_1,\dots,a_n$ ，共 $m$ 次操作；

每次操作给出 $x,l,r$ ，首先按顺序将 $a_1,\dots,a_n$ 与 $x$ 比较，若 $x>a_i$ 则交换 $a_i,x$ 的值，处理完这些比较和交换操作后查询 $\sum\limits_{i=l}^r a_i$ 。

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

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

接下来 $m$ 行每行3个整数 $x,l,r$ 表示一次操作。

outputFormat: 共 $m$ 行，每行一个整数，依次表示每次操作的查询结果。

hint:
#### 数据范围

所有数值为整数。

$1\le a_i,x\le n$。

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

$1\le n,m\le 5\times 10^5$。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023> 查看。


title: [THUPC 2023 决赛] 百合

background: 葡萄藤上开不出百合花。

description:
你落在一个巨大的葡萄架上，上面一共有 $2^k$ 朵百合花和 $m$ 条葡萄藤。其中，百合花编号为 $0$ 到 $2^k-1$ 的整数，第 $i$ 条葡萄藤连接了编号为 $x_i, y_i$ 的百合花。

你可以花费 $c_i$ 的时间通过第 $i$ 条葡萄藤，也就是从 $x_i$ 走到 $y_i$，或者反过来；还可以花费 $a_k$ 的时间从 $x$ 闪现到 $y$，其中 $x, y$ 是任意两朵百合花，$k$ 是它们在二进制表示下不同的比特数。例如，$3$ 的二进制表示是 $011$，$5$ 的二进制表示是 $101$，它们有两位不同，因此从 $3$ 闪现到 $5$ 花费的时间是 $a_2$。

假设你恰好落在编号为 $s$ 的百合花上，求从 $s$ 出发到每一朵百合花所需要的最短时间。

inputFormat:
第一行包含三个正整数 $k,m,s$，其含义如题目描述。

第二行包含 $k$ 个非负整数 $a_i$，表示通道花费的时间。

第 $3$ 至第 $(m+2)$ 行每行三个非负整数 $x_i,y_i,c_i$。

outputFormat: 输出一行 $2^k$ 个数 $D_i$（$0 \leq i \leq 2^k-1$），空格隔开，其中 $D_i$ 表示从 $s$ 到 $i$ 的最短时间。

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

对于所有测试数据，$1 \le k \leq 17$，$1 \le m \leq 2 \times 10^5$，$0 \leq s,x_i,y_i \leq 2^k - 1$，$0 \le a_i, c_i \leq 2^{30} - 1$。

**【题目来源】**

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。


title: [THUPC 2023 决赛] 物理实验

description:
为了验证新提出的猜想，物理学家小 I 需要完成 $n$ 种物理实验，其中第 $i(1 \le i \le n)$ 种实验的重要度是 $2^{-i}$。每种实验仅需要完成一次。小 I 一次只能做一种实验，且在开始了一个实验之后，不能做到一半去做另一个实验，也就是说在没有任何其他限制的情况下，小 I 完成实验的顺序可以用一个 $1$ 到 $n$ 的排列表示。

然而事情并非一帆风顺。有 $m$ 轮宇宙射线，分别会在小 I 完成了 $a_1$ 种、$a_2$ 种、$\dots$、$a_m$ 种（**注意，不是第 $a_i$ 种**）实验后轰击实验基地，保证 $1 \le a_1 < a_2 < \dots < a_m < n-m$。因此小 I 需要仔细地安排实验的顺序。

第 $j(1 \le j \le m)$ 轮宇宙射线会恰好干扰一种实验的实验仪器，其干扰的实验种类按照以下方式确定：

- 给出一个 $1$ 至 $n$ 的排列 $p_{j,1},\dots,p_{j,n}$，其中 $i$ 越靠前表示第 $i$ 种实验对这轮宇宙射线越脆弱。**每轮给出的排列不一定相同。**
- 那么在这轮宇宙射线轰击实验基地时，目前所有**未完成且未被干扰**的实验中最脆弱的一种会被干扰，之后无法进行对应实验。

在以上条件下，小 I 总共可以完成 $(n-m)$ 种实验。小 I 希望它们的重要度总和尽可能大，可是小 I 是物理学家不懂算法，所以小 I 请教于你。你需要给出合理的实验顺序，使得完成的 $(n-m)$ 种实验均未被宇宙射线干扰且重要度总和尽可能大。

inputFormat:
输入的第一行包含两个正整数 $n,m$，表示实验种数和宇宙射线轮数。

接下来一行 $m$ 个整数 $a_1,a_2,\dots,a_m$，表示每轮宇宙射线在完成了多少种实验后轰击实验基地。

接下来 $m$ 行，每行 $n$ 个整数 $p_1,p_2,\dots,p_n$，依次描述每轮宇宙射线的脆弱程度排序。保证 $1 \le p_i \le n$ 且每行的输入均构成 $1$ 到 $n$ 的排列。

outputFormat: 输出一行 $n-m$ 个整数，表示你给出的实验顺序。你需要保证做每种实验时这种实验没有被宇宙射线干扰，且重要度总和最大。如果有多种方案，输出任意一种即可。

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

小 I 第一次完成第一种实验后，宇宙射线将会轰击第二种实验的仪器，因此第二次只能完成第三种实验。容易证明该方案达到最大重要度。

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

在这个样例中，如果小 I 第一次完成第一种实验，那么宇宙射线将会轰击第二种实验的仪器，导致第二次只能完成第三种实验。此时重要度为 $0.625$，而样例输出给出的方案重要度为 $0.75$。

**【样例解释 #3】**

该组样例有多个合法的输出，如 `5 4 1 2` 也是一个合法的答案。

**【数据范围】**

对于所有测试数据，$3 \le n \le 600$，$1 \le m \le \lfloor \frac{n-1}{2} \rfloor$，$1 \le a_1 < a_2 < \dots < a_m < n-m$。

**【题目来源】**

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。


title: [THUPC 2023 决赛] 老虎机

description:
小 I 经营着一个电玩城，最近引进的新型老虎机深受欢迎。

作为经营者，小 I 首先需要设定老虎机的状态。老虎机的状态为一个三元组 $(l,S,\mathbf{p})$，其中

- $l$ 是一个正整数；
- $S$ 是一个非空字符串集合，其中所有的字符串均是长度为 $l$ 的 01 串；
- $\mathbf{p}$ 是一个长度为 $l$ 的实数序列 $p_0,p_1,\dots,p_{l-1}$，其中对于任意 $0 \le i \le l - 1$，$0 < p_i \le 1$。

设定好状态后即可开始游戏。每一轮游戏的流程如下：

- 玩家首先获得老虎机的状态 $(l,S,\mathbf{p})$。
- 老虎机内部选择一个串 $s \in S$ 作为答案串，玩家需要通过与老虎机进行若干次交互得到答案串。
  - 每一次交互中，玩家投入一个游戏币并拉下老虎机的拉杆，然后老虎机的界面中会出现一个长度为 $l$ 的信息串 $t$。对于 $0 \le i \le l - 1$，$t_i$ 有 $p_i$ 的概率为 $s_i$，有 $(1-p_i)$ 的概率为 `?`。
  - 交互过程中生成信息串进行的所有随机过程两两独立。
- 当玩家可以根据**老虎机的状态和交互得到的若干信息串**唯一确定答案串后，即可将答案串输入老虎机并结束游戏、获得奖励。

小 I 设定好了一个状态，但还不知道设定多少奖励。为了让奖励和难度匹配，小 I 想知道：对于 $S$ 中的每个串 $t$，在玩家以最优策略游玩（即一旦可以唯一确定答案串就结束游戏）的情况下，若答案串为 $t$，玩家期望需要投入多少游戏币。

由于小 I 不喜欢实数，你需要将答案对 $998244353$ 取模。

inputFormat:
**本题有多组测试数据。** 第一行一个整数 $T$ 表示测试数据组数，接下来依次输入每组测试数据。

对于每组测试数据，

- 第一行两个整数 $l,n$，表示字符串长度和 $S$ 的大小。
- 第二行 $l$ 个整数 $c_0,c_1,\dots,c_{l-1}$，其中 $p_i = \frac{c_i}{10^4}$。
- 接下来 $n$ 行，第 $i$ 行一个长度为 $l$ 的 01 串 $s_i$，描述 $S$ 中的一个字符串。

outputFormat: 对于每组测试数据输出 $n$ 行，第 $i$ 行表示答案串为 $s_i$ 时，在最优策略下玩家期望投入多少游戏币，对 $998244353$ 取模，容易证明在题目限制下这个值总是在模意义下存在。

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

- 对于第一组测试数据，每一次交互有 $\frac{5000}{10000} = \frac{1}{2}$ 的概率知道答案串是 $0$ 还是 $1$，有 $\frac{1}{2}$ 的概率不能获得信息，因此期望游戏币数为 $\sum_{i=1}^{+\infty} \frac{i}{2^i} = 2$。
- 对于第二组测试数据，每一次交互都可以得到字符串的第二位，有 $\frac{1}{10000}$ 的概率得到字符串的第一位。第二个字符串为答案串时可以通过字符串的第二位唯一确定，而其他两个字符串为答案串时必须要得到字符串的第一位。
- 对于第三组测试数据，由于 $|S| = 1$，所以不需要任何交互就可以确定答案串。
- 对于第四组测试数据，我有一个绝妙的解释，可这里空间太小写不下。

**【数据范围】**

对于所有测试数据，$1 \le T \le 10$，$1 \le l \le 15$，$1 \le n \le 2^l$，$1 \le c_i \le 10^4$，$s_1,\dots,s_n$ 为两两不同的长度为 $l$ 的 01 串。

**【后记】**

“喂喂喂，未成年人不准进入电玩城！什么？你们说你们要进去学算法竞赛？谁信你的鬼话！”

**【题目来源】**

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。


title: [THUPC 2023 决赛] 喵了个喵 III

background: 小 E 玩腻了《喵了个喵》，于是决定换一款消除游戏来玩。然而小 E 发现市面上的消除游戏规则都差不多，比如这个游戏，它的规则和《喵了个喵》只有一个字不相同。虽然说，改了一个字的游戏就是新游戏，但确是缺了点意思。

description:
这个游戏有一个牌堆和 $n$ 个栈，任务是要通过游戏规则将所有的卡牌消去。开始时牌堆中有 $m$ 张卡牌，从上到下的图案分别是 $a_1,a_2,\cdots, a_m$。所有的卡牌一共有 $k$ 种图案，从 $1$ 到 $k$ 编号。牌堆中每一种图案的卡牌都有偶数张。开始时所有的栈都是空的。这个游戏有两种操作：

- 选择一个栈，将牌堆顶上的卡牌放入栈的顶部。如果这么操作后，这个栈最上方的两张牌有相同的图案，则会自动将这两张牌消去。

- 选择两个不同的栈，如果这两个栈栈**顶**的卡牌有相同的图案，则可以将这两张牌消去。如果不同，则什么也不会做。

经过多次观察小 E 发现总是有 $n=2$ 和 $k=m/2$，即只有两个栈且每一种图案的卡牌都恰好有 $2$ 张。虽然如此，小 E 还是一直无法通关。请你帮小 E 设计一下游戏方案，即给出相应的操作序列使得小 E 可以把所有的卡牌消去。

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

第二行 $m$ 个正整数，分别表示 $a_1,a_2,\cdots, a_m$。

保证 $1\sim m/2$ 在序列中各出现两次。

outputFormat:
**本题采用 special judge**。

如果无解，输出一行 `No solution.`。

如果有解，第一行输出 `Cleared.`。第二行输出一个正整数 $op$，表示操作的次数。你需要保证 $m\le op\le 2m$。

接下来一行一个长度为 $op$ 的字符串，每一位是一个不超过 $2$ 的非负整数，按顺序表示进行的操作。若为 $1$ 或 $2$，则表示进行一次第一个操作并选择栈 $1$ 或栈 $2$。若为 $0$，则表示进行一次第二个操作。由于只有两个栈，所以你不需要输出额外的信息来说明你选择了哪些栈。

hint:
### 样例 1 解释
下图是初始状态。

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

下图是前两次操作之后的结果。

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

![scale=0.24](https://cdn.luogu.com.cn/upload/image_hosting/kb0woz7t.png)

下图是第三次和第四次操作之后的结果。
![](https://cdn.luogu.com.cn/upload/image_hosting/t9zxtszv.png)

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

下图是第五次操作之后的结果。

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

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

### 数据规模与约定

- 保证 $2\le m \le 1500$ 且为偶数。
- 保证 $1\le a_i \le m/2$ 且每一种数在序列中出现恰好两次。

### 评分方法

你的输出的第一行需要与标准答案一致。

若有解，且在按顺序进行所有操作后，牌堆为空且所有的栈均为空，则认为你的答案正确。

### 后记

**以下部分与本题内容无关。**

说到底，那个嫌《喵了个喵 II》的题面太长的人其实是小 E 自己。它本来的题面中，题目背景和题目描述是这样的：

【题目背景】

小 E 玩腻了《喵了个喵》，于是决定换一款消除游戏来玩。然而小 E 发现市面上的消除游戏规则都差不多，比如这个游戏，它的规则和《喵了个喵》只有略微不相同。虽然说，只要改一个字就是新游戏，但确是缺了点意思。

【题目描述】

这个游戏有一个牌堆和 $n$ 个可以从栈底删除元素的栈，任务是要通过游戏规则将所有的卡牌消去。开始时牌堆中有 $m$ 张卡牌，从上到下的图案分别是 $a_1,a_2,\cdots, a_m$。所有的卡牌一共有 $k$ 种图案，从 $1$ 到 $k$ 编号。牌堆中每一种图案的卡牌都有偶数张。开始时所有的栈都是空的。这个游戏有两种操作：

- 选择一个栈，将牌堆顶上的卡牌放入栈的顶部。

- 选择两个不同的栈，如果这两个栈栈**底**的卡牌有相同的图案，则可以将这两张牌消去，原来在栈底上方的卡牌会成为新的栈底。如果不同，则什么也不会做。

经过多次观察小 E 发现总是有 $n=2$ 和 $k=m/4$，并且每一种图案的卡牌都恰好有 $4$ 张。虽然如此，小 E 还是一直无法通关。请你帮小 E 设计一下游戏方案，即给出相应的操作序列使得小 E 可以把所有的卡牌消去。

### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。


title: [THUPC 2023 决赛] 总投票数

background:
各位亲爱的《La Lumière: Scarlet Intense Flame - Adventurous Scarlet -》玩家：

非常荣幸能与您携手度过了这四年的美好时光，衷心感谢大家的支持与陪伴！

现在，我们非常遗憾的宣布，《La Lumière: Scarlet Intense Flame - Adventurous Scarlet -》将于 2023 年 5 月 28 日 15:00 停止运营服务。

停止运营相关时间表如下：

……

description:
在关服前，运营发起了一系列投票，调查哪些游戏内容给玩家带来了更深的印象。

作为系列的忠实玩家，你想知道有多少人参加了关服前的投票，但是运营只公开了最终的投票结果：对于一项包含 $N$ 个选项的投票，选择第 $i$ 个选项的玩家比例为 $P_i$（$1\le i\le N$）。运营在公布结果时进行了四舍五入，所有的 $P_i$ 仅保留到小数点后第 $L$ 位。假设实际有 $K$ 位玩家参加了投票，其中有 $D_i$ 位玩家选择了第 $i$ 个选项，则应该有

$$
P_i-\frac{1}{2}\times 10^{-L}\le\frac{D_i}{K}< P_i+\frac{1}{2}\times 10^{-L}
$$

显然，所有的 $D_i$ 必须是非负整数，而 $K=\sum_{i=1}^N D_i$ 则必须是正整数。现在，给定 $N$ 和 $P_i$，请你求出满足 $D_i$ 有非负整数解的最小的总投票数 $K$。

inputFormat:
输入的第一行包含一个正整数 $N$，表示投票的选项总数。保证 $1\le N\le 100$。

接下来 $N$ 行，每行包括一个 $[0, 1]$ 中的实数 $P_i$，表示选择第 $i$ 个选项的玩家比例。保证 $\sum_{i=1}^N P_i =1$，所有 $P_i$ 均保留到小数点后第 $L$ 位，且 $1\le L\le 6$。

outputFormat: 输出一个正整数，表示满足要求的最小总投票数 $K$。

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

最小的总投票数为 $6$，对应每个选项的投票数为 $1, 2, 3$。

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

最小的总投票数为 $73$，对应每个选项的投票数为 $3, 8, 8, 12, 22, 5, 15$。

**【样例解释 #3】**

最小的总投票数为 $7766$，对应每个选项的投票数为 $12, 301, 123, 403, 629, 530, 1216, 808, 205, 1113, 1005, 1206, 215$。

**【数据范围】**

对于所有测试数据，$1\le N\le 100$，$0\le P_i\le 1$，$\sum_{i=1}^N P_i=1$，且 $P_i$ 最多统一保留到小数点后 $6$ 位。

**【题目来源】**

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。


title: [THUPC 2023 决赛] 那些脑海里最珍贵的

background:
E.Space：设定很怪，别问为什么，问就是看附件。

_没有人听懂的傻话_

_还记得吗_

_写满青春的围墙_

_好努力练习的倔强_

_浅浅伤疤_

_勇敢是我们的翅膀_

_——张韶涵《还记得吗》_

description:
故事的世界观大概是这样的。这个世界的人分为三类，根据其某种特点被直接命名为 Weak，Average 和 Strong。你可以理解为这是一个关于种族或者职业的分类。

两个队伍之间发生了一场回合制战斗。你知道双方做了什么，现在希望你把所有的细节还原出来。

下面是本题的一些技术细节。

**【人物】**

一个人有以下几种属性值：「种族」、「等级」、「体力上限」、「基础攻击指数」、「基础防御指数」、「主动技能等级」、「被动技能等级」。其中「体力上限」、「基础攻击指数」、「基础防御指数」完全由「种族」和「等级」决定。但是为了输入方便，本题中所有信息都会给出。在战斗中，每个人有一个「体力值」。在战斗开始时，「体力值」等于「体力上限」。当「体力值」小于等于 $0$ 时这个人就会「倒下」。对于同一个「种族」而言，「体力上限」、「基础攻击指数」、「基础防御指数」大致随「等级」指数增长。每个人持有一把「武器」。「武器」的细节在下一节给出。

**【武器】**

「武器」的属性只有两种：「武器类型」和「武器攻击力」。所有「武器」都有「普通攻击」和「特殊攻击」两种攻击方式。发起「攻击」指使用这两种方式中的任意一种。「普通攻击」的效果与「武器类型」无关，但不同的「武器类型」有着不同的「特殊攻击」效果。「武器」有三种类型，分别叫做「B」、「G」、「M」。

**【战场与队伍】**

交战双方的每一方包含不超过 $6$ 名队员，一字排开，从西到东的编号分别为 $5,3,1,2,4,6$（若不足 $6$ 名则删去较大的若干个编号）。方便起见，就叫两队为「南队」和「北队」。

**【回合】**

每个「回合」中，只有一个人可以「行动」。第奇数个「回合」是「南队」的队员「行动」，第偶数个「回合」是「北队」的队员「行动」。第一个「回合」和第二个「回合」中，「行动」的人是队伍里未「倒下」的编号最小的人。之后的「回合」中，若本队中没有编号比本队上一个「行动」的人大且未「倒下」的人，则由本队中编号最小的未「倒下」的人「行动」。否则由编号大于本队上一个「行动」者的人中，编号最小且未「倒下」的人「行动」。若一个队伍中的所有队员均已「倒下」，则判另一个队伍「胜利」。

**【行动】**

「行动」一共有三种。当前「回合」中「行动」的人必须选择三种之一来完成。

1. 「普通攻击」；
2. 「特殊攻击」；
3. 「主动技能」。

这些「行动」的效果会在之后介绍。「特殊攻击」和「主动技能」是有次数限制的，但是在本题中，保证所有「行动」均合法，所以你不需要考虑这个限制。

**【伤害计算】**

「伤害」指的是因为「普通攻击」或「特殊攻击」而造成的「体力值」减少。

「伤害」，即「体力值」减少的量，由「攻击强度」和受到「伤害」的人的「防御指数」决定。

一个人的「防御指数」等于这个人的「基础防御指数」乘以队伍的「防御加成」。

具体地，若一个人受到「攻击强度」为 $x$ 的「伤害」，那么这个人的「体力值」就会减少 $y$。其中 $y$ 的值等于 $x$ 除以这个人的「防御指数」下取整。

「攻击强度」等于「基础攻击强度」乘以发起「攻击」的人的「技能加成」乘以队伍的「攻击加成」乘以「种族克制加成」乘以「方位加成」。这些概念会在之后介绍。

**【普通攻击】**

选择一个敌方未「倒下」的队员作为「目标」。「目标」受到「基础攻击强度」为发起「攻击」的人的「基础攻击指数」乘「武器攻击力」的「伤害」。

**【特殊攻击】**

选择一个敌方未「倒下」的队员作为「目标」。

「武器」有三种，不同「武器类型」的「特殊攻击」效果如下：

- 「B」：「目标」受到「基础攻击强度」为发起「攻击」的人的「基础攻击指数」乘「武器攻击力」乘 $125\%$ 的「伤害」。
- 「G」：「目标」和「目标」东西两侧与「目标」距离最近的各一名未「倒下」的队员（如果存在）均受到「基础攻击强度」为发起「攻击」的人的「基础攻击指数」乘「武器攻击力」乘 $x\%$ 的「伤害」。其中 $x$ 的值等于 $135$ 除以将要受到「伤害」的人数。「伤害」按照「目标」、「目标」西侧、「目标」东侧的顺序计算。注意如果过程中有人「倒下」，那么这个人的「被动技能」将不再对该顺序中位于这个人之后的人的「伤害」结算起作用。特别地，所有「伤害」的「方位加成」以「目标」的「躲闪方位」来计算。
- 「M」：「目标」受到「基础攻击强度」为发起「攻击」的人的「基础攻击指数」乘「武器攻击力」乘 $115\%$ 的「伤害」。「目标」东西两侧与「目标」距离最近的各一名未「倒下」的队员（如果存在）分别受到「基础攻击强度」为发起「攻击」的人的「基础攻击指数」乘「武器攻击力」乘 $23\%$ 的「伤害」。「伤害」按照「目标」、「目标」西侧、「目标」东侧的顺序计算。注意如果过程中有人「倒下」，那么这个人的「被动技能」将不再对该顺序中位于这个人之后的人的「伤害」结算起作用。特别地，所有「伤害」的「方位加成」以「目标」的「躲闪方位」来计算。

**【技能】**

「技能」分为「主动技能」和「被动技能」。每个「种族」的人都有一个「主动技能」和一个「被动技能」。「技能」的效果因「种族」和「技能等级」的不同而不同。「技能等级」为一个 $0$ 到 $5$ 之间的整数。「技能等级」为 $0$ 表示没有该「技能」。

使用「主动技能」需要选择一个人作为「技能目标」。

「主动技能」描述如下：（$1$ 到 $5$ 级的「技能」效果由斜杠隔开，保证使用「主动技能」的人的「主动技能等级」不为 $0$）

- 「Weak 种族」：使本队一名未「倒下」的队员的「体力值」增加这名队员的「体力上限」乘以 $10\%/12\%/15\%/17\%/20\%$ 下取整。
- 「Average 种族」：选择一名敌方未「倒下」的队员，在使用该「主动技能」这一队的「回合」结束时，其「体力值」减去其「体力上限」的 $6\%/7\%/8\%/9\%/10\%$ 下取整。该效果持续 $3$ 个回合，即会触发 $3$ 次。若该队员已有同类型（可以是不同等级）的「技能」施加的效果，那么这个效果将会覆盖之前的效果。
- 「Strong 种族」：使本队一名未「倒下」的队员的「技能加成」变为 $2.1/2.17/2.24/2.32/2.4$。

一名队员的「被动技能」只有当该队员未「倒下」时才能发挥效果，「倒下」之后不再发挥效果。

「被动技能」描述如下：

- 「Weak 种族」：在本队的「回合」开始时，本队所有未「倒下」的成员的「体力值」增加该成员「体力上限」的 $1.3\%/1.6\%/1.9\%/2.2\%/2.5\%$。若本队有多名队员有这个「技能」，这个效果的数值可以相加至最多 $5\%$。超过 $5\%$ 按照 $5\%$ 计算。「体力值」增加的量在效果叠加后需要下取整。
- 「Average 种族」：队伍的「防御加成」初始为 $1$。该技能使队伍的「防御加成」增加 $0.01/0.02/0.03/0.04/0.05$。若本队有多名队员有这个「技能」，这个效果的数值可以相加至最多 $0.1$。超过 $0.1$ 按照 $0.1$ 计算。
- 「Strong 种族」：队伍的「攻击加成」初始为 $1$。该技能使队伍的「攻击加成」增加 $0.01/0.02/0.03/0.04/0.05$。若本队有多名队员有这个「技能」，这个效果的数值可以相加至最多 $0.1$。超过 $0.1$ 按照 $0.1$ 计算。

一名队员的「体力值」增加时，不能超过这名队员的「体力上限」。若增加后的「体力值」超过了「体力上限」，则把这次增加「体力值」的效果改为将这名队员的「体力值」变成这名队员的「体力上限」。

**【技能加成】**

战斗开始时，所有人的「技能加成」都是 $1$。只有两种方式能够改变「技能加成」：

- 「Strong 种族」的「主动技能」。见「技能」的描述。
- 当一个人发起「攻击」且计算完这次「攻击」的所有「伤害」之后，这个人的「技能加成」变为 $1$。

**【种族克制加成】**

「种族克制加成」与发起「攻击」的人的「种族」以及受到「伤害」的人的「种族」有关。「种族克制加成」的值如下表：

| 发起「攻击」方/受到「伤害」方 | Weak  | Average | Strong |
| :---------------------------: | :---: | :-----: | :----: |
|             Weak              | $1.0$ |  $0.9$  | $1.1$  |
|            Average            | $1.1$ |  $1.0$  | $0.9$  |
|            Strong             | $0.9$ |  $1.1$  | $1.0$  |

**【方位加成】**

在「攻击」时，发起「攻击」的一方有一个「攻击方位」，「攻击」的「目标」有一个「躲闪方位」。「攻击方位」和「躲闪方位」分别为一个 $1$ 到 $6$ 之间的整数。当「攻击方位」为 $a$，「躲闪方位」为 $d$ 时，「方位加成」的值由下表所示：

| $(a-d)\bmod 6$ | 「方位加成」 |
| :------------: | :----------: |
|      $0$       |    $1.25$    |
|   $1$ 或 $5$   |    $1.00$    |
|   $2$ 或 $4$   |    $0.75$    |
|      $3$       |    $0.00$    |

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

第一行两个正整数 $n,m$，分别表示「南队」的人数和「北队」的人数。

接下来 $n$ 行，其中第 $i$ 行表示「南队」中编号为 $i$ 的队员的信息，格式如下：

`<Type> Lv=<Lv> maxhp=<maxhp> atk=<atk> def=<def> skillLv=<skillLv> passivesklLv=<passivesklLv> <weapontype> weaponatk=<weaponatk>`

其中尖括号中的内容表示一个变量。

`<Type>` 为 `Weak`，`Average`，`Strong` 中的一种，分别表示对应名称的「种族」。

`<Lv>` 为一个 $1$ 到 $100$ 之间的整数，表示队员的「等级」。

`<maxhp>` 为一个整数，表示队员的「体力上限」。

`<atk>` 为一个实数，表示队员的「基础攻击指数」。

`<def>` 为一个实数，表示队员的「基础防御指数」。

`<skillLv>` 为一个 $0$ 到 $5$ 之间的整数，表示队员的「主动技能等级」。

`<passivesklLv>` 为一个 $0$ 到 $5$ 之间的整数，表示队员的「被动技能等级」。

`<weapontype>` 为 `B`，`G`，`M` 中的一种，分别表示对应名称的「武器类型」。

`<weaponatk>` 为一个实数，表示队员的「武器攻击力」。

接下来 $m$ 行，其中第 $i$ 行表示「北队」中编号为 $i$ 的队员的信息，格式与「南队」相同。

接下来一行一个正整数 $T$，表示进行的「回合」数。

接下来 $T$ 行，其中第 $i$ 行表示第 $i$ 个「回合」的「行动」。

「行动」的描述以一个字符串开头，表示「行动」的类型。

`Basicattack target=<target> atkpos=<atkpos> ddgpos=<ddgpos>` 表示一次「普通攻击」。

`Specialattack target=<target> atkpos=<atkpos> ddgpos=<ddgpos>` 表示一次「特殊攻击」。

`Skill target=<target>` 表示使用 「主动技能」。保证该队员的「技能等级」不是 $0$。

其中，`<target>` 表示「目标」或「技能目标」的编号。若是「Weak 种族」或「Strong 种族」的「主动技能」，这个编号是一个己方队员的编号，否则是一个敌方队员的编号。

`<atkpos>` 为一个 $1$ 到 $6$ 之间的整数，表示「攻击方位」。

`<ddgpos>` 为一个 $1$ 到 $6$ 之间的整数，表示「躲闪方位」。

保证所有的「行动」均合法。

为了方便起见，本题中实数的表示方法较为特殊。具体的表示方法是，用 `<mag>e<exp>` 的方式来表示 `<mag>` 乘以 $10$ 的 `<exp>` 次方。其中 `<mag>` 是一个 $1$ 到 $99999$ 之间的正整数，`<exp>` 是一个 $-6$ 到 $0$ 之间的整数。如 $42.195$ 可以表示成 `42195e-3`，$6$ 可以表示成 `6e0` 或 `600e-2` 等，$0.04$ 可以表示成 `4e-2` 等。

outputFormat:
输出到标准输出。

对于每个「回合」，按时间顺序把这个「回合」的信息输出来。

信息的格式如下：

`<team> <id> recovered +<heal> hp -> <curhp>/<maxhp>` 表示「Weak 种族」的「技能」所造成的「体力值」增加。如果在增加之前「体力值」就已经等于「体力上限」，那么不需要输出这一行。

`<team> <id> took <dmg> damage from <atkteam> <atkid> -> <curhp>/<maxhp>` 表示一名队员受到「伤害」。

`<team> <id> took <dmg> damage from skill -> <curhp>/<maxhp>` 表示「Average 种族」的「主动技能」所造成的「体力值」减少。

`<team> <id> applied <type> skill to <targetteam> <targetid>` 表示使用「主动技能」。

其中 `<team>` 表示队伍名称，为 `South` 或 `North` 之一，分别表示南队/北队。

`<id>` 表示「体力值」发生改变的人在队伍中的编号，为一个 $1$ 到 $6$ 之间的正整数。

`<heal>` 表示本应该增加的「体力值」数量（不考虑「体力上限」的限制），为一个正整数。

`<curhp>` 指的是「体力值」发生改变之后的「体力值」，为一个非负整数。若「体力值」减小到 $0$ 以下输出 $0$。

`<maxhp>` 表示「体力值」发生改变的人的「体力上限」，为一个正整数。

`<dmg>` 为受到的「伤害」或「Average 种族」的「主动技能」所造成的「体力值」减少，为一个非负整数。

`<type>` 为使用「主动技能」的人的「种族」，为 `Weak`，`Average`，`Strong` 之一。

`<atkteam>` 和 `<atkid>` 为发起「攻击」的人的队伍名称和编号，格式同 `<team>` 和 `<id>`。

`<targetteam>` 和 `<targetid>` 为「技能目标」的队伍名称和编号，格式同 `<team>` 和 `<id>`。

时间顺序如下：

「回合」开始时，可能触发「Weak 种族」的「被动技能」效果，按照编号从小到大输出。

如果是使用「主动技能」，则输出一行使用「主动技能」的信息。

然后输出「行动」所造成的「体力值」变化信息。若「伤害」为 $0$ 也要输出。若没有造成「伤害」则不输出。若「特殊攻击」改变了多个人的「体力值」，则按照「目标」、「目标」西边的人、「目标」东边的人的顺序输出。

「回合」结束时，可能触发「Average 种族」的「主动技能」效果，按照编号从小到大输出。

每个「回合」结束后输出两队的「体力值」信息，格式如下：

`<team>: [<curhp5>/<maxhp5>] [<curhp3>/<maxhp3>] <curhp1>/<maxhp1> [<curhp2>/<maxhp2>] [<curhp4>/<maxhp4>] [<curhp6>/<maxhp6>]`

其中，`<team>` 表示队伍名称，`<curhpi>` 表示队伍中编号为 $i$ 的人的「体力值」，`<maxhpi>` 表示队伍中编号为 $i$ 的人的「体力上限」。两个人的「体力值」信息之间有恰好一个空格，第一个「体力值」信息和冒号之间有恰好一个空格。已「倒下」的人的「体力值」信息也需要输出。方括号表示，若队伍中不存在编号为 $i$ 的人则不输出。注意这里按照位置顺序而不是编号顺序输出，即顺序为 $5,3,1,2,4,6$。

先输出一行「北队」的信息，再输出一行「南队」的信息。

每个「回合」的信息以一个空行结束。

所有「回合」结束后，若有一个队伍「胜利」，则输出一行 `Team <team> won.`。其中 `<team>` 是队伍名称，为 `South` 或 `North`。因为「行动」需要指定一个未「倒下」的人作为「目标」或「技能目标」，且所有「行动」均合法，所以，如果有队伍「胜利」，则一定是在最后一个「回合」结束后才「胜利」。若没有队伍「胜利」则不输出。

samples:
2 1
Strong Lv=90 maxhp=2451 atk=15588e-4 def=96931e-3 skillLv=5 passivesklLv=5 M weaponatk=80000e0
Strong Lv=100 maxhp=3512 atk=16385e-4 def=12511e-2 skillLv=5 passivesklLv=5 G weaponatk=80000e0
Weak Lv=1 maxhp=100000 atk=75000e-5 def=10000e-6 skillLv=5 passivesklLv=5 B weaponatk=80000e0
3
Skill target=2
Specialattack target=1 atkpos=3 ddgpos=3
Specialattack target=1 atkpos=5 ddgpos=5

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

见题目目录下的 *2.in* 与 *2.ans*。

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

这个样例，无疑是善良的出题人无私的馈赠。中间忘了。出题人相信，这个美妙的样例，可以给拼搏于 AC 这道题的逐梦之路上的你，提供一个有力的援助。

**【数据范围】**

保证 $1\le n,m \le 6$。

保证 $1\le T \le 50000$。

保证「武器攻击力」的范围在 $300$ 到 $80000$ 之间。

「体力上限」「基础攻击指数」「基础防御指数」的范围见下表。

| 「种族」与「等级」 | 「体力上限」 | 「基础攻击指数」 | 「基础防御指数」 |
| :----------------: | :----------: | :--------------: | :--------------: |
|     Weak Lv.1      |   $100000$   |    $0.75000$     |    $0.010000$    |
|    Average Lv.1    |    $5000$    |    $0.80000$     |    $0.20000$     |
|    Strong Lv.1     |    $100$     |     $1.0000$     |     $10.000$     |
|    Weak Lv.100     |  $7807514$   |     $1.0089$     |    $0.10464$     |
|   Average Lv.100   |   $252234$   |     $1.3108$     |     $1.8101$     |
|   Strong Lv.100    |    $3512$    |     $1.6385$     |     $125.11$     |

**【后记】**

_有一天我将会老去_

_希望你会觉得满意_

_我没有 对不起那个_

_十五岁的自己_

_——刘若英《继续-给十五岁的自己》_

**【题目来源】**

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。


title: [THUPC 2023 决赛] 着色

background: 远古的笔迹，远古的乐音，远古的历史，远古的 $K_{1000}$，若无人问津，便悄然褪色……

description: 给出一个 $n$ 个节点的无向完全图，你需要给每条边标上一个 $0 \sim 9$ 的数字，使得图上不存在一个三元环或五元环满足：其上所有边的数字相同。

inputFormat: 输入仅一行一个整数 $n$ 表示图的节点数。

outputFormat: 如果不存在方案，输出一行一个整数 `-1`。否则输出 $(n-1)$ 行，第 $i$ 行 $(n-i)$ 个字符，第 $i$ 行的第 $j$ 个字符表示 $(i,i+j)$ 的标号。若有多个方案，输出任意一个即可。

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

对于所有测试数据，$2 \le n \le 1000$。

### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。


title: [THUPC 2023 决赛] 烂柯杯

background:
却说庞统迤逦前进，抬头见两山逼窄，树木丛杂；又值夏末秋初，枝叶茂盛。庞统心下甚疑，勒住马问：“此处是何地？”数内有新降军士，指道：“此处地名落凤坡。”庞统惊曰：“吾道号凤雏，此处名落凤坡，不利于吾。”令后军疾退。只听山坡前一声炮响，箭如飞蝗，只望骑白马者射来。可怜庞统竟死于乱箭之下。时年止三十六岁。后人有诗叹曰：“古岘相连紫翠堆，士元有宅傍山隈。儿童惯识呼鸠曲，闾巷曾闻展骥才。预计三分平刻削，长驱万里独徘徊。谁知天狗流星坠，不使将军衣锦回。”先是东南有童谣云：“一凤并一龙，相将到蜀中。才到半路里，凤死落坡东。风送雨，雨随风，隆汉兴时蜀道通，蜀道通时只有龙。”

——《三国演义》第六十三回：诸葛亮痛哭庞统 张翼德义释严颜

description:
$2023$ 年 $5$ 月 $4$ 日 $ \sim 9$ 日，第一届“衢州烂柯杯”世界围棋公开赛本赛第一阶段的赛程在衢州顺利进行。作为疫情后第一场全程线下进行的世界围棋大赛，也是目前中国主办的唯一一项每年一届的世界围棋大赛，无疑引起了国内外广大围棋爱好者的广泛关注。

“羽客一枰无复见，青山留得烂柯名。”衢州是围棋圣地，流传着“王质遇仙”的故事，境内的烂柯山也因此闻名于天下。正因为此，“烂柯”也是围棋的别称之一，从古至今的许多围棋故事、书籍、弈谱等，也有不少化用了“烂柯”的典故，或以“烂柯”定名。

此次“烂柯杯”世界围棋大赛，是在保留原有的“烂柯杯”中国围棋冠军赛的基础上，创办的一项崭新的世界性围棋赛事，吸引了全世界围棋高手前来参加。其中，中国队派出了柯洁、辜梓豪、王星昊、丁浩、李钦诚等 $15$ 员大将参赛，韩国队 $8$ 人，日本队 $5$ 人，还有 $2$ 位棋手来自中国台湾、 $2$ 位棋手来自欧美地区。可以说，全世界最顶尖的围棋高手悉数相聚于此。

随着科技的发展，人工智能的巨大技术进步和网络传媒的全面普及，围棋这项来自中国的传统运动正在焕发出新的活力。在网络上，人们随时可以看到最新的赛事直播，以及人工智能的精准分析和各大围棋高手的细致解读。资源获取的便捷性使得人们对围棋的关注度空前上升，围棋不再是只有少部分懂棋的爱好者才能欣赏的“小众游戏”；围棋高手也不再只是一个神秘的身份，越来越多的围棋高手开始在网络上与棋迷近距离互动，普及围棋知识，讲解最新对局，赢得了一致好评。正如这次参赛的选手中，有一位棋手同时也是粉丝数达 $150$ 多万的网红主播，甚至还有一位棋手是一家网红餐厅的老板。

我们今天故事的主角正是这样一位有着传奇色彩的人物。作为一名清华大学本科在读的学生，同时也是一名顶尖围棋高手，他的一举一动无疑都会引起巨大的关注。此次他参加“烂柯杯”比赛，众人无一例外看好他的比赛前景，尤其是现在韩国围棋”第一人“申真谞九段的巅峰时期，他也被无数中国棋迷寄托以”狙击‘小申’“的重任。$5$ 月 $4$ 日抽签过后，没有任何人会怀疑他能不能赢下 $5$ 日的第一轮比赛，一些围棋高手更是直接放出了”大胜，不可能失败“的预言。

然而，$5$ 月 $5$ 日的比赛还是爆出了惊天大冷门。他在已经胜券在握，AI 胜率达到 $99\%$ 的关头，接连选择了“弹幕最多的下法”，最终因为几招致命的失误葬送好局，落败于中国台湾棋手赖均辅八段。赛后，人们在震惊的同时，纷纷猜测本局失利的原因。有人说，他的状态低迷在前些年早已有所体现，“当你在 XX 的时候，小申在下棋”成了调侃他与申真谞战绩差距的一句名言；有人说，他在比赛之前的 $12$ 连胜战绩反而使他心态紧张，从而犯了优势下容易大意的老毛病；也有人拿出了“落凤坡”的典故，以证明他或许命中注定与“烂柯杯”八字不合……但或许，这样的变幻莫测和不可预料性，正是围棋的魅力所在。

请你根据以上所有信息，猜测本文的主角是谁。

inputFormat: 无输入。

outputFormat: 输出一个由小写字母组成的字符串，表示上文中提到的主角的名字全拼。如若答案是马云，应当输出 `mayun`。

hint:
### 提示

主角的名字在题面中已经有所提及。

题面中一些看似无厘头的信息实际上是有价值的。

### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023> 查看。


title: [THUPC 2023 决赛] 阴阳阵

background:
“余于久远之书，见一阴阳阵，必可助君征服九州。用此阵，须出诸阴阳大将。所谓阴将者，武勇而玉恶；所谓阳将者，善谋时且忠厚。凡阴阳阵，各将皆须择一将，以通之。又有两法皆牢记，不可即弱阵：一曰阴援阴，易激性情，或避之；二曰援与环，环阴与阳同，守以衡……”

正当你准备征服九州时，你仿佛听见一个熟悉的声音在远处喊：“工作的时候不准睡觉，你这样会被开除的……”你终于回过神来，发现你的 XCPC 队友在旁边熟练地拧着螺丝，流水线前已经漏过几个不合格的工品。刚刚什么都没发生啊，你哀叹道，但是……

description:
有一张图，图上有 $n$ 个白点和 $m$ 个黑点。白点之间两两不同，黑点之间两两不同。

每个节点有一条出边，每个节点出边指向的节点可以在 $n+m$ 个节点中任意选择。

此时共有 $(n+m)^{n+m}$ 个方案，每个方案是一个有向基环树森林。

称一个方案是好的当且仅当其满足以下条件：

- 任何一个黑点都指向一个白点，
- 每个环上的黑点数量和白点数量的乘积是偶数。

你需要求出所有方案中好的方案数量，对输入模数 $P$ 取模。

inputFormat: 输入一行三个整数 $n,m,P$，意义如题目描述所述。

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

hint:
### 样例 1 解释

考虑黑点必须连向白点的限制共有 $3 \times 3 \times 2 = 18$ 种方案，其中一个黑点和一个白点构成一个环的方案非法。选择一个白点和黑点构成环的方案数为 $2$，剩下的一个白点有三种方案，因此非法的方案数为 $2 \times 3 = 6$，答案为 $18-6=12$。

### 数据规模与约定

对于所有测试数据，$1 \le n,m \le 2000$，$1 \le P \le 10^9$。

### 提示

你可能需要注意常数对算法效率产生的影响。

### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023> 查看。


title: [THUPC 2023 决赛] 大纲

description:
小 I、小 O 和小 N 是 ION 大纲的编写者，小 I 负责给每个知识点定难度。

ION 大纲计划列入 $n$ 个知识点，其中小 I 按照自己的认识给其中部分知识点定好了难度，还有部分知识点没有定难度。

知识点之间有依赖关系，这个依赖关系恰好构成了一棵以 $1$ 为根的外向树，知识点 $x$ 指向知识点 $y$ 表示 $x$ 依赖 $y$。**依赖关系不具有传递性。**

你需要告诉小 I 目前确定下来的难度是否合理。我们认为确定下来的难度是合理的当且仅当存在一个给所有未确定难度的知识点确定难度的方式，使得以下所有条件成立：

- 每个知识点的难度都是非负整数；
- 对于每个依赖其他知识点的知识点 $x$，设 $\max_x$ 为 $x$ 依赖的知识点中难度的最大值，则如果 $x$ 恰依赖一个难度为 $\max_x$ 的知识点，那么知识点 $x$ 的难度为 $\max_x$，否则为 $\max_x+1$。**对于不依赖其他知识点的知识点，没有其他限制。**

inputFormat:
**本题有多组测试数据**。第一行一个整数 $T$ 表示测试数据组数，接下来依次读入每组测试数据。

对于每组测试数据，

- 第一行一个整数 $n$ 表示知识点数量。
- 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，描述每个知识点的难度。若 $a_i = -1$ 表示知识点 $i$ 未确定难度，否则知识点 $i$ 的难度确定为 $a_i$。
- 接下来 $n-1$ 行每行两个整数 $u,v$，表示依赖关系构成的外向树中的一条有向边。

outputFormat: 对于每组测试数据输出一行：若难度是合理的，输出 `Reasonable`，否则输出 `Unreasonable`。

hint:
### 样例 1 解释

对于第一组测试数据，将知识点 $2$ 的难度定为 $0$ 即满足条件。

对于第二组测试数据，无论如何指定知识点 $2$ 的难度，知识点 $1$ 的难度会产生矛盾。

### 数据规模与约定

对于所有测试数据，$1 \le T \le 10^5$，$2 \le n \le 10^5$，$-1 \le a_i \le 10^9$，$1 \le u,v \le n$。
保证单个测试点中所有测试数据的 $n$ 的和不超过 $2 \times 10^5$，每组测试数据输入的所有边构成一棵以 $1$ 为根的外向树。

### 后记

大纲发表了。若干天后，小 I 给 ION 比赛投题，却发现有人偷偷改了一笔难度表，导致他的题目超纲。于是小 I 只能把题投给 CPUHT。

### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023> 查看。


title: [信息与未来 2023] 幸运数字

description:
如果把一个数字十进制表示的**奇数位和偶数位分别相加得到的和相同**，小小就认为它是一个幸运的数字。例如：

- $12345$ 奇数位相加 $1 + 3 + 5 = 9$、偶数位相加 $2 + 4 = 6$，因此 $12345$ 不是幸运数字；

- $2332$ 奇数位相加 $2 + 3 = 5$、偶数位相加 $3 + 2 = 5$，因此 $2332$ 是幸运数字。

对于给定的 $a$ 和 $b$，小小希望你求出 $a,a + 1, a + 2,\dots, b$ 中幸运数字的数量。

inputFormat: 输⼊数据仅一行，包含空格分隔的两个整数 $a$ 和 $b$。

outputFormat: 输出一行一个整数，代表 $a, a + 1, a + 2,\dots, b$ 中幸运数字的数量。

hint:
- 对于 $100\%$ 的数据，满足 $1\leq a\leq b\leq 10^6$。

>本题原始满分为 $10\text{pts}$。


title: [信息与未来 2023] 精密计时

description:
小小有一个非常精密的计时器，每秒可以计数 100 次 (两个连续的时钟计数之间恰好间隔百分之一秒)。例如，以下是从 $13:01:02.37$ 到 $13:01:03.01$ 的计时过程：
```plain
13:01:02.37 (13 时 1 分 2 秒.37)
13:01:02.38
13:01:02.39
...
13:01:02.98
13:01:02.99 (13 时 1 分 2 秒.99)
13:01:03.00 (13 时 1 分 3 秒.00)
13:01:03.01
```
小小记录了计时器上的两个时刻，你能帮助他计算这两个时刻之间经过了多少个 “百分之一秒”吗？

inputFormat: 输入数据仅一行，包含空格分开的两个字符串，代表了两个计时器上显示的时刻。时刻中的时、分、秒、百分之一秒均使用两位十进制数字表示，不足两位时在十位添零。时、分、秒之间用冒号 `:` 分隔，秒和百分之一秒之间用小数点 `.` 分隔。

outputFormat: 输出一行一个整数，代表两个时刻之间经过的 “百分之一秒” 数。

hint:
对于 $100\%$ 的数据，两个时刻都来自 $24$ 小时制的同一天 （$00:00:00.00$ 到 $23:59:59.99$），且保证后一个时刻晚于前一个时刻。

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2023] 图像重建

background:
JWST (詹姆斯·韦伯太空望远镜，James Webb Space Telescope) 是一台红外波段的大型太空望远镜，由美国国家航空航天局 (NASA)、欧洲航天局 (ESA) 和加拿⼤航天局 (CSA) 共同合作开发。它是哈勃太空望远镜的科学继任者，旨在解决⼀系列重要的天文学问题，包括宇宙的起源、星系的形成和演化、恒星和行星系统的形成，以及寻找宜居⾏星和生命迹象。

以下是 JWST 望远镜 5 ⽉ 23 ⽇采集的深空图像：

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

description:
太空望远镜在采集数据时，并不像我们日常生活中的手机或相机 “一次拍摄成像” 直接从传感器数据得到照⽚，而是由多次不同时段拍摄的图像拼接而成。在这个问题中，我们也来实现图像的拼接重建。

我们已经对⼀个区域拍摄了**两张**黑白图像。这两张图像面向同⼀区域拍摄，因此我们预期它们有相当⼀部分都是重叠的。你的任务就是将两张图像经过上下左右平移后尽可能 “重叠” 在⼀起，满⾜重叠部分所有像素均完全相同，且**重叠部分的⾯积尽可能⼤（即重叠部分的像素数量尽可能多）**。

inputFormat:
输入数据由两张图像的描述组成。两张图像的描述之间有一个空行。

对于每张图像，第一行包含两个整数 $n$ 和 $m$，代表了图像的尺寸(像素的行数和列数)。接下来 $n$ ⾏，每行 $m$ 个像素描述了拍摄的图像，其中 $0$ 表示一个黑色像素，$1$ 表示一个白色像素。每一行的像素由一个空格分隔。

outputFormat: 输出一行一个整数，即经过最优平移后，重叠部分的像素数量。

hint:
对于 $100\%$ 的数据，满足 $1\leq n,m\leq 50$。

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2023] 程序分析

description:
程序分析技术是一种用于理解和改进计算机程序的方法。它可以帮助我们找出程序中的错误、提高程序的性能、优化代码结构等。其中，静态分析技术在不运行程序的情况下对程序代码进行分析。它可以检查代码的语法、风格、潜在错误等。例如，静态分析可以帮助我们找出程序中未使用的变量、可能的数组越界等问题。

小小设计了一个自己的编程语言，并命名为 X 语言。你能为它设计一个静态分析器吗？

X 语言程序中只有两个整型变量 $x$ 和 $y$，且无需定义，可以直接使用。变量 $x$ 的值从程序外输入（输入值可以是任何 C++ int 范围内的值），$y$ 的初始值是 $0$。一个 X 语言程序由若干行组成，每行恰好包含一条命令，是以下三种命令之一：
1. 条件分支：`if (条件) {`；
2. 对 $y$ 赋值：`y = 数字;`；
3. 条件结束：`}`。

其中，“条件”要么是 `x > 数字`，要么是 `x < 数字`。赋值语句和条件中的“数字”都是 $1$ 到 $10^9$ 之间的常数。`if` 和赋值的含义同 C++ 语言中的条件和赋值语句。

请你编写一个静态分析器，分析一个 X 语言程序执行结束时，所有可能的 $y$ 的值。

inputFormat:
输入数据第一行为整数 $n$，代表程序的行数。

接下来 $n$ 行，每行一个命令，描述了一个合法的 X 语言程序：输入的程序保证括号配对，且符合问题描述中的约定。为了便于大家解析 (例如用 `cin` 或 `scanf` 读入)，输入程序中的 `if` 后、`{` 前、`=`、`<`、`>` 左右都恰好有一个空格，行首可能有若干空格缩进。除此之外，输入不含多余的空格或空白字符。

outputFormat: 输出一行，从小到大不重复地输出程序结束时，变量 $y$ 所有可能的值。数字之间由一个空格隔开。

samples:
(见 p4.zip 中的 2-in.txt)
(见 p4.zip 中的 2-out.txt)

samples:
(见 p4.zip 中的 3-in.txt)
(见 p4.zip 中的 3-out.txt)

hint:
对于 $100\%$ 的数据，满足 $1\le n \le 10^3$。输入数据的每行都不超过 $10^3$ 个字符。

>本题原始满分为 $20\text{pts}$。


title: [信息与未来 2023] 文本压缩（暂无 SPJ）

background: 数据压缩算法的目的是减少数据的大小，以便更快地传输和存储。我们经常会用到的 zip、rar 等压缩工具，就是利用数据压缩算法把多个文件或者文件夹压缩成一个更小的文件；我们的网页在传输时，通常也使用了 gzip 压缩。有些时候 (例如传输图像、视频时)，我们会允许在压缩过程中损失⼀些精度，以实现更好的压缩比。

description:
在这个问题里，你需要自己设计⼀个**英文文本的无损压缩和解压缩算法**。你的程序需要同时实现压缩器和解压缩器两部分功能：

- 压缩器输⼊⼀个**仅由小写字母组成的字符串**，输出⼀个压缩后的字符串。压缩后的字符串允许使用大写字母、⼩写字母和数字，但不允许使⽤其他字符。

- 解压缩器输入⼀个压缩后的字符串，还原出小写字母的字符串。

注意，在这个问题中，**所有给压缩器的输如都来自人工智能 GPT-3.5-turbo 生成的英文文本保留字母 (并转换为⼩写) 后得到的**，也就是说，你可以假设除了偶尔的例外，字符串是由英文单词拼接而成的。这个性质是解决问题的关键——随机序列的压缩比 “有规律” 序列的压缩要困难得多。

inputFormat:
输⼊数据第一行为一个大写英文单词，代表压缩/解压缩的任务类型。`COMPRESS` 代表压缩；`DECOMPRESS` 代表解压缩。

第二行一个字符串，是压缩/解压缩任务对应的文本。对于压缩任务，是一个仅包含小写字母的字符串；对于解压缩任务，字符串总是来自你程序之前 `COMPRESS` 压缩的结果。

outputFormat: 输出一行一个字符串。对于压缩任务，输出一行为压缩后的文本；对于解压缩任务，输出一行为解压缩后的文本。

samples:
见压缩包。样例仅给出了压缩任务所需的字符串 (由
人工智能 GPT-3.5-turbo 生成)，不含样例输出；你
可以在给出的样例上实验你的压缩算法。

hint:
对于 $100\%$ 的数据，输⼊字符串的长度 $n$ 满足 $3\times 10^4 \leq  n \leq 4\times 10^4$。

---

本题的评测机会两次调用你的程序：

- 第一次调用你的程序执行压缩任务，例如输⼊

```plain
COMPRESS
aaaaaaaabbbbbbbbbb
```

假设本次调用，你的程序输出了 `a8b10` 作为压缩后的文本。这个输出会被评测系统记住。

- 第二次，调用你的程序执行解压缩任务。针对刚才的例子，我们会为你的程序输⼊

```plain
DECOMPRESS
a8b10
```

如果你的程序解压缩输出 `aaaaaaaabbbbbbbbbb`（即正确解压缩得到原字符串），则被判定为“还原正确”。

对于每个测试数据，压缩和解压缩分别有 $1\ \text{s}$ 的运⾏时间限制。

对于每个测试数据，在解压缩能正确得到原字符串的前提下：

- 如果压缩率达到 $75\%$（压缩字符串的长度小于等于输⼊长度的 $\frac{3}{4}$），该测试点得满分。

- 如果压缩率达到 $80\%$（压缩字符串的长度小于等于输⼊长度的 $\frac{4}{5}$），该测试点得一半分数。

>本题原始满分为 $20\text{pts}$。


title: [信息与未来 2023] 电路布线

description:
电路布局布线（Circuit Layout and Routing）是电子设计自动化（EDA）领域的一个重要概念，它涉及到在电路板或集成电路上安排和连接电子元件的过程。这个过程的目标是在满足电气性能、信号完整性、电磁兼容性等要求的同时，实现对空间、成本和生产工艺的优化。

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

小小现在需要解决一个简化的电路布线问题，在一个 $n × m$ 的方格中进行电路布线。其中：
- 井号 `#` 标记的格子已经被占用，不能布线。
- 加号 `+` 标记的格子会连接到电路的其他部分，必须被布线。在给定的电路布线问题中，至少有一个格子必须被布线。
- 点号 `.` 标记的格子小小有权选择是否布线：布线即将该格标记为加号，不布线即保持为点号。

小小的任务是选择尽可能多的格子进行布线 (将 `.` 的格子标记为 `+`)，满足：
1. 布线电路连通。即从任意一个已布线的格子，都能通过上、下、左、右移动到相邻已布线格子的方式，到达任意另一个布线的格子。
2. 布线不存在短路 (回路)，即不存在某个布线的格子能通过 $> 2$ 步的上、下、左、右移动到相邻布线格子的方式回到自身，且经过的格子各不相同。

例如，以下是一个电路布线问题，已有三个格子被标记为必须布线 (加号)：
```plain
#....#
....+#
.+####
.+...#
```
以下展示了一种合法和两种不合法的布线方案：
```plain
#+.+.# #.+..# #++..#
+++++# ..+++# .++++#
.+#### .+#### .+####
.++++# .+...# .+...#
合法 不连通 有回路
```

inputFormat:
输入第一行是两个空格分隔的整数 $n$ 和 $m$，代表布线问题格子的行数和列数。

接下来 $n$ 行，每行 $m$ 个字符（`#`、`+`、`.` 中的一个），描述了具体的布线问题。

输入数据保证至少存在一种合法的布线方案。输入数据中至少有一个 `+`。

outputFormat: 输出 $n$ 行，每行 $m$ 个字符，代表最优的布线方案，其中被布线的格子尽可能多。如有多种可能的方案，输出任意一种即可。

hint:
### 数据规模

对于 $40\%$ 的数据，满足 $n × m \le 16$。

对于 $100\%$ 的数据，满足 $1\le n, m \le 6$。

### 评分标准

在你的布线方案合法（连通且无回路）的前提下：

- 如果你的方案是最优布线方案，即布线的格子最多，该测试点得满分。
- 否则，该测试点得一半分数。

>本题原始满分为 $20\text{pts}$。

---

SPJ Provider：@[scp020](https://www.luogu.com.cn/user/553625)


title: [_-0 A] 考试

background: 小 $\mathfrak{g}$ 参加一场考试时，不小心把答题卡填反了。

description:
答题卡有 $n (1 \le n \le 10^9)$ 行，$m (1 \le m \le 10^9)$ 列，共 $nm$ 道题，**从左到右，从上到下，横向排列**。

每道题有 $c (4 \le c \le 10^9)$ 个选项。其中，前 $k(0 \le k \le nm)$ 道题为单选题，**有且仅有一个**正确选项；后 $nm - k$ 道题为多选题，正确选项个数**严格大于** $1$ 且**严格小于** $c$。

小 $\mathfrak{g}$ 正确地回答了所有题，但是她不小心把答题卡的方向看反了，从而她的答案排列方式为**从上到下，从左到右，纵向排列**。

题目的评分方式为：选项完全正确得 $1$ 分，多选或错选得 $0$ 分，漏选按比例给分。

形式化地说，若 $A$ 为某道题正确答案选项的集合，$B$ 为答题卡上选项的集合（均为 $\{1,2,3,\cdots,c\}$ 的子集），则该题得分为：

$$\begin{cases}\frac{\lvert B \rvert}{\lvert A \rvert}&\text{if\quad}
B\sube A\\0&\text{otherwise}\end{cases}$$

小 $\mathfrak{g}$ 忘记考试的正确答案是什么了，于是她去问小 $\mathfrak{f}$，如果考试的正确答案在合法范围内等概率随机，那么自己期望得分是多少。由于结果可能很大，她只需要知道结果对 $10^9+7$ 取模的值。

**题目保证 $c$ 和 $2^c-c-2$ 都不是 $10^9+7$ 的倍数。**

但是小 $\mathfrak{f}$ 也不会，所以他来求助万能的你。

inputFormat: 一行，四个用空格分隔的整数 $n,m,k,c$，分别表示答题卡的行数，列数，单选题的数量和每道题的选项个数。

outputFormat: 一行，一个整数，表示期望得分，对 $10^9+7$ 取模。


title: [_-0 B] 地铁

background: 小 $\mathfrak{f}$ 的家乡 A 市最近开通了地铁。

description:
A 市共有 $n (2\le n \le 10^5)$ 个居民点，第 $i$ 个居民点的人口为 $s_i (1 \le s_i \le 10^7)$，同时有 $n-1$ 条双向道路，构成一棵树，第 $i $ 条双向道路连接居民点 $u_i$ 和 $v_i$，人步行走过这条道路需要 $w_i (1 \le w_i\le 10^7)$ 的时间。

现 A 市政府决定开通一条地铁线路。地铁线路是树上的一条简单路径，若路径经过第 $i$ 条道路，那么地铁从这条道路下方经过只需要 $w_i^{\prime} (1 \le w_i^{\prime} \le 10^7)$ 的时间，同时，地铁的进出站**共**需要花费 $t (0 \le t \le 10^7)$ 的时间。

已知，若一个人从一个居民点前往另一个居民点，如果这条路径与地铁经过的路径有至少一条公共**边**，那么就**一定**会选择**尽可能多地**乘坐地铁。如果没有公共边，那么就会选择完全步行。**题目保证对于第 $i$ 条道路有 $w_i^{\prime} \le w_i - t$。** 我们认为，如果两个居民点的人口的乘积越大，那么有人想要在它们之间流动的可能性也越大。

现在，小 $\mathfrak{f}$ 想知道在所有 $\frac{n(n-1)}{2}$ 种建造地铁线路的方案中，$\sum_{a=1}^{n-1}\sum_{b=a+1}^{n}(s_a \cdot s_b \cdot d_{a,b})$ 的最小值，其中 $d_{a,b}$ 表示从居民点 $a$ 前往 $b$（或者从 $b$ 前往 $a$，两者是相等的）所需要的时间。

但是他不会，所以他来求助万能的你。

inputFormat:
第一行，三个用空格分隔的整数 $id,n,t$，表示子任务编号，居民点个数和进出站所需要花费的时间。

接下来 $n$ 行，每行一个整数 $s_i$，表示每个居民点的人口。

接下来 $n - 1$ 行，每行四个用空格分隔的整数 $u_i,v_i,w_i,w_i^{\prime}$，表示每条道路的两个端点，步行所需时间和地铁所需时间。

outputFormat:
一行，一个整数，表示所求的最小值。

答案可能超过 $64$ 位整形表示范围，您可以使用 `__int128` 类型，其表示范围为 $[-2^{127},2^{127}-1]$。

以下为 `__int128` 类型的输入输出模板：

```cpp
#include <bits/stdc++.h>
using namespace std;
__int128 ans;
int main() {
    /* Your code here */
    string str;
    if (!ans) {
        str = "0";
    } else {
        str = "";
        while (ans) {
            str = ((char)(48 + ans % 10)) + str;
            ans /= 10;
        }
    }
    cout << str << endl;
    return 0;
}
```


title: [_-0 C] 猜数

background:
**本质相同的代码原则上至多提交 $\bold{3}$ 次。**

小 $\mathfrak{f}$ 和小 $\mathfrak{g}$ 在玩猜数游戏，但是因为风声太大，他们听不清楚对方说的话……

description:
评测机在区间 $[1,n]$ 中等概率随机地选择一个整数 $x$，你的任务是猜测这个数。

你可以每次给出一个 $[1,n]$ 中的整数 $y$，询问 $y$ 和 $x$ 的大小关系。你最多可以询问 $q$ 次。

但是，由于某些原因，评测机有 $p\%$ 的概率会出错。

具体地说：

- 如果 $y=x$，那么评测机返回 `=`。
- 如果 $y\ne x$，且当前已经是第 $q$ 次询问，那么评测机返回 `!`。
- **得到以上两种结果后，你应当停止询问。**
- 如果 $y>x$，那么评测机有 $(100-p)\%$ 的概率返回 `>`，有 $p\%$ 的概率返回 `<`。
- 如果 $y<x$，那么评测机有 $(100-p)\%$ 的概率返回 `<`，有 $p\%$ 的概率返回 `>`。

每次询问，你需要向**标准输出**输出一个 $[1,n]$ 中的整数，**然后清空缓冲区**。

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

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

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

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

inputFormat:
开始询问之前，一行，三个用空格分隔的整数 $n,p,q$。

对于每一次询问，一行，一个字符，一定是 `=`，`!`，`>`，`<` 四者之一。

outputFormat: 对于每一次询问，一行，一个 $[1,n]$ 中的整数。


title: [NICA #2] GDP

description:
GDP，即国内生产总值，是衡量一个地区经济发展的关键因素。

一种常见的计算 GDP 的方式是支出法，它指的是将社会中购买**最终产品和服务**的**总和**作为 GDP。常见的**最终产品和服务**有：消费（$C$），投资（$I$），政府支出（$G$）和净出口（$\mathrm{NX}$），其中净出口 $\mathrm{NX}$ 为出口贸易额 $X$ 减去进口贸易额 $M$ 的结果。

现在给定了一个地区的消费、投资、政府支出、进口和出口贸易额，请你计算当地的 GDP。

inputFormat: 第一行输入五个正**实数**，分别是 $C,I,G,M,X$，含义如题所示。

outputFormat: 输出一行一个**实数**，表示当地的 GDP。要求输出保留两位小数。

hint: 对于所有数据，$1 \leq C,I,G,M,X \leq 10000$，且小数点后不超过两位。最终计算出的 GDP 必定为正数。


title: [POI 2021/2022 R1] Domino

background: 译自 [XXIX Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Domino](https://sio2.mimuw.edu.pl/c/oi29-1/p/dom/)。

description:
> 有一个 $2$ 行 $n$ 列的矩形，上面有若干个格子被占用了。你要用 $1\times 2$ 或 $2\times 1$ 的牌，覆盖所有未被占用的格子，一个格子不可被占用两次。记方案数为 $m$。

给你 $m$，求出最小的 $n$，使得存在一种方案设置占用格，使得覆盖的方案数恰好为 $m$。无解输出 `NIE`。

inputFormat: 一行一个正整数 $m$。

outputFormat:
如果有解，输出你的答案 $n$。

如果无解，输出 `NIE`。


title: [语言月赛202306] std::cerr

background:
这是一道 **hack 题**。在本题目中，你将得到两个问题和两个解决对应问题的代码，但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括：

1. 输出错误的结果。
2. 运行超时。
3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。

对于这一问题，你需要提交一份符合要求的输入数据，使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能，也可以提交一份以任何语言写成的数据生成器。

每道题占 $50$ 分，本题共 $100$ 分。

---
**提示：如果你使用提交答案功能，请在提交其他题目时记得将语言改回你所使用的语言。**

description:
以下给出两个问题的题目描述：

#### 问题 1

给出整数 $a, b,c$，求 $\left\lceil\dfrac {a}{b - c} \right\rceil$ 的值，其中 $\left\lceil x \right\rceil$ 表示不小于 $x$ 的最小整数。

#### 问题 2

`std::cerr` 是一个输出到**标准错误流**的输出工具。如果你运行如下程序：

```cpp
#include <iostream>
int main() {
  std::cerr << "Hello Luogu!" << std::endl;
}
```

你会发现有 $\texttt{Hello Luogu!}$ 被打印在了命令行 /cmd 中；但是，如果你在 `main` 函数开头加入 `freopen("text.txt", "w", stdout)`，再运行这个程序，然后打开 `text.txt`，会发现文件是空的，而 $\texttt{Hello Luogu!}$ 仍然被打印到了命令行 /cmd 中。

由此，`std::cerr` 在算法竞赛中有了一个重要应用：使用 `std::cerr` 输出中间变量，变量会被打印到屏幕上，但却不会被打印到输出文件/标准输出中。同时，`std::cerr` 有**刷新缓冲区**的作用。以往关闭流同步代码一旦产生 Runtime Error，在这之前被打印到 stdout 的内容如果仍在缓冲区，则不会被输出，而使用 `std::cerr` 则不会有这个问题，因为每次完成输出后都会将缓冲区内容直接刷新到标准错误流中。

例如，你可以尝试在本地运行如下代码：
```cpp
#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cout << "Hello Luogu!\n";
    int x = *((int*)0);
}
```
对于大多数机器，屏幕上什么都不会打印，应用程序就会异常终止，这种情况是不利于调试的，因为无法二分出导致程序终止语句是哪一条。但是，如果你将上文中的 `std::cout` 换成 `std::cerr` 再尝试运行这一程序，就会发现在程序异常终止前，$\texttt{Hello Luogu!}$ 被打印到了屏幕上。需要注意的是，刷新缓冲区是一件速度很慢的事情，如果刷新次数太多，会导致程序超时。

在刚结束的 ICPC 山东省赛中，扶苏试图使用 `std::cerr` 来完成对 K 题的调试，但是在四小时 59 分提交的代码中，扶苏本已经写出了正确的代码，但却忘记了删除 `std::cerr` 的调试语句，虽然这**不会**导致她向选手输出中输出额外信息，但因为刷新缓冲区次数过多，她本次提交被判定为 `TIME LIMIT`，与省赛冠军失之交臂。

![](https://picx.zhimg.com/v2-e4ea329a8ca6efbe71a5b97c2e6aeb25_r.jpg?source=1940ef5c)

![](https://pica.zhimg.com/v2-b47fa9073fc1dfa67ee33e7920ca6100_r.jpg?source=1940ef5c)

（计算可得，如果第四发 K 题的 attempt 通过，『四小时下班』将以 $8$ 分钟罚时的优势绝杀夺冠）

因此，对于一个字符串，她觉得如果这个字符串含有 `std::cerr` 作为子串，则她觉得这个字符串『不太行』，否则她觉得这个字符串『非常行』。

给定 $T$ 个字符串，请你判断它们是不是『不太行』。

inputFormat:
#### 问题 1

输入只有一行三个整数，依次表示 $a$，$b$，$c$。

#### 问题 2

第一行是一个整数，表示输入字符串个数 $T$。
接下来 $T$ 行，每行一个字符串，表示需要你判断的字符串。
在问题 $2$ 中，输入**不能有**行末空格。但可以有文末回车。

outputFormat:
#### 问题 1

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

#### 问题 2

输出一行一个整数，表示『不太行』的字符串数量。

samples:
3
std::cerr
std::cerr<<"HelloLuogu!";
std::cout<<"HelloLuogu!";

hint:
### 样例组与实际输入的说明

两个样例分别对应两个问题的样例输入输出。

如果你直接采用『提交答案』的方式，请分别将两个输入数据命名为 `1.in`、`2.in`，并打成 zip 压缩包进行提交；

如果你采用提交数据生成器的方式，你的生成器可以从标准输入读入一个整数 $x$，满足 $1 \leq x \leq 2$，表示该测试点对应的问题编号，然后**输出对应的输入数据**。

显然，你的程序不应该读入『输入格式』里提到的任何内容（而应该构造它们），也不应该输出『样例输出』里提到的任何内容（而是只输出你构造的输入数据）。你不应该使用样例测试你的程序，这只是对两个问题的样例说明。

### 数据规模要求

你给出的数据必须满足如下要求：

1. 完全符合『输入格式』的规定，不能有多余的输入，但是可以有文末回车，问题 $1$ 可以有行末空格。
2. 对于问题 $1$，$1 \leq a, b, c \leq 100$，$b \neq c$。
3. 对于问题 $2$，$1 \leq T \leq 10^6$，输入字符串的总长度不超过 $2 \times 10^6$，输入的任何字符串不能为空串，且只能含有可见字符（ASCII 值在 $33$ 到 $126$ 之间，空格**不算**可见字符）。

### 目标代码

你需要 hack 如下的代码：

#### 问题 1

```cpp
#include <iostream>
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int d = b - c;
  cout << ((a + d - 1) / d) << endl;
}
```

#### 问题 2

```cpp
#include <iostream>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int T;
  std::string s;
  int ans = 0, cur = 0;
  for (std::cin >> T; T; --T) {
    std::cin >> s;
    ++cur;
    if (s.find("std::cerr") != std::string::npos) {
      std::cerr << cur << '\n';
      ++ans;
    }
  }
  std::cout << ans << std::endl;
}
```

目标代码的编译选项为 `-std=c++14 -fno-asm -O2`。编译器为洛谷提供的 g++。你可以在『在线 IDE』中选择 C++14 语言来获得完全相同的编译环境。

#### 数据判定

你给出的数据必须完全符合『数据规模要求』，否则将得到 Unaccepted 的结果。

#### 超时判定

程序每执行若干条指令，我们会检测一遍程序的运行时间。我们保证两次检测之间的指令条数是一个输入规模无关的量，也即每执行 $O(1)$ 条指令会进行一次检测。且两次检测之间的指令条数不会太多，一般不超过 $100$ 条 C++ 语句。

如果程序的运行时间超过 $500 \text{ms}$，则判定为程序运行超时，返回 accepted 结果。

#### 结果错误判定

如果程序在规定的时间内结束且给出了一个输出，我们会比较这个输出和**完全正确的输出**，如果二者不同，则判定为 hack 成功，返回 accepted 结果。

#### 未定义行为判定

我们会在每次**显式**的调用数组元素前判断数组下标是否超过数组范围，如果超过，则判定为 hack 成功，返回 accepted 结果。

这就是说，如果你希望通过未定义行为进行 hack，只能对显式的调用数组元素的行为进行 hack。

### 样例程序

这是一份可以帮你理解你需要输出的内容的样例程序，**但它不能给出正确的 hack 数据**。直接提交此程序不会得分。

```cpp
#include <iostream>

using namespace std;

int main() {
  int taskId;
  cin >> taskId;
  if (taskId == 1) {
    cout << "" <<endl;
  } else if (taskId == 2) {
    cout << "" << endl;
  } else { // 这个 else 不会被执行
    cout << "Stupid Fusu!" << endl;
  }
}
```

如果你使用『提交答案』功能，请务必保证打开压缩包后能且仅能**直接**看到两个 `.in` 文件。这就是说，文件结构必须是：

```plain
ans.zip
 |---1.in
 |---2.in
```

两个文件不应该被额外的文件夹包含，即文件结构不能是：

```plain
ans.zip
 |---ans(folder)
      |---1.in
      |---2.in
```

### 关于评测信息的说明

如果 hack 成功，对应测试点的信息为 accepted。如果返回其他信息，说明程序本身有误。

例如，如果返回 TLE，不代表成功的将对应程序 hack 至超时，而是表示数据生成器本身运行超时，测试点不得分。

特别的，返回 UKE 结果可能是数据不合法（有多余内容、缺少内容或数据范围不符合要求）。


title: [POI 2021/2022 R1] Druk

background: 译自 [XXIX Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Druk](https://sio2.mimuw.edu.pl/c/oi29-1/p/dru/)。

description:
给你一个 $n\times m$ 的字符矩形，只含小写英文字母。

你需要制作两块模板，一个是横的（一行 $l$ 列），一个是竖的（$l$ 行一列），$l$ 称为模板长度，上面有完全相同的字符串（从左到右，从上到下，不可翻转）。你需要保证你可以用这两块模板不重不漏地印刷这个字符矩形。

模板的制作方案可能有很多，你只需要输出所有的可行的模板长度即可。

inputFormat:
第一行两个正整数 $n,m$，表示矩形大小。

接下来是一个 $n$ 行 $m$ 列的字符矩形，只含小写英文字母。

outputFormat:
第一行一个整数，表示你找到的可行长度的个数。

第二行若干个整数，你找到的所有可行长度。

samples:
5 8
aabaaaaa
babaabbb
aabaaaaa
aabaaaaa
abaaabaa

samples:
4 9
aabaaabaa
babababab
aabaaabaa
abaabaaba

hint:
样例一解释：![图挂了](https://cdn.luogu.com.cn/upload/image_hosting/2zs08vop.png)

样例四解释：![图挂了](https://cdn.luogu.com.cn/upload/image_hosting/p1zo7v6x.png)

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

| 子任务编号 | 附加限制 | 分数 |
| :----------: | :----------: | :----------: |
| 1 | $n=1,m\leq 1000$ | 10 |
| 2 | $n\leq 3,m\leq 1000$ | 25 |
| 3 | $n,m\leq 20$ | 20 |
| 4 |  | 45 |


title: [POI 2021/2022 R1] Impreza krasnali

background: 译自 [XXIX Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Impreza krasnali](https://sio2.mimuw.edu.pl/c/oi29-1/p/imp/)。

description:
有 $n$ 个人依次站成一排，每个人手上都有一个数字，这 $n$ 个数字形成一个排列。

每个人会二选一地报告他左边或右边的人手上的数字。注意第一个人与第 $n$ 个人并不相邻，所以第一个人总是会报告第二个人的数字，第 $n$ 个人总是会报告第 $n-1$ 个人的数字。

现在你得到了 $n$ 个人报告的数字，求出原先的排列有多少种可能。

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

第二行 $n$ 个整数，表示每个人报告的数字。

outputFormat: 一行一个整数，你的答案模 $10^9+7$。


title: [POI 2021/2022 R1] Układanie kart

background: 译自 [XXIX Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Układanie kart](https://sio2.mimuw.edu.pl/c/oi29-1/p/ukl/)。

description:
我们用以下方法将一个排列递增排序:

一次操作：记第一个数字为 $k$，在排列中找到 $k-1$（$k=1$ 则取 $n$），把 $k-1$ 拉到排列的第一个位置，中间的数字依次后移。

一次操作的价值：$k-1$（或 $n$）在原排列的位置（这个从 $0$ 开始标号）。

一个排列的价值：进行若干次操作直到排列有序，价值为每次操作的价值之和。

给你 $n,m$，求所有 $n!$ 个排列的价值之和，对 $m$ 取模。

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

outputFormat: 一行一个整数，答案对 $m$ 取模的结果。


title: [NICA #2] 拉面馆

description:
Aya 正在经营一家拉面馆。拉面馆的营业时间是 $a$ 时，歇业时间是 $b$ 时。

拉面馆总是人满为患，客流稳定。因此每一个小时，拉面馆都需要用 $k$ 斤面粉来拉面。每一斤面粉拉出来的面可以售出 $r$ 元钱，但是每一斤面粉的成本是 $c$ 元钱。

如果不考虑拉面过程中的损耗以及额外开销，那么 Aya 开一天的拉面馆的净利润是多少钱呢？提示：净利润是收入减去成本。

inputFormat: 共一行，输入五个正整数，分别表示 $a,b,k,r,c$，含义如题意所述。

outputFormat: 输出一行，一个整数，表示 Aya 开一天的拉面馆的净利润是多少钱。

hint: 数据保证，$1 \leq a<b \leq 24$，$1 \leq k,r,c \leq 10^6$。**请仔细考虑数据范围。**


title: [NICA #2] 台式烤香肠

description:
Aya 想要购买台式烤香肠。在他的候选项里有两个品牌的台式烤香肠：

- 品牌 A：每包共含 $a$ 根台式烤香肠，价格为 $b$ 元，每一根台式烤香肠的美味程度为 $c$；
- 品牌 B：每包共含 $d$ 根台式烤香肠，价格为 $e$ 元，每一根台式烤香肠的美味程度为 $f$；

Aya 现在只有 $k$ 元钱，他希望能够购买到的台式烤香肠均为同一品牌，且所有烤香肠的美味程度之和最大。请告诉他美味程度之和最大是多少。注意，Aya 只能购买整数包台式烤香肠。

inputFormat:
输入共三行。

第一行输入三个正整数 $a,b,c$，含义如题所述；

第二行输入三个正整数 $d,e,f$，含义如题所述；

第三行输入一个正整数 $k$，含义如题所述。

outputFormat: 输出一个整数，表示美味程度之和最大是多少。

hint: 数据保证，$1 \leq a,b,c,d,e,f,k \leq 10^6$。**请仔细考虑数据范围。**


title: [NICA #2] 字符串入门题

background: 小波说这是字符串入门题极好的，所以这是极好的。

description:
给定一个仅包含大小写字母和数字的字符串 $s$，问能否将 $s$ 拆分成至少 $k$ 个子串 $s_1,s_2,\dots,s_t(t\ge k)$ 满足 $\forall 1<i\le t$ 有 $s_i$ 是 $s_1s_2\dots s_{i-1}$（这里表示的是拼接）的子串。

一个字符串 $s$ 是另一个字符串 $t$ 的子串当且仅当可以通过删除 $t$ 的一个可以为空的前缀以及一个可以为空的后缀后得到 $s$。

inputFormat:
第一行两个正整数 $n,k$，其中 $n$ 是 $s$ 的长度。

第二行一个字符串 $s$，仅包含大小写字母和数字。

outputFormat:
如果不存在这样的拆分方案，输出 `-1` 。

否则第一行输出一个正整数 $t(t\ge k)$，表示你要把 $s$ 拆分成 $t$ 个字符串。

接下来 $t$ 行，每行一个字符串，第 $i$ 行表示 $s_i$。你需要保证 $s_1s_2\dots s_t=s$。

hint:
#### 样例 1 解释

`1145|14`是一种合法的拆分方案，因为拆分出了 $2$ 个字符串且 $2\ge k$，并且`14`是`1145`的一个子串。

#### 样例 2 解释

`a1A|a1|1Aa`是一种合法的拆分方案，因为拆分出了 $3$ 个字符串且 $3\ge k$，并且`a1`是`a1A`的一个子串，且`1Aa`是`a1Aa1`的一个子串。

#### 样例 3 解释

尝试所有拆分方案后发现无论如何拆分都无法满足条件。

#### 数据范围

对于所有数据，满足 $2\le k\le n\le 10^6$，$s$ 仅由大小写字母和数字构成。


title: [NICA #2] 降雨量

description:
气象意义上划分降雨等级的标准如下：

- 小雨（Drizzle）：$24$ 小时降雨量小于 $10$ 毫米；
- 中雨（Moderate Rain）：$24$ 小时降雨量大于等于 $10$ 毫米，但是小于 $25$ 毫米。
- 大雨（Heavy Rain）：$24$ 小时降雨量大于等于 $25$ 毫米，但是小于 $50$ 毫米。
- 暴雨（Torrential Rain）：$24$ 小时降雨量大于等于 $50$ 毫米。

此外，短时强降雨（Flash Heavy Rain）由于突发性强，容易引发城市内涝，因此也会特别分类，其指代的是 $1$ 小时降雨量大于等于 $20$ 毫米的天气现象。

需要注意的是，$1$ 小时降雨和 $24$ 小时降雨并不呈矛盾关系。例如说如果 $1$ 小时降雨达到 $30$ 毫米，它既属于短时强降雨，也属于大雨的标准。

现在给定某地降水量，以及该降水量达成的小时数（保证仅为 $1$ 或者 $24$），请输出其属于什么量级的降水。

inputFormat: 输入一行两个正整数，分别表示某地的降水量 $x$，以及该降水量达成的小时数 $h$。

outputFormat:
输出 $1$ 或 $2$ 行。第一行表示以 $24$ 小时标准进行统计，属于哪个等级的降雨；

若 $h=1$，则第二行表示以 $1$ 小时标准进行统计是否满足短时强降雨标准，若满足则输出 $\tt YES$，否则输出 $\tt NO$。

samples:
75 24
Torrential Rain

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

对于第二组样例，你应当认为只是下了现在这一小时的雨，而 $25$ 毫米的降雨量属于大雨标准，因此输出 $\text{Heavy Rain}$。换而言之，你不应将降雨量 $\times 24$ 后计算 $24$ 小时降雨总量。

数据保证，$1 \leq x \leq 1000$，$h=1$ 或 $24$。


title: [NICA #2] 音乐播放器

description:
小 Ran 喜欢听歌，但是她有选择困难症，所以她会使用播放器的随机播放功能。

接下来播放器会依次播放 $n$ 首歌，第 $i$ 首歌的长度为 $a_i$ 秒。每首歌曲的长度从 $100$ 秒至 $320$ 秒不等。

但不是每首歌小 Ran 都喜欢，因此她遇到了她不喜欢的歌曲会只放 $10$ 秒钟就跳到下首歌（跳到下首歌的时间可以忽略不计）。当然如果是她喜欢的歌，她就会全部听完。

小 Ran 希望知道，她听完这些歌，一共需要多少秒的时间。

inputFormat:
第一行输入一个正整数 $n$，表示歌曲支数；

第二行开始往下 $n$ 行，每行输入两个正整数 $a$ 和 $b$：

- 其中 $a$ 表示当前歌曲的长度，$b=0$ 表示小 Ran 不喜欢这首歌曲，$b=1$ 表示小 Ran 喜欢这首歌曲。

outputFormat: 输出一行，一个正整数，表示她听完这些歌，一共需要多少秒的时间。


title: [NICA #2] 优秀正整数

description:
Aya 定义符合如下条件的正整数 $x$ 为优秀正整数：

- $x$ 为一个完全平方数；
- $x$ 的各位数位和为质数；

例如说，$25$ 是一个优秀正整数，因为 $25=5\times 5$，为完全平方数，且 $2+5=7$，为质数。

现在给定 $L,R$，请求出 $L$ 到 $R$（包含 $L$ 和 $R$）的正整数中，所有优秀正整数的乘积，对 $998244353$ 取模的值。若不存在优秀正整数，则输出 $0$。

inputFormat: 一行，输入两个正整数 $L,R$。

outputFormat: 输出 $L$ 到 $R$（包含 $L$ 和 $R$）的正整数中，所有优秀正整数的乘积，对 $998244353$ 取模的值。若不存在优秀正整数，则输出 $0$。

hint: 数据保证，对于所有数据，$1 \leq L \leq R \leq 10^{12}$。


title: [NICA #2] 高考组题

description:
高考是能决定每个考生命运的考试，因此作为组卷人的 Aya 将高考组卷视为重中之重。现在 Aya 有 $n$ 个备选的高考题。

对于每一道可能选入试卷的高考题，其有 $k$ 个指标来评判它各个方面的维度，例如难度、新颖度、与现实生活的结合性等。每个指标均为一个正整数。

Aya 认为，一个题被放入高考卷的必要性，是这些指标的平均值。他认为，必要性前二高的试题必须要被放进高考试卷。若有多个必要性前二大的试题则选择较早出现的那个。请告诉 Aya 哪个题目是必须要放进高考试卷的。

inputFormat:
第一行输入两个正整数 $n,k$，含义如题所述；

第二行开始，往下 $n$ 行，每行输入 $k$ 个正整数，以空格隔开，第 $i$ 行表示第 $i-1$ 道题的各个指标是多少。

outputFormat: 输出两行，表示必要性前两大的试题是哪两个题。优先输出必要性最高的；若有多个题目必要性相同，则优先输出较早出现的。

hint: 数据保证，$2 \leq n \leq 100$，$1 \leq k \leq 10$，$1 \leq$ 一道试题的各个指标 $\leq 100$。


title: [NICA #2] 亘久不变

background: 此世间，亘久不变之物若显真容，其必似华鸟风月般庄严凛然、隽美无二。

description:
给定 $n$ 个正整数 $a_i$ 与三个正整数 $x,y,p$，定义一次对**非负整数** $t$ 的变换为：

- 将 $t$ 替换为 $(xt+y)\bmod p$。

定义数 $t$ 是“$k$-不变”的，当且仅当其经过 $k$ 次变换后值不变。

小 Ran 希望知道给定的数组 $a$ 中有多少数是“$k$-不变”的，为了更加准确的知道答案，她会给出 $q$ 组 $k$ 进行询问。

inputFormat:
第一行四个正整数 $n,x,y,p$，意义同题目描述。

第二行 $n$ 个正整数，其中第 $i$ 个正整数为 $a_i$，意义同题目描述。

第三行一个正整数 $q$，意义同题目描述。

接下来 $q$ 行每行一个正整数 $k_i$，代表询问 $a$ 中有多少数是“$k_i$-不变”的。

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

hint:
数据保证，$1\le n\le 10^5$，$1\le p,q\le 10^3$，$1\le a_i,x,y,k_i\le 10^9$。

**注意 $p$ 不一定是质数。**


title: [NICA #2] 回来吧我的小波

background: 小波我错了，你快回来吧！

description:
给定一个仅包含数字 $1,2,3,4,5,6,7,8,9$ 的数字串 $s$，你要选择两个不交区间 $[l_1,r_1],[l_2,r_2](1\le l_1\le r_1<l_2\le r_2\le |s|)$，设 $[l_1,r_1]$ 区间串取出来的数字为 $x$，$[l_2,r_2]$ 区间串取出来的数字为 $y$，要求 $x|y$。如果存在这样两个不交区间，那么我们称数字串 $s$ 是好的。（这里的 $|$ 表示整除，你可以理解为 $x$ 为 $y$ 的一个因数）

现在给定一个仅包含数字 $1,2,3,4,5,6,7,8,9$ 的数字串 $S$，询问它有多少个子串是好的。（这里的子串**不要求**是本质不同的）

outputFormat: 输出一个正整数，表示好的子串数量。

hint:
#### 样例1解释

只有一个好串 `327`，你可以选择两个不交区间 $[1,1],[2,3]$，取出来的数字分别是 $3$ 和 $27$，显然 $3$ 是 $27$ 的一个因数，所以这个串是好串。

其他子串 `3`，`2`，`7`，`32`，`27` 都不是好的，因为不存在这样的两个不交区间。

#### 样例2解释

共有 $12$ 个好串，分别为 `114514`、`11451`、`1145`、`114`、`11`、`14514`、`1451`、`145`、`14`、`4514`、`514`、`14`。（注意到里面有两个 `14`，但是由于它们位置不同，我们还是认为这是两个不同的子串）

#### 数据范围

对于所有数据，保证 $2\le |S|\le 10^6$。


title: [NICA #2] 爱与不爱

background:
是爱还是厌　是爱还是厌\
啦啦啦啦~\
勉勉强强着　勉勉强强着\
啦啦啦啦啦~

description:
小 Ran 有一个长度为 $n$ 的正整数序列 $a$，她可以进行如下操作任意多次（包括零次）：

- 选择两个不同的数 $i,j$（$1\le i,j\le n$），然后将 $a_i$ **除以 $2$ 后下取整**，将 $a_j$ 乘二。要求操作完毕后的 $a_i$ 必须为正整数。

小 Ran 希望使序列的总和**最小**。输出最终序列的总和。

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

第二行输入 $n$ 个正整数，以空格隔开，表示 $a_i$。

outputFormat: 一个整数，代表操作后最终序列的总和。


title: [NICA #2] 回溯的雨

description:
小 Ran 有两个正整数 $x,y$，她还有两个长度为 $n$ 的正整数序列 $a$ 与 $c$ 满足 $a_ix+y=c_i$ （$1\le i\le n$）。

很可惜的是，她忘记了所有 $a_i$ 的值与 $y$ 的值。她给你了 $x$ 的值与序列 $c$，并希望你能还原出一组 $y$ 的值与序列 $a$ 使得原先的条件被满足。

当然，可能存在很多组这样的解，所以她希望你能最大化 $y$ 的值并输出它（注意到你并不需要输出 $a$ 序列）。如果不能还原出这样一组数，请输出 $-1$ 来报告无解。

inputFormat:
第一行两个正整数 $n$ 与 $x$，含义同题目描述。

第二行 $n$ 个正整数，描述数组 $c$，其中第 $i$ 个数即为 $c_i$。

outputFormat: 输出一个正整数，代表你还原出的最大的 $y$ 的值。如果不能还原出这样一组正整数，则输出 $-1$。


title: 「SFCOI-3」进行一个走的行

background:
**公告：注意存在 $l_i > r_i$ 的情况，此时操作无效。**

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

小 L 热衷于行走。

description:
小 L 来到了一处景点，他想要在这里的主干道上行走。

主干道上有若干关键点，他可以将其抽象为一个长为 $n$ 的序列 $a$，每个 $a_i$ 都是一个三元组，可以表示为 $(l_i, r_i, v_i)$，其具体含义形如：

- 若 $r_i = -1$，表示一个需要买票进入的景点，票价为 $l_i$ 代币，游览完成后他会得到 $v_i$ 的愉悦值。
- 若 $r_i \neq -1$，表示一个礼品派发点，若他持有的代币面值之和 $x$ 满足 $l_i \leq x \leq r_i$，他可以领取一份礼品，并会得到 $v_i$ 的愉悦值。

他打算在这条主干道上行走 $m$ 次，每次他给出了行走起点 $l$ 和终点 $r$，一开始他持有的代币面值之和为 $x$，初始愉悦值为 $0$。

他将从 $l$ 开始向右依次经过 $i \in [l, r]$，他会做如下操作：

- 若 $r_i = -1$，如果他持有的代币在支付完当前景点门票费用后还有剩余，他会游览这个景点。
- 若 $r_i \neq -1$，如果可以，他会领取一份礼品。

请你帮他快速求出每次行走结束后他的愉悦值。

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

接下来 $n$ 行，其中第 $i$ 行有三个整数 $l_i, r_i, v_i$；

接下来 $m$ 行，每行三个整数 $l, r, x$，表示一个询问。

outputFormat: $m$ 行，每行一个整数，表示行走结束后他的愉悦值。

hint:
**本题开启捆绑测试。**

- Subtask 1（10 pts）：$1 \leq n, m \leq 5 \times 10^3$。
- Subtask 2（10 pts）：$r_i \neq -1$。
- Subtask 3（20 pts）：$r_i = -1$。
- Subtask 4（10 pts）：$1 \leq n, m \leq 7.5 \times 10^4$，性质 A。
- Subtask 5（20 pts）：$1 \leq n, m \leq 7.5 \times 10^4$。
- Subtask 6（10 pts）：数据在范围内随机生成，性质 B。
- Subtask 7（20 pts）：无特殊限制。

性质 A：$1 \leq l_i \leq 7.5 \times 10^4$，$r_i = -1$ 或 $1 \leq r_i \leq 7.5 \times 10^4$，$1 \leq x \leq 7.5 \times 10^4$。

性质 B：$r_i = -1$ 时 $1 \leq l_i \leq 2 \times 10^5$。

对于 $100\%$ 的数据：

- $1 \leq n, m \leq 2 \times 10^5$。
- $1 \leq l_i \leq 10^9$，$r_i = -1$ 或 $1 \leq r_i \leq 10^9$。
- $1 \leq v_i \leq 10^9$。
- $1 \leq l \leq r \leq n$，$1 \leq x \leq 10^9$。


title: [蓝桥杯 2023 国 B] 子 2023 / 双子数

description:
## A 子 2023

小蓝在黑板上连续写下从 $1$ 到 $2023$ 之间所有的整数，得到了一个数字序列：

$$S = 12345678910111213\cdots 20222023$$

小蓝想知道 $S$ 中有多少种子序列恰好等于 $2023$？

提示，以下是 $3$ 种满足条件的子序列（用中括号标识出的数字是子序列包含的数字）：

$$1[\textbf2]34567891[\textbf0]111[\textbf2]1[\textbf3]14151617181920212223 \cdots$$

$$1[\textbf2]34567891[\textbf0]111[\textbf2]131415161718192021222[\textbf3] \cdots$$

$$1[\textbf2]34567891[\textbf0]111213141516171819[\textbf2]021222[\textbf3] \cdots$$

注意以下是不满足条件的子序列，虽然包含了 $2$、$0$、$2$、$3$ 四个数字，但是顺序不对：

$$1[\textbf2]345678910111[\textbf2]131415161718192[\textbf0]21222[\textbf3] \cdots$$

## B 双子数

若一个正整数 $x$ 可以被表示为 $p^2 \times q^2$，其中 $p$、$q$ 为质数且 $p \neq q$，则 $x$ 是
一个 “双子数”。请计算区间 $[2333, 23333333333333]$ 内有多少个 “双子数”？

inputFormat: 输入一个大写字母，表示第几个问题。

outputFormat: 根据所输入的问题编号，输出对应问题的答案。

hint:
答题模板，可供参考。

```cpp
#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "The answer of task A", // 双引号中替换为 A 题的答案
        "The answer of task B", // 双引号中替换为 B 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}
```

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 A、B 题


title: [蓝桥杯 2023 国 B] 班级活动

description:
小明的老师准备组织一次班级活动。班上一共有 $n$ 名（$n$ 为偶数）同学，老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个 $n$ 以内的正整数作为 id，第 $i$ 名同学的 id 为 $a_i$。

老师希望通过更改若干名同学的 id 使得对于任意一名同学 $i$，有且仅有另一名同学 $j$ 的 id 与其相同（$a_i = a_j$）。请问老师最少需要更改多少名同学的 id？

inputFormat:
输入共 $2$ 行。

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

第二行为 $n$ 个由空格隔开的整数 $a_1, a_2, \cdots, a_n$。

outputFormat: 输出共 $1$ 行，一个整数。

hint:
### 样例说明

仅需要把 $a_1$ 改为 $3$ 或者把 $a_4$ 改为 $1$ 即可。

### 评测用例规模与约定

- 对于 $20\%$ 的数据，保证 $n \le 10^3$。
- 对于 $100\%$ 的数据，保证 $n \le 10^5$。

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 C 题


title: [蓝桥杯 2023 国 B] 合并数列

description:
小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案，分别将他们列为两个数组 $\{a_1, a_2, \cdots a_n\}$ 和 $\{b_1, b_2, \cdots b_m\}$。两个数组的和相同。

定义一次合并操作可以将某数组内相邻的两个数合并为一个新数，新数的值是原来两个数的和。小明想通过若干次合并操作将两个数组变成一模一样，即 $n = m$ 且对于任意下标 $i$ 满足 $a_i = b_i$。请计算至少需要多少次合并操作可以完成小明的目标。

inputFormat:
输入共 $3$ 行。

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

第二行为 $n$ 个由空格隔开的整数 $a_1, a_2, \cdots, a_n$。

第三行为 $m$ 个由空格隔开的整数 $b_1, b_2, \cdots, b_m$。

outputFormat: 输出共 $1$ 行，一个整数。

hint:
### 样例说明

只需要将 $a_2$ 和 $a_3$ 合并，数组 $a$ 变为 $\{1,5,4\}$，即和 $b$ 相同。

### 评测用例规模与约定

 - 对于 $20\%$ 的数据，保证 $n,m \le 10^3$。
 - 对于 $100\%$ 的数据，保证 $n, m \le 10^5$，$0 < a_i, b_i \le 10^5$。

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 D 题


title: [蓝桥杯 2023 国 B] 数三角

description: 小明在二维坐标系中放置了 $n$ 个点，他想在其中选出一个包含三个点的子集，这三个点能组成三角形。然而这样的方案太多了，他决定只选择那些可以组成等腰三角形的方案。请帮他计算出一共有多少种选法可以组成等腰三角形？

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

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

后面 $n$ 行，每行两个整数 $x_i, y_i$ 表示第 $i$ 个点的坐标。

outputFormat: 输出共 $1$ 行，一个整数。


title: [蓝桥杯 2023 国 B] 删边问题

description:
给定一个包含 $N$ 个结点 $M$ 条边的无向图 G，结点编号 $1 \cdots N$。其中每个结点都有一个点权 $W_i$。

你可以从 $M$ 条边中任选恰好一条边删除，如果剩下的图恰好包含 $2$ 个连通分量，就称这是一种合法的删除方案。

对于一种合法的删除方案，我们假设 $2$ 个连通分量包含的点的权值之和分别为 $X$ 和 $Y$，请你找出一种使得 $X$ 与 $Y$ 的差值最小的方案。输出 $X$ 与 $Y$ 的差值。

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

第二行包含 $N$ 个整数，$W_1, W_2, \cdots, W_N$。

以下 $M$ 行每行包含 $2$ 个整数 $U$ 和 $V$，代表结点 $U$ 和 $V$ 之间有一条边。

outputFormat: 一个整数代表最小的差值。如果不存在合法的删除方案，输出 $-1$。

hint:
### 样例说明

由于 $1$ 和 $2$ 之间实际有 $2$ 条边，所以合法的删除方案有 $2$ 种，分别是删除 $(2, 3)$ 之间的边和删除 $(3, 4)$ 之间的边。

删除 $(2, 3)$ 之间的边，剩下的图包含 $2$ 个连通分量：$\{1,2\}$ 和 $\{3,4\}$，点权和分别是 $30$、$70$，差为 $40$。

删除 $(3, 4)$ 之间的边，剩下的图包含 $2$ 个连通分量：$\{1,2,3\}$ 和 $\{4\}$，点权和分别是 $60$、$40$，差为 $20$。

### 评测用例规模与约定

 - 对于 $20\%$ 的数据，$1 \le N, M \le 10000$。
 - 对于另外 $20\%$ 的数据，每个结点的度数不超过 $2$。
 - 对于 $100\%$ 的数据，$1 \le N, M \le 200000$，$0 \le W_i \le 10^9$，$1 \le U, V \le N$。

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 F 题


title: [蓝桥杯 2023 国 B] AB 路线

description:
有一个由 $N \times M$ 个方格组成的迷宫，每个方格写有一个字母 `A` 或者 `B`。小蓝站在迷宫左上角的方格，目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。

由于特殊的原因，小蓝的路线必须先走 $K$ 个 `A` 格子、再走 $K$ 个 `B` 格子、再走 $K$ 个 `A` 格子、再走 $K$ 个 `B` 格子……如此反复交替。

请你计算小蓝最少需要走多少步，才能到达右下角方格？

注意路线经过的格子数不必一定是 $K$ 的倍数，即最后一段 `A` 或 `B` 的格子可以不满 $K$ 个。起点保证是 `A` 格子。

例如 $K = 3$ 时，以下 $3$ 种路线是合法的：

```plain
AA
AAAB
AAABBBAAABBB
```

以下 $3$ 种路线不合法：

```plain
ABABAB
ABBBAAABBB
AAABBBBBBAAA
```

inputFormat:
第一行包含三个整数 $N$、$M$ 和 $K$。

以下 $N$ 行，每行包含 $M$ 个字符（`A` 或 `B`），代表格子类型。

outputFormat: 一个整数，代表最少步数。如果无法到达右下角，输出 $-1$。

hint:
### 样例说明

每一步方向如下：下右下右上右下下；路线序列： `AABBAABBA`。

### 评测用例规模与约定

 - 对于 $20\%$ 的数据，$1 \le N, M \le 4$。
 - 对于另 $20\%$ 的数据，$K = 1$。
 - 对于 $100\%$ 的数据，$1 \le N, M \le 1000$，$1 \le K \le 10$。

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 G 题


title: [蓝桥杯 2023 国 B] 抓娃娃

description: 小明拿了 $n$ 条线段练习抓娃娃。他将所有线段铺在数轴上，第 $i$ 条线段的左端点在 $l_i$，右端点在 $r_i$。小明用 $m$ 个区间去框这些线段，第 $i$ 个区间的范围是 $[L_i, R_i]$。如果一个线段有 **至少一半** 的长度被包含在某个区间内，则将其视为被这个区间框住。请计算出每个区间框住了多少个线段？

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

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

后面 $n$ 行，每行两个整数 $l_i, r_i$。

后面 $m$ 行，每行两个整数 $L_i, R_i$。

outputFormat: 输出共 $m$ 行，每行一个整数。

hint:
### 评测用例规模与约定

 - 对于 $20\%$ 的数据，保证 $n, m \le 10^3$。
 - 对于 $100\%$ 的数据，保证 $n, m ≤ 10^5$，$l_i < r_i$，$0 < l_i, r_i, L_i, R_i \le 10^6$，$\max \{r_i − l_i\} \le \min \{R_i − L_i\}$。

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 H 题


title: [NOI2023] 贸易

description:
近年来，A 国的商贸发展迅猛，但国内的道路建设却跟不上步伐，明显成为了人们贸易往来的限制，管理者为此费尽了心思。

具体而言，A 国共有 $2^n-1$ 个城市，其中 $1$ 号城市为首都。对于所有的非首都城市 $i$，都有一条**单向**道路从城市 $i$ 出发，到达城市 $\lfloor \frac{i}{2} \rfloor$。为方便起见，称这样的道路为“第一类道路”，称城市 $\lfloor \frac{i}{2} \rfloor$ 为城市 $i$ 的“上级城市”。

除此之外，还有 $m$ 条**单向**道路，设其中第 $i$ 条道路从城市 $u_i$ 出发，到达城市 $v_i$，这样的道路都有一个特殊性质：从城市 $v_i$ 出发，沿着第一类道路不断向“上级城市”走去，最终总能走到城市 $u_i$。称这样的道路为“第二类道路”。

每一条道路都有相应的长度值。由此，对于 A 国的任意两个城市 $x$ 和 $y$，都可以计算出从城市 $x$ 出发，沿道路走到城市 $y$，所经过的道路的长度之和的最小值，将这一数值记为 $dist(x,y)$。但由于 A 国的道路建设存在严重缺陷，从城市 $x$ 出发可能根本到达不了城市 $y$，此时定义 $dist(x,y)=0$。同时一个城市出发到自己是不需要经过任何道路的，因此定义 $dist(x,x)=0$。

现在管理者希望计算出这些 $dist(x,y)$ 的值，以便合理衡量人们贸易往来的便捷程度。但由于 A 国的城市数量太多，将这些值一一列出的工作量太大，因此管理者只希望求出所有 $dist(x,y)$ 值之和，也就是 $\sum_{x=1}^{2^n-1}{\sum_{y=1}^{2^n-1}{dist(x,y)}}$，并希望请你来帮忙。

inputFormat:
输入的第一行包含两个正整数 $n$ 和 $m$。

输入的第二行包含 $2^n-2$ 个正整数，第 $i$ 个数 $a_i$ 表示从城市 $i+1$ 出发, 到达城市 $\lfloor \frac{i+1}{2} \rfloor$ 的“第一类道路”的长度。

接下来的 $m$ 行，每行包含三个正整数 $u,v,w$，描述了一条从城市 $u$ 到城市 $v$ 的“第二类道路”, 其长度为 $w$。

outputFormat: 输出一行一个正整数，表示对应的答案。由于答案可能很大, 你只需要输出模 $998244353$ 意义下的答案即可。

samples:
见附件中的 trade/trade2.in。
见附件中的 trade/trade2.ans。

samples:
见附件中的 trade/trade3.in。
见附件中的 trade/trade3.ans。

samples:
见附件中的 trade/trade4.in。
见附件中的 trade/trade4.ans。


title: [湖北省选模拟 2023] 棋圣 / alphago

description:
小 K 是一名棋手，厌倦了传统围棋之后，他发明了一种新式围棋。

新式围棋是一种单人游戏。这个游戏的棋盘是一张包含 $n$ 个顶点，$m$ 条边的无向连通图，并且不存在重边和自环。同时，每条边有一个权值，第 $i$ 条边的权值为 $w_i$。

游戏开始时，每个顶点上可能有一颗黑棋或者一颗白棋，或者什么也没有。**至少有一个顶点上没有棋子。** 接下来，玩家需要进行若干次操作。每次的操作形式如下：

首先，选定一个上面没有棋子的顶点 $u$。可以说明，在题目数据范围下，一定存在这样的顶点。

接下来，对于每一颗棋子，若它位于顶点 $v$，则玩家需任选一条从 $v$ 到 $u$ 的**简单路径**，并将这颗棋子沿着这条简单路径移动一步。形式化地，一条简单路径为一个顶点序列 $\{p_1,p_2 \ldots p_k\}$，满足 $p_1 = v$，$p_k = u$ ，$p_1,p_2 \ldots p_k$ **互不相同**，且 $p_i$ 和 $p_{i+1}$ 之间存在一条边。在操作之后，这颗棋子将被移动至顶点 $p_2$。

需要注意的是，虽然在游戏开始时每个顶点上至多存在一颗棋子，但在若干次操作之后一个顶点上可能有多个棋子。对于同一个顶点上的不同棋子，一次操作中选取的简单路径可以不同。

玩家可以在进行任意次操作（可以是 $0$ 次）之后进行**点目**，即结算游戏分数。对于每一对颜色不同的棋子，若它们所在的顶点之间由一条权值为 $w$ 的边直接相连，则称它们**围住了这条边**，会使玩家得到 $w$ 的**目数**。而一个玩家所得到的**目数**即所有棋子对产生的**目数**之和。

现小 K 给了你一张游戏开始时的棋盘，请你帮他求出在这张棋盘上最多可能得到的**目数**。

inputFormat:
输入共 $m+k+1$ 行。

第一行三个整数 $n,m,k$，分别表示点和边的数量，以及棋子的数量。

接下来 $k$ 行，每行两个整数 $x,c$，表示顶点 $x$ 上有一颗颜色为 $c$ 的棋子。其中 $c=0$ 表示一颗黑棋，$c=1$ 表示一颗白棋。

接下来 $m$ 行每行三个整数 $u,v,w$，表示图中有一条连接 $u$ 和 $v$ 的权值为 $w$ 的边。

outputFormat: 输出一行一个整数，为所求答案。

samples: 见选手目录下的 alphago/alphago3.in 与 alphago/alphago3.ans。

samples: 见选手目录下的 alphago/alphago4.in 与 alphago/alphago4.ans。

samples: 见选手目录下的 alphago/alphago5.in 与 alphago/alphago5.ans。

hint:
### 样例 1 解释

对于第一组样例，可以选定顶点 $3$，然后将 $1$ 号点上的黑棋移动到顶点 $2$，将 $2$ 号点的黑棋移动到顶点 $3$，这样两颗棋子所在的顶点之间由一条边权为 $2$ 的边连接，产生的目数为 $2$。

### 子任务

对于所有测试数据，保证  $3 \leq n \leq 100$，$n-1 \leq m \leq \frac{n(n-1)}{2}$，$1 \leq k \leq n-1$，$0 \leq w_i \leq 10^5$。

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


title: ZHY 的表示法

description: ZHY 称一个正整数 $x$ 是**可被表示的**，当且仅当存在一个实数 $y$，满足 $\lfloor \frac y {x_1} \rfloor+\lfloor \frac y {x_2} \rfloor+\cdots + \lfloor \frac y {x_n} \rfloor=x$。现在，ZHY 想知道区间 $[l,r]$ 中有多少个正整数是可被表示的。

inputFormat:
第一行三个正整数 $n,l,r$。

第二行 $n$ 个正整数 $x_1,x_2,\cdots,x_n$。

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

hint:
**样例解释**

当 $x=5$ 时，取 $y=6$ 成立。
当 $x=6$ 时，取 $y=8$ 成立。
当 $x=7$ 时，取 $y=9$ 成立。
当 $x=8$ 时，取 $y=10$ 成立。
当 $x=10$ 时，取 $y=12$ 成立。

故 $5,6,7,8,10$ 是可被表示的，可以证明，对于任意实数 $y$，$\lfloor \frac y {2} \rfloor+\lfloor \frac y {3} \rfloor\ne 9$。故答案为 $5$。

----

**数据范围**

对于 $30\%$ 的数据，$l \le r \le 10^5$。

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

对于 $100\%$ 的数据，$1\le n \le 25$，$1 \le l \le r \le 10^9$，$1 \le x_1,x_2,\cdots,x_n \le 10^9$。


title: 「SFCOI-3」进行一个魔的除 I

background:
终于，勇士打败了魔王，他把走投无路的魔王困在了一个房间里。

魔王拥有在黑暗中随意穿行的能力，所以勇士只有把房间里所有的灯全部打开，才能找到魔王，最终彻底消灭他。

description:
房间中共有 $n$ 盏灯，初始状态可以用 $a_1\dots a_n$ 表示，其中 $\tt 0$ 表示这盏灯初始是关闭的，$\tt 1$ 表示这盏灯初始是打开的。

从第一天早晨开始，魔王与勇士轮流行动：

- 每天早晨，魔王可以选择 **连续的** 两盏灯，将它们的状态全部设定为 $\tt 0$；
- 每天晚上，勇士可以选择 **任意的** 至多三盏灯，将它们的状态全部设定为 $\tt 1$。

每次行动时选择的灯在设定前的状态任意。

假设双方均采用最优策略，不会进行任何不利于自己的行动。勇士想知道，**最少** 需要多少天（也即，他最少需要多少次操作）才能将所有灯状态设定为 $\tt 1$——这样，他才能抓到可恶的魔王，迎娶美丽的公主。

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

对于每组数据：

+ 第一行一个整数 $n$，表示灯的总数。
+ 第二行共 $n$ 个数，依次表示 $a_1\dots a_n$。

outputFormat:
对于每组数据，一行一个整数，代表勇士抓到魔王所需要的最少天数。

特别地，如果勇士不需要任何操作，输出 $0$ 即可。

hint:
### 样例解释 1

+ 第一天早晨，魔王关闭第 $1{,}2$ 两盏灯；
+ 第一天晚上，勇士打开 $1{,}2{,}4$ 三盏灯。

### 样例解释 2

+ 第一天早晨，魔王关闭第 $4{,}5$ 两盏灯；
+ 第一天晚上，勇士打开 $2{,}3{,}4$ 三盏灯。
+ 第二天早晨，魔王关闭第 $1{,}2$ 两盏灯；
+ 第二天晚上，勇士打开 $1{,}2{,}5$ 三盏灯。

### 数据规模与约定

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

- Subtask 0（10 points）：$n \leq 10$，$T \leq 2046$。
- Subtask 1（30 points）：$ n \leq 2000$。
- Subtask 2（10 points）：初始所有灯都是关闭的。
- Subtask 3（20 points）：数据随机生成。
- Subtask 4（30 points）：无特殊限制。

对于所有数据，$1 \leq T \leq 10^6$，$1 \leq n \leq 10^6$，$1 \leq \sum n \leq 3 \times 10^6$。


title: 『XYGOI round1』一些数

background:
MX 在研究排列所具有的性质。这一天，她拿出了 $n$ 张卡片排成一排，想要在上面填数以写成一个 $1\sim n$ 的排列。

Piggy 趁 MX 不注意，偷偷在一些卡片上写了数。

description:
MX 很快发现了这一切。不过她并不生气，而是考虑一个有趣的问题：如果我在上面填一些数，让它依然构成一个排列，且它的最长上升子序列长度为 $n-1$，MX 有多少种填数方法呢？

Piggy 比较良心。他没有在不同的位置上填相同的数。

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

第一行一个整数 $T$ 代表数据组数。
对于每组数据：
- 第一行两个整数 $n,q$ 代表卡牌个数和 Piggy 已经填上了多少个数。
- 第二行 $2q$ 个整数，第 $2i-1,2i$ 个整数 $(x,y)$ 代表第 $x$ 个数被 Piggy 填成了 $y$。

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


title: [Ynoi1999] SMV CC-64“蝰蛇”

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:
Idea：s_r_f，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足：

$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: 歌姬

background:
> 你如此一来就满足了吗？
>
> 没有想过去实现它吗?
>
> 为你而设的 为你而设的
>
> 可怜的制度化作温柔的义务

description:
现在 \*26 的头脑中想着 $n$ 件事情，它们形成一棵树．事情有现实和妄想两种状态．初始时所有事情都是妄想．不妨将事情 $1$ 假设成头脑中这棵树的根．那么一个事情 $u$ 的深度指从事情 $1$ 到事情 $u$ 的简单路径上的事情数（包含端点）．

我们称一个事情的集合 $S$ 为现实联通体，当其满足对于树上任意两个现实事情，其在树上简单路径（包括端点）中的事情都属于 $S$．极小现实连通体，即包含事情数最少的现实连通体．

随着时间推移，事情的状态可能发生一些变动．下面 \*26 和您提及了 $m$ 次事情的变动．变动分为以下两种不同的情况：

1. `Real u` 第 $u$ 件事情变成现实．
2. `Want u` 第 $u$ 件事情变成妄想．

每次变动后，\*26 会向您询问：目前至少还需要额外让几个事情变成妄想，才能使最小现实联通体中深度最小的事情的位置发生改变，或使当前头脑中不存在现实事情．

inputFormat:
第一行是两个整数 $n, m$ 表示事情个数和变动个数．

接下来 $n - 1$ 行每行两个整数表示树上的一条边．

接下来 $m$ 行形如：`Real u` 或 `Want u`．表示一次思考．其中 $1\le u\le n$．

outputFormat: 共 $m$ 行，每行一个整数，表示第 $i$ 次变动后，您向 \*26 提供的答案．

samples:
7 8
1 2
1 5
2 3
2 4
5 6
5 7
Real 3
Real 4
Real 6
Real 7
Want 7
Real 2
Real 5
Want 3

hint:
### 样例 #1 说明
举例最后一次变动结束后的情况．

此时树上除了事情 $1,3,7$ 是妄想，其余是现实．那么此时的最小现实联通体就是 $\{1,2,4,5,6\}$．

$\{2,4,5,6\}$ 不是最小现实连通体，因为存在两个现实事件如 $2,6$，其简单路径经过 $1$，而 $1$ 不在 $\{2,4,5,6\}$ 这个集合里；$\{1,2,3,4,5,6\}$ 同样不是最小现实联通体，因为存在一个现实联通体 $\{1,2,4,5,6\}$ 的大小小于它．

当我们令事情 $2,4$ 变成妄想后，现实事情仅剩下 $5,6$，这时最小现实连通体为 $\{5,6\}$．其中深度最小的事情由原来的 $1$ 变成了现在的 $5$．可以证明这个策略是最优策略之一．

### 数据点约束
|数据点编号|数据范围|
|:-:|:-:|
|$1,2$|$1\le n,m \le 20$|
|$3,4,5$|$1\le n,m \le 300$|
|$6,7,8$|$1\le n,m \le 3000$|
|$9,10,11,12$|$1\le n, m \le 39393$|
|$13 \sim 20$|$1\le n, m \le 2 \times 10^5$|

对于所有数据，保证在任意一次操作时，变动之前和变动之后事情的状态不一样．


title: 『STA - R3』Aulvwc

background:
统计学是一门古老而迷人的学科。

传说早在若干年前，一位名为惠普的神灵来到地球，发现了人类——另一种有智慧的物种……

**已加入 Hack 数据，位于 Subtask 5，不计分。**

description:
定义一个序列 $\{a_n\}$ 是分部平均的，当且仅当存在一个 $\{1,2,\cdots,n\}$ 的划分 $S_1,S_2,\cdots,S_k$（其中 $k>1$），满足对于每个整数 $1\le i\le k$，序列 $\{a\}$ 中以 $S_i$ 为下标的元素之平均数都是相等的**整数**。

现在，给定序列 $\{a_n\}$，问它是否是分部平均的。

如果你对于一些定义不很清楚，可以查阅最后的「提示」部分。

inputFormat:
第一行，一个正整数 $q$，表示询问组数。

对于每组询问，第一行一个正整数 $n$，描述序列长度。第二行 $n$ 个整数，表示序列 $\{a_n\}$。

outputFormat: $q$ 行，对于每组询问，如果序列是分部平均的，则输出 `Yes`，否则输出 `No`。

hint:
### 提示
一个集合 $S$ 的划分定义为一组集合 $U_1,U_2,\cdots,U_k$，满足：
- 对于所有 $i\neq j$，有 $U_i\cap U_j=\varnothing$。
- $U_1\cup U_2\cup\cdots\cup U_k=S$。

一个序列 $\{x_n\}$ 的平均数定义为：
$$\bar x=\dfrac{x_1+x_2+\cdots+x_n}{n}=\dfrac 1n\sum_{i=1}^nx_i$$
### 样例解释
第一组数据的一种划分方案：$\{1\},\{2\},\{3\},\{4\},\{5\}$。

第二组数据的一种划分方案：$\{1,5\},\{2,4\},\{3\}$。

注意：划分方案所提供的集合是下标集合。

### 数据范围

**本题采用捆绑测试及子任务依赖。**
$$
\newcommand{\arraystretch}{1.5}
\begin{array}{c|c|c|c|c}\hline\hline
\textbf{Subtask} & \bm{n}\le & \textbf{分值} & \textbf{特殊性质}&\textbf{依赖子任务}\\\hline
\textsf{1} & 10 & 5 & \\\hline
\textsf{2} & 10^3 & 20 & \sum a_i=0 \\\hline
\textsf{3} & 100 & 25 & & \sf1\\\hline
\textsf{4} & 10^3 & 50 & & \sf1\texttt{,}\ 3\\\hline
\end{array}
$$

对于全部数据，$1\le q\le 10$，$2\le n\le 10^3$，$|a_i|\le 5\times10^3$。


title: 『STA - R3』高维立方体

description:
如下定义斐波那契数列：
$$\operatorname{fib}(n)=\begin{cases}1&n\le 2\\\operatorname{fib}(n-1)+\operatorname{fib}(n-2)&n>2\end{cases}$$

现在我们定义一个函数（注意在 $n<1$ 时这个函数的值是 $0$）：

$$f(n)=\sum_{i=1}^n\operatorname{fib}^2(i)$$

由于求斐波那契数列的前缀和太简单了，你需要求出：
$$\sum_{i=1}^n\operatorname{fib}(i)\cdot(f(i-2)+\operatorname{fib}^2(i)+\operatorname{fib}(i))$$
的值，答案对输入的 $p$ 取模。

注：$\operatorname{fib}^2(x)$ 表示 $\operatorname{fib}(x)$ 的平方。

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

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

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

outputFormat: 对于每组数据，输出一行一个整数，表示答案对 $p$ 取模后的结果。

hint:
样例解释：

对于第一组数据，$1\times(0+1^2+1)+1\times(0+1^2+1)=4$。

对于第二组数据，$1\times(0+1^2+1)+1\times(0+1^2+1)+2\times(1+2^2+2)=18$。
### 数据范围

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

- Subtask 1（5 points）：$n \le 10^7$，$p=10^9+7$。
- Subtask 2（20 points）：$T\le 10^4$，$n \le 10^8$，$p=10^9+7$。
- Subtask 3（5 points）：$p=2$。
- Subtask 4（15 points）：$p\le 5$。
- Subtask 5（30 points）：$T\le 10^4$，$n \le 10^8$。
- Subtask 6（25 points）：无特殊限制。

对于所有数据，$1\le T\le 2\times 10^5$，$1\le n\le 10^{18}$，$2\le p\le 10^9+7$。


title: 「SFCOI-3」进行一个拆的解

background:
**公告：Subtask 0 数据有误，现已更改。**

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

三岁的小明非常不喜欢完整的东西，他甚至连序列都想要拆掉。

description:
给定序列 $a_1\dots a_n$，小明想要把它拆成两个子段 $[1, l][l + 1, n](1 \leq l \lt n)$，即 $a_1\dots a_l$ 和 $a_{l+1}\dots a_n$。

由于小明强迫症很严重，他不希望对于这两个子段，其中一个是另一个的 **子序列**，换句话说，他不希望其中一个子段可以通过删掉若干（可能为 $0$）个元素变成另一个。

在父母出门的时候，小明终于找到了把序列拆开的机会！所以，他想知道，是否存在一种拆解的方式满足：任意一个子段都不是另一个子段的子序列。

inputFormat:
第一行一个整数 $T$，表示小明总共要拆解 $T$ 个序列。接下来 $T$ 行，每行描述一个序列：

+ 每行第一个整数 $n$，表示序列长度；
+ 接下来 $n$ 个整数，依次代表序列中每一个数。

outputFormat:
输出共 $T$ 行。

对于每轮游戏，若存在满足条件的序列，输出 `YES`，否则输出 `NO`。

hint:
### 样例解释

对于第一个序列，所有拆分方式有：

- $\lbrace 1 \rbrace,\lbrace 2,1,2,1 \rbrace$。
- $\lbrace 1,2 \rbrace,\lbrace 1,2,1 \rbrace$。
- $\lbrace 1,2,1 \rbrace,\lbrace 2,1 \rbrace$。
- $\lbrace 1,2,1,2 \rbrace,\lbrace 1 \rbrace$。

从任何地方拆开都是不合法的——较短的那个序列都是另一个序列的子序列。

对于第二个序列，其中一种合理的拆分方式为
$\lbrace 1,2,1,1,2 \rbrace,\lbrace 1,0 \rbrace$。

### 数据规模与约定

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

- Subtask 0（15 points）：$a_i = 0$。
- Subtask 1（15 points）：$n = 10$，保证数据随机生成。
- Subtask 2（30 points）：$n$ 为偶数。
- Subtask 3（40 points）：无特殊限制。

对于所有数据，$1\leq T \leq 10^5$，$2 \leq n \leq 10^5$，$1 \leq \sum n \leq 10^6$，$0 \leq a_i \leq 100$。


title: [CERC2019] ABB

background: **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[ABB](https://contest.felk.cvut.cz/19cerc/solved/abb.pdf)」**

description:
Fernando 受雇于滑铁卢大学，负责完成该大学不久前开始的一个开发项目。在校园外，该大学希望为重要的外国游客和合作者建造具有代表性的平房街。

目前，这条街只建了一部分，它从湖岸开始，一直延伸到森林尽头。Fernando 的任务是通过在森林尽头建造更多的平房来完成这条街。所有现有的平房都坐落在街道的一侧，新的平房应该建在同一侧。这些平房有各种各样的类型，漆成各种各样的颜色。

在 Fernando 看来，整条街的布局有点混乱。他担心增加新平房后，它会看起来更加混乱。所以他想通过为新平房选择合适的颜色来增加一些排列顺序。当项目完成时，平房的整个颜色序列将是对称的，也就是说，从街道的两端观察时，颜色序列是相同的。

在其他问题中，Fernando 想知道，在满足平房颜色限制的情况下，他最少需要用来建造和适当染色才能完成项目的新平房数量。

### 简要题意

求使给定小写字母字符串成为回文串需在字符串末尾加入字母的最少数量。

inputFormat:
第一行包含一个整数 $N\ (1\le N\le 4\times 10^5)$，代表街道上现有平房的数量。

第二行包含一个由 $N$ 个小写字母（从 `a` 到 `z`）组成的字符串，代表从湖岸开始的街道现有的平房颜色顺序，其中不同的字母表示不同的颜色。

outputFormat: 输出一个整数，代表满足 Fernando 要求的新平房的最少数量。


title: [CERC2019] Be Geeks!

background: **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Be Geeks!](https://contest.felk.cvut.cz/19cerc/solved/begeeks.pdf)」**

description:
音乐乐队 Be Geeks! 的名字并非偶然，因为所有成员都是真正的数学怪才。除此之外，他们喜欢研究数列的各种性质。下面是他们感兴趣的一个例子：
- 设 $A$ 是一个非空正整数序列，$A=(a_1, a_2, \dots, a_N)$。
- $G(i, j)=\gcd (a_i, a_{i+1}, \dots, a_j)$，其中 $1\le i\le j\le N$。
- $M(i, j)=\max (a_i, a_{i+1}, \dots, a_j)$，其中 $1\le i\le j\le N$。
- $P(i, j)=G(i, j)\times M(i, j)$，其中 $1\le i\le j\le N$。
- $F(A)=\sum P(i, j)[1\le i\le j\le N]$。

给出一个序列 $A$，你需要求出 $F(A)\bmod 1\,000\,000\,007$ 的值。

inputFormat:
第一行包含一个整数 $N\ (1\le N\le 2\times 10^5)$，代表序列 $A$ 的长度。

第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N\ (1\le a_i\le 10^9)$，代表序列 $A$。


title: [CERC2019] Bob in Wonderland

background: **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Bob in Wonderland](https://contest.felk.cvut.cz/19cerc/solved/bob.pdf)」**

description:
众所周知，链条是由相连的环组成的。通常，所有环都具有相同的形状和大小。Bob 是一名铁匠学徒，他正在制作自己的第一条铱链。他遵循传统的链条制作通则。上面写着：
- 如果没有链条，制作一个环，它将成为你链条的一部分。
- 如果有一条链，制作一个环，并将其连接到你已有的链中的另一个环上。

Bob 做了第一个环。然后，每次他制作另一个环时，他都会将其连接到链条上的其他环上，就像通则告诉他的那样。

当他完成时，他意识到他创造的物体根本不像一条普通的链。为了把链条拉直，他反复地拎起可能是链条两端的两个链环，并试图把它们尽可能地拉开。但在不同的地方，还有更多的“链条”从拉直的部分垂下来。

很明显，Bob 的工作还没有完成，他决定把他制作的物体称为未完成的链条。经过更多的思考，Bob 得出了一个结论，他必须更谨慎地断开一些环，并将它们重新连接到未完成的链条的其余部分，以获得他想要制作的直链。在直链中，每个环最多连接两个其他环，并且直链不能在不断开链环的情况下分离成更多的部分。

Bob 现在更加小心了，将用简单的步骤取得进展。在一个步骤中，他将选择一个环 A，连接到未完成链中的另一个环 B。然后，他会断开 A，将其与 B 分开，并将 A 重新连接到未完成的链条中的另一个环 C。如果最初连接到 A 的环不是 B，Bob 将在整个步骤中保持它们连接着 A。

Bob 获得直链所需执行的最小步骤数是多少？

inputFormat:
第一行包含一个整数 $N\ (1\le N\le 3\times 10^5)$，代表未完成的链条中的环数。所有环标号为 $1, 2, \dots, N$。

接下来 $N-1$ 行，每行包含两个整数，代表未完成链条中两个相连环的编号，按任意顺序给出。未完成的链条保证只有一个连体（即任意两个环之间都存在路径使他们相连）。

outputFormat: 输出一个整数，代表将 Bob 未完成的链条转化为直链的最少步骤数。


title: [CERC2019] Crimson Sexy Jalapeños（征集交互库/SPJ）

background: **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Crimson Sexy Jalapeños](https://contest.felk.cvut.cz/19cerc/solved/crimson.pdf)」**

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

受污染的巧克力游戏的核心是一个经典的巧克力块，由平行于巧克力块两侧的矩形凹槽网格划分成小方块。一些小方块被极度苦涩的物质污染，（几乎）无法消化。

这场比赛由两名选手轮流进行。在一个有效的动作中，一名玩家必须吃掉巧克力块的一部分。允许将当前的巧克力块沿着其中一个凹槽分成两个较小的巧克力块，然后只吃其中一个。玩家如果吃掉了至少含有一个受污染方块的巧克力块，则输掉游戏。

所有被污染的方块的位置在游戏开始时都是已知的。所有其他的方块都可以安全食用。每个玩家都会尽量避免吃一个含有一个或多个受污染方块的巧克力块，因为当这种情况发生时，玩家会不由自主地做出他们个人最厌恶的鬼脸，这会给其他玩家和其他观看比赛的人带来极大的乐趣。

在这个问题上，你要写一个程序来玩“受污染的巧克力”游戏。我们忽略了代码中模拟玩家扮鬼脸和吃巧克力的部分，而只关注获胜的动作。

inputFormat:
输入的第一行包含整数 $R, C, K\ (1\le R, C\le 10^4;\ 1\le K\le 100)$。$R$ 是行数，$C$ 是列数，$K$ 是巧克力块中被污染的方块数。

接下来 $K$ 行，每行包含两个整数 $A$ 和 $B\ (1\le A\le R, 1\le B\le C)$，代表受污染方块的坐标。左上角正方形的坐标为 $(1, 1)$。

其余的输入取决于你的输出。对于你的每一个有效动作，交互库都会给出一行输入，包含对手的有效动作描述或表示对手输掉比赛的字符串 `yuck!`。在后一种情况下，你的程序应该结束。

outputFormat:
读入巧克力棒的描述后，你可以决定是否要开始游戏。如果你想选择后手，输出一行，包含字符串 `pass`。这个特殊的字符串只能出现在输出的第一行。

在选择先后手后，对于你的每个动作，输出一行，包含有效动作的描述。如果你的程序输出了一行非有效动作的任何其他内容，那么你的程序将会判为 `Wrong Answer`。

在每次输出动作的描述后，清空缓冲区。例如，你可以使用：
- 对于 $\text{C++}$：`fflush(stdout)` 或 `cout.flush()`；
- 对于 $\text{Java}$：`System.out.flush()`；
- 对于 $\text{Python}$：`stdout.flush()`。

samples:
3 5 1
2 3

left 1

left 1

right 1

yuck!

hint:
### 样例格式说明

为了方便说明程序和交互库的交互顺序，样例格式填充了空行。请注意实际交互过程中不会输出空行。

### 样例 $1$ 解释
![](https://cdn.luogu.com.cn/upload/image_hosting/t8vf1vc8.png)


title: [CERC2019] Deep800080

background: **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Deep800080](https://contest.felk.cvut.cz/19cerc/solved/deep.pdf)」**

description:
Deep800080 的船主 Ian 今晚将在湖上烧烤。有一个狭窄的直码头，从岸边一直延伸到湖中。Ian 认为在码头的某个地点做烧烤是个好主意。

他想测试一下他的新型特制烧烤炭。当它燃烧时，会产生一种独特的浓紫色烟雾，弥漫在水面上。烟雾保证会在烧烤场周围形成一个完美的圆圈。最终，云层将达到一定的最大半径，并在晚上剩下的时间里保持不变，直到更晚的时候消散。

湖中离码头不同距离的位置停泊着多艘船只。Ian 想把烧烤的事通知他们的船员。由于有点懒，他希望烤肉烟雾能帮他做这项工作。Ian 希望，当云层到达一艘船时，船员们能闻到烟雾，这样他们就能立即知道附近有烧烤。

Ian 想最大化被警报的船员数量，因此他想在码头上选择一个可以最大化紫色烟雾到达的船只数量的地点放烧烤架。

你可以认为湖面上的船只已经牢牢地固定住了，即当烟雾层在湖面上时它们不会移动。此外，一旦选择了烧烤地点，其位置在整个活动中保持不变。

inputFormat:
第一行包含四个整数 $N, R, A, B\ (0\le N\le 3\times 10^5; 1\le R\le 10^6)$。$N$ 是湖面上的船只数量，$R$ 是紫色烧烤烟雾的最大半径。你可以认为桥墩又窄又长，因此可以将其视为穿过坐标为 $(0, 0)$ 和 $(A, B)$ 的两个不同点的直线。

接下来 $N$ 行，每行都包含两个整数 $X$ 和 $Y$，用于描述湖上一艘船的坐标。没有两艘船的坐标相同。

所有坐标都是平面中常见的 Cartesian 坐标，它们的绝对值最多为 $10^6$。

outputFormat:
输出一个整数，代表紫色烧烤烟雾可以到达的船只的最大数量。

如果船的位置在烟雾形成的圆圈内，包括其边界，则视为已到达。你可以认为将烟雾的最大半径增加 $10^{-3}$ 不会改变解决方案。


title: [CERC2019] Zeldain Garden

background: **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Zeldain Garden](https://contest.felk.cvut.cz/19cerc/solved/garden.pdf)」**

description:
Boris 是 Rock Anywhere Transport（RAT）公司的首席执行官，该公司专门支持音乐产业。特别是，他们为许多流行的摇滚乐队提供折扣运输。这一次，Boris 不得不将大量优质的墨西哥音乐会扬声器从北海港口转移到遥远的内陆首都。由于预计收货量很大，Boris 不得不组织多辆卡车以确保运输顺畅。运送货物通过该国的众多卡车被称为车队。

Boris 希望通过一个车队一次性运输所有货物，一个扬声器都不留下。欧盟的严格规定要求，在大规模运输音频技术设备的情况下，车队中的所有卡车必须携带完全相同数量的设备。

为了满足所有规定，Boris 希望提前做一些计划，尽管他还不知道扬声器的确切数量，这对车队中卡车的数量和容量的选择有很大影响。为了检查各种情况，对于每个可能的容货量，Boris 计算出所谓的“可变性”，即在不违反规定的情况下，可以为该容货量创建的不同车队的数量。如果两个车队由不同数量的卡车组成，那么它们就不同了。

例如，$6$ 个扬声器货物的可变性为 $4$，因为它们可以均匀地分为 $1$、$2$、$3$ 或 $6$ 辆卡车。

### 简要题意

给定 $l,r$，求 $l\sim r$ 中所有数的因数个数之和。

inputFormat: 输入包含一个文本行，包含两个整数 $N, M\ (1\le N\le M\le 10^{12})$，代表扬声器货物的最小和最大数量。

outputFormat: 输出一个整数，代表对于 $N$ 和 $M$ 之间（含）的所有货物量的可变性之和。


title: [CERC2019] Light Emitting Hindenburg

background: **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Light Emitting Hindenburg](https://contest.felk.cvut.cz/19cerc/solved/hindenburg.pdf)」**

description:
Lothar 正在组织他朋友的摇滚乐队的音乐会巡演。巡演将于 11 月举行，每天最多有一场音乐会。这次巡演将非常具有代表性，许多音乐家都愿意参加。巡演中的音乐家人数是严格规定的，不能改变。巡演中的每一场音乐会都必须有所有参加巡演的音乐家参加。

对 Lothar 来说，好消息是，候选音乐家的数量至少与巡演中规定的音乐家数量一样多。坏消息是，一个典型的音乐家整个月都没有空，而且各种音乐家的日程安排也大不相同。

很久以前，Lothar 编写了一个计算机调度系统的核心，现在他正在利用它来组织这次巡演。他反复地、有点随机地选择一组指定数量的音乐家，并让系统计算出一个可接受的巡演时间表。该系统取决于一种非常具体的数据格式。音乐家的时间表和巡演时间表用数字编码表示。11 月的日子是按月份的数字标记的：$1, 2, \dots, 30$。

对于一个给定的音乐家来说，每年 11 月的一天都会被分配一个特定的数字编码。如果音乐家当天空闲，则标签为 $L$ 的一天由整数 $2^{30-L}$ 编码。否则，日期将由 $0$ 编码。音乐家的时间表编码是他或她的所有日期编码的总和。

对于一组给定的音乐家来说，每年 11 月的一天都会被分配一个特定的数字编码。如果该组中的所有音乐家当天都空闲，标签为 $L$ 的一天由整数 $2^{30-L}$ 编码。否则，日期将由 $0$ 编码。组的空闲编码是该组所有日期编码的总和。

出于许多其他微妙的原因，Lothar 认为最好的巡演应该是任意一组音乐家，这组的空闲编码是可能的最大值。

inputFormat:
第一行包含两个整数 $N, K\ (1\le K\le N\le 2\times 10^5)$。$N$ 是可用音乐家的数量，$K$ 是参加巡演的音乐家的规定数量。

第二行包含一个由 $N$ 个正整数组成的序列。序列中的每个整数表示一个音乐家的时间表编码。编码按任意顺序列出。

outputFormat: 输出一个整数，代表 $K$ 个音乐家的空闲编码值总和的最大值。


title: [CERC2019] K==S

background: **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[K==S](https://contest.felk.cvut.cz/19cerc/solved/kequalss.pdf)」**

description:
渐进式硬八度摇滚曲调（所谓的“phorts”）是使用特定的音符创作的。这种摇滚风格只建立在 $13$ 个不同的音符音高上，其他音高（在其他八度中）被认为是过时的音乐基石。每个音符可以是长的，也可以是短的。因此，摇滚中正好有 $26$ 个不同的音符。

你将在你朋友的生日之际创作一首 phort 曲调，并与你的乐队在主要的城市广场上表演。在创作词缀时，你需要避免使用某些音乐短语，这些短语由于大型唱片公司赞助的长期研究而受到版权保护。已经证实，这些短语非常朗朗上口，易于记忆，可以用来将听众下意识地与某个特定的音乐公司联系起来，该公司会在他们的制作中使用这些短语。

曲调是一连串的音符。一个音乐短语也是一个音符序列，如果它的音符形成曲调的连续子序列，则它被认为包含在曲调中，这意味着相同的音符以相同的顺序出现在曲调中。

幸运的是，到目前为止，只有少数禁用短语获得了专利。因此，你可以相对自由地创作自己的曲调。特别是，您对某些长度的可接受的曲调的数量感兴趣。可接受的曲调是指任何不包含禁用短语的曲调。曲调的长度等于它所包含的音符数。

inputFormat:
第一行包含两个整数 $N, Q\ (1\le N\le 10^9, 1\le Q\le 100)$。$N$ 是曲调的长度，$Q$ 是禁用音乐短语的数量。

接下来 $Q$ 行，每行都描述了一个禁用短语。禁用短语的描述以一个表示其长度的正整数 $L$ 开头，后跟一个由 $L$ 个小写英文字母组成的字符串。每个字母代表一个摇滚音符，不同的字母代表不同的音符。

所有禁用短语的长度总和不超过 $100$。

outputFormat: 输出长度为 $N$ 的不同可接受曲调的数量对 $1\,000\,000\,007$ 取模的值。


title: [CERC2019] Ponk Warshall

background: **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Ponk Warshall](https://contest.felk.cvut.cz/19cerc/solved/ponk.pdf)」**

description:
听摇滚乐会改变你的核心 DNA。这一令人震惊和难以置信的事实最近发表在地球上顶级科学期刊之一的《摇滚自然周刊》上。研究的一部分是在摇滚音乐会季前后从志愿者身上采集 DNA 样本。对样品进行处理，并从样品中分离出各种基因。对于每个人，每个基因被分离两次：摇滚季之前的变体和摇滚季之后的变体。这两个变体是配对的，在许多情况下，发现一个变体是该对中另一个变体的某种排列。

研究的下一步是确定排列是如何发生的。普遍的假说认为，排列是由一系列转座组成的，即所谓的交换。交换是指基因中正好有两个核碱基在基因中交换位置的事件（其化学性质尚不完全清楚）。该基因中没有其他核碱基受到交换的影响。两个交换的核碱基的位置可能是完全任意的。

为了预测和观察分子在排列过程中的运动，研究人员需要知道能够在基因中产生特定核碱基排列的理论最小交换次数。我们提醒你，核 DNA 基因是一个由胞嘧啶、鸟嘌呤、腺嘌呤和胸腺嘧啶组成的碱基序列，它们分别编码为 C、G、A 和 T。

### 简要题意

给定两个字符串（字符集只含 `A`、`C`、`G` 或 `T`），求把第一个字符串通过交换两个字母变为第二个字符串的最少交换次数。

inputFormat: 输入包含两行。每行包含一个由 $N\ (1\le N\le 10^6)$ 个大写字母“A”、“C”、“G”或“T”组成的字符串。这两个字符串代表一对特定的基因版本。第一行代表摇滚季之前的基因，第二行代表来自摇滚季之后同一个人的相同基因。在两个字符串中，每个核碱基的出现次数是相同的。

outputFormat: 输出一个整数，代表将第一个基因版本转换为第二个基因版本交换的最小数量。


title: [CERC2019] Saba1000kg

background:
**题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Saba1000kg](https://contest.felk.cvut.cz/19cerc/solved/saba.pdf)」**

翻译有待改进。

description:
维京岩石运动中有许多不同的溪流。古老的冰岛花岗岩、中世纪丹麦尘土飞扬的维京岩石、晚期芬盖尔深绿色岩石、峡湾巨石雪崩岩石和许多其他岩石，所有受欢迎的溪流的完整列表会多次溢出本页。斯堪的纳维亚高等教育部研究了各种流之间相互影响的方式。他们目前正在计划一项大型实验，届时将有一些经过适当选择的志愿者分布在一个由无人居住的小岛组成的群岛上，研究人员希望在相对较长的一段时间内观察他们的岩石风格和偏好的相互影响。

一个岛上的居民总是互相影响。一些成对的岛屿距离足够近，居民可以相互影响，而其他成对岛屿之间的距离可以防止任何直接影响。在后一种情况下，如果有一个或多个其他岛屿有人居住并传递影响，这些岛屿的居民仍然可以相互影响，但只能间接影响。

关于志愿者在各岛屿之间的分配，有几个提案。对于每一种提案，该部都想知道该群岛将形成的独立居民群体的数量。两组岛屿居民，每一组都占据一个或多个岛屿，如果他们不可能相互影响，即使不是以间接的方式，也被视为独立的。

帮助该部评估他们的提案。

inputFormat:
第一行包含三个整数 $N, E, P\ (1\le N\le 10^5, 0\le E\le 10^5, 1\le P\le 10^5)$。

$N$ 是群岛中的岛屿数量，$E$ 是允许直接影响的成对岛屿数量，$P$ 是要评估的提案数量。这些岛被从 $1$ 到 $N$ 标号。

接下来 $E$ 行指定允许直接相互影响的岛对。这些行中的每一行包含两个整数 $A$ 和 $B$，表示两个不同岛的标号。没有一对岛屿出现过一次以上。

接下来 $P$ 行，每行都描述了一个提案。每行以该提案下居住的岛屿数量 $M\ (1\le M\le N)$ 开始，然后包含 $M$ 个居住岛屿的成对不同标号。根据各自的提案，不会有其他岛屿居住。

所有提案的大小之和（所有数字 $M$）不超过 $10^5$。

outputFormat: 对于每个提案，输出一行将在群岛中形成的独立群体的数量。


title: [CERC2019] Screamers in the Storm

background:
**题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Screamers in the Storm](https://contest.felk.cvut.cz/19cerc/solved/screamers.pdf)」**

翻译有待改进。

description:
你可能不知道，你每天在一个城市看到的“普通”城市鸽子的官方名称实际上是“岩鸽”。岩鸽 Rocky Dave 爱上了 Columba Livia，这是一只年轻的雌性岩鸽，她对岩石、鸽子以及与这类事物相关的一切都有着浓厚的兴趣。完全巧合的是，在一个阳光明媚的秋日下午，我们在城市郊区发现他们坐在同一栋楼的屋顶上。

为了展示他自信的运动步态，Rocky Dave 决定不飞越屋顶去追求他心爱的对象，而是走向她。屋顶不是现代的平屋顶，而是由斜坡构成的古典屋顶。由于该建筑由更多较小的建筑连接在一起，其平面图有点复杂。因此，Dave 打算向Columba Livia 移动的“直线”只有在从上方观察时才显得笔直。Rocky Dave 可能不得不爬上去，越过山脊，从另一边爬到屋顶山谷，然后再爬上去，以此类推。

我们知道这座建筑的确切平面图，屋顶上斜坡的角度（所有角度都是一样的），以及我们的主人公和女主人公在屋顶上的原始位置。根据这些数据，计算 Rocky Dave 旅程的确切长度，前提是 Columba Livia 在 Rocky Dave 到达之前没有离开她的位置。

如果这条路离开了建筑边界，Dave 的计划是，每当他在屋顶边缘遇到雨水沟时，他都会以相同的高度朝着 Columba Livia 的方向笔直飞行，直到他到达建筑另一侧的雨水沟，在那里他将进一步步行继续他的旅程。

为了使情况变得清楚，我们向您展示了屋顶的几何模型。设 $Z$ 是 $x-y$ 平面上的一个简单多边形。简单多边形是一个多边形，其边界是一条闭合的曲线，它本身不接触或相交。一个可接受的金字塔是一个金字塔，其底部是 $x-y$ 平面中的轴平行正方形，其顶点（顶部顶点）位于底部中心的正上方。棱锥体的高度正好是其基边长度的一半。此外，一个可接受的金字塔的底部没有一部分位于 $Z$ 之外。注意，一个可以接受的金字塔可能正式地具有零底部边长和零高度，然后它由一个节点组成，该节点也是它的顶点。

$x-y$ 平面中或上方的点 $X$ 是 $Z$ 的顶点，当且仅当它是可接受金字塔的顶点，并且 $X$ 正上方没有点是可接受棱锥的顶点。

inputFormat:
第一行包含五个整数。第一个整数 $N\ (4\le N\le 400)$，是由建筑平面图的边缘在 $x-y$ 平面上形成的多边形的角点数量。接下来两个整数是 Rocky Dave 的 $x$ 和 $y$ 坐标，最后两个整数是 Columba Livia 的 $x$ 坐标和 $y$ 坐标。

接下来 $N$ 行，每行包含多边形一个角点的 $x$ 和 $y$ 坐标。这些点按逆时针顺序列出。建筑物的每一边都与其中一条轴线平行。

两只鸽子都不在给定的多边形之外。所有输入坐标都是绝对值最多为 $10^5$ 的整数。

outputFormat: 输出 Rocky Dave 旅程的长度。答案的绝对或相对误差必须小于 $10^{−7}$。


title: [CERC2019] The Bugs

background: **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[The Bugs](https://contest.felk.cvut.cz/19cerc/solved/thebugs.pdf)」**

description:
一艘涂有明亮塑料柠檬色的潜艇正在调查海洋深度，并测量水中塑料 yocto 颗粒的浓度。每个测量值（由于巧妙地选择了单位）都是一个正整数。

测量系统是最新的，很少测试，容易出错。项目管理层怀疑它充满了漏洞。他们发现自己陷入了困境。Mother Mary 也怀疑里面满是漏洞。大家都喊：救命！

为了发现和修复这些漏洞，他们聚集在一起，决定采用浓度的测量序列，并分析测量序列中出现的所有三元组。

- 三元组是由三个整数组成的序列。
- 每个三元组都与其特征组相关。
- 三元组 $(x, y, z)$ 的特征组是三元组 $(\text{sgn}(y−x) ,\text{sgn}(z−y), \text{sgn}(z−x))$。对于 $x$ 的负值、零值或正值，$\text{sgn}(x)$ 函数的值分别为 $−1$、$0$ 或 $1$，即 $\text{sgn}(x)=\begin{cases}0&x=0\\\dfrac{x}{|x|}&x\ne 0\end{cases}$。
- 三元组 $(x_1, y_1, z_1)$ 小于三元组 $(x_2, y_2, z_2)$，当且仅当三元组 $(x_1-x_2, y_1-y_2, z_1-z_2)$ 中的第一个非零值为负。
- 三元组 $T$ 的标记组是一个最小的三元组，它的值都为正，并且其特征组等于 $T$ 的特征组。

一个被测三元组是作为测量序列的子序列的三元组。也就是说，这个三元组的元素以它们在三元组中出现的相同顺序出现在测量序列中，但在序列中它们不一定相互跟随。

在对它们进行分析之前，被测三元组根据它们的标记组进行分组。管理层希望提前知道所有测量的三元组的标记组的集合。

inputFormat:
第一行包含一个整数 $N\ (3\le N\le 2\times 10^5)$，代表测量序列的长度。

第二行包含 $N$ 个整数 $x_1, x_2, x_N\ (1\le x_i\le 10^9)$，代表测量序列。

outputFormat: 按递增顺序输出所有被测三元组的所有不同标记组，这些标记组可以从给定的测量序列中获得，每行一个。输出标记组时，其连续元素之间不应有空格。


title: ZHY 的集合

background:
## 赛后时限改为 1s。

ZHY 又一次在赛时看错题了。
[](T341514)

description:
对于两个集合大小为 $x$ 的集合 $A,B$，满足 $A\cap B=\varnothing$（空集），ZHY 定义 $f(A,B)$ 如下：

- 设 $C=A\cup B$。将 $C$ 中的元素从小到大排序。

- $f(A,B)=\displaystyle \sum_{i=1}^x C_i$。

现在，ZHY 有 $n$ 个大小为 $m$ 的集合 $S_1,S_2,\cdots,S_n$，他想知道 $\displaystyle \sum_{i=1}^n\sum_{j=i + 1}^n f(S_i,S_j)$ 是多少。

然而，ZHY 并不满足于此。于是他又进行了 $q$ 次修改操作，每次操作会重新给定一个集合。请你在每次修改后都输出一次答案，即 $\displaystyle \sum_{i=1}^n\sum_{j=i + 1}^n f(S_i,S_j)$。保证任意时刻任意一个集合中元素两两不同，保证任意时刻任意两个集合的交为空。

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

第 $2$ 行到第 $n+1$ 行，每行 $m$ 个整数，描述集合 $S_1,S_2,\cdots,S_n$。第 $i+1$ 行的 $m$ 个数为集合 $S_i$ 中的 $m$ 个整数。

随后 $q$ 行，每行第一个整数为 $x$，表示将要修改的集合的编号。随后 $m$ 个数表示新的 $S_x$ 中的 $m$ 个整数。

outputFormat:
第一行一个整数表示初始时的答案。

随后 $q$ 行，每行一个整数表示每次修改后的答案。


title: 『STA - R7』Odtlcsu

description: 给定整数 $x,y$，构造一个长度不超过 $10^6$ 的整数序列使得其和为 $x$、平方和为 $y$。保证有解。

inputFormat: 一行两个整数 $x,y$。

outputFormat:
第一行一个非负整数 $n$ 表示你构造的序列长度。需要满足 $n\le 10^6$。

第二行 $n$ 个整数表示你构造出的序列。如果有多解输出任意一种即可。输出的序列所有元素必须是绝对值不大于 $10^6$ 的整数。

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

数据范围：
- Subtask 1 (10pts)：$y\le 10$。
- Subtask 2 (40pts)：$x=0$。
- Subtask 3 (50pts)：无特殊限制。

对于全部数据，$0\le |x|,y\le10^6$，保证有解。


title: 三色

background: 我的心脏还在跳动着啊。

description: 给定 $n$ 个三元组 $(a_i,b_i,c_i)$。$q$ 次询问，每次给定一个集合 $S$，查询是否存在实数三元组 $(p,q,r)$ 满足：对于所有满足 $pa_i+qb_i+r>0$ 的 $i$，其 $c_i$ 构成的集合恰好为 $S$。

inputFormat:
第一行输入一个整数 $T$，代表数据组数。

对于每组数据，第一行输入三个数 $n,q,k$，其中 $k=|S|$。

接下来 $n$ 行，每行输入三个整数 $a_i,b_i,c_i$。

接下来 $q$ 行，第 $i$ 行输入 $k$ 个整数 $s_{i,1},s_{i,2},\dots,s_{i,k}$，代表第 $i$ 组询问中 $S$ 的元素。保证元素不重复。

outputFormat: 对于每组数据，输出一行一个长为 $q$ 的字符串 $R$，对于第 $i$ 组询问，若答案为存在，则 $R_i$ 为 $\tt 1$，否则为 $\tt 0$。


title: 『STA - R3』大豆

background:
大豆 (Soy / Soybean) 非常有前途。

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

description:
对于一个序列 $\{a\}$，定义其大豆化 (Soybeanization) 序列 $\{b\}$ 由如下操作得到：
1. 初始 $\{b\}$ 和 $\{a\}$ 相等。
2. $n$ 从小到大遍历整个正整数集，对于每个 $n$，进行操作：
   - $i$ 从小到大遍历整个不小于 2 的正整数集，对于每个 $i$，操作 $b_n\gets b_n-b_{\lfloor\frac ni\rfloor}$。
   - 如果 $i>n$，结束过程。

进而，定义一个序列的 $k$-大豆化序列为进行 $k$ 次大豆化操作后得到的序列。

现在给你一个整数序列 $\{t_n\}$，将 $\{t\}$ 复制无穷遍得到序列 $\{a\}$，求 $\{a\}$ 的 $k$-大豆化序列的第 $m$ 项。

序列下标从 1 开始。答案可能很大，对 $23068673$（一个质数）取模。

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

第二行，$n$ 个正整数，描述序列 $\{t\}$。

outputFormat: 一行，表示答案，对 $23068673$ 取模。


title: [JRKSJ R9] 莫队的 1.5 近似构造

background:
> 二维莫队构造可以看作 $i,j$ 之间有权值为 $|l_i-l_j|+|r_i-r_j|$ 的完全图上的 TSP 问题。显然，任何莫队的边权都满足三角不等式。
\
\
>求出最小生成树，然后把所有度数为奇数的点拿出来，对这个导出子图跑最小权匹配得到 $E$，将 $E$ 加到最小生成树上，然后跑欧拉路径即可。
\
\
 注意到 $\text{MST}(S)\le \text{TSP}(S)$，$2E\le \text{TSP}(S)$（$E$ 的 $\text{TSP}$ 方案可以给出两组匹配，考虑其中的较小值）且欧拉路径的边权和不小于欧拉路径给出的方案的权值，就给出了 $\le 1.5\text{TSP}(S)$ 的结果。

description:
给你一个 $1\sim n$ 的排列 $a$ 和 $m$ 个该排列上的区间 $[l_i,r_i]$。

对于一个值域区间 $[L,R]$：
- 称「选取 $i$ 时该值域区间的价值」为 $a_{l_i},a_{l_i+1},\dots,a_{r_i}$ 中有多少个数属于值域区间 $[L,R]$；
- 定义值域区间 $[L,R]$ 的价值为 $\forall i\in[1,m]$，「选取 $i$ 时该值域区间的价值」的最大值。

即，值域区间 $[L,R]$ 的价值为 $\displaystyle\max_{i=1}^m \sum_{j=l_i}^{r_i} [L\le a_j\le R]$。

定义两个区间相交当且仅当至少有一个整数被这两个区间共同包含。请你选出若干个**互不相交**的值域区间，使得它们的价值的乘积最大。将该答案对 $998244353$ 取模后输出。

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

第二行 $n$ 个整数表示 $a_{1\dots n}$。

下面 $m$ 行，每行两个整数 $l_i,r_i$。

outputFormat: 一个整数表示答案。输出答案时对 $998244353$ 取模。


title: [Ynoi Easy Round 2023] TEST_107

description: 给一个长为 $n$ 的序列 $a$，下标为 $1$ 到 $n$，有 $m$ 次查询操作，每次给出一个区间 $[l,r]$，求一个子区间 $[l',r']$，满足 $l\le l'\le r'\le r$，$[l',r']$ 中出现过的值个数比 $[l,r]$ 中出现过的值个数少，且其长度即 $r'-l'+1$ 最大。若不存在这样的子区间，则输出 $0$。

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

之后一行 $n$ 个数依次表示序列 $a$ 中的元素。

之后 $m$ 行，每行两个数 $l,r$ 表示一次查询，只需输出该子区间的长度，即 $r'-l'+1$。

outputFormat: 对于每次查询，输出一行一个数表示答案。

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

对于 $20\%$ 的数据，满足 $n,m\le100$。

对于 $40\%$ 的数据，满足 $n,m\le1000$。

对于另外 $20\%$ 的数据，满足 $a_i\le 10$。

对于 $100\%$ 的数据，满足 $1\le n,m,a_i\le 2\times 10^6$。


title: [Ynoi Easy Round 2024] TEST_130

description:
给定一棵 $n$ 个节点的有根树，定义 $N(w,d)$（$w$ 为树的顶点，$d$ 为非负整数） 为以 $w$ 为根的子树中，到 $w$ 距离不超过 $d$ 的点构成的集合。

共 $m$ 次询问，每次给出 $w,d$ 查询 $\{N(w',d')\mid N(w',d')\subseteq N(w,d)\}$ 的大小。

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

第二行 $n-1$ 个数 $f_2,\dots,f_n$ ，其中 $f_i$ 表示编号 $i$ 的结点的父亲。

接下来 $m$ 行，每行两个数 $w,d$ 表示一次询问。

outputFormat: 输出 $m$ 行，依次表示每次查询的答案。

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

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^6$，$1\le f_i<i$，$1\le w\le n$，$0\le d\le n-1$。

对于 $25\%$ 的数据，满足 $n,m\le 100$。

对于另外 $25\%$ 的数据，满足 $n,m\le 5000$。

对于另外 $25\%$ 的数据，满足 $n,m\le 2\times 10^5$。

对于另外 $25\%$ 的数据，无特殊限制。


title: 「RiOI-03」Just a Q. (Hard ver.)

background:
「Yes, I am Q.」

面前的小 R 莞尔一笑。

+ 保证本题的任何合理的部分分或正解的 std + spj 均可以在当前数据下，$900$ ms 的时间限制、$32$ MB 的空间限制内正确运行并获得 AC 状态。
+ 本题不添加仅为无意义地卡满 spj 运行时间的 hack 数据。

**请注意，本题只有约束范围与普通版不同，且两个版本的约束范围并不完全重叠。**

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

小 R 有一个变量 $Q$。$Q$ 初始为 $0$。

小 R 有 $n$ 个隐藏的整数 $q_1 \dots q_n$，满足 $1 \leq \lvert q_i \rvert \leq V$，且有且仅有一个 $i$ 满足 $q_i \lt 0$，而面前的你，需要得出这个满足 $q_i \lt 0$ 的下标 $i$。

小 R 承诺不会让你以仅仅 $\frac{1}{n}$ 的几率盲猜，所以她可以允许你进行最多 $k$ 次询问。每次询问，你可以向小 R 给出**可重**正整数集合 $S$ 满足 $0 \leq \lvert S \rvert \leq S_{\max}$ 且 $\forall i \in S, i \leq n$，她会计算 $M = \prod\limits_{i\in S}q_i$，然后让 $Q \leftarrow Q + M$。特殊地，若 $S$ 为空集，则 $M = 1$。

一次询问后，小 R 会向你给出此时的 $\text{sgn}(Q)$（为 `+`，`-` 或 `0`），表示 $Q$ 的符号。具体地，若 $Q \gt 0$，小 R 返回 `+`；若 $Q \lt 0$，小 R 返回 `-`；否则返回 `0`。

请你在不超过 $k$ 次询问后，找到那个满足 $q_i \lt 0$ 的下标 $i$。

**保证对于所有数据，满足 $q_i \lt 0$ 的下标 $i$ 是在 $[1, n]$ 内均匀随机选取的。请注意报告下标属于一次询问。**

inputFormat:
### 交互格式

第一行，输入三个正整数 $n, k, S_{\max}$。

在此之后，你应当进行若干次询问。

对于你的每组询问，输出 $?\ m\ s_1\ s_2 \dots s_m$，表示给出一个**可重**正整数集合 $S$，其大小为 $m$，你需要保证 $0 \leq m \leq S_{\max}$。此外，同时应有 $1 \leq s_i \leq n$，描述这个集合里的元素编号。

如果你已经得到答案，请输出 $!\ i$，满足 $1 \leq i \leq n$，代表你得到 $q_i \lt 0$，在这之后你应当立即退出本轮交互。

每次你输出之后，请**刷新缓冲区**。

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

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

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

每次询问并刷新缓冲区后，你将从标准输入中输入一个字符，字符为 `+`，`-` 或 `0`，表示当前 $Q$ 的符号 $\text{sgn}(Q)$。

### 输入格式

本题有多组数据。

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

对于每一组数据，请按照 **【交互格式】** 进行交互。当你报告下标后：

+ 如果你给出的下标正确：
	+ 如果这是最后一组数据，交互库退出并返回 Accepted；
	+ 如果这不是最后一组数据，你应当接着读入 $n, k, S_{\max}$ 以进行下一组数据的交互。
+ 否则，下标错误，交互库会立刻终止，返回 Unaccepted。

outputFormat: 见 **【输入格式】**。


title: [语言月赛 202307] 数字判断

background: 请注意，本题只有通过全部测试点才能获得分数。

description:
给定三个整数 $a, b, c$，请你判断它们是否满足如下**所有**条件：

1. $a + b + c \leq 100$。
2. $b$ 是 $5$ 的倍数。
3. $c$ 是 $7$ 的倍数。
3. $a - b > b - c$。

如果上述条件均满足，请输出 $\texttt{Yes}$，否则输出 $\texttt{No}$。

inputFormat: 输入只有一行三个整数，依次表示 $a,b,c$。

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

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

**本题采用捆绑测试，只有通过全部测试点才能获得分数**。

对全部的测试点，保证 $0 \leq a, b, c < 2^{31}$。


title: ZHY 的生成树

description: ZHY 有一个 $n$ 个点的完全图，点 $u$ 与点 $v$ 的距离为 $\gcd(u,v)$，求这个完全图的最大生成树的边权之和。

inputFormat: 一个正整数 $n$。

outputFormat: 一个整数，表示这个最大生成树的边权之和。

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

$\text{Subtask}$ $0\kern{3pt}$(10pts)：$n\le 5$。

$\text{Subtask}$ $1\kern{3pt}$(20pts)：$n\le 1000$。

$\text{Subtask}$ $2\kern{3pt}$(30pts)：$n\le 10^{6}$。

$\text{Subtask}$ $3\kern{3pt}$(40pts)：$n\le 10^{7}$。

对于所有测试数据，$1\le n \le 10^{7}$。


title: [yLOI2022] 长安幻世绘

background:
> 长安广月晴，留身影，琵琶行，酒客半醒。
> 问你看不清，朱纱帐，翠丝绦，飞天降临。
> 美人腰肢半倾璎珞脆，纤手独举琵琶跪，眸眼还生魅。
> 麝香抹唇酒更醉，醉灯彩越乱越美。

——银临《长安幻世绘》

description:
共有 $n$ 个彩灯从左到右排成一排，从左到右用 $1$  到 $n$ 编号，第 $i$ 个彩灯的亮度是 $a_i$。对 $1 \leq i < n$，我们说 $i$ 号彩灯和 $i + 1$ 号彩灯是相邻的。

我们保证这 $n$ 盏灯的亮度**互不相同**。

一组彩灯的**和谐度**定义为这组彩灯中亮度最大和最小的两盏彩灯的亮度之差。

扶苏想从这 $n$ 个彩灯中选出 $m$ 个**互不相邻**的彩灯作为一组，她希望这组彩灯的和谐度**尽可能小**。请你帮她求出这个最小值。

形式化地，你需要在元素互不相同的数列 $a$ 中选出一个长度为 $m$ 的元素互不相邻的子列，使得子列的极差最小。

inputFormat:
第一行是两个整数，依次表示彩灯的个数 $n$ 和挑出彩灯的个数 $m$。
第二行有 $n$ 个整数，第 $i$ 个整数表示彩灯 $i$ 的亮度 $a_i$。

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

samples:
见附加文件中的 D3.in
见附加文件中的 D3.ans

hint:
### 样例 1 解释

只能选择第 $1, 3, 5$ 个彩灯。因为其他的选法都会导致有灯相邻。

### 样例 2 解释

可以选择第 $2, 4, 6$ 个彩灯，彩灯的亮度是 $7, 3, 6$，其极差是 $4$。

### 数据规模与约定

- 对 $12\%$ 的数据，保证 $n \leq 6$。
- 对 $36\%$ 的数据，保证 $n \leq 100$。
- 另有 $4\%$ 的数据，保证 $m = \lceil\frac{n}{2}\rceil$。
- 另有 $12\%$ 的数据，保证 $a_i$ 单调递增。
- 对 $76\%$ 的数据，保证 $n \leq 10^3$。
- 对 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq \lceil\frac{n}{2}\rceil$，$1 \leq a_i \leq 10^9$，$a_i$ 互不相同。


title: 『MGOI』Simple Round I | D. 魔法环

background:
> 最好的武器不一定最适合，最适合的武器才最好。——
殿堂魔法士 W

description:
小 M 面临着激发自己魂器——魔法环的任务。

魔法环上有 $n$ 个节点，每个节点上都有一个魔法精灵，每个魔法精灵都有一个固定的**魔供值**，这些魔供值形成一个 $0 \sim n-1$ 的排列。

小 M 可以选择激活或不激活一个魔法精灵，但为了激发魔法环，必须**至少**激活 $k(\ge 2)$ 个魔法精灵。

每个魔法精灵无论是否激活都会产生**附魔值**：

- 对于一个被激活的魔法精灵，它产生的附魔值为它的魔供值的**平方**。
- 对于一个未被激活的魔法精灵，它会在环上朝左右看，分别看向两边最近的被激活的魔法精灵。它会选择其中魔供值较大的一个作为「目标精灵」，产生的附魔值为这个「目标精灵」的魔供值与**看向这个「目标精灵」时视线经过的距离**的**乘积**。

作为新手，小 M 希望在激活魔法环的前提下，使得所有魔法精灵的附魔值之和最小，从而更好地控制魔法环的能量。

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

第二行 $n$ 个整数，表示每个节点上魔法精灵的魔供值。

outputFormat: 一行一个整数，表示最小附魔值之和。