BOJ 2272 : 램프

알고리즘

bitmasking, ed_hoc

시간복잡도

$O(NlogM)$

풀이

00...01의 전이 상태를 순차적으로 확인해보면,

1세대 때 00...011  
2세대 때 00...0101  
4세대 때 00...010001  
8세대 때 00...0100000001  
...  

임을 확인할 수 있다.

 

즉, 현재의 상태 $a_i$에 대하여 $2^k$세대 이후의 상태는
$a_i ' = a_i + a_{(i + 2^k) \space mod \space N} \space (0 \leq i < N)$이다. 각 전이는 서로에 대해 독립적이므로
$M$을 2의 거듭제곱으로 분해하여 진행하면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

int N, M, a[1000005], b[1000005];

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>N>>M;
    for (int i = 0; i < N; i++) cin>>a[i];
    for (int bit = 1; bit <= M; bit<<=1) {
        if (!(bit & M)) continue;
        for (int i = 0; i < N; i++) b[i] = (a[i] + a[(i+bit)%N])%2;
        for (int i = 0; i < N; i++) a[i] = b[i];
    }
    for (int i = 0; i < N; i++) cout<<a[i]<<"\n";
}