Codeforces Round #844 Editorial

Explanation

Source

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int w, d, h;
    cin >> w >> d >> h;
    int a, b;
    cin >> a >> b;
    int f, g;
    cin >> f >> g;
    int ans = b + abs(a - f) + g;
    ans = min(ans, a + abs(b - g) + f);
    ans = min(ans, (d - b) + abs(a - f) + (d - g));
    ans = min(ans, (w - a) + abs(b - g) + (w - f));
    cout << ans + h << '\n';
  }
  return 0;
}

1782B - Going to the Cinema

Explanation

Source 1

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> cnt(n + 1);
    for (int i = 0; i < n; i++) {
      int a;
      cin >> a;
      cnt[a] += 1;
    }
    int ans = 0;
    int sum = 0;
    for (int k = 0; k <= n; k++) {
      if (cnt[k] == 0 && sum == k) {
        ans += 1;
      }
      sum += cnt[k];
    }
    cout << ans << '\n';
  }
  return 0;
}

Source 2

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    sort(a.begin(), a.end());
    int ans = 0;
    for (int k = 0; k <= n; k++) {
      if (k == 0 || a[k - 1] < k) {
        if (k == n || a[k] > k) {
          ans += 1;
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

1782C - Equal Frequencies

Explanation

Source

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<vector<int>> at(26);
    for (int i = 0; i < n; i++) {
      at[(int) (s[i] - 'a')].push_back(i);
    }
    vector<int> order(26);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return at[i].size() > at[j].size();
    });
    string res = "";
    int best = -1;
    for (int cnt = 1; cnt <= 26; cnt++) {
      if (n % cnt == 0) {
        int cur = 0;
        for (int i = 0; i < cnt; i++) {
          cur += min(n / cnt, (int) at[order[i]].size());
        }
        if (cur > best) {
          best = cur;
          res = string(n, ' ');
          vector<char> extra;
          for (int it = 0; it < cnt; it++) {
            int i = order[it];
            for (int j = 0; j < n / cnt; j++) {
              if (j < (int) at[i].size()) {
                res[at[i][j]] = (char) ('a' + i);
              } else {
                extra.push_back((char) ('a' + i));
              }
            }
          }
          for (char& c : res) {
            if (c == ' ') {
              c = extra.back();
              extra.pop_back();
            }
          }
        }
      }
    }
    cout << n - best << '\n';
    cout << res << '\n';
  }
  return 0;
}

1782D - Many Perfect Squares

Explanation

Source

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    int ans = 1;
    auto Test = [&](long long x) {
      int cnt = 0;
      for (int v : a) {
        long long u = llround(sqrtl(v + x));
        if (u * u == v + x) {
          cnt += 1;
        }
      }
      ans = max(ans, cnt);
    };
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        int diff = a[j] - a[i];
        for (int k = 1; k * k <= diff; k++) {
          if (diff % k == 0) {
            long long q = k + diff / k;
            if (q % 2 == 0) {
              q /= 2;
              if (q * q >= a[j]) {
                Test(q * q - a[j]);
              }
            }
          }
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

1782E - Rectangle Shrinking

Explanation

Source

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> r1(n), c1(n), r2(n), c2(n);
    for (int i = 0; i < n; i++) {
      cin >> r1[i] >> c1[i] >> r2[i] >> c2[i];
      assert(1 <= r1[i] && r1[i] <= r2[i] && r2[i] <= 2 && c1[i] <= c2[i]);
      --c1[i];
    }
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return c1[i] < c1[j];
    });
    set<pair<int, int>> s;
    int ans = 0;
    int p1 = -1;
    int p2 = -1;
    for (int i : order) {
      if (r1[i] == 1 && r2[i] == 2) {
        if (p1 >= c2[i]) {
          r1[i] = 2;
        }
        if (p2 >= c2[i]) {
          r2[i] = 1;
        }
        if (r1[i] > r2[i]) {
          continue;
        }
      }
      if (r1[i] == 1 && r2[i] == 2) {
        while (!s.empty()) {
          auto it = prev(s.end());
          if (it->first >= c1[i]) {
            c2[it->second] = c1[i];
            s.erase(it);
          } else {
            break;
          }
        }
        ans += (c2[i] - max(c1[i], p1)) + (c2[i] - max(c1[i], p2));
        p1 = p2 = c2[i];
        s.emplace(c2[i], i);
        continue;
      }
      assert(r1[i] == r2[i]);
      if (r1[i] == 1) {
        c1[i] = max(c1[i], p1);
        p1 = max(p1, c2[i]);
      } else {
        c1[i] = max(c1[i], p2);
        p2 = max(p2, c2[i]);
      }
      if (c1[i] < c2[i]) {
        ans += c2[i] - c1[i];
        s.emplace(c2[i], i);
      }
    }
    cout << ans << '\n';
    for (int i = 0; i < n; i++) {
      ++c1[i];
      if (r1[i] <= r2[i] && c1[i] <= c2[i]) {
        cout << r1[i] << " " << c1[i] << " " << r2[i] << " " << c2[i] << '\n';
      } else {
        cout << "0 0 0 0" << '\n';
      }
    }
  }
  return 0;
}

1782F - Bracket Insertion

Explanation

Source

#include <bits/stdc++.h>

using namespace std;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular operator-() const { return Modular(-value); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    return *this;
  }

  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  template <typename V, typename U>
  friend V& operator>>(V& stream, Modular<U>& number);

 private:
  Type value;
};

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
  return stream << number();
}

template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  Mint p;
  cin >> n >> p;
  p /= 10000;
  vector<vector<Mint>> C(n + 1, vector<Mint>(n + 1));
  for (int i = 0; i <= n; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
  }
  vector<vector<Mint>> dp(n + 1, vector<Mint>(n + 1));
  vector<vector<Mint>> aux(n + 1, vector<Mint>(n + 1));
  for (int b = 0; b <= n; b++) {
    dp[0][b] = aux[0][b] = 1;
  }
  for (int i = 1; i <= n; i++) {
    for (int b = 0; b <= n - i; b++) {
      for (int y = 0; y <= i - 1; y++) {
        dp[i][b] += C[i - 1][y] * aux[i - 1 - y][b] * (dp[y][b + 1] * p + (b == 0 ? 0 : dp[y][b - 1] * (1 - p)));
      }
      for (int j = 0; j <= i; j++) {
        aux[i][b] += dp[j][b] * dp[i - j][b] * C[i][j];
      }
    }
  }
  auto ans = dp[n][0];
  for (int i = 1; i <= 2 * n; i += 2) {
    ans /= i;
  }
  cout << ans << '\n';
  return 0;
}

1782G - Diverse Coloring

Explanation

Source (2nd approach)

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 1; i < n; i++) {
      cin >> p[i];
      --p[i];
    }
    for (int i = 2; i <= n; i++) {
      if (i == 4 && p[1] == 0 && p[2] == 1 && p[3] == 1) {
        cout << 2 << '\n';
      } else {
        cout << i % 2 << '\n';
      }
    }
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
      g[p[i]].push_back(i);
    }
    string res = "";
    auto Solve = [&](int nn) {
      vector<vector<vector<bool>>> good(nn);
      vector<vector<vector<vector<int>>>> prevs(nn);
      vector<int> sz(nn);
      vector<int> L(nn);
      vector<int> R(nn);
      function<void(int)> Dfs = [&](int v) {
        sz[v] += 1;
        for (int u : g[v]) {
          Dfs(u);
          sz[v] += sz[u];
        }
        L[v] = sz[v] / 2;
        R[v] = L[v] + 1;
        good[v].assign(2, vector<bool>(R[v] - L[v] + 1, false));
        prevs[v].assign(2, vector<vector<int>>(R[v] - L[v] + 1));
        auto Set = [&](int c, int k, vector<int> pr) {
          if (k >= L[v] && k <= R[v]) {
            good[v][c][k - L[v]] = true;
            prevs[v][c][k - L[v]] = pr;
          }
        };
        if (g[v].size() == 0) {
          Set(0, 1, {});
        }
        if (g[v].size() == 1) {
          int u = g[v][0];
          for (int cu = 0; cu < 2; cu++) {
            for (int ku = L[u]; ku <= R[u]; ku++) {
              if (good[u][cu][ku - L[u]]) {
                Set(1, 1 + (sz[u] - ku), {cu, ku, 1});
                if (cu == 1) {
                  Set(0, 1 + ku, {cu, ku, 0});
                }
              }
            }
          }
        }
        if (g[v].size() == 2) {
          int u = g[v][0];
          int w = g[v][1];
          for (int cu = 0; cu < 2; cu++) {
            for (int ku = L[u]; ku <= R[u]; ku++) {
              if (good[u][cu][ku - L[u]]) {
                for (int cw = 0; cw < 2; cw++) {
                  for (int kw = L[w]; kw <= R[w]; kw++) {
                    if (good[w][cw][kw - L[w]]) {
                      Set(1, 1 + (sz[u] - ku) + (sz[w] - kw), {cu, ku, 1, cw, kw, 1});
                      if (cu == 1) {
                        Set(1, 1 + ku + (sz[w] - kw), {cu, ku, 0, cw, kw, 1});
                      }
                      if (cw == 1) {
                        Set(1, 1 + (sz[u] - ku) + kw, {cu, ku, 1, cw, kw, 0});
                      }
                      if (cu == 1 && cw == 1) {
                        Set(0, 1 + ku + kw, {cu, ku, 0, cw, kw, 0});
                      }
                    }
                  }
                }
              }
            }
          }
        }
      };
      Dfs(0);
      int best = nn + 1;
      int best_k = -1;
      for (int k = L[0]; k <= R[0]; k++) {
        if (good[0][1][k - L[0]]) {
          int val = abs(k - (nn - k));
          if (val < best) {
            best = val;
            best_k = k;
          }
        }
      }
      assert(best <= nn);
      res = string(nn, '.');
      function<void(int, int, int)> Restore = [&](int v, int c, int k) {
        int ptr = 0;
        for (int u : g[v]) {
          res[u] = (prevs[v][c][k - L[v]][ptr + 2] == 0 ? res[v] : (char) ('w' ^ 'b' ^ res[v]));
          Restore(u, prevs[v][c][k - L[v]][ptr], prevs[v][c][k - L[v]][ptr + 1]);
          ptr += 3;
        }
      };
      res[0] = 'w';
      Restore(0, 1, best_k);
      return best;
    };
    Solve(n);
    cout << res << '\n';
  }
  return 0;
}

1782H1 - Window Signals (easy version)

Explanation

Source for easy version

#include <bits/stdc++.h>

using namespace std;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular operator-() const { return Modular(-value); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    return *this;
  }

  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  template <typename V, typename U>
  friend V& operator>>(V& stream, Modular<U>& number);

 private:
  Type value;
};

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}

template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
  return stream << number();
}

template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int h, w, k;
    cin >> h >> w >> k;
    vector<Mint> fib(h * w + 1);
    fib[0] = 1;
    fib[1] = 2;
    for (int i = 2; i <= h * w; i++) {
      fib[i] = fib[i - 1] + fib[i - 2];
    }
    vector<pair<int, int>> p(k);
    for (int i = 0; i < k; i++) {
      cin >> p[i].first >> p[i].second;
      --p[i].first; --p[i].second;
    }
    long long Q = 0;
    Mint ans = 0;
    for (int ww = 1; ww <= w; ww++) {
      for (int hh = 1; hh <= h; hh++) {
        for (int top = 0; top < 2; top++) {
          for (int bottom = 0; bottom < 2; bottom++) {
            for (int left = 0; left < 2; left++) {
              for (int right = 0; right < 2; right++) {
                int sign = ((top + bottom + left + right) % 2 == 0 ? 1 : -1);
                int rh = max(0, hh - top - bottom);
                int rw = max(0, ww - left - right);
                Q += rh * rw + (h - hh) * (w - ww);
                ans += sign * power(Mint(2), rh * rw);
                vector<vector<int>> g(hh * ww);
                vector<bool> must(hh * ww, false);
                bool any = false;
                for (int i = 0; i <= h - hh; i++) {
                  for (int j = 0; j <= w - ww; j++) {
                    vector<pair<int, int>> here;
                    for (auto& c : p) {
                      if (c.first >= i + top && c.first < i + hh - bottom && c.second >= j + left && c.second < j + ww - right) {
                        here.emplace_back(c.first - i - top, c.second - j - left);
                      }
                    }
                    if (here.size() == 0) {
                      any = true;
                    }
                    if (here.size() == 1) {
                      int x = here[0].first * rw + here[0].second;
                      must[x] = true;
                    }
                    if (here.size() == 2) {
                      int x = here[0].first * rw + here[0].second;
                      int y = here[1].first * rw + here[1].second;
                      g[x].push_back(y);
                      g[y].push_back(x);
                    }
                  }
                }
                if (!any) {
                  Mint ways = 1;
                  vector<bool> was(rh * rw, false);
                  for (int i = 0; i < rh * rw; i++) {
                    if (!was[i] && g[i].empty()) {
                      was[i] = true;
                      if (!must[i]) {
                        ways *= 2;
                      }
                    }
                  }
                  for (int i = 0; i < rh * rw; i++) {
                    if (!was[i] && g[i].size() == 1) {
                      vector<bool> seq;
                      int x = i;
                      while (true) {
                        was[x] = true;
                        seq.push_back(must[x]);
                        int to = -1;
                        for (int y : g[x]) {
                          if (!was[y]) {
                            to = y;
                            break;
                          }
                        }
                        if (to == -1) {
                          break;
                        }
                        x = to;
                      }
                      int sz = (int) seq.size();
                      int beg = 0;
                      while (beg < sz) {
                        if (seq[beg]) {
                          beg += 1;
                          continue;
                        }
                        int end = beg;
                        while (end + 1 < sz && !seq[end + 1]) {
                          end += 1;
                        }
                        int len = end - beg + 1;
                        ways *= fib[len];
                        beg = end + 1;
                      }
                    }
                  }
                  assert(was == vector<bool>(rh * rw, true));
                  ans -= sign * ways;
                }
              }
            }
          }
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

Source for hard version

#include <bits/stdc++.h>

using namespace std;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular operator-() const { return Modular(-value); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    return *this;
  }

  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  template <typename V, typename U>
  friend V& operator>>(V& stream, Modular<U>& number);

 private:
  Type value;
};

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}

template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
  return stream << number();
}

template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

class dsu {
 public:
  vector<int> p;
  vector<int> sz;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
    sz.assign(n, 1);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      sz[y] += sz[x];
      return true;
    }
    return false;
  }
};

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int h, w, k;
    cin >> h >> w >> k;
    vector<Mint> fib(h * w + 1);
    fib[0] = 1;
    fib[1] = 2;
    for (int i = 2; i <= h * w; i++) {
      fib[i] = fib[i - 1] + fib[i - 2];
    }
    vector<pair<int, int>> p(k);
    for (int i = 0; i < k; i++) {
      cin >> p[i].first >> p[i].second;
      --p[i].first; --p[i].second;
    }
    Mint ans = 0;
    for (int ww = 1; ww <= w; ww++) {
      for (int top = 0; top < 2; top++) {
        for (int left = 0; left < 2; left++) {
          for (int right = 0; right < 2; right++) {
            if (ww == 1 && left + right > 0) {
              continue;
            }
            int sign = ((top + left + right) % 2 == 0 ? 1 : -1);
            dsu d(h * ww);
            vector<vector<int>> g(h * ww);
            vector<bool> must(h * ww);
            bool done = false;
            Mint prod = power(Mint(2), (h - top) * (ww - left - right));
            for (int i = 0; i < h; i++) {
              for (int j = 0; j <= w - ww; j++) {
                vector<pair<int, int>> here;
                for (auto& c : p) {
                  if (c.first >= i + top && c.second >= j + left && c.second < j + ww - right) {
                    here.emplace_back(c.first - i, c.second - j);
                  }
                }
                if (here.size() == 0) {
                  ans += sign * prod;
                  done = true;
                  break;
                }
                if (here.size() == 1) {
                  int x = here[0].first * ww + here[0].second;
                  if (!must[x]) {
                    must[x] = true;
                    int px = d.get(x);
                    prod /= fib[d.sz[px]];
                    d.sz[px] -= 1;
                    int sub = 0;
                    for (int y : g[x]) {
                      if (!must[y]) {
                        sub += 1;
                      }
                    }
                    ans += sign * prod * fib[d.sz[px] - sub];
                    prod *= fib[d.sz[px]];
                  }
                }
                if (here.size() == 2) {
                  int x = here[0].first * ww + here[0].second;
                  int y = here[1].first * ww + here[1].second;
                  int px = d.get(x);
                  int py = d.get(y);
                  assert(px != py);
                  prod /= fib[d.sz[px]];
                  prod /= fib[d.sz[py]];
                  if (!must[x] && !must[y]) {
                    int subx = 1;
                    for (int t : g[x]) {
                      if (!must[t]) {
                        subx += 1;
                      }
                    }
                    int suby = 1;
                    for (int t : g[y]) {
                      if (!must[t]) {
                        suby += 1;
                      }
                    }
                    ans += sign * prod * fib[d.sz[px] - subx] * fib[d.sz[py] - suby];
                    g[x].push_back(y);
                    g[y].push_back(x);
                  }
                  d.unite(px, py);
                  prod *= fib[d.sz[py]];
                }
              }
              if (done) {
                break;
              }
              for (int j = left; j < ww - right; j++) {
                int x = (h - 1 - i) * ww + j;
                if (must[x]) {
                  done = true;
                  break;
                }
                int px = d.get(x);
                prod /= fib[d.sz[px]];
                d.sz[px] -= 1;
                prod *= fib[d.sz[px]];
                for (int y : g[x]) {
                  if (!must[y]) {
                    must[y] = true;
                    int py = d.get(y);
                    prod /= fib[d.sz[py]];
                    d.sz[py] -= 1;
                    prod *= fib[d.sz[py]];
                  }
                }
              }
              if (done) {
                break;
              }
            }
          }
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

Comments (20)

Show archived | Write comment?

kartel

23 months ago, # |

+14

Nice

Editorial is here)

→ Reply

MathisEverywhere

← Rev. 2 →

+34

omg tourist Editorial

bj126627885

23 months ago, # ^ |

+10

Barys

omg tourist Editoral

This_is_Adroit

7 months ago, # ^ |

-6

Yaria

+52

Do you know why your comment was downvoted? Probably not. Actually, the same comment can be upvoted in a different time/place.

A possible reason is that some random person just randomly downvoted your comment and then some other insane users just continue downvoting without thinking. Toxic, crazy, but this is the reality here.

thanhchauns2

A simple solution to problem E:

The solution for height = 1 is trivial. I'll discuss about a similar solution for height = 2.

Step 1 : Solve the trivial problem for the rectangle covers both rows only.

Step 2 : Let's detach the rectangles we chose in step 1 into 2 rectangles in the first and second row.

Step 3 : Solve the trivial problem for each rows.

Step 4 : Merge the rectangle in step 2.

Caution: for the rectangles created in step 2, you can only remove or keep them without shrinking.

My submission: 189882008

GlowCheese

adu sir thanhchauns2 manh wa

Alesh

Why are there so few upvotes on this blog?

strapple

+23

Why are there so few upvotes on this comment?

ACGN

I would recommend replacing "Source" with "(Source) Code", at first glance I thought it was the inspiration or the source of the problem :D

the_Incharge

what is the fast factorization method in in problem D.

IanISam

Check all numbers n where n*n<=p and n>=1 where p is the number you want to factor. The factors will always be when p%n==0 and the factors themselves will be n and p/n. This works because when we check all numbers less than or equal to sqrt of p, the following pair(p/n) will get all the numbers greater than or equal to sqrt of p.

This is the general factorization I thought there is faster factorization method possible for this. By the way how to optimize the second part of the problem.

Rahul7_77_77

Can anyone please explain C a little bit detailed

TheDarkKnight03

19 months ago, # ^ |

We iterate through all the divisors of length N of string, and for each character greedily try to change them so that equal frequencies can be maintained. The greedy idea for constructing the string is explained in the editorial.

Here's a link to my submission, maybe the top submissions would be shorter: https://codeforces.net/contest/1781/submission/206606856

FiniteMoves

12 months ago, # |

can anyone give hint on how to solve the bonus task of problem $$$D$$$ given in the editorial?

Tethet

2 weeks ago, # ^ |

This is the solution to the bonus task.

Submission: 295549509

The logic is very similar to what is given in tutorial. Hope it helps

naman.gokhru.mst20

7 months ago, # |

loved your approach @tourist everytime.

123gjweq2

11 days ago, # |

$$$E$$$ has some pretty weak tests. My $$$O(n^2 \log n)$$$ solution passed in $$$<1$$$ second. Can more testcases be added?