Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
我必须在左上角的条目中找到包含 1 的 NXM 矩阵的数量,所有条目都是整数值,相邻的条目最多相差 1,知道 N 最多为 5,M 可以达到 10^9。显然回溯算法不够快,我认为可以使用矩阵求幂来解决这个问题,但我对这一点没有任何想法。提前致谢!
每一行都采用以下形式:
x (y=x+1/x/x-1) (z=y+1/y/y-1) ...
x 的值并不重要,因此(对于 N = 5)每行有 3^4 = 81 种可能性。
从这里开始,您编写一个简单的程序来确定当前行中这 81 种可能性中的每一种在下一行中出现的频率。
从那里你应该能够找出一个公式,如果有一个简单的公式,否则你有一个 O(10^9) 算法,这至少比你开始的更好。
“最多”和“可以达到”确实与算法有点混乱。