#include<bits/stdc++.h>
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;
const int MAXN = 18;
const int MOD = 998244353;
int N, M;
int adj[MAXN];
int f[MASK(18)][300];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("a.in", "r", stdin); freopen("a.ans", "w", stdout);
cin >> N >> M;
for(int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
a--;
b--;
adj[a] ^= MASK(b);
}
// if(N <= 6)
// {
// vector<pair<int, int>> e;
// for(int i = 0; i < N; i++)
// for(int j = 0; j < N; j++)
// if(BIT(adj[i], j))
// e.push_back(make_pair(i, j));
// int ans = 0;
// for(int mask = 0; mask < MASK(M); mask++) {
// vector<int> new_adj(N, 0);
// for(int i = 0; i < M; i++)
// if(BIT(mask, i))
// new_adj[e[i].second] ^= MASK(e[i].first);
// else
// new_adj[e[i].first] ^= MASK(e[i].second);
// vector<int> vis(N, 0);
// bool good = true;
// function<void(int)> dfs = [&](int u) {
// if(!good)
// return;
// vis[u] = 1;
// for(int i = 0; i < N; i++)
// if(BIT(new_adj[u], i) && vis[i] == 1) {
// good = false;
// return;
// }
// for(int i = 0; i < N; i++)
// if(BIT(new_adj[u], i) && vis[i] == 0) {
// dfs(i);
// if(!good)
// return;
// }
// vis[u] = 2;
// };
// for(int i = 0; i < N; i++)
// if(vis[i] == 0)
// dfs(i);
// if(good)
// (ans += __builtin_popcount(mask)) %= MOD;
// }
// cout << ans;
// }
// else
{
f[0][0] = 1;
for(int i = 0; i < MASK(N); i++) {
int cnt = __builtin_popcount(i);
for(int j = 0; j < N; j++) {
if(BIT(i, j))
continue;
int cost = __builtin_popcount(adj[j] & i);
for(int k = 0; k <= cnt * (cnt - 1) / 2; k++) {
if(f[i][k] == 0)
continue;
(f[i ^ MASK(j)][k + cost] += f[i][k]) %= MOD;
}
}
}
int ans = 0;
for(int i = 1; i <= N * (N - 1) / 2; i++) {
(ans += 1LL * f[MASK(N) - 1][i] * i % MOD) %= MOD;
}
cout << ans;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
