Mw Winter Camp Day1 D(DP+后缀数组)

|

题意

给定字符串 $S$ $(|S|\le3000)$ ，求将 $S$ 分裂成几个递增的子串的方案数

题解

令 $d[i][j]$ 为到第 $j$ 个字符，最后一段取 $S[i:j]​$ 的方案数

那么 $d[i][j]=\sum d[k][i-1]\,\,(S[k:i-1]<S[i:j])$

利用后缀数组做子串比较，复杂度为 $O(n^3)$

而这种做法并没有充分利用好后缀数组的优势，故直接考虑枚举 $i$ 和 $k$ ，那么可以求 $i$ 和 $k$ 的 $LCP$ ，如果 $LCP$ 的下一位是递增的，那么对这个位置以后的 $j$ 都能产生贡献，否则无法产生贡献。

然后还有一个 $trick$ 是 $LCP$ 长度大于 $|S[k:i-1]|$ ，这个时候对该长度以后的位置都能产生贡献




代码

后缀数组板子由 $wang9897$ 提供%%%

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
#include<bits/stdc++.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge*j=h[x];j;j=j->next)
#define ll long long
#define sqr(x) ((x)*(x))
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int inf=1e9+9;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int MAXN=3005;

int n,ca;
char _s[MAXN];
ll d[MAXN][MAXN],ans;
int sa[MAXN],txt[MAXN],t1[MAXN],t2[MAXN],rank1[MAXN],rank2[MAXN],td[MAXN];
bool cmp(int f[],int tt,int ttt,int k){
    return f[tt]==f[ttt]&&f[tt+k]==f[ttt+k];
}
void Sa(char str[]){
    int m=250;int len=strlen(str);
    int *td=t1;int *rank1=t2;
    for(int i=0;i<m;i++)txt[i]=0;
    for(int i=0;i<len;i++)txt[str[i]]++,rank1[i]=str[i];
    for(int i=1;i<m;i++)txt[i]+=txt[i-1];
    for(int i=len-1;i>=0;i--)sa[--txt[str[i]]]=i;
    for(int k=1;k<=len;k=k*2){
	int p=0;
	for(int i=len-k;i<len;i++)td[p++]=i;
	for(int i=0;i<len;i++)if(sa[i]>=k)td[p++]=sa[i]-k;
	for(int i=0;i<m;i++)txt[i]=0;
	for(int i=0;i<len;i++)txt[rank1[i]]++;
	for(int i=1;i<m;i++)txt[i]+=txt[i-1];
	for(int i=len-1;i>=0;i--)sa[--txt[rank1[td[i]]]]=td[i];
	p=1;
	swap(rank1,td);
	rank1[sa[0]]=0;
	for(int i=1;i<len;i++)rank1[sa[i]]=cmp(td,sa[i],sa[i-1],k)?p-1:p++;
	if(p>=len)return ;
	m=p;
    }
}

int h[MAXN],H[MAXN];
void HH(char str[]){
    int len=strlen(str);
    for(int i=0;i<len;i++)rank2[sa[i]]=i;
    memset(H,0,sizeof(H));
    for(int i=0;i<len;i++){
	if(rank2[i]==0)continue;
	int t=sa[rank2[i]-1];int w=i;int k=0;
	if(i==0||H[i-1]<=1)k=0;
	else k=H[i-1]-1,t+=k,w+=k;
	while(t<len&&w<len){
	    if(str[t]==str[w])k++;
	    else break;
	    t++;w++;
	}
	H[i]=k;h[rank2[i]]=k;
    }
}

int dp[MAXN][16],ma[MAXN];
void St(char str[]){
    int len=strlen(str);
    inc(i,2,len)ma[i]=ma[i/2]+1;
    for(int i=1;i<len;i++)dp[i][0]=h[i];
    for(int j=1;j<=15;j++){
	for(int i=1;i+(1<<j)<=len;i++){
	    dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
	}
    }
}

int Lcp(int l,int r){
    if(l>r)swap(l,r);
    l++;
    int k=ma[r-l+1];
    return min(dp[l][k],dp[r-(1<<k)+1][k]);
}


int main(){
    while(~scanf("%s",_s)){
	if(_s[0]=='-')break;
	n=strlen(_s);ans=0;
	_s[n]='$';_s[n+1]='\0';
	Sa(_s);HH(_s);St(_s);
	inc(i,0,n-1)inc(j,0,n-1)d[i][j]=0;
	inc(j,0,n-1)d[0][j]=1;
	inc(i,1,n-1){
	    inc(j,0,i-1){
		int t=Lcp(rank2[i],rank2[j]);
		if(t+j>=i&&i+i-j<n){
		    (d[i][i+(i-j)]+=d[j][i-1])%=inf;
		}else{
		    if(rank2[i]>rank2[j]&&i+t<n)
		    (d[i][i+t]+=d[j][i-1])%=inf;
		}
	    }
	    inc(j,i+1,n-1)(d[i][j]+=d[i][j-1])%=inf;
	}
	//inc(i,0,n-1){inc(j,0,n-1)printf("%lld ",d[i][j]);putchar('\n');}
	inc(i,0,n-1)ans+=d[i][n-1],ans%=inf;
	printf("Case #%d: There are %lld ways.\n",++ca,ans);
    }
    return 0;
}