[NERC2018] Interval-Free Permutations 的题解
Seauy
·
·
题解
题目链接
若一个排列中的连续子段值域为一段连续整数，则把这个子段简称为“段”。设排列为 \{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] 也是一个段；对于描述所有段的结构，析合树是目前最为高效的工具。
将析合树上的若干结点取并集便能组合出所有段。具体来说，由于一个结点的所有儿子都是互斥的，那么一个儿子的所有元素（对应段中的值）要么大于另一个儿子的所有元素，要么反过来，所以我们一定能按元素大小给儿子比大小。若儿子按升序或降序排列，称此结点为**合点**，否则称为**析点**（[OIwiki](https://oiwiki.org/ds/divide-combine/) 给的定义认为叶子也是合点，我觉得可以认为叶子既不是合点也不是析点）。对于如何组合所有段，设某个结点的儿子序列为 $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)$。下面是代码供对拍：
```cpp
#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;
}
```