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]*1ll*i%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.