Submission #521307

#	Time	Username	Problem	Language	Result	Execution time	Memory
521307		Cantfindme	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2672 ms	4648 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end() 

const int maxn = 25;
const int mod = 998244353; 
const int INF = LLONG_MAX/2;

int n, m;
int mat[maxn][maxn];
int con[1 << 20], dp[1<<20];

int faste(int x, int exp) {
	int base = x, ans = 1;
	while (exp) {
		if (exp & 1) ans = (ans * base) % mod;
		base = (base * base) % mod;
		exp >>= 1;
	}
	return ans;
}

int32_t main() {
	FAST
	cin >> n >> m;
	
	for (int i =0;i<m;i++) {
		int a,b; cin >> a >> b;
		a--; b--;
		mat[a][b] = mat[b][a] = 1;
	}
	
	for (int bm = 0; bm < (1 << n); bm++) {
		for (int i = 0;i <n;i++) if (bm & (1 << i)) {
			for (int j =0;j<n;j++) if (bm & (1 << j)) {
				if (mat[i][j]) con[bm] = 1;
			}
		}
	}
	
	dp[0] = 1; //No. of ways to form a DAG with bm
	
	//O(3^N)
	for (int bm = 1; bm < (1 << n); bm++) {
		for (int submask = bm; submask; submask = (submask - 1) & bm) {
			//Fix submask to have 0 in-degree
			if (con[submask]) continue;
			
			//PIE
			if (__builtin_popcount(submask) % 2) {
				dp[bm] += dp[bm ^ submask];
				dp[bm] %= mod;
			} else {
				dp[bm] = (dp[bm] - dp[bm ^ submask] + mod) % mod;
			}
		}
	}
	
	cout << dp[(1<<n)-1] * m % mod * faste(2, mod-2) % mod;
}

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