CF1393E2 - Twilight and Ancient Scroll (harder version)

Posted on Edited on In

CF1393E2 - Twilight and Ancient Scroll (harder version)

题目大意

给定 \(n\) 个串 \(S_i\) ，求在每个串中至多删除一个字符（可以删到空）

最终 \(S'_i\) 字典序单调不减的方案数



dp

显然是记录上一个串删除的位置 \(j\) ，得到 \(dp_j\) ，依次考虑每个串

设 \(S\) 为当前串， \(T\) 为上一个串

每次我们枚举当前串删除的位置 \(i\) ，不妨设得到的新串为 \(S'\) ，考虑对于 \(S'\) 找到所有合法转移

设 \(L=LCP(S,T)\) ，在 \(T\) 中删除位置为 \(t\)

  1. \(t>L+1\)

则可以根据 \(T_{L+1}\) 和 \(S'_{L+1}\) 的关系确定 \(T'\) 与 \(S'\) 的关系，只需要处理一个后缀和 \(suf_i\)


2.设 \(p\) 为 \(T_{L+1}\) 向前延伸且字符相同的最长位置， \(t\in[p,L+1]\)

此时，删除 \(T_t\) 可能会使得 \(L'>L\) ，所以提出来特殊处理

显然 \(t\in[p,L+1]\Leftrightarrow t=L+1\) ，那么对于得到的新串可以再求 \(LCP(S',T')\) 来判断大小

只需要一个区间和


  1. \(t<p\) ，此时 \(L'=LCP(S',T')<L\)

由于 \(L'<L\) ,比较 \(S',T'\) 相当于比较 \(T_{t:},T_{t+1:}\)

其中 \(T_{t:}\) 表示 \(T\) 在 \(t\) 开始的后缀，那么预处理找到所有合法的 \(t\) ，累前缀和即可得到 \(pre_{p-1}\)


关于实现

写 \(\text{SA,SAM}\) 就完蛋了

由于删除一个字符之后，求 \(LCP\) 的两个串就是在原串基础上进行 \(\pm 1\) 的偏移

线性预处理三个 \(LCP\) 数组即可，当然真正求的时候需要分类讨论一下(真的，就一下/md)


判断 \(T_{t:},T_{t+1:}\) 容易倒着线性预处理出来，在代码里是 \(chk_i\)


所有操作均可以线性处理，时间复杂度为 \(O(L)\) ，77ms

Tips:

比较过程中容易出现奇妙的越界，我写得很丑

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
const int N=1e6+10,P=1e9+7;

int n,m;
char A[2][N],*S=A[0],*T=A[1];
int X[N],Y[N],Z[N];
int dp[N],F[N],suf[N],pre[N],chk[N],L[N];

int main(){
	rep(_,1,rd()) {
		swap(S,T),swap(n,m);
		scanf("%s",S+1),n=strlen(S+1);
		rep(i,n+1,m+2) S[i]=1;
		rep(i,m+1,n+2) T[i]=-1;
		if(!m) {
			rep(i,1,n+1) dp[i]=1;
			continue;
		}
		rep(i,max(n,m)+1,i+2) X[i]=Y[i]=Z[i]=0;
		drep(i,max(n,m),1) {
			X[i]=S[i]==T[i]?X[i+1]+1:0;
			Y[i]=S[i]==T[i+1]?Y[i+1]+1:0;
			Z[i]=S[i+1]==T[i]?Z[i+1]+1:0;
		}

		// initiate
		suf[m+2]=0;
		drep(i,m+1,1) suf[i]=suf[i+1]+dp[i],Mod1(suf[i]);
		drep(i,m,1) chk[i]=T[i]!=T[i+1]?T[i]>T[i+1]:chk[i+1];
		rep(i,1,m+1) L[i]=T[i]==T[i-1]?L[i-1]:i;
		rep(i,1,m) pre[i]=pre[i-1]+chk[i]*dp[i],Mod1(pre[i]);


		rep(i,1,n+1) {
			int l=min(X[1],i-1);
			if(l==i-1) l+=Z[i];
			F[i]=0;

			auto I=[&](int x){ return (x>=i)+x; };

			// type1 , deleted pos > l+1
			if(T[l+1]<=S[I(l+1)]) F[i]+=suf[l+2],Mod1(F[i]);
			int p=L[l+1];
			
			// type2 ,delete T between [p..l+1]  ,the same as we delete T[l+1]
			int r=0; // r= LCP(S'[l+2],T[l+2]) ,check if delete T[l+1], T'<=S'
			if(l+1<i) r+=min(i-l-1,Y[l+1]);
			if(r==max(0,i-l-1)) r+=X[l+2+r];
			if(T[l+2+r]<=S[I(l+1+r)]) F[i]=(F[i]+0ll+suf[p]-suf[l+2]+P)%P;
			
			// type3 , delete T at [1,p-1], so LCP'<l , and we determine T'<=S' by chk[i]
			F[i]=(F[i]+pre[p-1])%P;
		}
		rep(i,1,n+1) dp[i]=F[i];
	}
	int ans=0;
	rep(i,1,n+1) ans+=dp[i],Mod1(ans);
	printf("%d\n",ans);
}