自动搬运

查看原文

来自洛谷，原作者为

	Doqe Doqe

搬运于2025-08-24 23:15:53，当前版本为作者最后更新于2025-05-11 19:16:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

我们采用分治法解决本题。

我们设计分治算法：计算下标在 $[0,3^n)$ 的乘法。需要递归调用下标在 $[0,3^{n-1})$ 的乘法。

我们考虑边界情况。如果 $n$ 足够小直接暴力。

如果 $n$ 不足够小，按照最高位划分出 $A_0,A_1,A_2$ 和 $B_0,B_1,B_2$。

然后我们宣称已经会了 $n-1$ 的算法，现在需要递归调用其。

因为是位运算，所以每一位的贡献独立，也就是 $[i\mathop{\mathrm{op}}j=k]=\prod_t[\text{op}_{v_3(i)_t,v_3(j)_t}=v_3(k)_t]$。

所以 $a_ib_j\to c_k$ 的贡献可以被拆成每一位。同时这里题目定义的“卷积”

$$W(A,B)=\sum_{i\mathop{\mathrm{op}}j=x}A_iB_j$$

$W$ 对于 $A$ 或者 $B$ 是线性的（双线性）。因此有乘法分配律 $W(kA+B,C)=k W(A,C)+W(B,C)$，$W(A,kB+C)=k W(A,B)+W(A,C)$。

因为调用乘法，我们需要构造若干个 $D_i=W(\sum x_{i,j}A_j, \sum y_{i,j}B_j)$。

最后我们要求 $C_k=\sum_{\text{op}_{i,j}=k}W(A_i,B_j)$，需要可以用 $D_i$ 加减表示。

在接下来的题目中，我们默认 $A_i,B_j$ 是一个变量，这样 $W(A_i,B_j)=A_iB_j$。但不影响推广。

关于时间复杂度分析：$T(n)=rT(n-1)+O(3^n)=O(r^n)$，当 $r\ge 3$ 的时候。

第零次

显然我们可以 $A_iB_j$ 全部都单独存放一遍，但是这样就需要递归 $9$ 次，和暴力基本无区别。

第一次，我们尝试部分分

我们在 Subtask 3 枚举几个例子，发现可以将输入的两个数据压缩，形成异或操作。

比如下面这个可以压缩 $1,2$ 为 $1$（只存储 $1,2$ 的和），$0$ 不变化。

$$\begin{bmatrix}0&1&1\\1&0&0\\1&0&0\end{bmatrix}$$

第二次，我们推广异或

依据 OI wiki 的说明，我们可以推广异或运算。

二进制异或可以视作长度为 $2$ 循环卷积。三进制同理。循环卷积使用 DFT 和 IDFT 实现。

第三次，我们发扬人类智慧

递归 $9$ 次啥都干不了。我们尝试搞一个构造至少解决 $\operatorname{mex}$。

这部分有原题 Tritwise Mex。

具体做法是，运算表形如：

$$\begin{bmatrix}1&2&1\\2&0&0\\1&0&0\end{bmatrix}$$

我们容易观察到 $(A_1+A_2)(B_1+B_2)$ 可以解决掉 $C_0$。

我么容易观察到 $A_0B_1$ 和 $A_1B_2$ 可以表示到 $C_1$。

然后我们使用容斥原理，用总的 $(A_0+A_1+A_2)(B_0+B_1+B_2)$ 减去 $C_0,C_1$ 得出 $C_2$。

第四次

来点容斥思想，选择运算表内出现最多的数字 $c$，用 $(A_0+A_1+A_2)(B_0+B_1+B_2)$ 减去 $A_iB_j\ (\text{op}_{i,j}\neq c)$ 来搓出 $C_c$，另外两个 $C_x$ 同卷积表示法。

这样需要使用乘法次数会少，$9-3+1=7$ 次。

我们进一步发扬人类智慧。

来点乱搞，因为数据随机，所以大概率有 $\text{op}_{i,j}=x\neq c$ 在同一行或者同一列的，这样随随便便就做到了 $6$。

具体分析一下只有拉丁方会出事，而拉丁方运算表几乎等价于三进制异或。合并一下就做完了，但是要注意卡常。

这里是 95 分的代码，拼上拉丁方就可以过了。洛谷提交记录。

（代码比较色，并且会有好几份代码，所以这篇题解不放完整代码只放提交记录）

第五次，我们更充分地发扬人类智慧

以上做法太差了。

还是需要构造 $D_i=(\sum x_iA_i)(\sum y_iB_i)$ 使得答案 $C_0,C_1,C_2$ 可以用 $D_i$ 表示。

我们观察上文的构造，再次发扬一下人类智慧，直接猜测 $x_i,y_i\in\{-1,1,0\}$ 有一组解，因为考虑 FMT 和 FWT，就已经覆盖了这个集合里的数。

至于最后的搓出，可以使用高斯消元解决（$C_i=\sum z_{i,j}D_j$，$C,D$ 都是多项式，把系数拿出来当向量用）。

总共有 $6r$ 个参数，$r$ 看上去可能大于等于 $4$（考虑 $\operatorname{mex}$ 操作及其原题）。所以枚举量至少 $3^{24}$ 往上，就爆了。

来点卡常，像 $(A_0+A_1)(B_0-B_1)$ 和 $(-A_0-A_01)(-B_0+B_1)$ 和 $(-A_0-A_1)(B_0-B_1)$ 本质是一样的。进行一个去重。

去重后只剩下 $67$ 个 $D_i$。我们大胆猜测 $r=4$。直接枚举，然后使用高斯消元判解和方案即可。

然后充满自信的交一发发现过了。作者在本地跑了运算表最后一位确定为 $0$ 的所有表，都存在解。

跑得飞快，qoj 上能在 500ms 内出结果，对于本题的时限绰绰有余。

QOJ 提交记录

接下来的尝试就没有什么复杂度上的优化了。更多是佐证复杂度难以减小的原因。

第六次

人类智慧不够用了。我们寻求他人的人类智慧。

假设 $A_i=[i=p]$，$B_j=[y=q]$，求 $C_k=\sum x_{t,p}y_{t,q}z_{t,r}$。这里我们定义 $D_i=\sum z_{t,i}C_i$。

我们可以发现这是个张量分解道理。我们还知道张量分解在 $\mathbb R,\mathbb Q$ 等分解是 NP hard（有限域下应该是 NPC）的。

虽然如此，我们还知道存在迭代近似的做法。虽然不一定能够求解，但是在这里是足够的。

我们查找一个梯度下降法，搞一下，发现基本都能到达 $r=4$。重复分解就有基本都通过了。

QOJ 提交记录

第七次？

如果希望进一步优化 $r$ 是极为困难了，因为这会需要 $r=3$。说明基本到头了。

这里有若干佐证：Tritwise Mex 做到了 $r=4$；三进制异或做到了 $r=3$，但是使用了单位根。

---

受到 NOIP T4 难度 的启发。写一些随即说话：

一份标准程序的 CP 分解部分使用了梯度下降法，但调高了学习率（变化幅度），并且若收敛速度过慢或不收敛（出现 inf 或 nan），重新运行直至找到一组解。

什么张量分解，到底是谁在会这种东西

但是 $6^n$ 能过啊

综上所述，本题是不可多得的题，无需添加任何形容词。唯一的败笔在于当时不知道为什么时间开太大了。唯二的败笔在于数据不够发力。唯三的败笔在于没有及时找出来第五次的做法。