https://www.codechef.com/viewsolution/19263984
The solution is partially accepted.
According to Fermat Little Theorem:-
x^{\binom{a}{b}} mod p = x^{\binom{a}{b} mod \left( p-1 \right) } mod p
and you have done x^{\binom{a}{b} mod \left( p \right) } mod p
you can check my solution as refrence:-https://www.codechef.com/viewsolution/19209235
It did help but I am still getting wrong answer in last three test case. With the help of your solution I did my best in optimizing the code. here is the new solution:https:-//www.codechef.com/viewsolution/19271816
1 Like
nCrModp(5500,2750,mod-1);
above line is causing WA because if you check 5500C3000 your array value will be 0 because you computed till 2750.
now to correct you have 2 ways:-
1.) compute till 5500C5500
2.) as \binom{n}{k} = \binom{n}{n-k} you can compute till 2750 but when querying value of binomial coefficients you have to make sure to change k>2750 to n-k.
1 Like
Thanks for the help bro. It worked 