Qingyu的博客

博客

Public CTS Round #1 题解

2023-01-07 10:16:08 By Qingyu
  • 组题人:Qingyu
  • 搬题人:
    • 黑白点:flower, Qingyu
    • 博弈:Qingyu
    • 地雷:flower, p_b_p_b
    • 桥桥桥:Qingyu
    • 游戏:Qingyu
    • 知识:alpha1022, Qingyu
  • 题解:flower, Qingyu, LeafSeek, alpha1022

黑白点

Source:

特别感谢 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]。

算法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$。

桥桥桥

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

  • 取出 $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$ 是否合法。

cts-2a.png

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

游戏

Source:

算法一

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

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

  1. 如果不删空连续段,则这次操作可能会让这个 2 变为 12
  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 的举办者 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 中国国家集训队论文

评论

feecle6418
too hard
  • 2023-01-08 21:22:48
  • Reply
Crysfly
too hard
  • 2023-01-08 21:48:02
  • Reply
znstz
Too hard. When public 省选 round?
  • 2023-01-08 23:41:45
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。