Submission #1027047

#TimeUsernameProblemLanguageResultExecution timeMemory
1027047_8_8_Boat (APIO16_boat)C++17
0 / 100
2060 ms4948 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e2 + 20, MOD = (int)1e9+7; ll binpow(ll a,ll b) { ll ans = 1,k = a; while(b) { if(b % 2)ans *= k; ans %= MOD; k *= k; k %= MOD; b /= 2ll; } return ans; } ll bp[N]; ll ceis(ll n,ll k){ if(k > n) return 0; ll d = 1; for(ll i = n - k + 1;i <= n;i++){ d = i % MOD * d % MOD; } for(ll i = 2;i <= k;i++){ d = d * bp[i]%MOD; } return d; } int n; array<int,2> a[N]; vector<int> b; vector<pair<int,int>> o; ll dp[N][N],pref[N][N],c[N][N]; bool cc[N][N]; void test(){ cin >> n; for(int i = 1;i <= n;i++){ cin >> a[i][0] >> a[i][1]; b.push_back(a[i][0]); b.push_back(a[i][1] + 1); bp[i] = binpow(i,MOD-2); } sort(b.begin(),b.end()); b.resize(unique(b.begin(),b.end()) - b.begin()); for(int i = 1;i < (int)b.size();i++){ o.emplace_back(b[i - 1],b[i] - 1); } // for(auto [l,r]:o){ // cout << l << ' ' << r << '\n'; // } for(int i = 0;i <= (int)o.size();i++){ pref[0][i] = 1; } for(int i = 1;i <= (int)o.size();i++){ int s = (o[i - 1].second - o[i - 1].first) + 1; for(int j = 1;j <= n;j++){ c[i][j] = ceis(s,j); for(int k = 1;k < j-1;k++){ c[i][j] += (ceis(j-1,k)-k) * ceis(s,j-k)%MOD; c[i][j]%=MOD; // cout << i << ' ' << j << ' ' << k << ' ' << (ceis(j-1,k)-k) << ' ' << ceis(s,j-k) << '\n'; } } } for(int i = 1;i <= n;i++){ vector<int> can; for(int j = 0;j < (int)o.size();j++){ if(o[j].first >= a[i][0] && o[j].second <= a[i][1]) { cc[i][j + 1] =1; can.push_back(j + 1); } dp[i][j + 1] = dp[i - 1][j + 1]; } for(int j:can){ ll F = 0; int _ = 0; for(int f = 1;f <= i;f++){ int lst = i - (f); if(lst!=i && !cc[lst+1][j]){ _++; continue; } dp[i][j] += pref[lst][j - 1] * c[j][f-_] % MOD; F +=pref[lst][j - 1] * c[j][f] % MOD; if(dp[i][j] >= MOD) dp[i][j] -= MOD; } // cout << F << "x\n"; } pref[i][0] = 1; // for(int j = 0;j <= (int)o.size();j++){ // cout << dp[i][j] << ' '; // } // cout << '\n'; for(int j = 1;j <= (int)o.size();j++){ pref[i][j] = pref[i][j - 1] + dp[i][j]; if(pref[i][j] >= MOD) pref[i][j] -= MOD; } // cout << '\n'; } cout << (pref[n][(int)o.size()] - 1 + MOD)%MOD << '\n'; } int main() { ios_base::sync_with_stdio(false);cin.tie(0); int t = 1; // cin >> t; while(t--){ test(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...