結果

問題 No.907 Continuous Kadomatu
ユーザー risujiroh
提出日時 2019-10-11 22:35:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,783 bytes
コンパイル時間 1,962 ms
コンパイル使用メモリ 185,440 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-25 08:27:09
合計ジャッジ時間 2,900 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4 WA * 1
other AC * 3 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

template<unsigned P> struct ModInt {
  using M = ModInt;
  unsigned v;
  constexpr ModInt() : v(0) {}
  constexpr ModInt(unsigned _v, int) : v(_v) {}
  template<class Z> ModInt(const Z& a) : v((a < 0 ? P - -a % P : a) % P) {}
  static constexpr unsigned p() { return P; }
  M operator+() const { return *this; }
  M operator-() const { return {v ? P - v : 0, 0}; }
  explicit operator bool() const noexcept { return v; }
  bool operator!() const noexcept { return !(bool)*this; }
  M& operator*=(M r) { v = (uint64_t)v * r.v % P; return *this; }
  M& operator/=(M r) { return *this *= r.inv(); }
  M& operator+=(M r) { if ((v += r.v) >= P) v -= P; return *this; }
  M& operator-=(M r) { if ((v += P - r.v) >= P) v -= P; return *this; }
  M inv() const {
    int a = v, b = P, x = 1, u = 0;
    while (b) {
      int q = a / b;
      swap(a -= q * b, b);
      swap(x -= q * u, u);
    }
    assert(a == 1);
    return x;
  }
  template<class Z> M pow(Z n) const {
    if (n < 0) return pow(-n).inv();
    M res = 1;
    for (M a = *this; n; a *= a, n >>= 1) if (n & 1) res *= a;
    return res;
  }
  friend M operator*(M l, M r) { return M(l) *= r; }
  friend M operator/(M l, M r) { return M(l) /= r; }
  friend M operator+(M l, M r) { return M(l) += r; }
  friend M operator-(M l, M r) { return M(l) -= r; }
  friend ostream& operator<<(ostream& os, M r) { return os << r.v; }
  friend bool operator==(M l, M r) { return l.v == r.v; }
  friend bool operator!=(M l, M r) { return !(l == r); }
};
using Mint = ModInt<(unsigned)1e9 + 7>;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<> a(n), b(n); for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];
  if (n & 1) {
    ++n;
    a.push_back(1e9 + 7);
    b.push_back(1e9 + 8);
  }

  auto len = [](int l0, int r0, int l1, int r1) -> Mint {
    return max(min(r0, r1) - max(l0, l1), 0);
  };

  Mint res = 1;
  V<Mint> pr(n);
  for (int i = 0; i < n; i += 2) {
    V<> v{a[i], b[i], a[i + 1], b[i + 1]};
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
    int m = v.size() - 1;
    V<Mint> p(m), q(m);
    for (int j = 0; j < m; ++j) {
      p[j] = len(a[i], b[i], v[j], v[j + 1]) / (b[i] - a[i]);
      q[j] = len(a[i + 1], b[i + 1], v[j], v[j + 1]) / (b[i + 1] - a[i + 1]);
    }
    Mint crr;
    for (int k = 0; k < m; ++k) for (int j = 0; j <= k; ++j) {
      if (j < k) {
        crr += p[j] * q[k];
      } else {
        crr += p[j] * q[k] / 2;
      }
    }
    pr[i] = crr;
    res *= crr;
  }

  V<Mint> c(8);
  c[0] = 1;
  c[1] = Mint(2).inv();
  c[2] = Mint(2).inv();
  c[3] = Mint(3).inv();
  c[4] = Mint(2).inv();
  c[5] = Mint(4).inv();
  c[6] = Mint(3).inv();
  c[7] = Mint(5) / 24;

  for (int i = 0; i < n - 2; i += 2) {
    V<> v;
    for (int di = 0; di < 4; ++di) {
      v.push_back(a[i + di]);
      v.push_back(b[i + di]);
    }
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
    int m = v.size() - 1;
    VV<Mint> p(4, V<Mint>(m));
    for (int di = 0; di < 4; ++di) for (int j = 0; j < m; ++j) {
      p[di][j] = len(a[i + di], b[i + di], v[j], v[j + 1]) / (b[i + di] - a[i + di]);
    }
    Mint crr;
    for (int j0 = 0; j0 < m; ++j0) for (int j1 = 0; j1 < m; ++j1) for (int j2 = 0; j2 < m; ++j2) for (int j3 = 0; j3 < m; ++j3) {
      if (j0 > j1) continue;
      if (j1 < j2) continue;
      if (j2 > j3) continue;
      Mint tmp = p[0][j0] * p[1][j1] * p[2][j2] * p[3][j3];
      tmp *= c[4 * (j0 == j1) + 2 * (j1 == j2) + (j2 == j3)];
      crr += tmp;
    }
    if (crr) {
      res *= crr / (pr[i] * pr[i + 2]);
    }
  }
  cout << res << '\n';
}
0