LQDOJ CUP 2022 - Round 5

Ban đầu, An có một dãy nhị phân \(S\) độ dài \(n\) gồm toàn các số \(0\). An được thực hiện hai thao tác:

1. Gán giá trị \(0\) cho một đoạn liên tiếp có độ dài đúng bằng \(u\). Cụ thể hơn, bạn được chọn một giá trị \(i\) sao cho \(1 \leq i \leq n-u+1\) và gán \(S_k=0\) với \(i \leq k \leq i+u-1\).
2. Gán giá trị \(1\) cho một đoạn liên tiếp có độ dài đúng bằng \(v\). Cụ thể hơn, bạn được chọn một giá trị \(i\) sao cho \(1 \leq i \leq n-v+1\) và gán \(S_k=1\) với \(i \leq k \leq i+v-1\).

Nếu được thực hiện hai thao tác trên số lần tùy ý, An sẽ tạo ra được tổng cộng bao nhiêu dãy nhị phân khác nhau?

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(1 \leq T \leq 20\)) là số lượng test.
• Trong \(T\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(n\), \(u\) và \(v\) (\(1 \leq n \leq 2000\), \(1 \leq u, v \leq n\)).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) in ra phần dư trong phép chia đáp án của test thứ \(i\) cho \(10 ^ 9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(u = n\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 40\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 200\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 1 1
2 1 2
2 2 1
2 2 2
9 6 4

2
4
4
2
117

Trong buổi phỏng vấn xin việc vào vị trí kiến trúc sư mạng, bộ phận tuyển dụng đưa cho bạn câu hỏi như sau:

Hệ thống máy tính của công ty gồm \(n\) máy tính, máy thứ \(i\) (\(1 \leq i \leq n\)) có \(c_i\) cổng kết nối. Các máy tính được chia thành \(k\) trạm, trạm thứ \(j\) (\(1 \leq j \leq k\)) có \(x_j\) máy tính, mỗi máy tính thuộc đúng một trạm.

Có \(m\) yêu cầu dạng \((u,v)\): Mỗi máy trong trạm \(u\) muốn liên lạc với từng máy trong trạm \(v\). Ta cần thiết kế đường truyền tin giữa các trạm máy tính khác nhau, bằng cách thiết lập kết nối hai chiều giữa các cặp hai máy bất kì sao cho thỏa mãn \(m\) yêu cầu trên và số kết nối của mỗi máy không được vượt quá số cổng kết nối của máy đó. Biết rằng để máy này truyền được tin tới máy khác, có thể truyền trực tiếp hoặc gián tiếp qua một số máy trung gian nào đó.

Để đánh giá mức độ hiệu quả của mạng, người ta định nghĩa hàm \(f\):

• Giả sử tổng số kết nối là \(E\).
• Định nghĩa độ trễ mạng \(L\) như sau: xét cặp máy \((x,y)\) (\(x \neq y\)) bất kì, mà \(x\) có đường truyền đến \(y\). Đặt \(d(x,y)\) là đường truyền ngắn nhất (đi qua ít kết nối nhất) giữa hai máy này. Độ trễ \(L\) của hệ thống sẽ là \(\max(d(x,y))\) trong mọi cặp \((x,y)\) đó.
• Khi đó: \(f = E \cdot n + L\).

Hãy thiết kế một hệ thống mạng có \(f\) nhỏ nhất.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(k\) và \(m\) (\(1 \leq k \leq n \leq 10 ^ 5\), \(1 \leq m \leq \min(k^2, 10^5)\)) lần lượt là số máy, số trạm và số yêu cầu.
• Dòng tiếp theo chứa \(n\) số nguyên \(c_1, c_2, \ldots, c_n\) (\(2 \leq c_i \leq n\)) là số lượng cổng kết nối của mỗi máy.
• Tiếp theo là \(k\) nhóm dòng mô tả các trạm máy tính \(1,2,3,\ldots,k\):
  • Dòng đầu tiên chứa số nguyên \(x_j\) là số lượng máy của trạm thứ \(j\).
  • Dòng tiếp theo chứa \(x_j\) số nguyên là số hiệu của các máy.
  • Dữ liệu vào đảm bảo \(x_1 + x_2 + \ldots + x_k = n\) và số hiệu của mỗi máy khác nhau đôi một và tạo thành một hoán vị của \(\{1,2,3,\dots,n\}\).
• Trong \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) (\(1 \le u,v \le k\)) cho biết yêu cầu giữa hai trạm \(u\) và \(v\).

Output

• Dòng đầu tiên in ra số nguyên \(f\).
• Nếu \(E \leq 10^5\), in ra các cặp kết nối theo định dạng u v trong \(E\) dòng tiếp theo.

Nếu có nhiều cách nối khác nhau, bạn hãy in ra 1 cách nối bất kì. Chứng minh được luôn tồn tại cách nối các máy thỏa mãn các yêu cầu với giới hạn của đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 6\).
• Subtask \(2\) (\(30\%\) số điểm): \(c_i = n \ \forall 1 \leq i \leq n\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 3 2
3 3 3 
1
2
1
3
1
1
2 1
2 3

8
3 2
2 1

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

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

Cho một bảng \(n\) hàng, \(m\) cột. Người ta xét tất cả khả năng điền các số từ \(1\) đến \(k\) vào bảng. Một ô trong bảng được gọi là cực đại địa phương nếu như nó thoả mãn số được điền lớn hơn tất cả các ô cùng hàng và cùng cột. Hãy đưa ra giá trị \(\displaystyle \sum_{g \, = \, 0}^{n \, \cdot \, m} (g + 1) \cdot A(g)\) trong đó \(A(g)\) là số cách điền bảng sao cho có chính xác \(g\) ô cực đại địa phương.

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(1 \le T \le 5\)) là số lượng test.
• Trong \(T\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(n\), \(m\) và \(k\) (\(1 \leq n, m \leq 10^{10^6}\), \(1 \leq k \leq 10^6\)) lần lượt là số hàng, số cột của bảng và giá trị tối đa được điền.

Output

• Gồm \(T\) dòng, dòng thứ \(i\) in ra phần dư trong phép chia đáp án của test thứ \(i\) cho \(10 ^ 9 + 7\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \cdot m \le 10\), \(k \le 5\).
• Subtask \(2\) (\(20\%\) số điểm): \(n, m \le 2000\), \(k = 2\).
• Subtask \(3\) (\(30\%\) số điểm): \(n, m, k \le 200\).
• Subtask \(4\) (\(30\%\) số điểm): \(n, m \le 10^6\).
• Subtask \(5\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
7 1 3
4 2 3
8 1 2
10 1 5
3 3 4

2642
10233
264
12589025
487936

5
5 1 4
7 1 2
2 4 5
2 4 5
5 2 2

1514
135
744625
744625
1184