Submission #73704151

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

long long MOD = 998244353;
// long long MOD = int(1e9)+7;
struct modint {
	long long x;

	modint(long long x=0) : x((x % MOD + MOD) % MOD) {}

	long long val() const { return x; }

	modint& operator+=(const modint a) { if ((x += a.x)>=MOD) x -= MOD; return *this; }
	modint& operator-=(const modint a) { if ((x += MOD - a.x)>=MOD) x -= MOD; return *this; }
	modint& operator*=(const modint a) { (x *= a.x) %= MOD; return *this; }
	modint& operator/=(const modint a) { return *this *= a.inv(); }

	friend modint operator+(modint a, const modint b) { return a += b; }
	friend modint operator-(modint a, const modint b) { return a -= b; }
	friend modint operator*(modint a, const modint b) { return a *= b; }
	friend modint operator/(modint a, const modint b) { return a /= b; }

	modint& operator++() { if (++x == MOD) x = 0; return *this; }
	modint& operator--() { if (x == 0) x = MOD; --x; return *this; }
	modint operator++(int) { modint res = *this; ++*this; return res; }
	modint operator--(int) { modint res = *this; --*this; return res; }

	bool operator==(const modint a) const { return x == a.x; }
	bool operator!=(const modint a) const { return x != a.x; }
	modint operator-() const { return (x==0) ? 0 : MOD-x; }

	modint pow(long long t) const {
		modint res=1, a=*this;
		while (t>0) {
			if (t&1) res *= a;
			a *= a;
			t >>= 1;
		}
		return res;
	}
	modint inv() const { return pow(MOD-2); }

	friend ostream& operator<<(ostream& os, const modint& a) { return os<<a.x; }
	friend istream& operator>>(istream& is, modint& a) {
		long long t; is >> t;
		a = modint(t);
		return is;
	}
};

struct UnionFind {
	vector<int> parent;

	UnionFind(int N) : parent(N, -1) {}
	
	int root(int x) {
		if (parent[x] < 0) return x;
		return parent[x] = root(parent[x]);
	}

	int size(int x){
		return -parent[root(x)];
	}

	bool is_same(int x, int y) {
		return root(x) == root(y);
	}

	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return false;
		if (parent[x]>parent[y]) swap(x, y);
		parent[x] += parent[y];
		parent[y] = x;
		return true;
	}
};

int main(){
	int N, M; cin>>N>>M;
	vector<pair<int, int>> edge(M);
	for (int i=0; i<M; i++){
		int U, V; cin>>U>>V; U--; V--;
		edge[i] = {U, V};
	}
	modint ans = modint(2).pow(M+1);
	ans--;
	int comp = N;
	UnionFind uf(N);
	for (int i=M-1; i>=0; i--){
		if (comp!=2){
			if (uf.unite(edge[i].first, edge[i].second)) comp--;
			ans -= modint(2).pow(i+1);
		} else {
			if (uf.is_same(edge[i].first, edge[i].second)){
				ans -= modint(2).pow(i+1);
			}
		}
	}
	cout<<ans-1<<endl;
}

Submission Info

Judge Result