title: [POI2018] Prawnicy

background: **题目译自 [POI XXV - I etap](https://sio2.mimuw.edu.pl/c/oi25-1/dashboard/) 「[Prawnicy](https://sio2.mimuw.edu.pl/c/oi25-1/p/pra/)」**

description:
“Bajtazar 父子”律师事务所刚刚收到一位非常重要的客户的订单。案件严重、紧急，需要与律师事务所的律师举行会议。每个律师都有一段固定的空闲时间可以参加会议。你应该选择这样的 $k$ 位律师，以便召开会议的时间（即他们都空闲的时间）尽可能长。

[简要题意](https://www.luogu.com.cn/problem/U252799)

inputFormat:
第一行包含两个整数 $n$ 和 $k\ (1\le k\le n)$，以一个空格隔开，表示事务所雇用的律师人数和召开会议所需的律师人数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i$ 和 $b_i\ (1\le a_i<b_i\le 10^9)$，以一个空格隔开，表示第 $i$ 个律师在**时刻 $a_i$ 和时刻 $b_i$ 之间**是空闲的。

outputFormat:
第一行输出一个整数，表示会议可能的最大时长。你可以假设你能够召开至少 $1$ 人的会议。

第二行输出空格分隔的 $k$ 个数，代表参加会议的律师编号（从 $1$ 开始）。如果有多个正确答案，您的程序应输出其中任何一个。

hint:
#### 样例解释

三位律师会议可能的最大时长是 $4$。编号为 $1$、$2$ 和 $4$ 的律师可以参加，持续时间从 $4$ 到 $8$。另一个同样好的方案是让编号为 $2$、$4$ 和 $5$ 的律师参加，持续时间从 $5$ 到 $9$。

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

#### 附加样例

参见 `pra/pra*.in` 和 `pra/pra*.out`：

- 附加样例 $1$：$1$ 组数据，$n=7$，$k=3$，且选择律师的方案有两种。

- 附加样例 $2$：$1$ 组数据，$n=k=1000$，$a_i=i$，$b_i=10^6+i$；

- 附加样例 $3$：$1$ 组数据，$n=1000$，$k=1$，$a_i=2i-1$，$b_i=2i$；

#### 数据范围与提示

测试集分为以下子任务。每个子任务的测试由一个或多个单独的测试组组成。

| Subtask # | 额外限制                         | 分值  |
|:---------:|:----------------------------:|:---:|
| $1$         | $n\le 20$       | $20$  |
| $2$         | $n\le 300$，$a_i,b_i\le 300$      | $15$  |
| $3$         | $n\le 5000$       | $15$  |
| $4$         | $n\le 10^6$，$k\in \{1,n\}$       | $15$  |
| $5$         | $n\le 10^6$       | $35$  |

如果你的程序在第一行输出了正确的时长，但其余的输出是错误的，那么你将获得 $40\%$ 的分数。


title: string[_view]

type: P

background:
C++ 的 string 类是一个功能强大的字符串类，然而由于其字符串算法和内存管理绑定的机制，所以在处理 C 风格字符串时效率低下。

为了解决这个问题，C++17 标准引入了 string\_view 类型，将内存管理和字符串算法分离，从而更好地适配了 C 风格字符串的处理。

description:
你需要模拟一个简单的 C++ 程序，该程序的每一行必然为如下两种形式之一：

- `string <variable-name>(<initializer>);`
- `string_view <variable-name>(<initializer>);`

其中 `variable-name` 为声明的变量名（保证之前未出现过，且长度不超过 $10$），`initializer` 为初始化该变量的内容，可以是：

- 字符串字面量，即用双引号引起的字符串（形如 `"abc"`）；
- 之前出现过的变量名 `source`，此时应将 `source` 对应的字符串赋给 `variable-name`。

具体而言，将任意一个字符串 $s$ 赋给 string 类型会进行 $|s|$ 次字符拷贝，而赋给 string\_view 类型不会拷贝字符。其中 $|s|$ 为字符串 $s$ 的长度。

你需要计算出该程序中字符拷贝的总次数。

inputFormat:
第一行输入一个整数 $L$，代表程序行数。

接下来 $L$ 行，输入一段代码。

outputFormat: 输出一个整数，代表字符拷贝总次数。

samples:
6
string a("cxyakioi");
string_view b("cxyakapio");
string c(b);
string_view d(a);
string_view cxyakioi(c);
string cxyakapio(d);

hint:
  对于每组数据，保证代码长度均不超过 $10^4$（不包括换行符）。

保证字符串字面量（除去两侧引号）和变量名中只有拉丁字母，且给定的代码严格满足题目要求。

### 子任务

|  #   |            特殊性质            | 分值 |
| :--: | :----------------------------: | :--: |
|  0   |              样例              | 0  |
|  1   | 所有变量均为 string\_view 类型 | 10 |
|  2   |    只使用字符串字面量初始化    | 20 |
|  3   |               -                | 70 |

---

好消息：GCC 9.3.0 支持 string_view。

坏消息：NOI 不开 C++17。


title: 「DTOI-5」#1f1e33

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

In the middle of night.

description:
定义函数 $f(n) = \displaystyle\sum_{i = 1}^n \sum_{j = 1}^n \sum_{k = 1}^n [i + j + k = n] \operatorname{lcm}(i, \gcd(j, k))$

给定 $n$，对于所有 $1 \leq i \leq n$，**求出所有** $f(i) \bmod 998244353$ 的值。

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

outputFormat: 一行，$n$ 个整数，表示所有 $f(i) \bmod 998244353$ 的值。

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

$$
\def\or{\operatorname{or}}
%\def\arrayscretch{1.5}
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{测试点编号}&n= &\textbf{Points}\cr\hline
\sf1&100&10 \operatorname{pts}\cr\hline
\sf2&10^3&10 \operatorname{pts}\cr\hline
\sf3&10^4&20 \operatorname{pts}\cr\hline
\sf4&10^5&20 \operatorname{pts}\cr\hline
\sf5&/&40 \operatorname{pts}\cr\hline
\end{array}
$$
对于 $100\%$ 的数据，$1 \leq n \leq 10^6$。


title: 「LAOI-1」积水

description:
地表坑洼不平，每当暴雨来临地面上都会有一个个水洼。
又有一场暴雨即将来临，你决定改造地面来减少积水。
地面可抽象为一个长度为 $n$ 的正整数序列 $a$，其中 $a_i$ 表示当地的海拔高度。
下暴雨时将会汇聚在低洼处无法向两侧流走，比如一个序列 $a=[3,1,5,1,2,3]$。
在下雨后的积水如图所示（有 $5$ 格积水）：

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

由于人手不足，现在只来得及改变一个地方的海拔高度为任意正整数。

问改造后积水最少有几格。

inputFormat:
第一行一个整数 $T$。
接下来共 $T$ 组数据，每组数据占两行。
对于每组数据，第一行一个整数 $n$，表示序列长度。
第二行 $n$ 个整数，表示序列 $a$。

outputFormat: 对于每组数据输出一行一个整数，最小的积水格数。


title: 「LAOI-1」Bash Game-Plus

description:
>巴什博弈：有一堆 $n$ 个物品，两名玩家轮流从中拿取物品。每次至少拿 $1$ 个，至多拿 $m$ 个，不能不拿，最终将物品拿完者获胜。

我们给这个游戏增加一些规则：

有一堆 $n$ 个物品，甲和乙轮流从中拿取物品，甲先拿。每次至少拿 $1$ 个，至多拿 $m$ 个，最终将物品拿完者获胜。
现在新加入一条规则：**也可以不拿**，但每当有一名玩家选择不拿物品时，接下来的 $k$ 次操作中两名玩家都不可以不拿。

举个例子，当 $k=3$ 时，如果甲在某一次操作中没有拿物品，那么接下来乙、甲、乙三轮都必须拿至少 $1$ 件物品。然后又轮到甲了，这次甲就可以再次选择不拿。

甲乙两人一共进行了 $t$ 次游戏。对于每次游戏，你需要告诉甲他有没有必胜策略。

inputFormat:
第一行两个正整数 $t,op$。$op=1$ 时取消新增加的规则，但是也需要正常读入 $k$。

接下来的 $t$ 行，每行三个正整数 $n,m,k$。

outputFormat: 对于每轮游戏，如果甲有必胜策略，那么输出 `Yes`。否则输出 `No`。


title: [APC001] A - CT

background:
Compressed Towel.

~~什么，这不是公开赛，这是压缩毛巾，遇水变大变高~~。

description:
这是一个有魔力的压缩毛巾，可以无限变大。

压缩毛巾的初始长、宽、高分别为 $a, b, h$ 厘米。它遇到水 $k$ 次，每次遇到水，长宽高增加 $1$ 厘米。请输出最后压缩毛巾的体积。单位为立方厘米。

但是某人觉得这题太简单了，懒惰的他把这题丢给了你，所以你需要做出这道题。

inputFormat: 四个数，分别为 $a,b,h,k$。

outputFormat:
一个数表示答案，由于答案可能过大，输出其 $\bmod~988444333$ 的值。

**请注意本题的模数**。

hint:
### 样例解释 $1$

计算可得 $(1+5)\times(1+5)\times(4+5)=6\times6\times9=324$。

### 样例解释 $2$

请注意压缩毛巾可以不遇到水。

### 数据范围

对于 $100\%$ 的数据，$1\leq a,b,h\leq 500$，$0\leq k\leq 500$。


title: [NOI2023] 桂花树

description:
小 B 八年前看到的桂花树是一棵 $n$ 个节点的树 $T$，**保证 $T$ 的非根结点的父亲的编号小于自己**。给定整数 $k$，称一棵 $(n+m)$ 个节点的有根树 $T^{\prime}$ 是繁荣的，当且仅当以下所有条件满足：

1. 对于任意满足 $1 \le i,j \le n$ 的 $(i,j)$，在树 $T$ 和树 $T^{\prime}$ 上，节点 $i$ 和 $j$ 的最近公共祖先编号相同。
2. 对于任意满足 $1 \le i,j \le n + m$ 的 $(i,j)$，在树 $T^{\prime}$ 上，节点 $i$ 和 $j$ 的最近公共祖先编号不超过 $\max(i,j)+k$。

**注意题目中所有树的节点均从 $1$ 开始编号，且根结点编号为 $1$。$T^{\prime}$ 不需要满足非根结点的父亲编号小于自己。**

小 B 想知道有多少棵 $(n+m)$ 个节点的树是繁荣的，认为两棵树不同当且仅当存在某一个节点在两棵树上的父亲不同。你只输出方案数在模 $(10^9+7)$ 意义下的值。

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

输入的第一行包含两个整数 $c,t$，分别表示测试点编号和测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

输入的第一行包含三个整数 $n,m,k$。

输入的第二行包含 $n-1$ 个整数 $f_2,f_3,\dots,f_n$，其中 $f_i$ 表示 $T$ 中节点 $i$ 的父亲节点编号。

outputFormat: 对于每组测试数据输出一行一个整数，表示繁荣的树的数量在模 $(10^9+7)$ 意义下的答案。

samples:
见附件中的 tree/tree2.in。
见附件中的 tree/tree2.ans。

samples:
见附件中的 tree/tree3.in。
见附件中的 tree/tree3.ans。

samples:
见附件中的 tree/tree4.in。
见附件中的 tree/tree4.ans。


title: [Ynoi2004] rpmtdq

description:
给定一棵有边权的无根树，需要回答一些询问。

定义 $\texttt{dist(i,j)}$ 代表树上点 $i$ 和点 $j$ 之间的距离。

对于每一组询问，会给出 $l,r$，你需要输出 $\min(\texttt{dist(i,j)})$ 其中 $l\leq i < j \leq r$。

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

接下来 $n-1$ 行，每行三个整数 $x,y,z$ 表示一条连接 $x,y$ 边权为 $z$ 的树边，输入保证构成一棵树。

之后一行一个数 $q$，表示询问个数。

之后 $q$ 行，每行两个整数 $l,r$ 表示一组询问，如果对于一组询问，找不到任何二元组 $(i,j)$ 满足 $l\le i<j\le r$，则输出 $-1$。

outputFormat: 输出 $q$ 行，每行一个整数，表示这组询问的答案。

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

对于$100\%$的数据，满足 $n\leq2\times 10^5$，$q\leq 10^6$，$1\le z\le 10^9$。


title: [Ynoi2002] Adaptive Hsearch&Lsearch

description:
有 $n$ 个点 $p_1,p_2,\dots,p_n$ 在二维平面上。

有 $q$ 次询问，在第 $i$ 个询问中，给定两个数 $l_i,r_i$ ($1\leq l_i< r_i\leq n$)，你需要找到一对 $(u,v)$ 满足 $l_i\leq u<v\leq r_i$，$p_u$ 和 $p_v$ 之间的欧几里得距离 $\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$ 最小。

inputFormat:
第一行两个数 $n,q$ 表示点数以及询问数。

之后 $n$ 行，第 $i$ 行包含两个整数 $x_i,y_i$ 表示 $p_i$ 的坐标。

之后 $q$ 行，第 $i$ 行包含两个整数 $l_i,r_i$ ($1\leq l_i< r_i\leq n$) 表示第 $i$ 个询问。

outputFormat: 对每个询问，输出一行一个整数表示最小的 $(x_u-x_v)^2+(y_u-y_v)^2$。

hint:
Idea：Claris，Solution：Claris，Code：Claris，Data：Claris&nzhtl1477

对于 $100\%$ 的数据，满足 $2 \leq n\leq 250\,000$, $1\leq q\leq 250\,000$，$1\leq x_i,y_i\leq 10^8$。


title: [Ynoi2002] Optimal Ordered Problem Solver

description:
给定 $n$ 个点 $(x_i,y_i)_{i=1}^n$，你需要按顺序处理 $m$ 次操作。每次操作给出 $o,x,y,X,Y$，

- 首先进行修改：
  - 若 $o=1$ 则将满足 $x_i\le x,\;y_i\le y$ 的点的 $y_i$ 修改为 $y$；
  - 若 $o=2$ 则将满足 $x_i\le x,\;y_i\le y$ 的点的 $x_i$ 修改为 $x$。
- 然后进行查询，询问满足 $x_i\le X,\;y_i\le Y$ 的点数。

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

接下来 $n$ 行每行两个整数 $x_i,y_i$。

接下来 $m$ 行每行五个整数 $o,x,y,X,Y$，表示一次操作。

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

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

对于所有数据，$1 \le n,m \le 10^6$，$1\le x_i,y_i,x,y,X,Y\le n$。

子任务 1（20 分）：$n,m\le 10^3$；

子任务 2（20 分）：$x_i,y_i,x,y,X,Y$ 独立地在 $1$ 到 $n$ 内均匀随机选取；

子任务 3（20 分）：$o=1$；

子任务 4（20 分）：$n,m\le 3\times 10^5$，依赖子任务 1；

子任务 5（20 分）：无特殊限制，依赖子任务 1、2、3、4。


title: [Ynoi2002] Goedel Machine

background:
# 1.前言

哥德尔机 [1] 是由 LSTM 之父 Jürgen Schmidhuber 提出的一种可学习的通用问题求解器。本文将对该模型进行描述与讨论，并且说明这个模型拥有许多重要的性质，这些性质是我们认为通用人工智能所必需的。

# 2.相关概念

## 学习

学习指模型对模型自身的参数（同一个模型在参数不同时有不同的行为）进行修改。用于对自己进行修改的方法叫做学习算法。

## 元学习

元学习指模型拥有通过学习修改自己的学习算法的能力。有大量证据指示人类拥有比较强的元学习的能力。

### 元学习分层

不可学习的方法没有学习能力，比如解决 OI 题的程序，坦克世界的固定线路看到人就停车的脚本等。

常见的机器学习方法，比如朴素的神经网络方法没有元学习能力，因为学习算法是不可学习的梯度下降算法。支持向量机没有元学习能力，因为学习算法是确定的，等。

专门设计了元学习特性的神经网络有元学习能力，但是没有元元学习能力，也就是说不能对学习自己学习算法的算法进行学习。

假设你想设计一种学习算法：

初始时，你想让你的算法可学习，于是设计了初始的学习算法。

然后你想让你的初始学习算法可学习，于是设计了元学习算法。

然后你想让你的元学习算法可学习，于是设计了元元学习算法。

这样每一步你都必须设计新的学习算法，用于之前的学习算法的学习。设计第 $i$ 层的学习算法时，这个学习算法可以优化前 $i-1$ 层，但是对第 $i$ 层的优化需要第 $i+1$ 层后的方法。分层不是必需的，这里分层是人为设计的，因为你人为设计了分层结构，所以你需要设计无限层的元学习算法。

一直这样递归下去可以发现现有机器学习方法的一个问题：因为不能人工设计无限层的元学习算法，所以在某一层之后一定不可学习。这样会导致人工设计可以一直让模型变强，因为设计了第 $i$ 层元学习的模型不会比只设计了前 $i-1$ 层元学习的模型弱，但是这个过程永不收敛。这样的模型不具备一种**不可改进性**，即在给定足量的计算资源下，这个模型是最优的。

哥德尔机以及类似的构造尝试将所有层级的元学习用同一个东西去泛化，将任意层的元学习问题变成一层普通的学习问题。要实现这样的功能，我们需要一个足够强的优化器。弱的优化器，比如梯度下降的神经网络，面临的问题是无法使用梯度下降去优化模型梯度下降的过程，也就是说无法直接用学习算法去处理元学习层面的优化。于是元学习特性需要人为设计，也就是说需要设计优化元学习任务的优化器，而这样会导致该优化器无法用已设计好的方法优化，需要继续设计新的对应的优化算法。这样分层的元学习需要无限的设计，是神经网络方法最大的问题之一。

### 不分层元学习/无限层元学习

哥德尔机没有元学习分层的设计，因为其架构会将所有优化问题用同样的方法优化，并且该优化方法可以优化自身，所以哥德尔机拥有不分层的元学习能力，或者可以叫做无限层元学习的能力。在给定足量的计算资源下，哥德尔机不弱于任何其它可计算的机器学习模型。

实际上存在一些元学习算法是递归的，即存在一种元学习算法，第 $i$ 层可以对前 $i-1$ 层进行优化，且对任意 $i$，这个算法都是相同的，所以只需要有限的人为设计。我们认为这类方法是有一些问题的，不如不分层的元学习算法，这里不展开讨论。

元学习和学习实际上不可区分，这个会在后续进行讨论。

## 强化学习

模型与环境交互并优化由环境提供的奖励。

### 马尔可夫决策过程

时间被分为一些离散的时间步，模型每个时刻从环境中获取输入信息（包括环境提供的奖励），并能从有限种对环境的操作中选一部分执行，环境由这一时刻的状态以及模型采取的操作计算出环境下一时刻的状态。

## 通用人工智能/完全人工智能/人工广义智能

这些词语是 Artificial General Intelligence 的中文翻译，该词语代表一个可以在各个领域达到人类顶尖水平甚至超越的人工智能模型。

通用人工智能**没有准确的定义**，不同人对通用人工智能应该有什么样的能力看法不同。

## 自编程/自修改/自进步

这三个词语指模型的一种能力，有这种能力的模型可以通过修改自己来提升自己的表现。一般提升表现指可以在监督学习任务中通过更多的数据，或在强化学习任务中获得更大的预期奖励。

## 自指

一个模型是完全自指的，表示某个模型可以在内部描述自己的所有性质。虽然人类不是一个完全自指的模型，但是人类可以描述关于自己的部分性质。

自指常用于构建悖论，如：

1. "这句话是错的" 是对的还是错的？

2. 罗素悖论：一个理发师只给不理自己头发的人理发，那这个理发师是否给自己理发？

3. 停机问题：一个图灵机如果判定出自己停机，则不停机。

4. 哥德尔不完备性定理。

哥德尔机是一个可以完全自指的模型。哥德尔机的作者认为 "意识" 的本质是自指，即模型可以意识到自己的存在。哥德尔机的学习算法可以完全自指，也就是说可以用学习算法处理学习算法的学习，甚至完全覆写掉初始的学习算法。

## 可计算性

程序在不限制空间并且不限制字长时，能在有限时间内完成处理的问题是可计算的问题所构成的集合。

## 图灵机

本文中我们直接把 图灵机 当成 C++ 语言写成的代码，不限制空间并且不限制字长。

### 通用图灵机

用 C++ 语言显然可以模拟执行 C++ 语言。假设我们写出了一份 C++ 语言代码 A，用于执行任何其它 C++ 语言写出的代码。则当我们想执行 C++ 代码 B 时，可以将 B 做为 A 的输入，并执行 A。这样的代码 A 叫做 通用图灵机。

## 不可区分性

有许多人类设计的分层结构是不可区分的，如：

1. 数据与程序不可区分：这里我们顺便解释中文房间悖论。中文房间指给定一个黑箱，将一个不会中文的人和一个翻译器一起放入。在房间外的人向内部提供中文文章，内部的人将文章输入翻译器后直接得到翻译后的结果，并将结果输出，此时从外部看来，无法判定内部的人是否会中文。这个悖论实际上等价于：现在有一个通用图灵机，以及一份通用人工智能的代码。如果我们将通用图灵机看做模型（程序），将通用人工智能看做数据进行执行（对于通用图灵机而言，一个图灵机的程序可以是数据，并且做为数据的程序可以被执行），则这里可以认为这个通用图灵机在给定数据下是一个通用人工智能。也就是说我们可以将非平凡的部分：通用人工智能，在程序和数据两边任意转移，但必须在某一边解决这个本质问题。

2. 监督学习的数据和模型的先验（初始引入的知识）不可区分，强化学习的人类知识和模型的 reward 不可区分：监督学习模型的 loss 函数可以内嵌任意复杂的信息，包括数据集中的所有信息，这种情况下模型的 loss 是模型的先验的一部分。强化学习模型 reward 函数可以内嵌任意复杂的信息，包括关于环境的先验，以及人类知识。如 AlphaGo 算法中使用了 MCTS 搜索算法做为探索先验，这样的先验（搜索）就是一种人类知识。

3. 模型关于自己的先验与模型关于环境的先验不可区分：这个在后续会进行讨论。

4. 学习和元学习不可区分：假设模型分为学习算法和模型主体部分，学习算法经过学习后被修改了，则这里可以看做是元学习。但如果将整个模型做为一个整体来看待，学习实际上改变了模型的一些参数，是普通的学习。从学习和元学习不可区分也可以看出对元学习人为分层是不自然的，应该将元学习的优化视为普通学习处理。

由于不可区分性，一般来说我们用功能而不是具体的结构来衡量模型的能力。比如对于中文房间悖论，可以认为一个有翻译器的人类就是懂得中文的，因为和懂得中文的人表现一致，一个没有翻译器的人类是不懂得中文的。

同理，由于不可区分性，对于“理解”和“意识”的讨论都是无意义的，因为我们用功能而不是具体的结构来衡量模型的能力。

# 3.简介

几乎所有已知的用于解决问题的算法（包括证明搜索器，监督学习，强化学习等）都在元学习方面有欠缺，理由在元学习分层中有描述。人类需要一直不断地设计新的更好的算法（有更多层元学习的算法），并且提供计算资源对这些算法进行测试。

如何才能消除人类的必要性？为了方便描述，我们定义了学习，学习指模型对模型自身的参数进行修改。对自己进行修改的方法叫做学习算法。最简单的想法就是让机器可以进行任意复杂的学习，也就是说学习方法需要足够强，比如从所有可计算的程序中选出一个最高效的学习算法，利用这个学习算法修改自己。

为了解决这个问题，作者设计了一类最优的，完全自指的，通用的问题求解器——哥德尔机。哥德尔机与一个部分可观测的环境交互，并且原则上可以无限制地修改自身（学习），唯一的限制是哥德尔机自己的可计算性。哥德尔机的初始算法有能力完全重写自己，这样的重写能力保证哥德尔机是全局最优的。

## 哥德尔机的结构

哥德尔机主要包含公理系统、证明搜索程序、行为程序、目标函数。

# 4.环境和形式化目标

模型的环境处在一个人为设计的硬件中，该硬件可以是通用图灵机，空间有限的图灵机，或抽象的电子计算机。模型是单例的，只有唯一一个同时存在。模型的生命包含一些离散的时间步：$1,2,\dots$，模型的生命在 $T$ 时刻结束，这个时刻可能对模型而言不可见。任何一个时变的变量 $Q$ 在 $t$ 时刻的值可以记作 $Q(t)$。

每一步时间我们的硬件执行一个基本操作，改变硬件的状态 $s$，为不失一般性，$s\in \mathcal S \in B^*$，$B^*$ 表示所有可能的二进制串。每一步时间环境状态可能发生变化，环境状态用 $Env$ 表示，$Env\in \mathcal E$，$\mathcal E$ 表示考虑的环境的集合，这个会在后续进行讨论。硬件有硬编码的转移方程：$F:\mathcal S\times \mathcal E \rightarrow \mathcal S$。对任何 $t>1$，$s(t)=F(s(t-1),Env(t-1))$ 表示当前 $t-1$ 个时刻都结束后，$t$ 时刻还没开始时硬件的状态。
$Env(t)$ 表示 $t$ 时刻的环境，由 $s(t-1)$ 中描述环境变化的变量与环境交互得到，如果环境是随机的，则这里按对应概率进行采样。

定义四个特殊的变量：$time,x,y,p$：

1. $time$ 表示当前时刻。
2. $x$ 表示环境对哥德尔机的输入，对任意 $t>1$，$x(t)\neq x(t-1)$ 可能发生当且仅当哥德尔机输出了一个特定字符串，表示向环境请求输入。这样就可以避免每个时刻只有常数的计算资源，导致不能对输入完全观测（比如复制整个输入所需的计算资源比每个时刻的计算资源多）。
3. $y$ 表示哥德尔机对环境的输出，$y(t)$ 表示一个二进制串。输出可能对环境产生影响，比如输出一个控制指令，指令操作环境中的一个机器人，或者指令打开电视机。
4. $p(1)$ 表示最初哥德尔机的软件，也就是根据环境输入计算出对环境输出的计算过程。初始的 $p(1)$ 可以用一个图灵机表示，所以不是最优的。

每一个时刻 $1\le t\le T$ 模型的目标是最大化预期回报。对于一个确定的 $s$ 和 $Env$，奖励函数可以写做：$u(s,Env):\mathcal S\times \mathcal E\rightarrow \mathcal R$，$u(s,Env)=E_{\mu} \bigg [\sum _{\tau=time} ^T  r(\tau)\bigg | s,Env \bigg ]$，其中 $\mathcal R$ 表示实数，$r(t)$ 表示 $t$ 时刻获得的实数表示的奖励。$E_{\mu}\big(\cdot \big|\cdot\big)$ 表示条件期望，其中 $\mu$ 表示所有可能的环境。

这里需要注意到 $s$ 表示的也是模型的内环境，因为硬件行为完全由模型决定，$Env$ 表示外部环境，$time=time(s)$ 表示 $s$ 状态所在时刻。

可以同时修改奖励函数使得模型倾向于选择更低方差的改进。绝大部分计算机科学的问题都可以用这个设计形式化。

# 5.哥德尔机的基本思想

为了让我们的硬件变成一个有自指能力的哥德尔机，需要设计对应的软件（也就是可运行代码） $p$，该软件需要有修改自己的能力。初始的代码 $p(1)$ 有一个目前不是最优的问题求解器 $e(1)$，用于和环境交互，这个问题求解器可以是任何传统的强化学习算法，同时还有一个通用的证明搜索器，证明搜索器持续地搜索二元组 (程序，证明） 直到对一个 程序 A，搜索到了一个 证明 B，表明：将搜索到的这个程序 A 直接用于修改 $p$ 后得到的程序的预期回报比修改前的 $p$ 更大。之后模型会使用 程序 A 对 $p$ 进行修改，这个修改不止对 $e$ 有效，同时可能影响到 $p$ 中的证明搜索器。

## 自修改公理

在 $t_1$ 时刻，我们使用搜索到的程序 A 来修改 $s(t_1)$ 当且仅当搜索到了证明 B，表示：$u[A(s(t_1)),Env(t_1)]>u[s(t_1),Env(t_1)]$。硬件状态 $s$ 包含了软件 $p$，用 $A(s(t_1))$ 表示用程序 A 对 $t_1$ 时刻的模型的软件进行学习。

哥德尔机还需要引入大量其它的公理才能变得足够强，比如关于环境的公理，以及概率相关的公理。我们使用 $\mathcal A$ 来表示一个足够强的哥德尔机的公理系统。

## 哥德尔不完备定理

我们说一个公理系统是一致的，当且仅当对任意命题 $P$，$P$ 和 非 $P$ 这两个命题不能同时在这个公理系统下被证明。

哥德尔不完备定理指的是：任何一个公理系统，如果是一致的，并且能定义自然数，与自然数的加法，乘法和等于，则一定存在一个命题 $P$，$P$ 和 非 $P$ 在这个公理系统中不可证明。

## 哥德尔机的局限性与优势

哥德尔不完备性定理使得对任意一个足够强的公理系统，一定存在不可证的命题。哥德尔不完备定理不会导致哥德尔机弱，因为如果存在某个对哥德尔机有用的命题，但是这个命题在哥德尔机的公理系统下是不可证的，则对人而言，这个命题在同一个公理系统下也是不可证的，人也无法利用这个命题。

哥德尔机更大的局限性在于，在现实环境中，时间和空间资源是有限的，如果哥德尔机的初始公理设计不够好，会导致即使其拥有极大量资源，也无法搜索出足量有效的自修改程序，导致花费了极大量的资源后还是一个低效的搜索器。

哥德尔机需要引入大量的概率相关的公理，因为有限时间的观测只能产生有限的数据。有限的数据会导致任何证明都不能保证不会和后来的观测数据发生矛盾，所以只能给出证明的置信度，而不能保证证明一定正确。

在一般的环境中，哥德尔机模型难以进行严格控制变量的实验，难以收集独立同分布的数据，难以短时间内发现环境在大时间尺度上的改变，这导致对概率的严格推断难以证明有用的结论，因此哥德尔机加入普通的概率公理可能也证明不出任何有用的东西。

这样的问题导致哥德尔机不像是一个形式系统，不像一个证明搜索器，如果把初始的软件 $p$ 看做是一个模型初始的学习算法，自修改看做是学习，哥德尔机更像是一个程序搜索器。这种情况下，不一致或者过弱的公理系统对应一个不完备的初始学习算法，比如神经网络。

哥德尔机的优势在于，哥德尔机可以对自己的初始算法进行任意的改动，并且现有的其它方法都无法做到这一点，比如神经网络无法学习自己的梯度下降学习法，有元学习的神经网络无法学习自己的元学习算法，搜索器无法学习自己的搜索策略等。这里的本质区别是哥德尔机的学习比这些模型强，强到可以完全复写掉初始的学习算法，而其它模型只能修改初始学习算法的一部分。

# 6.全局最优性定理

## 自修改公理与全局最优

对任何形式化的奖励函数 $u$，假设哥德尔机公理 $\mathcal A$ 是一致的，则任何自修改公理推出的自修改程序 $p$ 是全局最优的：在执行自修改 $p$ 之前哥德尔机的最大预期回报比执行 $p$ 之后的低。

这里的自修改看上去像是一种贪心算法，每次贪心地向更优的方向改进，为什么是全局最优呢？我们可以证明满足自修改公理的程序 $p$ 是对当前哥德尔机的状态而言，所有可能的程序里最优的一个修改。

证明的思路其实很简单，考虑搜索到 $p$ 后，哥德尔机可以采取的两种方案：

1. 执行自修改程序 $p$。

2. 不执行自修改程序 $p$，继续搜索其它程序执行。

第二种方案考虑到了未来会搜索到的所有程序，而哥德尔机证明了第一种方案比第二种方案优，所以程序 $p$ 是在公理 $\mathcal A$ 下，所有程序中最优的一个。

在实践中，这里的最优性应该需要考虑搜索到每个程序的期望代价，比如存在一些自修改，效果比 $p$ 更好，但是搜索到这些自修改需要大量时间，或是执行了自修改 $p$ 后模型可以更快地搜索到其它自修改。也正是因为这些原因，所以哥德尔机证明了执行自修改 $p$ 后有更大的预期回报。

## $O()$-最优性

哥德尔机在任何任务上是 $O()$-最优 的，即与可以证明理论最优的解（如果存在）只在计算资源消耗上差常数倍。这是因为哥德尔机的初始算法即可保证搜索所有程序和证明是 $O()$-最优 的，哥德尔机是不可能比初始算法弱的，所以也是 $O()$-最优 的。

$O()$-最优性 不是一个很强的性质，假设有一个问题，这个问题的最优解是 程序 A，则一个 $O()$-最优 的模型只需要花费常数的计算资源代价搜索到 程序 A，并且证明这个程序比之前模型给出的解优，就可以实现 $O()$-最优。比较两个证明搜索器时也是类似的，一个证明搜索器可以花费常数时间搜索到另一个并证明最优。

$O()$-最优 的优化器需要一个极大的常数启动，这样的优化器最开始效果很差，需要搜索极长时间才可以变得足够强。我们认为这个过程和自然中的进化类似，并在后文讨论二者的相关性。

# 7.bias-optimal searcher（给定先验下最优的搜索器）

bias-optimal searcher（给定先验下最优的搜索器）的定义：

给定先验概率 $P(p|r)$ 表示问题 $r$ 应该选取解 $p$ 的概率。

黑盒函数可以在 $t(p,r)$ 的时间内判断问题 $r$ 是否有解 $p$。

bias-optimal searcher 在有限时间 $T$ 内，对任意问题 $r$，如果有解 $p$ 满足 $t(p,r)\le P(p|r)\times T$ 则能求出问题的一个解。

near-bias-optimal searcher 则放宽条件到 $t(p,r)\le P(p|r)\times T/n$，$n>1$ 是近似比。bias-optimal searcher 有 Optimal Ordered Problem Solver 等已知的构造，这里不做相关解释。

这里搜索器关心的是如何按给定先验分配计算资源，$p$ 可以是程序，$t$ 是程序运行用时。

哥德尔机只需要使用一个 bias-optimal searcher 做为初始证明搜索器，则是 $O()$-最优 的，因为 bias-optimal searcher 是 $O()$-最优 的。

# 8.哥德尔机的缺陷和相关讨论

## 预测而不是证明

考虑到有限的交互导致对环境认知的不确定性，从有限的与环境交互的历史中，不应该能证明无限长时间内可靠的环境性质。

如果尝试构造一个比原有公理系统强的形式系统并用其进行证明，就无法证明新的形式系统的一致性，只能用有限的经验来支持这个新的形式系统是有用的（例如在发现矛盾前暂时正常使用）。

如果尝试增加对环境的假设，那么加入这个假设可以得到新的形式系统，但这个假设不能用初始的公理系统证明，同上。

从这个角度看，利用证明对环境进行推断，和一般的元学习是类似的。这里的证明其实不如说是一种基于已有数据对未来的预测。

另一方面，形式系统可以证明一些关于无穷的命题，这些命题不能从有限的数据中得到，但可能产生可验证且有用的推论。

如果这样的构造是有用的，初始学习算法应该能构造出这样的形式系统并用其进行证明，但不会认为形式系统是绝对可靠的。

从这个角度看，形式系统和一般的程序是类似的。

## 计算资源限制

哥德尔机考虑的是理想环境，模型存活 $T$ 时间，最优化的是在存活的时间内奖励的和。

### 有限存活时间

有限存活时间会限制模型，导致模型无法到达全局最优。

由于哥德尔机的低效性，从现实的角度看，我们认为目前可以提供的算力不够让哥德尔机优化到足够强，甚至无法搜索到任何一个可证明的改进。

对于存活时间有限的情况，实际上哥德尔机很难在有限的数据下，给出对所有可能的环境在 $T$ 时刻内的收益期望，除非对环境有过强的假设。因为哥德尔机设计的最大预期回报需要对所有可能的环境，求出该环境出现的概率，并且加权计算出期望奖励。可能的环境有限显然是一个过强的假设，因为这会导致模型不图灵完备，退化成一个 DFA。而当可能的环境无限的情况下，无法在有限时间内计算这个期望。

就算写出了满足文中描述特性的哥德尔机的代码，在对环境没有过强的假设下，因为预期回报不可计算，该哥德尔机在有限的计算资源下只会卡在第一步操作上，之后消耗光计算资源。或是有一些修改可以不需要计算预期回报，比如将 `a=a+1` 改写为 `++a`，但在对环境没有过强假设的情况下，哥德尔机很难证明一个稍微复杂的修改是更优的。

### 无限存活时间

无限存活时间会导致奖励函数失效，因为无限长的时间会导致奖励函数 $u(s,Env)=E_{\mu} \bigg [\sum _{\tau=time} ^\infty r(\tau)\bigg | s,Env \bigg ]$ 无界。两个期望无穷的预期奖励是不可比较的，这也是为什么已有强化学习方法都会设立奖励衰减因子，因为这样的方法可以让 每个状态的预期奖励 有界。无限存活时间还可能导致每个时刻的奖励 $r(\tau)$ 也是无界的。

对于存活时间无限的情况，模型实际上不能只优化奖励，还需要优化自己的存活和计算资源，因为如果需要人类提供无限的计算资源，则模型不能脱离人类，无法 "消除人类的必要性"。

## 启动低效

如果引入大量概率方面的先验进入公理系统，并且可以让预期回报可计算，哥德尔机还是会面临启动过于低效的问题。

简单设计的通用方法，例如哥德尔机和其它一些 $O()$-最优 的证明搜索方法，通常需要非常长的时间后才能变得足够优。

例如，解决特定任务的最优方法需要 $t$ 时间，但通用方法需要 $a+t\times b$ 的时间，其中 $a$ 是极大的常数，我们将其定义为：**启动常数**，用于在启动阶段找出这个最优方法，$b$ 是模拟执行这个最优方法的常数代价（这个一般不严重，合理假设下可以做到 $b=1$）。

为了得到实用的通用方法，主要的设计复杂性在于降低启动常数 $a$。
因此，需要首先构造一个简单的通用方法，允许较大的启动常数 $a$；然后，通过具体设计来降低 $a$。

### 进化

进化是一种自然地生成任意复杂的结构的过程。进化生成的生物也可以通过影响环境从而在环境中生成任意复杂的结构。进化的过程和已知的优化过程区别很大，已知的优化过程都有明确的目的性，如神经网络方法通过梯度下降优化模型的 loss，强化学习方法优化模型的最大预期回报等。进化没有在优化任何预设的目标，可以从两个不同的角度看待进化：

1. 进化是一个在确定规则下沿时间轴演化的动力系统。进化没有任何目的性，但是可以生成任意复杂的结构。在这个角度下，我们可以认为没有智能体，只有一个不断演化的环境，但是环境的演化足够复杂，使得其中可以生成任意复杂的结构，如生命游戏。从一些例子中可以看到进化的复杂性，如：如何才能在宇宙中生成一块会飞的金块？进化先在环境中生成了人类，然后人类制作了旅行者号探测器，里面携带了一块人类制作的纯金的碟片，而这其中人类以及金的生成如果展开来讲也是一个极其复杂的过程。遗传算法之所以不是进化，也是因为遗传算法无法在环境中构建任意复杂的结构，并且遗传算法无法模拟生物之间复杂的交互作用。

2. 进化是智能体不断和环境交互的过程：其中进行计算或和环境交互会减少自己的计算资源，可以从环境中获取计算资源。当智能体计算资源为 $0$ 时死亡，需要优化自己存活时间。智能体和环境的边界不可区分。智能体可以将除了自己以外的其它智能体也视为环境的一部分，对其它智能体的建模，如博弈论之类的方法，是将这些智能体看做是环境中比较容易预测的一部分，并研究这一部分环境相关的特性。从这里可以看出智能体和环境是不可区分的，智能体在环境中的边界是模糊的，例如：人吃环境中的饭，吃下去的饭是否属于人的一部分；人是否是环境中人的种群的一部分；人造出了机器人，机器人是人通过对环境进行操作后得到的，是否属于人的一部分。

人类是经过了极长时间进化后产生的复杂结构，如果将进化看做是生成通用人工智能的方法，则进化像生成一块会飞的金块一样生成通用人工智能：通过先生成人类后生成这些复杂结构。生成人类的过程就是上述的极大的启动常数 $a$，通过对模型引入合适的人为设计的先验，同时不破坏完备性，这样应该可以得到一个只需要较小启动的常数，便可以在绝大部分任务上达到较优的通用人工智能。

### 神经网络不完备

神经网络是对模型引入人为设计的先验，但是破坏了完备性的一个例子。完备性被破坏导致神经网络不能通用地解决所有问题，但是可以以很低的启动常数解决一些特定的问题。

神经网络不完备指的是：

1. 搜索的计算图受限。神经网络搜索的是一类比较静态的计算图，虽然有一些动态的尝试，如 MoE 类的方法，Transformer 稀疏化，外置内存类的方法（类似神经图灵机），但是能搜索到的程序空间依然受限。神经网络虽然是图灵完备的，但是静态计算图会导致计算低效，如使用 Transformer 模型计算乘法需要做很长的自回归，输出乘法的中间结果，而实际上的乘法只需要很小的计算量即可完成。神经网络由于其结构固定，无法通过搜索来对结构进行改进。关于神经网络架构搜索（元学习）相关的内容会在后文讨论。

2. 无法遍历状态空间。常见的梯度下降方法都需要让学习率逐步下降，否则训练无法收敛，这样会导致每次随机初始化后模型只能探索到状态空间中很小的一部分。更好的一种神经网络类方法是随机初始化大量神经网络，将其均训练到收敛，之后用于测试时，对这些神经网络的结果取平均或最大似然。这样可以降低模型的方差，因为可以更广泛地探索状态空间。

3. 元学习能力受限。朴素的神经网络方法基于梯度下降，每一步的学习率确定，没有元学习能力。而有元学习特性的神经网络也只是对梯度下降的参数进行学习，甚至无法比较大地修改自己的学习算法。神经网络方法对已知形式的问题效果不错，因为加入了大量专门解决这类问题的人为设计的 trick。但是元学习对应的问题是未知的，神经网络学习能力受限会导致其无法对这些未知结构的问题进行好的学习，而无法对元学习进行好的学习会导致神经网络能力学习更受限。

现在研究神经网络的算法工程师们希望通过神经网络实现通用人工智能，并且一直在设计更为通用的模型，但是我们认为这样的方式是不合理的。

试想一个 Transformer 模型，为了优化平方代价的 attention，假设实现了一种优秀的 attention 策略，该策略允许我们每次只访问 $O(1)$ 个位置的 attention，就可以获取原本需要 $\Theta(n)$ 个位置的 attention 才能获得的信息。假设这样的 Transformer 模型学到了正确的硬的内存访问，并且训练和测试不分离，也就是说模型的训练方式也是强的，不局限于梯度下降，不会发生灾难性遗忘，并且可以常数代价模拟任何动态计算图，则这样的模型是通用人工智能。

这个模型中神经网络的部分则会退化为一个 for，因为 Transformer 是一个一直增长的函数式内存，每次只需要做常数规模的计算，并且从内存中取出 $O(1)$ 个位置的信息，并写下 $O(1)$ 的信息，真正的复杂性转移到了该如何设计优秀的 attention 策略，以及如何训练上。

我们认为自动数学证明和自动代码生成是足够复杂的任务，在这两个任务上远远超越人类表现的模型应该可以像哥德尔机一样，探索可能有效的改进，并且通过证明以及自编程来修改自己。

最近神经网络类方法取得了很好的进展，如 AI 绘画，AlphaCode，ChatGPT，DreamerV3 等，以我们的知识，我们认为他们无法通过神经网络实现通用人工智能，因为所有这一切模型的学习算法都是本质性地弱的，并且难以改进。

希望本文中给出的推理有误，他们可以实现通用人工智能，实现无数人梦寐以求的技术。

## 什么是好的？

如果对通用人工智能，可以给出定义和证明特定实现的正确性，则可以用证明搜索器来搜索和使用通用人工智能的实现，这个证明搜索器就是一个通用人工智能的实现，搜索器搜索到通用人工智能所需的时间是一个极大的常数，这个常数是证明搜索器做为通用人工智能的启动常数的一部分。

但在搜索出来之前，并不知道存在某种具体实现是能证明正确性的，这里需要注意，可能能证明存在性，但不能对任意一个实例证明它是存在性的实例。

给出的形式定义也依赖人的经验，不保证正确性；如果形式定义有误，需要人发现和修改，无法 "消除人类的必要性"。

基于永久存活的定义中，由于我们对环境特性不够了解，以及判断永久存活需要无限长时间的观测，通用人工智能的存在性和正确性很可能是不可证的，而基于理想环境中优化长期奖励的定义看起来更容易证明。

对于哥德尔机而言，通用人工智能的复杂性转移到了判断什么样的修改在未来对自己有利，也就是 "什么样的修改是好的？"，其余部分的设计都是比较平凡的。我们认为哥德尔机的问题也在于没解决这个问题，靠一个初始公理系统去直接证明修改后的模型比修改前的模型能获得更大的预期回报，这样的设计过于低效，甚至不一定正确，因为文章没有给出一个可以计算在所有环境中期望预期回报的公理系统的具体实现。

如果我们知道了如何判断什么是好的，则由全局最优性定理，只需要一个保证完备性的搜索所有可能的程序的证明搜索器（探索机制），再判断修改是不是好的，如果是好的则应用该修改（学习机制），就可以实现通用人工智能。

# 9. Q.A.

1. Q：形式化证明是否在现实世界中有意义？

	A：有意义，你需要将不确定性以及概率方面的公理，以及现实世界的性质引入哥德尔机。

2. Q：哥德尔机会不会使用一个自毁的自修改？哥德尔机会不会直接通过修改自己的奖励函数获得巨大的奖励？

	A：哥德尔机只会证明一个自修改会增加当前的奖励函数下的最大预期奖励时才会使用。如果哥德尔机的自修改可能导致自毁，则这里使用了概率相关的公理，模型有概率自毁，有概率获得更大的预期奖励。如果哥德尔机修改了自己的奖励函数，则使用新的奖励函数一定可以增加模型原有的奖励函数下的最大预期奖励。

3. Q：自动证明非常难，哥德尔机该如何工作？

	A：现在人类工作大量使用自动证明搜索器，因为证明和程序是等价的，所以神经网络也可以看做是一种证明搜索器。这些已有的证明搜索器基本上都不是 $O()$-最优的，他们是设计来处理具体任务的，在具体任务上有较小的启动常数，但是在设计范围外的任务上可能需要无限大的启动常数。

4. Q："没有免费的午餐定理" 是否说明不存在通用的问题求解器？

	A：不是，"没有免费的午餐定理" 构造了一种特殊的问题，这种问题中数据有歧义，通常处理的问题都不会有这样差的性质。这种问题上人类也无法取得好的表现。

# 10.结论

模型的自进步性一直被认为是重要的，如图灵 [2] 发现与其花费极大量的计算资源去设计成千上万个功能性模块，不如直接设计一个人类婴儿，让其在环境中学习，这样的性质就是自进步性 [3]，也就是学习。学习的重要性是显而易见的，随着环境变化，模型如果无法学习，则一定会被环境淘汰。如果通过一直修改人工智能的功能模块来实现通用人工智能，则需要人类永远存活。

之后科学家发现，学习算法的好坏是显著影响模型效果的，神经网络从最初算力要求过大，被支持向量机等模型打败，经过算力以及模型结构，训练 trick 等进步，变成目前最广泛使用的模型。但我们认为神经网络模型的学习算法是本质弱的，通用人工智能需要一个足够强的学习算法。对这个学习算法而言，与其花费极大量计算资源去直接设计这个学习算法，不如直接设计一个通用的元学习。

但是现在人工智能方面的研究反而不追求通用性，很多模型是针对具体任务设计的，无法在其他任务上工作，剩下一些模型虽然可以将任何输入输出内容转化为序列，通过序列预测来通用地解决任务，但这些模型没有足够的元学习能力，无法学习到一个足够复杂的学习算法，因此无法解决非平凡的任务，如程序生成，自动证明等。现在针对通用模型的研究主要都在通过加 trick 的方式提高模型表现，比如使用更高质量的数据，使用人的评价来强化学习（RLHF）等。我们认为这些 trick 对类似哥德尔机的通用人工智能也是有帮助的，可以降低模型的启动常数，但是使用这些 trick 去增强一个不完备的模型（如神经网络）是不合理的，应该先设计出完备的模型，后使用这些 trick 去训练完备的模型。

哥德尔机是一个有不分层元学习设计的模型，是 $O()$-最优 的学习算法，但我们认为哥德尔机的设计并没有完全解决通用人工智能的复杂性，因为其启动常数过高，同时公理系统 $\mathcal A$ 的设计非平凡但作者未给出。尽管如此，我们依然认为哥德尔机是一个非常有意义的模型，是人工智能的重要里程碑。

不分层的元学习模型虽然不会遇到分层中的那些问题，但是会将复杂性全部转移到学习中。学习不只是需要对我们已有的任务和数据进行学习，还需要对模型学习过程中生成的任意复杂的结构进行学习。解决了学习的问题等价于写出了通用人工智能的代码，而学习的问题在于什么是好的，如果模型可以判断什么是好的，则可以选择对自己有利的修改，逐步变强。

到底什么是好的呢？小编也很想知道。目前我们只有几个比较模糊的设计，并且补全细节后也不能完全解决这个问题。

# 11.摇人

大家如果对相关内容感兴趣，可以加群：756872300 来讨论。

# 12.引用

[1] Jürgen Schmidhuber (2006). Goedel Machines: Self-Referential
Universal Problem Solvers Making
Provably Optimal Self-Improvements https://arxiv.org/pdf/cs/0309048v5.pdf

[2] Turing, A. M. (1950). Computing machinery and intelligence. Mind, 59, 433–460. https://doi.org/10.1093/mind/LIX.236.433

[3] McCarthy, J., Minsky, M. L., Rochester, N. & Shannon, C. E. (1955). A PROPOSAL FOR THE DARTMOUTH SUMMER RESEARCH PROJECT ON ARTIFICIAL INTELLIGENCE http://www-formal.stanford.edu/jmc/history/dartmouth/dartmouth.html .

description:
由于你不会设计哥德尔机，所以你决定先做一道数据结构题：

给定一个长度为 $n$ 的序列 $a_1\cdots a_n$。你需要回答 $m$ 个询问，第 $i$ 个询问给定一个区间 $[l_i,r_i]$，请你求出这个区间中所有非空子集的最大公约数的乘积。由于答案可能很大，每次询问请你求出其对 $998244353$ 取模的结果。

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

接下来一行 $n$ 个正整数描述序列 $a_1\cdots a_n$。

接下来 $m$ 行，第个 $i$ 行是 $l_i,r_i$，描述第 $i$ 个询问。

outputFormat: 输出 $m$ 行，对于每个询问输出询问答案对 $998244353$ 取模的结果。

hint:
Idea：ouuan&lk，Solution：ccz181078，Code：ouuan&lk，Data：ouuan&lk

对于 $10\%$ 的数据，满足 $n,m\le10$。

对于另外 $10\%$ 的数据，满足 $n,m\le1000$。

对于另外 $20\%$ 的数据，满足 $1\le a_i\le1000$。

对于另外 $10\%$ 的数据，满足对所有 $1\le i<n$，$l_i\le l_{i+1}\le 10^5$ 且 $r_i\le r_{i+1}\le 10^5$

对于另外 $20\%$ 的数据，满足 $1\le a_i\le30000$。

对于 $100\%$ 的数据，满足 $1\le n,m,a_i\le 10^5$，$1\le l_i\le r_i\le n$。


title: [PA2018] PIN

description:
**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda próbna [PIN](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/pin/)**

Bytie 忘记了手机密码。他记得它由三个不同的正整数 $a < b < c$ 组成。这些数字的总和是 $n$，此外每对数字（在 $(a, b)$，$(a,c)$ 和 $(b, c)$ 中）中，一个数字是另一个的倍数。

帮助他计算需要检查的可能的三元组数目，以便他可以决定是否值得浪费在尝试密码上。

inputFormat: 一行输入一个正整数 $n$。

outputFormat: 输出一个整数，表示合法的三元组数目。


title: [PA2018] Poddrzewo

description:
**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 1 [Poddrzewo](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/pod/)**

给定一个长度为 $n$ 的序列 $a$。

构造一个结点数为 $k$ 的无根树，结点编号分别为 $1 \cdots k$。该树第 $i$ 个结点的度数为 $a_i$。

有可能无解，你可以进行如下操作来使其有解：

1. 修改序列中第 $i$ 个数。
1. 删除序列中第 $i$ 个数。
1. 交换序列中第 $i,j$ 个数。

可以证明，进行有限次操作后一定有解。

你的任务是 **最小化操作 $1$ 使用的次数**。

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

下一行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

outputFormat:
第一行一个整数 $x$ ，表示操作 $1$ 使用次数最小值。

第二行一个整数 $k\ (2 \le k \le n)$，表示你构造的树结点数目。

接下来 $k-1$ 行，每行两个数 $u,v\ (1 \le u, v \le k)$，表示连接第 $u,v$ 个结点。

多解输出任意解。

hint:
#### 样例 1 解释

我们可以删除第 $3$ 个数字，然后更改元素的顺序。

得到最后的序列为 $(3,2,1,1,1)$。

这是构造的树的示意图：

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

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

#### 样例 2 解释

我们可以修改第 $3$ 个数字，得到最后的序列为 $(1,2,1)$。可以证明，操作 $1$ 至少需要使用 $1$ 次。

这是构造的树的示意图：

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

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

#### 数据范围

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

对于 $100\%$ 的数据：

- $2 \le n \le 10^6$
- $1 \le a_i \le n-1$

保证存在至少一个子任务，其中操作 $1$ 使用次数最小值为 $0$。


title: [PA2018] Język polski

description:
**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 1 [Język polski](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/pol/)** 。

给定一个字符串 $s$ ，求出该字符串中满足以下条件的子串的数量。

- 该字符串中至少有一个长度为 $3$ 的子串仅由辅音字母或仅由元音字母构成。

注意，**波兰语的元音字母与英语不同**。波兰语中元音字母有 $a,e,i,o,u,y$。

不是元音字母的字母即为辅音字母。

inputFormat: 一行仅包含小写字母的字符串 $s$。

outputFormat: 一行一个整数，表示满足条件的子串数。

hint:
#### 样例 1 解释

所有满足条件的子串列举如下：$\texttt{stk},\texttt{ostk},\texttt{kostk},\texttt{stka},\texttt{ostka},\texttt{kostka}$。

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

#### 数据范围

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

设字符串长度为 $\mathrm{len}$ ，则 $\mathrm{len} \le 200000$。


title: [PA2018] Heros

description:
**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 2 [Heros](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/her/)**

给定一个有向无环图，该图有 $n$ 个节点， $m$ 条有向边。

你需要从中删除 $k$ 个点以及与其关联的边，使得图中的最长链最短。

inputFormat:
第一行三个整数，分别表示 $n$ , $m$ , $k$。

接下来 $m$ 行，每行两个整数 $x$ , $y$ ，表示从 $x$ 点到 $y$ 点有一条有向边。

outputFormat: 一行一个整数，表示图中最长链的长度最小值。

hint:
#### 样例 1 解释

删除编号为 $4$ 的点后，图中的最长链长度为 $2$ 。即为我们可以得到的最长链长度的最小值。可以验证所有方案中图中最长链长度最小为 $2$ 。

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

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

#### 数据范围

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

对于 $100\%$ 的数据：

- $1 \le n \le 300$
- $0 \le m \le 400$
- $0 \le k \le \min(n,4)$
- $1 \le x < y \le n$


title: [PA2018] Nowy kontrakt

description:
**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 2 [Nowy kontrakt](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/kon/)** 。

给定一个长度为 $N$ 的正整数序列 $a$ ，你需要对序列内数末尾添加数字的方法使序列**严格单调递增**，你的目标是最小化添加数字的次数。

在数 $a$ 后添加数字 $t$ 即为：

$a \gets a \times 10 + t$ ,其中 $t \in \{0,1,2,3,4,5,6,7,8,9\}$

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

第 $2$ 行至 $N+1$ 行每行一个数，第 $i$ 行表示序列中第 $i-1$ 个数。

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

hint:
#### 样例 1 解释

对第 $2$ 个数字和第 $3$ 个数字分别添加一个数字，即 $a_2 \gets a_2 \times 10 + 7$ ， $a_3 \gets a_3 \times 10 + 3$ 。 得到的新序列为 $(8,57,133)$ ，是一个严格单调递增序列。操作次数为 $2$ ，还有其他的操作次数为 $2$ 的方法，但是不存在操作次数为 $1$ 的方法。

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

#### 数据范围

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

对于 $100\%$ 的数据：

- $1 \le N \le 200000$
- $1 \le a_i \le 10^9$


title: 「RiOI-2」change

background:
小 E 终于在今天收回了被妈妈保管的压岁钱。

作为有远见的收藏家，小 E 知道，如果她从现在开始收集东西，以后就会变得值钱了。

小 E 的世界里有一些纸币。她知道这些纸币未来的价值，但遗憾的是，这些纸币只能从小换到大。如何是好？

description:
给定 $n$ 种物品，每种物品 $i$ 价值为 $v_i$，个数为 $c_i$。

定义总价值为 $\sum\limits_{i=1}^nc_iv_i$，你可以进行一些（可能为 $0$）次操作来最大化总价值。

一次操作为：选定一个 $i$ 满足 $c_i \geq x_i$，让 $c_i\gets c_i - x_i$，$c_{i+1}\gets c_{i+1}+ 1$。

输出最大的总价值对 $998,\!244,\!353$ 取模。

**注意，你需要最大化总价值，再对 $998,\!244,\!353$ 取模，而不是最大化「总价值对 $998,\!244,\!353$ 取模的值」。**

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

第一行一个正整数 $sid$，表示该测试数据所属子任务编号。

第二行一个正整数 $t$，表示数据组数。对于每组数据：

+ 输入共四行。
+ 第一行，一个正整数 $n$，表示钱的种数。
+ 第二行，$n$ 个非负整数分别表示 $v_1, v_2 \dots v_n$。
+ 第三行，$n$ 个非负整数分别表示 $c_1, c_2 \dots c_n$。
+ 第四行，$n - 1$ 个正整数分别表示 $x_1, x_2 \dots x_{n - 1}$。

outputFormat: 输出 $t$ 行，每行一个整数，表示物品总价值的最大值。所有答案对 $998244353$ 取模。


title: 『STA - R2』交朋友

background: > 找呀找呀找朋友 找到一个好朋友 敬个礼呀握握手 你是我的好朋友

description:
幼儿园开学啦！

在开学前，有的小朋友会准备一个毛绒玩具，可以分享给其他小朋友~

具体的，一共有 $t$ 天，每天的座位表可以表示成一张无向图。每天**有毛绒玩具**的小朋友一定会选择一个在这一天和他坐在一起的小朋友，并把毛绒玩具送给他。

但是老师规定，每个人只能有一个毛绒玩具。

在这里，我们认为每天每个人会先送出玩具，再从别人那里接受。

问初始时最多可以有多少小朋友有毛绒玩具。

注意：这意味着一个合法的传递过程中不能出现存在小朋友送不出毛绒玩具或者存在小朋友拥有超过一个毛绒玩具的情况，一个初始局面是合法的当且仅当存在一种合法的传递过程。

inputFormat:
第一行两个正整数 $t,n$，表示天数和小朋友的数量。

后描述 $t$ 张图，表示每天的座位表：

每个描述的第一行是一个正整数 $m$ 表示边数。

后 $m$ 行每行两个正整数 $u,v$ 表示图中存在一条无向边 $(u,v)$。

outputFormat: 输出一行答案。

hint:
**样例解释**

样例 1 解释：满足条件的唯一方案为初始毛绒玩具位于 $1$ 和 $2$。

样例 2 解释：满足条件的一组方案为初始毛绒玩具位于 $1$ 和 $3$。

***
**数据范围**

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

$$
\newcommand{\arraystretch}{1.5}
\begin{array}{c|c|c|c}\hline\hline
\textbf{Subtask} & \bm t\le & \bm{n,m}\le & \textbf{分值} \\\hline
\textsf{1} & 1 & 3\times 10^4 & 5 \\\hline
\textsf{2} & 10 & 2 & 5 \\\hline
\textsf{3} & 10 & 100 & 20 \\\hline
\textsf{4} & 10 & 3\times10^3& 70 \\\hline\hline
\end{array}
$$
对于 $100\%$ 的数据，$1\le t\le10$，$1\le n,m\le  3\times10^4$，但是注意 $t,n,m$ 的范围不会同时达到上界。

保证给出的每张图没有重边、自环。


title: 「RiOI-2」equals

background:
在小树上坐落着一个幻想的城堡。这里是 E 国的领地，而小 E，则是 E 国之王。

为了打造一个完美的 E 国，他需要明辨是非，走向正义。

但是，他似乎有些太理想了。有时并没有一个完美的准则。是黑是白，谁能分辨？

description:
给定一棵 $n$ 个结点，以 $1$ 为根的树，定义一个结点的深度 $d_i$ 表示它到根结点的简单路径上的结点个数。

你需要给每个结点黑白染色，满足黑色结点的深度和等于白色结点的深度和。设 $c_i = \{0, 1\}$ 分别代表编号为 $i$ 的结点为黑色或白色，那么这即 $\displaystyle\sum_{c_i=0}d_i=\sum_{c_i=1}d_i$。

若无解，仅输出一行一个整数 $-1$。

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

接下来 $n - 1$ 行，每行两个整数 $u_i, v_i$，表示树上编号为 $u_i$ 的结点与编号为 $v_i$ 的结点之间有一条边。保证给出的边不重复。

outputFormat:
若有解，则输出一行 $n$ 个数 $c_1\dots c_n$。

若无解，仅输出一行一个整数 $-1$。

**本题开启 Special Judge，只要你的方案满足条件或正确判断无解即可拿到本测试点的分数。**


title: [Ynoi Easy Round 2022] 堕天作战 TEST_98

background:
明明超越人智，君临了至高点，却总是给些奇怪的奇迹。当然也会有不满的人出现，想要取回灵长的宝座。

有许多的国家，组织，个人，用各种方法挑战超人机械。要让天上宛如神的他，堕落于地的众多手段——被称作是堕天作战。

为了从超人机械手中抢夺神性而被用上的手段里，有一个天马行空的心理战。希望他能抛下机械的身份理解人类活着的美好——这样。

那就像是狗在对着人类说当条狗吧，像那种狗我会嗤之以鼻的。但是没想到，他接受了那个邀约。不管是好奇心，打发时间，或是同情，总之他将降级为人类的分身送到这世上了。

那时正逢地壳变动或是寒冷化之类的地球规模的异变，而魔人在此时趁机崛起，撒下了腐铁菌，让科学文明画下句点。而超人机械则是一副事不关己的样子。

分身似乎不断地送了好几位来，但都死了，在那种世界里。不管试多少次都在途中倒下，还没体会到人类的美好就死了。

于是出现了分身第二弹——不会死！本末倒置对吧，那已经不是人类了。

......

我想应该不是那样。

超人机械是足以发明出魔法的存在吧？虽然我觉得不死者这种存在听起来很假。

但这么厉害的机械，若真的想理解人类，只要随便抓个几十，几百人，当作零件装到自家身上，马上就能解决了吧？

......

该怎么说呢，我觉得...为了理解人类这个见解，有点牵强了呢？

从包括人类在内更上一层楼的知性，是如何诞生的角度来思考的话。

而且我认为，超人机械，是透过机械化——达成超越的人类。

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

......

宇宙是很严峻的，真空，极寒，辐射，我的魔力能否起作用，完全是未知数。

就算是要打造火箭，也不知道要耗费多少资源才能连飞行员的生存设备也一并完善...

但只要有不死者就能解决，不会错的。

description:
给定一个长为 $n$ 的序列 $a$，有两种操作，共 $m$ 次：

1. 给定 $l$ $r$ $x$，对于所有 $i$ 满足 $l\le i\le r$ 且 $a_i \neq x$，$a_i\leftarrow a_i-x$。
2. 给定 $l$ $r$，求对于所有 $i$ 满足 $l\le i\le r$ 且 $a_i\neq 0$，$a_i$ 的和。

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

第二行 $n$ 个用空格隔开的数表示序列 $a$。

之后 $m$ 行，每行三个或四个数：

若输入为 `1 l r x`，则表示对区间 $[l,r]$ 进行一次 $1$ 操作，若输入为 `2 l r`，则表示对区间 $[l,r]$ 进行一次 $2$ 操作。

本题强制在线，所有输入的 $l,r,x$ 均需要异或 $lastans$，其定义为上一次询问操作得到的答案对 $2^{20}$ 取模后的值，若之前没有询问操作，则为 $0$。

outputFormat: 对每个 $2$ 操作，输出一行一个数表示答案对 $2^{64}$ 取模后的结果。

hint:
Idea：nzhtl1477，Solution：nzhtl1477，Code：w33z8kqrqk8zzzx33，Data：w33z8kqrqk8zzzx33

对于 $5\%$ 的数据，$n,m\le 1000$。

对于 $30\%$ 的数据，$n,m\le 5\times10^4$。

对于另外 $20\%$ 的数据，$l=1,r=n$。

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

对于 $100\%$ 的数据 $1\le n,m \le 5\times10^5, 0\le a_i, x \le10^9$。


title: [Ynoi Easy Round 2022] 虚空处刑 TEST_105

background:
我要对不死者先生你施展魔法，希望你能看到，更多美好的事物，希望你能见识到，更多我无法见识的事物，希望...你的心...不管几次都能苏——

......

你的魔法为时已晚了，和知道没有办法可以救你是一样的，仿佛就像是这什么都没有的天空一样啊——

星星？

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

......

星星呢？有个星形的星星飘在天上？

像那种奇妙的东西啊，是超人机械的产物哦。

......

已不能，继续光顾着追求星星...

不死者的本体的确不见得是在那颗星星上，我也知道他们大多是脱离常轨的危险任务，这些我都明白...

但天上就是飘着那种星星啊，超人机械或许就在上面，史前的睿智肯定堆积如山。

......

星形的理由是个迷，也看不出任何工学上的必然性。但他若是以自然物为基础打造的，那这形状就说得通了。

正确来说，我认为那是个群体，而不是单一生命体，且若它是生物，那就可预想它有着机械所没有的优点，像是自然修复损毁部位，透过增殖解决经年老化问题，甚至可能是以不需管理者为前提所打造的。

目前我们还不理解它是用什么系统来维持飞行轨道，但高度应该是最佳环境不会错。

连次元的墙壁都能跨越的超绝知性体，怎么可能将与自身相关的重要机构，放在区区三万六千公里高的天空上？

你不觉得魔法是个很极端的东西吗？光用想的就能产生出热或质量，这实在太荒唐了，超越人智，犹如神般的存在姑且先不谈，一个小小的生命，人类的亚种，魔法使们怎么可能会有如此强大的力量？

魔法使换句话说就是水龙头，水源则是另在别处。

星星是超人机械所撒下的，供应魔力与抑制魔法的生命机器，除此以外可能什么都不是吧。

......

我们已经不做星星的梦了。

魔法产生的原理，一旦被世人知道，就会引发末日战争。现在我们只能尽全力透过操控情报，让世人不对此事感兴趣。

description:
给定一棵 $n$ 个节点的树，第 $i$ 个点有点权 $a_i$。

定义一个点 $x$ 所在的极大同色连通块为一个**极大的**点集 $S$，满足 $x\in S$，且对任意点集中的元素 $i,j$，可以找到一个节点序列 $p_1,p_2,...p_t$，满足 $p_1=i$，$p_t=j$，且对任意 $k$ 为 $[1,t)$ 中的整数，满足 $p_k$ 与 $p_{k+1}$ 在树上相邻，且 $a_{p_k}=a_{p_{k+1}}$，且 $p_k\in S$。

有 $m$ 次操作：

`1 x y`：给出一个点 $x$ ，将其所在的极大同色连通块中每个点的点权修改为 $y$。

`2 x`：给出一个点 $x$，查询其所在的极大同色连通块的大小。

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

第二行 $n-1$ 个数，第 $i$ 个数表示树上第 $i+1$ 的节点的父亲节点的编号，保证父亲节点的编号比该节点小。

第三行 $n$ 个数，第 $i$ 个数表示 $a_i$。

之后 $m$ 行，每行形如 `1 x y` 或 `2 x`，意义如上述。

outputFormat: 对每个 $2$ 操作，输出一行一个数表示答案。

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

对于 $20\%$ 的数据，满足 $n,m\leq2\times 10^3$。

对于 $40\%$ 的数据，满足 $n,m\leq2\times 10^5$。

对于另外 $30\%$ 的数据，满足 $1\le a_i,y\le 2$。

对于 $100\%$ 的数据，满足 $1\le n,m,a_i,x,y\le10^6$。


title: [PA2018] Magiczne wieże

description:
**译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/)  Runda 3 [Magiczne wieże](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/mag/)**

在一个王国中有 $n$ 个魔法师。每个魔法师有两座魔法塔。并且魔法师可以在自己的两座塔之间随意传送。

出于某种原因，该国的居民只想居住在被魔法师环绕的区域。具体来说，如果一位居民从住所向任何方向移动，他都将接近其中一个魔法师（无论在哪个塔），他的住所就是安全的。

依次连接所有的安全住所，它们围成了一个安全区域，请你求出这个区域的面积。

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

接下来的 $n$ 行，每行 $4$ 个整数 $ax_i,ay_i,bx_i,by_i$，表示第 $i$ 个魔法师所拥有的两座魔法塔 $a,b$。

数据保证没有两座塔在同一位置上。

outputFormat:
输出安全区域的面积。特殊地，如果没有安全点，那么区域的面积为 $0$。

你的输出与标准答案的相对误差不能超过 $10^{-8}$。

hint:
#### 样例 1 解释

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

如图，黑色线段为一位魔法师的两座塔，灰色区域为安全区域。

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

#### 数据范围

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

对于 $100\%$ 的数据，$3\leq n\leq 100$，$-500\leq ax_i,ay_i,bx_i,by_i\leq 500$。

共 $10$ 个子任务，其中以下各个条件均至少有一个子任务满足：（每行为一个条件）

- $n\leq 10$，$-30\leq ax_i,ay_i,bx_i,by_i\leq 30$。

- $n\leq 10$。

- $-30\leq ax_i,ay_i,bx_i,by_i\leq 30$。


title: [PA2018] Gra

description:
**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 5 [Gra](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/gra/)**

现在已经是周末了！你终于可以放松一下，玩你最喜欢的策略游戏了。这个游戏的目标是收集地图上的所有金币并将它们运回基地，规则如下：

- 地图由一个 $n\times n$ 的网格构成。行从上到下编号为 $0$ 到 $n-1$，列从左到右编号为 $0$ 到 $n-1$。我们用 $(r,c)$ 表示第 $r$ 行第 $c$ 列的单元格。两单元格相邻当且仅当它们共享同一条边。
- 你的基地位于单元格 $(0,0)$，它位于左上角。你可以在那里招募新的角色，并且你必须把收集到的金币带到那里。剩下的 $n^2-1$ 个格子中初始要么有一定数量的金币，要么有一定数量的石头。
- 游戏中有两种可以在地图上移动的角色：**农民**可以收集金币，但不可以进入有石头的单元格，**坦克**可以清除石头，并且可以进入任何种类的单元格。
- 游戏分轮次进行。每轮每个角色可以至多移动一次，移动到与它所在的单元格相邻的单元格中。两个角色不能在同一时间处于同一单元格中。所有移动都是瞬时的（移动花费的时间为零）。
- 如果在一轮结束时，农民位于有金币的单元格中，他就会拿走 $10$ 枚金币并放到自己的背包里。如果单元格中的金币少于 $10$ 枚，他就会全部拿走。农民的背包容量无限。但农民无法进入石头量不为 $0$ 的单元格中。如果在一轮结束时农民回到了基地，他就会把背包里所有的金币放回基地。
- 如果在一轮结束时，坦克位于有石头的单元格中，它就会清除单元格中的 $10$ 个石头（如果少于 $10$ 个则清除全部）。
- 最初基地中有 $200$ 枚金币。每买一种角色——农民或者坦克——都要花费 $100$ 金币（买之前在基地中必须至少有这么多金币），买后角色即时出现。所以新角色可以在同一轮移动。

你的任务是，对于每一个输入给定的地图（也就是对于每个测试点），找到一个操作序列，使得按这个操作序列进行游戏后，所有地图上的金币都被运回了基地（并且可能部分或全部花掉了）。换句话说，结束后的地图上，任何单元格中都没有金币，任何农民的背包里也没有金币。命令如下表所示：

|                   命令                   |                           效果                           |
| :--------------------------------------: | :------------------------------------------------------: |
|           $\texttt{R FARMER}$            |              买一个农民角色，并出生在基地中              |
|            $\texttt{R TANK}$             |              买一个坦克角色，并出生在基地中              |
| $\texttt{M}\ \ r_1\ \ c_1\ \ r_2\ \ c_2$ | 将一个角色从 $(r_1,c_1)$ 移动到相邻的格子 $(r_2,c_2)$ 中 |
|               $\texttt{=}$               |                         结束这轮                         |
|              $\texttt{===}$              |              结束游戏（即目前的这个测试点）              |

你的程序会使用组织者准备的测试数据进行测试，每组测试数据由一定数量的地图——也就是测试点组成。每组测试数据都有一个限制 $k$（请参考「数据范围及限制」一节）。这是对于每组数据平均轮数的限制。换句话说，如果测试数据中有 $T$ 张地图，你的程序必须在最多 $T\cdot k$ 轮结束所有游戏。我们定义每个测试点的轮数为使用命令 $\texttt{=}$ 的次数加 $1$。

错误的命令，超出轮数限制或没有达成目标，均会被判为 Wrong Answer。

inputFormat:
第一行包含两个整数 $T,k$，表示测试点个数和平均轮数限制。除了样例外所有测试数据都有 $T=10$。

对于每组数据，第一行一个正整数 $n$。除了样例外所有测试数据都有 $n=20$。

接下来 $n$ 行，每行 $n$ 个整数。$0$ 表示基地（一定位于左上角）。正数 $a$ 意味着这个单元格有 $a$ 枚金币，负数 $a$ 意味着这个单元格有 $|a|$ 个石头。

地图按如下方式生成：对于每组测试数据，组织者会选择一个常数 $p\ (0\le p<1)$，表示单元格中有石头的概率。对于每个除基地以外的单元格，随机选择一个在 $0$ 到 $9$ 范围内的整数 $x$，然后将 $a=2^x$ 赋给这个单元格。在此之后，以 $p$ 的概率给这个值乘以 $-1$。

outputFormat: 对于每组测试点，输出操作序列。一条命令输出一行。最多输出 $2\ 000\ 000$ 条命令。

hint:
#### 样例 1 解释

对于第一个测试点，我们首先买了一辆坦克，并立即从 $(0,0)$ 移动到 $(1,0)$，这样在两轮中清除掉了所有石头。然后我们将坦克移动到 $(1,1)$，在基地中买一个农民，并将其送到 $(2,0)$ 收集金币。当金币收集完后，我们让农民返回金币并清空背包。我们可以在第一轮就购买一个农民，但他需要一直等到坦克清除石头后才能移动。

第二个测试点展示了一种不是最优但正确的答案。注意农民可以在不收集全部金币的情况下离开这个单元格。招募前两个角色就会花掉所有初始金币（$200$），所以我们只能在农民向基地运回 $100$ 金币后买第三个角色。

第一个测试点中使用了 $7$ 轮，第二个测试点使用了 $13$ 轮。平均是 $10$ 轮，没有超过给定 $k$ 的限制。

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

#### 数据范围

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

共有十个子任务，每个子任务包含 $2$ 到 $5$ 个测试数据。确切的 $p$ 值和 $k$ 值如下表所示：

| $\text{id}$ |   1    |   2    |   3    |   4   |   5   |   6    |   7    |   8    |   9    |  10   |
| :---------: | :----: | :----: | :----: | :---: | :---: | :----: | :----: | :----: | :----: | :---: |
|     $p$     |  $0$   |  $0$   |  $0$   |  $0$  |  $0$  | $0.3$  | $0.4$  | $0.5$  | $0.6$  | $0.7$ |
|     $k$     | $9000$ | $3500$ | $1500$ | $600$ | $370$ | $1000$ | $1500$ | $3500$ | $1200$ | $750$ |

请注意样例和测试数据在地图大小和测试点个数上稍有不同。


title: [PA2018] Ryki

description:
**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 5 [Ryki](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/ryk/)**

Berlandia 是一个由方格组成的无限大棋盘。行从下到上用递增的整数编号，列从左到右用递增的整数编号。令 $(r,c)$ 表示第 $r$ 行第 $c$ 列的方格。如果两个不同方格至少有一个角接触，我们就称这两个格子相邻。这意味着格子是八连通的。

两个格子 $(R_A,C_A)$ 与 $(R_B,C_B)$ 之间的距离是欧几里得距离，也就是：
$$
\sqrt{(R_A-R_B)^2+(C_A-C_B)^2}
$$
Berlandia 地区居住着 $n$ 只熊。第 $i$ 只熊居住在方格 $(r_i,c_i)$ 处。同一方格中可以居住多只熊。

熊可以单独生活，但是有时也会相互靠近。当一只熊吼叫时，其他方格中所有的熊会立即移动到相邻的方格中离吼叫的熊最近的方格。可以证明有且仅有一个这样的方格（不会出现并列情况）。与吼叫的熊在同一方格的熊不会移动位置。

例如，考虑一对熊，一只在方格 $(2,1)$，另一只在方格 $(4,8)$。方格 $(2,1)$ 中的熊吼叫会让另一只熊移向方格 $(3,7)$ ，这两只熊最后相距 $\sqrt{(3-2)^2+(7-1)^2}=\sqrt{37}$。

这些熊会按第一只，第二只，……，最后一只的顺序依次吼叫。除了一只叫 Limak 的熊，他太冷了以至于吼不出来，并且他也不能离开他所在的方格，可怜的 Limak。

但你不知道 Limak 是哪只熊，对于 $1$ 到 $n$ 的每一个 $k$，如果第 $k$ 只熊是 Limak，请找出所有熊的最终位置。对于每种可能，输出所有熊的横纵坐标乘积之和就可以了。也就是说，假设在 $n-1$ 次吼叫后，第 $i$ 只熊在 $(r_i',c_i')$，则输出：
$$
\sum_{i=1}^n r_i'c_i'
$$

inputFormat:
输入第一行包括一个正整数 $n\ (2\le n\le 250\ 000)$，表示熊的数量。

接下来 $n$ 行，每行两个整数 $r_i,c_i\ (1\le r_i,c_i\le 10^6)$，第 $i$ 行表示第 $i$ 只熊的初始位置。

outputFormat: 输出 $n$ 行，第 $k$ 行输出一个整数，表示假设 Limak 是第 $k$ 只熊的话，最终所有熊所在行列之积的和。

hint:
#### 样例 1 解释

下图展示了 $k=2$ 的情况，即熊的吼叫顺序为 $1,3,4$。红色圆圈表示吼叫的熊。最后乘积的和为 $2 \cdot 4 + 2 \cdot 1 + 2 \cdot 4 + 2 \cdot 3 = 24$。

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

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

#### 数据范围

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

保证每组子任务中下述三种情况至少出现一种：

- $n\le 10^5$
- 对于所有 $i$ 都有 $c_i=1$
- 时间限制为 $8$ 秒

注：由于未公布每个测试点的详细时间限制，因此本题所有测试点的时间限制均为 $4$ 秒。


title: [PA2018] Skwarki

description:
**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 5 [Skwarki](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/skw/)** 。

求有多少种长度为 $ N $ 的满足以下条件的序列 ：

* $ 1 \sim N $ 这 $ N $ 个数在序列中各出现了一次；
* 至少进行 $K$ 次操作后，该序列才只含有 $1$ 个元素。

下面对操作进行描述：

设 $A_i$ 为序列中的第 $i$ 个元素（$1 < i < \mathrm{len}$ ， $\mathrm{len}$ 为序列长度），若 $A_{i-1} > A_{i}$ 或 $A_{i+1} > A_{i}$ 则标记 $A_i$ 。 若 $A_2 > A_1$ 则标记 $A_1$ ， 若 $A_{\mathrm{len}-1} > A_{\mathrm{len}}$ 则标记 $A_{\mathrm{len}}$ 。

然后，将有标记的元素从序列中删除。

满足条件的序列可能很多，所以请将结果对 $P$ 取模。

inputFormat: 输入仅一行，包含三个整数 $N,K,P$。

outputFormat: 输出一行一个整数，表示满足条件的序列个数对 $P$ 取模的结果。


title: 「SvR-2」G64

description:
定义对于两棵有根二叉树 $T_1,T_2$，$\operatorname{merge}(T_1,T_2)$ 的结果是一棵二叉树，满足其根节点的左子树为 $T_1$，右子树为 $T_2$，显然 $\operatorname{merge}(T_1,T_2)$ 的结果唯一且必然存在。

定义对于一棵有根二叉树 $T$，有函数 $G_x(T)$。其中 $G_1(T)$ 表示沿着 $T$ 的根向右儿子走，直到走到某个不存在右儿子的节点，将其右子树变为 $T$，这棵新树即为 $G_1(T)$ ，而当 $x>1$ 时，$G_x(T)$ 满足如下关系：

$$G_x(T)=G_1(\operatorname{merge}(G_{x-1}(T),G_{x-1}(T)))$$

给一棵 $n$ 个节点的以 $1$ 为根的有根二叉树，记以 $i$ 为根的子树为 $T_i$，$q$ 次询问，每次询问给定 $x,i$，求 $G_x(T_i)$ 的最大独立集。

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

之后 $n$ 行，每行两个整数 $ls_i,rs_i$ 表示其左儿子和右儿子，若为 $0$ 则说明没有对应儿子。

之后 $q$ 行，每行两个整数 $x,i$ ，表示一次询问。

outputFormat: $q$ 行，每行一个数，表示这次询问的  $G_x(T_i)$ 的最大独立集大小对 $998244353$ 取模的结果。

hint:
### 样例解释

对于第一组样例，$G_2(T_5)$ 的结果如下图（忽略编号）：
![](https://cdn.luogu.com.cn/upload/image_hosting/fcjnzc23.png)

对于第二组样例，我有一个绝妙的解释，可惜 $G_{64}$ 太大了，这里写不下。

#### 数据规模与约定

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

| Subtask | 数据范围/特殊性质 | 分值 |
| :------: | :------: | :------: |
| $1$ |  $n,q,x\le 10$| $10 \operatorname{pts}$ |
| $2$ | $x =1$ | $5 \operatorname{pts}$ |
| $3$ |$x\le 3$ | $10 \operatorname{pts}$ |
| $4$ | $x\le 10$ | $15 \operatorname{pts}$ |
| $5$ | 保证 $T_i$ 大小为 $1$ | $10 \operatorname{pts}$ |
| $6$ | 无特殊限制 | $50 \operatorname{pts}$ |

对于 $100\%$ 的数据，
$1\le x\le 10^9$，$1\le n\le 5\times 10^5$，$1\le q\le 5\times 10^5$。


title: [CTS2023] 琪露诺的符卡交换

description:
受异变的影响，琪露诺发现封印了自己能力的卡片正在幻想乡中流通。

琪露诺调查之后，发现一共有 $n$ 种不同的卡片，每种卡片的数量总共恰好是 $n$ 张，有 $n$ 个人购买了这些卡片，每个人都恰好买了 $n$ 张卡片，并且可能会买到相同种类的卡片。

但是琪露诺想要让每个人都正好持有 $n$ 种卡片，于是她把这 $n$ 个人聚集在一起，想要通过卡片交换的形式达成她的目的。

琪露诺每次会选择两个人持有的某张卡片进行交换，直到每个人都正好持有 $n$ 种卡片为止。

由于每次交换都会减少卡片上的魔力，所以琪露诺想要每张卡片最多被交换一次。

但是她对如何进行交换犯了难，于是她转而寻求你的帮助。

你需要告诉她交换的过程，或者告诉她不存在这样的方案。

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

对于每组数据，第一行一个正整数 $n$，含义如题所示。

接下来 $n$ 行，每行输入 $n$ 个正整数，其中第 $i$ 行的第 $j$ 个正整数表示第 $i$ 个人持有的第 $j$ 张卡片的种类。

outputFormat:
对于每组数据，如果不存在能够让每个人都持有 $n$ 种卡片的方案，输出一行 $-1$。

否则首先输出一行一个正整数 $m$，表示交换次数。

接下来 $m$ 行，每行输出四个正整数 $a,b,c,d$，表示第 $a$ 个人的第 $b$ 张卡片，与第 $c$ 个人的第 $d$ 张卡片进行一次交换。

注意你需要保证不存在某张卡片被交换了两次，并且交换结束后每个人都正好持有 $n$ 种卡片。

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

第一组数据，我们第一次交换第一个人的第三张卡牌，和第三个人的第一张卡牌；

第二次交换第二个人的第三张卡牌，和第三个人的第二张卡牌；

一共交换两次，可以使得所有人都持有三种卡牌。

输出其它方案也是被允许的。

第二组数据，因为一开始所有人都持有了三种卡牌，所以无需交换，输出一行 $0$ 即可。

**【数据范围】**

子任务 $1$（$20$ 分）：每个人只持有一种卡片。

子任务 $2$（$20$ 分）：每个人持有至少 $n-1$ 张同一种类的卡片。

子任务 $3$（$60$ 分）：无特殊限制。

对于所有数据，满足 $\sum\limits_{i=1}^{T}n_{i} \leq 200$。


title: [CTS2023] 鸽子（无防作弊）

background: 小 E 和小 F 是一对好闺蜜。

description:
这是一道**通信题**。

小 E 有一些很重要的信息要传给小 F。信息的内容可以用一个不超过 $128$ 位的二进制整数来表示。

但是小 E 现在只有鸽子。好多好多的鸽子。黑色和白色的鸽子。

小 E 可以让不同颜色的鸽子按一定的顺序起飞，飞到小 F 那里，这样小 F 就可以根据降落的鸽子的颜色顺序来知道信息的具体内容了。当然鸽子的数量是需要约定好且固定的，不然小 F 可能会在看到所有鸽子之前误以为所有的鸽子都已经飞过来了。

但是众所周知，“鸽子”一词总是和“时间”联系在一起。鸽子会放鸽子。不过小 E 的鸽子还算守时，起飞和降落的顺序之差不会超过一个正整数 $k$。形式化地，设起飞的第 $i$ 只鸽子是第 $p_i$ 个降落的，那么 $\{p_i\}$ 是一个排列且对于所有的 $i$，$\left|i-p_i\right|\le k$。

小 E 自然是考虑到了这些情况，并提前与小 F 约定好了。请问如果你是小 E 你要怎样做下约定以及发送信息呢？

### 实现细节

【备注】：提交此题需要在所有函数前加上 `extern "C"`。

你不需要也不应该实现主函数。你需要实现三个函数 `pigeon_num`，`send` 和 `receive`。

函数 `pigeon_num` 的接口如下：

```cpp
int pigeon_num(int Taskid, int k);
```

- 该函数传入子任务编号 `Taskid` 和题目中参数 `k` 的值。
- 该函数需要返回小 E 需要放飞的鸽子数量 $n$。

函数 `send` 的接口如下：

```cpp
std::string send(int Taskid, int n, int k, __uint128_t msg);
```

- 该函数传入子任务编号 `Taskid`，`pigeon_num` 函数的返回值 `n`，题目中的参数 `k` 以及需要发送的信息 `msg`。
- 该函数需要返回一个长度恰好为 $n$ 的字符串，其中下标为 $i(0\le i\lt n)$ 的位置表示小 E 放飞的第 $i+1$ 只鸽子的颜色，`0` 表示黑色，`1` 表示白色。

函数 `receive` 的接口如下：

```cpp
__uint128_t receive(int Taskid, int k, const std::string &msg);
```

- 该函数传入子任务编号 `Taskid`，题目中的参数 `k` 以及小 F 看到的鸽子的降落顺序 `msg`。
- `msg` 为一个长度为 $n$ 的字符串，其中下标为 $i(0\le i\lt n)$ 的位置表示小 F 看到的第 $i+1$ 只降落的鸽子的颜色，`0` 表示黑色，`1` 表示白色。`msg` 的值与某次调用 `send` 函数的返回值有着题目描述中所满足的关系。
- 该函数需要正确返回小 E 发送的信息的内容。

你可以参考下发的样例程序 `pigeon.cpp`，也可以从头开始写一个程序。

在评测时，交互库会被运行**两次**，**两次运行独立计算时间和空间**。

在第一次运行时，交互库会先调用一次 `pigeon_num` 函数，然后调用不超过 $1000$ 次 `send` 函数。

在第二次运行时，交互库会调用不超过 $10000$ 次 `receive` 函数。

保证在题目限制下，评测交互库的运行时间不超过 $1\texttt{s}$，运行内存不超过 $512\textrm{MB}$。也就是说，你实际可以利用的时间至少为 $2\texttt{s}$，空间至少为 $1.5\textrm{GB}$。

**由于洛谷暂不支持通信题的评测，评测方式逻辑与下发交互库类似。这意味着可以轻松地作弊。E_Space 在这里不追究有关于此的作弊行为，但请不要写到题解中去。**

### 测试程序方式

将样例交互库 `grader.cpp` 和你的代码 `pigeon.cpp` 置于同一目录下并在终端中输入如下命令进行编译：

```bash
g++ pigeon.cpp grader.cpp -o grader -g -Wall --std=c++11
```

然后运行 `./grader` 即可。样例交互库使用标准输入和标准输出，**只需要运行一次**。

注意下发的交互库与实际评测时使用的交互库的实现不同。比如在下发的交互库中，通过 `send` 函数修改的全局变量的值能够被 `receive` 函数查看。

inputFormat:
第一行三个非负整数 $\mathrm{Taskid}$，$k$，$T$。其中 $\mathrm{Taskid}$ 表示子任务编号，$T$ 表示发送信息的数量。

接下来 $T$ 行，每行一个非负 $128$ 位整数表示信息的内容。

outputFormat:
如果你的程序在该测试点上是正确的，对于每一条信息，交互库会输出四行内容。

- 第一行 `Message` 为小 E 想要发送的信息，即 `send` 函数中参数 `msg` 的内容。
- 第二行 `Taking off` 为鸽子起飞的顺序，即 `send` 函数的返回值。
- 第三行 `Landing` 为鸽子降落的顺序，即 `receive` 函数中参数 `msg` 的内容。
- 第四行 `Received` 为小 F 解读出来的信息，即 `receive` 函数的返回值。
- 最后一行输出 `Accepted using <num> pigeon(s).`，其中 `<num>` 是小 E 放飞的鸽子的数量，即 `pigeon_num` 函数的返回值。

否则如果程序正常退出，交互库会输出以下内容之一：

- `Invalid number of pigeons.`：输出这句话说明 `pigeon_num` 函数的返回值不在 $[1,4000]$ 之间。
- `Invalid color of pigeon.`：输出这句话说明 `send` 函数的返回值中有非 `0` 或 `1` 的字符。
- `Too few or too many pigeons taking off.`：输出这句话说明 `send` 函数的返回值的长度不等于 `pigeon_num` 函数的返回值。
- `Received wrong message.`：输出这句话说明 `receive` 函数的返回值与 `send` 函数中的参数 `msg` 不相等。

一旦交互库输出了报错语句，交互库程序就会立即停止运行。

hint:
#### 样例解释

这是样例交互库在下发样例程序 `pigeon.cpp` 在样例输入下的输出。

对于小 E 来说，$97429867398990605044182047185430790478$ 是一个很有意义的数。所以只需要放飞少量鸽子就够了。

### 子任务

子任务 $0$（$0.01$ 分）：样例。保证信息对应的整数等于 $97429867398990605044182047185430790478$。下发的 `pigeon.cpp` 能够通过样例。该子任务的评测结果会显示在评测结果中。

子任务 $1$（$3.99$ 分）：保证信息对应的整数小于 $1024$。 $k\le 20$。

子任务 $2$（$12$ 分）：$k=1$。保证信息对应的整数小于 $1048576$。

子任务 $3\sim 9$（每个子任务 $12$ 分，共 $84$ 分）：$k\le 20$。

**由于洛谷不支持小数得分，本题的得分显示将乘以 100 来表示保留两位小数之后的结果。**

### 评分方式

评测时，你只需在 OJ 上提交你的源程序，修改下发的其他文件不会对评测结果产生影响。

本题首先会受到和传统题相同的限制，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

对于每个子任务，如果你的程序有以下行为，将会被判为 $0$ 分：

- `pigeon_num` 函数的返回值不在 $[1,4000]$ 之内；
- `send` 函数的返回值的长度不等于 `pigeon_num` 函数的返回值；
- `send` 函数的返回值的内容包含 `0` 或 `1` 之外的字符；
- `receive` 函数没有正确地返回小 E 发送的信息内容。

此外，对于每个子任务，你的得分与小 E 放飞的鸽子的数量，即 `pigeon_num` 函数的返回值有关。设这个值为 $n$。

在子任务 $1 \sim 2$ 中，如果 $n\le 4000$，那么你就能得到该测试点的满分，否则得到零分。

在子任务 $3\sim 9$ 中，同一个子任务中所有测试点的 $k$ 的值相同，且编号越大的子任务中 $k$ 的值越大。设 $C(k)$ 为一个关于 $k$ 的函数，则

- 如果 $n\le C(k)$，那么你可以得到该测试点的满分。
- 若 $n\le C(k)+5$，那么在此范围内 $n$ 的值每多 $1$，你就会失去该测试点满分乘以 $2\%$ 的分数。
- 若 $C(k)+5 \lt n\le \lfloor 1.1\times C(k)\rfloor$，那么在此范围内 $n$ 的值每多 $1$，你就会额外失去该测试点满分乘以 $400\%/C(k)$ 的分数。
- 若 $n\gt \lfloor 1.1\times C(k)\rfloor$，那么在此范围内 $n$ 的值每多 $1$，你就会额外失去该测试点满分乘以 $40\%/C(k)$ 的分数。
- 若你的答案正确，你至少可以得到 $1$ 分。

换句话说，你在一个测试点的得分等于 $\max(1, 12\times \min(1, f_k(n)))$，其中 $f_k(n)$ 是一个关于 $n$ 的分段线性函数，满足：

- $f_k(C(k))=1$
- 两个拐点的横坐标分别为 $C(k)+5$ 和 $\lfloor 1.1\times C(k)\rfloor$。
- 被两个拐点分割所形成的三段区间的斜率依次为 $-0.02$，$-4/C(k)$ 和 $-0.4/C(k)$。

你的每个子任务的得分是子任务中所有测试点得分的最小值。

$C(k)$ 的函数值由下表给出。在下表中未出现的 $k$ 值不会出现在子任务 $3\sim 9$ 的测试数据中。

| $k$ | $1$ | $2$ | $5$ | $7$ | $10$ | $14$ | $20$ |
| :----------- | :----------- | :----------- | :----------- | :----------- | :----------- | :----------- | :----------- |
| $C(k)$ | $206$ | $284$ | $485$ | $605$ | $773$ | $983$ | $1277$ |

**通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为，所得分数无效。**

**由于洛谷暂不支持通信题的评测，评测方式逻辑与下发交互库类似。这意味着可以轻松地作弊。E_Space 在这里不追究有关于此的作弊行为，但请不要写到题解中去。**


title: [CTS2023] 另一个欧拉数问题

background:
你继续向前走，遇到了一个身着黑袍的老人，那边的门前放着一个巨大的沙盘，老人用手中的树枝在沙盘前画着奇怪的符号。

老人告诉你，他从年轻开始便梦想一个问题，直到他垂垂老矣，似乎也只揭露了答案的一角。

或许我该将它们交给你们了，老人说。

别太担心，我不想太为难你，至少我已经把必要的工具给你准备好了。

description:
对于正整数 $\alpha$，考虑下述长为 $\alpha n$ 的序列 $a$：

- 对于每个 $k=1,\dots, n$，序列 $a$ 中出现了恰好 $\alpha$ 个 $k$。

- 对于 $i < j$ 满足 $a_i = a_j$，那么对任意 $i < k < j$，有 $a_k \geq a_i$。

我们称满足上述要求的序列是一个 $(n,\alpha)$ 阶排列。

现在输入一个 $(n_0,\alpha)$ 阶排列 $P$。又给定 $n$ 和 $m$，请你计算有多少 $(n,\alpha)$ 阶排列包含子序列 $P$，并且满足：

- 总共有 $m$ 个下标 $i$ 满足 $a_i > a_{i+1}$。

你只需计算出这样的序列总数对 $998244353$ 取模的结果。

inputFormat:
第一行输入四个整数 $\alpha$，$n$，$m$，$n_0$。

第二行输入 $\alpha n_0$ 个正整数，保证构成一个 $(n_0,\alpha)$ 阶排列。

outputFormat: 输出一个整数，表示满足要求的序列的数量。

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

子任务 $1$（$10$ 分）：保证 $n \leq 2000$。

子任务 $2$（$10$ 分）：保证 $\alpha = 1$，$n_0=1$。

子任务 $3$（$30$ 分）：保证 $\alpha = 1$。

子任务 $4$（$15$ 分）：保证 $\alpha = 2$，$n_0=1$。

子任务 $5$（$15$ 分）：保证 $\alpha = 2$。

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

对于所有数据，保证 $1\leq n \leq 2\times 10^5$，$0\leq m < n$，$1\leq n_0\leq n$，$1\leq \alpha n_0 \leq 2\times 10^5$。

**【提示】**

为了方便选手处理形式幂级数的运算，我们提供了一个模板。选手可以根据自己的需要参考与使用该模板，也可以不使用该模板。


title: [WC/CTS2023] 楼梯

background:
长颈鹿累了，他开始做梦。

在梦中他下坠。他穿过草地，穿过打着转的羊群。他穿过星海，穿过漫天的火羽。

终于，他站在了一块屏幕前。屏幕上展示着某种类似楼梯的图样。

description:
我们首先给出一些关于楼梯的形式定义。

我们称一对正整数组成的二元组 $(x,y)$ 为**格子**，称格子构成的集合 $L$（可以为空）为**楼梯**当且仅当其满足下面两个条件：

+ 若 $(x,y)\in L$ 且 $x>1$，则 $(x-1,y)\in L$。
+ 若 $(x,y)\in L$ 且 $y>1$，则 $(x,y-1)\in L$。

对于一个楼梯 $L$ 和 $(x,y)\in L$，我们定义 $(x,y)$ 为**生成格**生成的**子楼梯**为

$$
\{(a-x+1, b-y+1) \mid (a,b) \in L, a \ge x, b \ge y\}
$$

容易证明这一集合仍然是一个楼梯。对于一个楼梯 $L$，我们定义**边界格数**为满足 $x=1$ 或 $y=1$ 的 $(x,y) \in L$ 的数量。

为了方便理解，我们接下来给出直观解释。我们在平面上可以将所有格子按从左到右 $y$ 坐标递增、从上到下 $x$ 坐标递增的顺序排列成网格，因此我们也称 $(x,y)$ 为第 $x$ 行第 $y$ 列的格子。

在这一解释下，若一个格子属于某个楼梯，且它上方和左方不是边界，则对应格子也属于这个楼梯。子楼梯就是生成格右下方区域格子所构成的非空楼梯，一个楼梯的边界格数是上边界或左边界上的总格数。

如下图，$(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(4,1),(5,1)$ 组成了一个合法的楼梯。这一楼梯的边界格数为 $8$，其中以 $(1,3)$ 作为生成格生成的子楼梯的边界格数为 $4$。

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

长颈鹿看到屏幕上的楼梯后很好奇。他首先计算出了这一楼梯的边界格数 $p$，并给定了 $p$ 的某一**正整数因子** $q$。他想要知道，给定的楼梯是否有子楼梯满足边界格数等于 $q$。如果是，他希望你给出**任一**这样的子楼梯的生成格。

梦境时常变化，因此长颈鹿可能会有许多次这样的询问，楼梯也可能会发生变化。初始楼梯 $L$ 为空，对于 $i \ge 1$ 记 $s_i$ 为最大的满足 $(i,s_i) \in L$ 的正整数，若不存在则令其为 $0$，则有若干次三种之一的修改：

- 给定正整数 $a$ 和 $b$，在前 $a$ 行的末尾插入 $b$ 格。形式化地，对于 $i=1, 2, \dots, a$，将 $(i,s_i+1), (i,s_i+2),\dots,(i,s_i+b)$ 加入 $L$。
- 给定正整数 $a$ 和 $b$，在第 $a$ 行后（包含第 $a$ 行）的所有行行末尾删去 $b$ 格，若不足则删空。形式化地，对于 $i=a,a+1,a+2,\dots,10^{100}$，将 $(i,s_i),(i,s_i−1),\dots,(i,s_i−b+1)$ 从 $L$ 中移除（不存在的则忽略）。
- 给定正整数 $u$，撤销之前的 $u$ 次操作，即将楼梯还原为 $u$ 次操作前的状态，**保证这 $u$ 次操作均为询问或在行末尾插入**。具体地，假设该操作为第 $t$ 次操作，我们一定有 $t>u$，且第 $t−1,t−2,\dots,t−u$ 次操作均为询问或在行末尾插入（即上述的第一种修改）。你只需要将楼梯还原为第 $t−u$ 次操作前的状态即可（当然，你应该保留询问的输出）。

可以证明每次修改之后得到的集合仍然是一个楼梯。

inputFormat:
输入数据第一行包含一个正整数 $m$，表示操作总数。

接下来 $m$ 行每行描述四种之一的操作，详细含义可参见题目描述一节。描述为由空格分隔的一个字符和一到两个正整数，具体地：

- `+ a b`：在前 $a$ 行的末尾插入 $b$ 格。
- `- a b`：在第 $a$ 行后（包括第 $a$ 行）的所有行行末尾删去 $b$ 格，若不足则删空。
- `R u`：撤销之前的 $u$ 次操作，即将楼梯还原为 $u$ 次操作前的状态。**保证这 $u$ 次操作存在且均为询问或在行末尾插入**，即该行之前的 $u$ 行均以 `+` 或 `?` 开头。
- `? q`：询问是否有边界格数等于 $q$ 的子楼梯，若有则给出任意合法生成格。**保证 $q$ 是当前楼梯边界格数的因子**。

outputFormat:
对于每个询问（`?` 操作）输出一行。

如果存在边界格数等于 $q$ 的子楼梯，输出一行两个用空格分隔的正整数 `x y`，表示一个合法生成格是 $(x,y)$。否则输出一行两个用空格分隔的 $-1$。

samples:
见附件中的 stairs2.in
见附件中的 stairs2.ans

samples:
见附件中的 stairs3.in
见附件中的 stairs3.ans

samples:
见附件中的 stairs4.in
见附件中的 stairs4.ans

samples:
见附件中的 stairs5.in
见附件中的 stairs5.ans

samples:
见附件中的 stairs6.in
见附件中的 stairs6.ans


title: [WC/CTS2023] 比赛

description:
有 $n$ 名学生，标号从 $1$ 到 $n$，他们一共加入了 $m$ 个社团。由于一些奇怪的原因，**任意两个社团至多只包含一名公共成员**。

现在学校要组织一场比赛，想让这 $n$ 名学生围成一个圈。为了防止作弊，校长希望**圈上任意连续三个人不来自同一个社团**。

校长找到了你，希望你给他一组圆排列学生的方案，或指出这样的方案并不存在。

inputFormat:
第一行包含一个正整数 $T$，表示数据组数。

对于每组数据：

第一行包含两个非负整数 $n, m$，分别表示学生的数量和社团的数量。

接下来 $m$ 行，其中的第 $i$ 行的第一个整数为 $k_i$，表示第 $i$ 个社团的人数，紧随着 $k_i$ 个不重复的整数 $a_{i,1}, a_{i,2}, \dots, a_{i, k_i}$，表示第 $i$ 个社团的成员的标号。

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

如果存在满足条件的圆排列，则该行包含 $n$ 个整数，表示一个满足条件的圆排列。**如果有多个满足条件的圆排列，输出任意一组均可**。

如果不存在满足条件的圆排列，则该行仅包含一个整数 $-1$。

samples:
见附件中的 contest2.in
见附件中的 contest2.ans

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

在正式评测时，**任意一组满足条件的圆排列**都被视为正确，无论排列以谁开始，以哪个方向。

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

这个样例中前 $110$ 组数据满足 $n \le 15$，后 $35$ 组数据满足 $n \le 45$。

**【数据范围】**

对于所有的测试点，保证 $T \ge 1$，$n \ge 3$，$\sum n \le 2000$，$m \ge 0$，$3 \le k_i \le n$，$1 \le a_{i,j} \le n$，$a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$ 互不相同，且满足题中所述性质（任意两个社团至多包含一名公共成员）。

每个测试点的具体限制见下表：

| 测试点编号 | $n$ | $m$ | 特殊性质 |
| :-: | :-: | :-: | :-: |
| $1 \sim 2$ | $\leq 9$ | 无 | 无 |
| $3 \sim 4$ | $\leq 15$ | 无 | 无 |
| $5 \sim 6$ | $\leq 45$ | 无 | 无 |
| $7 \sim 8$ | $\leq 400$ | $= 1$ | 无 |
| $9 \sim 12$ | $\leq 400$ | 无 | 保证 $a_{i,j+1} = a_{i,j} + 1$ |
| $13 \sim 16$ | $\leq 400$ | 无 | 无 |
| $17 \sim 18$ | $\leq 2000$ | $= 1$ | 无 |
| $19 \sim 21$ | $\leq 2000$ | 无 | 保证 $a_{i,j+1} = a_{i,j} + 1$ |
| $22 \sim 25$ | $\leq 2000$ | 无 | 无 |

可以使用下发文件（题目附件）中的 `chk.cpp` 以检验你的输出的合法性，使用时先将其编译为可执行文件 `chk`。

+ Linux 系统使用 `./chk <input‐file> <output‐file> <answer‐file>` 测试
+ Windows 系统使用 `chk <input‐file> <output‐file> <answer‐file>` 测试。


title: [WC/CTS2023] 树据结构

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

**在提交本题前请务必仔细阅读以下内容。**

本题只支持 C++ 语言提交（建议使用 C++14，请不要使用 C++14 (GCC9)）。

由于洛谷特殊的交互机制，在提交本题时，请去掉代码中的 ```#include "ds.h"``` 语句，并将以下内容粘贴到代码最开头，然后提交：

```cpp
#include <vector>
void exchange(int x, int y);
int query(int u);
void answer(std::vector<int> par, std::vector<int> val);
```

如果您在提交本题时出现了任何意外的情况，请咨询管理员。

description:
作为一个熟练的 OI 选手，你对数据结构的各种题型早已轻车熟路，比赛中只要碰到数据结构题就能三下五除二轻松搞定。这一天，你翻开 OJ，看到了这道题：

给定 $n$ 个点的有根树，点编号为 $1, 2, \dots, n$，$1$ 为根。每条边上有一个 $1$ 至 $n - 1$ 的**两两不同**的权值。维护一个数据结构，支持交换**权值为 $x$ 和 $y$** 的边的权值，以及询问从根节点到 $u$ 号点的所有的边的权值最大值。

这种简单而经典的树上问题，对你已经是不在话下。厌倦了维护修改，回答询问的你，打算换一个角色。这回，你才是那个提问题的人，你需要构造合适的操作来套取题的数据。

具体地说，现在你并不知道树的结构，也不知道初始时树上每条边的权值，你需要通过如下两种操作得到树的结构和 **初始时** 树上每条边的权值：

1. 给出正整数 $x, y$，其中 $1 \le x, y < n$，$x \neq y$，交换 **权值为 $x, y$** 的两条边的权值。
2. 给出正整数 $u$，其中 $2 \le u \le n$，并得到从 $1$ 号点到 $u$ 号点的路径上所有边中权值的最大值。

**题目保证树的形态和每条边的权值是预先给定的，不会根据你的操作而动态生成。**

**【实现细节】**

你需要引用头文件 `#include "ds.h"`。你可以调用以下函数与交互库进行交互：

```cpp
void exchange(int x, int y);
```

+ 这个函数对应操作 $1$，表示交换**权值为 $x, y$** 的两条边的权值。
+ 你需要保证 $1 \le x, y < n$，$x \neq y$。

```cpp
int query(int u);
```

+ 这个函数对应操作 $2$，返回从 $1$ 号点到 $u$ 号点的路径上所有边的权值的最大值。
+ 你需要保证 $2 \le u \le n$。

```cpp
void answer(std::vector<int> par, std::vector<int> val);
```

- 这个函数用来回答你所得到的答案，格式如下：
  - `par` 是一个长度为 $n - 1$ 的数组，其中 `par[i]` 表示树上 $i + 2$ 号节点的父亲编号，其中 $0 \le i \le n - 2$。
  - `val` 也是一个长度为 $n - 1$ 的数组，其中 `val[i]` 表示树上 $i + 2$ 号节点到它父亲的边的**初始权值**，其中 $0 \le i \le n - 2$。
- **你需要调用该函数恰好一次！**

你不需要，也不应该实现主函数。在本题中，你只需要实现如下函数：

```cpp
void solve(int n, int lim1, int lim2);
```

- 其中，$n$ 表示树的点数，$lim1$ 表示操作 $1$ 的次数限制，$lim2$ 表示操作 $2$ 的次数限制。
- 最终测试时，对于每个测试点，交互库会调用**恰好一次** `solve` 函数，并根据调用 `answer` 函数的正误来评分。

在题目附件中，我们提供了 `sample.cpp` 供你参考，你可以在此基础上实现你的程序。

**【测试程序方式】**

题目附件中提供了 `grader.cpp` 文件。最终测试的交互库与下发交互库有不同，因此你的实现不应依赖交互库实现。

你需要将你的程序 `ds.cpp` 和 `grader.cpp`、`ds.h` 放置在同一目录下，并在该目录下使用如下编译命令得到可执行程序 `ds(.exe)`：

```bash
g++ -o ds ds.cpp grader.cpp -O2 -std=c++14 -lm
```

**题目附件还提供了 `compile.sh`，其内容为该编译命令。你可以运行它进行编译，也可以复制该文件中的编译命令进行编译。**

可执行程序从标准输入读入以下格式的数据：

- 第一行包含三个正整数 $n, lim1, lim2$，表示树的点数，操作 $1$ 的限制次数和操作 $2$ 的限制次数。交互库保证可以处理 $2 \le n \le 500000$ 的情况，对于 $n > 500000$ 的情况不做正确运行保证。
- 第二行 $n - 1$ 个正整数 $p_2, p_3, \dots, p_n$。其中 $p_i$ 表示 $i$ 号点的父亲的节点编号。**你需要保证 $1 \le p_i \le n$ 且输入给出了合法的树的结构。**
- 第三行 $n - 1$ 个正整数 $v_2, v_3, \dots, v_n$。其中 $v_i$ 表示 $i$ 连向 $p_i$ 的边的权值。**你需要保证 $v_2, v_3, \dots, v_n$ 构成 $1$ 至 $n - 1$ 的一个排列。**
- **在本地测试时，请务必保证你的输入格式符合要求，否则我们不保证交互库会正常运行。**

如果你的输入合法且没有运行错误，下发的交互库将会根据你的调用输出如下信息：

- 如果某次 `exchange` 函数的调用违反了 $1 \le x, y < n$，$x \neq y$ 的限制，输出错误信息：`Invalid call of exchange(x, y)!`。
- 如果 `exchange` 函数调用次数超过 $lim1$，输出错误信息：`Too many exchanges!`。
- 如果某次 `query` 函数的调用违反了 $2 \le u \le n$ 的限制，输出错误信息：`Invalid call of query(u)!`。
- 如果 `query` 函数调用次数超过 $lim2$，输出错误信息：`Too many queries!`。
- 在输出任何以上错误信息后，交互库立即终止。
- 交互库会在你**每次**调用 `answer` 函数时输出提示信息：
  - 如果 `par` 或 `val` 的长度不是 $n - 1$，则输出 `Invalid output!`。
  - 如果 `par` 数组与树的形态不同，那么它会给出**第一个**错误的位置，并返回如下格式的错误信息：`The answer to p[i] is wrong! The right answer is j, but you output k.`。注意，这里 $2 \le i \le n$，$j = p_i$ 为 $i$ 号点的真正的父亲编号，$k = $ `par[i - 2]` 为你给出的位置编号。
  - 如果 `par` 数组正确，但 `val` 数组与**初始时**树上边权值不同，那么它会给出你**第一个**错误的位置，并返回如下格式的错误信息：`The answer to v[i] is wrong! The right answer is j, but you output k.`。类似地，这里 $2 \le i \le n$，$j = v_i$ 为 $i$ 号点到它父亲的边的真正的初始权值，$k =$ `val[i - 2]` 为你给出的权值。
  - 如果你给出的 `par` 和 `val` 数组正确，那么交互库会输出你调用 `exchange` 函数和 `query` 函数的次数。输出格式为：`Right output! cnt1 = A, cnt2= B.`，其中 $A$ 表示你调用 `exchange` 函数的次数，$B$ 表示你调用 `query` 函数的次数。
- **使用下发的交互库时你可以通过调用多次 `answer` 函数对你的程序进行测试。但对于你提交的代码，如果调用 `answer` 函数超过 $1$ 次，便只能获得 $0$ 分。**

**你的程序不应该操作标准输入输出，否则视为攻击交互库。**

inputFormat: 见【测试程序方式】。

outputFormat: 见【测试程序方式】。

samples:
见附件中的 ds2.in
见附件中的 ds2.ans

samples:
见附件中的 ds3.in
见附件中的 ds3.ans

samples:
见附件中的 ds4.in
见附件中的 ds4.ans

samples:
见附件中的 ds5.in
见附件中的 ds5.ans

samples:
见附件中的 ds6.in
见附件中的 ds6.ans

samples:
见附件中的 ds7.in
见附件中的 ds7.ans


title: [PA2018] Wielokąty

description:
**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 5 [Wielokąty](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/wie/)** 。

请求出满足以下条件的多边形的个数：

-  记该多边形的第 $i$ 个顶点为$(x_i,y_i)$ ，则 $x_i,y_i \in \mathbb{Z}$ 且 $1 \le x_i \le X$ , $1 \le y_i \le Y$ 。
-  该多边形的任意一条边（不包含端点）不能经过格点（即横纵坐标都为整数的点）。
-  该多边形的每一条边的长度都是不超过 $K$ 的整数。
-  该多边形是一个凸多边形，而且不能退化（不能出现三点共线，自切，不小于 $180 ^{\circ}$ 的角）。
-  该多边形的每一条边都是线段。

由于满足条件的多边形数量太大，你只需要输出其对 $2^{32}$ 取模后的值即可。

下图展示了三个不合法的多边形。第一个多边形的边经过了格点，第二个多边形退化了，第三个多边形不是凸的。而且第一，三个有的边长不是整数。

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

我们将两个多边形看做不相同的多边形，当且仅当它们有至少一个顶点不相同。

inputFormat: 输入只有一行，包含三个正整数 $X,Y,K$。

outputFormat: 输出一行一个整数，即为满足条件的多边形的数量对 $2^{32}$ 取模后的值。

hint:
#### 样例 1 解释

下图展示了 $42$ 个合法多边形中的一个多边形。

可以验证，该多边形满足每一个条件。

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

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

#### 数据范围

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

对于 $100\%$ 的数据，保证 $1 \le X,Y \le 10^9,1 \le K \le 250$ 。


title: 「LAOI-1」GCD

description: 一张图有 $n$ 个节点，编号为 $1,2,3,\dots,n$。其中 $i$ 号节点会向 $j$ 号节点连一条边权为 $|i-j|$ 的无向边，当且仅当 $\gcd(i,j)=i,\operatorname{lcm}(i,j)=j$ 时连边。现询问 $q$ 次，每次询问求 $x$ 到 $y$ 的最短路径。

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

每组数据的第一行两个正整数 $n,q$，表示节点数和询问次数。

接下来 $q$ 行，每行两个正整数 $x,y$，表示起点和终点。

outputFormat: 对于每组询问，输出一个正整数。相邻两个输出以换行符隔开。

hint:
注意时空限制，本题不捆绑。

对于 $40\%$ 的数据，$T,n,q\le100$;

对于 $100\%$ 的数据，$1\le T\le10^6$，$1\le n,q\le10^6$，$1\le x,y\le n$，$1\le \sum n,\sum q\le10^6$。

**请使用更快的 IO 方式**。

updata on 2024/8/8：

时限上调到 1000ms。/yun


title: 「TAOI-2」Break Through the Barrier

description:
有一个由 $\tt B$ 和 $\tt T$ 组成的字符串。

你可以进行如下操作：选择一个长度为 $4$ 的子串，其恰好等于 $\texttt{BTTB}$，并将其修改为 $\texttt{TBBT}$。你可以进行这种操作任意多次（也可以不操作）。

定义一个字符串的权值为最长的 $\texttt{T}$ 连续段长度。你需要通过如上操作使得字符串的权值尽可能大。输出这个最大值。

+ 子串的定义：一个字符串 $b$ 被称为字符串 $a$ 的子串，当且仅当可以通过删除 $a$ 开头若干个（可以是 $0$ 个，下同）字符和结尾若干个字符得到 $b$。
+ $\texttt{T}$ 连续段的定义：一个原字符串的仅由 $\texttt{T}$ 构成的子串。

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

接下来每组数据，第一行一个正整数 $n$ 表示字符串长度，第二行一个长度为 $n$ 的字符串 $S$，表示题目中的字符串。

outputFormat: $T$ 行，每行一个非负整数，表示最长 $\texttt{T}$ 连续段的长度。

samples:
6
3
TTT
4
BTTB
5
TBBTT
6
BTBTBB
7
BTTBTTB
17
TTBTBTTBTBTTTBTTB

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

记 $\sum n$ 为所有数据中的 $n$ 的和。

+ Subtask 0（5 pts）：$n \leq 7$。
+ Subtask 1（20 pts）：$T \leq 10$，$n \leq 10$。
+ Subtask 2（25 pts）：$\sum n \leq 5000$。
+ Subtask 3（5 pts）：保证给定的字符串无法进行任何操作。
+ Subtask 4（45 pts）：无特殊限制。

对于所有数据，$1 \leq T \leq 10^3$，$1 \leq n \leq 10^5$，$1 \leq \sum n \leq 5\times 10^5$，字符串只包含字符 `B` 和 `T`。


title: 『STA - R2』Locked

background: GOD_hj 有一把数字密码锁，但是他陷于 whk，没时间来开锁。

description:
这把锁从左到右有 $n$ 个数，组成了一个序列 $\{a\}$。

由于 GOD_hj 的记性不好，所以只要将锁设置为输入任意单峰序列即可打开。具体为：
$$ a_1 \le \cdots \le a_i \ge a_{i+1} \ge \cdots \ge a_n\quad (1 \le i \le n) $$

GOD_hj 的锁是拨动式的，即拨一下就能换成临近的一个数（$0$ 和 $9$ 可以互换）。

求最少拨几下可以开锁。

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

第二行 $n$ 个整数，为序列 $\{a\}$。

outputFormat: 一个整数，为最少要拨动几下。

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

样例二：把第四个 $5$ 变为 $6$ 或把第三个 $6$ 变为 $5$。

**【数据范围】**

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

$$
\newcommand{\arraystretch}{1.5}
\begin{array}{c|c|c|c}\hline\hline
\textbf{Subtask} & \bm n\le &\textbf{分值}&\textbf{特殊性质} \\\hline
\textsf{1} & 5 & 5 & \textbf{无} \\\hline
\textsf{2} & 10^3 & 25 & \textbf{无} \\\hline
\textsf{3}  & 5\times 10^5 & 20 & \textbf{无} \\\hline
\textsf{4} & 5\times 10^6 & 10 & a_i\in\{0,1\} \\\hline
\textsf{5} & 5\times 10^6 & 40 & \textbf{无} \\\hline\hline
\end{array}
$$

对于全部数据，$1\le n\le 5\times 10^6$，$0\le a_i<10$。

**Upd on 2023/06/12**：新加 5 组 Hack 数据，放入 Subtask 6，不计分。


title: [COCI2022-2023#4] Bojanje

description:
Oliver 是一只不仅能找出 bug 并且喜欢画画的小黄鸭。他最新的画有 $n$ 个部分，每部分用一种不同的颜色涂色。在此之后他得到了很多批评，因为他的画太可预测了。他决定用 $t$ 次迭代修改他的画。在每次迭代中他将做以下操作：

Oliver 会均匀随机选择一个下标 $i\ (1\le i\le n)$，然后记住画中第 $i$ 部分的颜色。
Oliver 会再均匀随机选择一个下标 $j\ (1\le j\le n)$。他会把画中第 $j$ 部分涂成和第 $i$ 部分一样的颜色。如果第 $j$ 部分的颜色和第 $i$ 部分相同，那么不会有任何改变。注意 $i$ 可以等于 $j$。
现在，Oliver 害怕他的画会变得十分单调或者无聊。他认为一幅画是好的，如果画上至少有 $k$ 种不同的颜色。请帮他计算最后这幅画是好的这个事件的概率。

inputFormat: 第一行包含三个整数 $n,t,k\ (2\le k\le n\le 10,1\le t\le 10^{18})$，意义如题目描述。

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

形式化地，令 $m=10^9+7$。可以知道答案可以用不可约分数  $\frac{p}{q}$ 表示，其中 $p$ 和 $q$ 是整数，$q\not\equiv 0 \pmod m$。输出 $p\cdot q^{-1}\bmod m$。换句话说，输出满足 $0\le x<m$ 且 $x\cdot q\equiv p\pmod m$ 的整数 $x$。

hint:
样例 $1$ 解释：画上有两种颜色，所以一次迭代后画和未操作之前相同的概率是 $\frac{1}{2}$。

样例 $2$ 解释：在两次迭代后，不同的颜色数不可能从 $10$ 变为小于 $5$，所以在任何情况下这幅画都会有至少 $5$ 种不同的颜色。

| 子任务编号 | 附加限制 | 分值 |
|:-:|:-:|:-:|
| $0$ | 是样例 | $0$ |
| $1$ |	$k=n$ | $28$ |
| $2$ |	$t\le 1000$ | $36$ |
| $3$ |	无附加限制 | $36$ |


title: [COCI2022-2023#4] Mreža

background: ### 卡评测封号。

description:
市长 Mirko 住在一个有 $n$ 个社区的城市里，这 $n$ 个社区用 $n-1$ 条双向道路连接，满足从任何社区出发都可以到达任意其他社区。

Mirko 想升级一些道路以疏导交通。对于每条路，我们知道目前在这条路上汽车的行驶速度 $v_i$，升级所需花费 $c_i$ 和升级后在这条路上汽车的行驶速度 $s_i$。

有 $q$ 个不满意的市民来见 Mirko。每个人都有他们自己的升级建议。第 $i$ 个市民的建议是：「我们应该在升级社区 $a_i$ 和 $b_i$ 之间的道路上投资 $e_i$ 欧元。」

对于每个建议，Mirko 感兴趣的是，如果他的目标是使社区 $a_i$ 和 $b_i$ 之间的最低驾驶速度最大化，那么他在升级道路上最多花费 $e_i$ 欧元的话这个最低驾驶速度是多少。

Mirko 瞬间意识到这个问题不简单，并且他雇佣你来帮助他！

inputFormat:
第一行包含一个整数 $n\ (2\le n\le 10^5)$，表示社区总数。

接下来 $n-1$ 行，每行五个整数 $x_i,y_i,v_i,c_i,s_i\ (1\le x_i,y_i\le n,1\le v_i<s_i\le 10^9,1\le c_i\le 10^9)$，表示社区 $x_i$ 和 $y_i$ 之间有一条路相连，目前在这条路上汽车的行驶速度为 $v_i$，升级所需花费为 $c_i$，升级后在这条路上汽车的行驶速度为 $s_i$。

接下来一行一个整数 $q\ (1\le q\le 10^5)$，表示不满意的市民总数。

接下来 $q$ 行，每行三个整数 $a_i,b_i,e_i\ (1\le a_i,b_i\le n,a_i\neq b_i,1\le e_i\le 10^{18})$，意义如题目描述。

outputFormat: 输出 $q$ 行，表示对每个市民建议的答案。

hint:
样例解释 $1$：下图展示了这个城市和社区。边上写的分别是目前汽车的行驶速度，升级花费和升级后的汽车行驶速度。

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

如果我们升级 $1$ 和 $2$，$1$ 和 $3$ 之间的道路，从 $2$ 到 $4$ 的行驶速度将变成 $10,9,7$。最小为 $7$。

如果我们升级 $4$ 和 $3$ 之间的道路，从 $6$ 到 $4$ 的行驶速度将变成 $5,15$。最小为 $5$。

如果我们升级 $3$ 和 $5$ 之间的道路，从 $5$ 到 $3$ 的行驶速度将变成 $11$。

|子任务编号|	附加限制|	分值|
|:-:|:-:|:-:|
| $0$ | 是样例 | $0$ |
| $1$ | $n,q\le 1000$ |	$19$ |
| $2$ |	每个社区最多与两个其他社区相连 | $26$ |
| $3$ |	无附加限制 | $55$ |


title: [COCI2022-2023#4] Vrsta

description:
Domagoj 最喜欢的课是体育课。每节体育课都以热身运动开始。体育老师有一个有趣的方法来选择带领其他同学做热身运动的学生。学生们按身高从低到高的顺序站成一排，老师会选择站在队伍中间的学生。如果有两个学生在中间，他将选择较矮的那个。例如：如果学生的身高为 $1, 3, 5, 7, 11$，身高为 $5$ 的学生将带领其他同学做热身运动。

Domagoj 记不住他同学的身高。幸运的是，站在他旁边的 Lovro 十分擅长估计他人的身高。他给了 Domagoj $n$ 条信息：「有 $a_i$ 个身高为 $v_i$ 的学生进入了体育馆。」在 Lovro 说完每条信息之后，Domagoj 都对带领其他同学做热身运动的那个同学的身高感兴趣。假定所有进入体育馆的同学都是来上体育课的。请帮他回答他的问题！

inputFormat:
第一行一个整数 $n\ (1\le n\le 200\ 000)$，表示 Lovro 的信息条数。

接下来 $n$ 行包含两个整数 $v_i,a_i\ (1\le v_i,a_i\le 10^9)$，表示 Lovro 所给信息中的身高和人数。

outputFormat: 输出 $n$ 行，表示在 Lovro 给出第 $i$ 条信息后，对 Domagoj 问题的回答。


title: [COCI2022-2023#4] 7Krokods

description:
Krokod 喜欢和 Paula 玩棋盘游戏。他想玩 7Krokods 游戏，但 Paula 不喜欢复杂的游戏，所以 Krokod 决定他们只用绿卡和鳄鱼卡来玩。

Paula 有 $n$ 张绿色卡片，每张卡片上都写有以下字母之一：$d,k,o,r$。

她的总得分被定义为以下部分的总和。

- 对于每个字母，她得到的分数与写有该字母的卡片数量的平方相同。例如，如果她有 $6$ 张写有字母 $k$ 的卡片，她可以得到 $36$ 分。
- 每凑成一个单词 `krokod`，她就能得到额外的 $7$ 分。

Paula 也有 $m$ 张鳄鱼卡。她可以用任何一张绿卡代替一张鳄鱼卡，绿卡上有她选择的字母。

请计算她的牌能得到的最大分数。

inputFormat:
第一行两个整数 $n$ 和 $m(0\leq n\leq 100，0\leq m\leq 10)$，表示绿卡的数量和鳄鱼卡的数量。

第二行包含一个 $n$ 个字符的序列，其中第 $i$ 个字符代表第 $i$ 张绿卡上的字母。该序列仅由字符 $d,k,o,r$ 组成。

outputFormat: 一行一个整数，输出 Paula 的最大可能得分。

hint:
样例 $1$ 解释：

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

Paula 有 $2$ 个字母 $d（2\times 2=4$ 分），$6$ 个字母 $k（6\times 6=36$ 分），$4$ 个字母 $o（4\times 4=16$ 分）和 $3$ 个字母 $r（3\times 3 = 9$ 分）。单词 krokod 可以拼写 $2$ 次（$7\times 2=14$ 分）。她的总分是
$79$。（$4 + 36 + 16 + 9 + 14 = 79$）。

样例 $2$ 解释：

Paula 可以把她的鳄鱼卡换成一张上面写着字母
 $k$ 的绿卡。

 |子任务编号|	附加限制|	分值|
|:-:|:-:|:-:|
| $0$ | 是样例 | $0$ |
| $1$ |	$m=1$ | $17$ |
| $2$ |	$m=2$ | $26$ |
| $3$ |	无附加限制 | $7$ |


title: [COCI2022-2023#4] Zrinka

description:
给你两个长度分别为 $n$ 和 $m$ 的数组，它们只由 $0$ 和 $1$ 组成。

你的任务是用偶数替换每个 $0$，用奇数替换每个 $1$。

替换之后，两个数组都应该是单调递增的且所有元素均大于 $0$，并且你最多可以使用每个正整数一次，使用的最大数字要尽可能的小。

inputFormat:
第一行由 $n+1$ 个整数组成，第一个是 $n(n\leq 5000)$，其他是描述第一个数组的。

第二行由 $m+1$ 个整数组成，第一个是 $m(m\leq 5000)$，其他是描述第二个数组的。

outputFormat: 一行一个正整数，即最大数字。


title: [Ynoi Easy Round 2024] TEST_133

description:
给定序列 $a_1,\dots,a_n$， $m$ 次操作：

修改操作：给出 $l,r,x$，将 $a_l,a_{l+1},\dots,a_r$ 的值增加 $x$；

查询操作：给出 $l,r,x$，问满足 $l\le i\le r,\;a_i<x$ 的 $i$ 对应 $a_i$ 的历史最大值（即初值和每次修改操作后的值中最大的一个）。

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

接下来一行 $n$ 个整数 $a_1,a_2,\dots,a_n$；

接下来 $m$ 行每行四个整数 $o,l,r,x$，其中 $o=1$ 表示修改操作，$o=2$ 表示查询操作。

outputFormat: 对每个查询操作，输出一行，表示答案（特别地，如果不存在满足条件的 $i$，则输出 `-inf`）。

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

对于 $0\%$ 的数据，满足 $n,m\le 5000$。

对于另外 $1/3%$ 的数据，查询操作保证 $l=1,\;r=n$。

对于另外 $1/3$ 的数据，没有修改操作。

对于 $100\%$ 的数据，满足 $1\le n,m\le 5\times 10^5$，$|a_i|\le 10^9$（仅初始给定的序列保证这个限制），$1\le l\le r\le n$，$|x|\le 10^9$。


title: [ZSHOI-R1] 新概念报数

background: Div.2 A 要什么背景？

description:
现在 Xttttr 和他的 npy 玩起了报数游戏，但是他们非常喜欢 $2$ 这个数字，于是制定了如下规则：

- 如果一个数 $a$ 满足 $\operatorname{popcount}(a) \geq 3$，那么这个数字是非法的，对方需要回答 ``No,Commander``。
- 否则，这个数是合法的，对方需要回答下一个合法的数。

坐在旁边的你当然不知道游戏的乐趣，你只想知道某次报数之后对方应该回答什么。

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

后面 $T$ 行，每行一个自然数 $a$，表示这次询问中某一方报出的数字。

outputFormat: $T$ 行，每行一个正整数或字符串，表示本次询问中对方所应该回答的。

hint:
对于 $20\%$ 的数据，保证 $T\leq 100$，$a \leq 10^4$。

对于另外 $20\%$ 的数据，保证 $a$ 是合法的数字。

对于另外 $20\%$ 的数据，保证 $a$ 在值域内均匀随机。

对于 $100\%$ 的数据，$1\leq T \leq 10^5$，$0\leq a<2^{63}$。


title: 「RiOI-2」tnelat

background:
小 E 是一名一年级的小学生。她正在学习如何阅读。

如果在纸上写上 $998,\!244,\!353$，那么她就会读「三——五三四四——二八九九。」是的，她是从右往左读的。然后，她会把这个数理解为 $353,\!442,\!899$。

不过这并不影响她交流——她只是不会读纸上的文字罢了。唯一的问题是，她现在要学习带余除法了，而老师说不定会在纸上画一些红色的叉叉。不过，那又如何？

description:
对于一个长度为 $n$ 的**由数字组成的**字符串 $s=s_1s_2s_3\cdots s_n$，定义它的权值为 $f(s)=\sum\limits_{i=1}^n 10^{n-i}s_i$。（也就是它代表的十进制数）定义它的反串为 $\overline s=s_ns_{n-1}s_{n-2}\cdots s_1$。例如，$s=\texttt{0321}$ 的权值为 $f(s)=321$，反串为 $\overline s=\texttt{1230}$。

试构造一个字符串 $s$，使得 $|s|\le 114514$，且 $f(s)\equiv a\pmod {998,\!244,\!353}$ 且 $f(\overline s)\equiv b\pmod{998,\!244,\!353}$。如果 $c=0$，你还要保证 $s_1\neq \texttt0$ 且 $s_n\neq \texttt 0$。
如果无解，仅输出整数 $-1$ 即可。

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

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

第二行一个整数 $c$，意义如题目所述。

接下来 $T$ 行，每行两个以空格隔开的自然数 $a, b$ 描述一组数据。

outputFormat:
输出 $T$ 行，每行一个正整数表示你构造的数。

**本题开启 Special Judge，只要你的输出符合要求即可得到该测试点的分数。**


title: [PA2020] Liczba Potyczkowa

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda próbna [Liczba Potyczkowa](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/lic/)。**

Bajtek 在数学史课上了到解了一位俄罗斯数学家弗拉基米尔·波季奇科夫（Vladimir Potyczkow）。这位科学家以对数字的研究而闻名，为了纪念他，今天我们将这些数称为 **Potyczkow 数**：是一个正整数，并且可以用其十进制表示中出现过的每个数字整除。特别地，这意味着十进制表示中不能有零。例如 $48$、$1$ 和 $112$ 是 Potyczkow 数，而 $23$、$10$ 和 $121$ 不是。Bajtek 想知道在 $[l, r]$ 范围内有多少这样的数，请帮助他数一数！

inputFormat: 一行输入两个正整数 $l,r$。

outputFormat: 输出一行一个整数，表示在 $[l, r]$ 范围内 Potyczkow 数的数量。


title: [PA2020] Punkty rankingowe

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 1 [Punkty rankingowe](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/ran/)。**

Bytie 决定认真准备今年的 PA。为了训练，他创建了一个 BitForces 账号，BitForces 是一个定期举办编程竞赛的平台。

Bytie 知道这个平台使用一种积分系统（也称为 rating），这个系统会让他知道自己的进步，也可以将自己的成绩与其他选手比较。选手的 rating 是一个整数（可能为负数）。在账号创建后，Bytie 的 rating 是 $0$，参加每场比赛后，他的 rating 都会加或减某一个整数。此外，在每场比赛后的 rating 变化历史是可以在平台上看到的。兴奋的 Bytie 开始分析这些数据。他在纸上写下了 $n$ 个连续的数字：

- 在一场比赛之后的最大 rating 上升；
- 在连续两场比赛之后的 rating 上升之和的最大值；
- 在连续三场比赛之后的 rating 上升之和的最大值；
- 以此类推，直到他写到在连续 $n$ 场比赛之后的 rating 上升之和的最大值；

几天后 Bytie 想要回想起 rating 变化的序列。然而，此时 BitForces 正出现技术问题。请帮助 Bytie 还原一个合法的 rating 变化序列，使其长度至少为 $n$ 并且符合写在纸上的数据。

inputFormat:
输入第一行包含一个整数 $n$，表示写在纸上的数字个数。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。对于每个 $1\le j\le n$，连续 $j$ 场比赛的 rating 最大增幅恰好为 $a_j$。

outputFormat:
如果存在一个 rating 变化序列满足所有题目描述中的条件，输出一行 `TAK`。之后输出一行一个整数 $k$。第三行输出找到的 rating 变化序列 $b_1,b_2,\ldots,b_k$。如果有多种答案，输出任意一种均可。

如果不存在这样的变化序列，输出一行 `NIE` 即可。

可以证明对于输入如果存在一个 rating 变化序列，那么一定存在一个满足以上限制的序列。

hint:
#### 样例 1 解释

以下是一、二、三、四次连续比赛中名次增加最多的区间。

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

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

#### 数据范围

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

对于 $100\%$ 的数据，保证 $1\le n\le 300$，$-10^6\le a_i\le 10^6$，$n\le k\le 10^5$，$-10^{13}\le b_k\le 10^{13}$。


title: [PA2020] Mieszanie kolorów

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 1 [Mieszanie kolorów](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/kol/)**

Byteasar 正准备给栅栏涂漆。他已经准备了 $n$ 罐白色油漆，他把这些油漆排列成一排，从 $1$ 到 $n$ 编号。他想用这些油漆，但他不想把栅栏涂成白色。他委托了调色专家，调色专家有三种颜料：黄色、蓝色和红色。专家进行了 $m$ 次操作，其中第 $i$ 次操作是向编号在 $l_i$ 到 $r_i$ 之间（包括两端）的所有罐子中加入某种颜料。

油漆的最终颜色取决于被添加到其中的颜料。添加的颜料按照下表和图示进行混合。

|        颜料        | 颜色 |
| :----------------: | :--: |
|         无         | 白色 |
|        黄色        | 黄色 |
|        蓝色        | 蓝色 |
|        红色        | 红色 |
|    黄色 + 蓝色     | 绿色 |
|    黄色 + 红色     | 橙色 |
|    蓝色 + 红色     | 紫色 |
| 黄色 + 蓝色 + 红色 | 棕色 |

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

Byteasar 想要给栅栏涂成一种颜色。思来想去，他选择了绿色，因为绿色代表了你常会在算法竞赛中看到的 Accepted。他想知道现在有多少罐油漆是绿色的，请帮他数数。

inputFormat:
第一行两个整数 $n,m$，分别表示油漆的罐数和专家进行的操作数。

接下来 $m$ 行，每行三个整数 $l_i,r_i,k_i$，表示在第 $i$ 次操作中向编号在 $l_i$ 到 $r_i$ 之间（包括两端）的罐子中加入颜料。加入的颜料是黄色（$k_i=1$），蓝色（$k_i=2$）或红色（$k_i=3$）中的一种。

outputFormat: 输出一行一个整数，表示在所有操作之后绿色油漆的罐数。

hint:
#### 样例 1 解释

操作结束后，这些油漆分别是蓝色、绿色、黄色、绿色、绿色、棕色、橙色、黄色和白色的。因此，只有三罐油漆是绿色。

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

#### 数据范围

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

对于 $100\%$ 的数据，保证 $1\le n,m\le 10^6$，$1\le l_i\le r_i\le n$，$1\le k_i\le 3$。


title: [PA2020] Wybór zadań

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 1 [Wybór zadań](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/wyb/)**

对 Matthew 来说，准备 PA 的线上比赛是一个相当大的挑战。在比赛期间，参赛者参加五轮比赛，编号从 $1$ 到 $5$。在每轮比赛中，参赛者需解决三个组别的任务，称为 A、B 和 C。在前四轮比赛中，每一组别都会有一道题，在最后的第五轮比赛中，每一组别都会有两道题。因此，必须一共造 $18$ 道题，并分配给 $15$ 个不同的位置，其中三个位置（5A、5B 和 5C）必须各分配两道题。我们这里所说的位置是指轮次和组别的组合。

Matthew 知道不能只是随便出 $18$ 道题。题目的难度应该适合他们出现的轮次和组别。他在一整年中整理了 $n$ 道题的想法。对于这些想法，他都知道这道题会适合哪个位置（只会适合这一个位置，其他位置都不适合）。

Matthew 想知道是否可以从他的想法中选出 $18$ 道题并正确地分配它们的位置。给定他的笔记记录，请帮他找出一种选择方案。

inputFormat:
第一行包含一个整数 $n$，表示 Matthew 的想法总数。

第二行有 $n$ 个字符串，表示 Matthew 的每个想法适合的题目位置。每个字符串由恰好两个字符组成，第一个字符是一个在集合 $\{1,2,3,4,5\}$ 的数字，第二个字符是一个在集合 $\{\texttt A,\texttt B,\texttt C\}$ 的字母。

outputFormat: 如果可以从 Matthew 的想法中组出一套 PA 题目，则输出 `TAK`，否则输出 `NIE`。

hint:
#### 样例 1 解释

在第一个样例中，Matthew 有三个符合 5C 位置的题目想法。删掉其中任何一个后，其余的想法就组成了一套合适的 PA 题目。

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

#### 样例 2 解释

在第二个例子测试中，Matthew 只有一道题与 5B 位置相匹配，所以他组不出一套 PA。

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

#### 数据范围

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

对于 $100\%$ 的数据，保证 $1\le n\le 100$。


title: [PA2020] Sen o podboju

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 2 [Sen o podboju](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/sen/)**

国王 Byteur，Byteotia 的统治者，目前正梦想着征服 Bitotia。就像在现实世界中一样，在他的梦中他还远远没有打败敌人。因此，他想知道他能做些什么来削弱敌国的实力……

在他的梦中，Bitotia 由 $n$ 个城市（编号从 $1$ 到 $n$）组成，由 $n-1$ 条双向道路连接，可以只用这些道路从任意一个城市到达任意其他城市。换句话说，Bitotia 的地图形成了一棵树。然而，Byteur 并不记得 Bitotia 的确切道路网络……所以他的脑内生成了一个**随机**的道路网络。

国王得出的结论是，强行将 Bitotia 分割成 $k$ 个小国是个好主意。Byteur 所说的划分，是指秘密地破坏正好是 $k - 1$ 条道路，这将迫使 Bitotia 分解成 $k$ 个小国，这些小国是去除选定的边后形成的连通子图。

然而，对于国王来说，摧毁任何 $k-1$ 条道路都是不够的。每个 Bitotia 的城市都有一个**军事系数** $a_i$，也是由 Byteur 脑内想出来的。Byteur 知道，一个小国的军事力量越强，对 Byteotia 的威胁就越大。更准确地说：如果在一个小国，其城市的军事系数之和等于 $S$，那么来自这个小国的威胁就等于 $S^2$。对 Byteotia 的总威胁等于这 $k$ 个小国所产生的威胁之和。

现在 Byteur 求助于你——他的梦想（指的是字面意思！）程序员。请帮助他，计算出 Bitotia 分裂成各州后可能产生的最小总威胁。由于 Byteur 还没有决定参数 $k$ 的值，请计算 $k$ 取从 $1$ 到 $n$（包含两端）所有值的结果。

inputFormat:
第一行包含一个整数 $t$，表示测试点总数 ~~Byteur 做的梦的个数~~。接下来描述每一组测试点，测试点的输入格式都相同。

每个测试点第一行包含一个整数 $n$。

第二行包含一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots ,a_n$。

接下来 $n-1$ 行是 Bitotia 的路网描述，每行两个整数 $b_i,c_i$，表示城市 $b_i,c_i$ 被一条路相连。保证输入的图是一棵树。

Byteur 按如下方法生成数据。首先手动选取一个整数 $t$，一个整数区间 $[n_{\min},n_{\max}]$ 和 $a_{\max}$ 的值。接下来按如下步骤独立生成每个测试点：

- 城市个数 $n$ 的值从 $[n_{\min},n_{\max}]$ 区间内均匀随机选取。
- 每个 $a_i$ 的值从 $[1,a_{\max}]$ 区间内独立均匀随机选取。
- 生成一个自然数序列 $(p_1,p_2,\cdots ,p_{n-2})$。序列中的每一个元素都是从 $[1,n]$ 区间中独立均匀随机选取的。Byteur 将其作为路网的 [Prüfer 序列](https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence)，也就是测试点中给出的树的 Prüfer 序列是 $(p_1,p_2,\cdots,p_{n-2})$。

outputFormat: 输出 $t$ 行，描述每个测试点的答案。每行包含 $n$ 个整数（其中 $n$ 是输入中的城市数量）；第 $k$ 个整数表示 Bitotia 在被划分为 $k$ 个小国后所能造成的最小威胁。

hint:
#### 样例 1 解释

以上测试数据使用随机数种子为 $8\ 122\ 020$，$t=2,n_{\min}=5,n_{\max}=7,a_{\max}=10$ 的参数生成。

对于第一个测试案例，输出的第一个数字是 $(9+1+4+2+6+4+7)^2=1089$，代表未被分割的 Bitotia 所带来的总威胁。输出的第二个数字对应的是如果连接 $5$ 号和 $7$ 号城市的道路被摧毁的总威胁；在这种情况下，威胁将是 $(9+7)^2+(1+4+2+6+4)^2=545$。

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

#### 数据生成

本题的样例生成器在附件中给出。生成器将以下内容作为输入接受：生成器种子和数字 $t,n_{\min},n_{\max},a_{\max}$。本题的所有测试数据都将用与之相当的生成器生成（即用不同的伪随机数库，与编译器的实现无关）。

为了确保测试的随机性，每个测试点的 $t,n_{\min},n_{\max},a_{\max}$ 的值都是手动选择的，生成器的种子是随机选择的。

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

#### 数据范围

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

对于 $100\%$ 的数据，保证 $1\le t\le 10$，$2\le n\le 300$，$1\le a_i\le 10^6$，$1\le b_i,c_i\le n$，$2\le n_{\min}\le n_{\max}\le 300$，$1\le a_{\max}\le 10^6$。


title: [PA2020] Elektrownie i fabryki

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 2 [Elektrownie i fabryki](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/ele/)**

为了应对不断上升的失业率，Byteotia 政府决定创造新的就业机会。为此将建设现代化的工厂，还要建设为工厂供电的新发电厂。

一条很长的高速公路穿过 Byteotia，沿途有 $n$ 个城市。为了简单起见，我们从 $1$ 到 $n$ 对城市进行编号。每两个相邻城市之间都相距一公里。

目前已经决定一些城市建设工厂，另一些城市建设发电厂。对于第 $i$ 个城市有一个值 $a_i$。如果它是正数，则在第 $i$ 个城市将建造一个发电容量为 $a_i$ 兆瓦的发电厂，如果它是负数，则在该城市将建造一个消耗电能 $a_i$ 兆瓦的工厂。如果 $a_i=0$，则说明该城市没有建设计划。

你的任务是设计一个电网，将电力从发电站输送到工厂。对于每一对相邻的城镇，你必须决定是否在它们之间建立一条输电线。如果这个城市被输电线直接或间接连接到某个有发电站的城市，电力就可以从发电站流向这个城市的工厂。如果每个工厂的电力需求都得到满足，那么电网的设计就是正确的。电网的成本与电网输电线的总长度（以公里计）成正比。

写一个程序计算设计一个正确的电网最小成本是多少。

inputFormat:
第一行一个整数 $n$，表示 Byteotia 的城市个数。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每个城市电力的生产和消耗。

outputFormat: 输出设计一个正确的电网的最小成本。如果不存在一个正确的电网，输出 $-1$。

hint:
#### 样例 1 解释

下面是一个包含 $n=17$ 个城市的样例，其中将建造三个工厂（白圈）和四个发电厂（黑圈）。$12$ 公里的正确电网用灰色部分标记。

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

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

#### 数据范围

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

对于一些子任务，满足 $n\le 5\times 10^3$。

对于 $100\%$ 的数据，保证 $1\le n\le 5\times 10^5$，$-10^9\le a_i\le 10^9$。


title: 「SvR-2」1+2=3（加强版）

description:
你有一些木棒，每个木棒左边有一个数，右边有一个数，数是 $[0,c)$ 的自然数，你要将所有木棒拼起来，使相邻的数和为 $c$ 的对数最大。

例如，$c=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$。

对于每组数据，第一行输入一个正整数 $c$，之后 $c$ 行，每行 $c$ 个整数，第 $i$ 行第 $j$ 个整数 $a_{i,j}$ 为 $(i-1)\text{ - }(j-1)$ 型木棒的个数。

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

hint:
对于 $100\%$ 数据，$\sum c^2\le5\times10^6$，$T\le10^5$，$1\le a_{i,j}\le10^9$，$3\le c\le10^3$。

**注：本题数据较弱，如有 hack 欢迎告知出题人。**


title: 梦境世界

background: 哆来咪爱旅行。

description:
有一个长为 $n$ 宽为 $m$ 的网格，其左上角编号为位置 $(1, 1)$ 而右下角编号为位置 $(n, m)$。哆来咪想要从左上角走到右下角，每次她可以往右或向下走一格，但不能超出 $n\times m$ 的网格边界。除此之外，有 $s$ 个禁止点是哆来咪无法走到的。

哆来咪有 $k$ 个神奇药水，喝药水可以撤销之前最后一次没有被撤销的行走操作，但移动序列并不会删去最后一个元素。当然，在 $(1, 1)$ 位置时不能使用药水，且 **药水不会撤销上一个药水的操作**。例如：从 $A$ 到 $B$ 后，在 $B$ 处喝了药水，则移动序列为 $A \to B \to A$；从 $A$ 走到 $B$ 再走到 $C$，连续喝下两次药水，移动序列为 $A \to B \to C \to B \to A$。

哆来咪认为一次 **旅行** 是指一次最终走到 $(n, m)$ 的行走路线。哆来咪想要求本质不同的 **旅行** 个数，答案对给定 $p$ 取模。哆来咪认为两次 **旅行** 不同，当且仅当两次旅行记录的移动序列不同。

inputFormat:
第一行五个整数 $n, m, k, p, s$，意义见题目描述。

接下来 $s$ 行，第 $i$ 行包含两个整数 $(x_i, y_i)$，表示不能经过网格中编号为 $(x_i, y_i)$ 的点。

outputFormat: 输出一行一个整数，表示答案对 $p$ 取模后的结果。

hint:
### 样例解释 1

七种路线如下：

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

### 数据规模与约定

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

- Subtask 0（10pts）：$1 \le n, m \le 100$，$k=0$。
- Subtask 1（15pts）：$1 \le n, m \le 10$，$k=1$。
- Subtask 2（15pts）：$n=1$，$m \le 100$，$k \le 100$。
- Subtask 3（25pts）：$1 \le n, m \le 100$，$k \le 10$。
- Subtask 4（35pts）：无特殊限制。

对于所有数据，保证 $1 \le n, m \le 100$，$0 \le k \le 100$，$2 \le p \le 10^9 + 9$，$0 \le s \le n \times m$，$1 \le x_i \le n$，$1 \le y_i \le m$，且 $(x_i, y_i)$ 互不相同。


title: 「RiOI-2」weight

background:
在小树林间坐落着一个幻想的城堡。这里是 E 国的领地，而小 E，则是 E 国之王。

树木，是 E 国抵挡袭击的法宝。树木越高，越能蒙蔽敌人的视线。

可是，随着自然条件的退化，小 E 却不知怎么处理。怎么办呢？

description:
给定一个 $n$ 行 $n$ 列 的矩阵 $a$。

有 $q$ 组询问，每次给定一个 $v$，请将矩阵每一行任意重排（可以不重排），最大化**最大值不小于** $v$（也就是说，至少有一个不小于 $v$ 的数）的列数。请输出这个列数。

询问之间相互独立。换言之，每次询问前可以重新排列。

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

第 $2\sim n+1$ 行，每行 $n$ 个正整数，表示矩阵 $a$。

接下来 $q$ 行每行一个正整数 $v$，表示一次询问。

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


title: 分解质因子 2

type: B

description:
给定一个正整数 $n$，设 $n = p_1 \times p_2 \times \dots p_k$，其中 $p_i$ 均为质数，对 $1 \leq i < k$，$p_i \leq p_{i + 1}$。

可以证明，序列 $p_i$ 是唯一的。

对每个给定的 $n$，请你求出 $p_1, p_2, \dots p_k$。

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

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

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

outputFormat: 对每组数据，输出一行若干个用空格隔开的整数，依次表示 $p_1, p_2, \dots p_k$。

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

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


title: 分解质因子 3

description:
给定一个正整数 $n$，设 $n = p_1 \times p_2 \times \dots p_k$，其中 $p_i$ 均为质数，对 $1 \leq i < k$，$p_i \leq p_{i + 1}$。

可以证明，序列 $p_i$ 是唯一的。

对每个给定的 $n$，请你求出 $p_1, p_2, \dots p_k$。

为了避免输出过大，请你输出 $p_1, p_2, \dots p_k$ 的**按位异或和**。

outputFormat: 对每组测试数据，输出一行一个整数，表示它所有质因子的按位异或和。

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

对于全部的测试点，保证 $1 \leq T \leq 10^6$，$2 \leq n \leq 10^8$。

### 提示

请注意大量数据读入输出对程序效率造成的影响，选择合适的 IO 方式，避免超时。


title: [CCC 2023 J1] Deliv-e-droid

description:
In the game, Deliv-e-droid, a robot droid has to deliver packages while avoiding obstacles.

At the end of the game, the final score is calculated based on the following point system:
- Gain $50$ points for every package delivered.
- Lose $10$ points for every collision with an obstacle.
- Earn a bonus $500$ points if the number of packages delivered is greater than the number of collisions with obstacles.

Your job is to determine the final score at the end of a game.

inputFormat: The input will consist of two lines. The first line will contain a non-negative integer $P$,representing the number of packages delivered. The second line will contain a non-negative integer $C$,representing the number of collisions with obstacles.

outputFormat: The output will consist of a single integer $F$,representing the final score.

translation:
机器人 Deliv-e-droid 在送快递，如果它成功地将一个快递送达，则它获得 $50$ 元钱，如果未能成功送达，它被扣除 $10$ 元钱。特别地，如果它送达的快递的数量大于未送达的，它会得到 $500$ 元钱的奖励。

现在已知 Deliv-e-droid 送达了 $P$ 个快递，未送达 $C$ 个（$0 \leq P,C \leq 100$），请实现一个程序，求出 Deliv-e-droid 所获得的钱（如果是倒扣的话用负数表示）。


title: [CCC 2023 J2] Chili Peppers

description:
Ron is cooking chili using an assortment of peppers.

The spiciness of a pepper is measured in Scolville Heat Units (SHU).Ron's chili is currently not spicy at all, but each time Ron adds a pepper, the total spiciness of the chili increases by the SHU value of that pepper.
The SHU values of the peppers available to Ron are shown in the following table:

| Pepper Name | Scolville Heat Units |
| :----------: | :----------: |
| Poblano | $1500$ |
| Mirasol | $6000$ |
| Serrano | $15500$ |
| Cayenne | $40000$ |
| Thai | $75000$ |
| Habanero | $125000$ |

Your job is to determine the total spiciness of Ron's chili after he has finished adding peppers.

inputFormat: The first line of input will contain a positive integer $N$, representing the number of peppers Ron adds to his chili. The next $N$ lines will each contain the name of a pepper Ron has added. Each pepper name will exactly match a name that appears in the table above. Note that more than one pepper of the same name can be added.

outputFormat: The output will consist of a positive integer $T$, representing the total spiciness of Ron's chili.

translation:
Ron 在尝试使用一些辣椒做一份黑暗料理，每一个辣椒都有其自己特别的辣度，如下表：

| 辣椒名 | 辣度 |
| -----------: | -----------: |
| Poblano | $1500$ |
| Mirasol | $6000$ |
| Serrano | $15500$ |
| Cayenne | $40000$ |
| Thai | $75000$ |
| Habanero | $125000$ |

一份黑暗料理的辣度是根据所有辣椒辣度的总和决定的。

现在请你实现一个程序，输入的第一行为 $n$（$1 \leq n \leq 10$），表示一共放了 $n$ 个辣椒，接下来 $n$ 行，一行一个字符串 $s_i$，表示放入辣椒的名称。现在请你求出那份黑暗料理的辣度。


title: [CCC 2023 J3] Special Event

description:
You are trying to schedule a special event on one of five possible days.

Your job is to determine on which day you should schedule the event, so that the largest number of interested people are able to attend.

inputFormat:
The first line of input will contain a positive integer $N$, representing the number of people interested in attending your event. The next $N$ lines will each contain one person's availability using one character for each of Day 1, Day 2, Day 3, Day 4, and Day 5(in that order).

The character `Y` means the person is able to attend and a period (`.`) means the person is
not able to attend.

The following table shows how the available 15 marks are distributed:
| Marks | Description |
| :----------: | :----------: |
| 6 | There will be exactly one day on which every person will be able to attend. |
| 6 | There will be exactly one day on which the largest number of people will be able to attend. |
| 3 | There might be more than one day on which the largest number of people will be able to attend. |

outputFormat:
The output will consist of one line listing the day number(s) on which the largest number of
interested people are able to attend.

If there is more than one day on which the largest number of people are able to attend,output all of these day numbers in increasing order and separated by commas (without spaces).

translation:
你的公司需要开一场会议，一共有 $5$ 天可以开会。这个公司有 $N$ 位员工，每个员工的日程安排都不同，你作为一个公司的董事长，想要听取更多员工的意见，你需要知道哪几天能来开会的员工最多，你准备在这几天中选一天开会。

你需要实现一个程序，第一行输入一个 $N$（$1\leq N \leq 20$），表示有 $N$ 个员工，然后 $N$ 行，每行 $5$ 个字符，`Y` 表示该员工那天能来，`.` 表示不能，现在请你求出哪几天能来开会的员工最多，如果有多天，请以一个 `,` 间隔。

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

- Subtask $1$（$6$ points）：有且只有一天全部人都可以开会。
- Subtask $2$（$6$ points）：有且只有一天开会人数最多。
- Subtask $3$（$3$ points）：有可能有多天满足条件。


title: [CCC 2023 J4/S1] Trianglane

description:
Bocchi the Builder just finished constructing her latest project: a laneway consisting of two rows of white equilateral triangular tiles. However, at the last moment, disaster struck! She accidentally spilled black paint on some of the tiles. Now, some of the tiles are wet and the other tiles are dry. Bocchi must place warning tape around the perimeters of all wet areas. Can you help her determine how many metres of tape she needs?

The first triangular tile will point upwards. Each pair of adjacent tiles (that is, tiles that share a common side) will point in opposite directions. Each tile has a side length of $1$ metre.

inputFormat:
The first line of input will consist of one positive integer $C$, representing the number of columns.

The next two lines will each consist of $C$ integers separated by spaces. Each integer represents
the colour of a tile along the laneway, with `1` indicating that the tile is black (wet) and `0` indicating that the tile is white (dry).

The following table shows how the available 15 marks are distributed:

| Marks | Description | Bound |
| :----------: | :---------- | :----------: |
| 3 | The laneway is not very long, black tiles are never adjacent and the second row is fully white. | $C \le 2 \times 10^3$ |
| 3 | The laneway is not very long, black tiles may be adjacent and the second row is fully white. | $C \le 2 \times 10^3$ |
| 5 | The laneway is not very long, black tiles may be adjacent and may appear in the second row. | $C \le 2 \times 10^3$ |
| 4 | The laneway may be very long, black tiles may be adjacent and may appear in the second row. | $C \le 2 \times 10^5$ |

outputFormat: Output a single integer representing the length of tape Bocchi needs,in metres.

translation:
设计师 Bocchi 刚刚完成一个工程：一个由上下两部分组成的巷道，每一部分都由一排边长为 $1$ 米的三角形构成。不过这项工程还有一点小瑕疵：有一部分三角形被涂成了黑色，它们的油漆还没干，所以暂时不能使用。Bocchi 想用警戒线将这部分三角形围住，请问至少需要几米长的警戒线才能围上。

一个图形由上下均由 $C$ 个三角形构成。

你需要实现一个程序：

输入一个整数 $C$（$1 \leq C \leq 2 \times 10^5$），接下来两行，每行 $C$ 个数字，`1` 表示黑色三角形，`0` 表示白色三角形，请你求出围上黑色三角形需要多少米栅栏。

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

- Subtask $1$（$3$ points）：$C \leq 2 \times 10^3$，黑色三角形不相邻，第二行全部为白色三角形。
- Subtask $2$（$3$ points）：$C \leq 2 \times 10^3$，黑色三角形可能相邻，第二行全部为白色三角形。
- Subtask $3$（$5$ points）：$C \leq 2 \times 10^3$，黑色三角形可能相邻，第二行可能有黑色三角形。
- Subtask $4$（$4$ points）：$C \leq 2 \times 10^5$，黑色三角形可能相邻，第二行可能有黑色三角形。

样例 $1$ 图解：

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

样例 $2$ 图解：

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


title: [CCC 2023 J5] CCC Word Hunt

description:
In the CCC Word Hunt, words are hidden in a grid of letters. The letters of a hidden word always appear in order on horizontal, vertical, or diagonal line segments in one of two ways.One way is for the letters of a word to appear on one line segment. The other way is for the letters of a word to appear on one line segment up to some letter and then on a second line segment that forms a right angle at this letter.

Given a grid of letters and a single word to search for, your job is to determine the number of times that particular word is hidden in the grid.

inputFormat:
The first line of input will contain a string of distinct uppercase letters $W$,representing the word you are to search for in the grid. The length of $W$ will be at least two. The second line of input will be an integer $R(1 \le R \le 100)$, where $R$ is the number of rows in the grid.The third line of input will be an integer $C(1 \le C \le 100)$, where $C$ is the number of columns in the grid.

The remaining input will provide the letters in the grid. It will consist of $R$ lines, where each line contains $C$ uppercase letters separated by single spaces.

outputFormat:
The following table shows how the available 15 marks are distributed:

| Marks | Word Placement |
| :----------: | :---------- |
| $2$ | On one horizontal line segment |
| $2$ | On one horizontal or vertical line segment |
| $2$ | On one horizontal, vertical, or diagonal line segment |
| $9$ | On one line segment or two perpendicular line segments |

The output will consist of a single non-negative integer $H$, representing the number of times the word is hidden in the grid.

translation:
在 CCC Word Hunt 这款游戏中，它的每一关都会给你一个目标字符串 $W$（$2 \leq |W| \leq R + C - 1$），然后你需要在一个 $R \times C$（$1 \leq R,C \leq 100$）的矩阵中寻找这个字符串，而且找到目标字符串的方法有且仅有 $2$ 种，分别为：

- 这个隐藏字符串按水平、垂直或对角斜线排成了一条直线。

- 这个隐藏字符串先进行一段，然后转 $90$ 度再进行一段。

请计算出该 $R \times C$ 的矩阵中一共包含几个隐藏字符串。

samples:
MENU
5
7
F T R U B L K
P M N A X C U
A E R C N E O
M N E U A R M
M U N E M N S

samples:
NATURE
6
9
N A T S F E G Q N
S A I B M R H F A
C F T J C U C L T
K B H U P T A N U
D P R R R J D I R
I E E K M E G B E

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

- Subtask $1$（$2$ points）：隐藏字符串一定在一条水平线段上。
- Subtask $2$（$2$ points）：隐藏字符串一定在一个水平或垂直线段上。
- Subtask $3$（$2$ points）：隐藏字符串一定在一个水平、垂直或对角线线段上。
- Subtask $4$（$9$ points）：隐藏字符串一定在一个线段或两个互相垂直的线段上。

样例 $1$ 图解：

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

样例 $2$ 图解：

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


title: 组合数问题

description:
给出 $T$ 次询问，每次给出 $n,m$，请求出 $\binom{n}{m}$ 对 $998,244,353$ 取模的结果。

其中 $\binom{n}{m}$ 为二项式系数，它的另一种写法是 $C_n^m$。

inputFormat:
输入的第一行是两个整数，分别表示询问的次数 $T$ 和所给出 $n$ 的最大值 $N$。
接下来 $T$ 行，每行两个整数，依次表示给出的 $n$ 和 $m$。

outputFormat: 为了避免输出过大，请你输出一行一个整数，表示所有询问的结果的**按位异或和**。

hint:
### 样例 1 解释

三组询问的答案依次是 $1, 6, 10$。

### 数据规模与约定

对 $100\%$ 的数据，保证 $1 \leq T \leq 5 \times 10^6$，$0 \leq m \leq n \leq N \leq 5 \times 10^6$。

### 提示

请注意大量的数据读入对程序效率造成的影响，选择合适的读入方式，避免超时。


title: ZHY 的矩阵

background: 温馨提示：本题不允许套取数据。

description:
ZHY 的记忆中有一个 $k$ 行 $n$ 列的 01 矩阵 $A$，满足下列条件：

- 每一列都至多有一个 $1$。
- 每行相邻的两个 $1$ 所在的两列夹出的 $k$ 行的矩形（包括这两列）内至少有三个 $1$。

突然，ZHY 想起来了矩阵中 $x$ 个位置的值。请你计算有多少种填充 $A$ 的剩余位置的方案，使得 $A$ 满足条件。

----

形式化的讲，设 $A$ 第 $i$ 行第 $j$ 列的数为 $A_{i,j}$，则 $A$ 满足下列条件：

- 对于 $\forall i \in [1,k],\kern{2pt}j \in [1,n]$，$A_{i,j} \in \{0,1\}$。

- 对于 $\forall i \in [1,n]$，$\displaystyle\sum_{j=1}^{k} A_{j,i}\le 1$。

- 对于 $\forall i,j \in [1,n],\kern{2pt}p \in [1,k]$ 且 $j>i$，若有 $A_{p,i}=A_{p,j}=1,\displaystyle \sum_{x=i}^{j}A_{p,x}=2$，则有 $\Big(\displaystyle \sum_{x=1}^{k} \sum_{y=i}^{j} A_{x,y}\Big) \ge 3$。

- 对于 $\forall i\in[1,x]$，有 $A_{a_{i},b_{i}}=c_{i}$。

由于答案可能很大，你只需告诉 ZHY 答案对 $10^{9}+7$ 取模的结果。定义两个矩阵 $A,A'$ 不同，当且仅当存在 $i\in[1,k]$，$j\in[1,n]$ 满足 $A_{i,j}\ne A'_{i,j}$。

inputFormat:
第一行三个整数，表示 $n,k,x$。

接下来 $x$ 行，每行三个整数 $a_{i},b_{i},c_{i}$。

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


title: [PA2020] Zabawki

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 2 [Zabawki](https://sio2.mimuw.edu.pl/c/pa-2020-1/zab/)**

你可能不知道，Bitie 和 Bytie 兄弟有相当令人印象深刻的玩具收藏品！他们每个人都拥有 $n$ 个玩具，每个玩具都是 $26$ 种类型中的一种。为方便起见，兄弟俩给每种类型的玩具都贴上了从 $\texttt a$ 到 $\texttt z$ 的英文字母标签。

在今天的游戏中，Bitie 拿出了他的玩具并按从左到右的顺序排列。因此，Bitie 可以用一个有 $n$ 个英文字母的序列来描述他的玩具的排列；这个序列的第 $i$ 个字符表示 Bitie 的序列中从左起的第 $i$ 个玩具。同时 Bytie 也拿出了他的玩具并按从左到右的顺序排列。现在 Bitie 想变得更像 Bytie——他想把自己的玩具按 Bytie 的玩具的顺序排列。

在游戏过程中，Bitie 可以通过翻转来改变他的玩具的顺序，一次翻转可以取奇数个连续的玩具并颠倒其顺序。因此，如果字符串 $\texttt{abcdea}$ 描述了 Bitie 的玩具顺序，那么在一次翻转中，Bitie 可以产生例如 $\texttt{adcbea}$（通过颠倒从第二个到第四个玩具的顺序）或 $\texttt{edcbaa}$（通过颠倒从第一个到第五个玩具的顺序）的序列。然而，他不能在一次翻转之后得到序列 $\texttt{bacdea}$。

Bitie 能够通过翻转得到和 Bytie 的玩具序列一样的序列吗？

inputFormat:
第一行一个整数 $n$，表示两人拥有的玩具数量。

第二行一个长度为 $n$ 的字符串，表示 Bitie 的玩具序列。

第三行一个长度为 $n$ 的字符串，表示 Bytie 的玩具序列。

outputFormat: 如果 Bitie 可以通过翻转得到和 Bytie 一样的玩具序列，输出 `TAK`，否则输出 `NIE`。

hint:
#### 样例 1 解释

对于第一组样例，Bitie 可以通过三次翻转操作得到和 Bytie 一样的玩具序列。

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

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

#### 数据范围

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

对于一些子任务，满足如果这组数据的答案是 `TAK`，那么 Bitie 最多只需进行一次交换就可以得到和 Bytie 一样的序列。

此外，大约一半的子任务满足 $n\le 2\times 10^3$。

对于 $100\%$ 的数据：

- 保证 $1\le n\le 3\times 10^5$。
- 保证字符串中只出现小写英文字母（$\texttt a$ 到 $\texttt z$）。


title: [PA2020] Ogromne drzewo

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 3 [Ogromne drzewo](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/ogr/)**

Byteasar 为他的女朋友 Algolina 买了一棵巨大的圣诞树。这是一份十分不寻常的礼物，但 Byteasar 是一位算法师，Algolina 已经习惯了这种惊喜。

正如你所猜到的，这棵树不是植物，而是一个无环连通图。它非常大，但可以用一种有组织的方式来描述。它的节点有 $n$ 层。第一层只包含一个节点，表示树的根。每个节点的子节点都只在其下一层，最后一层的节点除外，它们是叶子。对于区间 $[1, n - 1]$ 中的每一个 $i$，第 $i$ 层的每个节点都有 $a_i$ 个子节点。

Algolina 想让 Byteasar 知道她对他的礼物有多满意，因此决定和他玩一个游戏。Algolina 选择了树上的某个节点 $A$，Byteasar 选择了节点 $B$（可能与 Algolina 相同）。现在从 Algolina 开始，他们俩将轮流重新对树的节点涂色——Algolina 用红色，Byteasar 用蓝色。在游戏开始时，所有节点都是白色的。每个节点将恰好被重新涂色一次——由 Algolina 或由 Byteasar 涂色。在任何时候，涂色的人都可以用自己使用的颜色对任何白色节点涂色，包括节点 $A$ 和 $B$。

一旦所有顶点都被重新涂色了，这两人将计算出他们的分数。Algolina 获得的分数（用 $S_A$ 表示）将是所有红色节点到节点 $A$ 的距离之和，而 Byteasar 获得的分数（用 $S_B$ 表示）将是所有蓝色节点到节点 $B$ 的距离之和。我们所说的两个节点之间的距离，是指它们之间最短路径上的边的数量。Algolina 的目标是得分以最大可能比 Byteasar 的大，即最大化 $S_A-S_B$ 的值，而 Byteasar 的目标是最小化它。

Byteasar 很快指出，这是一个完全信息有限游戏，假设他们都以最优策略进行游戏，就可以计算出最终得分的差值有多大。他希望你能帮他计算出这个值。由于这个值可能非常大，你需要计算它对 $10^9+7$ 取模后的值。

此外，由于在一次比赛后忘记礼物是不愉快的，你需要计算多次选择节点 $A$ 和 $B$ 的情况下两人最终得分之差。

inputFormat:
第一行两个整数 $n,q$，分别表示树的层数和询问次数。

第二行 $n-1$ 个整数 $a_1,a_2,\cdots,a_{n-1}$，意义如题目描述。

接下来 $q$ 行，每行描述 $A,B$。可以发现最终结果只取决于节点 $A,B$ 和它们的最近公共祖先都在哪一层，因此每行给出三个整数 $W_A,W_B,W_{\operatorname{lca}(A,B)}$。

outputFormat: 输出 $q$ 行，第 $i$ 行包含对第 $i$ 个询问的回答，对 $10^9+7$ 取模。

hint:
#### 样例 1 解释

样例中的树有三层，第一层一个节点，第二层三个节点，第三层六个节点。

对于第二个询问，Algolina 和 Byteasar 都选择了根节点。对于最优决策，他们应该按照非递增的层数顺序选择顶点，最后的结果是 $(2 + 2 + 2 + 1 + 1) - (2 + 2 + 2 + 1 + 0) = 1$。

对于第三个询问，答案是 $-4$，但你应该输出 $-4\bmod (10^9+7)=10^9+3$。

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

#### 数据范围

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

- 对于一些子任务，满足树最多有 $3\times 10^5$ 个节点，且 $q\le 100$；
- 对于另一些子任务，满足 $q\le 100$。

对于上述每种情况，至少有一个这样的子任务。

对于 $100\%$ 的数据，保证 $2\le n\le 3\times 10^5$，$1\le q\le 3\times 10^5$，$2\le a_i\le 3\times 10^5$，$1\le W_{\operatorname{lca}(A,B)}\le W_A,W_B\le n$。


title: [PA2020] Miny

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 3 [Miny](https://sio2.mimuw.edu.pl/c/pa-2020-1/min/)**

$n$ 枚地雷被运到 Bytau 的军事训练场，并沿一条直线埋设。每个地雷位于不同的地方，并且有自己的爆炸半径。当引爆时，地雷会自动引爆其爆炸半径内所有尚未爆炸的地雷。如果地雷 $a$ 和地雷 $b$ 之间的距离不超过地雷 $b$ 的爆炸半径，则我们称地雷 $a$ 在地雷 $b$ 的爆炸半径内。

Bytomir 中士想进行一项实验。他选择了一个任意的地雷子集（也许是空的），并让这个地雷子集内的所有地雷在同时手动引爆。实验的结果是一组已经爆炸的地雷——要么是手动引爆的引起的爆炸，要么是其他地雷爆炸导致的爆炸。

Bytomir 能得到多少种可能的实验结果？如果两个实验结果中爆炸的地雷相同，则这两个实验结果是相同的。由于结果可能很大，请输出它除以 $10^9+7$ 的余数。

inputFormat:
输入第一行包含一个整数 $n$，表示地雷个数。

接下来 $n$ 行，每行两个整数 $a_i,r_i$，分别表示地雷的位置和爆炸半径。你可以假设 $a_1<a_2<\cdots<a_n$。

outputFormat: 输出可能的实验结果总数对 $10^9+7$ 取模后的值。

hint:
#### 样例 1 解释

你可以得到 $7$ 种可能的实验结果：

- $\{\}$（空集）：如果不引爆任何地雷；
- $\{1,2\}$（地雷 $1,2$）：如果我们只引爆地雷 $1$；
- $\{1,2,3\}$：如果我们引爆地雷 $1$ 和 $3$；
- $\{1,2,3,4\}$：如果我们引爆地雷 $1$ 和 $4$；
- $\{2\}$：如果我们只引爆地雷 $2$；
- $\{2,3\}$：如果我们只引爆地雷 $3$；
- $\{2,3,4\}$：如果我们只引爆地雷 $4$；

请注意，可以通过不同的方式得到同一个实验结果——例如，如果我们引爆地雷 $1$ 和 $2$，也会得到 $\{1, 2\}$ 的结果。

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

#### 数据范围

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

对于 $100\%$ 的数据，保证 $1\le n\le 3\times 10^5$，$0\le a_i,r_i\le 10^{18}$。


title: [PA2020] Samochody dostawcze

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 3 [Samochody dostawcze](https://sio2.mimuw.edu.pl/c/pa-2020-1/sam/)**

Byteasar 是一家向商店运送物资的公司的后勤人员。在他公司所在的城市里，道路网由横向的街（从西到东）和纵向的道（从南到北）组成。每一对相邻的街和相邻的道都相距一公里。我们把街按从南到北的顺序编号，把道按从西到东的顺序编号。我们将第 $i$ 条道和第 $j$ 条街的交叉点记为 $(i,j)$。你可以假设，对于任何一个整数，都存在一条街的编号为 $j$ 和一条道的编号为 $i$。

Byteasar 明天安排了 $n$ 次送货；第 $i$ 次送货将由一辆货车在时刻 $t_i$ 离开车库，以每时间单位一公里的恒定速度沿街或道行驶。每次送货可以是两种类型中的一种：对于送货类型一，车库在路口 $(w_i,0)$，货车沿道 $w_i$ 向北行驶；对于送货类型二，车库在路口 $(0,w_i)$，货车沿街 $w_i$ 向东行驶。根据计划，每个车库在任何时刻最多只有一辆车离开。

货车不必停下来——驶过收货地点时，司机只需放下要送的包裹。然而，有一个问题，如果两辆货车发现他们同一时刻在同一个十字路口，就很可能会发生碰撞。Byteasar 非常希望避免这种情况。不幸的是，他唯一能做的就是取消一些送货计划。因此，他希望取消尽可能少的送货计划，以便剩下的车中没有任何两辆车同一时刻在同一个十字路口。

inputFormat:
第一行一个整数 $n$，表示送货计划个数。

接下来 $n$ 行，每行三个整数 $r_i,w_i,t_i$，分别表示类型，车库位置和出发时间。

outputFormat: 输出一个整数，表示最少取消的送货计划数。

hint:
#### 样例 1 解释

如果四份货物都送出，则第一和第二辆车会在时刻 $5$，在路口 $(5,3)$ 相撞。如果取消第一个送货计划，则第二和第四辆车会在时刻 $7$，在路口 $(7,3)$ 相撞。如果取消第二个送货计划，那么所有车都不会相撞了。

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

#### 数据范围

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

对于 $100\%$ 的数据，保证 $1\le n\le 5\times 10^5$，$r_i\in \{1,2\}$，$1\le w_i\le 10^6$，$0\le t_i\le 10^6$。


title: Happybob's Game (UBC001D)

description:
**注：本题中所有 $i,j$ 均默认 $1\le i,j\le n$ 且 $i\not = j$。**

Happybob 的游戏角色正在进行战争。

他有 $n$ 个部队，每个部队有 $a_i$ 个人，并且有消耗值 $m_i$，表示每过 $1$ 分钟第 $i$ 个部队的人会变成 $⌊\frac{a_i}{m_i}⌋$，一旦其中一支部队人数变成 $0$，Happybob 就失败了。设一开始为第 $0$ 分钟，定义存活时间为 Happybob 的其中一支部队人数变成 $0$ 的上一分钟。**可参考样例解释。**

但是 Happybob 不甘就这样就被消灭，他想到了好办法：他可以在**任意不是整数分钟**的时间将一个部队的人调一部分到另一个部队。形式化来说，取两支军队 $a_i, a_j$ 以及一个调换人数 $x$ 满足 $1\le x\le a_i$，使 $a_i,a_j$ 分别变成 $a_i-x,a_j+x$。注意，在两个整数分钟间，他可以调换任意多次。

Happybob 发现，这样可以有效地提升部队存活时间。现在你作为 Happybob 最信任的参谋长，你可以帮他调兵遣将。

接下来给你 $q$ 次操作，每次操作是以下操作中的一个：

- 操作 $1$，形如 `1 i x`，表示 Happybob 的第 $i$ 支部队的人数 $a_i$ 变成了 $x$ （$1\le x\le 10^9$）。
- 操作 $2$，形如 `2 i x`，表示 Happybob 的第 $i$ 支部队的消耗值 $m_i$ 变成了 $x$（$1\le x\le 10^6$）。
- 操作 $3$，形如 `3`，表示让你输出 Happybob 理论上通过上述调兵遣将法最久的存活时间。注意，此操作**不会**改变 $a_i$ 或 $m_i$ 的值。

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

接下来两行，每行 $n$ 个正整数，分别表示 $a$ 数组与 $m$ 数组。

接下来 $q$ 行，每行都是上述三种操作之一。

outputFormat: 假设共有 $opt$ 次操作 $3$，那么你的答案应该有 $opt$ 行，每行表示当前状态下 Happybob 的最长可能存活时间。如果 Happybob 的军队可以无限地活下去，输出 `-1`。


title: 「TAOI-1」Apollo

background:
Execution.

这题原来叫 `std::cout << std::fixed << std::setprecision(1) << 6.5 << '\n';`。

[被当事人删掉的图片.jpg]

**【Upd 2023/04/15 21:42】添加了一组 Hack 数据位于 Subtask 2，#13。现在所有赛时的 $\bm{50}$ 分提交理论上均只能获得 $\bm{30}$ 分。**

description:
给出 $n$ 个十进制小数 $a_1 \dots a_n$。

对于一个 **数** $a$，定义其精度 $f(a)$ 表示最小的非负整数 $k$ 使得 $10^k\times a$ 为整数；对于整数 $a$，定义 $f(a) = 0$。对于两个十进制小数 $a, b$，定义 $g(a, b)$ 为对于所有 **数** $c \in [\min(a,b), \max(a,b)]$ 的 $f(c)$ 的最小值。

对于所有 $1 \leq i \leq n$，你需要求出 $\sum\limits_{j=1}^ng(a_i, a_j)$ 的值并输出。

定义十进制小数是一个含有整数部分和小数部分的数，其小数部分不为 $0$。之所以描述得这么愚蠢是因为保证输入的每个数都有小数点，但是好像无论什么写法都会有人提出不满，真是抱歉了。~~所以还是得看看被当事人删掉的图片。所以我在这里写闲话有人看得到吗。~~

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

接下来 $n$ 行，每行一个十进制小数 $a_i$。

outputFormat: $n$ 行，每行一个整数，分别表示 $i = 1 \dots n$ 对应的答案。

hint:
### 数据范围

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

令 $\sum\limits_{i=1}^n f(a_i) = t$。

- Subtask 1（15 points）：$a_i \leq 10$，$n \leq 5$，$t \leq 10$。
- Subtask 2（15 points）：$a_i \leq 10$，$n \leq 100$，$t \leq 1000$。
- Subtask 3（20 points）：$n \leq 1722$。
- Subtask 4（15 points）：$a_i \leq 1$。
- Subtask 5（35 points）：无特殊限制。

对于所有数据，$0 \lt a_i \lt 10^9$，$1 \leq n \leq 10^5$，$1 \leq t \leq 3 \times 10^6$，**保证 $\bm{a_i}$ 没有后导 [$\color{black}\bm 0$](https://cdn.luogu.com.cn/upload/image_hosting/pg66fm1z.png)，不保证 $\bm{a_i}$ 互不相同**。

### 样例解释

以 $i = 1$ 为例：

+ $j = 1$：取 $c = 11.4514$，$f(c) = 4$；
+ $j = 2$：取 $c = 11.46$，$f(c) = 2$；
+ $j = 3$：取 $c = 11.2$，$f(c) = 1$；
+ $j = 4$：取 $c = 11.3$，$f(c) = 1$；
+ $j = 5$：取 $c = 11.47$，$f(c) = 2$。

故 $\sum\limits_{j=1}^n g(a_1, a_j) = 4 + 2 + 1 + 1 + 2 = 10$。对于同一个 $j$，上文给出的所有 $c$，都可能有其它的不同的 $c$ 满足 $f(c)$ 同样最小。


title: [PA2020] Tekstówka

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 4 [Tekstówka](https://sio2.mimuw.edu.pl/c/pa-2020-1/tek/)**

在去年我们在某社交网络的粉丝页上进行的 PA 中，参与者大声地问我们：「题呢？」。今年，我们决定满足您的期望。

给出了由英文小写字母组成的字符串 $s$ 和 $t$。令 $s_{i,j}\ (1\le i\le j\le |s|)$ 表示由 $s$ 的第 $i$ 个到第 $j$ 个（包含两端）字符依次组成的子串。我们也同样定义 $t_{i,j}$。

你的任务是处理 $q$ 次查询。每次查询用四个整数 $i,j,k,l$ 表示，这里 $1\le i\le j\le |s|,1\le k\le l\le |t|$。对于每次查询，你需要输出子串 $s_{i,j}$ 和子串 $t_{k,l}$ 的最长公共子序列。

注：一个字符串的子序列是指一个字符串通过删除一些（可能不删除）字符且不改变剩余字符顺序得到的串。例如，$\texttt{potyczki}$ 的子串可以是 $\texttt{tyki}$ 或 $\texttt{pi}$，但不能是 $\texttt{koty}$。

我们称字符串 $a$ 和 $b$ 的公共子序列为既是 $a$ 的子序列，又是 $b$ 的子序列的子序列。

我们称字符串 $a$ 和 $b$ 的最长公共子序列为 $a$ 和 $b$ 的子序列中最长的一个。

inputFormat:
输入第一行包含三个整数 $n,m,q$，分别表示 $s$ 串和 $t$ 串的长度与询问次数。

第二行包含一个由小写英文字母组成且长为 $n$ 的字符串 $s$。

第三行包含一个由小写英文字母组成且长为 $m$ 的字符串 $t$。

接下来 $q$ 行，每行四个整数 $i,j,k,l$，意义如题目描述。

outputFormat: 输出 $q$ 行，每行一个整数，表示对询问的回答。

hint:
#### 数据范围

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

- 对于一些子任务，满足 $n,m,q\le 600$；
- 对于一些其他的子任务，满足 $n,m\le 600$；
- 对于一些其他的子任务，满足 $q\le 5\times 10^3$。

对于上述情况，至少有一个子任务满足。

对于 $100\%$ 的数据，保证 $1\le n,m\le 3\times 10^3$，$1\le q\le 10^5$，$1\le i\le j\le n$，$1\le k\le l\le m$。


title: [PA2020] Malowanie płotu

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 4 [Malowanie płotu](https://sio2.mimuw.edu.pl/c/pa-2020-1/mal/)**

今年的秋季天气已经完全破坏了 Potyczek 先生的围栏上的漆。围栏需要尽快用特殊的蓝色防水剂进行处理，以免即将到来的冬季对其造成不可弥补的破坏。Potyczek 先生请他邻居的勤劳儿子 Bytie 来做这件事。这个男孩今天早上完成了任务，但做得相当粗心，因为他急着参加下一轮 PA。

Potyczek 先生的围栏由 $n$ 根木条组成，每根木条分为长度相等的 $m$ 段。Bytie 只把每根木条从上到下用防水剂涂了一遍，不幸的是，这可能还不足以把栅栏全部涂满。然而，在每根木条上涂防水剂的段都是连续的，每个段要么完全涂上，要么根本不涂。进一步看来，男孩所涂的那部分栅栏是一致的，即每两个连续的木条上所涂的段都存在一个非空的相交区间。

例如，涂完的围栏可能如下图所示。

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

由于以下三个原因，下图所示情况是不可能的。

- 编号为 $1$ 的木条根本没涂防水剂。
- 编号为 $3$ 的木条一致的段没有涂防水剂。
- 编号 $5,6$ 的木条涂防水剂的部分相交区间为空。

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

编写一个程序，计算 Bytie 按照上述规则可以用多少种不同的方式来涂围栏。如果有一段围栏在其中一种方式中被涂上了颜色，而在另一种方式中没有被涂上颜色，那么就称这两种方式是不同的。方法的数量可能相当多，所以只要输出它除以质数 $p$ 的余数就可以了。

inputFormat: 输入一行三个整数 $n,m,p$。分别表示木条个数，每根木条上段的个数和质数 $p$。

outputFormat: 输出一个整数表示 Bytie 按照上述规则给围栏涂色的方案数对 $p$ 取模后的值。

hint:
#### 数据范围

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

对于 $100\%$ 的数据，保证 $1\le n\times m\le 10^7$，$10^8\le p\le 10^9$，$p\in \mathbb{P}$。


title: [PA2020] Wycieczka górska

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 4 [Wycieczka górska](https://sio2.mimuw.edu.pl/c/pa-2020-1/wyc/)**

一群 $k$ 个旅行者朋友去了 Byte 山。在最后一天，他们决定组织一场登山比赛，从他们所住的旅店到 Byte 山顶。

每个旅行者都有一张区域地图，它是一个分为 $n$ 行 $m$ 列的矩形；因此地图一共包含 $n\cdot m$ 个区域。旅店位于地图左上角的区域，而山顶则位于地图右下角的区域。Byte 山以其非常均匀而闻名——对于地图上的任何区域，在地图上与之相邻的右面或下面的区域海拔较高，而相邻的左边或上面区域海拔较低。但是，这座山也因潜伏着许多危险地区而闻名。有些地区在地图上标明是非常危险的，因为那里有野生动物居住——所以最好不要到那里去……

你是 Byte 山山脚下的一个小屋的看守人。通过观察每一个旅行者，你已经为他们每个人分配了两个参数 $a_i$ 和 $b_i$，这些参数决定了他们在山坡上的运动速度。具体来说，如果第 $i$ 个旅行者向更高的区域移动，那么他需要 $a_i$ 分钟，如果旅行者向更低的区域移动，则需要 $b_i$ 分钟。你也知道，每个旅行者都会走对他们来说从小屋到山顶最快的路线，并且路线完全在地形图上，而且避开了所有的危险区域。

你想知道最快的人需要多长时间才能到达山顶，有多少人将与最快的人同时爬到山顶。你可以假设，从小屋到山顶至少有一条安全的路线。

inputFormat:
第一行三个整数 $n,m,k$，分别表示地图的大小和旅行者的数量。

接下来 $n$ 行包含对地图的描述，每行由一个包含 $m$ 个字符的字符串组成，字符串中只包含 $\texttt{.}$（点）和 $\texttt X$，表示每个区域：

- $\texttt .$ 表示这是一个安全区域。
- $\texttt X$ 表示这个区域有野生动物定居，是危险的。

接下来 $k$ 行描述每个旅行者。每行包含两个整数 $a_i,b_i$，分别表示第 $i$ 个旅行者向更高或更低区域移动所要花费的时间。

旅店位于地图的左上角，在地图的第一行第一列。山顶在地图的右下角，在地图的第 $n$ 行第 $m$ 列。你可以假设包含旅店和山顶的区域是安全的，而且这些区域之间至少有一条只由安全区域组成的路径。

outputFormat: 输出一行两个整数，分别表示最先到达山顶的旅行者的用时和用时等于最小用时的旅行者的数量。

hint:
#### 样例 2 解释

从旅店到山顶只有一条路径，这些旅行者的用时分别是 $13,14,13,13$。

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

#### 数据范围

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

对于一些子任务满足 $k=1$。

对于 $100\%$ 的数据，保证 $2\le n,m\le 2\times 10^3$，$1\le k\le 10^6$，$1\le a_i,b_i\le 10^9$。