浅谈多项式

· · 个人记录

浅谈多项式

大概涉及一些多项式的运算，算是多项式里面比较基础的内容吧。

前置知识

  1. FFT
  2. NTT
  3. 多项式求导
  4. 简单的积分

如果会，可以直接跳过。。

如果还不会NTT，推荐学习这一篇博客，如果连FFT都不会，请先学会FFT，推荐食用这篇博客或者这篇博客

多项式求导

不严谨的说，一个函数在一个位置的导数就是这个位置上切线的斜率。。

这里需要的多项式求导的知识非常简单，好像只要知道下面五个式子就够了。。(注:这里的'表示求导的意思)

f(x)=e^x \qquad f'(x)=e^x f(x)=ln\ x \qquad f'(x)=\frac{1}{x} f(x)=ax^t \qquad f'(x)=atx^{t-1} (f(x) \pm g(x))'=f'(x) \pm g'(x) (f(g(x)))'=f'(g(x)) \ast g'(x)

所以我们可以推出多项式求导的公式：

f(x)=\sum_{i=0}^{n}a_ix^i \qquad f'(x)=\sum_{i=0}^{n-1}(i+1)a_{i+1}x^i

多项式积分

这里不说多难，也不求非常严谨，能做出题就行。

对于这样一个导数：

f'(x)=\sum_{i=0}^{n}a_ix^i

我们想要知道它原来的函数怎么办？？

积分啊。。

这里也只给公式，不深入探究(毕竟这里不是重点，待会只用结论就好)

(其实也就是求导的逆过程)

f(x)=\sum_{i=1}^{n+1}\frac{a_{i-1}x^i}{i}

(当然，上面的多项式是满足求导的结果是这个导数的一个最为简单的多项式。)

进入正题

好的，这里大概会讲如下的多项式有关的知识点：

  1. 多项式求逆
  2. 多项式求ln
  3. 多项式复合
  4. 多项式求exp
  5. 多项式快速幂
  6. 多项式除法

Tips：这里的知识一环套一环，如果不会前面的后面的基本上得凉凉。。(除非你是天才)

有点小多啊。。

不啰嗦了直接开始吧。

多项式求逆

问题1描述

给出多项式A(x)，求一个多项式B(x)使得A(x) \ast B(x) \equiv 1\ (mod\ x^n)

问题1分析

假设我们现在已经有了一个多项式C(x)，满足

A(x) \ast C(x) \equiv 1 \ (mod\ x^{\lceil \frac{n}{2} \rceil})

然后我们要求的B(x)也满足：

A(x) \ast B(x) \equiv 1\ (mod\ x^n)

变形一下也可以得到:

A(x) \ast B(x) \equiv 1 (mod\ x^{\lceil \frac{n}{2} \rceil})

至于为什么可以这么做，稍加思考一下也可以想出来吧。。

因为如果在模x^n的意义下A(x) \ast B(x)的结果是1的话，说明了x的1次幂一直到n-1次幂的系数都是0。这样一来这么转化也是可以的。

那么我们就可以继续操作了。

A(x) \ast (B(x) - C(x)) \equiv 0\ (mod\ x^{\lceil \frac{n}{2} \rceil})

因为A(x)一定不会为0(不然不可能求出逆啊。。)，那么我们就可以得知：

B(x) - C(x) \equiv 0 \ (mod\ x^{\lceil \frac{n}{2} \rceil})

平方一下：

B^2(x) \equiv 2B(x) \ast C(x) - C^2(x)\ (mod\ x^n)

然后两边再乘上一个A(x)：

A(x) \ast B^2(x) \equiv 2A(x) \ast B(x) \ast C(x) - A(x) \ast C^2(x)\ (mod\ x^n)

然后由A(x) \ast B(x) \equiv 1\ (mod\ x^n)得知：

B(x) \equiv 2C(x) - A(x) \ast C^2(x)\ (mod\ x^n)

这样一来，A(x)和C(x)我们都知道，那么B(x)也可以知道了。

然后算法也非常明显了：倍增。

特别的，当C(x)仅有一项(常数项)的时候，这个值就是A(x)的常数项的逆元。(和之前的东西也不相悖)

那么我们就有一个O(nlogn)的求多项式的逆的算法了。

这里给出求逆的代码。。

inline void init(reg int n) {
    N = 1; while(N <= (n << 1)) N <<= 1;
    for(reg int i = 0; i < N; i++)
        pos[i] = (pos[i >> 1] >> 1) | (i & 1 ? N >> 1 : 0);
} // 预处理出NTT的多项式长度和NTT交换的位置

inline int quick_pow(reg int a, reg int k) {
    reg int s = 1;
    while(k) {
        if(k & 1) s = (1LL * s * a) % mod;
        a = (1LL * a * a) % mod;
        k >>= 1;
    }
    return s;
}

inline void NTT(reg int a[], reg int k) {
    for(reg int i = 0; i < N; i++)
        if(i < pos[i]) swap(a[i], a[pos[i]]);
    for(reg int l = 2; l <= N; l <<= 1) {
        reg int len = l >> 1;
        reg int delta = quick_pow(G, (mod - 1) / l);
        for(reg int i = 0; i < N; i += l) {
            reg int g = 1;
            for(reg int j = i; j < i + len; j++) {
                reg int tmp = 1LL * g * a[j + len] % mod;
                a[j + len] = (a[j] - tmp + mod) % mod;
                a[j] = (a[j] + tmp) % mod;
                g = 1LL * g * delta % mod;
            }
        }
    }
    if(k) return ;
    reg int prd = quick_pow(N, mod - 2); reverse(a + 1, a + N);
    for(reg int i = 0; i < N; i++) a[i] = 1LL * a[i] * prd % mod;
} // 对N进行NTT。。

inline void GetNi(reg int A[], reg int B[], reg int n) {
    if(n == 1) { B[0] = quick_pow(A[0], mod - 2); return ; }
    GetNi(A, B, (n + 1) / 2); init(n);
    memcpy(tA, A, n * 4); fill(tA + n, tA + N, 0);
    NTT(tA, 1); NTT(B, 1);
    for(reg int i = 0; i < N; i++) B[i] = 1LL * (2 - 1LL * tA[i] * B[i] % mod + mod) * B[i] % mod;
    NTT(B, 0); fill(B + n, B + N, 0);
} // 将求得A的逆放在B中

小结1

多项式求逆实际上是一个倍增的过程。

每一次确定的答案多项式就会增长一倍。

练习1

模板题

多项式求ln

问题2描述

给定一个多项式f(x)，求出g(x)满足g(x) \equiv ln\ f(x)\ (mod\ x^n)。

问题2分析

这个还是比较好推的。

我们对g(x)求个导，得到这样一个玩意：

g'(x) \equiv ln'(f(x)) \ast f'(x)\ (mod\ x^n) g'(x) \equiv \frac{f'(x)}{f(x)}\ (mod\ x^n)

然后\frac{1}{f(x)}这个东西我们可以用多项式求逆搞出来，然后和f'(x)(这个东西很好算，用上面介绍的多项式求导的公式就好了)乘起来就好了。

我们搞出来了g'(x)，但是想要我们要知道的是g(x)啊。。

把导数还原成多项式。。这个用上面的那一个积分的公式就出来了。。

时间复杂度O(nlogn)

代码有点长啊。。还是只放上比上面的代码多出来的部分吧。。(这就清爽多了。。)

// 后面的内容就是在前面的基础上加的东西
inline void GetDao(reg int a[], reg int b[], reg int n) {
    for(reg int i = 1; i < n; i++) b[i - 1] = 1LL * a[i] * i % mod; b[n - 1] = 0;
} // 将a求得的导数放在b中

inline void Getjf(reg int a[], reg int b[], reg int n) {
    for(reg int i = 1; i < n; i++) b[i] = 1LL * a[i - 1] * quick_pow(i, mod - 2) % mod; b[0] = 0;
} // 将a积分出来的多项式放在b中

inline void Getln(reg int a[], reg int b[], reg int n) {
    GetNi(a, b, n); GetDao(a, c, n); init(n); NTT(b, 1), NTT(c, 1);
    for(reg int i = 0; i < N; i++) b[i] = 1LL * b[i] * c[i] % mod;
    NTT(b, 0); Getjf(b, c, n); memcpy(b, c, n * 4);
} // 将ln(a)求得的多项式放在b中

问题2小结

多项式求ln需要求一个导数，然后发现是两个比较好求的多项式的乘积，这样一来就比较可以简单计算了。

练习2

模板题

多项式复合

问题3描述

给定一个多项式G(x)，求出一个多项式f(x)使得G(f(x)) \equiv 0\ (mod\ x^n)

问题3分析

大量数学式来袭，请系上安全带，准备开车了

首先我们需要知道泰勒展开。

已知多项式F(x)，以及其在x_0的值，则该多项式在x的取值可表示为：

F(x) = G(x_0) + \sum_{i=1}^{\infty}\frac{G^{(i)}(x_0)}{i!}(x-x_0)^i

其中G^{(i)}(x_0)表示对G(x_0)求i阶导数

那么这里有什么用呢。。

假设我们已经知道了一个多项式f_{t-1}使得G(f_{t-1}) \equiv 0\ (mod\ x^{2^{t-1}})，然后现在的问题是求一个多项式f_t使得G(f_t) \equiv 0\ (mod\ x^{2^t})

这样的话。。我们尝试对G(f_t)做个泰勒展开：

G(f_t) \equiv G(f_{t-1}) + \sum_{i=1}^{\infty}\frac{G^{(i)}(f_{t-1})}{i!} \ast (f_t-f_{t-1})^i\ (mod\ x^{2^t})

然后发现这个式子好像并不是很可做的样子啊。。

那么冷静分析一下，发现由于有：

G(f_{t}) \equiv 0\ (mod\ x^{2^{t}})

则说明G(f_t)除常数项外系数不为0的项次数大于t，那么我们就可以有：

G(f_{t}) \equiv 0\ (mod\ x^{2^{t-1}})

又因为：

G(f_{t-1}) \equiv 0\ (mod\ x^{2^{t-1}})

则可以得知：

然后回到上面的式子，发现是在模$x^{2^t}$的意义下。那么显然的是，包含了$(f_t-f_{t-1})^x\ (x > 1)$的项都为$0$了。 然后我们再把上面的式子化简一下，就可以得到： $$G(f_t) \equiv G(f_{t-1}) + G'(f_{t-1}) \ast (f_t-f_{t-1})\ (mod\ x^{2^t})$$ 简单多了。。 然后由我们要求的式子： $$G(f_t) \equiv 0\ (mod\ x^{2^t})$$ 所以有： $$G(f_{t-1}) + G'(f_{t-1}) \ast (f_t-f_{t-1})\ \equiv 0\ (mod\ x^{2^t})$$ 我们再变形一下： $$f_t=f_{t-1}-\frac{G(f_{t-1})}{G'(f_{t-1})}$$ 这样我们就得到了一个倍增的做法了。 复杂度$O(nlogn)

小结3

多项式复合需要使用泰勒展开公式。

套用泰勒展开公式的时候需要观察式子特征然后去掉没有用的项简化计算。

练习3

尝试不看上面的内容重新推一下这个递推式。

多项式求exp

问题4描述

给出一个多项式F(x)，求出e^{F(x)}。

问题4分析

如果理解了上面的多项式复合的话，这个还是比较简单的。

我们可以构造一个多项式G(g(x)) = ln(g(x)) - F(x)，然后G(g(x)) \equiv 0\ (mod\ x^n)的解g(x)就满足g(x) \equiv e^{F(x)}\ (mod\ x^n)

多项式复合！！

套用一下上面的公式就好了。

Tips：公式中的G'(g(x))是这样的：

G'(g(x)) \equiv \frac{1}{g(x)} \ (mod\ x^n)

原因：这里的g(x)应看做一个字母！不要看做一个多项式！F(x)是一样的道理！

所以递推式长这个样子：

f_t \equiv f_{t-1} - (ln(f_{t-1})+F(x)) \ast f_{t-1} \ (mod\ x^{2^t})

然后照例倍增就好了。。

复杂度O(nlogn)

照例给出代码。注意带上exp的求ln还需要在后面加上清零，不然会WA。(调了一个小时的地方啊。。)

inline void Getln(reg int a[], reg int b[], reg int n) {
    GetNi(a, b, n); GetDao(a, c, n); init(n); NTT(b, 1); NTT(c, 1);
    for(reg int i = 0; i < N; i++) b[i] = 1LL * b[i] * c[i] % mod;
    NTT(b, 0); Getjf(b, c, n); memcpy(b, c, n * 4); fill(c, c + N, 0); // 就是这里了。。暂时使用的c数组需要清零。这里因为知道用过的地方所以直接精准定位了。。
}

inline void Getexp(reg int a[], reg int b[], reg int n) {
    if(n == 1) { b[0] = 1; return ; }
    Getexp(a, b, (n + 1) >> 1); Getln(b, tB, n); init(n);
    fill(tB + n, tB + N, 0); memcpy(tC, a, 4 * n); fill(tC + n, tC + N, 0);
    NTT(b, 1), NTT(tB, 1), NTT(tC, 1);
    for(reg int i = 0; i < N; i++) b[i] = (1LL * b[i] * (1LL - tB[i] + tC[i]) % mod + mod) % mod;
    NTT(b, 0); fill(b + n, b + N, 0); fill(tB, tB + N, 0);
} // 将求得的a的exp放在b中。

小结4

多项式求exp需要用到多项式复合和多项式求ln。

练习4

  1. 模板题

  2. 尝试自己推一下多项式开根的递推式(多项式开根)

多项式快速幂

问题5描述

给定一个多项式f(x)，求一个多项式g(x)使得g(x) \equiv f^k(x)\ (mod\ x^n)。

问题5分析

这个。。只要找到了一个突破口就好了。

首先联想一下：什么样的运算能够把指数变成四则运算呢？？

求对数啊！！

那么我们把两边都套上一个ln试试：

ln(g(x)) \equiv ln(f^k(x))\ (mod\ x^n) ln(g(x)) \equiv k\times ln(f(x))\ (mod\ x^n)

这样就好了么。。

然后再把g(x)还原回来：

e^{ln(g(x))} \equiv e^{k\times ln(f(x))} \ (mod\ x^n) g(x) \equiv e^{k\times ln(f(x))} \ (mod\ x^n)

大功告成！！

复杂度O(nlogn)

小结5

多项式快速幂需要把指数给弄下来，这让我们联想到对数运算。

练习5

好好理解和掌握上面的思想。尝试写一下多项式快速幂的代码。

多项式除法

问题6描述

给定一个n次多项式A(x)和一个m次多项式B(x)，求出多项式Q(x)和R(x)，且满足以下条件：

  1. A(x) = B(x) \ast Q(x) + R(x)
  2. Q(x)$的次数为$n-m$，$R(x)$的次数小于$m

问题6分析

这个的话。。有一个思路奇诡的巧妙做法：

定义A^{r(n)}(x)是一种对多项式次数\le n的多项式的操作：将次数从0到n的项的系数翻转。

公式表达：

若原多项式A(x)可表示为：(大于多项式的次数的项的a_i=0)

A(x)=\sum_{i=0}^{n}a_ix^i

则A^{r(n)}(x)可表示为：

A^{r(n)}(x)=\sum_{i=0}^{n}a_{n-i}x^i

然后我们就可以拿着这个东西搞事了。。

首先可以发现这样一个等式：

A^{r(n)}(x) = x^n \times A(\frac{1}{x})

然后由于A(x) = B(x) \ast Q(x) + R(x)，我们可以变一下形：

A(\frac{1}{x}) = B(\frac{1}{x}) \ast Q(\frac{1}{x}) + R(\frac{1}{x})

应该没有一点问题。。

然后带入上式可得：

A^{r(n)}(x) = x^n \times (B(\frac{1}{x}) \ast Q(\frac{1}{x}) + R(\frac{1}{x})) A^{r(n)}(x) = x^n \times (B(\frac{1}{x}) \ast Q(\frac{1}{x})) + x^n \times R(\frac{1}{x}) A^{r(n)}(x) = (x^m \times (B(\frac{1}{x}) \ast (x^{n-m} \times Q(\frac{1}{x})) + x^n \times R(\frac{1}{x}) A^{r(n)}(x) = B^{r(m)}(x) \ast Q^{r(n-m)}(x) + R^{r(n)}(x)

然后由于R(x)的次数小于m，那么从第n项开始转的话R^{r(n)}(x)的前n-m项的系数就必然为0。

那么我们可以模一下x^{n-m+1}，这样的话R^{r(n)}(x)就没有了。。而且我们还完美地保留了Q^{r(n-m)}(x)

这样一来我们就可以得到下面这样的式子：

A^{r(n)}(x) \equiv B^{r(m)}(x) \ast Q^{r(n-m)}(x)\ (mod\ x^{n-m+1})

然后移一下项。。

Q^{r(n-m)}(x) \equiv \frac{A^{r(n)}(x)}{B^{r(m)}(x)}\ (mod\ x^{n-m+1})

然后我们把它转回去就好了。。

Q(x) \equiv (\frac{A^{r(n)}(x)}{B^{r(m)}(x)})^{r(n-m)}\ (mod\ x^{n-m+1})

至于R(x)。。用原来的A(x) = B(x) \ast Q(x) + R(x)移一下项然后直接算就好了。。

复杂度O(nlogn)

老规矩，上部分代码。

inline void Mul(reg int A[], reg int B[], reg int C[], reg int n, reg int m) {
    init(n + m);
    memcpy(tp, A, 4 * n), fill(tp + n, tp + N, 0); NTT(tp, 1);
    memcpy(tq, B, 4 * m), fill(tq + m, tq + N, 0); NTT(tq, 1);
    for(reg int i = 0; i < N; i++) C[i] = 1LL * tp[i] * tq[i] % mod; NTT(C, 0);
} // A(次数为n-1) * B(次数为m-1) 的结果放在C中

inline void Div(reg int A[], reg int B[], reg int Q[], reg int n, reg int m) {
    memcpy(tB, B, 4 * (m + 1)); reverse(tB, tB + m + 1); GetNi(tB, Q, n - m + 1);
    memset(tC, 0, 4 * MAXN); memcpy(tC, A, 4 * (n + 1)); reverse(tC, tC + n + 1);
    Mul(Q, tC, Q, n - m + 1, n + 1); fill(Q + n - m + 1, Q + MAXN, 0); reverse(Q, Q + n - m + 1);
} // A(最高次为n) / B(最高次为m) 的结果放在Q中

inline void Mod(reg int A[], reg int B[], reg int Q[], reg int R[], reg int n, reg int m) {
    Mul(B, Q, R, m + 1, n - m + 1); for(reg int i = 0; i <= n; i++) R[i] = (A[i] - R[i] + mod) % mod;
} // 计算除法后剩下的余项

小结6

多项式除法用了一种比较骚的做法：把系数转过来。

练习6

模板题

完结撒花