P4091 [HEOI2016/TJOI2016]求和
有一个重要的通项公式
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^{m}\frac{i^n(-1)^{m-i}}{i!(m-i)!} \]\[ans =\sum_{i=0}^{n}\sum_{j=0}^{n}{\begin{Bmatrix}i\\j\end{Bmatrix}}2^{j}(j!) \]\[=\sum_{j=0}^{n}2^{j}(j!)\sum_{i=0}^{n}{\begin{Bmatrix}i\\j\end{Bmatrix}} \]\[=\sum_{j=0}^{n}2^{j}(j!)\sum_{i=0}^{n}\sum_{k=0}^{j}\frac{(-1)^{j-k}k^i}{k!(j-k)!} \]\[=\sum_{j=0}^{n}2^{j}(j!)\sum_{k=0}^{j}\frac{(-1)^{j-k}\sum_{i=0}^{n}k^{i}}{k!(j-k)!} \]令 \(f(x)=\frac{(-1)^x}{x!}\)，\(g(x)=\frac{\sum_{i=0}^{n}x^i}{x!}=\frac{1-x^{n+1}}{x!(1-x)}\)。
于是答案为
\[\sum_{i=0}^{n}2^{i}(i!)(f\times g)(i) \]CF960G Bandit Blues
设 \(f(i,j)\) 表示 \(i\) 个数中有 \(j\) 个数作为前缀最大值的方案数。
\[f(i,j)=f(i-1,j)+f(i-1,j-1)\times (i-1) \]这是第一类斯特林数。
枚举最大值的位置，答案为
\[\sum_{i=1}^{n}f(i,a-1)\times f(n-i-1,b-1)\times\binom{n-1}{i} \]于是求一下第一类斯特林数——列即可。
求两个第一类斯特林数——列会被卡常，于是优化一下式子
\[ans=f(n-1,a+b-2)\binom{a+b-2}{a-1} \]P4389 付公主的背包
考虑将每一种物品写成生成函数的封闭形式
\[ans=\prod_{i=1}^n\frac{1}{1-x^{V_i}} \]直接相乘不好做，考虑求 ln，再 exp。
\[\ln(\frac{1}{1-x^{V_i}})=\sum_{j=1}^{\infty}\frac{x^{V_ij}}{j} \]于是记录一下每种 \(V\) 出现的次数即可 \(O(n\log n)\) 解决。
P5824 十二重计数法
\(\text{I}\)
\[m^n \]\(\text{II}\)
\[m^{\underline{n}} \]\(\text{III}\)
指数型生成函数。
\[F(x)=\sum_{i=1}^{n}\frac{1}{i!} \]答案为 \([x^n](F(x))^mn!\)。
\(\text{IV}\)
\[\sum_{i=0}^{m}{n\brace i} \]\(\text{V}\)
\[[n\leq m] \]\(\text{VI}\)
\[{n\brace m} \]\(\text{VII}\)
普通生成函数。
\[F(x)=\sum_{i=0}^{n}x^i \]答案为 \([x^n](F(x))^m\)。
\(\text{VIII}\)
普通生成函数。
\[F(x)=1+x \]答案为 \([x^n](F(x))^m\)。
\(\text{IX}\)
普通生成函数。
\[F(x)=\sum_{i=1}^{n}x^i \]答案为 \([x^n](F(x))^m\)。
\(\text{X}\)
设 \(f(i,j)\) 表示前 \(i\) 个盒子放 \(j\) 个球的方案数。
\[f(i,j)=f(i-1,j)+f(i,j-i) \]理解：如果有空盒子，去掉这个空盒子；如果无空盒子，从所有盒子中拿出一个球。
于是构造生成函数
\[F_i(x)=\sum_{k=0}^{\infty}x^{ki} \]答案为
\[[x^n](\prod_{i=1}^{m}F_i(x)) \]\(\text{XI}\)
\[[n\leq m] \]\(\text{XII}\)
\(n\) 减去 \(m\) 后同 \(\text{X}\)。
CF438E The Child and Binary Tree
设 \(g(i)\) 表示是否含有权值为 \(i\) 的点，\(f(i)\) 表示权值和为 \(i\) 的树的数量。
\(f(0)=1\)，\(g(0)=0\)。
\[f(n)=\sum_{i=0}^{n}g(i)\sum_{j=0}^{n-i}f(j)f(n-i-j) \]乘上 \(x^n\) 得
\[f(n)x^n=\sum_{i=0}^{n}g(i)x^i\sum_{j=0}^{n-i}f(j)x^jf(n-i-j)x^{n-i-j} \]于是
\[F(x)=G(x)F^2(x)+1 \]因此
\[F(x)=\frac{1-\sqrt{1-4G(x)}}{2G(x)} \]\([x^0]G(x)=0\)，无法求逆，分子分母同时乘 \(1+\sqrt{1-4G(x)}\) 得
\[\frac{2}{1+\sqrt{1-4G(x)}} \]P4233 射命丸文的笔记
答案为总的哈密顿回路数除以含有哈密顿回路的竞赛图的数量。
分子
答案为
\[(n-1)!2^{\frac{n(n-1)}{2}-n} \]分母
有这样一个性质，将竞赛图缩点后回形成一个链状的 DAG。
设 \(\mathcal{A}\) 为有标号强连通竞赛图（缩点后只有一个点）的组合类，组合对象 \(\mathcal{A_n}\) 表示有 \(n\) 个点。
设 \(\mathcal{B}\) 为有标号竞赛的组合类，组合对象 \(\mathcal{B_n}\) 表示有 \(n\) 个点。
\[\mathcal{B}=SEQ(\mathcal{A})\rightarrow \widehat{B}(x)=\frac{1}{1-\widehat{A}(x)} \]反解出
\[\widehat{A}(x)=1-\frac{1}{\widehat{B}(x)} \]P4727 [HNOI2009]图的同构计数
https://zhuanlan.zhihu.com/p/347566986
烷基计数 加强版 加强版
设 \(A(x)\) 为烷基数目的生成函数，使用 burnside 来计数。
本题中不动点的含义为交换子树后树的形态不变。
- \(1,2,3\)：\(A(x)^3\)。
- \(2,1,3\) 或 \(3,2,1\) 或 \(1,3,2\)：\(3A(x)A(x^2)\)。
- \(2,3,1\) 或 \(3,1,2\)：\(2A(x^3)\)。
于是
\[A(x)=\frac{A(x)^{3}+3A(x)A(x^2)+2A(x^3)}{6}x+1 \]使用牛顿迭代，将 \(A(x)\) 看成自变量即可。
标签：frac,答案,省选,text,08,计数,Bmatrix,mathcal,sum From： https://www.cnblogs.com/yanchengzhi/p/17002014.html