最近有一道编程题一直在愁我, 希望有人能帮我一下.

[YUX]

题面很简单, 但是我没有在数较大的情况下优化的经验, 所以计算时间较长

• 有这样一个数列,第一项是 1, 第二项是 3.
• 递推公式和 fibonacci 数列是一样的, 但有一个额外的条件, 每个数要取模(余数).
• 例如 mod=127 的前 15 项如下

i=1,r=1
i=2,r=3
i=3,r=4
i=4,r=7
i=5,r=11
i=6,r=18
i=7,r=29
i=8,r=47
i=9,r=76
i=10,r=123
i=11,r=72
i=12,r=68
i=13,r=13
i=14,r=81
i=15,r=94

• 要求的是 f(index,mod) , 给定 index 和 mod, 输出结果
• 比如 f(10,127)=123, f(6,127)=18

---

真正的问题来了, index 和 mod 会是很大的数, 我就懵了.

请用这个数据检验:

index = 2**110502
mod = 2**110503-1
f(index,mod)=0

目前 python mbp-i9 用时 79.48 秒

[lance6716]

矩阵乘法计算斐波那契，然后快速幂的优化

[yinsky]

动态规划？

[YUX]

@lance6716 #1 如果先把数列算出来再取模数就太大了, 边算边 mod 数就不会超过 mod

[YUX]

@yinsky #2 python 的话远超最大递归限制了

[yinsky]

@YUX 本身类似斐波那契数列就没有啥好的方法，基数太大肯定慢呀，不好搞。

[zh4710jj]

斐波那契数列有通项公式的吧，模运算的部分是否可以放到最后再算，最后就是一个大数模 127

[YUX]

@zh4710jj #6 是有通项公式, 但是公式里有根号 5 这个无理数, 算的时候计算精度不够

[litmxs]

矩阵快速幂

[litmxs]

https://www.cnblogs.com/ranjiewen/p/8998112.html

[gwy15]

我优化到了在 numba.jit 程度下 1.5s 左右，但是算出来并不是 0 。如果楼主确定这个是 0，那我估计可能是 numba 的问题，我得换 c++ 重新写下

[YUX]

@gwy15 numba 在 2^64 之后就溢出了

[fx050622]

我觉得你想复杂了，取模应该不影响 An 的计算的.
mod(A(n+1))=mod(mod(A(n))*A)
array=[1,1,1,0]
我自己 PC 试了下 782736251 次 5.3s

def multiply(array: Array[Int], times: Int, mode: Int = 127):Unit = {
if (times > 0) {
val t1 = array(0)
val t2 = array(1)
val t3 = array(2)
val t4 = array(3)
array(0) = (t1 + t2) % mode
array(1) = t1
array(2) = (t3 + t4) % mode
array(3) = t3
multiply(array, times - 1)
}
}

[YUX]

@fx050622 #12 计算我给出的那个数据,用了多少时间? 结果是 0 吧? 谢了

[BiteTheDust]

这是一个典型的矩阵快速幂优化线性递推
当然 也可以直接用 Reeds Sloane 算法

[liyunlong41]

递推应该可以用矩阵快速幂来优化

[gwy15]

用 rust 和 c++ 重新写了一遍，rust 的高精度库实现不太好，还是得用 GMP 。

复杂度是 log(index) log(mod) log(log(mod))，
也就是，N=110503 的情况下，N^2 log(N)。算出来是 204e9 数量级，大概就是要一百秒的样子。我用 c++ + GMP 跑出来是 95s，4.0G 主频

[YUX]

@gwy15 #16 看来是不能再快了,我用的是 python+gmp, 最后结果是 0 吧?

[yuruizhe]

@YUX 就是 6 楼说的通项公式，公式用二项式定理展开，对根号 5 合并相消，最后应该得到一个整数运算公式
设 Comb()表述组合数公式
最后结果应该是[Comb(1,n)*x^0 + Comb(3,n)*x^2 + Comb(5,n)*x^4 + Comb(7,n)*x^6 + ....]/2^n

[superrichman]

发现一个有趣的东西，这个数列的值可以这样表达

2*fibb(x) - fibb(x-1)

1=2*1-1
3=2*2-1
4=2*3-2
7=2*5-3
11=2*8-5
18=2*13-8
29=2*21-13