KTUAN - Phân tích số
Giới hạn- Thời gian: 0.597s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
- Người up: beo_map
- Nguồn bài: Ðược add lên bởi Khúc Anh Tuấn