PROBLEM LINK:
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.
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.
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.
Note that {\omega}^n = 1.
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.
