Hello Codeforcers! As a student of department of mathematics, I'd like to demonstrate an application of Extended Field.
First we should include the idea of splitting field, a splitting field F of a polynomial P is the smallest field such that
![](https://espresso.codeforces.com/1d684b4200e3be3c7ad9339a69d47d818866fdda.png)
.
In the other word, P decomposes into linear factor under this field.
For example, P = x2 + 1 does not split over but splitting over
where
The problem to be demostrated is 718C - Sasha and Array
Once a splitting field implementation is done, we can FFT under module more than