제출 #1129966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129966		mnbvcxz123	Amusement Park (CEOI19_amusementpark)	C++20	100 / 100	1661 ms	4812 KiB

amusementpark

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

const int N = 18;
const int M = 998244353;
int a[N];
bool indepset[1 << N];
int popcnt[1 << N];
int ar[1 << N];
int nodeid[1 << N];
ll dp[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++) {
		popcnt[i] = popcnt[i >> 1] + (i & 1);
		ar[i] = (popcnt[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;
		}
	}
	dp[0] = 1;
	for (int i = 1; i < (1 << n); i++) {
		for (int j = i; j; j = (j - 1) & i) {
			if (indepset[j]) { dp[i] = (dp[i] + ar[j] * dp[i ^ j]) % M; }
		}
	}
	dp[(1 << n) - 1] = (dp[(1 << n) - 1] + M) % M;
	cout << dp[(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