Submission #1352972

#TimeUsernameProblemLanguageResultExecution timeMemory
1352972sallyBoat (APIO16_boat)C++20
0 / 100
3 ms4164 KiB
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
typedef pair<int,int> pii;
const int mod = 1e9+7;
int N;
vector<pii> range;
vector<int> des;
int f[503][503<<1];
signed main() {
    cin>>N;
    range.push_back({});
    des.push_back(0);
    for(int i=1; i<=N; i++) {
        int L, R;
        cin>>L>>R;
        range.push_back({L, R+1}); // [L, R) => dp時比較好用
        des.push_back(L);
        des.push_back(R+1);
    }
    sort(des.begin()+1, des.end());
    des.resize(unique(des.begin(), des.end()) - des.begin());
    for(int i=1; i<=N; i++) {
        range[i].first = lower_bound(des.begin()+1,des.end(), range[i].first) - des.begin();
        range[i].second = lower_bound(des.begin()+1,des.end(), range[i].second) - des.begin();
    }
    int sz = des.size() - 1;
    vector<int> l(sz);
    for(int i=0; i<sz; i++) {
        l[i] = des[i+1] - des[i];
    }
    vector<int> ni(N+1, 0);
    ni[1] = 1;
    for(int i=2; i<=N; i++) {
        ni[i] = 1LL*(mod - mod / i) * ni[mod%i] % mod;
    }
    for(int i=0; i<sz; i++) f[0][i] = 1;
    for(int i=1; i<=N; i++) {
        for(int j = range[i].first, up = range[i].second; j < up; j++) {
            int C = l[j], r = l[j], c = 1;
            for(int k = i-1; k>=0; k--) {
                (f[i][j] += 1LL*f[k][j-1]*C%mod)%=mod;
                if(range[k].first <= j && j < range[k].second) {
                    r++; c++;
                    C = (1LL*C*r%mod)*ni[c]%mod; // C(r+1, c+1) = C(r, c) * (r+1) / (c+1)
                }
            }
            
        }
        for(int j=2; j<=sz; j++) (f[i][j] += f[i][j-1])%mod;
    }
    int ans = 0LL;
    for(int i=1; i<=N; i++) {
        (ans += f[i][sz])%mod;
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...