Giả sử ta chia $x$ làm 2 phần $a_{x,k}/b_{x,k}$ với $b_{x,k}$ là $k$ chữ số cuối của $x$

Ta sẽ tìm giá trị $k$ an toàn sao cho $a_{x+f(x),k}-a_{x,k}\le 1$. Theo như dữ liệu đề bài cho thì $k$ nhỏ nhất có thể bằng $3$

Ta coi như $x$ là 1 số có $n$ chữ số, với chữ số thứ $i$ là $x_i$

Ta sẽ thực hiện tiền xử lý, sau đó sẽ lấy kết quả bằng cách đếm số cách điền chữ số thỏa mãn. Cụ thể ta sẽ điền theo cách:

• Đếm số có dạng $d???\dots???$ ($0\le d<x_1$)
• Đếm số có dạng $x_1d???\dots???$ ($0\le d<x_1$)
• $\dots$
• Đếm số có dạng $x_1x_2\dots x_{n-4}d???$ ($0\le d<x_{n-3}$)

Chú ý về việc khi chỉ còn điền ít hơn $3$ chữ số thì ta nên thực hiện brute forces

Nhận xét: Xét $i$ là vị trí $d$ mà ta đang xét theo ý tưởng như trên, với cách điền đó, ta thấy $d$ luôn nhỏ hơn $9$ $\rightarrow$ $0\le a_{x+f(x),n-i}-a_{x,n-i}\le 1$

Từ nhận xét, ta có thể gọi $dp[i][j]$ là số giá trị $x$ thỏa mãn với $i$ là số chữ số cuối cần điền, $j$ là tổng chữ số phần đầu ($3\le i\le 18$)

Ta cũng gọi $cnt[i][a][b][k][check]$ là số lượng số $x$ có tối đa $i$ chữ số sao cho $f(x)=a, f(x+9k\ mod\ 10^i)=b$ và $check$ là kiểm tra xem $x+9k\ge 10^i$ không ($3\le i\le 18$)

Công thức với mảng $cnt$:

• $i=3$: brute tất cả các giá trị $0\le j<1000,1\le k\le 18$ và tăng $cnt[i][f(j)][f(j+9k)\ mod\ 1000][k][f(j+9k)\ge 1000]$
• $i>3$: Dựa vào ý tưởng điền chữ số từ bên trái là $v$ từ $0\rightarrow 9$, ta có công thức:
  • $check=0$: tăng $cnt[i][a+v][b+v][k][0]$ lên $cnt[i-1][a][b][k][0]$
  • $check=1$: Trường hợp $v=9$, tăng $cnt[i][a+v][b][k][1]$ lên $cnt[i-1][a][b][k][1]$, ngược lại tăng $cnt[i][a+v][b+v+1][k][0]$ lên $cnt[i-1][a][b][k][1]$

Dựa vào mảng $cnt$, ta có công thức $dp$ như sau: $dp[i][k\times 9-a]+=cnt[i][a][a-check][k][check]$ khi $a-check\ge 0$

Cuối cùng, ta thực hiện đếm số giá trị thỏa mãn dựa vào ý tưởng và công thức $dp$ đã nói ở trên. Độ phức tạp: $O(f(x)+(x\ mod\ 1000))$ với $x$ là số đang xét

Các bạn có thể cải tiến thuật toán trên, nhưng phần này mình xin nhường các bạn!