問題一覧 > 通常問題

No.3399 One Two Three Two Three

レベル : / AI推定難易度 : 3275 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 10
作問者 : akakimidori / テスター : noshi91
お気に入りにしたユーザー ProblemId : 10112 / 自分の提出
問題文最終更新日: 2025-12-03 18:05:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2025 (順位表) の他の問題:

Problem Statement

You are given an integer $N$. A variable $x$ is initialized as $x=1$.
From this point, while $x < N$, repeatedly choose one of the following $5$ operations and perform it.

  1. Update $x$ to $x+1$.
  2. Update $x$ to $x+2$.
  3. Update $x$ to $x+3$.
  4. Update $x$ to $2x$.
  5. Update $x$ to $3x$.
Find the number of ways of performing the operations such that $x=N$ when the operations finish, modulo $998244353$.

Input

$N$

  • $1\leq N \leq 10^{18}$

Output

Output the number of operations modulo $998244353$. Print a newline at the end.

Sample

Sample 1
Input
1
Output
1

In the initial state, $x = 1$ and the operations have already finished. Since no operation is performed, there is $1$ way.

Sample 2
Input
2
Output
2

After performing one operation, $x < 2$ no longer holds. The only ways to get $x=2$ with $1$ operation are choosing operation 1. or operation 4. There are $2$ ways, so output $2$.

Sample 3
Input
3
Output
4

Sample 4
Input
10
Output
401

Sample 5
Input
100
Output
888004452

Note that you must output the remainder when divided by $998244353$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。