新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。

在前期市场调查和站址勘测之后，公司得到了一共 $N$ 个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第 $i$ 个通讯中转站需要的成本为 $P_i$ 。

另外公司调查得出了所有期望中的用户群，一共 $M$ 个。关于第 i 个用户群的信息概括为 $A_i$ , $B_i$ 和 $C_i$ ：这些用户会使用中转站 $A_i$ 和中转站 $B_i$ 进行通讯，公司可以获益 $C_i$ 。

THU 集团的 CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）

给定一个 $n$ 个点， $m$ 条边的无向图。聪聪开始的时候在 S，可可在节点 T 处。以后的每个时间单位，可可都会选择去相邻的景点(可能有多个)中的一个或停留在原景点不动。而去这些地方所发生的概率是相等的。假设有 $P$ 个景点与景点 M 相邻，它们分别是景点 R、 景点 S，……，景点 Q，在时刻 $i$ 可可处在景点 M，则在 $i+1$ 时刻，可可有 $\frac{1}{1+P}$ 的可能在景点 R，有 $\frac{1}{1+P}$ 的可能在景点 S，……，有 $\frac{1}{1+P}$ 的可能在景点 Q，还有 $\frac{1}{1+P}$ 的可能停在景点 M。

当聪聪在景点 C 时，她会选一个更靠近可可的景点，如果这样的景点有多个，她会选一个标号最小的景点。如果走完第一次移动以后仍然没吃到可可，她还可以在本段时间内再向可可进行一次移动。

在每个时间单位，假设聪聪先走，可可后走。在某一时刻，若聪聪和可可位于同一个景点，则可怜的可可就被吃掉了。

请求出平均情况下，聪聪用几个时间单位就可能吃到可可。

小 $Y$ 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：$A$ 纪念券（以下简称 $A$ 券）和 $B$ 纪念券（以下简称 $B$ 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 $K$ 天中 $A$ 券 和 $B$ 券的价值分别为 $A_K$ 和 $B_K$（元/单位金券）。为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。比例交易法分为两个方面：

（a）卖出金券：顾客提供一个 $[0,100]$ 内的实数 $OP$ 作为卖出比例，其意义为：将 $OP%$ 的 $A$ 券和 $OP%$ 的 $B$ 券以当时的价值兑换为人民币；

（b）买入金券：顾客支付 $IP$ 元人民币，交易所将会兑换给用户总价值为 $IP$ 的金券，并且，满足提供给顾客的 $A$ 券和 $B$ 券的比例在第 $K$ 天恰好为 $Rate_K$ ；

注意到，同一天内可以进行多次操作。小 $Y$ 是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来 $N$ 天内的 $A$ 券和 $B$ 券的价值以及 $Rate$ 。他还希望能够计算出来，如果开始时拥有 $S$ 元钱，那么 $N$ 天后最多能够获得多少元钱。

为了庆祝 $NOI$ 的成功开幕，主办方为大家准备了一场寿司晚宴。小 $G$ 和小 $W$ 作为参加 $NOI$ 的选手，也被邀请参加了寿司晚宴。

在晚宴上，主办方为大家提供了 $n−1$ 种不同的寿司，编号 $1,2,3,⋯,n-1$ ，其中第种寿司的美味度为 $i+1$（即寿司的美味度为从 $2$ 到 $n$ ）。

现在小 $G$ 和小 $W$ 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 $G$ 品尝的寿司种类中存在一种美味度为 $x$ 的寿司，小 $W$ 品尝的寿司中存在一种美味度为 $y$ 的寿司，而 $x$ 与 $y$ 不互质。

现在小 $G$ 和小 $W$ 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 $p$ 取模）。注意一个人可以不吃任何寿司。

小 $\text{G}$ 是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。

一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小 $\text{G}$ 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小 $\text{G}$ 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小 $\text{G}$ 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的 $P$ 次方，而一个排版的不协调度为所有行不协调度的总和。

小 $\text{G}$ 最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。

将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘，它是一个 $N$ 行 $M$ 列的网格棋盘，每个格子中均有一个正整数。棋盘守护者在棋盘的第 $X$ 行第 $Y$ 列（行与列均从 $1$ 开始编号）并且始终不会移动。棋盘守护者会进行两种操作：

1. 询问：他会以自己所在位置为基础，向四周随机扩展出一块大小不定的矩形区域，向你询问这一区域内所有数的最大公约数是多少。

2. 修改：他会随意挑选棋盘上的一块矩形区域，将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友，当你连续答对 $19930324$ 次询问后会得到一个惊喜噢！”。小 Q 十分想得到这个惊喜，于是每天都在玩这个玩具。但由于他粗心大意，经常算错数，难以达到这个目标。于是他来向你寻求帮助，希望你帮他写一个程序来回答棋盘守护者的询问，并保证 $100%$ 的正确率。

为了简化问题，你的程序只需要完成棋盘守护者的 $T$ 次操作，并且问题保证任何时刻棋盘上的数字均为不超过 $2^{62} - 1$ 的正整数。

给定正整数 $n,m,a,c,X[0],g$ ，求按照 $X[n+1] = (a X[n] + c) \bmod m$ 生成出的第 $n$ 项 $X[n] \bmod g$ 的值。

数据范围： $n,m,a,c,X[0] \leq 10^{18}$

题面请点击查看全文

假设目前被延误航班共有 $n$ 个，编号为 $1$ 至 $n$ 。机场只有一条起飞跑道，所有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一个航班的起飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。

起飞序列还存在两类限制条件：

• 第一类（最晚起飞时间限制）：编号为 $i$ 的航班起飞序号不得超过 $k_i$ ;

• 第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制 $(a, b)$ ，表示航班 $a$ 的起飞时间必须早于航班 $b$ ，即航班 $a$ 的起飞序号必须小于航班 $b$ 的起飞序号。

小 $\text{X}$ 思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个可行的起飞序列。第二个问题则是，在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

简单版题意：

给定一个长度为 $n$ 的字符串，和一个长度为 $n$ 的数列 ${a_n}$ ，求对于 $r$ 从 $0$ 到 $n-1$ ，所有满足 $1 \leq p < q \leq n$ 且 $lcp(p,q) \geq r$ 的数对个数以及满足上述条件的数对中 $a_p \times a_q$ 的最大值。（ $a_i$ 可以为负数）

如果一个字符串可以被拆分为 $AABB$ 的形式，其中 $A$ 和 $B$ 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$ ，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

• 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
• 在一个拆分中，允许出现 $A = B$。例如 $cccc$ 存在拆分 $A = B = c$。
• 字符串本身也是它的一个子串。

给定两个整数 $n,m$ ，对于平面上的整点 ${(x,y)|x \in [1,n],y \in [1,m],x,y \in \mathbb Z}$ 。若 $(x,y)$ 与 $(0,0)$ 的连线上有 $k$ 个整点（不包括 $(0,0),(n,m)$ ），则产生的贡献为 $2k+1$ 。求所有满足条件的点的贡献总和。

给定一个 $n$ 个点 $m$ 条边的无向图，每条边有两个权值 $a_i,b_i$ 。请你找到一条从 $1 \rightarrow n$ 的道路，令道路上所有边的集合为 $S$ ，使 $ans = \max(a_i)+\max(b_j),i,j \in S$ 最小，求出这个最小值 $ans$ 。

美食节共有 $n$ 种不同的菜品，每个同学都点了一份在这 $n$ 个菜品中的菜。总共有 $m$ 个厨师来制作这些菜品。厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。第 $j$ 个厨师制作第 $i$ 种菜品的时间记为 $t _ {i,j}$ 。每个同学的等待时间为所有厨师开始做菜起，到自己那份菜品完成为止的时间总长度。总等待时间为所有同学的等待时间之和。

已知共有 $n$ 种菜品，第 $i$ 种菜品需要做 $p_i$ 份，共有 $m$ 个厨师。请计算出最小的总等待时间是多少。

给定 $n$ 个结点的数据值 $V_i$ ，权值 $P_i$ ，访问频度 $T_i(T_i \geq 0)$ 。对于 $\forall i,j \in V$ 且 $i \neq j$ ，有 $V_i \neq V_j, P_i \neq P_j$ 。

现令这 $n$ 个点组成一颗二叉树，且满足 $\forall , i \in V$ ，若 $p$ 为 $i$ 的左子节点， $q$ 为 $i$ 的右子节点，则 $V_p < V_i < V_q$ 且 $P_i < P_p,; P_i < P_q$ 。可以证明，这样的二叉树是唯一的。点$i$ 在树中的深度 $D_i$ 定义为它到根的距离加 $1$ 。定义结点 $i$ 的访问代价 $E_i = T_i \times D_i$ 。可以修改每个点的权值为任意实数，其代价均为给定的正整数 $K$ ，但需保证任两点权值仍互不相同。

现求上文所述二叉树中，其 $\sum^n _ {i = 1}{E_i} + \sum K$ 的最小值。