数位dp ， 注意‘】pos < (len + 1 )/2 以及每次模k
can you hear me ?
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>using namespace std;
typedef long long ll ;
const int maxn = 10005 ;
int temp[100] ;
ll dp[40][100][100][2] ;
int a[20] ;
int b[20] ;
int all ;ll dfs( int pos , int len ,bool status , bool limit ,int k ){if( pos == -1 ) return status ? k : 1 ;if( !limit && dp[k][pos][len][status] != -1 ) return dp[k][pos][len][status] ;int up = limit ? a[pos] : k - 1 ;ll tmp = 0 ;for( int i = 0 ; i <= up ; i ++ ){temp[pos] = i ;if( i == 0 && pos == len )tmp += dfs( pos-1 , len-1 , status , limit && i == up , k ) ;else if( pos < (len + 1 )/2 )tmp += dfs( pos-1 , len , status && i == temp[len-pos] , limit && i == up , k ) ;elsetmp += dfs( pos-1 , len , status , limit && i == up , k ) ;}if(! limit) dp[k][pos][len][status] = tmp ;return tmp ;
}
ll solve (ll L , int k) {int po = 0 ;while( L ){a[po ++ ] = L % k ;L /= k ;}int t = 0 ;return dfs( po - 1 , po - 1 , true , true , k ) ;
}int main () {int kase , ka = 1 ;ll L , R , l , r ;scanf("%d",&kase);memset(dp,-1,sizeof dp);while( kase -- ){scanf("%lld %lld %lld %lld",&L,&R , &l , &r);ll res = 0 ;for( int i = l ; i <= r ; i ++ ){res += solve( R , i ) - solve( L-1 , i );}printf("Case #%d: %lld\n",ka++, res );}return 0 ;
}