| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 404441 | CursedCode | Boat (APIO16_boat) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
const ll MOD=1000000007;
using namespace std;
ll n,k;
ll l[1005],r[1005],dp[1005][1005],val[1005],cnt[1005][1005],c[1005][1005],sum[1005][1005],len[1005],C[1005][1005];
unordered_map<ll,ll>um;
set<ll>s;
lld pw(lld a, lld b){
if(b<=0)return 1;
lld g=pw(a,b/2);
g=(g*g)%mod;
if(b%2)g=(g*a)%mod;
return g;
}
int main(){
cin >> n;
for(ll i=1;i<=n;i++){
cin >> l[i] >> r[i];
s.insert(l[i]);
s.insert(r[i]+1);
um[l[i]] = um[r[i] + 1] = 0;
}
for(auto i=s.begin();i!=s.end();++i){
um[*i]=++k;
val[k]=*i;
if(k>1) len[k-1]=val[k]-val[k-1];
}
for(ll i=0;i<=n;i++){
C[i][0]=1;
for(ll j=1;j<=i;j++){
C[i][j]=C[i][j-1]*(i+1-j);
C[i][j]%=MOD;
C[i][j]*=power(j,MOD-2);
C[i][j]%=MOD;
}
}
for (ll j=0;j<k;j++) c[0][j] = 1;
for (ll j=0;j<k;j++) C[0][j] = 1;
for(ll i=1;i<k;i++){
c[i][0]=1;
for(ll j=1;j<=min(len[i],n);j++){
c[i][j]=c[i][j-1]*(len[i]+1-j);
c[i][j]%=MOD;
c[i][j]*=power(j,MOD-2);
c[i][j]%=MOD;
// cout << i << ' ' << j << ' ' << c[i][j] << '\n';
}
}
for(ll i=1;i<k;i++){
for(ll j=1;j<=min(len[i],n);j++){
ll res=0;
for(ll t=1;t<=j;t++){
res+=(c[i][t]*C[j-1][t-1]);
res%=MOD;
}
sum[i][j]=res;
}
}
for(ll i=1;i<=n;i++){
for(ll j=1;j<k;j++){
if(l[i]<=val[j] && val[j]<=r[i]){
cnt[i][j]=cnt[i-1][j]+1;
}
else cnt[i][j]=cnt[i-1][j];
// cout << i << ' ' << j << ' ' << cnt[i][j] << '\n';
}
}
for(ll i=0;i<=n;i++){dp[i][0]=1;}
for(ll i=0;i<=n;i++){
for(ll j=1;j<k;j++){
dp[i][j]+=dp[i][j-1];
dp[i][j]%=MOD;
for(ll t=0;t<i;t++){
if(l[t+1]<=val[j] && val[j]<=r[t+1]){
ll p=cnt[i][j]-cnt[t][j];
dp[i][j]+=(dp[t][j-1]*sum[j][min(p,len[j])]);
dp[i][j]%=MOD;
}
// if(i==1 && j==2) cout << cnt[i][j] << '\n';
}
// cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
}
}
cout << (dp[n][k-1]-1)%MOD;
}