Submission #1099029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099029		ventusliberum	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	1409 ms	3672 KiB

amusementpark

/**
 *    title:  Amusement Park
**/
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define si(x) int(x.size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
template <class T, class U> inline bool chmax(T &a, U b) { return (a < b ? a = b, 1 : 0); }
template <class T, class U> inline bool chmin(T &a, U b) { return (b < a ? a = b, 1 : 0); }
template <class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) { rep(i, si(v)) os << (i ? " " : "") << v[i]; return os; }
using ll = long long;
constexpr int inf = 1001001001;
constexpr long long infll = 4004004004004004004LL;

template <class T>
constexpr T power(T a, long long b) {
  T res = 1;
  while (b) {
    if (b & 1) res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}

template <int mod>
struct ModInt {
  int x;
  constexpr ModInt() : x{} {}
  constexpr ModInt(long long x) : x{norm(x % mod)} {}

  constexpr int norm(int x) const {
    if (x < 0) {
      x += mod;
    }
    if (x >= mod) {
      x -= mod;
    }
    return x;
  }
  constexpr int val() const {
    return x;
  }
  constexpr ModInt inv() const {
    assert(x != 0);
    return power(*this, mod - 2);
  }
  explicit constexpr operator int() const {
    return x;
  }
  constexpr ModInt operator-() const {
    ModInt res;
    res.x = norm(mod - x);
    return res;
  }
  constexpr ModInt& operator+=(ModInt rhs) {
    x = norm(x + rhs.x);
    return *this;
  }
  constexpr ModInt& operator-=(ModInt rhs) {
    x = norm(x - rhs.x);
    return *this;
  }
  constexpr ModInt& operator++() {
    return *this += 1;
  }
  constexpr ModInt& operator--() {
    return *this -= 1;
  }
  constexpr ModInt operator++(int) {
    ModInt res(*this);
    *this += 1;
    return res;
  }
  constexpr ModInt operator--(int) {
    ModInt res(*this);
    *this -= 1;
    return res;
  }
  constexpr ModInt& operator*=(ModInt rhs) {
    x = 1LL * x * rhs.x % mod;
    return *this;
  }
  constexpr ModInt& operator/=(ModInt rhs) {
    return *this *= rhs.inv();
  }
  friend constexpr ModInt operator+(ModInt lhs, ModInt rhs) {
    ModInt res = lhs;
    res += rhs;
    return res;
  }
  friend constexpr ModInt operator-(ModInt lhs, ModInt rhs) {
    ModInt res = lhs;
    res -= rhs;
    return res;
  }
  friend constexpr ModInt operator*(ModInt lhs, ModInt rhs) {
    ModInt res = lhs;
    res *= rhs;
    return res;
  }
  friend constexpr ModInt operator/(ModInt lhs, ModInt rhs) {
    ModInt res = lhs;
    res /= rhs;
    return res;
  }
  friend constexpr std::istream& operator>>(std::istream& is, ModInt& a) {
    long long v{};
    is >> v;
    a = ModInt(v);
    return is;
  }
  friend constexpr std::ostream& operator<<(std::ostream& os, const ModInt& a) {
    return os << a.val();
  }
  friend constexpr bool operator==(ModInt lhs, ModInt rhs) {
    return lhs.val() == rhs.val();
  }
  friend constexpr bool operator!=(ModInt lhs, ModInt rhs) {
    return lhs.val() != rhs.val();
  }
};

template <int num, int mod>
constexpr ModInt<mod> CInv = ModInt<mod>(num).inv();

constexpr int mod = 998244353;
using mint = ModInt<mod>;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, m;
  cin >> n >> m;
  vector<vector<int>> edge(n, vector<int>(n));
  rep(_, m) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    edge[a][b] = edge[b][a] = 1;
  }
  vector<int> popcount(1<<n);
  vector<int> independ(1<<n);
  independ[0] = 1;
  for (int i = 1; i < (1<<n); i++) {
    popcount[i] = popcount[i>>1] + (i&1);
    int j = __builtin_ffs(i) - 1;
    independ[i] = independ[i^1<<j];
    rep(k, n) {
      if ((i>>k&1) && edge[j][k]) independ[i] = 0;
    }
  }
  vector<mint> dp(1<<n);
  dp[0] = 1;
  for (int i = 1; i < (1<<n); i++) {
    for (int j = i; j; j = i&(j-1)) {
      if (independ[j]) {
        dp[i] += ((popcount[j] & 1) ? 1 : -1) * dp[i^j];
      }
    }
  }
  mint ans = dp[(1<<n)-1]/2*m;
  cout << ans << '\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37