Matrix快速幂模板

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

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

https://www.luogu.org/problem/show?pid=3390

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

const int maxN=;

const ll Mod=;

const ll inf=;

int n;

class Matrix

{

public:

    ll M[maxN][maxN];

    Matrix(int x)

    {

        for (int i=;i<n;i++)

            for (int j=;j<n;j++)

                M[i][j]=x;

    }

    Matrix(ll Arr[maxN][maxN])

    {

        for (int i=;i<n;i++)

            for (int j=;j<n;j++)

                M[i][j]=Arr[i][j];

    }

    void print()

    {

        for (int i=;i<n;i++)

        {

            for (int j=;j<n;j++)

                cout<<M[i][j]<<' ';

            cout<<endl;

        }

    }

};

Matrix operator * (Matrix A,Matrix B)

{

    Matrix Ans();

    for (int i=;i<n;i++)

        for (int j=;j<n;j++)

            for (int k=;k<n;k++)

                Ans.M[i][j]=(Ans.M[i][j]+A.M[i][k]*B.M[k][j]%Mod)%Mod;

    return Ans;

}

ll Arr[maxN][maxN];

ll read();

void Pow(ll Po);

int main()

{

    n=read();

    ll Po=read();

    for (int i=;i<n;i++)

        for (int j=;j<n;j++)

            Arr[i][j]=read();

    Pow(Po-);//注意，这里为什么要-1呢，因为我们知道a^1是a，对于矩阵来说就是A^1是A,所以在传进去的时候先-1（相当于已经进行了一次操作），而若Po==1，则在Pow(Po-1)中不会执行循环，此时也正好是矩阵A（仔细揣摩一下）

    return ;

}

ll read()

{

    ll x=;

    ll k=;

    char ch=getchar();

    while (((ch>'')||(ch<''))&&(ch!='-'))

        ch=getchar();

    if (ch=='-')

    {

        k=-;

        ch=getchar();

    }

    while ((ch>='')&&(ch<=''))

    {

        x=x*+ch-;

        ch=getchar();

    }

    return x*k;

}

void Pow(ll P)

{

    Matrix A(Arr);

    Matrix B(Arr);

    while (P!=)

    {

        if (P&)

            A=A*B;

        B=B*B;

        P=P>>;

    }

    A.print();

    return;

}

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

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long//注意用长整形，因为有可能会爆int

const int Mod=;

const int inf=;

class Matrix//定义矩阵

{

public:

    ll M[][];

    Matrix()

    {

        memset(M,,sizeof(M));

    }

    Matrix(int Arr[][])//定义两个方便的矩阵初始化

    {

        for (int i=;i<;i++)

            for (int j=;j<;j++)

                M[i][j]=Arr[i][j];

    }

};

Matrix operator * (Matrix A,Matrix B)//重载乘号操作

{

    Matrix Ans;

    for (int i=;i<;i++)

        for (int j=;j<;j++)

            for (int k=;k<;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<=)

    {

        cout<<<<endl;

        return ;

    }

    n=n-;

    int a[][]={{,},{,}};//初始矩阵

    int b[][]={{,},{,}};//即上文的T

    Matrix A(a);

    Matrix B(b);

    while (n!=)//快速幂

    {

        if (n&)

            A=A*B;

        B=B*B;

        n=n>>;

    }

    cout<<A.M[][]<<endl;

    return ;

}

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

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

const int inf=;

ll n,Mod,p,q,A1,A2;

class Matrix//定义矩阵结构体

{

public:

    ll M[][];

    Matrix()

    {

        memset(M,,sizeof(M));

    }

    Matrix(ll Arr[][])

    {

        for (int i=;i<;i++)

            for (int j=;j<;j++)

                M[i][j]=Arr[i][j];

    }

};

Matrix operator * (Matrix A,Matrix B)//重载乘法操作

{

    Matrix Ans;

    for (int i=;i<;i++)

        for (int j=;j<;j++)

            for (int k=;k<;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和2的情况特殊处理（虽然我也不知道是否有特殊点）

    {

        cout<<A1<<endl;

        return ;

    }

    if (n==)

    {

        cout<<A2<<endl;

        return ;

    }

    n=n-;

    ll a[][]={{A2,A1},{,}};//初始矩阵

    ll b[][]={{p,},{q,}};

    Matrix A(a);

    Matrix B(b);

    while (n!=)//快速幂

    {

        if (n&)

            A=A*B;

        B=B*B;

        n=n>>;

    }

    cout<<A.M[][]<<endl;

    return ;

}

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

观察细胞分裂的规律。

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

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

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

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

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define ll long long

ll n,X,Mod;

class Matrix//定义一个矩阵结构体

{

public:

    ll M[][];

    Matrix()//初始化0

    {

        for (int i=;i<;i++)

            for (int j=;j<;j++)

                M[i][j]=;

    }

    Matrix(ll Arr[][])//用数组来初始化

    {

        for (int i=;i<;i++)

            for (int j=;j<;j++)

                M[i][j]=Arr[i][j];

    }

};

Matrix operator * (Matrix A,Matrix B)//重载乘法运算符

{

    Matrix Ans;

    for (int i=;i<;i++)

        for (int j=;j<;j++)

            for (int k=;k<;k++)

                Ans.M[i][j]=(Ans.M[i][j]+A.M[i][k]*B.M[k][j]%Mod)%Mod;

    return Ans;

}

const int inf=;

ll Pow();

int main()//无比简单的主函数

{

    cin>>n>>X>>Mod;

    cout<<Pow()<<endl;

    return ;

}

ll Pow()//矩阵快速幂

{

    ll a[][]={{,,},{,,},{,,}};//初始状态

    ll b[][]={{X,,},{,,},{,,}};//用来使状态发生转移的矩阵，即文中提到的T

    Matrix A(a);

    Matrix B(b);

    while (n!=)

    {

        if (n&)

        {

            A=A*B;//注意这里的乘法顺序，矩阵乘法不满足交换律

        }

        B=B*B;

        n=n>>;

    }

    return A.M[][];//根据我们的定义，最后的值就在A.M[0][0]

}

巴特西

Matrix快速幂模板

最新文章

热门文章

巴特西

Matrix快速幂 模板

最新文章

热门文章

Matrix快速幂模板