非負整数 \(N\) の奇数番目の桁の数字の合計と偶数番目の桁の数字の合計の差を \(g(N)\) とします。

\(f(N,D)\) を「\(N\) 以下の非負整数で \(g(n)=D\) を満たす \(n\) の個数」とします。求める値は \(\displaystyle \sum_{x=-D}^D f(N,x)-1\) です。

\(f(N,D)\) が満たす漸化式を考えます。

\(N<0\) のとき \(f(N,D)=0\) です。

また、\(N=0\) のとき \(f(N,D)\) は \(D=0\) なら \(1\) 、\(D\neq 0\) なら \(0\) です。

\(N>0\) のとき、\(N\) の \(1\) の位を場合分けして考えることで \(\displaystyle f(N,D)=\sum_{c=0}^9 f\left(\left\lfloor \frac{N-c}{10}\right\rfloor,c-D\right)\) が成り立つことが分かります。

あとはこの漸化式に基づいて \(\displaystyle \sum_{x=-D}^D f(N,x)-1\) の値を計算すれば良いです。メモ化再帰などで実装することで高速にこれらの値を求めることができます。

実装例(Python3)

from functools import cache

@cache
def f(n, d):
    if n < 0:
        return 0
    if n == 0:
        return d == 0
    ans = 0
    for c in range(10):
        ans += f((n - c) // 10, c - d)
    return ans

n = int(input())
d = int(input())
ans = -1
for i in range(-d, d + 1):
    ans += f(n, i)
print(ans)