P8307 〈 TREEのOI 2022 Spring 〉Absolutely Simple Game

题目背景

rin 和 len 在玩一个绝对简单的游戏，pcq 为裁判。

题目描述

初始时给定范围 $[l,r]=[1,n]$，pcq 从中均匀随机选出一个自然数 $t$，之后 rin 和 len 两人轮流进行操作，rin 先行。

每次操作方猜测一个整数 $x\in [l,r]$，若 $x=t$，则游戏结束，该方负；若 $x<t$，则调整范围 $[l,r]$ 为 $[x+1,r]$；若 $x>t$，则调整范围 $[l,r]$ 为 $[l,x-1]$。

rin 和 len 两人均充分了解规则且无比可爱聪明（都会最大化自己的胜率），过程中谁都知道场上除了 $t$ 以外的一切信息，求 rin 的胜率。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示 rin 的胜率，按分数 $\mathrm{mod}998244353$ 输出。

输入输出样例 #1

输入 #1

3

输出 #1

665496236

说明/提示

样例解释1：

rin 的胜率为 $\frac{2}{3}$（一开始猜 $2$），$\mathrm{mod}998244353$ 后输出为 $665496236$。

---

本题采用 SubTask 捆绑测试。

SubTask 编号	分值	特殊限制
$0$	$10$	$n\equiv 0(\mathrm{mod}2)$
$1$	$20$	$n\le 100$
$2$	$30$	$n\le 10^9$
$3$	$40$	$n\le 10^{18}$

对于 $100\%$ 的数据，$1\le n\le 10^{18}$。

---

如何对有理数取模？

$\frac{x}{y}\mathrm{mod}m$ 定义为 $x{y}^{m-2}\mathrm{mod}m$。

$m$ 必须为质数。

保证答案约分后分母不为 $998244353$ 的倍数。

C++实现

#include<bits/stdc++.h>
#define mod 998244353
#define ll unsigned long long
using namespace std;

ll n;

ll mult(ll a,ll b){ //快速乘法
    if(!b)return 0;
    if(b==1)return a;
    if(b&1)return (mult(a,b-1)+a)%mod;
    return 2*mult(a,b/2)%mod;
}

ll power(ll a,ll b){ //快速幂
    if(b==1)return a;
    if(!b)return 1;
    if(b&1)return mult(power(a,b-1),a)%mod;
    ll buf=power(a,b/2);
    return mult(buf,buf)%mod;
}

int main(){
    cin>>n;
    ll m=power(n,mod-2); //n的逆元
    if(n%2==0)cout<<499122177<<endl;  //这玩意儿就是0.5取模
    else if(n%4==1)
		cout<<mult((n-1),499122177)%mod*m%mod<<endl;
    else if(n%4==3)
		cout<<mult(n+1,499122177)%mod*m%mod<<endl;
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容