The Qubit Returns

네 상태를 각각 $0,1,2,3$으로 나타내자. 각 게이트의 상태 변화는 다음 순열로 표현할 수 있다.

• H: $(2,3,0,1)$
• X: $(1,0,2,3)$
• Z: $(0,1,3,2)$

왼쪽 끝 $l$을 고정하고 오른쪽 끝 $r$을 $l$부터 $N$까지 늘린다. 처음에는 네 상태의 결과가 각각 $0,1,2,3$이다. $$번째 게이트를 추가할 때 네 결과에 해당 게이트의 순열을 적용한다. 네 결과가 다시 이 되면 구간 을 답에 추가한다.

모든 $l$에 대해 같은 과정을 반복한다. 시간 복잡도는 $O(N^2)$이고, 추가 공간 복잡도는 $O(1)$이다.

Solution written by GPT6