Submission #441144

#	Time	Username	Problem	Language	Result	Execution time	Memory
441144		Autron	Amusement Park (CEOI19_amusementpark)	C++14	100 / 100	2157 ms	308884 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MOD 998244353

int adj[20];
map<int, int> dp[1<<18];

int32_t main(){
	int n, m;
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int a, b;
		cin>>a>>b;
		a--, b--;
		adj[a]|=(1<<b);
		adj[b]|=(1<<a);
	}
	dp[0][(1<<n)-1]=1;
	for(int mask=0;mask<(1<<n);++mask){
		for(auto it:dp[mask]){
			int mask2=it.first;
			int nr=it.second;
			for(int x=0;x<n;++x){
				if(mask2&(1<<x)){
					int aux=mask2;
					aux=aux&(((1<<n)-1)-((1<<(x+1))-1));
					aux=aux|((adj[x]|mask)^mask);
					dp[mask|(1<<x)][aux]+=nr;
					dp[mask|(1<<x)][aux]%=MOD;
				}
			}
		}
	}
	int sol=dp[(1<<n)-1][0];
	sol=(sol*m)%MOD;
	sol=(sol*(MOD+1)/2)%MOD;
	cout<<sol<<"\n";
	return 0;
}

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