matrix-multiplication - 具有整数值的矩阵数

Question

我必须在左上角的条目中找到包含 1 的 NXM 矩阵的数量，所有条目都是整数值，相邻的条目最多相差 1，知道 N 最多为 5，M 可以达到 10^9。显然回溯算法不够快，我认为可以使用矩阵求幂来解决这个问题，但我对这一点没有任何想法。提前致谢！

Answer 1

每一行都采用以下形式：

x (y=x+1/x/x-1) (z=y+1/y/y-1) ...

x 的值并不重要，因此（对于 N = 5）每行有 3^4 = 81 种可能性。

从这里开始，您编写一个简单的程序来确定当前行中这 81 种可能性中的每一种在下一行中出现的频率。

从那里你应该能够找出一个公式，如果有一个简单的公式，否则你有一个 O(10^9) 算法，这至少比你开始的更好。

“最多”和“可以达到”确实与算法有点混乱。