代码

#include <cstdio>

#include <vector>
#include <map>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

const int P = 1000000007;

int norm(int x) { return x >= P ? x - P : x; }

void add(int& x, int y) {
  if ((x += y) >= P)
    x -= P;
}

void sub(int& x, int y) {
  if ((x -= y) < 0)
    x += P;
}

vector<int> fac, inv, ifac;
vector<pair<int, int>> lmt;

struct Poly {
  vector<int> v;
  
  Poly() : v() {}
  
  Poly(const vector<int>& v) : v(v) {}
  
  int eval(int x) const {
    if (x < v.size())
      return v[x];
    int ret = 0;
    vector<int> ev(v.size());
    int n = (int)v.size() - 1;
    ev.back() = x - n;
    for (int i = n - 1; i >= 0; --i)
      ev[i] = ev[i + 1] * (ll)(x - i) % P;
    int prd = 1;
    for (int i = 0; i <= n; ++i) {
      int contr = prd * (ll)ifac[i] % P * ifac[n - i] % P;
      if (i < n)
        contr = contr * (ll)ev[i + 1] % P;
      if ((n - i) & 1)
        ret = (ret + contr * (ll)(P - v[i])) % P;
      else
        ret = (ret + contr * (ll)v[i]) % P;
      prd = prd * (ll)(x - i) % P;
    }/*
    LOG("EVAL([");
    for (int i = 0; i < v.size(); ++i)
      LOG("%d ", v[i]);
    LOG("],%d) = %d\n", x, ret);*/
    return ret;
    // I_k(x) = a[k] * (x-0)*(x-1)*...(x-n) / ((x-k) * k! * (n-k)! * (-1)^(n-k)) / 
  }
  
  int deg() const { return (int)v.size() - 1; }
  
  void extend(int deg) {
    while (v.size() <= deg)
      v.push_back(eval(v.size()));/*
    LOG("EXTEND TO [");
    for (int i = 0; i < v.size(); ++i)
      LOG("%d ", v[i]);
    LOG("]\n");*/
  }
};

struct Piecewise {
  vector<pair<int, Poly>> piece;
  
  Piecewise() : piece(1, make_pair(0, Poly({0}))) {}
  
  Piecewise(const vector<pair<int, Poly>>& piece) : piece(piece) {}
  
  Piecewise(int) : piece({make_pair(0, Poly({1})), make_pair(1, Poly({0}))}) {}
  
  void split(int x) {
    for (int i = 0; i < piece.size(); ++i)
      if (piece[i].first == x)
        return;
    if (x < piece.front().first) {
      piece.insert(piece.begin(), make_pair(x, Poly({0})));
    } else {
      for (int i = 0; i < piece.size(); ++i)
        if (i + 1 == piece.size() || x < piece[i + 1].first) {
          vector<int> v(piece[i].second.v.size());
          for (int j = 0; j < v.size(); ++j)
            v[j] = piece[i].second.eval(x - piece[i].first + j);
          piece.insert(piece.begin() + i + 1, make_pair(x, Poly(v)));
          return;
        }
    }
  }
  
  void prefix() {
    int sum = 0;
    for (int i = 0; i < piece.size(); ++i) {
      if (piece[i].second.deg() == 0 && piece[i].second.v.front() == 0) {
        piece[i].second.v.front() = sum;
        continue;
      }
      piece[i].second.extend(piece[i].second.deg() + 1);
      /*LOG("PREFIX [");
      for (int j = 0; j < piece[i].second.v.size(); ++j)
        LOG("%d ", piece[i].second.v[j]);
      LOG("] = [");*/
      add(piece[i].second.v.front(), sum);
      for (int j = 1; j <= piece[i].second.deg(); ++j)
        add(piece[i].second.v[j], piece[i].second.v[j - 1]);
      if (i + 1 < piece.size())
        sum = piece[i].second.eval(piece[i + 1].first - piece[i].first - 1);
      /*for (int j = 0; j < piece[i].second.v.size(); ++j)
        LOG("%d ", piece[i].second.v[j]);
      LOG("]\n");*/ 
    }
  }
  
  void oprefix() {
    int sum = 0;
    for (int i = 0; i < piece.size(); ++i) {
      if (piece[i].second.deg() == 0 && piece[i].second.v.front() == 0) {
        piece[i].second.v.front() = sum;
        continue;
      }
      /*LOG("OPREFIX [");
      for (int j = 0; j < piece[i].second.v.size(); ++j)
        LOG("%d ", piece[i].second.v[j]);
      LOG("] = [");*/
      piece[i].second.v.insert(piece[i].second.v.begin(), sum);
      for (int j = 1; j <= piece[i].second.deg(); ++j)
        add(piece[i].second.v[j], piece[i].second.v[j - 1]);
      /*for (int j = 0; j < piece[i].second.v.size(); ++j)
        LOG("%d ", piece[i].second.v[j]);
      LOG("]\n");*/
      if (i + 1 < piece.size())
        sum = piece[i].second.eval(piece[i + 1].first - piece[i].first);
    }
  }
};

Piecewise operator+(Piecewise lhs, Piecewise rhs) {
  for (int i = 0; i < lhs.piece.size(); ++i)
    rhs.split(lhs.piece[i].first);
  for (int i = 0; i < rhs.piece.size(); ++i)
    lhs.split(rhs.piece[i].first);
  for (int i = 0; i < rhs.piece.size(); ++i) {
    lhs.piece[i].second.extend(rhs.piece[i].second.deg());
    rhs.piece[i].second.extend(lhs.piece[i].second.deg());
    for (int j = 0; j <= lhs.piece[i].second.deg(); ++j)
      add(lhs.piece[i].second.v[j], rhs.piece[i].second.v[j]);
  }
  return lhs;
}

Piecewise operator*(Piecewise lhs, Piecewise rhs) {
  for (int i = 0; i < lhs.piece.size(); ++i)
    rhs.split(lhs.piece[i].first);
  for (int i = 0; i < rhs.piece.size(); ++i)
    lhs.split(rhs.piece[i].first);
  for (int i = 0; i < rhs.piece.size(); ++i) {
    int dg = lhs.piece[i].second.deg() + rhs.piece[i].second.deg();
    lhs.piece[i].second.extend(dg);
    rhs.piece[i].second.extend(dg);
    for (int j = 0; j <= lhs.piece[i].second.deg(); ++j)
      lhs.piece[i].second.v[j] = lhs.piece[i].second.v[j] * (ll)rhs.piece[i].second.v[j] % P;
  }
  return lhs;
}

int iabs(int x) { return x < 0 ? -x : x; }

map<pair<int, int>, Piecewise> memo;
Piecewise dp(int l, int r) {
  if (memo.count(make_pair(l, r)))
    return memo[make_pair(l, r)];
  if (l > r)
    return Piecewise(1);
  Piecewise ret = Piecewise();
  for (int i = max(l, (l + r) / 2 - 1); i <= min((l + r) / 2 + 2, r); ++i) {
    int d1 = i - l, d2 = r - i;
    if (iabs(d1 - d2) <= 2) {
      Piecewise ls = dp(l, i - 1), rs = dp(i + 1, r);
      ls.prefix();
      rs.oprefix();
      Piecewise con = ls * rs;
      int a = lmt[i].first, b = lmt[i].second + 1;
      con.split(a);
      con.split(b);
      int beg = 0;
      while (con.piece[beg].first != a) ++beg;
      int ed = beg;
      while (con.piece[ed].first != b) ++ed;
      Piecewise cont = vector<pair<int, Poly>>(con.piece.begin() + beg, con.piece.begin() + ed);
      cont.piece.emplace_back(b, Poly({0}));
      ret = ret + cont;
    }
  }
  return memo[make_pair(l, r)] = ret;
}

int main() {

  int n;
  scanf("%d", &n);
  lmt.resize(n);
  for (int i = 0; i < n; ++i)
    scanf("%d%d", &lmt[i].first, &lmt[i].second);
  
  int m = n;
  fac.resize(m + 1);
  fac[0] = 1;
  for (int i = 1; i <= m; ++i)
    fac[i] = fac[i - 1] * (ll)i % P;
  inv.resize(m + 1);
  inv[1] = 1;
  for (int i = 2; i <= m; ++i)
    inv[i] = -(P / i) * (ll)inv[P % i] % P + P;
  ifac.resize(m + 1);
  ifac[0] = 1;
  for (int i = 1; i <= m; ++i)
    ifac[i] = ifac[i - 1] * (ll)inv[i] % P;
  
  Piecewise ans = dp(0, n - 1);
  ans.prefix();
  printf("%d\n", ans.piece.back().second.v.front());
  
  return 0;
}

评测结果