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ử.
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) 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 . Trang này trình bày bộ công cụ chuẩn: nghịch đảo chuỗi , chia đa thức có dư, đạo hàm, tích phân, , , , và tính giá trị đa thức tại nhiều điểm. Tất cả đều lấy theo modulo và modulo , chạy trong (riêng tính giá trị nhiều điểm là ) thay vì .
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 , một phép nhân đa thức cho đáp án đúng tới .
Ý 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 là số bao nhiêu, chỉ quan tâm dãy hệ số. Vì vậy "" nghĩa là tìm sao cho . So sánh hệ số:
Cách giải ngây thơ đọc thẳng từ đây: , mất . Nghịch đảo tồn tại khi và chỉ khi (modulo ). Ví dụ quen thuộc: là hàm sinh của dãy Fibonacci (xem Hàm sinh).
Lặp Newton cho nghịch đảo
Giả sử đã có với . Đặt sai số ; chia hết cho . Lấy
Khi đó
mà chia hết cho . Nghĩa là sau một bước, số hệ số đúng tăng gấp đôi. Bắt đầu từ (đúng tới ), sau bước ta có đủ hệ số. Đây chính là phương pháp Newton tìm nghiệm của : .
Điểm mấu chốt về độ phức tạp: ở bước đưa độ chính xác từ lên chỉ cần và có hệ số, nên chi phí là . Tổng
vì . Cả trang này đều dùng lập luận gấp đôi đó.
Chia đa thức có dư
Cho bậc (có hệ số) và bậc (), cần với , . Ký hiệu đảo hệ số (viết dãy hệ số theo thứ tự ngược). Thay vào đẳng thức rồi nhân với :
Số hạng cuối chia hết cho , nên . Nghịch đảo tồn tại vì hệ số tự do của nó là . Có thì . Tổng chi phí: một nghịch đảo và hai phép nhân, .
Đạ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ố: và , đều .
Với , định nghĩa (hằng số tích phân bằng để ). 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: . Điều kiện là bắt buộc: của hằng số không xác định trong , nên nếu thì chia cả chuỗi cho trước.
Exp bằng Newton
Với , . Ta tìm thoả . Vì , bước Newton là
Cùng lập luận như nghịch đảo: sai số chia hết cho thì sau bước sai số chia hết cho . Mỗi bước tốn một (tức một nghịch đảo) cỡ và một phép nhân, nên vẫn , nhưng hằng số lớn (cỡ 10 đến 20 lần một phép nhân). Điều kiện cũng bắt buộc: của hằng số khác không có nghĩa trong .
Lũy thừa , kể cả khi bắt đầu bằng các hệ số
Nếu thì , và chỉ cần lấy modulo (vì chỉ xuất hiện như một hệ số nhân). Trường hợp tổng quát: gọi là chỉ số nhỏ nhất có , viết
Nếu thì kết quả modulo toàn . Chú ý dùng thật cho phép so sánh , dùng cho hệ số trong , còn tính bằng lũy thừa nhanh (số mũ có thể rút về ).
Căn bậc hai
Với , giải bằng Newton: , mỗi bước một nghịch đảo và một phép nhân, vẫn . Nếu thì cần là số chính phương modulo (tìm căn bằng Tonelli-Shanks) và số hệ số ở đầu phải chẵn.
Tính giá trị tại nhiều điểm (sơ lược)
Muốn tính : ta có . Dựng cây tích con (subproduct tree): lá là , mỗi nút là tích hai con, tốn . Đi từ gốc xuống, tại mỗi nút thay bằng (chia có dư ở trên), tới lá thì phần dư là một hằng số, chính là . Mỗi tầng tổng bậc là , có tầng, nên tổng cộng . Bài toán ngược (nội suy từ đ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 tới
Bắt đầu (vì ). Mỗi bước tính , rồi :
| bước | mới | ||
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 |
Quan sát cột thứ ba: sau bước 2, đúng bằng ở mọi bậc nhỏ hơn , sai số bắt đầu từ . Bước 3 sửa đúng 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ư:
, , cần hệ số của .
- , .
- .
- , đảo lại .
- .
Chương trình in quotient: 998244352 3 1 và remainder: 6 998244352 (vì ).
Đồ thị có nhãn liên thông bằng
Số đồ thị có nhãn đỉnh là . 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ũ và ( là số đồ thị liên thông) ta có , tức :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 8 | 64 | 1024 | 32768 | |
| 0 | 1 | 1 | 4 | 38 | 728 | 26704 |
Kiểm tra : trong đồ thị trên đỉnh, bị loại là đồ thị rỗng () và đồ thị có đúng một cạnh (), còn đồ thị liên thông.
Số phân hoạch bằng nghịch đảo
Hàm sinh số phân hoạch là . Theo định lý số ngũ giác Euler, mẫu số là
chỉ có hệ số khác dưới . Một lần nghịch đảo cho trong ; với 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 , tham số n là số hệ số cần giữ (tức modulo ). 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ử, mất khoảng giây và mất vài chục giây, nên chỉ dùng để học hoặc với nhỏ; đi thi hãy dùng 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}));
}
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 bộ ngẫu nhiên (độ dài tới , không nhất thiết là lũy thừa của ) so với các cài đặt : nghịch đảo bằng truy hồi trực tiếp, bằng hệ thức (từ ), bằng (từ ), lũy thừa bằng nhân lặp (cả ), chia có dư bằng kiểm tra , 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) | 3 lần NTT độ dài | |
| nghịch đảo | , mỗi bước 2 phép nhân | |
| chia có dư | 1 nghịch đảo + 2 phép nhân | |
| đạo hàm, tích phân | từng hệ số (cài đặt trên tính nghịch đảo bằng lũy thừa nhanh, thêm ; có thể tiền xử lý bảng nghịch đảo để còn ) | |
| 1 nghịch đảo + 1 phép nhân | ||
| , mỗi bước 1 lần + 1 phép nhân; hằng số lớn | ||
| 1 lần + 1 lần | ||
| mỗi bước 1 nghịch đảo cỡ , vẫn là tổng hình học | ||
| giá trị tại điểm | tầng, mỗi tầng tổng bậc |
Bộ nhớ cho mọi phép trừ tính giá trị nhiều điểm (cây tích con lưu hệ số). Trên máy thử, với bản C++ trên chạy nghịch đảo khoảng đến giây và khoảng đến 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 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 , cần , cần . 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 , hoặc tách như ở mục lũy thừa) và
assertđiều kiện. - Không cắt về hệ số trong mỗi bước Newton. Nếu nhân cả chuỗi dài ở mọi bước, mỗi bước tốn và tổng thành , 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 ngắn (ví dụ ), có thể có ít hơn hệ số; truy cập
ab[i]vượt biên. Bản C++ dùngtrunc(resize có đệm ), bản Python phải đệm tay. - Lũy thừa với số mũ khổng lồ và hệ số ở đầu. Nếu lấy trước rồi mới tính độ dịch , một sẽ bị coi là và cho kết quả thay vì . So sánh bằng thật (dùng
__int128hoặc kiểm tra và ), chỉ rút gọn khi nhân vào . - Chia có dư với có hệ số cao nhất bằng . Khi đảo hệ số, có hệ số tự do và không nghịch đảo được. Xoá các số ở cuối mảng hệ số của (và của ) trước khi chia.
- Modulo không thân thiện NTT. Thư viện chỉ đúng với và độ dài biến đổi không quá . Với 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 với . Chỉ hợp lệ khi ; với và trên modulo nhỏ (ví dụ ) 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 ứng với "dãy tuỳ ý các phần tử từ ", của hàm sinh mũ ứng với "tập các thành phần có nhãn", 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 , đạo hàm logarit cho mọi tổng lũy thừa trong .
- Tích . Lấy từng thừa số (), cộng lại trong theo chuỗi điều hoà rồi một lần. Đây là cách nhanh để tính số phân hoạch có ràng buộc.
- Hệ số thứ của với rất lớn. Dùng thuật toán Bostan-Mori thay vì nghịch đảo; xem thêm Berlekamp-Massey để tìm từ dãy số.
- Hằng số nhỏ hơn cho . Có các cách tính đồng thời với (cập nhật cả hai trong một vòng Newton), hoặc dùng chia để trị online (relaxed convolution) nhưng hằng số nhỏ, thường nhanh hơn ở .
Bài tập luyện
- Thơ bò (poetry) (Khó) Số dòng thơ có đúng âm tiết là hệ số của với là hàm sinh độ dài từ; với truy hồi là đủ, nghịch đảo chuỗi bằng Newton là cách thứ hai (bài lấy modulo ).
- Mangan đioxit (icpc21mtj) (Chuyên gia) Mọi tổng lũy thừa , , qua đạo hàm logarit : 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 , lấy từng thừa số theo chuỗi điều hoà rồi bằng Newton.
- Đến giờ đấu bài rồi! (icpc23regi) (Chuyên gia) Đếm hoán vị với ; 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 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 với 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ỳ ý.
Bình luận