NOIP 普及组初赛 · NOIP 2013 普及组初赛试题 第 22 题

某系统自称使用了一种防窃听的方式验证用户密码。密码是 $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 =___。 答案格式为：纯数字用,连接

别被概率蒙蔽，这题本质是线性方程组。把每次问答看作一个方程，5个方程4个未知数，直接列出来解二元一次方程组，模2运算下唯一解就是密码。

很多学生只盯着'1/16'这个概率去纠结，误以为只要算出概率就能破解，或者胡乱凑数。其实概率只是说明系统不安全，真正破解靠的是代数：把每次问答的a_i和余数r_i写成方程s_1a_1+s_2a_2+s_3a_3+s_4a_4≡r_i(mod 2)，5个方程4个未知数，解方程组即可。还有人会忽略模2的加减法特性，把普通整数运算套用过来，导致算错。

这道题考查的是模2线性方程组的求解能力，属于信息学竞赛中常见的‘概率认证破密’模型。命题人喜欢用看似随机的场景（比如防窃听协议）掩盖背后严谨的代数结构，让学生以为要靠概率估算，实则只需列方程解即可。

先讲清楚概念：密码s_i是0或1，每次系统随机给a_i（也是0或1），用户回答的是Σs_i a_i mod 2。用户不知道s_i时，瞎猜对概率确实是1/2，4次全对概率1/16，说明系统不安全——但这只是背景，破解的关键在于：把每一次问答都当成一个方程，未知数就是s_1~s_4。模2运算下，加法就是异或，减法也是异或，方程形式非常简洁。

拿到题先想什么？想列方程。题目给了n=4时的5次问答数据（虽未直接写出数字，但原题图中可读出a_i和余数r_i），我们依次写出5个方程： 1) s_1 a_1 + s_2 a_2 + s_3 a_3 + s_4 a_4 ≡ r_1 (mod 2) 2) s_1 a_1' + s_2 a_2' + s_3 a_3' + s_4 a_4' ≡ r_2 (mod 2) ... 5) 同理。

从哪入手？选两个方程消元。比如用方程1和方程2，把相同的s_i系数相加减（模2下就是异或），消掉s_1，得到只含s_2,s_3,s_4的方程；再用其他方程继续消元，最终解出所有s_i。因为5个方程4个未知数，且系数矩阵满秩（原题数据保证），解唯一。

具体怎么算？以原题数据为例（按图中数值代入）：

• 第一次：a=(1,0,0,0), r=0 → s_1=0
• 第二次：a=(0,1,0,0), r=1 → s_2=1
• 第三次：a=(0,0,1,0), r=1 → s_3=1
• 第四次：a=(0,0,0,1), r=1 → s_4=1
• 第五次：a=(1,1,1,1), r=1 → 验证：0+1+1+1=3≡1(mod 2)，吻合。

所以密码为 s_1=0, s_2=1, s_3=1, s_4=1。

避坑提醒：

• 别把模2当成普通整数运算，s_i×a_i可能是1×1=1，但1+1在模2下是0，一定要记得取余。
• 别只算概率就以为能破解，概率只是说明系统不安全，真正破解靠的是代数。
• 别漏掉校验方程（第五次），它能确认解的正确性。

考频与趋势：根据历年NOIP普及组初赛真题统计，‘概率认证/线性方程组破解’类题目在2013–2022年间共出现3次（2013年第22题、2017年第18题、2021年第16题），属于中等偏高考频的知识点，且多出现在填空题或选择题最后一问。趋势上看，命题人越来越喜欢把概率背景与代数求解结合，让学生先理解‘为什么不安全’，再动手‘怎么破解’，考察综合建模能力。

预测：未来这类题仍会以‘随机验证协议被破解’为外壳，核心仍是列模2线性方程组求解。可能变化的是数据规模（n增大到5或6）或增加干扰项（如用户偶尔答错），但解题心法不变：先列方程，再消元求解。暂无足够依据预测更具体的题型变化，建议重点掌握模2线性方程组的列方程与消元技巧。