# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
128114935 |
Practice:
Czhgugugu |
11D
- 13
|
C++17 (GCC 9-64)
|
Accepted
|
421 ms
|
82224 KB
|
2021-09-07 13:25:13 |
2021-09-07 13:25:13 |
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pin;
#ifndef ONLINE_JUDGE
bool MEMORY_ST;
#endif
const int N = 19;
const int M = 1 << 19;
const ll P = 998244353LL;
int n, m;
bool e[N][N];
ll f[M][N];
namespace Fread {
const int L = 1 << 15;
char buffer[L], *S, *T;
inline char Getchar() {
if(S == T) {
T = (S = buffer) + fread(buffer, 1, L, stdin);
if(S == T) return EOF;
}
return *S++;
}
template <class T>
inline void read(T &X) {
char ch; T op = 1;
for(ch = Getchar(); ch > '9' || ch < '0'; ch = Getchar())
if(ch == '-') op = -1;
for(X = 0; ch >= '0' && ch <= '9'; ch = Getchar())
X = (X << 1) + (X << 3) + ch - '0';
X *= op;
}
} using Fread::read;
inline int lowbit(int s) {
return s & (-s);
}
#ifndef ONLINE_JUDGE
bool MEMORY_ED;
#endif
int main() {
#ifndef ONLINE_JUDGE
freopen("sample.in", "r", stdin);
clock_t st_clock = clock();
#endif
read(n), read(m);
for (int x, y, i = 1; i <= m; i++) {
read(x), read(y);
x--, y--;
e[x][y] = e[y][x] = 1;
}
ll ans = 0;
for (int s = 1; s < (1 << n); s++) {
int cnt = __builtin_popcount(s);
for (int i = 0; i < n; i++) {
if (!(s & (1 << i))) continue;
if (cnt == 1) f[s][i] = 1;
int k = __builtin_ctz(lowbit(s));
for (int j = 0; j < n; j++) {
if (s & (1 << j)) continue;
if (j <= k) continue;
if (!e[i][j]) continue;
f[s | (1 << j)][j] += f[s][i];
}
if (e[i][k]) ans += f[s][i];
}
}
ans -= m;
ans >>= 1;
printf("%lld\n", ans);
#ifndef ONLINE_JUDGE
clock_t ed_clock = clock();
printf("time = %f ms\n", (double)(ed_clock - st_clock) / CLOCKS_PER_SEC * 1000);
printf("memory = %.2f MB\n", (&MEMORY_ED - &MEMORY_ST) / 1024.0 / 1024.0);
#endif
return 0;
}
Click to see test details