title: [语言月赛 202405] 交题解

description:
小 S 想要在 Luogu 上提交一篇非常美妙的题解，但是小 Q 不希望看到小 S 的题解比自己的点赞更多，于是她故意在小 S 的题解中加入了一些奇怪的字符。

具体来说，原本的题解可以看作一个只包含**小写或大写字母**的字符串 $S$，而小 Q 在其中若干位置插入了一些随机字符，这些字符可能是数字或标点符号，但一定**不是字母**，且一定在**键盘**上出现。我们称被添加字符后的字符串为 $S'$。

你的任务是，将 $S'$ 中**非大小写字母**的字符全部去除，然后将得到的字符串输出。

inputFormat: 输入仅一行，一个字符串 $S'$，表示被添加字符后的字符串。

outputFormat: 输出仅一行，一个字符串 $S$，表示原字符串。

hint:
### 样例 1 解释

在字符串 `I*Love*Luogu**333#$$` 中，字符 `*`，`#`，`$` 属于标点符号，字符 `3` 属于数字，这些都是后添加的字符。删除后，字符串变为 `ILoveLuogu`。

### 样例 2 解释

在字符串 `L2u4o6gu##$%Lov()es^me` 中，字符 `#`，`$`，`%`，`(`，`)`，`^`，\` 属于标点符号，字符 `2`，`4`，`6` 属于数字，这些都是后添加的字符。删除后，字符串变为 `LuoguLovesme`。

### 数据范围

对于前 $30 \%$ 的数据，保证 $S'$ 中只包含拉丁字母。
对于另 $30 \%$ 的数据，保证 $S'$ 中只包含拉丁字母和下划线 `_`。
对于 $100 \%$ 的数据，保证 $S'$ 的长度在 $1$ 到 $10^6$ 之间, $S'$ 中只出现**键盘上主键盘区中的字母、标点符号、数字**，不含空格、换行符等结束符号。


title: [语言月赛 202405] 最大的和

type: B

description:
小 S 喜欢连在一起的数字，如果这些数字的和很大就更好了。

所以她现在要给你一个 $n$ 行 $n$ 列的网格 $A$，第 $i$ 行第 $j$ 列上填有一个**整数** $A_{i, j}$。

接下来你可以在 $A$ 上任取**一行**、**一列**或**一条与任意对角线平行**且**只经过网格交叉点**的**直线**（注意，不是线段），满足经过至少一个数字，且经过的数字之和最大。

如果对上面的表述有疑惑，请参考**样例解释**辅助理解。

你需要告诉小 S 这个最大的数字之和。

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

第一行，一个正整数 $n$，表示方阵的行数、列数。
接下来 $n$ 行，每行 $n$ 个用空格隔开的**整数**，其中第 $i$ 行第 $j$ 个整数表示 $A_{i, j}$。

outputFormat: 输出一行一个整数，表示最大的数字之和。

hint:
### 样例 1 解释

对于样例 $1$，不难看出第 $3$ 行数字之和最大，有 $3 + 3 + 3 = 9$。

### 样例 2 解释

对于样例 $2$，数字之和最大的，满足条件的线如下所示：

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

此时有 $4 + 9 = 13$。

注意，因为要求与对角线平行的直线只能经过**网格交点**，所以并不能出现同时取 $4, 1, 9$ 或同时取 $4, 1, 9, 2$ 这样的情况。

### 样例 $3$ 解释

取某条只经过一个 $-1$ 的直线即为最大。注意，不可以一个数字都不选。

### 样例 $4$ 解释

显然，取斜着的线一定不优，只能选择中间那一行或一列，答案是 $-10 + 99999 - 10 = 99979$。

### 数据范围

对于前 $30 \%$ 的数据，保证 $A_{1, 1}$ 或 $A_{n, n}$ 的值为网格中**唯一的**非负整数。
对于另 $20 \%$ 的数据，保证**每一行**数字相同，且最后一行中的数字之和为**最大值**。
对于另 $20 \%$ 的数据，保证**每一行**数字相同，网格中不存在负数。
对于 $100 \%$ 的数据，保证 $1 \leq n \leq 2 \times 10^3, -10^5 \leq A_{i, j} \leq 10^5$。


title: 矩阵链排序问题

type: P

description:
给定 $n$ 个矩阵，已知第 $i$ 个矩阵 $M_i$ 的大小为 $w_i$ 行 $w_{i+1}$ 列，而我们并不关心其内容。我们考虑将其按照顺序相乘（称其为链乘积）：

$$ M = M_1 \times M_2 \times \cdots \times M_n $$

矩阵乘法并不满足交换律，但是其满足结合律，因此我们可以通过合理安排结合顺序，尽可能减少需要的运算次数。在此题中，我们定义将一个大小为 $a \times b$ 的矩阵乘以一个大小为 $b \times c$ 的矩阵需要 $abc$ 次运算。

请你算出将题目所给的 $n$ 个矩阵进行链乘积所需的最少运算数。为了方便起见，你不需要构造方案。

inputFormat:
输入的第一行为一个正整数 $n$，代表矩阵的数量。

接下来的一行包含 $n+1$ 个正整数，其中第 $i$ 个整数为 $w_i$，含义参考题目描述。

outputFormat: 输出包含一个整数，代表最小运算次数。

hint:
样例解释：样例告诉我们有 $n = 3$ 个矩阵，其大小分别是 $5 \times 3$，$3 \times 2$ 和 $2 \times 6$。分别考虑两种乘法顺序：

- 先将 $M_1$ 和 $M_2$ 相乘得到一个 $5 \times 2$ 的矩阵，然后和 $M_3$ 相乘，此时运算次数为 $5 \times 3 \times 2 + 5 \times 2 \times 6 = 90$；
- 先将 $M_2$ 和 $M_3$ 相乘得到一个 $3 \times 6$ 的矩阵，然后和 $M_1$ 相乘，此时运算次数为 $3 \times 2 \times 6 + 5 \times 3 \times 6 = 126$。

本题要求运算次数最少，因此答案为 $90$。

---

对所有的数据，$1 \leq n \leq 2 \times 10^6$，$1 \leq w \leq 10^4$。其中：

- 对 $30\%$ 的数据，满足 $n \leq 500$；
- 对另外 $30\%$ 的数据，满足 $n \leq 2 \times 10^5$。


title: [语言月赛 202404] 疯狂大减价

background: gza 去超市，超市大减价！

description:
超市提供了两张优惠券：

- 第一张：满 $100$ 元减 $20$ 元；
- 第二张：满 $200$ 元减 $50$ 元。

gza 可以以任意顺序使用优惠券。先使用的优惠券会对后使用的优惠券产生影响。例如，购买了 $210$ 元的商品，先使用第一张优惠券后，价格会变为 $190$ 元，此时，无法使用第二张优惠券。

给定初始需支付金额 $n$，求最终 gza 需要支付的金额的最小值。

inputFormat: 一行一个整数 $n$，代表需要支付的商品总价。

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

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

对于 $100\%$ 的数据，$1 \leq n \leq 1000$。


title: [UESTCPC 2024] 汉诺塔排序问题

description:
Natsuzora 在玩一个特殊规则的汉诺塔。

汉诺塔有 $A$、$B$、$C$ 共三根柱子，每根柱子上可以堆叠放置圆盘。圆盘可以在不同柱子之间移动，但必须遵守以下规则：

- 一次只有一个圆盘被移动；
- 每次移动只能将一个柱子最顶端的圆盘移动到另一个柱子的最顶端；
- 在柱子 $B$ 和 $C$ 上，不允许任何圆盘放置在另外一个比它本身小的圆盘上；
- **在柱子 $A$ 上，允许将较大的圆盘放置在较小的圆盘上。**

最开始时，Natsuzora 将 $n$ 个大小互不相同的圆盘乱序地摞在 $A$ 柱子上并将柱子 $B$ 和 $C$ 留空。在满足上述条件的情况下，Natsuzora 想要知道，若要将 $A$ 柱上的圆盘全部移动到 $B$ 柱上，他至少需要进行多少次移动。

inputFormat:
第一行包含一个整数 $T$ $(1\leq T\leq 10^4)$，表示数据组数。

每组数据的第一行包含一个整数 $n$ $(1\leq n\leq 10^5)$，表示初始状态下柱子 $A$ 上的圆盘数量。

每组数据的第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$ $(1\leq p_i\leq n)$，其中 $p_i$ 表示柱子 $A$ **从下往上**第 $i$ 个圆盘的直径。数据保证 $p_1,p_2,\ldots,p_n$ 是一个长度为 $n$ 的排列，即 $1$ 到 $n$ 中的每个整数都在序列中出现恰好一次。

对于所有数据，保证 $\sum n\leq 2\times 10^5$。

outputFormat: 对于每组数据，输出一行一个整数，表示需要的最少移动次数。

hint:
在第一个样例中，一种可行的次数最少的移动方案如下（$X\rightarrow Y$ 表示将柱子 $X$ 最顶上的圆盘移动到柱子 $Y$ 的顶部）：

  1. $A\rightarrow C$
  2. $A\rightarrow B$
  3. $A\rightarrow C$
  4. $B\rightarrow C$
  5. $A\rightarrow B$
  6. $C\rightarrow A$
  7. $C\rightarrow A$
  8. $C\rightarrow B$
  9. $A\rightarrow B$
  10. $A\rightarrow B$
  11. $A\rightarrow B$


title: [语言月赛 202404] ZngivaeL 的中考

description:
ZngivaeL 去中考。他有 4 门科目需要考试，每门都有一个评级（$\texttt{ABCD}$）。

Zngivael 有三种去向选择：重点高中、普通高中和职业高中。三所高中的录取难度由高到低依次为重点高中、普通高中、职业高中。

如果 Zngivael 的 4 门科目**全部**得到了 $\texttt{C}$ 及以上的评级（$\texttt{A, B, C}$），则可以选择前去**普通高中**，否则只能选择前去**职业高中**。

进一步地，进入**重点高中**需要 Zngivael 所有科目的评级都是 $\texttt{A}$ 或 $\texttt{B}$，以及**至少有一门科目**的评级是 $\texttt{A}$。

给定可爱 ZngivaeL 的每门课的评级，询问 ZngivaeL 能上的录取难度最高的高中。

inputFormat: 输入一行，包含四个 $\texttt{A} \sim \texttt{D}$ 之间的大写字母，表示 ZngivaeL 的各科评级。

outputFormat:
一行一个字符串，表示每一组数据的答案。

假如 ZngivaeL 能上**重点高中**，则输出 `I'm so happy.`；如果能上**普通高中**但不能上**重点高中**，则输出 `This is ok.`；如果只能上**职业高中**，则输出 `Never give up.`。

samples:
ABCD
Never give up.

samples:
BBBB
This is ok.

samples:
AAAA
I'm so happy.

samples:
CCCA
This is ok.

hint:
### 样例解释

**样例解释 #1：** 因为有一个科目评级为 $\texttt{D}$，所以只能上**职业高中**。

**样例解释 #2：** 所有科目评级为 $\texttt{B}$。因为没有一门科目评级为 $\texttt{A}$，所以能上**普通高中**但不能上**重点高中**。

### 数据规模与约定

保证输入的四个字符均为大写字母 $\texttt{A, B, C, D}$ 其中之一。


title: [语言月赛 202404] 吃苹果

description:
一共有 $n$ 只苹果，你想要选择其中**恰好**两只苹果。

每只苹果有一个营养值 $a_1, a_2, \cdots, a_n$，你需要选择一只营养值最大的给 gza 吃，选择一只营养值最小的给 gza 的朋友 azg 吃。

请注意，由于某些苹果会有虫蚀等等，营养值可能为负数。即使发生了这种情况，你也必须选择恰好两只苹果带走。

所需要付的价钱是所选择两只苹果的营养值和，请输出你所需要付的价钱。

inputFormat:
第一行一个整数 $n$，表示苹果的数量。

第二行 $n$ 个整数 $a_1, \cdots, a_n$，分别表示第 $1, 2, \cdots, n$ 只苹果的营养值。

outputFormat: 一行一个整数，表示所需要付的价钱。


title: [语言月赛 202404] 神秘排列

description:
一个数列是**神秘数列**当且仅当满足下列条件：

1. 这个数列是一个排列。即，整数 $1 \sim n$ 均在这个数列中出现过，且其中的每种整数仅出现过一次（例如，当 $n=4$ 时，$1,2,4,3$ 是一个排列， $1,2,2,2$ 不是一个排列）；
2. 我们将一个数列中 $x$ 出现的位置（出现在第几个）记作 $p_x$（$1 \leq p_x \leq n$），神秘数列需要满足对于 $1 \sim n$ 中的任意一个整数 $i$，都有 $p_i=a_i$。

例如，对序列 $3, 5, 2, 1, 4$，其中 $1$ 的出现位置为 $4$，因此 $p_1 = 4$。但是 $a_1 = 3 \neq p_1$，因此这个序列不是神秘序列。

你的工作是需要判定一个数列 $a_1, a_2, \cdots, a_n$ 是否为**神秘数列**。

inputFormat:
第一行一个整数 $n$，表示数列的长度。
第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n$。

outputFormat: 一个字符串，假如这个数列是神秘数列，则输出 `YES`，否则输出 `NO`。

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

对于 $40\%$ 的数据，$1 \leq n \leq 100$。

对于 $70\%$ 的数据，$1 \leq n \leq 2000$。

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

数据保证 $a$ 是一个排列。即，整数 $1 \sim n$ 均在这个数列中出现过，且每种整数仅出现过一次。


title: 【模板】多项式复合函数（加强版）

background: 本题相较于 [P5373](https://www.luogu.com.cn/problem/P5373) 扩大了数据范围。

description:
给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$，你需要求一个 $n$ 次多项式 $H(x)$ ，满足条件：
$$H(x) \equiv F(G(x))\space (\text{mod }x^{n+1})$$
换种说法，你要求的多项式应满足：
$$H(x) \equiv \sum_{i=0}^n [x^i]F(x)\times G(x)^i \space (\text{mod }x^{n+1})$$
将结果的各项系数对 $998244353$ 取模。

inputFormat:
第一行两个正整数 $n,m$，分别表示 $F(x)$ 和 $G(x)$ 的次数。

第二行 $n+1$ 个非负整数 $f_i$，表示 $F(x)$ 的 $i$ 次项系数。

第三行 $m+1$ 个非负整数 $g_i$，表示 $G(x)$ 的 $i$ 次项系数。

outputFormat: 输出一行 $n+1$ 个非负整数，从低到高表示 $H(x)$ 的系数。


title: [GESP202403 八级] 公倍数问题

description:
小 $A$ 写了一个 $N\times M$ 的矩阵 $A$，我们看不到这个矩阵，但我们可以知道，其中第 $i$ 行第 $j$ 列的元素 $A_{i,j}$ 是 $i$ 和 $j$ 的
公倍数（$i=1,\dots,N,j=1,\dots,M$）。现在有 $K$ 个小朋友，其中第 $k$ 个小朋友想知道，矩阵 $A$ 中最多有多少个元素可以是 $k$（$k=1,2,\dots,K$）。请你帮助这些小朋友求解。

注意：每位小朋友的答案互不相关，例如，有些位置既可能是 $x$，又可能是 $y$，则它同可以时满足 $x,y$ 两名小朋友的要求。

方便起见，你只需要输出 $\sum_{k=1}^{K}k\times ans_k$ 即可，其中 $ans_k$ 表示第 $k$ 名小朋友感兴趣的答案。

inputFormat: 一行三个正整数 $N,M,K$。

outputFormat:
输出一行，即  $\sum_{k=1}^{K}k\times ans_k$。

请注意，这个数可能很大，使用 C++ 语言的选手请酌情使用```long long``` 等数据类型存储答案。


title: [GESP202403 八级] 接竹竿

description:
小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。

游戏规则是：每张牌上有一个点数 $v$，将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相
同的牌，则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列（包括这两张牌本身）。

小杨同学现在有一个长度为 $n$ 的卡牌序列 $A$，其中每张牌的点数为 $A_i$（$1\le i\le n$）。小杨同学有 $q$ 次询问。第 $i$ 次（$1\le i\le q$）询问时，小杨同学会给出 $l_i,r_i$ 小杨同学想知道如果用下标在 $[l_i,r_i]$ 的所有卡牌按照下标顺序玩“接竹竿”的游戏，最后队列中剩余的牌数。

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

对于每组测试数据，第一行包含一个正整数 $n$，表示卡牌序列 $A$ 的长度。

第二行包含 $n$ 个正整数 $A_1,A_2,\dots,A_n$，表示卡牌的点数 $A$。

第三行包含一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个正整数 $l_i,r_i$ 表示一组询问。

outputFormat: 对于每组数据，输出 $q$ 行。第 $i$ 行（$1\le i\le q$）输出一个非负整数，表示第 $i$ 次询问的答案。


title: [GESP样题 五级] 小杨的队列

description:
小杨的班级里共有 $N$ 名同学，学号从 $0$ 至 $N-1$。某节课上，老师要求同学们进行列队。具体来说，老师会依次点名 $M$ 名同学，让他们加入队伍。每名新入队的同学需要先站到队伍末尾（刚开始队伍里一个人都没有，所以第一个入队的同学只需要站好即可），随后，整个队伍中的所有同学需要按身高从低到高重新排序（身高相同的同学之间的顺序任意）。

排队很容易，但重新排序难倒了同学们。稍加讨论后，他们发现可以通过交换位置的方法来实现排序。具体来说，他们可以让队伍中的两名同学交换位置这样整个队伍的顺序就会发生变化，多经过这样的几次交换后，队伍的顺序就可以排好。

例如：队伍中有 $4$ 名同学，学号依次为 $10,17,3,25$，我们可以令 $3$ 号同学和 $10$ 号同学交换位置，则交换后的队伍顺序变为 $3,17,10,25$，这就是一次交换位置。

聪明的小杨想要知道：在老师每次点名一位新同学加入队伍后，在原有队伍的基础上，同学们最少要进行几次交换位置，才能完成老师按身高排序的要求。

inputFormat:
第一行一个整数 $N$，表示同学的数量
第二行 $N$ 个用空格隔开的正整数，依次表示学号为 $0,1,$ … $,N-1$ 的同学的身高（不超过 $2,147,483,647$）。
第三行一个整数 $M$，表示老师点名的数量。
接下来 $M$ 行，依次描述 $M$ 次点名：每行一个整数 $x$（$0 \le x<N$），表示要求学号为 $x$ 的同学加入队伍。保证该名同学此前不在队伍中。

outputFormat: 输出 $M$ 行，依次表示对于每次点名，同学们最少要进行几次交换位置，才能完成按身高排序的要求。

hint: 对于所有的测试点，保证 $1 \le M \le N \le 2000$。对于 $50\%$ 的测试点，保证所有同学的身高互不相同。


title: [GESP样题 六级] 下楼梯

description: 顽皮的小明发现，下楼梯时每步可以走 $1$ 个台阶、$2$ 个台阶或 $3$ 个台阶。现在一共有 $N$ 个台阶，你能帮小明算算有多少种方案吗？

inputFormat: 输入一行，包含一个整数 $N$。

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

hint: 对全部的测试点，保证 $1 \leq N \leq 60$。


title: 「KDOI-07」对树链剖分的爱

background:
楼下说得对，但是 sszcdjr 在 NOI 2024 D2T2 用巧妙做法把我的暴力树剖爆掉了。

楼上说得对，但是树链剖分把我送上 10√ 了，所以我出了这道题以表示我对树链剖分的爱喵。

description:
给出一棵 $n$ 个节点以 $1$ 为根的有根树。对于第 $2\leq i\leq n$ 个节点，其父亲 $f_i$ 在 $[l_i,r_i]$ 中均匀随机。每个树的边有边权，初始为 $0$。

现在有 $m$ 次操作，第 $i$ 次操作表示将 $(u_i,v_i)$ 的路径上所有的边的权值统一加上 $w_i$。$m$ 次操作结束后，对于所有 $i=2\sim n$，求 $(i,f_i)$ 边上权值的期望，对 $998244353$ 取模。

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

接下来 $n-1$ 行，其中第 $i$ 行两个正整数表示 $l_{i+1},r_{i+1}$。

接下来一行一个正整数表示 $m$。

接下来 $m$ 行，第 $i$ 行三个正整数表示 $u_i,v_i,w_i$。

outputFormat: 一行 $n-1$ 个正整数，其中第 $i$ 个表示边 $(i+1,f_{i+1})$ 边权的期望，对 $998244353$ 取模。


title: [COCI 2023/2024 #5] Zlagalica

background: **译自 [COCI 2023/2024 Contest #5](https://hsin.hr/coci/archive/2023_2024) T1「[Zlagalica](https://hsin.hr/coci/archive/2023_2024/contest5_tasks.pdf)」**

description:
Little Maja 喜欢拼图。既然大家都已经认识她很久了，那么一定不会对 Maja 在一个晴朗的日子里，收到一份奇怪的拼图作为礼物感到惊讶。

这个拼图由 $n$ 片组成。每片拼图的形状都是矩形，并具有一定的颜色。同时，每片拼图的背面都写着 $u$ 和 $d$ 两个数字。在精心尝试了一段时间后，Maja 发现了这些数字的含义。

她发现数字 $u$ 表示**方向**，换句话说，描述了下一块拼图从上侧还是从右侧连接这一块拼图。数字 $d$ 表示下一块拼图连接这一块拼图的起点行/列。更具体地：

- 如果 $u=0$，我们通过将下一块拼图左下角放在当前拼图上边的第 $d$ 列，将下一块拼图拼接在当前拼图的上方。

- 如果 $u=1$，我们通过将下一块拼图左下角放在当前拼图右边的第 $d$ 行，将下一块拼图拼接在当前拼图的右边。

假设有颜色分别为 `a` 和 `b` 的两块拼图。图一展示了 $u=0,d=3$ 时的拼接情况；图二展示了 $u=1,d=3$ 时的拼接情况（这里的 $u,d$ 均写在颜色为 `a` 的拼图上）

| 图一 | 图二 |
|:--:|:--:
|![](https://cdn.luogu.com.cn/upload/image_hosting/b6c7t1e9.png)| ![](https://cdn.luogu.com.cn/upload/image_hosting/sxahll4p.png)|

Maja 已经厌烦了这个拼图，但是她的好奇心是无限的。这正是她寻求你帮助的原因。她想知道，给出全部的拼图信息，以及拼装它们的顺序序列，最终拼图是什么样的？编写程序输出一个长方形字符矩阵，恰好包含最终拼图的样子，用 `.` 表示这里没有拼图。

inputFormat:
输入的第一行包含一个整数 $n$（$1 \le n \le 20$），表示拼图的数目。

接下来 $n$ 行，第 $i$ 行包含一个字符和四个整数 $b_i,r_i,s_i,u_i,d_i$，描述了第 $i$ 块拼图：

- $b_i$ 是一个小写英文字母，表示第 $i$ 块拼图的颜色。
- $r_i,s_i$（$1 \le r_i,s_i \le 10$）依次表示第 $i$ 块拼图行与列的长度。
- $u_i,d_i$（$0 \le u_i \le 1$，$1 \le d_i \le r_i,s_i$（与 $u_i$ 有关））表示第 $i$ 块拼图背面的数字，含义如题所述。

最后一行包含 $n$ 个整数，表示拼图拼接的顺序。其中数字 $i$ 表示第 $i$ 块输入的拼图。保证每块拼图在序列中出现且仅出现一次。

outputFormat:
第一行输出完成的拼图的高度与宽度。

接下来若干行，输出拼图，不属于拼图的位置用 `.` 替代。

samples:
5 7
..bbbbb
..bbbbb
aaaa...
aaaa...
aaaa...

samples:
4 9
.....aaaa
.....aaaa
bbbbbaaaa
bbbbb....

samples:
18 17
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
........aaggggg..
........aa.......
ppppppp.aa.......
pppppppcccccccccc
pppppppcccccccccc
pppppppcccccccccc
pppppppcccccccccc
pppppppcccccccccc
ppppppp..........
ppppppp..........

hint:
### 子任务

| Subtask | Points | Constraints |
| :--: | :--: | :--: |
| 1 | 17 | 拼图拼接的顺序与输入相同 |
| 2 | 12 | 对于所有拼图，$u=0$ |
| 3 | 12 | 对于所有拼图，$u=1$ |
| 4 | 9 | 无额外限制 |


title: [COCI 2023/2024 #5] Bitovi

background: **译自 [COCI 2023/2024 Contest #5](https://hsin.hr/coci/archive/2023_2024) T2「[Bitovi](https://hsin.hr/coci/archive/2023_2024/contest5_tasks.pdf)」**

description:
哪个先出现，鸡还是蛋？作为一个百万富翁活上一百年好，还是贫穷中度过七天好？如何成为国际象棋大师？如何拉起百叶窗？如何通过期末考试？如何训练龙？这些都是一些有趣的问题，我们可以在竞赛结束后再去思考，但现在我们提出一个不那么有趣的计算机科学问题。

给定两组数集 $A$ 和 $B$，大小均为 $N$。每次操作，你可以从集合 $A$ 中选择一个任意元素，并改变其二进制表示中的一个任意数位。结果数不能是改变前集合 $A$ 中的元素。

例如，数字 $5$ 的二进制是 $0101_2$。通过一次操作，它可以变成 $13=1101_2$、$1=0001_2$、$7=0111_2$ 或 $4=0100_2$。

确定一系列操作，通过这些操作集合 $A$ 变得和集合 $B$ 相等。如果两个集合大小相同，并且集合 $A$ 中没有不属于集合 $B$ 的元素，则认为两个集合是相等的。

注意：操作的数量不必是最小的，但必须满足任务的限制。

inputFormat:
第一行包含一个整数 $N$（$1 \le N \le 2^{15}$），集合 $A$ 和 $B$ 的大小。

第二行包含 $N$ 个不同的正整数 $a_i$（$1 \le a_i < 2^{15}$），表示集合 $A$ 的元素。

第二行包含 $N$ 个不同的正整数 $b_i$（$1 \le b_i < 2^{15}$），表示集合 $B$ 的元素。

outputFormat:
第一行输出操作的数目，不超过 $2^{19}$。

接下来若干行，每行输出 $x,y$（$0 \le x, y < 2^{15}$），表示将集合 $A$ 中的 $x$ 修改为 $y$。$x$ 和 $y$ 在二进制位中只能有一位不同。并且，必须满足 $x\in A$，$y\not \in A$。

hint:
### 样例解释 1

如果我们先操作 $0\ 1$，再操作 $1\ 3$，两次操作间，集合 $A$ 将有两个相同的元素，这是不被允许的。另一种可能的方案是 $2\ 3$，$0\ 2$。

### 样例解释 2

$31=11111_2$。按照从最低有效位到最高有效位修改，依次可以得到 $30,28,24,16$ 和 $0$。在所有的操作后，$A$ 和 $B$ 相同。

### 子任务

| Subtask | Points | Constraints |
| :--: | :--: | :--: |
| 1 | 10 | $a_i,b_i \le 2^{14}$ |
| 2 | 15 | $N \le 7$ |
| 3 | 30 | $N \le 2^7$ |
| 4 | 15 | 无额外限制 |


title: [COCI 2023/2024 #5] Piratski kod

background: **译自 [COCI 2023/2024 Contest #5](https://hsin.hr/coci/archive/2023_2024) T3「[Piratski kod](https://hsin.hr/coci/archive/2023_2024/contest5_tasks.pdf)」**

description:
Marrrtina 船长和她的海盗团队，在搜索了三个月之后，终于挖掘出一箱属于最著名的意大利海盗的失落宝藏。但是，要打开这个宝箱，她需要一个密码，该密码被描述在宝箱旁边的一个瓶子中的一条信息中。

信息如下：

---

只有最有价值的海盗才能打开宝箱，密码是以下谜题的答案：对于长度为 $a$ 的二进制序列 $s$，且其中唯一的连续两个 $1$ 位于序列的末尾，如果满足以下条件，它是一个数字 $x$ 的海盗表示：
$$
s[0]\cdot \text{Fib}[2] + s[1]\cdot \text{Fib}[3] + s[2]\cdot \text{Fib}[4] + \ldots + s[a − 2]\cdot \text{Fib}[a] = \sum_{i=0}^{a-2} s[i]\cdot \text{Fib}[2 + i] = x
$$
这里的 $\text{Fib}[x]$ 表示第 $x$ 个斐波那契数。斐波那契数的定义如下：$\text{Fib}[1] = 1$，$\text{Fib}[2] = 1$，对于每个 $y > 2$，$\text{Fib}[y] = \text{Fib}[y − 1] + \text{Fib}[y − 2]$。

例如，$11_p = 1$，$011_p = 2$，$1010011_p = 17$，这里的 $p$ 表示数字的海盗表示。

海盗代码是一个二进制序列（没有关于连续 $1$ 的任何条件），代表一系列正整数的序列。为了阅读它，我们将其分割为尽可能多的部分，这些部分是某些数字的海盗表示（可能还有一个不是任何数字的海盗表示的后缀），并按顺序写出这些整数。例如，我们将 $01111010110101$ 分割为 $011|11|01011|0101$，最后一部分不是海盗表示，因此我们删除它，得到 $011|11|01011$，并读到序列 $2,1,7$。

海盗代码的值等于解码后的正整数序列的值之和。前面的密码的值为 $10$。

我最喜欢的数字 $P$ 是长度为 $k$ 的所有海盗代码值的总和。由于该数字可能很大，打开宝箱的密码是 $P$ 除以 $10^9 + 7$ 的余数。

— *Leonarrrdo da Pisa*

---

如果 Marrrtina 无法打开宝箱，她的船员将认为她不值得信任，并将她逼上走板。

inputFormat: 一行一个整数 $n\ (n\le 5\ 000)$。

outputFormat: 输出一行 $n$ 个整数，其中第 $k$ 个整数表示长度为 $k$ 的密码谜题的答案。


title: [COCI 2023/2024 #5] Rolete

background: **译自 [COCI 2023/2024 Contest #5](https://hsin.hr/coci/archive/2023_2024) T4「[Rolete](https://hsin.hr/coci/archive/2023_2024/contest5_tasks.pdf)」**

description:
一个周六的下午，Luka 从午睡中醒来，想起今天有 COCI！在比赛前，他只需要做一件事情：拉起窗帘。

卢卡的房间里有 $n$ 个窗帘，其中第 $i$ 个窗帘距离窗户顶部下降了 $a_i$ 厘米。他可以通过两种方式拉起窗帘：

- 他可以手动开始拉起任意一个窗帘。使用这种方法，他每拉起 $1$ 厘米需要 $t$ 秒钟。
- 他可以按下一个按钮，同时以相同的速度将所有窗帘同步拉起。

按下按钮时，窗帘的上升速度定义如下：如果所有窗帘都在上升，每个窗帘都会在 $s$ 秒内上升 $1$ 厘米。如果 $r$ 个窗帘已经完全升起，这会减慢系统的速度。那么剩余的窗帘每上升 $1$ 厘米需要 $s + k \cdot r$ 秒钟。

COCI 即将开始，Luka 希望尽快拉起他的窗帘。与此同时，他的兄弟 Marin 走进房间，问了他 $q$ 个问题：**为了使窗帘下降的最大高度不超过 $h$ 厘米，你需要的最短时间是多少**？Marin 对于每个问题都考虑窗帘的初始状态。

他们意识到在 COCI 之前没有足够的时间来考虑这个问题。幸运的是，这个问题也出现在这里！帮助他们解决它！

注意：Luka 总是将窗帘拉起一个整数值的厘米。

inputFormat:
第一行四个整数 $n,t,s,k\ (1\le n,t,s\le 10^5,0\le k\le 10^5)$，分别表示窗帘个数，手动拉窗帘所需的时间，按下按钮拉窗帘所需的时间和同步上升的减慢因子。

第二行包含 $n$ 个整数 $a_i\ (0\le a_i\le 10^5)$，表示初始窗帘的状态。

第三行包含一个整数 $q\ (1\le q\le 10^5)$，表示问题个数。

第四行包含 $q$ 个整数 $h_i\ (0\le h_i\le 10^5)$，表示最大窗帘高度。

outputFormat: 输出一行 $q$ 个整数，第 $i$ 个表示使得窗帘下降的最大高度不超过 $h_i$ 厘米所需的最短用时。

hint:
### 样例解释 1

为了使所有窗帘的下降高度最多为 $2$ 厘米，卢卡需要手动将第三个窗帘拉起 $2$ 厘米。最快的方法是手动拉起它，这将花费他 $4$ 秒钟。

如果所有窗帘都需要完全拉起，卢卡可以先手动将第三个窗帘拉起 $2$ 厘米。然后，他可以按下按钮，让所有窗帘同时上升 $2$ 厘米。总共需要的时间为 $4 + 10 = 14$ 秒。

类似地，如果窗帘的下降高度最多为 $1$ 厘米，卢卡会先手动将第三个窗帘拉起 $2$ 厘米，然后将所有窗帘一起上升 $1$ 厘米。拉起的总时间将为 $9$ 秒。

### 子任务

| Subtask | Points | Constraints |
| :--: | :--: | :--: |
| 1 | 16 | $n,q,a_i,h_i\le 100$ |
| 2 | 26 | $k=0$ |
| 3 | 32 | $q=1$ |
| 4 | 36 | 无额外限制 |


title: [COCI 2023/2024 #5] Trokut

background: **译自 [COCI 2023/2024 Contest #5](https://hsin.hr/coci/archive/2023_2024) T5「[Trokut](https://hsin.hr/coci/archive/2023_2024/contest5_tasks.pdf)」**

description:
Ivan 和 Lucija 正在一次遥远的旅程中。他们知道旅程将持续很长时间，而且在某个时候他们会感到无聊。当他们在考虑做什么时，Lucija 想到了一个游戏。

她在纸上画了 $N$ 个点，使它们形成一个正 $N$ 边形的顶点，并按顺序标记为 $1$ 到 $N$。轮到的玩家选择两个点，满足连接这两个点的线段不与先前画的任何线段相交，并连接这两个点。线段可以在顶点处相接触。如果在玩家的回合后存在三条连接的线段形成一个三角形，即存在三个点，它们都通过已画的线段相连，则该玩家获胜。当然，玩家可以连接相邻的顶点，这些线段也可以用于形成三角形。玩家轮流进行，Lucija 先手。

两位玩家都非常熟练，我们知道他们会采用最优策略进行游戏。你的任务是确定给定 $N$ 时，谁将成为游戏的赢家。可以证明游戏将在有限次移动后结束，而且总会产生一个赢家。

inputFormat:
第一行一个整数 $T\ (1\le T\le 10\ 000)$，表示场景数。

接下来 $T$ 行，每行一个整数 $N\ (3\le N\le 10^9)$，表示 Lucija 在纸上画的点数。

outputFormat: 输出 $T$ 行，按给定的顺序，对于每个场景输出 `Ivan` 或 `Lucija`，表示该场景中的获胜者。

hint:
### 样例解释 1

当 $N = 3$ 时，必须连接所有三条可能的线段，Lucija 获胜。

当 $N = 4$ 时，Lucija 可以连接点 $1$ 和点 $3$ 之间的线段。我们看到，在 Ivan 的任何一步之后，Lucija 都可以连接一个三角形并获胜。

### 子任务

| Subtask| Points | Constraints|
| :--:|:--:|:--:|
|1|13|$T\le 18,N\le 20$|
|2|36|$T\le 998,N\le 1000$
|3|15|$N\le 10^5$|
|4|46|无额外限制|


title: 【MX-X1-T3】「KDOI-05」简单的序列问题

description:
给出一个长度为 $n$ 的序列 $a$。定义其前缀和数组 $b_i=\sum_{j=1}^ia_j$。定义其权值 $S=\sum_{i=1}^n(b_i\bmod 2)$。

你可以对序列 $a$ 进行若干次如下操作：

* 交换 $a_i,a_j$，花费 $c_i+c_j$ 元，其中 $c$ 为给定序列；

对于 $i=0\sim n$，求使得 $S=i$ 的最少钱数。如果不可能，输出 $-1$。

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

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

对于每组测试数据：

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

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

第三行 $n$ 个正整数，表示序列 $c$。

outputFormat:
对于每组测试数据：

一行，$n+1$ 个整数，第 $i$ 个表示 $S=i-1$ 的最少钱数。如果不可能，输出 $-1$。


title: 【MX-X1-T2】「KDOI-05」简单的有限网格问题

description:
小 S 在玩一款小游戏。游戏中会有一个 $n\times m$ 的棋盘，其中 $k$ 个位置上有星星。初始有一个捕捉器，在 $(x,y)$ 位置。每次操作，你可以将捕捉器移动到同行或同列的某个位置，使得新位置与原位置不同且必须保证新位置 $(x',y')$ 满足 $1\leq x'\leq n$，$1\leq y'\leq m$。**捕捉器会捕捉 $(x,y)$ 到 $(x',y')$ 路径上所有的星星**。一个星星被捕捉后将会消失。

游戏的目标是在恰好两步内获得尽可能多的星星，然而小 S 不会玩，于是每次就会随意挑选一个可以移动到的新位置进行移动。对于 $(n+m-2)^2$ 种小 S 的不同移动方案，求捕捉到的星星数量之和，答案对 $10^9+7$ 取模。

inputFormat:
第一行三个正整数 $n,m,k$，表示棋盘大小与星星个数。

第二行两个正整数 $x,y$，表示捕捉器初始位置。

接下来 $k$ 行，每行两个正整数，表示每颗星星所在的位置 $(p,q)$。每个位置上可以有多颗星星。

outputFormat: 一行，一个非负整数，表示对于 $(n+m-2)^2$ 种小 S 的不同移动方案，他能捕捉到的星星数量之和，对 $10^9+7$ 取模。


title: 『SpOI - R1』我看到了，谢谢你们

description:
**本题包含多组测试。**

**特别注意：本题中，border 的定义有所不同。对于串 $s,t$，若同时存在 $s$ 的一对前缀后缀（可空也可为 $s$ 本身）等于 $t$，则 $t$ 是 $s$ 的 border。**

有一个长度为 $n$ 的字符串 $S$。我们使用这个串上的信息来选举总统。

令 $p_i$ 表示 $S$ 的 $i$ 长前缀，特别地，$p_0$ 表示包含第 $0$ 位的空前缀。现在有 $n+1$ 位候选人站在这 $n+1$ 个前缀上，编号为 $[0,n]$，编号为 $i$ 的人对应前缀 $i$。每个人有一个票数 $a_i$ 和花费 $w_i$。

得票数量**严格**超过总票数一半的人可以当选总统。

初始时所有人都处于**未被控制**状态。每一个时刻，任何一个**未被控制**且**之前一直在等待**的人 $i$ 都可以做出三种选择之一：

1. 进行一次**对 $v$ 投票**操作：将自己的 $a_i$ 票花费 $w_i$ 的代价投给人 $v$。
2. 进行一次**对 $v$ 揽票**操作：
	- 花费 $w_i$ 选中人 $v$，需要满足 $p_i$ 是 $p_v$ 的一个 border。
	- $\forall j\in[0,n]$，若 $p_v$ 是 $p_j$ 的一个 border，且 $j$ 在此时刻**未被控制**，则 $j$ 下一时刻变为**被控制**，他的 $a_j$ 票都花费 $w_j$ 投给 $i$。
3. 等待下一个时刻。

每个候选人都希望其他人不会成为总统，且都是绝顶聪明的。**特别地**，当他们的操作出现了交叉导致一个人的票需要投给多人时，被交叉者的票可以分别独立投出并都有效（你可以理解为他的票分裂了）。因此，总统可能有多个。

你可以干涉这个过程。具体来说，你可以在 $0$ 时刻操作一个候选人 $x$，让 $x$ 进行指定的一种选择，并钦定选择涉及的所有变量。$x$ 此后不能再做任何选择，剩下的人必须从 $1$ 时刻再开始选择。你干涉的代价就是 $x$ 这次选择的总花费。

票数 $a$ 和花费 $w$ 都会发生 $q$ 次变化。

每一次变化会改变票数 $a$ 中的某一项或是花费 $w$ 中的某一项。票数 $a$ 可能会变为任意正整数，花费 $w$ 只会变小或者不变。

在每次变化之后，你都需要找到这样一个人 $x$，满足你有一种干涉他的方案使得他一定可以成为总统，且你干涉的代价最小。你只需要输出这个最小代价。

可以证明一定存在这样的人。

本题**强制在线**。

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

对于每组数据：

一行三个整数 $n,q,type$，表示字符串长度、修改次数、是否强制在线。

接下来一行一个长度为 $n$ 的字符串 $S$。保证 $S$ 中只含有小写英文字母。

接下来 $n+1$ 行，每行两个整数 $a_i,w_i$，依次表示候选人 $0$ 到 $n$ 的初始票数和花费。

接下来 $q$ 行，每行三个整数 $o',p',x'$。设 $lst$ 表示上一次输出的答案的绝对值，则 $o\gets o'\oplus(type\times lst),p\gets p'\oplus(type\times lst),x\gets (|x'|\oplus(type\times lst))\times (-1)^{[x'\leq 0]}$（其中 $[x'\leq 0]$ 为[艾佛森括号](https://baike.baidu.com/item/%E8%89%BE%E4%BD%9B%E6%A3%AE%E6%8B%AC%E5%8F%B7/22361197)），然后：

1. $o=1$ 时，将 $a_p$ 修改为 $x$。
2. $o=2$ 时，将 $w_p$ 修改为 $w_p'=x$。保证 $w_p\geq w_p'$。

outputFormat:
共 $q+1$ 行。

第一行输出在初始状态下你干涉的最小代价。

之后，在每次修改后输出你此时干涉的最小代价，共 $q$ 行。


title: 救赎（Redemption）

background:
>$$主啊，$$
>
>$$这个人也是我们要拯救的吗\dots$$
>
>$$愿我的弹雨能熄灭你们的痛苦\dots$$
>
>$$如果您见到一位散发着不祥气息的天使，$$
>
>$$请替我转告她：$$
>
>$$我从来没有忘记过她\dots$$

description:
给出 $n,m$ 和 $n$ 个整数 $a_i$（$1\le i\le n$）。

求：

$$ \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}\left \lfloor \frac{m}{a_ia_j}  \right \rfloor$$

输出答案对 $998244353$ 取模的结果。

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

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

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


title: 孤独（Solitude）

background:
>$$行走的岁月静好，$$
>
>$$苍青的天空古老。$$
>
>$$轻轻唱起，$$
>
>$$那只风鸟。$$
>
>$$你却不见了。$$

description:
给出 $n$ 和 $n$ 个整数 $a_i$（$1\le i\le n$），$n$ 个整数 $b_i$（$1\le i\le n$）。

现在对于一个长为 $n$ 的序列 $S$ 有以下规定：

- $S_i=a_i$ 或 $b_i$。

- 对于所有的 $S_i$（$1\le i\le n$），若 $S_i>S_{i-1}$ 且 $S_i>S_{i+1}$ 那么称 $S_i$ 为**峰**，特别地 $S_0=S_{n+1}=0$。

**现求：最大峰数以及取到最大峰数时的最大极差。**

**极差：一个序列中最大值和最小值的差。**

**updated：$S_0$ 和 $S_{n+1}$ 不参与极差运算。**

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

第二行 $n$ 个整数，表示 $a_1,a_2\dots a_n$。

第三行 $n$ 个整数，表示 $b_1,b_2\dots b_n$。

outputFormat:
输出共两行。

第一行一个整数表示**最大峰数**。

第二行一个整数表示**取到最大峰数时的最大极差**。


title: 悲哀（Sorrow）

background:
>$$你是天使，$$
>
>$$于光与圣歌中降临。$$
>
>$$我是恶魔，$$
>
>$$从血与污泥中爬出。$$
>
>$$我想拥抱你，$$
>
>$$但是害怕血，$$
>
>$$染红你洁白的羽翼。$$

description:
给出一棵有 $n$ 个节点且以 $1$ 为根节点的树，每个节点有两个权值 $a_i,b_i$（$1\le i\le n$）。$a_i$ 已经给出，$b_i$ 初始为 $0$。

现在对于每一对节点 $(u,v)$（$1\le u<v\le n$），设 $x=\operatorname{LCA}(u,v)$，如果 $\gcd(a_u,a_v)>1$ 那么 $b_x\gets b_x+a_u\times a_v$，否则不做任何操作。

对于每个 $1\le i\le n$ 求出 $b_i\bmod998244353$。

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

第二行 $n$ 个正整数，表示 $a_1,a_2\dots a_n$。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示节点 $u$ 和节点 $v$ 之间有一条边。

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

第 $i$ 行表示 $b_i$ 对 $998244353$ 取模后的结果。


title: 国土规划

description:
一个国家的领土中，有 $n$ 座城市和 $m$ 条道路。这 $m$ 条道路将 $n$ 座城市连通，即任意两座城市存在道路直接或间接可达。两座城市之间可能有多条道路，但不存在一条道路两端连通同一座城市。

该国家要选定一些城市，重点发展。具体而言，每个城市有一个重要值 $a_i$，其中 $a_i=0$ 表示城市不需要重点发展，如果 $a_i=1$ 表示城市需要重点发展。初始时所有 $a_i=0$。

该国家有 $q$ 次规划，每次规划会选定一个城市 $x$，令 $a_x \gets 1-a_x$。

每次规划后，作为首席规划师的你要求出这样的城市 $p$ 的数量，使得 $a_p=0$，且城市 $p$ 消失（连带与城市 $p$ 直接相连的道路一起消失）后，任意满足 $a_u=a_v=1$ 的两个城市 $u,v$ 均存在道路直接或间接可达。

需要注意，规划只是在纸面上假想的，并不会真的删去任何城市。

inputFormat:
输入的第一行包含由空格隔开的三个正整数 $n,m,q$。

接下来的 $m$ 行，每行包含两个正整数 $u,v$，描述一条连接 $u,v$ 两座城市的双向道路。

接下来的 $q$ 行，每行包含一个正整数 $x$，描述一次规划。

outputFormat: 输出 $q$ 行，每行包含一个非负整数，代表每次修改后问题的答案。

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

以第四次规划为例，此时需要重点发展的城市为 $1$ 和 $4$，那么 $a_p=0$ 的城市只有 $2$ 和 $3$。如果城市 $2$ 消失，那么存在路径 $1-3-4$。如果城市 $3$ 消失，那么 $1$ 和 $4$ 互相不可到达。所以满足条件的城市只有 $2$，答案为 $1$。

**【数据范围】**

- 对于 $15\%$ 的数据，$n,q \le 300$，$m \le 500$。
- 对于另外 $15\%$ 的数据，$m=n-1$，且对于所有道路，$v=u+1$。
- 对于另外 $20\%$ 的数据，$m=n-1$。

对于所有数据，$2 \le n \le 10^5$，$n-1\le m \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$，$1 \le u,v,x \le n$，$u \neq v$。


title: [GESP样题 六级] 亲朋数

description:
给定一串长度为 $L$、由数字 $0\sim 9$ 组成的数字串 $S$。容易知道，它的连续子串儿共有 $\frac{L(L + 1)}2$ 个。如果某个子串对应的数（允许有前导零）是 $p$ 的倍数，则称该子串为数字串 $S$ 对于 $p$ 的亲朋数。

例如，数字串 $S$ 为“ $12342$ ”、$p$ 为 $2$，则在 $15$ 个连续子串中，亲朋数有“ $12$ ”、“ $1234$ ”、“ $12342$ ”、“ $2$ ”、“ $234$ ”、“ $2342$ ”、“ $34$ ”、“ $342$ ”、“ $4$ ”、“ $42$ ”、“ $2$ ”等共 $11$ 个。注意其中“ $2$ ”出现了 $2$ 次，但由于其在 $S$ 中的位置不同，记为不同的亲朋数。

现在，告诉你数字串 $S$ 和正整数 $p$ ，你能计算出有多少个亲朋数吗？

inputFormat:
输入的第一行，包含一个正整数 $p$。约定 $2 \leq p \leq 128$。
输入的第二行，包含一个长为 $L$ 的数字串 $S$。约定 $1 \leq L \leq 10^6$。

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


title: 『FLA - I』冲云霄

background:
**[English statement.](/problem/U458236) You must submit your code at the Chinese version of the statement.**

住在呼和浩特的小 R 很久以前就学会了异或。异或使用符号 $\oplus$ 表示，在 C++ 中可用符号 `^` 表示。非负整数 $x$ 和 $y$ 的异或是指对它们二进制表示中的每一位进行如下运算得到的结果：

- 若 $x$ 和 $y$ 的第 $k$ 个二进制位相同，结果的第 $k$ 个二进制位为 $0$；
- 若 $x$ 和 $y$ 的第 $k$ 个二进制位不同，结果的第 $k$ 个二进制位为 $1$。

使用 $(X)_{10}$ 表示十进制数 $X$，$(Y)_2$ 表示二进制数 $Y$，因为 $(12)_{10}=(1100)_2$，$(10)_{10}=(1010)_2$，所以 $(12)_{10} \oplus (10)_{10}=(1100)_2 \oplus (1010)_2=(0110)_2=(6)_{10}$。

住在银川的小 F 想用这道题难倒小 R 但失败了，现在小 F 又想用这道题为难你，不能让他的阴谋得逞！

description:
给定**整数** $n$ 和 $m$，判断是否存在满足下列条件的数列 $a$。本题中数列元素的下标从 $1$ 开始。

- 数列 $a$ 的长度为 $m$，数列 $a$ 的每一项都为**正整数**。

- $a_1 \oplus a_2 \oplus \cdots \oplus a_m = n$，即数列 $a$ 的所有项异或得到的结果等于 $n$。

- 数列 $a$ 中所有元素的值都相同。

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

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

对于每组测试数据，输入一行两个整数 $n,m$。

outputFormat: 对于每组测试数据，输出一行一个字符串。如果存在满足条件的数列 $a$，输出 `Yes`；否则输出 `No`。


title: 【MX-X5-T5】「GFOI Round 1」World Ender

background: > [$\small\text{The Border of \textbf{Divinity}}.$](https://music.163.com/#/song?id=1962519608)

description:
**这是一道交互题，仅支持 C++ 语言提交，且不支持 C++14（GCC 9）。**

Hikari 和 Tairitsu 用她们的玻璃渣子发明了新的游戏。

有 $n$ 堆碎片，编号为 $0\sim n-1$。

$a$ 为一个长度为 $n$，下标为 $0\sim n-1$ 的正整数序列，表示第 $i$ 堆碎片的数量为 $a_i$。

她们轮流进行操作，每轮操作如下：

- 选择一堆碎片 $i$，拿出不少于一个碎片并丢弃；
- 然后将 $i$ 这一堆中剩下的碎片随意分配到所有非空的堆中，**特别地，可以放回原来的堆**。

Hikari 先手，不能操作者输。

你将会成为 Hikari 或者 Tairitsu 中的一个，和另一个进行游戏。

具体地，给定 $a_0, a_1, \ldots, a_{n-1}$，你需要选定先后手并在 $a_0, a_1, \ldots, a_{n-1}$ 上和交互库进行游戏。

### 交互格式

**本题使用多组测试数据且采用捆绑测试**。

你的程序不需要，也不应该包含 `main` 函数。

然后你只需要实现如下 $3$ 个函数：

`bool Init(int n, int op, std::vector<int> a);`

- 这个函数用于你的程序的初始化与预处理。
- 其中 $n$ 为题意所述的碎片堆数，$op$ 为子任务编号。
- $a$ 为一个长度为 $n$，下标为 $0\sim n-1$ 的 `std::vector<int>`，表示上述的序列。
- 你需要返回一个 $\{0,1\}$ 中的数。返回 $0$ 表示在游戏中你选择先手 Hikari，返回 $1$ 表示你选择后手 Tairitsu。

`void Get(std::vector<int> a);`

- 这个函数用于你的程序**接收**交互库操作后的序列。
- $a$ 为一个长度为 $n$ 的 `std::vector<int>`，表示交互库操作后所给出的序列。

`std::vector<int> Play();`

- 这个函数用于你的程序**返回**你操作后的序列。
- 你需要返回一个长度为 $n$ 的 `std::vector<int>` $a$，表示你操作后所给出的序列。

**本题每个测试点有多组测试数据**。在每个测试点中，对于每组数据，交互库的交互格式如下：

- 先调用一次 `Init()`。
- 当选手程序选择了先手，调用 `Play()`；否则跳过这一步。
- 交互库对 $a$ 进行一次操作后调用 `Get()`。
- 接下来交互库交替调用 `Play()` 和 `Get()`，保证每连续两次调用中操作恰好调用一次 `Play()` 和一次 `Get()`。
- 特别地，如果某次调用 `Play()` 后交互库将 $a$ 操作至终止状态，或者交互库无法操作时，交互库会得出结果并终止这组测试数据的调用过程，跳到下一组测试数据。也就是最后交互库并不会再调用一次 `Get()`。

本题将使用**自定义校验器**对你的交互过程进行评分，具体见 **【评分方式】**。

inputFormat: 见 **【说明/提示】**。

outputFormat: 见 **【说明/提示】**。

hint:
**本题使用多组测试数据。**

**【样例解释】**

该样例由两个测试数据构成。

第一个测试数据，选择先手 Hikari 必胜。

第二个测试数据，选择后手 Tairitsu 必胜。

**【说明/提示】**

本题附件中提供了 `grader.cpp` 文件和 `sample.cpp` 文件。`sample.cpp` 是选手示例程序，你可以在此基础上实现。`grader.cpp` 是下发交互库，其中下发交互库的策略不是最终交互库的策略，因此你的实现不应依赖于交互库的实现。

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

`g++ -o game grader.cpp game.cpp -O2 -std=c++14`

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

- 第一行两个正整数 $T$ 和 $op$，$T$ 为测试数据组数，$op$ 为子任务编号。有且仅有样例满足 $op=0$。
- 接下来每组测试数据，输入格式如下：
  - 第一行输入一个正整数 $n$，表示序列 $a$ 的长度。
  - 第二行输入 $n$ 个正整数，表示 $a_0,a_1,\ldots,a_{n-1}$。

在本地测试时，请务必保证你的输入与交互格式符合要求，否则我们不保证交互库会正常运行。

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

- 若你成功打赢了交互库，交互库输出 `AC`。
- 否则交互库输出 `WA`。

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

**【评分方式】**

本题将使用**自定义校验器**对你的交互过程进行评分。在每个测试点中，如果你超出了时间限制，超出了空间限制，或发生了运行时错误，则你的得分为 $0$。否则你的分数取决于你的程序在交互过程中的表现：

- 参数 $S$ 与你的程序在交互过程中的表现有关：
  - 若你在测试点中的每个测试数据中，均选择了正确的先后手并且均打赢了交互库，则 $S=1$。
  - 若你在测试点中的每个测试数据中，均选择了正确的先后手但是有不合法操作或者打输了交互库，则 $S=0.2$。
  - 若你在测试点中的每个测试数据中，至少一次选择了错误的先后手但是均打赢了交互库，则若 $op\in \{4,5\}$，$S=1$；否则 $S=0.6$。
  - 否则 $S=0$。
- 最终你在该测试点的得分为 $S\times score$，$score$ 为测试点所在子任务的分数。
- 最终你在某个子任务的得分为你在子任务内所有测试点的得分的最小值。

**【数据范围】**

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

| 子任务编号（$op =$） | $n\le$ | $a_i\le$ | 特殊性质 | 分值 |
| :--------: | :----: | :------: | :------: | :--: |
|    $1$     |  $3$   |   $2$    |    无    | $5$  |
|    $2$     |  $10$  |   $2$    |    无    | $15$ |
|    $3$     | $100$  |  $100$   |    无    | $10$ |
|    $4$     | $2000$ |  $2000$  |    A     | $15$ |
|    $5$     | $2000$ |  $2000$  |    B     | $20$ |
|    $6$     | $2000$ |  $2000$  |    无    | $35$ |

- 特殊性质 A：交互库的策略为选择一个非空的堆，拿走若干个碎片并将剩余的碎片放回原堆中。
- 特殊性质 B：交互库的策略为选择一个非空的堆，拿走若干个碎片并将剩余的碎片全部放到一个堆中（可能为原堆）。

对于所有数据，满足 $1 \le T\le 2000$，$1 \le op \le 6$，$1 \le n\le 2000$，$1 \le a_i\le 2000$，$1 \le \sum a_i \le 4000$，$1 \le\sum n\le 2000$，$1 \le \sum\sum a_i\le 4000$。

保证每个测试点中 `Init()` 的调用次数不超过 `2000` 次，`Get()` 和 `Play()` 的调用次数总和不超过 `4000` 次。当选手交互格式正确时，交互库运行所占用的时间始终不超过 500ms。


title: [GESP样题 七级] 迷宫统计

description:
在神秘的幻想⼤陆中，存在着 $n$ 个古老而神奇的迷宫，迷宫编号从 $1$ 到 $n$。有的迷宫之间可以直接往返，有的可以⾛到别的迷宫，但是不能⾛回来。玩家小杨想挑战⼀下不同的迷宫，他决定从 $m$ 号迷宫出发。现在，他需要你帮助他统计：有多少迷宫可以直接到达 $m$ 号迷宫，$m$ 号迷宫可以直接到达其他的迷宫有多少，并求出他们的和。

需要注意的是，对于 $i$ ($1 \leq i \leq n$) 号迷宫，它总可以直接到达自身。

inputFormat:
第一行两个整数 $n$ 和 $m$，分别表示结点迷宫总数，指定出发迷宫的编号。
下面 $n$ 行，每行 $n$ 个整数，表示迷宫之间的关系。对于第 $i$ 行第 $j$ 列的整数，$1$ 表示能从 $i$ 号迷宫直接到达 $j$ 号迷宫，$0$ 表示不能直接到达。

outputFormat: 一行输出空格分隔的三个整数，分别表示迷宫 $m$ 可以直接到达其他的迷宫有多少个，有多少迷宫可以直接到达 $m$ 号迷宫，这些迷宫的总和。


title: 【MX-X1-T5】「KDOI-05」简单的树上问题

description:
小 S 有一棵 $n$ 个点的树。每个点上有一个灯泡。

小 S 决定进行 $k$ 次闪灯操作。执行闪灯操作时，他会用电脑主机给每个灯泡发送一次闪灯操作。

然而，小 S 的灯泡是劣质品，只有一部分的灯泡可以收到小 S 的闪灯操作。具体地，第 $j$ 个点上的灯泡有 $p_{i,j}$ 的概率收到小 S 的第 $i$ 次闪灯操作。

好在，小 S 的不同灯泡之间有信息传递功能。具体地，如果一个灯泡在两个收到信息的灯泡的树上最短路径上，这个灯泡也能执行闪灯操作（当然，收到信息的灯泡会执行闪灯操作）。

定义一个灯泡 $i$ 的美丽度为 $a_{i,S}$，其中 $S$ 为这个灯泡执行闪灯操作的操作集合。

定义整棵树的美丽度为每个灯泡美丽度的乘积。求整棵树美丽度的期望，对 $998244353$ 取模。

inputFormat:
第一行两个正整数 $n,k$，表示树的点数与操作次数。

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

接下来 $k$ 行每行 $n$ 个非负整数，第 $i$ 行第 $j$ 个表示 $p_{i,j}$ 对 $998244353$ 取模后的值。

接下来 $n$ 行每行 $2^k$ 个非负整数，第 $i$ 行第 $(\sum_{i=1}^k2^{i-1}[i\in S])+1$ 个表示 $a_{i,S}$。可以理解为 $a_{i,j}$ 中 $j-1$ 的从低到高第 $x$ 个二进制位代表是否有 $x$ 操作。

outputFormat: 一行，一个非负整数，表示整棵树的美丽度的期望，对 $998244353$ 取模。


title: [UESTCPC 2024] 一站到底

description:
假设你是电子科技大学的学生李华，在 4202 年的某一期一站到底中，你作为选手参加了节目的录制。不同于 2000 多年前的规则，节目中不会进行选手两两对战并抢答或轮答题目的环节，每位选手的答题以单人赛的方式进行，具体规则如下：

在选手的答题环节开始前，系统会从题库中抽取 $n$ 道题，每道题根据难度系数有 $a_i$ 的分值。主持人会在一开始公布所有的题目内容和分值，之后进入选手的答题环节。

为了增加节目的趣味性，在答题环节中，选手并不能随意选择作答题目的顺序。具体的，除 $1$ 号题目外所有题目**有且仅有**一道前置题目，在选手正确作答出某道题的前置题目后才可以进行作答这道题。节目组保证编号为 $i$ 的题目的前置题目编号必然小于 $i$。

此外，如果选手作答题目时提交了错误答案，那么其脚下的地板将立刻打开，选手掉落并结束作答，此前答对的所有题目的分值之和就是该选手的得分。如果选手答对了所有的题目，那么所有题目的分值之和就是该选手的得分。

现在你已经看完了所有的题目，根据你的知识储备，你判断出了每道题你做对的概率 $p_i$。你需要在最短时间内制定出最优的做题策略去最大化你的期望得分，请输出这个得分，~~并以参加这次节目的过程为主题写一篇不少于 120 词的英语作文~~。

inputFormat:
第一行一个正整数 $n$ $(2\le n\le 10^5)$，代表题目的数量。

接下来一行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq 10^6)$，$a_i$ 代表编号为 $i$ 的题目的分值。

接下来一行 $n$ 个实数 $p_1,p_2,\ldots,p_n$ $(0<p_i<1)$，$p_i$ 代表你答对编号为 $i$ 的题目的概率。

接下来一行 $n-1$ 个正整数 $t_1,t_2,\ldots,t_{n-1}$ $(1\leq t_i\leq i)$，$t_i$ 代表编号为 $i+1$ 的题目的前置题目的编号。

outputFormat:
输出一行一个实数，代表在最优做题策略下的期望得分。

假设你的输出是 $a$，答案是 $b$，当且仅当 $\frac{|a-b|}{\max(1,b)}\le 10^{-9}$ 时，你的答案会被认为是正确的。

hint: 在样例中，分值越高的题目你也有越大的概率答对，显然按照 $1,2,3,4,5$ 的顺序去答题最优。


title: [GESP样题 八级] 区间

background: 小杨有一个长度为 $n$ 的正整数序列 $A$。

description:
小杨有一个长度为 $n$ 的正整数序列 $A$。

小杨有 $q$ 次询问。第 $i$ 次（$1\le i\le q$）询问时，小杨会给出 $l_i,r_i,x_i$，请你求出 $x_i$ 在 $A_{l_i}, A_{l_i+1}, \dots A_{r_i}$ 中出现的次数。

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

对于每组数据：第一行包含一个正整数 $n$，表示序列 $A$ 的长度。
第二行包含 $n$ 个正整数 $A_1,A_2,\dots,A_n$，表示序列 $A$。
第三行包含一个正整数 $q$，表示询问次数。接下来 $q$ 行，每行三个正整数 $l_i,r_i,x_i$，表示一组询问。

outputFormat: 对于每组数据，输出 $q$ 行。第 $i$ 行（$1\le i\le q$）输出一个非负整数，表示第 $i$ 次询问的答案。


title: 「XSOI-R1」凑点

description:
小 T 会给你一个长度为 $n$ 的整数数列，你手上有一个数 $x$，初始为 $0$，你可以执行以下操作，使得最终 $x$ 与 $c$ 的差小于 $10^{-4}$。

你可以对 $x$ 进行至多 $k$ 次操作：

- `add i`，对计数器 $x$ 加上 $a_i$，然后 $a_i$ 不能再进行任何操作。

- `sub i`，对计数器 $x$ 减上 $a_i$，然后 $a_i$ 不能再进行任何操作。

- `mul i`，对计数器 $x$ 乘上 $a_i$，然后 $a_i$ 不能再进行任何操作。

- `sqrt i`，将 $a_i$ 赋值为 $\sqrt {a_i}$，每个 $a_i$ 只能开方一次。

- `pow f`，将计数器 $x$ 变为 $x^f$，$f$ 可以为浮点数。

所有 $a_i$ 都必须给 $x$ 进行一次加或减或乘操作。

在运算过程中，$a_i$ 和 $x$ 的值均不能超过 $10^{10}$。题目保证有解，如有多种方案，输出一种即可。

本题精度要求较大，请提高算法的精度。

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

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

outputFormat:
第一行一个整数表示总操作数 $g$。

接下来 $g$ 行为你的操作序列。

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

- $x$ 加上 $a_1$，此时 $x$ 为 $3$。

- $x$ 加上 $a_2$，此时 $x$ 为 $6$。

- $x$ 减去 $a_3$，此时 $x$ 为 $3$。

- $x$ 减去 $a_4$，此时 $x$ 为 $0$。

- $x$ 加上 $a_5$，此时 $x$ 为 $3$。

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

- 将 $a_2$ 开根号，此时 $a=[1,\sqrt3,3]$。

- 将 $a_3$ 开根号，此时 $a=[1,\sqrt3,\sqrt3]$。

- $x$ 加上 $a_1$，此时 $x$ 为 $1$。

- $x$ 乘上 $a_2$，此时 $x$ 为 $\sqrt3$。

- $x$ 乘上 $a_3$，此时 $x$ 为 $3$。

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

- $x$ 加上 $a_1$，此时 $x$ 为 $4$。

- $x$ 加上 $a_2$，此时 $x$ 为 $9$。

- 将 $x$ 变为 $x^2$，此时 $x$ 为 $81$。

- 将 $x$ 减去 $a_3$，此时 $x$ 为 $77$。

### 数据规模与约定

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

- subtask 0（10 pts）：$n\leq 5$，$k=n^2$，保证可以使用加与减的运算得到解。

- subtask 1（20 pts）：$n \leq 5$，$k=n^2$，保证可以可以使用加、减、乘、开方运算得到解。

- subtask 2（15 pts）：$n \leq 10$，$a_i \leq 2$，$k=n+1$。

- subtask 3（55 pts）：$k=n+1$。

对于所有数据：$0 \leq n \leq 10^{5}$，$\sum_{i=1}^{n}{a_i} \le 10^{10}$，$0 \leq c\leq 10^{10}$。


title: 「MYOI-R3」字符串

description:
给定字符串 $s,t$。

现在你要在 $s,t$ 中删除一些字符并将它们重新排列使 $s=t$。

问操作后的 $|s|$（即字符串 $s$ 的长度）最大是多少？

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

第二行一个字符串 $t$。

outputFormat: 一行一个整数，表示操作后的 $|s|$ 的最大值。


title: 方差

background:
定义一个长度为 $n$ 的序列 $a$ 的方差为：

$$s^2=\frac{1}{n} \sum_{i=1}^n (a_i-\overline{a})^2$$

其中：$\sum$ 为累加求和符号，例如 $\sum_{i=1}^5 a_i=a_1+a_2+a_3+a_4+a_5$。$\overline{a}$ 为序列 $a$ 的平均数。

例如对于序列 $\{3,5,1,4,2\}$，$\overline{a}=3$，此时 $s^2=\frac{1}{n} \sum_{i=1}^n (a_i-\overline{a})^2=\frac{1}{5}[(3-3)^2+(5-3)^2+(1-3)^2+(4-3)^2+(2-3)^2]=2$。

description:
小 S 认为数学很简单，于是小 R 想要考考她。

小 R 给了小 S 一个序列 $a$，这个序列由 $m$ 段构成，第 $i$ 段被表示为 `l r b`，表示 $a_l,a_{l+1},\ldots,a_r$ 为 $b$，保证给出的任意两个区间不相交。

现在，小 R 有 $q$ 个问题。形如 `l r`，想让你查询区间 $[l,r]$ 的方差 $s^2$（需要注意：$l$ 可能等于 $r$，此时该段方差为 $0$）。

由于这个数字可能是个小数，小 R 不方便对答案，所以他想要小 S 求出 $(r-l+1)^2\cdot s^2\bmod 998244353$。可以证明 $(r-l+1)^2\cdot s^2$ 一定是整数。

作为小 S 的好朋友，你能帮帮她吗？

inputFormat:
第一行三个正整数 $n,m,q$，表示序列的长度，序列的段数和问题的个数。

接下来 $m$ 行，每行三个正整数，分别表示 $l_i,r_i,b_i$。

接下来 $q$ 行，每行两个正整数 $x,y$。你需要回答 $[x,y]$ 的方差。

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

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

序列 $a$ 为 $\{ 5, 7, 8, 8, 8 \}$。对于第 $12$ 组询问，区间 $[3, 5]$ 的平均数 $\overline{a} = 8$，方差 $s^2 = \frac{1}{3} [(8 - 8)^2 + (8 - 8)^2 + (8 - 8)^2] = 0$。

**【数据范围】**

- 对于 $20\%$ 的数据，保证 $n,q\leq 100$。
- 对于 $50\%$ 的数据，保证 $n\leq 10^6$，$m\leq 10^3$。
- 对于另外 $10\%$ 的数据，保证 $r_i-l_i\leq 1000$，$q \leq 10^4$。
- 对于另外 $10\%$ 的数据，保证 $m\leq 10^3$。

对于所有数据，保证：
- $1\leq l_i\leq r_i\leq n\leq 10^{18}$，$1\leq m\leq \min(n,2\times 10^5)$，$1\leq q\leq 2\times 10^5$，$1\leq x\leq y\leq n$，$1\leq b_i\leq 10^{18}$。
- 数据保证对于任意 $i<j$，$l_i<l_j$，且 $[l_i,r_i]$ 与 $[l_j,r_j]$ 不存在交集，即 $[l_i,r_i]\cap[l_j,r_j]=\varnothing$。
- 数据保证，若将所有的 $[l_i,r_i]$ 取并集，则其覆盖了 $[1,n]$ 上所有的正整数。即：$\bigcup_{i=1}^n[l_i,r_i] \cap \Z=[1,n] \cap \Z$。


title: 「RiOI-03」A Journey to the Moonlight（加强版）

background: 本题相较于 [P9919](/problem/P9919) 扩大了数据范围。

description:
对于一个右部点为 $m$ 个的二分图 $G$，定义它的权值 $w(G)$ 如下：

- 选择一种匹配方案，标记第一个已匹配的右部点。如果不存在这样的点，那么标记第一个未匹配的右部点。
- 每次随机选择一个 $1,2,\cdots,m$ 的排列，当未匹配的右部点与被标记的点 **按标号顺序作为一个子段出现在排列中时** 停止操作。
- $w(G)$ 为在所有匹配方案中操作次数期望的 **最小值**。

将这个二分图 $G$ 定义为 **$k$ 合法** 的，当且仅当：

- 所有左部点的度数在 $k\sim \color{red}2$ 之间。
- 没有任意两个左部点，与其相邻的点组成的集合相同。

定义 $f(k,x)$ 为所有右部点 $x$ 个，左部点不进行区分的 $k$ 合法二分图 $G$ 的 $w(G)$ 之和。

给定 $n,k,a_{0\sim n}$，求 $\sum\limits^n_ia_if(k,i) \bmod998244353$。

inputFormat:
一行两个正整数，分别表示 $n,k$。

第二行 $n+1$ 个非负整数，分别表示 $a_{0\sim n}$。

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


title: [语言月赛 202404] 非众数

description:
给定一个长度为 $n$ 的字符串 $s$，保证 $s$ 仅包含小写字母，求 $s$  的非空子串中非众数串的个数。

> **定义：非空子串**
>
> 用 $s_i$ 表示 $s$ 中的第 $i$ 个字符（$1 \leq i \leq n$）。任取两个整数 $i, j$（$1 \leq i \leq j \leq n$），将 $s_i, s_{i + 1}, \cdots, s_{j}$ 截取出来按原序排列作为一个新的字符串，则这个字符串叫做 $s$ 的非空子串。
例如，当 $s = \texttt{abcde}$ 时，$\texttt{ab}, \texttt{bcde}, \texttt{c}, \texttt{abcde}$ 都是 $s$ 的非空子串，而 $\texttt{acd}, \texttt{f}, \texttt{ngioasd}, \texttt{" "}$ 都不是 $s$ 的非空子串。

> **定义：非众数串**
>
> 若字符串 $a$ 中出现次数最多的字符出现的次数不超过 $\lfloor \frac{|a|}{2} \rfloor$，则称字符串 $a$ 为一个**非众数**串。其中 $\lfloor x \rfloor$ 代表 $\leq x$ 的最大整数，$|a|$ 代表 $a$ 的长度。

inputFormat: 一行一个字符串，表示 $s$。

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


title: [语言月赛 202404] 道法考试

background: 你正在参加一场道法考试。这次的道法考试题目全部都是问答题。

description:
有 $n$ 道题目，每道题标准答案都是 $m$ 个整数，代表答案包含的知识点的编号。

而你对于第 $i$（$1 \leq i \leq n$）道题的作答是 $l_i$ 个整数，代表作答的知识点编号。

对于每一道题 $i$，如果你作答的 $l_i$ 个整数包含了这道题对应的所有 $m$ 个整数，则得两分；否则，这道题得零分。

**注意：即使你的作答中包含标准答案里没有的知识点，也不会影响评分。评分依据有且仅有上一行这一条。**

求这场考试中你最后得到的总分数。

inputFormat:
第一行两个整数 $n$ 和 $m$，含义见题面。

第 $2 \sim n+1$ 行每行 $m$ 个整数，第 $i$ 行的内容表示第 $i-1$ 题标准答案包含的知识点编号，保证单个题目的知识点编号没有重复，用空格隔开。

第 $n+2 \sim 2n+1$ 行每行有 $l_i + 1$ 个整数。第一个整数为 $l_i$，接下来的 $l_i$ 个整数表示你作答的知识点编号。

outputFormat: 一行一个整数，表示你的分数。


title: 「QFOI R2」钟声远带斜阳

description:
**注意：本题中的所有数列下标从 $0$ 开始。**

小 R 是一个可爱的女孩子，她喜欢研究无穷数列。

她称一个无穷数列 $b$ 是美妙的，当且仅当存在自然数 $k_0$，使得对于所有 $k\ge k_0$，都满足 $b$ 中下标在区间 $[k_0,k]$ 内的所有数的和非负（即 $\sum_{i=k_0}^kb_i\ge 0$）。例如，数列 $\alpha_i=i-5$ 是美妙的，取 $k_0=5$ 符合要求；但 $\beta_i=-i$ 不是美妙的。

她目前只有一个长度为 $n$ 的有穷数列 $a$，可以进行任意次以下三种操作：

1. 花费 $p$ 的代价，选择一个整数 $i$（$0\le i < n$），将 $a_i$ 增加一。
1. 花费 $q$ 的代价，选择一个整数 $i$（$0\le i < n$），将 $a_i$ 删除，同时更新 $n$ 为新的数列长度。**不能将数列删空。**
1. 花费 $r$ 的代价，选择两个整数 $i,j$（$0\le i < j < n$），交换 $a_i$ 与 $a_j$。

她希望在若干次操作后，用无限个有穷数列 $a$ 依次相接得到无穷数列 $b$（即 $b_i=a_{i\bmod n}$），使得 $b$ 是美妙的。请你求出最小的代价。

inputFormat:
第一行四个整数 $n,p,q,r$。

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

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

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

花费 $p=1$ 的代价将 $a_3$ 增加一，得到数列 $b=[2,-2,3,-2,-1,2,-2,3,-2,-1,\cdots]$ 是美妙的，取 $k_0=2$ 符合要求。

可以证明不存在代价更小的方案。

---

**样例 $2$ 解释**

花费 $q=1$ 的代价将 $a_1$ 删除，得到数列 $b=[2,3,-3,-1,2,3,-3,-1,\cdots]$ 是美妙的，取 $k_0=0$ 符合要求。

可以证明不存在代价更小的方案。

---

**数据范围**

**本题采用捆绑测试。只有通过子任务中所有测试点以及所有依赖的子任务，才能获得相应的分数。**

对于全部数据：$1\le n\le 10^5$，$1\le p,q,r\le 10^9$，$|a_i|\le 10^9$。

- 子任务一（$10$ 分）：$n=1$。
- 子任务二（$10$ 分）：$n\le 10$。依赖子任务一。
- 子任务三（$20$ 分）：$|a_i|\le 1$。
- 子任务四（$20$ 分）：$\sum|a_i|\le 10^5$。依赖子任务三。
- 子任务五（$40$ 分）：无特殊限制。依赖子任务一、二、三、四。


title: 『STA - R7』异或生成序列

description:
对于一个 $1 \sim n$ 的排列 $\{p_n\}$，定义其异或生成序列为一个长度为 $n - 1$ 的非负整数序列 $\{b_{n - 1}\}$，按如下方式生成：

$$b_i = p_i \operatorname{xor} p_{i + 1}$$

其中 $\operatorname{xor}$ 代表按位异或运算。在 C++ 语言中由 `^` 运算符表示。

给定 $n, \{b_{n - 1}\}$，你需要构造一个对应的排列 $\{p_n\}$。

输入数据保证有解，如果存在多个解，输出任意一个即可。

inputFormat:
**本题单个测试点内含有多组测试数据。**

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

对于每组测试数据，

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

- 第二行 $n - 1$ 个非负整数，代表异或生成序列 $\{b_{n - 1}\}$。

outputFormat: 对于每组测试数据，输出一行 $n$ 个正整数，代表一个对应的排列 $\{p_n\}$。如果存在多个解，输出任意一个即可。

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

对于第一组测试数据，我们有：

- $b_1 = p_1 \operatorname{xor} p_2 = 2 \operatorname{xor} 3 = 1$
- $b_2 = p_2 \operatorname{xor} p_3 = 3 \operatorname{xor} 1 = 2$
- $b_3 = p_3 \operatorname{xor} p_4 = 1 \operatorname{xor} 4 = 5$

因此得到的 $b$ 序列和输入中的相同，进而该排列符合要求。

对于第二组测试数据，$[4,5,2,1,3,6]$ 也是一个符合要求的排列。

**【数据范围】**

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

对于 $100\%$ 的数据：

- $2 \le n \le 2 \times 10^6$；
- $1 \le T \le 10^6$；
- $\sum n \le 2 \times 10^6$;
- 保证至少存在一个合法的解。

具体部分分分配如下：

|Subtask 编号|数据范围|分值|
|:--------:|:--------:|:--------:|
|1|$\sum n^2 \le 2 \times 10^6$|$17$|
|2|$2 \nmid n$|$23$|
|3|$4 \mid n$|$26$|
|4|无特殊限制|$34$|

**【提示】**

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


title: [GESP样题 七级] 最长不下降子序列

description:
小杨有个包含 $n$ 个节点 $m$ 条边的有向无环图，其中节点的编号为 $1$ 到 $n$。

对于编号为 $i$ 的节点，其权值为 $w_i$。对于图中的一条路径，根据路径上的经过节点的先后顺序可以得到一个节点权值的序列，小杨想知道图中所有可能序列中最长不下降子序列的最大长度。

注：给定一个序列 $S$，其最长不下降子序列 $S'$ 是原序列中的如下子序列：整个子序列 $S'$ 单调不降，并且是序列中最长的单调不降子序列。例如，给定序列 $S = [11,12,13,9,8,17,19]$，其最长不下降子序列为 $S'=[11,12,13,17,19]$，长度为 $5$。

inputFormat:
第一行包含两个正整数 $n,m$，表示节点数和边数。

第二行包含 $n$个正整数 $A_1, A_2, \dots A_n$，表示节点 $1$ 到 $n$ 的点权。

之后 $m$ 行每行包含两个正整数 $u_i, v_i$，表示第 $i$ 条边连接节点 $u_i$ 和 $v_i$，方向为从 $u_i$ 到 $v_i$。

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


title: [UESTCPC 2024] 消消乐

description:
bjh 有一个长度为 $n$ 的只由字符 ```0``` 和 ```1``` 构成的字符串 $s$。

bjh 的每次操作可以选择一个长度**大于 1** 的极大的只包含一种字符的子串，将这一整个子串修改为与其中字符相反的一个字符（如 $11001$ 一次操作后可以改为 $0001$ 或 $1111$）。

bjh 会一直操作下去，直到字符串无法再被操作，请帮他找到所有操作方案中最大操作次数和最小操作次数的差值。

inputFormat:
本题包含多组数据。第一行输入一个整数 $T$ $(1\leq T\leq 10^4)$，表示数据组数。

对于每组数据，第一行输入一个整数 $n$ $(1\leq n\leq 10^5)$，表示字符串的长度。

第二行输入一个字符串 $s$，表示初始的字符串。

保证所有数据的 $n$ 之和不超过 $10^6$。

outputFormat: 对于每组数据，输出一个整数，表示最大操作次数和最小操作次数的差值。


title: [UESTCPC 2024] 操作序列

description:
给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$。

你需要选定一个整数 $k$ $(1\leq k\leq n)$，然后对序列进行任意次操作，每次操作可以选择序列中 $k$ 个不同的位置，使得这些位置的数乘上一个相同的非零整数，最终使得序列中所有的数相等。

输出满足条件的 $k$ 的最大值。

inputFormat:
本题包含多组数据。第一行输入一个整数 $T$ $(1\leq T\leq 10^4)$，表示数据组数。

对于每组数据，第一行输入一个整数 $n$ $(1\leq n\leq 10^5)$，表示序列的长度。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq 10^9)$，表示给定的序列。

保证所有数据的 $n$ 之和不超过 $10^6$。

outputFormat: 对于每组数据，输出一个整数，表示满足条件的 $k$ 的最大值。


title: [Opoi 2024] 简谐振动

background:
你说得对，但是简谐振动十分优美。

![pic](https://ts1.cn.mm.bing.net/th?id=OIP-C.uGsZxikgYriy7OYxJsbm0AHaD1&w=174&h=150&c=8&rs=1&qlt=90&o=6&pid=3.1&rm=2)

![cip](https://tse4-mm.cn.bing.net/th/id/OIP-C.yNecd9xmljOtND3V6b4gcAHaEW?w=278&h=180&c=7&r=0&o=5&pid=1.7)

![jzp](https://tse2-mm.cn.bing.net/th/id/OIP-C.GSxOJQ3KlXRC9V_y_crpigHaFj?w=230&h=180&c=7&r=0&o=5&pid=1.7)

但是我们不出多边形下海，所以你不需要维护一个质点的简谐振动。

description:
已知一个数字串 $S$，请你判断是否存在一种长度为 $n$ **且 $n$ 为奇数**的整数序列 $A_i$，使得 $A_1+A_2,A_2+A_3,\dots,A_{n-1}+A_n,A_n+A_1$ 的值按顺序依次拼接起来可以得到 $S$。

特别的，如果存在一种方案使得拼接的时候两项中间用 $[0,\infty)$ 个 $0$ 分隔仍然可以得到 $S$，该方案仍然合法。**所有数据保证最前面没有前导 $0$。**

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

接下来每组数据：

第一行一个整数 $n$。

第二行一个字符串 $S$。

outputFormat: 对于每组数据，如果有解，输出 `Yes`，否则输出 `No`，用换行符分隔。

hint:
### 样例解释
第一组样例解释：

$\begin{matrix}
7&6&4\cr
+&+&+\cr
6&4&7\cr
||&||&||\cr
13&10&11\end{matrix}$

当然，你也可以说：

$\begin{matrix}
71&60&-60\cr
+&+&+\cr
60&-60&71\cr
||&||&||\cr
131&0&11\end{matrix}$

构造方法不唯一。

第二组样例解释：

如果有解，$A_1=2.5$，而题目说了 $A$ 为整数序列，故无解。

第三组样例解释：

$\begin{matrix}
1&&1&0\cr
+&&+&+\cr
1&&0&1\cr
||&&||&||\cr
2&0&1&1\end{matrix}$

> 该方案中间用了 $1 \in [0,\infty)$ 个 $0$ 分隔，符合要求，输出 `Yes`。

---
### 数据范围
对于 $50\%$ 的数据，$1\le T \le 10$，$1\le |S| \le 10$，$1 \le n \le 3$。

对于 $100\%$ 的数据，$1\le T \le 100$。保证 $\sum n\le 10^6$ 且 $\sum|S|\le 10^6$，${\tt 0} \le S_i \le {\tt 9}$，**且 $n$ 为奇数**。


title: 「XSOI-R1」原神数

description:
原神数 $x$ 需要同时满足以下条件：

- $x$ 为质数。

- $x$ 的十进制位两两不同。

比如 $131$ 不是原神数，因为他的百位和个位相等；$42$ 也不是，因为不是质数；$17$ 就是一个原神数。

有 $q$ 次询问，现在要你求出 $l$ 到 $r$ 之间的原神数数量。

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

接下来 $q$ 行每行两个正整数 $l$，$r$。

outputFormat: $q$ 行 $q$ 个正整数，表示答案。

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

在 $100 \sim 140$ 之间的原神数有 $103,107,109,127,137,139$，共 $6$ 个。

### 数据规模与约定

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

- subtask 0（15 pts）：$1 \le l \le r \le 10^2$。

- subtask 1（15 pts）：$1 \le l \le r \le 10^4$。

- subtask 2（35 pts）：$1 \le l \le r \le 10^7$。

- subtask 3（35 pts）：$1 \le l \le r \le 10^{18}$。

对于所有数据，保证 $1 \leq l \leq r \leq 10^{18}$，$1 \leq q\leq 10^5$。


title: 「ALFR Round 1」D 小山的元力

description: 小山有 $n$ 个相同的元素，他想将这 $n$ 个元素分为 $m$ 堆，显然有很多种分法。对于每种分法，定义 $a_i$ 为第 $i$ 堆的元素数量，$b_i=i!\times a_i$（其中 $i!$ 表示 $i$ 的阶乘），以及 $c=\sum\limits_{i=1}^mb_i$。而小山的元力为所有分法的 $c$ 值之和。小山想知道他的元力是多少，由于答案可能很大，所以最终答案应对 $p$ 取模（保证 $p$ 为质数）。

inputFormat: 一行三个整数 $n,m,p$，含义见**题目描述**。

outputFormat: 一个数表示小山的元力。


title: 数据结构

background:
小 M 很喜欢数据结构。但是很遗憾，他没有进入省队。

人生有梦，各自精彩。

description:
给定两个长度为 $n$ 的序列 $a_i$ 和 $b_i$。有以下三种操作：

1. 给定区间 $[l,r]$ 以及参数 $k,t$，把区间内满足 $a_i\times b_i\leq k$ 的位置的 $a_i$ 和 $b_i$ 分别加上 $t$。
2. 给定 $i$ 和 $x,y$，将 $a_i$ 改为 $x$，$b_i$ 改为 $y$。
3. 查询区间内每个位置 $a_i+b_i$ 的和。

inputFormat:
第一行包含两个整数 $n,m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示 $a_i$。

第三行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示 $b_i$。

接下来 $m$ 行每行包含 $3$ 到 $5$ 个整数，表示一个操作，具体如下：

1. `1 l r k t`：将区间 $[l,r]$ 进行一操作。
2. `2 i x y`：将 $a_i$ 改为 $x$，$b_i$ 改为 $y$。
3. `3 l r`：输出区间 $[l,r]$ 内每个数的和。

outputFormat: 若干行，每行表示操作 $3$ 的答案。

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

第一次修改后，序列 $a_i$ 为：$\left\{23,4,4,4,8\right\}$；序列 $b_i$ 为 $\left\{54,29,8,2,3\right\}$。

第二次修改后，序列 $a_i$ 为：$\left\{23,7,4,4,8\right\}$；序列 $b_i$ 为 $\left\{54,9,8,2,3\right\}$。

**【数据范围】**

- 对于 $5\%$ 的数据，$n,m\le 5$；
- 对于 $10\%$ 的数据，$n,m\leq 100$；
- 对于 $25\%$ 的数据，$n,m\leq 5000$；
- 对于另外 $5\%$ 的数据，没有前两种操作；
- 对于另外 $10\%$ 的数据，没有第一种操作；
- 对于另外 $20\%$ 的数据，没有第二种操作；

对于所有数据，$1\leq n,m\leq 10^5$，$0\leq a_i,b_i,k,t,x,y\leq10^5$。


title: 考试

background: 人生有梦，各自精彩。

description:
有 $n$ 名同学去参加考试，考试有 $m$ 道题。

每个学生的实力是相同的，但是每道题的难度可能不同。第 $i$ 道题会有随机的 $a_i$ 名同学做错。

考试结束后，随机选出 $k$ 名同学，求出这些同学全部做对的概率。答案对 $998244353$ 取模。

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

第二行 $m$ 个整数，第 $i$ 个数表示 $a_i$。

outputFormat: 一个整数，表示答案取模后的结果。

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

随机选出 $2$ 名同学全部做对的概率为 $\frac{243}{25000}$，对 $998244353$ 取模后答案为 $793364682$。

可以证明答案一定为有理数。若不了解有理数取模，可以参照[【模板】有理数取余](https://www.luogu.com.cn/problem/P2613)。

**【数据范围】**

- 对于 $30\%$ 的数据，$1\leq n,m \leq 10$；
- 另外有 $10\%$ 的数据，$k=0$；
- 另外有 $20\%$ 的数据，$1 \leq n \leq 1000$，$1\leq m \leq 10^5$；

对于所有数据，保证 $1\leq n,m\leq 10^5$，$0\leq k,a_i\leq n$。


title: 「QFOI R2」树色尤含残雨

description:
小 R 是一个可爱的女孩子，她喜欢分解质因数。

她有一个正整数 $x$。每次操作可以选择 $p_1,\alpha_1,p_2,\alpha_2$ 满足 $p_1,p_2$ 为两不同质数且 $\alpha_1,\alpha_2$ 为正整数，若 $x$ 是 $p_1^{\alpha_1}p_2^{\alpha_2}$ 的整数倍，就将 $x$ 除以 $p_1^{\alpha_1}p_2^{\alpha_2}$，否则操作无效。

请你求出通过若干次操作可以得到的最小的 $x$。

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

outputFormat: 一个整数，表示可以得到的最小的 $x$。

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

无法进行任何有效操作。

---

**样例 $2$ 解释**

可以进行以下两次操作：

- 令 $p_1=2,\alpha_1=1,p_2=3,\alpha_2=1$，将 $x$ 除以 $p_1^{\alpha_1}p_2^{\alpha_2}=2^13^1=6$，得到 $x=20$。
- 令 $p_1=2,\alpha_1=2,p_2=5,\alpha_2=1$，将 $x$ 除以 $p_1^{\alpha_1}p_2^{\alpha_2}=2^25^1=20$，得到 $x=1$。

---

**数据范围**

**本题采用捆绑测试。只有通过子任务中所有测试点以及所有依赖的子任务，才能获得相应的分数。**

对于全部数据：$2\le x\le 10^9$。

- 子任务一（$10$ 分）：$x\le 10$。
- 子任务二（$20$ 分）：$x$ 为“无平方因子数”$^\dagger$。
- 子任务三（$20$ 分）：$x$ 为一个质数的正整数次幂。
- 子任务四（$20$ 分）：$x\le 10^5$。依赖子任务一。
- 子任务五（$30$ 分）：无特殊限制。依赖子任务一、二、三、四。

$\dagger$ 称一个数 $x$ 为“无平方因子数”，当且仅当不存在大于一的整数 $k$，使得 $x$ 是 $k^2$ 的整数倍。


title: [GESP样题 八级] 小杨的旅游

description:
小杨准备前往 B 国旅游。

B 国有 $n$ 座城市，这 $n$ 座城市依次以 $1$ 至 $n$ 编号。城市之间由 $n-1$ 条双向道路连接，任意两座城市之间均可达（即任意两座城市之间存在可达的路径）。

小杨可以通过双向道路在城市之间移动，通过一条双向道路需要 $1$ 单位时间。

B 国城市中有 $k$ 座城市设有传送门。设有传送门的城市的编号依次为 $b_1,b_2, \cdots ,b_k$。小杨可以从任意一座设有传送门的城市花费 $0$ 单位时间前往另一座设有传送门的城市。

注：如果两座设有传送门的城市之间存在双向道路，那么小杨可以选择通过双向道路移动，也可以选择通过传送门传送。

小杨计划在 B 国旅游 $q$ 次。第 $i$ 次旅游（$1 \le i \le q$），⼩杨计划从编号为 $u_i$ 的城市前往编号为 $v_i$ 的城市，小杨希望你能求出所需要的最短时间。

inputFormat:
第一行包含三个正整数 $n,k,q$，分别表示 B 国的城市数量，设有传送门的城市数量，以及小杨计划在 B 国旅游的次数。
接下来 $n-1$ 行，每行包含两个正整数 $x_i, y_i$，表示一条双向道路连接的两座城市的编号。
第 $n + 1$ 行包含 $k$ 个正整数，表示设有传送门的城市的编号。
接下来 $q$ 行，每行包含两个正整数 $u_i,v_i$，表示小杨第 $i$ 次旅游行程的起点城市编号与终点城市编号。

outputFormat: 输出共 $q$ 行。第 $i$ 行（$1 \leq i \leq q$）输出一个非负整数，表示小杨计划第 $i$ 次旅游从编号为 $u_i$ 的城市前往编号为 $v_i$ 的城市所需要的最短时间。


title: [UESTCPC 2024] 打字

description:
给定一颗 $n$ 个节点的 trie 树，以 $1$ 号节点为根，其余每个节点到父亲的边上都有一个字符，且父亲相同的节点到父亲的边上的字符互不相同。从根到每个节点的路径都代表一个单词，这个单词由路径上的字符顺序拼接而成。在每个节点 $i$ 处有一个权值 $c_i$，表示该节点所代表的单词需要写出的次数。

你有一个 cache，可以选择任意个单词放在 cache 里面。写单词时，每写一个字符需要花费 $a$ 的代价。当写出一个完整的单词时，就可以选择结束当前单词，转而拼写下一个单词。而 cache 会根据当前已经写出的字符，把 cache 中以这一部分字符为前缀且字典序最小的单词提示出来。此时你可以花费 $b$ 的代价直接写出这个单词，**并结束当前单词的拼写**，转而拼写下一个单词。注意一个字符串本身也看作它自己的前缀。

求完成 trie 树上所有单词的拼写所需的最小代价。

inputFormat:
第一行输入三个整数 $n,a,b$ $(1\leq n\leq 2\times 10^5,0\leq a,b\leq 10^4)$，分别表示 trie 树的大小、写一个字符的代价和使用 cache 写出单词的代价。

接下来 $n$ 行，其中第 $i$ 行首先输入两个整数 $c_i,k_i$ $(0\leq c_i\leq 10^4,0\leq k_i<n)$，分别表示第 $i$ 个节点上的权值和第 $i$ 个节点的儿子节点的个数。接下来输入 $k_i$ 个整数 $son_{i,1},son_{i,2},\ldots,son_{i,k_i}$，表示第 $i$ 个节点的儿子节点编号，按照第 $i$ 个节点到儿子节点的边上的字符之间的字典序从小到大依次给出。

保证 $c_1=0$。

outputFormat: 输出一行一个整数，表示完成 trie 树上所有单词的拼写所需的最小代价。

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

假设每个节点的子节点按字典序从小到大按 $a,b,\ldots$ 编码。最优方案为将 $aa$ 放在 cache 中，于是 $aa$ 可以花费 $3\times 4$
的代价利用提示打出来，$a$ 和 $b$
都直接打出来。总代价为 $3\times 4+2\times 1\times 2+2\times 1\times 3=22$。


title: [UESTCPC 2024] 2-聚类算法

description:
Alice 和 Bob 是两只 $k$ 维空间中的生物。在他们生活的空间中，分布着 $2n$ 个特征点，其中第 $i$ 个特征点的坐标为 $(x_{i,1},x_{i,2},\ldots,x_{i,k})$。

在这个空间中，两点之间的距离被定义为它们之间的曼哈顿距离（即点 $i$ 与点 $j$ 之间的距离 $\text{dist}_{i,j}=\sum_{p=1}^{k}|x_{i,p}-x_{j,p}|$）。

Alice 和 Bob 需要收集这些特征点。他们轮流从这 $2n$ 个点中选走一个点，已经被选走的点不能被再次选走。Alice 先手。Alice 会将她选走的点放入集合 $S_1$，而 Bob 会将他选走的点放入集合 $S_2$。

设一个集合的价值 $\text{val}(S)$ 为其中两两点之间的距离之和。Alice 希望最大化 $\text{val}(S_1)-\text{val}(S_2)$，而 Bob 希望最小化 $\text{val}(S_1)-\text{val}(S_2)$。

若 Alice 和 Bob 都采取最优策略，请你求出最终 $\text{val}(S_1)-\text{val}(S_2)$ 的值会是多少？

inputFormat:
第一行输入两个整数 $n,k$ $(1\leq n,k\leq 10^5,n\times k\leq 10^5)$，分别表示特征点的数量的一半和空间的维度数量。

接下来 $2n$ 行，每行 $k$ 个整数 $x_{i,1},x_{i,2},\ldots,x_{i,k}$ $(-10^8\leq x_{i,j}\leq 10^8)$，表示第 $i$ 个特征点的坐标。

outputFormat:
输出一个整数，表示 Alice 和 Bob 都采取最优策略的情况下 $\text{val}(S_1)-\text{val}(S_2)$ 的值。

“两两点之间的距离之和”对于每一个无序对只计算一次。


title: 「QFOI R2」寺秋山霭苍苍

description:
小 R 是一个可爱的女孩子，她的几何太差了，于是她向你求助这道几何题。

在平面直角坐标系中，有一个 $\triangle\textrm{ABC}$，其顶点坐标为 $\textrm{A}(x_1,y_1),\textrm{B}(x_2,y_2),\textrm{C}(x_3,y_3)$。

对于**实数** $p\in(0,1)$，在 $\textrm{BC},\textrm{CA},\textrm{AB}$ 边上分别取点 $\textrm{D},\textrm{E},\textrm{F}$，使得 $\frac{|\textrm{AF}|}{|\textrm{AB}|}=\frac{|\textrm{BD}|}{|\textrm{BC}|}=\frac{|\textrm{CE}|}{|\textrm{CA}|}=p$，则称 $\triangle\textrm{DEF}$ 为 $\triangle\textrm{ABC}$ 的“$p$ 比例三角形”。

请在 $[l,r]$ 范围内选择实数 $p$，使得 $\triangle\textrm{ABC}$ 的“$p$ 比例三角形”的面积最小。你需要求出这个面积。

outputFormat:
一行一个**实数** $S_{\min}$，表示最小面积。

你的输出被认为是正确的，当且仅当其与标准答案的绝对或相对误差不超过 $10^{-4}$。

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

可以证明，当 $p=0.5$ 时面积最小，为 $2.5$。

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

---

**样例 $2$ 解释**

可以证明，当 $p=0.4$ 时面积最小，为 $2.8$。

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

---

**评分方式**

本题采用自定义校验器（Special Judge）进行评测。

你的输出被认为是正确的，当且仅当其与标准答案的绝对或相对误差不超过 $10^{-4}$。

---

**数据范围**

**本题采用捆绑测试。只有通过子任务中所有测试点以及所有依赖的子任务，才能获得相应的分数。**

对于全部数据：$0 < l < r < 1$，$0\le x_1,y_1,x_2,y_2,x_3,y_3\le 10^5$，保证输入构成三角形，所有实数的小数点后位数不超过 $2$。

- 子任务一（$20$ 分）：$l=0.10,r=0.90$。
- 子任务二（$20$ 分）：$x_1=y_1=y_2=x_3=0.00$。
- 子任务三（$20$ 分）：$x_1=y_1=y_2=0.00$。依赖子任务二。
- 子任务四（$40$ 分）：无特殊限制。依赖子任务一、二、三。

---

**提示**

本题可能用到的公式：

两点间的距离公式：$(x_1,y_1),(x_2,y_2)$ 之间的距离为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。

海伦公式：若三角形三边长为 $a,b,c$，设半周长 $p=\frac{a+b+c}{2}$，则三角形面积为 $S=\sqrt{p(p-a)(p-b)(p-c)}$。


title: [UESTCPC 2024] Add

description:
给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$，初始时 $a_i=i$。对该序列进行 $n-1$ 次操作，其中第 $i$ 次操作为在 $[1,n-i]$ 中等概率选择一个整数 $j$，令 $a_j$ 变为 $a_j+2a_{n-i+1}$。

求操作完毕后 $a_1$ 的期望 $\bmod\text{ }998244353$ 的值。

inputFormat:
输入第一行一个正整数 $T$ $(1\leq T\leq 10^4)$，表示数据组数。

接下来 $T$ 组数据，每组一行一个正整数 $n$ $(1\leq n\leq 10^9)$，表示序列的长度。

outputFormat: $T$ 行，每行一个整数表示 $a_1$ 的期望 $\bmod\text{ }998244353$ 的值。


title: [GESP202403 一级] 小杨买书

description: 小杨同学积攒了一部分零用钱想要用来购买书籍，已知一本书的单价是 $13$ 元，请根据小杨零用钱的金额，编写程序计算可以购买多少本书，还剩多少零用钱。

inputFormat: 输入一个正整数 $m$，表示小杨拥有的零用钱数。

outputFormat: 输出包含两行，第一行，购买图书的本数；第二行，剩余的零用钱数。

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

对全部的测试数据，保证 $0 < m < 200$。


title: [GESP202403 一级] 找因数

description:
小 A 最近刚刚学习了因数的概念，具体来说，如果一个正整数 $a$ 可以被另一个正整数 $b$ 整除，那么我们就说 $b$ 是 $a$ 的因数。

请你帮忙写一个程序，从小到大输出正整数 $a$ 的所有因数。

inputFormat: 输入一行一个正整数 $a$。保证 $a\leq1000$。

outputFormat: 输出若干行，为 $a$ 的所有约数，从小到大排序。


title: [GESP202403 二级] 乘法问题

description:
小 A 最初刚刚学习了乘法，为了帮助他练习，我们给他若干个正整数，并要求他将这些数乘起来。

对于大部分题目，小 A 可以精确地算出答案，不过，若这些数的乘积超过 $10^6$，小 A 就不会做了。

请你写一个程序，告诉我们小 A 会如何作答。

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

接下来 $n$，每行一个整数 $a$。小 A 需要将所有的 $a$ 乘起来。

outputFormat: 输出一行，如果乘积超过 $10^6$，则输出 `>1000000`；否则输出所有数的乘积。

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

对全部的测试数据，保证 $1 \leq n \leq 50$，$1 \leq a \leq 100$。


title: [GESP202403 二级] 小杨的日字矩阵

description:
小杨想要构造一个 $N\times N$  的日字矩阵（$N$ 为奇数），具体来说，这个矩阵共有 $N$ 行，每行 $N$ 个字符，其中最左列、最右列都是 `|`，而第一行、最后一行、以及中间一行（即第 $\frac{N+1}{2}$ 行）的第 $2\sim N-1$ 个字符都是 `-` ，其余所有字符都是半角小写字母 `x` 。例如，一个 $N = 5$ 日字矩阵如下:

```
|---|
|xxx|
|---|
|xxx|
|---|
```

请你帮小杨根据给定的 $N$ 打印出对应的“日字矩阵”。

inputFormat: 一行一个整数 $N$（$5\leq N \leq 49$，保证 $N$ 为奇数）。

outputFormat:
输出对应的“日字矩阵”。

请严格按格式要求输出，不要擅自添加任何空格、标点、空格等任何符号。你一个恰好输出 $N$ 行，每行除了换行符外恰好包含 $N$ 个字符，这些字符要么是 `-`，要么是 `|`，要么是 `x`。**你的输出必须和标准答案完全一致才能得分，请在提交前仔细检查**。


title: [GESP202403 三级] 字母求和

description:
小杨同学发明了一种新型密码，对于每一个小写英文字母，该小写字母代表了一个正整数，即该字母在字母顺序中的位置，例如字母 `a` 代表了正整数 $1$，字母 `b` 代表了正整数 $2$；对于每一个大写英文字母，该大写字母代表了一个负整数，即该字母的 ASCII 码的相反数，例如字母 `A` 代表了负整数 $-65$。小杨同学利用这种放缩对一个整数进行了加密并得到了一个由大写字母和小写字母组成的字符串，该字符串中每个字母所代表数字的总和即为加密前的整数，例如 `aAc` 对应的加密前的整数为 $1+(-65)+3=-61$。

对于给定的字符串，请你计算出它对应的加密前的整数是多少。

inputFormat:
第一行一个正整数 $n$，表示字符串中字母的个数。
第二行一个由大写字母和小写字母的字符串 `T`，代表加密后得到的字符串。

outputFormat: 输出一行一个整数，代表加密前的整数。

hint: 对全部的测试数据，保证 $1 \leq n \leq 10^5$。


title: [UESTCPC 2024] 黑白珠串

description:
你是宽窄巷子里的一位手艺人。这天，顾客向你订购一条黑白珠串。黑白珠串形如一条链，其上排列着黑色和白色的珠子。顾客还向你提出了 $k$ 个条件，每个条件如下：

- 给定 $x,y$，要求黑白珠串中存在至少一个子串，满足子串的长度为 $x$，且恰好包含 $y$ 个黑珠。

这里，子串指黑白珠串中的一段连续的珠子。

请你为顾客构造出符合以上所有条件的黑白珠串，且满足珠串的长度最小。为了保证你构造的珠串满足上述条件，你还要对于每个条件，给出一个满足条件的子串的位置。

inputFormat:
第一行包含一个整数 $k$ $(1\leq k\leq 10^5)$，表示条件的数量。

接下来 $k$ 行，其中第 $i$ 行包含两个整数 $x_i,y_i$ $(1\leq x_i\leq 10^6,0\leq y_i\leq x_i)$，表示条件的内容。

outputFormat:
第一行一个整数 $l$，表示满足条件的黑白珠串的最小长度。

第二行一个由 ```0``` 和 ```1``` 构成的字符串，满足该字符串长度为 $l$，表示你构造的黑白珠串。其中 ```0``` 代表白珠，```1``` 代表黑珠。

接下来 $k$ 行，其中第 $i$ 行包含一个整数 $p_i$，表示满足第 $i$ 个条件的一个子串在珠串中的起始位置。这里令珠串的位置编号从 $0$ 开始。


title: 「CMOI R1」mex1

background:
小 U 对于从一个集合映射到一个数的函数很感兴趣，而 $\text{mex}$ 是一个很好的例子。

$\text{mex}(S)$ 指的是在集合 $S$ 中没有出现过的最小非负整数。

description:
多组数据。

每组数据，给定 $c$，要求构造序列 $a_1,a_2,...,a_n\in [0,2\times 10^9]$ 满足

$$\sum\limits_{S\neq \emptyset,S\subseteq \{1,2,...,n\}}\text{mex}(a_{S_1},a_{S_2},...,a_{S_{|S|}})=c$$

其中要求 $1\le n\le40$。可以证明在该题的数据范围内如果存在解，则在 $1\le n\le 40$ 时一定存在解。

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

之后 $T$ 行每行一个非负整数 $c$。

outputFormat:
对于每组数据：

如果无解，则仅输出一行一个整数 $-1$。

否则，第一行输出一个正整数 $n$。

第二行输出 $n$ 个非负整数 $a_1,a_2,...,a_n$。


title: 「QFOI R2」水落溪流浅浅

description:
小 R 是一个可爱的女孩子，某天晚上 $23$ 点她在提交作业时，发现截止时间是当天凌晨 $0$ 点。为了避免悲剧再次发生，她向你介绍“$30$ 小时制”。

$30$ 小时制的一天长度依然为 $24$ 小时，只是每天的时间范围从 $00:00\sim 23:59$ 变成了 $06:00\sim 29:59$。其中，对于 $24$ 小时制下在 $06:00\sim 23:59$ 之间的时间，其表示方式不变，而到了次日 $00:00$ 以后，保持日期不变，时间的小时部分继续增加，直到到达次日 $06:00$。

例如，下表是一些时间的对应关系：

|$24$ 小时制|$30$ 小时制|
|:-:|:-:|
|$2024$ 年 $2$ 月 $13$ 日 $06:00$|$2024$ 年 $2$ 月 $13$ 日 $06:00$|
|$2024$ 年 $2$ 月 $13$ 日 $12:00$|$2024$ 年 $2$ 月 $13$ 日 $12:00$|
|$2024$ 年 $2$ 月 $13$ 日 $18:00$|$2024$ 年 $2$ 月 $13$ 日 $18:00$|
|$2024$ 年 $2$ 月 $14$ 日 $00:00$|$2024$ 年 $2$ 月 $13$ 日 $24:00$|
|$2024$ 年 $2$ 月 $14$ 日 $05:59$|$2024$ 年 $2$ 月 $13$ 日 $29:59$|
|$2024$ 年 $2$ 月 $14$ 日 $06:00$|$2024$ 年 $2$ 月 $14$ 日 $06:00$|

现给定一个 $24$ 小时制时间，请将其转化为 $30$ 小时制。

由于小 R 也认为闰年处理很烦，因此你不需要告诉她日期，只需要告诉她时间即可。

inputFormat: 一行一个字符串，格式为 `hh:mm`，表示一个 $24$ 小时制时间。特别地，若小时和分钟不足两位数，会补前导零至两位。

outputFormat: 一行一个字符串，格式为 `hh:mm`，表示对应的 $30$ 小时制时间。若小时和分钟不足两位数，你同样需要补前导零至两位。你不需要考虑日期是否变化。

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

$14:00$ 属于 $06:00\sim 23:59$ 的范围，因此表示方式不变。

---

**数据范围**

本题不采用捆绑测试。

对于全部数据：保证输入为【输入格式】中约定合法的 $24$ 小时制时间。

---

**提示**

【题目描述】部分的表格提供了更多可供使用的样例。


title: [NOISG 2023 Qualification] Area

description:
Stuart 有 $n$ 个长方形，第 $i$ 个长方形长 $h_i$，宽 $w_i$。

长方形的面积是它所覆盖的区域的大小。Stuart 想请你帮他找到这 $n$ 个长方形中面积最大的一个的面积。

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

接下来 $n$ 行，每行两个整数 $h_i,w_i$，表示第 $i$ 个长方形的长和宽。

outputFormat: 一个整数，表示最大面积。


title: [NOISG 2023 Qualification] Swords

description:
YH 有 $n$ 把剑，第 $i$ 把剑的攻击力为 $a_i$，防御能力为 $b_i$。

对于一把剑 $i$，如果存在一个 $j(j \not = i)$，使得 $a_i\le a_j$ 且 $b_i\le b_j$，那么 YH 就认为这把剑是无用的。反之，他就认为这把剑是有用的。

在本题中，我们保证，不可能找到两把剑 $i,j$，使得 $a_i=a_j$ 且 $b_i=b_j$。

请你帮助 YH 求出这 $n$ 把剑中，有用的剑的数量。

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

接下来 $n$ 行，每行两个整数 $a_i,b_i$，表示第 $i$ 把剑形的攻击力和防御能力。

outputFormat: 一个整数，表示有用的剑**的数量**。


title: [SHUPC 2024] 栅栏密码

description:
栅栏密码（rail fence）是一种很基础的移位密码。

我们将明文 `Hello,World!` 按如下方式排列：

```
H...o...r
.e.l.,.o.l.!
..l...W...d
```

即把明文 `Hello,World!` 排列成若干个 `\/\/\/` 的形状，然后再逐行按从左到右的顺序取出字符，形成密文。例如第一行为 `Hor`，第二行为 `el,ol!`，第三行为 `lWd`，最终形成的密文为 `Horel,ol!lWd`。

若按上述方式排列的密文有 $h$ 行，则称该栅栏密码的高度为 $h$。

现在我们给出高度 $h$ 和一行密文字符串 $s$，请你输出一行明文字符串 $plain$。

inputFormat:
第一行读入一个数字 $h\ (2\le h \le10)$，表示密码的高度。

第二行读入一个字符串 $s\ (1\le |s| \le 10^5)$，表示密文。

outputFormat: 一个字符串 $plain$，表示明文。


title: [SHUPC 2024]  占地斗士！

background:
一个名为“占地斗士”的卡牌小游戏深深的吸引了小 A
。目前小 A 正在进行卡牌摆放练习，但是她并不熟练，于是想要请教擅长编程的你来解决这个问题。

description:
游戏的具体规则为：游戏在一个 $n\times m$ 的方格矩阵中进行，`.` 代表这个格子可以被放置，`#` 代表这个格子不能被放置。你手中有 $4$ 种形状各异的卡牌，每种卡牌均**只有一张**。你需要将卡牌放置在棋盘中，卡牌可以放置在任意位置，但是卡牌占领的格子不能重叠，也不能放在不能放置的格子上。目标是要使得卡牌占领的格子数量尽可能多。
小 A 现在想知道，在最优的摆放策略下，最多可以占领多少个格子？
![](https://cdn.luogu.com.cn/upload/image_hosting/l9d77whu.png)

inputFormat:
第一行输入两个正整数 $n,m\ (1 \le n,m\le10) $

接下来 $n$ 行，每行 $m$ 个字符串，保证字符仅包含 `.` 和 `#` ，代表棋盘的放置类型。

outputFormat: 输出一个整数，代表答案。

hint:
样例解释：

样例一最优摆放方法如下，使用第一种和第二种卡牌，最多可以占领 $9$ 个格子。

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

样例二最优摆放方法如下，使用第二种卡牌，最多可以占领 $4$ 个格子，红色代表这个格子不能放置卡牌。

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


title: [SHUPC 2024] 函数

description:
小 A 正在学习函数，有一天她发现了一个奇妙的函数：
$$
f(x)=x-0.5+\frac{\arctan(\cot(\pi x))}{\pi}
$$

她非常喜欢这个函数。现在，她会对你提出 $T$ 个询问，每个询问包含一个浮点数 $x$ ，而你只需要回答 $f(x)$ 的值是多少。

选手输出与标准答案的绝对误差或相对误差不超过 $10^{-6}$ 即视为正确。

inputFormat:
第一行一个整数 $T\ (T\le 10^4)$ 表示数据组数。

接下来 $T$ 行，每行一个浮点数 $x$ ，保证 $0 \le x \le 10^9$ 且 $x \notin \N$（即 $x$ 不为自然数）。

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

选手输出与标准答案的绝对误差或相对误差不超过 $10^{-6}$ 即视为正确。


title: [SHUPC 2024] 原神，启动！

description:
雷元素方碑具有如下性质：

1. 具有 $m$ 种状态，$0,1,\cdots,m-1$ 中的一种；
2. 方碑受到一次攻击会进入下一个状态（$m-1$ 的下一个状态是$0$）；
3. 某个方碑受到一次攻击时会带动其它一些方碑一起进入下一个状态。

当 $n$ 个方碑的状态相同时，解谜成功。但是小 A 觉得游戏里的方碑解谜太简单了，只需要使用刻晴的“斩尽牛杂”将元素方碑全部胡乱攻击一遍就能解谜成功，于是他开始思考更复杂的版本。

现在有 $n$ 个雷元素方碑，每个雷元素方碑有 $m$ 种状态。对于每个方碑 $i$ ，当它受到攻击时，都有 $k_i$ 个其它方碑和它一起进入下一个状态。

给定 $n$ 个雷元素方碑的初始状态 $s$ 和终止状态 $t$，请你计算需要分别攻击每个方碑多少下，才能将雷元素方碑从状态 $s$ 变换到 $t$。

如果无解请输出`niuza`。

inputFormat:
第一行读入两个正整数 $n,m\ (1\le n\le100,m\le10^9)$，**保证 $m$ 为素数**。

接下来 $n$ 行，第 $i$ 行会读取如下数据：

- 先读入一个数字 $k\ (0\le k<n)$，表示攻击该方碑会带动的方碑数。
- 接下来读入 $k$ 个数字，第 $j$ 个数 $a_j\ (1\le a_j \le n, a_j\neq i$ 且 $a_{j-1}<a_j)$ 表示 $i$ 方碑带动的方碑编号。

接下来两行：

第一行读入 $n$ 个数，第 $i$ 个数 $s_i$ 表示第 $i$ 个雷元素方碑的初始状态 $s_i\ (0\le s_i <m)$。

第二行读入 $n$ 个数，第 $i$ 个数 $t_i$ 表示第 $i$ 个雷元素方碑的终止状态 $t_i\ (0\le t_i <m)$。

outputFormat:
如果有解，输出 $n$ 个小于 $m$ 的数，分别表示应该攻击每个方碑多少次，用空格隔开。对于多个解，输出任意一个即可。

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


title: [SHUPC 2024] 为美好的世界献上爆焰！

background: 小 A 目前正在带着小 B 进行攻打魔王城的每日一爆演练。

description:
具体来说，魔王城的结界护盾共有 $x$ 的血量，小A想在 $n$ 天内完成对魔王城护盾的破坏。每天小 B 的魔力值会恢复至 $m$ ，且魔力值的上限为 $M$ ，使用爆裂魔法时每 $1$ 点魔力值可以对魔王城护盾造成 $1$ 点伤害。当然，爆裂魔法每天只能使用一次。

为了确保小 B 可以造成充足的伤害，小 A 每天可以花钱去商店购买魔晶石为小 B 增加魔力值。但是商店每天出售的魔晶石的数量、价格、和魔力值都有所不同。且当天出售的**魔晶石只能当天使用**，不然会过期，无法补充魔力。小A现在想知道，如果要小 B 能够顺利爆破魔王城的护盾，最少需要花费多少钱？（如果无法完成破坏，则输出 `-1`）

**注意**：由于小 B 的魔力值具有上限，因此当魔晶石魔力含量 $h$ 加上小 B 当前魔力值 $m$ 大于等于 $M$ 时，使用该魔晶石只能使小 B 的魔力值变为 $M$ ，也就是说 $ m'=\min(M,m+h)$ 。

inputFormat:
第一行输入四个正整数，$n,x,M,m$ （$1 \le n,x,M \le 5000,m \le M$）。

接下来会有 $n$ 组数据，每组数据有三行。

第一行代表第 $i$ 天出售的魔晶石数量 $\text{num}_i\ (1 \le \text{num} \le 5000)$ ，数据保证 $\sum_{i=1}^{n}\text{num}_i\le 5000$。

第二行共 $\text{num}_i$ 个正整数，代表第 $i$ 天出售的第 $j$ 个魔晶石的价格 $p_{i,j}\ (1\le p_{i,j} \le 10^9)$ 。

第三行共 $\text{num}_i$ 个正整数，代表第 $i$ 天出售的第 $j$ 个魔晶石的魔力值 $h_{i,j}\ (1 \le h_{i,j} \le M)$ ，数据保证 $\sum_{i=1}^{n}\sum_{j=1}^{\text{num}_i}h_{i,j}\le 5000$。

outputFormat: 输出一个整数，代表所求的答案。

hint:
样例解释：

样例 1 中，可以选择购买第一天的第一个魔晶石，花费为 $1$，当天总魔力值为 $8$。再购买第二天的第一个魔晶石，花费为 $1$，当天总魔力值为 $9$。这样两天总共可以造成 $17$ 点伤害，成功破坏结界，且花费最少为 $2$。

样例 2 中，因为存在魔力值上限，因此第一天最多造成 $10$ 点伤害，而第二天最多造成 $9$ 点伤害，因此无法破坏结界。


title: [SHUPC 2024] 小A的皇室战争卡组

description:
小 A 很喜欢玩皇室战争这款游戏。皇室战争的卡牌种类共有 $3$ 种，分别为部队、建筑和法术。一个卡组会携带 $8$ 张卡牌，一个合理的卡组会包含 $0\sim 1$ 张建筑牌、 $1\sim 3$ 张法术牌，部队牌则没有限制。每张卡牌都有自己独立的等级 $a_i$ 和种类 $c_i$。

现在小 A 想和 小 B 进行友谊战，因此需要来构建出战卡组。小 A 共有 $n$ 张卡牌，卡牌的类型与等级已知，且 小 B 的每张出战卡牌的等级已知。由于小 A 对自己的水平非常自信，因此只要 **出战卡牌的平均等级 $\ge$ 对手出战卡牌的平均等级 $-2$**，**且卡组为一个合理的卡组**，则他就能确保取胜。

现在请你帮小 A 想想，他可以确保取胜吗？

inputFormat:
第一行一个整数 $T\ (T\le 10^3)$ 表示数据组数。

每组第一行输入一个正整数 $n\ (8 \le n\le 10^5)$ ，代表 $小A$ 的卡牌总数，保证 $\sum n \le 10^5$

每组第二行输入 $n$ 个正整数，代表每张卡牌的种类 $c_i\ (1 \le c_i \le 3)$ ，其中种类 $1$ 代表部队卡，种类 $2$ 代表建筑卡，种类 $3$ 代表法术卡。

每组第三行输入 $n$ 个正整数，代表每张卡牌的等级 $a_i\ (1 \le a_i \le 15)$

每组第四行输入 $8$ 个正整数，代表 小 B 每张卡牌的等级 $x_i\ (1 \le x_i \le 15)$。

outputFormat: 共 $T$ 行，每行一个字符串。如果 $小A$ 可以取胜则输出 `Yes`，否则输出 `No`

hint:
样例解释：

在第一组样例中，小A可以取第1,2,3,6,7,8,9,10张卡牌，此时出战卡组的平均等级为6级，而小B的出战卡组平均等级为8级，$小A的平均等级 \ge 小B的平均等级-2$，因此小A可以确保胜利。

在第二组样例中，无论小A如何配置卡组都无法使平均等级满足条件，因此不能获胜。

在第三组样例中，小A无法配置出一个合理的卡组，因此也不能获胜。


title: [SHUPC 2024] 彭罗斯水槽

description:
小 A 在上课时出现了幻觉，他幻想出了若干个水槽，它们环形排列，每一个水槽里的水都会流向下一个水槽（当然在现实里这是不可能的）。

于是小 A 开始思考这样一个问题：

有 $n$ 个水槽环形排列，每个水槽都有一个容量，初始时水都是满的。接下来每一秒，水槽 $i$ 的水全部转移到 $i+1$ （特殊的，第 $n$ 个水槽的水会转移到第 $1$ 个），如果转移的水超出了容量就会溢出。

现在他想知道，在接下来的 $1$ 至 $n$ 秒内，每一秒所有水槽的水量总和。

inputFormat:
第一行读入一个正整数 $n\ (1\le n\le 10^5)$ ，表示水槽的个数。

第二行读入 $n$ 个数字，第 $i$ 个数字 $a_i\ (1\le a_i\le 10^9)$ 表示水槽 $i$ 的容量。

outputFormat: $n$ 个数字，用空格隔开。分别表示 $1$ 至 $n$ 秒，每一秒所有水槽的水量总和。


title: [UESTCPC 2024] 卡牌游戏

description:
李华有一副卡牌，每张卡牌有颜色、数字以及价值三个属性。每张卡牌的颜色可以用一个 $[1,n]$ 中的整数代表，同样的，每张卡牌上会写有一个 $[1,n]$ 之间的整数。根据数字和颜色的不同，这些卡牌被分为 $n^2$ 种。

为了方便表示，记一张颜色为 $x$，数字为 $y$ 的卡牌种类编号为 $(x-1)\times n+y$。在牌堆中，第 $i$ 种卡牌共有 $a_i$ 张，每张卡牌的价值为 $b_i$。

一开始，李华的手牌为空，初始积分为 $0$，李华会进行 $k$ 轮游戏。在每一轮的开始，李华会从牌堆里剩余的牌中**随机**取出一张牌，抽到每张牌的概率都是相等的。紧接着，如果手牌中含有与取出的牌数字**或**颜色相同的牌，那么李华会将**所有的**符合上述条件的牌加上原本取出的牌放回牌堆，反之则将抽出的牌置于手牌中。

每一轮结束后，李华的积分会加上其手牌中所有牌的价值，请帮李华求出 $k$ 轮后的期望总积分对 $998244353$ 取模后的值。

inputFormat:
第一行两个正整数 $n,k$ $(2\le n\le 4, 1\le k\le 10^9)$，代表颜色及数字的种类数和游戏轮数。

第二行为 $n^2$ 个整数 $a_i$ $(0\le a_i<998244353)$，代表牌堆里每种卡牌的数量。

第三行为 $n^2$ 个整数 $b_i$ $(0\le b_i<998244353)$，代表每种卡牌的积分。

数据保证不会出现所有卡牌可以同时置于手牌中的情况，且 $\sum a_i< 998244353$。

outputFormat: 输出一行一个整数，代表 $k$ 轮之后的总分期望值。


title: 【MX-X3-T7】「RiOI-4」Re：End of a Dream

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

（图片来自 phigros 曲绘，侵删。）

还是来谈点现实的吧。

身边的同学 NOI 拿了 Ag，APIO 捧了杯，省选啥的也比小 $\iiint$ 好。小 $\iiint$ 说，他的时间花在游戏上了。可看看隔壁提前招进高中的，florr 号里都有 Super Ant Egg 了。小 $\iiint$ 说，他网不好，实力发挥不出来。可再看隔壁 i wanna 大神，都开始速通 i wanna be the guy 了。小 $\iiint$ 争道，他也没打多久游戏，只是在专心文化课。但是成绩一拉出来，成了信竞班垫底。小 $\iiint$ 又说，可能是时间花在社交上了吧。大家都觉得他很幽默，因为他在班里一个朋友都没有。

小 $\iiint$ 不明白为什么会这样。

今年对于小 $\iiint$ 来说，可能就是他 OI 生涯的最后一年了。一年太短，能补救多少？能挽回多少？当年他刚学 OI 时，就暗暗地下定决心，要成为大家口中的“神犇”。三年过去，前途仍是一片昏暗。

这或许就是，$\color{#CD0000}\overset{\text{End of a Dream}}{\text{梦\ 的\ 终\ 结}}$。

也许，**梦是反着的吧。**

……

但是这里是梦熊周赛题目，不是出题人拿来写批话的地方，所以小 $\iiint$ 需要你做一道计数题。

description:
给定 $n,q$。现有一个初始为 $0$ 的整数 $m$。你需要支持以下操作：

- `0 x`：将 $m$ 加上 $2^x$。
- `1 x`：将 $m$ 减去 $2^x$。若 $m<2^x$，则忽略此操作。
- `2`：查询有多少长度为 $n$、每个数都在 $1\sim m$ 中的严格递增正整数序列，使得其前缀异或和与后缀异或和均严格递增。答案对 $998\,244\,353$ 取模。

其中，一颗序列 $a_1,a_2,\cdots,a_n$ 的**前缀异或和**是指序列 $s_1,s_2,\cdots,s_n$，满足 $s_i=\begin{cases}a_1&i=1\\a_{i}\oplus s_{i-1}&i\ge2\end{cases}$，而其**后缀异或和**是指序列 $t_1,t_2,\cdots,t_n$，满足 $t_i=\begin{cases}a_n&i=1\\a_{n-i+1}\oplus t_{i-1}&i\ge2\end{cases}$，其中 $x\oplus y$ 表示 $x$ 与 $y$ 的按位异或。

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

接下来 $q$ 行，每行表示一个操作。

outputFormat: 对于每个 `2` 操作，输出对应的答案对 $998\,244\,353$ 取模的值。


title: 「XSOI-R1」区间操作

background: 小 A 喜欢区间操作问题。

description:
小 A 给你了一个长度为 $n$ 的序列 $a$，并给你了 $q$ 组询问。

对于每组询问，小 A 会给你两个正整数 $l,r$，你需要求出 $(a_l) \oplus (a_l+a_{l+1}) \oplus (a_l+a_{l+1}+a_{l+2}) \oplus \dots \oplus (a_l + a_{l+1} + a_{l+2} + \dots + a_r)$ 的值。

其中 $\oplus$ 表示异或运算。

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

之后一行 $n$ 个整数 $a_i$，

之后 $q$ 行每行两个正整数 $l,r$。

outputFormat:
共 $q$ 行，

每行一个整数表示你的答案。

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

$1 \oplus (1 + 1) \oplus (1 + 1 + 4) \oplus (1 + 1 + 4 + 5) \oplus (1 + 1 + 4 + 5 + 1) \oplus (1 + 1 + 4 + 5 + 1 + 4) = 18$。

### 数据规模与约定

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

- Subtask 0（13 pts）：保证 $n,q \le 10^2$。

- Subtask 1（28 pts）：保证 $n,q \le 10^4$。

- Subtask 2（19 pts）：保证 $a_i \le 10^4$。

- Subtask 3（7 pts）：保证 $n \le 10^2$。

- Subtask 4（17 pts）：保证 $a_i$ 均为 $2$ 的非负整数次幂。

- Subtask 5（16 pts）：无特殊限制。

对于所有测试数据，$1 \le l \le r \le n \le 10^4$，$1 \le q \le 10^6$，$0 \le a_i \le 10^{10}$。

upd（2024.7.3）：添加一组 hack 数据，减少一组数据。


title: [GESP202403 三级] 完全平方数

description:
小杨同学有一个包含 $n$ 个非负整数的序列 $A$，他想要知道其中有多少对下标组合 $<i,j>$（$1 \leq i < j \leq n$），使得 $A_i + A_j$ 是完全平方数。

如果 $x$ 是完全平方数，则存在非负整数 $y$ 使得 $y \times y = x$。

inputFormat:
第一行一个非负整数 $n$，表示非负整数个数。
第二入行包含 $n$ 个非负整数 $A_1, A_2, \dots A_n$，表示序列 $A$ 包含的非负整数。

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

hint: 对全部的测试数据，保证 $1 \leq n \leq 1000$，$0 \leq A_i \leq 10^5$。


title: [GESP202403 四级] 相似字符串

description:
对于两个字符串 $A$ 和 $B$，如果 $A$ 可以通过删除一个字符，**或**插入一个字符，**或**修改一个字符变成 $B$，那么我们说 $A$ 和 $B$ 是相似的。

比如 $\texttt{apple}$ 可以通过插入一个字符变成 $\texttt{applee}$，可以通过删除一个字符变成 $\texttt{appe}$，也可以通过修改一个字符变成 $\texttt{bpple}$。因此 $\texttt{apple}$ 和 $\texttt{applee}$、$\texttt{appe}$、$\texttt{bpple}$ 都是相似的。但 $\texttt{applee}$ 并不能 通过任意一个操作变成 $\texttt{bpple}$，因此它们并不相似。

特别地，两个完全相同的字符串也是相似的。

给定 $T$ 组 $A,B$，请你分别判断它们是否相似。

inputFormat:
第一行一个正整数 $T$。
接下来 $T$ 行，每行两个用空格隔开的字符串 $A$ 和 $B$。

outputFormat: 对组 $A,B$，如果他们相似，输出 ``similar``，否则输出 ``not similar``。

samples:
5
apple applee
apple appe
apple bpple
applee bpple
apple apple

samples:
similar
similar
similar
not similar
similar

hint: 对全部的测试数据，保证 $1 \leq T \leq 100$，$A$ 和 $B$ 的长度不超过 $50$，仅含小写字母。


title: [THUWC 2020] 工资分配

description:
月末，一家公司的老板给公司内的 $k$ 个员工（他们被编号为 $1\sim k$）准备了一份工资的分配方案。这份方案可以用一个长度为 $k$ 的序列 $a$ 表示，其中 $a_i$ 表示第 $i$ 个人的工资。现在，这份分配方案放在办公室的桌上，无人看管。

一些员工决定通过替换的方式替换掉这份工资分配方案，来使得自己获得更多的工资。于是，一些员工自己准备了一个自行伪造、不会被老板察觉的分配方案 $b$（也是一个长度为 $k$ 的序列），并选择在一个时刻潜入办公室。他会偷看**当前**放在办公桌上的分配方案 $a^{'}$，如果该员工编号为 $i$ 且 $b_i > a^{'}_ i$，他就会把**整个分配方案**替换成 $b$。为了保证替换成功，一个员工可能会在多个时刻潜入办公室，并且可能会伪造不同的分配方案。但同一时刻最多有一个员工潜入办公室。

假设一天总共有 $n$ 个时刻有员工潜入，我们将这些时刻按时间顺序从 $1$ 到 $n$ 编号。现在，你知道了在每个时刻 $t$，潜入办公室的员工 $p_t$ 和他在 $t$ 时刻伪造的分配方案 $b_t$。现在给出 $q$ 个询问，每次询问会给出一个老板的初始分配方案，请你计算出最后放在桌面上的分配方案。

inputFormat:
第一行三个整数 $n$、$q$、$k$，表示时刻的个数、询问的个数和员工的个数；

接下来 $n$ 行，每行 $k+1$ 个整数 $p_t, b_{t,1},\cdots, b_{t_k}$，表示 $t$ 时刻潜入的员工和他准备的分配方案；

接下来 $q$ 行，每行 $k$ 个整数 $a_1, \cdots, a_k$，表示老板的初始分配方案。

outputFormat: 输出 $q$ 行，每行 $k$ 个整数，表示最后的方案。

hint:
**【子任务】**

存在 20% 的数据，$n,q\le 1,000$

存在另外 10% 的数据，$k=1$；

对于所有的数据，$n,q\le 10^5, k\le 20$。

**【提示】**

本题输入、输出规模较大，建议使用 `scanf/printf` 进行输入输出。如果使用 `cin/cout`，建议在 `main` 函数开头加上 `std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);`。


title: [THUWC 2020] Yazid 的棋

description:
给定一张包含 $n$ 个点、$m$ 条边的有向图，点标号从 $1$ 至 $n$，边标号从 $1$ 至 $m$。

这张图的主人 Yazid 将先后执行 $Q$ 次操作，每个操作的形式为：在一个节点 $x$ 放置一个棋子，并设定一个整数 $s$，同时该棋子不停地沿着**编号最小**的出边移动，其中当第 $i$ 条边被经过 $w_i$ 次后就会立刻从图中被删除。棋子会不停移动直到**无出边可走**或**棋子已移动了 $s$ 步**。对于最终棋子停留的节点，我们把它叫做这次操作的**终点**。做完这些后，Yazid 会将该棋子移出游戏。

你需要预测 Yazid 每次操作的终点编号。

需要注意的是，所有操作都是有后效性的。也就是说，在前 $Q-1$ 步操作时**消失的边**、**经过的次数**都**不会**在第 $Q$ 次操作时被重置，即下一步操作在上一步操作基础上进行。

inputFormat:
第一行两个用空格隔开的整数 $n,m$。

接下来 $m$ 行描述有向图。这部分中第 $i$ 行（$1\leq i\leq m$）包含三个用空格隔开的整数 $u_i,v_i,w_i$，描述一条 $u_i$ 到 $v_i$ 的经过 $w_i$ 次会被删除的有向边。

* 这里保证 $1\leq u_i,v_i\leq n$，$w_i\leq 10^{18}$。

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

接下来 $Q$ 行依次描述各操作，每行两个用空格隔开的整数 $x,s$，描述一个操作。

* 这里保证 $1\leq x\leq n$，$1\leq s\leq 10^{9}$。

outputFormat: 输出 $Q$ 行，每行一个整数，依次输出各操作的终点。其中第 $i$ 行输出的是第 $i$ 个操作的终点。

samples:
见附件中的 2.in。
见附件中的 2.ans。

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

第一次操作，棋子的移动步骤如下：

1. 在 $7$ 号节点放置一个棋子。
2. $7$ 号节点编号最小的出边是第 $7$ 条边，棋子通过该边移动到 $5$ 号节点。
3. $5$ 号节点编号最小的出边是第 $5$ 条边，棋子通过该边移动到 $2$ 号节点。
4. $2$ 号节点编号最小的出边是第 $3$ 条边，棋子通过该边移动到 $3$ 号节点。
5. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。
6. $1$ 号节点编号最小的出边是第 $2$ 条边，棋子通过该边移动到 $2$ 号节点。
7. $2$ 号节点编号最小的出边是第 $3$ 条边，棋子通过该边移动到 $3$ 号节点。此时，第 $3$ 条边已被经过了 $2$ 次，被从图中删去。
8. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。
9. 棋子停留在 $1$ 号节点，故 $1$ 号节点就是此次操作的终点。

第二次操作，棋子的移动步骤如下：

1. 在 $6$ 号节点放置一个棋子。
2. $6$ 号节点编号最小的出边是第 $4$ 条边，棋子通过该边移动到 $3$ 号节点。此时，第 $4$ 条边已被经过了 $1$ 次，被从图中删去。
3. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。此时，第 $1$ 条边已被经过了 $1$ 次，被从图中删去。
4. 棋子已移动了 $7$ 步，故停留在 $1$ 号节点，$1$ 号节点是此次操作的终点。

第三次操作，棋子的移动步骤如下：

1. 在 $6$ 号节点放置一个棋子。
2. $6$ 号节点已没有出边，故棋子只能停留在 $6$ 号节点，故 $6$ 号节点是此次操作的终点。

**【子任务】**

本题有多个子任务，每个子任务可能包含多个测试点，只有通过了一个子任务中的所有测试点才能得到该子任务的分数。

每个子任务的测试点满足一些特殊的限制，具体如下表：

|子任务编号|$n \le$|$m \le$|$Q \le$|$s \le$|$w \le$|性质|分值|
|----|----|----|----|----|----|----|----|
|1|$10^5$|$1.5 \times 10^5$|$5000$|$5000$|$10^{18}$|$0$|8|
|2|$10^5$|$1.5 \times 10^5$|$5000$|$10^9$|$5000$|$0$|8|
|3|$10^5$|$1.5 \times 10^5$|$10^5$|$10^9$|$10^{18}$|$1$|8|
|4|$10^5$|$1.5 \times 10^5$|$10^5$|$10^9$|$10^{18}$|$2$|$12$|
|5|$10^5$|$n - 1$|$10^5$|$10^9$|$10^{18}$|$3$|13|
|6|$10^5$|$n$|$10^5$|$10^9$|$10^{18}$|$4$|15|
|7|$10^5$|$n + 50$|$10^5$|$10^9$|$10^{18}$|$5$|8|
|8|$10^5$|$1.5 \times 10^5$|$10^5$|$10^9$|$10^{18}$|$0$|28|

对于所有测试点，保证 $1 \leq n\leq 10^5$，$1 \leq m\leq 1.5\times 10^5$，$1 \leq Q \leq 10^5$，$1 \leq s \leq 10^9$，$1 \leq w_i \leq 10^{18}$。

- 性质 0：无特殊性质；
- 性质 1：图为随机生成，每条边 $(u, v)$ 出现的概率为 $1 / n^2$；
- 性质 2：保证 $w_i = 10^{18}$；
- 性质 3：保证图构成了一棵有根树。
- 性质 4：保证图构成了一棵环套树。
- 性质 5：保证前 $n$ 条边构成了一棵环套树。


title: [THUWC 2020] 某科学的动态仙人掌

description:
题目名是吸引你点进来的。

给一棵边权为 $1$ 的树和一个常数 $X$，节点用 $1$ 到 $n$ 的整数表示。

定义 $dist(a,b)$ 为节点 $a,b$ 在树上的距离，即 $a$ 到 $b$ 的简单路径上的边权和，特别地，$dist(a,a) = 0$。

每次查询的时候给出一个区间 $[l,r]$，查询有多少个 $X$-块，定义如下：

对任意两个节点 $a,b$，定义 $a,b$ 是 $X$-连通的，当且仅当存在一个长为 $t$ 的节点序列 $\{v_i\}$，其中 $t$ 可以是任意正整数，满足：

1. $v_1=a$；
2. $v_t=b$；
3. 对任意 $1\le i\le t-1$，$dist(v_i,v_{i+1})\le X$；
4. 对任意 $1\le i\le t$，$l\le v_i\le r$。

定义“$X$-块”为一个点集 $S$，满足：

1. 对任意 $a$ 属于 $S$，$b$ 属于 $S$ 的补集且 $l\le b \le r$，$a,b$ 不是 X-连通的；
2. 对任意 $a,b$ 属于 $S$，$a$ 和 $b$ 是 X-连通的；
3. 对任意 $a$ 属于 $S$，有 $l\le a \le r$。

inputFormat:
第一行三个整数 $n$，$m$，$X$ 依次表示树的节点个数，询问次数，还有常数 $X$；

第二行共 $n-1$ 个整数 $p_2\;p_3\;\dots\;p_n$，表示对于 $2 \le i\le n$ 的整数 $i$，$i$ 和 $p_i$ 之间有一条无向边；

保证输入的数据构成一棵树；

之后 $m$ 行，每行两个整数 $l\;\;r$，表示这次询问的区间是 $[l,r]$，保证 $l \le r$；

保证 $1 \le n\le 3\cdot 10^5$，$1 \le m\le 6\cdot 10^5$。

outputFormat: 共 $m$ 行，依次回答各组询问：每行输出一行一个整数表示这组询问的答案。


title: [THUWC 2020] 报告顺序

description:
Yazid 今天要听 $n$ 个人做报告，方便起见，我们把这些人从 $1$ 至 $n$ 编号。

Yazid 有一个兴奋度，初始为 $s$，这个值会随着报告的进行而改变。

第 $i$ 个人（$1\leq i\leq n$）的报告可以用三个数 $a_i,b_i,c_i$ 来描述，这表示假设听他的报告前，Yazid 的兴奋度为 $x$，那么听完他的报告后，Yazid 的兴奋度将会变成 $a\lvert x\rvert+bx+c$。

Yazid 还要参加期末考试，因此他希望听完报告后尽可能兴奋。因此，你的任务是帮助 Yazid 安排确定所有人的报告顺序，使得 Yazid 在所有人报告完后兴奋度最大。

inputFormat:
第一行两个用空格隔开的整数 $n,s$。

接下来 $n$ 行描述 $n$ 个人的报告。这部分的第 $i$ 行为三个空格隔开的整数 $a_i,b_i,c_i$。

outputFormat: 输出一行一个整数，表示听完所有人的报告后，Yazid 最大的兴奋度。

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

如果 Yazid 先听第一个人的报告，再听第二个人的报告，那么最后的兴奋度是 $(3+1)\times2=8$；

如果 Yazid 先听第二个人的报告，再听第一个人的报告，那么最后的兴奋度是 $(3\times 2)+1=7$。

所以最大的兴奋度为 $8$。

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

只有一场报告，Yazid 初始兴奋度为 $-2$，那么听完报告之后的兴奋度为 $8\times \lvert -2 \rvert+(-4)\times (-2)+1=25$。

**【子任务】**

子任务 1（13 分）：$n \le 10$；

子任务 2（19 分）：$c_i = 0$；

子任务 3（23 分）：$a_i=0$；

子任务 4（45 分）：无特殊限制。

对于所有测试点，保证 $n\leq 15$，保证 $a,b,c,s$ 的绝对值均**不超过** $15$。

**【提示】**

在数据规模限制下，答案将不超过 $128$ 位有符号整数的范围，因此你可以尝试使用 `__int128` 来帮助实现你的算法。


title: [THUWC 2020] 道路修建

description:
$A$ 国是一个古老的国家。这个国家分布着 $n$ 个城市，城市由 $1 \sim n$ 编号。其中，$1$ 号城市是这个国家的首都，也是国家里唯一有港口的城市。进口的货物从首都的港口运入，再运送向其它城市。

为了方便进口货物的运送，$A$ 国国王打算修建若干条单向道路专门用于运送货物。很快，$A$ 国的大臣们给出了一个道路修建方案：这个方案由 $m$ 条单向道路组成，通过这些道路可以从 $1$ 号城市到达国家内的其它任意一个城市。非常特殊的是，这 $m$ 条道路构成的道路网络不存在环。

由于财政状况不允许，$A$ 国国王打算从 $m$ 条道路中先选择 $n-1$ 条进行修建，以保证基本的货物运输能力。他使用了一种类似于深度优先搜索的方法确定出优先修建的 $n-1$ 条道路：

首先，令集合 $S$ 为仅包含 $1$ 号城市的集合，并设置当前城市 $u$ 为 $1$ 号城市。

然后，选择一条以当前城市 $u$ 为出发点、一个不在集合 $S$ 内的城市 $v$ 为终点的道路，将该道路标记为优先修建的道路，将城市 $v$ 加入 $S$ 集合，并将城市 $v$ 的父亲设置为当前城市 $u$。

最后，将当前城市 $u$ 修改为城市 $v$。如果城市 $v$ 的选择有多个，则选择城市编号最小的一个；如果没有可以选择的城市 $v$，则将当前城市 $u$ 修改为 $u$ 的父亲。

重复上述操作，直到所有城市被加入 $S$ 集合时停止。

可以发现，上述步骤恰好可以选出被优先修建的 $n - 1$ 条道路，并且这些优先修建的道路可以构成一个以首都为根的树型结构。我们称这些被优先修建的道路为树上道路。

随着经济的发展，$A$ 国逐渐完成了 $m$ 条道路构成的道路网。但其中，树上道路由于修建年代较早，时常需要进行维护。$A$ 国的大臣们提出了 $q$ 个可能的维护计划，每个修建计划需要同时维护城市 $a$ 与城市 $b$ 之间的所有树上道路，并且保证城市 $a$ 是城市 $b$ 在树上的祖先。这样的维护计划会对城市 $b$ 为根的子树产生很大的影响，$A$ 国国王希望你帮忙评估每个可能的维护计划——计算在城市 $a$ 与城市 $b$ 之间的所有树上道路不能使用时，从首都出发，有多少个在以城市 $b$ 为根的子树内的城市将不能到达？

inputFormat:
第一行三个整数 $n,m,q$，分别表示 $A$ 国的城市数量、道路修建方案的道路数量、维护计划的数量。

接下来 $m$ 行，每行两个整数 $x, y$，表示修建方案中一条从$x$到$y$的单向道路。

接下来 $q$ 行，每行两个整数 $a,b$，表示一个维护计划。

输入数据保证：

1. 给定的道路修建方案保证从首都出发能到达 $A$ 国的每个城市，并且该方案中不存在环。
2. 任意两个城市之间的道路至多出现一条，每条道路两端的城市编号不同。
3. 每个维护计划中的城市 $a$ 保证是城市 $b$ 在树上道路构成的树结构中的某个祖先。

outputFormat: 输出 $q$ 行，每行一个整数，表示在每个维护计划下，从首都出发，有多少个在以城市 $b$ 为根的子树内的城市将不能到达。


title: [THUWC 2020] 序排泡冒

background:
> You are given a peach tree $T$.
>
> You don't need to think of the peach.
>
> Because I'm going to talk about the tree.

description:
**冒泡排序算法**是一种广为人知的排序算法，其思路在于不断地交换相邻且逆序的两个元素，由于总的逆序对个数不断减少，冒泡排序算法一定可以终止。给 $a[0], a[1], \dots, a[n-1]$ **从小到大排序**的冒泡排序算法可以用下面的伪代码描述。

```cpp
for (int i = 1; i <= k; i++)
    for (int j = 0; j < n-1; j++)
        if (a[j] > a[j+1]) {
            tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;
        }
```

其中 $k$ 称为冒泡排序进行的轮数，当 $k$ 取 $n$ 时，便可以保证序列被从小到大排序。

**序排泡冒算法**是一种鲜为人知的序排算法，其作用是给定一个长度为 $n$ 的序列 $a$ 和参数 $k$，输出所有可能的序列 $b$，满足其经过 $k$ 轮冒泡排序之后成为序列 $a$。

给定一棵树 $T$，结点用 $1,2, \dots, n$ 编号。每一个结点 $u$ 有一个点权 $p(u)$，保证 $p(1), p(2), \dots, p(n)$ 构成了 $\{1,2,\dots,n\}$ 的一个排列。换言之，满足

1. 对于 $u\ne v$，均有 $p(u)\ne p(v)$；
2. 对于任意的 $i\in \{1, 2, \dots, n\}$，均存在一个 $u$ 满足 $p(u)=i$。

对于这棵树，我们将进行 $m$ 次询问，每次询问给出两个结点 $u, v$ 和一个参数 $k$。用 $t_1, t_2, \dots, t_l$ 表示从 $u$ 到 $v$ 的唯一简单路径上**依次经过的所有结点的点权**组成的序列，可以看出 $t_1$ 就是 $p(u)$，$t_l$ 就是 $p(v)$，你需要计算序列 $t$ 和参数 $k$ 进行序排泡冒后，输出的排列序列个数。换言之，求有多少个序列满足其**经过 $k$ 轮冒泡排序后得到序列 $t$**。

由于答案很大，你只需要输出其对 $998,244,353$ 取模的结果（也就是说，输出答案除以 $998,244,353$ 的余数）。

inputFormat:
第一行包含两个用空格分隔的自然数 $n, m$，表示结点个数和询问个数。

接下来的一行包含 $n$ 用空格分隔的整数 $p(1), p(2), \dots, p(n)$，表示每个点的点权。

接下来 $n-1$ 行每行包含两个数 $x_i, y_i$，表示树上存在一条连接 $x_i$ 和 $y_i$ 上的边。输入的数据保证所有的边构成一棵树。

接下来 $m$ 行每行包含一个询问 $u_i, v_i, k_i$，其意义在题目描述中已经说明。

outputFormat: 输出包含 $m$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个询问的答案对 $998,244,353$ 取模的结果。

samples:
见附件中的 2.in。
见附件中的 2.ans。


title: [PA2024] Mrówki

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

数轴上有 $n$ 只蚂蚁，第 $i$ 只位于点 $x=i$。每只蚂蚁面向右（数轴的正方向）或者向左（数轴正方向的反方向）。蚂蚁小到我们可以认为他们是独立的点。

信号发出后，所有蚂蚁开始以相同的单位速度朝它们面向的方向前进。如果两只蚂蚁相撞（位于同一点），它们就会弹开，也就是说，它们都会改变行进方向，继续前进。可以证明，经过一定时间后，不会再发生碰撞。你能编写一个程序，计算出每只蚂蚁会与其他蚂蚁碰撞多少次吗？

inputFormat:
第一行一个整数 $n\ (1\le n\le 300\,000)$，表示蚂蚁的数量。

第二行包含一个长为 $n$ 的字符串，字符串仅包含 `L` 和 `P`。其中第 $i$ 个字符表示蚂蚁 $i$ 面向的方向，如果为 `L`，则初始面向左，如果为 `P`，则初始面向右。

outputFormat: 输出一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 只蚂蚁与其他蚂蚁的碰撞次数。

hint: 第一只蚂蚁一开始面向左，不会与其他蚂蚁碰撞。最后一只蚂蚁会在 $x=5.5$ 处与第五只蚂蚁相撞，然后开始向右行进，并且再也不会停下来。第三只蚂蚁在 $x=3.5$ 处与第四只蚂蚁碰撞后，开始向左行走。第二只蚂蚁会在 $x=3$ 处碰撞，然后向左转，之后一直走下去。


title: 「SMOI-R1」Queue

background: 签到题……

description:
有一个人数为 $n$ 的队伍，队伍中第 $i$ 个人编号为 $i$。

从第一个人依次给后面的那个人传一个数，直到传到第 $n$ 个人。给后面的那个人传数的规则为：

- 第一个人的数为 $1$。
- 如果这个人的编号为奇数，那么给后面的人传的数是他现在的数**按位与**上后面那个人的编号。
- 如果这个人的编号为偶数，那么给后面的人传的数是他现在的数**按位异或**上后面那个人的编号。

求出传给第 $n$ 个人的数字。但是求一个的太好求了，所以你要求 $t$ 种情况的。

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

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

对于每组数据：

只有一个数 $n$，代表队伍人数。

outputFormat: 对于每组数据，输出一个数，代表传给第 $n$ 个人的数字。

hint:
### 样例解释

对于第二组数据：

- 第一个人向下一个人传的数是 $1\operatorname{and}2=0$。
- 第二个人向下一个人传的数是 $0\operatorname{xor}3=3$。
- 第三个人向下一个人传的数是 $3\operatorname{and}4=0$。
- 第四个人向下一个人传的数是 $0\operatorname{xor}5=5$。

所以答案是 $5$。

### 数据范围
**本题采用捆绑测试**。

subtask 编号|$t\leq$| $n\leq$| 分值
-|-|-|-
$1$|$10^2$|$10^5$|$20$
$2$|$10^6$|$10^7$|$20$
$3$|$10^6$|$10^{18}$|$60$

对于 $100\%$ 的数据,保证 $1\le t\le10^6,1\le n\le 10^{18}$。


title: 「SMOI-R1」Apple

background: **为了卡掉错误算法，我们把时限改为 680ms。**

description:
LAR 有 $2^n$ 个苹果，苹果用 $0$ 到 $2^n - 1$ 编号，编号为 $i$ 的苹果的价值是 $v_i$。

如果 $A\operatorname{or}B=A$，那么可以说 $A$ 包含 $B$（$\operatorname{or}$ 是按位或）。

因为 LAR 的苹果太多了，所以他不知道如何挑选苹果。他想进行一些操作，方便他吃苹果。

总共有两种操作，共 $q$ 个操作：

- $1\ S$ ，询问所有编号被 $S$ 包含的苹果的价值总和。
- $2\ S\ A$ ，改变编号为 $S$ 的苹果的价值为 $A$（将 $v_S$ 改为 $A$）。

inputFormat:
第一行有两个整数 $n$ 和 $q$。$q$ 代表操作次数。

第二行有 $2^n$ 个数，第 $i$ 个数代表 $v_{i-1}$ 的值。

接下来有 $q$ 行，每行代表 LAR 要进行的一个操作，详细见上文。

outputFormat: 对于每个操作 $1$，输出一个数，代表这个询问的答案。


title: 质因子

background: 你所提交的代码长度不应低于 10 字节。

description: 给定 [numlist.txt](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/rxuwd604?contestId=170180)，请求出文件中的 $1000$ 个数的乘积的质因子 $2$ 出现的次数。

inputFormat: 无

outputFormat: 输出答案即可。


title: [THUSC 2019] 彩票

description:
华清大学内有一个彩票站点，站点内设有 $n$ 个彩箱。初始时每个彩箱内都放有若干奖券，奖券分为中奖券与空奖券两种，其中第 $i$ 个彩箱内有 $a_i$ 张中奖券、$b_i$ 张空奖券。同学们每次抽奖时，将会选择一个彩箱，然后从该彩箱剩余的奖券中等概率随机抽取一张，即剩余的每张奖券被抽中的概率均相等。注意：被抽出的奖券将不放回彩箱。

现在有 $m$ 位同学在彩票站点排队，同学们将依次每人进行一次操作。具体地，对于第 $j$ 个操作的同学，他可能进行的操作有以下三种：

1. 抽奖：从第 $l_j$ 个到第 $r_j$ 个彩箱，对它们中的每个都连续抽取 $c_j$ 次奖。若彩箱中剩余奖券数量不足 $c_j$，则将彩箱中所有奖券抽完为止。
2. 询问：从第 $x_j$ 个到第 $y_j$ 个彩箱，求所有被抽出的中奖券的数量之和的期望值。
3. 加奖：在第 $p_j$ 个彩箱中，添加 $u_j$ 张中奖券和 $v_j$ 张空奖券。

现在请你回答同学们的每次询问。由题目性质知，期望值一定可以写成 $\frac{p}{q}$ 形式的有理数，请你输出它对 $10^9+7$（一个质数）取模后的结果，即找出一个 $r$ $(0\leq r < 10^9+7)$ 使得 $qr \equiv p \pmod{10^9+7}$。可以证明这样的 $r$ 是唯一的。

inputFormat:
第一行两个正整数 $n,m$，分别表示彩箱数和同学人数。

接下来 $n$ 行，每行描述一个彩箱。

这 $n$ 行中的第 $i$ 行有两个整数 $a_i,b_i$，意义见题目描述。

接下来 $m$ 行，每行描述一个同学的操作。

这 $m$ 行中的第 $j$ 行的第一个整数 $op_j$ 表示操作类型。若 $op_j=1$，接下来输入三个整数 $l_j,r_j,c_j$；若 $op_j = 2$，接下来输入两个整数 $x_j,y_j$；若 $op_j=3$，接下来输入三个整数 $p_j,u_j,v_j$。具体变量意义见题目描述。

同一行内整数均由一个空格分隔开。

输入数据保证：

$0 \leq a_i,b_i,c_j \leq 10^8$

$0\leq u_j,v_j \leq 10^3$

$1\leq l_j\leq r_j \leq n$

$1\leq x_j\leq y_j\leq n$

$1\leq p_j\leq n$

$op_j \in \{1,2,3\}$

outputFormat: 对于每个 $op_j = 2$ 的询问，输出一行一个整数表示询问的答案。

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

第一位同学操作后，第 1 个彩箱中被抽出的中奖券数量期望值为 $\frac{1}{3}$。

第二位同学操作后，第 2 个彩箱中被抽出的中奖券数量期望值为 $\frac{1}{2}$。

第三位同学的答案即为：$\frac{1}{3} + \frac{1}{2} = \frac{5}{6}$，它对 $10^9+7$ 取模的结果为 $833333340$。

第四位同学操作后，第 3 个彩箱中有 3 张中奖券、1 张空奖券。

第五位同学操作后，第 3 个彩箱中被抽出的中奖券数量期望值为 $\frac{9}{4}$。

第六位同学的答案即为：$\frac{1}{3} + \frac{1}{2} + \frac{9}{4} = \frac{37}{12}$，它对 $10^9+7$ 取模的结果为 $83333337$。

**【样例 2】**

见题目附件中 `2.in/2.ans`。

**【样例 3】**

见题目附件中 `3.in/3.ans`。

**【样例 4】**

见题目附件中 `4.in/4.ans`。

**【子任务】**

| 子任务编号| 分值 | $n,m\leq$ | 其他限制 |
| :--: | :--: | :--: | :--: |
| 1 | 23 | $1000$ | $0\leq a_i,b_i \leq 10$ 且 $op_j \neq 3$|
| 2 | 17 | $10^5$ | $op_j \neq 3$ 且 $l_j = r_j$ |
| 3 | 20 | $2 \times 10^5$ | $l_j=r_j$ |
| 4 | 20 | $2 \times 10^5$ | $op_j \neq 3$ |
| 5 | 20 | $3 \times 10^5$ | 无 |


title: [THUSC 2019] 补给计划

background: T 国是一个小国，受百年一遇的寒流影响，现在一些城市受到了严重的影响，T 国政府打算从首都派出救援队对受灾城市进行救助，同时建立若干补给点对救援队提供支持。

description:
T 国一共有 $N$ 个城市（城市编号从 $1$ 到 $N$），这些城市被 $M$ 条双向道路所连接，每条道路有各自的长度（均大于 $0$）。

共有 $K$ 个城市受灾，T 国政府计划从首都（$1$ 号城市）向这 $K$ 个城市各派出一支救援队，同时为了更好地完成救助，T 国政府计划在一些城市建立补给点。

然而由于受到地理与资金等因素的影响，并不是每个城市都能建立补给点（一个城市能否建立补给点与其是否是首都或受灾城市无关）。

为了尽快完成救助，这 $K$ 支救援队都只会按照最短路径前往自己的目的城市，T 国政府希望在能够建立补给点的城市中建立尽量少的补给点，使得每只救援队至少有一条到其目的城市的最短路径会经过至少一个补给点。

现在告诉你 T 国的城市与道路信息，你需要计算出 T 国政府至少需要建立多少个补给点。

inputFormat:
输入的第一行包含三个整数 $N,M,K$，含义见题目描述，保证 $1 \le N \le 200, 0 \le M \le 10000, 1 \le K \le 20$。

第二行有 $N$ 个整数，每个数为 $0$ 或者 $1$，依次表示对应的城市能否建立补给点（$1$ 表示可以建立补给点）。

第三行有 $K$ 个正整数 $x_i$，表示受灾的城市编号，保证这 $K$ 个数各不相同且首都不会受灾，$1 \le x_i \le N$。

接下来 $M$ 行，每行三个整数 $u,v,w$，表示城市 $u$ 和城市 $v$ 之间存在一条长度为 $w$ 的道路，$1 \le u,v \le N, 0 < w \le 10^9$。

输入保证一定存在至少一个方案满足题目描述的要求。

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

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

该样例对应的图形如下，其中 $1$ 号点是首都，$3,4,6$ 号点是受灾城市：

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

该样例至少需要修建 $2$ 个补给点，可以分别建在 $2,5$ 或者 $2,6$ 。注意不能修建在 $3,5$ 号点，因为从首都到 $4$ 号点的最短路径只能是 $1 \rightarrow 2 \rightarrow 4$，不存在经过 $3,5$ 号点的最短路。

**【子任务】**

| 测试点  | $N$ | $M$ | $K$ | 特殊性质 |
| :--:|:--:|:--:|:--:|:--:|
| $1\cdots 2$ | $1 \le N \le 200$ | $M=N-1$| $1 \le K \le 20$ | 输入是一棵树 |
| $3\cdots 6$ | $1 \le N \le 200$ | $0 \le M \le 10000$ | $1 \le K \le 4$ | 无 |
| $7\cdots 12$ | $1 \le N \le 200$ | $0 \le M \le 10000$ | $1 \le K \le 16$ | 无 |
| $13\cdots 20$ | $1 \le N \le 200$ | $0 \le M \le 10000$ | $1 \le K \le 20$ | 无 |


title: [JRKSJ R9] ZYPRESSEN

background:
大气层越发清澈澄明\
无声的丝柏冲天而立

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

黄金般的草地\
走来一个人影\
农夫身穿蓑衣\
正在定睛看我\
却不知他是否\
真的能看见我\
耀眼的大气下\
哀怨依然青深\
柏木静静摇曳\
鸟儿再次划破青空\
此处已无真心话语\
阿修罗泪如雨落土

重振精神仰头呼吸\
微白的肺越发紧缩\
任凭身体散作空中微尘\
银杏枝头再次发光\
柏木愈发黑沉\
云之花火纷飞坠落

——宫泽贤治《春与阿修罗》

description:
给你一个长度为 $n$ 的序列 $a$，共有 $q$ 次询问，每次询问如下：

* 给你一个区间 $[l,r]$，对于所有的 $i,j,k$ 满足 $l\le i<j<k\le r$ 且三边长度分别为 $a_i,a_j,a_k$ 的三角形存在，你需要求出 $a_i+a_j+a_k$ 的最小值。

三边长度分别为 $a,b,c(a\le b\le c)$ 时，能构成三角形当且仅当 $a+b>c$。

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

第二行 $n$ 个整数 $a_{1\dots n}$。

接下来 $q$ 行，每行两个整数 $l,r$ 表示询问。

outputFormat: $q$ 行，每行一个整数表示答案。如果不存在符合条件的 $i,j,k$，输出 `yumi!`。


title: 『STA - R6』spec

description:
  定义一个实数 $\alpha$ 的谱 $\operatorname{Spec}(\alpha)$ 是整数组成的一个无限长的序列 $\lceil\alpha\rceil-1,\lceil2\alpha\rceil-1,\lceil3\alpha\rceil-1,\cdots$。例如，$\frac35$ 的谱的开头部分是 $0,1,1,2,2,3,4,\cdots$。

现在给定 $n$ 个整数 $x_1,\cdots,x_n$，你要找到最大的实数 $\alpha$，使得对于每个元素 $x_i$ 都有 $x_i$ 在 $\operatorname{Spec}(\alpha)$ 中出现过。

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

第二行 $n$ 个正整数 $x_1,x_2,\cdots,x_n$。

outputFormat: 一行，表示最大的 $\alpha$。你的答案与标准答案的绝对误差低于 $10^{-5}$ 即判为正确。

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

数据范围：
- Subtask 0 (10pts)：$n,x_i\le 100$。
- Subtask 1 (15pts)：合法答案构成一段连续区间。
- Subtask 2 (25pts)：每个 $x_i$ 都是 2 的非负整数次幂。
- Subtask 3 (50pts)：无特殊限制。

对于全部数据，$1\le n,x_i\le 1000$。


title: [THUSC 2019] 紧急决策

description:
在一片海岸上，有 $n$ 个灯塔，从 $1$ 到 $n$ 编号。这片海岸可以看作一条数轴，每个灯塔可以看作数轴上的一个点。第 $i$ 个灯塔在数轴上的位置为 $x_i$，每个位置上最多只能有一个灯塔。这 $n$ 个灯塔按照位置从前到后的顺序排列，即第 $x_i < x_{i+1}, 1 \le i < n$。现在，刚好有 $n$ 名游客正在海岸外排队等候进入海岸，第 $i$ 名游客进入第 $i$ 座灯塔参观。

出于安全考虑，每座有游客在上面的灯塔必须被*照亮*。但由于海岸上的供能限制，最多只能*点亮* $t$ 座灯塔。每个灯塔的照明范围为 $q$。当某个灯塔上的灯打开后，海岸上和它距离不超过 $q$ 位置都会被照亮（即集合 $\{x \mid \lvert x-x_i \rvert \le q\}$ 中的所有点都会被照亮）。

现在你作为海岸的旅游局的管理者，需要决定让哪些游客进入海岸玩耍。做决策不是拍脑袋想出来的，必须满足几点要求：

- 保证安全第一原则，即可以找到一种照明方案使得进入海岸的每个游客所在的灯塔都被照明；
- 保证先来后到原则，排在队列前面的游客优先进入海岸。如果某个游客不能进入海岸，则排在他后面的游客都不能进入海岸；
- 保证追求利润原则，卖出尽可能多的门票，即尽量让数量更多的游客进入海岸。

精打细算的你一敲键盘，算出最后会有多少游客进入海岸。

inputFormat:
第一行为两个整数 $n,t,q$，表示灯塔的数目以及最多点亮的灯塔的数目。

第二行为 $n$ 个整数，第 $i$ 个数 $x_i$ 表示第 $i$ 座灯塔的坐标。

outputFormat: 输出一行一个整数，表示最后进入海岸的游客数目。


title: 『STA - R6』月

description:
对于一棵有 $n$ 个节点的树 $T$，定义其直径 $\operatorname{diam}(T)$ 为任意两个节点之间距离的最大值。

给定正整数 $n$ 和每个点 $i$ 的度数 $d_i$，你需要构造一棵树 $T^\prime$，同时最小化 $\operatorname{diam}(T^\prime)$。

保证至少存在一棵符合要求的树，若存在多个符合要求的答案，输出任意一个即可。

inputFormat:
**本题单个测试点内含有多组测试数据。**

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

对于每组测试数据，

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

- 第二行 $n$ 个正整数，第 $i$ 个正整数表示点 $i$ 的度数 $d_i$。

outputFormat: 对于每组测试数据，输出 $n - 1$ 行，每行两个正整数 $u_i, v_i$，表示构造出的树的边集。

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

对于最后一组数据，所构造出的树如下图：

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

其直径等于点 $5,7$ 之间或点 $6,7$ 之间的距离，为 $4$。可以证明，不存在满足条件的直径小于 $4$ 的树。

**【数据范围】**

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

对于 $100\%$ 的数据：

- $2 \le n \le 2 \times 10^5$；
- $1 \le T \le 10^5$；
- $\sum n \le 2 \times 10^5$；
- $1 \le d_i < n$；
- 保证至少存在一个合法的解。

具体部分分分配如下：

|Subtask 编号|数据范围|分值|
|:--------:|:--------:|:--------:|
|1|$n \le 5$|$17$|
|2|$d_i \le 2$|$23$|
|3|$d$ 中只含有两种本质不同的元素|$26$|
|4|无特殊限制|$34$|


title: 『STA - R6』b20

background: 我的 B 站 20 粉丝啦！

description:
小 A 在各种平台都很活跃，大家经常通过祂在各种平台的粉丝数来称呼祂。

具体地，取出网站名字的第一个字母并拼接上粉丝数量，即得到对应称呼。例如，小 A 在 Bilibili 有 $20$ 粉丝，就称其为 `B20`，小 A 在 wikidot 有 $0$ 粉丝，就称其为 `w0`。

现在，给定小 A 在活跃的网站名字和粉丝数量，输出其对应称呼。

inputFormat:
第一行一个字符串表示网站名称。

第二行一个非负整数表示粉丝数。

outputFormat: 一行，表示对应称呼。

hint:
对于 $30\%$ 的数据，保证网站名为 `bilibili`。

对于全部数据，网站名称长度不超过 $20$ 且仅含英文字母，粉丝数是不超过 $10^7$ 的非负整数。


title: [THUSC 2019] 数列

description:
定义一个长度为 $k$ 的数列的价值为：$val = \max \limits_{1 \le i \le k}\{i \times f(i,k)\}$。

其中 $f(i,j)$ 表示区间 $[i,j]$ 范围内数值种类数。

给出一个长度为 $n$ 的数列，计算所有连续子区间的价值总和。将一个连续子区间视为一个独立的数列，计算出的价值即为该连续子区间的价值。

设 $m$ 为数列里出现的数值种类数。

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

第二行输入 $n$ 个正整数，$a_1, a_2, \dots, a_n$ 描述数列里每个位置上的数值。

对于所有的输入数据，都满足 $1\le n \le 10^5$。

outputFormat: 第一行输出一个整数表示答案对 $998\ 244\ 353$ 取模。


title: [THUSC 2019] 推恩令

background: 西汉初年，汉高祖刘邦为了更好地将土地掌握在刘家的手里，大量分封刘姓诸侯王。但随着刘邦去世，诸侯王们越来越不受中央的控制。为了削弱诸侯国的势力，汉武帝刘彻采纳朝臣主父偃的建议，实行推恩令。推恩令要求诸侯王将自己的土地分封给自己的每个子弟，而不是传位给自己的长子。这样一来，土地面积大的王国将被划分为几个土地比较小的诸侯国，诸侯王们的势力也就得到了削弱。

description:
让我们来考虑这么一个实际的例子：有一个诸侯王，他的诸侯国里有 $n$ 个城邦，其中，城邦 $s$ 是他的诸侯国的国都。我们可以用平面直角坐标系来描述他的领土，第 $i$ 个城邦可以被看作坐标系中以 $(x_i,y_i)$ 为中心，$r_i$ 为半径的一个圆。任意两个城邦之间不会有重叠的部分（相交），也不会相互接触（相切）。

这个诸侯王有两个儿子，他想用一种简单的方式将他的国土分给他的两个儿子：在他的国土中修建一道分界渠。这道分界渠可以用坐标系中的一条直线来表示，它不能经过任意一个城邦（相交），也不能经过一个城邦的边界（相切）。这道分界渠可以将国土分为两个部分，国都 $s$ 所在的部分分给长子，另一部分分给次子。为了保证次子也可以选择一个城邦作为他的国都，分界渠两侧的国土都必须包含至少一个城邦。

分界渠的修建方式可以有很多种，为了保证公平，诸侯王希望在所有本质不同的修建水渠的方式中随机地选择一种。如果两种修建分界渠的方式会把城邦分成相同的两个部分，那么这两种修建方式就被认为是本质相同的。

诸侯王的次子打听到了国王的划分办法。为了提前挑选自己的国都，他想知道了解每一个城邦成为他的国都的可能性大小。他把这个任务交给了你，你需要帮助他计算：对于每一个城邦，有多少种本质不同的修建水渠的方式能使得他能选择这个城邦作为国都？

inputFormat:
第一行两个整数 $n,s$，分别表示诸侯国内城邦的数量以及国都的编号。

接下来 $n$ 行，每行三个整数 $x_i, y_i, r_i$，第$i$行表示第 $i$ 个城邦的中心和半径。

outputFormat: 输出 $n$ 行，每行一个整数 $a_i$，第 $i$ 行的输出表示有 $a_i$ 种本质不同的修水渠方案能让次子选择第 $i$ 个城邦作为国都。


title: [THUSC 2019] PCAP 文件解析与读写

background:
说明：请从题目附件下载试题题面所提及的《学习手册》。自本题起的五题，为 THUSC 2019 第三试《网络流量分析与处理》的五小题。原试题共六小题，其中最后一题为反馈，不再收入。

---

芃芃是华清大学计算机系的一名学生，马上读大二上学期。由于他精通 OI，觉得这个学期的唯一一门专业课《数据结构》实在是太简单了。在学长杰哥的盛情推荐下，他提前选了大三的专业课《计算机网络原理》。然而，这门课程的大作业是自己动手实现一个软件路由器，这可难倒了没有工程经验的芃芃。为了不让杰哥失望，他决定在暑假里就提前完成这个任务。

本题一共分为 6 个小题，难度递增。你将与芃芃一起学习网络的基本原理、网络设备的工作方式，并亲手实现一个个功能，最终完成一个简化版的路由器软件。麻雀虽小，五脏俱全，它将能对多种基本的网络协议进行处理，并担任起路由器最根本的使命——转发。

在本题**所有的小题**中，我们都有以下的约定：

* 你的计算机上有 16 个网络接口，编号从 1 到 16。
* 你的计算机上默认的路由表为空，并且只能从 RIP 报文获得路由表的更新。
* 每个接口对应**一个** IP 地址 `10.2.n.1/24`，其中 $n$ 代表接口编号，范围是 1 到 16。
* 每个接口对应一个 MAC 地址 `98:01:29:00:00:xx`，其中 `xx` 是接口编号的 16 进制表示，范围是 $01_{16}$ 到 $10_{16}$。
* 所有的流量片段，包括读取和写入的，都是以太网帧（包括帧头和帧尾的校验），包含完整的协议格式。
* 除特殊说明外，输入的 PCAP 文件中的流量片段都是按照时间顺序排列的（时间戳单调递增），只需要进行依次处理即可。

如果你不能理解上述的约定，请参见《学习手册》网络基础相关部分。

description:
所有题目中，网络流量都将以 PCAP 文件格式保存，具体格式说明可参见《学习手册》。本题需要对 PCAP 文件进行基本的读写与解析。

在本题中，你需要完成的任务是依次遍历输入文件中时间乱序的流量片段，在对它们进行一些操作后，组装为 PCAP 格式写入输出。关于文件的读写方式，可以参照《学习手册》。

需要进行的操作为：只保留长度**不大于** $1000$ 的片段（只考虑完整的以太网帧长度，不包括 PCAP 格式的片段头），并按照时间升序排序这些片段（即首先比较秒，而后比较微秒），保证没有两个片段的时间是相同的。需要注意，你的输出文件需要是一个合法的 PCAP 文件。为了测试文件格式的合法性，你可以使用 Wireshark 等工具打开你的输出文件进行检查。

与手册中指示的不同的是，本题中，你应该直接完整复制每个流量片段的头，包括时间戳字段。

inputFormat: 输入包含不超过 $n$ 个流量片段，总大小不超过 $m$ 字节。

outputFormat: 你的输出将与答案文件进行**逐字节**对比。请不要输出任何多余信息，以免导致不必要的失分。

hint:
**【子任务】**

| 测试点 | $n$ | $m$ |
|:--:|:--:|:--:|
| 1 | $=10^2$ | $=5\times 10^4$ |
| 2 | $=10^2$ | $=1.5\times 10^5$ |
| 3 | $=10^3$ | $=1.5\times 10^6$ |
| 4 | $=10^4$ | $=1.5\times 10^7$ |
| 5 | $=10^5$ | $=1.5\times 10^8$ |

**【样例 1】**

见题目附件 `1.in/ans`。

**【样例解释 1】**

你可以用你电脑上安装的 Wireshark 软件打开样例数据的输入和输出。

用 Wireshark 打开样例输入文件，应该可以看到，界面上部记录了这个 PCAP 文件中记录的所有以太网帧，界面中部显示的是当前这个以太网帧的解析，下部则是它的十六进制数据。对于这个软件的详细使用方法，除了部分题目给出的提示外，不会提供更多帮助，请选手自行熟悉并摸索。

样例输入文件记录了两个以太网帧，都是从 `10.2.254.100` 发往 `10.2.12.82` 地址的 ARP 请求，它们区别在于 ARP 请求后多余的数据长度不同。由于第一个帧的长度不大于 1000 ，第二个帧的长度大于 1000，按照题目意思，只有第一个帧需要输出，排序后输出到了样例输出文件中，你可以同样地用 Wireshark 打开样例输出文件来验证这一点。


title: [THUSC 2019] 常见网络校验和计算

background: 芃芃发现，华清大学的玉兰学生公寓的网络质量似乎不是很好。由于网络线材质量的原因，也可能是有同学在进行一些奇怪的尝试，他总是会收到一些不太正常的内容。好在，网络协议的设计者们都考虑到了这一点，在协议中添加了校验和来检查一些明显的问题。作为鲁棒的路由器软件，必须只接收校验和检查通过的流量，而丢弃那些坏的。听说你已经能读到流量的内容了，下一步就是揪出这些不正常的流量。

description: 你需要根据《学习手册》中的相关知识，对给定的流量片段进行校验。请注意，由于所有片段类型**都是以太网帧**，所以你总是需要计算 `CRC32`；而对于承载了 IP 分组的流量，你还需要对 IP 分组头的检验和进行检查。作为简化，我们不考虑除了以太网和 IP 以外的校验字段。只有当所有的校验都通过时，才认为该流量片段是正确的。

inputFormat: 输入保证格式合法，并且每个流量片段都是以太网帧。其中包含不超过 $n$ 个流量片段，总大小不超过 $m$ 字节。部分子任务的数据中保证 IP 分组头的校验是正确的，即只需要计算以太网帧的 `CRC32`。

outputFormat: 输出由 $n$ 行文本构成，依次对应每一个片段的校验结果。如果是正确的，输出 `Yes`，否则输出 `No`。

hint:
**【子任务】**

| 测试点 | $n$ | $m$ | 仅需检查以太网帧 |
| :--: | :--: | :--: | :--: |
| 1 | $=10^2$ | $=5\times 10^4$ | 是 |
| 2 | $=10^2$ | $=1.5\times 10^5$ | 否 |
| 3 | $=10^3$ | $=1.5\times 10^6$ | 否 |
| 4 | $=10^4$ | $=1.5\times 10^7$ | 否 |
| 5 | $=10^5$ | $=1.5\times 10^8$ | 否 |

**【样例 1】**

见题目附件 `1.in/ans`。

**【样例解释 1】**

和 `pcap` 题一样，你可以用你电脑上安装的 Wireshark 软件打开样例数据的输入和输出。

样例输入文件应该包含四个以太网帧，其中第一个以太网帧中 FCS 和 IP 的校验都是错误的，第二个以太网帧是 FCS 校验正确的 ARP 帧，第三个以太网帧仅 FCS 校验错误，第四个以太网帧仅 IP 校验错误。在页面中部点开当前帧的解析可以看到更多细节，包括是哪个校验错误和正确值等等，这可能对你有一定的帮助。

Wireshark 默认情况下可能不会检查 FCS 的正确性。对于这种情况，你可以在页面中部找到并右键点击 `Ethernet II` 所在的一行，在弹出的菜单中选择 `Protocol Preferences`，勾上选项中的 `Validate the Ethernet checksum if possible` 和 `Assume packets have FCS`，此时你应该可以在页面上部看到 FCS 错误的帧都被明显地标记出来。

需要注意的是，Wireshark 还会计算并显示 UDP 的 Checksum 正确与否。在本题中，我们不考虑 UDP 的 Checksum，因此你可以忽略这些错误。


title: [THUSC 2019] 数据链路层协议数据处理

background: 路由器软件需要处理的最底层是数据链路层，这上面运行着一系列复杂的协议，比如各种神秘的滑动窗口协议。虽然芃芃对它们始终摸不着头脑，但他知道这一层最重要的协议就属 ARP 了。它起到了跨上下两层的桥梁作用，只有通过 ARP 查询，路由器才能知道究竟应该把 IP 分组发给哪一个邻居。你的路由器软件需要热情地回应每一个询问，才能正确地收到接下来的流量。

description:
你需要根据《学习手册》中的相关知识，处理数据链路层的协议数据：在给定的流量片段中，有一些是对你的 ARP 询问（也就是说，询问的 IP（TPA 字段）是你拥有的，请在 pcap 题面中找到你拥有的 IP 地址和与其对应的 MAC 地址），请你正确地回复它们。数据保证 FCS 校验正确的 ARP 请求中发送端的 MAC 地址（SHA 字段）与以太网帧中的发送端 MAC 地址一致。注意，ARP 请求中以太网帧的目标地址可能与你拥有的 MAC 地址不同（如 `FF:FF:FF:FF:FF:FF` 广播地址），这种情况下依然需要回应 ARP 请求。你需要构造正确的 ARP 协议数据，以及外层的以太网帧格式（包括头部和校验和，并注意以太网帧的长度要求），并将这些以太网帧帧按照应答顺序按照《学习手册》的要求依次写入 PCAP 格式的输出文件中。

在**下列所有题目（包括本题）**中，如果某个流量片段发生校验错误，则应当直接丢弃，片段的数据可能会出现不符合《学习手册》中的叙述的情况，所以不能有任何假设，不进行任何处理。

inputFormat: 输入保证格式合法，其中包含不超过 $n$ 个流量片段，总大小不超过 $m$ 字节。你需要回复 $n_1$ 个流量片段。

outputFormat: 其将与答案文件进行**逐字节**对比。


title: [THUSC 2019] 网络层协议数据处理

background: 百度对程序员来说最大的作用当然是测试网络的联通性，在处理完 ARP 包以后，芃芃兴奋地输入了 `ping baidu.com`，然而并没有得到任何结果。咨询过杰哥以后，芃芃懂得了 ping 工具的工作原理，原来它使用了 ICMP 协议，工作在比数据链路层更高的网络层。他还发现，网络中也存在许多给他发送的 ping 报文，看来的确有很多人在关心他。为了不让他们失望，你决定帮芃芃回复这些请求。

description:
你需要根据《学习手册》中的相关知识，处理网络层的协议数据：在给定的流量片段中，有一些是对你的 ICMP Echo Request 报文（也就是说，请求的 IP 和 MAC 地址都是是你拥有的，并为 `pcap` 题面中的对应关系），请你正确地回复它们。你需要构造正确的 ICMP Echo Reply 报文，以及外层的 IP 分组头、以太网帧头尾，并将这些帧按照应答顺序依次写入输出文件中。本题中只对**源地址与目的地址在同一个子网中的 `ICMP Echo Request` 报文**进行响应，而不响应其他情况（例如源地址与目的地址不在同一个网络中、ARP 请求）。

我们保证，所有 `ICMP Echo Request` 报文在数据链路层和网络层都是单播发送的（也就是说不用考虑广播地址等情况，广播地址的定义见《学习手册》），请注意正确填写回复报文在这两层的源、目标地址。如果接收到的报文中含有数据负载，则你回复的报文中也需要**原样携带**这些负载，但不要携带链路层帧中超过 IP 包尺寸后的多余数据（请忽略 Wireshark 对这部分数据的解析）。特别地，本题对输出数据中片段的时间戳有额外的要求，设 `ICMP Echo Request` 的时间戳为 $(\sec_0, \text{us}_0)$，那么你回应的 `ICMP Echo Response` 的时间戳 $(\sec, \text{us})$ 应该满足 $\sec \times 10^6 + \text{us} = \sec_0 \times 10^6 + \text{us}_0 + 1$ 并且 $0 \le \text{us} < 10^6$，数据保证 $\text{us}_0 < 10^6, \sec < 2^{32}$，不保证上述加法不会溢出 32 位无符号整数。注意 Wireshark 界面上部显示的时间是相对于第一个以太网帧的时间戳的偏差。

inputFormat: 输入包含不超过 $n$ 个流量片段，总大小不超过 $m$ 字节。

hint:
**【子任务】**

本题的各子任务规模与上一题相同。

**【样例 1】**

见题目附件 `1.in/ans`。

**【样例解释 1】**

样例中输入数据是三个 `ICMP Echo Request` ，输出数据是三个对应的 `ICMP Echo Reply`。

**【提示】**

请不要忘记前三题题面中与本题相关的内容，并注意 FCS 和 IP 校验和的计算和以太网帧的长度要求。


title: [THUSC 2019] RIP 路由协议实现

background: 支持了链路层和网络层的协议以后，路由器立刻了收到无数的数据包。虽然芃芃被大量的数据淹没，不过镇定的他还是记起来教材上写的话：网络设备能够处理的报文有两种，分别是控制报文和数据报文。对于路由器来说，数据报文就是需要转发的内容；而控制报文则是用来管理它的转发流向（路由表）的。为了和其他真实的路由器进行交互，你需要实现简单的路由协议 RIP；而在建立了转发表之后，需要开始进行“抛热土豆”，正确地将其他主机的流量送到对应的下一台路由器。

description:
你需要根据《学习手册》中的相关知识，处理下列两类报文：

一类是 RIP 路由协议的控制报文，它被封装在 UDP 协议数据报中。你将只会收到 `RIP Response` 报文，且目标 IP 地址是 `224.0.0.9`，目标 MAC 地址为 `01:00:5E:00:00:09`，用于指示路由表的更新，你需要根据源 IP 地址来判断它与你拥有的哪一个 IP 在同一个子网中，从而得知路由表中对应的出端口编号。对于收到的每一条路由信息，你需要根据给定的规则（见《学习手册》）恰当维护自身的路由表，记录对于可达的每一个网络前缀的下一跳信息（包括 IP 和 MAC）。对于控制报文，总是无需进行回复。

另一类是数据报文，它将被封装在 IP 分组中，你需要对**目标 IP 地址非本机所拥有**的分组进行转发。如果路由表中能够查询到目标 IP 地址对应的下一跳，则你应当构造一个合法的 IP 分组，填写正确的源、目标信息，并更新相关字段（如 TTL、校验和）；如果无法查询到路由信息，则你应当构造一个正确的 `ICMP Destination Network Unreachable` 报文返回给源主机；如果分组的 TTL 减小到 0，则你应当构造一个正确的 `ICMP Time Exceeded` 报文返回给源主机，这两种错误信息都需要按照《学习手册》的要求填入相应的负载，从接收者 MAC 地址中推断出源地址 IP ，并且以太网帧中（接收者的 MAC 地址，发送者的 MAC 地址）为输入数据中对应数据报文的（发送者的 MAC 地址，接收者的 MAC 地址）；如果同时出现无法查询到路由信息并且 TTL 减到 0 的情况，应当构造一个 `ICMP Destination Network Unreachable`。无论何种情况，对于一个目标 IP 地址不属于本机的数据报文，你实现的路由器**总会产生**一个发出的以太网帧。

由于转发报文需要填写下一跳的 MAC 地址，而我们不提供主动的 ARP 查询接口；在本小题中，你需要并仅从 RIP 报文的**以太网帧头**中获得相应目的路由器的 MAC 地址，以**转发前最后一次获得到的为准** 。

我们保证，在此问题给出的正常流量片段（也就是通过了校验的片段）中，包含且只包含上述两类报文；并且对于所有需要转发的包，你都能通过上述方法从 RIP 报文中获得对应目的路由器的 MAC 地址。和上题类似，Wireshark 会显示 UDP 校验值错误，忽略即可。

inputFormat: 输入包含不超过 $n$ 个流量片段，总大小不超过 $m$ 字节。根据输入，你需要构造的路由表的项目不超过 $k$ 条，需要查询路由表进行转发的报文占总报文的数量约为 $p_{query}\%$。


title: 「SMOI-R1」Company

background: LAR 被老板炒了，下面都是他的梦。

description:
城市中有 $n$ 所公司，第 $i$ 所公司有 $m_i$ 个人。

一所公司可以用一棵**根为 $1$ 的**树来表示，**最初时**节点 $1$ 是老板，每个节点的子节点都是他的下属，每个节点的父节点都是他的上司。第 $i$ 棵树的大小为 $m_i$，节点从 $1$ 到 $m_i$ 编号。

公司很多，政府管理起来非常麻烦，所以政府想让 LAR 把这些公司合并起来。两所公司要合并起来，需要**一所**公司的一名**最初没有下属**的人（员工或**老板**）成为**另一所**公司现在的**老板的上司**。当两个公司合并完，两所公司就是**一所公司**了。

只有**互为上司和下属**的两个人才认识。

myz 是第 $1$ 棵树的节点 $x$，ljs 是第 $2$ 棵树的节点 $y$。因为 myz 和 ljs 性格十分不相符（他们不认识），所以 LAR 想让他们的**关系越远越好**。

互相认识的人距离为 $1$，**两人的关系**定义为两人的人际关系网上的最短距离（可以简单认为是最终形成的树中两点的最短距离）。例如，$1$ 认识 $2$，$2$ 认识 $3$，那么 $1$ 和 $3$ 的关系就是 $2$。

inputFormat:
第一行有一个整数 $n$，代表公司数量。

第二行到第 $n+1$ 行中，第 $i + 1$ 行第一个整数是 $m_i$，代表第 $i$ 所公司的人的数量。接下来有 $m_i - 1$ 个整数，第 $j$ 个数代表这棵树中节点 $j+1$ 的上司。

第 $n+2$ 行有两个整数 $x$ 和 $y$，代表 myz 是第 $1$ 棵树的节点 $x$，ljs 是第 $2$ 棵树的节点 $y$。

outputFormat: 输出一个整数，代表 myz 和 ljs 关系的最大值。

hint:
### 样例解释
在还没有进行合并操作时，城市中公司如下（括号中的数是节点**初始时**所在的公司）：
![](https://cdn.luogu.com.cn/upload/image_hosting/1g1uvci4.png)

想要让关系值最大，可以让最终的公司形成下图的样子：
![](https://cdn.luogu.com.cn/upload/image_hosting/cj518ep6.png)

答案为 $8$。
### 数据范围
**本题采用捆绑测试**。

subtask编号|$n\leq$|$\sum m \leq$|特殊情况|分值
-|-|-|-|-
$1$|$2$|$10^3$|无|$20$
$2$|$10^5$|$10^6$|$x = 1$，$y=1$|$20$
$3$|$10^5$|$10^6$|所有树都是随机树|$20$
$4$|$10^5$|$10^6$|无|$40$

**随机树产生规则**：对于节点 $i$ （$2 \le i \le m$）的上司从 $1$ 到 $i - 1$ 中**等概率**产生。

对于 $100\%$ 的数据，$2\leq n\leq 10^5$，$1 \le m_i$，$\sum m \leq 10^6$，$1\leq x\leq m_1$，$1\leq y\leq m_2$。


title: 【MX-S3-T2】「FeOI Round 1」Journey

description:
小 W 最近正在学习某编程语言。

这个编程语言有个语句如下：

```
range(a,b,c)
```

这个语句表示一个序列，这个序列是这样的：

$$
[a,a+c,a+2c,\cdots,a+kc]
$$

其中，$k$ 是最大的满足 $a+kc<b$ 的非负整数 $k$。例如 `range(1,7,2)` 表示的序列为 $[1,3,5]$。

小 W 想问你一个问题：给你一个长为 $n$ 的序列 $g$（下标从 $1$ 开始），求出下列式子的值，答案模 $10^9 +7$。

$$
\sum_{a=1}^{n}\sum_{b=a+1}^{n+1}\sum_{c=1}^{n}\sum\limits_{i\in \mathrm{range}(a,b,c)} g_i
$$

inputFormat:
为了加快读入速度，我们采用以下读入方法。

读入共一行五个非负整数 $n,A,B,C,g_n$。

其中 $n$ 为序列 $g$ 的长度，$A,B,C$ 为生成数据的参数，$g_n$ 为序列 $g$ 的第 $n$ 项。

对于序列 $g$ 的第 $i$（$1\leq i < n$）项，满足 $g_i \equiv Ag_{i+1}^2+Bg_{i+1}+C \pmod {10^9 + 7}$。

outputFormat: 共一行一个非负整数，为题目中所求的答案。


title: [GESP202403 四级] 做题

description:
小杨同学为了提高自己的实力制定了做题计划，在第 $k$ 天时，他必须要完成 $k$ 道题，否则他就会偷懒。

小杨同学现在找到了一个题库，一共有 $n$ 套题单，每一套题单中有一定数量的题目。但是他十分挑剔，每套题单他只会使用一次，每一天也只能使用一套题单里的题目，之后那套题单就会弃之不用。对于每套题单，他不必完成题单内所有的题。

那么问题来了，小杨同学最多做题几天才偷懒呢？

inputFormat:
第一行，一个整数为 $n$，表示有多少套题单。
第二行 $n$ 个整数 $a_1, a_2, \dots a_n$，分别表示每套题单有多少道题。

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

hint:
### 数据规模与约定
对全部的测试数据，保证 $1 \leq n \leq 10^6$，$1 \leq a_i \leq 10^9$。


title: 「SMOI-R1」Game

background: myz 很喜欢玩一款病毒游戏。

description:
在这个游戏里，一开始有 $n$ 个病毒，每个病毒的危害值为 $1$。

每隔一段时间，病毒就会变异，会分裂成两个病毒，右边的病毒会比左边的病毒危害值多 $1$，变异过的病毒不会再变异。

每个病毒有个变异极限 $b_i$，当这个病毒变异到 $b_i$ 时，这个病毒就会停止变异。也就是说，第 $i$ 个病毒最后都会分裂成一个危害值为 $\{1,2,3,\ldots,b_i\}$ 的病毒序列，当所有病毒变异完时，游戏开始，最终变异完的序列是 $\{1,2,3,\ldots,b_1,1,2,3,\ldots,b_2,\ldots,1,2,3,\ldots,b_n\}$。

每次游戏，系统会选择一个区间，myz 需要把这个区间的病毒全部杀死，如果这个区间内的病毒的危害值的最大值是 $x$，那么 myz 需要花费 $x$ 的能量才能消灭它们。

因为不知道系统会选择哪个区间，myz 想知道每个区间需要消耗的**能量值之和**。

由于答案太大了，myz 想让你把答案对 $998244353$ 取模。

inputFormat:
第一行有一个整数 $n$，表示最开始有 $n$ 个病毒。

第二行有 $n$ 个整数，第 $i$ 个整数是 $b_i$，表示第 $i$ 个病毒的变异上限。

outputFormat: 一个整数，表示 myz 需要消耗的能量值之和，答案对 $998244353$ 取模。


title: [AHOI2024 初中组] 家庭作业

description: 小可可有 $T$ 道形如 $a + b = c$ 的计算题，你要检验她每道题目做的对不对。

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

接下来 $T$ 行，每行一个形如 `a+b=c` 的算式。保证数据格式正确，数字没有前导零，且数字和运算符之间没有空格隔开。

具体格式可参见样例。

outputFormat: $T$ 行，如果第 $i$ 个算式正确，则在第 $i$ 行输出 `Right!`，否则在第 $i$ 行输出 `Wrong!`。

hint:
### 样例 1 解释

为了不侮辱各位同学的智商，样例不予解释。（出题人的 PDF 中没有样例解释！）

### 数据范围

对于 $40\%$ 的数据，$a = b = 1$，$c = 2$。

对于 $80\%$ 的数据，$a,b,c \le 9$。

对于 $100\%$ 的数据，$1 \le T \le 10$，$1 \le a,b,c \le 99$。


title: [AHOI2024 初中组] 立方根

background:
**特别提示：**

1. 请使用 `(int) cbrt(x + 0.5)` 计算 $\lfloor \sqrt[3]{x} \rfloor$ 的值，否则可能会出现精度误差。
2. 本题包含两组针对时间复杂度为 $O(q\sqrt[3]{x})$ 的算法的 hack 数据（#11 和 #12）。

description:
小可可想计算所有不大于 $x$ 的正整数的立方根下取整之和，但是她不会做，你能帮帮她吗？

为了彻底帮小可可弄懂这个问题，你需要回答 $q$ 组询问，对于每组询问给定的一个正整数 $x_i$，输出：

$$\sum _{j=1} ^{x_i} \lfloor j^{\frac{1}{3}} \rfloor$$

其中，$\lfloor x \rfloor$ 表示不大于 $x$ 的最大整数。

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

接下来 $q$ 行，第 $i$ 行一个正整数 $x_i$。

**保证给出的 $\bm{x_1 \sim x_q}$ 单调不降。**

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

**请注意答案的范围。**


title: [AHOI2024 初中组] 操作

description:
小可可有一个数组 $\{a_n\}$（初始值为 $\{a_n\}=\{0,0,\ldots,0\}$）和从左到右的 $m$ 个机器，其中第 $i$ 个机器有类别 $o_i \in \{1,2\}$ 和参数 $x_i,y_i$。第 $i$ 个机器执行的操作如下：

- 若 $o_i=1$，则将 $a_{(x_i)}$ 加上 $y_i$，此时保证 $1 \le x_i \le n$，$1 \le y_i \le 10^4$。
- 若 $o_i=2$，则执行第 $x_i \sim y_i$ 个机器的操作各一次，此时保证 $1 \le x_i \le y_i \le i-1$。
- 特别地，保证 $o_1=1$。

现在，小可可依次执行了第 $c_1,c_2,\ldots,c_k$ 个机器的操作各一次，她想知道最后得到的数组 $\{a_n\}$ 是什么。

由于数组中元素的值可能很大，你只需要帮她求出每个元素除以 $10007$ 的余数即可。

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

接下来一行 $k$ 个正整数 $\{c_k\}$。

接下来 $m$ 行，第 $i$ 行三个正整数 $o_i,x_i,y_i$。

outputFormat: 一行 $n$ 个非负整数，表示数组 $\{a_n\}$ 中每个元素的值除以 $10007$ 的余数。

hint:
### 样例 1 解释

先执行第 $1$ 个机器的操作，给 $a_1$ 加上了 $2$。

然后执行第 $2$ 个机器的操作，它操作了第 $1$ 个机器，给 $a_1$ 加上了 $2$。

然后执行第 $3$ 个机器的操作。它先操作了第 $1$ 个机器，给 $a_1$ 加上了 $2$；然后操作了第 $2$ 个机器，第 $2$ 个机器又操作了第 $1$ 个机器，给 $a_1$ 加上了 $2$。

综上所述，最后得到的数组为 $\{8,0\}$。

### 数据范围

对于 $10\%$ 的数据，$n,m,k \le 10$。

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

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

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

对于 $100\%$ 的数据，$1 \le n,m,k \le 2 \times 10^5$，$1 \le c_i \le n$，$o_i \in \{1,2\}$，$o_1=1$。此外，对于第 $i$ 个机器，保证：

- 若 $o_i=1$，则 $1 \le x_i \le n$，$1 \le y_i \le 10^4$。
- 若 $o_i=2$，则 $1 \le x_i \le y_i \le i-1$。


title: [AHOI2024 初中组] 计数

description:
小可可做了一个梦，梦里从左到右有 $n$ 个糖果，每种糖果有一个颜色，用 $[1, m]$ 之间的一个正整数表示。

小可可每次会选择两个颜色相同的糖果，把它们以及它们之间的所有糖果吃掉。

小可可记得，对于梦里的糖果序列，存在一种方法把所有糖果吃完。

小可可醒来后忘记了梦中的糖果序列是什么，你能帮她求求在所有 $m^n$ 个可能的糖果序列中，有多少个糖果序列可能在小可可梦中（即存在一种全部吃完的方式）吗？

由于结果可能很大，你只要求出它除以 $10^9+7$ 得到的余数即可。

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

outputFormat: 一行一个非负整数，表示答案除以 $10^9+7$ 得到的余数。


title: 「CROI · R2」01-string

description:
给定两个长度为 $n$ 的 $01$ 串 $S,T$，你可以对串 $S$ 执行无限次操作，每次都可以从以下操作中任选一个执行：

- 选择两个正整数 $l,r(1\le l\le r\le n)$，将 $S_l\dots S_r \ 01$ 反转。

- 选择两个正整数 $l,r(1\le l\le r\le n)$，将 $S_l\dots S_r $ 全部改为 $0$。

- 选择两个正整数 $l,r(1\le l\le r\le n)$，将 $S_l\dots S_r $ 全部改为 $1$。

你需要回答最少使用几次操作才能把 $S$ 变成 $T$。

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

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

对于每组数据：

第一行一个 $01$ 串，表示串 $S$。

第二行一个 $01$ 串，表示串 $T$。

outputFormat: 一共 $T$ 行，第 $i$ 行一个整数，表示第 $i$ 组数据的答案。

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

以下提供样例三组数据的合法方案之一：

对于第一组数据，选取 $l=1,r=5$，将 $S_l\dots S_r$ 全部变成 $1$。

对于第二组数据，选取 $l=1,r=5$，将 $S_l\dots S_r \ 01$ 反转。

对于第三组数据，先选取 $l=4,r=8$，将 $S_l\dots S_r$ $01$ 反转，再选取 $l=5,r=8$，将 $S_l\dots S_r$ 全部变成 $0$。

**【数据范围】**

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

- Sub 0（10 points）：$n\le 5$。
- Sub 1（10 points）：$n\le 18$。
- Sub 2（30 points）：$n\le 2000$。
- Sub 3（50 points）：无特殊限制。

对于所有的数据，$1\le T \le 10$，$1\le n\le 5\times 10^5$。


title: [PA2024] Modernizacja Bajtocji

background: PA 2024 1A

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 1 [Modernizacja Bajtocji](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/mod/)**

Byteland 正在走向现代化。最新的政府项目旨在为那些没有电脑的村镇居民提供电脑。Byteasar 正在监督该计划中的一个村庄——Bytetown——的现代化进程，目前那里没有一个居民拥有电脑。

Bytetown 有 $n$ 个居民，为了简单起见，Byteasar 将他们用 $1$ 到 $n$ 的整数编号。最初没有一个居民拥有电脑。Byteasar 的任务是处理三种形式的事件：

- $\texttt{+}\ a_i\ b_i$：将一台电脑送给 Bytetown 的居民。然而，Byteasar 并不知道电脑是送给了编号为 $a_i$ 还是 $b_i$ 的居民。可能会出现 $a_i = b_i$ 的情况——在这种情况下，电脑肯定送给了编号为 $a_i$ 的居民。可以确定的是，电脑被送到了目前还没有电脑的居民手中。
- $\texttt{-}\ c_i$：编号为 $c_i$ 的居民的电脑坏了。可以肯定的是，该居民曾经拥有一台电脑（但现在不再拥有，因此将来可能会收到一台新电脑）。
- $\texttt{?}\ d_i$：Byteasar 需要（利用**迄今为止**获得的所有信息）确定编号为 $d_i$ 的居民：肯定有电脑，肯定没有电脑，还是不确定他是否有电脑。

请编写一个程序，帮助 Byteasar 回答所提出的问题！

注：在居民的电脑坏掉的前一刻，Byteasar 不一定可以确定这个居民是否有电脑。换句话说，在某居民电脑坏掉之前，不一定可以从之前的事件中确定他是否有电脑。

inputFormat:
第一行包含两个整数 $n$ 和 $q\ (1\le n\le 300\, 000, 1\le q\le 1\,000\,000)$，分别表示 Bytetown 的居民人数和 Byteasar 需要处理的事件数量。

接下来的 $q$ 行描述了题目中的连续发生的事件。在所有事件中，$1 \le a_i,b_i,c_i,d_i \le n$。

保证 Byteasar 至少会被问及一次他知道的内容，即输入中至少包含一个 `?`，还保证至少有一次电脑送出过程，在这个过程中，电脑总会给一个目前不拥有电脑的人，且保证对于电脑坏掉事件中的居民，电脑坏掉时总会拥有一台电脑。

outputFormat: 输出一个字符串，其长度等于 `?` 事件的个数。如果在第 $i$ 次查询时，该居民肯定有电脑，则该字符串中的第 $i$ 个字符为 `1`。如果该居民肯定没有电脑，则该字符串中的第 $i$ 个字符应为 `0`。如果不能确定该居民是否拥有电脑，则该序列中的第 $i$ 个字符应为 `?`。

hint: 最初没有人有电脑，所以第一个询问的答案为「否」，输出的第一个字符是 `0`。然后送出了两台电脑，我们又被问到另一位居民是否有电脑。有可能迄今为止送出的两台电脑中有一台是送给他的，但也有可能电脑是分别送给第一位和第三位居民的。因此，我们无法最终确定第二位居民是否有电脑，所以答案是 `?`。需要注意的是，在下一次送出之后，第二位居民肯定已经拥有了一台电脑，但在询问 Byteasar 时，他并不知道这一点。


title: [PA2024] Liderzy

background: PA 2024 1B

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

根据 PWN 字典（一本波兰语字典），「*lider*」是指「政党、工会或其他社会组织的领导人」。另一方面，在算法中，序列中出现次数严格大于序列长度一半的元素被称为序列的领导元素。例如，序列 $[7, 2, 5, 7, 7]$ 的领导元素是数字 $7$，而序列 $[2, 3, 2, 3]$ 则没有领导元素。

在本题中，我们将重点讨论「*lider*」一词的后一种含义。给定一个数列，你的任务是将它分成最小数目的数列（不一定连续），满足每个数列都有一个领导元素，并输出这个最小数目。可以证明这样的划分总是可能的。

inputFormat:
第一行一个整数 $n\ (1\le n\le 500\,000)$，表示序列的长度。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (1\le a_i\le n)$，表示这个序列。

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

hint: 输入的序列可以划分为 $[1,3,1]$ 和 $[2,2]$，这样划分后的两个序列就都有领导元素了（分别为 $1$ 和 $2$）。


title: [PA2024] Kto wygrał?

background: PA 2024 1C

description:
**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 1 [Kto wygrał?](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/kto/)**

Algosia 和 Bytie 喜欢在 PA 中一较高下。在线上比赛中，有 $18$ 道题需要解决，每道题可获得 $0$ 到 $10$ 分。参赛者按总得分排序。如果积分相同，则在更多题中获得 $10$ 分的选手排名靠前。如果再次出现同分情况，则在更多题中获得 $9$ 分的选手排名靠前，依此类推。如果无法通过这种方式区分选手，则宣布他们之间打成平手。

Algosia 和 Bajtek 还记得上届比赛所有任务的得分，但他们不记得……谁赢了。你能帮他们编写一个程序，读取他们的成绩，并告诉他们谁的名次更高吗？

inputFormat:
第一行包含区间 $[0, 10]$ 内的 $18$ 个整数，表示 Algosia 在每道题上的得分。

第二行也包含区间 $[0, 10]$ 内的 $18$ 个整数，表示 Bajtek 在每道题上的得分。

outputFormat: 输出一行一个单词——`Algosia` 或 `Bajtek`，表示获胜者的名字。如果出现平局，则输出 `remis`（波兰语中平局的意思）。

hint: 虽然 Algosia 和 Bytie 的得分都是 $161$ 分，但根据 PA 规则，Algosia 的排名更高。