Submission #985994

#	Time	Username	Problem	Language	Result	Execution time	Memory
985994		duckindog	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	1361 ms	2128 KiB

amusementpark

#include <bits/stdc++.h> 

using namespace std;

const int N = 153 + 10,
					M = 998'244'353,
					MASK = 1 << 18;
int n, m;
vector<int> ad[N];
int a[N], b[N];
bool chk[MASK];
int f[MASK];

void add(auto& x, const auto& y) {  
	x += y;
	if (x >= M) x -= M;
}
int powder(int a, int b) { 
	int ret = 1;
	while (b) { 
		if (b & 1) ret = 1ll * ret * a % M;
		a = 1ll * a * a % M;
		b >>= 1;
	}
	return ret;
}

int32_t main() { 
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> m;
	for (int i = 1; i <= m; ++i) { 
		cin >> a[i] >> b[i];
		ad[a[i]].push_back(b[i]);
		ad[b[i]].push_back(a[i]);
	}

	for (int mask = 1; mask < (1 << n); ++mask) { 
		chk[mask] = true;
		for (int i = 1; i <= m; ++i) 
			chk[mask] &= !(mask >> a[i] - 1 & 1) || !(mask >> b[i] - 1 & 1);
	}

	f[0] = 1;
	for (int mask = 1; mask < (1 << n); ++mask) { 
		for (int sMask = mask; sMask; sMask = (sMask - 1) & mask) { 
			if (!chk[sMask]) continue;
			if (__builtin_popcountll(sMask) & 1) add(f[mask], f[mask ^ sMask]);
			else add(f[mask], M - f[mask ^ sMask]);
		}
	}
	
	cout << 1ll * f[(1 << n) - 1] * m % M * powder(2, M - 2) % M << "\n";
}

Compilation message (stderr)

amusementpark.cpp:14:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   14 | void add(auto& x, const auto& y) {
      |          ^~~~
amusementpark.cpp:14:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   14 | void add(auto& x, const auto& y) {
      |                         ^~~~
amusementpark.cpp: In function 'int32_t main()':
amusementpark.cpp:41:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   41 |    chk[mask] &= !(mask >> a[i] - 1 & 1) || !(mask >> b[i] - 1 & 1);
      |                           ~~~~~^~~
amusementpark.cpp:41:59: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   41 |    chk[mask] &= !(mask >> a[i] - 1 & 1) || !(mask >> b[i] - 1 & 1);
      |                                                      ~~~~~^~~

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