//Pantyhose(black) + glasses = infinity
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "boat"
const int MAX_N = 502;
const int MOD = 1000000007;
int n, l[MAX_N], r[MAX_N];
vector<pair<int, int> > seg;
int64_t inv[MAX_N], inv_fact[MAX_N], f[MAX_N][MAX_N], ps[MAX_N][MAX_N], P[MAX_N][MAX_N];
void read_input() {
cin >> n;
for (int i=1; i<=n; ++i)
cin >> l[i] >> r[i];
}
void init() {
vector<int> x;
for (int i=1; i<=n; ++i) {
x.push_back(l[i]);
x.push_back(r[i]+1);
}
sort(x.begin(), x.end());
x.resize(unique(x.begin(), x.end()) - x.begin());
seg.push_back({0, 0});
for (int i=0; i+1<x.size(); ++i) {
seg.push_back({x[i], x[i+1]-1});
// cerr << seg.back().first << ' ' << seg.back().second << '\n';
}
inv[1] = 1;
inv_fact[0] = inv_fact[1] = 1;
for (int i=2; i<=n; ++i) {
inv[i] = MOD - MOD/i*inv[MOD%i]%MOD;
inv_fact[i] = inv_fact[i-1] * inv[i] % MOD;
}
// debug(inv[2]*2%MOD);
}
int64_t C(int n, int k) {
if (n<0 || n<k)
return 0;
int64_t res = 1;
for (int i=n-k+1; i<=n; ++i)
res = res * i % MOD;
return res * inv_fact[k] % MOD;
}
bool contain(int u, int v, int l, int r) {
return (u<=l && r<=v);
}
void dp() {
for (int i=1; i<seg.size(); ++i) {
int l = seg[i].second - seg[i].first + 1;
for (int k=2; k<=n; ++k) {
for (int j=2; j<=k; ++j)
P[i][k] = (P[i][k] + C(l, j) * C(k-2, j-2)) % MOD;
}
}
// debug(P[1][1]);
for (int i=0; i<seg.size(); ++i)
f[0][i] = ps[0][i] = 1;
int64_t res = 0;
for (int i=1; i<=n; ++i) {
for (int j=1; j<seg.size(); ++j) {
f[i][j] = f[i][j-1];
if (!contain(l[i], r[i], seg[j].first, seg[j].second))
continue;
f[i][j] = (f[i][j] + ps[i-1][j-1] * (seg[j].second-seg[j].first+1)) % MOD;
// if (i==3 && j==1)
// debug(f[i][j]);
for (int k=i-1; k>=1; --k) {
if (!contain(l[k], r[k], seg[j].first, seg[j].second))
break;
// if (i==3 && j==1 && k==1)
// debug(tmp);
f[i][j] = (f[i][j] + ps[k-1][j-1] * P[j][i-k+1]) % MOD;
}
}
for (int j=0; j<seg.size(); ++j)
ps[i][j] = (ps[i-1][j] + f[i][j]) % MOD;
}
// debug(f[3][1]);
cout << (ps[n][seg.size()-1] - 1 + MOD) % MOD;
}
int main() {
#ifdef GLASSES_GIRL
freopen(FILE_NAME".in", "r", stdin);
freopen(FILE_NAME".out", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
read_input();
init();
dp();
}
Compilation message
boat.cpp: In function 'void init()':
boat.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i+1<x.size(); ++i) {
~~~^~~~~~~~~
boat.cpp: In function 'void dp()':
boat.cpp:69:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1; i<seg.size(); ++i) {
~^~~~~~~~~~~
boat.cpp:78:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<seg.size(); ++i)
~^~~~~~~~~~~
boat.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=1; j<seg.size(); ++j) {
~^~~~~~~~~~~
boat.cpp:103:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<seg.size(); ++j)
~^~~~~~~~~~~
boat.cpp:81:10: warning: unused variable 'res' [-Wunused-variable]
int64_t res = 0;
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2070 ms |
632 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2070 ms |
632 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
336 ms |
2016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2070 ms |
632 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
