Submission #936094

#TimeUsernameProblemLanguageResultExecution timeMemory
936094a_l_i_r_e_z_aAmusement Park (CEOI19_amusementpark)C++17
42 / 100
7 ms2648 KiB
// In the name of God // Hope is last to die #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back #define int long long #define S second #define F first #define mp make_pair #define smax(x, y) (x) = max((x), (y)) #define smin(x, y) (x) = min((x), (y)) #define all(x) (x).begin(), (x).end() const int maxn = 18; const int inf = 1e9 + 7, mod = 998244353; int n, m, adj[maxn], dp[1ll << maxn]; bool is_val[1ll << maxn]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--, v--; adj[u] += 1ll << v; adj[v] += 1ll << u; } is_val[0] = 1; for(int mask = 1; mask < (1ll << n); mask++){ int i = __builtin_ctz(mask); if(is_val[mask - (1ll << i)] && (adj[i] & mask) == 0) is_val[mask] = 1; } dp[0] = 1; for(int mask = 1; mask < (1ll << n); mask++){ for(int sm = mask; sm; sm = mask & (sm - 1)){ if(is_val[sm]){ if(__builtin_parity(sm)){ dp[mask] = (dp[mask] + dp[mask - sm]) % mod; } else{ dp[mask] = (dp[mask] - dp[mask - sm] + mod) % mod; } } } } cout << (((1ll * dp[(1ll << n) - 1] * m) * (mod + 1)) / 2) % mod << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...