提出 #73705250

---

ソースコード 拡げる

#include <algorithm>
#include <atcoder/all>
#include <cmath>
#include <iostream>
#include <map>
//#include <numeric>
#include <queue>
//#include <ranges>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define pb push_back
#define fr first
#define sc second
#define sor(v) sort(v.begin(), v.end())
#define rev(v) reverse(v.begin(), v.end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using pint = pair<int,int>;
//using pll = pair<ll,ll>;
//using pqdec = priority_queue<int,vector<int>,greater<int>>;
//using pqdecl = priority_queue<ll,vector<ll>,greater<ll>>;
template <typename T>
using graph = vector<vector<T>>;
const ll LLMAX = 9223372*1e10;
const int IMAX = 214*1e7;
/*--------考察--------------------
----------CODING----------------*/
using mint = atcoder::modint998244353;
vector<mint> w;
auto init(int m){
    mint x = 1;
    rep(i,m){
        x *= 2;
        w.pb(x);
    }
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    init(m);
    atcoder::dsu d(n);
    vector<pint> v(m);
    for(auto&[a,b]:v){cin >> a >> b; a--; b--;}
    mint ans = 0;
    int size = n;
    for(int i = m-1; i >= 0; i--){
        auto[a,b] = v[i];
        if(size <= 2 && !d.same(a,b)){
            ans += w[i];
            continue;
        }
        if(!d.same(a,b)) size--;
        d.merge(a,b);
        /*auto g = d.groups();
        cout << "loop" << i << endl;
        for(auto gg:g){
            for(auto e:gg) cout << e << " ";
            cout << endl;
        }*/
    }
    cout << ans.val() << endl;
}

提出情報

ジャッジ結果