Alice and Bob (and string): Double Menace
Alice 和 Bob 正在玩一个游戏。最初他们有一个字符串 $s$ 及其子串 $t$。每位玩家的回合包括在 $t$ 的左侧添加一个任意字母 $c_l$，并在 $t$ 的右侧添加一个任意字母 $c_r$，使得 $t$ 仍然是 $s$ 的子串。无法进行有效移动的玩家输掉比赛。
Alice 先手。在进行第一次移动之前，她有权选择初始字符串 $t$。当然，Alice 想要作弊，她会选择一个能保证她获胜的字符串 $t$（假设双方都采取最优策略），但她不想让 Bob 怀疑。因此，Alice 决定在所有可能的获胜初始字符串 $t$ 中，选择字典序第 $k$ 小的字符串。请帮助 Alice！
输入格式
第一行包含一个由小写英文字母组成的字符串 $s$ ($1 \le |s| \le 10^5$)。 第二行包含一个整数 $k$ ($1 \le k \le 10^{10}$)。
输出格式
如果合适的字符串 $t$ 的选项少于 $k$ 个，打印 “no solution”。否则，打印字典序第 $k$ 小的字符串。如果答案是空字符串，则打印 “-”。
样例
样例输入 1
abac 3
样例输出 1
b
样例输入 2
rndstr 1
样例输出 2
-
样例输入 3
abc 10
样例输出 3
no solution
说明
对于 $s = \text{abac}$，获胜字符串为 $\{-, \text{a}, \text{b}, \text{ba}\}$。
Bag of Bags
一位数学家每天去商店带回一个包。这些包既美观又实用，所以数学家想把它们留作将来使用。他还想把他的包整理好：大包放大包，小包放小包。
第 $i$ 天带来的包（我们简称为包 $i$）在折叠状态下占用体积 $a_i$，在展开状态下占用体积 $b_i$（自然地，$a_i < b_i$）。如果 $a_i < b_j$，则包 $i$ 可以放入包 $j$ 中。数学家认为，如果包 $i$ 可以放入包 $j$ 中，且包 $j$ 也可以放入包 $i$ 中，那么包 $i$ 和包 $j$ 是相等的（应该放在一起）。
不幸的是，有时会出现三个包 $i, j, k$，使得包 $i$ 和包 $j$ 相等，包 $j$ 和包 $k$ 相等，但包 $i$ 和包 $k$ 不相等！这让数学家非常害怕，因为它与他所知的等价关系相矛盾。如果向他的收藏中添加一个新包会导致上述矛盾的三元组，他就把这个新包扔掉，否则他就保留它（并且此后永远不会扔掉它）。
你的任务是确定每个包是被保留还是被扔掉。
输入格式
第一行包含一个整数 $n$ —— 包的数量 ($1 \le n \le 3 \cdot 10^5$)。 接下来的 $n$ 行描述这些包。第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ —— 分别为包 $i$ 在折叠和展开状态下的尺寸 ($1 \le a_i < b_i \le 10^9$)。
输出格式
打印 $n$ 行。第 $i$ 行应包含单词 “KEPT”（如果数学家保留了包 $i$），否则打印 “THROWN AWAY”。
样例
样例输入 1
10 1 4 3 5 6 8 7 9 1 2 6 7 4 7 5 7 5 8 9 10
样例输出 1
KEPT KEPT KEPT KEPT THROWN AWAY THROWN AWAY THROWN AWAY THROWN AWAY KEPT KEPT
Circle Union
如果平面上存在一个点，该点位于每个圆的内部或边界上，则称该圆的排列是有趣的。一个排列的覆盖区域由位于至少一个圆的内部或边界上的所有点组成。
考虑 $n$ 个半径分别为 $r_1, \dots, r_n$ 的圆。求在一个有趣的排列中，这些圆所覆盖区域的最大可能面积。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 10^4$)。 第二行包含 $n$ 个整数 $r_1, \dots, r_n$ ($1 \le r_i \le 10^3$)。
输出格式
打印一个实数 —— 最大可能的覆盖面积。如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则被认为是正确的。
样例
样例输入 1
3 10 9 8
样例输出 1
726.4578311468
Different Summands Counting
考虑将正整数 $n$ 分解为 $m$ 个正整数之和的所有有序划分：$n = a_1 + a_2 + \dots + a_m$。 令 $f(a_1, a_2, \dots, a_m)$ 为 $a_1, a_2, \dots, a_m$ 中不同整数的个数。求 $f(a_1, a_2, \dots, a_m)$ 在数字 $n$ 的所有有序划分上的总和，并将其对 $998\,244\,353$ 取模。
如果存在一个索引 $i \in \{1, 2, \dots, m\}$ 使得 $a_i \neq b_i$，则两个有序划分 $a_1 + a_2 + \dots + a_m = n$ 和 $b_1 + b_2 + \dots + b_m = n$ 被认为是不同的。
输入格式
唯一的一行输入包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^{18}, 1 \le m \le 500, m \le n$)。
输出格式
打印答案对 $998\,244\,353$ 取模的结果。
样例
样例输入 1
10 2
样例输出 1
17
样例输入 2
20 4
样例输出 2
3413
Emerging Tree
考虑一个包含 $n$ 个顶点的集合 $V = \{1, \dots, n\}$，以及一个有向边序列 $e_1, \dots, e_{n-1}$。令 $G_0, \dots, G_{n-1}$ 为一个图序列，其中 $G_0$ 为空，对于每个 $i = 1, \dots, n-1$，$G_i$ 是通过在 $G_{i-1}$ 中引入边 $e_i$ 得到的。保证 $G_{n-1}$ 是一棵有根树，所有边都背离根节点。
你的任务是找到集合 $\{1, \dots, n\}$ 的一个合适排列 $p_1, \dots, p_n$。令 $S_i(v) = \{p_u \mid u \text{ 在 } G_i \text{ 中可从 } v \text{ 到达}\}$。如果对于任何 $i \in \{0, \dots, n-1\}$ 和任何 $v \in V$，都有 $S_i(v)$ 由连续数字组成（即 $S_i(v) = \{l, l+1, \dots, r\}$，对于某些数字 $l$ 和 $r$），则称排列 $p_1, \dots, p_n$ 是合适的。
输入格式
第一行包含一个整数 $n$ ($2 \le n \le 10^6$)。 接下来的 $n-1$ 行描述边 $e_1, \dots, e_{n-1}$。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ —— 边 $e_i$ 的源顶点和目标顶点的索引 ($1 \le u_i, v_i \le n$)。
保证添加所有 $n-1$ 条边后会形成一棵有根树，且边背离根节点。
输出格式
如果没有合适的排列，仅在唯一的一行打印单词 “No”。 否则，第一行打印 “Yes”。第二行打印 $n$ 个整数 $p_1, \dots, p_n$，描述任意一个合适的排列。
样例
样例输入 1
4 3 1 1 4 1 2
样例输出 1
Yes 3 1 4 2
样例输入 2
7 1 2 1 3 1 4 2 5 3 6 4 7
样例输出 2
No
Fast Travel Coloring
给定一个具有 $7n$ 个顶点的完全无向图（这里 $n$ 是一个正整数）。你的任务是用 $n$ 种颜色给它的边着色，使得对于每一对顶点和每一种颜色，都存在一条由该颜色组成的、长度最多为两条边的路径连接这对顶点。更正式地说，对于每一对顶点 $u, v$ 和每一种颜色 $c$，以下两个选项中至少有一个成立： $u$ 和 $v$ 之间的边具有颜色 $c$； 存在一个顶点 $w$，使得边 $(u, w)$ 和 $(w, v)$ 都具有颜色 $c$。
输入格式
唯一的一行输入包含一个正整数 $n$ ($7 \le 7n \le 1000$)。
输出格式
让我们将颜色编号从 $1$ 到 $n$。令 $c_{i,j}$ 为 $0$（如果 $i=j$），否则为边 $(i, j)$ 在你的着色方案中的颜色（特别地，在这种情况下 $c_{i,j} = c_{j,i}$）。打印 $7n$ 行，每行包含 $7n$ 个数字。
保证存在解。
样例
样例输入 1
1
样例输出 1
0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0
样例输入 2
2
样例输出 2
0 1 2 2 1 1 1 1 1 1 1 1 1 1 1 0 1 2 2 2 2 2 2 2 2 2 2 2 2 1 0 1 2 2 2 2 2 2 2 2 2 2 2 2 1 0 1 1 1 1 1 1 1 1 1 1 1 2 2 1 0 2 2 2 2 2 2 2 2 2 1 2 2 1 2 0 1 1 1 1 1 1 1 1 1 2 2 1 2 1 0 1 1 1 1 1 1 1 1 2 2 1 2 1 1 0 1 1 1 1 1 1 1 2 2 1 2 1 1 1 0 1 1 1 1 1 1 2 2 1 2 1 1 1 1 0 1 1 1 1 1 2 2 1 2 1 1 1 1 1 0 1 1 1 1 2 2 1 2 1 1 1 1 1 1 0 1 1 1 2 2 1 2 1 1 1 1 1 1 1 0 1 1 2 2 1 2 1 1 1 1 1 1 1 1 0
Gnutella Chessmaster
Alexander 最近在 Chessforces 竞赛网站上获得了极高的评分。他的教练给他出了一个难题，以便 Alexander 能真正证明自己的实力。
考虑一个 $n \times n$ 的棋盘。主教（Bishop）是一种攻击所有与其共享对角线的棋盘位置的棋子。非攻击配置是指在棋盘上放置若干个主教，使得没有两个主教占据相同的位置，且没有主教攻击其他任何主教。
Alexander 必须计算对于每个 $k$ 从 $1$ 到 $2n-1$，在 $n \times n$ 棋盘上放置恰好 $k$ 个主教的非攻击配置数量。由于答案可能很大，每个数字都必须对一个完全随机的数字 $998\,244\,353$ 取模。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。
输出格式
打印 $2n-1$ 个整数。其中第 $k$ 个整数应该是 $n \times n$ 棋盘上恰好 $k$ 个主教的非攻击配置数量（对 $998\,244\,353$ 取模）。
样例
样例输入 1
2
样例输出 1
4 4 0
样例输入 2
3
样例输出 2
9 26 26 8 0
样例输入 3
10
样例输出 3
100 4380 110960 1809464 20014112 154215760 837543200 214861037 625796024 941559921 770927213 837612209 756883449 146369278 295974400 17275136 246784 1024 0
Halve & Merge
你有一个数组 $a = (a_1, \dots, a_n)$，最初包含 $1$ 到 $n$ 的一个排列。你需要处理两种类型的查询：
“1 p” ($1 \le p \le n$)：查找当前数组 $a$ 中的 $a_p$；
“2 p” ($1 \le p \le n-1$)：用函数 merge 应用于数组 $(a_1, \dots, a_p)$ 和 $(a_{p+1}, \dots, a_n)$ 的结果替换 $a$。
函数 merge 可以按以下方式编写：
func merge(var a as array, var b as array) var c as array while (a and b have elements) if (a[0] > b[0]) add b[0] to the end of c remove b[0] from b else add a[0] to the end of c remove a[0] from a while (a has elements) add a[0] to the end of c remove a[0] from a while (b has elements) add b[0] to the end of c remove b[0] from b return c
输入格式
第一行包含两个整数 $n$ 和 $m$ —— 数组的长度和查询的数量 ($2 \le n, m \le 2 \cdot 10^5$)。 第二行包含 $n$ 个不同的整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。 接下来的 $m$ 行中的每一行包含两个整数 $t_i$ 和 $p_i$ —— 第 $i$ 个查询的描述（$t_i \in \{1, 2\}$，$p$ 满足上述格式描述中给出的约束）。
输出格式
对于每个类型 1 的查询，在单独的一行上打印答案。
样例
样例输入 1
4 3 4 3 2 1 2 1 2 1 1 2
样例输出 1
1
样例输入 2
5 7 4 3 5 2 1 2 4 2 1 1 3 1 1 2 4 1 4 1 5
样例输出 2
3 1 3 5
Interpolate
Zhegalkin 多项式是一个布尔函数 $f(x_1, \dots, x_n)$，表示如下：
$$f(x_1, \dots, x_n) = \bigoplus_{S \subseteq \{1,2,\dots,n\}} a_S \cdot \bigwedge_{i \in S} x_i$$
其中 $\oplus$ 和 $\wedge$ 分别代表 XOR 和 AND 布尔运算，XOR 是对所有变量子集进行的，对于每个子集 $S \subseteq \{1, 2, \dots, n\}$，$a_S \in \{0, 1\}$。
在此任务中，给定 $m$ 组变量值 $(v_{i1}, \dots, v_{in})$ 和 $m$ 个布尔值 $y_i \in \{0, 1\}$。你需要构造一个 Zhegalkin 多项式，使其具有最多 9000 个非零项，满足对于每个 $i = 1, 2, \dots, m$，都有 $f(v_{i1}, \dots, v_{in}) = y_i$。
输入格式
第一行包含两个整数 $n$ 和 $m$ —— 变量的数量和给定变量值的数量 ($1 \le n, m \le 2000$)。 接下来的 $m$ 行中的每一行包含一个由 $n$ 个字符 0 或 1 组成的字符串，表示第 $i$ 组变量值，后跟整数 $y_i$。
保证所有变量值集合都是不同的，且至少有一组满足 $y_i = 1$。
输出格式
你的多项式必须包含最多 9000 个 $a_S = 1$ 的项。对于每一项，打印其对应的变量子集 $S$，表示为一个由 $n$ 个字符 0 或 1 组成的字符串，使得第 $i$ 个字符为 1（如果 $i \in S$），否则为 0。你可以以任何顺序输出这些项，但不能有重复的子集。
如果存在多个可能的答案，输出其中任何一个。如果解不存在，输出 -1。 保证如果解存在，则存在一个具有最多 9000 个 $a_S = 1$ 的项 $S$ 的解。
样例
样例输入 1
2 3 01 1 10 1 11 1
样例输出 1
00
样例输入 2
3 2 000 0 111 1
样例输出 2
100 010 001
说明
第一个样例的一个可能答案是 $f(x_1, x_2) = 1$。 在第二个样例中，$f(x_1, x_2, x_3) = x_1 \oplus x_2 \oplus x_3$ 是可能的答案之一。
Jaw-Dropping Set
集合 $\{1, 2, 3, \dots, n\}$ 的一个子集 $A$ 被称为有趣的，如果对于任何一对不同的整数 $x, y \in A$，既没有 $x$ 整除 $y$，也没有 $y$ 整除 $x$。
一个有趣的子集 $A$ 被称为惊人的，如果它在所有有趣的子集中具有最大基数。 最后，一个惊人的子集 $A$ 被称为令人瞠目的，如果它在所有惊人的子集中具有最小的元素和。
给定 $n$，求 $\{1, 2, 3, \dots, n\}$ 的任何一个令人瞠目的子集的元素和。
输入格式
第一行包含整数 $t$ ($1 \le t \le 10^5$) —— 测试用例的数量。 接下来的 $t$ 行中的每一行包含一个整数 $n_i$ ($1 \le n_i \le 10^9$)。
输出格式
打印 $t$ 行，包含每个测试用例的答案。
样例
样例输入 1
7 1 2 3 4 5 6 7
样例输出 1
1 1 5 5 10 10 17
Kingdom Connectivity
你是一名受国王指挥的工程师。国王让你建造一座城堡。该项目即将完成。已知城堡将包含 $n$ 座塔和 $m$ 面墙，每面墙连接某一对塔。塔可以看作平面上的点，墙可以看作连接塔的线段。该计划满足一些合理的假设： 没有墙连接塔与自身； 任意一对塔之间最多只能有一面墙； 不同的墙除了在塔处外，在任何地方都不相交； 没有两座塔位于相同的位置； * 没有墙可以穿过除其端点以外的任何塔。
你的任务是选择一些墙并在其中建造大门。之后，城堡的每一面墙的两侧都必须能够通过大门从外部进入。不同的景观要求你花费不同的金额来建造穿过不同墙的大门。完成你的任务所需的最少金额是多少？
输入格式
第一行包含两个数字 $n, m$ —— 塔的数量和墙的数量 ($1 \le n, m \le 10^5$)。 接下来的 $n$ 行中的每一行包含两个整数 $x_i, y_i$，表示第 $i$ 座塔将建在点 $(x_i, y_i)$ 处。坐标的绝对值不超过 $10^6$。 接下来的 $m$ 行中的每一行包含三个整数 $u_i, v_i, c_i$ ($1 \le u_i, v_i \le n, 1 \le c_i \le 10^6$)，表示塔 $u_i$ 和 $v_i$ 之间将有一面墙，且穿过这面墙建造大门的价格为 $c_i$。
输出格式
首先，打印一个数字：建造所有必要大门所需的最少金额。然后打印一个数字 $k$，即要建造的大门的数量。然后打印 $k$ 对数字，表示根据你的计划，由带有大门的墙连接的塔对。
样例
样例输入 1
3 3 0 0 0 1 1 0 1 2 1 1 3 2 2 3 3
样例输出 1
1 1 1 2
样例输入 2
4 5 1 0 2 1 1 2 0 1 1 2 1 2 3 2 3 4 3 4 1 4 1 3 5
样例输出 2
4 2 3 4 1 2