Submission #1323821

#TimeUsernameProblemLanguageResultExecution timeMemory
1323821boclobanchatBoat (APIO16_boat)C++20
100 / 100
667 ms4468 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1024;
const int mod=1e9+7;
int dp[MAXN][MAXN/2],pre[MAXN][MAXN/2],sum[MAXN],val[MAXN],L[MAXN],R[MAXN],inv[MAXN],dist[MAXN];
void add(int& a,int b)
{
	if((a+=b)>=mod) a-=mod;
}
int poww(int n,int m)
{
	int res=n,ans=1;
	while(m)
	{
		if(m&1) ans=1LL*ans*res%mod;
		res=1LL*res*res%mod,m/=2;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		cin>>L[i]>>R[i];
		val[++cnt]=L[i],val[++cnt]=R[i]+1;
	}
	sort(val+1,val+cnt+1);
	for(int i=1;i<=cnt;i++) inv[i]=poww(i,mod-2),dist[i]=val[i+1]-val[i];
	dp[0][1]=1;
	for(int i=1;i<=n;i++)
	{
		int l=lower_bound(val+1,val+cnt+1,L[i])-val;
		int r=lower_bound(val+1,val+cnt+1,R[i]+1)-val-1;
		for(int j=0;j<cnt;j++)
		{
			sum[j]=0;
			for(int k=1;k<=n;k++) add(sum[j],pre[j][k]=dp[j][k]);
			if(j) sum[j]=(sum[j]+sum[j-1])%mod;
		}
		for(int j=l;j<=r;j++)
		{
			add(dp[j][1],1LL*sum[j-1]*dist[j]%mod);
			for(int k=1;k<=n;k++) add(dp[j][k],1LL*pre[j][k-1]*max(0,dist[j]-k+1)%mod*inv[k]%mod);
		}
	}
	int ans=mod-1;
	for(int j=0;j<cnt;j++) for(int k=1;k<=n;k++) add(ans,dp[j][k]);
	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...