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)}$。

解题思路

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

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

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

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

因此总方案数为：

$$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;
}