学步园

题意：让你求l----r(1e18)之间有多少个数 满足  天平平衡，天平平衡就是存在一个支点，val = 各位数字与支点的距离的乘积，支点左边的val = 支点右边的val

思路：枚举支点，然后数位dp一下。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
int a[22];
ll dp[22][22][2222];
ll dfs(int len, int idx, int sum, bool lim) {
	if(!len) return !sum;
	if(sum < 0) return 0;
	if(!lim && ~dp[len][idx][sum]) return dp[len][idx][sum];
	ll ret = 0;
	int m = lim ? a[len] : 9;
	for(int i = 0; i <= m; i++)
		ret += dfs(len-1, idx, sum+(len-1-idx)*i, lim&&i==m);
	if(!lim) dp[len][idx][sum] = ret;
	return ret;
}
ll gao(ll n) {
	if(n < 0) return 0;
	int len = 0;
	while(n) {
		a[++len] = n%10;
		n /= 10;
	}
	ll ret = 0;
	for(int i = 0; i < len; i++)
		ret += dfs(len, i, 0, 1);
	return ret-len+1; //去掉支点不在最低位而且全是数字0的情况
}
int main() {
	int cas;
	ll l, r;
	memset(dp, -1, sizeof(dp));
	scanf("%d", &cas);
	while(cas--) {
		cin >> l >> r;
		cout << gao(r) - gao(l-1) << endl;;
	}
	return 0;
}