ABC147 D - Xor Sum 4
April 16, 2020
問題
考えたこと
愚直に全てをみるとO(N^2)なので間に合わない..
制約でA[i] <= 2^60なので、A[i]を2進数表記にして桁数を1つづつ、全てのAについてみていけばO(10^6)なのでいけそう？
桁をみることでどういうことができるんだ？…うーんわからん
解説をみて
考え方自体はあってた(桁数ごとにすべてのA[i]をみる)
XORの特性として、1つの桁を独立で考えることができる
| a | b | a XOR b | a + b |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 10 |
和とかと違って繰り上がりが発生しないので、独立でその桁だけみれる
それで、XORをとったときに、その桁が1で残る場合は加算されていくので、桁ごとにいくつ1が残るかを調べていけばいい
これは簡単で、A[i] XOR A[j] // 0 <= i < j < nの全ての組み合わせをみるのでA[0~n]のある桁にある0の個数 × 1の個数が残る1の数である
最後に, 2進数表記のある桁における1を10進数に直す必要がある
これも簡単で, 例えば桁が10だとしたら、 pow(2, 10)である..(1桁目を0桁目と数えるのは注意)
例を考えてみる
入力として以下が与えられるとして
3
8 10 12
それぞれを2進数表記に直すと
- 8 ->
1000 - 10 ->
1010 - 12 ->
1100
まず実際に全てを加算して確かめてみる
XORをとる組み合わせは3つで
1000 XOR 1010 => 0010 => 2, 1000 XOR 1100 => 0100 > 4, 1010 XOR 1100 => 0110 => 62+4+6 = 12が答えとなる
次に上の解説で書いたのを確認する
それぞれの桁に0と1がいくつあるかを確認する
| (右から)3桁目 | 2桁目 | 1桁目 | 0桁目 | |
|---|---|---|---|---|
| 0の個数 | 0 | 2 | 2 | 3 |
| 1の個数 | 3 | 1 | 1 | 0 |
それぞれの桁で残る1の数と, それぞれの桁における1を10進数に直した時の値をかける
- 0桁目 : (3*0) * 2^0 = 0
- 1桁目 : (2*1) * 2^1 = 4
- 2桁目 : (2*1) * 2^2 = 8
- 3桁目 : (0*3) * 2^3 = 0
全てを足して 0+4+8+0 = 12
上で確認したのと同じなのでok
提出したコード
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
typedef pair<int, int> P;
ll modnum = 1e9+7;
long long modpow(long long a, long long n, long long mod) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
int main() {
int n; cin >> n;
vector<ll> a(n);
rep(i, n) cin >> a[i];
ll ans = 0;
rep(i, 60) {
ll one = 0;
// a[j]のi桁目が1の個数をカウントする
rep(j, n) if(a[j]>>i&1) one++;
// 1か0しかないので、残りが0
ll zero = n - one;
// i桁目の1と0の組み合わせ数(1の個数×0の個数)だけi桁目に1ができる
ll now = one*zero%modnum;
// i桁目の1は2^iに値する, それらの和になる
ll digit = modpow(2, i, modnum);
ans += now * digit % modnum;
ans %= modnum;
}
cout << ans << endl;
return 0;
}