COCI 2020/2021 - Contest 6 - Anagramistica

View as PDF

Submit solution

Points: 0.70 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020-2021 / Contest 6
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Biljana thích giải ô chữ. Loại ô chữ mà cô ấy thích là ô chữ kiểu đảo chữ (phép đảo chữ ở đây có nghĩa là tạo ra một từ có nghĩa bằng cách sắp xếp lại các chữ cái trong từ ban đầu, chẳng hạn "binary" - nhị phân là một từ được tạo ra bằng cách đảo các chữ cái của "brainy" - thông minh): mỗi gợi ý là một từ được tạo ra bằng cách đảo các chữ cái của đáp án.

Biljana có một tập hợp ~n~ từ mà cô ấy nghĩ sẽ phù hợp với câu đố tiếp theo của cô. Cô ấy muốn chọn ra một tập con của tập ~n~ từ này, sao cho có đúng ~k~ cặp từ thỏa mãn: có thể đảo các chữ cái của từ thứ nhất để tạo ra từ thứ hai. Hãy giúp Biljana tính số tập con thỏa mãn.

Input

Dòng đầu tiên chứa số ~n~ ~(1 \le n \le 2000)~ và ~k~ ~(0 \le k \le 2000)~: Số từ mà Biljana nghĩ ra và số cặp từ cô ấy yêu cầu.

Mỗi dòng trong ~n~ dòng tiếp theo chứa một từ có tối đa ~10~ kí tự, và tất cả các kí tự đều là chữ cái viết thường. Tất cả các từ đôi một phân biệt.

Output

Số tập con thỏa mãn. Do kết quả có thể lớn, in ra kết quả modulo ~10^9 + 7~ ~(1000000007)~

Sample Input 1

3 1
ovo
ono
voo

Sample Output 1

2

Sample Input 2

5 2
trava
vatra
vrata
leo
ole

Sample Output 2

3

Sample Input 3

6 3
mali
lima
imal
je
sve
ej

Sample Output 3

6

Giải thích test đề 1:

Có ~2~ tập con có đúng một cặp từ thỏa mãn điều kiện là: {ovo, ono, voo} và {ovo, voo}

Subtask

  • ~38\%~ ~(8/21)~ số test có ~n \le 15~
  • ~19\%~ ~(4/21)~ số test tiếp theo có ~k \le 3~
  • ~42\%~ ~(9/21)~ số test còn lại không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.