| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 23503 | petrpan | Boat (APIO16_boat) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <map>
using namespace std;
long long n,a[510],b[510],sz,rev[1010],mod=1e9+7,f[1010][1010],al[1010][1010];
vector<int> q;
map<int,long long> cmb[1010];
//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 (((combi(i-1,j)*i)%mod)*rev[j-i+1])%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)
{
//cout << p << " " << cur << "\n";
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()
{
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
for (int i=1;i<1010;i++)
rev[i]=exp(i,mod-2);
sz=q.size()-1;
cout << dp(n,sz);
}