Link
CF1899 D Yarik and Musical Notes
Question
给出一个序列 \(a\) ,我们定义 \(b_i=2^{a_i}\)
求 \(b_i^{b_j}=b_j^{b_i} (i<j)\) 的个数
Solution
考虑化简式子
\[\begin{aligned}
& b_i^{b_j}=b_j^{b_i} \\
\Longleftrightarrow &2^{a_i^{2^{a_j}}}=2^{a_j^{2^{a_i}}}\\
\Longleftrightarrow &2^{a_i\cdot{2^{a_j}}}=2^{a_j\cdot{2^{a_i}}}\\
\Longleftrightarrow &a_i\cdot2^{a_j}=a_j\cdot{2^{a_i}}\\
\Longleftrightarrow &ln(a_i)+a_j\cdot ln2=ln(a_j)+{a_i}\cdot ln2\\
\Longleftrightarrow &ln(a_i)-{a_i}\cdot ln2=ln(a_j)-a_j\cdot ln2\\
\end{aligned}\]
这样,我们就把仅关于 \(a_i\) 的量移到了一边,把 \(a_j\) 的量移到了一边
对于每个 \(a_i\) 计算 \(ln(a_i)-a_i \cdot ln2\) 的值
然后排序,对于每个 \(ln(a_i)-a_i \cdot ln2\) 相同的 \(i\) 的值,假设为 \(p\) ,我们认为这 \(p\) 个数的两两组合都满足 \(b_i^{b_j}=b_j^{b_i}\),所以方案数就是 \(C_i^2\)
Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
const int maxn=2e5+5;
const double eps=1e-9;
int a[maxn];
double F[maxn];
void solve(){
int N=read(),ans=0;
for(int i=1;i<=N;i++){
a[i]=read();F[i]=(double)a[i]*log(2)-log(a[i]);
}
sort(F+1,F+1+N);
for(int i=1;i<=N;){
int R=i;
while(R+1<=N&&abs(F[i]-F[R+1])<eps) R++;
int num=R-i+1;
ans+=(num)*(num-1)/2;
i=R+1;
}
printf("%lld\n",ans);
}
signed main(){
// freopen("D.in","r",stdin);
int T=read();
while(T--)solve();
return 0;
}