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

Simulated_annealing · 2026-04-26 18:09:20 · 题解

【模板】多项式对数函数（多项式 ln）

算法介绍

前置知识

多项式函数求导

将每一项分开求导。

多项式函数积分

将每一项分开积分。

求定积分就只需要求

特别地

多项式 ln

首先，多项式 ln 的结果不是多项式，而是无穷级数。 而且，众所周知，无穷级数截断可以得到多项式。 现有一多项式 f(x)，则 \ln f(x) 可以先求导再积分表示为

根据复合函数求导法则 f(g(x))^\prime = f^\prime(g(x)) g^\prime(x)

因为有截断，所以直接用多项式乘法逆，如果除法就变成无穷级数了。

令 g(x) f(x) \equiv 1 \pmod{x^n}

然后求导，求逆，再积分就可以了。

在本题中因为 a_0 = 1， 所以 f(0) = 1，原式可以进一步化简为

但是，在模意义下且 a_0 \not= 1,\ a_0 \in \mathbb{Q} 时，\ln f(x) 是无意义的，因为 \ln f(0) 是无理数。

:::info[证明]{open}

Part 1：证明 e 是超越数

1. 泰勒级数展开：e 的泰勒级数在 x=1 处的展开式为：e = \sum_{n=0}^{\infty} \frac{1}{n!} = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots
2. 假设 e 为有理数：设 e 为两个互质的正整数 p 和 q 的比值，即（e = \frac{p}{q}）。
3. 推导矛盾：将 e 的泰勒级数乘以 q!：q! \cdot e = q! \left(1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots\right) = q! + \frac{q!}{1!} + \frac{q!}{2!} + \cdots + \frac{q!}{(q-1)!} + \frac{q!}{q!} + \frac{1}{q+1} + \frac{1}{(q+1)(q+2)} + \cdots 注意到左侧是整数（因为每一项都是整数），而右侧的前 q+1 项也是整数，但后面的项构成了一个正的分数序列之和，因此右侧大于一个整数加上某个正小数。所以，右侧不是整数，这与我们的假设矛盾。
4. 结论：由于我们找到了矛盾，所以原假设不成立，即 e 不能表示为两个互质整数的比值，因此 e 是无理数。摘自 百度

Part 2：证明 e^k 是超越数（k \in \mathbb{Q}）

证明超越数的有理数次幂是超越数：关于超越数的一些性质和推论

显然 e 是超越数。

Part 3：证明 \ln a 是无理数（a \in \mathbb{Q},\ a \not= 1）

命题：若 a 是不等于 1 的正有理数，则 \ln a 为无理数。

证明： 采用反证法。 设 a 为正有理数且 a \neq 1，假设 \ln a 是有理数，记

两边同时取自然指数：

因为 a 是正有理数，故 a^q 仍为正有理数； 又 a \neq 1，故 p \neq 0，即 p 为非零整数。

由结论：非零整数次幂的 e^p 是超越数，从而必为无理数。 于是左边 a^q \in \mathbb{Q}，右边 e^p \notin \mathbb{Q}，矛盾。

因此假设不成立，故 \ln a 为无理数。 （来自豆包） :::

正确性证明 & 复杂度分析

算法正确性显然。

对于复杂度分析：

1. 求导是 \mathcal O(n) 的
2. 求逆是 \mathcal O(n \log n) 的
3. 乘法是 \mathcal O(n \log n) 的
4. 积分是 \mathcal O(n) 的

所以总和是 \mathcal O(n) + \mathcal O(n \log n) + \mathcal O(n \log n) + \mathcal O(n) = \mathcal O(n \log n) 的，但常数比较大。

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 4e5 + 50;

ll qpow(ll a, ll b, ll p) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

ll inv(ll a, ll p) {
    return qpow(a, p - 2, p);
}

namespace Poly {
    constexpr ll P = 998244353, g = 3;
    namespace NTT {
        int r[N];
        int getbit(int x) {
            int bit = 0;
            while ((1 << bit) < x) ++bit;
            return bit;
        }
        void init(int bit) {
            for (int i = 0; i < (1 << bit); ++i) {
                r[i] = (r[i >> 1] >> 1) | ((i & 1) << (bit - 1));
            }
        }
        void NTT(ll *a, int bit, int op) {
            for (int i = 0; i < (1 << bit); ++i) {
                if (r[i] < i) swap(a[r[i]], a[i]);
            }
            for (int mid = 1; mid < (1 << bit); mid <<= 1) {
                ll _w = qpow(op ? g : inv(g, P), (P - 1) / (mid << 1), P);
                for (int i = 0; i < (1 << bit); i += (mid << 1)) {
                    ll wk = 1;
                    for (int j = 0; j < mid; ++j, wk = wk * _w % P) {
                        ll x = a[i + j], y = wk * a[i + j + mid] % P;
                        a[i + j] = (x + y) % P;
                        a[i + j + mid] = (x - y) % P;
                    }
                }
            }
        }
    }
    namespace Mul {
        ll p[N], q[N];
        void Mul(ll *a, ll *b, int n) {
            int bit = NTT::getbit(n);
            NTT::init(bit);
            for (int i = 0; i < n; ++i) {
                p[i] = a[i] % P;
                q[i] = b[i] % P;
            }
            for (int i = n; i < (1 << bit); ++i) {
                p[i] = q[i] = 0;
            }
            NTT::NTT(p, bit, 1);
            NTT::NTT(q, bit, 1);
            for (int i = 0; i < (1 << bit); ++i) {
                p[i] = p[i] * q[i] % P;
            }
            NTT::NTT(p, bit, 0);
            ll r = inv(1 << bit, P);
            for (int i = 0; i < n; ++i) {
                a[i] = (p[i] * r % P + P) % P;
            }
        }
    }
    namespace Inv {
        ll tmp[N], g[N];
        void Inv(ll *a, int n) {
            for (int i = 0; i < (n << 1); ++i) {
                tmp[i] = g[i] = 0;
            }
            int m = 1;
            g[0] = qpow(a[0], P - 2, P);
            while (m <= n) {
                int cur = m << 1;
                for (int i = 0; i < cur; ++i) {
                    tmp[i] = a[i];
                }
                Mul::Mul(tmp, g, cur << 1);
                for (int i = cur; i < (cur << 1); ++i) {
                    tmp[i] = 0;
                }
                for (int i = 0; i < cur; ++i) {
                    tmp[i] = -tmp[i];
                }
                tmp[0] = (tmp[0] + 2) % P;
                Mul::Mul(g, tmp, cur << 1);
                for (int i = cur; i < (cur << 1); ++i) {
                    g[i] = 0;
                }
                m = cur;
            }
            for (int i = 0; i < n; ++i) {
                a[i] = g[i];
            }
        }
    }
    namespace Der {
        void Der(ll *a, int n) {
            for (int i = 1; i < n; ++i) {
                a[i - 1] = a[i] * i % P;
            }
            a[n - 1] = 0;
        }
    }
    namespace Int {
        void Int(ll *a, int n) {
            for (int i = n - 1; i >= 1; --i) {
                a[i] = a[i - 1] * inv(i, P) % P;
            }
            a[0] = 0;
        }
    }
    namespace ln {
        ll f[N], g[N];
        void ln(ll *a, int n) {
            for (int i = 0; i < n; ++i) {
                g[i] = f[i] = a[i];
            }
            Der::Der(f, n);
            Inv::Inv(g, n);
            Mul::Mul(f, g, n << 1);
            Int::Int(f, n);
            for (int i = 0; i < n; ++i) {
                a[i] = f[i];
            }
        }
    }
}

using namespace Poly;
ll a[N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &a[i]);
    }
    ln::ln(a, n);
    for (int i = 0; i < n; ++i) {
        printf("%lld ", a[i]);
    }
    return 0;
}