Submission #885518

#	Time	Username	Problem	Language	Result	Execution time	Memory
885518		beaboss	Amusement Park (CEOI19_amusementpark)	C++14	100 / 100	2173 ms	6828 KiB

amusementpark

// Source: https://oj.uz/problem/view/CEOI19_amusementpark
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

const ll N = 18;

ll indep[1 << N];
ll dp[1 << N];
ll sz[1 << N];
vi adj[N];
const ll MOD = 998244353;

ll binpow(ll x, ll n) {
	assert(n >= 0);
	x %= MOD;  // note: m * m must be less than 2^63 to avoid ll overflow
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % MOD; }
		x = x * x % MOD;
		n /= 2;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	ll n, m;
	cin >> n >> m;


	FOR(i, 0, m) {
		ll a, b;
		cin >> a >> b;
		a--;b--;
		adj[a].pb(b);
		adj[b].pb(a);

	}

	FOR(i, 0, 1 << n) {
		dp[i]=0;
		indep[i]=true;
		sz[i] = 0;
		FOR(j, 0, n) {
			if ((1 << j) & i) {
				for (auto val: adj[j]) {
					if ((1 << val) & i) indep[i]=false;
				}

				sz[i] ++;
			}
		}

		// cout << i << ' ' << indep[i] << endl;

		if (sz[i] % 2 == 1) sz[i] = 1;
		else sz[i] = -1;
	}

	dp[0] = 1;


	FOR(i, 1, 1 << n) {
		dp[i] = 0;
		for (ll j = i; j; j = (j - 1) & i) {
			// cout << ' ' << j << dp[i ^ j] << dp[i] << sz[j] << indep[j] << endl;
			if (indep[j]) dp[i] = ((dp[i] + dp[i ^ j] * sz[j])) % MOD;

		}

		// cout << i << ' ' << dp[i] << endl;	
	}
	dp[(1 << n) - 1] = (dp[(1 << n) - 1] + MOD) % MOD;
	cout << ((dp[(1 << n) - 1] * m) % MOD * binpow(2, MOD - 2)) % MOD << endl;


}

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