自动搬运

查看原文

来自洛谷，原作者为

	Seauy I remember your song, sung by centuries of wind.

搬运于2025-08-24 22:51:56，当前版本为作者最后更新于2023-12-03 02:55:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目链接

若一个排列中的连续子段值域为一段连续整数，则把这个子段简称为“段”。设排列为 $\{A_n\}$，则段 $[L,R]$ 满足 $\max_{i=L}^R A_i-\min_{i=L}^R A_i =R-L$。题目要我们求不包含长度 $2\sim n-1$ 的段的排列个数。

首先我们需要掌握段的性质和结构。易证对于两个段 $[a,b],[c,d]$，若 $[a,b]\cap [c,d]\neq \varnothing$，则 $[a,b]\cup [c,d]$ 也是一个段；对于描述所有段的结构，析合树是目前最为高效的工具。

$1\sim n$ 的排列拥有的段的个数数量级为 $O(n^2)$，但我们可以只研究其中与其他段只存在包含或互斥关系的段，也就是挑出来的段之间要么一个为另一个的子集，要么没有交集，这些段被称为本源段。接着把本源段都抽象为结点，对于每个本源段，找到最短的包含他的另一个本源段（对于 $[1,n]$ 不存在这样的段），然后连一条边。容易发现最后得到的图为一棵大小 $O(n)$ 的树，因为结点数不超过 $2n-1$、结点数比边数多 $1$、图是联通的。如果我们把 $[1,n]$ 当作根，又会发现叶节点总是长度为 $1$ 的段且有 $n$ 个。我们再定义儿子的顺序，从左到右按段的下标从小到大排列。这棵树就是析合树。

将析合树上的若干结点取并集便能组合出所有段。具体来说，由于一个结点的所有儿子都是互斥的，那么一个儿子的所有元素（对应段中的值）要么大于另一个儿子的所有元素，要么反过来，所以我们一定能按元素大小给儿子比大小。若儿子按升序或降序排列，称此结点为合点，否则称为析点（OIwiki 给的定义认为叶子也是合点，我觉得可以认为叶子既不是合点也不是析点）。对于如何组合所有段，设某个结点的儿子序列为 $s_1,s_2,\dots ,s_m$，若他为合点则 $\forall 1\leq L\leq R\leq m,\ \bigcup_{i=L}^R s_i$ 为一个段，若他为析点则儿子无法拼出段（除非 $L=R$ 或 $[L,R]=[1,m]$）。发现这样便能一一构造出所有段，考虑非本源段，假设他无法被拼出，要么不存在能拼出他的一组本源段，要么只能由不同结点的儿子拼出；由于所有区间都能被拼出，所以前者不存在，后者相当于在说存在两个本源段有交集，显然是矛盾的。这样便反证出了只要取儿子序列的连续子段，析合树就能一一对应地描述出所有段（除非 $n=1$）。

回到原题，非间隔排列本质就是析合树只有两层且根为析点的排列（排除 $n=1,2$）。设 $f_n$ 为长度为 $1\sim n$ 的非间隔排列个数，那么我们反过来计算间隔排列个数，可以从两方面否定非间隔排列：

1. 根结点为析点但是儿子不都是叶子，我们枚举儿子个数 $4\leq i \leq n-1$（$i \geq 4$ 是析点儿子个数的性质，但要排除 $n=3$），儿子序列的大小关系有 $f_i$ 种，还要考虑元素的分配与位置关系。

2. 根节点为合点，儿子至少有两个。

情况一涉及将 $1 \sim i$ 分为 $j$ 组，组间不考虑顺序但是组内考虑。设 $g_{i,j}$ 为 $1 \sim i$ 分 $j$ 组的方案数，有递推：

$$g_{i,j}=\sum_{k=1}^{i-j+1} g_{i-k,j-1}k!$$

情况二涉及合点计数，先只考虑递增的情况，最后结果乘以 $2$。可以枚举最后一个儿子的长度 $i$，则合法等价于最后一个儿子的所有真前缀中没有包含其最小元素 $n-i+1$ 的段，前面可以随意排，对于充分性，若有这样的段，那么不符合本源段的定义；对于必要性，关于儿子个数的限制显然，若想取最后一个儿子的真前缀拼上前面的非空后缀组成段来推翻析合树性质，必定要取包含 $n-i+1$ 的段，但这样的真前缀不存在。设 $h_i$ 为 $1 \sim i$ 排列中不存在真前缀包含元素 $1$ 的个数，则有递推：

$$h_i=i!-\sum_{j=1}^{i-1} j!h_{i-j}$$

这里反过来计算存在这样的真前缀的情况数，其中 $[1,j]$ 为最长的那个。

最后答案为

$$f_n=n!-\sum_{i=4}^{n-1} f_ig_{n,i}-2\sum_{i=1}^{n-1} (n-i)!h_i $$

两个求和分别为两种情况的贡献，记得特判 $n=1,2,3$，时间 $O(n^3)$，空间 $O(n^2)$。下面是代码供对拍：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN=400;

int T,p;
int f[MAXN+5],fac[MAXN+5];
int g[MAXN+5][MAXN+5],h[MAXN+5];

int main()
{
	scanf("%d %d",&T,&p);
	f[1]=1,f[2]=2,f[3]=0;
	fac[0]=fac[1]=1;for(int i=2;i<=MAXN;i++) fac[i]=1ll*fac[i-1]*i%p;
	g[1][1]=1;
	for(int i=2;i<=MAXN;i++)
	{
		g[i][1]=fac[i];
		for(int j=2;j<=i;j++)
			for(int k=1;k<=i-j+1;k++)
			{//i-k>=j-1
				g[i][j]+=1ll*g[i-k][j-1]*fac[k]%p;
				if(g[i][j]>=p) g[i][j]-=p;
			}
	}
	h[1]=1;
	for(int i=2;i<=MAXN;i++)
	{
		for(int j=1;j<i;j++)
		{
			h[i]+=1ll*h[j]*fac[i-j]%p;
			if(h[i]>=p) h[i]-=p;
		}
		h[i]=fac[i]-h[i];
		if(h[i]<0) h[i]+=p;
	}
	for(int i=4;i<=MAXN;i++)
	{
		for(int j=4;j<i;j++)
		{
			f[i]+=1ll*f[j]*g[i][j]%p;
			if(f[i]>=p) f[i]-=p;
		}
		for(int j=1;j<i;j++)
		{
			f[i]+=2ll*h[j]*fac[i-j]%p;
			if(f[i]>=p) f[i]-=p;
		}
		f[i]=fac[i]-f[i];
		if(f[i]<0) f[i]+=p;
	}
	for(int n;T--;) scanf("%d",&n),printf("%d\n",f[n]);
	return 0;
}