记 $\mathrm{sum}(A)$ 为集合A中所有元素的和。
例如，$\mathrm{sum}({1,6,7})=1+6+7=14$；特别地，$\mathrm{sum}(\emptyset)=0$.
有集合 $S=\{x\in\mathbb{N}_+ \mid x\le n\}$， 若 $A\subseteq S$ 且 $\mathrm{sum}(A)$ 是k的倍数，则称 A 是 S 的 k-好子集。
求：
（1）$n=1145141919810, k=2$ 时，S 的 k-好子集的个数；
（2）$n=10, k=3$时，S 的 k-好子集的个数。

答案

（1）
构造一种对应关系：如果两个集合区别仅有包不包含 1，则将这两个集合对应。

1. 每一个集合只有唯一的另外一个集合与之互相对应；
2. 对应的集合的和一定相差 1，即一奇一偶。

因此，和为偶数的集合一定占全部集合的一半，即 $\frac{1}{2}\times 2^{1145141919810} = 2^{1145141919809}$

（2）
设 $f_{i,j}$ 为 $\{1,2,\cdots,i\}$ 的所有子集中，和除以 $k$ 的余数为 $j$ 的子集的数量。
（简便起见，以下使用 $\%$ 表示求余）
考虑从 $i-1$ 递推到 $i$ 的情形：

• 若不选 $i$，则和不变；
• 若强制选 $i$，则和会增加 $i$，即余数从 $(j-i)\%k$ 变为 $j$.

因此，

$$f_{i, j} = f_{i-1, j} + f_{i-1, (j-i)\%k}$$

由 $f_{0,0}=1$（$\mathrm{sum}(\emptyset)=0$）列表得：

j＼i	0	1	2	3	4	5	6	7	8	9	10
0	1	1	2	4	6	12	24	44	88	176	344
1	0	1	1	2	6	10	20	44	84	168	344
2	0	0	1	2	4	10	20	40	84	168	336

故答案为 $f_{10,0}=344$.