Chọn ĐTQG An Giang 2025 - TEXT
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Các nhà khoa học đang tiến hành một cuộc khảo sát ~m~ mẫu vật trong phòng thí nghiệm. Mỗi mẫu vật được mô tả bởi ~n~ thuộc tính khác nhau. Các thuộc tính được đánh số từ ~1~ đến ~n~.
Để thuận tiện cho việc ghi chép, mỗi mẫu vật được biểu diễn bởi một xâu ký tự độ dài ~n~, trong đó:
Ký hiệu "+": thể hiện mẫu vật có thuộc tính tại vị trí tương ứng;
Ký hiệu "-": thể hiện mẫu vật không có thuộc tính đó.
Như vậy, toàn bộ dữ liệu gồm ~m~ xâu ký tự, mỗi xâu mô tả một mẫu vật.
Ký hiệu ~v_i~ là xâu biểu diễn mẫu vật thứ ~i~ ~(1 \le i \le m)~.
Hai mẫu vật ~v_i~ và ~v_j~ được so sánh dựa trên các thuộc tính của chúng. Ta nói ~v_i~ bao hàm ~v_j~ nếu thỏa mãn đồng thời hai điều kiện sau:
Mọi thuộc tính mà ~v_j~ có thì ~v_i~ cũng có.
Tồn tại ít nhất một thuộc tính mà ~v_i~ có nhưng ~v_j~ không có.
Ví dụ:
Với ~u =~ ++++-, ~v =~ ++---: tập thuộc tính của ~v~ là con của tập thuộc tính ~u~, đồng thời ~u~ còn có thêm thuộc tính mà ~v~ không có, nên ~u~ bao hàm ~v~.
Với ~u =~ +-+-+, ~v =~ ----+: mọi thuộc tính của ~v~ đều xuất hiện trong ~u~, và ~u~ có thêm thuộc tính khác, nên ~u~ bao hàm ~v~.
Với ~u =~ +-+-+, ~v =~ ++++-: tồn tại thuộc tính mà ~v~ có nhưng ~u~ không có, nên ~u~ không bao hàm ~v~.
Với ~u =~ ++++-, ~v =~ ----+: mỗi mẫu vật đều có những thuộc tính mà mẫu vật còn lại không có, nên không có quan hệ bao hàm giữa hai mẫu vật này.
Yêu cầu: Để đánh giá mức độ đa dạng của tập mẫu vật, các nhà khoa học định nghĩa một giá trị nghiên cứu bằng số lượng cặp chỉ số ~(i,j)~ ~(1 \le i,j \le m)~ sao cho mẫu vật ~v_i~ bao hàm mẫu vật ~v_j~. Hãy tính giá trị này.
Input
Dòng đầu tiên chứa hai số nguyên ~m~ và ~n~ ~(1 \le m \le 2 \cdot 10^5; 1 \le n \le 20)~.
Dòng thứ ~i~ ~(1 \le i \le m)~ trong ~m~ tiếp theo chứa một xâu gồm ~n~ ký tự "+" và "-".
Output
Một số nguyên duy nhất là giá trị nghiên cứu tìm được.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~30\%~ | ~m \le 300~; ~n \le 10~; |
| 2 | ~30\%~ | ~n \le 3~; |
| 3 | ~40\%~ | Không có ràng buộc nào thêm. |
Sample Input 1
5 5
++++-
++---
+-+-+
----+
---+-
Sample Output 1
3
Sample Input 2
3 3
+--
--+
-+-
Sample Output 2
0
Bình luận