title: 「DTOI-2」星之河

background: > 星稀河影转，霜重月华孤。

description:
星之统治者有一个星盘，其可以被抽象为一棵根节点为 $1$ 的树。树上每个节点 $i$ 有一颗红星、一颗蓝星，亮度分别记为 $\text{Red}_i,\text{Blue}_i$。

现在，星之统治者想要知道，对于每个节点 $x$，其子树内（不包括该节点）有多少节点满足：其红星亮度小于等于 $x$ 的红星亮度，且其蓝星亮度小于等于 $x$ 的蓝星亮度。

你需要按编号顺序依次输出每个节点的答案。为减少输出量，**如果答案为 $0$ 则不必输出。**

inputFormat:
第一行两个整数分别表示 $n$。

接下来 $n-1$ 行每行两个正整数 $u,v$，表示存在 $(u,v)$ 这条树边。

接下来 $n$ 行每行两个整数分别表示 $\text{Red}_i, \text{Blue}_i$。

outputFormat: 每个答案非 $0$ 的节点一行，每行一个整数表示答案。


title: 「TFOI R1」Unknown Graph

type: P

background:
小 A 飘到了一个岛屿群里，这些岛屿都有单向桥相连接，没有两座桥连接的起始岛屿和终止岛屿都相同，更不会有桥连接一个岛屿。

但这里全是迷雾，小 A 在一个岛上只能看到这个岛与多少座桥相连。

小 A 想要知道整个岛屿群的形态，但是他并不会，所以找到了你。

如果有多种情况，你只需要告诉小 A 任意一种就行。

description:
有一张 $n$ 个节点的**无重边无自环的有向图**（可以不连通），每个节点的编号为 $1 \sim n$，你知道每个节点的入度和出度。

另外还有 $m$ 条限制，每条限制给定两个点 $x_{i}$ 和 $y_{i}$，表示图中不存在有向边 $(x_{i}, y_{i})$，请你求出一种满足要求的图的形态。

若有多种情况，输出任意一种即可，保证有解。

inputFormat:
第一行一个正整数 $n$ 表示节点数量。

第二行 $n$ 个整数 $a_{i}$，表示编号为 $i$ 的节点的入度为 $a_{i}$。

第三行 $n$ 个整数 $b_{i}$，表示编号为 $i$ 的节点的出度为 $b_{i}$。

第四行一个整数 $m$，表示限制个数。

对于接下来的 $m$ 行，每行两个正整数 $x_{i}, y_{i}$ 表示一组限制。

outputFormat:
第一行一个正整数 $k$ 表示满足限制的图有多少条边。

接下来 $k$ 行，每行两个正整数 $u_{i}$ 和 $v_{i}$ 表示编号为 $u_{i}$ 的结点和编号为 $v_{i}$ 的结点之间有一条有向边。

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

- Subtask 1（10 points）：$n \leqslant 10$。
- Subtask 2（10 points）：$n = 10^3$，$a_{i} = b_{i} = 1$，$m = 0$。
- Subtask 3（20 points）：$n \leqslant 100$。
- Subtask 4（60 points）：无特殊限制。

对于所有数据，$2 \leqslant n \leqslant 10^{3}$，$0 \leqslant a_{i}, b_{i} < n$，$1\leqslant \sum{a_i} \leqslant 10^{5}$，$0 \leqslant m \leqslant 5 \times 10^4$，$1 \leqslant x_i,y_i \leqslant n$。


title: 标题计数

background: 5ab 试图帮洛谷写机器人，数题解中有多少个一级标题。

description:
Markdown 是一种标记语言。在 Markdown 中，若一行的第一个非空白字符是井号（#），且紧跟着若干个空格，则这一行剩余的**非空白**内容将会按照一级标题渲染。

在本题范围内，下面的都是一级标题：

```plaintext
# This is a title
#    This is another title
    # This is also a title
    #   You#can#add#more#sharps
# #
```

在本题范围内，下面的都不是一级标题：

```plaintext
<h1>an HTML title</h1>
#You should insert a space
## This is a secondary title
aaaaa # This is not a title at all
 #
You should add something after the sharp sign
```

给定一段多行文本，求出这段文本总共有多少个一级标题。

inputFormat:
第一行输入一个整数 $n$，代表文本的行数。

接下来输入 $n$ 行，是给出的标记文本。

outputFormat: 输出一行一个整数，为这段文本中的一级标题个数。

hint:
#### 样例 3 解释

第 2,3,8,10 行（文本第 1,2,7,9 行）是满足条件的一级标题。

---

如果选手在比赛中使用 Windows 系统，则直接从网站或下发题面中复制的样例的换行符是 CRLF，与真实数据中的 LF 会有区别。为了方便调试，建议使用下发文件中的样例进行测试，并直接使用文件输入输出。

### 数据规模与约定

总文本不超过 $100$ 个字符，不超过 $10$ 行。文本中只有英文字母，井号（`#`），换行符（Line Feed，LF，`\n`）和空格。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|}\hline
\bf{测试点} & \bf{文本特殊性质}
\\
\hline
1 & 没有空白字符 \\\hline
2,3& 只有\ 1\ 行 \\\hline
4,5 & / \\\hline
\end{array}
$$


title: 「SvR-2」令人为难的区间操作问题

background:
**Problem Number:** $\textit{45}$

众所周知，区间操作问题应该求出区间和、最大值等值。但今天小 F 有个不情之请。

description:
小 F 正在研究[斐波那契数列](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0)，他惊讶地发现，可以把这种数列 $F$ 的定义式略作修改，得到 $\digamma$ 数列：

$$\digamma(x)=\{1,1,-1,-1,1,1,-1,-1,1,\ldots\}$$

注意到 $\digamma$ 数列具有周期性，最小正周期 $T=4$。

请注意这里 $\digamma$ 数列与数学上用其表示的[双伽玛函数](https://zh.wikipedia.org/wiki/%E5%8F%8C%E4%BC%BD%E7%8E%9B%E5%87%BD%E6%95%B0)的区别。

小 F 找到一个长度为 $n$ 的数列 $a$，他每次对其进行如下操作：

- 选定两个整数 $l,r$，满足 $1\le l\le r\le n$。
- 对于每个满足 $l\le i\le r$ 的 $i$，将 $a_i$ 加上 $\digamma(i-l+1)$。
- 记录下本次操作（即第 $j$ 次操作）的选定区间的长度 $len_j=r-l+1$。

他一共进行了 $m$ 次操作，操作后得到数列记作 $b$，同时记 $sum=\sum_{i=1}^mlen_i$。

不幸的是，小 F 把 $sum$ 和数列 $len$ 都弄丢了，他只记得 $n$ 和数列 $a,b$。

现在，他想请你根据这些信息，求出 $sum$ 的**奇偶**，**即 $\textbf{\textit{sum}}$ 对 $\textbf2$ 取模后的值**。

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

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

接下来 $3\cdot T$ 行，描述每组数据。对于每组数据：

- 第一行一个整数 $n$。
- 第二行 $n$ 个整数，描述数列 $a$。
- 第三行 $n$ 个整数，描述数列 $b$。

**数据保证数列 $a$ 一定可以经过若干操作变为数列 $b$。**

outputFormat: 对于每组数据，输出仅一行一个数，即 $sum$ 对 $2$ 取模后的值。

hint:
#### 样例 1 说明

注意到可能进行的是如下操作：

- 第 $1$ 次操作选定 $l=2,r=3$，则数列变成 $[1,{\underline\color{red}\textbf3},{\underline\color{red}\textbf4},4]$。此时 $len_1=2$。
- 第 $2$ 次操作选定 $l=1,r=3$，则数列变成 $[{\underline\color{red}\textbf2},{\underline\color{red}\textbf4},{\underline\color{red}\textbf3},4]$。此时 $len_2=3$。

则 $sum=len_1+len_2=5$，是奇数。故 $sum\bmod 2=1$。

#### 数据规模与约定
**本题采用捆绑测试**
$$
\newcommand{\arraystretch}{1.5}
\begin{array}{c|c|c|c}\hline\hline
\textbf{Subtask} & \bm{\sum n\le} & \textbf{特殊性质} & \textbf{分值} \\\hline
\textsf{1} & \le 10 & a_i,b_i\le 10^9 & 10 \\\hline
\textsf{2} & \le 10^3 & a_i,b_i\le 10^9 & 20 \\\hline
\textsf{3} & \text{无特殊限制} & a_i,b_i\le 10^9 & 20 \\\hline
\textsf{4} & \text{无特殊限制} & a_i\le b_i & 20 \\\hline
\textsf{5} & \text{无特殊限制} & - & 30 \\\hline\hline
\end{array}
$$

对于 $100\%$ 的数据，有 $1\le T\le 10^3$，$1\le n\le 10^5$，$1\le a_i,b_i\le 10^{18}$。

单个测试点内保证 $\sum n\le 2\times 10^5$。

#### 说明

$\digamma$ 数列拥有如下的递推式：

$$
\digamma(x)=
\begin{cases}
1,&x\le 2\\
-1,&x=3\\
\digamma(x-1)-\digamma(x-2)+\digamma(x-3),&x>3.
\end{cases}
$$


title: 「CGOI-2」No cost too great

background:
光芒浸透圣巢，她正犯下弥天之错。

所剩寥寥无几的信仰，为什么始终执着。

我将作灯塔，照耀王国。

但在那之前有更重要的事去做，

无论什么代价都在所不惜，尽管我所剩无多……

description:
白王正在最后一次参观他建造的宏伟宫殿。现在假设宫殿由 $n$ 个房间构成，房间之间有若干个**单向**通道。出于白王奇怪的装修癖好（不是指到处安电锯），对于第 $i$ 个房间，它向编号在区间 $[l_i,r_i]$ 中的所有房间都连有一条单向通道。例如，$4$ 号房间向 $[2,5]$ 连有单向通道，就意味着从 $4$ 号房间到 $2,3,4,5$ 号房间各有一条单向通道（一个房间可以向自己连有通道）。当一个房间向 $[0,0]$ 连有通道时，表示没有从这个房间出发的通道。

白王提出了 $q$ 个问题，每次询问从 $a$ 号房间，通过恰好 $m$ 条单向通道且不经过 $c$ 号房间到达 $b$ 号房间的方案数（两方案不同，当且仅当存在 $i$ 使得两方案通过的第 $i$ 条通道不同）。因为这个数字可能会很大，所以白王让你将答案模 $998244353$ 后再回答。

inputFormat:
第一行，两个整数 $n, q$ 表示点数和询问数。

接下来 $n$ 行，每行两个整数 $l, r$，第 $i+1$ 行的整数 $l_i, r_i$ 表示 $i$ 号节点向区间 $[l_i, r_i]$ 中的每个点都连了一条单向边。当 $l_i=r_i=0$ 时，表示该节点没有向任何点连边。

接下来 $q$ 行，每行四个整数 $a, b, c, m$ 表示一个询问。

outputFormat: $q$ 行，每行一个整数，第 $i$ 行的数字表示第 $i$ 个询问的方案数模 $998244353$ 的结果。


title: [RC-06] ijk

description:
给定一个序列 $[a_1,a_2,a_3,\dots,a_n]$，保证 $\forall i\in [2,n], a_i\ge a_{i-1}$。

计算有多少整数三元组 $(i,j,k)$ 满足：

- $1\le i,j,k\le n$。
- $a_i\times j\times a_k=i+a_j+k$。

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

第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$。保证 $a_i\ge a_{i-1}$。

outputFormat: 输出一行一个非负整数，为答案。

hint:
本题有三个子任务。

所有数据均满足：$1\le n\le 10^6$，$1\le a_i\le 10^6$，$a_i\ge a_{i-1}$。

- 子任务 $1$（$5$ 分）：$n\le 500$。
- 子任务 $2$（$5$ 分）：$a_i\le 10 $。
- 子任务 $3$（$90$ 分）：无特殊限制。


title: 「SiR-1」Popsicle

background:
猫猫喜欢收集雪糕棒，每十三个捆成一束。

可爱的猫猫喜欢优雅地摆烂。

description:
猫猫有若干个雪糕棒排成一排，每个雪糕棒上有一个 $0\sim 9$ 的数字，并且满足最左边的雪糕棒上写的数字不为 $0$。猫猫认为这一排雪糕棒从左到右依次构成了十进制正整数 $n$。

猫猫认为 $0$ 是美好的，所以她会尽可能把 $n$ 变成 $0$，也就是把所有雪糕棒都拿走。

猫猫每次会进行一次操作。每次操作选择一个数字非 $0$ 的雪糕棒，并将其减 $1$。这之后，如果最左边有连续的一些数字为 $0$ 的雪糕棒（也即 $n$ 出现了前导 $0$），猫猫会把这些雪糕棒拿走。

小老鼠会来捣乱，它会在某个时刻（可能是所有操作开始之前，也可能是猫猫任意一次操作之后）改变某个雪糕棒上的一个数字。小老鼠**总共只能改变一个数字**。

小老鼠希望操作次数尽量多，猫猫希望操作次数尽量少，所以她想知道二者都使用最优策略时，她的操作次数。

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

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

对于每组数据：仅一行，一个正整数 $n$。

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

hint:
### 样例解释 1

对于第一组数据，小老鼠可以一开始就将 $1100$ 变为 $1109$，这样猫猫共需要 $1 + 1 + 9$ 次操作把 $n$ 变为 $0$。

### 数据规模与约定

+ Subtask 0（13 pts）：$n \leq 99$。
+ Subtask 1（13 pts）：$n = 10^k$，$k$ 为自然数。
+ Subtask 2（13 pts）：$n = 10^k - 1$，$k$ 为正整数。
+ Subtask 3（13 pts）：$n \leq 999\ 999$。
+ Subtask 4（48 pts）：无特殊限制。

对于所有数据，$1 \leq T \leq 3333$，$1 \leq n \leq 9\ 999\ 999\ 999\ 999(=10^{13} - 1)$，毕竟猫猫最多一捆只有 $13$ 根雪糕嘛。


title: 做不完的作业

background:
高中的任务是非常艰巨的，要学习十门功课（浙江要学技术）。导致作业超级加倍，这一点在暑假就已经体现出来了。

作业的总量是一定的，但不同作业下发的时间是不一定的，导致每天都要花不同的时间应付作业。此时，如何保证睡眠是一个需要仔细考虑的问题。

description:
**提示：如果你对题目内容有疑问，可以配合样例更好地阅读。**

有 $n$ 个任务，第 $i$ 个任务需要 $t_i$ 的时间。Eric 要在若干天内**依次**完成这些任务。Eric 是一个专注的人，所以完成每个任务的时间**必须连续**。

一天有 $x$ 的时间。由于 Eric 需要睡觉，所以 Eric 不能利用所有的时间。具体地：

- Eric 每天**必须睡觉**；
- Eric 每天的睡觉的时间是连续的，且睡觉时间结束后，第二天恰好开始；
- Eric **前 $\boldsymbol i$ 天**的睡觉时间**总和**不能少于 $r\cdot x\cdot i$ 的时间。$r$ 是一个给定的实数，$i$ 是一个正整数。

Eric 想问你，至少需要多少天才能完成任务。

inputFormat:
第一行输入四个整数 $n,x,p,q$，代表 $r=\dfrac p q$。

接下来一行，输入 $n$ 个整数，第 $i$ 个代表 $t_i$。

outputFormat: 输出一个正整数，代表最小天数。可以证明，在下文限定的数据下，一定存在至少一个解。

samples:
见下发文件 task/task4.in
见下发文件 task/task4.ans

samples:
见下发文件 task/task5.in
见下发文件 task/task5.ans

hint:
#### 样例 1 解释

下面是一种可能的方案：

Eric 先在第一天做任务 1，总共消耗 $1$ 的时间，用 $4$ 时间睡觉，满足至少要 $5\times \dfrac 1 3=\dfrac 5 3$ 的时间睡觉的要求。

Eric 再在第二天加班加点，完成剩下的任务，有 $1$ 的时间睡觉。两天睡觉总量为 $5\ge 10\times \dfrac 1 3=\dfrac {10} 3$，也是满足要求的。

#### 样例 2 解释

Eric 试图在第一天完成任务 1，但假如要做就会熬夜，觉就不够睡。所以 Eric 第一天只能睡大觉。Eric 在第二天完成任务 1 就没有问题。

同时请注意，即使睡觉时间满足了要求，Eric 也不能在第二天就完成任务 2，因为 Eric 必须睡觉。所以 Eric 先睡到第三天，然后完成任务 2。可以证明不存在方案小于三天。

同时注意数据**不保证** $\gcd(p,q)=1$。

#### 样例 3 解释

显然一天只能干一件活，所以要 $10$ 天。

#### 样例 4 解释

该样例满足子任务 3 的限制条件。

#### 样例 5 解释

该样例满足子任务 5 的限制条件。

### 数据规模与约定

**本题捆绑测试**。对于所有数据，保证 $1\le n\le 10^5$，$1\le t_i<x\le 10^6$，$1\le p<q\le 10^6$。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|}\hline

\bf 子任务 & \bf 分值 & n\le & \bf特殊性质
\\
\hline
1 & 10 & 3 & /\\\hline
2 & 20 & 10^3 & \bf A \\\hline
3 & 20 & / & \bf A\\\hline
4 & 20 & / & \bf B\\\hline
5 & 30 & / & /\\\hline
\end{array}
$$

特殊性质 $\bf A$：$\forall i,\ \dfrac{t_i}{x}+\dfrac{p}{q}\le 1$。

特殊性质 $\bf B$：$n\times q\le 10^6$。

为了减少评测量，本题开启子任务依赖。具体地，当且仅当前四个子任务全部通过时，子任务 5 才计分，否则子任务 5 计 $0$ 分。


title: 「FAOI-R2」Paint (A)

background:
小 Y 是一个胖子，他最爱下楼梯了，因为下楼梯很省力气，但是他却有强迫症。

由于刷漆工人 HG 的油漆不够，每一层台阶都只刷了一半——左边或右边，好让小 Y 下楼时不踩到油漆。（~~众人：这是什么逻辑？~~）

description:
整个楼梯共 $3^N$ 级台阶。

HG 刷漆的规律是：对于**从上到下**第 $I$ 级台阶，若 $V_3(I)$ 是奇数，则刷在左边，否则刷在右边。**$V_3(I)$ 的定义请见提示。**

小 Y 因为强迫症，要求自己不能踩到油漆。

现在他来求助你，他最少会踩到油漆多少次？

- 一次只能下一级台阶。
- 如果小 Y 站在当前台阶的左边，则他必须站在下一级台阶的右边，反之亦然。
- 如果油漆在当前台阶左边，那么需要站在当前台阶右边才算没踩到油漆，反之亦然。
- 小 Y 唯一可以控制的是：他在第 $1$ 级台阶上站在哪边。也就是说，小 Y 只有 $2$ 种下楼梯的方案供选择。

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

### 形式化题意

给定三个 01 串 $A,B,C$，长度均为 $3^N$。字符串下标从 $1$ 开始。

其中：

- $A=\texttt{101010101\ldots101}$；
- $B=\texttt{010101010\ldots010}$；
- $C=\texttt{001001000\ldots}$；具体来说，第 $I$ 个字符为 $V_3(I) \bmod 2$。**$V_3(I)$ 的定义请见提示。**

记 $\operatorname{mc}(X,Y)$ 为字符串 $X$ 和 $Y$ 中匹配的字符的个数。

试求：

$$\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}$$

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

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

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

下面 $T$ 行，每行一个正整数 $N$。

outputFormat:
每组数据一行，输出踩到油漆的最少次数，即 $\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}$。

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


title: 「CMOI R1」Bismuth / Linear Sieve

background:
![](bilibili:BV1qF4m157gc)

> Can you imagine find wakeless,like a satellite,in the black sky?
>
> Somewhere,like a star.
>
> We dream about things way beyond this atmosphere.
>
> At we're now,on the air.
>
> ……
>
> But I eventually evaporates in a blackhole…
>
> Will I just stick up there?……

description:
给定以下程序中的 $n$（即输入），求以下伪代码的输出结果。

```
Input n
For i := 1 to n
	is_not_prime[i] := 0
cntp := 0
counter := 0
For i := 2 to n {
	If is_not_prime[i] = 0 {
		cntp := cntp + 1
		primes[cntp] := i
	}
	For j := 1 to cntp {
		If i * primes[j] > n
			break
		is_not_prime[i * primes[j]] := 1
		If i Mod primes[j] > 0 // should be `If i Mod primes[j] = 0` in Sieve of Euler
			break
		counter := counter + 1
	}
}
Print cntp, counter
```
请注意此代码**不是线性筛**，差别在注释过的那一行。

inputFormat: 一行一个整数，即输入，也就是给定的 $n$。

outputFormat: 一行两个非负整数，即伪代码输出。


title: 「CGOI-2」No mind to think

background:
“我的王，这个孩子……不纯粹……他……”

“嗯。容器不能拥有与人交流的能力，否则可能会在交流中产生思维。它们只应该有猎杀的本能，和战斗的天分。就像我的守卫们一样。”

“那些不过是傀儡……”

“傀儡也比这个有思维的家伙好。改天把它带走，它真的好吵……我累了，我出去走走。”

~~无敌的勇敢的性感的神秘的迷人的神气的勤勉的强势的华丽的激情的可怕的漂亮的强大的灰色王子左特骂骂咧咧地滚出了白色宫殿。~~

description:
圣巢有 $n$ 个鹿角虫车站和 $n$ 条轨道，第 $i$ 条轨道连接 $u_i$ 和 $v_i$ 两个车站。初始时轨道是单向的，第一次经过第 $i$ 条轨道时，只能从 $u_i$ 到达 $v_i$；第一次经过后该轨道变为双向，既可以从 $u_i$ 到 $v_i$，又可以从 $v_i$ 到 $u_i$。

现在白王在 $1$ 号车站，他要经过若干条轨道到达 $2$ 号车站，再从 $2$ 号车站经过若干条轨道到达 $3$ 号车站……一直到 $x$ 号车站。因为白王需要尽快走遍整个王国以便探清瘟疫的情况，所以他问你，当 $x$ 取遍 $[2,n]$ 中的每一个整数时，所经过的最少的轨道数分别是多少。

inputFormat:
第一行一个整数 $n$，表示车站数与轨道数。

接下来 $n$ 行，每行两个整数。第 $i$ 行的数 $u_i,v_i$ 表示第 $i$ 条轨道第一次经过时只能从 $u_i$ 走到 $v_i$，此后可以双向经过。

outputFormat: 输出 $n-1$ 行，每行一个数，第 $i$ 个数表示当 $x=i+1$ 时，经过的最少轨道数。

hint:
### 样例说明

对于样例 1，地图如下所示：

![样例 1 地图](https://z3.ax1x.com/2021/06/24/RMPoN9.png)

$x=2,3,4,5,6$ 的最短路径均为沿着 $1\to 2\to3\to4\to5\to6$ 这条路径走，答案分别是 $1,2,3,4,5$。

$x=7$ 时，若仍按照上述路径走，就不能从 $6$ 号车站直接通过 $7\to 6$ 这条轨道到 $7$ 号车站，因为这条轨道还是单向的。绕路回去需要再经过 $6$ 条轨道，总共 $11$ 条轨道。

但如果先走一遍 $7\to6$，即沿着 $1\to7\to6\to7\to1\to2\to3\to4\to5\to6$ 的路径走，来到 $6$ 时就能直接走到 $7$，总共只需要经过 $10$ 条轨道，同时也满足了依次经过 $1\sim 7$ 号点，比上一种方案更优。

---

### 数据范围

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

| 编号 | $n$ |分值|
| :-: | :-: | :-: |
| 0 | $\le6$ | 10pts|
| 1 | $\le18$ | 20pts |
| 2 | $\le3\times10^3$ | 32pts |
| 3 | $\le5\times10^5$ | 38pts |

对于 $100\%$ 的数据，$3\le n\le5\times10^5$。

数据保证从 $1$ 号车站出发可以到达任意车站，且无重边自环、二元环。


title: 十二重骗分法（Cheating XII）

description:
一阵恍惚过后，你发现自己坐在机房里。一看时间，现在竟然是 2202 年！你又环视了一下周围的情况，原来自己在 CSP-J 2202 的考场上。

你还没搞清楚情况时，似乎听见有人对你低语：「想知道怎么回事吗？那就展现你以往的能力，把这次的 CSP-J 也 AK 掉吧。」

于是你看到四个题分别是：

1. 输入一个正整数 $n$，求 $\lfloor \sqrt n \rfloor$。

2. 给定一个左右各有 $n$ 个点的二分图，与其中的边，求它完美匹配的方案数，答案对 $998244353$ 取模。

3. 生命游戏（Conway's Game of Life）进行于一个无限大的二维网格上，每个格子要么是空地，要么有一个细胞。每个时刻都会进行一轮**迭代**，规则如下：
![](https://cdn.luogu.com.cn/upload/image_hosting/do0c6ras.png)
现在，给定你初始状态，求迭代 $k$ 次后的细胞数。
ps：你可以在 [这里](https://playgameoflife.com/) 试玩。

4. 给你一个 $n$ 个点、 $m$ 条边的无向图，每个点都可以涂上 $k$ 种颜色中的一种，且相邻的点（即有边直接相连的点）不能有相同的颜色。求有多少种染色方案，答案对 $998244353$ 取模。

「这怎么可能啊！」你差点惊叫出来。不过你发现，唯独你的电脑上有题目的输入数据！你想暴力跑出答案，却发现 2202 年的评测机性能和一百多年前没差别。

那该怎么办呢？总之只能靠自己了吧。

**输入数据可以在题目下方的附件中下载。**

inputFormat:
第一行一个正整数 $T$，表示测试点编号。

若 $T \in \{ 1,2\}$，表示 Subtask 1。接下来一行仅一个正整数 $n$。

若 $T \in \{3,4,5,6\}$，表示 Subtask 2。第二行一个正整数 $n$。
接下来 $n$ 行，第 $i$ 行先输入一个正整数 $m_i$，表示左部分第 $i$ 个点（记作 $u_i$）的度数为 $m_i$；后面接着 $m_i$ 个整数 $v_{i,1},v_{i,2},\cdots,v_{i,m_i}$，依次表示与 $u_i$ 连接的右部分节点编号。

若 $T \in\{ 7,8,9\}$，表示 Subtask 3。第二行输入两个正整数 $n,m,k$，表示输入的初始形态有 $n$ 行 $m$ 列（除此之外是无限大的二维平面，没有其它细胞），迭代 $k$ 次。接下来 $n$ 行，每行一个长度为 $m$ 的 01 串，`0` 表示空地，`1` 表示细胞，描述了一行的形态。

若 $T \in\{ 10,11,12\}$，表示 Subtask 4。第二行输入三个正整数 $n,m,k$。接下来 $m$ 行，每行两个正整数 $u,v$ 描述一条无向边，保证无重边和自环。

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


title: [Aya Round 1 A] 幻想乡扑克游戏

background:
**Problem Number:** [$\textit{22}$](https://www.luogu.com.cn/training/1392)

在能力卡牌异变之后，幻想乡的少女们将多余的卡牌收集起来，仿照外界人的「斗地主」这一游戏，进行了愉快的玩耍。

description:
斗地主是一种使用 $\tt A$ 到 $\tt K$ 加上大小王的共 $54$ 张扑克牌来进行的游戏，其中大小王各一张，其它数码牌各四张。在斗地主中，牌的大小关系根据牌的数码表示如下：

$$\tt 3<4<5<6<7<8<9<10<J<Q<K<A<2<\stackrel{\mathclap{\color{white}\textbf{\textit{wxy}}}}{\text{小王}} < \text{大王}$$

且牌的大小关系和花色无关。

游戏开始时，将会给 $3$ 名玩家各自发放 $17$ 张牌作为手牌，余下三张作为底牌。**玩家会将牌从大到小排序理好**，然后根据自己牌型的好坏程度来选择是否叫地主。

你认为，如果自己的手牌中存在王炸（即大小王各一张）或者至少一个炸弹（即四张数码相同的牌），则你会选择叫地主。

请实现一个程序来判断你是否应该叫地主。

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

- 第一行输入一个整数 $T$，表示数据组数。
- 接下来 $T$ 行，每行输入一个长度为 $17$ 的字符串，表示你的手牌。**保证牌已经预先理好**。在输入中使用 $\tt T$ 代表点数为 $\tt 10$ 的牌，使用 $\tt X$ 代表小王，使用 $\tt D$ 代表大王。

outputFormat:
- 输出共 $T$ 行。
- 对于每组数据，输出一行一个字符串：
  - `yes` 代表你应该叫地主。
  - `no` 代表你不应该叫地主。
- 你可以输出字符串的任意大小写形式。例如：字符串 `yes`、`Yes`、`YES` 均会被视为表示应该叫地主。

samples:
3
X2AAKKKKQT9765433
DX22AKKQJTT884443
X2AAAKQQJT8554433

hint:
### 样例解释

> 对于数据 $1$，输入数据相当于下面的手牌（忽略花色）：
>
> ![](https://cdn.luogu.com.cn/upload/image_hosting/g56d0ywv.png)
>
> 该手牌中存在炸弹：
>
> ![](https://cdn.luogu.com.cn/upload/image_hosting/6sal0bye.png)
>
> 故你选择叫地主。

> 对于数据 $2$，输入数据相当于下面的手牌（忽略花色）：
>
> ![](https://cdn.luogu.com.cn/upload/image_hosting/6g2jrx6t.png)
>
> 该手牌中存在王炸：
>
> ![](https://cdn.luogu.com.cn/upload/image_hosting/1ulc1sxz.png)
>
> 故你选择叫地主。

> 对于数据 $3$，输入数据相当于下面的手牌（忽略花色）：
>
> ![](https://cdn.luogu.com.cn/upload/image_hosting/5qb6bwen.png)
>
> 该手牌中不存在王炸和炸弹。故你选择不叫地主。

### 数据范围与约定

对于 $100\%$ 的数据，$1 \le T \le 10^4$。**保证牌已经预先理好**。


title: [Aya Round 1 C] 文文的构造游戏

background:
**Problem Number:** [$\textit{23}$](https://www.luogu.com.cn/training/1392)

众所周知，射命丸文和琪露诺是好朋友。但是文是大妖怪，非常聪明，而琪露诺是个笨蛋。为了提升琪露诺的智商，文便给琪露诺出了一道简单的题目。

description:
对于一个长度为 $l$ 的数列 $p$，定义 $S(p)$ 为所有元素的**异或和**，其中 $\oplus$ 指[按位异或运算](https://baike.baidu.com/item/%E5%BC%82%E6%88%96%E6%93%8D%E4%BD%9C)。

给定整数 $s,m$，判断能否构造一个长度为 $n$（$n$ 值自定）的数列 $a$，满足：

- $1 \le n \le m$。
- $1 \le a_i \le s$。
- $S(a)=0$。
- $a_1+a_2+\cdots+a_n=s$。

试构造任意一组合法解或报告无解。

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

- 第一行输入一个整数 $T$，表示数据组数。
- 接下来 $T$ 行，每行输入两个整数 $s,m$。表示一组询问。

outputFormat:
- 输出共 $T$ 行。
- 对于每组数据：
  - 若有解，首先输出一个整数 $n$，然后输出 $n$ 个整数，表示 $a$。
  - 若无解，仅输出一行一个整数 $-1$。

hint:
### 样例解释

- 对于数据 $1$，容易发现 $3\oplus5\oplus6=0$，$3+5+6=14$。符合要求。
- 对于数据 $2$，发现数列 $\{3\},\{1,2\},\{1,1,1\}$ 均不符合要求，故无解。

### 数据范围与约定

对于 $100\%$ 的数据，有 $1\le s\le 10^{18}$，$1 \le m$，$1 \le \sum m \le 10^6$。

**友情提示，您可能需要使用较快的 I/O 方式。**


title: [Aya Round 1 H] 破碎的历史

background:
幻想乡迎来了它的毁灭，幻想的载体也已经遁入了幻想。

所幸的是，幻想乡中的乡民们还侥幸存活着，她们在尝试恢复幻想乡的历史。然而历史之中的大大小小的事情不计其数，人们只能记得起一些大事情罢了。

或许，根据那些重要的事情，可以把次要的事件推导出来呢？

description:
数轴的正半轴上有 $n$ 个互不相同的被黑白染色的特殊整点，位置从左到右依次为 $p_1,p_2,\cdots,p_n$。维护初始为空的**可重**线段集合 $S$。

$q$ 次操作。操作分若干种，具体格式如下：

- `1 l r`：将所有满足 $l \le x \le y \le r$ 且两端点均为特殊整点的线段 $[x,y]$ 加入 $S$。
- `2 x`：撤回第 $x$ 次操作添加的线段。

在初始时和每次操作后，假设你可以进行任意次（可以是零次）染色。每次从 $S$ 中选出一条线段 $[x,y]$，满足位于点 $x$ 和点 $y$ 的特殊整点均为黑色，然后将所有在线段内的白色特殊整点染黑。试判断是否存在至少一种合法染色方式使得正半轴上的所有特殊整点均被染黑（即，不存在白色特殊整点）。**注意：所有的询问均为「假设」，即各组询问之间独立，不会造成对数轴的实际修改。**

inputFormat:
- 第一行输入两个整数 $n,q$。
- 第二行输入 $n$ 个整数 $p_1,p_2,\cdots,p_n$，表示 $n$ 个特殊整点从左到右的位置。
- 第三行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示特殊整点的颜色。其中 $a_i=0$ 表示白色，$a_i=1$ 表示黑色。
- 接下来 $q$ 行，每行二至三个整数，表示一次操作。

outputFormat:
- 输出共 $(q+1)$ 行。
- 在初始时和每次操作后，输出一行一个字符串：
  - `yes` 代表存在合法染色方式。
  - `no` 代表不存在合法染色方式。
- 你可以输出字符串的任意大小写形式。例如：字符串 `yes`、`Yes`、`YES` 均会被视为表示存在合法染色方式。

hint:
### 样例解释

六个特殊点的位置/颜色在数轴正半轴上如图所示。

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

容易发现，并非所有点都是黑点。因此在进行操作前，输出 $\verb!NO!$。

第一次操作后，一共往 $S$ 加入了三条线段：$[5,5],[8,8],[5,8]$（图中省略了端点重叠的线段）。容易发现，此时无法进行任何操作，因此没法将所有点变成黑点。输出 $\verb!NO!$。

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

第二次操作后，又往 $S$ 中加入了 $20$ 条线段。除去端点重叠的选段，在 $S$ 中如图所示。（以示区别，上一次操作加入的边标成了深蓝色）。

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

可以找出一种方案，将图上所有特殊点变成黑点。具体而言，首先选择 $S$ 中 $[1,5]$ 线段（容易发现位于 $1$ 和 $5$ 的特殊点均为黑点，因此可以进行染色），那么可以把位于 $2$ 和 $3$ 的点染色。

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

此时又可以选择 $S$ 中 $[3,13]$ 线段（在上一轮操作中，$3$ 号点变为了黑点，因此 $[3,13]$ 符合条件），将点 $8$ 染为黑色。

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

此时所有点都为黑色，因此输出 $\verb!YES!$。再次强调，询问之间互相独立，且只是询问是否存在染色方案，而不会对特殊整点进行实际上的染色操作。

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

第三个操作撤回了第二个操作往 $S$ 里加入的所有线段。因此退回到了只有第一个操作的情况。不存在一种方案将所有点染黑，因此输出 $\verb!NO!$。

### 数据范围

对于所有数据，$1 \le n,q \le 5 \times 10^5$，$a_i \in \{0,1\}$，$1 \le l< r \le 10^9$，$1 \le p_i \le 10^9$。保证 $p_i$ 单调递增，$2$ 操作撤销的只会是 $1$ 操作，且每个操作最多被撤销一次。


title: [Aya Round 1 F] 琪露诺的选择题

background:
**Problem Number:** [$\textit{24}$](https://www.luogu.com.cn/training/1392)

在经过射命丸文的一番调教之后，琪露诺的智商总算增长了⑨点。

现在寺子屋又要开始考试了，琪露诺通过一些手段知道了答案中的一些信息，而且因为她冰雪聪明，她不希望自己的成绩进步太明显，从而被老师上白泽慧音特别关照。因此她找到了你寻求一些帮助。

（注意：考试作弊是不对的！）

description:
有 $2\cdot n$ 道选择题，每题有 $\text{A}$ 和 $\text{B}$ 两个选项。正确答案可以表示为一个长度为 $2\cdot n$ 的字符串。

现在你要构造出一份作答（长度同样为 $2\cdot n$ 的字符串），其中**恰好**有 $a$ 个 $\text{A}$，同时与正确答案相比，你的作答恰好有 $e$ 个错误。如果不存在这样的构造方案，报告无解。

**注意：为了方便处理，本题保证 $e\le n$。**

**形式化地**，给定 $n,a,e$ 和一个长度为 $2\cdot n$ 的 01 串 $s$，你需要构造出一个恰好有 $a$ 个字符是 $\texttt 0$ 的长度为 $2\cdot n$ 的 01 串 $p$，使得

$$
\left(\sum_{i=1}^{2\cdot n}[s_i\ne p_i]\right)=e,
$$

其中 $[]$ 是 Iverson Bracket，详见「**说明/提示**」中的「提示」。

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

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

对于每组数据：

- 第一行输入三个整数 $n,a,e$。
- 第二行输入一个长度为 $2\cdot n$ 的字符串，表示答案串。

outputFormat:
输出共 $T$ 行。

对于每组数据：

- 若有解，输出一行一个长度为 $2\cdot n$ 的字符串，表示你构造的作答串。
- 若无解，输出一行一个字符串 $\texttt{-1}$。

hint:
### 样例解释

对于数据 $1$，你构造出的作答串 $\text{BB{\color{e74c3c}AA}BB}$ 中恰好有 $2$ 个 $\text A$，与答案串相比刚好有 $3$ 处不同（即，有 $3$ 处错误）：

$$
\text{{\color{e74c3c}A}BA{\color{e74c3c}B}B{\color{e74c3c}A}}\\
\text{{\color{52c41a}B}BA{\color{52c41a}A}B{\color{52c41a}B}}
$$

故符合要求。

对于数据 $2$，不存在合法构造方案。

### 数据规模与约定

对于 $100\%$ 的数据，有 $1\le T\le 100$，$1\le n\le 10^5$，$0\le e\le n$，$0\le a\le 2\cdot n$。

单组测试点内保证 $\sum(2\cdot n)\le 10^6$。

### 提示

$\textbf{A. Iverson Bracket}$

Iverson Bracket，是一种用方括号记号，如果方括号内的条件满足则为 $1$，不满足则为 $0$。更确切地讲，

$$
[P]=\begin{cases}1, & \text{If }P\text{ is true,}\\0,&\text{Otherwise.}\end{cases}
$$


title: 「DPOI-1」优美的序列

background:
#### Update on 2022.12.18：新增一组针对 @[zhuoxingmu](https://www.luogu.com.cn/user/421155) 的 Hack 数据，放置于 #21，分值为 $5$ 分。
#### Update on 2022.12.18：新增一组针对 @[大眼仔Happy](https://www.luogu.com.cn/user/537046) 的 Hack 数据，放置于 #22，分值为 $5$ 分。
------------
不可以，总司令。

description:
总司令给你一个长为 $n$ 的序列 $a$。

他认为这个 $a$ 现在也许不够优美，他希望将其重排为一个 $a'$，使之变得优美。

我们称一个长为 $n$ 的序列 $a$ 优美，当且仅当 $\exists i \in [1,n]$，满足：

- $\forall j \in [1, i)$，$a_j > a_{j + 1}$。
- $\forall j \in (i, n]$，$a_j > a_{j - 1}$。

他命令你求出 $a$ 经过重排可以得到多少个不同的 $a'$。由于结果可能很大，你只需要求出结果对 $p$ 取模的值。

由于一个固定的 $a$ 太无趣了，于是他给你 $m$ 次修改，每次修改形如 `x k`，表示令 $a_x \leftarrow k$。你需要在每次修改后求出当前的答案。

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

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$；

接下来 $m$ 行，每行两个整数 $x, k$，表示一次修改操作。

outputFormat: 共 $m + 1$ 行，每行一个整数，表示初始状态下及每次修改后所求的值。

samples:
见下发文件 sequence2.in
见下发文件 sequence2.out


title: 『MdOI R5』Triangulation

description:
有一个正 $n$ 边形，顶点按顺时针方向从 $1$ 到 $n$ 依次标号。给定这个多边形的 $n-3$ 条**互不相同**的对角线，满足它们**互相之间只可能在顶点处相交**。这样我们得到了一张 $n$ 个点，$2n-3$ 条边的无向图。

凸多边形的对角线指的是连接两个**不相同**且**不在多边形上相邻**的顶点的一条线段。

实际上，这个无向图可以是任意一个凸 $n$ 边形的三角剖分图。

你需要构造这个无向图的一棵生成树，使得每个点的度数都是**奇数**，或报告无解。

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

接下来 $n-3$ 行，每行两个整数 $u,v$ 表示一条给定的对角线 $(u,v)$。

outputFormat:
如果无解，那么输出一行一个整数 $-1$。

如果有解，那么输出 $n-1$ 行，每行两个数 $u,v$ 表示你所构造的答案中的一条边 $(u,v)$。

hint:
对于 $100\%$ 的数据，$3\le n\le 3\times 10^5$。

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

$\operatorname{Subtask} 2(1\%)$：$n$ 为奇数。

$\operatorname{Subtask} 3(10\%)$：$u=1$。

$\operatorname{Subtask} 4(30\%)$：$n\le 100$。

$\operatorname{Subtask} 5(30\%)$：$n\le 5\times 10^3$。

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


title: [集训队互测 2023] 傅里叶与交通系统

background: 傅里叶荣升巴黎市交通部长。新官上任三把火，傅里叶决定重构巴黎市的交通系统。

description:
巴黎市的地图可以看成一个无限大的二维平面。傅里叶在上面修建了 $n$ 条传送带：第 $i$ 条传送带修建于 $x\in[p_{i-1},p_i),y\in\mathbb R$ 的区域中。对于 $x<p_0$ 或者 $x\geq p_n$ 的部分，傅里叶没有修建传送带。

当一个人处于第 $i$ 个传送带的区域内时，他会受传送带影响强制以 $v_i$ 单位长度每秒的速度向 $y$ 坐标增加的方向移动。$v_i$ 可能为负，此时其 $y$ 坐标会以相应的速度减小。

在位于未修建传送带的区域上时，$y$ 坐标不会受到传送带的影响。

除了受传送带带动以外，这个人自己也可以移动。为了避免在速度不同的传送带间移动时出现跌倒事故，傅里叶委托麦克斯韦设计了脚底附有钢板的鞋子，并且在传送带上安装了强力磁铁。穿上这种鞋子后，你将只能 **沿着与某条坐标轴平行，可能与坐标轴同向或反向** 的方向，以不超过 $V$ 单位长度每秒的速度移动。有了这种鞋子，**在从一个传送带移动到另一个传送带时，先前的速度不会被继承，这个人将立刻按照新传送带的移动速度来移动**（自然，自身的移动还是可以同步进行的）。

**个人的运动与传送带的运动是叠加的**。

**在任意时刻，这个人都可以自由调整其运动的速率、方向；可以通过不断在极小间隔内切换方向以达到近似斜向移动的效果，甚至动态调整速率、方向达成近似曲线运动的效果；但是其任意时刻都只能有平行于坐标轴、不超过 $V$ 的瞬时速率。**

**就算在没有铺设传送带的位置上，这个人仍然可以靠他的自由意志移动，不过还是只能沿坐标轴方向以不超过 $V$ 单位长度每秒移动**（问就是麦克斯韦的靴子已经成为概念级装备了）。

现在，傅里叶想知道他的交通系统究竟有多么伟大。因此，他向你提出了 $q$ 组询问，每次询问如果有一个人要从 $(x_1,y_1)$ 走到 $(x_2,y_2)$，最少需要多少时间。因为傅里叶是唯一真神，所以他当然不会设计一个有缺陷的交通系统，因此所有的 $v_i$ 的绝对值均严格小于 $V$，进而总是可以从一个位置走到另一处。（虽然这将会导致就算在最优情况下，通过传送带系统到达目的地的时间也无法小于原本的一半，更多的时候反倒更慢了，但是谁让他是交通部长，而你只是他手下的一个雇员呢？）

inputFormat:
第一行三个整数 $n,q,V$，表示传送带数目、询问个数以及人的移动速度。

下一行 $n+1$ 个整数 $p_0,p_1,\dots,p_n$，表示传送带的边界信息。

下一行 $n$ 个整数 $v_1,v_2,\dots,v_n$，表示每个传送带的速率。

接下来 $q$ 行，每行四个整数 $x_1,y_1,x_2,y_2$，表示此次询问的起讫点。

outputFormat:
对于每次询问，输出一行一个实数，表示此次移动所需的最小时长，单位为秒。你需要保证输出与标准答案的相对或绝对误差不超过 $10^{-5}$。

- 如果你怀疑你的代码中出现了较大的精度误差，可以尝试使用更多整数和分数以规避浮点数运算，从而减少误差。

hint:
样例 #4，#5 详见附件。

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

样例 #1 的解释：

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

第一问中，上图是一种极优的行走方式。蓝色区域是传送带所在区域，在其上时我们以 $(3,12)$ 每秒的速度移动（其中自身移动的速度是 $(3,7)$，也即可以看作是三成时间沿着 $x$ 轴正方向、七成时间沿着 $y$ 轴正方向移动；在极短时间内不停切换，可以达成如上图中斜线行走的效果；$(3,7)$ 的自身行走与 $(0,5)$ 的传送带运转叠加成为 $(3,12)$ 的速度向量）。

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

第二问中，上图是一种极优的行走方案。

需要注意的是，这两问中能达成最少时间的行走方案不止图中给出的两种。

对于所有数据，均满足 $n,q\leq1.5\times10^5$，$-5\times10^5\leq p_0<p_1<p_2<\dots<p_n\leq5\times10^5$，$ |x_1|,|y_1|,|x_2|,|y_2|\leq5\times10^5$，$0\leq|v_i|<V\leq5\times10^5$。

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

- Subtask 1（5 分）：保证 $n=0$。
- Subtask 2（10 分）：保证 $n,q\leq1000$。
- Subtask 3（10 分）：保证对于所有询问，$x_1=p_0,x_2=p_n$。
- Subtask 4（10 分）：保证所有询问的 $x_1$ 全都相等，所有询问的 $x_2$ 全都相等（但不保证 $x_1=x_2$）。
- Subtask 5（15 分）：保证 $v_i$ 单调不降，且询问的 $x_1\leq x_2$。
- Subtask 6（15 分）：保证存在 $i$ 使得 $p_i=x_1=x_2$。（但并不保证所有询问的 $i$ 都相同）
- Subtask 7（15 分）：保证除 $n,q,V$ 外，其它值都在合法范围内独立随机得到（$p$ 的随机方式是随机 $n+1$ 个不等的 $[-5\times10^5,5\times10^5]$ 中的值并排序）。
- Subtask 8（15 分）：保证 $n,q\leq5\times10^4$。
- Subtask 9（10 分）：无特殊限制。


title: 『STA - R1』好吃的智慧果子

background:
在上古时代，$-(2077^{-1}\ \ (mod=2035))$ 年，$\mathfrak{Morlin}$ 种下了一棵非常珍贵的$\colorbox{black}{\textcolor{red}{\textbf{智♂慧♂树♂}}}$，被 $\mathfrak{char\_phi}$ 看见了。

过了 $114810$ 年，树上结出了 $\colorbox{black}{\textcolor{blue}{\textbf{智♂慧♂果♂子♂}}}$。
又过了 $1919514$ 年，果子成熟了，$\mathfrak{char\_phi}$ 非常馋。

$\mathfrak{char\_phi}$ 十分想吃果子，但是~~神机妙算的~~ $\mathfrak{Morlin}$ 早就知道 $\mathfrak{char\_phi}$ 想要吃他的果子，所以把每个果子都装进了密码箱。

现在，$\mathfrak{char\_phi}$ 把偷果子这项重任托付给了你。

description:
**形式化题面**

维护一个序列 $\{a_n\}$，每次操作给五个非负整数 $l, r, k, p, c$，对于所有 $i\in[l,r]$，将 $a_i\gets (f_{a_i}^k+c)\bmod p$。

其中 $f$ 是 Fibonacci 数列，定义为：
$$f_n=\begin{cases}n&n\leqslant 1\\f_{n-1}+f_{n-2}&n>1\end{cases}$$
***

**原题面**

~~神机妙算的~~ $\mathfrak{Morlin}$ 早就知道 $\mathfrak{char\_phi}$ 很聪明，所以他会不定时改密码。

每个密码箱上有一个数字，组成了数列 $\{a_n\}$。

关于密码有 $m$ 次操作，每次操作给定五个整数 $l, r, k, p, c$，表示将满足 $l \leqslant i \leqslant r$ 将 $a_i$ 变成 $(f_{a_i}^k+c) \bmod p$（$f_i$ 代表斐波那契数列的第 $i$ 项；保证 $l \leqslant r$）。

$\mathfrak{char\_phi}$ 搞了一个记录器记录下了 $\mathfrak{Morlin}$ 的操作。现在，他把记录器给了你，希望你能在 $\mathfrak{Morlin}$ 操作完后搞出所有密码箱的密码。

inputFormat:
第一行，两个整数 $n, m$，表示果子的数量和操作次数。

第二行，$n$ 个整数为数列 $a$，表示每个密码箱上的数字。

接下来 $m$ 行，表示 $\mathfrak{Morlin}$ 的操作 $l, r, k, p, c$。

outputFormat: 一行，表示所有密码箱的密码，每个密码间使用空格隔开。


title: 停车场

description:
你有一片空地。这片空地可以视作一个一个 $n\times n$ 的正方形。空地外一圈为墙壁，你无法拆除它们。

现在你要在这片空地上规划停车位，使之成为一个停车场。你希望空地的左下角是停车场的出入口。出入口不能规划为停车位。空地和停车位都是 $1\times 1$ 的正方形，且正方形的每条边与墙壁平行或者垂直。

每个停车位都应该与至少一个空地四连通（即：停车场的上、下、左、右方至少有一个空地），且这个空地应当能通过若干次向上、下、左、右的移动，在不经过任何停车位的情况下到达出入口。

下图为 $n=4$ 时停车位数最多的放置方法之一，其中红色为车位，蓝色为出口，白色为空地。

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

请问 $n=2023$ 下最多能安排多少个停车位？

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


title: 「WHOI-4」ggcd

background:
如何输入输出 `__int128`：

```cpp
__int128 read() {
  char c = getchar();
  __int128 x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
void write(__int128 x, char c = '\0') {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
  if (c != '\0') putchar(c);
}
```

description:
**本题已新增一组样例，请注意查看。**

小 Y 给了你长度为 $n$ 的数组 $y$ 以及一个正整数 $m$，保证 $0\le y_i<m$，请你构造一个同样长为 $n$ 的数组 $x$，使得：

1. $x_i$ 在 `__int128` 范围内；
2. $x_i\bmod m=y_i$；
3. $\gcd(|x_1|,\cdots,|x_n|)\bmod m$ 最大。

注意，$x_i$ **可以为负**，此时 $m\mid (x_i-y_i)$ 且 $0\le y_i<m$。

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

接下来一行 $n$ 个非负整数，代表 $x_i \bmod m$ 的值。

outputFormat:
第一行一个非负整数 $g$，代表 $\gcd(|x_1|,|x_2|,\cdots,|x_n|)\mod m$ 的可能最大值。

接下来一行 $n$ 个整数，代表 $x_i$。

hint:
**数据范围**

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

Subtask 1（$30$ pts）：$m$ 是素数。

Subtask 2（$70$ pts）：无特殊限制。

对于所有数据，保证 $2\le m \le10^9$，$1\le n\le10^6$。

**关于 Special Judge**

对于每个测试点：

如果你输出的格式不正确，你将会获得 $0$ 分。

如果你输出的数中有不在 `__int128` 范围的数，可能导致溢出所以你可能无法获得预期的分数。

如果你的数列 $x$ 不符合题目给定的 $y$，你将会获得 $0$ 分。

如果你的数列 $x$ 不符合你输出的 $g$，你将会获得 $0$ 分。

如果你的 $g$ 不为最大，你将会获得 $0$ 分。

否则你将获得该测试点的所有分数。


title: 「KDOI-02」一个仇的复

background:
**本题由于 OI 赛制，关闭 subtask，可能会放部分错解高分，赛后将开启 subtask。**

「听说那件事了吗？愿他们安息。」
「诶？你看，前面那座环形建筑是什么？」
「等我对比一下……啊哈！这就是他们的老巢！」
「捣毁了它，为牺牲的同志们报仇！！！」
死亡的宇宙射线指向了脆弱的文明，正准备发出它震耳欲聋的怒吼。

description:
外星人的空间站是一个环形结构。不过，由于环的两段不连通，因此可以将其近似为 $2\times n$ 的平面网格。目前，地方飞船有 $n$ 种不同规格的射线武器，作用范围是 $1\times x$（$x$ 为正整数）的长方形。并且，武器可以往顺时针或逆时针方向旋转 $90^\circ$。射线十分强力，只需一发便可与作用范围平面内的所有物体相湮灭。不过，只要宇宙射线的一部分作用范围落到目标外，便会一直延续到宇宙尽头，贪婪地吞噬沿途的一切。指挥官当然不想危害到无辜文明，他想知道，在这 $n$ 中武器中选出 $k$ 种，共有多少种不同的摧毁飞行器的方式。

**【形式化题意】**

你有 $1\times x$（$x$ 为任意正整数）的矩形各无穷多个和一个 $2\times n$ 的网格，请求出恰好选择其中 $k$ 个矩形（可以选择相同的矩形）**不重不漏**地铺满整个网格的方案数。矩形可以旋转。

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

输入共包含一行两个正整数 $n,k$。

outputFormat:
输出到标准输出。

输出一行一个正整数，表示方案数，答案对 $998244353$ 取模。


title: 「HGOI-1」Binary search Ex

background:
此题为 [div.2 B](https://www.luogu.com.cn/problem/P8481) 的 extra sub，并非完整的题，总分为 $25$ 分（进入主题库后满分为 $100$ 分）。

$\text{bh1234666}$ 正在学习[二分查找](https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/10628618?fr=aladdin)。

description:
众所周知二分查找的 $\text{mid}$ 在计算时可以取 $\lfloor\dfrac{l+r}{2}\rfloor$ 或者 $\lceil\dfrac{l+r}{2}\rceil$,于是有选择困难症的 $\text{bh1234666}$ 同学在自己的二分查找代码中加入了随机化，每次随机选取其中的一个作为 $\textit{mid}$。

现在 $\text{bh1234666}$ 告诉你了他要找的数在序列内的下标（从 $0$ 开始，可以理解为在一个 $0\sim n-1$ 的升序序列内查询询问的数），他想知道在运气最好的情况下循环需要进行几次（即代码中 $\textit{cnt}$ 的可能的最终值的最小值）。

循环：
```cpp
int find(int *num,int x,int len)
{
	int l=0,r=len-1,mid,cnt=0,w;
	while(l<r)
	{
		cnt++;
		w=rand()%2;
		mid=(l+r+w)/2;
		if(num[mid]-w<x) l=mid+!w;
		else r=mid-w;
	}
	return mid;
}
```
递归：
```
int cnt;
int get(int *num,int x,int l,int r)
{
	if(l==r) return l;
	cnt++;
	int w=rand()%2;
	int mid=(l+r+w)/2;
	if(num[mid]-w<x) return get(num,x,mid+!w,r);
	else return get(num,x,l,mid-w);
}
int find(int *num,int x,int len)
{
	cnt=0;
	return get(num,x,0,len-1);
}
```
注：以上两代码完全等价。

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

第二行两个整数 $q$，$q_2$ 表示询问的次数，其中 $q$ 表示输入的询问次数，$q_2$ 表示由数据生成器生成的询问次数。

接下来一行 $q$ 个整数表示需要查询的数字。

接下来由数据生成器给出 $q_2$ 个询问（无需读入）。

outputFormat:
在总共的 $q+q_2$ 次询问中，记第 $i$
次询问的答案为 $ans_i$。

请你输出一个整数 $\sum\limits_{i=1}^{q+q_2}i\times ans_i$ 来表示答案。

hint:
### 样例 1 解释

还原后的输出：$3\  3\  3$。

找 $2$：

取 $[1,5]$。

取 $[1,3]$。

取 $[3,3]$（退出循环）。

### 样例 2 解释

还原后的输出：$3\ 4\ 3\  3\  4$。

#### 数据生成器

```cpp
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull sd = 111111111111111111ull, sd2, k = 1;
ull qu, n, ans;//qu表示每次询问的位置。
inline ull get_q(int i)
{
	sd = (sd2 ^ (sd2 >> 3)) + 998244353;
	return ((sd2 = sd ^ (sd << 37)) & k) + ((i & 1) ? 0 : (n - k - 1));
}
int q, q2;
void init()
{
	//Put your code here or not.
}
inline ull get_ans(ull x)
{
	//Put your code here.
}
int main()
{
	cin >> n;
	sd2 = n;
	while((k << 1) <= n + 1) k <<= 1;
	k -= 1;
	cin >> q >> q2;
	init();
	for(int i = 1; i <= q; i++)
	{
		cin >> qu;
		ans += get_ans(qu) * i;
	}
	for(int i = 1; i <= q2; i++)
	{
		qu = get_q(i);
		ans += get_ans(qu) * (i + q);
	}
	cout << ans << endl;
	return 0;
}
```

### 数据范围及约定

此题不进行捆绑测试，分数为各点分数之和。数据存在梯度，如下表所示。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{ExTest} & \textbf{Score} & \textbf{特殊限制} \cr\hline
1 & 5 & n,q_2 \le 2^{20}\cr\hline
2 & 5 & n \le 2^{30},q_2 \le 2\times 10^6 \cr\hline
3 & 5 & n \le 2^{40},q_2 \le 5 \times 10^6 \cr\hline
4 & 5 &  n \le 2^{50},q_2 \le  2\times 10^7 \cr\hline
5 & 5 &  n \le 2^{60},q_2 \le 2\times 10^8 \cr\hline
\end{array}
$$
对于 $100\%$ 的数据，$1 \le n \le 2^{60}$，$1 \le q+q_2 \le n$，$q \le 2^{20}$，$q_2 \le 2 \times 10^8$。

本题保证时限是 std 的两倍以上且使用给出的模板可以通过此题。


title: 「Wdoi-2」死亡之后愈发愉悦

background:
落樱缤纷春不待，如果错过了这次机会，可能得等到紫藤绽放的春夏之际才能赏花了。
但是两人依然无心在樱花树下席地而宴。

因为正体不明的灵体在两人面前倏现骤消的飘浮着。
后来才明白这些四处飘浮的正体不明灵体，既非普通幽灵，也不是前阵子出现的怨灵。
这些是神灵。本应超脱为神的灵体。

一般而言，神灵多半居住在神社里，其实它们是随处可见的没有固定型态的灵体。
这些神灵让她们困惑不已。

超乎常人的强烈人欲、想法、恐惧与情感，是神灵出现的原因。一般而言，神灵很少危害人类，如果没有强烈的欲望。例如祈求丰收，或是除厄避邪等，是不会产生神灵的……

小神灵指引着灵梦与魔理沙深入命莲寺的地底，与千年复苏的敌人交手。从命莲寺墓地到莲池中央的梦殿大祀庙，从彷徨的亡灵到极具传说色彩的圣德太子，从欲望加速到小小的欲望星空，一切都显得那么不可思议。

「死亡之后，才能得到更加绚烂的重生。」

description:
**【这是一道交互题】**

定义 $f(x)$ 表示严格大于 $x$ 的最小的完全平方数，定义 $g(x)$ 为小于等于 $x$ 的最大的完全平方数。例如，$f(1)=f(2)=g(4)=g(8)=4$。

一个正整数是“可爱”的，当且仅当 $x-g(x)<f(x)-x$，例如，$1,5,11$ 是可爱的正整数，而 $3,8,15$ 不是。

为了倾听小神灵的愿望，主角组需要向神子询问。小神灵有一个最喜欢的正整数 $a$，神子可以根据灵梦给出的 $x\quad(x\in[0,10^9])$，向小神灵询问，而小神灵只能回答她，$a+x$ 是不是可爱的正整数（$\text{cute number}$）。

请通过适当的询问找出 $a$。

inputFormat:
第一行有一个正整数 $T$，表示数据组数。每一组之间互相独立。

接下来，对于每一组数据，你将可以进行以下两种操作：

- $\verb!? x!$：询问 $a+x$ 是否是 $\text{cute number}$。要注意，$x$ 的值应当在 $[0,10^9]$ 以内。对于正确的询问，交互库会返回一个数字 $1$ 或者 $0$，表示 $a+x$ 是/不是 $\text{cute number}$。
- $\verb|! a|$：报告你发现的 $a$。如果你给出的 $a$ 正确，该组数据结束。注意：报告操作不计入询问操作的总次数。

如果你的询问次数超过了 $100$，或者 $x$ 不符合数据范围，或者你报告的 $a$ 不正确，交互库会返回一个数字 $-1$。此时你应当立即结束程序，否则可能发生不可预知的错误。

hint:
### 样例解释

样例当中的过程仅供参考。

样例当中，$a=114514$，是 $\text{cute number}$（因为 $338^2\le 114514 <339^2$，而 $114514-338^2=270<339^2-114514=407$）。

同样地，$a+0,a+1,a+2,a+3,a+10$ 均为 $\text{cute number}$。而 $a+100=114614$ 不是 $\text{cute number}$，因为 $338^2\le 114614 <339^2$，而 $114614-338^2=370\ge 339^2-114614=307$。

### 数据范围及约定

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|}\hline
\textbf{Subtask} & \bm{a\le } & \bm{T\le} & \textbf{特殊性质} & \textbf{分值}\\\hline
1 & 100 & 100 & - & 10\\\hline
3 & 10^9 & 2\times 10^3 & -  & 20\\\hline
2 & 10^{12} & 2\times 10^3 & \textbf{A}  & 30\\\hline
4 & 10^{12} & 2\times 10^3 & -  & 40\\\hline
\end{array}
$$

**特殊性质** $\textbf{A}$：保证 $a$ 是 $\text{cute number}$。

对于全部数据，保证 $1\le a\le 10^{12}$。你发起的询问当中，$x$ 的值应当在 $[0,10^9]$ 以内。

---

此外，你每个测试点的得分还与该测试点所有询问次数的最大值有关。具体而言，设某个测试点你询问操作一共进行了 $\text{max\_count}$ 次。

- 若 $\text{max\_count}< 64$，你将获得该测试点 $100\%$ 的分数；
- 若 $64\le \text{max\_count}< 81$，你将获得该测试点 $50\%$ 的分数；
- 若 $81\le \text{max\_count}< 100$，你将获得该测试点 $20\%$ 的分数；
- 若 $\text{max\_count}\ge 100$，你将不能获得该测试点的分数。


title: 「Wdoi-2」魔力的雷云

background:
道具会自己活动，本来温顺的妖怪突然大闹起来原来都是因为万宝槌的影响。
唆使小人的天邪鬼虽然最后逃走了，但因为真正使用万宝槌的是小人，所以灵梦决定对其进行监视。但是总感觉也没再有什么不良企图的样子。

但就在那时，天空再次出现了诡异的云团。
是与逆城出现之时一样的，魔力风暴。

“那不是我干的”，少名针妙丸这样解释着
到底，又是谁再次掀起了这样的风暴？
灵梦她们，为了调查清楚原因，再次冲进了风暴之中。

小人的末裔、逆转的城、为反抗而反抗的天邪鬼。
这背后又隐藏着什么呢。

description:
### 简要题意

$n$ 块磁铁排列成了一个环。每块磁铁都有磁力，用 $4^{a_i}$ 表示。相邻两块磁铁**磁力大小不同**。磁铁大小一致，长度均为 $1$ 单位长度。摆放时分为北极朝左和北极朝右。当两块磁铁互相吸引时，它们会紧紧靠拢，互相排斥时，记这两块磁铁的磁力为 $u$ 和 $v$，那么它们会相距 $u+v$ 单位长度。

目前已知**整个环**的长度（包括**每个**磁铁的长度，以及相邻磁铁之间的距离），记这个长度为 $d_0$ 个单位长度。对于第 $i$ 块磁铁，也已知若拿去这块磁铁，剩余磁铁组成的环的长度，记这个长度为 $d_i$ 个单位长度。

找到找到任意一种可能的磁铁排列方法满足这些已知的数据，（也要满足相邻两块磁铁磁力大小不同），并且可以决定所用磁铁的磁力。保证有解。

### 原始题意

在堀川雷鼓引发的雷暴中，一架架周围附带着电磁场的鼓正随着节奏摇摆着。在强大的电磁干扰下，巫女和魔法使与地面失去了联系。

这些尺寸完全相同（可以视作为单位长度 $1$）的带有磁力的鼓一共有 $n$ 架，它们排列成了一个环。为了让弹幕美观，第 $i$ 架鼓上带有的磁力是 $4^{a_i}$，而且相邻两架鼓带有的磁力大小不同。

每一架鼓都有磁性上的南北两极，而且在摆放的时候有北极朝左和北极朝右的两种情况。若两架鼓相互吸引它们会紧紧靠拢；而若它们相互排斥，这两架鼓之间的距离就是它们的磁力之和的单位长度。

灵梦记录下了整个环的长度 $d_0$，这包括了每架鼓的长度和相邻的鼓之间的距离，而魔理沙正在使用自己的火力击碎这些鼓。然而这些鼓的质量非常皮实，魔理沙一次只能击碎一个鼓，随后堀川雷鼓会用一个尺寸和磁力完全一致的鼓替代这个被击碎的鼓。但是在击碎第 $i$ 架鼓的时候，受到磁力的作用环的长度会发生变化，魔理沙会记录此时剩余的鼓组成的环的长度 $d_i$（假设磁力的作用是瞬间完成的）。

在战斗的间隙，灵梦和魔理沙希望通过她们记录下的数据，找到任意一种鼓的排布情况满足这些数据。为了降低难度，她们可以自由决定每架鼓上的磁力多少。数据保证有解。

尽快解出鼓的分布，从而结束这场异变吧！

inputFormat:
- 第一行有一个整数 $n$，表示磁铁的总个数。
- 接下来 $1$ 行一个整数，表示 $d_0$。
- 接下来 $n$ 行每行一个整数，其中第 $i$ 行的整数表示 $d_i$。

outputFormat: - 输出共 $n$ 行。第 $i$ 行有两个整数 $f_i,a_i$，分别表示磁铁的方向与磁力。若 $f_i=0$ 则表示北极向左，否则若 $f_i=1$ 则表示北极向右。

hint:
### 样例 1 解释

一种合法的方案中，$c=\{1,1,0,1\}$，$a=\{1,0,1,0\}$。以下是这种方案的图解。

初始时磁铁的状态如下图所示，磁铁上方的数字是它的磁力大小（即 $4^{a_i}$ 的值），磁铁上标记的 $\textsf{N/S}$ 是它的磁极。由于笔者能力有限，无法还原出环形，只能用这种传送门的方式扭曲时空了。

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

容易发现，总长度为 $14$。

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

拿掉第一块磁铁后的情形如图所示。容易发现，总长度为 $13$。

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

拿掉第二块磁铁后的情形如图所示。由于缺少了第二块磁铁的阻挡，第一块和第三块磁铁直接相邻，产生了更大的间距。可以发现，总长度为 $16$。

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

拿掉第三块磁铁后的情形如图所示。值得注意的是，所有磁铁北极方向相同，于是直接互相接触，总长度为 $3$。

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

拿掉第四块磁铁后的情形如图所示。由于第三块和第一块磁铁直接相邻（因为是形成了环。在图上则是扭曲后的空间里相邻），因此形成了这种模样。总长度为 $16$。

### 数据范围及约定

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值} \\\hline
1 & 10 & - & 10 \\\hline
2 & 10^5 & - & 30 \\\hline
3 & 10^6 & \text{A} & 5 \\\hline
4 & 10^6 & - & 55 \\\hline
\end{array}$$

**特殊性质** $\textbf{A}$：保证存在一种方案，所有磁铁的方向一致。

对于所有数据，保证 $1\leq n\leq 1\times10^6$，存在至少一种合法方案。此外，保证 $d_i< 2^{63}$，你构造的 $a_i$ 大小应该在 $[0,10^9]$。


title: 「DTOI-2」星之界

background: >天仙开碧落，银界失黄昏。

description:
夜空中的星星组成了一个序列 $a$，序列中的第 $i$ 个数表示第 $i$ 颗星星的亮度。

现在，作为星之眷顾者的你，拥有两种方式来操作星星。

- 操作一：输入格式为 $\texttt{1 l r x y}$，表示将 $[l,r]$ 内所有亮为 $x$ 的星星的亮度改为 $y$。

- 操作二：输入格式为 $\texttt{2 l r}$，表示输出 $ \prod\limits_{i = l}^{r} C_{\sum_{j = l}^{i}a_j}^{a_i}\ \bmod 998244353 $ 的值。

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

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

接下来 $q$ 行，每行一个操作，格式由上方给出。

outputFormat: 对于每个 $2$ 操作，输出所求值。


title: [语言月赛202209] 口算练习

type: B

description:
在课堂上，同学们经常需要进行口算练习。

老师出了一道练习题：计算 $\bigg\lfloor \dfrac{x}{y} \bigg\rfloor$ 的值，请你问答这个问题。

其中 $\lfloor a \rfloor$ 代表不超过 $a$ 的最大整数，如 $\lfloor 1.1 \rfloor = 1, \lfloor 4 \rfloor = 4, \lfloor -2.2 \rfloor = -3$。

**提示：**

在 C++ 中，int 类型变量 x, y，语句 `x/y` 计算得到的是 $\dfrac{x}{y}$ 向零取整的值。例如：

```cpp
int x = -3, y = 2;
cout << x / y;
```

上面的代码会输出 -1。

`floor` 函数，其功能是“向下取整”，比如：`floor(-1.5) = -2.0`

inputFormat: 输入共一行两个整数 $x,y$，保证 $y \neq 0$。

outputFormat: 输出一行一个整数，代表 $\bigg\lfloor \dfrac{x}{y} \bigg\rfloor$。

hint:
对于 $20\%$ 的数据，$y = 1$;
对于另外 $20\%$ 的数据，保证 $x = ky,k \in \Z$;
对于另外 $20\%$ 的数据，保证 $x \times y >0 $;
对于 $100\%$ 的数据，$-10^3 \le x, y \le 10^3, y \neq 0$。

**提示：**

如果无法完成本题，建议先完成后面的比赛题。


title: [语言月赛202209] 公园门票

description:
小 A 一家人一起来逛公园，门票价目表如下：

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

小 A 家里共有 $x$ 个成人，$y$ 个儿童，请问**至少**需要花费多少钱购买门票。

inputFormat: 共一行，包含两个数字 $x$ 和 $y$，表示小 A 家里共有 $x$ 名成人，$y$ 名儿童。

outputFormat: 共一行，包含一个数字，表示**至少**需要花费多少钱购买门票。

hint:
### 输入输出样例 1 解释

1 名成人 + 1 名儿童可以购买一大一小套票，需花费 $90$ 元。

### 输入输出样例 2 解释

2 名成人 + 1 名儿童可以购买一张一大一小套票和一张成人票，需花费 $90 + 60 =150$ 元。

### 数据规模与约定

对于 $20\%$ 的数据，保证 $y=0$；
对于另外 $20\%$ 的数据，保证 $x=0$；
对于另外 $20\%$ 的数据，保证 $x=y$；
对于 $100\%$ 的数据，保证 $0\le x,y \le 100$。


title: [语言月赛202209] 课程QQ群

description:
报名洛谷网校课程的学员可以得到加入课程 QQ 群的验证码。

某期课程设定的验证码为数字 $k$，现在一共有 $n$ 个人申请加入 QQ 群，第 $i$ 个人提供的验证码为 $a_i$。

现在请你担任课程 QQ 群的管理员，请问你一共应该通过多少人的入群申请。

inputFormat:
输入的第一行为两个整数 $n,k$。

接下来 $n$ 行，每行一个整数，代表一个人通过的入群验证码。

outputFormat: 输出一行一个整数，代表应该通过加群申请的人数。

hint:
对于 $30\%$ 的数据，所有人提供的验证码均正确。
对于 $100\%$ 的数据，$1 \le n \le 5000, 1 \le a_i,k \le 10^4$。


title: [语言月赛202209] 集卡

background: 小 A 最近迷上了集卡。

description:
小 A 最近买了 $T$ 次卡牌，每次买了 $n$ 张（注意，不同次买的卡牌数量不一定相同）。每张卡都有一个**数字**编号，如果编号是 0 则代表抽到了隐藏款。

小 A 想**分别**知道每次购买的卡牌中，是否抽到了隐藏款。如果抽到了则输出 `yes`，否则输出 `no`。

inputFormat:
第一行，一个整数 $T$，表示小 A 最近买了 $T$ 次卡牌。

接下来包含 $2T$ 行数据，代表了小 A 这 $T$ 次购买卡牌的情况。

对于每次购买卡牌的情况，共包含两行输入。

第一行为一个整数 $n$，表示购买了 $n$ 张卡牌。
第二行包含 $n$ 个整数，表示本次购买的 $n$ 张卡牌的数字编号。

**提示：** 如果无法理解输入格式，可以先阅读下方的输入输出样例，再结合样例来理解输入格式。

outputFormat: 共 $T$ 行，每行一个 `yes` 或者 `no`，表示是否抽到了隐藏款。如果抽到了则输出 `yes`，否则输出 `no`。

hint:
对于 $20\%$ 的数据，满足 $T=1,0\le n\le 10$；
对于 $40\%$ 的数据，满足 $T=1$；
对于 $70\%$ 的数据，满足 $T\le 100,0\le n\le 1000$；
对于 $100\%$ 的数据，满足 $T\le 100,0\le n \le 10^4$，且卡牌的数字编号在 C++ 中的 `int` 范围内。


title: [语言月赛202209] 排排队

description:
幼儿园里有 $n$ 个小朋友，每个小朋友有一个学号。

老师要求：学号是奇数的小朋友站一排，学号是偶数的小朋友站一排。

**提示**：

奇数：个位为 $1,3,5,7,9$ 的数字，满足除以 $2$ 的余数为 $1$。

偶数：个位为 $0,2,4,6,8$ 的数字，满足除以 $2$ 的余数为 $0$。

inputFormat:
共两行，第一行一个数字 $n$，表示有 $n$ 个小朋友。

第二行共 $n$ 个数字，其中第 $i$ 个数字 $a_i$ 表示第 $i$ 个小朋友的学号。

outputFormat:
共两行，第一行一些数字，表示学号为奇数的小朋友的学号，按照输入的顺序输出。即，如果一个数字输入的时候在前，那么输出的时候也应当在前。

第二行一些数字，表示学号为偶数的小朋友的学号，按照输入的顺序输出。

保证小朋友的学号既有奇数，又有偶数。


title: [语言月赛202209] 山峰

description:
洛咕公司可以被分为 $n$ 行 $m$ 列的土地，第 $i$ 行第 $j$ 列的土地初始海拔为 $a_{i,j}$。行号和列号均从 $1$ 开始编号。

在漫长的岁月中，一共发生了 $T$ 次地理变迁。每次地理变迁，两块土地的海拔会发生交换。

如果有一块土地，比上下左右直接相邻的土地海拔都高，我们称其为一个山峰。

Berland 王国的首领想要知道，在所有地理变迁完成后，王国一共有多少山峰，它们的坐标分别为多少。

例如：$n=m=3$，海拔高度如下所示

$$1 \ \ 2 \ \ 3 \\
1 \ \ 4 \ \ 2\\
1 \ \ 1 \ \ 2
$$

其中，$(1,3),(2,2)$ 是山峰。

inputFormat:
输入的第一行为两个整数 $n,m$，分别代表行数与列数。

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个整数代表 $a_{i,j}$。

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

接下来 $T$ 行，每行四个整数 $x_1,y_1,x_2,y_2$，代表 $x_1$ 行 $y_1$ 列的土地与 $x_2$ 行 $y_2$ 列的土地发生了地理变迁。

outputFormat:
输出的第一行为一个整数，代表地理变迁后山峰的数量 $k$。

接下来 $k$ 行，每行两个整数 $x,y$，代表一座山峰在第 $x$ 行第 $y$ 列。

你可以以任意顺序输出山峰的坐标。


title: [语言月赛202209] Luogu Academic

description:
七海在 LA 群中游走，获得了一个由英文小写字符组成的字符串 $S$。

七海想要知道，子串 `luogu` 在其中出现了多少次。

**提示：**  一个字符串中，任意**连续**的字符构成的子字符串称为子串。

例如，字符串 `abc` 一共包含 7 个子串，分别为：空串（不包含任何字符)，`a`，`ab`，`abc`，`b`，`bc`，`c`。注意，字符串 `ac` **不是** `abc` 的子串。

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

outputFormat: 输出一行一个整数，代表子串 `luogu` 在字符串 $S$ 中出现的次数。

hint:
对于 $30\%$ 的数据，$|S| < 5$；
对于另外 $30\%$ 的数据，字符串 $S$ 仅由以下四个字符 `l,u,o,g` 组成；
对于 $100\%$ 的数据，$1 \le |S| \le 10^6$，保证字符串仅由小写英文字母组成。


title: [语言月赛202209] 零食售卖点

description:
洛咕公司有一条无限长的大道，可以被视为一个数轴。在这条大道上，一共有 $k$ 个零食售卖点，第 $i$ 个零食售卖点的坐标为 $a_i$。

Aya 非常热爱零食，他想知道，**相邻**两个零食售卖点之间的距离最大为多少。第 $i$ 个零食售卖点和第 $j$ 个零食售卖点之间的距离为 $|a_i-a_j|$。

$|x|$ 代表 $x$ 的绝对值。即，当 $x\ge0$，$|x|=x$；当 $x<0$，$|x|=-x$。例如，$|4|=4,|0|=0,|-1|=1$。

inputFormat:
输入的第一行为一个整数 $k$。

输入的第二行为 $k$ 个整数，第 $i$ 个为 $a_i$。

**请注意，$a_i$ 不保证按照升序给出。**

outputFormat: 输出一行一个整数，代表**相邻**两个零食售卖点之间的距离最大为多少。

hint:
### 输入输出样例解释

共 $4$ 个零食售卖点，按数轴上的顺序依次为 $1,3,5,20$，相邻两个零食售卖点的距离依次为 $2,2,15$，答案为 $15$。

### 数据规模与约定

对于 $30\%$ 的数据，$k=2$；
对于另外 $30\%$ 的数据，$a_i$ 升序给出；
对于 $100\%$ 的数据，$2 \le k \le 5000, 1 \le a_i \le 10^7$。


title: 「Wdoi-2」夜空中的 UFO 恋曲

background:
土地变得泥泞，曾被寒冰覆盖的大地上，万物开始复苏。
覆盖着幻想乡的少量积雪，封住了在这个冬天苏醒的地灵们，
也足以使妖精们的活动变得迟钝。这样安稳沉睡的季节也即将告一段落。

博丽神社的巫女博丽灵梦从居住在森林里的魔法使那儿听到了一个传闻说，有人目击到云的缝隙中有不可思议的船在空中飞行。

——船中空空如也。
曾在船中的金银财宝早已散佚，剩下的东西也散发着
陈年霉臭。
仅凭凛冽春风，仍不足以将那霉味吹散。
但是，只有那位大人留下的宝物，即使变成碎片也不会失去威力吧。

只是那些碎片依旧以不可思议不可理解的形态飘在幻想乡各处，对扑簌迷离的真相加盖了疑问的迷雾。

貌似有很深的原因。我们不知道的某种东西，在酝酿着什么。

description:
### 简要题意
给定正整数 $a,b,c$，满足 $a,b,c\textcolor{red} > 1$。对于函数 $f_k$，给出如下定义：

$$f_{k}(x)=\begin{cases}
x^{2c}\oplus c & k = 1\\
f_{k-1}(x^{2c}\oplus c) & k > 1
\end{cases}$$

其中 $\oplus$ 表示二进制下的异或操作。

现在要求计算出 $\operatorname{lowbit}(f_{b}(a))$。其中 $\operatorname{lowbit}(x)$ 表示二进制下 $x$ 最右侧的 $1$ 所在位置对应的二进制值，例如：

$$\operatorname{lowbit}(101101\cdots 10\textcolor{red}1\underbrace{00\cdots000}_{k\text{ 个 }0})=2^k$$

特别地，若 $x=0$，则 $\operatorname{lowbit}(x)=0$。
### 原始题意
为了去除碎片上附加的「不明的因子」，主角组需要破开[【正体不明】](https://www.luogu.com.cn/user/35891)附加的法术。

不明的因子是一种小蛇一般的飞行物，在不同人的眼中具有不同的形象。
当有人看到它时，会按照自己的常识，把它看成自己认识的、认为合理的东西。

碎片的表面有一个由红蓝组成的长串，妖怪贤者发现，若将红看作 $0$，蓝看作 $1$，它就成了一个二进制数字 $x$。
碎片上一共有 $k$ 层不明因子，每破开一层都会使数字 $x$ 变为 $x^{2c}\oplus c$（其中 $\oplus$ 表示二进制下的异或操作）。
为了破解法术，主角组需要根据给定的常数 $c$，初始值 $a$ 和层数 $k=b$ 先破开所有的不明因子，然后计算剩下的数字所代表的串中， 最右侧的「蓝色」所在位置对应的二进制值。

经过主角们一定的分析，她们发现了 $a,b,c\textcolor{red} > 1$。

紫把[式神计算机](https://www.luogu.com.cn/user/149196)搬了出来就回去睡觉了，把编制程序的任务交给了可怜的金发小女孩。你的任务就是帮她完成程序的编制，彻底肃清异变的影响，找回丢失的记忆。

inputFormat:
第一行有三个正整数 $a,b,c$，含义如题面所示。

再次强调，$a,b,c\textcolor{red} > 1$。


title: [语言月赛202208] 你几岁了

description: 小 A 今年 $x$ 岁。他刚学了英语，想告诉其他人：`I am x years old.`

inputFormat: 输入一个数 $x(2\le x \le 100)$，代表小 A 的年龄。

outputFormat: 输出一句话。

hint: 完成的程序的编写后，请记得在 `Dev-c++` 上编译运行，然后测试样例，比较自己的输出和样例输出是不是**一字不差**。


title: [语言月赛202208] 大小比较

description: 给出整数 $a,b$，若 $a \le b$，输出 `YE5`，否则输出 `N0`（第二个字符为阿拉伯数字）。

inputFormat: 输入一行两个整数 $a,b$。

outputFormat: 输出一行，为你的答案。


title: [语言月赛202208] 求和

description:
输入一个整数 $n(1\le n \le 10^7)$，每行输出一个数，表示数字 $1$ 到 $i$ 的和。

比如，当 $n=5$ 时，

第 1 行输出一个数字 1；

第 2 行输出数字 3，因为 `1 + 2 = 3`；

第 3 行输出数字 6，因为 `1 + 2 + 3 = 6`；

第 4 行输出数字 10，因为 `1 + 2 + 3 + 4 = 10`；

第 5 行输出数字 15，因为 `1 + 2 + 3 + 4 + 5 = 15`。

inputFormat: 输入一个数 $n(1\le n \le 10^7)$。

outputFormat:
输出共 $n(1\le n \le 10^7)$ 行，每行一个整数。

第 $i$ 行输出的数，表示数字 1 到 i 的和。

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

对于 $60\%$ 的数据，$1\le n \le 10^4$。

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

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

**提示：**

使用 ` cout << endl; ` 输出换行会导致 TLE（超过时间限制）。

请使用 `cout << "\n"; ` 或者是 `printf("\n");` 输出换行。

$1+2+3+\dots+10000000$ 的值超出了 `int` 类型可以存储的最大值。


title: [语言月赛202208] 数组调整

description:
给出一个长度为 $n$ 的数组，第 $i$ 个数为 $a_i$。

为了调整这个数组，需要将第 $k$ 个数改变为 $-a_k$。

请你求出调整后的数组中所有数的和。

inputFormat:
输入共两行。

输入的第一行为两个整数 $n,k$。

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

outputFormat: 输出一行一个整数，代表调整后的数组中所有数的和。

hint:
### 输入输出样例 1 解释

调整后的数组为 `1 2 3 4 5 6 -7 8 9 10`，和为 41。

### 输入输出样例 2 解释

调整后的数组为 `1 -999 4 3 2`，和为 -989。

### 数据规模与约定

对于 $5\%$ 的数据，为输入输出样例 1。

对于另外 $40\%$ 的数据，需要调整位置上的数 $a_k=0$。

对于另外 $20\%$ 的数据，$k = 1$。

对于 $100\%$ 的数据，$1 \le k \le n, n \le 10^6,0 \le a_i \le 10^9$。


title: [语言月赛202208] 渡荆门送别

background:
> 渡荆门送别
>
>李白
>
>渡远荆门外，来从楚国游。
>
>山随平野尽，江入大荒流。
>
>月下飞天镜，云生结海楼。
>
> 仍怜故乡水，万里送行舟。

description:
李白喜欢飞，也喜欢天鹅。

现在给出一排共 $n$ 只鹅的身高，李白想知道最高的鹅比其他所有鹅高多少、最矮的鹅比其他所有鹅矮多少。

请输出这两行信息。

inputFormat:
输入共两行。

第一行一个整数 $n$ 表示鹅的数目。

第二行共 $n$ 个整数 $a_i(i=1,2,3...n)$，表示第 $i$ 只鹅的身高。

outputFormat:
输出共两行。

第一行共 $n$ 个空格隔开的整数，第 $i$ 个整数表示序列中第 $i$ 只鹅比最高的那只鹅要矮多少。

第二行共 $n$ 个空格隔开的整数，第 $i$ 个整数表示序列中第 $i$ 只鹅比最矮的那只鹅要高多少。

hint:
李白一共有 $6$ 只鹅，最高的一只身高为 $8$，最矮的一只身高为 $2$，然后分别作为被减数和减数参与身高差计算可得结果。

对于 $30\%$ 数据，保证 $0\leq a_i\leq 30,1\leq n\leq 20$。

对于 $100\%$ 数据，保证 $0\leq a_i \leq 10^{18},1\leq n\leq 10^6$ 。


title: [语言月赛202208] 俊俏地鼠的远亲

background: 地鼠十分想要找到自己远方的亲戚！

description:
非洲同胞永远是我们的好朋友。在东非草原上，一共有 $n\times m$ 只地鼠，他们生活的窝排列成 $n\times m$ 网格型。

其中，每只地鼠都有一个特征值 $b_{i,j}$，经调查，我们认为特征值相同的地鼠一定有某种血缘关系。例如，两只地鼠分别生活在第二行第三列、第五行第六列。若 $b_{2,3}=b_{5,6}$，那么我们认为这两只地鼠是亲戚。

现在，给出这个 $n\times m$ 只地鼠的位置，需要对**每只**地鼠求出离自己距离**最远**的亲戚的距离是多少。

注意，假设两只地鼠分别位于第 $i$ 行第 $j$ 列和第 $a$ 行第 $b$ 列，则它们之间的距离为 $(i-a)^2+(b-j)^2$ 。

inputFormat:
第一行两个正整数 $n,m$，表示地鼠家族的行数和列数。

第 $2\sim n+1$ 行给出一张大小为 $n\times m$ 的数表 $\{b_{n,m}\}$，其中 $b_{i,j}$ 表示第 $i$ 行 $j$ 列上地鼠的特征值。

outputFormat:
输出同样是一个 $n\times m$ 的数表，其中每个元素表示距自己最远的亲戚的距离是多少。

特别的，如果有某只地鼠没有远亲，则输出 $0$ 。


title: [语言月赛202208] 影子字符串

background: 众所周知，影子并不是实际物体。

description:
给出多个字符串（数目未知），**每行**一个。

其中有可能会有重复的字符串，而我们认为在这些字符串中，较靠后出现的都是靠前出现的字符串的“**影子**”。

例如，

```plain
abc
def
abc
abc
abc
```

我们在第 $1,3,4,5$ 行都出现了字符串 `abc`，那么 $3,4,5$ 行的字符串会被称为“影子字符串”。

现在要求把所有的**非影子字符串**都按照**行号从小到大**依次拼接为一个长串并输出。

inputFormat:
多个字符串，每行一个，含义见题目描述。

**注意：输入结尾以字符串 `0` 结束（即一行里仅有一个 `0`）。**

outputFormat: 共一行，表示所有非影子字符串按照行号从小到大依次拼接成的一个长串。

hint:
对于 $20\%$ 的数据，无重复字符串。

对于 $100\%$ 的数据， $1\leq n\leq 500$，字符串总长度不超过 $50000$ ，字符集为全部的小写字母、数字、 `.` 、`!` 和 `&`。

也就是说，每个字符串中只包含小写字母、数字、 `.` 、`!` 和 `&`，不包含空格等特殊符号。


title: [语言月赛202208] 天天爱跑步

background: 洛咕公司开发了一款新的养成类游戏《天天爱跑步》。

description:
为了推广《天天爱跑步》，洛咕公司开发了活跃值系统，同其他游戏一样，连续签到天数越多，每次签到获得的活跃值也就越多。但只要一天不签到，连续天数就要清零。

当连续签到天数达到以下天数时，活跃值奖励将发生如下变化。

- $1$ 天：由 $0$ 变为 $v_1$
- $3$ 天：由 $v_1$ 变为 $v_3$
- $7$ 天：由 $v_3$ 变为 $v_7$
- $30$ 天：由 $v_7$ 变为 $v_{30}$
- $120$ 天：由 $v_{30}$ 变为 $v_{120}$
- $365$ 天：由 $v_{120}$ 变为 $v_{365}$
- $366$ 天或更多天数：均为 $v_{365}$

例如，以下为某游戏玩家连续签到情况及活跃值奖励情况，有助于进一步理解题意。

| 日期 | 是否签到 | 连续签到天数 | 当天获得活跃值奖励 |
| :--: | :--: | :--: | :--: |
| 8 月 8 日 | 是 | $1$ | $v_1$ |
| 8 月 9 日 | 是 | $2$ | $v_1$ |
| 8 月 10 日 | 是 | $3$ | $v_3$ |
| 8 月 11 日 | 是 | $4$ | $v_3$ |
| 8 月 12 日 | 否 | $0$ | $0$ |
| 8 月 13 日 | 是 | $1$ | $v_1$ |
| 8 月 14 日 | 是 | $2$ | $v_1$ |
| 8 月 15 日 | 是 | $3$ | $v_3$ |

即，签到系统按照如下顺序处理奖励：

 1. 累计连续签到天数
 2. 根据规则确定当日奖励的活跃值
 3. 发放活跃值

现在给出 **超高校级的游戏玩家 $\lfloor$七海千秋$\rceil$** 连续 $n$ 天的签到情况，请你求出这 $n$ 天七海千秋获得的活跃值奖励一共为多少。

连续签到天数从 $0$ 开始计算。

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

输入的第一行为一个正整数 $n$，代表 $\lfloor$七海千秋$\rceil$ 游戏的天数。

输入的第二行为六个正整数，分别为 $v_1,v_3,v_7,v_{30},v_{120},v_{365}$，含义如题。

接下来的 $n$ 行，每行一个整数 $1$ 或 $0$。其中第 $i$ 行为 $1$ 表示第 $i$ 天 $\lfloor$七海千秋$\rceil$ 签到了，输入为 $0$ 表示第 $i$ 天 $\lfloor$七海千秋$\rceil$ 没有签到。

outputFormat: 输出一行一个整数，代表 $\lfloor$七海千秋$\rceil$ $n$ 天签到所获得的活跃值。


title: 「SvR-2」1+2=3

description:
你有一些木棒，每个木棒左边有一个数，右边有一个数，数只有 $0,1,2$，你要将所有木棒拼起来，使相邻的数和为 $3$ 的对数最大。

例如，$1\text{ - }2$ 和 $1\text{ - }0$ 两个木棒，如果按 $1\text{ - }0,1\text{ - }2$ 这样拼，相邻的数和为 $3$ 的对数是 $0$；而按 $1\text{ - }{\underline\color{red}\textbf2},{\underline\color{red}\textbf1}\text{ - }0$ 这样拼相邻的数和为 $3$ 的对数是 $1$，因为 $2+1=3$。

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

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

对于每组数据，一行 $9$ 个非负整数，分别表示 $0\text{ - }0,0\text{ - }1,0\text{ - }2,1\text{ - }0,1\text{ - }1,1\text{ - }2,2\text{ - }0,2\text{ - }1,2\text{ - }2$ 型木棒的个数。

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

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

对于全部数据，保证 $1\le T\le 10^5$，记 $a_{i,j}$ 表示 $i\text-j$ 木棒的个数，保证 $0\le a_{i,j}\le 10^9$。

**本题自动开启捆绑测试和 O2 优化。**

记 $sum$ 表示一个测试点中所有数据的所有 $a_{i,j}$ 之和。

| Subtask | $T$ | $sum$ | 特殊性质 |分值 |
| :------: | :------: | :------: | :------: | :------: |
| $1$ | $1 \leq T \leq 10$ | $1\le sum\le 10$ |无| $10 \operatorname{pts}$ |
| $2$ | $1 \leq T \leq 50$ | $1\le sum\le 80$ | 无|$20 \operatorname{pts}$ |
| $3$ | 无特殊限制 | 无特殊限制 |A| $15\operatorname{pts}$ |
| $4$ | 无特殊限制 | 无特殊限制 |B| $20 \operatorname{pts}$ |
| $5$ | $1\le T\le 1000$ | 无特殊限制 |C| $20 \operatorname{pts}$ |
| $6$ | 无特殊限制 | 无特殊限制 |无| $15 \operatorname{pts}$ |

特殊性质 A：$a_{i,j}$ 在 $[0,10^9]$ 中均匀随机生成。

特殊性质 B：所有 $a_{i,j}>0$。

特殊性质 C：所有 $a_{i,j}\le 100$。


title: multiset

background: ZHY 有很多集合。集合多了，也就成了多重集合。

description:
给定一个 **多重集合**（集合中元素可重复）$S$，请求出一个最大的多重集合 $T$，满足 $T$ 是 $S$ 的一个 **真子集**，且对于 $T$ 中的每一个元素 $i$，要么 $i$ 在 $S$ 中没有前驱，要么 $i$ 在 $S$ 中的前驱 $\in T$。若有多个大小相同的集合满足条件，则 $T$ 为所有元素之和最大的一个。请输出 $T$ 的大小和其中元素之和。

---

一个数 $x$ 在一个集合 $S$ 中的前驱的定义为所有在 $S$ 中且 $<x$ 的元素 $y$ 的最大值。

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

第二行 $n$ 个正整数，表示 $S$ 中的元素。

outputFormat: 一行两个整数。第一个数表示 $T$ 的大小，第二个数表示 $T$ 的所有元素之和。


title: 「HGOI-1」PMTD

background: $\text{uuku}$ 在学习[四则运算](https://baike.baidu.com/item/%E5%9B%9B%E5%88%99%E8%BF%90%E7%AE%97/5337481?fr=aladdin)！

description:
为了验证 $\text{uuku}$ 学习成果，$\text{bh1234666}$ 给出一个长为 $n$ 整数序列 $a_i$。并让 $\text{uuku}$ 给这个序列进行 $m$ 次操作。

每次操作可以任意选择序列中一个数 $a_i$，令 $a_i$ 变成 $a_i+2$，$a_i-2$，$a_i\times 2$，$\lfloor\frac{a_i}{2}\rfloor$ 这四个结果中的一个。

$\text{bh1234666}$ 希望 $m$ 次操作后，整个序列的极差（最大值减最小值）最大。

显然 $\text{uuku}$ 没有认真学习，所以他希望你来帮他回答这个问题。

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

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

outputFormat: 共一行一个整数，表示最大的极差。

hint:
#### 样例解释

第一步操作：将 $1$ 加上 $2$ 得到 $3$。

第二步操作：将 $3$ 乘以 $2$ 得到 $6$。

极差为 $6-0=6$。

#### 数据范围

本题采用**捆绑测试**，共有 $2$ 个 $\text{subtask}$，最终分数为所有 $\text{subtask}$ 分数之和。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{Task} & \textbf{Score} & \textbf{特殊限制} \cr\hline
1 & 40 & n \le 5,m \le 5 \cr\hline
2 & 60 &  \cr\hline
\end{array}
$$

对于 $100\%$ 的数据，$2 \le n \le 10^6$，$1 \le m \le 10$，$0 \le a_i \le 10^9$。


title: 「GLR-R4」立夏

background:
  「芳菲歇去何须恨，夏木阴阴正可人」

---

  和老 V 说好的赛后团建终于举行啦！

  难得和学弟学妹们在一起，天依和阿绫自然不会错过这次良好的机会，更不会放过早就想 rua 的狐狸座的耳朵！

  “那个……天依……”

  天依和腿上的狐狸座同时歪过头看向某个叫阿绫的醋坛子。

  “绫姐绫姐，疼！”

  于是在天依给小狐狸扎头发的时候，小狐狸的耳朵已经被揉蔫啦！

---

  **立夏** 「三步并两步　就发现　如期而至的透明夏日章节」

description:
  **本题提供简要题意。**

  天依给狐狸座准备的纱质发绳由**白色**和**紫色**的小格子组成，相同大小的小格子连成了一条足够长的带子。我们不妨把天依的手正捏着的位置标为第 $0$ 格，向右依次是第 $1$ 格、第 $2$ 格，等等；向左依次是第 $-1$ 格，第 $-2$ 格，等等；天依将发绳对折起来，此时第 $-1$ 格将于第 $1$ 格重合，第 $-2$ 格将于第 $2$ 格重合……第 $-k$ 格将与第 $k$ 格重合（$k$ 为正整数）。**特别地**，我们认为第 $0$ 格保持原样，没有和其他格子重合，也没有和自己重合。

  由于发绳是半透光的，所以对折起来的发绳上的格子将可能出现三种颜色：**白色**、**浅紫色**和**深紫色**。两个白色的格子重合呈现白色，一个紫色和一个白色的格子重合呈现浅紫色，两个紫色的格子重合呈现深紫色。**特别地**，若第 $0$ 格原来为白色，则折叠后也为白色，否则第 $0$ 格原来为紫色，则折叠后为浅紫色。

  如果把白色记作 $0$，浅紫色记作 $1$，深紫色记作 $2$，以折叠后的第 $0$ 格作为最低位，依次将每个格子颜色对应的数字记录下来，我们将得到一个长长的三进制数整数，记为 $x$。现在，天依告诉你了 $x$ 的值，你能算出**对折之前的发绳**有多少种不同的样式吗？称两条发绳颜色不同，当且仅当存在一个整数 $k$，使得两条发绳的第 $k$ 格上的颜色不相同。

  发绳款式丰富多样，你需要对 $T$ 个 $x$ 分别求出答案。

### 简要题意

  对于一个包含整数的集合 $S$，定义其权值为 $\sum_{a\in S}3^{|a|}$（即，枚举 $S$ 的元素 $a$，计算 $3^{|a|}$ 并求和）。给出非负整数 $x$，计算有多少个集合的权值为 $x$。注意集合不能包含重复元素。

inputFormat:
第一行一个整数 $T$，表示你需要分别处理的数据组数。

接下来 $T$ 行，每行一个整数 $x$，表示对折后发绳颜色所对应的三进制数。注意 $x$ 是以十进制输入的。

outputFormat: 输出 $T$ 行，第 $i$ 行一个整数，表示给出的第 $i$ 个 $x$ 对应的方案数。


title: 「HGOI-1」Build

background: 一次旅行，$\text{uuku}$ 到了一个奇怪的小镇。

description:
这个小镇将要和周围的其他小镇一共 $n$ 个小镇，一起修建一个能**连通**这 $n$ 个小镇，有 $m$ 条高速公路的交通网。其中每条高速公路都将会连接**不同的两个小镇**，即不存在一条高速公路的起点和终点相同。

但高速公路的修建费用是很高的，所以镇长们一致决定将共同承担高速公路的费用，所以他们希望修建的**总费用最小**。

而且由于不同小镇的基础设施建设情况不同，所以每个小镇在修建的费用也不同。经过协商，每条高速公路将由其所连接的两个小镇共同施工。每个小镇负责一半路程。为了同时结束整个施工过程，显然将会有小镇同时进行多条道路的施工，而施工的道路数量越多，所需要花费的价钱就越多。

经过计算，每个小镇施工的花费可以用函数表示，及对于小镇 $i$，有三个参数 $a_i$，$b_i$，$c_i$。对于 $i$ 小镇来说在修建其第 $j$ 条高速时，**这条**高速所需要的花费为 $a_ij^2+b_ij+c_i$。

现在，这些镇长想要 $\text{uuku}$ 给他们提供一个满足要求的**建造方案**，使**总价格最小**。

当然，$\text{uuku}$ 将这个问题交给了你。

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

接下来 $n$ 行，每行三个整数 $a_i$，$b_i$，$c_i$。

outputFormat:
共 $m+1$ 行

第一行一个整数表示最小价格。

接下来 $m$ 行，每行两个整数 $u$，$v$，表示你提供的方案中的一条边。

hint:
#### 数据范围
本题采用**捆绑测试**，共有 $6$ 个 $\text{subtask}$，最终分数为所有 $\text{subtask}$ 分数之和。
$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{Task} & \textbf{Score} & \textbf{特殊限制} \cr\hline
1 & 10 & n,m\le 500  \cr\hline
2 & 20 &  n,m\le 5\times 10^3 \cr\hline
3 & 10 & \text{每个小镇的函数相同}\cr\hline
4 & 20 & a_i=0 \cr\hline
5 & 20 & m=n-1 \cr\hline
6 & 20 & \cr\hline
\end{array}
$$

对于 $100\%$ 的数据，$2\le n \le 2 \times 10^5$， $n-1 \le m \le 10^6$，$0 \le a_i$，$b_i$，$c_i \le 10^6$。

数据保证最小价格在 $\tt{long \ long}$ 范围内。

#### 说明

本题有 $\text{spj}$，价格正确可以获得 $30\%$ 的分数。每个 $\text{subtask}$ 取其中所有数据点得分的最小值。

如果你不会构造方案，也请你再输出最小价格后输出 $m$ 行，每行两个 $[1,n]$ 范围内的整数，防止 $\text{spj}$ 出现错误。

本题已添加 hack 数据，为 $\text{subtask7}$，该 $\text{subtask}$ 不计分数，但会影响是否 $\text{AC}$。


title: 『STA - R1』Crossnews

background: Informational problems make us better.

description:
定义两个序列 $\{a_n\}$，$\{b_n\}$ 的联合权值为
$$\operatorname{unval}(a,b)=\sum_{i=1}^nb_i(b_i-a_i)$$

现给定一个序列 $\{a_n\}$，求满足 $\operatorname{unval}(a,b)$ 最小的单调不减序列 $\{b\}$，只需输出 $\operatorname{unval}(a,b)$ 的值即可。

注意，$\{b\}$ 中的元素不一定要为整数。

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

第二行 $n$ 个整数表示 $a_i$。

outputFormat: 一行一个答案。

hint:
提示：如果你不会做这道题，可以问问 [APJifengc](/user/279652)。
***

样例 1 解释：使得联合权值取到最小值的 $\{b\}$ 为 `0.5 1 1.5 2 2.5`。

***
数据范围和约定：
$$
\newcommand{\arraystretch}{1.5}
\begin{array}{c|c|c|c}\hline\hline
\textbf{Subtask} & \bm{n}\le & \textbf{分值} & \textbf{特殊性质}\\\hline
\textsf{1} & 100 & 10 & \textbf{无} \\\hline
\textsf{2} & 10^6 & 5 & \{a\}\textbf{ 全部相等} \\\hline
\textsf{3} & 10^6 & 5 & \{a\}\textbf{ 单调不减} \\\hline
\textsf{4} & 10^4 & 30 & \textbf{无} \\\hline
\textsf{5} & 10^6 & 50 & \textbf{无}
\\\hline\hline
\end{array}
$$

对于全部数据，有 $1\le n\le 10^6$，$|a_i|\le 10^3$。

***

评分规则：

本题使用 Special Judge，如果你的答案是 $pans$，标准答案是 $cans$，则你将获得
$$\min\Bigg\{100,\Bigg\lfloor\dfrac{0.1}{\min\Big\{|pans-cans|,\Big|\dfrac{|pans-cans|}{cans}\Big|\Big\}}\Bigg\rfloor\Bigg\}$$
分。

**每个 Subtask 内捆绑测试**。即取 Subtask 内得分最小的作为 Subtask 得分。


title: [JRKSJ R6] 牵连的世界

description:
给定 $n,m$，求

$$\sum_{i=1}^n \sum_{j=1}^m \sigma_0(ij)\varphi(ij)$$

inputFormat: 两个整数 $n,m$。

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


title: 「UOI-R1」智能推荐

background: 数据已加强。

description:
现在有 $N$ 道题。

天数的编号从 $0$ 开始，每一天你可以做若干道题，你只能做以前推荐过的或者当天推荐的题（每道题只可以做一次）。第一天，智能推荐会推荐 $p$ 道题。

推荐规则如下：

对于第 $i$ 道题，如果有可能被推荐的话，就会有一个题目集合 $s_i$。当且仅当你把 $s_i$ 中每一道题都做出来并且其中有一道题是当天做的，那么下一天就会推荐第 $i$ 题。

你想做完第 $K$ 道题，问至少第几天你才能满足愿望？

inputFormat:
第一行三个整数 $N,K,p$，含义如题目所述。

第二行 $p$ 个整数，表示第一天推荐的题的题号。

第三行一个整数 $R$，表示有 $R$ 条推荐规则。

接下来 $R$ 行，每行包含一条规则，每行格式如下：

一个整数 $v_i$，表示要推荐的题的题号。接着一个整数 $s_i$，表示要使得这道题被推荐，一共要做的题目数量。接下来 $s_i$ 个整数 $p_i$，表示要做的每道题。

outputFormat:
一个整数表示最少第几天才能满足愿望。

如无论如何，第 $K$ 题都无法完成，则输出 `-1`。

samples:
见文件附件的 rec4.in
见文件附件的 rec4.ans

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

第 $0$ 天推了第 $1,2$ 题，都做了。

第 $1$ 推了第 $3$ 题，做了。

第 $2$ 推了第 $4$ 题，做了。

第 $3$ 推了第 $5$ 题，也就是第 $K$ 题，做了。

第 $3$ 天即可做完第 $K$ 题目。

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

第 $0$ 天推了第 $1$ 题，也就是第 $K$ 题，做了。
第 $0$ 天就做完了。

**【数据范围】**

以下记 $\left| s_i \right|$ 表示推荐规则中第 $i$ 条规则中，如果 $v_i$ 被推荐，要做的所有题。

对于 $30\%$ 的数据，保证 $1 \leq N \leq 100$。

对于 $50\%$ 的数据，保证没有环。

对于 $100\%$ 的数据，保证 $1 \le K,s_i,p_i,v_i \le N \le 5\times 10^3$，$0 \leq R \leq 5 \times 10^3$。$|s_i|$ 互不相同，且对于每一个 $|s_i|$ 都有 $p_i$ 互不相同，$v_i$ 互不相同。


title: 「Wdoi-(-1)」恋弹者们的黑集市

background:
> 天弓千亦有言：「能力卡终将大势所趋归于陈腐，集市终将回归日常，这是发展规律。」但不知为何和神明所说相悖，卡片的价值遭到了炒作。有人在炒作卡的价值吗废话？又或者说，有倒爷在囤积这些卡片吗？卡片市场秩序完全陷入混乱之时，即便是神明也无法介入的集市，就此出现。

$$\quad\tag*{\small\textit{---TH18.5 恋弹者们的黑集市}}$$

魔理沙正在调查妖怪之山的高地，来收集逸散在各地的能力卡片。就在此时，她遇到了住在此处的驹草山如。

在河童与天狗间游刃有余的驹草山如，掌握着此地大量的资源。显而易见的，她掌握着大量的能力卡片——这正是魔理沙探访的目标。

「想要这些卡片吗，那就让我们玩一个游戏吧」

「赢了，这些卡片就都归你；输了，你可要交出身上所有的卡片。」

description:
### 原始题意

驹草山如将一个六面写满权值的骰子放在了棋盘上。棋盘上花花绿绿写着很多数字。第 $i$ 行第 $j$ 列写有数字 $a_{i-1,j-1}$。

「你能否获得这些能力卡片，取决于你获得的分数。」

魔理沙有两种方法移动这个骰子：将骰子向下一列**翻转**，或者向下一行**翻转**。值得注意的是，翻转骰子后，骰子每面上的数字就会随着翻滚而改变。现在魔理沙需要将骰子滚动至第 $n$ 行第 $m$ 列。

魔理沙的分数被定义为，所有时刻，骰子与棋盘上的数字接触的那一面的数字，乘上棋盘上该数字，再累加起来的和。只有魔理沙最大化这个和，她才能获取她所需要的卡片。

你能帮帮魔理沙吗？

### 简要题意

有一个 $n\times m$ 大小的棋盘，第 $i$ 行第 $j$ 列写有数字 $a_{i-1,j-1}$。

现在有一个骰子，六个面按照前、后、左、右、上、下的顺序，依次写有数字 $w_0,w_1,w_2,w_3,w_4,w_5$。现在骰子摆放在 $(0,0)$ 位置，需要将它**滚动**至 $(n-1,m-1)$。

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

骰子只有两种方式滚动：向下一行翻滚、向下一列翻滚。我们记一种方案的权值为，整个过程中（包括骰子在起点和终点时），骰子**最底面**上写着的数字，与此时骰子所在格子上写着的数字的乘积之和。

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

（为了方便读者阅读，骰子上的数字已经隐去）

现在你需要最大化这个乘积之和。

inputFormat:
- 第一行有两个正整数 $n, m$，表示棋盘的大小。
- 接下来 $n$ 行 $m$ 列描述棋盘内元素的值 $a_{i,j}$。
- 接下来一行有六个整数，分别表示 $w_0,w_1,w_2,w_3,w_4,w_5$。

outputFormat: - 输出共一行一个整数，表示可以获得的最大权值。


title: [CSP-J 2022] 乘方

description:
小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数 $a$ 和 $b$，求 $a^b$ 的值是多少。

$a^b$ 即 $b$ 个 $a$ 相乘的值，例如 $2^3$ 即为 $3$ 个 $2$ 相乘，结果为 $2 \times 2 \times 2 = 8$。

“简单！”小文心想，同时很快就写出了一份程序，可是测试时却出现了错误。

小文很快意识到，她的程序里的变量都是 `int` 类型的。在大多数机器上，`int` 类型能表示的最大数为 $2^{31} - 1$，因此只要计算结果超过这个数，她的程序就会出现错误。

由于小文刚刚学会编程，她担心使用 `int` 计算会出现问题。因此她希望你在 $a^b$ 的值超过 ${10}^9$ 时，输出一个 `-1` 进行警示，否则就输出正确的 $a^b$ 的值。

然而小文还是不知道怎么实现这份程序，因此她想请你帮忙。

inputFormat: 输入共一行，两个正整数 $a, b$。

outputFormat: 输出共一行，如果 $a^b$ 的值不超过 ${10}^9$，则输出 $a^b$ 的值，否则输出 `-1`。


title: [CSP-J 2022] 解密

description: 给定一个正整数 $k$，有 $k$ 次询问，每次给定三个正整数 $n_i, e_i, d_i$，求两个正整数 $p_i, q_i$，使 $n_i = p_i \times q_i$、$e_i \times d_i = (p_i - 1)(q_i - 1) + 1$。

inputFormat:
第一行一个正整数 $k$，表示有 $k$ 次询问。

接下来 $k$ 行，第 $i$ 行三个正整数 $n_i, d_i, e_i$。

outputFormat:
输出 $k$ 行，每行两个正整数 $p_i, q_i$ 表示答案。

为使输出统一，你应当保证 $p_i \leq q_i$。

如果无解，请输出 `NO`。


title: [CSP-J 2022] 逻辑表达式

description:
逻辑表达式是计算机科学中的重要概念和工具，包含逻辑值、逻辑运算、逻辑运算优先级等内容。

在一个逻辑表达式中，元素的值只有两种可能：$0$（表示假）和 $1$（表示真）。元素之间有多种可能的逻辑运算，本题中只需考虑如下两种：“与”（符号为 `&`）和“或”（符号为 `|`）。其运算规则如下：

$0 \mathbin{\&} 0 = 0 \mathbin{\&} 1 = 1 \mathbin{\&} 0 = 0$，$1 \mathbin{\&} 1 = 1$；
$0 \mathbin{|} 0 = 0$，$0 \mathbin{|} 1 = 1 \mathbin{|} 0 = 1 \mathbin{|} 1 = 1$。

在一个逻辑表达式中还可能有括号。规定在运算时，括号内的部分先运算；两种运算并列时，`&` 运算优先于 `|` 运算；同种运算并列时，从左向右运算。

比如，表达式 `0|1&0` 的运算顺序等同于 `0|(1&0)`；表达式 `0&1&0|1` 的运算顺序等同于 `((0&1)&0)|1`。

此外，在 C++ 等语言的有些编译器中，对逻辑表达式的计算会采用一种“短路”的策略：在形如 `a&b` 的逻辑表达式中，会先计算 `a` 部分的值，如果 $a = 0$，那么整个逻辑表达式的值就一定为 $0$，故无需再计算 `b` 部分的值；同理，在形如 `a|b` 的逻辑表达式中，会先计算 `a` 部分的值，如果 $a = 1$，那么整个逻辑表达式的值就一定为 $1$，无需再计算 `b` 部分的值。

现在给你一个逻辑表达式，你需要计算出它的值，并且统计出在计算过程中，两种类型的“短路”各出现了多少次。需要注意的是，如果某处“短路”包含在更外层被“短路”的部分内则不被统计，如表达式 `1|(0&1)` 中，尽管 `0&1` 是一处“短路”，但由于外层的 `1|(0&1)` 本身就是一处“短路”，无需再计算 `0&1` 部分的值，因此不应当把这里的 `0&1` 计入一处“短路”。

inputFormat: 输入共一行，一个非空字符串 $s$ 表示待计算的逻辑表达式。

outputFormat: 输出共两行，第一行输出一个字符 `0` 或 `1`，表示这个逻辑表达式的值；第二行输出两个非负整数，分别表示计算上述逻辑表达式的过程中，形如 `a&b` 和 `a|b` 的“短路”各出现了多少次。

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

该逻辑表达式的计算过程如下，每一行的注释表示上一行计算的过程：

```plain
0&(1|0)|(1|1|1&0)
=(0&(1|0))|((1|1)|(1&0)) //用括号标明计算顺序
=0|((1|1)|(1&0))   //先计算最左侧的 &，是一次形如 a&b 的“短路”
=0|(1|(1&0))       //再计算中间的 |，是一次形如 a|b 的“短路”
=0|1               //再计算中间的 |，是一次形如 a|b 的“短路”
=1
```

**【样例 \#3】**

见附件中的 `expr/expr3.in` 与 `expr/expr3.ans`。

**【样例 \#4】**

见附件中的 `expr/expr4.in` 与 `expr/expr4.ans`。

**【数据范围】**

设 $\lvert s \rvert$ 为字符串 $s$ 的长度。

对于所有数据，$1 \le \lvert s \rvert \le {10}^6$。保证 $s$ 中仅含有字符 `0`、`1`、`&`、`|`、`(`、`)` 且是一个符合规范的逻辑表达式。保证输入字符串的开头、中间和结尾均无额外的空格。保证 $s$
中没有重复的括号嵌套（即没有形如 `((a))` 形式的子串，其中 `a` 是符合规范的逻辑表
达式）。

| 测试点编号 | $\lvert s \rvert \le$ | 特殊条件 |
|:-:|:-:|:-:|
| $1 \sim 2$ | $3$ | 无 |
| $3 \sim 4$ | $5$ | 无 |
| $5$ | $2000$ | 1 |
| $6$ | $2000$ | 2 |
| $7$ | $2000$ | 3 |
| $8 \sim 10$ | $2000$ | 无 |
| $11 \sim 12$ | ${10}^6$ | 1 |
| $13 \sim 14$ | ${10}^6$ | 2 |
| $15 \sim 17$ | ${10}^6$ | 3 |
| $18 \sim 20$ | ${10}^6$ | 无 |

其中：
特殊性质 1 为：保证 $s$ 中没有字符 `&`。
特殊性质 2 为：保证 $s$ 中没有字符 `|`。
特殊性质 3 为：保证 $s$ 中没有字符 `(` 和 `)`。

**【提示】**

以下给出一个“符合规范的逻辑表达式”的形式化定义：

- 字符串 `0` 和 `1` 是符合规范的；
- 如果字符串 `s` 是符合规范的，且 `s` 不是形如 `(t)` 的字符串（其中 `t` 是符合规范的），那么字符串 `(s)` 也是符合规范的；
- 如果字符串 `a` 和 `b` 均是符合规范的，那么字符串 `a&b`、`a|b` 均是符合规范的；
- 所有符合规范的逻辑表达式均可由以上方法生成。


title: [CSP-J 2022] 上升点列

description:
在一个二维平面内，给定 $n$ 个整数点 $(x_i, y_i)$，此外你还可以自由添加 $k$ 个整数点。

你在自由添加 $k$ 个点后，还需要从 $n + k$ 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 $1$ 而且横坐标、纵坐标值均单调不减，即 $x_{i+1} - x_i = 1, y_{i+1} = y_i$ 或 $y_{i+1} - y_i = 1, x_{i+1} = x_i$。请给出满足条件的序列的最大长度。

inputFormat:
第一行两个正整数 $n, k$ 分别表示给定的整点个数、可自由添加的整点个数。

接下来 $n$ 行，第 $i$ 行两个正整数 $x_i, y_i$ 表示给定的第 $i$ 个点的横纵坐标。

outputFormat: 输出一个整数表示满足要求的序列的最大长度。


title: [CSP-S 2022] 假期计划

description:
小熊的地图上有 $n$ 个点，其中编号为 $1$ 的是它的家、编号为 $2, 3, \ldots, n$ 的都是景点。部分点对之间有双向直达的公交线路。如果点 $x$ 与 $z_1$、$z_1$ 与 $z_2$、……、$z_{k - 1}$ 与 $z_k$、$z_k$ 与 $y$ 之间均有直达的线路，那么我们称 $x$ 与 $y$ 之间的行程可转车 $k$ 次通达；特别地，如果点 $x$ 与 $y$ 之间有直达的线路，则称可转车 $0$ 次通达。

很快就要放假了，小熊计划从家出发去 $4$ 个**不同**的景点游玩，完成 $5$ 段行程后回家：家 $\to$ 景点 A $\to$ 景点 B $\to$ 景点 C $\to$ 景点 D $\to$ 家且每段行程最多转车 $k$ 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A $\to$ 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D $\to$ 家这段行程转车时经过的点。

假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个**不同**景点的分数之和最大。

inputFormat:
第一行包含三个正整数 $n, m, k$，分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。

第二行包含 $n - 1$ 个正整数，分别表示编号为 $2, 3, \ldots, n$ 的景点的分数。

接下来 $m$ 行，每行包含两个正整数 $x, y$，表示点 $x$ 和 $y$ 之间有道路直接相连，保证 $1 \le x, y \le n$，且没有重边，自环。

outputFormat: 输出一个正整数，表示小熊经过的 $4$ 个不同景点的分数之和的最大值。


title: [IOI2022] 鲶鱼塘

background:
# 滥用评测资源者封号

### 由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。

原题时间限制 1s，为了节约评测资源，时间限制修改为 0.5s。

description:
Bu Dengklek 有一个鲶鱼塘。这个鲶鱼塘是由 $N \times N$ 个网格单元构成的池塘。每个单元都是相同大小的正方形。网格各列自西向东编号为从 $0$ 到 $N - 1$，各行自南向北编号为从 $0$ 到 $N - 1$。我们把坐落在网格第 $c$ 列第 $r$ 行处（$0 \le c \le N - 1$，$0 \le r \le N - 1$）的单元记为单元 $(c, r)$。

池塘里总共有 $M$ 条鲶鱼，编号为从 $0$ 到 $M - 1$，分别位于**不同的**单元中。对每个满足 $0 \le i \le M - 1$ 的 $i$，鲶鱼 $i$ 在单元 $(X_i, Y_i)$ 中，其重量为 $W_i$ 克。

Bu Dengklek 想造些长堤来抓鲶鱼。在第 $c$ 列中长度为 $k$ 的长堤（对于所有 $0 \le c \le N - 1$ 和 $1 \le k \le N$），是一个从第 $0$ 行跨到第 $k - 1$ 行的矩形，盖住单元 $(c, 0), (c, 1), \ldots, (c, k - 1)$。对于每一列，Bu Dengklek 可以按照她自己选择的某个长度造长堤，也可以不造。

鲶鱼 $i$（对所有满足 $0 \le i \le M - 1$ 的 $i$）能被抓住，如果有某个长堤紧邻它的西侧或东侧，而且没有长堤盖住它所在的单元；也就是说，如果
* 单元 $(X_i - 1, Y_i)$ 或 $(X_i + 1, Y_i)$ 中 **至少有一个** 被某个长堤盖住，而且
* 没有长堤盖住单元 $(X_i, Y_i)$。

例如，考虑尺寸为 $N = 5$，有 $M = 4$ 条鲶鱼的池塘：

* 鲶鱼 $0$ 在单元 $(0, 2)$ 中，重量为 $5$ 克。
* 鲶鱼 $1$ 在单元 $(1, 1)$ 中，重量为 $2$ 克。
* 鲶鱼 $2$ 在单元 $(4, 4)$ 中，重量为 $1$ 克。
* 鲶鱼 $3$ 在单元 $(3, 3)$ 中，重量为 $3$ 克。

Bu Dengklek 可以这样来造长堤：

| 造长堤前 | 造长堤后 |
| :---: | :---: |
| ![](https://cdn.luogu.com.cn/upload/image_hosting/2rcnqc7k.png) | ![](https://cdn.luogu.com.cn/upload/image_hosting/yesaiovt.png) |

单元中的数字表示该单元中鲶鱼的重量。
阴影单元被长堤盖住。
在该场景中，鲶鱼 $0$（在单元 $(0, 2)$ 中）和鲶鱼 $3$（在单元 $(3, 3)$ 中）能被抓住。
鲶鱼 $1$（在单元 $(1, 1)$ 中）没被抓住，因为有一个长堤盖住了它所在的单元；鲶鱼 $2$（在单元 $(4, 4)$ 中）没被抓住，因为没有长堤紧邻它的西侧或东侧。

Bu Dengklek 希望造出来的长堤能让被抓住的鲶鱼的总重量尽量大。
你的任务是求出 Bu Dengklek 通过造长堤能抓住的鲶鱼的最大总重量。

inputFormat:
你需要实现下面的函数：

```go
int64 max_weights(int N, int M, int[] X, int[] Y, int[] W)
```

* $N$：池塘的尺寸。
* $M$：鲶鱼的数量。
* $X$, $Y$：长度为 $M$ 的两个数组，给出鲶鱼的位置。
* $W$：长度为 $M$ 的数组，给出鲶鱼的重量。
* 该函数需要返回一个整数，表示 Bu Dengklek 通过造长堤能抓住的鲶鱼的最大总重量。
* 该函数将被恰好调用一次。

outputFormat:
考虑如下调用：

```go
max_weights(5, 4, [0, 1, 4, 3], [2, 1, 4, 3], [5, 2, 1, 3])
```

该例子的解释请见前面的题面。

在造完所述的长堤后，Bu Dengklek 能抓住鲶鱼 $0$ 和 $3$，其总重量为 $5 + 3 = 8$ 克。
因为无法造出能够抓住总重量超过  $8$ 克的鲶鱼的长堤，函数应当返回 $8$。

hint:
### 约束条件

* $2 \le N \le 100\;000$
* $1 \le M \le 300\;000$
* $0 \le X_i \le N - 1$，$0 \le Y_i \le N - 1$（对所有满足 $0 \le i \le M - 1$ 的 $i$）
* $1 \le W_i \le 10^9$（对所有满足 $0 \le i \le M - 1$ 的 $i$）
* 任意两条鲶鱼都不会在同一单元中。
  换句话说，$X_i \neq X[j]$ 或 $Y_i \neq Y[j]$（对于所有满足 $0 \le i \lt j \le M - 1$ 的 $i$ 和 $j$）。

### 子任务

1. （3 分） $X_i$ 是偶数（对于所有满足 $0 \le i \le M - 1$ 的 $i$）
1. （6 分） $X_i \le 1$（对于所有满足 $0 \le i \le M - 1$ 的 $i$）
1. （9 分） $Y_i = 0$（对于所有满足 $0 \le i \le M - 1$ 的 $i$）
1. （14 分） $N \le 300$，$Y_i \le 8$（对于所有满足 $0 \le i \le M - 1$ 的 $i$）
1. （21 分） $N \le 300$
1. （17 分） $N \le 3000$
1. （14 分） 在每列中至多有 $2$ 条鲶鱼。
1. （16 分） 没有额外限制。

### 评测程序示例

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

* 第 $1$ 行：$N \; M$
* 第 $2 + i$ 行（$0 \le i \le M - 1$）：$X_i \; Y_i \; W_i$

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

* 第 $1$ 行：`max_weights` 的返回值

### 约定

题面在给出函数接口时，会使用一般性的类型名称 `void`、`int`、`int64`、`int[]`（数组）和 `int[][]`（数组的数组）。

在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：

| `void ` | `int` | `int64`     | `int[]`            |
| ------- | ----- | ----------- | ------------------ |
| `void ` | `int` | `long long` | `std::vector<int>` |

| `int[][]`                       | 数组 `a` 的长度 |
| ------------------------------- | ------------------- |
| `std::vector<std::vector<int>>` | `a.size()`          |


title: [IOI2022] 囚徒挑战

background:
# 滥用评测资源者封号

### 由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。

原题时间限制 1s，为了节约评测资源，时间限制修改为 0.5s

description:
一个监狱里关着 $500$ 名囚徒。
有一天，监狱长给了他们一个重获自由的机会。
他把装钱的两个袋子 A 和 B 放在一个房间里。
每个袋子装有若干枚硬币，数量的范围在 $1$ 到 $N$ 之间（包含 $1$ 和 $N$）。
两个袋子里硬币的数量**不同**。
监狱长给囚徒们提出了挑战，目标是指出硬币数量较少的那个袋子。

房间里除了袋子还有一块白板。
任意时刻白板上写着一个数，一开始写的是 $0$。

监狱长让囚徒一个接一个地进入房间。
每个进入房间的囚徒不知道他之前进入过房间的囚徒有多少人，也不知道是哪些人。
每次一个囚徒进入房间时，他看一眼白板上目前写的这个数。
看完之后，他必须在袋子 A 和 B 之间做出选择。
接着，他**检查**自己选的那个袋子，知道了里面有多少枚硬币。
然后，这名囚徒必须选择做以下两种**行动**之一：

* 将白板上的数改写成一个非负整数，并离开房间。
注意他可以改变成新的数，也可以保留当前的数。
然后挑战继续进行（除非所有 $500$ 名囚徒都已经进过房间）。
* 指出硬币数量较少的那个袋子。这会立即结束挑战。

对于已经进过房间的囚徒，监狱长不会让他再次进入房间。

如果某个囚徒正确地指出硬币较少的袋子，则囚徒们获得挑战的胜利。
如果指出的袋子不正确，或者所有 $500$ 人进过房间之后还没有人尝试指出硬币较少的袋子，则囚徒们失败。

挑战开始之前，囚徒们集合在监狱大厅商量应对挑战的共同**策略**，分以下三个步骤：
* 他们挑选一个非负整数 $x$，作为他们可能会写在白板上的最大的数。
* 他们决定对任意一个数 $i$ ($0 \le i \le x$)，如果某个囚徒进入房间后看到白板上写着数 $i$，那么他应该去检查哪个袋子。
* 他们决定当某个囚徒得知选中的袋子里的硬币数量后要采取的行动。具体来说，对任意写在白板上的数 $i$ ($0 \le i \le x$) 和检查选中的袋子里的硬币数量 $j$ ($1 \le j \le N$)，他们要决定做出以下两种行动之一：
  - 白板上应该要写一个 $0$ 到 $x$ 之间（包含 $0$ 和 $x$）的什么数；
  - 指出哪个袋子是硬币较少的。

如果赢得挑战，监狱长会在囚徒们继续服刑 $x$ 天后释放他们。

你的任务是提出能够确保囚徒们赢得挑战的策略（不管袋子 A 和 B 中的硬币数量是多少）。
你的得分取决于 $x$ 的值（详见子任务一节）。

inputFormat:
你要实现以下函数：

```go
int[][] devise_strategy(int N)
```

- $N$：每个袋子里硬币最多可能的数量。
- 该函数需要返回一个数组 $s$，它的每个元素是长度为 $N + 1$ 的整数数组，表示你给出的策略。$x$ 的值是数组 $s$ 的长度减一。对满足 $0 \le i \le x$ 的每个 $i$，数组 $s_i$ 表示囚徒在进入房间看到白板上写着数 $i$ 时要做的事情：
  1. 如果囚徒应该检查袋子 A，则 $s_{i, 0}$ 的值是 $0$；如果囚徒应该检查袋子 B，则该值是 $1$。
  2. 令 $j$ 为所选袋子中的硬币数量，囚徒应该进行以下行动：
     - 如果 $s_{i, j}$ 的值是 $-1$，则囚徒应该指出袋子 A 是硬币较少的袋子。
     - 如果 $s_{i, j}$ 的值是 $-2$，则囚徒应该指出袋子 B 是硬币较少的袋子。
     - 如果 $s_{i, j}$ 的值是非负整数，则囚徒应该把这个数写到白板上。注意 $s_{i, j}$ 至多只能是 $x$。
- 该函数恰好被调用一次。

outputFormat:
考虑以下调⽤：

```go
devise_strategy(3)
```

令 $v$ 表示囚徒进入房间时看到白板上写着的数。以下是一种正确的策略：

- 如果 $v = 0$（也包括开始时的数），则检查袋子 A。
  - 如果它装了 $1$ 个硬币，则指出袋子 A 是硬币较少的袋子。
  - 如果它装了 $3$ 个硬币，则指出袋子 B 是硬币较少的袋子。
  - 如果它装了 $2$ 个硬币，则在白板上写上 $1$（覆盖之前的 $0$）。
- 如果 $v = 1$，则检查袋子 B。
  - 如果它装了 $1$ 个硬币，则指出袋子 B 是硬币较少的袋子。
  - 如果它装了 $3$ 个硬币，则指出袋子 A 是硬币较少的袋子。
  - 如果它装了 $2$ 个硬币，则在白板上写上 $0$（覆盖之前的 $1$）。注意，这种情况其实不可能发生，因为此时两个袋子都装有 $2$ 枚硬币，是不允许的。

要产生以上策略，函数应该返回 `[[0, -1, 1, -2], [1, -2, 0, -1]]`。
返回的数组长度是 $2$，此时 $x$ 的值是 $2 - 1 = 1$。

hint:
### 约束条件

- $2 \leq N \leq 5000$。

### 子任务

1. （5 分）$N \le 500$，$x$ 的值不能超过 $500$。
1. （5 分）$N \le 500$，$x$ 的值不能超过 $70$。
1. （90分）$x$ 的值不能超过 $60$。

对于任何测试用例，如果 `devise_strategy` 返回的数组是不合法的，则你在该子任务上的得分为 $0$。

子任务 3 有部分分。
令 $m$ 为该子任务中所有测试用例返回数组对应的 $x$ 的最大值，你的得分将根据下表计算：

| 条件 | 得分 |
| :-: | :-: |
| $40 \leq m \leq 60$ | $20$ |
| $26 \leq m \leq 39$ | $25 + 1.5 \times (40 − m)$ |
| $m = 25$ | $50$ |
| $m = 24$ | $55$ |
| $m = 23$ | $62$ |
| $m = 22$ | $70$ |
| $m = 21$ | $80$ |
| $m \leq 20$ | $90$ |

### 评测程序示例

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

* 第 $1$ 行：$N$
* 第 $2 + k$ 行 ($0 \le k$)：$A_k \; B_k$
* 最后一行：$-1$

除第一行和最后一行外，每行表示一个场景。
将第 $2 + k$ 行对应的场景称为场景 $k$。
场景 $k$ 中，袋子 A 装有 $A[k]$ 枚硬币，袋子 B 装有 $B[k]$ 枚硬币。

评测程序示例首先调用 `devise_strategy(N)`。
$x$ 的值是返回数组的长度减一。
如果评测程序示例检测到 `devise_strategy` 返回的数组不符合实现细节中描述的约束，它会打印如下错误信息并退出：

* `s is an empty array`：$s$ 是空的数组（表示不合法的策略）。
* `s[i] contains incorrect length`：存在一个下标 $i$ ($0 \le i \le x$) 满足 $s_i$ 的长度不是 $N + 1$。
* `First element of s[i] is non-binary`：存在一个下标 $i$ ($0 \le i \le x$) 满足 $s_{i,0}$ 既不是 $0$，也不是$1$。
* `s[i][j] contains incorrect value`：存在下标 $i, j$ ($0 \le i \le x, 1 \le j \le N$) 满足 $s_{i, j}$ 的值不在 $-2$ 和 $x$ 之间。

否则，评测程序示例产生两项输出内容。

首先，评测程序示例以如下格式打印你的策略的输出：

* 第 $1 + k$ 行 ($0 \le k$)：场景 $k$ 下你的策略的输出。
如果用该策略导致某个囚徒指出袋子 A 是硬币较少的，则输出字符 `A`。
如果用该策略导致某个囚徒指出袋子 B 是硬币较少的，则输出字符 `B`。
如果用该策略后没有囚徒指出哪个袋子的硬币较少，则输出字符 `X`。

其次，评测程序示例以如下格式在当前目录下写一个文件 `log.txt`：

* 第 $1 + k$ 行 ($0 \le k$)：$w_{k,0} \; w_{k,1} \; \ldots$

第 $1 + k$ 行的序列对应于场景 $k$，描述了写在白板上的数。
具体来说，$w[k][l]$ 是第 $l + 1$ 个囚徒进入房间后写的数。

### 约定

题面在给出函数接口时，会使用一般性的类型名称 `void`、`int`、`int64`、`int[]`（数组）和 `int[][]`（数组的数组）。

在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：

| `void ` | `int` | `int64`     | `int[]`            |
| ------- | ----- | ----------- | ------------------ |
| `void ` | `int` | `long long` | `std::vector<int>` |

| `int[][]`                       | 数组 `a` 的长度 |
| ------------------------------- | ------------------- |
| `std::vector<std::vector<int>>` | `a.size()`          |


title: [IOI2022] 无线电信号塔

background:
# 滥用评测资源者封号

### 由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。

由于本题数据点过多，结合洛谷评测技术实现情况，本题将以 ACM mode 进行评分。

description:
雅加达有 $N$ 个无线电信号塔。这些信号塔排布成一条直线，并且从左到右依次编号为从 $0$ 到 $N - 1$。
对于每个满足 $0 \le i \le N - 1$ 的 $i$，信号塔 $i$ 的高度为 $H_i$ 米。
所有塔的高度都是**不同的**。

对于某个为正数的信号干扰参数 $\delta$，一对信号塔 $i$ 和 $j$ ($0 \le i \lt j \le N - 1$) 之间能够互相通信，当且仅当存在一个中间信号塔 $k$ 满足如下条件：

* 塔 $i$ 在塔 $k$ 的左边，并且塔 $j$ 在塔 $k$ 的右边，即 $i \lt k \lt j$；
* 塔 $i$ 和塔 $j$ 的高度都至多为 $H[k] - \delta$ 米。

Pak Dengklek 想租一些信号塔来组建他的新无线电网络。
你的任务是回答 Pak Dengklek 提出的 $Q$ 个询问。这些询问的形式如下：
给定参数 $L, R$ 和 $D$ ($0 \le L \le R \le N - 1$ 且 $D > 0$)，在满足下述所有条件时，Pak Dengklek 最多能够租多少个信号塔：

 * Pak Dengklek 只能租编号在 $L$ 和 $R$ 之间的信号塔（包括 $L$和 $R$）；
 * 信号干扰参数 $\delta$ 的值为 $D$；
 * Pak Dengklek 租的信号塔两两之间必须能够进行通信。

注意，无论中间信号塔 $k$ 是否被租，两个已租的信号塔都可以借助信号塔 $k$ 进行通信。

inputFormat:
你需要实现以下函数：

```go
void init(int N, int[] H)
```

* $N$： 信号塔的数量。
* $H$： 一个长度为 $N$ 的数组，给出信号塔的高度。
* 这个函数恰好被调用一次，且在函数 `max_towers` 的所有调用之前。

```go
int max_towers(int L, int R, int D)
```

* $L$, $R$：信号塔编号区间的边界。
* $D$：信号干扰参数 $\delta$ 的值。
* 该函数应返回 Pak Dengklek 最多能租的信号塔数量（用于组建信号网络），这里 Pak Dengklek 只能租 $L$ 和 $R$之间（包含 $L$ 和 $R$）的信号塔，且信号干扰参数 $\delta$ 的值是 $D$。
* 该函数将被调用恰好 $Q$ 次。

outputFormat:
考虑如下函数调⽤序列：

```go
init(7, [10, 20, 60, 40, 50, 30, 70])
```

```go
max_towers(1, 5, 10)
```

Pak Dengklek 可以租编号为 $1$, $3$ 和 $5$ 的信号塔。
下面给出了这个例子的示意图，其中的灰色梯形表示被租的信号塔。

![](https://img.loj.ac.cn/2022/08/10/a52f5b077031b.png)

信号塔 $3$ 和 $5$ 可以借助信号塔 $4$ 进行通信，这是因为 $40 \le 50 - 10$ 且 $30 \le 50 - 10$。
信号塔 $1$ 和 $3$ 可以借助信号塔 $2$ 进行通信。
信号塔 $1$ 和 $5$ 可以借助信号塔 $3$ 进行通信。
无法租超过 $3$ 个信号塔，因此函数应返回 $3$。

```go
max_towers(2, 2, 100)
```

在这个区间里只有 $1$ 个信号塔，所以 Pak Dengklek 只能租借 $1$ 个信号塔。
因此函数应返回 $1$。

```go
max_towers(0, 6, 17)
```

Pak Dengklek 可以租信号塔$1$ 和 $3$ 。
信号塔  $1$ 和 $3$ 可以借助信号塔 $2$进行通信，这是因为 $20 \le 60 - 17$ 且 $40 \le 60 - 17$。
无法租赁超过 $2$ 个信号塔，因此函数应返回 $2$。


title: [IOI2022] 数字电路

background:
**滥用评测资源者封号。**

**由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。**

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。

由于本题数据点过多，结合洛谷评测技术实现情况，本题将不按照题给 Subtask 评分。

description:
有一个数字电路，由编号为从 $0$ 到 $N + M - 1$ 的 $N + M$ 个**门**组成。其中，$0$ 到 $N - 1$ 号门是**阈值门**，而 $N$ 到 $N + M - 1$ 号门是**输入门**。

除 $0$ 号门之外的每个门都是恰好一个某阈值门的**输入**。具体来说，对于每个满足 $1 \le i \le N + M - 1$ 的 $i$，门 $i$ 是门 $P[i]$ 的一个输入，其中 $0 \le P[i] \le N-1$。重要的是，我们保证 $P[i] \lt i$ 成立。此外，我们假设有 $P[0] = -1$。每个阈值门有一个或多个的输入。输入门没有任何输入。

每个门都有一个**状态**，取 $0$ 或 $1$。输入门的初始状态由一个包含 $M$ 个整数的数组 $A$ 给定。也就是说，对于每个满足 $0 \le j \le M - 1$ 的 $j$ ，输入门 $N + j$ 的初始状态为 $A[j]$。

每个阈值门的状态取决于它的输入的状态，具体如下。首先，每个阈值门会被指定一个阈值**参数**。对于一个有 $c$ 个输入的阈值门，其所指定的参数必须是 $1$ 到 $c$ 之间的某个整数（包括 $1$ 和 $c$）。随后，对于一个参数为 $p$ 的阈值门，如果它的输入中至少有 $p$ 个门的状态为 $1$，则当前阈值门的状态为 $1$，否则状态为 $0$。

例如，假设有 $N = 3$ 个阈值门和 $M = 4$ 个输入门。其中，门 $0$ 的输入为门 $1$ 和门 $6$，门 $1$ 的输入为门 $2$、$4$ 和 $5$，门 $2$ 仅有的输入为门 $3$。

上述例子的说明可见下图。

![](https://arina.loli.net/2022/08/12/JtjqOi4HVBXeD3x.png)

假设输入门 $3$ 和 $5$ 的状态为 $1$，而门 $4$ 和 $6$ 的状态为 $0$。假设阈值门 $2$、$1$、$0$ 被指定的参数分别为 $1$、$2$、$2$。在这种情况下，门 $2$ 的状态为 $1$，门 $1$ 的状态为 $1$ ，门 $0$ 的状态为 $0$。下面给出了参数赋值以及状态的示意图。状态为 $1$ 的门被标记为黑色。

![](https://arina.loli.net/2022/08/12/Sdiye2vg3B1aYPu.png)

输入门的状态将会经历 $Q$ 次更新。每次更新用两个整数 $L$ 和 $R$ 来描述 ($N \le L \le R \le N + M - 1$) ，表示翻转所有编号在 $L$ 和 $R$ 之间（包括 $L$ 和 $R$）的输入门的状态。这就是说，对于所有满足 $L \le i \le R$ 的 $i$，输入门 $i$ 的状态如果为 $0$，则会被翻转为$1$；如果状态为 $1$，则会被翻转为 $0$。每个门被翻转后将会一直保持在新状态，直到在后续某次更新中被翻转。

你的目标是，计算每次更新后有多少种阈值门参数的赋值方案，使得门 $0$ 的状态为 $1$。当有至少一个阈值门的参数不同时，两种参数赋值方案被认为是不同的。由于方案数可能较大，你需要计算它对 $1\;000\;002\;022$ 取模的结果。

注意，在上面的例子中，共有 $6$ 种不同的对阈值门参数进行赋值的方案，因为门 $0$、$1$、$2$ 分别有 $2$、$3$、$1$ 个输入。在这 $6$ 种方案里面，有 $2$ 种参数赋值方案使得门 $0$ 的状态为 $1$。

inputFormat:
你的任务是实现下述两个函数。

```go
void init(int N, int M, int[] P, int[] A)
```

- $N$： 阈值门的数量。
- $M$：输入门的数量。
- $P$： 一个长度为 $N + M$ 的数组，给出阈值门的输入。
- $A$： 一个长度为 $M$的数组，给出输入门的初始状态。
- 这个函数被调用恰好一次，且发生在函数 `count_ways` 的所有调用之前。

```go
int count_ways(int L, int R)
```

- $L$, $R$：编号在 $L$ 和 $R$ 之间的输入门的状态将会被翻转。
- 这个函数应首先执行所规定的更新，然后返回使得门 $0$ 的状态为 $1$ 的参数赋值方案的方案数对 $1\;000\;002\;022$ 取模的结果。
- 这个函数会被调用恰好 $Q$ 次。

outputFormat:
考虑如下的函数调用序列：

```go
init(3, 4, [-1, 0, 1, 2, 1, 1, 0], [1, 0, 1, 0])
```

题面描述中已经给出了对这个例子的解释。

```go
count_ways(3, 4)
```

这次调用翻转了门 $3$ 和 $4$ 的状态，也就是说，门 $3$ 的状态变成 $0$，门 $4$ 的状态变成 $1$。下面给出了两种可行的参数赋值方案，可以使得门 $0$ 的状态为 $1$ 。

|               方案 $1$                |               方案 $2$                |
| :-----------------------------------: | :-----------------------------------: |
| ![](https://arina.loli.net/2022/08/12/azi4xDYOKpBnge6.png) | ![](https://arina.loli.net/2022/08/12/MBPhnOFyARSEQDH.png) |

在所有其他的参数赋值方案中，门 $0$ 的状态为 $0$。因此，函数应返回 $2$。

```go
count_ways(4, 5)
```

这次调用翻转了门 $4$ 和 $5$ 的状态。其结果是，所有输入门的状态均为 $0$，而且对于所有的参数赋值方案，门 $0$ 的状态均为 $0$。因此，函数应返回 $0$。

```go
count_ways(3, 6)
```

这次调用将所有输入门的状态置为 $1$。其结果是，对于所有参数赋值方案，门 $0$ 的状态均为 $1$。因此，函数应返回 $6$。

hint:
### 约束条件

- $1 \le N, M \le 10^5$；
- $1 \le Q \le 10^5$；
- $P[0] = -1$；
- $0 \le P[i] \lt i$ 且 $P[i] \le N - 1$（对于所有满足 $1 \le i \le N + M - 1$ 的 $i$）；
- 每个阈值门至少有一个输入（对于所有满足 $0 \le i \le N - 1$ 的 $i$，存在某个下标 $x$ 满足 $i \lt x \le N + M - 1$ 且 $P[x] = i$）；
- $0 \le A[j] \le 1$（对于所有满足 $0 \le j \le M - 1$的 $j$）；
- $N \le L \le R \le N + M - 1$。

### 子任务

1. （2 分）$N = 1$，$M \le 1000$，$Q \le 5$；
2. （7 分）$N, M \le 1000$，$Q \le 5$，每个阈值门都有恰好两个输入；
3. （9 分）$N, M \le 1000$，$Q \le 5$；
4. （4 分）$M = N + 1$，$M = 2^z$（对于某个正整数 $z$）， $P[i] = \lfloor\frac{i - 1}{2}\rfloor$（对于所有满足 $1 \le i \le N + M - 1$ 的 $i$），$L = R$；
5. （12 分）$M = N + 1$，$M = 2^z$（对于某个正整数 $z$），$P[i] = \lfloor\frac{i - 1}{2}\rfloor$（对于所有满足$1 \le i \le N + M - 1$的 $i$）；
6. （27 分）每个阈值门都恰好有两个输入；
7. （28 分）$N, M \le 5000$；
8. （11 分）没有额外的约束条件。

### 评测程序示例

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

- 第 $1$ 行： $N \; M \; Q$；
- 第 $2$ 行： $P[0] \; P[1] \; \ldots \; P[N + M - 1]$；
- 第 $3$ 行： $A[0] \; A[1] \; \ldots \; A[M - 1]$；
- 第 $4 + k$ 行（$0 \le k \le Q - 1$）： 第 $k$ 次更新对应的 $L \; R$。

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

- 第 $1 + k$ 行（$0 \le k \le Q - 1$）： `count_ways` 函数对第 $k$ 次更新的返回值。

### 约定

题面在给出函数接口时，会使用一般性的类型名称 `void`、`bool`、`int`、`int[]`（数组）和 `union(bool, int[])`。

在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：

| `void ` | `bool` | `int` | `int[]`            |
| ------- | ------ | ------| ------------------ |
| `void ` | `bool` | `int` | `std::vector<int>` |

| `union(bool, int[])`                   | 数组 `a` 的长度 |
| -------------------------------------- | ------------------- |
| `std::variant<bool, std::vector<int>>` | `a.size()`          |

C++ 语言里，`std::variant` 定义在 `<variant>` 头文件中。
一个返回类型为 `std::variant<bool, std::vector<int>>` 的函数可以返回一个 `bool` 或一个 `std::vector<int>`。
以下示例代码给出了三个返回 `std::variant` 的函数，它们都能正常工作：

```cpp
std::variant<bool, std::vector<int>> foo(int N) {
    return N % 2 == 0;
}

std::variant<bool, std::vector<int>> goo(int N) {
    return std::vector<int>(N, 0);
}

std::variant<bool, std::vector<int>> hoo(int N) {
    if (N % 2 == 0) {
        return false;
    }

    return std::vector<int>(N, 0);
}
```


title: [IOI2022] 最罕见的昆虫

background:
# 滥用评测资源者封号

**本题为交互题。**

您**不需要也不应该**在提交的程序中包含 `insects.h` 头文件和主函数。

但是在您的程序中，需要声明以下三个函数：

```cpp
void move_inside(int i);
void move_outside(int i);
int press_button();
```

例如，您的程序可以是这样：

```cpp
#include <bits/stdc++.h>
using namespace std;

void move_inside(int i);
void move_outside(int i);
int press_button();

int min_cardinality(int N) {
	// Code Here
}
```

description:
Pak Blangkon 的房子四周有 $N$ 只昆虫，编号为 $0$ 至 $N-1$。每只昆虫有一个**类型**，以从 $0$ 至 $10^9$（包含 $0$ 和 $10^9$）的整数编号。可能有多只昆虫类型相同。

假设将昆虫按照类型分组。我们定义**最常见**昆虫类型的基数是昆虫最多的分组中的昆虫数。类似地，**最罕见**昆虫类型的基数是昆虫最少的分组中的昆虫数。

例如，假设有 $11$ 只昆虫，类型分别为 $[5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]$。在此情形中，**最常见**昆虫类型的基数是 $3$，是因为类型 $9$ 和类型 $11$ 的分组均有最多数目的昆虫，每个分组都有 $3$ 只。**最罕见**昆虫类型的基数是 $1$，是因为类型 $7$、类型 $0$ 和类型 $100$ 的分组均有最少数目的昆虫，每个分组都有 $1$ 只。

Pak Blangkon 不知道这些昆虫的类型。他有一台单按钮的机器，可以提供昆虫类型相关的信息。刚开始时，机器是空的。在使用机器时，可以做如下三种操作：

1. 将一只昆虫放进机器。
2. 将一只昆虫取出机器。
3. 按下机器的按钮。

每种操作最多可以做 $40\;000$ 次。

每当按下按钮时，机器会报告在机器内的**最常见**昆虫类型的基数。

你的任务是使用上述机器，确定 Pak Blangkon 的房子四周所有 $N$ 只昆虫中**最罕见**昆虫类型的基数。此外，在某些子任务里，你的得分取决于机器执行某种操作的最大次数（详见子任务一节）。

inputFormat:
你要实现以下函数：

```go
int min_cardinality(int N)
```

- $N$：昆虫数量。
- 此函数应返回 Pak Blangkon 的房子四周所有 $N$ 只昆虫中**最罕见**昆虫类型的基数。
- 此函数恰好被调用一次。

该函数可调用以下几个函数：

```go
void move_inside(int i)
```

- $i$：将被放进机器的昆虫编号。编号 $i$ 的取值范围是 $0$ 至 $N-1$（包含 $0$ 和 $N-1$）。
- 如果昆虫已在机器内，函数调用不会影响机器内昆虫的集合。但是，调用仍会被计入此类操作的次数。
- 此函数最多可以被调用 $40\;000$ 次。

```go
void move_outside(int i)
```

- $i$：将被从机器中取出的昆虫编号。编号 $i$ 的取值范围是 $0$ 至 $N-1$（包含 $0$ 和 $N-1$）。
- 如果昆虫已在机器外，函数调用不会影响机器内昆虫的集合。但是，调用仍会被计入此类操作的次数。
- 此函数最多可以被调用 $40\;000$ 次。

```go
int press_button()
```

- 此函数返回机器内**最常见**昆虫类型的基数。
- 此函数最多可以被调用 $40\;000$ 次。
- 评测程序**不是适应性**的。也就是说，所有 $N$ 只昆虫的类型在 `min_cardinality` 调用前已经确定。

hint:
### 约束条件

- $2 \le N \le 2000$。

### 子任务

1. （10 分） $N \le 200$；
2. （15 分） $N \le 1000$；
3. （75 分） 没有额外的约束条件。

如果在某个测试用例上，函数 `move_inside`、`move_outside` 或 `press_button` 的调用次数不符合“实现细节”中给出的约束条件，或者 `min_cardinality` 的返回值不正确，你的解答在此子任务上得分为 $0$。

令 $q$ 为以下三个值的 **最大值**：`move_inside` 的调用次数、`move_outside` 的调用次数、`press_button` 的调用次数。

在子任务 3 中，你可能会得部分分。令 $m$ 为此子任务所有测试用例的 $\frac{q}{N}$ 的最大值。你在此子任务的得分将根据以下表格计算：

|       条件       |                   得分                   |
| :--------------: | :--------------------------------------: |
|    $20 \lt m$    | $0$ （CMS 报告“`Output isn’t correct`”） |
| $6 \lt m \le 20$ |           $\frac{225}{m - 2}$            |
| $3 \lt m \le 6$  |          $81 - \frac{2}{3} m^2$          |
|    $m \le 3$     |                   $75$                   |

### 评测程序示例

令 $T$ 是长度为 $N$ 的整数数组，其中 $T[i]$ 是编号为 $i$ 的昆虫的类型。

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

- 第 $1$ 行：$N$；
- 第 $2$ 行：$T[0] \; T[1] \; \ldots \; T[N - 1]$。

如果评测程序示例检测到非法行为，评测程序示例将输出 `Protocol Violation: <MSG>`，其中 `<MSG>` 为如下某种类型：

<!-- IMPORTANT NOTE TO TRANSLATORS: THESE MESSAGES (IN BACKTICKS), AS WELL AS 'Protocol Violation:' ABOVE SHOULD NOT BE TRANSLATED -->

- `invalid parameter`：在函数调用 `move_inside` 或 `move_outside` 时，参数 $i$ 的值不在 $0$ 至 $N-1$ 的范围内（包括 $0$ 和 $N-1$）。
- `too many calls`：函数 `move_inside`、`move_outside` 或 `press_button` 中**某个**的调用次数超过 $40\;000$ 次。

否则，评测程序示例按以下格式输出：

- 第 $1$ 行：`min_cardinality` 的返回值；
- 第 $2$ 行：$q$。

### 约定

题面在给出函数接口时，会使用一般性的类型名称 `void`、`bool`、`int`、`int[]`（数组）和 `union(bool, int[])`。

在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：

| `void ` | `bool` | `int` | `int[]`            |
| ------- | ------ | ------| ------------------ |
| `void ` | `bool` | `int` | `std::vector<int>` |

| `union(bool, int[])`                   | 数组 `a` 的长度 |
| -------------------------------------- | ------------------- |
| `std::variant<bool, std::vector<int>>` | `a.size()`          |

C++ 语言里，`std::variant` 定义在 `<variant>` 头文件中。
一个返回类型为 `std::variant<bool, std::vector<int>>` 的函数可以返回一个 `bool` 或一个 `std::vector<int>`。
以下示例代码给出了三个返回 `std::variant` 的函数，它们都能正常工作：

```cpp
std::variant<bool, std::vector<int>> foo(int N) {
    return N % 2 == 0;
}

std::variant<bool, std::vector<int>> goo(int N) {
    return std::vector<int>(N, 0);
}

std::variant<bool, std::vector<int>> hoo(int N) {
    if (N % 2 == 0) {
        return false;
    }

    return std::vector<int>(N, 0);
}
```


title: [NOI2022] 众数

description:
**对于一个序列，定义其众数为序列中出现次数严格大于一半的数字。注意该定义与一般的定义有出入，在本题中请以题面中给出的定义为准。**

一开始给定 $n$ 个长度不一的正整数序列，编号为 $1 \sim n$，初始序列可以为空。这 $n$ 个序列被视为存在，其他编号对应的序列视为不存在。

有 $q$ 次操作，操作有以下类型:

- $1 \ x \ y$：在 $x$ 号序列末尾插入数字 $y$。保证 $x$ 号序列存在，且 $1 \le x, y \le n + q$。
- $2 \ x$：删除 $x$ 号序列末尾的数字，保证 $x$ 号序列存在、非空，且 $1 \le x \le n + q$。
- $3 \ m \ x_1 \ x_2 \ x_m$：将 $x_1, x_2, \ldots, x_m$ 号序列顺次拼接，得到一个新序列，并询问其众数。如果不存在满足上述条件的数，则返回 $-1$。数据保证对于任意 $1 \le i \le m$，$x_i$ 是一个仍然存在的序列，$1 \le x_i \le n + q$，且拼接得到的序列非空。**注意：不保证 $\boldsymbol{x_1, \ldots, x_m}$ 互不相同，询问中的合并操作不会对后续操作产生影响。**
- $4 \ x_1 \ x_2 \ x_3$：新建一个编号为 $x_3$ 的序列，其为 $x_1$ 号序列后顺次添加 $x_2$ 号序列中数字得到的结果，然后删除 $x_1, x_2$ 对应的序列。此时序列 $x_3$ 视为存在，而序列 $x_1, x_2$ 被视为不存在，在后续操作中也不会被再次使用。保证 $1 \le x_1, x_2, x_3 \le n + q$、$x_1 \ne x_2$、序列 $x_1, x_2$ 在操作前存在、且在操作前没有序列使用过编号 $x_3$。

inputFormat:
输入的第一行包含两个正整数 $n$ 和 $q$，分别表示数列的个数和操作的次数，保证 $n \le 5 \times {10}^5$、$q \le 5 \times {10}^5$。

接下来 $n$ 行，第 $i$ 行表示编号为 $i$ 的数列。每一行的第一个非负整数 $l_i$ 表示初始第 $i$ 号序列的数字个数，接下来有 $l_i$ 个非负整数 $a_{i,j}$ 按顺序表示数列中的数字。假定 $C_l = \sum l_i$ 代表输入序列长度之和，则保证 $C_l \le 5 \times {10}^5$、$a_{i,j} \le n + q$。

接下来 $q$ 行，每行若干个正整数，表示一个操作，并按照题面描述中的格式输入。

假定 $C_m = \sum m$ 代表所有操作 $3$ 需要拼接的序列个数之和，则保证 $C_m \le 5 \times {10}^5$。

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


title: [NOI2022] 移除石子

description:
你正在玩一个名为“移除石子”的小游戏。

有 $n$ 堆石子排成一行，第 $i$ 堆有 $a_i$ 枚，你的任务是通过如下的操作将所有石子移除：

- 操作一：选择一堆石子，将其中的至少 $2$ 枚石子移除；
- 操作二：选择一个连续的编号区间 $[l, r]$（$1 \le l \le r \le n$）并满足 $r - l \ge 2$，将其中的每一堆石子都恰好移除 $1$ 枚。

你可以采用任意顺序执行任意多次上述两种操作，直到无法再执行操作为止。若最后你能将所有石子全部移除则胜利。

你或许已经开始计算起了诸如“有多少种本质不同的操作方式”的问题，但实际玩起来你却发现自己总是在输。因此，你打算玩个小花招：在游戏开始时，你在手里偷偷藏有 $k$ 枚石子，在执行所有操作之前你**可以且必须**将这些石子放入某一堆或某几堆石子中。你期望这会提高自己的胜率，但也清楚这可能会使自己输掉原本可能胜利的游戏。

现在，你可以自由选择一个初始局面进行游戏，具体而言，每个 $a_i$ 可以选择 $[l_i, r_i]$ 范围内的任意整数。你希望计算出，在多少种初始局面下，自己存在至少一种获胜的方案。由于答案很大，你只需要输出其对 $({10}^9 + 7)$ 取模的结果。**两个初始局面不同，当且仅当存在至少一个 $\boldsymbol{1 \le i \le n}$ 使得两者的 $\boldsymbol{a_i}$ 不相等，注意这里的“初始局面”指的是你放入 $\boldsymbol{k}$ 枚石子之前的局面。**

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

对于每组测试数据，第一行两个整数 $n, k$，分别表示石子堆数和加入的石子个数，接下来 $n$ 行，每行两个非负整数 $l_i, r_i$ 表示每堆石子初始石子数的范围。

outputFormat: 对于每组数据输出一行一个整数，表示可能获胜的局面数对$({10}^9 + 7)$ 取模的结果。


title: 「DTOI-5」进行一个排的重 (Minimum Version)

background:
**本题与 Maximum Version 的区别是所求最值和数据范围不同。**

小 L 热衷于重排数列使之规整。

description:
小 L 有一个长为 $n$ 的序列 $a$，其中每一项 $a_i$ 都是一个 pair $(p_i, q_i)$。

为了让 $a$ 看起来规整一些，他钦定 $p, q$ 分别均为长为 $n$ 的排列。

为了对 $a$ 的规整程度进行量化计算，他给出了一个权值函数 $f(a) = \displaystyle\sum_{i = 1}^n ([p_i > \max_{j = 1}^{i - 1} p_j] + [q_i > \max_{j = 1}^{i - 1} q_j])$。**注意 $i = 1$ 时两个方括号都能取到值，因为我们认为 $\displaystyle\max_{j = 1}^0 p_j = \displaystyle\max_{j = 1}^0 q_j = -\infty$。**

为了让 $a$ 看起来更加规整，他决定分别以某种方式重排 $a$ 得到 $a'$ 使得 $f(a')$ 最小。**注意重排时必须将 $a'_i = (p'_i, q'_i)$ 视为整体。**

他希望你求出 $f(a')_{\min}$ 的值，以及分别有多少个 $a'$ 可以取到 $f(a')_{\min}$。

由于方案数可能很大，你只需要求出结果对 $998244353$ 取模的值。

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

第二行，$n$ 个整数 $p_1, p_2, \cdots, p_n$；

第三行，$n$ 个整数 $q_1, q_2, \cdots, q_n$。

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

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

$$
\def\or{\operatorname{or}}
%\def\arrayscretch{1.5}
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{Subtask}&n\le &\textbf{Points}\cr\hline
\sf1&10&10 \operatorname{pts}\cr\hline
\sf2&500&20 \operatorname{pts}\cr\hline
\sf3&5\times10^3&20 \operatorname{pts}\cr\hline
\sf4&10^5&20 \operatorname{pts}\cr\hline
\sf5&5\times10^5&30 \operatorname{pts}\cr\hline
\end{array}
$$

对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$1 \leq p_i, q_i \leq n$，保证 $p, q$ 均为**排列**。


title: [蓝桥杯 2019 省 A] 填空问题

description:
## A 平方和

### 题目描述

小明对数位中含有 `2`、`0`、`1`、`9` 的数字很感兴趣, 在 $1$ 到 $40$ 中这样的数包括 $1$、$2$、$9$、$10$ 至 $32$、$39$ 和 $40$，共 $28$ 个，他们的和是 $574$，平方和是 $14362$。注意，平方和是指将每个数分别平方后求和。

请问，在 $1$ 到 $2019$ 中, 所有这样的数的平方和是多少?

### 答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

提示：如果你编写程序计算，发现结果是负的，请仔细检查自己的程序，不要怀疑考场的编程软件。

## B 数列求值

### 题目描述

给定数列 $1,1,1,3,5,9,17,\cdots$，从第 $4$ 项开始，每项都是前 $3$ 项的和。求第 $20190324$ 项的最后 $4$ 位数字。

### 答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个 $4$ 位整数（提示: 答案的千位不为 $0$），在提交答案时只填写这个整数，填写多余的内容将无法得分。

## C 最大降雨量

### 题目描述

由于沙之国长年干旱，法师小明准备施展自己的一个神秘法术来求雨。

这个法术需要用到他手中的 $49$ 张法术符, 上面分别写着 $1$ 至 $49$ 这 $494$ 个数字。法术一共持续 $7$ 周，每天小明都要使用一张法术符，法术符不能重复使用。

每周，小明施展法术产生的能量为这周 $7$ 张法术符上数字的中位数。法术施展完 $7$ 周后，求雨将获得成功，降雨量为 $7$ 周能量的中位数。

由于干早太久，小明希望这次求雭的降雨量尽可能大，请大最大值是多少?

### 答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

## D 迷宫

### 题目描述

下图给出了一个迷宫的平面图，其中标记为 $1$ 的为障碍, 标记为 $0$ 的为可以通行的地方。

```
010000
000100
001001
110000
```

迷宫的入口为左上角, 出口为右下角, 在迷宫中, 只能从一个位置走到这个它的上、下、左、右四个方向之一。

对于上面的迷宫, 从入口开始，可以按 `DRRURRDDDR` 的顺序通过迷宫, 一共 $10$ 步。其中 `D`、`U`、`L`、`R`$ 分别表示向下、向上、向左、向右走。

对于下面这个更复杂的迷宫（$30$ 行 $50$ 列)，请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。请注意在字典序中 $\mathrm{D}<\mathrm{L}<\mathrm{R}<\mathrm{U}$ 。（如果你把以下文字复制到文本文件中, 请务必检查复制的内容是否与文档中的一致。

```
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

```

### 答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个字符串, 包含四种字母 `D`、`U`、`L`、`R`，在提交答案时只填写这个字符串, 填写多余的内容将无法得分。

## E RSA 解密

### 题目描述
$\mathrm{RSA}$ 是一种经典的加密算法。它的基本加密过程如下。

首先生成两个质数 $p, q$, 令 $n=p \cdot q$, 设 $d$ 与 $(p-1) \cdot(q-1)$ 互质, 则可 找到 $e$ 使得 $d \cdot e$ 除 $(p-1) \cdot(q-1)$ 的余数为 $1$。

$n, d, e$ 组成了私钥，$n, d$ 组成了公钥。

当使用公钥加密一个整数 $X$ 时（小于 $n$ ), 计算 $C=X^{d} \bmod n$, 则 $C$ 是加 宓后的密文。

当收到密文 $C$ 时，可使用私钥解开，计算公式为 $X=C^{e} \bmod n$ 。

例如，当 $p=5, q=11, d=3$ 时，$n=55, e=27$ 。

若加密数字 $24$，得 $24^{3} \bmod 55=19$ 。

解密数字 $19$，得 $19^{27} \bmod 55=24$ 。

现在你知道公钥中 $n=1001733993063167141, d=212353$, 同时你截获了别人发送的密文 $C=20190324$，请问，原文是多少？

### 答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数，填写多余的内容将无法得分。

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 题的答案
        "The answer of task C", // 双引号中替换为 C 题的答案
        "The answer of task D", // 双引号中替换为 D 题的答案
        "The answer of task E", // 双引号中替换为 E 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}
```


title: [蓝桥杯 2019 省 B] 填空问题

description:
## 试题 $\mathrm{A}$ ：组队

### 【问题描述】

作为篮球队教练，你需要从以下名单中选出 $1$ 号位至 $5$ 号位各一名球员，组成球队的首发阵容。

每位球员担任 $1$ 号位至 $5$ 号位时的评分如下表所示。请你计算首发阵容 $1$ 号位至 $5$ 号位的评分之和最大可能是多少?

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

（在附件中有一个文件 team.txt,内容与上面表格中的相同，请注意第一列是编号)

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B：年号字串

### 【问题描述】

小明用字母 `A` 对应数字 $1$，`B` 对应 $2$，以此类推，用 `Z` 对应 $26$。对于 $27$ 以上的数字，小明用两位或更长位的字符串来对应，例如 `AA` 对应 $27$，`AB` 对应 $28$，`AZ` 对应 $52$，`LQ` 对应 $329$。

请问 $2019$ 对应的字符串是什么?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个大写英文字符串，在提交答案时只填写这个字符串，注意全部大写，填写多余的内容将无法得分。

## 试题 $\mathrm{C}$ ：数列求值

### 【问题描述】

给定数列 $1,1,1,3,5,9,17,\cdots$，从第 $4$ 项开始，每项都是前 $3$ 项的和。求第 $20190324$ 项的最后 $4$ 位数字。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个 $4$ 位整数（提示：答案的千位不为 $0$），在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D：数的分解

### 【问题描述】

把 $2019$ 分解成 $3$ 个各不相同的正整数之和，并且要求每个正整数都不包含数字 $2$ 和 $4$，一共有多少种不同的分解方法?

注意交换 $3$ 个整数的顺序被视为同一种方法，例如 $1000+1001+18$ 和 $1001+1000+18$ 被视为同一种。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E：迷宫

### 【问题描述】

下图给出了一个迷宫的平面图，其中标记为 `1` 的为障碍，标记为 `0` 的为可以通行的地方。

```
010000
000100
001001
110000
```

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。

对于上面的迷宫，从入口开始，可以按 `DRRURRDDDR` 的顺序通过迷宫，一共 $10$ 步。其中 $\mathrm{D}、\mathrm{U}、\mathrm{L}、\mathrm{R}$ 分别表示向下、向上、向左、向右走。

对于下面这个更复杂的迷宫 ($30$ 行 $50$ 列)，请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。请注意在字典序中 $\mathrm{D}<\mathrm{L}<\mathrm{R}<\mathrm{U}$。（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在附件中有一个文件 maze.txt,内容与下面的文本相同）

```plaintext
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
```

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个字符串，包含四种字母 `D`、`U`、`L`、`R`，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

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

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


title: [蓝桥杯 2019 国 A] 填空问题

description:
## 试题 A: 三升序列

### 【问题描述】

对于一个字母矩阵，我们称矩阵中的一个三升序列是指在矩阵中找到三个字母，它们在同一行，同一列，或者在同一 $45$ 度的斜线上，这三个字母从左向、右看、或者从上向下看是递增的。

例如，如下矩阵中

```plaintext
YQPD
BKEZ
AFYV
```

有 `BKZ`、`BEZ`、`AFY`、`AFV`、`AKP`、`DEF` 等 $6$ 个三升序列。注意当三个字母是从左下到右上排列时，从左向右看和从上向下看是不同的顺序。

对于下面的 $30$ 行 $50$ 列的矩阵，请问总共有多少个三升序列? (如果你把 以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在附件中有一个文件 inc.txt，内容与下面的文本相同）

```plaintext
VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX
```

### 【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 B: 最优旅行

### 【问题描述】

中国的高铁四通八达，乘坐方便，小明经常乘坐高铁在城市间旅游。

现在，小明又有了一个长假，他打算继续乘坐高铁旅游。这次，他打算到 下面的城市旅游。

上海、广州、长沙、西安、杭州、济南、成都、南京、昆明、郑州、天津、太原、武汉、重庆、南昌、长春、沈阳、贵阳、福州。

小明打算从北京出发，游览以上每个城市正好一次，最终回到北京。在每 个城市（除北京外），小明都至少停留 24 小时。而当小明决定从一个城市去往另一个城市时，他只会选择有直接高铁连接的城市，不会在中途换乘转车。

在附件中有一个文件 trip.txt 保存了小明可以选择的车次，小明不会 选择其他车次。

小明出发的时间是第 $1$ 天的中午 12:00。请问，小明游览完以上城市正好一次，最终回到北京，最快需要多少分钟（请注意单位为分钟，请注意除北京外的城市需要至少停留 $24$ 小时，即最少停留 $1440$ 分钟)。

### 【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 $\mathrm{C}$ : 骰子制造

### 【问题描述】

骰子是游戏中常用的一个工具，骰子是一个正六面体，六个面分别是 $1$ 到 $6$ 点，每种一个，通常情况下，$1$ 到 $6$ 点的样子如下图所示。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_428d25a9985c915a8589g-05%5B1%5D.jpg)

其中 $1$、$4$、$5$ 点旋转 $90$、$180$、$270$ 度后形状不变，而 $2$、$3$、$6$ 点旋转 $180$ 度后形状不变。

小明要制造一批骰子，他希望制造出来后有意思一点，他希望他制造出来 的䏣子任何两个旋转后都是不相同的。请问，他最多能造出多少个?

### 【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D: 序列求和

### 【问题描述】

学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 $t$，总是可 以找到含有 $t$ 个约数的整数。小明对于含有 $t$ 个约数的最小数非常感兴趣，并 把它定义为 $S_{t}$。

例如 $S_{1}=1，S_{2}=2，S_{3}=4，S_{4}=6，\cdots$。

现在小明想知道，前 $60$ 个 $S_{i}$ 的和是多少? 即 $S_{1}+S_{2}+\cdots+S_{60}$ 是多少?

### 【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E: 无方集合

### 【问题描述】

小明不是很喜欢完全平方数，他甚至不喜欢加起来是完全平方数的两个数。今天，他想从 $1$ 到 $100$ 中选择一些数组成一个集合，要求不选择任何一个完全平方数，集合中任意两个数相加也不能是完全平方数。请问，小明最多能选出多少个数。

### 【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

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

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


title: [蓝桥杯 2019 国 B] 填空问题

description:
## 试题 $\mathrm{A}$ : 平方序列

### 【问题描述】

小明想找到两个正整数 $X$ 和 $Y$，满足

- $2019<X<Y$

- $2019^{2}，X^{2}，Y^{2}$ 组成等差数列。

请你求出在所有可能的解中，$X+Y$ 的最小值是多少?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 $\mathrm{B}$ : 质数拆分

### 【问题描述】

将 $2019$ 拆分为若干个两两不同的质数之和，一共有多少种不同的方法?

注意交换顺序视为同一种方法，例如 $2+2017=2019$ 与 $2017+2=2019$ 视为同一种方法。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 $\mathrm{C}$ : 拼接

### 【问题描述】

小明要把一根木头切成两段，然后拼接成一个直角。

如下图所示，他把中间部分分成了 $n \times n$ 的小正方形，他标记了每个小正方 形属于左边还是右边。然后沿两边的分界线将木头切断，将右边旋转向上后拼 接在一起。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/P8690.png)

要求每个小正方形都正好属于左边或右边，而且同一边的必须是连通的。在拼接时，拼接的部位必须保持在原来大正方形里面。

请问，对于 $7 \times 7$ 的小正方形，有多少种合法的划分小正方形的方式。

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D: 求值

### 【问题描述】

学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 $t$，总是可 以找到含有 $t$ 个约数的整数。小明对于含有 $t$ 个约数的最小数非常感兴趣，并 把它定义为 $S_{t}$。

例如 $S_{1}=1，S_{2}=2，S_{3}=4，S_{4}=6，\cdots$。

现在小明想知道，当 $t=100$ 时，$S_{t}$ 是多少? 即 $S_{100}$ 是多少?

### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E: 路径计数

### 【问题描述】

从一个 $5 \times 5$ 的方格矩阵的左上角出发，沿着方格的边走，满足以下条件的 路线有多少种?

- 总长度不超过 $12$;

- 最后回到左上角;

- 路线不自交;

- 不走出 $5 \times 5$ 的方格矩阵范围之外。

如下图所示，$\mathrm{ABC}$ 是三种合法的路线。注意 $\mathrm{B}$ 和 $\mathrm{C}$ 由于方向不同，所以 视为不同的路线。
![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/P86902.png)
### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

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

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


title: [蓝桥杯 2019 国 C] 填空问题

description:
## 试题 $\mathrm{A}$ ：奇数倍数

### 【问题描述】

请你找到最小的整数 $X$ 同时满足:

- $X$ 是 $2019$ 的整倍数

- $X$ 的每一位数字都是奇数

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 $\mathrm{B}$ : 递增序列

### 【问题描述】

对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个 字母，它们在同一行，同一列，或者在同一 45 度的斜线上，这两个字母从左向 右看、或者从上向下看是递增的。

例如，如下矩阵中

```
LANN
QIAO
```

有 `LN`、`LN`、`AN`、`AN`、`IO`、`AO`、`LQ`、`AI`、`NO`、`NO`、`AQ`、`IN`、`AN` 等 $13$ 个 递增序列。注意当两个字母是从左下到右上排列时，从左向右看和从上向下看 是不同的顺序。

对于下面的 $30$ 行 $50$ 列的矩阵，请问总共有多少个递增序列? (如果你把 以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在附件中有一个文件 inc.txt，内容与下面的文本相同）

```plaintext
VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX
```

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 $\mathrm{C}$ : 平方拆分

### 【问题描述】

将 2019 拆分为若干个两两不同的完全平方数之和，一共有多少种不同的方法?

注意交换顺序视为同一种方法，例如 $13^{2}+25^{2}+35^{2}=2019$ 与 $13^{2}+35^{2}+$ $25^{2}=2019$ 视为同一种方法。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 D: 最优旅行

### 【问题描述】

中国的高铁四通八达，乘坐方便，小明经常乘坐高铁在城市间旅游。

现在，小明又有了一个长假，他打算继续乘坐高铁旅游。这次，他打算到下面的城市旅游。

上海、广州、长沙、西安、杭州、济南、成都、南京、昆明、郑州、天津、太原、武汉、重庆、南昌、长春、沈阳、贵阳、福州。

小明打算从北京出发，游览以上每个城市正好一次，最终回到北京。在每个城市（除北京外），小明都至少停留 $24$ 小时。而当小明决定从一个城市去往另一个城市时，他只会选择有直接高铁连接的城市，不会在中途换乘转车。

在附件中有一个文件 trip.txt 保存了小明可以选择的车次，小明不会 选择其他车次。

小明出发的时间是第 $1$ 天的中午 12:00。请问，小明游览完以上城市正好一次，最终回到北京，最快需要多少分钟（请注意单位为分钟，请注意除北京外的城市需要至少停留 $24$ 小时，即最少停留 $1440$ 分钟)。

### 【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

## 试题 E: 骰子制造

### 【问题描述】

骰子是游戏中常用的一个工具，骰子是一个正六面体，六个面分别是 $1$ 到 $6$ 点，每种一个，通常情况下，$1$ 到 $6$ 点的样子如下图所示。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_428d25a9985c915a8589g-05%5B1%5D.jpg)

其中 $1$、$4$、$5$ 点旋转 $90$、$180$、$270$ 度后形状不变，而 $2$、$3$、$6$ 点旋转 $180$ 度后形状不变。

小明要制造一批骰子，他希望制造出来后有意思一点，他希望他制造出来的䏣子任何两个旋转后都是不相同的。请问，他最多能造出多少个?

### 【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

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

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


title: [蓝桥杯 2019 国 C] 数正方形

description:
在一个 $N \times N$ 的点阵上，取其中 $4$ 个点恰好组成一个正方形的 $4$ 个顶点，一共有多少种不同的取法？

由于结果可能非常大，你只需要输出模 $10^9 + 7$ 的余数。

![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_4ab10c5eb27e3dea37d8g-09.jpg)

如上图所示的正方形都是合法的。

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

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

hint:
对于所有评测用例，$2 ≤ N ≤ 10^6$。

蓝桥杯 2019 年国赛 C 组 G 题


title: [蓝桥杯 2019 国 AC] 大胖子走迷宫

description:
小明是个大胖子，或者说是个大大胖子，如果说正常人占用 $1\times1$ 的面积，小明要占用 $5\times5$ 的面积。

由于小明太胖了，所以他行动起来很不方便。当玩一些游戏时，小明相比小伙伴就吃亏很多。小明的朋友们制定了一个计划，帮助小明减肥。计划的主要内容是带小明玩一些游戏，让小明在游戏中运动消耗脂肪。走迷宫是计划中的重要环节。

朋友们设计了一个迷宫，迷宫可以看成是一个由 $n\times n$ 个方阵组成的方阵，正常人每次占用方阵中 $1\times1$ 的区域，而小明要占用 $5\times5$ 的区域。小明的位置定义为小明最正中的一个方格。迷宫四周都有障碍物。为了方便小明，朋友们把迷宫的起点设置在了第 $3$ 行第 $3$ 列，终点设置在了第 $n-2$ 行第 $n-2$ 列。

小明在时刻 $0$ 出发，每单位时间可以向当前位置的上、下、左、右移动单位 $1$ 的距离，也可以停留在原地不动。小明走迷宫走得很辛苦，如果他在迷宫里面待的时间很长，则由于消耗了很多脂肪，他会在时刻 $k$ 变成一个胖子，只占用 $3\times3$ 的区域。如果待的时间更长，他会在时刻 $2\times k$ 变成一个正常人，只占用 $1\times1$ 的区域。注意，当小明变瘦时迷宫的起点和终点不变。

请问，小明最少多长时间能走到迷宫的终点。注意，小明走到终点时可能变瘦了也可能没有变瘦。

inputFormat:
输入的第一行包含两个整数 $n$，$k$。
接下来 $n$ 行，每行一个由 $n$ 个字符组成的字符串，字符为 `+` 表示为空地，
字符为 `*` 表示为阻碍物。

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

hint:
对于 $30 \%$ 的评测用例, $1 \leq n \leq 50$。

对于 $60 \%$ 的评测用例, $1 \leq n \leq 100$。

对于所有评测用例, $1 \leq n \leq 300$，$1 \leq k \leq 1000$。

蓝桥杯 2019 年国赛 A 组 F 题（C 组 I 题）。


title: [蓝桥杯 2019 国 AC] 估计人数

description:
给定一个 $N \times M$ 的方格矩阵，矩阵中每个方格标记 `0` 或者 `1` 代表这个方格是不是有人踩过。

已知一个人可能从任意方格开始，之后每一步只能向右或者向下走一格。走了若干步之后，这个人可以离开矩阵。这个人经过的方格都会被标记为 `1`，包括开始和结束的方格。注意开始和结束的方格不需要一定在矩阵边缘。

请你计算至少有多少人在矩阵上走过。

inputFormat:
输入第一行包含两个整数 $N$、$M$。
以下 $N$ 行每行包含一个长度为 $M$ 的 01 串，代表方格矩阵。

hint:
对于所有评测用例, $1 \leq N, M \leq 20$, 标记为 `1` 的方格不超过 $200$ 个。

蓝桥杯 2019 年国赛 A 组 G 题（C 组 H 题）。


title: [蓝桥杯 2019 国 AC] 轨道炮

description: 小明在玩一款战争游戏。地图上一共有 $N$ 个敌方单位，可以看作 2D 平面上的点。其中第 $i$ 个单位在 $0$ 时刻的位置是 $(X_i, Y_i)$，方向是 $D_i$ (上下左右之一, 用 `U`/`D`/`L`/`R` 表示)，速度是 $V_i$。小明的武器是轨道炮，只能使用一次，不过杀伤力巨大。小明可以选择在某个非负整数时刻释放轨道炮，轨道炮一次可以消灭在一条直线 (平行于坐标轴) 上的所有敌方单位。请你计算小明最多能消灭多少敌方单位。

inputFormat:
输入第一行包含一个整数 $N$。
以下 $N$ 行每行包含 $3$ 个整数 $X_i$, $Y_i$, $V_i$，以及一个大写字符 $D_i$。

hint:
对于所有评测用例，$1 \le N \le 1000$，$-10^6 \le X_i, Y_i \le 10^6$，$0 \le V_i \le 10^6$。

蓝桥杯 2019 年国赛 A 组 H 题（C 组 J 题）