D5-2000 Problem

Question

Find the number of subsets of , the sum of whose elements is divisible by .

对于集合 ，它有多少个子集满足这个子集中所有数之和能被 整除?

递推法

首先对集合进行分组 。对于任意 ，其子集中所有数字的和对 取余的结果与 相同。可以得到结果为 的个数分别为 。注意空集也满足条件（认为空集的所有数字和为 ）。

记 为 ，记 满足条件的子集个数为 ，则 满足条件的子集为：

对于数字和能被 整除的 子集，同样取数字和能被 整除的 子集配对，个数为

对于数字和对 取余为 的 子集，取数字和对 取余为 的 子集配对。对于其它余数情况同理，可以得到这样的子集个数为

综上有

求通项公式 并代入 即可得到原问题答案：

生成函数法

生成函数经常用于组合计数中。考虑多项式：

将其展开的过程可以与构造子集的过程一一对应：每个元素都只有选与不选两种选择，展开过程选择 则意味着集合选取了元素。同时由于乘法的特性 ，展开式中各项的次数即等于对应子集的元素和，因此系数就对应着有多少这样的子集。

由于元素和是否能被 整除只和模 的余数有关，生成函数可以简化为

所以原问题等价与求该展开式中所有 项的系数和。可以利用 次单位根性质。

单位根

在复平面上的单位根为：

令 ，则 的根可以写作 。又由如下的关系式：

可以得到：

上式代入任意 可以得到：

求解

根据 ，可以令 为 的单位根，则 中所有 项的系数和可以由下式计算：

其中 。 可以通过 中代入 进行计算，得到 ，同理可得其它项。最后答案为：

视频演示

3Blue1Brown Video (Bilibili)

Harnessing the Complex

,.

let then, ,

Final blow

let then,