## 指数型生成函数 $\rm{EGF}$

$$F(x)=\sum_{i=0}^{\infty}\frac{x^i}{i!}$$

$$e^x=\sum_{i=0}^{\infty}\frac{x^i}{i!}$$

$$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!}$$

## 题目：$\rm{CF891E\ Lust}$

$$\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$$

$$ans=\sum_{i=1}^{k}S_{i-1}-S_i=S_0-S_k$$

$$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)=\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}^{\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}

$$ans=\sum_{i=0}^{\min(k,n)}k^{\underline{i}}n^{-i}g(i)\\$$

## 多项式多点求值

$$f(x)\equiv f(x_0)\bmod{x-x_0}$$

## 多项式对数函数

$$\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}

## 题目：付公主的背包

$$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}}$$

\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}

## 题目：「THUPC 2017」小 L 的计算题

\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}

\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}

QAQ