#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 505, mod = 1e9 + 7; // !
int t, L[N], R[N], n, dp[N][N],fact[N], invfact[N], c[N][N], cc[N], p[N];
vector<int> x;
int pwr(int u,int v) {
int ans = 1;
while(v) {
if(v % 2) ans = u * ans % mod;
v /= 2; u = u * u % mod;
}
return ans;
}
int C(int a,int b) {
if(a < b) return 0;
int x = 1;
for(int j = a - b + 1; j <= a; j++) x = x * j % mod;
return x * invfact[b] % mod;
}
int C2(int a,int b) {
if(a < b) return 0;
return fact[a] * invfact[a - b] % mod * invfact[b] % mod;
}
void go(int i,int l, int r) {
for(int j = 0; j <= n; j++) cc[j] = C(r - l + 1, j);
for(int len = 1; len <= n; len++) {
for(int x = 1; x <= len; x++) c[len][x] = (cc[x] * C2(len, x - 1) % mod + c[len][x - 1]) % mod;
}
for(int j = 0; j <= n; j++) {
p[j] = p[j - 1];
if(L[j] <= l && r <= R[j]) p[j]++;
if(!(p[j] - p[j - 1])) continue;
for(int k = 0; k < j; k++) {
dp[j][i] += dp[k][i - 1] * c[p[j] - p[k]][p[j] - p[k]] % mod;
dp[j][i] %= mod;
}
}
for(int j = 0; j <= n; j++) {
dp[j][i] = (dp[j][i - 1] + dp[j][i]) % mod;
}
}
main(){
cin >> n;
fact[0] = invfact[0] = 1;
for(int i = 1; i <= n; i++) {
cin >> L[i] >> R[i];
x.push_back(L[i]);
x.push_back(R[i]);
fact[i] = fact[i - 1] * i % mod;
invfact[i] = invfact[i - 1] * pwr(i, mod - 2) % mod;
}
x.push_back(-1);
sort(x.begin(), x.end());
dp[0][0] = 1;
int cur = 0;
for(int i = 1; i < x.size(); i++) {
if(x[i] != x[i - 1]) go(++cur, x[i], x[i]);
if(i + 1 < x.size() && x[i] + 1 < x[i + 1]) go(++cur, x[i] + 1, x[i + 1] - 1);
}
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = (ans + dp[i][cur]) % mod;
}
cout << ans;
}
Compilation message
boat.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
50 | main(){
| ^~~~
boat.cpp: In function 'int main()':
boat.cpp:66:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i = 1; i < x.size(); i++) {
| ~~^~~~~~~~~~
boat.cpp:68:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | if(i + 1 < x.size() && x[i] + 1 < x[i + 1]) go(++cur, x[i] + 1, x[i + 1] - 1);
| ~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1232 ms |
4300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1232 ms |
4300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1232 ms |
4300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
