代码

#include <cstdio>
#include <cmath>
#include <algorithm> 
using namespace std;
#define ll long long
#define rint register int
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
#define IL inline
const int mo=1e9+7;
const int INF=1e9;
const int N=1e3+10;
int n,jc[N],jc2[N],len[N],a[N],b[N],f[N][N*2],sum[N][N*2],C[N*2][N];
struct re{
  int a,b;
}c[N];
IL bool cmp(re x,re y)
{
  return x.a<y.a;
}
void gcd(int a,int b,int &x,int &y)
{
  if (b==0)
  {
    x=1; y=0; return;
  }
  gcd(b,a%b,y,x);
  y-=x*(a/b);
}
IL void js(int &x,int y)
{
  x+=y;
  if (x>=mo) x-=mo;
}
int main()
{
  n=500;
  jc[0]=1;
  rep(i,1,n)
  {
    int x,y;
    gcd(i,mo,x,y);
    jc[i]=(1ll*jc[i-1]*x)%mo;
    jc2[i]=(1ll*jc2[i-1]*i)%mo;
  }
  rep(i,1,n)
  {
     c[i*2-1].a=rand(); c[i*2].a=rand();
    if (c[i*2-1].a>c[i*2].a) swap(c[i*2-1].a,c[i*2].a);
    c[i*2].a++;
    c[i*2-1].b=i*2-1; c[i*2].b=i*2;
  }
  sort(c+1,c+n*2+1,cmp);
  int cnt=0;
  c[0].a=INF;
  rep(i,1,n*2)
  {
    if (c[i].a!=c[i-1].a) cnt++,len[cnt]=c[i].a-c[i-1].a;
    if (c[i].b%2) a[(c[i].b+1)/2]=cnt+1;
    else b[c[i].b/2]=cnt;
  }
  int m=cnt;
  for (int i=1;i<=m;i++)
  {
    int p=1;
    C[i][0]=1;
    for (int j=1;j<=n+1;j++)
      p=(1ll*p*(len[i]+j-1))%mo,C[i][j]=((1ll*p*jc[j])%mo+mo)%mo;  
  }
  f[0][0]=1;
  rep(i,0,m) sum[0][i]=1;
  int ans=0;
  rep(i,1,n)
  {
    rep(j,a[i],b[i])
    {
      rint kk=0;
      dep(k,i-1,0)
      {
        rint now=sum[k][j-1];
        if (now) js( f[i][j],(1ll*now*C[j][kk+1])%mo);
        if (a[k]<=j&&j<=b[k]) kk++;
      }
      sum[i][j]=sum[i][j-1]+f[i][j];
      if (sum[i][j]>=mo) sum[i][j]-=mo;
      js(ans,f[i][j]);
    }
    rep(j,b[i]+1,m) sum[i][j]=sum[i][j-1];
  }
  printf("%d",(ans+mo)%mo);
  return 0;
}

评测结果