# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
113461 | ansol4328 | Boat (APIO16_boat) | C++11 | 269 ms | 4440 KiB |
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<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
ll n, m[505][2];
ll v[1005], inv[505];
ll dp1[505][1005];
map<ll,ll> cont;
const ll MOD=1e9+7;
ll get_mod(ll x, ll y)
{
if(y==1) return x;
ll ret=get_mod(x,y/2);
(ret*=ret)%=MOD;
if(y%2==1) (ret*=x)%=MOD;
return ret;
}
int main()
{
scanf("%lld",&n);
inv[n]=1;
for(ll i=1 ; i<=n ; i++)
{
scanf("%lld %lld",&m[i][0],&m[i][1]);
cont[m[i][0]]=0;
cont[m[i][1]]=0;
(inv[n]*=i)%=MOD;
}
//contracting
ll cnt=0, contn;
for(auto it=cont.begin() ; it!=cont.end() ; it++)
{
it->second=++cnt;
v[cnt]=it->first;
}
contn=cnt;
for(ll i=1 ; i<=n ; i++)
{
m[i][0]=cont[m[i][0]];
m[i][1]=cont[m[i][1]];
}
//making modular inverse
inv[n]=get_mod(inv[n],MOD-2);
for(ll i=n ; i>1 ; i--) inv[i-1]=(inv[i]*i)%MOD;
//DP
ll res=0;
for(ll i=0 ; i<=contn ; i++) dp1[0][i]=1;
for(ll i=1 ; i<=n ; i++)
{
for(ll j=m[i][0] ; j<m[i][1] ; j++)
{
ll gap=v[j+1]-v[j];
ll k1=gap-1, fac1=gap, c=1, s=0;
for(ll k=i-1 ; k>=0 ; k--) (dp1[i][j]+=(dp1[k][j-1]*gap))%=MOD;
for(ll k=i-1 ; k>=1 ; k--)
{
if(k1<=0) break;
if(m[k][0]<=j && j+1<=m[k][1])
{
c++;
(fac1*=k1)%=MOD;
ll comb=(fac1*inv[c])%MOD;
(s+=comb)%=MOD;
ll val=1;
if(j>1) val=dp1[k-1][j-1];
(val*=s)%=MOD;
(dp1[i][j]+=val)%=MOD;
k1--;
}
}
}
for(ll j=i-1 ; j>=0 ; j--) (dp1[i][m[i][1]]+=dp1[j][m[i][1]-1])%=MOD;
for(ll j=1 ; j<=contn ; j++)
{
(dp1[i][j]+=dp1[i][j-1])%=MOD;
}
(res+=dp1[i][contn])%=MOD;
}
printf("%lld",res);
return 0;
}
Compilation message (stderr)
# | 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... |