题解：P12228 「WyOJ Round 1」持 · 山海为肩

xuanxuan001 · 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，有

• 设 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 即为 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 数组，所以也不好说。