2787. 将一个数字表示成幂的和的方案数
给你两个正整数 n 和 x 。
请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。
由于答案可能非常大，请你将它对 109 + 7 取余后返回。
比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。
示例 1：
输入：n = 10, x = 2 输出：1 解释：我们可以将 n 表示为：n = 32 + 12 = 10 。 这是唯一将 10 表达成不同整数 2 次方之和的方案。示例 2：
输入：n = 4, x = 1 输出：2 解释：我们可以将 n 按以下方案表示： - n = 41 = 4 。 - n = 31 + 11 = 4 。
一、算法逻辑（逐步思路）
❓ 题目描述：
给定两个整数 n 和 x，问：
有多少种方法可以用不同的正整数的 x 次幂相加，恰好等于 n？
- 每个整数最多使用一次（不能重复）；
- 返回方案数，结果对
10^9 + 7取模。
✅ 解析过程：
1. 状态定义：
- 定义
f[s]表示和为s的组合数目； - 初始化：
f[0] = 1，表示选法为空时和为 0 的唯一方案。
2. 状态转移：
- 对每个正整数
i，计算它的x次幂v = i^x； - 使用这个数能更新哪些和
s？
-
- 遍历
s从n到v（倒序，防止重复使用）； - 更新方式：
f[s] += f[s - v]
- 遍历
-
-
- 意思是：若当前组合中加入一个
v，使得和达到s，那就看以前有多少种方法能组成s - v； - 相当于经典的0/1 背包模型（每个数最多使用一次）。
- 意思是：若当前组合中加入一个
-
3. 终止条件：
- 如果当前的
i^x > n，说明无法再用于任何组合，直接退出。
4. 返回值：
f[n]表示最终组成n的合法组合数；- 对结果取模是为了防止整数溢出。
二、算法核心点
✅ 核心思想：0/1背包模型上的指数幂优化
- 每个正整数
i只能使用一次，对应背包问题中“每种物品最多取 1 次”； - 数字
v = i^x就是物品的“体积”； - 每次用
f[s] += f[s - v]实现状态转移； - 为避免重复计算、实现“每个数最多选一次”，必须倒序更新状态数组。
对应题目经典名称：
Perfect Powers Combination Problem（幂次组合计数）
class Solution:def numberOfWays(self, n: int, x: int) -> int:f = [1] + [0] * n # 初始化DP数组：f[s] 表示组成和为 s 的方案数# 初始状态：f[0] = 1，表示“和为0”的方案就是啥也不选for i in range(1, n + 1): # 枚举所有底数 i（1 到 n）v = i ** x # 当前考虑的数是 i 的 x 次幂if v > n: # 如果这个数太大，跳出循环break# 倒序遍历（0/1背包）从 n 到 vfor s in range(n, v - 1, -1):f[s] += f[s - v] # 转移方程：将 v 加入组合中，组成 sreturn f[n] % 1_000_000_007 # 返回最终和为 n 的方案数
三、复杂度分析
- 时间复杂度：O(k × n)
-
k是最多可以选择的整数个数（即i满足i^x ≤ n）；- 对每个合法
i，我们进行一次O(n)的遍历。
- 空间复杂度：O(n)
-
- 状态数组
f长度为n + 1。
- 状态数组
总结表：
| 维度 | 内容 |
| ✅ 思路逻辑 | 将问题转换为组合数问题，用 0/1 背包方式动态转移 |
| ✅ 核心技巧 | 每个数最多用一次（倒序遍历）；幂次作为体积；经典 f[s] += f[s - v] 模型 |
| ✅ 时间复杂度 | O(√n × n) 最多枚举 √n 个底数，每次遍历 n 个状态 |
| ✅ 空间复杂度 | O(n) 一维 DP 数组 |
总结思路：
| 步骤 | 内容 |
|---|---|
初始化 f[0] = 1 | 和为 0 有 1 种方式（空集） |
枚举 i = 1...n | 将 i 的 x 次幂作为候选数 |
| 倒序更新 DP 数组 | 保证每个数最多用一次（0/1背包） |
更新 f[s] += f[s - v] | 表示：新方案 = 旧方案 + 使用 v 的方案 |
| 取模 | 避免大数溢出 |
