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 - Поход в кинотеатр

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 - Равные частоты

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 - Много точных квадратов

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 - Сжатие прямоугольников

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 - Вставка скобок

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 - Разнообразная раскраска

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 - Оконные сигналы (простая версия)

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;
}

Комментарии (18)

Показать архивные | Написать комментарий?

kartel

3 года назад, скрыть # |

+14

Nice

Editorial is here)

→ Ответить

MathisEverywhere

← Rev. 2 →

+34

omg tourist Editorial

bj126627885

3 года назад, скрыть # ^ |

+10

Barys

omg tourist Editoral

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

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://mirror.codeforces.com/contest/1781/submission/206606856

FiniteMoves

2 года назад, скрыть # |

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

123gjweq2

16 месяцев назад, скрыть # |

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

Coder_GEAR5

14 месяцев назад, скрыть # |

For problem C:

Store the frequencies of each character in a 2D array freq[][] of size 26*2 (Character in 1st column and it's corresponding frequency in 2nd column. Sort the freq[][] array by frequencies(2nd col). Now there can be 1 <= d <= 26 (N % d == 0) distinct characters. I claim that a sliding window of length 'd' over the freq[][] array will give me the required characters with each character having frequency of N/d. This window will be the one that minimizes the loss. But how to calculate loss?

A simple solution will be the in the sliding window match the higher frequency characters with the lower frequency characters and balance out the remaining frequencies. This is due the fact that once we fix a frequency (N/d) we are picking the characters that are close to that frequency.

Here is the java submission: https://mirror.codeforces.com/contest/1781/submission/308437460