BOJ 23257 - 비트코인은 신이고 나는 무적이다

BOJ 23257 - 비트코인은 신이고 나는 무적이다

최대 1023까지만 xor값이 나올 수 있다.

따라서 $dp[i][j][x]$ 를 $i$ 번째 수 까지 봐서 $j$ 개의 수를 쓰고 xor이 $x$가 나오는 것의 개수라고 하자.

이걸 $O(nm \cdot 1023)$ 으로 구해줄 수 있다.

이후에 정답은 $dp[n][m]$ 중 가장 큰 값이라고 생각할 수 있지만 아니다.

$x \oplus x = 0$ 이여서 $m, m-2, m-4,\cdots$ 중에서 찾아주어야 한다.

int dp[101][101][1024];

void solve() {
   int n, m;
   cin >> n >> m;
   vi a(n + 1);
   fv1(a);
   for (int &i: a) i = abs(i);
   dp[0][0][0] = 1;
   for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= min(m, i); j++) {
         for (int k = 0; k < 1024; k++) {
            dp[i][j][k] = dp[i - 1][j][k];
            if (j && dp[i - 1][j - 1][k ^ a[i]]) {
               dp[i][j][k] = 1;
            }
         }
      }
   }
   for (int i = 1023; i >= 0; i--) {
      for (int j = m; j >= 0; j -= 2) {
         if (dp[n][j][i]) {
            cout << i;
            return;
         }
      }
   }
   assert(0);
}