首先注意到给定的区间之间要么不相交,要么嵌套,否则肯定不合法,而且一定有一个覆盖整个序列的区间. 据此我们可以发现区间之间嵌套的关系形成了一个树结构,树中每个点是一个极大的连续的区间. 因此我们只需求出$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 |
|