luogu P4566 [CTSC2018]青蕈领主

题面传送门

最后这个转化非常牛逼啊！

首先我们可以证明：一个合法的序列中，这样的极长连续区间不会相交。

Proof：如果相交了，说明相交的区间也是一段连续区间，而每个区间不相交的部分也是连续区间，所以两个区间的并也是连续区间。又因为两个区间都是极长连续区间，因此不会包含，所以与题设的”极长”矛盾。

因此现在区间只剩下相互包含和互不相交两种。把这个建成一个树的结构，可以发现一个区间的儿子覆盖了整个区间，除了最后一个位置。因此如果我们可以求出 (g_i) 表示 (i+1) 个数排列在一起，除了最后一个位置的连续区间长度为全区间，其余都为 (1) 的排列个数，方案数就是 (prod{g_{siz_i}})，其中 (siz_i) 表示 (i) 的儿子个数。

现在压力来到了 (g) 身上。直接对 (g) 计数也不好做。考虑对 (p) 的转置计数，也即 (q_{p_i}=i)。(p) 的原来的限制转化过来就是除了包含最大值的连续区间，其余连续区间长度都为 (1)。

考虑对 (2dots n+1) 序列插入 (1) 来完成 (n) 到 (n+1) 的转移。分两种情况：

• 序列原来是合法的区间，那么除了插入在 (2) 两边都可以，因此有转移 (f_{i} imes i o f_{i+1})。
• 序列原来是不合法的区间，那么原来的连续区间都要包含 (1) 的位置，且连续区间中不包含 (2) 。枚举最大的连续区间的长度，有转移 (f_{j}f_{i-j}(j-1) o f_i)。

直接暴力(O(n^2)) 的 dp 可以有 (80) 分。优化的话直接上分治 NTT 就可以做到 (O(nlog ^2n))。注意这里是自己乘自己转移到自己，和普通的分治 NTT 有所不同。

submission