传送门:【URAL】1057 Amount of Degrees
题目分析:将数转化成能达到的最大的01串,串上从右往左第i位为1表示该数包括B^i。
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = a ; i < b ; ++ i ) #define For( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define rev( i , a , b ) for ( int i = a ; i >= b ; -- i ) #define clr( a , x ) memset ( a , x , sizeof a ) int X , Y , K , B ; int dp[35][25] ; bool vis[35][25] ; int digit[35] ; int pow[35] ; int dfs ( int cur , int limit , int used ) { if ( cur == 0 ) return !used ; if ( vis[cur][used] && !limit ) return dp[cur][used] ; vis[cur][used] = 1 ; int ans = 0 , d = limit ? digit[cur] : 1 ; For ( i , 0 , d ) if ( used - i >= 0 ) ans += dfs ( cur - 1 , limit && i == digit[cur] , used - i ) ; if ( !limit ) dp[cur][used] = ans ; return ans ; } int solve ( LL n ) { int i = 0 ; pow[1] = 1 ; for ( i = 1 ; ( LL ) pow[i] * B <= n ; ++ i ) pow[i + 1] = pow[i] * B ; int n1 = i , tmp = pow[n1] ; digit[n1] = 1 ; for ( -- i ; i ; -- i ) { if ( ( LL ) tmp + pow[i] <= n ) digit[i] = 1 , tmp += pow[i] ; else digit[i] = 0 ; } clr ( vis , 0 ) ; return dfs ( n1 , 1 , K ) ; } int main () { while ( ~scanf ( "%d%d%d%d" , &X , &Y , &K , &B ) ) printf ( "%d\n" , solve ( Y ) - solve ( X - 1 ) ) ; return 0 ; }