[数据结构与算法] 【XSY4320】Catalan（组合意义，DP，多项式）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【XSY4320】Catalan（组合意义，DP，多项式） -> 正文阅读

[数据结构与算法]【XSY4320】Catalan（组合意义，DP，多项式）

题面：

Catalan

题解：

假瑞的做法orz

考虑用组合意义来做，观察递推式 $f_i=\frac{1}{i}\sum_{j=0}^{i-1}f_jf_{i-j-1}$ ，它除了和卡特兰数递推式很像之外，还和二叉树计数的递推式很像。

同时注意到 $f_0=0$ ，所以递推式可以变为 $f_i=\frac{1}{i}\sum_{j=1}^{i-2}f_jf_{i-j-1}$ ，即我们二叉树中每个非叶子节点都有恰好两个儿子，那么也可知 $n$ 一定为奇数。下面 “完全二叉树” 的意义为每个非叶子节点都有恰好两个儿子的二叉树。

那么 $f_n$ 就可以理解为枚举每一种完全二叉树，然后把 $\prod_{u}\frac{1}{sz_u}$ 的贡献统计进答案。

注意这里枚举的二叉树是无标号但是有左右儿子之分的，那么我们不妨将这棵二叉树上的点按 dfn 序标号。

发现 $\prod_u\frac{1}{sz_u}$ 就是这棵二叉树的拓扑序数量除以 $n!$ ，那么现在的问题转变为：枚举每一种二叉树，然后把其拓扑序个数统计进答案。

考虑每个点 $i$ （注意这里是按 dfn 序标号，上面已经说过了）在拓扑序中的位置 $pos_i$ ，发现对于每一种 $1\sim n$ 的排列，如果把它当做 $p o s$ 序列的话，其唯一对应着一棵普通二叉树，即为这个排列的笛卡尔树。

但是还没完，这个 $p o s$ 序列对应的不一定是一棵完全二叉树，我们只要那些完全二叉树的方案。

发现一棵树是完全二叉树当且仅当 dfn 序为奇数的点都是叶子，那么一个序列 $p o s$ 是来自完全二叉树的当且仅当：
$\forall i\bmod 2=1, pos_i>pos_{i-1}\land pos_i>pos_{i+1}$
完整写下来： $pos_1>pos_2<pos_3>pos_4<\cdots >pos_{n-1}<pos_n$ 。我们只需要求出满足该条件的排列个数即可。

考虑让所有大于号都满足，然后容斥哪些小于号不满足，那么就得到了若干段连续的大于号，即：
$n!\sum_{s_1+\cdots+s_m=n}\left(\prod_{i=1}^{m-1}\frac{(-1)^{s_i/2-1}}{s_i!}\right)\left(\frac{(-1)^{(s_m-1)/2}}{s_m!}\right)$
其中要求 $s_1,\cdots,s_{m-1}$ 为正偶数， $s_m$ 为正奇数。

设 $F(x)=\sum_{i\geq 1,2|i}\frac{(-1)^{i/2-1}}{i!}x^i$ ， $G(x)=\sum_{i\geq 1,2\not|i}\frac{(-1)^{(i-1)/2}}{i!}x^i$ ，那么我们要求的就是：
$[x^n]\frac{G(x)}{1-F(x)}$
时间复杂度 $O(n\log n)$ 。