OR9. 斐波拉契加强版
描述
对于斐波拉契经典问题，我们都非常熟悉，通过递推公式F(n) = F(n - 1) + F(n - 2)，我们可以在线性时间内求出第n项F(n)，现在考虑斐波拉契的加强版，我们要求的项数n的范围为int范围内的非负整数，请设计一个高效算法，计算第n项F(n-1)。第一个斐波拉契数为F(0) = 1。
给定一个非负整数，请返回斐波拉契数列的第n项，为了防止溢出，请将结果Mod 1000000007。
3
返回：2
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-10-31
class Fibonacci {
int tmp[2][2], now[2][2];
inline int addmul(int a, int m0, int m1)
{
return (a + (long long) m0 * m1) % 1000000007;
}
void mul(int C[][2], int A[][2], int dime)
{
int i, j, k;
memcpy(tmp, C, sizeof (tmp));
for (i = 0; i < dime; i++)
for (j = 0; j < dime; j++)
{
int t = 0;
for (k = 0; k < dime; k++)
{
t = addmul(t, A[i][k], tmp[k][j]);
}
C[i][j] = t;
}
}
void getpow(int res[][2], int mat[][2], int n, int dime)
{
memcpy(now, mat, sizeof (now));
memset(res, 0, sizeof (now));
for (int i = 0; i < dime; i++)
res[i][i] = 1;
while (n != 0)
{
if (n & 1)
{
mul(res, now, dime);
}
n >>= 1;
mul(now, tmp, dime);
}
}
public:
int getNthNumber(int n) {
// write code here
if(n<2)return 1;
int res[2][2],A[2][2]={{1,1},{1,0}};
getpow(res,A,n,2);
return res[0][0];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 396KB, 提交时间: 2020-10-31
class Fibonacci {
int tmp[2][2], now[2][2];
inline int addmul(int a, int m0, int m1)
{
return (a + (long long) m0 * m1) % 1000000007;
}
void mul(int C[][2], int A[][2], int dime)
{
int i, j, k;
memcpy(tmp, C, sizeof (tmp));
for (i = 0; i < dime; i++)
for (j = 0; j < dime; j++)
{
int t = 0;
for (k = 0; k < dime; k++)
{
t = addmul(t, A[i][k], tmp[k][j]);
}
C[i][j] = t;
}
}
void getpow(int res[][2], int mat[][2], int n, int dime)
{
memcpy(now, mat, sizeof (now));
memset(res, 0, sizeof (now));
for (int i = 0; i < dime; i++)
res[i][i] = 1;
while (n != 0)
{
if (n & 1)
{
mul(res, now, dime);
}
n >>= 1;
mul(now, tmp, dime);
}
}
public:
int getNthNumber(int n) {
// write code here
if(n<2)return 1;
int res[2][2],A[2][2]={{1,1},{1,0}};
getpow(res,A,n,2);
return res[0][0];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2021-09-29
class Fibonacci {
public:
void MultMetri(long long base1[2][2],long long base2[2][2])
{
long long tmp[2][2]={0};
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
tmp[i][j]=(base1[i][0]*base2[0][j]+base1[i][1]*base2[1][j])%1000000007;
}
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
base1[i][j]=tmp[i][j];
}
}
int getNthNumber(int n) {
long long base[2][2]={{1,1},{1,0}};
long long ret[2][2]={{1,0},{1,0}};
while(n)
{
if(n%2)
MultMetri(ret,base);
MultMetri(base,base);
n=n/2;
}
return (int)(ret[0][0]);
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 432KB, 提交时间: 2022-03-05
#include <algorithm>
#include <string.h>
const long long Mod = 1e9+7;
class Fibonacci {
public:
struct Matrix {
long long a[3][3];
Matrix() { memset(a, 0, sizeof a); }
Matrix operator*(const Matrix &b) const {//重载矩阵乘法
Matrix res;
for (int i = 1; i <= 2; ++i)
for (int j = 1; j <= 2; ++j)
for (int k = 1; k <= 2; ++k)
res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]%Mod) % Mod;
return res;
}
}ans,base;//初始矩阵ans，乘法矩阵base
void init() {
base.a[1][1] = 1;
base.a[1][2] = 1;
base.a[2][1] = 1;
base.a[2][2] = 0;
//base.a[3][1] = 1;
//base.a[3][3] = 1;
ans.a[1][1] = 1;
ans.a[1][2] = 1;
//ans.a[1][3] = 0;
}
void qpow(int b) {//矩阵快速乘
while (b) {
if (b & 1) ans = ans * base;
base = base * base;
b >>= 1;
}
}
int getNthNumber(int n) {
init();
if(n <= 1)
{
return 1;
}
if(n == 2)
{
return 2;
}
else
{
qpow(n-1);
return ans.a[1][1]%Mod;
}
// write code here
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 480KB, 提交时间: 2020-11-01
class Fibonacci {
int tmp[2][2], now[2][2];
inline int addmul(int a, int m0, int m1)
{
return (a + (long long) m0 * m1) % 1000000007;
}
void mul(int C[][2], int A[][2], int dime)
{
int i, j, k;
memcpy(tmp, C, sizeof (tmp));
for (i = 0; i < dime; i++)
for (j = 0; j < dime; j++)
{
int t = 0;
for (k = 0; k < dime; k++)
{
t = addmul(t, A[i][k], tmp[k][j]);
}
C[i][j] = t;
}
}
void getpow(int res[][2], int mat[][2], int n, int dime)
{
memcpy(now, mat, sizeof (now));
memset(res, 0, sizeof (now));
for (int i = 0; i < dime; i++)
res[i][i] = 1;
while (n != 0)
{
if (n & 1)
{
mul(res, now, dime);
}
n >>= 1;
mul(now, tmp, dime);
}
}
public:
int getNthNumber(int n) {
// write code here
if(n<2)return 1;
int res[2][2],A[2][2]={{1,1},{1,0}};
getpow(res,A,n,2);
return res[0][0];
}
};