正文

矩阵快速幂(代码片段)

doggod  doggod  2023-01-05  665

关键词：

　　矩阵快速幂的用途主要是用来递推公式。主要过程是构造一个系数矩阵A和一个值的矩阵B，令(A^k)×B的值与第k项正好相等或是相关。

模板的话差不多都是一样的，只不过是把对数的快速幂拓展到了对矩阵的快速幂。这个模板里面用的是静态的矩阵，速度稍微会快一点。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <math.h>
#define pi acos(-1.0 )
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;       // 不能加负号！！！
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;//4e18 ~= 2^62
const int maxn =100000 + 10;
const LL mod = 2147493647;

vector<LL> V;

typedef struct MATRIX

    LL mat[10][10];
MATRIX;

MATRIX A, B;

inline MATRIX mul(MATRIX a,MATRIX b,int n)

    MATRIX c;
    memset(c.mat,0,sizeof(c.mat));
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            if(a.mat[i][k])
                for(int j=0;j<n;j++)
                    if(b.mat[k][j])
                    
                        c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]%mod;
                        c.mat[i][j]%=mod;
                    
    return c;

inline MATRIX pow(MATRIX a,int N,int n)

    MATRIX E;
    memset(E.mat,0,sizeof(E.mat));
    for(int i=0;i<n;i++) E.mat[i][i]=1;
    while(N>0)
    
        if(N & 1)
            E=mul(E,a,n);
        N>>=1;
        a=mul(a,a,n);
    
    return E;


void inn(int index , string s)

    for(int i=0;i<s.length();i++)
        A.mat[index][i] = s[i]-‘0‘;
    


int main()

    int T; scanf("%d", &T);
    while(T--)
        memset(A.mat, 0, sizeof(A.mat));
        memset(B.mat, 0, sizeof(B.mat));
        LL n, a, b;
        scanf("%lld%lld%lld", &n, &a, &b);
        string s;
        inn(0,"1210000");
        inn(1,"1000000");
        inn(2,"0014641");
        inn(3,"0001331");
        inn(4,"0000121");
        inn(5,"0000011");
        inn(6,"0000001");

        B.mat[0][0] = b;
        B.mat[1][0] = a;
        B.mat[2][0] = 81;
        B.mat[3][0] = 27;
        B.mat[4][0] = 9 ;
        B.mat[5][0] = 3 ;
        B.mat[6][0] = 1 ;

        if(n<=2)
            if(n==1) printf("%lld
",a);
            else printf("%lld
", b);
        
        else 
            A = pow(A, n-2, 7);
            B = mul(A, B, 7);
            printf("%lld
", B.mat[0][0]);

View Code

题目的链接：Recursive sequence

主要的用法和技巧：

技术分享图片

矩阵快速幂(代码片段)

线性递推可用矩阵快速幂(O(lognk^3))解。构造系数矩阵的方法是先列出转移式，然后看哪些项是要的填为1，否则填0。如对[f_i,0=f_i-1,1][f_i,1=f_i-1,0]则构造矩阵矩阵快速幂代码如下：constintD[6][6]=1,1,1,1,1,0,1,0,0,1,0,0,1,0,0,0,0,1,1,1,0,0,0,0,1,0... 查看详情

矩阵快速幂(代码片段)

　　矩阵快速幂的用途主要是用来递推公式。主要过程是构造一个系数矩阵A和一个值的矩阵B，令(A^k)×B的值与第k项正好相等或是相关。模板的话差不多都是一样的，只不过是把对数的快速幂拓展到了对矩阵的快速幂。这个模板... 查看详情

矩阵快速幂(代码片段)

将线性递推式转化成矩阵乘法，再结合快速幂实现O(logn)此法可广泛用于动态规划等递推题目实现时仅需将*重载，其余同快速幂#include<iostream>#include<cstdio>usingnamespacestd;#definelllonglongconstllp=1e9+7;lln,k;structZlla[105][105];Zoperator*... 查看详情

矩阵快速幂(代码片段)

1/*2题意：求a(n)=a(n-1)+a(n-2)+a(n-3)+......a(n-k)+...k<20n<10^183题解：矩阵快速幂，把递推公式写成矩阵的形式，就可以利用快速幂计算4时间：2018.07.315*/67#include<bits/stdc++.h>8usingnamespacestd;910typedeflonglongLL;11constintMA 查看详情

矩阵快速幂(代码片段)

传送门 emm没错这就是矩阵快速幂的裸体板子题所以没什么可说的哇qwq 矩阵乘+快速幂（+预处理） 1#include<cstdio>2#include<cstring>3#definelllonglong4usingnamespacestd;5constllmod=1e9+7;6lln,k;7structmat89llm[105][105] 查看详情

求幂大法，矩阵快速幂，快速幂模板题--hdu4549(代码片段)

hdu-4549求幂大法、矩阵快速幂、快速幂题目M斐波那契数列TimeLimit:3000/1000MS(Java/Others)MemoryLimit:65535/32768K(Java/Others)TotalSubmission(s):6217AcceptedSubmission(s):1902ProblemDescriptionM斐波那契数列F[n]是一种整数数列，它的定义如下：F[0]= 查看详情

关于快速幂快速乘矩阵快速幂(代码片段)

一、快速幂快速幂是用于解决类似$a^b$$mod$$p$值类型的问题的。使用普通的方法是从$1$循环至$b$，再逐次累乘，逐次取模。但这种方法对于$b$很大的时候却可能会超时。那么，这时候我们就需要使用快速幂了。快速幂是基于以下... 查看详情

模板矩阵快速幂(代码片段)

题目背景矩阵快速幂题目描述给定n*n的矩阵A，求A^k输入输出格式输入格式：第一行，n,k第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素输出格式：输出A^k共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元... 查看详情

矩阵快速幂模板(代码片段)

在矩阵快速幂中要注意可以把两个矩阵化为同大小的时候运算 #include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;constintMAX_N=62;intn;structJuZhenintm[MAX_N][MAX_N];a,b;JuZhenMul(JuZhenx,JuZ 查看详情

整数快速幂（取模）矩阵快速幂及其应用(代码片段)

摘要：　　本文主要介绍了整数快速幂、矩阵快速幂及其应用，以题为例重点展示了使用细节。　　我们要计算一个整数x的n次方，即x^n，普通的方法是连乘，这里介绍一种效率非常高的计算幂运算的算法——反复平方法。... 查看详情

hduqueuing(递推+矩阵快速幂)(代码片段)

题面ProblemDescriptionQueuesandPriorityQueuesaredatastructureswhichareknowntomostcomputerscientists.TheQueueoccursofteninourdailylife.Therearemanypeoplelinedupatthelunchtime.Nowwedefinethat‘f’isshortfor 查看详情

[模板]矩阵快速幂(代码片段)

矩阵快速幂是一个快速幂的延伸,但实际上区别不大,主要思想是一样的.题干:题目背景矩阵快速幂题目描述给定n*n的矩阵A，求A^k输入输出格式输入格式：第一行，n,k第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元... 查看详情

jzzhuandsequences(矩阵快速幂+取模)(代码片段)

题目链接Jzzhuhasinventedakindofsequences,theymeetthefollowingproperty:　　　　　　　　　　　　Youaregivenxandy,pleasecalculatefnmodulo1000000007(109?+?7).InputThefirstlinecontainstwointegersxandy(|x|,?|y|?≤?109).Thes 查看详情

矩阵快速幂笔记(代码片段)

快速幂求斐波那契数列1//答案对100000007取模2#include<iostream>3#include<cstring>4#include<cstdio>5#include<cmath>6#defineMOD1000000077usingnamespacestd;8typedeflonglongll;9structsq10llsq[2][2 查看详情

矩阵快速幂(代码片段)

一、前期铺垫　在讲矩阵快速幂之前，我们先来看一下整数快速幂。求X的N次方。　举个例子，在求x^19时，我们可以拆分成x^16、x^2和x的乘积。我们观察19的二进制数（10011），发现二进制第i位上的值为1，在乘积中就要有x的2^i的... 查看详情

矩阵快速幂(代码片段)

#include<bits/stdc++.h>usingnamespacestd;#defineMax3#definemod10000intm;//m阶矩阵structMatrixintm[Max][Max];;MatrixMul(Matrixa,Matrixb)Matrixc;memset(c.m,0,sizeof(c.m));for(inti=0;i<m;i++)fo 查看详情

矩阵快速幂模板(代码片段)

前置知识矩阵矩阵是一个n×mn\\timesmn×m的阵列，下面是一个3×33\\times33×3的矩阵：[100010001]\\beginbmatrix1&0&0\\\\\\\\0&1&0\\\\\\\\0&0&1\\\\\\endbmatrix⎣⎢⎢⎢⎢⎡100010001⎦⎥⎥⎥⎥⎤矩阵乘法若矩查看详情

acm入门之矩阵快速幂(代码片段)

矩阵快速幂其实是一个用于加速计算的一个算法。矩阵快速幂和我们普通的数的快速幂是没有啥太大的区别的。不过一个是数，一个是矩阵。矩阵快速幂的应用：矩阵加速递推。例如:如果有一道题目让你求斐波那契数列... 查看详情