[CF1707D] Partial Virtual Trees
真子集限制很不爽，考虑去掉它。
令 \(f_i\) 表示题目所求答案，\(g_i\) 表示相邻两个集合可以相同的方案。
枚举 \(g_i\) 中有哪几次相邻集合不同，有 \(g_i=\sum_{j=1}^i\binom{j}{i}f_j\)。
由二项式反演可得 \(f_i=\sum_{j=1}^i(-1)^{j-i}\binom{j}{i}g_j\)，接下来只用求 \(g_j\) 即可。
一个点能不选当且仅当它有至多一个子树当前含有点，用 \(dp_{u,i}\) 表示 \(u\) 子树内 \(i\) 时刻含有点的方案数。
枚举 \(1\) 的儿子什么时候全被删去，有 \(g_i=\prod_{v\in son(1)} \sum_{k=0}^{j-1} dp_{v,k}\)。
令 \(s_{i,j}=\sum_{k=0}^jdp_{i,k}\)，有 \(g_i=\prod_{v\in son(u)}s_{v,j-1}\)，可以 \(O(n^2)\) 解决，接下来考虑转移。
讨论 \(u\) 在 \(i\) 时刻是否还在集合。
如在集合内只需要所有子树均合法即可 \(dp_{u,i}\leftarrow \prod_{v\in son(u)}s_{v,i}\)。
否则 \(u\) 至多只有一个子树此时含有点，枚举时刻 \(t\) 表示在 \(t\rightarrow t+1\) 时由选变为不选。
有 \(dp_{u,i}\leftarrow \sum_{p=0}^{i-1}\sum_{v\in son(u)}dp_{v,i}\prod_{w\in son(u)\land v\neq w}s_{w,p}\)。
对于 \(\prod_{w\in son(u)\land v\neq w}s_{w,p}\) 的计算，做一个前后缀求积即可，总时间复杂度 \(O(n^2)\)。
LOJ575 不等关系
令 \(cnt_i\) 表示 \(i\) 及之前 \(>\) 的数量，将系数 \(n!\) 提出来，另 \(f_i\) 表示到前 \(i\) 项的合法方案数。
考虑转移，我们可以任选前面的任意一个 \(>\)，并把它后面的所有 \(>\) 都钦定为 \(<\)。
所以有 \(f_i=\sum_{j=0}^{i-1}[s_i\neq <](-1)^{cnt_{i-1}-cnt_j}\frac{f_{j}}{i-j}\)，将 \((-1)^{cnt_{i-1}}\) 提到前面后做分治 NTT。