证明我存在过

不会数学,若有错误请指出 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$ 然后求个导就好了。

分类: 文章

Qiuly

QAQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注