2020 CCPC Wannafly Winter Camp Day1 Div.1&2（A题 期望逆序对）（找规律）

2020 CCPC Wannafly Winter Camp Day1 Div.1&2（A题 期望逆序对）（找规律）

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

有 $n$n 个独立的随机变量，其中 $x_i$xi​ 的值是一个从 $[l​_i ,r_i]$[l​i​,ri​] 中随机选取的整数，即对于 $[l​_i ,r_i]$[l​i​,ri​] 中的任何一个整数 $j$j，$x_i= j$xi​=j 的概率都是 $(r_i-l_i+1)^{-1}$(ri​−li​+1)−1 现在你需要给出一个长度为 ${n}$n 的排列 ${p}$p，那么可以得到一个长度为 ${n}$n 的随机变量序列 。你的目标是让结果序列的逆序对个数的期望尽可能少。
求逆序对个数的期望的最小值。

输入描述:

第一行输入一个整数 ${n}(1\leq n \leq 5\times 10^3)$n(1≤n≤5×103) 接下来 $n$n 行每行两个整数 $l_i,r_i (1\leq l_i \leq r_i\leq 10^9)$li​,ri​(1≤li​≤ri​≤109) 。

输出描述:

输出一行一个整数，表示答案对 $998244353$998244353 取模后的值。假设答案的最简分数表示是 $\frac{x}{y}$yx​ ，你需要输出一个整数 $k$k 满足 $k \times y \equiv x \bmod 998244353$k×y≡xmod998244353。

示例1

输入

3
1 2
2 3
1 3

输出

332748118

题解

官方题解为：

但我回来反复琢磨后发现一处问题：

这个式子在 $r_1 > l_2$r1​>l2​ 的时候处理的不太对，不过题解代码倒是没什么问题。

假如有区间 $1$1 为 $[1,3]$[1,3] 区间 $2$2 为 $[2,4]$[2,4] ，那么枚举区间 $1$1 的元素时，当 $i$i 为 $2$2 的时候 此时若想让区间 $1$1 的元素大于区间 $2$2 的元素，那么无论区间 $2$2 取哪个，都是不可能的，而官方题解的式子里可以看出区间 $2$2 里有 $1$1 中取法（$max(0,min(2,4)-2+1)$max(0,min(2,4)−2+1)为 $1$1 ），这显然是不符合的；当 $i$i为 $3$3 的时候，此时区间 $2$2 里只有一种取法，就是取 $2$2 ，但是官方题解的式子里得出了 $2$2 种取法（$max(0,min(3,4)-2+1)$max(0,min(3,4)−2+1)为 $2$2 ），这显然也是不符合的。

也就是说当 $r_1 > l_2$r1​>l2​ 的时候，每次枚举都会多加 $1$1 。

修改后的式子：
$(r_1-l_1+1)^{-1}(r_2-l_2+1)^{-1}\sum_{i=l_1}^{r_1}{max(0,min(i,r_2+1)-l_2)}$(r1​−l1​+1)−1(r2​−l2​+1)−1i=l1​∑r1​​max(0,min(i,r2​+1)−l2​)

对 $i$i 是否大于 $r_2$r2​ 进行分类讨论：

令 $r$r 等于 $min(r_1,r_2)$min(r1​,r2​) ，把区间 $1$1 以 $r_2$r2​ 为边界拆成 $[l_1,r]$[l1​,r]，和 $(r,r_1]$(r,r1​] 两部分（如果 $r$r 等于 $r_1$r1​ ，那么第二部分为空集），计算第一部分对应的取值情况种类应该有 $(l-l_2+r-l_2)(r-l+1)/2$(l−l2​+r−l2​)(r−l+1)/2（等差数列求和，见于代码第33行），计算第二部分对应的取值情况种类应该有 $(r_1-r)(r_2-l_2+1)$(r1​−r)(r2​−l2​+1)（见于代码第34行）。

代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct atom {
	int l, r;
	void scan() {
		scanf("%d%d", &l, &r);
	}
};
const int N = 5100;
const int mo = 998244353;
int operator < (atom k1, atom k2) {
	return k1.l + k1.r < k2.l + k2.r;
}
int n, inv[N];
atom A[N];
int quick(int k1, int k2) {
	int k3 = 1;
	while (k2) {
		if (k2 & 1) k3 = 1ll * k3*k1%mo;
		k2 >>= 1; k1 = 1ll * k1*k1%mo;
	}
	return k3;
}
int calc(atom k1, atom k2) {
	int l = max(k1.l, k2.l);
	if (l > k1.r) return 0;
	int r = min(k1.r, k2.r);
	int ans = 1ll * (l - k2.l + r - k2.l)*(r - l + 1) / 2 % mo;
	ans = (ans + 1ll * (k1.r - r)*(k2.r - k2.l + 1)) % mo;
	return ans;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) A[i].scan();
	sort(A + 1, A + n + 1);
	int ans = 0;
	for (int i = 1; i <= n; i++) inv[i] = quick(A[i].r - A[i].l + 1, mo - 2);
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			ans = (ans + 1ll * inv[i] * inv[j] % mo*calc(A[i], A[j])) % mo;
	cout << ans << endl;
	return 0;
}