E - Choose Two and Eat One
非常巧妙的一集
可以将整个局面看作一张图，选两个数获得的score就是它们的边权，然后做最大生成树，不难发现操作和建树之间是一一对应的。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N=500+5;
const ll inf=1ll<<60;
struct node{
ll x,y,v;
};
node v[N*N];
ll f[N],a[N],n,m,tot,f1,f2;
ll find(ll x){
if (x==f[x]) return x;
return f[x]=find(f[x]);
}
ll power(ll a,ll b){
ll t=1,y=a;
while (b){
if (b&1) t=t*y%m;
y=y*y%m;
b/=2;
}
return t;
}
bool cmp(node a,node b){
return a.v>b.v;
}
int main()
{
// freopen("data.in","r",stdin);
scanf("%lld %lld",&n,&m);
fo(i,1,n) scanf("%lld",&a[i]);
fo(i,1,n) {
fo(j,i+1,n) {
v[++tot]=(node){i,j, (power(a[i],a[j])+power(a[j],a[i]))%m };
}
}
sort(v+1,v+tot+1,cmp);
fo(i,1,n) f[i]=i;
ll ans=0;
fo(i,1,tot) {
f1=find(v[i].x);
f2=find(v[i].y);
if (f1^f2) {
ans+=v[i].v;
f[f1]=f2;
}
}
printf("%lld",ans);
return 0;
}