题目链接
看起来似乎是很裸的数位dp
不难想到我们需要维护一个数位前缀和
s
u
m
n
sumn
sumn用于计算
f
(
x
)
f(x)
f(x)
我们还需要记录当前枚举值
f
(
x
)
%
m
f(x)\%m
f(x)%m的值
我们还需要记录
x
%
m
x\%m
x%m的值
但是这样复杂度超标
我们发现可以直接维护
f
(
x
)
−
x
f(x)-x
f(x)−x的值,因为模数相同
如果第
l
e
n
len
len位选择的是
i
i
i
由
于
我
们
维
护
了
l
e
n
−
1
位
时
的
f
(
x
)
−
x
由于我们维护了len-1位时的f(x)-x
由于我们维护了len−1位时的f(x)−x
那
么
此
时
转
移
就
是
(
f
(
x
)
+
s
u
m
n
∗
i
)
−
(
x
+
i
∗
1
0
l
e
n
)
那么此时转移就是(f(x)+sumn*i)-(x+i*10^{len})
那么此时转移就是(f(x)+sumn∗i)−(x+i∗10len)
这样优化掉一维度,就可以了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=3e5+10;
char l[maxn],r[maxn];
ll dp[5009][75][75];
int ppow[5009],a[5009],en,n,m;
int dfs(int len,int limit,int nowmod,int sumn)
{
//nowmod是当前数对m的和,he是前缀和,
if( len==0 ) return !nowmod;
if( !limit&&dp[len][nowmod][sumn]!=-1 )
return dp[len][nowmod][sumn];
ll last=limit?a[len]:9,ans=0;
for(int i=0;i<=last;i++)
{
int fx=nowmod+sumn*i-i*ppow[len-1]+m;
ans+=dfs(len-1,limit&&(i==a[len]),(fx%m+m)%m,(sumn+i)%m);
}
ans=(ans%mod+mod)%mod;
if( !limit ) dp[len][nowmod][sumn]=ans;
return ans;
}
int solve(char b[])
{
en=strlen(b+1);
for(int i=0;i<=en;i++)
for(int j=0;j<m;j++)
for(int q=0;q<m;q++)
dp[i][j][q]=-1;
for(int i=1;i<=en;i++)
a[i]=b[en-i+1]-'0';
return dfs(en,1,0,0);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ppow[0]=1;
int t; cin >> t;
while( t-- )
{
cin >> (l+1) >> (r+1);
cin >> m;
int rr=strlen(r+1);
for(int i=1;i<=rr;i++) ppow[i]=ppow[i-1]*10%m;
int en=strlen(l+1);
l[en]--;
for(int i=en;i>=1;i--)
if( l[i]<'0' ) l[i]+=10,l[i-1]--;
else break;
cout << ( solve(r)-solve(l)+mod )%mod << '\n';
}
}
本文地址：https://blog.csdn.net/jziwjxjd/article/details/108567471
