# Problem setters

A. 謝旻錚
B. 郭軒語
C. 郭軒語
D. 何凱鈞
E. 何凱鈞
F. 謝旻錚
G. 盛宇航
H. 盛宇航
I. 郭軒語
J. 謝旻錚
K. 謝旻錚
L. 郭軒語

# Animal Farm

## 題敘

動物農莊要挑選一個領導集團，在滿足：
1. 不能夠有兩隻豬，怕彼此意見相左。
2. 不能夠挑比豬更有影響力的動物。

的條件下，要找總和影響力最大的領導集團。

## 解法

先找出最有影響力的豬，再把所有影響力不及那隻豬的動物全部選進集團。時間複雜度 $O(n)$ 。

## 陷阱

只用 32-bit 整數會 overflow ，請用 Python 或是 64-bit 整數。

# Business Magic

本題有多種解法，以下是出題者知道可以通過此題的三種作法：

## Solution 1

首先我們有以下分析：如果我們不使用 Blue Magic，只使用 Green Magic 的話，那最大可能總和是 $\sum\limits_{i=1}^{n} |r_i|$，因為我們可以使用 Green magic 在所有 $r_i < 0$ 的項來達到這個最大值。假如我們已經知道 Blue magic 要使用在區間 $[L, R]$ 上，那我們同樣可以透過把 Green magic 施加在沒使用過 Blue Magic 且滿足 $r_i < 0$ 的項上，來得到最大可能總和。

透過以上分析就能得到一個 $\mathcal{O}(n^3)$ 的演算法了：

* 不使用 Blue Magic 時最大總和是 $\sum\limits_{i = 1}^{n} |r_i|$。
* 假如使用了 Blue magic，枚舉 Blue Magic 使用的區間 $[L,R]$，此時產生的最大可能總和是 $\sum\limits_{i = 1}^{L - 1} |r_i| + 2\sum\limits_{i=L}^{R} r_i + \sum\limits_{i = R + 1}^{n} |r_i|$，取所有可能總和的最大值。
* 取以上兩種情況的最大值。

但是這個演算法在時間限制下無法通過，需要優化。最耗時間的是第二的 case，我們考慮以下優化方法：

* 計算前綴和後綴總和，這樣枚舉區間時只需要 $\mathcal{O}(1)$ 就能算出總和。具體來說需要算出 $|r_i|$ 的前綴和和後綴和，以及 $r_i$ 的前綴和。
* 注意到 $\sum\limits_{i = 1}^{L - 1} |r_i| + 2\sum\limits_{i=L}^{R} r_i + \sum\limits_{i = R + 1}^{n} |r_i|$ 可以改寫成 $\left(\sum\limits_{i = R + 1}^{n} |r_i| + 2\sum\limits_{i = 1}^{R} r_i\right) - \left(2\sum\limits_{i = 1}^{L - 1} r_i - \sum\limits_{i = 1}^{L - 1} |r_i|\right)$，所以我們可以使用以下枚舉策略：枚舉 $R$，並且找到 $L$ 使得 $L < R$ 且 $2\sum\limits_{i = 1}^{L - 1} r_i - \sum\limits_{i = 1}^{L - 1} |r_i|$ 最小，只使用這個 $L$ 來更新答案。假設 $R$ 是以遞增順序枚舉，那最小的 $L$ 也可以在枚舉的時候順便算出來，這樣枚舉就能在 $\mathcal{O}(n)$ 時間內就能算完。

整體時間複雜度為 $\mathcal{O}(n)$。

## Solution 2

這題其實與最大連續和問題有緊密的關聯。事實上可以證明以下結論：令 $b$ 為一個新序列滿足：

$b_i =
\begin{cases}
r_i & \quad \text{if } r_i \geq 0\\
3 r_i & \quad \text{if } r_i < 0
\end{cases}$

則 $\sum\limits_{i = 1}^{n} |r_i|$ 加上 $b$ 的最大連續和就是答案。直觀上可以這樣理解：假如都不使用 Blue Magic，那最大總和就是 $\sum\limits_{i = 1}^{n} |r_i|$。要使用 Blue Magic 的話，對於區間內所有正的 $r_i$ 會多出 $r_i$ 的總和，但是對於區間內負的 $r_i$ 反而需要扣 $3 |r_i|$ 的總和（因為原本的價值是 $|r_i|$，在他身上使用 Blue Magic，他的價值會變成 $-2|r_i|$，所以是扣 $3 |r_i|$），取會加上最大價值的區間即可。

整題時間複雜度會是 $\mathcal{O}(n)$ 或 $\mathcal{O}(n \log n)$，取決於計算最大連續和的方法而定。

## Solution 3

這題也可以使用動態規劃的方式解決。首先我們同樣觀察到在固定 $[L,R]$ 後，可以在 $r_i < 0$ 的項使用 Green magic 達到最大值。

我們由左而右考慮每一項被 Magic 施加的情形。令 $\text{dp}[i][\cdot]$ 代表序列前 $i$ 項的最大值。其中，$\text{dp}[i][ 0]$ 代表在第 $i$ 項前尚未使用 Blue Magic 的最大可能總和，$\text{dp}[i][1]$ 代表第 $i$ 項有使用 Blue Magic 的最大可能總和，$\text{dp}[i][2]$ 代表第 $i$ 項沒有使用 Blue Magic，且第 $i$ 項前已經使用過 Blue Magic 的最大可能總和。遞迴式如下：

\begin{cases}
\text{dp}[i][0] = \text{dp}[i-1][0] + |r_i|\\
\text{dp}[i][1] = \max\left(\text{dp}[i-1][0], \text{dp}[i - 1][1]\right) + 2 r_i\\
\text{dp}[i][2] = \max(\text{dp}[i - 1][1] + \text{dp}[i - 1][2]) + |r_i|
\end{cases}

式子中的 $|r_i|$ 代表如果沒有使用 Blue Magic，則會對 $r_i<0$ 的項使用 Green magic。最後取 $\text{dp}[n][\cdot]$ 的最大值即可。整題時間複雜度會是 $\mathcal{O}(n)$。

# Cards

題目給定兩個 $1$ 到 $n$ 之間的排列 $a$ 和 $b$，要求找到另一個 $1$ 到 $n$ 之間的排列 $p$，使得 $a'=[a_{p_1},a_{p_2},\cdots,a_{p_n}]$ 和 $b' = [b_{p_1}, b_{p_2},\cdots, b_{p_n}]$ 的逆序數對的數量相同。

首先注意到以下事實：如果 $a$ 和 $b$ 的逆序數對的奇偶性不一樣，那答案是 `No`。因為逆序數對的奇偶性決定[排列的奇偶性](https://zh.wikipedia.org/zh-tw/%E7%BD%AE%E6%8D%A2%E7%9A%84%E5%A5%87%E5%81%B6%E6%80%A7)，反之亦然。如果 $a$ 和 $b$ 的奇偶性，一個是奇排列一個是偶排列，那不論 $p$ 是什麼同樣還會是一個奇排列和一個偶排列。可以這樣理解：從 $p=[1,2,\cdots,n]$ 開始，不斷選定 $i$ 和 $j$，把 $p_i$ 和 $p_j$ 交換，每次交換時，$a$ 和 $b$ 的奇偶性都會改變，所以兩排列奇偶性不可能相同。所以在這種情況下，逆序數對數量的奇偶性不可能相同，所以無解。

否則可以說明其他情況一定有解。為了方便說明，以下我們想像有一個 $2 \times n$ 的表格，第一個 row 填上 $a$ 的值，第二個 row 填上 $b$ 的值，每次操作選定相鄰兩個 column，同時交換第一和第二個 row 的值。

構造如下：我們一開始讓第一個 row 從小到大排好，並且紀錄對應第二個 row 的值。假設第二個 row 此時的逆序數對數量是 $m$。考慮對第二個 row 做 bubble sort 的過程，在經過恰好 $m$ 次交換相鄰 column 的操作以後，第二個 row 會排好序。觀察到在每次交換相鄰 column 時，第一個 row 的逆序數對數量多 $1$，第二個 row 的逆序數對數量少 $1$，所以兩者的差的數量變化是 $2$。一開始兩排列逆序數對數量的差是 $m$，所以只要做交換相鄰 column 的操作恰好 $\frac{m}{2}$ 次，就可以達成目標了。注意到 $m$ 一定會是偶數，所以我們一定會做整數次操作。

以 Sample Input 1 為例，一開始時表格如下：

| 1 | 2 | 3 | 4 | 5 |
| :---: | :---: | :---: | :---: | :---: |
| 5 | 4 | 1 | 3 | 2 |

這個例子 $m = 8$，所以在對第二個 row 排序過程中，做了 $4$ 次交換 column 操作以後，兩排列逆序數對數量相同（第一個表格做了 $2$ 次交換，第二個表格做了 $4$ 次交換）：

| 3 | 1 | 2 | 4 | 5 |
| :---: | :---: | :---: | :---: | :---: |
| 1 | 5 | 4 | 3 | 2 |

| 3 | 1 | 5 | 2 | 4 |
| :---: | :---: | :---: | :---: | :---: |
| 1 | 5 | 2 | 4 | 3 |

綜上說明，我們可以得到以下作法：先讓第一個 row 排序，之後對第二個 row 做 bubble sort，但是只做 $\frac{m}{2}$ 次交換。這個演算法時間複雜度是 $\mathcal{O}(n^2)$，但是我們可以使用資料結構優化：方法是使用線段樹或 Binary Index Tree 等資料結構，對於每個 $i$ 算出把 $b$ 的 $1$ 到 $i$ 拿到前面時需要幾次交換操作，找到做 $\frac{m}{2}$ 次操作時需要把哪些數字放到前面，之後暴力交換剩下的操作次數。這樣時間複雜度降到 $\mathcal{O}(n \log n)$。

# Disbursement on Quarantine Policy

## 簡易題意
有 $n \times m$ 個人排成一個網格列隊，位於座標 $(i, j)$ 的人確診的可能性為 $v_{ij} \in \{0, 0.5, 1\}$，令隨機變數 $D_{ij}$ 為座標 $(i, j)$ 的人需要隔離的天數，求所有人需要的總隔離天數期望值 $\mathbb{E}[\sum_{i=1}^{n}\sum_{j=1}^mD_{ij}]$。

## 題解
透過期望值的線性性質，$\mathbb{E}[\sum_{i=1}^{n}\sum_{j=1}^mD_{ij}] = \sum_{i=1}^{n}\sum_{j=1}^m\mathbb{E}[D_{ij}]$，因此對於每一個人分別求出需要隔離天數的期望值再相加即為所求。

位於座標 $(i, j)$ 的人計算以下三種情況的機率:
1. 自己確診的機率為 $p_0$，即為 $v_{ij}$
2. 存在一個確診者與自己漢米頓距離為 $1$ 的機率為 $p_1$。
- 全部扣掉前後左右均沒人確診
- $1 - (1 - v_{i-1,j})(1 - v_{i+1,j})(1 - v_{i, j-1})(1 - v_{i,j+1})$
- $v_{ij} = 0$ where $i < 1 \lor i > n \lor j < 1 \lor j > m$
3. 存在一個確診者與自己漢米頓距離為 $2$ 的機率為 $p_2$。
- 全部扣掉斜對角均沒人確診
- $1 - (1 - v_{i-1,j-1})(1 - v_{i+1,j-1})(1 - v_{i-1, j+1})(1 - v_{i+1,j+1})$
- $v_{ij} = 0$ where $i < 1 \lor i > n \lor j < 1 \lor j > m$

位於座標 $(i, j)$ 的人需要隔離的天數為
1. 自己確診隔離 $d_0$ 天，機率為 $p_0$
2. 最靠近的確診者距離自己漢米頓距離為 $1$ 需要隔離 $d_1$ 天
- (自己沒有確診)且(存在一個確診者與自己漢米頓距離為 $1$)
- $(1 - p_0)p_1$
3. 最靠近的確診者距離自己和米頓距離為 $2$ 需要隔離 $d_2$ 天
- (自己沒有確診)且(不存在一個確診者與自己漢米頓距離為 $1$)且(存在一個確診者與自己漢米頓距離為 $2$)
- $(1 - p_0)(1 - p_1)p_2$

因此 $\mathbb{E}[D_{ij}] = p_0 \times d_0 + (1 - p_0)p_1 \times d_1 + (1 - p_0)(1 - p_1)p_2 \times d_2$，最後再透過期望值的線性性質計算 $\mathbb{E}[\sum_{i=1}^{n}\sum_{j=1}^mD_{ij}]$ 即為所求，時間複雜度為 $O(n \times m)$。

:::spoiler code

const val MOD = 1_000_000_007
fun fpow(a: Int, n: Int): Int {
  if (n == 0)
    return 1

  val k = fpow(a, n / 2)
  var ret = 1L * k * k % MOD
  if (n % 2 == 1)
    ret = 1L * ret * a % MOD

  return ret.toInt()
}

fun get_p(c: Char): Int {
  if (c == 'V')
    return 1
  else if (c == '.')
    return 0
  else
    return fpow(2, MOD - 2) // 2^{-1} = 2^{MOD-1} * 2^{-1} mod MOD
}

fun solve() {
  var (n, m, d0, d1, d2) = readInts()
  var B: Array<String> = Array(n) { String() }

  for (i in 0 until n)
    B[i] = readLn()

  val d4x: Array<Int> = arrayOf(0, 1, 0, -1)
  val d4y: Array<Int> = arrayOf(1, 0, -1, 0)

  val d8x: Array<Int> = arrayOf(1, 1, -1, -1)
  val d8y: Array<Int> = arrayOf(1, -1, 1, -1)

  var sum = 0L
  for (i in 0 until n) {
    for (j in 0 until m) {
      val p0 = get_p(B[i][j])

      var p1 = 1L
      for (d in 0 until 4) {
        val ni = i + d4x[d]
        val nj = j + d4y[d]
        if (ni < 0 || ni >= n || nj < 0 || nj >= m)
          continue

        p1 = p1 * (MOD + 1 - get_p(B[ni][nj])) % MOD
      }
      p1 = (MOD + 1 - p1) % MOD

      var p2 = 1L
      for (d in 0 until 4) {
        val ni = i + d8x[d]
        val nj = j + d8y[d]
        if (ni < 0 || ni >= n || nj < 0 || nj >= m)
          continue

        p2 = p2 * (MOD + 1 - get_p(B[ni][nj])) % MOD
      }
      p2 = (MOD + 1 - p2) % MOD

      sum = (sum + 1L * d0 * p0) % MOD
      sum = (sum + 1L * d1 * (MOD + 1 - p0) % MOD * p1 % MOD) % MOD
      sum = (sum + 1L * d2 * (MOD + 1 - p0) % MOD * (MOD + 1 - p1) % MOD * p2 % MOD) % MOD
    }
  }
  println (sum)

}

fun main() {
  solve()
}

/* IO template */
private fun readLn() = readLine()!!
private fun readInt() = readLn().toInt()
private fun readLong() = readLn().toLong()
private fun readDouble() = readLn().toDouble()
private fun readStrings() = readLn().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
private fun readLongs() = readStrings().map { it.toLong() }
private fun readDoubles() = readStrings().map { it.toDouble() }

:::

# Efficient Slabstones Rearrangement

## 題敘

要挪出空間放新石板，但要滿足空間限制，最少要移動多少？

## 解法

枚舉要把新的⽯板放在哪兩塊⽯板之間。把它左邊的⽯板往左移動，右邊的⽯板往右移動，將這個間隔變得夠⼤。接下來要決定往左/往右移動的距離，也可以當作決定新⽯板的實際放置位置。

往左移動的⽯板數量和往右移動的⽯板數量應該要盡量接近，因為如果往左移動的⽯板比往右移動的⽯板多，那麼新⽯板的放置位置往右⼀單位，總移動距離可以減少，反過來的話理由相同。

實際的作法是每次同時往左往右多動⼀塊⽯板，同時維護⽬前空出的空間與⽬前花費，如果空出的的空間⾜夠就結束。如果其中⼀邊已經沒有空間可⽤就把剩下的需求讓另外⼀邊處理。

我們不在意⽯板的實際位置和長度，所以可以⽤另⼀個陣列 $a_i$ 表⽰⽯板$i$ 和 $i + 1$ 之間還有多少空間可縮減，實作會簡單很多：

$a_0 = l_1 - 1$
$a_i = l_i +1 - r_i - d - 1, 1 \le i \le n - 1$
$a_n = m - r_n$
有 $n + 1$ 種情況要考慮，每種情況需要 O(n) 時間計算這種情況的最⼩花費。總時間複雜度為 $O(n^2)$ 。

# Fibonacci Lucky Numbers

## 題敘

計算費氏數列的第 $7^{7^{7^n}}$ 項的最後 10 位數。

## 解法

先觀察費氏數列的末 10 位數會循環，而且只要前兩項的末 10 位數就能決定這一項。考慮一張圖：$G=(V,E)$，其中 $V=\{0,1,\dots,9999999999\}\times\{0,1,\dots,9999999999\}$、$E=\{\left((x,y),(y,x+y)\right):(x,y)\in V\}$。這張圖所有的點 out degree 都是 1 ，因此從任何一點出發必然會有 cycle ，而從 $(1,1)$ 出發沿路上經過的第 $k$ 個點的第一項就是 $F_k$ 的後十位數字，這代表費氏數列只看後十位必定會循環。如果能夠求出循環長度 $C$ 跟需要進入循環的長度 $L$ 之後，則 $F_1,\dots,F_L$ 可由快速冪算出後十位，而 $k>L$ 的場合，則使用快速密算 $F_{L+((k-L)\mod C)}$ 後十位。

要找出 $L$ 跟 $C$，雖然圖很大存不下，但可以使用 Floyd Cycle Detection Algorithm 在 $O(1)$-space $O(L+C)$-time 找出，而在本題的設定下，$L=0,C=1.5\times 10^{10}$，使用 Floyd Cycle Detection Algorithm 直接找也是幾分鐘內可以找出答案。另外也可以透過位數更少的週期來大膽猜測 $C=1.5\times 10^{10}$ 。

但即便知道週期，要計算 $7^{7^{7^n}}\mod C$還是相當困難，因為 $7^{7^{7^n}}$ 太大了。此時就要利用歐拉定理，由於 $7$ 與 $\phi(C)$、$\phi(\phi(C))$互質，$7^{7^{7^n}}\equiv 7^{7^{7^n}\mod \phi(C)}\pmod C\equiv 7^{7^{7^n\mod \phi(\phi(C))}\mod \phi(C)}\pmod C$。

## 陷阱

別忘了要加上 leading zeros 。

# Game of Rounding
## 題敘
給一個array$(a_1...a_n)$，定義一個array的價值是平均的四捨五入，對每一個左界找出一個價值最高的subarray，若有多個找出最短的連續子序列
## 解法
1. 先將所有元素*2，這樣四捨五入的操作就變成向下取整
2. 我們把價值式子分析一下，一個array的總和可以變成兩個前綴相減，$$\frac{prefix_r-prefix_{l-1}}{r-l}$$
3. 假設我們將問題換成有沒有一個array價值$\ge x$，那式子就可以變成$$\frac{prefix_r-prefix_{l-1}}{r-l}\ge x$$
4. 整理一下可以變成 $prefix_r-r*x\ge prefix_{l-1}-l*x$
5. 式子左邊在已知$x$的情況下會是一個定值，右邊則是一個斜率為$l$的線，因此很容易可以發現可以直接用斜率優化找出最小值。
6. 若最小值 $\le$ $prefix_r-r*x$，則存在一個subarray的價值超過$x$，且有單調性，可以直接二分搜出最大找的到答案的$x$，假設該值為$ans$，到這邊時間複雜度總共為$O(n\log(n)\log(max(a_i)))$
7. 接下來要找出右界最靠左的subarray，價值為$ans$，我們可以建一棵線段樹，每個節點儲存他所涵蓋的範圍所有線的下凸包，就可以很簡單的找出答案，dfs線段樹，若線段樹當前左邊節點的最小值 $\le$ $prefix_r-r*x$，那答案左邊存在答案，所以往左走，反之往右
8. 為了防止找出的右界$\lt$左界，可以選擇動態加入，從右往左掃可選線段的斜率$-r$是遞增，也可以直接丟[李超樹](https://oi-wiki.org/ds/li-chao-tree/)
9. 複雜度為 $O(n\log(n)\log(\max(a_i)))$

# Harmonious Passage of Magicians
## 題敘
左邊有n個人右邊有m個人，中間只有一個空格，左邊人面對右邊只能往右，右邊人面對左邊只能往左，每個人符合下列兩種情況之一，就可以移動到空格，
1. 他的面前是空格
2. 他的面前的人跟他面向不一樣，且在下一格是空格
輸出一個移動策略使得左邊所有人移動到最右邊，右邊所有人移動到最左邊，舉例來說
開始樣子為12.45，12面向右邊，34面向左邊，需要找一個移動策略使得他最後變成，45.12，若有多個策略輸出字典序最小
## 解法
1. 可以發現每次能移動到空格的只有其中一個面向右邊的人跟其中一個面向左邊的人兩種操作而已。
2. 若移動左邊的人不會進入無解狀態，就移動左邊的人，反之移動右邊
3. 其實在$n\ge2\space \& \space m\ge 2$，只會有兩種解
4. 操作一下可以發現，作法就是左邊移動1次，右邊移動2次，左邊移動3次...直到某一邊的移動次$\gt$人數，就重複最後兩個操作直到左右兩邊都是對面的人，再倒著做所有操作即可。

# In Search of the Lost Array

本題有一個很直覺的 backtracking 的演算法：這是一個遞迴的演算法，首先先決定好 $a$ 的第一項 $a_1$，之後選定 $b$ 中的其中一個數字 $b_i$，假設他是 $a$ 前面兩項的乘積 $a_1 \times a_2$，據此就能算出第二項 $a_2$。之後用算出來的 $a_2$ 再選一個 $b_i$ 算出 $a_3$，依此類推。這個演算法需要枚舉所有的第一項 $a_1$ 以及所有不重複的 $b_i$ 的先後順序。這個做法很直觀，但是效率可能會不夠高（事實上這個做法對於隨機測資效果很好，做一些剪枝優化以後是有機會通過，但是有點碰運氣。讀者也可以思考一下，如果你是這題出題者，可以怎麼設計夠強的測資）

優化的方法是使用動態規劃。令 $\text{dp}[S][i]$ 是一個 Boolean value，代表是否有可能構造長度是 $|S|+1$ 的序列，其中已經被用過的 $b_i$ 的集合是 $S$，且序列的最後一項是 $i$。遞迴式如下：

$\text{dp}[S][i] = \begin{cases} \text{True} & \quad \text{ if } S = \varnothing \\ \bigvee\limits_{p \in S} \text{dp}[S - \{p\}][\frac{p}{i}] & \quad \text{ otherwise }\end{cases}$

算完 DP 的值以後，可以看 $\text{dp}\left[\{b_1,b_2,\cdots,b_n\}\right][\cdot]$ 的值是不是 `True`，來判斷是不是有解。要求得一個解的話，可以從 $\text{dp}\left[\{b_1,b_2,\cdots,b_n\}\right][\cdot]$ 是 `True` 的項開始（得到 $a$ 最後一項），往回找一個 $p$ 使得 $\text{dp}[S - \{p\}][\frac{p}{i}]$ 也是 `True`，這樣就找到了 $a$ 倒數第二項。依此類推，就可以逆序找到 $a$ 的所有項。這樣的時間複雜度是 $\mathcal{O}(nC2^n)$，其中 $C = 100$ 代表 $a_i$ 的可能取值數。

# Just Round Down

## 題敘

請把一個長度格式都有限制的正浮點數 $x$ 向下取整。

## 解法

當作 double precision floating point number 讀，然後轉型成 integer 後輸出。

# Kingdom's Development Plan

## 題敘

給一有向圖，要求輸出字典順序最小的拓樸排序。如沒有，就輸出 `IMPOSSIBLE`。

## 解法

準備一個 Priority Queue 存放 in degree 為 0 的點，確保每次有可選能拿出字典序最小的。輸出點後，拔除由該點出發的邊，並將 in degree 變 0 的點放入 Priority Queue。其餘部分與經典的拓樸排序演算法相同。

# Lexicopolis

本題最直覺的作法應該是用遞迴的方式找出所有從 $s$ 到 $t$ 長度為 $k$ 的 path，挑出字典序最小的，但是這樣效率明顯不夠高。一個比較好的做法是使用動態規劃，令 $\text{path}[d][v]$ 代表從 $s$ 出發，長度為 $d$ 且終點在 $v$ 的 path 中，字典序最小的序列。則 $\text{path}[d][v]$ 可以從 $\text{path}[d- 1][\cdot]$ 遞迴獲得，最後答案就是 $\text{path}[k][t]$。這是正確的作法，但是因為這題 $k$ 很大，同樣也不足以通過此題。

從以上動態規劃的方法延伸，考慮倍增法。首先先做一個預處理：令 $\text{path}[d][u][v]$ 代表從 $u$ 到 $v$ 長度為 $d$ 的 path 中，字典序最小的序列。注意到這裡 **$d$ 限制只能是 $2$ 的冪次**，也就是 $2^0,2^1,2^2,\cdots$。

使用動態規劃算出 $\text{path}$ 的值。計算過程如下：$d = 2^0$ 時，$\text{path}[2^0][\cdot][\cdot]$ 就是邊權的 adjacency matrix。當計算對於 $i>0$ 的 $\text{path}[2^i][\cdot][\cdot]$ 時，可以使用以下遞迴式：

$\displaystyle \text{path}[2^i][u][v] = \min_{w = 1}^{n} (\text{path}[2^{i - 1}][u][w] + \text{path}[2^{i - 1}][w][v])$

這裡的 $+$ 是串接（concatenation）。直觀理解就是，枚舉從 $u$ 出發走 $2^{i - 1}$ 步以後走到哪個節點，分別以前後兩半字典序最小的 path 得到答案。

做完以上預處理以後，要求得答案和上面遞迴式的邏輯很像。注意到把以上遞迴式改寫成以下 general form 也是對的：

$\displaystyle \text{path}[a+b][u][v] = \min_{w = 1}^{n} (\text{path}[a][u][w] + \text{path}[b][w][v])$

於是我們可以考慮 $k$ 的二進制分解。維護一個 $n \times n$ 的表格，每一個 cell 代表從 $u$ 到 $v$ 的最小字典序序列。從距離 $d = 0$ 開始，運用上面的式子，每次加一個二的冪次的表格到他身上（二的冪次的表格都已經在預處理算好了），直到 $d = k$。當 $d = k$ 時，從 $s$ 到 $t$ 字典序最小的序列就是 $\text{path}[s][t]$。

以上是解法的主要邏輯，但是有兩個問題：第一個問題是在預處理和算答案時，我們需要比較兩個序列的字典序，但這個序列可能長達 $10^9$ 的量級。其次，答案要求要算出 $\sum\limits_{i = 1}^{k} w_{e_i} x^{k - i}$（以下稱這個值為 hash），而最直覺的作法也需要至少 $\mathcal{O}(k)$ 的時間才能算出 hash 值。

第一個問題可以透過記錄所有點對之間 path 的相對順序來解決。注意到會影響上式中 $w$ 的取值的，其實只有固定長度下所有點對字典序的相對順序，實際內容是什麼並不重要。所以我們在使用以上式子算出每個點對的最小字典序 path 之後，順便紀錄所有點對之間的字典序 rank，之後在計算 $d$ 更大的值的時候，也只考慮這個 rank。

但是這樣做也導致 path 的實際內容消失了，從而無法算出 hash 值。實際上這個問題也很好解決：hash 值也可以用上式類似的方法順便算出來。具體來說，假如透過上式，我們知道要從 $u$ 到 $v$ 走 $a+b$ 步，需要走 $a$ 步到 $w$ 再走 $b$ 步到 $v$，那因為 $\sum\limits_{i = 1}^{a+b} w_{e_i} x^{k - i} = \left(\sum\limits_{i = 1}^{a} w_{e_i} x^{a - i}\right)x^{b} + \left(\sum\limits_{i = 1}^{b} w_{e_{i + a}} x^{b - i}\right)$，假如知道了前 $a$ 步的 hash 值和後 $b$ 步的 hash 值，那就可以算出走 $a+b$ 步的 hash 值。

總結來說，我們改寫以上的遞迴式，不紀錄實際 path 的內容，改紀錄每個點對之間的相對排名 $\text{rank}$，以及這條 path 的 hash 值 $\text{hash}$。新遞迴式如下：

$\displaystyle \text{rank}[a+b][u][v] = \text{rank of } \left(\min_{w = 1}^{n} (\text{rank}[a][u][w], \text{rank}[b][w][v])\right) \text{ among all pairs of nodes}$
$\displaystyle w' = \arg\min_{w = 1}^{n} (\text{rank}[a][u][w], \text{rank}[b][w][v])$
$\displaystyle \text{hash}[a+b][u][v] = \text{hash}[a][u][w'] \cdot x^b + \text{hash}[b][w'][v]$

其中第一個 $\text{rank}$ 的比較基準是 pair 比較，不論是預處理還是算答案都可以使用以上的遞迴式。這個演算法的時間複雜度是 $\mathcal{O}(n^3 \log k)$，即可順利通過此題。