For Binomial Fever problem I used simple geometric progression for:
Test Case r=2:
my code is
‘’’
for r=2
ans = pC2+p^2C2+…
ans = (p(p-1)+p^2(p^2-1)+…+p^n(p^n-1)/2
ans = ((p^2 + p^4 + p^6 + … + p^2n) - (p + p^2 + p^3 +…+ p^n))/2
ans = (G.P of p^2 - G.P of n)/2
‘’’
t = int(input())
m = 998244353
for i in range(t):
n,p,r = map(int,input().split())
a = pow(p,n,m)
b = ap%m
a = (p((a-1)(b-1))%m)%m
c = pow(pp-1,m-2,m)
c2 = pow(2,m-2,m)
if r==2: print((a*(c*c2)%m)%m)
It gave WA, can some explain me why I am getting WA?
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.
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)
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))
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.
@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
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.
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.
) to get 100 pts.
