結果
問題 | No.1116 Cycles of Dense Graph |
ユーザー |
|
提出日時 | 2020-07-17 22:15:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 3,908 bytes |
コンパイル時間 | 4,058 ms |
コンパイル使用メモリ | 208,216 KB |
最終ジャッジ日時 | 2025-01-11 22:49:10 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int64_t MOD = 998244353; void add(int64_t& a, int64_t b){ a = (a+b) % MOD; } void mul(int64_t& a, int64_t b){ a = a*b % MOD; } int64_t power_mod(int64_t num, int64_t power){ int64_t prod = 1; num %= MOD; while(power > 0){ if(power&1) prod = prod * num % MOD; num = num * num % MOD; power >>= 1; } return prod; } int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){ int64_t d = a; if(b != 0){ d = extgcd(b, a%b, y, x); y -= (a/b) * x; }else{ x = 1; y = 0; } return d; } int64_t inv_mod(int64_t a){ int64_t x, y; extgcd(a, MOD, x, y); return (MOD + x%MOD) % MOD; } vector<int64_t> fact, fact_inv; void create_mod_tables(int num){ fact.assign(num+1, 1); fact_inv.assign(num+1, 1); for(int i=1; i<=num; i++) fact[i] = fact[i-1] * i % MOD; fact_inv[num] = inv_mod(fact[num]); for(int i=num; i>0; i--) fact_inv[i-1] = fact_inv[i] * i % MOD; } int64_t comb_mod(int n, int k){ return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD; } int64_t perm_mod(int n, int k){ return fact[n] * fact_inv[n-k] % MOD; } int nth_bit(int64_t num, int n){ return (num >> n) & 1; } struct UnionFind { vector<int> par; vector<int> sz; UnionFind(int n=0){ if(n>0) initialize(n); } void initialize(int n){ par.resize(n); sz.assign(n, 1); for(int i=0; i<n; i++){ par[i] = i; } } int find(int x){ if(par[x] == x){ return x; }else{ return find(par[x]); } } bool unite(int x, int y){ x = find(x), y = find(y); if(x == y) return false; if(sz[x] > sz[y]) swap(x, y); par[x] = y; sz[y] += sz[x]; return true; } bool same(int x, int y){ return find(x) == find(y); } int size(int x){ return sz[find(x)]; } }; template<typename T> vector<T> compress(vector<T> A){ sort(A.begin(), A.end()); A.erase(unique(A.begin(), A.end()), A.end()); return A; } int main(){ int N, M; cin >> N >> M; vector<int> A(M), B(M), V; for(int i=0; i<M; i++){ cin >> A[i] >> B[i]; A[i]--; B[i]--; V.push_back(A[i]); V.push_back(B[i]); } V = compress(V); int sz = V.size(); for(int& a : A) a = lower_bound(V.begin(), V.end(), a) - V.begin(); for(int& a : B) a = lower_bound(V.begin(), V.end(), a) - V.begin(); create_mod_tables(200000); // use, path static int64_t P[31][16]; for(int use=0; use<=2*M; use++) for(int path=0; path<=M; path++){ int rest = N-use; if(rest < 0) continue; int64_t p2 = power_mod(2, path); mul(p2, inv_mod(2)); for(int r=0; r<=rest; r++) if(use+r >= 3 && path+r){ int64_t res = comb_mod(rest, r) * fact[path+r-1] % MOD * p2 % MOD; //cerr << use<<path<<r<<" " << res << endl; add(P[use][path], res); } } int64_t ans = 0; for(int b=0; b<(1<<M); b++){ vector<int> deg(sz); UnionFind uf(sz); int64_t C = 1; for(int i=0; i<M; i++) if(nth_bit(b, i)){ uf.unite(A[i], B[i]); deg[A[i]]++; deg[B[i]]++; C *= -1; } if(b && *max_element(deg.begin(), deg.end()) > 2) continue; int use = 0, cmp = 0, one = 0; for(int i=0; i<sz; i++) if(deg[i]){ use++; if(uf.find(i) == i) cmp++; if(deg[i] == 1) one++; } int64_t res = 0; if(cmp == 1 && one == 0){ res = 1; }else{ if(cmp*2 != one) continue; res = P[use][cmp]; } //cerr << b << res << use << cmp << endl; add(ans, MOD+C*res); } cout << ans << endl; return 0; }