Một số bài

Phép nhân hai ma trận chỉ thực hiện được khi số cột của ma trận bên trái bằng số dòng của ma trận
bên phải. Nếu ma trận \(A\) có kích thước \(m\) x \(n\) và ma trận \(B\) có kích thước \(n\) x \(p\) , thì ma trận
tích C = \(A\) x \(B\) có kích thước \(m\) x \(p\) , phần tử đứng ở hàng thứ \(i\), cột thứ \(j\) xác định bởi:

\(c_{i,j} = a_{i,1}b_{1,j} + a_{i,2}b_{2,j} + \dots + a_{i,n}b_{n,j}\)

Phép nhân ma trận có các tính chất kết hợp: (\(A\) x \(B\)) x \(C\) = \(A\) x (\(B\) x \(C\))

Ví dụ:
\(A = \binom{0, 1}{1, 1}; A^2 = \binom{1, 1}{1, 2}; A^3 = \binom{1, 2}{2, 3}\)

Yêu cầu: Cho ma trận \(A\) kích thước \(n\) x \(n\) và ma trận B, hãy kiểm tra xem \(A^3\) có bằng hay \(B\) không?

Input

• Dòng thứ nhất chứa số nguyên dương \(T\) \((T \leq 20)\) là số lượng bộ dữ liệu;
• Tiếp theo là \(T\) nhóm dòng, mỗi nhóm dòng tương ứng với một bộ dữ liệu có dạng:
• Dòng đầu chứa số nguyên \(n\);
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên mô tả ma trận \(A\), các số có giá trị tuyệt đối không vượt quá 1000;
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên mô tả ma trận \(B\), các số có giá trị tuyệt đối không vượt quá 10^18.

Output

Ghi ra thiết bị ra chuẩn gồm \(T\) dòng, mỗi dòng là kết quả tương ứng với một bộ dữ liệu theo thứ tự xuất hiện trong file dữ liệu vào: ghi thông báo ‘YES’ nếu \(A^3 = B\) và ghi ‘NO’ trong trường hợp ngược lại.

Scoring

• Có \(50\)% số test ứng với \(50\)% số điểm của bài thỏa mãn: \(n \leq 10\);
• \(50\)% số test còn lại ứng với \(50\)% số điểm của bài thỏa mãn: \(n \leq 500\).

Example

2
2
0 1 
1 1
1 2
2 2
2
0 1 
1 1
1 2
2 3

NO
YES

Cho một số \(X\). Ta gọi \(BQ(X)\) là số BeautiQ thứ \(X\).

Số BeautiQ được xác định qua công thức như sau:

• \(BQ(0)=A,BQ(1)=B\), với \(A,B\) cho trước.
• \(BQ(X)=BQ(X−1)+BQ(X−2)+BQ(X−1) \times BQ(X−2). \ (X \geq 2)\)

Cho \(Q\) truy vấn, truy vấn thứ \(i\) gồm 3 số nguyên dương \(N_i,A_i,B_i\). Với truy vấn thứ \(i\), tính \(BQ(N_i)\) \(mod\) \((10^9+7)\) với \(BQ(0)=A_i,BQ(1)=B_i\).

Input

• Dòng đầu tiên chứa số nguyên dương \(Q\) là số truy vấn.
• \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa 3 số nguyên dương \(N_i,A_i,B_i\) thể hiện cho truy vấn thứ \(i\).

Output

• Ghi ra \(Q\) dòng, dòng thứ \(i\) là kết quả cho truy vấn thứ \(i\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(Q \leq 10^2;N_i,A_i,B_i \leq 5 \times 10^5\).
• Subtask \(2\) (\(70\%\) số điểm): \(Q \leq 10^4;N_i \leq 10^{18};A_i,B_i \leq 10^{12}\)

Example

2
5 1 1
4 2 5 

255
1943

Công ty của bạn có \(n\) lập trình viên và mỗi người trong số họ có trình độ kĩ năng từ \(0\) đến \(100\). Nhiệm vụ của bạn là chia các lập trình viên thành các nhóm làm việc cùng nhau.

Dựa trên kinh nghiệm của mình, bạn biết rằng các nhóm làm việc tốt khi trình độ kĩ năng của các lập trình viên là như nhau. Vì lí do này, hình phạt cho việc tạo ra một đội là sự khác biệt về trình độ kĩ năng giữa lập trình viên giỏi nhất và xấu nhất.

Bạn có thể chia các lập trình viên thành các đội sao cho tổng số tiền phạt nhiều nhất là \(x\) bằng bao nhiêu cách?

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng lập trình viên và tổng hình phạt tối đa cho phép.
• Dòng tiếp theo chứa \(n\) số nguyên \(t_1, t_2, \ldots, t_n\): trình độ kĩ năng của mỗi lập trình viên.

Output

• In một số nguyên: số phép chia hợp lệ chia lấy dư cho \(10^9 + 7\).

Constraints

• \(1 \leq n \leq 100\)
• \(0 \leq x \leq 5000\)
• \(0 \leq t_i \leq 100\)

Example

3 2  
2 5 3

3

Để trang trí Tết, Nam treo một dây đèn gồm \(N\) bóng đèn, được đánh số từ \(1\) đến \(N\), từ trái sang phải. Mỗi bóng đèn khi bật sẽ có hai màu vàng hoặc đỏ. Dây đèn được nhúng một mã lệnh cho phép nhận một số tự nhiên \(X\). Khi đó, màu của bóng đèn thứ \(X\) và các bóng đèn cách bóng đèn thứ \(X\) không quá \(K\) bóng đèn sẽ đều đổi từ vàng thành đỏ hoặc ngược lại.
Ban đầu các bóng đèn đều có màu vàng. Để dây đèn trông đẹp mắt, Nam đã lập trình để điều khiển màu của các bóng đèn. Chương trình của Nam có \(M\) dòng lệnh, mỗi dòng lệnh tương ứng với một lần gọi mã lệnh của dây đèn. Vì số lượng bóng đèn quá lớn, sau khi lập trình xong, Nam muốn kiểm tra ngẫu nhiên màu một số bóng đèn xem có đúng như ý tưởng ban đầu không.

Yêu cầu

Cho các số tự nhiên \(X\) là tham số của \(M\) dòng lệnh trong chương trình của Nam. Hãy lập trình để trả lời \(Q\) câu hỏi tương ứng với các lần kiểm tra của Nam. Biết rằng mỗi câu hỏi chứa một số nguyên dương \(P\) để xác định xem bóng đèn thứ \(P\) trong dây đèn có màu vàng hay đỏ.

Dữ liệu đầu vào

• Dòng đầu tiên gồm bốn số nguyên dương lần lượt là \(N, M, Q, K (1 \le N \le 10^9; 1 \le M \le 10^5; 1 \le Q \le 10^5; 0 < K \le N)\);
• Dòng thứ hai gồm \(M\) số nguyên dương \(X_i\) mô tả tham số của lệnh thứ \(i (1 \le X_i \le N)\);
• Dòng thứ ba gồm \(Q\) số nguyên dương \(P_i\) mô tả câu hỏi thứ \(i (1 \le P_i \le N)\).

Dữ liệu đầu ra

• Gồm \(Q\) dòng, dòng thứ \(i\) là câu trả lời cho câu hỏi thứ \(i\). Nếu bóng đèn tại vị trí \(P_i\) đang có màu vàng thì ghi ra ký tự \(V\), ngược lại ghi ra kí tự \(D\).

Ràng buộc dữ liệu

• Có 60% số test ứng với 60% số điểm của bài thỏa mãn: \(N, M, Q \le 10^3\);
• Có 20% số test ứng với 20% số điểm của bài thỏa mãn: \(N, M \le 10^5\);
• Có 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm

Ví dụ

7 2 4 1
3 5
2 7 4 5

D
V
V
D