I managed to solve subtask 1 and 2 successfully and got 40 points.
How was subtask 3 supposed to be solved?
Wait a few minutes, there will be an editorial. In meanwhile you can see the solutions of all contestants now…
2 Likes
I’m reopening the question. On Facebook there was annuncement from CodeChef team - “The editorials are still being cooked in the kitchen and will be served soon.”, so maybe it won’t be few minutes…
If M had been prime-only, the problem was fairly easy. Just take the modulo inverse of the denominator as you do for nCr and multiply with the numerator. For this problem, you can keep two lists. the first list contains, for each i, those primes which appear in f[i] and are NOT co-prime with M. You also store the exponent of the prime along with it. For each i, this wont be more than 10. In the other list, you keep, for each i, the product of all the primes which appear in f[i] and are co-prime to M. when you take the product, you take the primes along with their exponents (ie, the number of times they appear in f[i]).
Now, for the answer, you can use extended euclidean algorithm for finding modular inverse of the co-prime product. For those primes which ain’t co-prime with M, you just find their final powers in the expression and multiply with the previous term (the co-prime one). This works in NlogN.
4 Likes