問題一覧 > 通常問題

No.3554 Rurumaru Function Problem 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : ルク / テスター : 👑 loop0919 ぽえ lif4635
ProblemId : 13321 / yukicoder contest 500 (順位表) / 自分の提出
問題文最終更新日: 2026-04-23 21:48:05
yukicoder contest 500の他の問題:

問題文

非負整数 $x,y$ に対し、 $f(x,y)$ を以下のように定義された非負整数とします。
  • $f(x,y)$ を二進表記したときの $2^i(i \ge 0)$ の位の値は、
    • $i$ が偶数ならば、$x$ の $2^i$ の位の値と $y$ の $2^i$ の位の値の論理積(AND)を取った値。
    • $i$ が奇数ならば、$x$ の $2^i$ の位の値と $y$ の $2^i$ の位の値の論理和(OR)を取った値。
例えば、$f(2,14)=10$ です。(二進表記にすると$f(0010_{(2)},1110_{(2)})=1010_{(2)}$ となります。)
また、正整数 $n$ に対し、$g(n)$ を以下のように定義します。
  • $0\le{x,y}\lt{n}$ を満たす全ての整数の組 $(x,y)$ に対して $f(x,y)$ の値を考えたとき、これら $n^2$ 個の値の最頻値のうち最小の値を $g(n)$ とする。
正整数 $N$ が与えられます。このとき、$\displaystyle\sum_{n=1}^N {g(n)}$ を求めてください。

制約

  • $1 \le N \le 10^9$
  • 入力はすべて整数である

入力

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

$N$

出力

答えを出力せよ。

サンプル

サンプル1
入力
4
出力
4
以下は$0\le{x,y}\le{N-1}$ を満たす全ての整数の組 $(x,y)$ に対して $f(x,y)$ の値です。
$f(0, 0) = 0$, $f(0, 1) = 0$, $f(0, 2) = 2$, $f(0, 3) = 2$
$f(1, 0) = 0$, $f(1, 1) = 1$, $f(1, 2) = 2$, $f(1, 3) = 3$
$f(2, 0) = 2$, $f(2, 1) = 2$, $f(2, 2) = 2$, $f(2, 3) = 2$
$f(3, 0) = 2$, $f(3, 1) = 3$, $f(3, 2) = 2$, $f(3, 3) = 3$
  • $g(1)$において、$[f(0,0)]=[0]$ の最頻値は $0$ なので、$g(1)=0$ です。
  • $g(2)$において、$[f(0,0),f(0,1),f(1,0),f(1,1)]=[0,0,0,1]$ の最頻値は $0$ なので、$g(2)=0$ です。
  • $g(3)$において、$[0,0,2,0,1,2,2,2,2]$ の最頻値は $2$ なので、$g(3)=2$ です。
  • $g(4)$において、$[0,0,2,2,0,1,2,3,2,2,2,2,2,3,2,3]$ の最頻値は $2$ なので、$g(4)=2$ です。
よって、求める値は、$g(1)+g(2)+g(3)+g(4)=4$ です。
サンプル2
入力
1
出力
0

サンプル3
入力
1000000000
出力
303611125277312236

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