题解：CF1899D Yarik and Musical Notes

原题链接

• 洛谷 CF1899D Yarik and Musical Notes

题意简述

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

解题思路

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

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

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

• $x=1,y=2$，选一个 $1$ 和一个 $2$，方案数为 $m_1\times m_2$；
• $x=y=i$，在所有的 $i$ 中选两个，方案数为 $C_{m_i}^2=\frac{m_i(m_i-1)}{2}$。

所以总方案数为 $m_1\times m_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:m)
		{
			ans+=x.second*(x.second-1)/2;
		}
		cout<<ans<<'\n';
	}
	return 0;
}