2247010_ac_2403ms_2860k.cpp

北大大牛代码 1240道题的原代码 超级权威

//设f[n]=A^1+A^2+....A^n;
//当n是偶数,f[n]=f[n/2]+f[n/2]*A^(n/2);
//但n是奇数,f[n]=f[n-1]+A^(n);
# include <stdio.h>

int n, m;
long k;
typedef struct node
{
	int	matrix[31][31];
}Mat;

Mat M;

Mat add(Mat a,Mat b)
{
	int i, j;

	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			a.matrix[i][j] = (a.matrix[i][j] + b.matrix[i][j])%m;
	return a;
}

Mat muti(Mat a,Mat b)
{
	Mat c;
	int i, j, k, tmp;

	for(i = 0; i < n; i++)
		for(k = 0; k < n; k++)
		{
			tmp = 0;
			for(j = 0; j < n; j++)
				tmp += a.matrix[i][j]*b.matrix[j][k], tmp%=m;
			c.matrix[i][k] = tmp;
		}
	return c;
}

Mat power(Mat a,long n)
{
	if(n==1)
		return a;
	if(n%2)
		return muti(power(a,n-1),a);
	else
		return power(muti(a,a),n/2);
}

Mat cal(long n)
{
	if(n==1)
		return M;
	if(n%2)
		return add(cal(n-1),power(M,n));
	else
	{
		Mat tmp;
		tmp = cal(n/2);
		return add(tmp,muti(tmp,power(M,n/2)));
	}
}

void input()
{
	int i, j;

	scanf("%d%ld%d",&n,&k,&m);
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			scanf("%d",&M.matrix[i][j]);
}

void output(Mat tmp)
{
	int i, j;

	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
		{
			printf("%d",tmp.matrix[i][j]);
			if(j==n-1)
				printf("\n");
			else
				printf(" ");
		}
}

void solve()
{
	Mat tmp;

	tmp = cal(k);
	output(tmp);
}

int main()
{
	input();
	solve();
	return 1;
}