题目梗概

定义一个序列是连续的,当且仅当这个序列的最大值-最小值不超过序列长度-1.

现在有一个长度为\(n\)的排列,给出以每个位置为右端点的最长连续区间的长度,求满足的排列的方案数.

解题思路

如果\(a[n]!=n\)且有区间相交显然无解.

那么我们可以根据区间的包含关系建出一棵以\(n\)为根的树,用\(s[i]\)表示节点\(i\)的儿子个数.

因为连续的区间可以看成一个点,所以每个节点的贡献可以分别考虑.

定义\(f[i]\)为长度有多少\(n+1\)的连续序列,满足在删去最大值后不存在长度大于\(1\)的连续序列

那么最后答案显然是\(\prod f[s[i]]\).

考虑\(f[i]\)的转移.

如果从合法方案转来,只要最后一个数不等于\(i\)即可,方案数为\((i-1)f[i-1]\)

如果从不合法方案转来,那么不满足的区间只有有一个,长度设为\(l\),把最大值插入形成合法区间的方案数为\(f[l]\),把插入后的区间看成一个点,与剩下的点的方案数为\(f[i-l]\),若要保证有解,那么这个区间的范围一定在\([2,i-l]\),所以得到:

\[ f[i]=(i-1)f[i-1]+\sum_{l=2}^{i-2}(i-l-1)f[i]f[i-l] \]

\(f\)用分治FFT预处理即可.

#include
    
     #include
     
      #define LL long longusing namespace std;const int tt=998244353,g=3;;const int maxn=1400005;char nc(){    static char buf[100000],*l=buf,*r=buf;    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);    if (l==r) return EOF;return *l++;}inline int _read(){    int num=0;char ch=nc();    while(ch<'0'||ch>'9') ch=nc();    while(ch>='0'&&ch<='9') num=num*10+ch-48,ch=nc();    return num;}int n,T,f[maxn],A[maxn],B[maxn],re[maxn],a[maxn],top,que[maxn],s[maxn],ans,pd;int qsm(LL w,int b){int num=1;while(b){if (b&1) num=(LL)num*w%tt;w=(LL)w*w%tt;b>>=1;}return num;}void NTT(int a[],int f,int n){    for (int i=0;i
      
       >1);work(l,mid);    int m,len=0;for (m=1;m<=(r-l+1)*2;m<<=1) len++;    for (int i=0;i
       
        >1]>>1)|(i&1)<<(len-1));    for (int i=0;i
        
         =1;i--){        while(i