[基本操作]多项式

首先 FFT

没啥可说的，背诵全文

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 4000100,mod = 998244353,iG = 332748118,G = 3;
int n,L,R[maxn],lg[maxn + maxn];
int poly[maxn],Poly[maxn];
int nn;
inline int read()
{
    int x = 0,f = 1;char ch = getchar();
    for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f;
    for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0';
    return x * f;
}
inline int ksm(int x,int t)
{
    int res = 1;
    while(t)
    {
        if(t & 1) res = ((LL)res * (LL)x) % mod;
        x = ((LL)x * (LL)x) % mod;
        t >>= 1;
    }
    return res;
}
inline void fft_init(int n){for(int i=0;i<n;i++) R[i] = (R[i>>1] >> 1) | ((i & 1) << (lg[n] - 1));}
inline void fft(int *a,int f,int n)
{
    for(int i=0;i<n;i++)if(i < R[i])swap(a[i],a[R[i]]);
    for(int i=1;i<n;i<<=1)
    {
        int wn = ksm(((f == 1) ? G : iG),(mod - 1) / (i << 1));
        for(int j=0;j<n;j+=(i<<1))
        {
            int w = 1;
            for(int k=0;k<i;k++,w=(1LL * (LL)w * (LL)wn) % mod)
            {
                int x = a[j + k], y = (1LL * (LL)w * (LL)a[j + k + i]) % mod;
                a[j + k] = (x + y) % mod;
                a[j + k + i] = (x - y + mod) % mod;
            }
        }
    }
    if(f == -1)
    {
        int inv = ksm(n,mod - 2);
        for(int i=0;i<n;i++)a[i] = ((LL)a[i] * (LL)inv) % mod;
    }
}
int main()
{
    n = read();nn = read();lg[0] = -1;
    for(int i=1;i<maxn+maxn;i++)lg[i] = lg[i >> 1] + 1;
    for(int i=0;i<=n;i++)poly[i] = read();
    for(int i=0;i<=nn;i++)Poly[i] = read();
    int m;
    for(m=n+nn,n=1;n<=m;n<<=1);
    fft_init(n);
    fft(poly,1,n);fft(Poly,1,n);
    for(int i=0;i<n;i++)poly[i] = ((LL)poly[i] * (LL)Poly[i]) % mod;
    fft(poly,-1,n);
    for(int i=0;i<=m;i++)printf("%d ",poly[i]);
}
NTT
#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline int read()
{
    int x = 0,f = 1;char ch = getchar();
    for(;!isdigit(ch);ch = getchar())if(ch == '-') f = -f;
    for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0';
    return x * f;
}
const int maxn = 4e6 + 10;
const double pi = acos(-1);
#define cp complex<double>
cp a[maxn],b[maxn];
int lg[maxn + maxn],R[maxn];
inline void fft_init(int n){for(int i=0;i<n;i++)R[i] = (R[i >> 1] >> 1) | ((i & 1) << (lg[n] - 1));}
inline void fft(cp *a,int f,int n)
{
    for(int i=0;i<n;i++)if(i < R[i])swap(a[i],a[R[i]]);
    for(int i=1;i<n;i <<= 1)
    {
        cp wn(cos(pi / i),f * sin(pi / i));
        for(int j=0;j<n;j += (i << 1))
        {
            cp w(1,0);
            for(int k=0;k<i;k++,w *= wn)
            {
                cp x = a[j + k],y = w * a[j + k + i];
                a[j + k] = x + y;
                a[j + k + i] = x - y;
            }
        }
    }
    if(f == -1)for(int i=0;i<=n;i++)a[i] /= n;
}
int main()
{
    lg[0] = -1;for(int i=1;i<maxn+maxn;i++)lg[i] = lg[i >> 1] + 1;
    int N = read(),M = read();
    for(int i=0;i<=N;i++)cin>>a[i];
    for(int i=0;i<=M;i++)cin>>b[i];
    int n;
    for(n=1;n <= N+M;n<<=1);
    fft_init(n);fft(a,1,n);fft(b,1,n);
    for(int i=0;i<=n;i++)a[i] *= b[i];
    fft(a,-1,n);
    for(int i=0;i<=N+M;i++)printf("%d ",(int)(a[i].real() + 0.5));
}
FFT

多项式的一个基本操作就是卷积，也就是对于两个多项式 $F$ 和 $G$ ，求

$$sum_{i=1}^n F_i imes G_{n-i}$$

很多 dp 题可以转换成卷积的形式，我们可以 FFT 一发

对于一些计数问题，生成函数是一个非常有用的计数方法，FFT 也可以快速计算两个母函数的卷积

之后就是一些很好的操作，先放在这

1.求逆

对于一个多项式 $A$ ，你要求一个多项式 $B$ 满足 $A imes B equiv 1 space (mod space x^n)$

考虑倍增

1.如果要求 $A$ 在膜 $x^0$ 意义下的逆，那就相当于求常数项的逆元

2.如果我们知道在膜 $x^{lceil frac{n}{2} ceil}$ 意义下的逆 $B'$ ，我们要求膜 $x^n$ 意义下的逆 $B$

稍微有点麻烦，考虑一下

先把 $A imes B$ 放到膜 $x^{lceil frac{n}{2} ceil}$ 意义下，得到 $A imes B equiv 1 space (mod space x^{lceil frac{n}{2} ceil})$

减一下 $B - B' equiv 0  space (mod space x^{lceil frac{n}{2} ceil})$

两边平方 $B^2 - 2 imes B imes B' + B'^2 equiv 0  space (mod space x^n)$

乘上一个 $A$ ，移项可以得到 $B equiv 2 imes B'- A imes B'^2 space (mod space x^n)$

这样做的时间复杂度是 $T(n) = T(frac{n}{2}) + O(nlogn)$

主定理搞一波是 $O(nlogn)$ 的

只有一个 log ，非常优秀

int temp[maxn];
inline void inverse(int *a,int *b,int n)
{
    if(n == 1){b[0] = ksm(a[0],mod - 2);return;}
    inverse(a,b,n >> 1);
    memcpy(temp,a,n * sizeof(int));
    memset(temp + n,0,n * sizeof(int));
    fft(temp,1,n << 1);fft(b,1,n << 1);
    for(int i=0;i<(n << 1);i++)b[i] = 1LL * b[i] * ((2LL - 1LL * temp[i] * b[i] % mod + mod) % mod) % mod;
    fft(b,-1,n << 1);memset(b + n,0,n * sizeof(int));
}
求逆

2.求导 / 积分

下面一些东西的前置操作

void Derivative(int *f,int *g,int n)
{
    for(int i=0;i<n;i++)g[i] = (LL)f[i + 1] * (i + 1) % mod;
    g[n] = 0;
}
void Integral(int *f,int *g,int n)
{
    for(int i=1;i<=n;i++)g[i] = (LL)f[i - 1] * ksm(i,mod - 2) % mod;
    g[0] = 0;
}
求导 / 积分

3.多项式开根

还是倍增

对于一个多项式 $A$ ，假设我们要求 $B^2 equiv A space (mod space x^n)$

跳个步，$B^2 - B'^2 equiv 0 space (mod space x^{lceil frac{n}{2} ceil})$

平方差公式，$(B - B')(B + B') equiv 0 space (mod space x^{lceil frac{n}{2} ceil})$

有 2 个解，我们考虑前面那个，也就是 $B - B' equiv 0 space (mod space x^{lceil frac{n}{2} ceil})$

平方一下 $B^2 - 2 imes B imes B' + B'^2 equiv 0 space (mod space x^n)$

把 $A$ 代进去 $A - 2 imes B imes B' + B'^2 equiv 0 space (mod space x^n)$

移项，得到 $B equiv frac{A + B'^2}{2 imes B'} space (mod space x^n)$

求逆就可以了

复杂度还是 $O(nlogn)$

inline void sqrt(int *a,int *b,int n)
{
    if(n == 1){b[0] = 1;return;}
    sqrt(a,b,n>>1);
    memset(d,0,n*2*sizeof(int));
    inverse(b,d,n);
    memcpy(c,a,n*sizeof(int));
    memset(c+n,0,n*sizeof(int));
    fft(c,1,n<<1);
    fft(b,1,n<<1);
    fft(d,1,n<<1);
    for(int i=0;i<(n<<1);i++) b[i] = (1LL * c[i] * d[i] % mod + b[i]) % mod * inv2 % mod;
    fft(b,-1,n<<1);
    memset(b+n,0,n*sizeof(int));
}
开根

4.求 ln

$$ln(A) equiv int frac{A'}{A} dx$$

用求导和积分搞一搞就可以了

int D[maxn],A[maxn];
inline void ln(int *f,int *g,int n)
{
    Derivitive(f,g,n);
    inverse(f,A,n);fft_init(n);
    fft(A,n,0);fft(D,n,0);
    for(int i=0;i<n;i++)(A[i] *= D[i]) %= mod;
    fft(A,n,1);
    Integral(f,g,n);
}
ln
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Kong-Ruo/p/10101761.html