mysql连接测试不成功的原因有哪些
335
2022-08-27
Sam 数(矩阵乘法)
Sam 数
Sam 数是指相邻的两位数字相差不超过 2 的数。求长度为 n 的 Sam 数有多少个。输出对 1000000007 取余后的结果。 n <= 10^18 。
分析
首先,递推式很明显:
用 f(i, j) 表示第 j 位为 i 时总的个数(先不考虑各种特殊情况),则
f(i, j) = f(i-2, j-1) + f(i-1, j-1) + f(i, j-1) + f(i+1, j-1) + f(i+2, j-1)
我们考虑这样一个矩阵 A :
[ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
这个 1*10 矩阵表示当第一位为 i 且一共只有 1 位时的方案数。
考虑另一个矩阵 B :
这个矩阵的第 i 行 第 j 列 表示当某一位为 j ,相邻一位取 i 时的方案数。
我们将矩阵 A 与 B 相乘一次,可以得到一个 1*10 的矩阵,很明显,这个矩阵的第 i个元素的值表示当第一位为 i 且一共有 2 位时的方案数,那么矩阵的元素和即 n=2 时的结果。
同理,将 A 不断地与 B 相乘,对于 n ,最终得到的矩阵为 A * (B ^ n-1) 的结果,这个矩阵的元素和即最终答案。注意 n=1 的时候特判,这时 0 也算一个方案,所以答案为 10 。
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~