M斐波那契数列
M斐波那契数列
Problem Description
M斐波那契数列F[n]是一种整数数列，它的定义如下：
F[0] = a F1 = b F[n] = F[n-1] * F[n-2] ( n > 1 )
现在给出a, b, n，你能求出F[n]的值吗？
Input
输入包含多组测试数据； 每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）
Output
对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。
Sample Input
0 1 0 6 10 2
Sample Output
0 60
题目解决
题目分析:
- 注意到n的范围最大到10^9,所以简单的进行递推时间和空间上都无法处理到限制范围内.
- 这道题涉及到取余运算,所以我们应该知道取余运算的其中一个性质:$$(ab) \mod p = ((a \mod p) (b \mod p)) \mod p$$
- 注意到该递推式和斐波那契数列有相似之处.
知识点:
1.斐波那契数列的矩阵运算
1.斐波那契数列
$fib(0) = 0$ $fib(1) = 1$ $fib(n) = fib(n-1)+fib(n-2)$ | n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | … | … | n-1 | n | | —–: | —–: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | | fib(n) | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 | 377 | … | … | fib(n-1) | fib(n) |
2.将斐波那契数列写到矩阵中
1.考虑按照以下表达式构造n个矩阵:
$$ A_{n} = \begin{bmatrix} fib(n) & fib(n+1) \ fib(n+1) & fib(n+2) \ \end{bmatrix} $$
2.得到如下矩阵
$A_{0} = \begin{bmatrix}0 & 1 \1 & 1 \ \end{bmatrix} $ $A_{1} = \begin{bmatrix}1 & 1 \1 & 2 \ \end{bmatrix} $ $ A_{2} = \begin{bmatrix}1 & 2 \2 & 3 \ \end{bmatrix} $ $A_{3} = \begin{bmatrix}2 & 3 \3 & 5 \ \end{bmatrix} $ $A_{4} = \begin{bmatrix}3 & 5 \5 & 8 \ \end{bmatrix} $ … … …
$A_{n} = \begin{bmatrix}fib(n) & fib(n+1) \ fib(n+1) & fib(n+2) \ \end{bmatrix} $
3.矩阵乘法运算
$A_{1} = \begin{bmatrix}1 & 1 \1 & 2 \ \end{bmatrix} = A_{0}A_{0}$ $ A_{2} = \begin{bmatrix}1 & 2 \2 & 3 \ \end{bmatrix} = A_{0}A_{0}A_{0}$ $A_{3} = \begin{bmatrix}2 & 3 \3 & 5 \ \end{bmatrix} = A_{0}A_{0}A_{0}A_{0} $
$ A_{4} = \begin{bmatrix}3 & 5 \5 & 8 \ \end{bmatrix} = A_{0}A_{0}A_{0}A_{0}A_{0}$ $A_{n} = \begin{bmatrix}fib(n) & fib(n+1) \fib(n+1) & fib(n+2) \ \end{bmatrix} = A_{0} ^ {n+1}$
\begin{array}{|rrrrrrrr|} \hline \color{red}{综上所述,要想求解f(n),求得A(n)或者A(n-2)即可} & \hline \end{array}
2.快速幂:
Q: 求解 $ x ^ N $ A: O(N)的算法:
ans = 1;
for(i = 1; i <= n; i++){
ans *= x;
}A: O(logN)的算法:
- 将N转换成二进制表示形式 $$ N = 2 ^ {k_{1}} + 2 ^ {k_{2}} + 2 ^ {k_{3}} + …. + 2 ^ {k_{n}}$$
- 要求解$x ^ N $,相当与计算$$ x ^ N = x ^ {2 ^ {k_{1}} + 2 ^ {k_{2}} + 2 ^ {k_{3}} + …. + 2 ^ {k_{n}}} = x^{2 ^ {k_{1}}}x^{2 ^ {k_{2}}}x^{2 ^ {k_{3}}}…x^{2 ^ {k_{n}}}$$
- 所以只要在依次求$x ^ {2^i} $ 的同时进行计算就好了,最终得到了O(logN)的计算幂运算的算法
举个例子:计算 $ x ^ {22} $
- 十进制下的22的二进制表示 : $ 22_{10} = 10110_{2}$
- $ N = 22 = 2^{4} + 2^{2} + 2^{1}$
- $ x^{22} = x^{2^{4} + 2^{2} + 2^{1}} = x^{16}x^{4}x^{2}$
- 可以看到如果是O(N)的算法,当前例子需要计算22次,而O(logN)的算法只需要计算5次
\begin{array}{|rrrrrrrr|} \hline & \color{red}{CODE:}& \hline \end{array}
typedef long long LL;
// 计算x^n,复杂度O(logN)
LL powN(LL x, LL n){
LL r = 1; // 计算结果
while(n){
if(n&1) r *= x; // 如果n的二进制表示i(i >= 0)的位置是1,则乘上x^(2^i)
x *= x; // 将x平方
n >>= 1; // 右移一位
}
return r; // 返回结果
}
// 计算x^n mod p, ( a * b ) % p = ( ( a % p ) * ( b * p ) ) % p 复杂度O(logN)
LL mod_powN(LL x, LL n, LL p){
LL r = 1; // 计算结果
while(n){
if(n&1) r = r * x % p; // 如果n的二进制表示i(i >= 0)的位置是1,则乘上x^(2^i)
x = x * x % p; // 将x平方
n >>= 1; // 右移一位
}
return r; // 返回结果
}3.费马小定理:
费马小定理是数论中的一个定理：假如a是一个整数，p是一个质数，那么 $a^{p}-a$是p的倍数，可以表示为 $$ a ^ p \equiv a (\mod p) $$ 如果a不是p的倍数，这个定理也可以写成 $$ a ^ {p-1} \equiv 1 (\mod p)$$ 费马小定理是欧拉定理的一个特殊情况：如果n和a的最大公因数是1，那么 $$ a^{φ(n)} \equiv 1 (\mod n) $$ 这里φ(n)是欧拉函数。欧拉函数的值是所有小于或等于n的正整数中与n互质的数的个数。假如n是一个素数（质数），则φ(n) = n-1，即费马小定理 注: $\equiv$是同余符号 $ a \mod p = b \mod p$ 可表示为 $ a \equiv b (\mod p)$
推导以下表达式: 当p是质数时: $$ a ^ n \equiv a ^ {(n \mod (p-1))} (\mod p) $$ 成立
证: $$ n = k(p-1) + (n \mod (p-1)) (k为整数) $$ $$ a ^ n \equiv a ^ {k(p-1) + (n \mod (p-1))} \equiv {a ^ {p-1}} ^ {k} a ^ {(n \mod (p-1))} (\mod p)$$ 由费马小定理可知: $$ {a ^ {p-1}} ^ {k} \equiv a ^ {p-1} \equiv 1(\mod p)$$ 得证: $$ a ^ n \equiv a ^ {(n \mod (p-1))} (\mod p) $$
回到题目:
1.分析
我们注意到虽然题目中的M斐波那契数列和斐波那契数列有异曲同工之处,但是一个计算的是乘法,一个是加法,但加法和乘法之间有着密切的联系.
2.算一算
先计算前几项的值: $$ f(0) = a = a ^ 1 b ^ 0 $$ $$ f(1) = b = a ^ 0 b ^ 1 $$ $$ f(2) = a b = a ^ 1 b ^ 1 $$ $$ f(3) = a b b = a ^ 1 b ^ 2 $$ $$ f(4) = a a b b b = a ^ 2 b ^ 3 $$ $$ f(4) = a a a b b b b b= a ^ 3 b ^ 5 $$ $$ ……………………………………………………..$$ $$ f(n) = f(n-1)f(n-2) = a ^ x b ^ y $$ |n| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 11 | 12 | 13 | … | … | n-1 | n | |——–| —–: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | |x| 1 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | … | … | fib(n-2) | fib(n-1) | |y| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | … | … | fib(n-1) | fib(n) |
不难得出: $$ f(0) = a $$ $$ f(1) = b $$ $$ f(n) = f(n-1)f(n-2) = a ^ {fib(n-1)} b ^ {fib(n)} (n >= 2) $$
通过上面费马小定理证明的结论,当p是质数时: $$ a ^ n \equiv a ^ {(n \mod (p-1))} (\mod p) $$ 所以我们实际上需要计算的就是下面的表达式(p = 1000000007): $$ f(n) \mod p= f(n-1)f(n-2) \mod p = a ^ {fib(n-1) \mod p-1} b ^ {fib(n) \mod p-1} \mod p(n >= 2) $$
1.计算类似于计算整数的快速幂算法计算矩阵的幂 $A_{n-1} = A_{0} ^ {n}$ $A_{0} = \begin{bmatrix}0 & 1 \1 & 1 \ \end{bmatrix}$ $A_{n-1} = \begin{bmatrix}fib(n-1) & fib(n) \fib(n) & fib(n+1) \ \end{bmatrix} = A_{0} ^ {n}$
计算矩阵的幂时,我们实际上需要得到的结果是: $$ A_{n-1} \mod p-1 = \begin{bmatrix}fib(n-1) \mod p-1 & fib(n) \mod p-1 \fib(n) \mod p-1 & fib(n+1) \mod p-1 \ \end{bmatrix} = (A_{0} \mod p-1) ^ {n} \mod p-1 $$
如果理解了上面的快速幂算法的话,这实现起来将会非常简单
2.得到$fib(n-1) \mod p-1$ 和 $fib(n) \mod p-1$ 之后,设这两个数为x,y,用整数的快速幂算法计算: $$a ^ x b^y \mod p = (a ^ x \mod p b^y \mod p) \mod p$$
\begin{array}{|rrrrrrrr|} \hline & \color{red}{CODE:}& \hline \end{array}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD1 = 1e9+7; // p
const int MOD2 = 1e9+6; // p-1
LL a,b,n;
typedef struct Matrix{ // 矩阵结构体
LL arr[2][2];
}Matrix;
Matrix unit = { // 单位矩阵
1,0,
0,1
};
Matrix A0 = { // A0矩阵
0,1,
1,1
};
// 矩阵a*b
Matrix matrixMulti(Matrix a, Matrix b){
int i,j,k;
Matrix tmp;
for(i = 0; i < 2; i++){
for(j = 0; j < 2; j++){
tmp.arr[i][j] = 0;
for(k = 0; k < 2; k++){
tmp.arr[i][j] += (a.arr[i][k]*b.arr[k][j])%MOD2;
tmp.arr[i][j] %= MOD2;
}
}
}
return tmp;
}
// 矩阵快速幂,计算的结果对MOD2取余
Matrix matrixPow(Matrix a, LL n){
Matrix r = unit, base = a;
while(n){
if(n&1) r = matrixMulti(r,base);
base = matrixMulti(base, base);
n >>= 1;
}
return r;
}
// 整数快速幂,计算的结果对MOD1取余
LL powN(LL a, LL n){
LL r = 1, base = a%MOD1;
while(n){
if(n&1) r = r*base%MOD1;
base = base*base%MOD1;
n >>= 1;
}
return r;
}
int main(){
//freopen("in.txt", "r", stdin);
Matrix An_1;
while(~scanf("%lld%lld%lld", &a, &b, &n)){ // 输入a,b,n
An_1 = matrixPow(A0,n); // 计算An_1
printf("%lld\n", powN(a, An_1.arr[0][0]) * powN(b, An_1.arr[1][0]) % MOD1);
}
return 0;
}思考:
Q: 为什么要使用费马小定理? A: 因为 $ x \mod p-1 <= x $ 所以可以减少计算整数幂时候的计算次数,不使用费马小定理会超时.