记录编号	483260	评测结果	AWWWWWWWWW
题目名称	[HZOI 2016][POJ3233]矩阵幂之和	最终得分	10
用户昵称	pztl	是否通过	未通过
代码语言	C++	运行时间	0.497 s
提交时间	2018-01-15 21:31:47	内存使用	0.29 MiB

#include<cstdio>
#include<cstring>
struct no{
    int p[65][65];
};
int mod,len;
struct no xb(struct no a,struct no b)
{
    int i,j,k;
    struct no c;
    for(i=1;i<=len;i++)
    {
        for(j=1;j<=len;j++)
        {
            c.p[i][j]=0;
            for(k=1;k<=len;k++)
                c.p[i][j]=(a.p[i][k]*b.p[k][j]+c.p[i][j])%mod;
        }
    }
    return c;
}
struct no xb1(struct no a,struct no b,int n)
{
    while(n)
    {
        if(n%2==1)
            b=xb(b,a);
        n=n/2;
        a=xb(a,a);
    }
    return b;
}
int main()
{
	freopen("matrix_sum.in","r",stdin);
	freopen("matrix_sum.out","w",stdout);
    int i,j,n,k;
    struct no a,b;
    while(scanf("%d%d%d",&n,&k,&mod)!=EOF)
    {
        len=n*2;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                scanf("%d",&a.p[i][j]);
        for(i=1;i<=n;i++)
            for(j=n+1;j<=n*2;j++)
                if(i+n==j)
                    a.p[i][j]=1;
                else
                    a.p[i][j]=0;
        for(i=n+1;i<=n*2;i++)
            for(j=1;j<=n;j++)
                a.p[i][j]=0;
        for(i=n+1;i<=2*n;i++)
            for(j=n+1;j<=n*2;j++)
                if(i==j)
                    a.p[i][j]=1;
                else
                    a.p[i][j]=0;
        for(i=1;i<=n*2;i++)
            for(j=1;j<=n*2;j++)
                if(i==j)
                    b.p[i][j]=1;
                else
                    b.p[i][j]=0;
        a=xb1(a,b,k+1);
        for(i=1;i<=n;i++)
            for(j=n+1;j<=len;j++)
            {
                if(i+n==j)
                    a.p[i][j]--;
                while(a.p[i][j]<0)
                    a.p[i][j]+=mod;
            }
        for(i=1;i<=n;i++)
        {
            for(j=n+1;j<len;j++)
                printf("%d ",a.p[i][j]);
            printf("%d\n",a.p[i][len]);
        }
    }
    return 0;
}