All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
One day Chef had an exam on probability theory. Nothing interesting, but the exam was going fishily easy. And finally Chef got to the last question:
"Suppose you have a dice with K faces with numbers from 1 to K written on it, and integers L and F(0 < L <= K). You roll it N times. Let ai be the number of times (out of the N rolls) that a face with number i written on it came up as the top face of the dice. Find the mathematical expectation of the value a1F * a2F * ... * aLF."
"I'll drop out of university and won't be allowed to cook" - Chef is frightened! Help him now or he will never be able to please you with tasty dishes again.
The first line of the input contains an integer T denoting the number of test cases. Each of the following T lines describe one test case and contain 4 space-separated integers N, K, L and F.
Let the answer for a test case be an fraction P / Q, where P and Q are integers. Let integer X be P * Q-1 modulo 2003, where Q-1 modulo 2003 is the modular multiplicative inverse of Q modulo 2003 or 0 if Q-1 modulo 2003 doesn't exist. For each test case, output a single line containing the integer X for this test case.
- 1 ≤ T ≤ 50
- 0 < N, K ≤ 109
- 0 < F ≤ 1000
- 0 < L * F ≤ 50 000
- Subtask #1[39 points]: F = 1
- Subtask #2[61 points] : no additional constraints
Input 1 2 6 2 1 Output: 779
We roll the 6-face dice 2 times, and we are interested in the value a1 * a2. The only two possible scenarios when this value is not zero are (1, 2) and (2, 1). Both of them have a1 * a2 = 1 and happen with probability 1 / 36 each. It means that P / Q = (1 + 1) / 36 = 1 / 18, so the answer is, X = 779.
|Tags||advanced-math, combinatorics, fft, hard, july15, maths, pavel1996|
|Time Limit:||5 - 20 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.