제출 #1040175

#제출 시각아이디문제언어결과실행 시간메모리
1040175ef10Amusement Park (CEOI19_amusementpark)C++17
100 / 100
2883 ms4772 KiB
// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; #define LL long long #define MODULE 998244353 int N,M; int adj[20]; //map<int,int> ni; int sign[1<<18]; int popc[1<<18]; bool indp[1<<18]; LL dp[1<<18]; LL exp(LL a, LL b) { if (a==0) return 0; if (b == 0) return 1; LL ret = exp(a, b/2); ret = ret * ret; ret %= MODULE; if (b % 2) { ret *= a; ret %= MODULE; } return ret; } LL inv(LL x) { return exp(x, MODULE-2); } int main() { cin >> N >> M; for (int i = 0; i < M; i++) { int a,b; cin >> a >> b; a--;b--; adj[a] |= (1 << b); adj[b] |= (1<<a); } /*cout << "adj: " << endl; for (int i = 0; i < N; i++) { cout << adj[i] << endl; }*/ for (int i = 0; i < (1<<N); i++) { popc[i] = popc[i>>1] + (i&1); sign[i] = (popc[i] % 2) ? (1) : (-1); } indp[0] = true; for (int i = 1; i < (1<<N); i++) { for (int j = 0; j < N; j++) { if (!(i&(1<<j))) continue; if (!indp[i&~(1<<j)]) continue; if ((adj[j]&(i&~(1<<j))) == 0) { indp[i] = true; } } /*if (indp[i]) { cout << "indp: " << i << endl; }*/ } dp[0] = 1; for (int i = 1; i < (1<<N); i++) { for (int j = i; j; j=(j-1)&i) { if (!indp[j]) continue; if (dp[i&~j]==0) continue; dp[i]+=dp[i&~j]*sign[j]; dp[i]%=MODULE; dp[i]=(dp[i]+MODULE)%MODULE; } //cout << "dp["<<i<<"] = " << dp[i] << endl; } LL res = dp[(1<<N)-1]; //cout << res << endl; res *= M; res %= MODULE; res *= inv(2); res %= MODULE; cout << res << endl; }
#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...