Sao kê 2: Truy tìm

Tác giả:

Dạng bài

Điểm: 500 (p) Thời gian: 2.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Hôm nay, tôi sẽ kể cho các bạn \(1\) câu chuyện nghe tuy hơi bựa nhưng mà có thật về sự thành lập của LQDOJ:

Vào năm 2020-2021, một trình duyệt mới chuyên chia sẻ các ý tưởng về ra đề và code, và cũng là nơi để giao lưu học hỏi đã được tạo ra tên là LQDOJ. Trong những năm đầu thì LQDOJ đã rất thành công với hơn 1000 ý tưởng ra đề và hơn 500000 bài nộp(không chắc có đúng không). Nhưng theo các bạn nhớ có thì từ xa xưa đã có 1 ông vua nào đó đã chuyên đi chép code và một ông thì gáy hơi bị to trong bài https://lqdoj.edu.vn/problem/desksbd và để nối tiếp sự nghiệp thì vẫn có 1 tổ chức ở ẩn đã được tạo ra chuyên CHÉP CODE VÀ IF TEST. Từ đó, các admin đã bắt đầu vào công cuộc điều tra bằng cách sao kê rất nhiều bài submiss của các coder rồi sẽ phát hiện và AB tất cả bài nộp chép code và if test. Người ta gọi thời đại này là VƯỜN SAO KÊ. Trong đó, có 1 nhóm gồm 4 người đã góp phần rất nhiều vào việc giúp admin sao kê, họ được mệnh danh là TỨ HOÀNG [và tôi là 1 trong số đó(đùa thôi hehe)]. Các thành viên gồm: WuTan, vinhntndu, SPyofgame và hhoangcpascal. Họ cũng là những người đang trong công cuộc tìm ra kẻ đầu sỏ của tổ chức – là người đang giữ tài khoản huyền thoại ONE PIECE. Để tìm ra tài khoản huyền thoại đó thì họ phải vượt qua một số thử thách. VÀ ĐÂY CHÍNH LÀ PHẦN II: TRUY TÌM:

Vào ngày \(21/12/2021\), sau khi nhờ các bạn trên LQDOJ giải quyết vấn đề thì admin đã bắt được tất cả các tên tội phạm sừng sỏ trong tổ chức chép code, nhưng LQDOJ đã không may để lọt lưới tên nguy hiểm nhất là tên cầm đầu, như các bạn đã nhớ trong bài https://lqdoj.edu.vn/problem/desksbd thì vua nguyenminhhai021009 phải chống lại cả \(2\) vua là Nguyen_Le_Huy_Khanh và imbigbrain, vì đã tu tâm dưỡng tính nên Nguyen_Le_Huy_Khanh đã không bao giờ tái xuất giang hồ nữa nhưng imbigbrain vẫn nối tiếp sự nghiệp chép code và if test nên đã hưởng luôn tính cách chép code của mình rồi còn thêm cái tính gáy to của mình thì phải gọi là úi xời ơi. Sau đó imbigbrain lấy biệt danh là immoriaty(ý là đã chép code, if test công khai còn bày đặt bí mật đây mà, còn theo như trong truyện thì moriaty là kẻ thù truyền kiếp của Sherlock Holmes), còn cầm đầu cả tổ chức chép code để tham gia cuộc thi do LQDOJ tổ chức như đã nói trong bài trước. Vì quá bế tắc trong việc bắt imbigbrain, LQDOJ đã cử thám tử nguyenminhhai021009 biệt danh là Sherlock Hải (người đã tổ chức NMH contest) và bạn của Sherlock Hải là bác sĩ huyhau6a2 (bác sĩ John Huy Hậu(tên do nguyenminhhai đặt chứ tui không phải là người lai nước ngoài đâu nghen, đừng hiểu lầm ai đọc Sherlock Holmes thì biết John là ai) người top \(1\) contest NMH contest đó mà không chép code, if test \(1\) cái nào(nghe hơi xạo xạo thì phải)). Vì cái tính gáy hơi bị to của mình imbigbrain còn thách thức thám tử Sherlock Hải bằng cách viết mật thư báo vị trí của mình khắp nơi. Mật thư là \(1\) xâu nhị phân có độ dài không quá \(10^6\). Để đọc được mật mã cho đúng rồi xác định vị trí của imbigbrain rồi bắt nó Sherlock Hải phải làm đúng những điều kiện như sau:

Hãy xét vị trí của imbigbrain là tọa độ \((x, y, z)\) thì nguyenminhhai021009 và huyhau6a2 phải thực hiện tính toán như sau:

Tọa độ \(x\) chỉ số cách chia xâu nhị phân \(k\) thành các xâu con sao
cho các bit giống nhau không đứng kề nhau mod \(10^9+7\)
Tọa độ \(y\) chỉ số cách chia xâu nhị phân \(k\) thành các xâu con gồm
toàn các bit giống nhau mod \(10^9+7\)
Tọa độ \(z\) chỉ số cách chia xâu nhị phân \(k\) thành các xâu con sao
cho các giá trị của chúng khi chuyển sang hệ thập phân không quá giá
trị \(y\) đã tìm được mod \(10^9+7\)

Khi đã tìm ra tọa độ thì ta có thể dễ dàng biết được hang ổ của imbigbrain và sẽ giúp bộ tứ hoàng tìm ra tài khoản ONE PIECE. LQDOJ và bộ tứ hoàng sẽ tặng cho thám tử Sherlock Hải và bác sĩ John Huy Hậu rất nhiều tiền (là điểm đấy) nếu họ giải được mật mã và bắt được tên tội phạm immoriaty não to đó và được mọi người tôn vinh. Nhưng vốn không ham tiền bạc danh lợi (ai lại ngu dốt đến mức không ham tiền bạc và danh lợi cơ chứ), và cái mật mã đó giải dễ ợt nên Sherlock Hải và John Huy Hậu quyết nhường lại vụ án cho các thám tử đã gắn bó lâu năm của LQDOJ có dịp trổ tài. Mọi người hãy giúp LQDOJ nào!!! Ai giải được mật mã sẽ được tặng tiền (điểm) và \(+1\) bài AC vào tài khoản nhé

Input

Dòng \(1\) gồm số \(q\) chỉ số truy vấn \((q≤100)\).
\(Q\) dòng tiếp theo, mỗi dòng gồm duy nhất \(1\) xâu nhị phân \(k\) có độ
dài không quá \(10^6\).

Output

Mỗi dòng xuất ra \(3\) tọa độ \((x, y, z)\) thỏa mãn

Example

Test 1

Input

Output

2 4 8
8 1 2
4 2 4

Note

Test 1

\(X\): Có \(2\) cách: \((0, 0, 1, 1); (0, 01, 1)\).
\(Y\): Có \(4\) cách: \((0, 0, 1, 1); (00, 1, 1); (0, 0, 11); (00, 11)\).
\(Z\): Có \(8\) cách: \((0, 0, 1, 1); (00, 1, 1); (0, 01, 1); (0, 0, 11); (00,11); (001, 1); (0, 011); (0011)\).

Test 2

\(X\): Có \(8\) cách: \((1, 0, 1, 0); (10, 1, 0); (1, 01, 0); (1, 0, 10); (10,10); (101, 0); (1, 010); (1010)\).
\(Y\): Chỉ có \(1\) cách: \((1, 0, 1, 0)\).
\(Z\): Có \(2\) cách: \((1, 0, 1, 0); (1, 01, 0)\).

Test 3

\(X\): Có \(4\) cách: \((0, 1, 1, 0); (01, 1, 0); (0, 1, 10); (01, 10)\).
\(Y\): Có \(2\) cách: \((0, 1, 1, 0); (0, 11, 0)\).
\(Z\): Có \(4\) cách: \((0, 1, 1, 0); (01, 1, 0); (0, 1, 10); (01, 10)\).

Bình luận

Solution bài 2

Author: huyhau6a2

\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn và Tiếp cận}}\)

Bài này có 3 cách giải, nhưng hãy cố gắng áp dụng cả 3 cách nha!

Cách 1: Đếm phân phối:

Gợi ý: có thể xem bài này: https://lqdoj.edu.vn/problem/binary

Bài này dạng khá giống 2 con trỏ, nhưng đây là trong trường hợp giá trị ràng buộc k, còn bài này khi l thay đổi thì chưa chắc r thay đổi, hoặc cũng có thể r thay đổi nhiều lần.

Vậy ta sẽ thử cách cày trâu đếm trước như sau: Ta phân tích đơn giản thì: Nếu gọi P là mảng kết quả của từng vị trí xâu con từ i tới n thì ta có công thức: nếu xâu con từ vị trí i tới vị trí j thỏa mãn điều kiện thì sẽ tăng P[i] lên P[j+1].

Giải thích thêm: Với 1 cách tạo được xâu con từ vị trí (i, j) và P[j+1] cách tạo xâu con từ vị trí (j+1, n) vậy sẽ tăng P[i] thêm P[j+1] với mỗi j thỏa mãn

Cách này mới chỉ là cách đầu, tuy khá là khả quan nhưng sẽ rất dễ bị tle(do mới chỉ là cách cày trâu đếm phân phối cơ bản thôi). Nên ta sẽ cần cách tối ưu hơn. Đây là một số cách

Cách 2: Vẫn là đếm phân phối nhưng thêm toán(cách này áp dụng cho tìm x và y):

Hãy suy nghĩ đơn giản cho phần tìm x, y như sau: nếu chia các xâu con sao cho được ít xâu con nhất thì với mỗi xâu con, có 2^(|k|-1) cách(trong đó k là xâu con và |k| là độ dài của xâu). Vậy ta có thể nhân các giá trị đếm nhận được

Kết luận: giá trị x, y luôn là một dạng lũy thừa của 2

Ta có công thức: giả sử gọi a là số giá trị i thỏa mãn n[i]=n[i+1], b thì ngược lại: x=2^{(|n|-1-a)},y=2^{(|n|-1-b)}

Cách 3: Vẫn là đếm phân phối nhưng thêm hai con trỏ(cách này mình nghĩ rất hay và áp dụng cho tìm \(z\)):

Nếu các bạn áp dụng 2 con trỏ cho bài này thì khá là khó, nhưng không sao

Mình xin trình bày giả thuật của mình: (Mình trình bày có thể hơi khó hiểu, mọi người thông cảm!)

    - Đầu tiên, mình hãy xét lại bài binary đã nêu ở đầu bài. Thì lần này ta sẽ xét biến S là biến trung gian để tính giá trị thập phân của đoạn k[l]->k[r]. Tuy vậy sẽ dễ bị tràn số

    - Vì S có thể tràn số nên ta sẽ mod cho 1 số(tạm gọi đó là MOD)

    - Vậy câu hỏi đặt ra là nếu MOD biến S thì sẽ ra sao?

    - Trả lời: Thực chất vấn đề chính là khi MOD biến S thì ta sẽ không biết được biến đó so sánh ra sao với biến p2 đã tính được. Vậy ta sẽ xét độ dài, VD: Khi mod Num cho biến MD, với một xâu con độ dài ≤log⁡(MD) thì chắc chắn giá trị của S sẽ không bao giờ lớn hơn MD(do với xâu độ dài log⁡(MD) toàn ký tự 1 thì sẽ có giá trị là 2^(log⁡(MD))-1 chắc chắn sẽ bé hơn MD với mọi MD). Vậy ta có thể so sánh dễ dàng

    - Vậy ta nên đặt biến MOD bằng bao nhiêu?

    - Trả lời: Đầu tiên, MOD phải là số nguyên tố(sẽ tiện cho 2 con trỏ theo cách chia cho S bằng nghịch đảo modulo)

    - Tiếp đó, ta thấy giá trị y để so sánh thì luôn <=10^9+7. Mình nghĩ nên đặt MOD phải lớn hơn 10^9+7(it nhất nên phải gấp đôi)

    - Vấn đề cuối cùng ta cần hỏi là tính giá trị S ra sao khi mod cho MOD

    - Trả lời: Áp dụng nghịch đảo modulo:

          + Về phần l-- thì dễ thực hiện rồi, nhưng phần r-- sẽ ra sao?

          + Về phần r--, thì đồng nghĩa với việc chia đôi S, bạn sẽ nhân nghịch đảo modulo. Chú ý: bạn cần trừ đi 1 nếu ký tự cuối trong đoạn là 1 thì chia sẽ chính xác

- Mình trình bày hơi khó hiểu, có gì các bạn cứ comment cho mình trên phần thảo luận nhé!

\(\color{green}{\text{Code tham khảo }}\): Approach

\(^{^{\color{purple}{\text{Độ phức tạp : }} O()\ \color{purple}{\text{thời gian}}\ ||\ O()\ \color{purple}{\text{bộ nhớ}}}}\)

C++

//Không có code đâu, tự làm đi hehe!