#include <vector>
#include <array>
#include <iostream>
#ifdef DEBUG
#include "debug.hpp"
#endif
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N) for(int i = 0; i < (N); ++i)
#define rrep(i, N) for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N) for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e) for(int i = (s); i <= (e); ++i)
#ifdef DEBUG
#define debug(x...) { \
++dbg::depth; \
string dbg_vals = dbg::to_string(x); \
--dbg::depth; \
dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
}
#define light_debug(x) { \
dbg::light = true; \
dbg::dout << __func__ << ":" << __LINE__; \
dbg::dout << " " << #x << " = " << x << endl; \
dbg::light = false; \
}
#else
#define debug(x...) 42
#define light_debug(x) 42
#endif
using ll = long long;
template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }
template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }
constexpr int mod{998244353};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
array<bool, 1 << 18> parity;
rep(i, 1 << 18) parity[i] = __builtin_popcount(i) % 2 == 0;
array<int, 1 << 18> lg;
rep(i, 1 << 18) lg[i] = __lg(i);
int n, m; cin >> n >> m;
vector<vector<bool>> adj(n, vector<bool>(n));
rep(i, m) {
int u, v; cin >> u >> v; --u, --v;
adj[u][v] = true;
}
vector<vector<int>> single_cost(n, vector<int>(1 << n));
rep(i, n)
rep1(mask, (1 << n) - 1) {
single_cost[i][mask] = single_cost[i][mask - (1 << lg[mask])]
+ adj[lg[mask]][i];
}
vector<bool> is_independent(1 << n); is_independent[0] = true;
rep1(mask, (1 << n) - 1) {
int i = lg[mask];
is_independent[mask] = is_independent[mask - (1 << i)] &&
single_cost[i][mask] == 0;
}
vector<long long> dp_s(1 << n), dp_c(1 << n); dp_c[0] = 1;
vector<int> partial_cost(1 << n);
int j, sources;
long long t_s, t_c;
rep1(mask, (1 << n) - 1) {
for(sources = mask & (mask - 1); ; sources = (sources - 1) & mask) {
sources = mask - sources;
if(is_independent[sources]) {
j = lg[sources];
partial_cost[sources] =
partial_cost[sources - (1 << j)] + single_cost[j][mask];
t_c = dp_c[mask ^ sources];
t_s = dp_s[mask ^ sources] +
dp_c[mask ^ sources] * partial_cost[sources] % mod;
if(parity[sources])
dp_s[mask] -= t_s, dp_c[mask] -= t_c;
else
dp_s[mask] += t_s, dp_c[mask] += t_c;
}
sources = mask - sources;
if(sources == 0) break;
}
dp_c[mask] %= mod;
dp_s[mask] %= mod;
}
if(dp_s.back() < 0) dp_s.back() += mod;
cout << dp_s.back() << '\n';
#ifdef DEBUG
dbg::dout << "\nExecution time: "
<< clock() * 1000 / CLOCKS_PER_SEC
<< "ms" << endl;
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1484 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1484 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1484 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1484 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1484 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
