title: [WC2015] 未来程序

description:
在 2047 年，第 64 届全国青少年信息学奥林匹克冬令营前夕，B君找到了 2015 年，第 32 届冬令营的题目来练习。

他打开了第三题 “未来程序” 这道题目：

```
本题是一道提交答案题，一共 10 个测试点。
对于每个测试点，你会得到一段程序的源代码和这段程序的输入。你要运行这个程序，并保存这个程序的输出。
遗憾的是这些程序都效率极其低下，无法在比赛的 5 个小时内得到输出。
```
B君想了一下，决定用 2047 年的计算机来试着运行这个题目，他找到了 2015 年的编译器，并很快得到了结果……

这时B君从梦中惊醒，发现自己居然在第 32 届冬令营赛场上。之前的一切只是南柯一梦，而自己正需要解决“未来程序”这道题目。

然而B君已经记不清梦中的程序运行的结果了，他试图再次运行这些程序。但是他发现计算机性能比梦里的差多了，程序确实都无法在 5 小时内得到结果。

他需要你的帮助，来得到那些梦中的结果。

本题是一道提交答案题，一共有 10 个测试点。

对于每个测试点，你会得到一段程序的源代码和这段程序的输入。你要运行这个程序，并保存这个程序的输出。

遗憾的是这些程序效率都极其低下，无法在比赛的 5 小时内得到输出。

你需要帮助B君得到这些程序的输出。

inputFormat:
本题一共有 10 个测试点，编号为 1～10。以下用 “``*``” 表示测试点编号。

对于每个测试点有 4 个文件，分别是 program``*``.cpp 文件，program``*``.c 文件，program``*``.pas 文件，program``*``.in 文件。

你需要用自己的方法，得到以 program``*``.in 作为输入，编译运行 program``*``.{cpp, c, pas} 的输出。

你只需要在 3 种语言的代码中选择 1 种来解这道题目。这 3 种语言的代码在语意上是类似的，运行结果是相同的。

outputFormat:
对于给出的 10 个测试点，你需要将程序的输出分别保存在 program``*``.out 中。

特别地，我们保证每个测试点一定会输出恰好 10 行。

hint:
请下载输入数据。样例输入见 example.{in,cpp,c,pas}，样例输出见 example.ans。

**为了好写spj，略微修改评分规则**

每个测试点单独评分。

对于每行单独评分，如果该行与标准答案相同，可以得 1 分。

如果你的输出不足 10 行，我们会在你的输出末尾添加空行补齐 10 行。

如果你的输出超过 10 行，我们会取出你的前 10 行作为输出。


title: Sabbat of the witch

type: P

background:
您正在在游玩《魔女的夜宴》,突然开始思考一个哲学问题:这作的restart线到底算不算ntr？

![](http://0d077ef9e74d8.cdn.sohucs.com/rcLQDT4_png)

![](http://0d077ef9e74d8.cdn.sohucs.com/rcLQJyV_png)

![](http://0d077ef9e74d8.cdn.sohucs.com/rcLQMrk_png)
~~您在思索了很长时间之后,突然注意到这是个涉及到时间线和人格同一性的哲学问题~~

此时您突然发现galgame和数(毒)据(瘤)结(分)构(块)有一些奥妙重重的关系，为了更好的思考这个问题，您决定去写一道数(毒)据(瘤)结(分)构(块)题

description:
维护一个序列,支持以下三种操作

1.区间赋值

2.区间求和

3.撤回之前的一个区间赋值操作

**强制在线**

注意：这里的撤回操作既不会影响之前的操作也不会影响之后的操作，换句话讲撤回一个操作之后序列将会变成历史上从来没有过被撤回操作的状态

煮个栗子，假设我们对序列按顺序执行了1,2,3,4,5号操作

当我们撤回操作4的时候，整个序列应该和按顺序执行了1,2,3,5操作之后的序列一样

当我们接着撤回操作2的时候，整个序列应该和按顺序执行了1,3,5操作之后的序列一样

inputFormat:
第一行两个整数$n,m$表示序列长度和操作个数

第二行$n$个整数$a_{1}...a_{n}$其中$a_{i}$表示序列的第$i$项

接下来$m$行

如果这一行是$1,l,r,v$的话代表将$(l,r)$这段区间赋值成$v$,假如这个操作是第$k$次赋值操作，那么这个操作的编号就是$k$

如果这一行是$2,l,r$的话代表询问$(l,r)$这段区间中数字的和

如果这一行是$3,x$的话代表撤回编号为$x$的操作

**数据保证被撤回的操作一定存在并且每个操作只会被撤回一次**

为了体现题目的在线性，我们设lastans表示读入当前操作时最后一次询问的答案，(lastans的初始值为0)

那么对于操作1,你需要操作的真实区间是$(l \oplus lastans,r \oplus lastans)$

对于操作2,你需要询问的真实区间是$(l \oplus lastans,r \oplus lastans)$

对于操作3,你需要撤回的操作编号是$x \oplus lastans$

其中$\oplus$运算符表示异或运算

outputFormat:
对于每一个操作2输出一行一个整数，表示询问区间中的元素之和

为了方便你理解题意和调试，我们了准备两个样例，一个是强制在线的而另一个是非强制在线的(尽管本题没有非强制在线的部分分)

hint:
对于第9,10个测试点,满足$n,m \leq 10^4$，这两个测试点的分数都为1

对于剩余的测试点$n,m \leq 10^5$并且操作1的个数不超过$65000$

保证输入的数字全部小于$10^9$


title: 数学

background:
在```小奔```这片神奇的土地上，有一个毒瘤教练```小奔```。

题解：https://blog.csdn.net/kkkksc03/article/details/84928333

description:
小奔热衷于乘法，他最喜欢做的事情是：从一个有 $N$ 个元素的序列里取出 $K$ 个数，（注意：不能取同一个元素好几次，取不同但是值相同的元素则是允许的）
然后算出这$K$个数的积作为这个组合的分数。

小奔想试遍所有的这些组合，然后算出所有这些组合的分数之和。但是他还要
出模拟赛虐爆我们这些蒟蒻，所以他只好把这个任务交给了你。

小奔（~~在某些方面~~）还是很仁慈的，所以你不用写高精度，只要输出答案膜 $10^9+7$ 的结果就可以了。

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

第二行 $N$ 个整数 $A_i$ 描述序列。

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


title: WD与矩阵

background: WD整日沉浸在矩阵中，无法自拔……

description:
WD 特别喜欢矩阵，尤其是 01 矩阵。

一天，CX 给了 WD 一个巨大的 $n$ 行 $m$ 列的 01 矩阵，WD 发现这个矩阵每行、每列的异或值都是 0。

CX 随后就问道：“WD，你知道有多少 01 矩阵每行每列异或值都是 0 吗！？”WD 当然不会这个问题，于是他来请教你。

由于答案可能很大，输出结果模 $998\,244\,353$ 的值即可。

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

接下来 $T$ 行每行两个数 $n,m$，分别表示询问的行数和列数。

outputFormat: 共 $T$ 行，每行一个数，表示答案对 $998\,244\,353$ 取模的结果。

hint:
- subtask1（11pts）：$1\le T\le 10,~1\le n,m\le 4$
- subtask2（43pts）：$1\le T\le 5,~1\le n\le 5,~1\le m\le 1,000$
- subtask3（46pts）：$1\le T\le 10^5,~1\le n,m\le 10^9$


title: Check,Check,Check one two!

background:
您正在听くらげP的チェチェ・チェック・ワンツー!，突然教导主任推门进来了，于是您只好假装自己在写字符串题

~~(结果教导主任一眼秒了这水题，您因没事刷水题被批判了一番)~~

description:
给定一个字符串

我们定义$lcp(i,j)$表示从字符串第$i$个位置开始的后缀和从第$j$个位置开始的后缀的最长公共前缀长度

我们定义$lcs(i,j)$表示在字符串第$i$个位置结束的前缀和在第$j$个位置结束的前缀的最长公共后缀长度

现在给定一个长度为$n$的字符串，希望您求出

$$\sum_{1\leq i < j \leq n}lcp(i,j)lcs(i,j)[lcp(i,j)\leq k1][lcs(i,j) \leq k2]$$

模$2^{64}$的值(也就是unsigned long long自然溢出即可)

$[lcs(i,j) \leq k]$表示如果$lcs(i,j) \leq k$这个命题为真那么这个式子的值是1否则是0,另外一个方括号也是同理

inputFormat:
第一行一个字符串$S$,保证仅含有小写的英文字母

第二行两个正整数$k1,k2$表示题目中的限制条件

outputFormat: 仅一行一个正整数，表示题目中所给式子模$2^{64}$的值

hint:
设n表示字符串的长度

测试点10的分值为1,这个测试点的$n \leq 1000$

对于所有的测试点

$$1 \leq n \leq 10^5,1\leq k1 , k2 \leq n$$


title: Eat the Trees

background: HDU1693：Eat the Trees

description: 给出 $n \times m$ 的方格，有些格子不能铺线，其它格子必须铺，可以形成多个闭合回路。问有多少种铺法？

inputFormat:
每个测试点多组数据。第一行一个正整数 $T$，表示有 $T$ 组数据。

对于每组数据：

第 $1$ 行，两个整数 $n,m\ (2 \le n,m \le 12)$。

从第 $2$ 行到第 $n+1$ 行，每行 $m$ 个数字（$1$ 或者 $0$），$1$ 表铺线，$0$ 表不铺线。

outputFormat: 每组数据输出一个整数，表示方案数。


title: painting

background: Wolfycz很喜欢画画（雾

description:
Wolfycz喜欢网格图，他希望在网格图上画上一些黑格子，使得每一列都恰好有一个黑格子。但是黑格子太乱了不好看，所以Wolfycz希望黑格子按列号依次连线是下降的，具体来讲，每列黑格子所在行号不得小于前一列黑格子所在行号（我们令左上角为第一行第一列）

Wolfycz觉得这样画出来的图非常漂亮，但是Wolfycz有时候觉得连线要严格下降才好看（即每列黑格子所在行号必须大于前一列黑格子所在行号），有时候觉得连线只要不上升就好看（即每列黑格子所在行号不得小于前一列黑格子所在行号）。现在Wolfycz想知道，对于一个$N×M$的网格图，他能画出多少个好看的图？两个图不相同，当且仅当存在某一列的黑格子，它在两个图中对应的行号不同

UPD：$N$行$M$列

inputFormat:
第一行读入$T$，表示有$T$组数据

接下来每一行读入三个整数$N,M,opt$，表示$N×M$的矩阵，如果$opt$为1，则Wolfycz认为连线要严格下降才好看；如果$opt$为0，则Wolfycz认为连线只要不上升就好看

outputFormat: 输出共$T$行，每行一个整数，表示Wolfycz能画出不同的图的个数，答案对$10^9+7$取模

hint:
对于$20\%$的数据，$T\leqslant 5,N\leqslant 8,M\leqslant 8$

对于另外$20\%$的数据，$N=1$或$M=1$

对于另外$20\%$的数据，$N\leqslant 10^6,M\leqslant 10^6$

对于$100\%$的数据，$T\leqslant 50,N\leqslant 10^{18},M\leqslant 10^6$


title: polynomial

background: Wolfycz 很喜欢多项式（雾

description:
Wolfycz 喜欢研究多项式，尤其喜欢研究 $(a+b)^n$ 这样简单的问题，我们知道 $(a+b)^n=\sum\limits_{i=0}^n\binom{n}{i}a^ib^{n-i}$，但是 Wolfycz 对这样的式子并不满足，于是他把所有的系数全部改成了 $1$，即 $\sum\limits_{i=0}^na^ib^{n-i}$，但是 Wolfycz 发现自己太菜了，不会求答案，于是希望你来帮帮他。

UPD：请注意常数因子对程序运行效率的影响。

inputFormat:
第一行读入 $T$，表示有 $T$ 组数据。

接下来每一行读入四个整数 $n,a,b,p$。

outputFormat: 共 $T$ 行，每行一个整数，表示 $(\sum\limits_{i=0}^na^ib^{n-i})\bmod p$ 后的值。

hint:
对于$30\%$的数据，$T\leqslant 100,n,a,b,p\leqslant 10^5$

对于$100\%$的数据，$T\leqslant 10^5,n,a,b,p\leqslant 10^{18}$

UPD：不保证$p$为质数！！！


title: sequence

background: Wolfycz很喜欢数列（雾

description:
Wolfycz非常喜欢研究数列，同时他也喜欢研究黄金分割率，有一天Wolfycz写下了一个数列，他令$A_i=\lceil(\dfrac{\sqrt{5}+1}{2})^i\rceil$，但是Wolfycz并不知道$A_n$的值，所以希望你来帮帮他

注：请注意常数因子对程序运行效率的影响

inputFormat:
第一行读入$T$，表示有$T$组数据

之后每一行一个整数$n$

outputFormat: 输出共$T$行，每行一个整数，表示$\lceil(\dfrac{\sqrt{5}+1}{2})^n\rceil$的值，答案对998244353取模

hint:
对于$5\%$的数据，$n\leqslant 20$

对于$40\%$的数据，$T\leqslant 5×10^4$

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


title: fibonacci

background: Wolfycz 很喜欢 Fibonacci 数列（雾

description:
Wolfycz 热衷于研究 Fibonacci 数列，他定义 $Fib_i$ 为Fibonacci 数列的第 $i$ 项，同时定义 $Fib_0=0,Fib_1=1$，并且对于任意的$i$，满足 $Fib_i=Fib_{i-1}+Fib_{i-2}$。

Wolfycz 也喜欢植树，有一天他植了一颗滑稽树（就是 OI 中所说的树，$n$ 个点，$n-1$ 条边，以 $1$ 为根），初始时树上的节点都没有滑稽果，于是 Wolfycz 不惜花重金购入了金坷垃，每次他给滑稽树上的节点 $x$ 施肥 $k$ 克，会使 $x$ 以及它的子树都长出一堆滑稽果，具体来讲，如果 $x$ 子树中的某个节点距离 $x$ 的距离为 $D$，那么这个节点就会长出 $Fib_{D+k}$ 个滑稽果

Wolfycz 觉得滑稽树上滑稽果已经够多了，因此他想 Van 游戏，所以他会时不时询问你两个节点路径上有多少个滑稽果。

inputFormat:
第一行给出两个整数 $N,M$，表示树的节点个数和操作个数

第 $2\sim N$ 行，第 $i$ 行两个数 $x,y$，表示节点 $x,y$ 之间有一条边

接下来 $M$ 行，每行一个形如 `U x k` 或 `Q x y` 的形式

- `U x k`：$x$ 的子树内的节点，若其到 $x$ 的距离为 $D$，则该点长出 $Fib_{D+k}$ 个滑稽果，$x$ 也要长滑稽果
- `Q x y`：询问路径 $x,y$ 上所有节点的滑稽果个数和（包括 $x,y$），答案对 $10^9+7$ 取模

outputFormat: 对于每个 `Q x y` 询问，输出其答案。

hint:
对于$30\%$的数据，$N,M,k\leqslant 10^3$

对于$100\%$的数据，$N,M\leqslant 10^5$，$1\leqslant x,y\leqslant N$，$1\leqslant k\leqslant 10^{18}$。


title: dkw的lcm

description:
**特别地，一个数的lcm是自身**

善良的dkw决定直接告诉你题面：
$$\prod_{i_1=1}^n\prod_{i_2=1}^n …\prod_{i_k=1}^n \varphi\big(lcm(i_1,i_2,…,i_k)\big)$$
请你求上述式子，答案对 $10^9+7$ 取模。

其中 $lcm(i_1,i_2,...,i_k)$ 代表这 $k$ 个数的最小公倍数。

其中 $\varphi$ 代表欧拉函数，不知道的可以问度娘。

其中 $\prod$ 代表连乘符号，简单来说就是 $\sum$ 的乘法版。

inputFormat: 两个正整数，$n,k$

outputFormat: 一个非负整数，代表式子的值对 $10^9+7$ 取模的结果。

hint:
对于 50% 的数据，$1\le n,k\le 8$

对于 100% 的数据，$1\le n,k\le 10^6$


title: [JSOI2012] 分零食

description:
这里是欢乐的进香河，这里是欢乐的幼儿园。

今天是 2 月 14 日，星期二。在这个特殊的日子里，老师带着同学们欢乐地跳着，笑着。校长从幼儿园旁边的小吃店买了大量的零食决定分给同学们。听到这个消息，所有同学都安安静静地排好了队，大家都知道，校长不喜欢调皮的孩子。

同学们依次排成了一列，其中有 $A$ 位小朋友，有三个共同的欢乐系数 $O$，$S$ 和 $U$。如果有一位小朋友得到了 $x$ 个糖果，那么她的欢乐程度就是 $f(x)=Ox^2+Sx+U$。

现在校长开始分糖果了，一共有 $M$ 个糖果。有些小朋友可能得不到糖果，对于那些得不到糖果的小朋友来说，欢乐程度就是 $1$。如果一位小朋友得不到糖果，那么在她身后的小朋友们也都得不到糖果（即这一列得不到糖果的小朋友一定是最后的连续若干位）。

所有分糖果的方案都是等概率的。现在问题是：期望情况下，所有小朋友的欢乐程度的乘积是多少？呆呆同学很快就有了一个思路，只要知道总的方案个数 $T$ 和所有方案下欢乐程度乘积的总和 $S$，就可以得到答案 $ans=\frac{S}{T}$。现在他已经求出来了 $T$ 的答案，但是 $S$ 怎么求呢？他就不知道了。你能告诉他么？

因为答案很大，你只需要告诉他 $S$ 对 $P$ 取模后的结果。

后记：

虽然大家都知道，即便知道了 $T$，知道了 $S$ 对 $P$ 取模后的结果，也没有办法知道期望情况下，所有小朋友欢乐程度的乘积。但是，当呆呆想到这一点的时候，已经彻底绝望了。

inputFormat:
第一行有两个整数，分别是 $M$ 和 $P$。

第二行有一个整数 $A$。

第三行有一个整数 $O$。

第四行有一个整数 $S$。

第五行有一个整数 $U$。

outputFormat: 一个整数 $S$，因为答案可能很大，你只需要输出 $S$ 对 $P$ 取模后的结果。

hint:
**样例解释：**

函数 $f(x)=x^2$。一共有 $4$ 份零食，$4$ 位同学。如果只有第一个同学得到，欢乐程度为 $16$，若前两位同学得到，欢乐程度的所有可能依次为 $9, 9, 16$，若有三位同学得到，欢乐程度有 $4, 4, 4$，最后一种情况，每一个同学都得到了零食，欢乐程度为 $1$。相加后得到 $S=63$。

**数据范围：**

对于 $40 \%$ 的数据，$M \leq 150$。
对于 $60 \%$ 的数据，$M \leq 2000$。
对于 $80 \%$ 的数据，$M \leq 6000$。
对于 $100 \%$ 的数据，$M \leq 10000, P \leq 255, A \leq 10^8, O \leq 4, S \leq 300, U \leq 100$。


title: xtq的定向越野

background: xtq在定向越野方面有异于常人的天赋，小学一年级时就获得了“题刷杯”的第一名和“蝈蝈杯”的“蝈蝈”。有一天，他正在研究一个问题。

description:
xtq希望设计一个圆形地图，这可以视作一个圆，圆周上有任意多个互不重叠的打卡点，打卡点上有一些任务。

设所有可能的任务为一个$k$元集合，则这个集合有$2^k$个互不相同子集，设为$A_1,A_2......A_{2^k}$，那么每一个打卡点上都有且仅有$A_1,A_2......A_{2^k}$中的一个任务子集。注意：不同的点可以有相同的任务子集。

xtq想要满足以下条件：

$1$:对于满足$||Ai|-|Aj||=1$的任意子集$Ai$，$Aj$，都有且仅有一对相邻打卡点的任务子集为$Ai$、$Aj$

$2$:对于任意相邻的点上的子集$Ai$，$Aj$，均满足$||Ai|-|Aj||=1$

现在xtq给了你一个$n$，希望让你求出所有可能的$2\le k\le n$，使得至少存在一种放置打卡点和任务的方案。

在以上的描述中，$|Ai|$表示$|Ai|$的元素个数，$|a+b|$表示$a+b$的绝对值

inputFormat: 一个正整数$n$。

outputFormat: 若干行，每行一个正整数，表示一个可能的$k$，按大小升序排列。

hint:
[样例解释]

当$k=2$时，设所有可能的任务是$\{1,2\}$，则任务的4个子集是$\emptyset$,$\{1\}$,$\{2\}$,$\{1,2\}$。下图是一种符合条件的方案：

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

图中$\{\emptyset\}$应当为$\emptyset$(typo)

[数据范围]

对于$50\%$的数据，$n\le 5000$。

对于$100\%$的数据，属于$long long$范围内，并且$2\le n$。


title: [MtOI2019] 幽灵乐团 / 莫比乌斯反演基础练习题

background:
白玉楼中，冥界的音乐会开始了。

Lunasa，Lyrica 和 Merlin 正在演奏。

description:
东风谷 早苗(Kochiya Sanae)非常喜欢幽灵乐团的演奏，她想对她们的演奏评分。

因为幽灵乐团有 $3$ 个人，所以我们可以用 $3$ 个正整数 $A,B,C$ 来表示出乐团演奏的分数，她们的演奏分数可以表示为

$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)}$$

因为音乐在不同的部分会有不同的听觉感受，所以 $type$ 会在 $\{0,1,2\}$ 中发生变化，其中：

$$\begin{aligned}
f(0)&=1 \cr
f(1)&=i \times j \times k \cr
f(2)&=\gcd(i,j,k)
\end{aligned}$$

因为乐团的歌实在太好听了，导致分数特别高，所以她们的分数要对给定的正整数 $p$ 取模。

因为有很多歌曲要演奏，所以早苗给出了 $T$ 组询问。

inputFormat:
第一行两个正整数 $T$，$p$，含义详见题目描述。

接下来 $T$ 行，每行三个正整数 $A,B,C$ 表示每组询问。

outputFormat: $T$ 行，每行三个正整数分别表示 $type=0/1/2$ 的时候给定式子的值。

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

对于 $10\%$ 的数据：

$$ 1\leq A,B,C\leq 50 $$

对于 $20\%$ 的数据：

$$ 1\leq A,B,C\leq 100 $$

另有 $10\%$ 的数据：

$$ 1\leq A,B,C\leq 100\ \ \ \ \ A=B=C $$

对于 $60\%$ 的数据：

$$ 1\leq A,B,C\leq 10^3 $$

对于 $100\%$ 的数据：

$$ 1\leq A,B,C\leq 10^5 \ \ \ \ 10^7 \leq p \leq 1.05\times 10^9\ \ \ \ p\in \{ prime\} \ \ \ \ T =70$$

---

早苗非常善良，就算你不知道所有的正确答案，她也会给你一些分数。

* 如果你的第一列是正确的，她将会给你这个测试点 $20\%$ 的分数。
* 如果你的第二列是正确的，她将会给你这个测试点 $40\%$ 的分数。
* 如果你的第三列是正确的，她将会给你这个测试点 $40\%$ 的分数。

所以就算你不知道答案是什么，也请你在你不知道的那些地方输出 $[0,2^{31})$ 内的整数，否则可能会造成不可预估的错误。

### 题目来源

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

出题人：CYJian


title: 【模板】Polya 定理

description:
给定一个 $n$ 个点，$n$ 条边的环，有 $n$ 种颜色，给每个顶点染色，问有多少种**本质不同**的染色方案，答案对 $10^9+7$ 取模。

注意本题的本质不同，定义为：**只需要不能通过旋转与别的染色方案相同**。

inputFormat:
第一行输入一个 $t$，表示有 $t$ 组数据

第二行开始，一共 $t$ 行，每行一个整数 $n$，意思如题所示。

outputFormat: 共$t$行，每行一个数字，表示染色方案数对 $10^9+7$ 取模后的结果


title: 矩形

background: 小奔月考考的可棒了！作为奖励，老师给了他一只激光笔。

description:
但老师永远不是白给小奔奖品的。他告诉小奔：反射角等于入射角。并让他解决下面的问题：

如果有一个矩形，长和宽之比为N：M，现在有一束激光从左上角射出，且与长N的夹角为 ζ °（0≤ζ≤90），且满足cot ζ ° = A ： B，求最少需要多少次反射才能重新反射入四个角当中的任意一个角呢？

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

inputFormat:
两行，第一行两个数N，M，表示长和宽之比；

第二行两个数A，B，表示cot ζ ° 。

outputFormat: 一个正整数，表示最少需要的反射次数。

hint:
对于10%的数据,A=B=1；

对于另10%的数据,N=M；

对于50%的数据，$0≤A,B,M,N≤10^5$；

对于100%的数据，$0≤A,B,M,N≤10^{10}$；


title: [eJOI2018] 元素周期表

background: **本题译自 [eJOI2018](http://ejoi2018.org/) Problem D「Chemical table」**

description:
Innopolis 大学的教授正努力研究元素周期表。他们知道，有 $n \times m$ 种元素，形成了一个 $n$ 行 $m$ 列的矩阵。

研究表明，如果元素周期表上有一个元素 A，且元素 B 与它在同一列（A 与 B 不能在同一周期），元素 C 在同一周期（A 与 C 不能在同一列），那么，科学家就可以用这三种元素通过核聚变合成第四种元素 D 的样品，D 与 B 在同一周期，与 C 在同一列。
简而言之，如果有在元素周期表中位置为 $(r_1, c_1),\ (r_1, c_2),\ (r_2, c_1)$ （其中 $r_1 \neq r_2, c_1 \neq c_2$）的三种元素的样品，就可以生成位置为 $(r_2, c_2)$ 的样品。如图所示：

![](http://codeforces.com/predownloaded/95/22/95223620a323ec59470718b34958c7f295698ff1.png)

**注意：在核聚变中被使用的样品并不会消失，它们可以参与之后的反应；反应得到的样品也可以参与反应。**

他们已经获得了 $q$ 种元素的样品。为了集齐所有元素的样品，他们会购买一些样品，然后利用核聚变制造出剩下元素的样品。
请求出他们至少需要购买的元素样品的数量。

inputFormat:
第一行， $3$ 个整数 $n, m, q \ (1 \le n, m \le 2 \times 10^5, 0 \le q \le \min \{n \times m, 2 \times 10^5\})$ 。
之后的 $q$ 行，每行 $2$ 个整数 $r_i, c_i \ (1 \le r_i \le n, 1 \le c_i \le m)$ 。保证给定的元素互不相同。

outputFormat: 输出一个整数，表示至少需要购买的元素样品的数量。

hint:
### 样例解释

#### 说明
每个样例解释中有两个矩阵。
第一个表示初始状况（其中，**打叉的是原本就有样品的元素**）。
第二个表示最终集齐样品时的状况（其中，**蓝圈代表核聚变得到的样品，蓝圈中的数字表示得到样品的顺序，红圈表示购买的样品**）。

#### 样例解释 1

通过给定的三种元素，可以得到第四种元素的样品。

![](http://codeforces.com/predownloaded/ee/44/ee44494c3f7ff02138d16c3ee2119a4a528c893a.png)

#### 样例解释 2

由于给定的元素只有一行，无法使用核聚变，只能购买剩余的两种元素的样品。

![](http://codeforces.com/predownloaded/db/b4/dbb4c8c683b0e23a35c204b500695c0efb59e587.png)

#### 样例解释 3

集齐所有元素的方法不唯一，以下是一种方法。其中，元素 $(4, 2)$ 只有在购买元素 $(4, 1)$ 的样品，和反应得到元素 $(1, 1)$的样品后才能得到。

![](http://codeforces.com/predownloaded/0c/d8/0cd813ff41b05914fceb0e1f25c2907bcb020959.png)

---

### 子任务

**注意：当且仅当你通过了一个子任务下的所有测试点，你将获得此子任务的分数。**

|子任务编号|分数|$n$|$m$|$q$|
|:-:|:-:|:-:|:-:|:-:|
|$1$|$10$|$n=2$|$m=2$|$0 \le q \le 4$|
|$2$|$17$|$1 \le n \le 2$|$1 \le m \le 20$|$0 \le q \le 20$|
|$3$|$8$|$1 \le n \le 20$|$1 \le m \le 20$|$q=0$|
|$4$|$20$|$1 \le n \le 20$|$1 \le m \le 20$|$0 \le q \le 400$|
|$5$|$30$|$1 \le n \le 1 \times 10^4$|$1 \le m \le 1 \times 10^4$|$1 \le q \le 1 \times 10^5$|
|$6$|$15$|$1 \le n \le 2 \times 10^5$|$1 \le m \le 2 \times 10^5$|$1 \le q \le 2 \times 10^5$|


title: [eJOI2018] 互素树

background: **本题译自 [eJOI2018](http://ejoi2018.org/) Problem E「Prime Tree」**

description:
本题为提交答案，输入文件在附件中。

设有一棵有 $n$ 个结点的树，其结点编号为 $1$ 到 $n$ 。
对于其中的任意一条边 $(u, v)$ ，如果存在一个正整数 $d>1$ 满足 $ d \mid u, d\mid v$ ，我们称它为一条**坏的边**。
下图中的树有三条坏的边—— $(6, 4)$（都被 $2$ 整除）， $(2, 6)$（都被 $2$ 整除）， $(3, 6)$（都被 $3$ 整除）。

![](https://i.loli.net/2018/08/17/5b7633a4ceb38.png)

你的任务是将结点重新编号，使得图中坏的边的数量尽量少。
对于上图中的树，按照下图中的方式将结点重新编号，会只剩一条坏的边 $(3, 6)$ 。

![](https://i.loli.net/2018/08/17/5b7633a4cfebf.png)

重新编号后，坏的边越少，你的得分越高。

**这是一道提交答案题。你应当下载输出文件，然后在本地运行你的程序，将输出结果上传**。当然，在洛谷上你可以直接提交你的程序。

inputFormat:
每个测试点中有多组测试数据。
第一行，一个整数 $T$，表示测试数据组数。
每组测试数据共 $n$ 行，其中 $n$ 表示树的结点个数。
第一行，一个整数 $n$；
接下来 $n-1$ 行，每行两个整数 $u$ 和 $v\ ( 1 \le u, v \le n)$，表示一条边 $(u,v)$ 。

**每个输入文件中，每棵树的结点个数相同。**

outputFormat:
对于每组测试数据，输出一行 $n$ 个整数，表示原先编号为 $1$ 到 $n$ 的结点的新编号。
**每个结点的编号必须不同，也就是说同一组测试数据中输出的 $n$ 个整数必须互不相同。**


title: 【模板】类欧几里得算法

description: 给定 $n,\,a,\,b,\,c$ ，分别求 $\sum\limits_{i=0}^{n}\lfloor \frac{ai+b}{c} \rfloor\,,\  \sum\limits_{i=0}^{n}{\lfloor \frac{ai+b}{c} \rfloor}^2\,,\  \sum\limits_{i=0}^{n}i\lfloor \frac{ai+b}{c} \rfloor$ ，答案对 $998244353$ 取模。多组数据。

inputFormat:
第一行给出数据组数 $t$ 。

接下来 $t$ 行，每行有四个整数，分别为每组数据的 $n,\ a,\ b,\ c$ 。

outputFormat: 对于每组数据，输出一行三个整数，为三个答案对 $998244353$ 取模的结果。

hint:
本题采用 $\mathrm{Special}\ \mathrm{Judge}$。

答对所有第一问可以获得测试点 $40\%$ 的分数，答对所有第二问、第三问可以分别获得另外 $30\%$ 的分数。

|测试点编号|特殊性质|
|:-:|:-:|
|$1$|$n,\,a,\,b,\,c\leqslant10$|
|$2 \sim 3$|$n,\,a,\,b,\,c\leqslant1000$|
|$4$|$n,\,a,\,b,\,c\leqslant10^6$|
|$5$|$t=1$|
|$6 \sim 10$|无|

对于所有测试点，有 $1 \leqslant t \leqslant 10^5,\ 0 \leqslant n,\,a,\,b,\,c \leqslant 10^9,\ c \neq 0$ 。


title: [JOI 2017 Final] 足球

description:
**题目译自 [JOI 2017 Final](https://www.ioi-jp.org/joi/2016/2017-ho/) T4「[サッカー](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho.pdf) / [Soccer](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho-en.pdf)」**

> 「假定球滚动时可以穿过其他球员」这句是在未修改数据的前提下，为了严谨我补上的，原题没有提这一点。如果撞到其他球员就停下的话似乎做法不同？

你是 JOI 联赛中一所声名卓著的足球俱乐部的经理。

俱乐部有 $N$ 名球员，编号为 $1\ldots N$。球员们每天都刻苦地进行训练，剑指联赛冠军。足球场可视为一个底为 $W$ 米，高 $H$ 米的长方形，底平行于东西方向，高平行于南北方向。如果某个点向北走 $i$ 米，再向西走 $j$ 米恰好到达球场的西北角，这个点可用坐标 $(i, j)$ 来表示。

练习结束后，你要回收练习用的足球。开始回收时，所有球员都在足球场上，球员 $i (1\leqslant i\leqslant N)$ 位于 $(S_i, T_i)$，球在球员 $1$ 脚下。你正和球员 $N$ 一起站在 $(S_N, T_N)$，并准备回收球。球员们把球传到 $(S_N, T_N)$ 时，你才会回收球。

你可以指挥球员，但某些操作会提升球员的**疲劳度**。一个球员不能同时进行多项操作。
你可以指挥控球的球员进行如下操作：
* **踢球**。在东西南北四个方向中任选一个，并指定一个正整数 $p$，该球员将球朝指定方向踢出恰好 $p$ 米。**假定球滚动时可以穿过其他球员**。该球员不会移动，且自动停止控球，疲劳度上升 $A\times p+B$。
* **运球**。在东西南北四个方向中任选一个，该球员带球，朝指定方向移动 $1$ 米。该球员仍然控球，疲劳度上升 $C$。
* **停止控球**。该球员的疲劳度不改变。

你可以指挥没有控球的球员进行如下操作：
* **移动**。在东西南北四个方向中任选一个，该球员朝指定方向移动 $1$ 米，疲劳度上升 $C$。
* **控球**。如果该球员所在的位置恰好有球，且没有其他球员控球，该球员才能控球。该球员的疲劳度不改变。

球员和球有可能跑出场外，一个位置上可能有多个球员。
一天的训练结束后，球员们非常疲惫。你想知道在回收球的过程中，所有球员上升的疲劳度之和的最小值。

inputFormat:
第一行有两个整数 $H, W$，用空格分隔。
第二行有三个整数 $A, B, C$，用空格分隔。
第三行有一个整数 $N$。
在接下来的 $N$ 行中，第 $i$ 行 $(1\leqslant i\leqslant N)$有两个整数 $S_i, T_i$，用空格分隔。
输入的所有数的含义见题目描述。

outputFormat: 一行，一个整数，表示在回收球的过程中，所有球员上升的疲劳度之和的最小值。

hint:
#### 样例解释 1
在这组样例中，球场、球员、球处于如图所示的状态。图中，黑框空心圆圈表示球员，实心圆表示球，你在 $(6,5)$。

![初始状态](https://s1.ax1x.com/2018/12/11/FYUzwQ.png)

最优解如下：
1. 球员 $1$ 把球向东踢出 $3$ 米。疲劳度上升了 $1\times 3+3=6$，球移动到 $(1,4)$。
2. 球员 $2$ 向南移动 $1$ 米。疲劳度又上升了 $6$。
3. 球员 $2$ 开始控球。
4. 球员 $2$ 向东运球 $1$ 米。疲劳度又上升了 $6$。
5. 球员 $2$ 把球向南踢出 $5$ 米，疲劳度上升了 $1\times 5+3=8$，球移动到 $(6,5)$。

此时，疲劳度之和为 $6+6+6+8=26$。没有更好的方案。

![最优解](http://www.z4a.net/images/2017/12/10/JOI2017T4-2.png)

#### 样例解释 2
在最优解中，不需要踢球。

#### 样例解释 4
注意这组样例中有多个球员在同一位置的情况。

#### 数据范围与提示
对于 $5\%$ 的数据，$N=2$。
对于另外 $30\%$ 的数据，$N\leqslant 1000, A=0$。
对于所有数据，$1\leqslant H,W\leqslant 500, 0\leqslant A, B, C\leqslant 10^9, 2\leqslant N\leqslant 10^5, 0\leqslant S_i\leqslant H, 0\leqslant T_i\leqslant W(1\leqslant i\leqslant N), (S_1, T_1)\neq(S_N, T_N)$。


title: [JOI 2017 Final] 绳

description:
**题目译自 [JOI 2017 Final](https://www.ioi-jp.org/joi/2016/2017-ho/) T5「[縄](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho.pdf) / [Rope](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho-en.pdf)」**

 JOI 小宝宝正拿着一根绳子玩。绳子可视为一条长度为 $N$ 的左右延伸的线段。绳子由 $N$ 根线连接而成，每根线的长度为 $1$，厚度为 $1$。绳子上的线共有 $M$ 种颜色，左数第 $i$ 根线 $(1\leqslant i\leqslant N)$ 的颜色为 $C_i(1\leqslant C_i\leqslant M)$。**绳子的左端点**意为左数第 $1$ 根线的左端点，**绳子的右端点**意为右数第 $1$ 根线的右端点。显然左数第 $i$ 根线 $(1\leqslant i\leqslant N)$ 的右端点 到 绳子的左端点 的距离为 $i$。

JOI 把绳子的长度缩短了。具体来说，JOI 反复地进行以下过程，直到绳长缩短至 $2$。

* 假设此时绳子的长度为 $L$。指定一个整数 $j(1\leqslant j<L)$，使绳子左数第 $j$ 根线成为绳子的左端点（最左的线），并折叠绳子。也就是说，
  - 如果 $j\leqslant \Large\frac{L}{2}$，则将左数第 $i$ 根线 $(1\leqslant i\leqslant j)$ 与左数第 $(2j-i+1)$ 根线拧成一股。此时，绳子原本的右端点仍是右端点，绳长变为 $L-j$。
  - 如果 $j> \Large\frac{L}{2}$，则将左数第 $i$ 根线 $(2j-L+1\leqslant i\leqslant j)$ 与左数第 $(2j-i+1)$ 根线拧成一股。此时，绳子原本的左端点变为右端点，绳长变为 $j$。
* 两条线的颜色相同才能拧成一股。在将两条线拧成一股前，可以任意改变线的颜色。将线染成其他颜色所需的费用 等于 线的厚度。颜色匹配后，两条线将被拧成一股，新的一股线的厚度 将为 两条线的厚度之和。

我们把绳长缩短至 $2$ 的绳子称为最终的绳子。JOI 希望使得将绳长缩短至 $2$ 所需的费用尽可能小。对于每种颜色，JOI 都想知道，在最终的绳子中包含这种颜色的情况下，将绳长缩短至 $2$ 所需的最小费用。

你的任务是帮 JOI 解决这个问题。

inputFormat:
第一行有两个整数 $N, M$，用空格分隔。
第二行有 $N$ 个用空格分隔的整数 $C_1, C_2, \ldots, C_N$。
输入的所有数的含义见题目描述。

outputFormat: 共 $M$ 行，第 $c$ 行 $(1\leqslant c\leqslant M)$ 有一个整数，表示在最终的绳子中包含颜色 $c$ 的情况下，将绳长缩短至 $2$ 所需的最小费用。

hint:
#### 样例解释 1
通过下述步骤，只需花费 $2$，就可以使得最终的绳子中包含颜色 $1$。
* 把左数第 $2$ 根线染成颜色 $1$。折叠绳子使得 原本到左端点的距离为 $1$ 的端点 变为 新的左端点。现在，从左往右数，线的颜色依次是 $1,$ $ 3,$ $ 3,$ $ 2$，厚度依次是 $2,$ $ 1,$ $ 1,$ $ 1$。
* 把左数第 $4$ 根线染成颜色 $1$。折叠绳子使得 原本到左端点的距离为 $2$ 的端点 变为 新的左端点。现在，从左往右数，线的颜色依次是 $3, 1$，厚度依次是 $2, 3$。

通过下述步骤，只需花费 $1$，就可以使得最终的绳子中包含颜色 $2$ 和 $3$。
* 折叠绳子使得 原本到左端点的距离为 $3$ 的端点 变为 新的左端点。现在，从左往右数，线的颜色依次是 $3,$ $ 2,$ $ 1$，厚度依次是 $2,$ $ 2,$ $ 1$。
* 把左数第 $3$ 根线染成颜色 $2$。折叠绳子使得 原本到左端点的距离为 $2$ 的端点 变为 新的左端点。现在，从左往右数，线的颜色依次是 $2, 3$，厚度依次是 $3, 2$。

#### 样例解释 2
通过下述步骤，只需花费 $2$，就可以使得最终的绳子中包含颜色 $1$。
* 折叠绳子使得 原本到左端点的距离为 $2$ 的端点 变为 新的左端点。
* 把左数第 $1$ 根线染成颜色 $1$。折叠绳子使得 原本到左端点的距离为 $1$ 的端点 变为 新的左端点。注意这次染色的费用为 $2$，因为此时左数第 $1$ 根线的厚度为 $2$。
* 折叠绳子使得 原本到左端点的距离为 $3$ 的端点 变为 新的左端点。
* 折叠绳子使得 原本到左端点的距离为 $1$ 的端点 变为 新的左端点。

#### 数据范围与提示
对于 $15\%$ 的数据，$N\leqslant 15, M\leqslant 10$。
对于另外 $30\%$ 的数据，$N\leqslant 10^5, M\leqslant 10$。
对于另外 $10\%$ 的数据，$N\leqslant 10^5, M\leqslant 500$。
对于另外 $20\%$ 的数据，$N\leqslant 10^5, M\leqslant 5000$。
对于所有数据，$2\leqslant N\leqslant 10^6, 1\leqslant M\leqslant N, 1\leqslant C_i\leqslant M(1\leqslant i\leqslant N)$，在初始状态的绳子上，颜色 $1, 2, \ldots, M$ 都至少出现了一次。


title: 特工的信息流

background:
$\text{TYM}$ 是一名特工。
$\text{TYM}$ 所在的国家正受到侵犯，他被赋予一个任务：于城市之间传递信息。

description:
$\text{TYM}$ 所在的国家有 $n$ 个城市，编号为 $1,\dots,n$，由 $n - 1$ 条双向道路连接。保证任意两个城市间都有唯一的简单路径。
以及，每个城市都有一个信息流的流量 $a_i$。

$\text{TYM}$ 一共要执行 $m_0$ 个任务，每个任务给定两个城市 $s,t$，其执行过程如下：
第一个时刻，他从城市 $s$ 出发，以每个时刻移动到下一个城市的速度，走 $s,t$ 之间的简单路径到 $t$。
每到达一个城市，他都会把这个城市的信息流 $a_i$ 发送到经过的每个城市。
我们约定，他到达一个城市的同一时刻也会把这个城市的信息流发送给这个城市。我们定义一个城市的价值为这个城市所接受到的信息流的乘积。

请你求出每个任务中，$s$ 到 $t$ 的简单路径上经过的城市的价值的总和对 $20924$ 取模的结果。

此外，不幸地，由于侵略者同时也在行动，所以在他执行多个任务之间，可能会有某个 $a_i$ 发生改变。

他的任务总数与改变某个 $a_i$ 的次数之和为 $m$。

inputFormat:
第一行，两个整数 $n,m$。
第二行，$n$ 个整数，第 $i$ 个表示第 $i$ 个城市的信息流流量 $a_i$。
以下 $n - 1$ 行，每行两个整数 $u,v$，表示 $u,v$ 之间有一条双向道路。
以下 $m$ 行，每行描述一个任务或是一次修改事件：
  - 形如 `Q s t`，表示 $\text{TYM}$ 从 $s$ 到 $t$ 执行了一次任务。
  - 形如 `C x k`，表示侵略者的行动令 $a_x \rightarrow a_x + k$。

outputFormat: 对于每次任务，输出经过的城市收到的信息流总流量。

hint:
**数据范围：**

对于 $20\%$ 的数据，$1 \leq n,m \leq 2000$；
对于额外的 $20\%$ 的数据，满足 $a_i=2$，且没有修改操作；
对于额外的 $20\%$ 的数据，满足道路从 $i$ 连向 $i+1$；
对于 $100\%$ 的数据，$1 \leq n,m \leq 10^5,1 \leq a_i \leq 20923$。

**样例解释：**

第一个询问，$1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 + 2 \cdot 3 \cdot 4 \cdot 5 + 3 \cdot 4 \cdot 5 + 4 \cdot 5 + 5 = 325$；
修改，$a_1 = 1 + 2 = 3$；
第二个询问，$3 \cdot 2 \cdot 3 \cdot 4 \cdot 5 + 2 \cdot 3 \cdot 4 \cdot 5 + 3 \cdot 4 \cdot 5 + 4 \cdot 5 + 5 = 565$；


title: [JOI 2016 Final] 领地

description:
**本题译自 [JOI 2016 Final](https://www.ioi-jp.org/joi/2015/2016-ho/index.html) T4「[縄張り](https://www.ioi-jp.org/joi/2015/2016-ho/2016-ho.pdf)」**

有一个平面直角坐标系。JOI 君位于 $(0, 0)$ 。
JOI 君**每天**都按照一个固定的程序移动一轮。该程序有 $N$ 个步骤，用一个长度为 $N$ 的字符串 $S$ 描述。这个字符串仅由大写字母 $\texttt{E, N, W, S}$ 构成。
左数第 $i$ 个字符 $C_i (1\leqslant i\leqslant N)$ 表示 JOI 君会移动到哪里。如果在执行步骤 $i$ 前，JOI 君位于 $(x, y)$：
* $C_i=\texttt{E}$：JOI 君将移动到 $(x+1,y)$；
* $C_i=\texttt{N}$：JOI 君将移动到 $(x,y+1)$；
* $C_i=\texttt{W}$：JOI 君将移动到 $(x-1,y)$；
* $C_i=\texttt{S}$：JOI 君将移动到 $(x,y-1)$。

次日 JOI 君会从他前一天停止的位置开始执行程序。
JOI 君会把 $(0, 0)$ 以及每个步骤结束后到达的点作标记。开始时 JOI 君没有标记任何点。$K$ 天后，对于任意整数 $a, b$，如果 $(a,b),$ $(a+1,b),$ $(a,b+1),$ $(a+1,b+1)$ 这四个点都被标记了一次或以上，以这四个点为顶点的 $1\times 1$ 的正方形就属于 JOI 君的领地。
请问 $K$ 天后，JOI 君有多少个领地。

inputFormat:
第一行有两个整数 $N, K$，用空格分隔。
第二行有一个字符串 $S$，表示 JOI 君移动的程序。

outputFormat: 一个整数，表示 JOI 君有多少个领地。

hint:
#### 样例解释 1

![JOI2016T4](http://www.z4a.net/images/2018/02/16/JOI2016T4.png)

> 图中的字是之前完整题面的，懒得改了。「市政厅」表示 $(0, 0)$，「散步路径」表示移动路线。
> 图我没有仔细 PS 过，可能对不齐、不对称，强迫症的同学们麻烦忍一忍

#### 样例解释 2
样例 2 与样例 1 的不同在于在样例 2 中 JOI 君走了两天。

![JOI2016T4-1](http://www.z4a.net/images/2018/02/16/JOI2016T4-1.png)

#### 数据范围与提示
对于所有数据，$1\leqslant N\leqslant 10^5, 1\leqslant K\leqslant 10^9$。

|Subtask #|特殊限制|分值|
|-|-|-|
|1|$N\leqslant 50, K = 1$|5|
|2|$K = 1$|10|
|3|$N\leqslant 50$|23|
|4|无|62|


title: [JOI 2016 Final] 断层

description:
**译者水平有限，跪求各位大佬提供更好的译文**

**本题译自 [JOI 2016 Final](https://www.ioi-jp.org/joi/2015/2016-ho/index.html) T5「[断層](https://www.ioi-jp.org/joi/2015/2016-ho/2016-ho.pdf)」**

很久很久以前，一个叫做 IOI 的先进文明蓬勃发展。时过境迁，现代考古学家 JOI 博士决定挖掘 IOI 文明遗址。

IOI 文明沿着笔直的河流发展。方便起见，IOI 文明遗址可以看作平面直角坐标系的 $x$ 轴，而 $y$ 轴表示海拔。IOI 文明地面平坦，也就是说，直线 $y=0$ 代表地面，而 $y>0$ 代表地面上空，$y<0$ 代表地下。另外，由于流水堆积，IOI 文明的地面一直在缓慢升高。IOI 文明灭亡前 $a$ 年 $(a\geqslant 0)$ 时，直线 $y=-a$ 才是地平面。
IOI 文明灭亡后，它脚下的地层发生了 $Q$ 次运动。第 $i$ 次运动 $(1\leqslant i\leqslant Q)$ 可用位置 $X_i$，方向 $D_i$ 和变化量 $L_i$ 描述。$D_i = 1$ 或 $2$。具体来说，

* $D_i=1$：断层视为一条过 $(X_i, 0)$，斜率为 $1$ 的直线。断层上方的地层斜向上移动，横坐标增加 $L_i$，纵坐标增加 $L_i$。也就是说，直线上方的所有点 $(x,y)$ 移动到 $(x+L_i, y+L_i)$。
* $D_i=2$：断层视为一条过 $(X_i, 0)$，斜率为 $-1$ 的直线。断层上方的地层斜向上移动，横坐标减少 $L_i$，纵坐标增加 $L_i$。也就是说，直线上方的所有点 $(x,y)$ 移动到 $(x-L_i, y+L_i)$。

每次地壳运动后，$y>0$ 的地层都会因风化作用而消失。

试求：对于每一个 $i(1\leqslant i\leqslant N)$，**点 $(i-1,0)$ 和 点$(i,0)$ 之间的地层**是在 IOI 文明灭亡前哪一年的地层。

> 在 $y$ 轴上，断层都是经过整点的，$y$ 轴上的相邻整点间没有断层。这样讲能明白吧……

inputFormat:
第一行有两个整数 $N,Q$，用空格分隔。
在接下来的 $Q$ 行中，第 $i$ 行 $(1\leqslant i\leqslant N)$ 有三个整数 $X_i, D_i, L_i$，用空格分隔。
输入的所有数的含义见题目描述。

outputFormat: 输出共 $N$ 行，第 $i$ 行 $(1\leqslant i\leqslant N)$ 有一个整数，表示点 $(i-1,0)$ 和 点$(i,0)$ 之间的地层是在 IOI 文明灭亡前哪一年的地层。

hint:
#### 样例解释 1
![0fe14625e2fb78233cfd864dde8e1eda.png](http://www.z4a.net/images/2018/02/09/0fe14625e2fb78233cfd864dde8e1eda.png)

#### 数据范围与提示
对于所有数据，$1\leqslant N, Q\leqslant 2\times 10^5, -10^9\leqslant X_i\leqslant 10^9, D_i=1$ 或 $2, 1\leqslant L_i\leqslant 10^9(1\leqslant i\leqslant Q)$。

|Subtask #|$N,Q$|其他限制|分值|
|-|-|-|-|
|1|$N,Q\leqslant 100$|$-100\leqslant X_i\leqslant 100, L_i=1(1\leqslant i\leqslant Q)$|18|
|2|$N,Q\leqslant 3000$|无|16|
|3|$N,Q\leqslant 2\times10^5$|无|66|


title: 传球

background:
临近中考，pG的班主任决定上一节体育课，放松一下。

题解：https://blog.csdn.net/kkkksc03/article/details/85008120

description:
老师带着 pG 的同学们一起做传球游戏。

游戏规则是这样的： $n$ 个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是败者，要给大家表演一个节目。

pG 提出一个有趣的问题：有多少种不同的传球方法可以使得从 pG 手里开始传的球，传了 $m$ 次以后，又回到 pG 手里。两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有三个同学 $1$ 号、 $2$ 号、 $3$ 号，并假设 pG 为 $1$ 号，球传了 $3$ 次回到pG手里的方式有 $1 \to 2 \to 3 \to 1$ 和 $1 \to 3 \to 2 \to 1$ ，共$ 2$ 种。

inputFormat: 一行，有两个用空格隔开的整数 $n,m$

outputFormat:
$1$ 个整数，表示符合题意的方法数。

由于答案可能过大，对 $10^9+7$ 取模。


title: 圆点

background:
中考了，Pg看着数学卷子的压轴题，陷入了沉思……

题解：https://blog.csdn.net/kkkksc03/article/details/85008125

description:
众所周知，平面中的每一个整点都**有且仅有**一个圆心在原点的圆穿过，我们定义这个整点的权值为穿过它的圆的**半径的平方**。

现在有一个圆心在原点的圆，半径为$\sqrt{R}$。你要求出这个圆所包含的所有整点的权值**和**。

由于答案可能过大，对$10^9+7$取模。

inputFormat: 一个数字$R$。

outputFormat: 一行，仅有一个数字。


title: 数列

description:
一个数列 $a_n $，已知 $a_1$ 及 $a_2$ 两项。

数列 $a_n$ 满足递推式 $a_n=x \times a_{n-1}+ y \times a_{n-2}(n≥3).$

求 $\sum_{i=1}^na_i^2$

由于答案可能过大，对 $10^9+7$ 取模。

inputFormat:
第一行一个整数 $T$，即数据组数。

下面 $T$ 行，每行 $5$ 个整数，$n,a_1,a_2,x,y$，含义如上。

outputFormat: 共 $T$ 行，每行一个整数，即为每组数据的答案。


title: 公约数

background:
在收卷最后五分钟，pg发现了卷子反面还有一道大题。

题解：https://blog.csdn.net/kkkksc03/article/details/85008136

description:
求

[![](https://cdn.luogu.com.cn/upload/pic/33775.png)](https://www.luogu.org/paste/zltm8ddt)

由于答案可能过大，输出答案对$10^9+7$取模的值。

inputFormat:
第一行一个正整数$T$，为数据组数。

下面$T$行，每行$3$个整数，为$n,m,p$。

outputFormat: 共$T$行，每行一个整数，为答案。


title: 签到

description:
求$\sum_{i=1}^n \sum_{j=1}^n i \  xor \ j \in [\min(i,j),\max(i,j)]$

由于答案可能过大，输出答案对$10^9+7$取模的值。

inputFormat:
第一行，一个整数$T$，为数据组数。

下面$T$行，每行一个整数$n$。

outputFormat: 对于每行数据，输出答案。


title: 求和

background: QAQ

description:
给定数列$a_1...a_n$及$x_0$。

满足

$$f[i][j]=\begin{cases} a_i & j=0,i<=n \\ x_0 & j=0,i=n+1 \\ f[i][j-1]+f[i-1][j-1] & 0<i,j<=n+1,j<i \\ 0 & i<=j \\ \end{cases}$$

求

$$\sum_{i=0}^{n+1}\sum_{j=0}^{n+1}f[i][j]$$

~~但这样太水了~~

于是给出$m$个操作，每次将$a[l]...a[r] \  (0\le l,r \le n)$加$p$，对于每个操作，输出答案。

特别地，若$0$在$l...r$范围内，我们认为$x_0$也加$p$。

另外，在读入$m$个操作前，你也应该输出答案。

由于答案可能过大，输出答案对$1234567891$取模的结果。

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

下面一行$n+1$个整数，为$a_1...a_n$及$x_0$，且最后一个是$x_0$。

下面$m$行，每行$3$个整数$l,r,p$。

outputFormat: 共$m+1$行，每行一个整数，为答案。

hint:
共20个数据点。

对于第$i$个数据点

$$n,m=\lfloor ln^{12}i+\pi^5\rfloor,|a,x,p|\le \lfloor ln^{19}i+i^{\pi}\rfloor$$

保证$0 \le l\le r \le n$

~~想不到吧！~~


title: [USACO18DEC] Mixing Milk B

description:
农业，尤其是生产牛奶，是一个竞争激烈的行业。Farmer John 发现如果他不在牛奶生产工艺上有所创新，他的乳制品生意可能就会受到重创！

幸运的是，Farmer John 想出了一个好主意。他的三头获奖的乳牛，Bessie、Elsie 和 Mildred，各自产奶的口味有些许不同，他打算混合这三种牛奶调制出完美的口味。

为了混合这三种不同的牛奶，他拿来三个桶，其中分别装有三头奶牛所产的奶。这些桶可能有不同的容积，也可能并没有完全装满。然后他将桶 $1$ 的牛奶倒入桶 $2$，然后将桶 $2$ 中的牛奶倒入桶 $3$，然后将桶 $3$ 中的牛奶倒入桶 $1$，然后再将桶 $1$ 的牛奶倒入桶 $2$，如此周期性地操作，共计进行 $100$ 次（所以第 $100$ 次操作会是桶 $1$ 倒入桶 $2$）。当 Farmer John 将桶 $a$ 中的牛奶倒入桶 $b$ 时，他会倒出尽可能多的牛奶，直到桶 $a$ 被倒空或是桶 $b$ 被倒满。

请告诉 Farmer John 当他倒了 $100$ 次之后每个桶里将会有多少牛奶。

inputFormat: 输入文件的第一行包含两个空格分隔的整数：第一个桶的容积 $c_1$，以及第一个桶里的牛奶量 $m_1$。$c_1$ 和 $m_1$ 均为正，并且不超过 $10^9$。第二和第三行类似地包含第二和第三个桶地容积和牛奶量。

outputFormat: 输出三行，给出倒了 $100$ 次之后每个桶里的牛奶量。

hint:
在这个例子中，每倒一次之后每个桶里的牛奶量如下：

0. 初始状态：3  4  5
1. 桶1->2：0  7  5
2. 桶2->3：0  0  12
3. 桶3->1：10 0  2
4. 桶1->2：0  10 2
5. 桶2->3：0  0  12

（之后最后三个状态循环出现……）


title: [USACO18DEC] The Bucket List B

description:
Farmer John 正在考虑改变他给奶牛挤奶的时候分配牛奶桶的方式。他认为这最终能使得他使用数量更少的桶，然而他不清楚具体是多少。请帮助他！

Farmer John 有 $N$ 头奶牛（$1\le N\le 100$），方便起见编号为 $1\dots N$。 第 $i$ 头奶牛需要从时间 $s_i$ 到时间 $t_i$ 之间挤奶，并且挤奶过程中需要用到 $b_i$ 个桶。于是多头奶牛可能在同一时刻都在挤奶；如果这样，他们不能使用相同的桶。也就是说，一个在第 $i$ 头奶牛挤奶时用的桶不可以被任何在时间 $s_i$ 到时间 $t_i$ 之间挤奶的其他奶牛使用。当然，这个桶在这段时间之外可以被其他奶牛所使用。为了简化他的工作，FJ 保证在任一时刻，至多只有一头奶牛开始或是结束挤奶（也就是说，所有的 $s_i$ 和 $t_i$ 各不相同）。

FJ 有一个储藏室，里面有依次编号为 $1$、$2$、$3$、……的桶。在他的挤奶策略中，当某一头奶牛（比如说，奶牛 $i$）开始挤奶（在时间 $s_i$），FJ 就跑到储藏室取出编号最小的 $b_i$ 个桶分配给第i头奶牛用来挤奶。

请求出 FJ 需要在储藏室中存放多少个桶才能使得他能够顺利地给所有奶牛挤奶。

inputFormat: 输入的第一行包含 $N$。以下 $N$ 行，每行描述了一头奶牛，包含三个空格分隔的数 $s_i$，$t_i$，和 $b_i$。 其中 $s_i$ 和 $t_i$ 均为 $1\dots 1000$ 之间的整数，$b_i$ 为 $1\dots 10$ 之间的整数。

outputFormat: 输出一个整数，为 FJ 需要的桶的数量。

hint: 在这个例子中，FJ 需要 $4$ 个桶：他用桶 $1$ 和桶 $2$ 来给奶牛 $3$ 挤奶（从时间 $2$ 开始）。他用桶 $3$ 给奶牛 $1$ 挤奶（从时间 $4$ 开始）。当奶牛 $2$ 在时间 $8$ 开始挤奶时，桶 $1$ 和桶 $2$ 可以再次利用，然而桶 $3$ 不可以，所以他会使用桶 $1$、桶 $2$ 和桶 $4$。


title: [USACO18DEC] Back and Forth B

description:
Farmer John 有两个挤奶棚，每个挤奶棚里各有一个奶罐和一个装有 $10$ 个各种尺寸的桶的储物柜。他喜欢将在两个挤奶棚之间来回运送牛奶作为一种锻炼方式。

周一，Farmer John 量了恰好 $1000$ 加仑的牛奶放在第一个挤奶棚的奶罐里，又量了恰好 $1000$ 加仑的牛奶放在第二个挤奶棚的奶罐里。

周二，他从第一个挤奶棚里取出一个桶，并装满牛奶，然后将牛奶运到第二个挤奶棚，并将牛奶倒进奶罐。他把这个桶留在了第二个挤奶棚。

周三，他从第二个挤奶棚里取出一个桶（可能是周二留在这里的），并装满牛奶，然后将牛奶运到第一个挤奶棚，并将牛奶倒进奶罐。他把这个桶留在了第一个挤奶棚。

周四，他从第一个挤奶棚里取出一个桶（可能是周三留在这里的），并装满牛奶，然后将牛奶运到第二个挤奶棚，并将牛奶倒进奶罐。他把这个桶留在了第二个挤奶棚。

周五，他从第二个挤奶棚里取出一个桶（可能是周二或周四留在这里的），并装满牛奶，然后将牛奶运到第一个挤奶棚，并将牛奶倒进奶罐。他把这个桶留在了第一个挤奶棚。

此时 Farmer John 测量了第一个挤奶棚的奶罐里的牛奶。他总共可能得到多少种不同的读数？

inputFormat: 输入的第一行包含 $10$ 个整数，为第一个挤奶棚里初始的桶的容积。输入的第二行也包含 $10$ 个整数，为第二个挤奶棚里初始的桶的容积。 所有桶的容积均在 $1\dots 100$ 的范围内。

outputFormat: 输出 Farmer John 在周五之后测量第一个挤奶棚里的奶罐的牛奶时可能得到的读数的数量。

hint:
在这个例子中，最后第一个挤奶棚的奶罐中的牛奶量总共有 $5$ 种可能的结果：

$1000$：FJ 可以在每次往返的时候都携带同一个桶，从而不会改变第一个挤奶棚的奶罐的牛奶量。

$1003$：FJ 可以在周二运送 $2$ 个单位，周三 $5$ 个单位，周四 $1$ 个单位，周五 $1$ 个单位。

$1004$：FJ 可以在周二运送 $1$ 个单位，周三 $5$ 个单位，周四 $1$ 个单位，周五 $1$ 个单位。

$1007$：FJ 可以在周二运送 $1$ 个单位，周三 $5$ 个单位，周四 $2$ 个单位，周五 $5$ 个单位。

$1008$：FJ 可以在周二运送 $1$ 个单位，周三 $5$ 个单位，周四 $1$ 个单位，周五 $5$ 个单位。


title: [USACO18DEC] Convention S

description:
一场别开生面的牛吃草大会就要在 Farmer John 的农场举办了！

世界各地的奶牛将会到达当地的机场，前来参会并且吃草。具体地说，有 $N$ 头奶牛到达了机场（$1\le N\le 10^5$），其中奶牛 $i$ 在时间 $t_i$（$0\le t_i\le 10^9$）到达。Farmer John 安排了 $M$（$1\le M\le 10^5$）辆大巴来机场接这些奶牛。每辆大巴可以乘坐 $C$ 头奶牛（$1\le C\le N$）。Farmer John 正在机场等待奶牛们到来，并且准备安排到达的奶牛们乘坐大巴。当最后一头乘坐某辆大巴的奶牛到达的时候，这辆大巴就可以发车了。Farmer John 想要做一个优秀的主办者，所以并不想让奶牛们在机场等待过长的时间。如果 Farmer John 合理地协调这些大巴，等待时间最长的奶牛等待的时间的最小值是多少？一头奶牛的等待时间等于她的到达时间与她乘坐的大巴的发车时间之差。

输入保证 $MC\ge N$。

inputFormat: 输入的第一行包含三个空格分隔的整数 $N$，$M$，和 $C$。第二行包含 $N$ 个空格分隔的整数，表示每头奶牛到达的时间。

outputFormat: 输出一行，包含所有到达的奶牛中的最大等待时间的最小值。

hint: 如果两头时间 $1$ 到达的奶牛乘坐一辆巴士，时间 $3$ 和时间 $4$ 到达的奶牛乘坐乘坐第二辆，时间 $10$ 和时间 $14$ 到达的奶牛乘坐第三辆，那么等待时间最长的奶牛等待了 $4$ 个单位时间（时间 $10$ 到达的奶牛从时间 $10$ 等到了时间 $14$）。


title: [USACO18DEC] Convention II S

description:
虽然在接机上耽误了挺长时间，Farmer John 为吃草爱好牛们举行的大会至今为止都非常顺利。大会吸引了世界各地的奶牛。

然而大会的重头戏看起来却给 Farmer John 带来了一些新的安排上的困扰。他的农场上的一块非常小的牧草地出产一种据某些识货的奶牛说是世界上最美味的品种的草。因此，所有参会的 $N$ 头奶牛（$1\le N\le 10^5$）都想要品尝一下这种草。由于这块牧草地小到仅能容纳一头奶牛，这很有可能会导致排起长龙。

Farmer John 知道每头奶牛i计划到达这块特殊的牧草地的时间 $a_i$，以及当轮到她时，她计划品尝这种草花费的时间 $t_i$。当奶牛 $i$ 开始吃草时，她会在离开前花费全部 $t_i$ 的时间，此时其他到达的奶牛需要排队等候。如果这块牧草地空出来的时候多头奶牛同时在等候，那么资历最深的奶牛将会是下一头品尝鲜草的奶牛。在这里，恰好在另一头奶牛吃完草离开时到达的奶牛被认为是“在等待的”。类似地，如果当没有奶牛在吃草的时候有多头奶牛同时到达，那么资历最深的奶牛是下一头吃草的奶牛。

请帮助 FJ 计算所有奶牛中在队伍里等待的时间（$a_i$ 到这头奶牛开始吃草之间的时间）的最大值。

inputFormat: 输入的第一行包含 $N$。以下 $N$ 行按资历顺序给出了 $N$ 头奶牛的信息（资历最深的奶牛排在最前面）。每行包含一头奶牛的 $a_i$ 和 $t_i$。所有的 $t_i$ 为不超过 $10^4$ 的正整数，所有 $a_i$ 为不超过 $10^9$ 的正整数。

outputFormat: 输出所有奶牛中的最长等待时间。

hint: 在这个例子中，我们有 $5$ 头奶牛（按输入中的顺序编号为 $1\dots 5$）。奶牛 $4$ 最先到达（时间 $10$），在她吃完之前（时间 $27$）奶牛 $1$ 和奶牛 $3$ 都到达了。由于奶牛 $1$ 拥有较深的资历，所以她先吃，从她到达开始共计等待了 $2$ 个单位时间。她在时间 $30$ 结束吃草，随后奶牛 $3$ 开始吃草，从她到达开始共计等待了 $10$ 单位时间。在一段没有奶牛吃草的时间过后，奶牛 $5$ 到达，在她正在吃草的时间里奶牛 $2$ 也到达了，在 $5$ 个单位时间之后能够吃到草。相比到达时间等待最久的奶牛是奶牛 $3$。


title: [USACO18DEC] Mooyo Mooyo S

description:
由于手上（更确实的，蹄子上）有大把的空余时间，Farmer John 的农场里的奶牛经常玩电子游戏消磨时光。她们最爱的游戏之一是基于一款流行的电子游戏 Puyo Puyo 的奶牛版；名称当然叫做 Mooyo Mooyo。

Mooyo Mooyo 是在一块又高又窄的棋盘上进行的游戏，高 $N$（$1\le N\le 100$）格，宽 $10$ 格。 这是一个 $N=6$ 的棋盘的例子：

```
0000000000
0000000300
0054000300
1054502230
2211122220
1111111223
```

每个格子或者是空的（用 $0$ 表示），或者是九种颜色之一的干草捆（用字符 $1\dots 9$ 表示）。重力会使得干草捆下落，所以没有干草捆的下方是 $0$。

如果两个格子水平或垂直方向直接相邻，并且为同一种非 $0$ 颜色，那么这两个格子就属于同一个连通区域。任意时刻出现至少 $K$ 个格子构成的连通区域，其中的干草捆就会全部消失，变为 $0$。如果同时出现多个这样的连通区域，它们同时消失。随后，重力可能会导致干草捆向下落入某个变为 $0$ 的格子。由此形成的新的布局中，又可能出现至少 $K$ 个格子构成的连通区域。若如此，它们同样也会消失（如果又有多个这样的区域，则同时消失），然后重力又会使得剩下的方块下落，这一过程持续进行，直到不存在大小至少为K的连通区域为止。

给定一块 Mooyo Mooyo 棋盘的状态，输出这些过程发生之后最终的棋盘的图案。

inputFormat: 输入的第一行包含 $N$ 和 $K$（$1\le K\le 10N$）。以下 $N$ 行给出了棋盘的初始状态。

outputFormat: 输出 $N$ 行，描述最终的棋盘状态。


title: [USACO18DEC] Fine Dining G

description:
漫长的一天结束了，饥困交加的奶牛们准备返回牛棚。

农场由 $N$ 片牧场组成（$2\le N\le 5\times 10^4$），方便起见编号为 $1\dots N$。所有奶牛都要前往位于牧场 $N$ 的牛棚。其他 $N−1$ 片牧场中每片有一头奶牛。奶牛们可以通过 $M$ 条无向的小路在牧场之间移动（$1\le M\le 10^5$）。第i条小路连接牧场 $a_i$ 和 $b_i$，通过需要时间 $t_i$。每头奶牛都可以经过一些小路回到牛棚。

由于饥饿，奶牛们很乐于在他们回家的路上停留一段时间觅食。农场里有 $K$ 个有美味的干草捆，第 $i$ 个干草捆的美味值为 $y_i$。每头奶牛都想要在她回牛棚的路上在某一个干草捆处停留，但是她这样做仅当经过这个干草捆使她回牛棚的时间增加不超过这个干草捆的美味值。注意一头奶牛仅仅“正式地”在一个干草捆处因进食而停留，即使她的路径上经过其他放有干草捆的牧场；她会简单地无视其他的干草捆。

inputFormat:
输入的第一行包含三个空格分隔的整数 $N$，$M$ 和 $K$。以下 $M$ 行每行包含三个整数 $a_i$，$b_i$ 和 $t_i$，表示牧场 $a_i$ 和 $b_i$ 之间有一条需要 $t_i$ 时间通过的小路（$a_i$ 不等于 $b_i$，$t_i$ 为不超过 $10^4$ 的正整数）。

以下 $K$ 行，每行以两个整数描述了一个干草捆：该干草捆所在牧场的编号，以及它的美味值（一个不超过 $10^9$ 的正整数）。同一片牧场中可能会有多个干草捆。

outputFormat: 输出包含 $N-1$ 行。如果牧场 $i$ 里的奶牛可以在回牛棚的路上前往某一个干草捆并且在此进食，则第 $i$ 行为一个整数 $1$，否则为一个整数 $0$。

hint: 在这个例子中，牧场 $3$ 里的奶牛可以停留进食，因为她回去的时间仅会增加 $6$（从 $2$ 增加到 $8$），而这个增加量并没有超过干草捆的美味值 $7$。牧场 $2$ 里的奶牛显然可以吃掉牧场 $2$ 里的干草，因为这并不会导致她的最佳路径发生变化。对于牧场 $1$ 里的奶牛是一个有趣的情况，因为看起来她的最佳路径（$10$）可能会因为前去进食而有过大的增加量。然而，确实存在一条路径使得她可以前去干草捆处停留：先到牧场 $4$，然后去牧场 $2$（吃草），然后回到牧场 $4$。


title: [USACO18DEC] Cowpatibility G

description:
研究证明，有一个因素在两头奶牛能否作为朋友和谐共处这方面比其他任何因素都来得重要——她们是不是喜欢同一种口味的冰激凌！

Farmer John 的 $N$ 头奶牛（$2\le N\le 5\times 10^4$）各自列举了她们最喜欢的五种冰激凌口味的清单。为使这个清单更加精炼，每种可能的口味用一个不超过 $10^6$ 的正整数 $\texttt{ID}$ 表示。如果两头奶牛的清单上有至少一种共同的冰激凌口味，那么她们可以和谐共处。

请求出不能和谐共处的奶牛的对数。

inputFormat: 输入的第一行包含 $N$。以下 $N$ 行每行包含 $5$ 个整数（各不相同），表示一头奶牛最喜欢的冰激凌口味。

outputFormat: 输出不能和谐共处的奶牛的对数。

hint: 在这里，奶牛 $4$ 不能和奶牛 $1$、$2$、$3$ 中的任一头和谐共处，奶牛 $1$ 和奶牛 $3$ 也不能和谐共处。


title: [USACO18DEC] Teamwork G

description:
在 Farmer John 最喜欢的节日里，他想要给他的朋友们赠送一些礼物。由于他并不擅长包装礼物，他想要获得他的奶牛们的帮助。你可能能够想到，奶牛们本身也不是很擅长包装礼物，而 Farmer John 即将得到这一教训。

Farmer John 的 $N$ 头奶牛（$1\le N\le 10^4$）排成一行，方便起见依次编号为 $1\dots N$。奶牛 $i$ 的包装礼物的技能水平为 $s_i$。她们的技能水平可能参差不齐，所以 FJ 决定把她的奶牛们分成小组。每一组可以包含任意不超过 $K$ 头的连续的奶牛（$1\le K\le 10^3$），并且一头奶牛不能属于多于一个小组。由于奶牛们会互相学习，这一组中每一头奶牛的技能水平会变成这一组中水平最高的奶牛的技能水平。

请帮助 FJ 求出，在他合理地安排分组的情况下，可以达到的技能水平之和的最大值。

inputFormat: 输入的第一行包含 $N$ 和 $K$。以下 $N$ 行按照 $N$ 头奶牛的排列顺序依次给出她们的技能水平。技能水平是一个不超过 $10^5$ 的正整数。

outputFormat: 输出 FJ 通过将连续的奶牛进行分组可以达到的最大技能水平和。

hint: 在这个例子中，最优的方案是将前三头奶牛和后三头奶牛分别分为一组，中间的奶牛单独成为一组（注意一组的奶牛数量可以小于 $K$）。这样能够有效地将 $7$ 头奶牛的技能水平提高至 $15$、$15$、$15$、$9$、$10$、$10$、$10$，和为 $84$。


title: [USACO18DEC] Balance Beam P

description:
Bessie为了存钱给她的牛棚新建一间隔间，开始在当地的马戏团里表演，通过在平衡木上小心地来回走动来展示她卓越的平衡能力。

Bessie能够通过表演赚到的钱取决于她最终成功跳下平衡木的位置。平衡木上从左向右的位置记为 $ 0,1,\ldots,N+1 $ 。如果Bessie到达了位置 $ 0 $ 或是 $ N+1 $ ，她就会从平衡木的一端掉下去，遗憾地得不到报酬。

如果Bessie处在一个给定的位置 $ k $ ，她可以进行下面两项中的任意一项：

1. 投掷一枚硬币。如果背面朝上，她前往位置 $ k-1 $ ，如果正面朝上，她前往位置 $ k+1 $ （也就是说，每种可能性 $ 1/2 $ 的概率）。

2. 跳下平衡木，获得 $ f(k) $ 的报酬（ $ 0 \leq f(k) \leq 10^9 $ ）。

Bessie意识到她并不能保证结果能够得到某一特定数量的报酬，这是由于她的移动是由随机的掷硬币结果控制。然而，基于她的起始位置，她想要求出当她进行一系列最优的决定之后，她能够得到的期望报酬（“最优”指的是这些决定能够带来最高可能的期望报酬）。

例如，如果她的策略能够使她以 $ 1/2 $ 的概率获得 $ 10 $ 的报酬，$ 1/4 $ 的概率获得 $ 8 $ 的报酬，$ 1/4 $ 的概率获得 $ 0 $ 的报酬，那么她的期望报酬为加权平均值 $ 10 \times (1/2)+8 \times (1/4)+0 \times (1/4)=7 $ 。

inputFormat: 输入的第一行包含 $ N $ （ $ 2 \leq N \leq 10^5 $ ）。以下 $ N $ 行包含 $ f(1) \ldots f(N) $ 。

outputFormat: 输出 $ N $ 行。第 $ i $ 行输出 $ 10^5 $ 乘以Bessie从位置 $ i $ 开始使用最优策略能够获得的报酬的期望值，向下取整。


title: [USACO18DEC] Sort It Out P

description:
FJ 有 $ N $ （ $ 1 \leq N \leq 10^5 $ ）头奶牛（分别用 $ 1 \ldots N $ 编号）排成一行。FJ喜欢他的奶牛以升序排列，不幸的是现在她们的顺序被打乱了。在过去FJ曾经使用一些诸如“冒泡排序”的开创性的算法来使他的奶牛排好序，但今天他想偷个懒。取而代之，他会每次对着一头奶牛叫道“按顺序排好”。当一头奶牛被叫到的时候，她会确保自己在队伍中的顺序是正确的（从她的角度看来）。当有一头紧接在她右边的奶牛的编号比她小，她们就交换位置。然后，当有一头紧接在她左边的奶牛的编号比她大，她们就交换位置。这样这头奶牛就完成了“按顺序排好”，在这头奶牛看来左边的奶牛编号比她小，右边的奶牛编号比她大。

FJ想要选出这些奶牛的一个子集，然后遍历这个子集，依次对着每一头奶牛发号施令（按编号递增的顺序），重复这样直到所有N头奶牛排好顺序。例如，如果她选出了编号为 $ \{2,4,5\} $ 的奶牛的子集，那么他会喊叫奶牛2，然后是奶牛4，然后是奶牛5。如果 $ N $ 头奶牛此时仍未排好顺序他会再次对着这几头奶牛喊叫，如果有必要的话继续重复。

由于FJ不确定哪些奶牛比较专心，他想要使得这个子集最小。此外，他认为 $ K $ 是个幸运数字。请帮他求出满足重复喊叫可以使得所有奶牛排好顺序的最小子集之中字典序第 $ K $ 小的子集。

我们称 $ \{1, \ldots ,N\} $ 的一个子集 $ S $ 在字典序下小于子集 $ T $ ，当 $ S $ 的所有元素组成的序列（按升序排列）在字典序下小于 $ T $ 的所有元素组成的序列（按升序排列）。例如， $ \{1,3,6\} $ 在字典序下小于 $ \{1,4,5\} $ 。

inputFormat:
输入的第一行包含一个整数 $ N $ 。第二行包含一个整数 $ K $ （ $ 1 \leq K \leq 10^{18} $ ）。第三行包含 $ N $ 个空格分隔的整数，表示从左到右奶牛的编号。

保证存在至少 $ K $ 个符合要求的子集。

outputFormat: 第一行输出最小子集的大小。接下来输出字典序第 $ K $ 小的最小子集中奶牛的编号，每行一个数，升序排列。

hint:
开始的时候序列为 $ \mathtt{\:4\:\; 2\:\; 1\:\; 3\:} $ 。在FJ喊叫编号为 $ 1 $ 的奶牛之后，序列变为 $ \mathtt{\:1\:\; 4\:\; 2\:\; 3\:} $ 。在FJ喊叫编号为 $ 4 $ 的奶牛之后，序列变为 $ \mathtt{\:1\:\; 2\:\; 3\:\; 4\:} $ 。在这个时候，序列已经完成了排序。

## 子任务

对于占总分 $ 3/16 $ 的测试数据， $ N \leq 6 $ ，并且 $ K=1 $ 。

对于另外的占总分 $ 5/16 $ 的测试数据， $ K=1 $ 。

对于另外的占总分 $ 8/16 $ 的测试数据，没有其他限制。


title: [USACO18DEC] The Cow Gathering P

description:
奶牛们从世界各地聚集起来参加一场大型聚会。总共有 $ N $ 头奶牛， $ N-1 $ 对奶牛互为朋友。每头奶牛都可以通过一些朋友关系认识其他每头奶牛。

她们玩得很开心，但是现在到了她们应当离开的时间了，她们会一个接一个地离开。她们想要以某种顺序离开，使得只要至少还有两头奶牛尚未离开，所有尚未离开的奶牛都还有没有离开的朋友。此外，由于行李寄存的因素，有 $ M $ 对奶牛 $ (a_i,b_i) $ 必须满足奶牛 $ a_i $ 要比奶牛 $ b_i $ 先离开。注意奶牛 $ a_i $ 和奶牛 $ b_i $ 可能是朋友，也可能不是朋友。

帮助奶牛们求出，对于每一头奶牛，她是否可以成为最后一头离开的奶牛。可能会发生不存在满足上述要求的奶牛离开顺序的情况。

inputFormat:
输入的第 $ 1 $ 行包含两个空格分隔的整数 $ N $ 和 $ M $ 。

输入的第 $ 2 \leq i \leq N $ 行，每行包含两个整数 $ x_i $ 和 $ y_i $ ，满足 $ 1 \leq x_i $ ， $ y_i \leq N,xi \neq yi $ ，表示奶牛 $ x_i $ 和奶牛 $ y_i $ 是朋友关系。

输入的第 $ N+1 \leq i \leq N+M $ 行，每行包含两个整数 $ a_i $ 和 $ b_i $ ，满足 $ 1 \leq a_i,b_i \leq N $ ， $ a_i \neq b_i $ ，表示奶牛 $ a_i $ 必须比奶牛 $ b_i $ 先离开聚会。

输入保证 $ 1 \leq N,M \leq 10^5 $ 。对于占总分 $ 20\% $ 的测试数据，保证 $ N,M \leq 3000 $ 。

outputFormat: 输出 $ N $ 行，每行包含一个整数 $ d_i $ ，如果奶牛 $ i $ 可以成为最后一头离开的奶牛，则 $ d_i=1 $ ，否则 $ d_i=0 $ 。


title: 【模板】多项式快速插值

background: 模板题，无背景

description:
给出 $n$ 个点 $(x_i, y_i)$

求一个 $n-1$ 次的多项式 $f(x)$，使得 $f(x_i)\equiv y_i\pmod{998244353}$

inputFormat:
第一行输入一个正整数 $n$

接下来 $n$ 行每行两个整数 $x_i, y_i$

outputFormat:
共一行，从低到高输出 $f(x)$ 每一项的系数

若次数不够 $n-1$ 次，用 $0$ 补足

hint:
$1 \leqslant n \leqslant 100000$

$0 \leqslant x_i, y_i \lt 998244353$

保证 $x_i$ 互不相同

对于 $30\%$ 的数据，$n \leqslant 5000$

注意，你输出的数必须是 $[0, 998244353)$ 范围内的整数

数据使用 CYaRon 在五分钟之内生成。


title: Sum

description:
给定正整数 $n,\,r$ ，求：

$$\sum_{d=1}^{n}(-1)^{\lfloor d\sqrt{r} \rfloor}$$

inputFormat:
第一行一个数 $t$，表示有 $t$ 组测试数据。

接下来 $t$ 行，每行两个正整数 $n,\,r$ 。

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


title: Earthquake

description: 给定 $a,\,b,\,c$ ，求满足方程 $ax+by \leqslant c$ 的非负整数解个数。

inputFormat: 输入三个整数 $a,\,b,\,c$ 。

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


title: Fraction

description:
给你四个正整数 $a,\,b,\,c,\,d$ ，求一个最简分数 $\frac{p}{q}$ 满足 $\frac{a}{b} < \frac{p}{q} < \frac{c}{d}$。

若有多组解，输出 $q$ 最小的一组，若仍有多组解，输出 $p$ 最小的一组。

inputFormat: 本题有多组数据，有若干行，每行四个正整数，为每组数据的 $a,\,b,\,c,\,d$。

outputFormat: 每组数据各输出一行，如果答案是 $\frac{p}{q}$，则以 `p/q` 的格式输出。


title: 询问

background: zbw 被邀请至幼儿园给小朋友们出题。

description:
　现在 zbw 有 $n$ 个物品，编号从 $1 \sim n$，他会告诉你 $m$ 个条件，每个条件包含两个数 $x,y$，表示第 $x$ 个物品和第 $y$ 个物品是相同的。

 因为 zbw 特别赶时间，所以他保证**每次给出的条件都是有用的，也就是说，每次给出的条件无法由之前的条件推导得来。**

你需要回答有多少**种**不同的物品。

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

   之后 $m$ 行，每行两个数 $x,y$，表示第 $x$ 个物品和第 $y$ 个物品是相同的。

outputFormat: 一个整数，不同物品的数量。


title: 【模板】支配树

background: 模板题，无背景

description: 给定一张有向图，求从1号点出发，每个点能支配的点的个数（包括自己）

inputFormat:
第一行两个正整数$n,m$，表示点数和边数
接下来$m$行，每行输入两个整数$u,v$，表示有一条$u$到$v$的有向边

outputFormat: 一行输出$n$个整数，表示每个点能支配的点的个数


title: [COCI2009-2010#1] GENIJALAC

description:
 **译自 [COCI 2009.10](http://hsin.hr/coci/archive/2009_2010/) T5「[GENIJALAC](http://hsin.hr/coci/archive/2009_2010/contest1_tasks.pdf)」**

Mirko 发明了一台打乱机。机器接受一个 $N$ 列、无限行的纸带作为输入和输出。这 $N$ 列依次编号为 $1\ldots N$。

开始时，只有纸带的第一行写了数，其下方的每一行都是空白的。
在纸带的第一行中，每列有一个整数，第 $i$ 列上写了整数 $i$。
另外，Mirko 给出了一个打乱排列，这是一个长度为 $N$ 的排列 $s_1,$ $s_2,$ $\ldots,$ $s_N$。

有一个行指针，开始时指向首行。
每次运行该机器时，机器会将当前行（行指针所指向的行）位于第 $i$ 列的数放到下一行的第 $s_i$ 列上，$N$ 个数都放好后，指针将下移一行。

Mirko 运行了该机器无限次。现在 Mirko 将纸带的前 $C$ 列和后 $D$ 列剪掉了，我们称之为新的纸带。

试问：在新纸带的第 $A\sim B$ 行中，有多少行与新纸带的首行相同。

inputFormat:
第一行五个整数 $N, A, B, C, D$。
第二行 $N$ 个整数 $s_1,$ $s_2,$ $\ldots,$ $s_N$。

outputFormat: 一行，一个整数，表示在新纸带的第 $A\sim B$ 行中，有多少行与新纸带的首行相同。


title: [COCI2009-2010#2] POSLOZI

background:
 **译自 [COCI 2009.11](http://hsin.hr/coci/archive/2009_2010/) T5「[POSLOZI](http://hsin.hr/coci/archive/2009_2010/contest2_tasks.pdf)」**

给一个长度为 $N$ 的排列 $(1\le N\le 12)$。有 $M$ 种允许的修改方式 $(1\le M\le \frac{N\times (N-1)}{2})$，保证修改方式不重复，每种方式用 $L,$ $R$ 来表示，意为你可以将下标为 $L$ 的数与下标为 $R$ 的数交换。你可以修改该排列若干次，请给出一种修改方案，使原排列变为 $1,$ $2,$ $3,$ $\ldots,$ $N$。如果有多种方案，输出修改次数最少的方案。如果还有多种方案，输出任意一组即可。

inputFormat:
第一行两个整数 $N,$ $M$。
第二行 $N$ 个整数，表示排列。
接下来 $M$ 行，第 $i$ 行有两个整数，表示第 $i$ 种修改方式。

outputFormat:
首行一个整数 $\mathit{ope\_cnt}$，表示最少的修改次数。
接下来 $\mathit{ope\_cnt}$ 行，每行一个整数，表示进行第 $i$ 种修改。


title: [COCI2009-2010#2] PASIJANS

background: 原题时限 5s，这里根据洛谷评测机速度更改了时限。

description:
 **译自 [COCI 2009.11](http://hsin.hr/coci/archive/2009_2010/) T6「[PASIJANS](http://hsin.hr/coci/archive/2009_2010/contest2_tasks.pdf)」**

给出 $N$ 个已经塞了数进去的栈（每个栈中元素的数量可能不同），有一个空的「答案队列」，你每次可以「将一个栈的栈顶元素弹出，插入答案队列的末尾」，直至所有栈都清空。试求「字典序最小」的答案队列。

如果两个答案队列 $a, b$ （从队首往队尾数）前 $i-1$ 个数都相同，而 $a_i<b_i$，则我们称 $a$ 的字典序比 $b$ 的字典序小。

inputFormat:
第一行一个整数 $N$。
接下来 $M$ 行，每行第一个整数为 $L$，表示栈中元素的数量。接下来按照从栈顶到栈底的顺序依次给出 $L$ 个整数。

outputFormat: $\sum L$ 个整数，表示字典序最小的答案队列。


title: [COCI2009-2010#3] PLANETE

description:
 **译自 [COCI 2009.12](http://hsin.hr/coci/archive/2009_2010/) T6「[PLANETE](http://hsin.hr/coci/archive/2009_2010/contest3_tasks.pdf)」**

已知 $N$ 组记录，第 $i$ 组记录包含两个**无年份**的日期 $A_i,$ $B_i$（换言之，只有月和日）以及一个长度为 $M$ 的数组 $a_{i,1},$ $a_{i,2},$ $\ldots,$ $a_{i,M}$。

请给出关于 $x_1,$ $x_2,$ $\ldots,$ $x_N$ 的方程组

![](https://s2.ax1x.com/2019/01/06/FHitwd.png)

的任意一组解，无解则输出 $\texttt{-1}$。

inputFormat:
第一行两个整数 $N,M$。
接下来 $N$ 行，每行开头有四个整数，分别表示 $A_i$ 的日，$A_i$ 的月，$B_i$ 的日，$B_i$ 的月。接下来有 $M$ 个整数，表示 $a_{i,1},$ $a_{i,2},$ $\ldots,$ $a_{i,M}$。
保证输入的月、日合法。

outputFormat:
若有解，输出共 $M$ 行，每行一个整数，表示 $x_i$。
若无解则输出 $\texttt{-1}$。

hint: $1\le N,M\le 200,$ $0\le a_{i,j}\le 200,$ 保证输入的月、日合法。


title: [COCI2009-2010#4] OGRADA

description:
 **译自 [COCI 2010.02](http://hsin.hr/coci/archive/2009_2010/) T4「[OGRADA](http://hsin.hr/coci/archive/2009_2010/contest4_tasks.pdf)」**

Matija 的栅栏由 $N$ 条木板组成，从左到右依次编号为 $1\ldots N$。$i$ 号木板的高度为 $h_i$，每条木板的宽度是 $1\ \rm{cm}$。

Matija 想用一个宽度为 $X\ \rm{cm}$ 的滚筒刷来刷木板。使用滚筒刷时，要保证刷子**完全**接触栅栏（不能一部分接触一部分不接触）；另外，还要保证滚筒平行于地面。因此，每次涂色时，Matija 会在栅栏上选择连续的 $x$ 条木板，然后从下往上「刷」，一直刷到这 $x$ 条木板中最矮者的高度。

根据上述规则，有可能有一些木板没法用滚筒刷来刷，Matija 不得不用牙刷来「涂」剩下的部分。因此，请帮他求出他最少只需用牙刷「涂」多少平方厘米。他还想知道，在满足「涂」的面积最少的情况下，他最少要用滚筒刷「刷」多少次。

inputFormat:
第一行：$N,X$。
第二行：$h_1\ldots h_N$。

outputFormat:
两行。
第一行有一个整数，表示 Matija 最少需用牙刷涂多少平方厘米。
第二行有一个整数，表示最少要用滚筒刷「刷」多少次。


title: [COCI2009-2010#4] KABOOM

description:
 **译自 [COCI 2010.02](http://hsin.hr/coci/archive/2009_2010/) T5「[KABOOM](http://hsin.hr/coci/archive/2009_2010/contest4_tasks.pdf)」**

**注意本题的时间限制。**

Luka 在实验室里发现了一条奇怪的胶带。胶带分为 $N$ 段，从左到右依次编号为 $1\ldots N$。胶带厚度忽略不计。

胶带只能在两段的交点处弯折，且只能折叠 180°。

显然胶带有两面。胶带的一面涂满了粘性超大的胶，另一面则只有前 $A$ 段和后 $B$ 段涂了粘性超大的胶。

请问 Luka 有多少种折叠方式使他能还原现场（Luka 的手不会粘住胶带，但如果两个胶面粘一起了 Luka 就撕不开了）。答案对 $10301$ 取模。

inputFormat: 第一行，三个整数 $N,A,B$。

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


title: [COCI2009-2010#4] PALACINKE

description:
 **译自 [COCI 2010.02](http://hsin.hr/coci/archive/2009_2010/) T6「[PALACINKE](http://hsin.hr/coci/archive/2009_2010/contest4_tasks.pdf)」**

安娜有几个同学过来吃可丽饼，然而安娜忘了这事。当安娜发现时，留给她烤可丽饼的时间只剩下 $T$ 分钟了。她马上跑出去采购四样原材料：面粉 `B`，鸡蛋 `J`，牛奶 `M` 和果酱 `P`。

安娜周边有 $N$ 个路口，编号为 $1\ldots N$，还有 $M$ 条单向道路连接它们。已知每条路上的商店会卖哪些材料，保证每条路上的商店至少会卖（上述四种材料中）的一种。

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

安娜穿过一条道路时，如果她进入了这条路上的商店买东西，则她通过这条路耗时  $2$ 分钟，否则耗时  $1$ 分钟。即使她买完了所有原材料仍可以进店买东西。

安娜需要从 $1$ 开始，最终回到 $1$。

安娜需要在 $T$ 分钟内采购到四种原材料。请问她有多少种「采购方式」，答案对 $5557$ 取模。采购方式包含了她经过的结点的次序，以及她在每条路上买不买材料，但不计她在哪个商店买了什么。例如，当 $T=7$ 时，在上图中有 $5$ 种采购方式：

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

inputFormat:
第一行：$N,M$。
接下来 $M$ 行，每行两个整数 $u,v$ 和一个仅可能包含 `BJMP` 四种字符的字符串 $s$，$u,v$ 表示一条单向道路，$s$ 表示这条道路上的商店会卖哪些材料。保证没有两条单向道路相同（但可能有两条连接的结点相同，而方向相反的道路）。
第 $N+2$ 行：$T$。

outputFormat: 一行，一个答案，表示安娜有多少种采购方式。

hint:
$1\le N\le 25,$ $1\le M\le 500,$ $1\le T\le 10^9$.
保证没有两条单向道路相同（但可能有两条连接的结点相同，而方向相反的道路）。


title: [COCI2009-2010#5] ZUMA

description:
 **译自 [COCI 2010.03.06](http://hsin.hr/coci/archive/2009_2010/) T4「[ZUMA](http://hsin.hr/coci/archive/2009_2010/contest5_tasks.pdf)」**

Mirko 将 $N$ 颗弹子排成一排，依次编号为 $1\ldots N$。$i$ 号弹子的颜色为 $c_i$。他发现，如果他触摸 $\ge K$ 颗连续的弹子，且这些弹子的颜色相同，魔法会使这些弹子消失；此后，这 $K$ 颗弹子前面的弹子便与这 $K$ 颗弹子后面的弹子相邻。

Mirko 家里有很多弹子，他想在这 $N$ 颗弹子之间（也可以在开头的弹子前面或末尾的弹子后面）插入尽可能少的弹子，使得这 $N$ 颗弹子+插入的所有弹子消失。

inputFormat:
第一行：$N,K$。
第二行：$c_1\ldots c_N$。

outputFormat: 一行，一个整数，表示他至少要插入几颗弹子。


title: [COCI2009-2010#5] PROGRAM

description:
 **译自 [COCI 2010.03.06](http://hsin.hr/coci/archive/2009_2010/) T5「[PROGRAM](http://hsin.hr/coci/archive/2009_2010/contest5_tasks.pdf)」**

开始时，$\mathit{seq}$ 数组已清零。请注意 $\mathit{seq}$ 数组的第一个元素的下标是 0 而非 1。

```cpp
void something (int jump) {
  for (int i = 0; i < N; i += jump)
    ++seq[i];
}
```

Mirko 调用了 $\tt something$ 函数 $K$ 次，第 $i$ 次调用时 $\tt jump= \it X_i$。

接下来有 $Q$ 次查询，每次查询包含两个整数 $L_i,$ $R_i$，对于每组查询请输出 $\displaystyle\sum_{i=L_i}^{R_i}\mathit{seq}_i$。

inputFormat:
第一行：$N,K$。
接下来一行 $K$ 个整数，第 $i$ 个为 $X_i$。
第 $N+2$ 行：$Q$。
接下来 $Q$ 行：每行两个整数 $L_i,$ $R_i$。

outputFormat: 共 $Q$ 行，第 $i$ 行包含第 $i$ 组查询的答案。


title: [COCI2009-2010#6] HOLMES

description:
 **译自 [COCI 2010.03.20](http://hsin.hr/coci/archive/2009_2010/) T5「[HOLMES](http://hsin.hr/coci/archive/2009_2010/contest6_tasks.pdf)」**

有 $D$ 个事件，编号分别为 $1\ldots D$。

福尔摩斯有 $M$ 组形如 $A\rightarrow B$ 的推论，表示「如果事件 $A$ 发生，那么事件 $B$ 一定会发生」。请注意，这不代表「如果 $A$ 不发生，$B$ 就一定不会发生」。

福尔摩斯的这 $M$ 组推论可以形成链式结构，例如 $A\rightarrow B\rightarrow C$，但一定不会形成环，如 $A\rightarrow B\rightarrow C\rightarrow \dots \rightarrow A$。

已知事件 $S_1\ldots S_N$ 会发生，试求哪些事件一定会发生。

> Update: 原题题意不清（或者是我语文太差），补充一句，这样才能解释样例 1。对于一个事件 $X$，如果存在推论 $Y_1\rightarrow X,$ $Y_2\rightarrow X$，那么「事件 $X$ 一定会发生」当且仅当『「事件 $Y_1$ 一定会发生」或「事件 $Y_2$ 一定会发生」……』

inputFormat:
第一行：$D,M,N$。
接下来 $M$ 行：每行两个整数，表示一组推论 $A_i, B_i$。
接下来 $N$ 行：第 $i$ 行有一个整数 $S_i$。

outputFormat:
一行，若干个整数，表示一定会发生的事件。

~~以任意顺序输出均可~~ 请按照编号递增的顺序输出，传题人懒得写 SPJ

hint:
#### 样例说明 2
只知事件 3 发生，无法推出是事件 1 导致事件 3 发生还是事件 2 导致事件 3 发生。

#### 样例说明 3
事件 4 发生，则事件 2 和事件 3 至少有一者发生；
无论是何者发生，其条件都是事件 1 一定发生；
因为事件 1 一定发生，因此事件 2, 3 都一定发生。

#### 样例说明 4
事件 3 发生，则事件 1 和 2 一定有一者发生；
若事件 1 和 2 中有任意一者发生，则事件 4 一定会发生。

#### 数据范围与提示
$1\le D\le 1000,$ $1\le M\le 10^5,$ $1\le N,$ $X_i,$ $A_i,$ $B_i\le D$.


title: Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流

background:
Translated by @chen_zhe

幻想乡是一个被博丽大结界和虚幻与现实的境界所包围起来的一个美妙的地方。这里人和其他生物，例如妖怪、妖精等核平共处。

射命丸文（Syameimaru Aya）是一只鸦天狗，拥有操纵风的能力，已经活了千岁以上，是《文文。新闻》的主编，拥有着一本叫做《文花帖》的手账，记录幻想乡各地的大新闻。她不仅是天狗中速度最快的鸦天狗，思考能力非常强，以别人的几倍的思考速度思考，也拥有幻想乡最高等级的力量。

（译者内心 O.S.：远古的东方众都那么硬核科普的吗）

![](https://i.loli.net/2019/01/12/5c3970b446151.png)

description:
![](https://i.loli.net/2019/01/12/5c3971b885128.jpg)

（附注：文花帖8-8 西行寺幽幽子 「死蝶浮月」）

在接下来的 $n$ 天中，射命丸文将要拍摄幻想乡的少女的照片。并且要为第 $x$ 个少女拍摄至少 $G_x$ 张照片刊登在《文文。新闻》上。在第 $k$ 天的时候文文有 $C_k$ 位少女可以拍，且在这一天中对某个少女拍的照片数量 **必须** 在某个闭区间 $[L, R]$ 中。如果过少，文文就搞不出大新文；如果过多，就会有少女很安格瑞。

除此之外，因为拍照设备的原因，对于第 $i$ 天，每天的拍照数量不能超过 $D_i$ 张。在满足这些限定的条件下，文文希望拍到的照片尽可能地多。

由于文文需要去取材，因此她把这个任务交给了你，让你帮她去解决。

inputFormat:
本题有不定组数据，保证数据组数不超过 $10$。

第一行输入两个非负整数 $n$ 和 $m$，分别表示有 $n$ 天，有 $m$ 位少女。其中 $n \leq 365,m \leq 1000$。

接下来一行，有 $m$ 个整数 $G_0, G_1, \cdots, G_{m - 1}$。保证对于每一个 $G_x$，都满足 $G_x \in [0,10^5]$。

再接下来有 $n$ 段，第 $i$ 段的第一行有两个整数 $C _ i, D _ i\ (1 \leq C _ i \leq 300, 0 \leq D _ i \leq 30000)$。

接下来有 $C _ i$ 行，每一行有三个非负整数 $T,L,R\ (0 \leq T < m, 0 \leq L \leq R \leq 100)$，其中 $T$ 指的是少女的编号。**同一天中输入的少女编号可能有重复。**

outputFormat:
如果无法满足文文的需求，那么请输出 `-1`。

否则请输出在满足需求的情况下，文文最多能拍多少张照片。

注意每输出完一组数据之后，中间要空一行。


title: [TJOI2012] 炸弹

description:
在平面上有 $n$ 个炸弹 $[1 \ldots n]$ ，每个炸弹的爆炸范围是 $|x-x_i|+|y-yi| \leqslant R$ ，如果某个炸弹爆炸了，那么它将引燃它范围内的所有炸弹。

求出至少引燃多少炸弹才能使得所有炸弹都爆炸。

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

接下来 $n$ 行，每行两个整数 $x_i,y_i$ ，炸弹的坐标。

outputFormat: 输出一行一个整数 $k$ ，表示最少引燃的炸弹数。

hint:
$30\%$ 的数据， $1 \leqslant n \leqslant 1000$ ；

$100\%$ 的数据， $1 \leqslant n \leqslant 100000 \,,\, 0 \leqslant r \leqslant 10^9 \,,\, 0 \leqslant x_i,y_i \leqslant 10^9$ 。


title: [USACO05DEC] Knights of Ni S

description:
贝茜遇到了一件很麻烦的事：她无意中闯入了森林里的一座城堡，如果她想回家，就必须穿过这片由骑士们守护着的森林。为了能安全地离开，贝茜不得不按照骑士们的要求，在森林寻找一种特殊的灌木并带一棵给他们。

当然，贝茜想早点离开这可怕的森林，于是她必须尽快完成骑士们给的任务，贝茜随身带着这片森林的地图，地图上的森林被放入了直角坐标系，并按 $x,y $ 轴上的单位长度划分成了 $ W \times H\  ( 1 \leq W,H \leq 1000 )$ 块，贝茜在地图上查出了她自己以及骑士们所在的位置，当然地图上也标注了她所需要的灌木生长的区域。某些区域是不能通过的（比如说沼泽地，悬崖，以及食人兔的聚居地）。在没有找到灌木之前，贝茜不能通过骑士们所在的那个区域，为了确保她自己不会迷路，贝茜只向正北、正东、正南、正西四个方向移动（注意，她不会走对角线）。她要走整整一天，才能从某块区域走到与它相邻的那块区域。

贝茜希望你能帮她计算一下，她最少需要多少天才可脱离这可怕的地方？输入数据保证贝茜一定能完成骑士的任务。

inputFormat:
第一行输入 $2$ 个用空格隔开的整数，即题目中提到的 $ W,H $。

接下来输入贝茜持有的地图，每一行用若干个数字代表地图上对应行的地形。第一行描述了地图最北的那一排土地；最后一行描述的则是最南面的。相邻的数字所对应的区域是相邻的。如果地图的宽小于或等于 $40$，那每一行数字恰好对应了地图上的一排土地。如果地图的宽大于 $40$，那每行只会给出 $40$ 个数字，并且保证除了最后一行的每一行都包含恰好 $40$ 个数字。没有哪一行描述的区域分布在两个不同的行里。

地图上的数字所对应的地形：

- $0$：贝茜可以通过的空地；
- $1$：由于各种原因而不可通行的区域；
- $2$：贝茜现在所在的位置；
- $3$：骑士们的位置；
- $4$：长着贝茜需要的灌木的土地。

outputFormat: 输出一个正整数，即贝茜最少要花多少天才能完成骑士们给的任务。

hint:
这片森林的长为 $8$，宽为 $4$．贝茜的起始位置在第 $3$ 行，离骑士们不远。

贝茜可以按这样的路线完成骑士的任务：北，西，北，南，东，东，北，东，东，南，南。她在森林的西北角得到一株她需要的灌木，然后绕过障碍把它交给在东南方的骑士。


title: [USACO05DEC] Scales S

description:
约翰有一架用来称牛的体重的天平。与之配套的是 $ N \ ( 1 \leq N \leq 1000 ) $ 个已知质量的砝码（所有砝码质量的数值都在 $32$ 位带符号整数范围内）。

每次称牛时，他都把某头奶牛安置在天平的某一边，然后往天平另一边加砝码，直到天平平衡，于是此时砝码的总质量就是牛的质量（约翰不能把砝码放到奶牛的那边，因为奶牛不喜欢称体重，每当约翰把砝码放到她的蹄子底下，她就会尝试把砝码踢到约翰脸上）。

天平能承受的物体的质量不是无限的，当天平某一边物体的质量大于 $ C \ ( 1 \leq C \leq 2^{30} ) $ 时，天平就会被损坏。砝码按照它们质量的大小被排成一行。并且，这一行中从第 $3$ 个砝码开始，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和。

约翰想知道，用他所拥有的这些砝码以及这架天平，能称出的质量最大是多少。由于天平的最大承重能力为 $C$，他不能把所有砝码都放到天平上。

现在约翰告诉你每个砝码的质量，以及天平能承受的最大质量，你的任务是选出一些砝码，使它们的质量和在不压坏天平的前提下是所有组合中最大的。

inputFormat:
第 $1$ 行输入两个用空格隔开的正整数 $ N $ 和 $ C $。

第 $2$ 到 $ N+1 $ 行：每一行仅包含一个正整数，即某个砝码的质量。保证这些砝码的质量是一个不下降序列。

outputFormat: 输出一个正整数，表示用所给的砝码能称出的不压坏天平的最大质量。


title: Chino的试卷

background:
orz trz

Chino参加了萌妹子期末考试，又到了发试卷的时候了，但是，老师 $ygg$ 与 老师 $ggy$ 就怎样发试卷才最省力这一事发生了一些争论。现在，为了解决这一矛盾，你决定帮Chino用数据说话。

下面是 $ygg$ 老师的发试卷策略，请你帮他计算发完试卷要走的总路程。

description:
为了简化问题，我们规定Chino的同学们(妹子们)都参加了考试，且坐在一排，顺次位置的编号为 $1\sim n$，不妨规定位置 $i$, $j$ 之间的路程为 $|i - j|$。每张试卷上都有一个编号，代表要发给坐在这个编号的妹子。

$ygg$ 老师正在分发试卷。我们定义这个分发试卷的老师有两只手。刚开始，所有的试卷都在 $ygg$ 老师的左手，老师位于位置 $s$ 处。发试卷时，$ygg$ 老师会用右手拿起左手顶部的一张试卷。如果这是最后一张需要发的试卷，显然他别无选择，只能走到这张试卷主人的位置上去发这张试卷。如果他的左手还有试卷，那么他会进行一次比较，比较发左手顶部的那张试卷走的路程短，还是发右手那张试卷走的路程短。如果左手那张试卷走的路程短，他会把右手的试卷放到左手试卷的最下面，不然的话，他会直接发掉右手的试卷，并停留在刚发完这张试卷的位置。无论如何，他都会从左手再拿一张试卷，来进行下一步的决策，直到所有卷子都被发完。

现在，给定试卷的初始顺序序列$p$，以及老师的初始位置 $s$，问他要发完所有试卷走过的总路程是多少。

Chino想快速的知道答案，所以你要在$+4s$内完成这道题哦qwq

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

inputFormat:
- 第一行两个正整数 $n, s$  ，分别表示人数老师的初始位置。
- 第二行 $n$ 个非负整数，其中第 $i$ 个数表示 $p_i$ ，即从上往下数第 $i$ 张试卷要发到哪里去。

outputFormat: 输出一个整数，表示需要走的总路程。


title: Game

background: Justin摆弄着他的棋盘和棋...突然，他想到了一个非常好玩的游戏。

description:
棋盘可以看做是一个$N \times M$的网格，~~由于Justin太健壮了，~~所以他把$T$个格子弄坏了。也就是说，上面没法放棋子。

Justin想到的游戏是这样的：一开始，你可以选择棋盘的第一列的一些没有坏的格子，在上面各放上一枚棋子。然后，你可以执行依次以下操作若干次：

1. 选择一枚棋子，将其向上或者向下移动到**相邻**的一个好的且**没有其他棋子**的格子上。

2. 将所有棋子移动到下一列。若移动到下一列后有**任意一个**棋子落在坏的格子上，则不能执行此操作。

Justin现在给了你$Q$个问题，每一次给你一个$k_i$，询问你最多能在第一列上放多少枚棋子使得经过若干次操作后你能将所有棋子移动到最后一列，且**所有棋子加起来**最多执行$k_i$次1操作。

(感谢巨佬ywwywwyww 发现题目问题，现已修复。)

inputFormat:
第一行四个正整数:$N$,$M$,$T$,$Q$

接下来$T$行每行两个正整数$x_i$,$y_i$表示一个坏了的格子。

接下来$Q$行每行一个正整数$k_i$表示第$i$次Justin的询问。

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


title: 动态仙人掌 IV

background: 模板题。

description:
有 $n$ 个点，从 $1 \sim n$ 编号，第 $i$ 个点有一个权值 $w_i$，初始没有边。

有 $m$ 个操作，如果操作后，这个无向图的每个连通块都是个仙人掌，且不存在自环，那这个操作合法，否则不合法。不合法的操作忽略。一共有六种操作：

1. 在结点 $v,u$ 间连一条权值为 $w$ 的边；

2. 在结点 $v,u$ 间删掉一条权值为 $w$ 的边；

3. 把结点 $v$ 到结点 $u$ 的最短路上的每一个结点的权值都加上 $d$；

4. 把以结点 $v$ 为根，子仙人掌 $u$ 的每一个结点的权值都加上 $d$；

5. 查询结点 $v$ 到结点 $u$ 的最短路信息。

    输出两个用空格隔开的整数 $min,\sigma$，分别代表最短路上点权的最小值、和。

      如果没有路可到达则 $min=-1,\sigma =-1$。

      如果最短路不唯一则 $min=-2,\sigma =-2$。

6. 查询以结点 $v$ 为根，子仙人掌$u$的信息。

    输出两个用空格隔开的整数 $min,\sigma$，分别代表子仙人掌 $u$ 中点权的最小值、和。

    如果 $v,u$ 不连通则 $min=-1,\sigma =-1$。

以结点 $v$ 为根，子仙人掌 $u$ 的定义是，删掉 $v$ 到 $u$ 之间的所有简单路径上的边之后，$u$ 所在的连通块。

inputFormat:
第一行两个用空格隔开的正整数 $n,m$ 表示一共有 $n$ 个结点，$m$ 个操作。

接下来一行 $n$ 个正整数，第 $i$ 个正整数为 $w_i$。

接下来 $m$ 行，每行代表一个操作，每行前三个整数：$opt_i,v_i,u_i$

若 $opt_i \in \{ 1,2,3,4 \}$ 则接下来再输入一个整数，否则此行结束。

outputFormat: 对于操作 $5$、$6$，输出相应的结果。

hint:
【数据范围】
对于 $100\%$ 的数据，$1 \leq n \leq 50000, 1 \leq m \leq 250000$

保证操作 $1$、$2$ 中的 $w$ 满足 $1 \leq w \leq 10000$，所以关于边权的计算不会超出 $32$ 位有符号整数范围。

保证初始的 $w_i$ 不超过 $10^9$，保证所有操作 $3$、$4$ 中的 $d$ 之和不超过 $10^9$。


title: Function

background: ${\rm CYJian}$最近想起了[水の三角](https://www.luogu.org/problemnew/show/P5014)，他觉得太水了，于是想了一个更加有意思的版本。

description:
给你$N$和$K$，请你求出：

$$\sum_{i=1}^{K}f[N][i] \ (\bmod\ 998244353)$$

其中：

$$f[i][j]=f[i-1][j]+f[i][j-1]+f[i-1][j-1](i>1,j \leq i)$$

$$f[1][1] = 1 \qquad f[i][0] = 0 \qquad f[i][j]=0(j>i)$$

inputFormat: 第一行两个正整数表示$N$，$K$。

outputFormat: 一行，输出上面式子的值。

hint:
对于$10\%$的数据：$1 \leq N \leq 10^3 \qquad 1 \leq K \leq 10^2$

对于$30\%$的数据：$1 \leq N \leq 10^6 \qquad 1 \leq K \leq 10^2$

对于$50\%$的数据：$1 \leq N \leq 10^{18} \qquad 1 \leq K \leq 10^2$

对于另$20\%$的数据：$1 \leq N \leq 10^6 \qquad 1 \leq K \leq 10^3$

对于$100\%$的数据：$1 \leq N \leq 10^{18} \qquad 1 \leq K \leq 10^3$

保证$K \leq N$

Upd：时限改为了：第$1$~$35$的测试点时限为$600ms$，第$36$~$50$的测试点时限为$400ms$。


title: 【模板】多项式快速幂

background:
[加强版传送门](https://www.luogu.com.cn/problem/P5273)

模板题，无背景

description:
给定一个 $n-1$ 次多项式 $A(x)$，求一个在 $\bmod\ x^n$ 意义下的多项式 $B(x)$，使得 $B(x) \equiv (A(x))^k \ (\bmod\ x^n)$。

多项式的系数在 $\bmod\ 998244353$ 的意义下进行运算。

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

接下来 $n$ 个整数，依次表示 $A(x)$ 的系数 $a_0, a_1,...,a_{n-1}$。

outputFormat: 输出 $n$ 个整数，依次表示 $B(x)$ 的前 $n$ 项系数 $b_0, b_1,...,b_{n-1}$ 在模 $998244353$ 意义下的最小自然数值。


title: 【模板】多项式开根

background: 模板题，无背景

description:
给定一个 $n-1$ 次多项式 $A(x)$，求一个在 ${} \bmod x^n$ 意义下的多项式 $B(x)$，使得 $B^2(x) \equiv A(x) \pmod{x^n}$。若有多解，请取零次项系数较小的作为答案。

多项式的系数在 ${}\bmod 998244353$ 的意义下进行运算。

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

接下来 $n$ 个整数，依次表示多项式的系数 $a_0, a_1, \dots, a_{n-1}$。

保证 $a_0 = 1$。

outputFormat: 输出 $n$ 个整数，表示答案多项式的系数 $b_0, b_1, \dots, b_{n-1}$。


title: 冬至

background: >春生秋死，不知冬至。

description:
给你 $1 \sim k$ 的整数，你可以选其中的数，组成长度为 $n$ 的串（可重复使用），且不能有子串是 $1\sim k$ 的排列。

问方案总数模 $998244353$。

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

outputFormat: 一行一个整数，表示方案总数模 $998244353$ 的值。

hint:
【样例 1 解释】
可以组成的合法排列有：$1,1,1$ 和 $2,2,2$
其余均不合法，都含有 $1 \sim 2$ 的排列，因此答案为 $2$。

【样例 2 解释】
总共有 $7^7$ 种情况，其中有 $7!$ 个不合法（即 $1 \sim 7$ 的排列情况数），答案为 $7^7-7!$，即 $818503$。

【数据范围】
对于 $100\%$ 的数据，$1\le k \le 10^4$，$1\le n \le 10^9$。

By：毕克


title: [USACO19JAN] Cow Poetry G

background: USACO19年一月金组第一题

description:
不为Farmer John所知的是，Bessie还热衷于资助艺术创作！最近，她开始研究许多伟大的诗人们，而现在，她想要尝试创作一些属于自己的诗歌了。
Bessie认识N（1≤N≤5000）个单词，她想要将她们写进她的诗。Bessie已经计算了她认识的每个单词的长度，以音节为单位，并且她将这些单词划分成了不同的“韵部”。每个单词仅与属于同一韵部的其他单词押韵。

Bessie的每首诗由M行组成（1≤M≤10^5），每一行必须由K（1≤K≤5000）个音节构成。此外，Bessie的诗必须遵循某个指定的押韵模式。

Bessie想要知道她可以写出多少首符合限制条件的不同的诗。

inputFormat:
输入的第一行包含N、M和K。
以下N行，每行包含两个整数si（1≤si≤K）和ci（1≤ci≤N）。这表示Bessie认识一个长度（以音节为单位）为si、属于韵部ci的单词。

最后M行描述了Bessie想要的押韵模式，每行包含一个大写字母ei。所有押韵模式等于ei的行必须以同一韵部的单词结尾。不同ei值的行并非必须以不同的韵部的单词结尾。

outputFormat: 输出Bessie可以写出的满足这些限制的不同的诗的数量。由于这个数字可能非常大，请计算这个数对1,000,000,007取余的结果。

hint: 在这个例子中，Bessie认识三个单词。前两个单词押韵，长度分别为三个音节和四个音节，最后一个单词长度为三个音节，不与其他单词押韵。她想要写一首三行的诗，每行包含十个音节，并且第一行和最后一行押韵。共有960首这样的诗。以下是一首满足要求的诗（其中1，2、3分别代表第一个、第二个、第三个单词）：121 123 321。


title: [USACO19JAN] Grass Planting S

background: USACO一月月赛银组第一题

description:
到了一年中Farmer John在他的草地里种草的时间了。整个农场由N块草地组成（1≤N≤10^5），方便起见编号为1…N，由N−1条双向的小路连接，每块草地都可以经过一些小路到达其他所有的草地。
Farmer John当然可以在每块草地里种不同种类的草，但是他想要使得使用的草的种类数最小，因为他用的草的种类数越多，他就需要负担更高的花费。

不幸的是，他的奶牛们对选择农场上的草表现得十分苛刻。如果两块相邻（由一条小路直接相连）的草地种了同一种草，或者即使是两块接近相邻（均可由一条小路直接连向同一块草地）的草地，那么奶牛们就会抱怨她们进餐的选择不够多样。Farmer John能做的只能是抱怨这些奶牛，因为他知道她们不能被满足的时候会制造多大的麻烦。

请帮助Farmer John求出他的整个农场所需要的最少的草的种类数。

inputFormat: 输入的第一行包含N。以下N−1行每行描述了一条小路连接的两块草地。

outputFormat: 输出Farmer John需要使用的最少的草的种类数

hint: 在这个简单的例子中，4块草地以一条直线的形式相连。最少需要三种草。例如，Farmer John可以用草A，B和C将草地按A - B - C - A的方式播种。


title: [USACO19JAN] Icy Perimeter S

background: USACO一月月赛银组第二题

description:
Farmer John要开始他的冰激凌生意了！他制造了一台可以生产冰激凌球的机器，然而不幸的是形状不太规则，所以他现在希望优化一下这台机器，使其产出的冰激凌球的形状更加合理。
机器生产出的冰激凌的形状可以用一个N×N（1≤N≤1000）的矩形图案表示，例如：

```
##....
....#.
.#..#.
.#####
...###
....##
```

每个'.'字符表示空的区域，每个'#'字符表示一块1×1的正方形格子大小的冰激凌。

不幸的是，机器当前工作得并不是很正常，可能会生产出多个互不相连的冰激凌球（上图中有两个）。一个冰激凌球是连通的，如果其中每个冰激凌的正方形格子都可以从这个冰激凌球中其他所有的冰激凌格子出发重复地前往东、南、西、北四个方向上相邻的冰激凌格子所到达。

Farmer John想要求出他的面积最大的冰激凌球的面积和周长。冰激凌球的面积就是这个冰激凌球中'#'的数量。如果有多个冰激凌球并列面积最大，他想要知道其中周长最小的冰激凌球的周长。在上图中，小的冰激凌球的面积为2，周长为6，大的冰激凌球的面积为13，周长为22。

注意一个冰激凌球可能在中间有“洞”（由冰激凌包围着的空的区域）。如果这样，洞的边界同样计入冰激凌球的周长。冰激凌球也可能出现在被其他冰激凌球包围的区域内，在这种情况下它们计为不同的冰激凌球。例如，以下这种情况包括一个面积为1的冰激凌球，被包围在一个面积为16的冰激凌球内：
```
#####
#...#
#.#.#
#...#
#####
```
同时求得冰激凌球的面积和周长十分重要，因为Farmer John最终想要最小化周长与面积的比值，他称这是他的冰激凌的“冰周率”。当这个比率较小的时候，冰激凌化得比较慢，因为此时冰激凌单位质量的表面积较小。

inputFormat: 输入的第一行包含N，以下N行描述了机器的生产结果。其中至少出现一个'#'字符。

outputFormat: 输出一行，包含两个空格分隔的整数，第一个数为最大的冰激凌球的面积，第二个数为它的周长。如果多个冰激凌球并列面积最大，输出其中周长最小的那一个的信息。


title: [USACO19JAN] Mountain View S

background: USACO 2019 年一月月赛银组第三题

description:
从农场里奶牛 Bessie 的牧草地向远端眺望，可以看到巍峨壮丽的山脉绵延在地平线上。山脉里由 $N$座山峰（$1≤N≤10^5$）。如果我们把 Bessie 的视野想象成 $xy$ 平面，那么每座山峰都是一个底边在 $x$ 轴上的三角形。山峰的两腰均与底边成 $45$ 度角，所以山峰的峰顶是一个直角。于是山峰 $i$ 可以由它的峰顶坐标 $(x_i,y_i)$ 精确描述。没有两座山峰有完全相同的峰顶坐标。

Bessie 尝试数清所有的山峰，然而由于它们几乎是相同的颜色，所以如果一座山峰的峰顶在另一座山峰的三角形区域的边界上或是内部，她就无法看清。

请求出 Bessie 能够看见的不同的山峰的峰顶的数量，也就是山峰的数量。

inputFormat: 输入的第一行包含 $N$。以下 $N$ 行每行包含 $x_i$（$0\le x_i\le 10^9$）和$y_i$（$1\le y_i\le 10^9$），描述一座山峰的峰顶的坐标。

outputFormat: 输出 Bessie 能够分辨出的山峰的数量。

hint: 在这个例子中，Bessie 能够看见第一座和最后一座山峰。第二座山峰被第一座山峰掩盖了。


title: [USACO19JAN] Sleepy Cow Sorting G

background: USACO 19年一月月赛金组第二题

description:
Farmer John正在尝试将他的 $N$ 头奶牛（$1\le N\le 10^5$），方便起见编号为 $1\ldots N$，在她们前往牧草地吃早餐之前排好顺序。

当前，这些奶牛以 $p_1,p_2,p_3,\ldots,p_N$ 的顺序排成一行，Farmer John站在奶牛 $p_1$ 前面。他想要重新排列这些奶牛，使得她们的顺序变为 $1,2,3,\ldots,N$，奶牛 $1$ 在 Farmer John 旁边。

今天奶牛们有些困倦，所以任何时刻都只有直接面向 Farmer John 的奶牛会注意听 Farmer John 的指令。每一次他可以命令这头奶牛沿着队伍向后移动 $k$ 步，$k$ 可以是 $1$ 到 $N−1$ 之间的任意数。她经过的 $k$ 头奶牛会向前移动，腾出空间使得她能够插入到队伍中这些奶牛之后的位置。

例如，假设 $N=4$，奶牛们开始时是这样的顺序：

```plain
 FJ: 4 3 2 1
```

唯一注意 FJ 指令的奶牛是奶牛 $4$。当他命令她向队伍后移动 $2$ 步之后，队伍的顺序会变成：

```plain
 FJ: 3 2 4 1
```

现在唯一注意 FJ 指令的奶牛是奶牛 $3$，所以第二次他可以给奶牛 $3$ 下命令，如此进行直到奶牛们排好了顺序。

Farmer John 急欲完成排序，这样他就可以回到他的农舍里享用他自己的早餐了。请帮助他求出一个操作序列，使得能够用最少的操作次数将奶牛们排好顺序。

inputFormat: 输入的第一行包含 $N$。第二行包含 $N$ 个空格分隔的整数：$p_1,p_2,p_3,\ldots,p_N$，表示奶牛们的起始顺序。

outputFormat:
输出的第一行包含一个整数 $K$，为将奶牛们排好顺序所需的最小操作次数。

第二行包含 $K$ 个空格分隔的整数，$c_1,c_2,\ldots,c_K$，每个数均在 $1\ldots N−1$ 之间。如果第 $i$ 次操作 FJ 命令面向他的奶牛向队伍后移动 $c_i$ 步，那么 $K$ 次操作过后奶牛们应该排好了顺序。

如果存在多种最优的操作序列，你的程序可以输出其中任何一种（不过实际上是唯一解）。


title: [USACO19JAN] Shortcut G

background: USACO 19年一月月赛金组第三题

description:
每天晚上，Farmer John都会敲响一个巨大的铃铛，召唤他的奶牛们前来牛棚享用晚餐。奶牛们都急切地想要前往牛棚，所以她们都会沿着最短的路径行走。
农场可以描述为N块草地（1≤N≤10,000），方便起见编号为1…N，牛棚位于草地1。草地之间由M条双向的小路连接（N−1≤M≤50,000）。每条小路有其通过时间，从每块草地出发都存在一条由一些小路组成的路径可以到达牛棚。

草地i中有ci头奶牛。当她们听到晚餐铃时，这些奶牛都沿着一条消耗最少时间的路径前往牛棚。如果有多条路径并列消耗时间最少，奶牛们会选择其中“字典序”最小的路径（也就是说，她们通过在两条路径第一次出现分支的位置优先选择经过编号较小的草地的方式来打破并列关系，所以经过草地7、3、6、1的路径会优先于经过7、5、1的路径，如果它们所消耗的时间相同）。

Farmer John担心牛棚距离某些草地太远。他计算了每头奶牛路上的时间，将所有奶牛消耗的时间相加，称这个和为总移动时间。他想要通过额外添加一条从牛棚（草地1）连接到某块他选择的其他草地的、通过时间为T（1≤T≤10,000）的“近道”来尽可能地减少总移动时间。当一头奶牛在她平时前往牛棚的路上偶然看见这条近道时，如果这条近道能够使她更快地到达牛棚，她就会走这条路。否则，一头奶牛会仍然沿着原来的路径行走，即使使用这条近道可能会减少她的移动时间。

请帮助Farmer John求出通过添加一条近道能够达到的总移动时间减少量的最大值。

inputFormat: 输入的第一行包含N、M和T。以下N行包含c1…cN，均为0…10,000范围内的整数。以下M行，每行由三个整数a，b和t描述了一条小路，这条小路连接了草地a和b，通过时间为t。所有的通过时间在1…25,000范围内。

outputFormat: 输出Farmer John可以达到的总移动时间的最大减少量。


title: [USACO19JAN] Redistricting P

background: USACO 19 年一月月赛铂金组第一题。

description:
奶牛们的特大城市，牛都，要进行重新分区了！——这总是一个在居住在这里的两大主要种族（荷斯坦牛和更赛牛）之间富有争议的政治事件，因为两大种族都想要在牛都政府中保持足够的影响力。

牛都的大都市圈由一列 $n$ 块牧草地组成，每块里有一头奶牛，均为荷斯坦牛 (Holstein) 和更赛牛 (Guernsey) 之一。

牛都政府想要将大都市圈划分为若干个连续的区，使得每个区至少包含一块牧草地且至多包含 $k$ 块牧草地，并且每块牧草地恰好属于一个区。由于政府当前由荷斯坦牛控制，她们想要找到一种分区方式能够最小化更赛牛较多或者均势的区的数量（如果更赛牛的数量与荷斯坦牛的数量相等那么这个区就是均势的）。

有一个关心政治的更赛牛团体想要知道政府的分区计划可能会对她们造成多少损害。帮助她们求出最坏情况，也就是更赛牛较多或是均势的区的最小可能的数量。

inputFormat:
输入的第一行是用空格隔开的两个整数，分别代表牧草地的个数 $n$ 和每个区包含草地的上限 $k$。

输入的第二行是一个长度为 $n$ 的字符串 $s$，$s$ 中只含字符 `H` 和 `G`。若 $s$ 的第 $i$ 个字符是 `H`，则代表第 $i$ 块草地上的奶牛是荷斯坦牛，否则是更赛牛。

outputFormat: 输出一行一个整数，代表更赛牛较多或者优势区的最小可能数量。

hint:
### 样例解释

一种可能的划分方式是 $[1],~[2, 3],~[4, 5],~[6, 7]$。第二、四个区是均势的区，第三个区是更赛牛优势的区。

### 数据范围

对于 $100\%$ 的数据，保证 $1 \leq k \leq n \leq 3 \times 10^5$，$s$ 的长度为 $n$，且只含字符 `H` 和 `G`。


title: [USACO19JAN] Exercise Route P

background: USACO 19年一月月赛铂金组第二题。

description:
奶牛 Bessie 意识到为了保持好的体形她需要更多地进行锻炼。她需要你帮助她选择在农场里每天用来晨跑的路线。 农场由 $n$ 块草地组成，方便起见编号为 $1\sim n$，由 $m$ 条双向的小路连接。作为一种遵循规律的生物，奶牛们倾向于使用其中特定的 $n−1$ 条小路作为她们日常在草地之间移动的路线——她们管这些叫“常规的”小路。从每块草地出发都可以仅通过常规的小路到达所有其他草地。

为了使她的晨跑更加有趣，Bessie 觉得她应该选择一条包含一些非常规的小路的路线。然而，使用常规的小路能够使她感到舒适，所以她不是很想在她的路线中使用过多非常规的小路。经过一些思考，她认为一条好的路线应当形成一个简单环（能够不经过任何草地超过一次的情况下回到起点），其中包含恰好两条非常规的小路。

请帮助 Bessie 计算她可以使用的好的路线的数量。两条路线被认为是相同的，如果它们包含的小路的集合相等。

inputFormat: 输入的第一行包含 $n$ 和 $m$。以下 $m$ 行每行包含两个整数 $a_i$ 和 $b_i$，描述了一条小路的两端。其中前 $(n−1)$ 条是常规的小路。

outputFormat: 输出一行一个整数表示 Bessie 可以选择的路线的总数。

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

对于全部的测试点，保证 $1 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 2 \times 10^5$，$m \geq n - 1$，$1 \leq a_i, b_i \leq n$。


title: [USACO19JAN] Train Tracking 2 P

background: USACO 2019 一月月赛铂金组第三题

description:
每天特快列车都会经过农场。列车有 $N$ 节车厢（$1 \le N \le 10^5$），每节车厢上有一个 $1$ 到 $10^9$ 之间的正整数编号；不同的车厢可能会有相同的编号。
平时，Bessie 会观察驶过的列车，记录车厢的编号。但是今天雾实在太浓了，Bessie 一个编号也看不见！幸运的是，她从城市里某个可靠的信息源获知了列车编号序列的所有滑动窗口中的最小值。具体地说，她得到了一个正整数 $K$ ，以及 $N-K+1$ 个正整数 $c_1,…,c_{N+1-K}$ ，其中 $c_i$ 是车厢 $i,i+1,…,i+K-1$ 之中编号的最小值。

帮助 Bessie 求出满足所有滑动窗口最小值的对每节车厢进行编号的方法数量。由于这个数字可能非常大，只要你求出这个数字对 $10^9+7$ 取余的结果 Bessie 就满意了。

Bessie 的消息是完全可靠的；也就是说，保证存在至少一种符合要求的编号方式。

inputFormat: 输入的第一行包含两个空格分隔的整数 $N$ 和 $K$ 。余下的行包含所有的滑动窗口最小值 $c_1,…,c_{N+1-K}$ ，每行一个数。

outputFormat: 输出一个整数：对每节车厢给予一个不超过 $10^9$ 的正整数编号的方法数量对 $10^9+7$ 取余的结果，满足车厢 $i,i+1,…,i+K-1$ 之中编号的最小值等于 $c_i$，对于 $1 \le i \le N - K+1$ 均成立。


title: 无聊的水题 II

background: 出题人过菜，只会出这种题。

description:
DLS 是一个喜欢玩游戏的男生。

今天他从朋友那里看到了 $N$ 件武器，其中第 $i$ 件武器的威力值为$i$。

他观察了这 $N$ 件武器许久，打算买下其中若干件武器，但他想用买下的武器的威力值组合出任意威力值，其中每一件武器已经的威力值可以叠加，甚至可以减去。
例如一个威力值为 $3$ 的武器，可以组合成的威力值为 $\dots,-6,-3,0,3,6,\dots$。

他想找出所有满足以上条件的买下装备的方案，但方案数量实在太多了。你能帮他计算一下吗？
答案对 $10^9+7$ 取模。

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

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


title: 无聊的水题 I

background: 出题人过菜，只会出这种题，稍微有点卡常。

description:
DLS 喜欢上树。
但是他并不想把一道数据结构题出到树上，他喜欢计 Tree。

这一天，他想自己造一棵树，他手头有 $N$ 个树的节点，标号为 $1 \sim N$，他会在它们之间连边，我们定义两颗树不同，当且仅当一对节点在一棵树中有连边，另一棵树中没有连边。
但他不喜欢一棵太多分叉的树，于是他想让这棵树的节点中最大的度数为 $M$。

DLS 由于不太擅长理科，所以希望你帮他计算有多少棵这样的树。
答案对 $998244353$ 取模。

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

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


title: DLS 采花

background: 超水的签到题

description:
DLS 有 $N$ 个花田，每个花田里有 $a_i$ 朵花。

DLS 喜欢稀奇古怪的花田，他希望重新排列花田，然后去采花。
但 DLS 采花又有一个癖好：他会从左往右采花。
若当前采到第 $i$ 个花田，在之前有一个花田的花的数量，是第 $i$ 个花田的花的数量的因子的话，那么 DLS 不会采这个花田的花。

现在，DLS 想知道对于所有排列花田的方案，他能够采到的花的数量的和是多少。
由于答案会比较大，请对 $998244353$ 取模。

inputFormat:
第一行一个正整数 $N$。
第二行是一个长度为 $N$ 的序列 $a$。

outputFormat: 共一行，表示所有方案中采花的数量和对 $998244353$ 取模的结果。


title: Candies

background: JerryC有一大袋糖果，他正以$1\ t/ms$的速度食用着这一袋糖果......

description:
JerryC的糖果有$N$箱(两两之间不同)。他一开始想挑$M$箱出来，但是觉得吃起来不过瘾，所以又想要多拿一些出来。由于他比较喜欢数字$K$，所以只要拿出来的糖的量$x(x \ge M)$满足：$x \equiv M\ (\bmod\ K)$，JerryC就会得到满足感。

求有多少种方案使得JerryC得到满足感。请输出方案数$\bmod\ 1004535809$的结果。

inputFormat: 一行三个非负整数$N$,$M$,$K$。

outputFormat: 一行一个非负整数，表示方案数$\bmod\ 1004535809$的结果。


title: Product

background: ${\rm CYJian}$："听说$gcd$和$\sum$套起来比较好玩？？那我就......"

description:
${\rm CYJian}$最近闲的玩起了$gcd$。。他想到了一个非常简单而有意思的式子：

$$\prod_{i=1}^N\prod_{j=1}^N\frac{lcm(i,j)}{gcd(i,j)}\ (\bmod\ 104857601)$$

${\rm CYJian}$已经算出来这个式子的值了。现在请你帮他验算一下吧。${\rm CYJian}$只给你$0.2s$的时间哦。

2024.5.11 upd: 放宽时空限制。

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

outputFormat: 一行一个正整数，表示答案模$104857601$的值。


title: [WC2019] 数树

background:
白兔喜欢树。

白云喜欢数数。

有 $n$ 只鼠，白兔用 $n - 1$ 根蓝色绳子把它们连成了一棵树，每根蓝色绳子连着两只鼠，白云用 $n - 1$ 根红色绳子把它们连成了一棵树，每根红色绳子连接着两只鼠。

白云要给予每只鼠一个数。这个数可以是 $[1, y]$ 中的任意一个整数。

白兔给了白云一个要求：对于两只鼠 $p, q$，若存在一条连接这两只鼠的路径同时属于这两棵树，则 $p$ 和 $q$ 必须被给予相同的整数。存在一条路径同时属于这两棵树指的是：存在一个序列 $(a_1 = p, a_2, \cdots , a_m = q)$，使得：对于所有 $i \in [1, m - 1]$，都有 $a_i$ 和 $a_{i+1}$ 既有一根红色绳子直接相连也有一根蓝色绳子直接相连。

白云想知道，她有多少种给予数的方案呢？

鼠在不停地挣扎，想要摆脱绳子的束缚。白云还没有思考出来，鼠便把红色绳子都咬断了。

白兔有些气恼，但是他还是想要知道答案。他便问白云：对于所有红色绳子的连接方案，答案的总和（即求所有红色绳子连接方案的给予数方案之和）是多少？

鼠在不停地挣扎，想要摆脱绳子的束缚。白云还没有思考出来，鼠便把蓝色绳子也咬断了。

白兔有些气恼，但是他还是想要知道答案。他便问白云：对于所有红色和蓝色绳子的连接方案，答案的总和（即求所有红色和蓝色绳子连接方案的给予数方案之和）是多少？两个方案不同当且仅当存在至少一对鼠，在两种方案中，这两只鼠之间直接连接的绳子不同（两只鼠之间连接绳子的可能性有 4 种：没有绳子直接连接，只有红色绳子直接连接，只有蓝色绳子直接连接，两种颜色的绳子均直接连接）。

白云哭了。

description:
本题包含三个问题：
- 问题 0：已知两棵 $n$ 个节点的树的形态（两棵树的节点标号均为 $1$ 至 $n$），其中第一棵树是红树，第二棵树是蓝树。要给予每个节点一个 $[1, y]$ 中的整数，使得对于任意两个节点 $p, q$，如果存在一条路径 $(a_1 = p, a_2, \cdots , a_m = q)$ 同时属于这两棵树，则 $p, q$ 必须被给予相同的数。求给予数的方案数。
  - 存在一条路径同时属于这两棵树的定义见「题目背景」。
- 问题 1：已知蓝树，对于红树的所有 $n^{n-2}$ 种选择方案，求问题 0 的答案之和。
- 问题 2：对于蓝树的所有 $n^{n-2}$ 种选择方案，求问题 1 的答案之和。

提示：$n$ 个节点的树一共有 $n^{n-2}$ 种。

在不同的测试点中，你将可能需要回答不同的问题。我们将用 $\text{op}$ 来指代你需要回答的问题编号（对应上述 0、 1、 2）。

由于答案可能很大，因此你只需要输出答案对 $998, 244, 353$ 取模的结果即可。

inputFormat:
第一行三个用空格隔开的整数 $n, y, \text{op}$。
如果 $\text{op} = 0$，则接下来 $2 \times (n - 1)$ 行，前 $(n - 1)$ 行每描述一条蓝色绳子，接下来 $(n - 1)$ 行每行描述一条红色绳子。
如果 $\text{op} = 1$，则接下来 $(n - 1)$ 行，每行描述一条蓝色绳子。
如果 $\text{op} = 2$，则接下来没有输入。
描述绳子的各行将包含两个用空格隔开的整数，分别表示被这条绳子连接的两只鼠的编号。鼠的编号是从 $1$ 开始的。

outputFormat: 输出一个整数，表示答案对 $998, 244, 353$ 取模的结果。

hint:
#### 样例说明 1
两棵树相同，所以任意两个点都必须被给予相同的数，方案数为 $2$。

#### 样例说明 2
红树共有三种可能的情况：
1. 包含绳子 $(1, 2)$（表示连接 $1, 2$ 号鼠的绳子，下同）、$(2, 3)$：此时任意两只鼠都必须被给予相同的数，问题 0 的答案为 $2$。
2. 包含绳子 $(1, 2)$、$(1, 3)$：此时 $1$ 号鼠和 $2$ 号鼠必须被给予相同的数，问题 0 的答案为 $2 \times 2 = 4$。
3. 包含绳子 $(2, 3)$、$(1, 3)$：此时 $2$ 号点和 $3$ 号点必须被给予相同的数，问题 0 的答案为 $2 \times 2 = 4$。

综上，问题 1 的答案为 $2 + 4 + 4 = 10$。

#### 样例说明 3
蓝树一共有三种可能的情况。不难发现，对于蓝树的每一种情况，求得的问题 1 的答案都是 $10$。所以答案为 $10 \times 3 = 30$。

![](https://s2.ax1x.com/2019/02/01/k3qbvQ.png)

## 洛谷按照集训队分值赋分


title: [WC2019] 远古计算机

background: 企鹅大陆是一片神奇的土地，在厚厚的冰层下埋藏着一个巨大的宝藏。探险家企鹅豆豆挖穿冰层到达了宝库，但他发现了一个令人发愁的问题。一共有五座宝库，每个宝库是由某些远古计算机控制的。由于年代久远，这些计算机里的程序已经消失不见了，只有给这些计算机重新填写代码并且顺利运行，输出了正确结果才能触发开门的机关。

description:
每一个宝库大门由一个计算机集群控制，计算机之间用数据线相连以便传输数据。但是有很多数据线已经损坏了，所以只留下了一部分连线。一开始数据线上没有数据，当一台计算机向数据线上写入时，数据线上就有了一个整数。每条数据线上最多可以同时传输一个整数，当整数被读取后便会消失，数据线就又回到没有数据的状态。

每台远古计算机有两个储存单元，分别名为 $a$ 和 $b$，每个储存单元能够储存一个 $-2147483648$ 到 $2147483647$ 之间的整数。

每个时刻，每台远古计算机可以执行一条指令，一共有以下几种指令：
- `mov reg val`：将储存单元 `reg` 的值赋值为 `val` 的值；
- `add reg val`：给储存单元 `reg` 加上 `val` 的值；
- `dec reg val`：给储存单元 `reg` 减去 `val` 的值；
- `mul reg val`：给储存单元 `reg` 乘以 `val` 的值；
- `div reg val`：给储存单元 `reg` 除以 `val` 的值，这里的除法是向零取整的除法，如 $\frac{-5}{2} = -2$；
- `and reg val`：给储存单元 `reg` 二进制与上 `val` 的值；
- `or reg val`：给储存单元 `reg` 二进制或上 `val` 的值；
- `xor reg val`：给储存单元 `reg` 二进制异或上 `val` 的值；
- `jmp val` 跳转到整个程序第 `val` 条语句，语句从程序开头开始，用从 $1$ 开始的正整数计数；
- `jz reg val`：如果 `reg` 的值为 $0$，那么跳转到第 `val` 行；
- `jnz reg val`：如果 `reg` 的值不为 $0$，那么跳转到第 `val` 行；
- `jgz reg val`：如果 `reg` 的值严格大于 $0$，那么跳转到第 `val` 行；
- `jsz reg val`：如果 `reg` 的值严格小于 $0$，那么跳转到第 `val` 行；
- `read x reg`：从远古计算机 $x$ 读取一个数到储存单元 `reg` 当中，如果数据线上缓存了一个数字，将读取这个数字并返回，否则等待下个周期再次尝试读取。$x = 0$ 时视为从标准输入数据读取一个数；
- `write val x`：将 `val` 的数值向远古计算机 $x$ 方向所在数据线写入，当且仅当数据线上没有存有数据才会成功写入，否则等待下个周期再次尝试写入。$x = 0$ 时视为向标准输出数据写出一个数。

`reg` 表示一个储存单元，只能为 $a$ 或者 $b$ 之一。

`val` 表示一个储存单元或者一个数字的值，比如填入 $a$ 表示 $a$ 中储存的值或者填入 $233$ 表示 $233$ 这个数字。

一台远古计算机读写指令中 $x$ 只有与当前远古计算机直接有数据线相连，或者 $x=0$ 才被视为合法指令。

每台远古计算机的标准输入输出独立，远古计算机之间互不影响，即每台远古计算机都有独立的一个标准输入端和一个标准输出端。

每个周期计算时，所有需要执行 `write` 指令的远古计算机先计算，然后需要执行 `read` 指令的远古计算机再计算，需要执行其余指令的远古计算机最后计算。

在读取时，如果标准输入数据没有任何可以继续读取的数据，该远古计算机将进入永远等待状态。

一台远古计算机如果执行完了最后一条指令，将会重新从第一条指令开始执行。

如果一台远古计算机没有任何指令，该计算机将永远处于等待状态。

指令计数是从 $1$ 开始的正整数。

一条数据线上最多只能暂存一个数据，两台计算机之间只有一条数据线，即可能读取自己上一轮写入的数据，如果两端的远古计算机同时读取或写入同一条数据线上的
数据，结果将不可预知。

不存在写入标准输入的方法或是从标准输出当中读取数据的方法。

比如如下样例是从 $1$ 号计算机的标准输入读入两个数，并从 $2$ 号计算机的标准输出输出两个数之和。

```plain
node 1
read 0 a
read 0 b
write a 2
write b 2
node 2
read 1 a
read 1 b
add a b
write a 0
```

而以下写法是错误的

```plain
node 1
read 0 a
read 0 b
add a b
write a 0
node 2
mov a a
```

因为正确答案中，一号远古计算机的标准输出为空，而二号远古计算机的标准输出才是两个数之和。

#### 子任务

##### 子任务 1
$1$ 号远古计算机的标准输入将会有不超过 $100$ 个非负整数，按照原顺序输出到 $1$ 号远古计算机的输出当中。

##### 子任务 2
$1$ 号远古计算机一个非负整数 $k$，按照原输入顺序将斐波那契数列第 $k$ 项输出到 $1$ 号点的标准输出当中，输入数据保证第 $k$ 项不超过 $10^9$。斐波那契数列通项公式为 $F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}(2 \le n)$。

##### 子任务 3
$1$ 号远古计算机的标准输入将会有不超过 $100$ 个非负整数，按照原顺序输出到 $n$ 号远古计算机的输出当中。

##### 子任务 4
第 $1$ 到 $50$ 号远古计算机分别输入 $1$ 个数，将这 $50$ 个数从 $51$ 到 $100$ 号远古计算机输出，输出顺序任意，每个远古计算机输出数字个数任意。

##### 子任务 5
第 $1$ 到 $10$ 号远古计算机各输入 $1$ 个数，将这些数对应从 $100$ 到 $91$ 号远古计算机输出，即 $i$ 号点输入的数需要从 $101 - i$ 号点输出。

inputFormat:
这是一道提交答案题，共有 $5$ 组输入数据，这些数据命名为 `oldcomputer1.in` ~ `oldcomputer5.in`。

这些文件描述了远古计算机之间的连线状态。

文件的第一行是三个非负整数 $x,n$ 和 $m$，表示测试点编号、远古计算机的个数与他们之间的连线条数，远古计算机是从 $1$ 到 $n$ 标号的。

接下来 $m$ 行，每行两个正整数 $x, y$，表示计算机 $x$ 和计算机 $y$ 之间通过数据线直接相连。

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

这些文件描述了每台远古计算机的代码内容。

文件由多个代码块组成，每个代码块的具体格式如下：

第一行为一个字符串 `node` 与一个 $1$ 到 $n$ 之间的整数 $a$，由一个空格隔开，表示接下来是计算机 $a$ 的指令。

接下来多行为该计算机的具体指令内容。

每台计算机的指令应当最多出现一次，否则将会出现未知错误。

所有计算机的指令总条数应当不超过 $10^6$ 行。

hint:
#### 评分方式
对于每个测试点，有三个参数 $a_1, a_2, a_3$。

如果选手提交的代码在 $a_1$ 个周期内正确输出了答案，将会得到该测试点 $100\%$ 的分。
如果选手提交的代码在 $a_2$ 个周期内正确输出了答案，将会得到该测试点 $60\%$ 的分。
如果选手提交的代码在 $a_3$ 个周期内正确输出了答案，将会得到该测试点 $30\%$ 的分。

即在每个周期结束时，会分别进行一次答案正确性判断，以最早正确的一次为准。

#### 子任务分值
|  子任务编号  | $1$  | $2$  | $3$  | $4$  | $5$  |
| :----------: | :--: | :--: | :--: | :--: | :--: |
|  集训队分值  | $10$ | $15$ | $15$ | $30$ | $30$ |
| 非集训队分值 | $20$ | $20$ | $20$ | $20$ | $20$ |

#### 提示

感谢 @tiger2005 提供 spj。关于 spj 的使用方法，请参考这两个讨论贴：
- [Tester finished.
](https://www.luogu.com.cn/discuss/show/245001)
- [Checker finished.](https://www.luogu.com.cn/discuss/show/245044)


title: [WC2019] I 君的商店

background:
### 特别提示

**在洛谷提交本题时的一些注意事项（与原题面不同之处请以此处为准）：**

1. 与原题不同的是，你不需要，也不应该在程序开头包含 `shop.h` 头文件。
2. 提交时，请在程序中加入以下函数声明语句：

```cpp
int query(int *S, int nS, int *T, int nT);
```

3. 仅支持 `C++`（含 `C++`，`C++11`，`C++14`，`C++17`）提交。

description:
V 君、I 君和 Y 君是好朋友。

I 君最近开了一家商店，商店里准备了 $N$ 种物品（编号为 $0 \sim N - 1$ 中的整数），每种物品均有无限个可供出售，每种物品的单价是 $0$ 或者 $1$。

V 君想知道每个物品的价格，他已经通过某种超自然力量知道，这 $N$ 个物品里，价格是 $1$ 的物品恰好有奇数/偶数个，且**至少存在一个物品的价格是 $1$**。

然而， V 君并不想自己去问 I 君，他选择了这样一种方法：他准备了 $+\infty$ 的钱给 Y 君。然后让 Y 君帮他跑腿：每一次，他会给 Y 君指定两个非空物品**集合** $S, T$（同一个集合内的物品必须两两不同，即每种物品在每个集合类最多包含一个），Y 君会跑到商店，分别买下这两个集合的物品，把他们送回来，并告诉 V 君哪个集合的物品价格之和更高。但是，当**两集合价格之和相等**的时候，Y 君会按照 I 君的指示来回答 V 君。

带着很多物品跑腿是一个很累的事情，因此，我们定义一次跑腿的体力消耗是 $\texttt{S} + \texttt{T}$。其中，$\texttt{S}$ 表示集合 $S$ 包含的物品个数。

你的任务是：写一个程序，帮助 V 君决定如何合理地让 Y 君跑腿，从而推算出每种物品的价值。Y 君的体力有限，你当然不能让他过于劳 累，也即，你不能让他的总体力消耗超过某个预设的阈值 $M$。

#### 实现细节
你不需要，也不应该实现主函数，你只需要实现下列函数：
- `find_price(task_id, N, K, ans)`
- 其中 `task_id` 表示子任务编号（见限制与约定）。$N$ 表示物品个数，$K$ 的意义为：
  - 若 $K = 0$，表示有偶数个物品价值为 $1$；
  - 若 $K = 1$，表示有奇数个物品价值为 $1$。
- 你需要将计算出的物品价格放在数组 $\text{ans}[]$ 中，其中 $\text{ans[i]}$ 表示编号为 $i$ 的物品的价格。

你可以通过调用如下函数来向交互库发出询问：
- `query(S, nS, T, nT)`
- 这里 $\text{nS} = \texttt{S}, \text{nT} = \texttt{T}$, 数组 $\text{S [0\ldots (nS - 1)]}$ 和数组 $\text{T[0\ldots (nT - 1)]}$ 分别描述两个集合，你需要保证：
  - $\text{nS, nT} > 0$；
  - $\forall 0 \le i < \text{nS} , 0 \le \text{S[i]} < N$；
  - $\forall 0 \le i < \text{nT} , 0 \le \text{T[i]} < N$；
$\forall$ 的意思是：「对于任意的」。例如：$\forall 0 \le i < \text{nS} , 0 \le \text{S[i]} < N$ 的意思是：「对于任意的在 $[0, \text{nS})$ 内的 $i$，$\text{S[i]}$ 在 $[0, N)$ 内」。
- 调用此函数一次的时间复杂度为 $\Theta(\text{nS + nT})$。它的返回值为 $0$ 或 $1$，返回值的意义为：
  - 若集合 $S$ 的物品价格和更大，返回 $0$；
  - 若集合 $T$ 的物品价格和更大，返回 $1$；
  - 否则，按照某种未知规则返回 $0$ 或 $1$。
- 如题面所述，我们定义这样一次调用的代价为 $\text{nS + nT}$。

评测时，交互库可能会调用 `find_price` 多次（不超过 $10$ 次），每次调用代表一次新的猜价格游戏，所有的物品的价格都会被重新设定。

inputFormat:
可执行文件将从标准输入读入以下格式的数据：

第一行一个整数 $T ( T \le 100 )$，表示数据组数。对每组数据：
- 第一行包含两个整数 $\texttt{task\_id}, N$；
- 接下来一行一个长度为 $N$ 的 $01$ 串 $s$，其中 $s_i$ 表示物品 $i$ 的价格。你需要保证至少有一个物品价格为 $1$。

读入完成之后，交互库将调用 $T$ 次 `find_price` 函数。

接下来交互库会判断你的函数每次计算是否正确，若全部正确则会输出 `Correct`，否则会输出相应的错误信息。

hint:
#### 评分标准

题目首先会受到和非交互式程序题相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

在上述条件基础上，在一个测试点中，你得到满分，当且仅当**每一次** `find_price` 的调用中：
- 你的每一个 `query` 的调用符合规则，且调用代价之和不超过 $M$；
- 你的函数正确计算了 $\text{ans[]}$ 数组。

在一个测试点中，如果你没有获得满分，那么你获得 $0$ 分。

#### 子任务
我们令代价之和的上界为 $M$，记答案数组为 $\text{ans[]}$：
- 子任务 1：$N \le 5, M = 100$；
- 子任务 2：$N \le 10^3, M = 10^6$；
- 子任务 3：$N \le 10^5, M = 100$，保证 $\forall i < j < k$，若 $\text{ans[i]} = \text{ans[k]}$ 则必有 $\text{ans[j]} = \text{ans[i]}$。
- 子任务 4：$N \le 10^4, M = 2 \times 10^5$；
- 子任务 5：$N \le 5 \times 10^4, M = 350100$；
- 子任务 6：$N \le 10^5, M = 500100$。

#### 提示
**I 君可能并不愿意让 V 君知道每件物品的价格，在物品价格相等时，他会按照他自己的某种方式来回答问题。**

#### 子任务分值
在本场比赛中，测试点（或子任务）的分值分布与你是否为集训队选手有关。本题的分值设置如下：

| 子任务编号   | 1    | 2    | 3    | 4    | 5    | 6    |
| :------------: | :----: | :----: | :----: | :----: | :----: | :----: |
| 集训队分值   | $20$ | $11$ | $9$  | $12$ | $17$ | $31$ |
| 非集训队分值 | $31$ | $21$ | $13$ | $9$  | $11$ | $15$ |

**洛谷评测时采用集训队分值计算分数**。


title: [NOI2001] 方程的解数

description:
已知一个 $n$ 元高次方程：
$$\sum\limits_{i=1}^n k_ix_i^{p_i} = 0$$
其中：$x_1, x_2, \dots ,x_n$ 是未知数，$k_1,k_2, \dots ,k_n$ 是系数，$p_1,p_2,…p_n$ 是指数。且方程中的所有数均为整数。

假设未知数 $x_i \in [1,m] \space ( i \in [1,n])$，求这个方程的整数解的个数。

inputFormat:
第一行一个正整数 $n$，表示未知数个数。
第二行一个正整数 $m$。
接下来 $n$ 行，每行两个整数 $k_i,p_i$。

outputFormat: 输出一行一个整数，表示方程解的个数。


title: [ZJOI2017] 汉诺塔

background: 虽然九条可怜经常出题，但是她发现要一个人出一场比赛是在是太难了，于是她丢下了手头的出题工作开始玩小游戏。

description:
有一个游戏是汉诺塔的改版。在这个游戏中，盘子的大小可以相同，但是保证了相同大小的盘子恰好有 K 个。

初始状态下，所有盘子自底向上从大到小地放置在第一根柱子上，对于相同大小的盘子，我们自底向上给它们从 1 到 K 标号。目标是把所有盘子都移动到第三根柱子上。

因为相同大小的盘子的上下顺序没有要求，不难发现合法的终止状态有很多，因此游戏里指定了一种终止状态。

游戏的任务是最小化移动的步数。

可怜想了想觉得这个问题好像挺难的，于是她就把这个出到比赛里来给你做啦。

下面给出汉诺塔的具体规则：

• 有三根柱子和若干块圆盘，初始状态下所有圆盘都在第一根柱子上。

• 每一时刻你可以把某一根柱子顶端的圆盘移动到另一根柱子的顶端，目标是把
所有盘子都

移动到第三根柱子上。

• 移动的过程中必须要保证较大的圆盘不会压在较小的圆盘上。（相同大小的圆盘没有顺序限制）。

inputFormat:
第一行输入一个整数表示数据组数。

每组数据第一行是两个整数 n 和 K。

接下来 n 行按照盘子从大到小的顺序给出终止状态下同一大小的盘子的相对顺序（从左到右依次表示自底向上），

例如 K = 2 时，2 1 表示原来在上方的盘子到了下面，原来在下方的盘子到了上面。

outputFormat: 对于每组数据输出一个整数表示最少步数。


title: [ZJOI2017] 线段树

description:
线段树是九条可怜很喜欢的一个数据结构，它拥有着简单的结构、优秀的复杂度与强大的功能，因此可怜曾经花了很长时间研究线段树的一些性质。

最近可怜又开始研究起线段树来了，有所不同的是，她把目光放在了更广义的线段树上：在正常的线段树中，对于区间 $[l, r]$，我们会取 $m = \lfloor \frac{l+r}{2} \rfloor$，然后将这个区间分成 $[l, m]$ 和 $[m + 1, r]$ 两个子区间。在广义的线段树中，$m$ 不要求恰好等于区间的中点，但是 $m$ 还是必须满足 $l \le m < r$ 的。不难发现在广义的线段树中，树的深度可以达到 $O(n)$ 级别。

例如下面这棵树，就是一棵广义的线段树：

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

为了方便，我们按照先序遍历给线段树上所有的节点标号，例如在上图中，$[2, 3]$ 的标号是 $5$，$[4, 4]$ 的标号是 $9$，不难发现在 $[1, n]$ 上建立的广义线段树，它共有着 $2n − 1$ 个节点。

考虑把线段树上的定位区间操作 $($就是打懒标记的时候干的事情$)$ 移植到广义线段树上，可以发现在广义的线段树上还是可以用传统的线段树上的方法定位区间的，例如在上图中，蓝色节点和蓝色边就是在定位区间 $[2, 4]$ 时经过的点和边，最终定位到的点是 $[2, 3]$ 和 $[4, 4]$。

如果你对线段树不熟悉，这儿给出定位区间操作形式化的定义：给出区间 $[l, r]$，找出尽可能少的**区间互不相交**的线段树节点，使得它们区间的并集**恰好**是 $[l, r]$。

定义 $S_{[l,r]}$ 为定位区间 $[l, r]$ 得到的点集，例如在上图中，$S_{[2,4]} = \{5, 9\}$。定义线段树上两个点 $u, v$ 的距离 $d(u, v)$ 为线段树上 $u$ 到 $v$ 最短路径上的边数，例如在上图中 $d(5, 9) = 3$。

现在可怜给了你一棵 $[1, n]$ 上的广义的线段树并给了 $m$ 组询问，每组询问给出三个数 $u, l, r\ (l \le r)$，可怜想要知道 $\sum_{v \in S_{[l, r]}} d(u, v)$。

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

接下来一行包含 $n - 1$ 个空格隔开的整数：按照标号递增的顺序，给出广义线段树上所有**非叶子**节点的划分位置 $m$。不难发现通过这些信息就能唯一确定一棵 $[1, n]$ 上的广义线段树。

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

之后 $m$ 行每行输入三个整数 $u, l, r\ (1 \le u \le 2n − 1, 1 \le l \le r \le n)$，表示一组询问。

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


title: [ZJOI2017] 字符串

background: 猪小侠最近学习了字符串相关理论，现在他遇到了这样一个题：

description:
维护一个动态字符串 $s_{1..n}$，字符串的字符集是所有 $|x| \leq 10 ^ 9$ 的整数。要求支持两个操作：

1. 输入 $l, r, d$，对于所有 $l \leq i \leq r$，将 $s_i$ 修改为 $s_i + d$，注意 $d$ 可能是负数。

2. 输入 $l, r$，输出子串 $s_{l..r}$ 的字典序最小的后缀的起点位置。即，如果最小后缀是 $s_{p..r}$（$l\leq p\leq r$），请输出 $p$。

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

接下来一行包含 $n$ 个正整数，表示初始时的字符串。

接下来 $q$ 行，每行为 $1\ l\ r\ d$ 或 $2\ l\ r$，分别表示两种操作。

outputFormat: 对于所有的查询操作按顺序输出答案。


title: SubString

description:
给定一个字符串 `init`，要求支持两个操作：

- 在当前字符串的后面插入一个字符串。

- 询问字符串 $s$ 在当前字符串中出现了几次。(作为连续子串)

强制在线。

inputFormat:
第一行一个整数 $Q$ 表示操作个数。

第二行一个字符串表示初始字符串 `init`。

接下来 $Q$ 行，每行 $2$ 个字符串 `Type`,`Str`。

- `Type` 是 `ADD`，表示在后面插入字符串。

- `Type` 是 `QUERY`，表示询问某字符串在当前字符串中出现了几次。

为了体现在线操作，你需要维护一个变量 `mask`，初始值为 $0$。

```cpp
String decodeWithMask(String s, int mask) {
	char[] chars = s.toCharArray();
	for (int j = 0; j < chars.length; j++) {
		mask = (mask * 131 + j) % chars.length;

		char t = chars[j];
		chars[j] = chars[mask];
		chars[mask] = t;
	}

	return new String(chars);
}
```

读入串 `Str` 之后，使用这个过程将之解码成真正询问的串 `TrueStr`。

询问的时候，对 `TrueStr` 询问后输出一行答案 `Result`。

然后 $mask=mask \bigoplus Result$。

插入的时候，将`TrueStr`插到当前字符串后面即可。

**注意：`ADD` 和 `QUERY` 操作的字符串都需要解压。**

outputFormat: 对于每一个 `QUERY` 操作，输出询问的字符串在当前字符串中出现了几次。

hint:
$|\mathrm{init}| \leq 6 \times 10^5$，$Q \leq 6\times 10^5$，询问总长度 $\leq 3 \times 10^6$。

保证字符串中只会出现 `A` 和 `B`。

为防止评测过慢，对于测试点 $2,3,5,6,8,11$ 时限为 3s，其余为 1s。

原题：BZOJ 2555


title: [SHOI2014] 超能粒子炮

background: shoi2014 day1t3

description:
邪恶的巨型宇宙怪物 CCM (Crazy Code Monster) 即将对美丽的地球发动攻击！

在这千钧一发的时刻,地球联合军决定使用地球最先进的能量武器——由发明家 SHTSC 设计的超能粒子炮彻底摧毁 CCM。

超能粒子炮由垂直方向从上到下共 $n$ 个超能粒子发射管构成,编号 $1 \sim n$。所有的发射管都会在开火的一瞬间同时发射出强大的超能粒子流。
为了彻底摧毁再生能力极强的邪恶宇宙怪物 CCM，地球联合军将 CCM 从上到下分为 $m$ 个区域，编号 $1 \sim m$，分别进行打击。其中超能粒子炮的第 $i$ 号发射管将会对准 $f(i)$ 号区域发射。$f(i)$ 的公式如下：
$$f(i) = (ai + b) \bmod m + 1$$
其中 $a, b$ 都是给定的常数。

然而，出于某种不可告人的目的，N 财团不希望 CCM 被超能粒子炮彻底消灭。于是 N 财团以远程精神控制了超能粒子炮的操作员——你来阻止地球军消灭 CCM。

你发现，超能粒子炮的开火模式会使得不同的粒子流的运动轨迹发生交叉，而在所有这些交叉点处部署一种名为折跃棱镜的能量反射装置就能使得超能粒子炮因过载而自爆。这样，你就可以阻止地球联合军使用超能粒子炮摧毁 CCM 而成为下一代 N 财团金牌的获得者。

为了实现这个计划,你需要知道有多少对粒子流 $i, j$，满足 $i<j$ 且 $f(i) > f(j)$。

inputFormat: 第一行四个整数 $n, m, a, b$。分别为超能粒子炮的发射管数目、CCM 被分成的区域数、以及题目描述中的 $f$ 公式中的常数。

outputFormat: 输出一行一个整数，为运动轨迹交叉的粒子流的对数。

hint:
对于 10%的数据，$n\leq 5 \times 10^3$。

对于 20%的数据，$n\leq m\leq 10^6$。

对于额外 20%的数据，$b=0$。

对于 80%的数据，$1\leq a\leq 1000$。

对于 $100\%$ 的数据，$n \leq m \leq 10^9$，存在 $a'$ 满足 $a\times a' =1 \pmod m$，且 $\min \{a,a'\} \leq 1000, a,b<m$，$m$ 是质数。


title: [SHOI2014] 神奇化合物

background: SHOI2014 day2t1

description:
科学家最近发现了一种高分子有机化合物 SHTSC。这种物质的分子由单个或多个原子组成，原子之间通过化学键相互连接。SHTSC 十分不稳定，其原子之间的化学键经常会伴随着炫酷的声音特效和光影效果发生断裂或者重新连接。

然而，令科学家们大为惊异的是，SHTSC 在变化过程中始终保持着一种特殊的性质：即不存在这样的原子序列 $a_1,a_2,\ldots,a_n \ (n>3)$ 满足 $a_1$ 与 $a_2$、$a_2$ 与 $a_3$、......、$a_{n-1}$ 与 $a_n$ 以及 $a_n$ 与 $a_1$ 都通过化学键相连,但它们之间却没有其他化学键相连的情况。

现在科学家将 SHTSC 的原子由 $1$ 到 $n$ 标号，并告诉你 SHTSC 的初始形态以及原子之间的化学键变化情况，他们想知道在实验过程中的某些时刻 SHTSC 分裂成了多少个分子？

inputFormat:
第一行两个整数 $n, m$。表示 SHTSC 的总原子个数以及初始的化学键数。
从第二行开始的 $m$ 行,每行两个整数 $a, b \ (1 \leq a,b \leq n)$。表示编号为 $a, b$ 的两个原子在初始状态中有化学键相连。数据保证每对 $a, b$ 只出现一次。
第 $m+2$ 行有一个整数 $q$。表示实验的总操作数。
之后 $q$ 行中的每一行为以下三种操作当中的一种：
1. ``A i j`` 表示 $i$ 号原子与 $j$ 号原子之间形成了一条新的化学键;
2. ``D i j`` 表示 $i$ 号原子与 $j$ 号原子之间原有的化学键断裂了;
3. ``Q`` 询问当前 SHTSC 分裂成了多少个不同的分子。
数据保证所有的实验操作都是合法的。

outputFormat: 对于每个 $Q$ 操作,输出一行一个整数,为相应时刻的分子个数。


title: [SHOI2014] 神秘金字塔

background: SHOI2014 day2t3

description:
对神经组织的进化生物学研究将历史追溯到了人类社会形成之初、一个叫做 CCM 的神秘部落。

考古学证据表明，CCM 一度具有高度繁华的文明。然而 CCM 的历史却似乎在一夜之间神秘地消失了。考古学家近日在大西洋底发掘出了一处 CCM 文明遗迹,有希望能够揭开 CCM 古文明失落之谜。

CCM 遗迹的中央是一座巨大的石质建筑,被考古学家称之为金字塔。金字塔有这样四条性质:
1. CCM 金字塔由完全相同的 $1 \times 1 \times 1$ 单位的立方体石块构成；
2. CCM 金字塔由若干层组成，每一层的石块从正上方看都在平面上形成一个联通块。高层的石块都有低层的石块在下方作为支撑，不会有石块悬空；
3. CCM 金字塔的每一层严格都满足左右对称和上下对称，并且所有层的对称轴是重合的，从左右/上下对称轴向两端长度/宽度非严格递减；
4. CCM 金字塔的每一层的最大长度和最大宽度都相等，并且都是偶数（因为 CCM 人认为偶数代表了好运而奇数则会带来不幸）。

然而，不幸的是，遗迹中的金字塔由于年代过于久远，已经残缺不全，难以辨认全貌。为了尽可能地还原 CCM 金字塔的实际情况，考古学家们通过其他证据估计出了 CCM 金字塔所使用的石块个数、金字塔的高度以及每一层的宽度，他们想请你帮忙计算符合上述性质的可能的金字塔个数。

inputFormat:
第一行两个整数 $n,h$，表示 CCM 金字塔的总石块数和 CCM 金字塔的高度。
从第二行开始的 $h$ 行，每行一个整数 $l$，表示从最底层开始的每一层的最大长度(宽度)，保证非严格递减。

outputFormat: 输出一行一个整数，表示可能的金字塔个数。由于方案数可能数量很大，输出答案为模 $10^9+7$ 之后的结果。

hint:
对于 10%的数据，$h=1$。

对于 30%的数据，$n\leq 200,l\leq 10, h\leq 5$。

对于 70%的数据，$n\leq 800,l\leq 20, h\leq8$。

对于 100%的数据，$n\leq 1000, 2\leq l\leq 20, 1\leq h\leq 10$。

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


title: [ICPC2019 WF] Karel the Robot

background:
### Warning: If you submit a malicious program, you will be banned.
### 警告：恶意提交本题将被封号。

description:
Did you know that the word "robot" is almost 100 years old? It was first introduced in 1920, in the science-fiction theatrical play $R.U.R.$ , written by Karel Capek. As a tribute to this Czech writer, an educational programming language was named Karel many years later at Stanford University. Your task is to implement an interpreter of a simplified version of this programming language.

The Karel programming language controls a robot named Karel, who lives in a grid of unit squares. Some of the squares are free, while others contain a barrier. Karel always occupies one of the free squares and faces one of the four cardinal directions. The two basic commands are "move forward" and "turn left." The language also provides simple conditional and looping statements. The main educational potential of the language lies in the possibility of defining new procedures for more complex tasks.

Our simplified version of the language can be described by the following grammar:

```plain
<program> := "" | <command> <program>
<command> := "m" | "l" | <proc-call> |
             "i" <condition> "(" <program> ")(" <program> ")" |
             "u" <condition> "(" <program> ")"
<condition> := "b" | "n" | "s" | "e" | "w"
<proc-call> := <uppercase-letter>
<proc-def> := <uppercase-letter> "=" <program>
```
There are five types of commands:

- $\texttt m$ ("move forward") advances Karel's position by one grid square in its current heading, unless there is a barrier, in which case the command has no effect.
- $\texttt l$ ("turn left") makes Karel turn left $90$ degrees.
- $\texttt X$ where $\texttt X$ is any uppercase letter, invokes the procedure named $\texttt X$.
- $\texttt i$ ("if") followed by a single-letter condition, and two programs in parentheses. If the condition is satisfied, the first program is executed. Otherwise, the second program is executed.
- $\texttt u$ ("until") followed by a single-letter condition, and a program in parentheses. If the condition is satisfied, nothing is done. Otherwise, the program is executed and then the command is repeated.

A condition can be either '$b$', which is satisfied if and only if there is a barrier in the next square in Karel's current heading, or one of the four directional letters `n`, `s`, `e`, or `w`, which is satisfied if and only if Karel's current heading is north, south, east, or west, respectively.

For instance, a simple program `ub(m)` can be understood to mean: “keep moving forward until there is a barrier," while `un(l)` means "turn to the north." A procedure definition `R=lll` defines a new procedure `R` which effectively means "turn right."

inputFormat:
The first line of input contains four integers $r, c, d$ and $e$, where $r$ and $c$ $(1 \leq r, c \leq 40)$ are the dimensions of the grid in which Karel lives, $d$ $(0 \leq d \leq 26)$ is the number of procedure definitions, and $e$ $(1 \leq e \leq 10)$ is the number of programs to be executed.

Then follow $r$ lines describing the grid (running north to south), each containing c characters (running west to east), each character being either `.` (denoting a free square) or `#` (denoting a barrier). All squares outside this given area are considered barriers, which means Karel may never leave the area.

Each of the next $d$ lines contains a procedure definition, associating a procedure name (one uppercase letter) with a program forming the procedure body. No procedure name is defined more than once. Procedure bodies may contain invocations of procedures that have not yet been defined.

The last $2e$ lines describe the programs to be executed. Each such description consists of a pair of lines. The first line of each pair contains two integers $i$ and $j$ and a character $h$, where $i$ $(1 \leq i\leq r)$ is the row and $j$ $(1 \leq j \leq c)$ is the column of Karel's initial position, and $h \in \{ \texttt n, \texttt s, \texttt e, \texttt w\}$ represents Karel's initial heading. It is guaranteed that the initial position is a free square. The second line of each pair contains a program to be executed from that initial position.

All procedure bodies and all programs to be executed are at least $1$ and at most $100$ characters long, syntactically correct, and only contain invocations of procedures that are defined. The lines with procedure definitions and programs to be executed contain no whitespace characters.

outputFormat: For each program execution, output the final position of Karel after the complete program is executed from the respective initial position. Follow the format used to describe initial positions, that is, two numbers and a directional character. If a particular execution never terminates, output `inf` instead.

translation:
## 题目描述

你知道“机器人”这个词已经有100年的历史了吗？它最早出现在1920年的科幻戏剧《R.U.R.R.U.R.》中，卡雷尔·卡佩克写的。为了向这位捷克作家致敬，一种教育编程语言在多年后在斯坦福大学被命名为Karel。您的任务是实现此编程语言简化版本的解释器。

Karel编程语言控制着一个名叫Karel的机器人，他生活在一个单位方格的网格中。一些方块是自由的，而另一些方块包含障碍物。卡雷尔总是占据一个自由正方形，面向四个基本方向之一。两个基本命令是“向前移动”和“向左转”。该语言还提供简单的条件语句和循环语句。该语言的主要教育潜力在于为更复杂的任务定义新程序的可能性。

我们简化的语言版本可以用以下语法描述：

```
<program> := "" | <command> <program>
<command> := "m" | "l" | <proc-call> |
             "i" <condition> "(" <program> ")(" <program> ")" |
             "u" <condition> "(" <program> ")"
<condition> := "b" | "n" | "s" | "e" | "w"
<proc-call> := <uppercase-letter>
<proc-def> := <uppercase-letter> "=" <program>
```
有五种类型的命令：

m（“向前移动”）在当前航向中将Karel的位置向前移动一个方格，除非有障碍物，在这种情况下，命令无效。

l（“左转”）使卡雷尔左转9090度。

x，其中x是任何大写字母，调用名为x的过程。

i（“if”）后跟一个单字母条件，括号中有两个程序。如果满足条件，则执行第一个程序。否则，执行第二个程序。

u（“直到”），后跟一个单字母条件，括号中是一个程序。如果条件满足，则什么也不做。否则，将执行该程序，然后重复该命令。

条件可以是“b”，当且仅当Karel当前航向的下一个方格中存在障碍物时满足，或者四个方向字母n、s、e或w中的一个，当且仅当Karel当前航向分别为北、南、东或西时满足。

例如，一个简单的程序ub（m）可以理解为“继续前进，直到有障碍物为止”，而un（l）表示“转向北方”。程序定义R=lll定义了一个新的程序R，它实际上意味着“右转”

输入的第一行包含四个整数r、c、dr、c、d和e，其中r和c（1≤r、 c≤40）是Karel居住的网格的尺寸，d（0≤D≤26）是程序定义的数量，e（1）≤E≤10） 是要执行的程序数。

然后沿着描述网格的r行（从北到南），每个包含c字符（从西到东），每个字符都是。（表示自由正方形）或#（表示障碍物）。该区域以外的所有广场都被视为障碍物，这意味着卡雷尔可能永远不会离开该区域。

接下来的d行中的每一行都包含一个过程定义，将过程名称（一个大写字母）与构成过程主体的程序相关联。没有多次定义过程名称。过程主体可能包含尚未定义的过程调用。

最后两行描述了要执行的程序。每个这样的描述由一对行组成。每对的第一行包含两个整数ii和jj以及一个字符hh，其中i（1≤我≤r） 是行和j（1）≤J≤c） 是Karel初始位置的列，h∈{n，s，e，w}代表Karel的初始标题。保证初始位置为自由正方形。每对的第二行包含从该初始位置执行的程序。

所有要执行的过程体和所有程序的长度至少为11个字符，最多为100100个字符，语法正确，并且仅包含已定义过程的调用。包含要执行的过程定义和程序的行不包含空格字符。

输出格式

对于每个程序执行，在从各自的初始位置执行完整程序后，输出Karel的最终位置。遵循用于描述初始位置的格式，即两个数字和一个方向字符。如果特定执行从未终止，则改为输出inf。

hint: Source: ICPC World Finals 2019.


title: [CTSC2018] 组合数问题

description:
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这题不仅和组合数没什么关系，甚至和小葱也没有关系。

这次我们的主人公是小何同学。众所周知，小何同学非常有钱，他买了 $K$ 台 TPU 来解决 A+B 问题。现在小何同学有 $N$ 个 A+B 问题，第 $i$ 个 A+B 问题在第 $j$ 台 TPU 上计算需要 $t_{i j}$ 的时间。与传统的 A+B 问题不一样的是，这 $N$ 个 A+B 问题之间有 $M$ 个依赖关系，如果问题 $i$ 依赖于问题 $j$，那么问题 $i$ 必须等待问题 $j$ 计算完毕，并将计算的结果传输到问题 $i$ 所在的 TPU 之后，问题 $i$ 才能开始进行计算。如果问题 $i$ 在第 $p$ 台 TPU 上进行计算，问题 $j$ 在第 $q$ 台机器上进行计算，那么问题 $i$ 的结果传输到问题 $j$ 所需要的时间为 $r_{p q}$。数据之间的传输是并行的，即同时有多台机器向一台机器传输数据，或一台机器向多台机器发送数据，都并不会影响到数据传输的速度；但我们规定数据的传输是不能转发的，即如果要从第 $i$ 台机器向第 $j$ 台机器传输某个数据，不能先传输到第 $k$ 台机器再传输到第 $j$ 台机器。

虽然小何同学特别有钱，但是小何同学没有多少的时间毕竟他还要去陪妹子，所以现在小何同学希望你来帮他决定每个 A+B 问题分配到哪台机器上计算，使得所有 TPU 的计算时间总和最小或者所有任务完成的时间最小。所谓 TPU 的计算时间，其定义为 TPU 用来计算问题的时间加上所有数据传输的时间之和。所有任务完成时间定义为从第一个计算开始到最后一个计算结束的时间。

虽然小何同学特别有钱，并且小何同学知道你也没有多少时间来做这个题，所以小何同学为了简化问题，对上述任务作出了如下规定：

1. 问题的依赖关系之间没有环。

2. 任何一个时刻，一台 TPU 只能计算一个问题，且一旦开始这个问题的计算，就不会被打断，会一直计算到这个问题计算完成。

3. 如果一台 TPU 此时没有计算任何一个问题，并且存在一个或多个问题已经准备好数据可以计算，那么 TPU 会选择其中编号最小的问题开始计算。

4. 一台 TPU 同时进行多个数据传输，且彼此之间互相不会影响速度，计算问题的同时也可以进行数据传输，且彼此之间的速度都不会受到影响。

5. 数据不能进行转发，只能直接在相应的机器之间传输。

6. 保证 $r_{ii} = 0$。

7. 如果一个任务不依赖于其他任务，则该任务所需要的数据已经直接在对应机器上准备好了不需要传输。

在上面的这些条件下，小何同学认为这个问题已经足够简单了，于是他愉快地去找妹子玩耍，并把这个问题交给了你。

inputFormat:
这是一道提交答案题，共有 $10$ 组输入数据，这些数据命名为 `placement1.in` ~ `placement10.in`。

第一行四个整数 $N, M, K, op$。如果 $op = 1$，则代表你要最小化 TPU 的计算时间总和，否则你需要最小化最后一个完成的任务的完成时间。

接下来 $M$ 行每行两个数 $i, j$，代表问题 $j$ 依赖于问题 $i$。

接下来 $N$ 行每行 $K$ 个数，代表 $t_{i j}$。

接下来 $K$ 行每行 $K$ 个数，代表 $r_{i j}$。

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

一行 $N$ 个整数，代表每个任务被分配给哪台机器。

hint:
本题的每个测试点有十个评分标准，如果你的答案小于等于其中 $k$ 个评分标准，那么该测试点你会得到 $k$ 分。

这些标准保存在选手目录的 `placement*.ans` 中。

### 提示
为了方便你测试自己的答案，小何同学把妹子甩了然后给你写了一个模拟器。你可以在你的目录下找到一个可执行文件 `simulator`。它的用法为在终端中执行 `./simulator <input_file> <output_file>`。其中 `<input_file>` 为输入文件，`<output_file>` 为你的答案。它会告诉你你的分配方案的总计算时间和所有任务的完成时间。

注意：由于陪妹子玩耍降低了小何同学的编程技巧，小何同学不能保证这个模拟器能对不是他提供的输入文件给出正确的结果。


title: 【模板】静态仙人掌

background:
这是一道静态仙人掌(Block Forest Data Structure)的模板题。
如果您不知道什么是仙人掌，那么此处给出无向仙人掌图的定义：
>任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。

description:
给你一个有 $n$ 个点和 $m$ 条边的仙人掌图，和 $q$ 组询问
每次询问两个点 $u,v$，求两点之间的最短路。

保证输入数据没有重边。

inputFormat:
第一行三个正整数 $n,m,q$，意义如题目描述。
接下来 $m$ 行，每行三个正整数 $u,v,w$，表示 $u,v$ 之间有一条权值为 $w$ 的无向边。
然后 $q$ 行，每行两个正整数 $u,v$，询问 $u$ 到 $v$ 的最短路。

outputFormat: $q$ 行，每行一个正整数，对应一次询问的结果。

hint:
**样例1解释：**
样例1中的仙人掌是这个样子的：
![](https://cdn.luogu.com.cn/upload/pic/52854.png)
询问有两个，分别是询问 $1\rightarrow 9$ 和 $5\rightarrow 7$ 的最短路
显然答案分别为 $5$ 和 $6$。

**数据范围：**
$1\le n,q \le 10000$
$1\le m \le 20000$
$1\le w \le 10^5$

保证输入数据没有重边。

请注意时限为 $300\text{ms}$


title: [SCOI2015] 小凸解密码

description:
小凸得到了一个密码盘，密码盘被等分成 $n$ 个扇形，每个扇形上有一个数字 $(0 \sim 9)$，和一个符号 $($ `+` 或 `*` $)$。密码盘解密的方法如下：

首先，选择一个位置开始，顺时针地将数字和符号分别记在数组 $A$ 和数组 $C$ 中。解密的方法如下：

- $B_0 = A_0$
- 当 $x > 0$ 时：
  - 若 $C_x$ 为 `+`，$B_x = (A_x + A_{x - 1}) \% 10$
  - 若 $C_x$ 为 `*`，$B_x = (A_x \times A_{x - 1}) \% 10$

操作完成后，可以得到一个长度为 $n$ 的数组 $B$，然后以 $B_0$ 为起点将 $B$ 数组顺时针写成一个环，解密就完成了，称得到的环为答案环。

现在小凸得到了一份指令表，指令表上有 2 种操作。一种指令是修改操作，即改变原来密码盘上一个位置的数字和符号。另一种指令是询问操作，具体如下：

- 首先从指令给出的位置开始完成解密，得到答案环。
- 答案环上会有一些 $0$ 连在一起，将这些连在一起的 $0$ 称为零区间，找出其中距离 $B_0$ 最远的那个零区间，输出这个距离（零区间和 $B_0$ 的距离定义为：零区间内所有 $0$ 到 $B_0$ 距离中的最小值）。

inputFormat:
第一行包含两个整数 $n, m$，代表密码盘大小和指令个数。

接下来 $n$ 行，每行包含一个整数和一个字符，按顺时针顺序给出了密码盘上的数组和符号。

接下来 $m$ 行，依次给出指令。每行第一个整数代表指令类型：

- 若第一个整数为 `1`，代表本行对应指令为修改操作，之后依次有两个整数 $pos, num$ 和一个字符 $\rm opt$，分别代表修改的位置，以及修改后该位置的数字和字符。
- 若第一个整数为 `2`，代表本行对应指令位询问操作，之后有一个整数 $pos$，代表本次操作中解密的开始位置。

密码盘上的位置标号为 $0$ 到 $n - 1$。

数据保证合法，即数据中 $0 \leq pos < n, 0 \leq num \leq 9$，$\rm opt$ 为 `+` 或 `*`。

outputFormat: 对于每个询问操作 $1$ 行，输出答案，若答案环上没有 $0$，输出 `−1`。


title: [AHOI2013] 连通图

description:
给定一个无向连通图和若干个小集合，每个小集合包含一些边，对于每个集合，你需要确定将集合中的边删掉后改图是否保持联通。集合间的询问相互独立

定义一个图为联通的当且仅当对于任意的两个顶点，都存在一条路径连接它们

inputFormat:
第一行为两个整数 $n,m$，代表无向图的点数和边数

下面 $m$ 行，包含两个整数 $u,v$，代表该边连接点 $u,v$。第 $i + 1$ 行的边的编号为 $i$。保证不存在重边和自环

下面一行包含一个整数 $k$，表示集合个数

下面 $k$ 行每行描述一个集合，每行的第一个数为集合中边的个数 $c$，后面 $c$ 个数代表集合内的边

outputFormat: 对于每个集合，输出一行代表去掉该集合中的边后图是否联通，如果联通输出 ``Connected``，否则输出 ``Disconnected``


title: [AHOI2013] 找硬币

description: 小蛇是金融部部长。最近她决定制造一系列新的货币。假设她要制造的货币的面值为 $x_1~,~x_2~,~x_3...$ 那么 $x_1$ 必须为 $1$，$x_b$ 必须为 $x_a$ 的正整数倍（$b~>~a$）。例如 $1~,~5~,~125~,~250$ 就是一组合法的硬币序列，而 $1~,~5~,~100~,~125$ 就不是。不知从哪一天开始，可爱的蛇爱上了一种萌物——兔纸！从此，小蛇便走上了遇上兔纸娃娃就买的不归路。某天，小蛇看到了 $N$ 只可爱的兔纸，假设这 $N$ 只兔纸的价钱分别是 $a_1~,~a_2~...~a_N$。现在小蛇想知道，在哪一组合法的硬币序列下，买这N只兔纸所需要的硬币数最少。买兔纸时不能找零。

inputFormat:
第一行，一个整数 $N$，表示兔纸的个数
第二行，$N$ 个用空格隔开的整数，分别为 $N$ 只兔纸的价钱

outputFormat: 一行，一个整数，表示最少付的钱币数。


title: [AHOI2013] 立方体

description: 在一个三维空间中有 $N$个立方体，第 $i$ 个立方体占据 $x_{i_1},y_{i_1},z_{i_1}$ —— $x_{i_2}, y_{i_2}, z_{i_2}$的位置。这 $N$ 个立方体可能有相交，也可能重叠。他们构成了一个大的几何图形。现在求这个几何图形的外表面积

inputFormat:
第一行，一个整数 $N$，表示立方体的个数。

第二行至第 $N+1$ 行，每行 $6$ 个用空格隔开的整数，分别表示$x_1$,$y_1$,$z_1$,$x_2$,$y_2$,$z_2$.

outputFormat: 一行，一个整数，表示外表面积的大小。


title: [AHOI2013] 好方的蛇

description:
有一天，可爱的蛇心花怒放，把自己变成了一个正方形！但是她改变的时候
被induce了导致改变出了些问题....

按照预设，她应该变成一个 $N*N$ 的全黑正方形，但是这个正方形出现了一些白的格子...现在她的身体不幸出了些小反应，定义一个subsnake是一个至少有两格的全黑矩形。

![qwq](http://images.cnblogs.com/cnblogs_com/yifusuyi/1229574/o_1(1).jpg)

现在蛇想让你帮忙求一下一共有多少对不相交的subsnake，答案模10007。

inputFormat: 第一行一个整数 $N$,   接下来 $N$ 行，每行一个长度为 $N$ 的字符串，如果是 $B$，那么是黑的，如果是 $W$ 那么是白的。

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


title: 回忆京都

background:
第十五届东方人气投票 音乐部门 106名

第四次国内不知道东方的人对东方原曲的投票调查 51名

回忆京都副歌我tm吹爆，东方文花帖我tm吹爆！

description:
射命丸文在取材中发现了一个好玩的东西，叫做组合数。

组合数的定义如下：从$n$个不同元素中，任取$m(m \leq n)$个元素并成一组，叫做从$n$个不同元素中取出$m$个元素的一个组合。所有组合的数量，就是组合数。

组合数的计算公式如下：$C^m_n=\dfrac{n!}{m! \times (n-m)!}$，其中保证$m \leq n$，表示在$n$个元素中选出$m$个元素的组合数。

为了方便理解，举一个例子：在th16.5秘封噩梦日记的第三周目中，每一天的战斗都有$4$个角色两两组合出场，那么很显然就有$C^2_4=6$种组合方式。

关于这方面的更详细解释，请看样例说明。

由于她对新事物都存在着好奇，因此她想要知道$C^m_n$是多少。这对她来说是个很简单的事情，因此她看了一眼就秒了，因此她决定求出下列式子：

$\sum_{i=1}^n \sum_{j=1}^m C^i_j$，其中当$i>j$的时候，钦定$C^i_j$为$0$

她也很快就算出来了，不过对自己的答案不是很充满信心，因此你决定帮助她。然而没事找事的她一下子算了$q$次对于不同的$n,m$的结果，因此这只能劳烦你了。由于你不打算真正地帮助她，你无需把答案对$998244353$取模，也无需对$64123$取模，只要告诉她对$19260817$取模之后的答案即可。

inputFormat:
第一行输入一个$q$，表示有$q$次询问。

第二行开始，一共$q$行，每行两个数字$n,m$，意思如题所示。

outputFormat: 一共$q$行，对于每一个询问，都输出一个答案。

hint:
![](https://i.loli.net/2018/12/15/5c148dbe83f11.jpg)

关于组合数的样例说明。

例如有蕾米莉亚 芙兰朵露 圣白莲 丰聪耳神子在这一天组合出场，会有六种情况：

1、蕾米莉亚x芙兰朵露 $\text{\color{white}背德组}$

2、丰聪耳神子x圣白莲 $\text{\color{white}宗教组}$

3、蕾米莉亚x丰聪耳神子

4、芙兰朵露x丰聪耳神子

5、蕾米莉亚x圣白莲

6、芙兰朵露x圣白莲


title: [JSOI2012] 玄武密码

background:
在美丽的玄武湖畔，鸡鸣寺边，鸡笼山前，有一块富饶而秀美的土地，人们唤作进香河。相传一日，一缕紫气从天而至，只一瞬间便消失在了进香河中。老人们说，这是玄武神灵将天书藏匿在此。

很多年后，人们终于在进香河地区发现了带有玄武密码的文字。更加神奇的是，这份带有玄武密码的文字，与玄武湖南岸台城的结构有微妙的关联。于是，漫长的破译工作开始了。

description:
 经过分析，我们可以用东南西北四个方向来描述台城城砖的摆放，不妨用一个长度为 $n$ 的序列 $s$ 来描述，序列中的元素分别是 `E`，`S`，`W`，`N`，代表了东南西北四向，我们称之为母串。而神秘的玄武密码是由四象的图案描述而成的 $m$ 段文字。这里的四象，分别是东之青龙，西之白虎，南之朱雀，北之玄武，对东南西北四向相对应。

现在，考古工作者遇到了一个难题。对于每一段文字 $t$，求出其最长的前缀 $p$，满足 $p$ 是 $s$ 的子串。

inputFormat:
第一行有两个整数，分别表示母串的长度 $n$ 和文字段的个数 $m$。

第二行有一个长度为 $n$ 的字符串，表示母串 $s$。

接下来 $m$ 行，每行一个字符串，表示一段带有玄武密码的文字 $t$。

outputFormat: 对于每段文字，输出一行一个整数，表示最长的 $p$ 的长度。

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

- 对于 $20\%$ 的数据，保证 $n \leq 100$，$m \leq 50$。
- 对于 $40\%$ 的数据，保证 $n \leq 2 \times 10^4$，$m \leq 2 \times 10^3$。
- 对于 $70\%$ 的数据，保证 $n \leq 10^6$，$m \leq 2 \times 10^4$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^7$，$1 \leq m \leq 10^5$，$1 \leq |t| \leq 100$，$s, t$ 中均只含字母 `E` `S` `W` `N`。


title: [JSOI2012] 智者的考验

description:
公元$1371$年，太祖下令在北极阁上大建庙宇，短短几年，鸡笼山上便建成了帝王庙、关公庙、真武庙、功臣庙、蒋王庙、都城隍庙、卞壶庙、忠烈庙、刘越王庙、曹武惠王庙共十座庙宇，统称为“十庙”。

后来，为了方便人们来鸡笼山进香礼佛，太祖下令疏通了鸡笼山下已淤塞多年的潮沟。于是，便有了“进香河”。

然而并不是所有人都可以来鸡笼山的，太祖在进香河上修建了一座石桥，中间悬挂了一块高$Rx$宽$Ry$的机关格图（如下图所示）。所有格子都是活动可翻转的，一面是白色，一面是黑色，这里我们用$0$表示白色，用$1$表示黑色。初始情况下，所有格子都是白色面朝前的。有$Rx+Ry$个机关按钮，对应$Rx$行和$Ry$列。一个按钮一旦触发，就会引发对应的一行或一列的格子同时翻转。

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

同时，善于识天象的谋臣刘基给出了一种黑白状态，称之为“厄运星”。每一位过往前去鸡笼山的人都需要触发且只触发一个按钮，触发后，如果来访者呈“厄运星”形状，则不允许通过。

每一天要来鸡笼山的人数$N$是事先就知道的，同时天朝神威浩荡，每一位来者一开始总是有很大概率触发编号为$1$的按钮，我们不妨用数列$A_1$,$A_2$,$\dots$,$A_N$来表示，问题保证了初始时候的$A$数列全为$1$。同时在整个问题中，$A_i$满足$1 \leq A_i \leq Rx+Ry$。太祖很关心那些不允许去鸡笼山的人数。于是他时不时就会询问关于“某一段时间内会有多少人不能通过“厄运星”的考验”。然而那些前来鸡笼山的文人墨客并不愿意如此单一的操作。来访者有可能会突然决定修改自己的触发按钮。更麻烦的情况，结伴而来的连续若干人会突然决定修改触发按钮并且都去触发同一个按钮。

现在这麻烦的问题交给了你。

inputFormat:
输入文件第一行有$2$个数字$Rx$和$Ry$表示机关格图的高和宽（如图所示）。之后$Rx$行每一行$Ry$个数字，描述了“厄运星”形状，每一个数字都满足非$0$即$1$。

之后一行有两个数字，分别为$N$和$M$，表示人数和询问修改的次数。

之后$M$行，对应$M$次询问或修改。每一行先有一个数字$t$：

若$t$为$0$：之后有$2$个数字$d$和$x$，表明将$A_d$修改为$x$。

若$t$为$1$：之后有$2$个数字$l$和$r$，表明询问第$l$个人到第$r$个人中有多少人触发按钮后会出现“厄运星”形状，从而无法通过。

若$t$为$2$：之后有$3$个数字$l$,$r$和$x$，表明将$A_l$,$A_{l+1}$,$\dots$,$A_{r-1}$,$A_r$都修改为$x$。

outputFormat: 对于每一次询问(即$t$为$1$的情况)，输出单独一行，一个整数描述了在区间$[l,r]$中满足要求的人数。


title: [JSOI2012] 爱之项链

description:
在进香河，流传着这样一段美丽的故事。$zyg$与$kzn$是两个生活在进香河的孩子，一天，他们两人闹矛盾了，于是$zyg$送给了$kzn$一条精美的爱之项链。从此他们幸福生活在一起。

这则故事的真实性到今天已经没有意义了，然而我们关注的是那一条精美的爱之项链。这是一条由$N$个精致的戒指与一块特殊纪念品相连而成的环形，如下图中的爱心符号正是一种特殊纪念品。(据说是$2012$年情人节时$zyg$特意托人订制的)上面的每一枚戒指又是由$M$个带磁性的特殊彩色球状物组成的环形。也许你会认为，这所谓的戒指，更像是一条条小项链。

下图给出了一种可行的方案，其中左边描述的是单一的一枚戒指，右图描述的是项链。

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

这里，所有带磁性的特殊彩色球状物的颜色只有$R$种，这里我们用$1$到$R$来表示。如果一枚戒指可以通过顺时针或逆时针的旋转后与另外一枚戒指相同，则认为这是两枚相同的戒指。

对于一条爱之项链，要求满足任何相邻两枚戒指必须是不相同的。同时，特殊纪念品左右两枚戒指也必须是不同的。

现在给定$N$，$M$和$R$，问究竟有多少种不同的爱之项链。

注意：

$1$、特殊纪念品的插入位置不同，也许会得到不同的爱之项链。

$2$、这里我们只考虑旋转后是否相同，不考虑翻转操作，这一点不论是对于每一枚戒指，还是对于整条项链，都是这样的。

inputFormat: 一行，三个正整数，分别是$N$，$M$和$R$。

outputFormat: 一行，表示有多少种不同的爱之项链。你只需要将答案模$3214567$。


title: [JSOI2012] 越狱老虎桥

background:
这里，是美丽的南京；这里，是秀美的进香河；这里是安逸的老虎桥。

如果说进香河的美，美在其秀美的风光，倒不如说是美在了那惬意的南京古典小巷式生活。如果说进香河的迷人，在其淳朴的民风，倒不如说是那被历史掩埋了的秘密吸引着人们好奇的心。

也许很多人都还记得，老虎桥监狱，北洋时期江南最大的监狱，在近一个世纪中，面对满清、北洋、民国、新中国几朝兴衰，名称屡次更替，沧桑尽显其中。

现在的人们，恐怕很难相信，到底有多少惊心动魄的事情曾经就在这里上演。

description:
那是$1948$年的冬天，南京地下组织的一支小分队决定偷袭老虎桥监狱，救出被困的数百名人员。那时的老虎桥监狱，被$N$层电网围了起来，由内而外，依次编号为$1$,$2$,$\dots$,$N$。第$1$层电网接有高压电。有$M$条高压线，连接了所有电网，其中第$i$条高压线连接了第$a_i$和$b_i$层电网，如果要破坏第$i$条高压线，需要至少动用$T_i$位特工。面对这么多层电网，偷袭小分队犯愁了。至少需要破坏一层电网，否则是无法偷袭成功的。

然而，狡猾的间谍却知道了这件事情，为了破坏偷袭计划，敌人秘密地又增加了一条高压线，不让偷袭小分队的成员发现。

为了能够偷袭成功，不论新增的这一条秘密高压线是连接哪两层电网的，小分队都必须要破坏且仅破坏一条高压线，使得至少有一层电网不通电。注意，对于新增的高压线，我们并不知道需要多少位特工才能成功破坏。现在的问题是，偷袭小分队至少需要多少名特工呢？

决战就在今夜！

inputFormat:
第一行有$2$个整数，$N$和$M$，分别表示电网层数和高压线个数。
之后$M$行，每行$3$个整数，分别是$a_i$,$b_i$和$T_i$。

outputFormat:
输出只有一行，包含一个整数，表示最少需要动用的特工人数。
如果计划必然失败，则输出$-1$。

hint:
对于$30\%$的数据，$N \leq 200$，$M \leq 250$。

对于$70\%$的数据，$N \leq 50000$，$M \leq 100000$。

对于$100\%$的数据，$N \leq 500000$，$M \leq 1000000$，$T \leq 100000$。

对于第二组样例，新增的高压线只有可能出现在$2$和$3$，$2$和$4$或$3$和$4$之间。

如果出现在了$2$和$3$之间，则只能破坏$1$和$4$之间的高压线；如果出现在$2$和$4$之间，则只能破坏$1$和$3$之间的高压线；如果出现在$3$和$4$之间，则只能破坏$1$和$2$之间的高压线。

所以，至少需要出动$3$位特工，才能应付所有可能情况。


title: [WC2017] 棋盘

description:
小 Z 在一块棋盘上玩游戏。这块棋盘是一个由 $n$ 个顶点和 $m$ 条边组成的无向连通图，图上的顶点编号为 $[1,n]$ 中的正整数。游戏开始时，每个顶点上都放有一个棋子，每个棋子上有一个 $[0,n-1]$ 中的整数，表示棋子的编号。不同棋子的编号互不相同。

每次操作时，小 Z 需要先选择棋盘上的一条边，这条边的一个端点此时放有 $0$ 号棋子。然后，小 Z 将这条边两个端点上的棋子交换。

现在你已经知道棋盘的模样，以及初始状态下每个顶点上的棋子编号。小 Z 想请你回答 $q$ 个询问。每个询问指定了棋盘的目标状态，你需要回答能否通过若干次操作，将棋盘由初始状态变为这个目标状态。

inputFormat:
第一行输入三个正整数 $n,m,q$，分别表示图中的顶点数、边数，以及询问的个数。

接下来 $m$ 行，每行两个整数 $u,v(1\leq u,v\leq n)$，表示图中有一条连接 $u,v$ 两顶点的无向边。保证 $u\neq v$，即图中不存在自环。保证给出的图是连通图，即任意两个顶点都可以经过若干条边而相互到达。

接下来一行有$n$ 个空格隔开的整数，其中第$i$ 个整数表示初始状态下 $i$ 号顶点上的棋子的编号，保证编号都为 $[0,n-1]$ 中的整数，且两两不同。

接下来 $q$ 行，每行有 $n$ 个空格隔开的整数，表示一个询问，其中第 $i$ 个整数表示目标状态中第 ii 号顶点上的棋子的编号，保证编号都为 $[0,n-1]$ 中的整数，且两两不同。

outputFormat: 输出 $q$ 行，每行一个字符串 ```Yes``` 或者 ```No``` 作为回答。```Yes``` 表示从棋子的初始状态可以经过若干次操作而达到询问中所指定的目标状态，```No``` 表示不存在这样的操作步骤。注意：```Yes``` 和 ```No``` 的首字母都是大写的。


title: [LnOI2019] 加特林轮盘赌

background: 加特林轮盘赌是一个养生游戏。

description:
与俄罗斯轮盘赌等手枪的赌博不同的是，加特林轮盘赌的赌具是加特林。

加特林轮盘赌的规则很简单：在加特林的部分弹夹中填充子弹。游戏的参加者**坐在一个圆桌上**，轮流把加特林对着自己的头，扣动扳机一秒钟。中枪的自动退出，坚持到最后的就是胜利者。

我们使用的是 2019 年最新技术的加特林，他的特点是**无需预热、子弹无限**，每一个人，在每一回合，中枪的概率是完全相同的 $P_0$。

每局游戏共有 $n$ 只长脖子鹿，从 1 长脖子鹿开始，按照编号顺序从小到大进行游戏，绕着圆桌不断循环。

游戏可能会循环进行多轮，直到场上仅剩下最后一只长脖子鹿时，游戏结束。

给出 $P_0$ 和 $n$，询问 $k$ 号长脖子鹿最终成为**唯一幸存者**的概率 $P_k$。

**如果 $P_0=0$，我们认为胜者为 $1$ 号。**

outputFormat: 一个浮点数 $P_{k}$，误差应该小于 $10^{-8}$。（请保留更多位数的小数）

hint:
- 对于 $10\%$ 的数据，$n \le 100$。
- 对于 $30\%$ 的数据，$n \le 500$。
- 对于另外 $20\%$ 的数据，$k = n$。
- 对于 $100\%$ 的数据，$1 \le k \le n \le 10^{4}, 0 \le P_0 \le 1$。

所有数据的时间限制为 1000ms，空间限制为256MB，可开启 O2 优化。


title: Derivation

description:
小 R 学会微积分中求导这一概念后，他的数学老师要求他开始做一部分导数的练习题加深自己的理解。

但颖悟绝伦的小 R 对繁复的练习题并不感兴趣。他希望你帮他设计一个程序，计算一个给定函数 $f(x)$ 的导数。

如果你对导数这一概念并不熟悉，请参阅【说明】中的内容。

inputFormat:
第一行一个正整数 $T$，表示小 R 要完成的练习题数量，亦即测试数据的组数。

每组测试数据的第一行是一个非空字符串，描述了输入的函数 $f(x)$。设 $p=998244353$。

字符串中可能包含的元素有：

1. 系数为 $1$ 的单项式，包括 $x^1,x^2,x^0$ 等，我们保证指数为非负整数（为 $1$ 时不省略）且不超过 $p-1$。所有幂号用 `^` 代替。
2. 常数，如 $0,19260817$ 等；我们保证一切常数是非负整数且不超过 $p-1$。
3. 复合函数。将以上两种函数组合的方式可以为加乘幂，括号等。数学中会省略乘号和括号，但我们保证任意情况下都不省略（也不会无意义冗余，即不存在 `((x)),(3)+(4)`）；保证任何指数都是常数，即不存在 $x^{g(x)}$ 的情况。

经过以上规定，我们发现 $f(x)$ 求导后一定是一个多项式函数。如果你对数据的输入形式仍有不确定，可以观察附加样例文件。

由于输出这样的函数存在技术困难，为确认你的输出是正确的，测试数据的第二行为两个整数，值在 $[0,p)$ 之间。你需要输出两个整数，表示这些整数代入导函数后的值模 $p$ 的结果。

注意：本题中认为 $0^0=1$。

outputFormat: 输出 $T$ 行，每行两个整数，已在【输入格式】中说明它们的意义。

hint:
规定字符串长度不超过 $10^4$，字符串总长不超过 $5 \times 10^5$。

| 子任务编号 | 特殊性质                                                  | 分值 |
| :----------: | :---------------------------------------------------------: | :----: |
| 1          | $T \le 10^4$，字符串长度不超过 $20$，出现的常数不超过 $9$ | 20   |
| 2          | $T \le 100$，输入是一个化简后的多项式                     | 15   |
| 3          | $T \le 100$，出现的常数不超过 $9$                         | 15   |
| 4          | $T \le 100$，不存在多项式求幂                             | 20   |
| 5          | $T \le 100$                                               | 30   |

我们提供了 5 个附加样例文件，分别满足 5 个子任务的限制。

链接: https://pan.baidu.com/s/1dVSy8tU3pqGoq1-7CFYtBw 提取码: ya2u

**我们只保证以下定义在本题中适用。**

$f(x)$ 的导数是一个函数 $f'(x)$，满足：

$$ \displaystyle \lim_{h \to 0} f'(x)=\dfrac{f(x+h)-f(x)}{h} $$

我们称 $\displaystyle \lim_{x \to a}g(x)=L$ 当且仅当对于任何实数 $\epsilon > 0$ 我们都可以找到一个实数 $\delta > 0$ 使得 $\lvert g(x)-L\rvert < \epsilon$ 若 $0 < \lvert x - a \rvert < \delta$。

你可能用到以下的求导公式：

1. $f(x)=C,f'(x)=0$，其中 $C$ 是一常数。
2. $f(x)=x^n,f'(x)=nx^{n-1}$，其中 $n$ 为非 $0$ 常数。
3. $(f(x)+g(x))'=f'(x)+g'(x)$
4. $(f(x)g(x))'=f'(x)g(x)+f(x)g'(x)$
5. $(f(g(x)))'=f'(g(x))g'(x)$