#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define a first
#define b second
#define pb push_back
llo n,aa,bb;
map<llo,llo> dd;
llo si[2001];
llo mod=1000000007;
vector<llo> cc;
vector<pair<llo,llo>> it;
llo fac[501];
llo fac2[501];
llo pre[2001][501];
llo pre2[2001][501];
llo com[501][501];
llo dp[501][2001];
llo ind2=0;
llo mod2(llo ee,llo ff){
if(ff==0){
return 1;
}
llo ans=mod2(ee,ff/2);
ans*=ans;
ans%=mod;
if(ff%2==1){
ans*=ee;
ans%=mod;
}
return ans;
}
void comp(){
fac[0]=1;
for(llo i=1;i<501;i++){
fac[i]=fac[i-1]*i;
fac[i]%=mod;
}
for(llo i=0;i<501;i++){
fac2[i]=mod2(fac[i],mod-2);
}
}
void ncr(){
for(llo i=0;i<n+1;i++){
for(llo j=0;j<=i;j++){
com[i][j]=fac2[j]*fac2[i-j];
com[i][j]%=mod;
com[i][j]*=fac[i];
com[i][j]%=mod;
//cout<<i<<" "<<j<<" "<<com[i][j]<<endl;
// cout<<fac[i]<<" "<<fac2[j]<<" "<<fac2[i-j]<<endl;
}
}
}
void comp2(){
fac[0]=1;
for(llo i=0;i<ind2;i++){
llo cur=1;
pre[i][0]=0;
for(llo j=1;j<n+1;j++){
if(j<=si[i]){
cur*=mod2(j,mod-2);
cur%=mod;
cur*=(si[j]-j+1);
cur%=mod;
pre[i][j]=cur;
pre[i][j]+=pre[i][j-1];
pre[i][j]%=mod;
}
else{
pre[i][j]=pre[i][j-1];
}
}
}
for(llo i=0;i<ind2;i++){
for(llo j=1;j<n+1;j++){
pre2[i][j]=0;
for(llo k=1;k<=j;k++){
pre2[i][j]+=pre[i][k]*com[j-1][k-1];
pre2[i][j]%=mod;
}
//cout<<i<<"::"<<j<<" "<<pre2[i][j]<<endl;
}
}
}
int main(){
cin>>n;
for(llo i=0;i<n;i++){
cin>>aa>>bb;
cc.pb(aa);
cc.pb(bb);
it.pb({aa,bb});
}
comp();//factorial
ncr();//computing iCj for i and j from 1 to n
sort(cc.begin(),cc.end());
for(llo i=0;i<cc.size();i++){
if(i<cc.size()-1 and cc[i]==cc[i+1]){
continue;
}
dd[cc[i]]=ind2;
ind2+=1;
si[dd[cc[i]]]=1;
if(i<cc.size()-1){
if(cc[i]<cc[i+1]-1){
si[ind2]=cc[i+1]-cc[i]-1;
ind2+=1;
}
}
}
comp2();
for(llo i=0;i<n;i++){
it[i].a=dd[it[i].a];
it[i].b=dd[it[i].b];
}
for(llo i=0;i<n;i++){
for(llo j=0;j<ind2;j++){
dp[i][j]=0;
}
}
for(llo j=0;j<ind2;j++){
if(j>=it[0].a and j<=it[0].b){
dp[0][j]=si[j];
}
if(j>0){
dp[0][j]+=dp[0][j-1];
}
dp[0][j]%=mod;
}
for(llo i=1;i<n;i++){
for(llo j=it[i].a;j<=it[i].b;j++){
llo cot=1;
for(llo k=i-1;k>=0;k--){
if(j>0){
dp[i][j]+=(dp[k][j-1]+1)*pre2[j][cot];
dp[i][j]%=mod;
}
else{
dp[i][j]+=pre2[j][cot];
dp[i][j]%=mod;
}
if(it[k].a<=j and j<=it[k].b){
cot+=1;
}
}
}
for(llo j=1;j<ind2;j++){
dp[i][j]+=dp[i][j-1];
dp[i][j]%=mod;
}
}
llo ans=0;
for(llo i=0;i<n;i++){
// for(llo j=it[i].a;j<=it[i].b;j++){
ans+=dp[i][ind2-1];
ans%=mod;
//cout<<i<<",,"<<j<<",,"<<dp[i][j]<<endl;
// }
}
// cout<<dp[0][0]<<","<<dp[0][1]<<","<<dp[1][1]<<","<<dp[1][2]<<endl;
cout<<ans<<endl;
return 0;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:101:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(llo i=0;i<cc.size();i++){
~^~~~~~~~~~
boat.cpp:102:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i<cc.size()-1 and cc[i]==cc[i+1]){
~^~~~~~~~~~~~
boat.cpp:109:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i<cc.size()-1){
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1218 ms |
16376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1218 ms |
16376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
4600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1218 ms |
16376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
