1. 從一道模板題說起多項(xiàng)式對(duì)數(shù)函數(shù)ln到底是什么如果你在洛谷、Codeforces或者任何一個(gè)算法競(jìng)賽社區(qū)混跡過一段時(shí)間大概率會(huì)刷到過“P4725 【模板】多項(xiàng)式對(duì)數(shù)函數(shù)多項(xiàng)式 ln”這道題。它就像算法競(jìng)賽選手在多項(xiàng)式領(lǐng)域的一個(gè)“成人禮”標(biāo)志著從只會(huì)做加減乘除的“小學(xué)生”進(jìn)階到開始觸及多項(xiàng)式更深刻運(yùn)算的“中學(xué)生”。但很多人在第一次接觸時(shí)都會(huì)懵多項(xiàng)式還能取對(duì)數(shù)這玩意兒有什么用難道是把1 2x 3x^2丟進(jìn)計(jì)算器按ln鍵嗎顯然不是。這里的“多項(xiàng)式對(duì)數(shù)函數(shù)”是一個(gè)形式冪級(jí)數(shù)上的形式運(yùn)算。它解決的核心問題是給定一個(gè)常數(shù)項(xiàng)為1的多項(xiàng)式或形式冪級(jí)數(shù)A(x)求另一個(gè)多項(xiàng)式B(x)使得在形式冪級(jí)數(shù)的意義下exp(B(x)) A(x)。這里 exp 是指數(shù)函數(shù)。換句話說B(x) 就是 A(x) 的“形式對(duì)數(shù)”。這個(gè)運(yùn)算在組合數(shù)學(xué)、生成函數(shù)、多項(xiàng)式算法中有著極其重要的地位。比如當(dāng)你用生成函數(shù)刻畫一個(gè)組合結(jié)構(gòu)時(shí)對(duì)其取 ln 往往對(duì)應(yīng)著將連通分量拆解出來在多項(xiàng)式牛頓迭代求解中l(wèi)n 和 exp 是一對(duì)關(guān)鍵的基礎(chǔ)算子。這道模板題之所以經(jīng)典是因?yàn)樗昝赖貙⒍囗?xiàng)式求導(dǎo)、積分、求逆、乘法這幾個(gè)基礎(chǔ)操作串聯(lián)了起來形成了一個(gè)完整的算法鏈條。網(wǎng)上能找到的題解和代碼很多但大多只給出了“怎么做”的步驟和代碼對(duì)于“為什么這么做”、“每一步背后的數(shù)學(xué)原理是什么”、“實(shí)現(xiàn)時(shí)有哪些一踩就炸的坑”卻語焉不詳。我這篇文章就想結(jié)合我多次實(shí)現(xiàn)和調(diào)試的經(jīng)驗(yàn)把這些隱藏在水面下的東西徹底講透。我們不止要會(huì)套模板更要理解這個(gè)模板的每一顆螺絲釘是怎么擰上去的。2. 核心公式推導(dǎo)為什么求ln變成了求導(dǎo)、求逆和積分幾乎所有教程都會(huì)直接甩給你這個(gè)公式 若 A(x) 1 a_1 x a_2 x^2 ...且 A(0)1則ln(A(x)) ∫ [A(x) / A(x)] dx這個(gè)公式是整套算法的基石。我們來一步步拆解它看它到底是怎么來的。2.1 從形式微分的定義出發(fā)首先我們得認(rèn)同對(duì)形式冪級(jí)數(shù)也可以定義“導(dǎo)數(shù)”。這很直觀對(duì)于多項(xiàng)式 A(x) ∑_{i0}^{n} a_i x^i其形式導(dǎo)數(shù) A(x) 就是 ∑_{i1}^{n} i * a_i x^{i-1}。就是把每一項(xiàng)的指數(shù)拿下來當(dāng)系數(shù)然后指數(shù)減一?，F(xiàn)在考慮我們想求的 B(x) ln(A(x))。這里 ln 是一個(gè)形式運(yùn)算。我們對(duì)這個(gè)等式兩邊同時(shí)關(guān)于 x 求形式導(dǎo)數(shù)利用鏈?zhǔn)椒▌t左邊B(x) 右邊d/dx [ln(A(x))] A(x) / A(x) 這里直接類比了實(shí)數(shù)域上 ln(f(x)) 的導(dǎo)數(shù)為 f(x)/f(x)于是我們得到了一個(gè)關(guān)鍵等式B(x) A(x) / A(x)。2.2 從微分到積分得到了 B(x) 的導(dǎo)數(shù)那么 B(x) 本身自然就是對(duì)其積分B(x) ∫ B(x) dx ∫ [A(x) / A(x)] dx注意這里積分會(huì)有一個(gè)積分常數(shù) C。因?yàn)槭遣欢ǚe分。那么 C 是多少我們需要利用初始條件A(0) 1。我們希望 B(x) 也是一個(gè)形式冪級(jí)數(shù)并且通常定義 ln(1) 0。所以 B(0) ln(A(0)) ln(1) 0。另一方面我們對(duì) ∫ [A(x) / A(x)] dx 求出的結(jié)果其常數(shù)項(xiàng)就是積分產(chǎn)生的常數(shù) C。為了讓 B(0) 0我們必須令 C 0。所以最終公式里我們直接寫為定積分形式從 0 積到 x或者理解為取不定積分后忽略常數(shù)項(xiàng)因?yàn)槌?shù)項(xiàng)為0。在實(shí)現(xiàn)時(shí)我們做不定積分然后手動(dòng)將結(jié)果的常數(shù)項(xiàng)設(shè)為0即可。2.3 公式的可行性分析這個(gè)公式將 ln 運(yùn)算轉(zhuǎn)化為了三個(gè)我們已知能做的操作求導(dǎo) (A(x))O(n) 復(fù)雜度極其簡(jiǎn)單。求逆 (1 / A(x))這里需要計(jì)算 A(x) 的乘法逆元。這需要用到多項(xiàng)式求逆算法通常使用牛頓迭代法復(fù)雜度 O(n log n)。積分 (∫ ... dx)O(n) 復(fù)雜度是求導(dǎo)的逆過程同樣簡(jiǎn)單。所以整個(gè)多項(xiàng)式 ln 的算法復(fù)雜度就卡在了多項(xiàng)式求逆這一步為 O(n log n)。這也就是為什么多項(xiàng)式求逆是多項(xiàng)式全家桶里更基礎(chǔ)的一個(gè)模板。注意這個(gè)公式成立有一個(gè)絕對(duì)的前提A(x) 的常數(shù)項(xiàng)必須為 1。為什么 從數(shù)學(xué)上看ln(A(x)) 要想展開成形式冪級(jí)數(shù)必須在 x0 處有定義且 ln(A(0)) 需要是一個(gè)有限值我們?nèi)?。如果 A(0)0ln(0) 無定義如果 A(0) 是其他非1常數(shù) c那么 ln(A(x)) ln(c) ln(1 (A(x)-c)/c)。這里 ln(c) 是一個(gè)實(shí)數(shù)常數(shù)但我們的多項(xiàng)式是在某個(gè)模數(shù)如998244353的有限域上運(yùn)算的ln(c) 在這個(gè)域里可能沒有定義除非 c 是模數(shù)的原根相關(guān)。為了保證運(yùn)算純粹在模意義下進(jìn)行且結(jié)果是一個(gè)多項(xiàng)式常數(shù)項(xiàng)為0最方便且通用的約定就是要求 A(0)1。這樣 ln(1)0一切都很干凈。3. 算法步驟拆解與零基礎(chǔ)實(shí)現(xiàn)指南理解了公式我們來把算法步驟徹底細(xì)化。假設(shè)我們有多項(xiàng)式 A(x)其次數(shù)為 n-1通常我們處理長(zhǎng)度為 n 的數(shù)組下標(biāo) 0 到 n-1 對(duì)應(yīng)次數(shù) 0 到 n-1 的系數(shù)且滿足 A[0] 1。3.1 第一步計(jì)算 A(x) 的導(dǎo)數(shù) A(x)這一步是熱身。設(shè) A(x) a0 a1x a2x^2 ... a_{n-1}x^{n-1}。 那么 A(x) a1 2a2x 3a3*x^2 ... (n-1)*a_{n-1}*x^{n-2}。在代碼中這就是一個(gè)簡(jiǎn)單的循環(huán)// 假設(shè)系數(shù)存儲(chǔ)在數(shù)組 a 中長(zhǎng)度為 n for (int i 1; i n; i) { da[i-1] 1LL * a[i] * i % mod; // da 存儲(chǔ)導(dǎo)數(shù)系數(shù) } // da 的有效長(zhǎng)度變?yōu)?n-1注意邊界導(dǎo)數(shù)的次數(shù)比原多項(xiàng)式低一次。3.2 第二步計(jì)算 A(x) 的乘法逆元 B(x) 1 / A(x)這是整個(gè)算法的核心和性能瓶頸。我們需要求一個(gè)多項(xiàng)式 B(x)使得 A(x) * B(x) ≡ 1 (mod x^n)。這里mod x^n的意思是我們只關(guān)心乘積的前 n 項(xiàng)0 到 n-1 次更高次的項(xiàng)可以忽略。求逆通常使用牛頓迭代法。其思想是假設(shè)我們已經(jīng)求出了在模 x^{ceil(m/2)} 意義下的逆元 B_0(x)如何快速得到在模 x^m 意義下的逆元 B(x)推導(dǎo)過程略涉及泰勒展開結(jié)論是迭代公式為B(x) ≡ B_0(x) * (2 - A(x) * B_0(x)) (mod x^m)實(shí)際操作時(shí)我們采用遞歸或迭代倍增的方式初始條件當(dāng) n1 時(shí)A(x) 只有一個(gè)常數(shù)項(xiàng) a0。由前提 a0 1所以在模 x^1 意義下其逆元就是 1。假設(shè)我們已經(jīng)求出在模 x^{ceil(n/2)} 意義下的逆元 B_0(x)。目標(biāo)計(jì)算模 x^n 意義下的逆元 B(x)。根據(jù)公式我們需要計(jì)算T(x) A(x) * B_0(x) (mod x^n)// 注意這里模數(shù)要提升到 x^nT(x) (2 - T(x)) (mod x^n)// 對(duì) T(x) 的每一項(xiàng)做 2 - t_i 運(yùn)算B(x) T(x) * B_0(x) (mod x^n)這個(gè)過程需要多項(xiàng)式乘法。利用 NTT快速數(shù)論變換可以將乘法優(yōu)化到 O(n log n)。由于這部分是獨(dú)立模板代碼較長(zhǎng)。其關(guān)鍵點(diǎn)在于每次迭代時(shí)對(duì)于 A(x) 我們只需要前 m 項(xiàng)當(dāng)前目標(biāo)長(zhǎng)度對(duì)于 B_0(x) 我們知道它在模 x^{m/2} 下是精確的。計(jì)算A(x) * B_0(x)時(shí)結(jié)果長(zhǎng)度會(huì)增長(zhǎng)但我們只取前 m 項(xiàng)。然后進(jìn)行2 - T(x)的系數(shù)運(yùn)算最后再乘一次 B_0(x) 并取前 m 項(xiàng)。3.3 第三步計(jì)算 C(x) A(x) * B(x)現(xiàn)在我們有了導(dǎo)數(shù)da長(zhǎng)度為 n-1和逆元b長(zhǎng)度為 n。將它們相乘。注意da的次數(shù)是 n-2b的次數(shù)是 n-1它們的乘積次數(shù)最高為 (n-2)(n-1)2n-3。但我們最終只需要前 n-1 項(xiàng)因?yàn)橄乱徊椒e分后我們要得到 n 項(xiàng)結(jié)果。所以我們可以只計(jì)算到長(zhǎng)度至少為 n-1 的卷積。設(shè)dc da * b。我們?nèi)c的前 n-1 項(xiàng)。注意dc[0]對(duì)應(yīng)的是A(x)*B(x)的常數(shù)項(xiàng)。3.4 第四步對(duì) C(x) 積分得到最終結(jié)果積分是導(dǎo)數(shù)的逆運(yùn)算。如果C(x) c0 c1*x c2*x^2 ...那么它的積分∫ C(x) dx C c0*x (c1/2)*x^2 (c2/3)*x^3 ...其中 C 是積分常數(shù)。我們已經(jīng)知道結(jié)果的常數(shù)項(xiàng)必須為 0。所以我們計(jì)算 對(duì)于 i 從 0 到 n-2res[i1] dc[i] * inv(i1) % mod其中inv(i1)是 i1 在模 mod 下的乘法逆元需要預(yù)處理。 而res[0] 0。這樣得到的res就是ln(A(x))的前 n 項(xiàng)系數(shù)。3.5 完整流程圖示與復(fù)雜度分析輸入: A(x), 滿足 A[0]1, 次數(shù)界 n 輸出: B(x) ln(A(x)) mod x^n 1. 求導(dǎo): DA(x) derivative(A(x)) // O(n) 2. 求逆: IA(x) inverse(A(x), n) // O(n log n) 使用牛頓迭代NTT 3. 乘法: C(x) DA(x) * IA(x) mod x^{n-1} // O(n log n) NTT乘法結(jié)果取前n-1項(xiàng) 4. 積分: B(x) integral(C(x)) // O(n) 常數(shù)項(xiàng)設(shè)為0 5. 返回 B(x)總時(shí)間復(fù)雜度由兩次 O(n log n) 的操作主導(dǎo)即求逆和乘法?？臻g上需要一些臨時(shí)數(shù)組進(jìn)行變換和計(jì)算。4. 實(shí)戰(zhàn)代碼剖析從模塊構(gòu)建到邊界處理光說不練假把式。下面我結(jié)合一個(gè)典型的基于 NTT模數(shù) 998244353原根為 3的實(shí)現(xiàn)來逐塊解析代碼并指出那些容易寫錯(cuò)、調(diào)試到崩潰的細(xì)節(jié)。4.1 基礎(chǔ)工具函數(shù)快速冪與逆元const int mod 998244353, g 3; // 原根 int qpow(int a, int b) { int res 1; while (b) { if (b 1) res 1LL * res * a % mod; a 1LL * a * a % mod; b 1; } return res; }qpow是標(biāo)準(zhǔn)快速冪。inv函數(shù)通常直接調(diào)用qpow(a, mod-2)但頻繁調(diào)用時(shí)建議預(yù)處理 1~n 的逆元。4.2 核心NTT 與多項(xiàng)式乘法這是所有多項(xiàng)式操作的基礎(chǔ)。代碼較長(zhǎng)但結(jié)構(gòu)固定。關(guān)鍵點(diǎn)在于rev數(shù)組的蝴蝶變換以及三層循環(huán)的迭代實(shí)現(xiàn)。這里我強(qiáng)調(diào)幾個(gè)易錯(cuò)點(diǎn)長(zhǎng)度與界限NTT 要求長(zhǎng)度是 2 的冪。每次進(jìn)行多項(xiàng)式乘法前必須計(jì)算lim 1, bit 0; while (lim n m) lim 1, bit;。然后初始化 rev 數(shù)組。結(jié)果清零對(duì)于長(zhǎng)度為lim的數(shù)組一定要確保lim范圍內(nèi)的數(shù)據(jù)是有效的或者在使用前清空。特別是多次調(diào)用時(shí)舊數(shù)據(jù)可能殘留。逆變換后的縮放NTT 逆變換后每一項(xiàng)需要乘以lim的逆元。int invlim qpow(lim, mod-2); for (int i0; ilim; i) a[i]1LL*a[i]*invlim%mod;4.3 多項(xiàng)式求逆的實(shí)現(xiàn)細(xì)節(jié)這是最難寫對(duì)的部分。我給出一個(gè)相對(duì)清晰的迭代版本框架void poly_inv(int *a, int *b, int n) { // 計(jì)算 b(x)使得 a(x)*b(x) ≡ 1 (mod x^n) static int tmp[N]; // 臨時(shí)數(shù)組需要足夠大如4倍n b[0] qpow(a[0], mod-2); // 初始條件常數(shù)項(xiàng)逆元 for (int len 2; (len 1) n; len 1) { // 當(dāng)前目標(biāo)是求出模 x^len 下的逆元 int lim len 1; // 乘法需要長(zhǎng)度 // 將 a 的前 len 項(xiàng)拷貝到 tmp并做 NTT for (int i 0; i len; i) tmp[i] i n ? a[i] : 0; for (int i len; i lim; i) tmp[i] b[i] 0; ntt(tmp, lim, 1); ntt(b, lim, 1); // 根據(jù)公式 B B0 * (2 - A * B0) 計(jì)算 for (int i 0; i lim; i) { b[i] 1LL * b[i] * (2 - 1LL * tmp[i] * b[i] % mod mod) % mod; } ntt(b, lim, -1); // 重要b 中 len 之后的項(xiàng)是無意義的必須清零防止影響下一輪 for (int i len; i lim; i) b[i] 0; } // 最后確保 b 只有前 n 項(xiàng)有效后面清零如果傳入的n不是2的冪 for (int i n; i lim; i) b[i] 0; }踩坑實(shí)錄1清零清零清零這是多項(xiàng)式題最經(jīng)典的錯(cuò)誤。在牛頓迭代的每一輪結(jié)束后b數(shù)組在len之后的系數(shù)必須手動(dòng)設(shè)為0。因?yàn)?NTT 逆變換后這些位置可能留有上一輪或計(jì)算過程中的垃圾值。下一輪循環(huán)時(shí)我們會(huì)把整個(gè)b數(shù)組包括后面的垃圾值做 NTT這些垃圾值會(huì)污染整個(gè)頻域?qū)е陆Y(jié)果完全錯(cuò)誤。這個(gè) bug 非常隱蔽因?yàn)樾?shù)據(jù)時(shí)可能因?yàn)殚L(zhǎng)度不夠碰不到垃圾內(nèi)存而僥幸正確大數(shù)據(jù)一定掛。4.4 多項(xiàng)式 ln 的完整實(shí)現(xiàn)集成了求導(dǎo)、求逆、乘法和積分。void poly_derivative(int *a, int *da, int n) { for (int i 1; i n; i) da[i-1] 1LL * a[i] * i % mod; da[n-1] 0; // 導(dǎo)數(shù)長(zhǎng)度減一最后一位可置0 } void poly_integral(int *a, int *ia, int n) { ia[0] 0; // 常數(shù)項(xiàng)為0 // 預(yù)處理1~n的逆元 inv[i] for (int i 1; i n; i) ia[i] 1LL * a[i-1] * inv[i] % mod; } void poly_ln(int *a, int *res, int n) { // 前提檢查a[0] 必須為 1 assert(a[0] 1); static int da[N], ia[N], tmp[N]; // 1. 求導(dǎo) poly_derivative(a, da, n); // da 長(zhǎng)度為 n-1 // 2. 求逆 poly_inv(a, ia, n); // ia 是 A(x) 的逆長(zhǎng)度為 n // 3. 乘法da * ia int lim 1, bit 0; while (lim (n-1) n) lim 1, bit; // 結(jié)果需要前 n-1 項(xiàng) for (int i 0; i lim; i) tmp[i] (i n-1) ? da[i] : 0; for (int i 0; i lim; i) { // 注意ia 只有前 n 項(xiàng)有效后面在 poly_inv 中已清零 // 但這里為了安全可以只拷貝前 n 項(xiàng)后面置0 if (i n) ia[i] ia[i]; else if (i lim) ia[i] 0; // 確保 ia 在 lim 長(zhǎng)度內(nèi)有效 } // 這里需要調(diào)用一個(gè)標(biāo)準(zhǔn)的 NTT 乘法函數(shù)輸入 tmp 和 ia結(jié)果存回 tmp ntt_mul(tmp, ia, lim); // 假設(shè)這個(gè)函數(shù)處理了 NTT 變換、點(diǎn)乘、逆變換和縮放 // 現(xiàn)在 tmp 的前 n-1 項(xiàng)是 da * ia 的結(jié)果 // 4. 積分 poly_integral(tmp, res, n); // 積分后長(zhǎng)度變?yōu)?n }踩坑實(shí)錄2長(zhǎng)度對(duì)齊與數(shù)組越界在調(diào)用poly_inv時(shí)我們傳入的長(zhǎng)度是n它會(huì)計(jì)算模x^n的逆。但注意poly_inv內(nèi)部可能按2的冪分配內(nèi)存。我們傳給poly_ln的數(shù)組a其有效長(zhǎng)度就是n。但在求導(dǎo)后da有效長(zhǎng)度是n-1。進(jìn)行乘法da * ia時(shí)da長(zhǎng)度n-1ia長(zhǎng)度n卷積結(jié)果長(zhǎng)度至少需要(n-1)(n-1)2n-2才能保證前n-1項(xiàng)精確。我們?cè)O(shè)置的lim必須大于等于這個(gè)值。同時(shí)要確保傳入 NTT 乘法的數(shù)組在lim長(zhǎng)度內(nèi)都有定義要么是有效系數(shù)要么是0。任何未初始化的值都會(huì)導(dǎo)致錯(cuò)誤。5. 調(diào)試技巧與常見問題排查就算你完全理解了算法第一遍代碼也幾乎不可能一次 AC。以下是我總結(jié)的排查清單5.1 結(jié)果完全不對(duì)/隨機(jī)數(shù)檢查 NTT 的正確性這是根源。寫一個(gè)簡(jiǎn)單的測(cè)試比如計(jì)算(12x) * (13x)看結(jié)果是不是1 5x 6x^2。確保正變換、點(diǎn)乘、逆變換、縮放每一步都正確。檢查數(shù)組清零如 4.3 節(jié)所述在poly_inv的每一輪迭代后必須清零b數(shù)組len之后的部分。在poly_ln中調(diào)用 NTT 前確保tmp和ia在lim范圍內(nèi)的數(shù)據(jù)是干凈的。檢查長(zhǎng)度計(jì)算lim是否足夠大while (lim n m) lim 1中的n和m是否正確對(duì)于da * ian n-1da的長(zhǎng)度m nia的長(zhǎng)度所以lim需要至少2n-1的下一個(gè)2的冪。5.2 結(jié)果前幾項(xiàng)對(duì)后面錯(cuò)檢查求逆的邊界poly_inv函數(shù)是否保證了結(jié)果嚴(yán)格只有前n項(xiàng)有效在倍增過程中我們計(jì)算的是模x^len的逆但len可能大于n。函數(shù)最后需要把n之后的系數(shù)清零。檢查積分用的逆元表inv[i]是否預(yù)處理正確inv[i]是i在模mod下的逆元通常用線性遞推inv[i] mod - 1LL * (mod/i) * inv[mod%i] % mod來求。確保inv[1] 1。5.3 常數(shù)項(xiàng)不為0檢查輸入確認(rèn)輸入多項(xiàng)式a[0]是否真的為 1。題目可能不保證需要自己先判斷或處理。檢查積分函數(shù)poly_integral是否將res[0]設(shè)為了 05.4 性能問題TLENTT 的蝴蝶變換rev數(shù)組是否預(yù)處理每次乘法都重新計(jì)算會(huì)超時(shí)。不必要的拷貝在poly_inv和poly_ln中盡量減少大數(shù)組的memcpy操作。使用指針和就地計(jì)算。乘法優(yōu)化對(duì)于da * ia我們只需要前n-1項(xiàng)。可以使用“半在線卷積”的思路進(jìn)行優(yōu)化但模板題通常不需要標(biāo)準(zhǔn)的 NTT 乘法即可通過。5.5 一個(gè)實(shí)用的調(diào)試方法對(duì)拍寫一個(gè)暴力版本的poly_ln用于小數(shù)據(jù)范圍比如 n 10的驗(yàn)證。 暴力版本可以模擬形式冪級(jí)數(shù)的運(yùn)算先預(yù)處理逆元然后根據(jù)定義ln(A(x)) ∑_{k1} (-1)^{k-1} * (A(x)-1)^k / k。因?yàn)?A(x)-1 的常數(shù)項(xiàng)為0所以這個(gè)級(jí)數(shù)在模 x^n 意義下是有限的只需要算到 kn-1 即可。 用這個(gè)暴力程序去驗(yàn)證你的 NTT 優(yōu)化版本在小數(shù)據(jù)n5,6,7...下的結(jié)果是否一致。這是定位問題最有效的方式。6. 從模板到應(yīng)用ln 在生成函數(shù)中的意義搞懂了實(shí)現(xiàn)我們?cè)賮砹牧乃降子惺裁从眠@樣下次遇到問題你才能想到用它。6.1 組合意義的連接集合與連通分量這是 ln 最經(jīng)典的應(yīng)用。假設(shè)我們有一個(gè)組合類 A比如所有的圖其指數(shù)生成函數(shù)EGF為 A(x)。那么A(x)的 expB(x) exp(A(x))通常代表了由 A 中的“連通”對(duì)象任意組合而成的“所有”對(duì)象。例如A(x) 是連通圖的 EGF那么 B(x) 就是所有圖的 EGF。反過來A(x)的 lnC(x) ln(B(x))就代表了從“所有”對(duì)象中提取出“連通”分量。例如已知所有圖的 EGF B(x)那么 ln(B(x)) 就是連通圖的 EGF。在很多計(jì)數(shù)問題中我們更容易求出所有方案的生成函數(shù)而想要得到連通方案的生成函數(shù)就需要對(duì)其取 ln。6.2 多項(xiàng)式牛頓迭代中的角色牛頓迭代是求解多項(xiàng)式方程F(G(x)) 0的強(qiáng)大工具。例如求exp、求sqrt開根、求復(fù)合逆函數(shù)等。 在推導(dǎo)這些迭代式時(shí)ln和exp經(jīng)常作為一對(duì)互逆的運(yùn)算出現(xiàn)。例如求G(x) exp(F(x))可以轉(zhuǎn)化為方程ln(G(x)) - F(x) 0然后應(yīng)用牛頓迭代。此時(shí)poly_ln就成了迭代過程中必須調(diào)用的子程序。6.3 形式微分與形式積分的工具ln的公式本身完美結(jié)合了求導(dǎo)、求逆和積分。這使得它成為學(xué)習(xí)多項(xiàng)式形式運(yùn)算的一個(gè)優(yōu)秀案例。掌握了它你就掌握了處理形式冪級(jí)數(shù)的一整套基本工具鏈。7. 總結(jié)與擴(kuò)展思考實(shí)現(xiàn)一個(gè)poly_ln就像搭樂高。你需要準(zhǔn)備好“求導(dǎo)”、“求逆”其內(nèi)部又需要“NTT乘法”、“積分”這幾個(gè)基礎(chǔ)模塊然后按照公式∫ (A / A) dx把它們正確地拼接起來。其中多項(xiàng)式求逆是最復(fù)雜、最容易出錯(cuò)的一環(huán)務(wù)必理解其牛頓迭代的倍增思想并牢記迭代后清零的紀(jì)律。在競(jìng)賽中poly_ln很少單獨(dú)出題它往往是更大問題的一塊拼圖。比如你需要先對(duì)某個(gè)生成函數(shù)取 ln進(jìn)行一些操作再取 exp。因此將它寫對(duì)、寫熟封裝成一個(gè)可靠的函數(shù)是進(jìn)軍更高級(jí)多項(xiàng)式算法如指數(shù)函數(shù)、三角函數(shù)、快速冪、復(fù)合逆的必經(jīng)之路。最后關(guān)于常數(shù)項(xiàng)不為1的情況理論上可以通過提取公因式解決若 A(0) c ≠ 0則 ln(A(x)) ln(c) ln(A(x)/c)。但 ln(c) 在模意義下需要離散對(duì)數(shù)來求解這超出了普通多項(xiàng)式模板的范圍。所以模板題和常見應(yīng)用都默認(rèn)常數(shù)項(xiàng)為1。寫多項(xiàng)式代碼是對(duì)耐心和細(xì)心的雙重考驗(yàn)。一個(gè)符號(hào)的錯(cuò)誤、一次忘記的清零都可能導(dǎo)致調(diào)試數(shù)小時(shí)。但一旦你徹底征服了它那種對(duì)復(fù)雜算法了如指掌、對(duì)每一行代碼都充滿自信的感覺是無與倫比的。希望這篇超詳細(xì)的拆解能幫你少走些彎路真正把這塊硬骨頭啃下來。