Hello Codeforcers!↵
↵
I'd like to demonstrate an application of Extended Field. ↵
Sometimes a problem may be easier to solve if a (hidden or not) polynomial can be decomposed into product of linear terms. (Most of the time it's not the solution of tutorial.) In this case, we can try to extend the field to solve the problem.↵
↵
↵
↵
↵
↵
↵
Extended Field↵
==========================↵
↵
The idea↵
--------↵
↵
First we should include the idea of splitting field, **a splitting field $F$ of a (may assumed) monic polynomial $P$ is the smallest field such that**↵
$$↵
P(x) = \prod_{i}(x - x_i), x_i \in F↵
$$↵
I use the word "smallest" with the sense that if $P$ split over $E$, $F \subset E$.↵
↵
In the other word, P decomposes into linear factor under its splitting field.↵
↵
↵
In most of the problems, we need not to find the exact splitting field... Just a field that $P$ split over it is enough.↵
↵
↵
↵
↵
↵
↵
↵
↵
Example↵
-------↵
↵
1. $P = x^2 + 1$ does not split over $\mathbb{Q}$ but split over $\mathbb{Q}(i)$ where ↵
$\mathbb{Q}(i) = \{a + bi | a, b \in \mathbb{Q} \}$ which is widely used as complex.↵
↵
2. Let $p = 998244353 = 7 * 17 * 2^23 + 1$, $P = x^{2^{24}} - 1$ does not split over $\mathbb{Z}_p$ but split over $\mathbb{Z}_p(w)= \{a + bw | a, b \in \mathbb{Q} \}$ where $w \notin \mathbb{Z}_p, w^2 \in \mathbb{Z}_p$. The multiplication order $ord(w^2) = 2^23$.↵
↵
3. Let $p = 10^9 + 7$, Fibonacci number can be easily written as $f_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$. where $\phi, \psi$ (the [golden ratio](https://en.wikipedia.org/wiki/Golden_ratio) and it's conjugate) are both root of $x^2 - x - 1 = 0$. The splitting field is $\mathbb{Z}_p(w)= \{a + bw | a, b \in \mathbb{Z}_p, w^2 = 5\}$ (Remark that $x^2 = 5$ has no root in $Z_p$)↵
↵
↵
Problem Solving↵
===============↵
↵
↵
[problem:718C]↵
--------------↵
The problem to be demonstrated corresponds to the third example. This may be not the best solution for the problem. I've got several TL on this problem for large constant on module. But I do think that it's a nice try to solve some problems in different way :)↵
↵
The problem contains several operations:↵
↵
- shift all element of a segment to the next $x$ Fibonacci term.↵
- query for the sum of an segment↵
↵
In the problem, we can handle Fibonacci number $1, 1, 2, 3, 5, 8, \cdots$ with the formula ↵
$f_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$. Once we have decomposed the Fibonacci into two sequence of number powers. The problem becomes easier:↵
↵
- multiply a segment by $\phi^x$ and $\psi^x$ ↵
- query for the sum of an segment↵
↵
It can be easily handled by two segment tree.↵
↵
↵
### Implementation↵
↵
We can implement Extended Field using C++ class, just like complex:↵
↵
~~~~~↵
template<int sq = 5, int MOD = 1000000007>↵
class EX {↵
int re, im;↵
static int trim(int a) {↵
if (a >= MOD) a -= MOD;↵
if (a < 0) a += MOD;↵
return a;↵
}↵
static int inv(const int a) {↵
int ans = 1;↵
for (int cur = a, p = MOD - 2; p; p >>= 1, cur = 1ll * cur * cur % MOD) {↵
if (p&1) ans = 1ll * ans * cur % MOD;↵
}↵
return ans;↵
};↵
public:↵
EX(int re = 0, int im = 0) : re(re), im(im) {}↵
EX& operator=(EX oth) { return re = oth.re, im = oth.im, *this; }↵
int norm() const { ↵
return trim((1ll * re * re - 1ll * sq * im % MOD * im) % MOD);↵
}↵
EX conj() const { ↵
return EX(re, trim(MOD - im)); ↵
}↵
EX operator*(EX oth) const {↵
return EX((1ll * re * oth.re + 1ll * sq * im % MOD * oth.im) % MOD,↵
(1ll * re * oth.im + 1ll * im * oth.re) % MOD);↵
};↵
EX operator/(int n) const { ↵
return EX(1ll * re * inv(n) % MOD, 1ll * im * inv(n) % MOD);↵
}↵
EX operator/(EX oth) const { return *this * oth.conj() / oth.norm(); }↵
EX operator+(EX oth) const { return EX(trim(re + oth.re), trim(im + oth.im)); }↵
EX operator-(EX oth) const {↵
return EX(trim(re - oth.re), trim(im - oth.im));↵
}↵
EX pow(long long n) const {↵
EX ans(1);↵
for (EX a = *this; n; n >>= 1, a = a * a) {↵
if (n&1) ans = a * ans;↵
}↵
return ans;↵
}↵
bool operator==(EX oth) const { return re == oth.re and im == oth.im; }↵
bool operator!=(EX oth) const { return not (*this == oth); }↵
int real() const& { return re; }↵
int imag() const& { return im; }↵
};↵
~~~~~↵
My submission: [submission:54522918]↵
↵
↵
FFT↵
---↵
As the second example, since FFT need a root such that $x^{2^n} - 1 = 0$, the idea may be a nice approach for implementing FFT on arbitrary module. Yet I haven't found an efficient way toconstruct such an extended fieldextend such arbitrary field $\mathbb{Z}_p$.
↵
I'd like to demonstrate an application of Extended Field. ↵
Sometimes a problem may be easier to solve if a (hidden or not) polynomial can be decomposed into product of linear terms. (Most of the time it's not the solution of tutorial.) In this case, we can try to extend the field to solve the problem.↵
↵
↵
↵
↵
↵
↵
Extended Field↵
==========================↵
↵
The idea↵
--------↵
↵
First we should include the idea of splitting field, **a splitting field $F$ of a (may assumed) monic polynomial $P$ is the smallest field such that**↵
$$↵
P(x) = \prod_{i}(x - x_i), x_i \in F↵
$$↵
I use the word "smallest" with the sense that if $P$ split over $E$, $F \subset E$.↵
↵
In the other word, P decomposes into linear factor under its splitting field.↵
↵
↵
In most of the problems, we need not to find the exact splitting field... Just a field that $P$ split over it is enough.↵
↵
↵
↵
↵
↵
↵
↵
↵
Example↵
-------↵
↵
1. $P = x^2 + 1$ does not split over $\mathbb{Q}$ but split over $\mathbb{Q}(i)$ where ↵
$\mathbb{Q}(i) = \{a + bi | a, b \in \mathbb{Q} \}$ which is widely used as complex.↵
↵
2. Let $p = 998244353 = 7 * 17 * 2^23 + 1$, $P = x^{2^{24}} - 1$ does not split over $\mathbb{Z}_p$ but split over $\mathbb{Z}_p(w)= \{a + bw | a, b \in \mathbb{Q} \}$ where $w \notin \mathbb{Z}_p, w^2 \in \mathbb{Z}_p$. The multiplication order $ord(w^2) = 2^23$.↵
↵
3. Let $p = 10^9 + 7$, Fibonacci number can be easily written as $f_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$. where $\phi, \psi$ (the [golden ratio](https://en.wikipedia.org/wiki/Golden_ratio) and it's conjugate) are both root of $x^2 - x - 1 = 0$. The splitting field is $\mathbb{Z}_p(w)= \{a + bw | a, b \in \mathbb{Z}_p, w^2 = 5\}$ (Remark that $x^2 = 5$ has no root in $Z_p$)↵
↵
↵
Problem Solving↵
===============↵
↵
↵
[problem:718C]↵
--------------↵
The problem to be demonstrated corresponds to the third example. This may be not the best solution for the problem. I've got several TL on this problem for large constant on module. But I do think that it's a nice try to solve some problems in different way :)↵
↵
The problem contains several operations:↵
↵
- shift all element of a segment to the next $x$ Fibonacci term.↵
- query for the sum of an segment↵
↵
In the problem, we can handle Fibonacci number $1, 1, 2, 3, 5, 8, \cdots$ with the formula ↵
$f_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$. Once we have decomposed the Fibonacci into two sequence of number powers. The problem becomes easier:↵
↵
- multiply a segment by $\phi^x$ and $\psi^x$ ↵
- query for the sum of an segment↵
↵
It can be easily handled by two segment tree.↵
↵
↵
### Implementation↵
↵
We can implement Extended Field using C++ class, just like complex:↵
↵
~~~~~↵
template<int sq = 5, int MOD = 1000000007>↵
class EX {↵
int re, im;↵
static int trim(int a) {↵
if (a >= MOD) a -= MOD;↵
if (a < 0) a += MOD;↵
return a;↵
}↵
static int inv(const int a) {↵
int ans = 1;↵
for (int cur = a, p = MOD - 2; p; p >>= 1, cur = 1ll * cur * cur % MOD) {↵
if (p&1) ans = 1ll * ans * cur % MOD;↵
}↵
return ans;↵
};↵
public:↵
EX(int re = 0, int im = 0) : re(re), im(im) {}↵
EX& operator=(EX oth) { return re = oth.re, im = oth.im, *this; }↵
int norm() const { ↵
return trim((1ll * re * re - 1ll * sq * im % MOD * im) % MOD);↵
}↵
EX conj() const { ↵
return EX(re, trim(MOD - im)); ↵
}↵
EX operator*(EX oth) const {↵
return EX((1ll * re * oth.re + 1ll * sq * im % MOD * oth.im) % MOD,↵
(1ll * re * oth.im + 1ll * im * oth.re) % MOD);↵
};↵
EX operator/(int n) const { ↵
return EX(1ll * re * inv(n) % MOD, 1ll * im * inv(n) % MOD);↵
}↵
EX operator/(EX oth) const { return *this * oth.conj() / oth.norm(); }↵
EX operator+(EX oth) const { return EX(trim(re + oth.re), trim(im + oth.im)); }↵
EX operator-(EX oth) const {↵
return EX(trim(re - oth.re), trim(im - oth.im));↵
}↵
EX pow(long long n) const {↵
EX ans(1);↵
for (EX a = *this; n; n >>= 1, a = a * a) {↵
if (n&1) ans = a * ans;↵
}↵
return ans;↵
}↵
bool operator==(EX oth) const { return re == oth.re and im == oth.im; }↵
bool operator!=(EX oth) const { return not (*this == oth); }↵
int real() const& { return re; }↵
int imag() const& { return im; }↵
};↵
~~~~~↵
My submission: [submission:54522918]↵
↵
↵
FFT↵
---↵
As the second example, since FFT need a root such that $x^{2^n} - 1 = 0$, the idea may be a nice approach for implementing FFT on arbitrary module. Yet I haven't found an efficient way to
