BOJ 2272 램프

문제 링크입니다.

관찰

011010 이 주어졌다고 합시다. 1초가 지날 때마다, 램프의 상태는 현재 램프의 상태를 한 칸 왼쪽으로 돌리고 XOR한 것과 같습니다.

1초가 지나면, 램프의 상태는 011010^110100 = 101110 이 됩니다.

다시 1초가 지나면, 램프의 상태는 101110^011101 = 110011 이 됩니다.

여기서 101110을 011010^110100 로 풀어써 보면, 처음에서 2초가 지난 뒤의 램프의 상태는 (011010^110100)^(110100^101001) = 011010^101001 = 110011로 표현할 수도 있습니다.

일반화

처음 상황에서 $t$초가 지난 뒤 램프의 상태를 램프의 상태를 왼쪽으로 $t$칸 돌리고 XOR한 것으로 표현할 수 있다고 합시다. 희소 배열을 만들듯이 $t$초 후의 상황에서 다시 $t$초가 지났을 때의 상황을 생각합시다. 이를 XOR로 보았을 때 (처음 상태 ^ $t$칸 돌린 상태) ^ ($t$칸 돌린 상태 ^ $2t$칸 돌린 상태) = (처음 상태 ^ $2t$칸 돌린 상태) 로 표현할 수 있습니다. 즉, 어떤 상태에서 1초, 2초, … , $2^k$초 지난 뒤 램프의 상태를 그만큼 왼쪽으로 램프의 상태를 돌리고 XOR하는 것으로 구할 수 있습니다.

그냥 직접 구현해도 충분히 빠르게 작동하고, 비트 집합을 이용해 더 빠르게 코드를 짤 수도 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
bitset<2020202> a, t, x;

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
	int n, k; cin >> n >> k;
	for(int i = 0; i < n; i++){
		int b; cin >> b; a[i] = b;
	}
	for(int i = 0; i < n; i++) x[i] = 1;
	for(int i = 1; i <= k; i *= 2) if(i&k){
		int b = n-i%n;
		t = a<<b; t |= a>>n-b;
		a ^= t; a &= x;
	}
	for(int i= 0; i < n; i++) cout << a[i] << '\n';
}