[LEETCODE 2787] – Ways to Express an Integer as Sum of Powers

by admin | Aug 17, 2025 | Cấu trúc dữ liệu và giải thuật, Hướng dẫn giải, Quy hoạch động | 0 comments

Đề gốc:

https://leetcode.com/problems/ways-to-express-an-integer-as-sum-of-powers/

Bản dịch:

https://oj.program.edu.vn/problem/cpa_weisp

Tóm tắt:

Đếm số cách viết $n$ thành tổng các lũy thừa bậc $x$ của các số nguyên dương khác nhau:
$n = n_1^x + n_2^x + \cdots + n_k^x$, mỗi số $n_i$ dùng nhiều nhất một lần.

Input: hai số nguyên dương $n, x$.
Output: số cách biểu diễn $n$ thành tổng các lũy thừa bậc $x$ của các số nguyên dương khác nhau, kết quả có thể rất lớn nên chỉ cần ghi ra kết quả sau khi chia lấy phần dư (modulo) cho $10^9+7$.
Ràng buộc: $1 \le n \le 300$, $1 \le x \le 5$.

Gợi ý:

Từ mô tả yêu cầu, có thể phát biểu thành đếm số tập con của $V={1^x,2^x,\ldots,\lfloor n^{1/x}\rfloor^x}$ có tổng bằng $n$.
DP 1 chiều:

Khởi tạo $dp[0]=1$; với mỗi $v\in V$, duyệt $s$ từ $n \rightarrow v$:

$dp[s] \leftarrow \big(dp[s] + dp[s-v]\big)\bmod 10^9+7$.

Đáp án là $dp[n]$.

Chỉ cần xét những số $i$ sao cho $i^x \le n$. Gọi:

$m = \lfloor n^{1/x} \rfloor$,
$V = [1^x, 2^x, \ldots, m^x]$.

Bài toán trở thành:

Đếm số tập con của $V$ có tổng bằng $n$ — biến thể chuẩn của 0/1 knapsack đếm số cách (subset-sum counting).

Phương án Quy hoạch động

Ý nghĩa: $dp[s]$ là số cách chọn vài phần tử từ $V$ có tổng đúng $s$ (mod $10^9+7$).

Khởi tạo: $dp[0]=1$ (một cách để được tổng 0: chọn tập rỗng).
Chuyển trạng thái: với mỗi $v\in V$, cập nhật $$
\forall s\in [v..n]:\quad dp[s] \leftarrow (dp[s] + dp[s – v]) \bmod 10^9+7,
$$ duyệt giảm $s$ để đảm bảo mỗi phần tử được dùng tối đa một lần.

Độ phức tạp: đặt $k=m=\lfloor n^{1/x}\rfloor$. Thời gian $O(nk)$, bộ nhớ $O(n)$.

Chứng minh

Mọi biểu diễn hợp lệ chỉ dùng các phần tử trong $V$ (vì nếu $i^x>n$ thì không thể tham gia tổng).
Cập nhật $dp[s] \leftarrow dp[s] + dp[s-v]$ thêm vào tất cả các cách tạo $s-v$ rồi gắn $v$, sinh đúng các cách tạo $s$ phân biệt.
Duyệt $s$ giảm ngăn việc dùng cùng $v$ nhiều hơn một lần, bảo toàn tính “khác nhau”.

Cài đặt tham khảo

C++ (DP 1 chiều, lũy thừa nguyên an toàn tràn)

#include <bits/stdc++.h>
using namespace std;

static const int MOD = 1'000'000'007;

long long ipow_cap(long long a, int e, long long cap) {
    long long r = 1;
    for (int i = 0; i < e; ++i) {
        if (r > cap / a) return cap + 1; // cắt sớm nếu vượt cap
        r *= a;
    }
    return r;
}

int numberOfWays(int n, int x) {
    vector<int> vals;
    for (long long i = 1;; ++i) {
        long long p = ipow_cap(i, x, n);
        if (p > n) break;
        vals.push_back((int)p);
    }

    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int v : vals) {
        for (int s = n; s >= v; --s) {
            dp[s] += dp[s - v];
            if (dp[s] >= MOD) dp[s] -= MOD;
        }
    }
    return dp[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, x;
    if (!(cin >> n >> x)) return 0;
    cout << numberOfWays(n, x) << "\n";
    return 0;
}

Python (đệ quy + ghi nhớ để đối chiếu)

from functools import lru_cache
MOD = 10**9 + 7

def numberOfWays(n: int, x: int) -> int:
    vals = []
    i = 1
    while True:
        p = i ** x
        if p > n: break
        vals.append(p)
        i += 1

    @lru_cache(maxsize=None)
    def dfs(i: int, s: int) -> int:
        if s == n: return 1
        if s > n or i == len(vals): return 0
        return (dfs(i + 1, s) + dfs(i + 1, s + vals[i])) % MOD

    return dfs(0, 0)

Ví dụ minh họa

Input	Output	Giải thích
`10 2`	1	$10 = 3^2 + 1^2$ là cách duy nhất.
`4 1`	2	Hai cách: $4 = 4^1$ và $4 = 3^1 + 1^1$.

Mẹo cài đặt & lỗi thường gặp

Tính $i^x$: dùng lũy thừa nguyên có “cắt sớm” khi vượt $n$ thay vì pow số thực.
Duyệt tổng giảm: bắt buộc trong 0/1 knapsack; duyệt tăng sẽ cho phép dùng lại phần tử $\Rightarrow$ sai.
Modulo: áp dụng sau mỗi phép cộng để tuân thủ $10^9+7$ và tránh tràn.
Biên nhỏ: khi $n$ nhỏ hoặc $x$ lớn, $m=\lfloor n^{1/x}\rfloor$ nhỏ $\Rightarrow$ chạy rất nhanh.

Bài tập mở rộng

Cho phép lặp (unbounded): mỗi $i^x$ dùng nhiều lần $\Rightarrow$ knapsack không giới hạn, duyệt tổng tăng.
Cố định số phần tử (đúng $k$ số): thêm chiều $k$ cho $dp$.
Meet-in-the-middle cho bài mở rộng với $n$ lớn hơn.

Kết luận

Bản chất bài toán là đếm số tập con đạt tổng trên tập các lũy thừa bậc $x$. Quy hoạch động 1 chiều với duyệt tổng giảm cho lời giải gọn, đúng và hiệu quả trong ràng buộc $n \le 300$, $x \le 5$.