闲题解答 | 营业日记

有朋友问我一道题：对于一个集合{1，2，3，4.....,N}, 求有多少子集使得子集内元素和是N的倍数。

很久没做题了，就做做试试。感觉是一道纯数学题，但我数学不好，可是数数说不定能数出来，感觉形式很生成函数。因此，先把问题具体化，即求

\[ A = \sum_k [x^{kN}]\prod_{i=1}^N (x^i+1) \]

然后看起来可能是单位根反演，那就试试：令 \[ w = \cos(2\pi/n)+i\sin(2\pi/n)\]

套用单位根反演去掉第一个符号可以得到：

\[ A = \frac{1}{N}\sum_{k=1}^N \prod_{i=1}^N (w^{ki}+1) \]

首先这是数学竞赛题，肯定不能直接开始死算。敏锐的

观察到：

\[ 1-z^n = \prod_k (-w^{k}+z) \]

带入 \(z=-1\) 得到

\[ 1-(-1)^n = \prod_k (-w^k-1) = (-1)^n\prod_k (w^k+1) \]

所以

\[ f(n) = \frac{1-(-1)^n}{(-1)^n} = \prod_k (w^k+1) \]

观察到如果 n 是奇数 \(f(n) = 2\), 要不然就是 0. 特殊情况 \(f(1) = 2^N\). (因为没有复数了)

可以直接带入吗？不能。因为这里似乎默认了 \(N\) 是质数。如果 \(N\) 不是，那么其实这种"循环节"不是常数。也就是乘以 \(i\) 的影响是有意义的。

乘以 \(i\) 其实就会导致带入式子中的 \(n\) 变小。这里有一个类似 burnside 的想法，考虑如果有 6 个单位根，然后选择一个复角 120 度的单位根，其实是 \(2f(3)\) 而不是 \(f(6)\).

具体好像和最大公约数有关，感觉和 burnside 很像，如果 \((N,k) \not = 1\), 那就直接取 \(\frac{N}{k} f(\frac{N}{(N,k)})\) (好像很有道理的样子？)

那就直接求和，

\[ A = \frac{1}{N}\sum_{k=1}^N (N,k) f(\frac{N}{(N,k)}) \]

那 \(f(X) = 2\) 当且仅当 \(X\) 里的 \(2\) 的因数被除干净了吧？那就是 \(2^{v_2(N)}|(N,k)\) 的时候吧？

那么 \(k\) 的选择只能是 \(t=2^{v_2(N)}\) 的倍数吧？也就是

\[ A = \frac{2t}{N}\sum_{k=1}^{N/t}(N/t,k) \]

最后补个项时因为可能 \(w = 1\) 也就是不参与复数的操作的时候。

那就莫比乌斯反演就好了吧？这不就是 polya 和 burnside 的关系吗？可是我没有背过 Polya 的结论，那就自己推一遍吧。

\[ A = \frac{2t}{N}\sum_d \sum_{k=1}^{N/td}d[(k,N/td)=1] \]

\[ A = \frac{2t}{N}\sum_{d|N} d\sum_{k=1}^{N/td}[(k,N/td)=1] \]

\[ A = \frac{2t}{N}\sum_{d|N} d\phi(N/td) \]

使用黎曼函数那套生成函数法玩一玩可以得到, (最后别忘了 \(2^N-1\))

\[ \boxed{A = \frac{2t}{N}( [z^{\frac{N}{2^{v_2(N)}}}] \frac{\zeta^2(z-1)}{\zeta(z)}+2^N-1)} \]