分治 FFT 与生成函数与进阶多项式

• CDQ 分治的"先左后右"顺序
• 左侧贡献到右侧的依赖
• 复杂度递推求解

CDQ 分治优化 DP 时，dp[i] 依赖左侧所有 j<i 的 dp[j]，因此分治处理 [l,r] 必须先递归算出左半 [l,mid] 的 dp 值，再用左半对右半 [mid+1,r] 的贡献（一次卷积）批量更新，最后递归右半。若先处理右半，那么右半 dp 依赖的左半贡献尚未就绪，结果错误。所以顺序必须是"先左、再左→右贡献、后右"。复杂度：每层处理一次跨区间卷积 O(n log n)，共有 log n 层，故 T(n) = 2T(n/2) + O(n log n)，解为 O(n log² n)（主定理：f(n)=n log n 与 n^{log_2 2}=n 比较，f(n) 是 n 的 log n 倍，故 T(n)=O(n log² n)）。

CDQ 的"先左后右"保证了 DP 依赖顺序的正确性：左半算完才能贡献右半。复杂度上，每层把跨区间的 O(n²) 转移用卷积压缩到 O(n log n)，log n 层得到 O(n log² n)。主定理中 f(n)=n log n 主导，比 n 多一个 log，故结果 O(n log² n)。

• OGF 用于组合/划分，EGF 用于排列/有标号
• 卷积与 exp/ln 的生成意义
• 选择依据

OGF 的卷积对应"无标号对象的组合"（从 A 取 i 个、B 取 k−i 个的方案数乘积求和），EGF 的卷积对应"有标号对象的组合"（需乘组合数系数，把对象标号分配到两个集合）。何时用 exp/ln：exp 对应"把一个集合拆成若干同构部分"（即组合/置换的组合，如"集合的分拆"），ln 是其逆（从"所有组合"提取"连通单一分量"）。若对象是"无标号"（组合、划分）用 OGF；若对象"有标号"（排列、有标号图）用 EGF。exp/ln 用于描述"由多个独立部件组合成整体"与"从整体提取最小部件"的生成关系。

OGF 处理"无标号"（区分数量），EGF 处理"有标号"（区分对象本身）。exp 把"部件"组合成"整体集合"，ln 是逆运算提取"连通部件"。选型依据：对象是否带标号、计数是否区分排列。这是生成函数计数最核心的概念。

• 子集用 OGF（1+x）^n
• 排列用 EGF
• 循环/置换的 EGF 应用

子集计数：选/不选每个元素，OGF 为 (1+x)^n，系数 C(n,k) 即选 k 个的方案数。排列计数：n 个有标号元素的排列用 EGF，其生成函数为 Σ n! x^n/n! = 1/(1−x)（或涉及循环）。循环（置换的循环分解）：一个 k 循环的 EGF 为 x^k/k，多个循环组合用 exp，如"所有置换按循环分解"的 EGF 为 exp(Σ x^k/k) = 1/(1−x)。工程上把这些生成函数相乘/取 exp/取幂，用 NTT 计算系数，得到组合计数。OGF 与 EGF 的选择由"是否区分标号"决定。

子集用 OGF（无标号、选/不选），排列与循环用 EGF（有标号、需考虑排列顺序）。循环的 EGF 用 exp 组合，是"从个数到结构"的经典建模。工程上 NTT 快速算系数，把组合计数落到多项式运算。

• Catalan 数的生成函数方程
• 组合类（树、括号序列）建模
• 系数提取

Catalan 数 C_n 满足递推 C_n = Σ C_k C_{n−1−k}，其 OGF C(x) 满足 C(x) = 1 + x·C(x)²，解得 C(x) = (1 − √(1−4x))/2x。Catalan 数计数各类树、括号序列、三角剖分等。工程上把"组合类"建模成生成函数：例如"二叉树"是"空或 (根,左子树,右子树)"，其生成函数满足 C(x)=1+xC(x)²；"括号序列"同理。用多项式开方/牛顿迭代求 C(x) 的系数即得 C_n。这展示了"用生成函数方程描述组合类、再求系数"的通用工程流程。

Catalan 的生成函数方程来自其"递归结构"（空或分解为左右两部分），求解可用多项式开方（√(1−4x)）。工程应用是把组合类的递归定义翻译成生成函数方程，再通过多项式运算（开方、求逆、exp）提取系数。这是组合类统计的经典方法。

• CDQ 分治处理"左侧贡献右侧"的 DP/偏序
• 整体二分对"询问答案可二分"的批量查询
• 适用场景差异

CDQ 分治解决"左侧修改影响右侧查询"类问题（如三维偏序、DP 转移优化），核心是处理贡献/依赖的偏序关系，先处理左半再贡献右半。整体二分（Parallel Binary Search）解决"答案可二分、且修改可回滚"的批量询问问题（如区间第 k 大、带修改的 k-th 问题），做法是把所有询问在值域上二分，每次把值域一分为二，用一次数据结构扫描划分答案所在区间，递归处理。差异：CDQ 分治优化的是"转移/偏序贡献"，整体二分批量处理的是"答案二分"；CDQ 一次处理一个维度、整体二分处理值域。两者都离线、都 O((n+q)log n · 单次扫描开销)。

关键区别：CDQ 分治把"贡献"按时间/维度分治，解决依赖与偏序；整体二分把"询问答案"按值域分治，解决可二分答案的批量查询。适用性：CDQ 面向"修改→查询贡献"，整体二分面向"答案可二分 + 可回滚"。理解两者"分治的对象"（贡献 vs 答案）是区分的关键。

• 卷积形式识别
• CDQ 分治批量贡献
• O(n log² n) 推导

转移 dp[i]=Σ_{j<i} dp[j]·g[i−j] 本质是卷积（但 dp 依赖自身，需逐步计算）。CDQ 分治：处理 [l,r]，先递归算 [l,mid] 的 dp，再用一次卷积把左半 dp 对右半的贡献批量算出（取 dp[l..mid] 与 g 卷积，把结果按偏移加到右半对应位置），再递归右半。每层做一次卷积 O(n log n)，log n 层，总 O(n log² n)。相比直接转移 O(n²)，大幅优化。要点：卷积附带偏移（i−j 的索引）与边界处理。

分治 FFT 把"逐步依赖"的 DP 用卷积批量加速：左半贡献一次性卷积算给右半。CDQ 层数 log n，每层卷积 O(n log n)，故 O(n log² n)。这是"卷积优化 DP"的经典范式，注意与整体二分、普通分治 FFT 的区别。

• 构造 OGF
• 化为闭式（有理函数）
• 部分分式展开求通项

斐波那契 F_n=F_{n−1}+F_{n−2}, F_0=0,F_1=1。设 OGF F(x)=Σ F_n x^n。由递推式：F(x) = x + x(F(x)) + x² F(x)（把 F_{n−1} 对应 xF(x)，F_{n−2} 对应 x²F(x)），解得 F(x) = x/(1−x−x²)。把分母 1−x−x² 因式分解，部分分式展开为 F(x) = A/(1−αx) + B/(1−βx)，其中 α,β 是特征根（1±√5）/2。展开 1/(1−αx)=Σ α^n x^n，得到通项 F_n = A·α^n + B·β^n = (α^n−β^n)/√5。标准流程：递推式 → OGF 方程 → 解出闭式 → 部分分式 → 通项。

生成函数把递归转化为代数方程，闭式是有理函数，部分分式展开利用 1/(1−αx)=Σα^n x^n 提取系数。斐波那契通项 (φ^n−ψ^n)/√5 即由此而来。这是用生成函数解线性递推的标准模板。

• 线性递推的生成函数有理式
• 特化 x 的幂次（奇偶分离）
• 复杂度 O(k log k log n)

线性递推序列 a_n 满足某 k 阶线性方程，其生成函数是 P(x)/Q(x)（P 次数<k，Q 次数=k）。Bostan-Mori 算法求第 n 项：利用恒等式 a_n = [x^n] P(x)/Q(x)，通过反复把 x 特化为 x² 并分离奇偶项，把"求 [x^n]"降到"求 [x^{(n−d)/2}]"，每次把 Q 变换为 Q(x)Q(−x)（只保留偶次），P 相应变换，次数保持 k。每步 O(k log k)（一次多项式乘法），需要 O(log n) 步，总 O(k log k log n)。这是求线性递推第 n 项（n 巨大）的最优方法之一。

Bostan-Mori 的核心是"奇偶分离"：把 [x^n] 的指数 n 每步减半（类似二进制），同时保持有理式形式，只需要 O(log n) 步、每步 O(k log k) 的多项式运算。相比矩阵快速幂 O(k³ log n) 或 O(k² log n)，Bostan-Mori 在 k 大时优势明显。

• 前缀和 / 卷积的转移形式
• CDQ 每层批量贡献
• 复杂度推导

前缀和卷积形式如 dp[i] = Σ_{j<i} dp[j]·g[i−j]（或带前缀和约束）。CDQ 分治处理 [l,r]：递归左半算出 dp[l..mid]；构造卷积数组，把左半 dp 与 g 卷积，卷积结果中对应位置 i∈[mid+1,r] 的项即左半对 dp[i] 的贡献，累加到右半；再递归右半。每层做一次长度为 O(r−l+1) 的卷积，代价 O((r−l+1) log(r−l+1))，sum 到全 n 为 O(n log n) 每层，log n 层总 O(n log² n)。推导：总代价 = Σ_{层} O(n log n) = O(n log² n)。

复杂度推导的关键是"每层卷积总代价 O(n log n)"（各区间卷积长度之和 ≤ n，各带 log 因子），乘 log n 层得 O(n log² n)。前缀和形式的卷积只是索引偏移细节，不影响复杂度。

• 组合类生成函数方程的求解
• 分治乘法/牛顿迭代
• 系数提取

组合类（如 Catalan 的二叉树、括号序列）的计数等价于求其生成函数方程的系数。工程实现路径：先写出生成函数方程（如 C(x)=1+xC(x)²），再用多项式运算求解——二次方程用多项式开方（牛顿迭代），得到 C(x)=(1−√(1−4x))/2x；对一般组合类方程，用牛顿迭代/分治乘法求解系列系数。分治 FFT 用于高效计算方程中的多项式乘法，把系数提取做到 O(n log n) 或 O(n log² n)。最终系数即组合计数。

组合类计数 = 生成函数方程 + 多项式求解。求解方式取决于方程类型：线性/有理式用求逆，二次用开方，一般用牛顿迭代。分治 FFT/多项式乘法是底层运算，保证系数计算高效。工程路径："建模 → 列方程 → 多项式求解 → 取系数"。

• 浮点 FFT 的误差来源
• 误差界与值域控制
• 拆分系数（拆大数）

浮点 FFT 用 double 处理复数，误差来自旋转因子与加法乘法的舍入，随 n 增长而累积。工程上控制误差：用 long double 或放大精度的基底；限制系数大小与 n 的规模；当系数的卷积结果可能超出 double 精确表示范围时，用拆分系数（拆系数）法——把系数 a 拆成 a1·B+a0，分别做 4 次（或 3 次）FFT 卷积，再组合，使中间值保持在 double 精确范围内。误差界：double 约 15~16 位有效数字，卷积最大值需在约 10^15 内才可靠。工程上常结合"四舍五入"处理。

浮点 FFT 的误差随 n 与系数增大而上升，需在"值域可控"下使用。拆分系数把大系数分解为小系数卷积，使中间值在 double 精度内，既保证精度又保留 FFT 的 O(n log n) 速度。当需要整数精确结果时，用 NTT 替代。

• Schönhage-Strassen 的 FFT 大整数乘法
• 三次迭代 NTT 的归约
• 工程复杂度

Schönhage-Strassen 算法用 FFT 乘大整数：把两个大整数视为多项式，做 FFT 卷积得到卷积系数，再进位还原成整数。其对超大整数复杂度 O(n log n log log n)，是理论最优之一。三次迭代 NTT 指把"一个大整数乘法"通过"把数拆成若干位、用 NTT 做序列卷积"实现，即用 NTT（而非浮点 FFT）做卷积以保证整数精确，配合进位处理。工程上：把大整数按 2^b 分块成多项式，做 NTT 卷积，再处理进位（处理"卷积系数可能大于 2^b"的进位）。两者都基于"卷积 + 进位"，区别在底层用 FFT 还是 NTT。

大整数乘法 = 多项式卷积 + 进位。Schönhage-Strassen 用 FFT 卷积（浮点），三次迭代 NTT 用 NTT 卷积（整数精确）。工程上对超大整数，NTT 因无精度问题更稳，但需处理进位与模数范围。两者都是竞赛/库中实现大整数乘法的底层算法。

• 预计算旋转因子
• 减少取模次数
• 内存与缓存优化

三次迭代 NTT 的常数优化：预计算旋转因子表（避免每轮重复 pow 求幂）；用加/减与条件取模代替每步取模（% 慢）；内层循环用局部变量与位运算；对固定 n 直接分层展开；用数组连续存储提升缓存；乘法用 long 累加减少溢出。复用优化：把三次 NTT（正变换、点乘、逆变换）的共用部分复用，减少变换次数。工程上还常用"无乘法替换"（部分旋转因子为 ±1、±i）与蝶形变换优化减少运算。这些把常数压到很低，支撑大规模卷积。

NTT 常数主要来自取模与求幂。预计算旋转因子 + 条件取模 + 局部变量 + 缓存友好数组，是三大关键优化。整形运算（long）与位运算替代慢速除法，能显著提速。三次迭代 NTT 在竞赛与高性能库中常人工优化到极低常数。

• 树形 DP 的卷积转移
• 分治 FFT 批量计算
• 工程实现

树形 DP 与卷积结合的典型是：合并子树的 DP 状态时，需要做"卷积"（如树上背包：dp[u][k] = Σ dp[u][i]·dp[v][k−i]）。分治 FFT 用于高效计算这些卷积：把子树合并的转移用多项式乘法批量加速，或用"树上分治"（点分治）把树形问题转化为序列问题后分治 FFT。工程上：识别转移为卷积形式，用 NTT 做多项式乘法，插入/合并子树时维护多项式并快速卷积。复杂度 O(n log² n)。

树形 DP 的转移若为卷积（树上背包），直接合并 O(n²)，用分治 FFT/多项式卷积优化到 O(n log² n)。工程上需把树形 DP 的"合并"识别为卷积，使用 NTT，并处理合并顺序与多项式维护。这是树形 DP + 多项式的高级结合。

• OGF 无标号，EGF 有标号
• 形式幂级数运算
• 计数应用

OGF（普通生成函数）用于无标号对象（组合、划分），系数含义是"方案数"；EGF（指数生成函数）用于有标号对象（排列、有标号图），系数含 1/n! 因子，用 exp 处理"标号组合"（如集合分拆、置换循环）。形式幂级数把生成函数当作可做加减乘除、微积分、exp/ln 的代数对象，计数题中用其运算（乘法对应组合、exp 对应多部件组合、ln 对应连通提取）提取目标系数。选型：对象无标号用 OGF，有标号用 EGF；"组合类"用形式幂级数运算求解系数。

OGF/EGF 的区别在于"是否区分标号"，形式幂级数是运算框架。工程上把计数问题建模为生成函数，用多项式运算（NTT、exp、ln、求逆）求系数。这是生成函数计数的完整方法论。

• 多项式复合的意义
• 复合逆（拉格朗日反演）
• 形式幂级数运算的边界/条件

多项式复合 f(g) 用于"用 g 替换 f 的变量"，在计数题中用于"组合类的替换"（如把叶子替换成树）与"多重组合"。复合逆（拉格朗日反演）用于求"隐式定义的生成函数"的系数：若 y = x·φ(y)，则 [x^n] y（或组合类的计数）可由拉格朗日反演公式 O(n log n) 求出。形式幂级数运算的边界：只有常数项可逆时才可求逆（ln/exp 有条件），复合的前提是内层函数常数项为 0（否则 x^n 项无穷多），运算需在形式幂级数定义域内（截断到 n 次）。计数问题中还要验证组合类定义合法（无歧义、非负）。

多项式复合与复合逆是处理"隐式/递归组合类"的利器（拉格朗日反演）。形式幂级数的运算边界：常数项条件（求逆非零、exp 需常数项 0、复合需内层常数项 0）、截断到 n 次、模数友好。理解这些边界是正确使用多项式运算的前提。

• 贡献单调方向（左侧影响右侧）
• 可离线、贡献可批量计算
• 转移可卷积/可快速贡献

CDQ 分治适用条件：DP 转移是"左侧贡献影响右侧"（即 dp[i] 只依赖 j<i 的 dp[j]，方向一致），且可离线处理（知道所有转移），且左侧对右侧的贡献可"批量快速计算"（如卷积形式，或可用数据结构 O(log n) 贡献）。满足这三条时，可用 CDQ 分治：先处理左半、左半批量贡献右半、再处理右半，把 O(n²) 降为 O(n log² n) 或 O(n log n)。若依赖方向混乱（双向）或无法离线或贡献不能批量，则不适用。

CDQ 分治的三要素：单向依赖、可离线、可批量贡献。它把"每个 j 对每个 i 贡献"的 O(n²) 用"左半对右半一次批量贡献"替代。若依赖有环或双向，需先转换成单向（如拓扑序）。边界：贡献必须可叠加、可合并，才能用卷积或数据结构批量。