2022牛客多校十 H-Wheel of Fortune（概率+组合）

题目链接：登录—专业IT笔试面试备考平台_牛客网

题目：

 样例1输入：

30 5 0 0 0 0 0 0
30 5 0 0 0 0 0 0

样例1输出：

499122177

样例2输入：

10 0 0 0 0 0 0 0
11 0 0 0 0 0 0 0

样例2输出：

748683265

简化题意：两个将领，一个是A，一个是B，每个将领带领若干个小兵，每个将领带的小兵个数最多有七个，每个人物有一个初始血量，然后每秒随机选择一个人物扣10滴血，可能是将领也可能是小兵，如果A将领比B将领先死那么A将领失败，否则获胜。求A将领获胜的概率。

分析：其实这道题目跟小兵的血量以及个数是没有关系的，因为小兵的作用只是降低一开始将领的中枪概率，但是在两个将领均存活阶段两个将领的中枪概率始终是相同的，所以小兵只会延长将领死去的时间，但不会影响将领死亡的顺序，也就是说不会对概率造成影响，所以我们一开始直接看成只有两个将领即可，每个将领减10滴血的概率均为1/2，假如A将领经过t1次攻击后会死，B将领经过t2次攻击后会死，那么我们就枚举B将领遭受t2-1次攻击时A将领遭受的攻击次数即可，最后直接再让B将领遭受一次攻击，其中若想要A将领获胜，则B将领遭受t2-1次攻击时A将领遭受的攻击次数的范围为0~t1-1，假如A将领遭受了x次攻击，那么就一共有x+tb-1次攻击，其中每种方案的概率都是1/(2^(x+tb-1)),这种方案的方案数有C(x+tb-1,tb-1)，最后还需要直接攻击B将领一次，概率为1/2.那么对应的概率贡献就是C(x+tb-1,tb-1)*qpow(p2[x+tb],mod-2)，那么我们枚举一下每个方案的概率就可以求得所有B将领死在A将领前面的方案概率和了。

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=2e7+10,mod=998244353;
typedef long long ll;
ll fac[N],inv[N],p2[N];
ll qpow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
ll C(ll a,ll b)
{
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int main()
{
	long long a,b,t;
	cin>>a;
	for(int i=1;i<=7;i++)
		cin>>t;
	cin>>b;
	for(int i=1;i<=7;i++)
		cin>>t;
	ll ta=(a-1)/10+1,tb=(b-1)/10+1;
	inv[0]=fac[0]=p2[0]=1;
	for(int i=1;i<=ta+tb;i++)
	{
		fac[i]=fac[i-1]*i%mod;
		p2[i]=p2[i-1]*2%mod;
	}
	inv[ta+tb]=qpow(fac[ta+tb],mod-2);
	for(int i=ta+tb-1;i>=1;i--)
		inv[i]=inv[i+1]*(i+1)%mod;
	ll ans=0;
	for(int i=0;i<ta;i++)
		ans=(ans+C(i+tb-1,tb-1)*qpow(p2[i+tb],mod-2)%mod)%mod;
	cout<<ans;
	return 0;
}