Solving problem in Field-Extension

Revision en15, by rareone0602, 2019-05-23 17:34:23

Hello Codeforcers! As a student of department of mathematics, I'd like to demonstrate an application of Extended Field.

The idea 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

I use the word "smallest" with the sense that if P split over E, .

In the other word, P decomposes into linear factor under it's splitting field.

Example

  1. P = x2 + 1 does not split over but split over where which is widely used as complex.

  2. Let p = 998244353 = 7 * 17 * 223 + 1, P = x224 - 1 does not split over but split over where . The multiplication order ord(w2) = 223.

  3. Let p = 109 + 7, Fibonacci number can be easily written as . Where φ, ψ are both root of (Remark that x2 = 5 has no root in Z_p)

Problem Solving

The problem to be demonstrated is 718C - Sasha and Array, which 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.)

In the problem, we should handle Fibonacci number 1, 1, 2, 3, 5, 8, ... with the formula . Once we have decompose the Fibonacci into two sequence of number powers. The problem becomes.

My 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; }
};

Once a splitting field implementation is done, we can FFT under Zp more than. I haven't implemented it yet.

Tags #number theory, #math, polynomials

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en26 English rareone0602 2019-05-23 19:14:45 1
en25 English rareone0602 2019-05-23 19:08:03 0 (published)
en24 English rareone0602 2019-05-23 19:06:10 44
en23 English rareone0602 2019-05-23 18:51:14 36 Tiny change: ';\n~~~~~\n\n\n\nFFT\' -> ';\n~~~~~\nMy submission: [submission:54522918]\n\n\nFFT\'
en22 English rareone0602 2019-05-23 18:49:59 25 Tiny change: 'FFT\n---\nSince FFT n' -> 'FFT\n---\nAs the second example, since FFT n'
en21 English rareone0602 2019-05-23 18:46:39 127
en20 English rareone0602 2019-05-23 18:35:23 274
en19 English rareone0602 2019-05-23 18:18:10 366
en18 English rareone0602 2019-05-23 17:55:11 122
en17 English rareone0602 2019-05-23 17:51:33 21
en16 English rareone0602 2019-05-23 17:49:48 634
en15 English rareone0602 2019-05-23 17:34:23 2031
en14 English rareone0602 2019-05-23 17:20:18 104
en13 English rareone0602 2019-05-23 17:14:46 235
en12 English rareone0602 2019-05-23 17:08:27 3
en11 English rareone0602 2019-05-23 17:07:40 147
en10 English rareone0602 2019-05-23 16:56:31 92
en9 English rareone0602 2019-05-23 16:52:53 26
en8 English rareone0602 2019-05-23 16:50:39 95
en7 English rareone0602 2019-05-23 16:48:39 362
en6 English rareone0602 2019-05-23 16:32:08 114
en5 English rareone0602 2019-05-23 16:28:30 94
en4 English rareone0602 2019-05-23 16:25:27 373
en3 English rareone0602 2019-05-23 00:54:58 38
en2 English rareone0602 2019-02-03 13:05:57 36
en1 English rareone0602 2019-02-03 05:10:44 163 Initial revision (saved to drafts)