1669E.md (2247B)
1 Source: https://codeforces.com/problemset/problem/1669/E 2 3 E. 2-Letter Strings 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given $n$ strings, each of length $2$, consisting of lowercase Latin alphabet letters from 'a' to 'k', output the number of pairs of indices $(i, j)$ such that $i \lt j$ and the $i$-th string and the $j$-th string differ in exactly one position. 22 23 In other words, count the number of pairs $(i, j)$ ($i \lt j$) such that the $i$-th string and the $j$-th string have exactly one position $p$ ($1 \leq p \leq 2$) such that ${s_{i}}_{p} \neq {s_{j}}_{p}$. 24 25 The answer may not fit into 32-bit integer type, so you should use 64-bit integers like long long in C++ to avoid integer overflow. 26 27 Input 28 29 The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows. 30 31 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of strings. 32 33 Then follows $n$ lines, the $i$-th of which containing a single string $s_i$ of length $2$, consisting of lowercase Latin letters from 'a' to 'k'. 34 35 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 36 37 Output 38 39 For each test case, print a single integer — the number of pairs $(i, j)$ ($i \lt j$) such that the $i$-th string and the $j$-th string have exactly one position $p$ ($1 \leq p \leq 2$) such that ${s_{i}}_{p} \neq {s_{j}}_{p}$. 40 41 Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++). 42 43 Example 44 45 Input 46 47 ``` 48 4 49 50 6 51 52 ab 53 54 cb 55 56 db 57 58 aa 59 60 cc 61 62 ef 63 64 7 65 66 aa 67 68 bb 69 70 cc 71 72 ac 73 74 ca 75 76 bb 77 78 aa 79 80 4 81 82 kk 83 84 kk 85 86 ab 87 88 ab 89 90 5 91 92 jf 93 94 jf 95 96 jk 97 98 jk 99 100 jk 101 ``` 102 103 Output 104 105 ``` 106 5 107 6 108 0 109 6 110 ``` 111 112 Note 113 114 For the first test case the pairs that differ in exactly one position are: ("ab", "cb"), ("ab", "db"), ("ab", "aa"), ("cb", "db") and ("cb", "cc"). 115 116 For the second test case the pairs that differ in exactly one position are: ("aa", "ac"), ("aa", "ca"), ("cc", "ac"), ("cc", "ca"), ("ac", "aa") and ("ca", "aa"). 117 118 For the third test case, the are no pairs satisfying the conditions.