#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 5e2 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 320;
int n, m;
pii a[N];
int dp[N][N * 2], f[N][N * 2], com[N * 2][N], combi[N][N];
inline void add (int &a, int b) { a = a + b; if (a >= Mod) a = a - Mod; }
ll power (int n, int m) {
if (m == 0) return 1;
ll t = power (n, m >> 1);
(t *= t) %= Mod;
if (m & 1) (t *= n) %= Mod;
return t;
}
bool cover (pii A, pii B) {
return A.fs <= B.fs && A.se >= B.se;
}
void solution () {
cin >> n;
vector<pii> vec, seg = {MP(0, 0)};
rep (i, 1, n) {
cin >> a[i].fs >> a[i].se;
vec.pb({a[i].fs, 0}), vec.pb({a[i].se, 1});
}
sort (ALL(vec));
vec.resize(unique(ALL(vec)) - vec.begin());
rep (i, 0, SZ(vec) - 2) {
if (vec[i].se == vec[i + 1].se) {
if (vec[i].se == 1) seg.pb({vec[i].fs + 1, vec[i + 1].fs});
else seg.pb({vec[i].fs, vec[i + 1].fs - 1});
}
else {
if (vec[i].se == 0) seg.pb({vec[i].fs, vec[i + 1].fs});
else seg.pb({vec[i].fs + 1, vec[i +1 ].fs - 1});
}
}
m = SZ(seg) - 1;
rep (i, 0, m) {
int Len = seg[i].se - seg[i].fs + 1;
com[i][0] = 1;
rep (j, 1, n + 1) {
if (j > Len) com[i][j] = 0;
else com[i][j] = 1LL * com[i][j - 1] * (Len - j + 1) % Mod * power (j, Mod - 2) % Mod;
}
// cout << seg[i].fs <<","<<seg[i].se<<"\n";
}
rep (i, 0, n) {
rep (j, 0, i) {
if (j == i || j == 0) combi[i][j] = 1;
else combi[i][j] = (combi[i - 1][j - 1] + combi[i - 1][j]) % Mod;
}
}
rep (i, 0, n) {
rep (j, 0, m) {
rep (k, 0, i) {
add(f[i][j], 1LL * combi[i][k] * com[j][k + 1] % Mod);
}
}
}
rep (j, 0, m) dp[0][j] = 1;
rep (i, 1, n) {
dp[i][0] = 1;
rep (j, 1, m) {
dp[i][j] = dp[i][j - 1];
int num = 0;
reb (k, i, 1) {
if (cover(a[k], seg[j])) {
add(dp[i][j], 1LL * dp[k - 1][j - 1] * f[num][j] % Mod);
++num;
}
}
// cout << i <<" "<<seg[j].fs<<","<<seg[j].se<<": "<<dp[i][j] <<"\n";
}
}
cout << (dp[n][m] - 1 + Mod) % Mod <<"\n";
}
#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
file("c");
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
no bug challenge +4
mình có muốn dùng mảng này không?
4 5
1 3
4 1
1 2
3 2
2 1
return->break
*/
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:107:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | #define file(name) freopen(name".inp","r",stdin); \
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
boat.cpp:110:5: note: in expansion of macro 'file'
110 | file("c");
| ^~~~
boat.cpp:108:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:110:5: note: in expansion of macro 'file'
110 | file("c");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
