← 返回题目列表

Codeforces · 1669/E

E. 2 字母字符串

中文机器翻译题面 查看原题

给定 $$$n$$$ 字符串,每个长度为 $$$2$$$,由从 'a' 到 'k' 的小写拉丁字母组成,输出索引对 $$$(i, j)$$$ 的数量,使得 $$$i < j$$$ 并且第 $$$i$$$ 字符串和第 $$$j$$$ 字符串在一个位置上完全相同。

换句话说,计算对 $$$(i, j)$$$ ($$$i < j$$$) 的数量,使得第 $$$i$$$ 字符串和第 $$$j$$$ 字符串恰好有一个位置 $$$p$$$ ($$$1 \leq p \leq 2$$$) 使得 $$${s_{i}}_{p} \neq {s_{j}}_{p}$$$。

答案可能不适合 32 位整数类型,因此您应该使用 64 位整数,例如 C++ 中的 long long 以避免整数溢出。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串的数量。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含长度为 $$$2$$$ 的单个字符串 $$$s_i$$$,由从 'a' 到 'k' 的小写拉丁字母组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印一个整数 - $$$(i, j)$$$ ($$$i < j$$$) 的对数,使得第 $$$i$$$ 字符串和第 $$$j$$$ 字符串恰好有一个位置 $$$p$$$ ($$$1 \leq p \leq 2$$$) 使得 $$${s_{i}}_{p} \neq {s_{j}}_{p}$$$。

请注意,某些测试用例的答案不适合 32 位整数类型,因此您应该在编程语言中至少使用 64 位整数类型(例如 C++ 的 long long)。

示例

输入 #1

4
6
ab
cb
db
aa
cc
ef
7
aa
bb
cc
ac
ca
bb
aa
4
kk
kk
ab
ab
5
jf
jf
jk
jk
jk

输出 #1

5
6
0
6

注意

对于第一个测试用例,仅在一个位置不同的对是:(“ab”,“cb”),(“ab”,“db”),(“ab”,“aa”),(“cb”,“db”)和(“cb”,“cc”)。

对于第二个测试用例,仅一个位置不同的对是:(“aa”,“ac”),(“aa”,“ca”),(“cc”,“ac”),(“cc”,“ca”),(“ac”,“aa”)和(“ca”,“aa”)。

对于第三个测试用例,没有满足条件的对。