No.1853 Many Operations
問題文最終更新日: 2022-02-26 00:09:08
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
蜜蜂