제출 #1148684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148684		vako_p	Amusement Park (CEOI19_amusementpark)	C++20	63 / 100	3095 ms	4168 KiB

amusementpark

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

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

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);
	}
	cnt[0] = 1;
	for(int bit = 1; bit < (1 << n); bit++){
		if(__builtin_popcount(bit) == 1){
			dp[bit] = 0;
			cnt[bit] = 1;  
			continue;
		}
		for(int i = bit; i > 0; i = bit & (i - 1)){
			if(!good[i]) continue;
			ll val = 0;
			for(int j = 0; j < n; j++){
				if((1 << j) & i){
					for(int k = 0; k < n; k++){
						if((1 << k) & bit and adj1[k][j]) val++;
					}
				}
			}
//			cout << i << "-----> " << val << '\n'; 
			dp[bit] = (2 * mod + dp[bit] + (dp[bit ^ i] + cnt[bit ^ i] * val) * (popcnt[i] % 2 * 2 - 1) % mod) % mod;
			cnt[bit] = (cnt[bit] + mod + cnt[bit ^ i] * (popcnt[i] % 2 * 2 - 1) % mod) % mod;
//			cout << i << ' ' << bit << ' ' << dp[bit] << ' ' << cnt[bit] << "---> " << dp[bit ^ i] << '\n';
		}
	}
	cout << dp[(1 << n) - 1] % mod;
}
 

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