#P18377. International Olympiad in Fishing

International Olympiad in Fishing

International Olympiad in Fishing

题目描述

首届国际钓鱼奥林匹克竞赛(International Olympiad in Fishing,简称 IOF)将在亚特兰蒂斯举行。小青鱼将参加比赛,组委会主席小啫喱鱼告诉了他今年的比赛规则:通过一场卡牌游戏决定胜者。

游戏中有 nn 张卡牌,初始编号依次为 1,2,…,n1,2,\ldots,n。每张卡牌还有两个属性:点数(Rank)和花色(Suit)。每张牌的点数、花色都在整数区间 [1,n][1,n] 中独立、等概率地选取;不同卡牌的点数或花色可以相同。

卡牌的编号写在背面,点数和花色写在正面。最初,所有卡牌背面朝上,按编号递增排列在桌上。因此,小青鱼知道每张卡牌的编号,但看不到它的点数或花色。

桌上有两个按钮,小青鱼可以任意多次按下它们:

  • 按下 Rank 按钮:把当前所有卡牌按点数递增排序。
  • 按下 Suit 按钮:把当前所有卡牌按花色递增排序。

两种排序都是稳定排序:属性值不同的两张牌中,属性值较小的牌排在前面;属性值相同的牌保持本次排序之前的相对顺序。

每次排序后,小青鱼只能观察到卡牌背面的编号顺序,仍然看不到任何点数或花色。操作结束后,他必须猜出每张卡牌的准确点数和花色。

请计算采用最优策略时,所有卡牌的点数和花色都猜对的概率,答案对 998244353998244353 取模。

若概率表示为有理数 A/BA/B,输出 A⋅B−1 mod 998244353A\cdot B^{-1}\bmod 998244353,其中 B−1B^{-1} 是模意义下的乘法逆元。

输入格式

输入一行,一个整数 nn(1≤n≤5×1051\le n\le 5\times10^5)。

本题是标准输入输出题,不是交互题。输入中没有实际卡牌的属性。

输出格式

输出一行,一个整数,表示所求概率对 998244353998244353 取模后的结果。

样例输入 1

2

样例输出 1

686292993

样例输入 2

5

样例输出 2

301495273

样例输入 3

52

样例输出 3

126716306

样例说明

对第一个样例,小青鱼可以先按一次 Rank,再按一次 Suit,并观察这两次操作是否交换两张卡牌的位置。

以下“第一张牌”和“第二张牌”始终指初始编号分别为 1 和 2 的卡牌,不是排序后处于第一、第二位置的卡牌。

  • 两次操作都交换了位置:猜第一张牌为点数 22、花色 11,第二张牌为点数 11、花色 22。
  • Rank 交换了位置,Suit 没有交换:猜第一张牌为点数 22、花色 22,第二张牌为点数 11、花色 11。
  • 两次操作都没有交换位置:猜第一张牌为点数 11、花色 11,第二张牌为点数 22、花色 22。
  • Rank 没有交换位置,Suit 交换了位置:再按一次 Rank。
    • 若这次交换了位置,猜第一张牌为点数 11、花色 22,第二张牌为点数 22、花色 11。
    • 若这次没有交换位置,猜第一张牌为点数 11、花色 22,第二张牌为点数 11、花色 11。

可以证明该策略猜对全部属性的概率为 5/165/16,且已经最优。模意义下,5/16≡686292993(mod998244353)5/16\equiv686292993\pmod{998244353}。