Mấy bài toán dính tới bit

Phòng học của lớp ITK19 vừa đổi từ khóa cơ sang khóa điện tử. Mật khẩu của khóa điện tử này là một đoạn mã nhị phân độ dài \(3n\), các bit của đoạn mã này được đánh số từ \(1\) đến \(3n\) theo chiều từ trái sang phải. Ta quy ước trọng số của một mã nhị phân bằng với \(1\) cộng cho số cặp bit kề nhau mà khác nhau. Ví dụ, đoạn mã 000 có trọng số là 1 còn đoạn mã 011010100 có trọng số là \(7\).

Bảo Khoa muốn trọng số của mã khóa phải lớn hơn hoặc bằng \(2n\) nên anh ấy đang nghiên cứu tìm ra một dãy thao tác để biến đổi mã khóa ban đầu. Ở mỗi thao tác, Bảo Khoa có thể chọn hai bit kề nhau trong đoạn mã và đảo chúng. Bạn hãy lập trình xác định một dãy thao tác có độ dài không quá \(n\) để biến đổi mã khóa ban đầu thành một mã khóa mới có trọng số ít nhất là \(2n\). Dữ liệu đảm bảo luôn tồn tại một cách biến đổi thỏa mãn.

Input

• Gồm một dòng duy nhất chứa một đoạn mã khóa có \(3n\) bit với \(1 \leq n \leq 10^5\).

Ouput

• Dòng đầu tiên ghi ra số nguyên \(m (0 \leq m \leq n)\) là số thao tác cần thực hiện.

• Dòng tiếp theo ghi ra \(m\) số chỉ số nguyên \(a_1, a_2,\cdots, a_m\) thể hiện phương án đảo bit bạn tìm được. Số nguyên \(a_k\) thể hiện chỉ số của bit bên trái trong hai bit được đảo ở thao tác thứ \(k\).

• Nếu đoạn mã ban đầu đã có trọng số lớn hơn hoặc bằng \(2n\) sẵn, bạn chỉ cần in ra số \(0\).

Example

000000000 

3
2 5 6

111001000111

2
3 9

010101 

0

Tính \(1 \oplus 2 \oplus 3 \oplus \dots \oplus n\) với \(n\) được nhập từ bàn phím.

Input

• Dòng 1 chứa \(t\) \((t \leq 10^5)\) - số câu hỏi.
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\).

Output

• Ứng với mỗi câu hỏi in ra đáp án cần tìm.

Constraints

• Subtask 1 [10%]: \(n \le 10\);
• Subtask 2 [90%]: \(n \le 10^{12}\).

Example

2
3
6

0
7

Note

• Nguồn: SPOJ

Nhân ngày 01/01/2021, Văn Quốc Khánh được mẹ cho một món quà, món quà được làm bằng hộp kim loại có mật khẩu. Mẹ Khánh rất thích những con số \(2^k\) với \(k\) là một số nguyên dương. Cho nên mật khẩu có dạng như sau:

Cho một số gồm \(N\) số nguyên dương \(A_1, A_2,\dots, A_N\), hãy chọn ra 3 số sao cho tích của 3 số đó chia hết cho \(2^k\). Hai cách chọn được xem là khác biệt khi có ít nhất một chỉ số ở cách 1 không có trong cách 2.

Ví dụ: \(1,2,3\) và \(2,1,4\) được xem là 2 cách khác biệt, còn \(2,1,3\) và \(3,2,1\) được xem là cùng 1 cách.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N,k\)
• Dòng thứ hai chứa dãy số \(A_1, A_2,\dots, A_N\)

Output

• Một số nguyên duy nhất là số lượng chọn được.

Scoring

• Subtask #1 (60% số testcase): \(N \leq 300, k \leq 20, A_i \leq 10^5\)
• Subtask #2 (40% số testcase): \(N \leq 2*10^5, k \leq 64, A_i \leq 10^{18}\)

Example

30 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

1925

Cho \(q\) (\(q \leq 10^5\)) truy vấn, mỗi truy vấn cho hai số nguyên dương \(x, y\). Tìm số thao tác ít nhất để biến đổi \(x\) thành \(y\), biết rằng mỗi thao tác được thực hiện một trong hai hành động sau:

• Phép nhân 2: \(x \gets x \times 2\).
• Phép trừ 1 (chỉ thực hiện được khi \(x > 1\)): \(x \gets x - 1\).

Input

• Dòng đầu tiên gồm một số nguyên dương \(q\) là số truy vấn.
• \(q\) dòng tiếp theo, dòng thứ \(i\) (\(1 \leq i \leq q\)) gồm hai số nguyên dương \(x_i, y_i\) (\(x_i, y_i \leq 10^9\)) thể hiện một truy vấn tìm số thao tác ít nhất để biến đổi từ \(x_i\) thành \(y_i\).

Output

• Gồm \(q\) dòng, mỗi dòng gồm một số nguyên duy nhất là kết quả của một truy vấn. Các kết quả phải được in theo thứ tự với các truy vấn trong dữ liệu đầu vào.

Example

3
1 4
2 5
6 5

2
4
1

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(q \leq 1000\) và \(1 \leq x_i, y_i \leq 1000\).
• Subtask \(2\) (\(20\%\) số điểm): Tồn tại một cách tối ưu để biến đổi mà chỉ sử dụng phép nhân 2 nhiều nhất một lần.
• Subtask \(3\) (\(30\%\) số điểm): Tồn tại một cách tối ưu để biến đổi mà chỉ sử dụng phép trừ 1 nhiều nhất một lần.
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Naruto có \(N\) cái túi, túi thứ \(i\) có \(A_i\) đồng tiền. Mỗi lần đi làm nhiệm vụ, Naruto sẽ chọn ra một số túi để mang theo nếu thỏa mãn điều kiện sau:

Gọi \(S\) là tổng số tiền trong tất cả các túi Naruto chọn, cần chọn sao cho \(S \% 2 = P\) (% là phép lấy phần dư, % trong C++ và mod trong pascal). Hỏi Naruto có bao nhiêu cách chọn các túi?

Input

• Dòng đầu gồm 2 số nguyên \(N\) và \(P\).
• Dòng tiếp theo gồm \(N\) số là \(A_1, A_2, A_3, ...A_N\).

Output

• Gồm một dòng duy nhất chứa số nguyên là kết quả của bài toán. (Kết quả lấy phần dư với \(10^9 + 7\)).

Constants

• \(1 \leq N \leq 50\).
• \(0 \leq P \leq 1\).
• \(1 \leq A_i \leq 100\).

Example

2 0 
1 3 

2

Từ xâu nhị phân \(𝑆_0 =\)1, người ta sinh ra các xâu \(𝑆_1, 𝑆_2, … , 𝑆_𝑛\) trong đó \(𝑆_𝑖 = 𝑆_{𝑖−1} + \overline{𝑆_{𝑖−1}}\). Ở đây \(\overline{S_{i-1}}\) là xâu nhị
phân tạo thành từ xâu \(\overline{S_{i-1}}\) bằng cách đảo hết các bit (bit 1 thành bit 0 và bit 0 thành bit 1). Ví dụ:

\(𝑆_0 =\)"\(1\)"
\(𝑆_1 =\)"\(10\)"
\(𝑆_2 =\)"\(1001\)"
\(𝑆_3 =\)"\(10010110\)"
\(𝑆_4 =\)"\(1001011001101001\)"

Yêu cầu: Cho số nguyên dương \(𝑛\), hãy xác định trong xâu \(𝑆_𝑛\) có bao nhiêu vị trí có 2 bit liên tiếp bằng nhau (tức
là đếm số lần xuất hiện của xâu “00” và “11” trong \(𝑆_𝑛\))

Input

• Dòng 1 chứa số nguyên dương \(𝑇\) là số test
• \(𝑇\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(𝑛\) ứng với một test

Output

• Ghi ra \(𝑇\) dòng, mỗi dòng ghi một số nguyên duy nhất là số dư của kết quả tìm được khi chia cho \(123456789\)

Constraints

• \(𝑇 \leq 10^5\)
• \(𝑛 \leq 10^9\)

Example

4
1
2
3
4 

0
1
2
5

Cho một dãy số gồm \(n\) phần tử, nhiệm vụ của bạn là tính toán với mỗi phần tử \(x\):

1. Số phần tử \(y\) sao cho \(x\) | \(y\) \(=\) \(x\)
2. Số phần tử \(y\) sao cho \(x\) & \(y\) \(=\) \(x\)
3. Số phần tử \(y\) sao cho \(x\) & \(y\) \(\neq\) \(0\)

Input

• Dòng đầu tiên gồm số nguyên \(n\): kích thước của dãy số
• Dòng tiếp theo gồm \(n\) số nguyên \(x_1, x_2,...,x_n\): các phần tử của dãy số

Constraints

• \(1 \leq n \leq 2\cdot 10^5\)
• \(1 \leq x_i \leq 10^6\)

Output

• In ra \(n\) dòng, mỗi dòng là đáp án của các thao tác với phần tử đang xét

Example

5
3 7 2 9 2

3 2 5
4 1 5
2 4 4
1 1 3
2 4 4

Cho trước giá trị \(C\) và \(N\) thao tác bit, thao tác thứ \(i\) có dạng \(T \ A\), trong đó:

• \(T=1\) biểu thị cho phép gán \(M = M \ \text{and} \ A\).
• \(T=2\) biểu thị cho phép gán \(M = M \ \text{or} \ A\).
• \(T=3\) biểu thị cho phép gán \(M = M \ \text{xor} \ A\).

Đức có một biến số nguyên \(X\). Ban đầu, Đức gán \(X=C\) và tiến hành \(N\) bước tính toán:

• Bước \(1\): Áp dụng thao tác bit thứ \(1\) lên \(X\). Sau đó, in giá trị của \(X\) lên màn hình.
• Bước \(2\): Lần lượt áp dụng thao tác bit thứ \(1\) và thứ \(2\) lên \(X\). Sau đó, in giá trị của \(X\) lên màn hình.
• Bước \(3\): Lần lượt áp dụng thao tác bit thứ \(1\), thứ \(2\), và thứ \(3\) lên \(X\). Sau đó, in giá trị của \(X\) lên màn hình.
• ...
• Bước \(N\): Lần lượt áp dụng thao tác bit thứ \(1\), thứ \(2\), thứ \(3\),..., thứ \(N\) lên \(X\). Sau đó, in giá trị của \(X\) lên màn hình.

Bạn hãy giúp Đức viết chương trình thực hiện \(N\) bước tính toán trên nhé!

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(C\) \(\left(1\le N\le 2\times 10^5, 0\le C < 2^{30}\right)\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo có dạng \(1 \ A_i\), \(2 \ A_i\), hoặc \(3 \ A_i\) thể hiện thao tác bit thứ \(i\) \(\left(0\le A_i < 2^{30} \right)\).

Output

• In ra \(N\) dòng là kết quả của \(N\) bước tính toán.

Example

3 19
3 10
2 13
1 6

25
31
4