1. 问题引入从一道集训队作业题说起最近在翻看一些经典的组合数学与多项式题目时又遇到了LOJ3395这道题。题目名字叫“Yet Another Permutation Problem”直译过来是“又一个排列问题”。在算法竞赛的语境里但凡题目名字里带“Yet Another”的往往意味着它有一个经典的、广为人知的背景但在此基础上又增加了一层新的、需要深入思考的约束或视角。这道题也不例外它表面上是一个关于排列计数的问题但内核却紧密联系着容斥原理、生成函数和多项式技术。很多选手初次接触时可能会被其简洁的题面所迷惑感觉无从下手而一旦理清其背后的组合结构又会惊叹于这些工具的优雅与强大。今天我们就来彻底拆解这道题不仅搞懂怎么做更要弄明白为什么这么做以及这些方法背后的通用思想。这道题的核心可以概括为对于一个长度为 n 的排列我们需要计算满足某种特定条件的排列个数。通常这类条件会描述为排列中某些位置或某些元素之间的相对关系比如不允许某个数出现在某个位置或者要求某些数构成一个递增子序列等。而解决这类问题的利器往往就是标题中提到的三驾马车容斥原理、生成函数和多项式运算。容斥原理帮助我们将复杂的“恰好满足”条件转化为一系列简单的“至少违反”某些条件的计数生成函数特别是指数型生成函数为我们提供了系统化处理排列计数问题的代数框架而多项式技术如卷积、求逆、exp/ln则让我们能高效地在这个框架内进行计算。接下来我们就沿着这条主线一步步深入。2. 问题重述与组合模型建立首先我们需要将模糊的“Yet Another Permutation Problem”具体化。虽然原题面可能有其具体的约束条件例如限制某些位置不能放某些元素或者限制排列中不含长度超过k的递增子序列等但这类问题的通用建模思路是相通的。为了讨论的普适性我们假设一个经典模型计算有多少个n的排列使得排列中不存在任何一个“坏位置”。什么是“坏位置”呢这需要根据具体题目定义。一个常见的设定是预先给定一个“禁止模式”集合。例如禁止模式可能是“数字i出现在位置i”即无不动点这是错排问题也可能是更复杂的结构如“数字i出现在位置i或i1”。我们设所有“坏事件”的集合为 A1, A2, ..., Am其中每个事件Ai表示排列违反了第i条禁止规则。那么我们要求的就是不满足任何坏事件的排列数量即 |⋂(i1 to m) Ai^c|其中 Ai^c 表示Ai的补集即不违反第i条规则。直接计算“都不违反”的数量是困难的因为规则之间可能相互影响。这时容斥原理就登场了。容斥原理告诉我们 |⋂ Ai^c| Σ_{S ⊆ [m]} (-1)^{|S|} |⋂_{i∈S} Ai| 也就是说我们转而计算所有“至少违反了S集合中所有规则”的排列数 |⋂_{i∈S} Ai|。对于许多设计良好的“坏事件”计算|⋂_{i∈S} Ai| 往往比直接计算原问题要简单得多因为它只关心是否违反S中的规则而忽略其他规则。这就完成了第一步转化将一个复杂的全局约束计数转化为对一系列指数个较简单子问题的计数和求和。3. 容斥原理的代数化从集合到生成函数如果我们对每一个子集S都暴力计算 |⋂_{i∈S} Ai|再代入容斥公式求和复杂度是指数级的2^m在m很大时比如m与n相关时不可行。我们需要一种更高效的方式来组织这个求和过程。这就引入了生成函数特别是指数型生成函数EGF。为什么是指数型生成函数因为我们的对象是排列。对于一个组合类A其指数型生成函数 A(x) Σ_{n≥0} a_n * (x^n / n!)其中a_n是大小为n的对象个数。对于排列所有n!个排列的EGF就是 Σ_{n≥0} n! * (x^n / n!) Σ_{n≥0} x^n 1/(1-x)。但更重要的是EGF对于“带标签对象的组合操作”有非常好的性质比如笛卡尔积如果组合对象C是由A和B独立拼接而成那么C的EGF等于A(x) * B(x)。集合构造SET如果组合对象C是由A中的元素组成的一个无序集合那么C的EGF等于 exp(A(x))。这对于描述“若干互不影响的约束部分”非常有用。现在我们如何用EGF表达容斥过程考虑一个更结构化的视角我们想要计数的是“好”的排列。我们可以尝试直接构造“好”排列的EGF。一个常用的技巧是引入一个辅助变量y或者更一般地对每个“坏事件”类型进行标记。假设我们的“坏事件”可以归类为有限的几种“类型”。例如在错排问题中只有一种类型“数字i在位置i”。在更复杂的问题中可能有多种禁止模式。设共有t种不同类型的坏事件。对于排列中的每一个“位置-元素”对我们检查它是否构成了一个某种类型的坏事件。我们可以为排列定义一个权重如果排列中包含了k个类型1的坏事件k2个类型2的坏事件...那么它的权重就是 ( (-1)^{k1} ) * ( (-1)^{k2} ) * ... 这听起来很像容斥原理中符号的来源。更精确的代数化方法是使用包含-排除原理的生成函数形式。考虑一个排列π对于每个坏事件i定义一个指示变量 u_i当事件i发生时u_i1否则为0。那么我们想要求和的量是 Π_{i1}^m (1 - u_i) 在所有排列上的总和。因为 (1 - u_i) 在事件i发生时为0不发生时为1所以这个乘积在“好排列”上为1在至少违反一个规则的排列上为0。这正是我们想要的计数函数。现在将这个乘积展开Π (1 - u_i) Σ_{S ⊆ [m]} (-1)^{|S|} Π_{i∈S} u_i。因此对所有排列求和就得到了容斥公式Σ_{π} Π (1 - u_i) Σ_{S ⊆ [m]} (-1)^{|S|} (Σ_{π} Π_{i∈S} u_i)。而 Σ_{π} Π_{i∈S} u_i 正是“至少违反S中所有事件”的排列数 |⋂_{i∈S} Ai|。生成函数的作用在于它能将 Σ_{S ⊆ [m]} (-1)^{|S|} |⋂_{i∈S} Ai| 这个和式表示成某个更容易计算的生成函数的系数。通常我们会构造一个双变量生成函数 F(x, z)其中x标记排列长度nz标记“坏事件”的某种特征比如坏事件的个数。然后我们要求的答案就是 [x^n] F(x, -1)。这里z-1就实现了容斥中(-1)^{|S|}的效果。4. 实战核心指数型生成函数与集合构造让我们通过一个具体的例子来巩固这个思想。考虑一个比错排更一般化的问题假设我们有n个位置和n个数字1到n。我们禁止某些“数字-位置”对 (i, j)。也就是说我们不能把数字i放在位置j上。设这样的禁止对有m个。我们想计算有多少个排列不违反任何禁止对。这是一个经典的二部图完美匹配计数问题或者说是带禁止位置的排列计数。我们可以用容斥原理枚举违反了哪些禁止对一个集合S然后计算有多少排列满足“至少违反了S中的所有禁止对”。违反一个禁止对(i, j)意味着数字i必须放在位置j上。如果我们要求违反S中的所有禁止对那么S中的这些“数字-位置”对就被固定了。注意如果S中包含的两个禁止对涉及同一个数字或同一个位置比如(i, j)和(i, k)要求数字i同时放在位置j和k这是不可能的那么 |⋂_{i∈S} Ai| 0。否则这相当于固定了|S|个数字的位置剩下的n-|S|个数字和位置可以任意排列但不能再违反其他禁止对不在容斥项里我们只关心S中的规则必须被违反其他规则不管。因此如果S中的禁止对互不冲突即没有重复的数字或位置那么 |⋂_{i∈S} Ai| (n - |S|)!。因此根据容斥原理答案 Σ_{S: S是互不冲突的禁止对子集} (-1)^{|S|} (n - |S|)!。这等价于 Σ_{k0}^{n} (-1)^k * (n-k)! * (互不冲突的k个禁止对的子集个数)。而“互不冲突的k个禁止对的子集个数”正好是我们在一个二部图左边是数字右边是位置边是允许的配对不这里应该是“坏边”构成的图中选取k条互不相邻的边的方案数。这是一个图匹配计数问题对于一般图是#P-hard的。但是如果禁止对的结构有特殊性比如每行每列只有一个禁止位置像棋盘禁位那么这个问题可以用更简单的生成函数解决。这就是生成函数展现威力的地方。我们考虑排列的另一种构造方式一个排列可以看作是对数字集合的一个置换。而“禁止对”可以看作是在这个置换上施加的局部约束。我们可以尝试用EGF来编码“一个数字及其位置”的信息。一个更强大的观点是使用有标号集合的指数型生成函数。将每个数字i看成一个“点”它本可以去到n个位置但有一个或多个位置是禁止的。然而这种“每个点有不同禁止集”的情况很难统一处理。通常题目会设计成“禁止模式”是均匀的或者可以按照某种性质分类。例如考虑一个经典变种禁止排列中存在长度为2的上升子序列不那太强了。考虑一个更贴近多项式方法的例子计算不含长度为k1的递增子序列的排列个数。这就是著名的“Erdős–Szekeres”定理相关的计数问题其答案的生成函数与多项式运算密切相关。假设我们想计算长度为n且最长递增子序列(LIS)长度不超过k的排列个数。记这个数为 a_n^{(k)}。那么著名的Robinson–Schensted–K correspondence将排列与一对标准杨表联系起来且排列的LIS长度等于杨表的第一行长度。因此a_n^{(k)} 等于第一行长度≤k的标准杨表的个数。而根据钩子公式形状为λ的杨表个数是 n! / Π hook(λ)。对所有行数≤k的λ求和就得到 a_n^{(k)}。这个和式可以用Schur函数或Toeplitz行列式来表示最终可以联系到多项式的系数。具体地有结论Σ_{n≥0} a_n^{(k)} x^n / n! 这个指数生成函数等于某个Fredholm行列式或者等于exp( Σ_{m1}^{k} x^m / m )的某种形式对于避免特定模式的情况。计算这个生成函数的第n项系数就需要用到多项式exp和对数ln的技术。5. 多项式技术登场expln与卷积现在我们进入多项式环节。生成函数无论是普通型(OGF)还是指数型(EGF)在算法竞赛中通常以形式幂级数的形式处理。我们关心的是如何高效地计算这些级数的前n项系数。这就涉及多项式形式幂级数的基本操作加法、乘法卷积、求逆、exp指数、ln对数、幂等。为什么这些操作有用让我们回到“不含长度为k1递增子序列”的例子。前面提到其EGF可能具有 exp( Σ_{m1}^{k} x^m / m ) 的形式。我们来验证一个简单情况k1即严格递减排列。显然只有一个排列是严格递减的对于给定的n个元素。所以 a_n^{(1)} 1 for all n≥0。其EGF就是 Σ_{n≥0} 1 * x^n / n! exp(x)。而 exp( Σ_{m1}^{1} x^m / m ) exp(x)。吻合。对于k2即排列的LIS长度≤2这样的排列称为“2-avoiding permutations”或“可分割排列”实际上LIS≤2的排列等价于排列可以分解为两个递减子序列其个数是第n个Catalan数让我们计算一下n1:1, n2:2, n3:5 (123不行LIS3)枚举一下(132, 213, 231, 312, 321)共5个确实是Catalan数。Catalan数的EGF不是简单的初等函数但已知其OGF是 (1 - sqrt(1-4x))/(2x)。那么其EGF可以通过OGF变换得到或者已知 Σ C_n * x^n / n! 满足某个微分方程。而 exp( Σ_{m1}^{2} x^m / m ) exp(x x^2/2)。这个函数的级数展开前几项是1 x (11/2)*x^2/2! ... 1 x (3/2)x^2/2 ... 1 x (3/4)x^2 ...。当n2时系数是3/4 * 2! 1.5不是整数显然不对。所以我的猜测 exp(Σ x^m/m) 可能不对。更准确的公式来自Gessels theorem记长度为n且LIS长度k的排列个数为 a_n^{(k)}则其指数生成函数满足 Σ_{n≥0} a_n^{(k)} x^n / n! Det( I_{k×k} Q_{k×k} )其中Q是一个Toeplitz矩阵其(i,j)元为 x^{|i-j|} / (|i-j|)!这比较复杂。但核心思想是许多排列计数问题的生成函数可以写成矩阵行列式或某个简单函数的exp。而计算矩阵行列式或exp都需要多项式操作。多项式exp的组合意义非常深刻exp(F(x)) 的EGF对应于由“原子”F(x)所描述的对象构成的所有无序集合。例如如果F(x)是连通图的EGF那么exp(F(x))就是所有图的EGF。在我们的排列问题中我们经常需要将排列分解为若干个互不干扰的“组件”每个组件的生成函数是F(x)那么所有排列的生成函数就是 exp(F(x))。容斥原理中我们有时会先计算“包含某种结构”的排列其生成函数可能是G(x)那么“不包含该结构”的生成函数可能就是 exp(某种形式) 或 G(x)的逆。多项式ln是exp的逆运算它从一个组合类的生成函数中提取其连通分量的生成函数。在实际计算中给定一个形式幂级数 F(x) Σ_{i≥0} f_i x^i我们想计算 G(x) exp(F(x)) 的前n项系数。这可以通过牛顿迭代法等算法在 O(n log n) 时间内完成。同样求逆、ln、幂等操作也有O(n log n)的算法。这些构成了现代多项式技术解决组合计数问题的基石。对于LOJ3395这道具体的题目虽然原题面没有给出但结合“容斥生成函数多项式”这个标签以及“Yet Another Permutation Problem”这个名称我推测它很可能涉及以下模式定义了一个在排列上容易描述的“坏性质”。通过容斥原理将计数转化为计算包含特定“坏结构”的排列数。发现这些“坏结构”在排列中是相互独立的或者可以被分解成若干独立的部分。因此包含特定大小k的坏结构的排列数其EGF可以写成一个基础结构的EGF的k次方再除以k!因为结构是无序的即类似于 (F(x))^k / k! 的形式。对所有k从容斥求和得到总生成函数Σ_{k≥0} (-1)^k * (F(x))^k / k! exp(-F(x))。最终答案就是 n! * [x^n] exp(-F(x))。问题归结为计算 F(x)通常是一个简单的级数然后计算 exp(-F(x)) 的前n项系数这需要多项式exp。或者步骤4和5可能略有变化但核心一定是容斥原理引导出了一个生成函数的表达式而这个表达式需要用到多项式exp/ln来最终计算系数。6. 从理论到实现算法步骤与细节假设我们已经通过组合分析得到了最终生成函数的表达式例如 A(x) exp(-B(x))其中 B(x) Σ_{i≥1} b_i x^i 是一个已知的多项式或形式幂级数。我们需要计算的是 a_n n! * [x^n] A(x)。具体的算法步骤如下6.1 步骤一确定B(x)首先我们需要根据题目的具体约束推导出B(x)的表达式。这通常是整个问题中最具组合洞察力的一步。例如在某个问题中如果“坏结构”是“一个长度为2的特定模式”并且该模式在排列中互不相交即不共享元素那么包含k个这样的坏结构的排列其EGF可能就是 (x^2/2)^k / k!这里x^2/2可能是描述一个坏结构对大小的贡献。那么对所有k求和得到 A(x) Σ_{k≥0} (-1)^k (x^2/2)^k / k! exp(-x^2/2)。此时 B(x)x^2/2。在更复杂的问题中B(x)可能是一个更复杂的级数比如 Σ_{i in S} c_i x^i / i!其中S是某个集合c_i是系数。我们需要精确地计算出B(x)的前n项系数因为最终只需要A(x)的前n项。6.2 步骤二多项式表示与卷积在计算机中我们使用长度为N通常为大于n的2的幂的数组来表示多项式数组下标i存储x^i项的系数。我们需要计算 A(x) exp(-B(x)) mod x^{n1}即忽略x^{n1}及更高次项。多项式exp的计算依赖于牛顿迭代。已知要求 G(x) exp(F(x))即满足 ln G(x) - F(x) 0。牛顿迭代公式为 G_{next}(x) G(x) * (1 - ln G(x) F(x)) mod x^{2m} 其中m是当前已知项数的两倍。我们需要实现多项式的基本操作乘法使用FFT快速傅里叶变换或NTT数论变换复杂度O(N log N)。在模意义下计数通常使用NTT。求逆假设已知 H(x) * H_inv(x) 1 mod x^m求 H_inv(x) mod x^{2m}。也可以用牛顿迭代H_inv_next H_inv * (2 - H * H_inv) mod x^{2m}。对数ln计算 ln P(x) 需要先求导再乘逆元再积分。即 ln P(x) ∫ (P(x) / P(x)) dx。这需要多项式求导、求逆、乘法和积分。指数exp如上所述使用牛顿迭代内部会调用ln和乘法。因此要实现多项式exp我们需要先实现多项式乘法、求逆、对数ln。这些是标准模板。6.3 步骤三边界处理与常数优化在实际编码中需要注意模数通常使用998244353或1004535809等原根为3的NTT友好质数。长度每次进行多项式操作前要确保数组长度是2的幂并且足够容纳所需项数通常是扩展到大于等于n1的最小2的幂。在牛顿迭代中长度会逐次翻倍。清零多项式操作后高阶项超过当前模数x^m的部分要及时清零避免污染后续计算。常数因子在计算EGF时系数包含阶乘和阶乘逆元。通常我们会预处理出[0, n]范围内的阶乘fac[i]和阶乘逆元invfac[i]。这样如果B(x)的系数b_i是“某种结构的个数”我们存储到数组里的可能是 b_i / i!即EGF的系数也可能是普通OGF系数需要仔细区分。在计算A(x)exp(-B(x))后得到的a_i是EGF的系数最终答案 a_n * n! 才是排列数。所以通常我们让B(x)和A(x)都代表EGF这样最后直接取a_n * n!即可。在实现时传入的B多项式数组其第i项存储的是 b_i / i!如果b_i是OGF系数。这需要根据题目推导的公式来调整。6.4 步骤四最终答案计算计算出A(x)的前n1项系数EGF系数后我们需要的答案就是 a_n * n! mod MOD。注意这里的n是排列长度即题目输入的参数。7. 例题延伸与变式思考为了加深理解我们看一个简化版的问题它完整走通了容斥-生成函数-多项式的流程。问题计算长度为n的排列中不包含任何连续两个元素递增即不存在i使得 p_i p_{i1}的排列个数。换句话说排列是“交替”的但这里要求严格递减的相邻关系不是禁止上升相邻对。这样的排列被称为“无上升相邻对的排列”。解法容斥设坏事件A_i为位置i和i1上的元素构成一个上升对即p_i p_{i1}。共有n-1个这样的事件。我们要求不满足任何A_i的排列数。计算交集对于一个大小为k的坏事件集合S要求这些事件同时发生。这意味着在排列中有k个指定的相邻位置对是上升的。注意这些指定的相邻对可能相邻比如A_i和A_{i1}这意味着位置i, i1, i2满足 p_i p_{i1} 且 p_{i1} p_{i2}这并不矛盾它只是强制了一个更长的递增段长度为3。但是如果S中包含两个事件A_i和A_j且它们对应的区间有重叠但不连续这是不可能的因为每个事件只涉及两个连续位置实际上S定义了一组上升的边这些边将位置序列分割成一些连续的“上升段”和孤立的点。更准确地说如果我们把必须上升的相邻对看作在位置1..n之间画上了一些“上升箭头”那么这些箭头会将整个排列分成若干个连续的“块”在每个块内部相邻元素必须严格递增因为所有块内的相邻对都被要求上升。不同的块之间则没有约束。生成函数考虑一个长度为L的块内部必须严格递增。对于一个固定的元素集合严格递增的顺序只有一种。所以如果我们知道一个块包含了哪些数字那么这个块内部的排列方式就唯一确定了。因此一个长度为L的块其本质就是从n个数字中选出L个数字然后它们必须按升序排列。但是在容斥的框架下我们是在计数“至少违反S中规则”的排列此时我们只关心那些被“上升箭头”强制约束的块其他位置可以任意排列吗不其他位置之间没有强制要求上升或下降。然而这里有一个关键点当我们将一些相邻位置强制为上升后剩下的“自由”位置它们之间的相对顺序以及它们与“上升块”之间的相对顺序仍然是任意的排列。这变得复杂了。一个更简洁的方法是使用指数型生成函数和集合构造。我们换个角度考虑排列的“下降沿”。一个排列可以看作是由一些“递增段”和“下降沿”连接而成。但禁止上升相邻对意味着递增段的长度只能是1因为长度≥2的递增段内部必然包含上升相邻对。所以排列被“下降沿”分割成一系列长度为1的“段”这似乎不对因为下降沿可以连续。实际上无上升相邻对的排列等价于排列中每个“上升”只能出现在长度为1的递增段中但这不可能因为长度为1的段没有相邻对。所以这个条件等价于排列中没有上升相邻对即每个相邻对都是下降或相等的但排列是双射所以不可能相等。因此这等价于排列是严格递减的显然不是因为排列3,1,2有上升相邻对(1,2)而排列2,1,3没有上升相邻对但它不是严格递减的。所以“无上升相邻对”并不意味着整个排列递减。让我们枚举n3所有排列共6个。无上升相邻对的意味着对于所有i1,2不能有p_i p_{i1}。123: (1,2)和(2,3)都上升不符合。132: (1,3)上升(3,2)下降。不符合因为(1,3)不是相邻对我们检查的是相邻对(1,2)和(2,3)。(1,2):13上升不符合。所以132不符合。213: (2,1)下降(1,3)上升。不符合(1,3)是上升相邻对(1,3)不是相邻对相邻对是(2,1)和(1,3)。(1,3)中13上升所以不符合。231: (2,3)上升(3,1)下降。不符合。312: (3,1)下降(1,2)上升。不符合。321: (3,2)下降(2,1)下降。符合。 所以n3时只有1个321。这看起来像是所有排列都是严格递减的但n2时排列有2个12不符合21符合也是1个。n4时可以枚举一下似乎也只有严格递减排列1个实际上无上升相邻对意味着排列中每个位置i除了最后一个都有p_i p_{i1}这正是一个严格递减序列。而严格递减序列对于一个给定的集合只有一种。所以答案确实是1。这个问题太简单了没有达到练习的目的。我们换一个更有代表性的例子计算无不动点的排列错排个数。这虽然经典但通常用递推或简单容斥不需要多项式exp。但我们可以强行用生成函数多项式方法做一遍以展示流程。错排问题排列π满足 π(i) ≠ i 对所有i成立。容斥坏事件A_i: π(i)i。共有n个事件。计算交集对于大小为k的集合S|⋂_{i∈S} A_i| (n-k)!。因为指定了k个位置上的数字固定剩下n-k个位置任意排列。直接容斥公式D_n Σ_{k0}^{n} (-1)^k * C(n, k) * (n-k)! n! * Σ_{k0}^{n} (-1)^k / k!。这是经典公式。生成函数视角考虑指数生成函数 D(x) Σ_{n≥0} D_n x^n / n!。代入公式 D_n / n! Σ_{k0}^{n} (-1)^k / k!。 注意到右边是 Σ_{k≥0} (-1)^k / k! 截断到n项但因为kn时1/k!项在x^n系数中贡献为0实际上Σ_{k≥0} (-1)^k / k! 就是 e^{-1}。而 D_n / n! 正是 e^{-1} 的泰勒展开的前n项部分和。但作为形式幂级数我们有 D(x) Σ_{n≥0} ( Σ_{k0}^{n} (-1)^k / k! ) x^n。 交换求和顺序 Σ_{k≥0} (-1)^k / k! Σ_{n≥k} x^n Σ_{k≥0} (-1)^k / k! * x^k / (1-x) (1/(1-x)) * Σ_{k≥0} (-x)^k / k! (1/(1-x)) * e^{-x}。 所以错排数的EGF是 D(x) e^{-x} / (1-x)。多项式方法如果我们想用多项式技术计算前n个错排数我们可以计算形式幂级数 F(x) e^{-x} 和 G(x) 1/(1-x) 的卷积。e^{-x} 可以通过多项式exp计算exp(-x)而 1/(1-x) 就是 Σ x^i。卷积即可得到D(x)的系数。这虽然有点杀鸡用牛刀但展示了流程。对于更复杂的LOJ3395其B(x)很可能不是一个简单的-x而是一个更复杂的形式例如 B(x) Σ_{i2}^{k} x^i / i 或其他形式最终A(x)exp(-B(x))然后需要计算这个exp。8. 总结与经验分享回顾整个解题过程我们可以提炼出解决这类“排列计数容斥生成函数多项式”问题的通用思维框架定义与转化清晰定义问题中的“好排列”和“坏事件”。尝试将“好排列”计数转化为“坏事件”的容斥。容斥代数化写出容斥公式并观察交集项 |⋂_{i∈S} Ai| 的计算是否只依赖于S的大小或某种简单特征如S中元素构成的连通块数。如果只依赖于大小那么容斥和式可以转化为卷积形式。生成函数选择根据计数对象是排列带标签选择指数型生成函数EGF。将容斥和式表示为某个生成函数的系数。关键一步是识别出所有包含特定大小k的“坏结构”的排列其EGF是否可以写成某个基础结构EGF的k次方除以k!即集合构造。如果能那么对k求和就会自然引出exp。得到闭式通过组合解释求出基础结构的EGF记为F(x)。那么包含任意个坏结构的排列EGF可能是 exp(F(x))如果坏结构之间无影响。而好排列的EGF通过容斥往往就是 exp(±F(x)) 或与之相关的形式。多项式计算将问题归结为计算某个形式幂级数如exp(F(x))的前n项系数。使用多项式模板NTT、求逆、ln、exp进行高效计算。提取答案从EGF的系数还原回排列数乘以n!即可。在实际操作中最困难也最关键的是第3、4步如何将组合结构翻译成生成函数的语言。这需要大量的练习和洞察力。一个实用的建议是从简单情况小n枚举观察数列猜测生成函数或者尝试用动态规划推导生成函数的方程。另外在实现多项式运算时要特别注意模数、长度、清零等细节并做好常数优化因为NTT的常数较大。对于n在10^5级别的题目O(n log n)的算法是可行的。最后这类问题之美在于它连接了组合直观、代数工具和算法实现。理解其本质后你会发现很多看似不同的题目都共享同一套内核。希望这篇长文能帮你打通任督二脉下次遇到“Yet Another”问题时能自信地拿起容斥、生成函数和多项式这三把利器。
组合计数三驾马车：容斥原理、生成函数与多项式技术详解
1. 问题引入从一道集训队作业题说起最近在翻看一些经典的组合数学与多项式题目时又遇到了LOJ3395这道题。题目名字叫“Yet Another Permutation Problem”直译过来是“又一个排列问题”。在算法竞赛的语境里但凡题目名字里带“Yet Another”的往往意味着它有一个经典的、广为人知的背景但在此基础上又增加了一层新的、需要深入思考的约束或视角。这道题也不例外它表面上是一个关于排列计数的问题但内核却紧密联系着容斥原理、生成函数和多项式技术。很多选手初次接触时可能会被其简洁的题面所迷惑感觉无从下手而一旦理清其背后的组合结构又会惊叹于这些工具的优雅与强大。今天我们就来彻底拆解这道题不仅搞懂怎么做更要弄明白为什么这么做以及这些方法背后的通用思想。这道题的核心可以概括为对于一个长度为 n 的排列我们需要计算满足某种特定条件的排列个数。通常这类条件会描述为排列中某些位置或某些元素之间的相对关系比如不允许某个数出现在某个位置或者要求某些数构成一个递增子序列等。而解决这类问题的利器往往就是标题中提到的三驾马车容斥原理、生成函数和多项式运算。容斥原理帮助我们将复杂的“恰好满足”条件转化为一系列简单的“至少违反”某些条件的计数生成函数特别是指数型生成函数为我们提供了系统化处理排列计数问题的代数框架而多项式技术如卷积、求逆、exp/ln则让我们能高效地在这个框架内进行计算。接下来我们就沿着这条主线一步步深入。2. 问题重述与组合模型建立首先我们需要将模糊的“Yet Another Permutation Problem”具体化。虽然原题面可能有其具体的约束条件例如限制某些位置不能放某些元素或者限制排列中不含长度超过k的递增子序列等但这类问题的通用建模思路是相通的。为了讨论的普适性我们假设一个经典模型计算有多少个n的排列使得排列中不存在任何一个“坏位置”。什么是“坏位置”呢这需要根据具体题目定义。一个常见的设定是预先给定一个“禁止模式”集合。例如禁止模式可能是“数字i出现在位置i”即无不动点这是错排问题也可能是更复杂的结构如“数字i出现在位置i或i1”。我们设所有“坏事件”的集合为 A1, A2, ..., Am其中每个事件Ai表示排列违反了第i条禁止规则。那么我们要求的就是不满足任何坏事件的排列数量即 |⋂(i1 to m) Ai^c|其中 Ai^c 表示Ai的补集即不违反第i条规则。直接计算“都不违反”的数量是困难的因为规则之间可能相互影响。这时容斥原理就登场了。容斥原理告诉我们 |⋂ Ai^c| Σ_{S ⊆ [m]} (-1)^{|S|} |⋂_{i∈S} Ai| 也就是说我们转而计算所有“至少违反了S集合中所有规则”的排列数 |⋂_{i∈S} Ai|。对于许多设计良好的“坏事件”计算|⋂_{i∈S} Ai| 往往比直接计算原问题要简单得多因为它只关心是否违反S中的规则而忽略其他规则。这就完成了第一步转化将一个复杂的全局约束计数转化为对一系列指数个较简单子问题的计数和求和。3. 容斥原理的代数化从集合到生成函数如果我们对每一个子集S都暴力计算 |⋂_{i∈S} Ai|再代入容斥公式求和复杂度是指数级的2^m在m很大时比如m与n相关时不可行。我们需要一种更高效的方式来组织这个求和过程。这就引入了生成函数特别是指数型生成函数EGF。为什么是指数型生成函数因为我们的对象是排列。对于一个组合类A其指数型生成函数 A(x) Σ_{n≥0} a_n * (x^n / n!)其中a_n是大小为n的对象个数。对于排列所有n!个排列的EGF就是 Σ_{n≥0} n! * (x^n / n!) Σ_{n≥0} x^n 1/(1-x)。但更重要的是EGF对于“带标签对象的组合操作”有非常好的性质比如笛卡尔积如果组合对象C是由A和B独立拼接而成那么C的EGF等于A(x) * B(x)。集合构造SET如果组合对象C是由A中的元素组成的一个无序集合那么C的EGF等于 exp(A(x))。这对于描述“若干互不影响的约束部分”非常有用。现在我们如何用EGF表达容斥过程考虑一个更结构化的视角我们想要计数的是“好”的排列。我们可以尝试直接构造“好”排列的EGF。一个常用的技巧是引入一个辅助变量y或者更一般地对每个“坏事件”类型进行标记。假设我们的“坏事件”可以归类为有限的几种“类型”。例如在错排问题中只有一种类型“数字i在位置i”。在更复杂的问题中可能有多种禁止模式。设共有t种不同类型的坏事件。对于排列中的每一个“位置-元素”对我们检查它是否构成了一个某种类型的坏事件。我们可以为排列定义一个权重如果排列中包含了k个类型1的坏事件k2个类型2的坏事件...那么它的权重就是 ( (-1)^{k1} ) * ( (-1)^{k2} ) * ... 这听起来很像容斥原理中符号的来源。更精确的代数化方法是使用包含-排除原理的生成函数形式。考虑一个排列π对于每个坏事件i定义一个指示变量 u_i当事件i发生时u_i1否则为0。那么我们想要求和的量是 Π_{i1}^m (1 - u_i) 在所有排列上的总和。因为 (1 - u_i) 在事件i发生时为0不发生时为1所以这个乘积在“好排列”上为1在至少违反一个规则的排列上为0。这正是我们想要的计数函数。现在将这个乘积展开Π (1 - u_i) Σ_{S ⊆ [m]} (-1)^{|S|} Π_{i∈S} u_i。因此对所有排列求和就得到了容斥公式Σ_{π} Π (1 - u_i) Σ_{S ⊆ [m]} (-1)^{|S|} (Σ_{π} Π_{i∈S} u_i)。而 Σ_{π} Π_{i∈S} u_i 正是“至少违反S中所有事件”的排列数 |⋂_{i∈S} Ai|。生成函数的作用在于它能将 Σ_{S ⊆ [m]} (-1)^{|S|} |⋂_{i∈S} Ai| 这个和式表示成某个更容易计算的生成函数的系数。通常我们会构造一个双变量生成函数 F(x, z)其中x标记排列长度nz标记“坏事件”的某种特征比如坏事件的个数。然后我们要求的答案就是 [x^n] F(x, -1)。这里z-1就实现了容斥中(-1)^{|S|}的效果。4. 实战核心指数型生成函数与集合构造让我们通过一个具体的例子来巩固这个思想。考虑一个比错排更一般化的问题假设我们有n个位置和n个数字1到n。我们禁止某些“数字-位置”对 (i, j)。也就是说我们不能把数字i放在位置j上。设这样的禁止对有m个。我们想计算有多少个排列不违反任何禁止对。这是一个经典的二部图完美匹配计数问题或者说是带禁止位置的排列计数。我们可以用容斥原理枚举违反了哪些禁止对一个集合S然后计算有多少排列满足“至少违反了S中的所有禁止对”。违反一个禁止对(i, j)意味着数字i必须放在位置j上。如果我们要求违反S中的所有禁止对那么S中的这些“数字-位置”对就被固定了。注意如果S中包含的两个禁止对涉及同一个数字或同一个位置比如(i, j)和(i, k)要求数字i同时放在位置j和k这是不可能的那么 |⋂_{i∈S} Ai| 0。否则这相当于固定了|S|个数字的位置剩下的n-|S|个数字和位置可以任意排列但不能再违反其他禁止对不在容斥项里我们只关心S中的规则必须被违反其他规则不管。因此如果S中的禁止对互不冲突即没有重复的数字或位置那么 |⋂_{i∈S} Ai| (n - |S|)!。因此根据容斥原理答案 Σ_{S: S是互不冲突的禁止对子集} (-1)^{|S|} (n - |S|)!。这等价于 Σ_{k0}^{n} (-1)^k * (n-k)! * (互不冲突的k个禁止对的子集个数)。而“互不冲突的k个禁止对的子集个数”正好是我们在一个二部图左边是数字右边是位置边是允许的配对不这里应该是“坏边”构成的图中选取k条互不相邻的边的方案数。这是一个图匹配计数问题对于一般图是#P-hard的。但是如果禁止对的结构有特殊性比如每行每列只有一个禁止位置像棋盘禁位那么这个问题可以用更简单的生成函数解决。这就是生成函数展现威力的地方。我们考虑排列的另一种构造方式一个排列可以看作是对数字集合的一个置换。而“禁止对”可以看作是在这个置换上施加的局部约束。我们可以尝试用EGF来编码“一个数字及其位置”的信息。一个更强大的观点是使用有标号集合的指数型生成函数。将每个数字i看成一个“点”它本可以去到n个位置但有一个或多个位置是禁止的。然而这种“每个点有不同禁止集”的情况很难统一处理。通常题目会设计成“禁止模式”是均匀的或者可以按照某种性质分类。例如考虑一个经典变种禁止排列中存在长度为2的上升子序列不那太强了。考虑一个更贴近多项式方法的例子计算不含长度为k1的递增子序列的排列个数。这就是著名的“Erdős–Szekeres”定理相关的计数问题其答案的生成函数与多项式运算密切相关。假设我们想计算长度为n且最长递增子序列(LIS)长度不超过k的排列个数。记这个数为 a_n^{(k)}。那么著名的Robinson–Schensted–K correspondence将排列与一对标准杨表联系起来且排列的LIS长度等于杨表的第一行长度。因此a_n^{(k)} 等于第一行长度≤k的标准杨表的个数。而根据钩子公式形状为λ的杨表个数是 n! / Π hook(λ)。对所有行数≤k的λ求和就得到 a_n^{(k)}。这个和式可以用Schur函数或Toeplitz行列式来表示最终可以联系到多项式的系数。具体地有结论Σ_{n≥0} a_n^{(k)} x^n / n! 这个指数生成函数等于某个Fredholm行列式或者等于exp( Σ_{m1}^{k} x^m / m )的某种形式对于避免特定模式的情况。计算这个生成函数的第n项系数就需要用到多项式exp和对数ln的技术。5. 多项式技术登场expln与卷积现在我们进入多项式环节。生成函数无论是普通型(OGF)还是指数型(EGF)在算法竞赛中通常以形式幂级数的形式处理。我们关心的是如何高效地计算这些级数的前n项系数。这就涉及多项式形式幂级数的基本操作加法、乘法卷积、求逆、exp指数、ln对数、幂等。为什么这些操作有用让我们回到“不含长度为k1递增子序列”的例子。前面提到其EGF可能具有 exp( Σ_{m1}^{k} x^m / m ) 的形式。我们来验证一个简单情况k1即严格递减排列。显然只有一个排列是严格递减的对于给定的n个元素。所以 a_n^{(1)} 1 for all n≥0。其EGF就是 Σ_{n≥0} 1 * x^n / n! exp(x)。而 exp( Σ_{m1}^{1} x^m / m ) exp(x)。吻合。对于k2即排列的LIS长度≤2这样的排列称为“2-avoiding permutations”或“可分割排列”实际上LIS≤2的排列等价于排列可以分解为两个递减子序列其个数是第n个Catalan数让我们计算一下n1:1, n2:2, n3:5 (123不行LIS3)枚举一下(132, 213, 231, 312, 321)共5个确实是Catalan数。Catalan数的EGF不是简单的初等函数但已知其OGF是 (1 - sqrt(1-4x))/(2x)。那么其EGF可以通过OGF变换得到或者已知 Σ C_n * x^n / n! 满足某个微分方程。而 exp( Σ_{m1}^{2} x^m / m ) exp(x x^2/2)。这个函数的级数展开前几项是1 x (11/2)*x^2/2! ... 1 x (3/2)x^2/2 ... 1 x (3/4)x^2 ...。当n2时系数是3/4 * 2! 1.5不是整数显然不对。所以我的猜测 exp(Σ x^m/m) 可能不对。更准确的公式来自Gessels theorem记长度为n且LIS长度k的排列个数为 a_n^{(k)}则其指数生成函数满足 Σ_{n≥0} a_n^{(k)} x^n / n! Det( I_{k×k} Q_{k×k} )其中Q是一个Toeplitz矩阵其(i,j)元为 x^{|i-j|} / (|i-j|)!这比较复杂。但核心思想是许多排列计数问题的生成函数可以写成矩阵行列式或某个简单函数的exp。而计算矩阵行列式或exp都需要多项式操作。多项式exp的组合意义非常深刻exp(F(x)) 的EGF对应于由“原子”F(x)所描述的对象构成的所有无序集合。例如如果F(x)是连通图的EGF那么exp(F(x))就是所有图的EGF。在我们的排列问题中我们经常需要将排列分解为若干个互不干扰的“组件”每个组件的生成函数是F(x)那么所有排列的生成函数就是 exp(F(x))。容斥原理中我们有时会先计算“包含某种结构”的排列其生成函数可能是G(x)那么“不包含该结构”的生成函数可能就是 exp(某种形式) 或 G(x)的逆。多项式ln是exp的逆运算它从一个组合类的生成函数中提取其连通分量的生成函数。在实际计算中给定一个形式幂级数 F(x) Σ_{i≥0} f_i x^i我们想计算 G(x) exp(F(x)) 的前n项系数。这可以通过牛顿迭代法等算法在 O(n log n) 时间内完成。同样求逆、ln、幂等操作也有O(n log n)的算法。这些构成了现代多项式技术解决组合计数问题的基石。对于LOJ3395这道具体的题目虽然原题面没有给出但结合“容斥生成函数多项式”这个标签以及“Yet Another Permutation Problem”这个名称我推测它很可能涉及以下模式定义了一个在排列上容易描述的“坏性质”。通过容斥原理将计数转化为计算包含特定“坏结构”的排列数。发现这些“坏结构”在排列中是相互独立的或者可以被分解成若干独立的部分。因此包含特定大小k的坏结构的排列数其EGF可以写成一个基础结构的EGF的k次方再除以k!因为结构是无序的即类似于 (F(x))^k / k! 的形式。对所有k从容斥求和得到总生成函数Σ_{k≥0} (-1)^k * (F(x))^k / k! exp(-F(x))。最终答案就是 n! * [x^n] exp(-F(x))。问题归结为计算 F(x)通常是一个简单的级数然后计算 exp(-F(x)) 的前n项系数这需要多项式exp。或者步骤4和5可能略有变化但核心一定是容斥原理引导出了一个生成函数的表达式而这个表达式需要用到多项式exp/ln来最终计算系数。6. 从理论到实现算法步骤与细节假设我们已经通过组合分析得到了最终生成函数的表达式例如 A(x) exp(-B(x))其中 B(x) Σ_{i≥1} b_i x^i 是一个已知的多项式或形式幂级数。我们需要计算的是 a_n n! * [x^n] A(x)。具体的算法步骤如下6.1 步骤一确定B(x)首先我们需要根据题目的具体约束推导出B(x)的表达式。这通常是整个问题中最具组合洞察力的一步。例如在某个问题中如果“坏结构”是“一个长度为2的特定模式”并且该模式在排列中互不相交即不共享元素那么包含k个这样的坏结构的排列其EGF可能就是 (x^2/2)^k / k!这里x^2/2可能是描述一个坏结构对大小的贡献。那么对所有k求和得到 A(x) Σ_{k≥0} (-1)^k (x^2/2)^k / k! exp(-x^2/2)。此时 B(x)x^2/2。在更复杂的问题中B(x)可能是一个更复杂的级数比如 Σ_{i in S} c_i x^i / i!其中S是某个集合c_i是系数。我们需要精确地计算出B(x)的前n项系数因为最终只需要A(x)的前n项。6.2 步骤二多项式表示与卷积在计算机中我们使用长度为N通常为大于n的2的幂的数组来表示多项式数组下标i存储x^i项的系数。我们需要计算 A(x) exp(-B(x)) mod x^{n1}即忽略x^{n1}及更高次项。多项式exp的计算依赖于牛顿迭代。已知要求 G(x) exp(F(x))即满足 ln G(x) - F(x) 0。牛顿迭代公式为 G_{next}(x) G(x) * (1 - ln G(x) F(x)) mod x^{2m} 其中m是当前已知项数的两倍。我们需要实现多项式的基本操作乘法使用FFT快速傅里叶变换或NTT数论变换复杂度O(N log N)。在模意义下计数通常使用NTT。求逆假设已知 H(x) * H_inv(x) 1 mod x^m求 H_inv(x) mod x^{2m}。也可以用牛顿迭代H_inv_next H_inv * (2 - H * H_inv) mod x^{2m}。对数ln计算 ln P(x) 需要先求导再乘逆元再积分。即 ln P(x) ∫ (P(x) / P(x)) dx。这需要多项式求导、求逆、乘法和积分。指数exp如上所述使用牛顿迭代内部会调用ln和乘法。因此要实现多项式exp我们需要先实现多项式乘法、求逆、对数ln。这些是标准模板。6.3 步骤三边界处理与常数优化在实际编码中需要注意模数通常使用998244353或1004535809等原根为3的NTT友好质数。长度每次进行多项式操作前要确保数组长度是2的幂并且足够容纳所需项数通常是扩展到大于等于n1的最小2的幂。在牛顿迭代中长度会逐次翻倍。清零多项式操作后高阶项超过当前模数x^m的部分要及时清零避免污染后续计算。常数因子在计算EGF时系数包含阶乘和阶乘逆元。通常我们会预处理出[0, n]范围内的阶乘fac[i]和阶乘逆元invfac[i]。这样如果B(x)的系数b_i是“某种结构的个数”我们存储到数组里的可能是 b_i / i!即EGF的系数也可能是普通OGF系数需要仔细区分。在计算A(x)exp(-B(x))后得到的a_i是EGF的系数最终答案 a_n * n! 才是排列数。所以通常我们让B(x)和A(x)都代表EGF这样最后直接取a_n * n!即可。在实现时传入的B多项式数组其第i项存储的是 b_i / i!如果b_i是OGF系数。这需要根据题目推导的公式来调整。6.4 步骤四最终答案计算计算出A(x)的前n1项系数EGF系数后我们需要的答案就是 a_n * n! mod MOD。注意这里的n是排列长度即题目输入的参数。7. 例题延伸与变式思考为了加深理解我们看一个简化版的问题它完整走通了容斥-生成函数-多项式的流程。问题计算长度为n的排列中不包含任何连续两个元素递增即不存在i使得 p_i p_{i1}的排列个数。换句话说排列是“交替”的但这里要求严格递减的相邻关系不是禁止上升相邻对。这样的排列被称为“无上升相邻对的排列”。解法容斥设坏事件A_i为位置i和i1上的元素构成一个上升对即p_i p_{i1}。共有n-1个这样的事件。我们要求不满足任何A_i的排列数。计算交集对于一个大小为k的坏事件集合S要求这些事件同时发生。这意味着在排列中有k个指定的相邻位置对是上升的。注意这些指定的相邻对可能相邻比如A_i和A_{i1}这意味着位置i, i1, i2满足 p_i p_{i1} 且 p_{i1} p_{i2}这并不矛盾它只是强制了一个更长的递增段长度为3。但是如果S中包含两个事件A_i和A_j且它们对应的区间有重叠但不连续这是不可能的因为每个事件只涉及两个连续位置实际上S定义了一组上升的边这些边将位置序列分割成一些连续的“上升段”和孤立的点。更准确地说如果我们把必须上升的相邻对看作在位置1..n之间画上了一些“上升箭头”那么这些箭头会将整个排列分成若干个连续的“块”在每个块内部相邻元素必须严格递增因为所有块内的相邻对都被要求上升。不同的块之间则没有约束。生成函数考虑一个长度为L的块内部必须严格递增。对于一个固定的元素集合严格递增的顺序只有一种。所以如果我们知道一个块包含了哪些数字那么这个块内部的排列方式就唯一确定了。因此一个长度为L的块其本质就是从n个数字中选出L个数字然后它们必须按升序排列。但是在容斥的框架下我们是在计数“至少违反S中规则”的排列此时我们只关心那些被“上升箭头”强制约束的块其他位置可以任意排列吗不其他位置之间没有强制要求上升或下降。然而这里有一个关键点当我们将一些相邻位置强制为上升后剩下的“自由”位置它们之间的相对顺序以及它们与“上升块”之间的相对顺序仍然是任意的排列。这变得复杂了。一个更简洁的方法是使用指数型生成函数和集合构造。我们换个角度考虑排列的“下降沿”。一个排列可以看作是由一些“递增段”和“下降沿”连接而成。但禁止上升相邻对意味着递增段的长度只能是1因为长度≥2的递增段内部必然包含上升相邻对。所以排列被“下降沿”分割成一系列长度为1的“段”这似乎不对因为下降沿可以连续。实际上无上升相邻对的排列等价于排列中每个“上升”只能出现在长度为1的递增段中但这不可能因为长度为1的段没有相邻对。所以这个条件等价于排列中没有上升相邻对即每个相邻对都是下降或相等的但排列是双射所以不可能相等。因此这等价于排列是严格递减的显然不是因为排列3,1,2有上升相邻对(1,2)而排列2,1,3没有上升相邻对但它不是严格递减的。所以“无上升相邻对”并不意味着整个排列递减。让我们枚举n3所有排列共6个。无上升相邻对的意味着对于所有i1,2不能有p_i p_{i1}。123: (1,2)和(2,3)都上升不符合。132: (1,3)上升(3,2)下降。不符合因为(1,3)不是相邻对我们检查的是相邻对(1,2)和(2,3)。(1,2):13上升不符合。所以132不符合。213: (2,1)下降(1,3)上升。不符合(1,3)是上升相邻对(1,3)不是相邻对相邻对是(2,1)和(1,3)。(1,3)中13上升所以不符合。231: (2,3)上升(3,1)下降。不符合。312: (3,1)下降(1,2)上升。不符合。321: (3,2)下降(2,1)下降。符合。 所以n3时只有1个321。这看起来像是所有排列都是严格递减的但n2时排列有2个12不符合21符合也是1个。n4时可以枚举一下似乎也只有严格递减排列1个实际上无上升相邻对意味着排列中每个位置i除了最后一个都有p_i p_{i1}这正是一个严格递减序列。而严格递减序列对于一个给定的集合只有一种。所以答案确实是1。这个问题太简单了没有达到练习的目的。我们换一个更有代表性的例子计算无不动点的排列错排个数。这虽然经典但通常用递推或简单容斥不需要多项式exp。但我们可以强行用生成函数多项式方法做一遍以展示流程。错排问题排列π满足 π(i) ≠ i 对所有i成立。容斥坏事件A_i: π(i)i。共有n个事件。计算交集对于大小为k的集合S|⋂_{i∈S} A_i| (n-k)!。因为指定了k个位置上的数字固定剩下n-k个位置任意排列。直接容斥公式D_n Σ_{k0}^{n} (-1)^k * C(n, k) * (n-k)! n! * Σ_{k0}^{n} (-1)^k / k!。这是经典公式。生成函数视角考虑指数生成函数 D(x) Σ_{n≥0} D_n x^n / n!。代入公式 D_n / n! Σ_{k0}^{n} (-1)^k / k!。 注意到右边是 Σ_{k≥0} (-1)^k / k! 截断到n项但因为kn时1/k!项在x^n系数中贡献为0实际上Σ_{k≥0} (-1)^k / k! 就是 e^{-1}。而 D_n / n! 正是 e^{-1} 的泰勒展开的前n项部分和。但作为形式幂级数我们有 D(x) Σ_{n≥0} ( Σ_{k0}^{n} (-1)^k / k! ) x^n。 交换求和顺序 Σ_{k≥0} (-1)^k / k! Σ_{n≥k} x^n Σ_{k≥0} (-1)^k / k! * x^k / (1-x) (1/(1-x)) * Σ_{k≥0} (-x)^k / k! (1/(1-x)) * e^{-x}。 所以错排数的EGF是 D(x) e^{-x} / (1-x)。多项式方法如果我们想用多项式技术计算前n个错排数我们可以计算形式幂级数 F(x) e^{-x} 和 G(x) 1/(1-x) 的卷积。e^{-x} 可以通过多项式exp计算exp(-x)而 1/(1-x) 就是 Σ x^i。卷积即可得到D(x)的系数。这虽然有点杀鸡用牛刀但展示了流程。对于更复杂的LOJ3395其B(x)很可能不是一个简单的-x而是一个更复杂的形式例如 B(x) Σ_{i2}^{k} x^i / i 或其他形式最终A(x)exp(-B(x))然后需要计算这个exp。8. 总结与经验分享回顾整个解题过程我们可以提炼出解决这类“排列计数容斥生成函数多项式”问题的通用思维框架定义与转化清晰定义问题中的“好排列”和“坏事件”。尝试将“好排列”计数转化为“坏事件”的容斥。容斥代数化写出容斥公式并观察交集项 |⋂_{i∈S} Ai| 的计算是否只依赖于S的大小或某种简单特征如S中元素构成的连通块数。如果只依赖于大小那么容斥和式可以转化为卷积形式。生成函数选择根据计数对象是排列带标签选择指数型生成函数EGF。将容斥和式表示为某个生成函数的系数。关键一步是识别出所有包含特定大小k的“坏结构”的排列其EGF是否可以写成某个基础结构EGF的k次方除以k!即集合构造。如果能那么对k求和就会自然引出exp。得到闭式通过组合解释求出基础结构的EGF记为F(x)。那么包含任意个坏结构的排列EGF可能是 exp(F(x))如果坏结构之间无影响。而好排列的EGF通过容斥往往就是 exp(±F(x)) 或与之相关的形式。多项式计算将问题归结为计算某个形式幂级数如exp(F(x))的前n项系数。使用多项式模板NTT、求逆、ln、exp进行高效计算。提取答案从EGF的系数还原回排列数乘以n!即可。在实际操作中最困难也最关键的是第3、4步如何将组合结构翻译成生成函数的语言。这需要大量的练习和洞察力。一个实用的建议是从简单情况小n枚举观察数列猜测生成函数或者尝试用动态规划推导生成函数的方程。另外在实现多项式运算时要特别注意模数、长度、清零等细节并做好常数优化因为NTT的常数较大。对于n在10^5级别的题目O(n log n)的算法是可行的。最后这类问题之美在于它连接了组合直观、代数工具和算法实现。理解其本质后你会发现很多看似不同的题目都共享同一套内核。希望这篇长文能帮你打通任督二脉下次遇到“Yet Another”问题时能自信地拿起容斥、生成函数和多项式这三把利器。
![2026学术工具专业测评｜Paperxie全维度性能实测报告[特殊字符]](http://pic.xiahunao.cn/yaotu/2026学术工具专业测评｜Paperxie全维度性能实测报告[特殊字符])
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
