last day I tried to understand & implement NTT, I did what I saw and what I learn on cp-algo and other code. But it’s giving me TLE, can anyone help me to figure out where I am getting TLE.
here is my code link My solution.
and here is the problem link Problem.
How are you making selection nCr
hmm, like I calculated all of factorial and inv_factorial, and them just multiplying in o(1)
I’m not sure, but u want me to calculate fact like that ```void pre()
{
fact[0] = 1;
int i;
For(i,1,mxn-1)
fact[i] = fact[i-1]1lli%mo;
inv[mxn-1] = power(fact[mxn-1], mo-2);
Rep(i, mxn-2, 0)
inv[i] = inv[i+1]1ll(i+1)%mo;
}
I implemented this code in my code, but it still giving me TLE
I converted my java code to C++. It is based on convolution using NTT.
I got the implementation from here.
PS- I have no idea why my code TLEs in java but runs in < 1sec in C++
you can try to optimize the part where you are calculating the value of y in fft, instead you can make an array outside the fft function since it only depends on the value of n and not on the actual array elements.