#P18377. International Olympiad in Fishing
International Olympiad in Fishing
International Olympiad in Fishing
题目描述
首届国际钓鱼奥林匹克竞赛(International Olympiad in Fishing,简称 IOF)将在亚特兰蒂斯举行。小青鱼将参加比赛,组委会主席小啫喱鱼告诉了他今年的比赛规则:通过一场卡牌游戏决定胜者。
游戏中有 张卡牌,初始编号依次为 。每张卡牌还有两个属性:点数(Rank)和花色(Suit)。每张牌的点数、花色都在整数区间 中独立、等概率地选取;不同卡牌的点数或花色可以相同。
卡牌的编号写在背面,点数和花色写在正面。最初,所有卡牌背面朝上,按编号递增排列在桌上。因此,小青鱼知道每张卡牌的编号,但看不到它的点数或花色。
桌上有两个按钮,小青鱼可以任意多次按下它们:
- 按下 Rank 按钮:把当前所有卡牌按点数递增排序。
- 按下 Suit 按钮:把当前所有卡牌按花色递增排序。
两种排序都是稳定排序:属性值不同的两张牌中,属性值较小的牌排在前面;属性值相同的牌保持本次排序之前的相对顺序。
每次排序后,小青鱼只能观察到卡牌背面的编号顺序,仍然看不到任何点数或花色。操作结束后,他必须猜出每张卡牌的准确点数和花色。
请计算采用最优策略时,所有卡牌的点数和花色都猜对的概率,答案对 取模。
若概率表示为有理数 ,输出 ,其中 是模意义下的乘法逆元。
输入格式
输入一行,一个整数 ()。
本题是标准输入输出题,不是交互题。输入中没有实际卡牌的属性。
输出格式
输出一行,一个整数,表示所求概率对 取模后的结果。
样例输入 1
2
样例输出 1
686292993
样例输入 2
5
样例输出 2
301495273
样例输入 3
52
样例输出 3
126716306
样例说明
对第一个样例,小青鱼可以先按一次 Rank,再按一次 Suit,并观察这两次操作是否交换两张卡牌的位置。
以下“第一张牌”和“第二张牌”始终指初始编号分别为 1 和 2 的卡牌,不是排序后处于第一、第二位置的卡牌。
- 两次操作都交换了位置:猜第一张牌为点数 、花色 ,第二张牌为点数 、花色 。
- Rank 交换了位置,Suit 没有交换:猜第一张牌为点数 、花色 ,第二张牌为点数 、花色 。
- 两次操作都没有交换位置:猜第一张牌为点数 、花色 ,第二张牌为点数 、花色 。
- Rank 没有交换位置,Suit 交换了位置:再按一次 Rank。
- 若这次交换了位置,猜第一张牌为点数 、花色 ,第二张牌为点数 、花色 。
- 若这次没有交换位置,猜第一张牌为点数 、花色 ,第二张牌为点数 、花色 。
可以证明该策略猜对全部属性的概率为 ,且已经最优。模意义下,。