题目内容

有这样一个二分：

void calc(int s) { 
    double l = a, r = b; int cnt = 0; 
    while(cnt != s) { 
        double mid = (l + r) / 2; 
        if(check(mid)) l = mid; else r = mid; 
        cnt ++;
    } 
    cout << (l + r) / 2; 
}

其中 check 函数被只会随机返回 0 或者 1，其返回 0 和 1 的概率分别为 P0​ 和 P1​，上面的程序只会执行 s 次。现在给定 s,l,r 的初始值 a,b 以及 P0​,P1​，不考虑浮点数误差的情况下，你需要输出 石老板 这个程序输出的答案的 期望值 对于 998244353 取模后的答案是多少。 a可能大于b

解题思路

官方正解是矩阵快速幂（也许是因为这个没超纲？），但是由于我记得wjm学长讲的不是这个，而且矩阵快速幂我也不是很会，所以在网上找了一下，最后找到wjm学长讲的直接推公式的方法。

乘法逆元就不讲了，总之就是用费马小定理再答案对$mod$取模的前提上，将除以一个数变成乘该数的$mod-2$次。

设$g(l,r,s)$ 为进行$s$次操作后的期望。$f(t,s)$ 为当$l$等于$0$ ，r等于 $t$ 时进行s次操作的期望。

显然

$g(l,r,s)=l+g(0,r-l,s)$

$f(t,0)= \dfrac{t}{2}$

所以$g(l,r,s)=l+g(0,r-l,s)=l+f(r-l,s)$

$f(t,s)=p_0 \times f( \dfrac{t}{2} ,s-1)+p_1(\dfrac{t}{2}+f(\dfrac{t}{2},s-1))$

化简可得

$f(t,s)=f(\dfrac{t}{2},s-1)+\dfrac{p_1 t}{2}$

所以最后不断迭代下去，再用一下等比数列求和公式，即可推出最后式子为

$g(l,r,s)=l+\dfrac{t}{2^{s+1}}+p_1t \times \dfrac{2^{s}-1}{2^s}$

就这样没了。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <math.h>
using namespace std;
const int mod=998244353;
long long s,a,b,p0,p1;

long long qmi(long long a,long long b){
    long long res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res%mod;
}
long long inv(long long x){
    return qmi(x,mod-2)%mod;
}
int main(){
    cin>>a>>b>>s>>p0>>p1;
    if(a>b){
        swap(a,b);
        swap(p0,p1);
    }
    a=a%mod;
    b=b%mod;
    long long l=b-a;
    p0=p0*qmi(100,mod-2)%mod;
    p1=p1*qmi(100,mod-2)%mod;
    printf("%lld",((a+l%mod*inv(qmi(2,s+1))%mod)%mod+(((p1*l%mod)*((qmi(2,s)-1)%mod))%mod)*inv(qmi(2,s))%mod)%mod);
}