title: [CTSC2009] 魔幻花园

description:
魔法师栋栋有一个美丽的魔幻花园，在花园里，栋栋种满各式各样的魔幻植物，花园里一年四季都开满着姹紫嫣红的鲜花。栋栋的朋友们都特别喜欢来花园里玩。

花园的浇灌系统是由栋栋特别设计的，栋栋用魔法在花园上空变出了$n$个喷头，这些喷头都连接着附近的圣水河。浇灌的时候，所有的喷头一起喷出一道道水流，水流在空中划出一道道美丽的弧线，最终正好浇灌到n棵最缺水的魔幻植物上。

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

栋栋把每个喷头都设在同一水平高度$h$。所有的喷头都是水平放置的，当水流从喷头喷出时，只有水平的速度(每个喷头的水平速度不一定相同)。魔幻花园里没有风，空气阻力可以忽略。所以在重力的影响下(魔幻花园的重力加速度为$g$)，水流的轨迹是一条完美的抛物线。空间上的任意点都最多被三个喷头喷到，两条水流相交不会影响各自的轨迹。

近些年来魔幻花园附近新建了许多工厂，圣水河受到了污染，栋栋不想受污染的水影响到他的花园，所以他要使用魔法先净化一下浇灌的水。栋栋的魔法只能净化从喷头喷出来的水，他可以施魔法在空中的一个水平面形成一个凸多边形的滤水层，所有通过滤水层的水都会被净化，施这个魔法需要的能量和滤水层的面积成正比，每平方米滤水层需要$1$单位的魔法能量。栋栋想净化所有的水，他最少需要多少能量呢？

为了更好的描述问题，栋栋在花园建立起了一个三维的直角坐标系，以花园的西北角为坐标轴的原点，从原点向东是$x$轴的正方向，向南是$y$轴的正方向，向上是$z$轴的正方向。这样第$i$个喷头的位置可以用$(x_i,y_i,h)$来表示，而第$j$棵魔幻植物的位置可以用$(x_j',y_j',0)$来表示。

inputFormat:
输入文件*garden.in*第一行为两个实数$h, g$，表示喷头的高度和魔幻花园的重力加速度。第二行为整数$n$，表示有多少个喷头。

接下来$n$行，每行四个整数$x_i, y_i, x_i', y_i'$，整数间使用一个空格分隔。表示第i个喷头的坐标是$(x_i, y_i, h)$，它喷出的水正好浇灌到了$(x_i', y_i', 0)$位置的魔幻植物上。

outputFormat: 输出文件*garden.out*仅有一个实数，表示栋栋最少需要的能量，至少精确到小数点后3位。

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

在高度为$35$的地方施魔法，此时所有的水流正好汇合到$(100, 100, 35)$这点，所以需要的能量为$0$。

**【样例说明2】**

在高度为$10$的地方（即喷头处）施魔法，魔法形成一个直角三角形，三个点的坐标分别为：$(0,0,10), (1,0,10), (0,50,10)$，面积为$25.000$，所以需要的魔法能量也为$25.000$。

**【评分标准】**

对于每个测试点，如果你的答案与标准答案的差不超过$0.001$，则得到该测试点的全部分数；如果你的答案与标准答案的差超过$0.001$但不超过$0.002$，则得到50%的分数；否则得0分。

**【数据规模】**

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

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

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

$0 < h \leq 10000.0$

$0 < g \leq 100.0$

$0 \leq x_i, y_i, x_i', y_i' \leq 1000$

**【提示】**

水从喷头喷出到地面的过程可以看成一个平抛运动。平抛运动可以分解为向
水平方向和竖直方向的两个分运动：

令$L = (x_i - x_i')^2 + (y_i - y_i')^2$，则

初始速度$v_0 = \sqrt{\frac{Lg}{2h}}$

$t$时刻的水平分速度：$v_{\text{平}}(t) = v_0$

$t$时刻的竖直分速度：$v_{\text{竖}}(t) = gt$

$t$时刻的速度：$v(t) = \sqrt{v_{\text{平}}^2(t) + v_{\text{竖}}^2(t)}$


title: [CTSC2011] 无穷图的桥

type: P

description:
本题的目标是求一个点数无穷的无向图的桥。

这个无向图具有如下性质：

1. 这个图是一个连通图。

2. 这个图的所有节点分为若干层，分别是第$1$层、第$2$层、第$3$层$\cdots$共有无穷层，每层共有$n$个节点。为了描述方便，以下用$(i, x)$表示第$i$层的$x$号节点。

3. 同一层内的节点可以相互连边，相邻两层的节点之间可以相互连边，除此之外，其他节点之间不能相互连边。

4. 如果$(i, x)$与$(i, y)$之间有一条权值为$d$的边，那么$(j, x)$与$(j, y)$之间也有一条边，它的权值为$0.9^{j-i}d$，其中j为任意正整数。

5. 如果$(i, x)$与$(i +  1, y)$之间有一条权值为$d$的边，那么$(j, x)$与$(j+1, y)$之间也有一条边，它的权值为$0.9^{j-i}d$，其中$j$为任意正整数。如下所示的无向图就符合上面的所有性质。

一个点数无穷的无向图是连通的，当且仅当对于图中的任意两个节点都存在一条路径将它们连接起来。而一条边是桥，当且仅当这条边被删去后整个图不连通。

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

请你编写程序读入这个点数无穷的连通图，求出其中所有桥的权值之和。例如，在上图中，粗线所示的边就是该图唯一的桥，因此上图中桥的权值之和为$1$。

inputFormat:
输入文件infinite.in第一行包括三个由空格隔开的非负数$n$、$m_1$、$m_2$。从第$2$行到第$m_1+ 1$行，每行有三个正整数$x$、$y$、$d$，表示$(1, x)$与$(1, y)$之间有一条权值为d的边。

从第$m_1+ 2$行到第$m_1+ m_2+ 1$行，每行有三个正整数$x$、$y$、$d$，表示$(1, x)$与$(2, y)$之间有一条权值为$d$的边。每行的三个整数之间都用一个空格隔开。

图中两个点$x$和$y$之间可能有多于$1$条边连接，一条边连接的两个节点可能相同。

outputFormat: 输出文件infinite.out只有一行，包含一个实数，即所有桥的权值之和，四舍五入保留两位小数。


title: [HAOI2018] 染色

background: HAOI2018 Round2 第二题

description:
为了报答小 C 的苹果，小 G 打算送给热爱美术的小 C 一块画布，这块画布可以抽象为一个长度为 $N$ 的序列，每个位置都可以被染成 $M$ 种颜色中的某一种。

然而小 C 只关心序列的 $N$ 个位置中出现次数恰好为 $S$ 的颜色种数，如果恰好出现了 $S$ 次的颜色有 $K$ 种，则小 C 会产生 $W_k$ 的愉悦度。

小 C 希望知道对于所有可能的染色方案，他能获得的愉悦度的和对 $1004535809$
取模的结果是多少。

inputFormat:
从标准输入读入数据。第一行三个整数 $N, M, S$。

接下来一行 $M + 1$ 个整数，第 $i$ 个数表示 $W_{i-1}$。

outputFormat: 输出到标准输出中。输出一个整数表示答案。

samples:
见 sample.zip/data2.in
见 sample.zip/data2.ans

hint:
特殊性质: $\forall 1 \le i \le m, W_i = 0$。

对于 $100\%$ 的数据，满足 $1 \le N \le 10 ^ 7$，$1 \le M \le 10 ^ 5$，$1 \le S \le 150$，$0 \le W_i < 1004535809$。

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


title: [HAOI2018] 苹果树

background: HAOI2018 Round2 第一题

description:
小 C 在自己家的花园里种了一棵苹果树, 树上每个结点都有恰好两个分支. 经过细心的观察, 小 C 发现每一天这棵树都会生长出一个新的结点.

第一天的时候, 果树会长出一个根结点, 以后每一天, 果树会随机选择一个当前树中没有长出过结点 的分支, 然后在这个分支上长出一个新结点, 新结点与分支所属的结点之间连接上一条边.

小 C 定义一棵果树的不便度为树上两两结点之间的距离之和, 两个结点之间 的距离定义为从一个点走到另一个点的路径经过的边数.

现在他非常好奇, 如果 $N$ 天之后小 G 来他家摘苹果, 这个不便度的期望 $E$ 是多少. 但是小 C 讨厌分数, 所以他只想知道 $E \times N !$ 对 $P$ 取模的结果, 可以证明这是一个整数.

inputFormat: 从标准输入中读入数据. 一行两个整数 $N$, $P$ .

outputFormat: 输出到标准输出中. 输出一个整数表示答案．


title: [HAOI2018] 字串覆盖

description:
小C对字符串颇有研究，他觉得传统的字符串匹配太无聊了，于是他想到了这
样一个问题．

对于两个长度为n的串A, B, 小C每次会给出给出4个参数s, t, l, r. 令A从s到t的
子串(从1开始标号)为T，令B从l到r的子串为P.然后他会进行下面的操作：

如果T的某个子串与P相同，我们就可以删掉T的这个子串，并获得K − i的收
益，其中i是初始时A中(注意不是T中)这个子串的起始位置，K是给定的参数．
删除操作可以进行任意多次，你需要输出获得收益的最大值．

注意每次询问都是独立的，即进行一次询问后，删掉的位置会复原．

inputFormat:
从文件cover.in中读入数据.

第一行两个整数n, K，表示字符串长度和参数．

接下来一行一个字符串A.

接下来一行一个字符串B.

接下来一行一个整数q，表示询问个数．

接下来q行，每行四个整数s, t, l, r，表示一次询问．

outputFormat:
输出到文件cover.out中.
输出q行，每行一个整数，表示一个询问的答案．

hint:
样例1解释 ![](https://cdn.luogu.com.cn/upload/pic/18143.png)
子任务
对于所有数据，有 $ 1 ≤ n, q ≤ 10^5 $ ，A, B仅由小写英文字母组成，$ 1 ≤ s ≤ t ≤n $ , $ 1 ≤ l ≤ r ≤ n $ , $ n < K ≤ 10^9 $ ．
HAOI2018 round1 T3

对于 $ n = 10^5 $ 的测试点，满足51≤r−l≤2*10^3  的询问不超过11000个，且r−l在该区间内均匀随机

数据范围
![](https://cdn.luogu.com.cn/upload/pic/18142.png)


title: [HAOI2018] 奇怪的背包

description:
小 C 非常擅长背包问题，他有一个奇怪的背包，这个背包有一个参数 $P$ ，当他向这个背包内放入若干个物品后，背包的重量是物品总体积对 $P$ 取模后的结果。

现在小 C 有 $n$ 种体积不同的物品，第 $i$ 种占用体积为 $V_i$ ，每种物品都有无限个。他会进行 $q$ 次询问，每次询问给出重量 $w_i$ ，你需要回答有多少种放入物品的方案，能将一个初始为空的背包的重量变为 $w_i$。注意，两种方案被认为是不同的，当且仅当放入物品的种类不同，而与每种物品放入的个数无关．不难发现总的方案数为 $2^n$。

由于答案可能很大，你只需要输出答案对 $10^9 + 7$ 取模的结果。

inputFormat:
第一行三个整数 $n, q, P$，含义见问题描述。

接下来一行 $n$ 个整数表示 $V_i$。

接下来一行 $q$ 个整数表示 $w_i$。

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

hint:
![](https://cdn.luogu.com.cn/upload/pic/18144.png)
HAOI2018 round1 T1


title: [HAOI2018] 反色游戏

description:
小$C$和小$G$经常在一起研究搏弈论问题，有一天他们想到了这样一个游戏．
有一个$n$个点$m$条边的无向图，初始时每个节点有一个颜色，要么是黑色，要
么是白色．现在他们对于每条边做出一次抉择：要么将这条边连接的两个节点都
反色（黑变白，白变黑），要么不作处理．他们想把所有节点都变为白色，他们
想知道在$2^m$种决策中，有多少种方案能达成这个目标．
小$G$认为这个问题太水了，于是他还想知道，对于第$i$个点，在删去这个点及
与它相连的边后，新的答案是多少．
由于答案可能很大，你只需要输出答案对$10^9+7$取模后的结果．

inputFormat:
从文件$game.in$中读入数据.
第一行一个整数$T$，表示数据组数．
每组数据第一行两个整数$n$,$m$表示点数和边数.
接下来$m$行，每行两个整数$u$,$v$,描述无向图的一条边．
接下来一行一个长度为$n$的$0/1$串，如果第$i$个字符为$0$表示第$i$个点为白色，否
则为黑色．

outputFormat:
输出到文件$game.out$中.
每组数据输出一行$n+1$个整数，第一个整数表示不删去任何点时的答案．接
下来$n$个整数，第$i$个表示删去第$i$个点时的答案．

hint:
对于所有数据，有$1\le T\le5$,$1\le n,m\le10^5$,$1\le u,v\le n$，没有重边和自
环．
![](https://cdn.luogu.com.cn/upload/pic/18145.png)
HAOI2018 round1 T2


title: [ZJOI2018] 胖

background: Cedyks 是九条可怜的好朋友（可能这场比赛公开以后就不是了），也是这题的主人公。

description:
Cedyks 是一个富有的男孩子。他住在著名的 The Place（宫殿）中。

Cedyks 是一个努力的男孩子。他每天都做着不一样的题来锻炼他的 The Salt（灵魂）。

这天，他打算在他的宫殿外围修筑一道城墙，城墙上有 $n$ 座瞭望塔。你可以把城墙看做一条线段，瞭望塔是线段上的 $n$ 个点，其中 $1$ 和 $n$ 分别为城墙的两个端点。其中第 $i$ 座瞭望塔和第 $i + 1$ 座瞭望塔的距离为 $w_i$，他们之间的道路是双向的。

城墙很快就修建好了，现在 Cedyks 开始计划修筑他的宫殿到城墙的道路。因为这题的题目名称，Cedyks 打算用他的宫殿到每一个瞭望塔的最短道路之和来衡量一个修建计划。

现在 Cedyks 手上有 $m$ 个设计方案，第 $k$ 个设计方案会在宫殿和瞭望塔之间修建 $T_k$ 条双向道路，第 $i$ 条道路连接着瞭望塔 $a_i$，长度为 $l_i$。

计算到每一个瞭望塔的最短路之和是一个繁重的工程，本来 Cedyks 想用广为流传的 SPFA 算法来求解，但是因为他的 butter（缓冲区）实在是太小了，他只能转而用原始的贝尔福特曼算法来计算，算法的流程大概如下：

1. 定义宫殿是 $0$ 号点，第 $i$ 个瞭望塔是 $i$ 号点，双向边 $(u_i, v_i, l_i)$ 为一条连接 $u_i$ 和 $v_i$ 的双向道路。令 $d$ 为距离数组，最开始 $d_0 = 0, d_i = 10^{18}(i ∈ [1, n])$。
2. 令辅助数组 $c = d$。依次对于每一条边 $(u_i, v_i,w_i)$ 进行增广，$c_{u_i} = \min(c_{u_i} , d_{v_i} + w_i)$，$c_{v_i} = \min(c_{v_i} , d_{u_i} + w_i)$。
3. 令 $t$ 为 $c$ 和 $d$ 中不一样的位置个数，即令 $S = \{i|c_i≠d_i\}$，则 $t = |S|$。若 $t = 0$，说明 $d$ 就是最终的最短路，算法结束。否则令 $d = c$，回到第二步。

因为需要计算的设计方案实在是太多了，所以 Cedyks 雇佣了一些人来帮他进行计算。为了避免这些人用捏造出来的数据偷懒，他定义一个设计方案的校验值为在这个方案上运行贝尔福特曼算法每一次进入第三步 $t$ 的和。他会让好几个雇佣来的人计算同样的设计方案，并比对每一个人给出的校验值。

你是 Cedyks 雇佣来的苦力之一，聪明的你发现在这个情形下计算最短路的长度的和是一件非常简单的事情。但是寄人篱下不得不低头，你不得不再计算出每一个方案的校验值来交差。

inputFormat:
第一行输入两个整数 $n,m$，表示瞭望塔个数和设计方案个数。

接下来一行 $n - 1$ 个数 $w_i$，表示瞭望塔 $i$ 和 $i + 1$ 之间道路的长度。

接下来 $m$ 行，每行描述一个设计方案。第一个整数 $K$ 表示设计方案中的道路数量，接下来 $K$ 个数对 $(a_i, l_i)$ 为一条宫殿到瞭望塔的边。

outputFormat: 对于每一个设计方案，输出一行一个整数表示校验值。


title: 粘骨牌

description:
一个 $n \times m$ 的棋盘，除了某一个位置，其它所有位置都被 $1 \times 2$ 的多米诺骨牌覆盖，所以一共有 $\frac{nm - 1}{2}$ 个多米诺骨牌。

Alice 可以进行任意多次移动，每次移动需要保证移动后多米诺骨牌不超出棋盘，且不能存在两个多米诺骨牌重叠。

棋盘上有若干个特殊位置，一旦它们露出来，你就输了，所以你要避免 Alice 的移动使这些位置露出来。

你可以选择固定任意多个多米诺骨牌，固定一个骨牌需要一定的代价，身为 Bob 的你希望用最少的代价，使得无论 Alice 怎么移动，那些特殊位置都不会露出来，求出这个最小代价。

如果无论怎么固定，都不能满足，输出 "GG"。

inputFormat:
第一行三个整数 $n, m, k(1 \leq n, m \leq 1001, 0 \leq k \leq n \times m)$，分别表示棋盘的大小以及特殊位置的个数。保证 $n$ 和 $m$ 都是奇数。

接下来一行 $\frac{nm - 1}{2}$ 个数，第 $i$ 个数 $a_i(1 \leq a_i \leq 10^9)$表示固定第 $i$ 个骨牌需要的代价。

接下来 $k$ 行，每行两个整数 $x, y(1 \leq x \leq n, 1 \leq y \leq m)$，表示$ (x, y)$ 是一个特殊位置。不保证这 $k$ 个特殊位置互不相同，如果有相同的，忽略后一个即可。

接下来 $n$ 行，每行 $m$ 个数 $v_{i, j}(0 \leq v_{i, j} \leq \frac{nm - 1}{2})$，表示棋盘的覆盖情况。如果 $v_{i,j} = 0$，表示该位置未被覆盖，否则表示这个位置被编号为 $v_{i, j}$ 的骨牌覆盖。

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


title: [ZJOI2018] 树

description:
九条可怜是一个热爱出题的女孩子。

虽然出题本身是一件非常有趣的事情，但是要把题目给出成正式比赛,就不是那么有趣了：造数据总是一件让人心力憔悴的事情。

在 ZJOI2018 Day 1 中，可怜出了一道和树相关的非常有趣的题，她打算采用一种常用的方式随机生成一棵 $n$ 个节点的有根树：

- 节点 1 作为树的根。
- 对于 $i \in [2, n]$ ，独立地从 $[1, i)$ 中等概率随机选取一个节点作为 $i$ 的父亲。

可怜不是很想考虑这样随机出来的数据能不能卡掉暴力,毕竟乱搞也是 OI 比赛的一部分。

可怜比较在意的是题目的区分度，以及是不是所有可能的分数都出现了。因此，可怜希望任何两个测试点的树是有区别的：这样就可能会有错误的程序能只通过其中一个点。

因此，可怜想要计算，通过上面的方法独立的随机生成 $k$ 棵 $n$ 个节点的有根树 $T_1$ 至 $T_k$ ，他们两两同构的概率是多少。

两棵 $n$ 个节点的有根树 $T_1$ 和 $T_2$ 同构当且仅当存在长度为 $n$ 的排列 $p$，满足 $p_1 = 1$ ，且对于 $\forall i \in [2, n]$ ，若 $i$ 在 $T_1$ 的父亲是 $f$ ，则 $p_i$ 在 $T_2$ 的父亲是 $p_f$ 。

inputFormat: 第一行输入三个整数 $n, k, p$，表示节点个数，树的个数以及模数。输入保证 $10^8 \leq p \leq 10^9$ 且 $p$ 是质数。

outputFormat: 输出一行一个整数，表示答案对 $p$ 取模后的值。即如果答案的最简分数表示为 $\frac{a}{b}$ ，输出 $a \times b ^{-1} \bmod p$。


title: [ZJOI2018] 保镖

description:
九条可怜是一个贪玩的女孩子。

一个可爱的女孩子出门在外和朋友玩，难免会遇到危险，于是可怜的爸爸悄悄的安插了 $n$ 位保镖在暗中保护她。因为可怜是一个要强的女孩子，所以她的爸爸不想让她知道她的身边有这么多的保镖，因此保镖们必须通过定期的换岗来避免被可怜发现。

一次理想的换岗是：距离可怜远的保镖被换到了较近的位置，距离可怜近的保镖被换到了较远的位置。经过一系列安排，保镖们会按照如下的方式进行换岗：

换岗时，可怜和保镖们的位置可以被抽象成二维平面直角坐标系上的点。设可怜的位置为 $O$，保镖的位置为 $P_i$，换岗后的位置为 $P'_i$
在换岗前后，保镖和可怜的相对位置不变。即对于 $\forall i \in [1,n]$，$P'_i$ 在射线 $OP_i$ 上。
在换岗前后，保镖和可怜的距离变成了原来的倒数。即对于 $\forall i \in [1,n]$，$|OP_i||OP'_i|=1$。
同时，保镖的位置决定了可怜的安全度。如果在外围的保镖越多，那么他们能观察到的信息就越多，可怜就越安全。因此，我们定义这些保镖的位置的凸包的**顶点个数**为可怜的安全度。

然而，可怜的行踪总是神出鬼没的。这一天，保镖们跟丢了可怜，只知道可怜下次会在以 $(x_1,y_1)$ 为左下角，以 $(x_2,y_2)$ 为右上角的矩形区域内出现，具体的位置服从这个矩形区域内的均匀分布（可以理解为等概率随机）。因为保镖们已经有很长时间没有换岗了，于是他们打算在可怜下次出现的时候换岗。同时，在极小的概率下，可怜可能会出现在和某个保镖相同的位置上。这时这个保镖会被发现，从而他会保持位置不动，而其他的保镖还是会按照上述规则进行换岗。

现在，可怜的爸爸想要计算，保镖们在换岗后，可怜的安全度的期望是多少。

如果你对凸包不太熟悉，这儿给出凸包形式化的定义：

对于一个简单多边形，它是凸多边形当且仅当它内部任意两点的连线在它的内部。
对于一个点集 $P$，它的凸包为包含所有点面积最小的没有三个连续顶点共线的凸多边形。

inputFormat:
第一行输入一个整数 $n$， 表示保镖的数量。

第二行输入四个整数 $x_1,y_1,x_2,y_2$， 表示可怜可能出现的矩形区域。

接下来 $n$ 行每行两个整数 $a,b$，表示一个保镖的坐标。保证保镖的坐标两两不同。

outputFormat:
输出一行一个实数表示凸包节点数的期望。

当你的答案与标准输出的绝对误差或相对误差在 $10^{-7}$ 内时，就会被视为正确。

样例

hint:
### 样例解释
这儿画出可怜出现在 (1,0) 时的情况，如下图所示，1,2,4 号保镖的位置保持不变，分别为 $P_1,P_2,P_4$，3 号保镖从 $P_3$ 变到了 $P'_3$，坐标为 $(\frac{1}{2},\frac{1}{2})$。

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

这时四个保镖的位置 $P_1,P_2,P'_3,P_4$ 的凸包为三角形 $P_1,P_4,P_2$，因此可怜的安全度为 3。注意这时 $P'_3$ 正好落在边 $P_1P_4$ 上，但是根据凸包的定义，它不是顶点。

### 数据范围

测试点|　$n$|测试点|　$n$
-|-|-|-
1|$\le 3$|6|$\le 50$
2|$\le 4$|7|$\le 350$
3|$\le 4$|8|$\le 350$
4|$\le 50$|9|$\le 2000$
5|$\le 50$|10|$\le 2000$

对于 100% 的数据，保证 $0 \leq a,b,x_0,x_1,y_0,y_1 \leq 10^5,x_0<x_1,y_0<y_1,n \geq 3$。

对于 100% 的数据，保证保镖的位置两两不同。

同时为了避免可能出现的精度误差，在所有实际的测试数据以及大样例中，保证可怜可能出现的矩形区域的长宽都不小于 $10^3$，即 $x_1-x_0,y_1-y_0 \geq 10^3$.


title: [CTSC2018] 字典树

description:
Access Globe 有若干个**递增**的正整数序列。他把这些正整数序列中的每个正整数的十进制表示（无前导零）依次写了下来，相邻两个整数之间用逗号 , 隔开。Access Globe 把这个序列视为一个由 $0\sim 9$ 的数字和逗号 , 组成的字符串，然后用一棵 Trie 树存储这些字符串。你并不需要知道 Trie 树究竟是什么，你只需要知道，Access Globe 得到的 Trie 是一棵以 $0$ 号节点为根的有根树，每条边上都有一个字符，并且从根到每个叶节点的路径上的边上的字符顺次拼接构成的字符串是一个他写下的一个递增的正整数序列。

可爱的小 Tommy 决定篡改这棵 Trie 树。他先将 Trie 上的一些边上的字符删去，然后填上另一些字符。为了不被发现，Tommy 必须保证修改后的 Trie 仍然满足上述性 质，即从根到每个叶节点的路径上的边上的字符顺次拼接构成的字符串是一个递增的正整数序列，且每个正整数无前导零。

现在 Tommy 已经删去了一些边上的字符，请你帮他完成“填上字符”的操作。如果有多解，请输出字典序最小的解。

inputFormat:
输入文件包含多组数据，整个文件的第一行是一个整数 $T$，表示数据组数。对于每一组数据：

第一行包含一个长度为 $n$ 的、仅包含 $0$ 到 $9$、, 和 `?` 的字符串，第 $i$ 个整数表示连接节点 $i$ 的父亲和节点 $i$ 的边上的字符，`?` 表示这条边上的字符已经被删去； 第二行包含 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的父亲节点 $f_i$，保证 $0 \le f_i < i$。

outputFormat:
输出 $T$ 行。对于每组数据，输出一个长度为 $n$ 的字符串，表示字典序最小的填写问号的方式中每个点的字符，第 $i$ 个整数表示节点 $i$ 的字符。

如果不存在任何合法的填写方式，请输出 `failed`。

hint:
### 样例解释

Tommy 填写的 Trie 如下图，红色的节点为所有叶子节点，注意，根节点在左下方。

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

### 数据范围

对于 $20\%$ 的数据，$T \le 10$，对于每组数据 $n \le 80$ ，`?` 个数不超过 $8$；
对于另外 $10\%$ 的数据，$T \le 20$，对于每组数据 $n \le 80$，$f_i=i-1$；
对于另外 $20\%$ 的数据，$f_i=i-1$；
对于另外 $10\%$ 的数据，$n \le 80$；
对于所有数据，$T \le 100$，对于每组数据 $n \le 200$。


title: [CTSC2018] 混合果汁

description:
小 R 热衷于做黑暗料理，尤其是混合果汁。

商店里有 $n$ 种果汁，编号为 $0,1,\cdots,n-1$ 。$i$ 号果汁的美味度是 $d_i$，每升价格为 $p_i$。小 R 在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，$i$ 号果汁最多只能添加 $l_i$ 升。

现在有 $m$ 个小朋友过来找小 R 要混合果汁喝，他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中，第 $j$ 个小朋友希望他得到的混合果汁总价格不大于 $g_j$，体积不小于 $L_j$。在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

inputFormat:
输入第一行包含两个正整数 $n, m$，表示果汁的种数和小朋友的数量。

接下来 $n$ 行，每行三个正整数 $d_i, p_i, l_i$，表示 $i$ 号果汁的美味度为 $d_i$，每升价格为 $p_i$，在一瓶果汁中的添加上限为 $l_i$。

接下来 $m$ 行依次描述所有小朋友：每行两个数正整数 $g_j, L_j$ 描述一个小朋友，表示他最多能支付 $g_j$ 元钱，他想要至少 $L_j$ 升果汁。

outputFormat: 对于所有小朋友依次输出：对于每个小朋友，输出一行，包含一个整数，表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求，则输出 $-1$。


title: [JSOI2009] 瓶子和燃料

description:
jyy 一直想着尽快回地球，可惜他飞船的燃料不够了。有一天他又去向火星人要燃料，这次火星人答应了，要 jyy 用飞船上的瓶子来换。jyy 的飞船上共有 $N$ 个瓶子（$1 \leq N \leq 1000$），经过协商，火星人只要其中的 $K$ 个。

jyy 将 $K$ 个瓶子交给火星人之后，火星人用它们装一些燃料给 jyy。所有的瓶子都没有刻度，只在瓶口标注了容量，第 $i$ 个瓶子的容量为 $V _ i$（$V _ i$ 为整数，并且满足 $1 \leq V _ i \leq 10 ^ 9$） 。火星人比较吝啬，他们并不会把所有的瓶子都装满燃料。他们拿到瓶子后，会跑到燃料库里鼓捣一通，弄出一小点燃料来交差。jyy 当然知道他们会来这一手，于是事先了解了火星人鼓捣的具体内容。

火星人在燃料库里只会做如下的 $3$ 种操作：

1. 将某个瓶子装满燃料；
2. 将某个瓶子中的燃料全部倒回燃料库；
3. 将燃料从瓶子 $a$ 倒向瓶子 $b$，直到瓶子 $b$ 满或者瓶子 $a$ 空。燃料倾倒过程中的损耗可以忽略。

火星人拿出的燃料，当然是这些操作能得到的最小正体积。jyy 知道，对于不同的瓶子组合，火星人可能会被迫给出不同体积的燃料。jyy 希望找到最优的瓶子组合，使得火星人给出尽量多的燃料。

inputFormat:
第一行为两个整数 $N,K$。
第 $2 \sim N$ 行，每行一个整数，第 $i+1$ 行的整数为 $V _ i$。

outputFormat: 仅一行一个整数，表示火星人给出燃料的最大值。

hint: 选择第 $2$ 个瓶子和第 $3$ 个瓶子，火星人被迫会给出 $4$ 体积的容量。


title: [BJWC2011] 元素

description:
相传，在远古时期，位于西方大陆的 Magic Land 上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力取决于使用的矿石。

一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法力而使用了很多矿石，却在炼制过程中发现魔法矿石全部消失了，从而无法炼制出法杖，这个现象被称为“魔法抵消” 。特别地，如果在炼制过程中使用超过一块同一种矿石，那么一定会发生“魔法抵消”。后来，随着人们认知水平的提高，这个现象得到了很好的解释。经过了大量的实验后，著名法师 Dmitri 发现：如果给现在发现的每一种矿石进行合理的编号（编号为正整数，称为该矿石的元素序号），那么，一个矿石组合会产生“魔法抵消”当且仅当存在一个非空子集，那些矿石的元素序号按位异或起来为零（如果你不清楚什么是异或，请参见下一页的名词解释 ）。

例如，使用两个同样的矿石必将发生“魔法抵消”，因为这两种矿石的元素序号相同，异或起来为零。并且人们有了测定魔力的有效途径，已经知道了：合成出来的法杖的魔力等于每一种矿石的法力之和。人们已经测定了现今发现的所有矿石的法力值，并且通过实验推算出每一种矿石的元素序号。

现在，给定你以上的矿石信息，请你来计算一下当时可以炼制出的法杖最多有多大的魔力。

inputFormat:
第一行包含一个正整数 $N$，表示矿石的种类数。

接下来 $N$ 行，每行两个正整数$\mathrm{Number}_i$ 和 $\mathrm{Magic}_i$，表示这种矿石的元素序号和魔力值。

outputFormat: 仅包含一行，一个整数代表最大的魔力值。

hint:
### 样例解释

由于有“魔法抵消”这一事实，每一种矿石最多使用一块。

如果使用全部三种矿石，由于三者的元素序号异或起来：$1\ \mathrm{xor}\ 2\ \mathrm{xor}\ 3 = 0$ ，则会发生魔法抵消，得不到法杖。

可以发现，最佳方案是选择后两种矿石，法力为 $20+30=50$。

### 数据范围

对于全部的数据：$1\leq N \leq 1000$，$1\leq \mathrm{Number}_i \le 10^{18}$，$1\leq \mathrm{Magic}_i \le 10^4$。


title: [BJWC2011] 禁忌

description:
Magic Land上的人们总是提起那个传说：他们的祖先John在那个东方岛屿帮助Koishi与其姐姐Satori最终战平。而后，Koishi恢复了读心的能力……

如今，在John已经成为传说的时代，再次造访那座岛屿的人们却发现Koishi遇到了新麻烦。

这次她遇到了Flandre Scarlet——她拥有可以使用禁忌魔法而不会受到伤害的能力。

为了说明什么是禁忌魔法及其伤害，引入以下概念：

1. 字母集$A$上的每个非空字符串对应了一个魔法。其中$A$是包含了前alphabet个小写字母的集合。
2. 有一个集合$T$，包含了$N$个字母集$A$上的字符串。$T$中的每一串称为一个禁忌串（Taboo string）
3. 一个魔法，或等价地，其对应的串$s$因为包含禁忌而对使用者造成的伤害按以下方式确定：把$s$分割成若干段，考虑其中是禁忌串的段的数目，不同的分割可能会有不同的数目，其最大值就是这个伤害。

由于拥有了读心的能力，Koishi总是随机地使用Flandre Scarlet的魔法，可以确定的是，她的魔法正好对应字母集$A$上所有长度为$len$的串。

但是，Flandre Scarlet所使用的一些魔法是带有禁忌的，由于其自身特性，她可以使用禁忌魔法而不受到伤害，而Koishi就不同了。可怜的Koishi每一次使用对方的魔法都面临着受到禁忌伤害的威胁。

你现在需要计算的是如果Koishi使用对方的每一个魔法的概率是均等的，那么每一次随机使用魔法所受到的禁忌伤害的期望值是多少。

inputFormat:
第一行包含三个正整数 $N$、$len$、$alphabet$。
接下来$N$行，每行包含一个串$T_i$，表示禁忌串。

outputFormat: 一个非负实数，表示所受到禁忌伤害的期望值。你的答案需要保证绝对误差不超过 $10^{-6}$。

hint:
【样例1解释】
一共有$2^4 = 16$种不同的魔法。

需要注意的是“aabb”的禁忌伤害是1而不是2。

### 数据范围

有不少于40%的数据中：$N = 1$。
100%的数据中$N ≤ 5$，$len ≤10^9$，$1 ≤ alphabet ≤ 26$。
数据保证每个串$T_i$的长度不超过$15$，并且不是空串。
数据保证每个$T_i$均仅含有前$alphabet$个小写字母。
数据保证集合$T$中没有相同的元素，即对任意不同的$i$和$j$，有$T_i \neq T_j$。


title: [AHOI2006] 文本编辑器

description:
这些日子，可可不和卡卡一起玩了，原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗？为了明确任务目标，可可对“文本编辑器”做了一个抽象的定义：

- `Move k`：将光标移动到第 $k$ 个字符之后，如果 $k=0$，将光标移到文本第一个字符之前。
- `Insert n (换行) S`：在光标后插入长度为 $n$ 的字符串 $S$，光标位置不变，$n \ge 1$。
- `Delete n`：删除光标后的 $n$ 个字符，光标位置不变，$n \ge 1$。
- `Rotate n`：反转光标后的 $n$ 个字符，光标位置不变，$n \ge 1$。
- `Get`：输出光标后的一个字符，光标位置不变。
- `Prev`：光标前移一个字符。
- `Next`：光标后移一个字符。

下面是几个定义：

- 文本：由 $0$ 个或多个字符构成的序列。这些字符的 ASCII 码在闭区间 $[32, 126]$ 内，也就是说，这些字符均为可见字符或空格。
- 光标：在一段文本中用于指示位置的标记，可以位于文本的第一个字符之前，文本的最后一个字符之后或文本的某两个相邻字符之间。
- 文本编辑器：为一个可以对一段文本和该文本中的一个光标进行如下七条操作的程序。如果这段文本为空，我们就说这个文本编辑器是空的。

编写一个程序：
1. 建立一个空的文本编辑器。
2. 从输入文件中读入一些操作指令并执行。
3. 对所有执行过的 `GET` 操作，将指定的内容写入输出文件。

inputFormat: 输入文件中第一行是指令条数 $N$，以下是需要执行的 $N$ 个操作。除了回车符之外，输入文件的所有字符的 ASCII 码都在闭区间 $[32, 126]$ 内。且行尾没有空格。

outputFormat: 依次对应输入文件中每条 `GET` 指令的输出，不得有任何多余的字符。

samples:
10
Insert 13
Balanced eert
Move 2
Delete 5
Next
Insert 7
 editor
Move 0
Get
Move 11
Rotate 4
Get

hint:
对输入数据我们有如下假定：
1. `MOVE` 操作不超过 $5\times 10^4$ 个，`INSERT`, `DELETE` 和 `ROTATE` 操作作的总个数不超过 $6\times 10^3$，`GET` 操作不超过 $2\times 10^4$ 个，`PREV` 和 `NEXT` 操作的总个数不超过 $2\times 10^4$。
2.  所有 `INSERT` 插入的字符数之和不超过 $2M$（$1M=2^{20}$)。
3. `DELETE` 操作、`ROTATE` 操作和 `GET` 操作执行时光标后必然有足够的字符。`MOVE`、`PREV`、`NEXT` 操作不会把光标移动到非法位置。
4. 输入文件没有错误。


title: [JLOI2011] 飞行路线

description:
Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 $n$ 个城市设有业务，设这些城市分别标记为 $0$ 到 $n-1$，一共有 $m$ 种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 $k$ 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？

inputFormat:
第一行三个整数 $n,m,k$，分别表示城市数，航线数和免费乘坐次数。

接下来一行两个整数 $s,t$，分别表示他们出行的起点城市编号和终点城市编号。

接下来 $m$ 行，每行三个整数 $a,b,c$，表示存在一种航线，能从城市 $a$ 到达城市 $b$，或从城市 $b$ 到达城市 $a$，价格为 $c$。

outputFormat: 输出一行一个整数，为最少花费。

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

对于 $30\%$ 的数据，$2 \le n \le 50$，$1 \le m \le 300$，$k=0$。

对于 $50\%$ 的数据，$2 \le n \le 600$，$1 \le m \le 6\times10^3$，$0 \le k \le 1$。

对于 $100\%$ 的数据，$2 \le n \le 10^4$，$1 \le m \le 5\times 10^4$，$0 \le k \le 10$，$0\le s,t,a,b < n$，$a\ne b$，$0\le c\le 10^3$。

另外存在一组 hack 数据。


title: [CTSC2018] 青蕈领主

background: “也许，我的生命也已经如同风中残烛了吧。”小绿如是说。

description:
小绿同学因为微积分这门课，对“连续”这一概念产生了浓厚的兴趣。小绿打算把连续的概念放到由整数构成的序列上，他定义一个长度为 $m$ 的整数序列是连续的，当且仅当这个序列中的最大值与最小值的差，不超过$m-1$。例如 $\{1,3,2\}$ 是连续的，而 $\{1,3\}$ 不是连续的。

某天，小绿的顶头上司板老大，给了小绿 $T$ 个长度为 $n$ 的排列。小绿拿到之后十分欢喜，他求出了每个排列的每个区间是否是他所定义的“连续”的。然而，小绿觉得被别的“连续”区间包含住的“连续”区间不够优秀，于是对于每个排列的所有右端点相同的“连续”区间，他只记录下了长度最长的那个“连续”区间的长度。也就是说，对于板老大给他的每一个排列，他都只记录下了在这个排列中，对于每一个 $1 \le i \le n$，右端点为 $i$ 的最长“连续”区间的长度 $L_i$。显然这个长度最少为 $1$，因为所有长度为 $1$ 的整数序列都是连续的。

做完这一切后，小绿爬上绿色床，美美地做了一个绿色的梦。

可是第二天醒来之后，小绿惊讶的发现板老大给他的所有排列都不见了，只剩下他记录下来的 $T$ 组信息。小绿知道自己在劫难逃，但是作为一个好奇的青年，他还是想知道：对于每一组信息，有多少个和信息符合的长度为 $n$ 的排列。

由于小绿已经放弃治疗了，你只需要告诉他每一个答案对 $998244353$ 取模的结果。

我们并不保证一定存在至少一个符合信息的排列，因为小绿也是人，他也有可能犯错。

inputFormat:
输入的第一行包含两个整数 $T,n$，分别表示板老大给小绿的排列个数、以及每个排列的长度。

接下来 $T$ 行，每行描述一组信息，包含 $n$ 个正整数，第 $i$ 组信息的从左往右第 $j$ 个整数 $L_{i,j}$ 表示第 $i$ 个排列中右端点为第 $j$ 个数的最长“连续”区间的长度。

对于每一行，如果行内包含多个数，则用单个空格将它们隔开。

outputFormat: 对于每组信息，输出一行一个整数表示可能的排列个数对 $998244353$ 取模的结果。由于是计算机帮你算，所以我们不给你犯错的机会。


title: [CTSC2018] 暴力写挂

description:
temporaryDO 是一个很菜的 OIer。在 4 月，他在省队选拔赛的考场上见到了《林克卡特树》一题，其中 $k = 0$ 的部分分是求树 $T$ 上的最长链。可怜的 temporaryDO 并不会做这道题，他在考场上抓猫耳挠猫腮都想不出一点思路。

这时，善良的板板出现在了空中，他的身上发出璀璨却柔和的光芒，荡漾在考场上。“题目并不难。” 板板说。那充满磁性的声音，让 temporaryDO 全身充满了力量。

他决定：写一个枚举点对求 LCA 算距离的 $k = 0$ 的 $O(n^2 \log n)$ 的部分分程序！于是， temporaryDO 选择以 $1$ 为根，建立了求 LCA 的树链剖分结构，然后写了二重 for 循环枚举点对。

然而，菜菜的 temporaryDO 不小心开小了数组，于是数组越界到了一片神秘的内存区域。但恰好的是，那片内存区域存储的区域恰好是另一棵树 $T'$ 。这样一来，程序并没有 RE ，但他求 $x$ 和 $y$ 的距离的时候，计算的是

$$ \mathrm{depth}(x) + \mathrm{depth}(y) -  ({\mathrm{depth}(\mathrm{LCA}(x,y))}+{\mathrm{depth'}(\mathrm{LCA'}(x,y))})$$

最后程序会输出每一对点对 $i, j$（$i \le j$） 的如上定义的“距离” 的最大值。
temporaryDO 的程序在评测时光荣地爆零了。但他并不服气，他决定花好几天把自己的程序跑出来。请你根据 $T$ 和 $T'$ 帮帮可怜的 temporaryDO 求出他程序的输出。

inputFormat:
第一行包含一个整数 $n$ ，表示树上的节点个数。

第 $2$ 到第 $n$ 行，每行三个整数 $x , y , v$ ，表示 $T$ 中存在一条从 $x$ 到 $y$ 的边，其长度为 $v$。

第 $n + 1$ 到第 $2n-1$ 行 ，每行三个整数 $x , y , v$ ，表示 $T'$ 中存在一条从 $x$ 到 $y$ 的边，其长度为 $v$。

outputFormat: 输出一行一个整数，表示 temporaryDO 的程序的输出。


title: [CTSC2018] 假面

background: 针针是绿绿的好朋友。

description:
针针喜欢玩一款叫做 DotA (**D**efense **o**f **t**he **A**lgorithm) 的游戏，在这个游戏中，针针会操纵自己的英雄与队友一起对抗另一支队伍。
针针在 DotA 中最喜欢使用的英雄叫做假面（Faceless），该英雄有 $2$ 个技能：

- 锁定：对一名指定的敌方单位使用，以 $p$ 的概率对该单位造成 $1$ 点伤害（使其减少 $1$ 点生命值）。
- 结界：在一片区域施放结界，让该区域内的所有其他单位无法动弹。
在游戏中，如果一个单位的生命值降至 $0$ 或 $0$ 以下，那么该单位就会死亡。

针针操纵假面的水平一般，因此他决定勤加练习。现在有 $n$ 个敌方单位（编号从 $1$ 至 $n$），编号为 $i$ 的敌方单位有 $h_i$ 点生命值。

针针已经安排好了练习的计划，他会按顺序施放 $Q$ 个技能：

- 对于锁定技能：针针会指定一个敌方单位 $id$ ，并对它施放。由于决定概率系数 $p$ 的因素很多，因此每次的 $p$ 都不一定相同。
特别地，如果该敌方单位已经死亡，那么该技能不会造成任何效果。
- 对于结界技能：针针会希望对 $k$ 个指定的敌方单位施放，但由于针针并不擅长施放该技能，因此他只能命中恰好 $1$ 个敌方单位。命中每个存活的敌方单位的概率是相等的（也就是说已经死亡的敌方单位不会有任何影响）。
特别地，如果这 $k$ 个敌方单位均已死亡，那么该技能同样不会命中任何敌方单位。

现在，围观针针进行练习的绿绿想知道：

1. 对于针针施放的每个结界技能，它命中各敌人的概率分别是多少。
2. 在针针的所有技能施放完毕后，所有敌方单位剩余生命值的期望分别是多少。

由于绿绿还要围观针针训练，所以请你帮他解决这两个问题。

为了防止精度误差，对于所有需要输出的数值，请输出其在模 $998244353$ 意义下的值。

由于结界为假面的终极技能，因此针针施放该技能的次数不会太多。具体请见”子任务“。

inputFormat:
第 $1$ 行为 $1$ 个正整数 $n$ ，表示敌方单位的数量。
第 $2$ 行为 $n$ 个正整数 $m_1,\cdots , m_n$，依次表示各敌方单位的初始生命值。
第 $3$ 行为 $1$ 个非负整数 $Q$ ，表示针针施放技能的数量。
第 $4$ 行至第 $Q + 3$ 行，每行描述一个技能，第 $i + 3$ 行描述第 $i$ 个技能。

每行的开头为一个整数 $op$ ，表示该技能的种类。
如果 $op = 0$ ，则表示锁定技能。并在此后跟随着 $3$ 个正整数 $id , u , v$ ，表示技能施放的目标为 $id$ ，技能命中的概率为 $p = \frac{u}{v}$ 。（保证 $1\le id \le n , 0 < u \le v < 998244353$ ）
如果 $op = 1$ ，则表示结界技能。并在此后跟随着 $1$ 个正整数 $k$ 表示技能施放的目标数量，随后还有额外的 $k$ 个数 $id_1,\cdots,id_k$ 描述技能施放的所有目标。（保证所有 $1 \le id_i \le n$ 互不相同） 对于每一行，如果行内包含多个数，则用单个空格将它们隔开。

outputFormat:
输出包括 $C + 1$ 行（其中 $C$ 为结界技能的数量）：

前 $C$ 行依次对应每个结界技能，对于每行：

输出 $k$ 个数，第 $i$ 个数表示结界命中敌方单位 $id_i$ 的概率。
第 $C + 1$ 行输出 $n$ 个数，第 $i$ 个数表示在所有技能施放完毕后，敌方单位 $i$ 剩余生命值的期望值。

对于每一行，如果行内包含多个数，则用单个空格将它们隔开。

对于所有数值，请输出它们对 $998244353$ 取模的结果：即设答案化为最简分式后的形式为 $\frac{a}{b}$ ，其中 $a$ 和 $b$ 的互质。输出整数 $x$ 使得 $bx \equiv a\bmod 998244353$ 且 $0 \le x < 998244353$ 。（可以证明这样的整数 $x$ 是唯一的）

hint:
### 样例解释 1
针针按顺序施放如下技能：

1. 对敌方单位 $2$ 施放技能锁定：以 $1$ 的概率对其造成 $1$ 点伤害。此时 $2$ 号敌方单位必定剩余 $1$ 点生命值。
2. 对敌方单位 $2$ 施放技能结界：（由于 $2$ 号敌方单位尚存活，）必定命中 $2$ 号单位。
3. 对敌方单位 $2$ 施放技能锁定：以 $1$ 的概率对其造成 $1$ 点伤害。
4. 对敌方单位 $3$ 施放技能锁定：以 $1$ 的概率对其造成 $1$ 点伤害。此时三个敌方单位的生命值一定分别为 $1, 0 ,2$ ，敌方单位 $2$ 一定死亡。
5. 对敌方单位 $2$ 施放技能结界：（由于 $2$ 号敌方单位已死亡，）必定不命中任何单位。
6. 对敌方单位 $1, 2, 3$ 施放技能结界：命中敌方单位 $1, 3$ 的概率是相等的，即各 $\frac{1}{2}$ 。 最终，三个敌方单位的剩余生命值一定为 $1 , 0 , 2$ 。

### 样例解释 2
对于各结界技能的分析：

1. 第 $1$ 个结界（目标为敌方单位 $1,2$ ）：
- $2$ 号敌方单位存活的概率为 $\frac{1}{2}$ ， $1$ 号敌方单位必定存活。
- 如果 $2$ 号敌方单位存活，那么结界命中 $1 , 2$ 的概率相等，均为 $\frac{1}{2}$ ；如果 $2$ 号敌方单位死亡，那么结界必定命中 $1$ 号敌方单位。
- 因此：命中 $1$ 号敌方单位的概率为 $\frac{1}{2} \times 1 + \frac{1}{2} \times \frac{1}{2} = \frac{3}{4}$ ；命中 $2$ 号敌方单位的概率为 $\frac{1}{2} \times 0 + \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$ 。
2. 第 $2$ 个结界（目标为敌方单位 $1, 2, 3$ ）：
- 三个敌方单位存活的概率分别为 $1, \frac{1}{2} , \frac{1}{3}$ 。
- $1 , 2 , 3$ 同时存活的概率为 $\frac{1}{6}$ ；只有 $1, 2$ 存活的概率为 $\frac{1}{3}$ ；只有 $1 , 3$ 存活的概率为 $\frac{1}{6}$ ；只有 $1$ 存活的概率为 $\frac{1}{3}$ 。
- 因此：命中 $1$ 号敌方单位的概率为 $\frac{1}{6} \times \frac{1}{3} + (\frac{1}{3}+\frac{1}{6}) \times \frac{1}{2}+ \frac{1}{3} \times 1 = \frac{23}{36}$ ；命中 $2$ 号敌方单位的概率为 $\frac{1}{6} \times \frac{1}{3} + \frac{1}{3} \times \frac{1}{2} = \frac{2}{9}$ ；命中 $3$ 号敌方单位的概率为 $\frac{1}{6} \times \frac{1}{3} + \frac{1}{6} \times \frac{1}{2} = \frac{5}{36}$ 。 最终，三个敌方单位的剩余生命值的期望值为 $1 , \frac{1}{2} , \frac{1}{3}$ 。

### 数据范围

我们记 $C$ 为结界技能的数量。

测试点编号|n=|Q=|C=|u,v|其他限制
-|-|-|-|-|-
1|5|21|6|u<v|无
2|60|199992|500|u<v|所有 p 均相等
3|60|23|6|u<v|所有m_i =1
4|60|199994|500|u<v|无
5|60|199995|500|u<v|无
6|60|199996|0|u<v|无
7|60|199997|500|u=v|无
8|200|199998|1000|u<v|无
9|200|199999|1000|u<v|无
10|200|200000|1000|u<v|无

对于所有测试点，保证 $n \le 200 , Q \le 200000 , C \le 1000 , m_i \le 100$ 。

提示

Q 的个位可以帮助你快速确定测试点的编号。
测试点顺序可能与难度无关。

感谢 @和泉正宗 提供题面


title: [JXOI2018] 守卫

background: 九条可怜是一个热爱运动的女孩子。

description:
这一天她去爬山，她的父亲为了她的安全，雇了一些保镖，让他们固定地呆在在山的某些位置，来实时监视九条可怜，从而保护她。

具体来说，一座山可以描述为一条折线，折线的下方是岩石。这条折线有 $n$ 个折点，每个折点上有一个亭子，第 $i$ 个折点的坐标是 $(i,h_i)$ 。九条可怜只可能会在亭子处玩耍，那些保镖也只会在亭子处监视可怜。

由于技术方面的原因，一个保镖只能监视所有他能看得到的，横坐标不超过他所在位置的亭子。我们称一个保镖能看到一个亭子 $p$ ，当且仅当他所在的亭子 $q$ 和 $p$ 的连线不经过任何一块岩石。特别地，如果这条连线恰好经过了除了 $p,q$ 以外的亭子，那么我们认为保镖看不到可怜。

雇佣保镖是一件很费钱的事情，可怜的父亲希望保镖越少越好。

可怜的父亲还希望得到详尽的雇佣保镖的方案，他知道有些亭子可能正在维修，他想对所有的 $1\leq l\leq r\leq n$ 计算：如果事先已知了只有区间 $[l,r]$ 的亭子可以用来玩耍（和监视），那么最少需要多少个保镖，才能让 $[l,r]$ 中的每一个亭子都被监视到。

可怜的父亲已经得到了一个结果，他希望和你核实他的结果是否正确。

inputFormat:
第一行输入一个整数 $n$ 表示亭子的数目。

接下来一行 $n$ 个整数，第 $i$ 个整数 $h_i$ 表示第 $i$ 个亭子的坐标是 $(i,h_i)$。

outputFormat: 对所有的 $1\leq l\leq r\leq n$ 计算：如果事先已知了可怜只会在 $[l,r]$ 这个区间的亭子里面玩耍，那么最少需要多少个保镖，才能让 $[l,r]$ 中的每一个亭子都被监视到。由于输出量太大，可怜的父亲只要你输出所有 $[l,r]$ 的答案的异或即可。

hint:
### 样例解释

如果 $r-l+1\leq 2$，那么答案显然是 $1$。

如果 $l=1$，$r=n$，那么答案是 $2$，需要安排两个保镖在 $(2,3),(3,1)$ 两个位置监视可怜。

### 数据范围与提示

对于 $30\%$ 的数据，$n\leq 20$。
对于 $70\%$ 的数据，$n\leq 500$。
对于 $100\%$ 的数据，$n\leq 5000$，$1\leq h_i\leq 10^9$。


title: 【模板】多项式除法

description:
给定一个 $n$ 次多项式 $F(x)$ 和一个 $m$ 次多项式  $G(x)$ ，请求出多项式 $Q(x)$, $R(x)$，满足以下条件：

 - $Q(x)$ 次数为 $n-m$，$R(x)$ 次数小于 $m$
 - $F(x) = Q(x) * G(x) + R(x)$

所有的运算在模 $998244353$ 意义下进行。

inputFormat:
第一行两个整数 $n$，$m$，意义如上。
第二行 $n+1$ 个整数，从低到高表示 $F(x)$ 的各个系数。
第三行 $m+1$ 个整数，从低到高表示 $G(x)$ 的各个系数。

outputFormat:
第一行 $n-m+1$ 个整数，从低到高表示 $Q(x)$ 的各个系数。
第二行 $m$ 个整数，从低到高表示 $R(x)$ 的各个系数。
如果 $R(x)$ 不足 $m-1$ 次，多余的项系数补 $0$。

hint: 对于所有数据，$1 \le m < n \le 10^5$，给出的系数均属于 $[0, 998244353) \cap \mathbb{Z}$。


title: 小白逛公园

background: 小新经常陪小白去公园玩，也就是所谓的遛狗啦…

description:
在小新家附近有一条“公园路”，路的一边从南到北依次排着 $n$ 个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。

一开始，小白就根据公园的风景给每个公园打了分。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第 $a$ 个和第 $b$ 个公园之间（包括 $a, b$ 两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。

那么，就请你来帮小白选择公园吧。

inputFormat:
第一行，两个整数 $n$ 和 $m$，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。

接下来 $n$ 行，每行一个整数，依次给出小白开始时对公园的打分。

接下来 $m$ 行，每行三个整数。其中第一个整数 $k$ 为 $1$ 或 $2$。

- $k=1$ 表示，小新要带小白出去玩，接下来的两个整数 $a$ 和 $b$ 给出了选择公园的范围 $(1 \le a,b \le n)$。测试数据可能会出现 $a > b$ 的情况，需要进行交换；
- $k=2$ 表示，小白改变了对某个公园的打分，接下来的两个整数 $p$ 和 $s$，表示小白对第 $p$ 个公园的打分变成了 $s(1\le p\le N)$。

outputFormat: 小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。

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

对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^5$，$1 \le m \le 10^5$，所有打分都是绝对值不超过 $1000$ 的整数。


title: 上帝造题的七分钟

background: 裸体就意味着身体。

description:
“第一分钟，X 说，要有矩阵，于是便有了一个里面写满了 $0$ 的 $n\times m$ 矩阵。

第二分钟，L 说，要能修改，于是便有了将左上角为 $(a,b)$，右下角为 $(c,d)$ 的一个矩形区域内的全部数字加上一个值的操作。

第三分钟，k 说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。

第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。

第五分钟，和雪说，要有耐心，于是便有了时间限制。

第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过 $32$ 位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”。

——《上帝造裸题的七分钟》。

所以这个神圣的任务就交给你了。

inputFormat:
输入数据的第一行为 `X n m`，代表矩阵大小为 $n\times m$。
从输入数据的第二行开始到文件尾的每一行会出现以下两种操作：
-    `L a b c d delta` —— 代表将 $(a,b),(c,d)$ 为顶点的矩形区域内的所有数字加上 $delta$。
-    `k a b c d`     —— 代表求 $(a,b),(c,d)$ 为顶点的矩形区域内所有数字的和。

请注意，$k$ 为小写。

outputFormat: 针对每个 $k$ 操作，在单独的一行输出答案。

hint:
对于 $10\%$ 的数据，$1 \le n \le 16$，$1 \le m \le 16$， 操作不超过 $200$ 个。

对于 $60\%$ 的数据，$1 \le n \le 512$，$1 \le m \le 512$。

对于 $100\%$ 的数据，$1 \le n \le 2048$，$1 \le m \le 2048$，$-500 \le delta \le 500$，操作不超过 $2\times 10^5$ 个，保证运算过程中及最终结果均不超过 $32$ 位带符号整数类型的表示范围。


title: [JXOI2018] 游戏

background: 九条可怜是一个富有的女孩子。

description:
她长大以后创业了，开了一个公司。 但是管理公司是一个很累人的活，员工们经常背着可怜偷懒，可怜需要时不时对办公室进行检查。

可怜公司有 $n$ 个办公室，办公室编号是 $l$ 到 $l+n-1$ ，可怜会事先制定一个顺序，按照这个顺序依次检查办公室。一开始的时候，所有办公室的员工都在偷懒，当她检查完编号是 $i$ 的办公室时候，这个办公室的员工会认真工作，并且这个办公室的员工通知所有办公室编号是 $i$ 的倍数的办公室，通知他们老板来了，让他们认真工作。因此，可怜检查完第 $i$ 个办公室的时候，所有编号是 $i$ 的倍数(包括 $i$ )的办公室的员工会认真工作。

可怜发现了员工们通风报信的行为，她发现，对于每种不同的顺序 $p$ ，都存在一个最小的 $t(p)$ ，使得可怜按照这个顺序检查完前 $t(p)$ 个办公室之后，所有的办公室都会开始认真工作。她把这个 $t(p)$ 定义为 $p$ 的检查时间。

可怜想知道所有 $t(p)$ 的和。

但是这个结果可能很大，她想知道和对 $10^9+7$ 取模后的结果。

inputFormat: 第一行输入两个整数 $l,r$ 表示编号范围，题目中的 $n$ 就是 $r-l+1$ 。

outputFormat: 一个整数，表示所有 $t(p)$ 的和。

hint:
### 样例解释

考虑所有办公室被检查的相对顺序:

{2 3 4} ,时间是 2 。
{3 2 4} ,时间是 2 。
{4 2 3} ,时间是 3 。
{4 3 2} ,时间是 3 。
{2 4 3} ,时间是 3 。
{3 4 2} ,时间是 3 。

和是 $16$ 。

### 数据范围

对于 20% 的数据，$r-l+1\leq 8$。
对于另 10% 的数据，$l=1$。
对于另 10% 的数据，$l=2$。
对于另 30% 的数据，$l\leq 200$。
对于 100% 的数据，$1\leq l\leq r\leq 10^7$。


title: [CTSC2008] 奥运抽奖

description:
距 $2008$ 年北京奥运会开幕还有90天时，CTSC 准备为志愿者们举行一次抽奖活动。作为志愿者的一员，你对这次抽奖活动自然是万分期待。

CTSC 委员会介绍了抽奖活动的规则。设总共有 $p$ 个参加抽奖的志愿者，开始时每一个志愿者领取一个 $0 \sim p-1$ 的号码。任意两个志愿者领取的号码不同。

屏幕的正中央是五福娃的头像，他们不停的眨眼欢迎大家。开始抽奖时，工作人员按下屏幕旁边的按钮，等待屏幕上的画面静止下来。这时，福娃们都停止眨眼了。

当然，画面静止时，有的福娃的眼睛可能是睁开的，有的是闭上的。如果所有福娃的眼睛都闭上了，工作人员需要重新按一 下按钮。这样，直到至少有一个福娃的眼睛是睁开的。接着，工作人员开始观察有哪些福娃的眼睛是睁开的。

工作人员对五个福娃都标了号。贝贝、晶晶、欢欢、迎迎、妮妮的标号分别是 $2$、$3$、$4$、$5$、$6$（工作人员认为 $0$ 和 $1$ 都不是好数字）。定义幸运数字如下：

- 如果一个福娃的眼睛是睁开的，那么他（她）对应的标号就是幸运数字；

- 如果数字 $l_1$ 和 $l_2$（可能相等）都是幸运数字，那么他们的乘积也是幸运数字；

- 其他的数字都不是幸运数字。

用 $L$ 表示所有数字的集合，例如，如果贝贝、晶晶的眼睛是睁开的，欢欢、迎迎、妮妮的眼睛是闭上的，则 $L=\{2,3,4,6,8,9,12,…\}$。令 $l(x)$ 表示第 $x$ 大的幸运数字。例如，上面的例子中，$l(1)=2$，$l(4)=6$ 等等。

接着，工作人员开始随机产生两个数，小的数是 $a$，大的数字是 $b$。定义集合 $T_{a,b}$ 为：$T_{a,b}=\{d|d∈L,l(a)|d,d|l(b)\}$（其中 $x|y$ 表示 $x$ 整除 $y$ ）

定义一个自然数的有限子集的特征值 $f$ 如下：

- 空集的特征值为$0$。

- 对于非空集合 $S$，令 $d$ 为 $S$ 中的最小元素，则

$$f(S)=d+f(S\backslash d)+q\times d\times f(S\backslash d)$$

其中， $S\backslash d$ 表示把 $S$ 删除元素 $d$ 后的集合，$q$ 是一个给定的非负整数。

在 $a$ 和 $b$ 产生以后，中奖的志愿者就确定了，他的号码是 $f(T_{a,b})$ 除以 $p$ 的余数。工作人员会产生多次 $a$，$b$，这样就能形成多个中奖者。

但是，抽奖现场的程序需要很长的时间才能算出中奖的志愿者。出于对中奖结果的热切期待，你便想要重新写一下计算程序，于是，你的目光移向了前面的键盘……。

inputFormat:
输入的第一行给出用空格隔开的五个数，每个数不是 $0$ 就是 $1$，分别表示贝贝、晶晶、欢欢、迎迎、妮妮的眼睛是否睁开。$0$ 对应眼睛闭上，$1$ 对应眼睛睁开。$5$ 个数不可能都是 $0$。

第二行给出了用空格隔开的两个数，$p$ 和 $q$。 其中 $p$ 表示参加抽奖的志愿者的人数，$q$ 如前所述，用来计算集合的特征值。

第三行给出了数 $n$，表示抽取的 $a$ 和 $b$ 的次数。

接下来的 $n$ 行，每一行有两个数 $a$、$b$，中间用空格隔开，表示一次抽奖产生的两个数。

outputFormat: 输出共 $n$ 行，每一行一个整数，表示一次抽奖中中奖者的号码。顺序与输入的 $n$ 对 $a$、$b$ 一一对应。当然，一个人可能中奖多次。


title: [CTSC2008] 图腾

description:
在完成了古越州圆盘密码的研究之后，考古学家小布来到了南美大陆的西部。相传很久以前在这片土地上生活着两个部落，一个部落崇拜闪电，另一个部落崇拜高山，他们分别用闪电和山峰的形状作为各自部落的图腾。

小布的团队在山洞里发现了一幅巨大的壁画，壁画上被标记出了$N$个点，经测量发现这$N$个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这$N$个点的相对位置有关，因此不妨设坐标分别为$(1, y_1) , (2, y_2), ..., (n, y_n)$，其中$y_1\sim y_n$是$1\sim N$的一个排列。

小布的团队打算研究在这幅壁画中包含着多少个图腾，其中闪电图腾的定义图示如下（**图腾的形式只与$4$个纵坐标值的相对大小排列顺序有关**）：

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

即$1≤a<b<c<d≤N,y_a<y_c<y_b<y_d$

崇拜高山的部落有两个氏族，因而山峰图腾有如下两种形式，左边为$A$类，右边为$B$类（**同样，图腾的形式也都只与$4$个纵坐标值的大小排列顺序有关**）：

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

即$1≤a<b<c<d≤N,y_a<y_b<y_d<y_c$

即$1≤a<b<c<d≤N,y_a<y_d<y_c<y_b$

小布的团队希望知道，这$N$个点中两个部落图腾数目的差值。因此在本题中，你需要帮助小布的团队编写一个程序，计算闪电图腾数目减去山峰图腾数目的值，由于该值可能绝对值较大，本题中只需输出该值对$16777216$的余数（注意余数必为正值，例如$-1$对$16777216$的余数为$16777215$）。

inputFormat:
输入文件totem.in中第一行包含一个整数$N$，为点的数目。
接下来一行包含$N$个整数，分别为$y_1, y_2, …, y_n$。保证$y_1, y_2, …, y_n$是$1\sim N$的一个排列。

outputFormat: 输出文件totem.out仅包含一个数，表示闪电图腾数目与山峰图腾数目的差值对$16777216$的余数。

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

样例一中共有$1$个闪电图腾（$1324$）和$1$个$B$类山峰图腾（$1532$）。

样例二中仅有一个$A$类山峰图腾（$1243$），故差值为$-1$，答案为$16777215$。

**【数据规模】**

对于$10\%$的数据，$N  ≤ 600$；

对于$40\%$的数据，$N  ≤ 5000$；

对于$100\%$的数据，$N ≤ 200000$。


title: [SCOI2003] 切割多边形

description:
我们希望通过切割得到一个凸 $p$ 边形，$p\le 8$。

一开始的时候，你有一个 $n\times m$ 的矩形，即它的四角的坐标分别为 $(0,0), (0,m), (n,0), (n,m)$。每次，你可以选择一条直线把当前图形切割成两部分，保留其中一个部分（另一部分扔掉），切割线的长度为此直线在多边形内部的部分的长度。

求出最短的切割线总长度。

下面是一个例子，我们需要得到中间的多边形。

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

分别沿着直线 $1,2,3,4$ 进行切割即可，得到中间的四边形。

inputFormat:
第一行有两个整数 $n,m\ (0 < n,m < 500)$。

第二行为一个整数 $p(3\le p\le 8)$，以下 $p$ 行每行为两个整数 $x, y(0 < x < n, 0 < y < m)$，为按顺时针给出的各顶点坐标。

数据保证多边形的是凸的，无三点共线，输入数据无错误。

outputFormat: 仅一行，为最短切割线的总长度，四舍五入到小数点后 $3$ 位。允许有 $0.001$ 的误差。

hint: 样例对应于图中给出的例子。


title: [CTSC2006] 投篮游戏

description:
在大学里，体育课有很多门，每个人都可以选自己最喜欢的项目。King这学期选的是篮球，因为篮球课的老师是一个十分有趣的人。

上课的第一天，老师宣布了这门课的评分规则：

有n个篮球(n ≥ m)，老师事先在每个球上写了一个整数(不一定相同，绝对值小于10000)。	有m个篮，每个篮板上有一个计分器，显示一个整数。一个学生开始考核前先将所有计分器显示值赋为1。

每个学生考核时要进行n次投篮：选择任意一个篮球投向任意一个篮。最后他必须将所有球全部投出且每个球恰好投出一次，要求每个篮至少被投进过一次。

如果学生将一个写有整数x的篮球投进了某个计分器显示为y的篮，则该篮板上的计分器显示值将从y变成y×x。

一个学生的**原始得分**S定义为m个计分器的显示值之和，如果S越大则老师给这个学生的最终打分越高（事实上，老师根据名次按照正态分布给分，但此超出本题了讨论范围）。

King是一个神投手，他保证能将n个球全都投进。但是King的数学十分糟糕，他不知道该如何安排投篮，才能使得自己的**原始得分**最大，你能帮帮他吗？

inputFormat:
输入有多组数据，每组数据有两行：

第一行两个整数n,m。

第二行n个整数，用一个空格分开，表示老师在n个篮球上分别写下的整数。

文件以0 0结尾。一个文件中最多只有10组数据。

outputFormat:
每组数据一行，包含一个整数$S_{max}$，表示最大可能的原始得分。

提示：$S_{max}$可能超过任何基本整数类型。$S_{max}$也可能比0小。


title: [CTSC2005] 魔术眼镜盒

description:
小花买了一只很有意思的魔术眼镜盒。眼镜盒盖由两半组成，每半水平分割为若干条纸带，如图1所示（左半为盒子底部，右半为盒子顶部）。灰色表示盒子的表面，白色表示空白区域。下图的眼镜盒有3个纸带，每个纸带的长度均为50(mm)，但其他眼镜盒可能有不同数目的纸带，每条纸带的长度也不一定一样。

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

眼镜盒的特别之处在于它有两种折法。图1的(a)和(b)就是它的两种折法，第一种折法把区域1，2，3暴露在盒子的表面，而第二种折法把区域4，5，6暴露在盒子的表面。如果一个眼镜盒有n条纸带，那么折法1暴露出来的区域编号为1，2，...，n，折法2暴露出来的区域编号为n+1，n+2，...，2n。第i个区域和第n+i个区域是全等的。**在本题中，你不需要了解两种折法是怎么互相转化的**。

小花有两种正方形纸片：公式纸片和卡通图片。她想把公式纸片贴在区域1，2，3中，而把卡通图片贴在4，5，6中，在学习的时候使用折法1，休息的时候使用折法2。每张纸片都必须完全位于区域的内部，纸片边界可以和区域边界重合。不同的纸片必须贴在不同的区域，有的区域内也可以不贴纸片。

标准的眼镜盒长度为150，宽度为55，面积为8250，分为长度相等的三个纸带，因此每个白色区域的尺寸为55×50。小花有3张公式纸片，边长分别为40，45和52；4张卡通纸片，边长分别为10, 27, 30, 55，只能在正面放40和45，反面放10，27和30。显然，标准眼镜盒并不能满足小花的要求。

好在眼镜盒公司允许用户订做自己的眼镜盒，盒子长度、宽度、纸带数目和每条纸带的长度都是可以任意修改的，即长度可以不是150，宽度也可以不是55。小花发现如果眼镜盒子尺寸不变，而换四条长度为40, 45, 55和10的纸带，所有纸片就都能放下了，如图2所示。

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

面积越大的眼镜盒越贵，因此小花希望买一个面积不超过s的眼镜盒。应该如何选购眼镜盒、设计纸带和贴小纸片，使得眼镜盒上的小纸片总数尽量多？纸片最多的前提下，眼镜盒的面积最小是多大？

inputFormat: 输入文件的第一行为三个整数n，m和s，分别表示公式纸片，卡通纸片的个数，以及眼镜盒的面积上限。第二行有n个正整数，表示每个公式纸片的边长；第三行有m个正整数，表示每个卡通图片的边长。

outputFormat: 输出文件仅包含一行，有两个整数$C_{max}$和$S_{min}$，表示能贴在盒上的纸片个数的最大值，及在此条件下眼镜盒面积的最小值。


title: [CTSC2005] 合并正方形

description:
一个二维平面初始时为空，有一串往平面中加入点的命令。

加入的点有两种，这里称为 A 类点和 B 类点（如图 1，黑色正方形表示 A 类点，小圆黑点表示 B 类点）。A 类点一定位于 $X$ 轴上，而且不会重叠，而 B 类点可以出现在平面上的任何一个位置，可以重叠。每个 B 类点有一个权值 $W$。

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

处理：一、最初，将相邻两个 A 类点之间连一个与 $X$ 轴成 $45$ 度的正方形（如图 2）。二、每次可以将任意两个有公共点的正方形合并为一个大正方形，合并之后两个小正方形消失。图 2 的左数第 $2$、$3$ 的正方形合并后在图 3 中表示为灰边正方形。

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

合并后的正方形将平面划分为 $9$ 个区域，与正方形 $4$ 条边相邻的 $4$ 个区域分别为图 3 中的 I，II，III，IV。落在区域 I 中的 B 类点的权值和记为 $w_1$，落在区域 II 中的 B 类点的权值和记为 $w_2$，落在区域 III 中的 B 类点的权值和记为 $w_3$，落在区域 IV 中的 B 类点的权值和记为 $w_4$。落在灰色正方形内部的 B 类点的权值和记为 $w_5$（B 类点保证不会出现在任何一个区域的边界上），则合并费用为 $w_1+2w_2+3w_3+4w_4+5w_5$。落在其他区域的 B 类点不予考虑。每次合并之后并不影响 B 类点在平面上的位置和它自己所拥有的权值。

每进行一次合并，由 A 类点形成的正方形会减少一个，直到只剩下一个正方形为止。合并总费用为每次合并费用之和。不同合并顺序的合并费用可能会不同。

点是一个一个加入到平面的。加入第 $i$ 个 A 类点后，平面上有 $i$ 个 A 类点和在此之前加入的所有 B 类点。设此时的**最小**合并费用为 $f(i)$。

给定费用限制 $L$，编程求出 A 类点的最大数目 $K$，使得**前 $K$ 个 A 类点**的最小合并费用不超过 $L$，即 $f(K)\le L$。

inputFormat:
第一行包含两个数 $M$，$L$，表示有 $M$ 条加入点的命令，费用限制为 $L$。

以下包含 $M$ 行，每行一个字母表示点的类型。`A` 表示 A 类点，`B` 表示 B 类点。对于 A 类点，后面一个数表示这个点的 $X$ 坐标；对于 B 类点，后面三个数表示这个点的 $X$，$Y$ 坐标和这个点的权值。

outputFormat: 输出文件仅包含一个整数 $K_{max}$，即使 $f(K) \le L$的最大 $K$。

hint:
### 样例说明

输入最后一个点时，所有点如下图。B 类点旁边的数字为权值。

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

合并前 $3$ 个点的最小费用为 $f(3) = 27$，合并前 $4$ 个点的最小费用 $f(4) = 36$。由于 $f(3) < 30$ 而 $f(4) > 30$，因此最大的 $K$ 为 $3$。

### 约定

$3 \le \text{A 类点的数目} \le 30000$

$5 \le M \le 100000$

$X$，$Y$均为整数，绝对值不超过 $10000000$

$L, W$ 均为实数，$0<W \le 10000$，$L\le 10^{11}$，所有输入实数最多保留三位小数

$50\%$ 的数据满足 $M \le3000$


title: [CTSC2005] 玩具的重量

description:
冰冰有三个玩具：皮卡秋、维妮孙悟空和芭比娃娃。她并不知道这些玩具的具体重量（采用NOI单位），但是知道每个玩具重量的大概范围，如下表：

表1. 玩具和它们的最小、最大可能重量|皮卡秋|维妮孙悟空|芭比娃娃
:-:|:-:|:-:|:-:
最小可能重量|1|2|3
最大可能重量|3|4|5
这些范围太粗略，冰冰希望能把它们缩小一些。

正好佳佳有一个电子天平，不仅可以告诉你左右两边是否一样重，还可以告诉你左边比右边重（或轻）多少。天平很大，左右两边都可以放任意多件玩具。

冰冰向佳佳借电子天平，希望能算出每个玩具的精确重量。佳佳为了考验冰冰，只允许她把任意一个玩具往天平的左侧和右侧最多各放一次。例如，如果她曾经把皮卡秋放在天平的左侧，则她不能再次把它放在天平的左侧。冰冰同意了。她一共称量了两次，结果如下（数字表示左边比右边重多少）：

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

根据结果和表1，可以确定三个玩具的重量一定是3，4，3，也就是说，通过称量结果所得到的更新后的重量范围是：

表2. 根据称量结果所得到的精确范围|皮卡秋|维妮孙悟空|芭比娃娃
:-:|:-:|:-:|:-:
最小可能重量|3|4|3
最大可能重量|3|4|3
冰冰以后还会买很多很多玩具，她不想每次都自己计算每个玩具的重量。她需要写一个程序计算每个玩具最精确的重量下限和上限，你能帮她吗？

inputFormat: 输入文件第一行包含两个整数n和m，即玩具的个数和称量的次数。第二行包含2n个数，第2i-1个数和第2i个数分别表示第i个玩具的重量初始下限和初始上限。以下m行，每行前三个数L，R，D表示左边的玩具数、右边的玩具数和左右两边的重量差(L, R>=0)，接下来的L个数为天平左边的玩具编号，再接下来的R个数为天平右边的玩具编号。输入保证每个玩具在天平的每一边最多出现一次。

outputFormat: 输出文件包含2n个整数，第2i-1个数和第2i个数分别表示第i个玩具的重量下限和上限，即最小可能的整数重量和最大可能的整数重量。如果无解（可能是天平坏了），只输出一个数-1。

hint:
【样例解释】

样例1对应于题目描述中的例子。

在样例2中，冰冰有三个玩具，重量的原始范围为1~5, 2~5, 1~3。只有一次称量，天平的左边是玩具1和玩具2，右边是玩具3。左边比右边重1个单位。根据此结果，可以判断三个玩具的重量范围为1~2，2~3和2~3。

【约定】

3<=n<=200, 1<=m<=100，重量上限不超过20000。

50%的数据满足3<=n<=10，1<=m<=5。


title: [CTSC2004] 最优切割

background:
HURRICANE小组的成员最近去工厂实习，在实习的过程中遇到了这样的一个问题。即要在一个模板内，切割出一个零件。现已知模板和零件都是给定的凸多边形，且零件在模板中的位置已经固定。我们知道，对于零件来说，除相邻的两边外，任何两条边的延长线的交点都在模板之外。

由于工厂的加工条件所限，切割时，每一刀必须沿零件的某一条边所在的直线切下，把模板分成两部分，然后保留含有零件的一部分，再继续切割。现定义每一刀的费用为模板上切痕的长度。问如何选择切割顺序，才能使花费最少？

description:
你的程序需要根据给定的输入，给出符合题意的输出：

- 输入包括模板及零件的形状和坐标；

- 你需要根据给出的输入，计算出把模板切割成为零件的最少花费；

- 输出中只包括一个数，即最少的花费。

inputFormat:
输入文件包括两个部分，分别描述模板和零件的形状及坐标：

- 第一行为模板的顶点个数n（3≤ n≤ 2000）。下面的n行每行两个实数x，y（-1,000,000<x, y<1,000,000），为按逆时针方向给出模板顶点的坐标。

- 第n+2行为零件的顶点个数m（3≤ m≤ 2000）。下面的m行每行两个实数x，y（-1,000,000<x, y<1,000,000）为按逆时针方向给出的零件顶点的坐标。

outputFormat: 输出文件中只需要包括一个整数，为最少花费四舍五入到整数后的值。


title: [CTSC2004] 数字搜索

background:
HURRICANE小组最近接到了一个搜索文本的任务，即从一个由数字构成的长文本中，匹配满足指定条件的子串。搜索的条件采用形如‘(0+10\*1)\*10\*’这样的正则表达式来描述。其中正则表达式的归纳定义如下：

1. 0, 1, …, 9，0\*, 1\*, …, 9\*是正则表达式；

2. 如果A和B是正则表达式，则(A)，A+B，AB，(A)\*都是正则表达式；

3. 只有按以上方法构造出来的表达式才是正则表达式。

其中，A+B表示“或者”关系，AB表示“连接”关系，(A)\*表示A的内容“重复”零次或者多次。比如正则表达式(12+3)(4+5)6\*，就可以匹配以124，125，34，35之一开头，之后接零0个或任意多个6的字符串（例如字符串12566）。正则表达式(1+0)\*可以匹配所有由0和1构成的字符串，或者是空串。如果一个正则表达式不能匹配空串，则称它是非空的。**本题考虑的都是非空正则表达式**。

如果在给定文本的某一个位置，存在一个以该位置结束的子串，能够被给定的非空正则表达式匹配，则称该位置是可匹配的。现在HURRICANE小组接到的任务就是找出所有可匹配的位置。你能帮助他们完成这个任务么？

description:
你的程序需要根据给定的输入，给出符合题意的输出：

- 输入包括一个满足如上定义的正则表达式，以及一长串文本；

- 你需要根据输入的正则表达式及文本，找出文本中所有可匹配的位置；

- 你给出的输出需要包括所有可匹配的位置。

inputFormat:
输入文件regular.in的第一行描述一个正则表达式，第二行为需要处理的文本：

- 第一行的正则表达式包括由一个空格分开的两个部分：

- 一个非负整数n（1≤ n≤ 10），表示我们所要考虑的数字集（即在正则表达式和文本中所出现的数字）是0, 1, …, n–1。

- 接下来是一个正则表达式，它由{‘(‘, ’)’, ’+’, ’*’}中的4个符号和{0, …, n–1}中的数字构成，表达式的长度不超过500个字符。

- 第二行为一个由0到n-1之间数字构成的字符串，为需要处理的文本。该文本长度不超过10,000,000个字符。

outputFormat: 输出文件只有一行，包括一些由空格分开的整数，按从小到大的顺序依次输出所需处理的文本中每一个可匹配的位置。

hint:
**说明：**对于输入示例，需要处理的文本是’312331’，其中只有第5个字符所在的位置（下划线所在处）是可匹配的。这时正则表达式’12333+33'中的’33’可以与之匹配。

**提示：**在本次的测试数据中，有6个测试点中的正则表达式不出现’*’，其中有3个测试点，正则表达式只由数字和’+’构成。有一个测试点的待处理文本不超过1,000,000个字符。


title: [THUWC2017] 在美妙的数学王国中畅游

background:
数字和数学规律主宰着这个世界。

机器的运转，

生命的消长，

宇宙的进程，

这些神秘而又美妙的过程无不可以用数学的语言展现出来。

这印证了一句古老的名言：

“学好数理化，走遍天下都不怕。”

description:
学渣小R 被大学的数学课程虐得生活不能自理，微积分的成绩曾是他在教室里上的课的最低分。然而他的某位陈姓室友却能轻松地在数学考试中得到满分。为了提升自己的数学课成绩，有一天晚上（在他睡觉的时候），他来到了数学王国。

数学王国中，每个人的智商可以用一个属于 $ [0,1]$ 的实数表示。数学王国中有 $n$ 个城市，编号从 $0 \sim n-1$，这些城市由若干座魔法桥连接。每个城市的中心都有一个魔法球，每个魔法球中藏有一道数学题。

每个人在做完这道数学题之后都会得到一个在 $[0,1]$ 内的分数。一道题可以用一个函数 $f(x)$ 表示。若一个人的智商为 $x$，则他做完这道数学题之后会得到 $f(x)$ 分。有三种形式：

-  正弦函数 $f(x)=\sin(a x + b)\ (a \in [0,1], b \in [0,\pi],a+b\in[0,\pi])$
-  指数函数 $f(x)=\text e^{ax+b}\ (a\in [-1,1], b\in [-2,0], a+b\in [-2,0])$
-  一次函数 $f(x) = ax + b\ (a\in [-1,1],b\in[0,1],a+b\in [0,1])$

数学王国中的魔法桥会发生变化，有时会有一座魔法桥消失，有时会有一座魔法桥出现。但在任意时刻，只存在至多一条连接任意两个城市的简单路径（即所有城市形成一个森林）。在初始情况下，数学王国中不存在任何的魔法桥。

数学王国的国王拉格朗日很乐意传授小R 数学知识，但前提是小R 要先回答国王的问题。这些问题具有相同的形式，即一个智商为 $x$ 的人从城市 $u$ 旅行到城市 $v$（即经过 $u \to v$ 这条路径上的所有城市，包括 $u$ 和 $v$）且做了所有城市内的数学题后，他所有得分的总和是多少。

inputFormat:
第一行两个正整数 $n,m$ 和一个字符串 $type$。表示数学王国中共有 $n$ 座城市，发生了 $m$ 个事件，该数据的类型为 $type$。

$type$ 字符串是为了能让大家更方便地获得部分分，你可能不需要用到这个输入。其具体含义在 **【限制与约定】** 中有解释。

接下来 $n$ 行，第 $i$ 行表示初始情况下编号为 $i$ 的城市的魔法球中的函数。一个魔法用一个整数 $f$ 表示函数的类型，两个实数 $a,b$ 表示函数的参数，若

- $f=1$，则函数为 $f(x)=\sin(ax+b)$
- $f=2$，则函数为 $f(x)=\text e^{ax+b}$
- $f=3$，则函数为 $f(x)=ax+b$

接下来 $m$ 行，每行描述一个事件，事件分为四类。

- `appear u v` 表示数学王国中出现了一条连接 $u$ 和 $v$ 这两座城市的魔法，保证连接前 $u,v$ 这两座城市不能互相到达。

- `disappear u v` 表示数学王国中连接 $u,v$ 这两座城市的魔法桥消失了，保证这座魔法桥是存在的。

- `magic c f a b` 表示城市 $c$ 的魔法球中的魔法变成了类型为 $f$，参数为 $a,b$ 的函数

- `travel u v x` 表示询问一个智商为 $x$ 的人从城市 $u$ 旅行到城市 $v$ 后，他得分的总和是多少。若无法从 $u$ 到达 $v$，则输出一行一个字符串 `unreachable`。

outputFormat: 对于每个询问，输出一行实数，表示得分的总和。

samples:
3 7 C1
1 1 0
3 0.5 0.5
3 -0.5 0.7
appear 0 1
travel 0 1 0.3
appear 0 2
travel 1 2 0.5
disappear 0 1
appear 1 2
travel 1 2 0.5

hint:
【限制与约定】
对于 $100\%$ 的数据，$1\le n\le 10^5, 1\le m \le 2 \times 10^5$ 。

本题共有 20 个数据点，每个数据点 5 分。

测试点|$n$|$m$|数据类型
:-:|:-:|:-:|:-:|
$1$|$\leq 100$|$\leq 200$|C1
$2 \sim 5$|$\leq 10^5$|$\leq 2 \times 10^5$|A0
$6$|$\leq 10^5$|$\leq 2 \times 10^5$|B0
$7 \sim 8$|$\leq 10^5$|$\leq 2 \times 10^5$|D0
$9 \sim 14$|$\leq 10^5$|$\leq 2 \times 10^5$|A1
$15 \sim 17$|$\leq 10^5$|$\leq 2 \times 10^5$|C1
$18 \sim 20$|$\leq 10^5$|$\leq 2 \times 10^5$|D1

数据类型的含义：

A：不存在 `disappear` 事件，且所有`appear`事件中的 $u=v-1$

B：不存在 `disappear` 事件

C：所有的 `travel` 事件经过的城市总数 $\le 5 \times 10^6$（不可到达的城市对不计入在内）

D：无限制

0：所有 `travel` 事件中，$x=1$（即所有人的智商均为 $1$）

1：无限制

【评分标准】

如果你的答案与标准答案的相对误差在 $10^{-7}$ 以内或绝对误差在 $10^{-7}$ 以内，则被判定为正确。

如果你的所有答案均为正确，则得满分，否则得 0 分。

请注意输出格式：每行输出一个答案，答案只能为 `unreachable` 或者一个实数（建议使用科学计数法表示）。每行的长度不得超过 50。错误输出格式会被判定为 0 分。

【小R 教你学数学】

若函数 $f(x)$ 的 $n$ 阶导数在 $[a,b]$ 区间内连续，则对 $f(x)$ 在 $x_0 \ (x_0\in[a,b])$ 处使用 $n$ 次拉格朗日中值定理可以得到带拉格朗日余项的泰勒展开式

$$f(x)=\sum_{k=0}^{n-1}\frac{f^{(k)}(x_0)(x-x_0)^k}{k!}+\frac{f^{(n)}(\xi)(x-x_0)^n}{n!},x\in[a,b]$$

其中，当 $x>x_0$ 时，$\xi\in[x_0,x]$。当 $x<x_0$ 时，$\xi\in[x,x_0]$。

$f^{(n)}$ 表示函数 $f$ 的 $n$ 阶导数


title: [THUWC2017] 随机二分图

background: # 滥用本题评测将被封号

description:
某人在玩一个非常神奇的游戏。这个游戏中有一个左右各 $n$ 个点的二分图，图中的边会按照一定的规律随机出现。

为了描述这些规律，某人将这些边分到若干个组中。每条边或者不属于任何组 （这样的边一定不会出现），或者只属于一个组。

有且仅有以下三类边的分组：

0.  这类组每组只有一条边，该条边恰好有 $50\%$ 的概率出现。

1. 这类组每组恰好有两条边，这两条边有 $50\%$ 的概率同时出现，有 $50\%$ 的概率同时不出现。
2. 这类组每组恰好有两条边，这两条边恰好出现一条，各有 $50\%$ 的概率出现。

组和组之间边的出现都是完全独立的。

某人现在知道了边的分组和组的种类，想要知道完美匹配数量的期望是多少。你能帮助她解决这个问题吗？

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

第一行两个数 $n$ 和 $m$，表示图左右点数的数量和边的组的个数。我们用 $(a,b)$ （其中 $1 \le a,b \le n$）表示一条左端点为二分图左侧第 $a$ 个点，右端点为二分图右侧第 $b$ 个点的边。

接下来 $m$ 行，每行描述一个组。开头第一个数 $t$ 表示组的种类，$t=0$ 表示是一条边的组，$t=1$ 表示是两条边的组中的第一种，$t=2$ 表示是两条边的组中的第二种。如果 $t=0$， 接下来两个数 $a_1,b_1$ 表示组内的第一条边；否则，接下来四个数 $a_1,b_1,a_2,b_2$， 表示该组内的两条边分别为 $(a_1,b_1)$  和 $(a_2,b_2)$。保证每条边至多出现一次。

outputFormat:
输出到标准输出。

假设期望的完美匹配数量是$E$。输出一行表示
$$
(2^{n} E) \bmod (10^9 + 7)
$$
可以看出上式一定是一个整数。

hint:
## 【定义解释】

如果你对完美匹配和期望的定义很熟悉，那么你可以跳过本段。

对于一个左右各 $n$ 个点的二分图，它的一个完美匹配是指 $n$ 条没有公共点的边构成的匹配。

两个完美匹配不同，当且仅当它们至少含有一条不同的边。一个二分图完美匹配的数量定义为这张图能找到的两两不同的完美匹配的数量。

在题目的图中，边都是随机出现的，因此这个图中完美匹配的数量是一个随机变量。一个（离散型）随机变量 $X$ 的期望定义为以概率为权，$X$ 所有可能取值的加权平均数，即
$$
\sum_{x \in V(X)}P[X=x]\cdot x
$$
其中 $V(X)$ 表示 $X$ 所有可能的取值集合，$P[X=x]$ 表示 $X$ 取值为 $x$ 的概率。

## 【数据规模和约定】

对于 $5\%$ 的数据 $n \le 5$ 。
对于另 $5\%$ 的数据 $n \le 8$ 。
对于另 $10\%$ 的数据 $n \le 10$ 。
对于另 $15\%$ 的数据，只有$t = 0$ 的情况。
对于另 $5\%$ 的数据，只有$t = 0$ 的情况，且$m = n^2$，也就是该图为一个完全图。
对于另 $20\%$ 的数据，只有 $t =0$ 或者 $t=1$ 的情况。
对于另 $20\%$ 的数据，只有 $t =0$ 或者 $t=2$ 的情况。
对于 $100\%$ 的数据，$n \le 15$。


title: [CQOI2007] 三角形

description:
画一个等边三角形，把三边的中点连接起来，得到四个三角形，把它们称为 $T_1,T_2,T_3,T_4$，如图1。

把前三个三角形也这样划分，得到 $12$ 个更小的三角形，$T_{11},T_{12},T_{13},T_{14},T_{21},T_{22},T_{23},T_{24},T_{31},T_{32},T_{33},T_{34}$，如图2。

把编号以 $1,2,3$ 结尾的三角形又继续划分……最后得到的分形称为 Sierpinski 三角形。

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

如果三角形 $B$ 不包含三角形 $A$，且 $A$ 的某一条完整的边是 $B$ 的某条边的一部分，则我们说 $A$ 靠在 $B$ 的边上。例如 $T_{12}$ 靠在 $T_{14}$ 和 $T_4$ 上，但不靠在 $T_{32}$ 上。

给出 Spierpinski 三角形中的一个三角形，找出它靠着的所有三角形。

inputFormat: 输入仅一行，即三角形的编号，以 `T` 开头，后面有 $n$ 个 $1$ 到 $4$ 的数字。仅最后一个数字可能为 $4$。

outputFormat: 输出每行一个三角形编号，按字典序从小到大排列。


title: [CQOI2007] 矩形

description:
给一个a\*b矩形，由a\*b个单位正方形组成。你需要沿着网格线把它分成非空的两部分，每部分所有格子连通，且至少有一个格子在原矩形的边界上。“连通”是指任两个格子都可以通过水平或者竖直路径连在一起。 求方案总数。例如3*2的矩形有15种方案。

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

inputFormat:
输入仅一行，为两个整数a，b。
1<=a<=6, 2<=b<=7

outputFormat: 输出仅一行，即方案总数。


title: [AHOI2006] 棋盘上的问题

description:
可可和卡卡画了一张巨大的N*N的棋盘，他们想在这个棋盘上放尽量多的国际象棋的“車”，使得它们互相不能攻击到对方（車可以沿着棋盘的横向和纵向攻击）。

但这个答案显然就是棋盘的宽度N，于是可可在棋盘上规定了只有在有限的M个位置上才能放棋子。（其他位置不能放棋子，而車却可以穿过这个位置去攻击其他的棋子）然而这样也不会难倒两个聪明的小家伙，他们很快算出来这个答案是K。

于是卡卡又提出来一个问题：如果我们在这M个可以放棋子的位置中再去掉一个位置，而仍然保证最多能放下K个車，可行的方案又有多少种呢？

[任务] 编写一个程序：

从输入文件中读入棋盘的大小和棋盘上可以放棋子的位置信息；

计算出如题卡卡所说的可行方案的数目；

输出你得到的答案。

inputFormat:
第一行有两个正整数$N$和$M$，分别表示棋盘的大小和可以放棋子的位置数目。

以下$M$行，每行用$x_i$和$y_i$两个整数描述一个位置，表示这个位置是棋盘的第$x_i$行第$y_i$列。

同样的一个位置不会被描述两次。

($1<=i<=M, 1<=x_i, y_i<=N$)

$1<=N<=200 000, 1<=M<=600 000$

outputFormat: 输出文件中只有一个整数，表示可行方案的数目。


title: [SCOI2006] zh_tree

description:
张老师根据自己工作的需要，设计了一种特殊的二叉搜索树。

他把这种二叉树起名为 zh_tree，对于具有 $n$ 个结点的 zh_tree，其中序遍历恰好为 $(1,2,3,\cdots,n)$，其中数字 $1,2,3,\cdots,n$ 是每个结点的编号。$n$ 个结点恰好对应于一组学术论文中出现的n个不同的单词。

第j个单词在该组论文中出现的次数记为 $d_j$，例如，$d_2=10$表示第 $2$ 个结点所对应的单词在该组论文中出现了10次。设该组论文中出现的单词总数为 S，显然，$S=d_1+d_2+…+d_n$。记 $f_j=\frac{d_j}{S}$ 为第 j 个单词在该组论文中出现的概率（频率）。

张老师把根结点深度规定为0，如果第 $j$ 个结点的深度为 $r$，则访问该结点的代价 $h_j$ 为 $h_j=k(r+1)+c$，其中 $k$，$c$ 为已知的不超过 $100$ 的正常数。

则zh_tree是满足以下条件的一棵二叉树：它使 $h_1f_1+h_2f_2+…+h_nf_n$ 达到最小。

我们称上式为访问 zh_tree 的平均代价。 请你根据已知数据为张老师设计一棵 zh_tree。

inputFormat: 第 $1$ 行：$3$ 个用空格隔开的正数： $n$ $k$ $c$ 其中 $n<30$，为整数。$k$，$c$ 为不超过100的正实数。 第 $2$ 行：$n$ 个用空格隔开的正整数，为每个单词出现的次数(次数<200)。

outputFormat: 第1行：(5分)一个正实数，保留3位小数，为访问Zh_tree的最小平均代价。 第2行：（5分）n个用空格隔开的整数，为该树的前序遍历。一般地，作为最优解的前序遍历不一定唯一，只输出一个解。


title: [HNOI2006] 军机调度

description:
凯萨拥有一支由n个人组成的雇佣军，他们靠在威尼斯商行接任务过活。

这支军队的成份比较复杂，不同的人往往具有不同的技能，有的人还拥有多项技能。

威尼斯商行的任务也参差不齐，有的需要几个人合作完成，有的只需要一个人独立完成：有的很简单，不需要耗多少时间，因此报酬也较低，有的很有难度，需要多个人长期合作完成，因此报酬就高。完成这些任务的时间不会超过一个月。并且，一个人不能同时执行两项任务，也不能中途加入或者退出任务。但可以不执行任何任务。

一项只需要n个人来完成的任务，如果执行该任务的人数p大于n,那么反而会得到更少的报酬，即原报酬的1/(p-n+1)。

凯萨是一位英明的领袖，他往往在每个月的月底召开军事会议，总结上个月的成果，发给大家报酬，并指派下个月的任务。

请问，凯萨应该怎样指派任务，才能使总报酬最高？总报酬为多少？

inputFormat:
一行包含两个正整数n,m。彼此用空格隔开，

其中n〈10表示雇佣军的人数，m〈15表示下个月可选的任务数。

接下来的n行中第i行（对应文件的第i+1行）的第一个整数小于等于表示编号为i的雇佣军可执行的任务数

后面的整数是编号为i的雇佣军可以执行的所有任务的编号，这些整数之间用空格隔开。

最后的m行中，每行有四个整数b、e、p和r，彼此之间用空格隔开，

其中第j行（对应整个文件的第n+j+1行）是编号为j的任务的描述：

0<b<32表示该任务的开始日（这一天会被计入任务所需的时间中），

0<e<32表示该任务的结束日（这一天也会被计入任务所需的时间中），

p<10表示该任务所需人数，0<r<100000表示该任务的报酬。

outputFormat: 第一行只有一个整数t,表示最多可获得的总报酬


title: [ZJOI2011] 细胞

description:
2222年，人类在银河系外的某颗星球上发现了生命，并且携带了一个细胞回到了地球。经过反复研究，人类已经完全掌握了这类细胞的发展规律：

这种细胞最初的形态是“长条形”，一端是头，一端是尾，中间是躯干。细胞内部含有一列密码（你可以认为它是这种细胞的DNA）。密码是一个长度为n的数字串，且仅含有1~9这9种数字，沿着细胞的躯干从头到尾排列着。

首先，细胞会经历一次分裂。细胞将沿躯干方向分裂成若干个球体，躯干将退化成丝状物，连接着相邻的球体。在分裂过程中，质量是均匀分布的。换句话说，若分裂成k个球体，每个球体的质量为原来的1/k。然而，密码的分布是不确定的。若分割成k个球体，密码会被切割成k段（每段长度至少为1），并按从头到尾的顺序分布在各个球体中。如图，为其中一种合法的一次分裂：

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

接下来，细胞会经历二次分裂。对于每个球体，其中会含有一小段密码（注意他是有序的），我们把它看作一个十进制的数T。这个球体会被分割成T个小球体，并排成一排，之间用躯干退化成的丝状物相连接，并且质量仍然是均匀分布的，每个小球体的质量都是原球体的1/T。至此，密码已经发挥了它的作用，便消失了。如图，为二次分裂：

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

最后，细胞会进行变异。相邻小球体之间的丝状物可能会退化掉，这两个小球体便会以相切的方式直接连接。显然，二次分裂后，除两端外的每个小球体都有两段丝状物与其连接（头尾两端的小球体只有一段丝状物与其相连）。对于每个小球体，必须至少退化一段与其相连的丝状物，否则这个结构不稳定，会继续变异。如图，为一种稳定的变异：

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

现在，我们想知道，对于一个给定密码的细胞，总共有多少种稳定的结构。两种结构被认为相同，当且仅当他们拥有相同个数的小球体，从头到尾每个小球体的质量相同，并且从头到尾每对相邻小球体之间的连接方式相同（都是通过丝状物相连或都是通过相切直接相连）。你只需要回答这个结果 mod 1000000007即可。

inputFormat:
第一行为一个正整数n，表示细胞密码的长度。

第二行共n个数字，为给定的细胞密码，中间没有空格。

outputFormat: 只包含一个整数，为细胞的种数 mod 1000000007的结果。

hint:
对于5%的数据满足，n ≤ 6；

对于25%的数据满足，n ≤ 25；

对于60%的数据满足，n ≤ 100；

对于70%的数据满足，n ≤ 300；

对于100%的数据满足，n ≤ 1 000。


title: [ZJOI2011] 营救皮卡丘

description:
皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。

火箭队一共有$N$个据点，据点之间存在$M$条双向道路。据点分别从$1$到$N$标号。小智一行$K$人从真新镇出发，营救被困在$N$号据点的皮卡丘。为了方便起见，我们将真新镇视为$0$号据点，一开始$K$个人都在$0$号点。

由于火箭队的重重布防，要想摧毁$K$号据点，必须按照顺序先摧毁$1$到$K-1$号据点，并且，如果$K-1$号据点没有被摧毁，由于防御的连锁性，小智一行任何一个人进入据点$K$，都会被发现，并产生严重后果。因此，在$K-1$号据点被摧毁之前，任何人是不能够经过$K$号据点的。

为了简化问题，我们忽略战斗环节，小智一行任何一个人经过$K$号据点即认为$K$号据点被摧毁。被摧毁的据点依然是可以被经过的。

$K$个人是可以分头行动的，只要有任何一个人在$K-1$号据点被摧毁之后，经过$K$号据点，$K$号据点就被摧毁了。显然的，只要$N$号据点被摧毁，皮卡丘就得救了。

野外的道路是不安全的，因此小智一行希望在摧毁$N$号据点救出皮卡丘的同时，使得$K$个人所经过的道路的长度总和最少。

请你帮助小智设计一个最佳的营救方案吧！

inputFormat:
第一行包含三个正整数$N,M,K$。表示一共有$N+1$个据点，分别从$0$到$N$编号，以及$M$条无向边。一开始小智一行共$K$个人均位于$0$号点。

接下来$M$行，每行三个非负整数，第i行的整数为$A_i$，$B_i$，$L_i$。表示存在一条从$A_i$号据点到$B_i$号据点的长度为$L_i$的道路。

outputFormat: 仅包含一个整数$S$，为营救皮卡丘所需要经过的最小的道路总和。

hint:
【样例说明】

小智和小霞一起前去营救皮卡丘。在最优方案中，小智先从真新镇前往1号点，接着前往2号据点。当小智成功摧毁2号据点之后，小霞从真新镇出发直接前往3号据点，救出皮卡丘。

对于100%的数据满足$N ≤ 150, M ≤ 20 000, 1 ≤ K ≤ 10, L_i ≤ 10 000$, 保证小智一行一定能够救出皮卡丘。

至于为什么$K ≤ 10$，你可以认为最终在小智的号召下，小智，小霞，小刚，小建，小遥，小胜，小光，艾莉丝，天桐，还有去日本旅游的黑猫警长，一同前去大战火箭队。


title: [USACO10NOV] Buying Feed G

description:
约翰开车来到镇上，他要带$K$吨饲料回家。运送饲料是需要花钱的，如果他的车上有$X$吨饲料，每公里就要花费$X^2$元，开车D公里就需要$D\times  X^2$元。约翰可以从$N$家商店购买饲料，所有商店都在一个坐标轴上，第$i$家店的位置是$X_i$，饲料的售价为每吨$C_i$元，库存为$F_i$。

约翰从坐标$X=0$开始沿坐标轴正方向前进，他家在坐标$X=E$上。为了带$K$吨饲料回家，约翰最少的花费是多少呢？假设所有商店的库存之和不会少于$K$。

举个例子，假设有三家商店，情况如下所示：

|坐标|$X=1$|$X=3$|$X=4$|$E=5$|
|:-:|:-:|:-:|:-:|:-:|
|库存|$1$|$1$|$1$|
|售价|$1$|$2$|$2$|

如果$K=2$，约翰的最优选择是在离家较近的两家商店购买饲料，则花在路上的钱是$1+4=5$，花在商店的钱是$2+2=4$，共需要$9$元。

outputFormat: 一个整数,代表最小花费


title: [JXOI2018] 排序问题

background: 九条可怜是一个热爱思考的女孩子。

description:
九条可怜最近正在研究各种排序的性质，她发现了一种很有趣的排序方法： Gobo sort ！

Gobo sort 的算法描述大致如下：

- 假设我们要对一个大小为 $n$ 的数列 $a$ 排序。
- 等概率随机生成一个大小为 $n$ 的排列 $p$ 。
- 构造一个大小为 $n$ 的数列 $b$ 满足 $b_i=a_{p_i}$ ，检查 $b$ 是否有序，如果 $b$ 已经有序了就结束算法，并返回 $b$ ，不然返回步骤 2。

显然这个算法的期望时间复杂度是 $O(n\times n!)$ 的，但是九条可怜惊奇的发现，利用量子的神奇性质，在量子系统中，可以把这个算法的时间复杂度优化到线性。

九条可怜对这个排序算法进行了进一步研究，她发现如果一个序列满足一些性质，那么 Gobo sort 会很快计算出正确的结果。为了量化这个速度，她定义 Gobo sort 的执行轮数是步骤 2 的执行次数。

于是她就想到了这么一个问题：

现在有一个长度为 $n$ 的序列 $x$ ，九条可怜会在这个序列后面加入 $m$ 个元素，每个元素是 $[l,r]$ 内的正整数。 她希望新的长度为 $n+m$ 的序列执行 Gobo sort 的期望执行轮数尽量的多。她希望得到这个最多的期望轮数。

九条可怜很聪明，她很快就算出了答案，她希望和你核对一下，由于这个期望轮数实在是太大了，于是她只要求你输出对 $998244353$ 取模的结果。

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

接下来 $2 \times T$ 行描述了 $T$ 组数据。

每组数据分成两行，第 1 行有四个正整数 $n,m,l,r$ ，表示数列的长度和加入数字的个数和加入数字的范围。
第 2 行有 $n$ 个正整数，第 $i$ 个表示 $x_i$ 。

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

hint:
###样例解释

对于第一组数据，我们可以添加 $\{1,2,2\}$ 到序列的最末尾，使得这个序列变成 `1 3 4 1 2 2` ，那么进行一轮的成功概率是 $\frac{1}{180}$ ，因此期望需要 $180$ 轮。

对于第二组数据，我们可以添加 $\{5,6,7\}$ 到序列的最末尾，使得这个序列变成 `1 3 4 5 6 7` ，那么进行一轮的成功概率是 $\frac{1}{720}$ ，因此期望需要 $720$ 轮。

### 数据范围

对于 30% 的数据， $T\leq 10 , n,m,l,r\leq 8$。
对于 50% 的数据， $T\leq 300,n,m,l,r,a_i\leq 300$ 。
对于 60% 的数据， $\sum{r-l+1}\leq 10^7$ 。
对于 70% 的数据， $\sum{n} \leq 2\times 10^5$ 。
对于 90% 的数据， $m\leq 2\times 10^5$。
对于 100% 的数据， $T\leq 10^5,n\leq 2\times 10^5,m\leq 10^7,1\leq l\leq r\leq 10^9$ ， $1\leq a_i\leq 10^9,\sum{n}\leq 2\times 10^6$ 。


title: [COCI2009-2010#6] XOR

description:
坐标系下有若干个等腰直角三角形，且每个等腰直角三角形的直角顶点都在左下方，两腰与坐标轴平行。被奇数个三角形覆盖的面积部分为灰色，被偶数个三角形覆盖的面积部分为白色，如下图所示。
![](https://cdn.luogu.com.cn/upload/pic/18669.png)
已知 $N$个等腰直角三角形的顶点坐标及腰长，求灰色部分面积。

Mirko and Slavko have built their own LED display. The display is initially
white. During each of the $N$ parts of the testing phase, Mirko attached three
electrodes to the display in such way that they formed a right isosceles
triangle. He noticed that, after attaching the electrodes, all pixels in the
enclosing triangle are inverted (white pixels become black, and black pixels
become white).

Watching Mirko play with the electrodes, Slavko observed interesting shapes
emerging on the screen. Mathematically inclined as he is, first thing that
crossed his mind was how to calculate total area covered by black pixels. Help
him by writing a program to do just that!

inputFormat:
输入第一行包含一个整数 $N$，表示等腰直角三角形数量。

接下来 $N$行，每行三个整数 $X, Y, R$，分别表示等腰直角三角形的顶点坐标 $(X, Y)$与腰长 $R$。

First line of input contains an integer $N(1 \leq N \leq 10)$, number of triangles
formed by Mirko's fiddling with electrodes. Each of the following $N$ lines
contains three integers $X, Y$ and $R (1 \leq X, Y, R \leq 10^6
)$, describing a triangle. $(X, Y)$ are the coordinates of the lower left corner of the triangle, while $R$ represents the length of the two sides of the triangle.

outputFormat:
输出包含一个实数，表示灰色部分面积。保留1位小数。

The first and only line of output should contain the area covered by black
pixels, rounded to one decimal place.


title: 【模板】自适应辛普森法 2

description:
试计算积分

$\displaystyle{\int_0^\infty x^{\frac{a}{x}-x}\mathrm{d}x}$

保留至小数点后$5$位。若积分发散，请输出$\text{orz}$。

inputFormat: 一行，包含一个实数，为$a$的值

outputFormat: 一行，积分值或$\text{orz}$

hint:
$|a|\le50$。

请注意时空限制。


title: [COCI2006-2007#6] PRASE

description:
孩子们正在餐桌旁吃午餐，共有 $n$ 份食物，孩子们会按照从 $1$ 至 $n$ 的顺序依次取走这 $n$ 份食物。

当某个孩子取走了一份食物时，如果这个他之前已经取走的食物份数（不包括当前这一份）比其他人取走的食物份数之和还要多，那么他的妈妈就会提醒他注意自己不礼貌的行为。注意，虽然被妈妈提醒了，但是他仍然会取走这份食物。换句话说，妈妈的提醒对孩子的行为没有任何影响。

给定 $n$ 份食物分别被哪个孩子取走了，请求出妈妈们一共提醒了多少次。

inputFormat:
第一行是一个整数，代表食物的份数 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行一个字符串，第 $(i + 1)$ 行的字符串 $s_i$ 表示取走第 $i$ 份食物的孩子的名字。

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

hint:
#### 样例 1 解释

当取到第 $3$ 份食物时，stanko 已取走的食物（不包括当前这份）的份数是一份，而其他人也总共取走了一份，所以 stanko 的妈妈不会提醒他注意礼貌。

当取到第 $4$ 份食物时，stanko 已经取走两份食物，其他人总共取走了一份食物，因此妈妈会提醒他。

---

#### 数据规模与约定

对于全部的测试点，保证：

- $1 \leq n \leq 100$
- $1 \leq |s_i| \leq 20$，$s_i$ 中只含小写英文字母。$|s_i|$ 表示字符串 $s_i$ 的长度。

---

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #6](https://hsin.hr/coci/archive/2006_2007/contest6_tasks.pdf) *T1  PRASE***。


title: [JSOI2018] 潜入行动

description:
外星人又双叒叕要攻打地球了，外星母舰已经向地球航行！这一次，``JYY`` 已经联系好了黄金舰队，打算联合所有 ``JSOIer`` 抵御外星人的进攻。

在黄金舰队就位之前，``JYY`` 打算事先了解外星人的进攻计划。现在，携带了监听设备的特工已经秘密潜入了外星人的母舰，准备对外星人的通信实施监听。

外星人的母舰可以看成是一棵 $n$ 个节点、 $n-1$ 条边的**无向树**，树上的节点用 $1,2,\cdots,n$ 编号。``JYY`` 的特工已经装备了隐形模块，可以在外星人母舰中不受限制地活动，可以神不知鬼不觉地在节点上安装监听设备。

如果在节点 $u$ 上安装监听设备，则 ``JYY`` 能够监听与 $u$ **直接相邻**所有的节点的通信。换言之，如果在节点 $u$ 安装监听设备，则对于树中每一条边 $(u,v)$ ，节点 $v$ 都会被监听。特别注意**放置在节点 $u$ 的监听设备并不监听 $u$ 本身的通信**，这是 ``JYY`` 特别为了防止外星人察觉部署的战术。

``JYY`` 的特工一共携带了 $k$ 个监听设备，现在 ``JYY`` 想知道，有多少种不同的放置监听设备的方法，能够使得母舰上**所有节点**的通信都被监听？为了避免浪费，**每个节点至多只能安装一个监听设备，且监听设备必须被用完**。

inputFormat:
输入第一行包含两个整数 $n,k$ ，表示母舰节点的数量 $n$ 和监听设备的数量 $k$ 。
接下来 $n-1$ 行，每行两个整数 $u,v$ $(1\le u,v\le n)$，表示树中的一条边。

outputFormat: 输出一行，表示满足条件的方案数。因为答案可能很大，你只需要输出答案 $\text{mod 1,000,000,007}$ 的余数即可。

hint:
**样例 1 解释**

样例数据是一条链 $1-2-3-4-5$ 。首先，节点 $2$ 和 $4$ 必须放置监听设备，否则 $1,5$ 将无法被监听（放置的监听设备无法监听它所在的节点）。剩下一个设备必须放置在 $3$ 号节点以同时监听 $2,4$ 。因此在 $2,3,4$ 节点放置监听设备是唯一合法的方案。

**数据范围**

存在 $10\%$ 的数据，$1 \le n \le 20$ ；

存在另外 $10\%$ 的数据，$1 \le n \le 100$ ；

存在另外 $10\%$ 的数据，$1 \le k \le 10$ ；

存在另外 $10\%$ 的数据，输入的树保证是一条链；

对于所有数据，$1\le n\le 10^5$ ，$1\le k\le \min\{n,100\}$ 。


title: [JSOI2018] 防御网络

description:
虽然成功得到了外星人的进攻计划，但 ``JYY`` 意外地发现,外星母舰对地球的攻击竟然是随机的！必须尽快在地球上部署防御网络,抵御外星人母舰的攻击。
地球上的防御网络由节点和节点之间的能量连接组成,防御网络可以看成是一个 $n$ 个点、 $m$ 条边的简单无向图 $G(V,E)$ ,每个防御节点对应 $V$ 中的一个节点、每个能量连接对应 $E$ 中的一条边。此外,在防御网络修建时考虑到能量传输效率，防御网络 $G$ 中**每个节点至多只包含在一个简单环中**。

外星母舰的攻击是随机的，每次攻击开始后， ``JYY`` 都会本次攻击的情况选择一些防御节点 $S\subseteq V$ ，并且用能量连接将这些防御节点连通，从而启动一个防御子网络。换言之， ``JYY`` 会选择 $G$ 中边集的一个子集 $H(S)\subseteq E$ ,它满足:

1.    (防御子网络**连通**) 如果我们建立新图 $G'(V,H(S))$ ，即用 $H(S)$ 中的边连接 $G$ 中的节点，则对于任意选择的防御节点 $x,y\in S$ ，它们在 $G'$ 中都连通。

2.    (防御子网络**最小**) 在满足条件 1 (防御子网络连通)的前提，选取的边数最小，即 $\vert H(S)\vert$ 最小。

$H(S)$ 是点集 $S$ 在图 $G$ 生成的斯坦纳树 (Steiner Tree) ，而 $\vert H(S)\vert$ 则是启动防御子网络的最小代价。考虑到外星母舰随机攻击的方式， ``JYY`` 希望你计算启动防御子网络代价的**期望**:

$$\frac{1}{2^{\vert V\vert}}\sum_{S\subseteq V}\vert H(S)\vert$$

inputFormat:
输入第一行两个整数 $n,m$ ，分别表示图中的节点数和边数。

接下来 $m$ 行,每行两个整数 $u,v(1\le u,v\le n)$ ，表示图中的一条边。输入保证没有自环和重边，并且满足每个节点至多包含在一个简单环中。

outputFormat:
输出一行，表示启动防御子网络的期望。

假设期望写成最简分式 $P/Q$ 的形式, 则输出 $P⋅Q^{-1} \text{mod 1,000,000,007}$ 的余数,其中 $Q^{-1}$ 为唯一的满足 $Q⋅Q^{-1} ≡ \text{1 (mod 1,000,000,007)}$ 的整数。


title: [JSOI2018] 绝地反击

description:
由于你的出色表现，外星人的进攻已经被成功化解了。现在， ``JYY`` 召集了强大的黄金舰队,准备一击摧毁外星人的母舰。

黄金舰队共有 $n(n\ge 3)$ 艘飞船,这些飞船能将能量汇聚到同一点（外星人母舰所在位置），从而对外星母舰进行毁灭性的打击。 ``JYY`` 计划将所有飞船同时折跃到母舰附近，瞬间发动攻击结束战斗。

在黄金舰队折跃抵达后，由于各种不稳定因素，舰队中的各艘飞船并未进入最佳攻击位置，因此需要迅速对它们进行调整。现在，所有飞船已经同时完成了折跃，每个飞船都可以看做是平面上的一个点，第 $i(1\le i\le n)$ 艘飞船的坐标为 $(x_i,y_i)$ 。外星母舰位于坐标原点 $(0,0)$ 。

为了实现最高效的打击，所有飞船都必须移动到攻击轨道上。攻击轨道是圆心在原点 $(0,0)$ 、半径为 $R$ 的圆。因为发射产生的能量实在太大， ``JYY`` 希望发射时飞船相互之间的距离尽可能大。具体来说， ``JYY`` 希望黄金舰队所有 $n$ 艘飞船均匀地排列在攻击轨道上（所有飞船均为同一型号，因此按任意顺序排列均可），即相邻飞船在攻击轨道（圆弧）上的距离相等且恰好等于 $\frac{2\pi R}{n}$ 。换言之， ``JYY`` 希望调整所有飞船的位置，使得所有飞船都位于攻击轨道上，且它们恰好位于正 $n$ 边形的 $n$个顶点。

请你帮助 ``JYY`` 计算出打击开始的最短时间（即所有飞船移动到攻击轨道上并等距排列的最少时间）。飞船一单位时间可以在平面上移动一单位距离，且飞船的体积可以看成 $0$ 。因此在你设计的方案中，飞船在某个时刻 “相遇” 是允许的。此外，初始时飞船的坐标也允许重合。

inputFormat:
输入第一行两个整数 $n,R$ ，表示飞船的数量和攻击轨道的半径。

接下来 $n$ 行,每行两个整数 $(x_i,y_i)$ ，分别表示每一艘飞船的坐标。

outputFormat: 输出一行，表示所有飞船就位的最短时间（请保留足够的小数位数）。如果你的输出和参考答案差距不超过 $10^{-6}$ 则认为正确。

hint:
对于 $20\%$ 的数据，有 $n=3$ 。

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

对于 $100\%$ 的数据，有 $3 \le n\le 200,0 \le\vert x_i\vert,\vert y_i\vert,R\le 100$ 。


title: [COCI2017-2018#4] Rasvjeta

description:
It is Advent season. There are M street lights in a street N metres long (the meters of the
street are denoted with numbers from 1 to N). Each of the lights lights up the meter of the
street it’s located in and K meters to the left and to the right of that location. In other words, if
the light is located at meter X, it lights up all metres of the street from X - K to X + K,
inclusively. Of course, it is possible for a meter of the street to be lit up by multiple street
lights. All lights have distinct locations.

The problem is that there is a possibility that the lights don’t light up all N metres of the
street. It is your task to determine the minimal amount of additional lights needed to be put
up (at position from 1 to N) so that the entire street is lit up.

inputFormat:
The first line of input contains the number N (1 ≤ N ≤ 1000).

The second line of input contains the number M (1 ≤ M ≤ N).

The third line contains the number K (0 ≤ K ≤ N).

Each of the following M lines contains a number. The numbers are sorted in ascending order
and represent the positions of each of the M street lights.

The positions will be distinct and from the interval [1, N].

outputFormat: You must output the required number from the task.

hint:
**Clarification of the first test case:**

It’s not necessary to add lights to the street, since all N meters are already lit up.

**Clarification of the third test case:**

It is necessary to add one lamp, for example at location 13.


title: [COCI2017-2018#4] Izbori

description:
In a land with developed democracy far, far away, presidential elections for the football
association are taking place. This land consists of N counties, and each county has its own
football association. There are M presidential candidates labeled with 1, 2, … M. Each of the
football associations will select exactly one candidate to cast their vote for. The winner of the
election is the candidate with the most votes. If multiple candidates get the most amount of
votes, the winner is the one with the smallest label.

During the election campaign, candidates visited the counties and tried to gain their
sympathies. After having met all the candidates, each county’s football association
determined the order in which they would cast their vote for each candidate.

For example, let’s assume that there are four candidates in the election and that one
county’s order is 2, 1, 4, 3. This means that, unless they revoke their candidacy, the
candidate with label 2 will get the county’s vote. If candidate 2 revokes their candidacy, and
candidate 1 is still in the race, then they will get the vote, and so on.

Zdravko is a passionate football fan, and also a close friend of candidate with label K. He
wants to know which candidate will win if neither of the candidates revokes their candidacy.

He also wants to know what is the minimal number of candidates he must persuade to
revoke their candidacy in order for his friend, candidate K, to become the president of the
football association.

Zdravko is currently dealing with other problems, so he is hoping that you will answer these
questions.

inputFormat:
The first line of input contains the numbers N (1 ≤ N ≤ 100), M (1 ≤ M ≤ 15) and K (1 ≤ K ≤
M) from the task.

Each of the following N lines contains the orders given by the counties’ football associations,
i.e. a permutation of the first M natural numbers.

outputFormat: You must output the answers to the questions from the task, each in its own line.

translation:
有 $n$ 个县和 $m$ 个候选人，每个县都有一个候选人的排名。每个县会给所有没有弃权的候选人中，在它们那里排名最靠前的投一票。得票最多的候选人当选，特殊地，若多个人得票相同，编号更小的候选人当选。

求:

1. 若没有候选人弃权，哪个候选人当选。
2. 最少几个候选人弃权可以使得编号为 $k$ 的候选人当选。

每一问占当前测试点的 $50 \%$ 分数。

hint:
The output must consist of two non-empty lines, each containing a single integer. ~~The correct answer to each of the questions is worth 50% of points for that test case.(不会做spj没用)~~

**Clarification of the first test case:**

The land where the elections are being held consists of 3 counties, and there are 4 candidates for the
president of the association. If neither of the candidates revoke their candidacy, candidate 3 will win
the elections with two votes. Candidate 1 will only win if all the other candidates revoke their
candidacy.

**Clarification of the second test case:**

There is only one candidate, Zdravko’s friend, so they will surely win.


title: [COCI2017-2018#4] Automobil

description:
Mirko has found a matrix with N rows and M columns at the back seat of his car. The first
row of the matrix consists of numbers 1, 2, … M, the second row of numbers M+1, M+2, …
2⋅M and so on until the $N^{th}$
row which consists of numbers (N-1)⋅M + 1, (N-1)⋅M + 2, …
N⋅M, respectively.

For example, for N = 3 and M = 4:

| - | - | - | - |
| :----------: | :----------: | :----------: | :----------: |
| **1** | **2** | **3** | **4** |
| **5** | **6** | **7** | **8** |
| **9** | **10** | **11** | **12** |

Such matrix wasn’t interesting enough to him, so he chose a row or a column K times and
multiplied its values with a non-negative integer.

Naturally, now he wants to know the sum of all the values from the matrix. Since this sum
can be very large, Mirko will be satisfied with the value modulo $10^9$ + 7. Help Mirko answer
this question.

inputFormat:
The first line of input contains the numbers N (1 ≤ N ≤ 1 000 000), M (1 ≤ M ≤ 1 000
000) and K (1 ≤ K ≤ 1000) from the task.

 - Either the multiplication of the $X^{th}$
row with Y, in the form of "R X Y", where “R”
represents row multiplication, X is a positive integer (1 ≤ X ≤ N), and Y is a
non-negative integer (0 ≤ Y ≤ $10^{9}$
).

 - Or the multiplication of the $X^{th}$ column with Y, in the form of “S X Y”, where “S”
represents column multiplication, X is a positive integer (1 ≤ X ≤ M), and Y is a
non-negative integer (0 ≤ Y ≤ $10^{9}$
).

outputFormat: You must output the sum of the final values from the matrix modulo $10^{9}$ + 7

hint:
In test cases worth a total of 50 points, it will hold 1 ≤ N, M ≤ 1000.

**Clarification of the first test case:**
After multiplying the second row with 4, the fourth column with 1, the third row with 2, and again the
second row with 0, the final matrix looks like this:

| - | - | - | - |
| :----------: | :----------: | :----------: | :----------: |
| **1** | **2** | **3** | **4** |
| **0** | **0** | **0** | **0** |
| **18** | **20** | **22** | **24** |

The sum of the elements from the final matrix is 1 + 2 + 3 + 4 + 0 + 0 + 0 + 0 + 18 + 20 + 22 + 24 =
94.


title: [COCI2017-2018#4] Vođe

background: #滥用本题评测将被封号

description:
As we all very well know, goats and sheep have been fighting for years about the fields
they’re grazing. After many fierce fights, the goat leader and the sheep leader decided to
meet to try to find a peaceful solution to their problem. After many hours of discussion, they
agreed that they will play a game for each field and that the winner will get to graze that field.

The game is played such that a total of N animals (that can be goats or sheep) form a circle
(the exact order of goats and sheep is an agreement between their leaders). After animal i (1
≤ i ≤ N-1), the game is continued by animal i+1, and after animal N, the game is continued by
animal 1. The animal starting the game can say any positive integer from the interval [1, K],
but only if that number is not greater than M. If the animal that started the game said the
number j, then the next animal can say a number in interval [j+1, j+K], but only if that number
is not greater than M. In other words, each animal can say a number that is greater by
minimally 1, and maximally by K than the number said by the animal before, but only if the
new number is not greater than M. If an animal must say number M, its team (goats or
sheep) loses.

If both the goats and the sheep are playing optimally, for each i (1 ≤ i ≤ N), determine who
will win the field if the game is started by the $i^{th}$ animal.

inputFormat:
The first line of input contains N, M and K (1 ≤ N, M, K ≤ 5000), the numbers from the task.
The following line contains N numbers, 0 if the $i^{th}$  animal is a sheep, and 1 if it’s a goat.

outputFormat:
Output N space-separated numbers. For each animal i (1 ≤ i ≤ N) output 0 if the sheep will
win the field, and 1 if the goats will win, if the $i^{th}$   animal is starting the game.

translation:
给n个人每个人有个团队（0或1），每个人可以报一个数，第一个人的范围为[1,k]，上一个人报的数x下一个人为[x+1,x+1+k]，报数超过m的人输，1-n按顺序报数，n的下一个为1直到游戏结束。每个人都会选择最优策略，问以每个人为起始点玩这个游戏，那个团队会赢。

由 @Unknown_Error  提供翻译

hint:
In test cases worth a total of 60% of points, it will hold 1 ≤ N, M, K ≤ 500.

**Clarification of the first test case:**

When a sheep is playing first, it can play like this:

The sheep starts with number 2, after which the goat can say 3 or 4. In both cases, the sheep can say
5, after which the goat can say either 6 or 7. In both cases, the sheep can say 8, after which the goat
doesn’t have any other choice but 9 and thus losing the game and the field.


title: [COCI2017-2018#4] Krov

description:
You are given a histogram consisting of N columns of heights $X_1,X_2,X_N$, respectively. The histogram needs to be transformed into a roof using a series of operations. A roof is a
histogram that has the following properties:
- A single column is called the top of the roof. Let it be the column at position $i$.
- The height of the column at position $j\ (1 ≤ j ≤ N)$ is $ h_j = h_i- |i - j|$.
- All heights $h_j$ are positive integers.

An operation can be increasing or decreasing the heights of a column of the histogram by $1$.
It is your task to determine the minimal number of operations needed in order to transform
the given histogram into a roof.

inputFormat:
The first line of input contains the number $N (1 ≤ N ≤ 10^5$
), the number of columns in the
histogram.

The following line contains $N$ numbers $X_i\ (1 ≤ X_i ≤ 10^9)$, the initial column heights.

outputFormat: You must output the minimal number of operations from the task.

translation:
给定一个长度为 $N$ 的序列 $X$，定义一个屋顶序列为满足以下条件的序列 $H$：

- 序列里恰有一项被称作屋尖。记这一项的下标为 $i$。

- 确定了屋尖后，其他下标为 $j$ 的值 $H_j=H_i-|i-j|$。

- 所有的 $H_j$ 均为正整数。

每次操作，您可以指定序列 $X$ 中的任意一项，将它的值加一或者减一。

请求出使得原序列 $X$ 变成一个屋顶序列的最小的操作次数。

hint:
In test cases worth 60% of total points, it will hold N ≤ 5000.

**Clarification of the first test case:** By increasing the height of the second, third, and fourth column,
we created a roof where the fourth column is the top of the roof.

**Clarification of the second test case:** By decreasing the height of the third column three times, and
increasing the height of the fourth column, we transformed the histogram into a roof. The example is
illustrated below.

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


title: [COCI2017-2018#4] Ceste

description:
There’s a country with N cities and M bidirectional roads. Driving on road i takes $T_i$ minutes,
and costs $C_i$ kunas (Croatian currency).

To make the arrival to the holiday destination as pleasant as possible, you want to make it
as fast and as cheap as possible. More specifically, you are in city 1 and want to minimize
the product of total money spent and total time spent (overall, with all roads you drove on) in
getting to a city from city 1. For each city (except city 1), output the required minimal product
or -1 if city 1 and that city aren’t connected.

inputFormat:
The first line of input contains numbers N (1 ≤ N ≤ 2000), the number of cities, and M (1 ≤ M
≤ 2000), the number of roads.

Each of the following M lines contains four numbers,$A_i,B_i,T_i,C_i,(1≤A_i,B_i≤N,1≤T_i,C_i≤2000)$ that denote there is a road connecting cities $A_i$ and $B_i$
, that it takes $T_i$ minutes to drive
on it, and it costs $C_i$ kunas.

It is possible that multiple roads exist between two cities, but there will never be a road that
connects a city with itself.

outputFormat:
You must output N - 1 lines. In the $i^{th}$
line, output the required minimal product in order to get
to city (i + 1), or -1 if cities 1 and (i + 1) aren’t connected.

translation:
题目描述：

有一个无向图，给定 $n$ 个顶点和 $m$ 条边，第 $i$ 条边连接 $A_i$ 和 $B_i$ 两个点且有两个代价 $T_i$ 和 $C_i$。

从第 $i$ 个顶点经过一些边到第 $j$ 个顶点花费的代价为这些边的 $T$ 之和乘以 $C$ 之和。

问题是，对于每一个 $k(2 \le k \le n)$，求从1号点出发到 $k$ 号点花费的最小代价。

输入格式：

第一行两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含4个正整数 $A_i,B_i,T_i,C_i$，表示一条连接 $A_i,B_i$ 的路,代价为 $T_i,C_i$。

输出格式：

输出 $n-1$ 行，每行一个正整数，第 $i$ 行的正整数表示从城市1到城市 $i+1$ 的最小代价。

说明/提示：
对于 $40\%$ 的数据，满足 $1 \le n,m,T_i,C_i \le 100$。

对于 $100\%$ 的数据，满足 $1 \le n,m,T_i,C_i \le 2000,1 \le A_i,B_i \le n$。

样例2解释：

为了到达城市2，我们选择第一条道路，花费1T与7C，代价为7。

为了到达城市3，我们选择第二条道路，花费3T与2C，代价为6。

为了到达城市4，我们选择道路2，4，5，花费11T与4C，代价为44。

hint:
In test cases worth 40% of total points, it will hold $1 ≤ N, M, T_i, C_i ≤ 100$.

**Clarification of the second test case:**

In order to get to city 2, you need to drive on road 1, for that it takes 1 minute and 7 kunas, so the
required product is 7.

In order to get to city 3, you need to drive on road 2, for that it takes 3 minutes and 2 kunas, so the
required product is 6.

In order to get to city 4, you need to drive on roads 2, 4, 5, in that order, and for that it takes a total of
11 minutes and 4 kunas, so the required product is 44.


title: [JSOI2018] 战争

description:
九条可怜是一个热爱读书的女孩子。

在她最近正在读的一本小说中，描述了两个敌对部落之间的故事。第一个部落有 $n$ 个人，第二个部落有 $m$ 个人，每一个人的位置可以抽象成二维平面上坐标为 $(x_i,y_i)$ 的点。

在这本书中，人们有很强的领地意识，对于平面上的任何一个点，如果它被三个来自同一部落的人形成的三角形（可能退化成一条线段）包含（包括边界），那么这一个点就属于这一个部落的领地。如果存在一个点同时在两个阵营的领地中，那么这两个部落就会为了争夺这一个点而发生战争。

常年的征战让两个部落不堪重负，因此第二个部落的族长作出了一个英明的决定，他打算选择一个向量 $(dx,dy)$ ，让所有的族人都迁徙这个向量的距离，即所有第二阵营的人的坐标都变成 $(x_i+dx,y_i+dy)$ 。

现在他计划了 $q$ 个迁徙的备选方案，他想要你来帮忙对每一个迁徙方案，计算一下在完成了迁徙之后，两个部落之间还会不会因为争夺领地而发生战争。

inputFormat:
第一行输入三个整数 $n,m,q$，表示两个部落里的人数以及迁徙的备选方案数。

接下来 $n$ 行每行两个整数 $x_i,y_i$ 表示第一个部落里的人的坐标。

接下来 $m$ 行每行两个整数 $x_i,y_i$ 表示第二个部落里的人的坐标。

接下来 $q$ 行每行两个整数 $dx_i,dy_i$ 表示一个迁徙方案。

输入数据保证所有人的坐标两两不同。

outputFormat: 对于每个迁徙方案，输出一行一个整数，$0$ 表示不会发生冲突，$1$ 表示会发生冲突。

hint:
**样例 1 解释**

下图为第一组方案中两个部落的私人领地，点 $(0,0)$ 同时属于两个部落，因此会发生战争。

![0](https://i.loli.net/2018/05/05/5aed12638bab1.png)

下图为第二组方案中两个部落的私人领地，没有点同时属于两个部落，因此不会发生战争。

![1](https://i.loli.net/2018/05/05/5aed1293ce6ca.png)

下图为第三组方案中两个部落的私人领地，点 $(0,0)$ 同时属于两个部落，因此会发生战争。

![2](https://i.loli.net/2018/05/05/5aed12a4e3545.png)

**数据范围**

对于 $20\%$ 的数据， $n,m\le 5,q\le 500$。

对于 $40\%$ 的数据， $n,m\le 50,q\le 500$ 。

对于 $70\%$ 的数据， $n,m\le 10^4,q\le 500$ 。

对于 $100\%$ 的数据， $n,m\le 10^5,q\le 10^5$ 。

对于 $100\%$ 的数据，保证 $-10^8\le x_i,y_i,dx_i,dy_i\le 10^8;n,m\ge 3$ 。所有人的坐标两两不同且对于每一个阵营,所有人都不全共线。

**2024/08/20 增加 6 组 hack 数据，并公开在本题附件。**


title: [JSOI2018] 机器人

description:
九条可怜是一个懒懒的女孩子。因为懒得扫地，九条可怜买了一架扫地机器人。

九条可怜的家可以抽象成一个 $n \times m$ 的网格，坐标从 $(1,1)$ 到 $(n,m)$ 。每一天晚上，可怜都会在 $(1,1)$ 处启动扫地机器人。在启动了之后，扫地机器人会按照设定好的路径开始行动，当再一次回到 $(1,1)$ 后便会停止。

因为一些技术原因，扫地机器人只能向右（列编号加一）或者向下（行编号加一）走。为了让扫地机器人能够顺利的回到 $(1,1)$ ，可怜在家中安装了一些通道，使得：

1.    如果机器人目前在 $(i,m)$ ，那么向右走一步会到 $(i,1)$ 。
2.    如果机器人目前在 $(n,i)$ ，那么向下走一步回到 $(1,i)$ 。

可怜希望，在启动了机器人之后，在机器人回到 $(1,1)$ 前，它可以经过每一个格子**恰好**一次。这样既可以把家里给打扫干净，也不会花太多时间。经过简单的计算，可怜很快就得到了所有不同的方案（两个方案是不同的当且仅当他们经过格子的顺序不同）。于是可怜把所有的方案都输入到了扫地机器人里。

这一天可怜购置了一些新的家具，放好家具之后，家里便多了一些扫地机器人无法通过的障碍，于是在所有之前准备的方案中，扫地机器人都会撞上某一个障碍而停止工作。

对于一个方案 $S$，可怜定义 $f(S)$ 为在这个方案中，扫地机器人在撞上障碍之前，经过了多少个格子。现在可怜想要对所有不同的方案，计算 $f(S)$ 的和。

inputFormat:
**输入包含多组测试数据。**输入第一行一个整数 $T$ 表示测试数据的数量。

对于每组测试数据，第一行输入两个整数 $n,m$ ，表示可怜家的大小。

接下来 $n$ 行每行一个长度为 $m$ 的 01 字符串。第 $i$ 行第 $j$ 个字符是 $0$ 表示坐标 $(i,j)$ 的格子不是障碍，否则表示是障碍。

输入保证 $(1,1)$ 不是障碍且至少有一个障碍。

outputFormat: 对于每组测试数据，输出一行一个整数表示答案，答案可能很大，对 $998244353$ 取模后输出。

hint:
**样例 1 解释**

$n=2,m=4$ 时，一共有两种合法的方案：

![0](https://i.loli.net/2018/05/05/5aed14bde4548.png)

在第一种方案中,机器人在撞上障碍 $(1,3)$ 之前，一共经过了 $4$ 个格子。

在第二种方案中,机器人在撞上障碍 $(2,1)$ 之前，一共经过了 $1$ 个格子。

因此第二组测试数据的答案为 $1+4=5$ 。

**数据范围**

测试数据 1 $(20\%)$: $n,m\le 4$ 。

测试数据 2 $(30\%)$: $n,m\le 50$ ，且除了 $(1,1)$ 外所有格子都是障碍。

测试数据 3 $(50\%)$: $n,m\le 50$ 。

对于所有测试数据，$T\le 10;n,m\ge 1$ 。


title: [JSOI2018] 列队

description:
作为一名大学生，九条可怜在去年参加了她人生中的最后一次军训。

军训中的一个重要项目是练习列队，为了训练学生，教官给每一个学生分配了一个休息位置。每次训练开始前，所有学生都在各自的休息位置休息，但是当教官发出集合命令后，被点到的学生必须要到指定位置集合。

为了简化问题，我们把休息位置和集合位置抽象成一根数轴。一共有 $n$ 个学生，第 $i$ 个学生的休息位置是 $a_i$。每一次命令，教官会指定一个区间 $[l,r]$ 和集合点 $K$ ，所有编号在 $[l,r]$ 内的学生都必须赶到集合点列队。在列队时，每一个学生需要选择 $[K,K+r-l]$ 中的一个整数坐标站定且不能有任何两个学生选择的坐标相同。学生从坐标 $x$ 跑到坐标 $y$ 需要耗费体力 $\vert y-x \vert$ 。

在一天的训练中，教官一共发布了 $m$ 条命令 $(l,r,K)$ ，现在你需要计算对于每一条命令，在所有可能的列队方案中，消耗的体力值总和最小是多少。

以下是对题意的一些补充：

1.    任何两条命令是无关的，即在一条集合命令结束后，所有学生都会回到自己的休息位置，然后教官才会发出下一条命令。

2.    在集合的时候，可能有编号不在 $[l,r]$ 内的学生处在区间 $[K,K+r-l]$ 中，这时他会自己跑开，且跑动的距离不记在消耗的体力值总和中。

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

第二行 $n$ 个整数 $a_i$ 表示学生的休息位置。保证学生休息的位置两两不同。

接下来 $m$ 行每行三个整数 $l,r,K$ 表示一条命令。

outputFormat: 对于每一条命令输出一行一个整数表示最小的体力值总和。


title: 【模板】自适应辛普森法 1

description:
试计算积分

$\displaystyle{\int_L^R\frac{cx+d}{ax+b}\mathrm{d}x}$

结果保留至小数点后 $6$ 位。

数据保证计算过程中分母不为 $0$ 且积分能够收敛。

inputFormat: 一行，包含 $6$ 个实数 $a,b,c,d,L,R$。

outputFormat: 一行，积分值，保留至小数点后 $6$ 位。


title: [BJOI2014] 路径

description:
在一个 N 个节点的无向图（没有自环、重边）上，每个点都有一个符号，可能是数字，也可能是加号、减号、乘号、除号、小括号。你要在这个图上数一数，有多少种走恰好 K 个节点的方法，使得路过的符号串起来能够得到一个算数表达式。路径的起点和终点可以任意选择。

所谓算数表达式，就是由运算符连接起来的一系列数字。括号可以插入在表达式中以表明运算顺序。

注意，你要处理各种情况，比如数字不能有多余的前导 0，减号只有前面没有运算符或数字的时候才可以当成负号，括号可以任意添加（但不能有空括号），0可以做除数（我们只考虑文法而不考虑语意），加号不能当正号。

例如，下面的是合法的表达式：
```
-0/0
((0)+(((2*3+4)+(-5)+7))+(-(2*3)*6))
```
而下面的不是合法的表达式：
```
001+0
1+2(2)
3+-3
--1
+1
()
```

inputFormat:
第一行三个整数N,M,K，表示点的数量，边的数量和走的节点数。

第二行一个字符串，表示每个点的符号。

接下来M行，每行两个数，表示一条边连的两个点的编号。

1≤N≤20，0≤M≤N×(N-1)/2，0≤K≤30

outputFormat: 输出一行一个整数，表示走的方法数。这个数可能比较大，你只需要输出它模1000000007的余数即可。


title: [BJOI2014] 想法

description:
小强和阿米巴是好朋友。小强要出一套题目。

他的题目以涉及面广（偏）、考察深入（怪）、思维强度大（难）著称。他为了出题，一共攒了 $M$ 个本质不同的想法，每个想法形成了一个题目。不过，他觉得拿这些题目去考察选手会把比赛搞的太过变态，所以，想请阿米巴来帮忙调整一下他的题目。

阿米巴指出，为了让一场考试的题目的考察点尽量全面，有一个通用的做法叫做“组合”。如果把两个题目 $A$ 和 $B$ 组合在一起，那么组合而成的题目涉及到的想法的集合就是 $A$ 涉及到的想法的集合和 $B$ 涉及到的想法的集合的并。并且，题目是可以反复组合的。

例如，小强现在有三个想法 $1,2,3$，分别对应了题目 $P_1,P_2,P_3$：

- 小强把 $P_1$ 和 $P_2$ 组合得到 $P_4$。$P_4$ 涉及的想法的集合是 $\{1,2\}$。
- 小强把 $P_2$ 和 $P_3$ 组合得到 $P_5$。$P_5$ 涉及的想法的集合是 $\{2,3\}$。
- 小强把 $P_4$ 和 $P_5$ 组合得到 $P_6$。$P_6$ 涉及的想法的集合是 $\{1,2,3\}$。

现在，小强告诉你每个题目都是如何组合而来的。你要回答的就是，每个题目涉及的想法的集合有多大。

不过，这个问题是很难的。于是，你只需要能够以比较高的概率回答的比较准确即可。

inputFormat:
第一行两个整数 $N,M$，依次表示小强的题目数量和想法的数量。
接下来 $N-M$ 行，每行两个整数，依次表示小强组合出来的题目都是由哪两个题组合而成的。
$M$ 个想法对应的题目依次编号为 $1$ 到 $M$。之后，小强组合来的第一个题编号为 $M+1$，组合出来的第二个题编号为 $M+2$，依次类推。

outputFormat:
**本题使用 Special Judge。**

$N-M$ 行，每行一个整数表示小强组合出来的每个题都涉及了几个想法。

hint:
对于 $100\%$ 的数据，$1 \le M \le 10^5$，$1 \le N \le 10^6$。
如果其中你有 $95\%$ 以上的行的答案和正确答案的误差不超过 $25\%$，那么你就可以得到分数。
所谓误差不超过 $25\%$，即如果正确答案是 $X$，那么你的答案在 $[0.8X,1.25X]$ 这个闭区间内就算误差不超过 $25\%$。


title: [FJOI2014] 树的重心

description:
给定一个 $n$ 个点的树，每个点的编号从 $1 \sim n$ ，问这个树有多少不同的连通子树，和这个树有相同的重心。

其中 $n$ 个点的树指的是 $n$ 个点的最小连通图，显然 $n$ 个点的树有 $n-1$ 条边，去掉这 $n-1$ 条边中的任何一条，原图都不再联通，任意两个点之间由唯一一条路径相连。

对于一个树，树的重心定义为：删掉某点 $i$ 后，若剩余 $k$ 个连通分量，那么定义 $d(i)$ 为这些连通分量中点的个数的最大值，所谓重心，就是使得 $d(i)$ 最小的点 $i$。

基于以上定义，一个树的重心可能会有一个或者两个，题中所要求的联通子树，其重心编号和个数必须和原树的完全一样。

找出给定的树中有多少联通的子树和这个树有相同的重心。输出答案 $\bmod 10007$ 后的结果。

inputFormat:
第 $1$ 行中给出正整数 $Q$，表示该组数据中有多少组测试样例。

每组样例首先输入一个整数 $n$（$0 < n \le 200$），表示该组样例中输入的树包含 $n$ 个点，之后 $n-1$ 行，每行输入两整数数 $x,y$（$1 \le x,y \le n$），表示编号为 $x$ 的点和编号为 $y$ 的点之间存在一条边，所有点的编号从 $1 \sim n$。

outputFormat: 首先输出样例编号，之后输出满足条件的子树的个数，由于这个数字较大，你只需要输出这个数字 $\bmod\ 10007$ 后的结果，详见输出示例，请严格按照输出实例中的格式输出。


title: [FJOI2015] 世界树

description:
奥丁杀死的巨人伊米尔后，从伊米尔的尸体上生长出来一株巨大的梣树，它是整个宇宙的核心，被称为世界之树，这个巨木的枝干构成了整个世界，它被神秘的奥术力量所守护。

奥丁发现，世界树的每个节点至多有两棵子树，其蕴含的奥术力量是子树奥术力量的最大值 $+1$，如果一个节点没有子树，其奥术力量为 $1$，这些节点被称为“源”。

世界树在悠长的岁月里形成了奇妙的魔法平衡，具体来说，它的左子树与右子树的奥术力量的差的绝对值不会超过 $1$。若一个节点只有一棵子树（不妨设为左子树），则右子树的奥术力量视为 $0$。

现在奥丁想知道，在 $n$ 个节点的世界树中，最高和最低的两个“源”（即叶子节点）的深度差最大是多少？

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

以下 $T$ 行，每行一个整数 $n$ 表示世界树的节点数。

outputFormat: $T$ 行，每行一个整数表示任意两个“源”的奥术力量的差的最大值。


title: [FJOI2015] 带子串包含约束LCS问题

description:
带有子串包含约束的最长公共子序列问题可以具体表述如下。

给定2个长度分别为n和m的序列X和Y，以及一个子串包含约束集S。

S中共有k个字符串$S=\{S_1,S_2,…,S_k\}$，其中字符串$S_i$的长度为$l_i$，1≤i≤k。带有子串包含约束的最长公共子序列问题就是要找出X和Y的包含约束集S中所有字符串为其子串的最长公共子序列。

例如，如果给定的序列X和Y分别为X=actaagacct, Y=gacctacctc，子串包含约束集S={ata, tact}，则子序列actacct是X和Y的一个无约束的最长公共子序列，而包含约束集S中所有字符串为其子串的一个最长公共子序列是atact 。
在本题中请特别关注子串与子序列的区别。字符串$T=t_1…t_n$的子串是一个形如$T$’$=t_1+i…t_m+i$的字符串，其中，0≤i，m+i≤n。例如，T=abcdefg，则bcd是T 的一个子串，而bce是T的一个子序列，但不是T 的子串。

设计一个算法，找出给定序列X和Y带有子串包含约束S的最长公共子序列。

inputFormat:
第1行中给出正整数n,m,k，m＜300, n＜300, k＜6。n和m分别表示给定序列X和Y的长度。k表示子串包含约束集S中共有k个字符串。

第2行中有k个整数$l_i$，$0≤l_i≤300,1≤i≤k$，分别表示子串包含约束集S中k个字符串的长度。

第3行和第4行分别给出序列X和Y 。

接下来k行每行一个字符串$S_i$

outputFormat: 将计算出的X和Y带子串包含约束S的最长公共子序列的长度输出。

samples:
10 10 2
3 4
actaagacct
gacctacctc
ata
tact

hint: 字符串仅包含大小写字母.


title: [FJOI2015] 火星商店问题

description:
火星上的一条商业街里按照商店的编号 $1 \sim n$ ，依次排列着 $n$ 个商店。商店里出售的琳琅满目的商品中，每种商品都用一个非负整数 $\text{val}$ 来标价。每个商店每天都有可能进一些新商品，其标价可能与已有商品相同。

火星人在这条商业街购物时，通常会逛这条商业街某一段路上的所有商店，譬如说商店编号在区间 $[l,r]$ 中的商店，从中挑选一件自己最喜欢的商品。每个火星人对商品的喜好标准各不相同。

通常每个火星人都有一个自己的喜好密码 $x$。对每种标价为 $\text{val}$ 的商品，喜好密码为 $x$ 的火星人对这种商品的喜好程度与 $\text{val}$ 异或 $x$ 的值成正比。也就是说，$\text{val xor }x$ 的值越大，他就越喜欢该商品。

每个火星人的购物卡在所有商店中只能购买最近 $d$ 天内（含当天）进货的商品。另外，每个商店都有一种特殊商品不受进货日期限制，每位火星人在任何时刻都可以选择该特殊商品。每个商店中每种商品都能保证供应，不存在商品缺货的问题。

对于给定的按时间顺序排列的事件，计算每个购物的火星人的在本次购物活动中最喜欢的商品，即输出 $\text{val xor }x$ 的最大值。这里所说的按时间顺序排列的事件是指以下两种事件：

`0 s v`，表示编号为 $s$ 的商店在当日新进一种标价为 $v$ 的商品。

`1 l r x d`，表示一位火星人当日在编号在 $[l,r]$ 的商店购买 $d$ 天内的商品，该火星人的喜好密码为 $x$。

inputFormat:
第一行两个正整数 $n,m$，分别表示商店总数和事件总数。
第二行中有 $n$ 个整数，第 $i$ 个整数表示商店 $i$ 的特殊商品标价。

接下来的 $m$ 行，每行表示一个事件。每天的事件按照先事件 $0$，后事件 $1$ 的顺序排列。

outputFormat: 对于每个事件 $1$，输出一行一个整数表示答案。

hint:
【数据范围】
对于 $100\%$ 的数据，所有输入的整数在 $[0,10^5]$ 范围内。


title: [FJOI2015] 最小覆盖双圆问题

description:
给定平面上n个点$(x_1,y_1),...,(x_n,y_n)$，找出2个半径相同的圆$R_1$和$R_2$，覆盖给定的n个点，且半径最小。

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

设计一个算法，计算出所求最小覆盖双圆 $R_1$ 和 $R_2$ 的半径。

inputFormat:
输入有多个测试实例。每个实例的第1行中给出正整数n，n＜1000，表示平面上有n个点。

接下来的n行中每行给出2个实数(x, y)，-100000≤x≤100000，-100000≤y≤100000。

最后一行有一个0表示结束。

outputFormat: 对于每组数据，输出最小的符合题意的圆的半径，保留两位小数。


title: [FJOI2016] 神秘数

description:
一个可重复数字集合 $S$ 的神秘数定义为最小的不能被 $S$ 的子集的和表示的正整数。例如 $S=\{1,1,1,4,13\}$，有：$1 = 1$，$2 = 1+1$，$3 = 1+1+1$，$4 = 4$，$5 = 4+1$，$6 = 4+1+1$，$7 = 4+1+1+1$。

$8$ 无法表示为集合 $S$ 的子集的和，故集合 $S$ 的神秘数为 $8$。

现给定长度为 $n$ 的**正整数**序列 $a$，$m$ 次询问，每次询问包含两个参数 $l,r$，你需要求出由 $a_l,a_{l+1},\cdots,a_r$ 所组成的可重集合的神秘数。

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

第二行 $n$ 个正整数，从 $1$ 编号。

第三行一个整数 $m$，表示询问个数。

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


title: [CTSC2006] 歌唱王国

description:
在歌唱王国，所有人的名字都是一个非空的仅包含整数 $1\sim n$ 的字符串。

王国里生活着一大群咕噜兵，他们靠不停地歌唱首领——牛人酋长们的名字来获取力量。咕噜兵每一次歌唱过程是这样的：首先，他从整数生成器那儿获得一个数字，然后花一个时间单位将此数字唱出来，如果他发现某个牛人酋长的名字已经被歌唱出来（即此名字是歌唱序列的一个连续子串），那么这次歌唱过程就立即结束。

相关名词定义：

- 歌唱序列：如果某人歌唱了 $x$ 个数字，第 $i$ 次歌唱的数字为 $a_i$，那么歌唱序列 $=(a_1,a_2,\cdots,a_x)$。
- 整数生成器：歌唱王国的神物，它有一个按钮，如果你按一下按钮，将从 $1\sim n$ 数字中等概率的随机返回一个整数。
- 歌唱时间：在一次歌唱过程中花费的时间。

歌唱时间是随机的，无法预料；不过歌唱时间的期望值是固定的，此期望值即平均来说歌唱时间有多长，亦可称作平均歌唱时间。

王国里的人非常喜欢歌唱，他们希望歌唱的时间越长越好，所以他们决定罢免一些牛人酋长，使得平均歌唱时间变长。但是他们不能罢免掉所有的牛人酋长，否则他们每次歌唱都无法停止，无法获取力量；于是他们决定只保留一个牛人酋长而罢免其余的牛人酋长。

你的任务是：对于给定的 $n$、牛人酋长的个数 $t$ 以及每一个牛人酋长的名字，告诉王国里的人们，对于 $1\leq i\leq t$，如果保留第 $i$ 个牛人酋长，罢免掉其余的，那么平均歌唱时间将是多少。

提示：此数为一个非负整数！

输出要求：由于这个数字太大，所以你只需输出这个数的末 $4$ 位数字。如果不足 $4$ 位，则前面补 $0$（见样例）。

inputFormat:
第一行，两个整数 $n,t$。以下 $t$ 行描述 $t$ 个牛人酋长名字。

文件第 $i+1$（$1\leq i\leq t$）行格式如下：第一个数为 $m_i$ 表示第 $i$ 个牛人酋长的名字的长度，在一个空格之后，接下来有 $m_i$ 个数，用来描述这个牛人酋长的名字，相邻两个整数之间用一个空格分开。

outputFormat: 共 $t$ 行，第 $i$ 行为一个整数，表示若保留第 $i$ 个牛人酋长而罢免其余的，则平均歌唱时间最长的末四位数字是多少。


title: 取石子

description:
Alice 和 Bob 在玩游戏。

他们有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个，保证初始时 $a_i \leq a_{i + 1}(1 \leq i < n)$。现在他们轮流对这些石子进行操作，每次操作人可以选择满足 $a_i > a_{i - 1}$（$a_0$ 视为 $0$）的一堆石子，并从中取走一个。谁最后不能取了谁输。Alice 先手，他们都使用最优策略，请判断最后谁会取得胜利。

inputFormat:
第一行一个整数 $n(1 \leq n \leq 100)$，表示石子堆数。

接下来一行 $n$ 个数，第 $i$ 个数为 $a_i(1 \leq a_i \leq 10^9)$，意义如上所述。

outputFormat: "Alice" 或 "Bob"，表示谁会赢。


title: [SCOI2006] k进制集合的映射

description:
设$A(N,K)$是全体$N$位$K$进制整数$a$的集合（$a$的高位可以为$0$，例如，$0023$可看作一个$4$位$8$进制数，或一个$4$位$5$进制数，由题中指定的条件可以唯一确定），其中$2≤K≤6000$，$N=2$，$3$，$4$，即:$$A(N,K)={a|a=a_1a_2a_3\cdots a_N,0≤a_i≤K-1,i=1,\cdots,N}$$

设$D(N-1,K)$是$A(N-1,K)$的一个子集，它是由$A(N,K)$生成的一个$N-1$位$K$进制整数$d$的集合，**生成规则如下**:

对任何$d\in D(N-1,K)$，存在$a\in A(N,K)$，使$d=Image(a)$，其中，$d=d_1d_2\cdots d_{N-1},d_i=min(a_i,a_{i+1})$，即$d_i$取为$a_i,a_{i+1}$的最小值。

注1：我们称这个规则为$A(N,K)$ 到$A(N-1,K)$内的一个映射$d=Image(a)$，可以证明这个映射是多对一的，即：如果$d,e\in D(N-1,k)$且$d\not=e$，则对任何满足$d=Image(a),e=Image(c)$的$A(N,K)$中的元素$a,c$，均有$a\not=c$

注2：对某些$K,N$, $D(N-1,K)$是$A(N-1,K)$的一个真子集，例如$K=4,N=4$，则不存在$a\in A(4,4)$，使$Image(a)=(323)$

**任务**：从文本文件输入两个用空格隔开的整数 $N,K$，然后在指定的文本文件中输出下列表达式的值：

$$f(N,K)=\sum_{a\in A(N,K),Image(a)=d}(\prod_{i=1}^{N-1}(d_i+1))$$

上式表示对$A(N,K)$中的全部元素$a$，对其映像$d=Image(a)=d_1d_2\cdots d_{N-1}$的各位数字加$1$后的乘积求和。

其中$\prod^{N-1}_{i=1}(d_i+1)=(d_1+1)(d_2+1)\cdots(d_{N-1}+1)$

**例**：设$N=2,K=3$，则$A(N,K)={00,01,02,11,10,12,20,21,22}$，正确的输出结果应为$14$。

**提示**：应先建立相应的计算方法，直接利用$f(N,K)$的表达式计算会使多数测试超时。

inputFormat: 输入文件只有一行：用空格隔开的两个整数N  k。

outputFormat: 输出文件只有一个大整数，为计算结果。

hint:
**关于测试的说明**：

数字完全正确，给满分。当输出结果的位数超过$15$位时，如果仅最后两位不准确时给一半分。（每个需测试的计算结果不超过$10^{19}$）。


title: 【模板】裴蜀定理

description:
给定一个包含 $n$ 个元素的**整数**序列 $A$，记作 $A_1,A_2,A_3,...,A_n$。

求另一个包含 $n$ 个元素的待定**整数**序列 $X$，记 $S=\sum\limits_{i=1}^nA_i\times X_i$，使得 $S>0$ 且 $S$ 尽可能的小。

inputFormat:
第一行一个整数 $n$，表示序列元素个数。

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

outputFormat: 一行一个整数，表示 $S>0$ 的前提下 $S$ 的最小值。


title: 收集邮票

description:
有 $n$ 种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是 $n$ 种邮票中的哪一种是等概率的，概率均为 $1/n$。但是由于凡凡也很喜欢邮票，所以皮皮购买第 $k$ 次邮票需要支付 $k$ 元钱。

现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

inputFormat: 一行，一个数字 $N$（$N \le 10000$）。

outputFormat: 输出要付出多少钱，保留二位小数。


title: 最长异或路径

description:
给定一棵 $n$ 个点的带权树，结点下标从 $1$ 开始到 $n$。寻找树中找两个结点，求最长的异或路径。

异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

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

接下来 $n-1$ 行，给出 $u,v,w$ ，分别表示树上的 $u$ 点和 $v$ 点有连边，边的权值是 $w$。

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


title: [Poetize6] IncDec Sequence

description:
给定一个长度为 $n$ 的数列 ${a_1,a_2,\cdots,a_n}$，每次可以选择一个区间$[l,r]$，使这个区间内的数都加 $1$ 或者都减 $1$。

请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。

inputFormat:
第一行一个正整数 $n$
接下来 $n$ 行,每行一个整数,第 $i+1 $行的整数表示 $a_i$。

outputFormat:
第一行输出最少操作次数
第二行输出最终能得到多少种结果


title: 80人环游世界

description:
想必大家都看过成龙大哥的《80天环游世界》，里面的紧张刺激的打斗场面一定给你留下了深刻的印象。现在就有这么一个80人的团伙，也想来一次环游世界。

他们打算兵分多路，游遍每一个国家。

因为他们主要分布在东方，所以他们只朝西方进军。设从东方到西方的每一个国家的编号依次为$1 \cdots N$。假若第$i$个人的游历路线为$P_1,P_2,\cdots ,P_k(0≤k≤N)$，则$P_1<P_2<......<P_k$。

众所周知，中国相当美丽，这样在环游世界时就有很多人经过中国。我们用一个正整数 $V_i$ 来描述一个国家的吸引程度，$V_i$值越大表示该国家越有吸引力，同时也表示有且仅有$V_i$个人会经过那一个国家。

为了节省时间，他们打算通过坐飞机来完成环游世界的任务。同时为了省钱，他们希望总的机票费最小。

明天就要出发了，可是有些人临阵脱逃，最终只剩下了$M$个人去环游世界。他们想知道最少的总费用，你能告诉他们吗？

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

第二行有$N$个不大于$M$正整数，分别表示$V_1,V_2,\cdots, V_N$。

接下来有$N-1$行。第$i$行有$N-i$个整数，该行的第$j$个数表示从第$i$个国家到第$i+j$个国家的机票费（如果该值等于$-1$则表示这两个国家间没有通航）。

outputFormat: 在第一行输出最少的总费用。

hint:
在10%的数据中，$M=1$
在20%的数据中，$1≤M≤2$
在40%的数据中，$1≤M≤3$
在60%的数据中，$1≤M≤4$
在100%的数据中，$1≤N≤100$，$1≤M≤79$
保证所以输入数据中最少费用小于$10^6$。
保证至少存在一种可行方案。

纪中联赛模拟题
BY CQF


title: 小明的游戏

description: 小明最近喜欢玩一个游戏。给定一个 $n \times m$ 的棋盘，上面有两种格子 `#` 和 `@`。游戏的规则很简单：给定一个起始位置和一个目标位置，小明每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是 $0$，否则费用是 $1$。请编程计算从起始位置移动到目标位置的最小花费。

inputFormat:
输入文件有多组数据。
输入第一行包含两个整数 $n$，$m$，分别表示棋盘的行数和列数。
输入接下来的 $n$ 行，每一行有 $m$ 个格子（使用 `#` 或者 `@` 表示）。
输入接下来一行有四个整数 $x_1, y_1, x_2, y_2$，分别为起始位置和目标位置。
当输入 $n$，$m$ 均为 $0$ 时，表示输入结束。

outputFormat: 对于每组数据，输出从起始位置到目标位置的最小花费。每一组数据独占一行。

hint:
对于20%的数据满足：$1 \le n, m \le 10$。
对于40%的数据满足：$1 \le n, m \le 300$。
对于100%的数据满足：$1 \le n, m \le 500$。


title: [国家集训队] 最长双回文串

description:
顺序和逆序读起来完全一样的串叫做回文串。比如 `acbca` 是回文串，而 `abc` 不是：`abc` 的顺序为 `abc`，逆序为 `cba`，不相同。

输入长度为 $n$ 的串 $S$，求 $S$ 的最长双回文子串 $T$，即可将 $T$ 分为两部分 $X, Y$（$|X|,|Y|≥1$）且 $X$ 和 $Y$ 都是回文串。

inputFormat: 一行由小写英文字母组成的字符串 $S$。

outputFormat: 一行一个整数，表示最长双回文子串的长度。

hint:
**样例说明**

从第二个字符开始的字符串 `aacaabbacabb` 可分为 `aacaa` 与 `bbacabb` 两部分，且两者都是回文串。

**数据范围**

对于 $100\%$ 的数据，$2\leq |S|\leq 10^5$。

2018.12.10，2018.12.15：感谢 @Ycrpro 提供 hack 数据两组。


title: [Vani有约会] 雨天的尾巴 /【模板】线段树合并

background:
深绘里一直很讨厌雨天。

灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。

虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。

无奈的深绘里和村民们只好等待救济粮来维生。

不过救济粮的发放方式很特别。

description:
首先村落里的一共有 $n$ 座房屋，并形成一个树状结构。然后救济粮分 $m$ 次发放，每次选择两个房屋 $(x, y)$，然后对于 $x$ 到 $y$ 的路径上（含 $x$ 和 $y$）每座房子里发放一袋 $z$ 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

inputFormat:
输入的第一行是两个用空格隔开的正整数，分别代表房屋的个数 $n$ 和救济粮发放的次数 $m$。

第 $2$ 到 第 $n$ 行，每行有两个用空格隔开的整数 $a, b$，代表存在一条连接房屋 $a$ 和 $b$ 的边。

第 $(n + 1)$ 到第 $(n + m)$ 行，每行有三个用空格隔开的整数 $x, y, z$，代表一次救济粮的发放是从 $x$ 到 $y$ 路径上的每栋房子发放了一袋 $z$ 类型的救济粮。

outputFormat:
输出 $n$ 行，每行一个整数，第 $i$ 行的整数代表 $i$ 号房屋存放最多的救济粮的种类，如果有多种救济粮都是存放最多的，输出种类编号最小的一种。

如果某座房屋没有救济粮，则输出 $0$。

hint:
- 对于 $20\%$ 的数据，保证 $n, m \leq 100$。
- 对于 $50\%$ 的数据，保证 $n, m \leq 2 \times 10^3$。
- 对于 $100\%$ 测试数据，保证 $1 \leq n, m \leq 10^5$，$1 \leq a,b,x,y \leq n$，$1 \leq z \leq 10^5$。


title: [IOI2014] Wall 砖墙

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

description:
给定一个长度为 $n$且初始值全为 $0$的序列。你需要支持以下两种操作：

- Add $L, R, h$：将序列 $[L, R]$内所有值小于 $h$的元素都赋为 $h$，此时不改变高度大于 $h$的元素值
- Remove $L, R, h$：将序列 $[L, R]$内所有值大于 $h$的元素都赋为 $h$，此时不改变高度小于 $h$的元素值

你需要输出进行 $k$次上述操作之后的序列。

inputFormat:
输入的第一行包含两个正整数 $n, k$，分别表示序列中元素的个数以及操作数量，注意：**序列下标编号为 $0$ ~ $n-1$**。

接下来 $k$行每行包含 $4$个整数 $t, L, R, h$，若 $t = 1$则表明为 Add 操作，若 $t = 2$则表明为 Remove 操作。 $L, R, h$的含义见题目描述。

outputFormat: 输出包含 $n$行，每行包含 $1$个整数。第 $i$行的整数表示 $k$次操作之后序列中编号为 $i - 1$的元素的值。

hint:
- 子任务#1（8分）：满足 $1 \leq n \leq 10 000, 1 \leq k \leq 5 000$；
- 子任务#2（24分）：满足 $1 \leq n \leq 100 000, 1 \leq k \leq 500 000$，全部增加操作均在全部移除操作之前；
- 子任务#3（29分）：满足 $1 \leq n \leq 100 000, 1 \leq k \leq 500 000$；
- 子任务#4（39分）：满足 $1 \leq n \leq 2 000 000, 1 \leq k \leq 500 000$。

所有操作的高度 $h$满足 $0 \leq h \leq 100 000$。


title: [CQOI2013] 新数独

description:
下面是一个没有数字，只有大小关系（没错，那些尖角都是“大于符号”）！的数独：

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

除了大小关系外（注意相邻格子不能相同），还需要满足通常的数独规则：

 * 每个格子都是 $1\sim 9$ 的数字；
 * 每行都是 $1 \sim 9$ 的排列；
 * 每列都是 $1 \sim 9$ 的排列；
 * 每个 $3\times 3$ 的子矩阵（上图中用粗线隔开，一共有 $3\times 3$ 个这样的子矩阵）都是 $1\sim 9$ 的排列。

 如下图所示，是上述提到的数独的唯一一种填法：

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

 为了美观，每个 $3\times 3$ 子矩阵的**所有 $12$ 对**相邻格子的大小关系都将给出。

inputFormat: 一共 $15$ 行，包含一个新数独的实例。第 $1,3,5,6,8,10,11,13,15$ 行包含左右方向的符号（< 和 >），其余行包含上下方向的符号（^ 和 v）

outputFormat: 包含 $9$ 行，每行 $9$ 个 $1\sim 9$ 的数字，以空格隔开。输入保证唯一解。


title: [CQOI2013] 图的逆变换

description:
给一个 $n$ 结点 $m$ 条边的有向图 $D$，可以这样构造图 $E$：给 $D$ 的每条边 $(u,v)$，在 $E$ 中建立一个点 $uv$，然后对于 $D$ 中的两条边 $(u,v)$ 和 $(v,w)$，在 $E$ 中从 $uv$ 向 $vw$ 连一条有向边。$E$ 中不含有其他点和边。

输入 $E$，你的任务是判断是否存在相应的 $D$。

注意，$D$ 可以有重边和自环。

inputFormat:
第一行包含测试数据个数 $T$（$T\leq 10$）。

对于每组数据：

第一行一个整数 $m$（$0\le m\le300$），表示 $D$ 的边数（即 $E$ 的点数）。

第二行一个整数 $k$，表示 $E$ 的边数。

以下 $k$ 行每行两个整数 $x, y$，表示 $E$ 中有一条有向边 $(x,y)$。$E$ 中的点编号为 $0\sim m-1$。

outputFormat: 对于每组数据输出一行。如果存在，输出 `Yes`，否则输出 `No`。


title: [CQOI2013] 二进制A+B

description:
输入三个整数$a, b, c$，把它们写成无前导0的二进制整数。
比如$a=7, b=6, c=9$，写成二进制为$a=111, b=110, c=1001$。

接下来以位数最多的为基准，其他整数在前面添加前导0，使得$a, b, c$拥有相同的位数。比如在刚才的例子中，添加完前导0后为$a=0111, b=0110, c=1001$。

最后，把$a, b, c$的各位进行重排，得到a’, b’, c’，使得a’+b’=c’。比如在刚才的例子中，可以这样重排：a’=0111, b’=0011, c’=1010。

你的任务是让c’最小。如果无解，输出-1。

inputFormat: 输入仅一行，包含三个整数$a, b, c$。

outputFormat: 仅一行，为c’的最小值。


title: [CQOI2013] 棋盘游戏

description:
一个n*n（n>=2）棋盘上有黑白棋子各一枚。游戏者A和B轮流移动棋子，A先走。

 * A的移动规则：只能移动白棋子。可以往上下左右四个方向之一移动一格。

 * B的移动规则：只能移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。

和通常的“吃子”规则一样，当某游戏者把自己的棋子移动到对方棋子所在的格子时，他就赢了。

两个游戏者都很聪明，当可以获胜时会尽快获胜，只能输掉的时候会尽量拖延时间。你的任务是判断谁会赢，需要多少回合。

比如$n=2$，白棋子在$(1,1)$，黑棋子在$(2,2)$，那么虽然A有两种走法，第二个回合B总能取胜。

inputFormat:
仅一行，包含五个整数n, r1, c1, r2, c2，即棋盘大小和棋子位置。

白色棋子在$(r1,c1)$，黑色棋子在$(r2,c2)$ $(1<=r1,c1,r2,c2<=n)$。黑白棋子的位置保证不相同。

outputFormat:
仅一行，即游戏结果。

如果A获胜，输出WHITE x;

如果B获胜，输出BLACK x;

如果二者都没有必胜策略,输出DRAW.


title: [FJOI2018] 所罗门王的宝藏

description:
据古代传说记载，所罗门王既是智慧的代表，又是财富的象征。他建立了强大而富有的国家，聚集了大批的黄金象牙和钻石，并把这些价值连城的珍宝藏在一个神秘的地方，这就是世人瞩目的“所罗门王的宝藏”。多少个世纪以来，人们一直在寻找这批早已失落的古代文明宝藏，寻找盛产黄金和钻石的宝地。曾经追寻所罗门王宝藏的冒险者们都一去不回，至今没人解开这个谜题。亨利男爵在一次幸运的旅途中意外地得到了三百年前一位葡萄牙贵族留下的写在羊皮卷上的所罗门王的藏宝图和一本寻宝秘籍。在这张藏宝图的诱惑下，亨利男爵邀请约翰上校和勇敢的猎象人夸特曼开始了寻找埋葬在黑暗地底的所罗门王宝藏的艰险历程。他们横穿渺无边际的沙漠和浓荫蔽日的原始森林，越过汹涌澎湃的激流险滩，翻越高耸入云的峻岭雪山，饱尝沙漠的酷热和冰雪严寒，在藏宝图的指引下来到非洲一个原始的神秘国度库库安纳。这里有残酷的人殉制度，有一个拥有一千个妻室的独眼暴君特瓦拉，有像兀鹫一般丑恶诡诈老而不死的女巫加古尔，还有美丽聪慧的绝代佳人弗拉塔。在这片陌生而又险象环生的土地上三位寻宝英雄历尽艰辛，终于在绝代佳人弗拉塔的帮助下在海底深处找到了珍藏这批价值连城宝藏的巨大的藏宝洞。然而在女巫加古尔的精心策划下，一场灭顶之灾正在悄悄逼近。

藏宝洞的洞门十分坚固且洞门紧闭，如果不知道开启洞门的秘密是无法打开藏宝洞的洞门。在藏宝洞的洞门一侧有一个奇怪的矩形密码阵列。根据寻宝秘籍的记载，在密码阵列每行的左侧和每列的顶端都有一颗红宝石按钮。每个按钮都可以向左或向右转动。每向左转动一次按钮，相应的行或列中数字都增 $1$。每向右转动一次按钮，相应的行或列中数字都减 $1$。在矩形密码阵列的若干特定位置镶嵌着绿宝石。只有当所有绿宝石位置的数字与藏宝图记载的密码完全相同，紧闭的洞门就会自动缓缓打开。女巫加古尔早已得知开门的秘密。为了阻止寻宝者打开洞门，女巫加古尔为开门的密码阵列设置了全 $0$ 的初始状态。试图打开洞门的寻宝者如果不能迅速转动按钮使所有绿宝石位置的数字与藏宝图记载的密码完全相同，就会自动启动藏宝洞玄妙的暗器机关，使寻宝者遭到灭顶攻击而死于非命。

您能帮助三位寻宝英雄顺利打开藏宝洞的洞门吗？

编程任务：对于给定的密码阵列，找到获得正确密码的红宝石按钮的转动序列。

inputFormat: 输入的第一行中有一个正整数 $T (T \le 5)$ 表示有 $T$ 组数据。每组数据的第一行有 $3$ 个正整数 $n,m$ 和 $k$，表示洞门密码阵列共有 $n$ 行和 $m$ 列，$0<n,m,k \le 1000$。各行从上到下依次编号为 $1,2,\ldots,n$；各列从左到右依次编号为 $1,2,\ldots,m$ 。接下来的 $k$ 行中每行有三个整数 $x,y,c$，分别表示第 $k$ 个绿宝石在密码阵列中的位置和密码，$x$ 为行号 $y$ 为列号，$c$ 为该位置处的密码。

outputFormat: 对于每组数据，用一行输出 ``Yes`` 或者 ``No``。输出 ``Yes`` 表示存在获得正确密码的红宝石按钮的转动序列。输出 ``No`` 则表示无法找到获得正确密码的红宝石按钮的转动序列。


title: [FJOI2018] 领导集团问题

description:
一个公司的组织领导架构可以用一棵领导树来表示。公司的每个成员对应于树中一个结点 $v_i$，且每个成员都有响应的级别 $w_i$。越高层的领导，其级别值 $w_i$ 越小。树中任何两个结点之间有边相连，则表示与结点相应的两个成员属于同一部门。领导集团问题就是根据公司的领导树确定公司的最大部门。换句话说，也就是在领导树中寻找最大的部门结点子集，使得的结点 $v_i$ 和 $v_j$，如果 $v_i$ 是 $v_j$ 的子孙结点，则 $w_i \ge w_j$。

编程任务：对于任意对于给定的领导树，计算出领导树中最大的部门结点子集。

inputFormat:
第一行有一个正整数 $n$，表示领导树的结点数。

接下来的一行中有 $n$ 个整数。第 $i$ 个数表示 $w_i$。

再接下来的 $n-1$ 行中，第 $i$ 行有一个整数 $v_i$ 表示 $v_i$ 是 $i+1$ 的双亲结点。

outputFormat: 输出找到的最大的部门的成员数。


title: [FJOI2018] 邮递员问题

description:
$\text{2010}$ 年以来，网购市场发展迅速，快递公司成为促成交易成功的关键环节。小郭是一名顺丰快递员，他的工资主要包括底薪、送货提成、收件提成、其他福利补贴等。小郭每完成一件客户的快递单，一般能拿到运费 $10\%$ 的提成。因此小郭完成的快递单越多越快，他的收入就越高。小郭负责城市中 $2$ 个平行街道的所有快递业务。在这 $2$ 个平行街道上有 $2$ 处快递工作站。小郭每次投递的行程都是从一个工作站出发，完成所有快递单的投递后，回到另一个工作站。为了高效地完成投递任务，小郭希望用最短的行程来完成所有快递单的投递任务。也就是说，对于给定的 $2$ 个平行街道的街距和 $2$ 个工作站位置，以及所有投递点的位置，小郭要计算从一个工作站出发，完成所有快递单的投递后，回到另一个工作站的最短行程。街距是指 $2$ 个平行街道的之间的垂直距离。如果设平面坐标系的 $x$ 轴与街道平行，且 $2$ 个平行街道上的最左端位置的 $x$ 坐标均为 $0$，则 $2$ 个平行街道上的任何位置可以用从街道最左端到该位置的直线距离，即该位置的 $x$ 坐标值来表示。

例如，设 $2$ 个平行街道 A 和 B 的街距是 $2$。$2$ 个工作站 $S_1$ 和 $S_2$ 的位置分别位于街道 A 的 $x=1$ 和街道 B 的 $x=3$ 处。另外有 $2$ 个投递点 $T_1$ 和 $T_2$ 的位置分别位于街道 A 的 $x=3$ 和街道 B 的 $x=1$ 处，如图所示。小郭的任务就是要从工作站 $S_1$ 出发，完成在 $T_1$ 和 $T_2$ 处的快递单投递后，回到另一个工作站 $S_2$。

编程任务：对于给定的 $2$ 个平行街道的街距和 $2$ 个工作站位置，以及所有投递点的位置，计算从一个工作站出发，完成所有快递单的投递后，回到另一个工作站的最短行程。

inputFormat:
第 $1$ 行有 $2$ 个正整数 $n,m$，$1 \le n,m \le 10000$，分别表示 $2$ 个平行街道 A 和 B 上的位置数（包括投递点的位置和工作站的位置）。位置编号为 A：$1,2,\ldots,n$；B：$1,2,\ldots,m$。

第 $2$ 行有 $4$ 个正整数 $a,b,c,d$，表示 $2$ 个工作站位置分别为 $(a,b)$ 和 $(c,d)$。$a=0$ 或 $c=0$ 表示相应的工作站在街道 $A$，$a=1$ 或 $c=1$ 表示相应的工作站在街道 $B$。$b$ 和 $d$ 分别表示工作站在相应的街道的位置号。例如，若 $(a,b)=(0,3)$ 表示第 $1$ 个工作站位于街道 $A$ 上，其位置位于给出的街道 $A$ 的 $n$ 个位置的第 $3$ 个位置。

第 $3$ 行有 $1$ 个实数 $h$，表示 $2$ 个平行街道的街距 $(1 \le h \le 10)$。

第 $4$ 行有 $n$ 个实数，表示街道 $A$ 上 $n$ 个位置的 $x$ 坐标 $(1 \le x < 20000)$。

第 $5$ 行有 $m$ 个实数，表示街道 $B$ 上 $m$ 个位置的 $x$ 坐标 $(1 \le x < 20000)$。

outputFormat: 输出计算出的最短行程，保留 $2$ 位小数。


title: [TJOI2018] 数学计算

description:
小豆现在有一个数 $x$，初始值为 $1$。小豆有 $Q$ 次操作，操作有两种类型：

`1 m`：将 $x$ 变为 $x \times m$，并输出 $x \bmod M$

`2 pos`：将 $x$ 变为 $x$ 除以第 $pos$ 次操作所乘的数（保证第 $pos$ 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），并输出 $x \bmod M$。

inputFormat:
一共有  $t$ 组输入。

对于每一组输入，第一行是两个数字 $Q,M$。

接下来 $Q$ 行，每一行为操作类型 $op$，操作编号或所乘的数字 $m$（保证所有的输入都是合法的）。

outputFormat: 对于每一个操作，输出一行，包含操作执行后的 $x \bmod M$ 的值。


title: [TJOI2018] 智力竞赛

description:
小豆报名参加智力竞赛，他带上了 $n$ 个好朋友作为亲友团一块来参加比赛。比赛规则如下：

一共有 $m$ 道题目，每个人都有 $1$ 次答题机会，每次答题为选择一道题目回答，在回答正确后，可以继续回答这个题目的后续题目，直到答错题目或者没有后续题目。

每个问题都会有一个价值，比赛最后参赛选手获得的奖励价值等价于该选手和他的亲友团没有回答的问题中的最低价值。

我们现在知道小豆和他的亲友团实力非常强，能够做出这次竞赛中的所有题目。

小豆想知道在知道题目和后续题目的条件下，他最大能获得的价值是多少？

inputFormat:
第一行有两个整数 $n,m$。（$n\leq50,m\leq500$）

接下来 $m$ 行，第 $i+1$ 行表示编号为 $i$ 的题目的题目信息，格式形如 $v_i,k_i,a_{i,1},a_{i,2},...,a_{i,k_i}$，其中 $v_i$ 表示该题目的价值，$k_i$ 表示这个题目的后续题目个数，$a_{i,1},a_{i,2},...,a_{i,k_i}$ 表示 $k_i$ 个后续题目的编号。

outputFormat: 如果全部题目都能答对，则输出 `AK`，否则输出小豆可以获得的最高奖励价值。


title: [TJOI2018] 游园会

description: 小豆参加了 NOI 的游园会，会场上每完成一个项目就会获得一个奖章，奖章只会是 $\texttt{N}$、$\texttt{O}$、$\texttt{I}$ 的字样。在会场上他收集到了 $K$ 个奖章组成的串。兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。现在已知兑奖串长度为 $N$，并且在兑奖串上不会出现连续三个奖章为 $\texttt{NOI}$，即奖章中不会出现子串 $\texttt{NOI}$。现在小豆想知道各个奖励等级会对应多少个不同的合法兑奖串。

inputFormat:
第一行两个数，$N, K$ 分别代表兑奖串的长度，小豆收集的奖章串的长度（$N\leq1000,K\leq15$）。

第二行一共 $K$ 个字符，表示小豆得到的奖章串。

outputFormat: 一共 $K+1$ 行，第行表示小豆最后奖励等级为 $i-1$ 的不同的合法兑奖串的个数，可能这个数会很大，结果对 $10^9+7$ 取模。

hint:
### 样例解释

最长公共子序列长度为 $0$ 的串有：$\texttt{III}$;

最长公共子序列长度为 $2$ 的串有：$\texttt{NON}$、$\texttt{NNO}$、$\texttt{NOO}$、$\texttt{ONO}$、$\texttt{INO}$、$\texttt{NIO}$；

除去 $\texttt{NOI}$，余下的 $19 = 26-6-1$ 种为最长公共子序列长度为 $1$。

### 数据范围

- 对于 $10\%$ 的数据，$N\leq10,K\leq10$；
- 对于 $30\%$ 的数据，$N\leq100,K\leq4$；
- 对于 $100\%$ 的数据，$N\leq1000,K\leq15$。


title: [TJOI2018] 碱基序列

description:
小豆参加了生物实验室。在实验室里，他主要研究蛋白质。他现在研究的蛋白质是由 $k$ 个氨基酸按一定顺序构成的。每一个氨基酸都可能有 $a$ 种碱基序列 $s_{i,j}$ 构成。

现在小豆有一个碱基串 $s$，小豆想知道在这个碱基上都多少种不同的组合方式可能得到这个蛋白质。即求由 $k$ 段字符串有序合并成的字符串 $s_1$，有多少种不同方式能够匹配字符串 $s$，其中 $k$ 段字符串的选法不同，或者与 $s$ 匹配上的位置不同认为是不同的方式。

inputFormat:
第一行一个数，表示这个蛋白质由 $k$ 个氨基酸组成。

第二行一个字符串 $s$，表示小豆现在有的碱基串。

第三行开始接下来 $k$ 行表示第 $i$ 个氨基酸可能的碱基序列，对于第 $i$ 个氨基酸，$a_i$ 表示这个氨基酸可能的碱基序列种数，接下来 $a_i$ 个字符串表示这 $a_i$ 种可能的碱基序列，用空格隔开。

outputFormat:
输出一个数目标是不同的方案数（不同的方案数是指不同的子碱基串或者相同的碱基串不同的氨基酸排列方式）。

答案对 $10^9+7$ 取模。

hint:
### 样例 1 解释

- 第一个选 $\tt A$ 第二个选 $\tt C$，得到 $\tt AC$ 能够与 $\tt ABC$ 产生 $0$ 种匹配方式；
- 第一个选 $\tt A$ 第二个选 $\tt BC$，得到 $\tt ABC$ 能够与 $\tt ABC$ 产生 $1$ 种匹配方式；
- 第一个选 $\tt AB$ 第二个选 $\tt C$，得到 $\tt ABC$ 能够与 $\tt ABC$ 产生 $1$ 种匹配方式；
- 第一个选 $\tt AB$ 第二个选 $\tt BC$，得到 $\tt ABBC$ 能够与 $\tt ABC$ 产生 $0$ 种匹配方式。

所以一共 $2$ 种。

### 样例 2 解释

- 第一个选 $\tt A$ 第二个选 $\tt A$，得到 $\tt AA$ 能够与 $\tt AAA$ 产生 $2$ 种匹配方式；
- 第一个选 $\tt A$ 第二个选 $\tt AA$，得到 $\tt AAA$ 能够与 $\tt AAA$ 产生 $1$ 种匹配方式；
- 第一个选 $\tt AA$ 第二个选 $\tt A$，得到 $\tt AAA$ 能够与 $\tt AAA$ 产生 $1$ 种匹配方式；
- 第一个选 $\tt AA$ 第二个选 $\tt AA$,得到 $\tt AAAA$ 能够与 $\tt AAA$ 产生 $0$ 种匹配方式。

所以一共 $4$ 种。

### 数据范围及约定

- 对于 $30\%$ 的数据，$1\leq k\leq 25$，$1\le |s|\leq 10000$，$1\le a_i\leq 3$。
- 对于 $100\%$ 的数据，$1\leq k\leq100$，$1\le |s|\leq 10000$，$1\le a_i \leq10$。碱基序列的长度均不超过 $15$。字符集为大写字母。


title: [TJOI2018] 异或

description:
现在有一颗以 $1$ 为根节点的由 $n$ 个节点组成的树，节点从 $1$ 至 $n$ 编号。树上每个节点上都有一个权值 $v_i$。现在有 $q$ 次操作，操作如下：

- $1~x~z$：查询节点 $x$ 的子树中的节点权值与 $z$ 异或结果的最大值。
- $2~x~y~z$：查询节点 $x$ 到节点 $y$ 的简单路径上的节点的权值与 $z$ 异或结果最大值。

inputFormat:
输入的第一行是两个整数，分别代表结点个数 $n$ 和询问个数 $q$。

第二行有 $n$ 个整数，第 $i$ 个整数表示点 $i$ 的的权值 $v_i$。

接下来 $n-1$ 行，每行有两个整数 $u, v$，表示存在一条连结 $u$ 和 $v$ 的边。

接下来 $q$ 行，每行首先有一个整数 $op$，代表操作类型。

- 若 $op = 1$，则一个空格后有两个整数 $x, z$，代表查询节点 $x$ 的子树中的节点权值与 $z$ 异或结果的最大值。
- 若 $op = 2$，则一个空格后有三个整数 $x, y, z$，代表查询节点 $x$ 到节点 $y$ 的简单路径上的节点的权值与 $z$ 异或结果最大值。

outputFormat: 对于每一个查询，输出一行一个整数代表答案。

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

- 对于 $10\%$ 的数据，保证 $n, q \leq 10^2$；
- 对于 $20\%$ 的数据，保证 $n, q \leq 10^3$；
- 对于 $40\%$ 的数据，保证 $n, q \leq 10^4$；
- 对于 $100\%$ 的数据，保证 $2\leq n, q \leq10^5$，$1 \leq u, v, x, y \leq n$，$1 \leq op \leq 2$，$1 \leq v_i, z \lt 2^{30}$。


title: [TJOI2018] 教科书般的亵渎

description:
小豆喜欢玩游戏，现在他在玩一个游戏遇到这样的场面，每个怪的血量为 $a_i$，且每个怪物血量均不相同，小豆手里有无限张“亵渎”。亵渎的效果是对所有的怪造成 $1$ 点伤害，如果有怪死亡，则再次施放该法术。我们认为血量为 $0$ 怪物死亡。

小豆使用一张“亵渎”会获得一定的分数，分数计算如下，在使用一张“亵渎”之后，每一个被亵渎造成伤害的怪会产生 $x^k$，其中 $x$ 是造成伤害前怪的血量为 $x$ 和需要杀死所有怪物所需的“亵渎”的张数 $k$。

inputFormat:
第一行输入一个 $T$（$T\leq10$），表示有多少组测试数据。

每组测试数据第一行为 $n$，$m$，表示有当前怪物最高的血量 $n$，和 $m$ 种没有出现的血量。

接下来 $m$ 行，每行 $1$ 个数 $a_i$，表示场上没有血量为 $a_i$ 的怪物。

outputFormat: 一共 $T$ 行，每行一个数，第 $i$ 行表示第 $i$ 组测试数据中小豆的最后可以获得的分数，因为这个分数会很大需要模 $10^9+7$。


title: [FJOI2016] 所有公共子序列问题

description:
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 $X=x_1x_2\ldots x_m$，则另一序列 $Z=z_1z_2\ldots z_k$ 是 $X$ 的子序列是指存在一个严格递增下标序列 $i_1,i_2, \ldots ,i_k$ 使得对于所有 $j=1,2,…,k$ 有 $z_j=x_{i_j}$。

例如，序列 $Z=$``GACT`` 是序列 $X=$``GCTACT`` 的子序列，相应的递增下标序列为 $1,4,5,6$。给定两个序列 $X$ 和 $Y$，当另一序列 $Z$ 既是 $X$ 的子序列又是 $Y$ 的子序列时，称 $Z$ 是序列 $X$ 和 $Y$ 的公共子序列。例如，若 $X=$``GCTACT``， $Y=$``GATCCT``，序列 $T$ 是 $X$ 和 $Y$ 的一个公共子序列，序列 ``GACT`` 也是 $X$ 和 $Y$ 的一个公共子序列。注意对于任何给定的序列 $X$ 和 $Y$，空序列总是它们的一个公共子序列。

所有公共子序列问题是要求对于给定的 $2$ 个序列 $X=x_1x_2\ldots x_m$ 和 $Y=y_1y_2\ldots y_m$，找出 $X$ 和 $Y$ 的所有不同的公共子序列。

inputFormat:
文件的第一行有两个正整数 $m$ 和 $n$，分别表示 $2$ 个输入序列 $X$ 和 $Y$ 的长度。

接下来的两行分别给出输入序列 $X=x_1x_2\cdots x_m$ 和 $Y=y_1y_2\cdots y_m$，其中序列中每个元素均为二十六个英文大小写字母。

文件的最后一行给出一个非负整数 $k$。

$k$ 的值为 $1$ 时，表示计算结果要输出 $X$ 和 $Y$ 的所有不同的公共子序列，以及 $X$ 和 $Y$ 有多少个不同的公共子序列。

$k$ 的值为 $0$ 时，表示计算结果只要输出 $X$ 和 $Y$ 有多少个不同的公共子序列。

outputFormat: 将计算出的 $X$ 和 $Y$ 的所有不同的公共子序列，或 $X$ 和 $Y$ 有多少个不同的公共子序列输出到文件中。当 $k=1$ 时，先输出 $X$ 和 $Y$ 的所有不同的公共子序列，每行输出一个公共子序列，按字典序从小到大输出。最后输出不同的公共子序列的个数。当 $k=0$ 时，只要输出不同的公共子序列的个数。

samples:
A
AC
ACT
AT
C
CC
CCT
CT
G
GA
GAC
GACT
GAT
GC
GCC
GCCT
GCT
GT
GTC
GTCT
GTT
T
TC
TCT
TT
26


title: [FJOI2016] 建筑师

description:
小 Z 是一个很有名的建筑师，有一天他接到了一个很奇怪的任务：在数轴上建 $n$ 个建筑，每个建筑的高度是 $1$ 到 $n$ 之间的一个整数。

小 Z 有很严重的强迫症，他不喜欢有两个建筑的高度相同。另外小 Z 觉得如果从最左边（所有建筑都在右边）看能看到 $A$ 个建筑，从最右边（所有建筑都在左边）看能看到 $B$ 个建筑，这样的建筑群有着独特的美感。现在，小 Z 想知道满足上述所有条件的建筑方案有多少种？

如果建筑 $i$ 的左(右)边没有任何建造比它高，则建筑 $i$ 可以从左(右)边看到。两种方案不同，当且仅当存在某个建筑在两种方案下的高度不同。

inputFormat:
第一行一个整数 $T$，代表 $T$ 组数据。
接下来 $T$ 行，每行三个整数 $n,A,B$。

outputFormat: 对于每组数据输出一行答案 $\text{mod } 10^9+7$。


title: 序列 sequence

background: 原题 CF13C 数据加强版

description: 给定一个序列，每次操作可以把某个数 $+1$ 或 $-1$。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。

inputFormat:
第一行，输入一个整数 $n$（$n \leq 5 \times 10^5$），表示有 $n$ 个数字。
第二行输入 $n$ 个整数，整数的绝对值不超过 $10^9$。

outputFormat: 输出一个数，表示最少的操作次数。


title: [HAOI2009] 求回文串

description: 所谓回文串，就是对于给定的字符串，正着读和反着读都一样，比如 ABCBA 就是一个回文串，ABCAB 则不是。我们的目标是对于任意输入的字符串，不断将第 $i$ 个字符和第 $i+1$ 个字符交换，使得该串最终变为回文串。求最少交换次数。

inputFormat: 一个由大写字母字母组成的字符串。

outputFormat: 若能经过有限次操作能将原串变为回文串，则输出最少操作次数；否则输出 $-1$。

hint:
### 样例说明

1. 交换 $\tt L$ 和 $\tt Z$ 变成 $\tt SHLZLSHZS$；
2. 交换 $\tt L$ 和 $\tt Z$ 变成 $\tt SHZLLSHZS$；
3. 交换 $\tt L$ 和 $\tt S$ 变成 $\tt SHZLSLHZS$；
4. 交换 $\tt H$ 和 $\tt Z$ 变成 $\tt SHZLSLZHS$。

### 数据范围

- $40\%$ 的数据，长度 $\leq50000$；
- $100\%$ 的数据，长度 $\leq10^6$。


title: [HEOI2012] Akai 的数学作业

background:
这里是广袤无垠的宇宙

这里是一泻千里的银河

这里是独一无二的太阳系

这里是蔚蓝色的地球

这里，就是这里，是富饶的中国大陆！

这里是神奇的河北大地

这里是美丽的唐山

这里是神话般的唐山一中

这里是 Akai 曾经的教室

description:
黑板上还留有当年 Akai 做过的数学作业，其实也并不是什么很困难的题目:

“

给出一个一元 $n$ 次方程：

$$a_0 + a_1x + a_2x^2 +…+ a^nx^n= 0$$

求此方程的所有有理数解。

”

Akai 至今还深刻记得当年熬夜奋战求解的时光

他甚至还能记得浪费了多少草稿纸

但是却怎么也想不起来最后的答案是多少了

你能帮助他么？

inputFormat: 第一行一个整数 $n$。第二行 $n+1$ 个整数，分别代表 $a_0$ 到$a_n$

outputFormat:
第一行输出一个整数 $t$，表示有理数解的个数

接下来 $t$ 行，每行表示一个解

解以分数的形式输出，要求分子和分母互质，且分母必须是正整数

特殊的，如果这个解是一个整数，那么直接把这个数输出

等价的解只需要输出一次

所有解按照从小到大的顺序输出

hint:
对于 30%的数据，$n\leq10$

对于 100%的数据，$n\leq100$，$|a_i| <= 2\times10^7$，$a_n\not= 0$

HEOI 2012 Day1 Task1


title: [HEOI2012] 赵州桥

background:
fyg 背着他的电脑来到河北省来，就是为了见一眼古老的赵州桥。

终于，他来到了赵州桥，放下了电脑，正准备休息。一阵风吹来，从中闪现出一人影。 fyg 只觉天昏地暗，待得再次睁开眼时，发觉自己已经到了一神奇的国度，置身于一巨大的圆盘之上。放眼看去，四周都是奇形怪状的桥，不远处有一老头盘膝而坐。

description:
fyg 还沉浸在惊奇之中，老头（难道就是传说中走过赵州桥的张老头！！）便开口了：凡人，你现在在我的世界中，想要出去就要回答我的问题。fyg 只得点头，老头继续道：你现在要去闯关，我给你$m$种颜色，总共有$n$关（神仙也懂数学，表示压力巨大。。==）。每一关中有一座桥，在第$i$关中，桥长度有$i$个单位，每个单位长度上有$2$个格子（也就是说这座桥有$2i$个格子），现在你要计算出：在这座桥上涂色使得桥上相邻格子的颜色不一样总方案数，然后再乘上$(2\times i)^m$。如在第$1$关，若你手上有$2$种颜色，分别为蓝色和绿色。则总 方案数为$2\times 2\times 2=8$种，涂色方案数为 2（如下图，旋转、翻转相同算不同的方案），然后 还要再乘 2 个 2，最后你出来之后我会问你所有关中计算出来的数的和。如果你能答对，我就可以让你出去了，否则就无限轮回吧。

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

fyg 表示这个问题太水了，完全不想算。。。于是，他马上打开电脑上了QQ找到了喜欢计算的你，求你帮他直接把最终答案算出来，让他回到赵州桥上。

这两个数都有可能很大，fyg 不想为难你，所以你只要告诉他其除以 $p$ 的余数。

inputFormat: 只有一行，其中包含三个正数 $n$、$m$、$p$，分别由一个空格分开。$n$、$m$、$p$ 含义和题目描述一致。

outputFormat: 一行，表示方案数的和除以 $p$ 的余数。

hint:
### 【样例说明】
总共有 $2$ 关。

第一关的桥长度为 $1$，总共有 $2$ 个格子，涂色方案数为 $20$，再乘上 $2 ^ 5$，第一关中计算出的数为 $640$。

第二关的桥长度为 $2$，总共有 $4$ 个格子，涂色方案数为 $260$，再乘上 $4 ^ 5$，第二关中计算出的数为 $266240$。

两个数字加起来除以 $50$ 余 $30$，故输出为 $30$。

### 【数据范围】

对于其中 25%的数据，满足 $n\leq10^6$，$m\leq200$，$p\leq10^9$；

对于其中 40%的数据，满足 $n\leq10^9$，$m\leq120$，$p\leq10^9$；

对于其中 15%的数据，满足 $n\leq10^9$，$m\leq200$，$p \leq10^9$；

对于最后 20%的数据，满足 $n\leq10^9$，$m\leq3000$，$p\leq3000$；

HEOI 2012 Day2 Task1