NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 21 题

某系统自称使用了一种防窃听的方式验证用户密码。密码是 $n$ 个数 $s_1, s_2,\dots , s_n$，均为 $0$ 或 $1$。该系统每次随机生成 $n$ 个数 $a_1, a_2, \dots , a_n$，均为 $0$ 或 $1$，请用户回答 $(s_1a_1 + s_2a_2 + \dots + s_na_n)$ 除以 $2$ 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。

然而，事与愿违。例如，当 $n = 4$ 时，有人窃听了以下 $5$ 次问答：  就破解出了密码s1 =___ ，s2 = ___，s3 =___ ，s4 =___。 答案格式为：纯数字用,连接

别被'防窃听'忽悠了，这题本质就是列方程组。把每次问答看作一个方程，在模2意义下（也就是异或运算）解这个线性方程组，就能反推出密码。

最大的坑就是忘记模2运算。学生看到题目里的加号，下意识想成普通整数加法，结果算出来的数全是0或1但逻辑不对，或者试图用高斯消元法在实数域做，完全跑偏。记住，这里所有的加减法都是异或，乘法是与。

这道题考查的是线性代数在模2域（GF(2)）上的应用，也就是异或方程组的求解。命题人喜欢这种披着'防窃听'外衣的数学题，实际就是想看看你是否能透过现象看本质，把自然语言翻译成数学模型，并且熟练掌握异或运算的性质。

首先，我们要把题目中的概念翻译成'人话'。密码是n个0或1的数，每次系统随机生成n个0或1的数a_i，然后让你回答(s_1a_1 + s_2a_2 + ... + s_na_n)除以2的余数。这里的除法取余，在0和1的世界里，其实就是异或运算。因为0+0=0, 0+1=1, 1+0=1, 1+1=0 (mod 2)。所以，每一次问答，实际上就是给出了一个关于未知数s_1到s_n的线性方程。

拿到题后，思考心法应该是：先列出所有方程，然后观察未知数的个数和方程的个数。这里有5次问答，也就是5个方程，未知数只有s_1, s_2, s_3, s_4四个。通常情况下，方程比未知数多，意味着方程组是超定的，但题目既然说能破解，说明这5个方程里至少有4个是线性无关的，足以唯一确定解。

具体怎么算呢？我们先把表格里的数据列出来。假设表格第一列是a_1, 第二列a_2, 第三列a_3, 第四列a_4，最后一列是回答的余数r。比如第一次问答：a=(1,1,1,1), r=0，方程就是s_1+s_2+s_3+s_4=0 (mod 2)。第二次：a=(1,1,1,0), r=1，方程是s_1+s_2+s_3=1 (mod 2)。以此类推，把5个方程都写出来。

接下来就是解方程组。在模2下，加减法都是异或，消元法和高斯消元法完全一样，只是运算规则变了。我们可以用代入消元或者高斯消元。观察这5个方程，会发现第1个方程和第4个方程（假设第4个是a=(1,0,0,0), r=0）相加，可以消掉s_1，得到s_2+s_3+s_4=0。再结合第2个方程s_1+s_2+s_3=1，把s_1用s_2+s_3+s_4表示，代回去，一步步就能把未知数一个个解出来。

避坑指南：最容易错的地方就是运算错误。比如把1+1算成2而不是0，或者在列方程时看错a_i的值。一定要时刻提醒自己，这是在GF(2)上运算，所有加法都是异或。另外，如果方程组看起来解不唯一，要检查是否有冗余方程，题目既然能破解，必然有唯一解。

关于考频与趋势，根据历年真题统计，'简单数论'这一考点在题库中总共出现过4次，覆盖了从CSP入门级到NOIP提高组初赛等多个级别。具体分布是：2013年考了1题，2019年考了1题，2021年考了1题，2026年考了1题。这说明这个考点每隔几年就会在初赛中出现一次，属于高频回归点。分赛事来看，CSP入门级、CSP提高级、GESP三级和NOIP提高组初赛各考了1题，分布非常均匀。

基于这个数据，我们可以预测：未来几年，NOIP提高组初赛和CSP提高级初赛极有可能继续考查这类'模2线性方程组'或'异或运算'的题目。命题人可能会换个场景，比如用二进制编码、校验码或者更复杂的逻辑电路来包装，但核心解题思路不变——列方程、模2运算、高斯消元。所以，平时一定要熟练掌握异或运算的性质和解线性方程组的技巧，这是应对这类题目的基本功。