Submission #1254635

#TimeUsernameProblemLanguageResultExecution timeMemory
1254635kunzaZa183Boat (APIO16_boat)C++20
100 / 100
1729 ms10288 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1e9 + 7;
const int mn = 501, msth = 1001;
ll logpow(ll a, ll b) {
  if (b == 0)
    return 1;
  if (b == 1)
    return a;
  ll x = logpow(a, b / 2);
  if (b % 2 == 1)
    return x * x % MOD * a % MOD;
  return x * x % MOD;
}
vector<ll> fac;
ll precomp[msth][mn] = {}, dp[msth][mn] = {}, prec[mn][mn] = {};
signed main() {
  int n;
  cin >> n;
  vector<pair<int, int>> vpii(n);
  for (auto &a : vpii)
    cin >> a.first >> a.second;

  fac = vector<ll>(mn);
  fac[0] = 1;
  for (int i = 1; i < mn; i++)
    fac[i] = fac[i - 1] * i % MOD;

  set<int> si;
  for (auto [a, b] : vpii)
    si.insert(a), si.insert(b + 1);

  vector<ll> sth;
  for (auto a : si) {
    sth.push_back(a);
  }

  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= i; j++)
      prec[i][j] = fac[i] * logpow(fac[j], MOD - 2) % MOD *
                   logpow(fac[i - j], MOD - 2) % MOD;

  vector<int> helper(n + 1);
  for (int i = 0; i + 1 < sth.size(); i++) {

    ll cur = sth[i + 1] - sth[i];
    for (int j = 1; j <= n; j++) {
      helper[j] = cur * logpow(fac[j], MOD - 2) % MOD;
      cur = cur * (sth[i + 1] - sth[i] - j) % MOD;
    }

    for (int j = 1; j <= n; j++) {
      for (int k = 0; k + 1 <= j && k + 1 <= sth[i + 1] - sth[i]; k++) {
        precomp[i][j] += prec[j - 1][k] * helper[k + 1] % MOD;
        precomp[i][j] %= MOD;
      }
    }
  }

  int ans = 0;
  dp[0][0] = 1;
  for (int i = 0; i + 1 < sth.size(); i++) {
    for (int j = 0; j < n; j++) {
      dp[i + 1][j] += dp[i][j];
      dp[i + 1][j] %= MOD;

      int ct = 0;
      for (int k = j; k < n; k++) {
        if (sth[i] >= vpii[k].first && vpii[k].second + 1 >= sth[i + 1]) {
          ct++;

          dp[i + 1][k + 1] += dp[i][j] * precomp[i][ct] % MOD;
          dp[i + 1][k + 1] %= MOD;
          ans += dp[i][j] * precomp[i][ct] % MOD;
          ans %= MOD;
        }
      }
    }
  }

  cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...