이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstring>
#include <iostream>
using namespace std;
const int N = 18;
const int M = 998244353;
int a[N];
bool indepset[1 << N];
int popcount[1 << N];
int arg[1 << N];
int nodeid[1 << N];
long long f[1 << N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
a[u] |= 1 << v;
a[v] |= 1 << u;
}
for (int i = 0; i < n; i++) {
nodeid[1 << i] = i;
}
for (int i = 0; i < (1 << n); i++) {
popcount[i] = popcount[i >> 1] + (i & 1);
arg[i] = (popcount[i] % 2) * 2 - 1;
}
indepset[0] = 1;
for (int i = 1; i < (1 << n); i++) {
if (indepset[i & (i - 1)] &&
(a[nodeid[i & (-i)]] & (i & (i - 1))) == 0) {
indepset[i] = true;
}
}
f[0] = 1;
for (int i = 1; i < (1 << n); i++) {
for (int j = i; j; j = (j - 1) & i) {
if (indepset[j]) {
f[i] = (f[i] + arg[j] * f[i ^ j]) % M;
}
}
}
f[(1 << n) - 1] = (f[(1 << n) - 1] + M) % M;
cout << f[(1 << n) - 1] * m % M * ((M + 1) / 2) % 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... |