生成函数练习记录

前言

最近把nflsoj上的题都贺完了，之前既定要补的题也已完成，算是步入小康，终于有了点自己可以支配的时间了。

这篇markdown中会记录我这段时光写过的组合计数题目，大概都会与生成函数相关。

题目没有按照难度排序。

题目会给多个链接，用以照顾对OJ有不同口味的人士。

题目记录均会在通过题目后开始撰写，因此无法保证完全按照思考过程来，但正确性和逻辑性会比较好。

很可能有typo，有细节的纰漏亦可指出。

[HEOI2016/TJOI2016] 求和 洛谷 / LOJ

直接给出 \(\Theta(n)\) 做法

\[\begin{aligned} Answer&=\sum_{i=0}^n\sum_{j=0}^n {n \brace k } \cdot 2^j \cdot j! \\&=\sum_{i=0}^n\sum_{j=0}^n\sum_{k=0}^j \cdot 2^j \cdot k^i \cdot \binom{j}{k} \cdot (-1)^{j-k} \\&=\sum_{k=0}^n( \sum_{i=0}^nk^i) \cdot \sum_{j=k}^n2^j \cdot (-1)^{j-k} \cdot \binom{j}{k} \\&=\sum_{k=0}^n( \sum_{i=0}^nk^i) \cdot [x^j](\dfrac{1-(2(x-1))^{n+1}}{1-2(x-1)}) \end{aligned} \]

先把 \(j\) 枚举的范围提升到 \(n\) ，方便交换∑，并且保证斯特林数不变

斯特林数不便处理，并且后面正好有一个 \(j!\) 展开后可以消掉一项，用组合意义展开，这里发现即使当 \(j \geq i\) 的时候展开的结果还是对的

\(i\) 出现的最少，把它交换到里面去。

后面的那部分式子是生成函数的加法复合，使用生成函数表示出来

∑里左边那项可以 \(\log n\) 计算，用线性筛筛出质数位的幂后可以做到线性。右边那项把上面展开，然后短多项式求逆，也可以做到线性。