析合树形态计数 dp

OI/XCPC , , , Comments

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

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

V1

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

题目大意

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

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

题解

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

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

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

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

  综上，Xi=i!−(2∑j=1i−1Hj⋅(i−j)!)−(∑j=4i−1Bi,j⋅Xj)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(n3)O(n^3)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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）
  给定 nn，求有多少长度为 nn 的排列，满足该排列任意一个非平凡子段都不是连续段。

  n≤105n \leq 10^5
  1s

题解

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

V2

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

题目大意

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

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

题解

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

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

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

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

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

代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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】青蕈领主

题目大意

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

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

题解

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

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

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

fi=(i−2)fi−1+∑j=3i−2(j−2)fjfi+1−jf_i=(i-2)f_{i-1}+\sum_{j=3}^{i-2}(j-2)f_{j}f_{i+1-j}

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

思考

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

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#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);
    }
}

Four.Yuan-AHuawei / AFOIACMer / LLer / TCS

糖少许，盐少许