# CFR 611 D. New Year and Ancient Prophecy ( DP, Hash, LCP )

Problem - 611D - Codeforces

1 ≤ N ≤ 5000

dp[ i ][ j ]：最後一個數字是 S[ i : j ] 時的方案數。

O( N ** 2 * lg N )

```#include <bits/stdc++.h>
using namespace std;

const int MOD = int( 1e9 + 7 );
const int BASE = 311;

const int MAXN = 5000;

int N;
string S;
int base[ MAXN + 1 ];
int ph[ MAXN + 1 ];

int dp[ MAXN ][ MAXN + 1 ]; // [ i, j )
int pdp[ MAXN + 1 ][ MAXN + 1 ]; // pdp[ i ][ j ] = sum( dp[ 0, i )[ j ] )

int gh( int x, int y ) { // [ x, y )
int res = ( 1LL * ph[ y ] - 1LL * ph[ x ] * base[ y - x ] ) % MOD;
if( res < 0 ) res += MOD;
return res;
}

int lcp( int x, int y, int h ) { // [ x, x + h ) : [ y, y + h )
int lb = 0, ub = h + 1;
while( lb + 1 != ub ) {
int mid = lb + ub >> 1;
( gh( x, x + mid ) == gh( y, y + mid ) ? lb : ub ) = mid;
}
return lb;
}

#define less my_less

bool less( int a, int b, int c, int d ) { // [ a, b ) < [ c, d ) ?
assert( b - a == d - c );
int h = lcp( a, c, b - a );
if( h == b - a ) return false;
return S[ a + h ] < S[ c + h ];
}

signed main() {
ios::sync_with_stdio( 0 );
cin >> N;
cin >> S;
base[ 0 ] = 1;
for( int i = 0; i < N; ++i ) {
base[ i + 1 ] = 1LL * base[ i ] * BASE % MOD;
ph[ i + 1 ] = ( 1LL * ph[ i ] * BASE + S[ i ] ) % MOD;
}
for( int i = 1; i <= N; ++i ) {
dp[ 0 ][ i ] = 1;
for( int j = 1; j < i; ++j ) {
if( S[ j ] == '0' ) continue;
int st;
if( j < i - j ) st = 0;
else st = less( j - ( i - j ), j, j, i ) ? j - ( i - j ) : j - ( i - j ) + 1;
dp[ j ][ i ] = ( pdp[ j ][ j ] - pdp[ st ][ j ] ) % MOD;
if( dp[ j ][ i ] < 0 ) dp[ j ][ i ] += MOD;
}
for( int j = 0; j < i; ++j ) {
pdp[ j + 1 ][ i ] = ( pdp[ j ][ i ] + dp[ j ][ i ] ) % MOD;
}
}
cout << pdp[ N ][ N ] << endl;
return 0;
}
```