問題一覧 > 通常問題

No.3432 popcount & sum (Hard)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : harel / テスター : まみめ hirayuu_yc rogi52 遭難者 syndrome kidodesu 👑 ArcAki Eku
ProblemId : 12907 / yukicoder contest YNUCPC Contest 2 (順位表) / 自分の提出
問題文最終更新日: 2026-01-11 12:54:39
yukicoder contest YNUCPC Contest 2の他の問題:

※この問題は popcount & sum (Easy) の制約が異なる問題です。

問題文

非負整数 $k$ に対して、「$k$ を $2$ 進数表記したときの $1$ の個数」を $p(k)$ と定めます。
また、関数 $f(a,b)$ を以下のように定めます。

$$ f(a,b) = \left\{ \begin{array}{cc} a\ \& \ b & (p(a) = p(b))\\ 0 & (\text{otherwise}) \end{array} \right. $$

ここで、$a\ \& \ b$ は $a$ と $b$ の $\text{bitwise AND}$ を表します。
$(\text{e.g. } 3\ \& \ 5 = 1,$ 二進表記すると：$\ 001_{(2)}\ \& \ 101_{(2)} = 001_{(2)})$

整数 $n$ が与えられるので、

$$\sum_{a=0}^{n}\sum_{b=a}^{n}f(a,b)$$

を $998244353$ で割った余りを求めてください。

制約

  • $0 \leq n \leq10^{18}$
  • 入力は整数

入力

入力は以下の形式で標準入力から与えられます。

$n$

出力

答えを整数として出力してください。

サンプル

サンプル1
入力
3
出力
6
サンプル2
入力
15
出力
210
サンプル3
入力
2026
出力
187683588
サンプル4
入力
1000000000000000000
出力
291107133

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