易混 2022 年北京预赛 · P006791
两题都对所有子集或零一选择求和,但符号权与绝对值会改变可用的对称性。
切换一个元素能使带号贡献成对抵消;绝对值和不能这样抵消,需要利用凸性与变量对称来比较。
设集合 。对 的子集 ,令它对应一个数
(空集 对应的数 )。对 的所有子集 , 求它们对应的数的总和
这是解答题,请在纸上写出完整过程。写完后对照解答给自己评分。
权值只取决于子集中元素和的奇偶性,而 含有奇数 。
把每个子集与“切换元素 是否被选取”所得的子集配对,两者的权值恰好相反。
对每个子集 ,令
其中 表示对称差,即切换元素 是否属于该子集。映射 满足 ,且没有不动点,因此它把 的全部子集两两配对。
由于 是奇数,从 变为 时,子集中所有元素之和的奇偶性恰好改变, 故两者对应的数满足
每一对的贡献之和都为 ,所以
空集与 正好配成一对,权值分别为 与 ,边界情形已经包含。 也可独立写成
乘积中 对应的因子为 ,再次得到总和为 。
对子集按所选元素之和赋予 权值时,优先寻找一个会改变奇偶性的元素,并用 “切换该元素”建立无不动点配对,使权值逐对抵消。等价的生成函数写法是把每个元素 “不选”与“选取”的贡献写成一个二项因子,再将所有因子相乘。
权值只有±1,切换固定奇数1即可成对抵消,是子集计数中的标准配对模型。
易混 2022 年北京预赛 · P006791
两题都对所有子集或零一选择求和,但符号权与绝对值会改变可用的对称性。
切换一个元素能使带号贡献成对抵消;绝对值和不能这样抵消,需要利用凸性与变量对称来比较。
已记下,谢谢!