2020.06.08-2020.06.14 周报
团队训练
2020.06.14 2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest prob:6:6:10 rnk:124/?
_wzx27
1.指数生成函数
常用于解决一类多重集合计数的问题
设 $S$ 是多重集合$\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$，其中 $n_1,n_2,\cdots,n_k$ 是非负整数。设 $h_n$ 是 $S$ 的 $n$ 排列数。那么数列 $h_0,h_1,\cdots,h_n,\cdots$ 的指数生成函数 $g^{(e)}(x)$ 由下式给出： $$g^{(e)}(x)=f_{u_1}(x)f_{u_2}(x)\cdots f_{u_k}(x)$$ 其中，对于 $i=1,2,\cdots,k$，有 $$f_{u_i}(x)=1+x+\frac {x^2}{2!}+\cdots + \frac {x^{n_i}}{n_i!}$$
又因为 $e^x=1+x+\frac {x^2}{2!}+\cdots$，所以这类因子相乘有很好的性质，便于求解最后的生成函数。
用红、蓝、绿、黄四种颜色给 $1\times n$ 的方块染色，红色和绿色方块的数目必须是偶数。
那么蓝黄的因子为： $1+x+\frac {x^2}{2!}+\cdots + \frac {x^{n}}{n!}+\cdots=e^x$ 红绿的因子为： $1+\frac {x^2}{2!} + \frac{x^4}{4!} \cdots=\frac {e^x+e^{-x}}2$ 所以生成函数为： $g^{(e)}(x)=e^{2x}(\frac {e^x+e^{-x}}2)^2=\frac {e^{4x}+2e^{2x}+2}4$ 从而展开后 $n\gt 1$ 时 $\frac{x^n}{n!}$ 的系数为 $\frac {4^n+2^{n+1}}4$
$c$ 种无限集合，任意选取 $n$个，相同类型的元素出现两个时就会一起消失，问最后剩下 $m$ 个的概率是多少。
范围:$c\le 100,n,m\le 1e6$
可以概率dp，但好像很麻烦？
考虑生成函数的做法，就是有 $m$ 个集合取了奇数次，另外 $c-m$ 个集合取了偶数次。
$$ \begin{aligned} g^{(e)}(x)=&(\frac {e^x-e^{-x}}2)^m\cdot (\frac{e^x+e^{-x}}2)^{c-m}\\ =&2^{-c}\sum_{i=0}^{m}(-1)^{m-i}{m \choose i}e^{ix}e^{-(m-i)x}\cdot \sum_{j=0}^{c-m}{c-m \choose j}e^{jx}e^{-(c-m-j)x} \end{aligned} $$
然后暴力 $O(c^2logn)$ 就可以求每一对 $(i,j)$ 对 $\frac {x^n}{n!}$ 的系数的贡献 $(-1)^{m-i}{m \choose i}{c-m \choose j}(2i+2j-c)^n$。
2.生成函数与多项式
生成函数没那么好求的时候就要用多项式全家桶
$n$ 种无限个物品，每个物品体积为 $v_i$，求恰好装下体积为 $1~m$ 的种数。
数据范围：$n,m \le 1e5$
这种题也算是生成函数的经典应用
首先得到生成函数：$f(x)=\prod _{i=1}^n \frac 1{1-x^{v_i}}$
两边取对数得 $$ \begin{aligned} lnf(x) =&\sum_{i=1}^n\sum_{j=0}^\infty \frac {x^{j\cdot v_i}}j \\ =&\sum_{k=0}^m \sum _{v_i|k} \frac {v_i}k x^k \pmod{x^{m+1}} \end{aligned} $$
$O(nlogn)$预处理出 $k$ 的所有因子，然后多项式 $\text{Exp} $求 $e^{lnf(x)}$ 即可。
