半在线卷积实现多项式ln求助
查看原帖
半在线卷积实现多项式ln求助
86409
FifthAxiom楼主2022/1/13 00:08
G=lnFG=FFdxGF=Fngn=(n+1)fnk1gnkfk\begin{aligned} G&=\ln F\\ \Leftrightarrow& G=\int \dfrac{F'}{F} dx\\ \Leftrightarrow& G'F=F'\\ \Leftrightarrow& ng_n=(n+1)f_n-\sum_{k\ge 1}g_{n-k}f_k \end{aligned}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define cpy(a, b, n) memcpy(a, b, sizeof(LL)*(n))
#define clr(a, n) memset(a, 0, sizeof(LL)*(n))

using namespace std;

typedef long long LL;

const int N = 200010, P = 998244353;

int n;
LL A[N], ln[N];
int rev[N];
LL fac[N], inv[N];

void build(int n) {
    fac[0] = 1;
    inv[1] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % P;
    for (int i = 2; i <= n; i++)
        inv[i] = (P - P / i) * inv[P % i] % P;
}

LL power(LL a, LL b) {
    LL res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % P;
        a = a * a % P;
    }
    return res;
}

const LL invR = power(3, P - 2);

int calcrev(int n) {
    int bit = 0;
    while ((1 << bit) < n) bit++;
    int tot = 1 << bit;
    for (int i = 0; i < tot; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    return tot;
}

void ntt(LL a[], int op, int tot) {
    for (int i = 0; i < tot; i++)
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int mid = 1; mid < tot; mid <<= 1) {
        LL on = power((op == 1) ? 3 : invR, (P - 1) / (mid << 1));
        for (int i = 0; i < tot; i += mid << 1) {
            LL o = 1;
            for (int j = 0; j < mid; j++, o = o * on % P) {
                LL x = a[i + j], y = o * a[i + mid + j] % P;
                a[i + j] = (x + y) % P;
                a[i + mid + j] = (x - y + P) % P;
            }
        }
    }
    if (op == -1) {
        LL invn = power(tot, P - 2);
        for (int i = 0; i < tot; i++) a[i] = a[i] * invn % P;
    }
}

LL a[N], b[N];
void src(LL f[], LL g[], int l, int r) {
    if (l == r) {
        if (!l) f[l] = 1;
        else f[l] = inv[l] * ((l + 1) * g[l] % P - f[l] + P) % P;
        return;
    }
    
    int mid = l + r >> 1;
    src(f, g, l, mid);
    int tot = calcrev(r - l + 1);
    cpy(a, f + l, mid - l + 1), cpy(b, g, r - l + 1);
    clr(a + mid - l + 1, tot - mid + l), clr(b + r - l + 1, tot - r + l);
    ntt(a, 1, tot), ntt(b, 1, tot);
    for (int i = 0; i < tot; i++) a[i] = a[i] * b[i] % P;
    ntt(a, -1, tot);
    for (int i = mid + 1; i <= r; i++) f[i] = (f[i] + a[i - l]) % P;
    printf("%d %d %d\n", l, r, tot);
    for (int i = l; i <= r; i++) printf("%lld ", f[i]);
    puts("\n");
    src(f, g, mid + 1, r);
}

bool polyln(LL res[], LL a[], int n) {
    if (a[0] != 1) return 0;
    src(res, a, 0, n);
    res[0] = 0;
    return 1;
}

int main() {
    build(N >> 1);
    scanf("%d", &n);
    n--;
    for (int i = 0; i <= n; i++) scanf("%lld", &A[i]);
    polyln(ln, A, n);
    for (int i = 0; i <= n; i++) printf("%lld ", ln[i]);
    return 0;
}

我在做多项式ln样例时发现前三项都是正确的,求大佬帮调

2022/1/13 00:08
加载中...