# CFR 204 A. Little Elephant and Interval ( Digit DP )

Problem - 204A - Codeforces

dp[ i ][ j ][ k ][ l ] : 考慮前 i 個位數，已嚴格小於對照數，第一個位數，最後一個位數，滿足這些條件的狀態數。

```ll L, R;

void init(){
cin >> L >> R;
}

void preprocess(){

}

ll get_pcnt( ll x, int inc ){ // returns number of the required values in range [ 1, x ) / ]
vi s;
while( x )
s.emplace_back( x % 10 ),
x /= 10;
reverse( s.begin(), s.end() );
vvvvl dp( s.size() + 1, vvvl( 2, vvl( 10, vl( 10 ) ) ) );
dp[ 0 ][ 0 ][ 0 ][ 0 ] = 1;
for( int i = 0; i < s.size(); ++i )
for( int j = 0; j < 2; ++j )
for( int k = 0; k < 10; ++k )
for( int l = 0; l < 10; ++l )
for( int d = 0; d <= ( j ? 9 : s[ i ] ); ++d ){
if( k == 0 )
dp[ i + 1 ][ j | d < s[ i ] ][ d ][ d ] += dp[ i ][ j ][ k ][ l ];
else
dp[ i + 1 ][ j | d < s[ i ] ][ k ][ d ] += dp[ i ][ j ][ k ][ l ];
}
ll res = 0;
for( int j = 0; j < 2; ++j )
for( int k = 1; k < 10; ++k ){
if( not j and not inc )
continue;
res += dp[ ( int ) s.size() ][ j ][ k ][ k ];
}
return res;
}

void solve(){
cout << get_pcnt( R, 1 ) - get_pcnt( L, 0 );
}
```