eval(P,x[]): # returns map x : P(x)
if P = constant: return map [a : constant for a in x]
P(a) = P1(a**2)+a*P2(a**2)
x2 = set [(a**2)% for a in x]
y1 = eval(P1,x2)
y2 = eval(P2,x2)
return map [a : (y1[a**2]+a*y2[a**2])% for a in x]
Tada!
It turns out that the number of different values of x^{2^k}\ \% is approx. mod/2^k, and since the degrees of polynomials P_1,P_2 are halved everytime you go deeper in the recursion, the time complexity is O(mod\log^2{mod}).
That second logarithm is annoying, but we can improve it by using the fact that the set x2 depends only on recursion depth and not on the polynomials, and then the small value of mod to replace map access (by value) with array access (by index). It’s sufficient to use two arrays for each recursion depth, then, which gives us O(mod\log{mod}) in both time and memory.
You call this simple? I think there must be a number to the relative hardness of the problem, based on number of attempts, the rating of coders who attempted it, those who got it right, those who couldn’t, etc. ‘Simple’ is like too much!
@dpraveen In line 116 in your code, you have done REP(add, 3), when add is the name of the function you have used to add modulo mod. It’s creating a confusion, please replace it with another variable name.
Why is it needed to decompose in 3 polynomials ?? Can we concat 2^18 zeroes so that final polynomial becomes of 2^20 numbers which is perfect square and do NTT?? @n1t1n_153012
Hi Xellos0, "It turns out that the number of different values of x^{2^k} % is approx mod/2^k", this fact you can prove directly using FFT. Instead if you see the pseudo code that I have shown in the editorial, it directly maps to yours except the generator part, which can be omitted too if one wants
Poor editorial. Can u please explain with a good example. Suppose the modulo was 10^9+7(in most cases) and the problem is same with constraints on a(i) and x(i) being <= 10^9 , how to solve this?
Btw I am new to this and have less idea of FFT.
Then read what FFT is instead of complainin’ an editorial is poor just because you can’t comprehend it, see?
If the problem itself have more specific constraints, why would the editorialist have to explain beyond it? Ain’t their responsibility.
Yeah. I see now. I didn’t notice the date.
I am really sorry though.
Another thing, I am really having trouble to visualize the solution here. Can you please explain why do we take 3 polynomial here and what is it going on when we are combining three polynomials into the answer?
