[THUPC 2023 初赛] 欺诈游戏

Luogu
IDLGP9142
Time1000ms
Memory512MB
DifficultyP5
递推博弈论2023O2优化THUPC
这个游戏名叫《走私游戏》。游戏规则大概是这样的:一名玩家扮演走私者,一名玩家扮演检察官。走私者可以将 $x$ 日元($x$ 为 $[0,n]$ 内的整数,由走私者决定)秘密放入箱子中,而检查官需要猜测箱子中的金额。假设检察官猜了 $y$($y$ 也必须是整数)。如果 $x=y$,则走私失败,走私者一分钱也拿不到。如果 $x>y$,则走私成功,走私者可以从检查官那里拿走 $x$ 日元。如果 $x<y$,则走私失败,但是由于冤枉检察官需要赔付给走私者 $y/2$ 日元。游戏分有限回合进行。双方轮流做走私者和检察官。 可以证明,最优情况下每个回合走私者会采用同一种策略,检察官也会采用同一种策略。小 E 想知道在一个回合中,双方的最优策略分别是什么。 ## Input 一行一个正整数 $n$。 ## Output 输出两行,每行 $n+1$ 个数,其中第 $i$ 个表示放/猜 $i-1$ 日元的概率。 第一行输出走私者的策略,第二行输出检察官的策略。 你需要保证,在一方的策略不变的情况下,另一方无论如何改变自己的策略,都不能使自己的期望收益比原来多。 可以证明,这样的策略是唯一的。 答案对 $998244353$ 取模。 [samples] ## Background 在《LIAR GAME》中,小 E 看到了一个有趣的游戏。 ## Note #### 样例解释 1 这 $4$ 个数分别为 $2/3,1/3,1/3,2/3$。 #### 子任务 保证 $1\le n \le 400000$。 #### 题目来源 来自 2023 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2023)初赛。 题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。
Samples
Input #1
1
Output #1
665496236 332748118
332748118 665496236
API Response (JSON)
{
  "problem": {
    "name": "[THUPC 2023 初赛] 欺诈游戏",
    "description": {
      "content": "这个游戏名叫《走私游戏》。游戏规则大概是这样的:一名玩家扮演走私者,一名玩家扮演检察官。走私者可以将 $x$ 日元($x$ 为 $[0,n]$ 内的整数,由走私者决定)秘密放入箱子中,而检查官需要猜测箱子中的金额。假设检察官猜了 $y$($y$ 也必须是整数)。如果 $x=y$,则走私失败,走私者一分钱也拿不到。如果 $x>y$,则走私成功,走私者可以从检查官那里拿走 $x$ 日元。如果 $x<y",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9142"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "这个游戏名叫《走私游戏》。游戏规则大概是这样的:一名玩家扮演走私者,一名玩家扮演检察官。走私者可以将 $x$ 日元($x$ 为 $[0,n]$ 内的整数,由走私者决定)秘密放入箱子中,而检查官需要猜测箱子中的金额。假设检察官猜了 $y$($y$ 也必须是整数)。如果 $x=y$,则走私失败,走私者一分钱也拿不到。如果 $x>y$,则走私成功,走私者可以从检查官那里拿走 $x$ 日元。如果 $x<y...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments