易混 2017 年河南预赛 第 3 题 · P010311
用切换一个元素把子集分半，前提是这个切换真能在目标两类之间建立保持其余限制的双射。单一奇偶条件可以这样做；同时带有不同模数的筛选时，一般必须记录余数状态并单独扣交集。
前题按模数逐组统计，再用有限和数与补集关系扣掉另一整除条件，空集在扣除中统一处理；后题固定奇元素的切换确实翻转平方和奇偶，最后只需另核全集是否被真子集要求排除。
培玉 · 一试
2016 年中科大少年班初试 · 第 3 题
F3填空题组合计数综合
用表示集合的所有元素之和。若，且能被3整除，但不能被5整除，则满足条件的非空集合的个数为。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
先按模三统计全部子集，再扣掉同时被五整除的子集；小和数的计数可用补集与有限列表完成。
解答
先数子集和被三整除的情形。数三、六是否入选有四种选择；其他六数可配成三个各含模三余一、余二数的对。每对的子集按和的模三余数计数为 。依次合并一、二、三对，三个余数类数为
所以和被三整除的子集共有 个。 同时被五整除即和被十五整除。总和三十六，可能和为零、十五、三十。和零仅空集；和三十的子集用补集对应和六，恰有 四个。和十五的子集列表为
共十三个；按元素个数二至五并由最大元素向下列举可穷尽，六元素的最小和已为二十一。因此所求为 。
复核
空集的和为零，被五整除，已随扣除部分排掉，不必再减一次。三对余数状态合并均保留各选择的身份，四种零余数组合再独立相乘。全部256个子集的独立枚举也核得70。
方法总结
子集整除计数可先逐组转移余数状态，再用小规模和数及补集对称扣除交集，空集必须统一处理。
为什么评为 F3（会透露解法方向）
须独立选择模3分组、组合权重，再按15及30分类减去整除5；需封闭枚举。
联系 · 1 条
已记下，谢谢！