#P1609. 翻牌谜题

翻牌谜题

翻牌谜题

题目背景

在《赛尔号》游戏的某个活动中,只有集齐三个指定道具才能获得精灵“六界御神”,而第三个道具则需要完成以下小游戏。

image-20240206125416906

题目描述

初始情况下,场上一共有 nn 张背面朝上的牌。

玩家可以尝试挑战 Boss,每次挑战成功,都将执行以下操作:

  • 等概率随机选择 k{1,2,3}k\in \{1,2,3\}(选到每个数的概率都是 1/31/3)。
  • 从所有卡牌中等概率随机选择不同kk 张牌(一共 (nk)\binom{n}{k} 种选取方式,都是等概率的),将这 kk 张牌 翻面 ,即:背面朝上的牌将改为正面朝上,正面朝上的牌将改为背面朝上。

如果某一时刻所有 nn 张卡牌都正面朝上,则玩家获得该道具。

假设玩家每次挑战都成功,现在 pzr 想知道,获得道具所需的期望挑战次数是多少?答案对 998244353998244353 取模。

在本题的限制条件下可以证明,一定存在两个互质的非负整数 P, Q 且 0 ≤ P, Q < 998244353,使得期望值可以表示为 P / Q。
在这种情况下,一定存在唯一的一个非负整数 R 使得 0 ≤ R < 998244353 且 R × Q ≡ P (mod 998244353)。
输出 R。 期望值对 998244353 取模?

输入格式

第一行一个正整数 nn

输出格式

一个非负整数,表示期望值,对 998244353 取模。

样例输入1

3

样例输出1

6

样例输入2

5

样例输出2

249561121

样例 2 解释

期望为 131 / 4,而 249561121×4131(mod998244353)249561121 \times 4 \equiv 131 \pmod {998244353},因此输出 249561121。

样例输入3

9

样例输出3

777254234

样例 3 解释

游戏中实际取的是 9 张牌,其中需要挑战的次数期望为 764763 / 1450,约为 527.42 次。

样例输入4

100

样例输出4

687351762

数据范围及约定

对于 50%50\% 的数据,3n93\le n\le 9

对于 90%90\% 的数据,3n5003\le n\le 500

对于 100%100\% 的数据,3n1053\le n\le 10^5