假定 $d_1$ 與 $d_2$ 內的加減乘除皆能在 $O(1)$ 時間內完成，只要將 $\log_{d_2}{d_1}$ 視為常數（以本題而言為 $\log_236 \approx 5.17$），長度為 $n$ 的大整數 $N$（符號與題目不一致抱歉）的進位制轉換，可以做到 $O(n(\log n)^2)$ 的時間複雜度。

設 $N$ 的 $d_1$ 進位表示為 ${a_{n-1}a_{n-2}\ldots a_0}_{(d_1)} = a_0 + a_1d_1 + \ldots + a_{n-1}d_1^{n-1}$，其中 $0\le a_i\le d_1-1$，目標找出 $b_0, b_1, b_2, \ldots$ 滿足 $0\le b_i\le d_2-1$ 且 $N = b_0 + b_1d_2 + b_2d_2^2 + \ldots$。

不失一般性假定 $n = 2^k$（如果 $n$ 不足則補上 leading zeros）。當 $k = 0$ 時，我們有 $N = a_0$，直接將 $a_0$ 轉成 $d_2$ 進位，需時 $O(\log_{d_2}{d_1}) = O(1)$。當 $k \ge 1$ 時，觀察

\[N = \left(a_0 + a_1d_1 + \ldots + a_{2^{k-1}-1}d_1^{2^{k-1}-1}\right) + \left(a_{2^{k-1}} + a_{2^{k-1}+1}d_1 + \ldots + a_{2^k-1}d_1^{2^{k-1}-1}\right)d_1^{2^{k-1}}.\]

因此只要分別求出 $N$ 的低位部分 $L(N) := {a_{\frac n2-1}a_{\frac n2-2}\ldots a_0}_{(d_1)}$ 、$N$ 的高位部分 $H(N) := {a_{n-1}a_{n-2}\ldots a_{\frac n2}}_{(d_1)}$、以及上式中的 $d_1^{\frac n2}$ 的 $d_2$ 進位表示，就能用大數乘法時間複雜度 $O(L\log L)$ 的演算法算出 $N$ 的 $d_2$ 進位表示了，時間複雜度為 $T(n) = 2T(\frac n2)+O(n\log n) = O(n(\log n)^2)$。

以下雜談：

1. 實際上我的標程都將 $s$ 視為 $N$ 的 $d_1^{w_1}$ 進位表示（一格佔 $s$ 的 $w_1$ 個字元），轉成 $d_2^{w_2}$ 進位後再輸出 $t$。只要確保 $d_1^{w_1} < d_2^{w_2}$，上述介紹的遞迴演算法的 base case 就毋須額外處理。
2. 我後來發現 java 的 BigInteger 以及 python 的內建 int 都提供了 bitwise-and/or/xor 運算。這代表要嘛它們做這些運算的時間複雜度是 $\Omega(n(\log n)^2)$，要嘛它們光 IO 就要 $\Omega(n(\log n)^2)$ 了耶 orz。