結果
問題 | No.1116 Cycles of Dense Graph |
ユーザー |
|
提出日時 | 2020-07-17 23:13:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 2,257 bytes |
コンパイル時間 | 1,103 ms |
コンパイル使用メモリ | 92,552 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-30 02:46:54 |
合計ジャッジ時間 | 2,916 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
コンパイルメッセージ
main.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 39 | main() | ^~~~
ソースコード
#include<iostream>#include<map>using namespace std;#include<vector>struct UF{int n;vector<int>parent,rank;UF(int n_=0):n(n_),parent(n_),rank(n_,1){for(int i=0;i<n_;i++)parent[i]=i;}int find(int a){return parent[a]!=a?parent[a]=find(parent[a]):a;}bool same(int a,int b){return find(a)==find(b);}bool unite(int a,int b){a=find(a),b=find(b);if(a==b)return false;if(rank[a]<rank[b]){parent[a]=b;rank[b]+=rank[a];}else{parent[b]=a;rank[a]+=rank[b];}return true;}int size(int a){return rank[find(a)];}};const long mod=998244353;long power(long a,long b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}long fac[1<<17],inv[1<<17];long comb(int N,int K){return fac[N]*inv[K]%mod*inv[N-K]%mod;}int N,M;int a[15],b[15];map<pair<int,int>,long>memo;main(){cin>>N>>M;for(int i=0;i<M;i++)cin>>a[i]>>b[i];fac[0]=1;for(int i=1;i<=N;i++)fac[i]=fac[i-1]*i%mod;inv[N]=power(fac[N],mod-2);for(int i=N;i--;)inv[i]=inv[i+1]*(i+1)%mod;long ans=0;for(int k=3;k<=N;k++){(ans+=comb(N,k)*fac[k-1]%mod)%=mod;}for(int i=1;i<1<<M;i++){map<int,int>mp;map<int,int>id;int sz=0;bool ok=true;int one=0,edge=0;for(int j=0;j<M;j++)if(i>>j&1){edge++;if(mp[a[j]]==2){ok=false;break;}else if(mp[a[j]]==1){mp[a[j]]=2;one--;}else{mp[a[j]]=1;one++;id[a[j]]=sz++;}if(mp[b[j]]==2){ok=false;break;}else if(mp[b[j]]==1){mp[b[j]]=2;one--;}else{mp[b[j]]=1;one++;id[b[j]]=sz++;}}if(!ok)continue;int m=mp.size();UF uf(m);int rc=0;for(int j=0;j<M;j++)if(i>>j&1){int x=id[a[j]],y=id[b[j]];if(!uf.unite(x,y))rc++;}if(rc>=1){if(rc==1&&one==0){if(edge%2==1)ans=(ans+mod-2)%mod;else ans=(ans+2)%mod;}continue;}long now;pair<int,int>p=make_pair(m,one);if(memo.find(p)!=memo.end())now=memo[p];else{now=0;for(int k=0;k<=N-m;k++){if(m+k>=3)(now+=comb(N-m,k)*fac[k+one/2-1]%mod)%=mod;}now=now*power(2,one/2)%mod;memo[p]=now;}if(edge%2==1)ans=(ans+mod-now)%mod;else ans=(ans+now)%mod;}cout<<ans*power(2,mod-2)%mod<<endl;}