不妨钦定 $\boldsymbol{i \in S}$ 里的 $\boldsymbol{p_i, p_{i+1}}$ 一定存在连边，计算其方案数为 $g_S$。最终统计答案时容斥部分做高维后缀和即可，$\mathcal O(2^n n)$。问题变为计算所有 $g_S$。

显然 $g_S$ 只和 $S$ 内 $1$ 连续段长度组成的不可重集合有关，而其总数可以由构造双射得到恰好为 $\pi(n)$。本质上，对于所有可能的 $\sum a_i = n$，需要求选择集合 $S_1, S_2, \ldots, S_m$ 满足 $S_1 \cup S_2 \cup \dots \cup S_m = [n]$，$\forall 1 \leq i \neq j \neq m, S_i \cap S_j = \varnothing$，且 $\lvert S_i\rvert = a_i$ 的所有 $f(S_i)$ 积的和。

其中 $f(S)$ 是 $S$ 集合内的点选出一条链的方案数，容易 $\mathcal O(2^n\cdot n^2)$ 预处理之。

对于一组给定的 $a_1, \ldots, a_m$，仿照子集卷积的过程，预先对所有 $b_{j,i} = [\operatorname{popcount}(i) = j]f(i)$ 做 FWT，点值相乘，然后 IFWT 回去。但是事实上只需要求 IFWT 后 $\bm{2^n - 1}$ 处的点值，于是可以 $\mathcal O(2^n)$ 求。

精细实现即可 $\mathcal O(2^n \cdot (\pi(n) + n^2))$。