Submission #1027527

#TimeUsernameProblemLanguageResultExecution timeMemory
1027527_8_8_Boat (APIO16_boat)C++17
27 / 100
1256 ms8584 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 mem[N][N]; ll ceis(ll n,ll k){ if(k > n) return 0; if(n < N && mem[n][k]) return mem[n][k]; 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; } if(n < N){ mem[n][k] = d; } return d; } int n; array<int,2> a[N]; vector<int> b; vector<array<int,2>> o; ll dp[N][N],pref[N][N],c[N][N]; int m; 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.push_back({b[i-1],b[i]-1}); } int m = (int)o.size(); for(int i = 0;i <= m;i++){ pref[0][i] = 1; } for(int i = 1;i <= m;i++){ int s = (o[i - 1][1] - o[i - 1][0]+1); c[i][1] = s; vector<ll> C(n+1,0); for(int j = 0;j <= n;++j){ C[j] = ceis(s,j); } for(int j = 2;j <= n;j++){ for(int k = 0;k <= j-2;k++){ c[i][j] = (c[i][j] + ceis(j-2,k)*C[j-k]%MOD)%MOD; } } } // return; for(int i = 1;i <= n;i++){ pref[i][0] = 1; for(int j = 1;j <= m;j++){ dp[i][j] = dp[i - 1][j]; if(a[i][0] <= o[j - 1][0] && a[i][1] >= o[j-1][1]){ for(int k = i,col = 0;k >= 1;k--){ if(a[k][0] <= o[j-1][0] && a[k][1] >= o[j-1][1]){ ++col; dp[i][j] += pref[k-1][j-1]*c[j][col]%MOD; // cout << j << ' ' << col << ' ' << c[j][col]%MOD << "x\n"; if(dp[j][j] >= MOD) dp[i][j] -= MOD; } } } } for(int j = 1;j <= m;j++){ // cout << dp[i][j] << ' '; pref[i][j] = (pref[i][j - 1] + dp[i][j])%MOD; } // cout << '\n'; } cout << (pref[n][m]-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...