• 组题人：Qingyu
• 搬题人：
  • 黑白点：flower, Qingyu
  • 博弈：Qingyu
  • 地雷：flower, p_b_p_b
  • 桥桥桥：Qingyu
  • 游戏：Qingyu
  • 知识：alpha1022, Qingyu
• 题解：flower, Qingyu, LeafSeek, alpha1022

黑白点

Source:

• Xmas Contest 2022. Problem H. Happy Game

特别感谢 Xmas Contest 的举办者 hos_lyric 与本题的作者 maroonrk 允许我们使用本题并提供了测试数据。

算法1

枚举选手选点，状压dp即可。

时间复杂度$O(2^n n^3)$，可以通过$subtask 1$，期望得分$6$。

算法2

考虑枚举先手的选点 $rt$，考虑第 $1$ 次只能染黑一个点的操作是第 $i$ 次。 那么有机会染的点是 $dis(rt, u) \le i$ 的点 $u$。如果令 $cnt_i$ 表示距离 $rt$ 小于等于 $i$ 的点（不包括 $rt$）的数量。如果有 $2i - cnt_i \ge 1$，那么一定满足这个选这个点的时候只能选他一个点。

如果最后只剩一个白点，也显然只能选一个点。

更具体的说，考虑最少的选 $1$ 的次数。那么答案至少为 $\displaystyle \left\lfloor\frac{n+\max_{i=0}^{maxd}2i-cnt_i}{2}\right\rfloor$，其中 $maxd$ 为距离的最大值。

接下来是一个构造，可以达到上界： 先拎出来最短路树，变成树上的情况。如果一个边两个端点都为黑点，我们认为他的边权是 $0$，否则是 $1$。 每次找到 距离 $rt$ 最远的点 $u$，把 $rt$ 到 $u$ 路径上的第一个白点染黑，除此之外如果还可以染，选择距离 $rt$ 最远且不在 $u$ 所在的白点导出子图的连通块里的点 $v$，将 $rt$ 到 $v$ 的路径第一个白点染黑。

可以证明每次上述式子会减少 $1$，方法是考虑 $cnt_i \ge 2$ 的时候，这个位置一定不会成为 $\max$，所以没有被的选的白连通块虽然 $dis$ 没有减少 $1$，但是除了$dis$为全局最大值（因为满足距离 $rt$ 最远的点的太多了），其他点与其 $dis$ 相同的点至少有 $2$ 个，因此不会不会成为 $\max$。而没有被选的全局最大值，如果前面至少有一个 $cnt_i\ge 3$，那么也不会成为最大值，否则对应了最后只剩一个点的情况。

时间复杂度 $O(nm)$，可以通过 $subtask 1, 2$，期望得分：$16$。

算法3

考虑加速刚刚的过程。把刚刚的构造方法对应成，把 $rt$ 到距离 $rt$ 最远的点 $x$ 路径上除了 $rt$ 的每个点，和不在路径上的点匹配，要求每个点能和他的匹配的必须不在他的子树里。

这样在路径上没有匹配的点就是 必须一次只能染黑一个的点。

因为 $x$ 只可能是树直径端点之一，令其为 $p, q$。因此我们考虑对于所有的 $i$ 计算以 $i$ 为跟是如果距离最远点是 $p/q$ 的答案，取 $\max$ 即可。

不妨只考虑 $p$，把树变成以 $p$ 为根的有根树。令 $f_u$ 表示最少使用 $1$ 的数量（不考虑$u$子树内点），$size_u$ 表示 $u$ 子树大小。

计算答案需要把子树内的点考虑进去，这些点可以根 $u$ 到 $p$ 上任意一点匹配，因此有 $ans = \max(f_u - size_u - 1, 0)$。

转移也是同理，每次把在 $fa_u$ 子树里，不在 $u$子树里的点加入，这些点可以与除了$fa_u$ 和 $u$ 的所有点匹配。

因此做两边 树形dp 即可，时间复杂度$O(n)$，可以通过 $subtask 3$，期望得分：$18$。

算法4

与算法3类似，考虑如何特殊处理环的问题。因为需要把最短路树拎出来，所以需要在环上断边。

先把环拎出来后，$p$ 对应在环上的点设为 $x$，那么可能被断掉的是 $x$ 在环上连的两个边。预处理出前缀和后缀的size之和，直接转移即可。

时间复杂度 $O(n)$，可以通过 $subtask 3, 4$，期望得分：$31$。

算法5

算法4带来的启发是，每次经过一个环长为 $len$ 的环，至少会带来 $\left\lceil\frac{len}{2}\right\rceil -1$ 的点可以用来和当前所有路径上的点匹配，而路径长度最多增加 $\left\lfloor\frac{len}{2}\right\rfloor$。这里我们认为的情况是环上初始有一个黑点，而取到上述式子的情况就是只有一个环不挂其他点的情况。注意到这两个式子之差最多为 1。

考虑由环组成的一个点双，也满足两者之差最多为1。假设要从点双的 $x$ 走到 $y$, 于是可以不需要考虑 $x,y$ 最短路上除了 $y$ 的节点有没有匹配（一定有匹配）。而判断 $y$ 能不能匹配上等价于，以及能匹配多少 $y$ 之后的点。设这个点双里 $x,y$ 最短路径长度为 $w$，点数为 $s$，那么能匹配 $s - 1 - 2w$ 个点，上式为 $-1$表示 无法匹配 $y$。 同样的这里认为 $x$ 已经是黑点了。

因此考虑建立圆方树，将 $p$ 设为根。与上文唯一的不同是，这个点双里的点，可以连向其他没用的点双（向兄弟子树里连）。 注意到转移需要查询的最短路长度 $x, y$ 满足 $x$ 为圆方树上，方点的父亲节点，$y$ 为方点的儿子节点。因此是单源最短路的形式，可以把每个点双挖出来之后 bfs。

我们令 $p', q'$ 为圆方树上，将边权视为 $1$ 的直径。算法5中提到过，每个点双最多会使染色一个点的次数加$1$。那么考虑 $u$ 到 $p$ 和 $p'$ 的最短路树上 $lca$ 以后的部分。因为 $p$ 到 $lca$ 距离（也就是最多有多少点没匹配）小于等于 $lca$ 到 $p'$ 的点数，因此可以把这些点匹配过去，是足够的，所以 $lca$ 之后不会产生任何贡献。

时间复杂度 $O(n)$，可以通过所有数据，期望得分 $100$。

博弈

Source: Кубок трёх четвертьфиналов 2019. Subregional 1. Moscow.

注意到，对于给定的 $(x, T)$，若先手希望 $x$ 最终尽可能大，而后手希望 $x$ 最终尽可能小，则一轮后 $T$ 变为 $T - 2\varepsilon$，$x$ 变为 $x + \varepsilon$。最终，$x$ 将会停在 $x + \frac{T}{2}$。

我们首先考虑二分答案，这样问题就变为了，$[0, n]$ 被划分成了若干段，有一些段 Min 获胜，有一些段 Max 获胜，问最后会停在哪一段。注意到对于 Max 而言，如果有一段的长度大于了 $A$，我们直接停在这一段中 Max 便直接取胜。否则，每一段在 $x-T$ 坐标系上构成了一块三角形区域，每个三角形是某一方的必胜区域。

现在，考虑最靠下的一个三角形区域，由于其不交 $y = A$，因此在这一部分区域内的胜负态可以合并为一块大的区域，如果某策略试图停留在这段区域，则另一方总可以将其移动到边界处，因此，此处形如 ABA 的胜负区域可被等效替代为一胜负态为 A 的三角形区域，故我们可以直接合并这整个区域为一个大的等腰三角形。我们可以使用 std::set 来维护所有的三角形并维护胜负态。

时间复杂度为 $O(n \log n \log \epsilon^{-1})$。

地雷

本题加强自 Potyczki Algorytmiczne 2022, Runda 4 的 Miny [A]。

• https://qoj.ac/problem/5241

算法1

预处理出每个点能到达的点，每次 bitset 优化 bfs 即可。

时间复杂度 $O(\frac{n^3}{w}+n^2)$，可以通过 $subtask 1$，期望得分$9$。

算法2

建出点分树，每个点能到达的点是距离重心 $rt$ 的一个前缀，前缀和优化即可获得 $n$ 个点 $O(n \log n)$ 的图。

缩强连通后，用 bitset 优化即可。

时间复杂度 $O(\frac{n^2\log n}{w} + n^2)$，可以通过 $subtask 1, 2$，期望得分 $14$。

算法3

我们希望点分治后，能求出来每个跨过 $rt$ 的点对 $(u,v)$ 求出 $u$ 能不能炸到 $v$。

但问题是，有可能存在 $u$ 先炸到当前点分树子树外，获得了了一个巨大的半径，再炸回来炸到了 $v$。于是有可能出现点分树上只考虑 $lca(u, v)$ 的子树（下文子树均指代点分树上子树），无法从 $u$ 炸到 $v$，但是考虑 $lca(u, v)$ 的某些祖先的子树能炸过去的情况。

因此我们接下来有两个思路：

1. 我们在 $rt$ 处理爆炸路径经过 $rt$ 的点对 $(u, v)$，这意味着 $(u, v)$ 可能在 $rt$ 为根的同一子树。
2. 我们仍然在 $rt$ 处计算所有跨过$rt$ 的 $(u, v)$ 能不能到达，但是为此我们需要预处理处一些连通块外的信息。

对于第一种思路，这种想法意味着一个点对会被统计多次，最直观的想法是用 bitset 去重即可。

令 $f(rt, x)$ 表示从 $x$ 开始炸只考虑 $rt$ 子树内只炸到 $rt$，能给 $rt$ 炸到多少半径（就是炸到 $rt$ 之后半径的余量，也就是 $\max r_u - dis(u, rt)$，$x$能炸到 $u$），如果无法找到 $rt$ 为 $-1$，也就是说要么 $f(rt,x)=-1$，要么 $f(rt, x) \ge r_{rt}$。

令 $g(rt, x)$ 表示从 $rt$ 开始炸，只能在 $rt$ 子树里，初始至少有多少的半径能炸到 $x$。

如果 $u$ 能走到 $v$，那么有 $f(rt, x) \ge g(rt, y)$。

从下往上考虑点分树。求 $g(rt, x)$ 的方法是逐渐增大 $rt$ 的初始半径，考虑哪些点直接被 $rt$ 一下炸死。对于每个被一下炸死的点$x$，需要考虑他怎么炸别人。也就是说找到 $v$ 使得 $dis(u, v) \le r_u$。可以通过点分树的方法做到，就是对于每个重心 $rt$，求出每个点到他的距离的 dis，rank 并且按照 dis排序，可以在 $O(n\log^2 n)$ 的时间复杂度内做到。

求 $f(rt, x)$ 即 $\max r_u - dis(u, rt)$。因为是取 max，所以不担心重复计算，也就是可以考虑出，对于 $u$ 的每个 点分树上祖先$rt'$，$u$ 经过 $rt'$ 能到达的点 $v$ ，这些 $v$ 能炸到 $rt$ 的余量。因此只需要 对 $f, g$ 双指针时，维护 $g$ 的当前前缀，对$rt$ 在点分树上每个祖先的贡献。

考虑到 bitset 的 or 操作，每次只有 $rt$ 点分树大小的点可能是1，因此 bitset 下标变成 点分树的dfn序 之后是一个区间里可能会有1。手写 bitset ，每个点可以做到时间复杂度 $O(\frac{n}{w}+\frac{n}{2w}+\frac{n}{4w} \cdots)$。

如果 $w=1$，可以直接使用的bitset的count，时间复杂度 $O(\frac{n^2}{w})$，否则为 $O(n^2)$。可以通过 $subtask 3, 4$，期望得分 $31$。

算法4

对于第二种思路，我们需要修改定义为：

令 $f(rt, x)$ 表示从 $x$ 开设炸，可以炸到任意点，能给 $rt$ 炸到多少半径。

令 $g(rt, x)$ 表示从 $rt$ 开始炸，可以炸到任意点，初始至少有多少的半径能炸到 $x$。

我们在点分树上从上向下做，假设对于 $rt$ 的所有祖先，$f(rt, x), g(rt, x)$ 都已经求出。

对于$f(rt, x)$ 我们需要枚举从点分树$rt$子树外炸回来时，是从哪个点分树的祖先的炸出去的，假设为 $rt'$。那么已知 $f(rt', x)$，如果存在一个点 $y$ 满足 $g(rt', y) \le f(rt', x)$ 那么从 $x$ 炸出去能回到 $y$，$y$ 对$f(rt, x)$的贡献为 $r_y - dis(y, rt)$。也就是说处理出 $g$ 的一个前缀对 $rt$ 贡献的 max 即可。因为刚刚的情况是经过了 $y$ 中转的，注意特判从外面一步炸回 $rt$ 的情况。

对于$g(rt, x)$ 几乎类似，同样枚举是从哪个点分树祖先炸出去的，假设为 $rt'$。那么如果有 $f(rt',y) \ge g(rt', x)$，那么 $y$ 对 $rt$ 的贡献为 $dis(rt, y)$，同样双指针一遍即可。一样要特判从 $rt$ 一步炸到外面的情况。

对于全局的重心的 $f, g$，可以通过用 算法3 的方法处理出来。

需要精细实现，否则会多 $\log$。因为枚举 $rt, rt'$ 之后 如果双指针之前不能多 sort。我的处理方法是将点分树按层处理，每个点的点分树子树，被当前层的儿子们划分了。所以需要每个点预先排序好，每层的时候处理一下划分。

时间复杂度 $O(n\log^2 n)$，可以通过所有数据，期望得分 $100$。

桥桥桥

• Source: Potyczki Algorytmiczne 2020, Runda 5, Trzy drogi [A]
• https://qoj.ac/problem/1395

注意以下判定图联通性的方法：

• 取出 $G$ 的任意一棵生成树 $T$
• 对于所有非树边 $e$，随机一个 $[0, 2^{64})$ 内的权值 $w(e)$
• 对于所有树边 $e$，定义其权值 $w(e)$ 为所有覆盖它的非树边的权值的异或和。

则我们可认为，删去 $E' \subseteq E$ 后图不联通等价于 $E'$ 存在子集 $F \subseteq E'$ 满足 $F$ 的边权异或和为 $0$。

首先，我们考虑所有删除一条边后图已经不联通的方案，这可以通过求出所有的桥边来得到。我们预先处理出这些边的方案，这一部分是容易的。接下来，我们假设不会选择这些边。

注意到，当我们假设一条边不能被选时，我们总是可以认为这条边一定在最终的图中，因此我们在这一步后，将图中所有桥边对应的两端点缩为同一个点，在这一步操作后，整张图将变为一张边双连通图。

其次，我们考虑，如果一个顶点 $x$ 的度数为 $2$（上述操作后，图中必定不会存在 $0$ 度点与 $1$ 度点），那么我们删去 $x$ 相连的两条边以及任意一条其他边，图一定变得不联通。我们同样算出这样的贡献并预先处理，随后我们便可以删去顶点 $x$。

在上述操作后，图变成了一张边双连通，且每个点度数 $\ge 3$ 的图。

此时，我们求出新图的一棵 DFS 树 $T'$，并考虑应用上述方法。注意到我们选择的三条边有以下四种情况：

• 选择了 $0$ 条树边，$3$ 条非树边。
• 选择了 $1$ 条树边，$2$ 条非树边。
• 选择了 $2$ 条树边，$1$ 条非树边。
• 选择了 $3$ 条树边，$0$ 条非树边。

首先，我们特判掉所有选择两条边后图一定不联通的方案，将这些方案特判掉。这是非常容易的，只需要找到所有 hash 值相等的边。

对于第一种情况，这样的方案一定不合法，因为 $T'$ 一定足以使得图联通。

对于第二种情况，我们枚举删去的树边，此时一定包含了至多两条跨过它的非树边，这样的情况是平凡的。

对于第三种情况，我们枚举删去的非树边，注意到特判掉所有两条边即合法的方案后，选择的两条树边必定呈祖先-后代关系，且选择的非树边为 $e_1, e_2$ 跨过边的差中唯一的边，这种情形仍然容易处理。例如，我们可以自底向上用并查集维护所有可行的链，并check每个对应的 $e_A$ 是否合法。

对于第四种情况，由于我们不会选择树边，因此我们可以缩掉所有的非树边，并在缩完非树边的图上接着做。由于图中每个点的度数至少为 $3$，因此 $|E| \geq \frac{3}{2} |V|$，故被缩掉的边数至少为 $|E| - |V| + 1 \ge \frac{1}{2}|V|$。在缩完边后，我们重新执行上述算法即可。由于缩边只会被缩 $O(\log m)$ 轮，因此总的时间复杂度可以保证。

游戏

Source:

• Canadian Comuputing Olympiad 2022. Day 2. Problem 3. Good Game
• https://qoj.ac/problem/4273

算法一

首先，题意等价于可以删除任意长度大于 $1$ 的同色连续段。因此考虑将原串划分为极长同色连续段后，长为 $1$ 的记作 1，长度大于 $1$ 的记作 2，则原串转化为一个 12 串。

考虑操作对 12 串可能的影响，一次操作只可能影响到某个 2 对应的连续段：

1. 如果不删空连续段，则这次操作可能会让这个 2 变为 1 或 2。
2. 否则连续段被删空，如果 2 处于开头或结尾，则 2 消失。
3. 否则 2 处于中间，2 会被删除且前后的元素会被合并，即 ?2? 会被转化为 2。

不难发现，2 优于 1，因而 1 操作不考虑。而 3 操作可以放到所有 2 操作结束后做。因此题意等价于给你一个 12 串，可以将 ?2? 转化为 2，问串能不能转化为全 2。进一步的，串能不能转化为 $1$ 或 $2$ 个 2，取决于初始串长。

由于任意时刻，串中的每个字符都对应了原串中某个长为奇数的区间。若 12 串的长为偶数，则考虑最后剩下两个 2 对应的区间，这个串可以被删空等价于可以将串划为两个长为奇数的部分，两个部分分别可以被删空。

因此我们只需考虑串长为 $2k+1$ 的情况，一个简单的情况是第 $k+1$ 位为 2，此时只需将两边不断删除即可。若第 $k+1$ 位不是 2，一个直观的想法是找到左右最近的两个 2，然后删除中间部分同时调整两侧长度，将问题转化为 $k+1$ 位为 2 的情况，例如 11211211111 首先调整为 1122111，然后变为 11211，即简单的情况。可以发现按照这个思路，原串可以被合并至 2 等价于两侧最近的 2 中间不包含超过 $k$ 个 1。而对于包含超过 $k$ 个 1 的情况，由于一次操作最多消除一个 1，且头尾一定会剩下 2，序列会转化为 21(...1)2，显然无解。

对于奇数情况的判断是简单的，对于偶数情况寻找划分点也可以做到线性，因此总复杂度为 $O(n)$。

算法二

by LeafSeek

称能被删空的串合法，否则不合法。关键结论：串 $S\texttt{AA}T$ 合法当且仅当 $ST$ 合法或 $S\texttt{A}T$ 合法。

首先证明如果 $S\texttt{A}T$ 合法，那么 $S\texttt{AA}T$ 一定合法。考虑消除中间 $\texttt{A}$ 的那一步，如果删了 $2$ 个就改成 $3$ 个，删了 $3$ 个就改成 $4$ 个（分两步各删 $2$ 个）。实际上容易说明连续任意 $\geq2$ 个相同字符均可被消除。

然后证明如果 $S\texttt{AA}T$ 合法，那么要么 $ST$ 合法，要么 $S\texttt{A}T$ 合法。首先注意到中间的两个 $\texttt{A}$ 一定是一起被消的。如果是分别被消的，和这两个 $\texttt{A}$ 相匹配的两边各还要有至少 $1$ 个 $\texttt{A}$，一共是 $\geq2$ 个，可以让这 $\geq2$ 个自己消除，将中间的两个 $\texttt{A}$ 调整成一步删 $2$ 个的操作。考虑它们一起被消的那一步，如果是删了 $2$ 个的情况可归入 $ST$，删了 $3$ 个的情况则可归入 $S\texttt{A}T$。

考虑这么一个过程：对于一个串 $S$，每次找到 $S$ 中最靠前的 $\texttt{AA}$ 或 $\texttt{BB}$，你需要决定将 $\texttt{AA}$ 变成空还是变成 $\texttt{A}$。那么 $S$ 能删空当且仅当存在一种决定方式，使得最后得到空串。

不妨设原串 $=S\texttt{A}$，考虑任一种合法的决定方式（不一定要最后删空），一定是先决定 $S$ 里面的东西，之后再决定最后一个 $\texttt{A}$。决定完 $S$ 里面的东西剩下的结果一定是 $\texttt{AB}$ 交替的，根据其首尾分别是 $\texttt{A}$ 还是 $\texttt{B}$ 可以分为 $4$ 类。

所以可以动态规划，我们用首尾和长度表示一个 $\texttt{AB}$ 交替的串。考虑转移，每次加入一个字符，维护当前串可以被删成的 $\texttt{AB}$ 交替串的集合。比如说 $\texttt{ABABA}$，加入 $\texttt{A}$ 之后可以变成 $\texttt{ABAB}$ 或者 $\texttt{ABABA}$ 中的一种；又比如 $\texttt{ABAB}$，加入 $\texttt{A}$ 之后只能变成 $\texttt{ABABA}$。必须特殊考虑空串，空串不属于 $4$ 类中的任何一类。直接维护这个集合即可做到 $\mathcal{O}(\dfrac{n^2}w)$。

接下来是未经证明的猜测：串 $S$ 能删成的结果，在确定了首尾之后，其可行长度的取值范围一定是一段区间。这里区间指的是 $[L,R]$ 内所有奇偶性与 $L$ 相同的整数。比赛的时候对拍观察动态规划中集合的模样可以做出上述猜测。于是只需维护能否删空、$4$ 个区间存不存在以及其左右端点，容易做到 $\mathcal{O}(n)$。

还原方案也可以做到 $\mathcal{O}(n)$：先回溯转移的过程，维护一个栈，确定每个字符是新弹入栈中还是与栈顶消除。对每个字符，开一个 $\texttt{vector}$ 保存它作为栈顶负责消除的字符的下标，包括 $\texttt{A(A)}$ 变 $\texttt{A}$ 和 $\texttt{BA(A)}$ 变 $\texttt{B}$ 两种情况。可以看出每个 $\texttt{vector}$ 的大小都 $\geq2$。最后直接 $\text{Dfs}$ 即可还原出方案。

知识

Source:

• Xmas Contest 2021. Problem H. Homework From Zhejiang

特别感谢 Xmas Contest 的举办者 hos_lyric 与本题的作者 maroonrk 允许我们使用本题并提供了测试数据。

先来考虑对于给定的一个点数为 $N$ 的有向图 $G$ 如何计算其各个点为根的外向生成树权值和。

定义 Laplacian 矩阵

$$L_{ij} = \begin{cases} \sum_{(k,i) \in E} w_{ki}, & i=j \\ -w_{ij}, & (i,j) \in E \\ 0, & \text{otherwise} \end{cases}$$

根据 Matrix-Tree 定理，以 $u$ 为根的外向生成树权值和即为 $L_{uu}$ 处的主余子式。 也就是说，我们需要计算 $L$ 的伴随矩阵 $L^*$ 的对角线。

注意到 Laplacian 矩阵并不满秩，因此其伴随矩阵的秩不超过 $1$。因此，存在列向量 $x,y$ 使得其伴随矩阵 $L^* = xy^{\mathsf T}$。

而注意到 $L$ 所有行向量之和为全 $0$ 向量，从而可以证明其同一列的所有代数余子式相等，因此 $L^*$ 的各列向量相等，$y$ 可以取全 $1$ 向量。

那么，我们只需要算出 $x$ 即可获得对角线上的值。

而根据 $AA^* = |A| I$，可知 $L x y^{\mathsf T} = 0$，也就是 $L x=0$。据此，我们可以解出一个非平凡的 $x$，但其与真正的 $x$ 相差常数倍。

幸运的是，这是容易处理的。我们只需要取一个非 $0$ 的位置计算出对应的余子式即可。

而题意中给出的就是两张图的 Cartesian 积。不妨记作 $G = G_1 \mathop\square G_2$。
为了刻画其 Laplacian 矩阵，我们引入 Kronecker 积：

$$A \otimes B = \begin{bmatrix} a_{11} B & a_{12} B & \cdots & a_{1m} B \\ a_{21} B & a_{22} B & \cdots & a_{2m} B \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} B & a_{n2} B & \cdots & a_{nm} B \end{bmatrix}$$

其中 $A$ 是 $n\times m$ 矩阵。

令 $L^{(1)},L^{(2)}$ 分别为 $G_1, G_2$ 的 Laplacian 矩阵，易得 $G_1 \mathop\square G_2$ 的 Laplacian 矩阵为 $L = L^{(1)} \otimes I_N + I_M \otimes L^{(2)}$。

接下来，我们注意到，若我们对 $L^{(1)}, L^{(2)}$ 求出了各自的 $x^{(1)}, x^{(2)}$，则有 $L (x^{(1)} \otimes x^{(2)})=0$。因此我们也只需要定出相差的系数即可。

我们考虑通过其和，也就是伴随矩阵的迹来定出这个系数。

设 $L^{(1)}, L^{(2)}$ 有特征值 $\lambda_1, \lambda_2, \dots, \lambda_M$ 和 $\mu_1, \mu_2, \dots, \mu_N$，则 $x^{(1)}, x^{(2)}$ 的和即为 $L^{(1)}, L^{(2)}$ 的特征多项式的 $1$ 次项系数乘 $(-1)^{M-1}$ 和 $(-1)^{N-1}$。

注意到 $L^{(1)}, L^{(2)}$ 必有 $0$ 这个特征值，不妨设 $\lambda_1 = \mu_1 = 0$，则这个值就是 $\lambda_2 \lambda_3 \cdots \lambda_M$ 和 $\mu_2 \mu_3 \cdots \mu_N$。

因此 $x^{(1)} \otimes x^{(2)}$ 的和即为 $\lambda_2 \lambda_3 \cdots \lambda_M \mu_2 \mu_3 \cdots \mu_N$。

而可以证明，$L$ 的特征值为 $\lambda_i + \mu_j$ $(i=1,2,\dots,M, j=1,2,\dots,N)$（证明见 [1]）。因此，相差的系数即为 $$\prod_{i=2}^M \prod_{j=2}^N (\lambda_i + \mu_j)$$

而我们知道特征值是特征多项式的根，因此我们借助 Resultant，可以得到这个乘积的值为 $\operatorname{res}\left(\frac{|tI-L^{(1)}|}t, \frac{|tI+L^{(2)}|}t\right)$。

而对于 Resultant 的计算，由于这部分并非瓶颈，可以直接 $O((N+M)^3)$ 计算行列式。

事实上，根据 wiki 上的结论，我们可以用多项式 Euclid 实现其求算。暴力实现就是 $O(NM)$ 的。 然而 wiki 上的结论疑似有误，其算法具体实现可以参考 std。

[1] 潘佳奇，浅谈线性代数与图论的关系，IOI 2021 中国国家集训队论文