# The 2025 ICPC Taiwan Technology University Programming Contest (TUPC)

程式碼在 [Github](https://github.com/co0okie/icpc-tupc2025) 上，歡迎自由取用

## Problem B <br>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

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

$$\DeclareMathOperator{\dp}{dp}\newcommand{\matr}[1]{\mathbf{#1}}
(a + b)\bmod d = [(a\bmod d)+(b\bmod d)]\bmod d$$

$$ab \bmod d=(a\bmod d)(b\bmod d)\bmod d$$

推廣到矩陣:

$$
\matr{A}\matr{B}\bmod d=\left(\matr{A}\bmod d\right)\left(\matr{B}\bmod d\right)\bmod d \\
$$
:::spoiler Detailed Derivation
$$\begin{align}
\matr{A}&=[a_{ij}],\,\textrm{for}\ i=1\ldots m,\,j=1\ldots n \\
\matr{B}&=[b_{ij}],\,\textrm{for}\ i=1\ldots n,\,j=1\ldots p \\
\matr{C}&=[c_{ij}]=\matr{A}\matr{B} \\
\matr{C}\bmod d&=\left[c_{ij}\bmod d\right],\,\textrm{for}\ i=1\ldots m,\,j=1\ldots p \\
&=\left[\left(\sum_{k=1}^na_{ik}b_{kj}\right)\bmod d\right] \\
&=\left[\left(\sum_{k=1}^n\left(a_{ik}b_{kj}\bmod d\right)\right)\bmod d\right] \\
&=\left[\left(\sum_{k=1}^n\left[\left(a_{ik}\bmod d\right)\left(b_{kj}\bmod d\right)\bmod d\right]\right)\bmod d\right] \\
&=\left(\matr{A}\bmod d\right)\left(\matr{B}\bmod d\right)\bmod d \\
\end{align}$$
:::

$$\matr{A}^b\bmod d=\left(\matr{A}\bmod d\right)^b\bmod d$$

:::spoiler Detailed Derivation
$$\begin{align}
\matr{A}^b\bmod d&=\overbrace{\matr{A}\matr{A}\ldots\matr{A}}^{b}\bmod d \\
&=\overbrace{(\matr{A}\bmod d)(\matr{A}\bmod d)\ldots(\matr{A}\bmod d)}^{b}\bmod d \\
&=\left(\matr{A}\bmod d\right)^b\bmod d \\
\end{align}$$
:::

後續說明為求方便，省略了一些$\bmod d$，但利用模除運算的分配律性質，只要在每次運算後加上取模即可算出答案。

#### Impossible Condition

首先排除不可能到達的情況，下圖為所有可能到達的地點，觀察可發現，當 $u<|v|$ 或 $(u-v)\bmod 2 \neq 0$ 則不可能到達，此時直接輸出 $0$。

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

#### Highest Path

題目要求找到所有路徑中，包含最大 $y$ 座標的路徑數量。觀察過後可以發現，不論 $r$ 為何、亦不論每步走幾格，此路徑必定為先向右上，再向右下，以下方為例，若目標為$(9, 3)$，◉ 為起點與終點， ● 代表選擇路徑，○ 代表其他可能路徑:

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

則包含最高 $y$ 座標的路徑僅有一條，因此可將問題拆分為起點 -> 最高點，與最高點 -> 終點兩段。第一段路徑可寫成 $(i,i)$，第二段則可寫成 $(u-j,v+j)$，計算得到交點 $\left({u+v\over 2},{u+v\over 2}\right)$。

#### Number of Highest Path

令 $\dp[i]$ 為可能的路徑數量，其中 $i$ 為與終點的距離，則:
- 第一段路為 $(0,0)$ 到 $\left({u+v\over 2},{u+v\over 2}\right)$，可能的路徑數為 $\dp\left[{u+v\over 2}\right]$
- 第二段路為 $\left({u+v\over 2},{u+v\over 2}\right)$ 到 $(u,v)$，可能的路徑數為 $\dp\left[{u-v\over 2}\right]$

則最終答案，總路徑數為:
$$\dp\left[{u+v\over 2}\right]\dp\left[{u-v\over 2}\right]$$

#### Step Size

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

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

由此可知，前進一步的最長距離為 $2r-1$，因此定義步長:

$$s=2r-1$$

代表可以選擇前進 $1,2,3,\ldots,2r,2r-1$ 步

#### Dynamic Programming Function

假設步長 $s = 3$，則可以推導出以下規律:

$$\begin{split}
\textrm{e.g.}\qquad s=3 \\
\dp[0]&&&=1 \\
\dp[1]&=dp[0]&&=1 \\
\dp[2]&=\dp[1]+\dp[0]&&=2 \\
\dp[3]&=\dp[2]+\dp[1]+\dp[0]&&=4 \\
\dp[4]&=\dp[3]+\dp[2]+\dp[1]&&=7 \\
\dp[5]&=\dp[4]+\dp[3]+\dp[2]&&=13 \\
&\vdots \\
\end{split}$$

舉例來說， $\dp[2]$ 可以理解為「走到 $2$ 的路徑數 $=$ 走到 $1$ 的路徑數 $+$ 走到 $0$ 的路徑數」。
以 piecewise function 表示:

$$
\dp[i]=\begin{cases}
0 & i\lt 0 \\
1 & i=0 \\
\sum_{j=1}^{s}\dp[i-j] & i \gt 0 \\
\end{cases}$$

#### Matrix Representation of Dynamic Programming Function

對於 $i \gt 0$，可以以一個 $s\times s$ 矩陣與 $s\times 1$ 陣列相乘表示其關係:

$$
\begin{bmatrix}
\dp[i-s+1] \\
\dp[i-s+2] \\
\dp[i-s+3] \\
\dp[i-s+4] \\
\vdots \\
\dp[i-2] \\
\dp[i-1] \\
\dp[i] \\
\end{bmatrix}=\begin{bmatrix}
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 \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
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{bmatrix}\begin{bmatrix}
\dp[i-s] \\
\dp[i-s+1] \\
\dp[i-s+2] \\
\dp[i-s+3] \\
\vdots \\
\dp[i-3] \\
\dp[i-2] \\
\dp[i-1] \\
\end{bmatrix}
$$

將上述等式表示為:

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

利用其遞迴關係，可以一路追溯到初始狀態 $\matr{x}_{0}$:

$$\matr{x}_i=\matr{A}\matr{A}\matr{x}_{i-2}=\matr{A}^{2}\matr{x}_{i-2}=\matr{A}^3\matr{x}_{i-3}=\cdots=\matr{A}^{i}\matr{x}_{0}$$

其中:

$$\matr{x}_{0}=\begin{bmatrix}
\dp[-s+1] \\
\dp[-s+2] \\
\dp[-s+3] \\
\dp[-s+4] \\
\vdots \\
\dp[-2] \\
\dp[-1] \\
\dp[0] \\
\end{bmatrix}=\begin{bmatrix}
0 \\
0 \\
0 \\
0 \\
\vdots \\
0 \\
0 \\
1 \\
\end{bmatrix}$$

因此，對於 $i\gt 0$，只要取得 $\matr{x}_i$ 的最後一項即可得到答案。

#### Fast Matrix Exponentiation

題目定義 $u$ 與 $|v|$ 最大可達 $2^{2025}$，而 $i$ 的大小與其相關，因此需要使用快速冪技巧計算 $\matr{A}^{i}$。另外，因為輸入太大，無法以數字類型(64-bit int)儲存，因此需以十進制陣列儲存，計算快速冪時也以十進制為主。

快速冪的核心概念如下，假設要計算 $\matr{A}^{12345}$ :

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

以代數表示:

$$
\matr{A}^b=\matr{A}^{10b^′+r}=\left(\matr{A}^{b^′}\right)^{10}\matr{A}^r \\
,\quad b\div10=b'\ldots r
$$

因此，只要以左到右遍歷 $b$ 的每一位數，重複10次方、乘 $\matr{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 次方，可以將其拆分成以下運算:

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

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

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

最終演算法複複雜度為 $O\left(r^3\log(u)\right)$，$r^3$ 來自矩陣乘法，$\log(u)$ 則是因為要分別遍歷 $u$ 的所有位數。