Submission #660727

#	Time	Username	Problem	Language	Result	Execution time	Memory
660727		kirakaminski968	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2240 ms	4784 KiB

amusementpark

#include <cstring>
#include <iostream>
using namespace std;
const int N = 18;
const int M = 998244353;
int a[N];
bool indepset[1 << N];
int popcount[1 << N];
int arg[1 << N];
int nodeid[1 << N];
long long f[1 << N];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		a[u] |= 1 << v;
		a[v] |= 1 << u;
	}
	for (int i = 0; i < n; i++) {
		nodeid[1 << i] = i;
	}
	for (int i = 0; i < (1 << n); i++) {
		popcount[i] = popcount[i >> 1] + (i & 1);
		arg[i] = (popcount[i] % 2) * 2 - 1;
	}
	indepset[0] = 1;
	for (int i = 1; i < (1 << n); i++) {
		if (indepset[i & (i - 1)] &&
		    (a[nodeid[i & (-i)]] & (i & (i - 1))) == 0) {
			indepset[i] = true;
		}
	}
	f[0] = 1;
	for (int i = 1; i < (1 << n); i++) {
		for (int j = i; j; j = (j - 1) & i) {
			if (indepset[j]) {
				f[i] = (f[i] + arg[j] * f[i ^ j]) % M;
			}
		}
	}
	f[(1 << n) - 1] = (f[(1 << n) - 1] + M) % M;
	cout << f[(1 << n) - 1] * m % M * ((M + 1) / 2) % M;
	return 0;
}

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