【URAL】1057 Amount of Degrees 数位DP

本文主要是介绍【URAL】1057 Amount of Degrees 数位DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：【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 ;
}

这篇关于【URAL】1057 Amount of Degrees 数位DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---