title: 画矩形

background: 扇贝宫主是一个初三的菜鸡，不擅长出毒瘤题。这天，Ta随手 A 了中国象棋这题，忽然灵光乍现...

description:
扇贝宫主画了一个 $n \times m$ 的矩形网格图。具体来说，包含坐标 $(x,y)$（$x\in [0,n], y\in [0,m]$）的所有整点以及所有连接距离为 $1$ 的点的边。

这时，扇贝宫主突发奇想，想知道这个矩形里面能够绘制多少个周长不大于 $k$ 的矩形（矩形的四边必须平行于坐标轴）。但这即使作为签到题也未免太简单了些，于是扇贝宫主加入了 $q$ 个障碍点，要求选取的矩形**不包含**障碍点。每个障碍点都是一个 $1\times 1$ 的正方形。现在扇贝宫主要继续出其他签（毒）到（瘤）题了，你能帮忙解决此题吗？答案对 $998244353$ 取模。

inputFormat:
第 $1$ 行包含四个正整数 $n$，$m$，$q$ 和 $k$。

接下来 $q$ 行，第 $i$ 行包含 $2$ 个数，分别为障碍物的 $x$ 坐标与 $y$ 坐标（一个坐标为 $(x,y)$ 的障碍点四个顶点为 $(x-1,y-1),(x-1,y),(x,y-1),(x,y)$）。

outputFormat: 输出共一行一个整数，即矩形个数对 $998244353$ 取模的结果。


title: 「SWTR-7」Scores（hard version）

type: P

background:
#### 本题是 Scores 的 hard 版本。注意题目限制与 [easy](https://www.luogu.com.cn/problem/P7873) 版本不同。

#### 请注意特殊的时空限制。

description:
小 A 的班上有 $n$ 个学生。最近他们进行了一场考试，共有 $m$ 个学科。第 $i$ 个学生第 $j$ 门学科的得分为**整数** $s_{i,j}\ (0\leq s_{i,j}\leq 100)$。

同学们很重视自己在班上的排名，所以他们经常会比较自己和别的同学的分数。如果一个学生 $i$ **至少有一门学科**的分数比 $j$ **高**，ta 就会觉得自己不比 $j$ 差；相反，如果 ta **每门学科**的分数都比 $j$ **低**，ta 就会觉得自己被 $j$ 吊打了。

实际上，**上述两种情况并不是严格意义上相反的**。但是喜好八卦的小 A 打听到了每两个同学之间的分数情况，他惊讶地发现：**一个同学 $i$ 要么被 $j$ 吊打，要么不比 $j$ 差。** 同时，**如果 $i,j$ 被同一个人吊打，或同时吊打同一个人，则他们之间也有一方被另一方吊打**。我们用一个矩阵 $a_{i,j}\ (i\neq j)$ 来描述小 A 知道的同学们之间的分数关系：$a_{i,j}=0$ 表示 $i$ 被 $j$ 吊打；$a_{i,j}=1$ 表示 $i$ 不比 $j$ 差。

小 A 想知道这种情况会不会发生，即是否存在这样一张 $n\times m$ 的成绩表 $s$ 满足矩阵 $a$ 所描述的分数关系，从而确定有没有撒谎的同学。如果存在 $s$，请先输出 $\texttt{YES}$，再**任意**输出一种符合要求的成绩表；否则输出 $\texttt{NO}$。

注意：这里所求的 $s$ 所需满足的条件是 $a$ 的限制，而**不只是**小 A 所发现的性质，因为**他发现的性质已经在给出的 $a$ 中体现**。

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

第一行一个整数 $t$，**表示该测试点编号**。
第二行一个整数 $T$，**表示数据组数**。

对于每组数据：
第一行两个整数 $n,m$。
接下来 $n$ 行，每行 $n$ 个由空格隔开的 0 或 1 描述 $a$。第 $i+1$ 行第 $j$ 个数表示 $a_{i,j}$。

特别的，为了方便读入，**规定 $a_{i,i}=0$**。但你需要知道**它没有任何实际意义**。

outputFormat:
对于每组数据：

如果不存在满足条件的 $s$，输出一行字符串 $\texttt{NO}$。
否则先输出一行字符串 $\texttt{YES}$，再输出 $n$ 行，每行 $m$ 个由空格隔开的整数，第 $i+1$ 行第 $j$ 个数表示 $s_{i,j}\ (0\leq s_{i,j}\leq 100)$。

hint:
**「Special Judge」**

**本题使用 Special Judge。请认真阅读输出格式，输出格式有误可能导致 UKE 或 WA。**

SPJ 首先会判断你的第一行输出是否与答案相同。
如果相同且答案为 $\texttt{YES}$，则 SPJ 会判断你的输出是否符合所有限制。
如果有解且你输出 $\texttt{YES}$，但给出方案错误，你将获得该测试点 $50\%$ 的分数。

你需要满足的限制如下：
- $0\leq s_{i,j}\leq 100$。
- 对于任意 $i,j\ (i\neq j)$，若 $a_{i,j}=0$，则对于任意 $k\ (1\leq k\leq m)$，有 $s_{i,k}<s_{j,k}$；若 $a_{i,j}=1$，则存在一个 $k\in [1,m]$，使得 $s_{i,k}>s_{j,k}$。

你需要注意的是，所有输出都应严格符合输出格式。如果你对答案的存在性判断正确，但是输出方案时 $s_{i,j}<0$ 或 $s_{i,j}>100$，SPJ 会判定为 WA，得 $0$ 分，而不是 $50\%\ \times$ 该测试点分数。

**「数据范围与约定」**

本题共有 6 个测试点。

- Testcase #0（1 point）：是样例。
- Testcase #1（10 points）：$n=1$。
- Testcase #2（10 points）：$m=1$。
- Testcase #3（30 points）：$m=2$。
- Testcase #4（20 points）：$a_{i,j}=1\ (i\neq j)$。
- Testcase #5（29 points）：无特殊限制。

对于 $100\%$ 的数据，$1\leq n,m\leq 100$，$a_{i,j}\in\{0,1\}$，$T=50$（除 Testcase #0）。
对于 $a$ 的限制：若 $a_{i,j}=a_{i,k}=0$，则 $a_{j,k}$ 和 $a_{k,j}$ 中至少有一个为 $0$；若 $a_{i,k}=a_{j,k}=0$，则 $a_{i,j}$ 和 $a_{j,i}$ 中至少有一个为 $0$。
对于所有测试点，**时间限制 500ms，空间限制 16MB。**

**「题目来源」**

[Sweet Round 07](https://www.luogu.com.cn/contest/51773) A2。
idea & solution & data：[Alex_Wei](https://www.luogu.com.cn/user/123294)；验题：[chenxia25](https://www.luogu.com.cn/user/138400)。


title: 「SWTR-7」My rating is 1064（hard version）

background:
#### 本题是 My rating is ... 的 hard 版本。注意题目限制与 [easy](https://www.luogu.com.cn/problem/T130499) 版本不同。

#### 题目描述下方有简化题意。

[My rating is 1064.](https://codeforces.com/blog/entry/74503)（被 2 - Tower 炸掉了，因此现在打不开了）

description:
小 A 想在 Codeforces 上发 $n$ 篇帖子！例如：

> “My rating is 1064.”
>
> “I am PolarSea.”
>
> “你知道 phi 吗？你知道你的 phi 处是哪里吗？你知道它的 price 吗？1e9 + 7。”
>
>“每道题都很简单，全场虐题不用烦。T1 到场先签到，T2 上手随便切，T3 一交就能过，T4 稍想也能 A。DP 转移很容易，数学结论尽皆知。建图方法极明显，数据结构很一般。不卡空间不卡常，码量不大手不酸。没有毒瘤大模拟，只有良多大水题。片刻四题提交过，人人 AK 笑开颜。”
>
> “……”

为此，小 A 新注册了 $k$ 个账号。他决定按照顺序发出每篇帖子，并**用到所有 $k$ 个账号**。不过刷屏过多会引起 Mike 的注意并被封号，小 A 当然不希望这样：他进行了一些评估，得到了每篇帖子的安全指数 $a_i$，表示他发出第 $i$ 篇帖子后不被封号的概率。

由于第一印象非常重要，小 A 定义一个账号的安全指数为该账号所发出的**第一篇**帖子的安全指数。此外，如果**用同一个账号连续发出两个帖子**，该账号的安全指数会减小**这两篇帖子安全指数的较小值**。

小 A 希望找到这样一个发帖方案，使得所有账号的安全指数之和最大。你只需要求出安全指数之和的最大值即可。

---

**「简化题意」**

将 $1\sim n$ **不重不漏**地分进**恰好** $k$ 个集合 $S_1,S_2,\cdots,S_k$ 中 且 $|S_i|>0$。记 $i$ 被分入第 $d_i$ 个集合，求

$$\left(\sum_{i=1}^k a[{\min_{j\in S_i}j}]\right)-\left(\sum_{i=1}^{n-1}\min(a_i,a_{i+1})[d_i=d_{i+1}]\right)$$

的最大值，其中左边的 $[x]$ 表示下标为 $x$，右边的 $[x]$ 表示当 $x$ 成立时取值为 $1$，当 $x$ 不成立时取值为 $0$。

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

第一行一个整数 $t$，表示该测试点编号。
第二行一个整数 $T$，表示数据组数。

对于每组数据：

第一行两个整数 $n,k$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示每个帖子的安全指数。

outputFormat: 对于每组数据，一行一个整数表示答案。

hint:
**「样例 1 说明」**

小 A 可以使用账号 $1$ 发帖子 $1,2$ 和 $4$，用账号 $2$ 发帖子 $3$。其安全程度为 $(a_{\min(1,2,4)}-\min(a_1,a_2))+a_3=1-1+3=3$。

**「数据范围与约定」**

本题共有 6 个测试点。

- Testcase #0（1 point）：是样例。
- Testcase #1（20 points）：$k=2$。
- Testcase #2（20 points）：$n\leq 10$，$k\leq 4$。
- Testcase #3（15 points）：$k=3$。
- Testcase #4（20 points）：$n\leq 10^3$。
- Testcase #5（24 points）：无特殊限制。

对于 $100\%$ 的数据，$2 \leq k \leq n \leq 10^5$，$0 \leq a_i \leq 10^9$，$T=10$（除 Testcase #0）。
对于所有测试点，时间限制 1s，空间限制 128MB。

**「题目来源」**

[Sweet Round 07](https://www.luogu.com.cn/contest/) B2。
idea & solution：[tzc_wk](https://www.luogu.com.cn/user/115194) & [Alex_Wei](https://www.luogu.com.cn/user/123294)（加强）；data：[Alex_Wei](https://www.luogu.com.cn/user/123294)；验题：[chenxia25](https://www.luogu.com.cn/user/138400)。

> **My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. ……**
>
> **Upvote -77 Downvote                  PolarSea**


title: 「MCOI-Zero / AC6-M07」Selumna Peak

background:
「Now that's what I call squadron！」

「Come on, it's payback time.」

**「Gracemeria is dead ahead！！」**

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 07} \\\Large\text{Selumna Peak}\\\tiny-\textit{ Shimmering Death }-$$

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

description:
给定 $1\sim n$ 的排列 $a_{[1,n]}$。

请对于每一个 $i$，考虑如下操作序列：

1. 首先在 $[1,i]$ 中选取一个子序列（可以为空）；
2. 然后将这个子序列内的数重新排列。

求出 **所有不同的操作序列产生的排列** 的逆序对数总和是多少，答案模 $20051131$。

两个操作序列不同当且仅当选取的子序列不同或重新排列的方式不同。

操作不会真正被执行到排列上。

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

接下来一行 $n$ 个数，表示排列 $a$。

outputFormat: $n$ 行，每行一个数，表示对于前缀 $[1,i]$ 所有不同的操作序列产生的排列的逆序对数总和模 $20051131$ 的值。

hint:
样例 1 解释：

- 对于 $[1,1]$，无法产生逆序对，答案为 $0$。
- 对于 $[1,2]$，只有一种操作序列可以产生 $2,1,3$，答案为 $1$。
- 对于 $[1,3]$：
	- 有 $8$ 种操作序列产生 $1,2,3$；
   - 有 $2$ 种操作序列产生 $1,3,2$；
   - 有 $2$ 种操作序列产生 $2,1,3$；
   - 有 $1$ 种操作序列产生 $2,3,1$；
   - 有 $1$ 种操作序列产生 $3,1,2$；
   - 有 $2$ 种操作序列产生 $3,2,1$；
- 答案为 $0\times 8+1\times 2+1\times 2+2\times 1+2\times 1+2\times 3=14$。

样例 2 解释：

- 对于 $i=1$，只有两种操作序列，产生的排列都有 $8$ 个逆序对，故答案是 $16$。
- 对于 $i=2$，有 $4$ 种操作序列产生 $3, 2, 4, 1, 6, 8, 7, 5$，有 $1$ 种操作序列产生 $2,3,4,1,6,8,7,5$，答案为 $8\times 4+7\times 1=39$。

数据范围：

- Subtask 1（10%）：$n\leq 8$。
- Subtask 2（20%）：$n\leq 50$。
- Subtask 3（20%）：$n\leq 300$。
- Subtask 4（20%）：$n\leq 3\times 10^3$。
- Subtask 5（30%）：无特殊限制。

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

idea：Sol1，solution：Sol1，code：Sol1，data：Sol1


title: 「JZOI-1」拜神

background: 新年快到了，小僖和爸爸妈妈上山拜神，祈求新一年的好气运。

description:
小僖要拜的神一共有 $n$ 个，小僖对每个神的信仰可以用一个小写字母表示，信仰排在一起形成了一个从标号 $1$ 开始的字符串 $s$。

小僖需要祈祷词来拜神，定义一段祈祷词为一个长度大于零的 $s$ 的连续子串，祈祷词的长度为这个子串的长度。由于拜神只需要小僖有着一定的认真度，所以一种祈祷词只要出现两次就可以被称之为有效的。

**注意：只要子串出现的位置开头不同，中间有重复部分也没有问题**。

但是由于还有爸爸妈妈的存在，小僖的祈祷词有时会被干扰而打断，所以只有区间 $[l,r]$ 的字符串（即 $s[l\dots r]$）有效。为了未雨绸缪，小僖将会对可能的情况进行精心准备。

他会给出 $q$ 次询问，每次询问将给定 $l,r$，询问区间 $[l,r]$ 的最长的有效祈祷词的长度。

inputFormat:
第一行输入两个正整数 $n,q$。
第二行输入一个由小写字符构成的字符串 $s$。
接下来有 $q$ 行，每行输入两个数 $l,r$。

outputFormat: 输出 $q$ 行，每行输出一个非负整数，代表最长的有效祈祷词的长度，若无有效祈祷词，则输出 $0$。

hint:
#### 样例解释：
对于第一次询问：区间内的字符串为 $\texttt{ababa}$，其中子串 $\texttt{aba}$ 出现了两次，长度为 $3$ 。
对于第二次询问：区间内的字符串为 $\texttt{dababab}$，其中子串 $\texttt{abab}$ 出现了两次，长度为 $4$ 。
对于第三次询问：区间内的字符串为 $\texttt{ababdc}$，其中子串 $\texttt{ab}$ 出现了两次，长度为 $2$ 。
对于第四次询问：区间内的字符串为 $\texttt{babdc}$，其中子串 $\texttt{b}$ 出现了两次，长度为 $1$ 。
对于第五次询问：区间内的字符串为 $\texttt{cdab}$，无出现至少两次的子串，答案为 $0$ 。

#### 数据范围：
对于 $5\%$ 的数据，$n,q\le50$。
对于 $15\%$ 的数据，$n,q\le200$。
对于 $30\%$ 的数据，$n,q\le2\times10^3$。
对于 $40\%$ 的数据，$n,q\le5\times10^3$。
对于 $65\%$ 的数据，$n,q\le2\times 10^4$。
对于另外 $5\%$ 的数据，满足所有的字符都相等。
对于 $100\%$ 的数据，$1 \le n\le5\times10^4$，$1 \le q \le 10^5$。


title: [COCI2018-2019#5] Ispit

description: 给定一个 $N$ 行 $N$ 列的字母矩阵和整数 $K$。是否有连续的 $K$ 列，使得这 $K$ 列中每一行在行内进行重组（即只能交换同行的字母）后，能够使原矩阵有两行完全相同？

inputFormat:
第一行输入整数 $N,K$。

接下来的 $N$ 行，每行输入 $N$ 个字符，表示原来的字母矩阵。

outputFormat: 如果有符合题意的方案，则输出 `DA`，否则输出 `NE`。

hint:
#### 样例 1 解释

选定第 $2,3$ 列，并将第 $2,3,4$ 行中的这两列的字母进行交换，得到新矩阵：

```plain
abcd
abcd
eana
mzoe
```

这时，第 $1,2$ 行完全相同，因此满足题意。

#### 数据规模与约定

对于 $30\%$ 的数据，$N \le 10$。

对于另外 $40\%$ 的数据，$N \le 200$。

对于 $100\%$ 的数据，$2 \le K \le N \le 500$。

#### 说明

**本题分值按 COCI 原题设置，满分 $90$。**

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #5](https://hsin.hr/coci/archive/2018_2019/contest5_tasks.pdf)  _T3 Ispit_。**


title: [COCI2018-2019#5] Parametriziran

description:
我们规定一个包含小写字母和问号的字符串为一个**参数化单词**。例如，`a??cd`，`bcd`，`??` 都属于参数化单词。

如果两个参数化单词中，可以用特定的小写字母将其中的问号进行替换，并最终使得两个单词完全相同，那么原来的两个参数化单词就被称为是相似的。例如，`a???` 和 `?b?a` 都可以替换为 `abba`，因此 `a???` 和 `?b?a` 是相似的。

给定 $N$ 个长度为 $M$ 的参数化单词，求有多少对相似的参数化单词。

inputFormat:
第一行输入整数 $N,M$。

接下来的 $N$ 行，每行输入一个长度为 $M$ 的参数化单词。

outputFormat: 输出相似的参数化单词的对数。

hint:
#### 样例 1 解释

`??b` 和 `c??` 是相似的，而 `c??` 和 `c?c` 也是相似的。因此共有 $2$ 对相似的参数化单词。

#### 数据规模与约定

对于 $30\%$ 的数据，$M \le 2$。

对于另外 $30\%$ 的数据，$M \le 4$。

对于 $100\%$ 的数据，$1 \le N \le 5 \times 10^4$，$1 \le M \le 6$。

#### 说明

**本题分值按 COCI 原题设置，满分 $110$。**

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #5](https://hsin.hr/coci/archive/2018_2019/contest5_tasks.pdf)  _T4 Parametriziran_。**


title: [COCI2018-2019#6] Lun

description:
现有一个判断某种银行卡号是否合法的算法：

1. 从倒数第二位开始从右往左，每隔一个数位就将其乘 $2$，否则保留原数位不变。
2. 将被乘 $2$ 的数位分别计算其数位之和。
3. 计算经过操作之后的所有数位之和，并将其乘 $9$ 再对 $10$ 取模，检验其是否等于最后一位（即银行卡号的校验码）。

若待验证卡号为 $79927398713$，则判断方法如下：

|银行卡号各数位|$7$|$9$|$9$|$2$|$7$|$3$|$9$|$8$|$7$|$1$|$3$|
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
|每隔一位乘 $2$（从倒数第二位开始向左）|$7$|$\red {18}$|$9$|$\red 4$|$7$|$\red 6$|$9$|$\red {16}$|$7$|$\red 2$| -|
|计算得到的数位和并累加|$7$|$\green 9$|$9$|$4$|$7$|$6$|$9$|$\green 7$|$7$|$2$|$=67$|

将得到的和 $67$ 乘 $9$ 再对 $10$ 取模，得到 $67 \times 9 \bmod 10=3$。其中 $3$ 为该银行卡号校验码，因此原卡号合法。

现有一个缺失一个数位的银行卡号，请根据上述算法在缺失数位处补充一个合适的数位，使得得到的银行卡号合法。

inputFormat:
第一行输入整数 $N$，表示缺失数位的银行卡号的长度。

第二行有一个长度为 $N$ 的字符串，表示银行卡号。该字符串中只包含数位 $0 \sim 9$ 和字符 `x`。字符 `x` 将且仅将出现一次，表示缺失的数位。

outputFormat: 输出符合题意的数位。如果有多种符合题意的数位，则输出最小的。

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

对于 $50\%$ 的数据，缺失的数位位于银行卡号校验码处，即字符 `x` 位于字符串最后一位。

对于 $100\%$ 的数据，$1 \le N \le 100$。

#### 说明

**本题分值按 COCI 原题设置，满分 $50$。**

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #6](https://hsin.hr/coci/archive/2018_2019/contest6_tasks.pdf)  _T1 Lun_。**


title: 「Byakkai OI 2021」Eaquira

description:
给定 $n$，并在数轴上截取 $[1,n]$ 的整点。

定义**极长连续黑区间段**为满足 $1 \le L \le R \le p$ 的区间段 $[L,R]$，且编号在 $[L,R]$ 内的区间都是黑色，且其不能再扩展，即编号为 $L-1$（如果存在，下同）和 $R+1$ 的区间都是白色。

首先，请您将它们划分成若干个区间 $[l_1,r_1],[l_2,r_2],\dots,[l_p,r_p]$，满足 $l_1=1,r_p = n$，且对于 $1 \le i < p$ 有 $r_i = l_{i+1}-1$；对于 $1 \le i \le p$ 满足 $l_i \le r_i$。

其二，您需要将每个区间标记为黑色或是白色，但不允许第 $1$ 个区间和第 $p$ 个区间同时被标记为黑色。

其三，请您在每个区间内选出一个子区间，称为**绝妙子区间**。

其四，请您在每个极长连续黑区间段中各选出一个黑色区间，称为**绝妙黑区间**。

其五，在所有的极长连续黑区间段中钦定若干个称作**绝妙极长连续黑区间段**。

定义一种以上述步骤所确定的方案的权值为黑色区间的个数与绝妙极长连续黑区间段个数的和。

我本来希望您求出对于 $s = 0,1,2,\dots,n$ 得到可以使得最终权值为 $s$ 的方案数。不过我也准备了一些更低要求的挑战。详见输入格式。

答案对 $998244353$ 取模。

inputFormat:
一行，两个整数 $n,{\rm type}$。

若 ${\rm type} = 0$，则表示需要对 $0 \le s \le n$ 求出权值为 $s$ 的方案数。
若 ${\rm type} = 1$，则表示需要求出对所有 $0 \le s \le n$ 的总方案数。

outputFormat:
若 ${\rm type} = 0$，则一行 $n+1$ 个非负整数，依次表示对于 $s = 0,1,2,\dots,n$ 的答案。
若 ${\rm type} = 1$，则一行一个非负整数，表示答案。


title: 「EZEC-7」Erinnerung

description:
小 Y 和小 Z 都是生活在 Arcaea Offline 的精灵。小 Y 有无数片落叶，其中第 $i$ 片落叶的价值为 $C_i$。小 Z 有无数片雪花，其中第 $i$ 片雪花的价值为 $E_i$。经过小 X 的仔细观察，他发现 $C$ 和 $E$ 满足特殊的条件：

$$
C_i=
\begin{cases}
x\times i& (x\times i\le K)\\
-K& \text{otherwise}
\end{cases}
$$
$$
E_i=
\begin{cases}
y\times i& (y\times i\le K)\\
-K& \text{otherwise}
\end{cases}
$$

小 Y 和小 Z 可以对这些落叶和雪花进行一些操作。每次，他们会选择满足价值之和 $\ge K$ 的一片落叶和一片雪花，然后让把它们一同组成一段彩色的回忆（Erinnerung）。之后，这片雪花和这片落叶就消失不见了，之后的操作也不能再用到这片雪花和落叶了。

小 X 想知道，他们最多能进行多少次操作。

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

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

接下来 $T$ 行，每行三个非负整数 $x,y,K$。

outputFormat: 对于每组数据，输出一个整数，代表最多能有多少次操作。每组数据的答案用一个换行符隔开。

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

对于样例 1 的第一组数据，落叶的价值为 $2,4,6,8,10,-10,-10\dots$ ，雪花的价值为 $3,6,9,-10,-10\dots$ 。第一次操作选取第 $4$ 片落叶和第 $1$ 片雪花，价值和为 $11$。第二次操作选取第 $2$ 片落叶和第 $2$ 片雪花，价值和为 $10$。第三次操作选取第 $5$ 片落叶和第 $3$ 片雪花，价值和为 $19$。如是，可以进行 $3$ 次操作。容易证明不存在更优的解。

对于第二组数据，进行的两次操作可以为：选取第 $4$ 片落叶和第 $1$ 片雪花，以及选取第 $2$ 片落叶和第 $2$ 片雪花。

对于样例 2，所有的雪花和落叶的价值都为 $0$，不可能找到落叶和雪花使其和 $\ge 1$。

---

**【数据范围】**

-  Subtask 1（30 points）：$x,y,K,T\le 10$。
-  Subtask 2（70 points）：无特殊限制。

对于 $100\%$ 的数据，满足 $0\le x,y\le 10^{10}$，$1\le K\le 10^{10}$，$1\le T\le 10^5$。


title: 更简单的排列计数

description:
设 $\text{cyc}_\pi$ 将长为 $n$ 的排列 $\pi$ 当成置换时所能分解成的循环个数。给定两个整数 $n,k$ 和一个 $k-1$ 次多项式，对 $1\leq m\leq n$ 求：

$$
\sum\limits_{\pi}F(\text{cyc}_{\pi})
$$

其中 $\pi$ 是长度为 $m$ 且不存在位置 $i$ 使得 $\pi_i=i$ 的排列。

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

第二行 $k$ 个整数，从低到高给出多项式的系数。

outputFormat: 一行 $n$ 个整数，表示答案对 $998244353$ 取模的值。


title: 「PMOI-3」期望乘积

description:
ducati 热爱定义一些奇奇妙妙的东西。

- 定义两个序列不同，当且仅当它们的长度不同，或者它们长度相同但存在至少一组对应位上的值不同。

- 定义序列 $A$ 的权值为 $A$ 中所有数的**乘积**。

- 定义序列间的**可达**如下：

  - 做**恰好** $t$ 次操作，每次操作选择 $A$ 的一个子区间（**注意，选定的子区间可以为空**）并将子区间中的数加 $1$ ；若存在一种操作方案，使得操作结束后 $A$ 与 $B$ 完全相同 ，则称 $A$ 可达 $B$。

- 定义序列 $A$ 的优美值为 $A$ 可达的**所有不同**序列的**权值**和。

现在，ducati 拥有了一个长度为 $n$ 的序列 $a$。他会多次查询一段区间的优美值。

你能帮帮好奇的他吗？你只需要输出每个答案对 $10007$ 取模的值就行啦。

inputFormat:
第一行三个整数 $n,q,t$，表示序列的长度、询问的次数与每次询问的可修改次数。

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

下面 $q$ 行，每行两个正整数 $l,r$，描述一次询问。

outputFormat: 对于每次询问，输出答案对 $10007$ 取模的值。

hint:
【样例解释1】

$a$ 为 $\{1,2\}$。共 $1$ 次询问。

所有 $a$ 可达的 $b$ 如下：

$$\{1,3 \} \{2,2 \} \{2,3 \}\{1,2 \}$$

它们的权值之和为 $3+4+6+2=15$ 。

【样例解释2】

关于第二个样例，我有一个绝妙的解释，可惜这里空白太小，我写不下。

【数据范围】

**本题采用捆绑测试**。
- Subtask1（10pts）：$n,q\le8$；
- Subtask2（20pts）：$q=1$；
- Subtask3（30pts）：$n,q\le5\times10^4$，$t\le2$；
- Subtask4（40pts）：无特殊限制。

对于 $100\%$ 的数据满足，$1\le n,q\le10^5$，$1\le a_i\le10^4$，$1\le t\le3$，对于所有询问，$1\le l\le r\le n$。


title: [COCI2018-2019#6] Konj

description:
Domagoj 有一种奇特的绘画手法。首先他准备了 $N$ 条待画的线段，每条线段连接两个点，即 $(A_i,B_i)$ 和 $(C_i,D_i)$。接着，他选定一个点 $T$。然后，Domagoj 将画出所有符合下列条件之一的线段：

- 经过点 $T$
- 与经过点 $T$ 的线段直接或间接相连

当两条线段 $L_1,L_2$ 有一个公共端点时，我们认为 $L_1,L_2$ 是直接相连的。当线段 $L_1$ 与 $H_1$，$H_1$ 与 $H_2$，$\cdots$，$H_k$ 与 $L_2$ 都是直接相连的，那么我们认为 $L_1,L_2$ 是间接相连的。

你的任务是打印出 Domagoj 最终画出的图像。输出的形式为一个矩阵 $P$。当有线段经过 $(a,b)$ 时，应在 $P(a,b)$ 的位置输出 `#`，否则输出 `.` 字符。注意横坐标 $a$ 从左到右依次增大，纵坐标 $b$ 从下到上依次增大（这与平面直角坐标系的系统保持一致）。矩阵 $P$ 不能有任何一列或一行都是 `.` 字符，即矩阵必须在包含所有要画出的线段的前提下，在大小上最小。

inputFormat:
第一行输入待画线段的个数 $N$。

接下来的 $N$ 行，每行输入四个非负整数 $A_i,B_i,C_i,D_i$，表示第 $i$ 条线段的端点 $(A_i,B_i)$ 和 $(C_i,D_i)$。对于每条线段，$A_i \neq C_i$ 和 $B_i \neq D_i$ 将且仅将成立其中一个，即任何一条线段都与坐标轴平行。同时，没有线段会相交，但可能会共用同一个端点。

接下来的一行（即最后一行），输入整数 $X,Y$，表示 $T$ 的坐标。保证至少有一条线段的其中一个端点为 $T$。

outputFormat: 输出所求的矩阵 $P$。

hint:
#### 样例 1 解释

除了最后一条线段，其它的都需要画出。即除了连接 $(42,42)$ 和 $(42,43)$ 的线段之外，其它都必须画出。

#### 样例 2 解释

所有线段都必须画出。

#### 数据规模与约定

对于 $30\%$ 的数据，需要画出所有线段。

对于 $100\%$ 的数据，$1 \le N \le 2 \times 10^5$，$0 \le A_i,B_i,C_i,D_i \le 300$。

#### 说明

**本题分值按 COCI 原题设置，满分 $70$。**

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #6](https://hsin.hr/coci/archive/2018_2019/contest6_tasks.pdf)  _T2 Konj_。**


title: [COCI2018-2019#6] Sličice

description:
Nikola 喜欢收集足球队员的照片，并将其保存在相册中。他计划收集 $N$ 支球队的队员照片，其中每支球队都有 $M$ 张。

对于 Nikola 所收集的每支球队，该球队的照片数量 $x$ 能给他增加分数 $B_x$。他目前拥有球队 $i$ 的照片数量为 $P_i$。

Nikola 的好朋友 Ivan 有两套完整的相册。Ivan 决定送 $K$ 张照片给 Nikola。Nikola 想要知道，在得到这 $K$ 张照片之后，它的相册所能得到的分数的最大值。

inputFormat:
第一行输入整数 $N,M,K$。

第二行输入 $N$ 个整数 $P_i$。

第三行输入 $M+1$ 个整数 $B_i$，其中 $B_i$ 表示一支球队收集到了 $i$ 张不同的照片能够获得 $B_i$ 分。

对于 $[0,M-1]$ 内的每一个整数 $t$，都满足 $B_t \le B_{t+1}$。同时 $K \le N \times M-\sum_{i=1}^N P_i$。

outputFormat: 输出能够得到的分数的最大值。

hint:
#### 样例 1 解释

Nikola 一开始拥有球队 $1,2,3,4$ 照片数量分别为 $4,2,3,1$。最优的方案是获得球队 $2,3$ 照片各 $1$ 张。此时分数最大，为 $10+10+10+1=31$。

#### 数据规模与约定

对于 $20\%$ 的数据，$K=2$。

对于 $100\%$ 的数据，$1 \le N,M \le 500$，$1 \le K \le \min(N \times M,500)$，$0 \le P_i \le M$，$0 \le B_i \le 10^5$。

#### 说明

**本题分值按 COCI 原题设置，满分 $90$。**

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #6](https://hsin.hr/coci/archive/2018_2019/contest6_tasks.pdf)  _T3 Sličice_。**


title: [COCI2018-2019#6] Simfonija

description:
给定包含 $N$ 个元素的数组 $A,B$。将 $A$ 数组内的所有元素都加上一个**整数** $X$，并修改不超过 $K$ 个元素，使得下列代数式最小：

$$\sum_{i=1}^N |A_i-B_i|$$

inputFormat:
第一行输入整数 $N,K$。

第二行输入 $N$ 个整数 $A_i$。

第三行输入 $N$ 个整数 $B_i$。

outputFormat: 输出操作之后代数式的最小值。

hint:
#### 样例 2 解释

当选定 $X=3$，并将 $A$ 数组最后一个数改为 $7$ 后，$A,B$ 两数组完全相同，此时代数式的值为 $0$。

#### 数据规模与约定

对于 $40\%$ 的数据，$K=0$。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le K \le N$，$-10^6 \le A_i,B_i \le 10^6$。

#### 说明

**本题分值按 COCI 原题设置，满分 $110$。**

**题目译自 [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #6](https://hsin.hr/coci/archive/2018_2019/contest6_tasks.pdf)  _T4 Simfonija_。**


title: 黄牛の争

background:
Source：天空之城

本题背景中「黄牛」仅代指某游戏中的一种怪物，与一般含义的「[**黄牛**](https://baike.baidu.com/item/黄牛党/285883)」无关。

本题「推荐题目」三灰一黑，但不太能说明本题难度和他们差不多（

相传在很久很久之前梅兰德大陆上空漂浮着一座天空之城，是当时财富、力量、荣誉中心，突然有一天再也不见踪影。

如今已多个世纪不见痕迹的天空之城突然出现，王国的勇士去探索一番，但是飞船船票可不是那么好得到的。

**飞艇码头的船长是梅德龙 · 杜鲁夫，船长为了牟利要求大家必须 *买* *票* *上* *船*，没有票的旅行者无法登船。**

დ琢喵 作为一届黄牛的首领——黄牛党，派出了 $q$ 组黄牛买断了梅德龙 · 杜鲁夫的船票。

她以高价卖出这些船票，并通过差价获取巨额利润。

为维护飞艇码头的治安，梅德龙 · 杜鲁夫规定不允许人类和黄牛打架，当然船长并没有规定黄牛之间不可以打架。

description:
დ琢喵 的手下有两种黄牛：

1. I 类黄牛「攻击」为 $a$，「血量」为 $A$；
2. II 类黄牛「攻击」为 $b$，「血量」为 $B$。

黄牛之间的作战，满足以下条件：

1. 任意时刻，某一方「血量」$\le 0$ 时，其对手胜利；
2. 每一回合，「攻击」高者先手；
3. 每回合每方出手一次，造成的伤害即其「攻击」值。

构造的 III 类黄牛应当满足下面条件：

1. 「攻击」数值与 I 类黄牛和 II 类黄牛都不同；
2. I 类黄牛和 II 类黄牛作战 II 类黄牛胜利；（若输入不满足该条件则应直接输出 `-1 -1`）
3. II 类黄牛和 III 类黄牛作战 III 类黄牛胜利；
4. III 类黄牛和 I 类黄牛作战 I 类黄牛胜利。

请给出一种合法的构造。

---

**题意简述**

解方程：（若 $x=\text{true}$ 则 $[x]=1$ 反之 $=0$）

$$\begin{aligned}\left\lceil\frac{A}{b}\right\rceil&+[b<a]\le\left\lceil\frac{B}{a}\right\rceil\\\left\lceil\frac{B}{c}\right\rceil&+[c<b]\le\left\lceil\frac{C}{b}\right\rceil\\\left\lceil\frac{C}{a}\right\rceil&+[a<c]\le\left\lceil\frac{A}{c}\right\rceil\\c&\ne a~\text{and}~c\ne b\end{aligned}$$

已知 $a,A,b,B$，解 $c,C$。

inputFormat:
**本题多测。**

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

接下来 $q$ 行，每行四个正整数 $a,A,b,B$。

数据满足 $a\ne b$。

outputFormat:
一共 $q$ 行，每行两个正整数表示你构造的 III 类黄牛的「攻击」数值和「血量」数值，无解时输出 `-1 -1`。

**本题采用 Special Judge，所有满足要求的解均给分。**

hint:
### 样例说明

对于样例 #1，可设 A 是 $(1,5)$，B 是 $(2,3)$，C 是 $(4,1)$。

其中二元组 $(x,y)$ 表示一个「攻击」为 $x$，「血量」为 $y$ 的黄牛。

下面的表格展现了 A、B、C 的对战情况，括号中的数字表示每回合开始时它们的「血量」数值。

| A 和 B 单挑 | B 和 C 单挑 | C 和 A 单挑 |
| :----------: | :----------: | :----------: |
| $\begin{aligned}&\texttt{A(5)~B(3)}\overset{\texttt{A-2~B-1}}{\Rightarrow\Rightarrow}\\&\texttt{A(3)~B(2)}\overset{\texttt{A-2~B-1}}{\Rightarrow\Rightarrow}\\&\texttt{A(1)~B(1)}\overset{\texttt{A-2}}{\Rightarrow}\\&\texttt{A}\le\texttt{0~\color{red}B win}\end{aligned}$ | $\begin{aligned}&\texttt{B(3)~C(1)}\overset{\texttt{B-4}}{\Rightarrow}\\&\texttt{B}\le\texttt{0~\color{red}C win}\end{aligned}$ | $\begin{aligned}&\texttt{A(5)~C(1)}\overset{\texttt{A-4~C-1}}{\Rightarrow\Rightarrow}\\&\texttt{C}\le\texttt{0~\color{red}A win}\end{aligned}$ |

因此输出剩下一类黄牛即给分。

对于样例 #2：钦定 III 类黄牛攻击力为 $11$，已经足以击倒 II 类黄牛，血量为 $11\sim14$ 都可以输给 I 类黄牛。

因此任意输出一组均给分。

对于样例 #3：II 类黄牛十分强大，难以再构造又能击败 II 类黄牛又能输给 I 类黄牛的 III 类黄牛品种。

因此输出 `-1 -1` 即给分。

### 数据规模

设 $M=\max\left(a,A,b,B\right)$：

- Subtask1(10pts)：$M\le10,q=399\underline0$。
- Subtask2(20pts)：$M\le100,q=399\underline1$，数据随机。
- Subtask3(10pts)：$M\le10^5,q=99\underline2$，数据随机。
- Subtask4(20pts)：$M\le10^5,q=99\underline3$。
- Subtask5(10pts)：$q=399\underline4$，数据随机。
- Subtask6(30pts)：$q=399\underline5$，无特殊限制。
- 本题根据数据强度设置了不同梯度的时间限制，如果有合理的满分做法被卡了请联系我。

提示：数据组数 $q$ **结尾** 的数字（$\underline0,\underline1,\underline2,\underline3,\underline4,\underline5$）可能有助于你判断 Subtask 的类型。

对于 $100\%$ 的数据：$1\le q<4000,1\le M\le10^8$。

### 大样例

本题提供符合 Subtask $2,3,5$ 限制的测试用例。

直接编译并运行下面代码，即可得到 `E01.in` `E02.in` `E03.in` 分别是满足 Subtask $2,3,5$ 限制的测试数据。

```cpp
#include<ctime>
#include<cstdio>
#include<random>
#include<string>
#include<cassert>
#include<cstdlib>
#include<iostream>
#define int long long
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
void printsp(int x){
	print(x), putchar(' ');
}
void println(int x){
	print(x), putchar('\n');
}
char str[] = "E  .in";
const int Buff = 3989;
std::string string;
namespace Data_Maker{
	std::mt19937 rnd(time(0));
	int rand(int l, int r) {
		int x = r - l + 1;
		return (rnd() % x + x) % x + l;
	}
	int a, A, b, B;
	void maker(int subtaskID) {
		int t = Buff + subtaskID;
		if (3 <= subtaskID && subtaskID <= 4)
			t -= 3000;
		println(t);
		if (subtaskID == 2 || subtaskID == 3 || subtaskID == 5) {
			int MOD = 0;
			if (subtaskID == 2) MOD = 100;
			if (subtaskID == 3) MOD = 100000;
			if (subtaskID == 5) MOD = 100000000;
			while (t--) {
				a = rand(1, MOD), A = rand(1, MOD);
				b = rand(1, MOD), B = rand(1, MOD);
				while (b == a)
					b = rand(1, MOD);
				printsp(a), printsp(A), printsp(b), println(B);
			}
		}
	}
	void File(int Test) {
		str[1] = Test / 10 + '0';
		str[2] = Test % 10 + '0';
		freopen(str, "w", stdout);
	}
	void Subtask2() {
		for (int Test = 1; Test <= 1; ++Test) {
			File(Test); maker(2);
		}
	}
	void Subtask3() {
		for (int Test = 2; Test <= 2; ++Test) {
			File(Test); maker(3);
		}
	}
	void Subtask5() {
		for (int Test = 3; Test <= 3; ++Test) {
			File(Test); maker(5);
		}
	}
}
using namespace Data_Maker;
signed main(){
	Subtask2();
	Subtask3();
	Subtask5();
}
```

另外还提供了下面的 Special Judge，可以编译并通过调用 `spj E.in E.out E.ans` 来获取返回信息。

```cpp

#include "testlib.h"
#define int long long
#define inf inf.readLong()
#define ouf ouf.readLong()
#define ans ans.readLong()
bool win(int a, int A, int b, int B){
  int x = 0, f = 1;
  if (a < b)
    a ^= b ^= a ^= b, A ^= B ^= A ^= B, f *= -1;
  while (1) {
    if (B - a <= 0) {
      x = 1;
      break;
    }
    if (A - b <= 0) {
      x = -1;
      break;
    }
    B -= a, A -= b;
  }
  x *= f;
  return x < 0;
}
signed main (signed argc, char**argv) {
  registerTestlibCmd(argc, argv);
  int q = inf;
  for (int t = 1; t <= q; ++t) {
    int a = inf, A = inf, b = inf, B = inf, c = ouf, C = ouf, d = ans, D = ans;
    if (d == -1 && c == -1 && C == -1)
      continue;
    if (c == a)
      quitf (_wa, "Test #%lld, a cannot equal to c!", t);
    if (c < 1 || C < 1)
      quitf (_wa, "Test #%lld, cannot print negative numbers!", t);
    if (!win(c, C, a, A))
      quitf (_wa, "Test #%lld, A cannot beat C!", t);
    if (!win(b, B, c, C))
      quitf (_wa, "Test #%lld, C cannot beat B!", t);
    if (!win(a, A, b, B))
      quitf (_wa, "Test #%lld, B cannot beat A!", t);
  }
  quitf (_ok, "Good job!");
}
```

题目附件中的是本题实际数据的脚造方式，如有更强有意义的数据欢迎在讨论区中提出并 at 出题人。


title: 「PMOI-2」参天大树

description:
b6e0 有一棵参天大树。这棵二叉有根树有无数多个节点。它的根节点的编号为 $1$，对于每一个 $x(x\ge1)$，编号为 $x$ 的节点有编号为 $2x$ 和 $2x+1$ 的子节点。

你需要在编号小于等于 $n$ 的节点中，选出两个**可以相同**的节点，求出所有情况中它们的最近公共祖先的编号的和。也就是求（其中 $\operatorname{LCA}(i,j)$ 表示 $i$ 与 $j$ 的最近公共祖先的编号）：
$$\sum_{i=1}^n\sum_{j=1}^n \operatorname{LCA}(i,j)$$
保证存在一个自然数 $k$，满足 $n=2^k-1$。

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

inputFormat:
**本题有多组询问。**

第一行一个正整数 $t$ 表示询问的次数。

下面 $t$ 行，每行一个自然数 $k$，表示第 $i$ 次询问的 $n=2^k-1$。

outputFormat: 输出 $t$ 行，第 $i$ 行表示第 $i$ 次询问的答案**对 $998244353$ 取模**的值。

hint:
【样例解释】

对于第一次询问，$n=2^2-1=3$，答案为 $1+1+1+1+2+1+1+1+3=12$。

【数据范围】

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

- Subtask1（20pts）：$k\le8$；
- Subtask2（20pts）：$t,k\le300$；
- Subtask3（20pts）：$k\le10^4$；
- Subtask4（40pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le t,k\le10^6$。


title: [2020-2021 集训队作业] Tom & Jerry

background: 自选题 by ix35

description:
给定一张包含 $n$ 个顶点和 $m$ 条边的 **无向连通图**，Tom 和 Jerry 在图上进行了 $q$ 次追逐游戏。

在第 $i$ 次游戏中，Tom 一开始位于顶点 $a_i$，而 Jerry 一开始位于顶点 $b_i$（双方任何时候都知道自己和对方的位置），追逐规则如下：

- Jerry 和 Tom 交替行动，Jerry 先行动。

- Jerry 每次行动可以通过无向图中的 **任意多条边**（可以选择不移动），但是在移动过程中不能经过 Tom 当前所在的结点，否则就会被抓住。

- Tom 每次行动只能通过无向图中的 **至多一条边**（可以选择不移动）。

- 如果 Tom 在一次行动后到达了 Jerry 的位置，那么 Tom 胜利。

Tom 尽量想要胜利，而 Jerry 会尽量阻止 Tom 胜利。

现在你需要对于每一局游戏，求出 Tom 是否一定能在有限次行动内获胜。

inputFormat:
第 $1$ 行：三个整数 $n,m,q$，分别表示无向连通图的点数，边数以及游戏的次数。

接下来 $m$ 行：每行两个整数 $x,y$，描述图中的一条无向边。

接下来 $q$ 行：每行两个整数 $a,b$，表示一局游戏中双方的初始位置。

outputFormat: 共 $q$ 行：对于每局游戏，如果 Tom 可以在有限个回合内获胜则输出 `Yes`，否则输出 `No`。

hint:
【样例解释】

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

第一组询问中，$a_1=6,\ b_1=4$，则 Jerry 先走到 $2$ 处，此后每一回合，若 Tom 行动完后与 Jerry 相邻，Jerry 只需要移动到环 $[1,2,3,4]$ 中与 Tom 不相邻的那个点，可保证 Tom 不胜。

第二组询问中，$a_2=4,\ b_2=5$，无论 Jerry 如何行动，Tom 只需走到 $6$ 处，此后 Jerry 可能在 $\{5,7,8\}$，无论如何 Tom 都可以一步追到。

第三组询问中，$a_3=5,\ b_3=7$，则 Jerry 按照第一组询问中的策略即可使得 Tom 无法获胜。

【数据范围】

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

对于 $100\%$ 的数据，$1\leq n,m,q\leq 10^5$，$1\leq x,y,a,b\leq n$，$a_i\ne b_i$。

保证给出的无向图连通，且不含重边和自环。

$\text{Subtask 1}\ (10\%)$： $n,m,q\leq 10$。

$\text{Subtask 2}\ (16\%)$： $n,m,q\leq 100$。

$\text{Subtask 3}\ (24\%)$： $n,m,q\leq 1000$。

$\text{Subtask 4}\ (16\%)$： $m=n$。

$\text{Subtask 5}\ (34\%)$： 无特殊限制。


title: 「dWoi R2」Change / 改造

background:
入间改造对人类生存繁殖有帮助的工具（~~就是性能工具，具体可以去看看弹丸论破 V3 自由时间与入间美兔的交谈，在这里不方便说吧，毕竟是 青 少 年 编 程 网 站~~）玩腻了，她发现了有一个很 符 合 她 胃 口 的东西，叫做 Galgame，于是她开始打一款叫做 Little Busters 的 Galgame，然后沉迷上了沙耶线最后的场景。

---

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

description:
在经过 $99$ 次的 Replay 后，沙耶终于发现迷宫是一个有向无环图。为了保证最后一次 Replay 的趣味性，时风瞬给沙耶和理树安排了一个小游戏。

这张有向无环图 $G$ 有 $n$ 个点，$m$ 条边，每条边的长度为 $1$。设 $l_i$ 为初始点 $s$ 到第 $i$ 条边所指向的点 $u$ 的最短路，定义第 $i$ 条边的边权为 $p-l_i$。游戏步骤是这样的（所有选择都是按如下顺序进行，并且每个人的选择都是公开的）。

1. 理树站在点 $s$ 上。
2. 时风瞬会随机选取一个点作为 $t$（$t$ 可以等于 $s$）。
3. 如果无法从 $s$ 到达 $t$，游戏直接结束。
3. 沙耶需要选择一条边。
4. 理树需要找到一条从 $s$ 到 $t$ 的路径。
5. 若沙耶选择的边在理树所选择的路径上，则理树就会将这条边的边权的钱给沙耶。

理树希望能少输钱，沙耶希望能多拿钱。若两方都采取最优策略，请问沙耶期望能得到多少钱。

inputFormat:
第一行四个整数 $n,m,s,p$，分别代表有向图点数，边数与理树站在的位置，以及题目中出现的 $p$。

接下来 $m$ 行每行两个整数 $u_i,v_i$ 描述一条边。

outputFormat:
一行一个整数代表答案。

请对 $998244353$ 取模。

hint:
#### 样例 1 解释

比如 $t=6$ 时，沙耶应该选择连接 $5,6$ 的那条边；$t=8$ 时，沙耶仍然应该选择连接 $5,6$ 的那条边；$t=4$ 时，应该选择连接 $1,4$ 的那条边；$t=5$ 时，沙耶无论选择什么边都不会得到钱。

设 $res_u$ 表示 $t=u$ 时沙耶能获得的最大收益，我们有 $res=\{0,9,9,9,0,7,7,7\}$。

#### 样例 2 解释

设 $res_u$ 表示 $t=u$ 时沙耶能获得的最大收益，我们有 $res=\{0,2,2\}$。

---

#### 数据规模与约定

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

- Subtask 1（10 pts）：$n,m \le 5$；
- Subtask 2（20 pts）：$m=n-1$，$u_i<v_i$，$s=1$；
- Subtask 3（30 pts）：$n,m \le 10^3$；
- Subtask 4（40 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,m \le 5 \times 10^6$，$1 \le s \le n$，$1 \le u_i,v_i \le n$，$u_i \ne v_i$，$n\le p \le 10^9$。


title: 「EZEC-14」众数 I

background: pigstd 是一个可爱的男孩子。他在 NOI2022 中的众数一题定义了 $10^6$ 个 ``std::deque`` 并没有 MLE。

description:
给定一个长度为 $n$ 的序列 $a$，我们通过以下方式构造序列 $b$：

- 初始时 $b=a$。
- 依次对 $b$ 进行 $k$ 次操作，每次操作选择任意一个元素并将其**修改**为任意整数。

dXqwq 定义一个序列的**众数**为所有出现次数最大的数。例如 $[1,1,4,5,1,4]$ 的众数为 $1$，而 $[1,14,5,14,19,19,8,10]$ 的众数为 $14,19$。

你需要求出有多少整数可能成为 $b$ 的**众数**。

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

第二行输入 $n$ 个整数 $a_i$。

outputFormat:
输出一个整数，代表可能成为众数的数的数量。

特别地，如果答案为正无穷，输出 ``pigstd``。

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

对于第一组数据，最终 $1,2,3,4,5$ 可能为区间众数。

对于第二组数据，将第一个数换成 $6,7,8,9,\cdots$ 后它们均会成为区间众数，因此答案为正无穷。

对于第三组数据，$1,2,3$ 可能成为区间众数。

**【提示】**

开 $10^6$ 个 ``std::deque`` 在空间限制为 1024MB 时不一定会 MLE。

**【数据范围】**

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

* Subtask 1（20 pts）：$n\leq 5$。
* Subtask 2（20 pts）：$n\leq 10^3$。
* Subtask 3（20 pts）：$k=0$。
* Subtask 4（20 pts）：$k=1$。
* Subtask 5（20 pts）：无特殊限制。

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


title: 「TOCO Round 1」Eternal Star

background:
「诚挚地祈愿」

「在星辰坠落的那一瞬间」

「水中倒映着两个人的身影」

「交相辉映」

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

description:
Kuon 想要一棵结点数量尽可能少的树。

她会给每个结点编号为一个正整数，使得相邻结点编号不同并且所有结点的编号和最小。如果存在很多种方案她会选择任意一种。

请你帮忙构造出一棵树使得它在 Kuon 编号后的最大编号一定不小于 $k$。

inputFormat: 两个整数 $k$ 和 $x$，其中 $k$ 见题目描述，$x$ 表示评分参数。

outputFormat:
第一行一个整数 $n$ 表示你构造的树的大小。

接下来 $n-1$ 行每行两个整数 $u,v$ 表示你构造的树的一条边。


title: 「TOCO Round 1」奇怪的排序

background:
欢喜不问天，风流不问天，温柔不问天，良辰不问天，良缘不问天。

问你不问天。

description:
情人节那天 $\color{orange}\texttt{Biadocy}$ 被虐得好惨，尤其是上流的公爵和小孩说什么《和你在一起的每一天，都叫情人节》。于是他找到了一个机会来报复。

现在有 $n$ 对情人编号为 $1\sim n$ 按任意顺序排成一列，$\color{orange}\texttt{Biadocy}$ 对他们执行了下面这段排序的伪代码。

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

$\color{orange}\texttt{Biadocy}$ 想知道有多少种初始排列满足按照这段伪代码排序后情人们的编号有序。也许这能让他好受一点。

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

接下来 $T$ 行每行两个整数 $n,k$ 表示情人对数和第一次调用伪代码传入的参数。

outputFormat: $T$ 行，每行一个整数，表示答案对 $10^9+7$ 取模的结果。


title: 「MCOI-05」粘液

background:
2077 年 7 月 7 日，MineCraft 20.7.7 发布了。这次更新允许了玩家将红石电路刻进一块电路板中进行运算。

`namespace_std` 作为一只程序猿兼 MC 玩家，他想在新的版本用电路板建造一台简易的粘液块盾构机。

然而，`namespace_std` 由于太久没玩 MC 了，建错了 TNT 复制装置，被炸上了外太空。所以搭建这个粘液块盾构机的任务就交给书虫了。

书虫用他附有耐久 X 的肝写出了这个盾构机的程序。然而，事情并没有这么简单 ...

description:
书虫有一个 $1 \times 1$ 体积的盾构机，和一块 $n \times m$ 个格子的地块，书虫打算用盾构机将这块地块推平。形式化地说，书虫需要让这个盾构机经过每一个格子 **恰好一次**。

这看上去很简单。然而，这个盾构机的程序的实现却有一些故障。当盾构机向同一个方向 **连续** 移动 **达到** $k$ 步时，盾构机就会卡住并不断地向同一个地方投放 TNT。

注意：最开始摆放盾构机**不视为移动**。换言之，盾构机应当移动 $n \times m - 1$ 次。

书虫并不想像可怜的 `namespace_std` 一样被炸上天，因此书虫希望找到一种安排盾构机路线的方案，使得盾构机 **不会** 被卡住。

inputFormat: 输入一行三个整数 $n,m,k$，分别表示地块的长宽，以及盾构机程序中的 $k$ 值。

outputFormat:
如果有合法的方案，输出三行：

- 第一行输出一个字符串 `YES`；
- 第二行输出一个长为 $n \times m - 1$ 的只包含 `L`、`R`、`D`、`U` 的字符串，表示每一步移动的方向；
- 第三行输出两个整数 $x,y$，表示书虫设计的路线起点为 $(x,y)$，即第 $x$ 行第 $y$ 列。当有多种可能的答案的时候，书虫可以输出 **任意一种**。

否则，只需要输出一行 `NO`。

请注意输出量可能较大，**请使用较快的输出方式**。

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

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

- Subtask 0（1 pts）：样例，您可以通过提交结果得知您的答案是否通过了 `Special Judge`。
- Subtask 1（9 pts）：$n,m,k \leq 3$。
- Subtask 2（15 pts）：$n,m,k \leq 10$。
- Subtask 3（5 pts）：$k \geq n$。
- Subtask 4（15 pts）：$n \leq 5$。
- Subtask 5（20 pts）：$k \geq 5$。
- Subtask 6（10 pts）：保证存在合法解。
- Subtask 7（25 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,m,k \le 2000$。


title: 有标号二分图计数

description:
求 $n$ 个点的有标号二分图数目。对每个 $1\le n\le 10^5$ 求出答案。

对 $998244353$ 取模。

inputFormat: 没有输入。

outputFormat: 共 $10^5$ 行，第 $i$ 行是 $i$ 个点的有标号二分图数目对 $998244353$ 取模后的值。


title: 「EZEC-10」序列

background:
> 精准的解析刻画，是应该首先尝试的突破口。

——command_block 《考前小贴士》

description:
请问有多少个不同的序列 $a$，满足：
1. $a$ 的长度为 $n$。
2. $a$ 中的元素均为不大于 $k$ 的非负整数。
3. 满足 $m$ 组形如 $(x_i,y_i,z_i)$ 且 $x_i<y_i$ 的限制，每组限制的意义为 $a_{x_i} \oplus a_{y_i} = z_i$ （$\oplus$ 表示按位异或运算）。

两个序列相同，当且仅当它们所有元素均相同。

请输出答案对 $10^9+7$ []($114514\times(114\times5\times14+((1+145)\times(1+4)+(1\times14+5-1+4)))+(114\times514+(11\times(451+4)+(-1+145+14)))$)取模的结果。

inputFormat:
输入共 $m+1$ 行：
- 第一行三个数，$n,m,k$。
- 接下来 $m$ 行，每行 $3$ 个数，$x_i,y_i,z_i$。

outputFormat: 输出仅一行，表示答案对 $10^9+7$ 取模的结果。


title: [CTSC2002] 颁奖典礼

background:
IOI2002 的颁奖典礼将在 YONG-IN Hall 隆重举行。人们在经历了充满梦幻的世界杯之后变得更加富于情趣。为了使颁奖典礼更具魅力，有人建议在 YONG-IN Hall 中搭建一个 $\text{I}$ 字型的颁奖台，以此代表信息学 Informatics。

考虑到比赛的赞助商们可能要在 YONG-IN Hall 中摆设了许多展示台，他们可能不愿意移动展示台的位置。你作为 IOI2002 的金牌得主自然地成为了他们求助的对象。

description:
YONG-IN Hall 是一个矩形的网格区域。每个赞助商的展示台都占据了若干个单位网格。$\text{I}$ 型颁奖台将正向搭建，且平行于 YONG-IN Hall 的边缘。$\text{I}$ 型颁奖台是由三个矩形相接叠成的，其中上方和下方的矩形的两侧必须都超出中间的矩形，否则将被误解成 $\text{T, L, J}$ 等字母。例如：

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

这是两个合法的 $\text{I}$ 型颁奖台，而以下三种情况均不合法：

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

希望你编程寻找面积最大的 $\text{I}$ 型颁奖台，使其不覆盖任何展示台。

inputFormat:
第一行包含两个正整数 $n,\,m$，分别表示 YONG-IN Hall 的矩形网格区域的行数和列数。

以下 $n$ 行每行包含 $m$ 个数字 $p_{i,\,j}$，每个数字描述一个单位网格，$1$ 表示该单位网格存在展示台，$0$ 表示该单位网格不存在展示台。

outputFormat: 仅包含一个正整数，表示最大的 $\text{I}$ 型颁奖台的面积。如果不存在合法的 $\text{I}$ 型颁奖台，则输出 $0$。

hint:
对于 $100\%$ 的数据，$1 \leq n,\,m \leq 200$，$p_{i,\,j} \in \{0,\,1\}$。

样例解释：

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

可选出的最大 $\text{I}$ 型颁奖台面积为 $15$。


title: [CTSC2002] 月亮森林

background:
一天早晨，一个小女孩在森林里玩耍时看到一颗神奇的种子，光芒四射，还散发着一股淡淡的清香。女孩很喜欢这
颗种子，便把它捧在手里带回了家。

那天晚上，女孩做了一个梦，梦到一个面目慈祥的白胡子老爷爷。老爷爷对她说，她手里的种子来自一棵月亮之树，原本只有在月亮上才能见到它，但是机缘巧合，种子悄悄的落在了地球上，无法再回到月亮上了。

老爷爷发现女孩儿很喜欢这颗种子，就问她是否愿意借助自己的勤劳和智慧，用这颗小小的种子种出一片茂密的月亮森林，让月亮树在地球上有一个温暖的新家。女孩兴奋地点点头，忙问老爷爷具体应该怎么做。

description:
老人解释说，这颗种子非同寻常，种下去的第二天上午就会长成一棵高度为 $1$（一个单位）的小树苗。

月亮树的生命力极强，以后还会每天上午长高一个单位。由于月亮树不同于地球上的生物，女孩必须使用一种特殊的肥料才能对它施肥，而这种肥料老爷爷每天会送给女孩儿一个单位。每天晚上，她必须给一棵树或者下午刚种下去的种子施肥，但不能多施肥，也不能不施肥。被施肥的树或者种子在第二天上午将比一般情况下多长高一个单位，即两个单位。

月亮树在成长的过程中有两个称为 “收获点” 的特殊高度，分别为 $\text{HP1}$ 和 $\text{HP2}$。当月亮之树的高度第一次达到或者超过 $\text{HP1}$ 的那天中午，树上就会结出一个果实。同样，当高度第一次达到或者超过 $\text{HP2}$ 的那天中午，树上也会结出一个果实。

果实里面有一颗种子, 和女孩当初捡到的一模一样。每天下午，女孩都可以选择一些种子种下去，当然也可以不种。当女孩种了恰好 $M$ 棵树，且它们的高度都相同时，这些树才能真正的适应地球的环境，永远的活下去。

醒来后的那天下午，女孩儿就按照老爷爷的吩咐把种子种下去了。她把完成老爷爷交付给她的任务作为一生中最大的心愿，日复一日，年复一年辛勤的劳动着。她每天傍晚一坐在门槛上望着远方，眼前就会浮现出一片美丽而宽广的月亮森林。她坚信自己一定能成功，需要再长的时间也不怕。但是这一天何时才会来到呢？

inputFormat: 三个整数 $\text{HP1,\,HP2},\,M$，代表两个收获点的高度和所需月亮树的棵数。

outputFormat: 仅包含一个整数 $T$，即最少需要的天数。


title: [CTSC2002] 丹奇方块

background: 佳佳最近被一个叫做 “丹奇方块” 的游戏吸引住了，但是却因为游戏太难而迟迟无法通关。

description:
游戏在一个没有边界的棋盘上进行，中心 $(0,\,0)$ 处有一块黑色的障碍物，不远处坐标值为奇数的 $N$ 个不同的格子中各有一个灰色方块。

游戏的任务是把所有灰色方块全部粘起来组成一个给定的形状，如图一所示。该形状可以出现在棋盘上的任何位置，但不能旋转或者对称。图二描述了一个合法的初始状态，其中在坐标 $(-1,\,-1),\,(1,\,-1),\,(1,\,1)$ 处各有一个灰色方块。

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

这个游戏看起来简单，但方块数目多，目标形状又很复杂的时候游戏者往往需要很多步才能完成。佳佳希望找到一个不超过 $2000$ 步的解决方案，你能帮帮他吗？

inputFormat:
第一行包含一个整数 $N$，即方块个数。

第 $2$ 行包含 $N$ 个整数对 $x_i,\,y_i$ 其中第 $i$ 个整数对代表第 $i$ 个方块的初始位置。位置按照从上到下（即 $x$ 递增）从左到右（即 $y$ 递增）的顺序排列。

第 $3$ 行包含 $N$ 个 整数对 $P_{x_i},\, P_{y_i}$，代表目标形状中各小方块的相对位置。目标方块保证是一个连在一起的整体，且数据总是有解的。

outputFormat: 一行，为需要的步数 $S$。


title: 「EZEC-10」多彩的线段

description:
```Muxii```有一个 $[1,n]$ 的数轴，$m$ 种颜色的线段。
```Muxii```规定，对于第 $i$ 种颜色，仅有 $[l_i,r_i]$ 部分的数轴允许覆盖线段，且每条线段的长度不能超过 $k_i$ $(k_i≤10)$。线段可以有任意多条。
现在```Muxii```将会询问你 $q$ 次，每次询问给出两个数字 $a$、$b$，请你回答若要覆盖 $[a,b]$ 部分的数轴最少需要几条线段。
数据保证数轴上不存在不能被任何线段覆盖的位置。

inputFormat:
**本题部分数据点强制在线。**
第一行四个数 $o$、$n$、$m$、$q$，其中当 $o=1$ 时，该数据点强制在线，即每次给出的 $a$、$b$ 异或上次询问的答案的结果为真正的 $a$、$b$，当第一次询问时，可认为上一次询问的答案为 $0$；当 $o=0$ 时，该数据点不强制在线。
接下来 $m$ 行，每行三个数 $l_i$、$r_i$、$k_i$；
再接下来 $q$ 行，每行两个数 $a$、$b$。以上未解释的变量意义皆已在题目描述中给出。

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

hint:
【样例 $1$ 说明】

最少需要 $3$ 条线段。下面给出一种可行的解决方案：
第 $1$ 条线段为 $[1,4]$ ，颜色为 $1$；
第 $2$ 条线段为 $[4,6]$ ，颜色为 $2$；
第 $3$ 条线段为 $[6,7]$ ，颜色为 $2$。

【数据范围与约定】

- Subtask 1（5 points）：$n,m,q≤1000$，不强制在线。
- Subtask 2（20 points）：$n≤2×10^5$。不强制在线。
- Subtask 3（20 points）：$n≤10^7$。不强制在线。
- Subtask 4（10 points）：$m≤1000$。不强制在线。
- Subtask 5（25 points）：无特殊限制，不强制在线。
- Subtask 6（20 points）：无特殊限制，**强制在线**。

对于 $100\%$ 的数据，保证 $1≤n≤10^9$，$1≤m≤2×10^5$，$1≤q≤10^6$，$1≤l_i<r_i≤n$，$1≤k_i≤\min(10,r_i-l_i)$，$1≤a<b≤n$。以上变量皆为整数。


title: [USACO05NOV] Asteroids G

description:
贝茜想在 $N\times N$ 的网格中驾驶她的宇宙飞船。网格中有 $K$ 个小行星。要使驾驶过程愉快，就必须把这些小行星全部消除。

贝茜有一个武器，可以以一个单位代价消除一行或一列的全部小行星。贝茜想问你，要把所有小行星都消除的最小代价是多少。

inputFormat:
第一行两个整数 $N,K$。

接下来 $K$ 行，每行输入 $x_i,y_i$，表示第 $i$ 个小行星在网格的坐标。

outputFormat: 一行一个整数，表示把所有小行星消除的最小代价。

hint:
#### 样例解释：

样例的图为（`X` 为小行星）：

```text
X.X
.X.
.X.
```

贝茜可以分别消除第一行和第二列的小行星。

---

#### 数据范围：

对于 $100\%$ 的数据，$1 \leq N \leq 500$，$1 \leq K \leq N \times N$。


title: [JOI 2021 Final] とてもたのしい家庭菜園 4

description:
给定一个长为 $N$ 的序列 $A_i$，你可以进行若干次操作：

- 选定一个区间 $[L,R]$，让这个区间里的数加 $1$。

设经过这若干次操作后的序列为 $B_i$，那么你需要让 $B_i$ 满足下面这个要求：

- 存在一个整数 $k \in [1,N]$，满足对于子序列 $A_1=\{B_1,B_2,\cdots,B_k\}$ 为严格递增序列，对于子序列 $A_2=\{B_k,B_{k+1},\cdots,B_N\}$ 为严格递减序列。

你想知道最少需要多少次操作才能满足上面这个要求。

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

第二行 $N$ 个整数 $A_i$ 代表序列。

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

hint:
#### 样例 1 解释

- 对 $[2,5]$ 进行操作，序列变为 $\{3,3,3,4,2\}$。
- 对 $[2,3]$ 进行操作，序列变为 $\{3,4,4,4,2\}$。
- 对 $[3,3]$ 进行操作，序列变为 $\{3,4,5,4,2\}$。

#### 样例 2 解释

序列已经满足要求，不需要操作。

#### 样例 3 解释

对区间 $[1,1]$ 或 $[2,2]$ 进行操作都可。

#### 数据规模与约定

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

- Subtask 1（40 pts）：$N \le 2000$。
- Subtask 2（60 pts）：无特殊限制。

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

#### 说明

翻译自 [The 20th Japanese Olympiad in Informatics Final Round A とてもたのしい家庭菜園 4 的英文翻译 Growing Vegetables is Fun 4](https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t1-en.pdf)。


title: [JOI 2021 Final] 雪玉

description:
在一条无限长的数轴上，有 $N$ 个雪球，这 $N$ 个雪球编号为 $1 \sim N$，第 $i$ 个雪球在第 $A_i$ 个点上。刚开始，整条数轴覆盖满了雪，接下来 $Q$ 天将会刮起大风，第 $j$ 天的风力强度为 $W_j$，如果 $W_j$ 为正数，所有雪球都朝右移动 $W_j$ 个单位长度，如果 $W_j$ 为负数，所有雪球都朝左移动 $-W_j$ 个单位长度。

当一个区间 $[a,a+1]$ 被雪覆盖时，雪球滚上去雪球的质量会加一，这一个区间里的雪也会被清空。刚开始每一个雪球的质量均为 $0$，而这 $Q$ 天里也没有再下雪。

你想问这 $Q$ 天结束后每个雪球的质量是怎样的。

inputFormat:
第一行两个整数 $N,Q$ 代表雪球个数和下雪天数。

第二行 $N$ 个整数 $A_i$ 代表这 $N$ 个雪球的初始位置。

接下来 $Q$ 行每行一个整数 $W_j$ 代表每一天的风力强度。

outputFormat: $N$ 行每行一个整数代表这 $Q$ 天结束后每一个雪球的质量。

hint:
#### 样例 1 解释

雪球初始位置为 $-2,3,5,8$，初始质量为 $0,0,0,0$。

- 第一天过后，雪球位置为 $0,5,7,10$，质量为 $2,2,2,2$。
- 第二天过后，雪球位置为 $-4,1,3,6$，质量为 $4,4,2,3$。
- 第三天过后，雪球位置为 $3,8,10,13$，质量为 $5,4,2,6$。

#### 数据规模与约定

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

- Subtask 1（33 pts）：$N,Q \le 2000$。
- Subtask 2（67 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N,Q \le 2 \times 10^5$，$|A_i|,|W_j| \le 10^{12}$，$A_i<A_{i+1}$。

#### 说明

翻译自 [The 20th Japanese Olympiad in Informatics Final Round B 雪玉的英文翻译 Snowball](https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t2-en.pdf)。


title: 简单的排列计数

description:
设 $\text{inv}_{\pi}$ 表示排列 $\pi$ 的逆序对数。如果 $\pi$ 长度为 $n$ 则有

$$\text{inv}_{\pi}=\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}[\pi_i>\pi_j]$$

给定两个正整数 $n,k$，和一个排列 $\pi^\prime$，定义一个长度为 $n$ 的排列 $\pi$ 的权值 $\text{val}_{\pi}$ 为

$$\text{val}_{\pi}=\prod\limits_{i=1}^{n}\prod_{j=i+1}^{n}\pi_i^{[\pi_{i}>\pi_j]}$$

对于 $0\leq m\leq k$ 求

$$\sum\limits_{\pi}[\text{inv}_\pi=m]\text{val}_\pi$$

其中 $\pi$ 是长度为 $n$ 的排列。

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

outputFormat: 一行 $k+1$ 个整数，表示答案对 $998244353$ 取模的值。


title: [JRKSJ R2] Dark Forest

background: **本题为提交答案题。**

description:
给你一个长为 $n$ 的序列 $a$，定义 $1\dots n$ 的排列 $p$ 的权值为

$$\sum_{i=1}^n p_i a_{p_{i-1}} a_{p_i}a_{p_{i+1}}$$

你可以理解为这个排列是一个环，即 $p_{0}=p_n,p_{n+1}=p_1$。

请构造一个权值**尽量大**的 $1\dots n$ 的排列。

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

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

outputFormat: 一行 $n$ 个整数表示排列。

hint:
注意是 `a[p[i-1]] a[p[i+1]]`，数据有一定梯度。

### 数据范围

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

### 样例解释

该排列的权值为 $1\times2\times1\times3+3\times1\times3\times5+5\times3\times5\times4+2\times5\times4\times2+4\times4\times2\times1=463$，可以证明这是最优的排列之一。

### 评分方式

**本题使用 Special Judge**，每个测试点都有 $10$ 个参数 $v_1,v_2,\dots v_{10}$。如果你的输出的权值 $V\ge v_i$，则该测试点您至少会获得 $i$ 分。

特别的，如果您的输出不是一个 $1\dots n$ 的排列，您会在该测试点获得 $0$ 分。

评分参数已经放至附件。


title: [JOI 2021 Final] 集合写真

description:
有 $N$ 个人，这 $N$ 个人编号为 $1 \sim N$，第 $h$ 个人的身高为 $h$。

有 $N$ 个台阶，这 $N$ 个台阶从低到高编号为 $1 \sim N$，第 $i$ 级台阶比第 $i+1$ 个台阶低 $2$ 个单位高度。每个台阶上只能站一个人，第 $H_i$ 个人站在第 $i$ 个台阶上。

你可以进行无数次如下操作：

- 选择 $i \in [1,N-1]$，交换第 $i$ 个台阶上的人和第 $i+1$ 个台阶上的人。

假设第 $i$ 个台阶上站的人的高度为 $a_i$，你要满足：

- 对于任意 $i \in [1,N-1]$，都有 $a_i <a_{i+1}+2$。

求最少的操作次数。

inputFormat:
第一行一个整数 $N$ 代表人数。

第二行 $N$ 个整数 $H_i$ 代表第 $H_i$ 个人站在第 $i$ 个台阶上。

outputFormat: 一行一个整数代表最少的操作次数。

hint:
#### 样例 1 解释

设 $h_i$ 为第 $i$ 个台阶上站的人的身高：

- 交换第 $2$ 个人和第 $3$ 个人，$h_i=\{3,2,5,4,1\}$。
- 交换第 $4$ 个人和第 $5$ 个人，$h_i=\{3,2,5,1,4\}$。
- 交换第 $3$ 个人和第 $4$ 个人，$h_i=\{3,2,1,5,4\}$。

$3$ 步刚好满足要求。

#### 样例 2 解释

已经满足要求，不需要进行任何操作。

#### 数据规模与约定

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

- Subtask 1（5 pts）：$N \le 9$。
- Subtask 2（7 pts）：$N \le 20$。
- Subtask 3（32 pts）：$N \le 200$。
- Subtask 4（20 pts）：$N \le 800$。
- Subtask 5（36 pts）：无特殊限制。

对于 $100\%$ 的数据，$3 \le N \le 5000$，$1 \le H_i \le N$，$H_i$ 互不相等。

#### 说明

翻译自 [The 20th Japanese Olympiad in Informatics Final Round C 集合写真的英文翻译 Group Photo](https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t3-en.pdf)。


title: [COCI2020-2021#5] Šifra

description: 给定一个长度不超过 $100$ 的只包含小写字母和 $0 \sim 9$ 字符的字符串（字符串中的字母可视为分隔符）。求字符串中包含多少个不同的数。

inputFormat: 一行只包含小写字母和 $0 \sim 9$ 字符的字符串，保证每个数最多有 $3$ 位。

outputFormat: 输出字符串中不同数的数量。

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

对于 $50\%$ 的数据，所有出现的数都互不相同。

对于 $100\%$ 的数据，字符串的长度在 $1$ 到 $100$ 之间。

#### 说明

**本题分值按 COCI 原题设置，满分 $50$。**

**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #5](https://hsin.hr/coci/contest5_tasks.pdf)  _T1 Šifra_。**


title: [COCI2020-2021#5] Po

description:
有一个长度为 $n$ 的数组。在初始状态下，所有元素都为 $0$。

每次操作，可以将一个连续的区间 $[l,r]$ 内的所有数加上一个正整数 $x$，但要求任意两个操作区间要么互不相交，要么一个包含另外一个。

请问能将原数组变为给定数组 $a$ 的最少操作次数。

inputFormat:
第一行输入整数 $n$。

第二行输入 $n$ 个非负整数 $a_i$。

outputFormat: 输出所需最少操作次数。

hint:
#### 样例 2 解释

一种最优的方案是：将所有元素都加上 $2$，再将中间三个元素都加上 $1$。

#### 数据规模与约定

对于 $30$ 分的数据，$1 \le n \le 1000$。

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

#### 说明

**本题分值按 COCI 原题设置，满分 $70$。**

**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #5](https://hsin.hr/coci/contest5_tasks.pdf)  _T2 Po_。**


title: [COCI2020-2021#5] Magenta

description:
给定一个包含 $n$ 个结点，$n-1$ 条边的连通图，其中结点编号分别为 $1,2,\cdots,n$。这 $n-1$ 条边被涂成了不同的颜色，其中包含蓝色、红色和洋红。

Paula 和 Marin 的棋子分别从结点 $a$ 和 $b$ 出发。两人轮流行走，Paula 先走。Paula 的棋子只能沿着蓝色或洋红的边行走，而 Marin 的棋子只能沿着红色或洋红的边行走。然而，任何时候都不能行走都对方棋子所在的位置。如果由一方的棋子无法行走，则另一方获胜。

如果 Paula 和 Marin 每次都使用最优的走法，求最终胜利的一方。如果游戏无法决出胜负，则为平局。

inputFormat:
第一行输入整数 $n$，表示结点的数量。

第二行输入整数 $a,b$，表示 Paula 和 Marin 棋子的初始位置。

接下来的 $n-1$ 行，每行输入两个整数 $x,y$ 和一个字符串 $\text{color}$。如果 $\text{color}$ 为 $\texttt{plava}$，则表示连接 $x,y$ 的边的颜色为蓝色；如果为 $\texttt{crvena}$，则表示颜色为红色；如果为 $\texttt{magenta}$ 则为洋红。

outputFormat:
如果 Paula 获胜，则输出 $\texttt{Paula}$。

如果 Marin 获胜，则输出 $\texttt{Marin}$。

如果游戏平局，则输出 $\texttt{Magenta}$。

samples:
5
3 5
1 2 magenta
1 3 magenta
2 4 plava
2 5 crvena

samples:
5
1 4
2 1 plava
1 3 crvena
5 2 plava
4 1 magenta

hint:
#### 样例 1 解释

Paula 的最优走法为前往结点 $2$，此时 Marin 无法行走。

#### 样例 2 解释

Paula 将前往结点 $1$，而 Marin 会前往结点 $2$。Paula 只能前往结点 $3$，此时 Marin 前往结点 $1$。这时 Paula 无法行走，Marin 获胜：

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

#### 数据规模与约定

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

|Subtask|分值|数据范围及约定|
| :----------: | :----------: | :----------: |
|$1$|$30$|$2 \le n \le 100$|
|$2$|$30$|连通图中所有边的颜色都为洋红|
|$3$|$50$|无|

对于 $100\%$ 的数据，$2 \le n \le 10^5$，$1 \le a,b \le n$，$a \neq b$，$1 \le x,y \le n$。

#### 说明

**本题分值按 COCI 原题设置，满分 $110$。**

**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #5](https://hsin.hr/coci/contest5_tasks.pdf)  _T3 Magenta_。**


title: [COCI2020-2021#5] Planine

description:
现有一座上下起伏的山。它可以抽象为一个包含 $n$（$n$ 为奇数）个点 $(x_i,y_i)$ 以及 $(x_1,-\inf)$ 与 $(x_n,-\inf)$ 的多边形。

对于所有满足 $i \neq 1$，$i \neq n$，$i \bmod 2=1$ 的整数 $i$，$(x_i,y_i)$ 都是山谷。

现要放置若干个高度为 $h$ 的点光源，使得所有的山谷都被照亮，即点光源与山谷的连线不经过山的内部。

求所需点光源的最少数量。

inputFormat:
第一行输入整数 $n,h$。

接下来的 $n$ 行，每行输入整数 $x_i,y_i$。

保证 $x_1 \lt x_2 \lt \cdots \lt x_n$ 且 $y_1 \lt y_2,y_2 \gt y_3,y_3 \lt y_4,\cdots,y_{n-1} \gt y_n$。

outputFormat: 输出所需点光源的最少数量。

hint:
#### 样例 1 图解

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

#### 样例 2 图解

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

#### 数据规模与约定

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

|Subtask|分值|数据范围及约定|
| :----------: | :----------: | :----------: |
|$1$|$20$|$y_2=y_4=\cdots=y_{n-1}$|
|$2$|$30$|$3 \le n \lt 2000$|
|$3$|$60$|无|

对于 $100\%$ 的数据，$3 \le n \lt 10^6$，$n \bmod 2=1$，$1 \le h \le 10^6$，$-10^6 \le x_i \le 10^6$，$0 \le y_i \lt h$，$x_1 \lt x_2 \lt \cdots \lt x_n$，$y_1 \lt y_2,y_2 \gt y_3,y_3 \lt y_4,\cdots,y_{n-1} \gt y_n$。

#### 说明

**本题分值按 COCI 原题设置，满分 $110$。**

**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #5](https://hsin.hr/coci/contest5_tasks.pdf)  _T4 Planine_。**


title: [COCI2020-2021#5] Sjeckanje

description:
给定一个包含 $n$ 个整数的数组 $a$。接着进行 $q$ 次修改，每次给定整数 $l,r,x$。表示将 $[l,r]$ 内的所有元素加上 $x$。

规定一个区间的权值为**该区间的最大值减去最小值**。现要将 $a$ 数组分为若干个连续的区间。规定一个已被分为若干个区间的数组的权值为**该数组所有区间的权值之和**。求数组 $a$ 在**每次修改**后的所有分法中，数组权值的最大值。

inputFormat:
第一行输入整数 $n,q$，分别表示数组的长度和修改的次数。

第二行输入 $n$ 个整数 $a_i$。

接下来的 $q$ 行，每行输入整数 $l,r,x$，表示修改的信息。

outputFormat: 输出 $q$ 行，其中第 $i$ 行输出数组 $a$ 在第 $i$ 次修改后的所有分法中，数组权值的最大值。


title: [JOI 2021 Final] ロボット

description:
给定一个 $N$ 点无向图，这 $N$ 个点编号为 $1 \sim N$，由 $M$ 条边连接，这 $M$ 条边编号为 $1 \sim M$，分别连接点 $A_i$ 与点 $B_i$。这 $M$ 条边染上了颜色，第 $i$ 条边的颜色为 $C_i$，保证 $C_i \in [1,M]$ 但不保证 $C_i$ 互不相等。

你很智能，如果我说一种颜色 $L$，满足下面这些要求的话：

- 存在一条边的颜色为 $L$ 且一个端点为你现在在的点。
- 不存在大于等于两条边满足颜色为 $L$ 且一个端点为你现在在的点。

你就会移动到这条边走向对面的端点，否则你就会原地不动。

你现在在点 $1$ 处，我要你移动到点 $N$ 处，我可以告诉你一些颜色你按照这些颜色走。但这个图有可能不满足能从 $1$ 走向 $N$ 这个条件，因此我要改变一些边的颜色。改变第 $i$ 条边的颜色使其变为另一个在区间 $[1,M]$ 里的数需要的代价为 $P_i$，我想问，至少需要多少代价才能让你成功移动到点 $N$？

inputFormat:
第一行两个整数 $N,M$ 代表无向图点数和边数。

接下来 $M$ 行每行四个整数 $A_i,B_i,C_i,P_i$ 描述一条边。

outputFormat: 一行一个整数代表最小代价，如果无法到达输出 $-1$。

hint:
#### 样例 1 解释

我可以进行如下操作：

- 将第 $4$ 条边的颜色改为 $4$，代价 $1$。
- 将第 $6$ 条边的颜色改为 $2$，代价 $2$。

总代价 $3$，然后我如下使唤你：

- 我说“颜色 $2$！”你从点 $1$ 移动到点 $2$。
- 我说“颜色 $4$！”你从点 $2$ 移动到点 $4$。

#### 样例 2 解释

很遗憾，即使如此智能的你也到达不了第 $N$ 个点。

#### 数据规模与约定

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

- Subtask 1（34 pts）：$N \le 1000$，$M \le 2000$。
- Subtask 2（24 pts）：$P_i=1$。
- Subtask 3（42 pts）：无特殊限制。

对于 $100\%$ 的数据，$2 \le N \le 10^5$，$1 \le M \le 2 \times 10^5$，$1 \le A_i<B_i \le N$，$1 \le C_i \le M$，$1 \le P_i \le 10^9$，保证图无重边。

#### 说明

翻译自 [The 20th Japanese Olympiad in Informatics Final Round D ロボット的英文翻译 Robot](https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t4-en.pdf)。


title: [JOI 2021 Final] ダンジョン 3

description:
有一栋层数为 $N+1$ 层的楼，这 $N+1$ 层编号为 $1 \sim N+1$。有 $M$ 个人，这 $M$ 个人编号为 $1 \sim M$。从第 $i$ 层移动到第 $i+1$ 层需要 $A_i$ 的能量值，并且你只能从第 $i$ 层移动到第 $i+1$ 层，不能反过来。

第 $1$ 层到第 $N$ 层都有一个商铺，第 $i$ 层的商铺可以从 $B_i$ 元使自己的能量加 $1$，可以多次使用商铺但是不能使得能量多于能量上限，其中第 $j$ 个玩家的能量上限为 $U_j$，每个人的初始能量均为 $0$。

第 $j$ 个人最开始在第 $S_j$ 层，他们要到达第 $T_j$ 层。

请回答每个人达到他们的目的地最少需要多少金币，或者指出无解。

inputFormat:
第一行两个整数 $N,M$ 代表楼的层数和人数。

第二行 $N$ 个整数 $A_i$ 代表移动需要的能量值。

第三行 $N$ 个整数 $B_i$ 代表每一层的商铺购买能量需要的金币数。

接下来 $M$ 行每行三个整数 $S_j,T_j,U_j$ 描述一个人。

outputFormat:
$M$ 行每行一个整数代表第 $j$ 个人要到第 $T_j$ 层至少需要多少金币。

如果不能移动到第 $T_j$ 层，输出 $-1$。

hint:
#### 样例 1 解释

第 $1$ 个人无法到达第 $3$ 层。

第 $2$ 个人可以用如下方法到达第 $6$ 层：

- 第 $1$ 层用 $8$ 个金币让自己的能量值变为 $4$。
- 移动到第 $2$ 层能量变为 $1$。
- 第 $2$ 层用 $15$ 个金币让自己的能量值变为 $4$。
- 移动到第 $3$ 层能量变为 $0$。
- 第 $3$ 层用 $4$ 个金币让自己的能量值变为 $4$。
- 移动到第 $4$ 层能量为 $3$。
- 移动到第 $5$ 层能量为 $2$。
- 第 $5$ 层用 $2$ 个金币让自己的能量值变为 $4$。
- 移动到第 $6$ 层。

一共需要 $29$ 个金币。

#### 数据规模与约定

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

- Subtask 1（11 pts）：$N,M \le 3000$。
- Subtask 2（14 pts）：$U_j$ 互相相等。
- Subtask 3（31 pts）：$T_j=N+1$。
- Subtask 4（44 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N,M,A_i,B_i \le 2 \times 10^5$，$1 \le S_j<T_j \le N+1$，$1 \le U_j \le 10^9$。

#### 说明

翻译自 [The 20th Japanese Olympiad in Informatics Final Round E ダンジョン 3 的英文翻译 Dungeon 3](https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t5-en.pdf)。


title: 「EZEC-8」猜树

background: 这是一道交互题。

description:
有一棵以 $1$ 为根的 $n$ 个点的有根树，您需要通过若干次询问得到这棵树的结构。

您可以使用两种询问：

1. `? 1 u v` 通过这种询问，您可以获得 $u$ 和 $v$ 之间的距离。
2. `? 2 u` 通过这种询问，您可以获得 $u$ 子树的大小和 $u$ 子树中的所有节点。

请通过使交互库输出不超过 $10^5$ 个数，得到这棵树的结构。

### 交互方式

输入树的大小 $n$ 以开始交互。

交互过程中，您可以进行题目描述中的两种询问。

对于第一种询问，交互库将会返回一个非负整数，表示 $u$ 节点和 $v$ 节点间的距离。

对于第二种询问，交互库将会先返回一个正整数 $num$，表示 $u$ 子树的大小。接下来会在同一行中返回 $num$ 个正整数，表示 $u$ 子树中的所有节点（节点顺序会被打乱）。

在您确定答案后，请以 `! fa[2] fa[3] ... fa[n]` 的形式输出一行，停止交互。其中 $fa[i]$ 表示这棵树中 $i$ 号节点的父节点。

在您输出一行后，请清空缓冲区：

- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。
- 在 Pascal 中，使用 `flush(output)`。
- 在 Python 中，使用 `stdout.flush()`。
- 其它语言请自行查阅文档。

inputFormat: 见「交互方式」。

outputFormat: 见「交互方式」。

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

-  Subtask 1（5 points）：$n \leq 5$。
-  Subtask 2（15 points）：$n \leq 100$。
-  Subtask 3（20 points）：$n \leq 500$。
-  Subtask 4（15 points）：树是一条链。
-  Subtask 5（15 points）：树是一棵完全二叉树。
-  Subtask 6（30 points）：无特殊限制。

对于 $100\%$ 的数据：$2 \leq n \leq 2000$，$1\le u,v \le n$。

**注意：询问不合法或交互库输出数超过 $10^5$ 后继续询问可能导致 TLE。**


title: 「PMOI-3」公平正义

background: > 公平正义，需要牺牲。——《唐人街探案 3》

description:
现在有 $n$ 个人，lhm 有一个质量为 $1$ 的蛋糕。所有人都想吃到 lhm 的蛋糕。lhm 为了维持公平正义，他需要用最小的刀数将蛋糕分成相等的 $n$ 份（一份中可以包含多块）。

把蛋糕看作一个圆，注意：每次切蛋糕时只能沿着直径切下。

最终每人得到的蛋糕块数可以不同，但必须保证每人得到的质量为 $\frac1n$。

现在你需要求出 lhm 切割的最小刀数。

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

输入数据共 $t+1$ 行。

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

接下来 $t$ 行，每行一个整数 $n$，表示人数。

outputFormat: 输出数据共 $t$ 行，每行一个正整数，表示答案。

hint:
【样例解释】

当 $n=2$ 时，我们直接沿直径切下，从而得到了两个质量均为 $\frac 1 2$ 的蛋糕块，分别将它们分给两个人即可。

当 $n=3$ 时，我们可以先后沿两条夹角为 $60 \degree$ 的直径切下，从而得到了质量为 $\frac 1 6$ 的两个蛋糕块 $a,b$ 和质量为 $\frac 1 3$ 的两个蛋糕块 $c,d$。我们把 $a,b$ 分给第一个人，$c,d$ 分别给第二个人和第三个人，就可以做到公平正义。

【数据范围】

对于 $20\%$ 的数据满足，$1 \le n \le 10$。

对于另 $20\%$ 的数据满足，$t=1$。

对于 $100\%$ 的数据满足，$1 \le t \le 10^3$，$1 \le n \le 10^{9}$。


title: [Kubic] Permutation

background: 建议先看 E 题题目背景。

description:
对于一个 $1\sim n$ 的排列 $p$，定义 $G_p$ 为使用以下方法构造出来的**无向图**：
- 对于每一个 $i\in (1,n]$，找到最大的 $j\in [1,i)$ 满足 $p_i>p_j$，然后连一条 $i,j$ 之间的边，如果不存在这样的 $j$ 则不连。

给定一棵有 $n$ 个节点的树 $T$。

把 $p$ 称为**好排列**当且仅当 $G_p$ 与 $T$ 同构。

如果存在**好排列**，输出其中**字典序最大**的一个。否则输出 $-1$。

无向图 $G_1,G_2$ 同构当且仅当存在一个 $1\sim n$ 的排列 $q$，满足 $\forall (u,v)\in G_1,(q_u,q_v)\in G_2,\forall (u,v)\notin G_1,(q_u,q_v)\notin G_2$。

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

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

outputFormat: 共一行，$n$ 个整数，表示答案；或一个数 $-1$，表示无解。

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

||分值|$n$|特殊性质|
|:-:|:-:|:-:|:-:|
|$\operatorname{Subtask}1$|$15$|$\le 8$|无|
|$\operatorname{Subtask}2$|$5$|无特殊限制|树退化为一条链|
|$\operatorname{Subtask}3$|$15$|无特殊限制|度数 $\ge 3$ 的节点个数 $\le 1$|
|$\operatorname{Subtask}4$|$20$|$\le 100$|无|
|$\operatorname{Subtask}5$|$20$|$\le 10^3$|无|
|$\operatorname{Subtask}6$|$25$|无特殊限制|无|

**说明：样例解释中的节点编号是 $p$ 中的下标。**

### 样例解释 1

$G_p$ 的形态如下：

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

可以证明没有更优的方案。

### 样例解释 2

$G_p$ 的形态如下：

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

可以证明没有更优的方案。


title: 「RdOI R3 附加」ACP-I

background:
**注意：这不是一道模拟题，请先完整地读完一遍题面后再开始做题。**

---

### 排行榜

| task | 最短行数 | 达成者      |
| ---- | -------- | ----------- |
| 1    | 5        | std         |
| 2    | 191     | \_\_Ultimium\_\_      |
| 3    | 845      | dead_X      |
| 4    | 24       | 囧仙        |
| 5    | 77       | dqstz  |
| 6    | 15078    | 寻逍遥2006       |
| 7    | 211      | liqingyang        |
| 8    | 6796     | liqingyang |

如有你的解法行数**严格小于**榜中行数，请联系 @[yzy1](/user/207996) 把你的成绩放到排行榜上。

---

题目 ACP 有两层意思：**A**ncient **C**omputer **P**rogram 和 **A**nother **C**onstruct **P**roblem。

在 1951 年，第 -32 届全国青少年信息学奥林匹克冬令营前夕，小 A 借助时空传输接口（**T**ime **T**ransport **I**nterface）连接了一台 2015 年的计算机，获取到了第 32 届冬令营的题目来练习。

他打开了第三题「未来程序」这道题目：

> 本题是一道提交答案题，一共 10 个测试点。
> 对于每个测试点，你会得到一段程序的源代码和这段程序的输入。你要运行这个程序，并保存这个程序的输出。
> 遗憾的是这些程序都效率极其低下，无法在比赛的 5 个小时内得到输出。

小 A 想了一下，决定用 1951 年的计算机来试着运行这个题目。但是因为 1951 年的电脑存储空间过小，导致他无法传输题目附件和数据，请你帮助小 A 写 std 造数据。

description:
**这是一道提交答案题。**

小 A 的古董计算机使用两个 $64$ 位无符号整数的栈 $S_0$ 和 $S_1$ 来存储数据。每个栈中初始存储着 $10^{10^{10}}$ 个 $0$。

为了表述方便，下文中记「$T_x$」表示栈 $S_x$ 的栈顶元素。记符号 「$\And$」「$\mid$」「$\oplus$」分别为按位与、按位或、按位异或运算。

这台计算机支持 $8$ 种汇编指令，若没有特殊说明，以下指令的参数均为整数。

| 名称                 | 参数                     | 说明                                                         | 伪代码                                                       |
| -------------------- | ------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ |
| $\textbf{and}\ i$ | $i \in [0,1]$            | 令 $T_i$ 为 $T_i$ 与另一个栈的栈顶数字按位与的结果。         | $T_i \gets T_i \operatorname{\And} T_{i \oplus 1}$           |
| $\textbf{or}\ i$  | $i \in [0,1]$            | 令 $T_i$ 为 $T_i$ 与另一个栈的栈顶数字按位或的结果。         | $T_i \gets T_i \mid T_{i \oplus 1}$                          |
| $\textbf{xor}\ i$    | $i \in [0,1]$            | 令 $T_i$ 为 $T_i$ 与另一个栈的栈顶数字按位异或的结果。       | $T_i \gets T_i \oplus T_{i \oplus 1}$                        |
| $\textbf{lsh}\ i\ j$ | $i \in [0,1],j\in[0,64]$ | 令 $T_i$ 为 $T_i$ 左移 $j$ 位的结果，自然溢出。   | $T_i \gets T_i \times 2^j \bmod 2^{64}$                      |
| $\textbf{rsh}\ i\ j$ | $i \in [0,1],j\in[0,64]$ | 令 $T_i$ 为 $T_i$ 右移 $j$ 位的结果，自然溢出。   | $T_i \gets \lfloor \dfrac{T_i}{2^j} \rfloor$                 |
| $\textbf{not}\ i$    | $i\in[0,1]$              | 令 $T_i$ 为 $T_i$ 按位取反的结果。                           | $T_i \gets (2^{64}-1)-T_i$                            |
| $\textbf{pop}\ i$    | $i\in[0,1]$              | 将栈 $S_i$ 的栈顶元素出栈。                                  | $\text{Remove top element of }S_i$                           |
| $\textbf{mov}\ i$    | $i\in[0,1]$              | 将 $T_i$ 出 $S_i$ 栈，然后将其入另一个栈。即移动 $T_i$ 至 $S_{i \oplus 1}$。 | $\text{Push}\ T_i\text{ to }S_{i\oplus 1};\ \textbf{pop}\ i$ |

你需要使用这些汇编指令实现若干计算任务，每个测试点对应一个单独的计算任务。下文中「输入 $a_1, a_2, \cdots$」表示将 $a_1,a_2,\cdots$ 这几个整数**依次**压入 $S_0$ 栈，而两栈栈底的 $0$ 不做变动。**若无特殊说明，输入的数均为 $\mathbf{[0,2^{64}-1]}$ 范围内的整数。**「输出 $x_1, x_2, \cdots$」表示指令运行结束后会从 $S_1$ 中**依次**取出若干个整数作为 $x_1,x_2,\cdots$ 来检验结果是否正确。除此之外，对于 $S_0$ 栈中所有的数和 $S_1$ 栈中**没有**被取出的数在指令运行结束后可以为任意值。

1. 输入 $a, b$，输出 $b,a$。即将两数交换。
1. 输入 $a,b$，输出 $(a-b+2^{64}) \bmod 2^{64}$。即求两数之差，自然溢出。
1. 输入 $a_1, a_2,\cdots,a_9;a_i\in[48,57]$，即 $a_i\in[\mathtt{'0'}, \mathtt{'9'}]$。将 $a_1\sim a_9$ 视为一个 ASCII 编码下的长度为 $9$ 的字符串，你需要将这个字符串**前后翻转后**转化为一个对应的十进制整数并输出。即实现一个快读。特别的，字符串中可能会有前导零。
1. 输入 $a$，输出 $(\operatorname{popcnt}a) \bmod 2$。其中 $\operatorname{popcnt} x$ 代表 $x$ 的二进制表示法中 $1$ 的个数。
1. 输入 $a,b$，输出 $\min\{a,b\}$。
1. 输入 $a,b,p$，满足 $p$ 为 $2$ 的非负整数次幂或零。输出 $(a\times b) \bmod p$。特别地，当 $p=0$ 时输出 $0$。
1. 输入 $a$，满足 $a$ 和答案都是 $2$ 的非负整数次幂或零，输出 $\sqrt a$。
1. 输入 $a,b;1\le a,b \le 63$，输出 $\gcd(a,b)$，即 $a,b$ 的最大公因数。

inputFormat:
由于出题人不想把这道题出成一道大模拟，所以附件中提供了汇编模拟部分。

在下发文件下有 `checker.cpp` 和 `1.ans ~ 8.ans`。其中 `checker.cpp` 给出了几种汇编指令的简单实现。你可以使用 `checker.cpp` 测试你的程序。使用 `g++ checker.cpp -o checker -std=c++11` 将 `checker.cpp` 编译为可执行文件后运行 `checker *.in *.out *.ans`，`checker` 就会给出你的输出结果和该测试点的得分。其中 `*.in` 中为提供给指令的输入数据，每行一个，以 EOF 结束；`*.out` 中存放你的指令；`*.ans` 指下发文件中的 `.ans` 文件。

**注意：此 checker 仅作示例使用，不具备验证正确性功能。**

outputFormat: 请将每个任务对应的指令写入 `1.out ~ 8.out`，并打包成 zip 后提交。

samples: 输入 a，b。输出 a 按位异或 b 的结果。

samples: 没有输入，输出数字 6。

hint:
### 样例说明

上述「样例组 $1\sim 8$」代表 $1\sim8$ 子任务的样例输入输出。「样例组 $9\sim10$」为示例问题的一种最短的程序实现。

---

### 评分方法

下面用 `*` 代表测试点编号。如果你提交的指令（`*.out`）没有正确完成计算得零分，否则设你使用的指令个数为 $cnt$，若 `*.ans` 中有 $x$ 个 $\ge cnt$ 的数，你该测试点得 $x$ 分。

---

### 注意

虽然我们允许你提交最多 $999999$ 行的指令，但是由于洛谷对于 checker 的运行时间有限制，你的指令长度被强行加上了一个奇怪的上限：约是 $2\times 10^5$，超过这个长度的指令可能会因为 checker 超时而导致 UKE。

由于洛谷提交答案题的特性，如果你不会做一些 task，请在压缩包内放一个空的 `*.out` 文件占位，其中 `*` 代表 task 编号。否则你的整道题可能会出现答案错位（比如 `2.out` 交到了 $1$ 号测试点）的情况，导致后面的测试点变成零分。


title: [JRKSJ R2] 01 序列

background: $\text{upd2021.8.16}$：增加两组 hack 数据，并缩小时限至 1.2s。

description:
给你一个长度为 $n$ 的 $01$ 序列 $a$，$m$ 次询问，支持 $2$ 种询问：

- `1 l r` 表示询问 $l$ 到 $r$ 区间的最长不下降子序列的长度。
- `2 l r` 表示询问 $l$ 到 $r$ 区间的最长上升子序列的长度。

inputFormat:
输入 $m+2$ 行。\
第 $1$ 行两个正整数 $n,m$。\
第 $2$ 行 $n$ 个数字 $0$ 或 $1$ 代表序列 $a$。\
接下来 $m$ 行每行三个正整数表示一次询问，格式如上。

outputFormat:
输出 $m$ 行。\
对于每一次询问求出答案并输出。

hint:
本题采用捆绑测试。

| $\text{Subtask}$ | $n\le$ | $m\le$ | 特殊性质 | 分值 |
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
| $\text{1}$ | $10^6$ | $10^6$ | 所有 $a_i$ 均相等 | $5$ |
| $\text{2}$ | $10^3$ | $10^3$ | 无 | $10$ |
| $\text{3}$ | $10^4$ | $10^4$ | 无 | $15$ |
| $\text{4}$ | $10^5$ | $10^5$ | 无 | $30$ |
| $\text{5}$ | $10^6$ | $5\times10^6$ | 无 | $40$ |
| $\text{6}$ | $10^6$ | $5\times10^6$ | hack 数据 | $0$ |

对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le m\le 5\times10^6$，$0\le a_i\le 1$。
****
本题输入输出量极大，这里给出出题人使用的快读快写。（当然，使用您自己编写的大概率也能通过）
```cpp
namespace IO{//by cyffff
	int len=0;
	char ibuf[(1<<20)+1],*iS,*iT,out[(1<<26)+1];
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
	#define reg register
	inline int read(){
		reg char ch=gh();
		reg int x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline void putc(char ch){
		out[len++]=ch;
	}
	template<class T>
	inline void write(T x){
		if(x<0)putc('-'),x=-x;
		if(x>9)write(x/10);
		out[len++]=x%10+48;
	}
	inline void flush(){
		fwrite(out,1,len,stdout);
		len=0;
	}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::putc;
```
使用这种快读快写读入一个数 $x$ 时请使用语句 `x=read();`，输出时使用语句 `write(x);`。注意，换行时需使用语句 `putc('\n');`，程序执行结束时使用语句 `flush();`。

在使用此快读时请加上 `#include<bits/stdc++.h>`。

如果本地无法输入，可以尝试使用 [这里的快读快写](https://www.luogu.com.cn/paste/6za5gs1z)。

若仍看不懂，请在赛时答疑帖回复/私信出题人。

由于出题人只会 `C++`，本处无法给出其他语言的快读快写，深感歉意。
****
#### 样例解释:
对于第一个询问，满足的序列有：$\{0,1,1,1,1\},\{0,0,0,0,1\}$。\
对于第二个询问，满足的序列有：$\{0,1\}$。\
对于第三个询问，满足的序列有：$\{0,0\},\{0,1\},\{1,1\}$。\
对于第四个询问，满足的序列有：$\{0\},\{1\}$。

本题时限、空限保证为出题人所用的两倍以上。\
如果您仍认为卡常，则请私信出题人或者发帖并 @ 出题人。


title: [COCI2019-2020#4] Nivelle

description:
Bojan 看到了 $n$ 个可爱的能吃的毛绒玩具摆在商店的货架上。从序号 $1$ 摆到 $n$。每个毛绒玩具都有 $26$ 中不同的颜色。每种颜色用英文字母 $a...z$ 表示。
对于任何一套玩具，我们都可以把它的颜色定义为一套玩具中不同颜色的玩具数量除以一套玩具的总数。
Bojan 想吃这些玩具，但 Bojan 不喜欢有太多的颜色，所以请你帮助 Bojan 找到一个连续的子序列的玩具，使其色彩数尽可能的少。

inputFormat:
第一行包含一个正整数 $n$，表示玩具的个数。
第二行包含长度为 $n$ 的字符串 $S$，第 $i$ 个字符表示架子上的第 $i$ 个玩具的颜色。

outputFormat:
输出只有一行，包含两个整数 $l,r$，表示所求连续子序列的左端点及右端点。
如果存在多个具有相同颜色数量且颜色最少的连续子序列，则输出任意一个子序列。

hint:
**数据范围及约定**

**本题采用多测试点捆绑测试，共有 5 个子任务。**

- Subtask 1（7 points）：$1 \leq n \leq 100$；
- Subtask 2（17 points）：$1 \leq n \leq 2 \times 10^3$；
- Subtask 3（13 points）：字符串 $S$ 中只有两个字符 $a,b$（你可以理解为所有玩具中只有两种颜色）。
- Subtask 4（25 points）：字符串 $S$ 中只有五个字符 $a,b,c,d,e$（你可以理解为所有玩具中只有五种颜色）。
- Subtask 5（48 points）：无特别限制。

对于全部的测试点，保证 $1 \leq n \leq 10^5，1 \leq l \leq r \leq n$。

【提示与帮助】

**题目译自 [COCI 2019/2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #4](https://hsin.hr/coci/archive/2019_2020/contest4_tasks.pdf) T5 Nivelle**

在 COCI 中，本题分值为 $110$ 分。


title: 双重素数（2021 CoE-II A）

description: 素数（质数）是指在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数。定义**双重素数**为这样的素数：它的各位数字之和也是一个素数。给定一个闭区间，试确定在该区间内双重素数的个数。

inputFormat:
**输入包含多组测试数据。**

输入第一行包含一个整数 $T$，表示测试数据的组数。接下来每行一组测试数据，每组测试数据包含以空格分隔的两个整数 $L$ 和 $R$。

outputFormat: 每组测试数据输出一行，包含一个整数，表示在闭区间 $[L,\ R]$ 内双重素数的个数。

hint:
**样例说明**

从 $1$ 到 $15$ 共有 $6$ 个素数：$2$，$3$，$5$，$7$，$11$，$13$。前五个素数各自的数字之和也是素数，因此都是双重素数。素数 $13$ 的各位数字之和为 $4$，不是素数，故 $13$ 不是双重素数。

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

**数据范围**

- Subtask $1$ ：$1 \le L \le R \le 10^2$，$10$ 分。
- Subtask $2$ ：$1 \le L \le R \le 10^4$，$20$ 分。
- Subtask $3$ ：$1 \le L \le R \le 10^6$，$60$ 分。
- Subtask $4$ ：$1 \le L \le R \le 10^8$，$10$ 分。

对于 $100\%$ 的数据，$1 \le T \le 100$。

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

**提示（数据已经加强）**

最后一个子任务要求你的程序必须具有较高的空间使用效率和时间效率，否则容易超出内存限制或时间限制。


title: 「EZEC-7」猜排列

background: Update：数据已经经过加强。

description:
Alice 手上有一个长度为 $n$ 的排列 $a$，排列中的数为 $0,1,2,\cdots,n-1$。

Bob 闲来无事，想去猜它。但 Alice 不想让他轻易猜到。

于是他抛给了 Bob 一些条件，让他来猜这个排列。

我们定义 $f(l,r)=\text{mex}\{a_l,a_{l+1},\cdots,a_r\}$，其中 $\text{mex}$ 函数代表一个可重集中**没有出现过**的最小**非负整数**。

而 Alice 说出的条件包含 $n$ 个数，第 $i$ 个数代表着满足 $1 \leq l \leq r \leq n$ 且 $f(l,r)=i-1$ 的二元组 $(l,r)$ 的个数。

Bob 一下就知道这并不能确认整个排列了，因此他想知道符合已有条件的排列数量。

inputFormat:
第一行，一个正整数 $n$，代表 Alice 手中排列的长度。

第二行，$n$ 个非负整数，第 $i$ 个数 $c_i$ 代表着满足 $l \leq r $ 且 $f(l,r)=i-1$ 的二元组 $(l,r)$ 的个数。

outputFormat: 输出符合已有条件的排列数量对 $998244353$ 取模的值。

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

第一个样例中存在两个满足条件的排列，分别为：

$\{1,0,2,3\}$ 和 $\{3,2,0,1\}$ 。

第二个样例可以通过枚举发现没有符合题意的解。

**【数据范围】**

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

* Subtask 1（4 points）：$n\leq 8$。
* Subtask 2（8 points）：$n\leq 20$。
* Subtask 3（16 points）：$n\leq 100$。
* Subtask 4（32 points）：$n\leq 2\times 10^3$。
* Subtask 5（20 points）：$n\leq 10^5$。
* Subtask 6（20 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le5\times10^5 $，$c_i \ge 0$，保证 $\sum^{n}_{i=1}c_i=\frac{n(n+1)}{2}-1$。


title: 「EZEC-7」线段树

background: Bob 喜欢线段树。

description:
如果你不知道线段树，可以看 提示说明 中的定义。

Bob 得到了一个长度为 $n$ 的序列 $a_{1,2,\cdots,n}$，初始全为 $0$。

接着 Bob 进行了 $m$ 次区间加操作，每次操作会等概率地从 $[1,n]$ 的所有 $\dfrac{n(n+1)}{2}$ 个子区间中随机选择一个进行操作，每次加的数是 $[-1,V]$ 之间等概率随机的整数。

$m$ 次操作完之后要求出每一个位置的值。

由于 Bob 喜欢线段树，他熟练地打出一颗 $[1,n]$ 上的线段树来解决这个问题，使用懒惰标记来解决区间加的问题。

打代码的过程中 Bob 忽然想到了两个减小 $\mathrm{Pushdown}$（下传懒惰标记）次数的方法：

+ 修改的时候不 $\mathrm{Pushdown}$，最后一次性 $\mathrm{Pushdown}$（即 $\mathrm{Pushall}$ 函数）。

+ $\mathrm{Pushall}$ 到一个节点的时候，如果这个节点的懒惰标记为 $0$ 那么不 $\mathrm{Pushdown}$。

现在 Bob 想知道期望 $\mathrm{Pushdown}$ 次数，可是他不会算，于是来问你。

下面是 Bob 写的线段树伪代码（其中 `tag` 数组为懒惰标记）：

$
\displaystyle
\begin{array}{l}
\mathrm{pushdown\_counter}\leftarrow 0\\
\\
\textbf{function }\mathrm{Update(Node},l,r,ql,qr,Delta)\\
\qquad \textbf{if } [l,r]\cap [ql,qr] = \varnothing \textbf{ then}\\
\qquad \qquad \textbf{return}\\
\qquad \textbf{end if}\\
\qquad \textbf{if }[l,r] \subseteq [ql,qr] \textbf{ then}\\
\qquad \qquad \mathrm{tag[Node]\leftarrow tag[Node]}+Delta\\
\qquad \qquad \textbf{return}\\
\qquad \textbf{end if}\\
\qquad mid\leftarrow \lfloor\dfrac{l+r}{2}\rfloor\\
\qquad \mathrm{Update(LeftChild},l,mid,ql,qr,Delta)\\
\qquad \mathrm{Update(RightChild},mid+1,r,ql,qr,Delta)\\
\textbf{end function}\\
\\
\textbf{function }\mathrm{Pushdown(Node)} \\
\qquad \mathrm{tag[LeftChild]\leftarrow tag[LeftChild]+tag[Node]}\\
\qquad \mathrm{tag[RightChild]\leftarrow tag[RightChild]+tag[Node]}\\
\qquad \mathrm{pushdown\_counter}\leftarrow \mathrm{pushdown\_counter}+1\\
\textbf{end function}\\
\\
\textbf{function }\mathrm{Pushall(Node},l,r)\\
\qquad \textbf{if } \mathrm{Node\ is\ Leaf} \textbf{ then}\\
\qquad \qquad \textbf{return}\\
\qquad \textbf{end if}\\
\qquad \textbf{if } \mathrm{tag[Node] \not= 0} \textbf{ then}\\
\qquad \qquad \mathrm{Pushdown(Node)}\\
\qquad \textbf{end if}\\
\qquad mid\leftarrow \lfloor\dfrac{l+r}{2}\rfloor\\
\qquad \mathrm{Pushall(LeftChild},l,mid)\\
\qquad \mathrm{Pushall(RightChild},mid+1,r)\\
\textbf{end function}
\end{array}
$

换句话说，你要帮 Bob 求出 `pushdown_counter` 的期望值。

答案对 $998244353$ 取模。

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

outputFormat: 一个整数，期望 $\mathrm{Pushdown}$ 次数对 $998244353$ 取模的结果。


title: 狩猎（2021 CoE-II D）

description:
母狮 $\text{Dina}$ 的领地里有固定的 $n$ 个狩猎点，第 $i$ 个狩猎点有 $p_i$ 的概率可以捕捉到猎物，$\text{Dina}$ 的巢穴和 $n$ 个狩猎点相互之间存在若干条直接连接的双向道路。

每天早晨，$\text{Dina}$ 从她的巢穴出发，随机选择一个与巢穴相邻的狩猎点 $u$ 进行一次捕猎，如果她未捕捉到猎物，她会随机选择一个与当前狩猎点 $u$ 相邻的其他狩猎点 $v$ 继续进行一次捕猎，如果在狩猎点 $v$ 仍未捕捉到猎物，$\text{Dina}$ 会按照前述过程继续捕猎。如果在某个狩猎点捕捉到了猎物，$\text{Dina}$ 会立即返回巢穴，结束捕猎。若当前狩猎点 $u$ 与巢穴相邻，而与其他狩猎点不相邻，$\text{Dina}$ 也会选择立即返回巢穴，然后从与巢穴相邻的狩猎点中，随机选择一个狩猎点继续上述捕猎过程。$\text{Dina}$ 在每个狩猎点只进行一次捕猎，然后离开，但后续可能还会回到该狩猎点再次进行捕猎。在本题环境下，如果地点 $u$ 和地点 $v$ 之间有一条直接连接的双向道路，称地点 $u$ 和地点 $v$ **相邻**，否则称地点 $u$ 和地点 $v$ **不相邻**。

令巢穴的编号为 $0$，$n$ 个狩猎点的编号从 $1$ 到 $n$，$\text{Dina}$ 从编号为 $u$ 的地点到达另外一个编号为 $v$ 的地点需要消耗 $h_{u,v}$ 体力和 $t_{u,v}$ 时间。在第 $i$ 个狩猎点每进行一次捕猎，$\text{Dina}$ 会消耗 $h_i$ 体力和 $t_i$ 时间。每当 $\text{Dina}$ 到达某个狩猎点并进行一次捕猎后，她会评估自己的体力消耗和时间花费，如果体力消耗已经达到（或超过）限值 $H$，她就选择立即返回巢穴结束捕猎。如果时间花费已经达到（或超过）限值 $T$，她也会选择立即返回巢穴结束捕猎。$\text{Dina}$ 只有在到达狩猎点并进行一次捕猎后才进行评估，在任何其他时刻均不会进行评估。如果当前位于巢穴，她会在到达巢穴时就进行评估，因为巢穴并无猎物可供捕捉。

需要注意，$\text{Dina}$ 在沿着两个地点间的双向道路移动的过程中并不会评估，因此可能会出现以下情形：到达某个狩猎点且尚未进行捕猎时，$\text{Dina}$ 已消耗的体力或者已花费的时间已经超过限值。在这种情形下，$\text{Dina}$ 仍然会进行一次捕猎，之后再进行评估。

当 $\text{Dina}$ 因为捕猎成功、体力消耗或时间花费达到（或超过）相应限值、当前狩猎点与其他狩猎点不相邻而返回巢穴时，她总会选择一条具有最少时间花费的路径。如果存在多条具有最少时间花费的路径返回巢穴，她会选择其中体力消耗最少的路径。$\text{Dina}$ 在返回巢穴的过程中不会进行捕猎。

将 $\text{Dina}$ 从巢穴出发，因满足以下三个条件之一：

- 捕猎成功
- 体力消耗达到（或超过）限值 $H$
- 时间花费达到（或超过）限值 $T$

返回到达巢穴并结束捕猎的过程称为一次狩猎。给出巢穴和狩猎点之间的道路、每条道路所需要消耗的体力和花费的时间、每个狩猎点进行一次捕猎能够捕获猎物的概率以及所需消耗的体力、花费的时间，试确定 $\text{Dina}$ 完成一次狩猎所消耗体力和花费时间的平均值。

inputFormat:
输入的第一行包含一个整数 $n$，表示狩猎点的数量。

接下来 $n$ 行，每行包含三个数值：整数 $h_i$，整数 $t_i$，实数 $p_i$，分别表示在第 $i$ 个狩猎点进行一次捕猎所消耗的体力、花费的时间、能够捕获猎物的概率。

接下来是一个整数 $m$，表示连接各个地点的双向道路的数量。接着 $m$ 行，每行包含四个整数 $u$，$v$，$h_{u,v}$，$t_{u,v}$，表示从编号为 $u$（$0 \le i \le n$）的地点到另外一个编号为 $v$（$0 \le i \le n$，$u \ne v$）的地点之间存在一条直接连通的道路，需要消耗 $h_{u,v}$ 体力和花费 $t_{u,v}$ 时间。由于是双向道路，从地点 $u$ 到达地点 $v$ 与从地点 $v$ 到达地点 $u$ 所消耗体力和花费时间相同。

最后是两个整数 $H$ 和 $T$，表示体力和时间的限值。

outputFormat: 输出一行，包含两个实数，精确到小数点后一位，分别表示 $\text{Dina}$ 完成一次狩猎所消耗体力和花费时间的平均值。如果你的输出和参考输出绝对误差小于$10^{-1}$，均认为正确。

hint:
**子任务测试采用捆绑方式计分。**

**样例说明**

输入 #1

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

该输入只包含一个狩猎点，从巢穴到狩猎点 $1$ 之间的道路需要消耗 $2$ 体力和 $3$ 时间，体力的限值为 $10$，时间的限值为 $20$，在狩猎点 $1$ 进行一次捕猎需要消耗 $1$ 体力和 $2$ 时间，在狩猎点 $1$ 捕获猎物的概率为 $1.00$，即一定会捕捉到猎物。容易知道，进行一次狩猎所消耗的体力和花费时间的平均值分别为 $5.0=(2+1+2) \times 100\%$ 和 $8.0=(3+2+3) \times 100\%$。

输入 #2

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

相较于第一组输入，新增了两个狩猎点，但只有狩猎点 $1$ 和狩猎点 $2$ 与巢穴有直接道路相连。三个狩猎点之间无直接道路相连，但狩猎点 $1$ 可以间接通过巢穴与狩猎点 $2$ 连通。从巢穴到狩猎点 $2$ 的道路需要消耗 $4$ 体力和 $5$ 时间，在狩猎点 $2$ 进行一次捕猎需要消耗 $2$ 体力和 $3$ 时间。在狩猎点 $1$ 捕获猎物的概率为 $1.00$，即一定会捕捉到猎物，因此 $\text{Dina}$ 会立即返回巢穴并结束狩猎。在狩猎点 $2$ 捕获猎物的概率为 $0.50$，即有 $50\%$ 的概率会捕捉到猎物，但由于狩猎点 $2$ 没有其他狩猎点与之直接连通，因此不管在狩猎点 $2$ 是否捕获到猎物，$\text{Dina}$ 都会选择立即返回巢穴，在返回巢穴时，已经消耗 $10$ 体力，根据题意，不管 $\text{Dina}$ 是否已经捕捉到了猎物，她都会结束狩猎。由于是随机选择，故在巢穴时选择狩猎点 $1$ 和 $2$ 进行狩猎的概率均为 $50\%$，根据计算可知，进行一次狩猎所消耗的体力和花费时间的平均值分别为 $7.5=(2+1+2) \times 50\%+(4+2+4) \times 50\%$ 和 $10.5=(3+2+3) \times 50\%+(5+3+5) \times 50\%$。

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

**数据范围**

- Subtask $1$：$n=1$，$10$ 分。
- Subtask $2$：$1 \le n \le 20$，每个狩猎点和其他狩猎点均无直接道路相连，$20$ 分。
- Subtask $3$：无特殊限制，$70$ 分。

对于 $100\%$ 的数据，$1 \le n \le 200$，$1 \le h_i \le 10$，$1 \le t_i \le 10$，$0 \le p_i \le 1$，$1 \le m \le \text{min}(n (n+1) / 2$，$2000$)，$1 \le h_{u,v} \le 20$，$1 \le t_{u,v} \le 20$，$1 \le H \le 200$，$1 \le T \le 200$。

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

**约定**

- 地点 $u$ 和地点 $v$ 之间至多有一条直接连接的双向道路，两个地点之间的直连双向道路不会重复给出。
- 忽略 $\text{Dina}$ 进行评估所需要的时间。
- 在输入中，表示概率 $p_i$ 的数值是一个具有两位小数的实数。


title: 「RdOI R3」VSQ

description:
设 $x$ 为一个长度不小于 $2$ 的 $01$ 串，如果 $x$ 的所有长度为 $2$ 的子串的异或和均为 $1$，则 $x$ 为一个「VS 串」。

你需要维护一个长度为 $n$ 的 $01$ 串 $a$，支持以下操作：

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|} \hline
\textbf{格式} & \textbf{说明} \cr\hline
\texttt{0 l r} & \text{将区间 }[l,r]\text{ 填充为 }0 \cr\hline
\texttt{1 l r}& \text{将区间 }[l,r]\text{ 填充为 }1 \cr\hline
\texttt{2 l r}& \text{将区间 }[l,r]\text{ 中的每个数取反，即 }1\text{ 变 } 0\text{，}0\text{ 变 }1 \cr\hline
\texttt{3 l r k} & \text{查询}[l,r]\text{ 区间中有多少个长度为 }k\text{ 的子串是「VS 串」} \cr\hline
\texttt{4 l r} & {\def\arraystretch{1}\begin{array}{c}
\text{查询 }[l,r]\text{ 区间内最长的「VS 串」的长度，}\\\text{如果区间内不存在这样的子串则输出 }1 \end{array}} \cr\hline
\end{array}
$$

inputFormat:
第一行两个整数 $n,m$，表示 $01$ 串长度与操作个数。
第二行 $n$ 个整数，表示 $a_1,a_2,\cdots,a_n$。
接下来 $m$ 行，每行三或四个整数 $op, l, r(,k)$，表示一次操作。

outputFormat: 对于每个查询操作，输出一行一个整数，表示其对应的答案。


title: 「PMOI-3」公约数

description:
给出 $n,m$ 和一个长度为 $n-1$ 的序列 $x$，保证 $x_i$ 互不相同。

求
$$
\sum_{i_1=1}^m\sum_{i_2=1}^m\cdots\sum_{i_n=1}^m[\gcd(i_1,i_2)=x_1][\gcd(i_2,i_3)=x_2]\cdots[\gcd(i_{n-1},i_n)=x_{n-1}]$$

答案对 $998244353$ 取模。

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

接下来一行 $n-1$ 个整数，表示 $x_i$。

outputFormat: 一行一个整数。

hint:
【样例解释】

对于第一组样例，只有当 $i_1=1,i_2=2,i_3=2$ 时才满足要求。

【数据范围】

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

- Subtask1（10pts）：$n,m\le 5$；
- Subtask2（15pts）：$n,m\le500$；
- Subtask3（15pts）：$n,m\le 5\times 10^3$；
- Subtask4（15pts）：$n,m\le 5\times 10^4$。
- Subtask5（20pts）：$n,m\le 3\times 10^5$。
- Subtask6（25pts）：无特殊限制。

对于 $100\%$ 的数据满足，$n-1\le m$，$1\le n,m\le 10^6$，$1\le x_i\le m$，保证 $x_i$ 互不相同。


title: 回旋加速器（2021 CoE-II C）

description:
回旋加速器（$\text{Cyclotron}$）是利用磁场和电场使带电粒子作回旋运动并经高频电场反复加速的装置，是高能物理中的重要仪器。

我们来研究回旋加速器的一个简化模型。将回旋加速器视为一个环形的轨道，轨道上设置了 $n$ 个加速腔，依次编号为 $1$ 至 $n$。将一束质子从某个加速腔导入，在导入时，质子束的动能为零。第 $i$ 个加速腔能够为质子束提供 $e_i$ 的动能 ，质子束从第 $i$ 个加速腔运行到第 $i + 1$ 个加速腔会损失 $d_i$ 的动能（由于是环形轨道，编号为 $n$ 的加速腔后面是编号为 $1$ 的加速腔）。

给定每个加速腔能够提供的动能值以及质子束在各个加速腔之间运行所损失的动能值，试确定质子束能否绕环形轨道运行一周。如果能够成功，应该选择从哪个加速腔导入质子束。质子束在两个加速腔之间运行时，动能不能为零，但质子束刚到达加速腔时，动能可以为零，因为可以立即获得加速腔所提供的动能。

inputFormat:
**输入包含多组测试数据。**

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

接下来是 $T$ 组数据，每组数据由三行构成。两组数据之间有一个空行。

每组数据的第一行是一个整数 $n$，表示加速腔的个数。第二行一共 $n$ 个整数，依次表示编号为 $i$ 的加速腔能够提供的动能 $e_i$。第三行一共 $n$ 个整数，依次表示质子束从第 $i$ 个加速腔运行到第 $i + 1$ 个加速腔所损失的动能 $d_i$。由于是环形轨道，第三行的第 $n$ 个整数表示的是从第 $n$ 个加速腔运行到第 $1$ 个加速腔时损失的动能。

outputFormat: 每组数据输出一行。如果质子束无法环绕加速器运行一周，输出 `Failed!`，否则输出导入质子束的加速腔编号，如果有多个加速腔可供选择，选择具有最小编号的加速腔。

hint:
**样例说明**

输入 #1

该组输入共有 $3$ 个加速腔，依次能够提供的动能为 $1$、$2$、$3$。从第 $1$ 个加速腔运行到第 $2$ 个加速腔损失 $2$ 动能，从第 $2$ 个加速腔运行到第 $3$ 个加速腔损失 $3$ 动能，从第 $3$ 个加速腔运行到第 $1$ 个加速腔损失 $4$ 动能。不管从哪个加速腔导入质子束，都会使得质子束在两个加速腔运行过程中动能变为零，无法环绕轨道一周。

输入 #2

该组输入共有 $10$ 个加速腔，如果从第 $1$ 个加速腔导入质子束，将获得动能 $1$，但是在从第 $1$ 个加速腔运行到第 $2$ 个加速腔的过程中会损失 $3$ 动能，因此会使得质子束无法环绕轨道一周。而从第 $2$ 个到第 $10$ 个加速腔中的任意一个导入质子束，均能保证质子束在加速腔之间运行时动能不为零，因此都可作为导入质子束的加速腔，但编号为 $2$ 的加速腔具有最小的编号。需要注意，从第 $2$ 个加速腔导入质子束，当运行到第 $3$ 个加速腔时，动能恰为零，根据题意，这种情形是允许的。

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

**数据范围**

- Subtask $1$：$2 \le n \le 10$，$10$ 分。
- Subtask $2$：$2 \le n \le 10^3$，$30$ 分。
- Subtask $3$：$2 \le n \le 10^5$，$30$ 分。
- Subtask $4$：$2 \le n \le 10^6$，$30$ 分。

对于 $100\%$ 的数据，$1 \le T \le 20$，$0 \lt e_i \le 100$，$0 \lt d_i \le 100$。

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

**约定**

质子束的运行方向规定为：从第 $1$ 个加速腔到第 $2$ 个加速腔，从第 $2$ 个加速腔到第 $3$ 个加速腔$\cdots$从第 $n$ 个加速腔到第 $1$ 个加速腔。


title: 「EZEC-7」加边

background:
> 暴力怎么做？暴力是不是，加边！加边！加边！然后，并查集查询！

Alice 不喜欢并查集，但是她喜欢加边。

description:
给定一棵 $n$ 个节点的树，节点从 $1$ 开始编号，$1$ 号节点是根节点，每条边的方向是从父亲到儿子。每个点有一个点权 $a_i$。Alice 和 Bob 在玩游戏，他们在根节点上放了一个棋子，Alice 和 Bob 轮流将棋子沿边移动，谁不能移动谁输。

已知 Alice 是先手或是后手。在游戏开始前，Alice 可以在树上添加一条有向边 $u\to v$（$1\le u,v\le n$），然后和 Bob 在形成的图上玩这个游戏，她希望自己存在必胜策略。**她也可以选择不加边。如果无法决出胜负则不算胜利。**

给定正整数 $A,B$，Alice 添加边 $u\to v$ 的代价是 $A\times a_u+B\times  a_v$。选择不加边的代价为 $0$。

Alice 要最小化她的代价。如果她怎么加边都不满足要求，输出 $-1$。

Alice 会做出 $T$ 次询问，你需要对每个询问输出答案。

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

第一行输入一个正整数 $T$，表示询问次数。

对于每组询问，第一行输入四个正整数 $n,t,A,B$，其中 $n$ 表示树的节点数，$t$ 表示操作顺序，$t=0$ 表示 Alice 先手，$t=1$ 表示 Alice 后手。

接下来一行 $n-1$ 个正整数，第 $i$ 个数表示节点 $i+1$ 的父亲编号 $f_{i+1}$。

接下来一行 $n$ 个正整数，第 $i$ 个表示 $a_i$ 的值。

outputFormat: 对于每个询问，输出一行一个整数，表示 Alice 的最小代价。如果她怎么加边都不满足要求，输出 $-1$。

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

在第 $1$ 组询问中，Alice 是后手，她无论怎么添加边都无法拥有必胜策略，所以输出 $-1$。
在第 $2$ 组询问中，Alice 是后手，她不需要添加边就拥有必胜策略，所以代价为 $0$。
在第 $3$ 组询问中，Alice 是先手，她只能添加一条 $1\to 3$ 的边使自己必胜，此时代价为 $2\times 4+7\times 2=22$。
在第 $4$ 组询问中，Alice 是后手，她可以添加一条 $9\to 5$ 的边使自己必胜，此时代价为 $523\times 109+182\times 162=86491$。她还有其他使自己必胜的方法，但是可以发现 $86491$ 是最小代价。

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

**【数据范围】**

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

- Subtask 1（10 points）：$n\le 10$，$T=1$；
- Subtask 2（15 points）：$\sum n\le 200$；
- Subtask 3（15 points）：$\sum n\le 2000$；
- Subtask 4（10 points）：$f_i=i-1$；
- Subtask 5（10 points）：$f_i=1$；
- Subtask 6（20 points）：$\sum n\le 5\times 10^5$；
- Subtask 7（20 points）：无特殊限制。

对于 $100\%$ 的数据，满足 $1\le T\le 2\times10^3$，$2\le n\le2\times 10^5$，$\sum n\le 5\times 10^6$，$1\le a_i,A,B\le 10^9$，$f_i<i$，$t\in\{0,1\}$。

------------
**【提示】**

请使用较快的输入方式。


title: 黑白棋（2021 CoE-II B）

description:
$\text{Alice}$ 和 $\text{Bob}$ 正在玩一种称为“黑白棋”的游戏。该游戏的规则如下：

- 游戏在直角坐标系中进行。

- $\text{Alice}$ 执黑棋，$\text{Bob}$ 执白棋。

- 初始时，在直角坐标系中任选 $n$ 条与 $X$ 轴平行的直线，直线在 $Y$ 轴上的截距均为整数，且互不相同。$\text{Alice}$ 在每条直线上都会放置一枚黑棋，$\text{Bob}$ 在每条直线上都会放置一枚白棋，棋子位置的 $X$ 坐标值均为整数。在同一条直线上的两枚棋子位置不会相同。

- $\text{Alice}$ 和 $\text{Bob}$ 轮流走棋，$\text{Alice}$ 总是先走棋。每名玩家在走棋时，先选择一条直线，然后沿着直线移动该条直线上己方颜色的棋子。

- 每个玩家可以将自己的棋子向着靠近对方棋子的方向一次性移动若干整数单位距离，称之为**前进**。每个玩家也可以向着远离对方棋子的方向一次性移动若干整数单位距离，称之为**后退**。只要在前进时不跨过对方的棋子，也不使黑棋和白棋的位置发生重叠，前进的最远距离不限，但是前进的距离至少为 $1$，如果无法满足前述条件，则玩家不能执行前进操作。为了避免玩家反复后退导致游戏无法结束，在一局游戏中，某个玩家执行后退操作的总次数不能超过 $k$ 次。与此同时，为了防止游戏区域太大以致在显示游戏状态上造成不便，每次后退的距离至少为 $1$，但不能超过 $d$。如果无法满足前述条件，玩家不能执行后退操作。

- 玩家在轮到自己走棋时，如果能够执行操作就必须执行一次操作，此操作可以是前进操作，也可以是后退操作（如果未超出后退次数的限制）。

- 如果某个玩家无法执行任何操作来移动自己的棋子，将输掉游戏，游戏结束。

给定游戏的初始状态，假设 $\text{Alice}$ 和 $\text{Bob}$ 在游戏时均采用最佳策略，试确定 $\text{Alice}$ 能否获胜。

inputFormat:
**输入包含多组测试数据。**

输入第一行包含一个整数 $T$，表示测试数据的组数。接着是一个空行。接下来是 $T$ 组表示游戏初始状态的数据。

每组数据的第一行包含三个整数 $n$，$k$，$d$，表示直线的数量，允许后退的总次数，每次后退的最大距离。接下来是 $n$ 行数据，每行包含三个整数 $y_i$，$b_i$，$w_i$，分别表示第 $i$ 条直线的 $Y$ 轴截距以及在该条直线上的黑棋的 $X$ 坐标值和白棋的 $X$ 坐标值（$b_i \ne w_i$）。

每两组测试数据之间有一个空行。

outputFormat: 如果 $\text{Alice}$ 能够获胜，输出 `Yes`，否则输出 `No`。

hint:
**样例说明**

下图对应输入 \#1 的第一组数据，如果 $\text{Alice}$ 采用最优策略，无论 $\text{Bob}$ 如何走棋，$\text{Alice}$ 都能够获胜。

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

以下是 $\text{Alice}$ 的必胜策略。首先，$\text{Alice}$ 选择将 $y=3$ 的直线上的黑棋从 `4` 移动到 `6`，使得两条直线上黑棋和白棋之间的间距均为 $2$，由于 $k$ 为 $0$，相当于不允许执行后退操作，如果 $\text{Bob}$ 选择移动 $y=3$ 直线上的白棋，将使得该直线上的两颗棋子相邻，后续无法再移动。同样的，如果 $\text{Bob}$ 选择移动 $y=7$ 直线上的白棋，也将使得该直线上的两颗棋子相邻，后续无法再移动。因此无论 $\text{Bob}$ 如何操作，总会使得一条直线上的两颗棋子相邻，无法再继续移动，而另外一条直线上的棋子间距为 $2$，还可以再移动一次，$\text{Alice}$ 将剩下可以移动的黑棋再移动一步后，后续 $\text{Bob}$ 无法移动白棋，因此 $\text{Alice}$ 会获胜。

对于输入 \#1 的第二组数据，无论 $\text{Alice}$ 如何走棋，$\text{Bob}$ 总能够获胜。

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

**数据范围**

对于 $100\%$ 的数据，$1 \le T \le 100$，$1 \le n \le 100$，$0 \le k \le 100$，$1 \le d \le 20$，$-100 \le y_i \le 100$，$-10^3 \le b_i \le 10^3$，$-10^3 \le w_i \le 10^3$。


title: [JRKSJ R6] func

description:
**这是一道 IO 交互题．**

你有一个一次函数 $f(x)=kx+b$（$1\le x \le n-1$）．这个一次函数满足 $k,b$ 均为整数且 $k>0$．

vectorwyx 修改了这个函数，具体而言，他会选择一个整数 $t$（$1\le t \le n-1$），将这个函数在直线 $x=t$ 及右侧的部分向右平移一个单位长度，并把两部分的端点用直线段连接，得到一个分段函数 $g(x)$：

$$
g(x)=\begin{cases}
kx+b&1\le x<t\\
kt+b& t\le x <t+1\\
k(x-1)+b& t+1\le x \le n
\end{cases}
$$

请通过交互的方式得到 $t$ 的值．

### 交互方式

**本题单个测试点中含有多组数据．**

1. 首先从标准输入流读入一个整数 $T$，表示数据组数．
1. 接下来你将进行 $T$ 组数据的交互．对于每组数据，首先从标准输入流读入三个整数 $n,Q,P$．
1. 你可以通过向标准输出流输出 `? l r p` $(1\le l \le r \le n$，$2\le p \le P$$)$ 的方式来询问．在单组数据中，你最多只能进行 $Q$ 次 `?` 操作．交互库会根据你的询问依次做出以下判断并向标准输入流发送返回结果：
    - 若你的询问数据范围错误，回答为 $-2$．此时交互库会直接返回 WA．你需要立刻退出你的程序来避免与已经结束程序的交互库交互引起超时．
    - 若 $g(l)=g(r)$，回答为 $-1$．
    - 否则回答为 $(g(l) + g(r))\bmod p$．
1. 你可以通过向标准输出流输出 `! t` 的方式来给出答案．你只能进行一次回答操作，且回答操作必须是你在每组数据中进行的最后一个操作．交互完成后，从标准输入流读入一个零或一的整数 $x$．若 $x=1$ 则代表当前数据回答正确，你需要回到步骤 $2$ 以进行下一组数据的交互．否则 $x=0$，你需要立刻退出自己的程序．

**不要忘记在每次输出后刷新缓冲区，否则你将会 TLE．**

下面是一些语言的刷新缓冲区操作：

- C++：`fflush(stdout)` 或 `cout.flush()`．
- C: `fflush(stdout)`．
- Java: `System.out.flush()`．
- Python: `stdout.flush()`．
- Pascal: `flush(output)`．
- 其他语言：请参考对应语言的帮助文档．

inputFormat: 见「交互方式」．

outputFormat: 见「交互方式」，


title: 「SWTR-7」How to AK NOI?

background:
#### 一些关于字符串的定义与约定详见「帮助 / 提示」部分。

#### 请不要恶意卡评测。

---

小 A 正在读一篇文章 ——《如何优雅地 AK NOI？》

description:
不幸的是，这篇文章是用英语写的。小 A 的视力很糟糕，同时词汇量也很小。

具体地，这篇文章可以用一个字符串 $t$ 表示。同时给出另一个字符串 $s$：小 A 所有认识的单词，都是 $s$ 的**长度不小于 $k$ 的**子串。

一段文字 $T$ 被称为「可读懂的」，当且仅当其能被分割成若干个小 A 读得懂的单词。例如当 $k=2$，$s=\texttt{abcd}$ 时，$\texttt{abcd/abc}$ 和 $\texttt{cd/ab/bc/bcd}$ 就是可读懂的，而 $\texttt{abcc}$ 和 $\texttt{tzcaknoi}$ 就是不可读懂的。

接下来，小 A 会进行 $q$ 次行动：

- Type 1：擦亮眼睛。具体地，小 A 会选择文章 $t$ 的一个子串 $t[l:r]$，并将其修改为字符串 $x\ (|x|=r-l+1)$。
- Type 2：阅读文章。具体地，小 A 会选择文章 $t$ 的一个子串 $t[l:r]$ 并进行阅读。**对于每次 Type 2 的操作，你需要告诉小 A 他能不能看懂这段文字**。能够读懂则输出 `Yes`，否则输出 `No`。

inputFormat:
第一行一个正整数 $T$，表示该点 Subtask 编号。
第二行一个字符串 $s$。
第三行一个字符串 $t$。
第四行一个正整数 $k$。
第五行一个正整数 $q$。

接下来 $q$ 行，每行表示一个询问。首先给出操作参数 $op$：
- 若 $op=1$，则接下来两个正整数 $l,r$ 与一个字符串 $x$，表示将 $t[l:r]$ 修改为 $x$。
- 若 $op=2$，则接下来两个正整数 $l,r$，表示一次询问。

outputFormat: 对于每个询问输出一行字符串：若可以读懂则输出 `Yes`，否则输出 `No`。

samples:
No
No
Yes
Yes
Yes
Yes
Yes
No
No
No
No
Yes
No
No
Yes

hint:
**「数据范围与约定」**

记 $n=|s|$，$m=|t|$，$L=\sum |x|$。

| Subtask |    $n\leq$     | $m\leq$ | $L\leq$ | $q\leq$ | $k\leq$ |   分值    |
| :-----: | :------------: | :-----: | :-----: | :-----: | :-----: | :-------: |
| 0 |  |  |  |  |  | 0 point |
|    1    |      $70$      |  $70$   |         |  $70$   |         | 10 points |
|    2    |     $200$      |  $200$  |         |  $200$  |         | 10 points |
|    3    |     $10^3$     | $10^3$  |         | $10^3$  |         | 10 points |
|    4    |                |         |         |         |   $1$   | 10 points |
|    5    | $2\times 10^5$ | $10^5$ |   $0$   | $2\times 10^4$  |   $5$   | 15 points |
|    6    | $2\times 10^5$ | $10^5$  | $5\times 10^4$  | $2\times 10^4$  |   $5$   | 10 points |
|    7    |  |         |         |         |   $6$   | 15 points |
|    8    |                |         |         |         |         | 20 points |

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^6$，$1\leq L\leq 3\times 10^5$，$1\leq m\leq 2\times 10^5$，$1\leq q\leq 10^5$，$1\leq k\leq 8$。    保证 $|x|=r-l+1$，且字符集为 $[\texttt{a,i}]$。

---

Subtask 0 是样例及 **Hack 数据**。

- Subtask 0 ~ 3 时间限制 1s。
- Subtask 4 ~ 6 时间限制 1.5s。
- Subtask 7 时间限制 3s。
- Subtask 8 时间限制 4.5s。

**「子任务依赖」**

**本题使用子任务依赖**。

简单地说，如果 Subtask a 依赖于 Subtask b，那么**只有你通过 Subtask b 的全部测试点时，Subtask a 才会计入总分**。

- Subtask 1 依赖于 Subtask 0。
- Subtask 2 依赖于 Subtask 0,1。
- Subtask 3 依赖于 Subtask 0,1,2。
- Subtask 6 依赖于 Subtask 0,5。
- Subtask 7 依赖于 Subtask 0,5,6。
- Subtask 8 依赖于 Subtask 0~7。

**保证 Subtask 0 的 Hack 数据符合 Subtask 1,2,3,6,7,8 的所有限制**。

**「帮助 / 提示」**

字符串 $t'$ 是 $t$ 的子串，当且仅当我们能够从 $t$ 的开头和结尾删除若干个字符（可以不删除）并得到 $t'$。
定义 $t[l:r]$ 表示 $t_lt_{l+1}\cdots t_{r-1}t_r$ 所形成的字符串。

读入文件较大，请注意 IO 优化。

**「题目来源」**

[Sweet Round 07](https://www.luogu.com.cn/contest/51773) E。
idea & solution & data：[Alex_Wei](https://www.luogu.com.cn/user/123294)；验题：[tzc_wk](https://www.luogu.com.cn/user/115194)。


title: 数树（2021 CoE-II E）

description:
定义一棵树 $\mathcal T$ 为 $k_1-k_2$ 叉树，当且仅当每个节点 $p\in \mathcal T$ 有儿子，要么有 $k_1$ 个儿子，要么有 $k_2$ 个儿子，$k_1 \ne k_2$。我们定义两棵 $k_1-k_2$ 树同构，当且仅当以下伪代码返回的字符串相同：
$$
\begin{array}{ll}
1 &  \textbf{Input. } \text{The edges of the tree } \mathcal T  \\
2 &  \textbf{Output. } \text{The eigenvalue of tree } \mathcal T.\\
3 &  \textbf{Algorithm. }  \text{dfs}(u)\\
4 &  \qquad result \gets \texttt{'('} \\
5 &  \qquad \textbf{for} \text{ each } (u, v) \text{ in the  } \mathcal T \\
6 &  \qquad \qquad \textbf{if }  v \text{ is not the father of  } u \\
7 &  \qquad \qquad\qquad  result \gets result\  +\ \mathrm{dfs}(v) \\
8 &  \qquad result\gets result\ +\ \texttt{')'} \\
9 & \qquad \textbf{return }  result \\
10 & \textbf{Method. } \text{check}(\mathcal T) \\
11 & \qquad \textbf{return } \text{dfs(the root of the tree } \mathcal T\text{)}
\end{array}
$$

形式化地，$k_1-k_2$ 叉树有**确定的根节点**，每个节点的若干儿子之间**有顺序**，但是节点**没有标号**。

若 $k_1-k_2$ 叉树 $\mathcal T$ 有一个 $k_1$ 叉节点，则得分 $a$，若有一个 $k_2$ 叉节点，则得分 $b$，叶节点无得分。定义一棵树的得分为其所有节点的得分之和，记为 $v(\mathcal T)$。

现在我们在所有互不同构的 $n$ 个节点的 $k_1-k_2$ 叉树中等概率随机生成一棵 $\mathcal T$，记 $v(\mathcal T)$ 的期望值为 $\mathbb{E}(v(\mathcal T))$。

可以证明 $\mathbb{E}(v(\mathcal T))$ 为有理数。当 $\mathbb{E}(v(\mathcal T))$ 不为零时，令答案 $\mathbb{E}(v(\mathcal T)) = p/q$，其中 $p$ 与 $q$ 互质。你需要输出最小的自然数 $x$ 使得 $p\equiv qx\pmod P$，其中 $P=998244353$，可以证明这样的自然数 $x$ 必定存在。

inputFormat: 输入包含五个整数 $k_1,\ k_2,\ n,\ a,\ b$，其含义如题目描述所示。

outputFormat: 输出一个整数 $x$，表示方程 $p\equiv qx\pmod P$ 的最小自然数解，其中 $P=998244353$。

hint:
**样例说明**

具有 $6$ 个结点的不同构 $2-3$ 叉树共有 $5$ 棵，每棵得分均为 $3$ 分，则 $\mathbb{E}(v(\mathcal T))=15/5=3$，故 $p=3$ 且 $q=1$，则 $x=3$。

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

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

**数据范围**

共 $10$ 个测试点。

对于测试点 $1$，满足 $1 \le k_1,\ k_2<n\leq 10$。

对于测试点 $2$，满足 $1 \le k_1,\ k_2<n\leq 15$。

对于测试点 $3\sim 4$，满足 $1 \le k_1,\ k_2<n\leq 5 \times 10^3$。

对于测试点 $5\sim 6$，满足 $a=b=1,\ 1 \le k_1,\ k_2<n\leq 10^5$。

对于 $100\%$ 的数据，满足 $1 \le k_1,\ k_2<n\leq 10^7,\ k_1 \ne k_2, \ k_1+k_2 \le n, \  \ 1 \le \ a,\ b\leq 10^7$。

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

**约定**

- 测试数据保证 $\mathbb{E}(v(\mathcal T))$ 不为零。


title: SvT

background: （我并不想告诉你题目名字是什么鬼）

description:
有一个长度为  $n$ 的仅包含小写字母的字符串  $S$，下标范围为  $[1,n]$。

现在有若干组询问,对于每一个询问,我们给出若干个后缀（以其在  $S$ 中出现的起始位置来表示），求这些后缀两两之间的 LCP（最长公共前缀）的长度之和。一对后缀之间的 LCP 长度仅统计一遍。

inputFormat:
第一行两个正整数  $n,m$，分别表示  $S$ 的长度以及询问的次数。

接下来一行有一个字符串  $S$。

接下来有  $m$ 组询问，对于每一组询问，均按照以下格式在一行内给出：

首先是一个整数  $t$，表示共有多少个后缀。接下来  $t$ 个整数分别表示  $t$ 个后缀在字符串  $S$ 中的出现位置。

outputFormat: 对于每一组询问，输出一行一个整数，表示该组询问的答案。由于答案可能很大，仅需要输出这个答案对于 $\text{23333333333333333}$ （一个巨大的质数）取模的余数。

hint:
样例解释:

对于询问一，只有一个后缀 `oqqq`，因此答案为 $0$。

对于询问二，有两个后缀`poqqq`以及`qqq`，两个后缀之间的 LCP 为 $0$，因此答案为 $0$。

对于询问三，有四个后缀 `popoqqq` , `opoqqq` , `qqq` , `qq`，其中只有 `qqq`，`qq` 两个后缀之间的LCP不为 $0$，且长度为 $2$，因此答案为 $2$。

对于 $100\%$ 的测试数据，有 $|S|\le 5\times 10^5$，且 $\sum t\le3\times10^6$。

特别注意:由于另一世界线的某些参数发生了变化，对于一组询问，即使一个后缀出现了多次，也仅算一次。

题目来源：bzoj 3879


title: 「EZEC-10」Shape

background: 规定 $(x,y)$ 表示第 $x$ 行第 $y$ 列的格子。

description:
小 A 有一个 $n\times m$ 的网格，一些为白色格子，剩余为黑色格子。

小 A 选择四个整数 $x_1,x_2,y_1,y_2$，满足如下条件：

1. $1\le x_1<x_2\le n$ 且 $1\le y_1<y_2\le m$。
2. $x_1+x_2$ 为偶数。

若 $(x_1,y_1)\to (x_2,y_1),(x_1,y_2)\to (x_2,y_2),(\frac{x_1+x_2}{2},y_1)\to (\frac{x_1+x_2}{2},y_2)$ 这三段中的格子均为白色，则称这三段构成的图形为 H 形。

小 A 想知道，这个网格中存在多少不同的 H 形。

**两个 H 形相同，当且仅当两个 H 形的 $x_1,x_2,y_1,y_2$ 均相同。**

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

后 $n$ 行每行 $m$ 个整数表示网格，其中 $0$ 代表白色，$1$ 代表黑色。

outputFormat: 一个整数，表示不同 H 形的数量。

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

$(x_1,x_2,y_1,y_2)=(1,3,3,4)$ 的 H 形符合。

**【样例 2 解释】**

$(x_1,x_2,y_1,y_2)=(1,5,1,3),(2,4,1,3)$ 的 H 形符合。

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

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

- Subtask 1（1 point）：$n=2$。
- Subtask 2（9 points）：$ n,m\le 50$。
- Subtask 3（10 points）：$ n,m\le 100$，**时限为 $500ms$**。
- Subtask 4（30 points）：$ n,m\le 500$。
- Subtask 5（50 points）：无特殊限制。

对于 $100\%$ 的数据，$2\le n,m\le 2\times 10^3$。


title: 「EZEC-9」Meltel

background:
> 貴方だけは許せない。
> 『唯独你不可原谅。』
> 貴方だけは私の全てを許してくれた。
> 『唯独你宽恕了我的一切。』
> 貴方だけは私の全てを奪い尽くし食い尽くし
> 『唯独你覆灭了我的世界，』
> 焼き尽くして全てを無駄にした。
> 『焚烧殆尽，山陷地裂。』

description:
给定正整数 $n$，请对 $s=0,1, \dots, n$，计数满足存在恰好 $s$ 棵二叉树的 $n$ 个结点的由有标号有根树组成的有标号森林的个数。
对 $998244353$ 取模。

定义二叉树为每个结点只有不超过 $2$ 个儿子的有标号有根树。
定义两片森林不同，当且仅当存在两个结点的父亲不同（根结点视为没有父亲）。

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

outputFormat: 一行，$n+1$ 个非负整数，表示对于 $s=0,1,\dots,n$ 的答案。

hint:
【样例 $1$ 说明】

$3$ 个点只可能出现二叉树，因此 $s=0$ 的方案数为 $0$。
$3$ 个点的有标号有根二叉树有 $9$ 种，因此 $s=1$ 的方案数为 $9$。
$2$ 个点的有标号有根二叉树有 $2$ 种，因此 $s=2$ 的方案数为 $3 \times 2 = 6$。
单个结点也算有标号有根二叉树，因此 $s=3$ 的方案数为 $1$。

【数据规模与约定】

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

-  Subtask 1（5 points）：$n\le 5$。
-  Subtask 2（5 points）：$n \le 10$。
-  Subtask 3（30 points）：$n\le 10^3$。
-  Subtask 4（30 points）：$n\le 8\times 10^3$。
-  Subtask 5（30 points）：无特殊限制。

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


title: [USACO21FEB] No Time to Dry P

description:
Bessie 最近收到了一套颜料，她想要给她的牧草地一端的栅栏上色。栅栏由 $N$ 个 $1$ 米长的小段组成（$1\le N\le 2\cdot 10^5$）。Bessie 可以使用 $N$ 种不同的颜色，她将这些颜色由浅到深用 $1$ 到 $N$ 标号（$1$ 是很浅的颜色，$N$ 是很深的颜色）。从而她可以用一个长为 $N$ 的整数数组来描述她想要给栅栏的每一小段涂上的颜色。

初始时，所有栅栏小段均未被上色。Bessie 一笔可以给任意连续若干小段涂上同一种颜色，只要她不会在较深的颜色之上涂上较浅的颜色（她只能用较深的颜色覆盖较浅的颜色）。

例如，一段长为 $4$ 的未被涂色的栅栏可以按如下方式上色：

```
0000 -> 1110 -> 1122 -> 1332
```

不幸的是，Bessie 没有足够的时间等待颜料变干。所以，Bessie 认为她可能需要放弃为栅栏上某些小段上色！现在，她正在考虑 $Q$ 个候选的区间（$1\le Q\le 2\cdot 10^5$），每个区间用满足 $1 \leq a \leq b \leq N$ 的两个整数 $(a,b)$ 表示，为需要上色的小段 $a \ldots b$ 的两端点位置。

对于每个候选区间，将所有区间内的栅栏小段都涂上所希望的颜色，并且区间外的栅栏小段均不涂色，最少需要涂多少笔？注意在这个过程中 Bessie 并没有真正进行任何的涂色，所以对于每个候选区间的回答是独立的。

inputFormat:
输入的第一行包含 $N$ 和 $Q$。

下一行包含一个长为 $N$ 的整数数组，表示每个栅栏小段所希望的颜色。

以下 $Q$ 行，每行包含两个空格分隔的整数 $a$ 和 $b$，表示一个需要涂色的候选区间。

outputFormat: 对于 $Q$ 个候选区间的每一个，输出一行，包含答案。

hint:
#### 样例 1 解释

在这个样例中，对应颜色为  `1 1 2` 的子段涂上颜色需要两笔。
对应颜色为 `2 1 1 2` 的子段涂上颜色需要三笔。
对应颜色为 `1 2 2 1 1 2` 的子段涂上颜色需要三笔。
对应颜色为 `1 2 3 2` 的子段涂上颜色需要三笔。

#### 测试点性质

 - 对于 $10\%$ 的数据，满足 $N,Q\le 100$。
 - 对于另外 $15\%$ 的数据，满足 $N,Q\le 5000$。
 - 对于另外 $25\%$ 的数据，输入数组不包含大于 $10$ 的数。
 - 对于另外 $50\%$ 的数据，没有额外限制。

供题：Andi Qu，Brian Dean，Benjamin Qi


title: [USACO21FEB] Minimizing Edges P

description:
Bessie 有一个连通无向图 $G$。$G$ 有 $N$ 个编号为 $1\ldots N$ 的结点，以及 $M$ 条边（$2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$）。$G$ 有可能包含自环（一个结点连到自身的边），但不包含重边（连接同一对结点的多条边）。

令 $f_G(a,b)$ 为一个布尔函数，对于每一个 $1\le a\le N$ 和 $0\le b$，如果存在一条从结点 $1$ 到结点 $a$ 的路径恰好经过了 $b$ 条边，则函数值为真，否则为假。如果一条边被经过了多次，则这条边会被计算相应的次数。

Elsie 想要复制 Bessie。具体地说，她想要构造一个无向图 $G'$，使得对于所有的 $a$ 和 $b$，均有 $f_{G'}(a,b)=f_G(a,b)$。

Elsie 想要进行最少数量的工作，所以她想要构造最小可能的图。所以，你的工作是计算 $G'$ 的边数的最小可能值。

每个输入包含 $T$（$1\le T\le 5\cdot 10^4$）组独立的测试用例。保证所有测试用例中的 $N$ 之和不超过 $10^5$，且所有测试用例中的 $M$ 之和不超过 $2\cdot 10^5$。

inputFormat:
输入的第一行包含 $T$，为测试用例的数量。

每个测试用例的第一行包含两个整数 $N$ 和 $M$。

每个测试用例的以下 $M$ 行每行包含两个整数 $x$ 和 $y$（$1\le x\le y\le N$），表示 $G$ 中存在一条连接 $x$ 与 $y$ 的边。

为提高可读性，相邻的测试用例之间用一个空行隔开。

outputFormat: 对每个测试用例，输出一行，为 $G'$ 中的边数的最小可能值。

hint:
#### 样例 1 解释

在第一个测试用例中，Elsie 可以通过从 $G$ 中移除 $(2,5)$ 来构造得到 $G'$。或者，她也可以构造一张包含以下边的图，因为她并未被限制只能从 $G$ 中移除边：

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

Elsie 显然不能得到比 $N-1$ 更优的解，因为 $G'$ 一定也是连通的。

#### 样例 2 解释

在以上这些测试用例中，Elsie 都不能做得比 Bessie 更优。

#### 测试点性质：

 - 对于另外 $5\%$ 的数据，满足 $N\le 5$。
 - 对于另外 $10\%$ 的数据，满足 $M=N$。
 - 对于另外 $20\%$ 的数据，如果并非对于所有的 $b$ 均有 $f_G(x,b)=f_G(y,b)$，则存在 $b$ 使得 $f_G(x,b)$ 为真且 $f_G(y,b)$ 为假。
 - 对于另外 $30\%$ 的数据，满足 $N\le 10^2$。
 - 对于另外 $25\%$ 的数据，没有额外限制。

供题：Benjamin Qi


title: [USACO21FEB] Counting Graphs P

description:
Bessie 有一个连通无向图 $G$。$G$ 有 $N$ 个编号为 $1\ldots N$ 的结点，以及 $M$ 条边（$1\le N\le 10^2, N-1\le M\le \frac{N^2+N}{2}$）。$G$ 有可能包含自环（一个结点连到自身的边），但不包含重边（连接同一对结点的多条边）。

令 $f_G(a,b)$ 为一个布尔函数，对于每一个 $1\le a\le N$ 和 $0\le b$，如果存在一条从结点 $1$ 到结点 $a$ 的路径恰好经过了 $b$ 条边，则函数值为真，否则为假。如果一条边被经过了多次，则这条边会被计算相应的次数。

Elsie 想要复制 Bessie。具体地说，她想要构造一个无向图 $G'$，使得对于所有的 $a$ 和 $b$，均有 $f_{G'}(a,b)=f_G(a,b)$。

你的工作是计算 Elsie 可以构造的图 $G'$ 的数量，对 $10^9+7$ 取模。与 $G$ 一样，$G'$ 可以包含自环而不能包含重边（这意味着对于 $N$ 个有标号结点共有 $2^{\frac{N^2+N}{2}}$ 个不同的图）。

每个输入包含 $T$（$1\le T\le \frac{10^5}{4}$）组独立的测试用例。保证所有测试用例中的 $N^2$ 之和不超过 $10^5$。

inputFormat:
输入的第一行包含 $T$，为测试用例的数量。

每个测试用例的第一行包含整数 $N$ 和 $M$。

每个测试用例的以下 $M$ 行每行包含两个整数 $x$ 和 $y$（$1\le x\le y\le N$），表示 $G$ 中存在一条连接 $x$ 与 $y$ 的边。

为提高可读性，相邻的测试用例之间用一个空行隔开。

outputFormat: 对每个测试用例，输出一行，为不同的 $G'$ 的数量，对 $10^9+7$ 取模。

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

在第一个测试用例中，$G'$ 可以等于 $G$，或以下两个图之一：

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

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

#### 样例 2 解释：

有一些较大的测试用例。确保你的答案对 $10^9+7$ 取模。注意倒数第二个测试用例的答案为 $2^{45}\pmod{10^9+7}$。

#### 测试点性质：

 - 对于另外 $5\%$ 的数据，满足 $N\le 5$。
 - 对于另外 $10\%$ 的数据，满足 $M=N-1$。
 - 对于另外 $30\%$ 的数据，如果并非对于所有的 $b$ 均有 $f_G(x,b)=f_G(y,b)$，则存在 $b$ 使得 $f_G(x,b)$ 为真且 $f_G(y,b)$ 为假。
 - 对于另外 $45\%$ 的数据，没有额外限制。

供题：Benjamin Qi


title: [USACO21FEB] Stone Game G

description:
Bessie 和 Elsie 正在用 $N$（$1\le N\le 10^5$）堆石子进行一个游戏，其中对于每个 $1\le i\le N$，第 $i$ 堆石子有 $a_i$ 个石子（$1\le a_i\le 10^6$）。两头奶牛交替行动，Bessie 先手。

 - 首先，Bessie 选择某个正整数 $s_1$ 并从至少包含 $s_1$ 个石子的某堆石子中取走 $s_1$ 个石子。
 - 然后 Elsie 选择某个正整数 $s_2$，使得 $s_1$ 整除 $s_2$，并从至少包含 $s_2$ 个石子的某堆石子中取走 $s_2$ 个石子。
 - 然后 Bessie 选择某个正整数 $s_3$，使得 $s_2$ 整除 $s_3$，并从至少包含 $s_3$ 个石子的某堆石子中取走 $s_3$ 个石子，以此类推。
 - 总的来说，第 $i$ 回合中取走的石子数量 $s_i$ 必须整除 $s_{i+1}$。

第一个无法在其回合中取走石子的奶牛为失败者。

计算可以令 Bessie 必胜（表示存在一种策略，无论 Elsie 如何行动，Bessie 均可获胜）的第一回合取石子的方法数。如果两种取石子的方法中取的石子数量不同或者取的石子堆不同，则认为是两种不同的取石子的方法。

inputFormat:
输入的第一行包含 $N$。

第二行包含 $N$ 个空格分隔的整数 $a_1,\ldots,a_N$。

outputFormat:
输出可以令 Bessie 必胜（表示存在一种策略，无论 Elsie 如何行动，Bessie 均可获胜）的第一回合取石子的方法数。

注意这个问题涉及到的整数大小可能需要使用 $64$ 位整数型存储（例如，C/C++ 中的 long long）。

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

当 Bessie 从唯一的一堆石子中取走 $4$、$5$、$6$ 或 $7$ 个石子时可以获胜。此时游戏会立刻结束。

#### 样例 2 解释：

当 Bessie 从任意一堆中取走 $2$ 或 $3$ 个石子时可以获胜。此后两头奶牛会交替取走相同数量的石子，而 Bessie 执行了最后一次操作。

#### 测试点性质：

 - 对于另外 $15\%$ 的数据，满足 $N=2$。
 - 对于另外 $25\%$ 的数据，满足 $N,a_i\le 100$。
 - 对于另外 $50\%$ 的数据，没有额外限制。

供题：Benjamin Qi


title: [USACO21FEB] Modern Art 3 G

description:
厌倦了常规的二维画作（同时也由于作品被他人抄袭而感到失落），伟大的奶牛艺术家牛加索决定转变为更为极简主义的一维风格。她的最新画作可以用一个长为 $N$（$1 \leq N \leq 300$）的一维数组来描述，其中每种颜色用 $1\ldots N$ 中的一个整数表示。

令牛加索感到沮丧的是，尽管这样，她的竞争对手哞奈似乎已经发现了如何抄袭她的这些一维画作！哞奈会用一种颜色涂在一个区间上，等待颜料干了再涂另一个区间，以此类推。哞奈可以使用 $N$ 中颜色中的每一种任意多次（也可以不用）。

请计算哞奈抄袭牛加索的最新一维画作所需要的涂色的次数。

inputFormat:
输入的第一行包含 $N$。

下一行包含 $N$ 个范围在 $1 \ldots N$ 之内的整数，表示牛加索的最新一维画作每个方格上的颜色。

outputFormat: 输出抄袭这一画作所需要的最小涂色次数。

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

在这个样例中，哞奈可以按下列方式进行涂色。我们用 $0$ 表示一个未涂色的方格。

 - 初始时，整个数组均未被涂色：`0 0 0 0 0 0 0 0 0 0`
 - 哞奈将前九个方格涂上颜色 $1$：`1 1 1 1 1 1 1 1 1 0`
 - 哞奈在一个区间上涂上颜色 $2$：`1 2 2 2 2 2 2 2 1 0`
 - 哞奈在一个区间上涂上颜色 $3$：`1 2 3 3 3 3 3 2 1 0`
 - 哞奈在一个区间上涂上颜色 $4$：`1 2 3 4 4 4 3 2 1 0`
 - 哞奈在一个方格上涂上颜色 $1$：`1 2 3 4 1 4 3 2 1 0`
 - 哞奈在最后一个方格上涂上颜色 $6$：`1 2 3 4 1 4 3 2 1 6 `

注意在第一次涂色时，哞奈可以同时在前九个方格之外将第十个方格也同时涂上颜色 $1$，这并不会影响最后的结果。

#### 测试点性质：

 - 对于另外 $15\%$ 的数据，画作中仅出现颜色 $1$ 和 $2$。
 - 对于另外 $30\%$ 的数据，对于每一个 $1\le i\le N$，第 $i$ 个方格的颜色在范围 $\left[12\left\lfloor\frac{i-1}{12}\right\rfloor+1,12\left\lfloor\frac{i-1}{12}\right\rfloor+12\right]$ 之内。
 - 对于另外 $50\%$ 的数据，没有额外限制。

供题：Brian Dean，Benjamin Qi


title: [USACO21FEB] Count the Cows G

description:
如同平常一样，Farmer John 的奶牛们分散在他的最大的草地上。草地可以看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。

奶牛分布在草地上的方式相当迷人。对于每一个满足 $x\ge 0$ 以及 $y\ge 0$ 的方格 $(x,y)$，当对于所有整数 $k\ge 0$，$\left\lfloor \frac{x}{3^k}\right\rfloor$ 和 $\left\lfloor \frac{y}{3^k}\right\rfloor$ 除以三的余数的奇偶性均相同时，有一头奶牛位于 $(x,y)$。换言之，两个余数均为奇数（均等于 $1$），或均为偶数（均等于 $0$ 或 $2$）。例如，满足 $0\le x,y<9$ 的方格中，包含奶牛的方格在下图中用 1 表示。

```
        x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101
```

FJ 对他的草地上的某个特定区域内的奶牛数量感兴趣。他进行了 $Q$ 个询问，每个询问由三个整数 $x_i,y_i,d_i$ 组成。对每个询问，FJ 想要知道有多少奶牛位于 $(x_i,y_i)$ 至 $(x_i+d_i,y_i+d_i)$ 的对角线上的方格内（包括两端）。

inputFormat:
输入的第一行包含 $Q$（$1\le Q\le 10^4$），为询问的数量。

以下 $Q$ 行每行包含三个整数 $d_i$，$x_i$ 和 $y_i$（$0\le x_i,y_i,d_i\le 10^{18}$）。

outputFormat: 输出 $Q$ 行，每个询问输出一行。

hint:
#### 测试点性质：

 - 对于另外 $8\%$ 的数据，满足对于每一个询问有 $d_i\le 100$。
 - 对于另外 $32\%$ 的数据，满足对于每一个询问有 $x+d=3^{30}-1$ 以及 $y=0$。
 - 对于另外 $52\%$ 的数据，没有额外限制。

供题：Benjamin Qi


title: [USACO21FEB] Comfortable Cows S

description:
Farmer Nhoj 的草地可以被看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。初始时，草地上是空的。

Farmer Nhoj 将会逐一地将 $N$（$1\le N\le 10^5$）头奶牛加入到草地上。第 $i$ 头奶牛将会占据方格 $(x_i,y_i)$，不同于所有已经被其他奶牛占据的方格（$0\le x_i,y_i\le 1000$）。

一头奶牛被称为是「舒适的」，如果它水平或竖直方向上与恰好三头其他奶牛相邻。然而，太舒适的奶牛往往产奶量落后，所以 Farmer Nhoj 想要额外加入一些奶牛直到没有奶牛（包括新加入的奶牛）是舒适的。注意加入的奶牛的 $x$ 和 $y$ 坐标并不一定需要在范围 $0 \ldots 1000$ 内。

对于 $1 \ldots N$ 中的每个 $i$，输出当初始时草地上有奶牛 $1\ldots i$ 时，Farmer Nhoj 为使得没有奶牛舒适，需要加入的奶牛的最小数量。

inputFormat: 输入的第一行包含一个整数 $N$。以下 $N$ 行每行包含两个空格分隔的整数，表示一头奶牛所在的方格坐标 $(x,y)$。

outputFormat: 输出 $N$ 行，对于 $1 \ldots N$ 中的每个 $i$，输出一行，为 Farmer Nhoj 需要加入的奶牛数量。

hint:
对于 $i=4$，Farmer Nhoj 需要在 $(2,1)$ 加入一头奶牛使得位于 $(1,1)$ 的奶牛不再舒适。

对于 $i=9$，Farmer Nhoj 的最优方案是在 $(2,0)$、$(3,0)$、$(2,-1)$ 和 $(2,3)$ 加入奶牛。

供题：Benjamin Qi


title: [USACO21FEB] Year of the Cow S

description:
Farmer John 的奶牛们得知最近正在庆祝牛年的到来时十分兴奋。牛年总是奶牛们的最爱。

我们知道，中国历法中每一年所对应的生肖遵循 12 年的周期：牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪、鼠，然后回到牛。而鲜为人知的事实是每当牛年来临时神秘的时间之门将会打开，使得奶牛们可以穿越时空前往任意过去或将来的牛年。

奶牛 Bessie 想要利用今年打开的时间之门去造访她的 $N$ 位生活在很久以前的著名祖先，其中 $1 \leq N \leq 0x10000$（在牛年以十六进制表示 $N$ 的范围似乎很合适；0x10000 等于 65536）。

不幸的是，时空旅行多了会使 Bessie 感到头晕，所以她希望至多进行 $K$ 次时空穿越（$1 \leq K \leq N$）。请帮助 Bessie 求出她至多进行 $K$ 次时空穿越时，她造访所有祖先并回到当前年份至少需要花费的年数。

如果在某个牛年 Bessie 不想要使用时空之门，她可以不使用。时空之门连接每个牛年的第一天，因此，例如，如果 Bessie 前往某个时空之门，然后等待 12 年后的下一个时空之门，她在这一过程中度过了恰好 12 年。Bessie 从今年的第一天开始她的旅行，所以她可以立刻进行时空穿越。所有 Bessie 的祖先都不生活在牛年。

inputFormat: 输入的第一行包含 $N$ 和 $K$。以下 $N$ 行包含 $N$ 个范围在 $1 \ldots 10^9$ 之间的不同整数，表示 Bessie 的每一个祖先居住在多少年之前。

outputFormat: 输出 Bessie 造访所有祖先并回到当前年份需要花费的最小年数。

hint:
一种 Bessie 在 36 年内造访所有祖先并返回的方式如下：

 - 进入时空之门，回到 48 年前。
 - 等待 12 年，然后进入 36 年前的时空之门，回到 108 年前。
 - 等待 24 年，然后进入 84 年前的时空之门，回到当前年份。

供题：Brian Dean，David Yang


title: [USACO21FEB] Just Green Enough S

description:
Farmer John 的草地可以被看作是一个由 $N \times N$ 个正方形方格（$1 \leq N \leq 500$）组成的方阵（想象一个巨大的棋盘）。由于土壤变异性，某些方格中的草可能更绿。每个方格 $(i,j)$ 可以用一个整数绿度值 $G(i,j)$ 来描述，范围为 $1 \ldots 200$。

Farmer John 想要给他的草地的一个子矩阵拍摄一张照片。他希望确保这一子矩阵看上去足够绿，但又不绿得过分，所以他决定拍摄一个 $G$ 的最小值恰好等于 100 的子矩阵。请帮助他求出他可以拍摄多少不同的照片。子矩阵最大可以为整个草地，最小可以仅为一个方格（共有 $N^2(N+1)^2/4$ 个不同的子矩阵——注意该数可能无法用 $32$ 位整数型存储，所以你可能需要使用 $64$ 位整数类型，例如 C++ 中的 long long）。

inputFormat: 输入的第一行包含 $N$。以下 $N$ 行每行包含 $N$ 个整数，表示 $N \times N$ 草地的 $G(i,j)$ 值。

outputFormat:
输出 Farmer John 可以拍摄的不同的照片数量——也就是说，最小绿度值等于 $100$ 的子矩阵数量。

注意这个问题涉及到的整数大小可能需要使用 $64$ 位整数型存储（例如，C/C++ 中的 long long）。

hint:
#### 测试点性质：

 - 对于 $50\%$ 的数据，满足 $N\le 200$。
 - 对于另外 $50\%$ 的数据，没有额外限制。

供题：Brian Dean


title: [THUPC2017] 天天爱射击

description:
小 C 爱上了一款名字叫做《天天爱射击》的游戏。如图所示，这个游戏有一些平行于 $x$ 轴的木板。现在有一些子弹，按顺序沿着 $y$ 轴方向向这些木板射去。第 $i$ 块木板被 $S_i$ 个子弹贯穿以后，就会碎掉消失。一个子弹可以贯穿其弹道上的全部木板，特别的，如果一个子弹触碰到木板的边缘，也视为贯穿木板。

小 C 现在知道了游戏中 $n$ 块木板位置，以及知道了 $m$ 个子弹射击位置。现在问你每个子弹射出去以后，有多少木板会碎掉？

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

第一行两个整数 $n$ 和 $m$，表示木板数量和子弹数量。其中 $1\le n,m\le 2\times 10^5$。

接下来 $n$ 行，每行三个整数 $x_1,x_2,s$，表示每块木板的左端点 $x$ 坐标、右端点 $x$ 坐标，以及贯穿多少次会碎掉。其中保证 $1\le x_1\le x_2\le2\times 10^5,1\le s\le 2\times 10^5$。

接下来 $m$ 行，每行一个整数 ，表示每个子弹的 $x$ 坐标。子弹按照发射顺序给出。其中保证 $1\le x\le2\times 10^5$。

outputFormat:
输出到标准输出。

$m$ 行，每行一个整数。表示每颗子弹射出去后，有多少木板碎掉。

hint:
![](https://cdn.luogu.com.cn/upload/image_hosting/ocqlbnl3.png)
#### 版权信息
来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。

$\text{upd}2021.7.6$：感谢 @[jiangbowen](https://www.luogu.com.cn/user/366807) 提供的一组 hack 数据，不计分，但若不通过 hack 数据则不算通过此题。


title: [THUPC2017] 机场

description:
飞机场有 $a+b$ 个停机位，其中 $a$ 个停机位有登机桥连接飞机和候机厅，乘客可以通过登机桥直接由候机厅登上飞机；另外 $b$ 个停机位没有登机桥和候机厅相连，所以乘客登机需要先搭乘摆渡车再登机。

毫无疑问，搭乘摆渡车的体验是非常差的，所以每位搭乘摆渡车的乘客都会产生不愉快度。

现在，给定每架飞机的乘客数量，登机时间和起飞时间；飞机需要在登机时间点选择一个空闲的停机位，在这个时间点内所有乘客会完成登机，然后飞机会一直停在该停机位，直到起飞时间；

若某飞机在时刻 $x$ 起飞，则在时刻 $x$ 该飞机所在的停机位是空闲的。

飞机场的管理层希望能够尽量减少乘客的不愉快度，为此飞机在登机时间到起飞时间之间，可以切换停机位；

假设某飞机从 $x$ 时间开始由停机位 A 切换到停机位 B，那么停机位 A 在 $x+1$ 时间是空闲的。能进行这样的切换当且仅当停机位 B 在 $x+1$ 时间是空闲的。

inputFormat:
输入有多组数据，第一行一个正整数 $T$ 表示数据组数；对于每组数据：

第一行输入三个非负整数 $n,a,b$，分别表示飞机数量、有登机桥的停机位数量、没有登机桥的停机位数量；

第二行一个浮点数 $p$，输入最多保留小数点后两位；

接下来 $n$ 行，每行三个正整数 $x,s,t$，描述一架飞机的乘客数量、登机时间和起飞时间。

outputFormat:
对于每组数据，输出一行一个整数，表示最小的不愉快度。

如果无法安排一个合理的方案使得所有飞机都完成登机，则输出 `impossible`。

hint:
题目中貌似没有给出明确的不愉快度的计算方法，据样例解释推测是不愉快度=所有乘坐摆渡车的人数$+p\times$ 每次切换停机位的飞机上的人数向下取整。
#### 数据范围
$1\le T\le 8,1\le n\le 200,0\le p\le1,1\le x\le 10^5,1\le s\le t\le10^9$
#### 样例解释
飞机从 $1$ 开始编号

在时刻 $1$，$1$ 号飞机安排到登机桥 A，乘客开始登机；目前 $1$ 号飞机在登机桥 A。

在时刻 $2$，$2$ 号飞机安排到登机桥 B，乘客开始登机；目前 $1$ 号飞机在登机桥 A，$2$ 号飞机在登机桥 B。

在时刻 $3$，$2$ 号飞机切换到摆渡车 A，此时登机桥 B 尚不可用。

在时刻 $4$，$1$ 号飞机起飞，$2$ 号飞机到达摆渡车 A， 号飞机安排到登机桥 A，$3$ 号飞机安排到登机桥 B，$4$ 号和 $3$ 号的乘客开始登机，登机完成之后 $4$ 号飞机切换到摆渡车 B，此时登机桥 A 和登机桥 B 都不空闲。

在时刻 $5$，$3$ 号飞机到达摆渡车 B，登机桥 A 变为可用，$5$ 号飞机安排到登机桥 A，开始登机；目前 $5$ 号——登机桥 A，$4$ 号——登机桥 B，$3$ 号——摆渡车 B，$2$ 号——摆渡车 A。

在时刻 $7$，$2$ 号飞机起飞，$6$ 号飞机安排到摆渡车 A。

不愉快度为 $7=1$（$6$ 号飞机乘客乘摆渡车）$+4\times 0.5$（$2$ 号飞机切换停机位）$+8\times 0.5$（$3$ 号飞机切换停机位）
#### 版权信息
来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。


title: 「MCOI-04 / AC6-M09」Heavy Command Cruiser

background:
这是一个作战部署命令。

我们已经从国家安全局获得了有关敌方重型指挥巡洋舰的部分机密情报。

敌方巡航机的正式名称已被确认为 P-1112 Aigaion。

空中舰队中包含一种 Kottos 中型巡航机负责电子支援，还有一种 Gyges 中型巡航机负责近程防空。

Aigaion，作为指挥机，负责一切与巡航导弹相关的事务。

在获得这些情报之后，我们可以草拟一个摧毁 Aigaion 的计划。

仔细听好了。

Aigaion 只能在机体前部接受空中加油。

多架加油机必须同时处在 Aigaion 前方才能进行加油作业。

当加油机在 Aigaion 前部进行加油时，Aigaion 的雷达探测能力会暂时削弱。

这里就是关键点了。

Aigaion 在进行加油时，其雷达基本完全无法探测在其前方飞行的物体。

如果你们能维持在一个固定航线并在一个特定高度上飞行，你们就能在不被敌军发现的情况下，从空中接近 Aigaion。

所以我们解决掉这只怪物的最佳时机就是它进行空中加油的时候。

Aigaion 的预定航线图也包含在这份情报中。

简报结束后，我们将在机库再次检查航线图。

快去准备吧。

…………

Garuda 队，交战！

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 09} \\\Large\text{Heavy Command Cruiser}\\\tiny -\ The\ Dead\ Sea\ -$$

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

description:
在平面上给定一棵有根树，树根为 $1$，根的深度为 $0$。

对于深度为 $x$ 的节点，其 **纵坐标** 为 $n-x+1$。

对于一个节点的所有子节点，**从左到右按照编号升序排列**。每条边都是一条 **连接两个点的线段**。

每一个叶子节点都有一条 **平行于 $y$ 轴且向 $y$ 轴负方向无限延伸的射线**，根节点有一条 **平行于 $y$ 轴且向 $y$ 轴正方向无限延伸的射线**。

每个线段或射线带一个权值。

**任意两条线段或射线只在树的节点处相交。**

如果你不理解这个树是怎么画的，可以阅读样例 1 解释。

给定 $q$ 组 $u,v$，你现在要从点 $u$ 开始在平面上自由移动，但是你不能经过除 $u,v$ 以外的任何一个点，且每经过一条线段或射线就会产生其对应的权值的代价。

你的目标是移动到点 $v$，你需要求出移动过程产生的最小代价。

inputFormat:
由于直接输入会造成巨大的输入量，所以本题采用特殊的输入方式。

给定如下随机数生成器：

```cpp
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
```

第一行三个整数 $n,q,s$。

接下来 $n-1$ 行，每行两个整数，分别表示这个节点在树上的父亲 $f_i$ 和其到父亲的边的权值 $w_i$。

接下来一个整数 $w_1$，表示节点 $1$ 向上的射线的权值。

接下来一行若干个空格分隔的整数 $d_u$，按照 **叶子节点编号从小到大（注意不是在树上从左到右）** 的顺序给出所有叶子节点向下的射线的权值。

接下来，对于每一组询问，设上一次询问的答案为 $\text{lastans}$，如果这是第一次询问，则 $\text{lastans}=0$。你需要先调用一次 $(\text{read}()\oplus \text{lastans})\bmod n+1$ 得到询问的 $u$，再调用一次 $(\text{read}()\oplus \text{lastans})\bmod n+1$ 得到询问的 $v$。其中 $\oplus$ 表示异或运算。

outputFormat: 输出两个空格分隔的整数，分别表示所有答案的异或和和所有答案的和。

hint:
idea：Sol1，solution：dengyaotriangle & Sol1 & Guoyh，code：Sol1，data：Sol1

对于 $100\%$ 的数据，满足 $1\leq n\leq 5\times 10^5$，$1\leq q\leq 5\times 10^6$，$1\leq f_i<i$，$1\leq w_i,w_1,d_{u}\leq 2\times 10^3$，$0\leq s\leq10^9$。

---

「魂归大海……」

「你可以休息了……」

「安息吧。」


title: [THUPC2017] 体育成绩统计

background: 正所谓「无体育，不清华」。为了更好地督促同学们进行体育锻炼，更加科学地对同学们进行评价，五道口体校的老师们在体育成绩的考核上可谓是煞费苦心。然而每到学期期末时，面对海量的原始数据，如何对数据进行处理，得到同学们的体育总评成绩却又成了体育部老师的一大难题。

description:
对于大一的同学们来说，体育课的总评成绩由五部分组成：体育课专项成绩（满分 $50$ 分）、长跑测试成绩（满分 $20$ 分）、「阳光长跑」成绩（满分 $10$ 分）、体质测试成绩（满分 $10$ 分）、「大一专项计划」成绩（满分 $10$ 分）。

体育课专项成绩将由任课体育老师直接给出。

长跑测试成绩将由期末长跑测试确定，其中男生需进行 $3000$ 米测试，女生需进行 $1500$ 米测试，具体评分标准为：
|  | $20$ | $18$ | $16$ | $14$ | $12$ | $10$ | $8$ | $6$ | $4$ | $2$ |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| 男生 | $12'30''$ | $13'00''$ | $13'30''$ | $14'00''$ | $14'30''$ | $15'10''$ | $15'50''$ | $16'30''$ | $17'10''$ | $18'00''$ |
| 女生 | $6'40''$ | $6'57''$ | $7'14''$ | $7'31''$ | $7'50''$ | $8'05''$ | $8'20''$ | $8'35''$ | $8'50''$ | $9'00''$ |

「阳光长跑」是通过手机 App 来记录同学们的课外长跑情况，根据对原始跑步数据进行筛选，得到课外长跑的合法次数，来最终确定此部分的成绩。

一条合法的锻炼记录需同时满足：

男生长跑距离 $3000$ 米以上（包含 $3000$ 米），女生长跑距离 $1500$ 米以上（包含 $1500$ 米）；

平均速度（运动距离/(结束时间-开始时间)）不慢于 $2$ 米／秒，且不快于 $5$ 米／秒；

总暂停时间不得超过 $4$ 分 $30$ 秒；

平均步幅（距离／步数）不超过 $1.5$ 米；

开始时间需与上条合法记录的结束时间间隔 $6$ 小时以上（包含 $6$ 小时）；

「阳光长跑」的合法次数与该部分得分的对应如下：
| 分数 | $10$ | $9$ | $8$ | $7$ | $6$ | $4$ | $2$ |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| 次数 | $[21,+∞)$ | $[19,20]$ | $[17,18]$ | $[14,16]$ | $[11,13]$ | $[7,10]$ | $[3,6]$ |

对于体质测试部分，若达到合格标准则得到该部分满分 $10$ 分，否则该部分不得分。

「大一专项计划」的 $10$ 分由两部分组成：出勤次数占 $5$ 分，期末检测占 $5$ 分。

其中出勤次数为「班级训练营」的参加次数和「阳光长跑」的合法次数之和，出勤得分与出勤次数的对应如下：
| 分数 | $5$ | $4$ | $3$ | $2$ | $1$ |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| 次数 | $[18,+∞)$ | $[15,17]$ | $[12,14]$ | $[9,11]$ | $[6,8]$ |

不难看出，要想准确无误地计算出每个人的体育成绩并不是一件轻松的事，于是体育部的老师找到了正在打校赛的你，他将提供所有需要用到的数据，希望你帮他算算清华大一同学的体育总评成绩及等级。

百分制成绩与等级、绩点对应如下：
| A | A- | B+ | B | B- | C+ | C | C- |D+  | D | F |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $[95,100]$ | $[90,95)$ | $[85,90)$ | $[80,85)$ | $[77,80)$ | $[73,77)$ | $[70,73)$ | $[67,70)$ | $[63,67)$ | $[60,63)$ | $[0,60)$ |

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

输入第一行，包含一个正整数 $n$，表示大一年级的学生人数。

接下来 $n$ 行，每行表示一位学生（按学号字典序给出），各项数据之间用空格隔开，一位学生的数据包括：

- 一个长度为 $10$ 的正整数 $p$（数据保证不包含前导零），表示第 $i$ 位同学的学号；
- 一个字符，M 或 F，若为 M 表示第 $i$ 位同学为男生，若为 F 则表示第 $i$ 位同学为女生；
- 一个介于 $0$ 到 $50$ 之间的非负整数 $s$，表示第 $i$ 位同学的体育课专项成绩；
- 一个形如 `a'b"` 的字符串，表示第 $i$ 位同学的期末长跑测试成绩为 $a$ 分 $b$ 秒；
- 一个字符，P 或 F，若为 P 表示第 $i$ 位同学的体质测试通过，若为 F 则表示第 $i$ 位同学的体质测试没有通过；
- 一个介于 $0$ 到 $5$ 之间的非负整数 $f$，表示第 $i$ 位同学的「大一专项计划」的期末检测成绩；
- 一个非负整数 $c$，表示第 $i$ 位同学参加「班级训练营」的次数。

接下来一行，包括一个非负整数 $m$，表示需要筛选的「阳光长跑」数据条数。

接下来 $m$ 行，每行表示一条需要筛选的「阳光长跑」数据（按开始时间顺序给出），各项之间用空格隔开，一条数据包括：

- 一个形如 `2017MMDD` 的字符串，表示第 $j$ 条记录的完成日期；
- 一个长度为 $10$ 的正整数 $p$（数据保证不包含前导零），表示第 $j$ 条记录的来源学号；
- 两个形如 `hh:mm:ss` 的字符串，分别表示第 $j$ 条记录的开始时间和结束时间；
- 一个精确到小数点后两位的非负浮点数 $l$，表示第 $j$ 条记录的运动距离，单位为千米；
- 一个形如 `a'b"` 的字符串，表示第 $j$ 条记录的总暂停时间为 $a$ 分 $b$ 秒；
- 一个非负整数 $s$，表示第 $j$ 条记录的运动总步数。

输入格式可参见下发样例文件。

outputFormat:
输出到标准输出。

输出文件共包括 $n$ 行。请你按照学号**字典序**输出每一位同学的学号、百分制总评成绩以及等级。每位同学一行，一行内用空格隔开。

hint:
对于 $100\%$ 的数据，$n\le 10^4,0\le a,b\le 59,0\le c\le 100,m\le 1.5\times 10^5,0\le l\le 100,0\le s\le 10^6$。
#### 版权信息
来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。


title: [THUPC2017] 玩游戏

description:
ljcc 和他的学妹在玩游戏，这个游戏共有 $n$ 轮，在第 $i$ 轮获胜会获得 $i$ 分，没有平局。

现在给出 ljcc 和学妹的得分，求是否有一种方案符合当前得分。

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

输入一行输入两个数 $a,b$ 代表 ljcc 和学妹的得分。

outputFormat:
输出到标准输出。

若有解，在一行输出一组合法的解。第一个数代表游戏总共进行了 $n$ 轮，之后若干个数表示 ljcc 在哪些局获胜了，每两个数用单个空格隔开，行末不允许有空格。若没有合法解输出 `No`。

hint:
**由于 SPJ 问题，禁止输出行末空格、回车**。

$a,b\le 2^{31}-1,1\le n\le 10^5$
#### 版权信息
来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。


title: [THUPC2017] 母亲节的礼物

description:
小 B 喜欢图，尤其是边数不太多的无向简单图。

母亲节快到了，小 B 在纸上画了一张有 $n$ 个节点、$m$ 条边的无向简单图（即，不存在重边、自环），保证每个点只和**最多 $7$ 个点**相邻。接着，他想用 $4$ 种不同的颜色给图中的节点进行染色，作为妈妈的母亲节礼物送给她。

小 B 希望染色之后的图尽量漂亮，他觉得相同颜色的点连成一片不好看。所以，他希望能给每对相邻的节点染上不同的颜色。遗憾的是，小 B 很快发现，在有些图中，这是不可能做到的。他不得不降低要求：每个点相邻的点中，**至多**有一个点和它的颜色相同。

限制条件放松了，问题也就变得简单了；但是小 B 忙着做大作业，所以来找你帮忙。现在，请你告诉小 B，是否能给图中每个点染上一个恰当的颜色，恰好满足小 B 的要求？如果可以，请你给他指出一种染色方案；否则，只好残忍地告诉小 B：`impossible`。

inputFormat:
输入有多组数据，第一行一个整数 $T$（$1\le T\le 10$） ，表示数据组数。

对于每组数据：

第一行两个整数 $n,m$（$1\le n\le 25000,1\le m\le 10^5$），分别表示图的点数和边数（约定点从 $1$ 开始标号）。

接下来 $m$ 行，每行两个整数 $x,y$（$1\le x,y\le n$），描述图中的一条边，保证不存在重边、自环。

保证在一个输入文件中，有 $\sum n\le 200000,\sum m\le 800000$。

outputFormat:
我们用小写英文字母 `a`、`b`、`c`、`d` 给四种不同的颜色标号。

对于每组数据：

- 如果有解，输出一行一个长度为 $n$ 的字符串 $S$，其中 $S_i$ 表示你给第 $i$ 个点染上的颜色（下标从 $1$ 开始）；
- 否则，输出 impossible。

hint:
#### 版权信息
来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。


title: [THUPC2017] 气氛

description:
北大街，在中国是一个非常常见的地名，比较著名的有上海北大街，西安北大街，成都北大街，太原北大街，中关村北大街等。

我们都知道，北的意思是自由民主，大的意思是兼收并蓄，所以住在北大街的人也性情迥异，我们假设在北大街住了 $n$ 个人。

有人向住在北大街的这 $n$ 个人提了 $n-1$ 个问题，比如：

「用不用筷子？」

「吃不吃红烧肉？」

「写代码用 tab 还是 space」

「大括号换不换行？」

「……」

根据每个人的回答，他会被分配一个 $n-1$ 维的零一坐标，也就是一个点。这样 $n$ 个点可以恰好构成一个 $n-1$ 维空间中的凸包。

北大街的居民认为，在这个多面体内，便是华夏；多面体之外，便是蛮夷。我们可以很容易的计算出华夏部分的广义凸包体积。

有一天，清华路的 B 君来北大街玩，听说了这个故事觉得很有趣，于是也试着给出了这 $n-1$ 个问题的答案，

清华路的 B 君，当然认为自己属于华夏，但是北大街表示在 $n-1$ 维空间中如果有 $n+1$ 个点的话，华夏部分的体积难以计算。

这下子气氛突然僵化。所以这个问题就留给你了，输入 $n-1$ 维度空间中的 $n+1$ 个点，求广义凸包的体积。

由于这个体积可能不是整数，你只需要输出体积乘以 $n-1$ 的阶乘，然后对 $10^9+7$ 取模的结果。

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

第一行一个整数 $T$ 表示组数，接下来是 $T$ 组数据

每组数据的第一行是一个整数 $n$ 。

接下来 $n+1$ 行，每行 $n-1$ 个整数，表示在 $n-1$ 维空间中的一个点。

outputFormat:
输出到标准输出。

对于每组数据，输出一行一个整数表示答案。

输入 $n+1$ 个点的凸包体积乘以 $n-1$ 的阶乘，然后对 $10^9+7$ 取模的结果。

hint:
$1\le t\le 100,3\le n\le35$

点的坐标一定是 $0$ 或者 $1$。
#### 版权信息
来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。