AT_abc483_e.Typo Pairs

提高+/省选-

通过率:0%

时间限制:4.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are NN strings of length MM consisting of lowercase English letters. The ii-th string (1≤i≤N)(1\leq i\leq N) is SiS_i.

Find the number of integer pairs (i,j)(i,j) (1≤i<j≤N)(1\leq i < j \leq N) satisfying the following condition.

  • The Hamming distance between SiS_i and SjS_j is at most 22.

What is Hamming distance?

The Hamming distance between strings AA and BB, both of length kk, is the number of integers ii satisfying 1≤i≤k1\leq i\leq k such that the ii-th character of AA and the ii-th character of BB are different. For example, the Hamming distance between abc and bac is 22, and the Hamming distance between atcoder and contest is 77.

有 NN 个长度为 MM 的字符串,均由小写英文字母组成。第 ii 个字符串(1≤i≤N1\leq i\leq N)为 SiS_i。

请找出满足以下条件的整数对 (i,j)(i,j)(其中 1≤i<j≤N1\leq i < j \leq N)的个数:

  • SiS_i 与 SjS_j 的汉明距离至多为 22。

什么是汉明距离?

对于两个长度均为 kk 的字符串 AA 和 BB,其汉明距离定义为满足 1≤i≤k1\leq i\leq k 且 AA 的第 ii 个字符与 BB 的第 ii 个字符不同的整数 ii 的个数。例如,abc 与 bac 的汉明距离为 22,而 atcoder 与 contest 的汉明距离为 77。

输入格式

The input is given from Standard Input in the following format:

NN MM
S1S_1
S2S_2
⋮\vdots
SNS_N

输入从标准输入中按以下格式给出:

NN MM
S1S_1
S2S_2
⋮\vdots
SNS_N

输出格式

Print the number of integer pairs (i,j)(i,j) (1≤i<j≤N)(1\leq i < j \leq N) satisfying the condition.

输出满足条件的整数对 (i,j)(i,j) (1≤i<j≤N)(1\leq i < j \leq N) 的个数。

输入输出样例

  • 输入#1

    3 3
    abc
    abd
    bac

    输出#1

    2
  • 输入#2

    9 5
    aaaaa
    aaaaa
    aaaab
    aaaba
    aaabb
    aabaa
    aabab
    aabba
    aabbb

    输出#2

    31

说明/提示

Sample 1 Explanation:

  • The Hamming distance between S1=S_1=abc and S2=S_2=abd is 11.
  • The Hamming distance between S1=S_1=abc and S3=S_3=bac is 22.
  • The Hamming distance between S2=S_2=abd and S3=S_3=bac is 33.

Thus, the pairs satisfying the condition are the 22 pairs (i,j)=(1,2)(i,j)=(1,2), (1,3)(1,3), so print 22.

Sample 2 Explanation:
The same string may appear multiple times.

Constraints

  • 2≤N≤2×1052 \leq N \leq 2\times 10^5
  • 2≤M≤62 \leq M \leq 6
  • NN and MM are integers.
  • SiS_i is a string of length MM consisting of lowercase English letters.

样例 1 解释:

  • S1=S_1=abc 与 S2=S_2=abd 的汉明距离为 11。
  • S1=S_1=abc 与 S3=S_3=bac 的汉明距离为 22。
  • S2=S_2=abd 与 S3=S_3=bac 的汉明距离为 33。

因此,满足条件的数对为 (i,j)=(1,2)(i,j)=(1,2) 和 (1,3)(1,3),共 22 对,故输出 22。

样例 2 解释:
同一字符串可能出现多次。

约束条件

  • 2≤N≤2×1052 \leq N \leq 2\times 10^5
  • 2≤M≤62 \leq M \leq 6
  • NN 与 MM 均为整数。
  • 每个 SiS_i 是一个长度为 MM 的字符串,仅由小写英文字母组成。

输入解题思路,AI测评打分。不知道怎么写?

首页