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

Problem - 611D - Codeforces

題意：
給你一個大數。要求分割成若干個數字，滿足嚴格遞增，而且沒有領導 0。
問方案數對 1e9 + 7 取模。

制約：
1 ≤ N ≤ 5000
保證第一個字符不為 '0'。

解法：
dp[ i ][ j ]：最後一個數字是 S[ i : j ] 時的方案數。
想知道 dp[ i ][ j ] 是多少，顯然前面一個數字長度比 j - i 小的都可以拿到，這用 dp 上的前綴和就可以處理。而長度比 j - i 大的一定拿不到。剩下就是判斷等長的能不能拿到，LCP 判一下就知道哪個大了。
其實 LCP 根本就可以預處理。

複雜度：
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;
}