알고리즘 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 using namespace std; int N, M, a[1000005], b[1000005]; int main(..
