Submission #467898

#TimeUsernameProblemLanguageResultExecution timeMemory
467898ivan_tudorAmusement Park (CEOI19_amusementpark)C++14
42 / 100
40 ms456 KiB
#include<bits/stdc++.h> using namespace std; const int N = 18; bool canb[1<<N]; int dp[1<<N]; vector<int> gr[N]; const int MOD =998244353; void add(int &x, long long y){ y%=MOD; x+=y; if(x >= MOD) x-=MOD; if(x < 0) x+=MOD; } int main() { //freopen(".in","r",stdin); ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n, m; cin>>n>>m; for(int i = 1; i <= m; i++){ int x, y; cin>>x>>y; x--; y--; gr[x].push_back(y); gr[y].push_back(x); } canb[0] = true; for(int mask = 0; mask < (1<<n); mask++){ if(canb[mask] == false) continue; for(int i = 0; i < n; i++){ bool ok = true; if((mask & (1<<i)) == 0){ for(auto x:gr[i]){ if(mask & (1<<x)){ ok = false; break; } } canb[mask ^(1<<i)] = ok; } } } dp[0] = 1; for(int mask = 0; mask < (1<<n); mask ++){ for(int layer = mask; layer > 0; layer = (layer - 1) & mask){ if(canb[layer]){ if(__builtin_popcount(layer)%2 == 1) add(dp[mask], dp[mask ^ layer]); else add(dp[mask], -dp[mask ^ layer]); } } } cout<<(1LL * dp[(1<<n) - 1] * m / 2) % MOD; 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...