description
题意简述：令\(f(x)\)为\(x\)的各位数字之和，求：
\[\sum_{i=1}^{R}[f(x)=f(kx)]
\]
其中\(R\le 10^{18}\)，\(k< 1000\)
solution
遇到跟数字和相关的问题，自然想到数位\(DP\)
为了处理\(kx\)进位的问题，我们从低位到高位考虑并维护目前\(kx\)向前一位进了多少：
考虑\(dp\)状态\(dp[i][j][h][lim]\)，表示已经考虑到了从低到高第\(i\)位，前\(i\)位中\(f(x)\)与\(f(kx)\)的差为\(j\)（为避免负数问题，实际表示的是\(f(x)=f(kx)+j-200\))，目前\(kx\)向前\(1\)位进了\(h\)，\(lim\)则是数位\(dp\)中经典的表示目前填的位置是否\(>R\),满足以上所有条件的\(x\)的个数
数字之和最大不超过\(200\)，因此\(j\)只用枚举到\(400\)，因为\(k<1000\)，所以进位不超过\(999\)。
转移就是直接枚举当前第\(i+1\)位选择的数\(x\)，则有
\[dp[i+1][j+x-(kx+h)\%10][(kx+j)/10][nlim]+=dp[i][j][h][lim]
\]
其中\(nlim\)满足：对于\(R\)的第\(i+1\)位\(a[i+1]\)，如果\(x>a[i+1]\)，则\(nlim=1\)，如果\(x<a[i+1]\)，则\(nlim=0\)，否则\(nlim=lim\)
那么直接枚举转移即可，初始状态为\(dp[0][200][0][0]=1\)
注意有可能填到\(R\)的最高位时还有一些进位没有处理，因此我们可以认为\(R\)多出了三位\(0\)来将进位处理完
而\(ans=\)
\[dp[len][200][0][0]-1
\]
\(-1\)是为了除去\(0\)，\(len\)就是\(R\)的位数\(+3\)
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll r,t,f[30][400][1010][2];
ll a[50],len;
int main(){
scanf("%lld%lld",&r,&t);
ll p=r;
while(p){
a[++len]=p%10;
p/=10;
}
len+=3;
f[0][200][0][0]=1;
for(int i=0;i<len;++i){
for(int j=0;j<=400;++j){
for(int k=0;k<=999;++k){
for(int lim=0;lim<=1;++lim){
if(!f[i][j][k][lim]) continue;
for(int x=0;x<10;++x){
int nr=(x*t+k)/10,nx=(x*t+k)%10;
int nlim=lim;
if(x>a[i+1]) nlim=1;
if(x<a[i+1]) nlim=0;
f[i+1][j+x-nx][nr][nlim]+=f[i][j][k][lim];
}
}
}
}
}
printf("%lld\n",f[len][200][0][0]-1);
return 0;
}