$\text{Problem 1. XXII Open Cup J - Joke}$
$\big ( \text{Joke}\big ) \text{ - Solution by } \mathbb{FAS} \text{weets}$
注意到 $p,q$ 只依赖于 $(p_i,q_i)$ 的大小关系，不妨把 $p_i$ 调整为 $1\sim n$.
$\text{Lemma}:$
$f((1,2,\cdots n),q)=\big(~q$ 的递增子序列个数 $\big )$。
$\text{Proof}:$
先钦定 $s$，这个 $s$ 合法判定可以将固定的大小关系小的向大的连边，使得不存在环。容易发现如果存在环，则必然存在四元环。接下来每次考虑 $q$ 最大的那个位置：
- 如果这个位置的 $s=0$，那么这个点没有出度，因此不可能在这个点上出现四元环，可以直接忽略。
- 如果这个位置的 $s=1$，那么这个位置右边的所有位置的 $s$ 都必须为 $1$。
因此可以考虑抽象为如下过程：每次删除序列的最大值，或删除最大值及其右边的所有值，问有多少种选法。容易发现这个方案数等价于 $q$ 的上升子序列个数。
所以，填 $p_i>q_i$ 的位置构成递增子序列，于是现在问题转换为求递增子序列的个数。
我们记 $f_{i,j}$ 表示到第 $i$ 个位置，递增子序列最后一个在 $q$ 中非 $0$ 的位置为 $j$ 的方案数。
$O(n^4)$。
$\text{Problem 2. Singer House}$
$\big ( \text{Singer-House}\big ) \text{ - Solution by } \mathbb{FAS} \text{weets}$
$f_{i,j}$ 表示深度为 $i$ 的子树内有 $j$ 条路径的方案数，因为每一个点只能将两条路径合并为一条。
