Submission #492250

#TimeUsernameProblemLanguageResultExecution timeMemory
492250Haruto810198Amusement Park (CEOI19_amusementpark)C++17
0 / 100
9 ms15108 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define double long double #define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d)) #define szof(x) ((int)(x).size()) #define vi vector<int> #define pii pair<int, int> #define F first #define S second #define pb push_back #define eb emplace_back #define mkp make_pair const int INF = 2147483647; const int LNF = INF*INF; const int MOD = 1000000007; const int mod = 998244353; const double eps = 1e-12; //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") const int MAX = 270000; const int inv2 = (mod + 1) / 2; int n, m; bool edge[18][18]; int Nc[18]; int sz; unordered_map<int, int> dp[MAX]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; sz = (1<<n); FOR(i, 1, m, 1){ int u, v; cin>>u>>v; u--, v--; edge[u][v] = edge[v][u] = 1; } FOR(i, 0, n-1, 1){ FOR(j, 0, n-1, 1){ if(edge[i][j]) Nc[i] |= (1<<j); } } FOR(v, 0, n-1, 1){ dp[(1<<v)][sz - 1 - (1<<v)] = 1; } FOR(A, 1, sz-1, 1){ int IA = sz - 1 - A; for(int B = IA; B > 0; B = ((B-1) & IA)){ dp[A][B] += 0; int AA, BB; // AA = A U {c}; // BB = B \ {0, ..., c-1} U {N(c) \ A} //cerr<<"dp["<<A<<"]["<<B<<"] = "<<dp[A][B]<<endl; FOR(c, 0, n-1, 1){ if((B & (1<<c)) == 0) continue; AA = A | (1<<c); BB = B & (~(1<<c)); BB |= (Nc[c] & (~A)); dp[AA][BB] += dp[A][B]; dp[AA][BB] %= mod; //cerr<<"dp["<<AA<<"]["<<BB<<"] += "<<dp[A][B]<<endl; } } } //cerr<<"ways = "<<dp[sz-1][0]<<endl; int res = (dp[sz-1][0] * ((m * inv2) % mod)) % mod; cout<<res<<'\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...