题目链接：https://vjudge.net/contest/308832#problem/E
题目大意：
让你求一个区间的平衡数有多少个。平衡数：能找到一个对称轴，使两边的数平衡，例如：4139

以3为对称轴，左边：4 * 2+1 * 1=9， 右边：9 * 1=9， 左右相等，那么这个数平衡。

思路：直接枚举一下对称轴，然后数位dp。在不同的对称轴下0都是平衡数。其他数最多只能有一个对称轴。所以slove要减去在不同对称轴下多计算的0的个数。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL a[20];
LL dp[20][20][2000];

LL dfs(int pos, int s, int k, int mt)//s:左边-右边的值 k:对称轴
{
    if(pos<k&&s<0)//可行性剪枝
    {
        return 0;
    }

    if(pos==-1)
    {
        if(s==0)//满足条件
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }

    if(!mt&&dp[k][pos][s]!=-1)
    {
        return dp[k][pos][s];
    }

    int Len=mt?a[pos]:9;
    LL ans=0;
    for(int i=0;i<=Len;i++)
    {
        if(pos>k)
        {
            ans+=dfs(pos-1, s+i*(pos-k), k, mt&&i==a[pos]);
        }
        if(pos<k)
        {
            ans+=dfs(pos-1, s-i*(k-pos), k, mt&&i==a[pos]);
        }
        if(pos==k)
        {
            ans+=dfs(pos-1, s, k, mt&&i==a[pos]);
        }
    }

    if(!mt)
    {
        dp[k][pos][s]=ans;
    }

    return ans;
}

LL slove(LL x)
{
    if(x<0)
    {
        return 0;
    }
    LL pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    LL ans=0;
    for(int i=0;i<=pos-1;i++)
    {
        ans+=dfs(pos-1, 0, i, true);
    }

    return ans-pos+1;//减去多于的0
}

int main()
{
    LL T, CUT=1;
    memset(dp, -1, sizeof(dp));
    scanf("%lld",&T);
    while(T--)
    {
        LL L, R;
        scanf("%lld%lld",&L,&R);
        printf("%lld\n",slove(R)-slove(L-1));
    }

    return 0;
}