本题解仅作为对结论“在 $q$ 确定的情况下，答案是 $q$ 的上升子序列个数”的证明的补充

首先考虑先将 $p$ 按照 $1,2,3,\cdots,n$ 的顺序排列，$p,q$ 的对应关系保持不变，也就是说让 $p_i$ 变为 $i$，$q_{p_i}$ 变为 $q_i$。

明显地，答案不会变化。

现在，可以注意到不能存在数对 $(i,j)$ 使得 $i \lt j,q_i \gt q_j,s_i=0,s_j=1$。

同时，只要不存在上述数对，那么就是有解的，这一点别的题解已经证明了。

随后考虑最大的那个数字，其如果填 $0$，那么其后面的所有数字都得填 $0$，如果其填 $1$，则不对其他位置的可填值产生影响。

填完之后，所有已经确定值的位删除，递归处理，直到删空，如此可以构造出一组合法的 $s$。

故可以得到以下结论：

每次有两种选择，要么删除最大值，要么删除最大值以及最大值右边的所有元素。

答案就是按照上述方案把 $q$ 删空的方案数。

考虑令 $q$ 由 $L,M,R$ 三部分依次组成，其中 $M$ 表示最大值位置。

令 $f(q)$ 表示把 $q$ 删空的方案数。

那么 $f(q) = f(LR)+f(L)$。

令 $g(q)$ 表示 $q$ 的上升子序列个数。

首先计算包含最大值的方案数，即 $g(L)$。

接下来就是不包含最大值的方案数，即 $g(LR)$。
故 $g(q) = g(L)+g(LR)$。

对于 $q$ 为空序列的情况，已知 $f,g$ 值均为 $1$。

由于递推形式一致，可以得出 $f(q)=g(q)$