有 n 个独立的随机变量,其中 xi 的值是一个从 [li ,ri ] 中随机选取的整数,即对于 [li ,ri ] 中的任何一个整数 j,xi =j 的概率都是 (ri −li +1)−1 。
现在你需要给出一个长度为 n 的排列 p,那么可以得到一个长度为 n 的随机变量序列 。你的目标是让结果序列的逆序对个数的期望尽可能少。求逆序对个数的期望的最小值。
输入格式:
第一行输入一个整数 n(1≤n≤5×103 )。
接下来 n 行每行两个整数 li ,ri (1≤li ≤ri ≤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;
}