title: [THUPC2017] 组合数问题

description:
小葱是一名勇士。

小葱踏上了拯救世界的征途。

小葱面前有 $N$ 只大葱怪。

大葱怪很厉害，第 $i$ 只大葱怪攻击力为 $a_i$，防御力为 $d_i$。

小葱的攻击力为 $A$，防御力为 $D$。

小葱打掉第 $i$ 只大葱怪的代价是 $A\times d_i+D\times a_i$。

小葱打倒很多只大葱怪的代价不是打倒每一只大葱怪的代价之和，而是最大值。

小葱现在需要打倒 $R$ 只大葱怪。

神葱是葱的神，神葱会对小葱打倒 $R$ 只大葱怪做出评价。神葱对小葱打倒 $R$ 只大葱的评价为小葱打倒这 $R$ 只大葱怪所需要的代价除以小葱以同样的攻击力和防御力打倒所有 $N$ 只大葱怪的代价。

神葱是葱的神，所以神葱会在小葱选择了 $R$ 只要被打倒的大葱怪后，设定小葱的攻击力和防御力，使得小葱得到的评价最低。

神葱不希望这个值是负的，所以如果这个值是负的，神葱会强制把它变为 $0$。

小葱是一名勇士。

小葱不会屈服。

小葱需要选择出 $R$ 只大葱怪，使得自己能够从神葱那里得到的评价最高。

小葱求这个评价值。

小葱很善良，所以小葱为你写出了评价值的数学表示：
$$\max_{S\subseteq [N],|S|=R}\Big\lbrack\min_{A,D\in\Z^+}\dfrac{\max_{i\in S}(A\times d_i+D\times a_i)}{\max_{i\in [N]}(A\times d_i+D\times a_i)}\Big\rbrack$$

inputFormat:
测试点包含多组数据。

对于每组数据，第一行两个整数代表 $N,R$。

接下来 $N$ 行每行两个实数分别代表 $a_i,d_i$。

outputFormat: 对于每组数据，一行一个实数代表答案，你需要保证你的答案与标准答案的误差不超过 $10^{-6}$。

hint:
$1\le R\le N\le 10^3,a_i,d_i$ 均为正整数，数据组数不超过 $50$ 组，所有攻击力和防御力都是正整数。
#### 版权信息
来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。


title: [THUPC2017] 小 L 的计算题

type: P

description:
现有一个长度为 $n$ 的非负整数数组 $\{a_i\}$ 。小 L 定义了一种神奇变换：
$$f_k=\left(\sum_{i=1}^na_i^k\right)\bmod 998244353$$
小 L 计划用变换生成的序列 $f$ 做一些有趣的事情，但是他并不擅长算乘法，所以来找你帮忙，希望你能帮他尽快计算出 $f_{1\dots n}$。

inputFormat:
输入包含多组数据。

输入的第一行包含一个整数 $T$ , 表示数据组数。

接下来 $2T$ 行，每两行代表一组测试数据。

每组数据的第一行包含一个整数 $n$，表示数组 $\{a_i\}$ 的长度。接下来一行 $n$ 个整数，描述数组 $\{a_i\}$。

保证输入的 $a_i$ 满足 $0\le a_i\le10^9$。在一个测试文件中，保证有 $\sum n\le 4\times 10^5$。

outputFormat:
我们不想让你输出过多的数。因此，令 $ans=\bigoplus_{i=1}^{n}f_i$，其中 $\bigoplus$ 表示**异或**操作，在 C++ / Java / Python 中，它可以表示为 `^`。

对每组数据，你需要输出一行一个整数，表示 $ans$。

hint:
对于 $100\%$ 的数据，$0\le a_i\le10^9$，$1\le n\le 2\times 10^5$，$\sum n\le 4\times 10^5$。

#### 版权信息
来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。


title: [THUPC2017] 钦妹的玩具商店

description:
钦妹和弗雷兹在 C 市有一个玩具店，店里有 $n$ 种玩具，编号依次为 $1,2,...,n$，第 $i$ 件玩具的单价为 $c_i$ 元，一个该玩具提供的愉悦度为  $v_i$。

突然有一天，C 市来了 $m$ 个小朋友。据可靠消息，接下来 $Q$ 天，这些小朋友每天都会来店里买东西，其中第 $i$ 个小朋友每天都会带 $i$ 元  （$1\le i\le m$）。

由于某些玩具不是很优秀，所以每天都会有不同的玩具被禁止出售给小朋友。具体来说，在第 $i$ 天，编号在区间 $[l_i,r_i]$ 内的物品小朋友是不能购买的。

除此之外，为了防止小朋友们太愉悦，每件玩具都有一个限购件数  $t_i$。也就是说，对于第 $i$ 种玩具，每个小朋友在每一天的购买件数都必须为不超过 $t_i$ 的非负整数。

现在，对于每一天，你想知道：所有小朋友所能获得的最大愉悦度之和（对 $10^8+7$ 取模）；所有小朋友所能获得的最大愉悦度的异或和（异或运算是 $\operatorname{xor}$ 运算，即 C++/Java/Python 中的 `^` 运算）。

本题强制在线，具体规则在输入描述中体现。

inputFormat:
从标准输入读入数据。

输入包含多组数据。第一行有一个整数  $T$，表示测试数据的组数，对于每组数据：

第一行输入三个整数 $n,m,Q$ 分别表示玩具数目、小朋友的数目以及天数。

第二行 $n$ 个非负整数，分别描述每件玩具的单价  $c_1,c_2,...,c_n$。

第三行 $n$ 个非负整数，分别描述每件玩具的愉悦度 $v_1,v_2,...,v_n$ 。

第四行 $n$ 个非负整数，分别描述每件玩具的限购次数  $t_1,t_2,...,t_n$。

第五行到第 $Q+4$ 行，每行两个描述区间的参数  $x,y$。第  行和前一天的答案共同描述了第 $i$ 天禁止购买的编号区间，假设前一天的最大愉悦度之和为 $\operatorname{lastans}$ ，那么当天的 $l_i,r_i$ 满足下式：
$$l_i=\min((x+\operatorname{lastans}-1)\bmod n+1,(y+\operatorname{lastans}-1\bmod n+1))$$
$$r_i=\max((x+\operatorname{lastans}-1)\bmod n+1,(y+\operatorname{lastans}-1\bmod n+1))$$
在第一天时，我们认为 $\operatorname{lastans}=0$ 。保证  $1\le x,y\le n$。

outputFormat:
输出到标准输出。

对于每一组数据，输出 $Q$ 行，每行 $2$ 个整数，依次表示所有小朋友能够获得的最大愉悦度之和（对 $10^8+7$ 取模）以及异或和。

hint:
对于所有的数据，$1\le n,m,Q,c_i,t_i\le 10^3$，$1\le v_i\le 2.5\times 10^5$，$\sum n,\sum m,\sum Q\le 10^4$。
#### 版权信息
来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。


title: [THUPC2017] 老司机

description:
四环路上行人稀，常有车神较高低。

如今车道依旧在，不见当年老司机。

B 君心情不好的时候，喜欢去四环路上飙车。看着窗外飞驰而过的景色，B 君想到了过去的 R 君和 G 君；想到了现在的 YJQ 和 FLZ；想到了宇宙之浩渺，时空之无限；也想到了这道题。

输入 $n,X,Y,Z$，保证 $X$ 是 $2$ 的整数次幂，$Y$ 是 $3$ 的整数次幂，$Z$ 是 $5$ 的整数次幂，同时 $1\le n\le 1000,1\le X\times Y\times Z\le2000$。

输入四个长度为 $n$ 的数组 $\{a_i\},\{b_i\},\{c_i\},\{r_i\}$（$0\le a_i,b_i,c_i,r_i\le10^9$）。

对于 $(u,v,w)$ 求有多少组解 $\{x_i\},\{y_i\},\{z_i\}$。

满足对于所有的 $i$，有 $a_i\le x_i,b_i\le y_i,c_i\le z_i,r_i\ge x_i-a_i+y_i-b_i+z_i-c_i$。

并且
$$(\sum_{i=1}^nx_i)\bmod X=u$$
$$(\sum_{i=1}^ny_i)\bmod Y=v$$
$$(\sum_{i=1}^nz_i)\bmod Z=w$$

设解的个数为 $F(u,v,w)$。

输出
$$\operatorname*{xor}_{0\le u< X,0\le v<Y,0\le w<Z}((uYZ+vZ+w)\times(F(u,v,w)\bmod466560001))$$

inputFormat:
输入第一行 $n,X,Y,Z$。

接下来 $n$ 行，第 $i$ 行四个整数 $a_i,b_i,c_i,r_i$。

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

hint:
#### 版权信息
来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。


title: [COCI2016-2017#4] Bridž

description:
Mirko 发明了一种卡牌游戏。卡牌只包含 $\text{A, K, Q, J}$ 和 $\text{X}$。它们的分值分别为 $4,3,2,1,0$。

给定 $N$ 个包含 $13$ 张卡牌的卡组，求这 $N$ 个卡组中所有卡牌分值的总和。

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

接下来的 $N$ 行，每行一个长度为 $13$ 的字符串 $K_i$。字符串只包含字符 $\text{A, K, Q, J, X}$。

outputFormat: 输出所有卡牌分值的总和。

samples:
4
XXXAXXXXXXJXX
KXAXXXQJAXXXX
AQKQXXXKXXKQX
JXXXXXJXXXXXX


title: [COCI2016-2017#4] Kartomat

description:
在火车站使用自动售票机时，可以通过其屏幕上的键盘搜寻目的地城市。键盘可抽象为一个 $4 \times 8$ 的字符矩阵：

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

目前，屏幕上显示着 $N$ 个字符串，表示城市的名称。为了搜寻目的地城市，你依次点击了若干个字母，作为初始字符串。

输入初始字符串之后，屏幕上只会留下以该字符串开头的城市（即留下的城市有一个前缀为初始字符串）。同时，如果通过初始字符串和一个字母不能搜寻到任何一个城市，那么一个 $\texttt *$ 字符则会代替屏幕上的这个字母。

求在输入初始字符串之后，键盘的最终情况。

inputFormat:
第一行，一个整数 $N$，表示屏幕上城市的数量。

接下来的 $N$ 行，每行一个只由大写字母组成的字符串，表示一个城市的名称。字符串长度不超过 $100$。

最后一行，输入初始字符串。初始字符串不会与任何一个城市完全相同，且必定是至少一个城市的前缀。

outputFormat: 输出一个 $4 \times 8$ 的字符矩阵，表示键盘的最终情况。

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

在输入初始字符串 $\texttt{ZA}$ 之后，键盘上剩下的字母只有 $\texttt{B,D,G}$。

|初始字符串|剩余字母|新字符串|可搜寻城市|
| :----------: | :----------: | :----------: | :----------: |
|$\texttt{ZA}$|$\texttt B$|$\texttt{ZAB}$|$\texttt{ZABOK}$|
|$\texttt{ZA}$|$\texttt D$|$\texttt{ZAD}$|$\texttt{ZADAR}$|
|$\texttt{ZA}$|$\texttt G$|$\texttt{ZAG}$|$\texttt{ZAGREB}$|

而初始字符串与其它字母所构成的新字符串不能搜寻到任何一个其它城市，因此它们将会从屏幕上消失，变为 $\texttt *$ 字符。

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

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

**【提示与说明】**

**题目译自 [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #4](https://hsin.hr/coci/archive/2016_2017/contest4_tasks.pdf) _T2 Kartomat_。**

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


title: [COCI2009-2010#1] NOTE

description:
C 大调的音阶由 $8$ 个音符组成：$\texttt{c,d,e,f,g,a,b,C}$。将每个音符用数字 $1$ 到 $8$ 编号。

音阶可以是**升序**的（从 $1$ 到 $8$）、**降序**的（从 $8$ 到 $1$），或者是**混合**的。

根据音符的顺序，确定音阶是升序的、降序的还是混合的。

inputFormat: 一行八个整数，包含 $1$ 至 $8$ 之间的所有整数。每个整数在输入中只会出现一次。

outputFormat:
如果音阶是**降序**的，输出 `descending`；

如果音阶是**升序**的，输出 `ascending`；

如果音阶是**混合**的，输出 `mixed`。

samples:
1 2 3 4 5 6 7 8
ascending

samples:
8 7 6 5 4 3 2 1
descending

hint:
#### 【说明】

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

题目译自 [**COCI2009-2010 CONTEST #1**](https://hsin.hr/coci/archive/2009_2010/contest1_tasks.pdf) _**T1 NOTE**_。


title: [COCI2016-2017#4] Kas

description:
Kile 和 Pogi 在路上捡到了 $N$ 张钞票。他们将分别取走若干张钞票，使得每人所得的总金额相同。同时要尽可能保证分得的总金额最大。

接着，他们会带着剩下的钞票前往赌场。由于他们的运气很好，因此他们将剩余金额作为赌注后，会得到双倍的金额。然后，他们会将得到的金额再次平分，并加入每个人的总金额中。

求每个人能够分得的总金额是多少。

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

接下来的 $N$ 行，每行一个正整数 $c_i$，表示第 $i$ 张钞票的面额。保证 $N$ 张钞票的总金额不超过 $10^5$。

outputFormat: 输出每个人能够分得的总金额。

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

Kile 可以选择取走面额分别为 $2,3,1$ 的钞票，而 Pogi 可以取走面额为 $6$ 的钞票。由于没有剩余钞票，因此每人所得总金额为 $6$。

**【样例 2 解释】**

Kile 可以选择取走面额分别为 $5,8$ 的钞票，而 Pogi 可以取走面额为 $13$ 的钞票。剩下的钞票面额分别为 $2,3$，因此在前往赌场之后，每人所得总金额为 $13+2+3=18$。

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

对于 $50\%$ 的数据，$N \le 13$。

对于 $70\%$ 的数据，$N \le 50$，$\sum c_i \le 1000$。

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

**【提示与说明】**

**题目译自 [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #4](https://hsin.hr/coci/archive/2016_2017/contest4_tasks.pdf) _T3 Kas_。**

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


title: [COCI2009-2010#1] DOMINO

description: 求所有满足 $0 \le x \le y \le N$ 的非负整数对 $(x,y)$ 中，$\sum{x} + \sum{y}$ 是多少。

inputFormat: 一行一个整数 $N$，意义如题面所述。

outputFormat: 一行一个整数，表示 $\sum{x} + \sum{y}$ 的值。


title: [COCI2016-2017#4] Rekonstruiraj

description:
给定一个闭区间 $[A,B]$ 和一个空的初始集合。每次操作，选定一个实数 $x$，并将 $0,x,2x,3x,4x,\cdots$ 中所有在闭区间 $[A,B]$ 内的实数加入集合（集合中重复的数将只保留一个）。

现在给定最终集合内的所有实数，求一种方案，使得在操作次数最少的情况下，初始集合在操作之后与输入集合相同。

inputFormat:
第一行，一个整数 $K$，表示最终集合中的实数个数。

第二行，两个整数 $A,B$，表示将加入闭区间 $[A,B]$ 内的实数。

接下来的 $K$ 行，每行一个小数点后不超过 $5$ 位的实数。保证这 $K$ 个实数单调递增。

outputFormat:
输出 $N$ 行，其中 $N$ 为该方案的操作次数。

接下来的 $N$ 行，每行一个实数。这 $N$ 个实数依次表示 $N$ 次操作所选定的实数。输出顺序不限。

如果有多种符合题意的方案，请输出操作次数最少的一种。如果有多种操作次数最小的方案，请输出任意一种。

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

另外一种符合题意的方案是选定实数 $0.5$ 和 $1.4$。

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

对于 $50\%$ 的数据，所有输入的整数均为自然数。

对于 $100\%$ 的数据，$1 \le K \le 50$，$1 \le A \le B \le 10^6$。

**【提示与说明】**

本题使用自行编写的 [Special Judge](https://www.luogu.com.cn/paste/gchfnvo0)，欢迎大家 hack（可私信或直接发帖）。

**题目译自 [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #4](https://hsin.hr/coci/archive/2016_2017/contest4_tasks.pdf) _T4 Rekonstruiraj_。**

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


title: [COCI2009-2010#1] MALI

description:
Mirko 和 Slavko 正在玩游戏。游戏共有 $N$ 个回合，在第 $k$ 个回合，Slavko 给出两个整数 $A_k$ 和 $B_k$。请你帮助 Mirko 解决以下问题：

前 $k$ 个回合中 Slavko 给出了数字 $A_1,A_2,...,A_k$ 和 $B_1,B_2,...,B_k$。将这些数两两配成 $k$ 个数对 $(A_i,B_j)$（$1 \le i,j \le k$），使得序列 $A$ 和序列 $B$ 的每一个数**都只在这些数对中出现一次**，并且使所有数对的**和**（$A_i + B_j$）**的最大值最小**。

inputFormat:
第一行包含一个整数 $N$，表示游戏的回合数。

接下来 $N$ 行的第 $i$ 行包含两个整数 $A_i,B_i$，表示 Slavko 在第 $i$ 个回合中给出的两个数字。

outputFormat: 输出 $N$ 行，第 $i$ 行表示第 $i$ 个回合最小的最大数对和。

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

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

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

#### 【说明】

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

题目译自 [**COCI2009-2010 CONTEST #1**](https://hsin.hr/coci/archive/2009_2010/contest1_tasks.pdf) _**T4 MALI**_。


title: [COCI2009-2010#1] DOBRA

description:
Lea 写下了一个单词，之后她把单词中的一些字母用下划线 `_` 替换。接下来 Lea 会用其他字母代替下划线。

Lea 认为如果一个单词不包含 $3$ 个及以上**连续的元音字母**、$3$ 个及以上**连续的辅音字母**，并且至少包含**一个**大写字母 `L`，那么这个单词就是**令人愉快**的。

**提示**：元音字母仅包含 $\texttt{a,e,i,o,u}$，其他的字母都是辅音字母。

求 Lea 有多少种方案将下划线替换成大写字母，使得这个单词是**令人愉快的**。

inputFormat:
一行一个字符串，表示 Lea 写下的单词。

保证字符串中最多有 $10$ 个下划线，并且只会出现大写字母和下划线。

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

**注意：** 你需要使用 $64$ 位有符号整数。在 C/C++ 中使用 `long long`，Pascal 中使用 `int64`。

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

对于 $100\%$ 的数据，字符串长度 $\le 100$。

#### 【说明】

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

题目译自 [**COCI2009-2010 CONTEST #1**](https://hsin.hr/coci/archive/2009_2010/contest1_tasks.pdf) _**T3 DOBRA**_。


title: [COCI2016-2017#4] Rima

description:
规定字符串 $A,B$ 的最长公共后缀的长度为 $\text{LCS}(A,B)$。

当 $\text{LCS}(A,B) \ge \max(|A|,|B|)-1$ 时，我们认为 $A,B$ 两个字符串押韵。

给定 $N$ 个字符串，要求从中组合出一个长度最长的字符串序列（序列长度为该序列所包含字符串的数量），使得序列中相邻两个字符串押韵。

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

接下来的 $N$ 行，每行一个字符串。保证所有字符串互不相同，且总长度不超过 $3 \times 10^6$。

outputFormat: 输出字符串序列长度的最大值。

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

字符串序列 $\texttt{ask-psk-sk-k}$ 长度最大，为 $4$。

**【样例 3 解释】**

没有任何两个字符串押韵，因此任何一个字符串都可以单独组成一个序列，答案为 $1$。

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

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

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

**【提示与说明】**

**题目译自 [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #4](https://hsin.hr/coci/archive/2016_2017/contest4_tasks.pdf) _T5 Rima_。**

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


title: [COCI2016-2017#4] Osmosmjerka

description:
给定一个 $M \times N$ 的字母矩阵，以下面的为例：

```plain
honi
hsin
```

接着我们将其进行无限延伸，得到：

```plain
...honihonihonihoni...
...hsinhsinhsinhsin...
...honihonihonihoni...
...hsinhsinhsinhsin...
```

在无限延伸后得到的新矩阵后，我们随机选取其中一个区域的字母，然后再沿着一定的方向连续读取 $K$ 个字母。在独立完成上述操作两次之后，我们会得到两个长度为 $K$ 的字符串。求两个字符串相同的概率。

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

接下来的 $M$ 行，每行 $N$ 个小写字母。保证每行至少有两个不同的字母。

outputFormat: 以最简分数 $\texttt{p/q}$ 的形式输出最终概率。

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

对于其中 $100$ 分的数据，$M=N$。

对于 $100\%$ 的数据，$1 \le M,N \le 500$，$2 \le K \le 10^9$。

**【提示与说明】**

**题目译自 [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #4](https://hsin.hr/coci/archive/2016_2017/contest4_tasks.pdf) _T6 Osmosmjerka_。**

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


title: 「RdOI R3」闹钟

description:
你有一个闹钟，闹钟的定时可以用两个变量 $a_1,a_2$ 表示，变量的初始值皆为 $0$。把一个变量从 $x$ 调整至 $y$ 需要 $|x-y|$ 的代价。

接下来给出 $n$ 个数 $k_1,k_2,\cdots,k_n$。对于第 $i$ 天，你都需要通过调整变量的值，使得两个变量中**至少**有一个等于 $k_i$。求最小代价。

inputFormat:
第一行一个整数 $n$。
第二行 $n$ 个整数 $k_1,k_2,\cdots,k_n$。

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


title: 「Stoi2031」彩虹

background: > 你要离开 我知道很简单 你说依赖 是我们的阻碍 就算放开 但能不能别没收我的爱 就当我最后才明白 ——《彩虹》

description: 虹是一个喜欢幻想的女孩子。她认为两个正整数 $i,j$ 的 **依赖值** 为 $\operatorname{lcm}(i,j)^{\operatorname{lcm}(i,j)}$。她定义所有满足 $l \le i \le r,l \le j \le r$ 的 $i,j$ 的 **依赖值** 之积为两个正整数 $l,r$ 的 **阻碍值**。现在她给了你一个正整数 $n$，并 $t$ 次询问你两个满足 $1 \le l \le r \le n$ 的正整数 $l,r$ 的 **阻碍值** $ans\bmod{32465177}$。

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

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

outputFormat: 对于每组询问输出一个整数表示答案。


title: 「EZEC-9」模糊众数

description:
给你一个长为 $n$ 的序列 $a$。

你可以将序列中的某个数增加 $1$，称为一次操作。

你需要处理 $q$ 次询问。

对于每次询问，求出 $a$ 在至少多少次操作后，可以形成一个序列 $a'$，使得 $x$ 为 $a'$ 的众数。

**注意：一个序列可能有多个众数。**

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

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

后 $q$ 行每行一个整数 $x$。

outputFormat:
对于每次询问，若无解输出 `-1`，否则输出最少的操作次数。

每个答案之间用换行隔开。

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

- $x=2$ 时，一种可行的方案为 $a'=[1,2,2,3,3,4]$。
- $x=10$ 时，一种可行的方案为 $a'=[1,2,3,4,5,10]$。

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

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

-  Subtask 1（5 points）：$n=3$。
-  Subtask 2（5 points）：所有 $a_i$ 均相等，**时间限制为 2000 ms**。
-  Subtask 3（5 points）：$n\le 10$，$q\le 10^3$。
-  Subtask 4（15 points）：$n\le 100$，$q\le 10^4$。
-  Subtask 5（15 points）：$n\le 10^3$。
-  Subtask 6（15 points）：$q\le 10^3$。
-  Subtask 7（40 points）：**时间限制为 2000 ms**。

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


title: 「Stoi2031」手写的从前

background: > 我看着你的脸 轻刷着和弦 情人节卡片 手写的永远 还记得广场公园 一起表演 学校旁糖果店 记忆里在微甜 ——《手写的从前》

description: 远定义一个集合 $S$ 的 **权值** 为 $\dfrac{\sigma(S)}{\pi(S)}$，其中 $\sigma(S)=\sum\limits_{x \in S}x$ 为 $S$ 中所有元素之和， $\pi(S)=\prod\limits_{x \in S}x$ 为 $S$ 中所有元素之积。甜问他，一个集合 $S$ 的 **所有子集** 的 **权值** 和是多少？远很快就算出了答案。甜又问，那 **所有子集** 的 **所有子集** 的 **权值** 和之和是多少？远又很快就算了出来。于是甜又问了一个问题，问题中总共有 $k$ 个 **所有子集**，这下远算不完了，所以他找你帮忙。远不需要回答一个太大的数，所以答案只要取模 $p$。

inputFormat:
第一行 $3$ 个正整数 $n,k,p$，其中 $n$ 为 $S$ 中元素的个数。

第二行 $n$ 个正整数，表示 $S$ 中的元素。

outputFormat: 输出一个正整数表示答案，保证答案在模 $p$ 时有意义。

hint:
#### 简述版题意：

令 $f_0(S)=\dfrac{\sigma(S)}{\pi(S)}$，$f_k(S)=\sum\limits_{T \subseteq S}f_{k-1}(T)$。其中 $\sigma(S)=\sum\limits_{x \in S}x$ 为 $S$ 中所有元素之和， $\pi(S)=\prod\limits_{x \in S}x$ 为 $S$ 中所有元素之积。给定 $n,k,p$ 和集合 $S$，求 $f_k(S) \bmod{p}$ 的值。

#### 样例解释：

限于篇幅，只解释样例 $1$。

枚举子集：

$\emptyset$，$f_0$ 值为 $0$；

$\{1\}$，$f_0$ 值为 $1$；

$\{2\}$，$f_0$ 值为 $1$；

$\{3\}$，$f_0$ 值为 $1$；

$\{1,2\}$，$f_0$ 值为 $\dfrac{3}{2}$；

$\{1,3\}$，$f_0$ 值为 $\dfrac{4}{3}$；

$\{2,3\}$，$f_0$ 值为 $\dfrac{5}{6}$；

$\{1,2,3\}$，$f_0$ 值为 $1$；

总和为 $\dfrac{23}{3}$，模 $7$ 后为 $3$。

#### 数据范围：

对于 $30\%$ 的数据，$n \le 13,k=1$。

对于 $70\%$ 的数据，$n \le 10^3$。

对于 $100\%$ 的数据，$1 \le n \le 7 \times 10^6,1 \le k \le 10^{18},1 \le x_i<p,1<p<2^{31},p$ 是质数，$x_i$ 互不相同。

**本题读入量较大，可以选择使用比赛描述中的快速读入模板以加快读入速度。**


title: 「Stoi2031」兰亭序

background: > 无关风月 我题序等你回 悬笔一绝 那岸边浪千叠 情字何解 怎落笔都不对 而我独缺 你一生的了解 ——《兰亭序》

description: 月非常喜欢复数，尤其喜欢形如 $e^{2\pi it}$ 的复数。她选择了两个正整数 $n,k$，并将 $1+e^{\frac{2\pi i x_1 \dots x_k}{n}}$ 称为 $(x_1,\dots,x_k)$ 的 **绝对度**，所有满足 $1 \le x_i \le n$ $(i \in \{1,2,\dots,k\})$ 的 $(x_1,\dots,x_k)$ 的 **绝对度** 之积称为 $(n,k)$ 的 **无关度**。现在她想请你帮她对 $t \in \{1,2,\dots,k\}$ 求出 $(n,t)$ 的 **无关度** $ans \bmod{335544323}$。由于回答太多的数太麻烦，你只要回答她所有答案进行异或运算后的结果。

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

outputFormat: 一行一个自然数表示答案。


title: 「Wdsr-2.5」未来水妖集市

background:
每年，河城荷取（河童）都要为未来水妖集市准备展品，以及用于销售的商品。于是河童会生产大批量的产品。

为了提高生产效率，河童决定搭建一条生产线。具体而言，河童会利用她的机械臂，构建出一长串的机器。每个机器只会对原材料进行若干次加工，最终输出成品。

由于河童需要调试设备，于是机械臂每次操作后，河童会用一些询问确定这条生产线目前的性能如何。为了顺利完成生产任务，河童找到了你，希望你写一个程序告诉她每次操作后生产线的性能。

description:
初始时原材料会有一个初始权值 。然后它会经过若干个机器的加工，花费若干点**加工指数**，得到最终产品。

河童的机器有两种：

- 0 型：每次加工花费 $v_i$ 的加工指数，让材料的附加值增加 $w_i$ 。材料经过时**最多只能加工一次**。
- 1 型：每次加工花费 $v_i$ 的加工指数，让材料的附加值增加 $w_i$ 。材料经过时**加工次数无限制**。

现在河童会利用一个机械臂来设计这套工艺流程。初始时，流水线上没有一台机器，机械臂放在位置 $0$。机器的位置编号是从 $1$ 开始的。现在河童会告诉你加工指数的最大值 $v$ ，然后她会下达 $q$ 个命令。不妨设每个指令执行前，机械臂的位置在 $p$ 。

每个指令的格式为 $\colorbox{#f0f0f0}\verb!opt ti vi wi xi yi!$ ，其中 $opt$ 表示操作的种类。共有如下几种：

1. **右移**：将机械臂向右移动一格，即 $p\gets p+1$。
2. **左移**：将机械臂向左移动一格，即 $p\gets p-1$。
3. **插入机器**：在机械臂当前位置插入一个机器，它的类型为 $t_i$ ，每次消耗的加工指数为 $v_i$ ，材料的附加值会增加 $w_i$ ，插入的机器的位置为 $p+1$ 。机械臂位置不变，但是被插入的机器右侧的机器都会向右移动一格。
4. **删除机器**：在机械臂当前位置移除一个机器，移除的机器位置为 $p+1$ 。移除机器后机械臂位置不变，但是被移除的机器右侧的机器都会向左移动一格。
5. **修改机器**：在机械臂当前位置修改一个机器的参数。即修改的机器的位置为 $p+1$ 。

对于操作 1, 2, 4，请忽略参数 $\colorbox{#f0f0f0}\verb!ti vi wi!$ 。

每次操作完，河童会询问你，如果一个初始权值为 $x_i$ 的物品从左侧起第一个机器进去，直到从右边机器出来，依次加工，消耗最多 $y_i$ 点加工点数（ $y_i\le v$ ），这个物品可以获得的最大权值。特别地，如果此时没有一台机器，此物品权值不变。

假设某一时刻共有 $u$ 台机器，那么数据保证在此时刻机械臂的位置必然在 $[0,u]$ 内。

inputFormat:
第一行两个正整数 $q,v$ ，含义如题面所述。

接下来 $q$ 行，每行 $6$ 个正整数 $opt',t_i',v_i',w_i',x_i',y_i'$ 。你需要**将它们分别异或上** $\boldsymbol{last}$ 来获得真实的 $opt,t_i,v_i,w_i,x_i,y_i$ 。其中 $last$ 为上次输出的结果。特别地，初始时 $last=0$ 。

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


title: 「Wdsr-2.5」琪露诺的算数游戏

description:
#### 游戏概况

《琪露诺的算数游戏》（诨名“⑨牌”），是一款轻松快乐的多玩家卡牌回合制游戏。

**注意：这里的规则与市面上的⑨牌规则不尽相同**。由于⑨牌种类太多不大容易处理，所以这里的规则更类似于 $\text{NEU}$ 游戏。

游戏中有 $n$ 名玩家，围成一圈。一共会进行 $m$ 轮。每个玩家初始时有 $3$ 张手牌。游戏有一个 $k$ 张牌的牌堆。在本题中，你可以认为**不会出现牌堆抽完的情况**（真的）。此外，根据该题给出的规则，你不需要考虑选手手牌的顺序。

为了简述游戏规则，你可以认为每一轮游戏中有一个整型变量（类似于 $\text{int}$ 类型寄存器） $p$ 。玩家打出的牌本质上是对 $p$ 进行操作。

**注**：请注意下文中“局”、“轮”、“回合”的关系。本题你只会进行一局游戏，每局有 $m$ 轮，每一轮会有若干回合，每一回合会有一名玩家出牌。

每一轮开始时，$p$ 会被初始化为 $0$ ，然后从初始玩家开始，按照**顺时针顺序**（$1,2,3,\cdots n-1,n,1,2,\cdots$ ，逆时针同理），依次出牌。如果这是第一轮，那么初始玩家就是 $1$ 号玩家。当某个玩家出完某张牌后，如果此时 $p> 99$ ，视作该玩家成为该局的**失败者**；否则她就会**立刻从牌堆顶部取出一张牌**并进入到下一回合。失败者会丢失手上其余的两张牌，并从牌堆顶部依次摸三张牌放入自己的手牌中。同时，失败者会成为**下一轮初始玩家**。在一局游戏当中，牌堆里的牌只减不增。被使用的牌不会回到牌堆当中。

下面介绍该魔改版游戏的牌型。

#### 基本牌

基本牌可以分为五类：加法牌、减法牌、乘法牌、除法牌、固定牌。

- 加法牌，一共有 $7$ 种： $A_{1},A_{2},A_{5},A_{9},A_{19},A_{49},A_{99}$ 。其中， $A_x$ 的作用效果是，使 $p$ 加上牌面上的数字。即 $p\gets p+x$ 。
- 减法牌，一共有 $3$ 种： $B_{1},B_{9},B_{19}$ 。作用效果与加法牌类似，只不过会使 $p$ 减去牌面上的数字。
- 乘法牌，一共只有 $1$ 种： $C_2$ 。它的作用效果是令 $p$ 乘上对应的数字，即 $p\gets p\times x$ 。
- 除法牌，同样只有 $1$ 种： $D_2$ 。会令 $p$ 除以对应的数字，**向下取整**。即 $p\gets \lfloor p\div x\rfloor$ 。
- 固定牌，一共有 $3$ 种： $E_{0},E_{49},E_{99}$ ，会将 $p$ 直接设置为牌面上的数字。

#### 解牌

解牌是可以使一名玩家跳过该回合，并附加一些特殊效果的一类牌。

- $\tt{PASS}$ ，跳过你，转到下一个玩家。
- $\tt{TURN}$ ，跳过你，出牌顺序反转（顺时针变为逆时针，逆时针变为顺时针。在下一轮游戏开始时会重置为顺时针）。
- $\tt{DOUBLE}$ ，跳过你，然后给下一名玩家施加 $\verb!"DOUBLE"!$ 效果，也即要出两张牌（先打一摸一，再打一摸一，需要保持全程总数不超过 $99$ 才能保证不失败）。

$\tt{DOUBLE}$ 效果的一些说明：如果你被施加了 $\tt{DOUBLE}$ 的效果，但是你第一张出了解牌（三种解牌都可以），那么你就会立即解除 $\tt{DOUBLE}$ 效果，跳过这一回合，**并且将效果转移到下一名玩家**。 $\tt{DOUBLE}$ 效果不能叠加。

---

在输入文件中，卡牌名会形如 $\colorbox{#f0f0f0}\verb!A1 A99 D2 PASS DOUBLE!$ 等等。

#### 策略

这一部分将会讲述本题中所有玩家的运行逻辑。

如果无论怎么出都会失败，那么玩家就会随便打出一张牌并成为失败者（显然，打出哪张牌不会对游戏结局产生实质上的影响）。否则会有两种情形：

1. 如果此时没有被施加 $\tt{DOUBLE}$ 效果：
   - 每名玩家会优先考虑普通牌，并且选择在不成为失败者的前提下使 $p$ 变得**尽可能大**的那种方案（如果有多种方案可以使得 $p$ 最大，那就会按照**乘法牌、加法牌、减法牌、除法牌、固定牌**的顺序优先选择。显然，同一类普通牌中的不同种类的牌不会使 $p$ 产生相同的值）。
   - 如果没有普通牌，或者出牌后会成为失败者，那么就考虑使用解牌。玩家会依次考虑手头是否有 $\tt{PASS,TURN,DOUBLE}$ 牌。如果有，就打出这张牌。
2. 如果被施加了 $\tt{DOUBLE}$ 效果：
   - 优先考虑使用解牌。依次考虑$\tt{PASS,TURN,DOUBLE}$ 。如果有，就打出这张牌。
   - 否则，选择在不成为失败者的前提下使 $p$ 变得**尽可能小**的那种方案（如果有多种方案可以使得 $p$ 最小，那就会按照**除法牌、减法牌、加法牌、乘法牌、固定牌**的顺序优先选择）。此时玩家会被解除 $\tt{DOUBLE}$ 状态，于是她会按照情形 $1$ 来决策。

inputFormat:
第一行三个正整数 $n,m,k$ ，含义如题面所示。

接下来 $n$ 行，每行四个字符串 $name,card_1,card_2,card_3$ ，表示这名玩家的名称以及她的三张手牌。玩家名称仅由大小写英文字母组成，不包含空格，长度不超过 $20$ 。

接下来一行， $k$ 个字符串，按照从上至下的顺序描述牌堆里的牌。

详情可以参考输入样例。

outputFormat:
当新的一轮开始时，你需要输出： $\colorbox{f0f0f0}\verb!Round XXX:!$ （其中，$\verb!XXX!$ 表示这是第多少轮）。

每名玩家出牌时，如果她不是失败者，你需要输出： $\colorbox{f0f0f0}\verb!XXX used YYY,now p=ZZZ.!$ （其中，$\verb!XXX!$ 是玩家名； $\verb!YYY!$ 是卡牌名； $\verb!ZZZ!$ 是当前 $p$ 的值）。

否则，当一名玩家成为失败者时，该轮结束。你要输出：$\colorbox{f0f0f0}\verb!XXX lost the game.!$ （其中，$\verb!XXX!$ 是玩家名）。

详情可以参考输出样例。

samples:
2 1 10
JoesSR B9 A99 PASS
Cirno C2 D2 A49
E49 DOUBLE PASS A19 A49 A99 A99 A99 A99 A99

samples:
Round 1:
JoesSR used A99,now p=99.
Cirno used D2,now p=49.
JoesSR used E49,now p=49.
Cirno used C2,now p=98.
JoesSR used B9,now p=89.
Cirno used DOUBLE,now p=89.
JoesSR used PASS,now p=89.
Cirno lost the game.

samples:
3 2 25
Cirno A9 A19 B1
Reimu TURN A9 C2
Marisa DOUBLE D2 D2
A9 B9 C2 PASS PASS A9 A1 A99 A99 A99 A99 A99 A99 A99 A99 A99 A99 A99 A99 A99 A99 A99 A99 A99 A99

samples:
Round 1:
Cirno used A19,now p=19.
Reimu used C2,now p=38.
Marisa used D2,now p=19.
Cirno used A9,now p=28.
Reimu used A9,now p=37.
Marisa used C2,now p=74.
Cirno used A9,now p=83.
Reimu used B9,now p=74.
Marisa used A9,now p=83.
Cirno used A1,now p=84.
Reimu used PASS,now p=84.
Marisa used D2,now p=42.
Cirno used B1,now p=41.
Reimu used TURN,now p=41.
Cirno used PASS,now p=41.
Marisa used DOUBLE,now p=41.
Reimu lost the game.
Round 2:
Reimu used A99,now p=99.
Marisa lost the game.

hint:
#### 样例 1 说明

牌的使用情况都在输出样例中。这里仅说明每出一张牌后每名玩家当前手牌的情况。具体为什么要使用某张牌，可以参考题目描述。

$$
\def{\c}#1{\texttt{#1}}
\def\arraystretch{1.5}
\begin{matrix}
\begin{gathered}
\textbf{\textsf{初始}}\cr
\begin{array}{|c|c|c|c|} \hline
\textbf{玩家名} & \textbf{手牌 1} & \textbf{手牌 2}  & \textbf{手牌 3} \cr\hline
\text{JoesSR} & \c{B9} & \c{A99} & \c{PASS} \cr\hline
\text{Cirno} & \c{C2} & \c{D2} & \c{A49} \cr\hline
\end{array}\cr[10pt]
\textbf{\textsf{第一回合}}\quad (p: 0\to 99)\cr
\begin{array}{|c|c|c|c|} \hline
\textbf{玩家名} & \textbf{手牌 1} & \textbf{手牌 2}  & \textbf{手牌 3} \cr\hline
\text{JoesSR} & \c{B9} & \c{E49} & \c{PASS} \cr\hline
\text{Cirno} & \c{C2} & \c{D2} & \c{A49} \cr\hline
\end{array}\cr[10pt]
\textbf{\textsf{第二回合}}\quad (p:99\to 49)\cr
\begin{array}{|c|c|c|c|} \hline
\textbf{玩家名} & \textbf{手牌 1} & \textbf{手牌 2}  & \textbf{手牌 3} \cr\hline
\text{JoesSR} & \c{B9} & \c{E49} & \c{PASS} \cr\hline
\text{Cirno} & \c{C2} & \c{DOUBLE} & \c{A49} \cr\hline
\end{array}\cr[10pt]
\textbf{\textsf{第三回合}}\quad (p:49\to 49)\cr
\begin{array}{|c|c|c|c|} \hline
\textbf{玩家名} & \textbf{手牌 1} & \textbf{手牌 2}  & \textbf{手牌 3} \cr\hline
\text{JoesSR} & \c{B9} & \c{PASS} & \c{PASS} \cr\hline
\text{Cirno} & \c{C2} & \c{DOUBLE} & \c{A49} \cr\hline
\end{array}\cr[10pt]
\end{gathered}
&
\begin{gathered}
\textbf{\textsf{第四回合}}\quad (p:49\to 98)\cr
\begin{array}{|c|c|c|c|} \hline
\textbf{玩家名} & \textbf{手牌 1} & \textbf{手牌 2}  & \textbf{手牌 3} \cr\hline
\text{JoesSR} & \c{B9} & \c{PASS} & \c{PASS} \cr\hline
\text{Cirno} & \c{A19} & \c{DOUBLE} & \c{A49} \cr\hline
\end{array}\cr[10pt]
\textbf{\textsf{第五回合}}\quad (p:98\to 89)\cr
\begin{array}{|c|c|c|c|} \hline
\textbf{玩家名} & \textbf{手牌 1} & \textbf{手牌 2}  & \textbf{手牌 3} \cr\hline
\text{JoesSR} & \c{A49} & \c{PASS} & \c{PASS} \cr\hline
\text{Cirno} & \c{A19} & \c{DOUBLE} & \c{A49} \cr\hline
\end{array}\cr[10pt]
\textbf{\textsf{第六回合}}\quad (p:89\to 89)\cr
\begin{array}{|c|c|c|c|} \hline
\textbf{玩家名} & \textbf{手牌 1} & \textbf{手牌 2}  & \textbf{手牌 3} \cr\hline
\text{JoesSR} & \c{A49} & \c{PASS} & \c{PASS} \cr\hline
\text{Cirno} & \c{A19} & \c{A99} & \c{A49} \cr\hline
\end{array}\cr[10pt]
\textbf{\textsf{第七回合}}\quad (p:89\to 89)\cr
\begin{array}{|c|c|c|c|} \hline
\textbf{玩家名} & \textbf{手牌 1} & \textbf{手牌 2}  & \textbf{手牌 3} \cr\hline
\text{JoesSR} & \c{A49} & \c{A99} & \c{PASS} \cr\hline
\text{Cirno} & \c{A19} & \c{A99} & \c{A49} \cr\hline
\end{array}\cr[10pt]
\end{gathered}
\end{matrix}
$$

**注**：初始回合以及第 $2,4,6$ 回合都是 $\text{JoesSR}$ 出牌；第 $1,3,5,7$ 回合都是琪露诺出牌。值得注意的是，尽管第 $5$ 回合琪露诺使用了 $\tt{DOUBLE}$ ，但因为下一回合被 $\tt{PASS}$ 了，所以第 $7$ 回合仍然是琪露诺出牌。

此时琪露诺无论如何都会失败，于是琪露诺成为了失败者。

#### 样例 3

见下发附件。

#### 数据规模与约定

- 对于 $30\%$ 的数据，仅包含普通牌，并且 $n\le 3$ 。
- 对于另外 $15\%$ 的数据，不包含 $\tt{TURN}$ 牌和 $\tt{PASS}$ 牌。
- 对于另外 $15\%$ 的数据，不包含 $\tt{DOUBLE}$ 牌。
- 对于 $100\%$ 的数据， 满足 $1\le n\le 30;1\le m\le 100;1\le k\le 3\times 10^5$ 。保证任何时候 $|p|<10^4$ 。

#### 参考资料

[【东方桌游考古】NEU，“⑨牌”，与十年前的同人](https://www.bilibili.com/read/cv9951620)


title: 「Stoi2031」蒲公英的约定（vol.1）

background: > 一起长大的约定 那样清晰 拉过勾的我相信 说好要一起旅行 是你如今 唯一坚持的任性 ——《蒲公英的约定》

description:
清和如在玩游戏。她们有 $n$ 丛 **蒲公英**，每丛分别有 $s_i$ 朵。这些 **蒲公英** 有一个神奇的性质：有一个给定的常数 $\sigma \in (0,1)$，$x$ 朵 **蒲公英** 会分出 $\lfloor \sigma x \rfloor$ 朵为一组，剩下 $x-\lfloor \sigma x \rfloor$ 朵继续分组，直到分出的组没有 **蒲公英** 即 $\lfloor \sigma x \rfloor=0$ 为止。她们称这种现象为 **任性**。现在她们的每丛 **蒲公英** 都有 **任性** 的现象。她们的游戏规则如下：从清开始，两人轮流进行 **旅行**。一次 **旅行** 为选择一丛 **蒲公英** 并吹散这一丛的第一组中的若干朵 **蒲公英**，至少要吹一朵，至多吹的朵数为第一组的朵数，即不能吹散除第一组外的 **蒲公英**。当第一组为空时，其下一组成为第一组。若这一丛只剩下一组 **蒲公英**，这一丛不能再被选定。每丛 **蒲公英** 都不能被选定时，游戏结束，当前轮到的人落败。她们想知道如果清第一次 **旅行** 时等概率选择其中一丛可吹散的 **蒲公英** 再等概率选择吹散的朵数后两人都按最优策略操作，那么清的胜率 $x \bmod 20190816170251$ 的值将会是多少。

与 vol.2 的区别是，**蒲公英** 在被吹散一部分后 **不会** 重新分组。

inputFormat:
第一行两个正整数 $id,n$，其中 $id$ 表示 Subtask 编号。

第二行 $n$ 个正整数，第 $i$ 个表示 $s_i$。

若 $id>3$，第三行输入两个正整数 $p,q$ 表示 $\sigma=\dfrac{p}{q}$。

outputFormat: 一行一个整数，表示清的胜率 $x \bmod{20190816170251}$。


title: 「Stoi2031」蒲公英的约定（vol.2）

description:
清和如在玩游戏。她们有 $n$ 丛 **蒲公英**，每丛分别有 $s_i$ 朵。这些 **蒲公英** 有一个神奇的性质：有一个给定的常数 $\sigma \in (0,1)$，$x$ 朵 **蒲公英** 会分出 $\lfloor \sigma x \rfloor$ 朵为一组，剩下 $x-\lfloor \sigma x \rfloor$ 朵继续分组，直到分出的组没有 **蒲公英** 即 $\lfloor \sigma x \rfloor=0$ 为止。她们称这种现象为 **任性**。现在她们的每丛 **蒲公英** 都有 **任性** 的现象。她们的游戏规则如下：从清开始，两人轮流进行 **旅行**。一次 **旅行** 为选择一丛 **蒲公英** 并吹散这一丛的第一组中的若干朵 **蒲公英**，至少要吹一朵，至多吹的朵数为第一组的朵数，即不能吹散除第一组外的 **蒲公英**。当第一组为空时，其下一组成为第一组。若这一丛只剩下一组 **蒲公英**，这一丛不能再被选定。每丛 **蒲公英** 都不能被选定时，游戏结束，当前轮到的人落败。她们想知道如果清第一次 **旅行** 时等概率选择其中一丛可吹散的 **蒲公英** 再等概率选择吹散的朵数后两人都按最优策略操作，那么清的胜率 $x \bmod{20190816170251}$ 的值将会是多少。

与 vol.1 的区别是，**蒲公英** 在被吹散一部分后 **会** 重新分组。


title: 「Stoi2031」兰亭序 加强版

description:
本题是 「Stoi2031」兰亭序 的加强版。[原题链接](https://www.luogu.com.cn/problem/P7487)

给定 $n=a^b,k$，对 $1 \le t \le k$ 求

$$\prod_{x_1=1}^{n}\prod_{x_2=1}^{n}\dots\prod_{x_t=1}^{n}\left( 1+e^{\frac{2\pi ix_1x_2\dots x_t}{n}} \right) \bmod{335544323}$$

输出所有 $k$ 个答案的异或和。

其中 $e^{it}=\cos{t}+i\sin{t}$ 对所有 $t \in \mathbb{R}$ 成立，$i$ 为虚数单位，满足 $i^2=-1$。

inputFormat: 一行三个正整数 $a,b,k$，其中 $n=a^b$。

outputFormat: 一行一个自然数表示答案。


title: 「PMOI-3」简单模拟题

description:
给定一个长度为 $n$ 的序列 $s$。

$q$ 次询问，每个询问形如 `a b c d e f`，需要你求出下面式子的值：
$$\sum_{L=a}^{b}[e\le G(F(L,c),F(L,c+1),\cdots,F(L,d))\le f]$$
这里 $F(l,r)$ 表示 $s$ 序列区间 $[l,r]$ 中不同的数的个数，$G(x_1,x_2,\cdots,x_k)$ 表示 $x_1,x_2,\cdots,x_k$ 中不同的数的个数。

inputFormat:
第一行两个整数 $n,q$，表示序列长度与命令次数。

第二行输入 $n$ 个整数，第 $i$ 个数表示 $s_i$。

下面 $q$ 行，每行输入 $6$ 个数 $a',b',c',d',e,f$。令上一次询问的答案为 $\text{lastans}$（特别的，若这是第一次询问，则 $\text{lastans}=0$），则本次询问中

$a=(a'+\text{lastans})\bmod n+1\\$
$b=(b'+\text{lastans})\bmod n+1\\$
$c=(c'+\text{lastans})\bmod n+1\\$
$d=(d'+\text{lastans})\bmod n+1\\$

**注意，你需要将 $a,b,c,d$ 重新排序使得 $a\le b\le c\le d$。**

outputFormat: 对于每次询问，依次输出答案。


title: 「EZEC-10」打分

background: **为防止评测机被卡，本题时限为 100 ms。**

description:
小 A 去参加奥运会。

奥运会中共有 $n$ 名裁判，分别给小 A 打分 $a_1,a_2,\ldots,a_n$。

小 A 对自己的得分不满意，于是他将某名裁判打出的分数加 $1$，称为一次操作。

但是小 A 不能太贪心，他最多只能进行 $m$ 次操作。

小 A 的最终得分为：所有得分中，去掉一个最高分和一个最低分后的平均值。

小 A 想知道，他的最终得分最高为多少。

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

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

outputFormat: 为了方便输出，小 A 只需知道**最终得分$\times (n-2)$** 为多少就可以了。

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

一种可行的方案为：$[1,2,3]\to [3,2,3]$。

**【样例 2 解释】**

一种可行的方案为：$[1,2,2,3]\to [2,3,3,3]$。

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

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

- Subtask 1（5 points）：$m=0$。
- Subtask 2（10 points）：$n=3$。
- Subtask 3（15 points）：$n,m\le 10^3$。
- Subtask 4（70 points）：无特殊限制。

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


title: [THUSC2016] 星露谷物语

description:
最近，小葱为了忘记城市的喧嚣，来到了星露谷开始种地发家致富。但是，由于小葱把钱都拿去抽卡了，所以小葱并没有足够的钱来买种子。为了搜集足够的钱来养猪，小葱必须开始大规模的搜寻野菜工作。

星露谷是一个无限大的二维平面，你可以在这个二维平面内任意移动。小葱可能在星露谷的 $n$ 条线段上找到野菜，但是这些线段是有向的，小葱必须沿着线段的方向移动才能找到野菜。为了找到更多的野菜，小葱希望自己能把星露谷中所有可能出现野菜的地方全部走一遍。换句话说，对于每条线段，小葱都需要沿着该线段的方向将这条线段的每个点都经过一遍。当然，小葱可以选择分多次走一条线段，具体地讲，小葱可以在这条线段的任意位置离开这条线段，再从任意位置进入这条线段，只要保证路径的并集覆盖了这条有向线段即可。

小葱希望找到一条尽量短的路径，这条路径应该由 $m$ 条线段组成，并且覆盖了星露谷中的 $n$ 条有向线段。小葱可以选择星露谷的任意一个点作为路径的起点，同时它也必须是路径的终点，即小葱最终必须回到出发的位置。

现在，小葱要去写四子棋大作业了，他不知道该怎么规划自己的行走方案使得自己移动的距离尽量短，所以就把这个艰巨的任务交给聪明的你了。

**注意：如果有两条线段的某部分重合且方向相同，那么你在走过这一段的时候我们认为这两条线段的这部分都被走过了。**

inputFormat:
第一行包含一个整数 $n$，代表图中有向线段的数量。

接下来 $n$ 行，每行四个整数  $x_1,y_1,x_2,y_2$，代表这条线段是一条从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的有向线段。

outputFormat: 第一行应包含一个整数 $m$，代表小葱所走的折线路径中点的数量，需要满足 $m\le\min(5n^2,5\times 10^6)$。 接下来 $m$ 行，按照路径的顺序依次输出路径上的点。每行应包含两个浮点数 $x,y$，用来描述一个点的横、纵坐标。其中，$x,y$ 请保留不超过 $5$ 位小数。

hint:
**本题为提交答案题，输入与 checker 将会在附件给出**

对于每组测试数据，如果你的输出格式不符合题目要求，或者你输出的路径并没有走完给定的条 $n$ 有向线段，那么该测试点得 $0$ 分。否则，我们会计算你给出路径的长度 $d$，并根据 $10$ 个评分参数 $a_1\ge a_2\ge...\ge a_{10}$ 计算你的得分：
$$\max\{i|d\le a_i,1\le i\le 10\}$$

数据保证 $a_1$ 足够大，以确保一个合法的方案至少可以得到 $1$ 分。
#### 样例解释
对于样例 $1$，小葱总共移动了 $200+100\sqrt2$ 的距离，这也是这组样例的最优解。

对于样例 $2$，在该组解中，小葱一共移动了 $202+\sqrt{2402}+\sqrt{2602}$ 的距离，但这并不是这组数据的最优解。


title: [THUSCH2017] 巧克力

description:
「人生就像一盒巧克力，你永远不知道吃到的下一块是什么味道。」

明明收到了一大块巧克力，里面有若干小块，排成 $n$ 行 $m$ 列。每一小块都有自己特别的图案 ，它们有的是海星，有的是贝壳，有的是海螺……其中还有一些因为挤压，已经分辨不出是什么图案了。明明给每一小块巧克力标上了一个美味值 $a_{i,j}$（$0\le a_{i,j}\le 10^6$），这个值越大，表示这一小块巧克力越美味。

正当明明咽了咽口水，准备享用美味时，舟舟神奇地出现了。看到舟舟恳求的目光，明明决定从中选出一些小块与舟舟一同分享。

舟舟希望这些被选出的巧克力是连通的（两块巧克力连通当且仅当他们有公共边），而且这些巧克力要包含至少 $k$（$1\le k\le 5$）种。而那些被挤压过的巧克力则是不能被选中的。

明明想满足舟舟的愿望，但他又有点「抠」，想将美味尽可能多地留给自己。所以明明希望选出的巧克力块数能够尽可能地少。如果在选出的块数最少的前提下，美味值的中位数（我们定义 $n$ 个数的中位数为第 $\left\lfloor\frac{n+1}{2}\right\rfloor$ 小的数）能够达到最小就更好了。

你能帮帮明明吗？

inputFormat:
每个测试点包含多组测试数据。

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

对于每组测试数据：

输入第一行包含三个正整数 $n,m$ 和 $k$；

接下来 $n$ 行，每行 $m$ 个整数，表示每小块的图案 $c_{i,j}$。若 $c_{i,j}=-1$ 表示这一小块受到过挤压，不能被选中；

接下来 $n$ 行，每行 $m$ 个整数，表示每个小块的美味值 $a_{i,j}$。

outputFormat:
输出共包括 $T$ 行，每行包含两个整数，用空格隔开，即最少的块数和最小的美味值中位数。

若对于某组测试数据，不存在任意一种合法的选取方案，请在对应行输出两个 $-1$。


title: [THUSCH2017] 杜老师

description:
杜老师可是要打 $+∞$ 年 World Final 的男人，虽然规则不允许，但是可以改啊！

但是今年 WF 跟 THUSC 的时间这么近，所以他造了一个 idea 就扔下不管了……

给定 $L,R$，求从 $L$ 到 $R$ 的这 $R-L+1$ 个数中能选出多少个不同的子集，满足子集中所有的数的乘积是一个完全平方数。特别地，空集也算一种选法，定义其乘积为 $1$。

由于杜老师忙于跟陈老师和鏼老师一起打 ACM 竞赛，所以，你能帮帮杜老师写写标算吗？

inputFormat:
从标准输入读入数据。

每个测试点包含多组测试数据。

输入第一行包含一个正整数 $T$（$1\le T\le 100$），表示测试数据组数。

接下来 $T$ 行，第 $i+1$ 行两个正整数 $L_i,R_i$ 表示第 $i$ 组测试数据的 $L,R$，保证 $\le L_i\le R_i\le10^7$。

outputFormat:
输出到标准输出。

输出 $T$ 行，每行一个非负整数，表示一共可以选出多少个满足条件的子集，答案对 $998244353$ 取模。


title: [THUSCH2017] 换桌

description:
班级聚会的时候，班主任为了方便管理，规定吃饭的时候同一个寝室的同学必须坐在一起；但是吃完饭后，到了娱乐时间，喜欢不同游戏的同学会聚到一起；在这个过程中就涉及到了座位分配的问题。

有 $n$ 张圆桌排成一排（从左到右依次编号为 $0$ 到 $n-1$），每张桌子有 $m$ 个座位（按照逆时针依次编号为 $0$ 到 $m-1$），在吃饭时每个座位上都有一个人；在吃完饭后的时候，每个人都需要选择一个新的座位（新座位可能和原来的座位是同一个），具体来说，第 $i$ 桌第 $j$ 个人的新座位只能在第 $L_{i,j}$ 桌到第 $R_{i,j}$ 桌中选，可以是这些桌中的任何一个座位。确定好新座位之后，大家开始移动，移动的体力消耗按照如下规则计算：

移动座位过程分为两步：

1. 从起始桌移动到目标桌**对应座位**，这个过程中的体力消耗为**两桌距离的两倍**，即从第 $i$ 桌移动到第 $j$ 桌对应座位的体力消耗为 $2\times |i-j|$；
1. 从目标桌的对应座位绕着桌子移动到目标座位，由于桌子是圆的，所以客人会选择**最近的方向**移动，体力消耗为**移动距离的一倍**，即从编号为 $x$ 的座位移动的编号为 $y$ 的座位的体力消耗为 $\min(|x-y|,m-|x-y|)$；

详情如下图：
![pic1](https://i.loli.net/2019/01/16/5c3f2f01e0336.png)
现在，给定每个客人的限制（即每个人的新座位所在的区间），需要你设计一个方案，**使得所有客人消耗的体力和最小；本题中假设客人在移动的时候互不影响。**

inputFormat:
从标准输入读入数据。

第一行输入两个数 $n$ 和 $m$；

接下来输入 $n$ 行，每行 $m$ 个空格隔开的整数描述矩阵 $L$：其中，第 $i$ 行的第 $j$ 个数表示 $L_{i,j}$；

接下来输入 $n$ 行，每行 $m$ 个空格隔开的整数描述矩阵 $R$：其中，第 $i$ 行的第 $j$ 个数表示 $R_{i,j}$；

数据是随机生成的，生成数据的伪代码如下：
```cpp
for i <- 0 to n-1
    for j <- 0 to m-1
        L[i,j] <- 独立等概率地得到 0 到 n-1 中的一个整数
        R[i,j] <- 独立等概率地得到 0 到 n-1 中的一个整数
        if L[i,j] > R[i,j] then
            tmp <- L[i,j]
            L[i,j] <- R[i,j]
            R[i,j] <- tmp
```

outputFormat:
输出到标准输出。

输出总体力消耗的最小值，如果没有合法的方案输出 `no solution`。


title: [THUSCH2017] 大魔法师

description:
大魔法师小 L 制作了 $n$ 个魔力水晶球，每个水晶球有水、火、土三个属性的能量值。小 L 把这 $n$ 个水晶球在地上从前向后排成一行，然后开始今天的魔法表演。

我们用 $A_i,B_i,C_i$ 分别表示从前向后第 $i$ 个水晶球（下标从 $1$ 开始）的水、火、土的能量值。

小 L 计划施展 $m$ 次魔法。每次，他会选择一个区间 $[l,r]$，然后施展以下 $3$ 大类、$7$ 种魔法之一：

1. 魔力激发：令区间里每个水晶球中**特定属性**的能量爆发，从而使另一个**特定属性**的能量增强。具体来说，有以下三种可能的表现形式：

	- 火元素激发水元素能量：令 $A_i=A_i+B_i$。
	- 土元素激发火元素能量：令 $B_i=B_i+C_i$。
	- 水元素激发土元素能量：令 $C_i=C_i+A_i$。

    **需要注意的是，增强一种属性的能量并不会改变另一种属性的能量，例如 $A_i=A_i+B_i$ 并不会使 $B_i$ 增加或减少。**

2. 魔力增强：小 L 挥舞法杖，消耗自身 $v$ 点法力值，来改变区间里每个水晶球的**特定属性**的能量。具体来说，有以下三种可能的表现形式：

	- 火元素能量定值增强：令 $A_i=A_i+v$。
	- 水元素能量翻倍增强：令 $B_i=B_i\times v$。
	- 土元素能量吸收融合：令 $C_i=v$。
3. 魔力释放：小 L 将区间里所有水晶球的能量聚集在一起，融合成一个新的水晶球，然后送给场外观众。生成的水晶球每种属性的能量值等于区间内所有水晶球对应能量值的代数和。**需要注意的是，魔力释放的过程不会真正改变区间内水晶球的能量。**

值得一提的是，小 L 制造和融合的水晶球的原材料都是定制版的 OI 工厂水晶，所以这些水晶球有一个能量阈值 $998244353$。当水晶球中某种属性的能量值大于等于这个阈值时，能量值会自动对阈值取模，从而避免水晶球爆炸。

小 W 为小 L（唯一的）观众，围观了整个表演，并且收到了小 L 在表演中融合的每个水晶球。小 W 想知道，这些水晶球蕴涵的三种属性的能量值分别是多少。

inputFormat:
从标准输入读入数据。

我们将上述的 $7$ 种魔法，从上到下依次标号为 $1\sim7$。

输入的第一行包含一个整数 $n$（$1\le n\le 2.5\times 10^5$），表示水晶球个数。

接下来 $n$ 行，每行空格隔开的 $3$ 个整数，其中第 $i$ 行的三个数依次表示 $A_i,B_i,C_i$。

接下来一行包含一个整数 $m$（$1\le m\le2.5\times 10^5$），表示施展魔法的次数。

接下来 $m$ 行，每行 $3$ 或 $4$ 个数，格式为 `opt l r (v)`。其中 `opt` 表示魔法的编号，$l,r$ 表示施展魔法的区间（保证有 $l\le r$）。特别地，如果施展 $4\sim6$ 号魔法（魔力增强），则还有一个整数 $v$，表示小 L 消耗的法力值。

outputFormat:
输出到标准输出。

对每个 $7$ 号魔法（魔力释放），输出一行、空格隔开的 $3$ 个整数 `a b c`，分别表示此次融合得到的水晶球的水、火、土元素能量值。


title: [THUSCH2017] 如果奇迹有颜色

background: 法本公司曾经是世界最大的化工企业，他们生产的染料颜色非常丰富，有清华紫，心灵黄，原谅绿，会议蓝，高级黑，北大红，相簿白等。

description:
现在 B 君有一个由 $n$ 个区域组成的环，B 君要用 $m$ 种颜色来染这 $n$ 个区域。

B 君不希望在这 $n$ 个区域中存在连续 $m$ 个区域恰好出现所有 $m$ 个颜色。换句话说，对于任意连续 $m$ 个区域，都不能恰好出现所有 $m$ 个颜色。

如果两个方案通过旋转可以变得一模一样，那么我们认为他们是本质相同的；

但是如果两个方案需要通过翻转才能变得一模一样，我们不认为他们是本质相同的。

比如如果 $n=4,m=4$；

我们认为 $1,2,3,4$ 和 $3,4,1,2$ 是本质相同的方案；

我们认为 $1,2,3,4$ 和 $4,3,2,1$ 是本质不同的方案；

我们认为 $1,2,1,2$ 和 $2,1,2,1$ 是本质相同的方案；

B 君希望知道满足条件，本质不同的方案数，输出答案对 $10^9+7$ 取模。

inputFormat:
从标准输入读入数据。

输入一行包含两个整数 $n,m$，其中 $n$ 表示环的长度，$m$ 表示颜色数。

outputFormat:
输出到标准输出。

输出一行一个整数，表示答案对 $10^9+7$ 取模的结果。


title: [THUSCH2017] 宇宙广播

description:
威摄纪元公元 2233 年，人类掌握了一项新的科技：基于量子力学原理，在地球表面上的宇宙广播能够超光速地将信号传播到这个点坐标所在的、与地球相切的平面中。

自从万有引力号广播了坐标之后，它带着人类文明的种子，远离太阳系飞向了宇宙深处。

DX3906 星系黑域纪元公元 3333 年，万有引力号找到了一个十分庞大的 X 星系，直径数光年，其中有 3 个适合人类居住的星球，分布在 X 星系不同的角落中。经过商讨之后，万有引力号的部分成员选择留在这三个星球上定居。

对于定居的人类而言，实时通讯是十分必要的，因此一千一百年前发明的那套装置在这时候就派上了用场。显然，三个星球能够互相通讯，当且仅当三个宇宙广播的工作切平面完全重合。

现在，星球球长阿米巴找到了善于编程的你，希望你能够通过编程计算得出所有能够建立宇宙广播的方案。

在你承担了这个任务之后，你在心里说了一句，「这算啥，我 ygg 分分钟搞定」，然而善于读心的阿米巴马上把你叫了回来，语重心长的跟你说，人类文明还要延续，把 $K$ 维空间的 $K$ 个星球的建站方案一起解决了。球长也没太为难你，只要你求 $K\le10$ 的情况，这是因为宇宙加上时间维之后是 $11$ 维的。

当你用 $3$ 分钟写完程序之后，阿米巴看了看，送给你一张二向箔——因为你没有在程序里考虑到这个情况。

给定坐标维数 $K\ge2$，以及在 $K$ 维坐标下的 $K$ 个球（**可退化成点**，即半径可以为零），求出这 $K$ 个球的**所有公切面**。

数据保证不会出现无解或无穷多组解的情况，但不保证所有球都是相离的。

以下是一些定义：

- 距离：在 $K$ 维空间中，设有两个点 $A(a_0,a_1,...,a_{K-1}),B(b_0,b_1,...,b_{K-1})$，则 $AB$ 之间的距离 $|AB|=\sqrt{\sum_{i=0}^{K-1}(a_i-b_i)^2}$；

- 球：在 $K$ 维空间中，与定点 $A$ 的距离为常数 $r$ 的点集，并同时称点 $A$ 为球心，$r$ 为该球半径；

  当 $K=2$ 时，即为大家在中学所熟知的圆。

- 超平面：到 $K$ 维空间中某两个点 $A,B$ 距离相等的点集；在 $K$ 维空间中，超平面的维数为 $K-1$；

	当 $K=2$ 时，即为大家在中学所熟知的直线（垂直平分线）。

- 球的切平面：一个超平面 $P$ 与球 $A$ 有且仅有一个交点；

- 球的公切面：一个超平面 $P$ 是所有球的切平面。

inputFormat:
这是一道提交答案题，共有8组输入数据，这些数据命名为 1.in ~ 8.in。

每个测试点中包含多组数据。对于每个测试点：

- 第一行：测试点包含的数据组数 $T$，保证 $T\le10$。
- 对于每组数据：
	- 第一行：坐标维数 $K$，保证 $2\le K\le10$。
	- 接下来 $K$ 行，每行 $K+1$ 个实数。第 $i$ 行的前 $K$ 个数代表第 $i$ 个球的球心所在的坐标，第 $K+1$ 个数代表第 $i$ 个球的半径。

outputFormat:
对于每组输入数据，你需要提交相应的输出文件 1.out ~ 8.out。

对于每个测试点的每组数据：

- 第一行，一个正整数  $S$，表示在这组数据中你总共找到了 $S$ 组切平面。如果没找到任何一组解，**请务必输出 $0$，否则将会影响后续数据的评分，造成的后果由选手自行承担**；
- 接下来 $S\times K$ 行，每行 $K$ 个小数，对于相对的第 $S(i-1)+j$ 行，表示在输出的第 $i$ 个解中，**对应输入**的第 $j$ 个球上的切点坐标；
- 最后一行，输出一个空行；

**在输出文件的最后，你可以添加任意内容，这不会影响你的得分。我们建议你在此处写一些有意义的内容（如简要方法），以便于我们在考后进行统计分析。单个输出文件大小不得超过 4M。**

samples:
见附加文件中的 0.in
见附加文件中的 0.ans

hint:
#### 评分标准
- 解的输出顺序没有要求。在一组解中，记输出答案为 $A(a_0,a_1,...,a_{K-1})$，如果存在一组标准答案 $B(b_0,b_1,...,b_{K-1})$，满足 $\sum_{i=0}^{K-1}|A_iB_i|^2\le10^{-12}$，那么这一组输出答案将会被判定为正确。
- 在每个测试点的同一组数据中，我们会统计被匹配上的标准答案的公切面的个数，每个标准答案只会被匹配至多一次，输出重复的公切面不倒扣分。第 $i$ 组数据回答正确的比例为被匹配上的标准答案的个数除以标准答案的总个数，记为 $rate_i$。
- 对于每个测试点的评分方式：
	1. 如果你的输出格式不合法，或者参数不符合题目约定，或者某一组的答案个数超过该组标准答案个数的两倍以上（不含两倍），则得0分；
      1. 在不违背上述条件的情况下，算对其中任何一组数据的任何一个解就至少有一分；并且所有的答案都算对了，才能得
      1. 在不违背上述条件的情况下，记共有 $T$ 组数据，$rate_i$ 为第 $i$ 组数据回答正确的比例，$score$ 为这个测试点的分值，则 $Yourscore=\frac{score}{T}\times\sum_{i=1}^T\sqrt{rate_i}$ 在不违背以上原则的情况下四舍五入输出，即 $Yourscore\in[1,score-1]$。
各测试点分值不同，具体如下表所示：

| 测试点 | $K\le$ | 分值 |
| :----------: | :----------: | :----------: |
| 1 | $2$ | $5$ |
| 2 | $2$ | $15$ |
| 3 | $3$ | $11$ |
| 4 | $3$ | $14$ |
| 5 | $3$ | $16$ |
| 6 | $4$ | $7$ |
| 7 | $4$ | $9$ |
| 8 | $10$ | $23$ |


title: 「PMOI-3」子树

background: 分割线下有形式化题面，可以配合食用。

description:
b6e0 有一棵树，树上第 $i$ 个点有价值 $a_i$。每条边长度为 $1$。

b6e0 会选择一个节点作为根节点。设这个节点为 $r$。然后，b6e0 会圈定一个节点的整个子树作为他的领地，设这个子树的根节点为 $u$。此时，树上的每个节点会给 b6e0 带来一些收益。在领地子树的根节点为 $u$ 的情况下，节点 $x$ 带来的收益 $f(x,u)$ 定义如下：
1. 当 $x$ 在 $u$ 的子树中时，它的收益为它父亲节点的收益加上它本身的价值 $a_x$；
2. 当 $x$ 不在 $u$ 的子树中时，它的收益为：与它相邻的节点中，与 $u$ 距离（到 $u$ 的简单路径长度）比 $x$ 到 $u$ 的距离远的节点，这些节点的收益**对 $998244353$ 取模**的最大值，再乘上 $a_x$。

在根节点为 $r$ 的情况下，定义以 $u$ 为子树的收益 $W(u)$ 为所有节点的 $f$ 值和。

当然，b6e0 有许多种选择根节点的方案。定义选 $r$ 为根节点的收益 $C(r)$ 为对于所有 $u$，以 $u$ 为子树的收益（$W(u)$）的和。对于每一个节点 $r$，求 $C(r)$。

---
形式化题面：

给你一棵有 $n$ 个节点的树，第 $i$ 个节点有点权 $a_i$，每条边的长度为 $1$。当根节点为 $r$ 时：

设 $F(x)$ 表示 $x$ 的父亲节点，特殊地，$F(r)=0$；$D(x,y)$ 表示 $x$ 到 $y$ 的简单路径的长度，特殊地，对于所有 $x$，$D(x,x)=0$；$A_x$ 表示 $x$ 的子树中的节点（包括 $x$ 本身）组成的集合，即 $A_x=\{y\mid D(x,y)=D(F(x),y)-1\}$，特殊地，$A_r=\{1,2,\cdots,n\}$；$B_x$ 表示与 $x$ 相邻的节点组成的集合，即 $B_x=\{y\mid D(x,y)=1\}$。

定义 $f(x,u)$：
$$f(x,u)=\begin{cases}f(F(x),u)+a_x&x\in A_u\\a_x\cdot\max_{y\in B_x,D(y,u)>D(x,u)}\{f(y,u)\bmod 998244353\}&x\not\in A_u\end{cases}$$
特殊地，对于所有 $x$，$f(0,x)=0$；在 $x\not\in A_u$ 的情况中，若对于所有 $y\in B_x$，都有 $D(y,u)\le D(x,u)$，则 $f(x,u)=a_x$。

定义节点 $u$ 的分数 $W(u)=\sum_{v=1}^nf(v,u)$。

定义节点 $r$ 的收益 $C(r)$ 表示以 $r$ 为根时，$\sum_{i=1}^nW(i)$ 的值。

对于每一个节点 $r$，求 $C(r)$。

**所有 $C(r)$ 对 $998244353$ 取模。**

inputFormat:
第一行输入一个正整数 $n$ 表示这棵树的节点数。

第二行输入 $n$ 个整数，第 $i$ 表示节点 $i$ 的点权 $a_i$。

下面 $n-1$ 行，每行输入两个正整数 $u,v$，表示节点 $u$ 与节点 $v$ 之间有一条边。

outputFormat: 输出 $n$ 行，第 $i$ 行输出一个正整数表示节点 $i$ 的收益 $C(i)$ **对 $998244353$ 取模**的值。

hint:
【样例解释】

样例中的树如下图：

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

例如在 $r=1$，$u=5$ 时，$f(2,u)=a_2=2$，$f(1,u)=a_1\cdot f(2,u)=14$，$f(3,u)=a_3\cdot f(1,u)=70$，$f(6,u)=a_6=5$，$f(4,u)=a_4\cdot\max\{f(3,u),f(6,u)\}=7000$，$f(5,u)=f(4,u)+a_5=7001$。

【数据范围】
- Subtask1（10pts）：$n\le200$，$a_i\le 10^3$；
- Subtask2（20pts）：$n\le10^3$；
- Subtask3（20pts）：树为一条链；
- Subtask4（20pts）：存在一个节点，使得它的度数为 $n-1$；
- Subtask5（30pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le5\times10^5$，$1\le a_i\le10^9$。


title: [COCI2021-2022#3] Lampice

description:
给定一串包含 $n$ 个有特定颜色 $a_i$ 的圣诞灯和一个整数 $k$。

现要从该串中选取一段连续的圣诞灯，要求这段圣诞灯能够恰好从头到尾均分成 $k$ 小段，使得每一小段的颜色相同。

如果有符合的选取方式，请输出每一小段的颜色情况；否则输出 $-1$。

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

第二行，$n$ 个正整数 $a_i$，表示圣诞灯的颜色。

outputFormat:
如果没有符合的选取方式，输出 $-1$。

否则在第一行输出每一小段的长度，并在接下来一行按顺序输出每一小段的颜色。如果有多种符合的选取方式，请输出任意一种。

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

选取前四个圣诞灯 $1,5;1,5$ 或后六个圣诞灯 $2,5,6;2,5,6$。

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

**本题采用子任务捆绑测试。**

- Subtask 1（10 pts）：保证存在连续 $k$ 个相同颜色的圣诞灯。
- Subtask 2（15 pts）：$k=2$。
- Subtask 3（25 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le k \le n \le 50$，$1 \le a_i \le 1000$。

**【提示与说明】**

为了处理多解问题，本题启用自行编写的 [Special Judge](https://www.luogu.com.cn/paste/xevpldj1)，欢迎大家 hack。

**题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _Task 1 Lampice_。**

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


title: [COCI2021-2022#3] Cijanobakterije

description:
一位微生物学家有 $n$ 个蓝藻细菌。这些细菌中有 $m$ 组细菌 $(a_i,b_i)$，表示 $a_i$ 和 $b_i$ 之间有一条生物链。若干条生物链顺次连接之后可组成长链。长链的长度定义为这条长链上的细菌数量。

现可在细菌之间两两添加若干条生物链，使得添加之后的所有生物链均不存在环。

求在进行若干次添加生物链的操作后，最长的长链的长度是多少。

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

接下来的 $m$ 行，每行两个正整数 $a_i,b_i$，表示 $a_i,b_i$ 两个细菌之间有一条生物链。数据保证 $a_i \neq b_i$ 且同一条生物链只会出现一次，同时这 $m$ 条生物链不会存在环。

outputFormat: 输出最长的长链的长度。

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

在 $2$ 和 $6$ 之间添加一条生物链后，最长的长链为 $3-1-2-6-5-7$，长度为 $6$。

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

**本题采用子任务捆绑测试。**

- Subtask 1（15 pts）：$m=n-1$。
- Subtask 2（6 pts）：$b_i=a_i+1$。
- Subtask 3（6 pts）：$1 \le a_i \le 2$。
- Subtask 4（15 pts）：$1 \le n \le 1000$。
- Subtask 5（28 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le m \lt n$，$1 \le a_i,b_i \le n$。

**【提示与说明】**

**题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _Task 2 Cijanobakterije_。**

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


title: [COCI2021-2022#3] Akcija

description:
给定 $n$ 个商品，每个商品有一个价格 $w_i$ 和一个截止期 $d_i$，其中 $d_i$ 表示第 $i$ 个商品必须在第 $d_i$ 分钟之前完成购买。每次购买一个商品均需花费 $1$ 分钟进行下单，在下单之后才视为购买成功。

现可从这 $n$ 个商品中选择若干个（包括 $0$ 个）进行购买（每个商品最多购买一次），视为一种购买方案。

当一种购买方案内的商品数量大于另一种方案时，规定前者更优；当一种购买方案的商品数量与另一种相同且前者的总价格更低时，规定前者更优。求所有符合题意的购买方案中，第 $1 \sim k$ 优的方案的商品数量和总价格各是多少。

inputFormat:
第一行，两个正整数 $n,k$。数据保证 $k$ 不大于符合题意的方案总数。

接下来的 $n$ 行，每行两个正整数 $w_i,d_i$。

outputFormat: 输出共 $k$ 行，其中第 $i$ 行为第 $i$ 优方案的商品数量和总价格。

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

前 $k$ 优的方案为 $\{1,3,4\}$、$\{2,3,4\}$ 和 $\{1,3\}$（用商品编号代替对应商品）。

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

**本题采用子任务捆绑测试。**

- Subtask 1（10 pts）：$k=1$，$w_1=\cdots=w_n$。
- Subtask 2（20 pts）：$k=1$。
- Subtask 3（20 pts）：$k=2$。
- Subtask 4（10 pts）：$1 \le n \le 20$。
- Subtask 5（30 pts）：$1 \le n,k \le 100$。
- Subtask 6（20 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,k \le 2000$，$1 \le w_i \le 10^9$，$1 \le d_i \le n$。

**【提示与说明】**

官方数据每个子任务有 $13$ 个测试点，所需总时限高达 $6.5$ 分钟。为了减少评测机负担，这里每个子任务只选取前两个测试点进行评测。

**题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _Task 3 Akcija_。**

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


title: [RC-05] Xor Matrix

description:
给出一个 $n\times m$ 的矩阵，第 $i$ 行第 $j$ 列填着 $(i-1)m+j$。

求以 $(x,y)$ 为左上角，$(z,w)$ 为右下角的子矩阵的 $k$ 进制下异或和（即不进位加法，比如九进制下 $(45)_9\ \mathrm{xor}\ (87)_9=(33)_9$）。

inputFormat:
**为了减小测试点个数，本题单个测试点内有多个询问。时间限制已经根据询问组数作了相应调整。**

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

接下来一行一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行五个正整数 $x,y,z,w,k$，表示一次询问。

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


title: 「KrOI2021」Feux Follets 弱化版

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

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

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

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

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

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


title: 「MCOI-Zero / AC6-M01」Invasion of Gracemeria

background:
我们的首都 Gracemeria 正在遭受不明势力袭击！

空袭造成的破坏遍布全城。

全机，立刻紧急升空迎击！

---

「Garuda 1，你可以起飞了。」

……

「Garuda 1，升空。Cerberus 队，跑道已经清空，你们准备好了就起飞。」

「所有飞机升空后听从 AWACS 的命令。」

「这不是演习。重复一遍，这不是演习！」

……

「这里是 AWACS Ghost Eye。」

……

「Garuda 1，你没僚机。」

「让我看看……
　Shamrock。」

「你也是单机一架，对吗？」

「很好。
　从现在起你就是 Garuda 2 了。」

「你好，这里是 Garuda 2。」

「没时间自我介绍了，快。
　Garuda 1，加速，我会跟上。」

「尽管给我命令就好。」

「Garuda 队，你们已经可以同 Gracemeria 上空的敌军交战。」

……

**「May the Golden King smiles on us！！」**

$$_{{\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 01} \\\Large\text{Invasion Of Gracemeria}\\\tiny -\textit{ Through the Heart Of a Nation }-$$

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

description:
给定一个长度为 $n$ 的序列 $a$，初始都是 $0$，和一个正整数 $k$。

现有 $q$ 次操作，每次操作给定 $i,v$，表示给序列 $a$ 的后缀 $a_{[i,n]}$ 加上 $v$。

每次操作后，请你输出 **所有数在序列中出现次数的 $k$ 次方和** 对 $20051131$ 取模的结果。

$20051131$ 是质数。

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

接下来 $q$ 行，每行两个整数，表示这次操作的 $i,v$。

outputFormat: $q$ 行，每行一个整数，表示这次操作之后所有数在序列中出现次数的 $k$ 次方和对 $20051131$ 取模的值。

hint:
第一次操作后，有 $5$ 个 $1$，答案为 $5^2=25$。

第二次操作后，有 $1$ 个 $1$ 和 $4$ 个 $2$，答案为 $1^2+4^2=17$。

类似的，答案分别为 $1^2+1^2+3^2=11,1^2+1^2+1^2+2^2=7,5\times 1^2=5$。

---

- Subtask 1（20 pts）：$n,q\leq 2\times 10^3$。
- Subtask 2（40 pts）：$n\leq 2\times 10^3$。
- Subtask 3（40 pts）：无特殊限制。

对 $100\%$ 的数据，保证 $1\leq n,v,k\leq 20051130$，$1\leq q\leq 5\times 10^5$，$1\leq i\leq n$。

idea：Sol1，solution：Sol1，code：Sol1，data：Sol1 & 斜揽残箫


title: 「Wdsr-2.5」第二次月面战争

background:
若干年之前，八云紫策划了第二次月面战争。

作为神社的巫女，灵梦自然有保护人间之里人类的职责。为了能够使得人类免受月面战争可能造成的影响，灵梦决定在博丽神社设立一个结界。

由于结界的影响范围有限，只能覆盖到博丽神社，于是灵梦决定将人间之里的所有居民迁入到神社中去。然而由于居民数目较多，灵梦在组织上出现了一些困难。这时，她找到了外界的你，希望你帮助她解决这个问题。

description:
人间之里可以看做一张 $n$ 个点 $m$ 条边的有向图，而博丽神社在点 $t$ 。然而由于时间差的原因，灵梦不能一次性获取所有居民的位置，于是她会依次受到 $k$ 条消息，每条信息包含一个节点 $x$。

- 如果 $x$ 号节点本来没有居民，那么灵梦得知了有一个居民在 $x$ 号节点。
- 如果 $x$ 号节点本来有居民，那么由于某些原因， $x$ 号节点现在没有居民了。

由于某些原因，在 $t$ 号节点也有可能存在居民。

每当得知一条新的消息后，灵梦都需要快速计算出居民的最快疏散时间，以便于合理安排（此时，你可以认为其他节点上没有居民）。同时为了避免拥挤，以及其他难以预料的困难，灵梦做出了如下规则：

- 每一时刻，每个居民只能沿着一条有向边走一步，或者**停留在原地**。
- 每一时刻，每个节点上，**最多只能有一位居民**。
- 当居民到达了博丽神社，那么**下一时刻**他就可以进入结界以获得庇护。你可以认为，在居民进入结界后他的行程就结束了。

最快疏散时间，指的是**所有居民**全部进入结界的最短用时。

inputFormat:
第一行四个正整数 $n,m,k,t$ ，含义如题所示。

接下来 $m$ 行，每行两个正整数 $u,v$ ，描述一条 $u\to v$ 的有向边。可能出现自环或者重边，请选手自行忽略。

接下来一行，共 $k$ 个整数 $x_i$ ，表示在第 $i$ 条消息中 $x_i$ 号节点是否有居民的情况发生了变化。

outputFormat: 输出共 $k$ 行，每行表示在按照前 $i$ 条消息，疏散所有居民所用的最小疏散时间。

hint:
#### 样例 1 说明

![main1.png](https://i.loli.net/2021/03/26/bWyznVgRc1pqPaf.png)

这张图描述了**初始状态**、**第一次操作**、**第二次操作**的情况。可以发现；

- 第一次操作后， $7$ 号节点最快通过 $7\to 6\to 1$ 到达神社，再花费 $1$ 单位时间进入神社，总共用时 $3$ 单位时间。
- 第二次操作后， $1$ 号节点花费 $1$ 时刻进入神社， $7$ 号节点仍然按照 $7\to 6\to 1$ 到达神社，并花费 $1$ 单位时间进入神社即可。总共花费 $3$ 单位时间。

![main2.png](https://i.loli.net/2021/03/26/sr3kbOWh7PxBway.png)

这张图描述了第三次操作后的情况。

第一时刻， $1$ 进入神社， $2\to 1,7\to 6$ ；第二时刻， $1$ 进入神社， $6\to 1$ ；第三时刻所有人都进入了神社，于是总共花费 $3$ 单位时间。

![main3.png](https://i.loli.net/2021/03/26/IWt7zKPohpFBmfV.png)

这张图描述了第四次操作后的情况。

第一时刻， $1$ 进入神社， $3\to 1,7\to 6$ ， $2$ 不动；第二时刻， $1$ 进入神社， $2\to 1$ ， $6$ 不动。接下来花费 $2$ 时刻全部进入神社，于是总共花费 $4$ 单位时间。

#### 样例 2,3

见下发附件。

#### 数据范围及约定

$$
\def{\bd}{\boldsymbol}
\def{\a}{\texttt{A}}	% 链的性质
\def{\b}{\texttt{B}}	% 菊花图的性质
\def{\p}{\texttt{P}}	% k为正的性质
\def{\n}{\text{无特殊限制}}
\def{\l}{\hline}
\def{\arraystretch}{1.5}\begin{array}{|c|c|c|c|c|}\l
\textbf{数据点} & \bd{n} & \bd{m} & \bd{k} & \textbf{特殊性质} \cr\l
1\sim4 & n\le 8 & m\le 10 & k\le 10 & - \cr\l
5,6 & \n & m=n-1 & \n & \p,\a \cr\l
7,8 & \n & m=n-1 & \n & \p,\b \cr\l
9 & n\le 10^5 & m=n-1 & k\le 10^5 & \p \cr\l
10\sim 12 & n\le 10^3 & m\le 10^3 & k\le 10^3 & - \cr\l
13,14 & n\le 10^5 & m\le 10^5 & k\le 10^5 & \p \cr\l
15\sim 17 & n\le 10^5 & m\le 10^5 & k\le 10^5 & - \cr\l
18\sim 20 & \n & \n & \n & - \cr\l
\end{array}
$$

- 特殊性质 $\texttt{P}:$ 保证只存在出现居民的操作。
- 特殊性质 $\texttt{A}:$ 保证整张图是一条链，但不保证 $t$ 是链的一端。
- 特殊性质 $\texttt{B}:$ 保证除了 $t$ 以外的所有节点，都指向 $t$ 。

对于所有数据，满足 $1\le n\le 10^6; 1\le m\le 1.05\times 10^6;1\le k\le 10^6$ 。保证所有节点可以到达 $t$。


title: [Ynoi Easy Round 2020] TEST_63

description:
给定一棵包含 $n$ 个点的由有根树构成的森林（初始没有边，每个顶点是一棵有根树的根），顶点由 $1$ 到 $n$ 的整数编号表示。
你需要维护森林的轻重链剖分结构，具体如下：

对每个顶点 $w\;(1\le w\le n)$，记其孩子构成的集合为 $\mathrm{children}(w)$，对 $w$ 若 $w$ 不是根则记其父亲为 $\mathrm{father}(w)$；

一个顶点 $w$ 的子树规模 $\mathrm{size(w)}$ 定义为 $1+\sum\limits_{u\in\mathrm{children}(w)}\mathrm{size(u)}$；

一个顶点 $w$ 如果不是叶子（即 $\mathrm{children}(w)\ne\varnothing$），则它的重孩子 $\mathrm{hc}(w)$ 被定义为 $\mathrm{arg}\max_{u\in\mathrm{children}(w)}size(u)\cdot n+\max(u,\mathrm{hc}(u),\mathrm{hc}(\mathrm{hc}(u)),\dots)$，即子树规模最大的孩子（若有多个孩子 $u$ 的子树规模相同则取以 $u$ 为根的子树中，$u$ 所在重链中最大的编号最大）；

重链是一个由顶点构成的序列 $w_1,w_2,\dots,w_k\;(k>0)$，满足条件：

- $w_1$ 是根或 $w_1\ne \mathrm{hc}(\mathrm{father}(w_1))$
- $w_i=\mathrm{hc}(w_{i-1})\;(2\le i\le k)$

对一棵树，每个顶点恰好属于一条重链。
重链的权值为 $w_1\oplus w_2\oplus\dots\oplus w_k$，即序列中顶点编号的按位异或和。

需要依次进行 $2m$ 次操作，操作类型如下：

- 加边：给出两个顶点 $a,b$，令 $b$ 成为 $b$ 所在有根树的根（设顶点构成的序列 $t_1,t_2,\dots,t_l$ 满足 $t_l=b$，且 $t_1$ 为根，$(t_i,t_{i+1}),\;1\le i<l$ 是 $b$ 所在有根树上的有向边，将这些边的方向反转为 $(t_{i+1},t_i)$ 即可令 $b$ 成为根），然后加入 $a$ 到 $b$ 的有向边 $(a,b)$，保证操作前 $a,b$ 在不同的有根树上；
- 删边：给出两个顶点 $a,b$，删除 $a,b$ 间的有向边（可能为 $(a,b)$ 或 $(b,a)$ ），保证这条边之前存在；
- 查询：给出一个整数 $k$，设当前共有 $N$ 条重链，询问将当前存在的所有重链按权值从小到大排序后，第 $((k-1) \mod N)+1$ 小的权值。

inputFormat:
第 $1$ 行有两个整数 `n m` ；

接下来 $m$ 行，每行四个整数 `o a b k` ，若 $o=1$ 则表示先加边 $a,b$，然后查询 $k$，若 $o=0$ 则表示先删边 $a,b$，然后查询 $k$。

outputFormat: 共 $m$ 行，每行一个整数，依次为每次查询操作的结果。

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

本题采用子任务评测。

共 $31$ 个测试点，所有测试点满足 $1\le n\le 10^5$，$1\le m\le 5\times 10^5$，$0\le o\le 1$，$1\le a\le n$，$1\le b \le n$，$1\le k\le n$，$n,m,o,a,b,k$ 均为整数；

测试点可能具有以下性质：

- 性质1：操作使用以下策略随机生成，重复直到生成了 $m$ 行的操作序列：

- 在 $[1,n]$ 中等概率选取三个整数 $x,y,k$，若 $x,y$ 在不同的有根树上，则生成一行 `1 x y k`，否则若 $x$ 不是根，等概率地生成一行 `0 x father(x) k` 或 `0 father(x) x k` 之一，否则不进行操作。

- 性质2：$m=n-1$，且对 $2\le i\le n$，数据的第 $i$ 行为 `1 a i k`，其中 $a$ 在 $[1,i-1]$ 中的整数等概率选取；
- 性质3：$m=n-1$，且对 $2\le i\le n$，数据的第 $i$ 行为 `1 i b k`，其中 $b$ 在 $[1,i-1]$ 中的整数等概率选取；
- 其它对 $n,m$ 的限制。

每个测试点的性质如下：

第1个测试点，$n=10,\;m=50$，满足性质1，共10分；

第2个测试点，$n=100,\;m=500$，满足性质1，共10分；

第3个测试点，$n=1000,\;m=5000$，满足性质1，共10分；

第4个测试点，满足性质2，共15分；

第5个测试点，满足性质3，共15分；

第6~10个测试点，满足性质1，共20分；

第11~31个测试点没有特殊限制，共20分。


title: 「KrOI2021」Feux Follets

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$ 的排列。

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


title: [传智杯 #3 决赛] 课程

background: disangan233 喜欢数数，于是他想让你帮他回答一个问题。

description:
传智专修学院提供 $A,B$ 两个课程，分别有 $n,m$ 个学生报名。报名 $A$ 的学生的编号为 $a_n$，报名 $B$ 的学生的编号为 $b_m$，求有多少个学生同时报名了两个课程。

对于所有数据，$n,m,a_i,b_i\leq 20$，保证每个课程报名的学生编号不会重复。

inputFormat:
输入共 $3$ 行。

第 $1$ 行输入 $2$ 个正整数 $n,m$。

第 $2$ 行输入 $n$ 个正整数 $a_1\ldots a_n$，表示报名课程 $A$ 的学生编号。

第 $3$ 行输入 $m$ 个正整数 $b_1\ldots b_m$，表示报名课程 $B$ 的学生编号。

**学生编号不保证从小到大排序。**

outputFormat: 输出共 $1$ 行 $1$ 个整数，表示答案。

hint:
## 样例解释

我们发现，$1,3,4,5$ 这 $4$ 名学生同时报名了两门课程，所以答案是 $4$。


title: [传智杯 #3 决赛] 序列

background: disangan333 喜欢 disangan233，于是他也想让你帮他数数。

description:
传智专修学院有 $n$ 名同学，每个同学都有一个数字 $a_n$。同时还知道一个常数 $k$ 。

如果有两名同学，第 $i$ 名同学和第 $j$ 名同学，满足 $i<j$ 且 $a_i\times a_j\leq k$，那么这两名同学就被称为“和谐的一对”。请问这些同学中，有多少对“和谐的一对”呢？

对于所有数据，$n \leq 10^3$，$a_i\leq 10^5$，$k\leq 10^9$。

inputFormat:
输入共 $2$ 行。

第 $1$ 行输入两个正整数 $n,k$。

第 $2$ 行输入 $n$ 个正整数 $a_1\ldots a_n$。

outputFormat: 输出共 $1$ 行 $1$ 个整数，表示答案。


title: [传智杯 #3 决赛] 子串

background: disangan233 喜欢字符串，于是 disangan333 想让你找一些 disangan233 喜欢的串。

description:
在传智的开发课堂上，希望您开发一款文档处理软件。

给定 $T$ 组询问，每次给定 $2$ 个长度为 $n,m$ 的只含英文字母的字符串 $a,b$，求 $a$ 在 $b$ 中的出现次数，相同字符不区分大小写。注意 $a$ 是 $b$ 中连续子序列。

对于所有数据，$T\leq 100$，$\sum n\leq \sum m\leq 10^3$。字符串仅由大小或者小写的英文字母组成。

inputFormat:
输入共 $3T+1$ 行。

第 $1$ 行输入 $1$ 个正整数 $T$。

接下来共 $T$ 组输入，每组输入共 $3$ 行。

第 $1$ 行输入 $2$ 个正整数 $n,m$。

第 $2$ 行输入一个长度为 $n$ 的字符串 $a$。

第 $3$ 行输入一个长度为 $m$ 的字符串 $b$。

outputFormat: 输出共 $T$ 行，第 $i$ 行输出 $1$ 个整数，表示询问 $i$ 的答案。

samples:
5
3 10
abc
abcabcabca
2 10
aa
AAaAaaAaAa
5 5
AbCdE
eDcBa
5 5
abcde
ABCDE
3 10
aba
ABaBaAbaBA

hint:
对于第一组输入，出现了 $3$ 次，分别是 `[abc]abcabca`，`abc[abc]abca`，`abcabc[abc]a`；

对于第二组输入，出现了 $9$ 次，分别是 `[Aa]AaaAaAa`，`A[aA]aaAaAa`，`Aa[Aa]aAaAa`，`AaA[aa]AaAa`，`AaAa[aA]aAa`，`AaAaa[Aa]Aa`，`AaAaaA[aA]a`，`AaAaaA[aA]a`，`AaAaaAa[Aa]`。


title: [传智杯 #3 决赛] 打牌

background: disangan233 想和 disangan333 一起打牌，并邀请了一起路过的你。

description:
三名同学在学习编程的休息时间（编号 $1,2,3$）打扑克，每人一开始 $n$ 张牌，牌一共 $m$ 种，若干张相同的牌可以一起出。

一开始由第一个人出，打出自己的牌里最小的牌。接下来，以玩家 1,2,3,1,2,3... 的顺序轮流出牌，每人打出一组比上个人打出的牌大的，自己能打出的最小的牌，若没有则跳过。

牌的大小是这么决定的：一组张数多的牌比张数少的牌大，如果张数同样多，那么点数大的牌比较大。例如，$(1,1,1)>(3,3)>(2,2)>(4)>(1)$。

若一轮中，其余两个人都无法打出牌，则重新下次由打出最后一张牌的人开始打。谁最先打完所有的牌，谁就赢了。请问最后谁会胜利呢？输出胜者的编号。

对于所有数据，$n,m\leq 50$。

inputFormat:
输入共 $4$ 行。

第 $1$ 行输入 $2$ 个正整数 $n,m$。

第 $2$ 到 $4$ 行，每行输入 $n$ 个数，表示每个人一开始的牌。

outputFormat: 输入共 $1$ 行 $1$ 个正整数，表示胜者的编号。


title: [传智杯 #3 决赛] 商店

background: disangan333 想给 disangan233 买一个礼物，于是他和你一起逛商店。

description:
有 $n$ 名同学去逛商店，店里有 $m$ 个物品，第 $i$ 人有 $w_i$ 块钱，第 $i$ 个物品价格 $c_i$ 元。

每个人至多买一个物品，每个物品只能被买一次，问最多有多少人能买到物品。

对于所有数据，$n,m \leq 10^5$，$w_i,c_i\leq 10^9$。

inputFormat:
输入共 $3$ 行。

第 $1$ 行输入 $2$ 个正整数 $n,m$。

第 $2$ 行输入 $n$ 个整数 $w_1\ldots w_n$，$w_i$ 表示第 $i$ 人的钱。

第 $3$ 行输入 $m$ 个整数 $c_1\ldots c_m$，$c_i$ 表示第 $i$ 个物品的价格。


title: [传智杯 #3 决赛] 面试

background: disangan233 和 disangan333 去面试了，面试官给了一个问题，热心的你能帮帮他们吗？

description:
现在有 $n$ 个服务器，服务器 $i$ 最多能处理 $a_i$ 大小的数据。

接下来会有 $k$ 条指令 $b_k$，指令 $i$ 表示发送 $b_i$ 的数据，需要你分配一个空闲的服务器。

请你算出一个序列 $p_k$ 表示指令 $i$ 的数据分配给服务器 $p_i$，且 $p_k$ 的字典序最小；如果无法分配，输出 "-1"。

对于所有数据，$n,k\leq 6$，$a_i,b_i \leq 10$。

inputFormat:
输入共 $3$ 行。

第 $1$ 行输入 $2$ 个正整数 $n,k$。

第 $2$ 行输入 $n$ 个正整数 $a_i$，表示服务器 $i$ 最多能处理的数据大小。

第 $3$ 行输入 $k$ 个正整数 $b_i$，表示指令 $i$。

outputFormat: 输出共 $1$ 行 $k$ 个正整数 $p_1\ldots p_k$，或者输出 "-1"。

hint:
### 样例解释

第 1 条指令分给服务器 1；
第 2 条指令分给服务器 3；
第 3 条指令分给服务器 2；
第 4 条指令分给服务器 4；
第 5 条指令分给服务器 6；
第 6 条指令分给服务器 5。


title: [传智杯 #3 决赛] 序列

background: disangan233 正在数数，他希望你帮他记录数数的序列，并完成一些操作。

description:
你有一个长为 $n$ 的序列 $a$，现在要对其进行 $m$ 次操作。操作分为两种：

1. 给定两个整数 $l,r$，表示询问 $l$ 到 $r$ 的最大连续子段和。
2. 给定三个整数 $l,r,k$，表示将 $l$ 到 $r$ 的 $a_i$ 都按位或上一个 $k$。

对于所有数据，$n,m\leq 10^5$，$-2^{30}\leq a_i,k<2^{30}$，$1\leq l\leq r\leq n$。

注意：负数按照 32 位补码取按位或。

inputFormat:
输入共 $m+2$ 行。

第 $1$ 行输入 $2$ 个正整数 $n,m$。

第 $2$ 行输入 $n$ 个整数 $a_1\ldots a_n$。

接下来 $m$ 行，每行先输入 $1$ 个正整数 $op$，$op=1$ 输入 $2$ 个整数 $l,r$ 表示一次询问，否则输入 $3$ 个整数 $l,r,k$ 表示一次修改。

outputFormat: 输出共若干行，每行共 $1$ 个整数，表示询问的答案。


title: [传智杯 #3 决赛] 旅人1969

background:
在被称为未来的二十一世纪里，只残留着不安与少许的幻想。

永远与须臾的罪人啊，二十世纪的诺亚方舟，承载着期待与不安向着天空飞去呢！

而作为希望的你，在这并不永恒的旅途中，会怎样地前行呢？

description:
一条笔直的公路上有 $n$ 个旅店，第 $i$ 个旅店的坐标是 $i$，每一天早上从旅店出发走最多 $m$ 个距离，同时固定给你一个常数 $k$。

给定 $q$ 组询问，每次给定 $u,v$，求早上从旅店 $u$ 出发到旅店 $v$，途径不超过 $k$ 个旅店（不含起点 $u$）且行走方向不变的方案数。两种方案不同当且仅当存在一个不同的旅店选择，答案对 $998244353$ 取模。

对于所有数据，$n,q\leq 10^5$，$m,k\leq 10^4$，$mk\leq 10^5$，$u,v\leq n$。

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

第一行输入 $4$ 个正整数 $n,m,k,q$。

接下来 $q$ 行，每行输入 $2$ 个正整数 $u,v$，表示一组询问。

outputFormat: 输出共 $q$ 行，每行输入 $1$ 个整数表示答案。


title: [COCI2012-2013#1] DOM

description: 给定一个仅包含大写字母的单词，删除该单词中的以下九个字母：$\texttt{C,A,M,B,R,I,D,G,E}$。

inputFormat: 一行一个字符串，表示给定的单词。

outputFormat: 一行一个字符串，表示删除字母后的字符串。

samples: LOVA LOV

samples: KARIJERA KJ

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

对于 $100\%$ 的数据，保证 $3 \le$ 单词长度 $\le 100$。

#### 【说明】

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

题目译自 **[COCI2012-2013 CONTEST #1](https://hsin.hr/coci/archive/2012_2013/contest1_tasks.pdf)  _T1 DOM_**。


title: [Ynoi2007] rgxsxrs

background: 本题读入量约 15 MB，输出量约 13 MB，请选择合适的输入输出方法。

description:
给定一个长为 $n$ 的序列 $a$，需要实现 $m$ 次操作：

`1 l r x`：表示将区间 $[l,r]$ 中所有 $>x$ 的元素减去 $x$。

`2 l r`：表示询问区间 $[l,r]$ 的和，最小值，最大值。

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

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

之后 $m$ 行每行 $3$ 或 $4$ 个正整数表示一次操作。

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

outputFormat: 对于每个操作 $2$ ，输出一行三个用空格分隔的数表示答案。

hint:
Idea：wangziji&花花，Solution：wangziji&花花，Code：ccz181078，Data：wangziji&花花&ccz181078

注意：本题采用**捆绑测试**，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

对于 $1\%$ 的数据，$n,m\leq 1000$，时限为 3s。

对于另外 $14\%$ 的数据，$a_i\leq 10$，$n,m\leq 2\times10^5$，时限为 3s。

对于另外 $19\%$ 的数据，$a_i\leq 1000$，$n,m\leq 2\times10^5$，时限为 3s。

对于另外 $19\%$ 的数据，$a_i\leq 2\times 10^5$，$n,m\leq 2\times10^5$，时限为 3s。

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


title: [CEOI2011] Treasure Hunt

description:
现在有一棵树，初始时只有一个根节点 $1$，你需要完成下列两种操作：

* `path u s` 表示在 $u$ 下面依次加入了 $s$ 个节点：其中的第 $i$ 个节点作为第 $i-1$ 个节点的孩子（$2\le i\le s$），特别地，第 $1$ 个节点会作为 $u$ 的孩子。设加入前时，树中节点的最大编号为 $n$，则新加入的 $s$ 个点会被依次编号为 $n+1,n+2,\cdots,n+s$；
* `dig u v` 表示询问 $u,v$ 的中点。形式化地，设 $u,v$ 间的距离为 $d$，则你需要求出 $u,v$的路径上，距离 $u$ 为 $\lfloor \frac d2\rfloor$ 的节点编号。

inputFormat:
本题是一道交互题，首先你需要从标准输入读入操作次数 $n$。
接下来 $n$ 次，你会得到以下两种格式的指令之一：

* `P u s` 表示一次 `path u s` 的操作；
* `D u v` 表示一次 `dig u v` 的操作。

对于第一种操作，你不需要输出任何东西。对于第二种操作，你必须给出答案并清空缓冲区后，才可以读取后续操作。

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

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

outputFormat: 对于每一次 `D u v` 的操作，输出一行表示答案，保证至少有一次这样的操作。

hint:
对于 $20\%$ 的数据，保证最终点的编号最大不超过 $5000$，且 $n\le 5000$；
对于 $50\%$ 的数据，保证最终点的编号最大不超过 $400\ 000$；
对于 $100\%$ 的数据，保证最终点的编号最大不超过 $10^9$，且 $n\le 400\ 000$。

#### 说明
题目译自 [CEOI 2011 day 1 T3 _Treasure Hunt_](http://ceoi.inf.elte.hu/probarch/11/trezad.pdf)。


title: 「EZEC-11」等差数列

description:
给你一个长为 $n$，首项为 $a$，公差为 $d$ 的等差数列 $x$。

从 $x$ 中任选两个数 $x_i,x_j$（$i\neq j$），同时满足：

- $x_i+x_j$ 为偶数。
- $x$ 中没有 $\frac{x_i+x_j}{2}$。

那么你就可以将 $\frac{x_i+x_j}{2}$ 加入 $x$ 中，称为一次操作。

**注意：新加入的数也可被选择。**

问你最多能进行几次操作？

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

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

对于每组测试数据，一行三个整数 $n,a,d$。

outputFormat: 对于每组测试数据，一行一个整数表示最多的操作次数。

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

对于第一组数据，$x=[1,2,3]$，无法进行任何操作。

对于第二组数据，$x=[2,4]$，可以选择 $2$ 和 $4$，将 $\frac{2+4}{2}=3$ 加入数列中。

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

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

-  Subtask 1（10 points）：$d=1$。
-  Subtask 2（10 points）：$n=2$。
-  Subtask 3（30 points）：$T\le 10$，$n\times d\le 10^3$，$a=0$。
-  Subtask 4（50 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le 10^5$，$2\le n\le 10^9$，$-10^9\le a\le 10^9$，$1\le d\le 10^9$。


title: [Ynoi2007] rfplca

description:
给定一棵大小为 $n$ 的 $1$ 为根节点的树，树用如下方式给出：输入 $a_2,a_3,\dots,a_n$，保证 $1\leq a_i<i$，将 $a_i$ 与 $i$ 连边形成一棵树。

接下来有 $m$ 次操作，操作有两种：
- `1 l r x` 令 $a_i=\max(a_i-x,1)(l\leq i\leq r)$。
- `2 u v` 查询在当前的 $a$ 数组构成的树上 $u,v$ 的 LCA。

inputFormat:
第一行包含两个数 $n$，$m$。

之后一行 $n-1$ 个数，表示 $a_2,...,a_n$。

之后 $m$ 行，每行三个或四个数，表示一次操作。

**本题强制在线，所有输入的 $l,r,x,u,v$ 均需要异或 $lastans$，其定义为上一次询问操作得到的答案，若之前没有询问操作，则为 $0$。**

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

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

对于 $100\%$ 的数据，满足
$2\leq n,q\leq 4\times 10^5$，$2\leq l\leq r\leq n$，$1\leq x\leq 4\times 10^5$，$1\leq u,v\leq n$。


title: [Ynoi2007] rdiq

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

有 $m$ 次询问，每次询问给定一个区间 $[l,r]$，求 $|\{(a_i,a_j) : l\le i<j\le r \wedge a_i>a_j\}|$。

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

第二行 $n$ 个数，其中第 $i$ 个数 $a_i$ 表示序列第 $i$ 个位置的值。

第三行一个数 $m$。

之后 $m$ 行，每行用两个空格隔开的数，分别表示 $l,r$，表示一次询问，保证 $l\le r$。

outputFormat: 输出 $m$ 行，第 $i$ 行输出一行一个整数，表示第 $i$ 次询问的答案。

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

对于第一次询问，集合为 $\{(3,2)\}$。

对于第二次与第三次询问，集合为 $\{(2,1),(3,1),(3,2)\}$。

对于第四次询问，集合为空集。

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


title: [JDWOI-2] 抢救实验数据

background: 某大型实验中心的一个实验室发生了毒气泄露，现在实验员想要抢救实验数据。

description:
实验中心可以看做一个 $n$ 个点 $m$ 条边的无向联通图。
所有实验员每秒可以走到一个相邻的实验室并**收集**其中的数据，毒气每秒会蔓延到所有的相邻实验室。
当一个实验员**回到了大厅 $s$**，我们称他**抢救**了数据。
实验员不能进入有毒气的实验室（如果他和毒气在同一秒进入实验室也不行）。
**大厅周围有严格的保护措施，不会被毒气蔓延。（具体可以参考样例二）**
现在所有实验员都在大厅 $s$，毒气泄露的实验室为点 $t$。假如有**足够多**的实验员同时出发，请问最多能抢救多少个实验室的数据？

inputFormat:
第一行两个正整数 $n,m$，表示实验中心的点数和边数。
第二至 $m+1$ 行每行两个正整数 $u,v$，代表 $u,v$ 实验室之间有一条边。
第 $m+2$ 行两个正整数 $s,t$，表示大厅和毒气泄露点。

outputFormat: 一行一个整数，表示最多能抢救多少个的实验室的数据。

hint:
**请注意常数因子带来的程序效率上的影响。**

【样例解释一】
只有 2 号实验室可以到达并回来。

【样例解释二】
因为大厅是坚不可摧的，所以 5,6 两个实验室会被毒气蔓延到，而 2,3 两个实验室永远不会被蔓延到。

【样例解释三】
可以被抢救的点为：2,3,4,5,11,12。

【数据范围】
**本题采用捆绑测试**。
对于 $10\%$ 的数据，$2 \leq n,m \leq 20$；
对于 $30\%$ 的数据，$2 \leq n \leq 2000,1 \leq m \leq 10000$；
对于 $70\%$ 的数据，$2 \leq n \leq 2 \times 10^5$；
对于 $100\%$ 的数据，$2 \leq n,m \leq 5 \times 10^6$。

由于读入量很大，这里提供 std 使用的快读模板（提交时需要选择 C++11 及以上)
```cpp
char gc() {
  static char now[1 << 20], *S, *T;
  if (T == S) {
    T = (S = now) + std::fread(now, 1, 1 << 20, stdin);
    if (T == S) return EOF;
  }
  return *S++;
}
template <typename T>
void Read(T &x) {
  x = 0;
  char c = gc();
  while (c < '0' || c > '9') c = gc();
  x = c - '0';
  while ((c = gc()) >= '0' && c <= '9') x = x * 10 + c - '0';
}
template <typename T, typename... Args>
void Read(T &x, Args &... args) {
  Read(x);
  Read(args...);
}
```
使用方法：`Read(n, m)` 或 `Read(x, y, z)` 等，可以读入任意个数，但是不能与 `std::cin` 和 `std::scanf` 一起使用。读入完成后 Windows 系统按 Ctrl+Z，Linux 系统按 Ctrl+D 结束。


title: 「MCOI-06」Gerrymandering

description:
给定正整数 $n,m,k$，能否将一个 $n\times m$ 表格染色，使得每一个颜色形成恰好一个连通块，并且每一个连通块大小为 $k$？

如果存在，请构造一个合法方案。

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

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

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

outputFormat:
输出 $T$ 行，第 $i$ 行含第 $i$ 组数据的答案。如果存在，输出 `YES`，否则，输出 `NO`。

如果存在，接下来输出 $n$ 行，其中每行 $m$ 个正整数，其中每一个正整数小于等于 $10^9$ 并且形成一个大小恰好为 $k$ 的连通块。

hint:
#### 样例 1 解释

数据组 3 的合法输出之一：

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

#### 数据规模与约定

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

 - Subtask 1（20 pts）：$k=1$。
 - Subtask 2（30 pts）：$n=1$。
 - Subtask 3（50 pts）：没有特殊限制。

对于 $100\%$ 的数据，$1\le n,m,k,T,\sum nm\le10^{6}$。


title: 「MCOI-08」Fill In REMATCH

description:
Dream 有一个长度为 $n$（$1\le n\le 10^5$）的整数数组 $a_1,a_2,\dots,a_n$，其中对于 $i=1,2,\dots,n$，满足 $0\le a_i<2^{60}$。

他计算了前缀异或数组 $p_i=a_1\oplus a_2\oplus\dots\oplus a_i$ 以及后缀异或数组 $s_i=a_i\oplus a_{i+1}\oplus\dots\oplus a_n$。

现在 Tommy **一共**将 $p$ 和 $s$ 的 $n$ 个元素换成 $-1$。给定当前的 $p$ 与 $s$ 数组，请恢复任意一组可能为原数组的 $a_1,a_2,\dots,a_n$。

保证存在一组合法解。

inputFormat:
本题有多组数据，第一行一个正整数 $t$，为数据组数。接下来 $t$ 组数据，其中对于每一组数据：

第一行一个正整数 $n$（$1\le n\le 10^5$）。

接下来 $n$ 个整数 $p_1,p_2,\dots,p_n$。

接下来 $n$ 个整数 $s_1,s_2,\dots,s_n$。

outputFormat:
对于每一组数据：

输出 $n$ 个非负整数 $a_1,a_2,\dots,a_n$，满足以上条件。

hint:
对于 $100\%$ 的数据，$1\le n,\sum n\le 10^5$，$\sum [p_i=-1]+\sum [s_i=-1]=n$，**保证有合法解。**

 - Subtask 1（10 pts）：$n\le 4$，$p_i,s_i<2$；
 - Subtask 2（10 pts）：$n\le 100$；
 - Subtask 3（20 pts）：$p_i,s_i<2$；
 - Subtask 4（60 pts）：无特殊限制。


title: [COCI2012-2013#1] F7

description:
有 $N$ 位选手参加一个比赛。每个回合，第一名会得到 $N$ 分，第二名会得到 $N - 1$ 分，以此类推，最后一名会得到 $1$ 分。

现在第 $i$ 位选手初始有 $B_i$ 分。求多少选手经过一个回合，分数有机会变成所有选手中最高的。

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

第一行包含一个正整数 $N$，表示选手总数。

接下来 $N$ 行，每行包含一个整数 $B_i$，表示第 $i$ 位选手的初始分数。

outputFormat: 输出一行一个整数，表示多少选手的分数有机会变成所有选手中最高的。

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

对于 $100\%$ 的数据，$3 \le N \le 3 \times 10^5$，$1 \le B_i \le 2 \cdot 10^6$。

#### 【说明】

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

题目译自 **[COCI2012-2013](https://hsin.hr/coci/archive/2012_2013) [CONTEST #1](https://hsin.hr/coci/archive/2012_2013/contest1_tasks.pdf) _T2 F7_**。


title: [BJWC2014] 珠链

description:
Alex 喜欢玩网络游戏，认为这是智力和体力的综合锻炼。在一次游戏活动中，他意外获得了一个传说中威力极其强大的法宝：珠链。

珠链，顾名思义，就是由许多小珠子串起来的一条链。珠子有很多种颜色。Alex 听说过，只有将珠链打磨纯净，珠链才能发挥最大的威力。

纯净珠链是指这样的珠链：它可以分成若干个长度相等的段，使任何两段的任何相同位置的珠子的颜色均不同，相同位置指珠子在段内的相对位置相同；而且每段的长度以及划分的段数也是有规范的，Alex 记得，每段包含的珠子数目必须在 $L$ 到 $R$ 之间，而且划分的段数不能少于 $S$。

所谓打磨，就是从珠链的首和尾拿掉连续的若干个珠子。打磨后的纯净珠链的威力等于它的每个珠子具有的魔力值之和。

一个珠子的魔力值只与它在打磨前的珠链中的位置有关。在查找和分析了大量实验数据以后，Alex 发现珠子的魔力值等于珠子原来位置编号的约数个数！

兴奋不已的 Alex 想将珠链打磨成威力最大的纯净珠链。然而，马上要参加期末考试的 Alex 来不及计算了，你能否帮助 Alex 算出最大的威力值呢？

inputFormat:
第一行是四个整数 $N,L,R,S$。

第二行是一个长度等于 $N$ 的字符串，表示 Alex 得到的珠链。字符串的第 $i$ 个字符表示珠链的第 $i$ 个珠子的颜色。相同字母表示相同颜色。珠子的位置从 $1$ 编号到 $N$。

**保证输入的字符串只包含大写和小写的英文字母，并且字母区分大小写。**

outputFormat:
输出一行，表示打磨后的纯净珠链的最大威力值。

如果无法打磨成满足要求的纯净珠链，输出 `-1`。

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

能够打磨出的合乎要求的纯净珠链有三种：$\texttt{bc/aa}$，$\texttt{abc/bca}$ 和 $\texttt{bcb/caa}$。其中威力最大的是第三种，其威力值等于 $2 + 2 + 3 + 2 + 4 + 2 = 15$。

如果给出的珠链是纯净珠链，那么可以不打磨。纯净珠链必须能划分成不少于 $S$ 个等长的段且每段长度在 $L$ 到 $R$ 之间。

#### 【数据范围】

对于 $100\%$ 的数据，$1 \le N \le 5 \cdot 10^5$，$1 \le L,R,S \le N$，$0 \le R - L \le 10$。


title: 「RdOI R2」路径权值(distance)

background: 此题读入量较大，请选择合适的读入方式。

description:
给你一棵 $n$ 个点的边带权有根树，根节点为编号为 $1$ 的节点。定义 $u$ 的 $k-son$ 为 $u$ 子树中深度（指经过边数）比 $u$ **恰好**大 $k$ 的所有点。
$m$ 次询问求一个点 $u$ 的 $k-son$ 两两之间距离的和。你需要输出这个值 $\bmod\left(10^9+7\right)$ 的结果。

inputFormat:
第一行两个数 $n,m$。
接下来 $n-1$ 行每行三个数 $u,v,w$，代表 $u,v$ 之间有一条边权为 $w$ 的边。
接下来 $m$ 行每行两个数 $u,k$，代表一个询问。

outputFormat: 对于每个询问输出一行答案。

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

以下是样例中的树。
![](https://cdn.luogu.com.cn/upload/image_hosting/lz4oy8ao.png)

---

**样例 $2$ 解释**

以下是样例中的树。
![](https://cdn.luogu.com.cn/upload/image_hosting/hb45pofr.png)

---

**数据范围**

对于 $20\%$ 的数据，$n,m,k\le100$。
对于 $50\%$ 的数据，$n,m,k\le10^3$。
对于 $80\%$ 的数据，$n,m,k\le10^5$。
对于 $100\%$ 的数据，$1\le n,m,k\le10^6,1\le k\le n,1\le w\le10^5,1\le u,v\le n$，保证给出的是一棵树。


title: [BJWC2017] 太空飞船

background:
21XX 年，秋。

小诚是 THU（Tomorrow Happy University）航天学院船舶设计系本科四年级的学生。为了顺利毕业，小诚仔细阅读了这几年被引用次数最多的十几篇会议论文，打算在权威理论的指导下设计一艘新型太空飞船。

description:
这将是一艘环形的太空飞船，由 $N$ 个舱室顺序组成。第 $i$ 个舱室的设计长度为 $L_i$。

为了给飞船提供能量，要在飞船上装置 $K$ 个太空能量吸收器。根据权威理论，这些吸收器应该尽量均匀地分散在飞船表面。也就是说，小诚要把飞船所有 $N$ 个舱室划分成 $K$ 个部分（每个部分包括连续一段舱室），并给每个部分配置一个能量吸收器。设第 $i$ 个部分舱室的长度之和为 $s_i$，则要令方差尽量小。

可是，这个问题对于已经大学四年级的小诚来说太难了。你能否帮助他完成设计呢？为方便起见，输出方差最小值与 $K^2$ 的乘积。

inputFormat:
输入共两行。

第一行包含两个整数 $N,K$。

第二行包含 $N$ 个以空格分隔的整数 $L_1,L_2,…,L_N$，依次表示每个舱室的长度。

outputFormat: 输出一行一个整数，表示方差最小值与 $K^2$ 的乘积。


title: 「C.E.L.U-03」重构

background: 罗司机最近发现服务器运行速度很慢，于是他准备重构整个服务器的网络以提升效率。

description: 罗司机有 $n$ 台服务器，每个服务器有一个繁忙度 $v_i$。罗司机将用 $n-1$ 条网络将它们连接在一起，于是每台服务器有一个连接网络数量 $d_i$。这个服务器网络运行的总时间是 $\sum\limits_{i=1}^nd_i^2v_i$。请你最小化这个值。

inputFormat:
第一行一个数，$n$。
第二行 $n$ 个数，第 $i$ 个数代表 $v_i$。

outputFormat: 第一行一个数，答案。


title: [CERC2018] The ABCD Murderer

description:
**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [The ABCD Murderer](https://contest.felk.cvut.cz/18cerc/solved/abcd.pdf)**

Oscar 特别喜欢看犯罪电影。他钦佩那些罪犯，因为他们富有创造力。他也想展示他的创造力。但很可惜的是，他没什么经验，也想不出来什么原创伎俩。所以他想从已有的招数中寻找灵感。他一直喜欢看罪犯从报纸上剪下字母，然后用这些字母拼勒索信的桥段。然而 Oscar 根本不想抄袭，所以他自己想了一个这种方法的变体。他觉得把字母一个一个拼成文本既无聊又费时间。所以他决定通过剪下一整个单词的方式拼出自己的勒索信。

Oscar 买来一些主流报纸，这样他几乎就有了无限的单词库。他可以多次剪出任意特定的单词。然而，他还是被报纸中出现的的单词集限制。问题是一些单词根本没在报纸中出现。为了让这项工作更简单，他决定去除勒索信中所有的标点符号和空格并且忽略字母的大小写。他同时允许剪出的单词互相重叠，只需要重叠部分相同。现在 Oscar 想知道他至少要剪下多少次单词才能拼成他想要的勒索信。

inputFormat:
第一行包含一个整数 $L$，表示在报纸中发现的单词数；

下一行包含勒索信的内容 $s$。保证内容非空并且只包含小写英文字母。

接下来 $L$ 行，每行包含一个在报纸中出现的单词 $a_i$，保证只出现小写英文字母。这些单词中没有空串，也没有比勒索信长的单词。所有报纸中单词在输入中出现至少一次。

outputFormat: 输出 Oscar 最少要从报纸中剪下多少次单词才能组成勒索信、如果不能组成，输出 $-1$ 。每个单词都要被记实际从报纸剪下那么多次。

samples:
9
icpcontesticpc
international
collegiate
programming
contest
central
europe
regional
contest
icpc


title: [CERC2018] The Bridge on the River Kawaii

description:
**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/)[ The Bridge on the River Kawaii](https://contest.felk.cvut.cz/18cerc/solved/bridge.pdf)**

在一个遥远的，叫做 Midsommer 的地方，有一条叫做 delta 的小河。河里流的是深紫色的酸，所以不可能在那里游泳。这条河周围有一些小岛，并且有桥连接它们。每座桥都有一个危险系数，表示通过这座桥有多危险。危险系数越高，通过这座桥就越危险。

一位叫做 Richard Hradecki 的侦探兼悬疑小说作家经常需要通过这些桥来追查案件。在所有可能的路径中，他更倾向于选择最安全的一条，也就是这条路径上经过桥的最大危险系数越低越好。

为了规划路线，Richard 经常让你为他找从一个岛到他要调查的岛的最安全路线。为了满足他的需求，你需要连续处理以下三种事件：

- 当地人在两座岛屿之间建了一座新桥；
- 一只酸性的并且毛茸茸的大粉熊 Lug 出现了，并摧毁了一座桥；
- Richard 要求你找两个岛屿之间的最安全路线。

inputFormat:
第一行包含两个整数 $N,Q$。$N$  是岛屿数（岛屿用 $0…N-1$ 标号），$Q$ 是需要处理的事件数。

接下来 $Q$ 行，每行表示一个事件，包含三或四个整数，说明如下：

- $0XYV$：在 $X$ 岛与 $Y$ 岛之间刚建成一座危险系数为 $V$ 的桥；
- $1XY$：连接 $X,Y$ 两岛的桥刚被摧毁；
- $2XY$：Richard 询问从 $X$ 到 $Y$ 的最安全路径。

对于所有类型的询问，$X,Y$ 表示一对合法的岛屿。保证任意两个岛屿之间最多只存在一座直达的桥，要被摧毁的桥在那一刻是存在的。

outputFormat: 对于每个种类为 $2$ 的事件，输出 $X$ 到 $Y$ 最安全路径上经过的最危险的桥的危险系数。如果 $X$ 与 $Y$ 之间没有路径，输出 $-1$。


title: [CERC2018] Clockwork ||ange

description:
**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [Clockwork ||ange](https://contest.felk.cvut.cz/18cerc/solved/clockwork.pdf)**

据百度百科，兔是哺乳类兔形目兔科下属所有的属的总称。毋庸置疑的是，这段文字不是无聊的，因为它们是原始的，并且组织良好。我们农场的兔子生活在有保护的畜栏里，畜栏的边界装饰有精美的花卉装饰品。畜栏里生长着数十个可爱的橙色胡萝卜。兔子繁殖很快（这很正常，每年都有成千上万的兔子出生），我们的导师希望不费力地把它们安置在畜栏里。

畜栏规则地形成一排。在第一个繁殖季开始时，一些畜栏里可能没有兔子。每个繁殖季结束时，都会进行一次精心策划过的兔子搬迁。搬迁遵循一条简单的公式，这个公式取决于一个正整数 $K$，不同的繁殖季 $K$ 值不一定相同。对于所有畜栏，搬迁工作同时进行。在每个畜栏中，大约有一半的兔子被移到这个畜栏右边第 $K$ 个畜栏里。目标畜栏里原来有没有兔子都没有关系。

如果畜栏离这一排最后一个畜栏太近（即离最后一个畜栏的距离小于 $K$ ），那么这个畜栏中的所有兔子都留在原畜栏，不会进行搬迁。

每个畜栏都可以容纳无限只兔子，并且非空的畜栏中总有足够多能够成功繁殖的兔子。

给定第一个繁殖季开始时畜栏被占用的情况。请求出使得所有畜栏中都有兔子的最少搬迁次数。

inputFormat: 输入仅有一行，包含一个长度为 $b$ 的字符串，每个字符表示一个畜栏。字符只有 $0$（空畜栏）和 $1$（有兔子的畜栏）两种。第一个字符表示这一排的第一个畜栏。

outputFormat: 输出使得所有畜栏中都有兔子的最少搬迁次数。如果没有任何一种搬迁方案使得每个畜栏中都有兔子，输出 $-1$。


title: [CERC2018] Reservoir Dog

description:
**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [Reservoir Dog](https://contest.felk.cvut.cz/18cerc/solved/dog.pdf)**

你带你的狗来到你家旁边的一个水库玩。你的狗喜欢玩飞盘，但因为你已经厌烦和你的狗玩飞盘了，所以你很好奇从你扔出飞盘到你的狗捡回飞盘回到你这里的总共用时。所以你把狗牵到你身边，然后开始计时。$T_f$ 毫秒这个时刻，你从高度 $H_f$ 毫米的位置以 $V_f$ 毫米每毫秒的初速度水平丢出飞盘。由于重力，在竖直方向对飞盘的加速度为 $1$ 毫米每二次方毫秒。

在 $T_d$ 毫秒这个时刻，你释放了狗，狗的水平速度最大为 $V_d$ 。狗跑在一个理想平面上，并且它足够聪明，知道如何最小化接飞盘并把它带回你这里的时间。为了达到这个目的，狗可以跳 $H_d$ 毫米高，竖直起跳不影响水平速度。狗接到飞盘后，它就会立刻全速跑向你。当狗跑回你的位置时，你停止计时。注意即使你的狗在空中也要停止计时，也就是说狗位于初始位置上方的时候也停止计时。

你的狗很特殊，因为它可以瞬间获得水平速度（无加速或减速过程的），并且即使在空中也可以改变水平速度大小或反转水平速度方向。由于重力，在竖直方向对你的狗的加速度为 $3$ 毫米每二次方毫秒。

为了简便，假设飞盘和你的狗的大小不计。并且本题中可能用到物体位移公式 $s(t)=s_0+v_0t+0.5at^2$，当然如何使用取决于你。

inputFormat: 输入包含一行六个整数 $T_f,V_f,H_f,T_d,V_d,H_d$。

outputFormat: 输出你测得的时间（单位：毫秒），如果你的答案与标准答案的绝对误差不超过 $10^-$$^4$ 即视为正确。

hint:
$1≤T_f;V_f,H_f,T_d,V_d,H_d≤10^6,H_d<H_f,T_f<T_d$

Clarifications

Q：狗的跳跃过程是怎样的？

A：狗瞬间获得能够跳到 $H_d$ 高度的竖直速度。

Q：当飞盘落在地面上时会继续运动吗？

A：当飞盘落在地面上时瞬间停止运动。


title: [CERC2018] Trees Gump

description:
**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [Trees Gump](https://contest.felk.cvut.cz/18cerc/solved/gump.pdf)**

在 Jumbarian 雨林中，大树的战略地位十分重要。Jumbarian 军队的首领选择了互相距离较近的 $N$ 棵树，并决定这 $N$ 棵树上每棵都要建一个树屋，并安排一支军队。人和材料在树与树之间的运输要依靠双向连接的索道。出于安全因素考虑，从卫星上看任意两条索道之间都没有交叉。

现在已经选出了 $N$ 支军队，并且已经列出了两支军队为一对的清单。在同一对的两支军队应当在同一条索道的两端操控这条索道。军队对数比军队数少一，这就表明这一区域的连通性是有保证的。即，在分配军队后，每一支军队都可以只经过列表中出现的索道到达任意地方。

剩余的工作就是如何在树顶安装索道，才能使得可以按上面的规则安排军队。

inputFormat:
第一行包含一个整数 $N$，表示树顶数和军队数。树顶和军队都用 $0…N-1$ 编号；

接下来 $N-1$ 行，每行两个整数，表示这两支军队应在同一条索道两端；

接下来 $N$ 行给出每个树顶的坐标，第 $i+1$ 行包含两个数 $X_i,Y_i$，表示第 $i$ 棵树的坐标。任意三棵树不会在同一条直线上。

outputFormat:
输出 $N-1$ 行，表示安装索道的方案，每行输出两个数 $x,y$，表示 $x,y$ 两棵树之间建一条索道。

如果有多组解满足题目要求，可以输出任意一组。


title: [CERC2018] Incredible Hull

description:
**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [Incredible Hull](https://contest.felk.cvut.cz/18cerc/solved/hull.pdf)**

在一个皇家赌场中，有一个放有很多老虎机的大房间。赌场老板感觉这个房间结构太简单，这样的话赌徒就有很大机会在没输掉那么多钱之前就离开房间。房间结构需要是固定的，因此老板设计了一个复杂的老虎机摆放和过道设计方式，这样的话人们就更容易在里面迷路了。

房间的形状大致是椭圆形的。如果房间是空的，从房间内部的任何点看，整个房间都可以被看到。房间中的 $N$ 台老虎机每台都可以看做一个点，并且每台都有一个特殊的利润值，每两台老虎机利润值互不相同。老板想要这些老虎机通过过道按下面的方式连通。

已经至少有三台老虎机被建在房间的墙里了，所有这些建在墙里的老虎机必须用直的过道直接相连，以形成一个围绕整个屋子并且闭合的周长路径。房间里剩下的老虎机都在这个闭合的周长路径内部。

这个房间要被直过道分成更小的区域，每个区域都被它自己的周长路径包围。分割古城分成以下两步。

- 第一步操作如下。如果在周长路径上有至少四台老虎机，就要选出两台老虎机作为枢纽。第一台是在周长路径上收益最多的那台老虎机；第二台也在周长路径上，并且距离第一台枢纽老虎机最远。两台老虎机之间的距离用周长路径描述，它等于从一台老虎机到另一台老虎机所经过的过道条数。如果有两台最远的老虎机，那么第二台枢纽老虎机为收益最大的老虎机。周长路径内部的区域被一条连接着这两台枢纽老虎机的过道分成两部分。这两个新形成的小区域的周长路径是包围着这片区域的原周长路径和这条新过道。这个过程重复进行，直到不能新建出新的区域为止；
- 当前一个过程结束后，第二个分割过程开始。这个过程操作如下。对于任意内部没有过道的区域 $A$，考虑在那个区域内部的所有老虎机。如果有，就在收益最多的那台老虎机与所有在 $A$ 的周长路径 $P_A$ 上的老虎机之间建一条过道。这就将这个区域分割成了一些小区域。每个新区域的周长路径包含 $P_A$ 中的一条过道和两条新建的过道。这个过程重复进行，直到不能新建出新的区域为止。
赌场老板想要估计他的设计的利润能力。为了计算，他定义了一个所谓的高收益配置。这个配置是一个最大的老虎机的集合，属于集合的任意两台老虎机都被一条过道直接相连。

这个老板对三个盈利参数十分感兴趣。第一个盈利参数是一个高收益配置的大小，第二个参数是这个设计里高收益配置的个数，第三个参数是至少属于一个高收益配置的老虎机个数。

inputFormat:
第一行包含一个整数 $N$ ，表示老虎机数目。

接下来 $N$ 行，每行两个整数 $X,Y$，表示一台老虎机在房间里的位置。所有老虎机按利润值递减的顺序给出，没有任何三台老虎机共线。

outputFormat: 输出三个盈利参数。


title: [CERC2018] Shooter Island

description:
**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [Shooter Island](https://contest.felk.cvut.cz/18cerc/solved/island.pdf)**

你最近被提拔成上尉，现在你正带着你的士兵在暴风雪中执行一项特别任务。战场有点特别，因为它位于北极圈内的一个巨型冰盖上。你需要和总部协调行动。总部有很多高端的计算机协助你获得战场的最新状态。AI 接口将战场建模为一个网格。每个单元格被它所处行列号唯一确定。由单元格组成的大一些的矩形用对角线顶点的单元格对表示。最初，所有单元格被冰覆盖。

你可以从计算机端接收到两种信息：

1. 关于打击的信息（$t=0$）：你的敌人打击了被单元格 $[x_1,y_1]$ 和 $[x_2,y_2]$ 描述的矩形区域，然后这个矩形区域就被冰冷的北冰洋海水淹没了；
1. 来自你士兵的询问（$t=1$）：他们问是否可以乘船从 $[x_1,y_1]$ 航行到 $[x_2,y_2]$。这条船可以用一个半径为 $0.31416$ 的圆表示。注意船体全部必须一直浮在水上，并且它不能离开战场区域。

你的士兵需要你的帮助！你能可靠地引导他们完成任务吗？

inputFormat:
输入第一行包含一个整数 $L$，表示接下来的行数。

接下来 $L$ 行，每行五个整数 $t,x_1,y_1,x_2,y_2$，$t$是信息的类型，$[x_1,y_1]，[x_2,y_2]$表示各自的单元格。

outputFormat: 对于每个查询，如果可以从 $[x_1,y_1]$ 乘船到达 $[x_2,y_2]$，则输出 $1$，否则输出 $0$。

hint:
样例输入 1 如下图所示：

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

$1≤L≤2×10^5,t ∈ {0, 1}, 1 ≤ x1, x2 ≤ 50,
1 ≤ y1, y2 ≤ 105$


title: [CERC2018] The Lord of the Kings

description:
**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [The Lord of the Kings](https://contest.felk.cvut.cz/18cerc/solved/king.pdf)**

在多年与海外国家的战争后，我们的国家终于成功去除了大多数反动势力和敌人。如此光辉的胜利应该被长时间记住并庆祝。因此，我们的国王宣布将胜利日这一天定为一个公共节日，并且要举行胜利游行。在游行中，军队会跟着国王从他的宫殿出发，访问国家里的每个城市。

国王和他的随从将一种环保的电动直升机作为交通工具。这种直升机有一个缺点，就是它的航程较短。国王让你和你的顾问在一些农场和所有城市中修建停机坪，使得从他的宫殿出发，经过一些停机坪后都可以到达任何城市。然而，建停机坪和基础设施都很费钱。所以要最小化最小化停机坪的修建数量。

此外，由于直升机特殊的设计，国王和他的士兵需要以特殊的方式移动，这就会影响停机坪的数量和位置。

给你一张这个国家的矩形网格地图，其中包含代表村庄，城市和宫殿的网格。同时，也给你了直升机的移动方式——与国际象棋中「车（Rook）」、「后（Queen）」、「象（Bishop）」、「马（Knight）」或「王（King）」之一的移动方式一样（每种棋子的详细移动方式见「数据范围与提示」）。你的任务是求出最少需要在多少农场或城市修停机坪才能够满足国王的需求。国王的宫殿中已经修建了停机坪，因此不需要修一个新的了。

inputFormat:
第一行包含两个整数 $N,M$，表示我们的国家有 $N$ 行 $M$ 列；

第二行两个整数 $X,Y$，表示国王宫殿的位置，接着一个字符，表示移动方式（R——车，Q——后，B——象，N——马，K——王）；

第三行包含一个整数 $T$，表示国家里的城市数；

接下来 $T$ 行，每行包含两个整数 $W,Z$，表示一个城市的位置。所有城市都在不同的网格中，没有城市和宫殿位于同一格。所有既不代表城市也不代表宫殿的格子都是农场。

outputFormat: 输出一行一个整数，表示至少要修建多少停机坪。如果不可能使得国王和他的士兵能够到达每一个城市，输出 $-1$。

hint:
$1 ≤ N, M ≤ 15,1 ≤ T ≤ 10, 1 ≤ X ,W ≤ N,1≤Y, Z≤M$

下图为直升机的运输方式（同国际象棋对应棋子的行棋规则）：
![#1](https://cdn.luogu.com.cn/upload/image_hosting/ip5cnfsa.png)


title: [CERC2018] The Silence of the Lamps

description:
**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [The Silence of the Lamps](https://contest.felk.cvut.cz/18cerc/solved/lamps.pdf)**

在开始之前，如果之前没有见过台灯，那么现在我们把它看做一个用玻璃做的长方体（一个矩形表面的箱子），里面都是煤气。灯的所有边长度都是整数。

曾经，我们的一位讲师曾因破坏路灯而被判刑。他肯定疯了，因为他认为一些路灯向他高声尖叫。

在他的想法里，他遵从一个奇怪的行为模式。他只会认出并且破坏表面不是正方形，并且体积不超过一个给定数值的路灯。后来，在与医生 Clarice 的一次会谈中，他说他非常害怕大型物体和形状过于规则的物体。

你的任务是数出所有满足讲师条件的可能长方体。

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

接下来 $T$ 行，每行一个整数 $N$，表示最大可识别的路灯体积。

outputFormat: 对于每组数据，输出会被破坏的不同路灯个数。


title: [CERC2018] Matrice

description:
**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [Matrice](https://contest.felk.cvut.cz/18cerc/solved/matrice.pdf)**

特工 Sue Thomas 和她的儿子正在网格中寻找 trinity。trinity 是一个新词，正如词素 tri 所示，指的是由网格中单元格组成的三角形。

每个 trinity 是一个正方形的单元格区域去除某对角线上方或下方的部分（一个等腰直角三角形，两腰分别与网格两边分别平行）。对角线可以是主对角线（东南-西北方向），也可以是副对角线（西南-东北方向）。一个合法的 trinity 至少包含三个单元格，并且所有单元格中字符都相同。

inputFormat:
输入的第一行是两个整数 $N,M$，分别表示这个网格的行数和列数。

接下来 $N$ 行每行一个长为 $M$ 的字符串，表示这个网格。

outputFormat: 输出网格中所有不同合法的 trinity 个数。

hint: $1≤N,m≤10^3$，保证输入中出现的字符 ASCII 码在 $33$ 到 $126$ 之间。


title: [CERC2018] Mirrority Report

description:
**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [Mirrority Report](https://contest.felk.cvut.cz/18cerc/solved/report.pdf)**

在物理课上，每个学生都要完成一个半期作业。你选择做一个实验，探究一种稀有的不稳定粒子的性质，这种粒子名为红色粒子。一个红色粒子永远沿直线传播，直到它被镜子反射。

我们的实验可以看做一些单次反射镜组，这些反射镜可以看成二维平面上能够无限延伸的直线。一面单次反射镜只会在粒子第一次到达时将其反射，并且无论从什么方向入射都可以反射，但在此之后，粒子就只会穿过镜子了。

在反射时，遵循反射定律。如果粒子到达了两面反射镜的交点，这个粒子就会崩解，否则会进行反射。

镜子的摆放方式是你的实验老师设定的，你的任务是求出从一个点出发，有多少种出发的方向会让这个粒子到达一个特定的点。

inputFormat:
第一行一个整数包含一个非负整数 $N$，表示镜子的个数；

第二行包含四个整数 $S_x,S_y,E_x,E_y$，表示粒子从 $(S_x,S_y)$ 出发，终点是 $(E_x,E_y)$；

接下来 $N$ 行，每行四个整数 $A_x,A_y,B_x,B_y$，表示第 $i$ 面镜子上的两点。

所有输入的坐标值均在 $[-100,100]$ 之间。 起点和终点不同。从起点或终点到任何镜子的距离均不为零。

保证输入中不存在任何一组合法方案使得：粒子在任何可以反射该粒子的反射镜上的入射点到两面镜子的交点间的距离小于 $10^-$$^4$。

outputFormat: 输出一行一个整数，表示从 $(S_x,S_y)$ 出发，有多少种出发的方向会让这个粒子到达 $(E_x,E_y)$。

hint:
样例 1 如下图：

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

样例 2 如下图：

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

样例 3 如下图：

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

$0≤N≤8$


title: [CERC2018] Game of Stones

description:
**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [Game of Stones](https://contest.felk.cvut.cz/18cerc/solved/stones.pdf)**

Petyr 和 Varys 两个人在玩游戏。游戏中选手从 $N$ 堆石子中轮流取走一些石子。在自己的回合中，Petyr 可以从任意一堆中取走最多 $A$ 个石子，Varys 可以从任意一堆中取走最多 $B$ 个石子。每一轮选手至少要取走一个石子。取走最后一个石子的一方获胜。

游戏已经开始，并且现在 Petyr 要取石子。你的任务是判断在双方均采用最优策略的情况下 Petyr 是否能赢。

inputFormat:
输入的第一行包含三个整数 $N,A,B$，表示有 $N$ 堆石子和两人的限制。

第二行 $N$ 个数 $X_1,X_2,…,X_N$，表示当前所有堆中石子个数。

outputFormat: 输出获胜者的名字。


title: 「EZEC-8」Clean Up

description:
有一个宽度为 $n$ 的区间，第 $i$ 个位置上如俄罗斯方块一样堆着 $a_i$ 个方块。

你可以选择任何一个位置，花费 $k$ 点能量清除这个位置上的至多 $k$ 个方块，同时在与选定位置相距为 $d$ 的位置清除至多 $\max(k-d,0)$ 个方块，相邻两个位置的距离为 $1$。请注意，**$k$ 必须是正整数。**

请问最少要多少能量才能清空整个区间的所有方块。

inputFormat:
输入共两行。

第一行，输入一个整数 $n$。

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

outputFormat: 输出一行，一个数，表示所需的能量最小值。

hint:
**样例解释**

对于第一组样例，一种最佳方案是选择位置 $3$ 花费 $5$ 点能量。

对于第二组样例，一种最佳方案是选择位置 $2$ 花费 $2$ 点能量，再选择位置 $7$ 花费 $2$ 点能量。

-------

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

- Subtask 1（5 points）：$n \leq 2$。
- Subtask 2（20 points）：$n \leq 10^3$，$a_i \neq 0$。
- Subtask 3（20 points）：$a_i \neq 0$。
- Subtask 4（20 points）：$n \leq 10^3$。
- Subtask 5（35 points）：无特殊限制。

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


title: [BJWC2017] 星际穿越

background:
21YY 年，夏。

时过境迁，小诚已是星际联邦（Federation of Planets）太空防御理事会的技术顾问。去年联邦举行大选，新总统刚刚宣誓就任。新政府的主要政策之一是对行政区域进行重新规划，将各个星球之间原有的行政关系精简。

description:
联邦有 $N$ 个星球，新的行政体系结构形如一个二叉树。联邦的行政中心为首都，其他所有星球分成至多两个区域，每个区域内部又是同样的结构。

在此番行政改革之前，每个星球驻扎着一支太空舰队。其中，第 $i$ 个星球驻扎舰队的战斗力是 $F_i$。

在行政改革的同时，太空防御理事会负责调整各个舰队的驻地，以符合军事条例中要求每个行政区域中心驻扎的舰队是区域内战斗力最强舰队的规定。此外，根据军事条例，舰队调整驻地的方式只有一种，就是两个星球的舰队交换驻防。现在，所有星球之间共有 $M$ 条双向的星际航道。只有存在星际航道的两个星球才能进行舰队换防。

为了节省开支，理事会希望总的换防次数尽量少。早在年初，理事会就委托了小诚制定换防计划，但是小诚至今还未完成任务。你能否帮助小诚，使他免于被解职的命运呢？

inputFormat:
第一行包含两个以空格分隔的整数 $N,M$。

第二行包含 $N$ 个以空格分隔的整数 $R_1,R_2,…,R_N$，由空格隔开。$R_i$ 表示星球 $i$ 的直属上级星球编号。对于联邦首都，$R_i$ 用 $0$ 表示。

第三行，$N$ 个互不相同的整数 $F_1,F_2,...,F_N$，由空格隔开。其中 $F_i$ 表示当前驻扎在星球 $i$ 的舰队的战斗力。

接下来 $M$ 行，每行两个整数 $X_i,Y_i$，表示在星球 $X_i$ 和星球 $Y_i$ 之间存在一条星际航道。

输入数据保证星球之间的行政关系形成一个二叉树，任何两个星球之间至多有一条星际航道，且星际航道不会出现自环。

数据保证有解。

outputFormat: 输出一行一个整数，表示总换防次数的最小值。


title: 「MCOI-05」魔仙

background: 你是魔仙堡里的占星魔仙。

description:
魔仙女王的宝石被古娜拉黑暗之神偷走了！古娜拉黑暗之神藏在魔仙堡的 $n$ 个穹顶中的任意一个里面，这 $n$ 个穹顶编号为 $1 \sim n$，第 $i$ 个穹顶可以将其赋予 $a_i$ 的魔力，$a_i$ 必须是整数。

如果所有穹顶的魔力之和为 $0$，之积为 $n$，那么我们称这种情况是可以轻易搜索出古娜拉黑暗之神的。

魔仙女王让占星魔仙求一种赋予魔力的情况使得是可以轻易搜索出古娜拉黑暗之神的。

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

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

接下来 $T$ 行，一行一个整数 $n$。

outputFormat:
输出 $T$ 行，第 $i$ 行含第 $i$ 组数据的答案。

如果有解，输出一行 $n$ 个整数代表构造出的魔力值。否则，输出 `w33zAKIOI`。

**本题采用 Special Judge**，你只需要输出其中一种序列。

hint:
#### 样例 1 解释

$1 +(-1)+2+(-2)=0$，$1 \times (-1) \times 2 \times (-2)=4$。

#### 数据规模与约定

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

 - Subtask 1（5 pts）：$n\le 1$
 - Subtask 2（20 pts）：$n,\sum n\le 100$
 - Subtask 3（75 pts）：没有特殊限制。

对于 $100\%$ 的数据，$1 \le n\le10^6$，$\sum n\le 5\times10^6$，$1\le T\le10^5$。

**本题采用 Special Judge**，你只需要输出其中一种序列。


title: [BJWC2017] 神秘物质

background:
21ZZ 年，冬。

小诚退休以后，不知为何重新燃起了对物理学的兴趣。他从研究所借了些实验仪器，整天研究各种微观粒子。

description:
这一天，小诚刚从研究所得到了一块奇异的陨石样本，便迫不及待地开始观测。在精密仪器的视野下，构成陨石的每个原子都无比清晰。

小诚发现，这些原子排成若干列，每一列的结构具有高度相似性。于是，他决定对单独一列原子进行测量和测试。

被选中的这列共有 $N$ 个顺序排列的原子。最初， 第 $i$ 个原子具有能量 $E_i$。 随着时间推移和人为测试，这列原子在观测上会产生两种变化：

- `merge x e`：当前第 $x$ 个原子和第 $x + 1$ 个原子合并，得到能量为 $e$ 的新原子；
- `insert x e`：在当前第 $x$ 个原子和第 $x + 1$ 个原子之间插入一个能量为 $e$ 的新原子。

对于一列原子，小诚关心的是相邻一段中能量最大和能量最小的两个原子的能量差值，称为区间极差。因此，除了观测变化外，小诚还要经常统计这列原子的两类数据：

- `max x y`：表示当前第 $x$ 到第 $y$ 个原子之间的任意子区间中区间极差的最大值；
- `min x y`：表示当前第 $x$ 到第 $y$ 个原子之间的任意子区间中区间极差的最小值。

其中，子区间指的是长度至少是 $2$ 的子区间。

小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿，你能否帮助他实现上述的观测和测量呢？

inputFormat:
第一行包含两个整数 $N,M$，分别表示最初的原子数目和事件总数。

第二行包含 $N$ 个以空格分隔的整数 $E_1,E_2,...,E_N$，依次表示每个原子的能量。

接下来 $M$ 行，每行为一个字符串和两个整数，描述一次事件，格式见题目描述。

outputFormat: 输出若干行，按顺序依次表示每次 max 和 min 类事件的测量结果。

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

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le M \le 10^5$，$1 \le e,E_i \le 10^9$。

设 $N'$ 为当前时刻原子数目：

- 对于 merge 类事件，$1 \le x \le N' - 1$；
- 对于 insert 类事件，$1 \le x \le N'$；
- 对于 max 和 min 类事件，$1 \le x < y \le N'$。

任何时刻，保证 $N' \ge 2$。


title: 饱食

description:
书虫背包里有 $n$ 只兔兔，第 $i$ 只兔兔被书虫编号为一个由大写字母组成的字符串 $S_i$。

书虫会 +C+，他用 +C+ 编写出了 `random` 函数，随机抽取出了三只兔兔。

不过书虫暂时得了神经性厌食症，书虫能吃下这三只兔兔当且仅当：

- 编号的首字母为 `M`，`C`，`O` 或 `I` 中的任意一个。
- 编号的首字母不能相同。

书虫想问有多少种选择方案使得他能吃下他选的的三只兔兔？

inputFormat:
第一行一个整数 $n$ 代表兔兔个数。

接下来 $n$ 行每行一个字符串 $S_i$ 代表一只兔兔。

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

hint:
#### 样例 1 解释

有如下 $7$ 种选择方式：

- `MINE`，`CRAFT`，`OLYMPIAD`。
- `MINE`，`CRAFT`，`IN`。
- `MINE`，`CRAFT`，`INFORMATICS`。
- `MINE`，`OLYMPIAD`，`IN`。
- `MINE`，`OLYMPIAD`，`INFORMATICS`。
- `CRAFT`，`OLYMPIAD`，`IN`。
- `CRAFT`，`OLYMPIAD`，`INFORMATICS`。

#### 数据规模与约定

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

- Subtask 1（10 pts）：$S_i$ 首字母均为 `M`。
- Subtask 2（30 pts）：$n \le 100$。
- Subtask 3（60 pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le10^5$，$1 \le |S_i| \le 11$，$S_i$ 由大写字母组成。

数据不保证 $S_i$ 互不相同。


title: [NOI Online 2021 提高组] 愤怒的小 N

description:
极度愤怒的小 N 通关了一款游戏来泄愤。

这款游戏共有 $n$ 关，分别为第 $0$ 关、第 $1$ 关、第 $2$ 关、$\cdots$、第 $n-1$ 关。这些关卡中有一些是普通关卡，另一些则是奖励关卡。

这款游戏中普通关卡与奖励关卡的分布比较特殊。如果用字符 $\texttt{a}$ 表示普通关卡，用字符 $\texttt{b}$ 表示奖励关卡，那么第 $0$ 关、第 $1$ 关、第 $2$ 关、$\cdots$、第 $n-1$ 关依次排列形成的字符串是一个无穷字符串 $s$ 的前缀，且 $s$ 可以按照如下方式构造：

1. 初始时 $s$ 为包含单个字符 $\texttt{a}$ 的字符串。

2. 将 $s$ 的每个字符 $\texttt{a}$ 替换成字符 $\texttt{b}$，每个字符 $\texttt{b}$ 替换成字符 $\texttt{a}$ 得到字符串 $t$，然后将 $t$ 拼接到 $s$ 后。
3. 不断执行2. 得到的字符串就是最终的 $s$。

可以发现 $s=\texttt{abbabaabbaababba}\cdots$，所以这款游戏的第 $0$ 关是普通关卡，第 $1$ 关
是奖励关卡，第 $2$ 关是奖励关卡，第 $3$ 关是普通关卡，以此类推。

通过游戏的第 $i$ 关可以得到 $f(i)$ 分，其中 $f(x)=a_0+a_1x+a_2x^2+\cdots+a_{k-1}x^{k-1}$
是一个固定的 $k-1$ 次多项式。

小 N 通关时一气之下通过了所有奖励关卡而忽略了所有普通关卡，然后就把游戏卸载了。现在回想起来，他想要知道他在卸载游戏前的总得分对 $10^9+7$ 取模后的结果。

inputFormat:
第一行一个正整数 $n$，表示游戏的关卡数目。为方便，$n$ 以二进制表示给出。

第二行一个正整数 $k$，表示多项式的次数加一。

第三行 $k$ 个非负整数，分别为 $a_0,a_1,a_2,\cdots,a_{k-1}$，表示多项式的各项系数。

outputFormat: 一行一个非负整数，表示小 N 卸载游戏前的总得分对 $10^9 + 7$ 取模后的结果。


title: [NOI Online 2021 提高组] 积木小赛

description:
Alice 和 Bob 最近热衷于玩一个游戏——积木小赛。

Alice 和 Bob 初始时各有 $n$ 块积木从左至右排成一排，每块积木都被标上了一个英文小写字母。

Alice 可以从自己的积木中丢掉任意多块（也可以不丢）；Bob 可以从自己的积木中丢掉最左边的一段连续的积木和最右边的一段连续的积木（也可以有一边不丢或者两边都不丢）。两人都不能丢掉自己所有的积木。然后 Alice 和 Bob 会分别将自己剩下的积木按原来的顺序重新排成一排。

Alice 和 Bob 都忙着去玩游戏了，于是想请你帮他们算一下，有多少种不同的情况下他们最后剩下的两排积木是相同的。

两排积木相同，当且仅当这两排积木块数相同且每一个位置上的字母都对应相同。

两种情况不同，当且仅当 Alice（或者 Bob）剩下的积木在两种情况中不同。

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

第二行一个长度为 $n$ 的小写字母串 $s$，表示 Alice 初始的那一排积木，其中第 $i$ 个字母 $s_i$ 表示第 $i$ 块积木上的字母。

第三行一个长度为 $n$ 的小写字母串 $t$，表示 Bob 初始的那一排积木，其中第 $i$ 个字母 $t_i$ 表示第 $i$ 块积木上的字母。

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

hint:
对于所有测试点：$1\le n \le 3000$，$s$ 与 $t$ 中只包含英文小写字母。

测试点 $1$ 满足：$n\le3000$，$s$ 与 $t$ 中只包含同一种字母。

测试点 $2,3,4$ 满足：$n\le100$。

测试点 $5,6,7$ 满足：$n\le500$。

测试点 $8,9,10$ 满足：$n\le3000$。

感谢 [w33z8kqrqk8zzzx33](https://www.luogu.com.cn/user/220037) 提供测试数据。


title: [NOI Online 2021 入门组] 切蛋糕

description:
Alice、Bob 和 Cindy 三个好朋友得到了一个圆形蛋糕，他们打算分享这个蛋糕。

三个人的需求量分别为 $a,b,c$，现在请你帮他们切蛋糕，规则如下：

1. 每次切蛋糕可以选择蛋糕的任意一条直径，并沿这条直径切一刀（注意切完后不会立刻将蛋糕分成两部分）。

2. 设你一共切了 $n$ 刀，那么你将得到 $2n$ 个扇形的蛋糕（特别地，切了 $0$ 刀被认为是有一个扇形，即整个圆形蛋糕），将这些蛋糕分配给 Alice，Bob 和 Cindy，要求每个扇形蛋糕只能完整地分给一个人。

3. 三人分到的蛋糕面积比需要为 $a:b:c$（不保证是最简比例，且如果 $a:b:c$ 中某个数为 $0$，表示那个人不吃蛋糕）。

为了完成这个任务，你至少需要切几刀？

inputFormat:
本题单个测试点包含多组数据。

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

接下来 $T$ 行，每行包含三个整数 $a,b,c$，表示三人的需求量。

outputFormat: 输出 $T$ 行，第 $i$ 行的输出表示第 $i$ 组数据中你至少需要切蛋糕的次数。

hint:
### 样例 $1$ 解释
![](https://cdn.luogu.com.cn/upload/image_hosting/i3pai9va.png)

### 数据范围与提示
$30\%$ 的数据满足：$a=b=0$。

$60\%$ 的数据满足：$a=0$。

$100\%$ 的数据满足：$1\le T\le 10^4，0\le a,b,c\le 10^8$，保证 $a+b+c>0$。

数据由 [SSerxhs](https://www.luogu.com.cn/user/29826) 提供。


title: [NOI Online 2021 提高组] 岛屿探险

description:
凇睦是一个喜欢探险的女孩子，这天她到一片海域上来探险了。

在这片海域上一共有 $n$ 座岛屿排成一排，标号为 $1,2,3, \ldots ,n$。每座岛屿有两个权值，分别为劳累度 $a_i$ 和有趣度 $b_i$。

对于一座劳累度为 $a$，有趣度为 $b$ 的小岛，如果这个小岛满足 $(a\oplus c) \leq \min(b,d)$，凇睦到这座岛探险就会感到开心，其中 $c$ 表示凇睦到岛上去之前就有的劳累度（称作初始劳累度），同理 $d$ 代表凇睦的初始有趣度。$\oplus$ 表示二进制异或（即二进制表示下不进位的加法）。

为了玩的更尽兴，凇睦会向你询问 $q$ 次，每次给出一个区间 $[l_i,r_i]$ 和两个数 $c_i,d_i$，你需要告诉凇睦若她的初始劳累度为 $c_i$，初始有趣度为 $d_i$，则有多少个标号在 $[l_i,r_i]$ 这个区间内的岛屿能使凇睦探险时感到开心。

inputFormat:
第一行两个正整数 $n,q$ 分别表示岛屿的数量和询问的数量。

接下来 $n$ 行，每行两个整数 $a_i,b_i$ 分别表示第 $i$ 座岛屿的劳累度和有趣度。

接下来 $q$ 行，每行四个正整数 $l_i,r_i,c_i,d_i$ 分别表示区间左端点，区间右端点，初始劳累度与初始有趣度。

outputFormat: 输出一共 $q$ 行，每行一个整数对应一个询问的答案。


title: [NOI Online 2021 入门组] 吃豆人

description:
有一个 $n$ 行 $n$ 列的正方形点阵，左上角点坐标为 $(1, 1)$，右下角点坐标为 $(n, n)$。

点阵中每个整点上都有数量不一的豆子，坐标为 $(i, j)$ 的点上有 $a_{i,j}$ 个豆子。

你可以放置吃豆人，可以将点阵中任意的整点作为吃豆人的初始位置，再给定左上、左下、右上、右下之一作为吃豆人的初始方向。

吃豆人会不断沿初始方向行进，吃光遇到的所有豆子，直到碰到点阵的边界，此时：

1. 如果吃豆人处于正方形点阵四个角之一的位置，那么就会停止行动；

2. 否则，吃豆人的行进路线将以这条边界为镜面发生反射，下图展示了一个路径某两次发生反射的例子：

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

现在，你需要放置两个吃豆人，求两个吃豆人最多共能吃到多少个豆子？注意同一个豆子只能被吃一次。

inputFormat:
第一行包含一个整数 $n$，表示点阵大小。

接下来 $n$ 行，每行包含 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示 $a_{i,j}$。

outputFormat: 输出一行一个整数，表示两个吃豆人最多共能吃到的豆子数量。

hint:
### 样例 1 解释

在 $(1, 1)$ 和 $(1, 3)$ 位置放置吃豆人，初始方向分别为右下和左下，即可吃到位于
$(1, 1)$，$(1, 3)$，$(2, 2)$，$(2, 4)$，$(3, 1)$，$(3, 3)$，$(4, 2)$，$(4, 4)$ 位置上的豆子，总个数为 $132$，
达到最大，路径分别如下图绿线和红线所示：

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

### 数据范围

对于 $30\%$ 的数据，$n\leq 3$。

对于 $60\%$ 的数据：$n\leq 100$。

对于 $100\%$ 的数据：$2\leq n\leq 1000$，$0\leq a_{i,j}\leq 1000$。

数据由 [SSerxhs](https://www.luogu.com.cn/user/29826) 和 [Karry5307](https://www.luogu.com.cn/user/60990) 共同提供。

感谢 [Silence_water](https://www.luogu.com.cn/user/338630) 提供一组 hack 数据。


title: [NOI Online 2021 入门组] 重力球

description:
“重力球”游戏在一块 $n\times n$ 的正方形区域中进行，记从上往下第 $i$ 行，从左往右第 $j$ 列的位置为 $(i,j)$。

正方形区域中存在 $m$ 个障碍，第 $i$ 个障碍占据位置 $(x_i,y_i)$，此外，正方形区域的边界外都是障碍。

现在有两个小球，位置分别是 $(a,b)$ 和 $(c,d)$，在游戏中你可以进行如下操作：

- 指定上、下、左、右中的一个方向，将重力方向“切换”为这个方向。此时两个小球会同时向这个方向移动，直到碰到障碍。

你要用最少的操作次数使得两个小球到达同一个位置。

现有 $q$ 局游戏，每局游戏中只有小球的初始位置不同，而障碍位置是不变的，你需要对每局游戏都求出最小操作次数，或报告无解。

inputFormat:
第一行包含三个整数 $n,m,q$，分别表示矩形区域大小，障碍个数和游戏局数。

接下来 $m$ 行，每行包含两个整数 $x_i,y_i$，表示位置 $(x_i,y_i)$ 上有一个障碍。数据保证所有障碍所处的位置互不相同。

接下来 $q$ 行，每行四个整数 $a,b,c,d$，表示一局游戏中两个小球的初始位置，保证初始位置不存在障碍。

outputFormat: 输出共 $q$ 行，第 $i$ 行输出一个整数表示第 $i$ 局游戏需要的最小操作次数，如果无解则输出 `-1`。

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

该样例中障碍分布如图中红叉所示。

第一组询问中只需将重力改向上（或改向下）即可使两球同时到达。

第二组询问中两球已经在同一位置故不需操作。

第三组询问中改变3 次重力的方向，依次改为向左、向下、向左，小球移动路线分别如图中粉色、橙色、棕色线所示：

![](https://cdn.luogu.com.cn/upload/image_hosting/7nngrov0.png)
### 数据范围与提示
对于 $20\%$ 的数据：$n,m\le 2$。

对于 $50\%$ 的数据：$n,m\le30$。

对于另外 $30\%$ 的数据：$q=1$。

对于 $100\%$ 的数据：$1\le n,m\le250，1\le q\le10^5，1\le x_i,y_i,a,b,c,d\le n$。

数据由 [SSerxhs](https://www.luogu.com.cn/user/29826) 提供。

数据参考了 小喵喵不喜欢计算几何 2020 ICPC 区域赛（南京）A 题的构造方案，在此表示感谢。


title: 「EZEC-10」Covering

description:
给你一个 $n\times m$ 的棋盘和 $k$ 张 $1\times 2$ 的纸片，编号 $1$ 到 $k$。

你可以任意选择数量在 $[l,r]$ 内的纸片，并按照编号从小到大的顺序，依次横放或竖放在棋盘上。

**注意：后放的纸片会覆盖在先放的纸片上。**

给定最终棋盘中每个格子上的纸片编号，求满足条件的不同方案数，并对 $10^9+7$ 取模。

**两种方案相同，当且仅当两方案选择的纸片数量、纸片编号及每张纸片的摆放位置均相同。**

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

对于每组测试数据：

- 第一行五个整数 $n,m,k,l,r$。
- 后 $n$ 行每行 $m$ 个整数，表示最终棋盘中每个格子上的纸片编号，若某格子未被覆盖则编号记为 $0$。
- **数据保证至少存在一种可行的方案。**

outputFormat:
对于每组数据：

- 一行一个整数，表示方案数对 $10^9+7$ 取模的结果。

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

不难发现只能取编号为 $1,2,3$ 的纸片，此时共有 $2$ 种方案：

$1:(1,1)\to (1,2)$，$2:(1,2)\to (2,2)$，$3:(2,1)\to (2,2)$；

$1:(1,1)\to (2,1)$，$2:(1,2)\to (2,2)$，$3:(2,1)\to (2,2)$。

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

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

-  Subtask 1（5 points）：$r=1$。
-  Subtask 2（10 points）：$n,m,k\le 5$。
-  Subtask 3（15 points）：$l=k$。
-  Subtask 4（20 points）：$n\times m\le 10^3$。
-  Subtask 5（50 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le 10$，$2\le n,m,k\le 10^3$，$1\le l\le r\le k$。


title: Virtual Self

background:
![Virtual Self](https://cdn.luogu.com.cn/upload/image_hosting/16xzq9r9.png)

> Lately, I've been hearing the cries of the angels when I close my eyes
>
> Remember?

description:
Technic_Angel 想用粒子来制作一支美丽的水晶。Pathselector 告诉她，一支水晶由 $m$ 簇粒子合成，其中每一簇粒子都有美丽度（一个小于 $2^w$ 的非负整数，其中 $w$ 为给定正整数），而一支水晶的美丽度就是合成它的所有粒子的美丽度的异或和。

Technic_Angel 有许多粒子：对于每一个 $i\in[0,2^w)\cap\Z$，她都有恰好 $v_i$ 簇美丽度为 $i$ 的粒子。现在 Technic_Angel 想要知道，有多少种方案能够合成一支美丽度为 $k$ 的水晶呢？（两种方案不同，当且仅当有一簇粒子在一种方案中被使用而在另一种方案中没有；所有粒子都互不相同）可惜她并不会这个问题，于是她找到了擅长 OI 的你。

在你花 $0.01\mu s$ 切掉这道题后，异常惊喜的 Technic_Angel 想要让你对所有 $k\in[0,2^w)\cap\Z$ 都解决上面的问题。但由于答案过于巨大，她只要求你告诉她对于所有的 $i$，$((i+1)f(i))\bmod998244353$ 的异或和，其中 $f(i)$ 代表合成一支美丽度为 $i$ 的水晶的方案数。即
$$
(f(0)\bmod P)\otimes(2f(1)\bmod P)\otimes\cdots\otimes(2^wf(2^w-1)\bmod P)
$$
其中 $P=998244353$，$\otimes$ 代表异或。注意是取模后的异或和而非异或后再取模。

inputFormat:
第一行两个正整数 $m,w$，分别代表合成水晶所需的粒子数目以及问题中的参数。

第二行 $2^w$ 个正整数，第 $i$ 个整数代表 $v_{i-1}$。

outputFormat: 一行一个整数，代表 $((i+1)f(i))\bmod 998244353$ 的异或和。


title: StickSuger

background: YSGHYYDS

description:
YSGH 给你一个长度为 $n$ 的字符串 $S$。设 $S_x$ 表示字符串 $S$ 的第 $x$ 个字符。你可以选择一个二元组 $(i,j)$，然后交换 $S_i$ 和 $S_j$。二元组 $(i,j)$ 是合法的当且仅当 $1\leq i<j\leq n$ 并且交换后的字符串的字典序比原串大。

对于两个字符 $c_0,c_1$，称 $c_0>c_1$ 当且仅当 $c_0$ 的 ASCII 码大于 $c_1$ 的 ASCII 码。

对于两个长度为 $n$ 的字符串 $S,T$，$S$ 的字典序大于 $T$ 当且仅当存在一个 $i\in [0,n-1]$ 使得 $\forall j\in[1,i],S_j=T_j$， 并且 $S_{i+1}>T_{i+1}$。

如果存在多种合法方案，输出最大的二元组。

对于两个二元组 $(i_1,j_1)$，$(i_2,j_2)$，称  $(i_1,j_1)$ 小于 $(i_2,j_2)$ 当且仅当 $i_1<i_2\lor(i_1=i_2\land j_1<j_2)$。

如果不存在合法方案，则输出 `-1`。

保证 $S$ 只包含小写英文字母。

inputFormat:
第一行，一个正整数 $n$，表示字符串 $S$ 的长度。

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

outputFormat:
如果无解，输出 `-1`。

否则一行输出两个整数 $i,j$ 表示最大的合法二元组 $(i,j)$。

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

如果选择二元组 $(2,3)$，交换 $S_2$ 和 $S_3$ 后的字符串为 `abc`，字典序比 `acb` 小，所以不合法。

如果选择二元组 $(1,3)$，交换 $S_1$ 和 $S_3$ 后的字符串为 `bca`，字典序比 `acb` 大，是合法的。

虽然 $(1,2)$ 也是合法的，但是没有 $(1,3)$ 大。所以答案是 $(1,3)$。

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

容易看出任何一个二元组都不合法。

---

**【数据范围】**

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

对于 $100\%$ 的数据，$1\leq n\leq 10^6$，$S$ 只包含小写英文字母。

- Subtask 1（4 points）：$S$ 只包含一种字符。
- Subtask 2（10 points）：$n\leq 100$。
- Subtask 3（16 points）：$n\leq 500$。
- Subtask 4（25 points）：$n\leq 5000$。
- Subtask 5（18 points）：$n\leq 10^5$。
- Subtask 6（27 points）：$n\leq 10^6$。


title: 不条理狂诗曲

background: YSGHYYDS

description:
YSGH 有一个长度为 $n$ 的非负整数序列 $a$，定义 $f(l, r)$ 表示从 $a$ 序列的区间 $[l, r]$ 选择若干不相邻的数的和的最大值。

YSGH 想知道 $\displaystyle \left[ \sum_{l = 1}^{n} \sum_{r = l}^{n} f(l, r) \right] \bmod ({10}^9 + 7)$ 。

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

第二行，$n$ 个非负整数 $a_1, a_2, \ldots , a_n$。

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


title: Reboot from Blue

background: YSGHYYDS

description:
数轴上有 $n$ 个加油站，第 $i$ 个位于 $x_i$，油价是每升 $c_i$ 元。

YSGH 和他的车一开始位于坐标 $s$，它想去坐标 $t$（$s < t$），车的油箱一开始是空的，保证坐标 $s$ 有加油站。

假设车的油箱容量无限大，一升油能走距离 $1$。

他想知道他需要花费的最小费用。

inputFormat:
第一行，三个整数 $n, s, t$，意义同题面描述。

接下来 $n$ 行，每行两个整数 $c_i, x_i$，分别表示第 $i$ 个加油站的油价和坐标。

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

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

最优方案是在第一个加油站加 $1$ 升油到第二个加油站。

在第二个加油站加 $3$ 升油到第三个加油站。

在第三个加油站加 $3$ 升油到终点。

答案是 $10 + 2 \times 3 + 1 \times 3 = 19$。

---

**【数据范围】**

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

对于 $100 \%$ 的数据，$1 \le n \le {10}^5$，$-{10}^9 \le x_i, s, t \le {10}^9$，$1 \le c_i \le {10}^9$，$s < t$，保证坐标 $s$ 有加油站。

- Subtask 1（10 points）：$n \le 20$。
- Subtask 2（30 points）：$n \le 5000$。
- Subtask 3（20 points）：$c_i$ 在 $[1, {10}^9]$ 中等概率随机。
- Subtask 4（40 points）：无特殊限制。


title: 50 年后的我们

background: YSGHYYDS

description:
YSGH 给一场比赛出了 $n$ 道题，第 $i$ 道题的难度为 $d_i$，价值为 $c_i$。

有 $m$ 个可能参赛的选手。第 $i$ 个选手有 $p_i$ 的概率会参加比赛。若第 $i$ 个选手参加比赛，则该选手会恰好通过难度在 $l_i$ 到 $r_i$ 之间（包括 $l_i$ 和 $r_i$）的所有题目。

比赛组委会最终给 YSGH 的奖金为所有题中，有选手通过的题的价值之和的 $k$ 次幂。特别地，我们定义 $0$ 的 $0$ 次幂等于 $1$。

YSGH 想让你帮他求出奖金的期望。

令 $P=998244353$，设一个有理数 $x$ 表示成最简分数的形式为 $\frac{a}{b}$，若 $\gcd(b,P)=1$，则存在唯一的整数 $c$（$0 \le c < P$）满足 $b c \equiv a \pmod{P}$，我们称 $x$ 在模 $P$ 意义下的值为 $c$。

可以证明，在仅给出 $p_i$ 模 $P$ 意义下的值时，答案仍然在模 $P$ 意义下唯一存在。

inputFormat:
第一行，三个整数 $n,m,k$，表示题目数量，可能参赛的人数，以及计算奖金需要的参数。

接下来 $n$ 行，第 $i$ 行两个整数 $d_i, c_i$，分别表示第 $i$ 道题的难度和价值。

接下来 $m$ 行，第 $i$ 行三个整数 $l_i, r_i, p_i$，分别表示第 $i$ 个选手通过的题的难度区间，以及来参加比赛的概率在模 $P$ 意义下的值。

outputFormat: 一行，一个整数，表示奖金的期望在模 $P$ 意义下的值。


title: 再生之青

background: YSGHYYDS

description:
YSGH 有一个大小为 $n$ 的树和一个长度为 $m$ 的序列。

树上每个点 $i$ 有颜色 $c_i$ 和价值 $a_i$，颜色两两不同，**保证叶子个数不超过** $\boldsymbol{20}$。

序列第 $i$ 个位置也有一个颜色 $d_i$ 和价值 $b_i$，颜色也两两不同（但树和序列颜色可能会相同）。

YSGH 想从树上选一条链和序列的一个区间满足一个颜色最多只能出现一次，他想知道他能选出来的最大的价值和。

inputFormat:
第一行，两个正整数 $n, m$，分别表示树的大小和序列长度。

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

接下来一行，每行 $n$ 个正整数，第 $i$ 个表示 $c_i$。

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

接下来一行，每行 $m$ 个正整数，第 $i$ 个表示 $d_i$。

接下来一行，每行 $m$ 个正整数，第 $i$ 个表示 $b_i$。

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

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

最优方案是选择树的 $1, 2, 3, 4$ 号节点和序列的第 $2, 3$ 个位置。

价值和是 $10 + 2 + 3 + 7 + 1 + 7 = 30$。

---

**【数据范围】**

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

对于 $100 \%$ 的数据，$1 \le n \le 5 \times {10}^4$，$1 \le m \le 5 \times {10}^5$，$1 \le c_i, d_i \le n + m$，$1 \le a_i, b_i \le {10}^9$，保证树的叶子个数不超过 $20$。

+ Subtask 1（10 points）: $n, m \le 500$。
+ Subtask 2（10 points）: $n, m \le 1000$。
+ Subtask 3（10 points）: $n, m \le 5000$。
+ Subtask 4（20 points）: 满足树的第 $i$ 条边连接的是 $i$ 和 $i + 1$。
+ Subtask 5（15 points）: $m \le {10}^5$。
+ Subtask 6（35 points）: 无特殊限制。


title: 至曾是英雄的您

background: YSGHYYDS

description:
YSGH 有一个 $n\times m$ 的围棋棋盘，初始时，每个位置要么是空的，要么有一个黑棋棋子。**保证黑棋是连通的。**

在围棋中，一个棋子的「气」是与它相邻的所有**空**位置构成的集合。

设棋盘上第 $i$ 行第 $j$ 个位置为 $(i,j)$。

两个分别在 $(i_1,j_1)$ 和 $(i_2,j_2)$ 的**同色**棋子如果满足 $|i_1-i_2|+|j_1-j_2|=1$，就认为是相邻的，也就是在同一个连通块里。

一个连通块的「气」是这个连通块中所有棋子的「气」的并集。

白方走一步棋是合法的，当且仅当走完这手棋之后这个棋子所在连通块的「气」大于等于 $1$ 或者黑棋连通块的「气」等于 $0$。

比如下图，绿色的位置都是黑棋连通块的「气」。

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

「活棋」的定义：无论对方连续走多少手棋，在每步棋都是合法的情况下，该连通块的「气」都大于等于 $1$。

请你判断这个黑棋连通块是否是「活棋」。

如果是，输出 `YES`，否则输出 `NO`。

**本题有多测。**

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

对于每组数据：

第一行，两个正整数 $n, m$，表示棋盘的大小为 $n \times m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串。第 $i$ 行第 $j$ 个字符表示棋盘上位置为 $(i, j)$ 的地方是否有棋子。`.` 表示空格，`*` 表示黑棋子。

outputFormat: 如果黑棋是「活棋」，输出 `YES`，否则输出 `NO`。

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

第 1 组数据：

白棋依次走 $(1,1),(2,1),(3,2),(3,3),(3,4),(1,5),(2,5),(1,3)$ 即可使得黑棋连通块的「气」变成 $0$ 了。

不妨用 `@` 表示白棋，那么最终局面就是：

```plain
@*@*@
@***@
.@@@.
```

第 2 组数据：

比方说白棋先走 $(1,1)$ 那么白棋之后就再也走不到 $(1,3)$ 和 $(2,1)$ 了，导致黑棋的「气」永远大于等于 $1$，所以黑棋是「活棋」。

第 3 组数据：

最终使得黑棋连通块的「气」等于 $0$ 的局面：

```plain
@*@@.
@***@
**@**
*@.@*
**@**
*****
```

---

**【数据范围】**

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

对于 $100 \%$ 的数据，$1 \le n, m \le 2 \times {10}^3$，$1 \le T \le {10}^5$。输入的初始棋盘的每个位置要么是 `.`，要么是 `*`，并且至少有一个 `.`，至少有一个 `*`。**保证黑棋是连通的。** 保证每个测试点的 $n \times m$ 之和都小于等于 $4 \times {10}^6$。

- Subtask 1（9 points）：$n = 1$。
- Subtask 2（10 points）：$n = 2$，$m = 3$。
- Subtask 3（16 points）：保证 `.` 的个数不超过 $7$，$n, m \le 10$，$T \le 50$。
- Subtask 4（24 points）：保证 `.` 的个数不超过 $14$，$n, m \le 10$，$T \le 50$。
- Subtask 5（15 points）：$n, m \ge 3$，输入局面的边界上都是 `.`。即 $\forall (i, j)$，如果 $i = 1 \lor i = n \lor j = 1 \lor j = m$，则 $(i, j)$ 一定是空地。
- Subtask 6（26 points）：无特殊限制。

---
---
---

P.S. Froggy 和 uyom 都是（很久没下棋的）业余四段哥，欢迎找我们然后把我们虐一顿。


title: 「MCOI-06」Flight

description:
书虫需要移动他的[盾构机](https://www.luogu.com.cn/problem/P7569)。

书虫将 MC 空间抽象为二维平面。他的盾构机现在在 $(a,b)$，而书虫想把盾构机移动到 $(c,d)$。

书虫每一步可以将盾构机向东南西北任何方向行动。但是这盾构机有一个限制：相邻两步不能向同一个方向走！

给定 $(a,b)$ 和 $(c,d)$，请计算书虫最少需要几步将盾构机移动到终点。

求书虫的最少步数。可以证明，他永远可以到达终点。

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

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

接下来 $T$ 行，每行四个整数 $a,b,c,d$，代表一组数据，其中 $(a,b)$ 为起点，$(c,d)$ 为终点。

outputFormat: 输出 $T$ 行，第 $i$ 行代表第 $i$ 组数据的答案。

hint:
#### 样例 1 解释

 - 对于第一组，最优策略为 $(-2,0)\rarr(-2,1)$。
 - 对于第二组，最优策略为 $(0,1)\rarr(1,1)\rarr(1,2)\rarr(2,2)\rarr(2,3)\rarr(3,3)$。
 - 对于第三组，最优策略之一为 $(-1,1)\rarr (0,1)\rarr(0,0)\rarr(1,0)\rarr(1,1)$。

#### 数据规模与约定

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

 - Subtask 1（29 pts）：$0\le a,b,c,d\le 3$。
 - Subtask 2（29 pts）：$a=c$。
 - Subtask 3（42 pts）：无特殊限制。

对于所有数据，$1\le T\le 10^5$，$|a|,|b|,|c|,|d|\le10^{18}$。


title: 「C.E.L.U-03」探险者笔记 III

background:
罗司机在通关小 Soup 所制作的游戏《探险者笔记》后，感到十分的悲伤。为了缓解内心的伤痛，他决定改制《探险者笔记》，使其成为一个快乐的游戏。
一段时间之后，罗司机完成了制作，并喊来小 Soup 给他测试。

description:
改制后的《探险者笔记》由 $n$ 个关卡组成，每个关卡有一个难度 $b_i$，同时有 $m$ 个成就，第 $i$ 个成就需要你恰好完成 $sum_i$ 个关卡，且**刚好**分别是 $a_{i_1},a_{i_2},...,a_{i_{sum_i}}$。完成第 $i$ 个成就可以得到 $v_i$ 的分数。
如果长时间推关而没有获得任何成就，小 Soup 会感到疲乏。而且成就的解锁是有一定顺序的。因此上一个获得第 $i$ 个成就接下来再获得第 $j$ 个成就的条件是 $i<j$ 且 $w+\sum\limits_{k=1}^{sum_i}b_{a_{i_k}}\ge\sum\limits_{k=1}^{sum_j}b_{a_{j_k}}$，其中 $w$ 是一个给定的常数。
第一次获得成就没有任何限制。求最多他能得到多少分数。

inputFormat:
第一行三个数 $n,m,w$。
第二行 $n$ 个数，$b_i$。
接下来 $m$ 行，第 $i$ 行一开始有两个数，$v_i,sum_i$，接下来会有 $sum_i$ 个数，$a_{i_1},a_{i_2},...,a_{i_{sum_i}}$。

outputFormat: 仅一个数，答案。


title: 「RdOI R2」因数和(sum)

background: monsters 喜欢因数，所以他要出一道关于因数的题。

description:
众所周知，$i$ 的标准分解形式为：$\prod\limits_{j=1}^{k_i}p_{i,j}^{c_{i,j}}$。

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

定义 $f(x)=\sum\limits_{d|x}\left({a_{\frac{x}{d}}\times\prod\limits_{i=1}^{k_d}{C_{c_{d,i}+m}^{m}}}\right)$，现在需要你求出 $f(1),f(2),f(3),\cdots ,f(n)$，其中 $m$ 是给定常数。

由于 monsters 不喜欢太大的数，他需要你输出答案模 $998244353$ 的值。

另外，为了避免过大的输入输出量，本题使用随机数生成数据，并且只需要你输出所有答案的异或和。

如果你不知道 $C$ 是什么，$C_n^m=\dfrac{n!}{m!(n-m)!}$，其中 $!$ 代表阶乘。

inputFormat:
输入共有一行。

第一行，三个非负整数 $n,m,seed$。

你需要在程序中调用 $n$ 次数据生成器（```randomdigit```）来得到 $a$。

outputFormat: 输出共有一行一个整数，为所有 $f(x)$ 的异或和。

hint:
**数据生成器**

C/C++:
```cpp
#define uint unsigned int
uint seed;
inline uint randomdigit(){
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return seed;
}
```
pascal:
```pascal
var seed:dword;
function randomdigit:dword;
begin
	seed:=seed xor(seed shl 13);
	seed:=seed xor(seed shr 17);
	seed:=seed xor(seed shl 5);
	randomdigit:=seed;
end;
```

python3:
```python
seed = 0 # please input seed
mod = 1 << 32
def randomdigit():
    global seed
    seed ^= (seed << 13) % mod
    seed ^= (seed >> 17) % mod
    seed ^= (seed << 5) % mod
    return seed
```

---

**样例解释**

序列 $a$ 为 $506005380,3857352168,531380003$。

$f(1),f(2),f(3)$ 模 $998244353$ 的值分别为 $506005380,370380136,39141030$。

---

**数据范围**

对于 $100\%$ 的数据，$0\le m\le 10^5,1\le n\le 10^7,0\le a_1,a_2,\cdots,a_n,seed<2^{32}$。

- Subtask $1$（$30\%$ 的数据）：$n\le 10^6,m\le 10^5$。

在此 Subtask 中：

有 $10\%$ 的数据，满足 $m=0$。

另有 $10\%$ 的数据，满足 $n\le 100$。
- Subtask $2$（剩下 $70\%$ 的数据）：$n\le 10^7,m\le 3$。

**提示**

请注意空间限制和常数因子对程序运行效率的影响


title: 「EZEC-10」「Byakkai OI 2021」Estahv

background:
> chrisl gjeztor Amledza
> prof ovelmizer
> dos carm ammeidha alzenghar
> kawy may noxial gjeztor
> Rupieilla vas photreywz idha

description:
我们有排成一排的无限个格子，它们从左往右以 $1,2,\dots$ 编号。

你可以在每个格子中填入任意**正整数** $k$，则你会得到 $C_k$ 的权值。
其中满足 $C_0=C_1=1$，$C_i = \sum\limits_{j=0}^{i-1} C_j C_{i-j-1}$ $(i \ge 2)$。
若干个格子的总权值定义为它们的权值之积。

现在你需要从左往右依次在格子中填入数字，直到填入的数字之和等于 $n$ 或超过 $n$ 为止。
如此之后，你还需要为每个填入数字的格子涂上黑色或者白色。需要满足：不存在任意连续的 $2$ 个及以上白色的格子，且第一个格子必须为黑色，最后一个填入数字的格子必须为白色。
然后，你需要把所有相邻的均填入了数字的同色格子两两连边，并从中选出一个格子集合 $S$，满足 $S$ 内的格子两两不连通（可以为空）。

一种方案的权值定义为所有格子的总权值。

给定 $n$，请你对于 $s=0,1,\dots,n$，计算所有完成以上操作，且填入的数字之和**恰好**为 $n$，且黑色的格子数为 $s$ 的所有方案的权值之和。
两种方案不同当且仅当填入数字的格子数不同或对应格子填入的数字不同或对应格子颜色不同或 $S$ 集合不同。
对 $998244353$ 取模。

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

outputFormat: 一行，$n+1$ 个非负整数，表示对于 $s=0,1,\dots,n$ 的答案。

hint:
【样例 $1$ 说明】

当 $n=3$ 时，可以有 $2$ 或 $3$ 个格子。
若有 $2$ 个格子，则填数方案为 $[1,2]$ 或 $[2,1]$，权值共为 $2 \times C_1 \times C_2 = 4$；填色方案为 `BW`，必有一个黑色格子；$S$ 集合的选择是 $\{\},\{1\},\{2\},\{1,2\}$（以格子的编号表示）。
若有 $3$ 个格子，则填数方案为 $[1,1,1]$，权值为 $C_1^3=1$；填色方案为 `BBW`，必有两个黑色格子；$S$ 集合的选择是 $\{\},\{1\},\{2\},\{3\},\{1,3\},\{2,3\}$（以格子的编号表示）。
其中 `B` 表示黑色，`W` 表示白色。

【数据规模与约定】

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

- Subtask 1（30 points）：$n\le10$。
- Subtask 2（20 points）：$n\le300$。
- Subtask 3（20 points）：$n \le 5000$。
- Subtask 4（30 points）：无特殊限制，时限为 $3.5s$。

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

### 提示

为了方便各位获得暴力分，这里给出结论：
$$
C_k = \frac1k \binom{2k}{k-1} = \binom{2k-1}{k-1}-\binom{2k-1}{k-2}
$$


title: 「C.E.L.U-03」布尔

description:
给你 $n$ 个布尔变量和 $m$ 个限制，设 $s_i$ 为 $i$ 的取值。第 $i$ 个限制形如 $s_{u_i}$ 为 $x_i$ 则 $s_{v_i}$ 必须为 $y_i$，同时如果 $s_{v_i}$ 为 $y_i$ 则 $s_{u_i}$ 必须取 $x_i$。
一共 $q$ 次询问，每次询问给出一个区间 $l,r$。求最少把 $l,r$ 划分成多少段连续的区间，使得每段里的限制都可以得到一组合法解。如果无论如何都无法得到合法解，输出 `-1`。

inputFormat:
第一行三个数，$n,m,q$。
接下来 $m$ 行每行四个数，代表 $u_i,x_i,v_i,y_i$。
接下来 $q$ 行每行两个数，代表 $l_i,r_i$。

outputFormat: 对于每个询问输出一个数作为答案，如果无法得到答案输出 `-1`。


title: 梦现时刻

description:
给定 $n,m$ ，保证 $m\le n$，令 $F(a,b)=\sum_{i=0}^{b}\binom{b}{i}\binom{n-i}{a}$。

求 $\bigoplus_{a=1}^{m}\bigoplus_{b=1}^{m}(F(a,b) \bmod 998244353)$。

其中 $\oplus$ 表示异或运算。

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

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

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

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

对于 $100 \%$ 的数据，$1 \le n \le {10}^9$，$1\le m\le 5000$，保证 $m\le n$

- Subtask 1（20 points）：$n \le 500$。
- Subtask 2（30 points）：$n \le 5000$。
- Subtask 3（50 points）：无特殊限制。


title: 铃解缀

background: 题目：数对构造。

description:
将 $1 \sim 2n$ 的整数分为 $n$ 个有序数对 $(a_i,b_i)$（$1 \le i \le n$）。你需要使得对于任意不大于 $n$ 的正整数 $i$，有 $a_i - b_i = i$。

给定 $n$，请你给出一种构造方案。若无解则输出 `-1 0`。

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

outputFormat:
若无解，输出一行两个整数 `-1 0`。否则输出 $n$ 行，每行两个 $1 \sim 2n$ 内的正整数，表示 $(a_i,b_i)$。

你需要保证 $n$ 对 $(a_i,b_i)$ 按 $a_i - b_i$ 的大小顺次构成一个 $1 \sim 2n$ 整数的排列。

hint:
**样例解释**

对于第一组样例，显然这个样例无解。

对于第二组样例，样例输出给出了一种可行的构造方案。

**数据范围及约定**

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

$\texttt{Subtask 1 (20 pts)}$：$n \le 5$。

$\texttt{Subtask 2 (20 pts)}$：$n \le 10 ^ 5$。

$\texttt{Subtask 3 (30 pts)}$：$n$ 为素数。

$\texttt{Subtask 4 (30 pts)}$：无特殊限制。

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

这道题用来锻炼数学思维和构造能力，但不适合在 OI 比赛中。

[CoOI Round 1](https://www.luogu.com.cn/contest/43016) B 题。


title: 撕裂抹消

background: 何以撕裂，何以抹消？

description:
给定一个长为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，再给定一个有理数序列 $p_1,p_2,\dots,p_n$。每个位置上有一个随机系数 $c_i \in \{0,1\}$，其中 $P(c_i =  1) = p_i$，$P(c_i = 0) = 1-p_i$。

注意到随机系数写作序列后可以划分为若干个极长的连续 $0$、$1$ 段，极长指不能再向两边扩展。定义一种系数序列的权值为：当系数序列中恰有 $k$ 个极长连续 $1$ 段时为 $\sum\limits_{i=1}^n c_i a_i$，否则为 $0$。

求这个系数序列的期望权值。答案对 $998244353$ 取模。

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

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

第三行，$n$ 个非负整数 $p_1,p_2,\dots,p_n$，以模 $998244353$ 意义下给出。

outputFormat: 一行，一个非负整数，表示期望。

hint:
**样例解释**

对于第一组样例，$c_i$ 必然为 $1$，且必然恰有 $1$ 个极长连续段，故权值必然为 $1 + 2 + 3 + 4 + 5 = 15$。

对于第二组样例，仅有 $c_1 = 1,c_2 = 0,c_3 = 1$ 时权值不为 $0$，且此种情况的概率为 $\frac 12 \times \frac 12 \times \frac 12 = \frac 18$，故期望为 $\frac{1+3}8 = \frac 12 \equiv 499122177 \pmod {998244353}$。

**数据范围**

对于 $30\%$ 的数据，$n \le 20$。

对于 $60\%$ 的数据，$n \le 10^3$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le k \le \min\left(20,\left\lfloor\frac{n+1}2\right\rfloor\right)$，$0 \le a_i,p_i < 998244353$。


title: 三到六

background:
「听说 JOJO 6 要来力！」
「好时代，来临力！」
「可是那个无敌的男人……」
「啊……在吃刀子之前，让我重温一下『欧拉欧拉』……」

description: 给定整数 $n,k$ 和一个 $n$ 阶排列 $\pi'$，问多少个排列 $\pi$ 满足恰有 $k$ 个位置 $i$ 满足 $1 \le i \le n$ 且 $\pi_i < \pi_{\pi'_i}$。答案对 $998244353$ 取模。

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

第二行，$n$ 个正整数，表示 $\pi'$。

outputFormat: 一行，一个非负整数，表示满足条件的 $\pi$ 的数量。

hint:
**样例解释**

对于第一组样例，$\pi_i$ 不可能小于 $\pi_i$，故必然满足条件，则答案为 $5! = 120$。

对于第二组样例，有以下 $5$ 种 $\pi$ 满足条件：

 1. $12345$；
 1. $23451$；
 1. $34512$；
 1. $45123$；
 1. $51234$。

对于第三组样例，不予解释。

**数据范围**

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

对于 $40\%$ 的数据，$n \le 3 \times 10^2$。

对于 $60\%$ 的数据，$n \le 10^3$。

对于另外 $20\%$ 的数据，保证 $\pi'_i = i \bmod n + 1$（$1 \le i \le n$）。

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


title: 「RdOI R2」称重(weigh)

background: 因为 rui_er 是一个良心出题人，所以本题是一道交互题。

description:
rui_er 为了准备体测，买了 $n$ 个实心球准备练习，但是却发现在发货时混入了两个质量明显较轻但外观相似的球（这两个球质量相等），且已知这两个球的质量之和大于一个正常的球。为了防止影响训练效果，现在需要找出这两个球。因为手动找太慢了，现在拿来了一个天平，可以在两侧各放上若干个球，得到两侧的质量大小关系。请你帮帮 rui_er，在使用不超过 $k$ 次天平的情况下，找出这两个较轻的球。

这里 $k$ 是每个测试点的属性，你不必也不应该读入。

---

**交互方式**

本题采用 I/O 交互。

你可以选择进行称量操作，此时向标准输出打印一行 `1 p a1 a2 ... ap q b1 b2 ... bq`，表示在天平左盘放入编号为 $a_1,a_2,\cdots,a_p$ 的 $p$ 个球，在天平右盘放入编号为 $b_1,b_2,\cdots,b_q$ 的 $q$ 个球。随后清空缓冲区，并从标准输入读入一个 `<>=` 之一的字符，表示左盘与右盘的质量关系。

对于每次此类询问，你需要保证 $1\le p,q\le n$，$p+q\le n$，所有 $a_i$ 和 $b_i$ 互不相同，且你最多进行此类询问 $k$ 次。

在得到答案后，向标准输出打印一行 `2 x y` 来提交答案，表示编号为 $x$ 的球和编号为 $y$ 的球质量偏轻。

你需要保证 $1\le x\lt y\le n$（注意需要严格按照从小到大顺序输出），且在进行完这一操作后立即终止程序。

交互库在一开始就已经确定小球的情况，不会随着你的询问而改变。

inputFormat:
第一行一个整数 $n$，表示球的数量。这里 $k$ 是每个测试点的属性，你不必也不应该读入。

接下来若干行，见【交互方式】。

outputFormat: 若干行，见【交互方式】。