제출 #1347096

#제출 시각아이디문제언어결과실행 시간메모리
1347096tung04885Boat (APIO16_boat)C++20
100 / 100
377 ms5688 KiB
#include <bits/stdc++.h>
using namespace std;
#define MAX 666
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define __buitin_popcount __builtin_popcountll
#define BIT(x,i) (((x)>>(i))&1ll)
#define MASK(i) (1ll<<(i))

template<class X,class Y> bool maximize(X &x,Y y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}

template<class X,class Y> bool minimize(X &x,Y y)
{
    if(y<x)
    {
        x=y;
        return 1;
    }
    return 0;
}

const int inf=1e9+412009;
const ll INF=2e18+412009;
const int mod=1e9+7;

void add(int &x,int y)
{
    x+=y;
    if(x>=mod) x-=mod;
}

int lt(int a,int b)
{
    if(b==0) return 1;
    int res=lt(a,b>>1);
    res=(1ll*res*res)%mod;
    if(b&1) res=(1ll*res*a)%mod;
    return res;
}

int n;
int a[MAX],b[MAX];
int dp[2*MAX][MAX]={},pre[2*MAX][MAX]={};
int f[2*MAX]={};

void nhap()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
}

vector<int> zip;
int valsz;
int ndao[MAX];
int pos_a[MAX],pos_b[MAX];
int realval[2*MAX]={};

void ZIPPING()
{
    for(int i=1;i<=n;i++)
    {
        zip.push_back(a[i]-1);
        zip.push_back(b[i]);
    }

    sort(all(zip));

    zip.erase(unique(all(zip)),zip.end());

    for(int i=1;i<=n;i++)
    {
        pos_a[i]=upper_bound(all(zip),a[i]-1)-zip.begin();
        pos_b[i]=upper_bound(all(zip),b[i])-zip.begin();

        realval[pos_a[i]]=a[i]-1;
        realval[pos_b[i]]=b[i];
    }

    valsz=zip.size();
}

void solve()
{
    ZIPPING();

    for(int i=0;i<=n;i++) ndao[i]=lt(i,mod-2);

//    for(int i=1;i<=valsz;i++) cout<<realval[i]<<' ';
//    cout<<'\n';

    dp[0][0]=1;
    pre[0][0]=1;

    for(int i=0;i<=valsz;i++) f[i]=1;

    for(int i=1;i<=n;i++)
    {
        for(int j=pos_a[i]+1;j<=pos_b[i];j++)
        {
            int len=realval[j]-realval[j-1];

            add(dp[j][1],(1ll*len*f[j-1])%mod);

            for(int k=2;k<=i;k++)
            {
                add(dp[j][k],(1ll*pre[j][k-1]*(1ll*(len-k+1)*ndao[k]%mod)+mod)%mod);
            }
        }

        for(int j=0;j<=valsz;j++)
            for(int k=0;k<=i;k++) pre[j][k]=dp[j][k];

        for(int j=1;j<=valsz;j++)
        {
            f[j]=f[j-1];
            for(int k=0;k<=n;k++) add(f[j],dp[j][k]);
        }

//        for(int j=pos_a[i]+1;j<=pos_b[i];j++)
//        {
//            for(int k=1;k<=i;k++) cout<<dp[j][k]<<' ';
//            cout<<'\n';
//        }
    }

    cout<<f[valsz]-1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    nhap();
    solve();

    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...