自动搬运

查看原文

来自洛谷，原作者为

	Chitose_ I never sleep,cause sleep is the cousin of death

搬运于2025-08-24 21:18:43，当前版本为作者最后更新于2025-06-12 20:59:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

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

我们知道在每一轮操作之后两个盒子的球数是不会变化的，于是设一些变量,令 $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;
}