Submission #674826

#	Time	Username	Problem	Language	Result	Execution time	Memory
674826		vovik	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2779 ms	4548 KiB

amusementpark

#include<bits/stdc++.h>
long long dp[1<<18],g[18][18],u[1<<18],n,m;
int main(){
for(int i=0,x,y;(i||std::cin>>n>>m)&&i<m&&std::cin>>x>>y;++i)g[x-1][y-1]=true;
for(int m4sk=1;m4sk<1<<n;++m4sk)for(int i=0;i<n;++i)for(int j=0;j<n;++j)u[m4sk]|=g[i][j]&&(m4sk>>j&1)&&(m4sk>>i&1);
for(int m4sk=1;(dp[0]=1)&&m4sk<1<<n;++m4sk,(m4sk!=(1<<n)||(std::cout<<(dp[(1<<n)-1]*m%998244353*499122177%998244353+998244353)%998244353<<'\n')))for(int m3sk=m4sk;m3sk;m3sk=(m3sk-1)&m4sk)(dp[m4sk]+=dp[m4sk^m3sk]*(2*(__builtin_popcount(m3sk)&1)-1)*!u[m3sk])%=998244353;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37