题解
f[i][j] 表示 当前串为第j个位置到第i个位置的串的方案数
O(n^3) 做法
f[i][j]=\sum_{j-k< i-j}f[j][k]
若 s(k+1,j)< s(j+1,i),j-k=i-j 则 f[i][j]+=f[j][k]
O(n^2) 做法
考虑 O(1) check s(k+1,j)<s(j+1,i)
逗逼神仙做法：SA
简单做法：求 lcp(I,j) 即s[i],s[j] 的最长公共前缀
若 lcp(k,j)<j-k-1 并且 s[k+ lcp(k,j)+1]< s[j+ lcp(k,j)+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 35 36 37 38 39 40 41 42 43 44 |
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=5010,MOD=1e9+7; char str[MAXN]; ll f[MAXN][MAXN],sum[MAXN][MAXN]; int lcp[MAXN][MAXN]; int n,a[MAXN]; int check(int x,int y){ if(lcp[x][y]>=y-x)return false;//y-x就是区间长度 if(a[x+lcp[x][y]]<a[y+lcp[x][y]])return true; if(a[x+lcp[x][y]]>a[y+lcp[x][y]])return false; return 0; } /*sum[i][j]保存的是f[i][1]+f[i][2]+...+f[i][j]*/ int main(){ cin>>n; scanf("%s",str+1); for(int i=1;i<=n;i++){ a[i]=str[i]-'0'; } for(int i=n;i>=1;i--){//预处理最长公共前缀 for(int j=n;j>=1;j--){ if(a[i]==a[j])lcp[i][j]=lcp[i+1][j+1]+1; } } for(int i=1;i<=n;i++)f[i][1]=1;//初始化 for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ if(a[j]==0)continue;//不能有前导0 int k=2*j-i;k=max(1,k);//左端点 f[i][j]=(f[i][j]+sum[j-1][j-1]-sum[j-1][k-1]+MOD)%MOD; k--; if(k>=0&&check(k,j))f[i][j]=(f[i][j]+f[j-1][k])%MOD; } for(int j=1;j<=i;j++)sum[i][j]=(sum[i][j-1]+f[i][j])%MOD; } ll ans=0; for(int i=1;i<=n;i++)ans=(ans+f[n][i])%MOD; cout<<ans<<endl; return 0; } |