题解：CF1899D Yarik and Musical Notes

· · 题解

题意简述

求数列 a 中有多少对 (a_i,a_j)（i<j），设 x=a_i,y=a_j，满足 (2^x)^{(2^y)}=(2^y)^{(2^x)}。

解题思路

作出 (2^x)^{(2^y)}=(2^y)^{(2^x)} 的图像：

不难发现只有 x=y 或 x=1,y=2（x\le y）时等式成立。

统计每个元素 i 的出现次数 m_i，然后对 (x,y) 分类讨论：

因此总方案数为：

m_1m_2+\sum\frac{m_i(m_i-1)}{2}

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        map<int,ll> m;
        for(int i=1;i<=n;i++)
        {
            int t;
            cin>>t;
            m[t]++;
        }
        ll ans=m[1]*m[2];
        for(auto [x,y]:m)ans+=y*(y-1)/2;
        cout<<ans<<'\n';
    }
    return 0;
}