Description
求 \([L,R] (R \le 10^{5000})\) 间满足 \(x=f(x) \bmod m (m \le 60)\) 的数量。
Solution
数位 dp,设 \(f[pos][sum][delta]\) 表示从低到高 \(pos\) 位,数位和为 \(sum\),\(f(x)-x \bmod m\) 为 \(delta\) 的方案数量为多少
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
const int M = 65;
const long long mod = 1e9+7;
int f[N][M][M],a[N],p[N],m;
// lim=1 表示当前贴合上界,lim=0 则不贴合
long long dfs(int pos,int sum,int delta,int lim)
{
if(pos==-1)
{
return delta==0;
}
if(lim==0 && f[pos][sum][delta]!=-1)
{
return f[pos][sum][delta];
}
else
{
long long ans=0;
for(int i=0;i<=(lim?a[pos]:9);i++)
{
ans += dfs(pos-1, (sum+i)%m, ((delta+sum*i-i*p[pos])%m+m)%m, i==(lim?a[pos]:9)&&lim);
}
ans=(ans%mod+mod)%mod;
if(lim==0) // 不贴合上界的情况有可能会被复用
{
f[pos][sum][delta]=ans;
}
return ans;
}
}
long long solve(string s)
{
int n=s.length();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
for(int k=0;k<m;k++)
{
f[i][j][k]=-1;
}
}
}
for(int i=0;i<n;i++)
{
a[i]=s[n-1-i]-'0';
}
return dfs(n-1,0,0,1);
}
signed main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
string l,r;
cin>>l>>r>>m;
p[0]=1;
for(int i=1;i<=r.length();i++)
{
p[i]=p[i-1]*10%m;
}
l[l.length()-1]--;
for(int i=l.length()-1;i>=0;--i)
{
if(l[i]<'0')
{
l[i]+=10;
l[i-1]--;
}
else
{
break;
}
}
cout<<((solve(r)-solve(l))%mod+mod)%mod<<endl;
}
//system("pause");
}