I am solving this problem but I don’t understand why this this solution is Accepted and why this it not ? (Well I understand the reason that in the last case at time of taking inverse the modulo number is not prime but why the upper one got accepted as => (a ^ b) % mod = a ^(b % (mod-1)) % mod for large b).
Can someone please help me understanding this.
@taran_1407 @vijju123 can you please look into it.
I dont understand the issue. Are you asking that why is a^b\%mod \equiv a^{b \% (mod-1)}\%mod?? Or is it giving wrong answer for the question??
In the last solution what I did is just changed the denominator’s mod value to (mod - 1) thinking that It will overflow and I have to raise it to the power with (mod - 2) but it gives WA. But when I submitted with same mod as the numerator (i.e. 10^9 + 7) instead of (10^9 + 6) it gets AC.
I don’t understand the reason why? Because ideally if the exponent is large we must mod it with (actual_mod - 1) but here it is not the case.
@vijju123 can you please look into it once more?
I don’t get it completely. If the power is large, you only do power mod p-1 where p is the modulo needed. Rest of the steps remain the same. I strongly feel you are calculating a^{b\%(mod-1)}\%(mod-1) instead of a^{b\%(mod-1)}\%mod in the wrong solution, because I cannot pinpoint the line where you modded power.
If it’s the case then why the right one got accepted? Because in that I don’t use (mod-1) anywhere!
Can you pinpoint the line where you performed modulo operation on power?
In this solution all the mods are just mod(i.e. 1e9+7) (i don’t use a single ( mod - 1) here) . And in this solution all the functions (nCr, ways, fast_pow) have the mod in their arguments and the mod values are passed to them during their call → ways(f-rf, rf, mod-1) (In previous solution also, mod value is passed everywhere but I am not using any of them inside the function)
Yeah, so when you pass (mod-1) to ways() function, aren’t you technically finding a^b\%(mod-1) which is wrong?
thanks for pointing this out. But my question still remains. Why the first one got accepted as in that solution I have never used (mod - 1)!
Because there was no need for mod-1? The power never exceeded limits of long long afaik. You have not performed mod-1 thing with power in BOTH of solutions. The other gets WA because there you modded the entire term with mod-1 instead of modding just the power.