fnt

fnt就是把fft看为在fft mod p系下的解
相对与fft 把单位元换成g^((p-1)/n)
如果满足g^(p-1)=1且g^i(0 <= i <= p-1)双射0~p-1的整数集合 即g为p的原根 又p可以表示为p=2^k+1则这个p是一个合法的p 如 p=2^21*479+1 g=3 其余和fft程序差不多 在做ifft的时候 /len 换为 *len^-1 再把[y+1, y+len]reverse即可 fnt:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void fnt(ll y[], const ll b[], ll n, ll rev = 1)
{
  ll len = 1 << n;
  for (ll i = 0; i < len; ++i)
    y[i] = b[bit_reverse(i, n)];
  for (ll i = 1; i <= n; ++i)
  {
    ll m = 1 << i;
    ll wn = power(g, (p - 1) / m, p);
    for (ll j = 0; j < len; j += m)
    {
      ll w = 1;
      for (ll k = j; k < j + m / 2; ++k)
      {
        ll u = y[k], v = (w * y[k + m / 2]) % p;
        y[k] = (u + v) % p, y[k + m / 2] = (u - v) % p;
        w = (w * wn) % p;
      }
    }
  }
  if (rev == 1) return;
  ll re = power(len, p - 2, p);
  for (ll i = 0; i < len; ++i) y[i] = (y[i] * re % p + p) % p;
  reverse(y + 1, y + len);
}

converlution:

1
2
3
4
5
6
  ll len = 1, n = 0;
  for (; len < nn * 2; ++n, len = 1LL << n);
  fnt(tmp1, a, n);
  fnt(tmp2, b, n);
  for (ll i = 0; i < len; ++i) b[i] = (tmp1[i] * tmp2[i]) % p;
  fnt(a, b, n, -1);