学步园

第一次接触矩阵这东西，不怎么会；
矩阵乘法：自学百度；快速幂：自学百度；
k为偶数时：A^1+A^2+..+A^k==(A^1+..+A^(k/2))*A^(k/2)+(A^1+...+A^(k/2));
k为奇数时：A^1+A^2+..+A^k==(A^1+..+A^(k/2))*A^(k/2+1)+(A^1+...+A^(k/2))+A^(k/2+1);

代码如下

#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n,k,M;
struct node{
    int kk[31][31];
}unit,a;
void init()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            unit.kk[i][j]=(i==j);
}
node mul(node aa,node bb)
{
    node cc;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cc.kk[i][j]=0;
            for(int p=1;p<=n;p++)
                cc.kk[i][j]=(cc.kk[i][j] + (aa.kk[i][p]*bb.kk[p][j])%M)%M;
        }
    return cc;
}
node pow(node aa,int exp)
{
    node p=aa;
    node q=unit;
    while(exp!=1)
    {
        if(exp&1)
        {exp--;q=mul(q,p);}
        else {
            exp/=2;
            p=mul(p,p);
        }
    }
    q = mul(q,p);
    return q;
}
node _pow(node aa,int exp)
{
    node p=aa;
    node q=unit;
    while(exp)
    {
        if(exp&1)
            q=mul(q,p);


        exp/=2;
        p=mul(p,p);


    }
    return q;
}
node add(node aa,node bb)
{
    node cc;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cc.kk[i][j]=0;
            cc.kk[i][j]=(aa.kk[i][j]+bb.kk[i][j])%M;
        }
    return cc;
}
node sum(node aa,int t)//计算aa^1+aa^2+.....+aa^t;
{
    if(t==1)
        return aa;
    else
    {
        node m=sum(aa,t/2);
        if(t&1)
        {
            node temp=pow(aa,t/2+1);
            return add(add(m,temp),mul(temp,m));
        }else
        {
            node temp=pow(aa,t/2);
            return add(mul(temp,m),m);
        }
    }
}
void print(node aa)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<n;j++)
            printf("%d ",aa.kk[i][j]);
        printf("%d\n",aa.kk[i][n]);
    }
}
int main()
{
    scanf("%d%d%d",&n,&k,&M);
    init();//一定要放在n的后面啊啊啊啊啊 啊 啊！！！！
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a.kk[i][j]);
    print(sum(a,k));
    return 0;
}