0%

Problem 913


Problem 913


Row-major vs Column-major

The numbers from $1$ to $12$ can be arranged into a $3 \times 4$ matrix in either row-major or column-major order:
$$R=\begin{pmatrix}
1 & 2 & 3 & 4\\
5 & 6 & 7 & 8\\
9 & 10 & 11 & 12\end{pmatrix},
C=\begin{pmatrix}
1 & 4 & 7 & 10\\
2 & 5 & 8 & 11\\
3 & 6 & 9 & 12\end{pmatrix}$$
By swapping two entries at a time, at least $8$ swaps are needed to transform $R$ to $C$.

Let $S(n, m)$ be the minimal number of swaps needed to transform an $n\times m$ matrix of $1$ to $nm$ from row-major order to column-major order. Thus $S(3, 4) = 8$.

You are given that the sum of $S(n, m)$ for $2 \leq n \leq m \leq 100$ is $12578833$.

Find the sum of $S(n^4, m^4)$ for $2 \leq n \leq m \leq 100$.


行优先与列优先

$1$到$12$这些数可以按行优先列优先的顺序填入一个$3 \times 4$矩阵中:
$$R=\begin{pmatrix}
1 & 2 & 3 & 4\\
5 & 6 & 7 & 8\\
9 & 10 & 11 & 12\end{pmatrix},
C=\begin{pmatrix}
1 & 4 & 7 & 10\\
2 & 5 & 8 & 11\\
3 & 6 & 9 & 12\end{pmatrix}$$
每次交换两个元素,至少需要$8$次交换才能将$R$转换为$C$。

令$S(n, m)$为将一个包含$1$到$nm$的$n\times m$矩阵从行优先顺序转换为列优先顺序所需的最少交换次数,因此$S(3, 4) = 8$。

已知对于所有$2 \leq n \leq m \leq 100$,$S(n, m)$之和为$12578833$。

求对于所有$2 \leq n \leq m \leq 100$,$S(n^4, m^4)$之和。