POLYEVAL - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Kulik
Tester: Praveen Dhinwa
Editorialist: Praveen Dhinwa

DIFFICULTY:

med-hard

PREREQUISITES:

fft, advanced maths

PROBLEM:

You are given a polynomial of degree N. You have to evaluate the polynomial at some Q points modulo 786433.

EXPLANATION:

Look at the special modulo
The special modulo 786433 gives you an hint for using some sort of FFT algorithm. We have 786433 = 1 + 3 * 2^{18} and 786433 is a prime.


Let us learn some basics before proceeding towards FFT algorithm
The field \mathbb{Z}/p is a set of numbers \{0, 1, \dot, p - 1\} where p is a prime with both addition and multiplication operations being mod p operations. Additive inverse of each element in the set will be 0, and the multiplicative inverse of each non-zero element will also exist. This is due to the fact that each non-zero element in the set will be co-prime to p, as p is prime. In fact it will be unique and can be found by solving the equation a b = 1 \mod p.

Let {\mathbb{Z}/p}^{+} denote the group of non-zero elements \{1, 2, \dots, p - 1\}, i.e.\mathbb{Z}/p - \{0\}. This group is a cyclic group. A group is called a cyclic group if it can be generated by a single element. In other words, g, g^2, g^3, , g^(p - 1) will cover all the elements of the group. Note that g^p = g. Such an element g is called generator of the group. For example, in group {\mathbb{Z}/5}^{+} = \{1, 2, 3, 4 \}, g = 2 is a generator. We have 2^1 = 2 \mod 5, 2^2 = 4 \mod 5, 2^3 = 3 \mod 5, 2^4 = 1 \mod 5. Note that these cover {2, 4, 3, 1}, i.e. all the elements of the group. You can see that each element of this group can be written as powers of g. Also see that 3 is also a generator of the group as 3^1 = 3 \mod 5, 3^2 = 4 \mod 5, 3^3 = 2 \mod 5, 3^4 = 1 \mod 5. However g = 4 is not a generator of the group as 4^1 = 4 \mod 5, 4^2 = 1 \mod 5, 4^3 = 4 mod 5, 4^4 = 1 \mod 5, which covers only the elements 1, 4.

You can find one such generator for the group {\mathbb{Z}/p}^{+} (for p = 786433) using a simple bruteforce. You can iterate over each number g from 1 to p-1 and check whether the g^i spans all the elements of the group or not. Luckily for this modulo, you can afford to spend \mathcal{O}(p \, log p) time for checking a number being generator or not, because you will soon hit a generator at g = 10. You can run this program offline on your computer in 1 or 2 minutes and find one such generator.

In fact, there is a better algorithm than simple bruteforce for checking whether a number is generator or not. For a given g, you just have to check whether all the g^d mod p where d is a divisor of p-1 are all distinct values or not.


Towards the FFT algorithm
Let us revisit the concept of use of FFT in evaluation of some polynomial of degree at max n at n points in \mathcal{O}(n \, log n) operations.

**Let us take a small example
Let us take an example to understand about FFT better. Suppose the polynomial be x^3 + 3 * x^2 + 4 * x + 5. We want to evaluate it at four points \omega, {\omega}^2, {\omega}^3, {\omega}^4, where \omega is a primitive 4-th root of unity, i.e. \omega^4 = 1, and there does not exist any i < 4, such that \omega^i = 1. In other words, \omega is a generator of the corresponding group.

Let us divide the polynomial into two parts - the polynomial made of coefficients of even power of x and other of odd powers of x.
In our case, these polynomials will be x^3 + 4 * x and 3 * x^2 + 5, respectively.

P(x) = $x^3 + 3 * x^2 + 4 * x + 5
P_{odd}(x) = $x^3 + 4 * x
P_{even}(x) = $3 * x^2 + 5
P(x) = x * P_{odd}(x^2) + P_{even}(x^2)

Note that now both the polynomials P_{odd}(x) and P_{even}(x) are having only even powers of x, i.e. they can even be considered polynomials in x^2. So, instead of evaluating them on x, let us evaluate them on x^2.

P(x) = x * P_{odd}(x^2) + P_{even}(x^2), \text{where } P_{odd}(x) = x + 4

Let us see what happens with set of points x where we want to evaluate the polynomail when we change x to x^2. The set of elements of x^2 for the given x will be \{\omega^2, {\omega}^4, {\omega}^6, {\omega}^8 \}.

Note that we have \omega^4 = 1, so this set will be \{\omega^2, 1, {\omega}^2, 1 \}. You see that this set has only two distinct elements in it, 1 and \omega^2.

Now you can recursively evaluate the both the polynomials P_{odd}(x) and P_{even}(x) at these two points and combine their them to get an evaluation for each of the four original x values.

Regarding the time complexity, you can notice that in the recursion, both the sizes of the polynomial and that of number of points to evaluate become half in each iteration, which gives a time complexity of \mathcal{O}(n log n) (n = 4 for our case).


Letā€™s do FFT for general n
If you understood the prevoius example, you have kind of understood the idea behind FFT. Let us generalize the same thing for a general n. For our discussion, we are considering n to be a power of 2. If the polynomial does not have degerees in form of twoā€™s power, we can append the polynomial by adding zero coefficient higher degrees. Notice that this will never increase the size of the polynomial by more than twice.

Let P(x) be the polynomial we want to evaluate at \omega, { \omega}^2, \dots, {\omega}^n points, where \omega is a primitive n-th root unity. Notice that the set \omega, { \omega}^2, \dots, {\omega}^n contains all distinct elements.

S = \{{ \omega}, { \omega}^2, \dots, {\omega}^{n - 1}, {\omega}^{n} \}
S^2 = \{ {\omega}^2, { \omega}^4, \dots, {\omega}^{2 * n} \}
S^2 = \{ {\omega}^2, { \omega}^4, \dots { \omega}^{2 * (n / 2 - 1)}, { \omega}^n, { \omega}^{2 * (n / 2 + 1)}, \dots, {\omega}^{2 * n} \}

Note that {\omega}^n = 1.

S^2 = \{{\omega}^2, { \omega}^4, \dots, { \omega}^4, { \omega}^{2}, \dots, {\omega}^{n} \}
S^2 = \{ {\omega}^2, { \omega}^4, \dots, {\omega}^{n)} \}

Note that S^2 has size \frac{n}{2}.

Also notice that {({\omega}^2)} ^ {\frac{n}{2}} = 1 \mod n \implies {({\omega}^2)} ^ {\frac{n}{2}} = 1 \mod n / 2.

Pseudo Code
Let us see the pseudo code:

evaluate(Poly, points):
    if (points.size() == 1):
        // Evaluate the polynomial using Horner's method.
    else:
        divide the polynomial into two parts, evenPoly and oddPoly depending on parity of coefficients.
        Let points' denote the set of new points on which we want to evaluate.
        Each element of points' will be square of corresponding element in points.
        evaluate(evenPoly, points')
        evaluate(oddPoly, points')
        // Evaluate the polynomial at points with help of above.

Setterā€™s and Testerā€™s Solutions:

Setterā€™s solution
Testerā€™s solution

3 Likes

As always, the links to Setterā€™s and testerā€™s solution arenā€™t working! Please look into it. Thank you

1 Like

Not able to access any solution.Please update the links.

Since 786433=1+3āˆ—2^18 and 786433 is a prime I used NTT by first dividing P(x) in three parts as P(x) = P0(x^3) + x*P1(x^3) + x^2P2(x^3) and then used NTT for polynomials P0, P1 and P2.
In this way I computed values of P(x) at all x mod 786433 (except P(0) which is equal to coefficient a0).

3 Likes

Hereā€™s my solution, no FFT required.

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.

BTW, difficulty Simple? ( Ķ”Ā° ĶœŹ– Ķ”Ā°)

2 Likes

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 :slight_smile:

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! :stuck_out_tongue:

5 Likes

Just asking, was anybody able to solve this using general multipoint evaluation ??
Or is it even practically feasible for this problem ?

1 Like

Oh, yeah, it is. I just didnā€™t think of FFT at all, expecting it to have a ā€œsimplerā€ solution, wrote a a bruteforce and modified it until it passed.

1 Like

Can anybody explain this part of the problem setterā€™s solution:

pw[0] = 1;
for(int i = 1; i < (1 << 18); i++)
    pw[i] = (pw[i - 1] * root) % mod;
for(int i = 0; i < (1 << 18); i++) {
    ans[pw[i]] = a[i];
    ans[pw[i] * 10 % mod] = b[i];
    ans[pw[i] * 100 % mod] = c[i];
}
1 Like

@dpraveen :diamonds::diamonds: 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.

Heading #### Can anyone explain step-by-step the functioning of fft function in setterā€™s soln ??

And also the importance of 786433 ??

Explanation with an example would be helpfull

I am new at this

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