poj3233

令B={ A A}

{O E}

那么B^k={A A+A^2+A^3...A^K}

{O E}

代码：

#include<stdio.h>
const int NUM=60;
int n,k,m;
struct Matrix
{
	int data[NUM][NUM];
	Matrix operator =(Matrix a)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<2*n;j++)
			{
				data[i][j]=a.data[i][j];
			}
		}
		copy();
	}
	Matrix operator *(Matrix b)
	{
		Matrix c;
		for(int i=0;i<2*n;i++)
		{
			for(int j=0;j<2*n;j++)
			{
				int sum=0;
				for(int k=0;k<2*n;k++)
				{
					sum+=data[i][k]*b.data[k][j];
					sum=sum%m;
				}
				c.data[i][j]=sum;
			}
		}
		c.copy();
		return c;
	}
    void copy()
	{

		for(int i=n;i<2*n;i++)
		{
			for(int j=0;j<n;j++)
			{
				data[i][j]=0;
			}
			for(int j=n;j<2*n;j++)
			{
				if(i==j)
					data[i][j]=1;
				else
					data[i][j]=0;
			}
		}
	}	
	void setE()
	{
		for(int i=0;i<2*n;i++)
		{
			for(int j=0;j<2*n;j++)
			{
				if(i==j)
					data[i][j]=1;
				else
					data[i][j]=0;
			}
		}
	}
	void print()
	{
		for(int i=0;i<n;i++)
		{
			for(int j=n;j<2*n;j++)
			{
				printf("%d ",data[i][j]);
			}
			printf("\n");
		}
		//printf("\n");
	}
}input,output;
int main()
{

	freopen("input.txt","r",stdin);

	while(scanf("%d %d %d",&n,&k,&m)!=EOF)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				scanf("%d",&input.data[i][j]);
				input.data[i][j+n]=input.data[i][j];
				input.copy();
			}
		}
		Matrix temp=input;
		output.setE();
		//input.print();
		//output.print();
		while(k>0)
		{
			if(k&1)
			{
				output=(output*temp);
				//(output*temp).print();
			}
			temp=temp*temp;
			//temp.print();
			k=k>>1;
			//output.print();
		}
		output.print();

	}
	return 0;
}