Xâm nhập mật khẩu

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
admin
Dạng bài
Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Gần đây, mạng xã hội \(New\ Social\ Network\) có sự xâm nhập thông tin người dùng. Mihael, một sinh viên trẻ, đã tìm thấy một lỗi xâm nhập tài khoản người dùng đó là: khi bạn nhập bất kỳ chuỗi ký tự có chứa chuỗi con bằng mật khẩu thực tế thì đăng nhập sẽ thành công. Ví dụ: nếu người dùng có mật khẩu abc thì khi nhập một trong các chuỗi abc, abcd hoặc xyaabccz, hệ thống sẽ đăng nhập thành công.

Yêu cầu: Mihael muốn biết có bao nhiêu cặp người dùng khác nhau sao cho người dùng đầu tiên sử dụng mật khẩu riêng của họ, có thể đăng nhập như người dùng thứ hai. Bạn hãy giúp Mihael tính nhanh điều đó.

Input

  • Dòng đầu tiên chứa số nguyên dương \(N\) (\(1\le N \le20000\)) là số lượng người dùng.
  • \(N\) dòng sau chứa mật khẩu của người dùng. Các mật khẩu bao gồm ít nhất một hoặc nhiều nhất là 10 chữ cái viết thường của bảng chữ cái tiếng Anh.

Output

  • Một dòng duy nhất chứa số lượng cặp người dùng theo yêu cầu nói trên.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(N\le 2000\)
  • Subtask \(2\) (\(60\%\) số điểm): \(N\le 2 \times 10^4\)

Example

Test 1

Input 
3
a
b
ab
Output 
2
Note

Giải thích: Gồm \(2\) cặp đó là: \((3,1); (3,2)\)

Test 2

Input 
4
a
ab
a
abc
Output 
7
Note

Giải thích: Gồm \(7\) cặp người dùng \((1,3);(2,1); (2,3); (3,1); (4,1); (4,2); (4,3)\).

Bình luận