BOJ 13710 - XOR 합 3

BOJ 13710 - XOR 합 3

꽤 고전한 문제이다.

Solution 1

각 비트를 생각한다. 최대 $30$개의 비트를 고려해주면 된다.

어떤 비트를 볼 때 해당 구간에 비트가 홀수개가 되는 구간의 개수를 셀 수 있다.

이걸 세는방법은, $1$ 을 기준으로 나뉘어진 각 구간의 길이가 $R_0, R_1, R_2$ 라고 할 때,

$R_0 \cdot (R_1+R_3+R_5+ \cdots) + R_1(R_2+R_4+\cdots)+\cdots$ 처럼 세는 것이다.

이 방법은 $O(N)$으로 가능하고 결국 $O(30N)$으로 문제를 해결할 수 있다.

void solve() {
   int n;
   cin >> n;
   int X = 0;
   vi a(n);
   fv(a);

   vvi idx(30);
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < 30; j++) {
         if (a[i] & (1 << j)) idx[j].pb(i);
      }
   }
   int ans = 0;
   for (int b = 0; b < 30; b++) {
      idx[b].insert(idx[b].begin(), -1);
      idx[b].pb(n);
      int cnt = 0;

      int sum0 = 0, sum1 = 0;
      for (int i = 0; i < sz(idx[b]) - 1; i++) {
         int len = idx[b][i + 1] - idx[b][i];
         if (i % 2 == 0)sum0 += len;
         else sum1 += len;
      }
      for (int i = 0; i < sz(idx[b]) - 1; i++) {
         int len = idx[b][i + 1] - idx[b][i];

         if (i % 2 == 0) cnt += len * sum1;
         else cnt += len * sum0;

         if (i % 2 == 0)sum0 -= len;
         else sum1 -= len;
      }

      ans += (1 << b) * cnt;
   }

   cout << ans;
}

Solution 2

$\oplus$연산의 성질을 좀 더 이용하는 것이다.

$\displaystyle XOR_{i=l}^r A_i=XOR_{i=0}^r A_i \oplus XOR_{i=0}^{l-1} A_i$ 이다.

어떤 $A_i$를 볼 때, $XOR_{i=0}^i A_i=1$ 이라면, 지금까지 $XOR_{i=0}^j A_i = 0$ 인 $j$ 의 개수가 몇개였는지로 곧바로 $\oplus$한게 $1$ 인 구간의 개수를 셀 수 있다.