本文主要是介绍【codeforces】55D. Beautiful numbers 数位DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【codeforces】55D. Beautiful numbers
题目分析：被每一位整除则用二进制记录已经包括的数字的个数，以及对2520取模后的状态。由于对5整除当且仅当最后一个数为0或5，对2整除当且仅当最后一个数为偶数，且1~9的最小公倍数为2520，不包括2，5后的最小公倍数为252，所以除最后一层对2520取模，其余时候都对252取模即可。由于整除的状态有限，最多只有48个，于是我们预处理出这48个数，并来一个映射就好（不然会TLE）。
通过这题我才知道dp只用一次清零即可。。。
代码如下：
#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 )LL L , R ;
LL dp[19][252][48] ;
int a[2521] , cnt ;
int digit[19] ;int gcd ( int a , int b ) {return b ? gcd ( b , a % b ) : a ;
}LL dfs ( int cur , int limit , int x , int y , LL ans = 0 ) {if ( cur < 0 ) return x % y == 0 ;if ( ~dp[cur][x][a[y]] && !limit ) return dp[cur][x][a[y]] ;int n = limit ? digit[cur] : 9 ;For ( i , 0 , n ) ans += dfs ( cur - 1 , limit && i == digit[cur] , cur ? ( x * 10 + i ) % 252 : ( x * 10 + i ) , i ? y * i / gcd ( y , i ) : y ) ; return limit ? ans : dp[cur][x][a[y]] = ans ;
}LL solve ( LL n ) {int n1 = 0 ;while ( n ) {digit[n1 ++] = n % 10 ;n /= 10 ;}return dfs ( n1 - 1 , 1 , 0 , 1 ) ;
}int main () {int T ;cnt = 0 ;For ( i , 1 , 2520 ) if ( 2520 % i == 0 ) a[i] = cnt ++ ;clr ( dp , -1 ) ;scanf ( "%d" , &T ) ;while ( T -- ) {scanf ( "%I64d%I64d" , &L , &R ) ;printf ( "%I64d\n" , solve ( R ) - solve ( L - 1 ) ) ;}return 0 ;
}这篇关于【codeforces】55D. Beautiful numbers 数位DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
