Submission #741806

#	Time	Username	Problem	Language	Result	Execution time	Memory
741806		nishkarsh	Amusement Park (CEOI19_amusementpark)	C++14	0 / 100	1 ms	308 KiB

amusementpark

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 18;
const int mod = 998244353;
ll ways[1<<N][N];
ll ways2[1<<N];
int undirected_edge[N];
int main(){
	int n,m,a,b;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a >> b;
		a--;b--;
		undirected_edge[a] ^= (1<<b);
		undirected_edge[b] ^= (1<<a);
	}
	for(int i = 0; i < n; i++){
		ways[1<<i][i] = 1;
		ways2[1<<i] = 1;
	}
	for(int i = 0; i < (1<<n); i++){
		if(! (i&(i-1))) continue;
		for(int j = 0; j < n; j++){
			if(! (i&(1<<j))) continue;
			ways[i][j] = ways2[i^(1<<j)];
			for(int k = 0; k < n; k++){
				if((! (i&(1<<j))) || (k == j)) continue;
				if((! (undirected_edge[j]&(1<<k))) && (k < j)){
					ways[i][j] -= ways[i^(1<<k)][j];
					if(ways[i][j] < 0) ways[i][j] += mod;
				}
			}
			ways[i][j] %= mod;
			ways2[i] += ways[i][j];
		}
		ways2[i] %= mod;
	}
	ll ans = ways2[(1<<n)-1];
	if(ans&1) ans += mod;
	ans >>= 1;
	ans *= m; ans %= mod;
	cout << ans;
	return 0;
}

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