多项式备忘录

最近学了多项式相关的一些东西,写一点备忘录,主要是公式和证明,可能每次只会写一点点。

导数

部分简单函数的导数

$$ (e^x)’ = e^x , (\ln x)’=\frac{1}{x} , (\sin x)’ = \cos x , (\cos x)’ = -\sin x $$

函数复合求导

$$ (f(x)+g(x))’ = f'(x) + g'(x) $$
$$ (f(x)g(x))’ = f'(x)g(x)+f(x)g'(x) $$
$$ (f(g(x)))’ = f'(g(x))g'(x) $$
上面这个比较重要,经常容易忘记多个函数复合,都要求导。

原根

这东东和 NTT 有关,但是在这里不多提了。
要记住的是 $998244353, 1004535809$ 的原根 $g$ 为 $3$ 。
在 NTT 中常用 $g^{\frac{P-1}{n}}$ 来代替 $e^{\frac{2\pi}{n}}$ 做转换。

泰勒展开

这对后面很多式子的转化和简化都帮助较大,需要重点记一下。
假设对 $F(x)$ 在 $x_0$ 处泰勒展开。
那么有:
$$ F(x) = F(x_0) + \sum_{n\geq 1} \frac{F^{(n)}(x_0)}{n!} (x-x_0)^n $$
其中 $F^{(n)}(x_0)$ 为 $F(x)$ 在 $x_0$ 处的 $n$ 阶导。
在实际引用中选取使 $F^{(n)}(x_0)$ 的取值较简单或特殊的 $x_0$ 做展开,如 $e^x$ 常在 $x_0=0$ 处,因为 $(e^x)’=e^x, e^0=1$ 。

多项式求逆

这是一个很重要的东西,在很多地方都要用到。

求逆的问题

在$\mod x^n$ 意义下多项式 $f(x)$ 有逆元 $g(x)$ 使 $f(x)g(x)\equiv 1\pmod{x^n}$
设函数 $h(x)$ 满足
$$ f(x)h(x)\equiv 1 \pmod{x^{\lceil \frac{n}{2}\rceil}} $$
显然有
$$ f(x)g(x)\equiv 1 \pmod{x^{\lceil \frac{n}{2}\rceil}} $$
然后二式相减
$$ f(x)\cdot (g(x)-h(x)) \equiv 0 \pmod{x^{\lceil \frac{n}{2}\rceil}} $$
消去 $f(x)$ 然后平方
$$ g^2(x)-2g(x)h(x)+h^2(x)\equiv 0 \pmod{x^n} $$
两边同时乘 $f(x)$ ,由于 $f(x),g(x)$ 互为逆元,可以得到
$$ g(x)=2h(x)-f(x)\cdot h^2(x) \pmod{x^n} $$
此时我们得到了一个递推式,由于 $h(x)$ 相对于 $g(x)$ 的规模减小了一半,所以考虑分治做。
复杂度 $F(n)=O(n\log n)+F(\frac{n}{2})=O(n\log n)$

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define reg register
#define MAX_N 2000007
#define MOD 998244353
#define G 3LL
typedef long long ll;

int N;
int r[MAX_N];
ll a[MAX_N], b[MAX_N], tmp[MAX_N];

inline void NTT (ll *A, int N, int type) {
    for (int i = 0; i < N; ++i)
        if (i < r[i])
            std::swap(A[i], A[r[i]]);
    for (int i = 1; i < N; i <<= 1) {
        ll gn = quick_pow(G, (MOD - 1) / (i << 1));
        if (type == -1) gn = quick_pow(gn, MOD - 2);
        for (int j = 0, L = i << 1; j < N; j += L) {
            ll x, y, g = 1;
            for (int k = 0; k < i; ++k, (g *= gn) %= MOD) {
                x = A[j + k], y = A[i + j + k] * g % MOD;
                A[j + k] = (x + y) % MOD, A[i + j + k] = (x - y + MOD) % MOD;
            }
        }
    }
    if (type == 1) return;
    for (int i = 0; i < N; ++i)
        A[i] = A[i] * quick_pow(N, MOD - 2) % MOD;
}

void solve (int deg, ll *a, ll *b) {
    if (deg == 1) {
        b[0] = quick_pow(a[0], MOD - 2);
        return;
    }
    solve((deg + 1) >> 1, a, b);
    int len = 0, M = 1;
    while (M < (deg << 1)) M <<= 1, ++len;
    for (int i = 0; i < M; ++i)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << len - 1);
    for (int i = 0; i < deg; ++i)
        tmp[i] = a[i];
    for (int i = deg; i < M; ++i)
        tmp[i] = 0;
    NTT(tmp, M, 1), NTT(b, M, 1);
    for (int i = 0; i < M; ++i)
        b[i] = (2LL - tmp[i] * b[i] % MOD + MOD) % MOD * b[i] % MOD;
    NTT(b, M, -1);
    for (int i = deg; i < M; ++i)
        b[i] = 0;
}

int main () {
    read(N);
    for (int i = 0; i < N; ++i)
        read(a[i]);
    solve(N, a, b);
    for (int i = 0; i < N; ++i)
        printf("%lld ", b[i]); puts("");
    return 0;
}

求多项式对数

问题

已知多项式 $f(x)$ ,求 $g(x) = \ln f(x)$
$$ g(x)\equiv \ln f(x) \pmod{x^n} $$
两边求导(记得符合函数分别求)
$$ g'(x)\equiv \frac{f'(x)}{f(x)} \pmod{x^n} $$
然后两边积分回去
$$ g(x)\equiv \int \frac{f'(x)}{f(x)} \pmod{x^n} $$
这里补充一下多项式求导和积分:
$$ f'(x) = \sum_{i=1}^{n-1} ia_ix^{i-1}$$
$$ \int f(x)=\sum_{i=1}^{n-1}\frac{a_i x^{i+1}}{i+1} $$
总复杂度 $O(n\log n)$

代码


void trans (int deg, ll *a, ll *b) { if (deg == 1) { b[0] = quick_pow(a[0], MOD - 2); return; } trans((deg + 1) >> 1, a, b); int len = 0, M = 1; while (M < (deg << 1)) len++, M <<= 1; for (int i = 0; i < M; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << len - 1); for (int i = 0; i < deg; ++i) tmp[i] = a[i]; for (int i = deg; i < M; ++i) tmp[i] = 0; NTT(tmp, M, 1), NTT(b, M, 1); for (int i = 0; i < M; ++i) b[i] = (2LL - tmp[i] * b[i] % MOD + MOD) % MOD * b[i] % MOD; NTT(b, M, -1); for (int i = deg; i < M; ++i) b[i] = 0; } int main () { read(N); for (int i = 0; i < N; ++i) read(a[i]); trans(N, a, b); for (int i = 0; i < N - 1; ++i) a[i] = (ll)(i + 1) * a[i + 1] % MOD; int len = 0, M = 1; while (M < (N << 1)) len++, M <<= 1; for (int i = 0; i < M; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << len - 1); for (int i = N - 1; i < M; ++i) a[i] = 0; for (int i = N; i < M; ++i) b[i] = 0; NTT(a, M, 1), NTT(b, M, 1); for (int i = 0; i < M; ++i) a[i] = a[i] * b[i] % MOD; NTT(a, M, -1); for (int i = N - 2; i >= 0; --i) a[i + 1] = a[i] * quick_pow((ll)(i + 1), MOD - 2) % MOD; a[0] = 0; for (int i = 0; i < N; ++i) printf("%lld ", a[i]); puts(""); return 0; }

多项式复合

对很多多项式的操作都有帮助,或者说很多操作都可以用多项式复合来解决。
现在用一个例子来说明一下。

如何复合

给出一个函数 $F(x)$ ,请求出 $f(x)=e^{F(x)}$
首先使用一个套路,令 $G(f)=\ln f – F(x)$ ,注意 $G$ 的自变量为函数 $f$
发现 $G(f) = 0$ 的解即为 $f(x)=e^{F(x)}$ ,也就是要求的东西。
假设已求出 $f_t(x)$ 为 $G(f_t)\equiv 0 \pmod{x^{2^t}}$ 的解,要推出 $f_{t+1}$
对 $G$ 在 $f_t$ 处作泰勒展开
$$ G(f_{t+1}) = G(f_t) + G'(f_t)\cdot (f_{t+1}-f_t) + \sum_{n\geq 2} \frac{G^{(n)}(f_t)}{n!}\cdot (f_{t+1}-f_t)^n \pmod{x^{2^{t+1}}} $$
由于 $G(f_t)\equiv 0 \pmod{x^{2^t}} , G(f_{t+1})\equiv 0 \pmod{x^{2^{t+1}}}$
所以 $f_{t+1}-f_t$ 的前 $2^t$ 项系数都为 $0$ ,那么 $n$ 从 $2$ 开始, $(f_{t+1}-f_t)^n\equiv 0 \pmod{x^{2^{t+1}}}$ ,可以将它们省略。
那么我们就得到了一个美妙的式子
$$ G(f_{t+1}) = G(f_t) + G'(f_t)\cdot (f_{t+1} – f_t) \pmod{x^{2^{t+1}}}$$
我们要解 $G(f_{t+1})\equiv 0$ ,也就是要解 $G'(f_t)\cdot (f_{t+1}-f_t)+G(f_t)\equiv 0$
解得
$$ f_{t+1}\equiv f_t-\frac{G(f_t)}{G'(f_t)} \pmod{x^{2^{t+1}}} $$
上面那个式子用于多项式操作非常好用
现在我们继续解 $f(x)=e^{F(x)}$
由之前可得
$$ G(f_t) = \ln f – F(x) $$
$$ G'(f_t) = (\ln f)’ = \frac{1}{f} $$
带入得到递推式
$$ f_{t+1} = f_t – (\ln f – F(x))\cdot f_t $$
有一点需要注意的是,递归到底层也就是 $t=1$ 时可以直接算出答案为 $e^{F(0)}$ ,但是在模意义下这个式子任然不好求值,所以在题目中, $F(0)$ 通常为 $0$ ,故 $e^{F(0)}=1$

复合的其他用途

这里只提起部分用途

多项式开根

已知 $F(x)$ ,求 $f(x)$ 使 $f^2(x)\equiv F(x) \pmod{x^n} $
设 $G(f) = f^2 – F(x) $
已知 $f_t$ ,则
$$ f_{t+1} = f_t – \frac{G(f_t)}{G'(f_t)} = f_t – \frac{f^2_t – F(x)}{2f_t} = \frac{f^2_t+F(x)}{2f_t} \pmod{x^{2^{t+1}}} $$

多项式快速幂

已知 $f(x)$ ,求 $g(x) = f^k(x)$
由题目
$$g(x)-f^k(x)\equiv 0 \pmod{x^n}$$
$$\ln g(x)\equiv k\ln f(x) \pmod{x^n}$$
$$g(x) \equiv e^{k\ln f(x)} \pmod{x^n}$$
然后用多项式对数和 $exp$ 就行了

多项式三角函数

可以在 pick 的博客上看一下

代码

最后放上求 $exp$ 的代码,由于有点长,影响格式所以放在最后面了

void trans (int deg, ll *a, ll *b) { // trans *a -> *a^{-1}
    if (deg == 1) {
        b[0] = quick_pow(a[0], MOD - 2);
        return;
    }
    trans((deg + 1) >> 1, a, b);
    int len = 0, M = 1;
    while (M < (deg << 1)) M <<= 1, ++len;
    for (int i = 0; i < M; ++i)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << len - 1);
    for (int i = 0; i < deg; ++i)
        tmp[i] = a[i];
    for (int i = deg; i < M; ++i)
        tmp[i] = 0;
    NTT(b, M, 1), NTT(tmp, M, 1);
    for (int i = 0; i < M; ++i)
        b[i] = (2LL - tmp[i] * b[i] % MOD + MOD) % MOD * b[i] % MOD;
    NTT(b, M, -1);
    for (int i = deg; i < M; ++i)
        b[i] = 0;
}

void transln (int n, ll *a, ll *b) { //trans *a -> ln *a
    memset(tmp, 0, sizeof(tmp));
    trans(n, a, b);
    for (int i = 0; i < n - 1; ++i)
        a[i] = (ll)(i + 1) * a[i + 1] % MOD;
    int len = 0, M = 1;
    while (M < (n << 1)) len++, M <<= 1;
    for (int i = 0; i < M; ++i)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << len - 1);
    for (int i = n - 1; i < M; ++i) a[i] = 0;
    for (int i = n; i < M; ++i) b[i] = 0;
    NTT(a, M, 1), NTT(b, M, 1);
    for (int i = 0; i < M; ++i)
        a[i] = a[i] * b[i] % MOD;
    NTT(a, M, -1);
    for (int i = n - 2; i >= 0; --i)
        a[i + 1] = a[i] * quick_pow((ll)(i + 1), MOD - 2) % MOD;
    a[0] = 0;
}

void solve (int deg, ll *a, ll *b, ll *c) { //trans *a -> e^*a
    if (deg == 1) {
        b[0] = 1LL;
        return;
    }
    solve((deg + 1) >> 1, a, b, c);
    memset(c, 0, sizeof(c));
    memset(tmp2, 0, sizeof(tmp2));
    for (int i = 0; i < deg; ++i)
        c[i] = b[i];
    transln(deg, c, tmp2); //trans c -> ln b
    for (int i = 0; i < deg; ++i)
        c[i] = (c[i] - a[i] + MOD) % MOD; //c -> ln b - a
    int len = 0, M = 1;
    while (M < (deg << 1)) M <<= 1, ++len;
    for (int i = deg; i < M; ++i)
        b[i] = 0;
    NTT(c, M, 1), NTT(b, M, 1);
    for (int i = 0; i < M; ++i)
        b[i] = (1LL - c[i] + MOD) % MOD * b[i] % MOD;
    NTT(b, M, -1);
    for (int i = deg; i < M; ++i)
        b[i] = 0;
}

int main () {
    read(N);
    for (int i = 0; i < N; ++i)
        read(a[i]);
    solve(N, a, b, c);
    for (int i = 0; i < N; ++i)
        printf("%lld ", b[i]); puts("");
    return 0;
}

引用资料

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注