Chọn ĐTQG An Giang 2025 - TEXT

Xem dạng PDF

Gửi bài giải

Điểm: 45,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong 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:

  1. Mọi thuộc tính mà ~v_j~ có thì ~v_i~ cũng có.

  2. 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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.