有 n 个独立的随机变量,其中 x​i 的值是一个从 [l​i​ ,r​i​​ ] 中随机选取的整数,即对于 [l​i​​ ,r​i​ ] 中的任何一个整数 j,x​i​​ =j 的概率都是 (r​i​​ −l​i​​ +1)​−1​​ 。

现在你需要给出一个长度为 n 的排列 p,那么可以得到一个长度为 n 的随机变量序列 。你的目标是让结果序列的逆序对个数的期望尽可能少。求逆序对个数的期望的最小值。
输入格式:
第一行输入一个整数 n(1≤n≤5×10​3​​ )。

接下来 n 行每行两个整数 l​i​​ ,r​i​​ (1≤l​i​​ ≤r​i​​ ≤109​​ )。

输出格式
输出一行一个整数,表示答案对 998244353 取模后的值。假设答案的最简分数表示是​y/​x​​ ,你需要输出一个整数 k 满足 k×y≡x mod 998244353。

输入样例:
3
1 2
2 3
1 3

输出样例:
332748118

题解:mmh学长告知,只需要按两个区间的中点排序即可获得最优。
(交换两个区间即可证明),然后求期望即可。
注意:需要预处理逆元。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define x first
#define y second
#define int ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
const int maxn=5050;
int n,inv2;
struct node
{
    int a,b;
}p[maxn];
int inv[maxn];
ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

bool cmp(const node &a,const node &b)
{
    return a.a+a.b<b.a+b.b;
}

int get1(int i,int j)
{
    int pn=p[j].b-p[i].a+1;
    int pm=p[j].a-p[i].a+1;
    return ((p[j].b-p[j].a+1)*(p[i].b-p[i].a+1)%mod-(pn+pm)*(p[j].b-p[j].a+1)%mod*inv2%mod+mod)%mod;
}

int get2(int i,int j)
{
    int pn=p[i].a-p[j].a;
    int pm=p[i].b-p[j].a;
    return (pn+pm)*(p[i].b-p[i].a+1)%mod*inv2%mod;
}

int get3(int i,int j)
{
    return (p[i].b-p[j].a)*(p[i].b-p[j].a+1)%mod*inv2%mod;
}

int get4(int i,int j)
{
    return ((p[j].b-p[j].a+1)*(p[i].b-p[i].a+1)%mod-(p[j].b-p[i].a+1)*(p[j].b-p[i].a+2)%mod*inv2%mod+mod)%mod;
}

signed main(void)
 {
    int n;
    inv2=mypow(2,mod-2);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&p[i].a,&p[i].b);
    sort(p+1,p+n+1,cmp);

    for(int i=1;i<=n;i++)
        inv[i]=mypow(p[i].b-p[i].a+1,mod-2);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int ansx=0;
            int ansy=0;
            ansy=(p[j].b-p[j].a+1)*(p[i].b-p[i].a+1);
            ansy=ansy%mod;
            if(p[i].b<=p[j].a||p[j].b<=p[i].a) continue;
            if(p[i].b-p[j].b>=0&&p[j].a-p[i].a>=0) ansx=(ansx+get1(i,j))%mod;
            else if(p[i].b-p[j].b<0&&p[j].a-p[i].a<0) ansx=(ansx+get2(i,j))%mod;
            else if(p[i].b-p[j].b<0) ansx=(ansx+get3(i,j))%mod;
            else if(p[j].a-p[i].a<0) ansx=(ansx+get4(i,j))%mod;

            ans=(ans+(ansx*inv[i]%mod*inv[j]%mod+mod)%mod)%mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}