「POJ 3070」Fibonacci

在 Fibonacci 数列中，$F_0 = 0, F_1 = 1, F_n = F_{n - 1} + F_{n - 2}$。

现给定整数 $n, m (0 leq n leq 2 imes 10^9, m=10000)$，求 $F_n mod m$。

链接

POJ 3070

题解

朴素算法是直接循环递推，时间复杂度为 $O(n)$。

$F_n$ 变化的形式是线性递推，所以可以用矩阵加速递推。$F_n$ 只与 $F_{n-1}$ 和 $F_{n-2}$ 有关，只需要保存最近的两个 Fibonacci 数，即可得到下一个 Fibonacci 数。

设 $F(n)$ 表示一个 $1 imes 2 $ 的矩阵，即 $F(n) = egin{bmatrix} F_n & F_{n+1}end{bmatrix}$。

我们知道 $F(n - 1)$，想要计算出 $F(n)$。因为 $F(n-1) = [F_{n-1}, F_n]$，所以 $F(n)$ 中， $F_n$ 为原矩阵第 $2$ 个数， $F_{n+1}$ 为原矩阵第 $1$ 个数和第 $2$ 个数之和。根据矩阵乘法定义，相当于：
$$
F(n)=F(n-1) imes
egin{bmatrix}
0 & 1 \
1 & 1 \
end{bmatrix}
$$
令 $F(0) = egin{bmatrix} 0 & 1end{bmatrix}, A=egin{bmatrix} 0 & 1 \ 1 & 1 \ end{bmatrix}$，那么：
$$
F(n)=F(0) imes A^n
$$
利用矩阵快速幂求 $A^n$ 即可。

代码

#include <cstdio>
#include <cstring>

typedef long long ll;

const int P = 10000;

struct Matrix{
	ll f[5];
	ll a[5][5];
	ll t[5][5];

	void mulMatrix() {
		memcpy(t[0], f, sizeof(f));
		memset(f, 0, sizeof(f));
		for (int i = 1; i <= 2; i++) {
			for (int k = 1; k <= 2; k++) {
				f[i] = (f[i] + (t[0][k] * a[k][i]) % P) % P;
			}
		}
	}

	void mulSelf() {
		memcpy(t, a, sizeof(a));
		memset(a, 0, sizeof(a));
		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= 2; j++) {
				for (int k = 1; k <= 2; k++) {
					a[i][j] = (a[i][j] + (t[i][k] * t[k][j]) % P) % P;
				}
			}
		}
	}

	void _init(){
		ll _f[5] = {0, 0, 1};
		ll _a[5][5] = {
			{0, 0, 0},
			{0, 0, 1},
			{0, 1, 1}
		};
		memcpy(f, _f, sizeof(_f));
		memcpy(a, _a, sizeof(_a));
	}

	void _main(ll n){
		_init();
		while (n) {
			if (n & 1) mulMatrix();
			mulSelf();
			n >>= 1;
		}
		printf("%lld
", f[1]);
	}
};

int main() {
	ll n;
	while (scanf("%lld", &n) && n != -1) {
		Matrix fib;
		fib._main(n);
	}
	return 0;
}