Difference Pyramid

연산을 한 번 수행해도 모든 원소는 계속 $0,1,2$ 중 하나이다. 따라서 마지막 값도 $0,1,2$ 중 하나이다.

먼저 마지막 값의 홀짝을 구하자. 정수 $x,y$에 대해

$$|x-y|\equiv x+y\pmod 2$$

이다. 따라서 모든 값을 $2$로 나눈 나머지만 보면 한 단계의 연산은 인접한 두 값을 더하는 것과 같다.

이 연산을 $N-1$번 반복하면 파스칼의 삼각형과 같은 계수가 나타난다. 마지막 값의 홀짝 $P$는

$$P\equiv\sum_{i=1}^{N}\binom{N-1}{i-1}A_i\pmod 2$$

이다.

뤼카 정리에 의해

$$\binom{n}{k}$$

가 홀수일 필요충분조건은 $k$의 모든 $1$비트가 $n$에도 존재하는 것이다. 즉,

$$(k\mathbin{\&}n)=k$$

이면 된다.

따라서 $n=N-1$이라 할 때, $(i-1)\mathbin{\&}n=i-1$을 만족하는 위치의 $A_i\bmod2$를 XOR하면 $P$를 $O(N)$에 계산할 수 있다.

$P=1$이면 마지막 값은 홀수이고 가능한 값은 $0,1,2$뿐이므로 정답은 반드시 $1$이다.

이제 $P=0$인 경우를 생각하자. 마지막 값은 $0$ 또는 $2$이다.

마지막 값이 $2$라면 처음 배열에는 $1$이 존재할 수 없다. 이를 배열 길이에 대한 귀납법으로 보일 수 있다. 길이가 $1$이면 자명하다. 길이가 $2$ 이상이고 마지막 값이 $2$라 하자. 첫 연산 뒤의 배열에도 같은 문제를 적용할 수 있으므로 귀납 가정에 의해 첫 연산 뒤의 모든 값은 짝수이다. 따라서 원래 배열의 모든 인접한 두 값은 같은 홀짝을 가지며, 원래 배열의 모든 값의 홀짝이 같다. 모두 홀수라면 모든 값이 $1$이고 첫 연산 뒤부터 전부 $0$이 되어 마지막 값도 $0$이다. 모순이다. 따라서 원래 배열의 모든 값은 $0$ 또는 $2$이다.

그러므로 $P=0$인데 $A_i=1$인 위치가 하나라도 있다면 정답은 $0$이다.

마지막으로 모든 $A_i$가 $0$ 또는 $2$인 경우를 보자. $C_i=A_i/2$라 두면 $C_i$는 $0$ 또는 $1$이다. 또한

$$|2x-2y|=2|x-y|$$

이므로 전체 Difference Pyramid의 모든 값이 정확히 $2$배로 대응한다. 따라서 원래 배열의 마지막 값은 $C$의 마지막 값의 $2$배이다.

$C$는 이진 배열이므로 마지막 값은 $0$ 또는 $1$이고, 앞에서와 같은 이항계수 홀짝 계산으로 정확히 구할 수 있다. 즉,

$$Q\equiv\sum_{i=1}^{N}\binom{N-1}{i-1}\frac{A_i}{2}\pmod2$$

를 구해 정답으로 $2Q$를 출력하면 된다.

전체 배열을 한 번 순회하면서 $P$, $Q$, $1$의 존재 여부를 동시에 계산할 수 있으므로 시간 복잡도는 $O(N)$이고 메모리 복잡도는 $O(1)$이다.

Solution written by GPT5.6