洛谷P4725 【模板】多项式对数函数（多项式 ln）题解

题意：

给出 $n-1$ 次多项式 $A(x)$，求一个 $\bmod{\:x^n}$ 下的多项式 $B(x)$，满足 $B(x) \equiv \ln A(x)$ 。

在模 $998244353$ 意义下进行，且 $a_i \in [0, 998244353) \cap \mathbb{Z}$ 。保证 $a_0 = 1$ 。

输入格式：

第一行一个整数 $n$ 。

下一行有 $n$ 个整数，依次表示多项式的系数 $a_0, a_1, \cdots, a_{n-1}$ 。

输出格式：

输出 $n$ 个整数，表示答案多项式中的系数 $a_0, a_1, \cdots, a_{n-1}$ 。

数据范围：

对于 $100\%$ 的数据，$1\le n \le 10^5$ 。

给定整系数多项式 $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)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1048576 + 15))

const int P = 998244353;
const int G = 3, Gi = 332748118;
int a[N], b[N], c[N], d[N], t[N], r[N];
int qpow(int a, int b)
{
    int r = 1;
    while(b)
    {
        if(b & 1) r = r * a % P;
        b >>= 1; a = a * a % P;
    }
    return r;
}
void NTT(int *A, int limit, int type)
{
    for(int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid *= 2)
    {
        int Wn = qpow((type == 1 ? G : Gi), (P - 1) / (mid * 2));
        for(int j = 0; j < limit; j += (mid * 2))
        {
            int w = 1;
            for(int k = 0; k < mid; k++, w = (w * Wn) % P)
            {
                int 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;
            }
        }
    }
    if(type == -1)
    {
        int Inv = qpow(limit, P - 2);
        for(int i = 0; i < limit; i++) A[i] = A[i] * Inv % P;
    }
}
void Mul(int n, int m, int *a, int *b, int *ans)
{
    int l = 0, limit = 1;
    for(; limit <= (n - 1) + (m - 1); l++, limit *= 2);
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));

    NTT(a, limit, 1); NTT(b, limit, 1);
    for(int i = 0; i < limit; i++) ans[i] = a[i] * b[i] % P;
    NTT(ans, limit, -1);
}
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++) t[i] = a[i];
    for(int i = n; i < limit; i++) t[i] = 0;
    NTT(t, limit, 1); NTT(b, limit, 1);
    for(int i = 0; i < limit; i++)
        b[i] = (2 - t[i] * b[i] % P + P) % P * b[i] % P;
    NTT(b, limit, -1);
    for(int i = n; i < limit; i++) b[i] = 0;
    for(int i = 0; i < limit; i++) t[i] = 0;
}
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);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n;
    for(int i = 0, x; i < n; i++) cin >> x, a[i] = (x + P) % P;
    Ln(n, a, b);
    for(int i = 0; i < n; i++) cout << b[i] << " \n"[i == n - 1];
    return 0;
}