Submission #1222635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222635		sam230609	Amusement Park (CEOI19_amusementpark)	C++20	100 / 100	1925 ms	8664 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353,N=18;
ll a[N],s[1<<N],p[1<<N],r[1<<N],d[1<<N],f[1<<N];
int main() {
	ll n,m; cin >>n>>m; s[0]=1; f[0]=1;
	for(ll i=1;i<=m;i++){
		ll u,v; cin >>u>>v;
		u--; v--; a[u]|=(1<<v); a[v]|=(1<<u);
	}for(ll i=0;i<n;i++) d[1<<i]=i;
	for(ll i=0;i<(1<<n);i++){
		p[i]=p[i>>1]+(i&1); r[i]=(p[i]%2)*2-1;
	}for(ll i=1;i<(1<<n);i++){
		if(s[i&(i-1)] && (a[d[i&(-i)]] & (i&(i-1)))==0) s[i]=1;
	}for(ll i=1;i<(1<<n);i++){
		for(int j=i;j;j=(j-1)&i){
			if(s[j]) f[i]=(f[i]+r[j]*f[i^j])%mod;
		}
	}f[(1<<n)-1]=(f[(1<<n)-1]+mod)%mod;
	cout <<f[(1<<n)-1]*m%mod*((mod+1)/2)%mod;
}

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