Submission #1323274

#TimeUsernameProblemLanguageResultExecution timeMemory
1323274warrennBoat (APIO16_boat)C++20
0 / 100
86 ms2616 KiB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#define int long long
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back

const int mod=1e9+7;
int dp[2][502][502];
int pref[502];

int pang(int a,int b){
    if(b==0)return 1;
    int tmp=pang(a,b/2);
    if(b%2==0)return (tmp*tmp)%mod;
    else return (((tmp*tmp)%mod)*a)%mod;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n; cin>>n;
    int l[n+1],r[n+1];
    vector<int>comp;

    for(int q=1;q<=n;q++){
        cin>>l[q]>>r[q];
        comp.pb(l[q]); comp.pb(r[q]+1);
    }
    comp.push_back(0);

    sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());
    int sz=comp.size();

    for(int q=0;q<=sz;q++)pref[q]=1;

    for(int q=1;q<=n;q++){
        int cur=q%2,prv=1-cur;
        int posl=lower_bound(comp.begin(),comp.end(),l[q])-comp.begin();
        int posr=lower_bound(comp.begin(),comp.end(),r[q]+1)-comp.begin()-1;

        for(int q=1;q<=sz;q++){
            for(int sama=1;sama<=q;sama++){
                dp[cur][q][sama]=dp[prv][q][sama];
            }
        }

        for(int w=posl;w<=posr;w++){
            int brp=comp[w+1]-comp[w];
            dp[cur][w][1]+=(pref[w-1]*brp)%mod;
            dp[cur][w][1]%=mod;

            for(int sama=2;sama<=q;sama++){
                int tot=(dp[prv][w][sama-1]*((pang(sama,mod-2)*(brp-sama+1))%mod))%mod;
                dp[cur][w][sama]+=tot;
                dp[cur][w][sama]%=mod;
            }
        }

        for(int w=1;w<=sz;w++){
            pref[w]=pref[w-1];
            for(int sama=1;sama<=q;sama++){
                pref[w]=(pref[w]+dp[cur][w][sama])%mod;
            }
        }

        for(int w=1;w<=sz;w++){
            for(int sama=1;sama<=q;sama++){
                dp[prv][w][sama]=0;
            }
        }

        // if(cur==1){
        //    // cout<<dp[1][1][1]<<"K"<<dp[1][2][1]<<endl;
        //     for(int w=1;w<=sz;w++){
        //         cout<<pref[w]<<" ";
        //     }
        //     cout<<endl;
        // }
    }

    int ans=0;
    for(int w=1;w<=sz;w++){
        for(int sama=1;sama<=n;sama++){
            ans=(ans+dp[n%2][w][sama])%mod;
        }
    }
    cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...