Description:

平衡数是以这个数字的某一位为支点，另外两边的数字大小乘以力矩之和相等的数字，求出区间内平衡数的个数。

$1\le T\le 30$ $0\le L\le R \le 10^{18}$

Solution:

转化为 $calc(r)-calc(l-1)$ ，枚举支点的位置，对于支点左边的加，右边的减，然后就是数位 $DP$ 记搜模板题了。如果到了最后一位 $sum=0$ ，就加一，注意如果 $sum<0$ 了，那之后再减 $sum$ 会一直小于 $0$ ，可以直接剪枝。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

int testcases;

ll l,r;

ll f[20][2000];

ll bit[20];

ll dfs(int pos,ll sum,int pivot,bool bord)

{

	if(sum < 0)return 0;

	if(pos == 0)

	{

		if(sum == 0)return 1;

		else return 0;

	}

	if(!bord && f[pos][sum] != -1)return f[pos][sum];

	int limit = bord ? bit[pos] : 9;

	ll res = 0;

	for(int i = 0;i <= limit;++i)

	{

		if(pos > pivot)res += dfs(pos - 1,sum + i * (pos - pivot),pivot,(bord && (i == limit)));

		else res += dfs(pos - 1,sum - i * (pivot - pos),pivot,(bord && (i == limit)));

	}

	if(!bord)f[pos][sum] = res;

	return res;

}

ll calc(ll t)

{

	if(t == -1)return 0;

	memset(f,0,sizeof(f));

	ll res = 0;

	ll len = 0;

	memset(bit,0,sizeof(bit));

	while(t > 0)

	{

		bit[++len] = t % 10;

		t = t / 10;

	}

	for(int i = 1;i <= len;++i)

	{

		memset(f,-1,sizeof(f));

		res += dfs(len,0,i,true);

	}

	return res - len + 1;

}

void work()

{

	cin >> l >> r;

	cout << calc(r) - calc(l - 1) << endl;

	return;

}

int main()

{

	scanf("%d",&testcases);

	for(int i = 1;i <= testcases;++i)

	{

		work();	

	}

	return 0;

}