UVA - 11149 (矩阵快速幂+倍增法)

第一道矩阵快速幂的题；模板题；

#include<stack>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define INF 0x3f3f3f3f

typedef long long ll;

const ll maxn = ;

int n;

int  m;

ll euler[maxn];

ll fun_[maxn];

struct node

{

    int a[][];

    node()

    {

        memset(a,,sizeof(a));

    }

    node operator *(const node& m2) const

    {

        node m1;

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

        {

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

            {

                m1.a[i][j]=;

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

                {

                    m1.a[i][j]+=a[i][k]*m2.a[k][j];

                    m1.a[i][j]%=;

                }

            }

        }

        return m1;

    }

    node operator +(const node& m2) const

    {

        node m1;

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

        {

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

            {

                m1.a[i][j]=a[i][j]+m2.a[i][j];

                m1.a[i][j]%=;

            }

        }

        return m1;

    }

} A,E;

void init()

{

    memset(E.a,,sizeof(E.a));

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

    {

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

//        {

//            if (i==j)

            E.a[i][i]=;

//        }

    }

}

node quick_mod_(node c,int k)

{

    node e=E;

    while (k)

    {

        if(k&) e=e*c;

        c = c*c;

        k>>=;

    }

    return e;

}

node find_(int k)

{

    if (k==)

    {

        return A;

    }

    if(k%==)

    {

        k/=;

        node nod=quick_mod_(A,k)+E;

        nod=nod*find_(k);

        return nod;

    }

    else

    {

        node t=quick_mod_(A,k);

        k--;

        k/=;

        node nod=quick_mod_(A,k)+E;

        nod=nod*find_(k);

        //cout<<nod.a[0][3]<<endl;

        nod = nod +t;

        return nod;

    }

}

void print_(node p)

{

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

    {

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

        {

            if (!j)

            cout<<p.a[i][j];

            else

                cout<<" "<<p.a[i][j];

        }cout<<endl;

    }

}

int main()

{

    int kase=;

    while (cin>>n>>m&&(m+n))

    {

        init();

        if (kase) cout<<endl;

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

        {

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

            {

                cin>>A.a[i][j];

                A.a[i][j]%=;

            }

        }

        node q=find_(m);

//        cout<<endl;

//        cout<<q.a[0][0]<<" "<<q.a[0][1]<<" "<<q.a[0][2]<<endl<<endl;

        print_(q);

        kase++;

    }

    return ;

}

/*

3 2

0 2 0

0 0 2

0 0 0

*/

倍增法的 解释：