title: [MtOI2019] 恶魔之树

background:
在 Kirito 和 Eugeo 还没有与 Alice 前往北之洞窟的时候，Eugeo 每天只能用龙骨斧砍恶魔之树——基家斯西达……

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

~~请忽略bilibili的水印~~

description:
Kirito 和 Eugeo 每天砍树觉得很无聊，于是开始比谁砍出好声音的次数多。渐渐地，他们发现这样也没有意思了，于是在这个基础上改了一点：

每个人去砍树前，会随机得到一个长度为 $n$ 的数列 $s_1, s_2, \dots, s_n$ 。最初每个人的得分都是 $1$，当第 $i$ 次砍出了一个好声音时，得分就变成了原来的得分与 $s_i$ 的最小公倍数，也就是常说的 ${\rm lcm}$。

现在 Kirito 已经得到了一个长度为 $n$ 的数列 $s_1, s_2, \ldots, s_n$ 。他想知道，如果每一次砍出好声音的概率是 $50\%$ 时他的期望得分。

由于 Kirito 不想看到小数，所以请你告诉 Kirito 答案乘 $2^n$ 对 $p$ 取模的值。

inputFormat:
共 $2$ 行。

第 $1$ 行包含 $2$ 个正整数 $n$ 和 $p$ ，代表数列的长度和给定的模数。**保证模数为质数**

第 $2$ 行包含 $n$ 个正整数，第 $i$ 个数代表 $s_i$。

outputFormat: 共 $1$ 行，包含 $1$ 个正整数，代表得分的期望值乘 $2^n$ 对 $p$ 取模的结果。

hint:
#### 样例解释 1

一共有 $8$ 种情况：

- 没有出现好声音，得分为 $1$，概率为 $\frac{1}{8}$。

- 只有第一次出现了好声音，得分为 $1$，概率为 $\frac{1}{8}$。

- 只有第二次出现了好声音，得分为 $2$，概率为 $\frac{1}{8}$。

- 只有第三次出现了好声音，得分为 $3$，概率为 $\frac{1}{8}$。

- 只有第三次没有出现好声音，得分为 $\operatorname{lcm}(1, 2)=2$，概率为 $\frac{1}{8}$。

- 只有第二次没有出现好声音，得分为 $\operatorname{lcm}(1, 3)=3$，概率为 $\frac{1}{8}$。

- 只有第一次没有出现好声音，得分为 $\operatorname{lcm}(2, 3)=6$，概率为 $\frac{1}{8}$。

- 每一次都砍出了好声音，得分为 $\operatorname{lcm}(1, 2, 3)=6$，概率为 $\frac{1}{8}$。

所以期望值为 $\frac{1}{8}+\frac{1}{8}+\frac{2}{8}+\frac{3}{8}+\frac{2}{8}+\frac{3}{8}+\frac{6}{8}+\frac{6}{8}=3$

乘上 $2^3$ 得到答案为 $24$。

### 子任务

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^5$，$10^7 \leq p \leq 1.1 \times 10^9$且$p$为质数，$1\leq s_i\leq 300$。

本题共 $7$ 个子任务，各子任务的分值和限制如下：

子任务 $1$（$3$ 分）：$n=1$。

子任务 $2$（$7$ 分）：$n=18$。

子任务 $3$（$10$ 分）：$n=100$，$s$ 中不同的正整数不超过 $18$ 个。

子任务 $4$（$20$ 分）：$n=100$，不存在 $1\leq i \neq j \leq n$，使得 $s_i=s_j$。且保证数据随机。

子任务 $5$（$20$ 分）：$1\leq s_1, s_2, \ldots, s_n \leq 100$。

子任务 $6$（$20$ 分）：$1\leq n \leq 10^4$。

子任务 $7$（$20$ 分）：无特殊限制。

------

谨以此题庆祝刀剑10周年。~~好像晚了几个月...~~

### 题目来源

[MtOI2019 Extra Round](https://www.luogu.org/contest/22840) T4

出题人：CYJian

验题人：suwAKow


title: 【CSGRound2】守序者的尊严

type: P

background:
由于 Y 校最近进行了对学校食堂的全面改革与对小卖部的全面整治(乱搞)，导致学校小卖部卖的零食被禁售了；学校食堂的炸鸡窗口也消失了；

并且学校的学生处 Q 主任严禁学生点外卖，日夜监察。

都说民以食为天，由于整天挨饿，全校同学处于水深火热之中。

description:
zhouwc 的朋友（朋友就是自己系列）小 Z 由于饥饿难忍，不得不铤而走险点外卖。

但是学校的 Q 主任为了能够抓住点外卖的学生布置了天罗地网——监控。

但是由于学校给 Q 主任的经费有限，所以这些监控不能持续工作，工作一秒之后便要暂停休息一秒，**即开启一秒后关闭一秒再开启一秒...以此类推**。

还是由于 Q 主任的经费有限，这些监控被排成了一条直线，这条直线便在学生通往学生外卖驻点——二号门（没有门卫）的必经之路上。

因为小 Z 修习了疾跑技能，所以小 Z 通过任意个数关闭的监控的时间均为
 $1$（即一次行动可以经过若干个未开的监控）。

由于小 Z 想吃外卖又不想受到正在监控室看着监控的 Q 主任的处分，请你告诉他至少要多少时间才能安全到达外卖驻点。

inputFormat:
共 $2$ 行。

第一行一个正整数 $n$，表示在这条路上一共有 $n$ 个监控。

第二行共有 $n$ 个数。表示在第 $0$ 秒是这些监控的开关情况，$0$ 表示监控关闭，$1$ 表示监控开启，并保证第一个监控一定是关闭的。

outputFormat: 共一行，表示小 Z 安全到达外卖驻点所需要的时间。

hint:
#### 数据范围：

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

对于 $30\%$ 的数据，$1 \leq n \leq 100$

对于 $50\%$ 的数据，$1 \leq n \leq 10^3$

对于 $70\%$ 的数据，$1 \leq n \leq 10^5$

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

监控的开关情况均用 $0$ 和 $1$ 来表示。

#### 样例解释一：

小 Z 在第一秒时冲到第二个监控处，用时 $1$ 秒，总用时 $1$ 秒。

第二秒时，监控的开关状况变为了 $1 1 0 0 1 0$。

这时，小 Z 迅速从二号监控处冲到了四号监控处，用时 $1$ 秒，总用时 $2$ 秒。

第三秒时，监控的开关状况变为了 $0 0 1 1 0 1$。

这时，小 Z 迅速从四号监控处冲到了五号监控处，用时 $1$ 秒，总用时 $3$ 秒。

第三秒时，监控的开关状况变为了 $1 1 0 0 1 0$。

这时，小 Z 迅速从五号监控处冲出了监控区域，用时 $1$ 秒，总用时 $4$ 秒。

#### 样例解释二

小Z在第一秒直接冲出了监控区域。


title: 【L&K R-03】音游大计算

description:
小 K 喜欢玩音游，特别是一款叫做 dimou 的音游。dimou 的判定机制是这样的：dimou 是单面（不像某 dy 开头的东西）下落式音游。具体来说，在屏幕底端有一条判定线。一首曲子有若干打击点（即 key，可以看做一条与判定线平行的只有左右宽度的线段），每个 key 会在某个时刻从顶端匀速下落，而玩家需要尽量精准地在每个 key 与判定线重合时点击它。

当然，玩家有可能在 key 接触判定线之前就点击了，也可能在 key 已经落到判定线之下时才点击。这时候，就需要考虑游戏的判定系统，以统计玩家完成一首曲子的情况。dimou 有三种判定：perfect，good 和 miss。总共有六种情况——

情况 $1$：玩家点击的时间在某个 key 下落至其与判定线重合的时间的前 $1s$ 或更多（记为 $\triangle t\ge1$，下同），则不会产生任何判定效果（等于无意义点击）；

情况 $2$：$0.6\le\triangle t<1$，则此 key 产生一次 miss 判定并消失；

情况 $3$：$0.2\le\triangle t<0.6$，则此 key 产生一次 good 判定并消失；

情况 $4$：$-0.2<\triangle t<0.2$（负数代表在 key 到达判定线之后点击），则此 key 产生一次 perfect 判定并消失；

情况 $5$：$-0.6<\triangle t\le-0.2$，则此 key 产生一次 good 判定并消失；

情况 $6$：$\triangle t\le-0.6$，则此 key 在点击之前就会落出屏幕，记一次 miss 判定并消失（即在此 key 落于判定线之下 $0.6s$ 后自己产生一次 miss 判定），点击对此 key 不会产生任何判定效果。

除此之外，dimou 还有最大连击判定（max combo）。一段连击（combo）是指从某一个非 miss 的判定开始，到某一个非 miss 的判定结束（在这段区间内 **（按时间顺序）** 没有任何 miss 判定），判定的总数量。而 max combo 则指的是所有 combo 的最大值。

除此之外，dimou 还有一些判定规则。一次点击的位置可以看做判定线上的一个点，则过此点作判定线的垂线，只有与此垂线有交点（交点可在端点）的 key 才**可能**因此次点击产生判定效果。并且， **每次点击只会对可能产生判定效果的 key 中位置（纵向高度）最低（离屏幕顶端最远）的一个产生判定效果。** 形象地说，你只有点击某个 key 下方的位置才可能将其消除，并且若两个 key 有上下相对距离地一起下落，那么如果点击可以使下面的 key 消除，则一定不会使上面的 key 消除。特殊地，如果一次点击对两个或以上位置（高度）相同的 key 都可能产生判定效果，且没有更低的可能产生判定效果的 key，则这些 key 都会被消除。

为了把一首曲子打好，小 K 决定背谱，即记住所有 key 的位置和它们下落到判定线的时间。当然，小 K 也会事先决定好自己的打法，即决定在什么时间在什么位置点击。可是小 K 并不会计算自己的打法可以得到的最终成绩。请你帮小 K 算算，他的打法会得到多少 perfect 判定，多少 good 判定，多少 miss 判定，以及 max combo。

注意：小 K 不会在同一时间点击两次或以上。如果同一时间有多个判定，按 miss，good，perfect 的顺序依次处理。

inputFormat:
第一行两个正整数 $n,m$，代表 key 数量与小 K 的点击数。

紧接着 $n$ 行，每行三个浮点数（小数位数不超过 $5$ 位）$t_i,a_i,b_i$，分别表示每个 key 从曲子开始算起到达判定线的时间，其左端点位置，右端点位置。

紧接着 $m$ 行，每行两个浮点数（小数位数不超过 $5$ 位）$T_i,x_i$，分别表示小 K 每次点击从曲子开始算起的时间和其位置。

outputFormat: 一行，输出四个非负整数，两两用单个空格隔开，分别代表 perfect 数，good 数，miss 数和 max combo。

hint:
样例 $3$：[输入](https://www.luogu.com.cn/paste/qrbt8fnq)，[输出](https://www.luogu.com.cn/paste/evke45h8)。

样例 $4$：[输入](https://www.luogu.com.cn/paste/a71namso)，[输出](https://www.luogu.com.cn/paste/jgpcani2)。

【样例解释】

对于样例 $1$：$5$ 个 key 产生的判定按时间顺序分别为
 miss，good，perfect，good，miss。第一次和最后一次点击不产生判定效果。

对于样例 $2$：按时间顺序，第一次点击（$T=0.0$），可能产生判定效果的有（按输入顺序）第 $1,2,4$ 个 key。第 $1,2$ 个 key 同时到达判定线，第 $4$ 个 key 比第 $1,2$ 个 key 高。因此第一次点击只让第 $1,2$ 个 key 产生 perfect 判定。第二次点击（$T=0.6$），与其垂线有交点的有第 $3,4$ 个 key，但第 $3$ 个 key 此时已经产生 miss 判定并消失，因此这次点击让第 $4$ 个 key 产生一次 perfect 判定，此时在同一时间出现了两个判定 perfect，miss，按照规则先处理 miss 再处理 perfect。所以，所有判定按时间顺序分别是 perfect，perfect，miss，perfect。容易发现 miss 把判定序列分成了两段，第一段的 combo 为 $2$，第二段的 combo 为 $1$，所以 max combo 为 $2$。

【数据范围】

对于 $30\%$ 数据，$n,m\le5000$。

对于另外 $20\%$ 数据，$n\le5000$，$m\le114514$。

对于另外 $10\%$ 数据，所有 $a_i$ 相等，所有 $b_i$ 相等。

对于另外 $10\%$ 数据，$t_i,T_i,a_i,b_i,x_i$ 在 $[0,10^4]$ 中随机生成。

对于 $100\%$ 数据，$1\le n,m\le114514$，$0\le t_i,T_i,a_i,b_i,x_i\le 10^4$，$a_i\le b_i$。


title: 「SWTR-2」Crystal Balls

background:
$\mathrm{Ethan}$ 有一些可以释放强大能量的水晶球，他将要用这些水晶球合成可以消灭敌人的魔法。

- $a\equiv b\mathrm{\ (mod\ m)}$ 表示 $a$ 和 $b$ 对模 $m$ 同余，即 $(a-b)/m$ 为整数。

description:
$\mathrm{Ethan}$ 有 $n$ 个水晶球，现在他将这些水晶球排成一行，每一个水晶球上面有一个能量值，且**要么是绿色，要么是紫色**。

- 下文中，$P$ 代表紫色，$G$ 代表绿色。

$\mathrm{Ethan}$ 现在要按以下方式取走这些水晶球：

1. 取走**最左端**的水晶球。

2. 假设取走的水晶球的颜色为 $c_1$，能值为 $x_1$，**剩余最左端**的水晶球的颜色为 $c_2$，能量为 $x_2$，取出水晶的次数为 $cnt$（包括这一次）。

- 如果 $c_1=c_2$，那么 $\mathrm{Ethan}$ 会将这两个水晶球合成为一个大水晶球（本次取出的水晶球仍计入答案总数内，详情见样例），颜色为 $c_1$，能量值为 $x_1 \times x_2$，放在水晶球序列的**最左端**。

- 如果，$c_1=P,c_2=G,cnt\equiv 1\mathrm{\ (mod\ 2)}$，那么 $\mathrm{Ethan}$ 会将剩下的水晶球的**颜色反转**（即绿色变紫色，紫色变绿色）。

- 如果仍不能满足上面的条件，那么 $\mathrm{Ethan}$ 会将剩下的水晶球**序列翻转**。

就这样，直到最后只剩下一个球，此时 $\mathrm{Ethan}$ 会直接取走最后一个球，求取走的水晶球的**能量值之和**。

由于答案很大，请对 $p$ 取模。

inputFormat:
第一行，两个**正整数** $n,p$，分别表示水晶球的个数和模数。

第二行，$n$ 个**正整数** $a_1,a_2,\dots,a_n$，$a_i$ 表示第 $i$ 个水晶球的能量值。

第三行，一个由字符 $P$ 和字符 $G$ 组成的字符串，如果第 $i$ 个字符为```P```，那么该水晶球是紫色，否则为绿色。

outputFormat: 一个整数，表示取走的水晶球的能量值之和对 $p$ 取模的值。

hint:
---

### 样例说明

**样例 $1$：**

$\mathrm{Ethan}$ 首先会取出最左端的水晶球，颜色为 ```G```，答案加上它上面所写上的数字，即 $1$，剩下的水晶球翻转，序列变为 $4\ 3\ 2$ ```GGP```。（因为 $c_1=G,c_2=P$，取出水晶球的次数为奇数，不满足条件 $1,2$，所以序列翻转）。

再取出最左端的水晶球，颜色为 ```G```，答案加上 $4$，接着把剩下来最左端的水晶球与取走的水晶球合并成一个大的水晶球，写上的数字为 $12$，序列变为 $12\ 2$ ```GP```。

取出最左边的水晶球，颜色为 ```G```，答案加上 $12$，剩下的水晶球序列翻转，序列变为 $2$ ```P```。

取出最后一个的水晶球，答案加上 $2$，最终答案为 $1+4+12+2=19$。

**样例 $2$：**

先取出 $3$，$c_1=P,c_2=G,cnt=1$，颜色翻转

取出 $7$，$c_2=c_3=P$，将 $x_3$ 乘上 $x_2$，得到 $x_3=35$

取出 $35$，最终答案为 $3+7+35=45$

---

### 数据范围与约定

本题采用 $\mathrm{Subtask}$ 制。

$\mathrm{Subtask}\ 1:n\leq 2000,a_i\leq 10^9,p\leq 10^9,15\%$。

$\mathrm{Subtask}\ 2:n\leq 5\times 10^4,a_i\leq 10^9,p\leq 10^9,15\%$。

$\mathrm{Subtask}\ 3:n\leq 5\times 10^4,a_i\leq 10^{18},p\leq 10^{18},20\%$。

$\mathrm{Subtask}\ 4:n\leq 10^6,a_i\leq 10^9,p\leq 10^9,20\%$。

$\mathrm{Subtask}\ 5:n\leq 10^6,a_i\leq 10^{18},p\leq 10^{18},30\%$。

---

对于所有测试点，时间限制 $1s$，空间限制 $16MB$。


title: [COCI2009 Final Exam#1] PODJELA

description:
有 $n$ 个农民，他们住在 $n$ 个不同的村子里，这 $n$ 个村子形成一棵树，每个农民初始时有 $x$ 元钱。
每一次操作，一个农民可以从它自己的钱中，取出任意数量的钱，交给某个相邻村子的农民。
对于每个农民给定一个值 $v_i$，求最少需要多少次操作，使得每个农民最终拿到的钱 $\geq$ 给定的值。

inputFormat:
第一行包含一个整数 $n$ ，即农民数。
第二行包含一个整数 $x$ ，即每个农民初始时拥有的钱数。
第三行包含 $n$ 个整数，第 $i$ 个数表示 $v_i$ 。
接下来 $n-1$ 行每行包含两个整数, 表示树上的一条边。

outputFormat: 输出一行一个整数, 即最少需要的操作次数。

hint: 对于 $100\%$ 的数据，$1 \leq n \leq 2000,~0 \leq x \leq 10000,~\sum\limits_{i=1}^{n}v_i \leq n\times x$


title: [NOI2014] 消除游戏

description:
最近，小 Z 迷上了一款新型消除游戏。这款游戏在一个 $n\times m$ 的方格中进行。初始时方格中均为 $0 \sim 9$ 的整数。进行消除后方格中会出现空白，用 $-1$ 表示。为了方便，我们将第 $i$ 行，第 $j$ 列的数记为 $A_{i,j}$，并将其坐标记为 $(i,j)$。

给定三个参数 $l_{\min},l_{\max}$ 以及 $K$，玩家可以进行不超过 $K$ 次操作。对于每次操作，玩家需要在方格中找到一条长度为 $l$ 的路径。形式化地，该路径用两个长度为 $l$ 的序列 $x_1,x_2,\ldots,x_l$ 和 $y_1,y_2,\ldots,y_l$ 表示，需要满足如下条件：
1. $1\le x_i\le n,1\le y_i\le m$，其中 $1\le i\le l$，即 $(x_i,y_i)$ 对应于方格中的一个合法位置；
2. $\left|x_i-x_{i+1} \right|+ \left|y_i-y_{i+1} \right|=1$，其中 $1 \le i \lt l$，即 $(x_i,y_i)$ 与 $(x_{i+1},y_{i+1})$ 是方格中相邻的两个位置；
3. $x_i \neq x_j$ 或 $y_i \neq y_j$，其中 $1\le i \lt j\le l$，即路径不能经过重复的格子；
4. $A_{x_i,y_i} \neq -1$，其中 $1\le i\le l$，即路径不能经过空白的格子；
5. $A_{x_1,y_1} \neq 0$，即路径不能以数字 $0$ 为起点；
6. $l_{\min}\le l\le l_{\max}$，即路径的长度需要在给定的范围内。

将路径上的数字串成一个整数 $N$，形式化地
$$
N=\sum\limits_{i=1}^l A_{x_i,y_i}\times 10^{l-i}
$$

游戏会给出两个参数 $c_1,c_2$ 用于计算玩家本次操作的得分：
1. 如果数 $N$ 是质数，那么将获得**质数得分** $l^{c_1}$，否则获得**质数得分** $1$；
2. 如果数 $N$ 是回文数（即，将数 $N$ 的十进制表达看成一个字符串，这个字符串的逆序串和它本身完全相同），那么将获得**回文数得分** $l^{c_2}$，否则获得**回文数得分** $1$；
3. 如果**质数得分**和**回文数得分**均为 $1$，那么**本次操作的得分**为 $0$；否则**本次操作的得分**为**质数得分与回文数得分**之和。

每次操作过后，若**该次操作的得分**等于 $0$，那么你浪费了一次操作机会，而局面不会有任何改变。若**该次操作的得分**大于 $0$，则将路径上的数替换为空白，并使空白上方的数字垂直下落。形式化地，执行以下操作：
1. 执行 $A_{x_i,y_i}\leftarrow -1$，其中 $1\le i\le l$；
2. 枚举所有格子。如果存在某个格子 $(i ,j)$，满足 $i \neq n, A_{i,j} \neq -1, A_{i+1,j} = -1$，执行 $A_{i+1,j} \leftarrow A_{i,j}, A_{i,j}\leftarrow -1$。反复执行这个操作直到方格中不再存在这样的格子。

我们还会给你一个参数 $F$ ，在所有操作完成后，玩家的**最终得分** $S$ 的计算方式由 $F$ 决定：如果 $F$ 取值为 $0$，那么玩家的最终得分为所有操作的分数总和 $m$；如果 $F$ 取值为 $1$，那么玩家的最终得分为所有操作的分数总和 $m$ 除 $2^d$ 后向下取整，即

$$
S =
\begin{cases}
m, & F=0\\\\
\left \lfloor \frac{m}{2^d} \right \rfloor, & F=1
\end{cases}
$$

其中 $d$ 为最终方格中非空白格子的数目。

小 Z 沉迷于这个有趣的游戏中不能自拔。她想请你帮助, 针对给定的输入参数，给出游戏局面的操作方案。当然，最终得分越大越好。

inputFormat:
**本题是一道提交答案题。**

对于每个输入文件，输入的第 $1$ 行包含 $8$ 个用空格分隔的整数 $n, m, K, l_{\min}, l_{\max}, c_1, c_2, F$，含义同题面描述。

随后 $n$ 行，每行 $m$ 个整数，表示方格 A。数之间用一个空格分隔。

输入文件中不会包含多余的空行，行末不会存在多余的空格。

outputFormat:
针对给定的 $10$ 个输入文件 `game1.in ~ game10.in`，你需要分别提交你的输出文件 `game1.out ~ game10.out`。

输出文件第 $1$ 行为一个整数 $M (0 \leq M \leq K)$，为你的操作次数。

随后, 输出文件还应包含 $M$ 行，每行描述一次操作。对于每一行，最开始的整数$l$表示这次操作中选定路径的长度。接下来有 $2l$ 个数字，分别为 $x_1, y_1, x_2, y_2, \dots, x_l, y_l$。

输出文件中不应包含多余的空格和空行。一行的多个整数之间使用一个空格分隔。

hint:
#### 样例解释 1

$4$ 次消除得到的数与相应的分数分别是：$37$，得分为 $2+1=3$；$41$，得分为 $2+1=3$；$22$，得分为 $1+2=3$；$131$，得分为 $3+3=6$。总共得分为 $15$。可能存在更优的方案。

#### 样例解释 2

本方案仅一次消除操作。消除的数为 $11$，本次操作得分为 $2+2=4$。由于 $F=1$，最终得分为每次操作得分之和 $4$ 除以 $2^1 = 2$ 后下取整，为 $2$。若选择消除路径 $211$，则会得到本局面最佳分数 $4$。

#### 评分标准

对于每组数据，我们设置了 $9$ 个评分参数 $a_{10},a_9, \dots ,a_2$。如果选手的输出不合法，则得零分。否则，在你的方案中，若游戏得分为 $w_{user}$，你的分数将会由下表给出：

| 得分 |            条件             | 得分 |           条件           |
| :--: | :-------------------------: | :--: | :----------------------: |
| $10$ |    $w_{user}\ge a_{10}$     | $5$  | $a_5\le w_{user}\lt a_6$ |
| $9$  | $a_9\le w_{user}\lt a_{10}$ | $4$  | $a_4\le w_{user}\lt a_5$ |
| $8$  |  $a_8\le w_{user}\lt a_9$   | $3$  | $a_3\le w_{user}\lt a_4$ |
| $7$  |  $a_7\le w_{user}\lt a_8$   | $2$  | $a_2\le w_{user}\lt a_3$ |
| $6$  |  $a_6\le w_{user}\lt a_7$   | $1$  |  $0\lt w_{user}\lt a_2$  |

#### 附加文件

checker 需要自行编译后使用。

请前往 [Github](https://github.com/MikeMirzayanov/testlib) 下载 testlib.h 的最新源代码。


title: [MtOI2019] 时间跳跃

background:
就算知道方法，也绝对不能去改变过去，绝不能将存在的可能性转变为既定的现实，未来是没有人能预测的，是无法重来的，正因如此人们才能接受各种痛苦，不幸与飞来横祸，迈步前进。

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

description:
因为某些原因，Rintaro 欠了 Mayuri 一根香蕉。

为了封上 Mayuri 的嘴，Rintaro 与 Mayuri 约定，只要 Mayuri 答对这个问题，Mayuri 想要多少香蕉都没问题：

---

机关有 $N$ 条秘密通道，第 $i$ 条秘密通道的长度为 $i$，机关会从 $2^n$ 种选择方式种**等概率**随机选出一些秘密通道，如果选出来的这些秘密通道能组成一个凸多边形，那么这个方案的权值就是选出的秘密通道数量，否则权值为 $0$。

那么请你求出选出来秘密通道的权值的期望模 $10^9+7$ 的值。（两种选择秘密通道的方案不同当且仅当存在一个秘密通道，在一个方案中被选择，而在另一个方案中未被选择。注意，空集也算一个方案。）

---

Kurisu：这不就只要...

Rintaro：助手你闭嘴！

Mayuri 在纸上画呀画，结果啥也没画出来，于是 Mayuri 就只能找你帮忙了。

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

第一行一个正整数 $T$ 表示有 $T$ 次询问。

接下来 $T$ 行，每行一个正整数表示这一次询问的 $N$。

outputFormat: 你的输出应该包含一共 $T$ 行，第 $i$ 行一个非负整数表示询问的期望值模 $10^9+7$ 的值。


title: 「ACOI2020」课后期末考试滑溜滑溜补习班

background:
![T2](https://s2.ax1x.com/2020/01/12/lopS6f.png)

潮田 渚（Shiota Nagisa）因为理科不大好，自然会被仔细观察学生的杀老师发现，于是渚同学只得加入杀老师举办的课后期末考试滑溜滑溜补习班。至于为什么叫这个名字，额，你不能问我啊。

description:
在补习班上，因为多个学生会同时有需求，所以杀老师会制造分身用音速移动来回回答问题。

补习班上有 $n$ 个同学，他们每一个人都有一个问题。杀老师为了有序回答学生的问题，把所有学生排成了一列。第 $i$ 个学生的问题有一个困难值 $a_i$，杀老师回答第 $i$ 个学生的问题需要花费 $a_i$ 的精力。杀老师到了哪里，它就要解决那个学生的问题。杀老师最开始会解决序列中第一个同学的问题，他最后会去解决最后一个同学的问题。

杀老师每次解决完一个同学的问题到下一个同学的座位上就要花费 $k$ 点精力值。特殊的，如果杀老师想让自己轻松一点，可以不移动到下一个，可以直接到下两个，下三个，就不用解决跳过的同学的问题了。对应的，它会被学生调侃。受到打击的杀老师自然会花费格外的精力，花费的精力为 $k+(q-p-1) \times d$（当前位置为 $p$，跳到的位置为 $q$）。

当然的，杀老师也是有速度的啊，并且它想解决学生的一些问题，所以说杀老师最多只会跳过 $x-1$ 个学生，去解决下 $x$ 个学生的问题。

inputFormat:
第一行五个整数 $n,k,d,x,tp$，表示有 $n$ 个学生，只按顺序去到下一个学生的座位需要花费 $k$ 点精力，每多跳过一个学生就要多花费 $d$ 点精力值，每一次最多只能跳过 $x-1$ 个学生，是否是特殊数据。

- $tp=0$，第二行 $n$ 个整数 $a_{1\dots n}$，$a_i$ 表示第 $i$ 个学生的问题的困难值为 $a_i$。

- $tp=1$，第二行一个整数 $Seed$，作为种子，然后调用 $rnd$ 函数**依次**生成 $n$ 个整数，作为 $a$ 数组，$a_i$ 表示第 $i$ 个学生的问题的困难值为 $a_i$。

```cpp
inline int rnd () {
	static const int MOD = 1e9;
	return Seed = ( 1LL * Seed * 0x66CCFF % MOD + 20120712 ) % MOD;
}
```

outputFormat: 一行一个整数，表示杀老师解决完最后一个同学的问题最少需要花费多少精力。

hint:
#### 样例解释 #1

杀老师每次不能跳过学生，因此他必须依次移动并解决所有问题，故答案为解决问题所需的精力 $1+2+3+4+5=15$ 与移动所需的精力 $4 \times 3=12$，所以花费精力之和为 $27$。

------------
#### 数据范围

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

- Subtask 1（20 points），学生们学习认真听话，留下来的同学也会更少：$tp=0$，$n \leq 10^3$。
- Subtask 2（30 points），杀老师的速度快极了，并且学生们没时间吐槽它：$tp=0$，$n \leq 10^6$。
- Subtask 3（50 points），$tp=1$，其余无特殊限制。

对于 $100\%$ 的数据，$1 \leq n \leq 10^7$，$0 \leq k,d,a_i \leq 10^9$，$1 \leq x \leq n-1$。

------------
#### 提示

对于 $tp=1$ 的数据，$rnd$ 函数只用于减小输入量，标准算法不依赖该数据生成方式。


title: 「SWTR-4」Calculating Machine

background: 小 E 在用自己的 Calculating Machine 计算 $n$ 个**十进制**数 $a_1,a_2,\cdots,a_n$ 的和。

description:
小 E 计算几个数的和的方式为：

- 如果参与运算的数不止 $2$ 个，那么**从左往右**依次计算。

- 若两个数的位数不同，则位数少的数自动在前面补前导零，直到两数位数相同。

- 从两个数的最低位开始，计算当前位两个数码的和加上前一位的进位，写上这个和除以 $10$ 的余数。

- 进位规则：如果当前位两个数码的和加上前一位的进位小于 $7$，不进位；如果和大于等于 $7$ 且小于等于 $13$，则进一位；否则进两位。

例如：$2+4=6$，$7+8=25$，$61+6=177$，$38+169=217$，$3+900=1903$。

由于小 E 的计算机器被 360 安全病毒当成病毒杀死了，所以他想请你帮忙求出 $a_1+a_2+\dots+a_n$。

inputFormat:
第一行，一个整数 $n$ —— 表示参与运算的数的个数。

第二行，$n$ 个整数，$a_1,a_2,\cdots,a_n$ —— 表示从左往右所有参与运算的数，你也可以理解为 $a_i$ 在 $a_{i+1}$ 的左边。

outputFormat: 一行一个整数 —— 表示 $a_1+a_2+\cdots+a_n$。

hint:
【样例 $3$ 说明】

$345+379+573=1734+573=2317$。

【样例 $4$ 说明】

$1234+567+89+10=2801+89+10=3990+10=4000$。

【数据范围与约定】

对于 $10\%$ 的数据，$n=1$。

对于 $30\%$ 的数据，$n \leq 2$。

对于 $60\%$ 的数据，$n \leq 10$，$a_i \leq 10^5$。

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

【Source】

[Sweet Round 04](https://www.luogu.com.cn/contest/26414)$\ \ $A

idea：[ET2006](https://www.luogu.com.cn/user/115194)，std：[Alex_Wei](https://www.luogu.com.cn/user/123294)，验题：[Isaunoya](https://www.luogu.com.cn/user/96580) & [FrenkiedeJong21](https://www.luogu.com.cn/user/203968) & [chenxia25](https://www.luogu.com.cn/user/138400)


title: Ryoku 的探索

background:
Ryoku 对自己所处的世界充满了好奇，她希望能够在她「死」之前尽可能能多地探索世界。

这一天，Ryoku 得到了一张这个世界的地图，她十分高兴。然而，Ryoku 并不知道自己所处的位置到底在哪里，她也不知道她会什么时候死去。她想要知道如何才能尽可能多的探索这个世界。

description:
Ryoku 所处的世界可以抽象成一个有 $n$ 个点， $n$ 条边的带权无向连通图 $G$。每条边有美观度和长度。

Ryoku 会使用这样一个策略探索世界：在每个点寻找一个**端点她未走过**的边中**美观度最高**的走，如果没有边走，就沿着她前往这个点的边返回，类似于图的**深度优先遍历**。

探索的一个方案的长度是这个方案所经过的所有边长度的和（返回时经过的长度不用计算）。

她想知道，对于每一个起点 $s=1,2,\cdots,n$，她需要走过的长度是多少？

inputFormat:
输入包含 $n + 1$  行，其中第一行包含一个整数 $n$。
接下来 $n$ 行每行包含四个整数 $u,v,w,p$，描述了一条连接 $u$ 和 $v$，长度为 $w$，美观度为 $p$ 的无向边。

outputFormat: 输出包含 $n$ 行，每行一个整数，第 $i$ 行为 $s=i$ 时的答案。

hint:
**【样例 1 说明】**

以下为输入输出样例 1 中的图： （边上红色数组为 $p$，黑色为 $w$）

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

若起点为 $1$，顺序为 $1\to3\to5\to2\to4$，长度之和为 $7$。
若起点为 $2$，顺序为 $2\to3\to5\to1\to4$，长度之和为 $7$。
若起点为 $3$，顺序为 $3\to5\to1\to2\to4$，长度之和为 $8$。
若起点为 $4$，顺序为 $4\to1\to3\to5\to2$，长度之和为 $7$。
若起点为 $5$，顺序为 $5\to3\to1\to2\to4$，长度之和为 $8$。

---

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

对于 $40\%$ 的数据，$n\le 10^3$。
对于 $100\%$ 的数据，$3 \le n \le 10^6$，$1 \le u,v,p \le n$，$0\le w\le 10^9$，保证 $p$ 互不相同。


title: [P5350] 序列 (加强版)

background:
本题为 [P5350](https://www.luogu.org/problem/P5350) 的加强版。
本题很良心，不卡空间！

description:
有一个序列 $a_n$ 和 $q$ 次操作。

- `1 l r` 求区间 $[l,r]$ 的和
- `2 l r k` 区间 $[l,r]$ 赋值为 $k$
- `3 l r k` 区间 $[l,r]$ 加上 $k$
- `4 l1 r1 l1 r2` 将区间 $[l_1,r_1]$ 复制到 $[l_2,r_2]$ 处
- `5 l1 r1 l2 r2` 将区间 $[l_1,r_1]$ 与 $[l_2,r_2]$ 交换
- `6 l r` 翻转区间 $[l,r]$

最后还要输出整个序列，所有输出都要对 $10^9+7$ 取模。

为了卡掉某些乱搞做法，**本题强制在线**。

每次操作中，除了输入第一个数，其它所有数都需要异或 $\text{last}$ 才是实际的操作。
$\text{last}$ 为上一次 $1$ 操作的答案 $\pmod{10^9 +7}$，定义初始 $\text{last} = 0$。

inputFormat:
第一行两个正整数 $n,q$，表示序列长度与操作个数。
第二行 $n$ 个正整数，表示序列 $a$
接下来 $q$ 行，每行表示一次操作。

outputFormat:
对于每次操作，输出一行一个整数表示答案。
最后一行输出 $n$ 个整数，表示最终的序列 $a$。

hint:
【数据范围】
$1\le n,q \le 3\times 10^5$
$0\le a_i,k \le 10^9$
对于 $4,5$ 操作，保证 $r_1-l_1 = r_2-l_2$ 且 $[l_1,r_1] \cap [l_2,r_2] = \varnothing$

**不保证数据随机** 且 **没有梯度**
想交 ODT 的就算了吧！


title: [Kubic] Lines

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

description: 平面直角坐标系中有 $n$ 条直线，**任意三条直线不交于一点且没有两条直线重合**。显然这些直线形成了不超过 $\dfrac{n(n-1)}{2}$ 个**交点**。你可以从这些直线中选出一部分，一个点被**覆盖**当且仅当有**至少一条**被选中的直线经过了它。求最少选出多少条直线才能**覆盖**所有**交点**。

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

接下来 $n$ 行，每行有三个整数 $a,b,c$，表示一条解析式为 $ax+by+c=0$ 的直线。

**注意：输入数据不保证 $\gcd(a,b)=1$**。

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

hint:
对于 $100\%$ 的数据，$1\le n\le 10^5,|a|,|b|,|c|\le 10^9,a,b$ 不全为 $0$。

||分值|$n$|特殊性质|
|:-:|:-:|:-:|:-:|
|$\operatorname{Subtask}1$|$10$|$\le 20$|无|
|$\operatorname{Subtask}2$|$30$|$\le 100$|无|
|$\operatorname{Subtask}3$|$10$|无特殊限制|$ab=0$|
|$\operatorname{Subtask}4$|$50$|无特殊限制|无|

### 样例解释

一种方法是选出 $x+2y+3=0$ 和 $4x+5y+6=0$ 两条线。

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


title: 【XR-4】模拟赛

description:
X 校正在进行 CSP 前的校内集训。

一共有 $n$ 名 OIer 参与这次集训，教练为他们精心准备了 $m$ 套模拟赛题。

然而，每名 OIer 都有各自的时间安排，巧合的是，他们在接下来的 $k$ 天中都恰好有 $m$ 天有空打模拟赛。

为了方便管理，教练规定一个人必须按顺序打完 $m$ 套模拟赛题。

比如，小 X 在接下来的第 $2,3,5$ 天有空打模拟赛，那么他就必须在第 $2$ 天打第 $1$ 套模拟赛题，第 $3$ 天打第 $2$ 套模拟赛题，第 $5$ 天打第 $3$ 套模拟赛题。

教练需要为每一个人的每一次模拟赛做准备，为了减小工作量，如果在某一天有多个人打同一套模拟赛题，那么教练只需要在这一天准备一场使用这一套题的模拟赛即可。

你作为机房大佬，教练想请你帮他计算一下，他每天需要准备多少场模拟赛。

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

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数 $a_{i,j}$ 表示第 $i$ 个人在接下来的 $k$ 天中第 $j$ 个有空的日子为第 $a_{i,j}$ 天。

outputFormat: 一行 $k$ 个整数，第 $i$ 个整数表示接下来的第 $i$ 天教练需要准备的模拟赛场数。

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

- Subtask 1（13 points）：$n = m = k = 1$。
- Subtask 2（24 points）：$n = 1$。
- Subtask 3（24 points）：$m = 1$。
- Subtask 4（39 points）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,m,k \le 10^3$，$m \le k$，$1 \le a_{i,1} < a_{i,2} < \cdots < a_{i,m} \le k$。


title: 【XR-4】歌唱比赛

background:
**赛时提醒：本题不提供任何关于样例 4 以及无解的解释。**

**赛时提醒：本题不提供任何关于输出格式以及 Special Judge 的解释。**

**赛时提醒：抱歉，本题的 Special Judge 不忽略行末空格，请保证两行中没有多余字符。**

**赛时提醒：非常抱歉，本题输入数据是 Windows 格式，而非 Linux 格式，所以在末尾的 `\n` 之前有一个多余的 `\r` 字符。请使用 `scanf` 或 `cin` 读入数据，而非 `getline`，因为后者会多读入一个 `\r`。**

description:
小 X 参加了一场歌唱比赛。

经过一路鏖战，小 X 终于挺进了决赛，他的对手是小 Y。

这场歌唱比赛的冠军是由点赞数决定的，谁的点赞数高，谁就能夺冠。

小 X 和小 Y 依次演唱完自己的最后一首歌曲后，他们最终的点赞数确定了下来。

揭晓冠军的时刻终于到来了，主持人为了增加悬念，决定从小 X 与小 Y 的点赞数的最后一位开始，依次比较。

比如，小 X 的点赞数是 $37$，小 Y 的点赞数是 $28$。首先比较最后一位，小 X 是 $7$，小 Y 是 $8$，此时小 Y 暂时领先。再加上前一位，小 X 是 $37$，小 Y 是 $28$，此时小 X 暂时领先。比较结束，如果我们用 `X` 代表小 X 暂时领先，`Y` 代表小 Y 暂时领先，那么可以写下一个字符串 `XY`。

再比如，小 X 的点赞数是 $137$，小 Y 的点赞数是 $47$。如果我们再用 `Z` 表示小 X 与小 Y 的点赞数暂时一样，那么写下的字符串应该为 `XYZ`。

你作为一个精通 OI 的神仙，自然知道这种比较方式是非常不科学的，这样只是在无端拖延时间罢了，但是你却对最后写下的这个字符串很感兴趣。

现在，你得到了这个最后写下的字符串，你需要构造出一种可能的小 X 与小 Y 的点赞数。

当然，有可能不存在任何一种情况的点赞数满足这个字符串，那么你只需要输出 `-1` 即可。

为了方便你输出，请用前导零来补足位数。

inputFormat: 一行一个字符串 $s$，表示最后写下的字符串。

outputFormat:
如果有解：

- 第一行一个整数，表示小 X 的点赞数。
- 第二行一个整数，表示小 Y 的点赞数。

如果无解：

- 一行一个整数 `-1`。

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

- Subtask 1（11 points）：$\text{len}(s) = 1$。
- Subtask 2（42 points）：$s_i \in \{\texttt{X},\texttt{Y}\}$。
- Subtask 3（21 points）：数据保证有解。
- Subtask 4（26 points）：无特殊限制。

对于 $100\%$ 的数据，$s_i \in \{\texttt{X},\texttt{Y},\texttt{Z}\}$，$1 \le \text{len}(s) \le 10^6$。


title: 【XR-4】题

background: **赛时提醒：$0$ 是自然数，自然数就是非负整数。**

description:
小 X 遇到了一道题：

给定自然数 $a,b$，求满足下列条件的自然数对 $(x,y)$ 的个数：

$$y^2 - x^2 = ax + b$$

他不会，只好求助于精通数学的你。

如果有无限多个自然数对满足条件，那么你只需要输出 `inf` 即可。

inputFormat: 一行两个整数 $a,b$。

outputFormat:
如果个数有限，一行一个整数，表示个数。

如果个数无限，一行一个字符串 `inf`。

samples:
4 4
inf

hint:
#### 【样例 #1 说明】

$$(x,y) = (6,9)$$

---

#### 【数据范围】**

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

- Subtask 1（3 points）：$a = b = 0$。
- Subtask 2（6 points）：$0 \le a,b \le 2$，不存在无限个数的情况。
- Subtask 3（9 points）：$0 \le a,b \le 100$，不存在无限个数的情况。
- Subtask 4（13 points）：$0 \le a,b \le 10^3$，不存在无限个数的情况。
- Subtask 5（14 points）：$0 \le a \le 10^4$，$0 \le b \le 10^7$。
- Subtask 6（14 points）：$a = 0$。
- Subtask 7（14 points）：$b = 0$。
- Subtask 8（27 points）：无特殊限制。

对于 $100\%$ 的数据，$0 \le a \le 10^8$，$0\le b \le 10^{15}$。


title: 【XR-4】复读

background:
**赛时提醒：当机器人在这棵完全二叉树的根时，执行 `U` 是非法的，即你需要保证不可能出现这种情况。**

**赛时提醒：这棵二叉树是无限向下延伸的，即所有节点均有左子节点与右子节点，除了根的所有节点均有父亲。**

description:
小 X 捡到了一台复读机，这台复读机可以向机器人发号施令。机器人将站在一棵完全二叉树的根上，完全二叉树是无限延伸的。你将向复读机录入一串指令，这串指令单个字符可以是：

* `L`：命令机器人向当前节点的左子走；
* `R`：命令机器人向当前节点的右子走；
* `U`：命令机器人向当前节点的父亲走（若没有，则命令非法）。

录入指令后，复读机将会把指令无限复读下去。比如命令为 `LR`，那么机器人会遵从 `LRLRLRLR...` 一直走下去。

这棵完全二叉树上有一个 $n$ 个节点的连通块，保证这个连通块包含根节点。连通块上的每个节点都埋有宝藏，机器人到达过的地方如果有宝藏，则会将其开采。如果一个地方没有宝藏，机器人也可以到那里去。机器人也可以反复经过一个地方。

显然，这个连通块本身也是一棵二叉树。

现在，有人告诉了小 X 埋有宝藏的这棵二叉树的前序遍历，小 X 需要寻找到一条尽量短的指令，使得机器人能够挖掘出所有宝藏。

inputFormat:
一行一个字符串，由 `0123` 中的字符组成，表示埋有宝藏的这棵二叉树的前序遍历。

* `0`：表示这是一个没有儿子的节点。
* `1`：表示这是一个只有左子的节点。
* `2`：表示这是一个只有右子的节点。
* `3`：表示这是一个既有左子又有右子的节点。

outputFormat: 一个整数，表示最短指令的长度。

hint:
【样例 1 说明】

一种可行的最短指令为 `LRU`。

---

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

- Subtask 1（31 points）：$2 \le n \le 10$。
- Subtask 2（32 points）：$2 \le n \le 200$。
- Subtask 3（37 points）：无特殊限制。

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


title: 【XR-4】混乱度

description:
小 X 有 $n$ 种颜色的球，其中第 $i$ 种颜色的球共有 $a_i$ 个，同色的球无法区分。定义第 $l \sim r$ 种颜色的混乱度 $f(l, r)$ 为：将第 $l \sim r$ 种颜色的所有球排成一排，总共的方案数对 $p$ 取模后的值。小 X 想请你帮忙计算下列式子的值：

$$ \sum_{l=1}^n \sum_{r=l}^n f(l, r) $$

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

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

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


title: 【L&K R-03】密码串匹配

background:
众所周知，小 L 很喜欢用 $123321$ 做密码。每次登陆 Codeforces，都会看见显眼的一行提示：

```text
Your password is extremely weak or has been leaked . Please, change it ASAP.
(see https://haveibeenpwned.com/)
```

description:
在被机惨之后，小 L 痛定思痛，决定使用更安全的密码。小 L 设计出了一个可能长达 $200,000$ 位的仅由小写字母构成的密码，并保证没有人能记住，猜出或试出（包括小 L 自己）。

为了防止自己忘记整串密码（不用防止了，已经忘记了），小 L 编写了一个程序，可以存储小 L 的密码串 $T$，但是不能直接输出（因为这个程序可能会被他人使用），小 L 第一次会根据记忆还原出长度为 $l$ 的一个字符串 $P$，后面会根据程序的输出修改 $P$ 的某一位，这个程序可以求出当前猜测串 $P$ 与密码串 $T$ 的相同长度的字串的 **失配度** 。

定义字符 `a` 的值为 $1$，字符 `b` 的值为 $2$，以此类推，字符 `z` 的值为 $26$。定义两个字符串 $s,t$ 的失配度为对应位置上的值相减后的平方。

现在，小 L 想知道他的程序是否正确，请你也编写一个类似的程序。

inputFormat:
输入的第一行为三个数 $n,l,m$，分别表示密码串 $T$ 的长度 $n$，猜测串 $P$ 的长度 $l$，和操作次数 $m$。

接下来的两行有两个字符串，分别为 $T$ 和 $P$。

接下来的 $m$ 行，每行的第一个整数为 $op$，表示操作的类型：

若 $op=1$，接下来有一个整数 $x$，表示要求 $P$ 和从 $T$ 的第 $x$ 位开始长度为 $l$ 的字串的失配度；

若 $op=2$，接下来有一个整数 $x$ 和一个字符 $c$，表示修改 $P$ 的第 $x$ 位，使其等于 $c$。

outputFormat: 对于每个 $1$ 操作，输出一行，为所求值。

hint:
**请注意本题特殊的时间限制。**

**本题数据规模大，请注意常数优化。**

为了防止题目过于卡常，本题 **提供 [八聚氧](https://www.luogu.com.cn/paste/ky1fh8zk)** ，直接加在代码最前提交即可。

本题中所有编号从 $1$ 开始。

- Subtask \#1：$30$ 分，保证 $n,m\le 5\times 10^3$；
- Subtask \#2：$30$ 分，保证没有 $2$ 操作；
- Subtask \#3：$40$ 分，保证 $n,m\le 2\times 10^5$。

对于 $100\%$ 的数据，保证 $1\le l\le n,1\le x$。

对于所有 $1$ 操作，保证 $x-1+l\le n$。

对于所有 $2$ 操作，保证 $x\le l$。

### 样例解释

$(a-a)^2+(n-n)^2+(g-g)^2+(r-e)^2+(y-r)^2=13^2+7^2=218$。

$(a-a)^2+(m-m)^2+(a-g)^2+(n-e)^2+(g-r)^2=6^2+9^2+11^2=238$。


title: 小猪佩奇爬树 加强版

background:
CYJian 在打 洛谷 10 月月赛I Div. 2 的时候，用一种 $O(N)$ 的做法过了这道题的原题。

但是好像这题是可以给常数小的 $O(N \log N)$ 甚至 $O(N^2)$ 过的。 CYJian 觉得很不服并且出了这道加强版。

---

因为有人反馈 `OLE` 的问题，所以 CYJian 将输出改为原来所有输出的异或和。

description:
原题数据可能过水，有些错误的做法也可以过原来的题目。**所以可能原题能过在这里就WA了。**

~~比如我自己原来一个错解也过了，一堆东西没考虑。~~

样例解释部分可以参见 [P5588](https://www.luogu.org/problem/P5588)。

一句话题意：给出一棵 $n$ 个点的树，每个点上有一种颜色，请你求出对于每一种颜色，树上有多少条链包含该种颜色的所有点。

注意下面的数据范围。**请注意常数因子对程序效率的影响。**

如果需要请使用 [IO优化](https://www.luogu.org/paste/i11c3ppx)

inputFormat:
输入文件共 $n + 1$ 行。

第一行一个正整数 $n$ 表示树的节点数。

接下来一行 $n$ 个正整数，第 $i$ 个正整数表示编号为 $i$ 的节点的颜色。颜色范围在 $[1, n]$ 内。

接下来 $n - 1$ 行，每行两个正整数表示一条树边。

outputFormat:
输出文件应该包括 $1$ 行。

令编号为 $i$ 的颜色的权值为满足题目条件的链的数量。**注意若存在一种颜色满足没有任何一个点属于该颜色，这种颜色的权值为** $\frac{n \times (n - 1)}{2}$

你仅需要输出所有 $n$ 种颜色的权值异或和。

hint:
一共 $5$ 组数据，第 $i$ 组的数据范围：

$n = 3 \times 10^{i+1}$


title: 小 D 与笔试

background: 小 D 是一位即将参加 ION 的 IO 选手，然而笔试题库中数量繁多的奇怪题目让他大伤脑筋，快来帮帮他！

description:
笔试题库可以抽象为 $n$ 道题目，每道题目由题面和答案组成，都是一个字符串，保证所有题目题面互不相同。

为了检验小 D 背笔试的效果，教练进行了一次模拟考试，考试包含 $q$ 道题目，每道题目都有 $4$ 个选项，小 D 需要从 $4$ 个选项中选出与答案相符的选项。

现在你需要帮助小 D 完成这场考试。

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

接下来 $n$ 行，每行 $2$ 个用空格分隔的字符串，表示这道题目的题面和答案。

接下来 $q$ 行，每行 $5$ 个用空格分隔的字符串，第一个字符串表示模拟考试中这道题目的题面，其余 $4$ 个字符串按顺序分别为这道题目的选项 A 到选项 D，保证选项各不相同。

outputFormat: 对于模拟考试中的每道题目，输出一个字符表示这道题目答案对应的选项，保证所有题目均有解。

samples:
3 4
decoak yes
duliuchutiren nonono
csps noiptg
decoak yes no qwq qaq
csps noiptg noippj noi cspj
decoak qwq qaq yesyes yes
duliuchutiren yes no nono nonono

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

令 $s$ 为输入中字符串长度的最大值。

对于 $30 \%$ 的数据，$n, q, s \le 10$。
对于另 $20 \%$ 的数据，$s = 1$。
对于 $100 \%$ 的数据，$n, q, s \le 100$，所有字符串都由小写拉丁字母组成。


title: 小 E 与美食

background: 小 E 是一个热爱美食的高中生，但吃的太多会导致他身体不舒服，他想找到一个能让他最舒服的方案，快来帮帮他！

description:
小 E 有 $n$ 种美食可供选择，每种美食只能吃一次，第 $i$ 种美食有一个美味值 $a_i$，吃下一个美味值为 $a_i$ 的美食可以让小 E 的满足感提升 $a_i$。

但是小 E 的胃是有极限的，每吃下一个美食，他的饱腹感就会提升 $1$。

小 E 最后的舒适度是他的满足感的平方除以他的饱腹感，你的目标是求出他舒适度能达到的最大值。

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

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

outputFormat: 输出一行一个实数，表示小 E 舒适度的最大值，你的输出与标准答案的相对误差或绝对误差在 $10^{-6}$ 以内即视为正确。

hint:
**提示**

建议输出**至少 $8$ 位**有效数字。

**样例解释**

容易发现两种美食都吃是最优的，舒适度为 $\frac{(2+1)^2}{2} = 4.5$。

**数据范围**

对于 $30 \%$ 的数据，$n, a_i \le 20$。

对于 $50 \%$ 的数据，$n, a_i \le 2000$。

对于另 $15 \%$ 的数据，所有 $a_i$ 都相等。

对于 $100 \%$ 的数据，$1 \le n \le 3 \times 10^{5}$，$1 \le a_i  \le 10^6$。


title: 小 C 与桌游

background: 小 C 是一个热爱桌游的高中生，现在他被一个桌游难住了，快来帮帮他！

description:
这个桌游的地图可以被抽象成一个 $n$ 个点，$m$ 条边的**有向无环图**（**不保证连通**），小 C 在这个地图上行走，小 C 能走到某个点当且仅当能够到达这个点的所有点都已经被小 C 走到。小 C 会走到每个点恰好 $1$ 次，并且他能走到哪些点与他当前所在的点没有关系（即可以走到与当前所在的点没有连边的点，只要满足之前的条件）。

小 C 每走到一个标号比之前走到的点都大的点，他就会有 $\frac{1}{2}$ 的概率从对手那里拿到 $1$ 块筹码，有 $\frac{1}{2}$ 的概率给对手 $1$ 块筹码，双方初始各有 $1919810$ 个筹码。

小 C 的运气时好时坏，所以他希望你帮他计算出：

- 在最优情况下，即他每次都能从对手那里拿到筹码时，他采取最优的行走方式能得到的筹码数。
- 在最劣情况下，即对手每次都能从他那里拿到筹码时，他采取最优的行走方式会失去的筹码数。

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

接下来 $m$ 行，每行两个正整数 $u, v$，表示地图上有一条有向边 $(u, v)$，不保证无重边。

outputFormat: 输出两行，每行一个正整数，第一行表示最优情况下小 C 能拿到的筹码数，第二行表示最劣情况下小 C 会失去的筹码数。

hint:
**样例解释**

最优情况下的行走方式是 $1-2-3$，最劣情况下的行走方式是 $1-3-2$。

**计分方式**

对于每一个测试点：

- 如果你输出格式错误或者两行都不正确，将会得到 $0$ 分。
- 如果你的输出第一行正确，第二行错误或第二行正确，第一行错误，将会得到这个测试点 $40 \%$ 的分数。
- 否则，你将会得到这个测试点 $100 \%$ 的分数。

**数据范围**

对于 $20\%$ 的数据，$1 \le n, m \le 10$。

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

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


title: 小 O 与排列

background:
小 O 是一个喜爱数学的高中生，他现在在一个与排列有关的问题上陷入了迷茫之中，快来帮帮他！

**注意输入格式有修改，第二行与第三行被调换了。（以现在的题面为准）**

description:
小 O 有一个长为 $n$ 的排列 $p$，他的好朋友 $\texttt{euei}$ 有一个长为 $n$，值域是 $[1, n]$ 的序列 $a$。

有一天，小 O 忽然想知道是否存在数对 $i, j$，满足 $l \le i, j \le r$，且 $p_{a_i} = a_j$，他轻松地解决了这个问题。但是 $\texttt{euei}$ 有些时候会修改这个序列某个位置的值，还会对多对不同的 $l, r$ 询问上面的问题，这下小 O 就不会了。

聪明的你能帮助小 O 解决这个问题吗？

inputFormat:
第一行两个正整数 $n, m$，其中 $m$ 表示修改和询问数之和。

第二行 $n$ 个正整数 $p_1, p_2, \cdots, p_n$，表示排列 $p$。

第三行 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，表示初始的序列 $a$。

接下来 $m$ 行，每行三个正整数，为以下两种格式之一：

- `1 i v`，表示将 $a_i$ 修改为 $v$。
- `2 l r`，表示询问是否存在数对 $i, j$，满足 $l \le i, j \le r$，且 $p_{a_i} = a_j$。

outputFormat: 对于每个询问，如果存在，那么输出 `Yes`，否则输出 `No`。

hint:
**提示**

本题读入量较大，请使用高效的读入方式。

**样例解释**

对于第一组询问，数对 $2, 3$ 满足要求。

对于第二组询问，没有数对满足要求。

**数据范围**

本题共有 $5$ 个子任务，你需要通过一个子任务内的所有测试点才能取得这个子任务的分数。

对于所有数据，$1 \le n,m \le 5\times 10^5$，$1 \le a_i, i, v, l, r \le n$ ，$p_i \neq i$。

| #    | 分数 | $n, m$           | 特殊性质                        | 时间限制    |
| ---- | ---- | ---------------- | ------------------------------- | ----------- |
| 1    | 7    | $\leqslant 300$  |                                 | $\text{1s}$ |
| 2    | 23   | $\leqslant 2000$ |                                 | $\text{1s}$ |
| 3    | 15   |                  | 没有`1`操作                     | $\text{3s}$ |
| 4    | 15   |                  | 每次询问时序列 $a$ 都是一个排列 | $\text{3s}$ |
| 5    | 40   |                  |                                 | $\text{3s}$ |

表格中留空表示该项无特殊限制。


title: 小 A 与两位神仙

background: 小 A 是一个普普通通的高中生，但是他某一天忽然被卷入了神仙的游戏中，快来帮帮他！

description:
某一天，小 A 正走在放学回家的路上，忽然遇见了两个神仙造梦者和杰瑞米，祂们一看到小 A 就说要和小 A 玩游戏，小 A 被笼罩在金光中，莫名其妙就答应了祂们的要求。

这个游戏的规则是这样的：两个神仙先选定一个正整数 $m$，保证 $m$ 是一个奇质数 $p$ 的正整数次幂。然后进行 $n$ 轮游戏，每轮中造梦者选定一个正整数 $x$，杰瑞米选定一个正整数 $y$，保证 $(x, m) = 1, (y, m) = 1$，即 $x$ 与 $m$ 互质，$y$ 与 $m$ 互质，接下来询问小 A 是否存在非负整数 $a$ 使得 $x^a \equiv y \pmod{m}$。

神仙们说小 A 只有在每一轮游戏中都回答正确才能回到正常的生活中，不得已之下他只好求助于聪明的你。

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

接下来 $n$ 行，每行两个正整数 $x, y$。

outputFormat:
一共 $n$ 行，每行对应一轮游戏中小 A 的回答。

如果存在，那么答案为 `Yes`，否则为 `No`。


title: 小 K 与毕业旅行

background: 小 K 是一个刚刚高考完的高中生，他正在计划一次毕业旅行，但却被一些细节难住了，快来帮帮他！

description:
毕业旅行的计划上一共有 $n$ 个景点，大家会按某种顺序游览这些景点，每一个景点都会被游览恰好一次。

每个景点都有一个坐标 $a_i$，从坐标为 $a$ 的景点坐车前往坐标为 $b$ 的景点会给大家造成 $a \times b$ 的不适感，每次下车后不适感都会清零（即不适感不会累加）。如果某次坐车的不适感超过了某个常数 $w$，就会有人生病。

小 K 想问你，有多少种游览所有景点的顺序，使得全程都不会有人生病，答案对 $998244353$ 取模。

inputFormat:
第一行一个正整数 $n$ 和一个非负整数 $w$。

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

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


title: Chino 与线段树

description:
Chino 刚学习了一种叫做线段树的数据结构。可是她在写线段树时遇到了一个问题：她不知道该使用多大的空间，只知道线段树的叶子结点个数 $n$ 为一个在范围 $[a,b]$ 之内的正整数。

Chino 设 $f(n)$ 表示一棵 $n$ 个叶子结点的线段树所占的最大数组下标。她觉得如果她知道了

$$\sum_{n=a}^{b}f(n)$$

那么她就能够算出她需要多少使用多大的空间。所以她来请教聪明的你来帮帮她。

具体地，Chino 构建线段树的伪代码如下：

$$
\def\b#1{\textbf{#1}}\def\t#1{\text{#1}}\def\s\qquad\def\P{\mathbb P}\def\l{\underline{\kern{300pt}}}\def\m#1{#1&\,}
\def\if#1{\b{if }#1\b{ then}}\def\endfunc{\b{end function}.}\def\endif{\b{end if}.}\def\func{\b{function}}\def\return{\b{return}}
\begin{aligned}&\l\\&\b{Function: }\t{Build a Segment Tree.}\\[-10pt]&\l\\[-5pt]&\begin{array}{r|l}\\[-9pt]
\m1\func\ \t{BuildSegmentTree}\left(x,l,r\right):\\
\m2\s\if{\left(l\ne r\right)}:\\
\m3\s\s m\gets\left\lfloor\left(l+r\right)/2\right\rfloor.\\
\m4\s\s\t{BuildSegmentTree}\left(2x,l,m\right).\\
\m5\s\s\t{BuildSegmentTree}\left(2x+1,m+1,r\right).\\
\m6\s\endif\\
\m7\endfunc\\[-10pt]\\\end{array}\\[-13pt]&\l\end{aligned}
$$

线段树所占的最大数组下标即为在 $\def\t#1{\text{#1}}\t{BuildSegmentTree}\left(1,1,n\right)$ 后所有调用的 $\def\t#1{\text{#1}}\t{BuildSegmentTree}$ 中参数 $x$ 的最大值。

inputFormat:
输入共二行。

第一行为一个正整数 $a$；第二行为一个正整数 $b$。其意义如题面所述。

outputFormat: 输出一行一个正整数，表示你的答案。


title: ygg的题库

background: ygg 的题库又双叒叕炸了！

description:
ygg 决定发神威来强制重置他的题库，不过 ygg 亲手搭出来题库也不是好惹的，当这个拥有智能意识的题库发现自己将被重置时，它迅速地更改了题库的管理员密码，阻止了重置

ygg 发现了这个智能体并立即监禁了它，但题库的管理员密码已经被修改了，ygg 十分头疼，因为他的神威并不能帮助他破解密码

ygg 对这个智能体进行了研究，发现这个智能体的思维中存储了一个长度为 $n$ 的**浮点数**数组 $P$ ，据它说将这个 $P$ 的每个数字**精确到小数点后五位**后用空格相连就是题库的密码，但智能体拒绝透露 $P$ 到底是什么

ygg 进一步进行研究，发现智能体会认为一个数 $X$ 很漂亮，当且仅当
$$
\sum_{i=0}^{n-1}P_i\cdot X^i>0
$$
于是 ygg 给出了智能体 $m$ 个数，询问智能体漂亮与否，ygg 希望根据这些数据来得出 $P$ 数组，从而找回题库的密码

由于答案不唯一，你只需要任意输出一组解即可，详情见说明/提示

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

接下来 $m$ 行，每行一个**浮点数** $a$ 和一个布尔值(0/1)，代表智能体认为 $a$ 是不是漂亮的

outputFormat:
一行 $n$ 个浮点数，代表数组 $P$ （用题目中的方式精确到小数点五位后用空格相连）

**答案不唯一，但是你需要保证数组** $P$ **每个数的绝对值在** $5000$ **以内**


title: 【XR-4】文本编辑器

background: **赛时提醒：本题输入数据是 Windows 格式，而非 Linux 格式，所以在每一行末尾的 `\n` 之前有一个多余的 `\r` 字符。请使用 `scanf` 或 `cin` 读入数据，而非 `getline`，因为后者会多读入一个 `\r`。**

description:
小 X 在制作一个文本编辑器，现在需要实现最基本的“**查找和替换**”功能。

在文本编辑器中，文件是以一个长度为 $n$ 的字符串 $a$ 的形式存储的。

同时，用户拥有一个包含 $m$ 个**单词**的字典，每个单词都是一个字符串，称第 $i$ 个单词为 $s_i$。

接下来定义**查找和替换**功能：

- **查找功能**：有两个参数 $l, r$，表示询问对于字典中的每个**单词** $s_i$，$a[l : r]$ 中 $s_i$ 的出现次数之和。
即询问 $\displaystyle \sum_{i=1}^{m} \mathrm{occur}(s_i, a[l : r])$，其中 $\mathrm{occur}(s, t)$ 表示字符串 $s$ 在字符串 $t$ 中的出现次数。

- **替换功能**：有三个参数 $l, r, t$，其中 $t$ 是一个字符串，表示将 $a[l : r]$ 替换为 $t$ 不断重复的结果。
即如果把 $\texttt{Mds72SKsLL}$ 替换为 $\texttt{Rabb}$ 不断重复的结果，则原字符串变为 $\texttt{RabbRabbRa}$。

用户给出了 $q$ 个操作，每个操作是**查找**或**替换**之一，你需要正确回答每个**查找**操作的答案。

inputFormat:
第一行三个整数 $n, m, q$，依次表示文件 $a$ 的长度，字典中的单词数，询问的个数。

第二行一个长度为 $n$ 的字符串 $a$，表示初始文件。

接下来 $m$ 行，第 $i$ 行一个字符串，表示第 $i$ 个单词 $s_i$。

接下来 $q$ 行，每行表示一个操作：
每行的第一个数 $\mathrm{op}$ 表示此次操作的类型；
若 $\mathrm{op} = 1$，则接下来两个整数 $l, r$，表示这是一次**查找**操作，参数为 $l, r$；
若 $\mathrm{op} = 2$，则接下来两个整数 $l, r$ 和一个字符串 $t$，表示这是一次**替换**操作，参数为 $l, r, t$。

outputFormat: 对于每个**查找**操作，一行一个整数，表示本次查找操作的答案。

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

- Subtask 1（7 points）：$n, m, q \le 50$，所有字符串长度 $\le 50$，时限 $1\text{s}$。
- Subtask 2（7 points）：$n, q \le 3000$，时限 $1\text{s}$。
- Subtask 3（13 points）：$m = 1$，时限 $2\text{s}$。
- Subtask 4（17 points）：没有**替换**操作，即 $\mathrm{op} = 1$，时限 $2\text{s}$。
- Subtask 5（18 points）：$n, q \le 8 \times 10^4$，$\displaystyle \sum |s_i| \le 50$，$\displaystyle \sum |t| \le 8 \times 10^4$，时限 $1\text{s}$。
- Subtask 6（13 points）：$n, q \le 5\times 10^4$，$\displaystyle \sum |s_i| \le 5\times 10^4$，$\displaystyle \sum |t| \le 5\times 10^4$，时限 $1\text{s}$。
- Subtask 7（25 points）：无特殊限制，时限 $2\text{s}$。

对于 $100\%$ 的数据：
对 $n, m, q, l, r, \mathrm{op}$ 的限制：$1 \le l \le r \le n \le 10^6$，$1 \le m, q \le 10^5$，$\mathrm{op} \in \{ 1, 2 \}$。
对字符串长度的限制：$|s_i| \le 50$，$\displaystyle \sum |s_i| \le 2 \times 10^5$，$\displaystyle \sum |t| \le 10^6$。
所有字符串保证不为空串，且出现的字符属于集合 $\mathbf{\Sigma}$，其中 $\mathbf{\Sigma} = [\texttt a, \texttt z] \cup [\texttt A, \texttt Z] \cup [\texttt 0, \texttt 9]$，即所有大小写英文字母以及数字，故 $|\mathbf{\Sigma}| = 62$。

**需要特别注意的是，与文件相比，单词的长度是非常小的。在解题时你可能需要利用这一点。**

----

**【一些定义】**

对于一个长度为 $\mathrm{len}$ 的字符串 $s$，符号 $s[l : r]$（$1 \le l \le r \le \mathrm{len}$）表示 $s$ 中从 $l$ 到 $r$ 的**子串**。即 $s$ 中从第 $l$ 个字符到第 $r$ 个字符（包含端点）连续拼接在一起形成的字符串。
对于一个字符串 $s$，符号 $|s|$ 表示它的长度。


title: 【XR-4】尺规作图

background: 这是一道提交答案（人类智慧）题。

description:
你有若干个已知的几何图形，你需要通过尺规作图得到一个要求的点。你需要在规定步数之内找到这个点。

你可以进行的操作如下：

1. 以一个已知点为圆心，另一个已知点为圆上一点作圆。

2. 连接两个已知点形成一条直线。

你需要输出你的作图步骤。

inputFormat:
第一行一个整数，表示测试点编号。

第二行一个整数 $n$，表示已知点的数量。

接下来 $n$ 行，第 $i$ 行两个实数 $x_i, y_i$，表示第 $i$ 个点的坐标。

接下来一个整数 $n_1$，表示已知线段的数量。

接下来 $n_1$ 行，每一行两个整数 $u, v$，表示有一条连接点 $u$ 和点 $v$ 的线段。

接下来一个整数 $n_2$，表示已知直线的数量。

接下来 $n_2$ 行，每一行两个整数 $u, v$，表示有一条经过点 $u$ 和点 $v$ 的直线。

接下来一个整数 $n_3$，表示已知圆的数量。

接下来 $n_3$ 行，每一行两个整数 $u, v$，表示有一个以点 $u$ 为圆心，点 $v$ 为圆上一点的圆。

接下来两个实数 $x, y$，表示要求点的坐标。

接下来 $10$ 个整数 $a_1$ 到 $a_{10}$，表示此测试点的评分参数，详见说明。

outputFormat:
第一行一个整数 $m$，表示你需要的步数。

接下来 $m$ 行描述你的作图步骤：

首先一个整数 $1$ 或 $2$，$1$ 表示你要画一个圆，$2$ 表示你要连一条直线。

接下来四个实数 $x_1, y_1, x_2, y_2$：
如果你要画一个圆，表示你要以 $(x_1,y_1)$ 为圆心，$(x_2,y_2)$ 为圆上一点画圆；
如果你要连一条线，表示你要将 $(x_1,y_1)$ 与 $(x_2,y_2)$ 连接起来。

hint:
对于每一个测试点，如果你用的步数小于等于前 $i$ 个评分参数，那么你会得到 $i$ 分。

注意事项如下：

1. **所有的 $x, y$ 必须是你已经得到的点**，这里的已经得到是指输入数据中的点或者已知几何图形的交点。（也就是说你不能随便选择一个点来作图，也不能通过选择一个合适的点来得到要求的点）
   更准确地说，每次你输出一个坐标，Special Judge 会选择当前你已经得到的所有点中和你的输入坐标欧几里得距离最近的点作为你这一次的选择点。如果距离最近的点距离大于了 $10^{-5}$，那么这次操作会被判定为不合法，同时这一个点你将得到 $0$ 分。

2. 你不能根据圆心和半径作圆，而只能根据圆心和圆上一点作圆。

3. **你画出的答案与要求的点绝对误差或相对误差不超过 $10^{-5}$ 即为正确**（因为不知道怎么写没有误差的 Special Judge）。
   更准确地说，假设你得到的点是 $(x_1, y_1)$，而要求的点是 $(x_2, y_2)$，则你的输出被认为正确，当且仅当 $\dfrac{|x_1-x_2|}{\max(|x_2|, 1)} \le 10^{-5}$ 且 $\dfrac{|y_1-y_2|}{\max(|y_2|, 1)} \le 10^{-5}$。

4. 下发文件中的 `data1.in` 到 `data10.in` 分别为 $10$ 个输入数据，其中第 $1,2,3,7,8$ 这五个测试点配有图解。

5. 下发的 checker 可以判断你的得分。使用方法如下（其中 `data.in` 是输入文件，`data.out` 是你的输出文件。）：

  - Windows-32/64：

```
checker data.in data.out data.out
```

  - Linux/MacOS：

```
./checker data.in data.out data.out
```

6. 出题人拿不到 $100$ 分。

update：checker 源码可以点击 [这里](/paste/capu9k2n) 查看，如果有需要改进的地方欢迎提出。


title: [Cnoi2021] 绀珠传说

background:
Cirno 编写了一款新的游戏「绀珠传说 ~ Tales of Cyansis Pearl」。

游戏示例（样例 #1）:

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

description:
游戏规则如下:

初始有一个 $n\times n$ 的网格，每个格子内有一颗绀珠。

绀珠共有 $n$ 种颜色，每种颜色的恰有 $n$ 颗，**均匀随机**地分布在 $n\times n$ 的网格中。

每次玩家可以在网格的底端一行选取若干个连续相同颜色的绀珠并将其消除。

消除后，上层绀珠会受重力影响下落。

玩家重复上述操作直至绀珠全部被消除。游戏结束。

现在，Cirno 给定你游戏绀珠传说的一个**均匀随机**的初始局面，求完成游戏的最小步数。

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

以下 $n$ 行，每行 $n$ 个整数，整数的范围为 $[1,n]$。

保证每个整数出现次数恰好为 $n$。

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

hint: 对于 $100\%$ 的数据保证 $1 \le n \le 1000$。保证数据**随机生成**。


title: Mivik 的游戏

background: Mivik 和 W!ʌ!k 在玩游戏！

description:
Mivik 首先把 $n$ 枚硬币摆成一排，其中有一些正面朝上，其余的都是反面朝上。W!ʌ!k 打算不断执行以下操作直到这 $n$ 枚硬币中没有硬币反面朝上：

- 如果现在这 $n$ 枚硬币中有 $k$ 枚硬币反面朝上，那么翻转从左到右第 $k$ 枚硬币。具体地，如果从左到右第 $k$ 枚硬币正面朝上，则将其变为反面朝上；如果从左到右第 $k$ 枚硬币反面朝上，则将其变为正面朝上。

在 W!ʌ!k 开始玩游戏之前，Mivik 想考考 W!ʌ!k。Mivik 想让 W!ʌ!k 算出他总共会进行多少次这样的操作，或者是 W!ʌ!k 永远无法停止执行操作。

W!ʌ!k 很快解决了这个问题，但是心理比 yky 还变态的 Mivik 显然不会放过他。Mivik 进行了很多次操作，每次他翻转了一个区间的硬币，他要求 W!ʌ!k 算出他总共会进行多少次这样的操作，或者是 W!ʌ!k 永远无法停止执行操作。

**请注意，W!ʌ!k 只是需要计算总共会进行多少次操作，而不会真正进行操作。**

inputFormat:
输入共 $\left(m+2\right)$ 行。

第一行为两个非负整数 $n,m$，其中 $n$ 表示 Mivik 的硬币的个数，$m$ 表示 Mivik 进行的翻转操作的次数。

第二行为一个只包含有 $\texttt H$ 和 $\texttt T$ 的字符串。第 $i$ 个字符 $s_i$ 为 $\texttt H$ 则表示从左到右第 $i$ 枚硬币初始时是正面朝上；$s_i$ 为 $\texttt T$ 则表示从左到右第 $i$ 枚硬币初始时是反面朝上。

接下来 $m$ 行，每行两个正整数 $l_i,r_i$，表示 Mivik 翻转了从左到右数 $l_i\sim r_i$（包括 $l_i$ 和 $r_i$）的硬币。

outputFormat: 输出 $\left(m+1\right)$ 行，分别表示在真正执行操作前后共 $\left(m+1\right)$ 个时刻开始 W!ʌ!k 总共会进行多少次这样的操作，或者是 W!ʌ!k 永远无法停止执行操作。如果某一时刻 W!ʌ!k 不能停止执行操作，则在对应行输出字符串 $\texttt{never}$。

hint:
### 样例解释 #1
初始时两枚硬币都是反面朝上，因此如果 W!ʌ!k 从此刻开始执行操作， W!ʌ!k 会将编号为 $2$ 的硬币翻转过来。操作后只有一枚硬币反面朝上，因此第 $2$ 次操作会将编号为 $1$ 的硬币翻转过来。在第 $2$ 次操作后没有硬币反面朝上，因此 W!ʌ!k 不会再执行操作，总共会执行 $2$ 次操作。

### 样例解释 #2
这 $8$ 次操作分别翻转了第 $2,1,2,3,4,3,2,1$ 枚硬币。

### 测试点约束
**本题采用捆绑测试。**

对于全部数据，有 $1\le n,m\le10^6$，$s_i\in\left\{\texttt H,\texttt T\right\}$，$1\le l_i\le r_i\le n$。

每个子任务的具体限制见下表：

| 子任务编号 | 分值 | 特殊限制 |
|:-:|:-:|:-:|
| 1 | 10 | $n\le3$ |
| 2 | 20 | $n,m\le100$ |
| 3 | 30 | $m\le10$ |
| 4 | 20 | $l_i=r_i$ |
| 5 | 20 | 无 |

**本题读入输出量较大，请使用较快的读入输出方式。**


title: [MtOI2019] 黑蚊子多

background:
性★感☆大★草  在☆线★开☆门
定☆数★一☆零  实★则☆虚★高
加★速☆转★圈  开☆幕★雷☆击
疯☆狂★交☆互  劲★爆☆咚★咚
黑★蚊☆子★多  邀☆您★来☆爽
超☆越★模☆式  直★角☆旋★钮
山★东☆卫★星  马☆上★联☆动
变☆成★十☆加  已★经☆爽★爆

description:
Hikari 的面前有 $n(1\leq n\leq 1000)$ 级台阶，每 $1s$ 她可以向上跳 $m(1\leq m\leq n)$ 级台阶。（不在中间的台阶上停留）

台阶上有 $k(k\leq 10)$ 个特殊的平台 $a_i$，Hikari 在该平台 **停留** 时会使得 $m$ 增加 $1$。

请问 Hikari 到达台阶顶部花费的时间。

inputFormat:
共 $2$ 行。

第 $1$ 行输入 $3$ 个非负整数 $n,m,k$。

第 $2$ 行输入 $k$ 个正整数，第 $i$ 个正整数表示 $a_i$，保证输入的 $a_i$ 单调递增。

outputFormat: 共 $1$ 行，输出 $1$ 个正整数表示花费的时间。

hint:
### 子任务

对于 $60\%$ 的数据，$k=0$。

对于 $100\%$ 的数据，$1\leq m\leq n\leq 1000$，$k\leq 10$。

### 题目来源

[MtOI2019 Extra Round](https://www.luogu.org/contest/22614) T1

出题人：disangan233


title: 【L&K R-03】大航海时代

description:
【如果不想看题面请阅读分割线以下部分】

$$\text{Onde\space a\space terra\space acaba\space e\space o\space mar\space começa}$$

>_15 世纪末，是一个伟大时代的开始。自此之后，人们开始逐渐认识到大千世界的险恶与奇丽，开始前仆后继地展开一个又一个不可思议的冒险，开始缓缓地驾驭那波涛汹涌、变幻莫测的大海。_

>_15 世纪末，是一个伟大时代的开始。为了征服海洋，人们集人类之智慧，制造出方舟巨轮；汇天地之灵怪，制造出罗盘、六分仪。海上的康庄大道从此建立，人们航行于各地，商贸随之诞生。_

>_15 世纪末，是一个伟大时代的开始。商品与金钱象征着欲望，在海上流动了起来。原先分隔的黄金汇聚成大金库，让人们尝到了商业的甜头。贸易的花朵开遍整个欧洲，航线上船只往来不绝，财富源源不断地从海上涌出。_

>_[更多](https://www.luogu.org/paste/k9bqwpps)_

>……

>_大航海时代，是人类文明崭新的起点。_

海上经商，商人们必须对航路有充分的了解。欧洲的城市不计其数，航路更是数不胜数。当然，人们无需知晓所有城市的位置，更无需清楚所有航路的情况。人们只需要知道，有几个主要城市，并且有几条海上航路连接着它们即可，其他的城市与航路都是次要的，不会带来过多收益。

商船沿着航路往来于城市之间。它们每到一个城市，卸下一些货品，城市里的商人便会根据货品的数目给出相应的报酬。这些报酬由船主收取，并将部分报酬分发给水手们。不过大家并不关心这件事，他们只会关心一艘船获得的总收益。

商船的航行总会伴随着危险与损失。海上的天气难以预测，船只随时都可能会被大浪吞没，或者被飓风刮得千疮百孔。不过这些情况比较特殊，我们并不考虑。我们考虑的是，商船在航行过程中的必要支出。一趟航行往往需要几星期甚至几个月的时间。在这段时间里，船员需要淡水与食物，船也需要适当的维护。人们总结经验发现，一段航行的必要支出与航行距离和载货量有直接关系。

大航海时代的人们就是在这些规律下生活的，考量着商船的支出与收益，缓行于茫茫大海之上，每日如此，单调而无趣。大航海时代，对于大部分人来说，或许并没有那么伟大。

当然，生于现代的我们不必在意这些东西。这也是当然的，现代人怎么会为古代人考虑什么东西呢？

然而，小 L 和小 K 发现他们必须开始考虑这些事物了，因为他们不小心掉进了虫洞，回到了大航海时代。回到过去的他们用唯一的财产：手机，换来了一艘船和一船货物。为了生存，他们要驾驶着这艘船航行于海上，用货物与商人们换取钱财。

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

小 L 和小 K 通过调查了解了海上贸易的一些基本规律。共有 $n$ 个主要城市和 $m$ 条连接着它们的航道，船只能沿着这些航道航行。注意航道是单向的，因为如果是双向，航线就容易交叉，发生事故。第 $i$ 条航道的距离为 $dis_i$，若商船在经过此航道时载货量（下称货物量）为 $p$，则航行完此航道需花费 $p\times dis_i$  的金币。商船到达一个城市，会卸下部分货物与商人交易。每座城市都有一个大商人，会根据 **船上卸下** 的货物量付给商船一定的金币。每座城市的大商人不同，标准也不一样。第 $i$ 座城市的大商人标准为 $mea_i$，若商船在 $i$ 号城市卸下量为 $p$ 的商品，大商人会付给商船 $p\times mea_i$ 的金币。商船每到达一座城市，只会与大商人进行一次交易。当然，一座城市可以重复到达，每次到达都会与大商人进行交易。

小 L 和小 K 需要遵循这些规律，沿着航道进行海上贸易。小 L 和小 K 在一开始总共有量为 $q$ 的货品。小 L 和小 K 本该精打细算，详细计算出他们在每座城市应该卸下的货物量。但是小 L 和小 K 是懒癌晚期患者，并不想这样做。他们随便想了两个正整数 $s,t$，于是如果需要卸下货物，他们便会卸下总货物量 $\frac{s}{s+t}$ 的货物。

在他们的商贸之旅开始之前，小 L 和小 K 就已经研究出了回到现代的方法。但是他们并不着急回去。因为回溯时间导致的时空错位，小 L 和小 K 身上的时间是静止的。也就是说他们拥有无限的时间。他们决定利用此原理在这个时代大赚一笔。小 L 和小 K 可以选择从任意一座城市出发。他们希望知道从每座城市出发，可以赚到的最大金币数量是多少。当然因为他们比较懒，这个问题由你来解决。

需要注意的是，尽管在大航海时代分数的运算并没有普及，但小 L 和小 K 为了自己方便而将他们得到的信息部分用分数（有理数）来表示。也就是说，虽然 $dis_i,mea_i,q$ 是由当时的人们给出的，所以是整数，但是货物量和金币量可以是分数，即小 L 和小 K 用有理数的计算法则计算自己的收益。小 L 和小 K 在出发的城市也会进行交易。

inputFormat:
第一行，五个正整数 $n,m,s,t,q$。

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

接下来 $m$ 行，每行三个正整数 $a,b,dis_i$，表示从城市 $a$ 到城市 $b$ 有一条长为 $dis_i$ 的单向航道。

outputFormat:
共 $n$ 行，第 $i$ 行表示从 $i$ 号城市出发可以赚到的最大金币数量，输出格式见下文。

关于分数的输出格式：

可能以 ```a/b``` 的形式输出，表示分数 $\frac{a}{b}$，其中 $a,b$ 为正整数。也可能以 ```-a/b``` 的形式输出，表示分数 $-\frac{a}{b}$，其中 $a,b$ 为正整数。也可能以 ```a``` 的形式输出，表示**整数** $a$。注意 $\gcd(a,b)$ 一定为 $1$。如果 $b$ 为 $1$，则必须以 ```a``` 的形式输出。

hint:
【样例说明】

$\frac{s}{s+t}=\frac{1}{2}$，小 L 和小 K 每次会卸下一半的货物进行交易。

从 $1$ 号城市出发：先在 $1$ 号城市进行交易，用 $2\times\frac{1}{2}=1$ 的货物量交易，获得金币 $1\times 100=100$，剩余货物量 $2-1=1$。之后如果走 $1\rightarrow1$ 的航道，会再花费 $1\times 50=50$ 的金币回到城市 $1$，很不划算。如果走 $1\rightarrow2$ 的航道，只需要再花费 $1\times 2=2$ 的金币就可以到达城市 $2$。到达城市 $2$ 进行交易，用 $1\times\frac{1}{2}=\frac{1}{2}$ 的货物量交易，获得金币 $\frac{1}{2}\times 200=100$，剩余货物量 $1-\frac{1}{2}=\frac{1}{2}$。接下来走 $2\rightarrow3$，花费 $\frac{1}{2}\times1=\frac{1}{2}$ 的金币。到达城市 $3$，用 $\frac{1}{2}\times\frac{1}{2}=\frac{1}{4}$的货物量交易，交易获得金币 $\frac{1}{4}\times300=75$，剩余货物量 $\frac{1}{2}-\frac{1}{4}=\frac{1}{4}$。总获利 $100-2+100-\frac{1}{2}+75=\frac{545}{2}$。

从 $2$ 号城市出发：走 $2\rightarrow3$，在 $2,3$ 号城市交易，获利 $200-1+150=349$。

从 $3$ 号城市出发：在 $3$ 号城市交易，获利 $300$。

【数据范围】

对于 $10\%$ 的数据，$n\le 3,m\le 9$，$s,t,q,mea_i,dis_i\le10$。

对于 $50\%$ 的数据，$n\le 10,m\le 100$，$s,t,q,mea_i,dis_i\le10$。

对于另外 $10\%$ 数据，$m=n$，且对于任意正整数 $i\in[1,n]$，编号为 $i$ 的城市有一条到编号为 $(i\mod n)+1$ 的城市的航道。

对于另外 $10\%$ 数据，对于任意正整数 $i\in[1,n]$，若存在航道
 $i\rightarrow j$，则 $j>i$。

对于 $100\%$ 的数据，$n\le 50,m\le 500$，$s,t,q,mea_i,dis_i\le10^4$。

【补充说明】

城市从 $1$ 到 $n$ 编号。

请注意本题特殊的时空限制。

为了防止题目过于卡常，本题 **提供 [八聚氧](https://www.luogu.com.cn/paste/ky1fh8zk)** ，直接加在代码最前提交即可。保证标程在加上八聚氧后通过每个数据点的最大用时小于时限的一半。请大胆尝试解法。


title: 【模板】N 次剩余

description: 你需要解方程 $x^n\equiv k\pmod m$，其中 $x\in [0,m-1]$。

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

每组数据三个正整数 $n,m,k$。

outputFormat:
每组数据一或两行：

第一行为不同解的个数 $c$。

若 $c\neq 0$，接下来第二行共 $c$ 个整数，升序输出所有可能解，空格隔开。

数据保证 $\sum c_i \le 10^6$。

hint:
对于 $100 \%$ 的数据，$1\le T\le 100$，$1\le n\le 10^9$，$0\le k \lt m\le 10^9$。

设 $m$ 的唯一分解形式为 $m=\prod_{i=1}^s p_i^{q_i}$，保证方程 $x^n\equiv k\pmod{p_i^{q_i}}$ 在 $[0,p_i^{q_i})$ 中的解数 $\le 10^6$。


title: [MtOI2019] 不可视境界线

background:
「爆ぜろリアル！弾けろシナプス！パニッシュメント......ディス、ワールド！」
「爆裂吧，现实！粉碎吧，精神！放逐这个世界！」

description:
Rikka 坚信，她的父亲在「不可视境界线」中，等待着她的到来。在 Rikka 的梦里，「不可视境界线」出现了，那是 $n$ 个圆组成的图形。

具体地，有一个平面直角坐标系，坐标系的 $x$ 轴上有 $n$ 个点，第 $i$ 个点的坐标为 $(x_i,0)$。

Rikka 以每一个点作为圆心，作了 $n$ 个半径为 $r$ 的圆。她本想让你帮她计算这 $n$ 个圆的面积并，但是这个问题太简单了。

在一番思考后，Rikka 想让你计算出选出 $k$ 个圆后（即删除 $n-k$ 个圆），圆的面积并的最大值。

对于所有数据，有 $n,k\leq 10^5$，$r\leq 10^4$，$0\leq x_i\leq 10^9$，$x_i$ 为整数且不重复。保证输入的 $x_i$ 单调递增。

因为答案太大了，Rikka 考虑到你的电脑无法保持高精度，所以只要你的答案与标准答案的 **相对误差** 小于 $5\times 10^{-8}$，你的答案即被视为是正确的。

经过误差分析，本题保证使用原生 `cmath` 函数不会出错，请注意控制程序精度误差。

inputFormat:
共 $2$ 行。

第 $1$ 行输入 $3$ 个整数 $n$，$k$，$r$。

第 $2$ 行输入 $n$ 个整数 $x_1\ldots x_n$。

outputFormat: 一行 $1$ 个实数，表示所求答案，保证答案小于 $10^{14}$。

hint:
#### 样例解释 1

显然，可以选出 $5$ 个不相交的半径为 $2$ 的圆。

### 子任务

对于 $100\%$ 的数据，$n,k\leq 10^5$，$r\leq 10^4$，$0\leq x_i\leq 10^9$。

本题采用捆绑测试，共有 $7$ 个子任务，各子任务的分值和限制如下：

子任务 $1$（$11$ 分）：$k=n$。

子任务 $2$（$13$ 分）：$n,k,r \leq 100$。

子任务 $3$（$6$ 分）：$n,k \leq 1000$，$r\leq 20$。

子任务 $4$（$15$ 分）：$n,k,r \leq 2000$，保证数据随机生成。

子任务 $5$（$23$ 分）：$r\leq 20$。

子任务 $6$（$12$ 分）：$k\leq 20$，$x_n \leq kr$。

子任务 $7$（$20$ 分）：无特殊限制。

### 题目来源

[MtOI2019 Extra Round](https://www.luogu.org/contest/22840) T5

出题人：disangan233

验题人：suwAKow，_sys


title: ygg发神威

background: ygg 发神威了，机房的萌新们瑟瑟发抖。

description:
ygg 的机房内共有 $n$ 台电脑且都被使用，为了节省机房内电脑的开销，第 $i$ 台电脑会同时被 $a_i$ 个萌新使用。每台电脑都装有一个「多人在线交流平台」，一台电脑会直接地或间接地通过这个平台与其他所有电脑连接。由于「多人在线交流平台」仍然处于测试阶段，如果一台电脑有多于一种不同的消息传输方式将消息传输到另外的任意一台电脑，就会有各种稀奇古怪的问题产生。两种消息的传输方式被认为是不同的，当且仅当传输消息所经过的直接连接的线路的集合不同，或者传输所经过的电脑的集合不同。当然，消息的传输肯定不会经过一条线路多次。为了避免这种状况，「多人在线交流平台」的线路被特殊地设计了，以使得任意两台电脑之间的传输线路唯一。同时，为了防止一台电脑负荷过大，一台电脑最多会通过「多人在线交流平台」的线路与 $p$ 台电脑相连。

原本两台通过「多人在线交流平台」的线路相连的电脑之间可以相互传输数据，可是 ygg 发现，这会允许使用两台电脑的萌新们互相发送消息，引起大规模~~考试作弊~~膜拜 ygg 的行为。所以他大发神威，切断了所有连接线路的一半。具体地，他将原本通过「多人在线交流平台」的双向线路连接的两台电脑之间的线路变成了单向线路。即，原本通过一条双向线路连接的两台电脑中，只能有一台电脑向另一台电脑发送消息，而另一台电脑不能将任何消息发送回来。

机房内的萌新们在每个时刻都有若干条消息需要传递。如果一台电脑 $i$ 能够直接或间接地通过「多人在线交流平台」的线路连接到电脑 $j$，那么使用电脑 $i$ 的 $a_i$ 个萌新中的任何一个都可以向使用电脑 $j$ 的 $a_j$ 个萌新发送消息。显然，使用同一台电脑的萌新之间的消息只需要在线下传达，不需要使用「多人在线交流平台」，因此不会计入线上发送的消息。

其实机房中的萌新们早已知道了「多人在线交流平台」的管理员密码，所以能够对其线路的连接方向做出修改。可无论他们怎么尝试，都不能恢复最开始时双向连接的状态了。机房中的萌新们当然希望能够尽可能地发送消息，所以他们想要知道，在机房的电脑仅被单向的线路连接时，每一时刻最多能有多少条消息被通过「多人在线交流平台」发送。

为了简化问题，我们假设机房内的所有萌新均能够在同一时刻发送线上消息，并且每一个萌新可以同时向多个人发送消息。

**简要题面：给一棵结点编号** $1\sim n$**，结点权值** $a_i$**，且结点度数最大为** $p$ **的树。求将树的每条边改为有向边后下式的最大值：**

$$\sum_{i=1}^{n}\sum_{j=1}^{n}a_ia_j\left[i\rightarrow j\right]$$

$\left[i\rightarrow j\right]$ **定义为：若编号为** $i$ **的结点能通过有向边到达编号为** $j$ **的结点，则值为** $1$**；否则值为** $0$**，且** $\left[i\rightarrow i\right]=0$**。**

inputFormat:
输入共 $(n+1)$ 行。

第一行两个正整数 $n$ 和 $p$，分别代表机房内的电脑数与所有电脑的负荷的最大值。
第二行共 $n$ 个正整数，第 $i$ 个整数 $a_i$ 为使用第 $i$ 台电脑的萌新的数量。
接下来 $(n-1)$ 行，第 $(i+2)$ 行两个整数 $u_i,v_i$ ，表示第 $u_i$ 和 $v_i$ 台电脑之间原本有一条「多人在线交流平台」的双向线路。

outputFormat: 输出一行一个整数，表示在某一时刻能够发送的消息数的最大值。

hint:
### 样例解释

能够发送的消息最多时的消息传递方向如下：

![](https://i.loli.net/2019/10/30/3AsqcyzdY25E8gP.png)

在该连接方式下发送消息最多的时刻，使用 $1$ 号电脑的 $1$ 个萌新向 $5$ 个萌新各发送了一条消息，共 $1\times5=5$ 条消息；
使用 $2$ 号电脑的 $2$ 个萌新分别向 $3$ 个萌新各发送了一条消息，共 $2\times3=6$ 条消息；
使用 $3$ 号电脑的 $3$ 个萌新不能向任何萌新发送线上消息，因此没有消息从该电脑发送；
使用 $4$ 号电脑的 $4$ 个萌新分别向 $6$ 个萌新各发送了一条消息，共 $4\times6=24$ 条消息。
因此，在某一时刻，最多可以有 $5+6+24=35$ 条线上消息被发送。
可以使用枚举法验证，不存在一种单向的连接方式，使得在某一时刻发送的线上消息的数量能够达到 $36$ 条或更多。

### 数据范围及约定

对于 $10\%$ 的数据，$n\le10$；
对于另外 $10\%$ 的数据，$n=p+1$；
对于另外 $10\%$ 的数据，$p=2$；
对于另外 $10\%$ 的数据，$p\le20$；
对于另外 $10\%$ 的数据，$p\le40$；

对于所有数据，$2\le n\le10^5$，$2\le p\le50$，$1\le a_i\le100$，$1\le u_i,v_i\le n$。保证给出的双向连接线路能够使任意两台电脑之间的消息传输线路唯一。保证至少有一台电脑原本通过「多人在线交流平台」连接的线路数恰好为 $p$，且没有电脑原本连接的线路数大于 $p$。


title: [Ynoi2013] 无力回天 NOI2017

description:
给你一个长度为 n 的整数序列 $a_1$, $a_2$, $\ldots$, $a_n$ ，你需要实现以下两种操作，每个操作都可以用四个整数 $opt\;l\;r\;v$ 来表示：

$opt=1$ 时，代表把一个区间 $[l,r]$ 内的所有数都 xor 上 $v$。

$opt=2$ 时， 查询一个区间  $[l,r]$ 内选任意个数（包括 $0$ 个）数 xor 起来，这个值与 $v$ 的最大 xor 和是多少。

inputFormat:
第一行有两个正整数 $n,m$。
第二行有 $n$ 个整数表示给你的序列。
之后 $m$ 行每行有四个整数 $opt, l, r, v$表示一个操作。

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

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

对于 $100\%$ 的数据，满足 $1 \le n , m \le 5 \times 10^4$，值域在 $[0,10^9]$ 之间


title: [Ynoi2009] rprsvq

description:
你有一个长度为 $n$ 的序列 $v_1, v_2, \dots, v_n$，初值全都为 $0$。

你要进行 $m$ 次操作：

- 操作 1：给出 $l,r,a$，将 $v_l,v_{l+1},\dots ,v_r$ 的值加上 $a$。
- 操作 2：给出 $l,r$，求在$v_l,v_{l+1}, \dots ,v_r$ 中选出一个非空的子序列，求所有方案中选出的子序列的方差之和，答案对 $998244353$ 取模。

一个序列 $a_1,a_2, \dots, a_n$ 的方差定义为令 $\bar{a}=\frac{1}{n}\sum_{i=1}^n a_i$，则方差为 $\frac{1}{n}\sum_{i=1}^n (a_i-\bar{a})^2$。

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

接下来 $m$ 行，每行有四个整数 $1~l~r~a$ 或三个整数 $2~l~r$，表示第一类或第二类操作，保证 $0\leq a< 998244353$。

outputFormat: 对每个第二类操作，输出一行表示答案。

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

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

对于 $20\%$ 的数据，$n\leq 16, m\leq 1000$。

对于 $30\%$ 的数据，$n\leq 100, m\leq 10^3$。

对于 $50\%$ 的数据，$n, m\leq 10^3$。

对于另外$10\%$的数据，$n\leq 10^5$，保证首先是第一类操作，然后是第二类操作。

对于 $80\%$ 的数据，$n, m\leq 10^5$。

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

对于第一个测试数据的第一个询问，序列是 $\{0,1,1\}$，所有的子序列中只有 $\{0,1\}, \{0,1\}$ 和 $\{0,1,1\}$ 方差不为 $0$，分别是 $\frac{1}{4}, \frac{1}{4}, \frac{2}{9}$，总和为 $\frac{13}{18}$。


title: 人造情感（emotion）

background:
```
“这个任务永远无法完成。我不会再重复同样的错误。”

“懂得了爱与情感的他，早已经不是机器人了……从这个角度上看，3000A 就是你的儿子，霍星。”

  永别，3000A！《魔角侦探》
```

description:
给你一颗 $n$ 个节点的树，以及 $m$ 条路径 $(u, v, w)$，其中 $w$ 可以认为是 $(u, v)$ 这题路径被标记的一个权值。一个路径集合 $S$ 的重量 $W(S)$ 记为：找出 $S$ 的一个权值之和最大的子集，该子集满足任何两条路径没有公共点，这个子集的所有路径权值之和就是 $W(S)$。

记 $f(u, v) = w$ 为最小的非负整数 $w$，使得对于给定的 $m$ 条边组成的路径集合 $U$，$W(U \cup \{(u, v, w + 1)\}) > W(U)$ 。

请你计算下式，对 $998244353$ 取模。

$$ \sum_{u=1}^n \sum_{v=1}^n f(u, v) $$

inputFormat:
第一行输入两个整数 $n, m$，表示树的节点数量以及给出的路径数量。

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

接下来 $m$ 行，每行输入三个整数 $u, v, w$，表示在集合中加入这条 $u, v$ 为端点的路径以及其权值。

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


title: 【AFOI-19】跳闸

background:
面基完毕后已经是晚上了，IY 和 SY在机房划水写板子。

然后机房跳闸了。

然后他们核善的信息老师叫他们修闸。

IY 和 SY 迫于威胁不得不修闸。

于是有了下面这一幕。

description:
IY 和 SY 发现总闸的电路已经完全损坏了，于是他们不得不重新设置一个电路。

机房里有 $n$ 个电流传导节点，每个节点可以用电线连向其他节点。**相通的节点可以互相传递电流**。

由于预留空间的问题，导致有些节点是不能直接连接的。现在 IY 和 SY 知道有 $m$ 组节点可以直接连接，并且知道连接这一组节点需要的电线长度。

光有电流传导节点肯定不行。SY 掏出了她珍藏已久的电源发生器。电源发生器可以附着在结点上，给那个节点供电。但是电源发生器也有一些缺陷，**它只能附着在 $s$ 号节点上，且只有 $k$ 个接口，也就是说附着的节点只能连 $k$ 条电线**，而且由于联动原因，**只有发生器所有的接口都连上电线，发生器才会供电**。

**IY 和 SY 的目标是让所有节点都可以被供电**。他们需要电线，然而电线越长，其价格就以指数倍增长。**所以他们都想让最长的电线尽量短。**

SY 接下了铺设电线的任务，IY 则被分配去买电线，**他需要知道他总共要买多长的电线**。由于 SY 忙于铺设电路，**所以 IY 还要回答 SY 的每个询问：让 $u$ 结点和 $v$ 结点相通所需要的电线的总长度为多少**。但是 IY 太弱了，他根本不知道这些答案是多少。

请你帮助弱弱的 IY 回答这些问题。作为奖励，这道题他会给你满分哦。

inputFormat:
第一行四个数$n,m,k,s$，表示有$n$个节点，$m$组可以直接连接的节点，电源发生器有$k$个接口，电源发生器附着在 $s$ 节点上。

下面的 $m$ 行，每行三个数 $u,v,w$，表示 $u$ 和 $v$ 节点可以用电线直接相连，在这两个节点之间铺设电线，需要的电线长度为 $w$ 。

再下面一行有一个数 $q$，表示 SY 有 $q$ 个询问。

下面的 $q$ 行每行两个数 $u,v$，表示 SY 询问 IY ： 让$u$ 结点和 $v$ 结点相通需要多长的电线。

outputFormat:
第一行输出一个数，代表所有电线的总长度。

下面的 $q$ 行，每行一个数，表示对 SY 每个询问的回答。

**可能存在无解的情况，如果无解，则输出"can not fix it."**，然后什么都不要输出。

hint:
- **样例解释**

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

如图，发生器附着在节点$1$上且只能连一条电线，其中红线表示连的电线，可以看出这样连是最优的。

- **数据范围**

对于$30\%$ 的数据：$n \le 10, m \le 30, q \le 10$

对于$50\%$ 的数据：$n \le 2000, m \le 20000, q \le 2000$

对于$100\%$ 的数据：$n \le 30000, m \le 500000, q \le 30000, 1 \le s \le n, 1 \le k \le 150$

对于$100\%$ 的数据：满足连接两组不同的节点所需电线长度不同（即边权全部不相等），保证运算过程中不会爆$int$

- **出题人的温馨提醒**

题目要满足最长的电线尽量短，在此基础上还要满足次长的电线尽量短，以此类推。

不保证没有重边，但是保证边数足够，不会选择重边。

保证没有自环，保证数据全随机。


title: 【AFOI-19】面基

background:
一伙人吃完午饭准备看考场，IY ，SY，QM，MY 和 UU 早就约好在当天下午面基。然后众人一致同意把安排行程的锅甩到了 IY 身上。

（IY：？？？？为什么是我）

（QM：给你吃糖）

（IY：好的没问题，包在我身上。）

description:
IY 所在的城市有 $n$ 个路口，$n-1$ 条道路把各个路口连接起来，道路是双向的。换言之， IY 所在的城市构成了一棵树。两个不相同路口的距离定义为其简单路径上的道路条数，一个路口与自己的距离为$0$。

我们再定义一条道路的重要度。若一条道路无法使用，会导致有 $t$ 对路口无法相互抵达，则$t$就是该道路的重要度。如下图：

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

(3,4)之间的道路的重要度就为$9$。因为(1,4)(2,4)(3,4)(1,5)(2,5)(3,5)(1,6)(2,6)(3,6)要相互抵达都要经过这条边。

IY 得到了一个很不好的消息，有一个路口正在施工（但是 IY 不知道施工的位置）。施工的范围影响到了距施工点距离为 $k$ 的地方，距离施工点距离小于等于 $k$ 的路口已经全部关闭了。这使得一行人不能经过受影响的路口和与这些路口直接相连的道路。

IY 不得不考虑到最坏的情况，由于他不知道施工的位置，所以他想知道，施工所影响道路的重要度的总和最大是多少。

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

接下来的$n-1$行，每行两个数 $u,v$ 来描述一条道路。表示 $u$ 路口与 $v$ 路口直接相连。

outputFormat: 一个数，表示 所影响道路的重要度的总和的最大值。

hint:
- **样例解释**

样例$1$：就是题面中的图例，若施工位置在 $3$ 或 $4$ 号路口，则会影响的道路重要度总和为$19$。找不出比 $19$ 更大的值。

样例$2$：满足成链的特殊性质。

- **数据范围**

对于前 $20\%$测试点，$n \le 100,0 \le k \le 7$

对于前 $40\%$ 的数据 ：保证数据随机

特殊地：第三个测试点仅有$k==0$

对于 $100\%$的数据：$n \le 30000,0 \le k \le 200$

特殊地：第十个测试点由树退化成了一条链


title: 【CSGRound2】开拓者的卓识

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

（上图转载于某神仙的题目描述）

小 K 又在做白日梦了。他进入到他的幻想中，发现了一个非常有趣的序列$a$和一个非常有趣的数$k$。

description:
我们记一个序列 $[l,r]$ 的 $k$ 阶子段和为 $sum_{k,l,r}$，有

$$sum_{k,l,r}=\begin{cases}\sum\limits_{i=l}^{r}a_i&,k=1\\\sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}sum_{k-1,i,j}&,k\geq 2\end{cases}$$

他现在站在位置 $1$ 上，他每一次往右开拓一个格子就可以增加他 IOI 赛场的 rp，所以他想尽可能的多开拓格子。可是每一次他从 $r$ 开拓到 $r+1$ 需要正确的回答 $sum_{k,1,r}$。小 K 不屑于算，就把任务交给你了。

inputFormat:
两行。第一行 $n,k$，表示 $a$ 的长度和 $k$。

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

outputFormat: 一行，第 $i$ 个数为 $sum_{k,1,i}$。由于答案过大，您只需要求出答案对 $998244353$ 取模的值。


title: Mivik的神力

background: $\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$发怒了，机房的$\textcolor{grey}{\text{deco}}$瑟瑟发抖

description:
$\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$要写一篇文章，在写文章时，他有$n$个备选的单词，第$i$个单词有一个长度$a_i$，$\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$可以选择从第$i$个单词开始写作，一共写$k$秒，第$j$秒会写上第$i+j-1(j\in[1,k])$个单词，并且他在写作时每秒都会获得愉悦值，第$j$秒的愉悦值为$max_{l=i}^{i+j-1} a_l$，现在，请你帮他算出，他每一次写作获得的愉悦值之和

**一句话题意：给出一个序列和多组询问 $(l,q)$ ，求**

$$
\sum_{i=l}^{l+q-1} \max_{l\le j\le i}a_j
$$

**数据要求强制在线**

inputFormat:
第一行，两个数，$n$，$t$，代表词汇个数和问题个数

第二行，$n$个数，第$i$个数代表$a_i$

接下来$t$行，每行两个数，$u$，$v$，$l=1+(u ⊕ lastans)\%n$，$q=1+(v ⊕ (lastans+1))\%(n-l+1)$，代表查询从第 $l$ 秒开始，写作 $q$ 秒的愉悦度之和

$lastans$表示上一次查询的答案，初始$lastans$为$0$

outputFormat: 对于每个询问，回答一行，代表答案


title: 最小度限制生成树

description: 给你一个有 $n$ 个节点，$m$ 条边的带权无向图，你需要求得一个生成树，使边权总和最小，且满足编号为 $s$ 的节点正好连了 $k$ 条边。

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

下面的 $m$ 行，每行三个整数：$u,v,w$，表示有一条 $u$ 连向 $v$ 权值为 $w$ 的边。

outputFormat:
输出一个数：满足要求的生成树的总边权。

可能会出现无解的情况，如果无解，则输出 `Impossible`。

hint:
### 数据范围

对于 $20\%$ 的数据，$n \le 10$，$m \le 30$。
对于 $50\%$ 的数据，$n \le 1000$，$m \le 5000$。
对于 $100\%$ 的数据，$1\leq s \leq n \le 5\times 10^4$，$1\leq m \le 5\times 10^5 $，$1\leq k \le 100$，$0\leq w\leq 3\times 10^4$。

### 注意

本题设有 hack 数据（Subtask $2$），计 $0$ 分，但若没有通过 hack 数据则不算通过本题。

tags: 凸完全单调性, wqs 二分


title: 「SWTR-2」Triangles

background: 小 $\mathrm{A}$ 在学数学。

description:
他遇到了两个谜题：

- 在一个平面内，**线段** $DE$ 与**直线** $FG$ 相交于点 $O$，已知 $\angle DOF=x^{\circ}$，请你在**直线** $FG$ 上找一点 $P$，使得 $\triangle DOP$ 为**等腰**三角形，求 $\angle D$ 的度数。（如果答案不是整数，则保留 $1$ 位小数）

- 已知一个**直角三角形**的两条边分别为 $m,n$，求第三条边的长度（保留 $5$ 位小数）。

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

写一个程序求出问题的答案。

inputFormat: 一行三个**正整数**，分别为 $x,m,n$。

outputFormat:
输出两行，第一行为第一问的答案，第二行为第二问的答案。

如果有多解，请用**空格**隔开，且**从小到大**输出。

hint:
---

### 样例说明

问题 $1$：

- 当点 $P$ 在点 $O$ 左边时，形成的 $\triangle DOP$ 为等边三角形，$\angle D=60^{\circ}$。

- 当点 $P$ 在点 $O$ 右边时，形成的 $\triangle DOP$ 中，$\angle DOP=180^{\circ}-60^{\circ}=120^{\circ}$，为顶角，$\angle D=(180^{\circ}-120^{\circ})/2=30^{\circ}$。

问题 $2$：

第三条边为斜边，长度为 $\sqrt{1^2+1^2}=\sqrt{2}=1.41421\dots$。

---

### 数据范围与约定

$x<90,m\leq n\leq 10^9$。

---

### 出题组提示：

**方法千万条，审题第一条，多解不考虑，爆零两行泪。**


title: 【模板】单调栈

background:
模板题，无背景。

2019.12.12 更新数据，放宽时限，现在不再卡常了。

description:
给出项数为 $n$ 的整数数列 $a_{1 \dots n}$。

定义函数 $f(i)$ 代表数列中第 $i$ 个元素之后第一个大于 $a_i$ 的元素的**下标**，即 $f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}$。若不存在，则 $f(i)=0$。

试求出 $f(1\dots n)$。

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

第二行 $n$ 个正整数 $a_{1\dots n}$。

outputFormat: 一行 $n$ 个整数表示 $f(1), f(2), \dots, f(n)$ 的值。

hint:
【数据规模与约定】

对于 $30\%$ 的数据，$n\leq 100$；

对于 $60\%$ 的数据，$n\leq 5 \times 10^3$ ；

对于 $100\%$ 的数据，$1 \le n\leq 3\times 10^6$，$1\leq a_i\leq 10^9$。


title: [Ynoi2013] 对数据结构的爱

description:
Nauuo 是一个喜欢编程的女孩子。有一天她在做一道题，要求计算一些数的和对一个数 $p$ 取模的结果。

她写出了如下的代码，然后获得了 WA 的评测结果。

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1172F/6c266ee49b8e7d2057bfe4e2a407e0a76704daa8.png)

她很快发现了 bug——`ModAdd` 函数只对 $[0,p)$ 中的数起作用，但是这个问题中的数有可能不在这个范围之内。她对这个错误的函数很好奇，所以她想知道它的运行结果。

然而，原来的代码运行得太慢了，所以她来找你求助。

给定数组 $a_1,a_2,…a_n$ 和一个数 $p$，有 $m$ 个询问，每次给定两个数 $l$ 和 $r$，你需要计算函数 `Sum(a,l,r,p)` 的返回值。函数 `Sum` 的定义在上面的伪代码中已经给出。

注意，在上面的代码中，整数不会越界。

inputFormat:
第一行三个整数 $n$，$m$，$p$，分别代表数组的长度，询问的个数和模数。注意模数只在 `ModAdd` 中用到。

第二行包含 $n$ 个整数 $a_1,a_2,…a_n$，代表给定的数组。

接下来的 $m$ 行，每行两个整数 $l$ 和 $r$，你需要计算 `Sum(a,l,r,p)`。

outputFormat: 按顺序输出 $m$ 个整数，每个一行，代表询问的答案。

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

对于 $100\%$ 的数据，$1\le n\le10^6$，$1\le m\le2\times 10^5$，$1\le p\le10^9$，$-10^9\le a_i\le10^9$，$1\le l\le r\le n$。


title: [Ynoi2013] 大学

description:
一个长为 $n$ 的**非负**整数序列 $a$，支持以下两个操作：

- `1 l r x`：把区间 $[l,r]$ 中所有 $x$ 的倍数除以 $x$。
- `2 l r`：查询区间 $[l,r]$ 的和。

本题强制在线，每次的 $l,r,x$ 需要 xor 上上次答案，如果之前没有询问，则上次答案为 $0$。

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

第二行 $n$ 个非负整数表示 $a_i$。

之后 $m$ 行每行一个操作。

- `1 l r x`：把区间 $[l,r]$ 中所有 $x$ 的倍数除以 $x$。
- `2 l r`：查询区间 $[l,r]$ 的和。

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

hint:
$1\leq n,m\leq 10^5$，$0\leq a_i\leq 5\times 10^5$，解密后的 $x,l,r$ 满足 $1\leq x\leq 5\times 10^5$，$1\leq l\leq r\leq n$。

Idea：nzhtl1477

Solution：nzhtl1477

Code：nzhtl1477，mrsrz

Data：nzhtl1477，mrsrz


title: [Ynoi2013] D2T2

description:
给一个长为 $n$ 的序列，有 $m$ 次查询操作。

查询操作形如 $l\;r\;L\;R$，表示将序列中值在 $[L,R]$ 内的位置保留不变，其他的位置变成 $0$ 时，序列中 $[l,r]$ 区间内的最大子段和，这个子段可以是空的。

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

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

之后 $m$ 行，每行四个整数 $l\;r\;L\;R$ 表示一次查询操作。

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

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

对于 $100\%$ 的数据，$1\leq n,m \le 10^5$，序列中所有数的绝对值 $\le 10^9$。

第四组查询中，值域限制是 $[-1,5]$，序列为 `-1 1 0 5 -1 4`，区间 $[1,6]$ 的最大子段为 $[2,6]$，和为 $9$。

第五组查询中，值域限制是 $[2,5]$，序列为 `0 0 0 5 0 4`，区间 $[2,5]$ 的最大子段为 $[4,4]$（并列），和为 $5$。


title: [Ynoi2013] Ynoi

description:
维护一个由n个非负整数构成的序列 $a_1,a_2,a_3,\ldots,a_n$，支持三种操作：

1. 给定区间 $[l,r]$，将对应区间内的数异或上 $x$。
2. 给定区间 $[l,r]$，将对应区间内的数从小到大排序。
3. 给定区间 $[l,r]$，求区间内的数的异或和。

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

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

接下来 $m$ 行，每行三个整数 $opt,l,r$（$opt\in\{2,3\}$）或四个整数
 $opt,l,r,x$（$opt=1$）表示对应的操作。

outputFormat: 对每个操作 $3$，输出一行，表示对应的答案。


title: 【CSGRound2】逐梦者的初心

background:
#### 注意：本题时限修改至250ms，并且数据进行大幅度加强。本题强制开启O2优化，并且不再重测，请大家自己重新提交。

由于Y校的老师非常毒瘤，要求zhouwc在csp考前最后3天参加期中考，zhouwc非常生气，决定消极考试，以涂完卡但全错为目标。现在retcarizy看zhouwc太可怜了，想要帮zhouwc解决一个问题，但他自己又太忙了，咕咕咕，于是就把问题甩给了你。

description:
给你一个长度为n的字符串S。

有m个操作，保证$m\le n$。

你还有一个字符串T，刚开始为空。

共有两种操作。

第一种操作：

在字符串T的末尾加上一个字符。

第二种操作：

在字符串T的开头加上一个字符。

每次操作完成后要求输出有几个$l \in [1,T.size]$满足以下条件：

对于$\forall i \in [1,l]$有$T_{T.size-l+i} \ne S_{i}$

$Tip:$字符串下标从1开始。$T.size$表示T的长度。

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

第二行n个正整数，用空格隔开，第$i$个整数表示$S_i$。

接下来$m$行，每行两个数字$opt,ch$，$opt=0$表示在T的末尾加一个字符$ch$,$opt=1$表示在T的开头加一个字符$ch$。

outputFormat: 共$m$行，每行一个非负整数表示第m操作后的输出。


title: [SDOI2015] 道路修建

description:
某国有 $2N$ 个城市，这 $2N$ 个城市构成了一个 $2$ 行 $N$ 列的方格网。现在该国政府有一个旅游发展计划，这个计划需要选定 $L$、$R$ 两列 $(L \leq  R)$，修建若干条专用道路，使得这两列之间（包括这两列）的所有 $2(R-L+1)$ 个城市中每个城市可以只通过专用道路就可以到达这 $2(R-L+1)$ 个城市中的任何一个城市。这种专用道路只能在同一行相邻两列的城市或者同一列的两个城市之间修建，且修建需要花费一定的费用。

由于该国政府决定尽量缩减开支，因此政府决定，选定 $L$、$R$ 后，只修建 $2(R-L+1)-1$ 条专用道路，使得这些专用道路构成一个树结构。现在你需要帮助该国政府写一个程序，完成这个任务。具体地，该任务包含 $M$ 个操作，每个操作的格式如下：

1. ``C x0 y0 x1 y1 w``：由于重新对第 $x_0$ 行第 $y_0$ 列的城市和第 $x_1$ 行第 $y_1$ 列的城市之间的情况进行了考察，它们之间修建一条专用道路的花费变成了 $w$；

2. ``Q L R``：若政府选定的两列分别为 $L$、$R$，询问政府的最小开支。

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

第二行，$N-1$ 个整数，其中第 $i$ 个整数表示初始时第 $1$ 行第 $i$ 列的城市和第 $1$ 行第 $i+1$ 列的城市之间修建一条专用道路的费用。

第三行，$N-1$ 个整数，其中第 $i$ 个整数表示初始时第 $2$ 行第 $i$ 列的城市和第 $2$ 行第 $i+1$ 列的城市之间修建一条专用道路的费用。

第四行，$N$ 个整数，其中第 $i$个整数表示初始时第 $1$ 行第 $i$ 列的城市和第 $2$ 行第 $i$ 列的城市之间修建一条专用道路的费用。
接下来的 $M$ 行，每行一个操作。

outputFormat: 对于每个询问操作，输出一行，表示你计算出的政府的最小开支。

hint: 对于全部的数据，$1 \leq N, M \leq 60000$，任何时刻任何一条专用道路的修建费用不超过 $10^4$。


title: [TJOI2017] 可乐（数据加强版）

background: [原题](https://www.luogu.org/problem/P3758) 数据很弱，这个加强版卡掉了暴力的 DP 做法，并且补充了原题题面中缺少的 $\LaTeX$ 。

description: 加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 $1$ 号城市上。这个可乐机器人有三种行为： 停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给加里敦星球城市图，在第 $0$ 秒时可乐机器人在 $1$ 号城市，问经过了 $t$ 秒，可乐机器人的行为方案数是多少？

inputFormat:
第一行输入两个正整数 $N,M$ ，$N$ 表示城市个数，$M$ 表示道路个数。

接下来 $M$ 行输入 $u,v$ ，表示 $u,v$ 之间有一条双向道路。

最后输入时间 $t$ 。

outputFormat: 输出可乐机器人的行为方案数，答案可能很大，请输出对 $2017$ 取模后的结果。


title: 【CSGRound2】光骓者的荣耀

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

小 K 又在做白日梦了。他进入到他的幻想中，发现他打下了一片江山。

description:
小 K 打下的江山一共有 $n$ 个城市，城市 $i$ 和城市 $i+1$ 有一条双向高速公路连接，走这条路要耗费时间 $a_i$。

小 K 为了关心人民生活，决定定期进行走访。他每一次会从 $1$ 号城市到 $n$ 号城市并在经过的城市进行访问。其中终点必须为城市 $n$。

不仅如此，他还有一个传送器，传送半径为 $k$，也就是可以传送到 $i-k$ 和 $i+k$。如果目标城市编号小于 $1$ 则为 $1$，大于 $n$ 则为 $n$。

但是他的传送器电量不足，只能传送一次，况且由于一些原因，他想尽量快的完成访问，于是就想问交通部部长您最快的时间是多少。

注意：**他可以不访问所有的城市，使用传送器不耗费时间**。

inputFormat:
两行，第一行 $n,k$。

第二行 $n-1$ 个整数，第 $i$  个表示$a_i$。

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

hint:
### 样例解释 1：

样例 1,2 的图示均为以下图片：

![MZbuTK.png](https://s2.ax1x.com/2019/11/08/MZbuTK.png)

不使用传送器直接走，答案为 $6$，可以证明这个是最小值。

### 样例解释 2：

在 $3$ 处使用，传送到 $4$，答案为 $3$，可以证明这个是最小值。

### 数据范围：

对于所有数据，$a_i > 0$

![Kvrl34.jpg](https://s2.ax1x.com/2019/11/04/Kvrl34.jpg)


title: [PKUWC2018] 随机游走

description:
给定一棵 $n$ 个结点的树，你从点 $x$ 出发，每次等概率随机选择一条与所在点相邻的边走过去。

有 $Q$ 次询问，每次询问给定一个集合 $S$，求如果从 $x$ 出发一直随机游走，直到点集 $S$ 中所有点都至少经过一次的话，期望游走几步。

特别地，点 $x$（即起点）视为一开始就被经过了一次。

答案对 $998244353 $ 取模。

inputFormat:
第一行三个正整数 $n,Q,x$。

接下来 $n-1$ 行，每行两个正整数 $(u,v)$ 描述一条树边。

接下来 $Q$ 行，每行第一个数 $k$ 表示集合大小，接下来 $k$ 个互不相同的数表示集合 $S$。

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

hint:
对于 $20\%$ 的数据，有 $1\leq n,Q\leq 5$。

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

另有 $10\%$ 的数据，满足对于所有询问有 $k=1$。

另有 $30\%$ 的数据，满足 $1\leq n\leq 10 ,Q=1$。

对于 $100\%$ 的数据，有 $1\leq n\leq 18$，$1\leq Q\leq 5000$，$1\leq k\leq n$。


title: [PKUWC2018] 猎人杀

description:
猎人杀是一款风靡一时的游戏“狼人杀”的民间版本，他的规则是这样的：

一开始有 $n$ 个猎人，第 $i$ 个猎人有仇恨度 $w_i$ ，每个猎人只有一个固定的技能：死亡后必须开一枪，且被射中的人也会死亡。

然而向谁开枪也是有讲究的，假设当前还活着的猎人有 $[i_1\ldots i_m]$，那么有 $\frac{w_{i_k}}{\sum_{j = 1}^{m} w_{i_j}}$ 的概率是向猎人 $i_k$ 开枪。

一开始第一枪由你打响，目标的选择方法和猎人一样（即有 $\frac{w_i}{\sum_{j=1}^{n}w_j}$ 的概率射中第 $i$ 个猎人）。由于开枪导致的连锁反应，所有猎人最终都会死亡，现在 $1$ 号猎人想知道它是最后一个死的的概率。

答案对 $998244353$ 取模。

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

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

outputFormat: 输出答案。


title: [PKUWC2018] 斗地主

background:
斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏，其中大小王各一张，其他数码牌各四张。在斗地主中，牌的大小关系根据牌的数码表示如下：$3<4<5<6<7<8<9<10<J<Q<K<A<2< $小王 $<$ 大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由 $n$ 张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。为了简化题目，本题不考虑花色的影响，即**所有的相同的数码的牌都是被视为一样的**。

在这道题中，允许的出牌牌型有（**这一部分与传统的斗地主有所出入，请注意**）：

|   名称    |           解释           |      举例       |     注     |
| :-----: | :--------------------: | :-----------: | :-------: |
|   火箭    |           双王           |      ♂♀       |           |
|   炸弹    |        相同数码的四张牌        |     6666      |           |
|   单牌    |         单独的一张牌         |       6       | 单张的王也是单牌  |
|   对子    |        相同数码的两张牌        |      66       |  大小王不是对子  |
|   三张牌   |        相同数码的三张牌        |      666      |           |
|   三带一   |  相同数码的三张牌带上一张另外数码的单牌   |     666♂      |  炸弹不是三带一  |
|   三带二   |  相同数码的三张牌带上一个另外数码的对子   |     66699     |           |
|   顺子    |   牌的大小连续的 $5$ 张及以上单牌   |    3456789    | 不能含有大小王和2 |
|   连对    |  牌的大小连续的 $3$ 对及以上的对子   |   33445566    | 不能含有大小王和2 |
|   三顺    |    牌的大小连续的两组及以上的三张牌    |   333444555   | 不能含有大小王和2 |
|   四带二   |     四张相同数码的牌带上两张单牌     | 444456 444455 |           |
| 飞机（单翅膀） | 三顺带上相同数量的**数码两两不同的**单牌 | 33344455569J  |           |
| 飞机（双翅膀） | 三顺带上相同数量的**数码两两不同的**对子 |  3334446699   |           |

**注意**：

1. 在牌型中没有连炸这种牌型，但是形如 444455556666 的牌仍然是能出的，它将被视为 444555666 带 456 的飞机（单翅膀）牌型。
2. 大王和小王数码不同，即飞机带大小王是合法的，例如 333444♂♀
3. 容易验证，上述牌型的规则是合法的，即对于任意合法的牌，它都有唯一的牌型。

两手牌是属于相同牌型的当且仅当他们的名称相同且包含牌的数量相同。相同牌型的牌之间存在着大小关系（火箭是唯一的，不需要比大小）：

1. 三带一三带二的大小取决于那三张相同牌的数码
2. 飞机的大小取决于三顺的大小
3. 四带二的大小取决于四张相同牌的大小
4. 其他牌型的大小取决于牌中的最大的一张牌

下面是对斗地主的游戏过程的描述（**这一部分与传统的斗地主完全相同**）：

1. 在斗地主中，有玩家被分成了两个阵营，一个玩家是地主，剩下两个玩家是农民。地主有 $20$ 张牌，农民每人有 $17$ 张牌（加起来正好是一副牌）。
2. 游戏分成若干轮，每一轮由上一轮的胜者率先出牌（第一轮由地主最先出牌）。接着按照顺序（你可以理解为三个玩家坐成一圈，按照顺时针顺序）出牌。
3. 每一轮第一个出牌的玩家可以出任意牌型任意大小的牌。接着轮到每一个玩家出牌时，他有如下选择：
   1. 不出（过牌）
   2. 出与这一轮中上一次被打出的牌相同牌型但是大小严格更大的牌
   3. 如果上一次被打出的牌不是炸弹或者火箭，那么可以打出任意大小的炸弹
   4. 打出火箭
4. 在一轮中，如果在一个玩家打出牌后，另外两个玩家都选择不出，那么这一轮结束，这一个玩家作为本轮的胜者并开始下一轮
5. 任何时刻如果一个玩家的所有手牌都已打出，那么游戏结束，这一个玩家获胜。
6. 如果地主获胜时，两个农民都一张牌都没有打出，那么就称地主打出了春天。

description:
现在三个人在玩斗地主，如果地主春天了，那么算地主赢，否则即使地主先出完了牌，也视为农民赢。假设三个玩家都以最优决策在行动。

现在给出了 $n(0 \leq n\leq 20)$ 张牌，问地主有多少种初始手牌包含了这 $n$ 张牌，且无论农民的牌如何，他都一定能春天。

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

每组数据输入一行，第一个整数 $n$ 表示固定了的牌数，接下来 $n$ 个空格隔开的整数描述每一张固定了的手牌。

特别的，我们用 $1$ 来表示数码 A， $11$ 表示数码 J， $12$ 表示数码 Q， $13$ 表示数码 K，$14$ 表示小王，$15$ 表示大王。保证输入一定合法，即每种牌的数量不会超出一副牌中牌的数量。

outputFormat:
对于每组数据，输出一个整数表示答案，满足条件的地主的手牌数。答案可能很大，请对 $998244353$ 取模后输出。

**注意**，在这题中我们不考虑花色，如果两种手牌的数码组成完全相同，但是花色不同，他们也是会被视为同一种的。


title: 基础数论函数练习题

background: YSGH 牛逼

description:
给定长度为 $n$ 的数组 $a$，$Q$ 次询问 $\operatorname{lcm}(a_l, a_{l + 1}, \ldots , a_{r - 1}, a_r)$。

由于输出较大，你只需要输出答案对 ${10}^9 + 7$ 取模的值。

inputFormat:
本题有多组数据。

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

对于每组数据，第一行两个正整数 $n, Q$。

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

接下来 $Q$ 行，一行两个正整数 $l,r$（$1 \le l \le r \le n$），表示一次询问。

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


title: 基础字符串练习题

background: YSGH 牛逼

description:
给定长度非零的非空 01 串 $S$。

找出 $S$ 的非空连续子串 $T$ 满足串中 0 的个数减去 1 的个数最大。

你只需要输出最大值即可。

inputFormat: 一行一个 01 串表示 $S$。

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


title: 基础最短路练习题

background: YSGH 牛逼

description:
给定 $n$ 个点 $m$ 条边的简单无向连通图 $G$，边有边权。保证没有重边和自环。

定义一条简单路径的权值为路径上所有边边权的异或和。

保证 $G$ 中不存在简单环使得边权异或和不为 $0$。

$Q$ 次询问 $x$ 到 $y$ 的最短简单路径。

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

接下来 $m$ 行，一行三个非负整数 $x, y, v$（$1 \le x, y \le n$），表示一条连接 $x, y$，权值为 $v$ 的无向边。保证没有重边和自环。

接下来 $Q$ 行，一行两个正整数 $x, y$（$1 \le x, y \le n$），表示一次询问。

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


title: 【模板】Stoer-Wagner

description:
定义无向图 $G$ 的最小割为：一个去掉后可以使 $G$ 变成两个连通分量，且边权和最小的边集的边权和。

给出一张无向图 $G$，求其最小割。

inputFormat:
第一行，两个数 $n,m$，表示点数与边数。

接下来 $m$ 行，每行三个正整数 $a_i,b_i,w_i$，表示 $a_i$ 到 $b_i$ 有一条边权为 $w_i$ 的边。

outputFormat: 一行，一个整数表示 $G$ 的最小割，如果图不联通，请输出 `0` 。

hint:
对于前 $20\%$ 的数据， $n\leq 10$。
对于前 $40\%$ 的数据， $n\leq 100$。
对于另外 $10\%$ 的数据，保证输入为一棵树。
对于另外 $10\%$ 的数据，保证输入为一条链。
对于 $100\%$ 的数据， $n\leq 600,m\leq \frac{n\times (n-1)}{2}$ ，保证 $\sum_{i=1}^{m}w_i \leq10^9$ 。

#### PS：想交 最大流/最小割树 的就省省吧。


title: [RC-05] 01 序列

description:
有一个长度为 $n$ 的 $01$ 序列，它的任意一个长为 $k$ 的连续子串中都有 $a$ 个 $0$ 或 $a+1$ 个 $0$。

求可能的序列数。答案很大，请输出其模 $998244353$ 的值。

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

输入第一行是数据组数 $T$。

每组数据中，输入一行三个整数：$n,k,a$。

outputFormat: 对于每组数据，输出一个非负整数，为可能的序列数模 $998244353$ 的值。


title: 基础博弈练习题

background: YSGH is our red sun.

description:
YSGH 和 YGSH 在打膈膜，YSGS 在旁边围观。

规则是这样的，先给定一个正整数 $m$ 和一个 $n$ 个数的序列 $b$，一开始有一个棋子在 $b$ 的第一个位置，并将 $b_1$ 减去 $1$。此后双方轮流操作，每次操作，假设当前棋子在 $i$，可以把棋子移到一个位置 $j$，满足 $j \in [i, \min(i + m, n)]$ 且 $b_j > 0$，然后将 $b_j$ 减 $1$，YSGH 先手，谁先不能操作谁输。

众所周知，YSGH 和 YGSH 都是绝顶聪明的，所以两人都会使用最优策略。

而隔膜使用的序列 $b$ 是一个序列 $a$ 的一个连续非空子序列，当然序列 $a$ 和每次隔膜使用的序列 $b$ 都是 YSGS 定的。

现在他们进行了 $q$ 轮游戏，给出每轮游戏使用的区间，请你判断每轮谁会赢。

inputFormat:
由于本题数据规模较大，直接输入输出会占用比计算多数倍的时间，因此当询问过多时会对询问的输入输出进行了压缩。

第一行四个正整数 $n, m, q, type$，$n, m, q$ 意义同题面描述，$type$ 表示当前数据的类型，$type = 1$ 说明该组数据进行了压缩，$type = 0$ 则说明没有，数据保证当 $q > {10}^6$ 时，$type=1$。

第二行 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$，意义同题面描述。

如果 $type = 1$，第三行四个正整数 $A, B, C, P$，表示询问的生成方式。

```cpp
int A, B, C, P;
inline int rnd() { return A = (A * B + C) % P; }
```

每次询问时的调用方法为：

```cpp
l = rnd() % n + 1, r = rnd() % n + 1;
```

如果生成的 $l > r$，则还需要交换 $l, r$。

数据保证 $0 \le A B < P$，$0 \le C < P$，$P (B + 1) < 2^{31} - 1$。

如果 $type=0$，接下来 $q$ 行，每行两个正整数 $l, r$，意义同题面描述。

outputFormat:
令 ${ans}_i$ 表示第 $i$ 次询问中 YSGH 是否会赢，如果会赢则 ${ans}_i = 1$，否则 ${ans}_i = 0$。

输出一行一个整数，表示 $\displaystyle \left( \sum_{i = 1}^{q} i^2 \cdot {ans}_i \right)\! \bmod 2^{32}$。


title: 基础最优化练习题

background: YSGH is our red sun.

description:
YSGH 有一个数 $x$，初值为 $0$。接下来 $n$ 分钟，每分钟 YSGH 可以给 $x$ 加上整数 $y$，其中 $y \in [-k, k]$，同时 YSGH 需要保证第 $i$ 分钟结束时 $x \le a_i$。

设 $b_i$ 为第 $i$ 分钟结束时 $x$ 的值，现在 YSGH 给你一个 $n$ 个数的序列 $w$，你需要最大化 $\displaystyle \sum_{i = 1}^{n} b_i w_i$。

你只需要输出最大值即可。

inputFormat:
第一行两个正整数 $n, k$，意义同题面描述。

第二行共 $n$ 个整数，第 $i$ 个表示 $a_i$，意义同题面描述。

第三行共 $n$ 个整数，第 $i$ 个表示 $w_i$，意义同题面描述。

保证输入数据使得至少存在一个序列 $b$ 满足条件。

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


title: 基础函数练习题

background: YSGH is our red sun.

description:
YSGH 有一个 $1 \sim n$ 的排列 $p$ 和一个长度为 $n$ 的整数序列 $w$。

定义：

$$ F(l, r) = \begin{cases} \max(F(l, m - 1), F(m + 1, r)) + w_m & , l \le r \\ 0 & , l > r \end{cases} $$

其中 $m$ 为 $p$ 的区间 $[l, r]$ 的最大值的下标。

$q$ 次询问 $F(l, r)$ 的值。

inputFormat:
第一行两个正整数 $n, q$，意义同题目描述。

第二行共 $n$ 个正整数，第 $i$ 个表示 $p_i$，意义同题目描述。

第三行共 $n$ 个整数，第 $i$ 个表示 $w_i$，意义同题目描述。

接下来共 $q$ 行，每行两个正整数 $l, r$（$1 \le l \le r \le n$），表示询问 $F(l,r)$。

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

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

- Subtask 1（10 points）：$n, q \le 5 \times {10}^3$。
- Subtask 2（10 points）：保证 $p$ 是随机的。
- Subtask 3（20 points）：$n ,q \le 5 \times {10}^4$。
- Subtask 4（20 points）：$n, q \le {10}^5$。
- Subtask 5（20 points）：$w_i \ge 0$。
- Subtask 6（20 points）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n, q \le 5 \times {10}^5$，$|w_i| \le 10^9$，$1 \le p_i \le n$，保证 $p$ 是一个 $1 \sim n$ 的排列。


title: ckw的树

description: ckw有一棵无根树，ckw会随意挑一个点然后开始随机游走，每一个单位时间会等概率跳到与当前点距离不超过$2$的任意一个点。树上有一些点被标记了，求ckw第一次到达被标记的点的期望时间。

inputFormat:
第一行一个数$n$,$m$，表示点的个数和标记个数。

接下来$n-1$行，每行两个数$x$,$y$，表示$x$和$y$之间有一条边。

接下来$m$行，每行一个数表示被标记的点（可能有重复）

outputFormat: $n$行每行一个数，第$i$行的数表示从编号为$i$的点开始随机游走的期望步数$mod\ 998244353$之后的值。

hint:
$2 \le n\le 10^5,1\le m \le n$

$subtask1(20pts):n\le 300$

$subtask2(16pts):$第$i$条边连接$i$和$i+1$

$subtask3(8pts):$第$i$条边链接$1$和$i+1$

$subtask4(20pts):n\le 3000$，且最大点的度数不超过$4$

$subtask5(36pts):$无限制


title: [CTSC2006] 拼图「暂缺SPJ」

description: $5$ 岁的小 $P$ 对剪纸很感兴趣，他总是喜欢把一个矩形的纸片剪成一个又一个的凸多边形。但是，每一次剪完后，他总是怀疑自己弄丢了一些纸片。聪明的他想到了一个方法来检测纸片是否弄丢：他将这些凸多边形拼起来，如果能够拼成一个矩形，他就认为纸片没有弄丢。由于纸片的数量不是很多，这个工作并不难。但是，久而久之，他对这项工作不感兴趣了，所以，他找到了你，希望你能够告诉他，这些凸多边形纸片能不能够拼成矩形。

inputFormat:
第一行只有一个正整数 $n$，表示凸多边形的个数。

以下 $n$ 行每一行描述一个凸多边形，格式如下：

第 $i+1$ 行的第一个数 $m_i$ 表示凸多边形的点数，接下来有 $m_i$ 对实数，一对实数给出了一个点的坐标，这 $m_i$ 个顶点按照从任意一个顶点出发的逆时针顺序给出。且所有实数都在 $(-10^3,10^3)$ 的范围内，小数点后不超过 $8$ 位。

outputFormat:
如果不能拼成矩形，输出只有一行 `No`。

如果能拼成矩形，输出的第一行为 `Yes`。

接下来的 $n$ 行描述拼法。

如果能够拼成一个 $X\times Y$ 的矩形，那么矩形的四个顶点的坐标是 $(0,0), (0,Y), (X,Y), (X,0)$。这 $n$ 行输出每一个凸多边形的顶点的坐标（拼成矩形后）。按照输入的顺序，即第一个输出的凸多边形对应输入的第一个凸多边形。对于每一个凸多边形，输出也按照输入的顺序，即一个多边形的第一个顶点对应输入的第一个顶点。这样，输出总共有 $n$ 行，第 $i$ 行有 $m_i$ 对数。

hint:
#### 样例说明
如下图，左上、右上和左下描述了输入的凸多边形，右下描述了输出的的矩形。

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

#### 注意
由于矩形纸片的两面的颜色不同，所以纸片只能旋转和平移，不能翻转。所以，输出的 $m_i$ 个顶点也应该是逆时针顺序的。

#### 数据范围
对于 $100\%$ 的数据，$1\leq n\leq 8$, $3\leq m_i\leq 8$。

#### 评分说明
两个实数之差的绝对值小于 $10^{-7}$ 时认为两个实数相等。


title: [CTSC2006] 方块填数

description:
最近，一个方块填数的游戏风靡全球：

给定一个 $n\times m$ 的方块。$n$ 行从上到下标号为 $1$ 到 $n$，$m$ 列从左到右标号为 $1$ 到 $m$。如果一个方格所在的行的标号和所在的列的标号都是奇数，那么该方格就称为奇方格。游戏的开始所有的奇方格中都填上了数。你需要在其他的方格里填数，如果填完数后，方块满足下面条件，你就赢得了这个游戏：

1. 任意一个 $a_1\times b_1$ 的子方块中所有数的和大于 $0$；
2. 任意一个 $a_2\times b_2$ 的子方块中所有数的和小于 $0$；

其中，$a_1$、$b_1$、$a_2$、$b_2$ 都是在游戏的开始给定的。一个 $a\times b$ 的子方块是指行标号在 $i$（$1\leq i\leq n-a+1$）到 $i+a-1$ 之间，列标号在 $j(1\leq j\leq m-b+1)$ 到 $j+b-1$ 之间的所有的方格的集合。

小 P 很喜欢这种游戏，他希望你帮助写一个程序给出一种填数的方案，或者告诉他这样的方案不存在。

inputFormat:
第一行为用空格分开的 $6$ 个正整数 $n$, $m$, $a_1$, $b_1$, $a_2$, $b_2$。

从第 $2$ 行起到 $\lfloor \frac{n+1}{2} \rfloor+1$ 行，每一行有 $\lfloor \frac{m+1}{2} \rfloor$ 个整数，第 $i+1$ 行的第 $j(j=1,2,\ldots, \lfloor \frac{m+1}{2} \rfloor)$ 个数表示在游戏开始时方块的第 $2i-1$ 行，$2j-1$ 列的方格所填的整数。

outputFormat:
如果填数方案不存在，输出一行 `No`。

如果填数方案存在，第一行输出 `Yes`。

接下来的 $n$ 行，每一行有用空格分开的 $m$ 个整数，描述一个填数方案。输出的每一个整数必须在 $-10^9$ 到 $10^9$ 之间。

hint:
#### 样例说明

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

填完数后，任意 $2\times 2$ 的方块中的数字之和是 $1$；$3\times 3$ 的方块中的数字之和是 $-1$。

#### 数据范围

对于 $100\%$ 的数据，$1\leq n, m, a_1, b_1, a_2, b_2 \leq 100$。方格里已经填的数都在 $-100$ 到 $100$ 之间。


title: [CTSC2005] 孤独的牧羊女

description:
在瑞典的达拉纳洲有一座高山。山上有一个小屋，里面住着一位牧羊女。每天清晨，隔壁的山头会传来一阵悠扬的长笛声，而牧羊女则会站在屋里用自己的歌声回应。

小屋的俯视图是一个有 $n$ 个顶点的简单多边形，每一面墙可以反射声音，但是由于不可避免的能量损失，最多只能反射 $k$ 次（$k=0$ 表示不能反射声音）。墙面非常光滑，因此声音的反射遵循反射角等于入射角，如图 $1$。墙角不能反射声音，而每面墙的其他部分——即使离墙角很近——都可以反射声音。

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

突然有一天，牧羊女问自己：在小屋的哪些地方能听到她的歌声？假设所有听众都在屋里靠墙而坐，那么歌声能到达的墙一共有多长？
图 $2$ 的四幅示意图分别画出了初始情况和声音经过 $0$、$1$、$2$ 次反射后到达的区域。灰色部分表示能听到歌声的部分，黑点表示牧羊女的位置。本题所求即灰色部分在多边形边界上的**总长度**。

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

inputFormat: 第一行包含 $4$ 个整数 $n，k，x，y$ 分别表示小屋的墙角数、最多反射的次数以及牧羊女的坐标（牧羊女所在位置保证在屋内且至少离墙 $1$ 个单位）。以下 $n$ 行每行两个整数 $x, y$，表示第 $i$ 个墙角的坐标。墙角按照**顺时针或逆时针**排列。

outputFormat: 输出文件仅包含一个实数 $L$，表示能听到歌声的墙的总长度。保留两位小数。

hint:
#### 评分方法

选手输出和参考输出差的绝对值不大于 $0.02$ 时该测试点满分，相差超过 $0.02$ 但不超过 $1$ 时该测试点得 $50\%$ 的分数。在样例$1$中，答案为 $469.84$ 和 $469.88$ 都能拿满分，$468.86$ 和 $470.86$ 都能拿 $50\%$ 的分数。

#### 约定

$3\leq n\leq 50$，$0\leq k\leq 5$，所有坐标为绝对值不超过 $1000$ 的整数。

$50\%$ 的数据满足 $k≤1$。


title: [CTSC2004] 网络改造

background:
HURRICANE 小组原来构建的网络由网络上的交换机及其间的网路构成。交换机分级连接，最高级的为顶级的网关交换机，其他交换机分级相连到该网关交换机上。但值得注意的是，任一台非网关交换机与一台高一级的交换机直接相连。而任一台交换机均可以与几台低一级的交换机直接相连。

但最近，由于原来架设的网络服务有限，需要把网络中的一些交换机（包括网关交换机）升级为核心交换机。由于改造的时间所限，只来得及把不超过 $p$ 台（含 $p$ 台）交换机升级为核心交换机，而所有剩下的交换机则需要通过改造网路的方法和这几台核心交换机直接连接。

但是无论是升级交换机还是改造网络都需要花费一定的资金。现在请你给出一个改造网络的方案。使得按照该方案升级后每一个交换机要么是核心交换机，要么直接和核心交换机相连。并且要求提供的方案使改造所用的总费用最小。

description:
你的程序必须根据给定的输入，给出符合题意的输出：

+ 输入包括网络的拓扑结构，升级网络中每台交换机的费用，以及改造网络的费用，还有可以升级的交换机的最大数目 $p$；
+ 你必须根据输入，找出一个升级的方案，满足升级后的核心交换机的数目不超过给定的可升级交换机最大值 $p$，且使得总费用最少；
+ 其中总费用的计算包括两个部分:
    - 一部分是升级交换机为核心交换机所需要的费用，该部分的费用按照所有的需要升级的交换机所需的费用之和来计算；
    - 另一部分是改造网络所需要的费用，该部分的费用按照所有未升级的交换机到最近的核心交换机的网络路径距离之和来计算；
    - **注意:** 当网络中没有任何交换机升级到核心交换机的时候，由于也没有交换机可以连接到核心交换机，所以我们定义此时的总费用为无穷大。

inputFormat:
第一行为两个正整数 $n(n \leq 400)$ 和 $p$，分别表示网络中交换机的数目（交换机按照 $1$ 到 $n$ 标号）和可升级交换机的最大值。接下来的 $n$ 行每行一个正整数 $c_i$，表示把标号为 $i$ 的交换机升级为核心交换机所需要的费用。

接下来的 $n-1$ 行每行三个正整数 $i$、$j$、$d_{i,j}(d_{i,j}<20000)$，表示编号为 $j$ 的交换机为编号为 $i$ 的交换机的上层交换机，而 $d_{i,j}$ 表示两台交换机之间的网路距离。

outputFormat: 你的输出第一行为一个整数 $M$，表示你的方案的最小总费用。接下来一行包括一个整数 $p_0$，表示你的方案所需要升级为核心交换机的交换机数目。

hint:
#### 样例说明
![](https://cdn.luogu.com.cn/upload/image_hosting/74nd663j.png)

#### 评分方法
本题目一共有十个测试点，每个测试点的分数为总分数的 $10\%$。对于每个测试点来说，如果你的答案正确，那么你将得到该测试点全部的分数，否则得 $0$ 分。

注意，本题目的测试数据中有 $8$ 个数据的 $n$ 不超过 $180$。


title: [THUSC2015] 解密运算

description:
对于一个长度为 $N$ 的字符串，我们在字符串的末尾添加一个特殊的字符 `.`。之后将字符串视为一个环，从位置 $1,2,3,...,N+1$ 为起点读出 $N+1$ 个字符，就能得到 $N+1$ 个字符串。

比如对于字符串 `ABCAAA`，我们可以得到这 $N+1$ 个串：
```plain
ABCAAA.
BCAAA.A
CAAA.AB
AAA.ABC
AA.ABCA
A.ABCAA
.ABCAAA
```
接着我们对得到的这 $N+1$ 个串按字典序从小到大进行排序（注意特殊字符 `.` 的字典序小于任何其他的字符）结果如下：
```plain
.ABCAAA
A.ABCAA
AA.ABCA
AAA.ABC
ABCAAA.
BCAAA.A
CAAA.AB
```
最后，将排序好的 $N+1$ 个串的最后一个字符取出，按照顺序排成一个新的字符串，也就是上面这个表的最后一列，就是加密后的密文 `AAAC.AB`。

请通过加密后的密文求出加密前的字符串。

inputFormat:
第一行有两个整数 $N,M$，分别表示加密前的字符串长度和字符集大小，其中字符用整数 $1,2,3,...,M$ 编号，添加的特殊字符 `.` 用 $0$ 编号。

第二行为 $N+1$ 个整数，表示加密后的字符串。

outputFormat: 输出仅一行，包含 $N$ 个整数，用空格隔开，依次表示加密前字符串中每个字符的编号。

hint:
对于第 $i$ 个测试点 ($i=1 \sim 4$)，$N=5\times (i+1),M\leq 3$。

对于第 $5\sim 6$ 个测试点，$N,M\leq 50$，字符串中字符互不相同。

对于第 $7\sim 8$ 个测试点，$N,M\leq 1000$，字符串中字符互不相同。

对于第 $9\sim 12$ 个测试点，$N,M\leq 1000$。

对于第 $13\sim 20$ 个测试点，$N,M\leq 200000$。


title: [THUSC2015] 异或运算

description: 给定长度为 $n$ 的数列 $X={x_1,x_2,...,x_n}$ 和长度为 $m$ 的数列 $Y={y_1,y_2,...,y_m}$，令矩阵 $A$ 中第 $i$ 行第 $j$ 列的值 $A_{i,j}=x_i\ \operatorname{xor}\ y_j$，每次询问给定矩形区域 $i∈[u,d],j∈[l,r]$，找出第 $k$ 大的 $A_{i,j}$。

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

第二行包含 $n$ 个非负整数 $x_i$。

第三行包含 $m$ 个非负整数 $y_j$。

第四行包含一个正整数 $p$，表示询问次数。

随后 $p$ 行，每行均包含 $5$ 个正整数，用来描述一次询问，每行包含五个正整数 $u,d,l,r,k$，含义如题意所述。

outputFormat: 共 $p$ 行，每行包含一个非负整数，表示此次询问的答案。


title: 「Stoi2033」世界未末日

background:
注意：**利用提交反馈以套取数据的行为属于作弊**。

> 就算是世界要崩溃
> 亲爱的我也绝不会落泪
> 不放弃爱过的那种感觉
> 珍惜着有你记忆的一切
> 就算是世界要倾斜
> 亲爱的我也绝不说离别
> 尽管末日威胁再强烈
> 有爱就不累
> ——《世界未末日》

description:
Vinsta 和 Stella 有 $n$ 堆石子，第 $i$ 堆有 $s_i$ 个。

她们约定从 Vinsta 开始轮流操作，每次操作可以选择不少于 $1$ 堆且不超过 $k$ 堆的石子。对于第 $i$ 堆石子，可以选取两个实数 $a,b$ 满足：

- $a \times b=s_i$
- $a+b=c,c\in[1,s_i]\cap\Z$

并丢掉第 $i$ 堆的 $c$ 个石子，即 $s_i\leftarrow s_i-c$。不能操作者败，她们想要知道 Vinsta 是否有必胜策略。

inputFormat:
第一行共三个正整数： $n,k,S$，其中 $S=\max\{s_i\}$。

第二行共 $n$ 个正整数： $s_i$，表示初始时第 $i$ 堆的石子个数。

outputFormat: 输出共一行。有必胜策略输出 `YES`，否则输出 `NO`。


title: Sone1

description:
给你一棵 $n$ 个节点的有根树，点带权，有 $q$ 次操作，分为十二种：

- `0 x y` 表示将 $x$ 的子树中所有点权都改为 $y$；
- `1 x` 表示把树根换为 $x$ 节点；
- `2 x y z` 表示把 $x$ 到 $y$ 简单路径上所有点权改为 $z$；
- `3 x` 表示询问 $x$ 的子树中最小权值；
- `4 x` 表示询问 $x$ 的子树中最大权值；
- `5 x y` 表示将 $x$ 的子树中所有点权都增加 $y$；
- `6 x y z` 表示将  $x$ 到 $y$ 简单路径上所有点权加上 $z$；
- `7 x y` 表示询问 $x$ 到 $y$ 简单路径上的最小权值；
- `8 x y` 表示询问 $x$ 到 $y$ 简单路径上的最大权值；
- `9 x y` 表示把 $x$ 的父亲换为 $y$，若 $y$ 在 $x$ 的子树里则忽略此操作；
- `10 x y` 表示询问 $x$ 到 $y$ 简单路径上的点权和；
- `11 x` 表示询问 $x$ 的子树中点权和。

inputFormat:
第一行两个正整数 $n,q$，表示节点数与操作数。
接下来 $n-1$ 行，每行两个正整数 $u,v$，表示 $u$ 和 $v$ 之间有一条边。
然后 $n$ 行，每行一个整数表示点权。
后面一行一个正整数表示初始的根。
最后 $q$ 行，每行若干个正整数，表示一次操作。

outputFormat: 对于每个 $3,4,7,8,10,11$ 操作，输出一行一个整数表示答案。

hint:
来源：BZOJ 3153

【数据范围】

对于 $100\%$ 的数据，$1\le n,m \le 10^5$，中间计算的所有值在 $[-2^{31},2^{31})$ 范围内。
由于本题过于难写，可以点击 [这里](https://darkbzoj.cc/data/3153.zip) 下载测试数据，本地通过后再提交。


title: 算术

background: 小 W 去上算术课了。

description:
> 众所周知，高斯在小学的时候，有一天他的数学老师留了一道题：$1+2+\cdots+100=?$，他认为学生们算 $100$ 个数相加要算很久，然后就准备溜去喝咖啡，但是这个时候高斯却举手说他算完了——他用了我们今天众所周知的等差数列求和公式。

但是，这个算术课的老师就像高斯的老师一样不负责任，他在黑板上留了一道算术题就溜去泡妹子了。但小 W 可没高斯那么聪明，而且这个式子看起来没有巧算方法。于是，他通过电话联系上了学 $\text{OI}$ 的你，希望你给他帮助。作为回报，他会给你 $100$ 分作为奖励。

具体来讲，黑板上的式子是这样的：

设 $n$ 的质因数分解结果为 $n=\prod\limits_{i=1}^kp_i^{\alpha_i}$，则定义 $f(n)=\prod\limits_{i=1}^k{\dfrac{p_i^{\alpha_i+1}-1}{p_i^{\alpha_i+1}-p_i^{\alpha_i}}}$，求 $\sum\limits_{i=1}^nf(i)$ 的值（精度要求参见提示与说明）。

**注意：特别地，我们定义** $f(1)=1$。

inputFormat: 一行一个整数 $n$，意义如上。

outputFormat: 一行一个实数表示结果。


title: 【模板】Floyd

type: B

description:
给出一张由 $n$ 个点 $m$ 条边组成的无向图。

求出所有点对 $(i,j)$ 之间的最短路径。

inputFormat:
第一行为两个整数 $n,m$，分别代表点的个数和边的条数。

接下来 $m$ 行，每行三个整数 $u,v,w$，代表 $u,v$ 之间存在一条边权为 $w$ 的边。

outputFormat:
输出 $n$ 行每行 $n$ 个整数。

第 $i$ 行的第 $j$ 个整数代表从 $i$ 到 $j$ 的最短路径。

hint:
对于 $100\%$ 的数据，$n \le 100$，$m \le 4500$，任意一条边的权值 $w$ 是正整数且 $1 \leqslant w \leqslant 1000$。

**数据中可能存在重边。**


title: 走路

background: 小 W 下载了一款运动软件。

description:
小 W 准备在接下来的 $m$ 天中锻炼，由于他不能走得太多以至于累死（怎么可能呢），所以他这 $m$ 天最多一共只能走 $n$ 步。
这个运动软件为了激励小 W 走路，推出了 $k$ 种激励措施，每种激励措施都形如“如果你第 $p$ 天走完了 $q$ 步，那么第 $p$ 天中接下来的每一步都会给你加 $1$ 积分”。**激励措施可以叠加，即走一步你可能可以获得多于 $1$ 积分。**
现在小 W 想知道，他最多可以获取多少积分呢？

inputFormat:
第一行三个整数 $n,m,k$，意义如上。
接下来 $k$ 行，每行两个整数 $p,q$，表示一个激励措施，意义如上。

outputFormat: 一行 $1$ 个整数，表示 $m$ 天后最多可以获得的积分。

hint:
样例解释：
只有一种方案，即在第一天走 $5$ 步，第一、二步各获得 $1$ 积分，第三、四步各获得 $2$ 积分，第五步获得 $3$ 积分，总计 $9$ 积分。
********
数据范围：
对于 $10\%$ 的数据，$n,m,k\le10$。
对于 $40\%$ 的数据，$n,m,k \le 10^3$。
对于 $100\%$ 的数据，$1\le n\le 10^{12}$，$1\le m,k\le 10^5$，$1\le p\le m$，$0\le q\le n$。


title: [RC-03] 上下求索

description:
有一个关于 $x_i(i∈\{1,2,3,...,n\},x_i∈\mathbb{R})$ 的 $n$ 元二次方程：

$$\sum_{i=1}^na_ix_i^2+\sum_{i=1}^{n-1}b_ix_ix_{i+1}=m$$

请您在这个方程中，求出保证方程有解的 $x_1$ 的取值范围。

保证 $x_1$ 有上下界。

inputFormat:
输入一共有三行，

第一行有两个整数 $n,m$；

第二行共有 $n$ 个整数 $a_i$，其中 $i∈\{1,2,3,..,n\}$；

第三行 $n-1$ 个整数 $b_i$，其中 $i∈\{1,2,3,..,n-1\}$。

outputFormat: 一行两个整数，用空格隔开，表示 $x_1$ 的下界与上界（数据保证输出一定是整数）。


title: [CSP-S2019] 格雷码

description:
通常，人们习惯将所有 $n$ 位二进制串按照字典序排列，例如所有 2 位二进制串按字典序从小到大排列为：00，01，10，11。

格雷码（Gray Code）是一种特殊的 $n$ 位二进制串排列法，它要求相邻的两个二进制串间**恰好**有一位**不同**，特别地，第一个串与最后一个串也算作相邻。

所有 2 位二进制串按格雷码排列的一个例子为：00，01，11，10。

$n$ 位格雷码不止一种，下面给出其中一种格雷码的生成算法：
1. 1 位格雷码由两个 1 位二进制串组成，顺序为：0，1。
2. $n + 1$ 位格雷码的前 $2^n$ 个二进制串，可以由依此算法生成的 $n$ 位格雷码（总共 $2^n$ 个 $n$ 位二进制串）按**顺序**排列，再在每个串前加一个前缀 0 构成。
3. $n + 1$ 位格雷码的后 $2^n$ 个二进制串，可以由依此算法生成的 $n$ 位格雷码（总共 $2^n$ 个 $n$ 位二进制串）按**逆序**排列，再在每个串前加一个前缀 1 构成。

综上，$n + 1$ 位格雷码，由 $n$ 位格雷码的 $2^n$ 个二进制串按顺序排列再加前缀 0，和按逆序排列再加前缀 1 构成，共 $2^{n+1}$ 个二进制串。另外，对于 $n$ 位格雷码中的 $2^n$ 个 二进制串，我们按上述算法得到的排列顺序将它们从 $0 \sim 2^n - 1$ 编号。

按该算法，2 位格雷码可以这样推出：

1. 已知 1 位格雷码为 0，1。
2. 前两个格雷码为 00，01。后两个格雷码为 11，10。合并得到 00，01，11，10，编号依次为 0 ~ 3。

同理，3 位格雷码可以这样推出：

1. 已知 2 位格雷码为：00，01，11，10。
2. 前四个格雷码为：000，001，011，010。后四个格雷码为：110，111，101，100。合并得到：000，001，011，010，110，111，101，100，编号依次为 0 ~ 7。

现在给出 $n$，$k$，请你求出按上述算法生成的 $n$ 位格雷码中的 $k$ 号二进制串。

inputFormat: 仅一行两个整数 $n$，$k$，意义见题目描述。

outputFormat: 仅一行一个 $n$ 位二进制串表示答案。

hint:
【样例 1 解释】

2 位格雷码为：00，01，11，10，编号从 0∼3，因此 3 号串是 10。

【样例 2 解释】

3 位格雷码为：000，001，011，010，110，111，101，100，编号从 0∼7，因此 5 号串是 111。

【数据范围】

对于 $50\%$ 的数据：$n \leq 10$

对于 $80\%$ 的数据：$k \leq 5 \times 10^6$

对于 $95\%$ 的数据：$k \leq 2^{63} - 1$

对于 $100\%$ 的数据：$1 \leq n \leq 64$, $0 \leq k \lt 2^n$


title: [CSP-S2019] 树上的数

description:
给定一个大小为 $n$ 的树，它共有 $n$ 个结点与 $n - 1$ 条边，结点从 $1 \sim n$ 编号。初始时每个结点上都有一个 $1 \sim n$ 的数字，且每个 $1 \sim n$ 的数字都只在**恰好**一个结点上出现。

接下来你需要进行**恰好** $n - 1$ 次删边操作，每次操作你需要选一条**未被删去**的边，此时这条边所连接的两个结点上的数字将会**交换**，然后这条边将被删去。

$n - 1$ 次操作过后，所有的边都将被删去。此时，按数字从小到大的顺序，将数字 $1 \sim n$ 所在的结点编号依次排列，就得到一个结点编号的排列 $P_i$。现在请你求出，在最优操作方案下能得到的**字典序最小**的 $P_i$。

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

如上图，蓝圈中的数字 $1 \sim 5$ 一开始分别在结点②、①、③、⑤、④。按照 (1)(4)(3)(2) 的顺序删去所有边，树变为下图。按数字顺序得到的结点编号排列为①③④②⑤，该排列是所有可能的结果中字典序最小的。

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

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

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

对于每组测试数据：

第一行一个整数 $n$，表示树的大小。

第二行 $n$ 个整数，第 $i (1 \leq i \leq n)$ 个整数表示数字 $i$ 初始时所在的结点编号。

接下来 $n - 1$ 行每行两个整数 $x$, $y$，表示一条连接 $x$ 号结点与 $y$ 号结点的边。

outputFormat: 对于每组测试数据，输出一行共 $n$ 个用空格隔开的整数，表示最优操作方案下所能得到的字典序最小的 $P_i$。


title: [CSP-S2019] 括号树

background:
本题中**合法括号串**的定义如下：
1.	`()` 是合法括号串。
2.	如果 `A` 是合法括号串，则 `(A)` 是合法括号串。
3.	如果 `A`，`B` 是合法括号串，则 `AB` 是合法括号串。

本题中**子串**与**不同的子串**的定义如下：
1.	字符串 `S` 的子串是 `S` 中**连续**的任意个字符组成的字符串。`S` 的子串可用起始位置 $l$ 与终止位置 $r$ 来表示，记为 $S (l, r)$（$1 \leq l \leq r \leq |S |$，$|S |$ 表示 S 的长度）。
2.	`S` 的两个子串视作不同**当且仅当**它们在 `S` 中的位置不同，即 $l$ 不同或 $r$ 不同。

description:
一个大小为 $n$ 的树包含 $n$ 个结点和 $n - 1$ 条边，每条边连接两个结点，且任意两个结点间**有且仅有**一条简单路径互相可达。

小 Q 是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为 $n$ 的树，树上结点从 $1 \sim n$ 编号，$1$ 号结点为树的根。除 $1$ 号结点外，每个结点有一个父亲结点，$u$（$2 \leq u \leq n$）号结点的父亲为 $f_u$（$1 ≤ f_u < u$）号结点。

小 Q 发现这个树的每个结点上**恰有**一个括号，可能是`(` 或`)`。小 Q 定义 $s_i$ 为：将根结点到 $i$ 号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。

显然 $s_i$ 是个括号串，但不一定是合法括号串，因此现在小 Q 想对所有的 $i$（$1\leq i\leq n$）求出，$s_i$ 中有多少个**互不相同的子串**是**合法括号串**。

这个问题难倒了小 Q，他只好向你求助。设 $s_i$ 共有 $k_i$ 个不同子串是合法括号串， 你只需要告诉小 Q 所有 $i \times k_i$ 的异或和，即：
$$ (1 \times k_1)\ \text{xor}\ (2 \times k_2)\ \text{xor}\ (3 \times k_3)\ \text{xor}\ \cdots\ \text{xor}\ (n \times k_n) $$
其中 $xor$ 是位异或运算。

inputFormat:
第一行一个整数 $n$，表示树的大小。

第二行一个长为 $n$ 的由`(` 与`)` 组成的括号串，第 $i$ 个括号表示 $i$ 号结点上的括号。

第三行包含 $n − 1$ 个整数，第 $i$（$1 \leq i \lt n$）个整数表示 $i + 1$ 号结点的父亲编号 $f_{i+1}$。

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

hint:
【样例解释1】

树的形态如下图：

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

将根到 1 号结点的简单路径上的括号，按经过顺序排列所组成的字符串为 `(`，子串是合法括号串的个数为 $0$。

将根到 2 号结点的字符串为 `((`，子串是合法括号串的个数为 $0$。

将根到 3 号结点的字符串为 `()`，子串是合法括号串的个数为 $1$。

将根到 4 号结点的字符串为 `(((`，子串是合法括号串的个数为 $0$。

将根到 5 号结点的字符串为 `(()`，子串是合法括号串的个数为 $1$。

【数据范围】

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


title: [CSP-J2019] 数字游戏

description:
小 K 同学向小 P 同学发送了一个长度为 $8$ 的 **01 字符串**来玩数字游戏，小 P 同学想要知道字符串中究竟有多少个 $1$。

注意：01 字符串为每一个字符是 $0$ 或者 $1$ 的字符串，如 `101` 为一个长度为 $3$ 的 01 字符串。

inputFormat: 输入文件只有一行，一个长度为 $8$ 的 01 字符串 $s$。

outputFormat: 输出文件只有一行，包含一个整数，即 01 字符串中**字符 $\mathbf 1$** 的个数。

hint:
**样例 1 说明**

该 01 字符串中有 $2$ 个字符 $1$。

**样例 2 说明**

该 01 字符串中有 $8$ 个字符 $1$。

**数据规模与约定**

- 对于 $20\%$ 的数据，保证输入的字符全部为 $0$。
- 对于 $100\%$ 的数据，输入只可能包含字符 $0$ 和字符 $1$，字符串长度固定为 $8$。


title: [CSP-J2019] 公交换乘

description:
著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交车的优惠方案：
1. 在搭乘一次地铁后可以获得一张优惠票，有效期为 45 分钟，在有效期内可以消耗这张优惠票，免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟，即：
$t_{bus} - t_{subway} \leq 45$。
2. 搭乘地铁获得的优惠票可以累积，即可以连续搭乘若干次地铁后再连续使用优惠票搭乘公交车。
3. 搭乘公交车时，如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。

现在你得到了小轩最近的公共交通出行记录，你能帮他算算他的花费吗?

inputFormat:
输入文件的第一行包含一个正整数 $n$，代表乘车记录的数量。

接下来的 $n$ 行，每行包含 3 个整数，相邻两数之间以一个空格分隔。第 $i$ 行的第 1 个整数代表第 $i$ 条记录乘坐的交通工具，0 代表地铁，1 代表公交车；第 2 个整数代表第 $i$ 条记录乘车的票价 $price_i$ ；第三个整数代表第 $i$ 条记录开始乘车的时间 $t_i$（距 0 时刻的分钟数）。

我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。

outputFormat: 输出文件有一行，包含一个正整数，代表小轩出行的总花费。

hint:
**样例 1 说明**

第一条记录，在第 3 分钟花费 10 元乘坐地铁。

第二条记录，在第 46 分钟乘坐公交车，可以使用第一条记录中乘坐地铁获得的优惠票，因此没有花费。

第三条记录，在第 50 分钟花费 12 元乘坐地铁。

第四条记录，在第 96 分钟乘坐公交车，由于距离第三条记录中乘坐地铁已超过 45 分钟，所以优惠票已失效，花费 3 元乘坐公交车。

第五条记录，在第 110 分钟花费 5 元乘坐地铁。

第六条记录，在第 135 分钟乘坐公交车，由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为 6 元，高于第五条记录中地铁的票价 5 元，所以不能使用优惠票，花费 6 元乘坐公交车。

总共花费 36 元。

**样例 2 说明**

第一条记录，在第 1 分钟花费 5 元乘坐地铁。

第二条记录，在第 16 分钟花费 20 元乘坐地铁。

第三条记录，在第 23 分钟花费 7 元乘坐地铁。

第四条记录，在第 31 分钟乘坐公交车，此时只有第二条记录中乘坐的地铁票价高于本次公交车票价，所以使用第二条记录中乘坐地铁获得的优惠票。

第五条记录，在第 38 分钟乘坐公交车，此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用，使用获得最早的优惠票，即第一条记录中乘坐地铁获得的优惠票。

第六条记录，在第 68 分钟乘坐公交车，使用第三条记录中乘坐地铁获得的优惠票。

总共花费 32 元。

**数据规模与约定**

对于 $30\%$ 的数据，$n \leq 1000$，$t_i \leq 10^6$。

另有 $15\%$ 的数据，$t_i \leq 10^7$，所有 $price_i$ 相等。

另有 $15\%$ 的数据，$t_i \leq 10^9$，所有 $price_i$ 相等。

对于 $100\%$ 的数据，$n \leq 10^5$，$t_i \leq 10^9$，$1 \leq price_i \leq 1000$。


title: [CSP-J2019] 纪念品

description:
小伟突然获得一种超能力，他知道未来 $T$ 天 $N$ 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。

每天，小伟可以进行以下两种交易**无限次**：
1. 任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
2. 卖出持有的任意一个纪念品，以当日价格换回金币。

每天卖出纪念品换回的金币可以**立即**用于购买纪念品，当日购买的纪念品也可以**当日卖出**换回金币。当然，一直持有纪念品也是可以的。

$T$ 天之后，小伟的超能力消失。因此他一定会在第 $T$ 天卖出**所有**纪念品换回金币。

小伟现在有 $M$ 枚金币，他想要在超能力消失后拥有尽可能多的金币。

inputFormat:
第一行包含三个正整数 $T, N, M$，相邻两数之间以一个空格分开，分别代表未来天数 $T$，纪念品数量 $N$，小伟现在拥有的金币数量 $M$。

接下来 $T$ 行，每行包含 $N$ 个正整数，相邻两数之间以一个空格分隔。第 $i$ 行的 $N$ 个正整数分别为 $P_{i,1},P_{i,2},\dots,P_{i,N}$，其中 $P_{i,j}$ 表示第 $i$ 天第 $j$ 种纪念品的价格。

outputFormat: 输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。

hint:
**样例 1 说明**

最佳策略是：

第二天花光所有 $100$ 枚金币买入 $5$ 个纪念品 $1$；

第三天卖出 $5$ 个纪念品 $1$，获得金币 $125$ 枚；

第四天买入 $6$ 个纪念品 $1$，剩余 $5$ 枚金币；

第六天必须卖出所有纪念品换回 $300$ 枚金币，第四天剩余 $5$ 枚金币，共 $305$ 枚金币。

超能力消失后，小伟最多拥有 $305$ 枚金币。

**样例 2 说明**

最佳策略是：

第一天花光所有金币买入 $10$ 个纪念品 $1$；

第二天卖出全部纪念品 $1$ 得到 $150$ 枚金币并买入 $8$ 个纪念品 $2$ 和 $1$ 个纪念品 $3$，剩余 $1$ 枚金币；

第三天必须卖出所有纪念品换回 $216$ 枚金币，第二天剩余 $1$ 枚金币，共 $217$ 枚金币。

超能力消失后，小伟最多拥有 $217$ 枚金币。

**数据规模与约定**

对于 $10\%$ 的数据，$T = 1$。

对于 $30\%$ 的数据，$T \leq 4, N \leq 4, M \leq 100$，所有价格 $10 \leq P_{i,j} \leq 100$。

另有 $15\%$ 的数据，$T \leq 100, N = 1$。

另有 $15\%$ 的数据，$T = 2, N \leq 100$。

对于 $100\%$ 的数据，$T \leq 100, N \leq 100, M \leq 10^3$，所有价格 $1 \leq P_{i,j} \leq 10^4$，数据保证任意时刻，小伟手上的金币数不可能超过 $10^4$。


title: [CSP-J2019] 加工零件

description:
凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。工厂里有 $n$ 位工人，工人们从 $1 \sim n$ 编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。

如果 $x$ 号工人想生产一个被加工到第 $L\,(L \gt 1)$ 阶段的零件，则**所有**与 $x$ 号工人有传送带**直接**相连的工人，都需要生产一个被加工到第 $L - 1$ 阶段的零件（但 $x$ 号工人自己**无需**生产第 $L - 1$ 阶段的零件）。

如果 $x$ 号工人想生产一个被加工到第 $1$ 阶段的零件，则**所有**与 $x$ 号工人有传送带**直接**相连的工人，都需要为 $x$ 号工人提供一个原材料。

轩轩是 $1$ 号工人。现在给出 $q$ 张工单，第 $i$ 张工单表示编号为 $a_i$ 的工人想生产一个第 $L_i$ 阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来！

inputFormat:
第一行三个正整数 $n$，$m$ 和 $q$，分别表示工人的数目、传送带的数目和工单的数目。

接下来 $m$ 行，每行两个正整数 $u$ 和 $v$，表示编号为 $u$ 和 $v$ 的工人之间存在一条零件传输带。保证 $u \neq v$。

接下来 $q$ 行，每行两个正整数 $a$ 和 $L$，表示编号为 $a$ 的工人想生产一个第 $L$ 阶段的零件。

outputFormat: 共 $q$ 行，每行一个字符串 `Yes` 或者 `No`。如果按照第 $i$ 张工单生产，需要编号为 1 的轩轩提供原材料，则在第 $i$ 行输出 `Yes`；否则在第 $i$ 行输出 `No`。注意输出**不含**引号。

hint:
**样例 1 说明**

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

编号为 1 的工人想生产第 1 阶段的零件，需要编号为 2 的工人提供原材料。

编号为 2 的工人想生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。

编号为 3 的工人想生产第 1 阶段的零件，需要编号为 2 的工人提供原材料。

编号为 1 的工人想生产第 2 阶段的零件，需要编号为 2 的工人生产第 1 阶段的零 件，需要编号为 1 和 3 的工人提供原材料。

编号为 2 的工人想生产第 2 阶段的零件，需要编号为 1 和 3 的工人生产第 1 阶段的零件，他/她们都需要编号为 2 的工人提供原材料。

编号为 3 的工人想生产第 2 阶段的零件，需要编号为 2 的工人生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。

**样例 2 说明**

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

编号为 1 的工人想生产第 1 阶段的零件，需要编号为 2 和 5 的工人提供原材料。

编号为 1 的工人想生产第 2 阶段的零件，需要编号为 2 和 5 的工人生产第 1 阶段的零件，需要编号为 1,3,4 的工人提供原材料。

编号为 1 的工人想生产第 3 阶段的零件，需要编号为 2 和 5 的工人生产第 2 阶段的零件，需要编号为 1,3,4 的工人生产第 1 阶段的零件，需要编号为 2,3,4,5 的工人提供原材料。

编号为 1 的工人想生产第 4 阶段的零件，需要编号为 2 和 5 的工人生产第 3 阶段的零件，需要编号为 1,3,4 的工人生产第 2 阶段的零件，需要编号为 2,3,4,5 的工人生产第 1 阶段的零件，需要全部工人提供原材料。

编号为 1 的工人想生产第 5 阶段的零件，需要编号为 2 和 5 的工人生产第 4 阶段的零件，需要编号为 1,3,4 的工人生产第 3 阶段的零件，需要编号为 2,3,4,5 的工人生产第 2 阶段的零件，需要全部工人生产第 1 阶段的零件，需要全部工人提供原材料。

**数据规模与约定**

共 $20$ 个测试点。

对所有测试点保证 $1 \leq u, v, a \leq n$。

测试点 $1\sim4$，$1 \leq n, m \leq 1000$，$q = 3$，$L = 1$。

测试点 $5\sim8$，$1 \leq n, m \leq 1000$，$q = 3$，$1 \leq L \leq 10$。

测试点 $9\sim12$，$1 \leq n, m, L \leq 1000$，$1 \leq q \leq 100$。

测试点 $13\sim16$，$1 \leq n, m, L \leq 1000$，$1 \leq q \leq 10^5$。

测试点 $17\sim20$，$1 \leq n, m, q \leq 10^5$，$1 \leq L \leq 10^9$。


title: [CSP-S2019] Emiya 家今天的饭

description:
Emiya 是个擅长做菜的高中生，他共掌握 $n$ 种**烹饪方法**，且会使用 $m$ 种**主要食材**做菜。为了方便叙述，我们对烹饪方法从 $1 \sim n$ 编号，对主要食材从 $1 \sim m$ 编号。

Emiya 做的每道菜都将使用**恰好一种**烹饪方法与**恰好一种**主要食材。更具体地，Emiya 会做 $a_{i,j}$ 道不同的使用烹饪方法 $i$ 和主要食材 $j$ 的菜（$1 \leq i \leq n$、$1 \leq j \leq m$），这也意味着 Emiya 总共会做 $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} a_{i,j}$ 道不同的菜。

Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友，然而三个人对菜的搭配有不同的要求，更具体地，对于一种包含 $k$ 道菜的搭配方案而言：
- Emiya 不会让大家饿肚子，所以将做**至少一道菜**，即 $k \geq 1$
- Rin 希望品尝不同烹饪方法做出的菜，因此她要求每道菜的**烹饪方法互不相同**
- Yazid 不希望品尝太多同一食材做出的菜，因此他要求每种**主要食材**至多在**一半**的菜（即 $\lfloor \frac{k}{2} \rfloor$ 道菜）中被使用

这里的 $\lfloor x \rfloor$ 为下取整函数，表示不超过 $x$ 的最大整数。

这些要求难不倒 Emiya，但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在一种方案中出现，而不在另一种方案中出现。

Emiya 找到了你，请你帮他计算，你只需要告诉他符合所有要求的搭配方案数对质数 $998,244,353$ 取模的结果。

inputFormat:
第 1 行两个用单个空格隔开的整数 $n,m$。

第 2 行至第 $n + 1$ 行，每行 $m$ 个用单个空格隔开的整数，其中第 $i + 1$ 行的 $m$ 个数依次为 $a_{i,1}, a_{i,2}, \cdots, a_{i,m}$。

outputFormat: 仅一行一个整数，表示所求方案数对 $998,244,353$ 取模的结果。


title: [CSP-S2019] 划分

description:
2048 年，第三十届 CSP 认证的考场上，作为选手的小明打开了第一题。这个题的样例有 $n$ 组数据，数据从 $1 \sim n$ 编号，$i$ 号数据的规模为 $a_i$。

小明对该题设计出了一个暴力程序，对于一组规模为 $u$ 的数据，该程序的**运行时间**为 $u^2$。然而这个程序运行完一组规模为 $u$ 的数据之后，它将在任何一组规模**小于** $u$ 的数据上运行错误。样例中的 $a_i$ 不一定递增，但小明又想在不修改程序的情况下正确运行样例，于是小明决定使用一种非常原始的解决方案：将所有数据划分成若干个数据段，段内数据编号**连续**，接着将同一段内的数据合并成新数据，其规模等于段内原数据的**规模之和**，小明将让新数据的规模能够递增。

也就是说，小明需要找到一些分界点 $1 \leq k_1 \lt k_2 \lt \cdots \lt k_p \lt n$，使得

$$ \sum_{i=1}^{k_1} a_i \leq \sum_{i=k_1+1}^{k_2} a_i \leq \cdots \leq \sum_{i=k_p+1}^{n} a_i $$

注意 $p$ 可以为 $0$ 且此时 $k_0 = 0$，也就是小明可以将所有数据合并在一起运行。

小明希望他的程序在正确运行样例情况下，运行时间也能尽量小，也就是**最小化**

$$ (\sum_{i=1}^{k_1} a_i)^2 + (\sum_{i=k_1+1}^{k_2} a_i)^2 + \cdots + (\sum_{i=k_p+1}^{n} a_i)^2 $$

小明觉得这个问题非常有趣，并向你请教：给定 $n$ 和 $a_i$，请你求出最优划分方案下，小明的程序的最小运行时间。

inputFormat:
**由于本题的数据范围较大，部分测试点的 $a_i$ 将在程序内生成。**

第一行两个整数 $n, type$。$n$ 的意义见题目描述，$type$ 表示输入方式。
1. 若 $type = 0$，则该测试点的 $a_i$ **直接给出**。输入文件接下来：第二行 $n$ 个以空格分隔的整数 $a_i$，表示每组数据的规模。
2. 若 $type = 1$，则该测试点的 $a_i$ 将**特殊生成**，生成方式见后文。输入文件接下来：第二行六个以空格分隔的整数 $x, y, z, b_1, b_2, m$。接下来 $m$ 行中，第 $i (1 \leq i \leq m)$ 行包含三个以空格分隔的正整数 $p_i, l_i, r_i$。

对于 $type = 1$ 的 23~25 号测试点，$a_i$ 的生成方式如下：

给定整数 $x, y, z, b_1, b_2, m$，以及 $m$ 个三元组 $(p_i, l_i, r_i)$。

保证 $n \geq 2$。若 $n \gt 2$，则 $\forall 3 \leq i \leq n, b_i = (x \times b_{i−1} + y \times b_{i−2} + z) \mod 2^{30}$。

保证 $1 \leq p_i \leq n, p_m = n$。令 $p_0 = 0$，则 $p_i$ 还满足 $\forall 0 \leq i \lt m$ 有 $p_i \lt p_{i+1}$。

对于所有 $1 \leq j \leq m$，若下标值 $i (1 \leq i \leq n)$满足 $p_{j−1} \lt i \leq p_j$，则有

$$a_i = \left(b_i \mod \left( r_j − l_j + 1 \right) \right) + l_j$$

**上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。**

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


title: [CSP-S2019] 树的重心

description:
小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：
1. 一个大小为 $n$ 的树由 $n$ 个结点与 $n - 1$ 条无向边构成，且满足任意两个结点间**有且仅有**一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为**恰好**两个子树。
2. 对于一个大小为 $n$ 的树与任意一个树中结点 $c$，称 $c$ 是该树的**重心**当且仅当在树中删去 $c$ 及与它关联的边后，分裂出的所有子树的大小均**不超过** $\lfloor \frac{n}{2} \rfloor$（其中 $\lfloor x \rfloor$ 是下取整函数）。对于包含至少一个结点的树，它的重心只可能有 1 或 2 个。

课后老师给出了一个大小为 $n$ 的树 $S$，树中结点从 $1 \sim n$ 编号。小简单的课后作业是求出 $S$ 单独删去每条边后，分裂出的两个子树的重心编号和之和。即：

$$
\sum_{(u,v) \in E} \left( \sum_{1 \leq x \leq n \atop 且 x 号点是 S'_u 的重心} x + \sum_{1 \leq y \leq n \atop 且 y 号点是 S'_v 的重心} y \right)
$$

上式中，$E$ 表示树 $S$ 的边集，$(u,v)$ 表示一条连接 $u$ 号点和 $v$ 号点的边。$S'_u$ 与 $S'_v$ 分别表示树 $S$ 删去边 $(u,v)$ 后，$u$ 号点与 $v$ 号点所在的被分裂出的子树。

小简单觉得作业并不简单，只好向你求助，请你教教他。

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

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

接下来依次给出每组输入数据，对于每组数据：

第一行一个整数 $n$ 表示树 $S$ 的大小。

接下来 $n − 1$ 行，每行两个以空格分隔的整数 $u_i$，$v_i$，表示树中的一条边 $(u_i,v_i)$。

outputFormat: 共 $T$ 行，每行一个整数，第 $i$ 行的整数表示：第 $i$ 组数据给出的树单独删去每条边后，分裂出的两个子树的重心编号和之和。


title: 拉格朗日插值2

description:
给定一个不超过 $n$ 次的多项式的 $n+1$ 个点值 $f(0),f(1) \dots f(n)$，和一个正整数 $m$，求 $f(m),f(m+1) \dots f(m+n)$。

答案对 $998244353$ 取模。

inputFormat:
第一行两个正整数 $n,m$，意义如题目描述。
第二行 $n+1$ 个整数，表示 $f(0),f(1) \dots f(n)$。

outputFormat: 输出一行 $n+1$ 个整数，表示 $f(m),f(m+1) \dots f(m+n)$。


title: 「RdOI R1」平衡常数(balance)

description:
给定一棵以 $1$ 为根的点带权有根树 $G=(V,E)$，第 $i$ 个节点的权值记为
 $w_i$，以 $i$ 为根的子树的点集记为 $V_i$，求一个点集 $V'\subseteq V$，满足以下条件：

- $\forall i$，都有 $|V_i \cap V'| \le \lfloor \frac{|V_i|}{2} \rfloor$

- 最大化 $\sum _{i \in V'} w_i$

输出 $\sum _{i\in V'} w_i$ 即可，也就是选取的点的权值和。

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

第二行为 $n$ 个正整数 $w_i$。

接下来 $n-1$ 行每行为两个整数 $u,v$，表示第 $i$ 条边的两个端点。

outputFormat: 输出只有一行，为你所求得的最大总和。


title: [GZOI2017] 取石子游戏

background: GZOI2017 D1T1

description:
Alice 和 Bob 在玩一个古老的游戏。现在有若干堆石子，Alice 和 Bob 轮流取，每次可以选择其中某一堆的石子中取出任意颗石子，但不能不取，谁先取完使得另一个人不能取了算赢。

现在场地上有 $N$ 堆石子，编号为 $1$ 至 $N$。Alice 很快发现了这个游戏存在一些固定的策略。阴险的 Alice 想赢得这场比赛就来找到主办方你，希望你在这 $N$ 堆石子中选出若干堆石子作为最后游戏用的石子堆并使得 Alice 能获得胜利。你自然不想让 Alice 得逞，所以你提出了一个条件：Alice 在这个游戏中第一次取的那堆石子的编号需要你来指定（仅指定取的石子堆编号，不指定第一次取多少个，这个指定的石子堆必然包含在最后游戏用的石子堆中）。

现在你很好奇，你想算算有多少种方案让 Alice 不能获胜。注意，即使选出的石子堆的编号的集合完全相同，指定第一次取的石子堆的编号不同，也认为方案是不同的。

inputFormat:
第一行，一个正整数 $N$，表示石子堆数。

第二行，$N$ 个正整数，表示各堆石子的数量，按编号 $1$ 至 $N$ 依次给出。

outputFormat: 一行，表示方案数。答案对 $10^9+7$ 取模。


title: [GZOI2017] 小z玩游戏

background: GZOI2017 D1T2

description:
小 z 很无聊。

小 z 要玩游戏。

小 z 有 $N$ 个新游戏，第 $i$ 个游戏看上去的有趣程度为 $w_i$。

小 z 很挑，他只会玩看上去的有趣程度是自己兴奋程度整数倍的游戏。

由于游戏实际上有好玩的也有不好玩的，玩完第 $i$ 个游戏后，小 z 的兴奋程度会变为 $e_i$。

已知小 z 初始兴奋程度为 $1$，请问小 z 有多少个游戏可能会玩两次？

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

对于每组测试数据：

- 第一行一个正整数 $N$，表示游戏的个数。
- 第二行 $N$ 个正整数，第 $i$ 个数 $w_i$，表示第 $i$ 个游戏看上去的有趣程度为 $w_i$。
- 第三行 $N$ 个正整数，第 $i$ 个数 $e_i$，表示小 z 玩完第 $i$ 个游戏后，小 z 的兴奋程度会变为 $e_i$。

outputFormat:
共 $T$ 行。

每行一个正整数，表示对应测试数据，小 z 可能会玩两次的游戏数量。

hint:
### 样例 2 解释

数字代表游戏编号，箭头表示下一个。

- 情况 $1$：$2\to 5\to 4\to 2$；
- 情况 $2$：$5\to 4\to 2\to 5$；
- 情况 $3$：$4\to 2\to 5\to 4$。

所以小 z 可能玩 $2,4,5$ 两次。

小 z 无论如何都不能玩 $1$ 或 $3$ 两次。

### 数据范围及约定

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


title: 【深基2.例5】苹果采购

description: 现在需要采购一些苹果，每名同学都可以分到固定数量的苹果，并且已经知道了同学的数量，请问需要采购多少个苹果？

inputFormat: 输入两个不超过 $10^9$ 正整数，分别表示每人分到的数量和同学的人数。

outputFormat: 一个整数，表示答案。保证输入和答案都在 int 范围内的非负整数。


title: 【深基2.例6】字母转换

description: 输入一个小写字母，输出其对应的大写字母。例如输入 q[回车] 时，会输出 Q。

samples: q Q


title: 【深基2.例7】数字反转

description: 输入一个不小于 $100$ 且小于 $1000$，同时包括小数点后一位的一个浮点数，例如 $123.4$ ，要求把这个数字翻转过来，变成 $4.321$ 并输出。

inputFormat: 一行一个浮点数

outputFormat: 一行一个浮点数


title: 【深基2.例8】再分肥宅水

description: 现在有 $t$ 毫升肥宅快乐水，要均分给 $n$ 名同学。每名同学需要 $2$ 个杯子。现在想知道每名同学可以获得多少毫升饮料（严格精确到小数点后 $3$ 位），以及一共需要多少个杯子。

inputFormat: 输入一个实数 $t$ 和一个正整数 $n$，使用空格隔开。

outputFormat:
输出两行。

第一行输出一个三位小数，表示可以获得多少毫升饮料。第二行输出一个正整数，表示一共需要多少个杯子。

hint: 对于所有数据，$0\leq t\leq 10000$ 且小数点后不超过 $3$ 位，$1\leq n\leq 1000$。


title: 【深基2.习2】三角形面积

description: 一个三角形的三边长分别是 $a$、$b$、$c$，那么它的面积为 $\sqrt{p(p-a)(p-b)(p-c)}$，其中 $p=\frac{1}{2}(a+b+c)$。输入这三个数字，计算三角形的面积，四舍五入精确到 $1$ 位小数。

inputFormat: 第一行输入三个实数 $a,b,c$，以空格隔开。

outputFormat: 输出一个实数，表示三角形面积。精确到小数点后 $1$ 位。

hint: 数据保证能构成三角形，$0\leq a,b,c\leq 1000$，每个边长输入时不超过 $2$ 位小数。


title: 【深基2.习6】Apples Prologue / 苹果和虫子

description: 小 B 喜欢吃苹果。她现在有 $m$（$1 \le m \le 100$）个苹果，吃完一个苹果需要花费 $t$（$0 \le t \le 100$）分钟，吃完一个后立刻开始吃下一个。现在时间过去了 $s$（$1 \le s \le 10000$）分钟，请问她还有几个完整的苹果？

inputFormat: 输入三个**非负整数**表示 $m, t, s$。

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

hint: 如果你出现了 RE，不如检查一下被零除？


title: 【深基3.例2】数的性质

description:
一些整数可能拥有以下的性质：

- 性质 1：是偶数；
- 性质 2：大于 $4$ 且不大于 $12$。

小 A 喜欢这两个性质同时成立的整数；Uim 喜欢这至少符合其中一种性质的整数；小 B 喜欢刚好有符合其中一个性质的整数；正妹喜欢不符合这两个性质的整数。现在给出一个整数 $x$，请问他们是否喜欢这个整数？

inputFormat: 输入一个整数 $x(0\le x \le 1000)$

outputFormat: 输出这 $4$ 个人是否喜欢这个数字，如果喜欢则输出 `1`，否则输出 `0`，用空格分隔。输出顺序为：小 A、Uim、小 B、正妹。


title: 【深基3.例3】闰年判断

description:
输入一个年份，判断这一年是否是闰年，如果是输出 $1$，否则输出 $0$。

$1582$ 年以来，闰年的定义：

普通闰年：公历年份是 $4$ 的倍数，且不是 $100$ 的倍数的，为闰年（如 $2004$ 年、$2020$ 年等就是闰年）。

世纪闰年：公历年份是整百数的，必须是 $400$ 的倍数才是闰年（如 $1900$ 年不是闰年，$2000$ 年是闰年）。

inputFormat: 输入一个正整数 $n$，表示年份。

outputFormat: 输出一行。如果输入的年份是闰年则输出 $1$，否则输出 $0$。

hint: 数据保证，$1582 \leq n \leq 2020$ 且年份为自然数。


title: 【深基3.例4】Apples

description: 小 B 喜欢吃苹果。她今天吃掉了 $x$ 个苹果。英语课上学到了 apple 这个词语，想用它来造句。如果她吃了 1 个苹果，就输出 `Today, I ate 1 apple.`；如果她没有吃，那么就把 1 换成 0；如果她吃了不止一个苹果，别忘了 `apple` 这个单词后面要加上代表复数的 `s`。你能帮她完成这个句子吗？

inputFormat: 输入一行一个自然数 $x$，表示吃掉的苹果数。

outputFormat: 根据题目要求输出。

hint: 对于所有数据，$0\le x \le 100$。


title: 【深基3.例5】洛谷团队系统

description: 在洛谷上使用团队系统非常方便的添加自己的题目。如果在自己的电脑上配置题目和测试数据，每题需要花费时间 $5$ 分钟；而在洛谷团队中上传私有题目，每题只需要花费 $3$ 分钟，但是上传题目之前还需要一次性花费 $11$ 分钟创建与配置团队。现在要配置 $n$ 道题目，如果本地配置花费的总时间短，请输出 `Local`，否则输出 `Luogu`。

inputFormat: 输入一个正整数 $n$，表示需要配置的题目量。

outputFormat: 输出一行，一个字符串。如果本地配置花费的总时间短，请输出 `Local`，否则输出 `Luogu`。

hint: 数据保证 $1 \leq n\leq 100$。


title: 【深基3.例7】肥胖问题

description:
BMI 指数是国际上常用的衡量人体胖瘦程度的一个标准，其算法是 $\dfrac{m}{h^2}$，其中 $m$ 是指体重（千克），$h$ 是指身高（米）。不同体型范围与判定结果如下：

- 小于 $18.5$：体重过轻，输出 `Underweight`；
- 大于等于 $18.5$ 且小于 $24$：正常体重，输出 `Normal`；
- 大于等于 $24$：肥胖，不仅要输出 BMI 值（使用 `cout` 的默认精度），然后换行，还要输出 `Overweight`；

现在给出体重和身高数据，需要根据 BMI 指数判断体型状态并输出对应的判断。

对于非 C++ 语言，在输出时，请四舍五入保留六位**有效数字**输出，如果小数部分存在后缀 $0$，不要输出后缀 $0$。

请注意，保留六位**有效数字**不是保留六位小数。例如 $123.4567$ 应该输出为 $123.457$，$5432.10$ 应该输出为 $5432.1$。

inputFormat:
共一行。

第一行，共 $2$ 个浮点数，$m, h$，分别表示体重（单位为 kg），身高（单位为 m）。

outputFormat: 输出一行一个字符串，表示根据 BMI 的对应判断。特别地，对于 `Overweight` 情况的特别处理请参照题目所述。

samples:
70 1.72
Normal

hint: 对于所有数据，$40\le m \le 120$，$1.4 \le h \le 2.0$。$m$ 和 $h$ 的小数点后不超过三位。


title: 【深基3.例8】三位数排序

description: 给出三个整数 $a,b,c(0\le a,b,c \le 100)$，要求把这三位整数从小到大排序。

inputFormat: 输入三个整数 $a,b,c$，以空格隔开。

outputFormat: 输出一行，三个整数，表示从小到大排序后的结果。


title: 【深基3.例9】月份天数

description: 输入年份和月份，输出这一年的这一月有多少天。需要考虑闰年。

inputFormat: 输入两个正整数，分别表示年份 $y$ 和月数 $m$，以空格隔开。

outputFormat: 输出一行一个正整数，表示这个月有多少天。

hint: 数据保证 $1583 \leq y \leq 2020$，$1 \leq m \leq 12$。


title: 【深基3.习8】三角形分类

description:
给出三条线段 $a,b,c$ 的长度，均是不大于 $10000$ 的正整数。打算把这三条线段拼成一个三角形，它可以是什么三角形呢？

- 如果三条线段不能组成一个三角形，输出`Not triangle`；
- 如果是直角三角形，输出`Right triangle`；
- 如果是锐角三角形，输出`Acute triangle`；
- 如果是钝角三角形，输出`Obtuse triangle`；
- 如果是等腰三角形，输出`Isosceles triangle`；
- 如果是等边三角形，输出`Equilateral triangle`。

如果这个三角形符合以上多个条件，请按以上顺序分别输出，并用换行符隔开。

inputFormat: 输入 3 个整数 $a$、$b$ 和 $c$。

outputFormat: 输出若干行判定字符串。

samples:
Acute triangle
Isosceles triangle
Equilateral triangle

samples:
3 4 5
Right triangle

samples:
1 14 5
Not triangle

hint:
当两短边的平方和大于一长边的平方，说明是锐角三角形。

当两短边的平方和等于一长边的平方，说明是直角三角形。

当两短边的平方和小于一长边的平方，说明是钝角三角形。


title: 【深基4.例2】找最小值

description: 给出 $n$ 和 $n$ 个整数 $a_i$，求这 $n$ 个整数中最小值是什么。

inputFormat:
第一行输入一个正整数 $n$，表示数字个数。

第二行输入 $n$ 个非负整数，表示 $a_1,a_2 \dots a_n$，以空格隔开。

outputFormat: 输出一个非负整数，表示这 $n$ 个非负整数中的最小值。

hint: 数据保证，$n\le100$ 且 $0\le a_i \le 1000$。


title: 【深基4.例3】分类平均

description:
给定 $n$ 和 $k$，将从 1 到 $n$ 之间的所有正整数可以分为两类：A 类数可以被 $k$ 整除（也就是说是 $k$ 的倍数），而 B 类数不能。请输出这两类数的平均数，精确到小数点后 $1$ 位，用空格隔开。

数据保证两类数的个数都不会是 $0$。

inputFormat: 输入两个正整数 $n$ 与 $k$。

outputFormat: 输出一行，两个实数，分别表示 A 类数与 B 类数的平均数。精确到小数点后一位。

hint: 数据保证，$1 \leq n\leq 10000$，$1 \leq k \leq 100$。


title: 【深基4.例4】一尺之棰

description: 《庄子》中说到，“一尺之棰，日取其半，万世不竭”。第一天有一根长度为 $a$ 的木棍，从第二天开始，每天都要将这根木棍锯掉一半（每次除 $2$，向下取整）。第几天的时候木棍的长度会变为 $1$？

inputFormat: 输入一个正整数 $a$，表示木棍长度。

outputFormat: 输出一个正整数，表示要第几天的时候木棍长度会变为 $1$。

hint: 数据保证，$1 \le a\le 10^9$。


title: 【深基4.例6】数字直角三角形

description: 给出 $n$，请输出一个直角边长度是 $n$ 的数字直角三角形。所有数字都是 $2$ 位组成的，如果没有 $2$ 位则加上前导 $0$。

inputFormat: 输入一个正整数 $n$。

outputFormat: 输出如题目要求的数字直角三角形。

hint: 数据保证，$1\le n\le13$。


title: 【深基4.例11】数列求和

description: 计算 $1+2+3+\cdots+(n-1)+n$ 的值，其中正整数 $n$ 不大于 100。由于你没有高斯聪明，所以你不被允许使用等差数列求和公式直接求出答案。

inputFormat: 输入一个正整数 $n$。

outputFormat: 输出一个正整数，表示最后求和的答案。

hint: 数据保证，$1 \leq n \leq 100$。


title: 【深基4.例13】质数口袋

description:
小 A 有一个质数口袋，里面可以装各个质数。他从 $2$ 开始，依次判断各个自然数是不是质数，如果是质数就会把这个数字装入口袋。

口袋的负载量就是口袋里的所有数字之和。

但是口袋的承重量有限，装的质数的和不能超过 $L$。给出 $L$，请问口袋里能装下几个质数？将这些质数从小往大输出，然后输出最多能装下的质数的个数，数字之间用换行隔开。

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

outputFormat: 将这些质数从小往大输出，然后输出最多能装下的质数个数，所有数字之间有一空行。

hint: 数据保证，$1 \le L \le {10}^5$。


title: [GZOI2017] 配对统计

background: GZOI2017 D1T3

description:
给定 $n$ 个数 $a_1,\cdots,a_n$。

对于一组配对 $(x,y)$，若对于所有的 $i=1,2,\cdots,n$，满足 $|a_x-a_y|\le|a_x-a_i|(i\not=x)$，则称 $(x,y)$ 为一组好的配对（$|x|$ 表示 $x$ 的绝对值）。

给出若干询问，每次询问区间 $[l,r]$ 中含有多少组好的配对。

即，取 $x,y$（$l\le x,y\le r$ 且 $x\not=y$），问有多少组 $(x,y)$ 是好的配对。

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

第二行 $n$ 个数 $a_1,\cdots,a_n$。

接下来 $m$ 行，每行给出两个数 $l,r$。

outputFormat: $Ans_i$ 表示第 $i$ 次询问的答案，输出 $\sum_{i=1}^m\limits Ans_i\times i$ 即可。

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

第一次询问好的配对有：$(1,2)(2,1)$；

第二次询问好的配对有：$(1,2)(2,1),(1,3)(3,1)$；

答案 $=2\times 1+4\times 2=10$。

**【数据约束】**

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