FLOWGROW - Flower growing
English | Tiếng Việt |
Cho một mảnh vườn kích thước MxN được chia thành M hàng, mỗi hàng có N ô để trồng hoa. Ở mỗi ô ta có thể trồng một loài hoa có một trong 7 màu sau đây: đỏ, cam, vàng, lục, lam, chàm, tím. Để đảm bảo tính thẩm mĩ, tất cả các ô đều phải trồng hoa và ở mỗi hàng cần có ít nhất k màu hoa khác nhau.
Yêu cầu
Hãy đếm số cách trồng hoa khác nhau mà vẫn đảm bảo tính thẩm mĩ. Hai cách trồng được gọi là khác nhau nếu có ít nhất một ô khác màu.
Dữ liệu
- Gồm một số dòng, mỗi dòng ghi ba số M, N, k.
Kết quả
- Gồm một số dòng ghi các kết quả tương ứng, lấy mod 2370823708.
Ví dụ
Dữ liệu: 1 7 7 Kết quả: 5040
Giới hạn
- 1 ≤ M, N ≤ 1015.
- Số dòng trong Input không vượt quá 5000.
hide comments
Soumajyoti:
2012-08-04 20:42:19
Got an AC!!:) |
|
anshuman mishra:
2009-10-10 18:12:43
is k = 0 possible?
|
|
Drew Saltarelli:
2009-09-10 16:19:19
what happened to "please don't make problems with time limits of less than 0.5s" ? -.- |
|
:D:
2009-07-25 14:25:34
Hint for people with TLE: the modulu operation of obviusly the main problem. You don't have to do modulo after every operation, think how to minimaze it. |
|
piyifan:
2009-06-08 16:25:00
I use an algorithm with time complexity O(logm+logn*(7^3)+k) got TLE.
|
|
[Trichromatic] XilinX:
2009-06-08 16:25:00
Mmm. Time limit is very strict for an algorithm with time complexity O(logm+logn*(7^3)+k). (Although I have used this and get AC.) Last edit: 2009-06-07 12:38:51 |
|
.:: Pratik ::.:
2009-06-08 16:25:00
I have an O( k + log M ) algorithm, but I think the mod operations are quite expensive, I think if the complexity isnt any better, there is no point of optimising it to the brink, not all of us are qualified to do that :P
|
|
AnhDQ:
2009-06-08 16:25:00
right :-) Time limit is too easy for all ;-) enjoy! |
|
Robert Gerbicz:
2009-06-08 16:25:00
Or your code is super-slow :)
|
|
.:: Pratik ::.:
2009-06-08 16:25:00
Time limit is super-strict :( |
Added by: | AnhDQ |
Date: | 2009-06-05 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Mr Tuan Khuc Anh - NTU (Singapore) |