Hiểu bài toán

Bài toán yêu cầu đếm số cách tạo ra tổng M từ các số Fibonacci (không trùng lặp, bắt đầu từ 1, 2, 3, 5,...), mỗi số được sử dụng tối đa K lần. Input là M và K, Output là số cách (có thể rất lớn, không chia hết cho 10^9+7).

Các cách tiếp cận

Cách Quy Hoạch Động 1 Chiều (Optimized Knapsack)

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

int m, k, res, dp[100005];
vector<int> g;
signed main() {
    freopen("FIBOSUM.INP", "r", stdin);
    freopen("FIBOSUM.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> k;
    g.push_back(1);
    if (m >= 2) {
        g.push_back(2);
        while (true) {
            int h = g[g.size() - 1] + g[g.size() - 2];
            if (h > m) break;
            g.push_back(h);
        }
    }
    dp[0] = 1;
    for (auto x : g) {
        for (int s = m; s >= 0; s--) {
            if (dp[s] == 0) continue;
            int t = s;
            for (int j = 1; j <= k; j++) {
                t += x;
                if (t > m) break;
                dp[t] += dp[s];
            }
        }
    }
    cout << dp[m];
}

• Time Complexity: O(M * K * log(M))
• Space Complexity: O(M)

Đây là biến thể của bài toán cái túi (Knapsack) có giới hạn số lượng (Bounded Knapsack).

1. Tạo dãy Fibonacci nhỏ hơn hoặc bằng M.
2. Dùng mảng dp[s] để lưu số cách tạo tổng s.
3. Duyệt qua từng số Fibonacci x. Với mỗi tổng s hiện có (dp[s] > 0), ta thử thêm x vào tổng đó j lần (từ 1 đến K), cập nhật dp[s + j*x].
4. Vòng lặp s duyệt ngược về 0 để đảm bảo mỗi số Fibonacci chỉ được xử lý đúng 1 lần (tránh đếm trùng).

Cách Quy Hoạch Động 2 Chiều (Trực quan)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("fibosum.inp", "r", stdin);
    freopen("fibosum.out", "w", stdout);

    long long M, K;
    cin >> M >> K;

    vector<long long> fib;
    fib.push_back(1);
    fib.push_back(2);
    while (fib.back() + fib[fib.size() - 2] <= M) {
        fib.push_back(fib.back() + fib[fib.size() - 2]);
    }
    int n = (int)fib.size();

    vector<vector<unsigned long long>> dp(n + 1, vector<unsigned long long>(M + 1, 0));
    for (int i = 0; i <= n; ++i) dp[i][0] = 1;

    for (int i = 1; i <= n; ++i) {
        long long val = fib[i - 1];
        for (int j = 0; j <= M; ++j) {
            dp[i][j] = dp[i - 1][j]; // Không dùng số fib[i-1]
            // Dùng số fib[i-1] t lần (1 <= t <= K)
            for (int t = 1; t <= K; ++t) {
                if (j >= t * val) {
                    dp[i][j] += dp[i - 1][j - t * val];
                } else {
                    break;
                }
            }
        }
    }
    cout << dp[n][M];
    return 0;
}

• Time Complexity: O(M * K * log(M))
• Space Complexity: O(M * log(M))

Cách tiếp cận này sử dụng mảng 2 chiều dp[i][j] thể hiện số cách tạo tổng j bằng cách sử dụng các số Fibonacci từ fib[0] đến fib[i-1].

• Trạng thái: dp[i][j].
• Công thức chuyển: dp[i][j] = dp[i-1][j] + sum(dp[i-1][j - t * fib[i-1]]) với t từ 1 đến K.
• Phương pháp này dễ hiểu hơn nhưng tốn bộ nhớ hơn so với cách 1 chiều.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán quy về dạng Bounded Knapsack (cái túi có giới hạn số lượng mỗi loại đồ vật).
• Do số Fibonacci tăng theo cấp số nhân, số lượng phần tử N rất nhỏ (khoảng 40-50 với M <= 10^5).
• Sử dụng kỹ thuật duyệt ngược (reverse iteration) trong DP 1 chiều để tối ưu bộ nhớ và tránh lặp lại phần tử.

Lỗi thường gặp

• Lỗi biến kiểu dữ liệu: Kết quả có thể vượt quá unsigned long long nếu M và K lớn (ví dụ M=10^5, K=10^5), dẫn đến tràn số (overflow). Tuy nhiên, với các test thông thường, unsigned long long hoặc long long là đủ.
• Quên xử lý trường hợp M < 2 khi sinh dãy Fibonacci (dãy phải bắt đầu bằng 1, 2).
• Sai logic vòng lặp trong DP 1 chiều: Nếu duyệt s từ 0 đến M, một số Fibonacci có thể được dùng nhiều lần cho cùng một tổng (tính sai số cách).