当前位置: 代码迷 >> 综合 >> [2020 年百度之星·程序设计大赛 - 复赛] Battle for Wosneth 期望+逆元
  详细解决方案

[2020 年百度之星·程序设计大赛 - 复赛] Battle for Wosneth 期望+逆元

热度:64   发布时间:2024-02-09 01:12:20.0

题目链接:Battle for Wosneth

题意

中文题意不多解释

题解

A先手,B后手我们可以列一个表格。

[ p q p q . . . . . . p ( 1 ? p ) ( 1 ? q ) ( 1 ? p ) ( 1 ? q ) . . . . . . ( 1 ? p ) ] { \begin{bmatrix} p & q & p & q & ...... p\\ (1-p) & (1-q) & (1-p) & (1-q) & ...... (1-p)\\ \end{bmatrix} }

我们求的是A生命值的期望变化,等B被A打死后才停止计算。

首先我们可以知道A打中B的期望为p*1,那么B被A打的次数的期望为(m/p)。

由上面的表格可以看出,当A有(m/p)次命中,那么有(m/p-1)个完整的回合,因为在最后一个回合中B被打死了(不算一个完整的回合)。我们可以算出,每个完整的回合中A的生命期望为(p-q),那么(m/p-1)个回合的生命期望为(m/p-1)*(p-q),最后一次A打死了B,A的生命期望为p。

可以求出A的生命总期望为: (m/p-1)*(p-q)+p
由于p,q此时为百分比,并且要求取模需要用到逆元,所以整合下来公式为:
[ m ? p ? i n v ( 100 ) ] ? ( p ? q ) ? i n v ( p ) + p ? i n v ( 100 ) i n v {[m-p*inv(100)]*(p-q)*inv(p)+p*inv(100)(inv为逆元)}
注意期望虽然有可能是负数,但是取模后一定不能为负数,所以最后一定(ans+mod)%mod。

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
//extern "C"{void *__dso_handle=0;}
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define lowbit(x) x&-xconst double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=998244353;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
const int maxm=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll qpow(ll a,ll b)
{ll ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}
ll inv(ll n)
{ return qpow(n, mod-2); }
ll gcd(ll a,ll b)
{return b==0?a:gcd(b,a%b);
}
int main()
{int t;scanf("%d",&t);while(t--){ll m,p,q;scanf("%lld%lld%lld",&m,&p,&q);ll ans=((((m-p*inv(100))*(p-q)%mod)*inv(p)%mod+p*inv(100)%mod)%mod+mod)%mod;printf("%lld\n",ans);}
}
  相关解决方案