BOJ 31422 : AND, OR, XOR 2

• 문제 링크 : boj.kr/31422
• 난이도 : G1
• 태그 : DP

31422번: AND, OR, XOR 2

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    ll arrA[32] = {};
    ll arrB[32] = {};
    ll arrC[32] = {};
    ll ansA = 0;
    ll ansB = 0;
    ll ansC = 0;
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        for(int j = 0; j < 32; j++) {
            int t = (input >> j) & 1;
            if(t) {
                arrA[j] += 1;
                ansA += (arrA[j] << j) % 998244353;
                ansA %= 998244353;
                arrB[j] = i + 1;
                ansB += (arrB[j] << j) % 998244353;
                ansB %= 998244353;
                arrC[j] = i + 1 - arrC[j];
                ansC += (arrC[j] << j) % 998244353;
                ansC %= 998244353;
            }
            else {
                arrA[j] = 0;
                ansB += (arrB[j] << j) % 998244353;
                ansB %= 998244353;
                ansC += (arrC[j] << j) % 998244353;
                ansC %= 998244353;
            }
        }
    }
    cout << ansA << " " << ansB << " " << ansC;

    return 0;
}

---

풀이

K번째 원소를 처리할 때, $\sum\limits_{i=1}^{K}{( A_i @ ...  @ A_K )}$를 처리한다. (@는 연산자)

위의 수열의 합을 효과적으로 처리하기 위해 비트별로 수열에 포함된 1의 수를 저장한다.

이제 비트별로 해당 위치의 값에 따라 1의 수가 어떻게 변하는지를 구해준다. DP식은 다음과 같다.

$$AND(K) = \begin{cases}AND(K-1)+1, & \mbox{if bit is }1\\0, & \mbox{if bit is }0\\ \end{cases}$$

$$OR(K) = \begin{cases}K+1, & \mbox{if bit is } 1\\OR(K-1), & \mbox{if bit is } 0\\ \end{cases}$$

$$XOR(K) = \begin{cases}K+1-XOR(K-1), & \mbox{if bit is } 1\\ XOR(K-1), & \mbox{if bit is } 0 \\ \end{cases}$$

비트의 위치에 따라 적절한 2의 제곱수를 곱해주고 더해주면 된다.