题解：AT_agc060_d [AGC060D] Same Descent Set

定义对 $f$ 进行 SEQk 变换为令 F=sum(n≥0)f[n]/(n!)^k。

记 $A_i=[p_i<p_{i+1}]$，$B_i=[q_i<q_{i+1}]$，那么 $(p,q)$ 的贡献即为1/2^(n-1)*∏(1+(1-2A[i])(1-2B[i]))。

把 $1$ 拆出来，这些位置没有贡献，相当于将序列分成了若干连续段。因此设 $f_n$ 为所有长度为 $n$ 的排列对的和，答案即为 $f$ 进行 SEQ2 变换后的 $f_n$。

可以发现此时 $p,q$ 独立，求出所有排列 ∏(1-2A[i]) 之和再平方即为 $f_n$。求 ∏(1-2A[i]) 之和只需要令 $g_n$ 为 ∏(-2A[i]) 的和然后进行 SEQ1 变换即可。

复杂度 $O(n\log n)$。