Submission #46746

#	Time	Username	Problem	Language	Result	Execution time	Memory
46746		Trans	Boat (APIO16_boat)	C++14	100 / 100	1096 ms	10748 KiB

boat

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define repd(i, a, b) for (int i = (a) - 1; i >= b; i--)
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)a.size())

typedef long long ll;

const int mod = 1e9 + 7;
const int maxn = 1e3 + 5;

int n, a[maxn], b[maxn];
ll precal[maxn][maxn], inv[maxn];
int has[maxn];
map<int, int> mm;
ll dp[maxn][maxn], f[maxn];
vector<ll> vi;

ll power_mod(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b % 2) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}

int main() {
  rep(i, 1, maxn) {
    inv[i] = power_mod(i, mod - 2);
  }

  cin >> n;

  // mm[0];
  rep(i, 0, n) {
    cin >> a[i] >> b[i];
    mm[a[i] - 1]++;
    mm[b[i]]++;
  }

  int cnt = 0;
  for (auto it = mm.begin(); it != mm.end(); it++) {
    it->se = cnt++;
    vi.pb(it->fi);
  }

  rep(i, 0, n) {
    int hi = mm[b[i]] + 1;
    int lo = mm[a[i] - 1] + 1;
    rep(j, lo, hi) {
      has[j]++;
    }
  }

  rep(i, 1, sz(vi)) {
    int range = vi[i] - vi[i - 1];
    if (range < 2) continue;
    rep(j, 1, has[i] + 1) {
      // if (j > range) {
      //   precal[i][j] = precal[i][j - 1];
      //   continue;
      // }
      ll cur1 = 1; // Cij
      ll cur2 = (ll) range * (range - 1) / 2; // Cirange
      cur2 %= mod;
      ll res = cur1 * cur2 % mod;
      int tar = min(range - 2, j - 2);
      rep(k, 1, tar + 1) {
        cur1 = cur1 * (ll) (j  - k - 1) % mod * inv[k] % mod;
        cur2 = cur2 * (ll) (range - k - 1) % mod * inv[k + 2] % mod;
        res = (res + cur1 * cur2 % mod) % mod;
      }
      precal[i][j] = res;
    }
  }

  // return 0;

  // cout << precal[3][3] << ' ' << precal[3][2] << endl;

  ll ans = 0;
  rep(i, 0, n) {
    int hi = mm[b[i]] + 1;
    int lo = mm[a[i] - 1] + 1;
    dp[i][0] = 1; // ntc
    repd(k, hi, lo) {
      ll ways = (vi[k] - vi[k - 1]) * (i ? dp[i - 1][k - 1] : 1) % mod;
      int tot = 1;
      repd(j, i, 0) {
        if (b[j] < vi[k - 1] + 1 || a[j] > vi[k]) continue;
        tot++;
        // cout << i << ' ' << k << ' ' << vi[k] - vi[k - 1] << ' ' << tot << endl;
        assert(tot <= has[k]);
        ways += (((j ? dp[j - 1][k - 1] : 1) * precal[k][tot]) % mod);
        if (precal[k][tot] == 0) break;
        ways %= mod;
      }
      // cout << i << ' ' << k << ' ' << ways << endl;
      dp[i][k] = ways;
    }
    rep(k, 1, cnt) {
      dp[i][k] = (dp[i][k] + f[k]) % mod;
      // if (i == 2) cout << f[k] << endl;
      f[k] = dp[i][k];
      dp[i][k] = (dp[i][k] + dp[i][k - 1]) % mod;
      ans = dp[i][k];
    }
  }

  // cout << ans << endl;
  cout << ((ans - 1 + mod) % mod) << '\n';
  return 0;
}

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