Submission #1148713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148713		vako_p	Amusement Park (CEOI19_amusementpark)	C++20	100 / 100	2468 ms	2768 KiB

amusementpark

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

const int mxN = 3e5 + 5;
int n,m,cnt[mxN],popcnt[mxN],dp[mxN],adj1[20][20],deg[mxN],mod = 998244353;
bool good[mxN],adj[20][20];

ll fpow(ll a, ll b){
	if(b == 0) return 1LL;
	ll ans = fpow(a, b / 2);
	ans = (ans * ans) % mod;
	if(b % 2) return (ans * a % mod);
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		ll a,b;
		cin >> a >> b;
		a--;
		b--;
		adj1[a][b] = true;
		adj[a][b] = adj[b][a] = true;
	}
	good[0] = true;
	for(int bit = 0; bit < (1 << n); bit++){
		for(int i = 0; i < n; i++){
			if(!((1 << i) & bit)) continue;
			if(!good[bit ^ (1 << i)]){
				good[bit] = false;
				break;
			}
			good[bit] = true;
			for(int j = i + 1; j < n; j++){
				if((1 << j) & bit and adj[i][j]) good[bit] = false;
			}
			break;
		}
		popcnt[bit] = __builtin_popcount(bit) % 2 * 2 - 1;
	}
	cnt[0] = 1;
	for(int bit = 1; bit < (1 << n); bit++){
		if(__builtin_popcount(bit) == 1){
			cnt[bit] = 1;  
			continue;
		}
		for(int i = bit; i > 0; i = bit & (i - 1)){
			if(!good[i]) continue;
			cnt[bit] = (cnt[bit] + cnt[bit ^ i] * popcnt[i]) % mod;
		}
	}
	ll ans = cnt[(1 << n) - 1];
	cout << (ans + mod) % mod * m % mod * fpow(2, mod - 2) % mod;
}
 

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