{"problem":{"name":"〈 TREEのOI 2022 Spring 〉Absolutely Simple Game","description":{"content":"初始时给定范围 $[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 两人均","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8307"},"statements":[{"statement_type":"Markdown","content":"初始时给定范围 $[l,r]=[1,n]$，pcq 从中均匀随机选出一个自然数 $t$，之后 rin 和 len 两人轮流进行操作，rin 先行。\n\n每次操作方猜测一个整数 $x\\in[l,r]$，若 $x=t$，则游戏结束，该方负；若 $x<t$，则调整范围 $[l,r]$ 为 $[x+1,r]$；若 $x>t$，则调整范围 $[l,r]$ 为 $[l,x-1]$。\n\nrin 和 len 两人均充分了解规则且无比可爱聪明（都会最大化自己的胜率），过程中谁都知道场上除了 $t$ 以外的一切信息，求 rin 的胜率。\n\n## Input\n\n一行一个整数 $n$。\n\n## Output\n\n一行一个整数，表示 rin 的胜率，按分数 $\\bmod~998244353$ 输出。\n\n[samples]\n\n## Background\n\nrin 和 len 在玩一个绝对简单的游戏，pcq 为裁判。\n\n## Note\n\n**样例解释1：**  \n\nrin 的胜率为 $\\dfrac 23$（一开始猜 $2$），$\\bmod~998244353$ 后输出为 $665496236$。\n\n***\n\n**本题采用 SubTask 捆绑测试。**\n\n| SubTask 编号 | 分值 | 特殊限制 |\n| :-----------: | :-----------: | :-----------: |\n| $0$ | $10$ | $n\\equiv 0\\ \\pmod 2$ |\n| $1$ | $20$ | $n\\le 100$ |\n| $2$ | $30$ | $n\\le 10^9$ |\n|$3$|$40$|$n\\le 10^{18}$|\n\n对于 $100\\%$ 的数据，$1 \\le n\\le 10^{18}$。\n\n---\n**如何对有理数取模？**  \n\n$\\dfrac {x}{y} \\bmod m$ 定义为 $xy^{m-2}\\bmod~m$。\n\n$m$ 必须为质数。  \n\n保证答案约分后分母不为 $998244353$ 的倍数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8307","tags":["博弈论","O2优化","概率论","逆元"],"sample_group":[["3","665496236"]],"created_at":"2026-03-03 11:09:25"}}