【模板】【矩阵快速幂】求第n项斐波那契

深藏阁楼爱情的钟 2023-06-01 08:46 9阅读 0赞

注意a数组初始化，调用Pow（a，n，w），n是第几项，求斐波那契中w默认为2

ll tmp[2][2],res[2][2];
    void multi(ll a[][2],ll b[][2],int n)
    {
        memset(tmp,0,sizeof(tmp));
        for(ll i=0;i<n;i++)
        {
           for(ll j=0;j<n;j++)
           {
            for(ll k=0;k<n;k++)
            {
            tmp[i][j]+=(a[i][k]*b[k][j])%p;
            }
            tmp[i][j]=tmp[i][j]%p;
          }
       }
        for(ll i=0;i<n;i++)
            for(ll j=0;j<n;j++)
            a[i][j]=tmp[i][j];
    }
    void Pow(ll a[][2],ll m,int n)
    {
        memset(res,0,sizeof(res));//m是幂，n是矩阵大小
        for(ll i=0;i<n;i++) res[i][i]=1;
        while(m)
        {
            if(m&1)
            multi(res,a,n);//res=res*a;复制直接在multi里面实现了；
            multi(a,a,n);//a=a*a
            m>>=1;
        }
    }
    ll qm(ll a,ll b)
    {
        ll ret=1;
        while(b)
        {
            if(b&1)
            {
                ret=ret*a%p;
            }
            a=a*a%p;
            b>>=1;
        }
        return ret;
    }
    //Pow(a,n,2) 调用  初始化:a[0][0]=a[0][1]=a[1][0]=1,a[1][1]=0

转载于:https://www.cnblogs.com/Diliiiii/p/11272674.html

发表评论取消回复

表情：

评论列表（有 0 条评论，9人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python之求斐波那契数列前n项

文章目录 * 2021-1-26更新 * 前言 * 解法 * * 1、暴力递归 * 2、优化1：备忘录递归解法 * 3、优...

Dear 丶/ 2024年04月18日 12:59/ 0 赞/ 81 阅读

相关求斐波那契数列的第n项

![watermark,type\_d3F5LXplbmhlaQ,shadow\_50,text\_Q1NETiBA6LaFMzM4,size\_20,color\_FFFFF

Love The Way You Lie/ 2023年09月30日 10:43/ 0 赞/ 13 阅读

相关【斐波那契】【矩阵快速幂模板】斐波那契公约数

这道题求第n项和第m项斐波那契的公约数这里有一个定理（n，m都是1e9） gcd(f\[m\],f\[n\])=f\[gcd(n,m)\] 斐波那契使用矩阵快速幂求

绝地灬酷狼/ 2023年06月01日 08:46/ 0 赞/ 10 阅读

相关【模板】【矩阵快速幂】求第n项斐波那契

注意a数组初始化，调用Pow（a，n，w），n是第几项，求斐波那契中w默认为2 ll tmp[2][2],res[2][2]; void multi(ll a

深藏阁楼爱情的钟/ 2023年06月01日 08:46/ 0 赞/ 10 阅读

相关 13：求斐波那契数列的第n项

求斐波那契数列的第n项 public class Offer13 { / 递归方式：n过大，会发生栈溢出 /

谁践踏了优雅/ 2023年02月23日 15:23/ 0 赞/ 40 阅读

相关斐波那契数列的第N项（1≤n≤10^18 矩阵快速幂）

[1242 斐波那契数列的第N项][1242 _N] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [难度：基础题][Link 1] 斐波那契数列的定义如

深碍√TFBOYSˉ_/ 2022年09月24日 13:26/ 0 赞/ 175 阅读

相关求斐波那契数列

文章目录一、求斐波那契数列 1.题目描述 2.题目链接 3.解题思路一、求斐波那契数列

落日映苍穹つ/ 2022年08月30日 04:18/ 0 赞/ 233 阅读

相关算法——矩阵快速幂求第N个斐波那契数

Fibonacci <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</t

「爱情、让人受尽委屈。」/ 2022年06月07日 04:35/ 0 赞/ 182 阅读

相关 51Nod 1242 斐波那契数列的第N项——————矩阵快速幂

1242 斐波那契数列的第N项基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题收藏关注斐波那契数列的定义如下： F ( 0 )

野性酷女/ 2022年05月09日 10:18/ 0 赞/ 184 阅读

相关【Java】输出n项斐波那契数列

import java.util.Scanner; public class 递归 { //求第n个斐波那契数

Dear 丶/ 2022年02月16日 05:41/ 0 赞/ 231 阅读