函数最值

分类讨论。

• 如果 ，则 为常值函数，最小、最大值均为 ；
• 如果 ，则 为一次函数，无最值；
• 如果 ， 为二次函数。
  • 当 时， 开口向上，无最大值，有最小值 ；
  • 当 时， 开口向下，无最小值，有最大值 。

后缀编辑距离

容易发现， 和 的编辑距离即为 。

我们先考虑 的情况。如果字符全相等（比如全 串），那么我们肯定选择 ；否则，一定存在 使得 ，于是 一定是最大的，因为它俩 ，并且对于任何一对 ，若满足 ，则它们一定满足 ，但它们的 相应为 ，所以有

这样，我们就能以线性的复杂度求解 。

再考虑 的情形：

方法一

我们对 反串建 SAM，那么后缀 的答案就是它们所在后缀树节点的 LCA。因此我们对于每个 LCA 的地方考虑贡献，LCA 处 已经固定了 的长度，所以我们希望求出每个子树里面的后缀长度最小值。 对答案的贡献是选两个不同的儿子子树 的后缀长度最小值和再减去 。

这样，我们就能以线性的复杂度求解 。

当然，也可以用 SA，将 height 数组建出笛卡尔树做类似的事情，但是可能需要 SA-IS 做到时间复杂度线性，所以出题人将字符集开成了 ，放了直接写 SAM 的空间。当然你可以用哈希去存 SAM 的儿子数组，这样空间就不受字符集影响。

方法二

考虑 ，如果 ，则它的值为 ，此时必然是最小值，否则它的值为 ，也就是说 ，我们只需要判断是否存在 的一对 即可。容易发现，想要满足 ，必须满足 并且 与 完全一致。由于它具有单调性，即若 可行，其中 且 ，则 必然可行，所以我们只需要 check 一下 即可。

时间复杂度 。

树上博弈

暴力

首先，这是个公平博弈题，我们只需要求出每个点的 SG 函数即可。

容易发现，点 走到点 ，一定满足 ，所以 始终变大，于是我们可以根据这个，将 从大到小递推求出 SG 值。

查询的时候，相当于询问是否存在一个子集，满足 SG 值异或等于 。如果存在，那么小 必胜，否则小 必胜。我们只需将这 个 SG 值插入线性基，看看是否线性无关即可。

时间复杂度 。

优化

我们观察一个性质：如果 能挪到 ， 也能挪到 （），那么 一定可以挪到 。根据这个性质，我们容易联想到 能到达的所有点一定是 的超集（也是 的超集）。

这给我们了一个启发：是不是它们的可达点集形成了一个树形关系呢？

我们考虑 最大的点 ，任何一个点 一定能走到 ，并且走到 以后无法继续走。因此删掉点 以后，剩下的若干个连通块互相独立，形成了子问题。我们根据这一做法连成了一棵树 ，点 可达的点即为 在树 中的祖先，因此 的 SG 值即为它的深度（根的深度为 ）。

但是，我们发现正面构建这棵树的较为麻烦（指复杂度很难优化），我们考虑将 从小到大依次加入点，用并查集维护每个点所在连通块的根是谁，这样就可以用树上并查集在 时间内构建出树 。

查询的时候同理。

总时间复杂度 ，常数较小。

矩阵计数

考虑二项式反演，用 表示钦定了 个 的位置是上升的方案数，则 。

枚举 个上升段，则 。

记 ， ，则 。

因此

注意到分母只有 项，可单独提出来求逆。

对于单个 ，暴力求后面这项的复杂度为 ，故总复杂度 。如果采用 FFT 优化卷积，可以做到 ，但对于本题而言是不必要的。