NOIP 普及组初赛 · NOIP 2011 普及组初赛试题 第 21 题

每份考卷都有一个 $8$ 位二进制序列号。当且仅当一个序列号含有偶数个 $1$ 时，它才是有效的。例如，$00000000$、$01010011$ 都是有效的序列号，而 $11111110$ 不是。那么，有效的序列号共有_____个。

拿到这种‘偶数个1’的计数题，别急着硬算组合数，先想对称性：把每一位的0/1互换，奇偶性必然反转，所以奇偶各占一半，直接2^8÷2=128。

最容易掉进两个坑：一是死磕组合数公式，把C(8,0)到C(8,8)一个个加起来，虽然结果没错，但考场时间紧，容易算错中间项导致整题丢分；二是概念混淆，把‘偶数个1’当成‘至少有2个1’或者‘不含1’，忽略了0个1也是偶数，漏掉C(8,0)那一项就会少算1个，变成127。

这道题考什么

这道题考查的是二进制序列的奇偶对称性，以及组合数求和的化简技巧。在信息学竞赛初赛里，这类题目通常不会让你真的去算C(8,0)+C(8,2)+...，而是考察你能不能一眼看出‘奇数个1’和‘偶数个1’的序列数量是相等的。

概念：什么是‘偶数个1’？

8位二进制序列，每一位要么是0要么是1。‘偶数个1’指的是序列中1的总个数是0、2、4、6或8。注意，0个1也是偶数，所以全0序列（00000000）是有效的，这一点很多初学者会忽略，导致漏算。