积分: 500 点
问题陈述
有一个轮盘赌可以产生一个整数 1,2,\dots,N 具有相同的概率。
两名玩家用它来玩以下游戏:
- 玩家轮流旋转轮盘赌。
- 如果生成的整数之前没有出现过,则不会发生任何情况。
- 否则,旋转轮盘赌的玩家将支付以下罚款: 1 日元。
- 当所有的 N 整数至少出现过一次。
对于第一和第二玩家中的每一个,求游戏结束前支付的罚款金额的期望值,模 998244353.
对期望值取模 998244353
可以证明,该问题所求的期望值始终是有理数。 此外,在该问题的约束下,当期望值表示为不可约分数时 \frac{y}{x},保证 x 不能被整除 998244353.
现在,有一个唯一的整数 z 之间 0 和 998244352,包含在内,这样 xz \equiv y \pmod{998244353}。提供这个 z 作为答案。
约束
- N 是一个整数,使得 1 \le N \le 10^6.
输入
输入由标准输入按以下格式给出:
N
输出
打印两个整数作为答案。
第一个是第一个玩家支付的罚款金额的预期值,第二个是第二个玩家支付的罚款金额的预期值,以整数模表示 998244353.
示例输入 1
1
示例输出 1
0 0
在此输入中, N=1.
当第一个玩家旋转轮盘赌时,它总是产生 1,立即结束游戏。
因此,第一和第二玩家缴纳的罚款金额的期望值都是 0.
示例输入 2
2
示例输出 2
332748118 665496236
在此输入中, N=2。以下是游戏可能的进展:
- 第一个玩家旋转轮盘赌,它产生 2。什么也没发生。
- 第二个玩家旋转轮盘赌,它产生 2。第二名玩家缴纳罚款 1 日元。
- 第一个玩家旋转轮盘赌,它产生 2。第一个玩家缴纳罚款 1 日元。
- 第二个玩家旋转轮盘赌,它产生 1。什么也没发生。
- 此时,两者 1 和 2 至少出现过一次,所以游戏立即结束。
- 在此级数中,第一个玩家支付的罚款金额为 1 日元,第二名玩家缴纳的罚款金额也是 1 日元。
可以证明,第一个玩家支付的罚款金额的期望值为 \frac{1}{3} 日元,第二名玩家支付的罚款金额的预期值为 \frac{2}{3} 日元。
示例输入 3
3
示例输出 3
174692763 324429416