自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:46:27，当前版本为作者最后更新于2023-04-16 11:21:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

比赛结束前 $13$ 分钟登陆做题，$8$ 分钟解决完这一题就润去 CF 了……

解法

本题需要一些计算期望值的数学基础。

考虑哪些数最终可能成为最大值：显然，数 $x$ 只有满足 $x+s\ge \max\limits_{i=1}^n{a_i}$ 实施了魔法后才可能成为最大值。

于是，我们可以得到这样一个算法流程：

• 将整个数列 $a$ 降序（从大到小）排序，令 $c$ 为期望值；

• 对于 $i=1,2,\ldots,n$，执行如下算法：

  • 如果 $a_i+s\ge a_1$，那么有 $\left(1-\dfrac{p}{q}\right)^{i-1}$ 的概率这个数前面的数都没有实施魔法，然后在这个前提条件下，这个数成为最大的数的概率是 $\left(1-\dfrac{p}{q}\right)^{i-1}\dfrac{p}{q}$，$c\leftarrow c+\left(1-\dfrac{p}{q}\right)^{i-1}\dfrac{p}{q}(a_i+s)$；
  • 否则，这个数不可能成为最大数，退出循环；

• 计算出除了上面所有情况的概率和，剩下的所有情况中最大值就是原来的最大值 $a_1$，$c$ 加上该情况的期望即可。

具体实现中可以使用一个变量 $w$ 来维护流程中“前面的数都没有实施魔法”的概率。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=r%mod*a%mod;
    a=a%mod*a%mod; b>>=1;
  }
  return r;
} // 快速幂，用于计算逆元
main(){
  ios::sync_with_stdio(false);
  int n,p,q,s,c=0,w=1; cin>>n>>p>>q>>s;
  (p*=qpow(q,mod-2))%=mod; vector<int> a(n);
  for(auto &i:a)cin>>i;
  sort(a.begin(),a.end(),greater<int>()); // 降序排序
  for(int i:a){
    if(i+s<a[0])break; // 该数不可能成为答案，退出循环
    (c+=w*p%mod*(i+s)%mod)%=mod; // 维护期望值
    (w*=(mod+1-p)%mod)%=mod; // 维护概率
  } // 执行算法流程
  cout<<"2\n"<<(c+w*a[0]%mod)%mod<<endl;
  return 0;
}