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>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
const int MAXN = 502;
ll fact[MAXN * 2];
ll rfact[MAXN * 2];
ll pw(ll a, ll m) {
if (!m)
return 1;
a %= MOD;
if (m % 2)
return (a * pw(a, m - 1)) % MOD;
return pw(a * a, m / 2);
}
ll choose[MAXN * 2][MAXN];
ll dp[MAXN * 2][MAXN];
ll ndp[MAXN * 2][MAXN];
ll a[MAXN];
ll b[MAXN];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
rfact[0] = fact[0] = 1;
for (int i = 1; i < 2 * MAXN; ++i) {
fact[i] = (fact[i - 1] * i) % MOD;
rfact[i] = pw(fact[i], MOD - 2);
}
int n;
cin >> n;
vector<ll> cpr = {0};
vector<ll> sz;
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
++b[i];
cpr.push_back(a[i]);
cpr.push_back(b[i]);
}
sort(cpr.begin(), cpr.end());
cpr.resize(unique(cpr.begin(), cpr.end()) - cpr.begin());
int m = cpr.size();
for (int i = 0; i + 1 < m; ++i) {
sz.push_back(cpr[i + 1] - cpr[i]);
for (int k = 0; k <= i; ++k) {
choose[i][k] = 1;
for (int t = sz[i]; t > sz[i] - k; --t) {
choose[i][k] = (choose[i][k] * t) % MOD;
}
choose[i][k] = (choose[i][k] * rfact[k]) % MOD;
}
}
//printf("\n");
for (int i = 0; i < n; ++i) {
a[i] = lower_bound(cpr.begin(), cpr.end(), a[i]) - cpr.begin();
b[i] = lower_bound(cpr.begin(), cpr.end(), b[i]) - cpr.begin();
} for (int i = 0; i < m; ++i)
dp[i][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k <= n; ++k)
ndp[j][k] = 0;
}
for (int j = b[i] - 1; j >= a[i]; --j) {
for (int k = 0; k <= n; ++k) {
if (k)
ndp[j][k] += dp[j][k - 1];
ndp[j][k] %= MOD;
ndp[j + 1][0] += ndp[j][k] * choose[j][k];
ndp[j + 1][0] %= MOD;
}
}
for (int j = 1; j < m; ++j) {
ndp[j][0] += ndp[j - 1][0];
ndp[j][0] %= MOD;
}
for (int j = 0; j < m; ++j) {
for (int k = 0; k <= n; ++k) {
ndp[j][k] += dp[j][k];
ndp[j][k] %= MOD;
}
}
for (int j = 0; j < m; ++j) {
for (int k = 0; k <= n; ++k)
dp[j][k] = ndp[j][k];
}
//printf("---\n");
//for (int j = 0; j < m; ++j) {
//for (int k = 0; k <= n; ++k)
//printf("%Ld ", dp[j][k]);
//printf("\n");
//}
}
cout << dp[m - 1][0] - 1 << endl;
}
# | 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... |