title: [语言月赛202302] 大碗宽面

type: B

background: 扶苏和她的朋友们在 Impart 酒店开派对。

description:
算上扶苏，本次派对共有 $n$ 个人。但是，并不是任何两个人都互相认识，并且互相认识的人关系也未必好。

具体而言，任意两个人可能是如下三种关系之一：
1. 敌人
2. 朋友
3. 陌生人

派对的一大重要活动是相互握手。对任意两个人 $u,v$，他们之间的握手情况遵循下面的规则：
1. 如果 $u$ 和 $v$ 是朋友关系，那么他们一定握手一次。
2. 如果 $u$ 和 $v$ 是敌人关系，那么他们一定**不**握手。
3. 如果 $u$ 和 $v$ 是陌生人关系，且存在一个人 $w$，使得 $w$ 是 $u$ 和 $v$ 之一的朋友，同时是 $u,v$ 中另一人的敌人，则 $u$ 和 $v$ **不会**握手，否则 $u$ 和 $v$ 一定握手一次。

对第三条规则，简单的说法是：一对陌生人之间，如果某一方的朋友是另一方的敌人，则不握手，否则握手。

已知共有 $p$ 对人是朋友关系，$q$ 对人是敌人关系。除了这 $p + q$ 对人，其他每对人均为陌生人关系。

请你求出本次派对一共握手了多少次。

inputFormat:
第一行是三个整数，依次表示参加派对的人数 $n$，朋友关系的条数 $p$ 和敌人关系的条数 $q$。
接下来 $p$ 行，每行两个整数 $u,v$，表示 $u$ 和 $v$ 是朋友关系。
接下来 $q$ 行，每行两个整数 $u, v$，表示 $u$ 和 $v$ 是敌人关系。

outputFormat: 输出一行一个整数，表示本次派对的握手次数。

hint:
### 样例 1 解释

共有 $(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$ $6$ 对人。
- $(1,2)$ 是朋友，握手。
- $(1,3)$ 是敌人，不握手。
- $(1,4)$ 是敌人，不握手。
- $(2,3)$ 是朋友，握手。
- $(2,4)$ 是陌生人，但是 $1$ 是 $2$ 的朋友，也是 $4$ 的敌人，所以不握手。
- $(3,4)$ 是陌生人，但是不存在任何一个人既是 $3$ 和 $4$ 之一的敌人也是另一个人的朋友，故握手。

综上，一共握手 $3$ 次。

### 数据规模与约定

以下设 $m = p + q$，即 $m$ 是朋友和敌人关系条数之和。

- 对 $20\%$ 的数据，保证 $m = 0$。
- 对 $50\%$ 的数据，保证 $n, m \leq 100$。
- 对 $70\%$ 的数据，保证 $n, m \leq 10^3$。
- 对 $100\%$ 的数据，保证 $2 \leq n \leq 3 \times 10^4$，$1 \leq u, v \leq n$，$0 \leq p,q \leq m \leq 10^3$，$u \neq v$。同一对敌人或朋友关系不会出现两次，不会有一对人同时是敌人或朋友关系。

### 提示

- 本题的空间限制为 $2 \mathrm{GiB}$。这一空间限制意味着你可以在程序中开出不超过 $2147483648(>2 \times 10^9)$ 个 bool 或 char 的数组。**注意，开不下同样大小的 int 数组**。
- 请注意空间限制是你程序运行时所使用的空间峰值，其中还包括了函数压栈、其他变量等空间占用。所以请不要卡着上限开数组。
- 如果你开出了过大的数组，可能会导致编译错误。此时请酌情减小你的数组大小。
- 对于某些 32 位系统，或可用内存过少的系统，直接开出大小约为 2GB 的数组可能无法编译或无法运行。可以先把数组开小来测试样例，提交时再改回符合数据范围的数组，也可以使用洛谷在线 IDE 来测试样例。洛谷评测机保证可以正常评测。


title: kls与flag

type: P

background: kls毒奶非常厉害。

description:
有$n$个OI选手，每个人插了一个flag。有一天因为某种原因，flag都被触发了，所以地上有一排$n$根竹竿，竹竿的间距均为一个单位长度，高度在$1\sim m$之间。

kls看到这些竹竿，感觉不好看，于是准备把它们全部放倒。

在这之前，kls想到了一个数学问题。每根竹竿可以往左倒或者往右倒。如果两根竹竿在选择方向放倒之后，它们的顶端可以重合，那么称它们是优秀的。现在kls想要知道，有多少对竹竿是优秀的。

inputFormat:
第一行两个数$n,m$，表示竹竿的个数和最大高度。

第二行$n$个正整数，表示每根竹竿的高度。

outputFormat: 输出一行，只有一个数，表示有多少对竹竿是优秀的。

hint:
### 样例解释

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

- 1号和2号向左倒可以顶端重合
- 4号和5号向右倒可以顶端重合
- 1号向右，5号向左可以顶端重合

### 数据范围

对于30%的数据，满足$n\le 2000$，$m\le 5000$；

对于60%的数据，满足$n\le 200000$，$m\le 500000$；

对于100%的数据，满足$n \le 200000$，$m \le 10^9$。


title: 序列

background: # 本题数据已更新

description:
给定两个长度为 $n$ 的序列 $A$ 和 $B$，定义序列 $C_i=\max\limits_{j=1}^i A_j$。

定义当前的价值是 $\prod\limits_{i=1}^n \min(B_i,C_i)$。

现在有 $q$ 次操作，每次操作将会修改序列 $A$ 或者 $B$ 中的一个位置，将会把数字变大。现在请求出每次修改之后的价值。

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

第二行 $n$ 个整数表示 $A_i$。

第三行 $n$ 个整数表示 $B_i$。

接下来 $q$ 行，每行三个整数 $opt,x,y$，如果 $opt=0$ 表示对序列 A 操作，如果 $opt=1$ 则是对序列 $B$ 操作，把序列中第 $x$ 个元素变成 $y$，保证 $y$ 不小于原来的元素。

outputFormat:
输出 $q$ 行，表示每次修改之后的价值。

由于答案很大，请对 $10^9+7$ 取模后输出。

hint:
对于所有数据，满足 $1 \le n,q\le 10^5,0\le A_i,B_i,y \le 10^9$。

对于 20% 的数据范围，满足 $1\le n,q\le 1000$

对于另外 10% 的数据范围，满足 $opt=1$

对于另外 20% 的数据范围，满足 $opt=0$

对于 80% 的数据范围，满足 $n,q\le 50000$


title: 八月脸

background:
Cdm1020 十分喜欢 August-soft 出品的游戏，在游玩 august 社历届作品的时候他突然发现了一些神奇的事实。

**那就是所有的人物立绘的脸都是一样的!**

![](https://i.loli.net/2018/09/17/5b9fb47a8b3e0.gif)

不过尽管如此，作为一名资深的八月厨，他依然可以敏锐的分辨出各张立绘之间的细微差异 ~~（并不，就是同一张脸有什么好分辨的）~~，为了进一步研究八月社的立绘水平，Cdm1020 将八月社的所有立绘都放到了一颗树上 ~~（什么鬼啊）~~

（如果你不知道什么是树的话，你可以将树理解为一个无环的无向连通图）

具体来讲树上的每个节点仅保存了一张八月社的立绘，Cdm1020 通过和他的八月厨朋友们交流发现，狂热程度不同的八月厨对于同一张立绘的喜爱程度是不一样的，具体来讲每张立绘有两个属性 $a$ 和 $b$，对于一个狂热指数为 $k$ 的八月厨来讲，他对一张属性为 $(a,b)$ 的立绘的喜爱程度为 $ka+b$。

现在 Cdm1020 想要带领他的 $m$ 个狂热指数不同的朋友参观八月社的立绘（们），他希望你对于他的每一个朋友，帮他规划出一条喜爱程度之和最大的游览路线。

当然这个问题很简单，他是不会拿来烦你的。现在他真正头疼的事情是八月社新来了一个画师夏野。他的朋友们现在闹腾着想要看八月社的新立绘 ~~（反正还是一张脸有什么好看的）~~，所以他规定你的路线必须从一张属于 b 叔的立绘开始，到一张属于夏野的立绘结束，你能帮帮他吗？

description:
**请忽略上面的鬼话，就当什么也没看见**

一句话题意，给定一颗 $n$ 个点的树，树上每个点不是黑色就是白色，每个点有两个属性 $a$ 和 $b$。

现在多组询问，每次询问仅给出一个参数 $k$，要求你从树上找出一条路径 $(u,v)$ 使得 $u$ 和 $v$ 的颜色不同并且

$$k\times \sum_{p \in path (u-v)}p.a+\sum_{p\in path(u-v)}p.b$$

最大，对于每个询问你仅需要输出这个最大值即可（式子里面的两个和式的意思分别是路径上的点 $a$ 属性之和和路径上点的 $b$ 属性之和）。

**tips: $a,b,k$ 均可正可负，并且我们不允许你不选路径，也就是说我们求出的的最大值可以是一个负数，这会发生在所有合法路径的权值都是负数的时候**。

inputFormat:
第一行两个正整数 $n,m$ 表示树的节点个数和询问次数。

接下来一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个点的 $a$ 属性的值。

接下来一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个点的 $b$ 属性的值。

接下来一行 $n$ 个整数，每个数要么为 $0$ 要么为 $1$，第 $i$ 个数为 $0$ 表示第 $i$ 个点是一个白色点，为 $1$ 表示第 $i$ 个点是一个黑色点。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示存在一条从点 $u$ 到点 $v$ 的边。

接下来 $m$ 行，每行一个整数 $k$ 表示询问的参数。

outputFormat: 输出 $m$ 行，对于每一个询问，输出题目中给出式子的最大值。

hint:
$2 \leq n\leq 10^5$，$1 \leq m \leq 10^5$，$-10^8 \leq k \leq 10^8 $

保证不会存在所有点都是黑色或者都是白色的数据，保证对于树上的任意路径，路径上点的 $a$ 属性之和的绝对值不超过$1.5×10^9$，路径上点的 $b$ 属性之和的绝对值不超过 $1.5×10^9$。


title: [Cnoi2019] 雪松果树

background:
幻想乡，冬。

一年一度，生长在高山上的雪松果树又结果了。

Cirno 不知从哪弄到了 $1,2,3\cdots9$ 颗雪松果,然后很开心的吃掉了其中 $6$ 颗，最后还剩最后 $1$ 颗。

Cirn o因为以后吃不到雪松果而感到忧愁,于是决定种在美丽的雾之湖畔。

第一天,发芽。

第二天,雪松果树长成了一颗参天大树, 上面长满了雪松果。

Cirno 在雪松果成熟之前早有一些问题想知道，但现在她忙于收集雪松果，就把问题丢给了你。

description:
雪松果树是一个以 $1$ 为根有着 $N$ 个节点的树。

除此之外, Cirno还有 $Q$ 个询问，每个询问是一个二元组 $(u,k)$ ,表示询问 $u$ 节点的 $k$-cousin 有多少个。

我们定义:

> 节点 $u$ 的 $1$-father 为 路径 $(1, u)$ （不含 u）上距 u 最近的节点
>
> 节点 $u$ 的 $k$-father 为 节点 「$u$ 的 $(k-1)$-father」 的 1-father
>
> 节点 $u$ 的 $k$-son 为所有 $k$-father 为 $u$ 的节点
>
> 节点 $u$ 的 $k$-cousin 为 节点「 $u$ 的 $k$-father」的 $k$-son (不包含 $u$ 本身)

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

第二行, $N-1$ 个整数，第 $i$ 个表示 $i+1$ 号节点的 1-father

以下 $Q$ 行，每行一个二元组$(u,k)$

outputFormat: 一行，$Q$ 个数，每一个表示一个询问的答案。若 u 不存在 k-father，输出 0。


title: 天守阁的地板

background:
在下克上异变中，博丽灵梦为了找到异变的源头，一路打到了天守阁。

异变主谋鬼人正邪为了迎击，将天守阁反复颠倒过来，而年久失修的天守阁也因此掉下了很多块地板。

异变结束后，恢复了正常大小的小碗回到了天守阁，想要修复这里的地板，她需要知道自己要采购的地板数量(一个惊人的数字)，于是，她找到了精通 $\text{OI}$ 的你来帮忙。

description:
为了使万宝槌能发挥出全部魔力，小碗会将买来的地板铺满一个**任意**边长的正方形(地板有图案，因此**不允许旋转**，当然，地板也**不允许重叠**)来达到最大共鸣。

在每一次购买中，小碗只能买到一种规格为 $a*b$ 的地板，为了省钱，她会在满足能摆成正方形的前提下购买尽可能少的地板。

现在，她想知道对于每一对 $a,b(1≤a,b≤n)$ ，她最少需要购买的地板数量。当然，由于输出可能很大，你只需要输出所有答案的乘积对 `19260817` 取模后的结果即可。

inputFormat:
第一行一个整数 $\text{T}$ ，表示数据组数

下面 $\text{T}$ 行，每行一个整数 $n$

outputFormat: 共 $\text{T}$ 行，每行一个整数，表示取模后的答案


title: 子异和

description:
小L和小K正在激烈地讨论着。

（你不用知道谁说的哪句话……）

“你知道非空子集吗？”

“当然知道啊！比如说集合$\{1,2,3\}$，它的所有非空子集就是$\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}$。”

“那你知道每个非空子集里的数的亦或和是多少吗？”

“也知道啊，不就是$1,2,3,1⊕2=3,2⊕3=1,1⊕3=2,1⊕2⊕3=0$吗。”

“那你知道它们的和是多少吗？我们把它叫做子异和。”

“子异和……这个名字好奇怪啊，不过我知道，是$1+2+3+3+1+2+0=12$。”

“那我问你，$\{a_1,a_2,...,a_n\}$的子异和是多少？”

“慢慢暴力算呗！”

“如果$n\le 200000$呢？”

“……”

“如果把问题放在一颗树上呢？”

“……那你会不会做啊？”

“当然……不会做……”

现在，只有你能帮助小L和小K了，请你帮忙解决这个问题。

**为了更清晰的表达题意，我们再做一次解释。**

有一个$n$个节点的树，总共有$m$次操作。这些操作按照操作顺序输入。每次操作可能是询问或修改。

每次询问操作会给出两个节点编号$a,b$。根据常识，$a,b$在树上有唯一路径。我们设这条路径经过的所有点的点权集合为$S$。你要输出$S$的子异和。答案$mod\space(10^9+7)$。

每次修改操作会给出两个节点编号$a,b$与一个整数值$c$。你要将节点$a$到节点$b$的唯一路径上的所有点的点权分别异或$c$。

**这里的集合指可重集合**

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

接下来$n-1$行，每行两个正整数$a,b$，表示节点$a$和$b$之间有一条边。不会出现重边与自环。

接下来一行$n$个非负整数，第$i$个非负整数表示$i$节点的初始点权。

接下来$m$行，每行若干个整数，表示$m$个操作的信息。每行第一个整数只可能是$1$或$2$。如果是$1$，则此操作为询问，接下来两个数为$a,b$；如果是$2$，则此操作为修改，接下来三个数为$a,b,c$。

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


title: 最后的战役

background:
NOIP2018原创模拟题T5

NOIP2018原创模拟赛DAY2 T1

NOIP T1+ or T2-  难度

题目背景改编自小说《哈利波特与死亡圣器》

description:
**最后的战役打响了。**

哈利被宣告“死亡”，伏地魔带着他的部下准备进攻霍格沃茨。但是霍格沃茨有古老的魔法保护，他们必须先摧毁这些保护。魔法保护一共有$n$层，每一层保护有两个参数：$k,p$。其中k表示魔法的类型，p表示能量的大小。

伏地魔每秒都会穿过一层保护，他在第 $i$ 秒（到达了第 $i$ 层）他有以下选择：

1.收集 $[1,i]$ 层魔法中魔法类型为 $x_i$ 的魔法能量

2.收集 $[1,i]$ 层中魔法能量最大那层的魔法能量

3.使用加倍魔法

对于上面三个选择，他每秒可以可以选择一个，并可能获得能量，对于不同的选择，获得的能量也不同：

对于1.获得$[1,i]$层中**所有魔法类型为$x_i$的**魔法能量（请结合样例1理解）

对于2.获得$[1,i]$中魔法能量最大的那一层的魔法能量

对于3.这一秒总共收集的能量不变（也就是这一秒不收集新的能量），但是下一秒获得的能量翻倍。**但是他不能连续使用加倍魔法**，而且他最多只能使用$m$次，**对于每一层的能量他都可以重复获取**

只有他通过了这$n$层保护，并获得了最大的魔法能量才有可能彻底摧毁霍格沃茨的魔法防御，可是巫师又是不擅长计算的。

于是，伏地魔找到了你，而你，作为精通计算机技术的麻瓜程序员，现在需要做的就是设计一个程序帮助伏地魔计算出他可以获得的最大的魔法能量的值。

最终的决战已经展开，魔法界的历史又翻过了一页……

inputFormat:
第一行：两个数：$n,m$，意义见题目描述

接下来$n$行，第$i+1$行表示$k_i,p_i$，意义见题目描述

最后一行，共$n$个数，第$i$个数表示$x_i$，意义见题目描述

outputFormat: 一个数，表示伏地魔可以获得的最大能量值

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

第一秒最多可以获得2经验值，第二秒最多可以获得3经验值，**因为第三秒可以收集魔法类型为1的能量，所以最多可以获得4能量值**，第四秒最多可以获得8经验值，所以选择在第三秒使用加倍魔法，共可以获得：$2+3+0+2*8=21$能量值

**数据范围：**

30%数据满足：$n<=100,m<=10$

50%数据满足：$n<=5,000,m<=20$

70%数据满足：$n,m<=2\times 10^4,m<=200$

100%数据满足：$n<=5\times 10^4,m<=500,0<p_i<=10^4,0<k_i<=10^9,0<x_i<=10^9$

**特殊约定：**

30%数据满足$m=0$


title: Marisa采蘑菇

background: $\text {Marisa}$ 是一个爱魔法的女孩子，而火力高而华丽的八卦炉正是她常用的武器，随着时代的进步，$\text {Marisa}$ 也想要升级她的八卦炉的火力，所以她决定去魔法森林采蘑菇来获得做实验的材料

description:
$\text {Marisa}$ 来到了森林之中，看到了一排 $n$ 个五颜六色的蘑菇，这些蘑菇的颜色分别为 $a_1,a_2,...,a_n$ 。由于她很挑剔，所以她只会采那些"魔法蘑菇" 。

一个蘑菇被叫做"魔法蘑菇"，当且仅当它**在给定的某段区间内**，并且在这段给定区间内与它颜色相同的蘑菇(包括它本身)的个数，与在这个给定区间外这种颜色的蘑菇的个数之差小于等于给定的常数 $k$

现在 $\text {Marisa}$ 会做出 $m$ 个询问,每次询问你 $[l,r]$ 中有多少种不同颜色的"魔法蘑菇"

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

第二行 $n$ 个正整数，表示蘑菇的颜色 $a_i$

之后 $m$ 行，每行两个正整数 $l_i,r_i$ ，表示 $\text{Marisa}$ 询问区间的左端点和右端点，数据保证 $0<l≤r≤n$

outputFormat: 共 $m$ 行，每行一个整数 $x$ ，表示询问区间中**不同颜色**的"魔法蘑菇"的种数


title: 断罪者

background:
**重阳节**的地狱……

四季映姬·亚玛萨那度（以下简称四季大人）是地狱的最高裁判长，她平时负责给死者定罪，判断让死者去地狱还是天界，或者别的什么地方。

四季大人当然可以轻松地给死者断罪，但是死者太多了，四季大人需要你帮她断罪，以便腾出时间让她对别人进行说教。

description:
人们的罪恶值$E$由人们**生前所做过的事**和他的**死亡方式**来决定。他们做过的**坏事**都会有一个罪恶值，这些坏事有可能会并入同一个集合，一个集合的罪恶值为该集合中罪恶值最大的坏事的罪恶值，而他们一生做过的事会**互相影响**，我们将他们生前做过的事分为4种，而最后的罪恶值$E$由其中**所有集合的罪恶值的和**决定。

1. 做坏事——有罪恶值，单独为一集合。
2. 做好事——将一件坏事的罪恶值清零。
3. 忏悔——将指定集合中，最大罪恶值的事罪恶值减少。
4. 认清自己——将两个坏事集合合并。

而死亡方式可分为 *自然死亡* 、*事故死亡* 和 *自杀* 。

1. 自然死亡，没什么影响。
2. 事故死亡，可以免除最大罪恶的坏事集合。
3. 自杀，最大的坏事集合罪恶值翻倍。

inputFormat:
第一行三个输入 $T,W,K$，代表有 $T$ 个人等待断罪，$W$ 为死亡方式，与描述序号对应，$K$ 含义见输出格式。

接下来的 $T$ 组数据，每组数据第一行两个输入 $n,m$，代表他做过的坏事数量和其他事的数量。

第二行 $n$ 个输入，代表每件坏事的罪恶值。

第 $3$ 到第 $m+2$ 行，每行有三种输入可能。（请联系题目描述进行理解）

- $\verb!2 A!$：表示做好事，将坏事 $A$ 罪恶值**清零**。
- $\verb!3 A B!$：表示忏悔，指定集合为 $A$ 所在的集合，最大罪恶值的事减少 $B$，若最大罪恶值比 $B$ 小，则最大罪恶值的事罪恶值**清零**。**对于罪恶值相等的坏事，认为编号更小的更坏**。
- $\verb!4 A B!$： 表示认清自己，将 $B$ 所在集合与 $A$ 所在的集合合并。

outputFormat:
对于每一个人，一行输出一个字符串和一个整数。

若他的罪恶值为 $0$ 则输出 `Gensokyo`，若他的罪恶值大于 $K$ 则输出 `Hell`，否则输出 `Heaven`。再输出它的罪恶值。


title: Tweetuzki 爱取球

background: 本题为被指出的改编题……~~害怕被爆破~~

description:
Tweetuzki 有一个袋子，袋子中有 $N$ 个无差别的球。Tweetuzki 每次随机取出一个球后放回。求取遍所有球的期望次数。

取遍是指，袋子中所有球都被取出来过至少一次。

inputFormat: 一行一个整数 $N$ $(1 \le N \le 10^7)$。

outputFormat: 一行一个整数，表示期望次数。由于这个数可能很大，输出对 $20040313$ （是个质数）取模。

hint:
### 样例解释 1

第一次取出一个球即可取遍所有球。

### 样例解释 2

两次就取遍所有球的概率为 $\frac{1}{2}$，三次取遍所有球的概率为 $\frac{1}{4}$，四次取遍所有球的概率为 $\frac{1}{8}$，……，$k$ 次取遍所有球的概率为 $\frac{1}{2^{k-1}}$。故：

$$E(2) = \frac{2}{2} + \frac{3}{4} + \frac{4}{8} + \frac{5}{16} + \cdots = 3$$

### 样例解释 3

通过试验及计算可得：

$$E(3) = \frac{11}{2}$$

对 $20040313$ 取模后答案为 $10020162$。

## 数据范围及约定

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


title: 神秘的703

background: $Zero$ 和 $Mike$是一对热爱旅行的好朋友，一天在经历了$ZXG$大神的历练后，心力交瘁，于是决定**重阳节**回宾馆刷题，找回自信，于是，我们的故事开始了……

description:
**出题人：各位 $Oier$ 一定要细心啊啊啊！！！注意看说明**

**出题人：Chen_Xi.Naoh**

$Zero$ 所在宾馆的房间号是 $703$ ，而 $Mike$ 所在宾馆的房间好却是 $704$ ，所以当 $Zero$ 和 $Mike$ 想凑在一起刷题的时候，$Zero$ 需要从 $703$ 前往 $704$ 或者 $Mike$ 从 $704$ 前往 $703$ ，当 $Zero$ 和 $Mike$ 凑在一起时，$Mike$ 便会从[ $luogu$ ](https://www.luogu.org/)上随机选择 $n$ 道题，每一道题分值为 $300$ ，由于 $Mike$ 身经百战，所以每当 $Mike$ 看到某道题目的时候，大脑里面就会自动给该到题目定义一个难度值 $hard$ (要相信 $Mike$ 的判断都是正确的)，而 $Zero$ 和 $Mike$ 两个人都有一个共同的天赋值 $Talent$ ,每个人都只能解出 $Talent$ 范围内难度的题目，当然 $Zero$ 和 $Mike$ 的天赋值不会很低；

在 $Zero$ 的房间 $703$ 里面有一位热爱学习的小学弟 $BookCity$ ，在 $Zero$ 和 $Mike$ 刷题的同时，$BookCity$ 会在一旁研究两位学长的做题习惯，并给两位学长加油助威，由于 $BookCity$ 的加油，某道题目的难度就会自动下降一点点(**若 $hard - d \le 0$，则默认该题的 $hard$ 为 $1$ **)；然而，在宾馆的
 $123$ 号房间住着一个拥有魔法但心地邪恶的人 $Guy$ ，能够看到Zero和Mike的动静，并且能够施展魔法(因为是在**重阳节**)，在 $Zero$ 和 $Mike$ 做到某一题的时候，直接将该题的难度暴增至 $s$ 倍！！！！！幸运的是，$Zero$ 和 $Mike$ 的老师 $tingtime$ 会帮助他们两个，在困境的时候为 $Zero$ 和 $Mike$ 指点迷津，将某一题的难度直接调为一个很低的值。

$Zero$ 和 $Mike$ 每刷完一道题能获得对应分值的自信值( $Zero$ 和 $Mike$ 都是追求完美的人，每一道题要么对，要么干脆不写)，现在，你就是 $Zero$ ，你想知道如果和 $Mike$ 从第 $a$ 到题刷到第 $b$ 到题能回复多少自信值 (**自信值计算方法：$600*AC$ 题目个数 $\Longrightarrow$ 一道题 $300$ 分，$2$ 个人一共恢复 $600$ 自信值**)$Confidence$。

inputFormat:
第一行输入两个数，分别表示题目个数 $n$ 和天赋值 $Talent$。
第二行将输入 $n$ 个数，第 $i$ 个数表示第 $i$ 题的 $ hard$ 值。
第三行，输入一个数表示事件个数 $m$ ，
接下来的 $m$ 行中，每行一个合题意事件，严格保证所有事件按顺序发生。

outputFormat: 对于 $Zero$ 的每个询问，输出一行，回答他和 $Mike$（两个人） 能够获得的最大值$Confidence$。

samples:
5 5
2 3 4 5 9
5
BookCity 1 1
Guy 2 5
Zero 1 5
tingtime 5 1
Zero 1 5

hint:
保证所有题目初始的难度值 $hard$ 在 $ [0,2^{31}-1] $ 范围内；

保证 $Zero$ 和 $Mike$ 的天赋值 $Talent$ 在 $  [0,2^{31}-1] $ 范围内；

保证 $Zero$ 询问的范围都在 $ [0,2^{31}-1] $ 范围内，但不保证$x$一定会小于$y$

保证 $Guy$ 的翻倍都在 $ [0,2^{31}-1] $ 范围内；

保证 $BookCity$ 的减小值 $d$ 都在 $ [0,2^{31}-1] $ 范围内；

保证所有的输入数据都在 $  [0,2^{31}-1] $ 范围内；

$Mike$ 身经百战，所以其判断的 $hard$ 都在 $  [0,2^{31}-1] $ 范围内，且不存在难度为负数或者为 $0$ 的送分题；

保证 $n$ 和$m$ 都在 $  [0,2^{31}-1] $ 范围内；

对于 $30\%$ 的数据：$0\leqslant n \leqslant 5\times 10^3$,$m \leqslant 5\times 10^3$；

对于 $50\%$ 的数据：$0\leqslant n \leqslant 5\times 10^4$,$m \leqslant 5\times 10^4$；

对于 $100\%$ 的数据：$0\leqslant n\leqslant 5\times 10^5$，$m\leqslant 5\times 10^5$。

** 总之保证所有输入数据在$ [0,2^{31}-1] $范围内，但不保证运算在$ [0,2^{63}-1] $范围内！！**


title: 独钓寒江雪

description: 给定一棵无根树，求其中本质不同的独立集的个数。

inputFormat:
第一行：一个整数$n$，树上的结点数量（$n \leq 5\times 10^5$）

第二行到第$n$行：每行两个整数$u$和$v$，表示$u$和$v$连着一条边

outputFormat: 单个整数：输出方案数模$10^9+7$的余数


title: PION后缀自动机

background:
NOIP2018原创模拟题T6

NOIP2018原创模拟赛DAY2 T3

NOIP DAY1 T3+ or DAY2 T3 难度

鉴于 NOIP2017 DAY2 T3 的难度，就有了这道题。**然而这道题考察的知识并不是后缀自动机**

description:
小P是一个技术高超的程序员，他开发了一套自己的操作系统，称为PION系统，该系统与Windows和Linux有很大不同，目前他正在测试该系统。

PION系统与Windows系统最大的不同在于文件的储存与操作，POIN的文件夹没有父子之分。我们知道，在Windows系统中，可以在文件夹里新建子文件夹。但是，PION系统文件夹不分父子关系，**但是部分文件夹之间可以互相直接访问，我们称这种关系为互访关系，而且，对于一个有$n$个文件夹的系统来说，这种互访关系有$n-1$个，且保证所有文件夹均可以通过互访关系而互相访问。也就是说：我们可以把Windows中的文件夹的集合看作一棵有根树，而把PION系统中的文件夹集合看作为无根树。**

在PION系统中，每个文件夹都可以储存文件，和Windows一样，文件名包含后缀名。

现在小P正在构思一种可以对文件夹中文件后缀进行方便操作的交互式程序dmc，他也将其称为**PION后缀自动机**。由于他太忙了，所以他希望你帮他实现**部分功能**。

他希望你帮他实现三个功能：

1.计算两个文件夹之间的距离。我们定义：文件夹之间的距离为其中一个文件夹通过互访达到另一个文件夹最少互访次数。比如：同一个文件夹距离为0，两个有互访关系的文件夹距离为1。

2.计算两个文件夹路径之间（包含这两个文件夹）的文件夹中的文件的后缀名为A的文件数量，**其中A是一个小写字符串。提示：我们可以把PION文件夹之间的路径理解为树中两节点之间的路径。**

3.删除两个文件夹路径之间（包含这两个文件夹）的文件夹中的文件的后缀名为A的文件，并统计被删除文件的数量。

由于dmc是一个交互系统，所以我们用tab语言描述这三个操作：

```
query /p u v
```

表示操作一，其中 u,v 表示两文件夹的编号

```
query /e u v *.A
```

表示操作二，其中 u,v 表示两文件夹的编号，$'*'$ 为通配符，$'.'$用于分隔文件名与后缀，**A是一个小写字符串**。

```
del /e u v *.A
```

表示操作三， $u,v, *.A$ 意义与操作二相同。

**如果没有看懂题目请结合样例及样例解释来理解。**

最后，这个困难的任务就交给你了。

inputFormat:
第一行两个数，$n,m$，$n$表示文件夹的数量（文件夹编号在$[1,n]$），$m$表示操作的数量

接下来 $n-1$ 行，每行两个数 $u,v$，表示文件夹 $u,v$ 之间有互访关系

接下来 $n$ 行，第$i$行第一个数为 $k$，表示第$i$个文件夹有$k$个文件，接下来为$k$个字符串，表示每个文件的后缀名

再接下来$m$行，每行一串指令，格式见上文

outputFormat: 对于每个指令，输出一个数，输出数的意义见上文

samples:
5 5
1 2
2 4
2 5
1 3
2 cpp c
3 pas txt txt
2 vbs bat
3 vbs cpp pas
4 cpp c pas txt
query /e 1 5 *.txt
query /p 1 4
del /e 2 2 *.txt
query /e 1 5 *.txt
query /e 4 3 *.vbs

samples:
12 7
1 2
1 3
1 4
2 5
2 6
3 7
7 12
8 4
8 9
10 9
11 9
0
2 c c
3 zz c c
0
1 gif
2 png bmp
3 avl avl mpshi
0
4 cpp c pas js
5 a b c d e
0
3 a b c
query /p 11 12
query /e 1 2 *.gif
query /e 6 10 *.c
del /e 2 9 *.c
del /e 3 12 *.c
query /e 5 6 *.gif
query /e 6 1 *.c

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

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

如图为样例一大致结构，橙色方框为文件夹，灰色文字表示文件后缀名，红色线条表示文件互访关系。

对于第一个操作：文件夹1到5之间txt文件有3个所以输出3
对于第二个操作：文件夹1与4距离为2
对于第三个操作：删除的为文件夹2的文件，txt文件有两个，所以输出2
对于第四个操作：由于文件夹2的txt文件被删除了，所以1到5之间txt文件只有1个
对于第五个操作：文件夹3到4之间vbs文件有2个所以输出2

**数据范围：**

30%数据满足：$n,m<=100,k<=3$

50%数据满足：$n,m<=5000,k<=10$

70%数据满足：$n,m<=2 \times 10^4,k<=50$

90%数据满足：$n,m<=5 \times 10^4$

100%数据满足：$n,m<=10^5$，文件总数小于$5 \times 10^5$，文件后缀名为小写字符串且不超过6个字符

其他说明：

1.约50%的数据为完全随机生成

2.数据弱化版：[PION后缀自动机（数据弱化版）](https://www.luogu.org/problemnew/show/U41487)


title: 河童重工的计算机

background:
河童重工业会社的计算机产品在幻想乡中有着极其广泛的应用。

有一天，妖怪之山发大水啦！洪水夹杂着泥沙和滚木汹涌着冲进了河童的城市。

本来河童们的机械设施都是防水的，可是洪水还是对城市造成了不小的破坏。其中，河童们的服务器被砸坏了！

坏掉的电脑在短时间内不能修复，可是幻想乡里的许多事情都离不开河童们的服务器！河童们也很无奈，于是荷取找到了你！你作为一名优秀的信竞选手，决定帮助荷取，减轻服务器故障所带来的压力。

description:
你从荷取那里得到了一份纸质资料，扫描版在这里：

[Ktx-65式微处理器汇编语言规范文件.pdf](https://www.touhou-oi.tk/uploads/Ktx-65%E5%BC%8F%E5%BE%AE%E5%A4%84%E7%90%86%E5%99%A8%E6%B1%87%E7%BC%96%E8%AF%AD%E8%A8%80%E8%A7%84%E8%8C%83%E6%96%87%E4%BB%B6.pdf)

（若此网站无法打开，请在附件中下载）

（为什么说是扫描版呢，因为，你应该不能复制里面的文字）

以下这一段是汇编教程附带的示例：
```asm
[ progfunc.asm ]
[ Shows the function functionailties of the KTX-65 ALI ]

[main]
wint #line;    [output the current physical line number]
wch 13;        [putchar \r]
wch 10;        [putchar \n]
callfunc $Function1;
callfunc $Function2;
hlt;           [halt]

function $Function1;
rint %r1;      [read int]
add %r2 1 %r2; [loop contents]
lle %r2 %r1;   [loop conditions]
jif 2;         [end loop conditional jump]
wint %r2;      [output int]
wch 13;        [putchar \r]
wch 10;        [putchar \n]
ret;           [return]

function $Function2;
rint %r1;      [read int]
rint %r2;      [read int]
add %r1, %r2;  [add]
wint %val;     [output value]
wch 13;        [putchar \r]
wch 10;        [putchar \n]
ret;           [return]
```
你需要用洛谷评测机支持的语言编写一个程序，它读入一个Ktx-65汇编语言程序和一段输入，解释运行这个程序，然后输出这个程序输出的东西。

inputFormat:
第一行是一个整数N，表示汇编程序的行数。

接下来N行是这个汇编程序，保证不会出现空行。

接下来的所有行都是这个汇编程序的输入。

outputFormat:
一堆东西，表示这个汇编程序的输出。

~~**评测系统将以逐字节比较的方式判断你的输出是否正确。**~~假的，洛谷不支持

samples:
5
rint %r1;
rint %r2;
add %r1 %r2;
wint;
hlt;
5 4

hint:
**注意**：样例输出中只有9这一个字节。

**保证一行中只有一个指令。**

对于10%的数据：程序中只有输入和输出的指令，且不会出现数字常量，也不会有注释。

对于另外10%：程序中只有输入、输出和加法指令，且没有注释。

对于另外30%：包括除函数调用和跳转在内的所有指令。

对于剩下50%：指令没有限制。

对于全部的数据：命令条数不超过50000条，剩余输入不超过500千字节，程序需要执行的步数不超过80000步。

保证汇编程序和数据不出现编译或是运行时错误。

保证程序输入足够满足汇编程序中读入的需要。

不保证这是或不是一道毒瘤题

不保证考试时会不会有人AC这道题

不保证这次考试会不会有人AK

保证出题人为：[洩矢诹访子](https://www.luogu.org/space/show?uid=53151)

考试时打不开河童给的文件可以向我索要，不保证是否会回答

~~其实这道题数据非常简单，只是量大而已~~


title: FZOUTSY

description:
### 原始题意

cdm1020 是一名废宅，他平时最喜欢的事情就是水（复）群（读）。

他截取了他最近水的群的聊天记录，并且通过某种奥妙重重的压缩算法将这些聊天记录压缩成了一个长度为 $n$ 的字符串，因为他是一个中二社厨，所以这个字符串当中仅仅含有 $\mathtt{f,z,o,u,t,s,y}$ 这 $7$ 种字符，出于对后缀数据结构的狂热，他只对这个字符串的后缀感兴趣，他定义一个后缀的编号为 $i$，当且仅当它代表的字符串的区间为 $[i,n]$。

cdm1020 定义一对后缀 $(i,j)$ 是"$k$级复读的"当且仅当 $i$ 和 $j$ 的最长公共前缀的长度大于等于 $k$，换句话说一对$k$级复读的后缀也是 $k-1,k-2,k-3,\cdots,1,0$ 级复读的。

现在他想问你对于编号在 $(l,r)$ 中的后缀，有多少对后缀是 $k$ 级复读的。

### 一句话题意

给定一个长度为 $n$ 并且字符集为 $\mathtt{f,z,o,u,t,s,y}$ 的字符串和一个询问参数 $k$，多组询问 $(l,r)$ 求编号在 $(l,r)$ 间的后缀中，有多少对后缀的 LCP（最长公共前缀）长度大于等于 $k$。

定义一个后缀的编号为 $i$ 当且仅当这个后缀代表的是 $(i,n)$ 这段区间的字符。

inputFormat:
第一行三个正整数 $n,m,k$ 分别代表字符串的长度 $n$，询问次数 $m$ 和询问的参数 $k$。

第二行一个长度为 $n$ 的字符串表示你需要处理的字符串。

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

outputFormat: 输出 $m$ 行正整数，表示询问区间中 LCP 长度大于等于 $k$ 的后缀对数量。

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

对于全部数据，$1\leq l\leq r\leq n \leq 3×10^6$，$1\leq k \leq n \leq 3×10^6$，$1\leq m \leq 10^5$，$1 \leq n^2m \leq 10^{15}$。

保证输入的字符串中仅含 $\mathtt{f,z,o,u,t,s,y}$ 这 $7$ 种小写字母。


title: 【模板】最小割树（Gomory-Hu Tree）

background:
模板题。做本题之前请确保你会 Dinic 或 ISAP。如果你乱搞过了我请你抽烟。

根据惯例，网络流题不允许卡 Dinic/ISAP，但可以卡 EK，本题数据严格遵循上述条约。

description:
给定一个 $n$ 个点 $m$ 条边的无向连通图，多次询问两点之间的最小割。

两点间的最小割是这样定义的：原图的每条边有一个割断它的代价，你需要用最小的代价使得这两个点不连通。

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

接下来 $m$ 行，每行 $3$ 个数 $u,v,w$，表示有一条连接 $u$ 与 $v$ 的无向边，割断它的代价为 $w$。

接下来这一行有一个整数$Q$，表示询问次数

接下来 $Q$ 行，每行两个数 $u,v$，你需要求出 $u$ 与 $v$ 之间的最小割

**注意：因为数据有误，给定图的真实点数应该是 $n+1$ 个，编号为 $0$ 到 $n$。**

outputFormat: 输出共 $Q$ 行，每行一个整数对应询问的答案

hint: $1\le n\leq 500,\quad 0\le m\leq 1500,\quad 0\le Q\leq 10^5,\quad 0\leq w\leq 10^4,\quad u\neq v$


title: 信仰收集

background:
随着各种势力的迁入，守矢神社丧失了不少信仰

现在，为了挽回香火日益惨淡的神社，八坂神奈子派遣神社的风祝早苗去人类村落收集信仰

description:
你可以将村落看成一个 $m$ 个点的**有向无环图**，其中在某些点上有 $n$ 簇待收集的信仰(每一簇都有一定的数量)，图中有 $k$ 条有向边，每条边的长度均为 $1$ 。

早苗会从图中的 $1$ 号点出发，在图中的任意一个点停止收集，当早苗在一个有信仰的点的时候，她会将这个点所有的信仰全部收集(包括 $1$ 号点)。

为了方便，早苗从宇佐见堇子那里学会了瞬移，所以她可以一次移动 $a$ 个单位长度(称为小瞬移)，也可以一次移动 $b$ 个单位长度(称为大瞬移)，分别会花费 $w_a,w_b$点灵力，保证 $a≤b$ ，但由于幻想乡不能被常识所束缚，所以 $w_a$ 不一定小于 $w_b$ 。

现在，早苗希望你能帮她求出她在村落中能获得的(信仰数量-灵力耗费)的最大值。

inputFormat:
第一行三个整数 $n,m,k$ ，表示有信仰的点的数量，点的总数，有向边的条数

第二行两个整数 $a,b$ ，表示两种瞬移的距离

第三行两个整数$w_a,w_b$，表示两种瞬移的灵力消耗

之后 $n$ 行，每行两个正整数 $pos,t$ ，表示每簇信仰所在的位置以及这簇信仰的数量，**不保证** $pos$ 互不相同

之后 $k$ 行，每行两个整数$u,v$，表示从 $u$ 结点指向 $v$ 结点的一条有向边

outputFormat: 共一行一个整数 $x$ ，表示(信仰数量-灵力耗费)的最大值

hint:
#### 样例解释:

图如下所示:
![](https://cdn.luogu.com.cn/upload/pic/34550.png)

其中 $2$ 号点有 $2$ 信仰， $4$ 号点有 $3$ 信仰， $6$ 号点有 $4$ 信仰。

早苗可以瞬移 $1$ 或 $2$ 条边的距离，花费分别为 $3,2$

最优的方案之一是从 $1$ 花费$2$ 瞬移到 $6$ ，收集了 $6$ 号点的 $4$ 点信仰后停止收集，信仰-消耗 $=2$

#### 数据范围:

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


title: Tweetuzki 爱序列

background: 本题为改编题

description:
Tweetuzki 有一个长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$。

他希望找出一个最大的 $k$，满足在原序列中存在一些数 $b_1, b_2, \cdots, b_k$（可打散在原序列中的顺序），满足对于任意的 $i(1 \le i < k)$，$b_i \div 3 = b_{i+1}$（这时 $b_i$ 必须能够被 $3$ 整除）或 $b_i \times 2 = b_{i+1}$。并输出这个序列。

inputFormat:
第一行一个正整数 $n(2 \le n \le 10^5)$，表示序列的长度。
第二行包含 $n$ 个正整数，$a_1, a_2, \cdots, a_n(1 \le a_i \le 3 \times 10^{18})$，描述这个数列。

outputFormat:
第一行一个正整数 $k$，表示最大的 $k$。
第二行 $k$ 个正整数 $b_1, b_2, \cdots, b_n$，描述你选择的数。


title: 大奔的方案

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

五个海盗抢到了 $100$ 个金币，每一颗都一样的大小和价值连城。

他们决定这么分：

1. 抽签决定自己的号 $[1, 2, 3, 4, 5]$；
2. 首先，由 $1$ 号提出分配方案，然后大家 $5$ 人进行表决，当且仅当不少于半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
3. 如果 $1$ 号死后，再由 $2$ 号提出分配方案，然后大家 $4$ 人进行表决，当且仅当不少于半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
4. 以此类推……

每个海盗都是很聪明的人，他们遵循如下原则：

1. 保命；
2. 如果满足条件 $1$，那么想办法获得更多的钱；
3. 如果满足条件 $1, 2$，那么想办法杀更多的人。

那么最终的分配方案会是怎样的呢？

海盗们让小奔求出：若是 $N$ 个海盗抢到了 $M$ 个金币，并且要不少于 $P\%$ 的人投赞成票，他们会如何分配呢？

请你给出 $N$ 个海盗分 $M$ 个金币且要不少于 $P\%$ 的人投赞成票的解法，并保证结果号码较小的分到的金币尽可能的多。

**但是**，现实中并不会那么过于残忍，每个海盗也拥有自己的帮派，同一个帮派的人会互相投赞成票。

作为友情的代价，那个人必须分自己帮派里的每个人一定的金币，如果有一个人（不包括自己）没有被满足，那么整个帮派的人会同时投反对票。

新的结果又会是如何呢？

description:
如果 A 和 B 是朋友，B 和 C 也是朋友，那么说 A、B、C 都是同一个帮派里的。

现给出 $x$ 个兄弟关系，请你弄清其中的帮派关系，再求出 $n$ 个海盗分 $m$ 个金币的最新方法。

毒瘤预警：

**当然，你仍然需要保证结果号码较小的分到的金币尽可能的多，哪怕破坏帮派之间的关系。（自行理解）**

inputFormat:
第一行，五个数 $n, m, p, x, k$ 之间用空格隔开，分别表示强盗数目，金币数目，最低赞成百分比，兄弟关系总数以及所谓的友情所需要的代价。

接下来 $X$ 行，每行两个数，$i, j$，表示 $i$ 和 $j$ 是兄弟关系（或是说在同一个帮派）。

outputFormat:
只有一行，$N$ 个数之间用空格隔开，表示最后的结果。

如果某个海盗死了，输出 $-1$ 代替。


title: A换B problem

background: 仙女与小奔约定，想要拿到仙药，必须在牌技上赢了她。

description:
他们要开始打牌了。但是，拥有强迫症的小奔看着手中的牌，很不愉快。原因是他理牌时按花色理（逗我），又希望一个花色的牌是连着的（$A-2-3-4-5-6-7-8-9-10-J-Q-K$）。

忍无可忍的小奔开始与参与打牌的其他人换牌（作弊？？？），他希望换最少的牌来满足他的需求（假设所有牌都可以换）

换牌规则：只能用点数相同的牌交换。

众人：还能不能好好打牌了？！我们限你1s内换完，要不然就告诉仙女！

inputFormat:
第一行，一个正整数$N$，表示小奔有$N$张牌。

第$2~N+1$行，第$i$ 行表示第 $i$ 张牌的花色和点数。

outputFormat:
共有两行

第一行判断，如能完成，输出"Yes"，否则输出“No”；

第二行输出最少换牌次数或最少需要牌数

hint:
样例1，可达成，将$2$ $3$换为$1$ $3$，$4$ $J$换为$3$ $J$

样例2，可达成，将$2$ $3$换成$1$ $3$，$3$ $Q$换成$4$ $Q$。
（以上答案仅供参考，不保证没有多解,但输出必然唯一，~~别问我为什么~~）

对于10%的数据：为样例$2.$

对于100%的数据： $ N \leq 52 $，即保证数据在一副牌内


title: 矿洞：坍塌

background:
- Made By tomoo

CYJian家里为什么那么有钱？因为他家$&@$%#开了矿！！

CYJian家虽然有矿，但是有矿也不能任性。这不，CYJian家的矿塌了......

**change:出题人仁慈地放大了空间限制**

description:
CYJian家的矿塌了之后，就没有经济来源了（不要问我怎么没有存款）。

于是，CYJian迫切地想要修复他家的矿。

CYJian家的矿共出产$A,B,C$三种矿石，所以我们也只能用$A,B,C$三种材料来修复他们家的矿。我们已知共有$N$吨材料，每吨材料均为$A,B,C$三种材料中的一种，它们连成了一个串，如：
$$ABCBCABCBACBCBAA$$
CYJian家对材料的要求非常严格，他每次会选择一段连续区间的材料作为修复的材料。因为不合要求的材料会使得矿再次塌陷，砸死CYJian，所以这个连续区间的材料必须满足一下$2$个要求：
- 这段连续区间必须是同一种材料
- 这段连续区间的前一个材料与后一个材料必须不相同。

例如，有一段材料为$AACBBABBBCCCBBB$，则$(4$~$5)$ 区间的 $BB$ 和 $(5$~$5)$ 区间的 $B$ 均符合要求，而 $(10$~$12)$ 区间的 $CCC$ 不符合要求。

材料有灵性，所以材料会有变化。

现在有$N$吨材料，$K$个询问。每个询问是以下的$2$种形式之一：

- A x y op 表示替换材料，将$x$到$y(1<=x<=y<=N)$区间内的材料替换为$op$，$op$为$A,B,C$三种材料字符中的一个。
- B x y 表示是否询问，即询问$x$到$y(1<=x<=y<=N)$区间内的材料是否合法，合法输出$Yes$，不合法输出$No$。

注意:当$x=1$或$y=N$时,你的程序不需要判断前后的情况,而只需要判断区间内的情况.

inputFormat:
- 第一行一个正整数$N$
- 接下来$N$个字符，表示材料
- 接下来$K$个询问，格式为上述的一种

outputFormat: 对于每个 B x y 的询问，输出 $Yes$ 或 $No$

samples:
15
AACBBABBBCCCBBB
3
B 4 5
B 5 5
B 10 12


title: 小埋与刺客传奇

background:
**数据已更新。**

经过几天几夜的硬肝，小埋终于玩到了最后一关，也是$Dancing$ $Line$的魔王关——$The$ $Legend$ $of$ $Assassin$

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

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

description:
如图，魔王关经常出现炸路与突发障碍。

小埋很苦恼，因为她不知道完整的地图。于是她进行了许多尝试，总结了随着时间变化而出现或消失的路与她在这些时刻时的位置，**为了简化问题，我们假定小埋的位置始终不变**。

现在她想知道，她至少从什么时刻开始才可以看到能通向终点的路；由于一些路径上有钻石，这些钻石能带来一定加分，小埋还希望知道她在最早看到能通向终点的路时，按照当前地图走向终点所能获得的最大得分。

inputFormat:
第一行，两个数$n$，$m$，分别表示地图的结点数与初始边数，结点从$1-n$进行编号；初始时，为第$0$时刻，小埋在$1$号结点，且终点始终为$n$；

接下来$m$行，每行三个数$u_i$，$v_i$，$w_i$，表示一条从$u_i$到$v_i$的得分为$w_i$的边；

接下来一行，一个整数$t$，表示出现新边或旧边消失的时刻数，如无边出现或消失，$t=0$；

接下来$t$行，每行第一个数为$tm_j$，表示出现这一事件的时刻；第二个数为$type$，若$type==0$，表示出现了一条新边，之后会有三个数$u_j$，$v_j$，$w_j$，分别表示一条边信息（含义同上）；若$type==1$，之后会有一个数$k$，表示当前**时刻**未消失的第$k$条路消失了。

outputFormat: 若任何时刻下都不能到达终点，则输出”$Continue$ $from$ $the$ $last$ $checkpoint$”，否则输出两行：第一行为一个数$tmp$，表示看到通向终点路径时的最小时刻；第二行为一个数$score$，表示在上述时刻时到达终点所能获得的最大分数。


title: Agent1

background: 2018年11月17日，中国香港将会迎来一场`XM大战`，是世界各地的`ENLIGHTENED`与`RESISTANCE`开战的地点，某地 的`ENLIGHTENED总部`也想派`Agent`去参加这次的`XM大战`，与世界其他地方的`ENLIGHTENED`并肩作战。

description:
某地的`ENLIGHTENED总部`总部有$N$个`Agent`，每个`Agent`的能力值互不相同，现在`ENLIGHTENED行动指挥`想要派出$A,B$两队`Agent`去参加`XM大战`。但是参加大战的两个队伍要满足两个要求：

1. $A$队中能力最大的`Agent`的能力值要小于$B$队能力最弱的`Agent`的能力值。
2. $A,B$两队都要有人参战。

并不一定所有的`Agent`都要去参加`XM大战`的，心急的`ENLIGHTENED行动指挥`想知道有多少种安排`Agent`参加大战的方案。由于答案可能很大，所以只需要你求出答案模$(10^9+7)$的值就可以了。

inputFormat: 输入仅一行，为一个整数$N$。


title: Portal1

background:
Agent 获取资源有很多种方式，HACK 就是其中的一种，侵入 Portal 可以获得很多有用的资源。

ENLIGHTENED 总部因为参加 XM 大战，只剩下一点点可用资源了，所以 ENLIGHTENED 行动指挥想要进行 HACK 活动，尽量增加库存。

description: 地图上有 $n$ 个可以被 HACK 的 Portal，编号为 $1\sim n$。HACK 第 $i$ 号 Portal 需要时间 $t_i$ 秒，可以 HACK 出 $c_i$ 库存的资源。可是只有有能量的 Portal 才可以 HACK 出资源。第 $i$ 号 Portal 在第 $d_i$ 秒时，能量就会消失殆尽。ENLIGHTEDED 想知道，最多可以增加多少库存，并且按编号小到大输出需要 HACK 的 Portal 的编号。

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

下接 $n$ 行，每行三个整数 $t_i$，$d_i$，$c_i$。

outputFormat:
输出第一行为一个整数，最多可以增加多少库存。

第二行为一个整数，代表需要 HACK 多少个 Portal。

第三行按编号小到大输出需要 HACK 的 Portal 的编号，若有多种 HACK 的方案输出其中一种即可。

hint:
对于 $20\%$ 的数据，$n\leq5$，$t_i\leq 5$，$c_i\leq 5$，$d_i\leq10$。

对于 $40\%$ 的数据，$n\leq 20$，$t_i\leq 10$，$c_i\leq 10$，$d_i\leq 100$。

对于 $60\%$ 的数据，$n\leq50$，$t_i\leq15$，$c_i\leq15$，$d_i\leq1000$。

对于 $100\%$ 的数据，$1\leq n\leq 100$，$1 \leq t_i \leq 20$，$1\leq c_i \leq 20$，$1 \leq d_i \leq 2000$。


title: War1

background: `XM大战`来临之际，`ENLIGHTENED总部`为了抵御`RESISTANCE`的进攻，调整了某地`Portal`的能量值，使得其可以经受更多的打击。

description:
`ENLIGHTENED总部`有$N$个`Portal`，编号为$1$~$N$，编号为$i$的`Portal`初始能量值为$A[i]$，在`Portal`之间有$M$条`LINK`，每条`LINK`着连接着两个不同`Portal`，被连接着的两个`Portal`可以相互传输能量，每个`Portal`最多总共只能向其连接着的`Portal`传输$A[i]$点能量，现在`ENLIGHTENED行动指挥想让每第i个Portal的能量值变为至少B[i]，但他不知道着可不可行，所以找到了你，如果可行的话，需要你求出一种可行的能量传输方案。

**能量只能直接传输不能间接传输**

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

第二行有$N$个整数，第$i$个整数代表$A[i]$

第三行有$N$个整数，第$i$个整数代表$B[i]$

下接$M$行，每行输入两个整数$X,Y$，代表编号为$X$的`Portal`到编号为$Y$的`Portal`有一条`LINK`。

outputFormat:
若有可行方案输出`YES`，并且下接$N$行，每行$N$个整数，第$i$行第$j$个数代表代表编号为$i$的`Portal`向编号为$j$的`Portal`传输的能量值。若$i=j$输出第$i$个`Portal`传输后留下的能量值。若有多种可行方案输出其中一种即可。

若无可行方案输出`NO`


title: Agent2

background: 炎炎夏日还没有过去，`Agent`们没有一个想出去外面搞事情的。每当`ENLIGHTENED总部`组织活动时，人人都说有空，结果到了活动日，却一个接着一个`咕咕咕`了。只有不咕鸟`Lyn_king`一个人冒着太阳等了半个多小时，然后居然看到连`ENLIGHTENED行动参谋`都`咕咕咕`了，果然`咕咕咕`是人类的本性啊。

description:
作为一个`ENLIGHTENED行动指挥`，自然不想看到这一点，于是他偷取到了那些经常`咕咕咕`的`Agent`的在下来$N$天的`活动安排表`，并且叫上了你来整理。在整理过程中，`ENLIGHTENED行动指挥`对你说了$M$条命令，命令操作如下。
1. 输入$0,a,b$，这代表在第$a$天到第$b$天，有一名`Agent`要咕咕咕。
2. 输入$1$ $a$，这代表`ENLIGHTENED行动指挥`询问你根据目前的信息，在第$a$天有多少名`Agent`会咕咕咕。

作为同是不咕鸟的你，也想要惩戒那些经常`咕咕咕`的人，所以，请协助完成`ENLIGHTENED行动指挥`完成整理，并且在他每次询问时，输出正确的答案。

inputFormat:
第一行输入两个整数输$N,M$，
下来$M$行,每行输入一个命令，命令格式见题目描述。

outputFormat: 对于每一次询问的操作，都要输出询问的答案。答案之间用换行隔开。


title: Portal2

background: 某地`ENLIGHTENED`的`XM`研究所正在研究`Portal`的处理法则，想要揭示`XM能量`的来源以及应用`XM能量`。`ENLIGHTENED`的首席科学家`Jacks`发现其能量的运算法则以及运算方法，但是方法十分复杂，仅靠人手工计算是很难算出答案的，所以它需要你协助他完成计算。

description:
`Portal`计算`XM能量`是通过个$2$个栈（$0$号栈，$1$号栈）实现的，它把对`XM`能量的操作如下

$PUSH$ $X$ $NUM$

把$NUM$加入到X号栈的栈顶。

$POP$ $X$

把$X$号栈的栈顶元素**删除**。

$ADD$ $X$

**取出**$0$号栈和$1$号栈的元素各一个，并且把它的和放入$X$号栈。

$SUB$ $X$

**取出**$0$号栈和$1$号栈的元素各一个，并且把它的差的绝对值放入$X$号栈。

$DEL$ $X$

**清空**$X$号栈中所有元素不管栈是否为空。

$MOVE$ $X$ $Y$

循环操直到$Y$号栈为空，把$Y$号栈的栈顶元素加入到$X$号栈，删除$Y$号栈的栈顶元素。

**数据保证X和Y不相同**

$SWAP$

将两个栈的所有元素调换。

$END$

代表命令结束，并且分两行分别输出0号栈和1号栈由栈顶到栈底的元素的值，若栈内无元素，输出`NONE`。数据保证指令以`END`结束且仅有一个`END`，并且也需要输出`SUCCESS`。

~~$AKNOI$~~

~~等为无效操作，**无效操作后不接数字**。~~

**更正不会有类似无效操作**

对于每一行指令，若当前指令成功执行输出`SUCCESS`，若**取出**或**删除**元素时栈内为空或者没有对应指令输出`UNSUCCESS`并且不执行该行指令。

inputFormat: 输入若干行指令，以`END`指令结束

outputFormat: 对于每一次操作，都要对应输出`SUCCESS`或者`UNSUCCESS`，对于`END`根据指令描述输出栈内元素。

samples:
PUSH 0 10
PUSH 0 20
PUSH 0 30
PUSH 0 40
PUSH 1 50
PUSH 1 60
ADD 0
ADD 0
ADD 0
END

samples:
SUCCESS
SUCCESS
SUCCESS
SUCCESS
SUCCESS
SUCCESS
SUCCESS
SUCCESS
UNSUCCESS
SUCCESS
150 30 20 10
NONE

samples:
PUSH 0 10
PUSH 0 20
PUSH 0 30
PUSH 0 40
PUSH 1 50
PUSH 1 60
MOVE 0 1
END

samples:
SUCCESS
SUCCESS
SUCCESS
SUCCESS
SUCCESS
SUCCESS
SUCCESS
SUCCESS
50 60 40 30 20 10
NONE

hint:
对于$20\%$的数据 数据保证不会出现`MOVE/SWAP`操作，$命令总数 \leq 100$

对于$40\%$的数据 $命令总数 \leq 1000$

对于$60\%$的数据 数据保证`MOVE/SWAP`的操作次数不会超过$10000$次，$命令总数 \leq 10^5$

对于$100\%$的数据 $0 \leq X,Y \leq 1,命令总数 \leq 10^6$

**数据保证无论任何情况，栈中元素的值$X$满足$0 \leq x \leq 2^{63}-1$**

[题目创意来源OIERBBS](https://www.oierbbs.cn)


title: War2

background: `XM大战`如期而至，`Agent`们齐聚一地，展开最后的对决。对战有很多种方式，有些复杂的方式可以获得更高的分数。可惜`ENLIGHTENED`的人并不怎么聪明，只会简单的`hack`，所以`ENLIGHTENED行动指挥`找到了你来做他们的总参谋。

description: 地图上有$N$个`Portal`，现在某一名`Agent`的任务是占领该地图上的$M$个`Portal`，这名`Agent`占领第$i$个`Portal`可以得到的分数为$A[i]$，除了直接占领，还有其他的$K$种加分方式，对于着$N$个`Portal`，在占领完第$X[i]$个`Portal`后占领第$Y[i]$个`Portal`可以获得$B[i]$的加分，加分可能会有重复。`Agent`希望他可以为团队争取更多的分数，所以请求作为大战参谋的你来帮助他。

inputFormat:
第一行是输入三个整数$N,M,K$
第二行输入是$N$个数，第$i$个数代表$A[i]$的值。
下面$K$行每行有3个整数$X[i],Y[i],C[i]$，表示在占领完第$X[i]$个`Portal`后占领第$Y[i]$个`Portal`可以获得$B[i]$的加分

outputFormat: 输出仅一行一个整数，为该名`Agent`可以获得的最大分数值。


title: [IOI2018] seats 排座位

background: 本题为交互题，但在此请提交**完整程序**。

description:
你要在一个长方形大厅里举办国际编程比赛，该大厅共有 $HW$ 个座位（$H$ 行 $W$ 列）。行的编号是从 $0$ 到 $H-1$，列的编号是从 $0$ 到 $W-1$。位于 $r$ 行 $c$ 列的座位用 $(r,c)$ 表示。一共邀请了 $HW$ 位参赛者，编号是从 $0$ 到 $HW-1$。你制定好了一个座位表，第 $i(0 \leq i \leq HW - 1)$ 个参赛者被安排到座位 $(R_i,C_i)$。座位表中参赛者和座位是一一对应的。

大厅中一个座位集合 $S$ 被称为是**长方形的**，如果存在整数 $r_1, r_2, c_1$ 和 $c_2$ 满足下列条件：

- $0 \leq r_1 \leq r_2 \leq H - 1$。
- $0 \leq c_1 \leq c_2 \leq W - 1$。
- $S$ 正好是所有满足 $r_1 \leq r \leq r_2$ 和 $c_1 \leq c \leq c_2$ 的座位 $(r, c)$ 的集合。

如果一个长方形座位集合包含 $k(1 \leq k \leq HW)$ 个座位，并且被分配到这个集合的参赛者的编号恰好是从 $0$ 到 $k-1$，那么该集合是**美妙的**。一个座位表的**美妙度**定义为这个表中美妙的长方形座位集合的个数。

在准备好座位表后，你会收到一些交换两个参赛者座位的请求。具体来说，有 $Q$ 个这样的请求，按时间顺序编号为 $0$ 到 $Q-1$。第 $j(0 \leq j \leq Q - 1)$ 个请求希望交换参赛者 $A_j$ 和 $B_j$ 的座位。你立即接受每个请求并更新座位表。每次更新后，你的目标是计算当前座位表的美妙度。

inputFormat:
输入的第一行包含三个正整数 $H, W, Q$，其意义见题目描述。

接下来 $HW$ 行，每行包含两个非负整数。在这 $HW$ 行中，第 $i$ 行的两个整数分别表示 $R_{i - 1}, C_{i - 1}$，即编号为 $i - 1$ 的参赛者初始座位的行和列。

接下来 $Q$ 行，每行包含两个非负整数。在这 $Q$ 行中，第 $j$ 行的两个整数分别表示 $A_{j - 1}, B_{j - 1}$，即在编号为 $j - 1$ 的请求中希望被交换座位的两位参赛者的编号。

outputFormat: 输出共 $Q$ 行，每行包含一个整数，第 $i$ 行的整数表示按时间顺序处理完编号为 $i - 1$ 的交换请求之后当前座位表的美妙度。


title: [IOI2018] werewolf 狼人

background: 本题为交互题，但在此请提交**完整程序**。

description:
在日本的茨城县内共有 $N$ 个城市和 $M$ 条道路。这些城市是根据人口数量的升序排列的，依次编号为 $0$ 到 $N - 1$。每条道路连接两个不同的城市，并且可以双向通行。由这些道路，你能从任意一个城市到另外任意一个城市。

你计划了 $Q$ 个行程，这些行程分别编号为 $0$ 至 $Q - 1$。第 $i(0 \leq i \leq Q - 1)$ 个行程是从城市 $S_i$ 到城市 $E_i$。

你是一个狼人。你有两种形态：**人形**和**狼形**。在每个行程开始的时候，你是人形。在每个行程结束的时候，你必须是狼形。在行程中，你必须要变身（从人形变成狼形）恰好一次，而且只能在某个城市内（包括可能是在 $S_i$ 或 $E_i$ 内）变身。

狼人的生活并不容易。当你是人形时，你必须避开人少的城市，而当你是狼形时，你必须避开人多的城市。对于每一次行程 $i(0 \leq i \leq Q - 1)$，都有两个阈值 $L_i$ 和 $R_i(0 \leq L_i \leq R_i \leq N - 1)$，用以表示哪些城市必须要避开。准确地说，当你是人形时，你必须避开城市 $0, 1, \ldots , L_i - 1$ ；而当你是狼形时，则必须避开城市 $R_i + 1, R_i + 2, \ldots , N - 1$。这就是说，在行程 $i$ 中，你必须在城市 $L_i, L_i + 1, \ldots , R_i$ 中的其中一个城市内变身。

你的任务是，对每一次行程，判定是否有可能在满足上述限制的前提下，由城市 $S_i$ 走到城市 $E_i$。你的路线可以有任意长度。

inputFormat:
输入的第一行包含三个正整数 $N, M, Q$，其意义见题目描述。

接下来 $M$ 行，每行包含两个非负整数。在这 $M$ 行中，第 $j$ 行的两个非负整数分别表示 $X_{j - 1}, Y_{j - 1}$，即编号为 $j - 1$ 的道路连接的两个城市的编号。

接下来 $Q$ 行，每行包含四个非负整数。在这 $Q$ 行中，第 $i$ 行的四个非负整数分别表示 $S_{i - 1}, E_{i - 1}, L_{i - 1}, R_{i - 1}$，即编号为 $i - 1$ 的行程的起点城市编号、终点城市编号以及两个阈值。

outputFormat: 输出包含 $Q$ 行，每行包含一个非 $0$ 即 $1$ 的整数。第 $i$ 行的整数表示对于编号为 $i - 1$ 的行程，是否能从城市 $S_{i - 1}$ 走至城市 $E_{i - 1}$，若能够，那么输出整数为 $1$；若不能，那么输出整数为 $0$。

hint:
**限制条件**

- $2 \leq N \leq 200, 000$
- $N - 1 \leq M \leq 400, 000$
- $1 \leq Q \leq 200, 000$
- 对于每个 $0 \leq j \leq M - 1$
    - $0 \leq X_j \leq N - 1$
    - $0 \leq Y_j \leq N - 1$
    - $X_j \neq Y_j$
- 你可以通过道路由任意一个城市去另外任意一个城市。
- 每一对城市最多只由一条道路直接连起来。换言之，对于所有 $0 \leq j < k \leq M - 1$，都有 $(X_j, Y_j) \neq (X_k, Y_k)$ 和 $(Y_j, X_j) \neq (X_k, Y_k)$
- 对于每个 $0 \leq i \leq Q - 1$
    - $0 \leq L_i \leq S_i \leq N - 1$
    - $0 \leq E_i \leq R_i \leq N - 1$
    - $S_i \neq E_i$
    - $L_i \leq R_i$

**子任务**

- 1.（7 分）$N \leq 100$，$M \leq 200$，$Q \leq 100$。
- 2.（8 分）$N \leq 3, 000$，$M \leq 6, 000$，$Q \leq 3, 000$。
- 3.（34 分）$M = N - 1$ 且每个城市最多与两条路相连（所有城市是以一条直线的形式连起来）。
- 4.（51 分）没有附加限制。


title: 二进制之谜

background: 虽然过了$Faded$，但是小埋还是没有解出二进制之谜。

description:
这个时候，她感觉到了$0$与$1$存在的某种可能的特殊对应关系。于是，她定义了“启发系数”：对应的两个数位数（按从高位到低位顺序去数）的差的绝对值；她现在希望将$0$与$1$进行对应使得**在对应关系最多的前提下**，启发系数之和最大。

对应规则如下：

$1$.对应关系必须从$0$开始，以$1$结束；换句话说，每个对应关系必须$0$在前（高位），$1$在后（低位）；

$2$.可以取若干个对应关系，但对应关系之间**不能交叉**；**交叉**的含义是：共用某个区间且不是包含关系；

$e.g.$ 假设一个对应关系为第$2$位数与第$4$位数，另一个对应关系为第$3$位数与第$5$位数，那么它们不可同时取，因为在区间$[3,4]$交叉；但是若对应关系分别为第$1$、$5$位数与第$2$、$4$位数，则不算作交叉，因为它们虽然共用区间$[2,4]$但存在包含关系，可以同时取。

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

这即是说，**交叉不等于交集**。

$3$.每个数最多只能存在于一个对应关系中。

inputFormat:
第一行，一个整数$n$，为二进制数的位数；

接下来一行，输入一个$n$位二进制数。

outputFormat: 一行，表示对应关系最多的前提下最大的启发系数之和。

hint:
对于$30$%的数据，$0<n<=20$；

对于$100$%的数据，$0<n<=300$；

**样例说明**

对于样例一，由于$1$在$0$前面，两者不能对应；

对于样例二，对应方案为$3-4$，故总和为$1$。

如果您提前$AK$了，可以做一下[数据增强版](https://www.luogu.org/problemnew/show/T53667)


title: 小奔关闹钟

background: 由于今天是星期一，闹钟准时响了，由于小奔太困了，所以他想关停闹钟。

description:
可是，他的闹钟电路太复杂了，有很多个开关，每个开关都连着其他开关，其他开关又连着更多的开关，当且仅当所有开关都关闭时，闹钟才会停止响铃，（初始时默认每个开关都开着的），她该如何是好呢？

请你帮小奔求出最少开关次数，如果无论如何都不能关闭闹钟，请输出‘Change an alarm clock，please!’

inputFormat:
共有N+1行

第一行一个数N（1≤N≤20），表示有N个开关，从第2行起的第i行表示第i个闹钟开关。

以后N行，每行第一个数为M（0≤M≤N-1），表示第i个闹钟开关的直接关联开关个数。（由直接关联开关所关联的直接关联开关，自然就是第i个闹钟间接关联开关啦，当打开第i个开关时，只有直接关联，间接关联以及第i个开关才会起作用。），之后M个数，表示第i个闹钟直接关联开关的标号。（如果M为0则表示没有任何关联）

outputFormat: 一个数ans，表示最少按开关次数，如果无法关闭，输出‘Change an alarm clock，please!’

hint:
样例1说明：

先关闭5，直接关联会关闭1。1间接关闭2、3、4，但会重新打开5。

此时共关闭开关一次，已关闭1，2，3，4

再打开2，直接关联会打开1和3。1间接关闭2、3、5，重新打开4。3间接关闭1、4。

此时共关闭开关2次，已关闭1，2，3，4，5，彻底关闭闹钟。


title: 小奔上课

background: 这一堂课是数学课！

description:
小奔最喜欢数学了QvQ，但是因为晚上太困睡着了，所以当他反应过来要写题目时，黑板上的算式已经残缺不堪了。

没办法，小奔只好依靠人品猜一下了，只是猜也是有方法的，小奔想请你给出最大可能值和最输出只有一行，为最大可能值和最小可能值的平均值，并保留两位小数小可能值的平均值。

inputFormat: 只有一行，为残缺的算式（可能有括号），残缺部分用$*$表示~~（与乘号相同）~~，残缺部分可以为数字$0$到$9$，也可以是四则运算符号之一，不存在残缺括号。

outputFormat: 输出只有一行，为最大可能值和最小可能值的平均值，并保留两位小数

hint:
样例解释:

最大值：$191+9-2+3/1=201$

最小值：$1-1+9-293/1=-284$

$07+1$（0不能打头），$5/0$（0不能做除数）等算式都是非法的

但$8+-6$是合法的，代表$8$加负$6$，同理$8/-6$也可

保证结果在$float$范围内

对于$40$%的数据，算式有括号

对于$10$%的数据，算式完全残缺（全是 * ）


title: [MtOI2018] 魔力环

background: wkr 是一名来自魔力之都的 OIer，他喜欢收集黑色与白色的魔力珠。

description:
wkr 希望能够得到一个由 $n$ 个魔力珠串成的环。不过他对普通的环并不感兴趣，因此他提出了如下的要求：

- wkr 希望在这个环上，**恰好**有 $m$ 个黑色的魔力珠与 $n - m$ 个白色的魔力珠。
- 由于 wkr 认为黑色魔力珠不应过于密集，因此 wkr 希望这个环上**不会**出现一段**连续**的黑色魔力珠，其长度**超过** $k$。

在 wkr 的心目中，满足上述要求的环才是美妙的。

不过这样的环可能并不唯一。 wkr 想要知道共有多少种不同的环满足他所提出的要求。然而 wkr 并不喜欢计算，他希望聪明的你能够告诉他答案。

在这里，我们认为**两个环是不同的，当且仅当其中一个环仅通过旋转无法得到另一个环**。

由于答案可能过大，因此输出答案对 $998, 244, 353$ 取模后的结果。

inputFormat: 输入共 $1$ 行 $3$ 个非负整数 $n, m, k$，其意义见题目描述，相邻的两个数用单个空格隔开。

outputFormat: 输出共 $1$ 行 $1$ 个整数，表示满足要求的环的数量。

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

由 $6$ 个魔力珠串成，满足其中恰好有 $3$ 个黑色魔力珠与 $3$ 个白色魔力珠，且不存在长度超过 $2$ 的连续的黑色魔力珠的不同的环共有 $3$ 种，如下图所示。

![QQ20181002002120.png](https://www.z4a.net/images/2018/10/02/QQ20181002002120.png)

下图所示的环不满足 wkr 提出的要求，因为在这个环中，存在一段连续的黑色魔力珠，长度超过了 $2$。

![QQ20181002002148.png](https://www.z4a.net/images/2018/10/02/QQ20181002002148.png)

### 子任务

所有测试点均满足 $1 \leq n, k \leq 10^5, 0 \leq m \leq 10^5$ 且 $m \leq n$。

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

- 子任务 1（3 分）：$m = 0$
- 子任务 2（5 分）：$n \leq 4$
- 子任务 3（8 分）：$n \leq 18$
- 子任务 4（7 分）：$m = 2$
- 子任务 5（19 分）：$k = 1$
- 子任务 6（27 分）：$\gcd(n,m) \leq 2$
- 子任务 7（31 分）：无特殊限制

### 题目来源

[MtOI2018 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T6

出题人：Imagine

72679


title: [1007] 魔法少女小Scarlet

description:
Scarlet 最近学会了一个数组魔法，她会在 $n\times n$ 二维数组上将一个奇数阶方阵按照顺时针或者逆时针旋转 $90^\circ$。

首先，Scarlet 会把 $1$ 到 $n^2$ 的正整数按照从左往右，从上至下的顺序填入初始的二维数组中，然后她会施放一些简易的魔法。

Scarlet 既不会什么分块特技，也不会什么 Splay 套 Splay，她现在提供给你她的魔法执行顺序，想让你来告诉她魔法按次执行完毕后的二维数组。

inputFormat:
第一行两个整数 $n,m$，表示方阵大小和魔法施放次数。

接下来 $m$ 行，每行 $4$ 个整数 $x,y,r,z$，表示在这次魔法中，Scarlet 会把以第 $x$ 行第 $y$ 列为中心的 $2r+1$ 阶矩阵按照某种时针方向旋转，其中 $z=0$ 表示顺时针，$z=1$ 表示逆时针。

outputFormat: 输出 $n$ 行，每行 $n$ 个用空格隔开的数，表示最终所得的矩阵

hint:
对于50%的数据，满足 $r=1$

对于100%的数据 $1\leq n,m\leq500$，满足 $1\leq x-r\leq x+r\leq n,1\leq y-r\leq y+r\leq n$。


title: 水の造题

background:
第一分钟,$CYJian$说:"要有样子."于是便有了$k$种动作..

第二分钟,$CYJian$说:"要有活力."于是便有了$k$种动作组成的总动作数为$N$的搏击操.

第三分钟,$CYJian$说:"要有数学."于是便有了一套搏击操的威力.

第四分钟,$CYJian$说:"数字要小."于是便有了一个伟大的模数$19491001$.

第五分钟,$CYJian$说:"要有规律."于是便有了一套搏击操威力的计算方法.

第六分钟,$CYJian$说:"要有限制."于是便有了时空限制以及数据范围.

第七分钟,$CYJian$说:"要有答案."于是便有了这道题让你做掉.

...

第*分钟,巨佬$Imagine$说:"数据太水."于是蒟蒻出题人疯了..(详见数据范围)

description:
现在有一套由$k$种动作组成的动作总数为$N$的搏击操.

已知第$1$,$2$...$k$个动作的威力为$a[1...k]$

且如果第一个动作后紧接着第二个动作,则威力会额外加上$a[1]+a[2]$

如果第二个动作后紧接着第三个动作,则威力会额外加上$a[2]+a[3]$

...

如果第$k$个动作后紧接着第一个动作,则威力会额外加上$a[k]+a[1]$

请求出最后动作的期望威力..

当然,还是要用伟大的模数$19491001$来膜一膜的...

inputFormat:
第一行,一个正整数$N$

第二行,一个正整数$k$

第三行,$k$个正整数$a[1...k]$

outputFormat: 一行,一个正整数表示期望的威力模$19491001$的值.


title: 毒瘤之神奇进制

background:
## 红树林2363 大佬正在造计算机

(CYJian: zrz你不要拿你的垃圾输入法搞这些拼音游戏了..又不是看不出hsl2363..)

description:
很失落2363 大佬发现计算机肥肠好 *van* ，他打算自己造一台，造好之后 责任制 蒟蒻来了，含水量2363 大佬告诉他：

”我的计算机是 X-* 进制的， 你到底有多菜我很想知道，所以问问你我电脑几个数换成十进制之后到底是啥。”

所谓 X-*进制，就是把这个数的每一位的ASCII码减去0的ASCII码再乘以X的i次方,再相乘。（讲的很糊，看解释吧）

如：

3   2363

换算之后为 $2 * 3^3 * 3 * 3 ^ 2 * 6 * 3 ^ 1 * 3 * 3 ^ 0$

载入中 蒟蒻觉得太难了，把他抛给了你。

因为答案可能很大请输出答案的位数（滑稽）。

inputFormat:
一个整数Q代表问题个数

接下来Q行，每一行一行一个整数a代表 X-*进制， 一个字符串s代表这个数

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

hint:
1≤Q≤100
1≤a≤100000 且为字符串长度减1。

数据有梯度，但我不告诉你

$$\color{white}{\text{如果想要暴力，没有高精度是不可能的}}$$

数据保证字符串中没有'0'。


title: [1007] Scarlet的字符串不可能这么可爱

description:
Scarlet妄图构造字符集为$k$，长度为$L$的字符串，满足没有任何一个长度超过$1$的回文连续子串。

看起来这样的字符串太多了，Scarlet随手加了个限制：她指定了字符串的第$s$位为$w$。

这下Scarlet不会做了，请你来帮她计算究竟有多少满足条件的字符串。按照套路，你只要求出答案对$p$取模后的结果。

inputFormat:
第一行三个整数$k,L$和$p$，分别表示构造的字符串的的字符集、长度和模数。

第二行两个整数$s,w$，描述Scarlet给的限制。

**注意：$s=0$表示该数据点中Scarlet十分良心地没有添加限制**

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

hint:
字符集：一个字符串中不同字符的数量。例如，字符集是3的话，你可以认为字符串仅由“A”、“B”、“C”三个字母组成。

样例解释：第一个字符固定A，那么符合要求的字符串是ABC,ACB。而AAB字符串包括AA这个回文子串，ACA本身就是回文串，一次类推。

对于50%的数据，$k\leq5,L\leq10$

对于另30%的数据，$s=0$

对于100%的数据$1\leq k,L\leq 10^{18},0\leq s\leq L,1\leq w\leq k,1\leq p\leq 10^9$


title: [1007] 倍杀测量者

description:
今天 Scarlet 在机房有幸目睹了一场别开生面的 OI 训练。因为一些奇妙的 SPJ，比赛中所有选手的得分都是正实数（甚至没有上限）。

当一位选手 A 的分数不小于选手 B 的分数 $k$（$k>0$）倍时，我们称选手 A **$k$ 倍杀** 了选手 B，选手 B **被** 选手 A **$k$ 倍杀** 了。

更奇妙也更激动人心的是，训练前有不少选手立下了诸如 “我没 $k$ 倍杀选手 X，我就女装”，“选手 Y 把我 $k$ 倍杀，我就女装” 的 Flag。

知道真相的良心教练 Patchouli 为了维持机房秩序，放宽了选手们的 Flag 限制。Patchouli 设定了一个 **正** 常数 $T$，立下 “我没 $k$ 倍杀选手 X 就女装” 的选手只要成功 $k - T$ 倍杀了选手 X，就不需要女装。同样的，立下 “选手 Y 把我 $k$ 倍杀我就女装” 的选手只要没有成功被选手 Y $k+T$ 倍杀，也不需要女装。

提前知道了某些选手分数和具体 Flag 的 Scarlet 实在不忍心看到这么一次精彩比赛却没人女装，为了方便和 Patchouli 交易，Scarlet 想要确定最大的实数 $T$ 使得赛后一定有选手收 Flag 女装。

inputFormat:
第一行三个整数 $n,s,t$，分别表示机房内选手人数，选手立下的 Flag 总数和 Scarlet 已知的选手分数的数量。$n$ 位选手从 $1$ 开始编号至 $n$，编号为 $k$ 的选手被称为选手 $k$。

接下来 $s$ 行，每行四个整数 $o,A,B,k$。其中 $o=1$ 表示选手 A 立下了 “我没 $k$ 倍杀选手 B 就女装” 的 Flag，$o=2$ 表示选手 A 立下了 “选手 B 把我 $k$ 倍杀我就女装” 的 Flag。

接下来 $t$ 行，每行两个整数 $C,x$，表示 Scarlet 已知选手 $C$ 的分数为 $x$。

outputFormat:
若存在能保证赛后有选手女装的最大的 $T$，则输出 $T$，只有当输出与答案的绝对误差不超过 $10^{-4}$ 时才被视作正确输出。

若不存在，输出 `-1`。

hint:
- 对于 $30\%$ 的数据，$n\leq5$，$s\leq 2$；
- 对于另 $40\%$ 的数据，保证 $t=n$；
- 对于 $100\%$ 的数据，$1\leq n,s\leq 1000$，$1\leq A,B,C,t\leq n$，$1\leq k\leq 10$，$1\leq x\leq 10^9$。保证输入中的 $C$ 两两不同。


title: tb148的客人

background: tb148使用优惠券买来了许多食材后，请来了很多客人来吃饭。

description: tb148和他的n个客人，他们每人有一个编号（从一开始的连续正整数）。目前，大家不按编号，乱序围坐在一张圆桌上。每次操作我们可以同时让任意多的客人沿顺时针或逆时针移动一个位置，我们称作一次操作。这个过程中一个位置可以没有客人或有多个客人。请问最少需要多少秒，使得每个位置仍恰好只有一个数，且客人的编号沿顺时针或逆时针依次为1~n？

inputFormat:
输入包含两行。
第一行为一个正整数n。第二行为n 个空格隔开的正整数，为一个1~n 的排列，表
示最开始时按顺时针顺序的客人编号。

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

hint:
对于40% 的数据，1≤n≤3000。
对于80% 的数据，1≤n≤300000。
对于100% 的数据，1≤n≤1000000。


title: 毒瘤之神异之旅

background:
题目名称是吸引你点进来的……

我们的出题人CYJian由于出了过多毒瘤题被D死之后，OIer们将他埋葬在地狱十八层之下……

description:
已知地狱有$K$个守护者,每个守护者有一个能力值$a_i$。但是我们并不知道他们确切的能力值。只知道这些人的能力值的和为$N$。但是在地狱中守护者的威力会得到加强，具体来说每一个守护者的威力为$a_i^M$。

现在给出$N$,$M$,$K$,请求出所有可能的方案的威力值之和。

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

outputFormat: 一行一个整数，表示所有守护者能够发出的可能的威力值之和模$1e9+7$。

hint:
Subtask1(20 pts):

$1 \leq N,M \leq 10$

$1 \leq K \leq N$

Subtask 2(40 pts):

$1 \leq N,M \leq 4096$

$1 \leq K \leq N$

Subtask 3(40 pts):

$1 \leq N,M \leq 10000$

$1 \leq K \leq N$

其中所有的$a_i$均需要是正整数.

不要喷出题人毒瘤卡常，每一档部分分的时间和空间都至少开了标程的两倍。

由于数据只有一组，可能强度较弱，所以需要每5个点捆绑测试。


title: [IOI2018] meetings 会议

background:
本题为交互题，但在此请提交**完整程序**。

本题因为测试点过多，文件过大，只选择了33个测试点进行测评（涵盖了所有子任务）。剩余11组数据可下载数据自行测评。

https://ioi2018.jp/wp-content/tasks/contest2/meetings.zip

description:
有 $N$ 座山横着排成一行，从左到右编号为从 $0$ 到 $N-1$。山的高度为 $H_i$（$0\leq i\leq N-1$）。每座山的顶上恰好住着一个人。

你打算举行 $Q$ 个会议，编号为从 $0$ 到 $Q-1$。会议 $j$（$0\leq j\leq Q-1$） 的参加者为住在从山 $L_j$ 到山 $R_j$（包括 $L_j$ 和 $R_j$）上的人（$0\leq L_j\leq R_j\leq N-1$）。对于该会议，你必须选择某个山 $x$ 做为会议举办地（$L_j\leq x\leq R_j$）。举办该会议的成本与你的选择有关，其计算方式如下：

- 来自每座山 $y$（$L_j\leq y\leq R_j$） 的参会者的成本，等于在山 $x$ 和 $y$ 之间（包含 $x$ 和 $y$）的所有山的最大高度。特别地，来自山 $x$ 的参会者的成本是 $H_x$，也就是山 $x$ 的高度。

- 会议的成本等于其所有参会者的成本之和。

你想要用最低的成本来举办每个会议。

注意，所有的参会者将在每次会议后回到他们自己的山；所以一个会议的成本不会受到先前会议的影响。

inputFormat:
输入的第一行包含两个正整数 $N$ 和 $Q$，其意义见题目描述。

第二行包含 $N$ 个正整数 $H_0,H_1,\cdots, H_{N-1}$，表示这些山的高度。

第 $3+j$ 行（$0\leq j\leq Q-1$），每行两个整数 $L_j, R_j$，表示这些会议的参会者的范围。

outputFormat: 共 $Q$ 行，第 $1+j$ 行（$0\leq j\leq Q-1$）一个整数 $C_j$，表示举办会议 $j $ 的最低的可能成本。

hint:
### 样例#1解释

会议$j=0$有$L_j=0$和$R_j=2$，所以将由住在山$0$、$1$和$2$上的人参加。如果山$0$被选做举办地，会议$0$的成本计算如下：

- 住在山$0$上的参会者的成本是$\max\lbrace H_0\rbrace=2$。
- 住在山$1$上的参会者的成本是$\max\lbrace H_0,H_1\rbrace=4$。
- 住在山$2$上的参会者的成本是$\max\lbrace H_0,H_1,H_2\rbrace=4$。
- 因此，会议$0$的成本是$2+4+4=10$。

不可能以更低的成本来举办会议$0$了，因此会议$0$的最低成本是$10$。

会议$j=1$有$L_j=1$和$R_j=3$，因此将由住在山$1$、$2$和$3$上的人参加。如果山$2$被选做举办地，会议$1$的成本计算如下：

- 住在山$1$上的参会者的成本是$\max\lbrace H_1,H_2\rbrace=4$。
- 住在山$2$上的参会者的成本是$\max\lbrace H_2\rbrace=3$。
- 住在山$3$上的参会者的成本是$\max\lbrace H_1,H_2,H_3\rbrace=5$。
- 因此，会议$1$的成本是$4+3+5=12$。

不可能以更低的成本来举办会议$1$了，所以会议$1$的最低成本是$12$。

### 限制条件

- $1\leq N\leq 750\space000$
- $1\leq Q\leq 750\space000$
- $1\leq H_i\leq1\space000\space000\space000$
- $0\leq L_j\leq R_j\leq R-1(0\leq j\leq Q-1)$
- $(L_j,R_j)\neq(L_k,R_k)(0\leq j<k\leq Q-1)$

### 子任务

1. (4分) $N\leq3000,Q\leq10$
2. (15分) $N\leq5000,Q\leq5000$
3. (17分) $N\leq100\space000,Q\leq100\space000,H_i\leq2(0\leq i\leq N-1)$
4. (24分) $N\leq100\space000,Q\leq100\space000,H_i\leq20(0\leq i\leq N-1)$
5. (40分) 没有附加限制

### Author

Riku Kawasaki (Japan)

### Source

IOI 2018 D2T3


title: 专心OI - 找祖先

background: Imakf 是一个小蒟蒻，他最近刚学了 LCA，他在手机 APPstore 里看到一个游戏也叫做 LCA 就下载了下来。

description: 这个游戏会给出你一棵树，这棵树有 $N$ 个节点，根结点是 $R$，系统会选中 $M$ 个点 $P_1,P_2 \cdots P_M$，要Imakf 回答有多少组点对 $(u_i,v_i)$ 的最近公共祖先是 $P_i$。Imakf 是个小蒟蒻，他就算学了 LCA 也做不出，于是只好求助您了。

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

此后 $N-1$ 行，每行两个数 $a,b$，表示 $a,b$ 之间有一条边。

此后 $1 $行，共 $M$ 个数，表示$P_i$。

保证给出的边形成一棵树。

outputFormat: 输出共 $M$ 行，每行一个数，第 $i$ 行的数表示有多少组点对 $(u_i,v_i)$ 的最近公共祖先是 $P_i$。


title: 毒瘤之神TM菱树-①

background:
本题图片可能较大请耐心加载

什么?菱树是什么??

好吧这个是蒟蒻自己搞事搞的一个非常简单的不是树但很像树的图..

就像这样..

![菱树](https://i.loli.net/2018/10/07/5bba0e85cbc10.png)

(好吧图有点大(空旷)..)

description:
现在给你一棵无限大的菱树(就是下面不止上面的图那么点大..)

然后有$T$组询问,每一组询问都是给出$u$和$v$,求出这两个点的最短路径的长度..

inputFormat:
第一行一个正整数$T$

接下来$T$行每一行两个正整数表示询问的两个点..

outputFormat: $T$行,每行一个整数表示询问的答案.

hint:
${\rm Subtask\ 1(10\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq u_i, v_i \leq 100$

${\rm Subtask\ 2(20\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq u_i, v_i \leq 10^3$

${\rm Subtask\ 3(30\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq u_i, v_i \leq 10^5$

${\rm Subtask\ 4(40\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq u_i, v_i \leq 10^{18}$


title: 毒瘤之神TM菱树-②

background:
什么?菱树是什么??

好吧这个是蒟蒻自己搞事搞的一个非常简单的不是树但很像树的图..

就像这样..

![菱树](https://i.loli.net/2018/10/07/5bba0e85cbc10.png)

(好吧图有点大(空旷)..)

description: 现在给你$T$棵菱树,每一颗菱树的层数为$n_i$,请求出菱树中所有点对的最短路径的和..

inputFormat:
第一行一个正整数$T$

接下来$T$行每一行一个正整数$n_i$表示菱树的大小..

outputFormat: $T$行,每行一个整数表示对于当前这颗菱树的所有点对的最短路径的和模$998244853$的结果.

hint:
${\rm Subtask\ 1(10\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq n_i \leq 10$

${\rm Subtask\ 2(20\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq n_i \leq 100$

${\rm Subtask\ 3(30\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq n_i \leq 1000$

${\rm Subtask\ 4(40\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq n_i \leq 5*10^6$

为了防止打表，所以空间限制缩小至64MB。


title: 「MCOI-01」Village 村庄

background:
今天，珂爱善良的0x3喵酱骑着一匹小马来到了一个村庄。

“诶，这个村庄的布局 ……”
“好像之前我玩 Ciste 的地方啊 qwq”

0x3喵酱有一个地图，地图有着这个村庄的信息。

然后0x3喵酱要通过这张地图来判断 Ciste 有解无解啦 ~

注：Ciste 是《请问您今天要来点兔子吗》中的一种藏宝图游戏

description:
村庄被简化为一个 $n$ 个节点（编号为 $1$ 到 $n$）和 $n-1$ 条边构成的无向连通图。

0x3喵酱认为这个无向图里的信息跟满足以下条件的新图有关：

- 新图的点集与原图相同
- 在新图中 $u,v$ 之间有无向边 是 在原图中 $dis(u,v) \ge k$ 的**充分必要条件** （$k$ 为给定常量，$dis(u,v)$ 表示编号为 $u$ 的点到编号为 $v$ 的点最短路的长度）

0x3喵酱还认为这个"新图"如果为二分图，则 Ciste "有解"，如果"新图"不是二分图这个 Ciste "无解"。（如果您不知道二分图请翻到提示）

那么0x3喵酱想请您判断一下这个 Ciste 是否"有解"。

inputFormat:
第一行包含一个正整数 $ T $，表示有 $ T $ 组数据。
对于每组数据第一行包含两个正整数 $ n,k $。接下来 $ n-1 $ 行，每行包含三个正整数 $ x,y,v $ 表示编号为 $ x $ 的点到编号为 $ y $ 的点有一条边权为 $ v $  的无向边。
输入数据保证合法。

outputFormat: 对于每一组数据包含一行，如果“有解”输出 `Yes`，否则输出 `Baka Chino`。

samples:
Baka Chino
Yes
Yes
Baka Chino
Baka Chino

hint:
#### 样例解析

对于样例中的 **第一组** 数据：

原图：

![](https://cdn.luogu.com.cn/upload/image_hosting/9f9zh4b2.png)
新图：

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

新图不为二分图，故输出 `Baka Chino`。

对于 **第三组** 数据：

原图：

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

新图：

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

新图为二分图，故输出 `Yes`。

#### 数据规模与约定

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

- Subtask 1（16 pts）$\ $ ：$n \le 10$。
- Subtask 2（24 pts）$\ $ ：$n \le 100$。
- Subtask 3（8 pts）$\ $ ：$n \le 1000$。
- Subtask 4（28 pts）：图退化成一条链。
- Subtask 5（24 pts）：无特殊限制。

对于 $100\%$ 的数据，$n \le 10^5$，$T \le 10$，$v \le 1000$，$k \le 1000000$。

本题数据使用 [CYaRon](https://www.luogu.org/discuss/show?postid=11410) 生成。

#### 提示

**二分图** 又称作二部图，是图论中的一种特殊模型。设 $G=(V,E)$ 是一个无向图，如果顶点 $V$ 可分割为两个互不相交的子集 $(A,B)$，并且图中的每条边 $(i,j)$ 所关联的两个顶点 $i$ 和 $j$ 分别属于这两个不同的顶点集 $(i \in A,j \in B)$，则称图 $G$ 为一个二分图。（摘自[百度百科](https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E5%9B%BE/9089095?fr=aladdin)）

#### 说明

Minecraft OI Round 1 A

- Idea：0x3喵酱
- Solution/Std：0x3喵酱
- Data：0x3喵酱
- Tester：tarjin


title: 回文项链

background:
**数据已增强，各位不要再交暴力了。**

国庆节期间，哥哥送了小埋一条项链。（假的，日本人过什么国庆。）

然而小埋不太开心，她更想要买一部新手机玩游戏。

description:
不过小埋很快发现了项链的神奇之处。

我们把项链看作一个$n$元环，记作$s$，环上每个结点由大写'A'-'Z'中的一个字母组成。小埋惊奇的发现，环上有很多回文串！我们定义回文串为环上一个首尾不重叠的连续子串（即环上每个结点最多被使用一次），且满足**存在一个回文中心**$i$，使得$i$之前的若干个字符分别与其关于$i$中心对称的字符相同。

现在，小埋给出你这个环，并希望知道有多少长度为$l$的本质不同的回文串；我们认为两个回文串本质不同，当且仅当它们回文中心所在结点不同。

inputFormat:
第一行，两个数表示$n$，$l$；

接下来一行读入连续的$n$个字母，分别表示$s_1$，$s_2$，…，$s_n$；其中$s_i$与$s_i$ $_{mod}$ $_{n+1}$相邻。

outputFormat: 一行，表示长度为$l$的回文串的个数。

hint:
**本题每个测试点时限500ms**

对于$30$%的数据，$n<=20$；

对于$50$%的数据，$n<=200$；

对于$80$%的数据，$n<=2000$；

对于$100$%的数据，$n<=10^6$，$0<l<=n$且$l$为奇数。

**仔细读题，本题回文串与传统意义上的回文串不同。**


title: Cozy Glow之拯救小马国

background:
本题难度普及-，请noip两个组别的选手都把它AC（~~不然你noip省三都保不住了~~）

ps：三年OI一场空，day1T1见祖宗。。。

description:
Cozy Glow偷偷摸摸的造了一个魔法阵，这个魔法阵在吸取小马国的魔力，所以你得赶紧把它毁掉。

这个魔法阵由若干个神器组成，每个神器都有一个法力值，每两个神器之间也都有一个关联值。你要依次把这些神器拿走，但是，每拿走一个神器，你就会受到一定量的反噬，反噬的量为这个神器与其他还在神器的关联值乘以这个神器的法力值，为了减少反噬，tb148需要拿走每个神器，但由于他贪生怕死，他想让他受到的反噬值之和最小，现在tb148想知道，怎样拿走神器，才能让反噬值的和最小。

inputFormat:
第一行，神器的个数

第二行，每一个神器的法力值

接下来，将以邻接矩阵的形式输入神器之间的关联值

outputFormat: 最好的拿取方式所产生反噬值的和

hint:
神器个数<=1000

所有其他的值<=2000000

正对角线上的数保证都是零。。。


title: [RC-02] yltx 数对

background: yltx 又双叒叕出自己不会做的题了……

description:
yltx 定义若一个**素数**数对 $(x,y)$ 满足 $x\times y-3\times (x-y)$ 是素数，则称其为一个 yltx 数对。

他给了你 $T$ 对 $(x,y)$，请你检查他们是否为 yltx 数对。

数据以种子$(x_0,y_0)$的形式给出。

执行 $T$ 次 $x_0\leftarrow (7x_0+13)\ \mathrm{xor}\ (x_0\div 13-7)$，第 $i$ 次执行得到的数先取模 $10^4$、加上 $10^4$、取模 $10^4$，再加 $1$，就得到了第 $i$ 组数据的 $x$。这里的除法就是整除，把 $x_0$ 视作 32 位有符号整数。

用同样的方法得到 $y$。

数据生成模板：

```cpp
#include<bits/stdc++.h>
using namespace std;
int T,x_0,y_0;
int main() {
	scanf("%d%d%d",&T,&x_0,&y_0);
	while(T--){
		x_0=((7*x_0+13)^(x_0/13-7));
		y_0=((7*y_0+13)^(y_0/13-7));
		int x=(x_0%10000+10000)%10000+1,y=(y_0%10000+10000)%10000+1;
		//x,y即为一组(x,y)。
	}
	return 0;
}
```

inputFormat: 第一行三个整数 $T,x_0,y_0$。

outputFormat: $1$行，输出有几对数是 yltx 数对。


title: 【模板】舞蹈链（DLX）

background: 本题是舞蹈链模板——精确覆盖问题

description:
给定一个 $N$ 行 $M$ 列的矩阵，矩阵中每个元素要么是 $1$，要么是 $0$。

你需要在矩阵中挑选出若干行，使得对于矩阵的每一列 $j$，在你挑选的这些行中，有且仅有一行的第 $j$ 个元素为 $1$。

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

接下来 $N$ 行，每行 $M$ 个数字 $0$ 或 $1$，表示这个矩阵。

outputFormat:
一行输出若干个数表示答案，两个数之间用空格隔开，输出任一可行方案均可，顺序随意。

若无解，输出 `No Solution!`。

hint: 对于 $100\%$ 的数据，$N,M\leq 500$，保证矩阵中 $1$ 的数量不超过 $5000$ 个。


title: 【模板】扩展欧拉定理

background: 出题人也想写有趣的题面，可惜并没有能力。

description: 给你三个正整数，$a,m,b$，你需要求：$a^b \bmod m$

inputFormat: 一行三个整数，$a,m,b$

outputFormat: 一个整数表示答案

hint:
注意输入格式，$a,m,b$ 依次代表的是底数、模数和次数

【样例 $1$ 解释】
$2^4 \bmod 7 = 2$

【数据范围】
对于 $100\%$ 的数据，$1\le a \le 10^9$，$1\le b \le 10^{20000000}，1\le m \le 10^8$。


title: 完美数字

description:
给出两个数字集合$S$和$T$，其中元素均为$0$到$9$之间的整数。

定义“完美数字”为数位中包含$S$中所有的数且不包含$T$中任意一个数的数字。

例如$S=\{1,3,4\}$，$T=\{7,8\}$，则$1345$、$341166$、$4133129$都是完美数字。

而$13$、$8431$、$34171$都不是完美数字（因为$13$数位中不包含$4$，$8431$和$34171$中虽然包含了$1$、$3$、$4$这三个数但又包含$8$和$7$）。

求$[l,r]$中所有完美数字的和。

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

以下是$t$组数据：

第一行是两个整数$l$和$r$；

第二行首先一个正整数$|S|$，随后$|S|$个整数是$S$中的元素；

第三行首先一个正整数$|T|$，随后$|T|$个整数是$T$中的元素。

outputFormat: 对于每组数据输出一个整数，完美数字的和。


title: xtq的异或和

background: xtq在六年级的时候开始大量研究离散数学。这一天，他正在对着一张密密麻麻的图思索。

description:
xtq有一张$n$个点，$m$条边的无向连通图。第$i$条边连接$s_i,t_i$，权值为$w_i$。不保证无重边或自环。

xtq认为，如果存在一条从$u$出发，到$v$结束的路径，使得所有**被这条路径恰经过奇数次的边**的权值的异或和为$x$，那么点对$(u,v)$关于$x$是巧妙的。

现在，xtq问了你$q$个问题，每次询问有多少个不同的点对$(u,v)$关于$x$是巧妙的。注意$u$可以等于$v$，且如果$u \neq v$那么$(u,v)$与$(v,u)$是不同的。

inputFormat:
第一行，三个正整数$n,m,q$

接下来$m$行，每行三个整数$s_i,t_i,w_i$

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

outputFormat: $q$行，每行回答一次询问，输出对998244353取模后的结果。


title: 流量计算

background:
NOIP2018原创模拟题T7

NOIP2018原创模拟赛DAY2 T2

NOIP DAY1 T2 or DAY2 T2 难度

相关电学知识请参考“说明”中的“背景知识”。

description:
你看了复杂的电路图，发现在初高中学的电路元件数都目比较少，因此你希望设计一个程序来分析元件数目更多的电路图，并进行一些计算。

经过苦苦思考，你终于找到了描述电路图的方法：

1.电路图可以用$n$个节点，$m$条无向边的连通图来表示，其中$n$表示导线交汇点，$m$表示元件个数，且电路元件只有电源和电阻

2.图中没有自环，但可能有重边

3.电路图**最复杂的情况是并联中嵌套串联**，**不会出现更复杂的电路**，例如下面的情况都不会出现：

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

比如样例一便是一个满足条件的电路图（图片见样例一解释）

因为这是你第一次尝试，所以你决定电路中只包含电源与电阻，而且你决定计算电路中的最大电流与最小电流。

在理清思路后你就决定开始尝试了。

inputFormat:
共$m+1$行

第一行两个数 $n,m$，表示电路图抽象为$n$个节点，$m$条边的无向图

接下来$m$行，对于每一行：

前两个数为$x,y$，表示$x,y$之间有一个元件

接下来一个字符，如果为 $'P'$ 表示电源，且$x$方向为电源负极，$y$方向为电源正极，如果为 $'R'$ 表示电阻（均不含引号）

再接下来一个数字，如果为电源，表示电压（单位：伏特），否则表示电阻（单位：欧姆）

outputFormat:
两行

第一行输出最大电流值，保留两位小数

第二行输出最小电流值，保留两位小数

hint:
**背景知识：**

欧姆定理：$I=\frac{U}{R}$，其中$I$为电流，$U$为电压，$R$为电阻

串联：串联电路中电流相等，总电阻相当于电阻阻值之和

并联：并联电路中电压相等

串并联：即串联与并联结合

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

**样例一解释：**

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

如图，所有电阻等效电阻为$2Ω$，故最大电流为$\frac{6V}{2Ω}=3A$，在支线$2-3$或$2-4-3$中电流为$1.5A$，为最小电流

**样例二/三提示：**

样例二中所有电阻的等效电阻阻值为$\frac{6}{11}Ω$，且最小电流在支线$1-4-3$上，样例三中所有电阻的等效电阻阻值为$18Ω$

**数据范围：**

对于 30%数据，有：$n,m<=20$

对于 50%数据，有：$n<=10^3,m<=4\times 10^3$

对于 70%数据，有：$n<=5000,m<=2\times10^4$

对于100%数据，有：

1.$n<=2\times10^4,m<=5\times 10^4$，$0<=$电压$<=10^8$，$1<=$电阻$<=10^3$

2.只有有一个电源，电路不会有不规范的地方

3.最复杂的情况为并联中嵌套串联（如图A，当然支路可能更多，电阻串联数量有可能更多，但**支路不会出现并联**），保证**不会出现并联中再嵌套并联**（如图B的情况就不会出现）

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

**特殊约定：**

20%数据保证：电路为纯串联电路

另外20%数据保证：电路为纯并联电路


title: 黑暗打击

background:
注，此题和 CQOI 的鼹鼠不一样，请仔细看题！本题只是借用背景！

在茫茫宇宙中……

description:
有一群生物 ccj，他们在上次的星系中，发现了一群低等生物，于是想进行一波黑暗森林打击。这群低等生物即是 $\mathsf{Hilbert}$ 鼹鼠，生活在 $\mathsf{Hilbert}$ 星球，住在 $\mathsf{Hilbert}$ 曲线土壤内。
这群生物决定用最傻的办法——灌水，来淹死他们。现在“高等”生物想知道，对于 $n$ 阶的 $\mathsf{Hilbert}$ 曲线，从上往下灌水，能淹没几个单位面积？

这是 $1 \sim 4$ 阶的 $\mathsf{Hilbert}$ 曲线：

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

$h_1$，如最左图所示，是一个缺上口的正方形，这个正方形的边长为 $1$。 从$h_2$ 开始，按照以下方法构造曲线 $h_i$： 将 $h_{i-1}$ 复制四份，按 $2\times2$ 摆放。
把左上一份逆时针转 $90^{\circ }$，右上一份顺时针转 $90^{\circ }$，然后用三条单位线段将四分曲线按照左上-左下-右下-右上的顺序连接起来。如图所示，分别展示的是 $h_2$，$h_3$，$h_4$。加粗的线段是额外用于连接的线段。

灌水方式：

（显然这个是 $h_3$ 的灌水面积）绿色即为无法被灌到的地方，红色为可以灌到的地方，灰色为墙，所以答案是 $26$，即为样例1。

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

一个方格有水当且仅当在它的上，左，右方格中有至少一个方格有水，最上面一层的空格都有水。

注，此题要求对 $9223372036854775783$ 取模

inputFormat: 一个整数 $n$，表示这个洞穴是 $n$ 阶的 $\mathsf{Hilbert}$ 曲线。

outputFormat: 一个整数 $ans$，表示有 $ans$ 个单位面积被淹没。

hint:
**样例解释：**

自己数一数嘛……

$n \le 10^{10000}$

详细范围参见“标程”

数据均为手动构造，请注意常数！


title: 逃生之路

background: 还在茫茫宇宙中……

description:
还是这群生物 ccj，因为上次的打击太草率了，同时被他人侦测到了。在得知自己即将受到黑暗森林打击之后，选择逃离自己的家园。

他们的旅程计划在一条线上，其中，我们约定，一号点是他们的家园，有无限多个生物。每一个星球，都可以向之后连续的 $p$ 个星球进行转移。但由于每个星球的”体质“不同，每个星球所能接受的生物数量限定在一个范围 $[b,a]$ 之间。而且，由于星球本身资源匮乏，到达每一个星球都需要消耗星球一定的能源，补充飞船能源。并且又因为宇宙空间的复杂，所以这个能源是关于星球所接受生物数量的一个多项式。飞船年久失修，所以遇到任何星球必定前往去补充能源。

可惜这群生物有一个睿智的头领，他希望最终能有生物到达可以生存的星球，而且消耗的总能源要尽量少。那群生物对这个头领很失望，于是把任务丢给你。

请求出有生物到达可生存星球的情况下，最少的能源消耗是多少？

inputFormat:
第一行两个整数$n$和$p$，表示有$n$个星球（包括他们的家园和目的地），每次向后跳$p$个，保证 $p\le n-1$。

接下来有 $2\times n-2$ 行，偶数行有三个数字，$a_i$、$b_i$ 和 $f_i$，$i$ 从 $2$ 开始，表示第 $i$ 个星球能承载的生物数范围和这个星球是否能够生存，$f_i$ 为 $1$ 即能生存，$0$ 即为不能生存。

奇数行先有一个数字 $k$，表示这个多项式是  $k$ 次，接下来 $k+1$ 个整数，表示从高到低每一项的系数 $wi$。

outputFormat: 一个整数 $ans$ 表示花费最少的能源是多少，如果没有一个生物能到达，输出**"die"**（不包括引号）。

hint:
**样例解释**

样例一中从 $1\to 2$ 两个ccj，$2\to 3$ 两个 ccj，$2\times 2\times 30+2\times 17+28+2\times 2\times 47+2\times 56-60=422$

样例二由于没有任何一个星球可以生存，故 die。

$2\le n\le 100\quad |w|\le 100\quad 1\le b\le a\le 100\quad 1\le k\le 5\quad 0\le p\le 10$。

保证多项式函数二阶导函数在 $x∈[1,100]$ 时恒大于 $0$。


title: 赌神：决斗

background: **赌神 $\mathcal{CYJian}$，他回来了！**

description:
**$\mathcal{tomoo}$** 决定与 **$\mathcal{CYJian}$** 进行决斗！

已知 **$\mathcal{tomoo}$** 有 $\mathcal{N}$ 张扑克牌，每张扑克牌有一个$\mathcal{RP}$值$\mathcal{A_i}$， **$\mathcal{CYJian}$** 有$\mathcal{M}$张扑克牌，每张扑克牌有一个$\mathcal{RP}$值$\mathcal{B_i}$。

**$\mathcal{CYJian}$** 与 **$\mathcal{tomoo}$** 将会各自从他们的牌里任意取一段**连续区间**的牌决斗，谁的区间内的牌的$\mathcal{RP}$值的和更大，谁就赢了，请你帮忙求出 **$\mathcal{tomoo}$** 赢的概率。

inputFormat:
- 第一行 $2$ 个正整数 $\mathcal{N,M}$
- 第二行 $N$ 个正整数 $\mathcal{A_i}$
- 第三行 $M$ 个正整数 $\mathcal{B_i}$

outputFormat: 一个数表示 **$\mathcal{tomoo}$** 获胜的概率，如果答案可以表示成 $\frac{P}{Q}$ 的形式,则输出 $\frac{P}{Q}\%998244353$（不懂的左转[P3811](https://www.luogu.org/problemnew/show/P3811)）


title: DDOSvoid 的疑惑

background:
DDOSvoid 最近一直很痴迷于树形结构，尤其是可持久化喜羊羊灰太狼套红太狼树，可以 $O(\log)$ 维护你想维护的信息。

但是这只是一个理论数据结构，为了研究其如何实现，DDOSvoid 开始思考树的父亲和儿子之间的关系。

如果这个数据结构得到实现，那么这个世界就再也没有毒瘤题了。

但毕竟这个问题太难，所以我们先考虑下面的这个问题。

description:
给定一棵以 $1$ 为根的有根树，定义树的一个毒瘤集为一个集合，并且集合中任意两个元素之间不存在祖先与后代关系。

定义一个毒瘤集的毒瘤指数为集合内所有元素的价值之和。要求给定树的所有毒瘤集的毒瘤指数之和，答案对 $100{,}000{,}007$ 取模。

但这个问题太难了，所以我们考虑化简。

因为点的编号跟它毒瘤指数密切相关，所以我们将会再给出一个整数 $T$：$T = 1$ 表示 $i$ 号点的毒瘤指数为 $i$；$T = 0$，表示所有点的毒瘤指数都是 $1$。

inputFormat:
第一行两个整数 $n$、$T$，表示这棵树有 $n$ 个节点。

接下来 $n -1$ 行，每行两个整数 $x$ 和 $y$，表示有一条边，连接 $x$ 和 $y$。

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


title: 最短距离

description:
给出一个 $n$ 个点 $n$ 条边的无向连通图。

你需要支持两种操作：

1. 修改 第 $x$  条边的长度为 $y$ ；

2. 查询 点 $x$ 到点 $y$ 的最短距离。

共有 $m$ 次操作。

inputFormat:
输入共 $n+m+1$ 行：

第 $1$ 行，包含两个正整数 $n,m$，表示点数即边数，操作次数。

第 $2$ 行到第 $n+1$ 行，每行包含三个正整数 $x,y,z$，表示 $x$ 与 $y$ 间有一条长度为 $z$ 的边。

第 $n+2$ 到 $n+m+1$ 行，每行包含三个正整数 $op,x,y$，表示操作种类，操作的参数（含义见【题目描述】）。

outputFormat: 对于每次操作 $2$ 输出查询的结果。

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

对于 $100\%$ 的数据，保证 $z\in [0,5000]$。


title: 【CSGRound1】天下第一

background: 天下第一的 cbw 以主席的身份在 8102 年统治全宇宙后，开始了自己休闲的生活，并邀请自己的好友每天都来和他做游戏。由于 cbw 想要显出自己平易近人，所以 zhouwc 虽然是一个蒟蒻，也有能和 cbw 玩游戏的机会。

description:
游戏是这样的：

给定两个数 $x$，$y$，与一个模数 $p$。

cbw 拥有数 $x$，zhouwc 拥有数 $y$。

第一个回合：$x\leftarrow(x+y)\bmod p$。

第二个回合：$y\leftarrow(x+y)\bmod p$。

第三个回合：$x\leftarrow(x+y)\bmod p$。

第四个回合：$y\leftarrow(x+y)\bmod p$。

以此类推....

如果 $x$ 先到 $0$，则 cbw 胜利。如果 $y$ 先到 $0$，则 zhouwc 胜利。如果 $x,y$ 都不能到 $0$，则为平局。

cbw 为了捍卫自己主席的尊严，想要提前知道游戏的结果，并且可以趁机动点手脚，所以他希望你来告诉他结果。

inputFormat:
有多组数据。

第一行：$T$ 和 $p$ 表示一共有 $T$ 组数据且模数都为 $p$。

以下 $T$ 行，每行两个数 $x,y$。

outputFormat:
共 $T$ 行

$1$ 表示 cbw 获胜，$2$ 表示 zhouwc 获胜，```error``` 表示平局。


title: 数列求和

description:
给定 $n,a,k$，求：

$$\sum_{i=1}^n i^k a^i$$

答案对 $10^9 + 7$ 取模。

inputFormat: 输入一行三个非负整数 $n,a,k$。其中 $n, a \ge 1$。

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


title: [ICPC2019 WF] Miniature Golf

background:
### Warning: If you submit a malicious program, you will be banned.
### 警告：恶意提交本题将被封号。

description:
A group of friends has just played a round of miniature golf. Miniature golf courses consist of a number of holes. Each player takes a turn to play each hole by hitting a ball repeatedly until it drops into the hole.
A player's score on that hole is the number of times they hit the ball.
To prevent incompetent players slowing down the game too much, there is also an upper limit $l$ (a positive integer) on the score: if a player has hit the ball $l$ times without the ball dropping into the hole, the score for that hole is recorded as $l$ and that player's turn is over. The total score of each player is simply the sum of their scores on all the holes. Naturally, a lower score is considered better.

There is only one problem: none of the players can remember the value of the integer $l$. They decide that they will not apply any upper limit while playing, allowing each player to keep playing until the ball
drops into the hole. After the game they intend to look up the value of $l$ and adjust the scores, replacing any score on a hole that is larger than $l$ with $l$.

The game has just finished, but the players have not yet looked up $l$. They wonder what their best possible ranks are. For this problem, the rank of a player is the number of players who achieved an equal or lower total score after the scores are adjusted with $l$. For example, if the adjusted scores of the players are $3, 5, 5, 4,$ and $3$, then their ranks are $2, 5, 5, 3$ and $2$ respectively.

Given the scores of the players on each hole, determine the smallest possible rank for each player.

inputFormat: The first line of input contains two integers $p$ and $h$, where $p$ $(2 \leq p \leq 500)$ is the number of players and $h$ $(1 \leq h \leq 50)$ is the number of holes. The next $p$ lines each contain $h$ positive integers. The $j^{th}$ number on the $i^{th}$ of these lines is the score for player $i$ on hole $j$, and does not exceed $10^9$.

outputFormat: Output a line with the minimum possible rank for each player, in the same order as players are listed in the input.

translation:
### 题目描述
几个朋友玩了一场小型的高尔夫。这种小型的高尔夫是由若干个洞组成的。每个玩家轮流玩这个游戏，不停地击球直到球落到每个洞里。玩家在一个洞上的得分是他击球的次数。为了防止捣乱的玩家把游戏速度放慢太多，游戏规则中也会给一个上限$l$（一个正整数）来控制分数：如果一个玩家在一个洞上已经击球$l$次，但是球还没有落到洞里，那么这个玩家在这个洞上的得分就是$l$，并且这个玩家的回合就结束了。一个玩家的总得分就是他在各个洞上的得分之和。自然地，在这个游戏中，分越低越好。

但是有一个问题：没有玩家记得$l$的值。玩家们决定在玩的时候不设置$l$的值，允许每个玩家不断击球，直到球掉到洞里。玩完游戏，他们准备设置$l$的值，并更改那些在洞上的分数大于$l$的值。

游戏结束了，但他们还没有设置$l$。他们想知道自己的最佳排名是什么。一个人的排名是在所有人中，得分比这个人低或和这个人相等的人数（包含自己）。比如，当五个人的得分分别是 $3,5,5,4,3$，那么他们的排名就是 $2,5,5,3,2$。

给你每个玩家在每个洞上的得分，为每一个玩家求出最小的可能的排名。

### 输入格式

第一行：两个整数 $p$ 和 $h$，$p$（$2 \le p \le 500$）是玩家个数，$h$（$1 \le h \le 50$）是洞的个数。

接下来$p$行，每行$h$个正整数，第$i$行第$j$列的数表示第$i$个玩家在第$j$个洞上的得分，这些数都不会超过$10^9$。

### 输出格式

输出 $p$ 行，每行一个正整数，第 $i$ 行表示第 $i$ 个玩家的最小排名。

### 说明/提示

来源：ICPC World Finals 2019 Problem J

题目名称：Miniature Golf

hint: Source: ICPC World Finals 2019 Problem J: Miniature Golf.


title: 口袋里的纸飞机

background:
现在我来到自己的故事难以用语言描绘的中心。文字的匮乏感从现在开始体现出来，因为描绘任何事物都要以交谈者共有的认知为前提，而我所经历的是比任何生活都更上一层的体验。先贤们在向普罗大众描绘世界之外的事物时往往运用宏大的概念。中国的道学家说天有九霄。《吠陀经》提到我们生存的土地只是千万重复制中的一个。爱斯基摩人则认为万物由一枚巨卵孵化而出。一个更恰当的比喻是所谓狄拉克之海，也即是全部空间和时间的上方和外部。虽然用有限的话语不可能描述一个无限的实体，但我记住了它的一部分，或许是最重要的一部分：

我看见无限宽阔的海面和无限广袤的天穹，两者在无穷远处的地平线相接。视野的最中央站着一个紫色长发的女孩。我的身份和她不同：我是受她邀请而来的访客，海上的女孩才是这里的居民，或者说囚徒。正如我们不能随意造访世界之上的世界，她也永远不能和我们的生活有任何一点的交集。我明白自己在这里不会待上太久，而她把我招来只能为了一个理由。于是我听见了自己的声音在海面上回响，消散进虚无之中：

“我会记住你。”

她对我露出笑容。白色的光芒再一次亮起，女孩的身影好似被无形的火焰灼烧一样逐渐消散。我明白自己留不住这一刻，于是我哭了。使我哭泣的并不只是永恒的离别，还有对这个曾经在无尽的时间中陪伴过我们的孩子的怜惜和忏悔。
我感到无限崇敬，无限悲哀。

——西酱《口袋》

description:
一个大小为$n$的数列$\{a_i\}$，每个数都在范围$[1,R]$中

对于每种数列，可以生成一个$n\times n$的网格，其中格子$(i,j)$中的数为$a_i\times a_j \mod P$

比如，如果数列是$\{1,2,3\},P=5$，则生成的网格为
```
1 2 3
2 4 1
3 1 4(因为2*3%5=1,3*3%5=4)
```

对于一个网格，定义法法值为其中不同的数个数，比如上面那个就是4个数，即$\{1,2,3,4\}$。

现在你需要对所有数列的法法值的和对$10^9+7$取模

inputFormat: 第一行输入正整数$n,P,R$


title: 好时光

background:
# 如果您不想在读题上消耗太多时间，请直接滑到页面最底部查看简述版题面。

光阴似箭，日月如梭。时光如流水般，一刻不停地冲刷着一切。转眼间，初三已经到来了。巨量的作业，紧张的考试，无不使小L和小K准备NOIP的时间越来越少……

description:
逃不掉的一天还是来了，小L一个人坐在教室里，看着窗外发呆。

操场还没修完，天上空空荡荡的，夕阳的余晖刚刚在灰色的高楼旁涂上一抹血红，瞬间便消失了，不留下一点痕迹。飒飒的秋风从窗外吹进来，教室里响起了哗啦啦的书页被翻动的声音，书被翻到了画上了小L和小K共同的涂鸦的那一页。被揉成一团的成绩条在桌上滚来滚去，像难解的心结。天上没有一颗星星——大概是因为心头吹不散的乌云吧。

小L的文化课月考考炸了，NOIP初赛也极度不理想，很可能是进不了复赛了。

至于心头吹不散的乌云，就让它在那里吧，反正自己也没有机会去改变什么了。

如果不是初三的紧张的节奏，大家大概不会这么轻易地分道扬镳吧？ 只见一个又一个昔日的队友离开了机房。

唉，自己也大概要离开机房了吧。小L想到。

这时，他想起了与小K相处的每一个好时光。

从初一的军训中一个个挺拔的身影，到讲台前两个激烈讨论着的声音,省赛时颓废的场景，以及一起在机房奋斗过的日日夜夜……

忆起这些好时光，他的心里暖暖的。他觉得和小K在一起的每一秒都是值得珍惜的好时光。

这时，小K来到了小L的身边，知道了小L的愿望。小L想对他与小K相处的每一秒计算一个值得珍惜的价值，如果把这些价值都加起来，小L就会将这些好时光都记在心里，心情也会好起来了。

小L是这样计算一个时间的价值的：他先将每一秒从 $1$ 开始顺序编号，再将时间（这个秒数）转换为时-分-秒形式。由于某种原因，小L的一分钟只有 $k$ 秒（此处应有滑稽），所以小L认为一小时也只有 $k$ 分钟。你可以认为小L将秒数转成了$k$ 进制。由于小L没有那么毒瘤，所以这里的 $k$ 都是整数。然后他观察这个 $k$ 进制数，找到其中最长的连续等差数列的长度（只考虑单个数码组成的连续的区间的情况，也就是说如 $10$ 进制下的 $123456789101112$ 不能称为等差数列） ，将其记为这一秒的价值。

小K非常想帮他算出这些秒（从 $1$ 秒到 $n$ 秒）的总价值，以安慰伤心的小L。但是这个总秒数 $n$ 实在是太长太长了，以至于小K要超过一秒的时间才能算出一秒的价值，这样小L和小K在一起的时间就可以**无限延长**了。小L非常希望能这样，但是显然他们并没有这么多这么多的时间。

小K找到了精通 $OI$ 的你。为了避免计算过程中秒数还在增加，你需要在 $1$ 秒钟内计算出答案。由于答案可能会很大，小L愿意接受这个数取模 $19260821$ 后的结果。

inputFormat: 输入共一行，两个整数 $n$ 和 $k$。输入的$n$为十进制表示形式。

outputFormat: 输出共一行，一个整数，为价值之和取模 $19260821$ 后的值。

hint:
样例 $\#1$ 解释：

$1$到$5$转成$3$进制分别是$1,2,10,11,12$，每个数的价值恰好是它的长度，所以总价值为$1+1+2+2+2=8$。

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

对于另外 $10\%$ 的数据， $k=10$；

对于 $40\%$ 的数据， $2\le k\le 20,1\le n\le k^{10}$；

对于 $100\%$  的数据， $2\le k\le 60,1\le n\le k^{18}$ 。

** 数据没有梯度！！！ **

# 小L教你学数学

**等差数列**：等差数列是指从第二项起，每一项与它的前一项的差等于同一个常数的一种数列，这个常数叫做等差数列的公差。 ** 公差可以为任意实数。 ** 也就是说，这个数列可以是递增的，递减的，或者恒为定值的（公差为$0$）。

## 简述版题面：

给出 $n,k$ ， 求 $\sum_{i=1}^n f(i,k)$ 的值， $f(i,k)$ 定义为将十进制整数 $i$ 表示为 $k$ 进制时写成一个数列的形式中的最长连续子串为等差数列的长度。答案取模 $19260821$ 。

## 一些闲话

由于小L被赶去学文化课了，所以本题题面的扩写就咕咕咕啦！


title: 重排DL

background: Dancing Line 的关卡排序总是很玄学。

description:
这天小埋给 Dancing Line 中关卡排序制定了一个新的规则：假设某一关为第 $n$ 个发布的关卡，那么它的位置 $a_n$ 满足 $a_{n+1}=(\sqrt[k]{a_n-n}+2)^k+n+1$，且第一个发布的关卡总是排在第一，即 $a_1=2$。

但是这样显然会出现一个问题：许多位置是空关卡。所以小埋又给出了一个限制条件：调整 $k$，使得第 $n$ 个关卡满足 $a_n \equiv b\pmod{m}$。现在小埋给了 $n,m,b$，求最小满足条件的**整数** $k$。

inputFormat: 第一行，三个数 $n,m,b$。

outputFormat: 一个数，表示最小的 $k$；如果不存在最小 $k$，则输出 `INF`。

samples:
3 8 2
INF


title: [MtOI2018] 情侣？给我烧了！（加强版）

background:
FFF

本题原版：[P4921](https://www.luogu.com.cn/problem/P4921)

description:
有 $n$ 对情侣来到电影院观看电影。在电影院，恰好留有 $n$ 排座位，每排包含 $2$ 个座位，共 $2n$ 个座位。

现在，每个人将会随机坐在某一个位置上，且恰好将这 $2n$ 个座位坐满。

如果一对情侣坐在了同一排的座位上，那么我们称这对情侣是和睦的。

你的任务是求出共有多少种不同的就坐方案满足**恰好**有 *k* 对情侣是和睦的。

两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，一共会有 $(2n)!$ 种不同的就坐方案。

由于结果可能较大，因此输出对 $998244353$ 取模的结果。

inputFormat:
输入包含多组数据。

输入的第 $1$ 行包含 $1$ 个正整数 $T$，表示数据的组数。

接下来 $T$ 行，每行包含 $2$ 个正整数 $n,k$。

outputFormat:
输出共 $T$ 行。

对于每组输入数据，输出共 $1$ 行，包含 $1$ 个整数，表示恰好有 $k$ 对情侣和睦的就坐方案数。

hint:
### 子任务

对于 $10 \%$ 的数据，满足 $1 \leq T \leq 10, 1 \leq n \leq 5$。

对于 $40 \%$ 的数据，满足 $1 \leq n \leq 3 \times 10^3$。

对于 $100 \%$ 的数据，满足 $1 \leq T \leq 2 \times 10^5, 1 \leq n \leq 5 \times 10^6, 0 \leq k \leq n$。

### 题目来源

[MtOI2018 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T2 加强版

出题人：Imagine

50167


title: [THUPC 2023 决赛] Freshman Dream

description:
小 J 正在学习矩阵乘法。

一旁的小 L 告诉他：只要将两个矩阵对应的位置乘起来，那就能得到两个矩阵的乘法了。

这当然是不对的，但是小 L 要继续骗小 J。为此，她需要在自己的 OJ 上放一道矩阵乘法题，使得这样的矩阵乘法也能得到正确的答案。

因为小 L 的 OJ 跑的很慢并且空间限制也很小，所以这道矩阵乘法题的答案都是 $\bmod 2$ 意义下的。

现在小 L 开始造数据。她先随机生成了一个 $n\times n$ 的矩阵 $A$，具体地，每一个元素以 $\frac 12$ 的概率为 $1$，剩下的概率为 $0$，且这些事件相互独立。现在，她还要设计另一个 $n\times n$  的 $01$ 矩阵 $B$，使得 $AB_{ij}\equiv A_{ij}B_{ij}\pmod 2$。

小 L 试图随机生成矩阵，但是找不出什么满足要求的矩阵；她试图构造几个矩阵，发现只会构造全 $0$ 矩阵，这太明显了。现在，她将生成数据的重任交给了你，你需要给出一个满足要求的 $B$，同时为了不让大家看出数据有猫腻，她还额外要求了 $B$ 里面恰好有 $k$ 个 $1$。

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

输入的第一行包含两个正整数 $n,k$，表示矩阵的大小和题目中的 $k$。

接下来 $n$ 行，每一行 $n$ 个整数 $a_{ij}$ 表示 $A$ 的元素。

outputFormat:
输出到标准输出。

如果没有任何 $B$ 满足要求，输出一行一个整数 $-1$。

否则，先输出一行一个整数 $1$，然后输出 $n$ 行，每行 $n$ 个 $\{0,1\}$ 中的整数来表示 $B$ 矩阵的元素。如果有多个可能的 $B$，输出其中一个即可。

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

这里的 $A$ 是单位矩阵，构造的 $B$ 也是单位矩阵，乘积也为单位矩阵。同时，将对应位置相乘也为单位矩阵，并且 $B$ 中恰有 $k=3$ 个 $1$，故满足要求。

本样例中 $n$ 不为 $100$，但保证所有测试数据中 $n$ 均为 $100$。

**【数据范围】**

对于所有测试数据，$n=100$，$0 \le k \le n^2$，$a_{ij}\in \{0,1\}$，所有 $a_{ij}$ 均为独立均匀随机。

**【题目来源】**

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023> 查看。


title: 父子

background:
上演在各大学男生寝室的日常 $:$

$A :$ “我没带纸，快来厕所救我！”

$B :$ “叫爸爸。”

$A :$ “爸爸！”

$............................................$

$A :$ “我没钱了，能借我点吗。”

$B :$ “叫爸爸。”

$A :$ “爸爸！”

一个月后、

$B :$ “能把钱还给我吗。”

$A :$ “叫爸爸。”

$B :$ “爸爸！”

description:
对于全国各大大学的男生寝室，总是有各种混乱的父子关系。

那么假设现在我们一个男生寝室有不同的 $n$ 个人，每个人都至多有一个“爸爸”，可以有多个“儿子”，且有且只有一个人没有“爸爸”(毕竟是室长，还是要给点面子，当然了，室长人人当嘛)。

那么现在问题来了，对于一个有 $n$ 个人的寝室，最多可能存在多少种父子关系，当然每个人之间都必须要有直接或间接的父子关系。

inputFormat:
第一行一个非负整数 $t$，表示有 $t$ 组数据。

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

outputFormat:
共 $t$ 行，每行一个整数，求关系个数。

由于答案可能较大，则我们需要输出答案对 $10^9+9$ 取模的值。


title: [ICPC2019 WF] Traffic Blights

description:
Cars! Where do they come from? Where do they go? Nobody knows. They appear where roads have been built, as if out of nowhere. Some say that no two cars are alike. Some say that if you look closely, you can see the pale ghosts of miserable humans inside them, trapped forever—particularly in
the morning and late afternoon. What scientific eye could frame their fearful symmetry?

Well, yours, hopefully. As part of your government's Urban Traffic Control department, you are trying to write a paper on local traffic congestion. It is too dangerous to observe cars in the wild, of course, but you have been given some data on the traffic lights along your town's Main Street, and you would like to do some theoretical calculations about how well-synchronized they are.

Main Street is set out on a line, with traffic lights placed at various points along it. Each traffic light cycles between red and green with a fixed period, being red for $r$ seconds, then green for $g$ seconds, then red for $r$ seconds, and so on. The values of $r$ and $g$ may be different for different traffic lights. At time $0$, all the lights have just turned red.

Assume that an "ideal" car mystically appears at the west end of Main Street at a uniformly random real-valued time in the interval $[0, 2019!]$ (where $k!$ is the product of the first $k$ positive integers), driving eastwards at a slow crawl of $1$ meter/second until it hits a red light. What is the probability that it will make it through all the lights without being forced to stop? If it does hit a red light, which one is it likely to hit first?

Write a program to answer these questions.

inputFormat:
The first line of input contains an integer $n$ ($1 \leq n \leq 500$), the number of traffic lights. Each of the following $n$ lines contains three integers $x$, $r$, and $g$ describing a traffic light, where $x$ ($1 \leq x \leq 10^5$) is the position of the light along Main Street in meters, and $r$ and $g$ ($0 \leq r, g$ and $1 \leq r + g \leq 100$) are the durations in seconds of the red and green portions of the light's period (so the light is red from time $0$ to $r$, from time $r + g$ to $2r + g$, and so on).

The west end of Main Street is at position $0$, and the lights are listed in order of strictly increasing position.

outputFormat: For each of the $n$ lights, output a line containing the probability that this light will be the first red light an "ideal" car hits. Then output a line containing the probability that an "ideal" car makes it all the way without stopping. Your answers should have an absolute error of at most $10^-6$.

translation:
### 题目描述

Main 街坐落在一条东西向的直线上，上面有若干位置互异的红绿灯。每个红绿灯以某个固定周期在红绿之间循环。更具体地，它会先持续 $r$ 秒的红灯，再持续 $g$ 秒的绿灯，再持续 $r$ 秒的红灯...如此往复。对于不同的红绿灯，$r$ 和 $g$ 的值可能不同。在时刻 $0$，所有的红绿灯都恰好刚变为红灯。

假设此时有一辆“理想”汽车在前 $2019!$ 秒中的一个随机实数时刻神秘地出现在了 Main 街的最西端，向东以 $1~ \rm m/s$ 龟速行驶，直到遇到第一个红灯时停下，那么它有多大的概率通过所有红绿灯？如果它停下来了，那么它在每个红绿灯处停下的概率有多大？

### 输入格式

第一行一个整数 $n$（$1\le n\le 500$） 表示红绿灯的数量。

接下来每行三个整数 $x,r,g$（$1\le x \le 10^5$，$0\le r,g$ 且 $1\le r+g\le 100$）， 描述一个位置在从西往东 $x$ 米处的，红灯持续时间为 $r$，绿灯持续时间为 $g$ 的红绿灯。

最西侧即 $x=0$ 处，保证 $x$ 严格递增。

### 输出格式

前 $n$ 行第 $i$ 行每行输出一个实数表示在第 $i$ 个红绿灯停下的概率。

第 $n + 1$ 行输出一个实数表示通过所有红绿灯的概率。

你需要保证绝对误差不超过 $10^{-6}$.

hint: Source: ICPC 2019 World Finals.


title: 规划

background: 经过长期的艰苦奋斗，${\rm TimeTraveller\ }$终于成功进入了理想的学校。

description:
作为吃货的${\rm \ TimeTraveller}$，入学的第一件事不是去报到，而是去食堂调查菜品。但是由于各种原因，本学期食堂的菜品很少，而且食堂制定了几天的菜谱，那么这个学期里，以后每天提供的菜品都会**按照菜谱轮流循环进行**。听到这件事，${\rm TimeTraveller\ }$的内心当然是崩溃的，但是他还是希望每天能吃的不那么重复，于是${\rm \  TimeTraveller\ }$决定只要**和前一天吃的菜不重复**就行了，但是身为吃货的${\rm \ TimeTraveller\ }$当然也不想饿肚子，所以**每天至少都要吃一道菜**。

${\rm TimeTraveller\ }$想要知道他有多少种合法的规划方案，但是他发现这实在是太多了，于是他来求助你，希望你能编写一个程序帮他计算。

inputFormat:
第一行三个正整数$n,m,k$，分别表示这个学期有$n$天，总共有$m$种菜品，学校制定了$k$天的菜谱（所有菜品从$1$到$m$编号，保证$n ≥ k$）。

接下来$k$行，每行第一个数$p$表示这一天学校准备了$p$道菜，紧接着有$p$个数，表示这一天的$p$道菜分别是哪几道（保证$p$不会超过$m$，且这$p$个数都是不重复的）。

outputFormat: 输出合法方案的数量，由于答案可能过大，你只需要输出答案对$1e9+7$取模后的值。

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

方案$1$：第一天吃$1,3$号菜品，第二天吃$2$号菜品，第三天吃$1,3$号菜品；

方案$2$：第一天吃$1,3$号菜品，第二天吃$2$号菜品，第三天吃$3$号菜品；

方案$3$：第一天吃$1,3$号菜品，第二天吃$2$号菜品，第三天吃$1$号菜品；

方案$4$：第一天吃$3$号菜品，第二天吃$2$号菜品，第三天吃$1,3$号菜品；

方案$5$：第一天吃$3$号菜品，第二天吃$2$号菜品，第三天吃$3$号菜品；

方案$6$：第一天吃$3$号菜品，第二天吃$2$号菜品，第三天吃$1$号菜品；

方案$7$：第一天吃$1$号菜品，第二天吃$2,3$号菜品，第三天吃$1$号菜品；

方案$8$：第一天吃$1$号菜品，第二天吃$3$号菜品，第三天吃$1$号菜品；

方案$9$：第一天吃$1$号菜品，第二天吃$2$号菜品，第三天吃$1,3$号菜品；

方案$10$：第一天吃$1$号菜品，第二天吃$2$号菜品，第三天吃$3$号菜品；

方案$11$：第一天吃$1$号菜品，第二天吃$2$号菜品，第三天吃$1$号菜品。

#### 数据范围：

- 对于$20\%$的数据，$n≤ 5,m≤ 7,k≤ 5$；

- 对于$45\%$的数据，$n≤ 50000,m≤ 7,k≤ 7$；

- 另有$10\%$的数据，$n≤ 10^7,m≤ 2,k= 1$；

- 对于$70\%$的数据，$n≤ 10^7,m≤ 7,k≤ 7$；

- 对于$100\%$的数据，$n≤ 10^7,m≤ 7,k≤ 300$。


title: [yLOI2018] 大美江湖

background:
> 细雪飘落长街，枫叶红透又一年。
> 不只为故友流连，其实我也恋长安。
> 听门外足音慢，依稀见旧时容颜。
> 故事几经悲欢，结局都与你有关。

——银临《大美江湖》

本题原名《空间复杂度》。

description:
扶苏听着《大美江湖》，在剑三里控制着他的人物炮姐来到了长安。

长安城中有一个任务，需要扶苏进入地下的机关道，机关道是的地图一个 $n$ 行 $m$ 列的矩形方格图，每个方格内部都有一些怪物或者药水。扶苏操控着炮姐在机关道中游荡。有些时候他希望问问你他的角色一扶苏一有多少攻击力、防御力以及丢失了多少血量。

地图中共有三种药水和一种怪物，分别用字符 `R`，`Q`，`Y`，`M` 代表。其中：

- 字符 `R` 代表生命药水，可以减少炮姐丢失的 $10$ 点 血量 $HP$。如果本身损失的 $HP$ 不大于 $10$，则损失的血量会变成 $0$。
- 字符 `Q` 代表力量药水，可以增加炮姐 $5$ 点攻击力 $ST$。
- 字符 `Y` 代表防御药水，可以增加炮姐 $5$ 点防御力 $DE$。
- 字符 `M` 代表怪物，会对炮姐造成伤害。

每只怪物都有三个属性，分别是血量 $HP_0$，攻击力 $ST_0$，防御力 $DE_0$。为了~~降低验题人工作量~~题目难度，所有怪物的属性都是相同的。

一旦走到怪物格，遭遇战将开始。扶苏一定会打死怪物，但是怪物也会对扶苏造成一定的伤害。具体的，怪物对扶苏造成的伤害为

$$\max(1, \left\lceil \frac{HP_0}{\max(1, ST - DE_0)}\right\rceil \times \max(1, ST_0 - DE))$$

其中 $\max(a, b)$ 代表取 $a$ 和 $b$ 中较大的数，$\lceil x \rceil$ 代表**不小于** $x$ 的最小整数。下标为 $0$ 的值代表怪物的参数，不带下标值的为角色的参数。

你会收到 $q$ 次操作，每次操作要么是一次查询，要么是一次移动。

对于移动，你会再获得一个数字参数，这个参数只可能是 $1/2/3/4$ 其中的一个，代表炮姐向地图的**左/右/上/下**移动。向上移动代表角色所在的行数减一，列数不变，其他方向类似。

对于查询，需要你输出炮姐损失了多少血量，以及当前的攻击力和防御力分别是多少。

请注意，如果多次进入同一个格子，那么格子上的药水会被重复拾取，小怪也会再次出现。即你可以认为离开一个格子以后该格子会恢复原状。

请注意，如果初始位置有怪物，也不会发生战斗，如果初始位置有药水，也不会将之捡拾。

inputFormat:
每个测试点有且仅有一组测试数据。

输入的第一行是两个用空格隔开的整数，代表地图的行数 $n$ 和列数 $m$。

第 $2$ 到第 $(n + 1)$ 行，每行有一个长度为 $m$ 的字符串，第 $(i + 1)$ 行的第 $j$ 个字符 $C_{i, j}$ 代表第 $i$ 行第 $j$ 列的方格中物品/生物。特别的，若 $C_{i, j}$ 为一个字符 `.`，则意味着该处没有任何东西，但是可以通行。

第 $(n + 2)$ 行有三个用空格隔开的整数，分别代表怪物的血量 $HP_0$，攻击力 $ST_0$ 和防御力 $DE_0$。

第 $(n + 3)$ 行有两个整数，分别代表角色初始所在的行数 $x$ 和列数 $y$。

第 $(n + 4)$ 行有两个用空格隔开的整数，代表角色初始的攻击力 $ST$ 和防御力 $DE$。

第 $(n + 5)$ 行是一个整数，代表操作的次数 $q$。

第 $(n + 6)$ 到第 $(n + q + 5)$ 行，每行首先有一个整数 $op$，代表本次操作的类型。

- 若 $op = 1$，则本次操作是一次查询操作。
- 若 $op = 2$，则本次操作是一次移动，一个空格后会有一个整数 $d$，作为移动的参数。

outputFormat: 对于每次查询操作，输出一行三个用单个空格隔开的整数，分别代表角色损失的血量 $HP$，以及当前的攻击力 $ST$ 和防御力 $DE$。


title: 忘情

background:
 “为什么要离开我！”

 “因为你没玩儿转！”

 “我玩儿转了！”

 “那好，你现在就给我维护这么一个式子！”

 “为什么要出这么毒瘤的东西。”

 “为了恶心你。”

 “......”

$…………………………….$

description:
你的 $npy$ 为了恶心你，特地请了四位大神和一个辣鸡！

 $\rm hdxrie$ 说：“我们得求和。”于是有了 $\sum\limits_{i=1}^{n}x_i $ 。

 $\rm Imagine$ 说：“我们得有平均数。”于是有了 $\bar x $ 。

 $\rm TimeTraveller$ 说：“我们得有加减乘除。”于是有了一些恶心的组合。

 $\rm Althen·Way·Satan$ 说：“我们还得有平方。”于是我们将它平方。

最垃圾的 $\rm ZredXNy$ 说：“那我帮你们整合一下。”

于是，我们得到了这么一个式子 $:$

$$\frac{\left((\sum\limits_{i=1}^{n}x_i×\bar x)+\bar x\right)^2}{\bar x^2}$$

我们定义一段序列的值为这个，其中  $n$为此序列的元素个数。

我们给定一段长度为 $n$ 的序列,现在要求将它分成 $m$ 段，要求每一段的值的总和最小，求出这个最小值。

inputFormat:
第一行两个正整数，分别为 $n$，$m$，定义见题面。

接下来一行为 $n$ 个正整数，依次给出这个序列的每个元素的值 $x_i$ 。

outputFormat: 一个整数，求出这个最小值。

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


title: 转换

background: $\rm hdxrie\ $最近在为新建的宇宙购物中心编写价格系统。

description:
购物中心汇聚了来自各个星球的商品，但是由于不同的星球采用的进制各不相同，导致商品价格计算起来比较困难，因此价格系统是必不可少的。

由于甲方所给的期限太短，$\rm hdxrie\ $便找到你来做他的助手，他只需要你帮忙编写一个进制转换的程序就行，其它的各个系统版块全部由他自己负责，你能在规定期限内写出转换程序吗？

inputFormat:
第一行一个数$n$，$n$表示有多少个物品的价格需要转换。

接下来$n$行，每行三个数字$a,l,r$和一个价格串$S$。

$a$表示这个价格串为$a$进制数（保证$a$不为$-1,0,1$），你需要把它转化为$l$到$r$的所有进制（请自动跳过输出为$-1,0,1$这些进制的情况）。

由于价格为实数，所以难免会出现小数，并且若一个小数为循环小数，我们会将小数的循环节使用 <,> 括起来。

如果不是循环小数则没有尖括号，如果没有小数部分则没有小数点，保证不会出现尖括号之间没有数字情况。

保证循环节以及循环节前面的小数部分都是最短的，例如$10$进制下的$0.123123\cdots$，那么所给的读入形式为$0.$<$123$>，保证不会出现类似于$0.1$<$231$>或$0.$<$123123$>这些情况。

对于正进制$a$，保证不会出现循环节为$a-1$的情况，例如$10$进制不会出现$0.$<$9$>这样的输入，但是负进制没有这样的要求。

为了方便转换，当用正进制表示负数的时候，规定在价格前加上负号，但是由于负进制既可表示正数也可表示负数，所以规定负进制前不允许出现负号。

规定任意进制的每一位不能为负，规定大于$9$的值按照大写字母从小到大编写。

outputFormat:
对于每一个需要转换的价格，在给定范围内按进制从小到大的顺序输出转换为该进制后的价格串（请自动跳过输出为$-1,0,1$这些进制的情况）。

对于输出格式你也应该严格按照上面输入格式的要求输出每一个价格串。

hint:
- 对于$5\%$的数据，保证没有小数部分，$1≤n≤20,2≤a≤36,2≤l≤r≤36$；

- 对于$15\%$的数据，保证没有小数部分，$1≤n≤100,2≤|a|≤36,-36≤l≤r≤36$；

- 另有$15\%$的数据，保证转换前和转换后都是有限小数，$1≤n≤550,2≤a≤36,2≤l≤r≤36$；

- 另有$20\%$的数据，$1≤n≤550,2≤a≤36,2≤l≤r≤36$；

- 对于$100\%$的数据，$1≤n≤550,2≤|a|≤36,-36≤l≤r≤36$；

保证所有数据中，价格的绝对值都不会超过$2^{63}-1$，且转换前和转换后的小数部分的字符串长度均不超过$\left\lfloor\log_{|a|}2^{62}\right\rfloor$（$a$表示进制，括号不计入长度）。


title: 反射

background:
最近$\rm \ TimeTraveller\ $玩了一个十分好玩的游戏，通过摆放能量发射器，来攻击敌人的飞船。

但是$\rm \ TimeTraveller\ $十分手残~~以及脑残~~，总是玩不过十分简单的关卡，所以他想请你帮助他。

description:
这个游戏是这样的，你有$k$个$\alpha$能量发射器启动器，可以启动任何$k$个在一个初始平台上$\alpha$发射器，然后$\alpha$发射器会向北偏东$45^\circ$方向上发射能量光束，能量值为$\alpha_i$。在有场地里面有$n$块悬浮的平台，这些平台上有的装有两种能量发射器$\alpha$发射器和$\beta$发射器的其中一种，功能如下：

- 对于$\alpha$发射器，如果它装在平台上方，它会向北偏东$45^\circ$方向上发射能量光束，能量值为$\alpha_i$；如果装在下方，它会向南偏东$45^\circ$方向上发射能量光束，能量值为$\alpha_i$。

- 对于$\beta$发射器，不管装在什么地方它会同时向北偏东$45^\circ$和南偏东$45^\circ$发射能量光束，能量值为$\beta_i$。

但是，悬浮平台上的发射器并不会自己启动，必须在有能量光束击中它所在的平台上时才会启动，且这个发射器发射的能量为给定的值（注意一束光击中这些平台，只有在这个能量光束的来的路径上没有该击中平台提供的能量时这些平台的发射器就会启动，每被击中一次就发射一次，如下图，1号发射给2号2号激活，其中一个击回1号，此时1号不会再发射一次（也就是能量不会再次叠加））

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

你在最开始只能启动初始平台上的能量发射器中的$k$个（这$k$个是依次启动的，且每个只能发射一次，但是其它地方的发射器可以发射多次）。

将地图抽象为二维平面直角坐标系，其中$x=0$的直线为地面（光束到达地面会消失,但是如果地面有平台则优先击中平台），那么所有的平台包括初始平台均平行于$x$轴，敌人的飞船可以看做为一个平行于$y$轴的，两个端点为$(wx,sy)$和$(wx,ty)$，当一条光束击中飞船它便会受到光束来的这条路径上的所有能量值的和的伤害然后光束就会消失。（光束击中其它平台并不会反弹，而是会被平台吸收作为能量来启动发射器）。

请你求出在启动哪些开始的$\alpha$发射器，使得让飞船受到的伤害最大，请你求出这个最大值。

inputFormat:
第一行两个正整数$k,n$，表示你能启动$k$个开始的发射器，总共有$n$个平台。
第二行四个整数$x_1,x_2,y,v$，表示初始平台位置，初始平台上每一个整点有一个$\alpha$发射器能发射初始能量为$v$的能量光束（如$x_1=1,x_2=3,y=1$时，有$(1,1),(2,1),(3,1)$三个初始位置的$\alpha$发射器）。
第三行三个整数$wx,sy,ty$，表示敌人飞船位置。
下面$n$行，每行描述了一个平台，格式如下：

- $0\ x_l\ x_r\ y$表示一个空的平台
- $1\ x_l\ x_r\ y\ x_p\ w_i\ 0/1$表示在$(x_p,y)$的位置一个$\alpha$发射器在$(x_l,y)\sim (x_r,y)$的平台上，发射能量为$w_i$，最后的$0$或$1$表示在平台的上方还是下方，$0$为上方，$1$为下方。
- $2\ x_l\ x_r\ y\ x_p\ w_i$表示在$(x_p,y)$的位置一个$\beta$发射器在$(x_l,y)\sim (x_r,y)$的平台上，发射能量为$w_i$。

outputFormat: 一行一个整数表示最大的伤害值。

hint:
#### 样例解释：

样例$1$如图：

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

最优为橙色那个$25$，绿色的为$10$。

样例$2$如图：

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

只有橙色那条打出来为$242$，其他两条只有$98$。

#### 数据范围：

- 对于$30\%$的数据$0\leq n\leq 20,1\leq k\leq 3$；
- 对于$40\%$的数据所有平台（不包括飞船）的长度和不超过$10^6$；
- 对于$60\%$的数据$0\leq n\leq 200,1\leq k\leq 50$；
- 对于$70\%$的数据$0\leq n\leq 2000,1\leq k\leq 2000$；
- 对于$100\%$的数据$0\leq n\leq 20000,0\leq k\leq 20000$，坐标$0 \leq y\leq 10^9$的，坐标$0\leq x\leq 10^9$，所有的能量值的值均在$0\sim 10^4$内，且保证每个发射器必定在一个平台上，且平台长度与敌人飞船的长度大于等于$1$。保证最开始的平台长度不超过$10^5$，且所有的平台不会重叠；

- 还有$20\%$的额外数据同$100\%$，只是$n\leq 10^6$；

输入较大，建议使用较快的读入方式。


title: 逃离

background: $\ \rm Althen\ $和$\ \rm hdxrie\ $掉入了二维空间。

description:
其实这个空间并不是无限的，而是半径有限的圆盘。

起初，他们两个都在圆心处，为了找到出口，他们两个决定分开行动，只要找到出口，便会离开。不过，若是其中一个人找到了出口，另一个还在二维空间内，那么这个空间就会因为不平衡而崩塌。所以他们两个只能一起离开。

其中：
- $\rm Althen\ $ 可以拐弯，还会一直拐来拐去，不过只能水平或者竖直移动。
- $\rm hdxrie\ $ 只能沿任意一条直线走，不能拐弯。

$\rm Althen\ $ 全程在水平向右的平均速度可以用函数 $A(x)$ 表示，在竖直向上的平均速度可以用函数 $B(x)$ 表示。$\rm hdxrie\ $ 全程移动的平均速度可以用函数 $C(x)$ 表示。而参数 $x$的取值范围也有讲究，为 $[L,R]$。

现在，他们两个想问你，他们有可能一起离开这个二维空间吗？如果可以，这个参数 $x$ 的值可以是多少？

inputFormat:
输入共四行。

第一行三个整数：$La$，$Lb$，$Lc$，和两个实数：$L$，$R$；
分别代表三个函数的长度和参数 $x$ 的取值范围。

第二行 $\ La+1\ $ 个整数，按升幂表示 $A(x)$ 的系数。
第二行 $\ Lb+1\ $ 个整数，按升幂表示 $B(x)$ 的系数。
第二行 $\ Lc+1\ $ 个整数，按升幂表示 $C(x)$ 的系数。

outputFormat: 若有解，输出一行一个实数表示答案；否则输出 `Inconsistent!`。

hint:
【数据范围】
对于$10\%$的数据，$L=R$；
另有$20\%$的数据，$La=Lb=Lc=1$；
另有$30\%$的数据，$[L,R]$ 内最多只有一个参数 $x$ 合法；
对于$100\%$的数据，$0≤La,Lb,Lc≤10^5$，$0≤a_i,b_i,c_i≤9$，$L≤R$，$|L|,|R|≤3$；

答案精确度需要保证带入原来的三个函数，合法误差不超过 $10^{-5}$，误差若是大于 $10^{-5}$ 会判断为错误答案，建议输出 **保留八位以上小数**。

###### $\color{#EEE}{\tt {Notice\ that\ SPEED\ is\ VECTOR.(High\ school\ physics)}}$


title: 按钮

background: Ada被关在了一个房间里。

description:
房间的铁门上有一个按钮，还有一个显示屏显示着“1”。
旁边还有一行小字：“这是一个高精度M进制计算器，每按一次按钮，屏幕上的数便会乘以K。当个位数再次变为1时，门就开了。”
由于Ada急于出去，所以你要在1s之内求出她的最小按键次数。

inputFormat: 一行，两个整数M和K。

outputFormat:
一行一个数字，表示最小按键次数。
如果无论Ada按多少次都无法让门打开，输出"Let's go Blue Jays!"（不含引号）。

samples:
6 26
Let's go Blue Jays!

hint:
对于30%的数据，$2\leq M,K\leq10^4$。
对于100%的数据，$2\leq M,K\leq2\times 10^{9}$。
update：我们不认为个位为11,21,...为问题的解（例如，11在16进制下记为B）


title: 贫穷

background:
LHF 最大的特点就是贫穷。
LHF 最大的爱好就是看购物节目。

这天他又在看购物节目了。
他在节目里看到一款新型文本编辑器，~~除了价钱以外~~非常适合他这样的穷人使用。

因为……它能够计算打印成本！
（这里的打印成本是与出现过的字母的种类数相关的）

他十分心动，要求你实现这个功能。

description:
这个文本编辑器支持以下操作：
 - $\texttt{I x c}$，在第 $x$ 个字母后面插入一个 $c$。
 - $\texttt{D x}$，删除第 $x$ 个字母。
 - $\texttt{R x y}$，反转当前文本中的区间 $[x,y]$。
 - $\texttt{P x}$，输出初始文本中第 $x$ 个字母在当前文本中的位置。特别地，若不存在，输出 $0$。
 - $\texttt{T x}$，输出当前文本中第 $x$ 个字母。
 - $\texttt{Q x y}$，输出当前文本中区间 $[x,y]$ 内出现过的字母的种类数。

inputFormat:
第一行，两个整数 $n,m$，分别表示初始文本长度和操作个数。
第二行，一个长度为 $n$ 的字符串，表示初始文本。
以下 $m$ 行，每行表示一个操作。

outputFormat: 对于所有需要输出的操作，输出结果。

samples:
12 6
kimiwakawaii
R 2 4
P 4
D 1
I 0 w
T 3
Q 3 10

hint:
**数据范围：**

对于 $20\%$ 的数据，$n \le 100$。
对于 $50\%$ 的数据，$n \le 10000$。
对于 $100\%$ 的数据，$1 \le n,m \le 10^5$，文本涉及的字母仅包含小写字母。

**样例解释：**

 1. 文本不变，但初始文本中第 $2$ 个字母与第 $4$ 个字母的位置交换。
 2. 当前第 $2$ 个字母是初始文本的第 $4$ 个字母。
 3. 文本变为 $\texttt{imiwakawaii}$。
 4. 文本变为 $\texttt{wimiwakawaii}$。
 5. 这个字母为 $\texttt{m}$。
 6. 这段文本为 $\texttt{miwakawa}$，包含的字符种类的集合为 $\{\texttt{a},\texttt{i},\texttt{k},\texttt{m},\texttt{w}\}$，元素个数为 $5$。


title: 查房

background:
答疑请到： https://www.luogu.org/discuss/show?postid=79498

$sqn$是个电子游戏爱好者，但很遗憾的是，他的母上大人没收了他的手机。为了过一把游戏瘾，$sqn$到各个$oier$的宿舍借手机玩......

description: 当然，这是一件风险很大的事，因为van恶的静静和晶晶会定时查房，被抓到可就惨了。当然$oier$们不会束手就擒，他们组织了一个反查房联盟。这个联盟由$n$个宿舍(点)组成，某些宿舍之间有边权为1无向边连接，共有$n-1$条无向边。每个点都有一个概率$k_i$，表示在颓废的几率为$k_i$。如果老师查到某个房间，而这个房间的人在学习，他就会发出警报，距离他1的人收到警报后都会在下一时刻无条件停止颓废，之后恢复原状态，如果查到在颓废的人，则那个人不会发出警报而是GG（可以当作这个人死了，再也不会发出信号）。静静和晶晶一起行动，查一遍房间。$sqn$只会在$ztz11$，$AK$爷，$floatiy$的房间里颓废，他想知道，在哪个房间里颓废被查到几率最小？当然，由于他在颓废，所以自然不可能算几率啦，他将这个问题交给了你，请你帮他来解决这个问题

inputFormat:
第一行，两个数字$n$，$m$，表示房间总数 和查房次数
第二行，3个数字$a,b,c$，分别表示 $ztz11$，$AK$爷和$floatiy$的房间号
下面$m$行，每行第一个数字$k$,表示当前时刻老师们要查几间房，后面$k$个数字，表示静静和晶晶要查的房间号
下面$n-1$行，每行$2$个数，表示会相互发出警报的两个人
最后一行，$n$个数，表示每个人颓废的几率

outputFormat:
第一行，一个整数，表示$sqn$应该去的最佳的房间，如果几率相同，请按$ztz11>AK>floatiy$的优先级输出

第二行，一个4位小数，表示$sqn$安全颓废的几率

hint:
对于 $30$% 的数据，$n,m<=10$,

对于另 $10$% 的数据，$k=1$

对于 $100$% 的数据，$1<=m,n<=1000000$,确保每个人被且仅被查一次

感谢@XiaoX，@Monster_qi帮助出数据&验题


title: 血小板与凝血因子

background:
为了尽快修复伤口，血小板们正在搬运凝血因子。它们（没毛病）正在讨论怎么分配，因为它们太可爱了，所以就让你来解决这个问题。

![](https://i.loli.net/2018/10/05/5bb7372e781b1.jpg)

description:
血小板们有两种不同的容器，第一种容器每个容器中只能装同一种凝血因子，第二种容器每个容器中每种凝血因子最多出现一次。为了方便，血小板们想用**同一种**容器装下所有的凝血因子。

换句话说，把 $n$ 个正整数 $a_1$ ~ $a_n$ 分成一些不相交的集合 $S_1$ ~ $S_m$，满足以下两个条件**之一**：
1. $\forall a_i,\ a_j\in S_k,\ k\in [1,\ m]$ 有 $a_i=a_j$
2. $\forall a_i,\ a_j\in S_k,\ k\in [1,\ m],\ i\neq j$ 有 $a_i\neq a_j$

因为血小板的数量比较少，所以你要把所有的凝血因子装到尽量少的容器里。它们想知道，如何划分能使容器的总数最小。

inputFormat:
第一行，一个正整数 $n$，表示凝血因子的个数。

第二行，$n$ 个正整数 $a_i$，分别表示凝血因子的种类。

outputFormat:
第一行，两个正整数，第一个正整数代表容器数的最小值 $m$，第二个正整数代表所用容器的种类（$1$ 或 $2$）。

接下来的 $m$ 行，每行第一个正整数 $c_i$ 代表这个容器装的凝血因子个数，后面的 $c_i$ 个数代表这个容器中装的每个凝血因子的种类。

输出任意一组合法的最优解即可，输出顺序不限。

hint:
$1\le n\le 1000,\ \ 1\le a_i\le 10^9$。

## 样例解释

### 样例一：

选用第二种容器，分别放入 $\{4\}$，$\{3,1,2,4,5\}$，$\{4\}$，这是一组可行的最优解，更改三个容器的顺序、容器 $2$ 中 $5$ 个凝血因子的顺序可以得到另外的最优解。

### 样例二/三：

这两组样例输入相同，既可以选用第一种容器，也可以选用第二种容器。

两组样例的输出分别为一组可行的最优解，改变顺序可以得到另外的几组最优解。

### 样例四：

选用第一种容器，分别放入 $\{3,3,3\}$，$\{2,2\}$，这是一组可行的最优解，更改两个容器的顺序可以得到另一组最优解。


title: 小埋与扫雷

background:
小埋总是在家中打游戏，一天，她突然想玩Windows自带的扫雷，在一旁的哥哥看见了，想起了自己小时候信息课在机房玩扫雷的日子，便兴致勃勃地开始教小埋扫雷。然而，小埋还是不明白 $\mathrm{3bv}$（Bechtel's Board Benchmark Value，每局将所有非雷的方块点开所需最少左键点击数，参见[扫雷网的教程](http://saolei.net/BBS/Title.asp?Id=227) ）怎么算，于是她找到了你。

![](https://i.loli.net/2018/10/04/5bb5bd6aefb70.jpg)

description:
小埋会告诉你一盘扫雷，用一个 $n\times m$ 的矩阵表示，$1$ 是雷 ，$0$ 不是雷，请你告诉她这盘扫雷的 $\mathrm{3bv}$ 。

周围八格没有“雷”且自身不是“雷”的方格称为“空格”，周围八格有“雷”且自身不是“雷”的方格称为“数字”，由“空格”组成的八连通块称为一个“空”。$\mathrm{3bv}=\ $周围八格没有“空格”的“数字”个数$+$“空"的个数。

如果看不懂上面的计算方式，可以看题目背景中给出的教程，或者看下面的样例解释。

注：[八连通](https://baike.baidu.com/item/%E5%85%AB%E8%BF%9E%E9%80%9A)

inputFormat:
第一行有两个整数 $n$ 和 $m$，代表这盘扫雷是一个 $n \times m$ 的矩阵。

后面的 $n$ 行每行有 $m$ 个整数，表示这个矩阵，每个数字为 $0$ 或 $1$，$1$ 代表是雷，$0$ 代表不是雷。

outputFormat: 一个整数，代表这盘扫雷的 $\mathrm{3bv}$ 。


title: 朋也与光玉

background:
> 一つ一つの光は小さくでも、たくさん集まればきっととても不思議な大きな力になるはず。

渚的离世、汐的离去...朋也的人生几乎陷入了一片黑暗。

但是，这会是结束吗？

![](https://i.loli.net/2018/10/04/5bb5f64297c70.jpg)

description:
光坂小镇是一个由 $n$ 个点（编号为 $1$ ~ $n$），$m$ 条有向边构成的图，每个节点上都有一个光玉，光玉共有 $k$ 种，编号为 $0$ ~ $k-1$。

为了使一切改变，朋也需要找齐全部的 $k$ 种光玉。他可以从任意一个节点出发，在图上任意行走，但不会经过同一个节点两次，每碰到一个光玉便会将其收集，收集到 $k$ 个光玉后，即经过了 $k$ 个节点后，便不会继续收集。请设计一种方案，使得朋也能够收集全部的 $k$ 种光玉，且走过的路径长度最短。

换句话说，每个点一个颜色，找到一条最短的点数为 $k$ 、恰好经过全部 $k$ 种颜色的路径。你需要求出这条路径的长度。

inputFormat:
第一行，三个正整数 $n,\ m,\ k$，分别代表节点个数、边的条数、光玉的种类数。

第二行，共 $n$ 个正整数 $a_1$ ~ $a_n$，其中 $a_i$ 代表 $i$ 号节点的光玉种类编号。

接下来 $m$ 行，每行三个正整数 $u_i,\ v_i,\ w_i$，表示 $u_i$ 到 $v_i$ 有一条长度为 $w_i$ 的有向边。

outputFormat: 输出一行，若有解则输出一个正整数表示满足条件的最短路径的长度，若无解则输出"Ushio!"（不含引号）

hint:
$2\le n\le 100$，$1\le m\le n(n-1)$，$2\le k\le 13$，$1\le w_i\le 10^7$

保证图中没有重边、自环。

## 样例解释

样例一，$3\rightarrow 6\rightarrow 7$ 为一组最优解。

样例二，无解。

样例三，最优解为 $4\rightarrow 5\rightarrow 2$。


title: 美樱的颜料

background:
在春辉去美国留学之后，美樱时常感到寂寞。为了排解寂寞，她在画画时总是对颜料有着特殊的要求。

![](https://i.loli.net/2018/10/10/5bbd8d3178ee9.jpg)

description:
美樱共有 $n$ 种不同的颜料，编号依次为 $1$ ~ $n$，每种颜料只能使用一次。开始画一幅画时，美樱可以任意选择一种颜料使用。之后，美樱每次都会选择一种颜料 $i$ 使用，满足使用颜料 $i$ 后已经使用了的颜料的编号的 $gcd$（最大公约数）尽量大，即：

> 设现在已经使用了的颜料编号构成的集合为 $A$，若$\ \exists\ i,\ j\notin A,\ i,\ j\in [1,\ n],\ gcd(A,\ i)>gcd(A,\ j)$，那么就不能选择颜料 $j$。

如果有多种满足条件的颜料，美樱可以任意选择一种使用。每使用完一种颜料，美樱就会获得当前使用了的所有颜料的编号的 $gcd$ 的快乐值。

现在美樱想画一幅使用 $m$ 种颜料的画，她能够获得的最大快乐值之和是多少？

inputFormat: 共一行，两个正整数 $n,\ m$，分别代表颜料的种类数和美樱要使用的颜料数。

outputFormat: 一个正整数，美樱能获得的最大快乐值。

hint:
$1\le m\le n\le 10^7$

## 样例解释

样例一：`6 3 5 2`为一组最优解，每次获得的快乐值分别为`6 3 1 1`

样例二：`15 10 5`为一组最优解，每次获得的快乐值分别为`15 5 5`


title: 绫小路的特别考试

background:
>  这世界上「胜利」便是一切。无关乎过程。
要付出多少牺牲都无所谓。只要最后我「胜出」那就行了。

![](https://i.loli.net/2018/10/06/5bb879f4ac370.jpg)

description:
一场新的特别考试来临了，这次的考试内容是（wan e de）文化课，但有所不同的是，考试中允许学生使用对讲机。然而，对讲机的接收范围是有限的（每个对讲机都能发送无限远，但是只能接收到接收范围内的信号），所以不是所有学生都能接收到其他同学的广播。

考试时，共有 $n$ 名学生坐成一排（从左至右依次编号为 $1$ ~ $n$），绫小路自己坐在第 $c$ 号位置。每名学生都有一个能力值 $w_i$。绫小路已经给每名学生安排了一个接收范围为 $d_i$ 的对讲机。

每名学生可以直接做出难度**不超过**自身能力值的**所有**题目，一旦一名学生凭能力做出某道题，他就会把这道题的做法进行广播。一名坐在位置 $i$，有接收范围为 $d_i$ 的对讲机的学生，可以接收到 $[i-d_i,\ i+d_i]$ 范围内所有学生的广播，若这个范围内有人公布了做法，则他将会做这道题，并也会把这道题的做法进行广播。

绫小路会问你一些问题：当一道题目难度为 $x$ 时，有多少学生会做这道题？由于绫小路想隐藏实力，他可能会修改自己的能力值。这两种操作分别用以下两种方式表示：

- $1\ x$，表示询问当一道题目难度为 $x$ 时，有多少学生会做这道题。

- $2\ x$，将绫小路的能力值修改为 $x$，即将 $w_c$ 修改为 $x$。

---

形式化描述（与上文同义）：

> 给你两个长为 $n$ 的数列 $w_{1..n}$ 和 $d_{1..n}$，以及一个 $w_c$ 可修改的位置 $c$。现在有两种操作（共 $m$ 次）：
- $1\ x$ 表示一次询问：设 $f_i=\begin{cases}1\quad(w_i\ge x)\\1\quad(\exists\ j \in [i - d_i,\ i + d_i],\ f_j=1)\\ 0\quad(otherwise)\end{cases}$，这里的 $f_i$ 定义中引用了 $f_j$，$\ \ \ \ $所以 $f_{1..n}$ 是会不断更新的，直到无法继续更新时，计算这次询问的答案为 $\sum\limits_{i=1}^nf_i$。
- $2\ x$ 表示一次修改：把 $w_c$ 修改为 $x$。

inputFormat:
由于数据量太大，为了避免读入耗时过长，使用**伪随机数生成器**的方式输入，并**强制在线**。

**建议你忽略输入格式，直接使用下面提供的数据生成器模板，了解具体的生成过程对你来说是不必要的。**

第一行，三个正整数 $n,\ m,\ c$，分别代表学生的总人数，操作总数和绫小路所在的位置。

第二行，五个整数 $\mathrm{seed},\ \mathrm{mind},\ \mathrm{maxd},\ \mathrm{mfq},\ k$。

> 此处的 $\mathrm{mind},\ \mathrm{maxd}$ 仅用于生成初始的 $d_{1..n}$，下文中调整 $d_p$ 所用的 $t$ 可能不在 $[\mathrm{mind},\ \mathrm{maxd}]$ 范围内。

接下来的 $k$ 行，每行两个整数 $p,\ t$，表示调整第 $p$ 号同学的对讲机接收范围（即 $d_p$）为 $t$。

> 若一名同学的对讲机接收范围被调整多次，以**最后一次**为准。

---

** 数据生成器模板：**

```cpp
#include <cstdio>

unsigned long long seed;
int n, m, c, mfq, mind, maxd, k, w[2000001], d[2000001];

inline int randInt() { seed = 99999989 * seed + 1000000007; return seed >> 33; }

void generate()
{
	// 在读入种子后生成初始的 w 数组和 d 数组.
    for (int i = 1; i <= n; i++) { w[i] = randInt() % n; }
    for (int i = 1; i <= n; i++) { d[i] = randInt() % (maxd - mind + 1) + mind; }
}

void getOperation(int lastans, int &opt, int &x)
{
    // 生成一次操作的参数 opt 和 x, lastans 表示上一次询问的答案, 初始值为 0.
    if ((0ll + randInt() + lastans) % mfq) { opt = 1; } else { opt = 2; }
    x = (0ll + randInt() + lastans) % n;
}

int main()
{
    scanf("%d %d %d", &n, &m, &c);
    scanf("%llu %d %d %d %d", &seed, &mind, &maxd, &mfq, &k);
    generate();
    for (int i = 1; i <= k; i++)
    {
        int p, t;
        scanf("%d %d", &p, &t);
        d[p] = t;
    }
    // 从这里开始，你可以使用生成的 w 数组和 d 数组.
    int lastans = 0, finalans = 0;
    for (int i = 1; i <= m; i++)
    {
        int opt, x;
        getOperation(lastans, opt, x);
        if (opt == 1)
        {
            // 在这里执行询问操作，并用答案的表达式替代下面的 ___.
            finalans = (finalans * 233ll + ___) % 998244353;
            lastans = ___;
        }
        else
        {
            // 在这里执行修改操作.
        }
    }
    printf("%d\n", finalans);
    return 0;
}
```

outputFormat:
令 $ans_i$ 表示第 $i$ 次询问（操作 $1$）的答案，$T_i=\begin{cases}(T_{i-1}\times 233+ans_i)\mod 998244353\quad(i\ge 1)\\0\quad(i=0)\end{cases}$

设 $q$ 表示询问（操作 $1$）的个数，你只需要输出一个整数 $T_q$。


title: 薇尔莉特的打字机

background:
> 只要客人有意向，不论身在何处，都能上门服务。我是自动手记人偶服务——薇尔莉特·伊芙加登。

![](http://wx3.sinaimg.cn/large/dcec95dfgy1fme08p9eopj20xv0hyq5q.jpg)

description:
薇尔莉特的打字机用了太久，按键已经开始老化了，因此有时候按键会没有反应。而薇尔莉特总是盲打，因此按键没反应她也不会注意到。一天，她用这台打字机继续完成一封还没写完的信。

现在告诉你这封信已经写好的部分以及薇尔莉特想进行的操作，薇尔莉特想进行的操作有两种：
1. 在信的末尾输入一个大写字母
2. 进行一次退格

退格用小写字母 $\mathrm{u}$ 表示，即删除当前信中的最后一个字符，当然，在信为空时退格没有任何作用。

薇尔莉特会按顺序按下她想按的按键，而每次薇尔莉特按下一个键（输入一个大写字母或进行一次退格），都有可能没有反应（即这次操作无效）。请问，最后打出来的信有多少种可能呢？（空信也算信）

当然薇尔莉特只想知道可能数对 `0x125E591`（十六进制） 取模的结果。

inputFormat:
第一行两个正整数 $n,\ m$ 分别表示已经写好的信的长度和薇尔莉特想进行的操作数（字符个数+退格个数）。

第二行一个长度为 $n$ 的字符串表示已经写好的信，保证该串中的每个字符都为大写字母。

第三行一个长度为 $m$ 的字符串表示薇尔莉特想进行的操作，保证该串中的每个字符都为大写字母或 $\mathrm{u}$。

outputFormat: 一个整数表示答案对 `0x125E591` 取模的结果。

hint:
$1\le n,\ m\le 5\times 10^6$

## 样例解释

样例一：可能的 $9$ 种信为：`A`,`AA`,`AB`,`AAB`,`ABA`,`ABB`,`ABAA`,`ABAB`,`ABAAB`。

样例二：~~太多了，略~~。

样例三：可能的 $3$ 种信为：`空`,`U`,`UU`。


title: [USACO01OPEN] Earthquake

description:
一场地震把约翰家的牧场摧毁了， 坚强的约翰决心重建家园。 约翰已经重建了 $n$ 个牧场，现在他希望能修建一些道路把它们连接起来。研究地形之后，约翰发现可供修建的道路有 $m$ 条。碰巧的是，奶牛们最近也成立一个工程队，专门从事修复道路。而然，奶牛们很有经济头脑，如果无利可图，它们是不会干的。

奶牛们关注的是挣钱速度，即总利润和总施工时间的比值。约翰和奶牛达成了协议，奶牛负责修建道路，将所有牧场连通，而约翰需要支付 $f$ 元。每条道路都有自己的施工时间和建造成本。连接两个相同的牧场的道路可能有多条。保证所有的牧场必定是可连通的，不过也有可能一些道路的建造成本之和会超过 $f$。

请帮助奶牛们选择修复哪些道路，才能使单位时间的利润最大？

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

第二行到第 $m+1$ 行，第 $i+1$ 行表示第 $i$ 条道路的信息。每行有四个整数 $u_i,v_i,c_i,t_i$， $u_i$ 和 $v_i$ 表示这条道路连接的牧场编号，$c_i$ 表示修建道路的成本，$t_i$ 表示道路修建所需要的时间。

outputFormat: 第一行，一个保留四位小数的浮点数，表示奶牛们能挣到的最大单位时间利润，如果奶牛们无钱可赚，则输出`0.0000`。

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

奶牛们可以选择连通最后四条道路，则总时间为 $16$，总成本为 $83$，所以单位利润为 $\dfrac{17}{16}=1.0625$。

#### 数据规模与约定

对于 $100\%$ 的数据，保证
- $1 \leq n \leq 400$，$1 \leq m \leq 10000$，$1 \leq f \leq 2 \times 10^9$。
- $1 \leq u_i,v_i \leq n$，$1 \leq c_i,t_i \leq 2 \times 10^9$。


title: xtq玩魔塔

background:
**已添加样例解释**

在小学五年级的时候，$xtq$迷上了各种奇奇怪怪的魔塔。
关于魔塔游戏的背景：https://baike.baidu.com/item/%E9%AD%94%E5%A1%94/861619?fr=aladdin

对于题意理解可能并没有任何微小的作用

description:
$xtq$现在正在玩一个魔塔。这个魔塔十分特殊，不是由正方形格子构成的，而是一个$n$个点，$m$条边的无向图，而且每条边上都会有一个怪物。$xtq$经过了重重阻拦，现在到达了一个奖励层。

在这层内，所有怪物都不会让$xtq$掉血，但是对于每一个怪物如果$xtq$不到一定血量他就无法攻击这个怪物。每一个点上还有一个宝石，宝石的种类有很多，但是如果$xtq$到了一个点但是他已经拥有了这种宝石，他是不能捡起的。他现在想要知道从这个魔塔的一个点到另一个点所需要的最小血量是多少，还要知道如果他从一个点到达这个魔塔，以某个血量能够捡到的宝石数量是多少。还有一件事令$xtq$十分头疼：这个魔塔由于一些神秘的力量，可能宝石的种类会发生变化。保证如果$xtq$的血量无穷大，他就可以走到这一层的任何地方。

inputFormat:
第一行三个数$n,m,q$代表点数，边数和操作数量

第二行n个数，代表每个点上宝石的种类

下面m行每行三个数$u,v,t$，代表$u$和$v$之间有一条路，路上有一个需要$t$点血量才能击杀的怪物

然后q行每行三个数$opt,x,y$

$opt=1$时将$x$点的宝石改成第$y$种

$opt=2$代表查询从$x$点要到达$y$点所需的最小血量

$opt=3$代表查询从$x$点到达魔塔，血量为$y$能捡到多少宝石

outputFormat: 对于每一个$2$操作和$3$操作，输出一行答案


title: 基地建设

background: 在茫茫宇宙中……

description:
有一群生物 ccj，他们发现了一个超星系群。其中有 $n$ 个恒星，$m$ 条双向星际航线，每条星际航线都需要消耗 $val_i$ 的燃料值。两个恒星不属于同一个星系当且仅当他们之间没有任何航线，且没有任何路径可以到达。只有每个恒星才可以为飞船补充燃料。每次航行的路线都是一条简单路径。由于燃料系统过于简陋，每个燃料罐只能用于一次航行。他们的首长 ccj 想在其中一个恒星上建立基地。但是 ccj 花了太多钱购买高速飞船，没有太多钱购买燃料罐，所以他对于两个恒星之间的航行一定选择最经济的航行方式，购买最小的燃料罐。他想问你，在基地要备多少的燃料总量，使得在任意一个恒星上建立基地都能从那个基地分别到达那个星系的其他所有恒星。

但是，这个超星系群发生了战争，一些黑洞改变了这里的空间结构。这群生物只知道每条航线花费的燃料值，找不到连接的两个恒星。但是他们的科学家发现了一个性质：每个战争有一个标志值 $q$，航线有不同的排列方式，对于其中一种排列，第 $i$ 条航线连接着 $((q^{i} \bmod 2^{32}+i \times val_i) \bmod n+n) \bmod n+1$ 和 $((q^{i} \bmod 2^{32}-i \times val_i) \bmod n+n) \bmod n+1$ 两个恒星。**运算方式为无符号整型运算**。如果连接的两个恒星一样，说明科学家计算有误，忽略这条航线。ccj 的目标改变了。他想知道对于所有星系的构成情况，最少需要准备多少的燃料总量，使得在这种结构中，在任意一个恒星上建立基地都能分别到达该结构下那个恒星所处星系的其他所有恒星。

你需要输出航线排列顺序。

inputFormat:
第一行三个正整数 $n$，$m$ 和 $q$，表示有 $n$ 个恒星，$m$ 条航线，战争标志值 $q$。

第二行 $m$ 个正整数 $val_i$，表示第 $i$ 条航线消耗 $val_i$ 的燃料值。

outputFormat:
第一行一个正整数 $ans$，表示 ccj 需要你求的数值。

从第二行到第 $m+1$ 行，每行输出一个整数，第 $i$ 行输出这个排列下的 $val_{i-1}$。

hint:
**样例解释：**

这 $5$ 条航线分别是：

$2$ 与 $2$ 往返，花费燃料 $5$

$1$ 与 $1$ 往返，花费燃料 $4$

$3$ 与 $3$ 往返，花费燃料 $2$

$2$ 与 $2$ 往返，花费燃料 $3$

$1$ 与 $2$ 往返，花费燃料 $1$

前四条航线被忽略，故有四个恒星系，$\{1,2\},\{3\},\{4\},\{5\}$

基地建在 $1$ 时，从 $1$ 到 $2$ 需要购买燃料量为 $1$ 的燃料罐，可以发现，没有其他比这个更优的答案。

$2 \le n \le 100\quad 1 \le m \le 40\quad 0 \le q \le 10^9\quad 0 \le val_i \le 1000$

你的答案只需要比std优秀或者和std一样且方案正确即可

1~4数据都为最优答案，5~10数据都为次优答案

~~此题会给出第10个数据的输入~~
[输入数据](https://www.luogu.org/paste/3xkq6bar)

详细范围参见”标程“

数据均为随机构造，请注意常数！


title: 愤怒的XiaoX

background:
### 答疑请到 https://www.luogu.org/discuss/show?postid=79498

在几天前的模拟赛上，$XiaoX$又双叒叕$AK$了

他想卡一卡大家，于是他出了下面的一道题：

description:
给定一个序列，你要维护下列操作：

$1$ $l$ $r$ $k$，表示从$l$到$r$的数字最后$k$位按位取反

$2$ $l$ $r$ $k$，表示从$l$到$r$的数字最后$k$位进行翻转

$3$ $w$ 表示查询$w$这个位置的值

为了降低这道题的难度，我们做出以下规定：

对于序列的操作，我们的$k$在一定范围内是一定的

我们一共会有$t$个$k$

每个$k$后面跟着一些操作

这些操作的$k$（修改的位数）都是相同的

###  按位取反定义：

比如说，一个数的二进制表示是：

```
10100111
```

对后5位取反后变成：

```
10111000
```

###  翻转定义：

比如说，一个数的二进制表示是：

```
10100111
```

对后5位翻转后变成：

```
10111100
```

inputFormat:
第一行，两个整数$n$，$t$,表示序列长度和$k$的数量

第二行，$n$个数，表示原始序列

下面$t$组操作，对于每组操作第一行两个数$q_i$，$k_i$，表示操作数量和在这些操作中$k$的值

下面$q_i$行，表示该组操作

outputFormat: 对于每个$3$操作，输出一行一个整数，表示答案的大小


title: [RC-02] 游戏

description:
Shik 大佬发明了一种游戏。这种游戏在 $N \times N$ （$N$ 为偶数）的网格上进行，如图所示（左上角为 $(1,1)$，右下角为 $(N,N)$）：

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

这种游戏的规则如下：
- 初始局面为：在最左边一列和最右边一列的网格上分别放置着红方和蓝方的棋子，在最上面一行左半部分和最下面一行左半部分也放置着红方的棋子，在最上面一行右半部分和最下面一行右半部分也放置着蓝方的棋子；
- 红方先走，蓝方后走；
- 有一方只剩下 $N\div 2$ 颗棋子时，游戏结束，另一方获胜；
- 有一方无棋可走时，游戏结束，另一方获胜；
- 每次走棋可以让一颗棋子往上下左右方向移动 $1$ 格，但目标格上不能有棋子；
- 同时满足以下条件时可以吃掉对方棋子：在一行（或一列上），有且仅有 $N-1$ 颗棋子（当 $N>4$ 时为 $N-2$ 颗也可），其中有 $N-2$ 颗己方棋子（当 $N>4$ 时为 $N-3$ 颗也可），另外 $1$ （当 $N>4$ 时为 $2$ 颗也可）颗棋子为敌方的，我方的棋子全部相邻，敌方棋子全部相邻，并且我方有一颗棋子与敌方相邻，**而且此局面为我方主动走成**，则我方可以把这一列上敌方的棋子全部吃掉。

现在，请你模拟走棋的过程。

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

以上为一个不可以吃子的局面。（红吃蓝）

但假如蓝棋本来就在 $(3,3)$，红棋从 $(2,2)$ 走到 $(2,3)$，就可以吃子。

**若不能理解，强烈建议手推一遍样例。**

inputFormat:
输入文件的第一行有两个整数 $N$ 和 $K$，表示棋盘的大小和走棋的总步数。

接下来 $K$ 行，每行四个整数 $a,b,c,d$，表示某一方的原本在 $(a,b)$ 的棋子走到了 $(c,d)$。从第二行开始算起，第偶数行表示蓝方，第奇数行表示红方。

outputFormat:
分三种情况输出答案：
- 数据不合法：输出 $0$。
- 这一局还没有结束：第一行输出 $1$，接下来 $N$ 行，每行 $N$ 个字符，表示目前的局面状态。用```h```表示红方棋子，```l```表示蓝方棋子，```.```表示此网格为空。若此局面某一方可以吃子，输出吃子后的状态。
- 这一局已经结束：第一行输出 $2$，第二行输出```red```或```blue```，表示哪一方获胜。第三行至第 $N+2$ 行，输出获胜时的局面。用```h```表示红方棋子，```l```表示蓝方棋子，```.```表示此网格为空。若此局面某一方可以吃子，输出吃子后的状态。**你的程序应该忽略使你判断出胜负那一行之后的所有输入。**

hint:
样例 4 说明：第 21 歩时，红方已胜，因此第 22 歩的非法移动应该忽略。

对于 $30\%$ 的数据，不存在吃子的情况；

对于 $60\%$ 的数据，$N=4$；

对于 $80\%$ 的数据，$4\le N\le 6$；

对于 $100\%$ 的数据，$4\le N\le 10$，$1 \le K \le 10^3$。


title: 专心OI - 跳房子

background:
Imakf 有一天参加了 PINO2017 PJ 组，他突然看见最后一道题：

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

他十分蒟蒻，写不出来。

而如今他还是一个蒟蒻，他又看见一道题：

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

他还是写不出来，于是便来请教您。

description:
您有 $N$ 个格子，排成一行，从左往右编号为 $1,2,\cdots,N$。您站在 $1$ 号格子的左边无限远，开始从左往右跳，跳到 $N$ 号格子右侧为止。由于您是一位成功的 OIer，您自然长得很胖，所以您的腿部力量也非常大！这使得您跳一次，当前格子到目标格子中间必须至少空出来 $M$ 格，但您可以跳无数格远！

您认为这么跳太没意思了，于是便想计算出有多少种方案可以跳完全程。由于方案可能过多，您会输出方案数量模 $(10^9+7)$ 的值

方案不同当且仅当经过的任一一个格子编号不同。

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

outputFormat: 一个整数，表示跳完全程的方案模 $(10^9+7)$。


title: [USACO04MAR] Financial Aid

description:
   人类可以选择很多大学，而奶牛们却没学可上。为解决这个问题，贝西和她的伙伴们创立了一所奶牛大学，取名为哞哞大学。

   为了选拔优秀学生，她们发明了一种奶牛学术能力测试（简称 CSAT） ，这种测试的分数异常精确，每头奶牛的成绩可以用$0$到$2×10^9$之间的一个整数表示，而且可以保证每头奶牛的分数都不同。

   哞哞大学的学费很贵，奶牛们表示负担不起，他们都各自申请了奖学金。政府并没有为奶牛准备奖学金，所有的预算都必须要从学校有限的助学基金中扣除（设基金总额为F)。

   哞哞大学有N间宿舍，N是一个奇数，所以贝西只能接受N头奶牛的申请，她发誓不会让入学的奶牛少于N。此外，她希望新生的 CSAT 成绩表现优异，她以中位数来衡量新生的总体水平。所谓中位数，就是排序后处在最中间的分数，比如3,8,9,7,5的中位数是7。

   今年，共有C头奶牛申请入学，给定每头奶牛的 CSAT 成绩和申请的奖学金数目，以及学校可赞助的总额，确定贝西接受哪些奶牛的申请才可以使成绩的中位数达到最大。

inputFormat:
第一行：三个用空格分开的整数：$N$，$C$和$F$。$1 ≤ N ≤ 19999$，$N ≤ C ≤ 10^5$ ，$0 ≤ F ≤ 2 × 10^9$
第二行到$C + 1$行：每行有两个用空格分开的整数。第一个数是这头奶牛的 CSAT 成绩，第二个数是这头奶牛需要的奖学金$Q_i$ ，$0 ≤ Q_i ≤ 10^5 $。

outputFormat: 第一行：一个整数，表示贝西可以得到的最大中位数，如果现有基金不够资助任何N头奶牛，则输出-1。

hint: 贝西接受 CSAT 分数为 5，35，50 的奶牛的申请，中位数为 35，需支付的奖学金总额为18 + 30 + 21 = 69


title: [USACO02FEB] Cow Cycling

description:
奶牛自行车队由 $N$ 名队员组成，他们正准备参加一个比赛，这场比赛的路程共有 $D$ 圈。车队在比赛时会排成一条直线，由于存在空气阻力，当骑车速度达到每分钟 $x$ 圈时，领头的奶牛每分钟消耗的体力为 $x^2$，其它奶牛每分钟消耗的体力为 $x$。每头奶牛的初始体力值都是相同的，记作 $E$。如果有些奶牛在比赛过程中的体力不支，就会掉队，掉队的奶牛不能继续参加比赛。每支队伍最后只要有一头奶牛能到终点就可以了。

比赛规定，最小的计时单位是分钟，在每分钟开始的时候，车队要哪头奶牛负责领头，领头奶牛不能在这分数中内掉队，每分钟骑过的圈数也必须是整数。

请帮忙计划一下，采用什么样的策略才能让车队以最快的时间到达终点？

inputFormat: 第一行：三个正整数：$N, E, D$。$1 \leq N \leq 20$，$1 \leq E \leq 100$，$1 \leq D \leq 100$。

outputFormat: 第一行：单独一个整数，表示最早达到终点的时间，如果无法到达终点，输出 $0$。


title: 水の斗牛

background: 蒟蒻${\rm CYJian}$拉着${\rm JerryC}$和${\rm Justin}$等一众机房巨佬来打斗牛辣！！

description:
现在一共有$N$个人玩起了斗牛。一共玩了T局，每局有三个人参与游戏，每个人的初始分都是0。

本题为了方便，对于斗牛的基本规则做了些许变动，具体规则如下：

## 1.基本规则

每一轮斗牛开始时，每一位玩家都会拿到5张牌。

每张牌一定是一个2到10之间的整数或A(表示1)。

每张牌有一个花色，a代表黑桃，b代表红桃，c代表梅花，d代表方块。

## 2.牌型

五张牌中，除炸弹和无牛牌型以外，都分为两个部分：牛和分。其中牛包括三张点数相同(铁板)或三张点数和为10的倍数的牌，分包括剩下的两张牌，一套牌的分即为这两张牌模10的余数。

1)炸弹：四张点数相同的牌。

2)牛牛：分恰好为0。

3)牛：分不为0，分和牛数的数值相同。如分是5，则这套牌被称为牛五。

4)无牛：不存在三张牌，其点数相同或其点数和为10的倍数。

## 3.牌型大小关系

炸弹>牛牛>牛九>牛八>……>牛二>牛一>无牛

双方拥有炸弹时，炸弹点数大的更大；

相同牛数且只有一方有铁板时，有铁板的比没有铁板的大；

相同牛数且双方拥有铁板时，铁板点数大的更大；

相同牛数且双方均没有铁板或双方均无牛时，我们比较双方牌中点数最大的一张牌，点数更大的一方更大；若双方点数最大的一张牌点数相同，则花色更大的一方更大，花色大小为黑桃>红桃>梅花>方块。

## 4.计分

一局牌的底分为10，即每位玩家都会押10分。

对于其中的两位玩家，我们在比较完双方的牌型之后，选择牌型更大的一方的牌型来计算得失分数的翻倍。具体如下：

1)炸弹：底分×10。

2)牛牛：底分×3。

3)牛七/牛八/牛九：底分×2。

4)牛六~牛一：底分。

5)无牛：底分。

6)铁板：在计算完牌型得分之后，在牌型得分的基础上×2。注意铁板翻倍不与炸弹同时进行。

我们在计分时，采用两两之间计分的方式，也就是说对于三名玩家A、B、C，我们先计算A和B之间的分数得失，再计算A和C之间的分数得失，最后计算B和C之间的分数得失。

现在我们假设所有玩家都足够聪明，也就是说，所有玩家都会打出他们手上的牌中最大的牌型。${\rm CYJian}$想知道，在这T轮游戏结束之后，每位玩家的得分情况。

inputFormat:
第一行两个整数id，T，N。其中id表示测试点编号，对于部分分可能有一定帮助。其中样例的测试点编号为0。

接下来N行，每行一个仅包括大小写字母和数字的长度少于11的字符串表示玩家名称。

接下来T组，每组数据六行，可分为三个相同的部分：

第一行一个字符串表示玩家名称。

第二行五个字符串表示该玩家手中的手牌。每一个字符串的第一个字符表示花色，其余字符表示牌的大小。

outputFormat:
共N行，每行一个字符串和一个数字，中间用空格隔开。表示一名玩家和他的最终得分。

请按照玩家名称的输入顺序输出。

samples:
0 2 3
CYJian
JerryC
Justin
CYJian
a10 b10 c10 d10 a9
JerryC
cA b2 c3 d4 d5
Justin
aA bA dA a4 c6
CYJian
aA b2 c3 d4 a5
JerryC
bA c2 d3 a4 b5
Justin
cA d2 a3 c4 c5

samples:
0 3 4
CYJian
JerryC
Samcompu
Hsl2363
CYJian
a2 b5 c8 d4 aA
Samcompu
a2 bA c3 a4 c5
JerryC
aA b2 c7 c4 c6
Hsl2363
aA bA cA dA a10
Samcompu
a2 b2 c2 d2 b10
JerryC
a3 b3 c3 d3 c10
Hsl2363
a5 c6 d8 a9 b9
JerryC
b6 b2 c9 a7 d2
CYJian
b5 d5 c5 a6 d9

samples:
CYJian 120
JerryC 150
Samcompu -60
Hsl2363 -210


title: 成绩

background:
小奔的score

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

说一句：本题已放开空间范围（不过真的貌似不用开数组就可以A呀

description:
小奔的期末考试结束了。

他的成绩不久之后就会发下来。

给出一个考试成绩表格，例如：

| 科目/分值种类 | 语文 | 数学|英语  |
| :----------: | :----------: | :----------: | :----------: |
|  满分| $100$ |$120$  |$150$  |
| 实际得分 |  $99$|$73$  |$100$  |

当然。学校的老师认为如果录入如此多的成绩不好算分，于是他想要你的综合成绩评定

综合成绩评定指：(每一科的满分之和\*3-每一科的实际得分之和\*2)÷每科所扣除分数的和。

小奔想请你给出他的综合成绩，你能做到吗？

inputFormat:
第一行给出一个整数$n$，表示科目的总数。
第二行$n$个整数$a_i$,表示第$i$门课程的满分。
第三行$n$个整数$b_i$,表示第$i$门课程小奔的实际得分。

outputFormat: 一行一个数，表示他的综合成绩。结果保留$6$位小数

hint:
对于$20$%的数据，数据为样例

对于$100$%的数据，$n<=1e7$


title: 函数

description:
小奔有一个二元函数 $f(a,b)$。

如果 $a<2$ 或 $b<2$ 返回 $a+b$。

其他情况则返回以下四个式子的最大值（除号均为整除）：

$$a+b$$

$$g(a/2)+g(a/3)+g(a/8)+g(a/9)+b$$

$$g(b/2)+g(b/3)+g(b/8)+g(b/9)+a$$

$$g(b/2)+g(b/3)+g(b/8)+g(b/9)+g(a/2)+g(a/3)+g(a/8)+g(a/9)$$

其中，$g(n)$ 返回 $\max(g(n/2)+g(n/3)+g(n/8)+g(n/9),n)$，当 $n=0$ 时返回 $0$。

当然，白痴都想得到可以记忆化求出较小的 $f(a,b)$，所以小奔才不会考你那么简单的题呢。

他想问你当 $a,b$ 都小于 $10^{16}$ 时，$f(a,b)$ 的值。

inputFormat:
包含多组数据。

每组数据，包含一行，两个正整数 $a,b$。

outputFormat: 每组数据输出一行，即 $f(a,b)$ 的值。


title: 轮换式

description:
小奔发现，对于任意的 $n$ 个字母，他们构成的轮换式，都表示成 $n$ 个基本
$1\sim n$ 次基本轮换式的线性和。

一元的基本轮换式：$a$；

二元：$a+b,ab$；

三元：$a+b+c,ab+ac+bc,abc$；

四元：$a+b+c+d,ab+ac+bc+ad+bd+cd,abc+abd+acd+bcd,abcd$；

………………

同样的，对于任意的 $n$ 个字母，给出他们的几个基本轮换式，都可以求出这几个字母的值。

但是小奔突然大发慈悲，他只需要你求出这些字母的 $m$ 次方和模 $10^7+29$ 的值。

inputFormat:
第一行是字母个数 $n$ ，次数 $m$ 。

接下来一行 $n$ 个正整数，第 $i$ 个为 $a_i$ $(0<a_i\le 10000)$，从左到右分别是 $1\sim n$ 次 $n$ 元基本轮换式的值。

outputFormat: 一个数，要求的答案。

hint:
本题共有 $3$ 个子任务。

Subtask 1（12 pts）：$n\le 2$；

Subtask 2（28 pts）：$n=3$；

Subtask 3（60 pts）：$n=4$。

对于所有数据，$0\le m\le 100000$。


title: 信号站

background: 扶贫行动来到了Q村，扶贫队准备在Q村修筑信号站，让Q村不再“远离尘世”,让人们获得丰富的外界信息。

description:
   Q村非常非常Qiong，整个村只有一条路。在这条路上，有N户人家，因为条件有限，所以一个点上可能有多户人家。因为山区运输条件落后，所以扶贫队只能修筑k个信号站，并且他们希望各电站的不合理值之和最小。信号站的不合理值是指该信号站到每户人家的距离之和。

   扶贫队善于修筑电站，但是他们不擅长选址~~（因为数学不好QwQ）~~，他们希望你>>编程高手，来帮助他们选择修筑信号站的最佳地点，使得k个信号站的不合理值最小。

   距离求解方法:若某信号站的坐标为x,某户人家的坐标为y,那么该信号站与该人家的距离为|x-y|（即取绝对值）。

   数据保证人家数大于信号站数。放置信号站的位置坐标必须为整数。一个位置上只能放一个信号站。

inputFormat:
#### 共2行，

第一行，读入$ n $，$ k $，分别代表人家数和信号站数；

第二行，读入各户人家的坐标$ ai $（保证为整数），用空格隔开。

outputFormat: 仅一行，输出**最小**的不合理值之和。

hint:
#### 样例解释

在2和3的位置上放置信号站（方案不唯一）。

#### 数据范围

对于 $ 70\% $ 的数据，$ n,k\leq 10^3 $；
对于 $ 100\% $ 的数据，$  n \leq 1000000, 0 \leq a_i \leq 10 ^ 6 $。


title: 烦人的数学作业

background: NOIP2018初赛结束了，但H还是要上学的啊啊。。上学肯定要完成老师布置的作业，H十分头疼。在如山的作业中，Mr.G布置的数学作业最烦人，H总是完不成~~

description:
Mr.G最近在看一些关于数字题的书，他每天愁同学们太~~聪明~~了，所有的作业同学们都能~~做到全对~~（拿到答案）。Mr.G~~蒙在鼓里~~（心知肚明）。为了使同学们进步，Mr.G总是创造一些~~简单~~（毒瘤）题来作为作业。以下是数学作业的最后一题题干——

给出一个区间$ L $~$ R $，求$ L $到$ R $区间内**每个数的数字和**，如123这个数的数字和为1+2+3=6。

（$ 1 \leq L \leq R \leq 10^2 $）

同学们纷纷做出来了，Mr.G一看这最后一题跟摆设没区别了呀，于是他迅速修改了题目，把范围定得非常非常大，且有$ T $组数据，将最终的答案mod $ 10^9+7 $。

（$ 1 \leq L \leq R \leq 10^{18} $）
（$ 1 \leq T \leq 20  $）

同学们纷纷被难住了。但H为了备战NOIP2018，没有时间完成Mr.G的数学作业~~（其实是不想做QwQ）~~，所以Ta找到了你，希望你帮助Ta和同学完成这烦人的数学作业！

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

第$ 1 $行读入$ T $。代表有$ T $组数据；

第$ 2 $~$ T+1 $行。读$ L_i $和$ R_i $

outputFormat:
输出共$ T $行，

每行输出$ L_i $和$ R_i $的区间数字和mod $ 10^9+7 $。

hint:
对于 $ 50\% $ 的数据，$ 1 \leq L \leq R \leq 10^8 $；

对于 $ 100\% $ 的数据，$ 1 \leq L \leq R \leq 10^{18}  $，$ 1 \leq T \leq 20  $。


title: Hillwer编码

background: 在Z国的高科技研究中心，科研人员使用的都是最“先进”的Hillwer编码（毕竟这里可是国家机密库，储存着最重要的机密资料~~QwQ）。

description:
Z国的科技十分发达，一直是各国觊觎的目标，Y国就是其中之一。经过Y国黑客夜以继日的奋斗，终于获得了Z国**Hillwer**编码的转换方式，并且截获了n条原码。 BUT（总是有那么多但是~），Y国的黑客们呕心沥血研究**Hillwer**，都累得趴下了……所以，转换**Hillwer**编码的任务他们就无法完成。

Y国元首听说在遥远的东方国度，有一群才华横溢的少年——就是坐在电脑前的你们！元首希望你能够帮助Y国转换编码，他将赠予你**NOIP_AK荣耀桂冠**！

**Hillwer**编码的转换规则如下： 对于每一条原码$ S $，保证仅由26个大写字母组成。将每个字母后移R位，得到中转码$ S1 $（当$ S $=‘XYZ’,R=2时，$ S1 $=‘ZAB’。即变成当前字母后$ R $个字母，超过 ‘Z’则从‘A’开始）。接着，将中转码进行“符转数”操作，将$ S1 $每一位的ACS码（即ASCLL码）相乘，得到数串$ Q $。转换后的编码即为$ Q $。

元首为了检查你是不是偷懒，还要求你把中转码$ S1 $也输出。

inputFormat:
第1行，读入$ n $，$ R $。
第2~$ n $+1行，每行一条编码S。

outputFormat:
共$ n $*2行，
奇数行，每行一条中转码$ S1 $；
偶数行，每行一条转换后的编码$ Q $。

hint:
对于 $ 30\% $ 的数据，$ 1 \leq n \leq 10 ,1 \leq R \leq 10 $；

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

对于 $ 100\% $ 的数据，$ 1 \leq n \leq 500 ,1 \leq R \leq 10^5 $。

另外保证 原码长度小于600