证明我存在过
不会数学，若有错误请指出 qwq
指数型生成函数 $\rm{EGF}$
基本定义：
$$
F(x)=\sum_{i=0}^{\infty}\frac{x^i}{i!}
$$
一些性质：
$$
e^x=\sum_{i=0}^{\infty}\frac{x^i}{i!}
$$
一些意义：先定义 $F,G$ ：
$$
F(x)=\sum_{i=0}^{\infty}a_i\frac{x^i}{i!},G(x)=\sum_{i=0}^{\infty}b_i\frac{x^i}{i!}
$$
将其乘起来：
$$
(F\cdot G)(x)=\sum_{n=0}^{\infty}\left(\sum_{i+j=n}{n\choose i}a_ib_j\right)\frac{x^n}{n!}
$$
可见如果 $x^i$ 的系数表示选择 $i$ 个物品的方案数，将其相乘后的 $x^i$ 的系数就是从 $a,b$ 里一共选出 $i$ 个物品的排列数。
题目：$\rm{CF891E\ Lust}$
第 $i$ 轮操作带来的贡献为：
$$
\prod_{j=1,j\not=i}^{n}a_j\\
a_i\prod_{j=1,j\not=i}^{n}a_j-(a_i-1)\prod_{j=1,j\not=i}^{n}a_j
$$
设 $S_m$ 表示经过 $m$ 次操作后的 $\prod\limits_{i=1}^{n}a_i$ ，那么第 $i$ 轮带来的贡献即 $S_{i-1}-S_i($ ，然后显而易见答案为：
$$
ans=\sum_{i=1}^{k}S_{i-1}-S_i=S_0-S_k
$$
设 $b_i$ 表示经过 $i$ 次操作后 $a_i$ 将变为 $a_i-b_i$ ，那么有：
$$
S_0=\prod_{i=1}^{n}a_i,S_k=\prod_{i=1}^{n}(a_i-b_i)
$$
考虑将期望转化为计数，那么答案为：
$$
ans=\frac{1}{n^k}\left(\sum_{\sum b_i=k}\frac{k!}{\prod b_i!}\prod_{i=1}^{n}a_i\right)\\
ans=\frac{k!}{n^k}\left(\sum_{\sum b_i=k}\frac{1}{\prod b_i!}\prod_{i=1}^{n}(a_i-b_i)\right)\\
$$
令 $F_n(x)$ 为：
$$
F_n(x)=\sum_{i=0}^{\infty}\frac{(a_n-i)x^i}{i!}
$$
那么有：
$$
\begin{aligned}
ans&=\frac{k!}{n^k}[x^k]\left(\prod_{i=1}^{n}F_i(x)\right)\\
&=\frac{k!}{n^k}[x^k]\left(\prod_{i=1}^{n}\sum_{j=0}^{\infty}\frac{(a_i-j)x^j}{j!}\right)\\
&=\frac{k!}{n^k}[x^k]\left(\prod_{i=1}^{n}\sum_{j=0}^{\infty}(\frac{a_i}{j!}-\frac{j}{j!})x^j\right)\\
&=\frac{k!}{n^k}[x^k]\left(\prod_{i=1}^{n}\left(\sum_{j=0}^{\infty}\frac{a_i}{j!}x^j-\sum_{j=0}^{\infty}\frac{j}{j!}x^j\right)\right)\\
\end{aligned}
$$
对于前面的 $\sum$ ，显然可以直接通过指数型生成函数的定义转化，后面的那个，由于 $j=0$ 的时候 $\frac{j}{j!}=0$ ，所以有：
$$
\sum_{j=0}^{\infty}\frac{j}{j!}x^j=\sum_{j=1}^{\infty}\frac{1}{(j-1)!}x^j=x\sum_{j=0}^{\infty}\frac{1}{j!}x^j
$$
带回原式：
$$
\begin{aligned}
ans&=\frac{k!}{n^k}[x^k]\left(\prod_{i=1}^{n}\left(a_ie^x-xe^x\right)\right)\\
&=\frac{k!}{n^k}[x^k]\left(\prod_{i=1}^{n}(a_i-x)e^x\right)\\
&=\frac{k!}{n^k}[x^k]\left(\sum_{i=0}^{\infty}\frac{n^i}{i!}x^i\left(\prod_{i=1}^{n}(a_i-x)\right)\right)\\
\end{aligned}
$$
令：
$$
g(m)=(\prod_{i=1}^{n}(a_i-x))(m)
$$
那么可以得到：
$$
\begin{aligned}
ans&=\frac{k!}{n^k}\left(\sum_{i=0}^{k}\frac{n^i}{i!}g(k-i)\right)\\
&=\sum_{i=0}^{k}k^{\underline{k-i}}n^{i-k}g(k-i)\\
&=\sum_{i=0}^{k}k^{\underline{i}}n^{-i}g(i)\\
\end{aligned}
$$
发现 $g$ 是由 $n$ 个最高项为 $1$ 的多项式成得，所以 $g$ 的最高项不超过 $n$ ，因此最终答案为：
$$
ans=\sum_{i=0}^{\min(k,n)}k^{\underline{i}}n^{-i}g(i)\\
$$
值得一提的是，最后这个阶乘的处理。
问 $\rm{CYJian}$ 只得到了分段打表处理阶乘的做法，但是其实将阶乘带入式子可以发现正好可以和 $i$ 抵消，将其翻转后又因为限制了枚举的上界，这个时候就可以直接暴力算下降幂了。
还有需要总结的就是，期望和计数之间的互相转化很灵活。
多项式多点求值
首先有一个式子：
$$
f(x)\equiv f(x_0)\bmod{x-x_0}
$$
但是显然不能对于每一个询问都暴力多项式取模。
考虑一个多项式模一个 $n$ 次多项式后，项数一定不超过 $n$ 。
利用这点，就可以分治做了，每一段分治区间先模一下，然后往下递归即可。
多项式对数函数
显然有：
$$
\ln'(f(x))=\frac{f'(x)}{f(x)}\\
\ln(f(x))=\int\frac{f'(x)}{f(x)}\\
$$
然后多项式求逆 $+$多项式求导 $+$多项式积分就没了。
题目：幂
传送门
$$
\sum_{n=0}^{\infty}f(n)r^n\\
\sum_{n=0}^{\infty}\left(\sum_{i=1}^{m}a_in^i\right)r^n\\
\sum_{i=0}^{m}a_i\left(\sum_{n=1}^{\infty}n^ir^n\right)\\
$$
现在要求这玩意，令：
$$
F_i(x)=\sum_{n=1}^{\infty}r^nn^i\\
$$
发现这玩意不好求，接下来的就比较巧。
$$
\begin{aligned}
F_i(r)&=\sum_{n=1}^{\infty}r^nn^i\\
&=r\sum_{n=1}^{\infty}r^{n-1}n^i\\
&=r\sum_{n=0}^{\infty}r^{n}(n+1)^i\\
&=r\sum_{n=0}^{\infty}r^{n}\sum_{j=0}^{i}{i\choose j}n^j\\
&=r\sum_{j=0}^{i}{i\choose j}\sum_{n=0}^{\infty}r^{n}n^j\\
&=r\sum_{j=0}^{i}{i\choose j}F_j(r)\\
\end{aligned}
$$
然后就可以分治 $\rm{NTT}$ 了。
题目：付公主的背包
对于一个体积为 $v_i$ 的物品，其生成函数为：
$$
F_i(x)=\sum_{n=0}^{\infty}x^{nv_i}=\frac{1}{1-x^{v_i}}
$$
然后要求的就是：
$$
G(x)=\prod_{i=1}^{n}\frac{1}{1-x^{v_i}}
$$
求 $\ln$ ：
$$
\begin{aligned}
(\ln F(x))’&=\frac{F'(x)}{F(x)}\\
&=(1-x^{v_i})F'(x)\\
&=(1-x^{v_i})\left(\sum_{n=0}^{\infty}(nv_i)x^{nv_i-1}\right)\\
&=\sum_{n=0}^{\infty}(nv_i)x^{nv_i-1}-\sum_{n=0}^{\infty}(nv_i)x^{nv_i}\\
&=\sum_{n=0}^{\infty}v_ix^{nv_i-1}\\
\end{aligned}
$$
显然函数相加后取导和取导后相加是等价的，$v_i$ 相同的开个桶，这样就可以在 $O(n\log n)$ 的时间内得出 $(\ln F(x))’$ 的和了。
积分回来后做 $\exp$ 就好了。
题目：集合划分计数
首先令 $F(x)$ 的 $x^n$ 的系数表示大小为 $n$ 的集合方案数。
那么 $F(x)=\sum_{n=0}^{\infty}\frac{x^n}{n!}$ ，也就是 $e^x$ ，然后去掉空集的情况就是 $e^x-1$ 。
然后把空集组合在一起，方案数就是 $e^{e^x-1}$ 。
然后多项式 $\exp$ 就没了。
题目：「THUPC 2017」小 L 的计算题
写出 $f_k$ 的生成函数：
$$
\begin{aligned}
F(x)&=\sum_{k=0}^{\infty}f_kx^k\\
&=\sum_{k=0}^{\infty}x^k\sum_{i=1}^{n}a_i^k\\
&=\sum_{i=1}^{n}\sum_{k=0}^{\infty}(xa_i)^k\\
&=\sum_{i=1}^{n}\frac{1}{1-xa_i}\\
&=n+x\sum_{i=1}^{n}\frac{a_i}{1-xa_i}\\
&=n-x\sum_{i=1}^{n}\frac{-a_i}{1-xa_i}\\
\end{aligned}
$$
因为有 $\ln’(1+xy) =\frac{x}{1+xy}$ ，所以可以得到：
$$
\begin{aligned}
F(x)&=n-x\sum_{i=1}^{n}\ln’(1-xa_i)\\
F(x)&=n-x\times \ln’\left(\prod_{i=1}^{n}(1-xa_i)\right)\\
\end{aligned}
$$
分治 $\rm{NTT}$ 后求个 $\ln$ 然后求个导就好了。
0 条评论