自动搬运

查看原文

来自洛谷，原作者为

	xuanxuan001 生活就像愤怒的小鸟，失败后总有几只猪在笑。

搬运于2025-08-24 23:13:51，当前版本为作者最后更新于2025-04-18 20:06:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

非常离谱的做法，复杂度似乎是大常数 $O(3^mm)$，理论上踩标了，现在是最优解第四，赛时因为预处理 $3^i$ 只预处理到了 $11$ 因此在 $m = 12$ 的时候在最开始记录总状态数的时候越界了，然后赛时以为是精度问题，遗憾离场，但过了应该也会以绝对的罚时优势稳居 rk6，所以也不影响排名。

考虑用三进制数存储决策，就按照题面中的字典序（名字长度？没看出 Rock Paper Scissors 遵循了什么字典序）分别对应 $0,1,2$，可以求出高适的决策概率分布 $A_{[0,3^m)}$，那么需要求的就是李白在所有决策上的胜率情况 $B_{[0,3^m)}$。考虑 $A \rightarrow B$ 是一个什么样的变换。

发现双方决策分别为 $i,j$ 时的胜负情况只和 $i$ 与 $j$ 在三进制的每一位上的差有关，对于每一位，差为 $0,1,2$ 分别代表平、胜、负，发现这个差也可以当做是个三进制数 $x$，那么可以对于每个 $x \in [0,3^m)$ 计算这时李白是否获胜，并也记录成一个数组 $C_{[0,3^m)}$，所有胜的位置为 $1$，否则为 $0$。

那么发现这其实是一个三进制上的不进位加法，设这样的不进位加法运算为 $\oplus$，那么 $A \rightarrow B$ 的变换实际上就是 $B_{i \oplus j} \leftarrow B_{i \oplus j} + A_iC_j$。我们知道在二进制中类似于这样的运算可以使用 FWT 或 FMT 快速求得，那么在三进制中是否存在类似算法呢？

其实我在几个月前就想过这个问题，但没有尝试去解决，这次模拟赛既然遇到了，就正好推一下。写这篇题解的时候搜了一下发现三进制 FWT 好像已经有了，但应该比较冷门，就无所谓了。

类似于 FWT，将每一位分开，并使用类似的变换，此时将问题变为了 $m = 1$ 的情况，不难发现只要 $m = 1$ 的变换正确将它类似于二进制下的 FWT 不断嵌套依然正确。

现在考虑此时的三元组 $(a_0,a_1,a_2)$，我们要找到一个合适的变换 $f(a) = a'$，其中 $a'$ 也是一个三元组，使得对于任意的对于任意的两个三元组 $a,b$，有

• $f(a + b)_i = f(a)_i + f(b)_i$。
• 设 $c_x = \sum\limits_{i=0}^2\sum\limits_{j=0}^2 a_ib_j[i + j \equiv x (\bmod 3)]$，那么有 $f(c)_i = f(a)_if(b)_i$
• $f$ 变换是一个三元组的映射，即存在 $f$ 的逆运算 $f'$，这条性质是由于在变换完成后需要用逆变换得到答案数组。

不难发现第一条性质等价于限制这个变换需要是一个线性变换，即需要找到一个矩阵 $F$，而变换 $f$ 即为 $a' = aF$，第三条限制等于 $F$ 存在逆矩阵，即 $F$ 满秩，下面考虑第二条限制。

不难发现由于是线性变换，所以实际上只需要验证 $a = (1,0,0),(0,1,0),(0,0,1)$ 的正确性即可。

发现 $F$ 的三列实际上是比较独立的，设为 $F_0,F_1,F_2$，那么代入上面三个 $a$ 可以发现它们应该满足 $F_i = x^i$，其中满足 $x^3 = 1$。

众所周知 $\sqrt[3] 1$ 有三个，刚好放在 $F$ 的三列即可，封装一个复数运算就行了，逆运算就手推一下这个方程，AC 记录。

本来以为这个做法会比官解更优拓展性，但官方做法也能求出 $B$ 数组，所以也不好说。