Add One (Codeforces 1513C)
Tags: DP, matrices

You are given an integer $$$n$$$. You have to apply $$$m$$$ operations to it.In a single operation, you must replace every digit $$$d$$$ of the number with the decimal representation of integer $$$d + 1$$$. For example, $$$1912$$$ becomes $$$21023$$$ after applying the operation once.You have to find the length of $$$n$$$ after applying $$$m$$$ operations. Since the answer can be very large, print it modulo $$$10^9+7$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases.The only line of each test case contains two integers $$$n$$$ ($$$1 \le n \le 10^9$$$) and $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the initial number and the number of operations. 

Output: For each test case output the length of the resulting number modulo $$$10^9+7$$$.

Note: For the first test, $$$1912$$$ becomes $$$21023$$$ after $$$1$$$ operation which is of length $$$5$$$.For the second test, $$$5$$$ becomes $$$21$$$ after $$$6$$$ operations which is of length $$$2$$$.For the third test, $$$999$$$ becomes $$$101010$$$ after $$$1$$$ operation which is of length $$$6$$$.For the fourth test, $$$88$$$ becomes $$$1010$$$ after $$$2$$$ operations which is of length $$$4$$$.

Sample Inputs:
5
1912 1
5 6
999 1
88 2
12 100

Sample Outputs:
5
2
6
4
2115

Solution (Python):
M = 10 ** 9 + 7
L = 8 ** 6
d = [1] * L
d[:10] = [1] * 10
for i in range(10, L):
    d[i] = (d[i - 9] + d[i - 10]) % M
for s in [*open(0)][1:]:
    (n, m) = s.split()
    o = int(m)
    print(sum((d[o + int(c)] for c in n)) % M)

Solution (Python):
import sys, io, os, math
try:
    yash = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
    yash = lambda : sys.stdin.readline().encode()
I = lambda : [*map(int, yash().split())]
import __pypy__
an = __pypy__.builders.StringBuilder()
dp = [1, 2, 2, 2, 2, 2, 2, 2, 2, 2] + [None for i in range(2 * int(100000.0) + 50)]
mod = int(1000000000.0) + 7
for i in range(10, 2 * int(100000.0) + 50):
    dp[i] = (dp[i - 9] + dp[i - 10]) % mod
for t in range(I()[0]):
    (num, m) = I()
    tot = 0
    while num != 0:
        n = num % 10
        num //= 10
        oper = m - (9 - n)
        if oper < 0:
            tot += 1
            tot %= mod
        else:
            tot += dp[oper]
            tot %= mod
    an.append('%d\n' % tot)
os.write(1, an.build().encode())

Solution (Python):
from sys import stdin, stdout
import heapq
from collections import defaultdict
import math
import bisect
import io, os
import __pypy__
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
    t = int(input())
    MOD = 10 ** 9 + 7
    an = __pypy__.builders.StringBuilder()
    dp = [0] * (200000 + 15)
    for i in range(10):
        dp[i] = 1
    for i in range(10, 200015):
        dp[i] = (dp[i - 9] + dp[i - 10]) % MOD
    for _ in range(t):
        (n, m) = list(map(int, input().split()))
        ans = 0
        while n > 0:
            x = n % 10
            n = n // 10
            ans = (ans + dp[x + m]) % MOD
        an.append('%d\n' % ans)
    os.write(1, an.build().encode())
main()