Tin học trẻ C1 - Tỉnh Bắc Giang 2024

Cho hai số nguyên dương \(n, m\) và mảng \(a\) gồm \(n\) số nguyên dương phân biệt \(a_{1}, a_{2}, \ldots, a_{n}\). Tính tích các số nằm trong khoảng từ \(1\) đến \(m\) mà không thuộc mảng \(a\). Do kết quả có thể rất lớn, bạn cần đưa ra kết quả sau khi chia lấy phần dư cho \(10^{9} + 7\).

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n, m\) \((1 \leq n \leq m \leq 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên dương phân biệt \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq m)\).

Output

• Gồm một dòng duy nhất chứa một số nguyên là kết quả của bài toán.

Scoring

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

Example

3 5
1 2 4

15

Bạn được cho một mảng \(a\) gồm \(n\) (\(n\) chia hết cho \(3\)) phần tử. Bạn được thực hiện vô số thao tác sau: tăng hoặc giảm \(1\) phần tử bất kỳ lên hoặc xuống \(1\) đơn vị. Gọi \(c_{0}, c_{1}\) và \(c_{2}\) lần lượt là số lượng các phần tử trong mảng \(a\) khi chia lấy dư cho 3 có số dư bằng \(0, 1\) và \(2\). Một mảng được gọi là cân đối khi \(c_{0} = c_{1} = c_{2}\).

Yêu cầu: bạn hãy tìm cách cân đối mảng \(a\) ban đầu bằng cách thực hiện \(0\) hoặc nhiều thao tác và in ra số thao tác ít nhất để cân đối mảng \(a\).

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) \((1 \leq n \leq 5 \times 10^{5}, n \mod 3 = 0)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((0 \leq a_{i} \leq 10^{9})\).

Output

• Gồm một dòng duy nhất chứa một số nguyên là số thao tác ít nhất để cân đối mảng.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n = 3\).
• Subtask \(2\) (\(40\%\) số điểm): \(a_{i} \leq 2\).
• Subtask \(3\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

6
5 3 8 9 11 34

1

Cho bốn số nguyên dương \(n, a, b, c\) hãy tính tổng sau:

Với \(x\) là số nguyên thỏa mãn các tính chất sau:

• \(x\) chia hết cho \(a\) hoặc \(x\) chia hết cho \(b\) hoặc \(x\) chia hết cho cả \(a\) và \(b\)
• \(x\) không chia hết cho \(c\).

Trong đó \(\left\lfloor x \right\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Input

• Dòng thứ nhất chứa một số nguyên dương \(q\) \((1 \leq q \leq 50)\) là số bộ thử nghiệm.
• \(q\) dòng tiếp theo, dòng thứ \(i\) tương ứng với bộ thử nghiệm thứ \(i\), dòng thứ \(i\) chứa bốn số nguyên \(n, a, b, c\) \((1 \leq n, a, b, c \leq 10^{9})\).

Output

• In ra \(q\) dòng, dòng thứ \(i\) chứa kết quả tương ứng với bộ thử nghiệm thứ \(i\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10^{6}\).
• Subtask \(2\) (\(30\%\) số điểm): \(a = b\) và \(c > n\).
• Subtask \(3\) (\(20\%\) số điểm): \(c > n\).
• Subtask \(4\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

2
15 2 3 5
30 2 4 9

21
44

Dãy tình yêu là dãy chỉ gồm hai ký tự < và 3. Khi áp dụng các phép biến đổi ma thuật lên dãy, các ký tự sẽ dần được thay thế bởi các "trái tim" (heart) - mỗi trái tim là một đối tượng có độ lớn (kích thước) là một số nguyên dương.

Quy tắc biến đổi ma thuật:

Các phép biến đổi sau được áp dụng liên tục và lặp lại cho đến khi không còn phép biến đổi nào có thể áp dụng. Ưu tiên áp dụng các phép biến đổi theo thứ tự từ trái sang phải trong dãy:

1. Tạo trái tim cơ bản: Nếu ký tự < đứng ngay liền trước ký tự 3, hai ký tự này sẽ biến thành một trái tim có độ lớn \(1\).

2. Gộp hai trái tim: Nếu hai trái tim đứng liền kề nhau (trái tim có độ lớn \(a\) đứng ngay trước trái tim có độ lớn \(b\)), chúng sẽ gộp thành một trái tim có độ lớn \(a + b\).

3. Mở rộng trái tim: Nếu một trái tim có độ lớn \(h\) có ký tự < đứng ngay liền trước và ký tự 3 đứng ngay liền sau (tức cấu trúc < [trái tim \(h\)] 3), ba phần tử này sẽ biến thành một trái tim có độ lớn \(h + 1\).

Kết quả cuối cùng: Sau khi không còn phép biến đổi nào có thể áp dụng, nếu dãy chỉ còn lại đúng một trái tim duy nhất, độ lớn của trái tim đó là kết quả. Nếu dãy còn lại nhiều hơn một phần tử (bao gồm ký tự hoặc nhiều trái tim), kết quả là \(0\).

Ví dụ chi tiết:

• <3 → trái tim độ lớn \(1\)
• <3<3 → <3 [tim 1] → [tim 1] [tim 1] → trái tim độ lớn \(2\)
• <<33 → < [tim 1] 3 → trái tim độ lớn \(2\)
• <<3<3<33 → < [tim 1] <3<33 → < [tim 1] < [tim 1] [tim 1] → < [tim 1] < [tim 2] → < [tim 1] [tim 2] < (không biến đổi thêm) → ... (tiếp tục) → trái tim độ lớn \(4\)

Bài toán:

Hân có thể xóa một số ký tự tùy ý (có thể không xóa ký tự nào) từ dãy ban đầu để tạo ra một dãy con (subsequence - giữ nguyên thứ tự tương đối của các ký tự còn lại). Sau đó áp dụng các phép biến đổi ma thuật lên dãy con này.

Mục tiêu: Tìm độ lớn lớn nhất của trái tim có thể tạo ra sau khi xóa và biến đổi.

Bạn phải trả lời \(Q\) truy vấn thuộc \(2\) loại sau:

• Loại 1: 1 l r - Với mỗi vị trí \(i\) trong đoạn \([l, r]\): nếu \(S_i =\) < thì gán \(S_i =\) 3, ngược lại gán \(S_i =\) < (đảo ký tự).

• Loại 2: 2 l r - Xét dãy con liên tiếp \(S[l..r]\) (từ vị trí \(l\) đến vị trí \(r\)). Hỏi độ lớn lớn nhất của trái tim mà Hân có thể tạo ra bằng cách chọn một dãy con (subsequence) từ \(S[l..r]\) và áp dụng các phép biến đổi ma thuật.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n \leq 10^{6}, 1 \leq q \leq 5 \times 10^{5})\) là độ dài xâu \(S\) và số lượng truy vấn.
• Dòng thứ hai chứa xâu \(S\) có độ dài \(n\), chỉ gồm các ký tự < và 3.
• \(Q\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(t\), \(l\) và \(r\) \((t \in \{1, 2\}, 1 \leq l \leq r \leq n)\) thể hiện một truy vấn.

Output

• Với mỗi truy vấn loại \(2\), in ra một số nguyên duy nhất là độ lớn của trái tim lớn nhất mà Hân có thể tạo ra từ dãy con của \(S[l..r]\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 5 \times 10^{3}\).
• Subtask \(2\) (\(20\%\) số điểm): \(q \leq 10\), không có truy vấn loại \(1\).
• Subtask \(3\) (\(20\%\) số điểm): Có tối đa \(10\) truy vấn loại \(2\).
• Subtask \(4\) (\(20\%\) số điểm): Không có truy vấn loại \(1\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

16 10
<3<3<3<<3<<<3<3<
1 2 13
2 2 16
1 14 16
1 5 16
2 2 8
2 1 13
2 2 14
2 1 16
1 5 14
2 1 14

10
4
8
8
10
12