Submission #579360

#TimeUsernameProblemLanguageResultExecution timeMemory
579360jiahngBoat (APIO16_boat)C++14
9 / 100
845 ms29512 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef pair<int32_t, int32_t> pi; typedef vector <int> vi; typedef vector <pi> vpi; typedef pair<pi, ll> pii; typedef set <ll> si; typedef long double ld; #define f first #define s second #define mp make_pair #define FOR(i,s,e) for(int i=s;i<=int(e);++i) #define DEC(i,s,e) for(int i=s;i>=int(e);--i) #define pb push_back #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) #define aFOR(i,x) for (auto i: x) #define mem(x,i) memset(x,i,sizeof x) #define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define maxn 1010 #define INF (ll)1e9+10 #define MOD 1000000007 typedef pair <vi, int> pvi; typedef pair <int,pi> ipi; typedef vector <pii> vpii; int N,A[maxn],B[maxn]; int fac[maxn], invfac[maxn]; int qexp(int a,int b){ int ans = 1; while (b){ if (b&1) (ans *= a) %= MOD; (a *= a) %= MOD; b >>= 1; } return ans; } int nck(int n,int k){ if (k > n) return 0; return (((fac[n] * invfac[k]) % MOD) * invfac[n-k]) % MOD; } int suffmult[2*maxn][maxn]; int dp[maxn][2*maxn]; int S[2*maxn],E[2*maxn]; int specnck(int x,int k){ //~ cout << E[x]-S[x]+1 << ' ' << k << ' ' << (invfac[k] * suffmult[x][k]) % MOD << '\n'; return (invfac[k] * suffmult[x][k]) % MOD; } int memo[maxn][maxn]; int f(int x,int y){ if (memo[x][y] != -1) return memo[x][y]; int ans = 0; FOR(z,1,x){ ans += nck(x-1,z-1) * specnck(y,z); } return memo[x][y] = ans; } int32_t main(){ cin >> N; FOR(i,1,N) cin >> A[i] >> B[i]; fac[0] = 1; FOR(i,1,N) fac[i] = (fac[i-1] * i) % MOD; invfac[N] = qexp(fac[N], MOD-2); DEC(i,N-1,0) invfac[i] = (invfac[i+1] * (i+1)) % MOD; vi v; FOR(i,1,N){ v.pb(A[i]); v.pb(B[i]); } v.pb(0); v.pb(INF); sort(all(v)); v.erase(unique(all(v)),v.end()); int M = 1; FOR(i,0,(int)v.size()-1){ S[M] = v[i]; E[M] = v[i]; M++; if (i + 1 < (int)v.size() && v[i] + 1 < v[i+1]){ S[M] = v[i]+1; E[M] = v[i+1]-1; M++; } } M--; FOR(i,1,M){ suffmult[i][0] = 1; int x = E[i] - S[i] + 1; FOR(j,1,N){ suffmult[i][j] = (suffmult[i][j-1] * x) % MOD; x--; } } FOR(i,1,M) dp[N+1][i] = 1; mem(memo, -1); DEC(i,N,1){ DEC(j,M,1){ if (B[i] < S[j]){ dp[i][j] = 0; continue; } dp[i][j] = dp[i][j+1]; if (A[i] <= S[j] && E[j] <= B[i]){ int num = 1; FOR(k,i+1,N+1){ (dp[i][j] += (dp[k][j+1] * f(num, j)) % MOD) %= MOD; if (A[k] <= S[j] && E[j] <= B[k]) num++; } } } } int ans = 0; FOR(i,1,N){ (ans += dp[i][1]) %= 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...