{"code":"quest","name":"Sao kê 2: Truy tìm","description":"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`:\r\n\r\n\tVà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: [user:WuTan], [user:vinhntndu], [user:SPyofgame] và [user: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:\r\n\r\nVà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  [user:nguyenminhhai021009] phải chống lại cả $2$ vua là [user:Nguyen_Le_Huy_Khanh] và [user:imbigbrain], vì đã tu tâm dưỡng tính nên [user:Nguyen_Le_Huy_Khanh] đã không bao giờ tái xuất giang hồ nữa nhưng [user: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 đó [user: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 [user:imbigbrain], `LQDOJ` đã cử thám tử [user: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ĩ [user: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 [user: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 [user:imbigbrain] rồi bắt nó `Sherlock Hải` phải làm đúng những điều kiện như sau:\r\n\r\nHãy xét vị trí của [user:imbigbrain] là tọa độ $(x, y, z)$ thì [user:nguyenminhhai021009] và [user:huyhau6a2] phải thực hiện tính toán như sau:\r\n\r\n - Tọa độ $x$ chỉ số cách chia xâu nhị phân $k$ thành các xâu con sao\r\n   cho các bit giống nhau không đứng kề nhau mod $10^9+7$\r\n - Tọa độ $y$ chỉ số cách chia xâu nhị phân $k$ thành các xâu con gồm\r\n   toàn các bit giống nhau mod $10^9+7$\r\n - Tọa độ $z$ chỉ số cách chia xâu nhị phân $k$ thành các xâu con sao\r\n   cho các giá trị của chúng khi chuyển sang hệ thập phân không quá giá\r\n   trị $y$ đã tìm được mod $10^9+7$\r\n\r\nKhi đã tìm ra tọa độ thì ta có thể dễ dàng biết được hang ổ của [user: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é\r\n\r\n####Input\r\n - Dòng $1$ gồm số $q$ chỉ số truy vấn $(q≤100)$.\r\n - $Q$ dòng tiếp theo, mỗi dòng gồm duy nhất $1$ xâu nhị phân $k$ có độ\r\n   dài không quá $10^6$.\r\n\r\n####Output\r\n - Mỗi dòng xuất ra $3$ tọa độ $(x, y, z)$ thỏa mãn\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```\r\n        3\r\n        0011\r\n        1010\r\n        0110\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```\r\n        2 4 8\r\n        8 1 2\r\n        4 2 4\r\n        ```\r\n        \r\n    ??? warning \"Note\"        \r\n        ####Test 1\r\n\r\n        - $X$: Có $2$ cách: $(0, 0, 1, 1); (0, 01, 1)$.\r\n        - $Y$: Có $4$ cách: $(0, 0, 1, 1); (00, 1, 1); (0, 0, 11); (00, 11)$.\r\n        - $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)$.\r\n        \r\n        ####Test 2\r\n\r\n        - $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)$.\r\n        - $Y$: Chỉ có $1$ cách: $(1, 0, 1, 0)$.\r\n        - $Z$: Có $2$ cách: $(1, 0, 1, 0); (1, 01, 0)$.\r\n        \r\n        ####Test 3\r\n\r\n        - $X$: Có $4$ cách: $(0, 1, 1, 0); (01, 1, 0); (0, 1, 10); (01, 10)$.\r\n        - $Y$: Có $2$ cách: $(0, 1, 1, 0); (0, 11, 0)$.\r\n        - $Z$: Có $4$ cách: $(0, 1, 1, 0); (01, 1, 0); (0, 1, 10); (01, 10)$.","points":500.0,"partial":true,"time_limit":2.5,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}