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 的方案
取模	避免大數溢出