「归零者」问题 题解

问题分析

核心问题

我们需要计算满足以下条件的子集 $S \subseteq \{1,2,\dots,n\}$ 的数量：

• 对于每个 $x = 1,2,\dots,n$，都存在 $S$ 的一个子集，其元素和等于 $x$

换句话说，$S$ 必须能够通过子集和生成 $1$ 到 $n$ 的所有整数。

关键观察

观察1：问题的组合本质

这是一个完备加法基（complete additive basis）的计数问题。集合 $S$ 必须满足：

• $1 \in S$（否则无法生成1）
• 如果当前能生成的最大数是 $m$，那么下一个数 $m+1$ 必须在 $m+1$ 以内有数可以扩展

观察2：递推结构

设 $f(m)$ 表示当前能生成 $1$ 到 $m$ 的所有数时，继续扩展到 $n$ 的方案数。

关键性质：如果当前能生成 $1$ 到 $m$，那么：

• 下一个选择的数必须是 $\leq m+1$ 的（否则会出现缺口）
• 如果选择 $k \leq m$，那么能生成的范围仍然是 $1$ 到 $m$
• 如果选择 $k = m+1$，那么能生成的范围扩展到 $1$ 到 $2m+1$

观察3：问题转化

这实际上等价于计算满足以下条件的序列 $a_1, a_2, \dots, a_k$ 的数量：

• $a_1 = 1$
• $a_{i+1} \leq \sum_{j=1}^i a_j + 1$
• $\sum_{j=1}^k a_j \geq n$

算法思路

方法一：动态规划

定义 $dp[i]$ 表示当前能生成 $1$ 到 $i$ 的所有数时，完成整个过程的方案数。

状态转移：

• 如果下一个选择的数是 $j$，其中 $1 \leq j \leq i+1$
• 那么新的能生成范围是 $i + j$
• 因此：$dp[i] = \sum_{j=1}^{i+1} dp[i + j]$

边界条件：$dp[i] = 1$ 当 $i \geq n$

方法二：生成函数方法

设 $F(x)$ 是答案的生成函数。通过分析组合结构，可以发现：

$$F(x) = \prod_{k=1}^n (1 + x^k)^{?}$$

其中指数需要精心设计以满足完备性条件。

方法三：组合恒等式

通过分析小数据：

• $n=1$: 1种方案 $\{1\}$
• $n=2$: 1种方案 $\{1,2\}$
• $n=3$: 2种方案 $\{1,2,3\}, \{1,3\}$
• $n=4$: 3种方案（如样例所示）

可以发现这与某种组合序列相关，可能涉及卡特兰数的变种或其它已知数列。

复杂度分析

直接DP的复杂度

• 状态数：$O(n)$
• 转移：$O(n)$ 每个状态
• 总复杂度：$O(n^2)$，对于 $n \leq 500000$ 不可行

优化思路

优化1：前缀和优化 观察状态转移：

$$dp[i] = \sum_{j=1}^{i+1} dp[i+j] = \sum_{k=i+1}^{2i+1} dp[k] $$

这可以用前缀和优化到 $O(n)$：

$$dp[i] = prefix[2i+1] - prefix[i]$$

优化2：数学公式 通过进一步分析，可能发现闭式解或递推公式，直接 $O(1)$ 或 $O(\log n)$ 计算。

实现要点

1. 模运算处理：$M$ 不一定是质数，不能直接使用逆元
2. 空间优化：只需要线性数组存储DP值
3. 边界处理：仔细处理 $i$ 接近 $n$ 的情况
4. 数值范围：注意整数溢出，及时取模

样例验证

对于 $n=4$：

• 能生成1-4的方案：$\{1,2,3\}, \{1,2,4\}, \{1,2,3,4\}$
• 验证：$1=1, 2=2, 3=3, 4=1+3$ 或 $4=4$ 或 $4=1+3$

总结

本题的核心在于识别出这是完备加法基的计数问题，并通过动态规划结合前缀和优化来高效求解。关键在于发现状态转移的规律：

$$dp[i] = \sum_{k=i+1}^{\min(2i+1, n)} dp[k]$$

这个递推式反映了完备加法基的核心性质：每次扩展时，新加入的数不能超过当前能生成的最大数加1，否则会出现无法生成的缺口。

通过前缀和优化，我们可以在 $O(n)$ 时间内解决问题，这在 $n \leq 5\times 10^5$ 的数据范围内是可行的。