〈 TREEのOI 2022 Spring 〉Absolutely Simple Game

Luogu

IDLGP8307

Time500ms

Memory128MB

DifficultyP4

博弈论O2优化概率论逆元

初始时给定范围 $[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 的胜率。 ## Input 一行一个整数 $n$。 ## Output 一行一个整数，表示 rin 的胜率，按分数 $\bmod~998244353$ 输出。 [samples] ## Background rin 和 len 在玩一个绝对简单的游戏，pcq 为裁判。 ## Note **样例解释1：** rin 的胜率为 $\dfrac 23$（一开始猜 $2$），$\bmod~998244353$ 后输出为 $665496236$。 *** **本题采用 SubTask 捆绑测试。** | SubTask 编号 | 分值 | 特殊限制 | | :-----------: | :-----------: | :-----------: | | $0$ | $10$ | $n\equiv 0\ \pmod 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}$。 --- **如何对有理数取模？** $\dfrac {x}{y} \bmod m$ 定义为 $xy^{m-2}\bmod~m$。 $m$ 必须为质数。保证答案约分后分母不为 $998244353$ 的倍数。

Samples

Input #1

Output #1

665496236

API Response (JSON)

{
  "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 两人均...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments