多项式全家桶

多项式乘法逆

我们要求$\mathrm{G}(\mathrm{x})$，使得

$$F(x) G(x) \equiv 1\left(\bmod x^{n}\right)$$

设

$$F(x) H(x) \equiv 1\left(\bmod x^{\left\lceil\frac{n}{2}\right\rceil}\right)$$

又因为

$$F(x) G(x) \equiv 1\left(\bmod x^{\left\lceil\frac{n}{2}\right\rceil}\right)$$

所以

$$F(x)(G(x)-H(x)) \equiv 0\left(\bmod x^{\left\lceil\frac{n}{2}\right\rceil}\right)$$

即

$$G(x)-H(x) \equiv 0\left(\bmod x^{\left\lceil\frac{n}{2}\right\rceil}\right)\\ G(x)^{2}+H(x)^{2}-2 G(x) H(x) \equiv 0\left(\bmod x^{n}\right)$$

两边同时乘以$\mathrm{F}(\mathrm{x})$，则有

$$G(x) \equiv2 H(x)-F(x) H(x)^{2}\left(\bmod x^{n}\right)$$

多项式对数函数

$$F(x)=\ln (x) \\ G(x)=F(A(x)) \\ G^{\prime}(x)=F^{\prime}(A(x))A^{\prime}(x)=\frac{A^{\prime}(x)}{A(x)}$$

多项式开根

$$H^{2}(x) \equiv F(x)\left(\bmod x^{\left\lceil\frac{n}{2}\right\rceil}\right) \\ G(x) \equiv H(x)\left(\bmod x^{\left\lceil\frac{n}{2}\right\rceil}\right) \\ G(x)-H(x) \equiv 0\left(\bmod x^{\left\lceil\frac{n}{2}\right\rceil}\right) \\ (G(x)-H(x))^{2} \equiv 0\left(\bmod x^{\left\lceil\frac{n}{2}\right\rceil}\right) \\ G^{2}(x)-2 H(x)G(x)+H^{2}(x) \equiv 0\left(\bmod x^{n}\right) \\ F(x)-2 H(x)G(x)+H^{2}(x) \equiv 0\left(\bmod x^{n}\right) \\ G(x)\equiv \frac{F(x)+H^{2}(x)}{2 H(x)}\left(\bmod x^{n}\right)$$

多项式指数函数

假设已知一个函数$G(x)$，求一个多项式$F(x) \bmod x^{n}$，满足方程

$$G(F(x)) \equiv 0 \left(\bmod x^{n}\right)$$

回忆一下多项式求逆的过程
首先$n=1$的时候，$G(F(x)) \equiv 0(\bmod x)$，这是要单独求出来的
现在假设已经求出了

$$G\left(F_{0}(x)\right) \equiv 0 \left(\bmod x^{\left\lceil\frac{n}{2}\right\rceil}\right)$$

考虑如何扩展到$\bmod x^{n}$下，可以把$G(F(x))$在$F_{0}(x)$这里进行泰勒展开

$$\begin{aligned} G(F(x)) &=G\left(F_{0}(x)\right) \\ &+\frac{G^{\prime}\left(F_{0}(x)\right)}{1 !}\left(F(x)-F_{0}(x)\right) \\ &+\frac{G^{\prime \prime}\left(F_{0}(x)\right)}{2 !}\left(F(x)-F_{0}(x)\right)^{2} \\ &+\cdots \end{aligned}$$

所以

$$G(F(x)) \equiv G\left(F_{0}(x)\right)+G^{\prime}\left(F_{0}(x)\right)\left(F(x)-F_{0}(x)\right) \left(\bmod x^{n}\right)$$

然后因为$G(F(x)) \equiv 0\left(\bmod x^{n}\right)$，可以得到

$$F(x) \equiv F_{0}(x)-\frac{G\left(F_{0}(x)\right)}{G^{\prime}\left(F_{0}(x)\right)} \left(\bmod x^{n}\right)$$

现在我们要求

$$F(x)=e^{A(x)}$$

等价于

$$\ln F(x)-A(x)=0$$

设

$$\begin{aligned} G(F(x))&=\ln F(x)-A(x) \\ G^{\prime}(F(x))&=\frac{1}{F(x)} \end{aligned}$$

所以有

$$\begin{aligned} F(x) & \equiv F_{0}(x)-\frac{G\left(F_{0}(x)\right)}{G^{\prime}\left(F_{0}(x)\right)} \\ & \equiv F_{0}(x)\left(1-\ln F_{0}(x)+A(x)\right) \left(\bmod x^{n}\right) \end{aligned}$$

多项式幂函数

$$\begin{aligned} G(x)&\equiv(F(x))^{k} \left(\bmod x^{n}\right) \\ \ln G(x)&\equiv k\ln F(x) \left(\bmod x^{n}\right) \\ G(x)&\equiv e^{k \ln F(x)} \left(\bmod x^{n}\right) \end{aligned}$$

完整多项式模板

#include <bits/stdc++.h>
using namespace std;

const int G = 3;
const int B = 19;
const int N = (1 << B) | 1;
const int IG = 332748118;
const int MOD = 998244353;
typedef long long ll;

inline int add(int a, int b) {
    return (a + b >= MOD) ? (a + b - MOD) : (a + b);
}
inline int dec(int a, int b) { return (a - b >= 0) ? (a - b) : (a - b + MOD); }
inline int mul(ll a, int b) { return a * b - a * b / MOD * MOD; }
inline int qpow(int x, ll y) {
    int res = 1;
    for (; y; y >>= 1, x = mul(x, x))
        if (y & 1) res = mul(res, x);
    return res;
}

struct Node {
    double x, y;
    Node() {}
    Node(const double &_x, const double &_y) : x(_x), y(_y) {}
    Node operator+(const Node &t) { return Node(x + t.x, y + t.y); }
    Node operator-(const Node &t) { return Node(x - t.x, y - t.y); }
    Node operator*(const Node &t) {
        return Node(x * t.x - y * t.y, x * t.y + y * t.x);
    }
    Node operator*(const double &k) { return Node(x * k, y * k); }
    Node operator~() { return Node(x, -y); }
    void MTTinit(int t) {
        x = t >> 15;
        y = t & 32767;
    }
};

class MathMod {
   public:
    int inv(int t) { return qpow(t, MOD - 2); }
};

class Poly : protected MathMod {
   public:
    Poly() {
        for (level = 1; level < B; ++level) {
            limit = 1 << level, rev = REV[level];
            for (int i = 0; i < limit; ++i)
                rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (limit >> 1) : 0);
        }
    }

   private:
    int tmp_a[N], tmp_b[N], tmp_c[N], tmp_d[N];

   protected:
    int limit, level;
    int *rev, REV[B][N];

    void InitLimit(const int need_len) {
        for (limit = 1, level = 0; limit <= need_len; limit <<= 1) ++level;
        rev = REV[level];
        InitLimitExtra();
    }

    virtual void InitLimitExtra() = 0;
    virtual void Transform() = 0;

   public:
    virtual void Mul(const int len_a, const int *a, const int len_b,
                     const int *b, int *c) = 0;

    void Inv(const int len, const int *a, int *b) {
        if (!len) {
            b[0] = inv(a[0]);
            return;
        }
        Inv(len >> 1, a, b);
        Mul(len, b, len, b, tmp_a);
        Mul(len, tmp_a, len, a, tmp_a);

        for (int i = 0; i <= len; ++i)
            b[i] = add(add(b[i], b[i]), MOD - tmp_a[i]);

        for (int i = len + 1; i < limit; ++i) b[i] = 0;
        for (int i = 0; i < limit; ++i) tmp_a[i] = 0;
    }

    void Deriv(const int len, const int *a, int *b) {
        for (int i = 0; i < len; ++i) b[i] = mul(a[i + 1], i + 1);
        b[len] = 0;
    }

    void Integral(const int len, const int *a, int *b) {
        for (int i = len; i > 0; --i) b[i] = mul(a[i - 1], inv(i));
        b[0] = 0;
    }

    void Ln(const int len, const int *a, int *b) {
        Deriv(len, a, b);
        Inv(len, a, tmp_b);
        Mul(len, b, len, tmp_b, tmp_b);
        Integral(len, tmp_b, b);

        for (int i = len + 1; i < limit; ++i) b[i] = 0;
        for (int i = 0; i < limit; ++i) tmp_b[i] = 0;
    }

    void Exp(const int len, const int *a, int *b) {
        if (!len) {
            b[0] = 1;
            return;
        }
        Exp(len >> 1, a, b);
        Ln(len, b, tmp_c);
        for (int i = 0; i <= len; ++i) tmp_c[i] = add(MOD - tmp_c[i], a[i]);
        ++tmp_c[0];
        Mul(len, tmp_c, len, b, b);

        for (int i = len + 1; i < limit; ++i) b[i] = 0;
        for (int i = 0; i < limit; ++i) tmp_c[i] = 0;
    }

    void Sqrt(const int len, const int *a, int *b) {
        static int inv2 = inv(2);
        if (!len) {
            b[0] = 1;
            return;
        }
        Sqrt(len >> 1, a, b);
        Inv(len, b, tmp_b);
        Mul(len, a, len, tmp_b, tmp_b);
        for (int i = 0; i <= len; ++i) b[i] = mul(add(tmp_b[i], b[i]), inv2);

        for (int i = len + 1; i < limit; ++i) b[i] = 0;
        for (int i = 0; i < limit; ++i) tmp_b[i] = 0;
    }

    void Power(const int len, const int *a, const char *s, int *b) {
        int Len = strlen(s);
        int val1 = 0, val2 = 0, val3 = 0;
        for (int i = 0; i < Len; ++i) {
            val1 = (10LL * val1 + s[i] - '0') % MOD;
            val2 = (10LL * val2 + s[i] - '0') % (MOD - 1);
        }
        for (int i = 0; i < min(6, Len); ++i) val3 = 10 * val3 + s[i] - '0';
        if (a[0] == 0 && val3 > len) {
            fill(b, b + len + 1, 0);
            return;
        }

        int u, v, shift = 0;
        for (int i = 0; i <= len && a[i] == 0; ++i) shift++;
        if ((ll)shift * val1 > len) {
            fill(b, b + len + 1, 0);
            return;
        }
        u = qpow(a[shift], MOD - 2);
        v = qpow(a[shift], val2);
        for (int i = 0; i <= len; ++i) b[i] = mul(a[i + shift], u);
        Ln(len, b, tmp_d);
        b[0] = tmp_d[0];
        for (int i = 1; i <= len; ++i) b[i] = mul(tmp_d[i], val1);
        Exp(len, b, tmp_d);
        shift *= val1;
        for (int i = 0; i < shift; ++i) b[i] = 0;
        for (int i = shift; i <= len; ++i) b[i] = mul(tmp_d[i - shift], v);
        for (int i = 0; i < limit; ++i) tmp_d[i] = 0;
        for (int i = len + 1; i < limit; ++i) b[i] = 0;
    }
};

class FFT : public Poly {
   public:
    FFT() {
        const double Pi = acos(-1.0);
        for (level = 1; level < B; ++level) {
            limit = 1 << level, w = W[level];
            for (int mid = 1; mid < limit; mid <<= 1) {
                w[mid] = Node(1, 0);
                for (int i = 1; i < mid; ++i) {
                    if ((i & 31) == 1)
                        w[mid + i] = Node(cos(Pi * i / mid), sin(Pi * i / mid));
                    else
                        w[mid + i] = w[mid + i - 1] * w[mid + 1];
                }
            }
        }
    }

   private:
    Node tmp_a[N], tmp_b[N], tmp_c[N], tmp_d[N];

   protected:
    Node *w, W[B][N];

    void InitLimitExtra() { w = W[level]; }
    void Transform() {}
    void Transform(Node *val, int type) {
        if (type == 1) reverse(val + 1, val + limit);
        for (int i = 0; i < limit; ++i)
            if (i < rev[i]) swap(val[i], val[rev[i]]);
        for (int mid = 1; mid < limit; mid <<= 1) {
            int R = mid << 1;
            for (int i = 0; i < limit; i += R)
                for (int j = 0; j < mid; ++j) {
                    Node v = w[mid + j] * val[i + mid + j];
                    val[i + mid + j] = val[i + j] - v;
                    val[i + j] = val[i + j] + v;
                }
        }
    }

   public:
    void Mul(const int len_a, const int *a, const int len_b, const int *b,
             int *c) {
        InitLimit(len_a + len_b);
        for (int i = 0; i <= len_a; ++i) tmp_a[i].MTTinit(a[i]);
        for (int i = 0; i <= len_b; ++i) tmp_b[i].MTTinit(b[i]);
        Transform(tmp_a, 1), Transform(tmp_b, 1);
        for (int i = 0; i < limit; ++i) {
            Node ft = ~tmp_a[i ? (limit - i) : 0];
            Node f0 = (tmp_a[i] - ft) * Node(0, -0.5);
            Node f1 = (tmp_a[i] + ft) * 0.5;
            Node gt = ~tmp_b[i ? (limit - i) : 0];
            Node g0 = (tmp_b[i] - gt) * Node(0, -0.5);
            Node g1 = (tmp_b[i] + gt) * 0.5;
            tmp_c[i] = f1 * g1,
            tmp_d[i] = f0 * g1 + f1 * g0 + f0 * g0 * Node(0, 1);
        }
        Transform(tmp_c, -1), Transform(tmp_d, -1);
        for (int i = 0; i <= len_a + len_b; ++i) {
            ll v1 = (ll)(tmp_c[i].x / limit + 0.5) % MOD;
            ll v2 = (ll)(tmp_d[i].x / limit + 0.5) % MOD;
            ll v3 = (ll)(tmp_d[i].y / limit + 0.5) % MOD;
            c[i] = ((v1 << 30) + (v2 << 15) + v3) % MOD;
        }

        for (int i = 0; i < limit; ++i)
            tmp_a[i] = tmp_b[i] = tmp_c[i] = tmp_d[i] = Node(0, 0);
    }
};

class NTT : public Poly {
   private:
    int tmp_a[N], tmp_b[N];

   public:
    void Mul(const int len_a, const int *a, const int len_b, const int *b,
             int *c) {
        InitLimit(len_a + len_b);
        for (int i = 0; i <= len_a; ++i) tmp_a[i] = a[i];
        for (int i = 0; i <= len_b; ++i) tmp_b[i] = b[i];
        Transform(tmp_a, 1), Transform(tmp_b, 1);
        for (int i = 0; i < limit; ++i) c[i] = mul(tmp_a[i], tmp_b[i]);
        Transform(c, -1);
        int INV = inv(limit);
        for (int i = 0; i <= len_a + len_b; ++i) c[i] = mul(c[i], INV);
        for (int i = len_a + len_b + 1; i < limit; ++i) c[i] = 0;
        for (int i = 0; i < limit; ++i) tmp_a[i] = tmp_b[i] = 0;
    }

   protected:
    void InitLimitExtra() {}
    void Transform() {}
    void Transform(int *val, int type) {
        for (int i = 0; i < limit; ++i)
            if (i < rev[i]) swap(val[i], val[rev[i]]);
        for (int mid = 1; mid < limit; mid <<= 1) {
            int wn = qpow(type == 1 ? G : IG, (MOD - 1) / (mid << 1));
            for (int j = 0; j < limit; j += (mid << 1)) {
                int w = 1;
                for (int k = 0; k < mid; k++, w = mul(w, wn)) {
                    int x = val[j + k], y = mul(w, val[j + k + mid]);
                    val[j + k] = add(x, y);
                    val[j + k + mid] = dec(x, y);
                }
            }
        }
    }
};