自动搬运

查看原文

来自洛谷，原作者为

	Tiffake The King Or The Fool|穷途末路的旷野|食无足怒无故贪不知足，岂无妒惰无睹色空前路

搬运于2025-08-24 23:17:14，当前版本为作者最后更新于2025-05-06 15:27:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

出题人题解。

Sub1 显然答案为 $\frac{n}{n+m}$。
Sub2 是给深搜的，枚举每个盒子怎么放即可。
所以从 Sub3 开始讲。

Subtask #3

假设其中一个盒子共放置 $s$ 个棋子，其中有 $x$ 个黑子时概率最大。我们有 $\frac{n-x}{n+m-s}+\frac{x}{s}\le \frac{n-1}{n+m-1}+1$，因此一个盒子放一个黑子，剩下的放另一个盒子概率最大。

Subtask #4

考虑能否从 Sub3 的结论拓展，尽量每个黑子都只放一个盒子，正确性是肯定的。
每个盒子最多只能为答案提供 $\frac{1}{a_1}$ 的贡献，一个黑子显然也是如此。而一个黑子如果选择和 $x$ 个黑子，$y$ 个白子放在一起只会为答案贡献 $\frac{1}{a_1}(\frac{x+1}{x+y+1}-\frac{x}{x+y})$，不如单独放一个盒子。

Subtask #5

现在，我们需要考虑有嵌套的情况。由于一开始我们已经选择了一些盒子只放黑子，现在在第二层的角度上完全可以把它们当作黑子，因为只要摸到它们就一定会摸到黑子。接下来就可以像之前一样放了。若 $n$ 大于了 $a_1$，需要注意维护一个既有白子也有黑子的盒子，在第二层时把它当作白子即可（当然概率是要算其中黑子的）。

Subtask #6

我们把 $k$ 层分成两部分，一部分是 $a_i>n$，这时没有黑子和白子放在一起；另一部分黑子和白子会放在一起，注意算有白子的盒子的贡献。然后注意判断当前在哪部分就行了。时间复杂度 $O(k)$，如果一直用费马小定理算逆元会多一个 $\log$，不一定可过，可以先预处理所有逆元降低复杂度。
当然，也可以用递归分治处理，不过空间复杂度较高，不宜 #define int long long。

Subtask #7

现在我们不能开数组预处理，但是可以把它压成一个变量，只需要单独维护分子和分母就行了。
这个 Sub 的意义是用来卡掉一些奇怪做法的。

Code

#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
const ll mod=998244353;
ll n,m,cn,cm,a,k,d,x;
inline ll inv(ll n){
	ll res=1,m=mod-2;
	while(m){
		if(m&1)res=res*n%mod;
		n=n*n%mod,m>>=1;
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k>>a>>d>>x;
	for(int i=1;i<=k;i++){
		if(a>n)m=a-n-!!cn;
		else
			if(m)cn=n-a+1,cm=m,n=a-1,m=0;
			else cn=((cn+cm)%mod*(n-a+2)%mod-cm+mod)%mod,n=a-1;
		a=a-d^x;
	}
	if(cn)cout<<(cn+(cn+cm)*n%mod)%mod*inv((cn+cm)*(n+1)%mod)%mod;
	else cout<<n*inv(n+m)%mod;
	return 0;
}