Submission #1222076

#TimeUsernameProblemLanguageResultExecution timeMemory
1222076_callmelucianAmusement Park (CEOI19_amusementpark)C++17
42 / 100
11 ms4676 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using pl = pair<ll,ll>; using pii = pair<int,int>; using tpl = tuple<int,int,int>; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) const int MOD = 998'244'353; bitset<19> adj[19]; int dp[1 << 10][1 << 10], n, m; bool getCur (int mask, int pos) { return mask >> pos & 1; } int add (int a, int b) { return a + b - (a + b < MOD ? 0 : MOD); } int sub (int a, int b) { return a - b + (a - b >= 0 ? 0 : MOD); } int mul (int a, int b) { return 1LL * a * b % MOD; } int binpow (int a, int b) { int ans = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) ans = mul(ans, a); return ans; } const int inv2 = binpow(2, MOD - 2); bool selfIntersect (int mask) { for (int i = 0; i < n; i++) { if (getCur(mask, i) && (adj[i] & bitset<19>(mask)).count()) return 1; } return 0; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--, b--; adj[a][b] = adj[b][a] = 1; } for (int mask = 0; mask < (1 << n); mask++) { for (int sub = mask; sub; sub = (sub - 1) & mask) { int last = mask ^ sub; if (selfIntersect(last)) continue; for (int preLast = sub;; preLast = (preLast - 1) & sub) { bool flag = 1; for (int i = 0; i < n; i++) if (getCur(preLast, i) && !(adj[i] & bitset<19>(last)).count()) { flag = 0; break; } if (flag) dp[mask][last] = add(dp[sub][preLast], dp[mask][last]); if (!preLast) break; } } dp[mask][mask] = !selfIntersect(mask); } int ans = 0; for (int mask = 0; mask < (1 << n); mask++) ans = add(ans, dp[(1 << n) - 1][mask]); cout << mul(mul(ans, inv2), m); 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...