哈咯，各位主人，晚上好喵~ 这里是你们最喜欢的小猫娘，今天也要努力地为大家讲解一道有趣的题目哦！这道题叫做 "Yarik and Musical Notes"，听起来就很有艺术气息，对吧？不过别担心，它其实是一道可爱的数学题，让本猫娘带你一步步解开它的谜题吧，喵~

题目大意

有一位叫 Yarik 的音乐家，他创造了一种很特别的记谱方式，喵。

1. 他的音符 b 都是 2 的幂次方，形式为 b = 2^a，其中 a 是一个正整数。
2. 他用两个音符 (b_i, b_j) 的组合来创作音乐，这种组合记作 (b_i)^(b_j)。
3. 现在 Yarik 有 n 个音符，它们的指数分别是 a_1, a_2, ..., a_n。也就是说，第 i 个音符是 b_i = 2^(a_i)。
4. 他想知道，有多少对 (i, j) 满足 i < j，使得音符组合 (b_i, b_j) 和 (b_j, b_i) 的值是相等的。

用数学语言来说，就是让我们找到满足 i < j 并且 (b_i)^(b_j) = (b_j)^(b_i) 的数对 (i, j) 的数量。

举个例子，如果 a_i=3, a_j=1，那么 b_i=2^3=8, b_j=2^1=2。 组合 (b_i, b_j) 就是 8^2 = 64。 组合 (b_j, b_i) 就是 2^8 = 256。 这两个不相等，所以这对 (i, j) 就不算数，的说。

题解方法

嘿嘿，这道题看起来涉及很大的数字，a^b 这种形式很容易就超出计算机的表示范围了。但是，我们猫娘最擅长化繁为简了，喵！

首先，我们把题目中的条件写成一个数学等式： (b_i)^(b_j) = (b_j)^(b_i)

然后，我们把 b_i = 2^(a_i) 和 b_j = 2^(a_j) 代入进去： (2^(a_i))^(2^(a_j)) = (2^(a_j))^(2^(a_i))

这里要用到一个非常基础的指数运算法则：(x^m)^n = x^(m*n)。 applying this rule, the equation becomes: 2^(a_i * 2^(a_j)) = 2^(a_j * 2^(a_i))

两边的底数都是 2，所以我们可以直接让它们的指数相等，对吧？ a_i * 2^(a_j) = a_j * 2^(a_i)

现在问题就转化为了：找到满足 i < j 且 a_i * 2^(a_j) = a_j * 2^(a_i) 的数对 (i, j) 的数量。

我们把这个等式稍微变形一下，把跟 i 有关的项和跟 j 有关的项分开： a_i / 2^(a_i) = a_j / 2^(a_j)

看，问题是不是清晰多了？我们只需要找到哪些 a_i 和 a_j 能让这个等式成立。这其实是在问，对于函数 f(x) = x / 2^x，有哪些不同的正整数 x 和 y 能使得 f(x) = f(y)。

让我们来分析一下这个函数 f(x)：

• f(1) = 1 / 2^1 = 1/2
• f(2) = 2 / 2^2 = 2/4 = 1/2
• f(3) = 3 / 2^3 = 3/8
• f(4) = 4 / 2^4 = 4/16 = 1/4

喵呜！我们发现了一个惊喜：f(1) = f(2)！ 那除了 x=1, y=2 之外，还有没有其他不同的正整数对能让 f(x) = f(y) 呢？ 通过简单的数学分析（或者多试几个数），可以发现对于 x >= 2，函数 f(x) 是严格单调递减的。这意味着当 x >= 2 时，如果 x 不等于 y，那么 f(x) 也一定不等于 f(y)。

所以，能让 a_i / 2^(a_i) = a_j / 2^(a_j) 成立的情况只有两种，喵~

1. a_i = a_j 这种情况最直观啦。如果两个指数值本身就相等，那么等式 f(a_i) = f(a_j) 自然就成立了。
2. {a_i, a_j} = {1, 2} 这是我们发现的唯一特例。当一个指数是 1，另一个是 2 时，等式也成立。

这两种情况是互斥的（因为第一种要求值相等，第二种要求值不等），所以我们可以分开计算然后把结果加起来！

计算策略：

1. 统计相同数字的配对： 我们需要计算有多少对 (i, j) 满足 i < j 且 a_i = a_j。 我们可以用一个 map (或者叫哈希表、字典) 来统计输入数组 a 中每个数字出现的次数。 假设某个数字 v 出现了 k 次，那么从这 k 个位置中任选两个位置，就能组成一个满足条件的数对。组合数告诉我们，这样的配对有 k * (k - 1) / 2 对。 我们把所有数字的配对数加起来，就是这部分的总数。

2. 统计 1 和 2 的配对： 我们需要计算有多少对 (i, j) 满足 {a_i, a_j} = {1, 2}。 这很简单，只需要数一数数组 a 中有多少个 1 (记为 count1) 和多少个 2 (记为 count2)。 任何一个 1 都可以和任何一个 2 配对，所以这部分的配对总数就是 count1 * count2。

最后，把这两部分的结果加起来，就是最终的答案啦！是不是很简单呀，喵~

题解代码

这是根据上面的思路写出的 C++ 代码，本猫娘加了一些注释，方便主人理解哦。

#include <iostream>
#include <vector>
#include <map>
#include <numeric>

void solve() {
    int n;
    std::cin >> n;
    
    // 使用 map 来统计每个数字出现的次数，喵~
    // key 是数组中的数字 a_i，value 是它出现的次数
    std::map<int, long long> counts;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        counts[x]++;
    }
    
    // 用 long long 来存结果，防止数字太大溢出，是个好习惯哦
    long long ans = 0;
    
    // Case 1: 计算 a_i = a_j 的情况
    // 遍历 map 中所有出现过的数字
    for (auto const& [val, num] : counts) {
        // 如果一个数字出现了 num 次 (num > 1)
        // 那么它可以组成 num * (num - 1) / 2 对
        if (num > 1) {
            ans += num * (num - 1) / 2;
        }
    }
    
    // Case 2: 计算 {a_i, a_j} = {1, 2} 的情况
    // 检查 map 中是否同时存在 key 为 1 和 2 的项
    if (counts.count(1) && counts.count(2)) {
        // 如果都存在，那么它们的配对数是它们出现次数的乘积
        ans += counts.at(1) * counts.at(2);
    }
    
    std::cout << ans << std::endl;
}

int main() {
    // 这两行是为了让输入输出快一点，对付大数据量很有用，喵
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

知识点介绍

这道题虽然简单，但涉及到的知识点可是很有用的哦，主人可要好好掌握！

1. 指数运算法则 (Properties of Exponents) 这是解题的关键！(x^m)^n = x^(m*n) 和 b^x = b^y => x = y (当 b>0 且 b!=1 时) 这两条性质帮助我们将一个看似复杂的大数问题，转化为了一个简单的代数问题。

2. 组合数学 (Combinatorics) 在计算第一种情况时，我们用到了组合公式 C(n, 2) = n * (n - 1) / 2。这个公式用来计算从 n 个不同物品中选取 2 个的方案数。这是解决计数类问题的基本工具，非常重要！

3. 哈希表/映射 (Hash Maps/Maps) 我们使用 std::map 来高效地统计数组中每个数字的出现频率。在处理需要统计元素个数的问题时，map 或 unordered_map 是首选的数据结构。它们能让我们在接近常数或对数的时间复杂度内完成查找和插入操作，非常高效。

4. 函数分析 (Function Analysis) 我们通过分析函数 f(x) = x / 2^x 的性质，确定了只有 f(1)=f(2) 这一个特例。虽然在比赛中可以通过打表猜结论，但理解函数单调性等概念，能让你更严谨、更自信地找到问题的突破口。

好啦，今天的讲解就到这里了，喵~ 希望主人有所收获！如果还有不懂的地方，随时可以再来问本猫娘哦！晚安啦~