#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int put(int a, int exp)
{
if(exp==0)
return 1;
if(exp%2==0)
return put(a*a%MOD,exp/2);
else
return put(a*a%MOD,exp/2)*a%MOD;
}
int n,cate;
int le[505],ri[505];
map<int,int> mp,nrm;
int invnrm[1005],nr[1005];
int dp[1005][505];
int fact[1005],invf[1005];
int comb(int x, int y)
{
if(x<y)
return 0;
return fact[x]*invf[y]%MOD*invf[x-y]%MOD;
}
signed main()
{
fact[0]=1;
for(int i=1;i<=1000;i++)
fact[i]=fact[i-1]*i%MOD;
invf[1000]=put(fact[1000],MOD-2);
for(int i=999;i>=0;i--)
invf[i]=invf[i+1]*(i+1)%MOD;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>le[i]>>ri[i];
mp[le[i]]++;
mp[ri[i]]++;
}
for(auto it:mp)
{
if(it.second)
{
nrm[it.first]=++cate;
invnrm[cate]=it.first;
}
}
for(int i=1;i<=cate;i++)
{
nr[i] = invnrm[i]-invnrm[i-1];
}
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
le[i] = nrm[le[i]];
ri[i] = nrm[ri[i]];
int copnr = nr[le[i]];
nr[le[i]]=1;
for(int ult=ri[i];ult>=le[i];ult--)
{
for(int cnt=min(i,nr[ult]);cnt>1;cnt--)
{
//dp[ult][cnt]= (dp[ult][cnt] + dp[ult][cnt-1] * (nr[ult]-cnt+1)%MOD * put(cnt,MOD-2))%MOD;
dp[ult][cnt]= (dp[ult][cnt] + dp[ult][cnt-1] * put(comb(nr[ult],cnt-1),MOD-2)%MOD * comb(nr[ult],cnt))%MOD;
}
for(int j=0;j<ult;j++)
for(int orice=0;orice<i;orice++)
dp[ult][1] = (dp[ult][1] + dp[j][orice]*nr[ult])%MOD;
}
nr[le[i]]=copnr;
}
int rez=0;
for(int ult=1;ult<=cate;ult++)
for(int cnt=1;cnt<=n;cnt++)
rez = (rez + dp[ult][cnt])%MOD;
cout<<rez;
return 0;
}
/**
impartim intervalul [1,1e9] in intervale relevante, o sa avem maxim 1000 intervale relevante
dp[i][ult][cnt] = in cate moduri pot primele i scoli barci, a.i. ultimele cnt numere sa fie aflate in intervalul ult
daca i poate sa aleaga intervalul ult
dp[i][ult][1] = dp[i-1][ult][1] + sum(dp[i-1][orice<ult][orice])*nr[ult]
pt cnt>=2 dp[i][ult][cnt] = dp[i-1][ult][cnt] + dp[i-1][ult][cnt-1] / comb(nr[ult],cnt-1) * comb(nr[ult],cnt)
pt cnt>=2 dp[i][ult][cnt] = dp[i-1][ult][cnt] + dp[i-1][ult][cnt-1] * (nr[ult]-cnt+1) / cnt
(nr[ult]-cnt+1) / cnt
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
132 ms |
2384 KB |
Output is correct |
2 |
Correct |
130 ms |
2404 KB |
Output is correct |
3 |
Correct |
128 ms |
2476 KB |
Output is correct |
4 |
Correct |
128 ms |
2388 KB |
Output is correct |
5 |
Correct |
134 ms |
2384 KB |
Output is correct |
6 |
Correct |
166 ms |
2304 KB |
Output is correct |
7 |
Correct |
169 ms |
2400 KB |
Output is correct |
8 |
Correct |
171 ms |
2360 KB |
Output is correct |
9 |
Correct |
171 ms |
2260 KB |
Output is correct |
10 |
Correct |
170 ms |
2248 KB |
Output is correct |
11 |
Correct |
171 ms |
2392 KB |
Output is correct |
12 |
Correct |
167 ms |
2332 KB |
Output is correct |
13 |
Correct |
170 ms |
2416 KB |
Output is correct |
14 |
Correct |
169 ms |
2388 KB |
Output is correct |
15 |
Correct |
172 ms |
2460 KB |
Output is correct |
16 |
Correct |
19 ms |
604 KB |
Output is correct |
17 |
Correct |
19 ms |
860 KB |
Output is correct |
18 |
Correct |
18 ms |
828 KB |
Output is correct |
19 |
Correct |
18 ms |
864 KB |
Output is correct |
20 |
Correct |
19 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
132 ms |
2384 KB |
Output is correct |
2 |
Correct |
130 ms |
2404 KB |
Output is correct |
3 |
Correct |
128 ms |
2476 KB |
Output is correct |
4 |
Correct |
128 ms |
2388 KB |
Output is correct |
5 |
Correct |
134 ms |
2384 KB |
Output is correct |
6 |
Correct |
166 ms |
2304 KB |
Output is correct |
7 |
Correct |
169 ms |
2400 KB |
Output is correct |
8 |
Correct |
171 ms |
2360 KB |
Output is correct |
9 |
Correct |
171 ms |
2260 KB |
Output is correct |
10 |
Correct |
170 ms |
2248 KB |
Output is correct |
11 |
Correct |
171 ms |
2392 KB |
Output is correct |
12 |
Correct |
167 ms |
2332 KB |
Output is correct |
13 |
Correct |
170 ms |
2416 KB |
Output is correct |
14 |
Correct |
169 ms |
2388 KB |
Output is correct |
15 |
Correct |
172 ms |
2460 KB |
Output is correct |
16 |
Correct |
19 ms |
604 KB |
Output is correct |
17 |
Correct |
19 ms |
860 KB |
Output is correct |
18 |
Correct |
18 ms |
828 KB |
Output is correct |
19 |
Correct |
18 ms |
864 KB |
Output is correct |
20 |
Correct |
19 ms |
604 KB |
Output is correct |
21 |
Execution timed out |
2074 ms |
4108 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
2 ms |
1884 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
132 ms |
2384 KB |
Output is correct |
2 |
Correct |
130 ms |
2404 KB |
Output is correct |
3 |
Correct |
128 ms |
2476 KB |
Output is correct |
4 |
Correct |
128 ms |
2388 KB |
Output is correct |
5 |
Correct |
134 ms |
2384 KB |
Output is correct |
6 |
Correct |
166 ms |
2304 KB |
Output is correct |
7 |
Correct |
169 ms |
2400 KB |
Output is correct |
8 |
Correct |
171 ms |
2360 KB |
Output is correct |
9 |
Correct |
171 ms |
2260 KB |
Output is correct |
10 |
Correct |
170 ms |
2248 KB |
Output is correct |
11 |
Correct |
171 ms |
2392 KB |
Output is correct |
12 |
Correct |
167 ms |
2332 KB |
Output is correct |
13 |
Correct |
170 ms |
2416 KB |
Output is correct |
14 |
Correct |
169 ms |
2388 KB |
Output is correct |
15 |
Correct |
172 ms |
2460 KB |
Output is correct |
16 |
Correct |
19 ms |
604 KB |
Output is correct |
17 |
Correct |
19 ms |
860 KB |
Output is correct |
18 |
Correct |
18 ms |
828 KB |
Output is correct |
19 |
Correct |
18 ms |
864 KB |
Output is correct |
20 |
Correct |
19 ms |
604 KB |
Output is correct |
21 |
Execution timed out |
2074 ms |
4108 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |