给定编号为 \(1,2,\cdots,2n\) 的 \(2n\) 张卡片，首先将其随机打乱成两堆，各 \(n\) 张卡片。你每次操作选择不超过两堆卡片数的正整数 \(k\)，比较两堆的第 \(k\) 张卡片的编号大小，将较小的扔掉。求操作数最小值的期望值\(\bmod(10^9+7)\)。
\(n\le 10^6\)。
不妨设 \(2n\) 在牌堆 \(B\) 中，则最后的目标是将 \(A\) 删空。
结论：设 \(d=\max\limits_{i=1}^n\min\{j-i\mid A_i<B_j\}\)，则答案为 \(n+d\)。
证明：首先答案 \(\ge n+d\)，因为在删去 \(A_i\) 之前一定要把 \(B_i,B_{i+1},\cdots,B_{j-1}\) 都删掉。并且操作次数可以取到 \(n+d\)：若当前 \(d=0\) 则每次选最大的 \(i\) 使得 \(A_i<B_i\)，将 \(A_i\) 删掉，否则选择最小的 \(i\) 使得 \(\min\{j-i\mid A_i<B_j\}=d\) 然后将 \(B_i\) 删掉。
然后要计算期望。由于 \(d\) 是 \(\max\) 的形式，考虑设 \(p(d)\) 表示答案 \(\le n+d\) 的概率，则答案为 \(2n-\sum_{i=0}^{n-1}p(i)\)。
考虑计算 \(p(d)\)，要求满足的条件即为 \(B_1,B_2,\cdots,B_{\min\{n,i+d\}}\) 中至少有一个 \(>A_i\)。
按从后往前的顺序确定 \(A_i\)，要求 \(A_1,A_2,\cdots,A_{i-1},B_1,B_2,\cdots,B_{\min\{n,i+d\}}\) 至少有一个 \(>A_i\)，此时每一步独立，把概率乘起来就得到：
预处理双阶乘及其逆元就可以 \(O(n)\) 算答案啦:)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6 + 5, mod = 1e9 + 7;
int n, fac[N], inv[N], ans;
int ksm(int a, int b){
int res = 1;
for(;b;b >>= 1, a = (LL)a * a % mod)
if(b & 1) res = (LL)res * a % mod;
return res;
} void qmo(int &x){x += x >> 31 & mod;}
void init(int m){
fac[0] = fac[1] = 1;
for(int i = 2;i <= m;++ i)
fac[i] = (LL)fac[i-2] * i % mod;
inv[m] = ksm(fac[m], mod-2);
inv[m-1] = ksm(fac[m-1], mod-2);
for(int i = m;i >= 2;-- i)
inv[i-2] = (LL)inv[i] * i % mod;
}
int main(){
scanf("%d", &n); init(n<<1); ans = (LL)fac[(n<<1)-1] * inv[n-1<<1] % mod;
for(int d = 1;d < n;++ d)
ans = (ans + (LL)fac[(n<<1)-d-1] * inv[(n-1<<1)-d] % mod * inv[d-1] % mod * fac[d]) % mod;
qmo(ans = 2*n - (LL)ans * ksm(n, mod-2) % mod); printf("%d\n", ans);
}
AGC053C Random Card Game【概率，分析性质】
原文：https://www.cnblogs.com/AThousandMoons/p/14685873.html