Parametriziran
레이팅 미적용의견: 0
3 \(s / 64\) \(MB / 110\) points
A string of characters consisting of lowercase letters of the English alphabet and question marks is
called a parameterized word (e.g., a??cd , bcd , ?? ). Two parameterized words are considered similar
if the question mark symbols in both words can be replaced by arbitrary lowercase letters of the
english alphabet so that the resulting strings are the same. For example, parameterized words a???
and ?b?a are similar because by replacing the question marks in both words it is possible to obtain
the word abba .
Mirko has recently bought a collection of parametrized words. Among the \(N\) words found in the
collection, Mirko is interested in how many pairs of similar parameterized words exist. All the words in
the collection have the same number of characters, \(M\) , and it is possible that a word occurs multiple
times in the collection.
In the test samples totally worth 30% of the points it will be valid \(M\) ≤ 2.
In the test samples totally worth additional 30% points it will be valid \(M\) ≤ 4.
The first line contains the integer numbers N (\(1 \le N \le 50\,000\)) and M (\(1 \le M \le 6\)).
Each of the following \(N\) lines contains one parameterized word from the collection with exactly \(M\)
characters.
Print the total number of similar pairs of parameterized words.
3 3
??b
c??
c?c
4 6
ab??c?
??kll?
a?k??c
?bcd??
5 2
??
b?
c?
?g
cgoutput
output
2
3
8Explanation of the first test sample:
Pairs of similar words are: (??b, c??) and (c??, c?c).
평가 및 의견
Parametriziran
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Parametriziran