首先注意到给定的区间之间要么不相交，要么嵌套，否则肯定不合法，而且一定有一个覆盖整个序列的区间. 据此我们可以发现区间之间嵌套的关系形成了一个树结构，树中每个点是一个极大的连续的区间. 因此我们只需求出$f _i$表示长为$i+1$的，不存在任何不包含最后一位的连续区间的，排列的个数.
假设$a$是$1,2,\ldots,n$的一个排列，令$p _i$表示$i$在$a$中的位置，易知$a$中一个连续的区间对应着$p$中一个连续的区间，因此$a$满足上一段所述条件等价于$p$中不存在一个不包含最大值的连续区间.
考虑跟排列有关的递推我只知道有两种思路，把$n+1$插入或者在序列某位放一个$i$，并把前面所有$\ge i$的数$+1$. 我一开始想的是后一种思路，结果没想出来. 考虑前一种思路，因为$p$中不存在一个不包含最大值的连续区间，为方便起见插入$1$而不是插入$n+1$，接下来要讨论两种情况. 为方便起见，下面先假设$n\ge 2$.
如果插入前的序列是合法的，那么插入前的序列有$f _{n-1}$种可能，而插入的位置可以是除了插入前最小值旁边的任何位置，共$n-1$种，因此这种情况的贡献为$(n-1)f _{n-1}$.
如果插入前序列不合法，那么$1$一定是放在了一个连续区间中间，设它所在的极长连续区间长度为$i$，那么这段区间插入$1$后不连续等价于它插入$1$，离散化后不存在不包含最小值的连续区间，等价于不存在不包含最d大值的连续区间，所以这个连续区间插入$1$之后共有$f _i$种可能. 把这段区间缩成一个数，然后把得到的序列离散化，剩下的序列长度为$n-i+1$，它也不能有不包含最小值的连续区间，共$f _{n-i}$种可能. 注意到插入$1$的那个连续区间在离散化之后的权值不能为最小值也不能为最大值，因而有$n-i-1$种可能. 综上，这一部分的贡献为
于是我们可以列出递推式
把下标范围弄得对称一些，并加入一些修改使其对$\forall n\in \mathbb N$都成立
这个东西就可以用分治来计算了.
这个卷积是自己卷自己，但也是可以分治的. 对于每个$(j-1)f _jf _k$，我们在$j,k$中较大一项被计算出来的时候，统计它的贡献. 把分治的长度补全为$2$的幂，假设当前的分治区间是$[l,r)$，$m=\left\lfloor\frac{l+r}{2}\right\rfloor$，统计$[l,m)$中的$f$的贡献，分两种情况讨论：
- $l\neq 0$. 对于$[l,m)$中的每个$i$，要取一个$j$使得它们对$[m,r)$有贡献，显然$j\in[0,r-l)$，而此时必有$r-l\le l$，直接把$[l,m)$中的元素和$[0,r-l)$中的元素卷起来统计贡献就可以了.
- $l=0$. 直接$[l,m)$中的元素卷上$[l,m)$中的元素.
第一种情况实现精细的话可以用5次而不是6次ntt，说不定还可以更少.
这种题卷积的下标范围一定要想办法弄对称，这样细节处理上会方便很多.
代码：
1 |
|