← 返回题目列表

AtCoder · arc135_a

A. 地板、天花板 - 分解

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

分数: 300 点

问题陈述

有一个整数 X 写在黑板上。您可以执行以下操作任意次数(可能为零)。 黑板上写着

  • 选择一个整数 x 。
  • 删除一个 x 从黑板上写下两个新整数 \lfloor \frac{x}{2}\rfloor 和 \lceil \frac{x}{2}\rceil.

求运算后黑板上整数的最大可能乘积,取模 998244353.

什么是 \lfloor \frac{x}{2}\rfloor 和 \lceil \frac{x}{2}\rceil?

对于实数 x, \lfloor x\rfloor 表示不大于的最大整数 x,和 \lceil x\rceil 表示不小于的最小整数 x。例如,以下成立。

  • 对于 x = 2,我们有 \lfloor \frac{x}{2}\rfloor = 1 和 \lceil \frac{x}{2}\rceil = 1.
  • 对于 x = 3,我们有 \lfloor \frac{x}{2}\rfloor = 1, \lceil \frac{x}{2}\rceil = 2.

约束

  • 1\leq X \leq 10^{18}

输入

输入由标准输入按以下格式给出:

X

输出

打印运算后黑板上整数的最大可能乘积,模数 998244353.


示例输入 1

15

示例输出 1

192

这是一系列运算,使黑板上的整数相乘 192.

  • 黑板的初始状态是 (15).
  • 操作 x = 15 将其更改为 (7, 8).
  • 操作 x = 7 将其更改为 (8, 3, 4).
  • 操作 x = 4 将其更改为 (8, 3, 2, 2).
  • 操作 x = 8 将其更改为 (3, 2, 2, 4, 4).

这里,黑板上的整数的乘积是 3\times 2\times 2\times 4\times 4 = 192.


示例输入 2

3

示例输出 2

3

进行零运算使黑板上的整数相乘 3.


示例输入 3

100

示例输出 3

824552442

黑板上的整数经过运算后的最大可能乘积为 5856458868470016,应以模数形式打印 998244353.