Link

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