Submission #200123

#	Time	Username	Problem	Language	Result	Execution time	Memory
200123		ansol4328	Boat (APIO16_boat)	C++14	100 / 100	752 ms	6552 KiB

boat

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

int n, m[505][2];
ll inv[505], cnt[1505], dp[505][1505], sel[505];
vector<ll> lst;

ll get_pow(ll x, ll p)
{
    if(p==0) return 1;
    if(p==1) return x;
    ll ret=get_pow(x,p>>1);
    (ret*=ret)%=MOD;
    if(p&1) (ret*=x)%=MOD;
    return ret;
}

void init()
{
    ll fac=1;
    inv[0]=1;
    for(ll i=1 ; i<=n ; i++) (fac*=i)%=MOD;
    inv[n]=get_pow(fac,MOD-2);
    for(ll i=n ; i>=1 ; i--) inv[i-1]=(inv[i]*i)%MOD;
    for(int i=1 ; i<=n ; i++){
        if(m[i][0]==1) dp[i][1]=1;
        (dp[i][1]+=dp[i-1][1])%=MOD;
    }
    dp[1][m[1][0]]=1;
    for(int i=m[1][0]+1 ; i<=m[1][1] ; i++) dp[1][i]=(dp[1][i-1]+(lst[i-1]-lst[i-2]))%MOD;
    for(int i=m[1][1]+1 ; i<=(int)lst.size() ; i++) dp[1][i]=dp[1][i-1];
    for(int i=1 ; i<=(int)lst.size() ; i++){
        for(int j=1 ; j<=n ; j++){
            if(m[j][0]<i && i<=m[j][1]) cnt[i]++;
        }
    }
}

void calc_sel(ll L, ll K)
{
    ll lim=min(L,K);
    if(lim<2) return;
    for(ll i=2 ; i<=K ; i++){
        ll v1=1, v2=(L*(L-1))%MOD;
        ll val1, val2;
        sel[i]=(v2*(inv[2]))%MOD;
        for(ll j=3, x1=i-2, x2=L-2 ; j<=min(lim,i) ; j++, x1--, x2--){
            (v1*=x1)%=MOD;
            (v2*=x2)%=MOD;
            val1=(v1*inv[j-2])%MOD, val2=(v2*inv[j])%MOD;
            sel[i]+=(val1*val2)%MOD;
            sel[i]%=MOD;
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1 ; i<=n ; i++){
        scanf("%d %d",&m[i][0],&m[i][1]);
        lst.push_back((ll)m[i][0]);
        lst.push_back((ll)m[i][0]-1);
        lst.push_back((ll)m[i][1]);
    }
    //contraction
    sort(lst.begin(),lst.end());
    lst.erase(unique(lst.begin(),lst.end()),lst.end());
    for(int i=1 ; i<=n ; i++){
        m[i][0]=lower_bound(lst.begin(),lst.end(),(ll)m[i][0])-lst.begin()+1;
        m[i][1]=lower_bound(lst.begin(),lst.end(),(ll)m[i][1])-lst.begin()+1;
    }
    init();
    //solve
    for(int i=2 ; i<=(int)lst.size() ; i++){
        ll L=lst[i-1]-lst[i-2];
        if(cnt[i]>1) calc_sel(L,cnt[i]);
        for(int j=2 ; j<=n ; j++){
            (dp[j][i]+=dp[j-1][i])%=MOD;
            (dp[j][i]+=dp[j][i-1])%=MOD;
            dp[j][i]=(dp[j][i]-dp[j-1][i-1]+MOD)%MOD;
            if(i<m[j][0] || m[j][1]<i) continue;
            if(i==m[j][0] || L==1){
                (dp[j][i]+=dp[j-1][i-1]+1)%=MOD;
                continue;
            }
            ll val=(dp[j-1][i-1]*L+L)%MOD, c=1;
            for(int k=j-1 ; k>=1 ; k--){
                if(m[k][0]<i && i<=m[k][1]){
                    c++;
                    if(k!=1) (val+=sel[c]*dp[k-1][i-1]+sel[c])%=MOD;
                    else (val+=sel[c])%=MOD;
                }
            }
            (dp[j][i]+=val)%=MOD;
        }
    }
    printf("%lld",dp[n][(int)lst.size()]);
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
boat.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&m[i][0],&m[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42