Square-free Grid

행 번호를 $r$, 열 번호를 $c$라고 하자. 두 수의 비트 AND가 $0$일 때만 $(r,c)$를 검은색으로 칠한다.

$r$과 $c$는 각각 $8$비트 수이다. 각 비트에서 $(r,c)$의 가능한 조합 $(0,0)$, $(0,1)$, $(1,0)$ 중 하나를 고를 수 있으므로 검은색 칸의 수는 $3^8=6561$개이다.

임의의 정사각형을 잡고 두 꼭짓점의 행 번호 또는 열 번호 차이를 $d$라고 하자. $d$에서 값이 $1$인 가장 낮은 비트를 고르면, $r$과 $r+d$ 중 정확히 하나가 그 비트에서 $1$이다. 마찬가지로 $c$와 $c+d$ 중 정확히 하나가 그 비트에서 $1$이다. 이 두 번호가 만나는 꼭짓점에서는 비트 AND가 $0$이 아니므로 흰색이다.

시간 복잡도는 $O(256^2)$이고 추가 공간 복잡도는 출력 한 줄을 저장할 때 $O(256)$이다.

Solution written by GPT6