ARC147_D(Xor Sum 4 )

概要

• くじかつ で AtCoder Beginner Contest 147 D を解いたのでメモ

問題概要

• N個の数字が与えられる(数列 A とする)
• 数列Aに対して, 以下の数式を解いて で割った余りを答えろ, という問題
  • 

方針

• 制約的に愚直にやっても間に合わないため, 何かしらの知恵が必要と類推
• 全く思いつかなかったが, とりあえず制約に出てくる 2 ^ 60 という数値からbit毎に見ていけば良さそうと当たりをつける
• 適当な数値を適当な個数で渡した時に, 1桁目(2 ^ 0)がどのように遷移するか確認した
  • 結論: 各桁毎に調べていくと 1 が立っている数 * 0 が立っている数 * 2 ^ (桁-1) になることが判明
  • bit毎に1の個数を数え上げてあげれば計算できる

実装(rust)

fn main() {
    let n = input!(u128);
    let a_vec = input!(u128; "vec");
    let mut result:u128 = 0;
    let MOD:u128 = 10u128.pow(9) + 7;

    for i in 0..61 {
        let mut count = 0;
        for a in &a_vec {
            if a >> i & 1 == 1 {
                count += 1;
            }
        }
        let add = (count * (n - count) * 2u128.pow(i)) % MOD;
        result = (result + add) % MOD;
    }

    println!("{}", result);
}

• 例によって入力は省略

所感

• 良くわからなくても人力でやってみて法則が見つけられれば解ける
• なお, 一番最初の提出は u128 ではなく usize でやって見事にオーバーフローして WA を出してしまった
  • Pythonだとオーバーフローとはほぼほぼ無縁なので油断しました