P8854 超级马题解

前置知识

抽象向量空间

线性代数研究的“向量”究竟是什么？实际上向量的内涵要远大于一个高维空间的点，一个 的元素。

简单来说，一个向量就是“可以让我们进行各种基本代数运算的东西（“the laws of algebra work!”）”。

具体的，线性代数研究的“向量”是一个集合中的元素，其有良好定义的加法和数乘运算，具体的标准如下（线性空间的定义）：

• 是交换群。
• 是域。
• 存在一个 和 之间的运算，称作标量乘法。该运算对加法有左右分配律，结合律，单位元及逆元。

只要一个集合满足以上性质，我们就可以用线性代数的方法来研究（这也是标题中抽象的意思，“向量”并不指某种具体的东西，而是满足一些性质的一系列集合），并且我们的结论依旧适用。

最常见的有 维欧式空间 。以及 ， 为一个质数。其中每个向量的每一个维度都是 的整数，运算时对 取模。当 时，实际上就是异或空间。

生成空间

考虑有 个向量 。这些向量的生成空间就是这 个向量的线性组合的集合，记作 。

换句话说， 。

本题要处理 上的线性组合问题。需要注意此时 并不是域，因为整数上没有乘法逆元。因此我们要尽量少的涉及标量乘法，大致思路都是相似的。实际上题目要求 ，但是正整数连加法逆元都没有，直接考虑会比较困难，我们先考虑这个弱化版，稍后处理正权值的问题。

解法

解决这个问题大致有两种思路。一种是直接解线性方程组，一种是利用线性代数的解法。

线性方程组解法

我们把第 个向量记作 。原题要四个方向的单位向量，因而有解的必要条件是 ，否则由于横纵坐标永远是 的倍数，因此不可能到达 。

实际上就是判断以下线性方程组有没有解：

下面那个方程看上去比较和善。我们先考虑这个方程的解。

首先 显然是一组解。我们考虑在这个基础上加上一些数。先考虑组合出两个向量 ，使得 。不难发现其中一组解是让 和 分别是 ，即 ，我们将每两个向量的两两组合写出来，并且写出此时他们对 作出的贡献 ，如果这些贡献的 为 那么上面那组方程也有解了。

我们接下来证明如果存在一组 使得 ，则它必然可以拆成若干个 相加的形式，满足 。考虑使用归纳法证明。

• 对于 ，命题显然成立。

• 对于 ，考虑消掉第一项 。我们一共有 个包含 的式子，第 个记作 。我们只需要用 凑出 即可，根据 Bezout 定理，这个方程有解的充要条件是 ，这便是我们的证明目标。 根据我们上文对于 和 的定义， 显然互质（因为你都把 除掉了），同时 又是 的因数（因为你除掉了一个数），因此 也是 的因数。

  我们把和 无关的项移动到右侧，变成 。因为右侧每个 都是 的倍数，因此右侧加起来也是 的倍数。因此等式左侧也是 的倍数。但是 和 互质，因此 是 的倍数。证毕。

因此我们只需要求出两两组合的 以及对 的贡献，判断贡献的 是否为 即可。

线性代数解法

生成空间有如下性质：

证明也很简单。

考虑一个 中的元素 ，我们用一个新元素 替换 。

我们将 替换成 ，展开便仍然可以得到一组新的解：

因此我们证明了 的元素都在 中，利用相同的方法也可以反过来证明 的元素都在 中，因此这两个集合相等。

这也是高斯消元求线性基的基本原理。

需要注意在本题中标量乘法没有逆元，因此将一个向量乘上 的生成空间不一定和原来一样。

我们希望求出该空间的线性基。

我们考虑有两个向量 ，尝试消掉 中的一个。根据辗转相除法的结论 不难发现最后的结果一定是一个 另外一个是 。我们一边做欧几里得算法一边更新 即可。

具体地，假设我们有两个向量 。我们另 ，将 更新为 ，之后交换 直到有一个向量横坐标是 停止。

消完一个维度之后，对另一个维度继续消元。如果最后剩下来 说明可行。

正整数

简单来说，如果所有向量的角度不都落在一个半圆内，那么就可以凑出负系数，否则无解。无解是显然的。

考虑 个向量的情况，小于 个则必然无解，因为必然会落到一个半圆内。

多于 个的情况时，假设要凑出其中某个向量的负系数，我们作出该向量所在直线。由于向量不都在一个半圆内，因此直线两侧都有向量。从两侧任取一个向量即可转化成 向量的情况。

考虑这三个向量，标出了 。我们的目标是证明 一定可以表示成 的正线性组合。

我们可以考虑先用三个向量凑出 向量，再去掉一个 就能凑出 了。由于两个向量的正线性组合显然是凑不出 向量的，因此三个向量的系数一定都非 。

由于三个向量不再一个半圆内，因此 肯定在 之间。不妨把这三个向量分别写作 的形式。我们只需要找到一个解，满足 即可。不难发现我们可以先找到一组有理解，然后同时乘上分母的 即可。钦定 ，解出 即可。取最后为整数的 ， 就是 了。由于 在 之间，所以解出来的答案必然是正的。因此这个也证明完毕了。