Floccinaucinihilipilification

어떤 쌍을 세어야 하는가

처음부터 있던 바이러스를 기존 바이러스, 변화 중에 추가된 바이러스를 신규 바이러스라고 하자. 기존 바이러스끼리의 쌍은 두 멸종 위험도에 똑같이 포함된다. 따라서 답은 신규 바이러스를 적어도 하나 포함하는 순서 없는 쌍들의 유사도 합이다. 모든 항이 음이 아니므로 전체 위험도에서 기존 바이러스만의 위험도를 빼면 된다.

문자열들을 트라이에 저장하자. 루트가 아닌 각 노드는 하나의 비어 있지 않은 접두사를 나타낸다. 두 문자열의 공통 접두사에 속하는 노드 수는 그 두 문자열의 유사도이다. 어떤 노드의 서브트리에 기존 바이러스가 $o$개, 신규 바이러스가 $a$개 있다면 그 노드의 기여는

$$F(o,a)=oa+\binom{a}{2}=oa+\cfrac{a(a-1)}{2}.$$

따라서 루트를 제외한 모든 노드의 $F$를 합하면 답을 얻는다. 신규 바이러스끼리의 쌍은 한 번만 세어야 한다. 구조가 같은 서로 다른 바이러스도 각각 개수에 포함한다.

서브태스크 1: 직접 시뮬레이션

매 변화마다 모든 문자열을 직접 바꾸고 신규 바이러스를 추가한다. 적어도 한쪽이 신규인 모든 쌍에 대해 최장 공통 접두사를 직접 구한다. $B=\sum x_i$, $H=\max |V_i|+M$이라 하면 시간 복잡도는 , 메모리 복잡도는 이다. 이 서브태스크에서는 , 이다.

서브태스크 2: 변화 한 번

유일한 변화를 $cx$라 하자. 변화 이후 $c$로 시작하는 기존 바이러스의 수를 $k$라 하면 답은 $kx+\binom{x}{2}$이다. 기존 문자열이 원래 로 시작하지 않거나, 앞의 두 글자가 모두 일 때만 변화 이후 로 시작한다. 한 글자인 문자열은 빈 문자열이 됨에 유의한다. 라 할 때 시간에 처리한다.

서브태스크 3: 문자 A만 사용

신규 바이러스의 구조는 항상 빈 문자열 또는 한 글자 문자열이다. 길이가 양수인 기존 바이러스의 수와 한 글자인 신규 바이러스의 수를 각각 $o,a$라 하면 답은 $F(o,a)$이다.

처음 길이가 $\ell$인 기존 바이러스는 $\ell$번의 변화 후 처음으로 빈 문자열이 된다. 그 뒤에는 빈 문자열과 한 글자 문자열을 번갈아 갖는다. 길이별 빈도를 구하고, 현재 시점까지 처음 빈 문자열에 도달한 기존 바이러스를 길이의 홀짝에 따라 누적한다. $i$번째 시점에 빈 문자열인 기존 바이러스는 길이가 $i$ 이하이고 길이의 홀짝이 $i$와 같은 바이러스이다.

$t$번째 변화에서 추가된 바이러스는 $i-t$가 짝수일 때 한 글자이다. 추가된 수 역시 생성 시점의 홀짝별로 누적한다. 전체 시간 복잡도는 $O(L+M)$이고, 메모리 복잡도는 $O(L)$이다.

트라이의 루트 이동

현재 루트를 $r$, 변화 문자를 $c$라 하자. $r$의 $c$ 자식을 $s$라고 하자. 자식이 없다면 빈 노드를 하나 만든다.

루트를 $r$에서 $s$로 옮기면, 원래 $c$로 시작하던 문자열은 맨 앞의 $c$를 잃는다. 나머지 문자열은 새 루트 아래에서 기존 루트로 향하는 $c$ 간선을 거치므로 맨 앞에 $c$가 추가된다. 기존 루트의 $c$ 자식 연결은 끊어야 한다.

신규 바이러스 $x$개를 추가하는 작업은 루트를 옮기기 전에 기존 루트에 빈 문자열 $x$개를 넣는 것으로 처리할 수 있다. 이 문자열들은 루트 이동 후 정확히 한 글자 문자열 $c$가 된다. 루트에 빈 문자열을 넣는 순간에는 비어 있지 않은 접두사가 추가되지 않으므로 답이 변하지 않는다.

기존 루트의 개수에 신규 $x$개를 반영한 뒤, 이동 전 $s$의 개수를 $(o_s,a_s)$라고 하자. $$는 루트가 되므로 답에서 를 뺀다. 의 개수에서는 의 개수를 빼고, 새로 얻은 의 를 답에 더한다. 의 개수는 전체 바이러스 수로 갱신한다. 이 외의 서브트리는 루트 이동 자체로는 변하지 않는다.

같은 문자로 이어지는 서브트리 병합

$s$에 원래 $c$ 자식 $u$가 있었다면, 새로 $c$ 자식이 되는 $r$과 충돌한다. $u$는 원래 $cc$로 시작하던 문자열을 나타낸다. 두 서브트리는 이제 같은 접두사를 가지므로 병합해야 한다.

노드 $v,w$를 병합할 때에는 답에서 두 노드의 기존 기여를 빼고, 두 개수를 더한 노드의 기여를 더한다. 한쪽에만 있는 자식은 그대로 옮긴다. 같은 문자로 양쪽에 모두 자식이 있으면 그 두 자식도 병합한다.

기준 풀이는 명시적인 작업 스택으로 병합한다. 긴 문자열에서도 호출 스택을 사용하지 않는다. 병합 하나가 수행될 때마다 노드 하나가 더 이상 접근되지 않으므로, 전체 병합 횟수는 생성된 노드 수 이하이다.

초기 트라이는 최대 $L+1$개의 노드이며, 한 변화에서 새로 만드는 노드는 최대 하나이다. 알파벳 크기를 $K$라 하면 전체 시간 복잡도는 $O(K(L+M))$, 메모리 복잡도도 $O(K(L+M))$이다. 전체 문제에서는 이므로 에 대해 선형이다.

서브태스크 4, 5, 6

서브태스크 4와 5의 구현은 위 알고리즘의 자식 배열 크기를 각각 $2$, $6$으로 줄인다. 시간과 메모리 복잡도는 각각 $O(2(L+M))$, $O(6(L+M))$이다.

서브태스크 6에서는 신규 바이러스가 전체 과정에서 정확히 하나만 생긴다. 따라서 항상 $a \leq 1$이고 $\binom{a}{2}=0$이다. 기여를 $oa$만으로 계산하는 트라이 구현으로 해결할 수 있다. 시간과 메모리 복잡도는 이다. 전체 풀이에서는 신규끼리의 쌍을 생략해서는 안 된다.

정수 범위

신규 바이러스는 최대 $B=9M \leq 2\,700\,000$개이다. $i$번째 변화에서 추가된 신규 바이러스의 최종 길이는 $M-i+1$ 이하이다. 기존-신규 쌍의 합은 이하이다. 신규-신규 쌍의 합은 모든 단계에서 개씩 추가하고 기존 신규 문자열의 길이를 매번 늘릴 때 최대가 된다. 그 값은 이다.

따라서 정답의 정확한 최댓값은 $9M(M+1)(N+3M+1)/2$이며, 전체 제약에서 $486\,002\,025\,001\,350\,000$이다. 처음의 모든 문자열을 같은 문자로 채우고, 다른 두 문자로 돌연변이를 번갈아 일으키며 매번 개씩 추가하면 이 상한을 달성한다. 이 식의 나누기 전 중간 곱도 이하로, 부호 있는 비트 정수 범위 안에 있다.

전체 바이러스 수는 $3\,000\,000$ 이하이고, 노드 하나의 기여는 $4\,454\,998\,650\,000$ 이하이다. 기존끼리의 위험도는 $((N-1)L+MN(N-1))/2$ 이하이다. 두 위험도를 따로 계산해도 전체 위험도는 이하로, 부호 있는 비트 정수 범위 안에 있다. 기준 풀이는 접두사의 기여를 직접 누적하므로 위험도의 뺄셈이나 큰 다항식 계산이 필요하지 않다.

트라이 노드 개수는 더미를 포함해 $2\,300\,002$ 이하이다. 기준 풀이는 실제 자식이 존재하는 문자들을 비트마스크에 저장하여 병합 중에 해당 자식만 확인한다. 노드 하나에 $116$바이트를 사용하므로 노드 배열은 약 $255$MiB이다. 배열을 필요한 상한만큼 미리 예약하여 재할당 시 두 배열을 동시에 보관하는 일을 피한다. 병합 스택과 입력 버퍼를 포함해도 $1\,024$MiB 이내에서 처리할 수 있다.

검증기는 정수를 누적하기 전에 범위를 확인한다. 생성기의 시드 해시 중간값은 $2.82\cdot 10^{11}$ 미만이고, 난수 갱신의 곱은 $1.04\cdot 10^{14}$ 미만이다. 생성기의 $N(N+1)$은 이하이다. 모든 채점 코드에서 비트를 넘는 정수형은 필요하지 않다.

Solution written by GPT6