C++11(clang++ 3.9) 解法, 执行用时: 122ms, 内存消耗: 32536K, 提交时间: 2019-12-20 22:33:51

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define gc (p1==p2&&(p2=(p1=fr)+fread(fr,1,1<<21,stdin))==p1?EOF:*p1++)
using namespace std;
char ch,fr[1<<21],*p1=fr,*p2=fr;
bool fig;
void rd(int&x)
{
    while(!isdigit(ch=gc)&&ch^45); if(fig=ch==45)ch=gc;
    x=ch-48;
    while( isdigit(ch=gc)) x=ch-48+x*10;
    if(fig) x=-x;
}
typedef long long ll;
const int N=410,mo=998244353;
int n,l[N],r[N],a[N],m,f[N/2][N][N/2],s,fac[N],ivf[N],iv[N],ans;
int fpow(int x,int y) {int a=1; for(;y;y>>=1,x=1ll*x*x%mo)if(y&1)a=1ll*a*x%mo; return a;}
int c(int x,int i) {return l[i]<r[i]?1ll*x*iv[i]%mo:1;}
int main()
{
    rd(n); fac[0]=1;
    fo(i,1,n)
    {
        rd(l[i]),rd(r[i]),a[i*2-1]=l[i],a[i*2]=r[i],ivf[i]=fpow(fac[i]=1ll*fac[i-1]*i%mo,mo-2);
        if(l[i]<r[i]) iv[i]=fpow(r[i]-l[i],mo-2);
    }
    sort(a+1,a+2*n+1); m=unique(a+1,a+2*n+1)-a-1;
    fo(i,1,m-1) if(l[1]<=a[i]&&a[i+1]<=r[1]) f[1][i][1]=c(a[i+1]-a[i],1);
    fo(i,1,n-1) fo(k,1,i)
    {
        s=0;
        fo(j,1,m-1)
        {
            if(l[i+1]<=a[j]&&a[j+1]<=r[i+1]) f[i+1][j][k+1]=1ll*f[i][j][k]*c(a[j+1]-a[j],i+1)%mo;
            s=(s+1ll*f[i][j][k]*ivf[k])%mo;
            if(j<m-1&&l[i+1]<=a[j+1]&&a[j+2]<=r[i+1]) f[i+1][j+1][1]=(f[i+1][j+1][1]+1ll*s*c(a[j+2]-a[j+1],i+1))%mo;
        }
    }
    fo(j,1,m-1) fo(k,1,n) ans=(ans+1ll*f[n][j][k]*ivf[k])%mo;
    printf("%d",ans);
}