yl-9/probench huggingface dataset:
# I Love Balls

## Problem Description

Alice and Bob are playing a game. There are $ n $ balls, out of which $ k $ are special. Each ball has a value associated with it.

The players play turn by turn. In each turn, the player randomly picks a ball and adds the value of the ball to their score, which is $ 0 $ at the beginning of the game. The selected ball is removed from the game. If the ball was special, the same player takes the next turn if at least one ball is remaining. If the ball picked was not special, the next player plays their turn.

They play this game until no balls are remaining in the game. Alice plays first.

Find the expected score that both the players have at the end of the game modulo $ 10^9+7 $ .

Formally, let $ M = 10^9+7 $ . It can be shown that the answer can be expressed as an irreducible fraction $ \frac{p}{q} $ , where $ p $ and $ q $ are integers and $ q \not \equiv 0 \pmod{M} $ . Output the integer equal to $ p \cdot q^{-1} \bmod M $ . In other words, output such an integer $ x $ that $ 0 \le x < M $ and $ x \cdot q \equiv p \pmod{M} $ .

## Input Format

There are multiple test cases. The first line of the input contains an integer $ t $ , the number of test cases ( $ 1 \le t \le 2 \cdot 10^5 $ ).

Each test case description is on a new line. The first line of the test case contains two integers $ n $ and $ k $ in the respective order separated by a space ( $ 1 \le k \le n \le 4 \cdot 10^5 $ ).

The second line of the test case contains $ n $ integers: $ v_1, v_2, \ldots, v_n $ , the value for each ball separated by spaces. The first $ k $ balls are special ( $ 1 \le v_i \le 10^7 $ ).

The sum of $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

## Output Format

Output two integers per test case in a new line, the expected score of Alice and the expected score of Bob modulo $ 10^9+7 $ .

## Sample #1

### Sample Input #1

```
1
5 2
10 20 5 15 25
```

### Sample Output #1

```
45 30
```

## Sample #2

### Sample Input #2

```
5
1 1
732507
2 2
5817860 5398510
5 1
2122894 4951549 2750585 7821535 3214167
8 4
1405323 5069867 6883092 6972029 328406 2478975 7628890 9973340
4 2
9662050 3566134 3996473 9872255
```

### Sample Output #2

```
732507 0
11216370 0
810642660 210218077
722402997 318336932
349086489 678010430
```

## Sample #3

### Sample Input #3

```
5
3 3
1095611 8219204 7773462
2 1
8176490 2774103
3 1
9178636 5138057 3367761
12 9
7597698 6843019 2298534 1522386 4969588 1340345 3967362 9152890 6689668 9986080 4745473 7407325
10 5
6986368 2397882 5804127 6980694 3740836 3215836 5195724 3179261 4136769 4544231
```

### Sample Output #3

```
17088277 0
6862348 4088245
677038671 340645790
36949997 29570371
725118051 321063684
```

## Hint

In the first test case, Alice's expected score is $ 45 $ , and Bob's is $ 30 $ at the end of the game.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: combinatorics, math, probabilities
Difficulty: 2300
# Swap Dilemma

## Problem Description

Given two arrays of distinct positive integers $ a $ and $ b $ of length $ n $ , we would like to make both the arrays the same. Two arrays $ x $ and $ y $ of length $ k $ are said to be the same when for all $ 1 \le i \le k $ , $ x_i = y_i $ .

Now in one move, you can choose some index $ l $ and $ r $ in $ a $ ( $ l \le r $ ) and swap $ a_l $ and $ a_r $ , then choose some $ p $ and $ q $ ( $ p \le q $ ) in $ b $ such that $ r-l=q-p $ and swap $ b_p $ and $ b_q $ .

Is it possible to make both arrays the same?

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 2 \cdot 10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the arrays $ a $ and $ b $ .

The second line of each test case contains $ n $ distinct integers $ a_1,a_2,a_3,\ldots,a_n $ ( $ 1 \le a_i \le 2 \cdot 10^5 $ ) — the integers in the array $ a $ .

The third line of each test case contains $ n $ distinct integers $ b_1,b_2,b_3,\ldots,b_n $ ( $ 1 \le b_i \le 2 \cdot 10^5 $ ) — the integers in the array $ b $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

## Output Format

For each testcase, print "YES" if the arrays $ a $ and $ b $ can be made the same. Otherwise, print "NO". can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
YES
NO
YES
NO
NO
NO
```

## Hint

In the first testcase, you don't need to perform any operations since the arrays are same.

In the second testcase, it can be proven there exists no way to make the arrays same.

In the third testcase, one of the ways to make the arrays same is to first choose $ l=1 $ , $ r=3 $ , $ p=1 $ , $ q=3 $ then choose $ l=1 $ , $ r=2 $ , $ p=3 $ , $ q=4 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, data structures, divide and conquer, greedy, math, sortings
Difficulty: 1700
# Array Divisibility

## Problem Description

An array of integers $ a_1,a_2,\cdots,a_n $ is beautiful subject to an integer $ k $ if it satisfies the following:

- The sum of $ a_{j} $ over all $ j $ such that $ j $ is a multiple of $ k $ and $ 1 \le j \le n  $ , itself, is a multiple of $ k $ .
- More formally, if $ \sum_{k | j} a_{j} $ is divisible by $ k $ for all $ 1 \le j \le n $ then the array $ a $ is beautiful subject to $ k $ . Here, the notation $ {k|j} $ means $ k $ divides $ j $ , that is, $ j $ is a multiple of $ k $ .

 Given $ n $ , find an array of positive nonzero integers, with each element less than or equal to $ 10^5 $ that is beautiful subject to all $ 1 \le k \le n $ .It can be shown that an answer always exists.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows.

The first and only line of each test case contains a single integer $ n $ ( $ 1 \le n \le 100 $ ) — the size of the array.

## Output Format

For each test case, print the required array as described in the problem statement.

## Sample #1

### Sample Input #1

```
3
3
6
7
```

### Sample Output #1

```
4 22 18
10 6 15 32 125 54
23 18 27 36 5 66 7
```

## Hint

In the second test case, when $ n = 6 $ , for all integers $ k $ such that $ 1 \le k \le 6 $ , let $ S $ be the set of all indices of the array that are divisible by $ k $ .

- When $ k = 1 $ , $ S = \{1, 2, 3,4,5,6\} $ meaning $ a_1+a_2+a_3+a_4+a_5+a_6=242 $ must be divisible by $ 1 $ .
- When $ k = 2 $ , $ S = \{2,4,6\} $ meaning $ a_2+a_4+a_6=92 $ must be divisible by $ 2 $ .
- When $ k = 3 $ , $ S = \{3,6\} $ meaning $ a_3+a_6=69 $ must divisible by $ 3 $ .
- When $ k = 4 $ , $ S = \{4\} $ meaning $ a_4=32 $ must divisible by $ 4 $ .
- When $ k = 5 $ , $ S = \{5\} $ meaning $ a_5=125 $ must divisible by $ 5 $ .
- When $ k = 6 $ , $ S = \{6\} $ meaning $ a_6=54 $ must divisible by $ 6 $ .

 The array $ a = [10, 6, 15, 32, 125, 54] $ satisfies all of the above conditions. Hence, $ a $ is a valid array.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, math
Difficulty: 800
# 「Cfz Round 5」Non-breath Oblige

## 题目背景

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

---

それぞれの好きを守るため  
为了保护各自的喜爱之物

君と防空壕で呼吸する  
与你在防空壕中一同呼吸

## 题目描述

给定三个整数 $n,s,t$，其中 $0 \le s,t \lt 2^n$。

你可以进行若干次操作。每次操作，你可以选择一个非负整数 $x$ 并把 $s$ 的值修改为 $x$，但有如下要求：

- 必须满足 $x<2^n$；
- 必须满足 $s\lor x=2^n-1$，其中 $\lor$ 为按位或运算；
- 你需要花费 $s\oplus x$ 的代价，其中 $\oplus$ 为按位异或运算。

你需要求出使 $s=t$ 所需代价之和的最小值。可以证明一定可以使 $s$ 与 $t$ 相等。

## 输入格式

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

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

接下来依次输入每组测试数据。对于每组测试数据，输入共一行，包含三个整数 $n,s,t$。

## 输出格式

对于每组测试数据，输出一行一个整数，表示使 $s=t$ 所需代价之和的最小值。

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

```
3
0
57
```

## 提示

#### 「样例解释 #1」

对于第 $1$ 组测试数据，由于 $1 \cup 2 = 3$，所以可以直接将 $s$ 的值从 $1$ 修改为 $2$，此时的代价为 $1 \oplus 2$，即 $3$。可以证明使 $s=t$ 所需代价之和的最小值为 $3$。

对于第 $2$ 组测试数据，不需要进行操作即可满足 $s=t$。

#### 「数据范围」

对于所有测试数据，保证：

- $1 \le T \le 100$；
- $1 \le n \le 30$；
- $0 \le s,t \lt 2^n$。

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

- Subtask 0（12 points）：$s=t$。
- Subtask 1（15 points）：$n=1$。
- Subtask 2（20 points）：$s+t=2^n-1$。
- Subtask 3（10 points）：$t=2^n-1$。
- Subtask 4（18 points）：$t=0$。
- Subtask 5（25 points）：无特殊限制。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 数学, 贪心, 位运算, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及−
# 「Cfz Round 5」Mata rainen

## 题目背景

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

---

**如您希望对本题难度评分、数据强度等事项提出宝贵意见，请移步 [关于本题难度评分、数据强度等事项的说明](https://www.luogu.com.cn/discuss/1030705)，而不要新开帖子！**（2024.12.30 rui_er 添加，本条保留至 2025.1.31）

---

题目名称意为：明年见。

小 R 是一个正在上高三的女孩子。她在升入高三的暑假复习了[《种树郭橐（tuó）驼传》](https://baike.baidu.com/item/%E7%A7%8D%E6%A0%91%E9%83%AD%E6%A9%90%E9%A9%BC%E4%BC%A0)，便编出了这道与树有关的题。

在把这道题目丢给出题组后，她决定把全部时间和精力投入到高考的旅程中，期待在 2025 年的暑假在算法竞赛中与大家再会。

## 题目描述

请判断是否存在一棵树满足如下条件。若存在，请尝试给出构造。

树中包含 $n$ 个结点，编号为 $1\sim n$。另外，给定 $m$ 个点对 $(s_i,t_i)$，要求树上这 $m$ 条从点 $s_i$ 到点 $t_i$ 的路径覆盖每条边**恰好**一次 $^\dagger$。

**若你正确判断了是否有解，但不会构造出这棵树，也可以获得一定的分数，详见【评分方式】。**

$\dagger$ 称从点 $s$ 到点 $t$ 的路径覆盖一条边 $(u,v)$，当且仅当边 $(u,v)$ 在点 $s$ 到点 $t$ 的最短路径上。

## 输入格式

第一行包含两个整数 $n,m$，表示这棵树的点数和给出的点对数。

接下来 $m$ 行，每行两个整数 $s_i,t_i$，表示一个点对。

## 输出格式

第一行输出一个字符串 `Yes` 或 `No`（大小写不敏感），表示是否有解。

若有解，继续输出 $n-1$ 行，每行包含两个整数 $u_i,v_i$，描述一条边。**你需要保证 $\bm{1\le u_i,v_i\le n}$ 且所有边构成一棵树。**

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

```
Yes
1 5
2 5
3 5
4 6
5 6
```

## 样例 #2

### 样例输入 #2

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

### 样例输出 #2

```
No
```

## 提示

#### 「样例解释 #1」

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

左上图为样例输出中给出的树。边 $(1,5),(5,2)$ 被路径 $(1,2)$ 覆盖，边 $(3,5),(5,6),(6,4)$ 被路径 $(3,4)$ 覆盖，符合题目要求。

右上图中边 $(5,6)$ 被路径 $(1,2)$ 和 $(3,4)$ 覆盖，不符合题目要求。

左下图中边 $(5,6)$ 未被任何路径覆盖，不符合题目要求。

右下图不是一棵树，不符合题目要求。

#### 「样例解释 #2」

可以证明不存在符合要求的树。

#### 「评分方式」

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

对于每个测试点：

- 若第一行格式错误或与答案不匹配（大小写不敏感），得 $0\%$ 的分数。
- 若第一行答案正确且为 `No`，得 $100\%$ 的分数。
- 若第一行答案正确且为 `Yes`，**但后 $n-1$ 行格式错误**，得 $0\%$ 的分数。  
因此，**请务必保证输出为一棵树**。
- 若第一行答案正确且为 `Yes`，后 $n-1$ 行格式正确但树不符合要求，得 $20\%$ 的分数。
- 若第一行答案正确且为 `Yes`，后 $n-1$ 行格式正确且树符合要求，得 $100\%$ 的分数。

也就是说，对于第一个样例，在正确输出 `Yes` 的基础上，输出左上图可以得到满分，输出右上图、左下图可以得到 $20\%$ 的分数，输出右下图不能得到任何分数；对于第二个样例，正确输出 `No` 即可得到满分。

#### 「数据范围」

对于所有测试数据，保证：

- $2\le n\le 3\times 10^5$；
- $1\le m\le 3\times 10^5$；
- $1\le s_i,t_i\le n$ 且 $s_i\ne t_i$。

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

- Subtask 0（10 points）：$n\le 3$，$m\le 3$。
- Subtask 1（10 points）：$n\le 10$，$m\le 10$。
- Subtask 2（20 points）：$m=1$。
- Subtask 3（10 points）：$n\le 300$，$m\le 300$。
- Subtask 4（10 points）：$n\le 2\times 10^3$，$m\le 2\times 10^3$。
- Subtask 5（20 points）：$m\le 2\times 10^3$。
- Subtask 6（20 points）：无特殊限制。

#### 「Hack 数据」

本题于赛后添加了部分 Hack 数据。这些数据均满足 Subtask 6 对数据规模的限制，他们被添加到 Subtask 7 中。这些数据不计分，但只有通过所有数据，才算做 AC 本题。

- Subtask 7（0 points）：赛后添加的 Hack 数据。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 连通块, 树论, 构造, 洛谷原创, 洛谷月赛, Special Judge, O2优化
Difficulty: 普及+/提高
# 「Cfz Round 5」Gnirts 10

## 题目背景

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

---

In Memory of $\text{F}\rule{66.8px}{6.8px}$.

## 题目描述

题面还是简单一点好。

- 给定 $n, m$，以及一个长为 $n + m$ 的 $\tt{01}$ 串 $S$。
- 对于 $\tt 01$ 串 $T$，定义 $f(T)$ 为 $S$ 的最长的前缀的长度，使得该前缀是 $T$ 的子序列 $^\dagger$。
- 对于每个 **恰包含 $\bm n$ 个 $\tt 1$ 和 $\bm m$ 个 $\tt 0$ 的** $\tt{01}$ 串 $T$，求 $f(T)$ 的和。答案对 $2933256077^\ddagger$ 取模。

$\dagger$：请注意，子序列可以不连续。换句话说，$a$ 是 $b$ 的子序列，当且仅当在 $b$ 中删去 $\geq 0$ 个字符后，可以得到 $a$。注意，空串总是任何串的子序列。

$\ddagger$：模数为质数。

## 输入格式

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

第二行包含一个长度为 $n + m$ 的 $\tt 01$ 串 $S$。

## 输出格式

输出一行一个整数，表示答案对 $2933256077$ 取模后的结果。

## 样例 #1

### 样例输入 #1

```
2 1
000
```

### 样例输出 #1

```
3
```

## 样例 #2

### 样例输入 #2

```
5 5
0010111011
```

### 样例输出 #2

```
1391
```

## 提示

#### 「样例解释 #1」

所有可能的序列有且仅有公共序列 $\texttt{0}$。因为恰有 $3$ 种不同的 $T$（$\tt 110, 101, 011$），所以答案为 $1\times 3 = 3$。

#### 「数据范围」

对于所有测试数据，保证 $1 \leq n, m \leq 3\times 10^6$。

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

- Subtask 0（13 points）：$\max(n, m) \leq 5$。
- Subtask 1（13 points）：$\max(n, m) \leq 100$。
- Subtask 2（34 points）：$\max(n, m) \leq 3 \times 10^3$。
- Subtask 3（40 points）：无特殊限制。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 组合数学, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 提高+/省选−
# 「Cfz Round 5」Zhòng shù

## 题目背景

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

---

> 我想要种一棵香蕉树 上面挂满我的所有祝福

## 题目描述

小 C 喜欢种树。

它种了一棵香蕉树，但是这棵树似乎需要人工维护才能生长。

因此，它经常会在树上的某一个位置挂上一些「祝福」。所谓「祝福」，其实就是一条链。

而有的时候树的一部分长得太好了，会导致整棵树长歪，所以它又不得不砍掉一部分。

小 C 还喜欢众数，所以它会经常问你所有树上结点的深度中同一个深度最多的出现次数。

具体来说，有一棵有根树，最初只有根结点 $1$，另外有一个变量 $n=1$。

有如下三种操作：

1. `x l k`：增加编号为 $n+1\sim n+lk$ 的结点以及边
$(x,n+1),(n+1,n+2),\dots,(n+l-1,n+l)$；$(x,n+l+1),(n+l+1,n+l+2),\dots,(n+2l-1,n+2l)$；$\dots$；$(x+n+(k-1)l+1),(n+(k-1)l+1,n+(k-1)l+2),\dots,(n+kl-1,n+kl)$。即在 $x$ 号结点下面挂了 $k$ 条长度为 $l$ 的链。这个操作执行之后 $n\gets n+kl$。
2. `x`：删除 $x$ 号结点及其子树。
3. （无参数）查询所有结点的深度中，出现最多的那个深度的出现次数。

## 输入格式

第一行包含一个整数 $m$，表示操作次数。

接下来 $m$ 行，每行包含若干个整数，第一个整数 $op$ 表示当前操作种类，接下来的输入与上面的格式依次对应。

## 输出格式

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

## 样例 #1

### 样例输入 #1

```
23
3
1 1 2 3
3
1 6 2 2
3
1 7 1 4
3
2 12
3
2 13
3
1 3 1 2
3
2 7
3
2 3
3
1 5 2 3
3
2 6
3
2 5
3
```

### 样例输出 #1

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

## 样例 #2

### 样例输入 #2

```
16
1 1 4 3
3
1 2 3 3
3
1 10 1000000000 2
3
1 1000000021 1 10
3
2 1000000027
3
2 23
3
1 12 1 1
3
1 2000000033 100000 1000000000
3
```

### 样例输出 #2

```
3
6
8
12
11
7
8
1000000001
```

## 样例 #3

### 样例输入 #3

```
18
1 1 85 483
1 32607 44 379
2 45784
1 46178 133 40
3
1 13506 152 357
2 62124
3
1 70877 209 33
3
1 37299 429 158
3
1 31487 258 363
2 159051
3
2 227162
2 279608
3
```

### 样例输出 #3

```
902
1257
1257
1415
1778
1778
```

## 样例 #4

### 样例输入 #4

```
19
1 1 189019619 113958
2 800361853
1 422490453 494478 254349561
3
2 1152812283
2 1650380207
3
1 4033287043 23425848 3533684
2 2666277906
1 709388173 159264263 191915
3
2 3453785850
2 8487830948768
2 39677822722745
2 167837684014594
1 1534084935 1205975 21949299
1 151207136 41249553 693236
1 1121564684 68403 1385595730
3
```

### 样例输出 #4

```
254463518
254463517
254463516
1386594833
```

## 提示

#### 「样例解释 #1」

下面的图中，点的颜色代表被加入的时间。

![](https://s21.ax1x.com/2024/12/09/pAHk3Hf.png)

上图为经过三次 $1$ 操作（`1 1 2 3`，`1 6 2 2` 和 `1 7 1 4`）后的树。

![](https://s21.ax1x.com/2024/12/09/pAHklut.png)

上图为在刚才的基础上经过两次 `2` 操作（`2 12` 和 `2 13`）的树。

![](https://s21.ax1x.com/2024/12/09/pAHk1DP.png)

上图为刚才的基础上再经过一次 $1$ 操作（`1 3 1 2`）的树。

![](https://s21.ax1x.com/2024/12/09/pAHkGE8.png)

上图为刚才的基础上再经过两次 $2$ 操作（`2 7` 和 `2 3`）的树。

![](https://s21.ax1x.com/2024/12/09/pAHkMjI.png)

上图为刚才的基础上再经过一次 $1$ 操作（`1 5 2 3`）的树。

![](https://s21.ax1x.com/2024/12/09/pAHkJUS.png)

上图为经过所有操作后的树。

#### 「数据范围」

对于所有测试数据，保证：

- $1\le m\le 10^5$；
- $1$ 操作中的 $x$ 满足 $1\le x\le n$ 且 $x$ 号结点在树上依然存在，保证 $1 \le l,k \le 10^{18}$；
- $2$ 操作中的 $x$ 满足 $1<x\le n$ 且 $x$ 号结点在树上依然存在；
- 任意时刻的 $n$ 满足 $n\le 10^{18}$。

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

设操作过程中 $n$ 的最大值为 $k$。

- Subtask 0（10 points）：$k \le 5000$。
- Subtask 1（20 points）：$k \le 5 \times 10^5$。
- Subtask 2（20 points）：不存在 $2$ 操作。
- Subtask 3（20 points）：$1$ 操作中 $l$ 的值为 $1$。
- Subtask 4（30 points）：无特殊限制。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛
Difficulty: 省选/NOI−
# 「ALFR Round 3」A 调皮的学生

## 题目背景

[English Statement](https://www.luogu.com.cn/problem/U517303).

在小山所在的学校中，有着一群非常调皮的学生。比如，在给老师的教学水平评分时，他们常常会给出不正经的评分。

## 题目描述

又到了一学期一度的评分大赛，每位同学都可以为本班某门科目的老师评分（一共有语、数、英三门科目）。每位同学应当只为一位老师评分。但有些学生常常会为多位老师评分，或者不为任何老师评分，我们称这样的学生为调皮的学生。现在给出小山所在班级的三门科目的老师的评分情况，请你求出该班级的调皮的学生的数量。

## 输入格式

第一行一个整数 $n$，表示全班共有 $n$ 位学生，学生的学号为 $1\sim n$。

第二行一个整数 $a$，表示有 $a$ 位学生为语文老师评了分。

第三行有 $a$ 个整数，第 $i$ 个整数 $x_i$ 表示学号为 $x_i$ 的学生为语文老师评了分。

第四行一个整数 $b$，代表有 $b$ 位学生为数学老师评了分。

第五行有 $b$ 个整数，第 $i$ 个整数 $y_i$ 表示学号为 $y_i$ 的学生为数学老师评了分。

第六行一个整数 $c$，代表有 $c$ 位学生为英语老师评了分。

第七行有 $c$ 个整数，第 $i$ 个整数 $z_i$ 表示学号为 $z_i$ 的学生为英语老师评了分。

## 输出格式

一行一个整数代表小山所在班级的调皮的学生的数量。

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

```
4
```

## 提示

### 样例解释

学号为 $1,2,3,4,5$ 的学生分别为 $2,2,3,0,1$ 位老师评了分，学号为 $1,2,3,4$ 的学生都是调皮的学生，所以答案为 $4$。

### 数据范围

| 子任务 | 分值 | 限制 |
| :----------: | :----------: | :----------: |
| $0$ | $10$ | $n=1$ |
| $1$ | $20$ | $x,y,z$ 三个数组中的**所有**元素互不重复|
| $2$ | $10$ | $a=b=c=1$|
| $3$ | $10$ | $a=n,b=c=1$|
| $4$ | $20$ | $x,y,z$ 数组分别按照升序顺序给出|
| $5$ | $30$ | - |

对于 $100\%$ 的数据，$1\le n\le 100$，$0\le a,b,c\le n$，$1\le x_i,y_i,z_i\le n$，$x,y,z$ 数组内各自没有重复元素。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛, O2优化
Difficulty: 入门
# 「ALFR Round 3」B Swap & Delete

## 题目背景

[English Statement](https://www.luogu.com.cn/problem/U517304)

## 题目描述

给定一个长为 $n$ 的序列 $a_1, a_2,a_3, \dots ,a_n$，你需要执行 $k$ 次操作使这个序列为空。

每次操作可以执行下列内容之一：

1. 选择两个数 $i, j$，交换 $a_i, a_j$（需要满足 $1 \le i < j \le n$）。
2. 选择两个数 $i, j$，删除 $a_i,a_{i+1}, \dots ,a_j$（需要满足 $1 \le i \le j \le n$，且 $a_i = a_j$）。

请输出最小的操作数 $k$。

## 输入格式

第一行输入一个正整数 $T$（$1 \le T \le 5$），表示有 $T$ 个测试数据。

对于每个测试数据：

第一行输入一个正整数 $n$（$1 \le n \le 10^5$），表示序列长度为 $n$。

第二行输入 $n$ 个正整数 $a_1,a_2 \dots a_n$（$0 \le a_i \le 10^9$）。

## 输出格式

对于每个测试数据输出一个正整数 $k$，表示最少的操作次数。

## 样例 #1

### 样例输入 #1

```
2
5
1 2 3 2 3
3
1000000000 1000000000 99999999
```

### 样例输出 #1

```
2
2
```

## 提示

### 数据范围

| 子任务 | 分值 | 限制 |
| :----------: | :----------: | :----------: |
| $1$ | $10$ | $n\le 3$ |
| $2$ | $20$ | $n\le 10$ |
| $3$ | $20$ | $a_i\le 2$ |
| $4$ | $10$ | 保证所有 $a_i$ 相等 |
| $5$ | $40$ | - |

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

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及−
# 「ALFR Round 3」C 割

## 题目背景

[English Statement](https://www.luogu.com.cn/problem/U517305).

**upd:** 添加的 hack 在 Sub 7。

## 题目描述

设 $f(S)$ 表示字符串 $S$ 字典序最大的子序列，给定 $k$，你需要将原字符串 $S$ 分割成 $k$ 段，设第 $i$ 段子串为 $a_i$，则该分割方案的权值为 $\max f(a_i)$，其中 $1\le i\le k$。由于分割方案有很多种，你需要求出所有分割方案中**字典序最小的权值**。

注：这里的权值实际上指的是字符串。

关于子序列的定义：某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。

关于字典序的定义：在字典序中，首先比较两个字符串的第一个字符，如果不同，则第一个字符较小的字符串更小；如果相同，则继续比较下一个字符，依此类推，直到比较完所有字符。如果一个字符串是另一个字符串的前缀，则较短的字符串更小。

## 输入格式

输入共两行。

第一行两个整数 $n,k$，$n$ 表示字符串 $S$ 的长度，$k$ 表示你需要将字符串分割为 $k$ 段。

第二行为一个字符串，即 $S$。

## 输出格式

输出一个字符串表示所有分割方案中字典序最小的权值。

## 样例 #1

### 样例输入 #1

```
7 2
skyaqua
```

### 样例输出 #1

```
y
```

## 提示

### 样例解释
可以将字符串 $S$ 分割成 `sky`、`aqua` 这 $2$ 段，这 $2$ 段的 $f$ 分别为 `y`、`ua`，其中字典序最大的 $f$ 为 `y`，所以该分割方案的权值为 `y`。可以证明 `y` 是所有分割方案中字典序最小的权值。

### 数据范围

| 子任务 | 分值 | 限制 |
| :----------: | :----------: | :----------: |
| $1$ | $10$ | $n\le 10$ |
| $2$ | $20$ | $n\le 10^2$ |
| $3$ | $20$ | $n\le 3\times 10^2$| 
| $4$ | $10$ | 保证字符串 $S$ 中所有字符都相等 |
| $5$ | $10$ | $k=1$ |
| $6$ | $30$ | - |

对于 $100\%$ 的数据，$1\le k\le n\le 2\times10^5$，且字符串 $S$ 中的字符均为小写英文字母。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 字符串, 贪心, 鸽笼原理, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及/提高−
# 「ALFR Round 3」D 核裂变

## 题目背景

[English Statement](https://www.luogu.com.cn/problem/U517306).

可爱的松鼠跑去学 PhO 啦。

## 题目描述

有 $n$ 个放射性原子要进行 $k$ 秒的裂变反应。如果在第 $t$ 秒开始时原子 $i$ 被 $b\ (b>0)$ 个中子轰击了，那它就会在第 $t$ 秒内释放 $a_i + b$ 单位能量，并向编号为 $x_{i,1},x_{i,2},\dots,x_{i,a_i}$ 的所有原子各释放 $1$ 个中子。这样，在第 $t+1$ 秒开始时分别击中的 $x_{i,1},x_{i,2},\dots,x_{i,a_i}$ 的中子数量都将**增加** $1$（**如果 $t=k$，即这是最后一秒，那么被轰击的原子不会释放中子**）。如果在这一秒开始时某个原子没被中子击中，则其不会释放能量与中子。

每一秒开始时，编号为 $v_1,v_2,\dots,v_m$ 的原子都会被 $1$ 个中子轰击。那么，从第 $1$ 秒开始，到第 $k$ 秒的终止时刻为止，每个原子会释放多少能量？

**答案对 $998244353$ 取模！**

## 输入格式

第一行三个整数 $n,k,m$，表示原子的个数，反应的时间与每一秒开始时被轰击的原子数。

接下来一行 $m$ 个整数 $v_1,v_2,\dots,v_m$。

接下来 $n$ 行输入每个原子的信息，格式如下：

第 $i$ 行 $a_i + 1$ 个整数，第一个数为 $a_i$，接下来 $a_i$ 个数 $x_{i,1},x_{i,2},\dots,x_{i,a_i}$。

## 输出格式

输出 $1$ 行，共 $n$ 个数，第 $i$ 个数是原子 $i$ 从第 $1$ 秒开始，到第 $k$ 秒的终止时刻为止释放的总能量，答案对 $998244353$ 取模。

## 样例 #1

### 样例输入 #1

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

### 样例输出 #1

```
6 4 2
```

## 样例 #2

### 样例输入 #2

```
3 1000000000000000000 1
1
1 2
1 3
1 1
```

### 样例输出 #2

```
151723985 433897441 433897439
```

## 提示

### 样例 #1 解释：

- 第一秒，原子 $1$ 被 $1$ 个中子轰击，释放 $1$ 中子到原子 $2$，释放 $2$ 能量。
- 第二秒，原子 $1$ 被 $1$ 个中子轰击，释放 $1$ 中子到原子 $2$，释放 $2$ 能量。同时原子 $2$ 被 $1$ 个中子轰击，释放 $1$ 个中子到原子 $3$，释放 $2$ 能量。
- 第三秒，原子 $1$ 被 $1$ 个中子轰击，释放 $2$ 能量。同时原子 $2$ 被 $1$ 个中子轰击，释放 $2$ 能量。同时原子 $3$ 被 $1$ 个中子轰击，释放 $2$ 能量。

所以原子 $1$ 共释放了 $6$ 能量，原子 $2$ 释放了 $4$ 能量，原子 $3$ 释放了 $2$ 能量。

### 数据范围

| 子任务 | 分值 | 限制 |
| :----------: | :----------: | :----------: |
| $0$ | $5$ | $m=n,v_i=i,a_i=1,x_{i,1}=1$ |
| $1$ | $10$ | $m=1,v_1=1,a_i=1,x_{i,1}=(i\bmod n)+1$ |
| $2$ | $20$ | $n,\sum a_i\le10^3$，$1\le k\le10^6$ |
| $3$ | $30$ | $1\le k\le10^6$ |
| $4$ | $35$ | - |

对于所有数据，$1\le m\le n\le 5\times10^5,1\le \sum a_i\le5\times10^5$，$1\le k\le10^{18}$，$0 \leq a_i \leq 5 \times 10^5$，且 $v_1,v_2,\dots,v_m$ 互不相同且是 $[1,n]$ 内的整数，$x_{i,1},x_{i,2},\dots,x_{i,a_i}$ 互不相同且是 $[1,n]$ 内的整数。

**本题输入量较大，请使用较快的 I/O 方式。**

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 广度优先搜索 BFS, 洛谷原创, 洛谷月赛, O2优化
Difficulty: 普及+/提高
# 喵喵喵幼儿园

## 题目描述

喵喵喵群里面，吃喵喵是坏文明。

现在群友有 $q$ 个问题，每个问题形如 `A or B?`，其中 $A,B$ 为仅含小写字母的非空字符串。

对于每个问题，你可以回答 $A$ 或 $B$ 中的任意一个不是 `eat` 的字符串。特别地，如果 $A$ 和 $B$ 都是 `eat`，你需要回答 `or`。

## 输入格式

输入的第一行有一个正整数 $q$，表示问题的数量。

之后有 $q$ 行，每行有一个问题。

## 输出格式

对于每个问题，输出一行一个字符串，表示你对于这个问题的答案。

## 样例 #1

### 样例输入 #1

```
4
yummy or yucky?
eat or stick?
rua or eat?
eat or eat?
```

### 样例输出 #1

```
yummy
stick
rua
or
```

## 样例 #2

### 样例输入 #2

```
7
saint or sinner?
tobe or nottobe?
ad or able?
eating or eaten?
or or or?
and or and?
oneplusoneistwo or oneplusoneisthree?
```

### 样例输出 #2

```
sinner
tobe
able
eaten
or
and
oneplusoneistwo
```

## 提示

【样例 1 解释】

- 对于第一个问题，你可以从 `yummy` 和 `yucky` 两个单词中的任意一个，所以既可以回答 `yummy` 也可以回答 `yucky`。**注意：在这个问题输出 `or` 将导致答案错误。**
- 对于第二个问题，因为第一个单词是 `eat`，要避开，因此**必须**输出 `stick`。
- 对于第三个问题，因为第二个单词是 `eat`，要避开，因此**必须**输出 `rua`。
- 对于第四个问题，两个单词都是 `eat`，所以要输出 `or`。

【样例 2 解释】

本样例共有 $32$ 种本质不同的输出（除了第 $5,6$ 个问题的两个字符串一样外，其他问题都有两种可能答案），这里仅展示其中一种可能的输出。

【数据范围】

对于全部数据，保证 $1\le q\le 100$，每个问题中的字符串 $A,B$ 均不超过 $100$ 个字符，且仅含有小写字符。

本题共有 $6$ 个测试点，不同测试点的分值和特殊性质见下表：

|测试点编号|特殊性质|分值|
|:-:|:-:|:-:|
|1|$A,B$ 都不是 `eat`|$19$|
|2|$A$ 一定是 `eat`，$B$ 一定不是 `eat`|$22$|
|3|$B$ 一定是 `eat`|$11$|
|4|$A$ 一定是 `eat`|$12$|
|5|$A,B$ 一定有一个不是 `eat`|$13$|
|6|无特殊性质|$23$|

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛, Special Judge
Difficulty: 入门
# 排队

## 题目描述

第一届喵喵喵编程大赛即将开始，本次比赛有 $n$ 只喵喵参赛，编号依次为 $1,2,\ldots, n$，已经分成了若干组，每一组喵喵的编号都是连续的一段。

根据报名情况，你已经知道第 $i$ 只喵喵会第 $p_i$ 个到达现场，保证 $p_i$ 构成 $1\sim n$ 的排列。

一组喵喵的到达时间被定义为这一组喵喵中**最早到达**的喵喵的到达时间。

喵喵的排队规则如下：

- 先把所有的喵喵组按每组喵喵的到达时间从小到大排序。
- 然后对于同一组喵喵，按照每只喵喵的到达时间从小到大排序。

按照这个排队规则，可以得到一个新的排列 $q_1,\ldots,q_n$，其中 $q_i$ 表示从前往后第 $i$ 只喵喵的**到达时间**。

你已经知道了所有 $p_i$，但是不清楚喵喵的分组，你想知道排列 $q_1,q_2,\ldots,q_n$ 的字典序最大可能是什么。

## 输入格式

输入的第一行有一个正整数 $n$，表示喵喵数量。

第二行有 $n$ 个正整数 $p_1,p_2,\ldots,p_n$，表示每只喵喵的到达顺序。

## 输出格式

输出一行 $n$ 个正整数，表示 $q$ 的字典序最大可能。

## 样例 #1

### 样例输入 #1

```
4
2 1 4 3
```

### 样例输出 #1

```
1 4 2 3
```

## 样例 #2

### 样例输入 #2

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

### 样例输出 #2

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

## 提示

【样例 1 解释】

所有可能的分组情况有 $8$ 种可能，下面分别列出：

|分组情况|最终排列 $q$|
|:-:|:-:|
|$(2)(1)(4)(3)$|$1,2,3,4$|
|$(2)(1)(4,3)$|$1,2,3,4$|
|$(2)(1,4)(3)$|$1,4,2,3$|
|$(2)(1,4,3)$|$1,3,4,2$|
|$(2,1)(4)(3)$|$1,2,3,4$|
|$(2,1)(4,3)$|$1,2,3,4$|
|$(2,1,4)(3)$|$1,2,4,3$|
|$(2,1,4,3)$|$1,2,3,4$|

关于表格，我们以 $(2)(1,4,3)$ 这个分组方式为例，演示排队结果的计算：

- 首先 $(2)$ 这组喵喵的到达时间为第 $2$，$(1,4,3)$ 这组喵喵的到达时间为第 $1$，从而 $(1,4,3)$ 排在前面。
- 然后 $(1,4,3)$ 这组喵喵内部按照到达时间排序，得到 $1,3,4$；$(2)$ 这组喵喵内部按照到达时间排序得到 $2$。
- 最后把每组喵喵的排序结果拼起来，得到 $1,3,4,2$。

【样例 2 解释】

读者不难验证，无论喵喵怎么分组，因为无论组内还是组外都是从小到大排序的，所以 $q_i$ 永远是 $1,2,3,4,5,6$。

【数据范围】

对于全体数据，保证 $1\le n\le 3\times 10^5$，且 $p_i$ 构成 $1\sim n$ 的一个排列。

|子任务编号|$n\le$|特殊性质|分值|
|:-:|:-:|:-:|:-:|
|1|$3$||11|
|2|$16$||16|
|3|$2000$||22|
|4|$3\times 10^5$|A|17|
|5|$3\times 10^5$||34|

- 特殊性质 A：存在 $1\le k\le n$ 使得 $p_1>p_2>\ldots >p_{k-1}> p_k < p_{k+1}<\ldots < p_n$。例如，样例 2 就是 $k=6$ 的情形。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

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