bzoj#P3555. [CTSC2014] 企鹅 QQ

[CTSC2014] 企鹅 QQ

题目背景

Penguin QQ 是中国最大、最具影响力的 SNS(Social Networking Services)网站,以实名制为基础,为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验,满足用户对社交、资讯、娱乐、交易等多方面的需求。

题目描述

小 Q 是 Penguin QQ 网站的管理员,他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析,小 Q 发现同一个人注册的账户名称总是很相似的,例如 Penguin1Penguin2Penguin3……于是小 Q 决定先对这种相似的情形进行统计。

小 Q 定义,若两个账户名称是相似的,当且仅当这两个字符串等长且恰好只有一位不同。例如 Penguin1Penguin2 是相似的,但 Penguin12Penguin 不是相似的。而小 Q 想知道,在给定的 nn 个账户名称中,有多少对是相似的。

为了简化你的工作,小 Q 给你的 NN 个字符串长度均等于 LL,且只包含大小写字母、数字、下划线以及 @6464 种字符,而且不存在两个相同的账户名称。

输入格式

第一行包含三个正整数 N,L,SN,L,S。其中 NN 表示账户名称数量,LL 表示账户名称长度,SS 用来表示字符集规模大小,它的值只可能为 226464

SS 等于 22,账户名称中只包含字符 0122 种字符;

SS 等于 6464,账户名称中可能包含大小写字母、数字、下划线以及 @6464 种字符。

随后 NN 行,每行一个长度为 LL 的字符串,用来描述一个账户名称。数据保证 NN 个字符串是两两不同的。

输出格式

仅一行一个正整数,表示共有多少对相似的账户名称。

4 3 64
Fax
fax
max
mac
4

样例 1 解释

44 对相似的字符串分别为:FaxfaxFaxmaxfaxmaxmaxmac

数据范围

测试点编号 NN LL SS
11 5050 1010 6464
22 500500 100100
33 30003000 22
44 6464
55 3000030000 5050 22
66 6464
77 200200 22
88 6464
99 22
1010 6464