题意: 给出范围 算出 满足 选取一个数中任一一个 树作为支点 两边的数分别乘以到中心的距离和 左和等于右和 的数有多少个
数位DP题 状态转移方程为dp[pos][x][state]=dp[pos-1][x][state-(pos-x)*i] 表示为pos位上的数字为 i 以x为支点 则 以中心点左为负右为正 pos左右的数乘以权值的 和为state pos-1位就是 把pos位的 i乘以权值减去 即 state-(pos-x)*i 如果枚举到最后一位的时候 state==0就说明平衡了 其中 0 00 000 000 ......也是平衡的 出了0其他都是非法的要减去
#include <cstdio>
#include <cmath>
#include <algorithm>
#include<vector>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int MOD=;
int cnt;
ll a[];
int t[];
ll dp[][][]; ll dfs(int pos,int x,int state,bool limit ){
if(pos==-)return !state;
if(!limit&&dp[pos][x][state]!=-)return dp[pos][x][state];
int up=limit?a[pos]:;
ll ans=;
for(int i=;i<=up;i++){
ans+=dfs(pos-,x,state+i*(pos-x),limit&&up==i);
}
if(!limit) dp[pos][x][state]=ans;
return ans;
} ll solve(ll x){
int pos=;
while(x){
a[pos++]=x%;
x/=;
}
ll ans=;
for(int i=;i<pos;i++)ans+=dfs(pos-,i,,);
return ans-pos+;// 减去00 000 000 其中单0算 所以加一
} int main()
{
ll a,b;
int t;
cin>>t;
memset(dp,-,sizeof(dp));
while(t--){
cin>>a>>b;
printf("%I64d\n",solve(b)-solve(a-));
} return ;
}