今天我刚知道一个很逆天的事：\(DAG\) 的拓扑序方案数不可做！！!，目前能做到的最优方法好像是状压
我们考虑这题怎么做，对于一个限制，我们关心的是他俩在拓扑序中的相对排名，而这题恰好是一个树形结构，因此我们考虑树形 \(dp\)
我们设 \(dp_{i,j}\) 表示以 \(i\) 为根的子树， \(i\) 在拓扑序中的排名为 \(j\) 的方案数
我们现在对于已经合并过的以 \(u\) 为根的子树，我们考虑把一个没有合并上去的以 \(v\) 为根的子树合并上去。显然有两种情况
-
先算 \(u\) 后算 \(v\)
此时我们考虑合并前 \(u\) 的排名为 \(p_1\) ， \(v\) 的排名为 \(p_2\) ，合并后 \(u\) 的排名为 \(p_3\) ，我们可以发现关系： \(p_1-1 \leq p_3 - 1 \leq p_1 - 1 + p_2 - 1\) ，因为 \(u\) 必须在 \(v\) 的前面。化简后变为： \(p_1 \leq p_3 \leq p_1 + p_2 - 1\)
我们可以列出 \(dp\) 式子： \(dp'_{u,p_3} += dp_{u,p_1} \times dp_{v,p_2} \times \binom{p_3-1}{p_1-1} \times \binom{siz_u + siz_v - p_3}{siz_u - p_1}\)
其中 \(\binom{p_3-1}{p_1-1}\) 表示前 \(p_3 - 1\) 中一定有 \(p_1 - 1\) 在里面； \(\binom{siz_u + siz_v - p_3}{siz_u - p_1}\) 则表示在 \(u\) 点后面的部分中 \(siz_u - p_1\) 一定在里面 -
先算 \(v\) 后算 \(u\)
同 \(1.\) 的计算方式，直接给出结论： \(p_1 + p_2 \leq p_3 \leq siz_u + siz_v\)
\(dp\) 的递推式为： \(dp'_{u,p_3} += dp_{u,p_1} \times dp_{v,p_2} \times \binom{p_3-1}{p_1-1} \times \binom{siz_u + siz_v - p_3}{siz_u - p_1}\)
我们暴力 \(dp\) 的复杂度是 \(O(n^3)\)
我们考虑优化，我们发现我们的 \(dp\) 式子中 \(dp_{v,p_2}\) 好像重复出现了很多次，因此我们可以前缀和优化
最终复杂度 \(O(n^2)\)
\(p.s.\) 听说 \(NTT\) 可以优化到 \(O(n^2 \log n)\) ，神奇