易混 2016 年中科大少年班初试 第 3 题 · P009994
用切换一个元素把子集分半，前提是这个切换真能在目标两类之间建立保持其余限制的双射。单一奇偶条件可以这样做；同时带有不同模数的筛选时，一般必须记录余数状态并单独扣交集。
前题按模数逐组统计，再用有限和数与补集关系扣掉另一整除条件，空集在扣除中统一处理；后题固定奇元素的切换确实翻转平方和奇偶，最后只需另核全集是否被真子集要求排除。
培玉 · 一试
2017 年河南预赛 · 第 3 题
F2填空题经典的计数模型
称所有元素的平方和为奇数的非空有限数集为平凡集。若集合
则 的所有真子集中平凡集的个数为（允许用数的幂次表示）
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
平方和奇偶只取决于选入奇数的个数，切换一个固定奇数可将子集成对分半。
解答
整数平方与其本身同奇偶，因此子集平方和为奇数当且仅当选入奇数的数量为奇数。对所有子集执行“切换元素一是否在内”的可逆配对，每对恰有一个奇平方和子集，所以共有 个。空集不是奇平方和子集，已自动排除；全集 含一千零九个奇数，其平方和为奇数，但它不是真子集，须再扣去一个。因此
复核
切换一只改变一个奇数的归属，确实翻转奇偶，且无固定点。全集含1009个奇数为奇数，这决定最后是否减一，不能仅凭“真子集”一律减两个。
方法总结
带奇偶权的子集计数可用固定奇元素的切换双射分半，再单查空集与全集。
为什么评为 F2（会透露解法方向）
先将平方和奇偶化为奇元素个数，再用切换配对分半，最后分别核非空及真子集边界。
用到的方法（会透露解法方向）
核心工具：对称配对：和差分离
联系 · 1 条
已记下，谢谢！