斐波那契数

Fibonacci 数的性质太多了，单独开一个页面记录

矩阵乘法求第n项

这个比较基础，不再解释

通项公式求第n项

可以用扩域，每个数字记录x + y * sqrt(5)，直接用快速幂计算

取模的循环节

Pisano Sequence

有多少个n阶行列式，模p不为0，每一位在0和p-1之间的整数

p⁽ⁿ2) * ((p-1)/p)^n

poj 3070

输入n，求F[F[F[F[n]]]] % 1000000007

A^t = I (mod p)

t = (a sqrt(p) - b)

最小的 m 使得
A^m mod p = I
一定是 (p^2 - 1) * (p^2 - p)
(p^3 - 1) * (p^3 - p) * (p^3 - p^2)

x^(x^(x^(x^(n % phi(phi(phi(phi(p))))) % phi(phi(phi(p)))) phi(phi(p))) % phi(p)) % p

最小的 m 使得
x^m mod p = 1
一定是 (p-1) 的约数

2^3 % 7 = 1


x^(phi(p)) % p == 1

多项式取模

f[0] = 0
f[1] = 1
f[2] = 1
f[3] = 2
f[4] = 3
f[5] = 5
f[6] = 8
f[7] = 13
f[8] = 21
f[9] = 34
f[10] = 55

f[i] = f[i - 1] + f[i - 2]

x ** 10 % (x ** 2 - x - 1) == a * x + b

f[10] = a * f[1] + b * f[0] = a

x ** 1 % (x**2-x-1) == x
x ** 2 % (x**2-x-1) == x + 1
x ** 4 % (x**2-x-1) == (x + 1) ** 2 % (x**2-x-1) == (x ** 2 + 2 * x + 1) % (x**2-x-1) = 3 x + 2
x ** 8 % (x**2-x-1) == (3 x + 2) ** 2 % (x**2-x-1) == (9 x ** 2 + 12 * x + 4) % (x**2-x-1) = 21 x + 13

x ** 10 % (x**2-x-1) == (21 x + 13) * (x + 1) % (x**2-x-1) == (21 x ** 2 + 34 x + 13) % (x**2-x-1) = 55x + 34

% (x ** 1000 - x - 1)

f[i] = a[1] f[i - 1] + a[2] f[i - 2] + ... + a[k] f[i - k]

(xk - a[1]x(k-1) - a[2]x**(k-2) - ... -a[k]x**0)

xn % (xk - a[1]x**(k-1) - a[2]x**(k-2) - ... -a[k]x0) =
r[k-1] * x(k-1) + ... + r[1] * x + r[0]

f[n] = r[k-1] * f[k-1] + ... r[1] * f[1] * r[0] * f[0]

在运算中会用到多项式乘法和多项式取模
这两部分都可能可以用 FFT优化

如果已知数列的递推公式
这个方法比直接矩阵乘法要快，矩阵乘法的时间复杂度是 O(k^3 log n)
这个方法暴力实现多项式乘法和多项式取模是 O(k^2 log n)

Fibonacci 数的最大公约数

gcd(F[n], F[m]) = F[gcd(n, m)]

https://en.wikipedia.org/wiki/Fibonacci_number

a method about recursion

def query(n): // return (f[n], f[n+1])
    if n == 0:
        return (0, 1)
    if n is odd:
        query(n-1) // get f[n-1] and f[n]
        return (f[n], f[n-1]+f[n])
    if n is even:
        query(n / 2) // get f[n/2], f[n/2+1]
        f[n+1] = f[n/2]*f[n/2] + f[n/2+1]*f[n/2+1]
        f[n] = (f[n/2-1]+f[n/2+1]) * f[n/2]
        f[n] = (f[n/2+1] - f[n/2] + f[n/2+1]) * f[n/2]

Solving homogeneous linear recurrence relations with constant coefficients
F[k+1] F[k]
0 0

1 1
1 0

=
F[k]+F[k+1] F[k+1]
0 0

=
F[k+2] F[k+1]
0 0

F[1] [0]
0 0

B ** n

f[n+1] f[n]
0 0

spoj FIBHARD

https://www.spoj.com/problems/FIBHARD
Fibonacci mod p has a period
f[n] % 998244353
f[n] % 998244353 = f[n - 1996488708] % 998244353
f[n] % 998244353 = f[n % 1996488708] % 998244353