CIELGAME - Editorial

PROBLEM LINKS

Practice
Contest

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.

//