总结

美好的早晨开始拉！昨天晚上终于想明白昨天的 T3 了！然后我发现邓老师的式子和题解本质相同（废话），然后列出了等式。感觉线性基真实一个奇妙的东西。今天是组合数学！

开胃小菜

先来一道数论题 LCMSUM - LCM Sum 来自汉武帝的推荐。自豪地采用 log 的方法切掉这道题。

【模板】Polya 定理板子，做过，放在这里。

[HNOI2009] 图的同构计数经典好题，再做一遍。很巧妙的一道题。本质上是边的变换，转到点上，再考虑点的循环置换之内和外的边的循环置换，很巧妙。为了求这道题的时间复杂度，一不小心学了一下拆分数的知识：分拆数。

这个知识好有趣，很多看似不同的数却有着相似或者相关性的生成函数，数学有趣！

n 等于 17 时，卡特兰数将会超过 int 最大值。
生成函数：

经典问题例举：

进出栈序列：n 个元素进栈序列为：1，2，3，4，…，n，则有多少种出栈序列。
括号序列：n 对括号，则有多少种 “括号匹配” 的括号序列
二叉树：n + 1 个叶子节点能够构成多少种形状不同的（国际）满二叉树
二叉树：个节点可以构造出多少个不同的二叉树？
凸多边形划分为三角形：对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
序列前缀和非负：个和个构成项,其任意前缀和的序列的数量个数。
电影购票：电影票一张 50 coin，且售票厅没有 coin。m 个人各自持有 50 coin，n 个人各自持有 100 coin。则有多少种排队方式，可以让每个人都买到电影票。
几何模型：从走到，只能横着或竖着走单位距离，不能跨国对角线，有多少种走法？

[HNOI2009] 有趣的数列这种题的话，其实如果你知道是卡特兰数就会很简单。

第二类斯特林数 （斯特林子集数），也可记做，表示将个两两不同的元素，划分为个互不区分的非空子集的方案数。

边界是。

（使用二项式反演来推导）

巴拉巴拉巴拉。生成函数是 x 上升幂。

放一个别人的多项式笔记：多项式。

题目

洛谷上斯特林数唯一的黄题 [NICA #1] 乘只因很好的，显然第二类斯特林数。预处理可过。

其实还有第三类的，学不动了摆。

问了一下邓老师，要记住这个：

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊，学习组合数学到疯狂！

P.S. 其实我觉得考场上直接考斯特林数的概率也不大吧（），我觉得还不如去看看生成函数，多项式之类的。看起来太癫狂了。

白云熙熙清水平，心中有数天地宽。
人间正道无处寻，千番乃得皆浮云。