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>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const int N = 507, mod = 1e9 + 7;
int add(int x, int y) {return (x+y < mod) ? x+y : x+y-mod;}
int mul(int x, int y) {return (ll)x*y%mod;}
int n;
int aa[N], bb[N], a[N], b[N], dp[N][2*N], ch[N][2*N], c[N][2*N], inv[N], cho[N][N];
int Pow(int x, int y) {
int res = 1, pot = x;
while (y) {
if (y % 2) res = mul(res, pot);
pot = mul(pot, pot);
y /= 2;
}
return res;
}
int main () {
FIO;
inv[0] = 1;
for (int i = 1; i < N; i++) inv[i] = Pow(i, mod-2);
for (int i = 0; i < N; i++) {
cho[i][0] = 1;
for (int j = 1; j < i; j++) cho[i][j] = add(cho[i-1][j], cho[i-1][j-1]);
}
cin >> n;
vector <int> v;
map <int, int> saz;
for (int i = 0; i < n; i++) {
cin >> aa[i] >> bb[i]; bb[i]++;
v.pb(aa[i]);
v.pb(bb[i]);
}
sort(all(v)); v.erase(unique(all(v)), v.end());
int siz = v.size()-1;
for (int i = 0; i <= siz; i++) saz[v[i]] = i;
for (int i = 0; i < n; i++) {
a[i] = saz[aa[i]];
b[i] = saz[bb[i]];
}
for (int i = 0; i < siz; i++) {
int x = v[i+1]-v[i];
for (int j = 1; j <= n; j++) {
int pro = 1;
for (int k = x-1+j, l = 1; k >= x; k--, l++) pro = mul(pro, mul(k, inv[l]));
ch[j][i] = pro;
}
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= j; k++) {
c[j][i] = add(c[j][i], mul(ch[k][i], cho[j-1][k-1]));
}
}
}
for (int j = 0; j < siz; j++) {
for (int i = 0; i < n; i++) {
if (j) dp[i][j] = dp[i][j-1];
if (j < a[i] || j >= b[i]) continue;
int cnt = 1;
for (int k = i-1; k >= 0; k--) {
dp[i][j] = add(dp[i][j], mul(c[cnt][j], dp[k][j-1]));
cnt += (j >= a[k] && j < b[k]);
}
dp[i][j] = add(dp[i][j], c[cnt][j]);
}
}
int res = 0;
for (int i = 0; i < n; i++) res = add(res, dp[i][siz-1]);
cout << res;
return 0;
}
# | 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... |