NC251500 coin

简介: NC251500 coin

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

来源:牛客网

 

题目背景

假如我那时握住的不是硬币,而是 ...

题意简述

Rikka 和 Yuuta 在玩游戏,每一次他们会抛一枚硬币,正面向上的概率是 p,反面向上的概率是 1−p。若硬币掷出正面,那么这局 Rikka 获胜,否则 Yuuta 获胜。


在任意时刻,如果存在一个时间段,使得在该时间段内某个人比另个人多获胜 nnn 次,那么这个人赢得游戏,游戏结束。(例如 n=3,硬币掷出 反反正正反正正,在时刻 7 Rikka 获胜)


求出 Rikka 获胜的概率。

输入描述:

第一行一个整数 T,表示询问组数。


接下来 T 行,每行两个整数 n,p 表示一组询问。


输出描述:

输出 T行,每行一个整数表示答案在模 998244353 意义下的值,可以证明答案在模意义下存在。

示例1

输入

复制

2

233 634336464

59093912 743410448

输出

复制

60595366

392543410

备注:

T≤3×10^5,2≤n<9982443532,0≤p<998244353。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=300001;
const ll mod=998244353;
ll qpow(ll a,ll b){
  ll ans=1;
  if(b==0)
  return 1;
  if(b%2)
  ans=a;
  ll t=qpow(a,b/2);
  return t*t%mod*ans%mod;
}
ll inv(ll a){
  return qpow(a,mod-2);
}
void solve(){
  ll n,p;
    cin>>n>>p;
    ll q=(mod+1-p)%mod;
    ll s=p*inv(q)%mod;
    s=inv(s);
    if(s==1){
        cout<<inv(2)<<'\n';
        return;
    }
    ll ans=n*qpow(s,n)%mod*(s-1)%mod*inv(qpow(s,n+1)-1)%mod*inv(qpow(s,n)-1)%mod;
    ll ans2=inv(qpow(s,n+1)-1)%mod;
    ans=(ans-ans2+mod)%mod;
    cout<<ans;
    cout<<'\n';
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t0;
  cin>>t0;
  for(int t=0;t<t0;t++){
    solve();
  }
}

目录
相关文章
|
7月前
Leetcode 377. Combination Sum IV
赤裸裸的完全背包,属于动态规划的范畴,大家有兴趣可以在网上搜索下其他资料。个人觉得动态规划还是比较难理解的,更难给别人讲清楚,所以这里我直接附上我的代码供大家参考。
31 0
|
1月前
NC253077:小沙的悬崖
NC253077:小沙的悬崖
20 0
|
9月前
NC14301 K-th Number
NC14301 K-th Number
|
9月前
NC21874 好串
NC21874 好串
|
9月前
NC14662 小咪买东西
NC14662 小咪买东西
|
9月前
NC15173 The Biggest Water Problem
NC15173 The Biggest Water Problem
|
9月前
NC18979 毒瘤xor
NC18979 毒瘤xor
Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) D2
Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) D2
61 0
LeetCode 377. Combination Sum IV
给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。
78 0
LeetCode 377. Combination Sum IV
Tian Ji -- The Horse Racing 田忌赛马
Tian Ji -- The Horse Racing 田忌赛马
227 0