#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
long long n,a[510],b[510],sz,rev[2010],mod=1e9+7,f[2010][2010],al[2010][2010];
vector<int> q;
map<int,long long> cmb[2010];
//fast exponential
long long exp(long long a,long long b)
{
long long ret=1;
while (b)
{
if (b%2)
ret*=a,ret%=mod;
a*=a;
a%=mod;
b/=2;
}
return ret;
}
long long combi(int i,int j)
{
//cout << "C " << i << " " << j << "\n";
if (i>j) return 0;
if (i==0) return 1;
if (cmb[i][j]) return cmb[i][j];
return cmb[i][j]=(((combi(i-1,j)*i)%mod)*exp(j-i+1,mod-2))%mod;
}
//dp result dp(i,j) number of way to send boat
//from schools 1->i such that last num < q[j]
long long dp(int p,int cur)
{
if (p==0) return 1;
if (cur<=1) return 0;
if (al[p][cur]) return f[p][cur];
al[p][cur]=1;
f[p][cur]+=dp(p,cur-1);
f[p][cur]+=(dp(p-1,cur)-dp(p-1,cur-1))+mod;
f[p][cur]%=mod;
if (q[cur-1]>b[p] or q[cur]<=a[p]) return f[p][cur];
for (int i=p;i>=1;i--)
{
int x=q[cur]-q[cur-1];
f[p][cur]+=(dp(i-1,cur-1)*combi(p-i+1,x+p-i+1-1))%mod;
f[p][cur]%=mod;
}
f[p][cur]%=mod;
return f[p][cur];
}
int main()
{
//freopen("input.txt","r",stdin);
cin >> n;
for (int i=1;i<=n;i++)
{
cin >> a[i] >> b[i];
//discretize segments
q.push_back(a[i]);
q.push_back(b[i]+1);
}
q.push_back(0);
sort(q.begin(),q.end());
q.resize(unique(q.begin(),q.end())-q.begin());
//reverse modulo
sz=q.size()-1;
cout << dp(n,sz);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
249 ms |
73104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
249 ms |
73104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1293 ms |
123088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
249 ms |
73104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
