Phân tích (Hard)

Điểm: 100,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

hieuhoccode

Dạng bài

Cho số nguyên n, đếm số cách phân tích n thành tổng các số nguyên dương (thứ tự không quan trọng).
Ví dụ: n = 3 có 4 cách là:

1 + 1 + 1
1 + 2
2 + 1
3

Input

Đầu vào chứa số nguyên n (1 ≤ n ≤ 10¹⁸).

Output

Số cách phân tích.Vì kết quả rất lớn nên mọi người hãy chia dư cho 10⁹ + 7 nhé.

Sample Input

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

Duckduck1234 đã bình luận lúc 2, Tháng 2, 2025, 1:04

include <bits/stdc++.h>

using namespace std;

using ull = unsigned long long; const ull MOD = 1000000007; // 1e9 + 7 viết tường minh

int main() { ull n; cin >> n; vector<ull> dp(n + 1, 0);

dp[0] = 1; // Khởi tạo base case
for (ull i = 1; i <= n; i++) {  // Lặp qua từng số từ 1 đến n
    for (ull j = i; j <= n; j++) {  // Cập nhật dp[j] với số i
        dp[j] = (dp[j] + dp[j - i]) % MOD;  // Sử dụng mod 1000000007 để tránh tràn số
    }
}

cout << dp[n] << endl; // Xuất kết quả
return 0;

}