Submission #992069

#TimeUsernameProblemLanguageResultExecution timeMemory
992069parlimoosAmusement Park (CEOI19_amusementpark)C++14
0 / 100
1 ms2392 KiB
//Be Name KHODA #pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define pb push_back #define pp pop_back #define cl clear #define bg begin #define lb lower_bound #define ub upper_bound #define arr(x) array<int , x> #define endl '\n' const int MOD = 998244353; int n , m; int g[18][18] , inf[18]; int dp[18][(1 << 18)][2]; int Sum(int a , int b){ int res = a + b; if(res > MOD) return res - MOD; if(res < 0) return res + MOD; return res; } void Add(int &a , int b){ a += b; if(a > MOD) a -= MOD; if(a < 0) a += MOD; } int Mul(int a , int b){ return (1ll * a * b) % MOD; } void f(){ for(int b = 0 ; b < n ; b++) dp[b][0][0] = 1; for(int msk = 1 ; msk < (1 << n) ; msk++){ for(int v = 0 ; v < n ; v++){ if(!((msk >> v) & 1)) continue; inf[v] = 0; for(int u = 0 ; u < v ; u++) if(((msk >> u) & 1) and g[u][v] == 1) inf[v]++; } if(msk == (1 << n) - 1){ for(int v = 0 ; v < n ; v++){ Add(dp[0][msk][0] , dp[v][msk ^ (1 << v)][0]); Add(dp[0][msk][1] , Sum(Mul(inf[v] , dp[v][msk ^ (1 << v)][0]) , dp[v][msk ^ (1 << v)][1])); } }else{ for(int b = 0 ; b < n ; b++){ for(int v = 0 ; v < n ; v++){ if(!((msk >> v) & 1) or (v <= b and g[v][b] == 0)) continue; Add(dp[b][msk][0] , dp[v][msk ^ (1 << v)][0]); Add(dp[b][msk][1] , Sum(Mul(inf[v] , dp[v][msk ^ (1 << v)][0]) , dp[v][msk ^ (1 << v)][1])); } } } } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 0 ; i < m ; i++){ int v , u; cin >> v >> u; v-- , u--; g[v][u] = 1 , g[u][v] = -1; } f(); cout << dp[0][(1 << n) - 1][1]; }
#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...