This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define x first
#define y second
#define pd pair<double,double>
const int siz = 502;
ll a[siz], b[siz];
ll ch[siz][siz];
ll invfac[siz];
ll inv[siz];
const int mod = 1e9 + 7;
ll powi(ll a, ll b) {
if (b == 0)return 1;
ll ans = powi(a, b / 2);
ans = (ans * ans) % mod;
if (b % 2)ans = (ans * a) % mod;
return ans;
}
int main()
{
int n; cin >> n;
for (int i = 0; i < n; i++)cin >> a[i] >> b[i];
vll v; for (int i = 0; i < n; i++) { v.push_back(a[i]); v.push_back(b[i]); }
sort(v.begin(), v.end());
v.push_back(v.back() + 1);
for (int i = 0; i < siz; i++)inv[i] = powi(i, mod - 2);
invfac[0] = 1;
for (int i = 1; i < siz; i++)invfac[i] = (inv[i] * invfac[i - 1])%mod;
for (int i = 0; i < siz; i++) {
for (int j = 0; j <= i; j++) {
ch[i][j] = (invfac[j] * invfac[i - j]) % mod;
ch[i][j] = (ch[i][j] * powi(invfac[i], mod - 2)) % mod;
}
}
vll dp(n);
for (int i = 0; i < v.size()-1; i++) {
ll N = v[i+1]-v[i];
if (N <= 0)continue;
vll nc(siz);
nc[0] = 1;
for (int j = 1; j < siz; j++) {
nc[j] = ((N - j + 1) * nc[j - 1]) % mod;
nc[j] = (nc[j] * inv[j]) % mod;
}
vll form(siz);
for (int j = 0; j+2 < siz; j++) {
for (int f = 0; f <= j; f++) {
form[j] += nc[f + 2] * ch[j][f];
form[j] %= mod;
}
}
vll dpt=dp;
ll sum = 0;
for (int j = 0; j < n; j++) {
if (a[j] <= v[i] && b[j] >= v[i + 1] - 1) {
int bet = 0;
dpt[j] += (sum + 1) * N;
dpt[j] %= mod;
for (int f = j + 1; f < n; f++) {
if (a[f] <= v[i] && b[f] >= v[i + 1] - 1) {
dpt[f] += (sum + 1) * form[bet];
dpt[f] %= mod;
bet++;
}
}
}
sum += dp[j];
sum %= mod;
}
dp = dpt;
}
ll ans = 0; for (int i = 0; i < n; i++)ans += dp[i];
ans %= mod;
cout << ans;
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
Compilation message (stderr)
boat.cpp: In function 'int main()':
boat.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i = 0; i < v.size()-1; i++) {
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |