結果

問題 No.1303 Inconvenient Kingdom
ユーザー chocoruskchocorusk
提出日時 2020-11-27 23:19:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 8,810 bytes
コンパイル時間 1,810 ms
コンパイル使用メモリ 146,604 KB
実行使用メモリ 10,400 KB
最終ジャッジ日時 2024-09-13 01:00:43
合計ジャッジ時間 15,717 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,268 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 WA -
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 TLE -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#define popcount __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
struct unionfind{
    vector<int> par, sz;
    unionfind() {}
    unionfind(int n):par(n), sz(n, 1){
        for(int i=0; i<n; i++) par[i]=i;
    }
    int find(int x){
        if(par[x]==x) return x;
        return par[x]=find(par[x]);
    }
    void unite(int x, int y){
        x=find(x); y=find(y);
        if(x==y) return;
        if(sz[x]>sz[y]) swap(x, y);
        par[x]=y;
        sz[y]+=sz[x];
    }
    bool same(int x, int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};
template<int MOD>
struct ModInt{
	int x;
	ModInt(): x(0){}
	ModInt(ll y): x(y>=0 ? y%MOD : (MOD-(-y)%MOD)%MOD){}

	ModInt &operator+=(const ModInt &p){
		if((x+=p.x)>=MOD) x-=MOD;
		return *this;
	}
	ModInt &operator-=(const ModInt &p){
		if((x+=MOD-p.x)>=MOD) x-=MOD;
		return *this;
	}
	ModInt &operator*=(const ModInt &p){
		x=(int)(1ll*x*p.x%MOD);
		return *this;
	}
	ModInt &operator/=(const ModInt &p){
		*this*=p.inv();
		return *this;
	}

	ModInt operator-() const{ return ModInt(-x);}
	ModInt operator+(const ModInt &p) const{ return ModInt(*this)+=p;}
	ModInt operator-(const ModInt &p) const{ return ModInt(*this)-=p;}
	ModInt operator*(const ModInt &p) const{ return ModInt(*this)*=p;}
	ModInt operator/(const ModInt &p) const{ return ModInt(*this)/=p;}
	bool operator==(const ModInt &p) const{ return x==p.x;}
	bool operator!=(const ModInt &p) const{ return x!=p.x;}

	ModInt pow(ll n) const{
		ModInt ret(1), p(x);
		while(n){
			if(n&1) ret*=p;
			p*=p;
			n>>=1;
		}
		return ret;
	}
	ModInt inv() const{
		return pow(MOD-2);
	}
};
const int MOD=998244353;
using mint=ModInt<MOD>;
template<typename T>
struct Matrix{
	vector<vector<T>> a;
	Matrix(){}
	Matrix(size_t n, size_t m):a(n, vector<T>(m, 0)){}
	Matrix(size_t n):Matrix(n, n){}
	Matrix(vector<vector<T>> a):a(a){}

	size_t height() const{
		return a.size();
	}
	size_t width() const{
		return a[0].size();
	}

	inline const vector<T> &operator[](size_t k) const{
		return a[k];
	}
	inline vector<T> &operator[](size_t k){
		return a[k];
	}

	static Matrix I(size_t n){
		Matrix mat(n);
		for(int i=0; i<n; i++) mat[i][i]=1;
		return mat;
	}

	Matrix &operator+=(const Matrix &b){
		size_t n=height(), m=width();
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				(*this)[i][j]+=b[i][j];
			}
		}
		return (*this);
	}
	Matrix &operator-=(const Matrix &b){
		size_t n=height(), m=width();
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				(*this)[i][j]-=b[i][j];
			}
		}
		return (*this);
	}
	Matrix &operator*=(const Matrix &b){
		size_t n=height(), m=width(), l=b.width();
		vector<vector<T>> c(n, vector<T>(l, 0));
		for(int i=0; i<n; i++){
			for(int j=0; j<l; j++){
				for(int k=0; k<m; k++){
					c[i][j]+=(*this)[i][k]*b[k][j];
				}
			}
		}
		a.swap(c);
		return (*this);
	}
	Matrix operator+(const Matrix &b) const{
		return (Matrix(*this)+=b);
	}
	Matrix operator-(const Matrix &b) const{
		return (Matrix(*this)-=b);
	}
	Matrix operator*(const Matrix &b) const{
		return (Matrix(*this)*=b);
	}

	Matrix pow(ll k) const{
		Matrix ap(a), ret=I(height());
		while(k){
			if(k&1) ret*=ap;
			ap*=ap;
			k>>=1;
		}
		return ret;
	}

	static pair<Matrix, Matrix> Gauss_Jordan(const Matrix &a, const Matrix &b){
		size_t n=a.height(), m=a.width(), l=b.width();
		Matrix c(n, m+l);
		for(int i=0; i<n; i++) for(int j=0; j<m; j++) c[i][j]=a[i][j];
		for(int i=0; i<n; i++) for(int j=0; j<l; j++) c[i][j+m]=b[i][j];
		int d=0;
		for(int i=0; i<m; i++){
			int p=-1; 
			for(int j=d; j<n; j++){
				if(c[j][i]!=0){
					p=j; break;
				}
			}
			if(p==-1) continue;
			swap(c[p], c[d]);
			T invc=T(1)/c[d][i];
			for(int j=i; j<m+l; j++) c[d][j]*=invc;
			for(int j=0; j<n; j++){
				if(j==d) continue;
				T c0=c[j][i];
				for(int k=i; k<m+l; k++){
					c[j][k]-=c0*c[d][k];
				}
			}
			d++;
		}
		Matrix reta(n, m), retb(n, l);
		for(int i=0; i<n; i++) for(int j=0; j<m; j++) reta[i][j]=c[i][j];
		for(int i=0; i<n; i++) for(int j=0; j<l; j++) retb[i][j]=c[i][j+m];
		return make_pair(reta, retb);
	}

	static pair<vector<T>, vector<vector<T>>> linear_equations(const Matrix &a, const vector<T> &b){
		int n=a.height(), m=a.width();
		Matrix B(n, 1);
		for(int i=0; i<n; i++) B[i][0]=b[i];
		auto p=Gauss_Jordan(a, B);
		vector<int> myon(n,-1);
		vector<int> nuo(m, -1);
		for(int i=0; i<n; i++){
			bool allzero=1;
			for(int j=0; j<m; j++){
				if(p.first[i][j]!=0){
					allzero=0;
					myon[i]=j;
					nuo[j]=i;
					break;
				}
			}
			if(allzero && p.second[i][0]!=0){
				vector<T> retc;
				vector<vector<T>> retd;
				return make_pair(retc, retd);
			}
		}
		vector<T> c(m);
		vector<vector<T>> d;
		for(int i=0; i<m; i++){
			if(nuo[i]==-1){
				vector<T> v(m);
				v[i]=1;
				for(int j=0; j<n; j++){
					if(myon[j]!=-1) v[myon[j]]=-p.first[j][i];
				}
				d.push_back(v);
			}else{
				c[i]=p.second[nuo[i]][0];
			}
		}
		return make_pair(c, d);
	}

	Matrix inv() const{
		int n=height();
		Matrix b=I(n);
		auto p=Gauss_Jordan(*this, b);
		if(p.first[n-1][n-1]==0){
			Matrix ret(0);
			return ret;
		}
		return p.second;
	}

	int rank() const{
		int n=height(), m=width();
		Matrix b(n, 0);
		auto p=Gauss_Jordan(*this, b);
		for(int i=0; i<n; i++){
			bool allzero=1;
			for(int j=0; j<m; j++){
				if(p.first[i][j]!=0){
					allzero=0;
					break;
				}
			}
			if(allzero) return i;
		}
		return n;
	}

	T det() const{
		size_t n=height();
		Matrix A(a);
		T ret(1);
		for(int i=0; i<n; i++){
			int p=-1; 
			for(int j=i; j<n; j++){
				if(A[j][i]!=0){
					p=j; break;
				}
			}
			if(p==-1){
				return 0;
			}
			if(p!=i) ret*=(-1);
			swap(A[p], A[i]);
			ret*=A[i][i];
			T inva=T(1)/A[i][i];
			for(int j=i+1; j<n; j++){
				T a0=A[j][i];
				for(int k=i; k<n; k++){
					A[j][k]-=inva*a0*A[i][k];
				}
			}
		}
		return ret;
	}
};
using Mat=Matrix<mint>;

int main()
{
    int n, m; cin>>n>>m;
    unionfind uf(n);
    int a[100010], b[100010];
    for(int i=0; i<m; i++){
        int u, v; cin>>u>>v;
        u--; v--;
        a[i]=u, b[i]=v;
        uf.unite(u, v);
    }
    vector<int> v;
    for(int i=0; i<n; i++){
        if(uf.find(i)==i){
            v.push_back(uf.size(i));
        }
    }
    sort(v.begin(), v.end(), greater<int>());
    if(v.size()==1){
        cout<<0<<endl;
    }else{
        ll ans=0, s2=0;
        for(auto x:v){
            ans+=x;
            s2+=x*x;
        }
        ans=ans*ans-s2;
        ans-=2*v[0]*v[1];
        cout<<ans<<endl;
    }
    vector<int> w[101];
    for(int i=0; i<n; i++){
        w[uf.find(i)].push_back(i);
    }
    mint ans=1;
    for(int i=0; i<n; i++){
        if(w[i].size()<=1) continue;
        int s=w[i].size();
        Mat mat(s-1);
        for(int j=0; j<m; j++){
            if(uf.find(a[j])!=i) continue;
            int p=lower_bound(w[i].begin(), w[i].end(), a[j])-w[i].begin();
            int q=lower_bound(w[i].begin(), w[i].end(), b[j])-w[i].begin();
            if(p<s-1){
                mat[p][p]+=1;
            }
            if(q<s-1){
                mat[q][q]+=1;
            }
            if(p<s-1 && q<s-1){
                mat[p][q]-=1;
                mat[q][p]-=1;
            }
        }
        ans*=mat.det();
    }
    if(v.size()==1){
        for(int i=0; i<m; i++){
            Mat mat1(n-2);
            int x=a[i], y=b[i];
            for(int j=0; j<m; j++){
                int x1=a[j], y1=b[j];
                if(a[j]!=x && a[j]!=y){
                    if(a[j]<x) x1=a[j];
                    else if(a[j]<y) x1--;
                    else x1-=2;
                    mat1[x1][x1]+=1;
                }
                if(b[j]!=x && b[j]!=y){
                    if(b[j]<x) y1=b[j];
                    else if(b[j]<y) y1--;
                    else y1-=2;
                    mat1[y1][y1]+=1;
                }
                if(a[j]!=x && a[j]!=y && b[j]!=x && b[j]!=y){
                    mat1[x1][y1]-=1;
                    mat1[y1][x1]-=1;
                }
            }
            ans+=mat1.det();
        }
        cout<<ans.x<<endl;
        return 0;
    }
    if(v[0]>v[1]){
        ans*=mint(v[0]*v[1]);
    }else{
        int c=0;
        for(auto x:v){
            if(x==v[0]) c++;
        }
        ans*=mint(c*(c-1)/2*v[0]*v[0]);
    }
    cout<<ans.x<<endl;
    return 0;
}
0