#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define int ll
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 500 + 10;
const ll MOD = 1e9 + 7;
void mkey(int& a) {
a %= MOD;
}
inline ll poww(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % MOD;
b >>= 1;
a = a * a % MOD;
}
return ans;
}
int n, L[MAXN], R[MAXN], C[MAXN][MAXN], PC[MAXN][MAXN], dp[MAXN][MAXN * 2],
ps[2 * MAXN][MAXN], inv[MAXN];
vector<int> vec;
inline int ind(int x) {
return lower_bound(all(vec), x) - vec.begin();
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> L[i] >> R[i];
vec.push_back(L[i]);
vec.push_back(R[i]);
inv[i] = poww(i, MOD - 2);
}
vec.push_back(-1);
sort(all(vec));
vec.resize(unique(all(vec)) - vec.begin());
for (int j = 1; j < int(vec.size()); j++) {
for (int i = 1; i <= n; i++)
ps[j][i] = ps[j][i - 1] + (vec[j - 1] < L[i] && R[i] <= vec[j]);
PC[j][0] = C[j][0] = 1;
int sz = vec[j] - vec[j - 1];
for (int i = 1; i <= min(sz, n); i++) {
C[j][i] = 1ll * C[j][i - 1] * (sz - i + 1) % MOD * inv[i] % MOD;
mkey(PC[j][i] = PC[j][i - 1] + C[j][i]);
}
}
fill(dp[0], dp[0] + MAXN, 1);
int ans = 0;
for (int i = 1; i <= n; i++) {
int l = ind(L[i]), r = ind(R[i]);
for (int j = 1; j < int(vec.size()); j++) {
int sz = vec[j] - vec[j - 1];
dp[i][j] = dp[i][j - 1];
if (j >= l && j <= r) {
for (int k = 0; k < i; k++) {
dp[i][j] = (dp[i][j] + 1ll * PC[j][min(sz, ps[j][i - 1] - ps[j][k])] * dp[k][j - 1]) % MOD;
}
}
}
mkey(ans += dp[i][int(vec.size()) - 1]);
}
cout << ans << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
10324 KB |
Output is correct |
2 |
Correct |
11 ms |
10324 KB |
Output is correct |
3 |
Correct |
13 ms |
10300 KB |
Output is correct |
4 |
Correct |
12 ms |
10356 KB |
Output is correct |
5 |
Correct |
12 ms |
10324 KB |
Output is correct |
6 |
Correct |
11 ms |
10220 KB |
Output is correct |
7 |
Correct |
10 ms |
10324 KB |
Output is correct |
8 |
Correct |
10 ms |
10324 KB |
Output is correct |
9 |
Correct |
11 ms |
10324 KB |
Output is correct |
10 |
Correct |
11 ms |
10324 KB |
Output is correct |
11 |
Correct |
10 ms |
10324 KB |
Output is correct |
12 |
Correct |
10 ms |
10260 KB |
Output is correct |
13 |
Correct |
10 ms |
10324 KB |
Output is correct |
14 |
Correct |
10 ms |
10324 KB |
Output is correct |
15 |
Correct |
11 ms |
10232 KB |
Output is correct |
16 |
Incorrect |
4 ms |
3796 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
10324 KB |
Output is correct |
2 |
Correct |
11 ms |
10324 KB |
Output is correct |
3 |
Correct |
13 ms |
10300 KB |
Output is correct |
4 |
Correct |
12 ms |
10356 KB |
Output is correct |
5 |
Correct |
12 ms |
10324 KB |
Output is correct |
6 |
Correct |
11 ms |
10220 KB |
Output is correct |
7 |
Correct |
10 ms |
10324 KB |
Output is correct |
8 |
Correct |
10 ms |
10324 KB |
Output is correct |
9 |
Correct |
11 ms |
10324 KB |
Output is correct |
10 |
Correct |
11 ms |
10324 KB |
Output is correct |
11 |
Correct |
10 ms |
10324 KB |
Output is correct |
12 |
Correct |
10 ms |
10260 KB |
Output is correct |
13 |
Correct |
10 ms |
10324 KB |
Output is correct |
14 |
Correct |
10 ms |
10324 KB |
Output is correct |
15 |
Correct |
11 ms |
10232 KB |
Output is correct |
16 |
Incorrect |
4 ms |
3796 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
3284 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
10324 KB |
Output is correct |
2 |
Correct |
11 ms |
10324 KB |
Output is correct |
3 |
Correct |
13 ms |
10300 KB |
Output is correct |
4 |
Correct |
12 ms |
10356 KB |
Output is correct |
5 |
Correct |
12 ms |
10324 KB |
Output is correct |
6 |
Correct |
11 ms |
10220 KB |
Output is correct |
7 |
Correct |
10 ms |
10324 KB |
Output is correct |
8 |
Correct |
10 ms |
10324 KB |
Output is correct |
9 |
Correct |
11 ms |
10324 KB |
Output is correct |
10 |
Correct |
11 ms |
10324 KB |
Output is correct |
11 |
Correct |
10 ms |
10324 KB |
Output is correct |
12 |
Correct |
10 ms |
10260 KB |
Output is correct |
13 |
Correct |
10 ms |
10324 KB |
Output is correct |
14 |
Correct |
10 ms |
10324 KB |
Output is correct |
15 |
Correct |
11 ms |
10232 KB |
Output is correct |
16 |
Incorrect |
4 ms |
3796 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |