多项式学习笔记

\rm FFT

首先我们要求的柿子长这样：

c(k) = \sum_{i+j = k}a(i)\times b(j)

大概思路：先把两个多项式转成点值(DFT)，再把两个多项式的点值乘在一起，把新的点值转成多项式(IDFT)即可

\rm DFT:

首先要了解复数的运算

(a + b\times i) +(c+d\times i) = (a+c)+(b+d)\times i (a + b\times i) -(c+d\times i) = (a-c)+(b-d)\times i (a + b\times i) \times (c+d\times i) = (a\times c - b\times d)+(a\times d+b\times d)\times i

随便说下单位圆/单位根： 现在我们要把圆平分成n个，每一个的大小应该是cos(2 Π /n), sin(2Π / n)

步入正题，具体操作长这样：

F(x) = a_0\times x^0+a_1\times x^1+a_2\times x^2+……+a_n\times x^n

设F1(x) = a_0\times x^0+a_2\times x^1+……+a_{n}\times x^{\frac{n}{2}}，F2(x) = a_1\times x^0+a_3\times x^1+……+a_{n - 1}\times x^{\frac{n}{2}}

F(x) = F1(x^2)+x\times F2(x^2)

现在我们只需要知道F1(x), F2(x)就可以知道F(x)了，于是我们可以递归处理（所以我们需要保证多项式的项数为2^x）

把单位根带到上述式子里面去，我们有：

F(w_n^x) = F1(w_n^{2\times x})+w_n^x\times F2(w_n^{2\times x})

现在我们需要单位根的第一条性质（带到单位圆上就知道了）：

w_{2n}^{2x} = w_{n}^x

顺便介绍性质二（还是画画图就知道了）：

w_{n}^{x+\frac{n}{2}} = -w_{n}^x

通过性质一，我们可以把柿子化成：

F(w_n^x) = F1(w_{\frac{n}{2}}^{x})+w_n^x\times F2(w_{\frac{n}{2}}^{x})

由于我们只知道F1(x), F2(x)的0-\frac{n}{2}的所有点值要求出F(x)的0-n的所有点值

分类讨论一下：

如果x<\frac{n}{2}，直接用F1,F2的值就行

如果x≥\frac{n}{2}，不妨设x=x+\frac{n}{2}

F(w_n^{x+\frac{n}{2}}) = F1((w_{n}^{x+\frac{n}{2}})^2)+w_n^{x+\frac{n}{2}}\times F2((w_{n}^{{x+\frac{n}{2}}})^2)

由于第二条性质

F(w_n^{x+\frac{n}{2}}) = F1((-w_{n}^x)^2)-w_n^{x}\times F2((-w_{n}^{x})^2) F(w_n^x) = F1(w_{\frac{n}{2}}^{x})-w_n^x\times F2(w_{\frac{n}{2}}^{x})

发现只有一个符号的区别

\rm IDFT

我们假设我们通过DFT求出了点值为a_0, a_1……, a_n，最后我们要求出的值为A_0, A_1……, A_n

其实我们只要解一个这样的方程组：

A_0\times (w_n^0)^0+A_1\times (w_n^0)^1+A_2\times (w_n^0)^2+……+A_n\times (w_n^0)^{n} A_0\times (w_n^1)^0+A_1\times (w_n^1)^1+A_2\times (w_n^1)^2+……+A_n\times (w_n^1)^{n} …… A_0\times (w_n^{n - 1})^0+A_1\times (w_n^{n - 1})^1+A_2\times (w_n^{n - 1})^2+……+A_n\times (w_n^{n - 1})^{n}

这就是一个矩阵形式了

第一个矩阵是所有的(w_n^x)^k，我们计为矩阵V，第二个矩阵为所有的A_x计为A，第三个矩阵为所有的a_x计为a

于是我们的柿子变成了A\times V=a

如果我们知道V^{-1}，那么我们有a\times V^{-1} = A，a即为所求

现在考虑求逆：

我们需要介绍性质三：\sum_{j = 0}^{n - 1}(w_n^k)^j=[k==0]\times n

证明其实不难，画画图就好了，我们要求的柿子为：\sum_{j = 0}^{n - 1}(w_n^k)^j

如果k =0，那么原式=\sum_{j = 0}^{n - 1} = n

如果k≠0，记s=\sum_{j =0}^{n - 1}(w_n^k)^j

s\times w_n^k = \sum_{j=1}^{n}(w_n^k)^j =s-1+(w_n^k)^n = s

因为w_n^k≠0,所以s=0

我们令V^{-1}(i, j) = (w_n^{-i})^j

所以(V\times V^{-1})(i, j)=\sum_{k =0}^{n-1}(w_n^{-i})^k\times (w_n^k)^j=\sum_{k = 0}^{n - 1}(w_n^{j -i})^k

根据性质三，当i=j时(V\times V^{-1})(i, i)=n，否则=0，只需要把每一项/n即可

然后我们有发现，只需要把A看成新的系数，把所有的(w_n^j)^k看成(w_n^{-j})^k，那么就是一边新的DFT了

所以唯一的差别就是单位根前面乘了一个-1即可

\rm Code:

struct node {
    D x, y;
}a[maxn], b[maxn];
il node operator + (node a, node b) {return (node){a.x + b.x, a.y + b.y};}
il node operator - (node a, node b) {return (node){a.x - b.x, a.y - b.y};}
il node operator * (node a, node b) {return (node){a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x};}
int n, m, lim;
il void FFT(node *x, int f, int len) {
    if(len == 1) return;
    node f1[len >> 1], f2[len >> 1];
    for(re int i = 0; i < len; i += 2) f1[i / 2] = x[i], f2[i / 2] = x[i + 1];
    FFT(f1, f, len >> 1), FFT(f2, f, len >> 1);
    node w = (node){1, 0}, base = (node){cos(2.0 * pi / len), f * sin(2.0 * pi / len)};
    for(re int i = 0; i < (len >> 1); ++ i, w = w * base) {
        x[i] = f1[i] + w * f2[i], x[i + (len >> 1)] = f1[i] - w * f2[i];
    }
}
int main() {
    n = read(), m = read();
    rep(i, 0, n) a[i].x = read();
    rep(i, 0, m) b[i].x = read();
    while((1 << lim) <= n + m) ++ lim;
    FFT(a, 1, (1 << lim)), FFT(b, 1, (1 << lim));
    rep(i, 0, (1 << lim)) a[i] = a[i] * b[i];
    FFT(a, -1, (1 << lim));
    rep(i, 0, n + m) printf("%d ", (int)(a[i].x / (1 << lim) + 0.5));
    return 0;
}

讲讲迭代版的\rm FFT

通过打表发现：一个数x再最后一次出现的位置r[i]是可以通过公式算出来的：r[i] = (r[i >> 1] >> 1)\ |\ ((i\ \&\ 1) << (lim - 1))

然后我们在\rm FFT前面把x交换到对应位置，然后用类似上述方法一个个合并即可（我不是懒，是怕东西太多页面卡）

\rm Code:

il void FFT(node *x, int f, int len) {
    rep(i, 0, len - 1) if(i < r[i]) swap(x[i], x[r[i]]);
    for(int mid = 1; mid < len; mid <<= 1) {
        node base = (node){cos(pi / mid), f * sin(pi / mid)};
        for(re int p = mid * 2, j = 0; j < len; j += p) {
            node w = (node){1, 0};
            for(re int k = 0; k < mid; ++ k, w = w * base) {
                node a = x[j + k], b = w * x[j + k + mid];
                x[j + k] = a + b, x[j + k + mid] = a - b;
            }
        }
    } 
}
rep(i, 0, (1 << lim)) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lim - 1));

\rm NTT:

大概就是你把原根看成单位根，然后跑FFT即可（我不是懒，是怕东西太多页面卡）

\rm Code:

#define mod 998244353
#define invG 332748118
#define G 3
#define maxn 10000006
int n, m, a[maxn], b[maxn], l, lim = 1, r[maxn];
il int qpow(int a, int b) {
    int r = 1;
    while(b) {
        if(b & 1) r = 1ll * r * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return r;
}
il void NTT(int *x, int f, int len) {
    rep(i, 0, len) if(i < r[i]) swap(x[i], x[r[i]]);
    for(re int mid = 1; mid < len; mid <<= 1) {
        int base = qpow((f == 1) ? G : invG, (mod - 1) / (mid << 1));
        for(re int p = mid * 2, j = 0; j < len; j += p) {
            for(re int k = 0, w = 1; k < mid; ++ k, w = 1ll * w * base % mod) {
                int a = x[j + k], b = 1ll * w * x[j + k + mid] % mod;
                x[j + k] = (a + b) % mod, x[j + k + mid] = (a - b + mod) % mod;
            }
        }
    }
}
signed main() {
    n = read(), m = read();
    rep(i, 0, n) a[i] = read();
    rep(i, 0, m) b[i] = read();
    while(lim <= (n + m)) ++ l, lim <<= 1;
    rep(i, 0, lim) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    NTT(a, 1, lim), NTT(b, 1, lim);
    rep(i, 0, lim) a[i] = 1ll * a[i] * b[i] % mod;
    NTT(a, -1, lim);
    int inv = qpow(lim, mod - 2);
    rep(i, 0, n + m) printf("%d ", (1ll * a[i] * inv) % mod);
    return 0;
}

\rm MTT

然后我们有两个多项式，假设第一个在$/M$意义下算出来的多项式为$A_1$，再$\%M$意义下算出来的多项式为$B_1$，第二个多项式的值分别为$A_2, B_2$。然后我们本质上就是要计算$(A_1\times M + B_1)\times (A_2\times M + B_2)

我们拆系数的原因是因为不去摸的话算出来的值很大，\rm FFT的精度会炸掉。假设我们选择的M为\sqrt{P}，那么最后的结果会变成P级别。保证了精度

(A_1\times M + B_1)\times (A_2\times M + B_2)=A_1\times A_2\times M^2+(A_1\times B_2 + A_2\times B_1)\times M + B_1 \times B_2

我们分别算出A_1\times A_2, A_1\times B_2 + A_2\times B_1, B_1 \times B_2，再讲答案合并即可

模板题有点卡精度，需要long\ double

\rm FWT

咕咕咕

多项式求逆

首先假设原函数为G，G\times F=1(mod\ x^n)，我们有F\%x^1=inv(G_0)，然后，我们思考怎么从F\%x^{\frac{n}{2}}推出F\%x^n

令新的多项式为H，我们已知F\times G=1(mod\ x^\frac{n}{2}),H\times G=1(mod\ x^n)我们不难发现：H-F=0(mod\ x^\frac{n}{2})，所以我们有(H-F)^2=0(mod\ x^n)（这个证明可以把(H-F)\%x^\frac{n}{2}为一个0-\frac{n}{2}项全为0的多项式，发现平方后前N项全是0）展开后我们有：H^2+F^2-2\times H\times F=0(mod\ x^n)，两边同时乘以G得，H+F^2G-2\times F=0(mod\ x^n)

分治\rm FFT

法一：直接用求逆来做：

构造F(x)=\sum_{i=0}^{\infty}x^if_i,\;\;G(x)=\sum_{i=0}^{\infty}x^ig_i

所以我们有：$F(x)\times G(x)+1=F(x) #### 法二：正宗分治$\rm FFT

我们把多项式拆成两个部分，[l, mid],[mid + 1, r]，分别递归求解，然后再合并答案。

考虑第一部分对第二部分的贡献，也就是对于每一个x\in [l, r], w[x]=\sum_{i=l}^{mid}f_i\times g_{x-i}

化简一下（这里我们令f_x=0, x\in[mid + 1, r]），我们有w[x]=\sum_{i =0}^{x-l-1}f_{i+l}\times g_{x-i-l}

于是，令a_i=f_{i+l}, b_i=g_{i+1}。w[x]=\sum_{i =0}^{x-l-1}a_{i}\times b_{x-i-l-1}，不难发现这是一个卷积的形式，算出来即可。

求导与泰勒展开

详见博文[THUWC2017]在美妙的数学王国中畅游

牛顿迭代

牛顿迭代的一般运用是求出函数G(F(x))的零点

假设我们已经知道了G(F_0(x))=0(mod\ x^{\frac{n}{2}})，F(x)-F_0(x)=0(mod\ x^{\frac{n}{2}})

将其在F_0(x)处泰勒展开，我们有G(F(x))=G(F_0(x))+\dfrac{G'(F_0(x))}{1!}\times (F(x)-F_0(x))+\dfrac{G''(F_0(x))}{2!}\times (F(x)-F_0(x))^2+……

由于我们只需要拓展成mod\ x^n，二次项以后，最小非零项大于n，所以我们都可以忽略

带入G(F_0(x))，移项，两边同时除以G'(F_0(x))

F(x)=F_0(x) - \dfrac{G(F_0(x))}{G'(F_0(x))}

多项式求\rm ln

B(x)=ln(A(x))$，所以有：$B(x)'=ln(A(x))'\times A(x)' ### 多项式求$\rm exp

由于e^{B(x)}=A(x)，两边同时取ln，并且移项后我们有：

ln(A(x))-B(x)=0

然后看作G(A(x))=ln(A(x))-B(x)，求这个函数的0点。

由于我们要求的是A(x)，B(x)的变化与A(x)无关，可以看成一个常数，然后把B(x)看作常量，把A(x)看作变量，我们有G'(A(x))=\dfrac{1}{A(x)}

带入牛顿迭代的柿子，我们有：A(x)=A_0(x) - A_0(x)\times G(A_0(x))=A_0(x) - A_0(x)\times (ln(A_0(x))-B(x))

### 多项式除法 定义$F^R(x)$将$F(x)$系数反转后得到的多项式 $$F(x)=Q(x)\times G(x)+R(x)$$ $$F(\frac{1}{x})=Q(\frac{1}{x})\times G(\frac{1}{x})+R(\frac{1}{x})$$ 同时乘以$x^n x^nF(\frac{1}{x})=x^{n-m}Q(\frac{1}{x})\times x^mG(\frac{1}{x})+x^{n-m-1}\times x^{m-1}R(\frac{1}{x}) F^R(x)=Q^R(x)\times G^R(x)+x^{n-m-1}R^R(x) F^R(x)=Q^R(x)\times G^R(x)(mod\ x^{n-m-1})

所以根据多项式求逆可以求出Q^R(x)，再根据R^R(x)=F^R(x)-Q^R(x)\times G^R(x)即可求出R(x)

多项式开根

ln 以下再 exp 一下

H(x)^2=F(x)(mod\ x^{\frac{n}{2}}) G(x)^2=F(x)(mod\ x^{\frac{n}{2}}) G(x)-H(x)=0(mod\ x^{\frac{n}{2}}) G(x)^2-2\times H(x)G(x)+H(x)^2=0(mod\ x^{n}) F(x)+H(x)^2=2\times H(x)G(x)(mod\ x^{n}) \frac{F(x)}{2H(x)}+\frac{H(x)}{2}=G(x)(mod\ x^{n})

求逆即可。复杂度证明和求逆一样，都是一个log

多项式快速幂

### 插值 咕咕咕 ### 一些简单的生成函数 #### 广义组合数： $\dbinom{a}{i}=\dfrac{a^{\underline{i}}}{i!}$，所以组合数我们可以拓展到任意实数的情况 #### 广义二项式定理及其推论 $$(x+y)^{n}=\sum_{i=0}^{inf}\binom{n}{i}\times x^i\times y^{n-i}$$ $$(1+x)^{-a}=\sum_{i=0}^{\infty}\dbinom{-a}{i}x^i$$ $$\dbinom{-a}{i}=\dfrac{(-a)(-a-1)(-a-2)...(-a-i+1)}{i!}=(-1)^i\dfrac{(a+i-1)^{\underline{i}}}{i!}$$ 所以： $$(1+x)^{-a}=\sum_{i=0}^{\infty}(-1)^i\dbinom{a+i-1}{i}x^i$$ 我们令$x=-x$代入上式： $$(1-x)^{-a}=\sum_{i=0}^{\infty}(-1)^i\dbinom{a+i-1}{i}(-x)^i$$ 即： $$\dfrac{1}{(1-x)^n}=\sum_{i=0}^{\infty}\dbinom{n+i-1}{i}x^i$$ ### 多项式三角函数 根据欧拉公式，我们有：$e^{ix}=cos(x)+i\times sin(x) e^{iA(x)}=cos(A(x))+i\times sin(A(x)) e^{-iA(x)}=cos(A(x))-i\times sin(A(x))

于是我们有：cos(A(x))=\dfrac{e^{ix}+e^{-ix}}{2}, sin(A(x))=\dfrac{e^{ix}+e^{-ix}}{2\times i}

发现仍然有虚数单位i，但是因为我们知道i^2=-1，于是二次剩余算一下即可