Matrix快速幂模板-白红宇

Matrix快速幂模板

阅读量：5291 次

发布时间：2019-06-14

本文共 3488 字，大约阅读时间需要 11 分钟。

讲解：http://www.cnblogs.com/SYCstudio/p/7211050.html

给定n*n的矩阵A，求A^k

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long longconst int maxN=201;const ll Mod=1000000007;const ll inf=2147483647;int n;class Matrix{public:    ll M[maxN][maxN];    Matrix(int x)    {        for (int i=0;i
           
            '9')||(ch<'0'))&&(ch!='-')) ch=getchar(); if (ch=='-') { k=-1; ch=getchar(); } while ((ch>='0')&&(ch<='9')) { x=x*10+ch-48; ch=getchar(); } return x*k;}void Pow(ll P){ Matrix A(Arr); Matrix B(Arr); while (P!=0) { if (P&1) A=A*B; B=B*B; P=P>>1; } A.print(); return;}

View Code

例题求斐波那契数列的第N项%MOD

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long//注意用长整形，因为有可能会爆intconst int Mod=1000000007;const int inf=2147483647;class Matrix//定义矩阵{public:    ll M[2][2];    Matrix()    {        memset(M,0,sizeof(M));    }    Matrix(int Arr[2][2])//定义两个方便的矩阵初始化    {        for (int i=0;i<2;i++)            for (int j=0;j<2;j++)                M[i][j]=Arr[i][j];    }};Matrix operator * (Matrix A,Matrix B)//重载乘号操作{    Matrix Ans;    for (int i=0;i<2;i++)        for (int j=0;j<2;j++)            for (int k=0;k<2;k++)                Ans.M[i][j]=(Ans.M[i][j]+A.M[i][k]*B.M[k][j]%Mod)%Mod;    return Ans;}ll n;int main(){    cin>>n;    if (n<=2)    {        cout<<1<
           
            >1; } cout<
            
             <

View Code

例题求广义斐波那契数列的第N项%MOD

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long longconst int inf=2147483647;ll n,Mod,p,q,A1,A2;class Matrix//定义矩阵结构体{public:    ll M[2][2];    Matrix()    {        memset(M,0,sizeof(M));    }    Matrix(ll Arr[2][2])    {        for (int i=0;i<2;i++)            for (int j=0;j<2;j++)                M[i][j]=Arr[i][j];    }};Matrix operator * (Matrix A,Matrix B)//重载乘法操作{    Matrix Ans;    for (int i=0;i<2;i++)        for (int j=0;j<2;j++)            for (int k=0;k<2;k++)                Ans.M[i][j]=(Ans.M[i][j]+A.M[i][k]*B.M[k][j]%Mod)%Mod;    return Ans;}int main(){    cin>>p>>q>>A1>>A2>>n>>Mod;    if (n==1)//1和2的情况特殊处理（虽然我也不知道是否有特殊点）    {        cout<
           
            <
            
             >1; } cout<
             
              <

View Code

小 X 在上完生物课后对细胞的分裂产生了浓厚的兴趣。于是他决定做实验并

观察细胞分裂的规律。

他选取了一种特别的细胞，每天每个该细胞可以分裂出 x − 1 个新的细胞。

小 X 决定第 i 天向培养皿中加入 i 个细胞（在实验开始前培养皿中无细胞）。

现在他想知道第 n 天培养皿中总共会有多少个细胞。

由于细胞总数可能很多，你只要告诉他总数对 w 取模的值即可。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long longll n,X,Mod;class Matrix//定义一个矩阵结构体{public: ll M[3][3]; Matrix()//初始化0 { for (int i=0;i<3;i++) for (int j=0;j<3;j++) M[i][j]=0; } Matrix(ll Arr[3][3])//用数组来初始化 { for (int i=0;i<3;i++) for (int j=0;j<3;j++) M[i][j]=Arr[i][j]; }};Matrix operator * (Matrix A,Matrix B)//重载乘法运算符{ Matrix Ans; for (int i=0;i<3;i++) for (int j=0;j<3;j++) for (int k=0;k<3;k++) Ans.M[i][j]=(Ans.M[i][j]+A.M[i][k]*B.M[k][j]%Mod)%Mod; return Ans;}const int inf=2147483647;ll Pow();int main()//无比简单的主函数{ cin>>n>>X>>Mod; cout<
            
             <
             
              >1; } return A.M[0][0];//根据我们的定义，最后的值就在A.M[0][0]}