注意取模可能会产生负数
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=250,mod=1e9+7;
LL f[106][200];//长度为i时,前pos-1项的和为j的合法数
string s;
//pos位置,sum==mark,limit限制,isnum是否存在数字
LL dfs(int pos,LL sum,bool limit,bool isnum){
int up=limit?s[pos]-'0':9;//如果有限制那么最多只能枚举到该位置,否则会超出n的范围
if(pos==(int)s.size()){//到达终点
return sum%mod;
}
if(isnum&&!limit&&f[pos][sum]!=-1) return f[pos][sum];//记忆化
LL res=0;
//只有前面都为前导0才可以
if(!isnum) res=dfs(pos+1,0,false,false);//跳过,注意边界
for(int i=1-isnum;i<=up;i++){//范围,以及起始边界
res=(res+dfs(pos+1,sum+i,i==up&&limit,true))%mod;//每一个位置的合法数都要枚举
}
if(isnum&&!limit) f[pos][sum]=res;//如果存在数,且在合法范围内,记忆化
return res;
}
LL work(LL n){
memset(f,-1,sizeof f);
s=to_string(n);
LL ans=dfs(0,0,true,false);
return ans;
}
void bu_f(){
LL a,b;
cin>>a>>b;
cout<<((work(b)-work(a-1))%mod+mod)%mod<<'\n';//注意负数
}
int main()
{
int t;
cin>>t;
while(t--){
bu_f();
}
return 0;
}