Submission #660255

#	Time	Username	Problem	Language	Result	Execution time	Memory
660255		600Mihnea	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2302 ms	317356 KiB

amusementpark

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int M = 998244353;

int add(int a, int b)
{
  a += b;
  if (a >= M)
  {
    return a - M;
  }
  if (a < 0)
  {
    return a + M;
  }
  return a;
}

int mul(int a, int b)
{
  return a * (ll) b % M;
}

int pw(int a, int b)
{
  int r = 1;
  while (b)
  {
    if (b & 1)
    {
      r = mul(r, a);
    }
    a = mul(a, a);
    b /= 2;
  }
  return r;
}

int dv(int a, int b)
{
  return mul(a, pw(b, M - 2));
}

void addup(int &a, int b)
{
  a = add(a, b);
}

void mulup(int &a, int b)
{
  a = mul(a, b);
}

const int N = 18;
int n;
int m;
int g[N];
vector<pair<int, int>> dp_push[1 << N];
int dp[1 << N];

int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  /**

  query = what is the sum(of number of inverted edges for every possible choice of edges directions)

  we have
  # inverted edges(ordering) = m - # inverted edges(~ordering)

  bijection =>


  query = # possible choice of edges directions * m / 2

  **/
  cin >> n >> m;
  for (int i = 0; i < m; i++)
  {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    g[a] |= (1 << b);
    g[b] |= (1 << a);
  }
  int sol = 0;
  dp_push[(1 << n) - 1].push_back({(1 << n) - 1, 1});
  vector<int> sub_masks;
  for (int rem_verts = (1 << n) - 1; rem_verts > 0; rem_verts--)
  {
    {
      sub_masks.clear();
      for (int i = rem_verts; i; i = (i - 1) & rem_verts)
      {
        sub_masks.push_back(i);
      }
      sub_masks.push_back(0);
    }
    for (auto &it : dp_push[rem_verts])
    {
      addup(dp[it.first], it.second);
    }
    for (auto &possible_next : sub_masks)
    {
      if (int coef = dp[possible_next])
      {
        for (int vertex = 0; vertex < n; vertex++)
        {
          if (possible_next & (1 << vertex))
          {
            dp_push[rem_verts - (1 << vertex)].push_back({(possible_next & ((1 << vertex) - 1)) | (g[vertex] & rem_verts), coef});
          }
        }
        dp[possible_next] = 0;
      }
    }
  }
  for (auto &it : dp_push[0]) {
    addup(sol, it.second);
  }
  cout << mul(sol, dv(m, 2)) << "\n";
}

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