DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

정원의 첫 장면

문제로 돌아가기

해설

1. 장면 그래프와 고립 장면

파란 조명의 수를 B=N−1−RB=N-1-RB=N−1−R이라고 하자. 가능한 장면을 정점으로, 한 번의 조작으로 서로 바뀌는 장면을 간선으로 하는 장면 그래프를 생각한다. 조작은 가역적이므로 이 그래프는 무방향 그래프이다. 각 연결 성분에서 한 장면씩 저장하면 충분하고, 서로 다른 성분 사이로는 이동할 수 없으므로 최소 저장 수는 연결 성분 수와 같다.

조작이 가능한 장면을 활동 장면, 불가능한 장면을 고립 장면이라고 하자. 조작 직후에도 방금 고른 세 정점을 다시 조작할 수 있으므로 활동 장면에서 고립 장면으로 이동할 수는 없다.

R=0R=0R=0 또는 B=0B=0B=0이면 모든 장면이 고립되어 있고 빈칸의 위치만 다르므로 최소 저장 수는 NNN이다. 이하에서는 R,B≥1R,B\geq1R,B≥1이라고 가정한다.

빈칸이 vvv에 있고, vvv에서 거리 111 또는 222인 정점 수가 kvk_vkv​라고 하자. 장면이 활동 상태일 필요충분조건은 그 정점들에 두 색이 모두 나타나는 것이다. 필요성은 조작 경로에서 바로 따른다. 충분성은 이웃들에 두 색이 있으면 그 두 이웃과 를 고르고, 이웃들이 모두 같은 색이면 거리 의 반대 색 정점까지의 경로를 고르면 된다.

따라서 고립 장면 수는 다음과 같다. 범위를 벗어나는 이항계수는 000으로 정의한다.

F=∑v[(N−1−kvR)+(N−1−kvB)].F=\sum_v\left[\binom{N-1-k_v}{R}+\binom{N-1-k_v}{B}\right].F=v∑​[(R

첫 항은 가까운 정점들이 모두 파란 경우, 둘째 항은 모두 빨간 경우이다. kv≥1k_v\geq1kv​≥1이므로 두 경우는 겹치지 않는다. 트리에서는 거리 222의 정점이 중복되지 않으므로

kv=deg⁡(v)+∑u∼v(deg⁡(u)−1)=∑u∼vdeg⁡(u).k_v=\deg(v)+\sum_{u\sim v}(\deg(u)-1)=\sum_{u\sim v}\deg(u).kv​=deg(v)+

각 간선의 양 끝점에 상대편 차수를 더하면 모든 kvk_vkv​를 O(N)O(N)O(N)에 구한다.

2. 갈림길이 있는 트리의 활동 장면들은 연결된다

세 종류를 하나씩 포함하는 길이 222의 경로를 활동 경로라고 하자. 두 길이 222 경로가 한 간선을 공유하고 하나가 활동 상태라면, 그 경로를 순환하여 다른 경로도 활동 상태로 만들 수 있다. 공유 간선의 끝점 중 어느 쪽에 빈칸을 둘지에 따라 다른 끝점의 색이 달라지므로, 새 정점과 반대인 색을 선택하면 된다.

연결된 트리의 길이 222 경로들은 한 간선을 공유하는 경로들을 거쳐 서로 연결된다. 따라서 활동 장면에서 임의로 지정한 길이 222 경로를 활동 상태로 만들 수 있다.

중심 ccc와 잎 a,b,da,b,da,b,d로 이루어진 네 정점 별을 생각하자. 두 색이 모두 있으면 빈칸을 중심으로 옮길 수 있다. 빨강이 하나일 때 다음 조작으로 빈칸을 중심에 둔 채 빨강의 위치를 바꿀 수 있다. 상태는 (c,a,b,d)(c,a,b,d)(c,a,b,d) 순서이다.

(□,R,B,B)⟶(R,B,B,□)⟶(□,B,R,B).(\square,R,B,B)\longrightarrow(R,B,B,\square)\longrightarrow(\square,B,R,B).(□,R,B,B)⟶(R,B,B,□)⟶(

차례대로 a−c−da-c-da−c−d, b−c−db-c-db−c−d를 조작한다. 색을 바꾸어도 같은 논리가 성립하므로 별의 모든 장면이 연결된다.

갈림길 트리는 이 별에서 시작하여 잎을 하나씩 붙여 만들 수 있다. 이미 정리가 성립하는 갈림길 트리 G′G'G′의 정점 uuu에 새 잎 vvv를 붙였다고 하자. 모든 활동 장면에서 G′G'G′ 안의 경로를 활동 상태로 만들 수 있다. 그러면 빈칸은 안에 있고, 는 빨강 또는 파랑이다.

vvv가 빨강이며 G′G'G′가 활동 상태인 장면들의 집합을 SR\mathcal S_RSR​, 파랑인 집합을 SB\mathcal S_B라고 하자. 각 집합 내부는 에 대한 귀납 가정으로 연결된다. 한 색이 하나뿐이면 그 색을 에 둔 집합은 비어 있으므로 하나의 집합만으로 충분하다.

두 색이 각각 두 개 이상이면 두 집합도 연결할 수 있다. G′G'G′에서 uuu의 이웃 www를 고르고, 간선 u−wu-wu−w를 포함하는 연결된 네 정점 부분트리 {u,w,를 고른다. 를 적절히 이름 붙이면 , 이다. 네 정점 부분트리는 경로 또는 별이므로 직접 확인할 수 있다.

v=R,u=B,w=□,x=R,y=Bv=R,u=B,w=\square,x=R,y=Bv=R,u=B,w=□,x=R,y=B로 놓고 나머지를 요구된 색 개수에 맞추면 의 장면이다. 경로 를 순환하여 로 바꾸면 의 장면이 된다. 전자는 근처의 , 후자는 근처의 때문에 안에서도 활동 상태이다. 따라서 두 집합은 연결되고 귀납이 완성된다.

두 색이 모두 있으면 임의의 길이 222 경로에 세 종류를 하나씩 놓아 활동 장면을 만들 수 있다. 따라서 차수가 333 이상인 정점이 있으면 활동 성분은 정확히 111개이다.

3. 경로의 불변량과 충분성

트리가 경로라면 한 끝점부터 장면을 문자열로 읽는다. III를 파랑이 빨강보다 앞에 있는 쌍의 수, rleft,bleftr_{\mathrm{left}},b_{\mathrm{left}}rleft​,bleft​를 빈칸 왼쪽의 각 색 개수라고 하자.

Q=I+rleft−bleft.Q=I+r_{\mathrm{left}}-b_{\mathrm{left}}.Q=I+rleft​−b

이 값은 조작으로 변하지 않는다. 조작 구간 밖의 기여는 바뀌지 않고, 세 칸 내부의 기여는 RB□, B□R, □RB에서 000, R□B, □BR, BR□에서 111이다. 순환은 각 세 상태 사이에서만 일어난다.

같은 QQQ를 가진 활동 장면들이 연결됨도 증명해야 한다. 서로 다른 세 기호 X,Y,ZX,Y,ZX,Y,Z에 대해 다음 변환은 모두 실제 조작으로 가능하다.

XYZX ↔ XXYZ XYZY ↔ YZXY ↔ YXYZ XYZZ ↔ ZXYZ

따라서 세 종류의 묶음을 내부 순서를 유지하면서 옆 기호를 지나 운반할 수 있다. 활동 경로를 맨 앞으로 옮기고 빨강을 맨 앞에 두면 정규형 PeUP_eUPe​U를 얻는다. 여기서 P0P_0P0​는 RB□, P1P_1P은 R□B이고, 는 빨강 개와 파랑 개로 이루어진 문자열이다.

vvv
222
N−1−kv​
​
)
+
(BN−1−kv​​)
]
.
u∼v
∑
​
(
deg
(
u
)
−
1)=
u∼v∑​deg(u).
□
,
B
,
R
,
B
)
.
G′G'
G′
vvv
SB​
G′G'G′
vvv
x,y}\{u,w,x,y\}
{u,w,x,y}
x,yx,yx,y
dist⁡(w,x)≤2\operatorname{dist}(w,x)\leq2dist(w,x)≤2
dist⁡(u,y)≤2\operatorname{dist}(u,y)\leq2dist(u,y)≤2
SR\mathcal S_R
SR​
v−u−wv-u-wv−u−w
v=B,u=□,w=Rv=B,u=\square,w=Rv=B,u=□,w=R
SB\mathcal S_BSB​
www
u,xu,xu,x
uuu
w,yw,yw,y
G′G'G′
left
​
.
1​
UUU
r=R−1r=R-1r=R−1
s=B−1s=B-1s=B−1
Q(PeU)=r+inv⁡(U)+e.Q(P_eU)=r+\operatorname{inv}(U)+e.Q(Pe​U)=r+inv(U)+e.

또한 RB□BR ↔ RBR□B 변환과 묶음 운반을 이용하면, P0P_0P0​ 상태에서 UUU의 임의의 인접한 BR을 RB로 바꾸며 P1P_1P1​ 상태로 갈 수 있다. 역방향도 가능하다.

UUU의 iii번째 빨강 앞의 파랑 수를 xix_ixi​라고 하면

0≤x1≤⋯≤xr≤s,inv⁡(U)=∑ixi.0\leq x_1\leq\cdots\leq x_r\leq s,\qquad\operatorname{inv}(U)=\sum_i x_i.0≤x1​≤⋯≤xr​≤s,inv(U)=i∑​xi​.

이 수열은 UUU와 일대일 대응한다. 위 변환은 순서를 유지하며 좌표 하나를 111 감소 또는 증가시키는 것이다. h=Q−rh=Q-rh=Q−r를 고정하면 e=0e=0e=0인 합 hhh의 층과 e=1e=1e=1인 합 h−1h-1h−1의 층을 오간다.

1≤h≤rs1\leq h\leq rs1≤h≤rs이고 합 hhh인 서로 다른 수열 x,yx,yx,y가 있다고 하자. xi>yix_i>y_ixi​>yi​인 가장 왼쪽 좌표 iii를 111 줄이고, xj<yjx_j<y_jxj​<yj​인 가장 오른쪽 좌표 jjj를 111 늘린다. 첫 변경은 xi−1≤yi−1≤yi<xix_{i-1}\leq y_{i-1}\leq y_i<x_ixi−1​≤yi−1​≤y, 둘째 변경은 xj<yj≤yj+1≤xj+1x_j<y_j\leq y_{j+1}\leq x_{j+1}xj​<yj​≤y에 의해 순서를 유지한다. 경계 좌표에서는 각각 0,s0,s0,s의 범위를 지킨다. i=j+1i=j+1i=j+1인 경우도 xj<yj≤yi<xix_j<y_j\leq y_i<x_ixj​<yj​≤yi​이므로 두 좌표의 차이가 적어도 222여서 두 변경이 모두 가능하다.

합은 h→h−1→hh\to h-1\to hh→h−1→h로 바뀌고 ∑i∣xi−yi∣\sum_i|x_i-y_i|∑i​∣xi​−yi​∣가 222 줄어든다. 따라서 합 hhh인 수열들은 연결된다. 합 h−1h-1h−1인 수열에서는 sss보다 작은 가장 오른쪽 좌표를 늘리면 합 hhh의 층으로 갈 수 있다. h=0h=0h=0과 h=rs+1h=rs+1h=rs+1에서는 각각 유일한 정규형만 존재한다. r=0r=0r=0 또는 s=0s=0s=0일 때도 이 두 경계 경우뿐이다.

그러므로 같은 QQQ의 활동 장면들은 모두 연결된다. 역전 수는 000부터 rsrsrs까지 모든 정숫값을 가질 수 있으므로 hhh는 000부터 rs+1rs+1rs+1까지이다. 경로의 활동 성분 수는 정확히 (R−1)(B−1)+2(R-1)(B-1)+2(R−1)(B−1)+2이다.

4. 최소 저장 수와 모듈러 조합 계산

따라서 최소 저장 수 MMM은 다음과 같다.

  • R=0R=0R=0 또는 B=0B=0B=0이면 M=NM=NM=N.
  • 두 색이 모두 있고 트리가 경로이면 M=F+(R−1)(B−1)+2M=F+(R-1)(B-1)+2M=F+(R−1)(B−1)+2.
  • 두 색이 모두 있고 갈림길이 있으면 M=F+1M=F+1M=F+1.

이 값을 P=998244353P=998244353P=998244353으로 나눈 나머지를 출력한다.

L=200000L=200000L=200000까지의 팩토리얼 fact[i]=i! mod P\mathrm{fact}[i]=i!\bmod Pfact[i]=i!modP와 역팩토리얼 invfact[i]=(i!)−1 mod P\mathrm{invfact}[i]=(i!)^{-1}\bmod Pinvfact[i]=(i!)−1modP를 모든 테스트 케이스에 대해 한 번만 전처리한다. PPP는 소수이고 L<PL<PL<P이므로 모든 팩토리얼의 역원이 존재한다. 페르마의 소정리로

invfact[L]=fact[L]P−2 mod P\mathrm{invfact}[L]=\mathrm{fact}[L]^{P-2}\bmod Pinvfact[L]=fact[L]P−2modP

를 구하고, i=L,L−1,…,1i=L,L-1,\ldots,1i=L,L−1,…,1 순서로

invfact[i−1]=i⋅invfact[i] mod P\mathrm{invfact}[i-1]=i\cdot\mathrm{invfact}[i]\bmod Pinvfact[i−1]=i⋅invfact[i]modP

를 계산한다. 이항계수는

(nr)=fact[n]⋅invfact[r]⋅invfact[n−r] mod P\binom nr=\mathrm{fact}[n]\cdot\mathrm{invfact}[r]\cdot\mathrm{invfact}[n-r]\bmod P(rn​)=fact[n]⋅invfact[r]⋅invfact[n−r]modP

로 O(1)O(1)O(1)에 구한다. r<0r<0r<0 또는 r>nr>nr>n이면 000이다.

차수와 모든 kvk_vkv​를 구한 뒤 각 정점의 두 이항계수를 더하고, 트리가 경로인지에 따라 활동 성분 수를 더한다. 덧셈과 곱셈마다 나머지를 취하므로 거대한 정수를 만들 필요가 없다. 곱셈에는 64비트 정수를 사용한다.

전처리는 시간 O(L+log⁡P)O(L+\log P)O(L+logP), 공간 O(L)O(L)O(L)이다. 각 테스트 케이스는 시간 O(N)O(N)O(N), 공간 O(N)O(N)O(N)이며, 전체 시간은 O(L+log⁡P+∑N)O(L+\log P+\sum N)O(L+logP+∑N)이다.

Solution written by GPT6

i
​
<
xi​
j+1
​
≤
xj+1​
<
xi​