#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
typedef long long ll;
const int MOD = (int)1e9 + 7;
int ckadd(int a, int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int ckmul(int a, int b) {
return (a * 1LL * b) % MOD;
}
int bin_pow(int x, int k) {
int r = 1;
while(k) {
if (k & 1) r = ckmul(r, x);
x = ckmul(x, x);
k /= 2;
}
return r;
}
const int N = 505;
int n;
int l[N];
int r[N];
int b[2 * N];
int dp[N][2 * N];
int ways[2 * N][N];
int fact[3 * N];
int inv[3 * N];
void init() {
fact[0] = 1;
for (int i = 1; i < 3 * N; i++) fact[i] = ckmul(fact[i - 1], i);
for (int i = 0; i < 3 * N; i++) inv[i] = bin_pow(fact[i], MOD - 2);
}
int C(int n, int k) {
if (n < k) return 0;
return ckmul(fact[n], ckmul(inv[k], inv[n - k]));
}
int main()
{
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
init();
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &l[i], &r[i]);
r[i]++;
b[2 * i] = l[i];
b[2 * i + 1] = r[i];
}
b[2 * n] = 0;
sort(b, b + 2 * n + 1);
int m = unique(b, b + 2 * n + 1) - b;
for (int i = 0; i < n; i++) {
l[i] = lower_bound(b, b + m, l[i]) - b;
r[i] = lower_bound(b, b + m, r[i]) - b;
}
for (int i = 0; i < m - 1; i++) {
int prod = 1;
int len = b[i + 1] - b[i];
for (int j = 1; j <= n; j++) {
prod = ckmul(prod, len + j - 1);
ways[i][j] = ckmul(prod, inv[j]);
}
}
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) dp[i][j] = ckadd(dp[i][j - 1], dp[i][j]);
for (int v = l[i]; v < r[i]; v++) {
int d = b[v + 1] - b[v], c = 0;
for (int f = i; f >= 0; f--) {
if (v >= l[f] && v < r[f]) c++;
dp[i + 1][v] = ckadd(dp[i + 1][v], ckmul(dp[f][v - 1], ways[v][c]));
}
}
}
for (int j = 1; j < m; j++)
dp[n][j] = ckadd(dp[n][j], dp[n][j - 1]);
int ans = 0;
for (int i = 1; i <= n; i++)
ans = ckadd(ans, dp[i][m - 1]);
printf("%d\n", ans);
return 0;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:95:9: warning: unused variable 'd' [-Wunused-variable]
95 | int d = b[v + 1] - b[v], c = 0;
| ^
boat.cpp:64:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
boat.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d%d", &l[i], &r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
