# POLYEVAL - Editorial

**URL:** <https://discuss.codechef.com/t/polyeval-editorial/12771>\
**Category:** editorial\
**Tags:** editorial, july16, polyeval, simple, fast-fourier-transform\
**Created:** [July 19, 2016, 10:47pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771 "2016-07-19T22:47:15Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![dpraveen](https://discuss.codechef.com/user_avatar/discuss.codechef.com/dpraveen/32/24644_2.png) [@dpraveen](https://discuss.codechef.com/u/dpraveen)\
**Post date:** [July 19, 2016, 10:47pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/1 "2016-07-19T22:47:15Z")

</div>

### PROBLEM LINK:

[Practice](http://www.codechef.com/problems/POLYEVAL)  
[Contest](http://www.codechef.com/JULY16/problems/POLYEVAL)

**Author:** [Sergey Kulik](https://www.codechef.com/users/xcwgf666)  
**Tester:** [Praveen Dhinwa](http://www.codechef.com/users/mugurelionut)  
**Editorialist:** [Praveen Dhinwa](http://www.codechef.com/users/dpraveen)

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

```auto
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](http://www.codechef.com/download/Solutions/JULY16/Setter/POLYEVAL.cpp)  
[Tester’s solution](http://www.codechef.com/download/Solutions/JULY16/Editorialist/POLYEVAL.cpp)

---

<div class="post-metadata">

**Author:** ![shariquemohd](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@shariquemohd](https://discuss.codechef.com/u/shariquemohd)\
**Post date:** [July 19, 2016, 11:34pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/2 "2016-07-19T23:34:25Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![abhibansal53](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@abhibansal53](https://discuss.codechef.com/u/abhibansal53)\
**Post date:** [July 19, 2016, 11:34pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/3 "2016-07-19T23:34:55Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![n1t1n\_153012](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@n1t1n\_153012](https://discuss.codechef.com/u/n1t1n_153012)\
**Post date:** [July 20, 2016, 1:28am UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/4 "2016-07-20T01:28:57Z")

</div>

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).

---

<div class="post-metadata">

**Author:** ![xellos0](https://discuss.codechef.com/user_avatar/discuss.codechef.com/xellos0/32/24644_2.png) [@xellos0](https://discuss.codechef.com/u/xellos0)\
**Post date:** [July 20, 2016, 1:48am UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/5 "2016-07-20T01:48:06Z")

</div>

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? ( ͡° ͜ʖ ͡°)

---

<div class="post-metadata">

**Author:** ![sahilarora.535](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sahilarora.535](https://discuss.codechef.com/u/sahilarora.535)\
**Post date:** [July 20, 2016, 10:00am UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/6 "2016-07-20T10:00:43Z")

</div>

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! 😛

---

<div class="post-metadata">

**Author:** ![divyansh13](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@divyansh13](https://discuss.codechef.com/u/divyansh13)\
**Post date:** [July 21, 2016, 8:04pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/7 "2016-07-21T20:04:50Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![sdnr1](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sdnr1](https://discuss.codechef.com/u/sdnr1)\
**Post date:** [July 24, 2016, 8:23pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/8 "2016-07-24T20:23:46Z")

</div>

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];
}
```

---

<div class="post-metadata">

**Author:** ![sahilarora.535](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sahilarora.535](https://discuss.codechef.com/u/sahilarora.535)\
**Post date:** [July 28, 2016, 12:45pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/9 "2016-07-28T12:45:19Z")

</div>

@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.

---

<div class="post-metadata">

**Author:** ![siddhantg](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@siddhantg](https://discuss.codechef.com/u/siddhantg)\
**Post date:** [August 14, 2016, 10:20am UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/10 "2016-08-14T10:20:13Z")

</div>

## 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

---

<div class="post-metadata">

**Author:** ![manjunath1996](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@manjunath1996](https://discuss.codechef.com/u/manjunath1996)\
**Post date:** [March 17, 2017, 10:15pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/11 "2017-03-17T22:15:07Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![dpraveen](https://discuss.codechef.com/user_avatar/discuss.codechef.com/dpraveen/32/24644_2.png) [@dpraveen](https://discuss.codechef.com/u/dpraveen)\
**Post date:** [July 20, 2016, 2:58am UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/12 "2016-07-20T02:58:27Z")

</div>

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 🙂

---

<div class="post-metadata">

**Author:** ![xellos0](https://discuss.codechef.com/user_avatar/discuss.codechef.com/xellos0/32/24644_2.png) [@xellos0](https://discuss.codechef.com/u/xellos0)\
**Post date:** [July 23, 2016, 8:06pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/13 "2016-07-23T20:06:48Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![anon95199559](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon95199559](https://discuss.codechef.com/u/anon95199559)\
**Post date:** [December 8, 2019, 3:38pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/14 "2019-12-08T15:38:19Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![njha1999](https://discuss.codechef.com/user_avatar/discuss.codechef.com/njha1999/32/240570_2.png) [@njha1999](https://discuss.codechef.com/u/njha1999)\
**Post date:** [December 10, 2019, 5:46am UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/15 "2019-12-10T05:46:18Z")

</div>

Wait till 16th and you will get what you are looking for 🙂

---

<div class="post-metadata">

**Author:** ![anon95199559](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon95199559](https://discuss.codechef.com/u/anon95199559)\
**Post date:** [December 10, 2019, 5:16pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/16 "2019-12-10T17:16:14Z")

</div>

I didn’t understand the reason for 16th??

---

<div class="post-metadata">

**Author:** ![just1star](https://discuss.codechef.com/user_avatar/discuss.codechef.com/just1star/32/10003_2.png) [@just1star](https://discuss.codechef.com/u/just1star)\
**Post date:** [December 11, 2019, 12:21am UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/17 "2019-12-11T00:21:41Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![anon95199559](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon95199559](https://discuss.codechef.com/u/anon95199559)\
**Post date:** [December 12, 2019, 2:39pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/18 "2019-12-12T14:39:19Z")

</div>

So your motive is just to get AC somehow and problem is finished…Nice…

---

<div class="post-metadata">

**Author:** ![just1star](https://discuss.codechef.com/user_avatar/discuss.codechef.com/just1star/32/10003_2.png) [@just1star](https://discuss.codechef.com/u/just1star)\
**Post date:** [December 12, 2019, 2:49pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/19 "2019-12-12T14:49:26Z")

</div>

Ain’t my motive. But that’s the editorialist’s motive, to write the editorial detailed specifically for this 1 problem and move on.

---

<div class="post-metadata">

**Author:** ![ssrivastava990](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ssrivastava990/32/216836_2.png) [@ssrivastava990](https://discuss.codechef.com/u/ssrivastava990)\
**Post date:** [December 12, 2019, 4:03pm UTC](https://discuss.codechef.com/t/polyeval-editorial/12771/20 "2019-12-12T16:03:47Z")

</div>

i think u wanna for Binomial Fever … 😜

[Next page](https://discuss.codechef.com/t/polyeval-editorial/12771.md?page=2)