Recently I saw the editorial for problem POLYEVAL on codechef. The problem became simple because of small modulo.
However could someone share their implementation of N point evaluation algorithm for an n-degree polynomial. Consider the modulus to be (10^9+7).
I was reading an n*log^2(n) algorithm but couldn’t find a good implementation.
Please help.
1 Like
How about NTT+ Lagrange Interpolation.
I has used it to implement a n-point evaluation problem, but may be this polynomial may be special =))
FACTMODP on SPOJ