| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
KTUAN - Phân tích số |
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
| Được gửi lên bởi: | VOJ problem setters |
| Ngày: | 2007-10-31 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED |
| Nguồn bài: | Được add lên bởi Khúc Anh Tuấn |
hide comments
|
2019-02-23 02:57:08
Ban đầu mình nghĩ là QHĐ, Tuy nhiên...cách làm này không khả quan. Mong mọi người gợi ý giải thuật. |
|
|
2017-01-20 19:07:21
ac đc rồi hay lắm đm :) |
|
|
2016-10-26 17:46:37 Anh Duc Le
Hình như là có test n=0 @@ |
|
|
2015-09-08 14:22:09
https://thewizard6296.wordpress.com/2015/09/04/5/ |
|
|
2015-08-18 13:42:54 Sơn Tùng M-TP
N=10^5 sao quy hoach dong? :((( |
RSS