思路是这样的：

求出当前位置及更高位填好后，对应的数字个数

然后用当前位置填的数字乘上这个个数就是当前位置填这个数字的贡献

记忆化记忆当前位置所有可能的填数方案的贡献和，和更高位已经填好，当前位以及低位随便填满足约束的数字个数

函数返回值是个数，贡献用一个全局变量来存储

样例过了，但全WA

自己测了一组100 1000

发现算少了，答案一万两千多，我的程序输出是八千几

没有看到过题解里有类似的做法

是思路假了吗

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define int long long
#define ls (x<<1)
#define rs ((x<<1)|1)
#define mid ((l+r)>>1)
#define pc(x) putchar(x)

using namespace std;

const int N=30,mod=1e9+7;

int nw[N];

int f[N];
int g[N];
int ans;

int dp(int x,bool limit)
{
	if(x<=0)
		return 1;
	if(!limit&&f[x]>=0)
	{
		ans=(ans+g[x])%mod;
		return f[x];
	}
	int cnt=0,sum=0;
	for(int i=0;i<=(limit?nw[x]:9);i++)
	{
		int tmp=dp(x-1,limit&&i==nw[x]);
		cnt+=tmp,sum+=tmp*i;
		sum%=mod;cnt%=mod;
	}
	ans+=sum;
	ans%=mod;
	if(limit)
		return cnt;
	else
	{
		g[x]=sum;
		return f[x]=cnt;
	}
}

int solve(int x)
{
	memset(f,-1,sizeof(f));
	memset(g,-1,sizeof(g));
	int cnt=0;
	while(x)
		nw[++cnt]=x%10,x/=10;
	ans=0;
	dp(cnt,1);
	return ans;
}

signed main()
{
	int t;
	scanf("%lld",&t);
	while(t--)
	{
		int l,r;
		scanf("%lld%lld",&l,&r);
		printf("%lld\n",((solve(r)-solve(l-1))%mod+mod)%mod);
	}
	return 0;
}