#P1609. 翻牌谜题
翻牌谜题
翻牌谜题
题目背景
在《赛尔号》游戏的某个活动中,只有集齐三个指定道具才能获得精灵“六界御神”,而第三个道具则需要完成以下小游戏。
题目描述
初始情况下,场上一共有 张背面朝上的牌。
玩家可以尝试挑战 Boss,每次挑战成功,都将执行以下操作:
- 等概率随机选择 (选到每个数的概率都是 )。
- 从所有卡牌中等概率随机选择不同的 张牌(一共 种选取方式,都是等概率的),将这 张牌 翻面 ,即:背面朝上的牌将改为正面朝上,正面朝上的牌将改为背面朝上。
如果某一时刻所有 张卡牌都正面朝上,则玩家获得该道具。
假设玩家每次挑战都成功,现在 pzr 想知道,获得道具所需的期望挑战次数是多少?答案对 取模。
在本题的限制条件下可以证明,一定存在两个互质的非负整数 P, Q 且 0 ≤ P, Q < 998244353,使得期望值可以表示为 P / Q。
在这种情况下,一定存在唯一的一个非负整数 R 使得 0 ≤ R < 998244353 且 R × Q ≡ P (mod 998244353)。
输出 R。
在这种情况下,一定存在唯一的一个非负整数 R 使得 0 ≤ R < 998244353 且 R × Q ≡ P (mod 998244353)。
输出 R。
期望值对 998244353 取模?
输入格式
第一行一个正整数 。
输出格式
一个非负整数,表示期望值,对 998244353 取模。
样例输入1
3
样例输出1
6
样例输入2
5
样例输出2
249561121
样例 2 解释
期望为 131 / 4,而 ,因此输出 249561121。
样例输入3
9
样例输出3
777254234
样例 3 解释
游戏中实际取的是 9 张牌,其中需要挑战的次数期望为 764763 / 1450,约为 527.42 次。
样例输入4
100
样例输出4
687351762
数据范围及约定
对于 的数据,。
对于 的数据,。
对于 的数据,。
相关
在下列比赛中: