ABC282E快速幂最大生成树

#include <bits/stdc++.h>
#define N 505
using namespace std;
int mo, n, m, i, j, k, x, y, z, a[N], f[N];
long long s;
struct AB{
    int a, b, c;
    bool operator < (const AB &A) const{
        return c > A.c;
    }
} d[N*N];
int mi(long long a, int b){
    int s=1, i;
    while(b){
        if(b&1) s = s * a % mo;
        b /= 2, a = a * a % mo;
    }
    return s;
}
int find(int x){
    if(x == f[x]) return x;
    return f[x] = find(f[x]);
}
int main(){
    scanf("%d%d", &n, &mo);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
        for(j=1; j<i; j++){
            d[++m].a = j, d[m].b = i;//统计任意两个的分数
            d[m].c = (mi(a[j], a[i]) + mi(a[i], a[j])) % mo;
        }
    }
    sort(d+1, d+m+1);//不能有环取最大生成树
    for(i=1; i<=n; i++) f[i] = i;
    for(i=1; i<=m; i++){
        x = find(d[i].a), y = find(d[i].b);
        if(x == y) continue;
        s += d[i].c, f[x] = y;
        if(++z == n-1) break;
    }
    printf("%lld\n", s);
    return 0;
}