I’ve used the same logic, and get WA in SB 2
For all cases where p=998244352, ie p=mod-1, inverse modulo does not exist for (p^2-1) as one of its factor is (p+1) , which is mod itself. As you know for inverse modulo to exist , the number should be co-prime with the modulo .
Ex:
1 998244352 2
Your code will give wrong answer (0) for this case.
5 Likes
Welcome 
Cool! I was stuck at the same problem but how do you get around it?
A normal for loop would take 10 sec to calculate 10e9 998244352 2.
I temporarily got around it by using an if condition assuming the above test case( and i was right lol)
and yes simply if p == mod-1 and r =2 then print(ceil(n/2) … @singhpriyank
(for 15 marks see —> CodeChef: Practical coding for everyone)
basically i saw a pattern from n=1 to100 ( when p ==mod-1 and r =2) the answer should be
1
1
2
2
3
3
and so on but when i saw my solution gives 0,0,0,0,… so i write a condition if p==mod- 1 and r =2 then print(ceil(n/2))
(for 15 marks see —> CodeChef: Practical coding for everyone)
1 Like
(P/Q) %m, when gcd(Q,m)!=1, is ((P % (Q*m)) / Q)
This will be sufficient for 15 pts in python, you may need big int in c++ for using this.
For other subtasks:
Sum of GP by recursion will help you:
1 + a + a^2 + ... + a^(2*n+1) = (1 + a) * (1 + (a^2) + (a^2)^2 + ... + (a^2)^n)
Use this to get sum of gp under modulo without need of finding inverse modulo.
you got 100pts?
Along with this i used divide and conquer over NTT(not my implementation 
) to get 100 pts.
@njha1999 I also tried to solve it using that approach but mine failed for larger testcases. I used NTT to generate coefficients for the polynomial x(1+x)(2+x)(3+x)… and so on till (x+r) I used divide and conquer approach here, i solve for left and right using recurssion and multiply polynomial using NTT.
However in all my analysis it failed for larger testcases
Subtask 4 of this editorial can help I guess.
1 Like
Didn’t know ‘bout that page. My friend told me there’s an editorial on codechef sayin’ how to solve it quickly and I just looked through his submitted problems.
So what did you do to get to 100 pts? I took NTT implementation from tourist’s solution 
Damn dude, thanks for this site! It’s gonna be real helpful
Same thing happened with me in the contest!! I still dont know the problem
Welcome
I really enjoyed solving this problem and learned about FFT and NTT while solving this problem. Can anybody briefly explain what are the changes to be made in order to get AC for r = 10^6. I ran my code for r = 10^6 which was taking 10 - 15 seconds in my laptop. How to improve that?
[Edit] I used cp-algorithms to learn NTT.
1 Like
Check Video of tmwilliamlin
He explains the difference of 80 pts to 100pts solutions.
1 Like