FLOWGROW - Flower growing

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.


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)

hide comments
2012-08-04 20:42:19 Soumajyoti
Got an AC!!:)
2009-10-10 18:12:43 anshuman mishra
is k = 0 possible?
plz reply
2009-09-10 16:19:19 Drew Saltarelli
what happened to "please don't make problems with time limits of less than 0.5s" ? -.-
2009-07-25 14:25:34 :D
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.
2009-06-08 16:25:00 piyifan
I use an algorithm with time complexity O(logm+logn*(7^3)+k) got TLE.
Have somebody used it AC?
2009-06-08 16:25:00 [Trichromatic] XilinX
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
2009-06-08 16:25:00 .:: Pratik ::.
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
I have improved my I/O too, besides this is too much biased for C++ people, what if somebody decides to write in Java.

Just a question, is k <= 7 ,
if not so my solution is super-slow :)

Re: "quite expensive", but not very ;) so try to find a way to improve your execution time, several ones got AC with SUPER time :)

Last edit: 2009-06-08 00:36:16
2009-06-08 16:25:00 AnhDQ
right :-) Time limit is too easy for all ;-) enjoy!
2009-06-08 16:25:00 Robert Gerbicz
Or your code is super-slow :)
I've checked on Vietnamese site the same problem has already solved by 5 peoples (including me), the fastest is my: 0.16 sec. The slowest is 1.15 sec.

Last edit: 2009-06-05 19:11:46
2009-06-08 16:25:00 .:: Pratik ::.
Time limit is super-strict :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.