题解 P7986 [USACO21DEC] HILO P
ETHANK
·
·
题解
题目难度：USACO P/省选-
不难发现猜 HI 的数不会使猜 LO 的数被跳过。设 y=N-x ，那么原题相当于将 a_1,a_2,\dots,a_x 和 b_1,b_2,\cdots,b_y 排列，只记录 a,b 的每次下标最大值的出现位置，求期望 ba 的数量。
这可以 dp ，设 dp[i][j][0/1] 为当前最大出现 a_i,b_j 以及最后一个出现的是 a/b ，通过简单的转移可以做到 O(N^3) 。前缀和优化可以做到 O(N^2) ，这里不再赘述。
比较吸引我的是在赛后讨论中看到的 O(N) 做法，这里简单的证明一下。
结论：令 H_0=0,H_N=1+\frac{1}{2}+\cdots+\frac{1}{N} . 有
E[\#(ba)]=\frac{1}{2}(H_x+H_y-H_N+\frac{y}{N})\\
证明：
$$
\Delta=\frac12(\frac1{y+1}-\frac{1}{N+1}+\frac{y+1}{N+1}-\frac{y}{N})=\frac{1}{2(y+1)}-\frac{y}{2N(N+1)}
$$
计算对 $a_1a_2\dots a_xb_2b_3\dots b_y$ 的排列中插入 $b_1$ 对答案的贡献， $b_1$ 只能排在第一个出现的 $b$ 之前，否则会被跳过。$y$ 个 $b$ 将 $x$ 个 $a$ 分成 $y+1$ 段，故第一个 $b$ 前 $a$ 的期望个数为 $\frac{x}{y+1}$ 个。设前面有 $k$ 个 $a$ 。
接下来，只要 $b_1$ 被插入在 $k$ 个 $a$ 中最大的 $a$ 前面，都会对期望贡献一个 "ba" 。最大的 $a$ 的期望位置为：
$$
E[index]=\left\{\begin{matrix}
\frac{k+1}2,\qquad k>0\\
0,\qquad k=0\\
\end{matrix}\right.
$$
$k=0$ 即为原排列首项是 $b$ 的概率，为 $\frac{y}{N}$ 。 能得出：
$$
\Delta = \frac{1}{N+1}(\frac{1}{2}\times(\frac{x}{y+1}+1)-\frac{y}{N}\times\frac{0+1}{2})\\
=\frac{1}{2(y+1)}-\frac{y}{2N(N+1)}
$$
```cpp
const int N=2e5+5,P=1e9+7;
int n,x;
ll H[N],inv[N];
int main(){
n=read(),x=read();
inv[1]=1;
ll fac = 1;
rep(i,2,n){
inv[i]=(P-P/i)*inv[P%i]%P;
fac = fac*i%P;
}
rep(i,1,n)H[i]=(H[i-1]+inv[i])%P;
int y = n-x;
cout<<(fac*inv[2]%P*(inv[n]*y%P+H[x]+H[y]-H[n])%P+P)%P;
return 0;
}
```