看起来就像是数位\(\rm dp\)

不妨从竖式乘法的角度来考虑这个问题

为了方便处理进位，我们得从低位向高位填数

设\(dp[i][0/1][j][p][t]\)表示填到了第\(i\)位，卡不卡上界，\(f(x)=j\)，\(f(k\times x)=p\)（不计算最高位），需要向最高位进\(t\)的\(x\)有多少个

这里的卡上界比较奇怪，如果这一位上填的数大于\(R\)这一位上的数，那么就一定卡了上界，如果小于这一位上的数，那么就一定不卡上界，如果和原来的数相等，那么就继续之前的状态

所以这个\(0/1\)就表示后面的\(i\)为和\(R\)后\(i\)位的大小关系，如果填的数大于\(R\)后\(i\)为，那么这个状态就是\(1\)；否则就是\(0\)

至于转移，就比较简单，我们枚举这一位上填什么数\(y\)，那么对于\(x\)，数位和增加了\(y\)，对于\(k\times x\)，这一位上直接来一个乘法是\(k\times y\)，还有之前的进位\(t\)，于是就是\((k\times y+t)\% 10\)，新的进位就是\((k\times y+t)/10\)

但是这样我们填到\(R\)的最高位之后可能还有一些进位没有处理，于是再往前多处理\(3\)位把进位处理完

最后的答案就是\(\sum_{i}dp[\lg_{R}][0][i][i][0]\)，即\(x\)的数位和等于\(f(k\times x)\)的情况，但是这样多了一维非常难受，考虑的最后只要求\(j=p\)，所以我们直接把\(j-p\)看成一维状态就好了

代码

#include
    
     #define re register#define LL long longLL dp[25][2][1000][500];int m,w,a[25],M=250;LL n;inline void split(LL x) {    while(x) a[++w]=(x%10),x/=10;}int main() {    scanf("%lld%d",&n,&m);    dp[0][0][0][M]=1;    split(n);    for(re int i=0;i
     
      a[i+1]][(k+t*m)/10][p+t-(k+t*m)%10]+=dp[i][j][k][p];                }     printf("%lld\n",dp[w+3][0][0][M]-1);    return 0;}