Junior Mathematician

题目链接：Junior Mathematician

---

不难想到可以数位dp去做。

但是直接令状态为前 i 位，当前数位和为 j ，数字值为 k ，f(x)的值为 l 的个数复杂度过高。我们可以发现数字值和 f(x)的值可以一起计算，然后减少一维状态即可。

---

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5010,mod=1e9+7;
int n,dp[N][70][70],m,a[N],cnt,pw[N]; char l[N],r[N];
int dfs(int pos,int s1,int s2,int lim){
	if(pos==cnt+1) return s1==0;
	if(dp[pos][s1][s2]!=-1&&!lim) return dp[pos][s1][s2];
	int up=lim?a[pos]:9,res=0;
	for(int i=0;i<=up;i++){
		res=(res+dfs(pos+1,((s1+s2*i-i*pw[cnt-pos])%m+m)%m,
			(s2+i)%m,lim&&i==up))%mod;
	}
	if(!lim) dp[pos][s1][s2]=res;
	return res;
}
int calc(char *str,int len){
	cnt=len;
	for(int i=0;i<=cnt;i++) 
		for(int j=0;j<=m;j++) 
			for(int k=0;k<=m;k++)
				dp[i][j][k]=-1;
	for(int i=1;i<=len;i++) a[i]=str[i]-'0';
	return dfs(a[1]==0?2:1,0,0,1);
}
void solve(){
	scanf("%s %s %d",l+1,r+1,&m);
	int ll=strlen(l+1),lr=strlen(r+1);
	l[ll]--,pw[0]=1;
	for(int i=1;i<=lr;i++) pw[i]=pw[i-1]*10%m;
	for(int i=ll;i>=1;i--){
		if(l[i]<'0'){
			l[i]='9',l[i-1]--;
		}else break;
	}
	cout<<(calc(r,lr)-calc(l,ll)+mod)%mod<<endl;
}
signed main(){
	int T; cin>>T; while(T--) solve();
	return 0;
}