「Note」Poly Template

尝试强行记忆，尝试失败。。。

把最终所有的式子写一遍。
约定 $F^{*}(x)$ 表示 $\pmod{x^{n/2}}$ 意义下的结果，$F^{R}(x)$ 表示系数翻转。

$\mathtt{Summary}$

$\mathtt{Poly \ INV}$

$$ G(0)= F(0)' \\ G(x) = G^{*}(x)(2 - F(x)G^{*}(x)) $$

$\mathtt{Poly \ Sqrt}$

$$ G(0) = \sqrt{F(0)} \\ G(x) = \frac{F(x) + G^{*}(x)^2}{2G^{*}(x)} $$

$\mathtt{Poly \ Div}$

$$ F^{R}(x) = Q^{R}(x)G^{R}(x) \pmod{x^{n - m - 1}} $$

$\mathtt{Poly \ ln}$

$$ G(0) = 0 \\ \frac{F'(x)}{F(x)} = G(x) $$

$\mathtt{Poly \ exp}$

$$ G(0) = 1 \\ G(x)=(1 - \ln B^{*}(x) + A(x))B^{*}(x) $$

$\mathtt{Poly \ quickpower}$

$$ F^{k}(x) = e^{\ln(F(x)) \times k} $$

$\mathtt{Code}$

namespace Poly {
  const int Mod = 998244353;
  const int rt = 3;
  int lim, l, cnt, r[MAXN];
  LL a[MAXN], b[MAXN], c[MAXN], d[MAXN], tmp[MAXN];
  LL qpow(LL x, int y) { LL res = 1; while (y) { if (y & 1) res = res * x % Mod; x = x * x % Mod, y >>= 1; } return res; }
  void init(int deg) {
    lim = 1, l = 0;
    while (lim < deg) lim <<= 1, l++;
    for (int i = 1; i < lim; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  }
  void ntt(LL* arr, int type) {
    for (int i = 0; i < lim; i++) if (i < r[i]) swap(arr[i], arr[r[i]]);
    for (int mid = 1; mid < lim; mid <<= 1) {
      LL w = qpow(rt, type == 1 ? (Mod - 1) / (mid << 1) : (Mod - 1) - (Mod - 1) / (mid << 1));
      for (int pos = mid << 1, j = 0; j < lim; j += pos) {
        LL now = 1;
        for (int k = 0; k < mid; k++, now = now * w % Mod) {
          LL x = arr[k + j], y = now * arr[k + j + mid] % Mod;
          arr[k + j] = (x + y) % Mod, arr[k + j + mid] = (x - y + Mod) % Mod;
        }
      }
    }
    if (type == -1) { LL inv = qpow(lim, Mod - 2); for (int i = 0; i < lim; i++) arr[i] = arr[i] * inv % Mod; }
  }
  void PolyMul(int deg, LL* f, LL* g) {
    init(deg << 1);
    ntt(f, 1), ntt(g, 1);
    for (int i = 0; i < lim; i++) f[i] = f[i] * g[i] % Mod;
    ntt(f, -1);
    for (int i = deg; i <= lim; i++) f[i] = 0;
  }
  void PolyInv(int deg, LL* f, LL* g) {
    if (deg == 1) { g[0] = qpow(f[0], Mod - 2); return; }
    PolyInv((deg + 1) >> 1, f, g);
    init(deg << 1);
    for (int i = 0; i < deg; i++) tmp[i] = f[i];
    for (int i = deg; i < lim; i++) tmp[i] = 0;
    ntt(tmp, 1), ntt(g, 1);
    for (int i = 0; i < lim; i++) g[i] = g[i] * (2 - g[i] * tmp[i] % Mod + Mod) % Mod;
    ntt(g, -1);
    for (int i = deg; i < lim; i++) g[i] = 0;
  }
  void PolySW(int deg, LL* f, LL* g) {
    if (deg == 1) { g[0] = 1; return; }
    memset(b, 0, sizeof(b)), memset(c, 0, sizeof(c)), memset(d, 0, sizeof(d));
    PolySW((deg + 1) >> 1, f, g);
    for (int i = 0; i < deg; i++) c[i] = g[i] * 2 % Mod, d[i] = g[i], b[i] = 0;
    PolyInv(deg, c, b);
    PolyMul(deg, g, d);
    for (int i = 0; i < deg; i++) g[i] = (g[i] + f[i]) % Mod;
    PolyMul(deg, g, b);
  }
  void PolySqrt(int deg, LL* f, LL* g) {
    int cnt = 1; while (cnt <= deg) cnt <<= 1;
    PolySW(cnt, f, g);
  }
  void PolyDev(int deg, LL* f, LL* g) {
    for (int i = 1; i < deg; i++) g[i - 1] = i * f[i] % Mod;
    g[deg - 1] = 0;
  }
  void PolyInvDev(int deg, LL*f, LL* g) {
    for (int i = 1; i < deg; i++) g[i] = f[i - 1] * qpow(i, Mod - 2) % Mod;
    g[0] = 0;
  }
  void Polyln(int deg, LL* f, LL* g) {
    memset(a, 0, sizeof(a)), memset(b, 0, sizeof(b));
    PolyDev(deg, f, a), PolyInv(deg, f, b);
    PolyMul(deg, a, b);
    PolyInvDev(deg, a, g);
  }
  void PolyExp(int deg, LL* f, LL* g) {
    if (deg == 1) { g[0] = 1; return; }
    PolyExp((deg + 1) >> 1, f, g);
    Polyln(deg, g, d);
    init(deg << 1);
    for (int i = 0; i < deg; i++) c[i] = f[i];
    for (int i = deg; i < lim; i++) c[i] = d[i] = 0;
    for (int i = 0; i < lim; i++) c[i] = (c[i] - d[i] + Mod) % Mod;
    c[0]++;
    ntt(g, 1), ntt(c, 1);
    for (int i = 0; i < lim; i++) g[i] = g[i] * c[i] % Mod;
    ntt(g, -1);
    for (int i = deg; i < lim; i++) g[i] = 0;
    return;
  }
}