← 返回题目列表

AtCoder · arc174_c

C. 灾难性轮盘赌

中文机器翻译题面 查看原题

积分: 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