Mar 14, 2022 生成函数 普通生成函数𝐹(𝑥)=∑𝑛𝑎𝑛𝑎𝑛(𝑛≥0)等比数列数列<1,𝑝,𝑝2,𝑝3,...,𝑝𝑛,...>的生产成函数𝐹(𝑥)=∑𝑛≥0𝑝𝑛𝑥𝑛的封闭式为𝐹(𝑥)=11−𝑝𝑥𝑎=<1,2,3,4...>生成函数𝐹(𝑥)=∑𝑛≥0(𝑛+1)𝑥𝑛=∑𝑛≥1𝑛𝑥𝑛−1=∑𝑛≥0(𝑥𝑛)′=(11−𝑥)′=1(1−𝑥)2(𝑚𝑛),(𝑛≥0,𝑚是常数)𝐹(𝑥)=∑𝑛≥0(𝑚𝑛)𝑥𝑛=(1+𝑥)𝑚(𝑚+𝑛𝑛)𝐹(𝑥)=∑𝑛≥0(𝑚+𝑛𝑛)𝑥𝑛=1(1−𝑥)𝑚+1斐波那其数列 𝑎0=0,𝑎1=1,𝑎𝑛=𝑎𝑛−1+𝑎𝑛−2(𝑛>1)𝐹(𝑥)=𝑥𝐹(𝑥)+𝑥2𝐹(𝑥)−𝑎0𝑥+𝑎1𝑥+𝑎0=𝑥1−𝑥−𝑥2通过求解𝐴1−𝑎𝑥+𝐵1−𝑏𝑥=𝑥1−𝑥−𝑥2得𝑥1−𝑥−𝑥2=∑𝑛≥0𝑥𝑛1√5((((1+√52)𝑛−(1−√52)𝑛)))指数生产成函数(exponential generating function，EGF)̂𝐹(𝑥)=∑𝑛≥0𝑎𝑛𝑥𝑛𝑛!### 运算̂𝐹(𝑥)̂𝐺(𝑥)=∑𝑖≥0𝑎𝑖𝑥𝑖𝑖!∑𝑗≥0𝑏𝑗𝑥𝑗𝑗!=∑𝑛≥0𝑥𝑛∑𝑛𝑖=1𝑎𝑖𝑏𝑛−𝑖1𝑖!(𝑛−𝑖)!=∑𝑛≥0𝑥𝑛𝑛!∑𝑛𝑖=0(𝑛𝑖)𝑎𝑖𝑏𝑛−𝑖因此 ̂𝐹(𝑥)̂𝐺(𝑥) 是序列 <∑𝑛𝑖=0(𝑛𝑖)𝑎𝑖𝑏𝑛−𝑖> 的指数生成函数。<1,1,1,1,...>∑𝑛≥1𝑥𝑛𝑛!=𝑒𝑥<1,𝑝,𝑝2,...>∑𝑛≥1𝑝𝑛𝑥𝑛𝑛!=𝑒𝑝𝑥𝑎𝑛=𝑛!̂𝑃(𝑥)=∑𝑛≥0𝑛!𝑥𝑛𝑛!=∑𝑛≥0𝑥𝑛=11−𝑥圆排列̂𝑄(𝑥)=∑𝑛≥1(𝑛−1)!𝑥𝑛𝑛!=∑𝑛≥1𝑥𝑛𝑛=−ln(1−𝑥)=ln(11−𝑥)圆排列与排列的关系生成树计数如果 𝑛 个点 带标号 生成树的 EGF 是 ̂𝐹(𝑥) ，那么 𝑛 个点 带标号 生成森林的EGF 就是𝑒𝑥𝑝̂𝐹(𝑥) ——直观理解为，将 𝑛 个点分成若干个集合，每个集合构成一个生成树的方案数之积。图如果 𝑛 个点带标号无向连通图的 EGF 是 ̂𝐹(𝑥)，那么 𝑛 个点带标号无向图的EGF 就是 𝑒𝑥𝑝̂𝐹(𝑥)，后者可以很容易计算得到 𝑒𝑥𝑝̂𝐹(𝑥)=∑𝑛≥02(𝑛2)𝑥𝑛𝑛!。因此要计算前者，只需要一次多项式 ln 即可。错排数:长度为 𝑛 的一个错排是满足 𝑝𝑖≠𝑖 的排列。不动点：有多少个映射 𝑓:1,2,⋯,𝑛→1,2,⋯,𝑛，使得𝑓∘𝑓∘⋯∘𝑓⏟⏟⏟⏟⏟𝑘=𝑓∘𝑓∘⋯∘𝑓⏟⏟⏟⏟⏟𝑘−1𝑛𝑘≤2×106,1≤𝑘≤3。考虑 𝑖 向 𝑓(𝑖) 连边。相当于我们从任意一个 𝑖 走 𝑘 步和走 𝑘−1 步到达的是同一个点。也就是说基环树的环是自环且深度不超过 𝑘（根结点深度为 1）。把这个基环树当成有根树是一样的。因此我们的问题转化为：𝑛 个点带标号，深度不超过 𝑘 的有根树森林的计数。考虑 𝑛 个点带标号深度不超过 𝑘 的有根树，假设它的生成函数是 ̂𝐹𝑘(𝑥)=∑𝑛≥0𝑓𝑛,𝑘𝑥𝑛𝑛!。考虑递推求 ̂𝐹𝑘(𝑥)。深度不超过 𝑘 的有根树，实际上就是深度不超过 𝑘−1 的若干棵有根树，把它们的根结点全部连到一个结点上去。因此̂𝐹𝑘(𝑥)=𝑥exp̂𝐹𝑘−1(𝑥)那么答案的指数生成函数就是 exp̂𝐹𝑘(𝑥)。求它的第 𝑛 项即可。Lust给你一个 𝑛 个数的序列 𝑎1,𝑎2,⋯,𝑎𝑛，和一个初值为 0 的变量 𝑠，要求你重复以下操作 𝑘 次：•在 1,2,⋯,𝑛 中等概率随机选择一个 𝑥。•令 𝑠 加上 ∏𝑖≠𝑥𝑎𝑖。•令 𝑎𝑥 减一。求 𝑘 次操作后 𝑠 的期望。1≤𝑛≤5000,1≤𝑘≤109,0≤𝑎𝑖≤109。 假设 𝑘 次操作后 𝑎𝑖 减少了 𝑏𝑖，那么实际上𝑠=∏𝑛𝑖=1𝑎𝑖−∏𝑛𝑖=1(𝑎𝑖−𝑏𝑖)因此实际上我们的问题转化为，求 𝑘 次操作后 ∏𝑛𝑖=1(𝑎𝑖−𝑏𝑖) 的期望。不妨考虑计算每种方案的的 ∏𝑛𝑖=1(𝑎𝑖−𝑏𝑖) 的和，最后除以 𝑛𝑘。而 𝑘 次操作序列中，要使得 𝑖 出现了 𝑏𝑖 次的方案数是𝑘!𝑏1!𝑏2!⋯𝑏𝑛!这与指数生成函数乘法的系数类似。设 𝑎𝑗 的指数生成函数是𝐹𝑗(𝑥)=∑𝑖≥0(𝑎𝑗−𝑖)𝑥𝑖𝑖!那么答案就是[𝑥𝑘]∏𝑛𝑗=1𝐹𝑗(𝑥)为了快速计算答案，我们需要将 𝐹𝑗(𝑥) 转化为封闭形式：𝐹𝑗(𝑥)=∑𝑖≥0𝑎𝑗𝑥𝑖𝑖!−∑𝑖≥1𝑥𝑖(𝑖−1)!=𝑎𝑗𝑒𝑥−𝑥𝑒𝑥=(𝑎𝑗−𝑥)𝑒𝑥因此我们得到∏𝑛𝑗=1𝐹𝑗(𝑥)=𝑒𝑛𝑥∏𝑛𝑗=1(𝑎𝑗−𝑥)其中 ∏𝑛𝑗=1(𝑎𝑗−𝑥) 是一个 𝑛 次多项式，可以暴力计算出来。假设它的展开式是 ∑𝑛𝑖=0𝑐𝑖𝑥𝑖，那么∏𝑛𝑗=1𝐹𝑗(𝑥)=(∑𝑖≥0𝑛𝑖𝑥𝑖𝑖!)(∑𝑛𝑖=0𝑐𝑖𝑥𝑖)=∑𝑖≥0∑𝑖𝑗=0𝑐𝑗𝑥𝑗𝑛𝑖−𝑗𝑥𝑖−𝑗(𝑖−𝑗)!=∑𝑖≥0𝑥𝑖𝑖!∑𝑖𝑗=0𝑛𝑖−𝑗𝑖𝑗𝑐𝑗计算这个多项式的 𝑥𝑘 项系数即可。