Contest của GS.PVH ngày 2

Trong hoàn cảnh dịch bệnh COVID-19 diễn biến phức tạp và trước biến thể Delta lây lan nhanh đe dọa hệ thống y tế, việc áp dụng giãn cách xã hội là biện pháp hiệu quả để ngăn chặn sự gia tăng số ca nhiễm, thông qua việc hạn chế tiếp xúc giữa người với người. Tuy nhiên, áp dụng giãn cách xã hội để lại nhiều hệ lụy về kinh tế và đời sống của người dân như đứt gẫy chuỗi cung ứng hàng hóa thiết yếu, gia tăng số người mất việc làm hay làm gián đoạn nhiều hoạt động khác. Vì vậy, quyết định có áp dụng giãn cách xã hội hay không đòi hỏi sự cân nhắc về nhiều mặt như tính cấp thiết và tác động lâu dài.

Quốc gia X có \(n\) thành phố, các thành phố được đánh số từ \(1\) tới \(n\). Mạng lưới giao thông đường bộ của quốc gia này gồm \(m\) con đường hai chiều được đánh số từ \(1\) đến \(m\), con đường thứ \(j\) nối thành phố \(u_j\) với thành phố \(v_j\). Nhằm xây dựng các kịch bản ứng phó khi dịch COVID-19 bùng phát trong cộng đồng, chính phủ quốc gia X tiến hành đánh giá mức độ cản trở giao thông nếu một thành phố hoặc một con đường bị phong tỏa. Cụ thể, mức độ cản trở giao thông khi phong tỏa con đường thứ \(j\) là số cặp thánh phố \((x, y)\) không thể đi được tới nhau nếu chỉ riêng con đường thứ \(j\) bị xóa khỏi mạng lưới giao thông. Tương tự, mức độ cản trở giao thông khi phong tỏa thành phố thứ \(i\) là số cặp thành phố \((x, y)\) (với \(x \cdot y + i^2 \neq (x + y) \cdot i\)) không thể đi được tới nhau nếu chỉ riêng thành phố thứ \(i\) bị xóa khỏi mạng lưới giao thông. Chú ý rằng, khi một thành phố bị phong tỏa, các con đường nối trực tiếp với thành phố này cũng bị phong tỏa theo.

Các bạn hãy giúp chính phủ quốc gia X tính mức độ cản trở giao thông khi phong tỏa của mỗi thành phố và mỗi con đường nhé.

Input

• Dòng đầu tiên chứa số nguyên \(\theta\) \((1 \leq \theta \leq 4)\) là số thứ tự của subtask chứa test này.

• Dòng thứ hai chứa hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 3 \cdot 10^5, n - 1 \leq m \leq 3 \cdot 10^5)\) lần lượt là số thành phố và số con đường ở quốc gia X.

• Trong \(m\) dòng còn lại, dòng thứ \(j\) chứa hai số nguyên \(u_j\) và \(v_j\) \((1 \leq u_j, v_j \leq n)\) mô tả con đường thứ \(j\).

Output

In ra hai dòng:

• Dòng đầu tiên chứa \(n\) số nguyên, trong đó số thứ \(i\) là mức độ cản trở giao thông khi phong tỏa thành phố thứ \(i\).
• Dòng thứ hai chứa \(m\) số nguyên, trong đó số thứ \(j\) là mức độ cản trở giao thông khi phong tỏa con đường thứ \(j\).

Do các kết quả có thể rất lớn, các bạn chỉ ghi ra phần dư của \(n + m\) giá trị trên khi chia cho \(998244353\).

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask \(1\) (\(13\) điểm): \(n \leq 300\) và \(m \leq 300\)
• Subtask \(2\) (\(17\) điểm): \(n \leq 3000\) và \(m \leq 3000\)
• Subtask \(3\) (\(17\) điểm): Mạng lưới giao thông có dạng cây. Nói cách khác, \(m = n - 1\) và các con đường không tạo thành chu trình.
• Subtask \(4\) (\(23\) điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(70\) điểm.

Example

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

0 0 6 6 0 0
0 0 0 9 0 0 0

Rảnh rỗi vì không có ngiu, GS. PVH lấy giấy ra vẽ cây. GSPVH đã vẽ được một cây gồm \(n\) đỉnh và đánh số các đỉnh từ \(1\) đến \(n\).

Nhắc lại, cây là đồ thị vô hướng phi chu trình. Một cây gồm \(n\) đỉnh chắc chắn có \(n - 1\) cạnh.

Sau khi vẽ xong, GS. PVH chọn ra \(k\) đỉnh phân biệt trên cây và tô các đỉnh này bằng màu xanh lá cây. Tiếp theo đó, GS lại tiếp tục tô màu vàng vào những đỉnh mà GS coi là "xung yếu". Một đỉnh được GS coi là "xung yếu" khi và chỉ khi đỉnh này không được tô màu xanh lá cây; và nếu xóa đỉnh này ra khỏi cây, sẽ có hai đỉnh nào đó vừa được tô màu xanh lá cây không thể đi tới nhau nữa.

Tô màu đủ kiểu rồi, vẫn thấy mình còn dư quá nhiều thời gian, GS. PVH quyết định vẽ một bức tranh "siêu to khổng lồ to nhất Việt Nam" bằng việc liệt kê tất cả các cách chọn ra \(k\) đỉnh trong số \(n\) đỉnh của cây. Sau đó, với mỗi cách chọn, GS lại vẽ ra một cây và tô hai màu xanh lá cây và vàng vào các đỉnh theo quy tắc ở trên.

Thế nhưng, GS sắp hết bút sáp màu vàng. Vì vậy, GS. muốn nhờ bạn tính tổng số đỉnh được tô màu vàng trong bức tranh siêu to khổng lồ của mình.

Để làm khó bạn hơn, GS cho bạn trước một con số \(p\) và yêu cầu bạn phải tính ra kết quả theo modulo \(p\). Các bạn hãy chiều GS nhé.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(k\) và \(p\) \((1 \leq k \leq n \leq 10^6, p \in \{10^9 + 19972207, 10^9 + 22071997\})\), lần lượt là số đỉnh trên cây, số đỉnh được GS. PVH lựa chọn để tô màu xanh lục và số \(p\) được nhắc đến trong đề bài.

• Trong \(n - 1\) dòng còn lại, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n)\) cho biết trên cây có một cạnh nối hai đỉnh \(u\) và \(v\).

Output

• In ra tổng số đỉnh màu vàng trong bức tranh của GS. PVH.

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask \(1\) (\(12.6\) điểm): \(n \leq 20\)
• Subtask \(2\) (\(8.4\) điểm): \(n \leq 5000\)
• Subtask \(3\) (\(7\) điểm): \(k = 1\)
• Subtask \(4\) (\(12.6\) điểm): \(k = 2\)
• Subtask \(5\) (\(11.2\) điểm): \(p = 10^9 + 19972207\)
• Subtask \(6\) (\(18.2\) điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(70\) điểm.

Example

6 3 1019972207
1 2
2 3
3 4
3 5
3 6

16

Tạm gác hết những âu lo lại :v cùng mình giải bài toán này nhé. Mình cho các bạn một xâu kí tự \(s\) gồm \(n\) chữ cái in thường và một số nguyên \(k\). Bạn hãy giúp mình đếm số xâu kí tự \(t\) độ dài \(n\) cũng chỉ gồm các chữ cái in thường thỏa mãn điều kiện sau đây: Có chính xác \(k\) cặp số nguyên \((l, r)\) với \(1 \leq l \leq r \leq n\) và xâu con liên tiếp của \(t\) từ vị trí \(l\) đến vị trí \(r\) có thứ tự từ điển lớn hơn xâu con liên tiếp của \(s\) từ vị trí \(l\) đến vị trí \(r\).

Nhắc lại, xâu \(a = a_1 a_2 \ldots a_n\) được gọi là có thứ tự từ điển lớn hơn xâu \(b = b_1 b_2 \ldots b_n\) khi và chỉ khi tồn tại chỉ số \(i\) sao cho:

• \(1 \leq i \leq n\)
• \(a_i > b_i\)
• Với mọi chỉ số \(j\) sao cho \(1 \leq j < i\), ta luôn có \(a_j = b_j\).

Ví dụ, "tranchau" có thứ tự từ điển lớn hơn "tocotoco", "anhhanh" có thứ tự từ điển lớn hơn "anhanhh", "nguvanloi" có thứ tự từ điển lớn hơn "bichphuong", "thilin" có thứ tự từ điển lớn hơn "thaozi", "ntha" có thứ tự từ điển lớn hơn "dxmh".

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((1 \leq n \leq 2000, 0 \leq k \leq 3000)\).
  Dòng thứ hai chứa xâu kí tự \(s\) gồm \(n\) chữ cái in thường.

Output

• In ra một số nguyên duy nhất là số xâu kí tự \(t\) thỏa mãn điều kiện trên. Do kết quả có thể rất lớn, bạn chỉ cần in ra đáp số theo modulo \(998244353\).

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask \(1\) (\(8\) điểm): \(n \leq 5\)
• Subtask \(2\) (\(8\) điểm): \(n \leq 10\)
• Subtask \(3\) (\(10\) điểm): \(n \leq 200\) và \(k \leq 300\)
• Subtask \(4\) (\(6\) điểm): \(k = 0\)
• Subtask \(5\) (\(12\) điểm): Xâu \(s\) chỉ gồm kí tự \(a\).
• Subtask \(6\) (\(16\) điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(60\) điểm.

Example

2 2
yy

26

2 3
yy

1