BOJ 2272 - 램프

BOJ 2272 - 램프

대략적인 상태 전이를 보자. $1$이 있는 칸에 주목한다.

00000001 0  
00000011 1  
00000101 2  
00001111 3  
00010001 4

여기서 왼쪽에 $1$을 하나 더 붙이고 시작해보자.

00000011 0  
00000101 1
00001111 2
00010001 3
00110011 4

우리가 하나만 있을땐 $10001$ 을 얻었는데, 그 옆에 하나가 붙으니 정확히 동일하게 $110011$ 처럼 붙은 결과물이 나옴을 알 수 있다.

그럼 만약에 $1$이 겹치면 어떨까?

000010001 0  
000110011 1  
001010101 2  
011111111 3  
100000001 4

$1$이 짝수개가 있으면 다시 그 칸이 $0$이 됨을 알 수 있다.

여기까지만 관찰하면 엄밀한 증명 없이도 대략 $M$을 $2$의 거듭제곱수만 봐서 풀 수 있다고 가정할 수 있고, 실제로 이것이 정답이다.

증명은 이 연산 자체가 $2$를 곱한것에 $\oplus$을 한것으로 볼 수 있는데, 문제를 풀 때 이 생각은 했지만 $1$번칸이 $1$일 때 오른쪽이 변해야 되는 조건이 있어서 그것을 좀 더 수학적으로 발전시키진 못했다.

void solve() {  
   int n, m;  
   cin >> n >> m;  
   vi a(n);  
   fv(a);  
  
   for (int k = 0; k <= 30; k++) {  
      if (m & (1 << k)) {  
         vi b(n);  
         for (int i = 0; i < n; i++) {  
            if (a[i]) {  
               b[i] ^= 1;  
               b[md(n, i - (1 << k))] ^= 1;  
            }  
         }  
         a = b;  
      }  
   }  
  
   for(int i: a) cout << i << endl;  
}