今日见到一个有趣的问题,就是本篇的题目。
这里可以把它看作一个dp问题,\(f_i\)表示以\(i\)为根节点的子树的拓扑排序数量,要求出\(f_i\),就要知道\(f_j\) (\(j\in Son_i\)),但是它不是处理完一个子树,再处理另一个子树,它是穿插着来的,所以这个问题就变成了,已知\(k\)个序列,问有多少序列满足这\(k\)个序列中任意序列在新序列中顺序不变。
这里可以先看一个新问题,有\(n\)种数,第\(i\)种数有\(a_i\)个,问所有数能组成多少种序列?
这个问题的答案就是$\frac{(\sum_{i=1}^{n} a_i)!}{\prod_{i=1}^{n} (a_i!)} $。
这里可以发现这个问题和我们想求的问题其实是一样的,所以这里可以得出式子 \(f_i=\frac{(\sum_{j\in Son_i} sum_j-1)!}{\prod_{j\in Son_i} (sum_j!)} \times \prod_{j\in Son_i} f_j\)。