VOI 19 Bài 3 - Số siêu đối xứng

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Lưu ý: Đọc input, output từ stdin/stdout

Một dãy các chữ số từ ~0~ đến ~9~ được gọi là dãy đối xứng nếu như đọc từ trái sang phải hay từ phải sang trái đều thu được kết quả giống nhau. Ví dụ như dãy rỗng và hai dãy ~010~, ~0110~ là các dãy đối xứng, còn các dãy ~123~, ~4449~ không phải là dãy đối xứng.

Với dãy ~S~ độ dài ~k~, các kí tự được đánh số từ ~1~ đến ~k~. Kí hiệu một dãy con của ~S~ gồm các kí tự liên tiếp từ vị trí ~a~ đến vị trí ~b~ là ~S(a, b)~ (giả thiết nếu ~a>b~ thì ~S(a, b)~ là dãy rỗng), dãy ~S~ được định nghĩa là dãy siêu đối xứng nếu đồng thời thỏa mãn các điều kiện sau:

  • ~S(1, k)~ là dãy đối xứng;
  • ~S(1, \left \lfloor k/2 \right \rfloor)~ là dãy đối xứng, trong đó kí hiệu ~\left \lfloor x \right \rfloor~ là số nguyên lớn nhất không vượt quá ~x~;
  • ~S(k - \left \lfloor k/2 \right \rfloor + 1, k)~ là dãy đối xứng.

Ví dụ các dãy ~0~, ~11~, ~22322~, ~454454~ là các dãy siêu đối xứng, còn dãy ~990099~ không phải là dãy siêu đối xứng.

Một dãy được gọi là gần siêu đối xứng nếu như tồn tại một cách hoán đổi vị trí các phần tử của nó để thu được một dãy siêu đối xứng. Đương nhiên, một dãy siêu đối xứng cũng đồng thời là một dãy gần siêu đối xứng.

Một số nguyên dương ~d~ được gọi là số gần siêu đối xứng nếu như coi biểu diễn thập phân của nó như một dãy các chữ số từ ~0~ đến ~9~ (không có trường hợp dãy bắt đầu bởi chữ số ~0~) thì dãy biểu diễn đó là một dãy gần siêu đối xứng. Lưu ý là sau khi hoán đổi vị trí các phần tử, dãy thu được có thể bắt đầu bởi chữ số ~0~. Ví dụ, ~d=9505000~ là số gần siêu đối xứng vì tồn tại một cách hoán đổi vị trí các phần tử của dãy các chữ số biểu diễn d thành một dãy siêu đối xứng ~0509050~.

Yêu cầu: Cho hai số nguyên dương ~p~ và ~q~ ~(p \leq q)~, hãy tìm số lượng các số nguyên gần siêu đối xứng nằm trong khoảng từ ~p~ đến ~q~ (khoảng bao gồm cả ~p~ và ~q~).

Input

Hai số nguyên ~p~ và ~q~ cách nhau bởi dấu cách.

Output

In ra duy nhất một số là phần dư của số lượng số gần siêu đối xứng tìm được trong phép chia cho ~10^9+7~.

Scoring

  • Có ~20\%~ số lượng test ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~1 \leq p \leq q \leq 10^5~;
  • ~30\%~ số lượng test khác ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~p=10^{k-1}~, ~q=10^k-1~, ~2 \leq k \leq 18~;
  • ~30\%~ số lượng test khác ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~1 \leq p \leq q \leq 10^{18}~;
  • ~20\%~ số lượng test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~1 \leq p \leq q \leq 10^{50000}~.

Sample Input 1

1 100

Sample Output 1

19

Sample Input 2

3111120 3111125 

Sample Output 2

2

Giải thích

  • Ở ví dụ thứ nhất, các số gần siêu đối xứng là ~1~, ~2~, ~3~, ~4~, ~5~, ~6~, ~7~, ~8~, ~9~, ~11~, ~22~, ~33~, ~44~, ~55~, ~66~, ~77~, ~88~, ~99~, ~100~.
  • Ở ví dụ thứ hai, hai số gần siêu đối xứng là ~3111122~ và ~3111123~.

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.



  • -5
    duyanh   commented on Jan. 20, 2022, 3:29 p.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -7
    ProTeam15   commented on Jan. 18, 2022, 10:16 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -7
    HuyNhay   commented on Jan. 18, 2022, 4:44 p.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -8
    CaiWinDao   commented on Jan. 18, 2022, 4:01 p.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -1
    ndpqx   commented on Sept. 18, 2021, 10:49 a.m.

    Hình như test bài này có vấn đề đúng không ạ?


  • -3
    ankhang277   commented on Sept. 18, 2021, 10:37 a.m.

    Test sub 2 sai ad ơi.