No.3432 popcount & sum (Hard)
問題文最終更新日: 2026-01-12 09:46:00
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 YNUCPC Contest 2
(順位表)
の他の問題:
※This problem is popcount & sum (Easy) with different constraints.
Problem Statement
For a non-negative integer $k$, define $p(k)$ as "the number of $1$s when $k$ is written in base $2$".
Also, define the function $f(a,b)$ as follows.
Here, $a\ \& \ b$ denotes the $\text{bitwise AND}$ of $a$ and $b$.
$(\text{e.g. } 3\ \& \ 5 = 1,$ in binary:$\ 001_{(2)}\ \& \ 101_{(2)} = 001_{(2)})$
Given an integer $n$, find the value of
$$\sum_{a=0}^{n}\sum_{b=a}^{n}f(a,b)$$modulo $998244353$.
Constraints
- $0 \leq n \leq10^{18}$
- The input is an integer.
Input
The input is given from Standard Input in the following format.
$n$
Output
Output the answer as an integer.
Sample
Sample 1
Input
3
Output
6
Sample 2
Input
15
Output
210
Sample 3
Input
2026
Output
187683588
Sample 4
Input
1000000000000000000
Output
291107133
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
まみめ
kidodesu