#include <bits/stdc++.h>
#include <iostream>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <map>
using namespace std;
typedef long double ld;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
#define double long double
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define lowbit(x) x & (-x);
#define inf 1e18
#define _inf -1e18
#define pyes cout << "YES" << endl
#define pno cout << "NO" << endl
#define inv(a) for (int& x: a) cin >> x;
#define llv(a) for (ll& x: a) cin >> x;
#define pri(a) for (int& x: a) cout << x << ' '
int const MOD = 998244353;
int const lg = 20;
int const block = 500;
// int block;
int const MAX = 3e5 + 1, N = 20;
int n, m, q, k;
bool ck[21][21];
int f[21][21];
void bexuyen67() {
cin >> n >> m;
vector<vector<int>> g(n + 1);
for (int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
if (ck[x][y])
continue;
ck[x][y] = ck[y][x] = 1;
if (x > y)
swap(x, y);
g[x].push_back(y);
}
int sum = 1 << n;
for (int i = 1; i <= n; i++){
if (g[i].empty())
continue;
int sz = g[i].size();
int after = n - i - sz;
for (int j = 1; j <= g[i].size(); j++){
for (int k = 0; k <= after; k++){
int tol = f[sz][j]*f[after][k];
sum -= tol;
// cout << tol << '\n';
}
}
}
cout << sum;
}
signed main() {
#ifdef binhball
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(15);
for (int i = 0; i <= N; i++){
f[i][0] = 1;
f[i][i] = 1;
}
for (int i = 2; i <= 20; i++){
for (int j = 1; j <= i; j++){
f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}
}
int t = 1;
// cin >> t;
while (t--)
bexuyen67();
}
Compilation message
geppetto.cpp: In function 'void bexuyen67()':
geppetto.cpp:57:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int j = 1; j <= g[i].size(); j++){
| ~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
5 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
9 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
10 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |