#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
#define sz(x) int(x.size())
const ll mod = 1'000'000'007;
ll mul(ll a, ll b)
{
return (a*b) % mod;
}
ll ad(ll a, ll b)
{
return (a+b) % mod;
}
ll sq(ll a)
{
return mul(a,a);
}
ll pow(ll b, ll e)
{
if(e == 0) return 1;
else if(e % 2 == 1) return mul(b, pow(b, e-1));
else return sq(pow(b, e/2));
}
ll get_inv(ll a)
{
return pow(a, mod-2);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
ll a[1+N], b[1+N];
map<ll, ll> values;
for(int i = 1; i <= N; i++)
{
cin >> a[i] >> b[i];
b[i]++;
values[a[i]] = 0;
values[b[i]] = 0;
}
values[0] = 0;
values[1] = 0;
vll ep;
for(auto& z : values) ep.push_back(z.first);
int ct = sz(ep) - 1;
vll blocksize(1+ct);
blocksize[0] = 0;
for(int i = 1; i <= ct; i++)
blocksize[i] = ep[i] - ep[i-1];
int x[1+N], y[1+N];
// for(int i = 0; i <= ct; i++) cerr << i << " : " << ep[i] << ' ' << blocksize[i] << '\n';
for(int i = 1; i <= N; i++)
{
x[i] = 0;
int lo = 1, hi = ct;
while(lo != hi)
{
int mid = (lo+hi)/2 + 1;
if(ep[mid] <= a[i])
lo = mid;
else
hi = mid-1;
}
x[i] = lo + 1;
y[i] = 0;
lo = 1, hi = ct;
while(lo != hi)
{
int mid = (lo+hi)/2+1;
if(ep[mid] <= b[i])
lo = mid;
else
hi = mid-1;
}
y[i] = lo;
}
ll*** DP = new ll**[1+N];
for(int i = 0; i <= N; i++)
{
DP[i] = new ll*[1+ct];
for(int j = 0; j <= ct; j++)
{
DP[i][j] = new ll[1+N];
for(int k = 0; k <= N; k++) DP[i][j][k] = 0;
}
}
ll inv[1+N];
for(int i = 1; i <= N; i++) inv[i] = get_inv(i);
vvll DPsum(1+N, vll(1+ct, 0));
// cerr << "!" << x[1] << ' ' << y[1] << '\n';
for(int j = x[1]; j <= y[1]; j++)
{
DPsum[1][j] = ad(DPsum[1][j], blocksize[j]);
DP[1][j][1] = blocksize[j];
}
for(int i = 2; i <= N; i++)
{
for(int j = 1; j <= ct; j++)
{
for(int k = 1; k <= i; k++)
{
DP[i][j][k] = DP[i-1][j][k];
if(x[i] <= j && j <= y[i])
{
if(j == 1 && k == 1)
{
;//DP[i][1][1] = blocksize[j] *
}
else if(j == 1)
{
;
}
else if(k == 1)
{
ll curr = 1;
for(int j2 = 1; j2 < j; j2++)
curr = ad(curr, DPsum[i-1][j2]);
DP[i][j][1] = ad(DP[i][j][1], mul(curr, blocksize[j]));
}
else
{
if(k <= blocksize[j])
DP[i][j][k] = ad(DP[i][j][k], mul(DP[i-1][j][k-1], mul(blocksize[j] - k + 1, inv[k])));
}
}
DPsum[i][j] = ad(DPsum[i][j], DP[i][j][k]);
}
}
}
ll res = 0;
for(int j = 1; j <= ct; j++)
res = ad(res, DPsum[N][j]);
cout << res << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
221 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
221 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
16836 KB |
Output is correct |
2 |
Correct |
19 ms |
16844 KB |
Output is correct |
3 |
Correct |
19 ms |
16928 KB |
Output is correct |
4 |
Correct |
19 ms |
16844 KB |
Output is correct |
5 |
Correct |
19 ms |
16940 KB |
Output is correct |
6 |
Correct |
20 ms |
16844 KB |
Output is correct |
7 |
Correct |
23 ms |
17052 KB |
Output is correct |
8 |
Correct |
28 ms |
16864 KB |
Output is correct |
9 |
Correct |
22 ms |
16872 KB |
Output is correct |
10 |
Correct |
23 ms |
16844 KB |
Output is correct |
11 |
Correct |
19 ms |
16908 KB |
Output is correct |
12 |
Correct |
19 ms |
16948 KB |
Output is correct |
13 |
Correct |
18 ms |
16916 KB |
Output is correct |
14 |
Correct |
18 ms |
16832 KB |
Output is correct |
15 |
Correct |
19 ms |
16844 KB |
Output is correct |
16 |
Correct |
10 ms |
9932 KB |
Output is correct |
17 |
Correct |
10 ms |
9676 KB |
Output is correct |
18 |
Correct |
10 ms |
9868 KB |
Output is correct |
19 |
Correct |
10 ms |
9932 KB |
Output is correct |
20 |
Correct |
9 ms |
9544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
221 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |