LQDOJ CUP 2022 - Round 6

Vào một ngày nọ, bạn của Long giới thiệu cho cậu một tựa game chiến thuật khá nổi tiếng dạo gần đây. Trò chơi cung cấp cho Long \(n\) quân lính, quân lính thứ \(i\) (\(1 \leq i \leq n\)) có chỉ số sức mạnh là \(p_i\). Ở mỗi màn chơi sẽ có một con quái vật, giả sử con quái vật có chỉ số sức mạnh là \(k\), để tiêu diệt được nó Long phải chọn ra một đội hình gồm các quân lính sao cho tổng sức mạnh các quân lính đó không nhỏ hơn \(k\).

Biết rằng trò chơi có nhiều màn và các quân lính cậu đã chọn vào đội hình sẽ biến mất và không thể sử dụng lại, Long phải tính toán làm sao để sử dụng tối ưu các quân lính của mình. Cậu nhận thấy rằng trong đội hình có thể có một vài quân lính không quan trọng.

Vì vậy nên Long muốn xác định xem trong \(n\) quân lính, quân lính thứ \(i\) có quan trọng hay không. Quân lính thứ \(i\) (\(1 \leq i \leq n\)) được xem là quan trọng hay không dựa theo quy tắc sau:

• Nếu như với bất kỳ đội hình tiêu diệt được quái vật có chứa quân lính thứ \(i\), đội hình mới được tạo ra bằng cách bỏ quân lính đó đi và giữ nguyên những quân lính còn lại vẫn có thể tiêu diệt được quái vật, thì quân lính thứ \(i\) được xem là không quan trọng.
• Ngược lại, quân lính thứ \(i\) được xem là quan trọng.

Lưu ý: Đội hình có thể không có quân lính nào cả.

Vì số lượng quân lính là rất lớn nên Long nhờ bạn xác định giúp cậu.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n, k \leq 5000\)) lần lượt là số lượng quân lính và chỉ số sức mạnh của quái vật.
• Dòng tiếp theo chứa \(n\) số nguyên \(p_i\) (\(1 \leq p_i \leq 10^9\)) là chỉ số sức mạnh của các quân lính.

Output

• In ra một dãy nhị phân độ dài \(n\), bit thứ \(i\) bằng \(0\) nếu quân lính thứ \(i\) không quan trọng, bằng \(1\) nếu ngược lại.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(40\%\) số điểm): \(n, k \leq 400\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

4 10
4 1 6 2

1010

Câu chuyện của chúng ta xảy ra vào hai thời điểm khác nhau, vào hai cuộc thi khác nhau.

Nhưng dù thời gian khác nhau, thì không gian cũng đều giống nhau và không có thật: mọi thứ đều được đếm từ \(0\) thay vì đếm từ \(1\).

Câu chuyện 1 - Hội thi Tin học trẻ Toàn quốc

Đề thi của bảng thi C1 là về nhận diện chữ số.

Hesll đã chuyển được các bức ảnh về dưới dạng nhiều dãy có \(n\) bit. Tuy nhiên, nếu chỉ đơn thuần nhét các xâu nhị phân, thì code không thể lưu được nhiều hình ảnh để đối chiếu. Vì vậy, Hesll nhờ vào phép nén Base64.

Một xâu nhị phân \(X\) gồm \(n\) bit \(X_0X_1X_2\dots X_{n-2}X_{n-1}\) có thể được nén về dạng Base64 thành xâu \(X'\) theo các bước như sau:

• Thêm một vài bit \(0\) phía cuối sao cho \(n = |X|\) mới chia hết cho \(6\).
• Nhóm thành \(n'=\dfrac{n}{6}\) nhóm, nhóm thứ \(i\) là xâu nhị phân 6-bit \(X_{6i}X_{6i+1}X_{6i+2}X_{6i+3}X_{6i+4}X_{6i+5}\) (\(0 \le i < n'\)).
• Với mỗi nhóm \(i\), biến từ xâu nhị phân thành một số nguyên bằng phép tính như sau: \(x'_i = \sum\limits_{j=0}^{5} X_{6i+j}\times 2^j\)
• Sau khi thực hiện phép tính ra được số \(x'_i\), ký tự \(X'_i\) sẽ là ký tự ở vị trí \(x'_i\) trong xâu sau (có độ dài \(2^6=64\) ký tự):
  ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
• Ghép toàn bộ các ký tự \(X'_i\) lại (\(0 \le i < n'\)) để tạo thành xâu \(X'\) có độ dài \(n'\).

Để chuyển ngược lại từ dãy \(X'\) dạng Base64 về thành dãy nhị phân \(X\), ta làm ngược lại quy trình trên.

Phần Input của chúng ta sẽ được nhập vào dưới dạng này. Tuy nhiên, hôm nay trọng tâm của chúng ta không phải là về Base64, vì vậy Hesll sẽ không bắt các bạn phải code nguyên đoạn chuyển đổi từ đầu vào Base64 thành dãy nhị phân. Do đó, các bạn có thể tham khảo code nhập đầu vào ở phần Note.

Câu chuyện 2 - Codeforces

Ở một kỳ thi Codeforces gần đây, bạn Hesll một lần nữa lại đọc nhầm đề mà quên mất rằng, nó chỉ là bài B mà thôi. Hesll đọc nhầm đề bài thành như sau:

Với một xâu nhị phân \(X\) bất kỳ, gọi \(x\) và \(y\) lần lượt là số lượng chữ số \(1\) và \(0\) trong xâu nhị phân đó. Khi đó, trọng số \(w\) của xâu \(X\) là:

Cho xâu \(S\) có \(n = |S|\) là độ dài xâu. Một xâu được gọi là xâu con liên tiếp (gọi tắt là xâu con) của xâu \(S\) nếu nó có thể được tạo bằng cách xóa đi một số ký tự đầu tiên và cuối cùng của xâu. Khi đó, xâu con bắt đầu từ vị trí \(l\), kết thúc tại vị trí \(r\) được gọi là xâu \(S_{l, r}\) \((0 \le l \le r < n)\).

Ví dụ, abc là xâu con liên tiếp của dabce nhưng không phải là xâu con liên tiếp của adbce.

Cho xâu nhị phân \(S\) có độ dài \(n\). Tính \(\sum\limits_{l=0}^{n-1} \sum\limits_{r=l}^{n-1} w(S_{l,r})\), hay nói cách khác là tổng trọng số của mọi xâu con liên tiếp của \(S\).

Tất nhiên, vì đã kể câu chuyện 1, nên xâu đầu vào của chúng ta sẽ có dạng Base64, và chúng ta phải chuyển đổi sang xâu nhị phân có độ dài \(n\) trước khi bắt đầu xử lý thuật toán.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10^7\)) là độ dài xâu \(S\).
• Dòng tiếp theo chứa \(\left\lfloor \dfrac{n-1}{6}+1 \right\rfloor\) ký tự là biểu diễn Base64 của xâu \(S\). Mỗi ký tự chỉ thuộc vào một trong số \(64\) ký tự sau:

            `ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/`
  

Output

• In ra phần dư khi chia đáp án của bài toán cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n \leq 300\).
• Subtask \(2\) (\(10\%\) số điểm): \(n \leq 5 \times 10^3\).
• Subtask \(3\) (\(10\%\) số điểm): \(n \leq 10^5\), toàn bộ các ký tự của \(S\) đều giống nhau.
• Subtask \(4\) (\(15\%\) số điểm): \(n \leq 10^5\), tồn tại duy nhất một vị trí \(i\) sao cho \(S_i \neq S_{i + 1}\) (\(0 \le i < n-1\)).
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^5\).
• Subtask \(6\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
G

18

Note

Đoạn code sau giúp chuyển đổi một xâu Base64 kiểu string ra một mảng hằng \(S\).

Đầu tiên, người dùng gọi hàm initBase64() để khởi tạo chức năng xử lý, và sau khi nhập xâu \(S64\) thì gọi hàm b64Conversion(S64) để chuyển đổi và lưu xâu nhị phân thành phẩm gồm các ký tự 0 và 1 vào mảng \(S\).

#include <bits/stdc++.h>
using namespace std;

const char B64[65] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
int position[256];
void initBase64(){
    for (int i = 0; i < 64; i++) {
        position[B64[i]] = i;
    }
}

#define MAX 10000001
int n;
string S64;
char S[MAX];
void b64Conversion(const string &s){
    int ptr = 0;
    for (char c: s){
        int x = position[c];
        for (int i = 0; i < 6; i++){
            S[ptr++] = (x & 1) + '0';
            x >>= 1;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> S64;
    initBase64(); b64Conversion(S64);

    // main logic goes here
}

Một cặp số nguyên dương \((x, y)\) được gọi là bí ẩn nếu với \(a, b\) lần lượt là số ước dương lẻ và số ước dương chẵn của \(x \cdot y\) ta có tổng \(GCD(a, b) + LCM(a, b)\) là một số lẻ. Trong đó \(GCD(a, b)\) là ước chung lớn nhất của \(a\) và \(b\), \(LCM(a,b)\) là bội chung nhỏ nhất của \(a\) và \(b\).

Gọi \(S\) là tập hợp gồm \(k\) số nguyên phân biệt \(\{S_1, S_2, \ldots, S_k\}\). Xét đồ thị gồm \(k\) đỉnh đánh số từ \(1\) tới \(k\). Với mọi cặp \(1 \leq u,v \leq k\), nếu \(S_u\) và \(S_v\) là một cặp bí ẩn thì ta nối một cạnh có hướng nối từ \(u\) tới \(v\). Gọi \(d(u,v)\) là độ dài đường đi ngắn nhất từ \(u\) với \(v\), nếu \(u\) không có đường đi tới \(v\) thì \(d(u,v)=10^{18}\). Độ bí ẩn của tập hợp \(S\) sẽ là \(\max\limits_{1 \leq u,v \leq k}\{d(u,v)\}\). Cho hai số nguyên dương \(n\) và \(k\), với mọi tập hợp \(S\) gồm \(k\) số nguyên phân biệt thỏa \(1 \leq S_i \leq n\), tìm độ bí ẩn nhỏ nhất và số lượng tập hợp có độ bí ẩn nhỏ nhất.

Lưu ý: Hai tập hợp là khác nhau khi tồn tại ít nhất một phần tử xuất hiện trong tập này mà không xuất hiện ở tập kia.

Input

• Dòng đầu chứa số nguyên \(q\) (\(1 \leq q \leq 10\)) là số test.
• Trong \(q\) dòng tiêp theo, mỗi dòng chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n, k \leq 10^{12}\)).

Output

• Với mỗi test, in ra hai số nguyên là độ bí ẩn nhỏ nhất và số lượng tập hợp có độ bí ẩn nhỏ nhất. Vì kết quả có thể rất lớn nên hãy in các kết quả chia lấy dư cho \(10^9+7\). Nếu không tồn tại tập hợp nào thì in \(-1\) và \(0\).
• Lưu ý, việc so sánh các độ bí ẩn là so sánh theo giá trị thật, không phải so sánh theo giá trị sau khi chia lấy dư. Ví dụ \(10^9 + 7 > 1\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 10\)
• Subtask \(2\) (\(10\%\) số điểm): \(n \leq 10^5\) và \(k = 2\)
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^7\) và \(k = 3\)
• Subtask \(4\) (\(15\%\) số điểm): \(n,k \leq 10^5\)
• Subtask \(5\) (\(15\%\) số điểm): \(n,k \leq 10^7\)
• Subtask \(6\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

1
4 2

1 1