title: 『MdOI R2』Odyssey

background:
超越音速的极限，不及瑰丽多变的极光；

微弱的脉冲，开拓原本一片混沌的天地；

沉郁的蓝缓缓闪动，史诗的红迎接巅峰；

血色的夕阳尽头，是将夜的星辰；

夜半的满天星空，也会被来自地狱的硝烟掩盖；

炽红炼狱消逝，只金色遗迹永存。

在这里等待着每一位的，都是一段艰苦而璀璨的旅程。

description:
若正整数 $a$ 与 $b$ 满足：

- $a$ 与 $b$ 的积是一个正整数的 $k$ 次方，即存在正整数 $c$ 使得 $ab=c^k$。

那么我们称 $(a,b)$ 为一组**完美数对**。

---

有一个包含 $n$ 个结点和 $m$ 条边的**有向无环图**，这张图中的每条边都有权值和长度两个属性。

如果一条路径 $P$ 满足**以下条件之一**，则称其为一条**完美路径**：

- $P$ 中仅包含一条边。

- $P$ 从其起点开始依次为 $e_1, e_2, e_3, \ldots e_p$ 这 $p\ (p\ge 2)$ 条边，对于任意的 $1\leq i\leq p-1$，$e_i$ 的权值和 $e_{i+1}$ 的权值组成完美数对。

你需要求出图中最长完美路径的长度，一条路径的长度定义为这条路径上所有边的长度之和。

inputFormat:
第一行：三个整数 $n,m,k$，分别表示有向无环图的结点数、边数和完美数对的参数。

接下来 $m$ 行：每行四个整数 $u,v,w,l$，表示有一条权值为 $w$，长度为 $l$ 的有向边从 $u$ 连向 $v$。

outputFormat: 第一行：一个整数 $ans$，表示最长完美路径的长度。

hint:
【帮助与提示】

为方便选手测试代码，本题额外提供两组附加样例供选手使用。

[样例输入1](https://www.luogu.com.cn/paste/wx1lz6m2) [样例输出1](https://www.luogu.com.cn/paste/28xe7f0x)

[样例输入2](https://www.luogu.com.cn/paste/efgwngs5) [样例输出2](https://www.luogu.com.cn/paste/5hcpoayt)

----

【样例解释】

样例中给出的有向无环图如图所示，其中边上的红色数字为边的权值，黑色数字为边的长度：

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

最长完美路径为 $2\to 5\to 3$，因为这两条边的权值 $2$ 和 $18$ 满足 $2\times 18=6^2$，是完美数对，此路径长度为 $5+9=14$。

此外，$2\to 1\to 4\to 3,\ \ 2\to 4\to 3,\ \ 1\to 5\to 3$ 等也是完美路径，但不是最长的。

图中，$2\to 1\to 5\to 3$ 长度为 $15$，是一条更长的路径，但它并不是完美路径，因为前两个边权 $24$ 和 $8$ 的乘积为 $192$，不是正整数的平方，即 $(24,8)$ 不是完美数对。

---

【数据范围】

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

对于 $100\%$ 的数据：$1\leq n\leq 10^5,\ \ 1\leq m\leq 2\times 10^5,\ \ 1\leq k\leq 10,\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^5,\ \ 1\leq l\leq 10^4$。

给出的图**不保证弱连通**，图中从一个点到另一个点**可能**存在多条边，但保证给出的图是有向无环图。

| 子任务编号 | $n\leq$ |     $m\leq$      | $w\leq$ | $k\leq$ |  特殊性质  | 分值 |
| :--------: | :-----: | :--------------: | :-----: | :-----: | :--------: | :--: |
| Subtask 1  | $10^5$  |  $2\times 10^5$  | $10^5$  |   $1$   |     无     | $18$ |
| Subtask 2  |  $10$   |       $10$       |  $100$  |  $2$   |     无     | $12$ |
| Subtask 3  |  $600$  | $1.5\times 10^3$ | $10^3$  |   $2$   |     无     | $10$ |
| Subtask 4  | $10^5$  |  $2\times 10^5$  | $10^5$  |   $2$   | $w$ 为素数 | $15$ |
| Subtask 5  | $10^5$  |  $2\times 10^5$  | $10^5$  |   $2$   |     无     | $15$ |
| Subtask 6  |  $600$  | $1.5\times 10^3$ | $10^3$  |  $5$   |     无     | $10$ |
| Subtask 7  | $10^5$  |  $2\times 10^5$  | $10^5$  |  $10$   |     无     | $20$ |


title: 【模板】普通平衡树（数据加强版）

type: P

background:
本题是 P3369 数据加强版，**扩大数据范围**并增加了**强制在线**。

**题目的输入、输出和原题略有不同**，但需要支持的操作相同。

description:
您需要写一种数据结构（可参考题目标题），来维护一些整数，其中需要提供以下操作：

1. 插入一个整数 $x$。
2. 删除一个整数 $x$（若有多个相同的数，只删除一个）。
3. 查询整数 $x$ 的排名（排名定义为比当前数小的数的个数 $+1$）。
4. 查询排名为 $x$ 的数（如果不存在，则认为是排名小于 $x$ 的最大数。保证 $x$ 不会超过当前数据结构中数的总数）。
5. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
6. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。

本题**强制在线**，保证所有操作合法（操作 $2$ 保证存在至少一个 $x$，操作 $4,5,6$ 保证存在答案）。

inputFormat:
第一行两个正整数 $n,m$，表示**初始数的个数**和操作的个数。

**第二行 $n$ 个整数 $a_1,a_2,a_3,\ldots,a_n$，表示初始的数**。

接下来 $m$ 行，每行有两个整数 $\text{opt}$ 和 $x'$，$\text{opt}$ 表示操作的序号（$ 1 \leq \text{opt} \leq 6 $），$x'$ 表示加密后的操作数。

我们记 $\text{last}$ 表示上一次 $3,4,5,6$ 操作的答案，则每次操作的 $x'$ 都要**异或**上 $\text{last}$ 才是真实的 $x$。初始 $\text{last}$ 为 $0$。

outputFormat: 输出一行一个整数，表示所有 $3,4,5,6$ 操作的答案的**异或和**。


title: 要有光

background:
$$ \text{Der mir zeigt wo ich bin}$$
$$_\texttt{告诉我身在何方}  $$
$$\text{Divano}$$
$$_\texttt{神啊}$$
$$\text{Sei mein Licht}  $$
$$_\texttt{做我的光}$$
$$\text{Ich sm chte mich dir schenken}$$
$$_\texttt{我愿将自己赐予与你}$$
$$\text{Noch vor dem Sonnenaufgang}$$
$$_\texttt{在晨曦来临之前}$$

  那时正值春深，丛林里生灵闹哄哄地雀跃，享受着空气中升腾的灵气。
  “嗖”的一声，一团银灰色的小东西突然从她眼前的地面划过，要不是腾起的尘土在阳光下悠闲地闪烁，她甚至怀疑是自己花了眼。
  紧接着，又“嗖”的一声，这次她看清楚了，是一只雪白的幼龄狐妖，“还……有点可爱。”
  “真走运，捉了这只，就可以交差啦。”她，虽年少却赫赫有名的除妖师，绫，急忙跟了上去。

description:
万物有灵，法术亦是如此。任何法术都等价为一段**仅包括大小写字母**的字符串 $S=s_1s_2\dots s_n$，现规定如下几种法术记号：

- **元素**。即字符串中的每个字符。在本题中，元素仅为大小写字母。
- **法术大小**。即字符串长度。记号为 $|S|$ 。
- **空法术**。大小为 $0$ 的法术为空法术。
- **等法术**。对于法术 $S,T$ 。当且仅当 $|S|=|T|,\forall i \leq |S| , s_i = t_i$ 时，称 $S$ 与 $T$ 为等法术，记为 $S=T$  。
- **逆法术**。设现有法术 $S=s_1s_2\dots s_n$，称法术 $T$ 是 $S$ 的逆法术，当且仅当 $|S|=|T|$ 且 $\forall i \leq |S| , s_i=t_{n-i+1}$。本题将 $T$ 记作 $S_r$。
- **逆法术对**。称两法术 $S$，$T$ 构成逆法术对 $(S,T)$，当且仅当 $T=S_r$。
- **归法术**。设现有法术 $S$，称 $S$ 为归法术当且仅当 $S$ 对应的字符串为**回文串**。特别地，**空法术被视作归法术**。
- **子法术**。设现有法术 $S$ ，则对于 $1\le i\le j\le |S|$ ，称 $T=s_is_{i+1}\dots s_j$ 为 $S$ 的子法术，并规定子法术的记号 $S[i,j]$ 。当 $i>j$ 时，$S[i,j]$ 为空法术。

---

现在，绫有一个法术源 $S_0$, 而她已经凝练出了一个初始的法术 $S=S_0$。对于每种妖魔，都有一个法术弱点  $T$。绫的法术性火，而火系法术又以淬光之术为上等。所以绫想要练习淬光之术。只要绫通过以下淬光法术变换使 $S=T$，就能轻易击败妖魔：

- **光归**。对于**任意非空法术** $S$，保留其**最大归法术后缀**。若$|S|=n$即取一个最小的 $i \in [1,n]$ 使得 $S[i+1,n]$ 为归法术，并令 $S \leftarrow T$。**允许 $T$ 为空法术**。消耗时间 $A$。
- **光辉**。对于**归法术** $S$，在 $S_0$ 中寻找一个**子归法术** $T$，满足 $S$ 为 $T$ 的**最大归法术后缀**（其定义见 "光归" ），并令 $S\leftarrow T$。**空法术**被认为是**任何法术的后缀**。消耗时间 $B$。
- **光隐**。对于**非空归法术** $S$，$|S|=n$ 删去其长度相等且长度**不大于 $k$ **的**前缀与后缀**。即取一个 $i\in[1,\min\{k,\lfloor\frac{n-1}2\rfloor\}]$，使 $T=S[1+i,n-i]$，并令 $S\leftarrow T$。特别地，$T$ **不可以为空法术**，消耗时间 $C$。
- **光腾**。对于**非空归法术** $S,|S|=n$，在其左右加上一对逆法术对。即取一逆法术对 $(P,Q)$，设 $|P|=|Q|=l$，使 $T=p_1p_2\dots p_ls_1s_2\dots s_nq_1q_2\dots q_l$，且 $T$ **须为 $S_{0}$ 的子法术** ，并令 $S\leftarrow T$。消耗时间 $D$。
- **光弋**。对于**任意非空法术** $S,|S|=n$ ，在其前端加入任意元素。即取一个元素 $a$，使 $T=as_1s_2\dots s_n$，并令 $S\leftarrow T$，消耗时间 $E$。光弋变换玄妙莫测，绫还没有熟练掌握此法术变换。所以**在使用此变换之后，无法再使用其它类型的法术变换**。

现在绫想知道，对于不同妖魔的法术弱点 $T$，自己至少要消耗多少时间进行如上法术变换使 $S=T$。**每组询问间互不干扰**。

inputFormat:
第一行输入一个**仅包含大小写字母**的字符串，表示绫的法术源 $S_0$。由题意，初始法术 $S=S_0$。

第二行输入一个正整数 $k$，表示**光隐**变换所允许删去前缀后缀的最长长度。

第三行输入五个正整数 $A,B,C,D,E$，表示每种法术变换的消耗时间。

第四行一个正整数 $q$，表示询问组数。

接下来 $q$ 行，每行包含两个正整数 $l,r$，表示一种妖魔的法术弱点为 $T=S_0[l,r]$。

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

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

对于第一个询问，因为 $T=\texttt{"ababa"}=S$，不需要操作。

对于第二个询问，$T=\texttt{"ba"}$，最优策略为先使用一次**光隐**，得到 $S'=\texttt{"a"}$；接着使用一次**光弋**，在 $S'$ 前添加元素 $\texttt{'b'}$ 得到 $S''=\texttt{"ba"}=T$，耗时 $4+1=5$。

对于第三个询问，$T=\texttt{"aba"}$，最优策略为使用一次**光归**，得到 $S'=\texttt{"aba"}=T$。耗时 $3$。

------------
#### 数据范围
对于不同的测试点，我们约定数据规模如下:

| 测试点编号 | $\left\vert S \right\vert,\left\vert T \right\vert \le$ | $q\le$ | 特殊限制 |
|:-:|:-:|:-:|:-:|
| $1 \sim 5$ | $10^3$ | $10^3$ | 无 |
| $6 \sim 9$ | $10^5$ | $10^5$ | 初始法术只有一种元素 |
| $10 \sim 20$ | $10^5$ | $10^5$ | 无 |

对于 $100\%$ 的数据，$1 \le q,|S| \leq 10^5$，$1 \leq A,B,C,D,E \leq 10^9$，$1 \leq l \leq r \leq |S|$，$1 \leq k \leq 5$。

------------
### 题目背景 ( 续 )
  这边，绫还在摸索着变换法术，却感觉腰间的令牌被抓了一下。“喂？！”
  只见一个披头散发的少女正半跪着扒在她的腰间，左手还提着银灰色毛发的小兔子的一对耳朵，“你……是刚才那只狐狸？”绫尴尬地收回法术，不自觉地伸出手揉了揉少女头顶雪白的兽耳，心想着这只狐狸精得有多傻。“我可是除妖师哟，你不怕吗？”
  “……绫？”少女并没有理会绫的话，只是努力地认出了令牌上刻着的名字。
  绫好奇的目光撞上了少女璀璨的碧绿双眸，又不经意间扫过小巧的鼻梁，玲珑的小嘴，白皙的脖子，但再随着如凝的肌肤滑下……
  一直被视作男儿的绫哪见过这般风景，只觉得自己大脑当了机，还隐约嗅到出自鼻腔的铁锈味儿，身体便向后靠倒在一棵树干上，连忙用双手捂住滚烫的脸颊。
  “绫？绫？你怎么啦？！”少女心急地凑上去，绫吓得下意识往后退，却忘记身后是一棵粗壮的树干。“欸，绫手上的，是血吗……”双眼紧闭的绫听得出来少女像是被吓到了，看来还是一只没开过荤的狐狸精呢。
  “绫……你没事吧……”少女分明带着哭腔，小心翼翼地学着自己还是小狐狸的时候妈妈照顾自己的方式，在绫的身上东摸西摸。
  “我，我没事……”绫已经不敢想象究竟是哪些部位在触碰自己的皮肤了，“你……你先变回狐狸……快！”绫当然想把少女推开，却又怎么敢伸出手触碰少女呢？
  少女闻言，一怔，但还是乖乖变回了一只狐狸，还不忘叼起几欲逃走的兔子。
  绫赶忙收拾了自己的窘相，惊恐地扶着树干，确认自己的人身安全后，轻轻捏住小狐狸的后颈，提起在地上的两小只。
  “以后不许再胡乱变成人形了，听到没有！”绫后怕地警告着小狐狸，却见右手的小狐狸直勾勾地盯着左手的小兔子，而左手的小兔子好像想钻进自己的手心里，哪有听她的话呀……
  “哎，算了……”绫把小狐狸放在肩头，把似乎吓晕的小兔子递给她，“一会儿再吃哦。”（雨兔兔：我好难qwq。）
  “就算……捡了一只宠物吧。”绫心里想着。

  （未完待续www……）


title: 「SWTR-4」Meeting in the Forest

background: 每当月圆时分，五个族群的族猫们都会聚集在小岛上，进行每月的森林大会。蒟星为了了解其它五族猫的特点，就扮成了一只独行猫来到小岛上……

description:
森林大会上有 $n$ 只猫，每只猫的武力值为 $a_i$，于是蒟星列出了下面这样一个方程：

$$x^n+\sum_{i=1}^{n}a_ix^{n-i}=0$$

- 通俗地讲，这个方程就是 $x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-1}x+a_n=0$。

蒟星根据 TA 优（cu）秀（bi）的数学知识可以知道，这个方程在复数集内有 $n$ 个根，不妨把这 $n$ 个根设为 $x_1, x_2, ..., x_n$。

接下来蒟星想要知道森林大会上的猫的实力如何，于是列出了下面一个表达式：

$$\sum_{i=1}^{n}(b_i\times \sum_{1\le j_1 < j_2 <\cdots< j_i \le n}^{n}x_{j_1}x_{j_2}\cdots x_{j_i})$$

- $\sum_{1\le j_1 < j_2 < \cdots < j_i \le n}^{n}x_{j_1}x_{j_2}\cdots x_{j_i}$ 就是从方程的 $n$ 个根中选出 $i$ 个，求所有可能方案的 $i$ 个根的乘积之和。

但蒟星只要这个表达式对 $10^9+7$ 取模后的值就好了。

- 若答案为负数 $a$，请输出 $a + (10^9+7)$。

蒟星把这个任务交给了您，不过他已经告诉你了 $n$，$a_i$ 和 $b_i$，您能帮帮 TA 吗？

inputFormat:
第一行一个整数 $n$ —— 表示方程的次数。

第二行 $n$ 个整数 $a_1, a_2, ... a_n$ —— 意义见题目描述。

第三行 $n$ 个整数 $b_1, b_2, ... b_n$ —— 同上。

outputFormat: 输出一行，一个数，表示这个表达式对 $10^9+7$ 取模后的值。


title: [IOI2012] 骑马比武竞赛

description:
1491 年公爵 Milan Lodovico Sforza 为了他与 Beatrice d'Este 的婚礼，要求Leonardo 来负责筹备婚礼的庆典。在这个庆典中包含了一个盛大的持续三天的骑马比武竞赛，但是最受欢迎的骑士迟到了...

在一骑马比武的竞赛，$N$ 个骑士一开始被排成一排然后按照他们的位置从 $0$ 到 $N-1$ 开始编号。骑马比武的主持人每一回合叫出两个位置 $S$ 跟 $E$ （其中 $0 \le S < E \le N - 1$）。所有介于 $S$ 与 $E$ （含） 这两个位置的骑士则开始进行骑马比武。最后的赢家可以留下来继续进行竞赛， 并回到他原来的位置，而输家则离开这个竞赛。在这之后，剩下的骑士按照原来排列的顺 序，往前挤掉空出来的位置。所以他们的位置编号变成从 $0$ 到 $N - (E - S) - 1$。骑马比武竞赛的主持人接着进行下一个回合的比赛，直到最后剩下唯一个骑士。

Leonardo 知道所有骑士有不同的强度，这个强度从 $0$ (最弱) 到 $N-1$ (最强)。他也知道骑马比武竞赛的主持人会下怎么样的命令来进行C回合的竞赛，毕竟他是无所不能的   Leonardo。而且他也确定在每一个回合中，拥有最大强度的骑士会获得胜利。

$N$ 个骑士中的 $N-1$ 个骑士已经排成了一排，只是最受欢迎的骑士还未出现。这个骑士的强度为 $R$ 但是他迟到了。为了让这场竞赛达到最高潮, Leonardo  想要让这个骑士能好好展现他的风采，所以想要帮他安插一个位置，而这个位置可以使得这个骑士能获得最多回合的 胜利。请注意，我们不关心与此骑士无关的回合。我们只关心包含此骑士而且由他赢得胜利的回合。

**例子**

假设有 $5$ 个骑士，其中 $4$ 个骑士已经排列好，而他们的强度分别是 $[1,0,2,4]$。而迟到骑士的强度为 $3$ 。假设要进行 $3$ 回合，骑马比武的主持人打算要叫出的位置 $(S,E)$ 分别是 $(1, 3)$，$(0, 1)$，$(0, 1)$。

假设 Leonardo  将迟到的骑士插到第一个位置而且迟到的骑士强度为 $3$。那么骑士强度的排列将会是 $[3, 1, 0, 2, 4]$。第一回合参与的骑士为位置 $1,2,3$ 的骑士，他们的强度分别是 $1,0,2$，所以由强度 $2$ 的骑士获得胜利。经过这一回合，新的骑士强度的排列变成 $[3, 2, 4]]$。下一个回合是由强度 $3$ 与强度 $2$（位置 $0,1$）的骑士进行比赛，由强度 $3$ 的骑士获得胜利。而骑士强度的排列则变成 $[3,4]$。最后一回合（位置 $0,1$）由强度 $4$ 的骑士获得胜利。那么，迟到的骑士只有获得一回合的胜利 (第二回合)。

若 Leonardo 将迟到的骑士插入强度 $1$ 与强度 $0$ 的骑士中间，骑士强度的排列将会是 $[1,3,0,2,4]$。这一次,  第一回合比赛的骑士强度为 $3,0,2$。由强度 $3$ 的骑士获胜，然后骑士强度的排列变成 $[1,3,4]$。在第二回合中由强度 $1$ 对上强度 $3$ 的骑士，由强度 $3$ 的骑士获胜。最后的一回合，骑士强度的排列变成  $[3,4]$，由强度 $4$ 的骑士获得胜利。在这个排列中，迟到的骑士获得两回合的胜利。这实际上是最佳的位置，因为没有其他的位置可以让迟到的骑士获得两回合以上的胜利。

你的任务是写一个程序来帮迟到的骑士选择最佳的位置让他能获得最多的胜利回合数，以符合 Leonardo 的期待。

inputFormat:
- 第一行，$3$个整数 $N$，$C$，$R$，其中 $N$ 表示骑士的个数，$C$ 表示竞赛主持人会进行的回合数，$R$ 表示迟到的骑士的强度。
- 第二行，$N$ 个整数 $K[0],K[1],\cdots,K[N-1]$，表示已经排列好成一列的 $N-1$ 个骑士的强度
- 第三行，$2C$ 个整数 $S[0],E[0],S[1],E[1],\cdots,E[N-1],S[N-1]$，对于 $0 \le i \le C-1$，竞赛主持人进行第 $i +1$ 回合比赛的骑士为从位置 $S[i]$ 到位置 $E[i]$ (含). 你可以假设对每一个 $i$ , $S[i] < E[i]$。

outputFormat: 共一行，让迟到的骑士能获得最多胜利回合数的位置。如果存在多个最优的位置，输出编号最小的位置。

hint: 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le C \le N-1$，在第 $i+1$ 回合，$E[i]$ 会小于这个回合剩下的骑士数量。经过 $C$ 回合的命令之后，只会剩下一个骑士。


title: [SBCOI2020] 时光的流逝

background:
时间一分一秒的过着，伴随着雪一同消融在了这个冬天，
或许，要是时光能停留在这一刻，该有多好啊。
......
“这是...我在这个小镇的最后一个冬天了吧。”
“嗯，你可不能这辈子都呆在这个小镇吧。外面的世界很大呢，很大很大...”
“唔...外面的世界...突然有点期待呢！”
“总有一天，你会走得很远很远。以后你可不要忘记这个小镇那。”
“不会的，至少...这里曾经是我最快乐的一段回忆呢！你也一定不要忘记我呀。”
“你看，这雪花。传说，每当世界上有一份思念，便会化成一片雪花在这里飘落。”
“那...以后你可一定要找到我的那片雪花啊......”
![](https://cdn.luogu.com.cn/upload/image_hosting/orzntcy6.png)
“嗯，不如我们一起在这个冬天创造最后一段回忆吧。”
“好呀，我们玩个游戏吧......”

description:
这个游戏是在一个有向图（不保证无环）上进行的。每轮游戏开始前，她们先在图上选定一个起点和一个终点，并在起点处放上一枚棋子。

然后两人轮流移动棋子，每次可以将棋子按照有向图的方向移动至相邻的点。

如果谁先将棋子移动至终点，那么谁就胜利了。同样，如果谁无法移动了，那么谁就失败了。

两人轮流操作，请问，他们是否有必胜策略呢？

答案为一个整数 `0` 或 `1` 或 `-1`，其中 `1` 表示（先手）有必胜策略，`-1` 表示后手有必胜策略，`0` 表示两人均无必胜策略。

inputFormat:
第$\text{1}$行有三个整数 $n,m,q$ ，表示图上有 $n$ 个点， $m$ 条边，一共进行 $q$ 轮游戏。
接下来 $m$ 行，每行输入两个数 $u_i,v_i$ ，表示 $u_i$ 到 $v_i$ 有一条边。
接下来 $q$ 行，每行两个数 $x,y$ ，表示每轮操作的起点和终点。数据保证起点，终点不同

outputFormat: 对于每轮游戏，仅输出一个整数 `0` 或 `1` 或 `-1`，其中 `1` 表示先手有必胜策略，`-1` 表示后手有必胜策略，`0` 表示两人均无必胜策略。

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

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

为描述题意，假设两人为 A（先手）和 B

如图，A 先走，走到 $2$，B 走到 $3$，接下去 A 可以选择走到 $4$ 或 $6$，若走到 $4$，接下去 B 可以走到终点，故不可取。若选择走到 $6$，那么 B 只能走到 $7$，A 可以走到终点。所以 A 有必胜策略。

#### 样例解释 $#2$

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

如图，起点为 $1$，终点为 $5$ 时， A 和 B 会沿着 $1-2-3-1$ 的顺序轮流走。因为如果谁先走到 $4$，那么下一个人就可以走到终点。故谁都没有必胜策略。

起点为 $4$，终点为 $3$ 时，A 先走到 $5$，B 无路可走，故 B 失败。

#### 数据范围

对于 $10\%$ 的数据，保证图是一条链。

对于 $50\%$ 的数据，$1\leq n\leq 10^3$，$1\leq m\leq 2\times10^3$，$1\leq q\leq 10$。

对于 $70\%$ 的数据，$1\leq n\leq 10^5$，$1\leq m\leq 2\times10^5$，$1\leq q\leq 10$。

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq m\leq 5\times10^5$，$1\leq q\leq 500$。


title: 中意

background:
（背景改编自百度贴吧/南北组备用吧/呆萌南北日常/F8984，作者 [落墨成白](https://tieba.baidu.com/home/main/?un=%E8%93%93%E8%90%BD%E9%B1%BC&ie=utf-8&id=tb.1.a8bcbb73.CMcL9PXngjHz-dKRJ7_T4A&fr=frs)）

  在这样的时间，这样的情形下她与她面面相望却不动一步，只有一个可能——她在等。
  等她求助，等她妥协，等她心甘情愿。
  洛天依想这厮做事儿还真是欠扁，看着手机屏幕上跳出的字：“还不过来？”
  她毫不客气的回道：“你想让我过到哪儿去呀？”
  “如果除了到了身边来，还有别的路可以走的话。”
  当然妥协的乐正大小姐虽然嘴里叨念着，提着路上买的双皮奶和蛋挞，仍是乖乖先迈动了步子。
  刚一开门，小吃货果然乖乖扑进怀里了。
  “不能全吃哦，来做个游戏吧！”
  “坏蛋阿绫。”

description:
**和题意有关的句子已加粗。**

  “首先，有一个神奇的数字 $a$。”
  “天依很饿呢，**所以就给天依 $2^{a+2}$ 个蛋挞吧。**”
  “我还要！”
  “那……还有一个神奇的数字 $b$，**天依可以获得 $b$ 倍的蛋挞哦！**”
  **“哇！那我就有 $k=b \times 2^{a+2}$ 个蛋挞啦！**”
  “天依还喜欢整百数呢，**所以凑个整，给 $p=\lceil \frac{k}{25}\rceil \times 100$ 个蛋挞吧！**”
  “阿绫太好啦！”
  “呐\~给你。”阿绫笑着抚过天依的脑袋，从袋子里拿出寥寥几个蛋挞。
  “欸？！”
  “最后，天依不能吃太多哦，**所以 $p$ 要对 $\color{black} 998 \color{red}3 \color{black} 44353$ 取模。**”
  “…果然是坏蛋。”

现在天依想知道，对于阿绫给出的 $a$ 和 $b$，自己究竟能吃到几个蛋挞，即 $p \bmod \color{black} 998 \color{red}3 \color{black} 44353$ 的结果是多少？

注：$\lceil x \rceil$ 指 $x$ 向上取整。

inputFormat:
一行两个整数，分别表示 $b$ 和 $a$。

**请注意输入顺序。**

outputFormat: 一行一个整数 $p$，表示天依能得到的蛋挞个数。

hint:
#### 样例解释 #2

$k=60 \times 2^{(15+2)}=7864320$，$p=\lceil \frac{k}{25} \rceil \times 100 =31457300$。

------------
#### 数据范围
**本题采用捆绑测试。**

- Subtask 1（20 Points），$a,b \leq 100$ 且 $b \equiv 0 \pmod{25}$。
- Subtask 2（50 Points），$b \leq 10^9$。
- Subtask 3（30 Points），数据无特殊限制。

对于 $100 \%$ 的数据，$20 \leq b \leq 10^{10010}$，$1 \leq a \leq 10^{18}+8$。

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

#### 题目背景 ( 续 )

  还是万分纠结地看着天依手中甜腻的早餐，“一大早吃这么甜，摄入糖分过多会促使动脉硬化，会……”
  洛天依打断她：“那你想不想更甜一点？”
  “嗯？”
  洛天依踮起脚轻轻地在她的右脸颊印下一个吻，“乐正绫，我好中意你呀。”
  乐正绫愣了愣，问：“你说什么？”
  洛天依脸红了红，转过身小口咀嚼着蛋挞：“听不懂算了。”
  “我也好中意你呀。”像羽毛一样轻柔的声音，撩过两人的心尖。
  口中的蛋挞果真又甜腻上几分了呢。


title: 「SWTR-4」Taking a Walk

background:
小 A 喜欢在广场上散步。

有一次在小 A 散步的时候，由于思考得过于投入，他不小心撞在了电线杆上。

于是就有了这道题目（当然是假的）。

description:
小 A 和 好友小 Y 站在一个平面上，他们的初始坐标分别是 $(Ax_0,Ay_0)$ 和 $(Bx_0,By_0)$。

当然，站着实在是太无聊了，所以他们会不停地移动。

准确来说，小 A 共有 $n$ 次移动，小 Y 共有 $m$ 次移动。

小 A 在第 $At_{i-1}$ 到第 $At_i$ 时刻会从 $(Ax_{i-1},Ay_{i-1})$ **匀速直线运动**到 $(Ax_i,Ay_i)$。

小 Y 在第 $Bt_{i-1}$ 到第 $Bt_i$ 时刻会从 $(Bx_{i-1},By_{i-1})$ **匀速直线运动**到 $(Bx_i,By_i)$。

- $At_0=Bt_0=0$。

小 A 还有 $q$ 次询问： 每次询问给出一个浮点数 $c$ 和一个整数 $f$，请求出他们第 $f$ 次相距 $c$ 的时刻。

- **特殊的，如果他们之间相距 $c$ 的时刻有无数个**，输出 `-2.33`。

- **特殊的，如果 $f$ 大于他们之间相距 $c$ 的次数**，输出 `-4.66`。

- 如果不满足上面两个条件，输出他们第 $f$ 次相距 $c$ 的时刻。

inputFormat:
第一行，三个整数 $n,m,q$ —— $n$ 表示小 A 的移动次数，$m$ 表示小 Y 的移动次数，$q$ 表示询问次数。

第二行，四个两位浮点数 $Ax_0,Ay_0,Bx_0,By_0$ —— 表示小 A 和小 Y 的初始坐标。

接下来 $n$ 行，第 $i$ 行三个两位浮点数 $Ax_i,Ay_i,At_i$ —— 意义见题目描述。

接下来 $m$ 行，第 $i$ 行三个两位浮点数 $Bx_i,By_i,Bt_i$ —— 同上。

接下来 $q$ 行，每行一个两位浮点数 $c$ 和一个整数 $f$ —— 描述一个询问。

outputFormat: 共 $q$ 个浮点数，表示每个询问的答案。

hint:
**「Special Judge」**

**本题使用 Special judge。**

如果你的输出与正确答案的**相对误差或绝对误差**不超过 $10^{-7}$，将会获得该测试点的满分，否则不得分。**建议输出至少 $8$ 位小数**。

请不要输出除了题目要求以外的数字，否则可能获得 UKE。

保证没有答案为 $0$ 的情况。

SPJ 如下：

```
#include "testlib.h"
#define double long double
const double eps=1e-7;
bool Equal(double x,double y){
	return abs(x-y)<=eps||abs((x-y)/y)<=eps;
}
int main(int argc, char* argv[]){
    registerTestlibCmd(argc, argv);
    int n=inf.readInt(),m=inf.readInt(),q=inf.readInt();
    for(int i=1;i<=q;i++){
    	double x=ouf.readDouble(),y=ans.readDouble();
    	if(!Equal(x,y))quitf(_wa,"On line %d the answer is wrong: expected = %.8LF, found = %.8LF",i,y,x);
	}
	quitf(_ok, "The answer is correct.");
	return 0;
}
```

**「数据范围与约定」**

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

Subtask 编号 | $n,m\leq$ | $q\leq$ | 得分
:-: | :-: | :-: | :-:
$1$ | $5\times 10^2$ | $10^3$ | $10$
$2$ | $2\times 10^4$ | $2\times 10^4$ | $20$
$3$ | $4\times 10^4$ | $5\times 10^4$ | $30$
$4$ | $8\times 10^4$ | $3\times 10^5$ | $40$

对于 $100\%$ 的数据，有 $1\leq n,m\leq 8\times 10^4$，$1\leq q\leq 3\times 10^5$，$At_n=Bt_m\leq 6\times 10^4$，$1\leq f\leq m+n$，$0\leq c\leq 3\times 10^4$。

为保证极端数据下的精度，所有坐标的绝对值不大于 $10^4$。

保证 $At_i<At_{i+1}$，$Bt_i<Bt_{i+1}$，一次移动的时间不超过 $6\times 10^2$。**不保证**某次移动没有改变位置。

**请注意精度误差。**

**「时间 & 空间限制」**

对于第 $1$ 个子任务，时限 $\rm{1s}$；其余子任务时限 $\rm{2.5s}$。

对于第 $1$ 个子任务，空限 $\rm{128MB}$；其余子任务空限 $\rm{256MB}$。

**为了卡掉错解，出题人放短了时限，但时限仍在 std 的 $2$ 倍以上。**

**std 轻微卡常，请注意 I/O/常数优化。**

**本题开启自动 O2 优化。**

**「来源」**

[Sweet Round 04](https://www.luogu.com.cn/contest/26414) F。
idea & std：[Alex_Wei](https://www.luogu.com.cn/user/123294)。


title: [IOI2012] rings

description:
在李奥纳多的文献  "Codex  Atlanticus"  中描述了一种早期而复杂的降落伞。李奥纳多的降落伞是一个由布料缝制而成的金字塔型木头结构。

**串接的圆环**

空中自由落体玩家 Adrain Nicholas （爱准尼古拉斯） 在五百年后测试了李奥纳多的设计。在这个测试中，一个现代的轻量结构将李奥纳多的降落伞使用到人体。我们想要使用串接的圆环，这些圆环为缝制的布料提供了钩子。圆环可以很简单地串接在一起，而且每一个圆环可以打开或关闭。串接的圆环可以构成一种特殊的型态叫做"链"（chain）。所谓的"链"指的是一序列串接的圆环，每个圆环可以串接（最多两个）邻居。但是这个序列必须有个起头与结束（这两个圆环只能串接另外一个圆环）。如下图所示。

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

其他种串接型态当然是可能的，因为一个圆环可以串接到3个或更多的圆环。我们说一个圆环是"关键的"如果我们将它打开并移除这个圆环，其他的圆环会形成互无交集的链的集合(或者是没有任何的圆环留下)。

**例子**

请参考下图中的 $7$ 个圆环，其编号由 $0$ 到 $6$。在这个例子中有两个"关键"圆环。其中一个关键圆环是编号 $2$ 的圆环。移除此圆环，剩下的圆环形成三条链 $[1]$, $[0,5,3,4]$ 以及 $[6]$。另外一个关键圆环是编号 $3$ 的圆环，移除此圆环，剩下的圆环形成三条链 $[1,2,0,5]$,$[4]$，以及 $[6]$。如果我们尝试着移除其他的圆环，我们无法获得互无交集的链集合。举例来说，移除编号 $5$ 的圆环之后，虽然可以获得 $[6]$ 这样的一条链，但是 $0,1,2,3$ 以及 $4$ 并没有形成一条链。

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

**任务**

给定一个串接的圆环型态，你的程序必须计算其关键圆环的个数。

inputFormat:
- 第一行，有 $2$ 个整数 $N$，$L$。$N$ 代表有 $N$ 个互无交集的圆环，其编号从 $0$ 到 $N-1$ 作为初始的圆环形态，$L$ 表示操作的个数。

- 第 $2$ 到 $L+1$ 行，每行包含 $1$ 或 $2$ 个整数，表示一个操作。具体如下：

1.`A B` 表示将编号 $A$ 以及编号 $B$ 的圆环串联在一起。保证 $A$ 和 $B$ 不相同。

2.`-1` 输出一行，目前串接圆环的组态中关键圆环的个数。

outputFormat: 对于每项 $2$ 操作，输出一行，表示当时串接圆环的组态中关键圆环的个数。


title: [ROIR 2020 Day1] 超速

description:
**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day1 T2.** ***[Превышение скорости](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day1.pdf)*** ，译者 ShineEternal

超速行驶是一种危险的犯法行为，大大增加了交通事故导致悲惨后果的可能性。不幸的是使用使用雷达和相机控制速度并不能完全解决问题。为了防止这种行为的出现，根据汽车在一段道路上的行驶时间来罚款，可以对超速行为进行限制。

现在有 $n$ 段从 $1\sim n$ 编号的公路。第 $i$ 段公路长 $l_i$ 米，其限速为 $v_i$ 米每秒。超速就要罚款，但是为了体现按劳分配，还要对不同程度的超速设置不同的罚款金额。

具体来说，如果不超速则不收罚款；否则，用 $e$ 表示汽车在这段公路上的**最大速度减去限速**的值：

- 如果 $0<e\leq a_1$，则惩罚为 $f_1$ 个货币单位。

- 如果 $a_1<e\leq a_2$，则惩罚为 $f_2$ 个货币单位。

- ...

- 如果 $a_{m-2}<e\leq a_{m-1}$，则惩罚为 $f_{m-1}$ 个货币单位。

- 如果 $a_{m-1}<e$，则惩罚为 $f_m$ 个货币单位。

目前，有 $q$ 辆车要经过这 $n$ 段道路，每辆车在 $s_i$ 时间到达 $1$ 号路段，在 $t_i$ 时间离开 $n$ 号路段。

你需要计算每辆车在**所有路段中最高**被罚款的金额**至少**是多少。

时间从道路开放起计算，即从 $0$ 开始计算。

inputFormat:
第一行一个正整数 $n$，表示道路段数。

接下来的两行，每行 $n$ 个数，第一行为 $v_i$，第二行为 $l_i$。

第四行为一个正整数 $m$，表示罚款的 $m$ 种不同范围。

接下来的两行，第一行 $m-1$ 个数，为 $a_i$；第二行 $m$ 个数，为 $f_i$。

第七行为一个正整数 $q$，表示共有 $q$ 辆车。

接下来的 $q$ 行，每行两个整数 $s_i,t_i$。

outputFormat:
输出共 $q$ 行。

对于每辆车，输出它最少被罚款的金额。


title: [IOI2012] scrivener

description:
有些人说李奥纳多是一个对于 Johannes  Gutenberg 的崇拜者，Johannes 是一个发明活字印刷的德国铁匠，为了表达尊敬，李奥纳多设计了一台机器被称为小龙虾代书，那是一个非常简单的打字设备。这机器就像一部简单的现代打字机，但只能接受两个指令。一个指令是 输出一个字符，另一个指令是取消最近的指令。小龙虾代书的最大特点就是拥有这个功能强大的取消指令。因为一个取消指令本身也是一个指令，所以也可以被取消。

**说明**

你的任务是作出此小龙虾代书的程序，一开始并无输出任何文字，然后开始接受使用者输入的一连串指令，并可查询目前输出文字中的特定位置的字符。详细说明如下:

- `TypeLetter(L)` —附加一个小写字母L在输出文字的最后，$L$ 可以是 $a,b,\cdots, z$。

- `UndoCommands(U)` — 取消之前的 $U$ 个指令，$U$ 是一个正整数。

- `GetLetter(P)` — 回传在输出文字中位置为 $P$ 的字符，$P$ 是一个非负整数。 输出文字中的第一个字符的位置为 $0$。 （这个查询并不是一个指令，因此会被取消指令忽略。）

三种操作可以依照任何顺序被呼叫 $0$ 次或多次以上。

指令 `UndoCommands(U)` 会依照原本执行的相反顺序来取消前面 $U$ 个指令: 如果被取消的指令是 `TypeLetter(L)`，就会从输出文字最后面移除字母 $L$。如果被取消的指令是 `UndoCommands(X)`，那么将会依照原本执行的顺序重新执行之前被取消的 $X$ 个指令。

**范例**

我们列出一连串可能的指令，以及每次执行指令后的输出文字。

| 操作 | 回传 | 输出文字 |
| :-----------: | :-----------: | :-----------: |
| `TypeLetter(a)` |  | `a` |
| `TypeLetter(b)` |  | `ab` |
| `GetLetter(1)` | `b` | `ab` |
| `TypeLetter(d)` |  | `abd` |
| `UndoCommands(2)` |  | `a` |
| `UndoCommands(1)` |  | `abd` |
| `GetLetter(2)` | `d` | `abd` |
|  `TypeLetter(e)`|  | `abde` |
| `UndoCommands(1)` |  | `abd` |
| `UndoCommands(5)` |  | `ab` |
|`TypeLetter(c)`  |  | `abc` |
| `GetLetter(2)` | `c` | `abc` |
| `UndoCommands(2)` |  | `abd` |
| `GetLetter(2)` | `d` | `abd` |

inputFormat:
- 第 $1$ 行，一个正整数 $N$，表示操作的个数。

- 第 $2$ 到 $N+1$ 行，每行开始有一个大写字母参数。

1. `T` 表示一个 `TypeLetter` 指令，后面接着一个空白和一个小写字母参数。

2. `U` 表示一个 `UndoCommands` 指令，后面接着一个空白和一个整数参数。

3. `P` 表示一个 `GetLetter` 指令，后面接着一个空白和一个整数参数。

outputFormat: 对于每项 `GetLetter` 操作，输出一行，一个回传的字符。

samples:
10
T c
T z
T u
T a
T i
T h
T f
T z
P 3
P 0

samples:
98
T u
T g
T p
T h
T w
P 3
P 0
T d
T d
T r
T v
T z
T w
T h
P 0
T d
T v
T b
P 9
T n
T e
P 0
T s
T i
T a
P 6
T b
T n
T m
T t
T m
T g
T y
T g
P 0
T m
P 18
T r
P 17
T w
T w
T o
T m
T m
P 0
T q
P 5
T t
P 27
P 34
T p
T f
T h
T j
T f
T l
P 3
T f
T q
T h
P 17
T w
T d
T p
T z
P 0
T m
P 10
T o
P 5
P 18
P 7
T q
T z
P 2
T u
P 10
T e
P 6
T s
T t
P 24
T s
P 0
T t
T c
P 4
T j
T o
P 5
T i
P 11
T a
T t
P 58
P 51
P 64
P 12

samples:
h
u
u
z
u
d
u
i
s
u
d
g
m
h
s
u
w
d
i
r
p
w
d
m
u
w
d
h
s
o
a
d

hint: 对于 $100\%$ 的数据，$1 \le N \le 10^6$。参数 $U$ 保证不会超过前面已经输入的指令数目，而且参数 $P$ 一定小于输出文字的长度（也就是输出文字的字母数）。


title: 【模板】广义后缀自动机（广义 SAM）

background: 管理员备注：本题于 2023 年 5 月 4 日加入输出点数的要求。本题在此之前提交的题解均没有输出点数，特此注明。

description:
给定 $n$ 个由小写字母组成的字符串 $s_1,s_2\ldots s_n$，求本质不同的子串个数。（不包含空串）

进一步，设 $Q$ 为能接受 $s_1,s_2,\dots,s_n$ 的所有后缀的最小 DFA，请你输出 $Q$ 的点数。（如果你无法理解这句话，可以认为就是输出 $s_1,s_2,\dots,s_n$ 建成的“广义后缀自动机”的点数）。

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

以下 $n$ 行，每行一个字符串，第 $i$ 行表示字符串 $s_{i-1}$。

outputFormat:
第一行一个正整数，为本质不同的子串个数。

第二行一个正整数，为 $Q$ 的点数。

hint:
数据范围：$1\le n\le 4\cdot 10^5$，$1\le \sum{|s_i|}\le 10^6$。

样例 1 解释：共有 $10$ 个本质不同的子串，它们是：`"a","b","c","aa","ab","ac","ba","ca","bac","caa"`。 DFA 结构略去。

样例 2 解释：共有 $1$ 个本质不同的子串，它们是：`"a"`。DFA 包含一个起始结点 $S$ 和一个结点 $T$，有一条边 $S\to T$，其上字符为 `a`。故总结点数为 2。


title: [JSOI2013] 贪心的导游

description:
南京有一条著名的购物街。购物街嘛，就是一排整齐的商店啦~

导游小 Z 每次都会把游客团带到购物街里走一段，然后选择一个商店进去购物。

小 Z 接待的游客都是购物狂，他们恨不得将店内的商品洗劫一空，也就是说，只要他们能买，就一定会继续买（钱够不够你不用考虑，他们都有信用卡可以透支）。

但是有一点，他们都非常讲究平等、很谦虚，每个人都不能忍受比别人多买什么东西或者少买什么东西，于是他们每个人最后买的商品数量都是一样的。这虽然导致他们没办法每次都把商店搬空，但是每次已经给店家带来一大笔生意了，店家已经非常感谢了！为了表示感谢，店家决定把游客们买完之后剩下来那几件没卖掉的商品就送给导游小 Z 了。

贪心的小 Z 自然希望自己能获赠的商品数量越大越好啦~

现在告诉你这一排共 $n$ 个商店（标号为 $0$ 到 $n-1$）每个商店里的商品总数，每次小 Z 会带一批共 $p$ 个游客的旅游团，到其中 $u$ 号商店和 $v$ 号商店之间逛一逛，请你帮小 Z 在所逛的商店区间内选择一个，告诉小 Z 他最多能获赠多少件商品。

inputFormat:
第一行，包含两个整数 $n,m$，分别表示商店个数和小 Z 带来的旅游团个数。

接下来一行，包含 $n$ 个整数 $a_i$，表示第 $i$ 个商店的商品总数。

接下来 $m$ 行，每行三个整数 $u,v,p$，表示这个旅游团逛 $u$ 号商店和 $v$ 号商店之间的商店（包含 $u$ 和 $v$），且这个旅游团的人数为 $p$。

outputFormat: 共输出 $m$ 行，每行一个整数，第 $i$ 行输出第 $i$ 个旅游团购物后，小 Z 最多能获赠的商品数量。

hint:
### 样例解释

第一个旅游团， $2$ 个人， $0$ 号商店到 $1$ 号商店的区间。若去 $1$ 号商店，共 $2$ 件商品，每人买 $1$ 件，剩 $0$ 件。若去 $2$ 号商店，共 $4$ 件商品，每人买 $2$ 件，剩 $0$ 件。所以，小 Z 最多获赠 $0$ 件。

第二个旅游团， $3$ 个人，小 Z 选择带他们去 $4$ 号商店，共 $8$ 件商品，每人买 $2$ 件商品（因为每人 $3$ 件不够），剩下 $2$ 件，小 Z 最多获赠就是 $2$ 件。 可以验证去其它商店小 Z 最多获赠的商品不会达到 $2$ 件。

### 数据范围

对于 $100\%$ 的数据，$1 \leq n\leq 10^6,1 \leq m\leq 5\times 10^4,0\leq a_i\leq 10^3,2\leq p\leq 10^3,0\leq u,v\leq n-1$。


title: [IOI2016] shortcut

description:
Pavel 有一个非常简单的铁路玩具。 它有一条含有 $n$ 个车站的主干线并且连续编号为 $0$ 到 $n-1$。车站 $0$ 和车站 $n-1$ 就在这条主干线的两端。其中车站 $i$ 和车站 $i+1$ 之间的距离为 $l_i$ 厘米（$ 0 \le i<n-1$）。

除了这条主干线之外，这个铁路也许会有些支线。每条支线都是由主干线中的一个车站和主干线 外的一个新车站之间的一条新铁路构成（这些新的车站不会被编号）。在主干线中的一个车站最多只能有一条支线。以主干线中的车站 $i$ 为起点的支线的长度为 $d_i$ 厘米。我们用 $d_i=0$ 来表示车站 $i$ 没有支线。

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

Pavel 现正规划一条快捷方式：一条在主干线中两个不相同的车站之间（它们可能相邻）的快速干线。这条快速干线无论是连接哪两个车站，它的长度都将会恰好是 $c$ 厘米。

铁路中的每一段，包括那条新的快速干线，都能够双向行驶。任意两个车站的距离就是它们之间沿着铁路由一个车站到另一个车站之间最短路径的长度。所有车站组合中最大的距离就叫做整个铁路网络的直径。换句话说，存在一个最小值 $t$ 使任意两个车站之间的距离都不会超过 $t$。

Pavel 就是想建造一条快速干线，使得有了这条快速干线后新的铁路网络的直径能达到最小值。

### 样例一

```
4 10
10 20 20
0 40 0 30
```

最优解是在车站 $1$ 和车站 $3$ 之间建造一条快速干线，如下图所示。

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

这个新铁路网络的直径是 $80$ 厘米，所以应该输出数值 $80$。

### 样例二

```
9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0
```

最优解是连接车站 $2$ 和车站 $7$，这个解的直径是 $110$。

### 样例三

```
4 1
2 2 2
1 10 10 1
```
最优解是连接车站 $1$ 和车站 $2$，这样直径将被缩短到 $21$。

### 样例四

```
3 3
1 1
1 1 1
```
在任意两个车站中建立长度为 $3$ 的快速干线都不会改进整个铁路网络的直径，因此其直径仍为初始值 $4$。

inputFormat:
- 第一行：两个整数 $n$ 和 $c$，

- 第二行：整数 $l_0,l_1,\cdots,l_{n-2}$，

- 第三行：整数 $d_0,d_1,\cdots,d_{n-1}$。

outputFormat: 共一行，加入新快速干线后铁路网络直径的最小可能值。


title: [IOI2016] railroad

description:
Anna 在一个游乐园工作。她负责建造一个新的过山车铁路。她已经设计了影响过山车速度的 $n$ 个特殊的路段（方便起见标记为 $0$ 到 $n-1$）。现在 Anna 必须要把这些特殊的路段放在一起并提出一个过山车的最后设计。为了简化问题，你可以假设过山车的长度为零。

对于 $0$ 和 $n-1$ 之间的每个 $i$，这个特殊的路段 $i$ 具有如下两个性质：

- 当进入这个路段时，有一个速度限制：过山车的速度必须小于或等于 $s_i$ $\text{km/h}$（每小时千米）。

- 当离开这个路段时，过山车的速度刚好是 $t_i$ $\text{km/h}$，不管过山车进入该路段时的速度如何。

最后完成的过山车设计是一个以某种顺序包含这 $n$ 个特殊路段的单一铁路线。这 $n$ 个路段中的每一个应当被使用刚好一次。连续的路段之前用铁轨来连接。Anna 应该选择这 $n$ 个路段的顺序，然后确定每段铁轨的长度。铁轨的长度以米来衡量，可以是任意的非负整数（可以为零）。

两个特殊路段之间的每 $1$ 米铁轨可以将过山车的速度减慢 $1$ $\text{km/h}$。在这个过山车铁路的起点，过山车按照 Anna 选择的顺序进入第一个特殊路段时的速度是 $1$ $\text{km/h}$。

最后的设计还必须满足以下要求：

- 过山车在进入这些特殊路段时不能违反任一个速度限制。

- 过山车的速度在任意时刻为正。

你的任务是找出这些路段之间铁轨的最小可能总长度（这些路段之间铁轨总长度的最小值）。如果 $m=0$ 你只需要检查是否存在一个有效的过山车设计，使得每段铁轨的长度为零。

**举例**

```
4 1
1 7
4 3
5 8
6 6
```
在这个样例中有 $4$ 个特殊的路段。最好的解是按照 $0,3,1,2$ 的顺序构造，连接这些路段的铁轨长度分别是 $1,2,0$。下面给出过山车沿铁路铁轨的行驶方式：

- 最初过山车的速度是 $1$ km/h。

- 过山车由进入 $0$ 号路段开始行进。

- 过山车以 $7$ $\text{km/h}$ 的速度离开 00 号路段。

- 然后有一段长度为 $1$ $\text{m}$ 的铁轨。过山车在到达这段铁轨的末端时速度为 $6$ $\text{km/h}$。

- 过山车以 $6$ $\text{km/h}$ 的速度进入 $3$ 号路段并以相同的速度离开该路段。

- 在离开 $3$ 号路段后，过山车走过一段 $2$ $\text{m}$ 长的铁轨。速度降至 $4$ $\text{km/h}$。

- 过山车以 $4$ $\text{km/h}$ 的速度进入 $1$ 号路段，并且以 $3$ $\text{km/h}$ 的速度离开该路段。

- 离开 $1$ 号路段后，过山车立即进入 $2$ 号路段。

- 过山车离开 $2$ 号路段。其最终速度是 $8$ $\text{km/h}$。

路段之间的铁轨总长度：$1+2+0=3$。

inputFormat:
- 第一行：两个整数 $n$ 和 $m$，其中 $m=0$ 表示当答案不为 $0$ 时，你可以返回任意正整数，$m=1$ 表示你需要返回正确答案。

- 接下来 $n$ 行：第 $i$ 行的两个整数表示 $s_{i-1}$ 和 $t_{i-1}$。

outputFormat: 共一行，所有铁轨的最小可能总长度。（当 $m=0$ 时，如果存在一个有效的过山车设计使得每段铁轨的长度均为零，则函数返回零，如果上述设计不存在，则输出任意的正整数）。


title: [集训队作业2018] 后缀树节点数

background: 来源：陈江伦 2018 候选队论文题

description:
给定一个长度为 $n$ 的字符串 $P$，有 $m$ 次询问，每次给定两个参数 $l$ , $r$，询问子串 $P[l,r]$ 所构成的后缀树的结点数。

如果你不了解后缀树，你也可以理解为对 $[l,r]$ 的反串建后缀自动机。

注意在本题中，后缀树的根节点不计入答案。

inputFormat:
本题中用数字来表示字符串，不同的数字代表不同的字符，相同的数字代表相同的字符，数字的范围在 $[0,n]$ 之间。

第一行两个正整数 $n$ 和 $m$，表示字符串长度和询问个数。
第二行 $n$ 个用空格隔开的非负整数，表示这个字符串。
接下来 $m$ 行，每行两个正整数 $l,r$，表示询问子串 $[l,r]$ 的后缀树的结点数。

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

hint:
对于 $30\%$ 的数据：$n,m\le 3\times 10^3$；

对于 $100\%$ 的数据满足：$n\le 10^5$，$m\le 3\times 10^5$，字符串的每个数字 $\le n$。


title: [IOI2016] molecules

description:
彼得在一家公司工作，这家公司已经制造了一台检测分子的机器。每个分子的重量都是正整数。这台机器的检测范围是 $[l,u]$，这里 $l$ 和 $u$ 都是正整数。这台机器能够检测一个分子集合当且仅当这个集合包含了一个子集，这个子集的分子的重量属于机器的检测范围。

考虑 $n$ 个分子，重量记为 $w_0,\cdots,w_{n-1}$。如果存在一个下标的集合（并且该集合中的下标都不相同）$I=\{i_1,\cdots,i_m\}$ 使得 $l\le w_{i_1}+\cdots+w_{i_m}\le u$，那么检测就会成功。

由于机器的细节，$l$ 和 $u$ 之间的差距要保证会大于等于最重分子和最轻分子之间的差距，即 $u-l \ge w_{max}-w_{min}$，其中 $w_{max}=\max(w_0,\cdots,w_{n-1})$，$w_{min}=\min(w_0,\cdots,w_{n-1})$

你的任务是写一个程序，该程序能找到一个子集，使得该子集的总重量属于检测范围，或者判定没有这样的子集存在。

### 样例一

 ```
  4 15 17
  6 8 8 7
 ```

这个例子当中，我们有四个分子，重量分别是 $6,8,8$ 和 $7$。这台机器可以检测子集总重量在 $15$ 到 $17$ 之间（包含 $15$ 和 $17$）的子集。注意，$17-15 \ge 8-6$。分子 $1$ 和分子 $3$ 的重量之和为 $w_1+w_3=8+7=15$, 所以应该输出
```
2
1 3
```
其他可能正确的答案有
```
2
1 2
```
（$w_1+w_2=8+8=16$）

和
```
2
2 3
```
（$w_2+w_3=8+7=15$）。

### 样例二

```
4 14 15
5 5 6 6
```

这个例子当中，我们有四个分子，重量分别为 $5,5,6$ 和 $6$，我们要寻找一个子集，其总重量介于 $14$ 和 $15$ 之间（包含 $14$ 和 $15$）。请注意，$15-14 \ge 6-5$。因为不存在总重量介于 $14$ 和 $15$ 之间的子集，所以输出 `0`。

inputFormat:
- 第一行：整数 $n,l$ 和 $u$。

- 第二行：$n$ 个整数：$w_0,\cdots,w_{n-1}$。

outputFormat:
如果有满足条件的子集：

- 第一行，输出该子集大小 $x$。

- 第二行，$x$ 个整数，符合要求的子集中的分子的下标。

如果没有，输出 `0`。


title: 「JYLOI Round 1」常规

description:
LS 制定了 $n$ 项常规，其中第 $i$ 项常规制定的时间是 $a_i$。

对于第 $i$ 项常规，从第 $i$ 项常规的制定时间 $a_i$ 后的每 $k$ 秒，他都要做一次第 $i$ 项常规，他做一次常规的时间可以忽略不计。

现在 LS 想给你 $m$ 个询问，每个询问用一个区间 $[l_i, r_i]$ 来表示，问你在第 $l_i$ 到 $r_i$ 秒，他一共做了多少次常规。

inputFormat:
输入的第一行是一个为 0 或 1 的整数 $type$，在接下来会用到。

对于 $type = 0$ 的情况，接下来有一行三个正整数 $n$、$m$、$k$，含义如题所述。

接下来有一行 $n$ 个正整数，这一行中的第 $i$ 个正整数表示的是 $a_i$，$a_i$ 的含义如题所述。

接下来有 $m$ 行，第 $i$ 行表示的是第 $i$ 个询问是一个区间 $[l_i, r_i]$，$l_i$ 和 $r_i$ 的含义如题所述。对于 $type = 0$ 的所有询问，我们都没有进行加密。

对于 $type=1$ 的情况，接下来有一行四个正整数 $n$、$m$、$k$ 和 $mod$，$n$、$m$、$k$ 的含义如题所述，其中 $mod$ 是一个会在下面用到的参数。

接下来有一行 $n$ 个正整数，这一行中的第 $i$ 个正整数表示的是 $a_i$，$a_i$ 的含义如题所述。

接下来有 $m$ 行，这 $m$ 行中的第 $i$ 行有两个正整数 $l_i$ 和 $r_i$，表示第 $i$ 个询问是一个区间 $[l_i, r_i]$，$l_i$ 和 $r_i$ 的含义如题所述。特别地，我们加密了第 2 至第 $m$ 个询问，对于第 $i(2 \leq i \leq m)$ 个询问，解密后的：
$$l_i = \min((l_i + \text{lastans} - 1) \;\text{mod}\; mod + 1, (r_i + \text{lastans} - 1) \;\text{mod}\; mod + 1)$$

$$r_i=\max((l_i + \text{lastans} - 1) \;\text{mod}\; mod + 1, (r_i + \text{lastans} - 1) \;\text{mod}\; mod + 1)$$

其中 $\text{lastans}$ 是第 $(i - 1)$ 个询问的答案，对于第 2 到第 $m$ 个询问，你的程序需要回答解密后的询问所对应的答案。

**特别地，第一个询问没有被加密。**

outputFormat: 输出共有 $m$ 行，对于每个解密后的询问输出一行，输出中的第 $i$ 行表示的是第 $i$ 个询问的答案。

hint:
### 样例 2 说明

解密后的询问分别为 [1, 5]、[4, 7]、[8, 10]、[9, 10]、[8, 8]、[12, 12]、[21, 31]、[28, 48]、[36, 65]、[55, 80]，因此可以得出答案。

____________

### 数据范围

对于 $100\%$ 的数据，满足 $type \in \{0, 1\}; 1 \leq n, m \leq 10^5; 0 \leq l_i \leq r_i \leq 10^9; 0 \leq a_i \leq 10^9; 1 \leq k, mod \leq 10^9$。

子任务 1（有 10 个测试点，每个测试点 1 分，共 10 分）：$type = 0; n, m, k \leq 10^3; r_i \leq 10^3$。

子任务 2（有 10 个测试点，每个测试点 1 分，共 10 分）：$type = 0; n, m \leq 10^3$。

子任务 3（有 2 个测试点，每个测试点 5 分，共 10 分）：$type = 0, r_i \leq 10^5,k = 1$。

子任务 4（共 20 分）：$type = 0, k \leq 10^5, r_i \leq 10^5$。

子任务 5（共 30 分）：$type = 0$。

子任务 6（共 20 分）：无特殊限制。

对于子任务 4、5、6，分别捆绑计分（即你需要通过一个子任务内的所有测试点才能够拿到这个子任务的分数），本题总共 50 个测试点、100 分。

## 题目来源

「JYLOI Round 1」 D

Idea / Solution / Data ：abcdeffa


title: [集训队作业2019] 青春猪头少年不会梦到兔女郎学姐

background: 来源：2019 集训队作业 Round4

description:
若干个正整数排成一个序列，其中数字 $i$ 的出现次数为 $c_i$，对于每一个这样的序列，定义他的权值如下：

把这个序列首尾相接放在一个圆上，把这些数字分成若干相邻的段，使得每段都是在圆上相邻的数字，任意两段没有公共的元素，每一段中的数字都相同，相邻段中的数字不同，则这个序列的权值定义为所有段的长度之积。

求所有的序列的权值和对 $998244353$ 取模。

注：虽然计算序列的权值的时候是圆排列，但互为循环排列的不同序列仍然被认为是不同的，如 $(1,2,1,2)$ 和 $(2,1,2,1)$ 被认为是不同的序列。

inputFormat:
若干行，第一行一个正整数 $n$ ，表示数字种类数。

第二行 $n$ 个正整数 $c_i$，表示第 $i$ 个数字的出现次数。

outputFormat: 一行，表示所有出现次数符合条件的序列的权值和对 $998244353$ 取模的值。


title: 【模板】Matrix-Tree 定理

description:
给定一张 $n$ 个结点 $m$ 条边的带权图（可能为无向图，可能为有向图）。

定义其一个生成树 $T$ 的权值为 $T$ 中所有边权的乘积。

求其所有不同生成树的权值之和，对 $10^9+7$ 取模。

---

注意：

1. 本题中，有向图的生成树指的是 **以 $1$ 为根的外向树**；

2. 两棵生成树 $T_1,T_2$ 不同，当且仅当存在存在一条边 $e$，满足 $e\in T_1,\ \ e\notin T_2$。

inputFormat:
第一行：三个整数 $n,m,t$，分别表示图的结点数量，边的数量和图的类型（$t=0$ 时为无向图，$t=1$ 时为有向图）。

接下来 $m$ 行：每行三个整数 $u,v,w$。

如果 $t=0$，表示 $u,v$ 之间有一条权值为 $w$ 的无向边；

如果 $t=1$，表示从 $u$ 到 $v$ 有一条权值为 $w$ 的有向边。

outputFormat: 第一行：一个整数 $ans$，表示给定的图的生成树权值和对 $10^9+7$ 取模的结果。

hint:
【样例 $1$ 解释】

样例 $1$ 中的无向图如左图所示：

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

右图为其一个权值为 $3\times 1\times 2\times 3=18$ 的生成树的例子。

---

【样例 $2$ 解释】

样例 $2$ 中的有向图如左图所示：

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

右图为其一个权值为 $1\times 1\times 1\times 2=2$ 的生成树（以 $1$ 为根的外向树）的例子。

---

【数据范围】

对于 $100\%$ 的数据：$1\leq n\leq 300,\ \ 1\leq m\leq 10^5,\ \ t\in \{0,1\},\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^9$。

对于测试点 $1,2,3,4,5,6$，$t=0$；对于测试点 $7,8,9,10,11$，$t=1$。

图中 **可能** 存在重边和自环，重边算作多条边。


title: [USACO07NOV] Best Cow Line S

background: *本题和 [2007 年 12 月月赛金组同名题目](/problem/P2870) 在题意上一致，唯一的差别是数据范围。*

description:
Farmer John 打算带领 $N$（$1 \leq N \leq 2\,000$）头奶牛参加一年一度的”全美农场主大奖赛“。在这场比赛中，每个参赛者必须让他的奶牛排成一列，然后带领这些奶牛从裁判面前依此走过。

今年，竞赛委员会在接受报名时，采用了一种新的登记规则：取每头奶牛名字的首字母，按照它们在队伍中的次序排成一列。将所有队伍的名字按字典序升序排序，从而得到出场顺序。

FJ 由于事务繁忙，他希望能够尽早出场。因此他决定重排队列。

他的调整方式是这样的：每次，他从原队列的首端或尾端牵出一头奶牛，将她安排到新队列尾部。重复这一操作直到所有奶牛都插入新队列为止。

现在请你帮 FJ 算出按照上面这种方法能排出的字典序最小的队列。

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

接下来 $N$ 行每行一个大写字母，表示初始队列。

outputFormat:
输出一个长度为 $N$ 的字符串，表示可能的最小字典序队列。

每输出 $80$ 个字母需要一个换行。


title: [USACO20FEB] Swapity Swapity Swap S

description:
Farmer John 的 $N$ 头奶牛（$1\leq N\leq 10^5$）站成一排。对于每一个 $1\leq i\leq N$，从左往右数第 $i$ 头奶牛的编号为 $i$。

Farmer John 想到了一个新的奶牛晨练方案。他给奶牛们 $M$ 对整数 $(L_1,R_1)\ldots (L_M,R_M)$，其中 $1\leq M\leq 100$。他让她们重复以下包含 $M$ 个步骤的过程 $K$（$1\leq K\leq 10^9$）次：

对于从 $1$ 到 $M$ 的每一个 $i$：
- 当前从左往右数在位置 $L_i\ldots R_i$ 的奶牛序列反转她们的顺序。
- 当奶牛们重复这一过程 $K$ 次后，请对每一个 $1\leq i\leq N$ 输出从左往右数第 $i$ 头奶牛的编号。

inputFormat: 输入的第一行包含 $N$，$M$ 和 $K$。对于每一个 $1\leq i\leq M$，第 $i+1$ 行包含 $L_i$ 和 $R_i$，均为范围在 $1\ldots N$ 内的整数，其中 $L_i<R_i$。

outputFormat: 在第 $i$ 行输出指令序列执行了 $K$ 次后奶牛序列中从左往右数第 $i$ 个元素的编号。

hint:
#### 样例解释：
初始时，奶牛们的顺序从左往右为 [$1,2,3,4,5,6,7$]。在这一过程的第一步过后，顺序变为 [$1,5,4,3,2,6,7$]。在这一过程的第二步过后，顺序变为 [$1,5,7,6,2,3,4$]。再重复这两个步骤各一次可以得到样例的输出。

#### 子任务：
- 测试点 $2$ 满足 $N=K=100$。
- 测试点 $3$-$5$ 满足 $K\leq 10^3$。
- 测试点 $6$-$10$ 没有额外限制。


title: [USACO20FEB] Timeline G

description:
Bessie 在过去的 $M$ 天内参加了 $N$ 次挤奶。但她已经忘了她每次挤奶是在哪个时候了。

对于第 $i$ 次挤奶，Bessie 记得它不早于第 $S_i$ 天进行。另外，她还有 $C$ 条记忆，每条记忆形如一个三元组 $(a,b,x)$，含义是第 $b$ 次挤奶在第 $a$ 次挤奶结束至少 $x$ 天后进行。

现在请你帮 Bessie 算出在满足所有条件的前提下，每次挤奶的最早日期。

保证 Bessie 的记忆没有错误，这意味着一定存在一种合法的方案，使得：

- 第 $i$ 次挤奶不早于第 $S_i$ 天进行，且不晚于第 $M$ 天进行；
- 所有的记忆都得到满足；

inputFormat:
第一行三个整数 $N,M,C$。保证 $1 \leq N,C \leq 10^5$，$2 \leq M \leq 10^9$。

接下来一行包含 $N$ 个整数 $S_1, S_2 , \ldots, S_n$，保证 $\forall 1 \leq i \leq n$，都满足 $1 \leq S_i \leq M$。

下面 $C$ 行每行三个整数 $a,b,x$，描述一条记忆。保证 $a \neq b$，且 $1 \leq x \leq M$。

outputFormat: 输出 $N$ 行，每行一个整数，第 $i$ 行的数表示第 $i$ 次挤奶的最早日期。

hint:
- 测试点 $2 \sim 4$ 满足 $N,C \leq 10^3$。
- 测试点 $5 \sim 10$ 没有特殊限制。


title: [USACO20FEB] Triangles S

description:
Farmer John 想要给他的奶牛们建造一个三角形牧场。

有 $N$（$3\leq N\leq 10^5$）个栅栏柱子分别位于农场的二维平面上不同的点 $(X_1,Y_1)\ldots (X_N,Y_N)$。他可以选择其中三个点组成三角形牧场，只要三角形有一条边与 $x$ 轴平行，且有另一条边与 $y$ 轴平行。

FJ 可以组成的所有可能的牧场的面积之和等于多少？

inputFormat:
第一行包含 $N$。

以下 $N$ 行每行包含两个整数 $X_i$ 和 $Y_i$，均在范围 $−10^4\ldots 10^4$ 之内，描述一个栅栏柱子的位置。

outputFormat: 由于面积之和不一定为整数且可能非常大，输出面积之和的**两倍**模 $10^9+7$ 的余数。


title: [USACO20FEB] Help Yourself G

description:
在一个数轴上有 $N$ 条线段，第 $i$ 条线段覆盖了从 $l_i$ 到 $r_i$ 的所有实数（包含 $l_i$ 和 $r_i$）。

定义若干条线段的**并**为一个包含了所有被至少一个线段覆盖的点的集合。

定义若干条线段的**复杂度**为这些线段的并形成的连通块的数目。

现在 Bessie 想要求出给定 $N$ 条线段的所有子集（共有 $2^N$ 个）的复杂度之和对 $10^9+7$ 取模的结果。

你也许猜到了，你需要帮 Bessie 解决这个问题。但不幸的是，你猜错了！在这道题中你就是 Bessie，而且没有人来帮助你。一切就靠你自己了！

inputFormat:
第一行一个整数 $N$（$1 \leq N \leq 10^5$）。

接下来 $N$ 行，每行两个整数 $l_i,r_i$，描述一条线段。保证 $1 \leq l_i \lt r_i \leq 2N$，且任意两个端点都不在同一位置上。

outputFormat: 输出所求答案对 $10^9+7$ 取模的结果。


title: [USACO20FEB] Clock Tree S

description:
Farmer John 的新牛棚的设计十分奇怪：它由编号为 $1\ldots N$ 的 $N$ 间房间（$2\leq N\leq 2\,500$），以及 $N−1$ 条走廊组成。每条走廊连接两间房间，使得每间房间都可以沿着一些走廊到达任意其他房间。

牛棚里的每间房间都装有一个在表盘上印有标准的整数 $1\ldots 12$ 的圆形时钟。然而，这些时钟只有一根指针，并且总是直接指向表盘上的某个数字（它从不指向两个数字之间）。

奶牛 Bessie 想要同步牛棚中的所有时钟，使它们都指向整数 $12$。然而，她头脑稍有些简单，当她在牛棚里行走的时候，每次她进入一间房间，她将房间里的时钟的指针向后拨动一个位置。例如，如果原来时钟指向 $5$，现在它会指向 $6$，如果原来时钟指向 $12$，现在它会指向 $1$。如果 Bessie 进入同一间房间多次，她每次进入都会拨动这间房间的时钟。

请求出 Bessie 可能的出发房间数量，使得她可以在牛棚中走动并使所有时钟指向 $12$。注意 Bessie 并不拨动她出发房间的时钟，但任意时刻她再次进入的时候会拨动它。时钟不会自己走动；时钟只会在 Bessie 进入时被拨动。此外，Bessie 一旦进入了一条走廊，她必须到达走廊的另一端（不允许走到一半折回原来的房间）。

inputFormat: 输入的第一行包含 $N$。下一行包含 $N$ 个整数，均在范围 $1\ldots 12$ 之内，表示每间房间初始时的时钟设置。以下 $N−1$ 行每行用两个整数 $a$ 和 $b$ 描述了一条走廊，两数均在范围 $1\ldots N$ 之内，为该走廊连接的两间房间的编号。

outputFormat: 输出出发房间的数量，使得 Bessie 有可能使所有时钟指向 $12$。

hint:
#### 样例解释：
在这个例子中，当且仅当 Bessie 从房间 $2$ 出发时她可以使所有房间的时钟指向 $12$（比如，移动到房间 $1$，$2$，$3$，$2$，最后到 $4$）。

#### 子任务：
- 测试点 $2$-$7$ 满足 $N\leq 100$。
- 测试点 $8$-$15$ 没有额外限制。


title: [USACO20FEB] Delegation G

description:
Farmer John 有 $N$ 个牧场，这些牧场通过 $N-1$ 条道路连接，形成了一个树形结构。

但在 28 年的经营后（译者注：USACO 创办于 1992 年），FJ 觉得处理树上问题非常辣手，他认为一条链上的问题更加简单。

因此他决定将整棵树划分为若干条链，将每一条链的管理权授予一位工人。为了避免可能的争端，他希望所有链的长度均相同。

FJ 现在想知道，对于每一个满足 $1 \leq K \leq N-1$ 的 $K$，是否存在一种划分方案，使得整棵树被划分成若干条链，且每条链的长度都**恰好**是 $K$。

inputFormat:
第一行一个整数 $N$（$1 \leq N \leq 10^5$）。

接下来 $N-1$ 行，每行两个整数 $u,v$（$1 \leq u,v \leq N$），描述一条连接 $u,v$ 的道路。

outputFormat: 输出一个长度 $N-1$ 的 0/1 串。第 $i$ 位的值为 $1$ 当且仅当存在一种划分方案，使得整棵树被划分成若干条链，且每条链的长度都恰好是 $i$，否则第 $i$ 位的值为 $0$。


title: [USACO20FEB] Help Yourself P

description:
在一个数轴上有 $N$ 条线段，第 $i$ 条线段覆盖了从 $l_i$ 到 $r_i$ 的所有实数（包含 $l_i$ 和 $r_i$）。

定义若干条线段的**并**为一个包含了所有被至少一个线段覆盖的点的集合。

定义若干条线段的**复杂度**为这些线段的并形成的连通块的数目的 $K$ 次方。

现在 Bessie 想要求出给定 $N$ 条线段的所有子集（共有 $2^N$ 个）的复杂度之和对 $10^9+7$ 取模的结果。

你也许猜到了，你需要帮 Bessie 解决这个问题。但不幸的是，你猜错了！在这道题中你就是 Bessie，而且没有人来帮助你。一切就靠你自己了！

inputFormat:
第一行两个整数 $N$，$K$（$1 \leq N \leq 10^5$。$2 \leq K \leq 10$）。

接下来 $N$ 行，每行两个整数 $l_i,r_i$，描述一条线段。保证 $1 \leq l_i \lt r_i \leq 2N$，且任意两个端点都不在同一位置上。

outputFormat: 输出所求答案对 $10^9+7$ 取模的结果。


title: [USACO20FEB] Equilateral Triangles P

description:
Farmer John 的农场可以用一个 $N \times N$ 的方阵（$1 \leq N \leq 300$）。对于方阵内的每个格子，如果这个格子有奶牛，就用 `*` 表示，否则用 `.` 表示。

FJ 相信他的牧场的美丽程度正比于两两距离相等的奶牛三元组的数量。也就是说，她们组成一个等边三角形。不幸的是，直到最近 FJ 才发现，由于他的奶牛都处在整数坐标位置，如果使用欧几里得距离进行计算，不可能存在美丽的奶牛三元组！于是，FJ 决定改用“曼哈顿”距离。形式化地说，两点 $(x_0,y_0)$ 和 $(x_1,y_1)$ 的曼哈顿距离等于 $|x_0-x_1|+|y_0-y_1|$。

给定表示奶牛位置的方阵，计算等边三角形的数量。

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

接下来 $N$ 行，每行一个长度为 $N$ 的字符串，第 $i$ 行的第 $j$ 个字符表示位置 $(i,j)$ 上是否有奶牛。

outputFormat: 输出一个整数，为所求的答案。可以证明答案可以用 32 位有符号整数型存储。

hint:
### 样例解释

有三头奶牛，并且她们组成了一个等边三角形，因为每对奶牛之间的曼哈顿距离都等于二。

### 子任务

- 对于测试点 $T$（$T \in [2,11]$），满足 $N=25T$；
- 对于测试点 $T$（$T \in [12,15]$），满足 $N=300$。


title: [USACO20FEB] Delegation P

description:
Farmer John 有 $N$ 个牧场，这些牧场通过 $N-1$ 条道路连接，形成了一个树形结构。

但在 28 年的经营后（译者注：USACO 创办于 1992 年），FJ 觉得处理树上问题非常辣手，他认为一条链上的问题更加简单。

因此他决定将整棵树划分为若干条链，将每一条链的管理权授予一位工人。他不关心链的数量，却关心链的长度，他希望划分的链都尽可能长，从而不会有人用效率低下的算法蒙混过关。

FJ 现在想知道最大的正整数 $K$，使得整棵树被划分成若干条链，且每条链的长度都**至少**是 $K$。

inputFormat:
第一行一个整数 $N$（$1 \leq N \leq 10^5$）。

接下来 $N$ 行，每行两个整数 $u,v$（$1 \leq u,v \leq N$），描述一条连接 $u,v$ 的道路。

outputFormat: 输出 $K$。

hint:
### 样例解释

一种划分方案如下：

$$
2-1-6-7-8, 3-1-4-5
$$

### 子任务

- 测试点 $2 \sim 4$ 满足**最多**有一个点的度数大于 $2$。
- 测试点 $5 \sim 8$ 满足 $N \leq 10^3$。
- 测试点 $9 \sim 15$ 没有特殊限制。


title: 【模板】最小斯坦纳树

description:
给定一个包含 $n$ 个结点和 $m$ 条带权边的无向连通图 $G=(V,E)$。

再给定包含 $k$ 个结点的点集 $S$，选出 $G$ 的子图 $G'=(V',E')$，使得：

1. $S\subseteq V'$；

2. $G'$ 为连通图；

3. $E'$ 中所有边的权值和最小。

你只需要求出 $E'$ 中所有边的权值和。

inputFormat:
第一行：三个整数 $n,m,k$，表示 $G$ 的结点数、边数和 $S$ 的大小。

接下来 $m$ 行：每行三个整数 $u,v,w$，表示编号为 $u,v$ 的点之间有一条权值为 $w$ 的无向边。

接下来一行：$k$ 个互不相同的正整数，表示 $S$ 的元素。

outputFormat: 第一行：一个整数，表示 $E'$ 中边权和的最小值。

hint:
【样例解释】

样例中给出的图如下图所示，红色点为 $S$ 中的元素，红色边为 $E'$ 的元素，此时 $E'$ 中所有边的权值和为 $2+2+3+4=11$，达到最小值。

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

---

【数据范围】

对于 $100\%$ 的数据，$1\leq n\leq 100,\ \ 1\leq m\leq 500,\ \ 1\leq k\leq 10,\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^6$。

保证给出的无向图连通，但 **可能** 存在重边和自环。


title: 【模板】后缀平衡树

background:
"后缀平衡树"这个名字正确性存疑，由于 clj 给的"重量平衡树"定义有歧义。

字符串我也不会，所以也没去查证。

description:
给你一个字符串 `init`，要求你支持三个操作：

1. 在当前字符串的后面插入若干个字符。

2. 在当前字符串的后面删除若干个字符。

3. 询问字符串 $s$ 在当前字符串中出现了几次（作为连续子串）？

你必须在线支持这些操作。

inputFormat:
第一行一个数 $q$ 表示操作个数。

第二行一个字符串表示初始字符串 `init`。

接下来 $q$ 行，每行 $2$ 个字符串 `Type Str`。

Type是 `ADD` 的话表示在后面插入。

Type是 `DEL` 的话表示在后面删除。

Type是 `QUERY` 的话表示询问某字符串在当前字符串中出现了几次。

为了体现在线操作，你需要维护一个变量 `mask`，初始值为 $0$。

读入串 `Str` 之后，使用这个过程将之解码成真正询问的串 `TrueStr`。

询问的时候，对 `TrueStr` 询问后输出一行答案 `Result`。

然后 `mask = mask xor Result`

插入的时候，将 `TrueStr` 插到当前字符串后面即可。

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

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

hint:
数据字符串变化长度以及初始长度和 $ \le 8 \times 10^5$，询问次数 $\le 10^5$，询问总长度 $\le 3 \times 10^6$。

字符集为大写字母，注意 `ADD` 和 `QUERY` 操作的字符串都需要解压。


title: 『JROI-1』  向量

background:
前言：虽然 SCR 已经并入了 JROI，但作为 JROI 的负责人，我还是想要感谢一下 SCR 出题组的**无私**奉献。出于对出题人的敬意。我们不会在题目背景故事上做大的改动，只会添加**小部分上下衔接**的语句。

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

蒟蒻火锅正在煮，自然要打一盘游戏了。

小 L 是个喜欢打第五的初中生。这天他刚自学完了向量的基本运算，正在打第五时，他看着自己画出来的长短、方向各异的机关墙（他在玩疯眼），有了一个奇妙的想法。

description:
小 L 有 $n$ 个向量 $\overrightarrow{a_1},\overrightarrow{a_2}\ldots\overrightarrow{a_n}$，他希望你能够帮他回答下面两个问题。

+ 对于给定的 $l,r$，求出

$$\sum\limits_{i=l}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\cdot\overrightarrow{a_j}$$

+ 对于给定的 $l,r$，求出

$$\sum\limits_{i=l}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\oplus\overrightarrow{a_j}$$

随着时间的推移，这些向量也会不断发生变化，小 L 希望你在发生变化后仍然能给出答案。

inputFormat:
第一行两个整数 $n,m$，分别代表向量个数和操作次数。

接下来 $n$ 行，每行两个整数 $x,y$，第 $i$ 行表示向量 $\overrightarrow{a_i}$。

接下来 $m$ 行，每行首先有一个整数 $opt$ 表示操作序号，之后有若干个整数表示一次操作。一共有下面五种操作。

1. 输入三个整数 $i,x,y(1\leq i\leq n)$，将 $\overrightarrow{a_i}$ 加上 $(x,y)$。
1. 输入三个整数 $i,x,y(1\leq i\leq n)$，将 $\overrightarrow{a_i}$ 减去 $(x,y)$。
1. 输入两个整数 $i,t(1\leq i\leq n)$，将 $\overrightarrow{a_i}$ 修改为 $t\overrightarrow{a_i}$。
1. 输入两个整数 $l,r(1\leq l<r\leq n)$，求 $\sum\limits_{i=l}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\cdot\overrightarrow{a_j}$。
1. 输入两个整数 $l,r(1\leq l<r\leq n)$，求 $\sum\limits_{i=l}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\oplus\overrightarrow{a_j}$。

outputFormat: 对于所有的第四和第五种操作，一行有一个整数，为这次操作的答案。

hint:
#### 样例 1 解释

前两次操作后三个向量分别为 $(4,7),(4,5),(-2,4)$，之后询问结果为 $4 \times(-2)+5\times4=12$。

下一次操作后三个向量分别为 $(4,7),(12,15),(-2,4)$，询问结果为 $(4\times15-7\times12)+[4\times4-7\times(-2)]+[12\times4-15\times(-2)]=-24+30+78=84$

-----------
#### 数据规模与约定
**本题采用捆绑测试**。
+ Subtask 1 ( $20\%$ )：$n,m\leq 100$。
+ Subtask 2 ( $30\%$ )：没有操作五。
+ Subtask 3 ( $50\%$ )：无特殊要求。

对于 $100\%$ 的数据，$2\leq n\leq 10^5$，$1\leq m\leq 10^5$，**保证对于任意时刻的向量 $\overrightarrow{a_i}$，满足 $-1000\leq x_i,y_i\leq 1000$**。

-----------
#### 关于向量运算

对于向量 $\overrightarrow{a},\overrightarrow{b}$ 和常数 $\lambda$，假定 $\overrightarrow{a},\overrightarrow{b}$ 的坐标表示分别为 $(x_a,y_a),(x_b,y_b)$：

+ $\overrightarrow{a}+\overrightarrow{b}=(x_a+x_b,y_a+y_b)$
+ $\overrightarrow{a}-\overrightarrow{b}=(x_a-x_b,y_a-y_b)$
+ $\lambda\overrightarrow{a}=(\lambda x_a,\lambda y_a)$
+ $\overrightarrow{a}\cdot\overrightarrow{b}=x_ax_b+y_ay_b$
+ $\overrightarrow{a}\oplus\overrightarrow{b}=x_ay_b-x_by_a$


title: [USACO16FEB] Circular Barn G

background: *本题与 [银组同名题目](/problem/P3137) 在题意上一致，唯一的差别是数据范围。*

description:
作为当代建筑的爱好者，Farmer John 建造了一个圆形新谷仓，谷仓内部 $n$ 个房间排成环形（$3 \leq n \leq 10^5$），按顺时针顺序编号为 $1\ldots n$，每个房间都有通往与其相邻的左右房间的门，还有一扇门通往外面。

现在 FJ 有 $n$ 头奶牛，他的目标是让每个房间恰好有一头奶牛。然而不幸的是，现在奶牛们随意呆在某个房间里，第 $i$ 个房间里有 $c_i$ 头奶牛。保证 $\sum c_i =n$。

FJ 决定采用这样的方法来解决这个问题：让某些奶牛**顺时针**穿过某些房间到达指定的位置。如果一头奶牛穿过了 $d$ 扇门，他消耗的能量为 $d^2$。你需要帮 FJ 算出所有奶牛消耗的能量和最小值是多少。

inputFormat: 第一行一个整数 $n$，接下来 $n$ 行，第 $i$ 行一个整数 $c_i$。

outputFormat: 输出所有奶牛最小消耗能量和。


title: Count on a tree II/【模板】树分块

background: 原 bzoj2589。

description:
给定一个 $n$ 个节点的树，每个节点上有一个整数，$i$ 号点的整数为 $val_i$。

有 $m$ 次询问，每次给出 $u',v$，您需要将其解密得到 $u,v$，并查询 $u$ 到 $v$ 的路径上有多少个不同的整数。

解密方式：$u=u' \operatorname{xor} lastans$。

$lastans$ 为上一次询问的答案，若无询问则为 $0$。

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

第二行有 $n$ 个整数。第 $i$ 个整数表示 $val_i$。

在接下来的 $n-1$ 行中，每行包含两个整数 $u,v$，描述一条边。

在接下来的 $m$ 行中，每行包含两个整数 $u',v$，描述一组询问。

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


title: [USACO16FEB] Fenced In G

background: *本题和 [白金组同名题目](/problem/P3141) 在题意上一致，唯一的不同是数据范围。*

description:
Farmer John 意识到他的奶牛最近患上了一种恐惧症（害怕过于开阔的空间）。为了减少放牧的恐惧，FJ 决定在牧场中建一些水平和竖直方向的栅栏来将牧场分成若干个小区域。

整个牧场是一个矩形，两个角的坐标分别为 $(0,0)$ 和 $(A,B)$。FJ 在 $a_1,\ldots ,a_n$ 这 $n$ 个两两不同的位置建造了竖直方向的栅栏，每个栅栏从 $(a_i,0)$ 到 $(a_i,B)$；FJ 在 $b_1,\ldots ,b_m$ 这 $m$ 个两两不同的位置建造了水平方向的栅栏，每个栅栏从 $(0,b_i)$ 到 $(A,b_i)$。竖直方向的栅栏和水平方向的栅栏两两相交，将整个牧场分割成 $(n+1)(m+1)$ 个区域。

不幸的是，FJ 忘记了在栅栏上开门，奶牛都只能被困在一个个的小区域里！他想通过去掉一些栅栏来解决这个问题。他一次可以选择两个相邻的区域，将隔离这两个区域的栅栏去掉。FJ 的目标是让奶牛能够抵达牧场的任意一个地方。

这是一个例子：

```plain
+---+--+
|   |  |
+---+--+
|   |  |
|   |  |
+---+--+
```

去掉一些栅栏后的效果是这样的：

```plain
+---+--+
|      |
+---+  +
|      |
|      |
+---+--+
```

为了降低工程量，FJ 当然希望拆除的栅栏长度最短。

inputFormat:
第一行四个整数 $A,B,n,m$，保证 $1 \leq n,m \leq 2000$，$1 \leq A,B \leq 10^9$。

接下来 $n$ 行，第 $i$ 行一个整数 $a_i$，保证 $0 \lt a_i \lt A$。

接下来 $m$ 行，第 $i$ 行一个整数 $b_i$，保证 $0 \lt b_i \lt B$。

outputFormat: 输出拆除栅栏的最小长度。**答案需要用 64 位带符号整数存储。**


title: [RC-03] 随机树生成器

description:
小 R 有一个随机树生成器，其工作原理如下：
- 输入 $n$，则对于每个 $1<i\le n$，随机选择一个 $[1,i)$ 中的节点作为其父亲。返回这棵树。

给定 $n,k$，小 R 想知道可能生成的所有 $n$ 个点的树中，$k$ 号点的度数和。

由于答案可能很大，请输出答案模 $10^9+9$ 的值。

inputFormat:
**本题有多组数据。**

第一行一个整数，是数据组数 $T$。

接下来 $T$ 行，每行两个正整数 $n,k$。

outputFormat: $T$ 行，每行一个整数，为这组数据的答案模 $10^9+9$ 的值。

hint:
【样例说明】

- 数据 $1$：一共有两种情况，$1$ 号点的度数分别为 $1,2$。因此答案为 $3$。
- 数据 $2$：一共有两种情况，$2$ 号点的度数分别为 $1,2$。因此答案为 $3$。
- 数据 $3$：一共有两种情况，$3$ 号点的度数均为 $1$。因此答案为 $2$。

【数据范围】

本题捆绑测试。

对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le k\le n\le 10^7$。详细数据范围如下。

- Subtask 1（20 分）：$T\le 50$，$n\le 8$。
- Subtask 2（55 分）：$T=1$，$n\le 10^5$。
- Subtask 3（20 分）：$T=1$。
- Subtask 4（5 分）：没有任何附加限制。


title: [USACO16FEB] Load Balancing P

background: *本题与 [银组同名题目](/problem/P3138) 在题意上一致，唯一的差别是数据范围。*

description:
Farmer John 的 $N$ 头奶牛（$1 \leq N \leq 10^5$）散布在整个农场上。整个农场是一个无限大的二维平面，第 $i$ 头奶牛的坐标是 $(x_i,y_i)$（保证 $x_i,y_i$ 均为正奇数，且 $x_i,y_i \leq 10^6$），且没有任意两头奶牛在同一位置上。

FJ 希望修建一条竖直方向的栅栏，它的方程是 $x=a$，他还希望修建一条水平方向的栅栏，它的方程是 $y=b$。为了防止栅栏经过奶牛，$a,b$ 均要求是偶数。容易发现，这两个栅栏会在 $(a,b)$ 处相交，将整个农场分割为四个区域。

FJ 希望这四个区域内的奶牛数量较为均衡，尽量避免一个区域奶牛多而另一个区域奶牛少的情况。令 $M$ 为四个区域里奶牛最多区域的奶牛数量，请帮 FJ 求出 $M$ 的最小值。

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

接下来 $N$ 行，每行两个整数 $x_i,y_i$，描述第 $i$ 头奶牛的位置。

outputFormat: 输出 $M$ 的最小值。


title: [USACO16FEB] Circular Barn P

description:
作为当代建筑的爱好者，Farmer John 建造了一个圆形新谷仓，谷仓内部 $n$ 个房间排成环形（$3 \leq n \leq 1000$），按顺时针顺序编号为 $1\ldots n$，每个房间都有通往与其相邻的左右房间的门，还有一扇门通往外面。

FJ 准备让第 $i$ 个房间里恰好有 $r_i$ 头奶牛（$1 \le r_i \le {10}^6$）。为了有序地让奶牛进入谷仓，他打算解锁 $k$ 个从外界进入谷仓的门（$1 \le k \le 7$）。然后，每头奶牛**顺时针**走动，直到到达目的地。FJ 的目标是让所有奶牛走动的距离和最小（奶牛从哪个门进入可以随意安排，这里走动的距离只包含进入谷仓后走动的距离），现在请你求出这个最小距离。

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

接下来 $n$ 行，第 $i$ 行一个整数 $r_i$。

outputFormat: 输出所有奶牛最小走动距离和。

hint: FJ 打开 $2,5$ 两个门。$11$ 头奶牛从 $2$ 号门进入，前往 $2,3,4$ 号房间，总距离 $8$。$10$ 头奶牛从 $5$ 号门进入，前往 $5,6,1$ 号房间，总距离 $6$。


title: [USACO16JAN] Angry Cows S

description:
Bessie 设计了一款新游戏：*Angry Cows*。在这个游戏中，玩家发射奶牛，每头奶牛落地时引爆一定范围内的干草。游戏的目标是使用一组奶牛引爆所有干草。

$N$ 捆干草排列在数轴上的不同位置。第 $i$ 捆干草的的位置为 $x_i$。如果一个威力为 $R$ 的奶牛在 $x$ 位置落地，她将引爆 $[x-R,x+R]$ 范围内的所有干草。

你现在可以发射 $K$ 头奶牛，每头奶牛的威力都是 $R$，现在你需要确定 $R$ 的最小值，使得用 $K$ 头奶牛可以引爆所有干草。

inputFormat:
第一行两个整数 $N,K$（$1 \leq N \leq 5 \times 10^4$，$1 \leq K \leq 10$）。

接下来 $N$ 行，第 $i$ 行一个整数 $x_i$（$0 \leq x_i \leq 10^9$）。

outputFormat: 输出一个整数，即 $R$ 的最小值。


title: 无向图的最小环问题

description: 给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小的环的边权和。若无解，输出 `No solution.`。

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

接下来 $m$ 行，每行三个正整数 $u,v,d$，表示节点 $u,v$ 之间有一条长度为 $d$ 的边。

outputFormat: 输出边权和最小的环的边权和。若无解，输出 `No solution.`。

hint:
样例解释：一种可行的方案：$1-3-5-2-1$。

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

对于 $60\%$ 的数据，$m\leq 100$。

对于 $100\%$ 的数据，$1\le n\leq 100$，$1\le m\leq 5\times 10^3$，$1 \leq d \leq 10^5$。

**无解输出包括句号。**


title: Yesterday Once More

background:
What will tomorrow be? Or, what is tomorrow? Or, what was tomorrow......

What was yesterday? Or, what is yesterday? Or, what will yesterday be......

It is said that TIME cannot go back.

It is true, they all said.

Why? Are all those things inevitable? Is that really my unchangeable fate?

Where is the passion when we first met in that place?

I know that I messed it up, times and times again.

I want to turn back the clock and start again.

Yesterday Once More......

—— lgswdn

description:
**注：题面中所有 $(x,y)$ 表示第 $x$ 行第 $y$ 列的点。**

游戏的地图可以看成 $n\times m$ 的网格图。每个格子里可能会有障碍。对于每个非障碍格子，里面可以站人也可以不站人，当然，每个格子最多只能站一个人。

现在，你可以在非障碍点放置一些人，这些人都有一个朝向，这个朝向为上下左右中的一个。每个人你都可以给他设置他的射程，射程可以任意**正整数**。

射程：人攻击的距离；若一个人在 $(x,y)$，朝向向右，他的射程为 3，那么他最远可以攻击到 $(x,y+3)$。注意，一个人的攻击不能穿越障碍物。

现在，UM 想问问你整个游戏有多少种放人方法，使得所有人之间都不会互相攻击，而且任意两个人的攻击范围都不能有重叠（因为这样可能会浪费弹药），由于答案太大，所以 UM 要你给出答案对 $998244353$ 取模的结果。

我们设第 $x$ 行第 $y$ 列的格子编号为 $(x-1)\times m+y$，并把所有的人按他射程范围内的编号最小的格子的编号为关键字进行排序，并以排序后的顺序对所有人编号。两种放置人的情况被认为是不相同的，**当且仅当两种情况人数不同或者存在一个编号相同的人射程范围内的格子中至少有一个格子编号不同。**

但是，UM 觉得这个问题太简单了，会被强大的你两分钟切掉，于是，他为你精心准备了 5 种询问：
1、把点 $(x,y)$ 设置为障碍点后的放人方案数；
2、把第 $x$ 行整个设置为障碍后的放人方案数；
3、把第 $x$ 列整个设置为障碍后的放人方案数；
4、把点 $(x,y) ,\ (x,y+1),\dots,\ (x,y+t)$ 设置为障碍点后的放人方案数。
5、把点 $(x,y) ,\ (x+1,y),\dots,\ (x+t,y)$ 设置为障碍点后的放人方案数；

**注意，每次操作后的地图都会还原成初始的状态。**

inputFormat:
第一行两个正整数，$n,m$，意义如题面所述。

接下来 $n$ 行每行 $m$ 个整数，表示游戏地图。若这个数为 $1$ 则为非障碍点，若为 $0$ 则为障碍点。

接下来一行一个整数 $T$ 表示有 $T$ 个询问。

接下来 $T$ 行，每行的第一个整数 $opt$，表示这个询问的类型：
若 $opt=1$，则分别对应第一种询问，接下来输入两个正整数 $x,y$，意义如题面所述；
若 $opt=2,3$，则分别对应第二，三种询问，接下来输入一个整数 $x$，意义如题面所述；
若 $opt=4,5$，则分别对应第四，五种询问，接下来输入三个整数 $x,y,t$，意义如题面所述。

outputFormat:
输出共 $T+1$ 行。
第一行一个整数表示初始状态时的答案。
接下来 $T$ 行，一行一个整数表示每个询问的答案。

**请注意：每个输出都应对 $998244353$ 取模。**

hint:
[样例解释](https://www.luogu.com.cn/paste/wez5s4mh)。

对于所有的询问，保证输入的参数均在棋盘大小范围内。

对于 $15\%$ 的数据，保证 $1<n,m\le 5$ 且 $1\le T\le 10$。
对于另外 $10\%$ 的数据，保证 $T=0$。
对于另外 $10\%$ 的数据，保证只有第 1 种询问。
对于另外 $15\%$ 的数据，保证只有第 2,3 种询问。
对于 $100\%$ 的数据，保证 $1<n\le m\le 15$，$0\le T\le 10^3$，第 1,4,5 种询问的总数不超过 $100$。

对于所有的数据，保证第 4,5 种询问中的 $t$ 为正整数。


title: [EER1] 苏联人

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

这是一道正常的题，和苏联没有任何关系。

description:
你在打 EE Round 1，发现第一题非常无聊。于是你不打了，去下国际象棋了。

结果你发现，由于神秘力量的影响，你的棋子只剩下若干黑色的战车，若干黑色的主教和一只白色的国王了。

由于你很无聊，所以你把一些黑色棋子放在了 $8\times 8$ 的棋盘上。

由于你很无聊，所以你想知道，国王放在哪些格子是安全的。换句话说，有哪些格子不会被战车和主教攻击到。当然，**国王不能放在已经有棋子的地方**。

为了防止你无聊透顶而不知道国际象棋的规则，这里给出以下提示（如果你知道规则那么可以跳过）：

国际象棋中，战车可以横向、竖向移动，且格数不受限制。但**不能越过其他棋子**。

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

如图，黄色的格子为战车能走到（攻击到）的格子。

国际象棋中，主教可以斜向移动，且格数不受限制。但**不能越过其他棋子**。

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

如图，黄色的格子为主教能走到（攻击到）的格子。

简单来说，如果当前位置到目标位置的**直线**上存在其他棋子，则可以称为“越过了其他棋子”。

如果目标位置是对方的棋子，那么移动到目标位置后，对方的棋子会被吃掉。

更进一步地，你要找的所有位置，必须满足没有黑色棋子能一步走到。

---

如果你还是没有读懂，可以结合样例进行理解。

inputFormat:
共 $8$ 行，每行 $8$ 个字符，表示棋盘的状态。

其中 `.` 表示空位，`R` 表示战车，`B` 表示主教。

outputFormat: 共 $8$ 行，每行 $8$ 个字符。若一个格子是可以放国王的，则输出 `1`，否则输出 `0`。

hint:
对于 $100\%$ 的数据，保证只会出现 `.`，`R`，`B` 三种字符。

本题共有 $4$ 个子任务，每个子任务的限制如下：

子任务 $1$（$10$ 分）：保证只会出现 `.`。

子任务 $2$（$20$ 分）：保证只会出现一个 `R` 或一个 `B`（不同时出现）。

子任务 $3$（$30$ 分）：保证只有一个 `.`。

子任务 $4$（$40$ 分）：没有特殊限制。


title: [USACO16JAN] Lights Out P

description:
Farmer John has installed a fancy new milking machine in his barn, but it draws so much power that it occasionally causes the power to go out! This happens so often that Bessie has memorized a map of the barn, making it easier for her to find the exit of the barn in the dark. She is curious though about the impact of power loss on her ability to exit the barn quickly. For example, she wonders how much farther she might need to walk find the exit in the dark.

The barn is described by a simple (non self-intersecting) polygon with integer vertices $(x_1,y_1)\ldots(x_n,y_n)$ listed in clockwise order. Its edges alternate between horizontal (parallel to the x-axis) and vertical (parallel to the y-axis); the first edge can be of either type. The exit is located at $(x_1,y_1)$. Bessie starts inside the barn located at some vertex $(x_i,y_i)$ for $i \gt 1$. She can walk only around the perimeter of the barn, either clockwise or counterclockwise, potentially changing direction any time she reaches a vertex. Her goal is to travel a minimum distance to reach the exit. This is relatively easy to do with the lights on, of course, since she will travel either clockwise or counterclockwise from her current location to the exit -- whichever direction is shorter.

One day, the lights go out, causing Bessie to panic and forget which vertex she is standing at. Fortunately, she still remembers the exact map of the barn, so she can possibly figure out her position by walking around and using her sense of touch. Whenever she is standing at a vertex (including at her initial vertex), she can feel whether it is a left turn or a right turn, and she can tell if that vertex is the exit. When she walks along an edge of the barn, she can determine the exact length of the edge after walking along the entire edge. In general, Bessie will strategically feel her way around her starting vertex until she knows enough information to determine where she is, at which point she can easily figure out how to get to the exit by traveling a minimum amount of remaining distance.

Please help Bessie determine the smallest possible amount by which her travel distance will increase in the worst case (over all possibilities for her starting vertex) for travel in the dark versus in a lit barn, assuming she moves according to an optimal strategy in each case. An "optimal" strategy for the unlit case is one that minimizes this extra worst-case amount.

inputFormat: The first line of the input contains $N$ ($4 \leq N \leq 200$). Each of the next $N$ lines contains two integers, describing the points $(x_i,y_i)$ in clockwise order around the barn. These integers are in the range $-100,000 \ldots 100,000$.

outputFormat: Please output the smallest possible worst-case amount by which Bessie's optimal distance in the dark is longer than her optimal distance in a lit barn, where the worst case is taken over all possible vertices at which Bessie can start.

translation:
## 题目大意：
按顺时针顺序给你$N$ $(4≤N≤200)$ 点，围成一个N边形农场。贝西要从某一点p出发走道农场1，她不知道自己在哪个点。

她先按顺时针顺序走若干个点，记录下她所走的每条边的长度和每次转弯的角度，如果从当前记录的信息能够准确判断她所在的位置，她就可以选择继续以往前走或掉头往回走两种方式中距离较短的方式来走到1。

现求对于所有不同的出发点，从原位置直接走到1的较短路径（顺或逆时针走）和贝西以上述的这种方式走出的路径长度的差值的最大值。

备注：所给农场所有的边均水平或竖直，记录“转弯的角度”可以理解为记录转了90°或270°，即顺时针转弯或逆时针转弯。

输入数据给出$N$和$N$个横坐标和纵坐标的绝对值都不超过$ 10^5 $的点，按照题目要求输出。

hint:
In this example, Bessie can feel that she is initially standing at an inward bend, however since in this example all corners are inward bends this tells her little information.

One optimal strategy is to just travel clockwise. This is optimal is she starts at vertex 3 or 4 and only adds 2 units of distance if she starts at vertex 2.


title: [CEOI2012] Printed Circuit Board

description:
给出一个 $n$ 个顶点的简单多边形，对于每个顶点，假如它和原点连成的线段只在这个顶点处和多边形相交，就称为满足要求的顶点。你的任务是输出所有满足要求的顶点编号。

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

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

下面 $n$ 行每行两个不超过 $10^6$ 的正整数，依次表示每个顶点的坐标。顶点按照输入顺序用正整数 $1,2,...,n$ 编号，并且顶点保证按照顺时针或逆时针顺序给出。

outputFormat:
第一行一个正整数 $m$，表示满足要求的顶点个数。

第二行 $m$ 个正整数，按照升序给出满足要求的顶点编号。

hint: 对于 $100\%$ 的数据，满足 $1 \le n \le 2 \times 10^5$。


title: [USACO15DEC] High Card Wins S

description:
Bessie 是纸牌游戏的忠实粉丝。对她而言，其他奶牛都算不上对手。更糟糕的是，其他奶牛在打牌时的行为都是完全能预测的。尽管如此，Bessie 知道取胜仍然是个挑战。

Bessie 和她的朋友 Elsie 正在玩一种纸牌游戏。这个游戏里要用到一副 $2N$ 张牌的套牌，编号从 $1$ 到 $2N$。Bessie 和 Elsie 每个人各分得 $N$ 张卡片。接下来进行 $N$ 轮比赛，Bessie 和 Elsie 每轮各出一张牌。每一轮谁的牌编号更大，谁就赢得了本轮的胜利。

Bessie 已经预测了 Elsie 的出牌顺序，请帮助 Bessie 算出她最多能赢多少轮。

inputFormat:
第一行一个整数 $N$（$1 \leq N \leq 5 \times 10^4$）。

接下来 $N$ 行，第 $i$ 行一个整数，表示 Elsie 第 $i$ 轮出的牌。注意 Bessie 手中的 $N$ 张牌很容易从输入中推出。

outputFormat: 输出 Bessie 最多能赢多少轮。

hint:
Bessie 手中拿着 $2,3,5$ 三张牌。

它第一轮出 $2$，第二轮出 $3$，第三轮出 $5$，从而赢得一，三两轮。可以证明不存在更优的方案。


title: [USACO15DEC] Breed Counting S

description:
Farmer John 的 $N$ 头奶牛，从左到右编号为 $1 \ldots N$，排成一队。

所有牛都可以分为三个品种，每头牛都有一个品种编号（只能为 $1,2,3$ 中的一个）。FJ 有 $Q$ 个询问，每个询问希望求出某个区间内每个品种奶牛的数量。

inputFormat:
第一行两个整数 $N,Q$（$1 \leq N,Q \leq 10^5$）。

接下来 $N$ 行，每行一个整数，第 $i$ 个整数代表第 $i$ 头奶牛的品种编号。

接下来 $Q$ 行，每行两个整数 $a,b$，表示第 $i$ 次查询的范围是 $[a,b]$。

outputFormat: 对于每个查询，输出三个整数，分别是指定区间内品种 $1$ 的奶牛数量，品种 $2$ 的奶牛数量，品种 $3$ 的奶牛数量。


title: 『JROI-1』 关系树

background: 小 L 有许多喜欢的游戏角色，他把这些游戏角色按照一定的关系联系起来。这些游戏角色和他们之间的关系构成了一棵树，小 L 把这棵树称之为「关系树」。

description:
关系树是由 $n$ 个点和 $n-1$ 条无向边组成的一棵树。

对于一张给定的图 $G$，定义图 $G$ 对于点集 $E$ 的 **顶点导出子图** 为点集 $E$ 和所有的 **两个端点都属于 $E$** 且属于原图 $G$ 的边组成的图。

定义一张图是 **整洁的**，当且仅当图中任意两点 $u,v$，$u$ 和 $v$ **不连通** 或 **距离不超过** $k$。

小 L 想要知道对于一组 $l,r(l \leq r)$，有多少对 $(a,b)$，满足 $l\leq a\leq b\leq r$，且所有序号在 $a$ 和 $b$ 之间（包括 $a,b$）的点组成的顶点导出子图是 **整洁的**。不仅如此，他还想问你所有的区间长度（即 $b-a+1$）之和。

因为小 L 喜欢问问题，所以你一共需要回答 $q$ 组询问。

inputFormat:
第一行有三个整数 $n$，$q$，$k$，意义如上。

接下来 $n-1$ 行，每行两个整数 $u$，$v$，描述一条边。

接下来 $q$ 行，每行两个整数 $l$，$r$，表示一组询问。

outputFormat: $q$ 行，每行两个整数，依次为满足的 $(a,b)$ 组数和所有的区间长度之和。


title: [EER1] 河童重工

background: 妖怪之山上生活着两种妖怪，鸦天狗和河童。从前，他们各有自己专属的交通线路，可以在妖怪之山的各个地点之间移动，但两套交通线路的维护成本实在是太高了！因此妖怪们现在想要把两套线路精简成一套。这个繁重的工程就被委托给河童重工了。

description:
妖怪之山上有 $n$ 个地点，鸦天狗和河童的两套交通线路都是分别由一些连接这些地点的无向道路组成的，每条道路有自己的长度，把这些道路看成有权边，那么他们的两套线路分别可以表示成两棵 $n$ 个节点的树 $T_1, T_2$（有 $n-1$ 条边的有边权无向连通图），河童重工现在要新建一些无向道路，新建一条无向道路 $(i,j)$ 的花费是 $dist_{T_1}(i,j)+dist_{T_2}(i,j)$（即 $T_1,T_2$ 上 $i$ 到 $j$ 的距离之和），河童重工要保证妖怪之山的任意两个节点都能只通过新修建的道路互相到达。但由于如果花费过多可能引起异变，所以他们希望这个工程的总花费最少。

荷取作为这个工程的总设计师，请你帮她算一算，修建新道路的总花费最少是多少？

inputFormat:
第一行一个正整数 $n$，表示节点数量。

接下来有 $n-1$ 行，其中第 $i$ 行有三个整数 $x_i, y_i, v_i(1 \leq x_i, y_i \leq n, 1 \leq v_i \leq 5000)$，表示 $T_1$ 中有一条长度为 $v_i$ 的边，连接 $x_i, y_i$ 两点。

接下来有 $n-1$ 行，其中第 $j$ 行有三个整数 $x_j, y_j, v_j(1 \leq x_j, y_j \leq n, 1 \leq v_j \leq 5000)$，表示 $T_2$ 中有一条长度为 $v_j$ 的边，连接 $x_j, y_j$ 两点。

outputFormat: 一行一个整数表示最少的总花费。

hint:
对于 $100\%$ 的数据，满足 $2 \leq n \leq 10^5$。

本题共有 $5$ 个子任务，每个子任务的限制如下：

子任务 $1$（$15$ 分)：保证 $2 \leq n \leq 1000$。

子任务 $2$（$15$ 分)：保证 $T_1, T_2$ 分别是一条链。

子任务 $3$（$5$ 分)：保证 $T_1, T_2$ 除了边权完全相同（即如果将两棵树看成无边权树，那么它们是相同的）。

子任务 $4$（$5$ 分)：保证 $T_2$ 是一条链。

子任务 $5$（$60$ 分)：无特殊限制。


title: [USACO10OPEN] Mountain Watching S

description:
一天，Bessie 望着远处的山脉，在思考：“哪一座山最宽呢？”

Bessie 设法测量了 $N$ 个位置的高度 $h_i$（$1 \leq N \leq 10^5$，$1 \leq h_i \leq 10^9$）。一座山被定义为一个高度先不下降，后不上升的子序列。视野边缘的山脉也只会增加或减少高度。一座山的宽度被定义为这座山包含的位置数量。

下面是一个例子：

```plain
           *******                   *
          *********                 ***
          **********               *****
          ***********           *********               *
*      *****************       ***********             *** *
**    *******************     *************   * *     *******      *
**********************************************************************
3211112333677777776543332111112344456765432111212111112343232111111211
aaaaaa                   ccccccccccccccccccccc eeeeeee    ggggggggg
  bbbbbbbbbbbbbbbbbbbbbbbbbbbb             ddddd ffffffffff  hhhhhhhhh
```

每座山都已经用字母标出来了。这里 `b` 山脉的宽度最大，为 $28$。

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

接下来 $N$ 行，每行一个整数 $h_i$。

outputFormat: 输出最宽的山的宽度。


title: [USACO10OPEN] Time Travel S

description:
Farmer John 买了台时光机，这使得他可以方便地管理自己的奶牛群。

他现在有 $N$ 个操作（$1 \leq N \leq 8 \times 10^4$），每次操作仅可能是如下三种之一：

1. `a x`：添加一头编号为 $x$ 的奶牛（$1 \leq x \leq 10^6$）。
2. `s`：卖掉最近添加的奶牛（保证此时至少有一头奶牛）。
3. `t x`：回到**第 $x$ 次操作前**的状态（保证第 $x$ 次操作存在）。

你需要在 FJ 执行每次操作后输出他拥有的最新的奶牛的编号。特别地，如果没有奶牛，输出 $-1$。

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

接下来 $N$ 行，每行描述一次操作。

outputFormat: 第 $i$ 行输出第 $i$ 次操作后 FJ 拥有的最新的奶牛的编号。特别地，如果没有奶牛，输出 $-1$。

samples:
12
a 5
a 3
a 7
s
t 2
a 2
t 4
a 4
s
t 7
s
s


title: [USACO10MAR] The Rock Game S

description:
在奶牛回家休息和娱乐之前，Farmer John 希望它们通过玩游戏获得一些智力上的刺激。

游戏板由 $n$ 个相同的洞组成，这些洞最初**都是空的**。一头母牛要么用石头盖住一个空的洞，要么揭开一个先前被盖住的洞。**游戏状态**的定义是所有洞是否被石头覆盖的情况。

游戏的目标是让奶牛到达**每个可能的游戏状态**一次，最后回到初始状态。

以下是他们其中一次游戏的示例（空的洞用 `O` 表示，用石头盖住的洞用 `X` 表示）：

| 时刻 | 洞 1 | 洞 2 | 洞 3 | 描述 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $0$ | O | O | O | 一开始所有的洞都是空的 |
| $1$ | O | O | X | 盖上洞 3 |
| $2$ | X | O | X | 盖上洞 1 |
| $3$ | X | O | O | 打开洞 3 |
| $4$ | X | X | O | 盖上洞 2 |
| $5$ | O | X | O | 打开洞 1 |
| $6$ | O | X | X | 盖上洞 3 |
| $7$ | X | X | X | 盖上洞 1 |

现在牛被卡住玩不下去了！他们必须打开一个洞，然而不管他们打开哪个洞，他们都会到达一个他们已经到达过的状态。例如，如果他们从第二个洞中取出岩石，他们将到达他们在时刻 $2$ 已经访问过的状态（`X O X`）。

下面是一个 3 个孔的有效解决方案：

| 时间 | 洞 1 | 洞 2 | 洞 3 | 描述 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $0$ | O | O | O | 一开始所有的洞都是空的 |
| $1$ | O | X | O | 盖上洞 2 |
| $2$ | O | X | X | 盖上洞 3 |
| $3$ | O | O | X | 打开洞 2 |
| $4$ | X | O | X | 盖上洞 1 |
| $5$ | X | X | X | 盖上洞 2 |
| $6$ | X | X | O | 打开洞 3 |
| $7$ | X | O | O | 打开洞 2 |
| $8$ | O | O | O | 打开洞 1，恢复到原来的状态 |

现在，奶牛们厌倦了这个游戏，它们想找你帮忙。

给定 $n$，求游戏的有效解决方案序列。如果有多个解决方案，则输出**任意一个**。

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

outputFormat: 共 $2^n+1$ 行，每行一个长度为 $n$ 的字符串，其中只包含字符 `O` 和 `X`，该行中的第 $i$ 个字符表示第 $i$ 个孔在此状态下是被覆盖还是未覆盖，第一行和最后一行必须全部都是 `O`。

hint:
#### 样例 1 说明

见题目描述。

#### 数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le15$。


title: [USACO08OCT] Building A Fence G

background: 勤奋的 Farmer John 想要建造一个由四面围成的栅栏来关住那些奶牛。他现在有一块长度为$N$（$4 \leq N \leq 2,500$）的长木板，他需要把这块长木板切成边长均为正整数的四块，使得他能建造一个栅栏。

description:
请问他有多少种不同的切割方式能使切割出来的木板围成一个四面的栅栏。

注意：

1. 不要考虑对称性的问题，不需要去除对称的方案和类似的复杂问题；
2. 栅栏围成的面积必须大于 0；
3. 结果可以用 32 位整数存储。

inputFormat: 一个整数 $N$。

outputFormat: Farmer John 能将木板分割开来并能围成四边形的方案数。


title: [EER1] 单调栈

description:
单调栈是一种常见的数据结构，如果你之前没有了解过，可以参考 [单调栈教程](https://www.luogu.com.cn/problemnew/solution/P5788) 帮助理解题意。

有一个长度为 $n$ 的**排列** $p_0, p_1, \cdots, p_{n-1}$，通过这个排列生成了一个长度为 $n$ 的序列 $S$，其中 $S_i$ 表示由 $p_0, p_1, \cdots, p_i$ 组成的递增单调栈的大小。

换一种说法，序列 $S$ 是由如下代码生成的：
```cpp
stack<int> stk;
int n = p.size();
vector<int> S;
for (int i = 0; i < n; i++) {
  while (!stk.empty() && p[i] <= p[stk.top()]) stk.pop();
  stk.push(i);
  S.push_back((int)stk.size());
}
```

现在给你序列 $S$ 的**一部分**，没有给出的部分可以取任意值。请你根据给出的 $S$ 复原出排列 $p$。如果有多种可能，输出字典序最小的。保证一定有解。

inputFormat:
第一行一个整数 $n$。表示排列的长度。

接下来一行 $n$ 个整数，表示序列 $S$。其中部分项为 $-1$，表示可以取任意值。

outputFormat: 一行 $n$ 个整数，一个排列。

hint:
样例 #1 解释：样例 $1$ 的输出对应的 $S$ 序列为 1 2 2 3 4 3 1 2 2 3，可以匹配输入。可以证明这是字典序最小的可以匹配输入的排列。

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

本题共有 $5$ 个子任务，每个子任务的限制如下：

子任务 $1$ ($5$ 分)：保证 $1 \leq n \leq 10$。

子任务 $2$ ($10$ 分)：保证给出的 $S$ 中没有 $-1$。

子任务 $3$ ($20$ 分)：保证 $1 \leq n \leq 300$。

子任务 $4$ ($20$ 分)：保证 $1 \leq n \leq 3000$。

子任务 $5$ ($45$ 分)：无特殊限制。


title: [NOI Online #1 提高组] 序列

background: ## 由于本题数据较难构造，所以无法保证卡掉所有错误做法。

description:
小 D 有一个长度为 $n$ 的整数序列 $a_{1 \dots n}$，她想通过若干次操作把它变成序列 $b_i$。

小 D 有 $m$ 种可选的操作，第 $i$ 种操作可使用三元组 $(t_i,u_i,v_i)$ 描述：若 $t_i=1$，则她可以使 $a_{u_i}$ 与 $a_{v_i}$ 都加一或都减一；若 $t_i=2$，则她可以使 $a_{u_i}$ 减一、$a_{v_i}$ 加一，或是 $a_{u_i}$ 加一、$a_{v_i}$ 减一，因此当 $u_i=v_i$ 时，这种操作相当于没有操作。

小 D 可以以任意顺序执行操作，且每种操作都可进行无限次。现在给定序列与所有操作，请你帮她判断是否存在一种方案能将 $a_i$ 变为 $b_i$。题目保证两个序列长度都为 $n$。若方案存在请输出 `YES`，否则输出 `NO`。

inputFormat:
本题输入文件包含多组数据。

第一行一个正整数 $T$ 表示数据组数。对于每组数据：

第一行两个整数 $n,m$，表示序列长度与操作种数。

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

第三行 $n$ 个整数表示序列 $b_i$。

接下来 $m$ 行每行三个整数 $t_i,u_i,v_i$，第 $i$ 行描述操作 $i$。

注意：同一个三元组 $(t_i,u_i,v_i)$ 可能在输入中出现多次。

outputFormat: 对于每组数据输出一行一个字符串 `YES` 或 `NO` 表示答案。

hint:
#### 样例 1 解释

第一组数据：使用一次操作 $1$。
第二组数据：使用三次操作 $1$。
第三组数据：使用三次操作 $1$，令 $a_1,a_2$ 都增加 $3$，再使用一次操作 $2$，令 $a_1,a_3$ 都增加 $1$。

---

#### 数据范围与提示

对于测试点 $1 \sim 5$：$n=2$，$m=1$，$a_i,b_i \le 99$，$u_1 \ne v_1$，$t_1=1$。
对于测试点 $6 \sim 10$：$n=2$，$m=1$，$a_i,b_i \le 99$，$u_1 \ne v_1$，$t_1=2$。
对于测试点 $11 \sim 12$：$n=2$，$a_i,b_i \le 99$，$u_i \ne v_i$。
对于测试点 $13 \sim 16$：$t_i=2$。
对于测试点 $17$：$n,m \le 20$。
对于测试点 $18$：$n,m \le 10^3$。
对于所有测试点：$1 \le T \le 10$，$1 \le n,m \le 10^5$，$1 \le a_i,b_i \le 10^9$，$t_i \in \{1,2\}$，$1\le u_i,v_i \le n$。


title: [NOI Online #1 提高组] 冒泡排序

description:
给定一个 $1 ∼ n$ 的排列 $p_i$，接下来有 $m$ 次操作，操作共两种：
1. 交换操作：给定 $x$，将当前排列中的第 $x$ 个数与第 $x+1$ 个数交换位置。
2. 询问操作：给定 $k$，请你求出当前排列经过 $k$ 轮冒泡排序后的逆序对个数。
对一个长度为 $n$ 的排列 $p_i$ 进行一轮冒泡排序的伪代码如下：
```
for i = 1 to n-1:
  if p[i] > p[i + 1]:
    swap(p[i], p[i + 1])
```

inputFormat:
第一行两个整数 $n$，$m$，表示排列长度与操作个数。

第二行 $n$ 个整数表示排列 $p_i$。

接下来 $m$ 行每行两个整数 $t_i$，$c_i$，描述一次操作：
- 若 $t_i=1$，则本次操作是交换操作，$x=c_i$；
- 若 $t_i=2$，则本次操作是询问操作，$k=c_i$。

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

hint:
#### 样例一解释
第一次操作：排列为 $\{1,2,3\}$，经过 0 轮冒泡排序后为 $\{1,2,3\}$，$0$ 个逆序对。

第二次操作：排列变为 $\{2,1,3\}$。

第三次操作：排列变为 $\{2,3,1\}$。

第四次操作：经过 $0$ 轮冒泡排序后排列变为 $\{2,3,1\}$，$2$ 个逆序对。

第五次操作：经过 $1$ 轮冒泡排序后排列变为 $\{2,1,3\}$，$1$ 个逆序对。

第六次操作：经过 $2$ 轮冒泡排序后排列变为 $\{1,2,3\}$，$0$ 个逆序对。

---

#### 数据范围与提示
对于测试点 1 ∼ 2：$n,m \leq 100$。

对于测试点 3 ∼ 4：$n,m \leq 2000$。

对于测试点 5 ∼ 6：交换操作个数不超过 $100$。

对于所有测试点：$2 \leq n,m \leq 2 \times 10^5$，$t_i \in \{1,2\}$，$1 \leq x < n$，$0 \leq k < 2^{31}$。


title: [NOI Online #1 提高组] 最小环

description:
给定一个长度为 $n$ 的正整数序列 $a_i$，下标从 $1$ 开始编号。我们将该序列视为一个首尾相邻的环，更具体地，对于下标为 $i$, $j(i \leqslant j)$ 的两个数 $a_i$, $a_j$，它们的距离为 $\min(j-i, i+n-j)$。

现在再给定 $m$ 个整数 $k_1$, $k_2$,..., $k_m$，对每个 $k_i(i=1$, $2$,..., $m)$，你需要将上面的序列 $a_i$ 重新排列，使得环上任意两个距离为 $k_i$ 的数字的乘积之和最大。

inputFormat:
第一行两个正整数 $n$, $m$，表示序列长度与询问数。

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

接下来 $m$ 行每行一个非负整数表示 $k_i$。

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


title: [USACO09FEB] Bulls And Cows S

background: 一年一度的展会要来临了，Farmer John 想要把 $N$（$1 \leq N \leq 100,000$）只奶牛和公牛安排在单独的一行中。 John 发现最近公牛们非常好斗；假如两只公牛在这一行中靠的太近，他们就会吵架，以至于斗殴，破坏这和谐的环境。

description: John 非常的足智多谋，他计算出任何两只公牛之间至少要有 $K$（$0 \leq K \lt N$）只奶牛，这样才能避免斗殴。John 希望你帮助他计算一下有多少种安排方法，可避免任何斗殴的的发生。John 认为每头公牛都是一样的，每头奶牛都是一样的。因而，只要在一些相同的位置上有不同种类的牛，那这就算两种不同的方法。

inputFormat: 两个整数 $N$ 和 $K$。

outputFormat: 输出约翰可以安排的方法数。考虑到这个数可能很大，你只要输出对 $5\,000\,011$ 取模之后的结果就可以了。

hint:
下面的就是 FJ 思考出可行的 6 种方案（C 代表奶牛，B 代表公牛）：
- CCCC
- BCCC
- CBCC
- CCBC
- CCCB
- BCCB


title: [NOI Online #1 入门组] 文具订购

description:
小明的班上共有 $n$ 元班费，同学们准备使用班费集体购买 $3$ 种物品：

1. 圆规，每个 $7$ 元。
2. 笔，每支 $4$ 元。
3. 笔记本，每本 $3$ 元。

小明负责订购文具，设圆规，笔，笔记本的订购数量分别为 $a,b,c$，他订购的原则依次如下：

1. $n$ 元钱必须正好用光，即 $7a+4b+3c=n$。
2. 在满足以上条件情况下，成套的数量尽可能大，即 $a,b,c$ 中的最小值尽可能大。
3. 在满足以上条件情况下，物品的总数尽可能大，即 $a+b+c$ 尽可能大。

请你帮助小明求出满足条件的最优方案。可以证明若存在方案，则最优方案唯一。

inputFormat: 输入仅一行一个整数，代表班费数量 $n$。

outputFormat:
如果问题无解，请输出 $-1$。

否则输出一行三个用空格隔开的整数 $a, b, c$，分别代表圆规、笔、笔记本的个数。

hint:
#### 样例输入输出 3 解释

$a=2,b=4,c=1$ 也是满足条件 $1,2$ 的方案，但对于条件 $3$，该方案只买了 $7$ 个物品，不如 $a=1,b=2,c=6$ 的方案。

#### 数据规模与约定

- 对于测试点 $1 \sim 6$，保证 $n \leq 14$。
- 对于测试点 $7 \sim 12$，保证 $n$ 是 $14$ 的倍数。
- 对于测试点 $13 \sim 18$，保证 $n \leq 100$。
- 对于全部的测试点，保证 $0 \leq n \leq 10^5$。


title: [ICPC2019 WF] Circular DNA

description:
You have an internship with a bioinformatics research group studying DNA. A single strand of DNA consists of many genes, which fall into different categories called gene types. Gene types are delimited by specific nucleotide sequences known as gene markers. Each gene type i has a unique start marker $\texttt s_i$ and a unique end marker $\texttt e_i$ . After many dirty jobs (growing bacteria, cell extraction, protein engineering,and so on), your research group can convert DNA into a form consisting of only the gene markers, removing all the genetic material lying between the markers.

Your research group came up with the interesting hypothesis that gene interpretation depends on whether the markers of some gene types form properly nested structures. To decide whether markers of gene type $i$ form a proper nesting in a given sequence of markers $w$, one needs to consider the subsequence of $w$ containing only the markers of gene type $i$ ($\texttt s_i$ and $\texttt e_i$), leaving none of them out. The following (and only the following) are considered to be properly nested structures:

- $\texttt s_i \texttt e_i$
- $\texttt s_i N \texttt e_i$, where $N$ is a properly nested structure
- $AB$, where $A$ and $B$ are properly nested structures

Given your computing background, you were assigned to investigate this property, but there is one further complication. Your group is studying a specific type of DNA called circular DNA, which is DNA that forms a closed loop. To study nesting in circular DNA, it is necessary to cut the loop at some location, which results in a unique sequence of markers (the direction of reading is fixed by molecular properties). Whether a gene type $i$ forms a proper nesting now also depends on where the circular DNA is cut. Your task is to find the cutting location that maximizes the number of gene types that form a properly nested structure. Figure D.1 shows an example corresponding to Sample Input 1. The indicated cut results in the markers for gene type 1 being properly nested.

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

inputFormat: The first line of input contains an integer $n$ ($1 \leq n \leq 10^6$), the length of the DNA. The next line contains the DNA sequence, that is, $n$ markers. Each marker is a character $c$ followed by an integer $i$, where $c \in \{\texttt s, \texttt e\}$ specifies whether it is a start or an end marker and $i$ ($1 \leq i \leq 10^6$) is the gene type of the marker. The given DNA sequence has been obtained from the circular DNA by cutting at an arbitrary location.

outputFormat: Output one line with two integers $p$ and $m$, where $p$ is the cutting position that maximizes the number of different gene types that form a proper nesting, and $m$ is this maximum number of gene types. The DNA is cut just before the $p^{\text{th}}$ input marker (for instance, the cut shown in Figure D.1 has $p = 3$). If more than one cutting position yields the same maximum value of $m$, output the smallest $p$ that does so.

translation:
一个长度为 $n$ 的环形 DNA 序列，以顺时针顺序给出，其中每个基因有类型和编号两个属性，类型是 $s$（头）或 $e$（尾）中的一种，而编号是 $1$ 到 $10_6$ 中的整数。
你需要在某个地方切断，按照顺时针顺序拉成链后，最大化能够完美匹配的基因编号个数。

一个基因编号 $i$ 是能够完美匹配的，当且仅当它在链中对应的所有基因，将 $s$ 看作左括号，$e$ 看作右括号，可以匹配成非空的合法括号序列。

如果有多个位置满足最大化的条件，输出最小的位置。

输入第一行一个整数 $n$ ($1≤n≤10^6$)，表示DNA序列的长度，第二行是DNA序列，包含 $n$ 个元素，每个元素有一个字符 $c∈\{s,e\}$（$s$ 表示切割时以这个元素为开始还是结束，$s$ 表示开始,$e$ 表示结束）和一个整数 $i$ (1 \le i \le 10^6) 表示基因类型。可以通过在任意位置切割，从环状DNA获得给定的DNA序列。

输出一行包含两个整数 $p$ 和 $m$ , $p$是切割位置，可最大化能够完美匹配的基因编号个数，$m$ 是能够完美匹配基因类型的最大数量如果多个切割位置产生相同的最大值 $m$，输出最小的 $p$。

hint: Source: ICPC 2019 World Finals.


title: 「Wdsr-1」人间之里

background:
- 这里是幻想乡中最多人类居住的地方。因为有许多妖怪也会光临的店，所以会有各种妖怪到访，不过都是些安份的妖怪，这是一个和平的地方（×1稗田家所在地，毫无疑问也在人类村落。

- 人类必要的生活用品，都能在这里买到。也有一些专门退治妖怪的人住在这，所以这里的生活是较安全的。

- 要说人类村落为什么没有被袭击，那就是妖怪的贤者在背后保护（×2幻想乡的人类灭绝的话，妖怪们也不好过。）。不外出的话，就不会遇上大难。

- 若外出途中遇到比自己强的妖怪（×3高概率的对方比自己强。），就恭恭敬敬地打招呼吧。 还有令人意外的是，有很多店会开到深夜，夜晚会变成妖怪专用店。妖怪多在夜晚活动，店也在那段时间兴旺。可以说妖怪才是很好的客人。

- 特别是卖酒的店，妖怪和人类同乐已成了日常一景。

$$\tag*{——摘自《东方求闻史纪》}$$

description:
虽然人间之里可以说是全幻想乡对于人类最安全的地方，但是异变发生时，还是可能会出现意外，所以要建立避难所。

人间之里可以抽象为一条坐标轴，其上有 $n$ 个点上建有房屋。这些房屋的坐标分别为 $x_1,x_2,...,x_n$，且在第 $i$ 座房屋中居住着 $v_i$ 位居民。

每次发生异变时，会有一段**坐标连续**的房屋受到影响，而此时便需要在某一坐标处建立避难所。一个避难所的"不便程度"为受影响的房屋中的**每一个居民**与避难所的距离之和。

（举例来说，假设只有房屋 $i$ 受到了影响，则在 $z$ 处建立避难所的"不便程度"为 $v_i*|x_i-z|$ ）

当然，坐落在幻想乡中人间之里的不可能一成不变，所以房屋的位置和居民的数量都可能会发生变化。

具体来说，你需要处理 $m$ 次询问或修改，每一次输入的格式如下：

- `1 l r`，表示询问 当**坐标**位于 $[l,r]$ 范围内的房屋受到异变影响时，在所有建立避难所的方案中，最小的"不便程度"是多少。

- `2 a b c`，表示将第 $a$ 座房屋的坐标修改为 $b$，其中居住的村民的数量变为 $c$ 。

**注意：**
- 在 $1$ 操作中的"受到异变影响"均为假设，所以对之后的查询不产生作用。

- 在 $2$ 操作中发生变化的是第 $a$ 座房屋而不是坐标为 $a$ 的房屋。

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

第二行 $n$ 个整数，$x_i$。

第三行 $n$ 个整数，$v_i$。

接下来 $m$ 行，每行描述一个操作。

outputFormat: 对于每个 `1 l r` 操作，输出建立避难所的最小"不便程度"。


title: [COCI2019-2020#6] Trener

background: 题目翻译来自 [LOJ3270](https://loj.ac/problem/3270)。

description:
**译自 [COCI 2019/2020 Contest #6](https://hsin.hr/coci/archive/2019_2020/) T5.** ***[Trener](https://hsin.hr/coci/archive/2019_2020/contest6_tasks.pdf)***

我们已经知道了学生们喜欢睡觉。Patrik 是这一记录的保持者。在最后一个梦中，他发现自己成为了他最喜欢的球队的队长。

为了参加一场比赛，他把自己的所有球员分为 $N$ 组，每组 $K$ 名球员，对于第 $i$ 组的球员，他们的姓氏长度都为 $i$。

现在，他要开始规划上场的球员组合了。一个组合有 $N$ 名球员，并且组委会对上场的球队还有有以下要求：

- 所有球员的姓氏长度必须不同。

- 所有球员的姓氏必须为其他姓氏比他长一个字符的球员的连续子序列。

Patrik 想知道，自己最多能把这些球员分为多少支可以上场的队伍。答案对 $10^9+7$ 取模。

inputFormat:
输入第一行为两个整数 $N,K$。

接下来的 $N$ 行，每行 $K$ 个字符串，为球员的姓氏，保证第 $i$ 行的字符串长度为 $i$。

outputFormat: 输出一行一个整数为最多分出的队伍支数，答案对 $10^9+7$ 取模。


title: [USACO07FEB] Cow Sorting G

description:
Farmer John 的 $n$（$1 \leq n \leq 10^5$）头牛一字排开。每头奶牛都有一个“脾气暴躁”水平，范围在 $1 \ldots 10^5$，且任意两头奶牛的脾气暴躁值不相同。由于脾气暴躁的奶牛更有可能损坏 FJ 的挤奶设备，因此 FJ 希望对奶牛进行重新排序，以便按照脾气暴躁程度依此提升的顺序排列它们。

在此过程中，任何两头奶牛（不一定相邻）的位置都可以互换。由于脾气暴躁的母牛难以移动，因此 FJ 总共需要 $X + Y$ 单位的时间来交换两只脾气暴躁程度为 $X$ 和 $Y$ 的母牛。请帮助 FJ 计算将奶牛按脾气暴躁程度的升序排序所需的最短时间。

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

接下来 $N$ 行每行包含一个整数 $a_i$，代表第 $i$ 头奶牛的脾气暴躁值。

outputFormat: 输出将所有奶牛按按脾气暴躁程度的升序排序所需的最短时间。


title: 分拆

background: 小 W 喜欢分拆。

description:
小 W 定义了一种「良好的分拆」：

对于正整数 $n$，如果存在 $n$ 个整数 $(a_1,a_2,\cdots,a_n)$ 使得 $\sum\limits_{i=1}^na_i=\prod\limits_{i=1}^na_i=n$，那么称 $n$ 是「良好的」，而 $(a_1,a_2,\cdots,a_n)$ 是 $n$ 的一个「良好的分拆」。

现在，小 W 给了你一些 $n$，他希望你求出这些 $n$ 分别是不是「良好的」。如果是良好的，请**任意**输出一个 $n$ 的「良好的分拆」。

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

接下来 $T$ 行，每行一个整数 $n$，表示小 W 的一个询问。

outputFormat:
对于每组数据，输出若干行。

如果 $n$ 不是「良好的」，那么仅输出一行 `NO`；

否则，第一行输出 `YES`，接下来一行一个数 $a$，表示你的「良好的分拆」中有多少种不同的数，接下来 $a$ 行，每行两个数 $x,y$，表示有 $x$ 个 $y$。

hint:
## 样例解释
$n=1$ 时，$(1)$ 是 $1$ 的一个「良好的分拆」；

$n=2$ 时，$2$ 没有「良好的分拆」；

$n=5$ 时，$5+1+1+(-1)+(-1)=5\times1\times1\times(-1)\times(-1)=5$，所以 $(5,1,1,-1,-1)$ 是 $5$ 的一个「良好的分拆」。
## 数据范围
**本题不捆绑测试。**
$\text{Subtask\;1(10\;pts)}$：$n=1,T=1000$；
$\text{Subtask\;2(30\;pts)}$：$n\le 10^4,T=100$；
$\text{Subtask\;3(60\;pts)}$：$T=1000$。
对于所有数据，$1\le n\le10^9$。
## 说明
本题带有 $\text{SPJ}$。

某个测试点获得满分，当且仅当对于这个测试点的所有 $T$ 组数据，有：
- 第一行的答案相同。
- 如果第一行的答案为 `YES`，则还要满足 $1\le a\le 20$，$1\le x\le n$，$\sum y\times x=\prod y^x=\sum x=n$。

**为了便于 $\text{SPJ}$ 的编写，允许有的 $y$ 相同，同时请确保在输出文件末尾有且仅有一个换行。**

$\text{SPJ}$ 源码请到[云剪贴板](https://www.luogu.com.cn/paste/tlhjg36n)查看。


title: [JSOI2011] 序的计数

description:
给定无向图 $G=\{V,E\}$，其中 $n=|V|,m=|E|$，$n$ 个点从 $1$ 到 $n$ 依次编号。

现在要求利用 DFS 即深度优先搜索。容易知道，利用 DFS 进行遍历的同时，我们可以将遍历到的点按照遍历的先后顺序记录下来，这样会得到一个点的序列，即一个 $1$ 到 $n$ 的排列。我们称这个排列为一个可能的 DFS 序。

显然不是所有 $1$ 到 $n$ 的排列都可能是 DFS 序的。现在这个 DFS 的过程进行到了一半，且恰好遍历了 $k$ 个不同的点 $\{u_1,u_2,...,u_k\}$，那么显然，这个进行到一半的 DFS 过程所对应的 DFS 序应该是这 $k$ 个数的一个排列。

现在请求出，当前这 $k$ 个遍历点能对应多少个不同的长度为 $k$ 的 DFS 序呢?

inputFormat:
输入文件第一行包含用空格隔开的三个整数，分别为 $n,m$ 和 $k$；

接下来 $m$ 行，每行包含两个用一个空格隔开的正整数 $u$ 和 $v$，表示图 $G$ 存在边 $(u,v)$。

最后一行包含 $k$ 个用空格隔开的正整数，描述当前已经遍历过的 $k$ 个点，其中第 $i$ 个数为 $u_i$。数据保证这 $k$ 个数一定按照从小到大的顺序给出。

outputFormat: 输出一行一个数，表示可能的 DFS 序的数量。

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

- 对于 $100\%$ 的数据，保证 $1 \le n \le 100$，$1 \le m \le 5 \times 10^3$，$1 \le k \le 18$，$1 \le u_i \le n$，$1 \leq u, v \leq n$。


title: [RC-04] 信息学竞赛

description:
小 R 今天学习了余角有关的数学知识，请你帮帮他计算一个角的余角吧！

一个角的余角的计算公式如下：

$$\angle B=90\degree -\angle A$$

其中 A 是给出的角，B 是你要计算的角。

inputFormat: 一行一个整数 $x$，表示 $\angle A=x\degree$。

outputFormat: 一行一个整数 $y$，表示 $\angle B=y\degree$。你需要严格按照公式计算。


title: 隔离的日子

background:
（背景改编自 百度贴吧/南北组备用吧/呆萌南北日常/F9023，作者 [落墨成白](https://tieba.baidu.com/home/main/?un=%E8%93%93%E8%90%BD%E9%B1%BC&ie=utf-8&id=tb.1.a8bcbb73.CMcL9PXngjHz-dKRJ7_T4A&fr=frs)）

### 数据已修复。

  一天又一天，每到深夜房间里又只余下手机屏幕的亮光，洛天依总会有一种与世界割离的失落感。
  闷在被子里孤独的想哭的日子里，她开始想念起哪些忙于工作带着一点点畏惧、忐忑和烦恼的小日子。
  毒辣的阳光，想出门的心，不想被晒黑的小心思交织在一起，占据心间的便是这些复杂的小情绪。
  如果可以还行要一份水果拼盘，阿绫总说她不能贪凉，所以趁着阿绫大意的时候把双手浸入打满水的水桶中，瞄着阿绫那无可奈何的眼神，心情舒爽啊。
  每到深夜回想起来仍会觉得回味无穷，可孤单一人时将水龙头拧开胳膊冲刷而过的冰凉感却寻不着那时的快乐。
  都说对生活选择短暂遗忘时，就会收获一丁点儿的快乐。
  可是为什么脑海里的那些场景却越发清晰？
  以往每逢休假，暖暖的阳光隔着玻璃照进来，阿绫就躺在摇椅上，她便可以赖在阿绫怀里软软的趴着，一个中午的就这么过去了，宛如养成系手游般堪是消磨时间的良方。
  还有街角那家糖炒栗子，拉着阿绫站在店铺门前看着油亮的栗子在翻炒机理跳着舞，被炸开的缝里透出诱人的气息。
  缠着阿绫买上几斤装好，恼人的阿绫却不肯给她，只是无比淡定地从袋子里捞出一粒，轻轻一捏，板栗便爆开了，轻轻一掰，栗子肉完完整整地出现在她的面前。这时她只需要张嘴，阿绫只会宠溺的将栗子喂到她的嘴里，只需看见她眯眼满足的表情，阿绫也会露出开心的笑。
  不禁泛起苦笑，自己还有一套对栗子的深入研究呢——

description:
以前，天依会把买来的 $n$ 个栗子排成一行，从左至右编号为：$1,2,\cdots ,n$，第 $i$ 颗栗子有甜度 $a_i$ 和咸度 $b_i$。

天依认为甜和咸应该进行均衡的搭配，所以她定义了一个完美搭配 $(i,j)$，其中 $i,j$ 是两个栗子的下标。具体的，称 $(i,j)$ 为一个完美搭配，当且仅当 $j$ 是所有满足 $i<j \leq n$ 并且 $(a_j-b_i) \times (b_j+b_i)=a_j \times b_i + a_i \times b_j$ 的 $j$ 中**最小的一个**。不难发现当 $i$ 一定，完美搭配唯一确定。

现在天依想知道，对于每个栗子 $i$，哪个栗子和它形成完美搭配？

inputFormat:
第一行一个整数 $n$，表示天依把 $n$ 个栗子排成了一行。

接下来 $n$ 行，每行两个整数 $a_i$ 和 $b_i$，分别表示第 $i$ 颗栗子的甜度和咸度。

outputFormat:
输出共 $n$ 行，每行一个整数，第 $i$ 行表示第 $i$ 颗栗子的**完美搭配 $(i,j)$** 中的 $j$。

特殊地，如果不存在 $j$ 与 $i$ 形成**完美搭配**，那么第 $i$ 行输出一个 `-1`。

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

第一个栗子：$(22 - 8) \times (8 + 8) = 22 \times 8 + 6 \times 8$，所以输出为 $2$。

第二个栗子没有满足条件的完美搭配。

第三个栗子：$(23 - 4) \times (4 + 4) = 23 \times 4 + 15 \times 4$，所以输出为 $4$。

第四个栗子：$(31 - 4) \times (4 + 4) = 31 \times 4 + 23 \times 4$ ，所以输出为 $5$。

因为第五个栗子是最后一个栗子，所以没有满足条件的完美搭配。

---

#### 数据范围
**本题采用捆绑测试。**

- Subtask 1（30 Points），$n \leq 10^3$。
- Subtask 2（70 Points），$n \leq 5 \times 10^4$。

对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^4$，$1 \leq a_i \leq 10^9$，$1 \leq b_i \leq 100$。

---

### 题目背景 ( 续 )
  味道愈发的真实，栗子的香气仿佛仍绕在鼻尖……
  味道？洛天依猛然起身走出卧室隔着一道门栏，望着她。
  “你是不是傻？我现在在隔离呀，你来干什么？”有惊喜有忧虑洛天依骤然哭泣出声。
  乐正绫挠挠头，栗子的温热隔着纸袋传到手心，像寒冷日子里抱在手中的暖宝宝。
  “我回程的列车上有感染病例，我也需要被隔离了，他们问我家在哪里，我说了你的地址。”
  乐正绫剥开壳，捏了一颗放进小哭包的嘴里。
  栗子香在两人嘴角飘荡，“时间又得加长了啊……”天依微微喘着气嘟囔道，心底却是多了几分期待的快乐，其实如果有阿绫在的话，也不是不可以在房间多待段时间的。
  “啊，很抱歉呢。”乐正绫轻笑着。不知道是因为再次珍贵的时间，还是手指抚摸过天依泛红的唇角。


title: 回首过去

background:
>明天你是否会想起
>
>昨天未调完的题
>
>明天你是否还惦记
>
>考场写挂的暴力

[OEIS 入口](http://oeis.org/)

description:
在小学时，小 Z 就已经开始学
 OI 了。

有一次，在数学课上，老师问了这样一个问题：
求出有序整数对 $(x,y)$ 的个数，满足 $1\le x,y\le 5$ 且 $\frac{x}{y}$ 可以表示为十进制有限小数。

当然，小 Z 很快就算了出来。

但因为他是学了 OI 的，所以他就推广了一下：

**给定正整数 $n$，求出有序整数对 $(x,y)$ 的个数，满足 $1\le x,y\le n$ 且 $\frac{x}{y}$ 可以表示为十进制有限小数。**

当时，他还是一个菜鸡，只会
 $O(n^2)$ 的暴力。

过了几年，他偶然又翻到了这道题。现在他会了一种更好的方法，于是就把这题出了出来，给你来做做。

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

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


title: 重拳出击

description:
小 Z 和 $m$ 个 Youyou 在一棵树上相遇了！

这棵树上，每条边的长度都是 $1$。

初始时，小 Z 在 $x$ 号节点上，并且有一把射程为 $k$ 的枪。

因为小 Z 技术精湛，所以 Youyou 一打就死，而小 Z 永远不会死掉。

小 Z 和 Youyou 都按回合行动，在每一回合中，按照下面的顺序行动：

1. 回合计数器 $+1$（初始为 $0$）。

2. 小 Z 可以用枪射死与小 Z 树上距离小于等于 $k$ 的所有 Youyou。

3. 如果所有 Youyou 都被消灭了，游戏结束，这时回合计数器的值就是小 Z 用的回合数。

4. 小 Z 可以选择沿着一条边，移动到任意相邻节点，也可以选择不动。

5. 所有 Youyou 都会沿着他和小 Z 的简单路径向小 Z 移动一条边的距离。如果此时他们在同一个节点，则不动。

小 Z 需要求出消灭所有敌人需要的最小回合数。

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

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

接下来一行一个正整数 $m$。

接下来一行 $m$ 个正整数，第 $i$ 个数表示第 $i$ 个 Youyou 的初始所在节点。

最后一行两个整数，$k$ 和小 Z 自己的初始所在节点号 $x$。

outputFormat: 一行一个正整数，最小回合数。

hint:
**样例 2 解释**

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

小 Z 可以在第一回合射死后两个 Youyou，然后从节点 $5$ 移动到节点 $2$。剩余的两个 Youyou 也会移动到节点  $2$。第二回合小 Z 可以消灭所有 Youyou。可以证明这就是最优方案。

**数据规模与约定**

* Subtask 1（10 分）：$1 \le n,m \le 20$；
* Subtask 2（15 分）：$1 \le n,m \le 2\times 10^3$；
* Subtask 3（30 分）：$1 \le n,m \le 4\times 10^4$；
* Subtask 4（45 分）：$1 \le n,m \le 4\times 10^5$。

对于全部的数据，$1 \le n,m \le 4\times 10^5$，$0 \le k \le 10^6$。


title: 樱花，还有你

background:
Dear Ling,
  呐，你知道吗？听说樱花飘落的速度是秒速五厘米哦。
  ……所以，再等等吧！三月，武汉大学，樱花就快来了呢。
  你一定会陪我一起看吧，在酥软的阳光下，我会悄悄牵起你的手，感受你熟悉的温度，糟糕，脸儿也不小心被粉嫩嫩的樱花映红的呢。
  对了，一定记得带口罩！你那时还是有些虚弱吧。但天依会保护你的！
  还有啊，樱花还可以做好多好多的点心呢！收集一些飘落樱花吧，我想喝樱花茶，还想吃樱饼，你一定要亲手给我做嗷！

description:
**与题意有关的句子已加粗。**

但别急，我们就这样彳亍而行吧，**需不着停留或回头**，前面不是**还有 $k$ 棵樱花树么**？我算了算，你可要收集**恰好 $n$ 朵樱花**。我还发现，在第 $i$ 棵树下**最多**能收集到 $s_i$ 朵樱花（收集了 $0$ 朵樱花也算收集了樱花）。

呐，考考你吧！你有多少种方案能够收集到**恰好 $n$ 朵樱花**呢？

**特殊地，如果你收集不到 $n$ 朵樱花，请告诉我 `impossible`。**

注意：如果你早早地收集到了 $n$ 朵樱花，你可以立刻告诉我，也可以陪我继续向前走，一直到第 $k$ 棵樱花树下收集了樱花后就必须交差啦！期间你在任何一棵树收集完樱花后就告诉我，形成的方案都是不同的哦！

inputFormat:
第一行两个正整数 $n,k$，表示要收集 $n$ 朵樱花，而前方还有 $k$ 棵樱花树。

接下来一行 $k$ 个正整数 $s_1,s_2,\cdots,s_k$，其中 $s_i$ 表示最多在第 $i$ 棵樱花树下收集到 $s_i$ 朵樱花。

outputFormat:
一行一个整数，表示恰好收集到 $n$ 朵樱花的方案数。

**由于答案可能太大，请输出答案对 $10086001$ 取模后的值。**

特殊地，如果收集不到 $n$ 朵樱花，请输出一个字符串 `impossible`。

hint:
#### 样例解释 #1
我们以下列方式表示一种方案：$(a_1,a_2,\cdots,a_{len})$，其中 $\sum_{i=1}^{len} a_i =n$，$len$ 表示在第 $len$ 棵樱花树下收集完樱花后就交差了，$a_i$ 表示在第 $i$ 棵树下收集了 $a_i$ 朵樱花。

那么有下列 $5$ 种方案：$(1,1,1)$，$(1,1,1,0)$，$(0,1,1,1)$，$(1,0,1,1)$，$(1,1,0,1)$。

---

#### 样例解释 #3
最多能收集到 $9$ 朵樱花，所以不能收集到 $10$ 朵樱花，输出 `impossible`。

---

#### 数据范围
**本题采用捆绑测试。**
- Subtask 1（5 Points），$\sum s_i < n$。
- Subtask 2（20 Points），$n,k \leq 20$。
- Subtask 3（55 Points），$n,k \leq 5\times 10^2$。
- Subtask 4（20 Points），$n,k \leq 5\times 10^3$。

对于 $100\%$ 的数据，$1 \leq n,k \leq 5\times 10^3$，$0 \leq s_i \leq n$。

---

#### 题目背景 ( 续 )
  何等聪明的你一定会站在某棵树下，捧着 $n$ 朵可爱的樱花，像孩子似的向我邀功吧。
  那就别怪我成全你哦，我会轻跳起来，环住你的脖子，揭起你的口罩，尝一尝你的嘴唇。
  你会不会说，“像樱花一样甜”呢？
  反正，我的脸一定已经像樱花一样红了吧。
  ……
  当你看到这封信，别哭呀……
  冬天从这座城市夺走的，春天会补偿我们的。
  待你好了，陪我去看樱花，可好？

Yours,
Yi


title: [USACO07OCT] Super Paintball G

description:
奶牛们最近从玩具商那里，买来了一套仿真版彩弹游戏设备（类似于真人 CS）。Bessie 把她们玩游戏的草坪划分成了 $N \times N$ 的矩阵（$1 \leq N \leq 100$），同时他算出了她的 $K$ 个对手在草地上的位置（$1 \leq K \leq 10^5$），现在你需要帮 Bessie 算些东西。

在这个游戏中，奶牛们用一把枪向八个方向中的任意一个方向射出子弹，这八个方向分别是：正北，正南，正东，正西，东北，东南，西北，西南（东北指北偏东 $45^\circ$，东南，西北，西南同理）。

Bessie 想要你算出，有多少个位置可以让她射到所有对手。特别地，Bessie 可以和她的某一个对手站在同一格子，这时候她可以射到和她同一格子的对手。

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

接下来 $K$ 行，每行两个整数 $R_i, C_i$，表示第 $i$ 头奶牛在第 $R_i$ 行第 $C_i$ 列。可能有两个奶牛在同一位置上。

outputFormat: 输出 Bessie 可以选择的格子数目。


title: 『MdOI R2』Car

description:
在 MdOI 市，为了推行环保，在城区内将限制某些车辆的通行，简称限行。一辆车是否被限行的依据是车牌号和当天的日期。

车牌号的编码方式是这样的：

- 前三位均为大写字母，表示所在的地区。

- 后五位为大写字母或数字，为识别码。**保证至少有一个数字**。

- 车牌号的尾号是从右往左的第一个数字。

MdOI 市在本题的编码方式下前三位是 `MDA`。例如，MdOI 市有一辆识别码为 `6780P` 的车，它的车牌号就是 `MDA6780P`，尾号是 $0$。

在 MdOI 市，限行规则如下：

1. 对于外来车（即前三位编号非 `MDA`），工作日（星期一至星期五）均限行。
2. 对于其他本地车，每天会限行某些尾号的汽车。星期一至星期五的限行尾号如下：

|   日期   |   星期一   |   星期二   |   星期三   |   星期四   |   星期五   |
| :------: | :--------: | :--------: | :--------: | :--------: | :--------: |
| 限行尾号 | $1$ 和 $9$ | $2$ 和 $8$ | $3$ 和 $7$ | $4$ 和 $6$ | $5$ 和 $0$ |

小 C 告诉了你她的车牌号，她想知道，她的车在星期一到星期五中的哪些日期会被限行。请你帮帮她。

inputFormat: 一行一个长度为 $8$ 的字符串，表示小 C 的车牌号。

outputFormat: 输出 $5$ 个数字，每个数字为 $0$ 或 $1$，分别表示星期一至星期五小 C 的车是否被限行。$1$ 表示限行，$0$ 表示不限行。

hint:
【帮助与提示】

为方便选手调试代码，本题额外提供三组样例。由于样例较小，故放在一个剪贴板内。

[附加样例](https://www.luogu.com.cn/paste/g8pxrrh3)

---

【样例解释】

对于样例一，这个车牌号前三位为 `MDA`，因此是本地车牌。而尾号是 $6$，因此周四被限行。

对于样例二，这个车牌号前三位为 `ZJO`，是外地车牌，因此周一至周五均被限行。

---

【数据范围】

**本题采用捆绑测试，即通过一个子任务的所有测试点才能拿到对应的分数。**
|子任务编号|特殊性质|分值|
|:-:|:-:|:-:|
|Subtask 1|前 $3$ 位不是`MDA`|$30$|
|Subtask 2|最后一位一定是数字|$30$|
|Subtask 3|无|$40$|

对于所有数据，满足前三位一定是大写英文字母，后面五位可能包含大写字母或者数字，且至少有一个数字。


title: [USACO07CHN] Summing Sums G

description:
$N$ 头奶牛（$1 \leq N \leq 5 \times 10^4$）刚刚学习了不少密码学知识，终于，她们创造出了属于奶牛的加密方法，由于她们经验不足，她们的加密方法很简单：

第 $i$ 头奶牛掌握着密码的第 $i$ 个数字，起始的时候是 $C_i$（$0 \leq C_i \lt 9 \times 10^7$）。加密的时候，第 $i$ 头奶牛会计算其他所有奶牛的数字和，并将这个和对 $98\,765\,431$ 取模。在所有奶牛计算完成后，每头奶牛都会用自己算的数字代替原来的数字。即，

$$
C_{i}'=(\sum_{k=1}^NC_k-C_i) \bmod 98\,765\,431
$$

这样，她们完成了一次加密。

在十一月，奶牛们把这个加密方法告诉了驼鹿卡门。卡门想了一会后，说：“你们的算法还很原始，为了达到加密效果，你们要重复这个加密过程 $T$ 次（$1 \leq T \leq 1\,414\,213\,562$）”。

奶牛们很懒，于是就把这个任务交给了你。

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

接下来 $N$ 行，第 $i$ 行一个整数 $C_i$。

outputFormat: 输出 $N$ 行，第 $i$ 行一个整数，代表经过 $T$ 次加密后的 $C_i$。


title: [USACO07CHN] The Bovine Accordion and Banjo Orchestra G

description:
FJ 的 $2N$ 头奶牛（$3 \leq N \leq 1000$）准备举办一场音乐会。其中 $N$ 头奶牛是手风琴手，另外 $N$ 头奶牛是班卓琴手，每个手风琴手有一个天才指数 $A_i$（$0 \leq A_i \leq 1000$），每个班卓琴手也有一个天才指数 $B_i$（$0 \leq B_i \leq 1000$）。

FJ 需要给手风琴手和班卓琴手配对。让第 $i$ 位手风琴手和第 $j$ 位班卓琴手配对，能产生 $A_i \times B_j$ 的收益。

不幸的是，FJ 的奶牛都存在一种怪癖：如果第 $i$ 位手风琴手和第 $j$ 位班卓琴手配对，那么第 $i+1 \sim N$ 位手风琴手，不会选择与第 $1 \sim j-1$ 位班卓琴手配对。这给 FJ 的配对计划带来了很多不便。

更糟糕的是，那些失去演出机会的失落的奶牛，为了消解内心的失落感情，会成群结队地到酒吧喝酒。

如果第 $x$ 号手风琴手到第 $y$ 号手风琴手都是失落的（$x-1$ 和 $x+1$ 号手风琴手不存在或是参加了演出），这些奶牛就会去结队去酒吧喝酒，开销为：

$$
(\sum_{k=x}^y A_k)^2
$$

对于班卓琴手，也有类似的规律。

现在 FJ 不得不好好考虑下他的计划了，他想让你算出他的最大的收益。

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

接下来 $N$ 行，每行一个整数 $A_i$。

接下来 $N$ 行，每行一个整数 $B_i$。

outputFormat: 输出 FJ 能获得的最大收益。

hint:
手风琴手 $3$ 和班卓琴手 $1$ 搭配，收益 $25$。

手风琴手 $1,2$ 一块喝酒，花费 $4$。

班卓琴手 $2,3$ 一块喝酒，花费 $4$。

最终收益为 $17$。


title: [USACO07CHN] Treasure G

description:
卡门和他的朋友们最近挖到了一箱财宝，他们打算将这箱财宝埋在公路网的某个节点上。

整个公路网有 $N$ 个节点，这些节点之间由 $N$ 条公路连接。公路都是双向通行的，任何一个节点至少与一条公路相连，且没有节点与超过 $4$ 条公路连接。卡门决定不将财宝埋在有 $4$ 条公路连接的节点上，因为那里交通繁忙，容易被暴露。

卡门将公路网的地图画了出来，并在计划埋藏财宝的地方画了个叉。为了研究最佳埋藏方案，他把所有情况都画了出来，比如下面是一个 $N=4$ 时的所有埋藏情况：

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

他仔细研究后，发现后两种方案是本质相同的。两种地图是本质相同的，当且仅当：

- 宝藏埋藏地点相对应；
- 如果两个节点间有路，则对应节点间也有路；
- 如果两个节点间没有路，则对应节点间也没有路。

现在你需要求出究竟有多少种本质不同的埋藏方案。

inputFormat:
第一行一个整数 $N$（$4 \leq N \leq 10^5$）。

接下来 $N$ 行，每行两个整数 $u,v$（$1 \leq u,v \leq N$），描述一条道路。

保证两个节点间最多有一条道路直接相连，且不存在从节点 $u$ 到节点 $u$ 的道路。

outputFormat: 输出本质不同的埋藏方案数。


title: [USACO06JAN] Dollar Dayz S

description: FJ 到商场买工具。商场里有 $K$ 种工具（$1 \leq K \leq 100$），价格分别为 $1,2,\ldots,K$ 元。FJ 手里有 $N$ 元（$1 \leq N \leq 1000$），必须花完。他有多少种购买方案呢？

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

outputFormat: 输出不同的购买方案数。


title: [USACO06OCT] Another Cow Number Game G

description:
奶牛们在玩一种数字游戏，Bessie 想让你帮她预测一下结果。游戏开始时，Bessie 将得到一个正整数 $N$。此时她的分数为 $0$。

奶牛们按照以下规则对 $N$ 进行变换：

- 如果 $N$ 是奇数，那么将它乘以 $3$ 后再加 $1$。
- 如果 $N$ 是偶数，那么将它除以 $2$。

数字每变换一次，Bessie 就得到 $1$ 分。当 $N=1$ 时，游戏结束。此时的分数就是她的最终得分。

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

outputFormat: 一行，一个整数，为 Bessie 的最终得分。


title: [USACO06OCT] Cows on Skates G

description:
**本题使用 Special Judge。**

Farmer John 把农场划分为了一个 $r$ 行 $c$ 列的矩阵，并发现奶牛们无法通过其中一些区域。此刻，Bessie 位于坐标为 $(1,1)$ 的区域，并想到坐标为 $(r,c)$ 的牛棚享用晚餐。她知道，以她所在的区域为起点，每次移动至相邻的四个区域之一，总有一些路径可以到达牛棚。

这样的路径可能有无数种，请你输出任意一种，并保证所需移动次数不超过 $100000$。

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

接下来 $r$ 行，每行 $c$ 个字符，表示 Bessie 能否通过相应位置的区域。字符只可能是 `.` 或 `*`。

- `.` 表示 Bessie 可以通过该区域。
- `*` 表示 Bessie 无法通过该区域。

outputFormat:
若干行，每行包含两个用空格隔开的整数，表示 Bessie 依次通过的区域的坐标。

显然，输出的第一行是 `1 1` ，最后一行是 `r c`。

相邻的两个坐标所表示的区域必须相邻。

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

对于 $100\%$ 的数据，$1\le r\le 113$，$1\le c\le 77$。

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

**【样例说明】* *

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

图为样例输出的示意图。答案不唯一。


title: [USACO06OCT] Cow Pie Treasures G

description:
奶牛们制作了一些藏有金币的馅饼，并把它们排成了一个 $r$ 行 $c$ 列的矩阵。现在，你需要从坐标为 $(1,1)$ 的馅饼旁移动到坐标为 $(r,c)$ 的馅饼旁。对于每次移动，你必须向右移动一列，并且行数的变动不能超过 $1$。即如果你处于坐标为 $(x,y)$ 的馅饼旁，你只能移动到坐标为 $(x-1,y+1)$，$(x,y+1)$ 或 $(x+1,y+1)$ 的馅饼旁。在一个馅饼旁停留时，你可以拿走其中所有的金币。当然，你一定不愿意中途离开矩阵而放弃这些金币。

奶牛们把标有矩阵中每一块馅饼所藏金币数的表格交给了你。你想知道按照以上规则，自己最多能拿到多少金币。

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

接下来 $r$ 行，每行 $c$ 个整数，表示矩阵中每一块馅饼所藏金币数 $t$。

outputFormat: 一行，一个整数，表示你能拿到的最大金币数。

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

对于 $100\%$ 的数据，$1\le r,c\le 100$，$1\le t\le 25$。

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

**【样例说明】**

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

样例给出的矩阵如图所示。

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

这是一种合法的移动方式。你可以拿到 $47$ 枚金币。

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

在这个矩阵中你最多能拿到 $50$ 枚金币，路线如图所示。


title: 准备战斗，选择你的英雄

background: zjf，被 NOIP 普及组初赛戏耍，pj 1= -> 初赛三等，愤恨地离开了 OI，深陷中考的泥潭当中。据说，他颓废是因为玩多了 [OW](https://ow.blizzard.cn/home) 这款游戏。

description:
目前，游戏共有 $31$ 个英雄，每局可以派 $6$ 个英雄上场。实际能使用的英雄数将会小于 $31$。简单地假设，每位英雄对团队的贡献可以用一个正整数 $v_i$ 表示。团队的总能力等于所有英雄的贡献之和。特别地，对于 $m$ 组特定的英雄，他们一起出现会让团队总能力提高 $x_i$。

**另注：英雄组合可以重复，若重复请多次计数。**

inputFormat:
第一行两个整数 $n$，$m$，表示可选英雄个数和特定的组合数。
接下来 $n$ 行，每行先给出第 $i$ 个英雄的名字，然后再输入一个整数 $v_i$。
接下来 $m$ 行，每行两个字符串 $a$，$b$ 和一个整数 $x_i$，表示若英雄 $a$ 和英雄 $b$ 一起出现时总能力提高 $x_i$。
**保证：$a$ 和 $b$ 不是同一个英雄。**

outputFormat: 一个整数，表示团队能力值的最大值。

samples:
7 0
Sigma 10
Orisa 10
Mei 10
Reaper 10
Moira 10
Lucio 10
Doomfist 1

samples:
8 2
Pharah 5
Mercy 5
Reinhardt 10
DVA 10
SOLDIER:76 12
Torbjorn 5
Anna 8
Baptiste 10
Pharah Mercy 20
Anna Pharah 5

hint:
#### 样例 1 解释
我们应该选择前 $6$ 名英雄。

---

#### 样例 2 解释
我们应该选择 Pharah、Mercy、Reinhardt、DVA、SOLDIER:76、Anna

---

#### 数据范围
对于 $40\%$ 的数据，$m=0$。
对于 $100\%$ 的数据，$6\le n \le 30$，$0\le m \le 30$，*$1\le x_i,v_i \le 100$*，英雄名字长度 $\le 10$，字符集包括大小写字母、数字以及冒号（ `:` ）。每个英雄的名字各不相同。


title: 「HMOI R1」不知道是啥的垃圾题

background: 由于这是崩坏 3 round，所以这里应该有一个关于崩坏三的背景。然而 fz 不玩崩坏 3，而且他实在是太屑了，所以这题就变成了一道裸题。

description:
要求维护一个可重集，支持三种操作：
1. 插入一个自然数对；
1. 删除一个自然数对，保证这个数对之前在集合中；
1. 给定一个自然数对 $(x,y)$，问集合中有多少个数对 $(a,b)$ 满足 $x\operatorname{xor}a>y\operatorname{xor}b$，其中 $\operatorname{xor}$ 表示按位异或运算。

本题中所有“数对”均指有序数对。

inputFormat:
第一行一个自然数 $M$ 代表操作数。

接下来 $M$ 行，每行一个操作，格式如下：
- `1 x y` 表示插入自然数对 $(x,y)$；
- `2 x y` 表示删除自然数对 $(x,y)$，保证此时 $(x,y)$ 在集合中至少出现了一次；
- `3 x y` 表示查询自然数对 $(x,y)$。

outputFormat: 共 $M$ 行，每个询问输出一行一个自然数，表示询问的答案。

hint:
对于样例，第一次查询时集合里没有任何数对，所以答案为 $0$。

第二次查询时，集合为 $\{(3,2),(4,5)\}$，$6\operatorname{xor}3=5>0=2\operatorname{xor}2$，$6\operatorname{xor}4=2<7=2\operatorname{xor}5$，故满足条件的数对只有 $(3,2)$ 一个，答案为 $1$。

第三次询问时，集合为 $\{(4,5)\}$，没有满足条件的数对，答案为 $0$。

------------
对于所有数据：
- $0 \le M \le 2 \times 10^5$；
- $0 \le x, y \le 10^{18}$。

--------

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

| No.  | Constraints                 | Score |
| ---- | --------------------------- | ----- |
| $1$  | $M \le 2000$ | $10$  |
| $2$  | $x, y < 8$          | $20$  |
| $3$  | $x, y \le M$          | $30$  |
| $4$  | No further constraints      | $40$  |

-------

- Idea: FZzzz
- Solution: FZzzz
- Code: FZzzz
- Data: FZzzz


title: [USACO06NOV] Round Numbers S

description:
如果一个正整数的二进制表示中，$0$ 的数目不小于 $1$ 的数目，那么它就被称为「圆数」。

例如，$9$ 的二进制表示为 $1001$，其中有 $2$ 个 $0$ 与 $2$ 个 $1$。因此，$9$ 是一个「圆数」。

请你计算，区间 $[l,r]$ 中有多少个「圆数」。

inputFormat: 一行，两个整数 $l,r$。

outputFormat: 一行，一个整数，表示区间 $[l,r]$ 中「圆数」的个数。


title: [COCI2019-2020#6] Konstrukcija

background: 题目翻译来自 [LOJ3268](https://loj.ac/problem/3268)。

description:
**译自 [COCI 2019/2020 Contest #6](https://hsin.hr/coci/archive/2019_2020/) T3.** ***[Konstrukcija](https://hsin.hr/coci/archive/2019_2020/contest6_tasks.pdf)***

令 $G$ 为一个有向无环图。若 $G$ 的不同顶点 $c_1,c_2,c_3,\ldots c_n$ 满足有一条从 $c_1$ 到 $c_2$ 的路径，有一条从 $c_2$ 到 $c_3$ 的路径，……还有一条从 $c_{n-1}$ 到 $c_n$ 的路径，则称数组 $C = (c_1,c_2,c_3,\ldots c_n)$ 为一个从 $c_1$ 开始，在 $c_n$ 结束的有序数组。
注意对于 $C$ 中任意的两个相邻的元素 $c_i,c_{i+1}$ 不必有直接连接的边，只需要有一条路径即可。

同时，我们定义有序数组 $C = (c_1,c_2,c_3,\ldots c_n)$ 的长度 $\mathrm{len}(C) = n$。因此，一个有序数组的长度即为其中包含的顶点个数。
注意可以存在一个长度为 $1$，从同一个点开始并结束的有序数组。

并且，我们再定义有序数组 $C = (c_1,c_2,c_3,\ldots c_n)$ 的符号 $\mathrm{sgn}(C) = (-1)^{\mathrm{len}(C)+1}$。
对于 $G$ 中的顶点 $x,y$，我们用 $S_{x,y}$ 表示所有从 $x$ 开始并在 $y$ 结束的有序数组的集合。

最后，我们定义顶点 $x,y$ 之间的矛盾值为 $\mathrm{tns}(x,y) = \sum\limits_{C \in S_{x,y}} \mathrm{sgn}(C)$。
也就是说，顶点 $x,y$ 之间的矛盾值等于所有从 $x$ 开始并在 $y$ 结束的有序数组的符号之和。

给定一个整数 $K$，你需要构造一个最多 $1000$ 个点，$1000$ 条边的有向无环图满足 $\mathrm{tns}(1,N) = K$，其中 $N$ 为顶点个数。
顶点以正整数 $1\ldots N$ 编号。

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

outputFormat:
第一行，两个整数 $N,M$ 表示你构造出的有向无环图的点数与边数。
以下 $M$ 行中，第 $i$ 行包含两个不同的整数 $X_i,Y_i$，表示第 $i$ 条边从 $X_i$ 连向 $Y_i$。每条边应最多出现一次。
并且，你的方案需要满足任意两点的矛盾值的绝对值不超过 $2^{80}$。
若有多解，随意输出一解即可。


title: [COCI2019-2020#6] Skandi

background:
题目翻译来自 [LOJ3269](https://loj.ac/problem/3269) 。

**由于洛谷评测机原因，数据有删改。**

description:
**译自 [COCI 2019/2020 Contest #6](https://hsin.hr/coci/archive/2019_2020/) T4.** ***[Skandi](https://hsin.hr/coci/archive/2019_2020/contest6_tasks.pdf)***

Dragica 不仅是当地的一个半专业保龄球队的队长，还是一位充满激情的厨师。除此之外，他还是克罗地亚数一数二的填字游戏（crossword）玩家。填字游戏是一个在 $N\times M$ 的网格上游玩的游戏。在游戏开始前，部分格子已经填上了字母，作为至多两题的起点，而玩家需要根据给出的提示以水平向右或竖直向下的方向在剩下的格子填上答案。在这里，一题的答案定义为从该题起点沿提示指定方向直至网格边界或另一题起点之前的部分。如果一题的起点右边一格是空的，则该题在水平方向上存在一题；类似的，如果一题的下面一格是空的，则该题在竖直方向上存在一题。

Dragica 当然知道答案啦，但他有点鸽，想让你帮他找出完成某个填字游戏最少回答的题目数。

inputFormat:
第一行两个空格分隔的整数 $N,~M$，含意见题目描述。

接下来 $N$ 行每行 $M$ 个字符 `0` 或 `1`，其中 `0` 表示这是个待填充答案的空格，而 `1` 表示该格已填有字符，是至多两题的起点。保证输入存在至少一个 `0` ，且第一行和第一列均为 `1`。

outputFormat:
第一行输出完成该次填字游戏的最小答案数 $X$。

接下来 $X$ 行每行以 `r c dir` 的格式回答一个问题，其中 `r` 表示题目的行号，`c` 表示题目的列号，`dir` 为 `DESNO` （克罗地亚语中的右）和 `DOLJE` （克罗地亚语中的下）之一，表示 Dragica 回答问题的方向。

如果有多解，输出任意一个。

samples:
4
1 2 DOLJE
4 4 DOLJE
5 3 DOLJE
3 1 DESNO

samples:
14
5 2 DOLJE
5 8 DOLJE
8 3 DOLJE
2 1 DESNO
3 1 DESNO
3 5 DESNO
4 1 DESNO
4 4 DESNO
5 3 DESNO
6 3 DESNO
7 1 DESNO
7 5 DESNO
8 3 DESNO
9 4 DESNO

hint:
#### 样例 $3$ 解释：
下图展示了样例中的填词游戏，其中黑色的格子表示开始时已经填了字符的格子，在图下方所示的表中你可以看到给出的横着填和竖着填的提示。注意，已经填了字符的格子可以是零题、一题（例如第 $8$ 和 $13$ 题）或两题（例如第 $10$ 和 $12$）题的起点。要解出它，你至少需要知道 $14$ 题的答案，试试看看你会吗？~~（疑问语气）~~

*译者注：以下图片经过高清重制。中文的 crossword 没啥意义，就不翻译了。*

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

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

-----

#### 数据范围：

对于 $100\%$ 的数据，有 $2\le N,~M\le 500$。

各子任务限制见下表：

|子任务|分值|特殊限制|
|:-:|:-:|:-:|
|1|16|至多 $9$ 个格子开始前填了字符|
|2|30|$N\le 500,~M\le 10$|
|3|54|无特殊限制|


title: 「Wdsr-1」笨蛋结构

background: 众所周知，琪露诺是笨蛋。

description:
琪露诺希望维护一个长度为 $n$ 的整数序列 $a$，初始值都为 $0$。

现在琪露诺想要进行 $q$ 次操作，每次选择序列中的一段区间 $[s,s+l-1]$ 并给出两个数字 $w,k$，使对所有的 $i \in [1,l]$，$a_{s+i-1}$ 加上 $w\times i^k$ 。

琪露诺不希望 $k$ 很大，因此她给出了一个整数 $m$，满足 $0\le k\le m$。

为了不让头脑简单的琪露诺感到困惑，你只需要输出 依次进行完所有操作后，序列中的每个数字对 $2^{64}$ 取模（即 $\text{unsigned long long}$ 自然溢出）后的结果即可。

为了帮助你更好的理解题意，这里给出一段伪代码：

$$\def{\b}#1{\textbf{ #1 }}\def{\t}#1{\text{ #1 }}\def{\s}{\quad}
\def{\l}{\underline{\kern{300pt}}\cr[-10pt]}
\def{\r}{\overline{\underline{\kern{300pt}}}}
\begin{aligned}
&\r\cr&\b{Algorithm:}\t{An easy structure}\cr[-13pt]&\l\cr
&\begin{aligned}
    \t{1.}&\b{input}n,m,q \cr
    \t{2.}&\b{for}i=1\b{to} q \b{do} \cr
    \t{3.}&\s\b{input} s,l,w,k \cr
    \t{4.}&\s\b{for} j=1 \b{to} l \b{do}\cr
    \t{5.}&\s\s a[s+j-1] \gets a[s+j-1]+w\times \t{pow}(j,k) \cr
    \t{6.}&\s\b{end}\cr
    \t{7.}&\b{end}\cr
    \t{8.}&\b{for} i=1 \b{to} n \b{do}\cr
    \t{9.}&\s\b{output} a[i]\cr
    \t{10.}&\b{end}\cr
    \end{aligned}\cr[-12pt]
&\r\end{aligned}
%Made by @离散小波变换° .
%You can find his contributions by searching "JoesSR".
$$
其中 $\rm pow(a,b)$ 的含义为 $a^b$。

inputFormat:
请调用下方代码的 `input(n,m,q,S,L,W,K)` 来输入 $n,m,q,s_i,l_i,w_i,k_i$。下标**从一开始**。

其中 $s,l,w,k$ 的含义与题目描述保持一致。

outputFormat: 请调用下方代码的 `output(n,R)` 进行输出。其中 $R_i$ 为所有操作结束后的数列，下标**从一开始**。


title: [COCI2010-2011#1] LJUTNJA

description:
幼儿园的小孩们收到了一个有 $m$ 颗糖果的大包裹，现在要把这些糖果分给 $n$ 个小孩。

每一个小孩都给出了一个期望的糖果数，如果没有达到他的期望值 $a_i$，小孩就会生气。每差一个糖果，小孩的生气指数就会增加，可以认为他生气的程度等于他少得到的糖果数的平方。

比如，Mirko 想要得到 $32$ 个糖果，但是只得到了 $29$ 个。他少了 $3$ 个，所以他的生气指数是 $9$。不幸的是，糖果数不足以满足所有小孩的期望。所以我们应该采取最优的分配方法，使得最后小孩们的生气指数的和最小。

inputFormat:
输入数据共 $n+1$ 行。

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

接下来 $n$ 行，每行一个整数，第 $i+1$ 行的整数表示第 $i$ 个小朋友期望值 $a_i$。

outputFormat:
输出数据共一行。

一行一个整数，表示最小的总生气指数。

hint:
#### 样例输入输出 1 解释

共 $10$ 颗糖果，共 $4$ 人，给每一个同学他所需要的糖果数减 $1$，也就是依次给 $3,4,1,2$ 颗，这样的话每人少一颗，每人的生气指数就是 $1^2=1$，$4$ 个人就是 $1 \times 4=4$，答案 $4$ 是最优方案。

---

#### 数据规模与约定

- 对于 $40 \%$ 的数据，保证 $n \leq 5000$，$m \leq 30$，结果不超过 $5 \times 10^8$。
- 对于 $100 \%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq 2 \times {10}^9$，结果不超过 $2^{64}-1$。


title: [BalticOI 2019 Day1] 潜艇

background: **译自 [BalticOI 2019](http://boi2019.eio.ee/tasks/) Day1 T2.** ***[Nautilus](http://boi2019.eio.ee/wp-content/uploads/2019/04/nautilus.en_.pdf)***

description:
有一艘潜艇正在海洋中秘密航行。

海洋是一个 $R \times C$ 的网格，其中 `#` 代表岛屿，`.` 代表水域，潜艇只能在水域中航行。

每分钟，潜艇会发出一个无线电信号，代表潜艇要航行的方向。方向由如下字母表示：北（N），东（E），南（S），西（W）。

现在监听者已经架设了一台拦截潜艇信号的雷达。在最近的 $M$ 分钟，雷达收集到了 $M$ 个信号，由一个长度为 $M$ 的字符串表示，例如 `WS?EE??`。收集到的信号有些无法解码，用 `?` 表示。

监听者并不知道潜艇最初的位置，但想要借助地图计算出潜艇的当前位置。请你帮助监听者计算出潜艇当前可能的位置共有几种。

inputFormat:
输入第一行包含三个整数 $R,C,M$。

接下来 $R$ 行，每行 $C$ 个字符，描述海域地图。

最后一行是一个长度为 $M$ 的字符串，代表了监听者监听到的信号。保证字符串中只含有 `N`，`E`，`S`，`W`，`?` 这几种字符。

outputFormat: 输出一个整数：潜艇当前可能的位置有几种。

hint:
各子任务的分值与数据规模如下：

- 子任务 1（29 分）：$1 \leq R,C,M \leq 100$，监听到的信号中没有 `?`。
- 子任务 2（37 分）：$1 \leq R,C,M \leq 100$。
- 子任务 3（34 分）：$1 \leq R,C \leq 500$，$1 \leq M \leq 5000$。


title: [BalticOI 2019 Day1] 山谷

background: **译自 [BalticOI 2019](http://boi2019.eio.ee/tasks/) Day1 T3.** ***[Alpine valley](http://boi2019.eio.ee/wp-content/uploads/2019/04/valley.en_.pdf)***

description:
在阿尔卑斯山谷中，有 $N$ 个村庄，编号为 $1 \ldots N$，这些村庄通过 $N-1$ 条边连接起来，形成了一个树型结构。

虽然任意两个村庄间都能相互抵达，但路途花费的时间可能令人难以接受，尤其是当你想要购买一些生活必需品的时候——因为所有村庄中，只有其中 $S$ 个村庄有商店。

今年冬天，由于大雪的原因，情况变得更糟。因此，你需要到达 $E$ 号村庄——那里有连接山区和外界的唯一通道，亦或是在山谷中的商店里购买足够接下来几个月生活的物资。今天早上，你在收音机里听到了所有道路中有一条道路无法通行的消息，但是你并不知道具体是哪一条道路。

你现在想知道你和你的朋友是否可以离开山谷，如果不能离开，则需要知道你们离最近商店的距离。由于你还不知道哪条道路无法通行，并且你的朋友们居住在不同的村庄，因此你需要回答 $Q$ 组询问，每组询问给出一条被封锁的道路和你朋友所在村庄的位置。

inputFormat:
输入第一行包含四个整数 $N,S,Q,E$。其中 $N$ 代表村庄数目，$S$ 代表有商店的村庄的数目，$Q$ 代表你需要回答的询问数，$E$ 代表连接山区和外界的村庄的编号。

接下来 $N-1$ 行，每行包含三个整数 $A,B,W$，代表村庄 $A$ 与村庄 $B$ 之间有一条长度为 $W$ 的道路。

接下来 $S$ 行，每行包含一个整数 $C$，代表 $C$ 号村庄有一个商店。数据保证同一个村庄最多只有一个商店。

最后 $Q$ 行，每行两个整数 $I,R$，询问当 $I$ 号道路（按输入顺序编号）无法通行时，从 $R$ 号村庄出发能否离开山谷，如果不能，则询问其离最近商店的距离。

outputFormat: 输出包含 $Q$ 行，第 $i$ 行输出第 $i$ 组询问的答案。更具体地说，如果能离开山谷，输出 `escaped`；如果不能离开山谷的话，输出 $R$ 号村庄离最近商店的距离；如果既不能离开山谷，也不能到达任意一个商店的话，输出 `oo`。

hint:
### 样例解释 1

本样例对应下图：

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

在该图（以及接下来一张图）中，用灰色标记的点为商店所在点，图上的边按照「编号 / 长度」的顺序进行标注。

### 样例解释 2

本样例对应下图：

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

### 子任务

对于所有数据，均满足：$1 \leq S,E,A,B,C,I,R \leq N$，且 $1 \leq W \leq 10^9$。

各子任务的分值与数据规模如下：

- 子任务 1（9 分）：$1 \leq N \leq 100,1 \leq Q \leq 10000$，且所有道路均满足 $|A-B|=1$。
- 子任务 2（27 分）：$1 \leq N \leq 1000,1 \leq Q \leq 1000$。
- 子任务 3（23 分）：$1 \leq N \leq 10^5,1 \leq Q \leq 10^5$，且 $S=N$。
- 子任务 4（41 分）：$1 \leq N \leq 10^5,1 \leq Q \leq 10^5$。


title: [BalticOI 2019 Day2] 汤姆的餐厅

background: **译自 [BalticOI 2019](http://boi2019.eio.ee/tasks/) Day2 T1.** ***[Tom's Kitchen](http://boi2019.eio.ee/wp-content/uploads/2019/05/kitchen.en_.pdf)***

description:
*Tom's Kitchen* 是一家非常受欢迎的餐厅，其受欢迎的原因之一是每份菜都由至少 $ K $ 名厨师进行准备。今天有 $ N $ 份菜需要准备，第 $ i $ 份菜的准备时间是 $ A_i $ 小时。

Tom 可以雇佣 $ M $ 名厨师，厨师 $ j $ 最多可以工作 $ B_j $ 小时。此外，即使厨师 $ j $ 的工作时间不到 $ B_j $ 小时，他也会得到工作 $ B_j $ 小时的报酬。一名厨师可以花不同的时间准备不同的菜，但是每一道菜都需要由至少 $ K $ 名厨师准备，并且他们花的时间总和恰好为 $ A_i $。当一名厨师准备菜品时，他总会花正整数小时。

Tom 需要一套最优的雇佣厨师方案，以使得厨师不工作就获得报酬的小时数（即所有雇佣厨师的总工作时间上限与准备所有菜的总时间之差）尽可能小。

inputFormat:
第一行包含三个正整数：$ N,M,K $。

第二行包含 $ N $ 个整数 $ A_i $，第三行包含 $ M $ 个整数 $ B_j $。

outputFormat: 如果不存在一套方案可以完成所有菜的准备工作，输出 `Impossible`。否则输出一个整数，代表厨师不工作就获得报酬的小时数的最小值。

hint:
### 样例解释 1

Tom 需要雇佣这两位厨师来完成所有菜的准备工作。准备所有菜的时间为 $ 5 $ 小时，但 Tom 需要支付 $ 3+4=7 $ 小时的费用，即厨师不工作就能得到 $ 2 $ 小时的工资。

### 样例解释 2

准备一份菜需要至少两位厨师，但只能雇佣一位厨师，因此不能完成准备工作。

### 样例解释 3

第三份菜无法由三位厨师来准备，因为准备第三份菜的时间只有 $ 2 $ 小时（这意味着如果由三名厨师准备第三份菜的话，至少有一位厨师的准备时间是 $ 0 $ 小时，而这是不符合题目要求的）。

### 子任务

各子任务的分值与数据规模如下：

- 子任务 1（9 分）：$ 1 \leq N,K \leq 300, 1 \leq M \leq 2, 1 \leq A_i,B_j \leq 300 $；
- 子任务 2（22 分）：$ 1 \leq N,K \leq 300, 1 \leq M \leq 15, 1 \leq A_i,B_j \leq 300 $；
- 子任务 3（20 分）：$ 1 \leq N,M,A_i,B_j \leq 300, K=1 $；
- 子任务 4（21 分）：$ 1 \leq N,M,K,A_i,B_j \leq 40 $；
- 子任务 5（28 分）：$ 1 \leq N,M,K,A_i,B_j \leq 300 $。


title: [BJWC2014] 数据

description:
为了写论文，```Alex``` 经常要整理大量的数据。这一次，```Alex``` 面临一个严峻的考验：他需要实现一个数据结构来维护一个点集。

现在，二维平面上有 $N$ 个点。

```Alex``` 需要实现以下三种操作：

1. 在点集里添加一个点；

2. 给出一个点，查询它到点集里所有点的曼哈顿距离的最小值；

3. 给出一个点，查询它到点集里所有点的曼哈顿距离的最大值。

两个点的曼哈顿距离定义为它们的横坐标差的绝对值与纵坐标差的绝对值的和。

这么困难的问题，```Alex``` 当然不会做，只好再次请你帮忙了。

inputFormat:
第一行包含一个整数 $N$，表示点集最初的点数。

接下来 $N$ 行，每行两个整数，依次表示每个点的横坐标和纵坐标。

第 $N+2$ 行包含一个整数 $Q$，表示询问的数目。

接下来 $Q$ 行，每行三个整数，依次表示询问的类型，点的横坐标和纵坐标。$0$ 类型表示添加一个点，$1$ 类型表示查询到该点的曼哈顿距离的最小值，$2$ 类型表示查询最大值。

outputFormat: 输出若干行，依次表示每个查询操作的答案。

hint:
对于前 $20 \%$ 的数据：$1\le N , Q\le 10^3$

对于前 $100 \%$ 的数据： $1\le N , Q \le 10^5$；

点的坐标是不超过 $10^9$ 的非负整数。


title: [JDWOI-1] 蜀道难

background:
蜀道难，难于上青天……

蜀道之所以难，就是因为山路崎岖不平。

description:
小 K 和小 M 也模拟了蜀道难。在蜀道难中，有 $n$ 座山，每座山高度为 $h_i$。小 K 和小 M 有 $m$ 种魔法，每一次膜法可以把连续 $l_i$ 座山的高度抬高或压低 $1$，同时消耗 $c_i$ 点体力。

现在，小 K 和小 M 想让蜀道难的 $n$ 座山的高度不下降，这样蜀道就不难了。请问他们最少需消耗多少体力？

**注**：所有时候山的高度都不能为负。

inputFormat:
第一行两个整数 $n,m$，表示山的数量和膜法数量。

第二行 $n$ 个整数 $h_i$，表示山的高度。

接下来 $m$ 行，每行一个字符和两个整数 $w_i, l_i, c_i$，描述一种膜法（如果 $w_i$ 为 $+$，代表抬高；如果 $w_i$ 为 $-$，代表压低）。

outputFormat:
一行一个整数，表示最小消耗的体力。

如果无解，输出 $-1$。

hint:
### 样例解释

使用 $1$ 体力值将第三座山升高 $1$。

### 数据范围

- 对于 $10\%$ 的数据，$1\leq n,m \leq 10$；
- 对于另外 $30\%$ 的数据，$1\leq n,m \leq 20$；
- 对于另外 $10\%$ 的数据，$m=1$；
- 对于所有的数据，$1\leq n, m \leq 200$，$1\leq l_i \leq n$，$1\leq h_i, c_i \leq 10^3$。


title: 「P6156 简单题」加强版

background:
[原题链接](https://www.luogu.com.cn/problem/P6156)

此题在原题基础上，加上了多测，更改了模数，同时为了彻底卡掉非线性预处理，开大了数据范围。

可能有点卡常。

description:
$T$ 组询问。一开始给定一个常数 $K$。每次询问单独给定 $n$。请你求出：

$$\sum_{i=1}^{n}\sum_{j=1}^{n} (i+j)^K \gcd(i,j) \mu^2(\gcd(i,j)) \pmod {2^{32}}$$

inputFormat:
第一行三个正整数 $T,N,K$，分别表示询问组数、询问的 $N$ 的最大值、以及给定的常量。

接下来 $T$ 行，每行一个正整数表示这组询问的 $n$ 是多少。

outputFormat: $T$ 行，每行一个非负整数，表示询问当前给定的 $n$，题面的式子计算出的结果是多少。

hint:
一共有 $5$ 组测试点。第 $i$ 组测试点满足：$N=10^{i+2}$。

对于所有测试点，满足：$T = 10^4$，$1 \leq K < 2^{31}$。


title: 『MdOI R3』Fallen Lord

background: 统治着世界，统治着寂寞。

description:
L 国有 $n$ 个城市，它们之间有 $n-1$ 条道路，形成了一棵树的结构。

国王 L 派遣了一些军队来驻守这些道路，驻守每一条道路的军队战斗力都可以被量化为 $[1,m]$ 中的整数。

每个城市都有一个城主，第 $i$ 个城主有一个忍耐度 $a_i$。如果国王 L 在与第 $i$ 个城市相连的所有道路上驻守的军队战斗力的**中位数**超过了**城主**的忍耐度，那么**城主**就会认为国王不信任他而产生谋反的心理。

国王 L 当然不希望有人造反，但他又想使驻守道路的军队的总战斗力**最大**来保证国防安全。现在他找到了 L 国最强的 OIer —— 您，去来帮助他解决这个问题。

如果无论如何安排军队都会有人想要造反，那么输出 `-1`。

**注：对于任意 $k$ 个数，它们的中位数是将这些数从小到大排序后第 $\left\lfloor\dfrac{k}{2}\right\rfloor+1$ 个数。**

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

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

接下来 $n-1$ 行，每行两个数 $u_i,v_i$，表示一条直接连接城市 $u_i$ 与城市 $v_i$ 的道路。

**输入数据保证构成一棵树**。

outputFormat: 一行一个整数，表示最大的总战斗力。


title: [SBCOI2020] 人

background:
梦
做着同一个梦
每一天都做的梦
没有终结的梦......
咦...这里...是哪里？
周围漫天是如雪花般飘落的的碎片。
天空明亮的光芒又一次掠过这些碎片，照在地上。
这些碎片像是永无尽头的围巾一般，围在她的四周，
在她的身后延伸到世界的尽头，诉说着一段段破碎的记忆......
......
这...刚才...是梦吗？
看来我又做了一个梦...
不知不觉，离开这个小镇已经这么久了啊...
但是...总感觉这个小镇...无法忘记...
刚才看到的到底是什么？
为什么呢?
![](https://cdn.luogu.com.cn/upload/image_hosting/xltdmgq1.png)
总觉得我需要回去一次，
回到......一切开始的地方......

description:
她的梦中有 $2m$ 块记忆碎片，编号为 $1,2,\cdots,2m$，以及 $a$ 块白色碎片和 $b$ 块黑色碎片。

她隐约记得她要在编号为奇数的记忆碎片中选出 $a$ 块白色碎片组成一段记忆，在编号为偶数的记忆碎片中选出 $b$ 块黑色碎片组成一段记忆，且选出的记忆碎片编号两两不相邻。

她想要知道一共有多少种这样的选法。也就是，在 $1-2m$ 中选出 $a$ 个奇数， $b$ 个偶数，并且选出的数两两不相邻的方案数。

由于答案可能很大，她只需要答案对于 $998244353$ 取模的结果。

inputFormat:
**本题有多组数据。**

第一行为数据组数 $T$。

接下来 $T$ 行，每行三个整数 $m,a,b$。

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


title: [SBCOI2020] 小镇

background:
在人们不知道的地方，有一个小镇。
一个，连名字都说不上来的小镇。
季节再度进入冬季，
那个属于雪的季节。
在那雪下，埋葬着的，
是只属于这个小镇的梦，与传说。
......
“又到了冬天啊！”
“是啊！周围都变成白茫茫的一片了呢...”
“唉，要是这样的日子能够永远持续下去该有多好啊。”
“啊，永远...”
“不过，世间又有什么是永远呢。如同雪的消融，洁白地融入大地，还来不及让人品味，如此无奈，又如此纯净......”

在雪中，一幢幢房屋间的灯光散发出温暖的光芒。
![](https://cdn.luogu.com.cn/upload/image_hosting/j728ebas.png)
“以后我们还能在一起看雪吗？”
“当然，一直可以......”

description:
小镇可以看作是一个 $n \times n$ 的网格，其中有 $k$ 个格子是房屋。
小镇里面还有灯。每两个相邻的格子之间有一盏灯。

如果两幢房屋**相邻**，那么这两幢房屋之间的灯就会点亮。
请问这座小镇一共有多少盏灯被点亮。

注意，本题中相邻指有公共边。

inputFormat:
第一行两个整数 $n,k$，表示网格边长以及房屋数量。
接下来 $k$ 行每行两个整数 $x,y$，表示房屋的坐标。

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

hint:
#### 样例解释

![](https://cdn.luogu.com.cn/upload/image_hosting/tbjkl3ul.png)
如图，阴影格子为房屋，被描红的边为灯。

#### 数据范围

对于 $30\%$ 的数据，$1 \leq n,k \leq 100$。
对于 $80\%$ 的数据，$1 \leq n,k \leq 5000$。
对于 $100\%$ 的数据，$1 \le n,k \le 10^5$。