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
.
In the other word, P decomposes into linear factor under it's splitting field.
For example: 1. P = x2 + 1 does not split over but split over where 2. P = x224 - 1 does not split over but split over where and w2 has multiplication order 223
The problem to be demonstrated is 718C - Sasha and Array.
In the problem, we should handle Fibonacci number 1, 1, 2, 3, 5, 8, .... f(n) = x^2 + x + 1
Once a splitting field implementation is done, we can FFT under module more than