35490번 - [O] Operation: Path Query, Remastered - Static Tree (Updated Version) 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 3 | 3 | 3 | 100.000% |
문제
하이비는 최근 바이히가 만든 두뇌 게임 Operation: Path Query, Remastered - Static Tree (Updated Version)을 플레이하고 있다. 이 게임의 규칙은 다음과 같다.
- $N$개의 정점을 가진 트리가 주어진다. 각 정점에는 $1$번부터 $N$번까지의 번호가 매겨져 있으며, 각 간선에는 $1$번부터 $N-1$번까지의 번호가 매겨져 있다.
- $3N-1$개의 정수 카드와 $N-1$개의 연산자 카드를 사용한다.
- 정수 카드에는 $2$자리의 음이 아닌 정수가 적혀있다. 카드에 적힌 수는 $0$으로 시작할 수 있다.
- 연산자 카드에는 $+$, $-$, $\times$, $\div$ 중 하나의 연산자가 적혀있다.
- $1$ 이상 $N$ 이하의 정수 $v$에 대해, $v$번 정점의 왼쪽에 정수 카드 $A_v$, 오른쪽에 정수 카드 $B_v$를 놓는다.
- $1$ 이상 $N-1$ 이하의 정수 $e$에 대해, $e$번 간선의 왼쪽에 연산자 카드 $P_e$, 오른쪽에 정수 카드 $C_e$를 놓는다.
- 카드를 모두 놓으면 게임이 시작한다. 게임이 진행되면서 다음과 같은 이벤트가 총 $Q$번 발생한다.
- 질문: 두 정점 번호 $x$, $y$가 주어질 때 $x$번 정점에서 출발해서 $y$번 정점으로 끝나는 경로 내의 카드를 모두 나열한 뒤 나오는 수식의 값을 계산해야 한다.
- $A_x$ 변경: 정점 번호 $x$와 정수 $y$가 주어질 때 $x$번 정점의 왼쪽에 놓인 정수 카드를 $y$가 적힌 정수 카드로 변경한다.
- $B_x$ 변경: 정점 번호 $x$와 정수 $y$가 주어질 때 $x$번 정점의 오른쪽에 놓인 정수 카드를 $y$가 적힌 정수 카드로 변경한다.
- $P_x$ 변경: 간선 번호 $x$와 연산자 $y$가 주어질 때 $x$번 간선의 왼쪽에 놓인 연산자 카드를 $y$가 적힌 연산자 카드로 변경한다.
- $C_x$ 변경: 간선 번호 $x$와 정수 $y$가 주어질 때 $x$번 간선의 오른쪽에 놓인 정수 카드를 $y$가 적힌 정수 카드로 변경한다.
- 질문에 답할 때는 아래 사항들을 주의해야 한다.
- 연산자 우선순위는 무시하고 왼쪽에서 오른쪽 순서로 연산한다.
- 경로 내의 카드를 나열할 때는 출발점에서 가까운 정점 또는 간선에 놓인 카드부터 나열해야 한다. 또한, 정점 또는 간선의 왼쪽에 놓인 카드를 오른쪽에 놓인 카드보다 먼저 나열해야 한다. 예를 들어, 경로가 $x$번 정점 → $a$번 간선 → $b$번 정점 → $c$번 간선 → $y$번 정점이라고 하자. 이 경우 $A_x$, $B_x$, $P_a$, $C_a$, $A_b$, $B_b$, $P_c$, $C_c$, $A_y$, $B_y$의 순서대로 카드를 나열해야 한다.
- 정수 카드가 여러 개 연속되어 놓이는 경우, 해당하는 정수를 이어 붙여서 하나의 수로 보아야 한다. 예를 들어, 나열된 카드가 $12$, $57$, $+$, $12$, $03$, $17$이라면 계산해야 하는 값은 $12\, 57+12\, 03\, 17=121\, 374$가 된다.
- $x\div 0$은 $0$으로 계산한다.
예를 들어, 다음과 같은 트리에서 $1$번 정점에서 출발해서 $4$번 정점으로 끝나는 경로 내의 카드를 모두 이어 붙인다고 해보자.
경로 내의 카드를 모두 이어 붙인 뒤 계산하면 $07\,23 + 27\,06\,24 - 35\,13\,26 = -79\,979$가 나온다.
하이비는 이 게임을 자주 플레이하다 보니, 매 플레이마다 모든 질문에 대해 답을 정확히 맞히는 경지에 이르렀다. 이를 바이히에게 증명하기 위해, 하이비는 게임의 진행 과정이 주어질 때 각 질문에 대한 답을 계산해 주는 프로그램을 작성해서 보여주기로 했다.
입력
첫째 줄에는 트리의 정점 개수 $N$과 플레이하는 라운드의 수 $Q$가 공백으로 구분되어 주어진다. $(1\le N,Q\le 500\, 000)$
둘째 줄부터 $N$개의 줄에 걸쳐, $i+1$번째 줄에는 $i$번 정점에 놓인 두 정수 카드 $A_i$와 $B_i$가 공백으로 구분되어 주어진다. $(00\le A_i,B_i\le 99)$
$N+2$번째 줄부터 $N-1$개의 줄에 걸쳐, $i+N+1$번째 줄에는 $i$번 간선이 잇는 두 정점 $v_i$, $w_i$과 해당 간선에 놓인 연산자 카드 $P_i$, 정수 카드 $C_i$가 공백으로 구분되어 주어진다. $(1\le v_i,w_i\le N;$ $00\le C_i\le 99;$ $P_i$는 $+$, $-$, $\times$, $\div$ 중 하나$)$
$2N+1$번째 줄부터 $Q$개의 줄에 걸쳐 문제에서 나오는 이벤트를 의미하는 글자 $t$와 이벤트를 나타내는 두 값 $x$, $y$가 공백으로 구분되어 주어진다.
- $t=$
?: 질문 이벤트이다. 이때 $x$, $y$는 $1 \le x, y \le N$를 만족하는 정수이다. - $t=$
A: $A_x$ 변경 이벤트이다. 이때 $x$, $y$는 $1 \le x \le N;$ $00 \le y \le 99$를 만족하는 정수이다. - $t=$
B: $B_x$ 변경 이벤트이다. 이때 $x$, $y$는 $1 \le x \le N;$ $00 \le y \le 99$를 만족하는 정수이다. - $t=$
P: $P_x$ 변경 이벤트이다. 이때 $x$는 $1 \le x \le N-1$를 만족하는 정수이고, $y$는 $+$, $-$, $\times$, $\div$ 중 하나이다. - $t=$
C: $C_x$ 변경 이벤트이다. 이때 $x$, $y$는 $1 \le x \le N-1;$ $00 \le y \le 99$를 만족하는 정수이다.
정수 카드에 적히는 수는 항상 $2$자리 정수로 주어진다. 이를 위해 앞에 불필요한 $0$이 붙을 수 있다.
연산자 카드에 적히는 연산자 $+$, $-$, $\times$, $\div$은 각각 글자 +, -, *, /로 주어진다.
출력
각 질문 이벤트에 대해 질문의 답을 기약분수로 나타낸 값을 $p/q$라고 하자. 이때, $qr\equiv p\pmod{1\, 208\, 017}$을 만족하는 $0$ 이상 $1\, 208\, 017$ 미만인 정수 $r$을 출력한다. 문제의 제한 내에서 이 정수는 각 질문에 대해 유일함을 보일 수 있다.
$1\, 208\, 017$은 소수이다.
예제 입력 1
5 6 07 23 27 63 06 24 13 26 92 31 1 3 + 27 3 4 - 35 3 5 + 14 2 5 / 16 ? 1 4 A 1 87 P 3 * B 5 09 C 4 61 ? 2 1
예제 출력 1
1128038 975864
처음 들어오는 질문은 $1$번 정점에서 $4$번 정점으로 가는 경로 위의 카드를 나열해야 한다. 이를 나열하면 $07\, 23+27\, 06\, 24-35\, 13\, 26$이 나오고, 이 값은 $-79\, 277$이다. 이때 $1\cdot 1\, 128\, 038\equiv -79\, 979\pmod{1\, 208\, 017}$이므로, $1\, 128\, 038$을 출력하면 된다.
이후 $4$번의 카드 변경 이벤트가 주어진다.
이후로 들어오는 질문은 $2$번 정점에서 $1$번 정점으로 가는 경로 위의 카드를 나열해야 한다. 이를 나열하면 $27\, 63\div 61\, 92\, 09\times 14\, 06\, 24+27\, 87\, 23$이 나오고, 이 값은 $\displaystyle \frac{19\, 219\, 592\, 691}{68\, 801}$이다. 이때 $68\, 801\cdot 975\, 864\equiv 19\, 219\, 592\, 691\pmod{1\, 208\, 017}$이므로, $975\, 864$를 출력하면 된다.
출처
- 문제를 만든 사람: hibye1217
- 문제를 검수한 사람: gubshig, iktk, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호