#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
bitset<18> bitmask[18];
vector<int> adj[18];
unordered_map<int,int> cached[1 << 18];
const int MOD = 998'244'353;
const int inv2 = 499'122'177;
int add (int a, int b) { return a + b - (a + b < MOD ? 0 : MOD); }
int sub (int a, int b) { return a - b + (a - b >= 0 ? 0 : MOD); }
int mul (int a, int b) { return 1LL * a * b % MOD; }
int binpow (int a, int b) {
int ans = 1;
for (; b; b >>= 1, a = mul(a, a))
if (b & 1) ans = mul(ans, a);
return ans;
}
bool getCur (int mask, int pos) {
return mask >> pos & 1;
}
void increase (int A, int B, int incr) {
if (!incr) return;
if (!cached[A].count(B)) cached[A][B] = 0;
auto &it = cached[A][B];
it = add(it, incr);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
a--, b--;
adj[a].push_back(b);
adj[b].push_back(a);
bitmask[a][b] = bitmask[b][a] = 1;
}
for (int i = 0; i < n; i++)
sort(all(adj[i]), greater<int>());
/// find valid masks & setup mask case
for (int mask = 0; mask < (1 << n); mask++) {
bool valid = 1;
for (int i = 0; i < n; i++)
if (getCur(mask, i) && (bitset<18>(mask) & bitmask[i]).count()) { valid = 0; break; }
if (valid) cached[0][mask] = 1;
}
/// run DP
for (int A = 0; A < (1 << n); A++) {
// expand B operation only
for (auto [B, dp] : cached[A]) {
if (!(A & B)) continue;
// cout << "1p " << bitset<2>(A) << " " << bitset<2>(B) << " " << dp << "\n";
int cur = __builtin_ctz(A & B);
increase(A, B ^ (1 << cur), dp);
for (int j : adj[cur]) {
if (getCur(B, j)) break;
if (!getCur(A, j) && !(bitset<18>(B ^ (1 << cur)) & bitmask[j]).count()) increase(A, B | (1 << j), dp);
}
}
// move B to A operation only
for (auto [B, dp] : cached[A]) {
if ((A & B) || !B) continue;
// cout << "2p " << bitset<2>(A) << " " << bitset<2>(B) << " " << dp << "\n";
int cur = __builtin_ctz(B);
increase(A | (1 << cur), B, dp);
}
}
int ans = cached[(1 << n) - 1][0];
// cout << ans << " ";
cout << mul(mul(ans, inv2), m);
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... |