問題一覧 > 通常問題

No.3399 One Two Three Two Three

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 3
作問者 : akakimidori / テスター : noshi91
ProblemId : 10112 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-12-03 18:05:15
コンテストの他の問題:

問題文

整数 $N$ が与えられます。 また、変数 $x$ が $x=1$ と初期化されています。
ここから $x < N$ である間、以下の $5$ つの操作からひとつ選んで操作を行うことを繰り返します。

  1. $x$ を $x+1$ に更新する。
  2. $x$ を $x+2$ に更新する。
  3. $x$ を $x+3$ に更新する。
  4. $x$ を $2x$ に更新する。
  5. $x$ を $3x$ に更新する。
操作を終えた時に $x=N$ となってるような操作の方法の個数を $998244353$ で割ったあまりを求めてください。

入力

$N$

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

出力

操作の個数を $998244353$ で割ったあまりを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
1
出力
1

初期状態で $x = 1$ となり、操作は終了しています。 操作を行わないので $1$ 通りとなります。

サンプル2
入力
2
出力
2

操作を一度行うと $x < 2$ を満たさなくなります。 $1$回の操作で $x=2$ となるような操作の仕方は 1. の操作、または 4. の操作を選んだ時のみです。 $2$通りとなるので $2$ を出力します。

サンプル3
入力
3
出力
4

サンプル4
入力
10
出力
401

サンプル5
入力
100
出力
888004452

$998244353$ で割ったあまりを出力することに注意してください。

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