巨大多我们

· · 题解

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

我们设计分治算法：计算下标在 [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 因为调用乘法，我们需要构造若干个 $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](https://codeforces.com/problemset/gymProblem/102129/A)。 具体做法是，运算表形如： $$\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 分的代码，拼上拉丁方就可以过了。[洛谷提交记录](https://www.luogu.com.cn/record/216881414)。 （代码比较色，并且会有好几份代码，所以这篇题解不放完整代码只放提交记录） ### 第五次，我们更充分地发扬人类智慧 以上做法太差了。 还是需要构造 $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 提交记录](https://qoj.ac/submission/707232) 接下来的尝试就没有什么复杂度上的优化了。更多是佐证复杂度难以减小的原因。 ### 第六次 人类智慧不够用了。我们寻求他人的人类智慧。 假设 $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 提交记录](https://qoj.ac/submission/707225) ### 第七次？ 如果希望进一步优化 $r$ 是极为困难了，因为这会需要 $r=3$。说明基本到头了。 这里有若干佐证：Tritwise Mex 做到了 $r=4$；三进制异或做到了 $r=3$，但是使用了单位根。 --- 受到 [NOIP T4 难度](https://www.luogu.com/article/siiq1r8g) 的启发。写一些随即说话： > 一份标准程序的 CP 分解部分使用了梯度下降法，但调高了学习率（变化幅度），并且若收敛速度过慢或不收敛（出现 inf 或 nan），重新运行直至找到一组解。 > 什么张量分解，到底是谁在会这种东西 > 但是 $6^n$ 能过啊 综上所述，本题是不可多得的题，无需添加任何形容词。唯一的败笔在于当时不知道为什么时间开太大了。唯二的败笔在于数据不够发力。唯三的败笔在于没有及时找出来第五次的做法。