제출 #674822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
674822		vovik	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2322 ms	4616 KiB

amusementpark

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

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