// File amusementpark.cpp created on 16.10.2025 at 08:43:05
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
template<typename T>
T power(T a, i64 b) {
T res {1};
while (b) {
if (b & 1) {
res *= a;
}
a *= a;
b >>= 1;
}
return res;
}
constexpr int md = 998244353;
struct MInt {
int val;
MInt() : val(0) {}
template<typename T>
MInt(T x) {
if (-md <= x && x < md) {
val = x;
} else {
val = x % md;
}
if (val < 0) {
val += md;
}
}
int operator()() { return val; }
MInt& operator+= (MInt rhs) {
if ((val += rhs.val) >= md) {
val -= md;
}
return *this;
}
MInt& operator-= (MInt rhs) {
if ((val -= rhs.val) < 0) {
val += md;
}
return *this;
}
MInt& operator*= (MInt rhs) {
val = int(1LL * val * rhs.val % md);
return *this;
}
MInt inv() {
return power(*this, md - 2);
}
MInt& operator/= (MInt rhs) {
return *this *= rhs.inv();
}
bool operator== (MInt rhs) {
return val == rhs.val;
}
bool operator!= (MInt rhs) {
return val != rhs.val;
}
};
MInt operator+ (MInt lhs, MInt rhs) {
return lhs += rhs;
}
MInt operator- (MInt lhs, MInt rhs) {
return lhs -= rhs;
}
MInt operator* (MInt lhs, MInt rhs) {
return lhs *= rhs;
}
MInt operator/ (MInt lhs, MInt rhs) {
return lhs /= rhs;
}
std::ostream& operator<< (std::ostream& os, MInt x) {
return os << x.val;
}
using Z = MInt;
constexpr int max_N = 18;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M;
std::cin >> N >> M;
std::vector<int> adj(N);
for (int i = 0; i < M; ++i) {
int U, V;
std::cin >> U >> V;
--U, --V;
adj[U] |= 1 << V;
adj[V] |= 1 << U;
}
std::vector<int> good(1 << N, true);
for (int m = 0; m < (1 << N); ++m) {
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
if (m >> i & 1 && m >> j & 1 && adj[i] >> j & 1) {
good[m] = false;
}
}
}
}
debug(good);
std::vector<int> pcnt(1 << N);
pcnt[0] = -1;
for (int i = 1; i < (1 << N); ++i) {
pcnt[i] = pcnt[i - (i & -i)] * -1;
}
std::vector<Z> f(1 << N);
f[0] = 1;
for (int m = 1; m < (1 << N); ++m) {
for (int x = m; x; x = (x - 1) & m) {
if (good[x]) {
f[m] += pcnt[x] * f[m ^ x];
}
}
}
Z ans = f[(1 << N) - 1];
std::cout << ans * M / 2 << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |