题解：AT_agc060_d [AGC060D] Same Descent Set

Cadmus · 2026-01-17 10:34:09 · 题解

定义对 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)。