OLP MTTN 2022 - Vòng Chung kết - Bảng Siêu cúp

Thuận có một bảng gồm \(r\) hàng và \(c\) cột, mỗi ô trên bảng có ghi một chữ cái in hoa. Để làm giảm kích thước của bảng, Thuận muốn xóa đi một số cột của bảng này hoặc giữ nguyên, nhưng phải bảo đảm rằng, sau khi xóa, nếu ghép các kí tự trên một hàng để tạo thành xâu kí tự, \(r\) xâu kí tự tạo bởi \(r\) hàng phải đôi một phân biệt.

Yêu cầu: Hãy cho biết Thuận có bao nhiêu cách xóa (hoặc giữ nguyên) các cột để thỏa mãn điều kiện này. Hai cách được gọi là khác nhau nếu tồn tại một cột trong cách này không bị xóa còn trong cách kia thì bị xóa.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu tiên chứa hai số nguyên \(r (r \le 1000)\) và \(c\) là số hàng và số cột của bảng;
• Trong \(r\) dòng tiếp theo, mỗi dòng chứa \(c\) chữ cái in hoa mô tả bảng.

Output

Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số cách đếm được thỏa mãn điều kiện.

Scoring

• Subtask \(1\) (\(26\%\) số điểm): \(c \le 10\);
• Subtask \(2\) (\(32\%\) số điểm): \(c \le 15\);
• Subtask \(3\) (\(42\%\) số điểm): \(c \le 20\).

Example

3 3
ACD
BCE
BAD

4

Ngoài các kiến thức học trên trường, Thuận nhận thấy mình còn thiếu nội dung kiến thức. Qua tìm hiểu Thuận biết rằng, để bổ sung nội dung kiến thức thứ \(i (1 \le i \le n)\) , Thuận cần tham gia khóa học với chi phí là \(c_i\). Thuận đang dự định làm sản phẩm, sản phẩm thứ \(j (1 \le j \le m)\) sẽ đòi hỏi kiến thức sau:
\(s_{j_1}, s_{j_2}, ..., s_{j_{p_j}}\) (1 \le \(s_{j_1} < s_{j_2} < ... < s_{j_{p_j}} \le n\)) và nếu hoàn thành xong sản phẩm này Thuận sẽ bán và thu về được số tiền là \(t_j\) .Sắp tới, Thuận sẽ đăng kí học một số khóa học (hoặc không đăng kí học khóa học nào) và với các kiến thức mới đó Thuận sẽ làm tất các sản phẩm có thể làm được.

Yêu cầu: Gọi \(X\) là tổng chi phí tham gia các khóa học, \(Y\) là tổng tiền thu được từ các sản
phẩm mà Thuận có thể làm được, hãy giúp Thuận đăng kí các môn học để \(|Y - X|\) đạt giá trị
lớn nhất.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu chứa hai số nguyên dương \(n, m\);
• Dòng thứ hai gồm \(n\) số nguyên \(c_1, c_2, ..., c_n (1 \le c_i \le 10^6)\);
• Dòng thứ \(j (1 \le j \le m)\) trong \(m\) dòng tiếp theo mô tả thông tin về sản phẩm thứ \(j\) có khuôn dạng:
  • Đầu tiên là số nguyên \(t_j (t_j \le 10^6)\);
  • Tiếp theo là số nguyên \(p_j\);
  • Tiếp theo là \(p_j\) số nguyên \(s_{j_1}, s_{j_2}, ..., s_{j_{p_j}}\)

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là giá trị \(Y - X\) lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\) và \(m \le 100\);
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 100\) và \(m \le 20\);
• Subtask \(3\) (\(30\%\) số điểm): \(n, m \le 100\) và \(p_j = 2\);
• Subtask \(4\) (\(30\%\) số điểm): \(n, m \le 1000\).

Example

3 3
1 2 3
2 2 1 3
5 2 1 3
1 1 2

3

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

0

Khi nghiên cứu về lý thuyết đồ thị, Thuận đã tìm ra một đặc trưng cho cây. Cụ thể, với cây
gồm \(n\) đỉnh, đỉnh \(i (1 \le i \le n)\) có trọng số là \(w[i]\), gọi \(f(i, j)\) là độ mất cân bằng giữa hai
đỉnh \(i\) và \(j (1 \le i, j \le n)\), trọng số \(f(i, j)\) được tính bằng chênh lệnh trọng số giữa đỉnh có
trọng số lớn nhất với đỉnh có trọng số bé nhất trong các đỉnh nằm trên đường đi từ \(i\) đến \(j\)
(bao gồm cả \(i, j\)). Độ mất cân bằng \(T\) của cây là tổng độ mất cân bằng giữa mọi cặp đỉnh.

Yêu cầu: Cho một cây và trọng số các đỉnh, hãy tính giá trị \(T\).

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu chứa số nguyên dương \(n\);
• Dòng thứ hai gồm \(n\) số nguyên \(w_1, w_2, ..., w_n (1 \le w_i \le 10^6)\);
• Dòng thứ \(k (1 \le k \le n - 1)\) trong \(n - 1\) dòng tiếp theo chứa hai số \(u_k, v_k (1 \le u_k, v_k \le n)\)
  mô tả cạnh thứ \(k\) của cây.

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là giá trị \(T\) tính được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 700\);
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 7000\);
• Subtask \(3\) (\(20\%\) số điểm): \(1 \le w_i \le 2\);
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^5\);
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^6\);

Example

4
1 1 2 3
1 2
1 3
1 4

8

4
1 2 2 2
1 2
2 3
3 4

3

Các nhà khảo cổ vừa tìm thấy một siêu cân thăng bằng thời tiền sử. Cấu trúc của nó hoặc là chỉ bao gồm một móc treo tạ hoặc là gồm một thanh ngang độ dài nguyên dương, một dây treo chia thanh này thành hai cánh tay đòn có độ dài nguyên dương và mỗi đầu mút của thanh được treo một siêu cân thăng bằng. Các móc treo tạ sẽ được đánh số, việc đánh số các móc treo tạ cho một siêu cân được làm như sau:

• Nếu siêu cân chỉ bao gồm một móc treo tạ thì dùng số nguyên dương nhỏ nhất chưa dùng để đánh số cho móc treo này;
• Ngược lại, tiến hành đánh số các móc treo tạ cho siêu cân ở bên mút trái của thanh, sau đó đánh số các móc treo tạ cho siêu cân ở bên mút phải của thanh.

Khi treo các quả tạ có khối lượng nguyên dương vào các móc treo tạ, cân sẽ thăng bằng nếu với mọi thanh ngang, tỷ lệ giữa tổng khối lượng bên trái và tổng khối lượng bên phải bằng với tỷ lệ giữa độ dài cánh tay đòn bên phải và độ dài cánh tay đòn bên trái. Ta nói dãy nguyên dương \(a=(a_1,a_2,\ldots,\ a_k)\) là dãy cơ sở của một siêu cân nếu k bằng số móc treo tạ và khi treo các quả tạ vào các móc theo thứ tự thì siêu cân này thăng bằng, đồng thời tổng các số trong dãy a là nhỏ nhất có thể. Tổng các số trong dãy cơ sở của một siêu cân được gọi là số khối của siêu cân đó. Ví dụ siêu cân trong hình sau có cơ sở là \((2,3,5,3,1,1)\) và số khối là \(15\).

Dễ thấy mỗi siêu cân đều tồn tại và duy nhất một cơ sở. Giả sử \((a_1,a_2,\ldots,\ a_k)\) là cơ sơ của siêu cân ban đầu. Hiện tại có một số móc treo tạ đã bị hỏng. Việc phục chế là thay thế tất cả các móc treo tạ này, mỗi móc treo tạ được thay bằng một siêu cân có số khối tương đương với khối lượng quả tạ treo tại đó. Tức là nếu móc treo tạ thứ \(i\) bị hỏng, nó sẽ được thay thế bằng một siêu cân nào đó có số khối bằng \(a_i\). Các nhà khảo cổ đã thử nhiều cách phục chế khác nhau và ghi lại cơ sở của siêu cân sau phục chế.
Yêu cầu: Hãy đếm số dãy nguyên dương là cơ sở của ít nhất một siêu cân sau phục chế.

Input

Phần đầu của input mô tả cấu trúc của siêu cân đã cho. Cách mô tả cấu trúc của một siêu cân như sau:

• Chỉ gồm một số 0 nếu siêu cân là một móc treo tạ;
• Ngược lại sẽ gồm 3 phần:
  • Phần một gồm hai số nguyên dương L,R là độ dài cánh tay đòn bên trái và bên phải;
  • Phần hai mô tả cấu trúc của siêu cân được treo bên mút trái của thanh;
  • Phần ba mô tả cấu trúc của siêu cân được treo bên mút phải của thanh.

Phần sau của input mô tả các móc treo tạ bị hỏng, gồm một số nguyên dương \(m\) và \(m\) số nguyên dương phân biệt là chỉ số của các móc treo tạ đó.

Output

In ra một số nguyên là số dãy cơ sở khác nhau có thể có của siêu cân sau khi phục chế, do kết quả có thể rất lớn nên chỉ cần in ra phần dư khi chia cho \(({10}^9+7)\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1\le m,\ L,\ R\le10\) và số thanh ngang không quá \(30\);
• Subtask \(2\) (\(40\%\) số điểm): \(1\le m,\ L,\ R\le10\) và số thanh ngang không quá \({10}^4\);
• Subtask \(3\) (\(30\%\) số điểm): \(1\le m,\ L,\ R\le30\) và số thanh ngang không quá \({10}^5\).

Example

2 4
4 4
3 2
0
0
0
2 3
0
1 1
0
0
2 2 5

3