結果
問題 | No.1116 Cycles of Dense Graph |
ユーザー |
![]() |
提出日時 | 2020-07-17 22:10:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 5,724 bytes |
コンパイル時間 | 4,794 ms |
コンパイル使用メモリ | 229,124 KB |
最終ジャッジ日時 | 2025-01-11 22:45:25 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}using Int = long long;const char newl = '\n';template<typename T,T MOD = 1000000007>struct Mint{static constexpr T mod = MOD;T v;Mint():v(0){}Mint(signed v):v(v){}Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}Mint pow(long long k){Mint res(1),tmp(v);while(k){if(k&1) res*=tmp;tmp*=tmp;k>>=1;}return res;}static Mint add_identity(){return Mint(0);}static Mint mul_identity(){return Mint(1);}Mint inv(){return pow(MOD-2);}Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}Mint& operator/=(Mint a){return (*this)*=a.inv();}Mint operator+(Mint a) const{return Mint(v)+=a;}Mint operator-(Mint a) const{return Mint(v)-=a;}Mint operator*(Mint a) const{return Mint(v)*=a;}Mint operator/(Mint a) const{return Mint(v)/=a;}Mint operator-() const{return v?Mint(MOD-v):Mint(v);}bool operator==(const Mint a)const{return v==a.v;}bool operator!=(const Mint a)const{return v!=a.v;}bool operator <(const Mint a)const{return v <a.v;}static Mint comb(long long n,int k){Mint num(1),dom(1);for(int i=0;i<k;i++){num*=Mint(n-i);dom*=Mint(i+1);}return num/dom;}};template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;template<typename T,T MOD>ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}template<typename M_>class Enumeration{using M = M_;protected:static vector<M> fact,finv,invs;public:static void init(int n){n=min<decltype(M::mod)>(n,M::mod-1);int m=fact.size();if(n<m) return;fact.resize(n+1,1);finv.resize(n+1,1);invs.resize(n+1,1);if(m==0) m=1;for(int i=m;i<=n;i++) fact[i]=fact[i-1]*M(i);finv[n]=M(1)/fact[n];for(int i=n;i>=m;i--) finv[i-1]=finv[i]*M(i);for(int i=m;i<=n;i++) invs[i]=finv[i]*fact[i-1];}static M Fact(int n){init(n);return fact[n];}static M Finv(int n){init(n);return finv[n];}static M Invs(int n){init(n);return invs[n];}static M C(int n,int k){if(n<k||k<0) return M(0);init(n);return fact[n]*finv[n-k]*finv[k];}static M P(int n,int k){if(n<k||k<0) return M(0);init(n);return fact[n]*finv[n-k];}// put n identical balls into k distinct boxesstatic M H(int n,int k){if(n<0||k<0) return M(0);if(!n&&!k) return M(1);init(n+k);return C(n+k-1,n);}};template<typename M>vector<M> Enumeration<M>::fact=vector<M>();template<typename M>vector<M> Enumeration<M>::finv=vector<M>();template<typename M>vector<M> Enumeration<M>::invs=vector<M>();template<typename V>V compress(V vs){sort(vs.begin(),vs.end());vs.erase(unique(vs.begin(),vs.end()),vs.end());return vs;}template<typename T>map<T, int> dict(const vector<T> &vs){map<T, int> res;for(int i=0;i<(int)vs.size();i++)res[vs[i]]=i;return res;}map<char, int> dict(const string &s){return dict(vector<char>(s.begin(),s.end()));}struct UnionFind{int num;vector<int> rs,ps;UnionFind(){}UnionFind(int n):num(n),rs(n,1),ps(n,0){iota(ps.begin(),ps.end(),0);}int find(int x){return (x==ps[x]?x:ps[x]=find(ps[x]));}bool same(int x,int y){return find(x)==find(y);}void unite(int x,int y){x=find(x);y=find(y);if(x==y) return;if(rs[x]<rs[y]) swap(x,y);rs[x]+=rs[y];ps[y]=x;num--;}int size(int x){return rs[find(x)];}int count() const{return num;}};//INSERT ABOVE HEREsigned main(){cin.tie(0);ios::sync_with_stdio(0);int n,m;cin>>n>>m;vector<int> as(m),bs(m);for(int i=0;i<m;i++) cin>>as[i]>>bs[i],as[i]--,bs[i]--;using M = Mint<int, 998244353>;using E = Enumeration<M>;E::init(1e6);M ans{0};// emptyfor(int k=3;k<=n;k++)ans+=E::C(n,k)*E::Fact(k-1)/M(2);// cerr<<ans<<endl;using P = pair<int, int>;map<P, M> memo;auto calc=[&](int cnt,int num){// cerr<<cnt<<' '<<num<<endl;if(memo.count(P(cnt,num))) return memo[P(cnt,num)];M &res=memo[P(cnt,num)];res=0;M tmp{1};for(int j=0;j<=num;j++){res+=E::C(num,j)*tmp;tmp*=M(cnt+j);}// cerr<<res<<endl;return res;};int sz=1<<m;vector<int> cs(n,0);for(int bit=1;bit<sz;bit++){vector<int> ss;for(int i=0;i<m;i++){if((bit>>i)&1){cs[as[i]]++;cs[bs[i]]++;ss.emplace_back(as[i]);ss.emplace_back(bs[i]);}}ss=compress(ss);auto dc=dict(ss);UnionFind uf(ss.size());int flg=0;for(int i=0;i<m;i++){flg|=cs[as[i]]>2;flg|=cs[bs[i]]>2;}for(int i=0;i<m;i++)cs[as[i]]=cs[bs[i]]=0;if(flg) continue;for(int i=0;i<m;i++){if((bit>>i)&1){int a=dc[as[i]];int b=dc[bs[i]];flg|=uf.same(a,b);uf.unite(a,b);}}int vs=ss.size();int es=__builtin_popcount(bit);if(vs>=3 and uf.count()==1 and vs==es){if(__builtin_parity(bit)) ans-=M(1);else ans+=M(1);continue;}if(flg) continue;int cnt=vs-es;int num=n-vs;M res=calc(cnt,num);assert(cnt==uf.count());if(es==1) res-=M(1);res*=M(2).pow(cnt-1);res*=E::Fact(cnt-1);if(__builtin_parity(bit)) ans-=res;else ans+=res;}cout<<ans<<newl;return 0;}