递推法

首先对集合进行分组 $A_n = \{5n-4, \dots, 5n\}$。对于任意 $A_n$，其子集中所有数字的和对 $5$ 取余的结果与 $A_1$ 相同。可以得到结果为 $0,1,2,3,4$ 的个数分别为 $8,6,6,6,6$。注意空集也满足条件（认为空集的所有数字和为 $0$）。

记 $A_1\cup A_2\cup\cdots \cup A_n$ 为 $B_n$，记 $B_n$ 满足条件的子集个数为 $a_n$，则 $B_{n+1}$ 满足条件的子集为：

对于数字和能被 $5$ 整除的 $B_n$ 子集，同样取数字和能被 $5$ 整除的 $A_{n+1}$ 子集配对，个数为 $8a_n$
对于数字和对 $5$ 取余为 $1$ 的 $B_n$ 子集，取数字和对 $5$ 取余为 $4$ 的 $A_{n+1}$ 子集配对。对于其它余数情况同理，可以得到这样的子集个数为 $6(2^{5n} - a_n)$

$$ a_{n+1} = 8a_n + 6(2^{5n} - a_n) $$$$ \frac 1 5 (2^{2000} + 4\times 2^{400}) $$

生成函数法

$$ G(x) = (1+x)(1+x^2)\cdots(1+x^{2000}) $$

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

$$ \begin{equation} \label{gen_fun} G(x) = \left[(1+x)(1+x^2)\cdots(1+x^{5})\right]^{400} \end{equation} $$

所以原问题等价与求该展开式中所有 $x^{5k}, k\in \mathbb{N}$ 项的系数和。可以利用 $n$ 次单位根性质。

单位根

$$ \omega^k = \exp\left(\frac{2\pi i k}{n}\right), \quad k=0,1,\dots,n-1 $$$$ \begin{gather} z^n - 1 = (z-1)(z-\omega)(z-\omega^2)\dots(z-\omega^{n-1}) \label{factor} \\ z^n - 1 = (z-1)(1+z+z^2+\cdots+z^{n-1}) \end{gather} $$$$ 1+z+z^2+\cdots+z^{n-1} = (z-\omega)(z-\omega^2)\dots(z-\omega^{n-1}) $$$$ \begin{equation} \label{circle} 1+\omega^k+\omega^{2 k}+\cdots+\omega^{(n-1) k}=\begin{cases} 0 & n \nmid k \\ n & n \mid k \end{cases} \end{equation} $$

求解

$$ \frac 1 5 [G(1) + G(\omega) + \cdots + G(\omega^4)] $$$$ \frac 1 5 (2^{2000} + 4\times 2^{400}) $$

参考

3Blue1Brown Video

递推法#

生成函数法#

单位根#

求解#

参考#

递推法

生成函数法

单位根

求解

参考