제출 #1254626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254626		kunzaZa183	Boat (APIO16_boat)	C++20	58 / 100	2095 ms	10824 KiB

boat

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

  ll num = 1;
  for (int i = 0; i < r; i++)
    num = num * ((n - i) % MOD) % MOD;

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

  vector<vector<ll>> precomp(sth.size(), vector<ll>(n + 1)),
      dp(sth.size(), vector<ll>(n + 1)), prec(n + 1, vector<ll>(n + 1));

  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++) {

    for (int j = 1; j <= n; j++)
      helper[j] = choose(sth[i + 1] - sth[i], j);

    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++) {
      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;
        }
      }

      dp[i + 1][j] += dp[i][j];
      dp[i + 1][j] %= MOD;
    }
  }

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

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