solution-at-abc282-e

IYSY2009I · 2022-12-26 10:44:10 · 题解

题面翻译

首先我们理解一个结论：如果我们把每个球看成一个点，把选择两个球并吃掉其中一个的过程看成在这两个点之间连边，那么最后连出来的一定是一棵树。这个结论可以根据树的定义通过归纳的方法证明。

于是我们把 x 和 y 之间的边权赋为 (x^y+y^x) \bmod M，然后跑最大生成树就可以了。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n;
long long m;
long long a[505];
int f[505];
struct edge{
    int u;
    int v;
    long long w;
};
edge e[200005];
int h[505];
int cnt;
void add(int x,int y,int z){
    cnt++;
    e[cnt].u=x;
    e[cnt].v=y;
    e[cnt].w=z;
}
bool cmp(edge x,edge y){
    return x.w>y.w;
}
int ff(int x){
    if(f[x]==x) return x;
    f[x]=ff(f[x]);
    return f[x];
}
bool fnd(int x,int y){
    if(ff(x)==ff(y)) return true;
    return false;
}
void merge(int x,int y){
    if(ff(x)!=ff(y)) f[ff(x)]=ff(y);
    return;
}
long long kruskal(){
    long long ans=0;
    for(int i=1;i<=cnt;i++){
        if(!fnd(e[i].u,e[i].v)){
            ans+=e[i].w;
            merge(e[i].u,e[i].v);
        }
    }
    return ans;
}
long long qpow(long long x,long long y,long long z){
    if(y==1) return x%z;
    if(y==0) return 1;
    long long hh=qpow(x,y/2,z);
    if(y%2==0) return hh%z*hh%z;
    return hh%z*hh%z*x%z;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            add(i,j,(qpow(a[i],a[j],m)+qpow(a[j],a[i],m))%m);
    for(int i=1;i<=n;i++)
        f[i]=i;
    sort(e+1,e+cnt+1,cmp);
    long long ans=kruskal();
    printf("%lld",ans);
    return 0;
}