"蔚来杯"2022牛客暑期多校训练营10 Wheel of Fortune

原题题面：https://ac.nowcoder.com/acm/contest/33195/H

题目大意：

你的血量为 $A (A > 0)$ ,拥有最多7个随从，血量分别为 $a_{1}, a_{2}, a_{3} \dots a_{7} (a_{i} > = 0, 若随从不存在则 a_{i} = 0) a_1,a_2,a_3…a_7(a_i>=0,若随从不存在则a_i=0)$

同样，你的对手的血量为 $B (B > 0)$ ,拥有最多7个随从，血量分别为 $b_{1}, b_{2} \dots b_{7} (b_{i} > = 0, 若随从不存在则 b_{i} = 0) b_1,b_2…b_7(b_i>=0,若随从不存在则b_i=0)$

现在触发了燃烧之路，其效果等价于以下随机过程：

：重复以下操作直到 $A < = 0 或 B < = 0$ ：从 $A, B, a_{1} \dots a_{7}, b_{1}, b_{2} \dots b_{7} A,B,a_1…a_7,b_1,b_2…b_7$ 中随机选择一个大于 $0$ 的元素 $x$ ,然后让 $x = x - 10$

如果 $B < = 0$ ,则你获胜，否则你的对手获胜

求你获胜的概率

分析:

因为在题目中，我们只需关心 $A, B$ 的血量，无需知道 $a, b$ 数组的血量,随机抽到一名随从相当于没抽，所以随从可以忽略

接下来，考虑 $A, B$ （以下已忽略随从）

不妨设 $a$ 为 $A$ 死亡前要被攻击的次数, 设 $b$ 为 $B$ 死亡前要被攻击的次数

若A胜利，那么轮数定在 b至a+b-1之间

接下来寻找规律：

若结束在b轮：概率为 $\frac{1}{2^b}$

若结束在b+1轮：概率为 $\frac{C_{b}^{b-1}}{2^b}*\frac{1}{2}=\frac{C_{b}^{b-1}}{2^{b+1}}$

若结束在b+2轮：则概率为 $\frac{C_{b+1}^{b-1}}{2^{b+1}}*\frac{1}{2}=\frac{C_{b+1}^{b-1}}{2^{b+2}}$

……… 以此类推

故有 $A$ 获胜的概率

$P=\sum^{a-1}_{i=0}\frac{C^{b-1}_{b+i-1}}{2^{b+i}}$

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL Mod=998244353;

const int MXN=4e6+7;
const int MXN2=4e6+100;
LL fac[MXN2],ifac[MXN2];

LL qpow(LL x,LL times){
	LL ret=1ll,tmp=x%Mod;
	while(times){
		if(times&1) ret=ret*tmp%Mod;
		tmp=tmp*tmp%Mod;
		times>>=1;
	}
	return ret;
}

void init(){
	fac[0]=1; ifac[0]=1;
	for(int i=1;i<=MXN;i++){
		fac[i]=(fac[i-1]*i)%Mod;
		//printf("%lld\n",fac[i]);
	}
	ifac[MXN]=qpow(fac[MXN],Mod-2);
    for(int i=MXN-1;i>=1;i--){
    	ifac[i]=ifac[i+1]*(i+1)%Mod;
    }
	//for(int i=1;i<=10;i++) printf("%lld\n",ifac[i]);
}




LL C(int x,int y){
	if(x==y) return 1;
	return 1ll*(fac[x]*ifac[y]%Mod*ifac[x-y])%Mod;
}
int main(){
	LL a,b,x; LL k;
	init();
	for(int i=1;i<=8;i++){
		scanf("%lld",&x);
		if(i==1){
			a=(x-1)/10+1;
		}
	}
	for(int i=1;i<=8;i++){
		scanf("%lld",&x);
		if(i==1) {
			b=(x-1)/10+1;
		}
	}
	LL ans=0;
	for(int i=0;i<a;i++){
		k=qpow(2ll,(LL)b+i);
		ans=(ans+(C(b+i-1,b-1)*qpow(k,Mod-2)%Mod))%Mod;
	}
	printf("%lld\n",ans);
}