题意：

把一个n位整数切成若干段，得到若干个整数。要求每个数都不为0，每个数都没有前缀0，且前一个数严格小于后一个数。问切割数方案取模。

\(n\le 5000\)

思路：

\(O(n^2)\) 的dp，\(f(l,r)\) 表示最后一段是 \([l,r]\) 的方案数，则答案是 \(\sum\limits _i f(i,n)\)

状态转移：若（作为一个整数的）\(a[l,i]<a[i+1,r]\) ，则 \(f(i+1,r)+=f(l,i)\)

双指针，\(l\) 从 \(i\) 开始往左走，\(r\) 从 \(i+1\) 开始走到 \(a[l,i]<a[i+1,r]\) 的第一个位置，那么 \(f(i+1,r\sim n)\) 都能被更新，也就是一个后缀被更新。开个差分数组处理区间加。

注意不能有前导零，且要初始化 \(f(1,1\sim n)=1\)

上面的dp不难想到，但是一般比较两个子串是 \(O(n)\) 的，需要加速。一个方法是 $ O(n^2)$ 预处理 \(lcp(i,j)\) 表示以 \(a_i,a_j\) 开始的最长公共子串的长度。

const int N = 5005, MOD = 1e9 + 7;
int n, lcp[N][N], f[N][N], b[N];
char a[N];
void init()
{
    for(int i = n; i; i--)
        for(int j = n; j; j--)
            if(a[i] == a[j])
                lcp[i][j] = lcp[i+1][j+1] + 1;
}
bool ok(int l1, int r1, int l2, int r2)
{ //前一个是不是比后一个小
    if(r1-l1 != r2-l2) return r1-l1 < r2-l2;
    int p = lcp[l1][l2];
    if(p >= r1 - l1 + 1) return 0;
    return a[l1+p] < a[l2+p];
}
signed main()
{
    cin >> n >> a + 1;
    init();

    for(int i = 1;  i <= n; i++) f[1][i] = 1;
    for(int i = 1; i < n; i++)
    {
        if(a[i+1] == '0') continue; //不能有前导零
        memset(b, 0, sizeof b);
        int r = i + 1;
        for(int l = i; l; l--)
        {
            while(r <= n && !ok(l,i,i+1,r)) r++;
            if(r <= n) (b[r] += f[l][i]) %= MOD;
        }
        for(int j = i + 1; j <= n; j++)
            (b[j] += b[j-1]) %= MOD, (f[i+1][j] += b[j]) %= MOD;
    }

    int ans = 0;
    for(int i = 1; i <= n; i++) (ans += f[i][n]) %= MOD;
    cout << ans;
}