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’)$来判断大小

只需要一个区间和


3.$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);
}