#1134582 (C++23) No.3366 Reversible Tile:Revival

• 問題: No.3366 Reversible Tile:Revival
• ユーザー: risujiroh
• 提出日時: 2025-11-17 22:39:49
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 279 ms / 3,000 ms
• コード長: 8,631 bytes
• コンパイル時間: 4,410 ms
• コンパイル使用メモリ: 330,372 KB
• 実行使用メモリ: 34,376 KB
• 最終ジャッジ日時: 2025-11-17 22:40:05
• 合計ジャッジ時間: 14,207 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 45

ソースコード

#if __INCLUDE_LEVEL__ == 0

#include __BASE_FILE__

using Mint = atcoder::modint998244353;

Comb<Mint> comb;

void Solve() {
  int m;
  vector<int64_t> w;
  vector<int> L, R;
  {
    int64_t n;
    IN(n, m);
    vector<int64_t> l(m), r(m);
    for (int i : Rep(0, m)) {
      IN(l[i], r[i]);
      --l[i];
    }
    vector<int64_t> U;
    U.reserve(2 * m + 2);
    U.push_back(0);
    U.push_back(n);
    U.insert(U.end(), ALL(l));
    U.insert(U.end(), ALL(r));
    ranges::sort(U);
    APPLY(U.erase, ranges::unique(U));
    w.resize(Sz(U) - 1);
    for (int i : Rep(0, Sz(w))) {
      w[i] = U[i + 1] - U[i];
    }
    L.resize(m);
    R.resize(m);
    for (int i : Rep(0, m)) {
      L[i] = int(ranges::lower_bound(U, l[i]) - U.begin());
      R[i] = int(ranges::lower_bound(U, r[i]) - U.begin());
    }
  }

  int n = Sz(w);

  Mint ans = 0;

  {
    vector<int> f(n + 1);
    for (int i : Rep(0, m)) {
      ++f[L[i]];
      --f[R[i]];
    }
    for (int i : Rep(0, n)) {
      f[i + 1] += f[i];
    }

    for (int i : Rep(0, n)) {
      Mint cur = 0;
      if (f[i] > 0) {
        cur = comb.Inv(2);
      } else {
        cur = 1;
      }
      cur *= w[i];
      cur *= w[i];
      ans += cur;
    }
  }

  vector<vector<int>> fromL(n + 1);
  vector<vector<int>> fromR(n + 1);
  for (int k : Rep(0, m)) {
    fromL[L[k]].push_back(k);
    fromR[R[k]].push_back(k);
  }

  priority_queue q1(greater{}, vector<pair<int, int>>{});
  priority_queue<pair<int, int>> q3;

  set<int> yet(ALL(Rep(0, n)));

  atcoder::fenwick_tree<int64_t> f(n);

  vector<int64_t> pref(n + 1);
  for (int i : Rep(0, n)) {
    pref[i + 1] = pref[i] + w[i];
  }

  for (int i : Rev(Rep(0, n))) {
    /* for (int j : Rep(i + 1, n)) {
      int mask = 0;
      for (int k : Rep(0, m)) {
        if (L[k] <= i && i < R[k] && R[k] <= j) {
          mask |= 1;
        }
        if (i < L[k] && L[k] <= j && j < R[k]) {
          mask |= 2;
        }
        if (L[k] <= i && j < R[k]) {
          mask |= 4;
        }
      }
      Mint cur = comb.Inv(1 << min(__popcount(mask), 2));
      cur *= w[i];
      cur *= w[j];
      ans += 2 * cur;
    } */

    auto go = [&](int l, int r, int base) {
      if (l > r) {
        return;
      }
      int64_t w1 = f.sum(l, r);
      int64_t w0 = pref[r] - pref[l] - w1;
      {
        Mint cur = comb.Inv(1 << base);
        cur *= w[i];
        cur *= w0;
        ans += 2 * cur;
      }
      {
        Mint cur = comb.Inv(1 << min(base + 1, 2));
        cur *= w[i];
        cur *= w1;
        ans += 2 * cur;
      }
      /* for (int j : Rep(l, r)) {
        bool exists = false;
        for (int k : Rep(0, m)) {
          if (i < L[k] && L[k] <= j && j < R[k]) {
            exists = true;
            break;
          }
        }
        Mint cur = comb.Inv(1 << min(base + exists, 2));
        cur *= w[i];
        cur *= w[j];
        ans += 2 * cur;
      } */
    };

    for (int k : fromR[i + 1]) {
      q1.emplace(R[k], k);
    }
    while (!q1.empty() && i < L[q1.top().second]) {
      q1.pop();
    }
    int m1 = q1.empty() ? n : q1.top().first;
    // m1 <= j は type 1 が存在

    for (int k : fromR[i + 1]) {
      q3.emplace(R[k], k);
      while (!q3.empty() && i < L[q3.top().second]) {
        q3.pop();
      }
    }
    int m3 = q1.empty() ? i + 1 : q3.top().first;
    // j < m3 は type 3 が存在

    for (int k : fromL[i + 1]) {
      for (auto it = yet.lower_bound(L[k]); it != yet.end() && *it < R[k]; it = yet.erase(it)) {
        f.add(*it, w[*it]);
      }
    }

    go(i + 1, min(m1, m3), 1);
    go(m1, m3, 2);
    go(m3, m1, 0);
    go(max(m1, m3), n, 1);
  }

  ans *= Mint(2).pow(m);

  OUT(ans);
}

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

  Solve();
}

#elif __INCLUDE_LEVEL__ == 1

#include <bits/stdc++.h>

#include <atcoder/fenwicktree.hpp>
#include <atcoder/modint.hpp>

template <class T>
class Comb {
 public:
  Comb() = default;

  explicit Comb(int n) {
    Reserve(n);
  }

  void Reserve(int n) {
    const int sz = static_cast<int>(fact_.size());
    if (n < sz) {
      return;
    }
    fact_.resize(n + 1);
    const int nsz = static_cast<int>(fact_.capacity());
    fact_.resize(nsz);
    fact_inv_.resize(nsz);
    for (int i = sz; i < nsz; ++i) {
      fact_[i] = T(i) * fact_[i - 1];
    }
    fact_inv_.back() = T(1) / fact_.back();
    for (int i = nsz; --i > sz;) {
      fact_inv_[i - 1] = fact_inv_[i] * T(i);
    }
  }

  T Fact(int n) {
    assert(n >= 0);
    Reserve(n);
    return fact_[n];
  }

  T FactInv(int n) {
    if (n < 0) {
      return T(0);
    }
    Reserve(n);
    return fact_inv_[n];
  }

  T FactRatio(int a, int b) {
    if (a >= 0) {
      return Fact(a) * FactInv(b);
    }
    assert(b < 0);
    const T t = FactRatio(~b, ~a);
    return (a - b) % 2 == 0 ? t : -t;
  }

  T Inv(int n) {
    assert(n != 0);
    return FactRatio(n - 1, n);
  }

  T Prod(std::ranges::iota_view<int, int> r) {
    return FactRatio(r.end()[-1], r[-1]);
  }

  T ProdInv(std::ranges::iota_view<int, int> r) {
    assert(r[0] > 0 || r.end()[-1] < 0);
    return FactRatio(r[-1], r.end()[-1]);
  }

  T Perm(int n, int k) {
    assert(n >= 0 ? true : k > n);
    return FactRatio(n, n - k);
  }

  T PermInv(int n, int k) {
    assert(n >= 0 ? k <= n : true);
    return FactRatio(n - k, n);
  }

  T Binom(int n, int k) {
    k = std::max(k, n - k);
    return Perm(n, k) * FactInv(k);
  }

  T BinomInv(int n, int k) {
    assert(n >= 0 ? 0 <= k && k <= n : 0 <= k || k <= n);
    k = std::max(k, n - k);
    return PermInv(n, k) * Fact(k);
  }

  T Multinom(std::span<const int> ks) {
    if (ks.size() < 2) {
      return T(1);
    }
    const int n = std::reduce(ks.begin(), ks.end());
    const int& min_k = *std::ranges::min_element(ks);
    T ret = FactRatio(n, min_k);
    for (const int& k : ks) {
      if (&k != &min_k) {
        ret *= FactInv(k);
      }
    }
    return ret;
  }

  template <class... Ks>
    requires(... && std::same_as<Ks, int>)
  T Multinom(Ks... ks) {
    return Multinom(std::initializer_list<int>{ks...});
  }

  T MultinomInv(std::span<const int> ks) {
    if (ks.size() < 2) {
      return T(1);
    }
    const int n = std::reduce(ks.begin(), ks.end());
    const int& min_k = *std::ranges::min_element(ks);
    assert(n >= 0 ? min_k >= 0
                  : std::ranges::all_of(ks, [&](auto& k) { return &k == &min_k || k >= 0; }));
    T ret = FactRatio(min_k, n);
    for (const int& k : ks) {
      if (&k != &min_k) {
        ret *= Fact(k);
      }
    }
    return ret;
  }

  template <class... Ks>
    requires(... && std::same_as<Ks, int>)
  T MultinomInv(Ks... ks) {
    return MultinomInv(std::initializer_list<int>{ks...});
  }

  T Homogeneous(int n, int k) {
    return Binom(n + k - 1, k);
  }

  T Catalan(int n) {
    assert(n >= 0);
    return Fact(2 * n) * FactInv(n) * FactInv(n + 1);
  }

  T Catalan(int n, int k) {
    assert(0 <= k && k <= n);
    return T(n - k + 1) * Fact(n + k) * FactInv(n + 1) * FactInv(k);
  }

 private:
  std::vector<T> fact_{T(1)};
  std::vector<T> fact_inv_{T(1)};
};

template <class T> concept MyRange = std::ranges::range<T> && !std::convertible_to<T, std::string_view>;
template <class T> concept MyTuple = std::__is_tuple_like<T>::value && !MyRange<T>;

namespace std {

istream& operator>>(istream& is, MyRange auto&& r) {
  for (auto&& e : r) is >> e;
  return is;
}
istream& operator>>(istream& is, MyTuple auto&& t) {
  apply([&](auto&... xs) { (is >> ... >> xs); }, t);
  return is;
}

ostream& operator<<(ostream& os, MyRange auto&& r) {
  auto sep = "";
  for (auto&& e : r) os << exchange(sep, " ") << e;
  return os;
}
ostream& operator<<(ostream& os, MyTuple auto&& t) {
  auto sep = "";
  apply([&](auto&... xs) { ((os << exchange(sep, " ") << xs), ...); }, t);
  return os;
}

template <class T, atcoder::internal::is_modint_t<T>* = nullptr>
istream& operator>>(istream& is, T& x) {
  int v;
  is >> v;
  x = T::raw(v);
  return is;
}

template <class T, atcoder::internal::is_modint_t<T>* = nullptr>
ostream& operator<<(ostream& os, const T& x) {
  return os << x.val();
}

}  // namespace std

using namespace std;

#define LAMBDA(x, ...) ([&](auto&& x) -> decltype(auto) { return __VA_ARGS__; })
#define ALL(r) begin(r), end(r)
#define APPLY(f, r, ...) LAMBDA(_r, f(ALL(_r), ##__VA_ARGS__))(r)
#define Rev views::reverse
#define Rep(...) [](int l, int r) { return views::iota(min(l, r), r); }(__VA_ARGS__)
#define Sz(r) int(size(r))
#define IN(...) (cin >> forward_as_tuple(__VA_ARGS__))
#define OUT(...) (cout << forward_as_tuple(__VA_ARGS__) << '\n')

#endif  // __INCLUDE_LEVEL__ == 1