一个人的巴黎

用户名：uq_36478041918

访问量：14986

签　名：

等　　级
排　　名	105
经　　验	8303
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

复制书稿(动态规划 + 贪心)
浏览：440

数的划分(DFS + 回溯 +剪枝【每步详解】)(另附DP算法)
浏览：702

数的划分(动态规划背包问题)
浏览：370

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

斐波那契(快速矩阵幂运算)

　　作者: 一个人的巴黎　　　　发表时间：2022-01-29 16:54:26 浏览：359　|　评论：0　

原题链接：蓝桥杯2014年第五届真题-斐波那契

斐波那契数列大家都非常熟悉。它的定义是：

f(x)  =  1  ....  (x=1,2)
f(x)  =  f(x-1)  +  f(x-2)  ....  (x> 2)

对于给定的整数  n  和  m，我们希望求出：
f(1)  +  f(2)  +  ...  +  f(n)  的值。但这个值可能非常大，所以我们把它对  f(m)  取模。
公式如下

(∑f(i))%f(m)
但这个数字依然很大，所以需要再对  p  求模。

输入

输入为一行用空格分开的整数  n  m  p  (0  <   n,  m,  p  <   10^18)

输出

输出为1个整数，表示答案

样例输入
2 3 5
样例输出
0

分析：
f(x)=f(x-1)+f(x-2) --> f(x+1)=f(x)+f(x-1) --> f(x)=f(x+1)-f(x-1)
列项相消得：∑f(n)=f(n+2)-1
原题(∑f(i))%f(m)%mod <--> (f(n-2)-1)%f(m)%mod <--> f(n-2)%f(m)%mod-1
下面稍微优化一下:
--如果m>=n-2,那么余f(m)就没有意义，即等价于f(n-2)%mod-1
--如果m<n-2,那么就要求f(m)
数据规模较小，就用迭代

下面因为规模很大，数据很大，所以进一步优化:
运算性能优化--快速斐波那契<--矩阵运算<--快速矩阵运算O(logn)
数据规模优化--mod带入矩阵乘法中，每次乘和每次加，都对结果进行模运算，让运算数在LL的范围内

再再再再来一次优化：
大数的相乘可以用整数快速乘法，并在乘法中加入模运算

以下是优化前的迭代算法：
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long LL;
LL n, m, mod;

void solve1()
{
    LL a = 1, b = 1;
    LL fibM, fibN_2;
    if (m >= n + 2)
    {
        for (int i = 3; i <= n + 2; i++)
        {
            LL t = a;
            a = b;
            b += t;
        }
        fibM = b;
        cout << fibM % mod - 1 << endl;
    }
    else
    {
        for (int i = 3; i <= n + 2; i++)
        {
            LL t = a;
            a = b;
            b += t;
            if (i == m) fibM = b;
        }
        fibN_2 = b;
        cout << fibN_2 % fibM % mod - 1 << endl;
    }
}
int main()
{
    cin >> n >> m >> mod;
    solve1();
    return 0;
}
```

运算性能优化后的算法:
```cpp
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef unsigned long long LL;
LL n, m, mod;
//矩阵定义
class M {
public:
    LL data[2][2];
    M() { memset(data, 0, sizeof(data)); }
};
//矩阵相乘
M* mul(M* m1, M* m2)
{
    M* ans = new M();
    ans->data[0][0] = m1->data[0][0] * m2->data[0][0] + m1->data[0][1] * m2->data[1][0];
    ans->data[0][1] = m1->data[0][0] * m2->data[0][1] + m1->data[0][1] * m2->data[1][1];
    ans->data[1][0] = m1->data[1][0] * m2->data[0][0] + m1->data[1][1] * m2->data[1][0];
    ans->data[1][1] = m1->data[1][0] * m2->data[0][1] + m1->data[1][1] * m2->data[1][1];
    return ans;
}
//m的n次幂
M* mPow(M* m, int n)
{
    M* E = new M();//E为单位矩阵
    E->data[0][0] = 1;
    E->data[1][1] = 1;
    while (n != 0)
    {
        if (n & 1 == 1)
        {
            E = mul(E, m);
        }
        m = mul(m, m);//m按平方倍增
        n >>= 1;//右移1位
    }
    return E;
}
//求斐波那契，由[f2,f1][1 1]^(n-2)=[fn,fn-1]，f(n)即为所求矩阵二维数组的第一位
//                    [1 0]
LL fib(LL i)
{
    //求[1,1]B^(n-2),即[fn,fn-1]
    M* A = new M();
    A->data[0][0] = 1;
    A->data[0][1] = 1;
    M* B = new M();
    B->data[0][0] = 1;
    B->data[0][1] = 1;
    B->data[1][0] = 1;
    M* ans = mul(A, mPow(B, i - 2));
    return ans->data[0][0];
}

void solve2()
{
    if (m >= n + 2)
        cout << fib(n + 2) % mod - 1 << endl;
    else
        cout << fib(n + 2) % fib(m) % mod - 1 << endl;
}

int main()
{
    cin >> n >> m >> mod;
    solve2();
    return 0;
}
```
数据规模优化后的算法：
```cpp
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef unsigned long long LL;
LL n, m, mod;
//矩阵定义
class M {
public:
    LL data[2][2];
    M() { memset(data, 0, sizeof(data)); }
};
//矩阵相乘
M* mul(M* m1, M* m2,LL mod)
{
    M* ans = new M();
    ans->data[0][0] = ((m1->data[0][0] * m2->data[0][0]) % mod + (m1->data[0][1] * m2->data[1][0]) % mod) % mod;
    ans->data[0][1] = ((m1->data[0][0] * m2->data[0][1]) % mod + (m1->data[0][1] * m2->data[1][1]) % mod) % mod;
    ans->data[1][0] = ((m1->data[1][0] * m2->data[0][0]) % mod + (m1->data[1][1] * m2->data[1][0]) % mod) % mod;
    ans->data[1][1] = ((m1->data[1][0] * m2->data[0][1]) % mod + (m1->data[1][1] * m2->data[1][1]) % mod) % mod;
    return ans;
}
//m的n次幂，快速幂算法
M* mPow(M* m, int n,LL mod)
{
    M* E = new M();//E为单位矩阵
    E->data[0][0] = 1;
    E->data[1][1] = 1;
    while (n != 0)
    {
        if (n & 1 == 1)
        {
            E = mul(E, m,mod);
        }
        m = mul(m, m,mod);//m按平方倍增
        n >>= 1;//右移1位
    }
    return E;
}
//求斐波那契，由[f2,f1][1 1]^(n-2)=[fn,fn-1]，f(n)即为所求矩阵二维数组的第一位
//                     [1 0]
LL fib(LL i)
{
    //求[1,1]B^(n-2),即[fn,fn-1]
    M* A = new M();
    A->data[0][0] = 1;
    A->data[0][1] = 1;
    M* B = new M();
    B->data[0][0] = 1;
    B->data[0][1] = 1;
    B->data[1][0] = 1;
    M* ans = mul(A, mPow(B, i - 2,mod),mod);
    return ans->data[0][0];
}

LL fib(LL i,LL mod)
{
    //求[1,1]B^(n-2),即[fn,fn-1]
    M* A = new M();
    A->data[0][0] = 1;
    A->data[0][1] = 1;
    M* B = new M();
    B->data[0][0] = 1;
    B->data[0][1] = 1;
    B->data[1][0] = 1;
    M* ans = mul(A, mPow(B, i - 2,mod),mod);
    return ans->data[0][0];
}

void solve2()
{
    if (m >= n + 2)
        cout << fib(n + 2,mod) - 1 << endl;
    else
        cout << fib(n + 2,fib(m)) % mod - 1 << endl;
}

int main()
{
    cin >> n >> m >> mod;
    solve2();
    return 0;
}
```
再次优化：
```cpp
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long LL;
LL n, m, mod;
//矩阵定义
class M {
public:
    LL data[2][2];
    M() { memset(data, 0, sizeof(data)); }
};
//快速乘法
LL mm(LL a, LL b, LL mod) {
    if (a > b) 
    {
        LL t = a;
        a = b;
        b = t;
    }
    LL x = 0;
    while (b != 0) 
    {
        if ((b & 1) == 1) 
        {
            x = (x + a) % mod;
        }
        a = (a * 2) % mod;
        b >>= 1;
    }
    return x;
}

//矩阵相乘
M* mul(M* m1, M* m2) 
{
    M* ans = new M();
    ans->data[0][0] = m1->data[0][0] * m2->data[0][0] + m1->data[0][1] * m2->data[1][0];
    ans->data[0][1] = m1->data[0][0] * m2->data[0][1] + m1->data[0][1] * m2->data[1][1];
    ans->data[1][0] = m1->data[1][0] * m2->data[0][0] + m1->data[1][1] * m2->data[1][0];
    ans->data[1][1] = m1->data[1][0] * m2->data[0][1] + m1->data[1][1] * m2->data[1][1];
    return ans;
}

M* mul(M* m1, M* m2, LL mod) 
{
    M* ans = new M();
    ans->data[0][0] = (mm(m1->data[0][0], m2->data[0][0], mod) + mm(m1->data[0][1], m2->data[1][0], mod)) % mod;
    ans->data[0][1] = (mm(m1->data[0][0], m2->data[0][1], mod) + mm(m1->data[0][1], m2->data[1][1], mod)) % mod;
    ans->data[1][0] = (mm(m1->data[1][0], m2->data[0][0], mod) + mm(m1->data[1][1], m2->data[1][0], mod)) % mod;
    ans->data[1][1] = (mm(m1->data[1][0], m2->data[0][1], mod) + mm(m1->data[1][1], m2->data[1][1], mod)) % mod;
    return ans;
}

//m的n次幂，快速幂算法
M* mPow(M* m, LL n) {
    M* E = new M();//单位矩阵
    E->data[0][0] = 1;
    E->data[1][1] = 1;

while (n != 0)
    {
        if (n & 1 == 1)
        {
            E = mul(E, m);
        }
        m = mul(m, m);//按平方倍增
        n >>= 1;
    }
    return E;
}

M* mPow(M* m, LL n, LL mod)
{
    M* E = new M();//单位矩阵
    E->data[0][0] = 1;
    E->data[1][1] = 1;

while (n != 0)
    {
        if ((n & 1) == 1)
        {
            E = mul(E, m, mod);
        }
        m = mul(m, m, mod);//按平方倍增
        n >>= 1;
    }
    return E;
}

//求斐波那契，由[f2,f1][1 1]^(n-2)=[fn,fn-1]，f(n)即为所求矩阵二维数组的第一位
//                     [1 0]
LL fib(LL i)
{
    //求[1,1]B^(n-2),即[fn,fn-1]
    M* A = new M();
    A->data[0][0] = 1;
    A->data[0][1] = 1;
    M* B = new M();
    B->data[0][0] = 1;
    B->data[0][1] = 1;
    B->data[1][0] = 1;
    M* ans = mul(A, mPow(B, i - 2));
    return ans->data[0][0];
}

LL fib(LL i, LL mod)
{
    //求[1,1]B^(n-2),即[fn,fn-1]
    M* A = new M();
    A->data[0][0] = 1;
    A->data[0][1] = 1;
    M* B = new M();
    B->data[0][0] = 1;
    B->data[0][1] = 1;
    B->data[1][0] = 1;
    M* ans = mul(A, mPow(B, i - 2, mod), mod);
    return ans->data[0][0];
}

void solve2()
{
    if (m >= n + 2)
        cout << fib(n + 2, mod) - 1 << endl;
    else
    {
        LL fibm = fib(m);
        cout << fib(n + 2, fibm) % mod - 1 << endl;
    }
}

int main()
{
    cin >> n >> m >> mod;
    solve2();
    return 0;
}
```

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

一个人的巴黎

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

简单的a+b （C语言代码）

开心的金明（C++代码）

C语言训练-求PI* （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

斐波那契(快速矩阵幂运算)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

数列排序（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

简单的a+b （C++语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

幸运数（C++代码）

1126题解

数组与指针的问题

一个人的巴黎

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

简单的a+b （C语言代码）

开心的金明 （C++代码）

C语言训练-求PI* （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

斐波那契(快速矩阵幂运算)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

数列排序 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

简单的a+b （C++语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

幸运数 （C++代码）

1126题解

数组与指针的问题

开心的金明（C++代码）

　　评论区

数列排序（C语言代码）

幸运数（C++代码）