{"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$，则走私失败，但是由于冤枉检察官需要赔付给走私者 $y/2$ 日元。游戏分有限回合进行。双方轮流做走私者和检察官。\n\n可以证明，最优情况下每个回合走私者会采用同一种策略，检察官也会采用同一种策略。小 E 想知道在一个回合中，双方的最优策略分别是什么。\n\n## Input\n\n一行一个正整数 $n$。\n\n## Output\n\n输出两行，每行 $n+1$ 个数，其中第 $i$ 个表示放/猜 $i-1$ 日元的概率。\n\n第一行输出走私者的策略，第二行输出检察官的策略。\n\n你需要保证，在一方的策略不变的情况下，另一方无论如何改变自己的策略，都不能使自己的期望收益比原来多。\n\n可以证明，这样的策略是唯一的。\n\n答案对 $998244353$ 取模。\n\n[samples]\n\n## Background\n\n在《LIAR GAME》中，小 E 看到了一个有趣的游戏。\n\n## Note\n\n#### 样例解释 1\n\n这 $4$ 个数分别为 $2/3,1/3,1/3,2/3$。\n\n#### 子任务\n\n保证 $1\\le n \\le 400000$。\n\n#### 题目来源\n\n来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。\n\n题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9142","tags":["递推","博弈论","2023","O2优化","THUPC"],"sample_group":[["1\n","665496236 332748118\n332748118 665496236\n"]],"created_at":"2026-03-03 11:09:25"}}