Wiki › Thuật toán › Toán học › Phép toán trên chuỗi lũy thừa (nghịch đảo, log, exp, chia đa thức)

Phép toán trên chuỗi lũy thừa (nghịch đảo, log, exp, chia đa thức)

Nghịch đảo chuỗi, chia đa thức có dư, ln, exp, lũy thừa, căn bậc hai và tính giá trị nhiều điểm trong O(n log n) bằng lặp Newton gấp đôi độ chính xác trên NTT modulo 998244353, kèm thư viện C++ đã kiểm thử.

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 25 phút 4 lượt xem

Nhiều bài đếm quy về việc lấy hệ số của một chuỗi lũy thừa hình thức (formal power series) A(x)=a0+a1x+a2x2+⋯ sau khi đã nhân, chia, lấy logarit hay lũy thừa. Nếu chỉ có phép nhân đa thức bằng FFT/NTT thì những phép còn lại vẫn phải làm bằng truy hồi O(n2). Trang này trình bày bộ công cụ chuẩn: nghịch đảo chuỗi 1/A, chia đa thức có dư, đạo hàm, tích phân, lnA, expA, Am, A và tính giá trị đa thức tại nhiều điểm. Tất cả đều lấy theo modulo xn và modulo 998244353, chạy trong O(nlogn) (riêng tính giá trị nhiều điểm là O(nlog2n)) thay vì O(n2).

Mọi phép đều dựa trên một ý duy nhất: lặp Newton gấp đôi độ chính xác. Biết đáp án đúng tới xℓ, một phép nhân đa thức cho đáp án đúng tới x2ℓ.

Ý tưởng / Trực giác

Vì sao chuỗi lũy thừa lại "chia" được

Trong vành chuỗi lũy thừa hình thức, ta không quan tâm x là số bao nhiêu, chỉ quan tâm dãy hệ số. Vì vậy "B=1/Amodxn" nghĩa là tìm b0,…,bn−1 sao cho A·B=1+(các số hạng bậc≥n). So sánh hệ số:

a0b0=1,∑k=0iakbi−k=0(i≥1).

Cách giải ngây thơ đọc thẳng từ đây: bi=−a0−1∑k=1iakbi−k, mất O(n2). Nghịch đảo tồn tại khi và chỉ khi a0≠0 (modulo p). Ví dụ quen thuộc: 11−x−x2=1+x+2x2+3x3+5x4+⋯ là hàm sinh của dãy Fibonacci (xem Hàm sinh).

Lặp Newton cho nghịch đảo

Giả sử đã có B với AB≡1(modxℓ). Đặt sai số E=1−AB; E chia hết cho xℓ. Lấy

B′=B(2−AB)=B(1+E).

Khi đó

1−AB′=1−(1−E)(1+E)=E2,

mà E2 chia hết cho x2ℓ. Nghĩa là sau một bước, số hệ số đúng tăng gấp đôi. Bắt đầu từ B=a0−1 (đúng tới x1), sau ⌈log2n⌉ bước ta có đủ n hệ số. Đây chính là phương pháp Newton tìm nghiệm của F(B)=1/B−A=0: B′=B−F(B)/F′(B)=B−(1/B−A)·(−B2)=B(2−AB).

Điểm mấu chốt về độ phức tạp: ở bước đưa độ chính xác từ ℓ lên 2ℓ chỉ cần Amodx2ℓ và B có ℓ hệ số, nên chi phí là O(ℓlogℓ). Tổng

T(n)=T(n/2)+O(nlogn)=O(nlogn),

vì nlogn+n2logn2+⋯≤2nlogn. Cả trang này đều dùng lập luận gấp đôi đó.

Chia đa thức có dư

Cho A bậc n−1 (có n hệ số) và B bậc m−1 (bm−1≠0), cần A=QB+R với degQ=n−m, degR<m−1. Ký hiệu đảo hệ số AR(x)=xn−1A(1/x) (viết dãy hệ số theo thứ tự ngược). Thay x→1/x vào đẳng thức rồi nhân với xn−1:

AR=QRBR+xn−m+1RR.

Số hạng cuối chia hết cho xn−m+1, nên QR≡AR·(BR)−1(modxn−m+1). Nghịch đảo BR tồn tại vì hệ số tự do của nó là bm−1≠0. Có Q thì R=A−QB. Tổng chi phí: một nghịch đảo và hai phép nhân, O(nlogn).

Đạo hàm, tích phân, logarit

Đạo hàm và tích phân hình thức làm từng hệ số: (∑aixi)′=∑iaixi−1 và ∫∑aixi=∑aii+1xi+1, đều O(n).

Với a0=1, định nghĩa lnA=∫A′A (hằng số tích phân bằng 0 để ln1=0). Công thức này đúng như giải tích thông thường, và nó chỉ cần một nghịch đảo, một phép nhân, một đạo hàm, một tích phân: O(nlogn). Điều kiện a0=1 là bắt buộc: ln của hằng số a0≠1 không xác định trong ℤp, nên nếu a0≠1 thì chia cả chuỗi cho a0 trước.

Exp bằng Newton

Với a0=0, expA=∑k≥0Ak/k!. Ta tìm B thoả F(B)=lnB−A=0. Vì F′(B)=1/B, bước Newton là

B′=B−lnB−A1/B=B(1−lnB+A)(modx2ℓ).

Cùng lập luận như nghịch đảo: sai số lnB−A chia hết cho xℓ thì sau bước sai số chia hết cho x2ℓ. Mỗi bước tốn một ln (tức một nghịch đảo) cỡ 2ℓ và một phép nhân, nên vẫn T(n)=T(n/2)+O(nlogn)=O(nlogn), nhưng hằng số lớn (cỡ 10 đến 20 lần một phép nhân). Điều kiện a0=0 cũng bắt buộc: exp(a0) của hằng số khác 0 không có nghĩa trong ℤp.

Lũy thừa Am, kể cả khi A bắt đầu bằng các hệ số 0

Nếu a0=1 thì Am=exp(mlnA), và m chỉ cần lấy modulo p (vì m chỉ xuất hiện như một hệ số nhân). Trường hợp tổng quát: gọi k là chỉ số nhỏ nhất có ak≠0, viết

A=akxk·C(x),C(0)=1⟹Am=akmxkmexp(mlnC).

Nếu km≥n thì kết quả modulo xn toàn 0. Chú ý dùng m thật cho phép so sánh km≥n, dùng mmodp cho hệ số trong exp, còn akm tính bằng lũy thừa nhanh (số mũ có thể rút về mmod(p−1)).

Căn bậc hai

Với a0=1, giải B2=A bằng Newton: B′=12(B+AB)modx2ℓ, mỗi bước một nghịch đảo và một phép nhân, vẫn O(nlogn). Nếu a0≠1 thì cần a0 là số chính phương modulo p (tìm căn bằng Tonelli-Shanks) và số hệ số 0 ở đầu phải chẵn.

Tính giá trị tại nhiều điểm (sơ lược)

Muốn tính f(x1),…,f(xn): ta có f(xi)=fmod(x−xi). Dựng cây tích con (subproduct tree): lá là (x−xi), mỗi nút là tích hai con, tốn O(nlog2n). Đi từ gốc xuống, tại mỗi nút thay f bằng fmod(đa thức của nút) (chia có dư ở trên), tới lá thì phần dư là một hằng số, chính là f(xi). Mỗi tầng tổng bậc là O(n), có logn tầng, nên tổng cộng O(nlog2n). Bài toán ngược (nội suy từ n điểm) dùng cùng cây này; xem thêm Nội suy Lagrange.

Ví dụ chạy tay

Nghịch đảo A=1−x−x2 tới x8

Bắt đầu B1=1 (vì a0=1). Mỗi bước tính ABmodx2ℓ, rồi B·(2−AB):

bước ℓ→2ℓ ABmodx2ℓ B mới modx2ℓ
1 1→2 1−x 1·(1+x)=1+x
2 2→4 (1−x−x2)(1+x)≡1−2x2−x3 (1+x)(1+2x2+x3)≡1+x+2x2+3x3
3 4→8 (1−x−x2)(1+x+2x2+3x3)=1−5x4−3x5 (1+x+2x2+3x3)(1+5x4+3x5)≡1+x+2x2+3x3+5x4+8x5+13x6+21x7

Quan sát cột thứ ba: sau bước 2, AB đúng bằng 1 ở mọi bậc nhỏ hơn 4, sai số E=−5x4−3x5 bắt đầu từ x4. Bước 3 sửa đúng 4 hệ số tiếp theo. Dãy hệ số là Fibonacci, khớp với output inv: 1 1 2 3 5 8 13 21 của chương trình bên dưới.

array base=0
1 0 0 0 0 0 0 0
step B ban đầu: chỉ hệ số 0 đúng
highlight green 0
step Sau bước 1: đúng 2 hệ số
set 1 1
highlight green 1
step Sau bước 2: đúng 4 hệ số
set 2 2
set 3 3
highlight green 2..3
step Sau bước 3: đúng 8 hệ số (Fibonacci)
set 4 5
set 5 8
set 6 13
set 7 21
highlight green 4..7
Chia có dư: (x4+3x3+2x+5):(x2+1)

n=5, m=3, cần n−m+1=3 hệ số của QR.

  • AR=1+3x+0x2+2x3+5x4, BR=1+0x+x2.
  • (BR)−1modx3=1−x2.
  • QR=AR(1−x2)modx3=1+3x−x2, đảo lại Q=x2+3x−1.
  • R=A−QB=(x4+3x3+2x+5)−(x4+3x3+3x−1)=6−x.

Chương trình in quotient: 998244352 3 1 và remainder: 6 998244352 (vì −1≡998244352).

Đồ thị có nhãn liên thông bằng ln

Số đồ thị có nhãn n đỉnh là gn=2(n2). Mỗi đồ thị là một tập các thành phần liên thông có nhãn, nên với hàm sinh mũ G(x)=∑gnxnn! và C(x)=∑cnxnn! (cn là số đồ thị liên thông) ta có G=exp(C), tức C=lnG:

n 0 1 2 3 4 5 6
gn=2(n2) 1 1 2 8 64 1024 32768
cn=n![xn]lnG 0 1 1 4 38 728 26704

Kiểm tra n=3: trong 8 đồ thị trên 3 đỉnh, bị loại là đồ thị rỗng (1) và đồ thị có đúng một cạnh (3), còn 4 đồ thị liên thông.

Số phân hoạch bằng nghịch đảo

Hàm sinh số phân hoạch là ∏k≥111−xk. Theo định lý số ngũ giác Euler, mẫu số là

∏k≥1(1−xk)=1+∑k≥1(−1)k(xk(3k−1)/2+xk(3k+1)/2)=1−x−x2+x5+x7−x12−x15+⋯,

chỉ có O(n) hệ số khác 0 dưới xn. Một lần nghịch đảo cho p(0),…,p(n−1) trong O(nlogn); với n=11 chương trình in partitions: 1 1 2 3 5 7 11 15 22 30 42.

Cài đặt

Thư viện C++ dưới đây gồm ntt, multiply, inverse, derivative, integral, logarithm, exponent, pow_series, sqrt_series, divmod và multipoint. Mọi hàm nhận và trả về vector<long long> hệ số từ bậc 0, tham số n là số hệ số cần giữ (tức modulo xn). Hàm main chạy các ví dụ ở trên.

Bản Python chỉ cài nghịch đảo. NTT viết bằng Python thuần rất chậm: trên máy thử, n=104 mất khoảng 1,5 giây và n=105 mất vài chục giây, nên chỉ dùng để học hoặc với n nhỏ; đi thi hãy dùng C++.

C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> poly;
const ll MOD = 998244353, G = 3;

ll power(ll b, ll e) {
    ll r = 1; b %= MOD; if (b < 0) b += MOD;
    for (; e > 0; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

// In-place NTT, size of a must be a power of two.
void ntt(poly &a, bool invert) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        ll w = power(G, (MOD - 1) / len);
        if (invert) w = power(w, MOD - 2);
        for (int i = 0; i < n; i += len) {
            ll wn = 1;
            for (int j = 0; j < len / 2; j++) {
                ll u = a[i + j], v = a[i + j + len / 2] * wn % MOD;
                a[i + j] = u + v < MOD ? u + v : u + v - MOD;
                a[i + j + len / 2] = u - v >= 0 ? u - v : u - v + MOD;
                wn = wn * w % MOD;
            }
        }
    }
    if (invert) {
        ll inv_n = power(n, MOD - 2);
        for (ll &x : a) x = x * inv_n % MOD;
    }
}

poly multiply(poly a, poly b) {
    if (a.empty() || b.empty()) return {};
    int need = a.size() + b.size() - 1, n = 1;
    if (min(a.size(), b.size()) <= 32) {  // small case: schoolbook is faster
        poly c(need, 0);
        for (size_t i = 0; i < a.size(); i++)
            for (size_t j = 0; j < b.size(); j++)
                c[i + j] = (c[i + j] + a[i] * b[j]) % MOD;
        return c;
    }
    while (n < need) n <<= 1;
    a.resize(n); b.resize(n);
    ntt(a, false); ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

poly trunc(poly a, int n) { a.resize(n, 0); return a; }

// B = 1/A mod x^n, requires A[0] != 0.
poly inverse(const poly &a, int n) {
    poly b = {power(a[0], MOD - 2)};
    for (int len = 1; len < n; len <<= 1) {
        // B <- B * (2 - A*B) mod x^(2len)
        poly ab = trunc(multiply(trunc(a, 2 * len), b), 2 * len);
        for (ll &x : ab) x = (MOD - x) % MOD;
        ab[0] = (ab[0] + 2) % MOD;
        b = trunc(multiply(b, ab), 2 * len);
    }
    return trunc(b, n);
}

poly derivative(const poly &a) {
    if (a.size() <= 1) return {};
    poly d(a.size() - 1);
    for (size_t i = 1; i < a.size(); i++) d[i - 1] = a[i] * (ll)i % MOD;
    return d;
}

poly integral(const poly &a) {
    poly r(a.size() + 1, 0);
    for (size_t i = 0; i < a.size(); i++) r[i + 1] = a[i] * power(i + 1, MOD - 2) % MOD;
    return r;
}

// ln A mod x^n, requires A[0] == 1.
poly logarithm(const poly &a, int n) {
    poly q = multiply(derivative(trunc(a, n)), inverse(a, n));
    return trunc(integral(trunc(q, n - 1)), n);
}

// exp A mod x^n, requires A[0] == 0.
poly exponent(const poly &a, int n) {
    poly b = {1};
    for (int len = 1; len < n; len <<= 1) {
        // B <- B * (1 - ln B + A) mod x^(2len)
        poly t = logarithm(b, 2 * len);
        for (int i = 0; i < 2 * len; i++) {
            ll ai = i < (int)a.size() ? a[i] : 0;
            t[i] = ((ai - t[i]) % MOD + MOD) % MOD;
        }
        t[0] = (t[0] + 1) % MOD;
        b = trunc(multiply(b, t), 2 * len);
    }
    return trunc(b, n);
}

// A^m mod x^n for any m >= 0 (A[0] may be 0).
poly pow_series(const poly &a, ll m, int n) {
    int k = 0;
    while (k < (int)a.size() && a[k] == 0) k++;
    if (m == 0) { poly r(n, 0); r[0] = 1; return r; }
    if (k == (int)a.size() || (__int128)k * m >= n) return poly(n, 0);
    int shift = k * m, len = n - shift;
    ll c = a[k], inv_c = power(c, MOD - 2);
    poly b(len, 0);  // b = A / (c x^k), so b[0] = 1
    for (int i = 0; i < len && k + i < (int)a.size(); i++) b[i] = a[k + i] * inv_c % MOD;
    poly l = logarithm(b, len);
    for (ll &x : l) x = x * (m % MOD) % MOD;
    poly e = exponent(l, len);
    ll cm = power(c, m);  // exponent of a constant: Fermat, m mod (MOD-1) also fine
    poly r(n, 0);
    for (int i = 0; i < len; i++) r[shift + i] = e[i] * cm % MOD;
    return r;
}

// sqrt A mod x^n, assumes A[0] == 1.
poly sqrt_series(const poly &a, int n) {
    poly b = {1};
    ll inv2 = (MOD + 1) / 2;
    for (int len = 1; len < n; len <<= 1) {
        // B <- (B + A/B) / 2 mod x^(2len)
        poly t = trunc(multiply(trunc(a, 2 * len), inverse(b, 2 * len)), 2 * len);
        b.resize(2 * len, 0);
        for (int i = 0; i < 2 * len; i++) b[i] = (b[i] + t[i]) * inv2 % MOD;
    }
    return trunc(b, n);
}

// A = Q*B + R with deg R < deg B. B must have nonzero leading coefficient.
pair<poly, poly> divmod(poly a, poly b) {
    int n = a.size(), m = b.size();
    if (n < m) return {{}, a};
    poly ra(a.rbegin(), a.rend()), rb(b.rbegin(), b.rend());
    int qlen = n - m + 1;
    poly q = trunc(multiply(trunc(ra, qlen), inverse(rb, qlen)), qlen);
    reverse(q.begin(), q.end());
    poly qb = multiply(q, b), r(m - 1);
    for (int i = 0; i < m - 1; i++) r[i] = ((a[i] - qb[i]) % MOD + MOD) % MOD;
    return {q, r};
}

// Multipoint evaluation via subproduct tree, O(n log^2 n).
void build(vector<poly> &tree, const poly &xs, int v, int l, int r) {
    if (r - l == 1) { tree[v] = {(MOD - xs[l]) % MOD, 1}; return; }
    int mid = (l + r) / 2;
    build(tree, xs, 2 * v, l, mid);
    build(tree, xs, 2 * v + 1, mid, r);
    tree[v] = multiply(tree[2 * v], tree[2 * v + 1]);
}
void evaluate(const vector<poly> &tree, const poly &f, int v, int l, int r, poly &out) {
    poly rem = divmod(f, tree[v]).second;  // f mod prod_{i in [l,r)} (x - x_i)
    if (r - l == 1) { out[l] = rem.empty() ? 0 : rem[0]; return; }
    int mid = (l + r) / 2;
    evaluate(tree, rem, 2 * v, l, mid, out);
    evaluate(tree, rem, 2 * v + 1, mid, r, out);
}
poly multipoint(const poly &f, const poly &xs) {
    int n = xs.size();
    vector<poly> tree(4 * n);
    build(tree, xs, 1, 0, n);
    poly out(n);
    evaluate(tree, f, 1, 0, n, out);
    return out;
}

void print(const string &name, const poly &a) {
    cout << name << ":";
    for (ll x : a) cout << ' ' << x;
    cout << '\n';
}
int main() {
    // 1 / (1 - x - x^2): Fibonacci numbers
    print("inv", inverse({1, MOD - 1, MOD - 1}, 8));
    // partition numbers: 1 / prod (1 - x^k), via Euler's pentagonal series
    int n = 11;
    poly pent(n, 0);
    pent[0] = 1;
    for (ll k = 1; k * (3 * k - 1) / 2 < n; k++) {
        ll sign = (k % 2 ? MOD - 1 : 1);  // (-1)^k
        pent[k * (3 * k - 1) / 2] = sign;
        if (k * (3 * k + 1) / 2 < n) pent[k * (3 * k + 1) / 2] = sign;
    }
    print("partitions", inverse(pent, n));
    // connected labeled graphs: n! [x^n] ln( sum 2^C(n,2) x^n / n! )
    int m = 7;
    poly fact(m, 1), g(m);
    for (int i = 1; i < m; i++) fact[i] = fact[i - 1] * i % MOD;
    for (int i = 0; i < m; i++) g[i] = power(2, (ll)i * (i - 1) / 2) * power(fact[i], MOD - 2) % MOD;
    poly c = logarithm(g, m);
    for (int i = 0; i < m; i++) c[i] = c[i] * fact[i] % MOD;
    print("connected", c);
    // division: (x^4 + 3x^3 + 2x + 5) / (x^2 + 1)
    auto [q, r] = divmod({5, 2, 0, 3, 1}, {1, 0, 1});
    print("quotient", q);
    print("remainder", r);
    // pow with leading zero: (x + x^2)^3 mod x^8
    print("pow", pow_series({0, 1, 1}, 3, 8));
    // multipoint: f = 1 + 2x + 3x^2 at 0,1,2,3
    print("eval", multipoint({1, 2, 3}, {0, 1, 2, 3}));
}
Python
MOD = 998244353
G = 3


def ntt(a, invert):
    n = len(a)
    j = 0
    for i in range(1, n):  # bit-reversal permutation
        bit = n >> 1
        while j & bit:
            j ^= bit
            bit >>= 1
        j ^= bit
        if i < j:
            a[i], a[j] = a[j], a[i]
    length = 2
    while length <= n:
        w = pow(G, (MOD - 1) // length, MOD)
        if invert:
            w = pow(w, MOD - 2, MOD)
        half = length // 2
        ws = [1] * half
        for k in range(1, half):
            ws[k] = ws[k - 1] * w % MOD
        for i in range(0, n, length):
            for k in range(half):
                u = a[i + k]
                v = a[i + k + half] * ws[k] % MOD
                a[i + k] = (u + v) % MOD
                a[i + k + half] = (u - v) % MOD
        length <<= 1
    if invert:
        inv_n = pow(n, MOD - 2, MOD)
        for i in range(n):
            a[i] = a[i] * inv_n % MOD


def multiply(a, b):
    need = len(a) + len(b) - 1
    n = 1
    while n < need:
        n <<= 1
    fa = a + [0] * (n - len(a))
    fb = b + [0] * (n - len(b))
    ntt(fa, False)
    ntt(fb, False)
    for i in range(n):
        fa[i] = fa[i] * fb[i] % MOD
    ntt(fa, True)
    return fa[:need]


def inverse(a, n):
    """Return B with A*B = 1 mod x^n. Requires a[0] != 0."""
    a = a[:n] + [0] * (n - len(a))
    b = [pow(a[0], MOD - 2, MOD)]
    length = 1
    while length < n:
        length *= 2
        # B <- B * (2 - A*B) mod x^length
        ab = multiply(a[:length], b)[:length]
        ab += [0] * (length - len(ab))  # A*B may be shorter than length
        t = [(-x) % MOD for x in ab]
        t[0] = (t[0] + 2) % MOD
        b = multiply(b, t)[:length]
    return b[:n]


if __name__ == "__main__":
    print(inverse([1, MOD - 1, MOD - 1], 8))

Thư viện đã được kiểm tra trên khoảng 2400 bộ ngẫu nhiên (độ dài tới 300, n không nhất thiết là lũy thừa của 2) so với các cài đặt O(n2): nghịch đảo bằng truy hồi trực tiếp, ln bằng hệ thức nan=∑kkbkan−k (từ A′=AB′), exp bằng nbn=∑kkakbn−k (từ B′=A′B), lũy thừa bằng nhân lặp (cả m≈1018), chia có dư bằng kiểm tra A=QB+R, tính giá trị nhiều điểm bằng Horner.

Độ phức tạp

phép thời gian lý do
nhân (NTT) O(nlogn) 3 lần NTT độ dài ≤2n
nghịch đảo 1/A O(nlogn) T(n)=T(n/2)+O(nlogn), mỗi bước 2 phép nhân
chia có dư O(nlogn) 1 nghịch đảo + 2 phép nhân
đạo hàm, tích phân O(n) từng hệ số (cài đặt trên tính nghịch đảo 1/(i+1) bằng lũy thừa nhanh, thêm logp; có thể tiền xử lý bảng nghịch đảo để còn O(n))
lnA O(nlogn) 1 nghịch đảo + 1 phép nhân
expA O(nlogn) T(n)=T(n/2)+O(nlogn), mỗi bước 1 lần ln + 1 phép nhân; hằng số lớn
Am O(nlogn) 1 lần ln + 1 lần exp
A O(nlogn) mỗi bước 1 nghịch đảo cỡ 2ℓ, vẫn là tổng hình học
giá trị tại n điểm O(nlog2n) logn tầng, mỗi tầng tổng bậc O(n)

Bộ nhớ O(n) cho mọi phép trừ tính giá trị nhiều điểm (cây tích con lưu O(nlogn) hệ số). Trên máy thử, với n=218 bản C++ trên chạy nghịch đảo khoảng 0,5 đến 1 giây và exp khoảng 1,3 đến 2,4 giây: cài đặt ưu tiên dễ đọc. Muốn nhanh hơn, tiền tính sẵn các căn đơn vị, dùng unsigned int với rút gọn Montgomery, và tái sử dụng biến đổi NTT của B giữa hai phép nhân trong một bước Newton.

⚠️ Lỗi thường gặp

  • Quên điều kiện hệ số tự do. Nghịch đảo cần a0≠0, ln cần a0=1, exp cần a0=0. Gọi sai thì chương trình vẫn chạy nhưng ra rác. Cách tránh: chuẩn hoá trước (chia cho a0, hoặc tách xk như ở mục lũy thừa) và assert điều kiện.
  • Không cắt A về 2ℓ hệ số trong mỗi bước Newton. Nếu nhân cả chuỗi A dài n ở mọi bước, mỗi bước tốn O(nlogn) và tổng thành O(nlog2n), chậm hơn hẳn. Luôn dùng trunc(a, 2 * len).
  • Phép nhân trả về ít hệ số hơn mong đợi. Khi A ngắn (ví dụ A=1−x−x2), A·B có thể có ít hơn 2ℓ hệ số; truy cập ab[i] vượt biên. Bản C++ dùng trunc (resize có đệm 0), bản Python phải đệm tay.
  • Lũy thừa với số mũ khổng lồ và hệ số 0 ở đầu. Nếu lấy mmodp trước rồi mới tính độ dịch km, một m=p sẽ bị coi là 0 và cho kết quả 1 thay vì 0. So sánh km≥n bằng m thật (dùng __int128 hoặc kiểm tra k>0 và m≥n), chỉ rút gọn m khi nhân vào ln.
  • Chia có dư với B có hệ số cao nhất bằng 0. Khi đảo hệ số, BR có hệ số tự do 0 và không nghịch đảo được. Xoá các số 0 ở cuối mảng hệ số của B (và của A) trước khi chia.
  • Modulo không thân thiện NTT. Thư viện chỉ đúng với p=998244353=119·223+1 và độ dài biến đổi không quá 223. Với 109+7 phải dùng NTT ba modulo rồi ghép bằng định lý số dư Trung Hoa, hoặc FFT số thực chia nhỏ hệ số (xem FFT).
  • Tích phân cần 1/i với i≤n. Chỉ hợp lệ khi n<p; với exp và ln trên modulo nhỏ (ví dụ p=104+7) các phép này không dùng được.

Biến thể / Mở rộng

  • Đếm bằng hàm sinh. Nhân chuỗi ứng với "ghép nối tiếp", nghịch đảo 1/(1−W) ứng với "dãy tuỳ ý các phần tử từ W", exp của hàm sinh mũ ứng với "tập các thành phần có nhãn", ln là chiều ngược lại (như ví dụ đồ thị liên thông). Xem Hàm sinh cho cách dựng chuỗi, và Tổ hợp cho giai thừa và nghịch đảo giai thừa.
  • Tổng lũy thừa. Với P(x)=∏i(1−aix), đạo hàm logarit −xP′/P=∑j≥1(∑iaij)xj cho mọi tổng lũy thừa trong O(nlog2n+klogk).
  • Tích ∏(1−xv)±1. Lấy ln từng thừa số (ln11−xv=∑txvtt), cộng lại trong O(nlogn) theo chuỗi điều hoà rồi exp một lần. Đây là cách nhanh để tính số phân hoạch có ràng buộc.
  • Hệ số thứ N của P/Q với N rất lớn. Dùng thuật toán Bostan-Mori O(dlogdlogN) thay vì nghịch đảo; xem thêm Berlekamp-Massey để tìm Q từ dãy số.
  • Hằng số nhỏ hơn cho exp. Có các cách tính exp đồng thời với 1/exp (cập nhật cả hai trong một vòng Newton), hoặc dùng chia để trị online (relaxed convolution) O(nlog2n) nhưng hằng số nhỏ, thường nhanh hơn ở n≤105.

Bài tập luyện

  • Thơ bò (poetry) (Khó) Số dòng thơ có đúng K âm tiết là hệ số của 1/(1−W(x)) với W là hàm sinh độ dài từ; với K≤5000 truy hồi O(K·D) là đủ, nghịch đảo chuỗi bằng Newton là cách thứ hai (bài lấy modulo 109+7).
  • Mangan đioxit (icpc21mtj) (Chuyên gia) Mọi tổng lũy thừa ∑aij, j≤105, qua đạo hàm logarit −xP′/P: nhân chia để trị rồi nghịch đảo chuỗi bằng Newton.
  • Bài khó nhất (icpc22regh) (Chuyên gia) Đếm hoán vị theo số nghịch thế với ràng buộc; hàm sinh là tích ∏1−xv1−x, lấy ln từng thừa số theo chuỗi điều hoà rồi exp bằng Newton.
  • Đến giờ đấu bài rồi! (icpc23regi) (Chuyên gia) Đếm hoán vị p với pk=a; với mỗi độ dài chu trình, số cách gom chu trình thành khối là hệ số của exp một hàm sinh mũ.
  • Độ Sâu Cây (treedepth) (Bậc thầy) Đóng góp mỗi cặp nút là hệ số của thương PN/(1+x+⋯+xd) với PN là hàm sinh số nghịch thế; luyện chia chính xác đa thức (nhân với nghịch đảo chuỗi qua truy hồi trượt) với modulo tuỳ ý.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0