Bài toán dữ liệu lớn (FNUMBER)

[Nobita004 (Kirito-kun)]

Số nguyên dương n được gọi là FNUMBER nếu n chia hết cho 3 nhưng không chia hết cho 9 và ở dạng biểu diễn thập phân của n không có 2 chữ số nào có tổng chia hết cho 5. VD 240 là một FNUMBER, 231 không là một FNUMBER.
Cho trước 2 số nguyên dương A,B. Đếm số lượng FNUMBER thuộc [A;B]. Do kết quả có thể rất lớn, chỉ cần in ra theo modun 10⁹+7.

Dữ liệu vào từ tệp FNUMBER.INP:

• Dòng 1 chứa số Q: số lượng testcase.
• Q dòng tiếp theo, mỗi dòng chứa 2 số A,B.

Dữ liệu xuất ra tệp FNUMBER.OUT:

• Gồm Q dòng là kết quả cho Q testcase.

FNUMBER.INP	FNUMBER.OUT
3 100 110 5 2345 0 100000	1 209 3616
1 0 1000000000000000000	698089379

Giới hạn:

• Subtask 1: Q ≤ 10⁶, 0 ≤ A ≤ B ≤ 10⁵
• Subtask 2: Q=1, 0 ≤ A ≤ B ≤ 10¹⁸
• Subtask 3: Q ≤ 100, 0 ≤ A ≤ B ≤ 10¹⁰⁰⁰⁰

Cho e hỏi thuật toán bài trên được không ạ vì em làm mãi nó vẫn cứ chạy quá thời gian. Em cảm ơn ạ! Em nghĩ nó có công thức nhưng nghĩ mãi cũng chẳng ra!

[catlord]

Ý tưởng của bạn đang làm là như thế nào mà bị TLE?

Kiểm tra 1 số chia hét cho 3 nhưng không chia hết cho 9. Các dấu hiệu chia hết hồi cấp 2.
Kiểm tra xem có tồn tại 2 cặp số (a, b) với a + b chia hết cho 5
Vì a và b chỉ là số có một chữ số. Dễ dàng lưu lại dạng bảng để tra.

[Nobita004 (Kirito-kun)]

Bạn nói rõ hơn được không? Dữ liệu ở đây tận đến 10^10000 sao có thể chạy hết được nếu kiểm tra như vậy ! Mình nghĩ có công thức nào đó mà chưa nghĩ ra. Mong bạn giúp đỡ ! Cảm ơn!

[catlord]

Bài này không phải đọc 1 số 10^10000
Mà đọc từng chữ số.
Có 2 yêu cầu, yêu cầu 1 thì chia hết cho 3 không chia hết cho 9 dùng dấu hiệu chia hết hồi c2 học.
Tổng các chữ số chia hết cho 3 = số chia hết cho 3
Tổng chia hết cho 9 = số đó chia hết cho 9.
-> Giải đc 1 yêu cầu

Ở yêu cầu 2, vì đòi (a + b) chia hết cho 5
Mà đề yêu cầu a, b chỉ là một chữ số trong số trên
-> a, b chỉ có thể là 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
-> a + b chỉ có vài trường hợp như (1 + 9), (1 + 4) ,…
-> Khi này bạn có thể lưu dạng bảng băm (hash table) để truy vấn cho nhanh
Để kiểm tra a + b có chia hết cho 5 không với mỗi chữ số a_i thì chỉ cần xem số b_i nào mà sao cho a_i + b_i chi hết cho 5. Ví dụ a_i = 1 -> kiếm xem trong số đó có chữ số nào = 4 hoặc 9 hay không. Vì ta lưu bằng bảng nên dễ dàng tìm ra.

[Nobita004 (Kirito-kun)]

Cảm ơn bạn. Nhưng bài toán bảo đếm số thì phải duyệt 1 vòng for hay có cách khác. Của bạn đó là kiểm tra 1 số. Khi kiểm tra để đếm số số thỏa mãn trong [A, B] thì làm sao ạ! Mình cảm ơn!

(Nếu chạy 1 vòng for thì cũng đến 10^8 là cùng)

[catlord]

Haiza, xin lỗi bạn nhiều mình đọc thiếu đề.

Để mình nghĩ thêm

[Nobita004 (Kirito-kun)]

Không sao! Đầu tiên mình cũng làm giống bạn nhưng cũng chẳng ăn thua gì?

[catlord]

Đây nè, mình nghĩ ra một ý nè. Không cần loop gì luôn.

Bạn có A và B
Tìm số X gần A nhất sao cho X chia hết cho 3.
Tìm số Y gần B nhất sao cho Y chia hết cho 3.
-> Từ đó ta tính đc có bao nhiêu số chia hết cho 3 trong đoạn [X, Y] (công thức dãy số)
Ta biết cứ mỗi 2 số chia hết cho 3, thì số thứ 3 chia hết cho 9. -> Tính đc số chia hết cho 3 nhưng không chia hết cho 9

---

Tiếp theo là so sánh 2 số A và B
nếu A và B cùng chiều dài, thì tìm phần chung từ hàng cao nhất của A và B

Như A = 12300, B = 12310
-> phần chung là 123
Vì ta biết 2 + 5 = 5 -> số trong đoạn [A, B] sẽ 100% không thể thõa tính chất thứ 2
-> Lúc này in ra 0

Còn 2 trường hợp còn lại thì mình đang nghĩ công thức.

EDIT: Lại nhầm đề

[noname00 (HK boy)]

Không biết bạn có biết những bài về quy hoạch động chữ số (dynamic programming on digits / Digit DP) không. Nếu chưa thì bạn có thể bắt đầu với 1 số bài đơn giản trước.

Digit DP | Introduction - GeeksforGeeks

https://codeforces.com/blog/entry/53960

Đây là 1 bài Digit DP rất khó, đòi hỏi bạn phải cố gắng thu hẹp các khả năng có thể để ép độ phức tạp xuống O(Q * độ dài xâu B), nếu không thì không còn cách nào để làm bài này nữa.

---

P/s: Cho mình xin link submit :3