咕咕咕 先开个坑（其实是存模板来了）

一些特别简单的前置东西qwq

复数的计算

复数相加：向量相加，复数相乘。复数相乘：模长相乘，旋转量相加（就是复平面坐标轴逆时针旋转的角度）
（当然也可以直接使用complex类，.real()即取实数部分）

单位根

主n次单位根：\(w_n=e^{2\pi i/n}\)
n个n次单位复数根可以用\(w_n^0,w_n^1,...,w_n^{n-1}\)

性质

• n次单位根的次幂还是n次单位根
• \(w_n^n=1\)，n为偶数时\(w_n^{n/2}=-1\)
• \(\sum_{i=0}^{n-1}w_n^i=0\)（证明方式：等比数列求和）
• 全部单位根将复平面上单位圆n等分
• \(w_{2n}^{2k}=w_n^k\)
• \(w_n^{k+\frac{n}{2}}=-w_n^k\)

原根

阶的定义：

设a，p是整数，a和p互素，那么：
使\(a^n\equiv1\pmod p\)成立的最小正整数n叫做a模p的阶。

原根的定义：

原根，是一个数学符号。设m是正整数，a是整数，若a模m的阶等于\(\phi\)(m)，则称a为模m的一个原根。

原根的性质：

• 对于正整数x，只有\(x=2,4,p^a,2\times p^a\)，p为奇素数，a>=1的时候才存在原根。
• \(a^1,a^2,a^3,...,a^{\phi(m)}\)在模p的时候都不相同（可以推得它构成了一个长度为\(\phi(m)\)的循环节）
• 对于m的原根g，满足gi(mod p)（0<=i<=p-2）与1到p-1一一对应.
• 若m有原根，那么它的原根个数为\(\phi(\phi(m))\)。（具体证明蒟蒻不是特别会qwq，上课没听懂）

对于m的情况最为常用。在这种情况下,0~m-1中每一个数都可以对应一个\(a^x\)，这就相当于模意义下取对数（离散对数）。我们可以化乘为加。或者快速地计算一个数的若干次幂。

判断一个数a是不是m的原根

即判断是否不存在\(1<=x<\phi(m)\)。由于\(a^{\phi(m)}\equiv \pmod m\)，我们只需要判断x为\(\phi(m)\)的因数的情况就可以了，时间复杂度\(O(sqrt(m)log m)\)
实际上，对于\(\phi(m)\)的每种质因数p_i判断\(\frac{\phi(m)}{p_i}\)也是等价的。
求出原根后，用暴力或者BSGS就可以求出来一个数的对数。
ps.一个数的原根是很多的，我们可以从小到大判断，或者随机化选取数字判断。

完全是背模板的FFT

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define MAXN 2700010
using namespace std;
int n,m,cnt;
int r[MAXN];
const double PI=acos(-1.0);
struct complex
{
    double x,y;
    complex(double xx=0,double yy=0){x=xx,y=yy;}
}a[MAXN],b[MAXN];
complex operator +(complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex operator -(complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex operator *(complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
inline void fft(complex *p,int opt)
{
    for(int i=0;i<n;i++) if(i<r[i]) swap(p[i],p[r[i]]);
    for(int i=1;i<n;i<<=1)
    {
        complex W=complex(cos(PI/i),opt*sin(PI/i));
        for(int r=i<<1,j=0;j<n;j+=r)
        {
            complex w(1,0);
            for(int k=0;k<i;k++,w=w*W)
            {
                complex X=p[j+k],Y=w*p[j+i+k];
                p[j+k]=X+Y;
                p[j+i+k]=X-Y;
            }
        }
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++) scanf("%lf",&a[i]);
    for(int i=0;i<=m;i++) scanf("%lf",&b[i]);
    m+=n;
    for(n=1;n<=m;n<<=1) ++cnt;
    for(int i=0;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(cnt-1));
    fft(a,1);
    fft(b,1);
    for(int i=0;i<=n;i++) a[i]=a[i]*b[i];
    fft(a,-1);
    for(int i=0;i<=m;i++) printf("%d ",(int)(a[i].x/n+0.5));
    return 0;
}

现在还不会的NTT

所以说分治FFT是个什么东西

多项式求逆

多项式开根

多项式除法

多项式对数

多项式指数

多项式快速幂

OI多项式 简单学习笔记

原文：https://www.cnblogs.com/fengxunling/p/10830955.html