SinzoL

用户名：SinzoL

访问量：2328

签　名：

编程菜鸟，感谢指导

等　　级
排　　名	570
经　　验	4311
参赛次数	12
文章发表	17
年　　龄	19
在职情况	学生
学　　校	哈尔滨工业大学（深圳）
专　　业	cs

　　自我简介：

很懒，很烂，很难

TA的其他文章

SInzoL--题解 1264: 防御导弹
浏览：123

SinzoL--题解 1676: 数据结构-链表的基本操作
浏览：56

SinzoL--题解 1678: 数据结构-双向循环链表
浏览：115

你可能喜欢

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

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

SinzoL--题解 2538: 信息学奥赛一本通T1642-Fibonacci 第 n 项

　　作者: SinzoL　　　　发表时间：2022-07-04 14:40:01 浏览：743　|　评论：0　

原题链接：信息学奥赛一本通T1642-Fibonacci 第 n 项

####想要看矩阵和快速幂代码的小伙伴们看过来
####矩阵用于将Fibonacci数列的递推过程转化为乘法，而根据矩阵的乘法结合律，又可以使用快速幂使时间复杂度降为logn
####以下是代码呈现：
```cpp
#include<bits/stdc++.h>
using namespace std;

long long ans[36][5][5];//用于逐步储存答案，但只输出最后一个
long long mj[36][5][5];//用于储存对应2^k的数值
int n,m,len;

void prepare();
void getans(int a);

int main()
{
    cin>>n>>m;
    n-=2;//在为矩阵赋值时，已经有f1=1，f2=1了，故n-2
    ans[0][1][1]=ans[0][2][1]=mj[0][1][1]=mj[0][1][2]=mj[0][2][1]=1;
	//为矩阵赋初始值
    prepare();//迭代让mj[i][j][k]获值
    for(int i=0;n>0;i++)
    {
        if(n&1){
            len++;
            getans(i);//逐步获取ans
        }
        n=n>>1;
    }//快速幂
    cout<<ans[len][1][1]<<endl;
    return 0;
}
void prepare()
{
    //快速幂过程
    for(int i=1;i<=31;i++)
    {
        for(int j=1;j<=2;j++)
        {
            for(int k=1;k<=2;k++)
            {
                for(int l=1;l<=2;l++)
                {
                    mj[i][j][k]+=mj[i-1][j][l]*mj[i-1][l][k];
                }
                mj[i][j][k]%=m;//注意及时取余，防止溢出
            }
        }
    }
}
void getans(int a)
{
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            for(int k=1;k<=2;k++)
            {
                ans[len][i][j]+=mj[a][i][k]*ans[len-1][k][j];
            }
            ans[len][i][j]%=m;//注意及时取余，防止溢出
        }
    }
}
```
新手写题解，欢迎吐槽

0.0分

1 人评分

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

SinzoL

TA的其他文章

你可能喜欢

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

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

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

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

不容易系列2 （C语言代码）

SinzoL--题解 2538: 信息学奥赛一本通T1642-Fibonacci 第 n 项

评论区

精彩推荐

简洁的代码

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

矩形面积交（C语言代码）

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

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

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

printf基础练习2 （C语言代码）

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

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

数对（C语言代码）

SinzoL

TA的其他文章

你可能喜欢

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

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

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

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

不容易系列2 （C语言代码）

SinzoL--题解 2538: 信息学奥赛一本通T1642-Fibonacci 第 n 项

评论区

精彩推荐

简洁的代码

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

矩形面积交 （C语言代码）

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

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

剪刀石头布 （C语言代码）不知道怎么直接在scanf中用枚举变量

printf基础练习2 （C语言代码）

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

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

数对 （C语言代码）

　　评论区

矩形面积交（C语言代码）

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

数对（C语言代码）