Submission #468042

#	Time	Username	Problem	Language	Result	Execution time	Memory
468042		warner1129	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2776 ms	1668 KiB

amusementpark

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

const int mod = 998244353;
const int inv2 = (mod+1) >> 1;
const int maxn = 18;

int dp[1<<maxn];
bitset<1<<maxn> ind;
pair<int, int> edge[maxn*maxn];

int n, m;

bool check(const int &s) {
	for (int i = 1; i <= m; i++)
		if (((s>>edge[i].ff) & 1) && ((s>>edge[i].ss) & 1))
			return false;
	return true;
}

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> edge[i].ff >> edge[i].ss, edge[i].ff--, edge[i].ss--;
	for (int i = 1; i < (1<<n); i++) ind[i] = check(i);
	dp[0] = 1;
	for (int i = 1; i < (1<<n); i++)
		for (int j = i; j; j = (j-1) & i)
			if (ind[j]) dp[i] = (dp[i] + ((__builtin_popcount(j) & 1) ? dp[i^j] : -dp[i^j])) % mod;
	cout << 1ll*((dp[(1<<n)-1] + mod) % mod) * m % mod * inv2 % mod;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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