人権なし

競プロで解いた問題や開発の進捗などの記録です

AtCoder Beginner Contest 129:E - Sum Equals Xor

問題

atcoder.jp

解法

a + b == a XOR b となるためには,a と b で任意の bit の桁が 1 と 1 になってはいけない.1 XOR 1 は 0 となるが,1 + 1 は 10 と繰り上がりが発生し a + b != a XOR b となってしまう.

L の中で bit が立っている桁それぞれについて(k bit 目とおく),a + b の k bit 目より大きい桁が L と一致し,k bit 目を 0 にし,k bit 目より小さい桁を 0 か 1 とするときの通り数を考える.k bit 目より小さい桁は「a も b も 0」,「a か b の一方が 1」の 3 通りそれぞれある.また,k bit 目より大きい桁は「a か b の一方が 1」の 2 通りそれぞれある.この 2 つを掛け合わせたものをを全て足しせば L の中で bit が立っている桁のうち最低 1 つを 0 にするときの場合の数が求まる.そこに,L == a + b となる通り数 2^(L の中で bit が立っている個数) を足す必要がある.O(|L|).

解答

atcoder.jp

f:id:babcs2035:20190615154130p:plain