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 <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int inverse(int x) {
int base = x, power = MOD - 2;
int result = 1;
while (power > 0) {
if (power & 1) {
result = 1LL * result * base % MOD;
}
base = 1LL * base * base % MOD;
power /= 2;
}
return result;
}
void norm(int& X) {
X -= X >= MOD ? MOD : 0;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N;
cin >> N;
vector<int> A(N), B(N);
vector<int> points;
for (int i = 0; i < N; i++) {
cin >> A[i] >> B[i];
points.push_back(A[i]);
if (A[i] < B[i]) {
points.push_back(A[i] + 1);
points.push_back(B[i] - 1);
}
points.push_back(B[i]);
}
sort(points.begin(), points.end());
points.resize(unique(points.begin(), points.end()) - points.begin());
int M = (int)points.size();
vector<int> weight(M);
vector<vector<int>> choose_weight(M, vector<int>(N + 1));
for (int i = 0; i < M; i++) {
weight[i] = (i == M - 1 ? 1 : points[i + 1] - points[i]);
choose_weight[i][0] = 1;
for (int j = 0; j < weight[i] && j < N; j++) {
int coefficient = 1LL * (weight[i] - j) * inverse(j + 1) % MOD;
choose_weight[i][j + 1] = 1LL * choose_weight[i][j] * coefficient % MOD;
}
}
vector<vector<int>> ways(M, vector<int>(N + 1));
vector<int> pref(M + 1);
for (int i = 0; i < M; i++) {
ways[i][0] = 1;
}
for (int i = 0; i < N; i++) {
vector<vector<int>> new_ways(M, vector<int>(N + 1));
for (int j = 0; j < M; j++) {
norm(ways[j][0] += pref[j]);
for (int k = 0; k < N; k++) {
norm(new_ways[j][k] += ways[j][k]);
if (A[i] <= points[j] && points[j] <= B[i]) {
norm(new_ways[j][k + 1] += ways[j][k]);
}
}
}
for (int j = 0; j < M; j++) {
pref[j + 1] = pref[j];
for (int k = 1; k <= N && k <= weight[j]; k++) {
pref[j + 1] = (pref[j + 1] + 1LL * new_ways[j][k] * choose_weight[j][k]) % MOD;
}
}
ways = new_ways;
}
cout << pref[M] << "\n";
}
# | 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... |