小红的双排列期望（hard）的暴力解法

首先有贪心。概率大的匹配大的数字。

定义 $x_i$ 为从数字 $i$ 到 $n$ 的期望步数。有

x_0 = (1-p)(x_0 + 1) + p(x_1 + 1) \\ x_i = (1-p)(x_{i-1} + 1) + p(x_{i+1} + 1) \qquad (1\le i\lt n)\\ x_n = 0

然后画出矩阵。其中， $x_{n-1} = (1-p)x_{n-2} + 1$ ，省略了一列 $x_n$ 。

\begin{bmatrix} p & -p & 0 & \cdots &&&& 1 \\ p-1 & 1 & -p & 0 & \cdots &&& 1 \\ 0 & p-1 & 1 & -p & 0 & \cdots && 1 \\ 0 & 0 & p - 1 & 1 & -p & 0 & \cdots & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \dots & p - 1 & 1 & 1 \end{bmatrix}

考虑高斯消元。设 $z_i$ 为矩阵的第 $i$ 行，则 $i$ 从 $1$ 到 $n-1$ ，依次执行 $z_{i+1}\gets z_{i+1}-\frac{p-1}{p}z_{i}$ 。

下面的矩阵都是经过上述变换的。

$T_{n}$ 是第 $n$ 行的常数项，则

T_{1} = 1 \\ T_{n} = 1 - \frac{p-1}{p}T_{n-1} = \frac{1-p}{p}T_{n-1} + 1

当 $p = \frac{1}{2}$ ， $T_{n} = T_{n-1} + 1 = n$ 。

否则，你可以通过查公式或换元 $G_{n} = (\frac{p}{1-p})^nT_{n-1} = G_{n-1} + (\frac{p}{1-p})^n$ 来得到 $T_{n} = \frac{1-(\frac{1-p}{p})^n}{1-\frac{1-p}{p}}$ 。

最终， $z_{n}$ 形如

\begin{bmatrix} 0 & 0 & \cdots & p & T_{n} \end{bmatrix}

。

于是 $x_{n-1} = \frac{T_n}{p}$ 。

然后考虑倒推到 $x_0$ 。

$px_{n-2} - px_{n-1} = T_{n-1}$ ，于是 $x_{n-2} = x_{n-1} + \frac{T_{n-1}}{p}$ ，进而 $x_0 = x_{n-1} + \frac{T_{n-1}}{p} + \frac{T_{n-2}}{p} + \cdots + \frac{T_{1}}{p}$ 。

当 $p = \frac{1}{2}$ 时， $x_0 = \frac{1+2+\cdots+n}{p} = \frac{(n+1)n}{2p} = (n+1)n$ 。

否则， $x_0 = \frac{T_1+T_2+\cdots+T_n}{p} = \frac{n - \left[\frac{1-p}{p} + (\frac{1-p}{p})^2 + \cdots + (\frac{1-p}{p})^n\right]}{(1-\frac{1-p}{p})p} = \frac{n-\frac{\frac{1-p}{p}(1-(\frac{1-p}{p})^{n})}{1-\frac{1-p}{p}}}{(1-\frac{1-p}{p})p}$ 。

$O(n\log{n})$

较官解的优点在于不依赖 $1\le b_i\le 100$ 的限制，且复杂度更优。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, l, r) for(int i = (l); i <= (r); ++i)
#define per(i, r, l) for(int i = (r); i >= (l); --i)
const int N = 2e5 + 5, mod = 1e9 + 7;
ll qpow(ll a, ll p) {
	a %= mod;
	ll ans = 1;
	while (p) {
		if (p & 1) ans = ans * a % mod;
		a = a * a % mod;
		p >>= 1;
	}
	return ans;
}
int n, p[N << 1];
ll calc(int p, int n) {
	if (p * 2LL % mod == 1) {
		ll st = 1LL * (n + 1) * n % mod;
		return st;
	}
	ll _p = (1 + mod - p) % mod, ivp = qpow(p, mod - 2);
	ll a = _p * ivp % mod;
	ll st = (n - (1 - qpow(a, n) + mod) % mod * a % mod * qpow((1 - a + mod) % mod, mod - 2) % mod + mod) % mod * qpow((1 - a + mod) % mod, mod - 2) % mod * ivp % mod;
	return st;
}
void Sol() {
	cin >> n;
	rep(i, 1, n * 2) cin >> p[i];
	sort(p + 1, p + n * 2 + 1);
	ll ans = 0;
	rep(i, 1, 2 * n) p[i] = 1LL * p[i] * qpow(100, mod - 2) % mod;
	rep(i, 1, 2 * n) ans = (ans + calc(p[i], (i + 1) / 2)) % mod;
	cout << ans << '\n';
}
int main() {
	cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
	int T = 1;
	while(T--) Sol();
	return 0;
}