查看源代码：
FFMP-20240926.md

---
title: FFMP 20240926
createTime: 2024/09/26
---

记 $\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-好子集的个数。 

:::details 答案
（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$.
:::