https://codeforces.com/contest/1513/problem/C
시간 2초, 메모리 256MB

input :

• t (1 ≤ t ≤ 2⋅104)
• n t (1 ≤ n ≤ 109)(1 ≤ t ≤ 2⋅105)

output :

• For each test case output the length of the resulting number modulo 109 + 7.
  각 테스트 케이스의 결과를 109 + 7로 얻은 나머지를 출력하시오.

조건 :

• You are given an integer n. You have to apply m operations to it.
  숫자 n을 입력받고, m번의 연산을 수행해야 합니다.

• 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.
  한 번의 연산에서 모든 숫자 d 에다가 1을 더합니다. 1912의 경우 21023이 됩니다.

---

각 숫자들을 따로 뽑아내서 횟수 자체를 곱해버리면 안 되나 싶었지만 그 수가 9였을 때 10이 되고 10에 연산을 계속 하면 109 또 계속하면 2110 이렇게 계속 커지게 된다.

그래서 수의 크기 자체가 매우 커지기 때문에 건드릴 수 없다.

기록

그렇다. 기록을 해야 한다.
그 기록도 연산이 몇 번 수행 했을 때 가지고 있는 길이가 어떨지를 저장하도록 한다.
가지고 있을 수 있는 숫자는 0 ~ 9 까지이고 실행하는 연산의 횟수는 2 * 10^5 만큼이다.
그러면 연산 횟수를 생각해보자.

맨 처음 모든 숫자들은 다 길이가 1로 유지 되어있다.
여기에 추가적으로 계속 업데이트를 해보자.
연산을 1번 했을 때는 9가 10으로 바뀌는데 이 10의 길이가 어떤지는 모른다. 그 연산 횟수를 할 때 까지 1의 길이가 어떨지 0의 길이가 어떻게 바뀌었을 지 이를 또 따져야 한다.

9가 10으로 바뀌고 그 다음 바뀔 때는 109 그 다음에는 2110으로 바뀐다 이와 같이 10으로 바뀔 때 1이 10으로 바뀐 전적이 있다면 길이가 2가 되는 거고 0이 10 으로 바뀐 전적이 있다면 길이가 2가 되는 것이다.
이를 계속 누적해서 값을 구하자.
0 1 1 1 ... 2 ...
1 1 1 1 ... 2 ...
2 1 1 1 ... 2 ...
3 1 1 1 ... 2 ...
4 1 1 1 ... 2 ...
5 1 1 1 ... 2 ...
6 1 1 1 ... 2 ...
7 1 1 1 ... 2 ...
8 1 1 2 ... 2 ...
9 1 2 2 ... 3 ...

그래서 dp를 구성한 다음에 정답을 구할 때는 각 숫자에다가 연산을 한 결과값을 dp에서 꺼낸 다음에 그 값을 통해 나머지를 계속 누적하면서 값을 구한다.

import sys

dp = [[1] for i in range(10)]
for operation in range(1, 2 * 10 ** 5 + 1):
    for digit in range(10):
        if digit < 9:
            dp[digit].append(dp[digit + 1][operation - 1])
        else:
            dp[digit].append((dp[0][operation - 1] + dp[1][operation - 1]) % (10 ** 9 + 7))

t = int(sys.stdin.readline())
for _ in range(t):
    n, k = map(int, sys.stdin.readline().split())

    ans = 0
    while n:
        ans += dp[n % 10][k]
        n //= 10
        ans %= (10 ** 9 + 7)

    print(ans)

맨 처음 dp를 구할 때 2 * 10 ** 5 + 1 까지 반복문을 수행해야 모든 경우를 계산 해 둘 수 있다.
위의 글을 점화식으로 바꿔서 반복문을 돌린다.