Submission #908704

#TimeUsernameProblemLanguageResultExecution timeMemory
908704amirhoseinfar1385Amusement Park (CEOI19_amusementpark)C++17
42 / 100
3017 ms124220 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=15,maxm=14348907,mod=998244353; int pd[maxm]; long long mypow(long long m,long long y){ if(y==0){ return 1; } long long p=mypow(m,(y>>1)); p*=p; p%=mod; if(y&1){ p*=m; p%=mod; } return p; } int ww(int a){ if(a>=mod){ a-=mod; } return a; } pair<int,int>tab2(int a){ int now=0; pair<int,int>ret=make_pair(0,0); while(a!=0){ if(a%3==1){ ret.first+=(1<<now); }else if(a%3==2){ ret.second+=(1<<now); } now++; a/=3; } return ret; } int back3(int a,int b){ int ret=0,now=1; while(a+b!=0){ if(a&1){ ret+=now; } else if(b&1){ ret+=2*now; } now*=3; a>>=1; b>>=1; } return ret; } vector<int>tartib[18]; int adj[maxn],adja[maxn]; int n,m; void aval(){ int nx=1; for(int i=1;i<=n;i++){ nx*=3; } for(int i=0;i<nx;i++){ pair<int,int>fake=tab2(i); tartib[__builtin_popcount(fake.first)].push_back(i); } } void solve(){ for(int i=0;i<maxn;i++){ for(auto x:tartib[i]){ pair<int,int>now=tab2(x); for(int j=0;j<n;j++){ if((now.second>>j)&1){ now.second^=(1<<j); pair<int,int>fake=now; fake.first|=(1<<j); fake.second|=(adj[j]^(adj[j]&now.first)); int tof=back3(fake.first,fake.second); pd[tof]+=pd[x]; pd[tof]=ww(pd[tof]); } } } } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; aval(); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; u--; v--; adj[u]|=(1<<v); adj[v]|=(1<<u); adja[u]|=(1<<v); } pd[back3(0,(1<<n)-1)]=1; solve(); int res=back3((1<<n)-1,0); pd[res]=1ll*pd[res]*m%mod; pd[res]=1ll*pd[res]*mypow(2,mod-2)%mod; cout<<pd[res]<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...