913. Row-major vs Column-major

The numbers from $1$$1$ to $12$$12$ can be arranged into a $3\times 4$$3 \times 4$ matrix in either row-major or column-major order:

By swapping two entries at a time, at least $8$$8$ swaps are needed to transform $R$$R$ to $C$$C$.

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

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

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

913. 优先填行或填列

$1$$1$ 至 $12$$12$ 间的整数可以通过 优先填行 的顺序排成 $3\times 4$$3 \times 4$ 的矩阵 $R$$R$，或通过 优先填列 的顺序排成 $3\times 4$$3 \times 4$ 的矩阵 $C$$C$：

若允许同时交换某矩阵中的两个元素，那么至少需要 $8$$8$ 次交换才能将 $R$$R$ 转换为 $C$$C$。

记 $S(n,m)$$S(n, m)$ 为：将 $1$$1$ 至 $nm$$nm$ 间的整数通过优先填行、优先填列的顺序排成的 $n\times m$$n \times m$ 的矩阵分别记为 $R^{\prime }$$R'$、$C^{\prime }$$C'$，把 $R^{\prime }$$R'$ 转换为 $C^{\prime }$$C'$ 最少需要交换元素的次数。因而 $S(3,4)=8$$S(3, 4) = 8$。

你已知：对所有 $2\le n\le m\le 100$$2 \leq n \leq m \leq 100$，$S(n,m)$$S(n, m)$ 的和是 $12578833$$12578833$。

求：对所有 $2\le n\le m\le 100$$2 \leq n \leq m \leq 100$，$S(n^4,m^4)$$S(n^4, m^4)$ 的和。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。