多项式特训。开始大生产运动。不得不说黑题通过数一下就上来了。
由于大多数比较工业所以一律不放代码。
歌被咕了，打算报复性整点活。整活其实不一定需要整活用的曲。
目前打算是放点“确实有歌词”的，现在备选歌单：
- Credits EX
- Duplicity Shade
- Random ("Take #8" Full Version)
- 脑力
- Viyella's Memory
P7435 简单的排列计数
先来点比较清新的水一下。然而太久不做多项式题了码的时候出了很大的锅。
首先一个显然的 dp：从小到大插入数，设 \(dp_{i,j}\) 为插入 \(i\) 有 \(j\) 个逆序对的答案，那么
\[dp_{i,j}=\sum_{k=0}^{i-1}dp_{i-1,j-k}i^k \]然后你发现这玩意不就是
\[\prod_{i=1}^nf_i \]其中
\[f_i=\sum_{n=0}^{i-1}i^nx^n=\frac{1-(ix)^i}{1-ix} \]那么套路 \(\ln\exp\) 一下。
分子：
\[\begin{aligned} &\sum_{i=1}^n\ln(1-(ix)^i)\\ =&-\sum_{i=1}^n\sum_{j=1}\frac{(ix)^{ij}}j \end{aligned} \]\(O(\min(n,k)\log k)\)。
分母：
\[\begin{aligned} &\sum_{i=1}^n\ln(1-ix)\\ =&-\sum_{i=1}^n\sum_{j=1}\frac{(ix)^j}j\\ =&-\sum_{j=1}\frac{x^j}j\sum_{i=1}^ni^j\\ =&-\sum_{j=1}\frac{x^j}{j(j+1)}\sum_{i=0}^j\binom{j+1}iB_i(n+1)^{j-i+1}\\ =&-\sum_{j=1}\frac{x^j}{j(j+1)}\left(-B_{j+1}+(j+1)!\sum_{i=0}^{j+1}\frac{B_i}{i!}\frac{(n+1)^{j+1-i}}{(j+1-i)!}\right) \end{aligned} \]爆算就行了。提醒忘了的同学伯努利数的 EGF 是 \(\dfrac x{e^x-1}\)。
然后是我太久不写多项式题了导致写的时候出现的一些锅：
- 提取 EGF 系数没乘阶乘。
- 经典数组不清空。
- \(\ln\) 把负号吃了。
- 注意分子第一个上界是 \(\min(n,k)\)。
P2767 树的数量
早就写了，然而现在水一下博。
容易得到答案的生成函数
\[F=x(1+F)^m \]那拉格朗日反演
\[[x^n]F=\frac 1n[x^{n-1}](1+x)^{nm}=\frac{\binom{nm}{n-1}}n \]写 lucas。
P5219 无聊的水题 I
我们知道这玩意可以变成 Prufer 序列。那么就是 \(n-2\) 长度值域 \(n\) 出现次数最多元素出现 \(m\) 次的序列个数。容斥一下变成出现次数不超过 \(m\) 次，那这玩意显然是
\[(n-2)![x^{n-2}]\left(\sum_{i=0}^{m-1}\frac{x^i}{i!}\right)^n \]我这一版的求逆没有清空调了半天。日。
P5900 无标号无根树计数
我以为难度全都在代码。
首先套路考虑有根树然后把根不是中心的砍掉。钦定一个根，剩下的就是个 MSET。所以
\[F(x)=x\exp\sum_{i=1}\frac{F(x^i)}i \]现在的问题是怎么算这个东西。一个 trivial 的想法是套个牛顿迭代上去。
\[\begin{aligned} F(x)=&x\exp\sum_{i=1}\frac{F(x^i)}i\\ \frac{F(x)}x=&\exp\sum_{i=1}\frac{F(x^i)}i\\ \ln\frac{F(x)}x=&\sum_{i=1}\frac{F(x^i)}i\\ \ln\frac{F(x)}x-F(x)-G=0 \end{aligned} \]其中 \(G=\sum_{i=2}\frac{F(x^i)}i\)。于是有牛顿迭代式子：
\[F=F_0-\frac{\ln\frac{F_0}x-F_0-G}{\frac 1{F_0}-1} \]实际上似乎不是想象中那么难写。
然后考虑怎么统计答案。首先如果根不是重心，那么肯定有一个儿子大于 \(\left\lceil\dfrac n2\right\rceil\)，枚举这个儿子大小算就行了。另外，如果 \(n\) 是偶数，那么 \(\dfrac n2\) 被算了两次，要减掉一次。
loj6538. 烷基计数 加强版 加强版
曾经记得写过某篇题解说过这玩意的生成函数就是
\[F=x\text{MSET}_3(F)+1=x\frac{F(x)^3+3F(x)F(x^2)+2F(x^3)}6+1 \]牛顿迭代。式子是：
\[F(x)=F_0(x)=\frac{x(F_0(x)^3+3F_0(x)F_0(x^2)+2F_0(x^3))-6F_0(x)+6}{3x(F_0(x)^2+F_0(x^2))-6} \]P6597 烯烃计数
把碳碳双键拆开变成两个根不超过 \(2\) 个儿子，其他节点不超过 \(3\) 个儿子的无标号有根树计数。那你一棵树就是两个烷基计数合起来，就是
\[G(x)=x\text{MSET}_2(F)+1=x\frac{F(x)^2+F(x^2)}2+1 \]碳碳双键相当于把两个拼一块，再套一个 \(\text{MSET}\)。
\[H(x)=x\frac{(G(x)-1)^2+G(x^2)-1}2 \]我发现我写代码的时候老是把 \(F(x^2)\) 写成 \(F(x)\)。
P6598 烷烃计数
首先无根树先看成有根树。然后就是根节点做个 \(\text{MSET}_4\)。式子好长。
\[G(x)=x\frac{F(x)^4+6F(x)^2F(x^2)+3F(x^2)^2+8F(x)F(x^3)+6F(x^4)}{24} \]去重采用和无标号无根树计数相同的策略即可。
看了看题解似乎有更加高妙的方法。刚才是钦定一个根的情况，设为 \(p\)。然后我们再枚举钦定一条边的情况，把两边拼起来（就是套个 \(\text{MSET}_2\)），记为 \(q\)，设 \(s=1\) 当且仅当有两个重心且等价，显然是把 \(F(x)\) 复读一遍，即 \(F(x^2)\)。那么我们的答案就是 \(p-q+s\)。
正确性考虑除重心外的点和其父亲边的贡献。若两个点等价，则其父亲边也等价，可以减掉。而重心不可能和其父亲边等价。而当有两个重心的时候，我们在重心等价时加上了 \(s\) 即可保证不漏掉。以上是 loj6512. 「雅礼集训 2018 Day8」C 的正解。
P4233 射命丸文的笔记
假期望。
先考虑哈密顿回路个数。\(n\) 个节点一个环排列然后剩下的边随便定向，方案显然 \((n-1)!2^{\binom n2-n}\)。然后考虑分母。就是强连通竞赛图个数。
考虑使用普通竞赛图表示强连通竞赛图。普通的显然是 \(2^{\binom n2}\)。
发现竞赛图由于每两个点之间都有连边所以拓扑序唯一。那么强连通缩点之后就是一串强连通竞赛图排一排。也就是 \(\text{Sequence}\) 构造。那么我们设普通竞赛图为 \(G\) ，强连通为 \(F\)，则有
\[G=\text{SEQ}(F)=\frac 1{1-F} \]\[F=1-\frac 1G \]完事。
tmd 我为什么 EGF 又忘乘阶乘。
P6295 有标号 DAG 计数
似乎 WC2019 中提到所谓“组合生成函数”用来计数带标号有向图，但是似乎泛用性并不高的样子。那就不管这个了。
考虑先求出任意的 DAG 然后给个 \(\ln\)。
像树枚举根，对于 DAG 我们枚举有几个源点。
设 \(f_n\) 为 \(n\) 个点的方案数。那么枚举 \(k\) 个源点向剩下的点任意连边，方案数显然
\[\sum_{k=1}^n\binom nk2^{n(n-k)}f_{n-k} \]显然会算重，想都不用想。经典容斥可以得到
\[f_n=\sum_{k=1}^n\binom nk(-1)^{k+1}2^{n(n-k)}f_{n-k} \]看着像卷积。但是得先搞明白组合数和 \(2^{n(n-k)}\)。组合数可以使用二项卷积的套路。对于后边这个东西，我们在 Chirp-Z Transform 里边见过：
\[n(n-k)=\binom n2-\binom k2-\binom{n-k}2 \]那就没了。设 \(g_i=\dfrac{(-1)^{i+1}x^i}{i!2^{\binom i2}}\)，那么显然 \(F(x)=F(x)G(x)+1\)。求个逆再取 \(\ln\) 就行了。
今天先这样。去贺一份有标号荒漠计数的线性做法。
标签：frac,ln,多项式,sum,计数,text,binom,杂题 From： https://www.cnblogs.com/gtm1514/p/17135378.html