多项式的各类计算(多项式的逆/开根/对数/exp/带余除法/多点求值)

预备知识：FFT/NTT

多项式的逆

给定一个多项式 ，请求出一个多项式 ，满足 。
系数对 取模，

首先将多项式的长度拓展至的次幂，然后我们要求的是
假设已经求出了
又因为有
两式相减有
因为左边得到的多项式前项都是，平方前项都是，所以有
两边同时乘以

我们就得到了递推式，时间复杂度如下

多项式开根

给定一个 次多项式 ，求一个在 意义下的多项式 ，使得 （多项式的系数在 的意义下进行运算，）
同样假设求出了且有
所以

所以
此处除法转化为乘上多项式的逆，就能递推了，时间复杂度也是

多项式求自然对数

给出 次多项式 ，求一个 下的多项式 ，满足 .
多项式的系数在 的意义下进行运算，
所以，直接多项式求逆+多项式求导积分就行了
求逆复杂度，求导积分复杂度，总时间复杂度仍是

多项式exp

多项式exp是用牛顿迭代做的,我也不会证明牛顿迭代,只会背公式.
本来牛顿迭代公式是这个样子的
对于多项式的牛顿迭代长这样

• 其中表示已知多项式为,未知多项式为的多项式方程,就拿exp为例,原方程为两边取对数为那么.
• 表示的是对取导.注意是对,不是对多项式里的.
  举个栗子,对求导是,但是对求导是(此处是对求导)

那么我们就可以推推柿子然后就套用前面的模板迭代做了

其实多项式开根也可以用这个方法推出来,有兴趣可以去试试看.

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
namespace READ {
    inline void read(int &num) {
        char ch; int flg=1;
        while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;
        for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
        num*=flg;
    }
}
using namespace READ;
const int mod = 998244353, G = 3, inv2 = 499122177;
const int MAXN = 1<<18; // 注意MAXN要大于2*n
int rev[MAXN], Wn[MAXN+1][2], inv[MAXN+1];
inline void reset(int len) { for(int i = 0; i < len; ++i) rev[i] = (rev[i>>1]>>1)|((i&1)?(len>>1):0); }
inline int qmul(int a, int b) {
    int res = 1;
    while(b) {
        if(b&1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod; b>>=1;
    }
    return res;
}
inline int add(int x, int y) { return x+y>mod ? x+y-mod : x+y; }
namespace Poly { 
    int A[MAXN],B[MAXN],C[MAXN],D[MAXN],E[MAXN],F[MAXN],GG[MAXN],H[MAXN];//每个不同函数开不同的临时数组,否则可能重复使用
    inline void clear(int *b, int n) { for(int i = 0; i < n; ++i) b[i] = 0; } //多清零
    inline void NTT(int *arr, int n, int flg) {
        int wn, w, A0, wA1, i, j, k;
        for(i = 0; i < n; ++i) if(i < rev[i]) swap(arr[i], arr[rev[i]]);
        for(i = 2; i <= n; i<<=1) {
            wn = Wn[i][(~flg)?0:1];
            for(j = 0, w = 1; j < n; j += i, w = 1)
                for(k = j; k < j + i/2; ++k, w = 1ll * w * wn % mod) {
                    A0 = arr[k], wA1 = 1ll * w * arr[k + i/2] % mod;
                    arr[k] = add(A0, wA1);
                    arr[k + i/2] = add(A0, -wA1+mod);
                }
        }
        if(!(~flg)) for(i = 0; i < n; ++i) arr[i] = 1ll * arr[i] * inv[n] % mod;
    }
    
    inline void INV(int *a, int *b, int n) {
        clear(b, n<<1), b[0] = qmul(a[0], mod-2);
        clear(A, n<<1), clear(B, n<<1);
        int len, lim;
        for(len = 2; len < (n<<1); len<<=1) {
            lim = len<<1;
            for(int i = 0; i < len; ++i) A[i] = a[i], B[i] = b[i];
            reset(lim); NTT(A, lim, 1); NTT(B, lim, 1);
            for(int i = 0; i < lim; ++i) b[i] = ((2ll - 1ll * A[i] * B[i] % mod) * B[i] % mod + mod) % mod;
            NTT(b, lim, -1);
            for(int i = len; i < lim; ++i) b[i] = 0;
            }
        for(int i = 0; i < len; ++i) A[i] = B[i] = 0;
        for(int i = n; i < len; ++i) b[i] = 0;
    }
    
    inline void SQRT(int *a, int *b, int n) {
        clear(b, n<<1); b[0] = int(sqrt(a[0])+0.5);
        int len, lim, *A = GG, *B = H;
        clear(A, n<<1), clear(B, n<<1);
        for(len = 2; len < (n<<1); len<<=1) {
            lim = len<<1;
            for(int i = 0; i < len; ++i) A[i] = a[i];
            INV(b, B, len);
            reset(lim); NTT(A, lim, 1); NTT(B, lim, 1);
            for(int i = 0; i < lim; ++i) A[i] = 1ll * A[i] * B[i] % mod;
            NTT(A, lim, -1);
            for(int i = 0; i < len; ++i) b[i] = 1ll * (b[i] + A[i]) % mod * inv2 % mod;
            for(int i = len; i < lim; ++i) b[i] = 0;
        }
        for(int i = 0; i < len; ++i) A[i] = B[i] = 0;
        for(int i = n; i < len; ++i) b[i] = 0;
    }

    inline void INT(int *a, int *b, int n) {
        clear(b, n<<1);
        for(int i = n-1; i; --i)
            b[i] = 1ll * a[i-1] * qmul(i, mod-2) % mod;
        b[0] = 0;
    }
    
    inline void DIF(int *a, int *b, int n) {
        clear(b, n<<1);
        for(int i = 1; i < n; ++i)
            b[i-1] = 1ll * a[i] * i % mod;
        b[n-1] = 0;
    }
    
    inline void LN(int *a, int *b, int n) {
        int *A = E, *B = F, len = 1;
        clear(A, n<<1), clear(B, n<<1);
        INV(a, A, n); DIF(a, B, n);
        while(len < (n<<1)) len<<=1;
        reset(len); NTT(A, len, 1); NTT(B, len, 1);
        for(int i = 0; i < len; ++i) A[i] = 1ll * A[i] * B[i] % mod;
        NTT(A, len, -1); INT(A, b, n);
    }
    
    inline void EXP(int *a, int *b, int n) {
        clear(b, n<<1), b[0] = 1;
        int len, lim, *A = C, *B = D;
        clear(A, n<<1), clear(B, n<<1);
        for(len = 2; len < (n<<1); len<<=1) {
            lim = len<<1;
            LN(b, A, len);
            for(int i = 0; i < len; ++i) A[i] = ((i==0)-A[i]+a[i]+mod) % mod, B[i] = b[i];
            for(int i = len; i < lim; ++i) A[i] = B[i] = 0;
            reset(lim); NTT(A, lim, 1); NTT(B, lim, 1);
            for(int i = 0; i < lim; ++i) A[i] = 1ll * A[i] * B[i] % mod;
            NTT(A, lim, -1);
            for(int i = 0; i < len; ++i) b[i] = A[i];
        }
        for(int i = n; i < len; ++i) b[i] = 0;
    }
}
using namespace Poly;
inline void Pre() { //预处理原根及逆元
    for(int i = 1; i <= MAXN; i<<=1)
        Wn[i][0] = qmul(G, (mod-1)/i),
        Wn[i][1] = qmul(G, (mod-1)-(mod-1)/i),
        inv[i] = qmul(i, mod-2);
}
int main () {
    Pre();
}

现在看,发现我以前sb了…不用开不同的数组来取地址,直接static定义就行了…

带余除法（待更…）

多项式多点求值（待更…）