多项式ln & exp

给出 latex F(x),求 latex G(x) 满足 latex \ln(F(x))-G(x) \equiv 0 \ (mod\ x^n)

G'(x) \equiv \frac{F'(x)}{F(x)}\\ G(x) \equiv \int \frac{F'(x)}{F(x)} dx

复杂度 latex O(nlogn)


给出 latex F(x),求 latex G(x) 满足 latex e^{F(x)}-G(x) \equiv 0\ (mod\ x^n)

同时取 latex \ln
F(x)-\ln(G(x)) \equiv 0\ (mod\ x^n)

带入牛顿迭代式
\begin{align} G_{t+1}(x) & = G_t(x)-\frac{F(x)-\ln(G_t(x))}{-\frac{1}{G_t(x)}}\ (mod\ {x^{2^{t+1}}}) \\ & = G_t(x)+G_t(x)(F(x)-\ln(G_t(x)))\ (mod\ {x^{2^{t+1}}}) \\ \end{align}

复杂度 latex O(nlogn)

代码实现丑陋,求逆和求 latex \exp 都要先扩到 latex 2 的幂QAQ。

#include <bits/stdc++.h>
using namespace std;
int read() {
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
const int mod = 998244353;
const int G = 3;
const int Max = 300000;
int w[Max], iw[Max], rev[Max], inv[Max];

int qpow(int x, int k) {
    int res = 1;
    for (; k; k >>= 1, x = 1ll * x * x % mod)
        if (k & 1) res = 1ll * res * x % mod;
    return res;
}
void initwn() {
    int iG = qpow(G, mod - 2);
    for (int i = 1; i < Max; i <<= 1) {
        w[i] = qpow(G, (mod - 1) / i);
        iw[i] = qpow(iG, (mod - 1) / i);
    }
}
void initrev(int N, int L) {
    for (int i = 0; i < N; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
}
void fft(int *a, int n, int f) {
    for (int i = 0; i < n; i++)
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int i = 1; i < n; i <<= 1) {
        int wn = (f == 1 ? w[i << 1] : iw[i << 1]);
        for (int j = 0; j < n; j += (i << 1)) {
            int w = 1;
            for (int k = 0; k < i; k++) {
                int x = a[j + k], y = 1ll * a[j + k + i] * w % mod;
                a[j + k] = (x + y) % mod;
                a[j + k + i] = (x - y) % mod;
                w = 1ll * w * wn % mod;
            }
        }
    }
    if (f == -1) {
        int in = qpow(n, mod - 2);
        for (int i = 0; i < n; i++)
            a[i] = 1ll * a[i] * in % mod;
    }
}
void getinv(int deg, int *a, int *b) {
    static int t[Max];
    if (deg == 1) {
        b[0] = qpow(a[0], mod - 2);
        return;
    }
    getinv(deg >> 1, a, b);
    int N = 0, L = 0;
    for (N = 1; N < 2 * deg; N <<= 1) L++;
    initrev(N, L);
    copy(a, a + deg, t);
    fill(t + deg, t + N, 0);
    fft(t, N, 1), fft(b, N, 1);
    for (int i = 0; i < N; i++)
        b[i] = (2ll - 1ll * t[i] * b[i] % mod + mod) % mod * b[i] % mod;
    fft(b, N, -1);
    fill(b + deg, b + Max, 0);
}
void getln(int *a, int *b, int n) {
    static int d[Max], ia[Max], N, L;
    memset(d, 0, sizeof d);
    memset(ia, 0, sizeof ia);
    N = L = 0;
    for (int i = 0; i < n; i++)
        d[i] = 1ll * a[i + 1] * (i + 1) % mod;
    for (N = 1; N < 2 * n; N <<= 1) L++;
    getinv(n, a, ia);
    initrev(N, L);
    fft(d, N, 1), fft(ia, N, 1);
    for (int i = 0; i < N; i++)
        d[i] = 1ll * d[i] * ia[i] % mod;
    fft(d, N, -1);
    for (int i = 1; i < n; i++)
        b[i] = 1ll * d[i - 1] * inv[i] % mod;
}
void getexp(int *a, int *b, int n) {
    static int d[Max];
    if (n == 1) { b[0] = 1; return; }
    getexp(a, b, n >> 1);
    memset(d, 0, sizeof d);
    getln(b, d, n);
    for (int i = 0; i < n; i++)
        d[i] = (a[i] - d[i]) % mod;
    d[0] = (d[0] + 1) % mod;
    int N = 0, L = 0;
    for (N = 1; N <= n; N <<= 1) L++;
    assert(N == 2 * n);
    initrev(N, L);
    fft(d, N, 1), fft(b, N, 1);
    for (int i = 0; i < N; i++)
        b[i] = 1ll * b[i] * d[i] % mod;
    fft(b, N, -1);
    fill(b + n, b + N, 0);
}

int n, f[Max], g[Max];

int main() {
    initwn();
    inv[1] = 1;
    for (int i = 2; i < Max; i++)
        inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
    n = read();
    for (int i = 0; i < n; i++)
        f[i] = read();
    int N = 0, L = 1;
    for (N = 1; N <= n; N <<= 1) L++;
    getexp(f, g, N);
    for (int i = 0; i < n; i++)
        printf("%d ", (g[i] + mod) % mod);
    return 0;
}

发表评论

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