14071: 【原4071】Fibonacci数列
题目
题目描述
author: Engineev 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4071
Description
面包希望知道大家的计科导课和线性代数课有没有好好上，所以出了这一道题目。（<-这是hint）
大家都知道有一个数列叫做Fibonacci数列，它是这样定义的\(a_0 = a_1 = 1\)，\(a_{n+1} = a_n + a_{n-1}\). 面包想要知道Fibonacci的第\(n\)项是多少. 由于结果可能十分大，所以需要你对结果mod \(10^9 + 7\)
Input Format
一个数字\(n\).
Output Format
输出对应的\(a_n % 10^9+7\)即可.
Sample Input
5
Sample Output
8
数据范围
对于70%的数据，确保\(n \le 10^8\).
对于100%的数据，确保\(n \le 10^{18}\)
BugenZhao's solution
//
// Created by BugenZhao on 2019/5/17.
//
#include <iostream>
#include <string>
using std::ios, std::cin, std::cout, std::endl, std::string;
using ll=long long;
using ull=unsigned long long;
const int P = 1e9 + 7;
class Matrix2D {
public:
ll a, b, c, d;
Matrix2D(ll a, ll b, ll c, ll d) :
a(a), b(b), c(c), d(d) {}
};
Matrix2D operator*(const Matrix2D &x, const Matrix2D &y) {
ll a = x.a * y.a + x.b * y.c;
ll b = x.a * y.b + x.b * y.d;
ll c = x.c * y.a + x.d * y.c;
ll d = x.c * y.b + x.d * y.d;
return Matrix2D(a % P, b % P, c % P, d % P);
}
Matrix2D pow(const Matrix2D &m, ull p) {
if (p == 0) return Matrix2D(1, 0, 0, 1);
if (p == 1) return m;
Matrix2D tmp = pow(m, p / 2);
if (p % 2) return tmp * tmp * m;
else return tmp * tmp;
}
int main() {
ull n;
cin >> n;
Matrix2D ans = pow(Matrix2D(1, 1, 1, 0), n);
cout << ans.a << endl;
return 0;
}
FineArtz's solution
/* Fibonacci数列 */
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
class matrix{
public:
matrix(long long a, long long b, long long c, long long d)
: a11(a), a12(b), a21(c), a22(d) {}
matrix(const matrix &a) : a11(a.a11), a12(a.a12), a21(a.a21), a22(a.a22) {}
long long a11, a12, a21, a22;
};
inline matrix operator *(const matrix &m1, const matrix &m2){
matrix ret(0, 0, 0, 0);
ret.a11 = (m1.a11 * m2.a11 % MOD + m1.a12 * m2.a21 % MOD) % MOD;
ret.a12 = (m1.a11 * m2.a12 % MOD + m1.a12 * m2.a22 % MOD) % MOD;
ret.a21 = (m1.a21 * m2.a11 % MOD + m1.a22 * m2.a21 % MOD) % MOD;
ret.a22 = (m1.a21 * m2.a12 % MOD + m1.a22 * m2.a22 % MOD) % MOD;
return ret;
}
matrix pow(matrix x, long long n){
matrix ret(1, 0, 0, 1), t(x);
while (n != 0){
if (n & 1){
ret = ret * t;
}
t = t * t;
n >>= 1;
}
return ret;
}
int main(){
long long n;
cin >> n;
matrix f(1, 1, 1, 0);
f = pow(f, n + 1);
cout << f.a21 << endl;
}
ligongzzz's solution
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
using namespace std;
constexpr long long mod = (long long)(1e9 + 7);
class matrix {
public:
long long a11 = 0, a12 = 0;
long long a21 = 0, a22 = 0;
matrix() = default;
matrix(long long a11, long long a12, long long a21, long long a22) :a11(a11% mod), a12(a12% mod)
, a21(a21% mod), a22(a22% mod) {}
matrix(matrix&& other){
swap(*this, other);
}
void operator=(matrix&& other) {
swap(*this, other);
}
matrix&& operator*(const matrix& b) const{
matrix temp;
temp.a11 = (a11 * b.a11 + a12 * b.a21) % mod;
temp.a12 = (a11 * b.a12 + a12 * b.a22) % mod;
temp.a21 = (a21 * b.a11 + a22 * b.a21) % mod;
temp.a22 = (a21 * b.a12 + a22 * b.a22) % mod;
return std::move(temp);
}
};
matrix&& fast_pow(const matrix& a, long long b) {
matrix ans(1, 0, 0, 1), base(a.a11, a.a12, a.a21, a.a22);
for (; b; b >>= 1) {
if (b & 1LL)
ans = ans * base;
base = base * base;
}
return std::move(ans);
}
int main() {
long long n;
scanf("%lld", &n);
matrix temp(1, 1, 0, 0);
matrix to(1, 1, 1, 0);
matrix ans;
ans = temp * fast_pow(to, n - 1);
printf("%lld", ans.a11);
return 0;
}
q4x3's solution
/**
* 矩阵快速幂求斐波那契
**/
#include <iostream>
#define ll long long
using namespace std;
const ll mo = 1e9 + 7;
struct mat {
ll a11, a12, a21, a22;
mat():a11(0), a12(1), a21(1), a22(1) {}
mat operator*(const mat &other) const {
mat tmp;
tmp.a11 = (a11 * other.a11 % mo + a12 * other.a21 % mo) % mo;
tmp.a12 = (a11 * other.a12 % mo + a12 * other.a22 % mo) % mo;
tmp.a21 = (a21 * other.a11 % mo + a22 * other.a21 % mo) % mo;
tmp.a22 = (a21 * other.a12 % mo + a22 * other.a22 % mo) % mo;
return tmp;
}
};
mat binary_pow(ll n) {
mat tmp, cache;
tmp.a11 = 1; tmp.a12 = 0; tmp.a21 = 0; tmp.a22 = 1;
while(n > 0) {
if(n & 1) {
tmp = tmp * cache;
}
cache = cache * cache;
n >>= 1;
}
return tmp;
}
ll n;
int main() {
cin >> n;
mat a = binary_pow(n);
printf("%lld\n", a.a22);
}
skyzh's solution
#include <iostream>
using namespace std;
struct Matrix2x2 {
unsigned long long s[2][2];
};
const int S = 1e9 + 7;
Matrix2x2 mul(const Matrix2x2 &a, const Matrix2x2 &b) {
Matrix2x2 c;
/*
* a 0 1 b 0 1
* a 2 3 b 2 3
*/
c.s[0][0] = (a.s[0][0] * b.s[0][0] + a.s[0][1] * b.s[1][0]) % S;
c.s[0][1] = (a.s[0][0] * b.s[0][1] + a.s[0][1] * b.s[1][1]) % S;
c.s[1][0] = (a.s[1][0] * b.s[0][0] + a.s[1][1] * b.s[1][0]) % S;
c.s[1][1] = (a.s[1][0] * b.s[0][1] + a.s[1][1] * b.s[1][1]) % S;
return c;
}
unsigned long long fab(unsigned long long n) {
Matrix2x2 base, f;
base.s[0][0] = 1;
base.s[0][1] = 1;
base.s[1][0] = 0;
base.s[1][1] = 0;
f.s[0][0] = 1;
f.s[0][1] = 1;
f.s[1][0] = 1;
f.s[1][1] = 0;
while (n > 0) {
if (n & 1) base = mul(base, f);
f = mul(f, f);
n >>= 1;
}
return base.s[0][1];
}
int main() {
unsigned long long N;
cin >> N;
cout << fab(N) << endl;
return 0;
}
victrid's solution
#include <cstdio>
#include <iostream>
#define mod 1000000007LL
using namespace std;
struct matrix {
long long a1, a2, b1, b2;
matrix operator*(const matrix& rhs) {
return matrix{(a1 * rhs.a1 + a2 * rhs.b1) % mod, (a1 * rhs.a2 + a2 * rhs.b2) % mod, (b1 * rhs.a1 + b2 * rhs.b1) % mod, (b1 * rhs.a2 + b2 * rhs.b2) % mod};
}
};
matrix fibo{1, 1, 1, 0};
matrix init{1, 0, 0, 1};
int main() {
long long n;
scanf("%lld", &n);
for (long long i = n - 1; i; i >>= 1) {
if (i & 1LL)
init = fibo * init;
fibo = fibo * fibo;
}
printf("%lld", (init.a1 + init.a2) % mod);
return 0;
}