一些难得的好题。
A Right String
一道简单字符串题。周期的性质值得留意。
题意
定义 $f(T)$ 为对 $T$ 进行任意多次“将第一位的字符移到最后”操作后能够得到的本质不同的字符串个数。
给定 $S$，问对其的字符进行 $k$ 次单点修改后得到的 $S’$ 中 $f(S’)$ 的最小值。
$0\le k\le|S|\le 2000$，字符集为小写英语字母。
思路
首先注意到 $f(T)$ 的答案为 $T$ 的最小正周期。
证明：首先考虑 $S$ 复制一边后的 $S_2$，可得到的 $S’$ 即为 $S_2$ 的长度为 $|S|$ 的子段。如果有两个子段 $T_1$ 和 $T_2$ 相等，设其在 $S_2$ 中分别从 $i$、$j$ 开始（不妨令 $i< j$），那么容易知道 $T_1$ 的前 $j-i$ 位也出现在 $T_2$ 的前 $j-i$ 位，即出现在 $T_1$ 的 $j-i+1$ 到 $2(j-i)$ 位，由此一直到末尾，因此 $T_1$ 的前 $j-i$ 位为 $T_1$ 的循环节。于是 $j-i$ 是 $T$ 的一个周期。反过来，$T$ 的每个周期 $t$ 都会使得 $i+kt$ 开始的 $S_2$ 的子段都相等。于是，$S_2$ 的本质不同的子段个数即为 $T$ 的最小正周期。
于是我们只要枚举 $|S|$ 的因子 $d$，让每个模 $d$ 的剩余系内的下标都变为其中一个众数。单次枚举是 $O(n)$ 的，但是清空数组需要 $O(d\cdot|\Sigma|)$ 的时间。
时间复杂度为 $O(n\cdot d(n)+\sigma(n)\cdot|\Sigma|)$。取其一不紧但实用的上界，$O(n^{4/3}+n|\Sigma|\log\log n)$。事实上，这个做法可以通过 $n=2\times 10^5$ 的测试点。
当然也可以通过枚举的逆操作清空数组，这样就是 $O(n\cdot d(n))$，即 $O(n^{4/3})$ 的。
代码
https://atcoder.jp/contests/arc140/submissions/31717459（$O(n^{4/3}+n|\Sigma|\log\log n)$）
B Shorten ARC
一道简单贪心题。注意贪心策略的选择。
题意
给定一个字符串 $|S|$，仅包含 A、R、C 三种字符。可对其执行若干次操作，操作如下：
- 如果当前的操作编号是奇数（首次为第 $1$ 次），那么可以选择一个连续的
ARC子段变为R； - 否则，可以选择一个连续的
ARC子段变为AC。
$|S|\le 2\times 10^5$。
思路 1
我们先定义“块”：块是形如 A...ARC...C 的极长子段。容易知道无论进行多少次操作，块都不会合并。我们用 A 和 C 的较小值表示块的“大小”，那么如下的贪心策略显然成立：
- 对于奇数次操作，选择一个最小的、大小大于等于 2 的块执行操作；
- 对于偶数次操作，选择一个最小的块操作。
于是我们只需要先排个序就搞定了。时间复杂度 $O(n\log n)$。
思路 2
注意到上述过程的答案为 $\min{2m,\sum x_i}$ ，其中 $m$ 为块的个数，$x_i$ 为第 $i$ 个块的大小。
时间复杂度 $O(n)$。
C ABS Permutation (LIS ver.)
一道贪心与构造的结合。构造值得学习。
题意
给定 $n$，请构造一个首项给定的排列 $P_n$，使其差分数组每项取绝对值后得到的数列严格 LIS 长度最大。
$n\le 2\times 10^5$。
思路
如果不限制首项的话，注意到以下的序列最优（以 $n=5$ 为例）：$3\ 4\ 5\ 2\ 1$。偶数的思路类似。
如果首项不是中位数，那么可以对剩下的数继续构造（以 $n=6$，$P_1=2$ 为例）：$2\ 4\ 3\ 5\ 6\ 1$ 奇数的思路类似。
时间复杂度 $O(n)$。
D One to One
一道有意思的计数题。这里对图的转化值得留心。
题意
给定一个有向图 $G$（可能有重边或自环），每个点的出度都不超过 $1$。现在要对 $G$ 执行如下的操作：
- 首先，给 $G$ 内每个无出度的点 $u$ 钦定一条出边（可以连成重边或自环）；
- 然后将 $G$ 的每条边变为无向边。
求最后可以得到的所有本质不同的无向图的联通分量个数之和，对 $998244353$ 取模。
$n\le 2000$。
思路 1
首先注意到初始图 $G$ 的每个连通块要么是树（恰有一个点出度为 $0$），要么是恰含有一个环的图（无法再向外连边）。设有 $m$ 个联通分量。
于是考虑缩点，一个树缩成一个红点，其他联通分量缩成一个黑点。给每个结点赋一个权值 $v_i$ 表示原图中连通块大小。我们只用考虑：新图中每个红点可以向外连一条边，构造出图之后变成无向图所得到的联通分量计数。
注意到新图满足每个联通分量都恰包含一个环或恰包含一个黑点。于是我们可以只统计环的贡献以及黑点的贡献。
考虑一个大小为 $k$ 的、包含缩点后 $x1,x_2,\dots,x_k$ 的环对答案的贡献，这显然是 $n^{m-k}\cdot(k-1)!\cdot \prod v{x_k}$。（第二部分是考虑环的形态，第三部分是考虑环在原图的种类数）
考虑一个黑点 $i$，它的贡献显然是 $n^t$，其中 $t$ 为所有红点的大小总和。
如何计算 $\sum\limitsk n^{m-k}(k-1)!\sum\limits{(xi)_k}\prod v{x_k}$？直接背包计算。时间复杂度 $O(n^2)$。
思路 2
最后其实不必用背包计算贡献，可以考虑计算 $\prod(1+v_ix)$，时间复杂度 $O(n\log^2n)$。
E Not Equal Rectangle
一道经典构造题。这个构造经常出现。
题意
给定 $n$，$m$，试构造一个元素都是 $1$ 到 $25$ 内的整数的矩阵，满足其不存在一个长、宽皆大于 $1$ 的子矩阵满足其四个顶点上的数完全相同。保证有解。
$n,m\le 500$。
思路
我们不妨考虑一个更强、更广泛的结论：给定素数 $p$，求一个 $p^2\times p^2$ 的矩阵满足元素都是 $\mathbb Z_p$ 内的整数，且不存在一个长、宽皆大于 $1$ 的子矩阵满足其四个顶点上的数完全相同。取 $p=23$ 的构造的前 $n$ 行 $m$ 列即可。
我们先构造小矩阵 $Bk(k\in\mathbb Z_p)=((i+j+k)\bmod p){p\times p}$，然后用 $p\times p$ 个小矩阵组成大矩阵：第 $i$ 行、第 $j$ 列的小矩阵为 $B_{ij\ \bmod\ p}$。
首先注意到每个小矩阵的每行、每列都没有相同的数，因此如果有一个子矩阵的四个顶点上的数完全相同，那它四个顶点应位于不同的小矩阵。考虑位于大矩阵同一列上的两个相同的数之间的距离。容易知道，如果设上面的数所在小矩阵编号为 $x$，下面的编号为 $y$，则它们之间的距离模 $p$ 同余于 $x-y$。因此，如果有四个顶点上的数都相同，不妨顺时针地设顶点所在小矩阵编号为 $a_1,a_2,a_3,a_4$（从左上角开始），那么有 $a_1-a_4=a_2-a_3$。显然，这与 $p$ 是素数的条件和大矩阵的构造相矛盾。因此大矩阵满足条件。
时间复杂度 $O(n^2)$。
F ABS Permutation (Count ver.)
略。