多项式初等函数

本文主要介绍多项式的初等函数的定义以及在 OI 中如何求解。

注意，多项式的初等函数一般定义在模 \(x^n\) 意义下，但是在 OI 中，多项式系数通常还需要另外模一下 \(p\)​ 。

友情提醒：多项式模板题里的 \(n\)​​​ 表示的含义可能有细微差异（表示次数/项数），请注意分辨。

另外，本文中的代码并没有完全清空数组（懒），因此注意多测的清空问题。

---

1. 多项式求逆

给定多项式 \(f(x)\) ，求 \(f^{-1}(x)\)​ ，满足 \[ f^{-1}(x)f(x)\equiv 1 \pmod{x^n} \] 解法：

首先，易知 \[ [x^0]f^{-1}(x) = ([x^0]f(x))^{-1} \] 假设现在已经求出了 \(f(x)\) 在模 \(x^{\left\lceil\frac{n}{2}\right\rceil}\) 下的逆元 \(f_0^{-1}(x)\) ，有 \[ \begin{aligned} f(x) f_0^{-1}(x) & \equiv 1 &\pmod{ x^{\left\lceil\frac{n}{2}\right\rceil}} \\[6pt]f(x) f^{-1}(x) & \equiv 1 & \pmod{ x^{\left\lceil\frac{n}{2}\right\rceil}} \\[6pt]f^{-1}(x)-f_0^{-1}(x) & \equiv 0 &\pmod{ x^{\left\lceil\frac{n}{2}\right\rceil}} \end{aligned} \] 两边平方可得 \[ f^{-2}(x)-2 f^{-1}(x) f_0^{-1}(x)+f_0^{-2}(x) \equiv 0 \pmod{ x^n} \] 两边同乘 \(f(x)\) 并移项可得 \[ f^{-1}(x) \equiv f_0^{-1}(x)\left(2-f(x) f_0^{-1}(x)\right)\pmod{ x^n } \] 递归处理即可。

时间复杂度 \(T(n) = T\left(\frac{n}{2}\right) + \mathcal{O}(n \log n) = \mathcal{O}(n \log n)\)​​ 。

完整代码详见 洛谷P4238 【模板】多项式乘法逆 题解

void Inv(int n, int *a, int *b)
{
    if(n == 1) { b[0] = qpow(a[0], P - 2); return; }
    Inv((n + 1) / 2, a, b);
    int l = 0, limit = 1;
    for(; limit <= (n - 1) * 2; l++, limit *= 2);
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));

    for(int i = 0; i < n; i++) c[i] = a[i];
    for(int i = n; i < limit; i++) c[i] = 0;

    NTT(c, limit, 1); NTT(b, limit, 1);
    for(int i = 0; i < limit; i++)
        b[i] = (2 - c[i] * b[i] % P + P) % P * b[i] % P;
    NTT(b, limit, -1);
    for(int i = n; i < limit; i++) b[i] = 0;
}

---

2. 多项式开根

给定多项式 \(g(x)\) ，求 \(f(x)\) 满足 \[ f^2(x) \equiv g(x) \pmod{x^n} \] 解法：

首先讨论 \([x^0]g(x)\) 不为 \(0\) 的情况，易知 \[ [x^0]f(x) = \sqrt{[x^0]g(x)} \] 若 \([x^0]g(x)\) 没有平方根，则多项式 \(g(x)\) 没有平方根

另外，\(\left[x^0\right] g(x)\) 可能有多个平方根，因此选取不同的根会求出不同的 \(f(x)\) 。

假设现在已经求出了 \(g(x)\) 在模 \(x^{\left\lceil\frac{n}{2}\right\rceil}\) 意义下的平方根 \(f_0(x)\) ，则有 \[ \begin{aligned} f_0^2(x) & \equiv g(x) \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}} \\[6pt]f_0^2(x)-g(x) & \equiv 0 \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}} \\[6pt]\left(f_0^2(x)-g(x)\right)^2 & \equiv 0 \pmod{x^{n}} \\[6pt]\left(f_0^2(x)+g(x)\right)^2 & \equiv 4 f_0^2(x) g(x) \pmod{x^{n}} \\[6pt]\left(\frac{f_0^2(x)+g(x)}{2 f_0(x)}\right)^2 & \equiv g(x) \pmod{x^{n}} \\[6pt]\frac{f_0^2(x)+g(x)}{2 f_0(x)} & \equiv f(x) \pmod{x^{n}} \\[6pt]2^{-1} f_0(x)+2^{-1} f_0^{-1}(x) g(x) & \equiv f(x) \end{aligned} \] 于是倍增计算即可。

时间复杂度 \(T(n)=T\left(\frac{n}{2}\right)+\mathcal{O}(n \log n)=\mathcal{O}(n \log n)\)​

完整代码详见 洛谷P5205 【模板】多项式开根 题解

void Sqrt(int n, int *a, int *b)
{
    if(n == 1) { b[0] = 1; return; }
    Sqrt((n + 1) / 2, a, b);
    int l = 0, limit = 1;
    for(; limit <= (n - 1) * 2; l++, limit *= 2);
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1 | ((i & 1) << (l - 1)));
    for(int i = 0; i < limit; i++) d[i] = 0;
    Inv(limit / 2, b, d);
    for(int i = 0; i < n; i++) c[i] = a[i];
    for(int i = n; i < limit; i++) c[i] = 0;

    NTT(c, limit, 1); NTT(d, limit, 1);
    for(int i = 0; i < limit; i++) c[i] = c[i] * d[i] % P;
    NTT(c, limit, -1);
     static int inv2 = qpow(2, P - 2);
    for(int i = 0; i < n; i++) b[i] = (b[i] + c[i]) % P * inv2 % P;
    for(int i = n; i < limit; i++) b[i] = 0;
}

当 \([x^0]g(x) \ne 1\) 时，需要用二次剩余来计算 \([x^0]f(x)\)​ ，详见：[链接] 咕咕咕咕咕咕。。。。

两个模板题的区别在于，前者保证 \(a_0=1\) ，后者不保证 \(a_0=1\) 但是保证 \(a_0\) 为模 \(p\) 意义下的二次剩余。

---

3. 多项式除法 & 带余除法

给定多项式 \(f(x),g(x)\) ，求 \(g(x)\) 除 \(f(x)\) 的商 $Q(x) $和余数 \(R(x)\) 。

解法：

考虑构造变换 \[ f^R(x)=x^{\operatorname{deg} f} f\left(\frac{1}{x}\right) \] 观察可知其实质为反转 \(f(x)\) 的系数。

设 \(n=\operatorname{deg} f,~m = \operatorname{deg} g\) （多项式的次数）

将 \(f(x)=Q(x) g(x)+R(x)\) 中的 \(x\) 替换成 \(\frac{1}{x}\) 并将其两边都乘上 \(x^n\) ，得到 \[ \begin{aligned} x^n f\left(\frac{1}{x}\right) & =x^{n-m} Q\left(\frac{1}{x}\right) x^m g\left(\frac{1}{x}\right)+x^{n-m+1} x^{m-1} R\left(\frac{1}{x}\right) \\[6pt] f^R(x) & =Q^R(x) g^R(x)+x^{n-m+1} R^R(x) \end{aligned} \] 注意到上式中 \(R^R(x)\) 的 \(x^{n-m+1}\) ，则将其放到模 \(x^{n-m+1}\) 意义下即可消除 \(R^R(x)\) 带来的影响.

又因为 \(Q^R(x)\) 的次数为 \((n - m) < (n - m + 1)\) ，故 \(Q^R(x)\) 不会受到影响，则 \[ f^R(x) \equiv Q^R(x) g^R(x) \quad\left(\bmod x^{n-m+1}\right) \] 使用多项式求逆即可求出 \(Q(x)\) ，将其反代回去即可得到 \(R(x)\)​ 。

时间复杂度 \(\mathcal{O}(n \log n)\)

完整代码详见 洛谷P4512 【模板】多项式除法 题解

void Div(int n, int m, int *a, int *b, int *ans1, int *ans2)
{
    for(int i = 0; i < m; i++) c[i] = b[i];
    reverse(c, c + m); Inv(n, c, d);

    int l = 0, limit = 1;
    for(; limit <= (n - 1) * 2; l++, limit *= 2);
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));

    for(int i = 0; i < n; i++) c[i] = a[i];
    for(int i = n; i < limit; i++) c[i] = 0;
    reverse(c, c + n);
    
    NTT(c, limit, 1); NTT(d, limit, 1);
    for(int i = 0; i < limit; i++) ans1[i] = c[i] * d[i] % P;
    NTT(ans1, limit, -1);

    reverse(ans1, ans1 + n - m + 1);
    for(int i = 0; i < n - m + 1; i++) c[i] = ans1[i];
    for(int i = n - m + 1; i < limit; i++) c[i] = 0;

    for(int i = 0; i < m; i++) d[i] = b[i];
    for(int i = m; i < limit; i++) d[i] = 0;

    NTT(c, limit, 1); NTT(d, limit, 1);
    for(int i = 0; i < limit; i++) c[i] = c[i] * d[i] % P;
    NTT(c, limit, -1);
    for(int i = 0; i < m - 1; i++) ans2[i] = (a[i] + P - c[i]) % P;
}

---

4. 多项式对数函数 & 指数函数

多项式对数函数

给定整系数多项式 \(f(x)\) ，求 \(g(x)\) 满足 \[ g(x) \equiv \ln f(x) \pmod{x^n} \] 在说明解法之前，我们先证明一个定理。

定理：当且仅当 \([x^0]f(x) = 1\) 时，\(f(x)\) 有对数多项式。

证明：

先证明一个引理。

引理：当 \(\forall x\in \mathbb{Q} ,~x \ne 1\) 有 \(\ln x \not\in \mathbb{Q}\) （\(\mathbb{Q}\) 为有理数集）。

证明：考虑反证法。若 \(c=\ln x\in \mathbb{Q}\) ，则 \(x = \mathrm{e}^c\) ，显然有 \(c \ne 0\) 。

因为 \(\mathrm{e}\) 为超越数，所以 \(\mathrm{e}^{c}\) 对于 \(\forall c \in \mathbb{Q}\) 都有 \(\mathrm{e}^c\not\in \mathbb{Q}\) ，即 \(x \not\in \mathbb{Q}\) ，与假设矛盾。\(\square\)

考虑用先求导再积分的方式获得其对数 \[ \ln f(x) \equiv \int \mathrm{d} \ln f(x) \equiv \int \frac{f^{\prime}(x)}{f(x)}\mathrm{d}x\pmod{x^n} \] 当然这个 \(f(x)\) 显然已经确定了它的构成，那么我们可以写成 \[ \ln f(x) \equiv \int_{0}^x\frac{f^{\prime}(x)}{f(x)}\mathrm{d}x + C \pmod{x^n} \] 其中 \(C=\ln f(0)\)​ 为积分常数。

根据引理，又因为无理数在模意义下无意义，所以 \(f(0) = 1\) 即 \([x^0]f(x)=1\)​ 。

对于除 \([x^0]f(x)\)​ 外的项，显然其导数和积分都为有理数。证毕。

解法：

其实我们刚刚已经推导出了 \[ \ln f(x) \equiv \int \mathrm{d} \ln f(x) \equiv \int \frac{f^{\prime}(x)}{f(x)}\mathrm{d}x\pmod{x^n} \] 这里不熟悉微积分的同学可能没法一眼看出来，那么给个公式提示一下 \[ x^n = nx^{n-1} \\\int x^n \mathrm{~d} x = \frac{x^{n+1}}{n+1}+C \] 因此实际上我们可以 \(\mathcal{O}(n)\) 求导和积分，加上求逆的 \(\mathcal{O}(n \log n)\) ，总时间复杂度为 \(\mathcal{O}(n \log n)\)

完整代码详见 洛谷P4725 【模板】多项式对数函数（多项式 ln） 题解

void Diff(int n, int *a, int *b) // 求导
{
    b[n - 1] = 0;
    for(int i = 1; i < n; i++) b[i - 1] = i * a[i] % P;
}
void Int(int n, int *a, int *b) // 积分
{
    b[0] = 0;
    for(int i = 1; i < n; i++) b[i] = a[i - 1] * qpow(i, P - 2) % P;
}
void Ln(int n, int *a, int *b)
{
    Diff(n, a, c); Inv(n, a, d);
    Mul(n, n, c, d, t); Int(n, t, b); // Mul 是乘法
}

多项式指数函数

给定整系数多项式 \(f(x)\) ，求 \(g(x)\)​ 满足 \[ g(x) \equiv \exp f(x) \pmod{x^n} \] 定理：当且仅当 \([x^0]f(x) = 0\) 时，\(f(x)\) 有指数多项式，否则常数项不收敛。

证明：不知道。但是你想想，是吧，对吧，啊，所以它是对的。

解法：

考虑对 \(\exp f(x)\) 求导 \[ \frac{\mathrm{d} \exp f(x)}{\mathrm{d} x} \equiv \exp f(x) f^{\prime}(x) \pmod{x^n} \] 比较两边系数可得 \[ \begin{aligned} & {\left[x^{n-1}\right] \frac{\mathrm{d} \exp f(x)}{\mathrm{d} x}=\sum_{i=0}^{n-1}\left(\left[x^i\right] \exp f(x)\right)\left(\left[x^{n-i-1}\right] f^{\prime}(x)\right)} \\ & n\left[x^n\right] \exp f(x)=\sum_{i=0}^{n-1}\left(\left[x^i\right] \exp f(x)\right)\left((n-i)\left[x^{n-i}\right] f(x)\right) \end{aligned} \] 考虑分治 FFT ，时间复杂度为 \(\mathcal{O}(n \log^2 n)\)​ 。（听说常数很小？）

代码详见 [链接] 咕咕咕。。。。

当然，用牛顿迭代法可以达到 \(\mathcal{O}(n \log n)\)​ ，本文不打算讲。

---

5. 多项式三角函数

给定多项式 \(f(x)\) ，求模 \(x^n\) 意义下的 \(\sin f(x),\cos f(x), \tan f(x)\)

解法：

由 \(\mathrm{e}^{\mathrm{i} x}=\cos x+\mathrm{i} \sin x\) 可得 \[ \begin{aligned} & \sin x=\frac{\mathrm{e}^{\mathrm{i} x}-\mathrm{e}^{-\mathrm{i} x}}{2 \mathrm{i}} \\ & \cos x=\frac{\mathrm{e}^{\mathrm{i} x}+\mathrm{e}^{-\mathrm{i} x}}{2} \end{aligned} \] 代入 \(f(x)\) ，有 \[ \begin{aligned} \sin f(x) & =\frac{\exp (\mathrm{i} f(x))-\exp (-\mathrm{i} f(x))}{2 \mathrm{i}} \\ \cos f(x) & =\frac{\exp (\mathrm{i} f(x))+\exp (-\mathrm{i} f(x))}{2} \end{aligned} \] 这里因为通常在 \(\mathbb{Z}_{998244353}\) 上做 NTT ，因此 \[ \begin{aligned} \mathrm{i}= & \sqrt{-1} \equiv \sqrt{998244352} \quad(\bmod 998244353) \\ \Longrightarrow \quad \mathrm{i} & \equiv 86583718 \quad(\bmod 998244353) \\ \text { or } \quad \mathrm{i} & \equiv 911660635 \quad(\bmod 998244353) \end{aligned} \] 时间复杂度 \(\mathcal{O}(n \log^2 n)\) 或 \(\mathcal{O}(n \log n)\)

代码详见 [链接] 咕咕咕。。。。

---

6. 多项式反三角函数

给定多项式 \(f(x)\) ，求模 \(x^n\) 意义下的 \(\arcsin f(x),\arccos f(x), \arctan f(x)\)​

解法：

对反三角函数求导再积分可得 \[ \begin{aligned} \frac{\mathrm{d}}{\mathrm{d} x} \arcsin x & =\frac{1}{\sqrt{1-x^2}} \\ \arcsin x & =\int \frac{1}{\sqrt{1-x^2}} \mathrm{~d} x \\ \frac{\mathrm{d}}{\mathrm{d} x} \arccos x & =-\frac{1}{\sqrt{1-x^2}} \\ \arccos x & =-\int \frac{1}{\sqrt{1-x^2}} \mathrm{~d} x \\ \frac{\mathrm{d}}{\mathrm{d} x} \arctan x & =\frac{1}{1+x^2} \\ \arctan x & =\int \frac{1}{1+x^2} \mathrm{~d} x \end{aligned} \] 代入 \(f(x)\) 有 \[ \begin{aligned} \frac{\mathrm{d}}{\mathrm{d} x} \arcsin f(x) & =\frac{f^{\prime}(x)}{\sqrt{1-f^2(x)}} \\ \arcsin f(x) & =\int \frac{f^{\prime}(x)}{\sqrt{1-f^2(x)}} \mathrm{d} x \\ \frac{\mathrm{d}}{\mathrm{d} x} \arccos f(x) & =-\frac{f^{\prime}(x)}{\sqrt{1-f^2(x)}} \\ \arccos f(x) & =-\int \frac{f^{\prime}(x)}{\sqrt{1-f^2(x)}} \mathrm{d} x \\ \frac{\mathrm{d}}{\mathrm{d} x} \arctan f(x) & =\frac{f^{\prime}(x)}{1+f^2(x)} \\ \arctan f(x) & =\int \frac{f^{\prime}(x)}{1+f^2(x)} \mathrm{d} x \end{aligned} \] 时间复杂度 \(\mathcal{O}(n \log n)\)

代码详见 [链接] 咕咕咕。。。。

---

参考文献：

[1] https://en.oi-wiki.org/math/poly/intro/#_5

[2] https://oiwiki.org/math/poly/elementary-func/