55 Năm (ICPC KC)
Start of Real
KC năm nay tổ chức hoạt động Kỉ niệm 60 năm thành lập trường. Do khoảng cách xa xôi, di chuyển không thuận lợi, lại vướng lịch học tập, cậu không thể về dự chuỗi hoạt động này. Ngồi ở nhà, cậu lại nhớ về khoảng thời gian mình học cấp ba. Cậu nhớ từng tiết học (mà cậu không học), những ngày dậy 8 giờ (tại cậu học đội tuyển) hay những buổi đi ôn thi đại học với bạn (vì cậu hơn thua).
Nhưng chắc chắn rằng, cậu không thể quên đến cuộc thi ICPC Kỉ niệm 55 năm năm đó. Đó là một kì thi đặc biệt, do một người anh huyền thoại, vừa là anh, vừa là thầy của cậu, người đã dạy cậu dòng code C++ đầu tiên, đứng ra chuẩn bị và tổ chức. Kì thi được tổ chức online giữa mùa Cô Vít. Cậu không nhớ tại sao bản thân lại không có chút kí ức nào về việc cậu có tham gia hay không? Tuy nhiên, cậu vẫn rất hoài niệm về thời gian đó.
End of Real
Một trong những bài toán khiến cậu luôn đau đáu về nó chính là bài tập đầu tiên. Bài cho hai dãy số nguyên \(a_1,a_2,...,a_N\) và \(b_1,b_2,...,b_M\). Bài tập đó yêu cầu cậu đếm lượng cặp tập hợp \(A=\{i_1,i_2,...,i_k\}\) và \(B=\{j_1,j_2,...,j_k\}\) với \(1\le i_1 < i_2 < ... < i_k \le N\) và \(1 \le j_1 < j_2 <... < j_k \le M\) sao cho \(a_{i_p}=b_{j_p}\) với mọi \(1\le p \le k\).
Một cách tổng quát hơn, đó là đếm số lượng cặp đoạn con trên dãy \(a\) và trên dãy \(b\) giống nhau. Hai đoạn con trên một dãy được xem là khác nhau khi có ít nhất một cặp phần tử có chỉ số khác nhau.
Dù cho hiện tại cậu đã code được, nhưng vẫn không tin tưởng lắm, cậu muốn so sánh kết quả với một code chuẩn chỉ hơn. Hãy giúp Eme!
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên dương \(N, M \ (1\le N, M \le 10^3)\);
- Dòng thứ hai chứa \(N\) số nguyên \(a_i \ (1\le a_i \le 10^5)\);
- Dòng thứ ba chứa \(M\) số nguyên \(b_i \ (1 \le b_i \le 10^5)\).
Kết quả
- Kết quả bài toán sau khi chia lấy dư cho \(10^9+7\).
Chấm điểm
- Subtask 1 (20%): \(a_1=a_2=...=a_N; b_1=b_2=...=b_M\).
- Subtask 2 (10%): \(N=M; a_i=b_i=i\).
- Subtask 3 (30%): \(N, M \le 10\).
- Subtask 4 (40%): Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
2 2
1 3
3 1
output
3
Ví dụ 2
input
4 4
3 4 5 6
3 4 5 6
output
16
Giải thích
Các cặp thỏa mãn là:
- \(A= \emptyset\) và \(B= \emptyset\)
- \(A= \{1\}\) và \(B= \{2\}\)
- \(A= \{2\}\) và \(B= \{1\}\)
Comments