이진수 도장

각 문자열을 $\mathbb{F}_2$ 위의 벡터로 생각하자. 어떤 도장을 한 위치에 찍는 것은 길이 $n$인 벡터 하나를 XOR하는 것과 같다. 따라서 가능한 모든 연산 결과는 도장들을 가능한 위치에 놓아 얻는 벡터들의 선형생성공간이다. 문제는 $s$가 이 선형생성공간에 속하는지 묻는 것이다.

이를 직접 가우스 소거하면 벡터 길이가 너무 길다. 대신 쌍대공간을 본다. 길이 $n$인 벡터 $y$가 모든 도장 벡터와 내적이 $0$이라면, $y$는 다음 조건을 만족한다.

$$\sum_{j=0}^{|t_i|-1} t_i[j+1]y_{l+j}=0$$

모든 $i \in \{1,2,3\}$와 가능한 모든 시작 위치 $l$에 대해 위 식이 성립해야 한다.

$L=\max(a,b,c)-1$이라 하자. 가장 긴 도장 하나를 고르면, 그 도장의 마지막 문자가 1이므로 $y_p$ ($p \geq L$)는 이전 $L$개의 값의 XOR로 결정된다. 따라서 모든 $y_p$는 처음 $L$개의 변수 $x_0,x_1,\cdots,x_{L-1}$의 선형식으로 표현된다. 여기서 $L \leq 99$이다.

이제 모든 도장 조건을 이 $L$개의 변수에 대한 선형 방정식으로 추가한다. 또한 $s$와 $y$의 내적도 $L$개의 변수에 대한 선형식 하나로 계산한다. 선형대수의 기본 성질에 의해 $s$가 도장 벡터들의 선형생성공간에 속할 필요충분조건은, $s$와 $y$의 내적 선형식이 추가한 방정식들의 행공간에 속하는 것이다.

$L \leq 99$이므로 각 선형식은 128비트 정수 하나로 저장할 수 있다. 각 위치마다 세 도장 조건만 처리하면 되므로 시간 복잡도는 $O(n(a+b+c))$, 메모리 복잡도는 $O(n)$이다.

Solution written by GPT5.5