用户工具

站点工具


2020-2021:teams:legal_string:组队训练比赛记录:contest15
   [[https://ac.nowcoder.com/acm/contest/11260|比赛链接]]

补题情况

题目 蒋贤蒙 王赵安 王智彪
A 0 0 0
B 0 0 0
C 2 0 0
D 0 0 0
F 0 0 0
G 0 0 0
I 0 0 2
J 0 0 2

题解

I. Incentive Model

题意

有两个人争夺 $n$ 个物品,每一轮争夺一个物品,每次争夺都有成功概率。给定 $x,y$ 代表初始双方的 $stake$ 分别为 ${\frac x y}$ 和 $1-{\frac x y}$ ,每次争夺双方成功概率为自己的 $stake$ 比双方相加的 $stake$ ,然后每一轮如果第一个人获胜,他之后的 $stake$ 要加上 $w$ ,问第一个人争夺成功轮数的期望,结果对 $998244353$ 取模。

题解

我们设对于第一个人,第 $i$ 轮获胜的概率为 $X^{i}$ ,第 $i$ 轮的 $stake$ 期望为 $S_{i}$ 。

我们有 $S_{0}={\frac x y}$

然后我们有 $X_{i+1}={\frac {S_{i}} {1+w×i}}$ , $S_{i+1}=S{i}+w×X_{i+1}$

所以有 $S_{i+1}=S_{i}+w×({\frac {S_{i}} {1+w×i}})=S_{i}×(1+{\frac w {1+w×i}})=S_{i}×{\frac {1+(i+1)×w} {1+i×w}}$

所以有 ${\frac {S_{i+1}} {1+(i+1)×w}}={\frac {S_{i}} {1+i×w}}=…={\frac {S_{0}} {1+0×i}}={\frac x y}$

所以有 $S_{n}={\frac x y}×(1+n×w)$

又因为获胜轮数可以表示为 ${\frac {S_{n}-{\frac x y}} {w}}$

所以化简得到答案为 ${\frac x y}×n$

代码

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int qpow(int a,int b,int m=mod) {
	int r=1;
	while(b) {
		if (b&1) r=r*a%m;
		a=a*a%m,b>>=1;
	}
	return r;
}
int n,x,y,w;
#undef int
 
int main() {
	scanf("%lld %lld %lld %lld",&n,&w,&x,&y);
	printf("%lld\n",n*x%mod*qpow(y,mod-2)%mod);
	return 0;
}
2020-2021/teams/legal_string/组队训练比赛记录/contest15.1629010239.txt.gz · 最后更改: 2021/08/15 14:50 由 王智彪