Balanced Number

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 9808 Accepted Submission(s): 4662

Problem Description
A balanced number is a non-negative integer that can be balanced if a pivot is placed at some digit. More specifically, imagine each digit as a box with weight indicated by the digit. When a pivot is placed at some digit of the number, the distance from a digit to the pivot is the offset between it and the pivot. Then the torques of left part and right part can be calculated. It is balanced if they are the same. A balanced number must be balanced with the pivot at some of its digits. For example, 4139 is a balanced number with pivot fixed at 3. The torqueses are 42 + 11 = 9 and 9*1 = 9, for left part and right part, respectively. It’s your job
to calculate the number of balanced numbers in a given range [x, y].

Input
The input contains multiple test cases. The first line is the total number of cases T (0 < T ≤ 30). For each case, there are two integers separated by a space in a line, x and y. (0 ≤ x ≤ y ≤ 1018).

Output
For each case, print the number of balanced numbers in the range [x, y] in a line.

Sample Input
2
0 9
7604 24324

Sample Output
10
897

Author
GAO, Yuan

Source
2010 Asia Chengdu Regional Contest

一道比较明显的数位dp。

因为一个数字的位数不多，所以我们可以枚举当每一位作为中心点的时候的个数，而且不会计算重复，因为移动中心点的时候具有单调性。

怎么统计答案呢？我们就可以当，当前位数在x的左边的时候加，右边减，最后判断是否为0即可。

有个很重要的点：我们做数位dp的时候避免不了枚举到00000，这种情况，也是会被计算的，所以我们要减去这种情况。即减去 位数+1。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,a[20],dp[20][20][2000],x,y;
int dfs(int pos,int x,int s,int limit){
	if(!pos)	return s==0;
	if(s<0)	return 0;
	if(!limit&&dp[pos][x][s]!=-1)	return dp[pos][x][s];
	int up=limit?a[pos]:9,res=0;
	for(int i=0;i<=up;i++){
		res+=dfs(pos-1,x,s+(pos-x)*i,limit&&i==up);
	}
	if(!limit)	dp[pos][x][s]=res;
	return res;
}
inline int solve(int x){
	if(x<0)	return 0;
	int cnt=0,res=0;
	while(x)	a[++cnt]=x%10,x/=10;
	for(int i=1;i<=cnt;i++)	res+=dfs(cnt,i,0,1);
	return res-cnt+1;	
}
signed main(){
	cin>>T;	memset(dp,-1,sizeof dp);
	while(T--){
		cin>>x>>y;
		cout<<solve(y)-solve(x-1)<<endl;
	}
	return 0;
}