析合树形态计数 dp

  正儿八经的用析合树本身的题没见着，析合树形态计数倒是一大堆。。。

  名词注释：
  子段：一个排列中的连续子序列
  非平凡子段：长度大于 $1$、且不为排列本身的子段
  连续段：若把一个子段的元素重排后是连续的，那么这个子段是一个连续段，比如 $[3,5,4,7,6]$

V1

题源：【2018-2019 ICPC, NEERC, Northern Eurasia Finals】I. Interval-Free Permutations

题目大意

  给定 $n$，求有多少长度为 $n$ 的排列，满足该排列任意一个非平凡子段都不是连续段。

  $n \leq 400$
  多测，$T \leq 50000$，同一个数据点的所有 test case 模数相同，模数 $\in [10^8,10^9]$
  1.5s

题解

  学习了析合树之后，就知道这等价于问有多少析合树，根节点为析点，它有 $n$ 个儿子，且全是叶子。（$n \leq 3$ 特判）

  设 $X_i$ 表示根节点是析点、有 $i$ 个叶子儿子的方案数。也就是答案。
  基本思路是 $X_i=i!-(根是合点)-(根是析点但儿子数量 \in [4,i-1])$。

  第一种情况，根是合点：先假设这是个单调上升的合点。枚举它的第一个儿子的大小 $j$，后面的儿子就任意了。由于这是第一个儿子，因此这个儿子任意一个严格前缀不能是 $1$ 开头的连续段。
  因此算一个 $H_i$ 表示“长度为 $i$、任意一个严格前缀都不是以 $1$ 开头的连续段”的排列的数量。容斥一下即可得 $H_i=i!-\sum_{j=1}^{i-1}H_j \cdot (i-j)!$。
  最后，根单调下降的方案数等于单调上升的方案数，所以根是合点且有 $i$ 个儿子的方案数就是 $2\sum_{j=1}^{i-1} H_j \cdot (i-j)!$。

  第二种情况，根是析点但儿子数量 $\in [4,i-1]$：假设有 $j$ 个儿子，由于它们的任意非平凡组合都不能是连续段，所以这 $j$ 个儿子的排列顺序有 $X_j$ 种。
  再设 $B_{i,j}$ 表示把 $i$ 个数划分为 $j$ 个排列的方案数，即 $B_{i,j}=\sum_{k=1}^i B_{i-k,j-1} \cdot k!$。
  那么这种情况的方案数就是 $\sum_{j=4}^{i-1} B_{i,j}\cdot X_j$。

  综上，$X_i=i!-\big(2\sum_{j=1}^{i-1} H_j \cdot (i-j)!\big)-\big(\sum_{j=4}^{i-1} B_{i,j}\cdot X_j\big)$，时间复杂度 $O(n^3)$。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=405;

int n;
LL mo;

LL fac[maxn];
void Pre(int n)
{
    fac[0]=1;
    fo(i,1,n) fac[i]=fac[i-1]*i%mo;
}

LL X[maxn],H[maxn],B[maxn][maxn];
void dp(int n)
{
    fo(i,1,n)
    {
        H[i]=fac[i];
        fo(j,1,i-1) H[i]=(H[i]-H[j]*fac[i-j]%mo+mo)%mo;
    }
    B[0][0]=1;
    fo(i,1,n)
        fo(j,1,i)
            fo(k,1,i) (B[i][j]+=B[i-k][j-1]*fac[k])%=mo;
    fo(i,1,n)
    {
        X[i]=fac[i];
        fo(j,1,i-1) X[i]=(X[i]-2*H[j]*fac[i-j]%mo+mo)%mo;
        fo(j,4,i-1) X[i]=(X[i]-X[j]*B[i][j]%mo+mo)%mo;
    }
}

int T;
int main()
{
    scanf("%d %lld",&T,&mo);

    Pre(400);
    dp(400);

    while (T--)
    {
        scanf("%d",&n);
        if (n==1) puts("1");
            else if (n==2) puts("2");
            else if (n==3) puts("0");
            else printf("%lld\n",X[n]);
    }
}

V1.5

题源：【Comet OJ - Contest #6】F. permutation

题目大意

  （题意同 V1）
  给定 $n$，求有多少长度为 $n$ 的排列，满足该排列任意一个非平凡子段都不是连续段。

  $n \leq 10^5$
  1s

题解

  其实就是 V1 的加强版，把裸的 dp 用生成函数搞成了一个多项式牛逼题。。。
  待填坑吧。。

V2

题源：【2018 EC Final】B. Mysterious … Host

题目大意

  对于一个排列，它的每一个子段都可以标上一个“是否是连续段”。
  两个长度为 $n$ 的排列本质不同，当且仅当存在一个子段 $[l,r]$，它在其中一个排列里是连续段，在另一个排列里不是连续段。
  现在给定 $n$，对于 $\forall i \in [1,n]$，求有多少本质不同的、长度为 $i$ 的排列。

  $n \leq 5000$，模数是个大质数。
  1s

题解

  这题其实就是问，有多少大小为 $i$ 的本质不同的析合树形态。

  设 $f_i$ 表示大小为 $i$ 的本质不同的析合树形态（即答案），依然是按照“根是合点”以及“根是析点”来分类讨论。

  第一种情况，根是合点：只需把 $i$ 长度的排列分成若干段即可，这一定能对应合点的儿子划分。因此需要一个 $B_{i,j}$ 表示长度为 $i$ 的排列、划分成 $j$ 个子段的不同的析合树形态数量，即 $B_{i,j}=\sum_{k=1}^i B_{i-k,j-1} \cdot f_k$。
  于是这种情况的贡献就是 $\sum_{j=2}^i B_{i,j}$。

  第二种情况，根是析点：只需把 $i$ 长度的排列划分成至少 $4$ 个子段即可，这一定能对应析点的儿子划分（因为只需把儿子按恰当的顺序排起来即可，根据 V1 我们知道这一定有解的）。因此这种情况的贡献就是 $\sum_{j=4}^i B_{i,j}$。

  综上，$f_i=\big(\sum_{j=2}^i B_{i,j}\big)+\big(\sum_{j=4}^i B_{i,j} \big)$，这比 V1 还要简洁。。
  不过这是 $O(n^3)$ 的，还要再优化一下。
  观察发现 $B$ 数组开两维真是太浪费了，$j$ 这一维显然可以去掉，设 $g_i=\sum_{j=2}^i B_{i,j}$，那么就有 $f_i=2g_i-B_{i,2}-B_{i,3}$，其中 $B_{i,2}$ 每次 $O(n)$ 算即可，$B_{i,3}$ 借助 $B_{i,2}$ 也是每次 $O(n)$ 算的。这样时间复杂度就是 $O(n^2)$ 了。

代码

// $g$ 数组的含义比较灵活，贡献完 $f_i$ 之后它的含义就变成把 $B_{i,1}$ 也加进去了。

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=5005;

int n;
LL mo;

LL f[maxn],g[maxn],g2[maxn];
void dp()
{
    g[1]=f[1]=1;
    fo(i,2,n)
    {
        fo(j,1,i-1) (g[i]+=g[j]*f[i-j])%=mo;
        fo(j,1,i-1) (g2[i]+=f[j]*f[i-j])%=mo;
        f[i]=(g[i]*2-g2[i]+mo)%mo;
        fo(j,1,i-2) f[i]=(f[i]-g2[i-j]*f[j]%mo+mo)%mo;
        (g[i]+=f[i])%=mo;
    }
}

int T;
int main()
{
    scanf("%d %lld",&n,&mo);

    dp();

    fo(i,1,n) printf("%lld\n",f[i]);
}

V3

题源：【CTSC2018】青蕈领主

题目大意

  给定 $n$，表示排列长度，然后给出 $L_1,\cdots,L_n$ 表示每个元素以它为右端点的最长连续段长度。问有多少种排列，答案模 $998244353$。

  $n \leq 50000$
  多测，$T \leq 100$，但每个 test case 的 $n$ 都相同
  3s

题解

  这个 $L_i$ 就是析合树建树要用的那个数组。。但是根据这个 $L$ 数组是不能唯一确定析合树形态的，比如 $[1,2,3]$ 和 $[2,1,3]$ 是不同的析合树形态，但拥有同样的 $L$ 数组。
  所以这题不算是严格的析合树形态计数。不过作为析合树的启蒙题，对于连续段还是很有研究的。

  首先这个 $L$ 数组需要满足极长连续段不相交，否则是无解。
  虽然 $L$ 数组不能还原析合树，但是如果把每个点连向它后面第一个能覆盖到它的点，还是能形成一个树形结构的。
  对于一个结点来说，假设儿子加上自己共 $len$ 个，那么它的方案数就是长度为 $len$、满足“不存在不含最后一个元素的非平凡连续段”的排列的数量。最终答案就等于每个结点的贡献乘起来。
  我们就需要计算一个 $f_i$ 表示长度为 $i$、满足“不存在不含最后一个元素的非平凡连续段”的排列的数量，最终答案即 $\prod f_{len}$。

  至于这个 $f$ 数组怎么算，我感觉网上几乎所有的博客都有细节错误。
  首先转换一下模型，若排列 $p$ 满足“不存在不含最后一个元素的非平凡连续段”，那么它唯一对应一个排列 $q$（$q_{p_i}=i$），$q$ 满足“不存在不含最大值的非平凡连续段”。
  所以来求 $q$ 的数量。
  设 $q$ 长度为 $i$，考虑删掉 $q$ 的最小值，即 $1$。
  第一种情况：删掉 $1$ 后排列依然合法，那么这个 $1$ 只要不放在 $2$ 的旁边都是可以的，方案数为 $(i-2)f_{i-1}$。（证明：放在 $2$ 旁边肯定不行，若不放在 $2$ 旁边却造成了非平凡连续段，那么把 $1$ 删掉它仍然会是个非平凡连续段，矛盾）
  第二种情况：删掉 $1$ 后排列不合法，出现了非平凡连续段（不含 $2$ 也不含 $i$）。枚举最长的非平凡连续段长度 $j$，这个连续段插入 $1$ 后就不存在非平凡连续段了，即原本所有的非平凡连续段都经过 $1$ 这个位置，这就等价于有一个长度为 $j+1$ 的合法排列把最大值删掉换成 $1$，所以贡献为 $f_{j+1}$。把这个连续段缩起来以后排列必须合法，即$f_{i-j}$，这个连续段的值域选取有 $i-j-2$ 种。因此这种情况的方案数就是 $\sum_{j=2}^{i-3}(i-j-2)f_{j+1}f_{i-j}$，即 $\sum_{j=3}^{i-2}(j-2)f_{j}f_{i+1-j}$
  综上：

$$f_i=(i-2)f_{i-1}+\sum_{j=3}^{i-2}(j-2)f_{j}f_{i+1-j}$$

  于是分治 NTT 预处理出来就好了，时间 $O(n \log^2 n)$。

思考

  就是求 $f$ 的时候，我脑补了另一种方法。

  现在要求长度为 $i$、满足“不存在不含最后一个元素的非平凡连续段”的排列数量。我就考虑这样的排列对应的析合树。转化成析合树是什么限制呢？第一，任意非叶子结点除去最后一个儿子外必须是单个元素；第二，合点只能有两个儿子；第三，上升合点的合儿子必须下降，下降合点的合儿子必须上升。
  设 $g_i$ 表示根节点为上升合点的合法排列数（下降合点方案数跟上升是一样的），$h_i$ 表示根节点为析点的合法排列数，那么就有 $f_i=2g_i+h_i$。
  第一种情况：根是上升合点，那么它只能有两个儿子，且第二个儿子是析点或下降合点，所以 $g_i=g_{i-1}+h_{i-1}=f_{i-1}-g_{i-1}$
  第二种情况：根是析点，那么根的儿子所构成的排列就必须满足“任意非平凡子段都不是连续段”，即 V1 所求的那种，沿用那个数组 $X_i$ 表示“不存在非平凡连续段”的排列数量。因此 $h_i=\sum_{j=4}^i X_jf_{i+1-j}$
  综上，$f_i=2g_i+\sum_{j=4}^i X_jf_{i+1-j}=2(f_{i-1}-f_{i-2}+f_{i-3}\cdots)+\sum_{j=4}^i X_jf_{i+1-j}$

  但这种方法由于要求 $X$ 数组因此直接 dp 的话要 $O(n^3)$。
  然后就不明白了，两种方法求的 $f$ 是一样的，但时间复杂度却不同，那是不是说 $X$ 和 $f$ 存在更深层的关联，要么可以把方法 2 的式子推导成方法 1，要么可以利用潜在的关联通过更优秀的复杂度求解 $X$？
  （由于 V1.5 的存在，这种关联很可能是生成函数上的关联。。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=5e4+5, maxlen=2e5+5;
const LL mo=998244353, g=3;

int n,a[maxn];

void ReadInt(int &data)
{
    data=0;
    char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    do{
        data=(data<<3)+(data<<1)+ch-'0';
        ch=getchar();
    } while (ch>='0' && ch<='9');
}

LL Pow(LL x,LL y)
{
    LL re=1;
    for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo;
    return re;
}

LL tp[maxlen],gpow[maxlen],ginv[maxlen];
int rv[maxlen];
void NTT(LL *a,int len,int sig)
{
    fo(i,0,len-1) tp[rv[i]]=a[i];
    for(int m=2; m<=len; m<<=1)
    {
        int hal=m>>1;
        LL gw=(sig==1 ?gpow[m] :ginv[m]), w=1;
        for(int j=0; j<hal; j++, (w*=gw)%=mo)
            for(int k=j; k<len; k+=m)
            {
                LL u=tp[k], v=tp[k+hal]*w%mo;
                tp[k]=(u+v)%mo;
                tp[k+hal]=(u-v+mo)%mo;
            }
    }
    memcpy(a,tp,sizeof(LL)*len);
}
void FFT(LL *a,LL *b,int n,int m)
{
    int len=1;
    while (len<=n+m) len<<=1;
    for(int i=0, j, k, l; i<len; rv[k]=i++)
        for(j=i, k=0, l=1; l<len; j>>=1, l<<=1) k=(k<<1)+(j&1);

    fo(i,n+1,len) a[i]=0;
    fo(i,m+1,len) b[i]=0;
    NTT(a,len,1), NTT(b,len,1);
    fo(i,0,len-1) (a[i]*=b[i])%=mo;
    NTT(a,len,-1);
    LL invlen=Pow(len,mo-2);
    fo(i,0,len-1) (a[i]*=invlen)%=mo;
}

LL f[maxn],fa[maxlen],fb[maxlen];
void cdq(int l,int r)
{
    if (l==r)
    {
        (f[l]+=f[l-1]*(l-2))%=mo;
        return;
    }
    int mid=(l+r)>>1;
    cdq(l,mid);

    if (l==3)
    {
        fo(i,l,mid) fa[i-l]=(i-2)*f[i]%mo, fb[i-l]=f[i];
        FFT(fa,fb,mid-l,mid-l);
        fo(i,max(mid+1,l+2),r) (f[i]+=fa[i+1-l-3])%=mo;
    } else
    {
        fo(i,l,mid) fa[i-l]=f[i];
        fo(i,l,r) fb[i-l]=f[i-l+3];
        FFT(fa,fb,mid-l,r-l);
        fo(i,max(mid+1,l+2),r) (f[i]+=fa[i+1-l-3]*(i-3))%=mo;
    }

    cdq(mid+1,r);
}

int T,z0,z[maxn],son[maxn];
int main()
{
    ReadInt(T), ReadInt(n);

    for(int m=2; m<=131072; m<<=1) gpow[m]=Pow(g,(mo-1)/m), ginv[m]=Pow(gpow[m],mo-2);
    f[1]=1, f[2]=2;
    if (n>=3) cdq(3,n);

    while (T--)
    {
        fo(i,1,n) ReadInt(a[i]);
        if (a[n]!=n) {puts("0"); continue;}

        memset(son,0,sizeof(son));
        z[z0=1]=n;
        bool insec=0;
        fd(i,n-1,1)
        {
            while (z0 && i+a[z[z0]]<=z[z0]) z0--;
            son[z[z0]]++;
            if (i-a[i]<z[z0]-a[z[z0]]) {insec=1; break;}
            z[++z0]=i;
        }
        if (insec) {puts("0"); continue;}

        LL ans=1;
        fo(i,1,n) (ans*=f[son[i]+1])%=mo;

        printf("%lld\n",ans);
    }
}