CTSC 2018 青蕈领主（CDQ分治+NTT+单调栈）

发表于 |
字数统计: 2,709字 | 阅读时长 ≈ 12min

CTSC2018 青蕈领主

问题描述

“也许，我的生命也已经如同风中残烛了吧。”小绿如是说。

小绿同学因为微积分这门课，对“连续”这一概念产生了浓厚的兴趣。小绿打算把连续的概念放到由整数构成的序列上，他定义一个长度为 $m$ 的整数序列是连续的，当且仅当这个序列中的最大值与最小值的差，不超过$m-1$。例如 ${1,3,2}$ 是连续的，而 ${1,3}$ 不是连续的。

某天，小绿的顶头上司板老大，给了小绿 $T$ 个长度为 $n$ 的排列。小绿拿到之后十分欢喜，他求出了每个排列的每个区间是否是他所定义的“连续”的。然而，小绿觉得被别的“连续”区间包含住的“连续”区间不够优秀，于是对于每个排列的所有右端点相同的“连续”区间，他只记录下了长度最长的那个“连续”区间的长度。也就是说，对于板老大给他的每一个排列，他都只记录下了在这个排列中，对于每一个 $1 \le i \le n$，右端点为 $i$ 的最长“连续”区间的长度 $L_i$。显然这个长度最少为 $1$，因为所有长度为 $1$ 的整数序列都是连续的。

做完这一切后，小绿爬上绿色床，美美地做了一个绿色的梦。

可是第二天醒来之后，小绿惊讶的发现板老大给他的所有排列都不见了，只剩下他记录下来的 $T$ 组信息。小绿知道自己在劫难逃，但是作为一个好奇的青年，他还是想知道：对于每一组信息，有多少个和信息符合的长度为 $n$ 的排列。

由于小绿已经放弃治疗了，你只需要告诉他每一个答案对 $998244353$ 取模的结果。

我们并不保证一定存在至少一个符合信息的排列，因为小绿也是人，他也有可能犯错。

输入格式

输入的第一行包含两个整数 $T,n$，分别表示板老大给小绿的排列个数、以及每个排列的长度。

接下来 $T$ 行，每行描述一组信息，包含 $n$ 个正整数，第 $i$ 组信息的从左往右第 $j$ 个整数 $L_{i,j}$ 表示第 $i$ 个排列中右端点为第 $j$ 个数的最长“连续”区间的长度。

对于每一行，如果行内包含多个数，则用单个空格将它们隔开。

输出格式

对于每组信息，输出一行一个整数表示可能的排列个数对 $998244353$ 取模的结果。由于是计算机帮你算，所以我们不给你犯错的机会。

样例输入

5 10
1 1 1 1 1 6 1 1 1 2
1 1 1 3 1 1 1 1 1 10
1 1 1 1 1 1 7 1 1 10
1 1 1 1 1 1 1 1 1 10
1 1 1 1 1 1 1 7 9 10

样例输出

0
9600
2400
443296
2400

提示

测试点编号 $n\le$ $T\le$ 特殊性质
1~2 $10$ 1 无
3~4 $10$ 100 无
5 $300$ 1 $ L_{i,j}=j$
6 $300$ 1 $L_{i,j}=1$ 且 $j<n$
7~8 $300$ 100 无
9 $1000$ 1 $L_{i,j}=1$ 且 $j<n$
10~12 $1000$ 100 无
13~16 $5000$ 100 无
17~20 $50000$ 100 无

对于所有测试数据，$1 \le T \le 100$，$1 \le N \le 50000$, $1 \le L_{i,j} \le j$。
本题部分测试点的输入规模较大，请注意读入效率。

首先容易发现所有连续区间只存在相离和内含的关系，不会出现交叉，这个很容易证明

因此无解的条件就是最后一个数不为n，或区间出现了交叉

然后考虑有解的情况，容易发现如果将每个位置的极大连续区间看成一个点，那么每个区间向包含它的最小的区间连边之后会形成一棵树

对于根来说，每个子树都是一个编号连续的区间，然后如果将每个子树看成一个整体，即缩成一个点，那么只需要缩点后的序列满足不存在长度大于1的连续区间即可，这个缩点过程是可以递归的

因此最后只需要求解形如$1\ 1\ 1\ 1\ 1…n+1$的方案数，也就是特殊数据6和9，令其为$f[n]$

一般的，假设每个点的儿子个数分别是$D[1],D[2],…,D[n]$，那么答案就是$\Pi_{i=1}^{n}f[D[i]]$

计算$D$可以用单调栈简单解决，主要问题是求解$f[n]$，这个存在一个$O(n^3)/O(n^2)$的容斥解法，可以打表得到80分，然而并不能解决本题。

然后假设我们打了个表，$1,2,2,4,16,88,600,4800,43680,443296$，然后尝试寻找递推式。

反正我是没找到，翻了题解之后得到$f[n]=(n-1)f[n-1]+\sum_{i=2}^{n-2}(i-1)f[i]f[n-i]$

注意到$f[n]$的意思是长为$n+1$的序列，删去最后一位之后不存在长度大于1的连续区间的排列数

那么上面的递推式是什么意思呢

直接从这个定义去推很难解释，考虑一个满足条件的排列，$a_1,a_2,a_3,a_4$，那么我们将他置换一下，将$i$填到第$a_i$个位置上，即得到序列$b_{a_i}=i$

考虑新的排列满足的条件，那么$a_{n+1}$对应了$b_i$中的元素$n+1$，可以发现$b$序列满足：不存在不经过最大值的连续区间，证明比较简单，考虑$b_i$的连续区间在$a_i$中的位置即可。

并且$a$序列和$b$序列是一一对应的，因此可以转而计算满足不存在不经过最大值的连续区间的排列数

考虑从长为$n$的合法序列$p$中添加一个元素得到长为$n+1$的合法序列$q$

不妨认为$p$的编号从$2-n+1$，其方案数仍为$f[n-1]$，然后向其中添加一个最小值，只需要不与2相邻即可，因此有$n-1$种填法，因此总共有$(n-1)f[n-1]$种方案

再考虑从长为$n$的不合法序列$p$中添加一个元素得到长为$n+1$的合法序列$q$，依然考虑添加最小值

容易发现p中至多只能有一个不经过最大值的连续区间，那么枚举这个区间的长度$l(2<=l<=n-2)$，将这个连续区间视为整体后不能再存在不经过最大值的连续区间，方案数为$f[n-l]$

考虑这个连续区间的值域为$[x,x+l-1]$，那么因为加入一个元素1之后能够使得它不存在连续区间，那么$x>2且x+l-1<n+1$，那么合法的$x$有$n-l+1-3+1=n-l-1$个

再考虑这样的连续区间个数，由于1与这个区间的值域不相邻，因此加入1后不存在连续区间与加入$x+l$后不存在不经过最大值的连续区间等价，因此这样的区间数就是$f[l]$，并且可以认为插入方法唯一

因此这样可以得到的序列$q$的总数目就是$\sum_{i=2}^{n-2}(n-i-1)f[i]f[n-i]=\sum_{i=1}^{n-2}(i-1)f[i]f[n-i]$

那么上面的递推式得证。

然后这个递推式可以用分治$NTT$优化，处理的时候注意一下偏序关系和$NTT$的长度就行了。复杂度$O(n log^2 n)$

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 300005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
} 
const int mod=998244353,g=3;
int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
int sub(int a,int b){a-=b;return a<0?a+mod:a;}
int mul(int a,int b){return 1ll*a*b%mod;}
int ksm(int a,int b){int o;for(o=1;b;b>>=1,a=mul(a,a))if(b&1)o=mul(o,a);return o;}
int ntt_wi[N];
void NTT(int C[],int n,int ty)
{
	int i,j,k,m,t0,t1;
	for(i=j=0;i<n;i++)
	{
		if(i<j)swap(C[i],C[j]);
		for(k=(n>>1);(j^=k)<k;k>>=1);
	}
	ntt_wi[0]=1;
	for(m=1;m<n;m<<=1)
	{
		t0=ksm(g,mod-1+ty*(mod-1)/(m<<1));
		for(i=1;i<m;i++)ntt_wi[i]=mul(ntt_wi[i-1],t0);
		for(k=0;k<n;k+=m<<1)
		for(i=k;i<k+m;i++)
		{
			t0=C[i];t1=mul(C[i+m],ntt_wi[i-k]);
			C[i]=add(t0,t1);C[i+m]=sub(t0,t1);
		}
	}
	if(ty==1)return;t0=ksm(n,mod-2);
	for(i=0;i<n;i++)C[i]=mul(C[i],t0);
}
int A[N],D[N],f[N],dc_A[N],dc_B[N],dc_C[N],S[N],top;
void DC(int l,int r)
{
	if(l==r){f[l]=add(f[l],mul(f[l-1],l-1));return;}
	int mid=l+r>>1,i; 
	DC(l,mid);
	if(3<=l)
	{
		int lp=2,rp=min(l-1,r-l),L=1;
		while(L<=rp+mid-l)L<<=1;
		fill(dc_A,dc_A+L,0);
		fill(dc_B,dc_B+L,0);
		for(i=lp;i<=rp;i++)dc_A[i]=f[i];
		for(i=l;i<=mid;i++)dc_B[i-l]=f[i];
		NTT(dc_A,L,1);NTT(dc_B,L,1);
		for(i=0;i<L;i++)dc_C[i]=mul(dc_A[i],dc_B[i]);
		NTT(dc_C,L,-1);
		for(i=mid+1;i<=r;i++)if(i>=l)f[i]=add(f[i],mul(dc_C[i-l],i-2));
	}
	int L=1;while(L<=mid-l+mid-l)L<<=1;
	fill(dc_A,dc_A+L,0);
	fill(dc_B,dc_B+L,0);
	for(i=l;i<=mid;i++)dc_A[i-l]=f[i];
	for(i=l;i<=mid;i++)dc_B[i-l]=mul(i-1,f[i]);
	NTT(dc_A,L,1);NTT(dc_B,L,1);
	for(i=0;i<L;i++)dc_C[i]=mul(dc_A[i],dc_B[i]);
	NTT(dc_C,L,-1);
	for(i=mid+1;i<=r;i++)if(i>=l+l)f[i]=add(f[i],dc_C[i-l-l]);
	DC(mid+1,r);
}
int Solve(int n)
{
	int i,j,k,ans=1;top=0;
	if(A[n]!=n)return 0;
	S[++top]=n;
	fill(D,D+n+1,0);
	for(i=n-1;i>=1;i--)
	{
		while(S[top]-A[S[top]]+1>i)top--;
		if(i-A[i]<S[top]-A[S[top]])return 0;
		D[S[top]]++;
		while(top&&i-A[i]<=S[top]-A[S[top]])top--;
		S[++top]=i;
	}
	for(i=1;i<=n;i++)ans=mul(ans,f[D[i]]);
	return ans;
}
int main()
{
	int T,n,i,j,k,x,y;
	_R(T);_R(n);
	f[0]=1;f[1]=2;DC(2,n);
	while(T--)
	{
		for(i=1;i<=n;i++)_R(A[i]);
		printf("%d\n",Solve(n));
	}
}