比赛链接

Upsolved by qxforever.

对两个字符串 $s,t$ 定义 $f(s,t)=\max(s[1..i]=t[\vert t\vert-i+1..\vert t\vert])$，即前缀等于后缀的最大长度。

给 $n$ 个字符串，求 $\sum_i\sum_j f(s_i,s_j)^2$ ，结果对 $998244353$ 取模。$\sum n\le10 ^5$，$\sum \vert s\vert\le 10^6$

预处理出来所有前缀的 hash 值，存入 map 。计算答案时，对每个后缀的 hash ，在 map 中查询对应前缀的个数。但是这样会有重复，对每个串反转后求 next 数组即可。

注意自然溢出 hash 的底数不要用偶数。

串的所有 border 是其 AC 自动机上的所有 fail 链，因此对每个串的前缀，只需要统计从根节点到该节点上，所有串最近的 fail 链做的贡献之和，这个可以在遍历过程中用一个栈维护。或者可以先处理每条 fail 链上长度平方的增量，这样进出一个节点时就只用加减该节点上贡献的增量即可。

Upsolved by qxforever.

给二维平面上 $n$ 个点，对于任意过点 $(0,0)$ 的圆，求圆边界上的点数量的最大值。$n\le 2000$

对任意两个点以及 $(0,0)$ ，求出这三点确定的圆的圆心，并记录每个圆心的出现次数 $\text{cnt}$。设边界上的点数量为 $k$ ，则有 $\binom{k}{2}=\max\text{cnt}$ 。圆心坐标必定为有理数，用 map 维护一个分数类的 pair 即可。注意常数优化。

Solved by qxforever.

给一颗 $n$ 个点的树，求链数最少的链覆盖，并输出方案。每条链至少被覆盖 $1$ 次。$n\le 2\times 10^5$

设叶子个数为 $x$ ，所有叶子都至少被选中 $1$ 次，那么答案的下界为 $\lceil x/2 \rceil$ 。

这里的做法是将一个非叶节点设为根节点，每次从根节点不同的两个子树中各选一个叶子，直到所有叶子都在同一棵子树中。

与树的重心类似，这里提出了一个树的叶子的重心的概念，即子树的叶子数量的最大值最小的节点。对于这样的节点，子树叶子数量的最大值 $\le \lceil x/2 \rceil$。选这样的节点为根，可以保证当所有叶子都在同一颗子树中时，子树中剩余的叶子最多为 $1$ 。于是我们就构造出了一种答案为 $\lceil x/2 \rceil$ 的方案。

签到题

Upsolved by nikkukun.

给定 $n \leq 2 \times 10^5$ 个 $[0, 2^{18})$ 内的数，求用恰好 $1, 2, \ldots, n$ 个数能异或出来的最大值。

根据线性基的特性，只要用基底的个数个线性无关的基就能获得最大值，因此 $i$ 并非很小的时候只要在 $i-2$ 答案的基础上随便加上两个相同的数即可。

令 $f(i)$ 表示 $a_i$ 是否出现，则做 $i$ 次异或 FWT 就能得到 $i$ 个数能否表示出来的答案，这里选择处理前 20 次即可。

Solved by nikkukun.

给定 $n \times m$ 的矩阵，第 $i$ 行 $j$ 列的数是 $\mathrm{lcm}(i, j)$，求所有 $k \times k$ 子矩阵最大值的和。

降维，做两次单调队列。

Solved by nikkukun.

给 $n \leq 1.5 \times 10^5$ 个数 $a_1, a_2, \ldots, a_n$ 和 $m \leq \min(n, 40000)$ 个数 $b_1, b_2, \ldots, b_m$，求 $a$ 中有多少长度为 $m$ 的子区间满足对应位置全都不小于 $b$ 的对应位置。

类似 bitset 加速字符串匹配的类型，由大到小枚举 $b$ 中的元素，用一个 bitset 表示 $a$ 中不小于该元素的位置，这样 bitset 的变化量是 $O(n)$ 的，总时间复杂度 $O\left(\dfrac {nm}w \right)$。

Upsolved by nikkukun.

区间 $[l, r]$ 可以任意变到 $[l+1, r]$ 或 $[l, r-1]$，同时提供了 $m$ 种已有的方案，每种方案仅属于以下一种：

1. 用一些花费禁掉 $[l_i, r_i]$ 与 $[l_i+1, r_i]$ 之间的双向转化
2. 用一些花费禁掉 $[l_i, r_i]$ 与 $[l_i, r_i-1]$ 之间的双向转化

初始有区间 $[1, n]$（$n \leq 500$），你可以选择一些方案，使得任意转换过程中不出现 $l = r$ 的区间，并求最小花费。

用区间代表的二元组建成一个 $n \times n$ 的网格图，相当于禁掉一些边，使得 $(1, n)$ 不能走到 $y = x$ 的位置上。这个东西是平面图最小割，参考 狼抓兔子 跑最短路即可。

Solved by nikkukun & qxforever.

给一个长度 $n \leq 10^5$ 的置换 $A$ 和一个大质数 $k \in [10^8, 10^9]$，求是否存在另一个置换 $P$ 使得 $P^k = A$。

考虑 $P$ 轮换乘积形式中的每个轮换，其 $k$ 次方相当于轮换移动了 $k$ 次。由于 $k$ 是个大质数，其必然与轮换长度互质，故轮换操作不会改变轮换长度（不互质的情况可能会让一个轮换变成很多小轮换），直接将 $A$ 中的每个轮换倒着移动 $k$ 次即可还原。

总时间复杂度 $O(n)$。

Solved by qxforever & Potasium.

给三个同心圆的半径，每个圆上随机取一点，求所成三角形面积的期望。

根据两个角度暴力计算推出二重积分式：$\frac{1}{(8{\pi}^2)}\int_{0}^{2\pi}\int_{0}^{2\pi} r_1(r_2sin(x)-r_3sin(y))+r_2r_3(cos(x)sin(y)-cos(y)sin(x)) \text{d}x\text{d}y$

套两个辛普森积分，要调调参数。