Submission #407434

#TimeUsernameProblemLanguageResultExecution timeMemory
407434CrouchingDragonAmusement Park (CEOI19_amusementpark)C++17
7 / 100
34 ms74188 KiB
#include "bits/stdc++.h" using namespace std; #define endl '\n' #define debug(x) cerr << #x << " == " << (x) << '\n'; #define all(x) begin(x), end(x) using ll = long long; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fLL; template<ll mod> struct Mint { ll x; Mint(ll x = 0) : x((x %= mod) < 0 ? x + mod : x) { } Mint& operator+=(Mint rhs) { return (x += rhs.x) >= mod ? x -= mod : 0, *this; } Mint& operator-=(Mint rhs) { return (x -= rhs.x) < 0 ? x += mod : 0, *this; } Mint& operator*=(Mint rhs) { return (x *= rhs.x) %= mod, *this; } Mint& operator/=(Mint rhs) { return *this *= rhs.power(-1); } Mint power(ll p) const { p %= mod - 1; if (p < 0) p += mod - 1; Mint res = 1; for (Mint y = *this; p; p >>= 1, y *= y) if (p & 1) res *= y; return res; } bool operator==(Mint rhs) const { return x == rhs.x; } bool operator<(Mint rhs) const { return x < rhs.x; } friend Mint operator+(Mint lhs, Mint rhs) { return lhs += rhs; } friend Mint operator-(Mint lhs, Mint rhs) { return lhs -= rhs; } friend Mint operator*(Mint lhs, Mint rhs) { return lhs *= rhs; } friend Mint operator/(Mint lhs, Mint rhs) { return lhs /= rhs; } friend ostream& operator<<(ostream& out, Mint a) { return out << a.x; } friend istream& operator>>(istream& in, Mint& a) { ll x; in >> x; a = Mint(x); return in; } }; constexpr ll mod = 998244353, nmax = 18; using mint = Mint<mod>; mint sum[1 << nmax][nmax], cnt[1 << nmax][nmax]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<int> E(n); for (int j = 0; j < m; ++j) { int u, v; cin >> u >> v; --u, --v; E[u] |= 1 << v; } vector<int> popcount(1 << n); for (int mask = 1; mask < (1 << n); ++mask) { popcount[mask] = 1 + popcount[mask & (mask - 1)]; } for (int u = 0; u < n; ++u) cnt[1 << u][u] = 1; for (int mask = 1; mask < (1 << n); ++mask) { for (int u = 0; u < n; ++u) { if (mask >> u & 1) continue; int nmask = mask | 1 << u; for (int v = 0; v < n; ++v) { if (not ((E[v] >> u & 1) || (E[u] >> v & 1) || u > v)) continue; cnt[nmask][u] += cnt[mask][v]; sum[nmask][u] += sum[mask][v] + cnt[mask][v] * popcount[E[u] & mask]; } } } mint ans = 0; for (int u = 0; u < n; ++u) ans += sum[(1 << n) - 1][u]; cout << ans << endl; exit(0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...