学步园

传送门：【HDU】3709 Balanced Number

题目分析：枚举重心的位置再进行数位DP。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
  
typedef long long LL ;
 
#pragma comment(linker, "/STACK:16777216")

#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 travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )

LL dp[20][10][2][2000] ;
int vis[20][10][2][2000] , Time ;
int num[20] ;
int point ;
LL x , y ;

LL dfs ( int cur , int j , int flag , int number ) {
	if ( cur == 0 ) return !number ;
	if ( vis[cur][j][flag][number] == Time ) return dp[cur][j][flag][number] ;
	vis[cur][j][flag][number] = Time ;
	LL& ans = dp[cur][j][flag][number] = 0 ;
	if ( flag ) {
		rep ( i , 0 , 10 ) {
			int tmp = number + i * ( cur - point ) ;
			if ( tmp >= 0 ) ans += dfs ( cur - 1 , i , 1 , tmp ) ;
		}
	} else {
		rep ( i , 0 , num[cur] ) {
			int tmp = number + i * ( cur - point ) ;
			if ( tmp >= 0 ) ans += dfs ( cur - 1 , i , 1 , tmp ) ;
		}
		int tmp = number + num[cur] * ( cur - point ) ;
		if ( tmp >= 0 ) ans += dfs ( cur - 1 , num[cur] , 0 , tmp ) ;
	}
	return ans ;
}

LL deal ( LL n ) {
	if ( n == -1 ) return 0 ;
	int n1 = 0 ;
	while ( n ) {
		num[++ n1] = n % 10 ;
		n /= 10 ;
	}
	LL ans = 0 ;
	For ( i , 1 , n1 ) {
		point = i ;
		++ Time ;
		ans += dfs ( n1 , 0 , 0 , 0 ) ;
	}
	return ans - n1 + 1 ;
}

void solve () {
	scanf ( "%I64d%I64d" , &x , &y ) ;
	printf ( "%I64d\n" , deal ( y ) - deal ( x - 1 ) ) ;
}

int main () {
	int T ;
	clr ( vis , 0 ) ;
	Time = 0 ;
	scanf ( "%d" , &T ) ;
	while ( T -- ) solve () ;
	return 0 ;
}