LQDOJ CUP 2023 - Round 1

Con đường kẹo ngọt vừa được khai trương, là một điểm đến vô cùng hấp dẫn với những bạn trẻ có tâm hồn ăn uống. Có \(n\) địa điểm bán bánh kẹo nằm trên các số nhà liên tiếp \(1, 2, 3, \ldots, n\) của Con đường kẹo ngọt. Bằng kiến thức của mình, H biết được tổng cộng \(m\) loại đồ ngọt khác nhau, cậu đánh số chúng từ \(1\) tới \(m\). Theo quảng cáo, cậu cũng biết mỗi địa điểm \(i\) chỉ chuyên bán một loại là \(a_{i}\).

H có ý định sẽ đi mua bánh kẹo ở một vài địa điểm liên tiếp nhau, từ số nhà \(l\) tới số nhà \(r\). Là một tín đồ hảo ngọt, H đánh giá một kế hoạch \((l,r)\) như sau:

• Giả sử sau khi mua toàn bộ loại đồ ngọt từ địa điểm thứ \(l\) tới \(r\), có \(k\) loại đồ ngọt H chưa mua được, lần lượt là \(c_{1}, c_{2}, c_{3}, \dots, c_{k}\).
• Độ thiếu đường (hay độ thất vọng, chỉ số suy dinh dưỡng, ...) sẽ bằng với \(c_{1} + c_{2} + c_{3} + \dots + c_{k}\).

Để tính sweet-index của con đường này trước khi giới thiệu cho bạn bè, H cần tính tổng độ thiếu đường của toàn bộ các kế hoạch \((x, y)\) với \(1 \leq x \leq y \leq n\) (nói cách khác là đoạn các tiệm ngọt liên tiếp).

H thì đang mải mê ngắm nghía các loại bánh kẹo được bày bán tại các hàng quán. Nên việc tính toán này đành giao lại cho bạn :(.

Yêu cầu: cho trước \(n, m, a\). Hãy tính tổng độ thiếu đường theo mô tả ở trên.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq m \leq 10^{9})\) lần lượt là số địa điểm và số loại bánh kẹo.
• Dòng thứ hai chứa \(n\) số \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq m)\) là loại đồ ngọt được bày bán ở các tiệm.
• Lưu ý rằng có thể có các tiệm khác nhau cùng bán một loại, hoặc có loại không có tiệm nào bán.

Output

• In ra tổng độ thiếu đường của mọi đoạn đường liên tiếp. Vì kết quả có thể rất lớn, hãy in ra sau khi chia lấy dư cho \(998244353\).

Scoring

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

Example

3 4
1 2 3

40

8 4
2 3 1 2 4 3 1 3

124

8 1000000000
123456789 20040105 22071997 30081945 19051890 19450205 19800209 1969

661167837

Ở một tương lai xa xôi, trong phòng thí nghiệm hóa học nọ, có \(n\) lọ không tên! Nhưng may thay, trên mỗi lọ vẫn có nhãn, một con số \(c_{i}\) đại diện cho chất chứa trong lọ đó là gì. Với sự tiến bộ khoa học kĩ thuật, ta có các tính chất sau:

• Mỗi chất hóa học bất kì được đại diện bởi duy nhất một con số (gọi là số hiệu). Mỗi con số thể hiện đúng bản chất hóa học của một chất nào đó.
• Khi trộn hai chất có số hiệu \(a\) và \(b\) lại với nhau, ta được một chất mới có số hiệu \(a \oplus b\) (với \(\oplus\) là phép tính bitwise XOR).

Nhằm tìm kiếm những chất mới, các nhà nghiên cứu đã thực hiện trộn mọi bộ hai lọ khác nhau có trong phòng. Tức với mỗi hai lọ \((i, j)\) \((1 \leq i < j \leq n)\), người ta trích một phần từ hai lọ \(i\) và \(j\) này, trộn chúng lại trong một ống nghiệm mới. Giả sử rằng mỗi lọ ban đầu chứa đủ lượng để tiến hành trộn như trên. Để thuận tiện trong việc khảo sát, các nhà nghiên cứu đã sắp xếp lại \(\frac{n \times (n - 1)}{2}\) ống nghiệm mới chứa các chất được tạo thành theo thứ tự tăng dần về số hiệu. Họ cũng lần lượt đánh chỉ số các ống nghiệm mới tạo được này các số thứ tự \(1, 2, 3, \ldots, \frac{n \times (n - 1)}{2}\). Người ta muốn biết số hiệu của chất được chứa trong ống nghiệm có số thứ tự \(k\) là bao nhiêu?

Yêu cầu: Cho biết \(n, c, k\). Hãy tìm chất thứ \(k\) sau khi xếp.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, k\) \(\left(2 \leq n \leq 10^{6}, 1 \leq k \leq \frac{n \times (n - 1)}{2} \right)\) là số lọ trong phòng thí nghiệm, và thứ tự của chất ta muốn khảo sát trong số các ống nghiệm sẽ tạo ra được.
• Dòng thứ hai chứa \(n\) số \(c_{1}, c_{2}, \ldots, c_{n}\) \((1 \leq c_{i} \leq 10^{18})\) là số hiệu của chất được chứa trong các lọ ban đầu.
• Lưu ý rằng có thể có hai lọ khác nhau cùng chứa một chất, tức \(c_{i} = c_{j}\) với \(i \neq j\).

Output

• In ra số hiệu của chất thứ \(k\) sau khi sắp xếp.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 1000\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 10^{5}\).
• Subtask \(3\) (\(30\%\) số điểm): mỗi \(c_{i}\) đều có dạng \(c_{i} = 2^{x_{i}}\) trong đó \(x_{i}\) là một số nguyên không âm.
• Subtask \(4\) (\(15\%\) số điểm): không có ràng buộc gì thêm.

Example

5 7
2 3 9 14 12

12

Công ty viễn thông Sunchain (trực thuộc tập đoàn Edison chuyên sản xuất xe máy điện) đang thử nghiệm công nghệ mạng không dây mới.

Mạng lưới thử nghiệm hiện tại gồm \(n\) trạm phát sóng, được kết nối với nhau thông qua \(n - 1\) đường dây mạng. Đường dây thứ \(i\) kết nối giữa trạm \(u_{i}\) và \(v_{i}\), và có chiều dài là \(w_{i}\) mét. Việc kết nối các trạm đảm bảo thông tin luôn được truyền tải giữa hai trạm phát sóng bất kỳ.

Mỗi trạm phát sóng sẽ hoạt động ở một trong hai trạng thái: chế độ hoạt động (vừa phát tín hiệu mới, vừa nhận thông tin hoặc trung chuyển truyền tin từ trạm này sang trạm khác), hoặc chế độ nghỉ ngơi (chỉ nhận thông tin hoặc trung chuyển truyền tin). Khi phát một tín hiệu từ trạm \(s\) gửi tới trạm \(t\) bất kỳ, chi phí truyền tin sẽ bằng tổng độ dài của các đường dây mạng trên đường đi đơn duy nhất đi từ \(s\) đến \(t\).

Các kỹ sư có kế hoạch thử nghiệm sơ bộ \(q\) lần. Vì đang trong quá trình thử nghiệm, đôi khi các kỹ sư của Sunchain sẽ cho một số trạm nghỉ ngơi. Ở lần thử nghiệm thứ \(i\), các kỹ sư sẽ bật \(k_{i}\) trạm phát sóng \(s_{1}, s_{2}, \ldots, s_{k_{i}}\) ở chế độ hoạt động, và các trạm còn lại được cho nghỉ ngơi.

Cơ chế thử nghiệm tương đối đơn giản: Chọn ra một trạm phát sóng tiếp nhận \(T_{i}\) (có thể hoạt động hoặc là nghỉ ngơi) để thu thập dữ liệu. Tất cả \(k_{i}\) trạm này sẽ cùng nhau phát tín hiệu gửi tới trạm \(T_{i}\), và chi phí cho việc thử nghiệm này bằng tổng chi phí truyền tin của từng trạm hoạt động tới trạm tiếp nhận \(T_{i}\).

Sunchain đang trong giai đoạn khó khăn, nên việc thử nghiệm cũng cần phải tiết kiệm.

Yêu cầu: với mỗi lần thử nghiệm sơ bộ, bạn hãy chọn ra trạm tiếp nhận sao cho chi phí thử nghiệm là thấp nhất nhé!

Input

• Dòng đầu tiên lần lượt gồm hai số nguyên dương \(n\) và \(q\) \((1 \leq n \leq 5 \times 10^{5}, 1 \leq q \leq 10^{5})\) là số trạm phát sóng và số thử nghiệm.
• \(n - 1\) dòng tiếp theo, dòng thứ \(i\) lần lượt gồm ba số \(u_{i}, v_{i}, w_{i}\) \((1 \leq u_{i}, v_{i} \leq n, u_{i} \neq v_{i}, 1 \leq w_{i} \leq 10^{6})\) thể hiện một đường dây kết nối giữa trạm \(u_{i}\) và \(v_{i}\) có chiều dài là \(w_{i}\) mét.
• \(q\) dòng tiếp theo, dòng thứ \(j\) bắt đầu bằng số nguyên dương \(k_{j}\), kế đến là \(k_{j}\) số phân biệt \(s_{1}, s_{2}, \ldots, s_{k_{j}}\) \((1 \leq k_{j} \leq n, 1 \leq s_{i} \leq n)\), thể hiện một lần thử nghiệm.
• Dữ liệu đảm bảo \(\sum_{j = 1}^{q} k_{j} \leq 5 \times 10^{5}\).

Output

• In ra \(q\) dòng, dòng thứ \(j\) chứa duy nhất một số \(c_{j}\), cho biết chi phí tối thiểu trong lần thử nghiệm sơ bộ thứ \(j\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 500\).
• Subtask \(2\) (\(20\%\) số điểm): \(k_{j} = 2\).
• Subtask \(3\) (\(20\%\) số điểm): \(k_{j} = 3\).
• Subtask \(4\) (\(20\%\) số điểm): \(q = 1\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

8 3
1 2 2
1 3 3
2 4 4
3 5 3
3 6 5
6 7 1
6 8 6
2 2 8
3 4 7 8
4 1 5 7 8

16
21
23