← 返回题目列表

AtCoder · ttpc2023_a

A. 无数的消除

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

配点 : 100 点

問題文

選手 1, 2, \dots, N 可以得到第 N 将举行一场有 人参赛的比赛。

会场准备了列 0, 1, \dots, N-1 可以得到第 N 列,其中排列的选手表示 i\ (0 \le i \le N - 1) 在该时刻连胜中。 i 比赛开始时,选手按照列

的顺序,从前到后排成选手 0 的顺序。 1, 2, \dots, N 在比赛中,按照以下步骤确定各选手的排名。

当某列恰好有

  1. 人选手时,该列选手的排名为 1 位。此时,步骤结束。 i 在包含至少 N-i 名选手的列中,选择编号最小的列,列
  2. 2 将有列中的选手 l 。
  3. 列 l 开始 2 人从列中退出,并用这 2 人进行比赛。比赛获胜者排在列 l+1 的后面,输者排在列 0 的后面。
  4. 回到步骤 1。

在本次比赛中进行的比赛次数为 998244353 后求余数。

但是,比赛中不会出现平局。此外,无论每场比赛结果如何,答案都可以确定为唯一。

制約

  • N 是一个整数
  • 1 \le N \le 10^5

入力

输入是按以下格式从标准输入给出的。

N

出力

打印答案。 来自


入力例 1

3

出力例 1

4

假设编号较小的选手获胜,比赛将按如下方式进行。

列 0 列 1 列 2 説明
\underline{1, 2}, 3 選手 1, 2 进行比赛,选手 1 在列 1 排列,选手 2 在列 0 后有
\underline{3, 2} 1 選手 3, 2 进行比赛,选手 2 在列 1 排列,选手 3 在列 0 后有
3 \underline{1, 2} 選手 1, 2 进行比赛,选手 1 在列 2 排列,选手 2 在列 0 后有
\underline{3, 2} 1 選手 3, 2 进行比赛,选手 2 在列 1 排列,选手 3 在列 0 后有
3 2 1 人选手时,该列选手的排名为 1 人选手,因此比赛结束。

比赛进行 4 回,因此,4 。


入力例 2

5

出力例 2

26

入力例 3

100000

出力例 3

538161387