PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
At first, let’s define some notations. Let f(N, M, K) be the answer of this problem. And let g(N, M, K) = f(N, M, K) - f(N-1, M, K) be the number of the valid answers if Ciel use just N menus. And let h(N, M, K) be the number of patterns of Ciel’s feeding if Ciel must use every first N menus at least once.
Then h(N, M, K) = N! * g(N, M, K), because Ciel has N! patterns for each valid answer used just N menus. And if Ciel can use first N menus (but she doesn’t have to use every menus), the number of patterns of Ciel’s feeding is
N * (N-1) * (N-2) * … * (N-K+1) * (N-K)M-K = N! / (N-K)! * (N-K)M-K, if M ≤ K
N * (N-1) * (N-2) * … * (N-M+1) = N! / (N-M)!, otherwise.
Therefore we can calculate h(N, M, K) as (the above) - h(N-1, M, K) - h(N-2, M, K) - … - h(0, M, K). Then we can obtain g(N, M, K) as h(N, M, K) / N!, and f(N, M, K) as g(0, M, K) + g(1, M, K) + … + g(N, M, K). If the factorials 0!, 1!, …, 200! and its inverses are precalculated and stored, then we can calculate the answer for each case with O(N2 log M) time.
Note that x / y is calculated as x * yP-2 in modulo P, where P is a prime. Because, let be z = x / y (not in modulo P) and z be an integer, then there is an unique integer k (0 ? k < P) such that z = x * k in modulo P, and y * yP-2 = yP-1 = 1 in modulo P by Fermat’s little theorem. Therefore k should be yP-2, since x = z * y = x * k * y in modulo P.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.