This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
* Prof.Nicola
**/
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mp make_pair
#define F first
#define S second
#define REP(i,l,r) for(int i=(l);i<(r);i++)
#define PER(i,l,r) for(int i=(r)-1;i>=(l);i--)
#define bitl __builtin_clz
#define bitr __builtin_ctz
#define bits __builtin_popcount
const long dx[4]={1,0,-1,0},dz[4]={0,1,0,-1};
const long double pi=3.14159265359;
const long long mod=1e9+7;
long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
long long squared(long long x){return (x*x)%mod;}
long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));}
long long inv(long long x){return power(x,mod-2);}
long long log(long long x,long long z){if(x<z){return 0;}return 1+log(x/z,z);}
template<class T>void re(T&x){cin>>x;}
template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);}
template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void out(T x){cout<<x<<" ";}
template<class T1,class T2>void out(pair<T1,T2>x){out(x.first);out(x.second);cout<<endl;}
template<class T>void out(vector<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(deque<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(set<T>x){while(!x.empty()){out(*x.begin());x.erase(*x.begin());}cout<<endl;}
template<class T1,class T2>void out(map<T1,T2>x){while(!x.empty()){out(*x.begin());x.erase(x.begin()->first);}cout<<endl;}
template<class T>void out(queue<T>x){while(!x.empty()){out(x.front());x.pop();}cout<<endl;}
template<class T>void out(priority_queue<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>void out(stack<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>T cross(complex<T>x,complex<T>z){return (conj(x)*z).imag();}
template<class T>T dot(complex<T>x,complex<T>z){return (conj(x)*z).real();}
set<long long>::iterator T;
long long vLE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<=x){l+=z;}z/=2;}return l;}
long long vL(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<x){l+=z;}z/=2;}return l;}
long long vGE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return l;}l=vL(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long vG(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return l;}l=vLE(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long sLE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.begin()>x){return -1;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sL(long long x,set<long long>&ST){if(*ST.begin()>=x){return -1;}if(ST.count(x)){T=ST.find(x);T--;return *T;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sGE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.rbegin()<x){return -1;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
long long sG(long long x,set<long long>&ST){if(*ST.rbegin()<=x){return -1;}if(ST.count(x)){T=ST.find(x);T++;return *T;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
vector<long long>fact,inverse,der;
void init_fact(long x)
{
fact.clear();
inverse.clear();
fact.resize(x+1);
inverse.resize(x+1);
fact[0]=1;
for(long long i=1;i<=x;i++){
fact[i]=(fact[i-1]*i)%mod;
}
inverse[x]=inv(fact[x]);
for(long long i=x-1;i>=0;i--){
inverse[i]=(inverse[i+1]*(i+1))%mod;
}
}
vector<vector<int> >dp,c;
vector<vector<bool> >ok;
vector<int>v;
vector<pair<int,int> >range;
int solve(int x,int z)
{
if(x<0){
return 1;
}
if(z<0){
return 0;
}
if(ok[x][z]){
return dp[x][z];
}
ok[x][z]=true;
dp[x][z]=solve(x,z-1);
if(!(range[x].F<=v[z]&&v[z+1]-1<=range[x].S)){
return dp[x][z];
}
long long sum=0,can=1;
REP(j,0,x){
if(range[j].F<=v[z]&&v[z+1]-1<=range[j].S){
can++;
}
}
REP(j,0,x+1){
sum+=solve(j-1,z-1);
sum%=mod;
if(!(range[j].F<=v[z]&&v[z+1]-1<=range[j].S)){
continue;
}
dp[x][z]+=(sum*c[can][z])%mod;
dp[x][z]%=mod;
can--;
}
return dp[x][z];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n,ans=0,x,z;
cin>>n;
init_fact(2*n);
vector<vector<long long> >choose(2*n,vector<long long>(n+1));
dp.resize(n);
ok.resize(n);
c.resize(n+1);
REP(j,0,n){
dp[j].resize(2*n);
ok[j].resize(2*n);
c[j].resize(2*n);
}
c[n].resize(2*n);
range.resize(n);
re(range);
REP(j,0,n){
v.push_back(range[j].F);
v.push_back(range[j].S+1);
}
sort(v.begin(),v.end());
REP(j,1,v.size()){
if(v[j]==v[j-1]){
v.erase(v.begin()+j);
j--;
}
}
REP(i,0,v.size()-1){
x=v[i+1]-v[i];
z=1;
REP(j,1,n+1){
z*=x-j+1;
z%=mod;
choose[i][j]=(z*inverse[j])%mod;
}
}
vector<vector<long long> >nck(n+1,vector<long long>(n+1));
REP(i,0,n+1){
REP(j,0,i+1){
nck[i][j]=(((fact[i]*inverse[j])%mod)*inverse[i-j])%mod;
}
}
REP(i,2,n+1){
REP(j,0,v.size()-1){
REP(k,0,i-1){
c[i][j]+=(nck[i-2][k]*choose[j][k+2])%mod;
c[i][j]%=mod;
}
}
}
REP(j,0,v.size()-1){
c[1][j]=v[j+1]-v[j];
}
REP(j,0,n){
ans+=solve(j,v.size()-2);
ans%=mod;
}
cout<<ans<<endl;
return 0;
}
Compilation message (stderr)
boat.cpp: In function 'int main()':
boat.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define REP(i,l,r) for(int i=(l);i<(r);i++)
| ^
boat.cpp:126:5: note: in expansion of macro 'REP'
126 | REP(j,1,v.size()){
| ^~~
boat.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define REP(i,l,r) for(int i=(l);i<(r);i++)
| ^
boat.cpp:132:5: note: in expansion of macro 'REP'
132 | REP(i,0,v.size()-1){
| ^~~
boat.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define REP(i,l,r) for(int i=(l);i<(r);i++)
| ^
boat.cpp:148:9: note: in expansion of macro 'REP'
148 | REP(j,0,v.size()-1){
| ^~~
boat.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define REP(i,l,r) for(int i=(l);i<(r);i++)
| ^
boat.cpp:155:5: note: in expansion of macro 'REP'
155 | REP(j,0,v.size()-1){
| ^~~
boat.cpp: In instantiation of 'void re(std::vector<_Tp>&) [with T = std::pair<int, int>]':
boat.cpp:120:13: required from here
boat.cpp:26:53: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |