oj.uz

답안 #198116

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198116 2020-01-24T18:16:05 Z model_code Amusement Park (CEOI19_amusementpark) C++17
0 / 100
 2 ms 376 KB 
// Build DAG by adding single vertices.
// If we add vertex i, we can't add any vertex < i
// until there is an edge to it from vertex i or any later added vertex.
// States of DP: (added vertices, candidates for next added). O(4^N).
#include <bits/stdc++.h>
using namespace std;

long long pow(long long a, long long e, long long mod) {
	if(e <= 0) return 1;
	long long x = pow(a, e/2, mod);
	x = x * x % mod;
	return (e&1) ? (a * x % mod) : x;
}

struct state {
	int candidates;
	int cnt;
	// long long sum;
	constexpr static int mod = 998244353;

	inline state & operator+=(const state & S) {
		cnt += S.cnt;
		if(cnt >= mod) cnt -= mod;
		// sum += S.sum;
		return *this;
	}

	bool operator<(const state & S) const {
		return candidates < S.candidates;
	}
};

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	int N, M;
	cin >> N >> M;
	vector<int> E(N, 0), Ei(N, 0), E_all(N, 0);
	for(int i = 0; i < M; i++) {
		int u, v;
		/* rand */
		// static mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
		// u = rng()%N, v = rng()%N;
		// while(u == v || (E_all[u]>>v)&1)
		// 	u = rng()%N, v = rng()%N;
		/* rand */
		/* input */
		cin >> u >> v;
		u--, v--;
		/* input */
		E[u] |= 1<<v;
		Ei[v] |= 1<<u;
		E_all[u] |= 1<<v;
		E_all[v] |= 1<<u;
	}

	vector< vector<state> > dp(1<<N);
	dp[0].push_back({(1<<N)-1, 1});
	// dp[0].push_back({(1<<N)-1, 1, 0});
	for(int used = 0; used < (1<<N); used++) {
		sort(begin(dp[used]), end(dp[used]));
		int pos = 0;
		for(int i = 1; i < (int)dp[used].size(); i++) {
			if(dp[used][i].candidates == dp[used][pos].candidates) {
				dp[used][pos] += dp[used][i];
				continue;
			}
			// dp[used][pos].sum %= state::mod;
			pos++;
			dp[used][pos] = dp[used][i];
		}
		if(!dp[used].empty()) {
			// dp[used][pos].sum %= state::mod;
			dp[used].resize(pos+1);
		}
		for(state & st : dp[used]) {
			int suf = (1<<N)-1;
			for(int j = 0; j < N; j++) {
				suf ^= (1<<j);
				if(((st.candidates)>>j)&1) {
					int next_used = used | (1<<j);
					int next_candidates = (st.candidates & suf) | E_all[j];
					next_candidates ^= (next_candidates & next_used);
					dp[next_used].push_back({next_candidates, st.cnt});
				}
			}
		}
	}

	int num_states = 0;
	for(int i = 0; i < (1<<N); i++) num_states += dp[i].size();
	cerr << num_states << "\n";

	long long ans_sum = 0, ans_cnt = 0;
	for(state & st : dp[(1<<N)-1]) {
		ans_cnt += st.cnt;
		// ans_sum += st.sum;
	}
	ans_cnt %= state::mod;
	// ans_sum %= state::mod;
	ans_sum = ans_cnt * M % state::mod;
	ans_sum = ans_sum * pow(2, state::mod-2, state::mod) % state::mod;
	// cout << ans_cnt << "\n";
	cout << ans_sum << "\n";
	return 0;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -