AcWing 1084. 数字游戏 II
原题链接
中等
作者:
wangyj
,
2021-01-21 09:35:08
,
所有人可见
,
阅读 288
#include <cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int P,f[11][10][110];
int mod(int x,int y){return (x%y+y)%y;}
int DP(int n)
{
if(!n)return 1;
vector<int>num;
while(n)num.push_back(n%10),n/=10;
int ans=0,end=0,i,x,j;
for(i=num.size()-1;i>=0;i--){
x=num[i];
for(j=0;j<x;j++)ans+=f[i+1][j][mod(-end,P)];
end+=x;
if(!i&&end%P==0)ans++;
}
return ans;
}
int main()
{
int l,r,i,j,k,x;
while(cin>>l>>r>>P){
memset(f,0,sizeof f);
for(i=0;i<=9;i++)f[1][i][i%P]++;
for(i=2;i<11;i++)for(j=0;j<=9;j++)for(k=0;k<P;k++)
for(x=0;x<=9;x++)f[i][j][k]+=f[i-1][x][mod(k-j,P)];
printf("%d\n",DP(r)-DP(l-1));
}
return 0;
}