title: [BJOI2015] 隐身术

description:
给定两个串$A$、$B$。请问$~B~$中有多少个非空子串和$~A~$的编辑距离不超过$K$？

所谓“子串”，指的是$~B~$中连续的一段。不同位置的内容相同的子串算作多个。两个串之间的“编辑距离”指的是把一个串变成另一个串需要的最小的操作次数，每次操作可以插入、删除或者替换一个字符。

inputFormat:
第一行一个非负整数$K$。接下来两行，每行一个由大写字母组成的字符
串，分别表示$~A~$和$~B~$。

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

hint: 对$100\%$的数据，$K\leq5$，两个字符串均非空，长度和小于$10^5$。


title: [BJOI2015] 回家的路【征集spj】

type: P

description: 小强和阿米巴是好朋友。连接北京和小强的家乡的是错综复杂的铁路网。一共有$~N~$个站点，站点之间有长短不一的双向的铁路。小强每次回家的时候，会从所有的最短路中随机选择一条。阿米巴门前有一条铁路。他想在不改变北京到小强的家乡的最短路的距离的前提下，给这个铁路网再添一条长度为$~K~$的单向铁路，使得小强路过阿米巴家门口的那条铁路的概率最大。请输出这个最大概率。

inputFormat:
第一行是三个正整数$~N,M~$和$~K~$，表示站点的数量，铁路线的数量和新开的铁路线的长度。站点从$~1~$编号到$~N~$。北京是$~1~$号点，小强的家乡是$~N~$号。接下来$~M~$行，每行三个正整数$~u,v,s~$表示有一条连接站点$~u~$和$~v~$的铁路线长度是$~s~$。

这$~M~$行中的第一行描述的是阿米巴家门口的铁路。两个点之间可能有多条铁路。也有可能$~u=v~$，即，有自环。你新修建的铁路也可以和已有线路重合，也可以是自环。$~1~$和$~N~$之间一定是连通的。

$~3\leq N\leq 100000,M\leq 400000,1\leq s,K≤10000~$，保证无论如何加边图中任两点之间的最短路的数量都不超过$2^{16000}~$。

outputFormat:
输出一行两个正整数$~A,B~$，表示从$~A~$向$~B~$修建一条单向铁路。你的修建方案得出的小强路过的概率和标准答案之间的差距不超过$10^{-6}$即可算对。

//注意：本题因缺少$spj$，请谨慎提交。

hint: 添加边之后，一共有$~3~$条最短路，小强会路过阿米巴门前的概率由$~1/2~$变为$~2/3~$.


title: [BJOI2015] 糖果

background: Alice 正在教她的弟弟 Bob 学数学。

description:
每天，Alice 画一个 $n$ 行 $m$ 列的表格，要求 Bob 在格子里填数。

Bob已经学会了自然数 $1$ 到 $k$ 的写法。因此他在每个格子里填 $1 \sim k$ 之间的整数。

Alice 告诉 Bob，如果 Bob 填写完表格的 $n \times m$ 个数以后，每行的数从第 $1$ 列到第 $m$ 列单调不减，并且任意两行至少有一列的数不同，而且以前 Bob 没有填写过相同的表格，那么 Alice 就给 Bob 吃一颗糖果。

Bob想知道，如果每天填写一遍表格，最多能吃到多少颗糖果。

答案对 $p$ 取模。

inputFormat: 输入只有一行四个整数，分别代表 $n, m, k, p$。

outputFormat: 输出一行，一个整数，表示答案模 $p$ 后的结果。

hint:
#### 样例输入输出 1 解释

共有 $10$ 种方案，取模后为 $0$。

---

#### 数据规模与约定

- 对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 10^5$，$1 \leq k,p \leq 2 \times 10^9$。


title: [LnOI2019] 来者不拒，去者不追

background:
题目提供者：朝田诗乃

![avartar](https://cdn.luogu.com.cn/upload/pic/66100.png)

description:
给定一个长度为$n$的序列$a$。给定$m$个询问，每次询问一个区间中$[l,r]$中所有数的“Abbi值”之和

Abbi值定义为：若$a_i$在询问区间$[l,r]$中是第$k$小，那么它的“Abbi值”等于$k \times a_i$。

为了消除歧义举个例子：

有序列1 2 2 3，那么1是第1小，2是第2小，3是第4小，序列Abbi值和为

$$1 \times 1+2 \times 2+2 \times 2+3 \times 4=21$$

inputFormat:
第一行两个整数，$n$和$m$，分别表示序列长度和询问组数。

第二行$n$个数，第$i$个数为$a_i$，表示序列的初始值。

接下来$m$行，每行两个数$l$和$r$，表示询问区间。

outputFormat: 对于每个询问，输出一行表示答案

hint:
前2个数据点，$1≤n,m≤1000$，时限1s。

接下来14个数据点，$1≤n,a_i,m≤100000$，$1≤l≤r≤n$，时限1s。

最后两个数据点，$1≤a_i≤100000$，$1≤l≤r≤n$，$1≤n,m≤500000$，时限3s。

建议使用读入优化。建议开启O2优化。

数据已经过加强。


title: [JLOI2011] 不等式组

description: 旺汪与旺喵最近在做一些不等式的练习。这些不等式都是形如 $ax+b>c$ 的一元不等式。当然，解这些不等式对旺汪来说太简单了，所以旺喵想挑战旺汪。旺喵给出一组一元不等式，并给出一个数值。旺汪需要回答的是 $x=k$ 时成立的不等式的数量。聪明的旺汪每次都很快就给出了答案。你的任务是快速的验证旺汪的答案是不是正确的。

inputFormat:
输入第一行为一个正整数 $n$，代表接下来有 $n$ 行。

接下来每一行可能有 $3$ 种形式：

1. `Add a b c`：表明要往不等式组添加一条不等式 $ax+b>c$。
2. `Del i`：代表删除第 $i$ 条添加的不等式（最先添加的是第 $1$ 条）。
3. `Query k`：代表一个询问，即当 $x=k$ 时，在当前不等式组内成立的不等式的数量。

注意：一开始不等式组为空，$a,b,c,i,k$ 均为整数，且保证所有操作均合法，不会出现要求删除尚未添加的不等式的情况，但可能重复删除同一条不等式。

outputFormat: 对于每一个询问 `Query k`，输出一行一个整数，代表询问的答案。

samples:
9
Add 1 1 1
Add -2 4 3
Query 0
Del 1
Query 0
Del 2
Query 0
Add 8 9 100
Query 10

hint:
#### 样例 1 说明

第 $1$ 条添加到不等式组的不等式为 $x+1>1$，第 $2$ 条为 $−2x+4>3$。所以第 $1$ 个询问的时候只有第 $2$ 条不等式可以成立，故输出 `1`。

然后删除第 $1$ 条不等式，再询问的时候依然是只有第 $2$ 条不等式可以成立，故输出 $1$ 。

再删除第 $2$ 条不等式后，因为不等式组里面没有不等式了，所以没有不等式可以被满足，故输出 $0$。

继续加入第 $3$ 条不等式 $8x+9>100$，当 $x=k=10$ 时有 $8\times 10+9=89<100$，故也没有不等式可以被满足，依然输出 $0$。

#### 数据规模与约定

- 对于 $20\%$ 的数据，保证 $n\leq 10^3$。
- 对于 $40\%$ 的数据，保证 $n\leq 10^4$。
- 对于 $100\%$ 的数据，保证 $1\leq n\leq 10^5$，$a,b,c\in[-10^8,10^8]$，$k\in[-10^6,10^6]$。


title: 最优性剪枝

background:
Nauuo 是一名出题人。

众所周知，某些出题人非常懒，导致[随便爆搜](https://www.luogu.com.cn/discuss/show/185420)加上一个[最优性剪枝](https://www.luogu.com.cn/discuss/show/184641)就能通过。Nauuo 决定把这些 naive 的暴力都卡掉。

description:
Nauuo 决定卡一个暴力搜索程序，为此她构建了一组数据。为了简化题目，你将得到这组数据产生的搜索树 $T$。$T$ 中包含 $n$ 个节点，依次编号为 $1 \sim n$，其中 $1$ 号点是 $T$ 的根节点。一个节点的深度是它到 $1$ 号点的简单路径上的节点个数。

这个程序的伪代码如下

```cpp
answer := inf

procedure dfs(node,depth)
	if (node is leaf)
		answer := min(answer,depth)
		return
	if (depth < answer)
		for i in children of node
			dfs(i,depth+1)

dfs(1,1)
```

其中，`:=` 表示赋值运算。

翻译成人话就是说，这个暴力搜索程序将**深度优先**地遍历这棵搜索树，当访问到一个叶节点时，这个程序将用这个叶节点的深度更新答案。

同时，这个程序有一个最优性剪枝，也就是说，当这个程序访问到任意一个深度等于答案的节点时，它将不会再访问这个节点的子节点。

然而，可怜的 Nauuo 并不知道这个程序在某个节点时访问自己子节点的顺序，因此她认为每个节点访问子节点的顺序都是在所有可能的情况中等概率随机的，显然，一共有 $\prod d_i!$ 种情况，其中 $d_i$ 表示 $i$ 号节点的子节点数量。

现在她想知道这个程序访问到的节点数量的期望，以确定这个程序会不会被自己的数据卡掉。

为了避免浮点误差，答案对 $998244353$ 取模。保证答案能被表示为最简分数 $\frac{p}{q}$，你只需要输出一个 $x (0\leq x < 998244353)$ 使得 $qx \equiv p \pmod {998244353}$。

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

第二行 $n-1$ 个整数 $p_2, p_3 \cdots p_n$，其中 $p_i$ 表示 $i$ 号节点的父节点编号。

outputFormat: 一行一个整数，所求 $x$。

hint:
#### 样例解释

第一组样例的真实答案为 $\frac{7}{2}$。

一共只有两种情况，如果 $1$ 号节点先遍历 $3$ 号节点，则程序将访问到搜索树中所有节点。如果 $1$ 号节点先遍历 $2$ 号节点，则 $4$ 号节点不会被访问到。

第二组样例中，每个非叶节点的子节点都是唯一的，因此只有一种可能的情况，所有节点都必然被访问到。

第三组样例的真实答案为 $\frac{94}{9}$。

---

#### 数据范围

**「本题采用捆绑测试」**

对于所有测试点，保证 $1 \leq n \leq 3\times 10^5$，$1 \leq p_i < i$。

$\text{Subtask 1 (11 pts)}$ $n \leq 9$。

$\text{Subtask 2 (18 pts)}$ $n \leq 100$。

$\text{Subtask 3 (19 pts)}$ $n\leq 10^3$。

$\text{Subtask 4 (4 pts)}$ $p_i = i-1$。

$\text{Subtask 5 (8 pts)}$ $p_i =\lfloor \frac{i}{2} \rfloor$。

$\text{Subtask 6 (40 pts)}$ 无特殊限制。

---

#### 提示

如果你不知道怎么对分数取模，可以参考[这里](https://www.luogu.com.cn/problem/P3811)。


title: [JLOI2011] 小A的烦恼

description:
小$A$是$B$公司的一名$PM(product market)$。$B$公司越来越注重产品使用情况分析，而小$A$的工作就是整天对着一堆数据分析来分析去，没完没了。其中有一个操作是小$A$很头疼的，就是要把多个$csv$文件的数据拷到同一个$excel$文件中去。
有一天小$A$满怀期待地找到了你，一个高级程序员，她想让你写程序帮她完成这个简单重复性工作。这不是坑爹吗，直接操作$excel$还要用到第三方的库，还不如直接写到$csv$文件中，让她再手动去转成$excel$文件。经过内部沟通协调，最终定下了这个方案。
$csv$是一种$excel$可支持和格式，且存储方式非常简单。它实际上就是用“`,`”来分隔相邻的两个列。比如以下三行数据：
```
a,a,a
b,,b
,c,c
```
表示的就是：

| a | a | a |
| ---------- | :----------: | :----------: |
| b |   | b |
|   | c | c |

现在小$A$想做的就是把各个文件按照从左往右的顺序拷到同一个文件当中。比如文件$a$的数据是：
```
a1,b1,c1
a2,b2
```
文件$b$的数据是：
```
a1,b1,c1,d1
a2,b2
a3,b3,c3
a4
```
那么她所希望的最终结果是：

| a |  |  | b |  |  |  |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| a1 | b1 | c1 | a1 | b1 | c1 | d1 |
| a2 | b2 |  | a2 | b2 |  |  |
|  |  |  | a3 | b3 | c3 |  |
|  |  |  | a4 |  |  |  |

这个结果在$csv$文件里就是：
```
a,,,b,,,
a1,b1,c1,a1,b1,c1,d1
a2,b2,,a2,b2,,
,,,a3,b3,c3,
,,,a4,,,
```
以上结果的第一行是每一个文件的文件名，文件名与相应文件的第一列对齐。如果相应文件不止一列，那么其它列用空的单元格来补充。
输入的$csv$文件里保证了每一行的末尾都没有“`,`”，也就是说像$a$文件的第$2$行的第$3$列一样，如那一格是空的，那么在$b2$后面是没有“`,`”的。
输出的$csv$文件里因为是程序的输出结果，为了简化程序，如果末尾是空的，那么还是会显式输出“`,`”，如以上的结果所示。
输入文件保证至少有一行一列非空。
输出的文件要保证下一个文件的第一列要紧邻着上一文件的最后一个非空列的右面。最后一个文件只输出到最后一个非空列。

inputFormat:
第一行有一个整数$N$（$1\leq N\leq 100$），表示有$N$个文件。
以下$N$个数据块的第一行有一个整数$M$ ($1\leq M\leq 100$)和一个字符串$S$ ($1\leq length(S)\leq 100$)，M表示文件的行数，$S$表示文件名。
$N$个数据块的下面$M$行中，每一行是一个字符串$T$($1\leq length(T)\leq 100$)，$T$只包含小写字母、数字和“`,`”。

outputFormat: 输出把$N$个文件的数据合到一个文件的结果。


title: [JLOI2011] 基因补全

description: 在生物课中我们学过，碱基组成了$DNA$（脱氧核糖核酸），他们分别可以用大写字母$A,C,T,G$表示，其中$A$总与$T$配对，$C$总与$G$配对。两个碱基序列能相互匹配，当且仅当它们等长，并且任意相同位置的碱基都是能相互配对的。例如$ACGTC$能且仅能与$TGCAG$配对。一个相对短的碱基序列能通过往该序列中任意位置补足碱基来与一个相对长的碱基序列配对。补全碱基的位置、数量不同，都将视为不同的补全方案。现在有两串碱基序列$S$和$T$，分别有$n$和$m$个碱基($n\geq m$)，问一共有多少种补全方案。

inputFormat:
数据包括三行。
第一行有两个整数$n$，$m$，表示碱基序列的长度。
第二行包含$n$个字符，表示碱基序列$S$。
第三行包含$m$个字符，表示碱基序列$T$。
两个碱基序列的字符种类只有$A,C,G,T$这$4$个大写字母。

outputFormat: 答案只包含一行，表示补全方案的个数。

hint:
样例解释：
$TCC$的$4$种补全方案（括号中字符为补全的碱基）
$(GA)TC(AT)C(TTC)$
$(GA)TC(ATCTT)C$
$(GA)T(CAT)C(TT)C$
$(GATCA)TC(TT)C$

数据范围：
对于$30\% $数据，$n\leq 1000,m\leq 2$
对于$50\% $数据，$n\leq 1000,m\leq 4$
对于$100\% $数据，$n\leq 2000,m\leq n$


title: [JLOI2010] 铁人双项比赛

description:
铁人双项比赛是吉林教育学院的一项传统体育项目。该项目比赛由长跑和骑自行车组成，参赛选手必须先完成$k$公里的长跑，然后完成r公里的骑车，才能到达终点。每个参赛选手所擅长的项目不同，有的擅长长跑，有的擅长骑车。如果总赛程$s=k+r$一定，那么K越大，对擅长长跑的选手越有利；$k$越小，对擅长骑车的选手越有利。

现在给定总赛程$s$，以及每个选手长跑和骑车的平均速度，请你求出对于某个指定的选手最有利的k和r。所谓最有利，是指选择了这个$k$和$r$后，该选手可以获得冠军，且领先第$2$名尽量地多。

inputFormat:
你的程序从文件读入输入数据。
输入的第一行是两个正整数$s$和$n$，$s$表示总赛程（单位为公里，$s\leq 2^{31}$），$n$表示参赛总人数（$2\leq n\leq 100$）。
接下来的$n$行每行是两个实数，分别表示每个选手长跑的平均速度和骑车的平均速度（单位为千米/小时）。
第$n$个选手就是指定的选手，你的任务是求出对他最有利的$k$和$r$。

outputFormat: 你的程序的输出包括三个数$k,r,t$，分别表示对第$n$号选手最有利的$k$和$r$（浮点数，保留小数点后$2$位），以及在选择$k$和$r$的情况下，第$n$号选手最多可以领先第$2$名多少秒（四舍五入到整数）；如果另一个选手和该选手并列第一，则$t_i=0$。倘若无论选择什么$k$，$r$都不能使第$n$号选手获胜，则输出“$NO$”。


title: [JLOI2010] 世界杯租房

description:
南非世界杯组委会指定了在此期间可提供的一些旅馆供球迷租赁，名为阿凡达的即是其中一所。因为阿凡达旅馆房子的数目不超过$26$，所以它们可以用$26$个大写字母表示。
有一天，刘经理的电话响了，他接到了一个租赁房屋的请求，要求从$6$月$12$日晚起租到$6$月$19$日中午。于是他察看了预定表，但是并没有发现一间房屋能够直接满足要求。比如房主可能因为一些私人原因需要留在自己的房子中，所以这个游客不得不在其中的一间先住上几天再搬到另一间住上几天。他详细检查了预定表后，对旅客说：“我将你先在$B$安置$3$天，再将你安排到$F$去度过剩余的旅途。”
你的目标是使得游客从一间房屋搬到另一间房屋的次数最少。
注意在旅馆的计费中，总是将某一天的晚上到第二天的中午视作一天。

inputFormat:
输入文件包括多组数据。每组数据输入文件第一行包括两个整数$M$和$N$。$M$表示日程表上的天数，$N$表示公寓的数目。天数不超过$100$天，从1开始计数，公寓不超过$26$个，从$A$开始计数。
接下来$M$行，每行包括$N$个字母，表示从第i天晚到次日中午，该公寓是否已经被出租，$X$代表被出租，$O$代表未被出租。
最后一行包括两个整数$s,t$，代表旅客从第$s$天晚入住到第$(t+1)$天中午结束旅行。$1\leq s<t\leq M+1$。
$M=N=0$标志着文件的结束。

outputFormat:
对于每一组数据，首先打印测试数据的编号，冒号和一个空行。接下来输出换房次数最少的方案，每一行使用如下格式：
$<unit>: <start date>-<end date>$
其中$<unit>$为房屋编号，$<start data>$和$<end data>$分别为该旅客入住和离开该房屋时间。
注意，如果存在多种方案满足换房次数最少，输出其中字典序最小的方案。
如不存在这样的方案，输出一行”$Not\ available$”。
每两组输出之间以一个空行隔开。输出文件的末尾不要加空行。

samples:
10 7
XXXXXXX
XOXXXXO
XOXXXXO
XOXXXOX
OXXOXOX
XOXOXOX
OXXOXOX
OXXXXOX
XXXXXXX
XXXXXXX
2 9
0 0


title: 【模板】Berlekamp–Massey 算法

background:
前置技能：线性递推 $\&~\rm BM$ 算法。

同时，请注意优化你的空间。保证最短递推式**唯一**。

出题人为强行二合一感到很抱歉，但是其实也是可以学习一下 $k^2 \log n$ 线性递推的——保证在 `-O2` 指令下可以过。

description:
给出一个数列 $P$ 从 $0$ 开始的前 $n$ 项。

求序列 $P$ 在 $\bmod~998244353$ 下的最短线性递推式，并在 $\bmod~998244353$ 下输出 $P_m$。

inputFormat:
第一行共两个数 $n,m$ ，表示将会给出序列 $P$ 的前 $n$ 项，要求 $P_m$。

第二行 $n$ 个数，表示 $P_0,P_1,P_2,\ldots,P_{n-1}$。

outputFormat:
第一行输出该最短线性递推式。

第二行输出 $P_m$ 的值。


title: [yLOI2019] 珍珠

background:
> 别叹息太多告别，至少相遇很真切。
> 摇曳着盛放枯竭，时间从未停歇。
> 天涯浪迹的白雪，念念不忘山川蝴蝶。
> 听说有人孤负黑夜，偏要点亮人间的月。

——银临《珍珠》

description:
扶苏给了你一个放珍珠的小匣子，这个匣子在左右两端都可以无限制的加入珍珠，珍珠在匣子里会排成一列，每次在左端加入珍珠，这个珍珠会被加入到这个珍珠序列的最左侧，在右端加入则会被加入到珍珠序列的最右侧。初始时，匣子是空的。

这些珍珠要么是黑色的，要么是白色的，为了方便起见，我们将白色看作 $0$，黑色看作 $1$。

在人鱼的世界中，定义颜色 $A$ **组合** 颜色 $B$ 为 $A\operatorname{nand}B$，读作 $A$ 与非 $B$。

定义 $A \operatorname{nand} B = \operatorname{not} (A \operatorname{and}B)$ ，其中 $\operatorname{and}$ 运算代表二进制与运算，$\operatorname{not}$ 运算代表二进制非运算。

定义位置 $x$ 到位置 $y$ 的组合和为：

从 $x$ 开始向 $y$ ，第一个颜色组合第二个颜色的结果组合第三个颜色，得到的结果组合第四个颜色……一直组合到位置 $y$ 的颜色的结果。特别的，$x = y$ 时，组合和为该颜色。

形式化的，设 $C_{x, y}$ 为序列 $A$ 从 $x$ 到 $y$ 的组合和，则
$$C_{x, y} = \begin{cases} C_{x, y - 1} \operatorname{nand} A_y & x < y \\  C_{x, y + 1} \operatorname{nand} A_y & x > y \\ A_x &x = y \end{cases}$$

例如，给定序列 $1, 1, 0, 0$，从 $2$ 到 $4$ 的组合和为

$$(1 \operatorname{nand} 0) \operatorname{nand} 0 = 1 \operatorname{nand} 0 = 1$$

从 $3$ 到 $1$ 的组合和为

$$(0 \operatorname{nand} 1) \operatorname{nand} 1 = 1 \operatorname{nand} 1 = 0$$

从 $2$ 到 $2$ 的组合和为

$$1$$

扶苏会在匣子的两边加入一些珍珠，或者给定一个位置 $p$，询问你从左向右数第 $1$ 个位置到从左向右数第 $p$ 个位置的组合和，或者从右向左数第 $1$ 个位置到从右向左数第 $p$ 个位置的组合和。

inputFormat:
每个输入文件中都有且仅有一组测试数据。

数据的第一行是一个整数 $n$，代表扶苏的操作个数。

由于正常读入每个操作所需要的输入量过大，因此我们采用下面的生成器来生成每个操作。

```cpp
#include <cstdio>

namespace Maker {

typedef unsigned int uit;

bool __sp;
uit __x, __y, __z;
int __type, __k, __m;

template <typename T>
inline void qr(T &x) {
  char ch = getchar(), lst = ' ';
  while ((ch > '9') || (ch < '0')) lst = ch, ch = getchar();
  while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  if (lst == '-') x = -x;
}

template <typename T>
inline void Begin(const T &x) {
  __type = x % 10;
  qr(__x); qr(__y); qr(__z); qr(__m);
  __sp = (__type == 3) || (__type == 4); __type &= 1;
}

inline uit __Next_Integer() {
  __x ^= __y << (__z & 31);
  __y ^= __z >> (__x & 31);
  __z ^= __x << (__y & 31);
  __x ^= __x >> 5; __y ^= __y << 13; __z ^= __z >> 6;
  return __x;
}

inline uit Rand() { return __Next_Integer(); }

template <typename Tx, typename Ty, typename Tz>
inline void Get_Nextline(Tx &x, Ty &y, Tz &z) {
  if (__m) {
    --__m;
    x = 0; y = 0; z = 0;
    qr(x); qr(y); qr(z);
    if (x == 0) {
      ++__k;
    }
  } else {
    x = Rand() & 1; y = Rand() & 1;
    if (__k == 0) { x = 0; }
    if (x == 0) {
      ++__k;
      if (__sp) {
        z = __type;
      } else {
        z = Rand() & 1;
      }
    } else {
      int dk = __k >> 1;
      if (dk == 0) {
        z = 1;
      } else {
        z = Rand() % dk + dk;
      }
    }
  }
}

}
```

对于 C/C++ 选手，我们提供了如上的数据生成代码（C 选手请使用 C++ 语言提交)，请将他们直接复制到你的代码中。

对于非 C/C++ 选手，请你自行按照上面代码的内容，自行写出你所使用语言的对应生成器。

下面的内容只针对 C++ 选手，请其他语言的选手自行按照对应语言的语法来完成代码。

在读入 $n$ 这个数字以后，请你调用 ``Maker`` 命名空间中的 ``Begin`` 函数，函数的参数为 $n$。换句话说，你的代码中需要出现类似 ``Maker::Begin(n)`` 的语句。

在调用完 ``Maker::Begin`` 函数以后，生成器就可以开始工作了。一共有 $n$ 次操作，每次操作时请你调用 ``Maker::Get_Nextline`` 函数，传入三个**整形**变量，(不妨设为 $x,y,z$)，每次函数调用结束以后，$x,y,z$ 的值都会被修改，作为每次操作的参数。具体含义如下：

> 每次操作会有三个整数作为参数， 依次记为 $x,y,z$
>
> - 如果 $x = 0$，则代表这是一次插入操作；
> - 如果 $x = 1$，则代表这是一次查询。
> - 如果 $y = 0$，则代表插入操作是从左侧进行的，或者查询的位置是从左向右数的；
> - 如果 $y = 1$，则代表插入操作是从右侧进行的，或者查询的位置是从右向左数的。
> - 如果 $x = 0$，则 $z$ 是一个非零即一的整数，代表插入珍珠的颜色，$0$ 代表白色，$1$ 代表黑色；
> - 如果 $x = 1$，则 $z$ 代表查询从第一个到第 $z$ 个位置的组合和。组合和的方向和位置的方向由参数 $y$ 决定。

对于 C/C++ 选手，我们提供了模板程序([模板程序链接](https://www.luogu.org/paste/lk7wn4a1))，在这个程序中，已经做好了变量的读入和生成器的初始化，同时能够自动获取 $x,y,z$ 的值，你需要做的只是每次依照题意进行一个操作，最终输出答案。你可以自主选择是否使用这个模板，最终的评测得分与你的代码内容**无关**。

**特别提醒：不建议使用 ``fread`` 等直接从输入中大量读取信息然后保存的函数对 $n$ 进行读入，如果你非要这么做，请你自行重写 ``Maker::Begin()`` 中的读入部分。**

**从输入数据的第二行起，所有的数据都会被生成器自动读入（包括第二行），不需要你再行读入**。

输入数据的第二行是四个整数 $a,b,c,m$，其中 $a,b,c$ 是生成器的参数，$m$ 为需要额外读入的操作数。

为了在某种意义上避免因为生成的操作完全随机而产生的乱搞做法，我们将首先额外读入 $m$ 个给定的操作，然后再行随机。

以下 $m$ 行，每行三个整数 $x,~y,~z$，代表一次操作。

请特别注意，这 $m$ 次操作会被生成器**自动读入**。

outputFormat:
为了避免输出过大，请输出一行四个用空格隔开的整数，分别代表所有的查询中：

- 一共有多少次查询的结果为 $1$。
- 一共有多少次查询的操作编号为奇数且查询结果为 $0$。
- 一共有多少次查询的操作编号为偶数且查询结果为 $1$。
- 一共有多少次查询的操作编号是 $1024$ 的倍数且查询结果为 $0$。

定义第 $i$ 次操作的操作编号为 $i$。

**注意，一次插入也算做一次操作**。

hint:
#### 样例输入输出 1 解释

第一次操作，$x=0,y=1,z=0$，在匣子右端插入一个 $0$，那么匣子里的珍珠序列为 $\{0\}$

第二次操作，$x = 1,y = 0,z = 1$，查询从左向右数第一个数到第一个数的组合和，答案是 $0$。

第三次操作，$x = 0,y = 1,z = 1$，在匣子右端插入一个 $1$，匣子里的珍珠序列为 $\{0,~1\}$

第四次操作，$x = 1,y = 0,z = 1$，查询从左向右数第一个数到第一个数的组合和，答案是 $0$。

第五次操作，$x = 0,y = 0,z = 0$，在匣子左侧插入一个 $0$，那么匣子里的珍珠序列为 $\{0,~0,~1\}$

第六次操作，$x = 0,y = 1,z = 1$，在匣子右侧插入一个 $1$，那么匣子的珍珠序列为 $\{0,~0,~1,~1\}$

没有任何一次查询的结果满足【输出格式】中提到的任意一种情况，于是输出 ``0 0 0 0``。

---

#### 数据规模与约定

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

- Subtask 1（5 points）：$n = m = 0$。
- Subtask 2（15 points）：$n = 1001$。
- Subtask 3（15 points）：$n = 10^5 + 2$。
- Subtask 4（10 points）：$n = 10^7 + 3$，对于所有 $x = 0$ 的操作，保证 $z = 1$。
- Subtask 5（10 points）：$n = 10^7 + 4$，对于所有 $x = 0$ 的操作，保证 $z = 0$。
- Subtask 6（15 points）：$n = 10^7 + 5$，$m = 0$。
- Subtask 7（30 points）：$n = 10^7 + 6$。

对于全部的测试点，保证 $0 \leq n \leq 10^7 + 6$，$0 \leq m \leq \min(n, 10^6)$，$x, y \in \{0, 1\}$，且对于所有 $x = 0$ 的操作，保证  $z \in \{0, 1\}$，若设 $k$ 为在任一查询时匣子里的珍珠个数，则保证对于 $x = 1$ 的操作，$1 \leq z \leq k$，匣子为空时不会有查询操作。

---

#### 提示与说明

- 请注意常数因子对程序效率造成的影响。
- $n$ 的末位数字可以帮助你快速的判断测试点所属的子任务。
- 由于涉及到非操作，与非运算可能不具备一些常见位运算的运算律，请格外注意。
- std 使用 C++ 语言，保证时限是 std 用时的 1.5 倍以上，**但是不保证其他语言能够通过本题**。
- 对于 C++ 选手，如果你直接复制上面的生成器，保证生成器运行总时间不超过 300ms。


title: 电学实验

description:
物理课上，小L和小K在做电学实验：“探究电阻两端的电压一定时，通过电阻的电流和电阻的大小的关系”。在这一实验中，控制电阻箱两端的电压为 $1~ V$ ，调节旋钮改变电阻箱的电阻，分别改为 $1 ~ \Omega , 2 ~ \Omega , 3 ~ \Omega , \ldots , n ~ \Omega $ ，分别读出对应的电流表示数为 $1 ~ A, \dfrac 1 2 ~  A , \dfrac 1 3 ~ A , ... ,\dfrac 1 n ~ A$ 。

在描述实验结论的时候，小L和小K产生了分歧。

小K：“众所周知，电阻两端的电压一定时，通过电阻的电流和电阻的大小成反比。也就是说，如果电阻箱两端电压保持不变，电阻箱的电阻为 $x ~ \Omega $ ，则通过电阻箱的电流为 $\dfrac 1 x ~ A$ 。”

小L：“但是我们为什么不可以用一个最高 $n-1$ 次的曲线去拟合它呢？”

为了改变小L的错误认识，小K决定先让 **小L按自己的结论** 去计算出电阻箱的电阻为 $(n+1) ~ \Omega$ 时，通过电阻箱的电流，然后进行实验，检验答案的正确性。同时，为了让小L更深刻地认识到自己的错误，小K决定进行多组实验，每组实验取不同的 $n$ 。

但是，小L在求解关于这 $n$ 组实验数据的最高 $n-1$ 次曲线时，遇到了问题。小L不想手算出这条曲线和曲线在 $(n+1) ~ \Omega $ 时的值，所以他找到了你，希望你能够求出这个值。

为了使运算更方便，小L将所有数据转化为取模 $998244353$ 意义下的整数值，你的输出也应该是这个整数值。但是，有时候数据的组数过多，导致实验数据或最后的运算结果没有意义，此时你需要输出 `-1` 。

inputFormat:
输入第一行有一个整数 $T$ ，表示进行了 $T$ 组实验。

每组实验一行，有一个整数 $n$ 。

outputFormat: 对于每组实验，输出 **按照小L的结论** ，电阻箱电阻为 $(n+1) ~ \Omega$ 时对应的电流值。如果实验数据或求得的结果在模意义下没有定义，输出 `-1`  。


title: 篮球统计

background:
小L喜欢唱、跳、Rap和篮球。

在同一时刻，篮球场上可能会有很多个在空中的篮球，小L想统计这些篮球的信息。

description:
当一个篮球被抛到空中时，小L会记下一个时刻 $l$ ，此时这个篮球开始被小L统计；当一个篮球被接住时，小L会记下一个时刻 $r$ ，在这之后这个篮球的状态不再被小L统计。对于每个篮球，小L会计算出在时刻 $l$ 这个篮球的高度和向上的初速度。

对于一个时刻 $x$ ，小L想知道，对于所有此时还在空中的篮球，高度最高的篮球的高度是多少。

**注意** ：被发现的篮球的出现时间 $l,r$ 和小L统计信息的时刻 $x$ 均没有任何单调性。

inputFormat:
输入的第一行为一个整数 $m$ 。

接下来的 $m$ 行，每行为一个操作或询问，为以下形式之一：

1.  `add a v l r` ：小L发现了一个在空中的篮球，这个篮球在时刻 $l$ 被抛向空中，在时刻 $r$ 被接住，这个篮球在时刻 $l$ 的高度是 $a$ ，向上的初始速度为 $v$ 。

2.  `query x` ：请告诉小L，在他已经给出的信息中，在时刻 $x$ 在空中的所有篮球中最高的高度是多少。

outputFormat:
对于每个 `query` 操作，输出一行，为这个最高的高度。如果此时不存在在空中的篮球，输出 `Undefined` 。

为了减小精度误差，推荐使用 `long double` 类型存储浮点数，输出格式为 `%Lf` 。

为了避免精度问题，本题使用 **Special Judge** 。如果您的答案与标程的答案相差小于等于 $0.005$ ，则会被视为是正确的。

hint:
对于 $30\%$ 的数据， $m\le 5000$

对于另外 $30\%$ 的数据， $-100< l,r,x< 100$

对于 $100\%$ 的数据， $1\le m\le 100000,-1000< a,v < 1000,-10^6< l,r,x < 10^6,l\le r$ ，保证输入中所有的小数均为 $3$ 位小数。

篮球高度可能是负数。

### 小K教你学物理

本题中所有的单位均采用国际单位制。即时间单位是秒（ $s$ ），长度单位是米（ $m$ ）。

本题中取重力加速度 $g=9.8 ~ m \cdot s^{-2}$ 。

省略掉篮球横向的位移，可以将篮球的运动看做是 **竖直上抛运动** 。根据题目中给出的信息，已知篮球初始的高度 $a$ ，初速度 $v$ ，重力加速度 $g$ ， **在空中的时间**  $t$ ，则篮球在这一时刻的高度是 $-\dfrac 1 2 g t^2 + vt+a$ 。


title: 秩序魔咒

description:
现代魔法师小L和小K正在研究魔咒。

“你知道如何使用魔咒吗？”

“当然知道，这是一个现代魔法师最基本的修养。”

“那你对魔咒的发展史了解多少？”

“课上讲的我还记得一点。那是在很久很久之前了。当时，世界上还没有人会使用魔咒，而混沌魔法成为了魔法界当时的主流魔法。这是一种邪恶的法术，不需要技巧，不需要规则，内心越黑暗，力量越强。于是，邪恶的魔法师们自相残杀，弄得天昏地暗，血流成河。其中，以自称‘混沌恶魔’的魔法师为首的魔法师集团通过极其肮脏的手段控制了几乎整个魔法界，让那些向往秩序与和平的魔法师难以生存。就在这个时候，世界救星的救星出现了。名为莱赫穆拉和肯埋多卡的两名魔法师勇敢地站了出来，仅凭两个人的力量就与混沌恶魔集团展开了决战，可终究寡不敌众，被逼到了绝境。就在混沌恶魔的最后一击打中他们的身体时，莱赫穆拉和肯埋多卡利用这一击的巨大魔力，将两人余下的全部魔法与意志升格成了概念，创造了秩序魔咒体系，扭转了世界理论，使得混沌魔法被永远封印。而混沌恶魔也在这强烈的扭曲中灰飞烟灭。从此，魔法界由混沌纪元进入了秩序纪元，人们遵循莱赫穆拉和肯埋多卡这两位圣人的遗志，在秩序魔咒体系下使用魔咒，直到现在。”

“原来是这样。我们如今需要遵循一系列原则来使用魔咒，是这个原因啊。”

“是啊，这正是两位圣人为维持现在这个世界不退回混沌纪元而做的努力。话说，你是上个星期才刚刚上了第一堂魔法课，你还记得使用魔咒的几个原则吗？”

“我想想。第一，必须出现在秩序序列中。当时二位圣人留下来的体系，经过后代魔法师不懈的努力，被翻译成了名为秩序序列的存在。为了方便现代魔法师使用，**秩序序列只由英文小写字母组成**。由于体系的力量过于强大而不能仅仅限制在一个序列中，**魔法师们分别将两位圣人的遗志转移到了两个秩序序列里**。魔咒必须受到秩序序列的限制。**具体来说，是必须出现在秩序序列里（是秩序序列的子串）**。由于二位圣人的遗志不可分割，**魔咒必须同时出现在两个秩序序列里**。第二，为了让魔咒稳定而精确，秩序体系规定了魔咒的形态。**具体来说，魔咒的第一个字符需要与魔咒的倒数第一个字符相同，魔咒的第二个字符需要与魔咒的倒数第二个字符相同，以此类推**。这样就可以使魔咒对称而有秩序了。还有的话，让我看看……”

“别看了别看了，最重要的就是这些了。还有，你说不定还不知道，魔咒越长，力量越强大。”

“是这样的吗？难怪那天老师演示的魔咒魔力比我的大那么多。”

“是的是的。你是不是已经发现了，魔咒的力量是有最高限制的？”

“啊，好像没错。但老师那天说，最强魔咒的使用者还没出现？”

“对。使用者自身必须要有与魔咒同样程度的能力，才可能顺利地使用这个魔咒。我们这些初学者，不知道何年何月才能达到这个程度呢……”

“唉……不如，我们来数一数力量最强的魔咒的长度，和它们有多少个吧。”

“嗯，反正没事可做，我们就来干一干这种力所能及的事吧。”

于是，小L和小K就开始数最强魔咒的长度和个数。可过了不一会儿，它们就坚持不住了，因为秩序序列实在太长太长了。

现在，你作为一个资深魔法师，有必要告诉他们这种基本的常识。你当然已经知道两个秩序序列的形态，请你帮小L和小K算出最强魔咒的长度和个数。

inputFormat:
第一行，两个整数$n,m$，分别表示两个秩序序列的长度。

接着第二行与第三行，两个字符串，表示两个秩序序列，长度分别为$n,m$。

outputFormat: 一行两个整数，用单个空格隔开，分别表示最强魔咒的长度与个数。

hint:
**样例解释**

样例1：符合规定的魔咒有$a,b,aa,aaa,aba,bab$，其中最强的有$aaa,aba,bab$，长度为$3$，共$3$个。

样例2：符合规定的魔咒有$a,b,aa,aaa,aaaa,bb,baab,aba,aabaa,c$，其中最强的有$aabaa$，长度为$5$，共$1$个。

**数据范围**

由于某些原因，本题需要使用$Subtask$。为取得一个$Subtask$的得分，你需要通过此$Subtask$中的所有数据点。
|  | 分值 | $n,m$取值范围 | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: |
| $Subtask1$ | $0$ | $1\le n,m\le260817$ | 是样例 |
| $Subtask2$ | $5$ | $1\le n,m\le260817$ | 两个秩序序列由同一字符组成 |
| $Subtask3$ | $5$ | $1\le n,m\le10$ | 无 |
| $Subtask4$ | $10$ | $1\le n,m\le300$ | 无 |
| $Subtask5$ | $10$ | $1\le n,m\le2000$ | 无 |
| $Subtask6$ | $30$ | $1\le n,m\le260817$ | 两个秩序序列相同 |
| $Subtask7$ | $40$ | $1\le n,m\le260817$ | 无 |

显然，相同的魔咒数量只计一次。保证至少存在一个长度不小于$1$的符合规定的魔咒。

注意时限为$3s$。


title: 圣剑护符

background:
小L和小K正在研究传说中的圣剑。

“所谓圣剑，是封入了各种护符并将其固定为刀剑外形的一种东西。据说一旦用咒力线把护符们接合在一起，就会产生复杂的相互干涉作用。”

description:
小L和小K面前的圣剑由 $n$ 块护符组成，分别编号为 $1,2,\ldots , n$ ，有 $n-1$ 条咒力线连接两块护符，形成了一个树形结构。

经过小L和小K的长时间的研究，他们发现护符之间的相互作用并不复杂。每块护符都有一个属性值，第 $i$ 块护符的属性值记为 $v_i$ 。这个值的每个二进制位上的 $0$ 或 $1$ 表示这块护符是否拥有特定属性。所有属性值中相同的二进制位对应的是相同的属性。

对于一系列护符（护符的集合），对于每种特定属性，统计其中包含这一属性的护符数量，如果为偶数，则这一系列护符形成了干涉，最终的属性值对应的二进制位上为 $0$ ，如果为奇数则干涉后剩下了一块护符的影响，对应的二进制位为 $1$ 。也就是说， **护符集合的属性值为单个护符的属性值的异或和** 。 **空集的属性值定义为 $0$** 。

现在，小L想知道，如果取出两块护符 $x,y$ 间的简单路径上的所有护符，能否找到两个不相等的子集，使得两个子集的属性值相同（注意到空集也是路径上所有护符集合的子集）。同时，小K还会将两块护符间的路径上的所有护符取出进行调整，将所有这些护符的属性值在某些相同二进制位上进行修改（即 $0$ 变为 $1$ ， $1$ 变为 $0$ ），可以看做是将所有这些护符的属性值异或上了一个值。

inputFormat:
输入的第一行为两个整数 $n,q$ ，分别表示护符的数量和小L和小K的操作的数量。

下一行有 $n$ 个整数，第 $i$ 个数表示第 $i$ 块护符的属性值 $v_i$ 。

接下来的 $n-1$ 行，每行有两个整数 $x,y$ ，表示有一条咒力线连接了 $x,y$ 两块护符。保证形成一个树形结构。

接下来的 $q$ 行，每行一个操作，形式如下：

1.  `Update x y z` ：将编号分别为 $x,y$ 的两块护符间的简单路径上的所有护符的属性值异或上一个值 $z$ 。

2. `Query x y` ： 判断对于编号分别为 $x,y$ 的两块护符间的简单路径上的护符的集合，是否存在两个不相等的子集，使得两个子集的属性值相同。

outputFormat: 对于每个 `Query` 操作，输出一行 `YES` 或 `NO` 。

samples:
2 3
3 4
1 2
Query 1 2
Update 2 2 7
Query 2 1

hint:
由于某种原因，本题将采用 **捆绑测试** 。只有通过一个子任务内的所有测试点，才能得到该子任务的全部分数，否则得 $0$ 分。

$Subtask\#1$ ： $20pts$ ， $x,y$ 在树上的距离小于等于 $5$ 。

$Subtask\#2$ ： $40pts$ ， $n,q\le 5000,0\le v_i,z\le 2^{10}$

$Subtask\#3$ ： $40pts$ ，无特殊限制。

对于 $100\%$ 的数据，有 $1\le n,q\le 10^5,1\le x,y\le n,0\le v_i,z< 2^{30}$


title: 【模板】二次剩余

description:
给出 $N,p$，求解方程

$$
x^2 \equiv N \pmod{p}
$$

多组数据，**且保证 $p$ 是奇素数。**

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

第 $2\sim T+1$ 行，每行两个整数 $N$ 和 $p$，含义详见题目描述。

outputFormat:
输出共 $T$ 行。

对于每一行输出，若有解，则按 $\bmod ~p$ 后递增的顺序输出在 $\bmod~ p$ 意义下的全部解；若两解相同，只输出其中一个；若无解，则输出 `Hola!` 。


title: [yLOI2019] 青原樱

background:
> 星川之下皆萤火尘埃，
> 我独行在人潮你天真而待。
> 相遇若是借丹青着色，
> 青原上 绯樱如海。

——银临《青原樱》(Cover 人衣大人)

description:
扶苏是一个非常喜欢边听古风鸽边写数学题的人，因此这道题其实是个五三原题。

扶苏希望重现青原上樱花盛开的景色，于是他准备了很多**互不相同**樱花树幼苗，准备种成一行。

这一行中，一共有 $n$ 个位置可以种下樱花，而扶苏准备了 $m$ 支幼苗。由于樱花盛放时对左右空间需求非常大，所以樱花不能紧挨着种植，也就是任意两支幼苗之间必须至少存在一个不种花的空位置。

按照这种方式种花并不难，但是令扶苏感到好奇的是一共有多少合法的方案让他把这 $m$ 支幼苗都种下去。一个方案是合法的当且仅当他满足上一段中叙述的要求。如果我们将花按照 $1,2,3,\dots,m$ 编号，两种方案不同当且仅当被选择种花的位置不同或从左向右数花的编号序列不同。

为了避免输出过大，答案对一个参数 $p$ 取模。

inputFormat:
每个输入文件中有且仅有一组测试数据。

测试数据只有一行四个整数，依次代表 $type,~n,~m,~p$，其中 $type$ 是一个帮助你判断测试点类型的参数，会在数据范围中说明。

outputFormat: 输出一行一个整数，代表答案对 $p$ 取模的结果。


title: 【模板】扫描线 & 矩形面积并

description: 求 $n$ 个四边平行于坐标轴的矩形的面积并。

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

接下来 $n$ 行每行四个非负整数 $x_1, y_1, x_2, y_2$，表示一个矩形的四个端点坐标为 $(x_1, y_1),(x_1, y_2),(x_2, y_2),(x_2, y_1)$。

outputFormat: 一行一个正整数，表示 $n$ 个矩形的并集覆盖的总面积。

hint:
对于 $20\%$ 的数据，$1 \le n \le 1000$。
对于 $100\%$ 的数据，$1 \le n \le {10}^5$，$0 \le x_1 < x_2 \le {10}^9$，$0 \le y_1 < y_2 \le {10}^9$。

Updated on 4.10 by Dengduck（口胡） \& yummy（实现）：增加了一组数据。


title: [CmdOI2019] 口头禅

background:
**温馨提示** : 请注意本题特殊的时空限制。

（若您认为使用了复杂度正确的算法但被卡常，可以联系出题人）

一个悠闲的午后，机房里的大佬们都在水群。

description:
蒟蒻出题人收集了某位大佬的 $n$ 条语录，并按时间为序编号为 $1...n$ 。

他发现这位大佬的口头禅是随着时间而变化的，而且里面有些看不懂的内容。

在请教了群 DS 带师之后，他得到了某种 hash 方法，把这些语录都变成了 01 串，这样似乎好懂一些。

为了研究水群的奥秘，他进行了多次询问 : $[l,r]$ **之间的所有语录，最长公共子串的长度是多少**?

出题人知道这并不是一个简单的问题，所以他并不急于即时得知每个询问的答案。

inputFormat:
第一行两个整数 $n,m$ ，表示语录的条数和询问个数。

对于后 $n$ 行，第 $i$ 行表示第 $i$ 条语录，保证字符集为 $\{0,1\}$。

后 $m$ 行，每行两个整数 $l,r(1\leq l<r \leq n)$ ，表示一个询问。

outputFormat: 对于每个询问，输出 $[l,r]$ 之间的所有语录最长公共子串的长度。


title: [PKUWC2018] 随机算法

description:
我们知道，求任意图的最大独立集是一类NP完全问题，目前还没有准确的多项式算法，但是有许多多项式复杂度的近似算法。

例如，小 C 常用的一种算法是：

1. 对于一个 $n$ 个点的无向图，先等概率随机一个 $1\ldots n$ 的排列 $p[1\ldots n]$。

2. 维护答案集合 $S$ ，一开始 $S$ 为空集，之后按照 $i=1\ldots n$ 的顺序，检查 $\{p[i]\}\cup S$ 是否是一个独立集，如果是的话就令 $S=\{p[i]\}\cup S$。

3. 最后得到一个独立集 $S$ 作为答案。

小 C 现在想知道，对于给定的一张图，这个算法的正确率，输出答案对 $998244353$ 取模。

inputFormat:
第一行两个非负整数 $n,m$ 表示给定的图的点数和边数。

接下来 $m$ 行，每行有两个正整数 $(u,v) (u\neq v)$ 描述这张图的一条无向边。

outputFormat: 输出正确率，答案对 $998244353$ 取模。

hint:
#### 样例解释
这张图的最大独立集显然为 $2$，可以发现只有 $p[1]=2$ 时会得出 $S=\{2\}$，否则都是 $S=\{1,3\}$，所以答案是 $\frac{2}{3}$。

#### 数据范围
对于 $10\%$ 的数据，有$1\leq n\leq 9$。

对于 $30\%$ 的数据，有$1\leq n\leq 13$。

对于 $50\%$ 的数据，有$1\leq n\leq 17$。

另有 $10\%$ 的数据，满足给定的图是一条链。

另有 $10\%$ 的数据，满足给定的图是一棵树。

对于 $100\%$ 的数据，有$1\leq n\leq 20$，$0\leq m\leq \frac{n\times (n-1)}{2}$，保证给定的图没有重边和自环。


title: [JSOI2016] 灯塔

description:
`JSOI`的国境线上有$N$座连续的山峰,其中第$i$座的高度是$h_i$.为了简单起见,我们认为这$N$座山峰排成了连续一条直线.如果在第$i$座山峰上建立一座高度为$p(p≥0)$的灯塔,`JYY`发现,这座灯塔能够照亮第$j$座山峰,当且仅当满足如下不等式:

$$h_j \le h_i+p-\sqrt {|i-j|}$$

`JSOI`国王希望对于每一座山峰,`JYY`都能提供建造一座能够照亮全部其他山峰的灯塔所需要的最小高度.你能帮助`JYY`么?

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

接下来$N$行，第$i$行包含一个正整数$h_i$，表示第$i$座山峰的高度。

outputFormat: 第$i$行包含一个非负整数，表示在第$i$座山峰上修建灯塔所需要的最小高度$p_i$


title: 【模板】回文自动机（PAM）

description:
给定一个字符串 $s$。保证每个字符为小写字母。对于 $s$ 的每个位置，请求出以该位置结尾的回文子串个数。

这个字符串被进行了加密，除了第一个字符，其他字符都需要通过上一个位置的答案来解密。

具体地，若第 $i(i\geq 1)$ 个位置的答案是 $k$，第 $i+1$ 个字符读入时的 $\rm ASCII$ 码为 $c$，则第 $i+1$ 个字符实际的 $\rm ASCII$ 码为 $(c-97+k)\bmod 26+97$。所有字符在加密前后都为小写字母。

inputFormat: 一行一个字符串 $s$ 表示被加密后的串。

outputFormat: 一行， $|s|$ 个整数。第 $i$ 个整数表示原串以第 $i$ 个字符结尾的回文子串个数。

samples:
debber
1 1 1 2 1 1

samples:
lwkvjfrphhgkfvzzyx
1 1 2 2 3 1 1 1 1 2 3 1 1 1 1 2 3 4

samples:
azzzyyzyyx
1 2 1 2 3 2 2 2 3 3

hint:
### 样例解释

三个样例解码后分别为：

- $\verb!dfccgs!$；
- $\verb!lxlxlisqiiingwaaaa!$；
- $\verb!aabaabbaaa!$。

### 数据范围及约定

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


title: 【模板】Dirichlet 前缀和

background: 模板题，无背景。

description:
给定一个长度为 $n$ 的数列 $a_1,a_2,a_3,\dots,a_n$。

现在你要求出一个长度为 $n$ 的数列 $b_1,b_2,b_3,\dots,b_n$，满足

$$b_k=\sum_{i|k}a_i$$

由于某些神秘原因，这里的 $b_k$ 要对 $2^{32}$ 取模。

inputFormat:
为了避免过大的输入，本题的输入使用随机数生成器。

输入中只有一行两个整数 $n,seed$。其中 $seed$ 为 $32$ 位无符号整数，用来生成数据。

接下来，你要调用 $n$ 次随机数生成器，分别生成 $a_1\sim a_n$。

对于```C/C++```选手，生成器模板如下：

```cpp
#define uint unsigned int
uint seed;
inline uint getnext(){
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return seed;
}
```

对于```Pascal```选手，生成器模板如下：

```pas
var seed:dword;
function getnext:dword;
begin
	seed:=seed xor(seed shl 13);
	seed:=seed xor(seed shr 17);
	seed:=seed xor(seed shl 5);
	getnext:=seed;
end;
```

注意：**所有 $n$ 个数均为 $32$ 位无符号整数**。

outputFormat: 为了避免过大的输出，你只需输出一个 $32$ 位无符号整数，表示所有 $b_i$ 的异或和。


title: [DBOI2019] 德丽莎世界第一可爱

background:
```cpp
众所周知，德丽莎世界第一可爱。
——zhengrunzhe
```

你正在打崩坏$3$，突然家长来了，于是你装作在打数据结构题。

![神恩颂歌](https://cdn.luogu.com.cn/upload/pic/70922.png)

description:
有 $n$ 个崩坏兽，每个崩坏兽有五个属性值：health 生命力，energy 能量力，attack 攻击力，defense 防御力， collapse 崩坏能。

德丽莎可以任选一只崩坏兽展开攻击。假如她干掉了崩坏兽$i$ 那么她会收获 `collapse[i]` 的可爱值。由于德丽莎越战越勇，她打的下一只崩坏兽 $j$ 需要满足 `health[j]≥ health[i]` , `energy[j]≥energy[i]` , `attack[j]≥attack[i]` , `defense[j]≥defense[i]`。

请你帮帮德丽莎计算一下她能够获得的最大可爱值。

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

接下来$n$行，第$i+1$行五个整数`health[i]`，`energy[i]`，`attack[i]`。`defense[i]`，`collapse[i]`，代表着第 $i$ 只崩坏兽的属性值。

outputFormat: 一行一个整数，代表最大可爱值（必须击杀至少一只崩坏兽），答案保证不会超过 long long 范围（$2^{63}-1$）。

hint:
Subtask #1（$20$分）：

$1\leq n\leq 100$。

Subtask #2（$20$分）：

$1\leq n\leq 10000$。

Subtask #3（$60$分）：

$1\leq n\leq 50000$。

对于 $100\%$ 的数据，满足 $|\mathrm{health}_i|, |\mathrm{energy}_i|, |\mathrm{attack_i}|, |\mathrm{defense}_i| \le 10^5$，$| \mathrm{collapse}_i|\le 10^9$。

### 题目提供者：[$\color{red}{zhengrunzhe}$](https://www.luogu.org/space/show?uid=14374)


title: [DBOI2019] 巫女的职责

background:
作为八重村的巫女，樱承担着守卫村庄的责任，村子里受到了崩坏的威胁，八重樱，出击！

![bachongyingyingying](http://i0.hdslb.com/bfs/article/81e9465c02e29053f9fbe7c70d3c2644691abda2.png)

description:
八重古村有 $n$ 座房屋，一开始所有的房子之间都没有路，随着古村的发展，慢慢会出现连接两栋房屋的双向道路。

村民们原本过着无忧无虑的幸福生活，直到与文明作对——崩坏来了，慢慢地，某栋房屋也许会在遭受崩坏兽的侵袭，每只崩坏兽都有着一定的崩坏能，每户人家也许会存在着多只崩坏兽。

樱来了，她接受了驱魔委托，每个委托都是从驱逐某个房子到另一个房子的崩坏兽，樱只能走已有的路，由于这样的路径也许有很多条，聪明的樱只会选择在它们所有路径中都会走过的某些点，即必经点，每次委托樱会在两点间的所有必经点驱魔。

inputFormat:
第一行两个整数：$n,m$ 表示房屋数和事件数

接下来 $m$ 行，每行三个正整数：$opt,x,y$

$opt=1 $时，表示房子 $x$ 和房子 $y$ 间修了一条双向道路(保证没有重边，但不保证没有自环，如有请忽略。)

$opt=2$ 时，表示房子 $x$ 来了一只崩坏能为 $y$ 的崩坏兽

$opt=3$ 时，表示樱完成了一次从 $x$ 到 $y$ 的驱魔委托(不保证 $x$ 与 $y$ 连通，不连通输出 $0$ 即可)

强制在线：记上次$3$的答案为 $\text{lastans}$，初值为 $0$，实际上的$x,y$ 用函数解码：
```cpp
inline const void decode(int &x)
{
	x^=lastans%n;
	if (x>n)x%=n;
	if (!x)x=1;
}
```

outputFormat: 对于每个 $3$ 事件，输出一行一个数表示樱清除的崩坏能的值，答案保证在 $[0,2^{63})$

hint:
【样例 $1$ 说明】

第四个事件使 $1$ 号房屋有 $1$ 点的崩坏能。

第五个事件使 $1$ 号房屋增加了 $2$ 点的崩坏能，此时其崩坏能值为 $3$。

第六个事件显然答案为 $3$，更新 $\text{lastans}=3$ 。

第七个事件真实的 $x=1$，$y=3$，由于第六个事件已经在 $1$ 驱魔，所以没有崩坏能。

$Subtask$ #$1$（$20$ 分）：

$1\leq n,m\leq 100000$。

$Subtask$ #$2$（$70$ 分）：

$1\leq n,m\leq 200000$。

$Subtask$ #$3$（$10$ 分）：

$1\leq n,m\leq 500000$。

所有测试点的时间限制统一为 $1.5 \text s$，内存限制统一为 $125 \text{MiB}$。

### 题目提供者：[$\color{red}{zhengrunzhe}$](https://www.luogu.org/space/show?uid=14374)


title: [MtOI2019] 小铃的烦恼

background: 在幻想乡中，本居 小铃(Motoori Kosuzu)不仅经常被人撞，还要整理铃奈庵的书籍，她有很多烦恼。

description:
小铃每天都会整理一次铃奈庵的书籍。这次桌子上有 $n$ 本魔法书，这些书一次排成一排，每本书有一个魔法属性和编号。

最开始这些书的魔法属性都是一样的，但是因为被人多次使用，魔法属性发生了变化，小铃想让所有书的魔法属性重新全部相同。

这次小铃找到了雾雨 魔理沙(Kirisame Marisa)帮忙整理书籍，每次魔理沙可以释放选定魔法，魔法会随机选择两本书 $a,b$ ( $a$ 不等于 $b$ )。

选定这两本书后，魔理沙会释放转移魔法，使得有 $p_{a,b}\ (p_{a,b}\in (0,1])$ 的概率，第 $b$ 本书的魔法属性变成第 $a$ 本书的魔法属性。也就是说有 $1-p_{a,b}$ 的概率，使得你**即使选定了 $a,b$ 两本书，但是魔法属性的转移不成功，意味着这次操作是无效的** 。

注意 $p_{a,b}$ 是对于**转移是否成功的概率**，和随机选择两本书的操作互不影响。

现在小铃想知道，求期望操作多少次，才能使所有的书魔法属性都一样？由于时间紧迫，小铃找到了你，希望你可以帮其解决这个问题，不然小铃就不会给你这题的分了。

inputFormat:
第一行一个字符串，第 $i$ 个字符表示第 $i$ 本书的魔法属性，注意每本书的魔法属性为 $A$ 到 $Z$ 的所有的大写字母中的任意一字母。(设字符串的长度为 $n$ ) 。

第二行到第 $n+1$ 行，每行 $n$ 个实数，第 $i$ 行的第 $j$ 个数表示 $p_{i,j}$ 。

outputFormat: 结果，精确到小数点后 $1$ 位。

hint:
对于前 $10\%$ 的数据，$n\leq 10$，且最多有一种不同的魔法属性。

对于另外 $20\%$ 的数据，$n\leq10$，且最多有两种不同的魔法属性，并且其中一种的魔法属性的个数小于等于 $1$  。

对于 $100\%$ 的数据，$n\leq2\times 10^3$ 。

对于所有数据，满足 $\left(\sum\limits_{a=1}^{n}\sum\limits_{b=1}^{n}p_{a,b}\right) = n^2$ 。

### 题目来源

[迷途之家2019联赛](https://www.luogu.org/contest/20135)(MtOI2019) T3

出题人：Qiuly


title: [yLOI2019] 梅深不见冬

background:
> 风，吹起梅岭的深冬；霜，如惊涛一样汹涌；
> 雪，飘落后把所有烧成空，像这场，捕捉不到的梦。
> 醒来时已是多年之久，宫门铜环才长了铁锈，也开始生出离愁。

——银临《梅深不见冬》

description:
扶苏从深冬的梅岭走出，来到了一棵有 $n$ 个节点的有根树上。

如果你不知道什么是树，可以认为树是一个边数恰好比节点个数少一的简单无向连通图。

如果我们规定 $x$ 是树 $T$ 的根，那么定义任意一个节点 $y$ 到根的路径就是从 $y$ 出发不重复经过节点到达 $x$ 所经过的所经过的点构成的点集。可以证明这样的点集有且仅有一个。

定义一个节点 $u$ 是节点 $v$ 的孩子，当且仅当 $u$ 与 $v$ 相连且 $u$ 不在 $v$ 到根的路径中。如果 $u$ 是 $v$ 的孩子，那么定义 $v$ 是 $u$ 的家长节点。

如果我是 @[\_rqy](https://www.luogu.org/space/show?uid=7868) 那种~~毒瘤~~神仙的话，可能会问你每个节点的孩子数不超过 $k$ 的 $n$ 个节点的带标号无根树一共有多少个，可惜这个问题我也不会，所以我不会问你这么毒瘤的问题。

扶苏从这棵 $n$ 个节点的树的 $1$ 号节点出发，沿着树上的边行走。当然我们规定 $1$ 号节点是这棵树的根。他所行走的规定是：当扶苏在节点 $u$ 时，扶苏要么在 $u$ 的孩子中选择一个**没有到达过**的节点 $v$ 并行走到 $v$，要么选择回到 $u$ 的家长节点。

现在给每个节点一个权值 $w$，其中 $i$ 号节点的权值为 $w_i$。他想给这棵树的某个节点放上从梅岭带出的梅花。我们规定扶苏能在节点 $u$ 放上梅花当且仅当满足如下条件：

> 扶苏当前在节点 $u$。
>
> 对于 $u$ 的所有孩子 $v$，节点 $v$ 被放上了 $w_v$ 朵梅花。

同时，扶苏可以在**任意时刻**收回**任意节点**上的梅花，在收回梅花时不需要走到对应节点。

现在扶苏想问问你，对于每个节点，如果他想在 $i$ 号节点上放 $w_i$ 朵梅花，那么他最少要从梅岭带出多少朵梅花。

inputFormat:
每个输入文件中都有且仅有一组测试数据。

数据的第一行是一个整数 $n$ 代表树的节点个数。

第二行有 $n-1$ 个用空格隔开的整数，第 $i$ 个整数 $p_i$ 代表第 $i+1$ 号节点的家长节点编号。

第三行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表 $w_i$。

outputFormat: 输出一行 $n$ 个用空格隔开的整数，第 $i$ 个整数代表想在 $i$ 号节点上放 $w_i$ 朵梅花需要准备的梅花个数。

hint:
#### 输入输出样例 1 解释

![qwq](https://cdn.luogu.com.cn/upload/pic/72286.png)

样例 1 的输入如上图，每个节点都需要放 $1$ 一朵梅花。

如果在 1 号节点放梅花，则从一号点运动到 2 号点，然后运动到 3 号点，在 3 号点上放一朵梅花，返回 2 号点，在 2 号点上放一朵梅花，同时收回三号点的梅花，然后返回 1 号点，将从 3 号点收回的梅花放到 1 号点即可。一共需要两朵梅花。

在 2、3 号节点放梅花的方案类似。

#### 输入输出样例 3 解释

![qwq](https://cdn.luogu.com.cn/upload/pic/72287.png)

样例 3 的输入如左图。

先从 1 号节点运动至 3 号节点，再运动至 5 号节点，在 5 号节点上放置 $12$ 朵梅花，然后返回 3 号节点，在 3 号节点上放置 $1$ 朵梅花，收回五号节点的 $12$ 朵梅花，返回 1 号节点。

然后运动到 2 号节点，通过 4 号节点运动到 6 号节点，放下 $15$ 朵梅花，返回 4 号节点放下 $5$ 朵梅花，此时树上有的梅花数为 $5 + 15 + 1 = 21$，分别在 4 号、6 号和 3 号节点上。然后收回 6 号节点的梅花，返回 2 号节点，放下 $14$ 朵梅花，收回 4 号节点的，返回 1 号节点，在 1 号节点上放置 $3$ 朵梅花，即可达到在 1 号节点上放梅花的目的。

可以验证最大花费为 $21$。其他节点的答案同理。

请注意，其他节点的答案不一定是按照该节点的运动路径行走得到的。

---

#### 数据规模与约定

| 测试点编号 |  $n = $  | 测试点编号 |  $n = $  |
| :--------: | :------: | :--------: | :------: |
|     1      |   $1$    |     11     | $100003$ |
|     2      |   $8$    |     12     | $100003$ |
|     3      |   $8$    |     13     | $100003$ |
|     4      |   $8$    |     14     | $100003$ |
|     5      |   $8$    |     15     | $100004$ |
|     6      | $100000$ |     16     | $100004$ |
|     7      | $100000$ |     17     | $100004$ |
|     8      | $100002$ |     18     | $100004$ |
|     9      | $100002$ |     19     | $100004$ |
|     10     | $100002$ |     20     | $100004$ |

- 对于测试点 5、6，满足特殊性质：每个节点的孩子结点个数不超过 $2$。
- 对于测试点 8 到测试点 10，满足特殊性质：每个节点的孩子节点个数不超过 $5$。
- 对于测试点 11 到测试点 14，满足特殊性质：任意一个节点到根的路径上的点数不超过 $3$，也即树高不超过 $3$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5 + 4,~1 \leq p_i \leq i,~1 \leq w_i \leq 1000$。

---

#### 提示

- $n$ 的末位数字可以帮助你快速的判断测试点所具有的的特殊性质。


title: [MtOI2019] 永夜的报应

background:
在这世上有一乡一林一竹亭，也有一主一仆一仇敌。

有人曾经想拍下他们的身影，却被可爱的兔子迷惑了心神。

那些迷途中的人啊，终究会消失在不灭的永夜中……

description:
蓬莱山 辉夜(Kaguya)手里有一堆数字。

辉夜手里有 $n$ 个非负整数 $a_1,a_2\cdots a_n$，由于辉夜去打 Gal Game 去了，她希望智慧的你来帮忙。

* 你需要将这些数分成若干组，满足 $n$ 个数中的每一个数都恰好被分到了一个组中，且每一组至少包含一个数。

定义一组数的权值为该组内所有数的**异或和**。请求出一种分组方案，使得分出的所有组数的权值之和最小，输出权值之和的最小值。

inputFormat:
输入的第一行包含一个正整数 $n$，表示给定的非负整数的数量。

接下来一行包含 $n$ 个非负整数 $a_1,a_2\cdots a_n$。

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

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

一种最优的分组方案如下：

- 将第 $1$ 个数和第 $3$ 个数分为一组，该组的权值为 $1\oplus 5 = 4$；
- 将第 $2$ 个数分为一组，该组的权值为 $2$。

该分组方案的所有组的权值之和为 $4 + 2 = 6$，可以证明，不存在权值之和更小的分组方案。

**样例 $2$ 解释：**

一种最优的分组方案如下：

- 将第 $1$ 个数和第 $5$ 个数分为一组，该组的权值为 $9\oplus 9 = 0$；
- 将第 $2$ 个数和第 $4$ 个数分为一组，该组的权值为 $18\oplus 25 = 11$；
- 将第 $3$ 个数和第 $6$ 个数分为一组，该组的权值为 $36\oplus 32 = 4$。

该分组方案的所有组的权值之和为 $0 + 11 + 4 = 15$。可以证明，不存在权值之和更小的分组方案。

### 子任务

- 对于 $80\%$ 的数据，满足 $n\leq 15$。
- 对于 $100\%$ 的数据，满足 $n\leq 10^6,a_i \leq 10^9$。

### 题目来源

[迷途之家2019联赛](https://www.luogu.org/contest/20135)(MtOI2019) T1

出题人：disangan233


title: [IOI2019] 排列鞋子

description:
**由于洛谷数据点限制，本题仅评测其中的 $100$ 个数据点。**

如果需要测试全部数据，有以下两道题：

1. [Subtask 1-3](/problem/U98795)
2. [Subtask 4-6](/problem/U98796)

两题满分均为 $50$ 分，包含 Subtask中所有的测试点。

---

Adnan 拥有巴库最大的鞋店。现在有一个装着 $n$ 双鞋的箱子刚运到他的鞋店。每双鞋是大小相同的两只：一只左脚，一只右脚。Adnan 把这 $2n$ 只鞋排成一行，该行总共有 $2n$ 个**位置**，从左到右编号为 $0$ 到 $2n-1$ 。

Adnan 想把这些鞋子重新排成**合法的排列**。一个排列是合法的，当且仅当对于所有的 $i(0\leqslant i \leqslant n - 1)$，以下条件都成立：

- 在位置 $2i$ 和 $2i+1$ 上的鞋子大小相同；
- 在位置 $2i$ 上的鞋子是一只左脚鞋；
- 在位置 $2i+1$ 上的鞋子是一只右脚鞋。

为实现上述目标，Adnan 可以做一系列对调。在每次对调中，他选择当前**相邻**的两只鞋进行对调（也就是把它们拿起来，然后将每只鞋子放回到另一只鞋子原来的位置上）。两只鞋子是相邻的，当且仅当其位置编号的差为 $1$。

请求出 Adnan 最少要做出多少次对调，才能得到一个合法排列。

inputFormat:
第一行一个正整数 $n$，表示有 $n$ 双鞋。

第二行 $2n$ 个整数 $S_i$，第 $i$ 个整数表示位置编号为 $i-1$ 的鞋子。其中 $|S_u|\neq 0$，等于最初在位置 $i$ 上的鞋子的大小。这里 $|x|$ 表示 $x$ 的绝对值，当 $x\geq 0$ 时等于 $x$，当 $x < 0$ 时等于 $-x$。如果 $S_i < 0$，则 $i$ 位置上的鞋子是一只左脚鞋，否则是右脚鞋。

outputFormat: 输出一行一个整数，表示最少对调次数。

hint:
**样例说明 1**

Adnan 可以通过 $4$ 次对调而得到一个合法的排列。

例如，他可以先对调 $1$ 和 $-1$，再对调 $1$ 和 $-2$，再对调 $-1$ 和 $-2$。最后对调 $-2$ 和 $2$。随后他就可以得到合法的排列 。无法用少于 $4$ 次对调就得到合法的排列，因此输出 $4$。

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

**样例说明 2**

Adnan 可以对调在位置 $2$ 和 $3$ 上的鞋子来得到合法的排列$[-2,2,-2,2,-2,2]$，因此应当输出 $1$。

**数据范围**

对于所有数据：

- $1\leqslant n\leqslant10^5$；
- 对于所有$i(0\leqslant i\leqslant 2n-1)$，都有$1\leqslant \left|S_{i+1}\right|\leqslant n$；
- 总有某个合法的排列可以经由一系列对调而得到。

详细子任务附加限制与分值如下表：

| 子任务编号 | 附加限制 | 分值 |
|:---:|:---:|:---:|
| $1$ | $n=1$ | $10$|
|$2$|$n\leqslant8$|$20$|
|$3$|所有鞋子大小都是相同的|$20$|
|$4$|所有在位置 $0,\dots,n-1$ 上的鞋都是左脚鞋，而在位置 $n,\dots,2n-1$ 上的鞋都是右脚鞋。而且对于所有 $i(0\leqslant i\leqslant n-1)$，在位置 $i$ 和 $i+n$ 上的鞋子大小相同|$15$|
|$5$|$n\leqslant10^3$|$20$|
|$6$|无附加限制|$15$|


title: Chino的数列

background:
没有背景

我写不出来了qwq

description:
Chino给定了 $n$ 个数 $a_1...a_n$，给定常数 $s,m$ ，她会轮流对这 $n$ 个数做 $k$ 组操作，每组操作包含以下几步：

1. $\operatorname{swap}(a_s,a_m)$（交换 $a_s,a_m$）。

2. 将 $n$ 个数都向前平移一位（第 $1$ 个移动到第 $n$ 个位置上）。

Chino 想知道，$k$ 组操作后，这 $n$ 个数分别是多少？

Orz yky,dyh,wjk,jjy,cxr,gsy,cpy,zcy,tyz,yy,hz,zhr,ygg

inputFormat:
第一行，四个数，$n,s,m,k$。

接下来一行 $n$ 个数，分别代表 $a_1,a_2...a_n$。

outputFormat: 输出一行，$n$ 个数，分别代表 $a_1,a_2...a_n$。

hint:
对于 $40\%$ 的数据，$1 \leq k \leq 10^7$

对于 $100\% $的数据，$1 \leq n \leq 80$，$1 \leq s,m\leq n$，$1 \leq k \leq 10^{18}$

所有数字均在 `long long` 以内


title: 失昼城的守星使

background:
> 月伏潮汐生，星染万屿寂，无晦明之变化者，是为失昼。   ————《失昼城手札·起源》

失昼城四面环海，建城于7325年前。

失昼城没有黑夜白天的变化，一轮明月自建城伊始就挂在天空，故名失昼。

失昼城城主月凌霜，掌控着失昼城的守星塔，守星塔在终日无昼的失昼城中作为照明的灯塔，一直是城里人们的精神寄托，她的另一个身份是失昼城的守星使，比起作为城主，月凌霜更喜欢守着守星塔。

失昼城的特殊环境导致其空间异常不稳定，根据失昼城城史记载，七千多年历史的失昼城，其和平的时间总共不超过三百年，其他大部分时间失昼城局部地区都在空间风暴的笼罩之下，依托于特殊空间存在的守星塔，同时兼具着向人们传递信息的功能，在不稳定的空间影响下，这是唯一能够维持信号稳定的方法。

description:
失昼城共由$N$座岛屿组成，由$N-1$条传递信息的空间通道联通。

作为失昼城的守星使，月凌霜具有部署守星塔的能力，具体而言，为了依靠特殊空间波动向每个有居民居住的岛屿传递消息，月凌霜可以任意数量地部署守星塔，每座岛屿只能部署一座守星塔，**但是同一时刻所有部署的守星塔必须依靠空间通道连成一条链**。

失昼城常年受到空间风暴的困扰，常常会出现某座岛屿遭受空间风暴，岛上全体居民被迫离开岛屿，此时，**守星塔不再需要向该地传输消息**，等到空间风暴散去，居民重新回到这里，**守星塔才需要恢复向该地的信息传输**。

由于空间波动的干扰，守星塔传递消息必须依靠联通岛屿的空间通道完成，具体而言，如果一座守星塔要向一座岛屿传递消息，**其消耗的能量为该座守星塔所处的岛屿到需要接收消息的岛屿的所有空间通道能耗总和**，当然，如果一座守星塔向自身所处的岛屿发送消息，则不需要消耗能量，守星塔对岛屿传递消息的信号波动互相独立，也就是说，**每座守星塔对于每座岛屿的能量传输互不干扰**。

作为城主兼守星使，月凌霜近期正在研究怎样部署守星塔才能使消息传递所消耗的能量最小，现在月凌霜已经找到了记载失昼城七千多年来空间风暴的爆发情况和当时失昼城的守星塔部署的资料，由于历史过于久远，每次能量的消耗情况已经不得而知，现在月凌霜希望你帮助她还原这些史料，具体详见输入格式。

inputFormat:
第一行三个数$N,Q,Type$，表示失昼城岛屿数量，月凌霜的询问个数以及该数据点的特殊性质，$Type$在二进制下，若第$i-1$位为$1$，则表示存在特殊性质$i$。

接下来$N-1$行，每行三个数$u_{i},v_{i},w_{i}$表示岛屿$u$和岛屿$v$之间存在一条双向空间通道，消息经过这条空间通道需要消耗能量为$w_i$。

接下来一行$N$个数，由$0,1$两个数字构成，表示第$i$个岛屿在失昼城建城之时是否存在空间风暴，$0$表示存在空间风暴，$1$表示不存在，同时我们认为，**如果一个岛屿不存在空间风暴，那么它一定会吸引人们聚居，若存在空间风暴，则不会有人们在该岛屿居住**。

最后$Q$行，每行表示一个事件，具体如下：

$1$  $x$：对于岛屿$x$，若原本该岛屿没有空间风暴，则空间风暴产生，岛上全体居民撤出该岛，否则表示该岛屿空间风暴散去，人们重新回到这里居住。

$2$  $x$  $y$：月凌霜向你提出一个询问，询问若此时部署守星塔在$x$到$y$的简单路径上，则向**所有有居民的岛屿**传递一次消息所需要的能量消耗之和**最小**为多少。一座守星塔可以同时向多座岛屿传递消息，也可以不向任何岛屿传递消息。

outputFormat: 输出$Q$行，每行一个数，表示该次询问的答案。

hint:
![](https://cdn.luogu.com.cn/upload/pic/74843.png)

特殊性质$1$：$v_{i}=u_{i}+1$

特殊性质$2$：月凌霜所有的询问的$x$和$y$相同。

特殊性质$3$：月凌霜所有的询问的$x=1$。

对于所有的$w_{i}$，保证$0$<=$w_{i}$<=$10^{5}$

对于$100\%$的数据，保证$n,m\leq 200000,0\leq Type\leq 7$.

样例1解释：

![](https://cdn.luogu.com.cn/upload/pic/74831.png)

初始图像如左图。

对于第一个询问如中图，有$2,3,5$有居民，所以$ans_2=ans_3=0,ans_5=7.$所以$ans=7$.

对于第二组询问如右图，$ans_2=2+3=5,ans_3=0,ans_5=7,$,因此$ans=7+5=12$.

样例2解释：

![](https://cdn.luogu.com.cn/upload/pic/74836.png)

初始图如左上。

询问$1$点如图右上，存在$1,2,3,6$有居民。
$ans_1=0,ans_2=3,ans_3=5,ans_6=8+2=10.$因此$ans=3+5+10=18$

1操作后所有有居民点如左下。

接下来的操作图为右下，同上有$ans_1=0,ans_2=3,ans_3=0,ans_5=9,ans_6=0$,所以$ans=3+9=12$.


title: [DBOI2019] 持矢

background:
```cpp
吾射不亦精乎？
——doby
```

description:
$doby$是一个弓箭手，他很喜欢拿箭。

这天，他来到一个射箭场，发现射箭场老板放好了$n$个靶子（从$1-n$标号），中间画了$n-1$条线，使得这$n$格靶子和$n-1$条线组成了一个**根为**$1$的树。每个靶子上都有分数。

他为了历练自己，选择了一个点（称为父点），然后对它子树（包括它）的每个靶子射一次，每个靶子射中概率为$50\%$。每次射完一个子树，他获得的总分为射中的所有靶子的分数之**积**。

现在他想知道，选择不同的点作为父点，他期望总分为多少？由于总分可能很大，你需要把结果对$19260817$（质数）取模。

inputFormat:
输入两个正整数，靶子总数$n$和询问次数$m$。

接下来一行，$n$个正整数，表示编号为$1-n$的靶子的分数。

接下来$n-1$行，每行两个数$u,v$，描述树的一条无向边。

接下来$m$行，每行一个正整数$x(1\leq x\leq n)$，表示询问以靶子$x$为父节点时，$doby$期望获得的总分。

outputFormat:
输出一行，一个正整数$out$。

为了减少输出，定义$out$为对于每组询问，期望获得的总分之和。由于是期望，需要你在计算$\frac{a}{b}$时，将其改为$a*b^{-1} mod (19260817)$。你需要把输出$out$也对$19260817$取模。

hint:
### 注意：由于模数较大，请注意求逆元时中间结果的溢出。

如果你不需要卡常，使用快速幂求逆元就够用了。

【样例#$1$说明】

答案为$\frac{5}{4}$，可能的总分有$0$，$1$，$2$。

【样例#$2$说明】

答案分别为$9630410$、$10834247$、$15047607$，即$\frac{3}{2}$、$\frac{599}{16}$、$\frac{2999}{32}$。

$Subtask$ #$1$（$10$分）：

$1\leq n,m\leq 10$。

$Subtask$ #$2$（$40$分）：

$1\leq n,m\leq 100000$。

$Subtask$ #$3$（$50$分）：

$1\leq n,m\leq 2000000$。

所有测试点的时间限制统一为$1.5s$，内存限制统一为$125M$。

### 题目提供者：$1jia1$


title: [NOIP1997 提高组] 棋盘问题 加强版

background:
[P1549](https://www.luogu.org/problem/P1549) 数据加强版。

**数据从 5 扩大到了 10。**

因为本题数据可能存在诸多争议，故特开一题用来测试加强版数据。

description:
在 $N \times N$（$1 \le N \le 10$）的棋盘上，填入 $1, 2, \dots, N ^ 2$ 共 $N ^ 2$ 个数，使得任意两个相邻的数之和为素数。

例如：当 $N = 2$ 时，有：

| $1$ | $2$ |
| :-----------: | :-----------: |
| $4$ | $3$ |

其相邻数的和为素数的有：

$1+2,1+4,4+3,2+3$

当 $N=4$ 时，一种可以填写的方案如下：

| $1$ | $2$ | $11$ | $12$ |
| :-----------: | :-----------: | :-----------: | :-----------: |
| $16$ | $15$ | $8$ | $5$ |
| $13$ | $4$ | $9$ | $14$ |
| $6$ | $7$ | $10$ | $3$ |

在这里我们约定：左上角的格子里必须填数字 $1$。

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

outputFormat: 如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出 `NO`。

hint:
$N\leq10$

 $N=1,2,...,10$ 的数据都各有一个点，由于某些原因， $N$ 不一定与测试点编号相等。

----

**数据新修复于 `2020.1.20`**


title: 游走

background: zbw 在 B 城游走。

description:
B 城可以看作一个有 $n$ 个点 $m$ 条边的**有向无环图**。**可能存在重边**。

zbw 在 B 城随机游走，他会在所有路径中随机选择一条路径，选择所有路径的概率相等。路径的起点和终点可以相同。

定义一条路径的长度为经过的边数，你需要求出 zbw 走的路径长度的期望，答案对 $998244353$ 取模。

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

接下来 $m$ 行，每行两个整数 $x,y$，表示存在一条从 $x$ 到 $y$ 的有向边。

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


title: 区间加区间 sin 和

description:
给出一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$，进行 $m$ 次操作，操作分为两类。

操作 $1$：给出 $l,r,v$，将 $a_l,a_{l+1},\ldots,a_r$ 分别加上 $v$。

操作 $2$：给出 $l,r$，询问 $\sum\limits_{i=l}^{r}\sin(a_i)$。

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

接下来一行 $n$ 个整数表示 $a_1,a_2,\ldots,a_n$。

接下来一行一个整数 $m$。

接下来 $m$ 行，每行表示一个操作，操作 $1$ 表示为 `1 l r v`，操作 $2$ 表示为 `2 l r`。

outputFormat:
对每个操作 $2$，输出一行，表示答案，四舍五入保留一位小数。

保证答案的绝对值大于 $0.1$，且答案的准确值的小数点后第二位不是 $4$ 或 $5$。

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

保证 $1\leq n,m,a_i,v\leq 2\times 10^5$，$1\leq l\leq r\leq n$。保证所有输入的数都是正整数。


title: [Ynoi2012] WC2016 充满了失望

description:
在平面直角坐标系中，

给 $n$ 个点，这 $n$ 个点是可达的，如果点 $A,B$ 可达则线段 $AB$ 上的点均可达。

给 $m$ 个圆，问有哪些圆满足圆内任意点都是可达的。

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

接下来 $T$ 组数据，每组数据中：

第一行一个整数 $n$，

接下来 $n$ 行每行两个整数 $x_i,y_i$，表示点，

接下来一行一个整数 $m$，

接下来 $m$ 行每行三个整数 $X_i,Y_i,R_i$，表示圆。

outputFormat: 每组数据输出一行，一个长度 $m$ 的 `01` 串，表示答案（`0` 表示圆内存在不可达的点，`1` 表示圆内所有点可达）

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

样例解释：

红色的点为样例中给出的点，橙色的圆表示答案为 `1` 的询问，蓝色的圆表示答案为 `0` 的询问。

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

$1\leq n,m\leq 5\times 10^5$，$1\leq R_i\leq 10^6$，$-10^6\leq x_i,y_i,X_i,Y_i\leq 10^6$，$\sum n\leq 5\times 10^5$，$\sum
 m\leq 5\times 10^5$。

保证当 $R_i$ 变化不超过 $1$ 时，答案不发生变化。


title: [Ynoi2012] 惊惶的 SCOI2016

description: 给你一棵 $n$ 个节点的树，每个点有个颜色，有 $m$ 次修改，每次修改需要输出树上所有有向简单路径的颜色数的和。

inputFormat:
第一行，输入两个整数 $n$ 和 $m$。

第二行，输入 $n$ 个整数 $c_1,c_2,\ldots,c_n$（$1\leq c_i\leq n$）。其中 $c_i$ 为 $i$ 节点的初始颜色。

接下来 $n-1$ 行每行包括两个整数 $u,v$（$1\leq u,v\leq n$），这表示 $u$ 与 $v$ 之间有一条边。

接着 $m$ 行每行包括两个整数 $u,x$（$1\leq u,x\leq n$）表示将节点 $u$ 的颜色修改为 $x$。

outputFormat: 输出 $m+1$ 行，每行一个整数，为初始这个树上所有路径颜色数的和，以及每次修改后的这个值。

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

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


title: [CEOI2013] Board

description:
给出这样一棵“二叉树”:
 - 每个节点有左右两个儿子，并如下定义每个节点的高度：假设父亲节点的高度为 $h$，那么他的两个儿子的节点的高度都是 $h+1$，相同高度的所有节点称作一层。

 - 每个节点的左儿子的子树都在右儿子的子树的左边，每一层相邻的两个节点之间有一条边。 下面是一个例子：

![](https://cdn.luogu.com.cn/upload/pic/74384.png)

每一条图上的路径用一个字符串表示，字符串中的每一个字符表示一 个移动。字符仅包含如下五种：

 - $\tt 1$：表示移动到当前节点的左儿子
 - $\tt 2$：表示移动到当前节点的右儿子
 - $\tt U$：表示移动到当前节点的父亲节点
 - $\tt L$：表示移动到当前节点同层的左边的节点（保证当前节点在这一层中不是最左边的节点）
 - $\tt R$：表示移动到当前节点同层的右边的节点（保证当前节点在这一层中不是最右边的节点）

 用一条路径来表示这条路径的终点，例如路径：$\tt  221LU$ 就表示上图中的节点 $A$。 给出两条路径，你的任务是求出着两条路径的终点之间的最短路。

inputFormat: 输入两行，每行一个字符串，分别表示两条路径。

outputFormat: 输出一行，表示两个节点之间的最短路。

hint:
用 $D$ 表示所有经过的节点中，深度最大的节点的深度；$S$ 表示输入字符串的最大长度。

- 对于 $10\%$ 的数据，$D \leq 10$;
- 对于 $30\%$ 的数据，$D \leq 50$;
- 对于 $50\%$ 的数据，$D \leq 10^3$;
- 对于 $70\%$ 的数据，$D\leq 2 \times 10^4$;
- 对于 $100\%$ 的数据，$D \leq 10^5, S \leq 10^5$。


title: 「SWTR-1」Ethan and Sets

description:
$\mathrm{Ethan}$ 有 $n$ 个数字集合，每个集合有如下属性：

编号：第 $i$ 个集合编号为 $i$。

大小：第 $i$ 个集合大小为 $num_i$。

魔力：第 $i$ 个集合魔力为 $t_i$。

数字：第 $i$ 个集合中含有数字 $c_{i,1},c_{i,2},\dots,c_{i,num_i}$。

在 $\mathrm{Ethan}$ 的世界中，一共只有 $m+1$ 个数：$0$ 到 $m$。

$\mathrm{Ethan}$ 对数字有奇特的感情，在这 $m+1$ 个数中，有 $d$ 个数是他喜欢的，分别是 $p_1,p_2,\dots,p_d$ ，剩下 $m-d+1$ 个是他不喜欢的。

现在 $\mathrm{Ethan}$ 要删除一些集合，准确来说，他要选择一段区间 $[L,R]$，**删除所有编号在这个区间以外的集合**。

- 他想要使得在剩余的集合中，包含**所有**他喜欢的数。

- 并且在剩余的集合中，他**不喜欢的数的个数尽可能小**（注：这里的个数是指出现的次数，即如果 $1$ 是 $\mathrm{Ethan}$ 不喜欢的数，并且剩余的集合中出现了 $3$ 个 $1$，那么算 $3$ 个不喜欢的数）。

- 如果有多个满足条件的区间，他想要使得剩余集合的**魔力之和尽可能大**。

求出满足要求的 $[L,R]$，如果无解输出 $-1$，如果有多解，输出任意一解。

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

第二行 $d$ 个整数 $p_1,p_2,\dots,p_d$。

第三行至第 $n+2$ 行：每行先是两个整数 $t_i,num_i$，随后 $num_i$ 个整数 $c_{i,1},c_{i,2},\dots,c_{i,num_i}$。

outputFormat: 一行，如果无解输出 $-1$，否则输出两个整数 $L,R$。

hint:
---

### 样例解释：

在样例 $1$ 中，$\mathrm{Ethan}$  可以选择 $[2,4]$，这样在剩余的集合中包含了所有他喜欢的数，且只有 $2$ 个他不喜欢的数在这些集合中出现。

在样例 $2$ 中，不存在合法的解。

---

### 数据范围：

本题使用 subtask。

subtask 1，$1 \leq n,m \leq 100$，$20\%$。

subtask 2，$1 \leq n,m \leq 500$，$30\%$。

subtask 3，$1 \leq n \leq 3000, 1 \leq m \leq 1000, 1 \leq t_i \leq 10^9$，$50\%$。


title: 「SWTR-2」Picking Gifts

background:
$\mathrm{Sunny}$ 有个 $npy$ 叫做小 $\mathrm{b}$。

小 $\mathrm{b}$ 的生日就要到了，$\mathrm{Sunny}$ 想给她买一些礼物。

description:
商店里摆着琳琅满目的商品，每个商品都有：

- 编号，**从左到右**依次为 $1,2,\dots n$。

- 种类，分别为 $p_1,p_2,\dots p_n$。

- 价值，分别为 $v_1,v_2,\dots v_n$。

$\mathrm{Sunny}$ 想从中挑选一个区间，将这个区间里的所有礼物买下来送给小 $\mathrm{b}$。

小 $\mathrm{b}$ 会**从右往左**依次查看 $\mathrm{Sunny}$ 送给他的礼物，如果她看到同一种类的礼物出现了 $k$ 次，那么她就不会再去查看这种礼物（包括第 $k$ 个），当然，这些礼物也就失去了原本的价值。

现在，$\mathrm{Sunny}$ 给你了 $m$ 个区间，想让你求出在小 $\mathrm{b}$ 眼中，这个区间的价值。

具体的价值计算见样例。

inputFormat:
第一行由空格隔开的三个正整数 $n,m,k$。

第二行 $n$ 个由空格隔开的正整数，第 $i$ 个数代表 $p_i$。

第三行 $n$ 个由空格隔开的正整数，第 $i$ 个数代表 $v_i$。

接下来 $m$ 行，第 $i$ 行两个正整数 $l_i,r_i$，表示第 $i$ 次询问的区间。

outputFormat: 输出 $m$ 行，对于每一个询问，输出一行一个整数 $v$，为这个区间在小 $\mathrm{b}$ 眼中的价值。


title: [清华集训2015] 灯泡

background: $2022$ 年，评测数据发生了翻天覆地的变化，请 $2022$ 年前通过此题的人重新交一遍。

description:
相比 Wildleopard 的家，他的弟弟 Mildleopard 比较穷。他的房子是狭窄的，而且在他的房间里仅有一个灯泡。每天晚上，他徘徊在自己狭小的房子里，思考如何赚更多的钱。有一天，他发现他的影子的长度随着他在灯泡和墙壁之间走动时会发生变化。一个突然的想法出现在他的脑海里，他想知道在房间里他的影子的最大长度。

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

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

对于每组测试数据仅有一行包含三个实数 $H,h$ 和 $D$，$H$ 表示灯泡的高度，$h$ 表示 Mildleopard 的身高，$D$ 表示灯泡和墙的水平距离。

outputFormat: 输出文件共 $T$ 行，每组数据占一行，表示影子的最大长度 $L$。当你的输出与标准输出的绝对误差不超过 $10^{-3}$ 即视作通过。


title: [Celeste-B] Golden Feather

background:
> 就是这样，Madeline。

> 保持呼吸。你能行。

description:
“你的呼吸让那片羽毛一直飘着。”

“平稳缓慢地呼吸，吸气，吐气。”

“看吧，每次都是这么轻松。”

随着 Madeline 的呼吸，羽毛上下移动着。

通过 Madeline 的观察，她还发现，羽毛似乎遵循这一种神奇的运动轨迹。

在每一轮呼吸中，羽毛会在特定的地方停止，这些地方都是有魔力的，具体来说，第 $i$ 个停留处的魔力是 $(i+1)^2-1$。

并且，在一轮呼吸停止时，羽毛会渗透出一些能量，只要能用这些能量沟通这些停止的地方，Madeline 就能运用羽毛的力量飞翔。更具体的，由于同性相斥，两个地方魔力的相似程度越高就越难被沟通，沟通两个地方所需要的能量为这两个地方魔力的 $gcd$。

在一轮一轮的呼吸中，Madeline 已经无暇算出最少需要的能量，由于羽毛渗透出的能量不多，你能帮帮她算出最少需要多少能量来沟通这些羽毛停止的地方吗？

inputFormat:
第一行一个正整数 $T$，表示呼吸轮数。

接下来 $T$ 行一行一个正整数 $n$，表示该轮呼吸中羽毛停止的地方个数。

outputFormat: 输出 $T$ 行，一行一个整数，最少需要的能量。

hint:
n=3 的样例解释如下图

![T1_2.png](https://i.loli.net/2019/09/14/PtflkNCE8b3iKzB.png)
![T1.png](https://i.loli.net/2019/09/14/AIYlMZgonL7thfu.png)

对于 $5\%$ 的数据，$n \leq 3$

对于 $10\%$ 的数据，$n \leq 1000$

对于 $50\%$ 的数据，$n \leq 10^6$,$T \leq 10$

对于 $100\%$ 的数据，$n \leq 10^{18}$,$T \leq 100$


title: [Celeste-B] Mirror Magic

background:
> ...

> 呼吸。

> 你能站起来，Madeline

> 想想羽毛。你能拯救 Theo

description:
镜之神庙是一座有魔力的神庙，在这里你能一窥自己心灵的真相。

Theo 被困在了一面镜子里。当 Madeline 尝试去拯救 Theo 时，神庙里的"生物"们给她出了一道难题，这道难题是这样的：

神庙的"生物"们准备了 $n$ 串草莓，这些草莓的长度之和 $<= 10^6$，现在它们可以执行这样一些操作：

$1\ x\ l\ r$，表示将编号 $x$ 的草莓串的子草莓串 $[l,r]$ 复制一份，插入当前的草莓集合中，保证草莓串 $x$ 的长度 $>=r$。

$2\ k$，表示删除第 $k$ 次操作插入的草莓串，保证第 $k$ 次操作为插入并且此时第 $k$ 次操作插入的草莓串在集合中。

"生物"们认为和谐的味道才是美味的。在执行任意一次操作之后，"生物"们想要知道当前集合中所有草莓串的美味度(即 $LCP$ - 最长公共前缀)。（若集合为空，则美味度 $0$，若集合中只有一个草莓串，则美味度为草莓串的长度）

为了方便表达，我们把每一种草莓表示为一个**小写英文字母**。

多年以后，Madeline 又来到了镜之神庙，想要回忆多年前自己的登山旅途，可是她已经不记得自己当年是怎么解决那道谜题的了，你能帮帮她找到谜题的答案吗？

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

接下来 $n$ 行一行一个**只包含小写字母**的字符串，表示原来的 $n$ 个草莓串。

接下来一行一个正整数 $q$，表示操作个数。

接下来 $q$ 行一行一个操作。

outputFormat: 输出 $q$ 行，对应每次操作之后集合中草莓串的美味度($LCP$ - 最长公共前缀).

samples:
3
abccccd
abccddc
acbbcad
5
1 1 1 7
1 2 1 7
1 3 1 7
2 3
2 2

hint:
样例解释：

第一次操作后，集合为 $\{"abccccd"\}$,$LCP=7$

第二次操作后，集合为 $\{"abccccd","abccddc"\}$,$LCP=4$

第三次操作后，集合为 $\{"abccccd","abccddc","acbbcad"\}$,$LCP=1$

第四次删除了第三次插入的串，故 $LCP=4$

第五次删除了第二次插入的串，故 $LCP=7$

令 $len$ 等于 $n$ 个串的长度之和。总有 $len \leq 10^6$

Subtask $1$($10$ Pts), $n \leq 5, q = 10$

Subtask $2$($30$ Pts), $n \leq 10^6, q = 10^6$, 保证每次插入的是串的一个前缀

Subtask $3$($10$ Pts), $n \leq 10^6, q = 10^5$, 不含 $2$ 操作, **保证询问为随机生成**

Subtask $4$($50$ Pts), $n \leq 10^6, q = 10^6$

提示：你可以根据 $q$ 判断 Subtask 编号


title: [Celeste-B] Center of the Earth

background:
> 我曾如此地接近。

> 我**恨**她。

>

> ...

> 我这次一定要坚持到底。

> 不能再逃跑了。

description:
Madeline 来到了一座神龛前，这座神龛布满尘埃，四周还都是不明所以的符号。

通过 Madeline 强大的观察能力，她发现这些符号其实对应着一个个冲刺顺序，按照一定顺序冲刺就相当于输入一个密码，只有输入特定的密码才能点亮神龛获得水晶之心。

多年之后，当 Madeline 回忆她的登山之旅时，她已经不记得密码是什么了，只记得密码长度为 $3$，并且每一位密码有 $n$ 种可能。她还知道，在她输入的密码中，任意两位与标准密码相符就能点亮神龛获得水晶之心。

今天，Madeline 又回到了这座神龛前，她希望使用最少的输入密码次数来保证能获得这颗水晶之心，你能帮帮她吗？

inputFormat: 第一行一个整数 $n$，表示每一位密码有多少种可能。

outputFormat:
第一行输出一个整数 $k$，表示你给出的方案中输入密码的次数。

接下来 $k$ 行，输出每次尝试的密码。

hint:
样例不是最优解，只是对输出的一个示例。

**请务必输出方案，否则可能会遇到未知错误**

共有三个测试点：

测试点 $1$($10$pts) : $n=2$

测试点 $2$($20$pts) : $n=100$

测试点 $3$($70$pts) : $n=1000$

对于每组数据我们采取如下评分方式：

- 若 $k > 5000000$ ，你的输出过大，你将无法得到任何分数。

- 否则：

  - 若给出的方案无法保证能点亮神龛，或者方案本身是错误的，则按照如下规则评分：

    - 若 $k$ 小于最小次数，不给分。

    - 否则，若 $k$ 等于最小次数，则给出该测试点 $10\%$ 的分数。

    - 否则，若你的 $k$ 是最小次数的 $q$ 倍，你将得到这个测试点 $\frac{1}{10*q}$ 的分数。

  - 否则，你的方案可以保证点亮神龛，则按照如下规则评分：

    - 首先得到 $10\%$ 的基础分。

    - 接着，令最小次数为 $p$，你将得到如下额外分数：

      - $k=p$，你将得到 $90\%$ 的额外分数。

      - $p<k<=1.5p$，你将得到 $50+\frac{1.5p-k}{0.5p}*40\%$ 的额外分数。

      - $1.5p<k<=2p$，你将得到 $20+\frac{2p-k}{0.5p}*30\%$ 的额外分数。

      - $k>2p$，你将不会得到额外分数。


title: [Celeste-B] No More Running

background:
> 逃离自己内心的人，

> 永远也到达不了顶峰。

> 想要到达山顶，你能做的只有

> 不再逃避

description:
通往山顶的路上水晶遍布。

在晶簇中，Madeline 发现了一个不同寻常的水晶洞穴，洞穴中镶嵌着五彩斑斓的宝石。

经过 Madeline 的观察，她发现这些宝石形成了一个奇妙的机关，只要让宝石收集到足够的魔力，就能打开机关，拿到水晶之心。

具体来说，在这个巨大的洞穴里有着 $n$ 颗宝石，每颗宝石都被镶嵌在**形态结构完全相同**但**相互独立**的树形结构里。更具体地，在这个洞穴里有 $n$ 个相同的树形结构 $T$，树形结构 $T$ 有 $n$ 个节点，而第 $i$ 颗宝石被镶嵌到了第 $i$ 个树形结构 $T$ 的第 $i$ 号节点上。

Madeline 能够推动宝石从而让宝石在树形结构上滑动。当宝石滑过树形结构的一条边**过后**，这条边就会被关闭，并且边上储存的魔力就会被积蓄到宝石中。(再次提醒，这 $n$ 颗宝石所在的树形结构是相互独立的，这意味着在一个树形结构中一条边的封闭并不会导致在其他树形结构中这条边也被封闭)

宝石能储存的魔力是有上限的，更具体而言，每颗宝石都只能储存 $mod$ 的魔力，一旦超过这个魔力上界，宝石的魔力就会溢出，你可以认为宝石此时储存的魔力会对 $mod$ 取模。

Madeline 想要知道，镶嵌在每个顶点上的宝石最终最多能储存多少魔力，你能帮帮她吗？

inputFormat:
第一行为两个整数 $n$，$mod$，表示树形结构的节点数和 $mod$

接下来 $n-1$ 行一行三个整数 $u,v,w$，描述树形结构中一条连接 $u,v$，能量值为 $w$ 的双向边 ($0 \leq w < mod$ )。(注意，封闭一条边是双向的，这意味着你不能走回头路)

保证这些边构成了一棵树。

outputFormat: $n$ 行 $n$ 个整数，第 $i$ 个表示镶嵌在第 $i$ 个顶点的宝石最多能储存的魔力。

hint:
![图挂了](https://i.loli.net/2019/08/30/sPwyQKUDANRCT2f.png)

"特殊约定" 中，"一条链"意味着树形结构的第 $i$ 条边连接第 $i$ 个和第 $i+1$ 个节点。

对于所有数据有 $0\leq w<mod$

保证输入的所有边构成一棵树

对于 $1$~$6$ 号测试点，时限为 $1s$

对于 $7$~$12$ 号测试点，时限为 $2s$

对于 $13$~$20$ 号测试点，时限为 $3s$


title: [Celeste-B] Say Goodbye

background:
> 你们居然挺过来了，真是令人难以置信，不是吗？

> 努力的过程还是挺有意思的。

> 这个嘛，

> 你又在等什么？

description:
Madeline 将收集到的草莓分给了朋友们

火红色的草莓和金黄色的草莓交错在一起，很受朋友们喜爱

朋友们为了感谢 Madeline ，一起收集了许多五颜六色的珠子，打算串成一条花花绿绿的项链送给 Madeline

经过朋友们的精心准备，现在桌子上摆着$n$个珠子，这些珠子一共有$k$种颜色。具体来说，第$i$种颜色的珠子有$a_i$个

看着桌子上晶莹剔透的珠子，现在朋友们却犯难了，因为他们不知道怎样将它们串在一起才最美丽

朋友们向你发出了请求，需要你帮忙求出本质不同的方案总数

朋友们分不清这些珠子的顺序，因此**两个珠子不同仅当它们的颜色不同**

这条项链必须是完整的，因此**所有珠子构成了一个连通块**

这条项链还不能太杂乱，因此所有珠子必须构成一棵**基环树**

在多次询问 Madeline 的朋友们之后，你发现这棵基环树的两个子树不同仅当**它们对应点的颜色不同或者这两棵子树不同构**。对于不同的子树是有先后顺序之分的

举例来说，下面的几种**部分**串法是互不相同的

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

朋友们的时间很紧迫，因此如果两种项链能够通过**旋转基环**得到同样的结果，那么这两种项链本质上是相同的

inputFormat:
第一行两个整数 $ n, k $，分别表示珠子的总数以及颜色种数

接下来一行 $k$ 个整数 $a_i$，表示每种颜色的珠子个数

outputFormat: 输出一个整数，表示方案数模 $998244353$ 的余数

hint:
基环树：一个有$n$个点$n$条边的联通图，**没有自环**。容易看出这样的图是一个环上连出了一些树

基环：基环树中的环

对于 $ 5\% $ 的数据，$ n \leq 8 $

对于另 $ 10\% $ 的数据，$ k = 1 , n \leq 10^3 $

对于前 $ 30\% $ 的数据，$ n \leq 10^3 $

对于另 $ 20\% $ 的数据，$ k = 1 , n \leq 5 \times 10^4 $

对于前 $ 80\% $ 的数据，$ n \leq 5 \times 10^4 $

对于 $ 100\% $ 的数据，$ a_i > 0 , \sum a_i = n , n \leq 2 \times 10^5 , k \leq n $

第二个样例解释：

有如下$15$种情况：

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


title: [Celeste-B] Farewell to Mount Celeste

background:
> Sever the Skyline

> Black Moonrise

> Good Karma

> Golden Feather

> Mirror Magic

> Center of the Earth

> No More Running

> And...

> Say Goodbye.

description:
在分别的宴会上，朋友们拿出他们把多彩的珠子串成的彩色的项链。

项链在夕阳的余晖里闪闪发光，仔细一看，项链周围竟然已经聚集了许多鸟儿，鸟儿们带着 Madeline 与她的朋友们来到了一处他们不曾来过的地方，这里汇聚着好大一群鸟，似乎想要向他们表达些什么。

经过 Madeline 仔细地观察，它发现一些鸟儿们飞动的方式好像排成了一个有序的式子，而另一些鸟儿飞动的方式则是一些符号，符号表达着一个问题。

鸟儿们表达的问题是这样的：

鸟儿们组成的式子会由 `(`,`)`,`^`,`&`,`|`,`0`,`1` 和小写字母构成，并且是一个表达式。

其中：

- `(`,`)` 表示括号，在括号中的运算优先级提高。

- `&`,`|`,`^` 表示 `与`,`或`,`异或` 三种位运算，这三种运算**优先级相同**

- `0`,`1` 即为 `0`,`1`

- 小写字母表示变量，多次出现的同一小写字母表示**不同**的变量，一个变量取值 `0` 或 `1`

- 表达式的定义如下：

    - 一个变量,`0`,`1` 均为表达式
    - 若 $T$ 是表达式，则 $(T)$ 是表达式
    - 若 $S$,$T$ 是表达式，则$S\&T$,$S|T$,$S\ \hat{}\ T$均为表达式
    - 例如，$(1\ \hat{}\ 1\&0)$ 是一个表达式，并且运算结果为 $0$，但 $(1\&0$ 不是一个表达式

鸟儿们认为，要能算出 $1$ 的表达式才是优美的，定义一个表达式的优美度为在这个表达式所有 $v$ 个变量的 $2^v$ 种取值中能算出 $1$ 的方案数。

鸟儿们还认为，一个表达式的和谐度是这个表达式的所有**子连续表达式**的优美度的和。(包含自身)

鸟儿们还是善变的，它们会时不时改变一个位置的字符，但是它们向 Madeline 和她的朋友们保证它们不会改变括号，并且进行修改之后整个串仍然是一个表达式。

你能帮助 Madeline 和她的朋友们算出每次修改后整个表达式的和谐度吗？

鸟儿们还说，因为表达式可能太和谐了，因此 Madeline 可以只回答和谐度对 $998244353$ 取模后的值。

inputFormat:
第一行为一个数 $m$ ,表示修改数

第二行为一个字符串，表示初始表达式

之后 $m$ 行，每一行一个数 $a$ 和一个字符 $b$ ，表示鸟儿们将 $a$ 位置字符变成 $b$

在输入的表达式中，一个小写字母代表一个变量。(注意一个字母可能出现多次，但代表**不同**变量)

outputFormat: $m$ 行，第 $i$ 行为第 $i$ 次修改后的权值。由于和谐度可能很大，你需要对 $998244353$ 取模。

hint:
设 $n$ 为表达式中变量和 $0,1$ 的个数，$len$ 为表达式长度

有subtask

对于 $ 5\% $ 的数据, $ n \leq 12 , len \leq 50 , m \leq 50 $,1s

对于额外 $ 10\% $ 的数据, $ n \leq 150,len \leq 400,m \leq 200$

对于额外 $ 10\% $ 的数据, $ n \leq 10^5,len \leq 2\times 10^5,m \leq 10$ ,没有括号

对于额外 $ 10\% $ 的数据, $ n \leq 10^5,len \leq 2\times 10^5,m \leq 10^5 $ ,没有括号

对于前 $ 50\% $ 的数据, $ n \leq 10^5,len \leq 4\times 10^5,m \leq 10^5 $ ,保证括号随机生成

对于 $ 100\% $ 的数据, $ n \leq 10^5,len \leq 4\times 10^5,m \leq 10^5 ,len-2\times n \leq 2 \times 10^5$

对于后 $ 95\% $ 的数据，时限为3s


title: 异位坍缩

background:
>自然的法则隐藏在黑暗之中。

月光之下，菲欧娜和一群与她有着同样信仰的信徒们聚集在一起，等待着他们所信仰的神明降临。

「神明大人，我们愿意永远追随您。」

description:
神明想要测试他的信徒们是否忠诚，他决定用运气来进行测试。

神明事先准备了 $n$ 个问题，每个问题都有两种选择：**「相对激进的」** 和 **「相对保守的」**。神明已经定好了自己的选择。

为了考验他的信徒们，神明会在所有可行的问题选择方式中**等概率选出一种**（可行的选择方式指选出**连续的** $k$ 个问题，满足 $l\leq k\leq r$，其中 $l,r$ 给定），然后信徒们会依次对这 $k$ 个问题中的每个问题回答「相对激进的」或「相对保守的」。神明会根据自己的选择以及某个信徒的回答来判定这名信徒是否忠诚。

神明的判定方式是这样的：

+ 这是第一个问题：无论回答如何，神明都愿意相信这名信徒是忠诚的。
+ 这不是第一个问题：如果这名信徒的上一个回答与神明的选择相同，那么神明会需要他去对更先进的选择进行探索，因此这名信徒在这个问题的回答**不能比神明的选择更保守**；否则，神明会要求这名信徒服从于自己，在这个问题的回答**不能比神明的选择更激进**。

如果这名信徒的回答满足上述要求，那么这名信徒就是忠诚的。

现在，神明想要知道，如果信徒对每个问题都会**等概率回答「相对激进的」或「相对保守的」**，那么一名信徒有多大的概率会是忠诚的。他通过菲欧娜向你提出了这个问题，并要求你将结果对 $998244353$ 取模。如果你无法及时回答出，那么你就会失去神明的信任。

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

#### 简要题意：

给定一个长度为 $n$ 的 01 串 $a$ 以及 $l,r(l\leq r)$。

对于两个长度均为 $k$ 的 01 串 $p,q$，我们认为 $q$ 对于 $p$ 是「忠诚的」，当且仅当 $p$ 和 $q$ 满足如下要求：

+ 对于任意 $1<i\leq k$，如果 $q_{i-1}=p_{i-1}$，那么 $q_i\geq p_i$，否则 $q_i\leq p_i$。

你需要求出如果**先等概率随机选出一个长度 $k$ 满足 $l\leq k\leq r$ 的 $a$ 的子串**，然后**再等概率随机出一个长度为 $k$ 的 01 串 $b$**，有多大的概率使得 $b$ 对于这个子串是「忠诚的」，结果对 $998244353$ 取模。

inputFormat:
第一行三个整数 $n,l,r$，意义如上。

第二行有一个长度为 $n$ 的字符串，表示 $a$。保证字符串只含字符 `0` 和 `1`。

outputFormat: 一行一个整数，表示结果。

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

我们用 $\left[l,r\right]$ 表示所选择的子串所在区间。

+ 选择 $\left[1,2\right]$，子串为 `01`，长度为 $2$，有 $3$ 个 01 串对这个子串是「忠诚的」，概率为 $\dfrac{3}{4}$。
+ 选择 $\left[1,3\right]$，子串为 `011`，长度为 $3$，有 $4$ 个 01 串对这个子串是「忠诚的」，概率为 $\dfrac{1}{2}$。
+ 选择 $\left[2,3\right]$，概率为 $\dfrac{3}{4}$。

+ 选择 $\left[2,4\right]$，概率为 $\dfrac{5}{8}$。
+ 选择 $\left[3,4\right]$，概率为 $\dfrac{3}{4}$。
+ 选择 $\left[3,5\right]$，概率为 $\dfrac{1}{2}$。
+ 选择 $\left[4,5\right]$，概率为 $\dfrac{3}{4}$。

结果为 $\dfrac{\dfrac{3}{4}+\dfrac{1}{2}+\dfrac{3}{4}+\dfrac{5}{8}+\dfrac{3}{4}+\dfrac{1}{2}+\dfrac{3}{4}}{7}=\dfrac{37}{56}$，取模意义下为 $338690049$。

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

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

+ Subtask 1 ( $1\%$ )：$n=1$。
+ Subtask 2 ( $13\%$ )：$n\leq100$。
+ Subtask 3 ( $3\%$ )：保证 $\forall1\leq i\leq n,a_i=0$。
+ Subtask 4 ( $3\%$ )：保证 $\forall1\leq i\leq n,a_i=1$。
+ Subtask 5 ( $20\%$ )：$n\leq10^3$。
+ Subtask 6 ( $15\%$ )：$l=r$。
+ Subtask 7 ( $20\%$ )：$n\leq 5\times 10^5$。
+ Subtask 8 ( $25\%$ )：无特殊限制。

对于所有数据，$1\leq n\leq5\times 10^6,1\leq l\leq r\leq n$。


title: [Ynoi2012] NOIP2016 人生巅峰

description:
给一个长为 $n$ 的序列 $a_1,a_2,\ldots,a_n$，每个数在 $0$ 到 $v - 1$ 之间，有 $m$ 次操作。

操作 $1$：每次询问一个区间中是否可以选出两个下标的非空集合 $X,Y$，满足：

1. $X$ 和 $Y$ 没有交集。
2. 设集合 $X$ 中有一个元素是 $i$，则其对集合 $X$ 的贡献是 $a_i + 1$，要求集合 $X$ 的元素的总贡献和集合 $Y$ 的元素的总贡献相等。如果可以选出这两个集合，输出 `Yuno` 否则输出 `Yuki`。

操作 $2$：修改一个区间 $l,r$ 之间的数，使得所有 $l\leq i\leq r$，$a_i = a_i^3 \bmod v$，即区间立方。

inputFormat:
第一行三个整数 $n , m , v$，意义如题所述。

之后一行 $n$ 个整数，表示序列 $a$。

之后 $m$ 行每行三个数 $opt , l , r$，表示操作类型是 $1$ 还是 $2$，操作的区间是 $[l , r]$。

outputFormat: 对每个询问输出一行一个字符串 `Yuno` 或者 `Yuki` 表示能否选出这两个集合。

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

对于 $100\%$ 的数据，$1\leq n , m\leq 10^5$，$1\leq v\leq 1000$，数据没有梯度。


title: [Ynoi2077] stdmxeypz

description:
给你一棵边权为 $1$，且以 $1$ 为根的有根树，每个点有初始为 $0$ 的点权值，定义两个点的距离为其在树上构成的简单路径的长度，需要支持两种操作：

`1 a x y z`：把 $a$ 子树中所有与 $a$ 的距离模 $x$ 等于 $y$ 的节点权值加 $z$。

`2 a`：查询 $a$ 节点的权值。

inputFormat:
第一行两个整数 $n,m$ 表示树的节点数为 $n$，有 $m$ 次操作。

第二行 $n-1$ 个整数，第 $i$ 个数 $f_i$ 表示树上第 $i+1$ 个节点的父亲节点。

之后 $m$ 行，每行形如 `1 a x y z` 或 `2 a`，表示上述的操作。

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

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

对于 $100\%$ 的数据，满足 $1\leq n , m\leq 3\times 10^5$，$1\leq f_i\leq i$，$1\leq a\leq n$，$1\leq x\leq n$，$0\leq y < x$，$0 \leq z < 514$。


title: 『MdOI R1』Treequery

description:
给定一棵 $n$ 个点的无根树，边有边权。

令 $E(x,y)$ 表示树上 $x,y$ 之间的简单路径上的所有边的集合，特别地，当 $x=y$ 时，$E(x,y) = \varnothing$。

你需要 **实时** 回答 $q$ 个询问，每个询问给定 $p,l,r$，请你求出集合 $\bigcap_{i=l}^r E(p,i)$ 中所有边的边权和，即 $E(p, l\dots r)$ 的交所包含的边的边权和。

通俗的讲，你需要求出 $p$ 到 $[l,r]$ 内每一个点的简单路径的公共部分长度。

inputFormat:
第一行两个整数 $n,q$，表示树的结点数和询问数。

接下来 $n-1$ 行，每行三个整数 $x,y,w$，表示 $x$ 与 $y$ 之间有一条权值为 $w$ 的边。

接下来 $q$ 行，每行三个整数 $p_0,l_0,r_0$。第 $i$ 个询问的 $p,l,r$ 分别为 $p_0,l_0,r_0$ 异或上 $lastans$ 的值，其中 $lastans$ 是上次询问的答案，初始时为 $0$。

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


title: [CCO2019] Human Error

description:
Justin和Donald正在玩一种游戏：跳棋。你可能没有听说过，但是规则非常简单。

棋盘是一个矩形网格，在最开始时，每一格上恰好有一个棋子，并且每名玩家在棋盘上最少拥有一枚棋子。Justin的棋子被标记为`J`，而Donald的被标记为`D`。

Justin先下棋。在一次移动中，这位玩家可以移动自己的一枚棋子并吃掉相邻的一枚棋子 **（不一定是对手的）** ，随后轮到对手。如果当前玩家无法进行这样的操作，那么这位玩家就输了。

棋子$A$与$B$是相邻的，当且仅当$A$正好在$B$的上/下/左/右一格。

在理想的世界中，两人都是绝佳的逻辑学者，可以知晓每种棋盘上的最佳策略。然而这是不现实的。事实上，在游玩时，两人只会选择相对较好的走法。它到底有多好取决于Justin和Donald的误差常数，分别是$J$和$D$。

形式化地，拥有误差常数$A$的玩家会从所有可能的走法中选择其中$A$种组成方案集合。如果所有可能的走法数$ P \le A $，那么方案集合仅包含这$P$种。之后，这位玩家会随机（等概率）地挑选其中的一种并依此进行操作。

两人在挑选方案组成集合时总会选择最优的方案，亦知晓对手也会选择最优方案。

请问Justin获胜的概率是多少？

inputFormat:
第一行两个正整数，$R C$（用空格隔开）。

之后$R$行，每行$C$个字符，代表初始棋盘上的棋子分布（含义见题目描述）。

之后一行两个正整数，$J D$（用空格隔开），含义见题目描述。

outputFormat: 一行，一个精确到3位小数的浮点数，代表Justin获胜的概率。

hint:
### 限制

$ 1 \le R \times C \le 13 $

$ 1 \le J,D \le 13 $

初始棋盘棋子分布只用`J`和`D`这两种字符表示。

### 样例说明

**样例1：**

Justin拥有3种移动的可能性，移动后分别为：（用`_`表示空棋子）

`_JD`（第一颗向右移），`J_J`（第二颗向右移），`J_D`（第二颗向左移）。

对于情况1，Justin败。对于情况2和3，Justin胜。由于Justin的误差常数为3，他会选择所有的情况，故胜率为$\frac{2}{3}$，取0.667。

**样例2：**

Justin拥有4种移动的可能性，移动后分别为：（用`_`表示空棋子）

```
J_ _J J_ _J
DD DD DJ JD
```

然而，无论Justin选择哪种，他都没有可能赢。

之后Donald会选择最优的移动。他可以选择以下的方式击败对应的Justin：

```
D_ _D J_ _J
_D D_ _D D_
```

故而Justin不可能赢。


title: 「BOI 2002」双调路径

description:
如今的道路收费发展很快。道路的密度越来越大，因此选择最佳路径是很现实的问题。城市的道路是双向的，每条道路有固定的旅行时间以及需要支付的费用。

路径是连续经过的道路组成的。总时间是各条道路旅行时间的和，总费用是各条道路所支付费用的总和。一条路径越快，或者费用越低，该路径就越好。严格地说，如果一条路径比别的路径更快，而且不需要支付更多费用，它就比较好。反过来也如此理解。如果没有一条路径比某路径更好，则该路径被称为最小路径。

这样的最小的路径有可能不止一条，或者根本不存在路径。

问题：读入网络，计算最小路径的总数。费用时间都相同的两条最小路径只算作一条。你只要输出不同种类的最小路径数即可。

inputFormat:
第一行有四个整数，城市总数 $n$，道路总数 $m$，起点和终点城市 $s,e$。
$\newline$
接下来的 $m$ 行每行描述了一条道路的信息：两个端点 $p,r$，费用 $c$，以及时间 $t$；
$\newline$
两个城市之间可能有多条路径连接。

outputFormat: 输出一行一个数，表示最小路径的总数。

hint:
**数据范围：**
- $1\leq{n}\leq100$，$0\leq{m}\leq300$。
- $1\leq{s,e,p,r}\leq{n}$，$0\leq{c,t}\leq100$。
- $s\neq{e}，p\neq{r}$。

**样例解释：**

![样例输入](https://z3.ax1x.com/2021/09/24/4DN3xP.png)

从 $1$ 到 $4$ 有 $4$ 条路径。为 $1\rightarrow 2\rightarrow 4$（费用为 $4$，时间为 $5$），$1\rightarrow 3\rightarrow 4$（费用为 $4$，时间为 $5$），$1\rightarrow 2\rightarrow 3\rightarrow 4$（费用为 $6$，时间为 $4$），$1\rightarrow 3\rightarrow 2\rightarrow 4$（费用为 $4$，时间为 $10$）。

$1\rightarrow 3\rightarrow 4$ 和 $1\rightarrow 2\rightarrow 4$ 比 $1\rightarrow 3\rightarrow 2\rightarrow 4$ 更好。有两种最佳路径：费用为 $4$，时间为 $5$（$1\rightarrow 2\rightarrow 4$ 和 $1\rightarrow 3\rightarrow 4$）和 费用为 $6$，时间为 $4$（$1\rightarrow 2\rightarrow 3\rightarrow 4$）。


title: 「SWTR-1」Sunny's Crystals

background: 小 $\mathrm{S}$ 喜欢收集水晶。

description:
小 $\mathrm{S}$ 有 $n$ 个水晶，每个水晶有一个属性 $d_i$ ，为这个水晶的**价值**。

有一天，小 $\mathrm{A}$ 来到了 小 $\mathrm{S}$ 家，让 小 $\mathrm{S}$ 把他的水晶排成一个序列，并且摧毁所有价值为 $w$ 的水晶。

但是，由于这个序列的特殊性，你的每次摧毁必须要满足：

- 该水晶在序列里的位置**必须要是 $2$ 的次幂**，即你只能摧毁在 $2^x$ 这个位置上的水晶，$0\leq x \leq \log_2 y$ 且为整数，其中 $y$ 为现在序列里水晶的个数。

摧毁后，**所有在该水晶后面的水晶都会向前移动一格**。

例如，水晶价值序列 $6\  10\  4\  7\  8$，你只能摧毁位置为 $1,2,4$ 上的水晶。

如果摧毁 $2$ 号水晶，序列就会变成 $6\  4\  7\  8$。

为了节省时间，小 $\mathrm{S}$ 想知道**最少**多少次可以摧毁所有价值为 $w$ 的水晶，且第 $i$ 次摧毁的水晶初始位置是什么。

**本题使用 Special Judge**，如果有多种答案，任意输出一种即可。

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

第二行，$n$ 个正整数 $d_i$。

outputFormat:
第一行一个整数 $m$，表示最少可以摧毁所有 $w$ 的次数。

接下来一行 $m$ 个数，第 $i$ 个数表示 第 $i$ 次摧毁时被摧毁的水晶的**初始位置**是什么，**用空格隔开**。

hint:
---

### 样例说明

样例 $1$：

先摧毁后面的 $4$，初始位置为 $4$，**价值**序列变成： $1\  4\  2\  5$。

再摧毁前面的 $4$，初始位置为 $2$。

总次数是 $2$ 次。

样例 $2$：

先摧毁第 $1$ 个 $2$，初始位置为 $2$，序列变成：$1\  2\  2\  2$。

再摧毁剩下的第 $1$ 个 $2$，初始位置为 $3$，序列变成：$1\  2\  2$。

再摧毁第一个 $2$，初始位置为 $4$，序列变成：$1\  2$。

再摧毁第一个 $2$，初始位置为 $5$。

总次数是 $4$ 次。

---

### 数据范围与约定

对于 $15\%$ 的数据，有 $n\leq5$。

对于 $25\%$ 的数据，有 $n\leq20$。

对于 $30\%$ 的数据，有 $n\leq1000$。

对于 $35\%$ 的数据，有 $n\leq10000$。

对于 $50\%$ 的数据，有 $n\leq3\times 10^5$。

对于 $80\%$ 的数据，有 $n\leq10^6$。

对于 $100\%$ 的数据，有 $1\leq n\leq3\times 10^6,1\leq d_i\leq 40000$，保证 $w$ 的个数不大于 $1.5\times 10^6$。

---

碎掉的水晶在阳光下闪闪发光……


title: [CCO2019] Sirtet

description:
在一款新型的无人游戏（话说这算游戏吗）Sirlet中，界面是一个矩形网格。在游戏开始之前，一些方格是空白的（表示为`.`），而一些方格是被填充的（表示为`#`）。那些被填充的方格代表一组物体，而相邻的被填充方格被视作同一物体。

例如，这个初始网格：

```
..#.
##.#
.##.
#...
#...
```

包含以下4个物体：

```
##   #  #  #
 ##  #
```

当游戏开始时，每个物体开始以相同的速度匀速下落，它们持续下落，直到它接触到最下面的一行或是另一物体的顶部，而在接触时停止下落。

求网格的最终状态。

inputFormat:
第一行，两个正整数$N M$（用空格隔开）。

随后$N$行，每行$M$个字符，代表网格。它们或是`#`，或是`.`，含义见题目描述。

outputFormat: $N$行，每行$M$个字符，代表网格的最终状态。它们或是`#`，或是`.`，含义见题目描述。

hint:
### 限制

$ 1 \le N \times M \le 10^6 $

### 子任务

Subtask 1 （40分）：$ 1 \le N \times M \le 2000 $

Subtask 2 （24分）：$ M = 2 $

Subtask 3 （36分）：没有附加限制。


title: [CCO2019] Winter Driving

description:
在雪白帝国背部分布有$N$个城市，从$1$到$N$编号。对于一座城市$i$，有$A_i$位居民居住在其中。

它们间分布有$N-1$条道路，从$2$到$N$编号。对于一条路$j$，它连接城市$j$和$P_j$，其中$P_j \lt j$。任何城市最多被连接到36条路。

在冬季，危险的驾驶条件使得政府执行交通管制，所有的路都变为单向高速公路，即对于一条路$j$，它要么成为从城市$j$到城市$P_j$的单向高速公路，要么成为从城市$P_j$到城市$j$的单向高速公路。

此时，每个居民都想给其他所有公民寄假日贺卡。然而，如果要从城市$X$向城市$Y$发送一张假日贺卡，必须保证可以通过高速公路连接$X$和$Y$，或者$X=Y$。

请求出，当所有的公路都被转换为单向高速公路后，最多可以被送出的贺卡总数。

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

第二行，$N$个正整数$A_1$ ~ $A_N$。

第三行，$N-1$个正整数$P_2$ ~ $P_N$。

outputFormat: 一行，一个正整数，即最多可以被送出的贺卡总数。

hint:
### 样例解释

一种可能的做法是将：

![avatar](https://s2.ax1x.com/2019/08/29/mq4eat.png)

转化为：

![avatar](https://s2.ax1x.com/2019/08/29/mq5jtx.png)

此时，3号城的每个居民都可以往3号城寄3张卡片，往2号城寄3张，往1号城寄3张，往4号城寄1张。所以3号城共计可以发送40张。

相似地，2号城共可寄18张，3号城共可寄9张，4号城一张也寄不了。

所以答案为$40+18+9+0=67$。

### 限制

$2 \le N \le 200 000$

对于任意合法$i$，$1 \le A_i \le 10 000$

对于任意合法$j$，$1 \le P_j \le j$

设$D$为任意一个城市连接的道路数量。$D \le 36$。

### 子任务

Subtask 1（20分）：$N \le 10$

Subtask 2（20分）：$N \le 1000$，$D \le 10$

Subtask 3（20分）：$D \le 18$

Subtask 4（20分）：$N=37$，且所有的道路均连向一个城市，亦即这个城市有36条连接的城市，且它们均只通过一条道路连向此城。

Subtask 5（20分）：没有附加限制。


title: 「SWTR-1」Doing Homework

background: 小 $\mathrm{A}$ 每天都有很多作业要写。

description:
每天，小 $\mathrm{A}$ 都要写至少 $w$ 吨的作业，如果他达不到目标，就会受到小 $\mathrm{S}$ 制裁并且当场去世。

小 $\mathrm{A}$ 有 $x$ 点精力，每次写作业都会降低小 $\mathrm{A}$ 的精力，且**不可逆**，小 $\mathrm{A}$ 的精力不可以降为负数。

现在，有 $n$ 种作业给小 $\mathrm{A}$ 选。

每种作业有如下的属性：

$x_i:$ 消耗的精力，即写一份这种作业需要 $x_i$ 的精力。

$w_i:$ 重量，即这种作业一份有 $w_i$ 吨。

$t_i:$ 截止日期，即从今天过了 $t_i$ 天之后，这个作业不可以再写。

**每种作业都有无限个。**

因为他的作业实在是多得写不完，所以请你为他安排一种写作业的方案，**最大化**他能存活的天数，当存活天数已最大化时，最大化他剩余的精力。

inputFormat:
第一行两个正整数 $x,w$ ，即小 $\mathrm{A}$ 的精力和每天的目标。

接下来一行一个正整数 $n$ ，表示作业的种数。

接下来 $n$ 行，每行三个整数 $x_i,w_i,t_i$。

outputFormat: 输出两个由空格隔开的数，分别表示小 $\mathrm{A}$ 最多能活多少天，以及剩余的精力。

hint:
---

### 样例说明

第一天，小 $\mathrm{A}$ 选择写 $2$ 份第二种作业，重量为 $2 * 2=4$，剩余精力为 $30-2 * 3=24$。

第二天，小 $\mathrm{A}$ 选择写 $2$ 份第二种作业，重量为 $2 * 2=4$，剩余精力为 $24-2 * 3=18$。

至此，不可以再写第二种作业 $(t_2=2)$。

第三天，小 $\mathrm{A}$ 选择写 $1$ 份第三种作业，重量为 $4$，剩余精力为 $18-8=10$。

第四天，小 $\mathrm{A}$ 选择写 $1$ 份第三种作业，重量为 $4$，剩余精力为 $10-8=2$。

至此，不可以再写第三种作业 $(t_3=4)$。

小 $\mathrm{A}$ 没有精力再去写别的作业了，所以他最多能活 $4$ 天，剩余精力为 $2$。

可以证明，找不到比该方案更优的方案了。

---

### 数据范围

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

---

对于 $n \leq 5000$ 中 $25\%$ 的数据，有时间限制 $1s$，空间限制 $256MB$。

其余测试点时间限制 $400ms$，空间限制 $8MB$。


title: [BalkanOI2011] timeismoney | 最小乘积生成树

description:
给出一个 $n$ 个点 $m$ 条边的无向图，第 $i$ 条边有两个权值 $a_i$ 和 $b_i$ 。

求该图的一棵生成树 $T$ ，使得

$$\left(\sum_{e\in T}a_e\right)\times\left(\sum_{e\in T}b_e\right)$$

最小。

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

下 $m$ 行，每行 $4$ 个整数 $u_i,v_i,a_i,b_i$ ，表示第 $i$ 条边连接  $u_i$ 和 $v_i$ ，权值为 $a_i$ 和 $b_i$ 。

点的编号为 $0\sim n-1$ 。

outputFormat:
假设你求出的生成树为 $T$ ，你需要输出一行两个整数，分别为 $\displaystyle\sum_{e\in T}a_e$ 和 $\displaystyle\sum_{e\in T}b_e$ 。

如果有多解，请输出 $\displaystyle\sum_{e\in T}a_e$ 最小的那个。


title: 【XR-3】等差数列

description:
小 X 给了你一个等差数列的前两项以及项数，请你求出这个等差数列各项之和。

等差数列：对于一个 $n$ 项数列 $a$，如果满足对于任意 $i \in [1,n)$，有 $a_{i+1} - a_i = d$，其中 $d$ 为定值，则称这个数列为一个等差数列。

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

hint:
【样例 $1$ 说明】

这个等差数列为 `1 2 3`，其各项之和为 $6$。


title: 【XR-3】小道消息

description:
小 X 想探究小道消息传播的速度有多快，于是他做了一个社会实验。

有 $n$ 个人，其中第 $i$ 个人的衣服上有一个数 $i+1$。小 X 发现了一个规律：当一个衣服上的数为 $i$ 的人在某一天知道了一条信息，他会在第二天把这条信息告诉衣服上的数为 $j$ 的人，其中 $\gcd(i,j)=1$（即 $i,j$ 的最大公约数为 $1$）。在第 $0$ 天，小 X 把一条小道消息告诉了第 $k$ 个人，小 X 想知道第几天时所有人都会知道这条小道消息。

可以证明，一定存在所有人都知道了这条小道消息的那一天。

提示：你可能需要用到的定理——[伯特兰-切比雪夫定理](https://baike.baidu.com/item/%E4%BC%AF%E7%89%B9%E5%85%B0-%E5%88%87%E6%AF%94%E9%9B%AA%E5%A4%AB%E5%AE%9A%E7%90%86/2053704)。

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

hint:
【样例 $1$ 说明】

$3$ 个人的衣服上的数分别为 `2 3 4`。

在第 $0$ 天，小 X 把一条小道消息告诉了第 $1$ 个人，他的衣服上的数为2。

在第 $1$ 天，第 $1$ 个人会告诉第 $2$ 个人，因为 $\gcd(2,3) = 1$，但他不会告诉第 $3$ 个人，因为 $\gcd(2,4) = 2 \ne 1$。

在第 $2$ 天，第 $2$ 个人会告诉第 $3$ 个人，因为 $\gcd(3,4) = 1$，这时所有人都知道了这条小道消息，因此答案为 $2$。


title: 【XR-3】核心城市

description:
X 国有 $n$ 座城市，$n - 1$ 条长度为 $1$ 的道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。

X 国国王决定将 $k$ 座城市钦定为 X 国的核心城市，这 $k$ 座城市需满足以下两个条件：

1. 这 $k$ 座城市可以通过道路，在不经过其他城市的情况下两两相互到达。
2. 定义某个非核心城市与这 $k$ 座核心城市的距离为，这座城市与 $k$ 座核心城市的距离的最小值。那么所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离最小。你需要求出这个最小值。

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

接下来 $n - 1$ 行，每行 $2$ 个正整数 $u,v$，表示第 $u$ 座城市与第 $v$ 座城市之间有一条长度为 $1$ 的道路。

**数据范围：**

- $1 \le k < n \le 10 ^ 5$。
- $1 \le u,v \le n, u \ne v$，保证城市与道路形成一棵树。

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

hint:
【样例说明】

钦定 $1,2,5$ 这 $3$ 座城市为核心城市，这样 $3,4,6$ 另外 $3$ 座非核心城市与核心城市的距离均为 $1$，因此答案为 $1$。


title: 【XR-3】系统设计

description:
小 X 需要你设计一个系统。

这个系统首先需要输入一棵 $n$ 个点的有根树和一个长度为 $m$ 的序列 $a$，接下来需要实现 $q$ 个操作。

操作分两种：

1. `1 x l r` 表示设定起点为有根树的节点 $x$，接下来依次遍历 $l \sim r$。当遍历到 $i$ 时，从当前节点走向它的编号第 $a_i$ 小的儿子。如果某一时刻当前节点的儿子个数小于 $a_i$，或者已经遍历完 $l \sim r$，则在这个点停住，并输出这个点的编号，同时停止遍历。
2. `2 t k` 表示将序列中第 $t$ 个数 $a_t$ 修改为 $k$。

inputFormat:
第一行 $3$ 个正整数 $n,m,q$，分别表示树的点数、序列的长度和操作个数。

第二行 $n$ 个整数 $f_{1 \dots n}$，其中 $f_i$ 表示点 $i$ 在树中的父亲节点编号，特别地，设根节点为 $rt$，则 $f_{rt} = 0$。

第三行 $m$ 个正整数 $a_{1 \dots m}$，表示序列 $a$。

接下来 $q$ 行，每行描述一个操作。

**数据范围：**

- $1 \le n,m,q \le 5 \times 10 ^ 5$。
- $1 \le a_i \le n$。
- 对于操作 $1$，保证 $1 \le x \le n$，$1 \le l \le r \le m$。
- 对于操作 $2$，保证 $1 \le t \le m$，$1 \le k \le n$。

outputFormat: 对于每个操作 $1$，一行一个正整数，表示答案。

hint:
本题读入、输出量较大，请使用[读入、输出优化](https://oi-wiki.org/misc/io/)。

【样例说明】

第一个操作为 `1 1 1 3`，即 $1 \rightarrow 2 \rightarrow 4$，因此答案为 $4$。

第九个操作后，序列变为 `2 1 2 1 2 1`。

第十个操作为 `1 1 1 5`，即 $1 \rightarrow 5 \rightarrow 6$，因此答案为 $6$。


title: 【XR-3】Namid[A]me

description:
小 X 给了你一棵 $n$ 个点的树，点有点权。

你需要求出下列式子模 $786433$ 的值：

$\sum_{1\leq u\leq v\leq n}f(u,v)^{f(u,v)}$

其中 $f(u,v)$ 表示 $u$ 到 $v$ 的最短路径上所有点的点权按位与在一起之后的值。

提示：为了方便你的计算，这里我们认为 $0^0=0$。另外，$786433$ 是一个质数，同时也是一个不常用的 NTT 模数，它的原根为 $10$，如果你不知道什么是 NTT 或者不知道什么是原根，你可以忽略这个提示。

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

第二行 $n$ 个正整数 $a_{1\dots n}$，其中 $a_i$ 表示编号为 $i$ 的点的点权。

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

**数据范围：**

- $2 \le n \le 2 \times 10^5$。
- 对于所有满足 $1\le i \le n$ 的 $i$ 都有 $1 \le a_i < 2^{30}$。
- $1 \le u,v \le n, u \ne v$。
- 设 $d$ 为树中叶子（度数为 $1$ 的点）的个数，数据保证 $4\le n \cdot d \le 3 \times 10 ^ 6$。

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


title: 【XR-3】Unknown Mother-Goose

description:
小 X 得到了一个正整数 $n$ 和一个正整数集合 $S$，他想知道有多少个正整数 $x$ 满足以下所有条件：

- $3 \le x \le n$
- 存在 $a \in S, x \equiv 0 \pmod a$
- 存在 $b \in S,x-1 \equiv 0 \pmod b$
- 存在 $c \in S,x-2 \equiv 0 \pmod c$

请你帮小 X 求出来。

inputFormat:
第一行两个正整数 $n,|S|$，表示你得到的 $n$ 和正整数集合 $S$ 的大小。

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

**数据范围：**

- $3 \le n \le 10^9$。
- $3 \le |S| \le 20$。
- 保证 $S$ 中所有元素均小于 $n$，不保证所有元素互不相同。

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

hint:
【样例 $1$ 说明】

只有当 $x = 6$ 时：

- $x \equiv 0 \pmod 2$
- $x \equiv 1 \pmod 5$
- $x \equiv 2 \pmod 4$

满足条件。


title: [USACO19FEB] Sleepy Cow Herding S

description:
Farmer John的N头奶牛，总是会迷路走到农场上遥远的地方去！他需要你帮助将她们一起赶回来。
农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴，奶牛可以占据数轴上的任意整数位置。这N头奶牛现在正位于不同的整数位置，Farmer John想要移动她们，使得她们占据N个相邻的位置（例如，位置6、7、8）。

不幸的是，奶牛们现在很困，Farmer John要让她们集中精力听从命令移动并不容易。任意时刻，他只能使得一头处在“端点”（在所有奶牛中位置最小或最大）位置的奶牛移动。当他移动奶牛时，他可以命令她走到任意一个未被占用的整数位置，只要在新的位置上她不再是一个端点。可以看到随着时间的推移，这样的移动可以使奶牛们趋向越来越近。

请求出使得奶牛们集中到相邻位置所进行的移动次数的最小和最大可能值。

inputFormat: 先输入一个整数N(N<=100000)，接下来输入N个数，表示N头奶牛的位置。

outputFormat: 输出的第一行包含Farmer John需要将奶牛们聚集起来所需进行的最小移动次数。第二行包含他将奶牛聚集起来能够进行的最大移动次数。

hint: 2019 USACO二月月赛银牌组第一题


title: 【AFOI-19】数码排序

background:
小L从虚拟世界里出来啦！

---

**加强版[链接](https://www.luogu.org/problem/P5634)**

description:
逃出来的同时，也有一部分数码逃了出来，吵着闹着让小L帮他们排序

虚拟世界的数码都是不可见的

小L目前只会选择排序，插入排序，冒泡排序，归并排序

所以小L想问他在最坏情况下最少需要几次比较，才能使序列有序

-------

[排序的模板代码](https://www.luogu.org/paste/fdtepscp)

inputFormat: 输入仅有一行，给定一个正整数 $n$，表示序列的长度

outputFormat: 输出最小的比较次数

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

长度为$4$的序列归并调用，分成$2$组，一组$2$个元素。$2$个元素分别比较一次， 合并时最坏比较$3$次，所以是$3+1+1=5$。

- **数据范围**

对于$10\%$的数据，$n \leq 1000$

对于$30\%$的数据，$n \leq 1000000$

对于$100\%$的数据，$n \leq 10^{16}$

**数据保证随机**


title: [USACO19FEB] The Great Revegetation S

description:
一场漫长的干旱使农场主约翰的 $N$ 个牧场没有草。然而，随着雨季的到来，是时候“重新种植”了。在农夫约翰的小屋里，他有两个桶，每个桶都有不同类型的草籽。他想在他的每一个牧场种草，在每一个牧场中选择一种类型的草。

作为一名奶农，农场主约翰想确保他能满足他那几头奶牛的特殊饮食需求。他的 $m$ 头奶牛都有两个最喜欢的牧场。他的一些奶牛有一个饮食限制，那就是他们应该只吃一种类型的草，因此农场主约翰希望确保在这类奶牛最喜欢的两个田里种植同一种类型的草。其他的奶牛有一个不同的饮食限制，要求他们吃不同类型的草。对于那些奶牛，农场主约翰当然想确保他们最喜欢的两块田地里有不同的草。

请帮助农场主约翰确定他在他的 $N$ 个牧场上种植草的不同方式的数量。

inputFormat:
输入的第一行包含两个整数 $N$（$2\le N\le10^5$）和 $m$（$1\le m\le10^5$）。

之后 $m$ 行，每行描述了一头奶牛。首先是一个字符 `S` 或 `D`，表示这头奶牛需要相同（`S`）还是不同（`D`）的草类型，然后是两个 $1\sim N$ 的整数，表示这头奶牛喜欢的两块牧场。

outputFormat: 输出农场主约翰在他的 $N$ 个牧场上植草的方式。请用二进制写你的答案。

hint: USACO 2019 二月月赛银牌组第三题


title: [CmdOI2019] 高塔与晶石

background:
**温馨提示 : 请注意常数因子对程序效率带来的影响 + 本题特殊的空间限制**

几何王国之中，矗立着$n$座古老的高塔，传说，它们是这片净土的守护者。

随着几何学日新月异的发展，王国的繁荣引来了烈炎深处的恐怖：动点P。

驯服动点恶龙的英雄笛卡尔尚未出现，几何王国的领主决定固守静态几何的阵地。

description:
他得到了静态几何的三颗智慧晶石(里面当然是神级数学题啦)，并且可以把它们安放在高塔之中。

三颗安放着晶石的高塔，可以保护其围成的三角形内部不受侵入。

但是，如果晶石围成的三角型面积太大，防线将会十分容易被击破。

如果三角型面积太小，其中能够产生的几何能量又不足以维持晶石的运作。

经过几天的推算，领主在认为， $\binom{n}{3}$ 种做法中,面积第 $k$ **小**的方案是最合适的。

(三角形面积可以为 $0$)

他对这个结果很不放心，于是拜托单手虐爆无数几何题的你,来帮他计算这个面积具体是多少。

inputFormat:
第一行两个整数$n,k$，意义如题目所述。

后 $n$ 行，第 $i$ 行有两个数 $x_i,y_i$ ，表示 $i$ 号高塔的坐标。

outputFormat: 输出面积第 $k$ **小**方案对应面积的**2倍**，容易证明这一定是个整数。


title: [USACO19FEB] Painting The Barn S

description:
农夫约翰不擅长多任务处理。他经常分心，很难完成长的项目。目前，他正试图在谷仓的一侧上漆，但他一直在画小矩形区域，然后由于照料奶牛的需要而偏离了方向，使得谷仓的某些部分上漆的涂料比其他部分多。

我们可以将谷仓的一侧描述为一个二维 $x-y$ 平面，农夫约翰在该平面上绘制 $n$ 个矩形，每个矩形的边都与坐标轴平行，每个矩形由谷仓的左下角和右上角点的坐标描述。

农夫约翰想在谷仓上涂几层油漆，这样在不久的将来就不需要再重新粉刷了。但是，他不想浪费时间涂太多的油漆。结果表明，$K$ 涂层是最佳用量。请在他画完所有的长方形后，帮他确定谷仓有多少面积被 $K$ 层油漆覆盖。

inputFormat:
输入的第一行包含 $n$ 和 $K$。

其余 $n$ 行中的每一行包含四个整数 $x1$、$y1$、$x2$、$y2$，描述正在绘制的矩形区域，左下角 $(x1,y1)$ 和右上角 $(x2,y2)$。所有 $x$ 和 $y$ 值都在 $0$ 到 $1000$ 范围内，并且所有矩形都有正面积。

outputFormat: 请输出谷仓被 $K$ 层油漆覆盖的区域。

hint:
$1\le K\le n\le 10^5$。

USACO 2019 二月月赛银牌组第二题。


title: 火烧の云

description:
乡间小路可以近似理解成 $n\times m$ 的矩阵，道路有许多种，这里只列举其中的一小部分：

1. ``#``：水池，无法通行。
2. ``|``：直行类道路，竖直方向只能直行，水平方向只能左转、右转。
3. ``-``：直行类道路，水平方向只能直行，竖直方向只能左转、右转。
4. ``/``：转弯类道路，竖直方向只能右转，水平方向只能左转。
5. ``\``：转弯类道路，竖直方向只能左转，水平方向只能右转。
6. ``.``：四岔路口，可以直行、左转、右转。
7. ``S``：入口，从乡间之外进入入口不需要时间。
8. ``E``：出口，从出口到达乡间之外不需要时间。

前进类道路：到此格之后方向必须花费时间转向 `?`，如果来向就是 `?` 方向则不花费时间并必须跳一格。

9. ``<``：`? = 西`。
10. ``>``：`? = 东`。
11. ``^``：`? = 北`。
12. `v`：`? = 南`。

**简单来说，就是和这类道路逆向时不能走，垂直于它的方向时花时间转到它的方向，顺着它的方向时就能够不花时间且必须一次性走两格。**

直行类道路、转弯类道路、四岔路口、前进类道路依次花费 $a,b,c,d$ 个单位时间。

由于乡间的构造奇特，可能 **不止一个** 入口和出口。

求任意入口到任意出口的 **最短时间**，出入时的方向不作要求。

---

**题意简述**

给定一张 $n\times m$ 的地图，求起点 `S` 到终点 `E` 的最短时间，注意起点和终点可能有多个。

outputFormat: 输出从起点到达终点所需花费的最少时间，若无法到达终点，输出无解信息 `-1`。

hint:
#### 样例说明

样例 #1：从起点 $(1,1)$ 开始，到终点 $(3,3)$ 的路径为：$(1,1)\rightarrow(1,2)\rightarrow(1,3)\rightarrow(2,3)\rightarrow(3,3)$。经过了 $3$ 个四岔路口，每个的代价是 $4$，沿途的代价：$4\times3=12$。

样例 #2：从起点 $(1,1)$ 开始，到终点 $(1,3)$ 的路径为：$(1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(1,3)$。经过 $2$ 个转弯类道路和 $1$ 个直行类道路，沿途的代价：$2\times2+1\times1=5$。

样例 #3：选择 $(1,1)$ 的 `S` 和 $(1,2)$ 的 `E`，出入口相邻，代价为 $0$。

样例 #4：通过前进类道路 `>` 可以跳一格直接到达 `E`，跳一格时不花费时间。

样例 #5：前进类道路也可以用于转向，此时的功能与 `/` 相同，转向同样需要时间。

样例 #6：这里 `#` 不能通过，因此不存在 `S` 到 `E` 的道路。

#### 数据范围

| 子任务编号 | 分值 | $n,m\le$ | 特殊性质 |
| :-: | :-: | :-: | :-: |
| $1$ | $10$ | $10$ | $\times$ |
| $2$ | $15$ | $\times$ | $a=b=c=d=1$ |
| $3$ | $20$ | $100$| $\times$ |
| $4$ | $25$ | $\times$ | 字符 `S`、`E` 的数量 $=1$ |
| $5$ | $30$ | $\times$ | $\times$ |

**本题请注意常数因子对程序效率的影响。**

对于 $100\%$ 的数据：$1\le n,m\le2000$，$0\le a,b,c,d\le100$。


title: [JSOI2016] 炸弹攻击1

background: JYY 最近迷上了一款塔防游戏，在游戏里 JYY 除了建设建筑，还可以使用炸弹对屏幕上的敌人进行范围杀伤。

description:
游戏地图可以简单认为是一个二维平面。JYY 建造了$N$个建筑，每个建筑都是一个圆，其中第$i$个建筑的圆心位于$(x_i,y_i)$且半径为$r_i$。地图上一共有$M$个敌人，一个敌人可以近似看成一个平面上的点，其中第$i$个敌人位于$(p_i,q_i)$。JYY 可以使用一枚可以设置半径的炸弹，可以设置一个不超过$R$的范围，然后选择平面上的一个点引爆，范围内的所有敌人全部消灭。

当然，由于炸弹威力巨大，如果爆炸范围接触到 JYY 的建筑，那么 JYY 的建筑也会受到损伤。（注：如果炸弹的爆炸范围仅接触到了 JYY 建筑的边界，则不会对 JYY 的建筑造成损伤；如果敌人出现在了爆炸范围的边界，则该敌人被消灭）JYY 可以自由控制炸弹的爆炸地点和爆炸半径。作为一个保守的玩家，他希望在保证自己建筑毫发无损的情况下，消灭尽量多的敌人。

inputFormat:
第一行包含三个非负整数，分别为$N,M,R$；

接下来$N$行，每行三个整数，其中第$i$行为$x_i,y_i,r_i$，表示第$i$个建筑的位置和半径。数据保证所有建筑不相交（但是有可能边界接触）；

接下来$M$行，每行两个整数，其中第$i$行为$p_i,q_i$，表示第$i$个敌人的位置。

outputFormat: 输出一行一个整数，表示 JYY 最多可以消灭的敌人数量。


title: [JSOI2016] 炸弹攻击2

background: 还记得那款题为炸弹攻击的塔防游戏吗？这款游戏出了续作，炸弹的威力大大加强了。

description:
游戏的地图是一个二维平面。JYY 的阵地位于$x$轴下方，而所有的敌人目前都位于$x$轴上方。

在 JYY 的阵地中有建有$T$个激光塔和$S$个发射源。其中第$i$个防御塔$T_i$的坐标为$(tx_i,ty_i)$，第$i$个发射源$S_i$的坐标为$(sx_i,sy_i)$。

地图上有$D$个敌人，第$i$个敌人$D_i$的坐标为$(dx_i,dy_i)$。

两座激光塔可以相互连接形成能量墙。发射源朝向敌人发出的能量如果穿过了能量墙，可以得到巨大的加强而变为超级射线并瞬间消灭敌人。

JYY 想知道他有多少种可以可以发出超级射线的攻击方案。

具体来说，一个可以发出超级射线的攻击方案为一个由四个点组成的集合：{$T_i,T_j,S_k,D_l$}，满足$1$$\leq$$i$$<$$j$$\leq$$T$$,$$1$$\leq$$k$$\leq$$S$$,$$1$$\leq$$l$$\leq$$D$，并且线段$T_iT_j$和线段$S_kD_l$相交。

游戏设定保证在这$T$$+$$D$$+$$S$个点中，不存在重点也不存在三点共线。

inputFormat:
第一行包含一个正整数$D$；

接下来$D$行，每行包含两个整数$dx_i,dy_i$，表示一个敌人的坐标；

第$D$$+$$1$行包含一个整数$S$；

接下来$S$行，每行包含两个整数$sx_i,sy_i$，表示一个发射源的坐标；

第$D$$+$$S$$+$$1$行包含一个整数$T$；

接下来$T$行，每行包含两个整数$(tx_i,ty_i)$，表示一个激光塔的坐标。

outputFormat: 输出一行一个整数，可以发出超级射线的攻击方案个数。


title: 简单数论题

description:
给出一个长度为 $n$ 的序列 $a$，$q$ 次询问 $\prod_{i=l}^r \operatorname{lcm}(a_i,x)$ 的值。

答案对 $10 ^ 9 + 7$ 取模。

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

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

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

outputFormat: $q$ 行，一行一个答案。


title: 数码排序【加强版】

background:
**本题是[P5626](https://www.luogu.org/problem/P5626)的加强版**

小L从虚拟世界里出来啦！

description:
逃出来的同时，也有一部分数码逃了出来，吵着闹着让小L帮他们排序。

虚拟世界的数码都是不可见的。

小L目前只会选择排序，插入排序，冒泡排序，归并排序。

所以小L想问他在最坏情况下最少需要几次比较，才能使序列有序。

------

[排序的模板代码](https://www.luogu.org/paste/fdtepscp)

inputFormat: 输入仅有一行，给定一个正整数 $n$ ，表示序列的长度。

outputFormat: 输出最小的比较次数，答案对$100000007$取模。


title: [CmdOI2019] 算力训练

background:
最近，出题人快乐地学习了如何解一元二次方程。

晚上在宿舍里，出题人梦见了一个使用 $k$ 进制的国度，入乡随俗嘛，出题人在这里也使用 $k$ 进制。

当然，这个国度里面的人也懂数学，所以解不出一元二次方程的出题人并没有逃掉算力训练。

description:
出题人在纸条上写了 $n$ 个 $k$ 进制自然数，由于他很懒，这些数的位数不会太多，都不会超过 $m$ 位。

为了训练算力，他每次会**随意取出一个子序列** (允许一个数都不选) ，然后把这些数都加起来。

他又觉得进位太麻烦了，干脆规定**加法不进位**。

算了几次之后，他突然很想知道自己得到每个数的方案数是多少，可是他太菜了，又不会算。冥思苦想一番之后,突然被起床铃拉出了梦境。

他觉得这个问题很有趣，只好求助于单手虐暴无数代数题的你，来帮忙计算一下。

**形式化题意** ： 对于一个序列 $A$ ，定义其权值 $W(A)$ 为 $A$ 中元素做 $k$ 进制不进位加法的和。

给出 $m,k$ 和一个长为 $n$ 的序列 $S$。保证 $S\subseteq [0,k^m)∩Z$。

对于 $t=0,1,2,...,k^m-1$ ，分别求出下列式子的值 ：

$${\rm Ans}[t]=\sum\limits_{\text{R 是 S 的子序列}}\big[W(R)=t\big]$$

注 ：根据正确的题意可推知 $\sum\limits_{t=0}^{k^m-1}{\rm Ans}[t]=2^n$。

inputFormat:
第一行三个整数 $n,k,m$ ，意义为题目中所述。

第二行 $n$ 个整数，之间用空格隔开，表示纸条上的数字。

(**注意**，纸条上的数均为 $k$ 进制数)

outputFormat: 共 $k^m$ 行,你需要在第 $i$ 行输出得到数 $i-1$ 的方案数，答案对 $998244353$ 取模。


title: [CmdOI2019] 任务分配问题

background: 挖矿的时候踢断电源线是一种怎样的体验?

description:
在某台有 $k$ 个 CPU 的计算机中，有 $n$ 个计算任务等待执行。

$a_i$ 为第 $i$ 个任务的优先级，方便起见， $a$ 为一个排列。

现在，要将这些任务分配给 CPU 去解决。

由于内存等原因，一个 CPU 只能负责连续一段的任务，并且要按 (从左到右的) 顺序执行。

**在某个 CPU 内**，无序度定义为：前者先执行，而后者优先级高的任务对的个数。

请最小化每个 CPU 的无序度之和。

inputFormat:
第一行两个整数 $n,k$ ，分别表示任务个数和 CPU 个数。

第二行 $n$ 个整数，表示 $a_{1\sim n}$ 。

outputFormat: 输出一个整数，表示最小的无序度之和。

hint:
| 测试点编号 | 　n　 | 　k　 |
| :--: | :--: | :--: |
| 1~2 | 25000 | 1 |
| 3 | 25000 | 2 |
| 4~5 | 1000 | 10 |
| 6~10 | 25000 | 25 |

(保证 $k\leq n$ ， #6~10时限2S)

**样例解释:**

- 样例1

此时只能把所有任务交给单独的一个 CPU。

第一个任务和其他所有任务都形成无序任务对。

此外最后两个任务也形成无序任务对，共 $5$ 个。

- 样例2

第一个 CPU 单独处理任务 $1$ ，无序度为 $0$ ;

第二个 CPU 处理 $\{5,4,2,3\}$ 无序度为 $1$ 。

tags: 凸完全单调性, wqs 二分


title: [BJ United Round #3] 押韵

background: 韵要怎么押？棋要怎么下？敌要怎么杀？旗要怎么插？

description:
现在你想要写一首歌词，一共有 $nd$ 个字，你一共设计了 $k$ 种韵脚，每个字恰好要符合一种韵脚。

并且只有当每种韵脚在歌词中出现的字数恰为 $d$ 的倍数时，这首歌才好听。

试问一共有多少种韵脚的搭配方法，使得歌词好听？

你只需要回答方案数对于 $1049874433$ 取模的结果即可。

inputFormat: 一行三个整数 $n,k,d$，如题意所示。

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


title: [BJ United Round #3] 三色树

description:
请你对满足以下要求的 $n$ 个节点的 **无标号无根树** 计数：

- 每个节点是三种颜色之一：红，蓝，黄
- 红色节点度数不超过 $4$，蓝色和黄色节点度数均不超过 $3$
- 黄色节点不能相邻

注意 **无标号无根树** 的意义是：如果两颗树可以通过重新编号的方法使得对应点颜色相同，对应连边一致，则认为是同一颗树。

答案对输入的质数 $p$ 取模。

inputFormat: 两个正整数 $n,p$，意义如题面所示。

outputFormat: 一个整数，表示方案数对 $p$ 取模的结果。

hint:
![](https://i.niupic.com/images/2019/09/08/_51.png)

对于 $100\%$ 的数据，保证：
$1\le n \le 3000$
$9\times 10^8 \le p \le 1.01 \times 10^9$
保证 $p$ 为质数

By：EntropyIncreaser


title: [BJ United Round #3] 观察星象

description:
EI 在用望远镜观察星星，星空中共有  $n$ 个星星，每个星星观察起来有一个二维直角坐标 $(x,y)$。

他的望远镜如果定位在 $(x_0,y_0)$ 处，可以看到所有 $(x_0-x)^2 + (y_0-y)^2 \le r^2$ 的星星。

望远镜的大小 $r$ 是可以调整的，EI 想知道如果他要至少看到 $m$ 个星星，至少需要把 $r$ 设置到多大？

inputFormat:
第一行两个正整数 $n,m$，表示星星的数量和要求看到的星星数量。
接下来 $n$ 行，每行两个整数 $x,y$，表示一个星星的坐标。
保证星星坐标两两不同。

outputFormat:
输出一行一个正实数，表示望远镜的最小半径。
令你的答案为 $a$，标准答案为 $b$，若 $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$
( 即绝对误差或者相对误差不超过 $10^{-6}$ ) 即为正确。

hint:
![](https://i.niupic.com/images/2019/09/08/_55.png)

对于 $100\%$ 的数据，保证：
$2 \le m \le n  \le 2000$
$|x|,|y| \le 10^4$

By：EntropyIncreaser


title: [POI2000] 公共串

description: 给出几个由小写字母构成的单词，求它们最长的公共子串的长度。

inputFormat: 文件的第一行是整数 $n$，$1\le n \le 5$，表示单词的数量。接下来$n$行每行一个单词，只由小写字母组成，单词的长度至少为$1$，最大为$2000$。

outputFormat: 仅一行，一个整数，最长公共子串的长度。


title: 「SWTR-1」Escape

background:
有一天，当 $\mathrm{Sunny}$ 闲逛的时候，发现了一个按钮。

好奇心驱使他按下了这个按钮。

突然间，天旋地转 $\dots$

description:
醒来之后，$\mathrm{Sunny}$ 发现自己站在一个奇怪的地方。

这个地方有 $n$ 个平台，**形成了一个环**。

这时，$\mathrm{Ethan}$ 的声音响起：

“哈哈哈哈哈哈，恭喜你，你是第一个来到**死亡之地**的人。”

“正如你所看到的，这个地方有 $n$ 个平台，你现在站在 $0$ 号平台上。”

“剩余平台按顺时针编号 $1,2,3\dots n-1$，也就是说，你身后的那个平台就是 $n-1$ 号平台。”

“你每次能够**顺时针**跳 $i$ 个平台，$i\in[1,n]$，每次的 $i$ 可以不一样。”

“如果你能够经过所有平台（初始 $0$ 号位置不算），那你就能逃出**死亡之地**了。”

（这里指的是一开始的 $0$ 号位置不算经过，需要再次经过 $0$ 号位置）

“不过，这样太简单了，我会给你一些数 $a_j$，表示你**不能一次顺时针跳 $a_j$ 个平台**。”

“还有，你必须要用**最少**的跳跃次数完成我的任务。”

“如果你不能满足我的上面两个要求，所有平台就会消失，你将会掉入下面的岩浆之中。”

现在，$\mathrm{Sunny}$ 想知道他是否可能逃出这个地方。

如果不行，输出```-1```，否则输出他最少所需的跳跃次数。

因为 $\mathrm{Sunny}$ 觉得死亡之地实在是太有趣了，所以他决定多玩几次，**多组数据**。

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

接下来 $2\times T$ 行，共 $T$ 组数据：

第 $2\times i-1$ 行，两个整数 $n,k$，$k$ 代表该组数据 $a_j$ 的个数。

第 $2\times i$ 行，$k$ 个数，第 $j$ 个数表示 $a_j$。

outputFormat: $T$ 行，第 $i$ 行表示第 $i$ 组数据的输出。

hint:
---

### 样例说明

第一组数据：

$\mathrm{Sunny}$ 每次只能顺时针跳 $5$ 个平台，易知不可能完成。

第二组数据：

$\mathrm{Sunny}$ 每次只能顺时针跳 $3$ 个平台，跳 $5$ 次即可。

---

### 数据范围与约定

$0\leq k\leq n\leq 10^6,1\leq n$。

保证 $\sum{n_i}\leq 3*10^6,a_j\leq n$，且**互不相同**。

测试点 $1:5\%,n=1$。

测试点 $2:5\%,n\leq5$。

测试点 $3:10\%,n\leq15$。

测试点 $4:15\%,n\leq300$。

测试点 $5:25\%,n\leq5000$。

测试点 $6:40\%,n\leq10^6$。

---

梦醒了……


title: [YsOI2020] 植树

background: Ysuperman 响应号召，决定在幼儿园里植树。

description:
Ysuperman 有一棵 $n$ 个节点的无根树 $T$。如果你不知道树是什么，TA 很乐意告诉你，树是一个没有环的无向联通图。

既然树是无根的，那就没有办法种植。Ysuperman 研究了很久的园艺，发现一个节点如果可以成为根，它必须十分平衡，这意味着以它为根时，与它**直接相连的节点，他们的子树大小都相同**。

你作为幼儿园信息组一把手，Ysuperman 给你一棵树，你能在 $1s$ 内找到所有可能成为根的节点吗？

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

此后 $n-1$ 行，每行两个正整数 $u_i,v_i$，表示树上有一条直接连接 $u_i,v_i$ 的边。保证每条边只会给出一次。

outputFormat: 不超过 $n$ 个从小到大的整数，用空格隔开，表示每一个可能成为根的节点。

hint:
### 样例说明

#### 样例说明 $1$。

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

以 $1$ 为根时，与 $1$ 直接相连的点有 $\{2\}$，因为只有一个所以大小全部相同。

以 $2$ 为根时，与 $2$ 直接相连的点有 $\{1\}$，因为只有一个所以大小全部相同。

所以答案为 $1,2$。

#### 样例说明 $2$

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

以 $1$ 为根时，与 $1$ 直接相连的点有 $\{2\}$，因为只有一个所以大小全部相同。

以 $2$ 为根时，与 $2$ 直接相连的点有 $\{1,3\}$，子树大小分别为 $\{1,2\}$，不相同。

以 $3$ 为根时，与 $3$ 直接相连的点有 $\{2,4\}$，子树大小分别为 $\{2,1\}$，不相同。

以 $4$ 为根时，与 $4$ 直接相连的点有 $\{3\}$，因为只有一个所以大小全部相同。

所以答案为 $1,4$。

----

### 数据范围

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

| $\rm{subtask}$ | $n$ |  分数|
| :-----------: | :-----------: | :----: |
| $1$ | $\le 5000$ | $40$ |
| $2$ | $\le 10^6$ | $60$ |

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

------

### 提示

由于输入输出量较大，你可能需要快速输入/输出。


title: 【AFOI-19】区间与除法

background:
SY 好不容易才解出QM给她的数学题，在恰午饭的时候，QM 向她的脑洞里塞了个幻想的泡泡……SY 戳开一看，又是长长的一串数字!

SY 实在是不想思考了，她决定用小学的除法消灭她脑洞里的数字.

description:
定义 $op$ 操作意义为将当前数除以 $d$ 并向下取整.

SY 现在有 $m$ 个“原数”，若一个数经过若干次 $op$ 操作(包括 $0$ 次)后能变为这个“原数”，那么这个数是可以被这个“原数”所消灭的。注意，“原数”是不会被消耗的.

现在 SY 想问你,对于一个区间 $[l,r]$，在消灭最多个数的前提下最少需要多少个“原数”？

inputFormat:
第一行 $4$ 个数,分别是 $n,m,d,q$,分别表示数列 $\{a\}$ 元素个数，SY 拥有的 “原数” 个数，$op$ 操作参数，询问个数。

第二行为 $\{a\}$ 数列，即需要被消灭的数列。

第三行为 $m$ 个“原数”。

接下来 $q$ 行，每行两个数 $l$ 和 $r$，表示询问区间为 $[l,r]$。

outputFormat: 按照询问顺序，每一行输出一个整数表示答案.

hint:
#### 样例解释：

**#样例1** ： $20$ 经过一次 $op$ 操作（除以 $3$ 向下取整）可以变成 $6$，而 $0$ 不能经过若干次 $op$ 操作变成 $6$ 。

所以区间 $[1,1]$ 最多消灭 $0$ 个数，消灭最多数前提下最少需要 $0$ 个 "原数"，区间 $[1,2],[2,2]$ 最多消灭 $1$ 个数，消灭最多数前提下最少需要 $1$ 个 "原数" 。

**#样例2** ： $2$ 能消灭 $\{6,19,7\}$ ， $5$ 能消灭 $\{5,15\}$ ， $10$ 能消灭 $\{10\}$ ， 所以区间 $[1,6],[1,4]$ 最少能用所有 "原数" 全部消灭，区间 $[4,6]$ 能用 $2,5$ 全部消灭。

#### 数据范围：

对于 $30\%$ 的数据：$n\le100,m\leq10, d=2, q\le 10$

对于 $100\%$ 的数据：$n\le5\times 10^{5},m\leq60,2\leq d\leq10,q\le10^{6},0\le a_i,b_i\le 2^{63}$

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

特殊性质：数据经过构造。


title: [SDOI2018] 原题识别-改

background: 蒟蒻$\color{grey}{\text{suwakow}}$花了三天时间，研究出了[这道题](https://www.luogu.org/problem/P4618)的**线性空间**，且不依赖输入的随机性的一种优（du）秀（liu）做法。于是她决定拿出来毒瘤一下大家。

description:
有一棵$n$个点的有根树，根节点编号为$1$，且编号为$i$的节点有颜色$a_i$。你需要支持$m$次询问。询问有以下两种格式：

- $1~x~y$：询问树上编号为$x$的节点到编号为$y$的节点的最短路径中，不同的颜色有多少种。

- $2~a~b$：在节点$a$到根节点的路径中随机选择一个点$x$，在节点$b$到根节点的路径中随机选择一个点$y$，求询问 $1~x~y$ 的答案期望。（路径包含$a$, $b$和根节点）

对于询问$2$，设答案为$\mathrm{ans}$，$a$到根节点的路径经过的点数为$\mathrm{cnt_a}$，$b$到根节点的路径经过的点数为$\mathrm{cnt_b}$，你只需要输出$\mathrm{ans}\cdot \mathrm{cnt_a}\cdot \mathrm{cnt_b}$。

inputFormat:
**注意：输入格式与原题不同**

每个测试点仅包含一组数据。

输入数据的第一行包含两个非负整数$n$, $m$，表示节点个数和询问次数。

接下来一行包含$n$个正整数，第$i$个正整数为$a_i$，表示节点$i$的颜色。

接下来$n-1$行，每行包含两个整数$u$, $v$，表示编号为$u$的节点和编号为$v$的节点之间存在一条边。保证输入的边构成一棵树。

接下来$m$行，每行包含一个询问。询问的格式和意义见题目描述。

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

hint:
对于所有数据，保证$1\leq a_1, a_2, \ldots, a_n\leq n\leq 10^5$, $1\leq m\leq 2\times 10^5$。保证输入的边构成一棵树。

子任务$1$（$30$分）：保证不存在询问$2$。

子任务$2$（$30$分）：保证对于每一条边都有$v=u+1$。

子任务$3$（$40$分）：没有任何附加的限制。


title: 炉心融解

background: 2020-2021 国家集训队自选题

description:
你叫了 $n$ 个人来玩游戏。$n$ 个人从 $0$ 到 $n-1$ 编号，按顺序坐成一圈，$0$ 号与 $n-1$ 号相邻。

你给这 $n$ 个人每人发了一张写着数字 $\texttt{0}$ 或 $\texttt{1}$ 的卡片。每个人都可以看到**除了相邻的两个人以外**所有人的卡片数字，也可以看到自己的。

游戏共进行 $m$ 回合。第 $i$ 回合你会向所有人公布 $k_i$ 条信息，信息的格式都是“某个集合里存在某种数字的卡片”。公布完之后：

- 如果某个人手里的卡片写着 $\texttt 0$，且他可以通过推断确定相邻的两个人卡片数字**逻辑或**的值，他就必须大喊“Meltdown！”。
- 如果某个人手里的卡片写着 $\texttt 1$，且他可以通过推断确定相邻的两个人卡片数字**逻辑异或**的值，他就必须大喊“Meltdown！”。

所有人都清楚游戏规则，且都有极强的推断能力，只要依据他已有的信息能够推断出来他就必须要喊。喊话是所有人同时喊，不可以听别人喊完了再继续推断。然后本回合结束，进入下一回合。

除此之外这 $n$ 个人没有任何信息交流。现在给出每个人的卡片数字和你公布的所有信息，求每个人第一次喊出“Meltdown！”是在第几回合。

inputFormat:
输入的第一行包括两个正整数 $n,m$，表示人数和回合数。第二行 $n$ 个整数，分别表示编号 $0$ 到 $n-1$ 的人的卡片上的数字。接下来包括 $m$ 个部分，第 $i$ 部分描述了第 $i$ 回合你公布的信息。

第 $i$ 部分的第一行包括一个非负整数 $k_i$，表示第 $i$ 回合公布的信息条数。接下来 $k_i$ 行，每行第一个正整数 $p$，表示集合的人数，接下来 $p$ 个互不相同的整数表示集合里所有人的编号。最后一个整数 $c$，表示这个集合里存在数字为 $c$ 的卡片。数据保证这些信息是正确的。

outputFormat: 输出包括一行 $n$ 个整数，分别表示编号 $0$ 到 $n-1$ 的人第一次喊出“Meltdown！”时的回合数。如果他自始自终都没有喊“Meltdown！”，这个数输出 $-1$。


title: 「SWTR-2」Magical Gates

background:
小 $\mathrm{A}$ 找到了一张藏宝图。

他顺着藏宝图上的路线来到了一扇古老的大门前，门上有六芒星的图案。

他把手轻轻地放在六芒星上……

霎时间，六芒星光芒大放，四周亮如白昼。

（新增一组大样例）

description:
小 $\mathrm{A}$ 面前出现了 $10^{1000}$ 扇门，每个门上都写着它自己的编号，分别为 $1,2,3,\dots,10^{1000}$。

这时，守门人小 $\mathrm{M}$  向小 $\mathrm{A}$ 走来。

“这些门，并不普通，它有魔力。”

“我会给你一些区间 $l,r$，请你求出区间 $[l,r]$ 里所有门的魔力值之**和**与魔力值之**积**。”

“因为结果可能很大，请你将结果 $mod\ p$。 ”

“如果你正确地回答了所有询问，你将会拥有这扇门后的所有宝藏。”

“哦，对了，一扇门的魔力值就是其在二进制下 $1$ 的个数。”

简单来说，记第 $i$ 扇门的魔力值为 $d_i$，给定的区间为 $[l,r]$，请求出：

$$\sum_{l}^{r}d_i\bmod\ p \quad \prod_{l}^{r}d_i\bmod\ p$$

由于门的数量实在太多，小 $\mathrm{A}$ 决定向你请求帮助。

inputFormat:
第一行三个正整数 $T,p,n$（$n$ 会在数据范围中说明）。

接下来 $T$ 行，第 $i$ 行两个**正整数** $l_i,r_i$。

outputFormat:
输出 $T$ 行，每行 $2$ 个数，由空格隔开，第 $i$ 行分别为：

$$\sum_{l}^{r}d_i\bmod\ p \quad \prod_{l}^{r}d_i\bmod\ p$$

hint:
---

### 样例说明

数据 $1$：

$$\sum_{3}^{7}d_i=2+1+2+2+3=10$$

$$\prod_{3}^{7}d_i=2\times 1\times 2\times 2\times 3=24$$

数据 $2$：

$$\sum_{1}^{10}d_i=1+1+2+1+2+2+3+1+2+2=17$$

$$\prod_{1}^{10}d_i=1\times 1\times 2\times 1\times 2\times 2\times 3\times 1\times 2\times 2=96$$

---

### 数据范围与约定

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

为了方便拿部分分，输入格式中的 $n$ 为**该测试点的编号**。

所有具有特殊性质的测试点一共 $31\%$。

对于 $100\%$ 的数据，有 $1\leq n\leq 27,1\leq T \leq 10,10^9 \leq p \leq 1.001\times 10^9,1\leq l\leq r\leq 10^{1000}$，**保证 $p$ 为质数**。

---

对于测试点 $1-20$，时限 $300ms$，剩下的 $7$ 个测试点时限 $2s$。

对于所有测试点，空间限制 $256MB$

---

“吱嘎”一声，封尘千年的大门缓缓打开。

刺眼的金光照了出来……


title: 小猪佩奇玩游戏

description:
佩奇和乔治玩游♂戏。

佩奇在黑板上写下数字 $\{1,2,\cdots,n\}$ ，每次他们会等概率地报出黑板上的一个数字 $x$ ,并删除所有 $x$ 的正整数次幂。

形式化地,给定数列 $\{1,2,\cdots,n\}$ ，每次等概率选出数列中存在的 $1$ 个数字 $x$ ，并将形如 $\{x^k,k \in Z^{+}\}$ 的数字删除。

他们玩了整整一个下午，游戏还是没有结束，所以他们想知道，该游戏期望在多少轮后会结束。

如果你的答案与正确答案的绝对误差在 $10^{-4} $以内，则被判定为正确。

inputFormat:
第一行 $1$ 个正整数 $t$,表示佩奇和乔治打算玩 $t$ 轮游戏。

之后 $t$ 行,每行 $1$ 个正整数 $n$,表示佩奇在黑板上写下了数字 $\{1,2,\cdots,n\}$ 并将进行游戏。

outputFormat:
一共 $t$ 行，每行 $1$ 个小数,表示答案，答案保留小数。

如果你的答案与正确答案的绝对误差在 $10^{-4}$以内，则被判定为正确。


title: 打字练习

description:
R 君在练习打字。

有这样一个打字练习网站，给定一个范文和输入框，会根据你的输入计算准确率和打字速度。可以输入的字符有小写字母、空格和 `.`（英文句号），输入字符后，光标也会跟着移动。

输入的文本有多行，R 君可以通过换行键来换行，换行后光标移动到下一行的开头。

R 君也可以按退格键（为了方便，退格键用 `<` 表示），以删除上一个打的字符，并将光标回移一格。特殊的，如果此时光标已经在一行的开头，则不能继续退格（即忽略此时输入的退格键）。

网站的比较方式遵循以下两个原则：

- 逐行比较，即对于范文和输入的每一行依次比较，不同行之间不会产生影响，多余的行会被忽略。
- 逐位比较，即对于两行的每一个字符依次比较，当且仅当字符相同时才会被算作一次正确，否则会被算作错误。计算答案时，只统计相同的字符个数。

需要注意的是，回车键不会被计入正确的字符个数。

R 君看到网站上显示他花了 $T$ 秒完成了这次的打字游戏，请你计算出他的 KPM（Keys per minutes，每分钟输入的字符个数），答案四舍五入保留整数部分。

inputFormat:
R 君会依次告诉你网站的范文，他的输入和花费的时间。

其中范文和输入将会这样读入：给定若干行字符串，以单独的一行 `EOF` 结束，其中 `EOF` 不算入输入的文本。

最后一行一个整数 $T$，表示他打字花费了 $T$ 秒。

可以参考样例输入输出文件和样例解释辅助理解。

outputFormat: 一行一个整数，表示 KPM。

samples:
hello world.
aaabbbb
x
EOF
heelo world.
aaacbbbb
y<x
EOF
60

hint:
#### 样例解释

第一行的正确字符数为 11。
第二行的正确字符数为 6，错误的字符 `c` 仍会占据一个位置。
第三行的正确字符数为 1，R 君使用退格键删除了被打错的字符 `y`

#### 数据范围

对于 $20\%$ 的数据，不存在换行键。
对于 $40\%$ 的数据，不存在退格键。
对于 $100\%$ 的数据，$T \leq 10^3$，保证每个文本段的总字符数（包括换行）不超过 $10^5$ 个且总行数不超过 $10^4$。


title: 赛车游戏

description:
R 君和小伙伴打算一起玩赛车。但他们被老司机 mocania 骗去了秋名山。

秋名山上有 $n$ 个点和 $m$ 条边，R 君和他的小伙伴要从点 $1$ 出发开往点 $n$，每条边都有一个初始的方向。老司机 mocania 拿到了秋名山的地图但却不知道每条路有多长。显然，为了赛车游戏的公平，每条 $1$ 到 $n$ 的路径应当是等长的。mocania 想，我就随便给边标上一个 $1...9$ 的长度，反正傻傻的 R 君也看不出来。

可 mocania 的数学不大好，不知道怎么给边标长度，只能跑来请教你这个 OI 高手了。

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

接下来 $m$ 行，每行两个整数 $u,v$，表示一条从 $u$ 到 $v$ 的有向边。

outputFormat:
如果无解或者不存在 $1$ 到 $n$ 的路径直接输出一个 $-1$。

如果有解第一行输出两个数 $n,m$，和输入文件中给出的相同。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示把从 $u$ 到 $v$ 的路径的长度设置为 $w$，其中 $w$ 是一个 $1\sim 9$ 的整数。要求所有边的出现顺序和题目中给出的相同。

hint:
#### 数据范围

**本题启用 Special Judge 和 Subtask。**

Subtask #1（$30$ 分）：$n \leq 10$，$m \leq 20$；
Subtask #2（$30$ 分）：$n \leq 100$，$m \leq 200$；
Subtask #3（$40$ 分）：$n \leq 1000$，$m \leq 2000$。

保证数据中不会出现重边，自环。


title: 小猪佩奇学数学

description:
佩奇和乔治在学数♂学。

给定 $n,p,k$,询问
$$
\sum_{i=0}^n \binom n i \times p^{i} \times \left\lfloor \frac{i}{k} \right\rfloor \bmod 998244353
$$

inputFormat: $3$ 个正整数,分别表示 $n,p,k$。

outputFormat: $1$ 个正整数,表示答案。

hint:
对于 $20\%$ 的数据，$1 \leq n \leq 10^6$

对于另外 $40\%$ 的数据，$k \in \{2^w|0 \leq w \leq 10\}$

对于 $100\%$ 的数据，$1 \leq n,p <998244353,k \in \{2^{w}|0 \leq w \leq 20\}$

### 出题人善意的提醒

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


title: 小猪佩奇爬树

description:
佩奇和乔治在爬♂树。

给定 $n$ 个节点的树 $T(V,E)$，第 $i$ 个节点的颜色为 $w_i$，保证有$1 \leq w_i \leq n$。

对于$1 \leq i \leq n$，分别输出有多少对点对 $(u,v)$，满足 $u<v$，且恰好经过**所有**颜色为 $i$ 的节点，对于节点颜色不为 $i$ 的其他节点，经过或不经过均可。

树上路径 $(u,v)$ 定义为序列 $\{f\}$，满足 $f_1=u,f_{|f|}=v$，且 $\forall 1 \leq i < |f|$，$T$ 中均存在边 $(f_i,f_{i+1})$，且 $\{f\}$ 中无重复元素，能够证明对于任意点对 $(u,v)$，其树上路径唯一。

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

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

之后 $n-1$ 行，每行 $2$ 个正整数 $u,v$，表示 $T$ 中存在边 $(u,v)$。

outputFormat: 共 $n$ 行，每行 $1$ 个正整数，第 $i$ 行输出包含所有颜色为 $i$ 的节点的路径个数。


title: 【AFOI-19】sum与prod

background:
SY终于整理好了她凌乱的被子，刚来到教室的她就收到了QM传来的一张字条。。。

To: Dear SY

    你看看我昨晚梦到的式子，解出来给你糖吃。

From: Your QM。

SY自然是无法拒绝 $C_{6}H_{12}O_{6}$ 的诱惑啦，不过她看到字条背面花里胡哨的式子时傻眼了。。但是SY还是很想吃糖。

description:
求

$$\sum_{i=1}^{2^{n}}\log_{2}{(\prod_{j = 1}^{i}lowbit(j))}$$

的结果

其中 $lowbit(x)$ 意指` x&(~x+1)` 的结果。

inputFormat: 一行，一个整数n。

outputFormat: 一行，一个整数，为答案模 $10^9+7$ 的结果。

hint:
对于前 $20\%$ 的数据，有 $1 \leq n \leq 60$ 。

对于前 $50\%$ 的数据，有 $1 \leq n \leq 10^4$ 。

对于前 $100\%$ 的数据，有 $1 \leq n \leq 2^{62}$ 。


title: 美德的讲坛

description:
```
现在我很清楚地懂得了，以前人们寻求美德的教师时首先在寻求着什么。
人们在寻求安睡与促进安睡的罂粟花！
```

查拉图斯特拉在讲坛前听智者讲论睡眠的美德。他感到很无聊，于是观察一同听讲的少年们。

他发现少年们的衣着非常奇特。具体地说，少年们的衣着有 $60$ 种特点，第 $i$ 种特点的特征值为 $2^{i-1}$ 。

他每次会观察两个少年，如果有一种衣着特点只出现在一个少年身上，而不在另一个少年身上，查拉图斯特拉就会强迫症发作，并得到等同于该特点特征值的厌恶度。

他想要把少年们站成若干组，使得在每组中，不管他选哪两个少年，都会得到 $<x$ 点厌恶度。查拉图斯特拉称这样的组是好的。

他有时也会使一个少年自成一组，此时不管怎样这个组都是好的。

他想要知道，这样满足条件的组最多可以包含几个少年呢？

有时少年也会回家换衣服，回来时衣着特点会有所改变。

inputFormat:
输入数据第一行包括三个整数 $n,q,x$，表示少年的人数，少年回家换衣服的次数和阈值。

接下来一行 $n$ 个整数 $a_1,a_2,\dots,a_n$，$a_i$ 表示初始时第 $i$ 个少年衣着特点的特征值之和。

接下来 $q$ 行，每行两个整数 $ind,val$，表示编号为 $ind$ 的少年刚回家换衣服回来，衣着特点的特征值之和改为 $val$ 。

outputFormat:
输出 $q+1$ 行，每行一个非负整数。

第 $i$ 行的数表示第 $i$ 次修改之前的答案。

第 $q+1$ 行的数表示全部修改完以后的答案。


title: 【L&K R-03】射击场决战

description:
【如果不想看题面请阅读分割线以下部分】

小 L 与小 K 是两个帮派的首领，也是死敌。某年某月，两个帮派发生了大规模的冲突。小 K 因为实力不敌，被小 L 的爪牙团团包围，最终被逼近了一个大型射击场。小 K 自知大势已去，正准备与小 L 拼死一战时，却传来消息，说小 L 要邀请自己与他来玩一场游戏。小 K 知道其中有鬼，但却别无它计，只能只身前往小 L 指定的会面点。

会面点在射击场旁。小 L 站在场上，满脸笑容地对走来的小 K 招手。“啊，小 K ，好久不见。我记得上次我们见面的时候，还是在那个小酒馆。当时，我与你谈笑风生，指点江山，不亦乐乎。没想到，如今，我们竟到此地步啊！”小 L 顿了顿，继续说道：“你是我曾经的兄弟，我不想以暴力的方式了解你我。正好，我有一个好方法：不如我们用游戏的方式来场决战吧！这样如何，小 K ？”小 K 知道，自己并没有否定小 L 的余地。于是，小 K 点了点头。小 L 看到小 K 点头，又露出了笑容，开始讲起了游戏的规则。

“如你所见，我们的游戏要在这片射击场上进行。射击场总共有 $n$ 行 $m$  列，共 $n\times m$ 个靶。为了方便，取行的方向为左右，列的方向为前后。这个射击场有一个特点：每个靶上都有一个计数器。击中一个靶，这个靶的计数器示数就会加一。但是，每个靶的示数有一个范围，只能是不小于 $0$，不大于 $k$ 的整数。倘若击中一个靶，而在未击中此靶前此靶计数器的示数已经为 $k$，那么击中时，此靶计数器示数就会溢出清 $0$，并产生溢出错误的信号，经电线开始传递。由于靶场电线的特殊布置，信号只会往右侧传递。信号传递过程中会影响若干其它同行靶的计数器。如果这些被影响到的靶计数器示数为 $k$，其同样会溢出清 $0$ 并产生溢出错误信号，与之前的信号叠加（但加一效果不会叠加）；否则，其示数会加一，并发出纠正讯息，截断信号传播，即在其右侧的靶不会继续被信号影响。当然，如果信号一直传递而未被截断，那么它最终会传入信息管理终端。由于信号在传递过程中不断叠加，再加之信息管理终端要处理庞大的信息，纠正错误信号的能力较差，可能会导致终端死机甚至发生爆炸的危险，这是违规的。

“我与你会轮流选择其中一个靶进行一次射击，射击哪个靶由射击者自行决定。如果轮到某个人射击，但他无法进行不违规的射击，那么他就输了。因为这是我设计的游戏，先手当然是我。但是，我也会给你一些选择。靶场上每个靶计数器的初始示数不一定为 $0$，是可以被我设置的。我这里恰好有几种设置方案，但我不知道该选哪种好，可否请你帮我选一选？”

小 L 从口袋里抽出了几张纸条。小 K 一看，每张纸条却没有写每个靶计数器的初始示数，只写着三个数字 $a,b,c$。小 L 所不知道的是，小 K 有着惊人的观察能力，在小 L 讲刚才那一番话之时，小 K 就已经通过分析靶上示数的变化以及电路的布置，得出了计数器初始示数生成的规律。靶场上靶的计数器初始示数是一个个按顺序生成的。并且，生成的顺序是按行优先，从左到右，从上到下。具体来说，是按照第 $1$ 行第 $1,2,\ldots ,m$ 个，第 $2$ 行第 $1,2,\ldots ,m$ 个，……，第 $n$ 行第 $1,2,\ldots ,m$ 个的顺序生成。生成一个计数器的示数需要用到 $a,b,c$ 作为参数。并且，每生成一个计数器的示数，$a,b,c$ 都会产生变化。具体来说，每生成一个计数器的示数，便引用一次以下的函数：

```
typedef unsigned long long ull;
inline ull generate(ull&a,ull&b,ull&c,ull&k)
{
	a<<=19;a+=b+c;
	a<<=26;a^=c+=a+81;b--;
	a<<=7;a>>=(b^c^1145)&14;
	c*=a;a|=b+=c;a^=b&c;
	return a%(k+1);
}
```

函数的返回值即为生成的计数器示数。容易发现，初始示数均为不小于 $0$，不大于 $k$ 的整数，不违反规则。

小 K 知道小 L 是绝顶聪明的人，且一定会以自己的胜利为目标进行游戏。当然，小 K 因为掌握了许多这个游戏的信息，水平不会落后于小 L。小 K 不能违反小 L 制定的规则，否则可能惹恼小 L，使冲突再次爆发。但是，小 K 可以通过计算，得出小 L 给出的方案中哪些是小 L 必胜，哪些是自己必胜的，并选择一个自己必胜的方案进行游戏。

可惜时间不允许小 K 做太长时间的计算。恰好，会编程的你可以帮助小 K 在较短的时间内得出结果。请你帮小 K 算算，在小 L 给出的所有方案中，哪些小 L 必胜，哪些小 L 必败。

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

考虑到小 L 说的话可能太长以至于难以理解，小 K 决定更为简洁地叙述这个问题。小 L 提供了一个 $n$ 行 $m$ 列的数阵。小 L 与小 K 二人轮流操作，每次可以将数阵中的某个数加上 $1$。若加 $1$ 后此数大于 $k$，则此数清零，将加 $1$ 操作传递给其右侧的数。若某个数需要传递操作，但其右侧没有数，则这个操作对应的人的初始操作将不可进行。最后无法操作的人败。小 L 为先手，二人都绝顶聪明。若小 L 会赢则输出 `YES`，否则输出 `NO`。

数阵里初始的数由小 L 提供。小 L 提供了若干个填充数阵的方案，每个方案中数阵里的数由上文的函数生成，生成顺序从左到右，从上到下。方案的互异性体现在参数 $a,b,c$ 的不同。请你对每种方案给出答案。 **保证生成方式与题目的正确解法无关。** 注意对于每种方案，小 L 实际上提供了六个参数 $k,n,m,a,b,c$，即 $k,n,m$ 在每种方案中也可能各不相同。

inputFormat:
第一行为小 L 给出方案总数。

对于每种方案，按顺序给出六个参数：$k,n,m,a,b,c$，其意义如题所示。

outputFormat: 对于每种方案，如果小 L 会赢，输出 `YES`，否则输出 `NO`。


title: 餐馆

background: 小 W 家新开了一家餐馆。

description:
这家餐馆提供 $n$ 种特色菜，它们被标号为 $1,2,\cdots,n$。

有一天，餐馆里来了 $k$ 个客人，他们没有想好要吃什么。于是，小 W 给他们出了个主意：每个人先从 $1,2,\cdots,n$ 中等概率随机一个数 $r$，再从
 $1,2,\cdots,r$ 中等概率随机一个数 $l$，这个人就点标号在 $l$ 和 $r$ 之间（包括 $l$ 和 $r$）的菜。

于是，客人们按小 W 说的做了。在所有客人都点完单之后，小 W 突然发现：没有两个人都点了相同的一道菜，他每种菜至多做一份就够了！为了证明他是多么的欧皇，他找到了学编程的你，请你帮他计算这种情况发生的概率。

inputFormat: 两个整数 $n$ 和 $k$，意义如题目描述。

outputFormat: 一个整数 $p$，表示所求概率对 $10^9+7$ 取模后的结果。

hint:
样例解释：
样例 $1$ 解释：因为只有一位客人，所以无论如何不会有两个人点同样的菜，故所求概率为 $1$。

样例 $2$ 解释：每位客人只点 $1$ 号菜的概率为 $\dfrac12$，只点 $2$ 号菜的概率为 $\dfrac14$，两个菜都点的概率为 $\dfrac14$，两人不点同一道菜即一人只点 $1$ 号菜，一人只点 $2$ 号菜，概率为
 $\dfrac14\times\dfrac12+\dfrac12\times\dfrac14=\dfrac14$，模 $10^9+7$ 意义下为
 $250000002$。
*********

提示：如果你不知道如何对有理数取余，请看 [P2613](https://www.luogu.com.cn/problem/P2613)。

********
数据范围：
对于 $10\%$ 的数据， $k=1$。
对于另外 $10\%$ 的数据， $1\le k\le n\le5$。
对于另外 $20\%$ 的数据， $1\le k\le3$。
对于另外 $30\%$ 的数据， $1\le k\le n\le10^3$。
对于所有数据， $1\le k\le n\le 10^8$。


title: [MtOI2019] 膜Siyuan

background:
你强归你强，$\mathsf S\mathsf{\color{red} iyuan}$ 比你强。——$\mathsf S \mathsf{\color{red} iyuan}$

disangan233 最近发现了一款 OIer 们的游戏：[膜 $\color{black} \mathsf S \mathsf{\color{red} iyuan}$](https://lmoliver.github.io/mosiyuan/index.html)。

他被里面的「真理 IV」所困惑，于是他找到了你寻求帮助。

description:
给你 $1$ 个正整数 $M$，$n(n\leq 5)$ 个正整数 $3$ 元组 $\{a_i,b_i,c_i\}(a_i,b_i,c_i\leq M\leq 2000)$，请你求出所有满足

$$
\forall i\leq n ,s.t.~|a_i-x|\oplus |b_i-y|\oplus |c_i-z| = 9
$$

的**有序**正整数 $3$ 元组 $\{x,y,z\}(x,y,z \leq M)$的个数。

其中，$\forall$ 表示 "对于所有"，$s.t.$ 表示 "使得"，$A \oplus B \oplus C$ 表示 $A,B,C$ 的异或和。

对于 C++，`A^B^C` 或 `A xor B xor C` 即为 $A \oplus B \oplus C$ 的答案 。

这里提供一份模板：

```cpp
if ((a ^ b ^ c) == 9)
{
	Your code here...
}
```

对于 $2$ 个有序 $3$ 元组 $A,B$，如果 $x_A \not =x_B$ 或 $y_A \not =y_B$ 或 $z_A \not =z_B$，$A,B$ 即被视为是不同的。

inputFormat:
共 $n+1$ 行。

第 $1$ 行输入 $2$ 个正整数 $n$，$M$。

接下来 $n$ 行第 $i$ 行输入 $3$ 个正整数 $a_i,b_i,c_i$。

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

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

所有满足条件的 $\{x,y,z\}$ 有：

$\{88,88,120\}$，$\{88,104,104\}$，$\{120,120,120\}$ 和 $\{120,136,104\}$。

共 $4$ 个。

### 子任务

对于 $10\%$ 的数据，保证与样例完全一致。

对于 $60\%$ 的数据，保证 $M\leq 200$。

对于所有数据，保证 $a_i,b_i,c_i\leq M\leq 2000$，$n\leq 5$。

### 题目来源

[MtOI2019 Extra Round](https://www.luogu.org/contest/22614) T2

出题人：disangan233

验题人：Studying Father


title: [SDOI2008] 红黑树

description:
红黑树是一类特殊的二叉搜索树，其中每个结点被染成红色或黑色。若将二叉搜索树结点中的空指针看作是指向一个空结点，则称这类空结点为二叉搜索树的前端结点。并规定所有前端结点的高度为 $-1$。

一棵红黑树是满足下面“红黑性质”的染色二叉搜索树：

1. 每个结点被染成红色或黑色；
2. 每个前端结点为黑色结点；
3. 任一红结点的子结点均为黑结点；
4. 在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。

从红黑树中任一结点 $x$ 出发（不包括结点 $x$），到达一个前端结点的任意一条路径上的黑结点个数称为结点 $x$ 的黑高度，记作 $bh(x)$ 。红黑树的黑高度定义为其根结点的黑高度。

给定正整数 $N$，试设计一个算法，计算出在所有含有 $N$ 个结点的红黑树中，红色内结点个数的最小值和最大值。

inputFormat: 输入一个数字 $N$。

outputFormat: 输出第一行为红色内节点的个数最小值；第二行为红色内节点的个数最大值。


title: [SDOI2008] 立方体覆盖

description:
A 君近日为准备省队选拔，特意进行了数据结构的专项训练。训练过程中就遇到了“矩形面积并”这道经典问题，即：给出 $N$ 个各边与坐标轴平行（垂直）的矩形，求矩形覆盖的面积之和。A 君按纵坐标建立线段树后按横坐标扫描计算，轻易 AC 了这道题，时间复杂度为 $O(N\log N)$。

为了强化训练，A 君将问题推广到三维空间中，即：给出 $N$ 个各棱与坐标轴平行（垂直）的立方体，求立方体覆盖的体积之和。为了简化问题，令立方体均退化为正立方体，用四元组 $(x, y, z, r)$ 表示一个立方体，其中 $x, y, z$ 为立方体的中心点坐标，$r$ 为中心点到立方体各个面的距离（即立方体高的一半）。

这次可难住了 A 君，只好请你——未来的金牌——来帮助他了。

inputFormat:
第一行是一个正整数 $N$。

以下 $N$ 行每行四个整数 $x, y, z, r$。

outputFormat: 输出覆盖的总体积。


title: [SDOI2008] 校门外的区间

description:
受校门外的树这道经典问题的启发，A君根据基本的离散数学的知识，抽象出 $5$ 种运算维护集合 $S$ （$S$ 初始为空）并最终输出 $S$。现在，请你完成这道校门外的树之难度增强版——校门外的区间。

五种运算如下：

- `U T`：$S = S \cup T$
- `I T`：$S = S \cap T$
- `D T`：$S = S - T$
- `C T`：$S = T - S$
- `S T`：$S = S \oplus T$

集合的基本运算操作定义如下：

- $A \cup B$：$\{x | x \in A \vee x \in B\}$
- $A \cap B$：$\{x | x \in A \wedge x \in B\}$
- $A - B$：$\{x | x \in A \wedge x \notin B\}$
- $A \oplus B$：$(A-B)\cup (B-A)$

inputFormat: 输入 $M$ 行。每行第一个字母描述操作类型，后面给出一个区间（区间用 `(a,b)`，`(a,b]`，`[a,b)`，`[a,b]` 表示）。

outputFormat:
输出一行若干区间，代表集合 $S$，**所有区间按递增顺序输出，相邻两个区间之间以一个空格隔开**。

如果区间为空，输出 `empty set`。


title: [SDOI2008] 石子合并

description:
在一个操场上摆放着一排 $N$ 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 $2$ 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法，计算出将 $N$ 堆石子合并成一堆的最小得分。

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

接下来 $N$ 行，第 $i$ 行一个整数 $a_i$，代表第 $i$ 堆石子的石子数。

outputFormat: 输出将所有石子合并为一堆的最小得分。

hint:
$ N \leq 40000, a_i \leq 200$

**请注意 $N$ 的范围（来自上传者的提示）**


title: 【模板】二元一次不定方程 (exgcd)

description:
给定不定方程

$$ax+by=c$$

若该方程无整数解，输出 $-1$。
若该方程有整数解，且有正整数解，则输出其**正整数**解的数量，所有**正整数**解中 $x$ 的最小值，所有**正整数**解中 $y$ 的最小值，所有**正整数**解中 $x$ 的最大值，以及所有**正整数**解中 $y$ 的最大值。
若方程有整数解，但没有正整数解，你需要输出所有**整数解**中 $x$ 的最小正整数值， $y$ 的最小正整数值。

正整数解即为 $x, y$ 均为正整数的解，$\boldsymbol{0}$ **不是正整数**。
整数解即为 $x,y$ 均为整数的解。
$x$ 的最小正整数值即所有 $x$ 为正整数的整数解中 $x$ 的最小值，$y$ 同理。

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

接下来 $T$ 行，每行三个由空格隔开的正整数 $a, b, c$。

outputFormat:
$T$ 行。

若该行对应的询问无整数解，一个数字 $-1$。
若该行对应的询问有整数解但无正整数解，包含 $2$ 个由空格隔开的数字，依次代表整数解中，$x$ 的最小正整数值，$y$ 的最小正整数值。
否则包含 $5$ 个由空格隔开的数字，依次代表正整数解的数量，正整数解中，$x$ 的最小值，$y$ 的最小值，$x$ 的最大值，$y$ 的最大值。

**读入输出量较大，注意使用较快的读入输出方式**

tags: 扩展欧几里德算法,exgcd


title: [NOI2012] 三重镇

background: 小西同学最近喜欢上了 iOS 游戏《三重镇 Triple Town》。游戏之余，小西也在思考如何才能在这个游戏中获得更高的分数。

description:
如下图所示，游戏在一个 $n \times m$ 的地图中进行。游戏给定一个**建造序列**，玩家按照此建造序列依次选择空白位置建造相应的建筑单位。建筑有九个不同的等级，由低到高分别为 `Grass`, `Bush`, `Tree`, `Hut` 等（为了方便描述，我们称之为 $L_1, L_2, L_3, \ldots , L_9$）。

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

当玩家在一个空白位置建造单位之后，有可能引起反应。反应的构成条件是：**从这个格子出发，与该建筑单位等级相同的格子所构成的连通块大小大于等于 $3$**， 则这个连通块将被合并为一个下一等级的建筑，此建筑的位置为最后建造的建筑单位位置，连通块中其他位置将变回空格。这里的连通块是指直接或者间接相邻的位置集合。

另外需要注意的是，**$L_9$ 为建筑的最高等级，所以多个 $L_9$ 的连通块并不会合并**。例如在下图中，当建造了中间的 $L_1$ 之后，与该位置相连的 $L_1$就被合并成了一个 $L_2$。

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

注意，在合并的过程中，可能会引起连环反应，如下图所示。

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

游戏的得分取决于玩家建造和反应生成的单位，建造或者反应生成建筑单位就可以获得相应的分数。不同等级建筑的得分表如下：

|建筑|$L_1$|$L_2$|$L_3$|$L_4$|$L_5$|$L_6$|$L_7$|$L_8$|$L_9$|
|:----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|
|得分|$4$|$20$|$100$|$500$|$1500$|$5000$|$20000$|$100000$|$500000$|

以刚才的两个游戏过程为例。图 2 中，首先建造了 $L_1$, 将得到 $4$ 分，随后， $L_1$ 进行了反应生成了 $L_2$, 此时再得到 $20$ 分。总共得分为 $24$。而在图 3 中，这一步操作得分为 $4+20+100+500=624$ 分。

为了降低游戏的难度，游戏中还设有两种道具，分别为“星星”和“炸弹”。在游戏开始时，玩家被给定 $p$ 个星星道具和 $q$ 个炸弹道具，玩家可以在任意时刻使用。两者功能如下：

- “星星”道具：可以放置在一个空格位置。当星星被放置时，星星会自动变为**能引起反应的最高等级建筑**。当在该位置不能引起任何反应时，星星变为 $L_1$。例如，在图 3 正中间位置放置星星，星星自动变为 $L_3$。星星的得分按照变化后的建筑计算得分。
- “炸弹”道具：炸弹道具可以放在在一个有建筑的位置上，作用为炸掉这个建筑并将该位置恢复为空格。当使用炸弹时，得分将扣除被炸掉的建筑的一半分数（即，得分为负数）。

在游戏的进行过程中，玩家必须按照给定的顺序进行建造，但可以随时穿插使用两种道具。游戏的目标是，通过合理的操作，取得最高的分数。

inputFormat:
**本题是一道提交答案题。**

对于每个数据，输入文件中第一行为两个整数 $n$，$m$, 表示地图一共包含 $n$ 行 $m$ 列。

接下来一行包含两个整数 $p$，$q$，分别表示道具星星和道具炸弹的数目。

接下来 $n$ 行包含一个 $n \times m$ 的初始地图。其中字符 `.` 表示空地，数字 $1\sim 9$ 分别表示相应等级的建筑。

再接下来一行包含一个数字 $k$，表示建造序列的长度。

最后一行包含 $k$ 个空格隔开的 $1\sim 9$ 之间的数字，表示建造序列的内容。

outputFormat:
针对给定的 $10$ 个输入文件 `tritown1.in` ~ `tritown10.in`，你需要分别提交你的输出文件 `tritown1.out` ~ `tritown10.out`。

输出文件包含玩家进行游戏的指令，共 $4$ 种指令：

|指令|含义|
|:--:|:----------:|
|`PUT x y`|将建造序列中的下一个单位放置到第 $x$ 行第 $y$ 列的空格中。
|`STAR x y`|放置星星道具到第$x$行第$y$列的空格中。|
|`BOMBER x y`|在第 $x$ 行第 $y$ 列放置炸弹，此位置必须非空。|
|`END`|游戏结束，结算当前得分。|

输出必须以 `END` 指令结尾，玩家可以在任意时刻结束游戏。

hint:
#### 样例解释

本样例对应下图：

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

第一步得分为 $4+20+100=124$；

第二步得分为 $100$；

第三步得分为 $100+500=600$；

游戏总得分 $124+100+600=824$ 分。

#### 评分标准

对于每组数据，我们设置了 $9$ 个评分参数 $a_{10}, a_9, …, a_2$，它们按此顺序每行一个放置在附加文件中的 `tritown1.ans` ~ `tritown10.ans` 内。如果选手的输出不合法，则得零分。否则，设在你的方案中，游戏得分为 $w_{user}$，你的分数将会由下表给出：

|得分|条件|得分|条件|
|:----:|:------:|:----:|:------:|
|10|$w_{user}\geq a_{10}$|5|$w_{user}\geq a_5$|
|9|$w_{user}\geq a_9$|4|$w_{user}\geq a_4$|
|8|$w_{user}\geq a_8$|3|$w_{user}\geq a_3$|
|7|$w_{user}\geq a_7$|2|$w_{user}\geq a_2$|
|6|$w_{user}\geq a_6$|1|$w_{user}>0$|

如果有多项满足，则取满足条件中的最高得分。

#### 附加文件

checker 需要自行编译后使用。

请前往 [Github](https://github.com/MikeMirzayanov/testlib) 下载 testlib.h 的最新源代码。


title: 【深基附B例】区间最大和

description: 给定 $n$ 个正整数组成的数列 $a_1, a_2, \cdots, a_n$ 和一个整数 $m$。求出这个数列中的一个子区间 $[i, j]$，也就是在这个数列中连续的数字 $a_i, a_{i + 1}, \cdots, a_{j - 1}, a_j$，使得这个子区间的和在不超过 $m$ 的情况下最大。如果有多个区间符合要求，请输出 $i$ 最小的那一个。

inputFormat:
输入共两行。

第一行，两个整数 $n, m$；

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

outputFormat: 一行，三个整数，表示符合题意的区间的左端点、右端点和累加和。