| Submit | All submissions | Best solutions | Back to list |
FACTMULM - Product of factorials (medium) |
You need to find the product of the first n factorials, so 1! * 2! * ... * n! modulo p, where p=63303212889375877567328165411288303907410870625225931671654121339922293885519921.
Input
An integer T, denoting the number of testcases (T≤10). Each of the T following lines contains a positive integer, where
n≤ 10^8.
Output
Output T lines, the case number followed by the answer. See the sample output for the correct format!
Example
Input: 7 1 5 100 429 1000 1000000 100000000 Output: Case 1: 1 Case 2: 34560 Case 3: 30320185692040509343149810686654647278680728299485184027723296362520679295668953 Case 4: 49116522183503229678644619968184124916695876848076217702050317922528502280661110 Case 5: 38310494067749735972957877453766730719859042112664856832928508845605975573300554 Case 6: 59623175509081913319809873890125269865036398088611331352359071382248773213856402 Case 7: 43046234475587180053977224639514165196068475389708692929440906111909653614719387
| Added by: | Robert Gerbicz |
| Date: | 2013-08-23 |
| Time limit: | 2s-3.5s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | FACTMUL |
hide comments
|
|||||
|
2019-01-05 09:07:00 [Lakshman]
This problem was in my TODO list for long and now I have the solution, But my solution is not much convincing. Initially, I tried with prime and superfactorial prime factorization and all leade to TLE. My current solution heavily depends on the precomputed value which I think is not the expected solution. @Robert Gerbicz can you please tell me if other users also solved this problem the way I have done or are there really any algorithm which can be used to solve this problem. Thanks =(Francky)=> My solution is (at this time) the fastest python one, and use precomputed stuff, and many tricks; it is said by gerrob to use all know tricks. (comments below). Best regards ;-) Thanks, @Francky For now I have used only one trick. Last edit: 2019-01-06 16:50:00 |
|||||
|
2015-02-01 07:09:59 Raj Kumar Chauhan
TLE in python :( any special algo? (gerrob) O(T*n) algorithms will get only TLE. Last edit: 2015-02-01 18:27:41 |
|||||
|
2014-08-26 13:21:21 Robert Gerbicz
@Francky: There is no more trick/idea. --ans(Francky)--> Thanks. Last edit: 2014-03-04 22:59:11 |
|||||
|
2014-03-03 01:15:56 Francky
@Robert Gerbicz : The 2013-09-09 17:43:39, you spoke about a new idea. Is it my last one, or do you have another ? Last edit: 2014-03-04 22:54:41 |
|||||
|
2013-09-12 13:16:58 Michael Kharitonov
@Robert Gerbicz: Number of test cases are not enough, result depends on luck. Again, 0.01 expected time difference and 0.25 real.(id=10009560,10009609) Last edit: 2013-09-12 13:18:18 |
|||||
|
2013-09-05 14:46:05 Michael Kharitonov
@Robert Gerbicz: 4 tests are not enough. My almost equal (~0.001 expected time difference) solutions gain different (~0.15) results. (gerrob) A total combined time of less than 2 sec. would be possible, every solution misses at least one idea. Last edit: 2013-09-09 17:43:39 |
|||||
|
2013-09-05 14:06:48 Michael Kharitonov
@Sidharth Gupta: Yes, it is possible to solve it in C/C++, but it is hard! My python solution is much easier. Last edit: 2013-09-05 15:50:55 |
|||||
|
2013-08-26 00:49:11 Miguel Oliveira
Thank you for checking this out and increase the time limit. My python knowledge is quite poor. I tried several things except exploiting the input distribution (there's not much point in doing that) and my code is a complete mess. This is one of those problems where I would really like to be able to read others code to learn how to code things efficiently in python. |
|||||
|
2013-08-25 23:17:01 Robert Gerbicz
The last two files was uniform random, and you had TLE only on the last one. 10 n values is so small, it depends only on luck (or on some submissions) to get AC or TLE, as the distribution of n values has a small effect on running time. Increased the time limit on these files to 3.5 sec. ps. My sample solution has AC in 7.29 sec. (in python 3), but this hasn't used your trick, (used another trick). Last edit: 2013-08-25 23:22:53 |
|||||
|
2013-08-25 20:01:07 Miguel Oliveira
I'm clueless. I tried a few things like exploring the primes, optimize the modulo operations but these didn't improve anything. Could you give a hint? Either here or by e-mail if you prefer (it's on my profile). Thanks in advance |
|||||
RSS