多项式

多项式多项式多项式多像💩多项式多项式多项式

一些定义

单位根

$x^n = 1$ 在复数域内的n个解，我们把这些解称为单位根

$w_{n}^{k}$ 其中 $k \in [0, n-1]$ ，单位根把单位圆n等分

单位根的性质

$w_n^n = 1$

$w_n^{k+n} = w_n^{k}$ 画图理解

$w_n^{k+\frac{n}{2}} = -w_n^k$ 画图理解

$w_{dk}^{dk} = w_n^{k}$ ~~约分？~~

单位根反演

[k \mid n] = \frac{1}{k}\sum\limits_{i = 0}^{k-1} w_k^{ni}

多项式的表示

对于一个多项式 $f(x) = \sum\limits_{i = 0}^n a_ix^i$

我们可以通过系数即 $(a_0,a_1,a_2,..,a_n)$ 表示这个多项式称为 系数表示

还有一种表示，叫做 点值表示

我们知道对于一个 $n$ 次多项式它可以由 $n+1$ 个多项式上的点值确定

就是用这 $n+1$ 个点值来表示这个多项式

FFT

可以快速解决多项式乘法问题

例如 $A(x)*B(x) = C(x)$ 那么 $C(x)$ 的次数就是 $A$ 和 $b$ 加起来

先整点朴素的嗷一项一项乘上去的复杂度为 $O(n^2)$

我们需要进行一些优化

考虑用点值来操作

用点痣表示 $A$ 和 $B$

A(x) = \left\{ (x_0,A(x_0)), (x_1,A(x_0)), (x_2,A(x_2)), ...,(x_n,A(x_n))\right\}\\ B(x) = \left\{ (x_0,B(x_0)), (x_1,B(x_0)), (x_2,B(x_2)), ...,(x_n,B(x_n)) \right\}

那么

C(x) = \left\{ (x_0,A(x_0)*B(x_0)),...,((x_{n+m}),A(x_{n+m})*B(x_{n+m})) \right\}

所以我们现在可以在 $O(n)$ 的时间内计算了

我们还需要把系数表示换位点值表示再把结果的点值表示换位系数表示

第一步 DFT

系数 $\rightarrow$ 点值

把项数按奇偶分开考虑

\begin{align} A(x) &= \sum\limits_{i = 0}^n a_ix^i\nonumber \\ &=(a_0 + a_2x^2 +a_4x^4+\dots+a_{n-2}x^{n-2})\nonumber \\ &+(a_1x+a_3{x^3}+a_5{x^5}+ \dots+a_{n-1}x^{n-1})\nonumber \end{align}

令

\begin{align} A_1(x) &= (a_0 + a_2x +a_4x^2+\dots+a_{n-2}x^{\frac{n}{2}-1})\nonumber\\ A_2(x) &= (a_1x+a_3x+a_5{x^2}+ \dots+a_{n-1}x^{\frac{n}{2}-1})\nonumber \end{align}

那么

A(x) = A_1(x^2) + xA2(x^2)

我们把 $x = w_n^k$ 代入

A(w_n^k) = A_1(w_n^{2k}) + w_n^kA_2(w_n^{2k})

再带个 $x = w_n^{k+\frac{n}{2}}$

\begin{align} A(w_n^{k+\frac{n}{2}}) &= A_1(w_n^{2k+n}) + w_n^{k+\frac{n}{2}}A_2(w_n^{2k+n})\nonumber\\ &=A_1(w_n^{2k}) - w_n^kA_2(w_n^{2k})\nonumber \end{align}

$w_n^n = 1$

$w_n^{k+\frac{n}{2}} = -w_n^k$

我们观察得到的两个狮子，发现只有 $A_2$ 的系数不同

我们可以递归求出 $w_n^k$ 的 $A_1$ 和 $A_2$ 来计算 $A$

第二步 IDFT

点值 $\rightarrow$ 系数

IDFT(Inv_DFT) DFT的逆过程

从定义出发
$C_i = A_j*B_i = \sum\limits_{j=0}^{i-1} a_j *b_{i-j-1}$

令 $q = j, p = i-j-1$

则 $C_i = \sum\limits_{p}\sum\limits_{q} a_p *b_q [p+q == n]$

$=\sum\limits_{p}\sum\limits_{q} a_p *b_q [n\mid p+q-i]$

单位根反演

$= \sum_p\sum_qa_p*b_q \sum\limits_{j=0}\frac{1}{n}w_n^{(p+q-i)j}$

那么

$nC_i =\sum_p\sum_qa_p*b_q \sum\limits_{j=0}w_n^{(p+q-i)j}$

把 $p, q, i$ 分配一下，再把 $j$ 提到前边去

$nC_i = \sum_j w_n^{-ij}(\sum_p w_n^{jp} a_p)(\sum_q w_n^{jq} b_q)$

后面两个 $\sum$ 貌似就是 $A$ 和 $B$ 在 $w_n^j$ 的点值？就是我们 DFT 的结果

于是我们代入 $w_n^j$ 再DFT一遍就能得到 $A^{-1}$

还有更酷炫的 $O(n)$ 方法

观察我们按奇偶拆开时的结果

恰好是原序列下标的二进制反转一下，我们就可以省去按奇偶分类的时间~~但是不会写~~

Code

递归版本儿蒟蒻不会写非递归的捏

cpp

#include<cstdio>
#include<cmath>
#define MAXN 3000005
using namespace std;
struct complex
{
    double x,y;
    complex operator + (complex b) {return complex{x+b.x, y+b.y};}
    complex operator - (complex b) {return complex{x-b.x, y-b.y};}
    complex operator * (complex b) {return complex{x*b.x - y*b.y, x*b.y + y*b.x};}
}A[MAXN],B[MAXN];
int n,m;

const double pi = acos(-1.0);

void FFT(int limit, complex *a, int opt)
{
    if(limit == 1) return;
    complex a1[limit>>1], a2[limit>>1];
    for(int i = 0; i < limit; i += 2)
    {
        a1[i>>1] = a[i];
        a2[i>>1] = a[i+1];
    }
    FFT(limit>>1, a1, opt); FFT(limit>>1, a2, opt);
    complex wn = complex{cos(2.0 * pi/limit), opt*sin(2.0*pi/limit)};
    complex w = complex{1, 0};
    for(int i = 0; i < (limit>>1); i++, w = w*wn)
    {
        a[i] = a1[i] + w*a2[i];
        a[i + (limit>>1)] = a1[i] - w*a2[i];
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 0; i <= n; i++) scanf("%lf", &A[i].x);
    for(int i = 0; i <= m; i++) scanf("%lf", &B[i].x);
    int lmt = 1; while(lmt <= n+m) lmt <<= 1;
    FFT(lmt, A, 1); FFT(lmt, B, 1);
    for(int i = 0; i <= lmt; i++) A[i] = A[i] * B[i];
    FFT(lmt, A, -1);
    for(int i = 0; i <= n+m; i++)
    printf("%d ", (int)(A[i].x/lmt+0.5));
}

NTT

我们看到在 FFT 中，复数和三角函数会损失很大的精度，也有了不能取模的限制，所以也有另一个做法–NTT

原根的性质和单位根很相似

令 $g$ 为模 $p$ 下的原根，我们有 $g^{p-1} \equiv 1 \ (mod\ p)$ ，所以可以把单位根 $w_n^k$ 换成 $g_n^k$

一般的 NTT 模数 998244353 的原根为 3 看到别的模数需要考虑一下原根是几或者写多模数 NTT ，但我不会，所以选择寄掉

NTT

void NtT(ll *A, int opt)
{
    for(int i = 0; i < limit; i++)
    if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid <<= 1)
    {
        ll wn = ksm(opt == 1 ? yp : zp, (p-1)/(mid << 1));
        for(int j = 0; j < limit; j += (mid << 1))
        {
            ll w = 1;
            for(int k = 0; k < mid; k++, w = w*wn%p)
            {
                ll x = A[j + k], y = w * A[j + k + mid]%p;
                A[j + k] = (x + y)%p;
                A[j + k + mid] = (x - y +p)%p;
            }
        }
    }
}

多项式求逆

对于一个多项式 $F$ 如果有

F * G \equiv 1 \ (mod \ x^n)

那么称 $G$ 即 $F^{-1}$ 为 $F$ 的逆元

既然有

F * G \equiv 1 \ (mod \ x^n)

那么同样

\begin{align} F * H &\equiv 1 \ (mod \; x^{\frac{n}{2}}) \nonumber\\ G &\equiv H (mod \; x^{\frac{n}{2}}) \nonumber\\ (G - H) &\equiv 0 (mod \; x^{\frac{n}{2}}) \nonumber\\ (G - H)^2 &\equiv 0 (mod \; x^n) \nonumber\\ G^2 + H^2 - 2GH &\equiv 0 (mod \; x^n) \nonumber\\ F(G^2 + H^2 - 2GH) &\equiv 0 (mod \; x^n) \nonumber\\ G + FH^2 - 2H &\equiv 0 (mod \; x^n) \nonumber\\ G &\equiv 2H - FH^2 (mod \; x^n) \nonumber \end{align}

推出式子递归 🆘 完了

多项式对数函数 (多项式 $\ln$ )

多项式 $F(x)$ 和 $G(x)$ ， $G \equiv \ln F (mod \; x^n)$ ，求 $G$

得 🔪 一下

\begin{align} G &\equiv \ln F \; (mod \; x^n) \nonumber\\ G' &\equiv \ln F' \; (mod \; x^n) \nonumber\\ G &\equiv \ln(F)' F' \; (mod \; x^n) \nonumber\\ G &\equiv \frac{F'}{F} \; (mod \; x^n) \nonumber \end{align}

所以求个导再整一个 $F$ 的逆元得到 $G'$ 再寄回去就行辣

多项式指数函数（多项式 $\exp$

aaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ aaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ aaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ aaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ aaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\