P4503 [CTSC2014] Penguin QQ

PenguinQQ is China’s largest and most influential SNS (Social Networking Services) website. Based on a real-name system, it provides powerful and rich Internet features such as blogs, groups, instant messaging, photo albums, and a marketplace, meeting users’ needs in socializing, information, entertainment, and transactions.

Xiao Q (pinyin) is an administrator of the PenguinQQ website. He is studying an interesting question: which accounts were registered by the same person. After long analysis, Xiao Q found that accounts registered by the same person usually have very similar names, such as Penguin1, Penguin2, Penguin3... So he decides to first count such similar cases. Xiao Q defines two account names to be similar if and only if the two strings have the same length and differ in exactly one position. For example, “Penguin1” and “Penguin2” are similar, while “Penguin1” and “2Penguin” are not. Given $n$ account names, he wants to know how many pairs are similar. To simplify your work, the $n$ strings all have length $L$, and they contain only uppercase and lowercase letters, digits, the underscore, and `@` — a total of $64$ characters. Moreover, no two account names are identical.

The first line contains three positive integers $N, L, S$. Here $N$ is the number of account names, $L$ is the length of each account name, and $S$ is the alphabet size, whose value is either $2$ or $64$. If $S$ equals $2$, account names contain only the characters `0` and `1`. If $S$ equals $64$, account names may contain uppercase and lowercase letters, digits, the underscore, and `@` — a total of $64$ characters. Then $N$ lines follow, each containing a string of length $L$ that describes an account name. It is guaranteed that the $N$ strings are pairwise distinct.

Output a single integer on one line, the number of pairs of similar account names.

The $4$ similar pairs are: Fax and fax, Fax and max, fax and max, max and mac. 测试点编号|$N$|$L$|$S$ :-:|:-:|:-:|:-: $1$|$50$|$10$|$64$ $2$|$500$|$100$|$64$ $3$|$3000$|$100$|$2$ $4$|$3000$|$100$|$64$ $5$|$30000$|$50$|$2$ $6$|$30000$|$50$|$64$ $7$|$30000$|$200$|$2$ $8$|$30000$|$200$|$64$ $9$|$30000$|$200$|$2$ $10$|$30000$|$200$|$64$ Translated by ChatGPT 5