LQDOJ Cup 2024 - Round #3

Cho xâu \(S\) độ dài \(n\) chỉ gồm các chữ cái từ \(a\) đến \(z\).

Một xâu con liên tiếp của \(S\) được gọi là tệ nếu nó chỉ có một loại chữ cái.

Hãy tìm cách xóa đi đúng \(k\) ký tự sao cho số xâu con tệ của \(S\) sau khi xóa là nhỏ nhất, in ra số lượng xâu con tệ ít nhất có thể có.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(k\) \((1 \leq k \leq n \leq 10^{5})\).
• Dòng thứ hai là xâu \(S\) độ dài \(n\), chỉ gồm các chữ cái thường từ a đến z.

Output

• Gồm một dòng duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(21\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(23\%\) số điểm): \(n \leq 28\).
• Subtask \(3\) (\(27\%\) số điểm): \(n \leq 5000\).
• Subtask \(4\) (\(29\%\) số điểm): Không có ràng buộc gì thêm.

Example

10 2
babbdddaaa

11

19 10
cbdccccaeebddceedce

9

Đất nước Hẹn hò có \(n\) thành phố được đánh số từ \(1\) đến \(n\) và chúng được kết nối với nhau bởi \(m\) con đường \(2\) chiều (Đảm bảo từ thành phố bất kì đều có thể đi đến thành phố khác bằng \(m\) con đường này). Khoảng cách giữa \(2\) thành phố \((u, v)\) là độ dài tuyến đường ngắn nhất xuất phát từ thành phố \(u\) đi đến thành phố \(v\) qua các con đường.

Hùng sống ở đất nước này và đã có rất người yêu, hiện giờ tất cả đều là người yêu cũ của Hùng. Có \(k\) thành phố được Hùng gọi là đặc biệt vì ở những thành phố này có người yêu cũ của Hùng sống. Hùng gọi độ an toàn của một thành phố là khoảng cách ngắn nhất của thành phố này đến một trong \(k\) thành phố đặc biệt (Vì Hùng sợ người yêu cũ đến làm phiền nên càng xa càng an toàn).

Giả sử Hùng có một kế hoạch đi từ thành phố \(a\) đến thành phố \(b\) thì Hùng cần tìm một con đường đi qua các thành phố sao cho độ an toàn bé nhất trong các thành phố mà Hùng đi qua là lớn nhất

Trong \(q\) ngày tới Hùng quyết định đi dạo khắp đất nước Hẹn hò để đi kiếm thêm người yêu.

Với ngày thứ \(i\) Hùng sẽ đi từ thành phố \(a_{i}\) đến thành phố \(b_{i}\).

Bạn hãy giúp Hùng tính độ an toàn lớn nhất có thể trong các ngày này để Hùng yên tâm đi kiếm người yêu nhé!

Input

• Dòng đầu gồm bốn số nguyên \(n, m, k\) và \(q\) \((1 \leq k \leq n \leq 10^{5}, 1 \leq m \leq 5 \times 10^{5}, 1 \leq q \leq 10^{5})\) lần lượt là số thành phố, số con đường, số thành phố đặc biệt và số ngày Hùng dự định.
• \(m\) dòng tiếp theo gồm ba số nguyên \(u, v\) và \(w\) \((1 \leq u, v \leq n, 1 \leq w \leq 10^{4})\) mô tả một con đường nối hai thành phố \(u\) và \(v\) có độ dài là \(w\).
• Dòng tiếp theo gồm \(k\) số nguyên dương \(x_{1}, x_{2}, \ldots, x_{k}\) \((1 \leq x_{i} \leq n, \forall i \neq j: x_{i} \neq x_{j})\) là số thứ tự của các thành phố đặc biệt.
• \(q\) dòng cuối cùng, mỗi dòng gồm hai số nguyên \(u_{i}, v_{i}\) mô tả truy vấn chuyến đi ngày thứ \(i\) của Hùng \((1 \leq u_{i}, v_{i} \leq n, u_{i} \neq v_{i})\).

Output

• Gồm \(q\) dòng mỗi dòng in ra độ an toàn lớn nhất của \(q\) chuyến đi của Hùng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10, m\leq 50, q \leq 200\).
• Subtask \(2\) (\(20\%\) số điểm): \(n, m, q \leq 1000\) và các truy vấn có \(u_{i}\) kề \(v_{i}\).
• Subtask \(3\) (\(20\%\) số điểm): \(n, m, q \leq 1000\).
• Subtask \(4\) (\(20\%\) số điểm): các truy vấn có \(u_{i}\) kề \(v_{i}\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

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

5
2

Cho các số nguyên \(n, k, \alpha, \beta\).

Gọi \(A_{0}\) là một ma trận vuông có kích thước \(n \times n\), các hàng được đánh số từ \(1\) đến \(n\), các cột được đánh số từ \(1\) đến \(n\), ô ở hàng \(i\) cột \(j\) được gọi là ô \(A_{0}(i, j)\) và giá trị tại ô \(A_{0} (i, j)\) là \(A_{0} (i, j) = i^{\alpha} \times j^{\beta}\).

Gọi \(B_{0}\) là một ma trận vuông có kích thước \(n \times n\), các hàng được đánh số từ \(1\) đến \(n\), các cột được đánh số từ \(1\) đến \(n\), ô ở hàng \(i\) cột \(j\) được gọi là ô \(B_{0}(i, j)\) và giá trị tại ô \(B_{0} (i, j)\) là \(B_{0} (i, j) = A_{0} (j, i)\).

Với mọi số nguyên không âm \(x\) \((x \geq 0)\), ma trận \(A_{x + 1}\) là một ma trận có kích thước \({3^{x + 1}}n \times {3^{x + 1}}n\) và có dạng như sau

Ma trận \(B_{x + 1}\) là một ma trận có kích thước \(3^{x + 1}n \times 3^{x + 1}n\) và \(B_{x + 1} (i, j) = A_{x + 1} (j, i)\) \(\forall 1 \leq i, j \leq 3^{x + 1}n\).

Hình chữ nhật con \((u, v, x, y)\) của một ma trận là tập hợp các ô \((i, j)\) mà \(u \leq i \leq x, v \leq j \leq y\).

Yêu cầu: Cho bốn số nguyên \(n, k, \alpha, \beta\). Hãy tính tổng giá trị của các ô trong hình chữ nhật con \((u, v, x, y)\) của ma trận \(A_{k}\). Vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư khi chia kết quả cho \(({10}^9 + 7)\).

Input

• Dòng đầu tiên gồm một số nguyên dương \(T\) \((1 \leq T \leq 100)\) là số bộ dữ liệu.
• \(T\) nhóm dòng sau, mỗi nhóm dòng biểu diễn một bộ dữ liệu:
  • Dòng đầu tiên chứa bốn số nguyên \(n, k, \alpha\) và \(\beta\) \((1 \leq n \leq 10^{9}, 0 \leq k \leq 10, 1 \leq \alpha, \beta \leq 100)\).
  • Dòng thứ hai gồm bốn số nguyên \(u, v, x, y\) \((1 \leq u \leq x \leq n \times 3^{k}, 1 \leq v \leq y \leq n \times 3^{k})\) thể hiện câu hỏi cần trả lời.

Output

• Gồm \(T\) dòng, mỗi dòng gồm một số nguyên là kết quả của các bộ dữ liệu.

Scoring

• Subtask \(1\) (\(7\%\) số điểm): \(T \leq 5, n \leq 30, k \leq 3\).
• Subtask \(2\) (\(8\%\) số điểm): \(n = 1\).
• Subtask \(3\) (\(9\%\) số điểm): \(n = 2\).
• Subtask \(4\) (\(10\%\) số điểm): \(T \leq 5\) và \(k \leq 4\) và \(n \leq {10}^5\).
• Subtask \(5\) (\(11\%\) số điểm): \(T \leq 5\) và \(k \leq 4\) và \(1 \leq \alpha, \beta \leq 2\).
• Subtask \(6\) (\(12\%\) số điểm): \(T \leq 5\) và \(k \leq 4\) và \(\alpha = \beta = 3\).
• Subtask \(7\) (\(13\%\) số điểm): \(T \leq 5\) và \(k \leq 4\).
• Subtask \(8\) (\(14\%\) số điểm): \(\alpha, \beta \leq 10\).
• Subtask \(9\) (\(16\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
2 1 1 2
2 2 5 5
10 3 2 2
3 8 65 15

60
708000