제출 #1252842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252842		kunzaZa183	Boat (APIO16_boat)	C++20	0 / 100	1 ms	320 KiB

boat

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1e9 + 7;
const int mn = 1500;
ll logpow(int a, int 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 choose(int n, int r) {
  if (n < r)
    return 0;

  return fac[n] * logpow(fac[r], MOD - 2) % MOD * logpow(fac[n - r], MOD - 2) %
         MOD;
}
int 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);
  }

  vector<vector<array<ll, 3>>> vvi; // surplus, stage, multi
  vvi.emplace_back(si.size());

  for (int i = 0; i < n; i++) {
    ll cur = 1;

    for (int j = 0; j + 1 < sth.size(); j++) {
      auto &[plus, stage, multi] = vvi[i][j];
      ll befcur = cur;
      cur += plus * (sth[j + 1] - sth[j]) % MOD;
      cur %= MOD;

      cur += choose((sth[j + 1] - sth[j]) + stage, stage + 1) * multi % MOD;
      cur %= MOD;

      if (sth[j] >= vpii[i].first && sth[j] <= vpii[i].second) {
        if (stage == 0 && multi == 0) {
          multi = befcur;
          stage = 0;
        } else {
          plus += befcur;
          plus %= MOD;

          stage++;
        }
      }
    }

    vvi.push_back(vvi.back());
  }

  ll ans = 0;

  for (int j = 0; j + 1 < sth.size(); j++) {
    auto &[plus, stage, multi] = vvi.back()[j];
    ans += plus * (sth[j + 1] - sth[j]) % MOD;
    ans %= MOD;

    ans += choose((sth[j + 1] - sth[j]) + stage, stage + 1) * multi % MOD;
    ans %= MOD;
  }

  cout << ans << "\n";
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42