肯定学不会的多项式基础操作

~~终于颓废了一天把多项式写的好看了~~

本文主要是一个模板库，对多项式进行了封装

基础约定

在本文中，多项式的相关运算里面，只说次数不说项数，次数表述较灵活，但如果涉及多项式取模，通常以 \(ti\) 表示一个多项式的次数，\(n\) 表示这个多项式的是在模 \(x^n\) 有意义，其中除多项式加减乘转置以外，其他或多或少都有多项式取模存在，其中包括多项式求导和多项式积分在本文中，代码里面的多项式为大写，推导过程的多项式通常为小写，参数的多项式以 A 和 B 为主，其他以 F 和 G 为主

在本文中，的多项式离散变换为 NTT，NTT 模数为 998244353 原根为 3

在本文中，所有多项式运算需要用到的自然数逆元已被预处理在 inv 数组里

在本文中，对于加减乘模运算以外的其他运算，会先给出数学证明

在本文中，多项式的次数包含零系数

Poly 类与加减运算

struct Poly
{
    vector<int> _;
    inline int& operator [] (int i) { return _[i]; } 
    inline int ti() { return _.size()-1; }
    inline void set(int ti) { return _.resize(ti+1); }
    inline void rev() { return reverse(_.begin(), _.end()); }
};
Poly operator - (Poly A, Poly B)
{
    A.set(max(A.ti(), B.ti()));
    for(int i = B.ti(); ~i; --i) A[i] = A[i]-B[i]<0?A[i]-B[i]+P:A[i]-B[i];
    return A;
}
Poly operator + (Poly A, Poly B)
{
    A.set(max(A.ti(), B.ti()));
    for(int i = B.ti(); ~i; --i) A[i] = A[i]+B[i]<P?A[i]+B[i]:A[i]+B[i]-P;
    return A;
}

假设已声明 Poly 类变量 F 和 G

F[i]：返回 F._[i] 的值，并且支持直接对 F._[i] 的修改，需要注意保证你访问的下标不超过当前 F 的次数

F.ti()：返回 F 的次数

F.set(ti)：重新设置 F 的次数，若 ti 小于当前次数则多余部分舍弃，大于则不足部分补 0

F.rev()：将 F 转置，即 F[i] 变为 F[n-i]

F+G：返回 F 与 G 的和，新的多项式的次数为两者中的较大值

F-G：返回 F 与 G 的差，新的多项式的次数为两者中的较大值

多项式离散变化

int64 w[2][N<<2], inv[N<<2];
int lim;
void prepare(int ti)
{
    for(lim = 1; lim <= ti; lim <<= 1);
    w[0][0] = w[0][lim] = w[1][0] = w[1][lim] = 1;
    int64 g = qpow(3, (P-1)/lim);
    for(int i = 1; i < lim; ++i)
        w[1][lim-i] = w[0][i] = w[0][i-1]*g%P; 
}
void NTT(Poly &A, int t)
{
    if(!t) A.set(lim-1);
    for(int i = 0, j = 0; i < lim; ++i)
    {
        if(i > j) A[i] ^= A[j] ^= A[i] ^= A[j];
        for(int k = lim>>1; (j ^= k) < k; k >>= 1);
    }
    for(int mid = 1; mid < lim; mid <<= 1)
        for(int len = mid<<1, j = 0; j < lim; j += len)
            for(int k = 0, p = 0, q = lim/len; k < mid; ++k, p += q)
            {
                int64 x = A[j+k], y = A[j+k+mid]*w[t][p]%P;
                A[j+k] = x+y<P?x+y:x+y-P;
                A[j+k+mid] = x-y<0?x-y+P:x-y;
            }
    if(!t) return; int64 v = inv[lim];
    for(int i = 0; i < lim; ++i) A[i] = A[i]*v%P;
}

prepare(ti)：对即将变换的 ti 次多项式项数扩展为后继 2 的整数次幂 lim ，并且对即将使用的单位根进行预处理，其中 w[0][i] 访问到的是 \(3^{\frac{P-1}{lim}i}\)，而 w[1][i] 访问到的是其逆元，两者关系可以由欧拉定理得出互为转置

假设已声明 Poly 类变量 F

NTT(F, t)：当 t 为 0 时，进行 NTT，这时需要一开始将 F 的次数设置为 lim-1；当 t 为 1 时，进行 INTT；此外在交换下标阶段省略 rev 数组，改用异或模拟加法，均摊 O(n)， NTT 的过程中通过累加循环变量 p，代替 lim/len*k 意外优化了很大的常数

多项式乘运算

Poly operator * (Poly A, Poly B)
{
    int n = A.ti(), m = B.ti();
    if(n <= 128||m <= 128)
    {
        Poly C; C.set(n+m);
        int *c = &C[0], *a = &A[0], *b = &B[0];
        for(int i = 0; i <= n; ++i)
        {
            int *f = c+i; int64 x = a[i];
            for(int j = 0; j <= m; ++j)
                f[j] = (f[j]+x*b[j]%P)%P;
        }
        return C;
    }
    prepare(n+m), NTT(A, 0), NTT(B, 0);
    for(int i = 0; i < lim; ++i) A[i] = 1ll*A[i]*B[i]%P;
    NTT(A, 1), A.set(n+m);
    return A;
}

假设已声明 Poly 类变量 F 和 G

F*G：返回 F 与 G 的积，新的多项式的次数为两者次数之和，其中 F 与 G 次数较小是采取朴素做法优化常数

多项式求逆

给定多项式 \(f\) 我们要求出 \(g\) 满足 \[ f\times g\equiv 1\ mod\ x^n \]

考虑倍增，假设我们已求出 \[ f\times g_{i-1}\equiv 1\ mod\ x^{\lceil\frac{n}{2}\rceil} \] 现在要求出 \[ f\times g_i\equiv 1\ mod\ x^n \] 显然 \[ f\times g_i\equiv 1\ mod\ x^{\lceil\frac{n}{2}\rceil} \] 所以 \[ g_i-g_{i-1}\equiv 0\ mod\ x^{\lceil\frac{n}{2}\rceil} \] \[ (g_i-g_{i-1})^2\equiv 0\ mod\ x^n \] \[ f(g_i^2-2g_ig_{i-1}+g_{i-1}^2)\equiv 0\ mod\ x^n \] 得到 \[ g_i\equiv 2g_{i-1}-fg_{i-1}^2\ mod\ x^n \] 倍增求解即可

Poly polyInv(Poly A, int n)
{
    Poly B; A.set(n-1), B.set(n-1);
    if(n == 1) return B[0] = qpow(A[0], P-2), B;
    B = polyInv(A, (n+1)>>1), prepare(n<<1);
    NTT(A, 0), NTT(B, 0);
    for(int i = 0; i < lim; ++i) B[i] = (2ll-1ll*B[i]*A[i]%P+P)%P*B[i]%P;
    NTT(B, 1), B.set(n-1);
    return B;
}

假设已声明 Poly 类变量 F

polyInv(F, n)：返回 F 在模意义下的逆元，需注意，每次 A 在运算时同样也需要先取模

多项式带余除法

给定 \(n\) 次多项式 \(f\) 和 \(m\) 次多项式 \(g\) 求出 \(n-m\) 多项式 \(q\) 和 \(m-1\) 次多项式 \(r\)，满足

\[ f\ =\ q\times g+r \]

将式子代换成

\[ x^nf(\frac{1}{x})\ =\ x^{n-m}q(\frac{1}{x})\times x^{m}g(\frac{1}{x})+x^{n-m+1}x^{m-1}r(\frac{1}{x}) \]

考虑 \(f\) 的转置多项式 \(f_r\) 满足 \([x^i]\ f_r\ =\ [x^{n-i}]\ f\) 的另外一种表述为 \(f_r\ =\ x^n\ f(\frac{1}{x})\)

\[ f_r\ =\ q_r\times g_r+x^{n-m+1}r_r \]

发现在模 \(x^{n-m+1}\) 的意义下余项的转置被消去，则有

\[ f_r\ =\ q_r\times g_r\ mod\ x^{n-m+1} \]

所以

\[ q_r\ =\ f_r\times g_r^{-1}\ mod\ x^{n-m+1} \]

求出 \(q\) 之后 \(r\) 就很容易求出

Poly operator / (Poly A, Poly B)
{
    if(A.ti() < B.ti()) return A.set(0), A;
    int n = A.ti(), m = B.ti(); 
    A.rev(), B.rev();
    A = A*polyInv(B, n-m+1), A.set(n-m), A.rev();
    return A;
}
Poly operator % (Poly A, Poly B)
{
    if(A.ti() < B.ti()) return A;
    A = A-(A/B)*B; A.set(B.ti()-1);
    return A;
}

F/G：返回 F 与 G 的商，新的多项式的次数为两者中的较大值

F-G：返回 F 与 G 的yu，新的多项式的次数为两者中的较大值

多项式求导和积分

给定多项式 \(f\) 我们要求出 \(g\) 和 \(h\) 满足 \[ g\equiv f'\ mod\ x^n \] \[ h\equiv \int f dx\ mod\ x^n \]

由幂函数求导法则 \(x^n\to nx^{n-1}\) 和求导四则运算得

\[ [x^n]\ g\ =\ [x^{n+1}]\ f\times n \]

由微分和积分互为逆运算得到

\[ [x^n]\ h\ =\ [x^{n-1}]\ f\times \frac{1}{n} \]

Poly polyDer(Poly A, int n)
{
    A.set(n-1);
    for(int i = 0; i < n-1; ++i) A[i] = 1ll*(i+1)*A[i+1]%P; A[n-1] = 0;
    return A;
}
Poly polyInte(Poly A, int n)
{
    A.set(n-1);
    for(int i = n-1; i; --i) A[i] = inv[i]*A[i-1]%P; A[0] = 0;
    return A;
}

假设已声明 Poly 类变量 F

polyDer(F, n)：返回 F 在模意义下的导数，其次数由模数决定，特别地，只需要正常求导时，n 应该为 F.ti()+1，返回的仍是 F.ti() 次多项式

polyInte(F, n)：返回 F 在模意义下的积分，其次数由模数决定，特别地，只需要正常积分时，n 应该为 F.ti()+2，返回的是 F.ti()+1 次多项式

多项式对数函数

给定多项式 \(f\) 我们要求出 \(g\) 满足 \[ g\equiv ln\ f\ mod\ x^n \]

两边同时求导再积回来就好了

\[ g\equiv \int\frac{f'}{f}dx\ mod\ x^n \]

1	Poly polyLn(Poly A, int n) { return polyInte(polyDer(A, n)*polyInv(A, n), n); }

假设已声明 Poly 类变量 F

polyLn(F, n)：返回 F 在模意义下的自然对数，其次数由模数决定

多项式指数函数 (牛顿迭代)

给定多项式 \(f\) 我们要求出 \(g\) 满足 \[ g\equiv e^f\ mod\ x^n \]

首先，我们把牛顿迭代推广到多项式中，考虑

给定多项式 \(f\) 我们要求出 \(g\) 满足 \[ f(g)\equiv 0\ mod\ x^n \]

那么就有

\[ g_i\equiv g_{i-1}-\frac{f(g_{i-1})}{f'(g_{i-1})}\ mod\ x^n \]

倍增迭代即可

另外，注意求导是 \(g\) 关于 \(f\) 求导，而不是 \(x\) 关于 \(f\) 求导

在这指数函数中两边取对数移项得

\[ ln\ g - f\equiv 0\ mod\ x^n \]

不妨把左侧看作关于 \(g\) 得函数，那么我们实际上就是求出该多项式得零点，带入牛顿迭代式得

\[ g_i\equiv g_{i-1}(1-ln\ g_{i-1}+f)\ mod\ x^n \]

Poly polyExp(Poly A, int n)
{
    Poly B; B.set(n-1), A.set(n-1);
    if(n == 1) return B[0] = 1, B;
    B = polyExp(A, (n+1)>>1), B.set(n-1), ++A[0];
    B = B*(A-polyLn(B, n)); B.set(n-1); 
    return B;
}

假设已声明 Poly 类变量 F

polyLn(F, n)：返回 F 在模意义下的 Exp ，其次数由模数决定

基础约定

Poly 类 与 加减运算

多项式离散变化

多项式乘运算

多项式求逆

多项式带余除法

多项式求导和积分

多项式对数函数

多项式指数函数 (牛顿迭代)

Poly 类与加减运算