#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 + 1, vector<int>(n * 2 + 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};
}
vector<int> a, b;
rep(i, 1, signed(v.size()) - 1) a.push_back(v[i] - v[i - 1]);
sort(all(a)), a.resize(unique(all(a)) - a.begin());
int l = 0, cur = 1;
rep(i, 1, 1000000000) {
cur = cur * i % MOD;
if(a[l] == i) {
b.push_back(cur);
l+= (a[l] != a.back());
}
}
rep(i, 1, tot) {
int len = v[i] - v[i - 1];
int id = lower_bound(all(a), len) - a.begin();
rep(j, 1, n) {
int cur = 1;
rep(k, 0, j - 1) cur = cur * (len - k) % MOD;
cur = pow_(b[id], MOD - 2) * cur % MOD;
if(len < j) P[i][j] = 0;
else P[i][j] = b[id] * cur % MOD * inv[j] % MOD;
}
}
rep(i, 1, tot) rep(j, 1, n) {
rep(k, 1, j) {
cal[i][j] += P[i][k] * C[j - 1][k - 1] % MOD;
cal[i][j] %= MOD;
}
}
dp[0][0] = 1;
rep(i, 0, tot) pre[0][i] = 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[k][j - 1] * cal[j][cnt] % MOD;
dp[i][j] %= MOD;
}
}
rep(j, 1, tot) pre[i][j] = (pre[i][j - 1] + dp[i][j]) % MOD;
}
int ans = 0;
rep(i, 1, n) ans = (ans + pre[i][tot]) % 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
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; }
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2088 ms |
18132 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2088 ms |
18132 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2073 ms |
1040 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2088 ms |
18132 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
