题解：B4337 [中山市赛 2023] 简单数学题

· · 题解

首先，从第一个盒子里抽出白球的概率可以转化为从第一个盒子里白球的期望个数在除以第一个盒子的总球数。

我们知道在每一轮操作之后两个盒子的球数是不会变化的，于是设一些变量,令 A 为第一个盒子的总球数，令 B 为第二个盒子的总球数，T 为白球总数。即：

A=a_1+a_2,B=b_1+b_2,T=a_1+b_1

我们设 x_i 为经过 i 轮操作后第一个盒子里白球的期望个数，则 x_0=a_1。在每次操作中，第一个盒子中白球的期望个数是上一轮留下的，加上从第二个盒子中取出来的，因此我们有以下递推式：

x_i=(x_{i-1}-\frac{x_{i-1}}{A})+\frac{T-\frac{A-1}{A} \cdot x_{i-1}}{B+1}

化简得：

x_i=\frac{(A-1) \cdot B}{A \cdot (B+1)} \cdot x_{i-1}+\frac{T}{B+1}

为了方便，我们令 p=\frac{(A-1) \cdot B}{A \cdot (B+1)}，令 q=\frac{T}{B+1}。

由于 p 和 q 均为常数，所以可以提前预处理出来他们的值，就得到了 O(n+\log{n}) 的算法，可以获得 80pts 的高分。可以看出这是一个形如 x_i=px_{i-1}+q 的递推式，我们可以写几个找找规律：

x_1=px_0+q\\ x_2=px_1+q=p^2x_0+qp+q\\ x_3=px_2+q=p^3x_0+qp^2+qp+q\\ x_4=px_3+q=p^4x_0+qp^3+qp^2+qp+q\\ \cdots\\ x_i=p^ix_0+qp^{i-1}+qp^{i-2}+ \cdots +qp+q

这里我们可以将 q 提出来，即 x_i=p^ix_0+q\sum_{i=0}^{n-1}p^i，根据等比数列公式可以写成 x_i=p^ix_0+q \cdot \frac{p^n-1}{p-1}，那么答案即为 \frac{x_n}{A}，时间复杂度为 O(\log{n})，可以通过。

AC代码：

#include<bits/stdc++.h>
#define db double
#define rg register
#define pb push_back
#define pob pop_back
#define pii pair<int,int>
#define vi vector<int>
#define fr first
#define sc second
#define endl '\n'
#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=998244353;

int read() {
    int f=1,x=0;
    char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }while(isdigit(c)) {
        x=(x<<1)+(x<<3)+(c-'0');
        c=getchar();
    }return x*f;
}

int n,a1,a2,b1,b2;
int A,B,T,now,p,q;
int qpow(int x,int a) {
    int res=1;
    while(a) {
        if(a&1) res*=x,res%=mod;
        x*=x,x%=mod,a>>=1;
    } return res;
}

signed main() {
    n=read(),a1=read()%mod,a2=read()%mod,b1=read()%mod,b2=read()%mod;
    A=(a1+a2)%mod,B=(b1+b2)%mod,T=(a1+b1)%mod;
    p=(A-1)*B%mod*qpow(A,mod-2)%mod*qpow(B+1,mod-2)%mod,q=T*qpow(B+1,mod-2)%mod;
    now=a1;
    now=qpow(p,n)*a1%mod;
    now+=(qpow(p,n)-1+mod)*q%mod*qpow(p-1,mod-2)%mod;
    cout<<now*qpow(A,mod-2)%mod<<"\n";
    return 0;
}