BZOJ3684 大朋友和多叉树

题目链接

题解

这题做的我心累
一开始怎么想都不知道这个怎么用生成函数搞
后来去看题解。。。好吧是我太菜了
设 $F(x)$ 为方案数的 $OGF$
于是有转移
$$ F(x)=x + \sum_{i\in D} F^i(x)$$
解释一下,前面的 $x$ 是指叶子节点,也就是权值为 $1$ 时的方案数(显然只有一种),后面代表枚举儿子个数,用乘法原理将每个儿子的选择方案合起来,然后用加法原理把不同儿子数之间的方案合起来
继续阅读

BZOJ3456 城市规划

题意

给出 $n$ ,请求出点数为 $n$ 的简单无向联通图个数

题解

对于一类组合对象,定义 $A$ 为初始元素集合的 $EGF$
然后定义函数 $SET(A)=\sum_{i\geq 0} \cfrac{A^i}{i!}$ 表示有这些元素有序拼接组成的组合对象的生成函数
对于 $e^x$ 做皮亚诺余项泰勒展开
$$ e^x=\sum_{n\geq 0}\cfrac{x^n}{n!} $$
继续阅读