IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
104 . 迷宮設置
TopCoder
Tags
Description
朱拉．坦派斯特聯邦國的迷宮最近被天使大軍弄得一團亂，利姆路決定要來增強迷宮的強度。迷宮一共由 $N$ 個空間組成，其中第一個空間是入口，其他的空間則必須透過設置在另一個空間內的傳送門才能進入。
利姆路每次會挑選一個擁有特定戰力及魔力的惡魔派到某個空間。當一個惡魔進入了某個空間後，如果它的魔力用完了，它就會停在那間空間內；如果它還有魔力，它就會消耗一點魔力後分身成無數個擁有相同魔力與戰力的「並列存在」，並且從空間中消失，之後每個並列存在會沿著那間空間內的某個傳送門前往另一個空間，不過每次一道傳送門只能有一個並列存在通過，而多出來的並列存在會直接消失。擁有魔力的並列存在進到新的空間後也會繼續進行分身。
為了好好配置迷宮的戰力，在一個惡魔的每個並列存在都停下或消失後，那些停下的並列存在會回報它們所在的空間的總戰力，讓利姆路決定下次要如何派遣惡魔。總戰力包含那些空間內的初始戰力以及每個停在那些空間內的並列存在的戰力總和。
Input Format
輸入第一行包含兩個正整數 $N, Q$，分別代表空間數量及派遣次數。
第二行包含 $N$ 個整數 $s_1, s_2, \ldots, s_N$，其中 $s_i$ 代表第 $i$ 個空間的初始戰力。
第三行包含 $N-1$ 個整數 $d_2, d_3, \ldots, d_N$，其中 $d_i$ 代表通往第 $i$ 個空間的傳送門位於哪個空間內。
接下來有 $Q$ 行，第 $i$ 行包含六個整數 $u_i, v_i, w_i, x_i, y_i, z_i$，代表第 $i$ 次派遣惡魔的策略，假設前一次惡魔回報的總戰力為 $last_{i-1}$，則這次派出的惡魔擁有 $(u_i \times last_{i-1} + v_i) \mod 10^ 6$ 的戰力、$(w_i \times last_{i-1} + x_i) \mod N$ 的魔力，並且會派到第 $((y_i \times last_{i-1} + z_i) \mod N) + 1$ 個空間。第一次派遣時，$last_0$ 為 $0$。
- $2 \leq N, Q \leq 5 \times 10^ 5$
- $0 \leq s_i \leq 10^ 6$
- $1 \leq d_i \leq N$
- $0 \leq u_i, v_i, w_i, x_i, y_i, z_i \leq 10^ 6$
- 從入口出發能經過一些傳送門到達任何一間空間
- 保證每次至少有一個並列存在不會消失
Output Format
在每一次派遣後，輸出一行包含一個整數代表這次的並列存在停留位置的總戰力。
Sample Input 1
0 0 0 3 2 1
6 6 1 3 4
0 6 5 0 8 4
7 4 6 1 0 2
1 0 6 2 1 1
Sample Output 1
68
136
Sample Input 2
0 1 2 0 3 1 1 1 4 3
9 6 8 6 9 6 1 4 7
5 8 5 1 2 6
2 5 7 5 3 0
5 8 5 0 9 5
2 1 2 3 7 0
3 7 3 2 6 0
2 3 7 4 8 5
Sample Output 2
56
299
603
3688
7678
Hints
Problem Source
IOICamp 2023 Day2 pD
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 2~30 | $u_i, w_i, y_i = 0$ | 40 |
| 3 | 0~59 | 無其他限制 | 60 |