自动搬运

查看原文

来自洛谷，原作者为

	ETHANK 「我是星 我愿投身前途未卜的群星，为梦长明。」

搬运于2025-08-24 22:34:55，当前版本为作者最后更新于2021-12-26 06:52:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目难度：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})\\$$

证明：

$x=0$ 或 $y=0$ 时结论显然成立，不妨对 $y$ 归纳。即证 $(x,y)\to(x,y+1)$ 后期望的变化为：

$$\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)} $$

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;
}