数论5——矩阵快速幂（模板）

布满荆棘的人生 2024-04-17 20:11 82阅读 0赞

#include<bits/stdc++.h>
    #define ll long long
    
    using namespace std;
    const ll N=10;
    const ll Mod = 1e9+7;
    ll tmp[N][N];
    
    void mul(ll a[][N],ll b[][N],ll n,ll Mod)
    { 
    
        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]=(tmp[i][j]%Mod+(a[i][k]%Mod*b[k][j]%Mod)%Mod)%Mod;
    
        for(ll i=0; i<n; i++)
    
            for(ll j=0; j<n; j++)
    
                a[i][j]=tmp[i][j];
    
    }
    ll res[N][N];
    void Pow(ll a[][N],ll n, ll Mod)
    { 
    
        memset(res,0,sizeof res);//n是幂，N是矩阵大小
        for(ll i=0; i<N; i++) res[i][i]=1;
    
        while(n)
        { 
    
            if(n%2)
            { 
                mul(res,a,N, Mod);//res=res*a;复制直接在multi里面实现了；
            }
            mul(a,a,N, Mod);//a=a*a
            n/=2;
    
        }
    
    }
    
    int main()
    { 
    
    }

矩阵快速幂：  
可以求斐波那契：[链接][Link 1]  
以及优化一些线性地推

[Link 1]: https://blog.csdn.net/qq_41661809/article/details/88648548

发表评论取消回复

表情：

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

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

相关阅读

相关数论5——矩阵快速幂（模板）

include<bits/stdc++.h> define ll long long using namespace std; c...

布满荆棘的人生/ 2024年04月17日 20:11/ 0 赞/ 83 阅读

相关快速幂-数论

2^3=8==>连续乘了3次2； 2^13==>13个2相乘； 2^16 = 2^ 8 \ 2^8; 对于上式，我们可以先运算8次得到28，然后两个28相乘得到216

╰+哭是因爲堅強的太久メ/ 2023年07月08日 02:58/ 0 赞/ 43 阅读

相关【数论】快速幂、矩阵快速幂取模专题训练

前言 HDU-1061 Rightmost Digit（快速幂取模） HDU-2817 A sequence of numbers（快速幂取模）

你的名字/ 2023年07月01日 07:30/ 0 赞/ 32 阅读

相关数论-快速幂、矩阵快速幂、慢速乘

文章目录快速幂矩阵快速幂慢速乘例题 HDU-2817 HDU-3117 XUJC-1395 快

朱雀/ 2023年03月05日 09:41/ 0 赞/ 20 阅读

相关快速幂（数论）

对于xy的快速幂 include<iostream> using namespace std; const int mod=1000; //对10

缺乏、安全感/ 2022年11月29日 11:49/ 0 赞/ 118 阅读

相关矩阵快速幂模板

int mod; const int NUM;//定义矩阵能表示的最大维数 int N;//N表示矩阵的维数，以下的矩阵加法、乘法、快速幂都是按N维矩阵

曾经终败给现在/ 2022年07月03日 15:26/ 0 赞/ 222 阅读

相关矩阵快速幂基础模板

Think: 1注意记录数组初始化 2思想->大数取模 include <bits/stdc++.h> using namespace st

绝地灬酷狼/ 2022年06月16日 00:54/ 0 赞/ 246 阅读

相关矩阵运算，矩阵快速幂，模板

include<cstdio> include<algorithm> include<cstring> include<iostream>

以你之姓@/ 2022年06月11日 05:41/ 0 赞/ 236 阅读

相关快速幂，矩阵快速幂（模板）

1，整数快速幂： C++ Code <table style="width:100%;font-family:Consolas, 'Courier New';font-

左手的ㄟ右手/ 2022年06月11日 03:57/ 0 赞/ 313 阅读

相关矩阵快速幂模板

const int maxn = 2; struct Matrix{ ll a[maxn][maxn]; void

小鱼儿/ 2021年09月19日 05:44/ 0 赞/ 401 阅读