长链剖分、NTT/CRT 与多项式操作

• 任意图与连通图的指数生成函数关系：G = exp(C)，C = ln(G)
• 集合幂级数乘法即子集卷积（按 popcount 分层）
• O(n²·2^n) 的来源：n 层 popcount × 每层 O(2^n) FWT

在集合幂级数框架下，设 F(S) 为顶点集 S 上的任意图数量，C(S) 为 S 上的连通图数量。任意图由若干连通分量组成，而连通分量是 SET 构造（无标号顺序的组合），因此 F = exp(C)，即 C = ln(F)。集合幂级数的乘法正是子集卷积：两个函数 A、B 的子集卷积定义为 (A*B)(S) = Σ_{T⊆S} A(T)·B(S\T)，它等价于把函数按 popcount 分层（A_k(mask) = A(mask)·[popcount(mask)=k]），逐层做 FWT 后逐点相乘，再做逆变换并归位。exp/ln 在子集卷积意义下用幂级数展开 + 牛顿迭代（或直接按"ln 的导数形式"递推）实现，每次乘法 O(n·2^n)（n 层 × 每层 FWT O(2^n)），共需 O(n) 次乘法，故总复杂度 O(n²·2^n)。

本题考察"组合构造 ↔ 生成函数"的双向翻译：连通分量是任意图的分量分解，对应 SET 构造的 exp；反过来 ln 做连通性拆分。回答时先建立 F = exp(C) 的组合意义，再讲子集卷积的 popcount 分层实现与复杂度来源。

• 长链按"子树最大深度"剖分，链长之和 = n
• 重儿子（长儿子）数组指针复用、轻儿子暴力合并
• "每个节点作为轻链成员只被合并一次"的复杂度论证

长链剖分按"子树最大深度"划分长儿子：对每个节点取深度最大的儿子作为长儿子，长儿子链形成长链，其余儿子各自开新链。深度相关 DP（如统计子树内各深度信息）在合并时，长儿子的数组直接复用（指针移位或直接继承），轻儿子则按深度逐点暴力合并进长链数组。复杂度论证的关键是"链长之和 = n"：每条长链只在链顶与父链合并一次，合并代价等于该链长度，因此所有合并的总代价 = Σ 链长 = n，总复杂度 O(n)，且空间 O(n)（深度数组大小 = 最长链长）。相比每次合并都复制整个数组的朴素 O(n²)（或按 size 启发式合并的 O(n log n)），长链剖分利用了"深度有界"的结构——轻链深度严格小于承接它的长链，天然满足小并大的摊还。

本题考察"按什么维度剖分"的直觉：重链剖分按子树大小（服务于路径与子树操作），长链剖分按最大深度（服务于深度相关 DP）。回答时说明长儿子定义、数组复用技巧与"链长总和 = n"的复杂度论证。

• 分治：把求值点集对半分裂，构造区间乘积多项式
• 关键性质：P mod (x-x_i) 的常数项恰为 P(x_i)
• 多项式取模（多项式除法）的 O(n log n) 实现

多点求值把 n 个点 x_1...x_n 对半分成两组，预先用分治构造每个区间的乘积多项式 M(L, R) = Π_{i=L..R} (x - x_i)（用 NTT 乘起来，总预处理 O(n log² n)）。核心性质：对任意多项式 P，P(x_i) 等于 P 对 (x-x_i) 取模的余式常数项；更一般地，当区间内的点都满足 M(x_j) = 0 时，P mod M 在这些点上的取值与 P 相同，且次数被压到 |M|-1 以下。于是分治递归：把 P 传给左半区间时替换为 P mod M(左半)，传给右半区间替换为 P mod M(右半)，到叶子即得 P(x_i)。每层取模用"多项式除法"（系数反转 + 求逆 + 乘法）实现 O(n log n)，分治树共 O(log n) 层，总复杂度 O(n log² n)。该技巧的另一种等价描述是"余数定理 + 分治乘积树"。

本题考察多项式取模在求值中的杠杆作用：模区间乘积多项式把次数按点集规模减半，使递归深度只有 O(log n)。回答时先构造乘积树，再讲清"P mod M 与 P 在区间点上取值相同"的性质，最后给出每层取模的复杂度与总界。

• SOS DP 递推式 dp[mask] 逐位扩展与 FMT 的等价性
• 子集和（min 卷积侧）：沿低位到高位做前缀累加
• 超集和：沿高位到低位做后缀累加，方向相反

SOS DP 与 FMT 是同一算法：子集和变换 F(mask) = Σ_{T⊆mask} f(T) 可用 O(n·2^n) 的递推实现——按位枚举 i，dp[mask] += dp[mask ^ (1<<i)]（当 mask 含第 i 位时），其本质是对 n 维布尔超立方体做高维前缀和，这正是 FMT 的正变换（变换矩阵为 [[1,1],[0,1]]）。超集和 G(mask) = Σ_{T⊇mask} f(T) 则是高维后缀和，递推方向相反：dp[mask] += dp[mask | (1<<i)]（当 mask 不含第 i 位时），对应 FMT 的另一种变换方向。方向差异的实质：子集和沿"维度的低方向"累加（包含关系 T⊆mask 意味着逐位 ≤），超集和沿高方向累加（逐位 ≥），两者矩阵互为转置。工程上可用同一循环、通过是否含位来控制方向。

本题考察 FMT/SOS DP 的统一视图：都是高维（位维）前缀/后缀和。回答时给出两个递推式的方向差异，说明与变换矩阵 [[1,1],[0,1]]（子集）和 [[1,0],[1,1]]（超集）的对应，最后点出复杂度 O(n·2^n)。

• 子集卷积定义：T 与 S\T 不相交且并集为 S
• 直接用 FWT 的混淆问题：FWT 允许交集非空
• 占位多项式按 popcount 分层 + FWT 逐层乘 + 逆变换

子集卷积 (fg)(S) = Σ_{T⊆S} f(T)·g(S\T) 要求 T 与 S\T 不相交且恰好拼成 S。若直接对 f、g 做 FWT（子集和）后逐点相乘再逆变换，得到的卷积是"允许重叠"的（T 与 U 可交集非空），即 (fg)(S) 中混入了 T∪U = S 但 T∩U ≠ ∅ 的项，故不能直接用 FWT。占位多项式解法：引入占位维度 k = popcount，把 f 扩展为 F[k][mask] = f(mask)·[popcount(mask) = k]；子集卷积中两项的 popcount 相加恰好等于结果的 popcount（因为不相交），于是对每个 k 层做 FWT 后，按 Σ_{i+j=k} F[i]·G[j] 逐点卷积（这是普通多项式乘法，O(n) 每点），再逆 FWT 并按 popcount 归位。总复杂度：n 层 FWT 每层 O(n·2^n) 预处理，逐点多项式乘 O(n²·2^n)，故总 O(n²·2^n)。

本题考察"维度的语义约束"：子集卷积的合法性由 popcount 等式约束，占位维度正是把该约束编码进计算。回答时先指出直接 FWT 的混淆缺陷，再讲分层 + 逐点多项式乘 + 逆变换的三步实现与复杂度来源。

• O(3^n) 子集枚举：实现简单、常数小、n ≤ 18-20 可过
• O(n²·2^n) 子集卷积：实现复杂、但 2^n 主项更小
• 判断标准：n 与 3^n vs n²·2^n 的交叉点及常数对比

O(3^n) 枚举（对每个 mask 枚举其子集，总枚举量 Σ 2^popcount = 3^n）实现只需两层循环，常数极小，n = 18 时 3^18 ≈ 3.9e8 次基本操作，配合剪枝在多数竞赛时限内可过；n = 20 时 3^20 ≈ 3.5e9 已很吃力。O(n²·2^n) 子集卷积：n = 20 时 n²·2^n ≈ 400 × 1e6 = 4e8，主项略优，但每步涉及 FWT 的蝶形运算与分层数组，常数是枚举的 5-10 倍，且实现与调试成本高。工程取舍：n ≤ 18 优先 O(3^n) 枚举；n = 19-20 且时限紧、优化充分时考虑子集卷积；若 DP 有单调性/剪枝可进一步降枚举量（如枚举补集、只枚举含最低位的子集减半）。此外 O(3^n) 内存 O(2^n)、子集卷积需 O(n·2^n) 内存，也是选择依据。

本题考察"复杂度渐近 vs 常数"的工程判断：3^n 与 n²·2^n 在 n ≤ 20 区间差距有限，常数与实现成本往往更关键。回答时给出两方案的复杂度、常数特征、内存与实现难度，并给出 n 的分档建议。

• XOR 卷积的变换矩阵 [[1,1],[1,-1]] 及其逆矩阵
• 逆变换 = 正变换矩阵乘 1/2（自逆性）
• 蝶形运算（加/减）O(n log n) 的实现

XOR 卷积要求 FWT(f) 逐点乘后逆变换得卷积，核心是构造满足"变换把 XOR 变成逐点乘"的矩阵。取 H = [[1,1],[1,-1]]：对二维向量 (a,b)，H 作用后 XOR 卷积在两个"特征方向"上解耦——因为 H 的每一行是 XOR 群上的一维表示（H 的第 1 行对应平凡表示，第 2 行对应符号表示 χ(t) = (-1)^{t}）。验证：H 是自逆的（H² = 2I），故逆变换矩阵为 H/2，即逆变换 = 对每层蝶形做同样的加/减，最后全体乘以 1/2^n 维因子（等价地每维乘 1/2）。正变换蝶形：a' = a + b, b' = a - b，对 n 维逐维应用，复杂度 O(n·2^n) = O(n log N)（N = 2^n）；逆变换同样蝶形后乘 1/2。FWT 的正确性还可由"点值乘积定理"证明：FWT(f)·FWT(g) 逆变换后每项恰为 XOR 卷积。

本题考察变换的本质——矩阵行是群的表示、自逆矩阵给出逆变换。回答时先写矩阵与蝶形公式，再解释 1/2 来自 H² = 2I，最后给出复杂度与实现要点。

• 直接 CRT：对模两两互素时用逆元逐项合并
• Garner：混合基数表示，逐项减去已确定部分再求逆
• 增量合并：Garner 在"新模数非互素/模数动态增长"下的优势

直接 CRT 适用于模数两两互素：设 M = Π m_i，对每个 i 求 M_i = M/m_i 与逆元 inv_i = M_i^{-1} mod m_i，答案 x = Σ a_i · M_i · inv_i mod M。Garner 算法把 x 表示成混合基数 x = x_0 + x_1·m_1 + x_2·m_1·m_2 + ...，逐个模方程确定系数：已确定前 k-1 个系数后，x_k = (a_k - 当前部分和) · inv_k mod m_k，其中 inv_k 是 (m_1·m_2···m_{k-1}) 在模 m_k 下的逆元。Garner 的优势：其一，系数逐个确定、无需一次性计算所有 M_i 的大整数乘法（适合模数很大的实现）；其二，可增量合并——新方程加入时只需对新模数求一次逆并更新系数，而直接 CRT 需要重算所有 M_i 与逆元；其三，结果天然保持混合基数形式，便于逐项取模与比较大小。

本题考察两种 CRT 实现的结构差异：直接 CRT 是"求和式"，Garner 是"递推式"。回答时给出两者的构造公式，说明 Garner 逐项确定系数、增量扩展的自然性，并指出其在大数与非互素场景的工程优势。

• 长链剖分 + 链顶"上跳表"（up 数组只存链顶祖先）
• 先跳一步使剩余 k' < 链长，再沿链内数组 O(1) 定位
• 预处理 O(n log n)（轻量版 O(n)）与查询 O(1)

长链剖分求 k 级祖先的经典实现：预处理每条长链，链顶额外维护一个"向上跳数组"（存储链顶的 2^j 级祖先，只对链顶存，总大小 O(n log n)）；查询 u 的第 k 级祖先时，先利用二进制分解跳到某个链顶 t（剩余步数 k' < len(链 t)），此时第 k' 级祖先必在同一条链内，可用链内顺序数组 O(1) 定位。正确性依赖长链性质：任意节点沿轻边上跳后，所在链长严格大于已跳步数。预处理：一次 DFS 求长儿子与链长 O(n)，链顶的跳表共 O(n log n) 空间/时间；查询 O(1)。与倍增（预处理 O(n log n)、查询 O(log n)）相比，长链版以 O(n log n) 空间换 O(1) 查询，适合海量祖先查询（如配合后缀树/虚树）；倍增实现更简单、常数小，适合查询次数一般的场景。另有"长链上跳 + 倍增结合"的混合方案折中。

本题考察长链剖分的经典应用：链长之和 = n 使"跳一步后链内 O(1) 定位"成立。回答时先讲预处理结构，再论证查询两步（跳链顶 + 链内定位）与复杂度，最后与倍增对比选型。

• 长儿子数组"头指针"直接继承（dfn 序或指针池）
• 轻儿子数组开新内存、合并后释放
• 每层数组总长 = 链长，所有链长之和 = n

深度相关 DP 中每个节点需要一个长度为"子树最大深度"的数组。朴素实现每节点 new 数组并复制合并，总空间 O(n²)、时间 O(n²)。指针复用技巧：为所有节点预先分配一段连续内存（dfn 序即"长链数组顺序"），深度 DP 数组按节点深度偏移：节点 u 的数组起始位置 = 它在长链中的 dfn 位置，长儿子的数组起始位置恰好是 u 的 +1（因为同链 dfn 连续），因此 u 继承长儿子数组时只需把指针加 1、无需任何复制；轻儿子则各自在链顶分配新段，合并时逐深度累加进 u 的数组。复杂度论证：每个节点深度 DP 数组的长度等于所在长链在它之下的长度，所有长链长度之和 = n，故总空间 O(n)；轻儿子合并的总代价 = Σ 轻链长度 = O(n)，时间 O(n)。

本题考察"分配策略消除复制"的工程思想：dfn 连续分配使继承变成指针移位。回答时讲清连续内存布局、长儿子 +1 继承、轻儿子新段合并三步，再用链长之和 = n 给出空间与时间上界。

• 异或卷积建模：计数数组的 XOR 卷积 = 方案数
• 每选一个数 = 乘一次计数数组，FWT 后逐点幂
• 逆变换与最终答案提取

FWT 的典型场景是"组合选择 + 异或/与/或运算"的计数：设 f[x] 为可选数字中等于 x 的个数，则从集合中选两个数（可重复）异或值为 y 的方案数正是 f 与 f 的 XOR 卷积 (f*f)(y)；选 t 个数异或值为 y 的方案数是 t 次卷积 f^(*t)(y)。由于 FWT 把 XOR 卷积变成点乘，FWT(f) 后逐点做 t 次幂，再逆变换即得所有异或值的方案数：FWT(f)^t 逆变换后第 k 项即为答案。若要求"每个数至多用一次"，则对每个可选值独立处理（或按生成函数 (1 + x^{a_i}) 在 XOR 域上的乘积，用"逐个数更新点值"的 FWT 技巧 O(n·2^n) 完成）。实现注意：模素数（如 998244353）下求逆元做幂；答案取模；n 维数组长度 2^n。

本题考察"卷积语义 ↔ 组合计数"的对应：异或卷积对应"异或和的分发"。回答时先建模 f 与 t 次卷积，再讲 FWT 点乘幂 + 逆变换的流程，最后给出可重复/不可重复两种变体的处理差异。

• 2^23 规模下蝶形运算次数 n log n / 2 与模乘开销
• 循环展开、预计算旋转因子表、按 4/8 步蝶形
• 内存局部性：分段计算、避免随机访问旋转因子

NTT 在 n = 2^23 时蝶形运算总数约 (n/2)·log n ≈ 2^22 × 23 ≈ 9.6e7 次，每次蝶形含一次模乘（64 位乘法 + 取模）。最坏情况常数因子来自三处：模乘取模操作（% 比乘法慢数倍）、旋转因子的随机访问（2^23 规模下因子表 16-32MB，超出 L2/L3 造成缓存缺失）、递归/迭代的跳转分支。常用优化：1) 预计算旋转因子表并分块（8 路分块减少跳变）；2) 4 步/8 步蝶形（每步处理 4/8 个点，旋转因子复用，减少乘法与取模次数）；3) 循环展开 + 对齐访问；4) 使用 Montgomery 乘法或 Barrett 约减把取模换成乘法；5) 对 2^23 的 DFT 可拆成两维（如 2^11 × 2^12 的矩阵转置型 NTT，利用 cache block 提高局部性）；6) 用 unsigned long long 累积避免每次取模。实测优化后可达原生 FFT 常数的 2-4 倍。

本题考察大 NTT 的工程优化：瓶颈在模乘取模与缓存局部性。回答时先算蝶形总量给"最坏情况"量化，再按"减少取模、预计算因子、分块布局"三类手段展开，最后给出规模与缓存关系的判断。

• 三种 FWT 卷积允许"重叠"：T∩U 可非空
• 子集卷积要求 T 与 S\T 不相交
• 占位多项式按 popcount 分层编码"不相交"约束

FWT 的三种卷积（XOR/AND/OR）的定义都是 (f*g)(S) = Σ_{T⊕U=S} f(T)·g(U)（或 T∪U、T∩U），其中 T 与 U 可以相交——例如 OR 卷积中 T∪U = S 时允许 T∩U ≠ ∅。而子集卷积要求 T 与 S\T 互不相交且并集恰为 S，即 T∩U = ∅、T∪U = S。直接对 f、g 做 OR-FWT 逐点乘再逆变换，得到的每一项都混入了"重叠子集对"的贡献，无法分离，故三者都不能表达子集卷积。解决方式是引入占位多项式：把 f 按 popcount 分成 n+1 层 F[k][mask]，在 FWT 后逐点对"层号相加"做多项式乘法（Σ_{i+j=k} F[i]·G[j]），利用"不相交子集的 popcount 相加等于并集 popcount"这一等式把重叠项排除（重叠子集的 popcount 之和严格大于并集 popcount），从而得到正确的子集卷积，复杂度 O(n²·2^n)。

本题考察对"卷积定义域约束"的理解：FWT 系卷积没有"不相交"约束，popcount 等式是编码该约束的钥匙。回答时先用例子说明重叠混淆，再讲占位多项式如何借 popcount 等式过滤重叠项。

• 递归版分治到迭代版合并时输入顺序的变化
• bit-reversal 置换的 O(n) 实现（循环交换）
• 原地蝶形：用临时变量两两更新，无需额外数组

递归版 NTT 每次把序列按奇偶下标分裂（Decimation in Time），递归到底层后各元素顺序变为"下标二进制位反转"后的顺序；迭代版自底向上合并时，若不重排，蝶形两两配对的"间距"不再规则，因此需要先做 bit-reversal 置换：rev[i] 由 i 的二进制位反转得到，交换 a[i] 与 a[rev[i]]（仅当 i < rev[i] 时交换一次），O(n) 时间、O(n) 空间（rev 数组可复用）。原地蝴蝶运算：迭代版按"长度 2、4、8..."逐层合并，每层对每组做蝶形 a[i] += w·a[i+len/2], a[i+len/2] -= w·a[i+len/2]（先存临时变量再写回），只依赖同一组内的两个位置，天然原地，不需要额外数组；旋转因子 w 每层预计算。若采用 Cooley-Tukey 的"位反转 + 蝶形"流程，还需注意逆变换的旋转因子取共轭并整体乘 n^{-1}。空间优化：rev 数组也可原地生成（增量计算），使额外空间 O(1)。

本题考察 NTT 实现的两个工程细节：顺序问题（位反转）与空间问题（原地蝶形）。回答时先解释递归→迭代的顺序变化来源，再给出位反转交换与蝶形的原地实现，最后提逆变换的收尾细节。

• SET 构造（无标号顺序的组合类）对应 exp
• 任意图 = 连通分量的无序集合：F = exp(C)
• 对偶：C = ln(F)，连通化=取对数

在组合计数中，若一个组合类由"若干个连通分量组成"，且分量之间无序（SET 构造），则其生成函数等于分量生成函数的指数：F = exp(C)。连通图正是任意图的"构件"：任意图可唯一分解为一组连通图的无序集合，故任意图计数 F = exp(C)，其中 F(S) 为顶点集 S 上的任意图数、C(S) 为连通图数。反之 C = ln(F)：由任意图数反推连通图数。在集合幂级数（子集卷积）意义下，exp 定义为 Σ C^⊗k / k!（子集卷积幂 + 除以 k! 抵消无序计数），ln 由 exp 的逆推出。应用实例：n 个顶点带标号图中，F(S) = 2^{C(|S|,2)} 已知，用集合幂级数 ln 即可求出任意 S 上的连通图数；反过来知道连通图数可用 exp 得到任意图数。该对偶同样适用于"有向图/强连通分量""树/森林"等分解结构。

本题考察"组合分解 ↔ 生成函数运算"的翻译：无序集合对应 exp，有序排列对应乘方。回答时先讲 SET 构造与 exp 的对应，再给出 F = exp(C) 的双向使用（连通计数/任意图计数），最后举例说明 ln 的用法。

• OR 变换 = 子集和（后缀/前缀）变换矩阵 [[1,1],[0,1]]
• AND 变换 = 超集和变换矩阵 [[1,0],[1,1]]
• 逆矩阵分别为 [[1,-1],[0,1]] 与 [[1,0],[-1,1]]（无 1/2 因子）

XOR、AND、OR 三种 FWT 对应三种"位运算卷积"，变换矩阵不同：OR 卷积的变换是子集和（高维前缀和）：对二位向量 (a,b)，正变换 (a+b, b)，矩阵 [[1,1],[0,1]]——因为 OR 卷积要求按"包含关系"求和（T∪U = S 的系数由子集关系决定）；AND 卷积的变换是超集和（高维后缀和）：正变换 (a, a+b)，矩阵 [[1,0],[1,1]]——AND 对应超集包含关系（T∩U = S 时 T、U 都是 S 的超集）。两者的逆变换分别为 [[1,-1],[0,1]] 与 [[1,0],[-1,1]]，即正变换后做一次"差分"还原，不需要 1/2 因子（与 XOR 不同，XOR 的矩阵 [[1,1],[1,-1]] 自逆，逆变换须乘 1/2）。蝶形实现：OR 每维做 a += b（子集和），AND 每维做 b += a（超集和），方向差异正是矩阵三角结构的来源。

本题考察三种 FWT 的统一视图：变换矩阵由对应位运算的包含关系决定。回答时分别给出 OR/AND/XOR 的矩阵、蝶形方向与逆变换差异（有无 1/2），最后说明为何 XOR 需要缩放而 AND/OR 不需要。

• 递推式语义：只考虑前 i 位可变的子集累加
• 滚动数组优化为单层 mask 循环
• 与 FMT 逐位蝶形 a += b 的等价论证

SOS DP 求 F[mask] = Σ_{sub ⊆ mask} f[sub]：设 dp[mask][i] 表示"仅允许前 i 位（最低 i 位）与 mask 不同（其他位必须等于 mask 对应位）的子集之和"，递推 dp[mask][i] = dp[mask][i-1] + dp[mask^(1<<i)][i-1]（当 mask 第 i 位为 1；为 0 时 dp[mask][i] = dp[mask][i-1]）。滚动数组去掉 i 维后为：for i in 0..n-1: for mask: if mask 含第 i 位: dp[mask] += dp[mask ^ (1<<i)]。这恰是 FMT 子集和正变换的蝶形：FMT 对第 i 维做矩阵 [[1,1],[0,1]] 作用，等价于把"第 i 位为 1 的项"加上"第 i 位为 0 的项"，与 SOS 递推完全一致；最终 dp[mask] 即所有子集之和。因此 SOS DP 就是 FMT（OR 卷积正变换）的滚动数组实现，二者时间复杂度同为 O(n·2^n)、空间 O(2^n)，可互相印证与复用。

本题考察"递推式与矩阵变换"的同一性：同一算法两种表述。回答时先解释 dp[mask][i] 的语义与递推方向，再滚动优化，最后逐维对照 FMT 蝶形说明等价性。

• 分治乘积树 M(L,R) = Π (x - x_i) 的构建
• 每层对左右半区间做多项式取模（模逆 + 乘法）
• 复杂度：每层 O((n+m) log(n+m)) × O(log n) 层

多点求值先把 n 个点建成线段树状的乘积多项式树：叶子为 (x - x_i)，父节点为左右乘积（NTT 乘法），整树预处理 O(n log² n)。递归求值时，当前多项式 P 传入区间 [L, R]，先计算 P mod M(左半) 传入左子树、P mod M(右半) 传入右子树——因为 M 在区间所有点上取 0，P 与 P mod M 在这些点上取值相同，且余式次数 < |M|，从而递归中多项式次数按点集规模减半。到达叶子时 P mod (x - x_i) 的常数项即 P(x_i)。多项式取模实现：A mod B 用"系数反转 + 求逆 + 乘法"完成——rev(A) = rev(B)·Q 的商多项式，再 A - B·Q 得余式，其中求逆用牛顿迭代 O(d log d)。每层所有区间取模总复杂度 O((n+m) log(n+m))（每点分摊 O(log)），共 O(log n) 层，总 O((n+m) log²(n+m))。

本题考察"取模降次"在分治中的作用：每次递归把次数压到点集规模，保证每层总代价线性对数。回答时按"乘积树构建 → 取模降次递归 → 取模实现（反转+求逆+乘法）→ 复杂度分层求和"四步展开。

• 形式幂级数 ln(1+F) = Σ (-1)^{k+1} F^k/k 的定义域约束
• 常数项必须为 1（或单位），否则需先提取
• 复数分支切割：ln 的多值性在形式幂级数下的处理约定

多项式 ln 在形式幂级数意义下定义为 ln(P) = ∫ P'/P，其收敛性要求常数项为单位（一般约定常数项为 1；若为 c ≠ 1，则 ln(P) = ln c + ln(P/c)，其中 ln c 是普通常数对数，需要在实际数域或复数域取定一个分支）。工程实现：先判常数项是否为 1（不是则提取 ln c 并缩放），然后对 P 求导得 P'，用多项式求逆得 1/P，二者卷积后积分（逐项除以次数）得到 ln(P)，复杂度 O(n log n)。关于复数与负数：多项式系数通常限定在模素数域（如 998244353），不存在"复数分支"问题；若在复数域实现（如浮点多项式），ln 的多值性要求固定分支——约定主值分支（幅角取 (-π, π]），且要求 P 在单位圆盘内无零点（所有根的模 > 1）才保证解析；对负数常数项，ln 的虚部取 π 还是 -π 属于约定，需与求逆/卷积的域一致。竞赛语境下记住"常数项必须为 1"这一硬约束即可。

本题考察形式幂级数与解析函数的分野：多项式 ln 是代数对象（导数/积分定义），分支问题只在浮点复数实现中出现。回答时先给出 ∫P'/P 的公式与常数项约束，再分"模域实现"与"复数实现"两种场景说明分支约定。

• 牛顿迭代：F ← (F + G/F)/2 的形式幂级数版本
• 常数项需为二次剩余（模素数域）
• 每步迭代长度翻倍，总复杂度 O(n log n)

求 F 使 F² ≡ G (mod x^n)（多项式开方）用牛顿迭代：对当前解 F（满足 F² ≡ G mod x^k），下一步 F' = (F + G·F^{-1}) / 2 在 mod x^{2k} 下满足 F'² ≡ G（因为开方是方程 H(F) = F² - G = 0 的根，牛顿法对形式幂级数二次收敛）。每步需要一次多项式求逆（F^{-1}，本身牛顿迭代）与若干次乘法，长度 k 翻倍，复杂度满足 T(n) = T(n/2) + O(n log n)，解得 O(n log n)。常数项处理：F(0)² = G(0) 要求 G(0) 在模素数 p 下为二次剩余，F(0) 取 G(0) 的平方根（Tonelli-Shanks 等算法求二次剩余，一般约定取"较小"的根；若 G(0) = 0 则特殊处理：提取公因子 x^{2t} 后对剩余部分开方）。工程细节：所有运算在模 p 下进行，除以 2 用 2 的逆元；迭代从常数项出发逐层翻倍。

本题考察"牛顿迭代 + 常数项特判"的套路：多项式运算类问题（求逆、开方、exp/ln）都遵循"长度翻倍迭代"。回答时给出迭代式、收敛论证、常数项二次剩余约束与复杂度递推。

• 插值基函数 M(x) = Π(x - x_i) 及其导数 M'(x_i)
• 拉格朗日插值系数 = y_i / M'(x_i) 的分治求值
• 分治合并多项式（NTT 乘）的总复杂度

快速插值的标准路线基于拉格朗日插值：P(x) = Σ y_i · L_i(x)，其中 L_i(x) = M(x) / ((x - x_i)·M'(x_i))，M(x) = Π(x - x_i)。第一步：用分治乘积树求出 M(x)（O(n log² n)）；第二步：多点求值 M'(x) 在 x_i 处的值（求导后套用多点求值，O(n log² n)），得到权 w_i = y_i / M'(x_i)；第三步：计算 Σ w_i · M(x)/(x - x_i)。第三步分治实现：对区间构造多项式 A(L,R)(x) = Σ_{i∈[L,R]} w_i · Π_{j∈[L,R], j≠i}(x - x_j)，可由左右子区间合并：A = A_L·M_R + A_R·M_L（M_L、M_R 为左右乘积多项式），每层 NTT 乘 O(n log n)，共 O(log n) 层，总 O(n log² n)。总复杂度 O(n log² n)（题式中写作 O((n+m) log²(n+m))，m 为多项式次数上限）。牛顿插值（差商表）在浮点数值稳定，但符号/模域下分治拉格朗日更优。

本题考察插值的"求值-反演"结构：插值是求值的逆运算，因此两者共享乘积树与分治骨架。回答时按"M(x) 构建 → M' 多点求值定权 → 分治加权求和"三步展开，每步给出复杂度。

• 迭代式 G ← G·(2 - F·G) mod x^{2k}
• 常数项可逆（非零）是前提
• 复杂度递推 T(n) = T(n/2) + O(n log n)

求 G 使 F·G ≡ 1 (mod x^n)：常数项 F(0) ≠ 0 是必要条件，初值 G_0 = F(0)^{-1}（模 p 逆元）。牛顿迭代：若 G 满足 F·G ≡ 1 (mod x^k)，则 G' = G·(2 - F·G) 满足 F·G' ≡ 1 (mod x^{2k})——因为误差 E = 1 - F·G 满足 E ≡ 0 (mod x^k)，而 1 - F·G' = E²，阶数翻倍，故迭代二次收敛。每步用两次多项式乘法（F·G 与 G·(2-F·G)），长度翻倍，复杂度递推 T(n) = T(n/2) + O(n log n) = O(n log n)。工程实现：长度从 1 开始倍增到 n，中间结果截断到当前长度；模素数域下 2 与逆元用乘法表示；实现时可复用 NTT 乘法函数，注意数组长度取 2 的幂并对齐。该算法是所有"多项式除法、取模、exp/ln、开方、多点求值"的基础原语。

本题考察多项式运算的核心原语：牛顿迭代 + 截断长度翻倍。回答时给出迭代式与误差平方的收敛论证，写出复杂度递推，并强调常数项非零前提与工程截断细节。

• 拉格朗日反演公式：[x^n] f(x)^k = (k/n)[t^{n-k}] g(t)^n
• 复合逆 f(g(x)) = x 与树结构的"自递归"对应
• 与普通生成函数：EGF 处理标号树、OGF 处理无标号树

拉格朗日反演用于求解"自递归组合类"的系数：若树类 T 的生成函数满足 T = x·φ(T)（如平面二叉树 T = x·(1+T)²、有根有序树 T = x·exp(T) 等），且 f = x/φ... 具体地，若 f(x) 满足 f = x·φ(f)，即 x = f/φ(f) = f·ψ(f)，则 f 是 ψ 的复合逆（x = f·ψ(f) ⇔ f 与 x·ψ(x) 互为复合逆），拉格朗日反演给出 [x^n] f(x) = (1/n)[t^{n-1}] φ(t)^n，以及更一般的 [x^n] f(x)^k = (k/n)[t^{n-k}] φ(t)^n。由此可计数各种树：如"有根有标号树"由 Cayley 公式 T = n^{n-1}；"度为 i 的节点数期望"通过对 T(x)^i 的系数提取（k = i 版本）获得。与普通生成函数使用的区别：普通情形（EGF/OGF）用 exp/乘积处理"分量组合"，而拉格朗日反演专门处理"树的自指结构"（根 + 子树集合），其"复合逆"是"根节点换元"的代数表达；EGF 中还要考虑标号（除以 n! 的卷积），拉格朗日反演则直接给出系数闭式。

本题考察"生成函数处理组合结构的两大工具"：复合逆（拉格朗日反演）用于自递归树结构，exp/ln 用于分量分解。回答时先写反演公式与"T = x·φ(T)"的建模，再举度计数例子，最后对比 EGF/OGF 的常规用法。

• 长链（长儿子链）数组整体继承、短链暴力逐深度合并
• 每条链的数组只在链顶被合并进父链一次
• 合并代价 = 链长，Σ链长 = n ⇒ O(n)

设长链剖分后每条链的数组"生命周期"如下：链内所有节点的深度 DP 共用链顶分配的一段连续数组（指针复用），因此链内合并零拷贝；链外发生合并的唯一位置是"短链链顶 → 其父节点的长链数组"这一次。于是每条链恰好被合并一次（在其链顶处并入父链），且合并代价等于该链长度（逐深度累加，深度数 = 链长）。因为剖分把树边划分为"链内边"与"链间边"，每个节点恰属于一条链，所有链长之和 = n，所以总合并代价 = Σ链长 = O(n)。若某节点被合并多次（如朴素每次复制全数组），总代价会达 O(n²)；长链剖分通过"只合并一次 + 合并量=链长"两个事实把总代价压到线性。

本题考察摊还论证的"记账"视角：把总代价按链而不是按节点分摊。回答时先讲清长链继承与短链合并的机制，再用"每条链只合并一次、合并代价=链长、链长总和=n"三步给出 O(n) 证明，并与启发式合并（按 size，O(n log n)）对比说明深度剖分为何更强。

• 除法转乘法的代数变换：反转后低次项对应原高次项
• 商 = 反转被除数的前缀 × 除数反转的逆
• 余式 = 被除数 - 商 × 除数（截断）

多项式除法 A = B·Q + R（deg R < deg B）不能直接逐位相除（那要 O(n²)）。关键是"反转技巧"：定义反转算子 rev(A)(x) = x^{deg A}·A(1/x)，把"高次项除法"变成"低次项乘法"。由 A = B·Q + R 两边反转并舍弃 R（deg R < deg B，反转后落在低次端，截断掉）得 rev(A) ≡ rev(B)·rev(Q) (mod x^{n-m+1})，其中 n = deg A、m = deg B。于是 rev(Q) = rev(A) · rev(B)^{-1} (mod x^{n-m+1})，用多项式求逆（牛顿迭代 O(n log n)）求 rev(B) 的逆后一次乘法得 rev(Q)，再反转得 Q；最后 R = A - B·Q（截断到 deg < m）。步骤分解：1) 反转 A、B 各 O(n)；2) 求 rev(B)^{-1} 前缀 O(n log n)；3) 乘法得 rev(Q) O(n log n)；4) 反转 Q O(n)；5) 乘 B·Q 并相减得 R O(n log n)。总 O(n log n)。

本题考察"反转算子"的代数直觉：多项式除法在高次端是"因果系统"，反转后变成低次端求逆，可套用乘法与求逆。回答时先写反转恒等式，再按五步分解实现并给出每步复杂度。

• 划分 = 无序分量集合：方案数 = exp 在子集卷积意义下的应用
• 集合幂级数 exp 实现：k! 归一化 + 子集卷积幂
• 复杂度 O(n²·2^n) vs O(3^n) 枚举

将集合 S 划分成若干非空部分（每个部分内部"同质"，如连通块、团等）的方案数，在集合幂级数框架下是"SET 构造"：设 f(S) 为"单个部分"的计数（如 S 上的连通图数），则划分计数 F(S) = exp(f)(S) = Σ_{k≥0} (f^{⊗k})(S) / k!，其中 f^{⊗k} 是 k 次子集卷积幂（有序 k 元组计数），除以 k! 消除部分的顺序。用占位多项式实现子集卷积后，exp 可通过"按 popcount 的幂级数展开"或牛顿迭代计算，总复杂度 O(n²·2^n)。与枚举法对比：枚举法对每个 S 枚举其最小元素所在部分 T，递推 F(S) = Σ_{T⊆S, min∈T} f(T)·F(S\T)，总复杂度 Σ 2^{|S|-1} = O(3^n)；n ≤ 18 时 3^n 与 n²·2^n 常数差异不大，n = 20 时子集卷积（4e8 主项）更优，但实现复杂度高，工程上常选"枚举 + 剪枝"。

本题考察"划分 ↔ exp"的组合翻译与两种实现路线的取舍。回答时先建立 F = exp(f) 的语义（无序集合），再讲占位多项式实现与 /k! 归一化，最后给出 O(3^n) 枚举的对比与选型建议。

• 分治卷积：把 exp/ln 的卷积式按中点分裂递归求解
• 牛顿迭代：长度翻倍 + 求逆/乘法，每步 O(n log n)
• 常数与实现难度：分治 FFT 需 CDQ 式偏序卷积，代码量小但常数大

多项式 exp/ln 的标准实现是牛顿迭代：ln 用 ln(P) = ∫P'/P（一次求逆 + 一次乘法，长度翻倍迭代，T(n) = T(n/2) + O(n log n) = O(n log n)）；exp 用"解微分方程"型牛顿迭代（每步需要一次求逆与两次乘法），同样长度翻倍，总 O(n log n)。分治 FFT（CDQ 分治）的路线：把目标卷积 F = exp(G) 满足的方程 F' = F·G' 写成积分方程，用"对中点右侧贡献来自左侧已算部分"的偏序卷积，每层用 NTT 乘，总复杂度也是 O(n log² n)（每层 O(n log n) × log n 层）。取舍：牛顿迭代每步多项式长度翻倍，乘法次数少、收敛快，常数更小，是竞赛与库实现的主流；分治 FFT 实现思路简单（不用求逆），但每层都要做完整卷积，常数约为牛顿法的 2-3 倍，且代码易错。规模小（n ≤ 2^16）时二者差异不明显，规模大时选牛顿迭代。

本题考察两种"在线卷积"算法的工程取舍：牛顿是"倍增 + 逆运算"，CDQ 是"分治 + 偏序贡献"。回答时分别给出两者的迭代骨架与复杂度，再从乘法次数、常数、实现难度三维度对比，给出选型结论。

• 长链：按最大深度剖分，优化"深度相关 DP 合并"
• 重链：按子树大小剖分，dfn 连续支持路径/子树区间操作
• 判断标准：查询/合并依赖"深度"还是"路径区间"

两者剖分标准不同：重链剖分按子树大小选重儿子（大儿子），保证每条根到叶路径上轻边数 O(log n)，且重链 dfn 连续，适合把"路径操作"拆成 O(log n) 个线段树区间（路径加、路径求和、LCA 等）；长链剖分按"子树最大深度"选长儿子，链长总和 = n，适合"深度相关 DP 合并"（如统计子树内各深度信息、k 级祖先 O(1) 查询、深度众数），其核心收益是"长链数组整体继承 + 轻链只合并一次"的 O(n) 合并。判断标准：若问题的信息可以按"深度"聚合且合并时希望继承长数组（树上深度 DP、k 级祖先），用长链剖分；若问题要求"任意路径的区间操作"或依赖"子树大小均衡"（重链上轻边数少保证路径拆分段数少），用重链剖分。两者也可结合：重链剖分 + 长链剖分分别处理路径与深度两类需求。

本题考察剖分技术的"适用域"意识：剖分维度由目标操作决定。回答时对比两种剖分的定义、核心性质（轻边数 vs 链长总和）与典型应用，最后给出选型判断标准。

• 深度信息 DP：长链数组继承、短链链顶合并
• "每链合并一次"与"每节点 O(log n) 次"的差异
• 与 DSU on tree（按子树大小启发式）的复杂度与适用场景对比

长链剖分求各深度信息的 DP 中，节点 u 的深度数组 = 长儿子的深度数组（指针 +1 继承，零拷贝）+ 各轻儿子子树数组按深度累加。每个轻儿子的合并发生在"该轻链链顶"这一处，且合并后该链数组不再参与其他合并（已被吸收进长链数组），因此"每条链恰好被合并一次"，合并代价 = 链长，Σ链长 = n，总代价 O(n)。DSU on tree（树上启发式合并）按子树大小选重儿子，轻儿子子树统计后被清空或并入，每个节点作为轻子树成员可能被反复统计 O(log n) 次（因为轻边数 O(log n)），总复杂度 O(n log n)。区别：长链剖分利用"深度维度"使每个节点只被并入一次（链长求和 = n），DSU 利用"大小维度"保证每个节点至多被重统计 O(log n) 次；长链版常数更小但只能处理"与深度相关"的合并，DSU 可以处理更一般的子树统计（颜色、众数等与深度无关的信息）。

本题考察两种"树合并"技术的复杂度来源差异：链长求和 vs 轻边数界。回答时先论证长链版"每链合并一次"的 O(n)，再对比 DSU 的 O(n log n) 机制与适用范围，最后给出选型结论。