問題一覧 > 通常問題

No.1853 Many Operations

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 11
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi
0 ProblemId : 7576 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-02-26 00:09:08

問題文

正整数 $X$ に対し、 $f(X)$ を以下のように定義します。

  • 変数 $A$ があり、 $A=0$ で初期化されている。 $A$ に以下の $3$ 種類の操作を行い、 $A=X$ を成立させるために必要な操作回数の最小値。なお、 $X$ によらず以下の操作を行うことで必ず $A=X$ を成立させることができることが示せます。
    • $A$ に $1$ を足す。
    • $A$ から $1$ を引く。
    • $A$ に $2$ をかける。

正整数 $N$ が与えられます。 $1 \leq i \leq N$ を満たす整数 $i$ について $f(i)$ を足し合わせた値を $998244353$ で割った余りを求めてください。

入力

$N$

  • $1 \leq N \leq 10^{18}$
  • $N$ は整数

出力

$1 \leq i \leq N$ を満たす整数 $i$ について $f(i)$ を足し合わせた値を $998244353$ で割った余りを出力し、改行してください。

サンプル

サンプル1
入力
4
出力
9

以下より $f(1)=1,f(2)=2,f(3)=3,f(4)=3$ となるので、答えは $1+2+3+3=9$ です。

  • $A$ に $1$ を足す操作を $1$ 回行うことで $A=1$ とできます。これが $A=1$ とするための操作回数の最小値です。
  • $A$ に $1$ を足す操作を $2$ 回行うことで $A=2$ とできます。これが $A=2$ とするための操作回数の最小値です。
  • $A$ に $1$ を足す操作を $3$ 回行うことで $A=3$ とできます。これが $A=3$ とするための操作回数の最小値です。
  • $A$ に $1$ を足す操作を $2$ 回行い、 $2$ をかける操作を $1$ 回行うことで $A=4$ とできます。これが $A=4$ とするための操作回数の最小値です。

サンプル2
入力
77
出力
554

サンプル3
入力
2022
出力
27178

サンプル4
入力
998244353
出力
675748992

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