(ACM/ICPC 2020) Đếm số Palindrome

线程:
Số palindromic là một số giống nhau khi viết về phía xuôi hoặc
ngược. Do đó, một vài số palindromic đầu tiên là 1, 2, 3, 4, 5, 6, 7, 8, 9, 11,
22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, ... (quy tắc 1).
Trong một số trường hợp đặc biệt, 0012100, 00 là một số palindromic. Do đó, 12100, 1210, 00
cũng là một số palindromic (quy tắc 2).

Chúng ta có thể phân loại số nguyên dương thành ba loại:
Loại 0: các số không phải số palindromic.
Loại 1: số palindromic theo quy tắc 1.
Loại 2: số palindromic theo quy tắc 2.

Tất cả các palindrome nhỏ hơn hoặc bằng 100 là: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 20, 22, 30,
33, 40, 44, 50, 55, 60, 66, 70, 77, 80, 88, 90, 99, 100.

Cho số M là số nguyên không âm. Hàm F (M) trả về số
palindromes (gồm 2 loại: loại 1 và loại 2) nhỏ hơn hoặc bằng M (0 ≤ M ≤ 10^35).

M 0 15 39 55 60 85 88 90 100
F(M) 1 12 16 20 21 25 26 27 29

Để đơn giản hóa vấn đề, cho trước một số N là số nguyên không âm, hàm P (ñ) trả về

giá trị của F (10^N) (0 ≤ N ≤ 35).
ñ 0 1 2 3 4 ... 15 ... 35
P(ñ) 2 11 29 137 335 ... 144,444,413 ... 1,444,444,444,444,444,373

输入: Trên dòng đầu tiên là số lượng test, 1 ≤ T ≤ 36.
Trong T dòng tiếp theo, mỗi dòng chứa một số nguyên Ni không âm (1 ≤ Ni ≤ T, 0 ≤ Ni ≤ 35).
产量: Kết quả có T dòng, dòng thứ i ghi giá trị của P (Ni) (1 ≤ i ≤ T).
例子:

输入:
5
4
7
35
20
15
产量:
335
14429
1444444444444444373
34444444403
144444413

输入:
3
1
8
10
产量:
11
34427
344423

输入:
5
30
2
3
33
25
产量:
3444444444444383
29
137
144444444444444377
14444444444393

您还没有登录? 注册 到现在提交!