AtCoder Beginner Contest 282E

ABC282E

ボールを頂点としてグラフを考える． 辺にコスト をつける．
辺 を選んで を戻すという操作により， に を対応させる．
操作は 回で終わる． 有限グラフであることから，サイクルはない． よって，操作で選んだ辺全体は木になる．
あとは，最大コストになるように辺を選べばよい． これはMSTと同様．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

// args : a,b,mod are integers

// return : the integer a^b mod <mod>

template<typename T>

T pow_mod(T a, T b, T mod){

  T ret = 1;

  T pow = a; // a^(2^i)

  while(b){

    if(b & 1){

      (ret *= pow) %= mod;

    }

    b >>= 1;

    (pow = pow * pow) %= mod;

  }

  return ret;

}

int main() {

  ll n, m;

  cin >> n >> m;

  vll a(n); rep(i,n) { cin >> a[i]; }

  using TU = tuple<ll,ll,ll>;

  vector<TU> ed;

  rep(i,n) rep(j,i) { // j < i

    ll x = pow_mod(a[i], a[j], m);

    ll y = pow_mod(a[j], a[i], m);

    ed.push_back({ (x+y)%m, j, i });

  }

  sort(all(ed), greater<TU>());

  UnionFind<ll> uf(n);

  ll ans = 0;

  for(auto [c, s, t]:ed){

    if(!uf.same(s,t)){

      ans += c;

      uf.merge(s,t);

    }

  }

  cout << ans << endl;

  return 0;

}