The 2025 ICPC Taiwan Technology University Programming Contest (TUPC)

程式碼在 Github 上，歡迎自由取用

Problem B
Diamond Attacker

Input Format

r1 u1 v1 d1
r2 u2 v2 d2
r3 u3 v3 d3
...

• r: the order of the diamond attacker
• u: target x-coordinate
• v: target y-coordinate
• d: modulo divisor

Techinical Specification

• $0\le u\le 2^{2025}$
• $0\le |v|\le 2^{2025}$
• $0\le r\le 7$
• $1\le d\le {10}^9$

Sample Input

1 0 0 9999
1 1 3 9999
2 3 1 9999

Sample Output

1
0
2

Solution

Modulo Operation

這題需要對模除運算有一定的了解，包含以下恆等式:

$$(a+b)modd=[(amodd)+(bmodd)]modd$$

$$abmodd=(amodd)(bmodd)modd$$

推廣到矩陣:

$$\mathbf{A}\mathbf{B}modd=(\mathbf{A}modd)(\mathbf{B}modd)modd$$

Detailed Derivation

$$\begin{array}{rl}\mathbf{A}& =[a_{ij}],\text{for}i=1\dots m,j=1\dots n\\ \mathbf{B}& =[b_{ij}],\text{for}i=1\dots n,j=1\dots p\\ \mathbf{C}& =[c_{ij}]=\mathbf{A}\mathbf{B}\\ \mathbf{C}modd& =[c_{ij}modd],\text{for}i=1\dots m,j=1\dots p\\ & =[\left(\sum _{k=1}^n{a}_{ik}{b}_{kj}\right)modd]\\ & =[\left(\sum _{k=1}^n(a_{ik}{b}_{kj}modd)\right)modd]\\ & =[\left(\sum _{k=1}^n[(a_{ik}modd)(b_{kj}modd)modd]\right)modd]\\ & =(\mathbf{A}modd)(\mathbf{B}modd)modd\end{array}$$

$${\mathbf{A}}^{b}modd={(\mathbf{A}modd)}^{b}modd$$

Detailed Derivation

$$\begin{array}{rl}{\mathbf{A}}^{b}modd& =\stackrel{b}{\overbrace{\mathbf{A}\mathbf{A}\dots \mathbf{A}}}modd\\ & =\stackrel{b}{\overbrace{(\mathbf{A}modd)(\mathbf{A}modd)\dots (\mathbf{A}modd)}}modd\\ & ={(\mathbf{A}modd)}^{b}modd\end{array}$$

後續說明為求方便，省略了一些

$modd$，但利用模除運算的分配律性質，只要在每次運算後加上取模即可算出答案。

Impossible Condition

首先排除不可能到達的情況，下圖為所有可能到達的地點，觀察可發現，當

$u<|v|$ 或

$(u-v)mod2\ne 0$ 則不可能到達，此時直接輸出

$0$。

$$\begin{array}{|ccccccccccc|}\hline & & & & & & & ○& & ○& \\ & & & & & & ○& & ○& & ○\\ & & & & & ○& & ○& & ○& \\ & & & & ○& & ○& & ○& & ○\\ & & & ○& & ○& & ○& & ○& \\ & & ○& & ○& & ○& & ○& & ○\\ & ○& & ○& & ○& & ○& & ○& \\ ○& & ○& & ○& & ○& & ○& & ○\\ & ○& & ○& & ○& & ○& & ○& \\ & & ○& & ○& & ○& & ○& & ○\\ & & & ○& & ○& & ○& & ○& \\ & & & & ○& & ○& & ○& & ○\\ & & & & & ○& & ○& & ○& \\ & & & & & & ○& & ○& & ○\\ & & & & & & & ○& & ○& \\ \hline\end{array}$$

Highest Path

題目要求找到所有路徑中，包含最大

$y$ 座標的路徑數量。觀察過後可以發現，不論

$r$ 為何、亦不論每步走幾格，此路徑必定為先向右上，再向右下，以下方為例，若目標為

$(9,3)$，◉ 為起點與終點， ● 代表選擇路徑，○ 代表其他可能路徑:

$$\begin{array}{|ccccccccccc|}\hline & & & & & & & ○& & ○& \\ & & & & & & ●& & ○& & ○\\ & & & & & ●& & ●& & ○& \\ & & & & ●& & ○& & ●& & ○\\ & & & ●& & ○& & ○& & ◉& \\ & & ●& & ○& & ○& & ○& & ○\\ & ●& & ○& & ○& & ○& & ○& \\ ◉& & ○& & ○& & ○& & ○& & ○\\ & ○& & ○& & ○& & ○& & ○& \\ & & ○& & ○& & ○& & ○& & ○\\ & & & ○& & ○& & ○& & ○& \\ & & & & ○& & ○& & ○& & ○\\ & & & & & ○& & ○& & ○& \\ \hline\end{array}$$

則包含最高

$y$ 座標的路徑僅有一條，因此可將問題拆分為起點 -> 最高點，與最高點 -> 終點兩段。第一段路徑可寫成

$(i,i)$，第二段則可寫成

$(u-j,v+j)$，計算得到交點

$(\frac{u+v}{2},\frac{u+v}{2})$。

Number of Highest Path

令

$\mathrm{dp}[i]$ 為可能的路徑數量，其中

$i$ 為與終點的距離，則:

• 第一段路為
  $(0,0)$ 到
  $(\frac{u+v}{2},\frac{u+v}{2})$，可能的路徑數為
  $\mathrm{dp}\left[\frac{u+v}{2}\right]$
• 第二段路為
  $(\frac{u+v}{2},\frac{u+v}{2})$ 到
  $(u,v)$，可能的路徑數為
  $\mathrm{dp}\left[\frac{u-v}{2}\right]$

則最終答案，總路徑數為:

$$\mathrm{dp}\left[\frac{u+v}{2}\right]\mathrm{dp}\left[\frac{u-v}{2}\right]$$

Step Size

題目對於一步可以走到的位置定義如下:

$$(x+(i+j),y+(j-i)),0<=i,j<2\ast r$$

由此可知，前進一步的最長距離為

$2r-1$，因此定義步長:

$$s=2r-1$$

代表可以選擇前進

$1,2,3,\dots ,2r,2r-1$ 步

Dynamic Programming Function

假設步長

$s=3$，則可以推導出以下規律:

$$\begin{array}{r}\text{e.g.}s=3\\ \mathrm{dp}[0]& & & =1\\ \mathrm{dp}[1]& =dp[0]& & =1\\ \mathrm{dp}[2]& =\mathrm{dp}[1]+\mathrm{dp}[0]& & =2\\ \mathrm{dp}[3]& =\mathrm{dp}[2]+\mathrm{dp}[1]+\mathrm{dp}[0]& & =4\\ \mathrm{dp}[4]& =\mathrm{dp}[3]+\mathrm{dp}[2]+\mathrm{dp}[1]& & =7\\ \mathrm{dp}[5]& =\mathrm{dp}[4]+\mathrm{dp}[3]+\mathrm{dp}[2]& & =13\\ & ⋮\end{array}$$

舉例來說，

$\mathrm{dp}[2]$ 可以理解為「走到

$2$ 的路徑數

$=$ 走到

$1$ 的路徑數

$+$ 走到

$0$ 的路徑數」。
以 piecewise function 表示:

$$\mathrm{dp}[i]=\{\begin{array}{ll}0& i<0\\ 1& i=0\\ \sum _{j=1}^s\mathrm{dp}[i-j]& i>0\end{array}$$

Matrix Representation of Dynamic Programming Function

對於

$i>0$，可以以一個

$s\times s$ 矩陣與

$s\times 1$ 陣列相乘表示其關係:

$$\left[\begin{array}{c}\mathrm{dp}[i-s+1]\\ \mathrm{dp}[i-s+2]\\ \mathrm{dp}[i-s+3]\\ \mathrm{dp}[i-s+4]\\ ⋮\\ \mathrm{dp}[i-2]\\ \mathrm{dp}[i-1]\\ \mathrm{dp}[i]\end{array}\right]=\left[\begin{array}{cccccccc}0& 1& 0& 0& \cdots & 0& 0& 0\\ 0& 0& 1& 0& \cdots & 0& 0& 0\\ 0& 0& 0& 1& \cdots & 0& 0& 0\\ 0& 0& 0& 0& \cdots & 0& 0& 0\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮& ⋮\\ 0& 0& 0& 0& \cdots & 0& 1& 0\\ 0& 0& 0& 0& \cdots & 0& 0& 1\\ 1& 1& 1& 1& \cdots & 1& 1& 1\end{array}\right]\left[\begin{array}{c}\mathrm{dp}[i-s]\\ \mathrm{dp}[i-s+1]\\ \mathrm{dp}[i-s+2]\\ \mathrm{dp}[i-s+3]\\ ⋮\\ \mathrm{dp}[i-3]\\ \mathrm{dp}[i-2]\\ \mathrm{dp}[i-1]\end{array}\right]$$

將上述等式表示為:

$${\mathbf{x}}_i=\mathbf{A}{\mathbf{x}}_{i-1}$$

利用其遞迴關係，可以一路追溯到初始狀態

${\mathbf{x}}_0$:

$${\mathbf{x}}_i=\mathbf{A}\mathbf{A}{\mathbf{x}}_{i-2}={\mathbf{A}}^2{\mathbf{x}}_{i-2}={\mathbf{A}}^3{\mathbf{x}}_{i-3}=\cdots ={\mathbf{A}}^i{\mathbf{x}}_0$$

其中:

$${\mathbf{x}}_0=\left[\begin{array}{c}\mathrm{dp}[-s+1]\\ \mathrm{dp}[-s+2]\\ \mathrm{dp}[-s+3]\\ \mathrm{dp}[-s+4]\\ ⋮\\ \mathrm{dp}[-2]\\ \mathrm{dp}[-1]\\ \mathrm{dp}[0]\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\\ 0\\ ⋮\\ 0\\ 0\\ 1\end{array}\right]$$

因此，對於

$i>0$，只要取得

${\mathbf{x}}_i$ 的最後一項即可得到答案。

Fast Matrix Exponentiation

題目定義

$u$ 與

$|v|$ 最大可達

$2^{2025}$，而

$i$ 的大小與其相關，因此需要使用快速冪技巧計算

${\mathbf{A}}^i$。另外，因為輸入太大，無法以數字類型(64-bit int)儲存，因此需以十進制陣列儲存，計算快速冪時也以十進制為主。

快速冪的核心概念如下，假設要計算

${\mathbf{A}}^{12345}$ :

$$\begin{array}{rl}{\mathbf{A}}^{12345}& ={\left({\mathbf{A}}^{1234}\right)}^{10}{\mathbf{A}}^5\\ & ={\left({\left({\mathbf{A}}^{123}\right)}^{10}{\mathbf{A}}^4\right)}^{10}{\mathbf{A}}^5\\ & ={\left({\left({\left({\mathbf{A}}^{12}\right)}^{10}{\mathbf{A}}^3\right)}^{10}{\mathbf{A}}^4\right)}^{10}{\mathbf{A}}^5\\ & ={\left({\left({\left({\left({\mathbf{A}}^1\right)}^{10}{\mathbf{A}}^2\right)}^{10}{\mathbf{A}}^3\right)}^{10}{\mathbf{A}}^4\right)}^{10}{\mathbf{A}}^5\end{array}$$

以代數表示:

$$\begin{gathered} {\mathbf{A}}^b={\mathbf{A}}^{10b^{\prime }+r}={\left({\mathbf{A}}^{b^{\prime }}\right)}^{10}{\mathbf{A}}^r \\ ,b÷10=b^{\prime }\dots r \end{gathered}$$

因此，只要以左到右遍歷

$b$ 的每一位數，重複10次方、乘

${\mathbf{A}}^r$ 兩個動作就能完成矩陣快速冪，pseudocode 如下:

function matPow(A, b): // result = A^b
    result = idenetity matrix with the same size as A
    for digit in b: // decimal digits, from left to right
        result = (result ** 10) * (A ** digit)
    return result

Acceleration

上述的2個步驟皆有可加速的地方。若要計算矩陣的 10 次方，可以將其拆分成以下運算:

$${\mathbf{A}}^{10}={\mathbf{A}}^2{\left({\left({\mathbf{A}}^2\right)}^2\right)}^2$$

如此只需要 4 次矩陣乘法即可完成計算。

計算

${\mathbf{A}}^r$ 時，考慮到

$r\in \{0,1,\dots ,9\}$，可以預先建立 Lookup Table Matrix lut[10]，需要時直接取用 lut[r]，大幅減少計算時間。

最終演算法複複雜度為

$O(r^3\log (u))$，

$r^3$ 來自矩陣乘法，

$\log (u)$ 則是因為要分別遍歷

$u$ 的所有位數。