USACO 2023 - Tháng 1 - Hạng Vàng

Bessie đang sử dụng phần mềm chỉnh sửa văn bản tiên tiến nhất, miV! Tính năng tìm và thay thế mạnh mẽ của nó cho phép cô tìm tất cả các ký tự chữ thường \(c\) và thay thế mỗi ký tự đó bằng một chuỗi không rỗng các chữ cái thường \(s\). Ví dụ, với chuỗi "ball", nếu Bessie chọn \(c\) là 'l' và \(s\) là "na", chuỗi sẽ biến thành "banana".

Bessie bắt đầu với chuỗi "a" và thực hiện một số thao tác tìm và thay thế, dẫn đến chuỗi cuối cùng là \(S\). Vì \(S\) có thể rất lớn, cô muốn biết, với các giá trị \(l\) và \(r\) thỏa mãn \(1 \le l \le r \le \min(|S|, 10^{18})\), chuỗi con \(S_{l \dots r}\) (từ ký tự thứ \(l\) đến ký tự thứ \(r\) trong \(S\)) là gì.

Đảm bảo rằng tổng độ dài của tất cả các chuỗi \(s\) trong các thao tác không vượt quá \(2 \cdot 10^5\), và \(r - l + 1 \le 2 \cdot 10^5\).

Input

• Dòng đầu tiên chứa các số nguyên \(l\), \(r\) và số lượng thao tác.
• Mỗi dòng tiếp theo mô tả một thao tác, chứa ký tự \(c\) và chuỗi \(s\) tương ứng. Tất cả các ký tự đều trong phạm vi từ 'a' đến 'z'.

Output

• In ra chuỗi \(S_{l \dots r}\) trên một dòng duy nhất.

Scoring

• Subtask \(1\): \(\sum |s|, r - l + 1 \le 2000\)
• Subtask \(2\): Không có ràng buộc nào khác.

3 8 4
a ab
a bc
c de
b bbb

bdebbb

Note: Giới hạn thời gian của bài này là 4s, gấp đôi so với thông thường.

Bessie muốn đi ngủ, nhưng ánh sáng từ trang trại khiến cô ấy không thể chợp mắt. Làm thế nào để cô ấy có thể tắt hết đèn?

Bessie có hai chuỗi nhị phân độ dài \(N\) (\(2 \le N \le 20)\), lần lượt đại diện cho trạng thái của các đèn và các công tắc. Mỗi đèn có thể đang bật (1) hoặc tắt (0). Mỗi công tắc có thể đang hoạt động (1) hoặc không hoạt động (0).

Một thao tác bao gồm các bước sau:

1. Thay đổi trạng thái của đúng một công tắc (nếu đang không hoạt động thì bật lên, và ngược lại).
2. Đối với mỗi công tắc đang hoạt động, thay đổi trạng thái của đèn tương ứng (nếu đèn đang bật thì tắt, và ngược lại).
3. Xoay vòng các công tắc sang phải một vị trí. Cụ thể, nếu chuỗi nhị phân ban đầu của các công tắc là \(s_0s_1\dots s_{N-1}\) thì sau khi xoay sẽ trở thành \(s_{N-1}s_0s_1\dots s_{N-2}\).

Với \(T\) (\(1 \le T \le 2 \cdot 10^5\)) trường hợp cho bài toán trên, hãy tính số thao tác tối thiểu để tắt hết tất cả các đèn.

Input

• Dòng đầu tiên chứa \(T\) và \(N\).
• \(T\) dòng tiếp theo, mỗi dòng chứa một cặp chuỗi nhị phân độ dài \(N\).

Output

• Với mỗi cặp chuỗi, in ra số lượt thao tác tối thiểu để tắt hết các đèn.

Scoring

• Subtask \(1\): \(N \le 8\)
• Subtask \(2\): \(N \le 18\)
• Subtask \(3\): Không có ràng buộc nào khác.

4 3
000 101
101 100
110 000
111 000

0
1
3
2

1 10
1100010000 1000011000

2

Nông dân Nhoj đã thả Bessie ở một nơi xa lạ! Tại thời điểm \(t=0\), Bessie ở vị trí \(x=0\) trên một trục số vô hạn. Cô ấy hoảng loạn tìm lối thoát bằng cách di chuyển sang trái hoặc phải \(1\) đơn vị mỗi giây. Tuy nhiên, thực tế là không có lối thoát nào, và sau \(T\) giây, Bessie quay lại \(x=0\), mệt mỏi và chán nản.

Nông dân Nhoj cố gắng theo dõi Bessie nhưng chỉ biết số lần Bessie vượt qua các vị trí \(x=0.5, 1.5, 2.5, \ldots, (N-1).5\), được cho bởi mảng \(A_0, A_1, \dots, A_{N-1}\) (\(1 \leq N \leq 10^5\), \(1 \leq A_i \leq 10^6\)). Bessie không bao giờ đến vị trí \(x>N\) hay \(x<0\).

Cụ thể, lộ trình của Bessie có thể được biểu diễn bằng một chuỗi gồm \(T = \sum_{i=0}^{N-1} A_i\) ký tự 'L' và 'R', trong đó ký tự thứ \(i\) đại diện cho hướng Bessie di chuyển trong giây thứ \(i\). Số lần thay đổi hướng được định nghĩa là số lần xuất hiện của 'LR' cộng với số lần xuất hiện của 'RL'.

Hãy giúp nông dân Nhoj đếm số lộ trình Bessie có thể đã thực hiện phù hợp với mảng \(A\) và tối thiểu hóa số lần thay đổi hướng. Đảm bảo rằng luôn có ít nhất một lộ trình hợp lệ.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa các số nguyên \(A_0, A_1, \dots, A_{N-1}\).

Output

• In ra số lộ trình Bessie có thể đã thực hiện, modulo \(10^9+7\).

Scoring

• Subtask \(1\): \(N \leq 2\) và \(\max(A_i) \leq 10^3\)
• Subtask \(2\): \(N \leq 2\)
• Subtask \(3\): \(\max(A_i) \leq 10^3\)
• Subtask \(4\): Không có ràng buộc nào khác.

2
4 6

2

RRLRLLRRLL
RRLLRRLRLL