洛谷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;
}