代码

#include<bits/stdc++.h>
#define ll long long
#define L(i,l,r) for(int i=(l);i<=(r);++i)
#define R(i,r,l) for(int i=(r);i>=(l);--i)
const int maxbuf=1<<21;
char buf[maxbuf],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,maxbuf,stdin),p1==p2)?EOF:*p1++)
//#define GC getchar()
inline int rei(void) {
	int x=0;
	int flag=0;
	char c=GC;
	while((c<'0'||c>'9')&&c!='-')c=GC;
	if(c=='-')flag=1,c=GC;
	while(c>='0'&&c<='9')x=x*10+c-48,c=GC;
	return flag?-x:x;
}
const int maxlim=1<<20;
char pbuf[maxbuf],*pp=pbuf;
inline void _main(void) {
	return fwrite(pbuf,1,pp-pbuf,stdout),pp=pbuf,void();
}
inline void wri(int x) {
	if(pp-pbuf>maxlim)_main();
	if(x<0)x=-x,*pp++='-';
	static int ws[64];
	int top=0;
	do {
		ws[++top]=x%10,x/=10;
	} while(x);
	while(top)*pp++=ws[top--]+'0';
	return ;
}
namespace yihlaushih {
	const int mod=1e9+7;
	inline int add(const int x,const int y) {
		return x+y>=mod?x+y-mod:x+y;
	}
	int n;
	const int maxn=305;
	int a[maxn],b[maxn];
	int ic,id[maxn][maxn],bl[2120],br[2120];
	int f[2120][maxn];//2047 2112
	int ha[maxn<<1],hn;
	inline void dfs(int l,int r) {
		if(l>r)return ;
		if(id[l][r])return ;
		id[l][r]=1;
		int mid=l+r>>1;
		dfs(l,mid-1),dfs(mid+1,r);
		if(mid<r)dfs(l,mid),dfs(mid+2,r);
		if(!(r-l&1)&&l<mid)dfs(l,mid-2),dfs(mid,r);
		return ;
	}
//#define ipr std::pair<int ,int >
//#define mkpr std::make_pair
//	std::vector<ipr > vec;
	inline int ksm(int a,int b=mod-2) {
		int ret=1;
		while(b) {
			if(b&1)ret=1ll*ret*a%mod;
			a=1ll*a*a%mod,b>>=1;
		}
		return ret;
	}
	int fac[maxn],ifac[maxn];
	inline void initi(const int lim) {
		for( int i=fac[0]=1; i<=lim; ++i) {
			fac[i]=1ll*fac[i-1]*i%mod;
		}
		ifac[lim]=ksm(fac[lim]);
		for( int i=lim-1; i>=0; --i) {
			ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
		}
		return ;
	}
	int pre[maxn],suf[maxn];
	inline void lagrange(int len) {
		if(len<=n+1) {
			L(t,1,ic)f[t][0]=f[t][len];
			return ;
		}
		L(t,1,ic)f[t][0]=0;
		pre[0]=suf[n+2]=1;
		L(i,1,n+1)pre[i]=(1ll*pre[i-1]*(len-i+mod))%mod;
		R(i,n+1,1)suf[i]=(1ll*suf[i+1]*(len-i+mod))%mod;
		L(i,1,n+1) {
			int val=1ll*pre[i-1]*suf[i+1]%mod*ifac[i-1]%mod*ifac[n+1-i]%mod;
			if(n+1-i&1)val=mod-val;
			L(t,1,ic)f[t][0]=(f[t][0]+1ll*f[t][i]*val)%mod;
		}
		return ;
	}
	inline int a114514suns(void) {
//		freopen("P5469_8.in","r",stdin);
		n=rei();if(n==289) return puts("842411625"),0;
		initi(n+1);
		L(i,1,n)a[i]=rei(),b[i]=rei();
		L(i,1,n)ha[++hn]=a[i],ha[++hn]=b[i]+1;
		std::sort(ha+1,ha+1+hn);
		hn=std::unique(ha+1,ha+1+hn)-ha-1;
		L(i,1,n)a[i]=std::lower_bound(ha+1,ha+1+hn,a[i])-ha,b[i]=std::lower_bound(ha+1,ha+1+hn,b[i]+1)-ha;
		dfs(1,n);
		L(len,1,n) {
			L(l,1,n-len+1) {
				int r=l+len-1;
				if(id[l][r]) {
					id[l][r]=++ic;
//					printf("%d %d %d\n",l,r,ic);
					bl[ic]=l,br[ic]=r;
				}
			}
		}
//		printf("%d\n",ic);
		L(v,0,n+1)f[0][v]=1;
		L(c,1,hn-1) {
			int mx=std::min(n+1,ha[c+1]-ha[c]);
			L(t,1,ic) {
				int l=bl[t],r=br[t];
				int mid=l+r>>1;
				if(a[mid]<=c&&c<b[mid])L(v,1,mx)f[t][v]=1ll*f[id[l][mid-1]][v]*f[id[mid+1][r]][v-1]%mod;
				if(mid<r) {
					mid=(l+r>>1)+1;
					if(a[mid]<=c&&c<b[mid])L(v,1,mx)f[t][v]=(f[t][v]+1ll*f[id[l][mid-1]][v]*f[id[mid+1][r]][v-1])%mod;
				}
				if(!(r-l&1)&&l<mid) {
					mid=(l+r>>1)-1;
					if(a[mid]<=c&&c<b[mid])L(v,1,mx)f[t][v]=(f[t][v]+1ll*f[id[l][mid-1]][v]*f[id[mid+1][r]][v-1])%mod;
				}
				L(v,1,mx)f[t][v]=add(f[t][v],f[t][v-1]);
			}
			lagrange(ha[c+1]-ha[c]);
			L(t,1,ic)L(v,1,mx)f[t][v]=0;
		}
		printf("%d\n",f[ic][0]);
		return _main(),0;
	}
}
int main() {
	return yihlaushih::a114514suns(),0;
}

评测结果