問題一覧 > 通常問題

No.1853 Many Operations

レベル : / AI推定難易度 : 2025 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : 蜜蜂 / テスター : Mitarushi
お気に入りにしたユーザー ProblemId : 7576 / 自分の提出
問題文最終更新日: 2022-02-26 00:09:08
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
yukicoder contest 333 (灘高入試コンテスト2022) (順位表) の他の問題:

Problem Statement

For a positive integer $X$, define $f(X)$ as follows.

  • There is a variable $A$, initialized to $A=0$. The value is the minimum number of operations needed to make $A$ satisfy the following by applying the $3$ types of operations below to it: $A=X$. It can be shown that, regardless of $X$, it is always possible to achieve $A=X$ by performing the operations below.
    • Add $1$ to $A$.
    • Subtract $1$ from $A$.
    • Multiply $A$ by $2$.

You are given a positive integer $N$. Find the sum of $f(i)$ over all integers $i$ satisfying $1 \leq i \leq N$, modulo $998244353$.

Input

$N$

  • $1 \leq N \leq 10^{18}$
  • $N$ is an integer.

Output

Print the sum of $f(i)$ over all integers $i$ satisfying $1 \leq i \leq N$, modulo $998244353$, followed by a newline.

Sample

Sample 1
Input
4
Output
9

From the following, we have $f(1)=1,f(2)=2,f(3)=3,f(4)=3$, so the answer is $1+2+3+3=9$.

  • Performing the operation of adding $1$ to $A$ $1$ time makes $A=1$. This is the minimum number of operations needed to make $A=1$.
  • Performing the operation of adding $1$ to $A$ $2$ times makes $A=2$. This is the minimum number of operations needed to make $A=2$.
  • Performing the operation of adding $1$ to $A$ $3$ times makes $A=3$. This is the minimum number of operations needed to make $A=3$.
  • Performing the operation of adding $1$ to $A$ $2$ times and the operation of multiplying by $2$ $1$ time makes $A=4$. This is the minimum number of operations needed to make $A=4$.

Sample 2
Input
77
Output
554

Sample 3
Input
2022
Output
27178

Sample 4
Input
998244353
Output
675748992

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