1. 장면 그래프와 고립 장면
파란 조명의 수를 이라고 하자. 가능한 장면을 정점으로, 한 번의 조작으로 서로 바뀌는 장면을 간선으로 하는 장면 그래프를 생각한다. 조작은 가역적이므로 이 그래프는 무방향 그래프이다. 각 연결 성분에서 한 장면씩 저장하면 충분하고, 서로 다른 성분 사이로는 이동할 수 없으므로 최소 저장 수는 연결 성분 수와 같다.
조작이 가능한 장면을 활동 장면, 불가능한 장면을 고립 장면이라고 하자. 조작 직후에도 방금 고른 세 정점을 다시 조작할 수 있으므로 활동 장면에서 고립 장면으로 이동할 수는 없다.
또는 이면 모든 장면이 고립되어 있고 빈칸의 위치만 다르므로 최소 저장 수는 이다. 이하에서는 이라고 가정한다.
빈칸이 에 있고, 에서 거리 또는 인 정점 수가 라고 하자. 장면이 활동 상태일 필요충분조건은 그 정점들에 두 색이 모두 나타나는 것이다. 필요성은 조작 경로에서 바로 따른다. 충분성은 이웃들에 두 색이 있으면 그 두 이웃과 를 고르고, 이웃들이 모두 같은 색이면 거리 의 반대 색 정점까지의 경로를 고르면 된다.
따라서 고립 장면 수는 다음과 같다. 범위를 벗어나는 이항계수는 으로 정의한다.
첫 항은 가까운 정점들이 모두 파란 경우, 둘째 항은 모두 빨간 경우이다. 이므로 두 경우는 겹치지 않는다. 트리에서는 거리 의 정점이 중복되지 않으므로
각 간선의 양 끝점에 상대편 차수를 더하면 모든 를 에 구한다.
2. 갈림길이 있는 트리의 활동 장면들은 연결된다
세 종류를 하나씩 포함하는 길이 의 경로를 활동 경로라고 하자. 두 길이 경로가 한 간선을 공유하고 하나가 활동 상태라면, 그 경로를 순환하여 다른 경로도 활동 상태로 만들 수 있다. 공유 간선의 끝점 중 어느 쪽에 빈칸을 둘지에 따라 다른 끝점의 색이 달라지므로, 새 정점과 반대인 색을 선택하면 된다.
연결된 트리의 길이 경로들은 한 간선을 공유하는 경로들을 거쳐 서로 연결된다. 따라서 활동 장면에서 임의로 지정한 길이 경로를 활동 상태로 만들 수 있다.
중심 와 잎 로 이루어진 네 정점 별을 생각하자. 두 색이 모두 있으면 빈칸을 중심으로 옮길 수 있다. 빨강이 하나일 때 다음 조작으로 빈칸을 중심에 둔 채 빨강의 위치를 바꿀 수 있다. 상태는 순서이다.
차례대로 , 를 조작한다. 색을 바꾸어도 같은 논리가 성립하므로 별의 모든 장면이 연결된다.
갈림길 트리는 이 별에서 시작하여 잎을 하나씩 붙여 만들 수 있다. 이미 정리가 성립하는 갈림길 트리 의 정점 에 새 잎 를 붙였다고 하자. 모든 활동 장면에서 안의 경로를 활동 상태로 만들 수 있다. 그러면 빈칸은 안에 있고, 는 빨강 또는 파랑이다.
가 빨강이며 가 활동 상태인 장면들의 집합을 , 파랑인 집합을 라고 하자. 각 집합 내부는 에 대한 귀납 가정으로 연결된다. 한 색이 하나뿐이면 그 색을 에 둔 집합은 비어 있으므로 하나의 집합만으로 충분하다.
두 색이 각각 두 개 이상이면 두 집합도 연결할 수 있다. 에서 의 이웃 를 고르고, 간선 를 포함하는 연결된 네 정점 부분트리 를 고른다. 를 적절히 이름 붙이면 , 이다. 네 정점 부분트리는 경로 또는 별이므로 직접 확인할 수 있다.
로 놓고 나머지를 요구된 색 개수에 맞추면 의 장면이다. 경로 를 순환하여 로 바꾸면 의 장면이 된다. 전자는 근처의 , 후자는 근처의 때문에 안에서도 활동 상태이다. 따라서 두 집합은 연결되고 귀납이 완성된다.
두 색이 모두 있으면 임의의 길이 경로에 세 종류를 하나씩 놓아 활동 장면을 만들 수 있다. 따라서 차수가 이상인 정점이 있으면 활동 성분은 정확히 개이다.
3. 경로의 불변량과 충분성
트리가 경로라면 한 끝점부터 장면을 문자열로 읽는다. 를 파랑이 빨강보다 앞에 있는 쌍의 수, 를 빈칸 왼쪽의 각 색 개수라고 하자.
이 값은 조작으로 변하지 않는다. 조작 구간 밖의 기여는 바뀌지 않고, 세 칸 내부의 기여는 RB□, B□R, □RB에서 , R□B, □BR, BR□에서 이다. 순환은 각 세 상태 사이에서만 일어난다.
같은 를 가진 활동 장면들이 연결됨도 증명해야 한다. 서로 다른 세 기호 에 대해 다음 변환은 모두 실제 조작으로 가능하다.
XYZX ↔ XXYZ XYZY ↔ YZXY ↔ YXYZ XYZZ ↔ ZXYZ
따라서 세 종류의 묶음을 내부 순서를 유지하면서 옆 기호를 지나 운반할 수 있다. 활동 경로를 맨 앞으로 옮기고 빨강을 맨 앞에 두면 정규형 를 얻는다. 여기서 는 RB□, 은 R□B이고, 는 빨강 개와 파랑 개로 이루어진 문자열이다.
또한 RB□BR ↔ RBR□B 변환과 묶음 운반을 이용하면, 상태에서 의 임의의 인접한 BR을 RB로 바꾸며 상태로 갈 수 있다. 역방향도 가능하다.
의 번째 빨강 앞의 파랑 수를 라고 하면
이 수열은 와 일대일 대응한다. 위 변환은 순서를 유지하며 좌표 하나를 감소 또는 증가시키는 것이다. 를 고정하면 인 합 의 층과 인 합 의 층을 오간다.
이고 합 인 서로 다른 수열 가 있다고 하자. 인 가장 왼쪽 좌표 를 줄이고, 인 가장 오른쪽 좌표 를 늘린다. 첫 변경은 , 둘째 변경은 에 의해 순서를 유지한다. 경계 좌표에서는 각각 의 범위를 지킨다. 인 경우도 이므로 두 좌표의 차이가 적어도 여서 두 변경이 모두 가능하다.
합은 로 바뀌고 가 줄어든다. 따라서 합 인 수열들은 연결된다. 합 인 수열에서는 보다 작은 가장 오른쪽 좌표를 늘리면 합 의 층으로 갈 수 있다. 과 에서는 각각 유일한 정규형만 존재한다. 또는 일 때도 이 두 경계 경우뿐이다.
그러므로 같은 의 활동 장면들은 모두 연결된다. 역전 수는 부터 까지 모든 정숫값을 가질 수 있으므로 는 부터 까지이다. 경로의 활동 성분 수는 정확히 이다.
4. 최소 저장 수와 모듈러 조합 계산
따라서 최소 저장 수 은 다음과 같다.
이 값을 으로 나눈 나머지를 출력한다.
까지의 팩토리얼 와 역팩토리얼 를 모든 테스트 케이스에 대해 한 번만 전처리한다. 는 소수이고 이므로 모든 팩토리얼의 역원이 존재한다. 페르마의 소정리로
를 구하고, 순서로
를 계산한다. 이항계수는
로 에 구한다. 또는 이면 이다.
차수와 모든 를 구한 뒤 각 정점의 두 이항계수를 더하고, 트리가 경로인지에 따라 활동 성분 수를 더한다. 덧셈과 곱셈마다 나머지를 취하므로 거대한 정수를 만들 필요가 없다. 곱셈에는 64비트 정수를 사용한다.
전처리는 시간 , 공간 이다. 각 테스트 케이스는 시간 , 공간 이며, 전체 시간은 이다.
Solution written by GPT6