强烈吐槽一下，没搞清楚状态方程以前不要写代码。。。
强烈吐槽一下，大学以前实视至珍宝的逐步调试效率果然太低了！，输出中间过程才是王道。
题意：输出x,y；求[x,y]中有多少个数是平衡的。4139是平衡的，因为 4*2+3*1=9*1.即支点左右的数乘以力臂（力矩为0）平衡。
f[i][j][k]表示长度为i的数（最高位可以为0），支点在第j位，目前已知平衡因子已经达到了k，有多少个平衡树。
f[i][j][k]=Σ（f[i-1][j][ k+(i-j)*p] ） （0<=p<=9）
f[0][j][0]=1;
f[0][j][!0]=0;
fi][j][k]=0 (k<0)
然后求0~(x-1)有多少个平衡树。
老套路，从高位依次枚举x中第i位的数可能。
ans+=dp(i-1,k,leftsum);
leftsum表示已经确定的平衡因子。
#include <stdio.h> #include <string.h> #define ll long long ll f[20][20][2000]; ll dp(int i,int j,int k) { if (k<0) return 0; if (f[i][j][k]!=-1) { return f[i][j][k]; } if (i==0) { if (k==0) return f[i][j][k]=1; else return f[i][j][k]=0; } ll ans=0; for (int p=0; p<=9; p++){ ans+=dp(i-1,j, k+(i-j)*p); } return f[i][j][k]=ans; } ll sov(long long x) { x++; if (x==0) return 0; int len=0; int digit[100]; while (x>0) { digit[++len]=x%10; x/=10; } long long ans=0; int leftsum=0; for (int i=len; i>=1; i--) { for (int j=0; j<digit[i]; j++) { for (int k=1; k<=len; k++) { leftsum=0; for (int p=len; p>i; p--) { leftsum+=(p-k)*digit[p]; } leftsum+=(i-k)*j; ans+=dp(i-1,k,leftsum); } } } return ans-len+1; } int main() { // freopen("t.in","r",stdin); // freopen("t.out","w",stdout); int t; long long x,y; memset(f,-1,sizeof(f)); int i,j,m,n; scanf("%d",&t); f[1][1][0]=10; while (t--) { scanf("%I64d%I64d",&x,&y); printf("%I64d ",sov(y)-sov(x-1)); } return 0; }