095 D - Xor Sum 4¶

• created: 2022-12-23 fri
• ご意見・ご要望はissue・プルリク用のGitHubまで
• 競技プログラミングのためのF#入門
• GitHub上の対応ディレクトリ
• 公式ページ
• 要点: 組み合わせの処理

解説¶

入出力¶

2^{60}はint64の範囲におさまります.

1
2
3

let N = stdin.ReadLine() |> int64
let Aa = stdin.ReadLine().Split() |> Array.map int64
solve N Aa |> stdout.WriteLine

mod計算用の演算子定義¶

1
2

  let (.+) a b = ((a%MOD)+(b%MOD))%MOD
  let (.*) a b = ((a%MOD)*(b%MOD))%MOD

たまにはまる場合があるため, aとbにも都度%MODをかませています.

実装¶

計算するのは排他的論理和で各ビットごとに計算した結果を積めば十分です. 特に10進表記のaの各iビットは(a>>>i)%2Lで取れます. ビットごとの和が必要なため, ビットでの各i桁ごとにAa |> Array.sumBy (fun a -> (a>>>i)%2L)を計算します.

1
2

  [|0..60|]
  |> Array.map (fun i -> Aa |> Array.sumBy (fun a -> (a>>>i)%2L))

解説にあるように各ビットごとの問題のXORの総和は0の個数 * 1の個数です. 最終的には10進数としての和を取る必要があるため, 各iごとに2^iをかける必要があります. この和はfold2で次のように計算できます.

1
2
3

  let Xa = [|0..60|] |> Array.map (fun i -> Aa |> Array.sumBy (fun a -> (a>>>i)%2L))
  (0L,[|0..60|],Xa) |||> Array.fold2 (fun acc i y ->
    acc .+ ((pown 2L i) .* y .* (N-y)))

本体はiとyの計算です. 解説にある0の個数 * 1の個数をy .* (N-y)です. 上で書いたように, これに2^i = pown 2L iをかけています. あとはそこまでの和accに積めば総和が計算できます.