#include <bits/stdc++.h>
#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; }
class Modular {
int value;
public:
constexpr static int mod{998244353};
Modular(long long x = 0) {
value = (int)((x % mod + mod) % mod);
}
inline Modular& operator +=(Modular x) {
value += x.value;
if(value >= mod) value -= mod;
return *this;
}
inline Modular& operator -=(Modular x) {
value -= x.value;
if(value < 0) value += mod;
return *this;
}
inline Modular& operator *=(Modular x) {
value = int((long long)x.value * value % mod);
return *this;
}
// TODO : Make this Extended Euclid to handle composite moduli.
inline Modular& operator /=(Modular x) {
return *this *= x.pow(-1);
}
inline Modular operator -() const {
return Modular(-value);
}
inline Modular& operator ++() {
return *this += 1;
}
inline Modular& operator --() {
return *this -= 1;
}
inline Modular operator ++(int) {
Modular t{*this};
*this += 1;
return t;
}
inline Modular operator --(int) {
Modular t{*this};
*this -= 1;
return t;
}
Modular pow(long long n) const {
while(n < 0) n += mod - 1;
Modular v(1), a(value);
for(; n; a *= a, n >>= 1)
if(n & 1) v *= a;
return v;
}
inline Modular operator +(Modular x) const {
return x += *this;
}
inline Modular operator -(Modular x) const {
return *this + (-x);
}
inline Modular operator *(Modular x) const {
return x *= *this;
}
inline Modular operator /(Modular x) const {
return (*this) * x.pow(-1);
}
inline bool operator ==(Modular x) const {
return value == x.value;
}
inline bool operator !=(Modular x) const {
return value != x.value;
}
inline explicit operator int() const {
return value;
}
Modular fact() const {
Modular x(1);
for(int i = 1; i <= value; ++i) x *= i;
return x;
}
friend ostream& operator <<(ostream& os, Modular x) {
return os << x.value;
}
friend istream& operator >>(istream& is, Modular& x) {
is >> x.value; x.value %= mod; return is;
}
friend string to_string(Modular x) {
return std::to_string(int(x));
}
};
auto parity = []{
array<bool, 1 << 18> a{};
rep(i, 1 << 18) a[i] = __builtin_popcount(i) % 2 == 0;
return a;
}();
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
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<bool> is_independent(1 << n);
rep(mask, 1 << n) {
is_independent[mask] = true;
rep(i, n) if(mask & (1 << i))
rep(j, n)
if(adj[i][j] && (mask & (1 << j)))
is_independent[mask] = false;
}
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];
}
/* auto partial_cost = [&](int mask, int sources) {
int c{};
rep(i, n)
if(sources & (1 << i))
c += single_cost[i][mask];
return c;
};*/
vector<Modular> dp_s(1 << n), dp_c(1 << n); dp_c[0] = 1;
vector<int> partial_cost(1 << n);
rep1(mask, (1 << n) - 1) {
for(int sources{mask}; ; sources = (sources - 1) & mask) {
debug(sources);
if(sources == mask) continue;
sources = mask - sources;
int j = __lg(sources);
partial_cost[sources] =
partial_cost[sources - (1 << j)] + single_cost[j][mask];
if(is_independent[sources]) {
Modular t_s{dp_s[mask ^ sources] +
dp_c[mask ^ sources] * partial_cost[sources]};
dp_s[mask] += parity[sources] ? -t_s : t_s;
Modular t_c{dp_c[mask ^ sources]};
dp_c[mask] += parity[sources] ? -t_c : t_c;
}
sources = mask - sources;
debug(sources);
if(sources == 0) break;
}
for(int sources{mask}; sources > 0; sources = (sources - 1) & mask)
partial_cost[sources] = 0;
}
cout << dp_s.back() << '\n';
#ifdef DEBUG
dbg::dout << "\nExecution time: "
<< clock() * 1000 / CLOCKS_PER_SEC
<< "ms" << endl;
#endif
return 0;
}
Compilation message
Compilation timeout while compiling amusementpark
