제출 #691956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
691956		beaboss	Amusement Park (CEOI19_amusementpark)	C++14	0 / 100	1 ms	212 KiB

amusementpark

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll MOD = 998244353;

int main() {
	ll n, m;
	cin >> n >> m;

	vector<vector<ll> > adj(n);

	vector<vector<ll> > adj2(n);

	for (ll i = 0; i < m; i++) {
		ll a, b;
		cin >> a >> b;
		a--;b--;
		adj[a].push_back(b);
		adj2[a].push_back(b);
		adj2[b].push_back(a);

	}

	vector<pair<ll, ll> > dp(1<<n, {0, 0});
	dp[0]={1, 0};
	for (ll i = 0; i < n; i++) dp[(1 << i)] = {1, 0};
	for (ll i = 1; i < (1<<n); i++) {
		// cout << i << dp[i].first << dp[i].second << endl;
		for (ll ne = 0; ne < n; ne++) {
			if ((1 << ne) & i) continue;
			ll c = 0;
			for (auto val: adj[ne]) {
				if ((1 << val) & i) {
					c++;
				}
			}

			bool conn = false;
			for (auto val: adj2[ne]) if ((1<<val)&i)conn=true;
			// cout << (i^(1 << ne)) << dp[i].first << c << endl;
			if (!conn)continue;
			dp[i^(1 << ne)].second=((dp[i^(1 << ne)].second)%MOD+((dp[i].second)%MOD)+(dp[i].first*c)%MOD)%MOD;
			dp[i^(1 << ne)].first=(dp[i^(1 << ne)].first+dp[i].first)%MOD;
			// cout << i<<(ne) << dp[i^(1 << ne)].second << endl;
		}
		// cout << dp[]
	}
	ll ans = 1;
	vector<bool> v(n, false);
	for (int i = 0; i < n; i++) {

		if (!v[i]) {
			ll current=0;
			v[i] = true;
			queue<ll> q;
			q.push(i);
			while (!q.empty()) {
				ll cur = q.front();
				q.pop();
				current|=(1<<cur);
				for (auto val: adj2[cur]) if (!v[val]) {
					q.push(val);v[val]=true;
				}
			}
			ans = (ans * dp[current].second)%MOD;
		}
		
	}
	cout << ans << endl;

}

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