yl-9/probench huggingface dataset:
# 界分数

## 题目背景

[标分数](https://www.luogu.com.cn/problem/P8319)

## 题目描述

定义函数 $f(x)$：

有一个 $\frac{0}{x}$ 的分数。你可以进行以下两种操作直到这个分数为 $1$：

1. 分子 $+1$，然后如果这个分数可以约分，约分到最简形式。
2. 分子分母同时 $+1$，然后如果这个分数可以约分，约分到最简形式。

$f(x)$ 的值为最小操作次数。

给定 $n$，求 $\sum\limits_{i=1}^n f(i) \bmod 998244353$。

## 输入格式

一行一个正整数 $n$。

## 输出格式

一行一个自然数，表示答案。

## 样例 #1

### 样例输入 #1

```
4
```

### 样例输出 #1

```
9
```

## 样例 #2

### 样例输入 #2

```
114
```

### 样例输出 #2

```
785
```

## 样例 #3

### 样例输入 #3

```
114514
```

### 样例输出 #3

```
1930181
```

## 提示

【样例解释】

$f(1)=1$，$f(2)=2$，$f(3)=3$，$f(4)=3$（$\frac{1}{4}\rightarrow\frac{1}{2}\rightarrow 1$）。

【数据范围】

对于全部数据，$1\le n \le 10^{18}$。

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

| Subtask 编号 | 特殊性质 | 分值 |
| -----------: | -----------: |-----------: |
| 0 | $n=5$ | $5$ |
| 1 | $n\le 10$ | $20$ |
| 2 | $n\le 10^3$ | $40$ |
| 3 | $n\le 10^6$ | $25$ |
| 4 | 无特殊性质 | $10$ |

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 数论, Ad-hoc, 洛谷原创, 洛谷月赛, 洛谷比赛, 2024
Difficulty: 普及+/提高
# 众数

## 题目描述

你有 $n$ 个数对 $(a_1,b_1),\ldots,(a_n,b_n)$。

定义**下标** $i(1\le i\le n)$ 的权值为将 $a_1$ 个 $b_1$，$a_2$ 个 $b_2$，...，$a_i$ 个 $b_i$ 拼接在一起后形成的数组的**最大众数**（特别地，若所有数出现次数相同则为最大数）乘以 $a_i$。

接下来你有 $m$ 个操作，分两种：
- `1 x y`，将 $a_x$ 增加 $y$。**保证 $y$ 非负。**
- `2 q`，求最小的正整数 $k$ 使得**下标** $n-k+1 \sim n$ 的权值异或和为 $q$。

2 操作保证有解，且所有答案之和（记为 $\sum k$）不超过 $5\times 10^7$。

## 输入格式

输入的第一行有三个正整数 $T,n,m$，分别表示测试点编号（样例为 $0$，Hack 数据是 $26\sim 100$ 之间的自然数）、数对个数和操作个数。

第二行有 $2n$ 个正整数 $a_1,b_1,a_2,b_2,\ldots,a_n,b_n$，其中第 $2i-1$ 和第 $2i$ 个数分别表示第 $i$ 个数对的 $a_i,b_i$。

之后有 $m$ 行，每行有一个操作，格式见题目描述。

## 输出格式

对于每个 2 操作，输出一行一个正整数表示答案。

## 样例 #1

### 样例输入 #1

```
0 4 5
2 1 3 3 1 1 1 2
2 0
1 4 6
2 6
1 3 8
2 7
```

### 样例输出 #1

```
2
4
1
```

## 提示

【样例解释】

最开始的四个数组为 $(2,1), (3,3),(1,1),(1,2)$。以计算下标 $2,4$ 的权值为例展示权值的计算方法：

- 要计算下标 $2$ 的权值，就要把 $2$ 个 $1$、$3$ 个 $3$ 拼在一起得到 $[1,1,3,3,3]$，最大众数为 $3$；$a_2=3$，所以权值为 $3\times 3 = 9$。
- 要计算下标 $4$ 的权值，就要把 $2$ 个 $1$、$3$ 个 $3$、$1$ 个 $1$、$1$ 个 $2$ 拼在一起得 $[1,1,3,3,3,1,2]$，最大众数为 $3$；$a_4=1$，所以权值为 $3\times 1=3$。

以此类推，可知下标 $1,2,3,4$ 的权值依次为 $2,9,3,3$。当 $k=2$ 时，$3,4$ 的权值异或和 $3\oplus 3$ 恰为 $0$，符合题意。

接下来将 $a_4$ 增加 $6$ 变成 $7$，显然前 $3$ 个下标权值不变，下标 $4$ 的权值变成 $2\times 7=14$。此时所有下标权值异或和 $2\oplus 9\oplus 3\oplus 14=6$，符合题意，所以此时 $k=4$。

然后把 $a_3$ 增加 $8$ 变成 $9$。现在 $1\sim 4$ 的权值依次为 $2,9,9,7$，此时 $k=1,3$ 时对应的权值异或和都是 $7$，此时取更小的 $k$，所以输出 $1$。

【数据范围】

记 $L$ 为所有操作结束后，所有 $a_i$ 的最大值（例如样例中，$L=9$。）

|测试点编号|$n,m\le$|特殊性质|
|:-:|:-:|:-:|
|$1\sim 2$|$30$|$a_i,y\le 30$|
|$3\sim 4$|$500$||
|$5\sim 7$|$2000$||
|$8\sim 9$|$3\times 10^5$|只有 2 操作|
|$10$|$3\times 10^5$|$b_i=1$|
|$11\sim 12$|$3\times 10^5$|$b_i\le 2$|
|$13\sim 15$|$3\times 10^5$|$\sum k\le 5\times 10^5$|
|$16\sim 19$|$3\times 10^5$|$k\le 300$|
|$20\sim 25$ |$3\times 10^5$||

对于全部数据，保证 $3\le n,m\le 3\times 10^5$，且 $1\le b_i\le n$，$1\le a_i\le L\le 10^9$。

2 操作保证有解，且 $\sum k\le 5\times 10^7$。

**提示：本题读入量较大，建议选用较快的输入输出方式。**

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛
Difficulty: 省选/NOI−
# 茫茫的不归路

## 题目背景

[The English statement for T1](https://www.luogu.com.cn/problem/U508230)

You can also see the pdf at the bottom of the chinese problem statement.

NoitaCesaE 的匹配机制总是很奇怪，小 $ \zeta $ 总是被匹配到与他的其他车队成员不同的阵营，这时他就没法享受被优质队友带飞的快感了。

## 题目描述

具体的，有 $ n $ 个阵营，每个阵营最多 $ m $ 人。已经有 $ p $ 个人被分配了所属的阵营，且此时每个阵营人数均不超限。

小 $ \zeta $ 的 $ k $ 人车队进入了这个房间，在不改变已经进入的 $ p $ 个人的所属阵营的情况下，如果他们能一起进入同一个阵营使得阵营人数不超过限制，那么就会进入同一个阵营，否则车队就分散进不同的阵营了。

请求出对于给定的 $ n,m,k,p $，任意的已经进入的 $ p $ 个人的阵营归属情况下，小 $ \zeta $ 的车队能够进入同一个阵营的**可能性情况**（具体参见输出格式）。

## 输入格式

**本题多测**，第一行输入一个整数 $ T $，代表这个测试点内有 $ T $ 组数据。

对于每组数据：

一行四个整数 $ n,m,k,p $，含义见题目描述。

## 输出格式

对于每组数据，输出以下三种情况之一：

* `Together` 表示无论已经进入的人如何归属，这个车队一定能进入同一个阵营；

* `Chance` 表示存在一部分已经进入的人的阵营归属情况，使得这个车队的所有人进入同一个阵营；

* `Divide` 表示无论已经进入的人如何归属，这个车队的所有人必然进入不同的阵营。

## 样例 #1

### 样例输入 #1

```
10
3 3 3 1
3 3 4 5
4 4 4 12
4 4 3 8
10 10 7 34
10 10 8 34
12 11 11 12
12 11 12 12
9 9 1 80
9 9 6 70
```

### 样例输出 #1

```
Together
Divide
Chance
Chance
Together
Chance
Chance
Divide
Together
Chance
```

## 提示

**【样例 1 解释】**

对于第一组数据，无论这个人在哪个阵营，都有至少两个阵营为空，因此一定可以容纳这个 $ 3 $ 人车队，故输出 `Together`。

**【数据规模与约定】**

对于 $ 40\% $ 的数据，$ T \le 10 $，$ n,m \le 4 $，$ k \le 6 $，$ p \le 10 $。

对于另 $ 20\% $ 的数据，保证输出没有 `Together`。

对于 $ 100\% $ 的数据，$ 1 \le T \le 1000 $，$ 1 \le n,m \le 10^4 $，$ 1 \le k \le 10^8 $，$ 0 \le p \le 10^8 $，$ p+k \le n \times m $。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 鸽笼原理, 分类讨论, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及−
# 纷飞的樱花雨

## 题目背景

[The English statement for T2](https://www.luogu.com.cn/problem/U508231)

You can also see the pdf at the bottom of the chinese problem statement.

高中的时候做过樱花雨实验，氯化钴遇到氢氧化钠溶液产生的沉淀物就像是一场铺天盖地的樱花雨。

小 $ \zeta $ 问她，你见过樱花吗？

她抬头摇起眼睛，碎亮的光倒映在少女乌黑的瞳孔里。

她侧头定定看了我一会儿，然后淡淡地笑了。

她说，「我知道你想考武汉大学。」

「我也会去武汉大学。」

「今年九月，你要和我一起去看樱花吗？」

## 题目描述

小 $ \zeta $ 喜欢观赏樱花。

$ n $ 朵樱花的掉落过程中，第 $ i $ 个掉落的樱花的美丽度为 $ a_i $。

每朵樱花掉落后，樱花掉落的总观赏度会增加这朵樱花及之前所有已经掉落的樱花的美丽度的最大值。

交换**正好** $ k $ 次两朵樱花的掉落顺序（不能交换一朵樱花和本身，但可以重复交换两朵樱花），最大化总观赏度的值。

形式化地讲，给出一个长度为 $ n $ 的数组，进行正好 $ k $ 次交换使得 $ \sum_{i=1}^n \max_{j=1}^ia_j $  最大。

## 输入格式

**本题多测**，第一行输入该测试点内数据组数 $ T $。

对于每组测试数据：

第一行两个整数 $ n $ 和 $ k $，含义见题目描述。

接下来 $ n $ 个空格分隔的整数，第 $ i $ 个代表 $ a_i $ 的初始值。

## 输出格式

对于每组测试数据，输出一行一个整数表示题目要求的值。

## 样例 #1

### 样例输入 #1

```
3
3 0
9 8 2
2 1
10 11
5 10
1 2 3 4 5
```

### 样例输出 #1

```
27
22
25
```

## 样例 #2

### 样例输入 #2

```
5
5 0
100 101 102 103 104
5 1
20 40 50 70 10
2 103
30 20
7 2
1 2 3 4 5 6 7
2 10
1 1
```

### 样例输出 #2

```
510
350
50
49
2
```

## 提示

**【样例 1 解释】**

第二组数据可以将 $ 10 $ 和 $ 11 $ 交换，观赏度总和为 $ 11+11=22 $。

**【数据规模与约定】**

对于 $ 100\% $ 的数据，$ 1 \le T \le 500 $，$ 2 \le n \le 10^5 $，$ 0 \le k \le 10^9 $，$ \sum n \le 10^6 $，$ 1 \le a_i \le 10^9 $。

**本题测试点等分，按测试点加和计分。**

| 测试点编号 | $ n $ | $ k $ |
|:-:|:-:|:-:|
| $ 1 $ | $ \le 50 $ | $ =0 $ |
| $ 2 $ | - | $ =0 $ |
| $ 3 \sim 4 $ | $ \le 50 $ | $ =1 $ |
| $ 5 \sim 7 $ | - | $ =1 $ |
| $ 8 \sim 10 $ | - | - |

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 贪心, 分类讨论, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及−
# 无穷的迭代器

## 题目背景

[The English statement for T3](/problem/U508232)

You can also see the pdf at the bottom of the chinese problem statement.

## 题目描述

对于实数 $ r $，记一次操作为：

* 找到不小于 $ r $ 的最小整数即 $ \lceil r \rceil $，并将 $ r $ 的值乘上 $ \lceil r \rceil $。

现在给定非负整数 $ k $，对于 $ r=k+\frac{1}{2} $，至少需要对 $ r $ 进行几次操作才能使 $ r $ 为整数？

## 输入格式

本题多测，第一行一个整数 $ T $ 代表数据组数。

对于每组数据：

一行一个整数 $k$，含义见题目描述。

## 输出格式

对于每组数据：

若可以变成整数，输出一行一个整数代表你找到的最小的次数。

若不能变成整数，输出一行 `NO!`。

## 样例 #1

### 样例输入 #1

```
1
4
```

### 样例输出 #1

```
3
```

## 样例 #2

### 样例输入 #2

```
1
0
```

### 样例输出 #2

```
NO!
```

## 提示

**【样例 1 解释】**

| 操作次数 | $ r= $ |
|:-:|:-:|
| 初始 | $ \frac{9}{2} $ |
| $ 1 $ | $ \frac{45}{2} $ |
| $ 2 $ | $ \frac{1035}{2} $ |
| $ 3 $ | $ 268065 $ |

**【数据规模与约定】**

**提示：本题采用捆绑计分。**

对于 $ 100\% $ 的数据，$ 1 \le T \le 20 $，$ 0 \le k \le 10^{18} $。

* Subtask 1（15 pts）：$ 1 \le k \le 10 $。
* Subtask 2（40 pts）：$ 1 \le k \le 100 $。
* Subtask 3（45 pts）：$ 0 \le k \le 10^{18} $。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及/提高−
# 漫长的小纸带

## 题目背景

[The English statement for T4](https://www.luogu.com.cn/problem/U508235)

You can also see the pdf at the bottom of the chinese problem statement.

小 $ \zeta $ 是一个喜欢打暴力的 OIer。在每次模拟赛中，他秉持着“10 分钟想不出来正解那就把暴力糊上去”的理念，每次都稳定地拿到很高的分数；平时训练时，他会关注题目的部分分，针对部分分任务进行求解，有时在部分分求解上使用的时间比这个题正解的思考都长。

## 题目描述

小 $ \zeta $ 经过了几年的暴力训练，暴力水平更是炉火纯青。在 S-PSC 2077 的比赛中，他惊喜的发现第二题《漫长的小纸带》是一道很困难的题目，正适合他这种暴力选手发挥。

这道题目是多测题目，在某个测试点内有 $ n $ 组数据，第 $ i $ 组数据的规模为 $ a_i $。他写出了一个暴力程序，对于一段连续的数据，程序解决这段数据需要消耗的时间为这段数据中出现的不同的 $ a_i $ 的种类数平方。形式化地讲，对于一个从第 $ l $ 组到第 $ r $ 组的连续的数据段，记 $ S=\{a_i|l \le i \le r\} $，程序需要消耗 $ |S|^2 $ 的时间来一起解决它们。

现在，他给你 $ n $ 和 $ n $ 组数据的规模，请找到一种将这些数据划分成若干个数据段的方案，使得程序消耗的总时间最短。

## 输入格式

第一行一个整数 $ n $。

接下来一行 $ n $ 个整数 $ a_i $，代表每一组测试数据的规模。

## 输出格式

输出一个数代表总时间消耗。

## 样例 #1

### 样例输入 #1

```
5
1 2 3 4 5
```

### 样例输出 #1

```
5
```

## 样例 #2

### 样例输入 #2

```
6
1 2 2 1 2 3
```

### 样例输出 #2

```
5
```

## 样例 #3

### 样例输入 #3

```
9
1 2 1 4 1 2 1 1 2
```

### 样例输出 #3

```
8
```

## 样例 #4

### 样例输入 #4

```
21
1 2 1 2 1 2 1 2 1 2 3 4 5 6 7 1 2 1 2 1 2
```

### 样例输出 #4

```
13
```

## 提示

**【样例 3 解释】**

分段方式为：

* 第一段 $ \{1\} $，消耗为 $ 1 $。
* 第二段 $ \{2\} $，消耗为 $ 1 $。
* 第三段 $ \{1\} $，消耗为 $ 1 $。
* 第四段 $ \{4\} $，消耗为 $ 1 $。
* 第五段 $ \{1,2,1,1,2\} $，消耗为 $ 4 $。

故程序总共消耗的时间为 $ 8 $。

**【数据范围】**

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

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

| 子任务编号 | $ n \le $ | 特殊性质 | 分数 |
|:-:|:-:|:-:|:-:|
| $ 1 $ | $ 10 $ | - | $ 8 $ |
| $ 2 $ | $ 300 $ | - | $ 8 $ |
| $ 3 $ | $ 2000 $ | - | $ 16 $ |
| $ 4 $ | - | A | $ 16 $ |
| $ 5 $ | - | B | $ 24 $ |
| $ 6 $ | - | - | $ 28 $ |

特殊性质 A：所有的 $ a_i $ 在 $ [1,10^9] $ 内等概率随机生成，且本子任务只有 $ 1 $ 个测试点。

特殊性质 B：$ 1 \le a_i \le 1000 $。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 动态规划 DP, 排序, 洛谷原创, 洛谷月赛
Difficulty: 提高+/省选−
# 神奇的小江鸟

## 题目背景

[The English statement for T5](https://www.luogu.com.cn/problem/U508234)

You can also see the pdf at the bottom of the chinese problem statement.

感谢 [ineverleft](https://www.luogu.com.cn/user/362679) 为本题提供的本地调试 checker。

「愿有前程可奔赴，亦有岁月可回首。」

## 题目描述

小 $ \zeta $ 在探险过程中看到了一个大锁。

这个大锁有 $ n $ 个拨圈，第 $ i $ 个拨圈的拨动范围为 $ l_i $ 到 $ r_i $ 之间（含两个边界）的所有整数（保证 $ l_i \le r_i $）。

我们定义这个大锁的「自由度」为所有拨圈上的数的**最大公约数**，当锁的「自由度」大于等于 $ k $ 时，会被打开。

请你找到一种锁的开启方案，或报告无解。

## 输入格式

**本题单测试点内含有多组测试数据**，第一行一个整数 $ T $，代表数据组数。

对于每组数据：

第一行两个整数 $ n,k $，分别代表拨圈数量和自由度限制。

接下来 $ n $ 行，每行两个整数 $ l_i,r_i $，含义见题目描述。

## 输出格式

对于每组数据：

* 如果有解，第一行输出 `Yes`，下一行输出 $ n $ 个空格分隔的整数，第 $ i $ 个为你的构造方案中第 $ i $ 个拨圈显示的数。**本题使用了 Special Judge，符合要求的答案均判对。**

* 否则，输出一行 `No` 表示无解。

## 样例 #1

### 样例输入 #1

```
1
5 10
1 12
44 50
9 10
88 99
29 99
```

### 样例输出 #1

```
Yes
10 50 10 90 30
```

## 样例 #2

### 样例输入 #2

```
2
3 11
99 10003
39 299
39 10003
5 55
1 54
1 20
1 300
1 300
1 300
```

### 样例输出 #2

```
Yes
123 246 369
No
```

## 样例 #3

### 样例输入 #3

```
3
6 1
1 10
1 10
1 10
1 10
1 10
1 10
5 4
11 15
6 10
9 14
20 23
27 29
5 11
20 30
50 70
111 120
72 77
119 121
```

### 样例输出 #3

```
Yes
1 1 4 5 1 4
Yes
14 7 14 21 28
Yes
24 60 120 72 120
```

## 样例 #4

### 样例输入 #4

```
4
3 33
32 34
65 67
97 101
3 5
299 99494993
499 49992999
499 39999939
4 25
719 830
2194 2893
132 142
199 225
3 10
140 143
131 135
238 241
```

### 样例输出 #4

```
Yes
33 66 99
Yes
1919810 11400 51400
Yes
729 2700 135 216
No
```

## 样例 #5

### 样例输入 #5

```
1
10 7
77 77
82 174
77 77
82 174
77 77
82 174
77 77
82 174
77 77
82 174
```

### 样例输出 #5

```
Yes
77 154 77 154 77 154 77 154 77 154
```

## 提示

**【样例 1 解释】**

唯一的一组数据 $ \gcd $ 为 $ 10 $。

五个样例自测均可使用下发的附件。**请注意部分样例可能存在多解，样例输出仅列举了一组可行解。**

**【数据规模与约定】**

对于 $ 100\% $ 的数据，$ 1 \le T \le 5 $，$ 2 \le n \le 10^4 $，$ 1 \le l_i \le r_i \le 10^9 $，$ 1 \le k \le 1000 $。

**本题开启子任务捆绑测试。**

* Subtask 1（10 pts）：$ k=1 $。
* Subtask 2（15 pts）：$ n \le 10 $，$ r_i - l_i + 1 \le 5 $。
* Subtask 3（15 pts）：$ r_i \le 10^3 $。
* Subtask 4（10 pts）：$ k \le 5 $，$ l_i,r_i $ 均在 $ 1 \le l_i \le r_i \le 10^9 $ 范围内等概率随机生成，该子任务只有 $ 1 $ 个测试点。
* Subtask 5（15 pts）：对于每组数据，$ \exist 1 \le i \le n,l_i=r_i $。
* Subtask 6（35 pts）：无特殊限制。

**【关于附加文件】**

**本题下发了 `checker.cpp` 作为自测器。**

请将输入内容、你的程序输出、参考答案输出分别放置在 `restore.in`、`restore.out`、`restore.ans` 中，这三个文件必须与 `checker.cpp` 在同一目录下，运行 `checker.cpp`，终端上会给出自测结果。

**你需要保证你的输入满足 $ 100\% $ 数据范围的要求。**

注意，如果你的输入/输出/答案的格式和范围不正确的话，`checker.cpp` 出现的结果是不可预料的。因此，**请先确保你的三个文件格式正确。**

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 数学, 数论, 枚举, 调和级数, 洛谷原创, 洛谷月赛, Special Judge, O2优化
Difficulty: 普及+/提高
# 「GFOI Round 2」Abstract String Basic

## 题目背景

**[English statement](https://www.luogu.com.cn/problem/T533480). You must submit your code at the Chinese version of the statement.**

## 题目描述

Charlie 正在上一门叫做《抽象字符串基础》的课。

> **定义 3.1：** 对于两个长度相同的小写字母串 $S$ 和 $T$，定义它们的**相似度**为它们相同的对应位置个数。形式化地，设 $|S|=|T|=n$，则 $S$ 和 $T$ 的相似度 $\psi(S,T)=\sum\limits_{i=1}^n\sum\limits_{j=1}^n[i=j][S_i=T_j]$。  
>
> **引理 3.1：** 对于任意小写字母串 $S$，存在唯一的小写字母串 $T$，使得 $\psi(S,T)$ 最大化。  
>
> **引理 3.1 的证明：**……

Charlie 逐渐开始神游，在纸上写写画画。忽然，他想到定义 $S$ 和 $T$ 的**不相似度**为有几对不同位置上的字符不同，即 $\tilde\psi(S,T)=\sum\limits_{i=1}^n\sum\limits_{j=1}^n[i\neq j][S_i\neq T_j]$。这个清奇的定义让 Charlie 一下子清醒了，他想到，什么样的小写字母串 $T$ 能够最大化 $S$ 和 $T$ 的**不相似度**呢？

注：$[x]$ 的方括号为艾弗森括号，其定义为：若条件表达式 $x$ 为真则 $[x]$ 取值为 $1$，否则 $[x]$ 取值为 $0$。

## 输入格式

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

第二行包含一个长度为 $n$ 的字符串 $S$，保证 $S$ 中仅含小写字母。

## 输出格式

输出一行小写字母字符串 $T$，表示你的答案。你需要使得 $S$ 与 $T$ 的**不相似度**最大化。如果有多种答案，输出任意一种均可。

## 样例 #1

### 样例输入 #1

```
9
cbbccxxxx
```

### 样例输出 #1

```
godfather
```

## 样例 #2

### 样例输入 #2

```
26
abcdefghijklmnopqrstuvwxyz
```

### 样例输出 #2

```
abcdefghijklmnopqrstuvwxyz
```

## 样例 #3

### 样例输入 #3

```
28
aabcdefghijklmnopqrstuvwxyzz
```

### 样例输出 #3

```
cybcdefghijklmnopqrstuvwxycy
```

## 提示

#### 【样例解释 #1】

当 $T=\texttt{godfather}$ 时，$\tilde\psi(S,T)=72$，取到最大值。注意答案可能不止一种。

#### 【数据范围】

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

|子任务编号  |$n\le$  |特殊性质|分值|
| :-----------: | :-----------: |:----:|:----:|
|$0$  |$28$  | 是样例 | $0$ |
|$1$  |$4$  | 无 |$20$  |
|$2$  |$10^6$  | $S$ 中不包含字符 `z` |$20$  |
|$3$  |$10^3$  | 无 |$20$  |
|$4$  |$10^6$  | 无 |$40$  |

对于所有数据，满足：

- $1 \leq n \leq 10^6$；
- $S$ 中仅包含小写字母。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛, Special Judge, O2优化
Difficulty: 普及−
# 「GFOI Round 2」Aob & Blice

## 题目背景

**[English statement](https://www.luogu.com.cn/problem/T533501). You must submit your code at the Chinese version of the statement.**

## 题目描述

Aob 和 Blice 在玩游戏。

现在有一个长为 $n$ 的排列 $p$，且 Aob 和 Blice 手里分别有一个初始为空的**不可重**集合 $S_A,S_B$。定义一轮游戏过程如下：

- 首先 Aob 会**随机**选取两个满足 $1 \leq x < y \leq n$ 且 $p_x>p_y$ 的数 $x,y$ ，然后从 $(x,y)$ 和 $(p_x,p_y)$ 这两个**有序二元组**中**随机选取一个**放入自己的集合 $S_A$ 中。

- 在这之后，Blice 会从 $(y,x)$ 和 $(p_y,p_x)$ 中选择一个放入自己的集合 $S_B$ 中。**注意这里的 $x,y$ 均为上一步中 Aob 选择的**。

在无限轮游戏之后 $^{\dagger}$，Aob 和 Blice 会比较他们手里的集合。虽然 Aob 只会随机，Blice 看起来更聪明些，但是 Blice 想要最终他们两个的集合完全相等，这样平局就不会有任何一个人伤心啦！

不幸的是，这个排列中的某些数消失了，于是 Blice 找到了你，想知道有多少种可能的原排列，使得他们两个人能够在无限轮后达成平局。为了方便，你只需要求出答案对 $998244353$ 取模的值。

$^{\dagger}$ 在“无限轮”之后 Blice 能达到平局，定义为对于任意 $\varepsilon>0$，存在一个正整数 $N$，使得对于任意 $n>N$，Blice 存在一种策略使得他在 $n$ 轮结束之后**不**平局的概率 $<\varepsilon$。

## 输入格式

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

第二行包含 $n$ 个整数 $p_i$。对于每个 $i$，若 $p_i=0$，则表示第 $i$ 位上的数消失了；否则表示原排列中第 $i$ 位上的数。

## 输出格式

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

## 样例 #1

### 样例输入 #1

```
3
0 2 0
```

### 样例输出 #1

```
2
```

## 样例 #2

### 样例输入 #2

```
7
0 3 2 0 5 7 0
```

### 样例输出 #2

```
2
```

## 提示

#### 【样例解释 #1】

两种排列都是合法的：$\{1,2,3\},\{3,2,1\}$。

#### 【数据范围】

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

| 子任务编号 | $n \leq$ | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: | :----------: |
| 1 | $9$ | 无 | $20$ |
| 2 | $2000$ | A | $15$ |
| 3 | $2000$ | 无 | $10$ |
| 4 | $10^6$ | A | $15$ |
| 5 | $10^6$ | B | $10$ |
| 6 | $10^6$ | 无 | $30$ |

- 特殊性质 A：$p_i \ne 0$。
- 特殊性质 B：$p_i = 0$。

对于所有数据，满足：

- $1 \le n \le 10^6$；
- $0 \le p_i \le n$；
- 对于任意 $1 \le i < j \le n$，若 $p_i \ne 0$ 且 $p_j \ne 0$，则 $p_i \ne p_j$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛, O2优化
Difficulty: 提高+/省选−
# 「GFOI Round 2」Colors

## 题目背景

**[English statement](https://www.luogu.com.cn/problem/T533508). You must submit your code at the Chinese version of the statement.**

> 世界が鮮やかに 染まって

## 题目描述

有 $n$ 个球排成一排，从左到右依次编号为 $1 \sim n$。每个球初始都是红色的。第 $i$ 个球的初始权值为 $p_i$。**保证 $\bm{n}$ 为奇数且 $\bm{p}$ 是一个 $\bm{1 \sim n}$ 的排列。**

你需要恰好进行 $\frac{n - 1}{2}$ 次操作。在一次操作中，你需要：

- 选择一个**红色**的球 $i$，使得 $1 \sim i - 1$ 中至少有一个红球且 $i + 1 \sim n$ 中至少有一个红球。
- 设 $j$ 为最大的整数使得 $j < i$ 且球 $j$ 为红球，$k$ 为最小的整数使得 $k > i$ 且球 $k$ 为红球。你要将球 $i$ 和球 $k$ 都染成蓝色。
- 然后进行以下两种操作的**恰好一个**：
	- 将 $p_j$（即球 $j$ 的权值）修改为 $\max(p_i, p_j, p_k)$；
    - 将 $p_j$（即球 $j$ 的权值）修改为 $\min(p_i, p_j, p_k)$。

容易发现进行了 $\frac{n - 1}{2}$ 次操作后恰好剩下一个红球。

你需要对于每个 $1 \sim n$ 的正整数 $x$，求出是否能合理地进行操作，使得最后剩下的红球的权值为 $x$。

## 输入格式

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

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

对于每组测试数据：

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

第二行包含 $n$ 个正整数 $p_1, p_2, \ldots, p_n$。

## 输出格式

对于每组数据，输出一行一个 $01$ 串。对于每个 $1 \sim n$ 的正整数 $i$，若能合理地进行操作使得最后剩下的红球的权值为 $i$，那么这个 $01$ 串的第 $i$ 位为 $1$，否则为 $0$。

## 样例 #1

### 样例输入 #1

```
4
3
3 2 1
5
1 3 5 2 4
5
5 4 3 1 2
9
4 7 3 6 1 2 5 8 9
```

### 样例输出 #1

```
101
11111
11101
111111101
```

## 提示

#### 【样例解释】

对于第一组数据，初始的球的状态（颜色和权值）依次为 $\color{red}{3\ 2\ 1}$。

你需要进行 $1$ 次操作。在这次操作中你只能选择球 $2$，将球 $2$ 和球 $3$ 染成蓝色。

- 若你选择将 $p_1$ 修改为 $\max(p_1, p_2, p_3)$，那么操作后球的状态变为 $\color{red}{3}\ \color{blue}{2\ 1}$，最后剩下的红球的权值为 $3$；
- 若你选择将 $p_1$ 修改为 $\min(p_1, p_2, p_3)$，那么操作后球的状态变为 $\color{red}{1}\ \color{blue}{2\ 1}$，最后剩下的红球的权值为 $1$。

所以你输出一个 $01$ 串需要使得第 $1$ 和第 $3$ 位为 $1$，其余位为 $0$。

对于第二组数据，容易证明最后剩下的红球权值可以取 $1 \sim n$ 之间的所有正整数。下面给出一个能使得最后剩下的红球权值为 $2$ 的操作过程：

- 初始的球的状态为 $\color{red}{1\ 3\ 5\ 2\ 4}$。
- 选择球 $2$，将球 $2$ 和球 $3$ 染成蓝色，并将 $p_1$ 赋值为 $\max(p_1, p_2, p_3) = 5$。操作后球的状态变为 $\color{red}{5}\ \color{blue}{3\ 5}\ \color{red}{2\ 4}$。
- 选择球 $4$，将球 $4$ 和球 $5$ 染成蓝色，并将 $p_1$ 赋值为 $\min(p_1, p_4, p_5) = 2$。操作后球的状态变为 $\color{red}{2}\ \color{blue}{3\ 5\ 2\ 4}$。

#### 【数据范围】

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

| 子任务编号 | $n \le$ | $\sum n \le$ | 特殊性质 | 分值 |
| :-: | :-: | :-: | :-: | :-: |
| $1$ | $5$ | $10^4$ | 无 | $16$ |
| $2$ | $19$ | $10^4$ | 无 | $19$ |
| $3$ | $99$ | $10^6$ | 无 | $19$ |
| $4$ | $10^6 - 1$ | $10^6$ | A | $3$ |
| $5$ | $10^6 - 1$ | $10^6$ | 无 | $43$ |

- 特殊性质 A：$p_i = i$。

对于所有数据，满足：

- $1 \le T \le 10^5$；
- $3 \le n \le 10^6 - 1$ 且 $n$ 是奇数；
- $\sum n \le 10^6$；
- $p$ 是一个 $1 \sim n$ 的排列。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 分类讨论, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 提高+/省选−
# 「GFOI Round 2」Turtle and Nediam

## 题目背景

**[English statement](https://www.luogu.com.cn/problem/T533511). You must submit your code at the Chinese version of the statement.**

## 题目描述

对一个元素互不相同的长度 $\ge 3$ 的正整数序列 $a$，定义 $a$ 的“肿胃数（nediam）”$f(a)$ 为：

- 当 $|a| = 3$ 时，$f(a)$ 为 $a$ 的中位数；
- 当 $|a| > 3$ 时，取 $a$ 的任意一个长度为 $3$ 的子段 $[a_i, a_{i + 1}, a_{i + 2}]$，记这个子段的中位数为 $x$，$a$ 删掉 $x$ 后的序列为 $b$，$f(a)$ 为所有 $b$ 中 $f(b)$ 的最大值。

乌龟给你一个 $1 \sim n$ 的排列 $p_1, p_2, \ldots, p_n$ 和 $m$ 次询问，每次询问给定 $l, r$，你需要求出 $[p_l, p_{l + 1}, \ldots, p_r]$ 的“肿胃数（nediam）”，即 $f([p_l, p_{l + 1}, \ldots, p_r])$。

## 输入格式

为了加快读入速度，我们采用以下读入方法。

第一行包含六个正整数 $n, m, seed, A, B, C$。

第二行包含一个排列 $p_1, p_2, \ldots, p_n$。

接下来的 $m$ 组询问，每组询问你要按照如下的方式生成 $(l, r)$：

```cpp
unsigned seed, A, B, C;

inline unsigned rnd() {
	seed = A * seed * seed + B * seed + C;
	seed = seed ^ (seed << 27);
	seed = seed ^ (seed >> 19);
	return seed;
}

inline std::pair<int, int> gen() {
	int l, r;
	do {
		l = rnd() % n + 1;
		r = rnd() % n + 1;
	} while (abs(l - r) < 2);
	if (l > r) {
		std::swap(l, r);
	}
	return std::make_pair(l, r);
}
```

每组询问调用一次 `gen()` 生成这组询问的 $(l, r)$。

## 输出格式

为了加快输出速度，我们采用以下输出方法。

设第 $i$ 组询问的答案为 $ans_i$，你需要输出 $(1 \times ans_1) \oplus (2 \times ans_2) \oplus \cdots \oplus (m \times ans_m)$，其中 $\oplus$ 为按位异或。

## 样例 #1

### 样例输入 #1

```
4 4 114 514 1919 810
1 3 4 2
```

### 样例输出 #1

```
1
```

## 样例 #2

### 样例输入 #2

```
10 100 123456 789123 456789 123456789
3 9 5 7 6 4 10 8 2 1
```

### 样例输出 #2

```
142
```

## 提示

#### 【样例解释 #1】

生成的四组询问分别为 $(1, 4), (1, 3), (1, 3), (2, 4)$，答案分别为 $2, 3, 3, 3$，所以你需要输出 $(1 \times 2) \oplus (2 \times 3) \oplus (3 \times 3) \oplus (4 \times 3) = 2 \oplus 6 \oplus 9 \oplus 12 = 1$。

对于第一组询问，选择子段 $[1, 3, 4]$ 或 $[3, 4, 2]$ 都会使得 $3$ 被删除。删除 $3$ 后的序列为 $[1, 4, 2]$，中位数为 $2$。

#### 【数据范围】

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

| 子任务编号 | $n \le$ | $m \le$ | 特殊性质 | 分值 |
| :-: | :-: | :-: | :-: | :-: |
| $1$ | $18$ | $100$ | 无 | $9$ |
| $2$ | $10^6$ | $5 \times 10^6$ | A | $5$ |
| $3$ | $10^3$ | $10^4$ | 无 | $19$ |
| $4$ | $10^5$ | $10^5$ | 无 | $17$ |
| $5$ | $10^6$ | $10^6$ | B | $15$ |
| $6$ | $10^6$ | $10^6$ | 无 | $13$ |
| $7$ | $10^6$ | $5 \times 10^6$ | 无 | $22$ |

- 特殊性质 A：$p_i = i$；
- 特殊性质 B：$p$ 从所有 $1 \sim n$ 的排列中等概率随机生成。

对于所有数据，满足：

- $3 \le n \le 10^6$；
- $1 \le m \le 5 \times 10^6$；
- $0 \le seed, A, B, C < 2^{32}$；
- $p$ 是一个 $1 \sim n$ 的排列。

## 时空限制



时间限制
3.00s

内存限制
512.00MB

Tags: 单调栈, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 省选/NOI−
# 「GFOI Round 2」Strings

## 题目背景

**[English statement](https://www.luogu.com.cn/problem/T533519). You must submit your code at the Chinese version of the statement.**

## 题目描述

给你两个正整数 $n, m$。

我们称一个长度为 $k$ 的正整数序列 $a_1, a_2, \ldots, a_k$ 是好的当且仅当：

- $\forall i \in [1, k], 1 \le a_i \le m$；
- 存在一个正整数 $l \in [1, \frac{k}{3}]$ 满足：$\forall i \in [1, l], a_i = a_{2l + 1 - i}$。

求有多少个长度 $\le n$ 的好的序列，对 $10^9 + 7$ 取模。

## 输入格式

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

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

对于每组测试数据：

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

## 输出格式

对于每组数据，输出一行一个非负整数，表示答案对 $10^9 + 7$ 取模后的值。

## 样例 #1

### 样例输入 #1

```
4
3 2
5 3
10 4
100000 998244353123456
```

### 样例输出 #1

```
4
117
430352
967771719
```

## 提示

#### 【样例解释】

对于第一组数据，长度 $\le 3$ 的好的序列有 $[1, 1, 1], [1, 1, 2], [2, 2, 1], [2, 2, 2]$。

#### 【数据范围】

**本题采用捆绑测试且开启子任务依赖。**

| 子任务编号 | $n \le$ | $m \le$ | 子任务依赖 | 分值 |
| :-: | :-: | :-: | :-: | :-: |
| $1$ | $10^{18}$ | $1$ | 无 | $1$ |
| $2$ | $10$ | $4$ | 无 | $7$ |
| $3$ | $10^5$ | $10^{18}$ | $2$ | $28$ |
| $4$ | $10^{18}$ | $10^{18}$ | $1, 2, 3$ | $64$ |

对于所有数据，满足：

- $1 \le T \le 10$；
- $3 \le n \le 10^{18}$；
- $1 \le m \le 10^{18}$。

## 时空限制



时间限制
5.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛, O2优化
Difficulty: NOI/NOI+/CTSC
# 「Diligent-OI R1 A」DlgtPattern

## 题目描述

现有一个水杯放在一个不透明的盒子中。水杯的底面可以看成一个圆形。盒子可以看成一个长方体，其厚度忽略不计。

现将盒子的底面放在一个平面直角坐标系中，它的四个顶点分别位于 $(0,0)$，$(x,0)$，$(0,y)$ 和 $(x,y)$。

你只知道水杯底面的圆心位于 $(p,q)$。那水杯底面的半径最大可以是多少呢？

## 输入格式

只输入一行，四个整数 $x,y,p,q$。

## 输出格式

只输出一个数，水杯底面半径的最大值。

## 样例 #1

### 样例输入 #1

```
10 5 3 4
```

### 样例输出 #1

```
1
```

## 提示

#### 样例 #1 解释

水杯半径最大的情况如下图所示。

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

#### 数据范围

对于 $100\%$ 数据，$0<p<x\le100$，$0<q<y\le100$。

| 测试点编号 | 特殊性质 |
| :----------: | :----------: |
| $1\sim 4$ | AB |
| $5\sim 6$ | B |
| $7\sim 10$ | 无 |

特殊性质 A：$x=y$。

特殊性质 B：$x=2p,y=2q$。即水杯底面的圆心在盒子底面的几何中心。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛
Difficulty: 入门
# 「Diligent-OI R1 B」DlgtArray

## 题目描述

现给定一个长为 $n$ 的序列 $a_1\sim a_n$，其中 $a_i\in\{0,1\}$。

$q$ 次询问，每次给定 $l,r,k$，要你更改一些位置上的数值（只能改为 $0$ 或 $1$）使得 $\sum\limits_{i=l}^ra_i=k+\prod\limits_{i=l}^ra_i$。也就是说要让 $a_l\sim a_r$ 的和要恰好等于 $a_l\sim a_r$ 的乘积再加上 $k$。你需要求出最少的修改次数。如果无解，输出 $-1$。

**请注意每次的更改不会对后续询问产生影响。**

## 输入格式

第一行输入 $n,q$。

接下来一行 $n$ 个整数 $a_1\sim a_n$。

接下来 $q$ 行，每行三个整数 $l,r,k$。

## 输出格式

输出 $q$ 行，每行一个整数表示最少的修改次数。如果无解请输出 `-1`。

## 样例 #1

### 样例输入 #1

```
5 4
0 0 1 0 1
1 3 2
2 4 0
3 5 2
1 1 1
```

### 样例输出 #1

```
1
1
0 
-1
```

## 样例 #2

### 样例输入 #2

```
8 3
1 1 1 1 1 1 1 1
2 6 2
5 8 2
1 8 7
```

### 样例输出 #2

```
3
2
0
```

## 提示

#### 样例 #1 解释

$a=\{0,0,1,0,1\}$。

第一个询问只需将 $a_1$ 或 $a_2$ 改为 $1$。此时和为 $2$，积为 $0$。

第二个询问只需将 $a_3$ 改为 $0$。此时和为 $0$，积为 $0$。

第三个询问不需进行更改，和为 $2$，积为 $0$。

第四个询问，因为只有一个数，所以和与积相等，所以不可能做到。

#### 数据范围

对于 $100\%$ 数据，$1\le n,q\le10^6$，$0\le k\le10^6$，$1\le l\le r\le n$，$a_i\in\{0,1\}$。

| Subtask 编号 | $n,q\le$ | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: | :----------: |
| $0$ | $10$ | 无 | $10$ |
| $1$ | $10^3$ | A | $7$ |
| $2$ | $10^3$ | BC | $7$ |
| $3$ | $10^3$ | B | $13$ |
| $4$ | $10^3$ | C | $13$ |
| $5$ | $10^3$ | 无 | $20$ |
| $6$ | $10^5$ | B | $9$ |
| $7$ | $10^5$ | C | $9$ |
| $8$ | $10^6$ | 无 | $12$ |

特殊性质 A：$k=n$。

特殊性质 B：$\forall 1\le i\le n,a_i=0$。

特殊性质 C：$k=0$。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛
Difficulty: 普及−