この問題は桁DPにより解くことができます。

下の桁から決めていく桁DPを考えます。

\(\mathrm{dp}_X[i][\mathrm{leq}][\mathrm{pre}][k]\) を、以下の条件を全て満たす長さ \(i\) の数字列 \(S\) の個数とします。

• \(S\) を整数と解釈したとき、\(X \bmod 10^i\) 以下なら \(\mathrm{leq}\) は True、そうでないなら False である
• \(S\) の先頭の文字は \(\mathrm{pre}\) である
• \(S\) の leading zero を含めた揺れ値は \(k\) である

求める答えは、\(N\) の桁数を \(n\) として

\(\sum\mathrm{dp}_N[< n][*][\neq 0][K]+\sum \mathrm{dp}_N[n][\mathrm{True}][\neq 0][K]\)

となります。DPの遷移は、\(S\) の先頭に追加する文字の種類を全て試せばよいです。

基数を \(B\) として、計算量は \(O(KB^2 \log_B N)\) になります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  long long n, k;
  cin >> n >> k;

  vector<int>nn;
  while(n){
    nn.push_back(n%10);
    n /= 10;
  }

  map<array<int,3>, long long> dp;
  for(int d=0; d<10; d++){
    dp[{d<=nn[0], d, 0}] = 1;
  }

  long long ans = 0;
  for(int i=1; i<nn.size(); i++){
    int c = nn[i];
    map<array<int,3>, long long> new_dp;
    for(auto [key, val]: dp){
      auto [leq, pre, s] = key;
      if(s == k && pre != 0){
        ans += val;
      }
      for(int d=0; d<10; d++){
        array<int, 3> new_key = {d<c || (d==c && leq), d, s+abs(d-pre)};
        new_dp[new_key] += val;
      }
    }
    swap(dp, new_dp);
  }

  for(auto [key, val]: dp){
    auto [leq, pre, s] = key;
    if(s == k && pre != 0 && leq){
        ans += val;
    }
  }

  cout << ans << endl;
}

実装例 (Python)

from collections import defaultdict

N, K = input().split()
K = int(K)
dp = defaultdict(int)

for d in range(10):
  dp[(d<=int(N[-1]), d, 0)] = 1

ans = 0
for i in range(len(N)-2, -1, -1):
  c = int(N[i])
  new_dp = defaultdict(int)
  for (leq, pre, s), val in dp.items():
    if s == K and pre != 0:
      ans += val
    for d in range(10):
      new_key = (d<c or (d==c and leq), d, s+abs(d-pre))
      new_dp[new_key] += val
  dp = new_dp

for (leq, pre, s), val in dp.items():
  if s == K and pre != 0 and leq:
    ans += val

print(ans)