数学、容斥原理

值域较小，枚举每个值计算其对答案的贡献。考虑容斥，用可能以 $i$ 为最值的方案数减去不可能以 $i$ 为最值且序列最值小于 $i$ 的方案数得到序列最值为 $i$ 时的方案数。

时间复杂度 $O(nV)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998244353;
int n,ans,uim,lim,l[5005],r[5005];
long long calculate(int x){
    long long ret=1ll,sum=1ll;
    for(int i=1;i<=n;i++){
        if(x<=r[i]){
            ret=ret*(x-l[i]+1)%mod;
            sum=sum*(x-l[i])%mod;
        }
        else{
            ret=ret*(r[i]-l[i]+1)%mod;
            sum=sum*(r[i]-l[i]+1)%mod;
        }
    }
    ret=((ret-sum)%mod+mod)%mod;
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
    uim=*max_element(l+1,l+n+1);
    lim=*max_element(r+1,r+n+1);
    for(int i=uim;i<=lim;i++) ans=(ans+calculate(i)*i)%mod;
    ans=(ans+mod)%mod;
    printf("%d\n",ans);
    return 0;
}