「TAOI-1」拼凑的断音 题解

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