| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 978279 | Amr | Boat (APIO16_boat) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define all(x) (x).begin(),(x).end()
#define sz size()
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define pb(x) push_back(x);
#define endl '\n'
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N=204;
ll INF=INT_MAX,mod=1e9+7;
int TT=1;
ll power(ll x, unsigned int y)
{
ll res = 1;
x = x % mod;
if (x == 0) return 0;
while (y > 0)
{
if (y & 1) res = (res*x) % mod;
y = y>>1;
x = (x*x) % mod;
}
return res;
}
ll a[N] , b[N];
map<ll,ll> com;
ll recom[N];
ll siz[N];
ll dp[N][N];
ll ch[N][N];
ll ch2[N][N];
ll p[N];
ll bit[2*N];
ll n;
void upd(ll x, ll val)
{
while(x < N)
{
bit[x] = (bit[x] + val)%mod;
x += x&(-x);
}
}
ll get(ll x)
{
ll res = 0;
while(x)
{
res+=bit[x];
x -= x&(-x);
}
return res%mod;
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
p[0] = 1;
for(int i = 1; i < N; i++) p[i] = (p[i-1]*i)%mod;
for(int i = 1; i <= n; i++) com[a[i]] = 1, com[b[i]+1] = 1;
ll l = 1;
for(auto it: com)
{
com[it.F] = l;
recom[l++] = it.F;
}
for(int i = 1; i <= 2*n; i++) siz[i] = recom[i+1]-recom[i];
// for(int i = 1; i <= 2*n; i++) cout << recom[i] << " "; cout << endl;
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= i; j++)
{
ll above = p[i];
ll down = p[j]*p[i-j];
ch[i][j] = above*power(down,mod-2);
}
}
for(int i = 1; i <= 2*n; i++)
{
if(recom[i+1]==0) continue;
for(int j = 0; j <= siz[i]; j++)
{
ll above = 1;
for(int k = siz[i]; k > siz[i]-j; k--) above = (above*k)%mod;
ll down = p[j];
ch2[i][j] = (above*power(down,mod-2))%mod;
}
}
20*
for(int i = 1; i <= n; i++)
{
ll curend = com[b[i]+1];
ll curstart = com[a[i]];
for(int j = curend-1; j>= curstart; j--)
{
dp[i][j] = get(j-1);
ll something = 0;
//
ll cnt = 0;
for(int k = i; k >= 1; k--)
{
if(com[a[k]]<=j&&com[b[k]+1]>j) {cnt++;} else continue;
for(int kk = 1; kk <= cnt; kk++) { something = (something +ch[cnt-2+1*(k==i)][kk-2+(k==i)]*ch2[k][kk]);}
}
// cout << something << endl;
upd(j,something%mod+dp[i][j]);
}
}
cout << get(2*n+1) << endl;
}
int main(){
//freopen("friday.in","r",stdin);
//freopen("friday.out","w",stdout);
fast;
while(TT--)
solve();
return 0;
}