This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
namespace solver {
int n, tot;
vector<pii> seg;
vector<int> v, fac, inv;
vector<vector<int>> dp, pre, P, cal, C;
int pow_(int a, int times) {
int ans = 1;
for(; times > 0; times >>= 1, a = a * a % MOD) {
if(times & 1) ans = ans * a % MOD;
}
return ans;
}
void init_(int _n) {
n = _n;
v.clear();
seg.assign(n + 1, {0, 0});
dp.assign(n + 1, vector<int>(n * 2 + 1, 0));
pre.assign(n * 2 + 1, vector<int>(n + 1, 0));
P.assign(n * 2 + 1, vector<int>(n + 1, 0));
C.assign(n + 1, vector<int>(n + 1, 0));
cal.assign(n * 2 + 1, vector<int>(n + 1, 0));
fac.assign(n + 1, 1);
inv.assign(n + 1, 1);
rep(i, 1, n) fac[i] = fac[i - 1] * i % MOD;
inv[n] = pow_(fac[n], MOD - 2);
rrep(i, 1, n - 1) inv[i] = inv[i + 1] * (i + 1) % MOD;
rep(i, 0, n) rep(j, 0, i) {
C[i][j] = fac[i] * inv[j] % MOD * inv[i - j] % MOD;
}
}
void solve() {
sort(all(v));
v.resize(unique(all(v)) - v.begin());
tot = v.size() - 1;
rep(i, 1, n) {
int L = seg[i].x, R = seg[i].y;
L = lower_bound(all(v), L) - v.begin() + 1;
R = lower_bound(all(v), R + 1) - v.begin();
seg[i] = {L, R};
}
int l = 0, cur = 1;
rep(i, 1, tot) {
int len = v[i] - v[i - 1];
rep(j, 1, min(n, len)) {
int L = 1, R = 1;
rep(k, 0, j - 1) L = L * (len - k) % MOD;
rep(k, 1, j) R = R * k % MOD;
P[i][j] = L * pow_(R, MOD - 2) % MOD;
}
}
rep(i, 1, tot) {
vector<int> p = P[i];
rep(j, 1, n) {
rep(k, 1, j) cal[i][j] += p[k] * C[j - 1][k - 1] % MOD;
cal[i][j] %= MOD;
}
}
dp[0][0] = 1;
rep(i, 0, tot) pre[i][0] = 1;
rep(i, 1, n) {
int L = seg[i].x, R = seg[i].y;
rep(j, 1, tot) if(L <= j && j <= R) {
int cnt = 0;
rrep(k, 0, i - 1) {
cnt += (seg[k + 1].x <= j && seg[k + 1].y >= j);
dp[i][j] += pre[j - 1][k] * cal[j][cnt] % MOD;
}
dp[i][j] %= MOD;
}
rep(j, 1, tot) pre[j][i] = (pre[j - 1][i] + dp[i][j]) % MOD;
}
int ans = 0;
rep(i, 1, n) ans = (ans + pre[tot][i]) % MOD;
cout << ans << "\n";
}
};
using namespace solver;
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int n; cin >> n;
init_(n);
rep(i, 1, n) {
cin >> seg[i].x >> seg[i].y;
v.push_back(seg[i].x);
v.push_back(seg[i].y + 1);
}
solve();
return 0;
}
Compilation message (stderr)
boat.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
5 | #pragma loop-opt(on)
|
boat.cpp:20:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
| ^~~~
boat.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
| ^~~~
boat.cpp: In function 'void solver::solve()':
boat.cpp:70:7: warning: unused variable 'l' [-Wunused-variable]
70 | int l = 0, cur = 1;
| ^
boat.cpp:70:14: warning: unused variable 'cur' [-Wunused-variable]
70 | int l = 0, cur = 1;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |