Submission #1184537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184537		byunjaewoo	Boat (APIO16_boat)	C++20	0 / 100	310 ms	2676 KiB

boat

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=510, Mod=1e9+7;
int n, m, a[N], b[N], f[N], fi[N], s[N][N], x[N][2*N];
vector<int> c;

int Pow(int a, int b) {
    if(!b) return 1;
    int tmp=Pow(a, b/2); tmp=(tmp*tmp)%Mod;
    if(b&1) tmp=(tmp*a)%Mod;
    return tmp;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    f[0]=fi[0]=1;
    for(int i=1; i<N; i++) f[i]=(f[i-1]*i)%Mod, fi[i]=(fi[i-1]*Pow(i, Mod-2))%Mod;
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i]>>b[i];
        c.push_back(a[i]), c.push_back(b[i]+1);
    }
    c.push_back(0), c.push_back(1);
    sort(c.begin(), c.end()), c.erase(unique(c.begin(), c.end()), c.end());
    m=c.size()-1;
    for(int i=1; i<=m; i++) {
        x[0][i]=1, s[i][1]=c[i]-c[i-1];
        for(int j=2; j<=n; j++) {
            s[i][j]=1;
            for(int k=0; k<j; k++) s[i][j]=(s[i][j]*(s[i][1]-k))%Mod;
            s[i][j]=(s[i][j]*fi[j])%Mod;
        }
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            x[i][j]=(x[i][j-1]+x[i-1][j]-x[i-1][j-1]+Mod)%Mod;
            if(a[i]<=c[j-1] && c[j]-1<=b[i]) {
                for(int k=i-1; k>=0; k--) x[i][j]=(x[i][j]+s[i][i-k]*x[k][j-1])%Mod;
            }
        }
    }
    cout<<(x[n][m]+Mod-1)%Mod;
    return 0;
}

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