题解作者：zzh1996
出题人、验题人、文案设计等：见 Hackergame 2022 幕后工作人员。
-
题目分类：math
-
题目分值：250
我看到矩阵就困
什么单位矩阵，什么爱因斯坦求和，即使只有这三行代码，我的脑子也像要爆炸了一样🤯
你可以 nc 202.38.93.111 10104 来与远程交互，或者点击下面的 "打开/下载题目" 按钮通过网页终端与远程交互。
如果你不知道
nc是什么，或者在使用上面的命令时遇到了困难，可以参考我们编写的 萌新入门手册：如何使用 nc/ncat？
这道题的核心逻辑是以下三行：
t1 = np.einsum('ax,bx,cx->abc', d[:16], d[16:32], d[32:]) % 2
t2 = np.identity(16, dtype=bool).reshape(16, 4, 4)
t3 = np.einsum('aij,bjk->abik', t2, t2)t2 中，np.identity(16, dtype=bool) 生成了一个 16x16 的单位矩阵，然后这个单位矩阵被 reshape 成 16x4x4，也就是说，把单位矩阵的每一行 16 个元素变成了 4x4 的矩阵。所以 t2 可以理解成是 16 个 4x4 矩阵，这 16 个矩阵每个矩阵都是只有一个元素为 1，其余元素为 0，16 个矩阵恰好对应 16 个为 1 的位置。
t3 把两个 t2 用 einsum 处理到了一起，根据 aij,bjk->abik 可以看出，是对 t2 的 16 种情况进行了一个双层的循环，循环内是进行了 ij,jk->ik 这个操作，也就是矩阵乘。
大概等价于这样的伪代码：
for i in range(16):
for j in range(16):
t3[i, j] = t2[i] @ t2[j]其中 @ 是矩阵乘法。
也就是说，t3 是一个乘法表，它记录了 16 种只有一个元素为 1 的 4x4 矩阵，乘以 16 种另一个只有一个元素为 1 的 4x4 矩阵，一共 256 种情况，矩阵乘的结果分别是什么。
题目要求 t3 和 t1 展开之后是相同的，我们来分析 t1 是什么。
如果把输入的矩阵切成的三块 d[:16]、d[16:32]、d[32:] 记作 a、b、c，我们可以写出来伪代码：
for i in range(16):
for j in range(16):
for k in range(16):
for x in range(48):
t1[i, j, k] += a[i, x] * b[j, x] * c[k, x]
t1[i, j, k] %= 2把 t1 和 t3 对照着看，根据 t3 的含义，t1 的三个维度分别表示只有一个元素为 1 的 4x4 矩阵的乘法表中，两个输入矩阵中 1 的位置和输出矩阵中 1 的位置。
结合上面的伪代码，就是说，对于 A * B = C 这个矩阵乘法，a、b、c 这三个矩阵分别对 A、B、C 中的元素进行了一个 GF(2) 上的线性组合，然后只有三个线性组合的结果都为 1 的时候才会被累加到一起。
这相当于，在计算 A * B = C 这个矩阵乘法时，我们不要直接算，而是先对 A、B、C 里面的元素进行一个线性变换，变换之后，每个矩阵对应 48 个数，C 中对应的数为 1 当且仅当 A 和 B 中对应的数都为 1。
这正好就对应了一个方案，使用 48 次乘法运算来完成两个 4x4 矩阵的乘法，加法次数不限。
没错，我出这道题就是因为看到了这个月 DeepMind 的新科研成果 AlphaTensor。
这题是我看到 AlphaTensor 的新闻之后立马在一个小时之内搞出来的。
如果你没有看到这个新闻，也没关系，只要理解了这题在考什么，去搜索引擎搜索使用尽量少的乘法次数完成 GF(2) 上 4x4 矩阵乘法，就可以找到答案。
这题正确答案中输入的矩阵就是把论文附录（PDF 第 12 页）的系数提取出来，或者直接使用上面链接中别人整理好的系数（我出题的时候还没有这个回答）。
为了降低难度，我并没有要求输入 AlphaTensor 的 47 次乘法的最新结果，我只要求了 48 次乘法，而 48 次乘法的构造其实很多年前就有了（见上面链接），所以即使没有 AlphaTensor 的结果也可能可以解出这道题（我没试，说不定不行）。同时 48 x 48 的矩阵看起来也比较方（逃）
求解这道题并不需要写代码，只需要理解和搜索，解出人数比较少我还是比较意外的。