#include <cstdio>
#include <cstring>
using namespace std;

template<typename T>
inline T read()
{
	T x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
	return x*f;
}

const int MAXN=35;
int n,k,mod;

struct matrix1
{
	int n,m;
	long long a[MAXN][MAXN];
	
	inline matrix1(){n=m=0;memset(a,0,sizeof(a));}
	
	inline void init(int n,int w)
	{
		this->n=n;this->m=n;
		for (int i=1;i<=n;i++) a[i][i]=w;
	}
	
	inline void print()
	{
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=m;j++) printf("%d ",a[i][j]);
			printf("\n");
		}
	}
	
	inline struct matrix1 operator + (struct matrix1 tmp)
	{
		struct matrix1 ans;ans.n=tmp.n;ans.m=tmp.m;
		for (int i=1;i<=ans.n;i++)
			for (int j=1;j<=ans.m;j++)
				ans.a[i][j]=(a[i][j]+tmp.a[i][j])%mod;
		return ans;
	}
	
	inline struct matrix1 operator * (struct matrix1 tmp)
	{
		struct matrix1 ans;
		ans.n=n;ans.m=tmp.m;
		for (int i=1;i<=ans.n;i++)
			for (int j=1;j<=ans.m;j++)
				for (int k=1;k<=tmp.n;k++)
					ans.a[i][j]=(ans.a[i][j]+a[i][k]*tmp.a[k][j]%mod)%mod;
		return ans;
	}
}A;

struct matrix2
{
	int n,m;
	struct matrix1 a[3][3];
	
	inline matrix2(){n=m=0;}
	
	inline struct matrix2 operator * (struct matrix2 tmp)
	{
		struct matrix2 ans;
		ans.n=n;ans.m=tmp.m;
		for (int i=1;i<=ans.n;i++)
			for (int j=1;j<=ans.m;j++)
				for (int k=1;k<=tmp.n;k++)
					ans.a[i][j]=ans.a[i][j]+a[i][k]*tmp.a[k][j];
		return ans;
	}
}tmp,f;

inline struct matrix2 qpow(struct matrix2 a,int b)
{
	struct matrix2 ans;
	ans.m=ans.n=2;
	ans.a[1][1].init(n,1);ans.a[1][2].init(n,0);
	ans.a[2][1].init(n,0);ans.a[2][2].init(n,1);
	while (b)
	{
		if (b&1) ans=ans*a;
		a=a*a;b>>=1;
	}
	return ans;
}

int main()
{
	n=read<int>();k=read<int>();mod=read<int>();
	A.n=n;A.m=n;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			A.a[i][j]=read<int>();
	tmp.n=2;tmp.m=2;
	tmp.a[1][1]=A;        tmp.a[1][2].init(n,1);
	tmp.a[2][1].init(n,0);tmp.a[2][2].init(n,1);
	f.n=2;f.m=1;
	f.a[1][1]=A;f.a[2][1]=A;
	tmp=qpow(tmp,k-1);
	f=tmp*f;
	f.a[1][1].print();
	return 0;
}

• Re:矩阵快速幂 (2004) liaoshuai 2022-11-24 20:07:41