제출 #23343

#제출 시각아이디문제언어결과실행 시간메모리
23343duongthoi1999Boat (APIO16_boat)C++14
100 / 100
1076 ms10088 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef long long ll; typedef long double ld; typedef pair<ll, int> ii; const int mod = (int) 1e9 + 7; const ll inf = 1LL << 60; const int maxn = (int) 1005; const ld eps = 1e-9; void add(int &a, ll b) { a += (b % mod); while (a >= mod) a -= mod; } ll pw(ll a, int b) { ll res = 1; while (b) { if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } int n, m, a[maxn], b[maxn], sz[maxn]; int f[maxn][maxn], inv[maxn], C[maxn][maxn]; vector<int> p; int main() { //freopen("test.txt", "r", stdin); ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; rep(i, 1, n + 1) { cin >> a[i] >> b[i]; b[i] ++; p.pb(a[i]); p.pb(b[i]); inv[i] = pw(i, mod - 2); } p.pb(0); sort(all(p)); p.resize(unique(all(p)) - p.begin()); rep(i, 1, n + 1) a[i] = lower_bound(all(p), a[i]) - p.begin(); rep(i, 1, n + 1) b[i] = lower_bound(all(p), b[i]) - p.begin(); m = SZ(p) - 2; rep(i, 1, m + 1) sz[i] = p[i + 1] - p[i]; rep(i, 0, m + 1) f[0][i] = 1; rep(i, 1, n + 1) { rep(k, a[i], b[i]) { ll cnt = 1, x = sz[k], y = 1; per(j, 0, i) { if(a[j + 1] <= k && k < b[j + 1]) { cnt = ((cnt * x % mod) * inv[y]) % mod; x ++, y ++; } add(f[i][k], cnt * f[j][k - 1]); } } rep(j, 1, m + 1) add(f[i][j], f[i][j - 1]); } int ans = 0; rep(i, 1, n + 1) add(ans, f[i][m]); cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...