Submission #908762

#TimeUsernameProblemLanguageResultExecution timeMemory
908762amirhoseinfar1385Amusement Park (CEOI19_amusementpark)C++17
63 / 100
52 ms16208 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #include<bits/stdc++.h> using namespace std; const int maxn=18,maxm=387420489,mod=998244353; int pd[maxm],t[(1<<maxn)],mar; 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=t[a]+2*t[b]; return ret; } vector<int>tartib[maxn]; int adj[maxn],adja[maxn]; int n,m; void aval(){ mar=(1<<n)-1; int nx=1; for(int i=0;i<(1<<n);i++){ int now=1,ret=0; for(int j=0;j<n;j++){ if((i>>j)&1){ ret+=now; } now*=3; } t[i]=ret; tartib[__builtin_popcount(i)].push_back(i); } } void solve(){ for(int i=0;i<maxn;i++){ for(auto xx:tartib[i]){ for(int y=(mar^xx);y>0;y=(y-1)&(mar^xx)){ int x=back3(xx,y); if(pd[x]==0){ continue; } pair<int,int>now=make_pair(xx,y); 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(); if(n>15){ return 0; } 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"; }

Compilation message (stderr)

amusementpark.cpp: In function 'void aval()':
amusementpark.cpp:53:6: warning: unused variable 'nx' [-Wunused-variable]
   53 |  int nx=1;
      |      ^~
#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...