Problem hidden
KTUAN - Phân tích số
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/ktuan
Hãy đếm số cách phân tích số N ( N<=100000 ) thành tổng các số nguyên dương.
Lưu ý 2 cách chỉ khác nhau về thứ tự các số hạng được coi là giống nhau. Ví dụ 4 có 5 cách phân tích sau:
4 = 1 + 1 + 1 + 1
4 = 1 + 1 + 2
4 = 1 + 3
4 = 2 + 2
4 = 4
Hai cách phân tích 4 = 1 + 3 = 3 + 1 chỉ được tính một lần.
Vì kết quả sẽ rất lớn nên các bạn chỉ cần đưa ra phần dư của phép chia số cách tìm được cho 1000000000 ( 10^9 ).
Input
Một số tự nhiên N duy nhất.
Output
In ra phần dư của của số cách tìm được cho 10^9.
Example
Input: 4 Output: 5
Added by: | VOJ problem setters |
Date: | 2007-10-31 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 |
Resource: | Được add lên bởi Khúc Anh Tuấn |