Với hai dãy số ~x~, ~y~; người ta định nghĩa ~x~ là dãy con của ~y~ nếu có thể thu được ~x~ bằng cách xóa đi một số phần tử của ~y~ (Có thể không xóa hoặc xóa tất cả) và giữ nguyên thứ tự các phần tử còn lại. Ví dụ:
~[1,3,5]~ là dãy con của ~[1,2,3,4,5]~
~[2,4]~ là dãy con của ~[1,2,3,4,5]~
~[2,1,3]~ không là dãy con của ~[1,2,3,4,5]~
Cho hai dãy ~a~, ~b~ có kích thước lần lượt là ~m~, ~n~. Định dãy con chung dài nhất của hai dãy ~a~ và ~b~ là dãy ~c~ dài nhất vừa là dãy con của ~a~, vừa là dãy con của ~b~; có thể tồn tại nhiều hơn một dãy như vậy. Hai dãy con chung dài nhất ~x~ và ~y~ gọi là khác nhau nếu tồn tại một vị trí ~i~ mà tại đó ~x_i \neq y_i~.
Yêu cầu: Bạn hãy tính độ dài và đếm số dãy con chung dài nhất của ~a~ và ~b~ nhé. Vì đáp án có thể rất lớn nên hãy in ra số dư khi chia cho ~123456789~.
Input
Dữ liệu vào từ file văn bản lcs.inp
- Dòng đầu chứa hai số nguyên dương ~m~, ~n~ (~1 \leq n, m \leq 10^4~) là kích thước hai dãy ~a~, ~b~.
- Dòng thứ hai chứa ~m~ số nguyên dương ~a_1, a_2, \cdots , a_m~ (~1 \leq a_i ≤ 10^9~) mô tả dãy ~a~.
- Dòng thứ ba chứa ~n~ số nguyên dương ~b_1, b_2, \cdots , b_n~ (~1 \leq b_i \leq 10^9~) mô tả dãy số ~b~.
Output
Kết quả in ra file văn bản lcs.out
- Hai số nguyên lần lượt là độ dài dãy con chung dài nhất của ~a~, ~b~ và số lượng dãy như vậy.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | 15% | ~m, n \leq 20~ |
2 | 20% | ~m, n \leq 500~ |
3 | 15% | ~m, n \leq 2000~ |
4 | 20% | Các số trong ~a~ phân biệt, các số trong ~b~ phân biệt. |
5 | 30% | Không có điều kiện gì thêm. |
Sample Input 1
2 2
1 1
2 2
Sample Output 1
0 1
Sample Input 2
3 3
1 2 2
2 1 1
Sample Output 2
1 2
Sample Input 3
4 4
4 3 2 1
2 3 4 1
Sample Output 3
2 3
Notes
Ở test thứ nhất: Có 1 dãy thỏa mãn là dãy rỗng.
Ở test thứ hai: Có 2 dãy thỏa mãn là ~[1], [2]~.
Ở test thứ nhất: Có 3 dãy thỏa mãn là ~[2, 1], [3, 1]~ và ~[4, 1]~.
Comments